Advent of Code

[Oaky]

(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.

(click to show/hide)

I didn't use the recursive approach, instead iterated over each element in my disk_grid (of 1's and 0's) filling in a new grid (groups_grid) applying the following rules:

Code: [Select]

If the current disk cell is 1
    is the disk cell above populated? then:
        copy the group number from the group_grid cell above to this one
        is the group_grid cell to the left of me populated with a different number? then:
            replace that number everywhere in the group grid with the number I just filled in here (only have to consider this row and the ones above)
    else: is the disk cell to the left populated? then:
        copy the value from the group_grid cell left of me to this cell
    else:
        choose a new group number and fill it in in the current group_grid cell


(click to show/hide)

[Diver300]

Day 15

I thought that Javascript might struggle doing modulus 2³¹. It didn't, and only takes a few seconds to run.

The whole point about day 13 was that it took too long to run when brute-forced. When reading day 15, I thought that the maths that is simple in principle would have some feature that would trip up the simple approach.

[David Martin]

Far too busy to do yesterday and today till now.

Day 14 was easy for part 1,

(click to show/hide)

With such a small grid I walked it recursively from the next unassigned value, exploring all unassigned values and adding them to a hash. I should have put the group numbers in too.

Day 15 was straightforward

(click to show/hide)

barring silly errors. Just bitwise comparisons, remembering that (a & 2**16 -1) ^ (b & 2**16 -1) ==0 is a match.

and for part 2, repeating each calculation whilst n & (multiple - 1) filters very easily.

[Diver300]

day 16 part 2 is proving difficult.....

[Pickled Onion]

day 16 part 2 is proving difficult.....

You're not the only one stuck on that

(click to show/hide)

You will kick yourself when you spot it

[David Martin]

I am finding part 2 challenging

(click to show/hide)

You don't need to repeat the dance, just note how the dance transforms the input. Then that multiplies logarithmically.
So far I have built a bitwise transformation matrix. 1 dance applied to 1 dance gives 2 dances. 2 dances applied to 2 dances gives 4 and so on.
Then walk through the bit map of 1000000000 applying the appropriate transformations (they should be commutative).
The answer I get settles to a particular order - the program runs almost instantly.

But it is the wrong answer. This has me confused. Part 1 was correct so my transformation matrix is correct.

[Pickled Onion]

I didn't think that would work.

(click to show/hide)

The intermixing of "partner" and "exchange" means each transformation will be different

[David Martin]

OK, simple error

(click to show/hide)

Because the order has changed, the exchange of named entities (rather than positional) is not scalable.
Once the key thing has been thought about it becomes very quick.

[David Martin]

I didn't think that would work.

(click to show/hide)

The intermixing of "partner" and "exchange" means each transformation will be different

That is now obvious.

[Greenbank]

Bit late to it today...

(click to show/hide)

Seeing the requirement for 1,000,000,000 iterations I knew there was going to be some trick before I even attempted to put my main code into a bigger loop, and guessed there would be no point even trying to optimise the code in order to be run 1,000,000,000 times.

So I checked something else and it turned out to be very simple. (I'll leave it a bit before elaborating.)

It's annoying as I'm solving the majority of these in a faster time than the 100th person on the main leaderboard (today I would have scraped into the top 10). But I guess quite a few other people are too (who also just don't happen to be at their computer at midnight EST).

[Diver300]

I didn't think that would work.

(click to show/hide)

You don't need to repeat the dance, just note how the dance transforms the input. Then that multiplies logarithmically.
So far I have built a bitwise transformation matrix. 1 dance applied to 1 dance gives 2 dances. 2 dances applied to 2 dances gives 4 and so on.
Then walk through the bit map of 1000000000 applying the appropriate transformations (they should be commutative).
The answer I get settles to a particular order - the program runs almost instantly.

But it is the wrong answer. This has me confused. Part 1 was correct so my transformation matrix is correct.


The intermixing of "partner" and "exchange" means each transformation will be different

(click to show/hide)

I though that I could run it 1000 times, which takes a few seconds, then take the transformation that 1000 runs gives, run that 1000 times to give the transformation that 1,000,000 gives, and run that 1000 times.

I also found out that the mix of exchange and partner messes it up.

[Ben T]

(click to show/hide)

a not particularly hard to spot trick question 

[Diver300]

Day 16

(click to show/hide)

I realised that I could separate out the partner swaps from the two position swaps, and run all the partner swaps first.

I think that the two position swaps could be run by working out the transformation that 1000 runs produces, running that 1000 times and working out the resultant transformation etc

That left the partner swaps. I tried some trivial ones and found that I got back to the start after n+1 repeats, where n was the number of partner swaps. So I tried with the 2213 partner swaps in my puzzle input, and it didn't work. However, I found that there had been many instances of abcdefgehijklmnop, and that after every 36 repeats the result was back to the starting value.

At that point I thought that I could use the multiplying transformations for the two position swaps, and the knowledge that I only needed 28 (= 1,000,000,000 mod 36) repeats of the 2213 partner swaps. On a whim, I tried putting back the two position swaps and found that the complete transformation also came back to abcdefgehijklmnop in 36 repeats.

So I just ran the 10,000 actions of the puzzle input 28 times to get the answer.

I still have no idea why 36 repeats of the partner swaps or 36 repeats of all of the actions result in no change.

[Ben T]

Day 16

(click to show/hide)

I realised that I could separate out the partner swaps from the two position swaps, and run all the partner swaps first.

I think that the two position swaps could be run by working out the transformation that 1000 runs produces, running that 1000 times and working out the resultant transformation etc

That left the partner swaps. I tried some trivial ones and found that I got back to the start after n+1 repeats, where n was the number of partner swaps. So I tried with the 2213 partner swaps in my puzzle input, and it didn't work. However, I found that there had been many instances of abcdefgehijklmnop, and that after every 36 repeats the result was back to the starting value.

At that point I thought that I could use the multiplying transformations for the two position swaps, and the knowledge that I only needed 28 (= 1,000,000,000 mod 36) repeats of the 2213 partner swaps. On a whim, I tried putting back the two position swaps and found that the complete transformation also came back to abcdefgehijklmnop in 36 repeats.

So I just ran the 10,000 actions of the puzzle input 28 times to get the answer.

I still have no idea why 36 repeats of the partner swaps or 36 repeats of all of the actions result in no change.

(click to show/hide)

not that complicated...just watch for when it repeats and then jump to the nearest-to-the-end possible factor of that

startpos = "abcdefghijklmnop"
currentpos = startpos
N = 1 billion
for(n = 1; n < N; )
{
  currentpos = DoMoves(currentpos);
  n++;
  if(currentpos == startpos)
  {

      n *= floor(N/n);     
     //for me, this occurred when n == 60.
     //It therefore jumps to 999,999,960, and only has to do 40 more iterations.
  }
}

[Diver300]

Day 16

(click to show/hide)

I realised that I could separate out the partner swaps from the two position swaps, and run all the partner swaps first.

I think that the two position swaps could be run by working out the transformation that 1000 runs produces, running that 1000 times and working out the resultant transformation etc

That left the partner swaps. I tried some trivial ones and found that I got back to the start after n+1 repeats, where n was the number of partner swaps. So I tried with the 2213 partner swaps in my puzzle input, and it didn't work. However, I found that there had been many instances of abcdefgehijklmnop, and that after every 36 repeats the result was back to the starting value.

At that point I thought that I could use the multiplying transformations for the two position swaps, and the knowledge that I only needed 28 (= 1,000,000,000 mod 36) repeats of the 2213 partner swaps. On a whim, I tried putting back the two position swaps and found that the complete transformation also came back to abcdefgehijklmnop in 36 repeats.

So I just ran the 10,000 actions of the puzzle input 28 times to get the answer.

I still have no idea why 36 repeats of the partner swaps or 36 repeats of all of the actions result in no change.

(click to show/hide)

not that complicated...just watch for when it repeats and then jump to the nearest-to-the-end possible factor of that

startpos = "abcdefghijklmnop"
currentpos = startpos
N = 1 billion
for(n = 1; n < N; )
{
  currentpos = DoMoves(currentpos);
  n++;
  if(currentpos == startpos)
  {

      n *= floor(N/n);     
     //for me, this occurred when n == 60.
     //It therefore jumps to 999,999,960, and only has to do 40 more iterations.
  }
}

(click to show/hide)

Finding the repeat is fairly easy. I did it with a ctrl-F on a list of iteration results.
What I can't work out is why it repeats, except that there has to be a solution, and something that takes an average PC about a week to finish is viable.
Is there anything about the puzzle input that says it has to repeat?

[Pickled Onion]

(click to show/hide)

Is there anything about the puzzle input that says it has to repeat?

(click to show/hide)

IANAMathematician, but I think there can only be two scenarios. Either it repeats from the start or gets into a loop. The perfect dance would cover all 16! permutations, leaving the puzzle essentially unsolvable, but it would still repeat. Being asked for a billion iterations makes it obvious the repeat would be shorter (my implementation of a single dance would have taken 3 years to run for a billion). A loop would have made it a bit more fun, essentially a repeat but not from the starting point.

[Diver300]

Day 17 was quite straightforward.

(click to show/hide)

The effort for part 1 goes up with the square of the number of steps. Less information is needed for part 2, and the fact that there are so many steps means that the algorithm has to be simplified to complete in reasonable time for the huge number of steps.

[Pickled Onion]

Day 17 was quite straightforward.

(click to show/hide)

The effort for part 1 goes up with the square of the number of steps. Less information is needed for part 2, and the fact that there are so many steps means that the algorithm has to be simplified to complete in reasonable time for the huge number of steps.

64 characters for part 2, including input data. 

(click to show/hide)

Tomorrow...

[Greenbank]

(click to show/hide)

Finding the repeat is fairly easy. I did it with a ctrl-F on a list of iteration results.
What I can't work out is why it repeats, except that there has to be a solution, and something that takes an average PC about a week to finish is viable.
Is there anything about the puzzle input that says it has to repeat?

(click to show/hide)

No, nothing explicitly said it had to repeat although, as Pickled Onion said, there are a finite number of permutations (16! which is ~20,000 times greater than the 1 billion steps requested) so at some point it has to repeat.

But the number of steps combined with the fact that the algorithm was going to be quite expensive to implement made me think there was going to be some other trick, even before I started to implement it.

I'd assumed that there would be some repetition and so I stored the state after each dance and checked whether it had been seen before. I hadn't expected the period to be so short though - it was only 60 with my input.

I checked and there are no duplicate states within an individual dance, so there's no way that part of it can be made faster I don't think.

I'll see if I can make my implementation faster (and implement it in C). It can certainly be made O(n) where n is the number of dances as each operation can be done in linear time:-
* a spin is just incrementing an offset, no need to move anything in memory
* an exchanges and pairings are just swapping a couple of memory locations, with the help of an array which is kept up to date with the location of each item (although need to apply the current offset from spins after extracting this because I wouldn't update the entire array when a spin is executed)

I'm guessing even the more efficient/fastest algorithm is still going to be too slow to get to 1,000,000,000 dances in any reasonable time.

It would be no great surprise that the dance moves and the number of dances were specifically chosen to put the brute force method beyond reasonable computation bounds.

[Greenbank]

(click to show/hide)

I like these ones where the two parts mean you need to keep track of different things and the bulk of the code is thrown away for part b because it's too expensive.

Also remembered to keep accurate timestamps:-

10:07:37 started (no peeking at the day 17 page, or any hints here, before this time)
10:17:01 after submitting correct solution for part a
10:22:18 after submitting correct solution for part b

Which is 00:09:24 (wouldn't have made it onto the leaderboard if I'd started at 5am) but 00:14:41 to get to part b solution which would have been good for 74th. Ifs and buts.

64 characters for part 2, including input data. 

I can get it down to 84 in perl, but then I'm not very good at code golf.

[Pickled Onion]

64 characters for part 2, including input data. 

I can get it down to 84 in perl, but then I'm not very good at code golf.

I look forward to comparing line noise tomorrow!

[David Martin]

17a was quite straightforward.
17b required minor thought but eventually succumbed to brute force

(click to show/hide)

Once you notice that 0 is always the first position, you only need to keep track of the insert when pos = 0. Nothing else matters. It then becomes a loop. There should be a way of readily checking which values would be applicable and going straight there but my maths is not up to that. runs in a few seconds so not much bother.

[Diver300]

17a was quite straightforward.
17b required minor thought but eventually succumbed to brute force

(click to show/hide)

Once you notice that 0 is always the first position, you only need to keep track of the insert when pos = 0. Nothing else matters. It then becomes a loop. There should be a way of readily checking which values would be applicable and going straight there but my maths is not up to that. runs in a few seconds so not much bother.

(click to show/hide)

Code: [Select]

current = (current + step + 1) % buff_len;
if (current == 0){buff [1] = i;}
That's all that I ran 50 million times. (starting at i = 1)
It takes about 3 seconds

[David Martin]

pretty much the same here. Took a bit longer than 3 seconds (about 10 or so)

[Pickled Onion]

Don't you need to increment buf_len?

My Perl version took 18 seconds with a grep BLOCK, but that's because grep allocates the whole list before it starts. Turning that into a for(RANGE) runs in 8 seconds. Oh and I'm down to 61 characters in the golf version