Advent of Code

[Greenbank]

That's the thing with a lot of these - if you short-circuit part 1, you find part 2 needs the data from part 1.

Or if you don't short-circuit part 1 you find that part 2 involves computing something so big that it would take the naive algorithm years to finish so you do need to short-circuit it.

Most of the time (having just gone back and done the whole of 2016 and 2015 over the last few days) whatever I do in part (a) is usually the wrong one. I guess this is no coincidence.

The second part I used a dynamic programming approach and promptly filled it so full of bugs it took a long time to wrangle out. Was there a more elegant way that I somehow missed?

2017.3.b spoiler:-

(click to show/hide)

It didn't need to use anything like that.

Initialise 0,0 to 1. Set direction to E(ast)
iterate:-
* move in direction (E = inc x, y stays the same)
* calc new value
* Is square to left (in terms of direction being travelled, if moving East then 'left' means North) of me unset? If so turn left...
* repeat

So you go E (to 1,0 and calc).
Square left of there (1,1) is unset so turn L (dir is now N).
Move N to (1,1 and calc).
Square left of there (0,1) is unset so turn L (dir is now W).
Move W to (0,1 and calc).
Square left of there (0,0) is already set so don't change dir (still W)
Move W to (-1,1 and calc).
Square left of there (-1,0) is unset so turn L (dir is now S).
...

For langs that don't allow arrays with negative indicies, just add a constant to both X and Y to shunt it up into +ve values always.

[Pickled Onion]

That's the thing with a lot of these - if you short-circuit part 1, you find part 2 needs the data from part 1.

Or if you don't short-circuit part 1 you find that part 2 involves computing something so big that it would take the naive algorithm years to finish so you do need to short-circuit it.

Most of the time (having just gone back and done the whole of 2016 and 2015 over the last few days) whatever I do in part (a) is usually the wrong one. I guess this is no coincidence.

Yes, that's what makes these so much fun. I can solve it this way... or that way... which way is going to help in part 2?

[David Martin]

I suppose I just had a function that mapped the 2D onto the 1D array and went from there. I went back and checked and despite the dynamic programming, I still calculated every value.

[Oaky]

Didn't get to doing today's until this evening owing to family visiting plus putting up the Christmas decorations.

(click to show/hide)

I used almost the same algorithm for constructing the path as Greenbank, except my condition for turning left was to turn if the new location had only 1 populated neighbour.

I used a Python dict() keyed by the coordinates in a tuple with the value being either the address count (part 1) or the sum of neighbours (part 2).  In part 1, for laziness, I also constructed the inverse dict at the same time to easily look up the coordinate of the input address after I'd populated the dict(s).

[Diver300]

(click to show/hide)

I used almost the same algorithm for constructing the path as Greenbank, except my condition for turning left was to turn if the new location had only 1 populated neighbour.

I used the same method.

(click to show/hide)

Because every square that is populated is greater than zero, it works to populate the entire array with zeros and use >0 as the condition for having been visited.

I did part one without programming, just a text editor for notes and a calculator.

BTW, I'm mtrak

[Greenbank]

Was hoping for a meaty one today but no.

Still, I've got some of the older ones to revisit and make work more efficiently.

[Croft]

I'm impressed you rattled though the 2015 and 2016 ones so quickly. I seem to recall the Isotope lifts problem, the Wizard Spells game and Medicine for Rudolph problems taking quite some effort.

[David Martin]

Today's was very much a start of week 1 problem.

(click to show/hide)

The joy of having lists and unique sets, and for part two, mapping each word onto the word alphabetically sorted on parsing the line.

[Greenbank]

isotope lift

(click to show/hide)

I spotted the isomorphism optimisation early (the fact that element names didn't affect whether you'd been in a particular state before or not, only the position of the generators and microchips) and so that helps minimise the search space.

wizard spells I spent a fair while on as I had an annoying bug (one of my effects lasted for the wrong number of turns) - when I finally sorted that I had also missed the fact that you had to cast an effect on every turn, and my code allowed nothing to be done on a turn (with my input you got a lower score if you did nothing on the last turn as the poison spell was still in effect)

Another reminder to READ THE DESCRIPTION PROPERLY!

medicine for rudolph : maybe I was lucky...

(click to show/hide)

I worked backwards (aiming to go from the big long string back to 'e') doing a depth first search trying the possible replacements in length order (longest first) and I almost instantly got an initial result that didn't seem to drop after 10 seconds of the program running (in situations like this I report each time it finds a new 'better' score) so tried that number for fun and it was the right answer. Haven't tried to leave the program running to see how long it takes to run (it's been 10 minutes so far and still hasn't finished), unsurprising as there's little protection for it going down blind alleys at the moment.

I did notice that (in my puzzle input at least) 3 elements only appeared on the RHS of the rules, and was going to exploit that next if that initial answer hadn't been correct. I don't know how many different combinations there are when those 3 elements have been removed, might go back to this in a bit. It might be one that's best attacked from both ends in order to meet in the middle.

