Coding Challenge

Advent of Code 2016 Day 11 (Groovy)

~ patviafore ~ 10 Comments
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#.

 

Advent of Code 2016 Day 10 (OcaML)

~ patviafore ~ 11 Comments

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 10

Start: 12/13/2016

Finish 12/13/2016

Language: OcaML

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 OcaML happened.  Another day I struggled with.   It took me a while to get the toolchain set up, I didn’t understand that ;; only needed to be added for REPL lines (which made pasting between REPL and source code file annoying).  I love pattern matching, but the syntax kept tripping me up throughout.  It seemed every line I wrote a line of code was a compile error.  I didn’t find enough good documentation out on the web, and examples were limited to Stack Overflow.  I went through the tutorial on the OcaML website and tried the web REPL, but things still weren’t clicking for me.  Also, I seemed to get a lot of arguments wrong, and the OcaML compiler didn’t give me great errors.

So, complaining aside, the challenge was interesting.  There were a slew of robots roaming around on a floor all holding numbered microchips.  The input was a list of instructions for robots receiving a microchip or the instructions for what a robot should do if it has two microchips (either giving them to other robots or giving them to an output bin)

The instructions look like this :

value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2

Part 1

So, apologies if there are better ways of doing OcaML.  I would not hold this up as OcaML idiomatic code with what I wrote.


open Core.Std
type initial = {bot: string; value: int; }
type give_instruction = {bot: string; low: string; low_type: string; high: string; high_type: string; }
type command = Initial of initial | GiveInstruction of give_instruction

type overflow_instruction = Giver of give_instruction | None
type robot = {value: int; overflow: overflow_instruction; responsible: bool}


module StringMap = Map.Make(String)


let deref_list_string l n = 
   match List.nth l n with
    | None -> "0"
    | Some str -> str

let deref_list l n = int_of_string (deref_list_string l n)

let process_initial str = (Initial {bot=(deref_list_string str 5); value=(deref_list str 1)})
let process_give_instruction str = (GiveInstruction {bot=(deref_list_string str 1); low_type=(deref_list_string str 5); low=(deref_list_string str 6); high=(deref_list_string str 11); high_type=(deref_list_string str 10)})

let make_command str = 
     let l = String.split str ~on: ' ' in
     match List.hd l with
        None -> (Initial {bot=""; value=0;})
        | Some s -> if String.equal s "value" then process_initial l else process_give_instruction l

let rec give_bot_chip number v bots =
match StringMap.find bots number with
  | Some {value; overflow; responsible;} -> 
     if value == 0 then 
       StringMap.add ~key:number ~data:{value=v; overflow=overflow; responsible=responsible;} bots
     else
       match overflow with
        (Giver {bot; low; low_type; high; high_type;}) ->
        let l,h = if v  bots

and send_to dest num t bots =
   if String.equal t "output" then
    bots
   else
    give_bot_chip dest num bots

let update_instruction number low high low_type high_type bots =
    StringMap.add ~key:number ~data:{value=0; overflow=(Giver {bot=number;low=low;high=high;low_type=low_type;high_type=high_type;}); responsible=false} bots

let process_command bots command = 
    match command with
     | Initial {bot; value} -> give_bot_chip bot value bots
     | GiveInstruction {bot; low; low_type; high; high_type;} -> update_instruction bot low high low_type high_type bots

let compare_instruction_cast inst =
    match inst with
    | Initial { bot; value; } -> 1
    | GiveInstruction { bot; low; high; _; } -> 0

let compare_instruction in1 in2 = 
    compare (compare_instruction_cast in1) (compare_instruction_cast in2)

let is_responsible {value; overflow; responsible;} = responsible

let () =
   let file_to_read = "../day10.txt" in 
    let lines = In_channel.read_lines file_to_read in
    let commands = List.map ~f: make_command lines in
    let sorted_commands = List.stable_sort compare_instruction commands in
    let bots = List.fold_left ~f: process_command  ~init: StringMap.empty sorted_commands in
    let filtered_bots = StringMap.filter ~f:(fun ~key:k ~data:v -> is_responsible v) bots in
    StringMap.iter ~f:(fun ~key:k ~data:v -> print_endline ("The correct bot is "^k)) filtered_bots

So like previous problems, I’ll start with the main data transformations:


let () =
   let file_to_read = "../day10.txt" in 
    let lines = In_channel.read_lines file_to_read in
    let commands = List.map ~f: make_command lines in
    let sorted_commands = List.stable_sort compare_instruction commands in
    let bots = List.fold_left ~f: process_command  ~init: StringMap.empty sorted_commands in
    let filtered_bots = StringMap.filter ~f:(fun ~key:k ~data:v -> is_responsible v) bots in
    StringMap.iter ~f:(fun ~key:k ~data:v -> print_endline ("The correct bot is "^k)) filtered_bots

Read a file’s lines, map them to the Command datatype, sort them so that the “Give” instruction comes first, and then process each command by folding it into a map that stores bot state.  Then filter the bot that was responsible for the numbers we care about.

