Advent of Code

[Greenbank]

Off by one in your iteration count?

Nope, more serious than that, but I got it (took me about 20 minutes to find it but I've been doing some real work for the last couple of hours). 43 minutes from submitting part (a) to submitting part (b). Ugh.

(click to show/hide)

Added some test cases for the various functions.
My rotate/flip functions where fine, but I had functions to split up a big grid into smaller grids and also combine the smaller resulting grids into one big grid again.
split: ABC/DEF/GHI -> A,B,C,D,E,F,G,H,I
combine: A,B,C,D,E,F,G,H,I -> ABC/DEF/GHI

x wasn't the same as combine(split(x)). I'd flipped the x and y coordinates in the combine routine and it was doing:-

split: ABC/DEF/GHI -> A,B,C,D,E,F,G,H,I
combine: A,B,C,D,E,F,G,H,I -> ADG/BEH/CFI

With it fixed it produced the right answer. It didn't affect the answer of the output up to 5 iterations.

I'm wondering about optimisations now, mine isn't particularly fast (48s) as most of the time is spent splitting and combining strings. Of course # and . translate well to binary so I'm tempted to try implement it with bit bashing but that will be interesting with the boxes being split across multiple rows.

I got a reasonable speed up (113s to 48s) by adding rules for each of the translations as I found them, i.e. if there is no rule for x but there is for rotate(fliph(x)) -> Z then add x -> Z as a rule.
[EDIT] It doesn't get any noticably faster (well from 48s to 47s) by adding all of the rules/transformations at the start when reading the input (so no need to do any during the iterations).

So it's my storage method and implementation of the conversions/manipulations that is particularly slow.

[Oaky]

Off by one in your iteration count?

Nope, more serious than that, but I got it (took me about 20 minutes to find it but I've been doing some real work for the last couple of hours). 43 minutes from submitting part (a) to submitting part (b). Ugh.

(click to show/hide)

Added some test cases for the various functions.
My rotate/flip functions where fine, but I had functions to split up a big grid into smaller grids and also combine the smaller resulting grids into one big grid again.
split: ABC/DEF/GHI -> A,B,C,D,E,F,G,H,I
combine: A,B,C,D,E,F,G,H,I -> ABC/DEF/GHI

x wasn't the same as combine(split(x)). I'd flipped the x and y coordinates in the combine routine and it was doing:-

split: ABC/DEF/GHI -> A,B,C,D,E,F,G,H,I
combine: A,B,C,D,E,F,G,H,I -> ADG/BEH/CFI

With it fixed it produced the right answer. It didn't affect the answer of the output up to 5 iterations.

I'm wondering about optimisations now, mine isn't particularly fast (48s) as most of the time is spent splitting and combining strings. Of course # and . translate well to binary so I'm tempted to try implement it with bit bashing but that will be interesting with the boxes being split across multiple rows.

I got a reasonable speed up (113s to 48s) by adding rules for each of the translations as I found them, i.e. if there is no rule for x but there is for rotate(fliph(x)) -> Z then add x -> Z as a rule.
[EDIT] It doesn't get any noticably faster (well from 48s to 47s) by adding all of the rules/transformations at the start when reading the input (so no need to do any during the iterations).

So it's my storage method and implementation of the conversions/manipulations that is particularly slow.

(click to show/hide)

fun with functions and composition etc.

My solution took 14s for part 2.

I pre-generated all the rotated/flipped rules and used a list of lists of chars for the grids and a list of lists of grids when splitting.

I particularly enjoyed making the symmetry transformations as function compositions...

Code: [Select]

def compose(f,g):
    def new(x):
        return f(g(x))
    return new

def vflip(g):
    return list(reversed(g))

def hflip(g):
    return list(map(lambda x: list(reversed(x)), g))

def transpose(g):
    return list(map(list, zip(*g)))

def e(g):
    # identity element
    return g

r90 = compose(transpose, vflip)
r180 = compose(hflip, vflip)
r270 = compose(transpose, hflip)
neswflip = compose(vflip, r90)
nwseflip = compose(hflip, r90)

all_transforms = [e, r90, r180, r270, hflip, vflip, neswflip, nwseflip] # symmetry group of square

def fapply(flist, arg):
    '''apply a list of functions to an argument, returning the list of results
    fapply([f, g, h], x) => [f(x), g(x), h(x)]'''
    return list(map(lambda x: x(arg), flist))

https://github.com/MarkNOakden/AdventOfCode/blob/master/17/21/day21.ipynb

[Greenbank]

Down to 30s for 21.b. I'd left my test code in there so I was doubling up on the expensive split/combine work for each iteration.

Will work on ways to get this down to <1s if I can in-between bouts of RealWork(TM).

[EDIT] 17s after simplifying some of the steps, still a way to go.
[EDIT] 15.38s and I think I know how to remove a lot of the complexity from here
[EDIT] 5.23s and much simpler now too, enthusiasm for further refactoring is waning

[David Martin]

Calculating part 2 from scratch took <20secs with my rather naive implementation. Adding in the minor optimisation of adding patterns as you find them took it down to sub 14s from scratch.

(click to show/hide)

I have a function expand(grid) that does what it says on the tin. The timing is of a loop where grid is the initial start and the loop is:

Code: [Select]

for i in range(18):
    grid = expand(grid)

print(sum([x.count('#') for x in grid]))


[Ben T]

55 seconds. Probably some optimizations but possibly marginal gains.
Was hoping it would  create a christmas tree but it didn't.

(click to show/hide)

edit: in fact definitely one optimization which could make a big difference, namely equating cache keys with similar (rotated/flipped) ones.

[Oaky]

(click to show/hide)

click for animated GIF (large file ~6MB!)

[Diver300]

Day 21, part 2 took my computer 4.637 seconds

(click to show/hide)

That's running in Javascript under Chrome on a 10 year old MacBook

I copied the 2 -> 3 transformation so that there were 16 of them, and I could convert the 4 pixels to binary and do a direct look up.

For the 3 -> 4 transformations, I wrote a rotate function and a flip function.
I converted each input pattern into a number in binary, and found which combination of rotates and flips gave the largest value.
That gave me a lookup table of largest input value to output pattern, which only had to be done once at the start of the programme. Each time I had to transform a 3x3 square, I worked out the largest value its transformed bits could represent, and the lookup of that value gave the 4x4 pattern.

For 5 iterations I got it to output a pattern, and I counted the hashes with a text editor. That didn't work for 18, but all I needed was to get the code to count the hashes and it ran reasonably quickly.

[Oaky]

(click to show/hide)

day 21 was a puzzle of the type I really like since I could define the small steps that got me closer and closer to the solutiojj an implement those incrementally (I should have done it TDD the whole way with unittest module, but didnt bother this time).

Day 20, on the other hand, is really annoying me because I think I understand it fully, and I think my code is doing exactly what I want it to do, but my answer is wrong (and also "feels" wrong - I would really expect more collisions than I'm finding, and definitely some multi-way ones.)

Code: [Select]

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
395 13 -27 530 106 -185 89 4 -17 8
401 13 -27 530 -103 -6 89 -2 -11 8

iteration       10: count = 998

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
306 30 -14 728 -9 182 74 1 14 4
314 30 -14 728 -144 12 74 -12 5 4

iteration       18: count = 996

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
471 -8 -15 700 -338 -361 37 -11 -7 1
473 -8 -15 700 547 231 37 15 6 1

iteration       35: count = 994

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
212 -49 33 72 -299 72 2 -8 4 0
213 -49 33 72 -278 -148 2 -9 -1 0

iteration       36: count = 992


[David Martin]

(click to show/hide)

I'm normally not this directionally challenged. But got there and found my initial solution was readily adaptable for part 2 with minimal changes (just the cell state change changed).

not fast but it gets there in a few seconds.

[Ben T]

(click to show/hide)

Hmm, quite easy really. I think the only challenge of day 22 relies on you not knowing how to implement a potentially infinite grid.
https://github.com/bjtaylor1/AoC2017/blob/day22part2/Day22/Program.cs

[Greenbank]

(click to show/hide)

Hmm, quite easy really. I think the only challenge of day 22 relies on you not knowing how to implement a potentially infinite grid.
https://github.com/bjtaylor1/AoC2017/blob/day22part2/Day22/Program.cs

Late to it today as I was helping set up a family party.

(click to show/hide)

I used a 1000x1000 grid and plonked the initial map starting at 500,500.

I then got the wrong answers because I started from 500,500 rather than in the middle of the supplied map as the instructions clearly state. Doh.

I was hoping it wouldn't get far enough out for 1000x1000 not to be big enough, for my puzzle input it ranges: x=[348,709] and y=[270,692] so it turned out to be a good enough guess.

[David Martin]

(click to show/hide)

I started with the original grid at 0,0 and then kept track of all the points I had visited with a hash. I first set the new cell to clear, then checked to see whether I had been there (in which case it took that value. If I hadn't visited and it was on the grid, I took the initial grid value.

It was then just a case of starting in the right place, moving in the right direction, and knowing my left from my right.

They have been a little bit samey. Maybe a new thread with some 'extra' puzzles on?

[Greenbank]

(click to show/hide)

I was expecting part (b) of today to be "what is the fewest number of steps/burts/whatever that would leave no infected nodes?" or similar. That could have been truly horrid.

[Ben T]

(click to show/hide)

I started with the original grid at 0,0 and then kept track of all the points I had visited with a hash. I first set the new cell to clear, then checked to see whether I had been there (in which case it took that value. If I hadn't visited and it was on the grid, I took the initial grid value.

It was then just a case of starting in the right place, moving in the right direction, and knowing my left from my right.

They have been a little bit samey. Maybe a new thread with some 'extra' puzzles on?

Agree, unlike last year, there hasn't been any this year that I have found hard. Some fairly 'involved', that took a few hours, but nothing more than that.

[David Martin]

OK, new thread started. I'll throw some data up for the first in due course.

[Pickled Onion]

(click to show/hide)

Interesting reading the different approaches.

I just started with the map, centre=(0,0) and whenever my virus went to step off the edge I called the expand() function. All changes made in-place as there's no need to know the previous state of infection.

[Ben T]

(click to show/hide)

Interesting reading the different approaches.

I just started with the map, centre=(0,0) and whenever my virus went to step off the edge I called the expand() function. All changes made in-place as there's no need to know the previous state of infection.

I didn't even have a map.... just a 'bag' of nodes, each with X and Y position, which can be anything.
If it moves to a node that doesn't currently yet exist, it just creates one and it starts off in the default state of 'clean' (as specified).
The limits of the (imagined) "matrix" are simply the lowest/highest X and Y positions that happen to currently exist in the bag.
My (imagined) "matrix" is thus probably very rarely square or even regular shaped.

[Pickled Onion]

(click to show/hide)

Interesting reading the different approaches.

I just started with the map, centre=(0,0) and whenever my virus went to step off the edge I called the expand() function. All changes made in-place as there's no need to know the previous state of infection.

I didn't even have a map.... just a 'bag' of nodes, each with X and Y position, which can be anything.
If it moves to a node that doesn't currently yet exist, it just creates one and it starts off in the default state of 'clean' (as specified).
The limits of the (imagined) "matrix" are simply the lowest/highest X and Y positions that happen to currently exist in the bag.
My (imagined) "matrix" is thus probably very rarely square or even regular shaped.

(click to show/hide)

Eh? The puzzle input was a map even if you squish it to a bunch of nodes. But you are right, there was no need to extend the given map, everything outside is is clean. I guess I just did that to make it easier to print it out for the test cases.

[David Martin]

I did the same as Ben T.

(click to show/hide)

You just need to knwo where you have been and a limited subset of starting positions. So a hash of positions makes sense. Don't need to keep an entire map in memory.

[Oaky]

(click to show/hide)

day 21 was a puzzle of the type I really like since I could define the small steps that got me closer and closer to the solutiojj an implement those incrementally (I should have done it TDD the whole way with unittest module, but didnt bother this time).

Day 20, on the other hand, is really annoying me because I think I understand it fully, and I think my code is doing exactly what I want it to do, but my answer is wrong (and also "feels" wrong - I would really expect more collisions than I'm finding, and definitely some multi-way ones.)

Code: [Select]

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
395 13 -27 530 106 -185 89 4 -17 8
401 13 -27 530 -103 -6 89 -2 -11 8

iteration       10: count = 998

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
306 30 -14 728 -9 182 74 1 14 4
314 30 -14 728 -144 12 74 -12 5 4

iteration       18: count = 996

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
471 -8 -15 700 -338 -361 37 -11 -7 1
473 -8 -15 700 547 231 37 15 6 1

iteration       35: count = 994

Collision between particles:
p0 p1 p2 v0 v1 v2 a0 a1 a2
212 -49 33 72 -299 72 2 -8 4 0
213 -49 33 72 -278 -148 2 -9 -1 0

iteration       36: count = 992


Got it!

My code was doing exactly what I expected, apart from the input data importer, which had a mistake in my regexp so that I was truncating the z coordinates to one digit only.

(click to show/hide)

The clue was that when I was seeing collisions, there were several near misses with identical x and y but slightly different z coordinates

[David Martin]

Day 23 part A is straightforward

Part B:

(click to show/hide)

You need to work out what h is actually counting rather than trying to make the process faster.

(click to show/hide)

h is only incremented when f is 0. f is set to zero unless there is no e for which b is exactly divisible, ie b is prime.
The b to test are in steps of 17 (in my input) over a range of 17000.

I can count the number of times b is divisible by any integer less than sqrt(c)
but that gives me the wrong answer (too high).
What have I missed?
An off by one would give me a number that is too low.

ETA: Where was I going wrong? An inability to count the number of zeros. *blush*
And then an off by one errror

[Pickled Onion]

(click to show/hide)

That's quite a spoiler. Took me a while to convert to code then optimise, then realise what the algorithm was 

[David Martin]

(click to show/hide)

That's quite a spoiler. Took me a while to convert to code then optimise, then realise what the algorithm was 

That is why it is in (ETA: now multiple) spoiler tags.

[Pickled Onion]

(click to show/hide)

This is what I did while trying to work out why your solution didn't work and mine did. Golf: 73 characters:

(click to show/hide)

for($b=105700;$b<=122700;$b+=17){$h++if grep!($b%$_),(2..sqrt$b);}print$h;

shorter without the sqrt, but slower for the usual grep reasons.

[David Martin]

(click to show/hide)

len([x for x in range(105700,122701,17) if [y for y in range(2,1012) if x%y ==0]])