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

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

Start: 12/19/2016

Finish 12/20/2016

Language: Go

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 problem involving MD5 hash properties.  The goal was to find 64 MD5 hashes of an ever incrementing salt which had a triplet of characters in it (like aaa).  Furthermore, one of the next 1000 hashes had to have the same character repeated 5 times in a row.

I tackled this one with Go, and after a few mis-starts with regex (no backreferences in Go), I was off to the races

 

Part 1

For writing in a language that I’ve never touched before, I actually had this come together in a few hours.  My main algorithm was to memoize hashes as I saw them, as well as saving off the first triplet and all the quintuplets.  I figured the hash was the expensive operation, so I wanted to reduce the time as much as possible.

 

Here’s all the code


package main


import "crypto/md5"
import "encoding/hex"
import "fmt"
import "regexp"
import "strconv"

type Hash struct { 
    hash string
    triplet string
    quintuplets []string
}

var md5s map[int]Hash = make(map[int]Hash)
var salt = "zpqevtbw"
var re3 = regexp.MustCompile(`(aaa|bbb|ccc|ddd|eee|fff|000|111|222|333|444|555|666|777|888|999)`)
var re5 = regexp.MustCompile(`(aaaaa|bbbbb|ccccc|ddddd|eeeee|fffff|00000|11111|22222|33333|44444|55555|66666|77777|88888|99999)`)

func getHash(x int) Hash {
    if val, ok := md5s[x]; ok{
        return val
    }
    hasher := md5.New()
    hasher.Write([]byte(salt+strconv.Itoa(x)))

    hash := hex.EncodeToString(hasher.Sum(nil))

    triplet := re3.FindString(hash)
    t := ""
    if triplet != "" {
        t = string(triplet[0])
    }
    
    
    q := make([]string, 0)
    quintuplets := re5.FindAllString(hash, -1)
    for i := range quintuplets {
       q = append(q, string(quintuplets[i][0]))
        
    }

    md5s[x] = Hash{hash, t, q}
    return md5s[x]
}

func hasQuintuplet(x int, triplet string) bool {
    for i:= x+1; i <= x+1000; i++ {
        hash := getHash(i)
        for j:= range hash.quintuplets {
            if triplet == hash.quintuplets[j] {
                return true
            }
        }
    }
    return false
}

func main() {
    counter := 1
    for numberOfPads := 0; numberOfPads < 64;  {
        hash := getHash(counter)
        if hasQuintuplet(counter, hash.triplet) {
            numberOfPads += 1
        }
       
        counter+=1
    }
    fmt.Println(counter-1)
   
}

Here’s the memoization that I was doing:



func getHash(x int) Hash {
    if val, ok := md5s[x]; ok{
        return val
    }
    hasher := md5.New()
    hasher.Write([]byte(salt+strconv.Itoa(x)))

    hash := hex.EncodeToString(hasher.Sum(nil))

    triplet := re3.FindString(hash)
    t := ""
    if triplet != "" {
        t = string(triplet[0])
    }
    
    
    q := make([]string, 0)
    quintuplets := re5.FindAllString(hash, -1)
    for i := range quintuplets {
       q = append(q, string(quintuplets[i][0]))
        
    }

    md5s[x] = Hash{hash, t, q}
    return md5s[x]
}

Then in my main loop, I would just try to get each hash from an ever increasing counter, and then check if its triplet was in any of the next 1000 hashes.



func hasQuintuplet(x int, triplet string) bool {
    for i:= x+1; i <= x+1000; i++ {
        hash := getHash(i)
        for j:= range hash.quintuplets {
            if triplet == hash.quintuplets[j] {
                return true
            }
        }
    }
    return false
}

func main() {
    counter := 1
    for numberOfPads := 0; numberOfPads < 64;  {
        hash := getHash(counter)
        if hasQuintuplet(counter, hash.triplet) {
            numberOfPads += 1
        }
       
        counter+=1
    }
    fmt.Println(counter-1)
   
}

Part 2

Part 2 was using key-stretching, which just meant that we were running the hash function 2017 times.  Putting my code in a loop made it simple