Transforming the strings to commands wasn’t too bad.  It took me a while to figure out how to deal with custom data types and construtors for them.


let deref_list_string l n = 
   match List.nth l n with
    | None -> "0"
    | Some str -> str

let deref_list l n = int_of_string (deref_list_string l n)

let process_initial str = (Initial {bot=(deref_list_string str 5); value=(deref_list str 1)})
let process_give_instruction str = (GiveInstruction {bot=(deref_list_string str 1); low_type=(deref_list_string str 5); low=(deref_list_string str 6); high=(deref_list_string str 11); high_type=(deref_list_string str 10)})

let make_command str = 
     let l = String.split str ~on: ' ' in
     match List.hd l with
        None -> (Initial {bot=""; value=0;})
        | Some s -> if String.equal s "value" then process_initial l else process_give_instruction l

Sorting it wasn’t too bad either.  I had to write a custom sort function, but it wasn’t too bad.


let compare_instruction_cast inst =
    match inst with
    | Initial { bot; value; } -> 1
    | GiveInstruction { bot; low; high; _; } -> 0

let compare_instruction in1 in2 = 
    compare (compare_instruction_cast in1) (compare_instruction_cast in2)

Now that I have a sorted list of commands, I have to process them.  I am passing a map of bots around, mapping the name of each bot to the robots.

Updating the instructions of how to give what is easy, as I can assume this is the first entry into the map (given how I sorted the data).


let update_instruction number low high low_type high_type bots =
    StringMap.add ~key:number ~data:{value=0; overflow=(Giver {bot=number;low=low;high=high;low_type=low_type;high_type=high_type;}); responsible=false} bots

The tricky part was dealing with sending a value to a bot.  If the bot didn’t have a value (indicated by 0), it was a simple overwrite of the bot with the new value.

But if it did already have a value, it had to figure out high vs low, and then hand out the bots accordingly.  I used mutual recursion to figure this out, and let each “give_bot_chip” call “give_bot_chip” to its low destination and high destination so that it would just slowly recurse through the bots.


let rec give_bot_chip number v bots =
match StringMap.find bots number with
  | Some {value; overflow; responsible;} -> 
     if value == 0 then 
       StringMap.add ~key:number ~data:{value=v; overflow=overflow; responsible=responsible;} bots
     else
       match overflow with
        (Giver {bot; low; low_type; high; high_type;}) ->
        let l,h = if v  bots

and send_to dest num t bots =
   if String.equal t "output" then
    bots
   else
    give_bot_chip dest num bots

Part 2

I breathed out a sigh of relief when I saw part 2.  I was struggling with OcaML for a while now, and this was an easy modification.  Track what chips go to which output bins and multiply the numbers in bin 0, bin 1 and bin 2.

First, I just overloaded my map to keep track of bins.


and send_to dest num t bots =
   if String.equal t "output" then
     StringMap.add ~key:("output"^dest) ~data:{value=num; overflow=None; responsible=false} bots
   else
    give_bot_chip dest num bots

Then I just had to update the main data transformation to extract information from the map


let get_output_bin n bots=
    match StringMap.find bots ("output"^(string_of_int n)) with
    | Some {value; overflow; responsible;} -> value
    | None -> 1

let get_answer bots = 
    (get_output_bin 0 bots) * (get_output_bin 1 bots) * (get_output_bin 2 bots)

let () =
   let file_to_read = "../day10.txt" in 
    let lines = In_channel.read_lines file_to_read in
    let commands = List.map ~f: make_command lines in
    let sorted_commands = List.stable_sort compare_instruction commands in
    let bots = List.fold_left ~f: process_command  ~init: StringMap.empty sorted_commands in
    print_endline (string_of_int (get_answer bots))

Wrap-up

With this and Factor back to back, this was rough.  I got the solutions right first time I submitted them, but the code was a slog, it’s not pretty, and while I feel I learned something, I wouldn’t want to point to this code as a good example of too many things.

I give myself another C-.  I was ready to give up in the middle, but I got through it.  I feel like OcaML probably is a great language if you are familiar to the ML family of languages already, but I had a hard time coming in as a newbie to that style.  Thank god for Elixir and Haskell to get me used to some of these ideas before I really dove into OcaML.

Next up, I think I’m going to go back to the Java ecosystem, and try out Groovy.

Advent of Code 2016 Day 9 (Factor)

~ patviafore ~ 12 Comments

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 9

Start: 12/11/2016

Finish 12/11/2016

Language: Factor

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

Hoo boy.   This was a rough one.  It wasn’t too bad of a sounding problem (dealing with string expansion in compress/decompress encodings), but I chose Factor today.  I understand the idea of a stack-oriented concatenative language, and writing in it definitely makes you appreciate a stack.  I think these type of languages offer a great insight into how powerful composability is, but if you are sloppy in them, it will come back to haunt you.

