Advent of Code

[Greenbank]

Day 7: That was ok. Dependencies and scheduling.

What's scary, apart from the two syntax errors (missing parens), is both parts produced the correct answer first time without needing any tweaks.

[Ben T]

Done day 7 in Java but I might do it again in .NET with an actual thread to represent each worker.
https://github.com/bjtaylor1/AoC2018/blob/master/Day07/src/main/java/com/bjt/App.java

[Pickled Onion]

Day 7: That was ok. Dependencies and scheduling.

What's scary, apart from the two syntax errors (missing parens), is both parts produced the correct answer first time without needing any tweaks.

Bah. I got the code correct but typed in the wrong starting parameters for part 2 then spent ages implementing a "fix" to the logic

[Diver300]

Day 8. The first part didn't take me too long. For the second part, the example given didn't find a lot of the mistakes in my code.

[Greenbank]

Both bits of day 8 simple, made considerably easier by the fact that perl arrays automatically return a blank entry (interpreted as 0 in an integer context) for uninitialized elements, no need for any kind of bounds checking.

Was hoping for something a bit meatier at the weekend. We'll see tomorrow...

[David Martin]

Day 8. The first part didn't take me too long. For the second part, the example given didn't find a lot of the mistakes in my code.

This - took a wee while for the code to run.

(click to show/hide)

I kept track of forward and reverse dependencies, removing the node from the list of things waiting on something else when their dependencies were scheduled. A silly mistake or two led to some frustration.

(click to show/hide)

Late at night, much thinking but I got the basics sorted in my head, then sorted it this morning. Keep track of the worker pool. Remove from the pool all that finish at the current min finish time. Add in as many as are available to take up the extra space. Move on to the next finish time. At the end I just have one task and finish time left which is the right answer.

[David Martin]

And day 8 - the first really fun one. Ran extremely rapidly, so much so that I thought I had an error

(click to show/hide)

Classic recursive function on a data structure. I put the data points in an array and tracked where everything was, storing the cumulative meta sum in each node (which made summation easy as it is built).

(click to show/hide)

Walk back down the tree with another recursive function, calculating the value as you go - very fast again.

[Greenbank]

(click to show/hide)

No need for a tree structure or do multiple passes. Just one recursive function.

Code: http://www.greenbank.org/misc/aoc/2018_8b_pl.txt

[David Martin]

(click to show/hide)

No need for a tree structure or do multiple passes. Just one recursive function.

Code: http://www.greenbank.org/misc/aoc/2018_8b_pl.txt

(click to show/hide)

I kept the recursively built tree because I had a suspicion it would be useful for the second half, which it was.
As it was the code took fractions of a second to run.

 

[Pickled Onion]

(click to show/hide)

No need for a tree structure or do multiple passes. Just one recursive function.

Code: http://www.greenbank.org/misc/aoc/2018_8b_pl.txt

The hardest part of that was understanding the instructions. My version was similar to yours with added fluff.

(click to show/hide)

$r+=$cnvals[$mdvals[$ct]-1];   # Abuse perl's lack of bounds checking and uninitialised array elements return 0

Isn't there a danger here, you could get $cnvals[-1] instead of zero? My puzzle input didn't have such a case, so it didn't matter either way.

[David Martin]

OK, here is my python version for day 8 - not so different.

(click to show/hide)

Code: [Select]

data = [int(x) for x in open('day8.txt').read().split()]

def readnode(pos):
    node = {'nodes':[], 'meta':[], 'start':pos, 'end':pos+1, 'metasum':0}
    node['nodecount']=data[pos]
    node['metacount']=data[pos+1]
    pos=pos+2
    for i in range(node['nodecount']):
        newnode=readnode(pos)
        pos=newnode['end']+1
        node['nodes'].append(newnode)
        node['metasum']+= newnode['metasum']
    node['meta']=data[pos:pos+node['metacount']]
    node['metasum']+=sum(node['meta'])
    node['end']=pos+node['metacount']-1
    return node

tree = readnode(0)
print(tree['metasum'])

And as the tree structure was still there for the second part.

(click to show/hide)

Code: [Select]

def nodevalue(node):
    value=0
    if len(node['nodes']):
        for n in node['meta']:
            if n and n<=len(node['nodes']):
                value+=nodevalue(node['nodes'][n-1])
    else:
        value=sum(node['meta'])
    return value

print(nodevalue(tree))


[Greenbank]

Aha. Day 9 starts to make it really interesting.

(click to show/hide)

Naive implementation for part one took 4 and a half minutes. Not even going to try it for part two as it'll just be bonkers.

Need to rewrite it to be more efficient but that'll have to wait as I'm taking my family out for brunch and then buying a Christmas tree...

[Greenbank]

(click to show/hide)

