Advent of Code

[Ben T]

(click to show/hide)

Doh! I was looking at steps but not in the right directions.

That's what I did (since I couldn't remember it clearly enough), and when I couldn't figure it out in 20 seconds or so I gave up and continued with a 2D approach using N=[0,-1], NE=[1,-0.5], SE=[1,0.5], and then similar calculations as Oaky above.

At the time I'm not interested in the perfect solution, I'm (personally) only interested in doing it quickly and without looking anything up. Other approaches are available. But afterwards it is interesting to see the other (often better) approaches.

I'm far too thick to think up any 3D solution so just did it in 2D and for part 1 did a BFS that worked fine and ran in under a second.
But for part 2 I firstly assumed incorrectly that the furthest away in 2D distance (the geographical furthest) would have the furthest number of steps, in fact it didn't.
I knew that the max steps (the answer) couldn't be much more than the number of steps for geographical furthest, but didn't want to keep guessing.
So I simply optimized it by factorizing the hexagons and only considering moves outside a minimum radius inside which they couldn't possibly take as many steps as the geographical furthest.
Still takes about a minute though. https://github.com/bjtaylor1/AoC2017/blob/day11part2b/Day11/Program.cs   
Quite good though, first reasonably difficult one.

[David Martin]

Today was straightforward.

(click to show/hide)

I should look at the networkx module but there is some merit in working through from the ground up. Maybe I should spit out the necessary format for gephi or cytoscape and view the hairballs.
[/source]

[Oaky]

Today was straightforward.

(click to show/hide)

I should look at the networkx module but there is some merit in working through from the ground up. Maybe I should spit out the necessary format for gephi or cytoscape and view the hairballs.

(click to show/hide)

Using networkx and matplotlib.
The large green nodes are the graph containing node 0 and the red node is node 0 itself.

[Greenbank]

Slowly doing the Anti-AoC:-

How close to 5am (UK time) can I still be up but with no chance of being up to 5am to attempt the challenge (let alone be sober enough!)

[David Martin]

Today: I've done part 1 but part 2 will have to wait till I get home as I have too much marking to do. I recognize the problem but can't remember the elegant solution

(click to show/hide)

Each sentry maps onto a disk with diameter 2(n-1) where n is the range of the sentry.
This is the 'drop a ball through the disks' puzzle. It is a factorization one but I can't remember how to do it and haven't had time (or coffee enough) to work it out.
I'm not going to look it up - will sort it when I get home.
Brute force is not accessible for this.

[Ben T]

day 12 quite easy going from part 1 to 2 https://github.com/bjtaylor1/AoC2017/compare/day12part1...day12part2

[Greenbank]

My simple naive brute force version took just under 20 seconds for day 13 part b.

(click to show/hide)

Will reimplement it properly using linear algrebra a bit later.

It's not quite the same as the 'drop a ball through the disks' puzzle (which was the Chinese-Remainder-Theorem) as that was looking for a number that satisfied a series of relations of the form: x % y = n.

This problem is about finding a number that satisfies a series of relations of the form x % y != n although I'm guessing that the possible elements in each Galois field are thinned out by multiple relations against the same field size, in which case it may come down to the CRT after all.

[David Martin]

I've kind of worked out how I want to do part 2 but am currently shattered so will pick it up after a wee pause.

(click to show/hide)

There is some ugly kludging with bitmasks that can be done. I'm still seeking an elegant solution, the sticking point being the not falling through holes.
Each disc of a set size can be combines to give a single bitmask, and any complete factors can also form part of that.

[Greenbank]

Still working on a more elegant solution for day 13b.

My work in progress (big spoiler):-

(click to show/hide)

A layer of depth n has a periodicity of 2*(n-1)

So an example entry of "72: 14" translates into:
d+72 != 0 mod (2*(14-1))
d+72 != 0 mod 26
d != -72 mod 26
d != 6 mod 26

The entry of "1: 2" means d != 1 mod 2, i.e. d = 0 mod 2 as 0 is the only possible value remaining in the residue class mod 2.

I then apply this to every residue class that is divisible by 2, removing any entries that aren't equal to 0 mod 2.

Keep repeating this for residue classes that are multiples of each other, whilst I'm removing entries from residue classes, and if there's only one entry left in the residue class then it becomes a relation such as d = 20 mod 32.

Repeat this whilst it is learning something new each round and then report what is left:-

