Advent of Code - adventofcode.com

https://adventofcode.com/

Advent of Code is an Advent calendar of small programming puzzles.

This thread will contain spoilers.

lfgss group code: 194911-f096b184

2020, day 1: I ended up brute-forcing part 2 in Excel, as there weren't many combinations to try.

I'm struggling to remember my Python syntax from last year, but I'm sure it'll come back to me.

I got my Ansible solution for day 1 down to 35 seconds from 30 minutes: https://gist.github.com/rhowe/1059f9da52850f942e7e120d7b11bf80

Near instantaneous (including looking for a 4-tuple that satisfies the requirements) but that's the benefit of not doing in something bonkers like ansible.

$ cat 1.inp | time ./1.pl 4
Answer: 968 1052 = 1018336
Answer: 846 530 644 = 288756720
Answer: 1193 339 339 149 = 20428012197
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 9376maxresident)k
0inputs+0outputs (0major+625minor)pagefaults 0swaps

My python solution of nested for loops takes just under a minute to solve both. 🤷

Using a Scala app with the following snippet
https://gist.github.com/dmckennell/aca20ed0ee112be4806ea0ca7bb09038

gets me

Solving puzzle for Day 1 (Year 2020)
Loading input from 2020/Day01.txt
Part 1 took 0.176238641 seconds
Part 2 took 0.15863768 seconds
Part 1: 926464
Part 2: 65656536

done them both, ES5 javascript cos that's what I use at work, can post my quick and dirty code if anyone's interested.

In my java about 5 millis. It is dirty code but I am surprised it took so long.

https://github.com/ips-james/AdventOfCode/blob/main/day1.py

Anyone know how I make it stop searching after it's found one of the combinations?

I did almost the exact same thing but with Pandas dataframes instead, now I've changed it to lists it runs in barely a second. If you only have a hammer...

I also looked into breaking from nested loops but it wasn't trivial so I decided not to bother. But reading again the highest voted answer to this question has a solution.

import pandas as pd
from datetime import datetime

starttime = datetime.now()
print(starttime)
input_df = pd.read_csv("day1_input.csv", header=None)
\#part1
for index1, row in input_df.iterrows():
    for index2, row in input_df.iterrows():
        if row[0] + input_df[0][index1]  == 2020 :
            print(row[0] * input_df[0][index1])
            finishtime = datetime.now()
            print(finishtime)

\#part2
for index1, row in input_df.iterrows():
    for index2, row in input_df.iterrows():
        for index3, row in input_df.iterrows():
            if row[0] + input_df[0][index1] + input_df[0][index2]  == 2020 :
                print(row[0] * input_df[0][index1]* input_df[0][index2])
                finishtime = datetime.now()
                print(finishtime)

Granted it's not absolutely necessary for day 1 but if you don't see the obvious optimisation then some of the later puzzles are going to be tough going.

Hint: You don't need a nested for loop for part 1 if you use the right data structure. You only need a single nested for loop (e.g. two for loops, not three) for part 2.

Sweet, hadn’t heard of this before. Tackled this first one in Processing.

FWIW here's my python version:-

https://gist.github.com/alexgreenbank/55daaa31c84974e1971af2e40e207784

Thanks

Yep, that makes a lot of sense. Found the same thing in a different language looking at the Reddit solution thread so at least I did the Python implementation myself. Will no doubt be tough going, but that's what I'm doing it for.

expense_list = [int(line) for line in open('day1_input.txt', 'r')]
solved1 = False
solved2 = False

for e in expense_list:
    lookup1 = 2020 - e
    if lookup1 in expense_list:
        print(e * lookup1)
        solved1 = True
        
    for f in expense_list:
        lookup2 = lookup1 - f
        if lookup2 in expense_list:
            print(e * f * lookup2)
            solved2 = True
            
    if solved1 & solved2:
        finishtime = datetime.now()
        print(finishtime)
        exit()

I suppose this is also the moment to familiarize myself with Git so I'm no longer making a mess with codeblocks in this thread.

How come you used a dictionary with all values of 1, rather than a list or a set?

So it's not just pairs of numbers adding up to 2020, but groups of three and more?

In that case I'm out.

expense_list is still a python list in that code, it'll be no faster than using nested for loops.

You need to store the numbers as a python dict to make it faster.

How come you used a dictionary with all values of 1, rather than a list or a set?

Because searching through a list is just like a for loop, it needs to check each item in turn until it finds the item or runs out of items to check.

A python dict is based on a hash table, lookups are almost immediate and lookup performance is consistent regardless of the number of items stored in the dict (assuming you've got a sensible dict implementation). A dict takes a little longer to setup and insert values (and consumes a bit more memory) but that's a small price to pay for the massively faster lookup performance.

Ah ok, I thought a set was just a special case of a dict where there are no values, only keys.

Ah ok, I thought a set was just a special case of a dict where there are no values, only keys.

Yes but none of the above examples were using a set. (I've ninja edited the [and sets] out of my previous reply.)

$ cat z.py
expense_list = [int(line) for line in open('1.inp', 'r')]

print type(expense_list)
$ python z.py
<type 'list'>

And I didn't use a set because I don't really do python and don't know how to instantiate one reliably. Most of my programming is in C where there are no such fancy datatypes, or perl (for hacky prototypes), and perl only has the equivalents of scalars, lists and dicts.

Ah.

$ cat z.py
expense_list = {int(line) for line in open('1.inp', 'r')}

print type(expense_list)
$ python z.py
<type 'set'>

A python dict is based on a hash table, lookups are almost immediate and lookup performance is consistent regardless of the number of items stored in the dict.

That's a very crucial difference, thanks!

Here's my Python solution:

from itertools import combinations
import numpy as np


def sum_target(num_list: list, combs: int, target: int) -> int:
        for t in combinations(num_list, combs):
            if sum(t) == target:
                return np.prod(t)


if __name__ == '__main__':

        with open('day_01_input.txt', 'r') as f:
            input_num_list = [int(x) for x in f.readlines()]

        # Part 1
        print(f'{sum_target(input_num_list, 2, 2020)=}')

        # Part 2
        print(f'{sum_target(input_num_list, 3, 2020)=}')

Probably not as efficient as others but seems readable.

Today's lesson is string parsing and READING THE INSTRUCTIONS PROPERLY.

got the first part right, second part wrong