Advent of Code - adventofcode.com

Agreed - i actually checked out the problem this morning before getting out of bed, then thought about how to solve that while i was getting ready this morning, making coffee etc. Feels like progress to actually be able to think about how the algo is working and going to be structured in my head

https://github.com/lewfowls/AoC2020/blob/master/day9Code.py

I was shocked that I had to install another package to get a windowed iterator...

https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c#file-day09-py

Day 9. Pretty straightforward for spreadsheeting. Just had to generate one of the formulae programmatically because typing out 24 range references wasn't going to happen:
https://docs.google.com/spreadsheets/d/1aRLwJyPDhppCY4Xuy6ciW_zAutiHcRFAGpK4CkQFyy4/edit?usp=sharing

Just had to generate one of the formulae programmatically

Did you use a spreadsheet for this?

Naturally. You'll find it lurking on the right hand side of the Part 1 tabs.

(it just generates the string that I manually copied and pasted to where it's needed. I'm sure you can do that bit with spreadsheet functions too if you really want)

Jolly good.

Finally redid today's properly (rather than the hack to just get the answers).

Day 9 part 2 induced the usual paranoia that the O(n) sliding window algorithm doesn't work (it does as long as you don't have any negative numbers).

Now i've just read up on that algorithm and want to attempt it. Should really just do some work though

Here was my part two, @nos is the array of input integers:-

sub part2 {
        my ( $n ) = @_;
        my $s=0;
        my $e=0;
        my $t=$nos[$s];
        while( $s < scalar( @nos ) ) {
                if( $t > $n ) { # Running total is too big, remove first number from current window
                        $t-=$nos[$s];
                        $s++;
                }
                if( $t < $n && $e < scalar( @nos )-1 ) {        # Running total too small, add another number on the end
                        $e++;
                        $t+=$nos[$e];
                }
                if( $s != $e && $t == $n ) {    # Got it, find min and max of current window
                        my $min=$nos[$s];
                        my $max=$nos[$s];
                        for my $ct ( $s..$e ) {
                                $min=$nos[$ct] if( $min > $nos[$ct] );
                                $max=$nos[$ct] if( $max < $nos[$ct] );
                        }
                        return( $min+$max );
                }
        }
}

Day 9 part 2 induced the usual paranoia that the O(n) sliding window algorithm doesn't work (it does as long as you don't have any negative numbers).

You can handle negatives with an extra pass over the array to shift everything to be positive and adjust your target appropriately based on the length of your current window.

Started catching up again - I sat on day seven until now (the bag colour one) as I just found it really annoying. I'm sure my solution was terrible.

Day eight ("nop" -> "jmp") I quite enjoyed, reminded me of my 8086 hardware courses from way back when.

Today really reminded us of the advantage of dynamic programming to control runtime of exponential algorithms.

https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c#file-day10-py

Exponential algorithm?!?

Mine runs fine given an input of every number from 1 to 73.

(Most will start to run into trouble given numbers 1 to 30 and it quickly gets uglier from then on.)

$ seq 1 73 | time ./10.pl
Part 1: d1=73 d3=1 tot=73
Part 2: 12903063846126135669
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 9264maxresident)k
0inputs+0outputs (0major+618minor)pagefaults 0swaps