$r+=$cnvals[$mdvals[$ct]-1];   # Abuse perl's lack of bounds checking and uninitialised array elements return 0

Isn't there a danger here, you could get $cnvals[-1] instead of zero? My puzzle input didn't have such a case, so it didn't matter either way.

(click to show/hide)

Good point! Guess I was just lucky as that could have been a real bugger to catch!

[Pickled Onion]

Part 1.

Frustrating out-by-one error gave the correct answer for all but one of the examples. Implementing the instructions as written, array-splicing all the way, ran in sub-second.

Part 2.

No idea. Times ten ran in about a minute. Times 100 - forget it. Can't see the pattern or formula.

[Greenbank]

(click to show/hide)

Left original version (in perl using array slicing/splicing) running whilst I was out for brunch and lugging a Christmas tree home, just to see how far it would go.

7399s and it had got to marble 270,000 out of  ~7,000,000, so about 4% of the way through. Ha!

Rewrote it in C using a double linked list (so no array copying/slicing/splicing which is very expensive) and it gives the answer for part b in 0.259s (part a in 0.009s).

Using some really big marble numbers (100 million):-

$ time ./9 429 100000000
664880331050

real    0m2.921s
user    0m2.174s
sys     0m0.749s

[EDIT] Reimplemented in perl using a double linked list, a bit slower at 10.314s for my final puzzle input (last marble ~7 million).

[Diver300]

Part 1.

Frustrating out-by-one error gave the correct answer for all but one of the examples. Implementing the instructions as written, array-splicing all the way, ran in sub-second.

Part 2.

No idea. Times ten ran in about a minute. Times 100 - forget it. Can't see the pattern or formula.

As above.

Put a progress counter on and realised that 100 times would take hours and hours.

Had to go out and do real stuff and it was done by the time I came home.

I also tried to code a time-saving routine but I didn't get that to work before I had to go out.

edit:- corrected my time-saving routine and it ran in about 20 minutes. It is still O(n²).

(click to show/hide)

If there's an array of marble values, inserting one means moving many up by 1 which is slow. If 22 consecutive non-scoring moves are done with one move, it's much faster.

[David Martin]

(click to show/hide)

Left original version (in perl using array slicing/splicing) running whilst I was out for brunch and lugging a Christmas tree home, just to see how far it would go.

7399s and it had got to marble 270,000 out of  ~7,000,000, so about 4% of the way through. Ha!

Rewrote it in C using a double linked list (so no array copying/slicing/splicing which is very expensive) and it gives the answer for part b in 0.259s (part a in 0.009s).

Using some really big marble numbers (100 million):-

$ time ./9 429 100000000
664880331050

real    0m2.921s
user    0m2.174s
sys     0m0.749s

[EDIT] Reimplemented in perl using a double linked list, a bit slower at 10.314s for my final puzzle input (last marble ~7 million).

(click to show/hide)

D'oh. The original (using array splicing) was fractions of a second. The *100 was much much slower and obviously an exponential slowdown.
Rewriting it as a double linked list was not much extra code, and ran in O(n) rather than O(n^2)

[Ben T]

(click to show/hide)

Left original version (in perl using array slicing/splicing) running whilst I was out for brunch and lugging a Christmas tree home, just to see how far it would go.

7399s and it had got to marble 270,000 out of  ~7,000,000, so about 4% of the way through. Ha!

Rewrote it in C using a double linked list (so no array copying/slicing/splicing which is very expensive) and it gives the answer for part b in 0.259s (part a in 0.009s).

Using some really big marble numbers (100 million):-

$ time ./9 429 100000000
664880331050

real    0m2.921s
user    0m2.174s
sys     0m0.749s

[EDIT] Reimplemented in perl using a double linked list, a bit slower at 10.314s for my final puzzle input (last marble ~7 million).

similar to mine but C++ is far easier than plain C...
https://github.com/bjtaylor1/AoC2018/blob/master/Day09/Day09.cpp
 (link contains spoiler)

runs in a fraction of a second for my x100 input.

[Diver300]

I found day 10 straightforward.

(click to show/hide)

I realised that y dimension (and probably the x) would be a minimum when the message was legible, so I ran the movements until the y was a minimum.

I didn't try to get the computer to read the result.

For part 2, I had already counted the cycles to give me a way out of the loop if when it got too far before my code worked correctly.

[Ben T]

I found day 10 straightforward.

(click to show/hide)

I realised that y dimension (and probably the x) would be a minimum when the message was legible, so I ran the movements until the y was a minimum.

I didn't try to get the computer to read the result.

For part 2, I had already counted the cycles to give me a way out of the loop if when it got too far before my code worked correctly.

(click to show/hide)

