some notes on AoC 2024 1

the challenge is in two parts:

part one

you’re given a list of numbers in pairs, as such

you have to sort them lowest to highest and then measure the “distance” for each pair and add up the total

the distance is just the difference between each number

first i formatted out the numbers into a format that’s more palatable for the computerino

with open('/home/john/Desktop/skeppot/fish/adventofcode/bigboy.txt', 'r') as file:
    numberslist = file.read().split()
numberslist = [int(num) for num in numberslist]
# read the numbers from a file because there are too many for the terminal input
list1 = []
list2 = []
# get the list, separate the numbers out and make them integers
for i in range(len(numberslist)):
    if (i & 1) == 0:
        list1.append(numberslist[i])
    else:
        list2.append(numberslist[i])
# elements of odd-numbered indices go in list1 and even-numbered indices go in list2

this opens the file (there are two in use, one for the challenge and one “bigboy.txt” which is 80mb of pairs for testing), gets rid of all the linebreaks, and makes all of the numbers into integers instead of strings so you can do maths on them

then i make two lists, and put the first, third, fifth, etc numbers in the first and the second, fourth, sixth etc in the second

i do this by checking the last binary digit of each number since it’s faster than using modulo by one operation

list1.sort()
list2.sort()
# sort the lists into ascending order
running_total = 0
# take the nth value of both lists
for i in range(len(list1)):
    value1 = list1[i]
    value2 = list2[i]
    if value1 > value2:
        running_total = running_total + (value1 - value2)
    elif value1 < value2:
        running_total = running_total + (value2 - value1)
# compare the values, subtract the lesser one from the greater one, add the difference to the running total and iterate
print(running_total)

then i use the .sort() function to arrange each list into ascending order

i take the first, second, third, and so on, values of both lists, compare them, subtract the smaller one from the bigger one (to get the difference → distance)

this is all added up into a running total which is my key for the first part

part two

this part is easier, since we have the code to get the lists already

this time we’re looking at “similarity”; how many shared numbers are there between the lists?

similarity_score = 0
count_index = Counter(list2)
for number in list1:
    count = count_index.get(number, 0)
    similarity_score = similarity_score + (number * count)
print(similarity_score)

this is basically all of the extra code aside from importing Counter

make your similarity variable and use Counter to get an index of how many times each number comes up in the second list

others have made their own dictionaries for this but i’m just using Counter because it means the optimization is done for me already

then you run through every number in the first list and check it against your results from Counter

format it in the way the challenge wants and there’s your key for part two

bigboy

i made some optimizations for bigboy, especially to the second one

similarity_score = 0
for number in list1:
    count = list2.count(number)
    similarity_score = similarity_score + (number * count)
print(similarity_score)

this was my previous code for similarity testing, and it was shockingly slow

because bigboy is 4 million pairs long it would search the whole second list for every item in the first

which is dooming you to DNF

which i did, and then made the optimizations above

here's the link to download bigboy if you want it

here are the times for both programs (i split distance and similarity into two)

mileage will vary with the speed of your device, though

here’s all of the code in one box

when you run it do

$ time python3 <file directory>

for the timing

from collections import Counter
with open('/home/john/Desktop/skeppot/fish/adventofcode/bigboy.txt', 'r') as file:
    numberslist = file.read().split()
numberslist = [int(num) for num in numberslist]
# read the numbers from a file because there are too many for the terminal input
list1 = []
list2 = []
# get the list, separate the numbers out and make them integers
for i in range(len(numberslist)):
    if (i & 1) == 0:
        list1.append(numberslist[i])
    else:
        list2.append(numberslist[i])
# elements of odd-numbered indices go in list1 and even-numbered indices go in list2
list1.sort()
list2.sort()
# sort the lists into ascending order
running_total = 0
# take the nth value of both lists
for i in range(len(list1)):
    value1 = list1[i]
    value2 = list2[i]
    if value1 > value2:
        running_total = running_total + (value1 - value2)
    elif value1 < value2:
        running_total = running_total + (value2 - value1)
# compare the values, subtract the lesser one from the greater one, add the difference to the running total and iterate
print(running_total)
similarity_score = 0
count_index = Counter(list2)
for number in list1:
    count = count_index.get(number, 0)
    similarity_score = similarity_score + (number * count)
print(similarity_score)

new optimization: construct the lists on the fly

list1 = [numberslist[i] for i in range(len(numberslist)) if (i & 1) == 0]  # even indices
list2 = [numberslist[i] for i in range(len(numberslist)) if (i & 1) == 1]  # odd indices

if you use list comprehension instead of appending every time you can save a WHOPPING .03 seconds!!!!!

this “if (i & 1) == 1” thing is pretty cool, btw

most people just use modulo, but checking the last digit of the binary string by adding 1 is actually one less operation in the CPU (1 vs 2 for modulo) so it’s very marginally faster, which adds up when you’re doing lots of things with it

here’s a button (see how it says “Subscribe now”? that’s a threat)