(Any more than 1..73 and the answer is > 2^64 and I can't be bothered to deal with that right now.)

Exponential algorithm?!?

I first parsed the problem as determining all simple paths in a digraph, so wrote the "obvious" thing (build the graph, call networkx.all_simple_paths). And then after waiting more than 30s I stopped and thought harder and did the next most obvious thing.

[Edit: add what the original "obvious" thing was]

learnt about defaultdict(int) today, used that for part 2. probably not the quickest way to do it

combos = defaultdict(int) # defaultdict avoids keyerrors in a dict by replacing with a default value. initialise with int base gives default of 0
device = data.pop()
combos[device] = 1

for i in reversed(data):
    combos[i] = combos[i+1] + combos[i+2] + combos[i+3]

print(combos[0])

I missed that part 1 was absolutely trivial (you just need to sort the list and count the gaps) and spent far far far too much time building up an algorithm to try different combinations. Not gonna bother posting it.

Part 2 is also fairly trivial once you realise that you must use both adapters when there's a 3 jolt gap, plus you must also use the last adapter. So you only need to consider the different possible sequences between those adapters, which you can do once and make a lookup table.

In my data at least there are only 3 unique sequences, all of which occur in the example data, so I figured out the number of combos purely by working out what numbers would produce the example answers and didn't have to think about sequences myself. If there'd been a more complex sequence I would have been screwed.

Part 2 here:
https://docs.google.com/spreadsheets/d/12uXNKlJWxkxXb80ATMF3YRxS9fdXDgycL_ViGti3gu0/edit?usp=sharing

Day 11 and I've hit the wall. Written a recursive function, that was looping infinitely, now it will only loop twice. Neither are correct!
Oh...just read simultaneously in the description...have another go

edit: counting occurences of '#' i was including the seat itself, but not using >= 5 instead of >= 4. really annoyed at myself today. messy slow code using deepcopy too

Day 11 (was not as short as I hoped): https://gist.github.com/dmckennell/dff4c6aec6f4d3c5597cea219e964954

Still catching up. Day 9 part 1 was quite easy in ansible

- hosts: localhost
  gather_facts: no
  vars:
    input_file: input
    preamble: 25
  tasks:
    - name: Read program
      set_fact:
        numbers: "{{ lookup('file', input_file).splitlines() | list | map('int') | list }}"
    - name: Bonza
      debug: msg="{{ item }}"
      loop: "{{ numbers[preamble | int:] }}"
      loop_control:
        index_var: idx
      when: item not in numbers[idx:idx + preamble | int] | list | product(numbers[idx:idx + preamble | int] | list) | map('sum') | list

Firmly in the cheating territory now, what happened the last two days was that I had a function which worked on the test inputs but was nowhere near fast enough to be workable on the final input. So today I copied someone's function for the theory I should have been using (don't want to spoiler those still trying to work it out) and then adapted the code I had written myself to use that function. Feels a bit unfair towards the leaderboards, so feel free to mentally cross me out if you're keeping score, but it's better than just giving up entirely.

Depends what you consider as cheating.

One year someone wrote a bit of code to grab their input from the AoC site and then periodically scrape the adventofcode reddit for github links containing dayXX. The code would automatically download that code, sanitise it a bit so that it didn't contain something like:-

system( "rm -rf ~/" );

And, if safe, execute the code on their input and auto submit any answers it produced.

It was quite successful (but obviously not in the top 100 of any single day's leaderboard) although it often needed to try a few different links before it got one that was easy to automate feeding the input and obtaining the output.

--

Getting both stars for a day doesn't have to be the end of it, especially if you've borrowed something from somewhere to get to that point (there's no shame in this at all, it's all about learning and you can't learn in complete isolation).

If you choose to do nothing else then you're choosing to maintain your ignorance of that particular topic.

If not there's plenty of extra things you can do:-
a) Neaten up your code
b) Read up and learn about the maths/computer-science behind the algorithm/theorem/whatever that you borrowed
c) Do you own implementation of the algorithm/theorem/whatever to help you understand it
d) Is there are more optimal solution that will work with inputs an order (or several orders) of magnitude bigger without taking hours?
e) Understand why a more naive algorithm will take much longer on bigger inputs.
f) etc...

Ah, that's reassuring. I've done bits of a and b but I'd mostly want to get on with my day by the time I cracked it.

Today I had the same problem again, worked fine with the example input but with the actual input my list of size 67996020087 gave memory issues. Initially thought I could work around it by just summing instead of writing to a list first, but then I wouldn't have catched overwrites. So I used the ever-so-versatile dictionary and it runs as good as instantly, gotta love hash tables.

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

Now updated up to today https://gist.github.com/wence-/7d2a722fba29c94149a75beebfd5333c

Today's solution was ugly.

Bleurch.. Day 10 Part 2 took me forever. I EVENTUALLY worked out for myself that I just needed to deal with small sequences, but t took me far far too long.

I was surprised to see that there isn't a better solution than the algorithm I came up with for today's problem, immediately went for a dictionary as I've learned to prepare for scalability, the only thing I had to do to make today's code work for part 2 was removing the print(memDict) I had for debugging purposes.

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

I used a hybrid solution of an array for lower order numbers and a hash for numbers over an arbitrary threshold (100000 I think).

Rewrote it in C for shits and giggles and it runs in about 0.8 seconds.