FINAL:
d = 0 mod 2
d = 0 mod 4
d = 0 mod 6
d = 4 mod 8
d = 0 mod 10
d = 12 mod 14
d = 4 mod 16
d = 0 mod 18
d = 6 mod 22
d = 20 mod 32

incomplete:-

d = 16 24 mod 26
d = 0 2 4 6 10 12 14 16 18 20 22 24 26 28 30 32 mod 34
d = 2 4 6 8 10 12 16 18 20 22 24 26 28 30 32 34 36 mod 38
d = 0 2 4 6 8 10 12 14 16 18 20 22 24 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 mod 58

So the first lot should be combined to a nice single term with the modulus being the LCM of 2,4,6,8,10,14,16,18,22,32 which is, urm, 2^5 * 3^2 * 5 * 7 * 11 = 110880). From my answer I already have I know it will be:-
d = 60660 mod 110880

60660 doesn't satisfy all of the 'incomplete' relations (60660 = 2 mod 26 and only 16 and 24 are allowed mod 26), so from there I just keep adding 110880 on again until I get something that satisfies all of them.

I've just got to do the CRT step to combine the 'complete' relations (after making sure the moduli are co-prime) into that "d = 60660 mod 110880" relation and then do the code to do the final loop multiple times.

[Greenbank]

And the final bit (using my puzzle input, so it won't be the same for everyone)...

(click to show/hide)

...following on from the relations mine discovered above I start with n = 0 mod 1 (i.e. everything matches) and then add each of the relations in:-

Doing CRT
Called with n = 0 mod 1 and n = 0 mod 6
        combined to d = 0 mod 6
Called with n = 0 mod 6 and n = 20 mod 32
        combined to d = 84 mod 96
Called with n = 84 mod 96 and n = 0 mod 2
        combined to d = 84 mod 96
Called with n = 84 mod 96 and n = 12 mod 14
        combined to d = 180 mod 672
Called with n = 180 mod 672 and n = 6 mod 22
        combined to d = 1524 mod 7392
Called with n = 1524 mod 7392 and n = 4 mod 8
        combined to d = 1524 mod 7392
Called with n = 1524 mod 7392 and n = 0 mod 4
        combined to d = 1524 mod 7392
Called with n = 1524 mod 7392 and n = 0 mod 18
        combined to d = 16308 mod 22176
Called with n = 16308 mod 22176 and n = 4 mod 16
        combined to d = 16308 mod 22176
Called with n = 16308 mod 22176 and n = 0 mod 10
        combined to d = 60660 mod 110880
Combined: d = 60660 mod 110880
Trying...60660...171540...282420...393300...504180...615060...725940...836820...947700...1058580...1169460...1280340...1391220...1502100...1612980...1723860...1834740...1945620...2056500...2167380...2278260...2389140...2500020...2610900...2721780...2832660...2943540...3054420...3165300...3276180...3387060...3497940...3608820...3719700...3830580...3941460...
ANSWER: 3941460

Runs instantaneously too.

Here's the complete output using the simple example input from the challenge:-

$ cat inp.simp | time ./13c.pl
INIT: d mod 4 != 0
INIT: d mod 2 != 1
INIT: d mod 6 != 2
INIT: d mod 6 != 0
severity: 24
GOT: d = 0 mod 2
OK: Will apply d = 0 mod 2 to remain{4}
Removing d = 1 mod 4 because d=0 mod 2
Removing d = 3 mod 4 because d=0 mod 2
OK: Will apply d = 0 mod 2 to remain{6}
Removing d = 1 mod 6 because d=0 mod 2
Removing d = 3 mod 6 because d=0 mod 2
Removing d = 5 mod 6 because d=0 mod 2
d = 0 mod 2
Got: 6
GOT: d = 2 mod 4
GOT: d = 4 mod 6
d = 0 mod 2
d = 2 mod 4
d = 4 mod 6
Got: 2
d = 0 mod 2
d = 2 mod 4
d = 4 mod 6
Got: 0

FINAL:

d = 0 mod 2
d = 2 mod 4
d = 4 mod 6

Doing CRT
Called with n = 0 mod 1 and n = 4 mod 6
        combined to d = 4 mod 6
Called with n = 4 mod 6 and n = 2 mod 4
        combined to d = 10 mod 12
Called with n = 10 mod 12 and n = 0 mod 2
        combined to d = 10 mod 12
Combined: d = 10 mod 12
Trying...10...
ANSWER: 10
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 9488maxresident)k
0inputs+0outputs (0major+632minor)pagefaults 0swaps

[Pickled Onion]

Still working on a more elegant solution for day 13b.

