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

Advertisements

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s