Time permitting I am trying to keep up with the Advent of Code 2024. I will be posting my solutions here as blog entries. I used to really enjoy participating as team captain of one of Virginia Tech's teams for the ACM ICPC. Of course these days I have a full time job and a family so I'll post solutions as I have time or do a few days at a time. I'll be using Python for my solutions as that's the lingua franca of the ML community. My philosophy is to write clean, code that is easy to read and understand. As an AI/ML researcher, my preference will be to use Pandas, then Numpy, then old fashion python as much as it makes sense. Since I am already a day behind I'll just go ahead and post my solutions for the first two days. They're nothing difficult and were enjoyable to write.
The first one was a simple problem of sorting the data in two list and then finding the absolute different between the lists.
import pandas as pd
data = pd.read_csv("input/1_1.txt", delimiter="\\s+", header=None, index_col=None)
data[0] = data[0].sort_values(ignore_index=True)
data[1] = data[1].sort_values(ignore_index=True)
print((data[0] - data[1]).abs().sum())
The second one was also quite simple. It was a similarity score (though not a distance score! as \(\mathrm{score}(a,b) \ne \mathrm{score}(b, a)\) I don't believe is true. As it was, it was a good use of counting the values in one list and then multiplying them by the number of matching values in the other list. Great place to use a dict to count once and lookup many times.
import pandas as pd
data = pd.read_csv("input/1_1.txt", delimiter="\\s+", header=None, index_col=None)
left = data[0]
right = dict(data[1].value_counts())
print(left.apply(lambda x: x * right.get(x, 0)).sum())
They're already forcing me out of platitudes written in pandas. Part of me is annoyed but part of me is happy to be forced to write something else. Essentially here were we're looking find whether a list is monotonic and that the differences between the elements are in the range of \([1,3]\)
import numpy as np
safe = 0
with open("input/2_1.txt") as fp:
for line in fp:
report = np.array([int(x) for x in line.strip().split()])
diff = np.diff(report)
# check if the signs are the same (add up to length) and
# the differences are in the range are <= 3
if (abs(np.sign(diff).sum()) == len(diff)) & np.all(np.abs(diff) <= 3):
safe += 1
print(safe)
The second problem took a little more thought. The easiest thing to do was to check if the reactor was safe and if not then drop one of the elements, check again, and iterate until get true or run out of elements to drop. There's no fun in that solution even though these are small problems. The trick to this one is to know that you only have to check where it fails to be safe and drop one of the surrounding values. There is a special case where the first difference is the wrong one and we need to drop the first value in the list, other than that it works mostly the same. I use numpy here because vectorization makes things go zoom and to save on code.
import numpy as np
def is_safe(report, dropped=False):
diff = np.diff(report)
zeros = np.argwhere(diff == 0).flatten()
signs = np.sign(diff)
monotonic = np.argwhere(signs != signs[0]).flatten()
# edge case: if everything is wrong then the first element is the problem
if len(monotonic) == len(signs) - 1:
monotonic = [0]
limit = np.argwhere(np.abs(diff) > 3).flatten()
problems = np.unique(np.concatenate((zeros, monotonic, limit)))
if len(problems) == 0:
return True
if not dropped:
for i in problems:
for j in (i, i + 1):
if is_safe(np.delete(report, j), True):
return True
return False
safe = 0
with open("input/2_1.txt") as fp:
for line in fp:
report = np.array([int(x) for x in line.strip().split()])
if is_safe(report):
safe += 1
print(safe)
As I am writing this blog post, I realized there is a "mathier" way of doing this: The he distance (or difference if you will) of three points in a list must be interrelated. That is, if \(a, b, c\) are in a list, then:
This would allow you to not have to re-calculate the differences each time.