Advent of Code

Posted on
Page
of 8
/ 8
Last Next
  • 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/1059f9da52­850f942e7e120d7b11bf80

  • 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/aca20­ed0ee112be4806ea0ca7bb09038

    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/AdventOfCod­e/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.

  • 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

  • Post a reply
    • Bold
    • Italics
    • Link
    • Image
    • List
    • Quote
    • code
    • Preview
About

Advent of Code

Posted by Avatar for Drakien @Drakien

Actions