Advent of Code 2021 Reflection

Well, it took me way longer than I wanted (I did the first 20 throughout Advent, but took six months off ), but I finally finished 2021’s Advent of Code. It definitely got sloppier as I went on, but hey, I cracked 300 stars! (I only have 48 stars that I have not done at this point)

As I did in previous years, I wrote up a little blurb on each problem, and rated them in both difficulty and how much I liked it. You can find my solutions here. My rules are to use standard library only, write everything else from scratch (no reuse from past years) and lint/mypy as much as I can.

Day 1

Type of Problem: Iteration

Difficulty: Easy

Rating: 4/5

Day 1 typically is an iteration problem, where you have to loop through some data and either aggregate the data or compare the data with its previous or next values. To solve this one efficiently, I zip together the values I want to compare and track the data I want to compare:

MVP was the ability to call the first half’s function from the second.

Measurements = list[int]
def get_number_of_increasing_measurements(measurements: Measurements) -> int:
    measurement_pairs = zip(measurements, measurements[1:])
    return len([p for p in measurement_pairs if p[1] > p[0]])

def get_number_of_increasing_sliding_windows(measurements: Measurements) -> int:
    measurement_sums = [sum(w) for w in
                           zip(measurements, measurements[1:], measurements[2:])]
    return get_number_of_increasing_measurements(measurement_sums)

Read more

Day 2

Type of Problem: Coordinate Systems

Difficulty: Easy

Rating: 3/5

The problems that end up dealing with figuring out where you are after a series of directions are not typically my favorite. Similar to a Mars Rover problem, it’s fairly easy to figure out, and this problem was no different. This involved tracking x and y separately, or tracking x, y , and an aim variable as you go through each move.

Day 3

Type of Problem: Binary Manipulation

Difficulty: Easy-Medium

Rating: 3/5

This involved figuring out which bits are the most common, and doing some bitwise manipulation, so nothing too bad here. However, part 2 involves filtering bitstrings based on certain criteria, which could probably trip some people up as the code bloats on them. I thought this one was okay, as it was a long problem to read for not a complex problem.

MVP goes to my part 1 solution, which zipped each bit together, joined into a new bitstring, and then used bitwise negation to figure out the power rate.

def get_power_rate(numbers: list[str]) -> int:
    bitgroups = zip(*numbers)
    gamma_bitstring = [get_most_common_bit(b) for b in bitgroups]
    gamma_rate = int(''.join(gamma_bitstring), base=2)
    # this is a bit of cheat since we know its 12 bits long
    return gamma_rate * (~gamma_rate & 0xFFF)

Day 4

Type of Problem: Game Simulation

Difficulty: Easy-Medium

Rating: 3/5

This might be a bit more tedious since you are encoding a game of bingo (several, actually) so I ranked it easy-medium because some newbies might find the complexity overwhelming. When doing things like this, I like lots of small classes with useful methods to try and manage the complexity (see below for my Board class).

I also created a game class that handled figuring out which board wins, and which ones are remaining, which made simple while loops easy to write.

class Board:

    def __init__(self, rows: list[Row]):
        assert len(rows) == 5
        self.rows: list[Row] = rows

    def has_won(self) -> bool:
        return (any(row.is_all_marked() for row in self.rows) or
                any(self.is_column_marked(index)
                    for index in range(len(self.rows[0]))))

    def is_column_marked(self, index: int) -> bool:
        return all(row.is_marked(index) for row in self.rows)

    def get_score(self) -> int:
        return sum(row.get_sum() for row in self.rows)

    def apply_move(self, move: int):
        for row in self.rows:
            try:
                position = row.index(move)
                row.mark(position)
            except ValueError:
                pass

Day 5

Type of Problem: Grid Manipulation

Difficulty: Easy

Rating: 4/5

This one involved plotting lines on a grid and finding which point overlaps the most. A simple dictionary from point to number of lines would suffice, so I of course used the collections.Counter class to do just that. Nothing too fancy here:

def get_number_of_overlapping_points_no_diagonal(
            lines: list[LineSegment]) -> int:

    non_diagonal = [l for l in lines if l.is_vertical() or l.get_slope() == 0]
    return get_number_of_overlapping_points(non_diagonal)


def get_number_of_overlapping_points(lines: list[LineSegment]) -> int:
    all_points = itertools.chain.from_iterable(
        line.get_all_points() for line in lines)
    overlaps = Counter(all_points)
    return len([val for val, count in overlaps.items() if count >= 2])

Day 6

Type of Problem: Iteration / Data Structure

Difficulty: Easy-Medium

Rating: 5/5

These sort of problems are satisfying for me. Part 1 can typically be solved by brute force, but if you try doing that for part 2, you’re going to have a bad time. In this case, we have exponential growth of lanternfish, where a new one is created after certain conditions. You could keep a list of lanternfish, but you’ll quickly exhaust memory.

However, if you reduce the problem to just keeping count of how many lanternfish are in each stage, you just have to track roughly 7 counts. collections.Counter to the rescue again:

def get_lanternfish_after(fish: list[int], days: int) -> int:
    counter = Counter(fish)
    for _ in range(days):
        counter = reproduce_fish(counter)
    return sum(counter.values())

def reproduce_fish(counter: Counter) -> Counter:
    new_counter: Counter = Counter()
    for fish, number in counter.items():
        if fish > 0:
            new_counter[fish-1] = number
    if 0 in counter:
        new_counter[6] += counter[0]
        new_counter[8] = counter[0]
    return new_counter

Day 7

Type of Problem: Iteration

Difficulty: Easy-Medium

Rating: 3/5

As I’m writing this, I’m surprised how many pure iteration problems are here in the first week. (I define an iteration problem where you have to loop over your data, and figure out some calculation on it) This time, we’re calculating how much fuel is spent to get to an average position, and you keep moving the crabs until they are there.

Here’s my somewhat convoluted block of calculating fuel spent (whether linear or geometric consumption)

def calculate_fuel_spent(crabs: list[int], pos: int, geometric=False) -> int:
    func = (lambda c: sum(range(1, abs(c - pos) + 1))) if geometric else (lambda c: abs(c - pos))
    return sum(func(c) for c in crabs)

Day 8

Type of Problem: Deduction

Difficulty: Easy-Medium

Rating: 4/5

Deduction problems involve having some obscured information, and then trying to deduce the correct mappings. Typically they are all the same idea, as you create mappings to identify things you know for sure(in this case, some 7-segment display’s digits have a unique number of wires), and then you use that information to rule out other pieces of information, adding to your mapping as you go. Typically straightforward, I appreciated this one for at least having an interesting premise where we had to figure out the different numbers represented by the 7-segement displays.

Day 9

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 5/5

This was my favorite of the early problems. I like problems that have a visual component to them (in this case, figuring out low points of a basin). Each year, I start from scratch (I don’t compete for speed, rather I just like the practice of building components up), so this was my first chance to write my grid class (which I do every year). This year, I added a get_neighbors function so that I could find the orthogonal adjacent points.