func applyHash(input string) string {
    
    hash := ""
    for i:=0; i< 2017; i ++ {
        hasher := md5.New()
        hasher.Write([]byte(input))
        hash = hex.EncodeToString(hasher.Sum(nil))
        input = hash
    }
    return hash
}

func getHash(x int) Hash {
    if val, ok := md5s[x]; ok{
        return val
    }
   hash := applyHash(salt+strconv.Itoa(x))

    triplet := re3.FindString(hash)
    t := ""
    if triplet != "" {
        t = string(triplet[0])
    }
    
    q := make([]string, 0)
    quintuplets := re5.FindAllString(hash, -1)
    for i := range quintuplets {
       q = append(q, string(quintuplets[i][0]))
    }

    md5s[x] = Hash{hash, t, q}
    return md5s[x]
}

Wrap-up

This came together quickly (which is much appreciated when I have a 9-5 job and a family to care for), and I learned a bit of Go in the process.  I got to play with slicing and maps, which is core to most Go programming.  I didn’t get a chance to play with Go Channels, which is where Go shines apparently.  In the end, it was easy to find resources (docs were good), but I didn’t think the language was expressive to become one of my favorites.  I only briefly touched upon the ecosystem.

 

I give myself a B+ for this one.  I learned enough to solve the problem, wrote some simple code, and got the answer quickly.

Next up, Day 15 looks a little more challenging, and I’ll be tackling it in another completely new language -> Typescript

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 13

Start: 12/18/2016

Finish 12/19/2016

Language: Lua

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 about finding your way through a maze given open spaces and walls.  You only knew the walls based on a mathematical formula, and you had to take the optimal path to a destination.

This sounds like a job for my favorite algorithm -> the A* search algorithm.  I could use the number of steps I’ve taken so far in addition to the manhattan distance to my target (which works because I could only move horizontally and diagonally) to look for the shortest path to my destination.

I chose Lua for this problem.  At an ADTRAN hackathon I had put Lua into one of our embedded C products, so I had some familiarity.  Let’s see how I did.

Part 1

Not very proud of my main loop, but I’m trying to paste my raw original code as soon as I have it done.  I should have extracted three or four methods, but I didn’t, so here it is.


favorite_number = 1364

function isOdd(num)
    return num % 2 == 1
end


function get_number_of_bits(num, accum)
    if num == 0 then return accum end
    if isOdd(num) then return get_number_of_bits(bit32.rshift(num,1), accum+1) end
    return get_number_of_bits(bit32.rshift(num,1), accum)
end

function compute_is_wall(x,y)
    if x < 0 or y < 0 then return true end
    local num = x*x + 3*x + 2*x*y + y +y*y
    num = num + favorite_number   
    return isOdd(get_number_of_bits(num, 0))     
end


function filter(collection, f)
    local new = {}
    for k,v in pairs(collection) do
        if f(v) then table.insert(new, v) end
    end
    return new
end

eqmt = {__eq = function (k1, k2) return k1[1] == k2[1] and k1[2] == k2[2] end }

gridmeta = { __index = function(t,k) 
                         for key,val in pairs(t) do
                            if key == k then return t[key] end
                         end
                         t[k] = compute_is_wall(k[1], k[2])
                         return t[k]
                       end }
grid = {}
setmetatable(grid, gridmeta)
seen = {}
target = {31,39}
setmetatable(target, eqmt)

function get_manhattan_distance(x,y)
    return math.abs(target[1] - x) + math.abs(target[2] - y)
end

function is_seen(pos)
    for k,v in pairs(seen) do
        if k == pos then return true end
    end
    return false
end

function get_open_spaces(x,y,steps)
    local options =  { {x+1, y, steps+1}, {x-1, y, steps+1}, {x, y+1, steps+1}, {x, y-1, steps+1}}
    setmetatable(options[1], eqmt)
    setmetatable(options[2], eqmt)
    setmetatable(options[3], eqmt)
    setmetatable(options[4], eqmt)
    return filter(options, (function(v)  return not grid[v] and not is_seen(v); end))
end

function get_best_option(options)
    best = {1,1, 100000000}
    for k,v in pairs(options) do
        if v[3] + get_manhattan_distance(v[1], v[2])  < best[3] + get_manhattan_distance(best[1], best[2]) then
            best = v
        end
    end
    return best
