Advent of Code

[David Martin]

Day 18, those blinking lights again.
I didn't use recursion. Fortunately my approach meant that part B required minimal extra coding

(click to show/hide)

It runs very much easier if you add a border of always off lights around the edge to give an [n+2,m+2] grid, then there is no need to worry about boundary conditions. Just iterate over [2,2] to [n+1,m+1].
The minor change is to hard code the change in the resulting grid for the broken lights. Any sensible solution would be scalable to a different sized grid. I was expecting it to be harder, with the time of a bulb staying on being more than an individual iteration.

[Oaky]

Day 18, those blinking lights again.
I didn't use recursion. Fortunately my approach meant that part B required minimal extra coding

(click to show/hide)

It runs very much easier if you add a border of always off lights around the edge to give an [n+2,m+2] grid, then there is no need to worry about boundary conditions. Just iterate over [2,2] to [n+1,m+1].
The minor change is to hard code the change in the resulting grid for the broken lights. Any sensible solution would be scalable to a different sized grid. I was expecting it to be harder, with the time of a bulb staying on being more than an individual iteration.

(click to show/hide)

I initially planned to add the always off border, but decided in the end not to, and instead to avoid having to bounds check by just trying to reference outside the bounds and catching IndexError.  This, failed because Python is perfectly happy with an index of [-1] in a list or string  so I had to add a bounds check for the index < 0 case.   

I decided to do part 2 by subclassing my part 1 answer, so the additional code was just:

Code: [Select]

class LightArray2(LightArray):
    def __init__(self, str):
        LightArray.__init__(self, str)
        self.lightCorners()

    def lightCorners(self):
        self.elements[0]= '#'+self.elements[0][1:-1]+'#'
        self.elements[-1]= '#'+self.elements[-1][1:-1]+'#'

    def evolve(self, steps):
        for i in range(steps):
            LightArray.evolve(self, 1)
            self.lightCorners()
        return self

Which of course makes use of the [-1] index behaviour  that I fell foul of earlier.

[David Martin]

As Mr Wall says: TMTOWTDI
It was pleasantly easy. I was expecting something like 'if the bulb has been on for 10 iterations continuously it burns out and is permanently off'

[Oaky]

Indeed,  the part 2 variation was less taxing than I expected.

I was doing a bit of self-searching about which days i found hardest so far, and from memory the hardest two were

1. day 8 (the string storage thing)

(click to show/hide)

I got a bit of a headache trying to construct the code to test for some of the substrings for escape characters, when I had to escape the strings in the code.  Particularly the difficulty in specifying a string literal in Python win an odd number of "\" chars at the end.

2. day 7 (the circuit thing)

(click to show/hide)

.mainly because I'd never really thought about recursing through a structure like that before.

In terms of raw amounts of code (stripping comments), they rank as follows:-

Code: [Select]

oaky@jarlsberg ~/Dropbox/AdventOfCode $ for i in */s*.py; do echo `grep -v '^[ ]*#' $i |  wc -l` $i;done | sort -n
22 1/s1.py
26 2/s2.py
32 4/s4.py
48 17/s17.py
51 8/s8b.py
55 10/s10.py
58 12/s12.py
62 8/s8.py
71 14/s14.py
77 16/s16.py
82 3/s3.py
91 15/s15.py
95 13/s13.py
99 9/s9.py
100 6/s6.py
104 11/s11.py
137 5/s5.py
150 18/s18.py
173 7/s7.py

although it's skewed somewhat since after the first couple of days I started using a unit test framework for varying levels of testing within the script itself (some of the lmid to ater ones were more than 50% test code).

[Oaky]

from twitter earlier:-

Eric Wastl ‏@ericwastl 3h3 hours ago

If #AdventOfCode were a roller coaster, we're about to reach the corkscrews and loops and the part where it takes your picture.

[red marley]

Today's is right up David Martin's street.

Part two feels like a proper workout for me at least. I'm impressed that the highest entry on the leaderboard managed both parts within 18 minutes of the puzzle being released.

[David Martin]

I've just done part one which was easy. I'm thinking about part 2.

(click to show/hide)

It looks like you build the graph of all possible routes then seek the shortest path from e to alphabet soup. However there will only be one e => something transition in there, so you are looking for end points that match.
I have to invert my data structure for part 1 and then start at the end. I'll recurse through keeping track of the number of steps to get to a point in an e=> transition and note the smallest. At each step in the recursion I will stop if I get to a compound I have previously made and will add on it's fewest steps to the end. It is straightforward but may take a few mins to run.

[Pingu]

Took a couple of days off. Just finished day 11. The concept wasn't difficult, but it took me a while to sort out the letter incrementing business.

[David Martin]

Well that doesn't work for day 19 as the time/space required is too big. This requires more thought.

[Pingu]

Finally found an answer to Day 12b (JSON parsing)

(click to show/hide)