This kind of challenge (as in AoC) is exactly my kind of thing though. I've been coding as a job for 20+ years and have degrees in both Comp Sci and Maths, I've also done many of the Valladolid Online Judge (https://uva.onlinejudge.org/) programming challenges too so many of the concepts I've covered before.

[Croft]

Medicine for Rudolph (Day 19, 2015)

(click to show/hide)

It's worth spending a bit of time looking at the substitution rules as there are some properties that greatly reduce the number of computations required.

In fact:

(click to show/hide)

There is even a trivially simple algebraic solution for calculating the answer (i.e. no tree searching at all). This may have been an inadvertently exposed result of the problem generation algorithm.

[Oaky]

Today's was very much a start of week 1 problem.

(click to show/hide)

The joy of having lists and unique sets, and for part two, mapping each word onto the word alphabetically sorted on parsing the line.

(click to show/hide)

Another problem very well suited to the strengths of the Python Pandas/numpy libraries.

Code: [Select]

import pandas as pd
import numpy as np

df = pd.concat(list(map(lambda x: pd.Series(x.strip().split()), open('input.txt').readlines())), axis=1)

print(f'part 1 answer {sum(~df.apply(lambda x: any(x.dropna().duplicated())))}')

df = df.applymap(lambda x: np.nan if x is np.nan else ''.join(sorted(x)))

print(f'part 2 answer {sum(~df.apply(lambda x: any(x.dropna().duplicated())))}')


Days 1, 2, and 4 solved with pandas so far.  Maybe I need to go back and think harder about how to do 3.

[David Martin]

My pandas fu is not that developed.

[Diver300]

Day 5 seemed quite straightforward.

(click to show/hide)

Only a spoiler in as much as it refers to part 2 question.

I first thought that 3 or more meant in either direction, so I solved the wrong problem and came up with tiny answer.

[Greenbank]

At this point the private leaderboard is more about who gets up earliest than anything else. (7.30am is the earliest I'll ever be in front of a computer.)

(Not grumbling, the trickier problems will come...)

[David Martin]

Indeed. I appear to be 4th up in the morning.

I was idly thinking on whether there was a trivial way to determine the result from the values in the steps. I am led to believe it is pretty close to an ideal turing machine and therefore you only know if it will stop when it does, so there is no way to know the number of interations from the instructions without playing them out.

[David Martin]

For day 6, the brute force is obvious, but I was wondering whether there is a more elegant way to do it.

(click to show/hide)

Hash each combination with the number of steps to get to that hash. Makes both parts quite straightforward.

[Greenbank]

Day 6:

(click to show/hide)

The hash is just a (very) handy container, without it you'd just be implementing your own storage and comparison function.

I'm tempted to reimplement this in C (where there is no native dictionary/hash/hashmap structure) and rather than implementing one of those I'd probably use a tree structure to store the data, for semi-fast comparisons.

[EDIT] Ugh, that wasn't particularly pleasant, but it's redone in C just for fun.

[David Martin]

Day 6:

(click to show/hide)

I had a horrible feeling that for part b the valid combinations would include all rotations  so that having 1 2 3 4 would be seen as identical to 4 1 2 3  (which itself just walks backwards continuously around the loop - a glider in game of life terms). Fortunately it wasn't.

[Diver300]

Day 6
The debugging output for my code had basically solved part 2 by the time that I had solved part 1

(click to show/hide)

I displayed the line numbers for the latest iteration and the one it matched. The answer to the second part was simply the difference.

[David Martin]

Day 6
The debugging output for my code had basically solved part 2 by the time that I had solved part 1

(click to show/hide)

I displayed the line numbers for the latest iteration and the one it matched. The answer to the second part was simply the difference.

very similar

(click to show/hide)

I stored the step number as the value of the hash so it was just a question of retrieving the last hash and the value it pointed to. And then to make an off by one error

[Oaky]

Day 6
The debugging output for my code had basically solved part 2 by the time that I had solved part 1

(click to show/hide)

I displayed the line numbers for the latest iteration and the one it matched. The answer to the second part was simply the difference.

very similar

(click to show/hide)

I stored the step number as the value of the hash so it was just a question of retrieving the last hash and the value it pointed to. And then to make an off by one error

(click to show/hide)

I didn't store the step number, so rather than recode to do so, I added a method to my Memory() class to cycle on from the current value until it saw that hash again.  This works because the internal state of my machine is already in a value in the cycle when the part 1 code finishes.

I also added an automated test for the new method.

I then spent an age trying to work out why my cycle_length() method wasn't terminating on the test data, only to realise that in my test I had failed to do the "setup" step of solving Part 1 in the test object instance first, so it was waiting for the memory banks to return to the test case initial value, which isn't in the cycle so it never will

[Diver300]

Day 6
The debugging output for my code had basically solved part 2 by the time that I had solved part 1

(click to show/hide)

I displayed the line numbers for the latest iteration and the one it matched. The answer to the second part was simply the difference.

very similar

(click to show/hide)

I stored the step number as the value of the hash so it was just a question of retrieving the last hash and the value it pointed to. And then to make an off by one error

(click to show/hide)

I tried to save the previous iterations as an array of arrays, in Javascript, and failed miserably. Then I just stored the history as an array of text strings, with separators between numbers to differentiate between, for instance 11,2 and 1,12. Text string comparison is just == in Java script and this problem didn't need me to recover to numbers.

[David Martin]

That was a bit more satisfying.. Note: read the text more carefully.

[Greenbank]

Indeed, that's a bit better.

It's the first one (of 2017) where I've had to write psuedo-code first and then flesh it out, rather than knowing what to do straight from the start.

[David Martin]

The pattern and approach was quite straightforward. Better if I read the instructions for part 2 and deliver what was asked. No need for pseudo code.

(click to show/hide)

Obviously a Directed Acyclic Graph, the question was how to store the details.
Then a recursive algorithm that spits out the key information when it finds the problem.