Advent of Code - adventofcode.com

Day 15 (missed a few days and don't think I'll have time/energy to trawl back): https://gist.github.com/dmckennell/b55a51f8e018792d94381d46cc081c0f

Not the most optimal:

Part 1: 639
Part 2: 266
final map size: 3611963
took 17.286220559 seconds

Just over half a second in relatively simple C:-

(LFGSS mangles # embedded in code blocks.)

# include <stdio.h>
# include <stdlib.h>

int mem[30000000];

int main( int argc, char **argv) {
        int turn=0;
        int last=-1;
        while( argv[turn+1] ) {
                last=atoi(argv[turn+1]);
                mem[last]=turn+1;
                turn++;
        }
        while( turn < 30000000 ) {
                int say=0;
                turn++;
                if( mem[last] > 0 ) say = turn-1-mem[last];
                mem[last]=turn-1;
                last=say;
        }
        printf( "%d\n", last );
        return(0);
}

That array is only ~120MB in size.

$ gcc -ansi -pedantic -Wall -O4 15fast.c -o 15fast
$ time ./15fast 2 1 3
3544142

real    0m0.526s
user    0m0.442s
sys     0m0.084s

It can be so frustrating that 99% correct is still wrong, after comparing my code against working solutions I found out that I'm not catching the 'departure track' field. Tried to fix it for a while but gave up and decided to just add it manually at row 37.

https://github.com/TijmenK/AoC2020/blob/main/day16.py

Today I learned to pass variables instead of messing around with global. I could reuse the code from a couple of days back so most of today's challenge was in plumbing and matching up indexes. A tough one, not sure if I'll make it to the end if the difficulty keeps ramping up.

https://github.com/TijmenK/AoC2020/blob/main/day17.py

Caught up again. Although I'm not super-excited by the game of life style problems like today. Doing it with convolutions made it easy to move from part 1 to part 2. https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c#file-day17-py

Not short or elegant, but it works. I think this is the point where I should start looking at more advanced functions instead of doing everything with for loops and if statements.

https://github.com/TijmenK/AoC2020/blob/main/day18.py

I couldn't be bothered to write my own parser, so relearnt how to use pyparsing https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c#file-day18-py

No need for much parsing. I just used recursion to deal with any parentheses first and then when those are done do the rest iteratively:-

https://gist.github.com/alexgreenbank/9c1fce97c7f1d341b3ddfc92feb6cf67

Used some stacks for day 18. Got lazy and added padding around the braces so everything had a space between it and the next element:

https://gist.github.com/dmckennell/94848a751dd8385a3f9e61bff82adefe

Day 18 part 1:
https://docs.google.com/spreadsheets/d/1SmJDMWM0QfYyfTanZWOrZEGvkDF6yA8EabCrKCAXtdc/edit?usp=sharing

Part 2: https://docs.google.com/spreadsheets/d/1r78qCZenNR7SrqM1HmzznSoJcvQ4im_SmbZ1TcKr0UY/edit?usp=sharing

Easy enough to parse and calculate with just a spreadsheet, but I couldn't figure out an easy way to populate the substitutions tab without angering the circular reference fairy.

Hah. Have fun with Days 19 and 20.

Start of dat 19 seemed okay but I made a mess of two tries. Will need to give it a proper go tomorrow, hard to find concentration but if I don’t catch up tomorrow I don’t think I’ll make it.

Day 19. Bent my rules a bit and used regexes and a bit of manual intervention for part 2:
https://docs.google.com/spreadsheets/d/1c3sM2aFwMljOh9K5EcRXms9jCB55ErwjGsTzpp89TjM/edit?usp=sharing

Day 20:
Ludicrous amount of work for part 2, but very spreadsheetable:
https://docs.google.com/spreadsheets/d/1pMovEAF1L-UlmCy6rSLCFxMGXzA6VrhzESYRUmPPTQY/edit?usp=sharing

Eventually found some time to fill in the gaps again. Day 20 took a while but eventually got a depth first solution that runs in around 2 seconds. I suppose I could try and do something fancier to speed things up, but meh.

Solutions here as usual: https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c

Day 20 alternative input: https://gist.github.com/alexgreenbank/3b14389e7801ddbd22a0c531203de4aa

The trick is to find the four corners first - which you can do by looking for the four tiles with two unique edges.

Then for part 2 you only have to check two (or four) orientations of four tiles as the starting point.

Each edge of a tile is either:-
a) Unique, in which case it is one of the border edges
b) Paired with only one other edge (possibly one being reversed)

As grams says, non-corner edges only have one unique edge (even considering flipping). Corner edges have two adjacent unique edges (even considering flipping).

There's no need for any searching at all.

I processed all tiles and built up a hash/dictionary of edge "numbers" (treating the edge as binary) to tile number. (I took care of the possibility of 'flipped' tiles by also storing the "numbers" associated with the reverse of each of the edges).

So each tile has 8 "numbers" that map to it.

You start by finding a corner (because it has two adjacent unique edges). Rotate it so that the two unique edges point outwards (I started top left so the top and left edges needed to be unique). And then the finding an adjacent tile is simply a case of looking up the corresponding edge number in the hash/dictionary (and ignoring the tile number you already have in place) to get the corresponding tile number. Obviously you may need to flip/rotate the tile you find to get it to fit. Lather, rinse, repeat.

b) Paired with only one other edge (possibly one being reversed)

I guess I didn't check the input for these constraints.

They do seem to reliably keep the input simple on all of the problems so that solutions can be relatively narrow.

Also you only needed to know the corners to answer part 1, which is usually a big hint that there's a shortcut to get there.

I'm trying to learn Python while I am doing this, so my style is very much functional procedural, but I enjoyed the challenges (expect for day 7 part 2, which can f*ck off and burn in hell).

If anyone is interested - goes up to day 9 part 1 for the time being:
https://github.com/rainerkraft/advent_of_code

Went back and did it basically like this (https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c#file-day20b-py) although I didn't bother starting with a corner tile. The longest part was in gluing the thing together in the correct order (I always confuse myself going from image coordinates (bottom left is 0,0) to array coordinates (top left is 0,0)).

And done for the year (with everything here https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c), perhaps I will fill in the missing rust gaps in the coming week, or maybe ride a bike. Didn't feel quite as interesting (or difficult) as last year to me.

Eric's jigged the site in preparation for 2021 (link in the first post of this thread). Obviously no puzzles until 1st Dec.

Will be doing 2021 in Go.

Do you know Go already? Or learning for the challenge?

I've done a little bit, I think I did about 5 days of 2018 in Go before falling back to perl and C, but mostly the impetus is that the new job is a Go shop. One thing I like about AoC is that it often pushes you towards bits of a language that you don't use often enough.

I may also have a play around with Rust and/or Zig if I get a chance.