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.

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.

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