My work in progress (big spoiler):-

Neat!


Today's was the first this year where part 2 didn't respond well to a simplistic approach.

[Greenbank]

Today's was the first this year where part 2 didn't respond well to a simplistic approach.

Really? I spent 5 minutes writing this to get the answer in 20 seconds:-

(click to show/hide)

#!/usr/bin/perl

use strict;

my %n=();

while( my $x = <STDIN> ) {
        chomp( $x );
        if( $x =~ /^(\d+): (\d+)$/ ) {
                $n{$1}=$2;
        }
}

my $delay=-1;
while( 1 ) {
        $delay++;
        my $got=0;
        foreach my $a ( keys %n ) {
                if( ($delay+$a) % ($n{$a}+$n{$a}-2) == 0 ) {
                        $got=1;
                        last;
                }
        }
        next if( $got );
        print "DELAY: $delay\n";
        exit;
}

My usual method is to see if the basic/naive approach will work and whether it produces the answer before I can implement something that runs faster.

But then I spent another 90 minutes or so to bring the execution time down to nothing, just to do it the right way (or at least one of the right ways).

Yes, that's 90 minutes to bring the execution time of a one-off task down from 20 seconds to 0 seconds. Unsurprisingly according to the chart (https://xkcd.com/1205/) it was not worth the time. But I did learn (or at least remind myself of) a few things along the way.

[David Martin]

You have a faster computer than me. Mine took a few minutes to run and I was completely naive with searching every possibility. The approach I had been thinking about is this:

(click to show/hide)

x is a bitmap of n bits where n is the effective size (2* (range - 1))
It looks like this for  depth %n ==0    0 1 1 1
and for depth %n ==1  1 0 1 1
So the only allowed permutations from this is the logical and of the masks 0011

Add in n=3 and the bitmask is tripled so it becomes 001100110011 and is then anded with the bitmask 011 bitshifted as required to satisfy depth % 3 and then repeated as required eg 011011011011 so my new mask is now 001000010011
And repeat as required till the end. Unfortunately the bitmask gets very long - it is the lowest common multiple of the ranges.

A smarter way would be to start with the first few and that would give a suitable step size for searching - maybe use the difference between mask lengths as a step.

Thinking out loud a bit as the brute force method worked.

[Greenbank]

The one I posted checks every possibility (delay=0,1,2,3,4,5,...),  it just does the individual checks in a more 'mathsy' way.

Anyway, Day 14 and use of previous solutions (which I like and had hoped would appear more in AoC 2017).

I wonder if I need to make my knot hash code faster in case it's used more and more in future challenges. It currently takes 10 seconds to produce the 128 knot hashes required as input for parts (a) and (b), I'm sure I can get this down (and will give me something to do for AoC for part of the rest of the day).

[Ben T]

You have a faster computer than me. Mine took a few minutes to run and I was completely naive with searching every possibility. The approach I had been thinking about is this:

(click to show/hide)

x is a bitmap of n bits where n is the effective size (2* (range - 1))
It looks like this for  depth %n ==0    0 1 1 1
and for depth %n ==1  1 0 1 1
So the only allowed permutations from this is the logical and of the masks 0011

Add in n=3 and the bitmask is tripled so it becomes 001100110011 and is then anded with the bitmask 011 bitshifted as required to satisfy depth % 3 and then repeated as required eg 011011011011 so my new mask is now 001000010011
And repeat as required till the end. Unfortunately the bitmask gets very long - it is the lowest common multiple of the ranges.

A smarter way would be to start with the first few and that would give a suitable step size for searching - maybe use the difference between mask lengths as a step.

Thinking out loud a bit as the brute force method worked.

My day 13 part 2 runs in 0.4 of a second.

(click to show/hide)