So as I said, we were expanding strings.  There were (AxB) strings littered through the code, and they indicated how much a string should be expanded.  For instance(4×2)ABCD should transform into ABCDABCD (the following four characters repeated twice).

I started out with a few false starts.  First I wanted to write a state-machine, but that went nowhere.  Then I started trying to do a whole lot of regular expressions, and that didn’t help either (I can’t figure out how capture groups work in Factor).  So after two deletes of the file that I was writing (both the best and worst feeling in the world), here’s what I came up with (It’s a doozy and I’m not proud of it)


USE: accessors
USE: io
USE: io.encodings.utf8
USE: io.files
USE: kernel
USE: math
USE: math.parser
USE: pairs
USE: prettyprint
USE: regexp
USE: sequences
USE: splitting
USE: strings


IN: challenge1

: get-match ( str -- match ) R/ \((\d+)x(\d+)\)/ first-match ;
: extract-first-number ( str -- x ) dup R/ \d+x/ first-match [ from>> ] [ to>> 1 - ] bi pick subseq nip string>number ;
: extract-second-number ( str -- x ) dup R/ x\d+/ first-match [ from>> 1 + ] [ to>> ] bi pick subseq nip string>number ;
: extract-numbers ( str -- sel rep ) [ extract-first-number ] [ extract-second-number ] bi ;

: split-on-match ( match -- a b c match ) [ [ 0 ] 
                                    [ from>> ] 
                                    [ seq>> ] 
                                    tri subseq ] 
                                  [ [ from>> ] 
                                    [ to>> ] 
                                    [ seq>> ] 
                                    tri subseq extract-numbers * 48  ] 
                                  [ [ [ to>> ]
                                      [   
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers  drop ]
                                      bi 
                                       + ] 
                                    [ seq>> length ] 
                                    [ seq>> ] 
                                    tri subseq  ] 
                                 tri  ;
: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;
: read-file ( file-path encoding -- file-contents ) file-contents ;

"../day9.txt" utf8 read-file decompress dup . length .

First let’s talk about the regex handling.  Given the string, I wanted a way to grab the regular expression that matched (AxB) where A and B were numbers, and then have ways to get those two numbers out if I needed them.


: get-match ( str -- match ) R/ \((\d+)x(\d+)\)/ first-match ;
: extract-first-number ( str -- x ) dup R/ \d+x/ first-match [ from>> ] [ to>> 1 - ] bi pick subseq nip string>number ;
: extract-second-number ( str -- x ) dup R/ x\d+/ first-match [ from>> 1 + ] [ to>> ] bi pick subseq nip string>number ;
: extract-numbers ( str -- sel rep ) [ extract-first-number ] [ extract-second-number ] bi ;

Like I said not pretty, but wait for the behemoth that is coming up next.

I wrote a decompress function, that takes in a string, splits it into it’s three parts (before the (AxB), the (AxB) and A characters after the (AxB).  I took the AxB and replaced it with A*B instances of the 0 character



: split-on-match ( match -- a b c match ) [ [ 0 ] 
                                    [ from>> ] 
                                    [ seq>> ] 
                                    tri subseq ] 
                                  [ [ from>> ] 
                                    [ to>> ] 
                                    [ seq>> ] 
                                    tri subseq extract-numbers * 48  ] 
                                  [ [ [ to>> ]
                                      [   
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers  drop ]
                                      bi 
                                       + ] 
                                    [ seq>> length ] 
                                    [ seq>> ] 
                                    tri subseq  ] 
                                 tri  ;
: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;

For the A characters after the AxB, I recursed into decompress so that I could handle more than one decompression.

I then joined the strings back up and took their length.


: decompress ( str -- str ) dup get-match dup f eq? [ drop ] [ nip split-on-match decompress append append nip ] if ;

 

Part 2.

So now, we had to do recursive expansion inside any expanded text.  I stared at my computer a good long time trying to figure out how to mess with my ugly Factor code (the language isn’t ugly, it has a simple beauty to it like LISP does, but when I write, it sure is ugly).  Well I ended up making it uglier.

I changed decompress to return a length instead of the entire string:


: decompress ( str -- len ) dup get-match dup f eq? [ drop length ] [ nip split-on-match decompress dup fixnum? [  ] [ length ] if + + nip ] if ;

and I also changed how I handled the (AxB) expansion.  Instead of filling in with a set number of zeros, I had to grab the actual text, decompress it, and then multiply it by the B in (AxB).


                           [ ! length of the matched segment - b
                                    [ 
                                       ! selection number
                                       [ from>> ] 
                                       [ to>> ] 
                                       [ seq>> ] 
                                       tri subseq extract-numbers nip 
                                    ]
                                    
                                    [  ! repetition number
                                        [ from>> ] 
                                        [ to>> ] 
                                        [ seq>> ] 
                                        tri subseq extract-numbers drop 
                                    ] 
                                    [ ! everything after the (AxB) (up to x characters)
                                      [ to>> ]
                                      [ [ to>> ]
                                        [ [ from>> ] 
                                          [ to>> ] 
                                          [ seq>> ] 
                                          tri subseq extract-numbers drop  
                                        ]
                                        bi
                                        + 
                                      ] 
                                      [ seq>> ] 
                                      tri subseq  
                                    ]
                                    ! decompress the sequence
                                     tri decompress nip  * 
                                  ]

 

Wrap-up

I’m sorry.  I really am.  This code was bad.  It wasn’t Factor’s fault.  I didn’t extract enough things out to functions, I didn’t plan out my stack calls with care.  I ended up having to do a lot of swapping, duping, and dropping to massage the stack in a way that was coherent.   I feel like there is elegant Factor that can be written for this problem (prove me right, Internet), but with this being my first Factor solution ever, I’m happy that this just worked.

The problem was a real fun problem, and I feel like I squandered some time doing it in a language that challenged me.  But that’s the point of this.  To challenge me, and I’m glad I did some Factor.  I’m just hoping that when I roll around to Forth, I write a bit better code.

Overall grade: C-.  I had to delete code a whole lot, and just scrolling through, I say it’s ugly.  I got the answers on the first try of submit each time, so that’s something, but I’m not proud of the code.

Tomorrow, I’m going to tackle Day 10 with OcaML.  Another new language.   Should be interesting :).

 

 