The second part was definitely tricky, as you had to find a way to merge basins. In this case, it meant that I was creating a mapping of point to basin. I started in the top-left and iterated through all points, and if you had any point above or to the left, I merged with that basin. If you had no basin to your top or left, you were a new basin, getting a unique ID. Once I mapped point to ID, I just had to use a collections.Counter (my favorite AoC collection type it seems) to count which was the biggest.

Day 10

Type of Problem: Text Parsing

Difficulty: Easy-Medium

Rating: 3/5

The infamous parentheses balancing problem :). I’ve hit this during interviews for two out of the four jobs I’ve held, and it’s a good practice problem for dealing with stacks. This is pretty much identical to code I’ve written in interviews, but I put in some hooks to be able to track corrupt and incomplete scores. This allowed me to use the core function for both parts (I try to reuse as much as I can for both parts rather than rewriting)

(Note, when reviewing this, I should be checking if the letter is in my mapping’s keys or values instead of hardcoding the opening/closing braces.

def parse(line: str,
          on_corrupt: Callable[[str], None] = lambda _: None,
          on_incomplete: Callable[[str], None] = lambda _: None
         ):
    stack: list[str] = []
    for letter in line:
        if letter in "{[(<":
            stack.append(letter)
        if letter in ">]})":
            closing_letter = CLOSING_LETTER[stack.pop(-1)]
            if letter != closing_letter:
                on_corrupt(letter)
                return
    if stack:
        on_incomplete(''.join(stack))

Day 11

Type of Problem: Grid Manipulation

Difficulty: Easy-Medium

Rating: 4/5

I was happy to have my grid class for determining octopuses (octopodes?) interaction with their neighbors (I changed my get_neighbors function to optionally produce diagonal neighbors). In these sort of problems, it doesn’t makes sense to look at every piece of the grid, but instead checking which ones are about to “flash”. Once an octopus flashes, you just have to look at the neighbors and track flashes from them (repeating if necessary)

def flash(octopodes: Grid[Octopus]) -> int:
    flashes = 0

    for point in octopodes:
        octopodes[point] += 1

    potentials = [point for point, octopus in octopodes.items()
                  if octopus == 10]
    while potentials:
        point = potentials.pop(0)
        for neighbor_point,neighbor in octopodes.get_neighbors(point, None,
                                                               diagonal=True):
            if neighbor and neighbor != 10:
                #update original grid point
                octopodes[neighbor_point] += 1
                # it's getting bumped to >9
                if neighbor == 9:
                    potentials.append(neighbor_point)
    # reset and count flashes
    for point, octopus in octopodes.items():
        if octopus == 10:
            flashes += 1
            octopodes[point] = 0
    return flashes

Day 12

Type of Problem: Graph Theory

Difficulty: Medium

Rating: 4/5

I like graph theory problems, I really do. This problem was to find the number of paths through a cave, given that you can only visit a small cave at most once. At first I thought about Hamiltonian or Eulerian paths, but you can do it with just a breadth-first search, tracking which nodes you’ve seen already. The part 2 was allowing one revisit of a node, which just means we track a boolean whether we’ve hit it or not.

Day 13

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 5/5

I like problems that deal with some sort of visualization; this one involved folding a piece of transparent paper with marks and tracking what’s visible. At the end, you have to see what the message is. Straightforward to setup, but I had a few minor issues dealing with the folding logic.

Here’s how I’m folding a group of points. I especially like the list comprehensions and the splat operator (*) to expand lists.

def make_fold(points: list[Point], fold: Fold) -> list[Point]:
    if fold[0] == Direction.VERTICAL:
        normal_half = [p for p in points if p[1] < fold[1]]
        to_be_reversed = [p for p in points if p[1] > fold[1]]
        reverse = [(x, 2*fold[1]-y)
                    for x,y in to_be_reversed]
    else:
        normal_half = [p for p in points if p[0] < fold[1]]
        to_be_reversed = [p for p in points if p[0] > fold[1]]
        reverse = [(2*fold[1]-x, y)
                    for x,y in to_be_reversed]
    return list(set([*normal_half, *reverse]))

Day 14

Type of Problem: Iteration / Data structure

Difficulty: Medium

Rating: 3/5

I dreaded this one seeing it was a polymer chain (I’m still stuck on this polymer chain from 2017), but this didn’t turn out nearly as bad. Anytime you see an answer that is in the billions (or more), you know that you can’t just iterate over the problem, you have to find a more intelligent way of storing it. In this case, collection.Counter comes to the rescue again (My hero for this year). In this case, I just keep track of how many pairs I see, and add to that counter each iteration. Thus, after 40 rounds, I can get an answer lightning quick, because at most I have 16 (the number of possible pairs) counts in my counter.

Day 15

Type of Problem: Graph Theory

Difficulty: Medium

Rating: 5/5

I always like a a good Djikstra’s problem, and this was no exception. Trying to find your way through a grid isn’t too bad, as you use a heap to track your progress instead of a queue (which gives you BFS). Your lowest cost paths are at the top of the heap, and you go until you find the shortest path. I could use A*, but in most AoC problems, I haven’t found it worth the time to implement the heuristic part.

MVP is the heapq module in the standard library

def get_lowest_risk(grid: Grid[int]):
    grid_side_length = int(sqrt(len(grid)))
    start = (0, 0)
    end = (grid_side_length-1, grid_side_length-1)
    smallest_cost = 10*len(grid)*len(grid)
    heap_queue: list[tuple[int, Point, set[Point]]] = [(0, start, set())]
    while heap_queue:
        cost, point, seen = heapq.heappop(heap_queue)
        if point in seen:
            continue
        if cost > smallest_cost:
            continue
        if point == end:
            smallest_cost = cost
            continue
        seen.add(point)
        neighbors = grid.get_neighbors(point, -1) # type: ignore
        for neighbor, value in neighbors:
            if value != -1:
                heapq.heappush(heap_queue, (cost + value, # type:ignore
                                            neighbor, seen))
    return smallest_cost

Day 16

Type of Problem: Parsing / Recursion

Difficulty: Medium

Rating: 3/5

Ah this brings me back to parsing network protocol packets at ADTRAN. This was recursive parsing of a packet, where packets may contain other packets. The trick for these sort of problems is to use an iterator rather than looping through, as keeping a stateful iterator will make it easy to recurse into a sub-problem

Here’s how I broke down the value vs operator packets, so that it was easy to recursively evaluate the packet.

FUNC_LOOKUP: dict[int, Callable] = {
    0: lambda *args: reduce(operator.add, args),
    1: lambda *args: reduce(operator.mul, args),
    2: lambda *args: min(args),
    3: lambda *args: max(args),
    5: lambda t1, t2: 1 if t1 > t2 else 0,
    6: lambda t1, t2: 1 if t1 < t2 else 0,
    7: lambda t1, t2: 1 if t1 == t2 else 0
}
@dataclass
class LiteralValuePacket(Packet):
    value: int

    def get_value(self) -> int:
        return self.value

@dataclass
class OperatorPacket(Packet):
    func: Callable

    def get_value(self) -> int:
        values = [p.get_value() for p in self.subpackets]
        return self.func(*values)

Day 17

Type of Problem: Simulation

Difficulty: Medium-Hard

Rating: 4/5

This is the first stumbling block of the year I had, as I didn’t finish it the first day. I had to do some math to figure out the right answers, and there was a few false starts as I tried to work out the math. Eventually, I went to a simpler solution that worked well for me. I’m not going to paste the whole solution, but I like the interplay here between itertools and zip to figure out the x-step.


def accumulator() -> Generator[tuple[int, int], None, None]:
    yield from zip(itertools.count(start=1), itertools.accumulate(itertools.count(start=1)))


def get_first_x_value(target: Target) -> int:
    return next(i for i,sum in accumulator() if sum >= target[0])

Day 18

Type of Problem: Recursion

Difficulty: Hard

Rating: 3/5

This was another rough one for me. I would not get the right answer, no matter how hard I tried, and had quite a few crashes along the way. I knew I had to do a depth-aware tree, but I had a lot of problems crossing nodes of the tree. I’m not going to paste any code, but it was atrocious. My advice for when you have problems like this, is liberal usage of asserts. I started asserting my preconditions and postconditions and found out where I had logic problems.

Day 19

Type of Problem: Deduction, Coordinate Systems

Difficulty: Hard

Rating: 4/5

Three hard problems in a row (at least for me), as you had to deduce three dimensional coordinates based on distances between points, almost like an inverse triangulation. I had to optimize code all over the place to get it to actually finish. I wrote 160 lines of Python to solve this, and once again, it’s atrocious code. However, I still liked this as far as its uniqueness goes.

Day 20

Type of Problem: Grid Manipulation

Difficulty: Medium

Rating: 3/5

Grid manipulation comes back to figure out how many pixels are lit. I actually read this one wrong and thought this was one of those cellular automation problems where you have to wait until the problem converges to a stable solution. However, once I looked a little closer, I ran it a finite amount times and got the answer quite quickly.

Day 21

Type of Problem: Dynamic Programming

Difficulty: Medium-Hard

Rating: 4/5

This is the problem that took me 6 months to complete. The first half was simple (using iterators) but the second half took me for a loop. I knew dynamic programming was the play, as I had optimal substructure and a recurrence relation with overlapping solutions. The problem was, I picked the wrong recurrence relation.

I thought that the # of universes won was as followed

Wins(Turn, Space, Score) = Sum(Possibilities * Wins(Turn - 1, Space - Roll, Score - Space) for Roll, Possibilities in DicePossibilities)

Where DicePossibilities are the ways you can roll 3, 4, 5, 6, 7, 8 ,9 with 3 dice (for instance, you can roll 4 in 3 different ways (1,1,2; 1,2,1; 2,1,1).

However, this missed some key points. I put in my answer and got a too high answer, which means that I’m double counting something (or overcounting), which is a typical problem of dynamic counting. I was looking for errors in my algorithm, never thinking that my reccurence relation was wrong). However, I was treating a player as independent, when in fact, you shouldn’t count any games in which the other player has already won (nor where you have already run either).

Thus, the recurrence relation is closer to:

Wins(P1Score, P1Space, P2Score, P2Space, IsPlayer1) = Sum(Possibilities * (Wins(P1Score-P1Space, P1Space - Roll, P2Score, P2Space, False) if IsPlayer1 else Wins(P1Score, P1Space, P2Score-P2Space, P2Space - Roll, True)) for Roll, Possibilities in DicePossibilities)

The max score you can get is 30 (hitting a 10 after getting 20 points) so its easy enough to get what you want.

Day 22

Type of Problem: Iteration / Data Structure

Difficulty: Hard

Rating: 5/5

This string of 5 or 6 problems were quite hard. I had to visualize this one with some cube magnets to figure out what I needed. The trick is, given a new cube instruction, you have to figure out if it intersects with any cube you’ve done so far. I processed my cubes backwards, because I knew that if I already did that cube, it would override any previous instruction. To figure out intersection, I would decompose the new cube instruction into six new cuboids, ignoring any parts that were intersecting. It led to this ugly piece of code

 def get_external_cubes(self, cube: 'Cuboid',) -> list['Cuboid']:

        # Assuming our dimensions are Sx, Sy, Sz
        # and our sides are (SXmin, SXmax), (SYmin, SYmax), (SZmin, SZmax)
        # Given the cuboid with dimensions Cx, Cy, Cz and the
        # and its sides are (CXmin, CXmax), (CYmin, CYmax), (CZmin, CZmax)
        # with an intercept area of
        # Xmin, Xmax, Ymin, Ymax, Zmin, zmax

        # if it intersects the cube, there are 6 cuboids that need to
        # be prepended to the list to check
        # with the following dimensions
        # C1 = (Xmin, Xmax), (CYmax, Ymax),  (Zmin, Zmax)
        #    located above the intersection with same x,z
        # C2 = (Xmin, Xmax), (Ymin, CYmin),  (Zmin, Zmax)
        #    located benath the intersection with same x,z
        # C3 = (CXmin, Xmin), (CYmin, CYmax), (Zmin, Zmax)
        #    located to the left of intersection, with full height,
        #    same z
        # C4 = (Xmax, CXmax), (CYmin, CYmax), (Zmin, Zmax)
        #    located to the right of intersection, with full height,
        #    same z
        # C5 = (CXmin, CXmax), (CYmin, CYmax), (Zmin, CZmin)
        #    located in front of intersection, full height/width
        # C6 = (CXmin, CXmax), (CYmin, CYmax), (CZmax, Zmax)
        #    located in front of intersection, full height/width

        # intercept dimensions
        if self.x_min <= cube.x_min <= cube.x_max <= self.x_max:
            xrange = (cube.x_min, cube.x_max)
        elif cube.x_min <= self.x_min <= self.x_max <= cube.x_max:
            xrange = (self.x_min, self.x_max)
        elif self.x_min <= cube.x_min < self.x_max < cube.x_max:
            xrange = (cube.x_min, self.x_max)
        elif cube.x_min < self.x_min <= cube.x_max <= self.x_max:
            xrange = (self.x_min, cube.x_max)
        else:
            assert False, "Missing condition"

        if self.z_min <= cube.z_min <= cube.z_max <= self.z_max:
            zrange = (cube.z_min, cube.z_max)
        elif cube.z_min <= self.z_min <= self.z_max <= cube.z_max:
            zrange = (self.z_min, self.z_max)
        elif self.z_min <= cube.z_min < self.z_max < cube.z_max:
            zrange = (cube.z_min, self.z_max)
        elif cube.z_min < self.z_min <= cube.z_max <= self.z_max:
            zrange = (self.z_min, cube.z_max)
        else:
            assert False, "Missing z condition"

        new_cubes = [
            Cuboid(*xrange, self.y_max + 1, cube.y_max, *zrange),
            Cuboid(*xrange, cube.y_min, self.y_min - 1, *zrange),
            Cuboid(cube.x_min, self.x_min - 1, cube.y_min, cube.y_max,
                   *zrange),
            Cuboid(self.x_max + 1, cube.x_max, cube.y_min, cube.y_max,
                   *zrange),
            Cuboid(cube.x_min, cube.x_max, cube.y_min, cube.y_max,
                   cube.z_min, self.z_min - 1),
            Cuboid(cube.x_min, cube.x_max, cube.y_min, cube.y_max,
                   self.z_max + 1, cube.z_max)
        ]
        valid_cubes = [c for c in new_cubes if c]
        assert(sum(c.get_area() for c in new_cubes if c) < cube.get_area())
        return valid_cubes

Day 23

Type of Problem: Constraint Satisfaction Problem / Graph Theory

Difficulty: Medium

Rating: 5/5

This was another problem I thought was cool. At its heart, its a game, where you enumerate all the moves that can be made (keeping mind of constraints), see what’s possible, and then recurse into a subtree. Again, this is a djikstra’s algorithm through the game’s statespace and heapq makes another appearance.

I really liked the use of generators for my branch-and-pruning:

# get the solution space for possible moves
def get_possible_moves(spaces: Spaces) -> Generator[tuple[int, Spaces],
                                                    None, None]:
    for index, space in enumerate(spaces):
        # get hallway to room moves
        if isinstance(space, str):
            # start walking back and forth until you find an empty room
            yield from move_to_room(spaces, index, 0, -1)
            yield from move_to_room(spaces, index, len(spaces) - 1, 1)
        # get room to hallway moves
        if isinstance(space, Room):
            yield from move_to_hallway(spaces, index, 0, -1)
            yield from move_to_hallway(spaces, index, len(spaces) - 1, 1)

Day 24

Type of Problem: Computer Simulation / Reverse Engineering / Recursion

Difficulty: Hard

Rating: 4/5

This one was a puzzle. Given some assembly language, I first thought that I needed to simulate a computer. Then I realized I needed to check hundreds of billions of numbers, and said no way. I started to work out the assembly language by hand, and realized that for each digit Di, there was the same code run, with variables Xi, Yi, and Zi being the only things that changed.

I worked out that the equation looked like this:

z = z // Zi
if z%26 + Xi == Di:
    z = z*26 + (Di + Yi)

From this, I could set z to zero,, solve for the previous z, and start working my way back to find out all solutions that would eventually produce my result. The code took a little longer than I wanted, but it eventually found a solution, and I eagerly looked ahead to the next solution, given that this one took me about a week or two.

Day 25

Type of Problem: Grid manipulation

Difficulty: Medium

Rating: 3/5

Last puzzle of the year, woo!. This was a simple grid with rule-based movement, that you just had to loop through until the state was the same as the last turn. It took me a little longer than I wanted, because I was not operating on a copy for ‘v’ sea cucumbers. Remember, if everything moves in unison, your code should operate on a copy, so that as you mutate your data, you aren’t influencing current turns.

Advent Of Code 2016 Day 21 (PHP)

Advent of Code 2016 Day 20 (F#)
Advent of Code 2016 – Day 19 (Swift)

Advent of Code 2016 Day 18 (Bash)

Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 20

Start: 1/6/2016

Finish 1/7/2017

Language: PHP

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This challenge was to take a string, and apply a series of transformations on it (Swapping letters, rotating, reversing, etc.)

My idea was to keep an array where the head pointer moves around based on rotations, and operating based on that (similar to the idea of a circular array)

 

Part 1

Code Code Code ……


<?php

$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function printArray() {
    global $arr;
    for ($i = 0; $i < sizeof($arr); $i++){
        echo getCharAt($i);
    }
    echo "\n";
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

function getLines() {
    $f = fopen("../day21.txt", "r");
    $lines = array();
    while (($buffer = fgets($f)) !== false) {
        $lines[] = trim($buffer);
    }
    fclose($f);
    return $lines;
}

function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[2], $words[5]);
    }
}


