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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s