Day 3
After scoring some points on Day 1 and being humbled in Day 2, I was hyped to get into Day 3 of the Advent of Code.
Day 3 Part 1
--- Day 3: Spiral Memory ---
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...
While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.
For example:
- Data from square 1 is carried 0 steps, since it's at the access port.
- Data from square 12 is carried 3 steps, such as: down, left, left.
- Data from square 23 is carried only 2 steps: up twice.
- Data from square 1024 must be carried 31 steps.
How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?
Thought Process
So this question was super similar to a question I had been asked before during an interview except that I had been asked for the coordinates instead of the steps. The steps could be calculated by just adding the absolute values of the coordinates. I scrambled to my laptop to pull up the code that I thought I still had before and eventually found it. Unfortunately, I either hadn’t ran the code or had an old version since I had a bug where I had 1 instead of -1 in one of my constants. Also I had used dir which is a Python keyword so I just added a letter to get my code to run Also I had used dir which is a Python keyword so I just added a letter to get my code to run. there was a little bit of debugging I had to do but eventually I had a running solution.
Solution
def get_pos_after_n_steps(n):
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
dir_index = 0
curr_pos = [0, 0]
i = 2
steps_left = n
while steps_left > 0:
stride = min(steps_left, i/2)
dire = dirs[dir_index]
curr_pos[0] += dire[0] * stride
curr_pos[1] += dire[1] * stride
i = i + 1
steps_left -= stride
dir_index = (dir_index + 1) % 4
print curr_pos
return curr_pos
def steps(coor):
return abs(coor[1]) + abs(coor[0])
val = get_pos_after_n_steps(325488)
print val
print steps(val)
I could have probably saved myself some time by implementing it from scratch and it would have definitely helped for part 2 since this time I would not have overcomplicated it by using strides instead of just stepping one at a time. After losing about half my time to debugging I finished with a time of 11 minutes and 39 seconds and a rank of 162, indicating that this question was much more difficult than the ones in days past.
After crawling the subreddit afterwards, there was an interesting solution that used odd squares which were always in the lower right 1 = (0, 0), 9 = (1, -1), 25 = (2, -2) to solve the problem.
Day 3 Part 2
--- Part Two ---
As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.
So, the first few squares' values are chosen as follows:
- Square 1 starts with the value 1.
- Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
- Square 3 has both of the above squares as neighbors and stores the sum of their values, 2.
- Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4.
- Square 5 only has the first and fourth squares as neighbors, so it gets the value 5.
Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:
147 142 133 122 59
304 5 4 2 57
330 10 1 1 54
351 11 23 25 26
362 747 806---> ...
What is the first value written that is larger than your puzzle input?
Thought Process
At this point I was very disappointed that I didn’t implement it without the strides which would have saved me a lot of time. Although part of me had already accepted defeat, I knew I had to force myself through and went ahead and reimplemented it storing values in a dictionary.
import sys
def spiral(steps):
dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
dir_index = 0
coord = (0, 0)
prev_coord = (0, 0)
store = {coord: 1}
steps_left = 1
count = 1
while store[prev_coord] < steps:
store[coord] = calc_val(store, coord)
print "store"
print coord
print store[coord]
if steps_left == 0:
dir_index += 1
dir_index %= 4
if dir_index % 2 == 0:
count += 1
steps_left = count
prev_coord = coord
coord = (coord[0] + dirs[dir_index][0], coord[1] + dirs[dir_index][1])
# steps -= 1
steps_left -= 1
def calc_val(store, coord):
if coord ==(0, 0):
return 1
val = 0
for i in range(3):
for j in range(3):
if i == 1 and j == 1:
pass
else:
x = coord[0] + i - 1
y = coord[1] + j - 1
if ((x, y) in store):
val += store[(x, y)]
return val
def main():
ans = 0
for line in sys.stdin:
val = int(line)
print spiral(val)
print ans
main()
I eventually finished in 39 minutes and 18 seconds with a rank of 258. Apparently some people had found the sequence online for the second part in The On-line Encyclopedia of Integer Sequences
Day 4
I went into Day 4 back on my laptop with the same base template. This time it was actually useful since the input was a list of strings.
from collections import *
import itertools
import sys
def main():
ans = 0
for line in sys.stdin:
print line
# a = list(map(int, line.strip().split()))
print ans
main()
Day 4 Part 1
--- Day 4: High-Entropy Passphrases ---
A new system policy has been put in place that requires all accounts to use a passphrase instead of simply a password. A passphrase consists of a series of words (lowercase letters) separated by spaces.
To ensure security, a valid passphrase must contain no duplicate words.
For example:
- aa bb cc dd ee is valid.
- aa bb cc dd aa is not valid - the word aa appears more than once.
- aa bb cc dd aaa is valid - aa and aaa count as different words.
The system's full passphrase list is available as your puzzle input. How many passphrases are valid?
Solution
import sys
def main():
ans = 0
for line in sys.stdin:
print line
a = list(line.strip().split())
repeated = False
for i in xrange(0, len(a)):
for j in xrange(0, len(a)):
if a[i] == a[j] and i != j:
repeated = True
if repeated == False:
ans += 1
print ans
main()
This was similar in difficulty to day 1 and with the template I was using, I didn’t have to look up how to parse the input file so I finished in 3 minutes and 14 seconds which was good for rank 265. This was my fastest finish for Part 1 so far but I didn’t even get close to the scoring a point/being in the top 100.
Day 4 Part 2
--- Part Two ---
For added security, yet another system policy has been put in place. Now, a valid passphrase must contain no two words that are anagrams of each other - that is, a passphrase is invalid if any word's letters can be rearranged to form any other word in the passphrase.
For example:
- abcde fghij is a valid passphrase.
- abcde xyz ecdab is not valid - the letters from the third word can be rearranged to form the first word.
- a ab abc abd abf abj is a valid passphrase, because all letters need to be used when forming another word.
- iiii oiii ooii oooi oooo is valid.
- oiii ioii iioi iiio is not valid - any of these words can be rearranged to form any other word.
Under this new system policy, how many passphrases are valid?
Solution
import sys
def anagrams(s1, s2):
def sort(s):
return sorted(s.lower())
return sort(s1) == sort(s2)
def main():
ans = 0
for line in sys.stdin:
print line
a = list(line.strip().split())
repeated = False
for i in xrange(0, len(a)):
for j in xrange(0, len(a)):
if anagrams(a[i], a[j]) and i != j:
repeated = True
if repeated == False:
ans += 1
print ans
main()
I couldn’t figure out what the sort function was for a string so I ended up Googling the anagrams function and modifying that. I finished in 6 minutes and 50 seconds total for both parts which was rank 283 on the leaderboard.
Closing Thoughts
This has definitely been a fun yet humbling experience. A lot of these questions seem like good interview questions with the shorter ones being useful FizzBuzz questions. Stay tuned to see if I can scrape another point in the next 21 days or if my beginner’s luck on Day 1 was just that… luck.
Hopefully, by seeing how this computer science major from Caltech throws together ugly code and keep failing but refusing to give up, you can be motivated to join the Advent of Code challenge too! I was lucky enough to reach my goal of at least 1 point on the first day so hopefully the rest of this challenge will be a fun learning experience!
Apparently Haskell was the way to go. Haskell-ers on the AoC subreddit consistently placed in the top 100 with their one line solutions.