Advent of Code

[Greenbank]

Day 7:

(click to show/hide)

I overengineered my first attempt as I expected some caching to be required to avoid a lengthy execution.

I just thinned it down to a basic naive implementation (that only stores individual weight and parent name for each node) and recursively calculates everything else with no caching and it ran in under 2 seconds (the version that calculates total weights for each node and stores them runs instantaneously).

[David Martin]

Day 7:

(click to show/hide)

I overengineered my first attempt as I expected some caching to be required to avoid a lengthy execution.

I just thinned it down to a basic naive implementation (that only stores individual weight and parent name for each node) and recursively calculates everything else with no caching and it ran in under 2 seconds (the version that calculates total weights for each node and stores them runs instantaneously).

(click to show/hide)

No child node storage?
The first one required the parent nodes to be calculated. The second was a straightforward depth first search which requires knowing the child nodes (but not the parents)
I built the tree, then established how n-ary it was (distribution of number of children by node). This indicated the approach for the depth-first search. (check total masses of the children are equal, else squeal and report.)

[Greenbank]

Day 7:

(click to show/hide)

No child node storage?
...

(click to show/hide)

For every node I was just keeping track of its weight and its parent, i.e.

B (8)
  weight(B)=8
D (20) -> A, B, C
  weight(D)=20 ; parent(A)=D ; parent(B)=D ; parent(C)=D
A (10)
  weight(A)=10
C (10)
  weight(C)=10

The answer to part (a) is simply the node that does not have a parent, trivial to find. It's doable in a command line for example:-

Code: [Select]

$ cat inp.simp | sed -e 's/ -> \(.*\)/ -> \1, \1/' -e 's/ ([0-9]*)//' -e 's/ -> /\n/' -e 's/, /\n/g' |  sort | uniq -u
tknk

You can find the children of a node (i.e. D) by searching all nodes that have it (D) as their parent. Avoids needing anything other than 1:1 mappings but is wasteful to loop through every node when you want to find a few children but since the input space was not too large it wasn't a problem. Likewise calculating the total weights of each of the children of the current node being searched, that involves lots of duplication along the branches that are unbalanced but, again, it wasn't a problem with the final input.

Since I do most of my day to day programming in C where there are no built-in 1-to-many data structures I often initially attempt solve problems using just 1:1 data structures where possible (caveat performance at scale), this was a good example of that. Performance (and programming) is way faster with a list structure (let alone dict/hash/etc), but it's fun to do things without those kinds of extras.

[David Martin]

That reminds me of the reddit competition to find the most ridiculous way to test if a number was even or odd.
It is order(N) for every lookup, making it approach order (N^2) overall.

(click to show/hide)

By keeping the child references, the depth first search is easy.
node[n] = {parent:, children:, mass:, nodemass: }
Any randomly selected node will give you very rapidly the head node in log(N) time.
Then recursively calculate the node masses till you find the unbalanced one.

[Ben T]

did it in a probably over verbose OO way https://github.com/bjtaylor1/AoC2017/blob/day07part2/Day07/App.cs but didn't take long and was basically shot from the hip and didn't require any debugging to get right pretty much first time

[Greenbank]

Day 7:

(click to show/hide)

If you want some mostly uncommented perl then snigger away:-

http://www.greenbank.org/misc/aoc/2017_7.txt