Advent of Code 2016 Day 8 (c++)

~ patviafore ~ 13 Comments

Previous:

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 8

Start: 12/9/2016

Finish 12/9/2016

Language: C++

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 has been my favorite challenge so far.  So I decided to dip a bit into my wheelhouse with C++, and see if I could complete Day 8. I’m a little worried about using languages I know (C++, Javascript and Python) so early, as all I have left that I’m truly comfortable with is Elixir.

Anyway, this challenge was all about manipulating pixels to be on or off on a screen.  You could turn all the pixels in a rectangle on (starting at upper left corner), or you could rotate the pixels to the right on a row (overflowing to the beginning of the rote), or rotate a column of pixels down (with overflow going to the top of the column).

Let’s take a look at the (rather verbose) C++ code


#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <iterator>
#include <ostream>
#include <numeric>
#include <regex>
#include <sstream>
#include <string>
#include<<vector>

class Pixel
{
public:
    bool on;
    friend std::ostream& operator<<( std::ostream& stream, const Pixel &p);
};

std::ostream& operator<<(std::ostream & stream, const Pixel & p)
{
    stream << (p.on ? "*" : ".");
    return stream;
}

class Panel
{  
public:
    typedef std::vector Row;
    typedef std::vector Rows;
   
    Panel(uint8_t width, uint8_t height);
    void rect(uint8_t width, uint8_t height);
    void rotateColumn(uint8_t columnNumber, uint8_t num);
    std::vector getColumn(uint8_t columnNumber) const;
    void applyColumn(uint8_t columnNumber, std::vector column);

    void rotateRow(uint8_t rowNumber, uint8_t num);
    uint16_t getNumberOfPixelsLit() const;
    

    friend std::ostream& operator<<(std::ostream& stream, Panel panel);

private:
    Row makeRow(uint8_t width);
    
    Rows rows;

};

Panel::Panel(uint8_t width, uint8_t height) :
        rows(height, makeRow(width))
{
}

Panel::Row Panel::makeRow(uint8_t width)
{
    return Panel::Row(width, Pixel{false});
}

std::ostream& operator<<(std::ostream& stream, Panel panel)
{
    std::for_each(panel.rows.begin(), panel.rows.end(), [&stream](Panel::Row & row){
        std::copy(row.begin(), row.end(), std::ostream_iterator(stream));
        stream <<"\n";
    });
    return stream;
}

void Panel::rect(uint8_t width, uint8_t height)
{
    auto turnOnPixel = [](Pixel & p){p.on = true;};
    auto turnOnRowPixel = [turnOnPixel, width](Row & row){ 
        std::for_each(row.begin(), row.begin() + width, turnOnPixel);
    };
    std::for_each(rows.begin(), rows.begin() + height, turnOnRowPixel);
}

void Panel::rotateColumn(uint8_t columnNumber, uint8_t num)
{
    std::vector column = getColumn(columnNumber);
    std::rotate(column.rbegin(), column.rbegin()+num, column.rend() );
    applyColumn(columnNumber, column);
}

void Panel::rotateRow(uint8_t rowNumber, uint8_t num)
{
    auto& row = rows[rowNumber];
    std::rotate(row.rbegin(), row.rbegin()+num, row.rend());
}
    

std::vector Panel::getColumn(uint8_t columnNumber) const
{
    std::vector pixels;
    auto getPixel = [columnNumber](const Row & row){
        return row[columnNumber];
    };
    std::transform(rows.begin(), rows.end(), std::inserter(pixels, pixels.begin()), getPixel);
    return pixels;
}

