# Advent of Code 2018 Week 1: Recap

So I’ve decided to do Advent of Code this year again (no surprise there), but this time, I’m encouraging everyone in HSV.py to join me as well.

I’ve completed 8 challenges, and thought it was time for a recap.  I plan on breaking down solutions day by day, and then ending with some lessons learned that might help others.  I compete each night with ugly hacked together code, then work on refactoring it the next day.  What I share is the refactored version (Don’t think I spit something like this out in just an hour).  You can find all my code on my GitHub

So let’s get started.

# AdventOfCode2017 Day 5 and 6

Another two days down, no sweat (minus a segfault on day 6, but shhhh.)

Day 5’s challenge was to take a list of jump offsets and determine how many jumps you need to take before exiting the block of code (modifying the jump offsets each time)

Day 6’s challenge was to take a list of memory banks, run through a balancing algorithm regarding allocations, and count how many steps until an infinite loop.

Let’s take a look at the code, as they clock in at <40 lines apiece.

Hooray, another easy one.  After Day number 3, I could certainly use it.  This challenge involved taking a list of passphrases, and counting up the number of passphrases that had no duplicate words.   This seems simple, just a split, sort and application of std::unique.

Part 2 had me check for anagrams rather than duplicate words.  This was also easy, as I could map over a sort function to each word in the passphrase, and then check for uniqueness.

Let’s look at the code


#include <algorithm>
#include <iostream>
#include <string>

#include "algo.h"
#include "input.h"

std::string sortString(std::string s) {
std::sort(s.begin(), s.end());
return s;
}

bool isUnique(const std::string& passphrase) {
auto words = algo::map(input::split(passphrase), sortString);
std::sort(words.begin(), words.end());
return words.end() == std::unique(words.begin(), words.end());
}

int main() {
auto count = std::count_if(passPhrases.begin(), passPhrases.end(), isUnique);
std::cout << count << "\n";
return 0;
}


Super straight forward.  I think the trickiest thing was std::unique, because I didn’t realize it returned the end iterator of the range.  But once I figured that out, this wasn’t so bad.

Stay tuned for day 5!

So this day was a tad bit rougher.  I wasn’t expecting the sudden difficulty increase on day 3.  The problems were straight-forward enough, but I didn’t want to brute force my way through them.  Unfortunately, I didn’t get the math worked out, so brute force became one of my last options

However, on the bright side, I got to play with std::optional, so I got that going for me.

I’m going to have a tough time explaining the problem any better than advent of code, so I’m just going to link you there instead

# AdventOfCode2017 Days 1 and 2

It’s December and you know what that means!  Advent Of Code is back!.

This year, I’m not going to try the 25 languages in 25 days, but instead focus on my C++ skills.  More specifically, here are the constraints I am putting on myself.

• Use C++17 where I can if it makes sense
• Avoid raw loops on containers unless I have a performance concern
• If there are any raw loops needed, see if it can be abstracted into a generic algorithm

So Challenge 1: here we go. Continue reading

# 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 == "swap" &&$words =="position"){
swapPos($words,$words);
}
if($words == "swap" &&$words =="letter"){
swapLetters($words,$words);
}
if($words == "rotate" &&$words =="left"){
rotateLeft($words); } if($words == "rotate" && $words =="right"){ rotateRight($words);
}
if($words == "rotate" &&$words =="based"){
rotatePos($words); } if($words == "reverse"){
reverse($words,$words);
}
if($words == "move"){ move($words, $words); } }$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 == "swap" && $words =="position"){ swapPos($words, $words); } if($words == "swap" && $words =="letter"){ swapLetters($words, $words); } if($words == "rotate" && $words =="left"){ rotateRight($words);
}
if($words == "rotate" &&$words =="right"){
rotateLeft($words); } if($words == "rotate" && $words =="based"){ rotatePos($words);
}
if($words == "reverse"){ reverse($words, $words); } if($words == "move"){
move($words,$words);
}
}



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#) # 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 # 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. ## 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) # 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)

# 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


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.