(I'm generally aiming for the answer as quickly as possible, not aiming for well commented, understandable or easily maintained code.)

The children() function can be easily modified to use the non-optimised version that loops through every node to find the children.

[David Martin]

OK, here is my python

(click to show/hide)

Code: [Select]

fh = open('Downloads/input7.txt')
for line in fh.readlines():
    f = line.strip().split()
    node = f[0]
    mass = int(f[1][1:-1])
    nodes[node] = nodes.get(node,{})
    nodes[node]['mass'] = mass
    if len(f)> 2:
        child = [c.replace(',','') for c in f[3:]]
        nodes[node]['children']= child
        for c in child:
            nodes[c] = nodes.get(c, {})
            nodes[c]['parent'] = node

n = list(nodes.keys())[0]
while nodes[n].get('parent', None ) != None:
    n = nodes[n]['parent']
   
print(n)
headnode=n

orders = {}
for n in nodes.keys():
    o = len(nodes[n].get('children',[]))
    orders[o]= orders.get(o,0)+1
print(orders)
       
def get_mass(n):
    childmasses = []
    kinder = nodes[n].get('children', [])
    for k in kinder:
        childmasses.append(get_mass(k))
    if  len(set(childmasses)) == 2:
        for k in kinder:
            print(n, k, nodes[k]['nodemass'], nodes[k]['mass'])       
    cm = 0
    if len(childmasses)>0:
        cm = sum(childmasses)
    nodes[n]['nodemass'] = cm+nodes[n]['mass']
    return nodes[n]['nodemass']
   
get_mass(headnode)



[David Martin]

Day 7:

(click to show/hide)

If you want some mostly uncommented perl then snigger away:-

http://www.greenbank.org/misc/aoc/2017_7.txt

(I'm generally aiming for the answer as quickly as possible, not aiming for well commented, understandable or easily maintained code.)

The children() function can be easily modified to use the non-optimised version that loops through every node to find the children.

can you not (instead of the two cases) do:
my @c = split /\W*/, $x
my $n = unshift @c
my $w = unshift @c
if @c {
unshift @c
foreach my $child (@c) { ...}

to save repeating the code for the assignment of the first two lines.

[Greenbank]

can you not (instead of the two cases) do:

Almost certainly, but that file was pretty much the first thing that gave me the correct answer (whether it prints it explicitly like mine, or gives enough information to work out the answer like yours). I don't bother polishing it once I've submitted a correct answer. If I was going to use it for anything else in the future then I'd spend some time refactoring it and adding suitable comments. I'd also consider how it would handle much larger inputs.

The last thing I want to be doing is chasing bugs in the code that reads the input, so I've no problem with a bit of duplication there.

[EDIT] It's only when the problems start to get properly challenging that I will take more care on my programs. My goal is to get the answer as quickly as possible (and in a reasonable execution time). The competition is not really making me learn anything new (if you want that then the Valladolid Online Judge or Project Euler are much better).

[Pickled Onion]

My goodness I made a meal out of that one. Must remember to read the question properly 

[David Martin]

Thanks for the links to Project Euler and the Valladolid Judge sites. Interesting challenges though the sites are not terribly clear on how they work.

[Greenbank]

Valladolid was submit your code by email (at least when I was doing it back in 2001!). The automated system then sanitised it (to make sure you weren't doing anything silly or destructive) and then ran the code against an unseen input.

Their trick was the example inputs you got given on the website were a fraction of the size of the real input (which you never saw), or the real input was the pathological case for the standard algorithm.

So many times I'd be confident about my code, email it off, only to receive a "Time Limit Exceeded" response.

Can't remember much about Project Euler, only did one or two but I discussed a lot of the problems with someone from work I was mentoring.

Day 8: Will it be another fake CPU question (I do like them) or something like a knapsack or another TSP-esque classic?

[David Martin]

We have had the first tree traversal one. Must be some magic codes to parse (medicine for rudolf). Still in early days so shouldn't be too taxing (hostage to fortune there).

[Diver300]

Day 7
Solved with a spreadsheet. It did get quite big but not as large as many I written that have a more serious purpose.

[David Martin]

I cannot imagine voluntarily choosing to do it that way. It makes me cringe even thinking about it.

[Oaky]

Day 7 p2 is still not done.

RL has got in the way -- I can see two ways of attacking it, both of which should work, but haven had the time yet to give either a go.

(click to show/hide)

one is recursive, and one isn't.

I've learned from older AoC (but especially from the Synacor challenge) to be wary of jumping in with the obvious recursive solution in a language with insufficient stack limits, but looking at the longest path in the tree (which is, nicely, a directed acyclic graph), it seems that recursion here should be more than safe)

[David Martin]

Recursion works when recursion works.
What is the non-recursive approach?

[Diver300]

I cannot imagine voluntarily choosing to do it that way. It makes me cringe even thinking about it.

There towers are only 6 levels high, so finding a group of formulas that works, and copying across until there are no more sub-towers doesn't take long
The spreadsheet was 6000 lines long, as each step ended up at 9 lines. In retrospect 10 would have been easier on the brain.

[Diver300]

Day 8 didn't seem all that difficult.

(click to show/hide)

Transpose into Javascript. Add a line for each step to get the maximum.

[David Martin]

Pretty much

(click to show/hide)

With python (and perl) you can store references to functions in hashes so I just put the symbols in as keys. There is a more OO approach but this morning ICBA.

[Greenbank]

Day 8:

(click to show/hide)

Transpose...

(click to show/hide)

ooh, what a horrid idea...

Part a:-

Code: [Select]

cat inp.simp | ( sed -e 's/^/$r{/' -e 's/ inc /}+=/' -e 's/ dec /}-=/' -e 's/ if \([a-z]*\)/ if $r{\1}/' -e 's/ if ([a-z]+)/ if $r{&}/' -e 's/$/;/' ; echo "@a=sort { \$b <=> \$a } values %r;print \@\$a[0]\n\";" ) | perl
10

Part b:-

Code: [Select]

cat inp.simp | ( echo "\$l=-9999999999;" ; sed -e 's/^/$r{/' -e 's/ inc /}+=/' -e 's/ dec /}-=/' -e 's/ if \([a-z]*\)/ if $r{\1}/' -e 's/ if ([a-z]+)/ if $r{&}/' -e 's/$/;/' -e 's/^\(\$r{[a-z]*}\).*$/&; \$l=\1 if( \1 > \$l );/' ; echo "print \"\$l\n\";" ) | perl
10


[Ben T]

self contained dynamic compilation https://github.com/bjtaylor1/AoC2017/blob/day08part2/Day08/Program.cs
essentially the same, my TranslateCode function is your line of sed and my main function is orchestrating the running of it.

[Greenbank]

Day 8: Will it be another fake CPU question (I do like them) or something like a knapsack or another TSP-esque classic?

And, lo, it was a fake CPU type question.

I wrote an interpreter for my solution before doing the above horrific command line transpose nonsense.

Will we get a couple of biggies to do over the weekend? I hope so!

[Oaky]

Finally got round to doing day 7 part 2.  (after knocking out day 8 )

(click to show/hide)

networkx FTW!

Since it is a DAG, nx.descendents() comes in very handy.

(click to show/hide)

I decided to make my interpreter a little more general than was strictly necessary for the description/input program that I had.

whereas the test data (and my input, as far as a quick visual scan of it can tell) is always of the pattern

<register1> <operation> <integer1> if <register2> <comparator> <integer2>

I coded as if <integer1>, <integer2> and <register2> could all be either integers OR registers. (essentially,  I first try to feed them through int() and only if that throws an exception do I treat them as register names)

(click to show/hide)

[Ben T]

(click to show/hide)

I coded as if <integer1>, <integer2> and <register2> could all be either integers OR registers. (essentially,  I first try to feed them through int() and only if that throws an exception do I treat them as register names)

I thought that was what the difference between parts 1 and 2 was going to be, but decided not to pre-empt, and it wasn't.