void Panel::applyColumn(uint8_t columnNumber, std::vector column)
{
    uint8_t index = 0;
    std::for_each(rows.begin(), rows.end(), [&index, columnNumber, &column](Row &row){
        row[columnNumber] = column[index++];
    });
}

uint16_t Panel::getNumberOfPixelsLit() const
{
    auto isOn = [](const Pixel & p) { return p.on;};
    auto getCount = [isOn](const Row & row){ return std::count_if(row.begin(), row.end(), isOn);};
    std::vector counts;
    std::transform(rows.begin(), rows.end(), std::inserter(counts, counts.begin()), getCount);
    return std::accumulate(counts.begin(), counts.end(), 0);
}

void applyRectOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex regex("rect (\\d+)x(\\d+)");
    std::regex_match(operation, sm, regex);
    if (sm.size() == 3)
    {
        panel.rect(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyRotateRowOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex regex("rotate row y=(\\d+) by (\\d+)");
    std::regex_match(operation, sm, regex);
    if (sm.size() == 3)
    {
        panel.rotateRow(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyRotateColumnOperationIfMatching(Panel & panel, std::string operation)
{
    std::smatch sm;
    std::regex rotateColumnRegex("rotate column x=(\\d+) by (\\d+)");
    std::regex_match(operation, sm, rotateColumnRegex);
    if (sm.size() == 3)
    {
        panel.rotateColumn(stoi(sm[1]), stoi(sm[2]));
    }
}

void applyOperationOnPanel(Panel & panel, std::string op)
{
    applyRectOperationIfMatching(panel, op);
    applyRotateRowOperationIfMatching(panel, op);
    applyRotateColumnOperationIfMatching(panel, op);
}

int main()
{
    Panel panel(50,6);
    std::ifstream infile; 
    infile.open("../day8.txt");
    std::string data;
    while(getline(infile, data))
    {
        applyOperationOnPanel(panel, data);
    }
    infile.close();;
    std::cout << panel << "\n" << panel.getNumberOfPixelsLit() << "\n";
}

Whew, that’s a lot.  First I created a Pixel class.  I could have just kept it a bool, but vector has weird behaviors in C++, so I didn’t want to run into anything strange.


class Pixel
{
public:
    bool on;
    friend std::ostream& operator<<( std::ostream& stream, const Pixel &p);
};

std::ostream& operator<<(std::ostream & stream, const Pixel & p)
{
    stream << (p.on ? "*" : ".");
    return stream;
}

 

Then I compose a panel, which has a member variable Rows (which is just a vector of type Row, which is a vector of Pixels.)  This gives me my 2-dimensional array of pixels, and I just had to define functions to operate on them.

Here’s the class declaration in entirety:


class Panel
{  
public:
    typedef std::vector Row;
    typedef std::vector Rows;
   
    Panel(uint8_t width, uint8_t height);
    void rect(uint8_t width, uint8_t height);
    void rotateColumn(uint8_t columnNumber, uint8_t num);
    std::vector getColumn(uint8_t columnNumber) const;
    void applyColumn(uint8_t columnNumber, std::vector column);

    void rotateRow(uint8_t rowNumber, uint8_t num);
    uint16_t getNumberOfPixelsLit() const;
    

    friend std::ostream& operator<<(std::ostream& stream, Panel panel);

private:
    Row makeRow(uint8_t width);
    
    Rows rows;

};

First up is rect:


void Panel::rect(uint8_t width, uint8_t height)
{
    auto turnOnPixel = [](Pixel & p){p.on = true;};
    auto turnOnRowPixel = [turnOnPixel, width](Row & row){ 
        std::for_each(row.begin(), row.begin() + width, turnOnPixel);
    };
    std::for_each(rows.begin(), rows.begin() + height, turnOnRowPixel);
}

Just a nested for each loop to turn on things.

Then I wrote how to rotate a row (thank god for the algorithm library)

 


void Panel::rotateRow(uint8_t rowNumber, uint8_t num)
{
    auto& row = rows[rowNumber];
    std::rotate(row.rbegin(), row.rbegin()+num, row.rend());
}

 

Then I had to write rotate Column, which was a bit tricker


void Panel::rotateColumn(uint8_t columnNumber, uint8_t num)
{
    std::vector column = getColumn(columnNumber);
    std::rotate(column.rbegin(), column.rbegin()+num, column.rend() );
    applyColumn(columnNumber, column);
}

I get the column of pixels as a vector, rotate it, and then re-apply it back to the pixels. HEre’s the get and apply functions. I created a temp vectors of pixels and got the entire column for the get function, and then I apply the column back in through a similar method.



std::vector Panel::getColumn(uint8_t columnNumber) const
{
    std::vector pixels;
    auto getPixel = [columnNumber](const Row & row){
        return row[columnNumber];
    };
    std::transform(rows.begin(), rows.end(), std::inserter(pixels, pixels.begin()), getPixel);
    return pixels;
}

void Panel::applyColumn(uint8_t columnNumber, std::vector column)
{
    uint8_t index = 0;
    std::for_each(rows.begin(), rows.end(), [&index, columnNumber, &column](Row &row){
        row[columnNumber] = column[index++];
    });
}

 

FInally, I have to get the number of pixels lit:



uint16_t Panel::getNumberOfPixelsLit() const
{
    auto isOn = [](const Pixel & p) { return p.on;};
    auto getCount = [isOn](const Row & row){ return std::count_if(row.begin(), row.end(), isOn);};
    std::vector counts;
    std::transform(rows.begin(), rows.end(), std::inserter(counts, counts.begin()), getCount);
    return std::accumulate(counts.begin(), counts.end(), 0);
}

 

Part 2

Part two was so easy, I didn’t have to change any code.  Luckily, I was printing the screen for debugging, and that’s all the puzzle required.  So, no code for day 2.

 

Wrap-up

I liked this problem and I liked the solution.  I was happy with using the algorithm library to try and do as little for loops as I could.  It was also the first time I used regex in C++, and I was happy to see that it wasn’t as obtuse as expected (looking at you, lambda expressions).

I grade myself a solid A on this one.  I got the first problem right on the first try, and it worked for the second problem too.  I tried to use C++’s type system well throughout, and it actually caught some bugs for me.

Next up, I’m going to try the stack-oriented language, Factor, for day 9.

 

Advent of Code 2016 Day 7 (Javascript)

~ patviafore ~ 14 Comments

Previous:

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 7

Start: 12/7/2016

Finish 12/8/2016

Language: Javascript

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 time around, the goal was to take strings that were  sequences of characters, with some enclosed in square brackets, like so: ioxxoj[asdfgh]zxcvbn.

With those strings, we had to find ones where an ABBA pattern existed outside of the square bracketed enclosed sequence (it could be any two letters, not just A and B, but they had to be different).  It also could not have an ABBA sequence insidde the square bracket enclosed sequence.

I figured out I could use Javascript and regexes for this one, especially after learning about backreferences to solve http://jimbly.github.io/regex-crossword/.  Let’s look at the code:


const fs = require('fs')

function hasABBA(str){
    return str.match(/(\S)((?!\1).)\2\1/);
}

function splitOutSections(str){
    return str.split(/\[.*?\]/)
}

function getHypertext(str){
    return str.match(/\[(.*?)\]/g)
}

function isValid(str){
    return splitOutSections(str).some(hasABBA) &&
           getHypertext(str).every((str) => !hasABBA(str));

}

lines = fs.readFileSync("../day7.txt", "utf8").split("\n");
console.log(lines.filter(isValid).length);

This is pretty short.  I had a misstep with the regex, but a negative lookahead assertion helped me out.


function hasABBA(str){
    return str.match(/(\S)((?!\1).)\2\1/);
}

Then it was simple to split out what was in square brackets (Called “hypertext” in our example):


function isValid(str){
    return splitOutSections(str).some(hasABBA) &&
           getHypertext(str).every((str) => !hasABBA(str));

}

 

And that was really it to it.

 

 

Part 2

So now, the goal was to find an ABA sequence outside of the hypertext with a BAB in the hypertext.  I thought I could use a regular expression as well, but I could not get it to match a string like ABACA to match.  Instead, I had to write a normal for loop to do it.  (I even messed this up because I forgot about some of the global variable scoping in Javascript).

Let’s look at what was needed :


function isABA(substring) {
   
    return substring[0] === substring[2] && substring[1] !== substring[0]
}
function getABA(str){
    var abas = []
    for(let i = 0; i < str.length; i++){
        const substring = str.substring(i, i+3);
        if (substring.length == 3 && isABA(substring)) {
            abas.push(substring);
        } 
    }
    return abas;
}

I also had to change out the isValid function to check these.  Here, I get each section, get the ABA’s out of them, take out any empty strings and reduce the ABA sections to one list.  Then its a simple check to see if any of the ABA sequences are represented in BAB sections



function flip(str){
    return str[1] + str[0] + str[1];
}

function isValid(str){
    var abas = splitOutSections(str).map(getABA)
                                .filter((x) => {return x;})
                                .reduce((a,b) => { return a.concat(b)}, []);
    var babs = getHypertext(str).map(getABA)
                            .filter((x) => {return x;})
                            .reduce((a,b) => { return a.concat(b)}, []);

    return abas.some((aba) => {return babs.includes(flip(aba));});
}

 

Wrap-up

I had quite a few missteps in here.  I understood the Javascript part, but the Regexes fooled me a bit, and I should have really tested against the known input.  Overall I give myself a B-.  I did the first half great, but the second one had stupid mistakes in them, and I took too long to do it.

Next up, I’m going to use C++ to work on Day 8. Let’s hope it goes a lot better than this time around.

 

Advent of Code Day 6 (Julia)

~ patviafore ~ 15 Comments

Previous:

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 6

Start: 12/7/2016

Finish 12/7/2016

Language: Julia

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 take a stab at Julia this time around.  I was doing some column based reading of text, and I thought Julia’s arrays on steroids might give me something.

I was happy with how nicely this fit together, let’s take a look:


function getHighestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple), rev=true)[1]
end

f = open("../day6.txt")
    lines = readlines(f)
    chars = map(s -> split(strip(s), ""), lines)
    reshaped = hcat(chars...)
    columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))
    answer = *(map(c -> c[1], columns)...)
    println(answer)
