Today’s challenge has us helping a village of programs who are unable to communicate. We have a list of the the communication channels between their houses, and need to sort them out into groups such that we know that each program can communicate with others in its own group but not any others. Then we have to calculate the size of the group containing program 0 and the total number of groups.
Today’s challenge is to help a program find its child process, which has become lost on a hexagonal grid. We need to follow the path taken by the child (given as input) and calculate the distance it is from home along with the furthest distance it has been at any point along the path.
!!! commentary
I found this one quite interesting in that it was very quick to solve. In fact, I got lucky and my first quick implementation (max(abs(l)) below) gave the correct answer in spite of missing an obvious not-so-edge case. Thinking about it, there’s only a ⅓ chance that the first incorrect implementation would give the wrong answer!
Today’s challenge asks us to help a group of programs implement a (highly questionable) hashing algorithm that involves repeatedly reversing parts of a list of numbers.
!!! commentary I went with Haskell again today, because it’s the weekend so I have a bit more time, and I really enjoyed yesterday’s Haskell implementation. Today gave me the opportunity to explore the standard library a bit more, as well as lending itself nicely to being decomposed into smaller parts to be combined using higher-order functions.
In today’s challenge we come across a stream that we need to cross. But of course, because we’re stuck inside a computer, it’s not water but data flowing past. The stream is too dangerous to cross until we’ve removed all the garbage, and to prove we can do that we have to calculate a score for the valid data “groups” and the number of garbage characters to remove.
Today’s challenge describes a simple instruction set for a CPU, incrementing and decrementing values in registers according to simple conditions. We have to interpret a stream of these instructions, and to prove that we’ve done so, give the highest value of any register, both at the end of the program and throughout the whole program.
!!! commentary
This turned out to be a nice straightforward one to implement, as the instruction format was easily parsed by regular expression, and Python provides the eval function which made evaluating the conditions a doddle.
Today’s challenge introduces a set of processes balancing precariously on top of each other. We find them stuck and unable to get down because one of the processes is the wrong size, unbalancing the whole circus. Our job is to figure out the root from the input and then find the correct weight for the single incorrect process.
!!! commentary So I didn’t really intend to take a full polyglot approach to Advent of Code, but it turns out to have been quite fun, so I made a shortlist of languages to try. Building a tree is a classic application for object-orientation using a class to represent tree nodes, and I’ve always liked the feel of Ruby’s class syntax, so I gave it a go.
Today’s challenge asks us to follow a recipe for redistributing objects in memory that bears a striking resemblance to the rules of the African game Mancala.
!!! commentary When I was doing my MSci, one of our programming exercises was to write (in Haskell, IIRC) a program to play a Mancala variant called Oware, so this had a nice ring of nostalgia.
Back to Python today: it's already become clear that it's by far my most fluent language, which makes sense as it's the only one I've used consistently since my schooldays. I'm a bit behind on the blog posts, so you get this one without any explanation, for now at least!
import math
def reallocate(mem):
max_val = -math.inf
size = len(mem)
for i, x in enumerate(mem):
if x > max_val:
max_val = x
max_index = i
i = max_index
mem[i] = 0
remaining = max_val
while remaining > 0:
i = (i + 1) % size
mem[i] += 1
remaining -= 1
return mem
def detect_cycle(mem):
mem = list(mem)
steps = 0
prev_states = {}
while tuple(mem) not in prev_states:
prev_states[tuple(mem)] = steps
steps += 1
mem = reallocate(mem)
return (steps, steps - prev_states[tuple(mem)])
initial_state = map(int, input().split())
print("Initial state is ", initial_state)
steps, cycle = detect_cycle(initial_state)
print("Steps to cycle: ", steps)
print("Steps in cycle: ", cycle)
Today’s challenge has us attempting to help the CPU escape from a maze of instructions. It’s not quite a Turing Machine, but it has that feeling of moving a read/write head up and down a tape acting on and changing the data found there.
!!! commentary I haven’t written anything in C++ for over a decade. It sounds like there have been lots of interesting developments in the language since then, with C++11, C++14 and the freshly finalised C++17 standards (built-in parallelism in the STL!). I won’t use any of those, but I thought I’d dust off my C++ and see what happened. Thankfully the Standard Template Library classes still did what I expected!
Today’s challenge describes some simple rules supposedly intended to enforce the use of secure passwords. All we have to do is test a list of passphrase and identify which ones meet the rules.
!!! commentary Fearing that today might be as time-consuming as yesterday, I returned to Python and it’s hugely powerful “batteries-included” standard library. Thankfully this challenge was more straightforward, and I actually finished this before finishing day 3.
Today’s challenge requires us to perform some calculations on an “experimental memory layout”, with cells moving outwards from the centre of a square spiral (squiral?).
!!! commentary I’ve been wanting to try my hand at Go, the memory-safe, statically typed compiled language from Google for a while. Today’s challenge seemed a bit more mathematical in nature, meaning that I wouldn’t need too many advanced language features or knowledge of a standard library, so I thought I’d give it a “go”. It might have been my imagination, but it was impressive how quickly the compiled program chomped through 60 different input values while I was debugging.