The position of the scanner at given depth is given as a function of time t and the amplitude m (which is the scanner's range minus 1).
Because it moves back and forth its position is given by triangular wave equation x = m - abs(i % (2*m) - m) https://stackoverflow.com/questions/1073606/is-there-a-one-line-function-that-generates-a-triangle-wave
scanner position S = m - abs(x % (2*m) - m)
because x = t (we move one per second)
S = m - abs(t % (2*m) - m)
So we are caught when that is equal to zero.
For part 2, t is simply (t+delay) , and increment delay till you find one where you are never caught (the equation above is equal to zero).
I originally did it with a linq statement that was evaluating all the positions even if it were caught, once I changed it to one that moves  onto the next as soon as it's caught that brings it from 11 seconds to under a second.

Time to run should be proportional to the number of positions with a scanner, regardless of the max depth of any position with a scanner.
https://github.com/bjtaylor1/AoC2017/blob/day13part2/Day13/Program.cs

[Greenbank]

Naive 13b down to under 3 seconds if I check them in range depth order (from smallest to largest). I was already bailing early but checking the layers in a suboptimal order. Using an interpreted language doesn't help either.

But my 'clever' solution for day13b runs in 0.002 seconds.
* For the example input I do my pre-computation then checks just one possible delay value.
* For my real input I do my pre-computation and then have to check just 36 possible delay values.

I could speed this up too as:

(click to show/hide)

the various number theoretic bits (factorisation, LCM, CRT) are all implemented sub-optimally.

I'll see if I can knock up an input that has an answer that is orders of magnitude larger.

[David Martin]

Today's may have to wait till tomorrow or the weekend -overrun with other things right now.

[Diver300]

I used a spreadsheet (again!) for day 13.  It had far fewer active cells than for day 7 and it didn't do much more than I could have done with a pencil and paper and a calculator.

(click to show/hide)

For my puzzle input, odd numbered delays were clearly doomed.

For even numbered inputs, for each of the following periods:-
10
14
18
22
32

There was only one possible solution for each cycle. For instance, the solution had to be  4 + 10 * n , 2 + 14 * m , 14 + 18 * p etc

So I went up in 10s from 4 until I found a solution that could expressed as  2 + 14 * m.
Then I went up in 70s (the lowest common multiple of 10 and 14) until I found a solution that could be expresses as 14 + 18 * p
And so on until I had a solution worked for all 5 numbers. That only took a total of about 20 tries.

The other levels had more complicated rules with more than one solution, so I went up in jumps of 110880 and visually compared the remainders. That was under 40 lines of the spreadsheet, comparing 4 columns.

[Greenbank]

I'll see if I can knock up an input that has an answer that is orders of magnitude larger.

OK, try this against your 2017 day 13b solver: http://www.greenbank.org/misc/aoc2017/2017_13b.huge.txt

The answer is about ~250 times larger than my answer for 13b was, which should give you a rough idea of execution time if it's checking every number along the way. (The answer still fits inside a signed 32-bit integer though, so programs shouldn't need to be altered.)

Mine gets it in under 0.001s after only having to try 38 numbers.

[EDIT] In contrast, my naive solver took 738s to get the answer.

[Diver300]

Day 14 relies on a code written for day 10.

(click to show/hide)

Part 2. This is searching for contiguous areas. I'd done something similar when I wrote code for minesweeper on a Psion, where it automatically finds contiguous clear areas.

I ran a list of cells that I need dealing with.  That got up to 45 items.

[Greenbank]

(click to show/hide)

I did one script to generate the input to the knot-hash function (blah-0 to blah-127).
I then ran that input through the knot-hash function to get the list of hashes
I then had another script to convert it to binary representation.
I treated the output of the above as the input for the next program, so I didn't have to go do that work again and again each time I tested my code.

I stored the grid in a 128x128 array using # or . characters. (Should have just kept it as 1 or 0 thinking about it.)

I iterated through the grid to find an element that was still #. If I found one I incremented a counter (to signify a new group) and then used a recursive function to:-
a) set the element to . to indicate it was done (there's no need to keep track of whether it was originally set or not, and there's no need to store the group number along side each element)
b) call itself on each of the 4 neighbours that are still set to #

The alternative to a recursive function (if recursion depth could get too big) would be to use a list of element co-ordinates to know what to process next.

[EDIT] With the example my code managed to get to 105 nested recursions, with my final puzzle input it was only 89 max depth. My program (well, the perl interpreter) had no problem even with the pathalogical case of all hashes being ffffffffffffffffffffffffffffffff which leads to a recursion depth of 16384 and there only being one group.

Don't think there's any other optimisation that can be done.

If the goal was minimising memory usage I'd store each element of memory as a single bit (1 is # and 0 is .) So memory usage for the grid could be just 128*128/8 = 2048 bytes.

[Greenbank]

Pretty simple today (day 15), no surprises.

[Oaky]

(click to show/hide)

A little bit of eye-candy - groups coloured in:-

[Greenbank]

Ooh. Do 4 colours suffice?

[Oaky]

Ooh. Do 4 colours suffice?

Well, given my input, I'm using

(click to show/hide)

1019

  colours (including the black for the background), but in the 4-colour sense, two suffices for this pattern.   Doesn't look as nice then, though.