end

function main()
    options = {{1,1, 0}}
    setmetatable(options[1], eqmt)
    while true do
        position = get_best_option(options)
        if(not is_seen(position)) then
            seen[position] = true
        end

        for k,v in pairs(options) do
            if options[k] == position then 
                options[k] = nil
                break
            end
        end
        spaces = get_open_spaces(position[1], position[2], position[3])
        for _,space in pairs(spaces) do
            if(space == target) then
                return space[3]
            end
            table.insert(options, space)
        end
    end
end

print(main())

The code to compute is a wall is pretty straight-forward:



function isOdd(num)
    return num % 2 == 1
end


function get_number_of_bits(num, accum)
    if num == 0 then return accum end
    if isOdd(num) then return get_number_of_bits(bit32.rshift(num,1), accum+1) end
    return get_number_of_bits(bit32.rshift(num,1), accum)
end

function compute_is_wall(x,y)
    if x < 0 or y < 0 then return true end
    local num = x*x + 3*x + 2*x*y + y +y*y
    num = num + favorite_number   
    return isOdd(get_number_of_bits(num, 0))     
end

 

The cool thing about Lua is metatables.  Since a table is the only data structure in Lua, metatables are what gives Lua a lot of power.  I used metatables to compute if the space was a wall or not, and then cache it for later uses (so that I wasn’t doing a bunch of multiplications again and again and again)


gridmeta = { __index = function(t,k) 
                         for key,val in pairs(t) do
                            if key == k then return t[key] end
                         end
                         t[k] = compute_is_wall(k[1], k[2])
                         return t[k]
                       end }
grid = {}
setmetatable(grid, gridmeta)

 

One thing that bit me was the fact that tables aren’t equal just because there keys and values are equal.  So I had to define a equality metatable (eqmt) and use it wherever I was representing an X,Y coordinate.  I took a long time on this, as it slowed down tracking which I’ve seen last, as well as caching my wall calculations.


eqmt = {__eq = function (k1, k2) return k1[1] == k2[1] and k1[2] == k2[2] end }

 

For each position I evaluate, I need to figure out what the next open spaces are.  I look in the four cardinal directions (making sure that all my tables can be checked for equality) and then run over a custom filter function to make sure its not a wall and it hasn’t been seen already.


function get_open_spaces(x,y,steps)
    local options =  { {x+1, y, steps+1}, {x-1, y, steps+1}, {x, y+1, steps+1}, {x, y-1, steps+1}}
    setmetatable(options[1], eqmt)
    setmetatable(options[2], eqmt)
    setmetatable(options[3], eqmt)
    setmetatable(options[4], eqmt)
    return filter(options, (function(v)  return not grid[v] and not is_seen(v); end))
end

 

For the main loop, I run my heuristic to find my best option, figure out my next moves from there, and add it to the option list.


function get_best_option(options)
    best = {1,1, 100000000}
    for k,v in pairs(options) do
        if v[3] + get_manhattan_distance(v[1], v[2])  < best[3] + get_manhattan_distance(best[1], best[2]) then
            best = v
        end
    end
    return best
end

function main()
    options = {{1,1, 0}}
    setmetatable(options[1], eqmt)
    while true do
        position = get_best_option(options)
        if(not is_seen(position)) then
            seen[position] = true
        end

        for k,v in pairs(options) do
            if options[k] == position then 
                options[k] = nil
                break
            end
        end
        spaces = get_open_spaces(position[1], position[2], position[3])
        for _,space in pairs(spaces) do
            if(space == target) then
                return space[3]
            end
            table.insert(options, space)
        end
    end
end

 

This ran blazing fast, and it made me think that if I were to get equality on tables right the first time around, a Breadth First Search might have been sufficient.

Part 2

The next part of the code required that I find all unique coordinates within 50 steps.  Here a breadth first search was easy, and I just kept a count of positions I had not seen before