The first time all points are next to at least one other worked for me (and an additional check that no point is at the same location as another, but which may have been unnecessary).
A lower case "i" could have spannered that but the test message was in upper case so I figured that wouldn't happen!

[Greenbank]

(click to show/hide)

Minimal area of bounding box for me.

Off by one for part 2 though, realised it as soon as I hit submit on my answer and had to wait 60s to enter n+1.

Would have been much trickier if they'd included one or more stray points.

[Ben T]

(click to show/hide)

Minimal area of bounding box for me.

Off by one for part 2 though, realised it as soon as I hit submit on my answer and had to wait 60s to enter n+1.

Would have been much trickier if they'd included one or more stray points.

I thought of a statistical approach like that but the issue I had is how do you test a scenario in isolation?

e.g. you might have a series of bounding box areas like: 56, 54, 57, 53, 13, 54.
it's clear that 13 (t=4) is the minimum, and probably the answer - but when you get to 54 (t=1), that is the lowest so far, and so is 53 (t = 3).

How do you come to the conclusion that you have definitely reached the answer without false positives, or reading past the answer?

It's interestingly similar to the type of cryptography where a brute force attack doesn't know when it's got to the right answer, because the secret encrypted with the 'wrong' key looks 'sensible' to a computer. Not sure exactly how it works or how successful it is.

[Greenbank]

(click to show/hide)

I'd assumed that it would be at the minimum area of the local bounding box so the time to stop searching would be when you get a minimal bounding box that has an area that is larger than the lowest value seen so far.

In other words, once you'd passed the correct point the area of the bounding box would only grow again, so it's easy to detect.

As long as you know the time value for the minimum point you can compute what it looks like without needing to do any of the intermediate steps (or just go one step back).

In the end I didn't bother making it back up one or recompute it, I just ran it once to find out what the minimum area was and then edited the program to print the grid when the bounding box area is below a certain size.

I'd based all this on an assumption that the puzzles would have been generated by taking a grid representation of a string of characters, adding a random x and y offset (so that they aren't close to 0,0), giving each point a random velocity and then applying a random number of iterations to explode them outwards. This is how I'd generate the puzzles if it was me doing that side of things.

Code: [Select]

...
t=10270 171 85 222 183 sizes=3354
t=10271 166 90 217 188 sizes=2204
t=10272 163 95 212 193 sizes=1292
t=10273 161 100 207 198 sizes=549
-------------t=10273------------------
.####...######..#....#..#....#...####....####....####...#....#
#....#..#.......##...#..#...#...#....#..#....#..#....#..#....#
#.......#.......##...#..#..#....#.......#.......#.......#....#
#.......#.......#.#..#..#.#.....#.......#.......#.......#....#
#.......#####...#.#..#..##......#.......#.......#.......######
#..###..#.......#..#.#..##......#.......#..###..#..###..#....#
#....#..#.......#..#.#..#.#.....#.......#....#..#....#..#....#
#....#..#.......#...##..#..#....#.......#....#..#....#..#....#
#...##..#.......#...##..#...#...#....#..#...##..#...##..#....#
.###.#..#.......#....#..#....#...####....###.#...###.#..#....#
t=10274 166 95 212 193 sizes=1349

So it sees a minimum value of 549 and then stops on the next iteration as the area has gone up to 1349.

Obviously if this hadn't worked I would have done something different, such as print the grids for the 3 or 4 iterations either side of the local minima. It's possible to create inputs that explode the points out in such a way that the message is not the local minima (either by x, y or bounding box area), indeed it's possible to produce inputs that will spell out a message but at one point in time every point has exactly the same position x and y.

Eric tends not to be so cruel, at least not this early on in the challenge.

[Greenbank]

(click to show/hide)

For example, try this input:-

Code: [Select]