close(f)

That’s it, 16 lines of code.

Main processing part is straight-forward again (once you know Julia syntax).


f = open("../day6.txt")
    lines = readlines(f)
    chars = map(s -> split(strip(s), ""), lines)
    reshaped = hcat(chars...)
    columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))
    answer = *(map(c -> c[1], columns)...)
    println(answer)
close(f)

First we read the lines in, then map a split over them so we get a whole bunch of char arrays.  With 624, 8 byte arrays, I decided to hcat the values, so that I ended up with a 624×8 array of characters.  Then, using Julia’s n-dimensional array slicing, I did this


columns = map(x -> getHighestCount(reshaped[x,:]), 1:length(reshaped[:,1]))

We’ll take a look at getHighestCount in a bit, but for now, just know that it retrieves the letter of the most frequency.  So in essence, we are getting the highest frequency of a column of the original text.

Then we map over the returned tuples and use the * to concatenate all of them together


*(map(c -> c[1], columns)...)

Looking at getHighestCount, it was simply a dictionary that tracked frequency, and then sorted by the values in reverse order.


function getHighestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple), rev=true)[1]
end

And that was it.

 

Part 2

This part was almost laughably easy.  I turned getHighestCount into a getLowestCount, and removed the rev=true argument in the sort.  That’s it.  All there was.  It is great when all you have to do to gain functionality is delete code.