$lines = getLines();
foreach($lines as $line){   
    processLine($line);
}
printArray();
?>

This was my first foray in PHP in quite some time.  It was a bit more verbose than I remembered, but I still got this one relatively easy.

The main loop was easy, as it mostly took things line by line by line, and then chose a transformation based on the text.

Most transformations are straight forward.  I keep a global array and head pointer, along with a way to convert indices, get characters and set characters in the array.


$head = 0;
$arr = array("a", "b", "c", "d", "e", "f", "g", "h");

function convertIndex($index){
    global $arr, $head;
    $newIndex = $index+$head;
    while($newIndex < 0){
        $newIndex += sizeof($arr);
    }
    return  $newIndex%sizeof($arr);
}
function getCharAt($index)
{
    global $arr, $head;
    $newIndex =convertIndex($index);
    return $arr[$newIndex];
}

function setCharAt($index, $value)
{
    global $arr, $head;
    $arr[convertIndex($index)] = $value;
}

Swapping based on positions and swapping based on letters are pretty straight forward



function swapPos($pos1, $pos2) {
    $tmp1 = getCharAt($pos1);
    $tmp2 = getCharAt($pos2);
    setCharAt($pos1, $tmp2);
    setCharAt($pos2, $tmp1);
}

function swapLetters($letter1, $letter2) {
    global $arr;
    $index1 = array_search($letter1, $arr);
    $index2 = array_search($letter2, $arr);
    $arr[$index2] = $letter1;
    $arr[$index1] = $letter2;
}