Kludged the Processing JSON parser to work with the sample json file. Most parsers seem to be designed to work with a schema where you know what elements / objects / arrays to expect. Since this challenge involves navigating nested arrays and objects with a random structure and set of keys, I had to try for each type and do lots of exception catching when, for example, I tried to read an object when an array was found or integer when a String was found. Not very elegant, but it did find the solution in under a second.

(click to show/hide)

That is more or less what I did. The python stock json parser provides a list of objects. I wrote a recursive function that would test the type of the object it had been given. If it was an int it would return that value, if a list it would call itself on each element of the list, adding the values up and returning those, and likewise for an object - first check to see if it has a value of 'red' and return 0 if so, else iterate through the values and call the function on each one, adding the result.

I'm on 12b now. It's a bit of a bastard. I've not opened the spoilers (yet).

[David Martin]

I had a look at a spoiler for 19

(click to show/hide)

The pattern is not random. Look at what can only appear but never be changed..

[Oaky]

19b is eluding me for now, although I'm sure my BFI (brute force and ignorance) approach isn't the best.

I'm going to leave the BFI job running overnight, since it's not apparently consuming exponential memory, but in the morning, I am going to try a different approach:

(click to show/hide)

I'm going to run rules backwards from the target instead of forwards from e

It may not help, but it beats abusing the company AWS account to do an expensive massively parallel brute force search

[David Martin]

I think your revised approach is by far the most sensible (which is why I started with that. Still haven't managed a suitable solution though I think I know how to find one.

(click to show/hide)

There are two classes of process, and you can replace some elements with appropriate delimiters. Count the number of each element and look at how they can be converted.

[red marley]

Still working on an efficient way of reducing the search space for day 19b.

Day 20 is much easier...

(click to show/hide)

especially when you realise this is just about finding the factors of each house number and the factors of n can be found by testing just 2 to sqrt(n) inclusive.

[David Martin]

I haven't had a chance to look at 20 as my laptop has decided to overheat and kill the graphics every hour or so.

(click to show/hide)

Sussed the sum of factors thing but haven't done anything with it.

[Afasoas]

I took a look at day 7 yesterday and found myself in a perpetual state of confusion.

I might try and take another look at it tonight.

[red marley]

I now have a solution for 19b, Kicking myself I didn't get it earlier.

(click to show/hide)

If you get the algorithm right (and it's really quite simple), the answer can be found in milliseconds. The number of substitutions required is remarkably small (and I suspect for everyone's particular pattern).

[Afasoas]

For 7b, I found someone elses explanation of the problem and now I think I understand it.
I've also found out where the bitwise operators are in PowerShell*.


*I'm learning C and Ruby, I've a smattering of experience with Python, PHP and C#. But I'm nowhere near as proficient in those as I am with PowerShell. I figure if I find time to complete all the chellanges in PowerShell, I can try porting my solutions to other languages.

[David Martin]

Laptop was taken to laptop hospital and I really must finish my coursework marking before getting on with AoC.

[Afasoas]

Still stuck on day 7. I think my logic is sound.
I'm either hitting PowerShells limitations or I'm using it wrong.

Code: [Select]

[uint16]$foo = 1
[Uint16]$bar = $foo -shl 2
[Uint16]$car = $foo -shl 15
[Uint16]$har = $foo -shl 16
write-host "foo: $foo"
write-host "bar: $bar"
write-host "car: $car"
write-host "har: $har"
Output:

Code: [Select]

foo: 1
bar: 4
car: 32768
har: 0

On Edit: I'm being dufus. "shl" and "shr" are working as expected. ... **goes back, stares at code**

[Pingu]

Finally found an answer to Day 12b (JSON parsing)

(click to show/hide)

Kludged the Processing JSON parser to work with the sample json file. Most parsers seem to be designed to work with a schema where you know what elements / objects / arrays to expect. Since this challenge involves navigating nested arrays and objects with a random structure and set of keys, I had to try for each type and do lots of exception catching when, for example, I tried to read an object when an array was found or integer when a String was found. Not very elegant, but it did find the solution in under a second.

(click to show/hide)

That is more or less what I did. The python stock json parser provides a list of objects. I wrote a recursive function that would test the type of the object it had been given. If it was an int it would return that value, if a list it would call itself on each element of the list, adding the values up and returning those, and likewise for an object - first check to see if it has a value of 'red' and return 0 if so, else iterate through the values and call the function on each one, adding the result.

I'm on 12b now. It's a bit of a bastard. I've not opened the spoilers (yet).

12b done at last (without spoilers)! 

[Pingu]

Day 13 completed via a mix of Javascript and spreadsheet. Very much like day 9.

[Pickled Onion]

Yikes, made a bit of meal out of day 9, but quite happy with what I ended up with.

[Pickled Onion]

Quite pleased with this for day 10

(click to show/hide)

Code: [Select]

$input =~ s/((.)\2*)/length($1) . $2/gexms for 1..40;

[Diver300]

In 12b, does "red" after an object mean that the object is ignored?

e.g. { 1, 2, {3, 4} , red }

Should that be 7 or 0?