function getLowestCount(chars)
    dict = Dict()
    for char in chars
       dict[char] = get(dict, char, 0) + 1
    end
    return sort(collect(dict), by= tuple -> last(tuple))[1]
end

 

Wrap-up

I’m not going to pretend I understand a lot of Julia’s n-dimensional mathematics, but I can definitely recognize how it would be a boon in numerical computing.  At first, I wished there was a few more things in the standard library (I spent a lot of time looking for group_by, chunk_by, frequency counts, and so on) but in the end, I couldn’t find them (they may have very well been there), and it led me to what I think was a very Julian solution.

I grade myself as an A on this one.  I solved this in about an hour and a half, and that included skimming back through 7 more languages in 7 weeks to refresh myself on Julia.

Next up, it looks like Regex will help me out again, so I’m going to take a stab in ECMAScript 2016+/Javascript.

 

Advent of Code 2016 – Day 5( Java 8)

~ patviafore ~ 16 Comments

Previous:

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 5

Start: 12/7/2016

Finish 12/7/2016

Language: Java 8

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 really haven’t touched Java since my first job.  So, I saw a challenge that involved MD5, thought to the Java library that I remember using way back when, and decided to polish up some skills.  I wanted to dig into Java 8 since the introduction of lambda expressions and streams, but haven’t had a reason to.

So this time around, I had to MD5 a combination of a key and ever-incrementing numbers until I found 8 hashes that had a special property (started with 5 zeroes when converted to a string).   Then we had to grab the sixth character of those hashes and that forms our password. So this sounded perfect for an infinite stream.  Let’s take a look at the full code before I dive in.  (It’s a bit more verbose than others, but hey, it’s Java.)


import java.security.MessageDigest;
import java.util.stream.IntStream;
class Challenge1 
{
    static String doorId = "ffykfhsq";

    final protected static char[] hexArray = "0123456789ABCDEF".toCharArray();
    public static String bytesToHex(byte[] bytes) 
    {
        char[] hexChars = new char[bytes.length * 2];
        for ( int j = 0; j >> 4];
            hexChars[j * 2 + 1] = hexArray[v & 0x0F];
        }
        return new String(hexChars);
    }

    public static String md5(int index)
    {
        try
        {
            MessageDigest md = MessageDigest.getInstance("MD5");
            String str = doorId+new Integer(index).toString();
            byte[] digest = md.digest(str.getBytes("UTF-8"));
            return new String(Challenge1.bytesToHex(digest)); 
        }
        catch(Exception e)
        {
            return "";
        }
    }

    public static boolean isAGoodHash(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.startsWith("00000");
    }

    public static int getKey(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.charAt(5);
    }

    public static void main(String[] args)
    {
        
        IntStream.iterate(0, i-> i+1)
                 .filter(Challenge1::isAGoodHash)
                 .limit(8)
                 .map(Challenge1::getKey)
                 .forEach(i -> System.out.print((char)i));
        System.out.println();
    }
}