Reversing and Rotating were also pretty easy.


function reverse($pos1, $pos2) {
    for ($i = $pos1, $j=$pos2; $i < $j; $i++, $j--){
        swapPos($i, $j);
    }
}

function rotateLeft($steps)
{
    global $head;
    $head += $steps;
}

function rotateRight($steps)
{
    global $head;
    $head -= $steps;
}

Once we get into moving (removing from one index and inserting in the other index), it took me a little while longer to get this.  I treat moving differently based on which direction I’m going to, and then I effectively “bubble” the values to the appropriate position.  I originally tried to do array slicing and recombining, but my wonky index recalculations made it tricky.


function move($from, $to) {
    global $arr;
    
    if ($to =$to; $i--){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i+1, $newChar);
        }
    }
    else {
        $char = getCharAt($from);
        for ($i = $from+1; $i<=$to; $i++){ 
            $newChar = getCharAt($i);
            setCharAt($i, $char);
            setCharAt($i-1, $newChar);
        }
    }
}

Lastly, I worked on the rotate based on the position of a letter.  I pretty much searched for the letter in my array, then figured out how many rotations needed to happen.


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i = 4) {
        $index += 1;
    }
    rotateRight($index+1);
}

 

Part 2

This part was to unscramble a password rather than scramble a password.  I reversed the lines of code, and reversed the relevant sections (such as rotating left when the command is rotate right)


