From d520f8941d8fb63e70d19ea5bbc9246641ef7593 Mon Sep 17 00:00:00 2001 From: Brian Chu Date: Mon, 14 Feb 2022 14:47:31 -0800 Subject: solutions up to day 9 --- day6.ml | 41 +++++++++++++++++++++++++++++ day7.ml | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day8.fsx | 60 +++++++++++++++++++++++++++++++++++++++++++ day9.fsx | 25 ++++++++++++++++++ 4 files changed, 216 insertions(+) create mode 100644 day6.ml create mode 100644 day7.ml create mode 100644 day8.fsx create mode 100644 day9.fsx diff --git a/day6.ml b/day6.ml new file mode 100644 index 0000000..10d5e63 --- /dev/null +++ b/day6.ml @@ -0,0 +1,41 @@ +#use "topfind";; +#thread;; +#require "core";; +#require "stdio";; + +open Core +open Stdio + +let memory = In_channel.read_all "day6.txt" + |> String.strip |> String.split ~on:'\t' + |> Array.of_list |> Array.map ~f:int_of_string + +let len = Array.length memory +let seen = Caml.Hashtbl.create 5000 + +let array_max xs = + let f index (maxInd, maxVal) value = + if value > maxVal then (index, value) else (maxInd, maxVal) in + Array.foldi ~init:(0, 0) ~f:f xs + +let rec redist xs n i = + match n with + | 0 -> () + | _ -> + let pos = (i + 1) mod len in + xs.(pos) <- xs.(pos) + 1; + redist xs (n-1) pos + +let rec cycle count banks = + match Caml.Hashtbl.find_opt seen banks with + | Some x -> + Printf.printf "%d\n" count; + Printf.printf "%d\n" (count - x) + | None -> + Caml.Hashtbl.add seen (Array.copy banks) count; + let mi, mv = array_max banks in + banks.(mi) <- 0; + redist banks mv mi; + cycle (count+1) banks + +let () = cycle 0 memory diff --git a/day7.ml b/day7.ml new file mode 100644 index 0000000..498d732 --- /dev/null +++ b/day7.ml @@ -0,0 +1,90 @@ +#use "topfind";; +#require "containers";; +#load "str.cma";; + +module StrMap = Map.Make(String) +module StrSet = Set.Make(String) +module IntSet = Set.Make(Int) +module Regex = Str + +let r = Regex.regexp {|\([a-z]+\) (\([0-9]+\))\($\| -> \(.+\)\)|} + +let parse_row s = + if Regex.string_match r s 0 then + let name = Regex.matched_group 1 s in + let weight = Regex.matched_group 2 s |> int_of_string in + let kids = + if Regex.matched_group 3 s = "" then [] + else CCString.split ~by:", " (Regex.matched_group 4 s) + in + (name, weight, kids) + else ("", 0, []) + +let input = List.map parse_row CCIO.(with_in "day7.txt" read_lines_l) + +let create_map f = + List.fold_left f StrMap.empty +let get_weights = + create_map (fun a (n, w, _) -> StrMap.add n w a) +let get_relations = + create_map (fun a (n, _, k) -> StrMap.add n k a) + +let weights = get_weights input +let relations = get_relations input + + +let rec total_node_weight node = + let own_weight = StrMap.find node weights in + let kids = StrMap.find node relations in + let kids_weights = List.map total_node_weight kids in + own_weight + List.fold_left (+) 0 kids_weights + + +let find_different_weights kids = + if CCList.is_empty kids then None + else + let kids_weights = List.map total_node_weight kids in + let w_set = IntSet.of_list kids_weights in + if IntSet.cardinal w_set = 1 then None + else + let min_w = IntSet.min_elt w_set in + let max_w = IntSet.max_elt w_set in + let count v = + kids_weights + |> List.filter (fun w -> w = v) + |> List.length in + let min_count = count min_w in + let max_count = count max_w in + let (wrong_w, right_w) = + if min_count < max_count then (min_w, max_w) else (max_w, min_w) in + let wrong_i, _ = + CCList.find_idx (fun x -> x = wrong_w) kids_weights + |> Option.value ~default:(0, 0) in + let wrong_kid = List.nth kids wrong_i in + Some (wrong_kid, right_w) + + +let rec find_correct_weight node right_w = + let kids = StrMap.find node relations in + match find_different_weights kids with + | Some (wrong_kid, right_w) -> + find_correct_weight wrong_kid right_w + | None -> + let kids_weights = List.map total_node_weight kids in + let kids_total_w = List.fold_left (+) 0 kids_weights in + right_w - kids_total_w + + +let create_set f = + List.fold_left f StrSet.empty +let get_nodes = + create_set (fun a (n, _, _) -> StrSet.add n a) +let get_kids = + create_set (fun a (_, _, k) -> StrSet.union a (StrSet.of_list k)) + +let nodes = get_nodes input +let kids = get_kids input +let root = StrSet.diff nodes kids |> StrSet.choose + +let part_1 = root |> Printf.printf "%s\n" +let part_2 = find_correct_weight root 0 |> Printf.printf "%d\n" diff --git a/day8.fsx b/day8.fsx new file mode 100644 index 0000000..5a4f423 --- /dev/null +++ b/day8.fsx @@ -0,0 +1,60 @@ +open System.IO +open System.Text.RegularExpressions +open System.Collections.Generic + +let (|InstRegex|_|) input = + let m = Regex.Match(input, "(\w+) (dec|inc) (-?\d+) if (\w+) (>|<|>=|<=|==|!=) (-?\d+)") + if m.Success then + let op = if m.Groups[2].Value = "dec" then (-) else (+) + let comparator: int->int->bool = + match m.Groups[5].Value with + | ">" -> (>) + | "<" -> (<) + | ">=" -> (>=) + | "<=" -> (<=) + | "==" -> (=) + | "!=" -> (<>) + | _ -> (fun x y -> false) + Some((m.Groups[1].Value, op, int m.Groups[3].Value, m.Groups[4].Value, comparator, int m.Groups[6].Value)) + else None + +type Instruction = + struct + val opReg: string + val opFun: int -> int -> int + val opVal: int + val compReg: string + val compFun: int -> int -> bool + val compVal: int + new(inst: string) = + match inst with + | InstRegex (target, operator, value, compared, comparator, compValue) -> + { + opReg = target; + opFun = operator; + opVal = value; + compReg = compared; + compFun = comparator; + compVal = compValue + } + | _ -> {opReg = ""; opFun = (+); opVal = 0; compReg = ""; compFun = (>); compVal = 0} + end + +let registers = new Dictionary() +let mutable maxValue = 0 +let executeInstruction (inst: Instruction) = + let mutable regVal = 0 + registers.TryGetValue(inst.compReg, ®Val) |> ignore + if inst.compFun regVal inst.compVal then + registers.TryGetValue(inst.opReg, ®Val) |> ignore + registers[inst.opReg] <- inst.opFun regVal inst.opVal + if registers[inst.opReg] > maxValue then + maxValue <- registers[inst.opReg] + else () + else () + +File.ReadAllLines "day8.txt" |> Array.map (fun x -> new Instruction(x)) |> Array.iter executeInstruction +// part 1 +registers.Values |> Seq.max |> printfn "%A" +// part 2 +printfn "%d" maxValue \ No newline at end of file diff --git a/day9.fsx b/day9.fsx new file mode 100644 index 0000000..61cba2a --- /dev/null +++ b/day9.fsx @@ -0,0 +1,25 @@ +open System.IO +open System.Text.RegularExpressions + +let input = (File.ReadAllText "day9.txt").Trim() +let exclRegex = new Regex("!.") +let garbageRegex = new Regex("<.*?>") + +let part1 input = + let stripped = garbageRegex.Replace(exclRegex.Replace(input, ""), "") |> String.filter (fun x -> x <> ',') + let rec sumLevels input level acc = + if input = "" then acc else + + if input[0] = '{' then + sumLevels input[1..] (level + 1) (acc + level) + else + sumLevels input[1..] (level - 1) acc + + sumLevels stripped 1 0|> printfn "%A" + +let part2 input = + let stripped = exclRegex.Replace(input, "") + garbageRegex.Matches(stripped) |> Seq.map (fun x -> x.Groups[0].Value.Length - 2) |> Seq.sum |> printfn "%d" + +part1 input +part2 input \ No newline at end of file -- cgit 1.4.1-2-gfad0