count = 0
function main()
    options = {{1,1, 0}}
    setmetatable(options[1], eqmt)
    stopLooping = false
    while not stopLooping do
        position = options[1]
       
        if(not is_seen(position)) then
            count = count+1
            seen[position] = true
        end
        table.remove(options, 1)
        if(position[3] <= 49) then
            spaces = get_open_spaces(position[1], position[2], position[3])
            for _,space in pairs(spaces) do
                if(space == target) then
                    return space[3]
                end
                table.insert(options, space)
            end
        end
        stopLooping = (#options == 0)
    end
end

 

Wrap-up

It took me a little longer than it should have, as the aforementioned Lua table equality metamethod was missing for a while, which slowed me down.   But once I figured that out, I was done with both part 1 and part 2 in an hour.

My final grade for this is a solid B.  I got to use metatables and metamethods, and I always love writing an A* search, but I still had hindrances along the way.

For Day 14, looks like I’m back to calculating MD5 hashes, and I’m going to try out Go.

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 11

Start: 12/14/2016

Finish 12/18/2016

Language: Groovy

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 decided to go to the JVM ecosystem and try out the scripting language Groovy.  While the language itself didn’t boggle me (I had one big hang-up, but more on that later), but the problem took a long time (and I took two days off as well).

This challenge was an elaborate riff on the Farmer, Wolf, Goat and Cabbage crossing the river problem.  We had to move machine parts up and down floors, with incompatible configurations on a floor bricking your machines.

One of my favorite classes of problems are Constraint Satisfaction Problem, so I thought I’d tackle it with Branch-and-Prune with Backtracking.  But man, was I in for some unexpectedness.

 

Part 1

I wrote up all my code, and tried it out on the sample problem.  It got it no problem.  So then I loaded the bigger problem in, and after thirty minutes of runtime, I ran out of memory on my JVM.  This was my first sign of trouble.  I threw 16 gigs of RAM at the problem, but that didn’t help either.  The code ran all night with barely inching forward.  Hooray exponential big-O time.  One thing to remember with Branch and Prune is the more you can prune, the better off you will be, so I started pruning.  I found cases where it didn’t make sense to move pairs of machines, as it would always result in incompatibilities.  I figured out once a floor below is empty, you never need to go back to it.  But still, runtimes were killing me.  There was no way the code would finish in a century, let alone in the few minutes that I wanted it.

I looked up some hints on the Reddit thread, as I felt my code would work, just was too long.  Unfortunately , all the hints they gave are ones I had already considered myself.  The big hint was to skip over equivalent building structures, and I thought I had done that.  But, it turns out, my custom equals() method was never called.  The indexOf and contains methods I was using in Groovy were checking object equality, not calling my equals() method (or at least, that’s what I suppose).  Once I changed that, I had an answer in thirty minutes.

 

Let’s look at the code


class Floor implements Cloneable 
{
    def microchips;
    def generators;

    def Floor(String floorInfo)
    {
        this.microchips = getEquipmentOnFloor floorInfo, "microchip"
        this.generators = getEquipmentOnFloor floorInfo, "generator"
        this.microchips = this.microchips.collect { new String(it.charAt(0))+"m" }
        this.generators = this.generators.collect { new String(it.charAt(0))+"g" }
    }

    private Floor() { }

    def clone()
    {
        def c = new Floor()
        c.microchips = this.microchips.collect { new String(it) }
        c.generators = this.generators.collect { new String(it) }
        c
    }

    def print()
    {
        this.microchips.each { println "Microchip $it" }
        this.generators.each { println "Generator $it" }
    }

    def isEmpty()
    {
        return this.microchips.isEmpty() && this.generators.isEmpty()
    }

    def remove(option)
    {
        option.each{ op ->
            if (op.charAt(1) == 'm') {
                this.microchips.remove(this.microchips.indexOf(op))
            }
            else if (op.charAt(1) == 'g')
            {
                this.generators.remove(this.generators.indexOf(op))
            }
        }
    }

    def add(option)
    {
        option.each {
            op ->
              if (op.charAt(1) =='m'){
                  this.microchips.add(op)
              }
              else
              {
                  this.generators.add(op)
              }
        }
    }

    def get_safely_removable_combos()
    {
        def safely_removable = []
        def combos = this.microchips.clone()
        combos.addAll(this.generators)
        combos.each { c1 ->
             combos.each { c2 ->
                if(!c1.equals(c2) &&  this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
                {
                    if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
                    {
                        safely_removable << [c1, c2].sort()
                    }
                }
            }
             if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
                safely_removable << [c1]
             } 
             if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
                safely_removable <  generators.isEmpty() || generators.any {gen -> mc.charAt(0) == gen.charAt(0)} }
    }

    def isSafe()
    {
        return isSafeToLeave(this.microchips, this.generators)
    }


    def getEquipmentOnFloor(String floorInfo, String type)
    {
        def words = floorInfo.split(" ");
        def output = []
        for(int i =0; i < words.length; ++i)
        {
            if(words[i].startsWith(type))
            {
                output < new Floor(it)}
        this.elevator = 0;       
    }

    private Building()
    { }

    def clone() {
        def blding = new Building()
        blding.floors = this.floors.collect { it.clone() }
        blding.elevator = this.elevator
        blding.lastBuilding = this
        return blding
    }

    def equals(Building bldg) {
        return this.getPairs() == bldg.getPairs()
    }

    def getPairs()
    {
        def pairs = [:]
        (0..3).each {
            this.floors[it].microchips.every {mc ->
                 if (pairs[mc.charAt(0)] == null) {
                     pairs[mc.charAt(0)] = [-1, -1]
                 } 
                  pairs[mc.charAt(0)][0] = it
            }
            this.floors[it].generators.every {gen ->
                 if (pairs[gen.charAt(0)] == null) {
                     pairs[gen.charAt(0)] = [-1, -1]
                 } 
                  pairs[gen.charAt(0)][1] = it
            }
        }
        pairs.values().sort()
    }

    def print(){
        this.floors.eachWithIndex { it, index->
            print "Floor -> "
            println index
            it.print();
            
        }
        println ""
    }

    def get_possible_things_to_remove()
    {
        this.floors[elevator].get_safely_removable_combos()
    }

    def makeMove(new_floor, option)
    {
        this.floors[this.elevator].remove(option)
        this.elevator = new_floor
        this.floors[this.elevator].add(option)
    }

    def isFinished()
    {
        return this.floors[0].isEmpty() && this.floors[1].isEmpty() && this.floors[2].isEmpty()
    }

    def isGood(lastFloor) {
        return this.floors[this.elevator].isSafe() && this.floors[lastFloor].isSafe()
    }

    def areFloorsBelowEmpty()
    {
        (0..(this.elevator-1)).every { this.floors[it].isEmpty()}
    }
}


def find_solution(building)
{
    def buildings = [building]
    def time
    def seenBuildings = [0:[building], 1:[], 2:[], 3:[]]
    for(time = 0; buildings.size()!=0 && !buildings.any { it.isFinished() }; ++time)
    {
        def newBuildings = []
        buildings.each { 
             bldg ->
                getBuildingCandidates(bldg).each 
                    { candidate ->
                    if(seenBuildings[candidate.elevator].every { !it.equals(candidate) } )
                        newBuildings << candidate
                        
                        seenBuildings[candidate.elevator] << candidate
                }
         }   
        buildings = newBuildings
        println buildings.size()
    }
    time
}

def getBuildingCandidates(bldg)
{
    def candidates = []
    def options = bldg.get_possible_things_to_remove()
    if (bldg.elevator  0 && !bldg.areFloorsBelowEmpty())
    {
        candidates.addAll(getCandidatesOnNewFloor(bldg, bldg.elevator-1, options.grep{it.size() == 1}))
    }
    candidates
}
def getCandidatesOnNewFloor(bldg, newFloor, options)
{
    def candidates = []

    options.each { option ->
        candidate = apply_move(newFloor, option, bldg)
        if(candidate.isGood(bldg.elevator)) {
            candidates << candidate                            
        }
    }
    candidates
}

def apply_move(floor, option, building)
{
    clonedBuilding = building.clone()
    clonedBuilding.makeMove(floor, option)
    clonedBuilding
}



def fileContents = new File("day11.txt").text.split("\n")
def building = new Building(fileContents)


println find_solution(building)

First I’ll highlight the Floor class.  This takes in a string and figures out what microchips and generators are on that floor.  I provide clone methods, and ways to print, remove, and add equipment to the floor.


class Floor implements Cloneable 
{
    def microchips;
    def generators;

    def Floor(String floorInfo)
    {
        this.microchips = getEquipmentOnFloor floorInfo, "microchip"
        this.generators = getEquipmentOnFloor floorInfo, "generator"
        this.microchips = this.microchips.collect { new String(it.charAt(0))+"m" }
        this.generators = this.generators.collect { new String(it.charAt(0))+"g" }
    }

    private Floor() { }

    def clone()
    {
        def c = new Floor()
        c.microchips = this.microchips.collect { new String(it) }
        c.generators = this.generators.collect { new String(it) }
        c
    }

    def print()
    {
        this.microchips.each { println "Microchip $it" }
        this.generators.each { println "Generator $it" }
    }

    def isEmpty()
    {
        return this.microchips.isEmpty() && this.generators.isEmpty()
    }

    def remove(option)
    {
        option.each{ op ->
            if (op.charAt(1) == 'm') {
                this.microchips.remove(this.microchips.indexOf(op))
            }
            else if (op.charAt(1) == 'g')
            {
                this.generators.remove(this.generators.indexOf(op))
            }
        }
    }

    def add(option)
    {
        option.each {
            op ->
              if (op.charAt(1) =='m'){
                  this.microchips.add(op)
              }
              else
              {
                  this.generators.add(op)
              }
        }
    }

    def get_safely_removable_combos()
    {
        def safely_removable = []
        def combos = this.microchips.clone()
        combos.addAll(this.generators)
        combos.each { c1 ->
             combos.each { c2 ->
                if(!c1.equals(c2) &&  this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
                {
                    if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
                    {
                        safely_removable << [c1, c2].sort()
                    }
                }
            }
             if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
                safely_removable << [c1]
             } 
             if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
                safely_removable <  generators.isEmpty() || generators.any {gen -> mc.charAt(0) == gen.charAt(0)} }
    }

    def isSafe()
    {
        return isSafeToLeave(this.microchips, this.generators)
    }


    def getEquipmentOnFloor(String floorInfo, String type)
    {
        def words = floorInfo.split(" ");
        def output = []
        for(int i =0; i < words.length; ++i)
        {
            if(words[i].startsWith(type))
            {
                output << (words[i-1]);
            }
        }
        output;
    }
}

The big piece is the get_safely_removable_combos.  This tells me what I can safely remove from the floor without invalidating what is on it.  I check all pairs and only move two of the same type (such as two microchips or two generators) or a matching pair.  Then I check each microchip and generator independently.


def get_safely_removable_combos()
    {
        def safely_removable = []
        def combos = this.microchips.clone()
        combos.addAll(this.generators)
        combos.each { c1 ->
             combos.each { c2 ->
                if(!c1.equals(c2) &&  this.isSafeToLeave(this.microchips.grep {!it.equals(c1) && !it.equals(c2)}, this.generators.grep {!it.equals(c1) && !it.equals(c2)} ))
                {
                    if(c1.charAt(1) == c2.charAt(1) || c1.charAt(0) == c2.charAt(0))
                    {
                        safely_removable << [c1, c2].sort()
                    }
                }
            }
             if (this.isSafeToLeave(this.microchips.grep { !it.equals(c1)}, this.generators) ){
                safely_removable << [c1]
             } 
             if (this.isSafeToLeave(this.microchips, this.generators.grep { !it.equals(c1)}) ){
                safely_removable << [c1]
             }

        }
        safely_removable.unique()
    }

Next up was modelling the entire building.  You’ll find clone methods and equals() methods.  Instead of checking strict equality, we’re instead checking that the pairs of equipment match up (So that a plutonium microchip and a plutonium generator on the first floor is the same as a dilithium microchip and a dilithium generator on the first floor).

I also provide a way to check if things are safe and if we are at a finished state (everything on the fourth floor)



class Building implements Cloneable
{
    def floors;
    def elevator;
    def lastBuilding = null

    Building(String[] buildingInfo)
    {
        this.floors = buildingInfo.collect {it -> new Floor(it)}
        this.elevator = 0;       
    }

    private Building()
    { }

    def clone() {
        def blding = new Building()
        blding.floors = this.floors.collect { it.clone() }
        blding.elevator = this.elevator
        blding.lastBuilding = this
        return blding
    }

    def equals(Building bldg) {
        return this.getPairs() == bldg.getPairs()
    }

    def getPairs()
    {
        def pairs = [:]
        (0..3).each {
            this.floors[it].microchips.every {mc ->
                 if (pairs[mc.charAt(0)] == null) {
                     pairs[mc.charAt(0)] = [-1, -1]
                 } 
                  pairs[mc.charAt(0)][0] = it
            }
            this.floors[it].generators.every {gen ->
                 if (pairs[gen.charAt(0)] == null) {
                     pairs[gen.charAt(0)] = [-1, -1]
                 } 
                  pairs[gen.charAt(0)][1] = it
            }
        }
        pairs.values().sort()
    }

    def print(){
        this.floors.eachWithIndex { it, index->
            print "Floor -> "
            println index
            it.print();
            
        }
        println ""
    }

    def get_possible_things_to_remove()
    {
        this.floors[elevator].get_safely_removable_combos()
    }

    def makeMove(new_floor, option)
    {
        this.floors[this.elevator].remove(option)
        this.elevator = new_floor
        this.floors[this.elevator].add(option)
    }

    def isFinished()
    {
        return this.floors[0].isEmpty() && this.floors[1].isEmpty() && this.floors[2].isEmpty()
    }

    def isGood(lastFloor) {
        return this.floors[this.elevator].isSafe() && this.floors[lastFloor].isSafe()
    }

    def areFloorsBelowEmpty()
    {
        (0..(this.elevator-1)).every { this.floors[it].isEmpty()}
    }
}

Finally, there is the bulk of the CSP solution – how to find a solution.

I keep track of what I’ve seen per floor so that I don’t repeat previously seen states (again, trying to prune as much as possible) and then I just iterate through all possible options, adding all safe options to a queue, and then looping back over the queue


def find_solution(building)
{
    def buildings = [building]
    def time
    def seenBuildings = [0:[building], 1:[], 2:[], 3:[]]
    for(time = 0; buildings.size()!=0 && !buildings.any { it.isFinished() }; ++time)
    {
        def newBuildings = []
        buildings.each { 
             bldg ->
                getBuildingCandidates(bldg).each 
                    { candidate ->
                    if(seenBuildings[candidate.elevator].every { !it.equals(candidate) } )
                        newBuildings << candidate
                        
                        seenBuildings[candidate.elevator] << candidate
                }
         }   
        buildings = newBuildings
        println buildings.size()
    }
    time
}

def getBuildingCandidates(bldg)
{
    def candidates = []
    def options = bldg.get_possible_things_to_remove()
    if (bldg.elevator  0 && !bldg.areFloorsBelowEmpty())
    {
        candidates.addAll(getCandidatesOnNewFloor(bldg, bldg.elevator-1, options.grep{it.size() == 1}))
    }
    candidates
}
def getCandidatesOnNewFloor(bldg, newFloor, options)
{
    def candidates = []

    options.each { option ->
        candidate = apply_move(newFloor, option, bldg)
        if(candidate.isGood(bldg.elevator)) {
            candidates << candidate                            
        }
    }
    candidates
}

def apply_move(floor, option, building)
{
    clonedBuilding = building.clone()
    clonedBuilding.makeMove(floor, option)
    clonedBuilding
}

Part 2

No change here, as I just had to run with 4 extra pieces of equipment.  The solution took 2 hours to compute (still too long in my mind) but I am a few days behind now and got to catch up.

Wrap-up

Grade: A big fat “F”errooni.  I took 5 days.  I looked up hints.  My Groovy code is sprawling.  I got the wrong answer a few times.  This was not pleasant.  The problems are getting harder.  I learned a lot, and I feel comfortable in Groovy now, but my ultimate feeling was that it was too Java-ish for Ruby town, and too Ruby-ish for Java town.  It sat in the middle of the two for me, which was nice, but I could feel the influences seeping in (like object equality vs object equivalence).

 

Next up, it looks like I’m writing a simple assembler, and I think I’ll try it out in my first .NET language ever, C#.