function processLine($line) {
    $words = explode(" ", $line);
    if($words[0] == "swap" && $words[1] =="position"){
        swapPos($words[2], $words[5]);
    }
    if($words[0] == "swap" && $words[1] =="letter"){
        swapLetters($words[2], $words[5]);
    }
    if($words[0] == "rotate" && $words[1] =="left"){
        rotateRight($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="right"){
        rotateLeft($words[2]);
    }
    if($words[0] == "rotate" && $words[1] =="based"){
        rotatePos($words[6]);
    }
    if($words[0] == "reverse"){
        reverse($words[2], $words[4]);
    }
    if($words[0] == "move"){
        move($words[5], $words[2]);
    }
}

The tricky part of this one was figuring out how the rotate based on the position of a letter was handled.  Based on some pen and paper calculations, I found a way to derive how many rotations were needed to get to the next password


function rotatePos($letter) {
    global $arr, $head;
    $index = 0;
    for ($i = 0; $i < sizeof($arr); $i++){
        if (getCharAt($i) == $letter) {
            $index = $i;
            break;
        }
    }
    $numRotations=0;
    for ($j = 0; $j < sizeof($arr); $j++) {
        if ($j = 4 && ($j + $j + 2) % sizeof($arr) == $index) {
            $numRotations = $j+2;
            break;
        }
    }
    rotateLeft($numRotations);
}

 

Wrap-up

I had a lot of stupid mistakes in my part 2.  I kept not thinking through the problem.  Also PHP’s verbosity was weighing me down.  I felt like the array functions were clunky, and my code endd up all over the place.

I give myself a B- on this one.  I could have done better, and thought through the problems better.  My PHP code isn’t great either, so I wasn’t satisfied with this, but it’s better than some other ones.

Next up, is Day 22 with Elm.

 

Advent of Code 2016 Day 20 (F#)

Advent of Code 2016 – Day 19 (Swift)
Advent of Code 2016 Day 18 (Bash)

Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 20

Start: 12/26/2016

Finish 1/6/2017

Language: F#

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This challenge wasn’t too bad at first glance.  Given a list of blacklisted ranges of IP addresses, find the first IP address not in a blacklist.  I decided to give F# a go with this.  After OcaML didn’t go so well, I was determined to use my lessons learned and write some better code.

There was a long delay on this one due to Christmas, and a vacation in between, so I definitely missed my goal of 25 languages in 25 days.  But let’s see how far I can go.

Part 1

As usual, code first.


open System

let readlines  = System.IO.File.ReadAllLines("../day20.txt")
let toInts arr =  Seq.map uint32 arr
let getFilterFunction range =  (fun x -> x  (Seq.last range))
let uintRange = seq { System.UInt32.MinValue..System.UInt32.MaxValue} 
let allFiltersPass (filters:seqbool)>) (num:UInt32) = Seq.forall (fun f -> (f num)) filters
let skipIfOutOfRange filterFuncs = uintRange |> Seq.skipWhile (fun x -> (not (allFiltersPass filterFuncs x)) )

[]
let main argv = 
        Seq.toArray readlines 
        |> Seq.map (fun x -> x.Split[|'-'|])
        |> Seq.map toInts
        |> Seq.map getFilterFunction
        |> skipIfOutOfRange
        |> Seq.head
        |> printfn "%d"
        0


This wasn’t too bad, as I read and sanitize the input to be integers.  Then I just start iterating through numbers from 0 to MAX_INT until I find one that doesn’t fit within all the functions

Part 2

Part 2 is much tougher.  Instead of finding the first non-blacklisted IPs, we needed a count of all non-blacklisted IPs.

The basic idea was to start at zero, and then find the first number that is not in a blacklisted range.  Then find the next number that is a range and subtract the difference.  Add that difference to the sum, and start again with the ranges that are left.

First, I had to implement a solve method to do the basic checking


let rec solve num accum  ranges = 
        let matching = (getFiltersMatching num ranges)
        let remainingRanges = (getRemainingRanges ranges num)
        match Seq.isEmpty matching with
        | true ->
            match (Seq.isEmpty remainingRanges) with
            | true -> accum + (System.UInt32.MaxValue - num) + 1u
            | false -> 
                let invalidNumber = (getFirstInvalidNumber remainingRanges)
                let diff = invalidNumber - num
                solve (getNextStartingNumber (invalidNumber+1u) remainingRanges) (accum + diff) remainingRanges
        | false ->     
            let lastValid = (getLastValidNumber matching)
            match lastValid with
            | System.UInt32.MaxValue -> accum
            | otherwise -> solve (lastValid+1u) accum remainingRanges
       

[]
let main argv = 
        Seq.toArray readlines 
        |> Seq.map (fun x -> x.Split[|'-'|])
        |> Seq.map toInts
        |> solve 0u 0u
        |> printfn "%d"
        0

This was ugly code, to be sure.  First I check if I’m already in a range, and if I am, either I’m at the end of my int range, or I need to recursively check the number out of my current range.  If I’m currently in a number not in a range, I need to check what the next invalid number is.  I subtract my current number from the invalid number and then add it to an accumulator.

I had to write a few utility functions to find information about the ranges


let getFirstInvalidNumber ranges =
         ranges
         |> Seq.map (fun r -> (Seq.head r))
         |> Seq.min

let getNextStartingNumber num ranges = 
        getFiltersMatching num ranges
        |> Seq.map (fun r -> (Seq.last r))
        |> Seq.filter (fun x -> x >= num)
        |> Seq.min

let isNumBeforeRange num range =
        num  Seq.filter (fun r -> (isNumBeforeRange num r) )

let getLastValidNumber ranges =
         match (Seq.isEmpty ranges) with
         | false ->
                ranges
                |> Seq.map (fun r -> (Seq.last r))
                |> Seq.max
         | true -> System.UInt32.MaxValue

These were just straight forward sequence operations.

 

Wrap-up

F# did not go as smoothly as I wanted.  I got part two wrong at first, and it took me a while to write ugly code.  The documentation was great though, and Visual Studio Code was a blast to write F# in (inline type annotations? Yes, please.)  I would definitely consider F# for a .NET project over OcaML.

I give myself a C+ on this one.  I had a vacation in the middle, but I still had some time on either end that I was working on this one.

Next up, PHP.

 

Advent of Code 2016 – Day 19

Advent of Code 2016 Day 18 (Bash)
Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 19

Start: 12/25/2016

Finish 12/26/2016

Language: Swift

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

So I ran into toolchain issues off the bat (just what I feared).  I knew I had a messed up Clang install on my machine, and it caused Swift to not be able to find some .so objects that it wanted.  Thankfully, I found a Docker image to build Swift in.  This was my first time working in Swift, and I enjoyed it.  I had been avoiding it since it was so Apple-oriented (and I haven’t done any Apple development before), but I was quite surprised.  It reminded me of Scala or Rust as far as syntax goes, and it was easy to write code.

This challenge was a rehash of Circle of Josephus.  A quick wiki refresher was what I needed to figure everything out.

Part 1

The code was quite simple :


func josephus(circleSize: Int, num: Int)-> Int {
    var last = 0
    for index in 2...circleSize {
        last=(last + num) % index 
    }
    return last + 1 
}

print(josephus(circleSize: 3014603, num:2))

I don’t even need to spend a whole lot of time on this.  I grabbed the recurrence relation from Wikipedia, and used dynamic programming to transform this into a simple linear loop.

g(n,k)=(g(n-1,k)+k){\bmod  n},{\text{ with }}g(1,k)=0

Part 2

Part two threw me for a loop (no pun intended).  I was fully expecting to see the number go up, but instead, the trick was that instead of every Kth person being eliminated, it was the person directly across who got eliminated.

I tried to do a bunch of mathematical induction and proofs to figure this one out, but kept getting stuck.  I had to go sleep on it, and came up with a better way.  The first person to get eliminated will be n/2 positions away from your index.

First I created a circular linked list to represent the elves in this example.


public class Node {
    var value: Int
    init(value: Int) {
        self.value = value
    }

    var next: Node? = nil
    weak var previous: Node?
}

func createList(size: Int) -> Node {
    let head:Node = Node(value: 1)
    var tail:Node = head
    for index in 2...size {
        let node = Node(value:index)
        node.previous = tail
        tail.next = node
        tail = node
    }
    head.previous = tail
    tail.next = head
    return head
}

Then, I advanced n/2 positions.  Then it was a simple pattern of who got eliminated.  If the circle size was odd, it was n/2 and then you skipped n/2 +1.  If the circle size was even, it was just n/2 (no skipping after).  Thus you get in the pattern, eliminate eliminate skip eliminate eliminate skip eliminate eliminate skip….. and so on.


func removeSelf(node: Node) -> Node {
    let nextNode = node.next!
    let previousNode = node.previous!
    previousNode.next = nextNode
    nextNode.previous = previousNode
    return nextNode
}

func josephus(circleSize: Int)-> Int {
    var list: Node = createList(size: circleSize)
    for _ in 1...circleSize/2 {
        list=list.next!
    }
    for size in stride(from: circleSize, to: 1, by: -1) {
        list = removeSelf(node:list)
        if (size % 2 == 1){
            list=list.next!
        }
    }
    return list.value
}

This got the right answer.

Wrap-up

I give myself a B+ on this.  I got to play around with Swift, and I liked it.  The compiler was helpful, and I found a lot of good examples.  I had to go look at the wiki to remember the Josephus equation, and if I didn’t recognize this as a Josephus problem, I would have been waiting a lot longer.

Next up is Day 20, using F#

Advent of Code 2016 Day 18 (Bash)

Advent of Code 2016 Day 17 (Ruby)
Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 18

Start: 12/22/2016

Finish 12/24/2016

Language: Bash

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

 

So I started with good intentions with Forth.  Then it took me an hour to get the toolchain installed on my linux box (had to go scraping through mailing lists).  Then I spent a lot of time poring over documentation.  After a few hours of working, I couldn’t even figure out how to read a file.  Sometimes you have to know when you’re beat, and I feel like to learn Forth, I really needed a week or two and a good reference to learn it.  I much preferred Factor.

So I made the tough decision to pivot to Bash.  I figured I’d use Bash much more than Forth in my career.  It stung having to back down, but it was bound to happen.

This challenge was about figuring out which tiles were safe to step on, and you could derive the next row of tiles from the previous row.  Then you had to sum up all the safe tiles across a whole lot of rows.

Part 1

Let’s look at the code.


#!/bin/bash
target=$(<"../day18.txt")

getChar() {
    sequence=$1
    index=$2
    if [ "$index" == "-1" ]; then
        char="."
    elif [ "$index" == "${#sequence}" ]; then
        char="."
    else
        char=${sequence:$index:1}
    fi
}
getNextChar() {
    getChar $1 $(($2-1))
    char1=$char
    getChar $1 $2
    char2=$char
    getChar $1 $(($2+1))
    char3=$char
    if [[ "$char1" = "^" && "$char2" = "^" && "$char3" = "." ]]; then
        nextChar="^";
    elif [[ "$char1" = "." && "$char2" = "^" && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char1" = "." && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char3" = "." && "$char1" = "^" ]]; then
        nextChar="^";
    else   
         nextChar=".";
    fi
}

getNextSequence() {
    sequence=$1
    target=""
    for (( i=0; i<${#sequence}; i++)) 
    do
        getNextChar $sequence $i
        target=$target$nextChar
    done
}

rows=40
fullString=""
for (( j=0; j<${rows}; j++))
do
    fullString=$fullString$target
    getNextSequence $target    
done
safe="${fullString//[^.]}"
echo ${#safe}

Starting with the main loop -> We keep looping over the rows getting the next sequence, and concatenating that onto a string.  Then we loop over the string and get the only safe tiles (“.”).



rows=40
fullString=""
for (( j=0; j<${rows}; j++))
do
    fullString=$fullString$target
    getNextSequence $target    
done
safe="${fullString//[^.]}"
echo ${#safe}

The next part is figuring out what each sequence should look like.  We simply loop over the string, determining what the next character should be.   The next character is determined by a set of rules outlined in the problem (see the big four if statements comparing three characters)


getNextChar() {
    getChar $1 $(($2-1))
    char1=$char
    getChar $1 $2
    char2=$char
    getChar $1 $(($2+1))
    char3=$char
    if [[ "$char1" = "^" && "$char2" = "^" && "$char3" = "." ]]; then
        nextChar="^";
    elif [[ "$char1" = "." && "$char2" = "^" && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char1" = "." && "$char3" = "^" ]]; then
        nextChar="^";
    elif [[ "$char2" = "." && "$char3" = "." && "$char1" = "^" ]]; then
        nextChar="^";
    else   
         nextChar=".";
    fi
}

getNextSequence() {
    sequence=$1
    target=""
    for (( i=0; i<${#sequence}; i++)) 
    do
        getNextChar $sequence $i
        target=$target$nextChar
    done
}

The last part is how to get character from a string.  I wanted to wrap this in a function so that out of bounds accesses returned a safe tile (this was important due to the rules of  the problem)


getChar() {
    sequence=$1
    index=$2
    if [ "$index" == "-1" ]; then
        char="."
    elif [ "$index" == "${#sequence}" ]; then
        char="."
    else
        char=${sequence:$index:1}
    fi
}

Part 2

Part 2 made us care about 400,000.  I tried to run the same code again with a different parameter, and after 30 hours of runtime, it wasn’t getting anywhere.

I did some quick profiling using the time command and a smaller solution space size, and figured out the string concatenation was taking the long part.  So I swapped the code up a bit, and ran a count each time during the loop


rows=400000
fullString=""
count=0
for (( j=0; j<${rows}; j++))
do
    safe="${target//[^.]}"
    count=$(($count+${#safe}))
    getNextSequence $target
done
echo $count

After about an hour and a half of runtime, I finally got the right answer

 

Wrap-up

I wanted to get Forth up and going, but I was worried that it was taking too long.  Its not like Bash was that much better, but I had to do something.  The code wasn’t pretty, and it took me three days, but it’s something.  My time is running out (I didn’t think I’d get all 25 languages in 25 days, but there’s still a chance if I motor on up.

I give myself a D- on this one.  I gave up early with Forth, and only with perseverance did I go through with Bash.  I learned some stuff about Bash (knowing I don’t want to do any significant programming in it), like how it handles return values (it doesn’t) and how it handles parameters of functions.

 

Next up, I’ll be trying Swift for Day 19 (assuming I don’t run into any toolchain problems)

 

Advent of Code 2016 Day 17 (Ruby)

Advent of Code 2016 Day 16 (Scala)
Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 17

Start: 12/21/2016

Finish 12/21/2016

Language: Ruby

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This was another find-your-way out of a maze problem, but the trick was every time you entered a room, the paths you could take changed based on the path you have already walked.  Sounded like a job for a Breadth-First Search if you ask me.

I did this one in Ruby, and I was quite pleased with it.  This was my first from-scratch program in Ruby, which is kinda embarrassing, considering I named my dog after the Ruby Programming language.  However, it came together quickly, and it was another session I was quite happy with.

 

Part 1

You know the drill, code first :


require 'digest'

input = "qljzarfv"

def is_valid_hash_character(hash, pos) 
    ('b'..'f').include? hash[pos]
end

Point = Struct.new(:x, :y) do
    def get_moves(input)
        md5 = Digest::MD5.new.update(input)
        hash = md5.hexdigest
        moves = Array.new
        moves << "U" if y != 1 and  is_valid_hash_character(hash, 0)
        moves << "D" if y != 4 and  is_valid_hash_character(hash, 1)
        moves << "L" if x != 1 and  is_valid_hash_character(hash, 2)
        moves << "R" if x != 4 and  is_valid_hash_character(hash, 3)
        moves
    end
end

def move_point(point, move)
    return Point.new(point.x, point.y-1) if move == "U"
    return Point.new(point.x, point.y+1) if move == "D"
    return Point.new(point.x-1, point.y) if move == "L"
    return Point.new(point.x+1, point.y) if move == "R"
end

def move_state(state, move)
    return State.new(move_point(state.point, move), state.passcode+move)
end

State = Struct.new(:point, :passcode) do
    def get_moves
        point.get_moves(passcode)
    end
end

states = [State.new(Point.new(1,1), input)]
while not states.empty? do
    current = states.shift
    if current.point == Point.new(4,4) then 
        puts current.passcode.slice(input.length, current.passcode.length)
        break
    end
    states = states + current.get_moves.map { |move| move_state(current, move)}
end

Not bad, about 50 lines of code.

First I created a point structure that tracked x and y coordinates, while also being able to tell you what moves were valid from where you were.



def is_valid_hash_character(hash, pos) 
    ('b'..'f').include? hash[pos]
end

Point = Struct.new(:x, :y) do
    def get_moves(input)
        md5 = Digest::MD5.new.update(input)
        hash = md5.hexdigest
        moves = Array.new
        moves << "U" if y != 1 and  is_valid_hash_character(hash, 0)
        moves << "D" if y != 4 and  is_valid_hash_character(hash, 1)
        moves << "L" if x != 1 and  is_valid_hash_character(hash, 2)
        moves << "R" if x != 4 and  is_valid_hash_character(hash, 3)
        moves
    end
end

I wanted to keep immutability high on this, so I created a helper function to move a point around.  I’ll tell you, one thing I miss in other languages is the ability to put the if statement at the end of the line (or the unless statement.


def move_point(point, move)
    return Point.new(point.x, point.y-1) if move == "U"
    return Point.new(point.x, point.y+1) if move == "D"
    return Point.new(point.x-1, point.y) if move == "L"
    return Point.new(point.x+1, point.y) if move == "R"
end

Next I wanted to keep track of state by knowing what our current passcode was and our current state (with a move function as well)


def move_state(state, move)
    return State.new(move_point(state.point, move), state.passcode+move)
end

State = Struct.new(:point, :passcode) do
    def get_moves
        point.get_moves(passcode)
    end
end

Finally, the main loop was simply popping a state off a queue, finding the next moves, and pushing all those moves onto the queue.  If I ever ended up in my goal, I’d print out my path (and since this is BFS, I’m guaranteed to find that shortest distance first).


states = [State.new(Point.new(1,1), input)]
while not states.empty? do
    current = states.shift
    if current.point == Point.new(4,4) then 
        puts current.passcode.slice(input.length, current.passcode.length)
        break
    end
    states = states + current.get_moves.map { |move| move_state(current, move)}
end

 

Part 2

Part two asked me to find the longest path that terminated at my goal.  I dreaded this at first, as I was worried some complexity would bite me, but my code still ran fast.  All Ihad to change was the main loop.  Instead of breaking when I found an answer, I would just track if it was the longest so far and continue on with my loop


states = [State.new(Point.new(1,1), input)]
longest = 0
while not states.empty? do
    current = states.shift
    if current.point == Point.new(4,4) then 
        length = current.passcode.length - input.length
        longest = [length, longest].max
    else
        states = states + current.get_moves.map { |move| move_state(current, move)}
    end
end
puts longest

Wrap-up

I give myself another A.  I’m on a roll so far, which is good, because I think the next four languages I’m going to tackle are Forth, Swift, F# and PHP, all of which are going to be interesting.  I wish I had more code in my Ruby stuff that dealt with blocks, but I got a good chance to play around with it’s expressiveness, and I like how it came together.

Next up, I’m going back to another stack-based language and will be playing with Forth for day 18.

Advent of Code 2016 Day 16 (Scala)

Advent of Code 2016 Day 15 (Typescript)
Advent of Code 2016 Day 14 (Go)

Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 16

Start: 12/21/2016

Finish 12/21/2016

Language: Scala

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

This one felt easy.   It was all about generating an ever expanding string in a preset pattern, and then reducing it back down with a predefined algorithm.  Didn’t sound too bad.

I decided to tackle this guy in Scala.  I’ve done a little Scala at work, but not enough to be able to code up a Hello World without looking up a reference.

Part 1

It is nice working in an expressive language.  I tried to keep this as functional as I could, and ended up with 50 lines of Scala Code


object Challenge1 {

  val input = "01000100010010111"
  val diskSize = 272
  def invertByte(c: Char): Char = {
       if (c == '0')  '1' else '0'
  }

  def invert(s: String): String = {
      s.map(c=>invertByte(c))
  }

  def dragonize(s: String): String = {
      s + "0" + invert(s reverse)
  }

  def getDragon(input: String, maxSize: Int) : String = {
      if (input.length >= maxSize) {
          return input.slice(0, maxSize)
      }
      else {
          return getDragon(dragonize(input), maxSize)
      }
  }

  def condenseBytes(c1: Char, c2: Char): Char = {
      if (c1 == c2) '1' else '0'
  }

  def getChecksum(s: String):String = {
      if (s.length % 2 == 1) {
          s
      }
      else{
          val next:String = s.grouped(2).map(s => condenseBytes(s.charAt(0), s.charAt(1))).mkString
          getChecksum(next)
      }
  }

  def main(args: Array[String]): Unit = {
    val s:String = getDragon(input, diskSize)
    val checksum:String = getChecksum(s)
    println(checksum)
    
  }
}

The first part of this was, given a string, expand it by reversing it, inverting the bits, and appending it to the end of the original string (separated by a 0).  Keep doing this until you hit a max limit.  This wasn’t too bad.  I first went down the path of Scala Streams (I do like infinite sequences), but it turns out I didn’t care about the intermediate values, just the last one, so I converted to a function call


def invertByte(c: Char): Char = {
       if (c == '0')  '1' else '0'
  }

  def invert(s: String): String = {
      s.map(c=>invertByte(c))
  }

  def dragonize(s: String): String = {
      s + "0" + invert(s reverse)
  }

  def getDragon(input: String, maxSize: Int) : String = {
      if (input.length >= maxSize) {
          return input.slice(0, maxSize)
      }
      else {
          return getDragon(dragonize(input), maxSize)
      }
  }

The next part was to take our string, and reduce each pair of characters down to a ‘1’ if the two characters were the same or a ‘0’ otherwise.  Again, repeat until you have a string length that is odd.  That is the answer


 def condenseBytes(c1: Char, c2: Char): Char = {
      if (c1 == c2) '1' else '0'
  }

  def getChecksum(s: String):String = {
      if (s.length % 2 == 1) {
          s
      }
      else{
          val next:String = s.grouped(2).map(s => condenseBytes(s.charAt(0), s.charAt(1))).mkString
          getChecksum(next)
      }
  }

Part 2

Just had to change the input size on this (and up the memory on my JVM) and I got the answer lickity-split.

Wrap-up

I give myself an A for this one.  I did it quick, and I kept it closer to the FP side of Scala than the mutable state side.  The answers were right, and I got to learn about streams along the way (even though I didn’t use them in my final solution).

Next up is Ruby for day 17!  Yay for another expressive language.

Advent of Code 2016 Day 15 (Typescript)

Advent of Code 2016 Day 14 (Go)
Advent of Code 2016 Day 13 (Lua)
Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)

Advent of Code 2016 Day 10 (OcaML)

Advent of Code 2016 Day 9 (Factor)

Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)

Advent of Code 2016 – Day 4 (Perl 6)

Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)

Day 15

Start: 12/20/2016

Finish 12/20/2016

Language: Typescript

SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST.  DO NOT LOOK AT MY GITHUB PROJECT.  It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer.  This blog post is not to give away the answer, but instead, is there for people to learn from.

As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016

The Challenge

 

I’m not sure how to describe this challenge, as it was a bunch of math calculations to see when a bunch of interacting circles were in a specific position.   It’s probably best if you go check out the problem yourself, as I really can’t describe it well. 

I decided to try out Typescript on this one.  I prefer static typing, and I want to get better at some languages that compile to Javascript.

Part 1

 

This only took  me 40 lines of TypeScript, so that was real nice.  I think I found a pretty cool solution for taking care of this, and I got to learn about ECMAScript2015 generators along the way.

interface Disc {
   totalPositions: number,
   initialPosition: number,
}

function* infiniteSequence(){
  var index = 0;
  while(true)
    yield index++;
}

function* filter(iterable:IterableIterator, f:(number)=>boolean){
    for(let item of iterable){
        if(f(item)){
            yield item
        }
    }
}

function toDisc(str:string): Disc {
    const regex:RegExp = /Disc #\d has (\d+) positions; at time=0, it is at position (\d+)./
    const matches = str.match(regex);
    return {totalPositions: parseInt(matches[1], 10), initialPosition: parseInt(matches[2], 10)}
}

function isTimeAllowed(num: number, disc:Disc)
{
    return ((num + disc.initialPosition) % disc.totalPositions) == 0;
}

function getAllowedPositions(iterable:IterableIterator, disc:Disc, discNumber:number ){
    return filter(iterable, num => isTimeAllowed(num + discNumber + 1, disc));
}

declare function require(name:string);
const fs = require("fs");
const lines = fs.readFileSync("day15.txt", "utf8").split("\n");
const discs = lines.filter(s => s !== "").map(toDisc);
const allowedNumbers = discs.reduce(getAllowedPositions, infiniteSequence());
console.log(allowedNumbers.next().value);

I’m going to skip over the Disc interface, as it just kept up with the initial position and total number of positions.  Converting from a string to a disc was easy too, as I had the use of a regex to help me out.
So, how I tried to tackle this solution was to start with an infinite sequence of integers to represent my time domain.  I also provided a way to filter out values I didn’t want.

function* infiniteSequence(){
  var index = 0;
  while(true)
    yield index++;
}

function* filter(iterable:IterableIterator, f:(number)=>boolean){
    for(let item of iterable){
        if(f(item)){
            yield item
        }
    }
}
Then, I wanted to reduce each disc against that time series,  continuing to apply a filter function on it to make sure that only that disc’s positions would match up at that time. This meant that I was using the composition of all the discs at once to determine which allowedNumbers I could use.

const allowedNumbers = discs.reduce(getAllowedPositions, infiniteSequence());
console.log(allowedNumbers.next().value);
I calculate if a disk is allowed by taking the discNumber, adding my current time and adding 1.  I add the discNumber since it takes a second to reach each disc, and add 1 since the disc numbers are zero-based and I need them one-based.  Then I add the initial position in and make sure that my modulus of the total positions is zero (meaning I can accept a ball.


function isTimeAllowed(num: number, disc:Disc)
{
    return ((num + disc.initialPosition) % disc.totalPositions) == 0;
}

function getAllowedPositions(iterable:IterableIterator, disc:Disc, discNumber:number ){
    return filter(iterable, num => isTimeAllowed(num + discNumber + 1, disc));
}

Part 2

Another real easy one, as I just had to enter in another line of input to my text file and my code still worked.

 

Wrap-up

I give myself an A- for this one.  Typescript was fun; I prefer static typing and it was still Javascript that I was familiar with.  I didn’t dive deep enough to really understand what else Typescript can buy me, so that’s why its not a straight up A.  I really liked my solution too, as I got to deal with infinite sequences and reducing filter functions over them.

 

Next up is Scala for Day 16.  Back to the JVM for that one.  See you then.