The main part is pretty self explanatory.  Start with an infinite sequence 1,2,3……., filter out anything that isn’t a good hash, take the first 8 and grab the keys, finally printing them all out.

 


    public static boolean isAGoodHash(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.startsWith("00000");
    }

    public static int getKey(int index)
    {
        String hash = Challenge1.md5(index);
        return hash.charAt(5);
    }

    public static void main(String[] args)
    {
        
        IntStream.iterate(0, i-> i+1)
                 .filter(Challenge1::isAGoodHash)
                 .limit(8)
                 .map(Challenge1::getKey)
                 .forEach(i -> System.out.print((char)i));
        System.out.println();
    }

The MD5 code was able to heavily borrow off of java.security.MessageDigest to create the MD5


    public static String md5(int index)
    {
        try
        {
            MessageDigest md = MessageDigest.getInstance("MD5");
            String str = doorId+new Integer(index).toString();
            byte[] digest = md.digest(str.getBytes("UTF-8"));
            return new String(Challenge1.bytesToHex(digest)); 
        }
        catch(Exception e)
        {
            return "";
        }
    }

 

Finally, I took some code off the internet to convert a byte string to hex (I’d written this so, so many times before in Java that I didn’t feel like writing it once again.


    final protected static char[] hexArray = "0123456789ABCDEF".toCharArray();
    public static String bytesToHex(byte[] bytes) 
    {
        char[] hexChars = new char[bytes.length * 2];
        for ( int j = 0; j >> 4];
            hexChars[j * 2 + 1] = hexArray[v & 0x0F];
        }
        return new String(hexChars);
    }

And that was it!  That was all the code it took.  I really like how expressive streams are in languages that support that type of composability.  It reminds me of Clojure’s pipeline in Day 3, and I’m sure we’ll see it again in Elixir and Elm.

 

Part 2

Here was a kicker for the FP enthusiast in me.  It wasn’t enough to just grab the first 8 hashes anymore.  The fifth character in each hash was now the position of the final character in the password, and the sixth character was the character itself.  Any hash that didn’t have a position 0-7 should have been ignored, and only the first time the position is seen should we update the key.

I updated the isAGoodHash to at least check position 0-7


   public static boolean isAGoodHash(String hash)
    {
        return hash.startsWith("00000") && isValidPosition(hash.charAt(5));
    }

This means I have to track state through iteration.  I took a very precursory glance through Java docs to try and figure out if there was a way to use reduce or collect to stop iteration  when I the password was filled out, but wasn’t finding anything.  (I’m sure there’s something, I just didn’t have anything at the time.)

So, rather than try to make pure FP and bend the rules, I put in an explicit for loop to indicate that I’m mutating state.


 public static void main(String[] args)
    {
        
        Iterator it = IntStream.iterate(0, i-> i+1)
                                .mapToObj(Challenge2::md5)
                                .filter(Challenge2::isAGoodHash)
                                .iterator();
        List keys =  Arrays.asList('-', '-','-','-','-','-','-','-');
        while (it.hasNext())
        {
            String s = it.next();
            char pos = (char)(s.charAt(5) - 48);
            char c = s.charAt(6);
            if(keys.get(pos) == '-')
            {
                keys.set(pos,  c);
            }
            if(!keys.contains('-'))
            {
                break;
            }
        }

        keys.stream().forEach(c -> System.out.print(c));
        System.out.println();
    }

I found mapToObj this time around, which let me convert them to a String right away rather than dealing with ints the whole way through.

 

Wrap-up

I liked using Streams and Lambda Expressions in Java 8.  It definitely cuts down on some of the verbosity that plagued Java programs of the past.  However, it still had it’s limits, and Java as a whole felt fairly verbose to me.

I give this exercise of mine an A-.  I was able to use what I wanted, learned some new things, and got the problems right on my first try.  Next up, I’m going to take a stab at a numerical computing language, Julia.

 

Advent of Code 2016 – Day 4 (Perl)

~ patviafore ~ 17 Comments

Previous:

Advent of Code 216 – Day 3

Advent of Code – Day 2

Advent Of Code 2016 – Day 1

Day 4

Start: 12/5/2016

Finish 12/6/2016

Language: Perl

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 day, the goal was to try and figure out which rooms out of a list were valid by matching up a checksum with their most frequent characters.  I really liked this idea.  What I didn’t like was the fact that I chose Perl for this.  I had never written Perl before in my life.  And I never want to ever again either.
Continue reading →

Advent of Code – Day 2

~ patviafore ~ 19 Comments

Previous:

Advent Of Code 2016 – Day 1

Day 2

Start: 12/4/2016

Finish 12/4/2016

Language: Python3

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:

 

Problem Statement

The problem started off simple enough.  There is a 9 digit keypad listed:

123
456
789

 

If you start at the 5 key, and are given directions to move up, down, right or left, multiple times, what are the keys that you end at after each iteration of directions?

Not too bad, and I was picking a language in my wheelhouse, Python.  I chose Python 3, since I don’t get much experience with it, but unfortunately, this program did not stretch my knowledge of Python 3.  There wasn’t enough meat to the problem to really dive in.

So let’s look at the code:
Continue reading →