position=<  -803,   948> velocity=<   5,  -6>
position=<  -927,   948> velocity=<   6,  -6>
position=< -1671,   824> velocity=<  12,  -5>
position=<   437,   576> velocity=<  -5,  -3>
position=<  1057,   824> velocity=< -10,  -5>
position=<  -555,   700> velocity=<   3,  -4>
position=<  -803,   576> velocity=<   5,  -3>
position=< -1423,   576> velocity=<  10,  -3>
position=<   -59,   700> velocity=<  -1,  -4>
position=< -1671,   948> velocity=<  12,  -6>
position=<  -927,   700> velocity=<   6,  -4>
position=<   933,  1072> velocity=<  -9,  -7>
position=<  1181,   824> velocity=< -11,  -5>
position=<   933,   824> velocity=<  -9,  -5>
position=<  1305,   824> velocity=< -12,  -5>
position=< -1051,  1072> velocity=<   7,  -7>
position=<   933,   700> velocity=<  -9,  -4>
position=< -1795,   700> velocity=<  13,  -4>
position=<   189,  1196> velocity=<  -3,  -8>
position=<   -59,   824> velocity=<  -1,  -5>
position=<  1181,   576> velocity=< -11,  -3>
position=< -1051,   948> velocity=<   7,  -6>
position=<  -555,   948> velocity=<   3,  -6>
position=<  1305,   576> velocity=< -12,  -3>
position=<    65,  1196> velocity=<  -2,  -8>
position=<   -59,  1072> velocity=<  -1,  -7>
position=< -1051,   824> velocity=<   7,  -5>
position=< -1051,  1196> velocity=<   7,  -8>
position=< -1919,   576> velocity=<  14,  -3>
position=<  1553,   576> velocity=< -14,  -3>
position=<  -431,   824> velocity=<   2,  -5>
position=<  1429,   824> velocity=< -13,  -5>
position=<   313,   576> velocity=<  -4,  -3>
position=<   313,  1196> velocity=<  -4,  -8>
position=< -1671,  1072> velocity=<  12,  -7>
position=<  -431,   948> velocity=<   2,  -6>
position=<  -679,   576> velocity=<   4,  -3>
position=<   437,  1196> velocity=<  -5,  -8>
position=<  1057,   576> velocity=< -10,  -3>
position=<  -431,  1072> velocity=<   2,  -7>
position=<  1429,   576> velocity=< -13,  -3>
position=<  -431,  1196> velocity=<   2,  -8>
position=< -1547,   700> velocity=<  11,  -4>
position=<   933,  1196> velocity=<  -9,  -8>
position=<   933,   948> velocity=<  -9,  -6>
position=<   933,   576> velocity=<  -9,  -3>
position=<    65,   576> velocity=<  -2,  -3>
position=<  -679,   948> velocity=<   4,  -6>
position=< -1671,  1196> velocity=<  12,  -8>
position=<   -59,   948> velocity=<  -1,  -6>
position=<   561,  1072> velocity=<  -6,  -7>
position=<   561,   700> velocity=<  -6,  -4>
position=<   189,   576> velocity=<  -3,  -3>

The answer isn't at the minima of area or x or y, but it's obviously very close.

[Ben T]

(click to show/hide)

I'd assumed that it would be at the minimum area of the local bounding box so the time to stop searching would be when you get a minimal bounding box that has an area that is larger than the lowest value seen so far.

In other words, once you'd passed the correct point the area of the bounding box would only grow again, so it's easy to detect.

As long as you know the time value for the minimum point you can compute what it looks like without needing to do any of the intermediate steps (or just go one step back).

In the end I didn't bother making it back up one or recompute it, I just ran it once to find out what the minimum area was and then edited the program to print the grid when the bounding box area is below a certain size.

I'd based all this on an assumption that the puzzles would have been generated by taking a grid representation of a string of characters, adding a random x and y offset (so that they aren't close to 0,0), giving each point a random velocity and then applying a random number of iterations to explode them outwards. This is how I'd generate the puzzles if it was me doing that side of things.

Code: [Select]

...
t=10270 171 85 222 183 sizes=3354
t=10271 166 90 217 188 sizes=2204
t=10272 163 95 212 193 sizes=1292
t=10273 161 100 207 198 sizes=549
-------------t=10273------------------
.####...######..#....#..#....#...####....####....####...#....#
#....#..#.......##...#..#...#...#....#..#....#..#....#..#....#
#.......#.......##...#..#..#....#.......#.......#.......#....#
#.......#.......#.#..#..#.#.....#.......#.......#.......#....#
#.......#####...#.#..#..##......#.......#.......#.......######
#..###..#.......#..#.#..##......#.......#..###..#..###..#....#
#....#..#.......#..#.#..#.#.....#.......#....#..#....#..#....#
#....#..#.......#...##..#..#....#.......#....#..#....#..#....#
#...##..#.......#...##..#...#...#....#..#...##..#...##..#....#
.###.#..#.......#....#..#....#...####....###.#...###.#..#....#
t=10274 166 95 212 193 sizes=1349

So it sees a minimum value of 549 and then stops on the next iteration as the area has gone up to 1349.

Obviously if this hadn't worked I would have done something different, such as print the grids for the 3 or 4 iterations either side of the local minima. It's possible to create inputs that explode the points out in such a way that the message is not the local minima (either by x, y or bounding box area), indeed it's possible to produce inputs that will spell out a message but at one point in time every point has exactly the same position x and y.

Eric tends not to be so cruel, at least not this early on in the challenge.

(click to show/hide)

I get your idea, but surely did you not still get a lot of false positives early on?
e.g. in my example where the areas go  56, 54, 57, 53, 13, 54.
Your code would have identified 57 as the first "bounding box that has an area that is larger than the lowest value seen so far".
And would have printed the scenario with 54 as the answer.