Reason Dojo

390.re

let partition_by_identity = xs => {
  let rec impl = (xs, cur) => {
    switch (xs, cur) {
    | ([], _) => [cur]
    | ([x, ...xs], []) => impl(xs, [x])
    | ([x, ...xs], [y, ..._]) =>
      if (x == y) {
        impl(xs, [x, ...cur]);
      } else {
        [cur, ...impl(xs, [x])];
      }
    };
  };
  impl(xs, []);
};

let factor_to_string = ((factor, power)) => {
  {j|$factor^$power|j};
};

let factors_to_string = factors => {
  let v = List.reduce(factors, 1, ( * ));

  string_of_int(v)
  ++ " = "
  ++ partition_by_identity(factors)
     ->List.map(l => (List.headExn(l), List.length(l)))
     ->List.map(factor_to_string)
     ->String.concat(" x ", _);
};


factors_to_string([2, 2, 2, 3])->Js.log;

Day01.re

let input = Node_fs.readFileSync("input/day01.in", `utf8);

let list_of_digits = input =>
  Js.String.castToArrayLike(input)
  ->Js.Array.fromMap(int_of_string)
  ->List.fromArray;

let rotate = (xs, step) =>
  List.concat(xs, xs)
  ->List.drop(step)
  ->Option.flatMap(List.take(_, List.length(xs)))
  ->Option.getWithDefault([]);

let captcha = (xs, ys) =>
  List.zip(xs, ys)
  ->List.map(((x, y)) => x == y ? x : 0)
  ->List.reduce(0, (+));

let part1 = {
  let xs = list_of_digits(input);
  let ys = rotate(xs, 1)
  captcha(xs, ys)->Js.log
}

let part2 = {
  let xs = list_of_digits(input);
  let ys = rotate(xs, List.length(xs) / 2)
  captcha(xs, ys)->Js.log
}

Day02.re

let input = {
  let lines =
    Node_fs.readFileAsUtf8Sync("input/day02.in")
    ->Js.String2.trim
    ->Js.String2.split("\n");
  let parseInts = line =>
    line->Js.String2.split("\t")->Array.map(int_of_string);

  lines->Array.map(parseInts);
};

let part1 = () => {
  Array.(
    input
    ->map(row => reduce(row, min_int, max) - reduce(row, max_int, min))
    ->reduce(0, (+))
  );
};

let part2 = () => {
  let intQuot = (xs, x) =>
    xs
    ->List.getBy(y => x mod y == 0 || y mod x == 0)
    ->Option.map(d => max(d, x) / min(d, x));

  let rec division = xs =>
    switch (xs) {
    | [] => 0
    | [x, ...ys] =>
      switch (intQuot(ys, x)) {
      | None => division(ys)
      | Some(q) => q
      }
    };

  input
  ->Array.map(xs => division(List.fromArray(xs)))
  ->Array.reduce(0, (+));
};

part1()->Js.log;
part2()->Js.log;

Day03.re

open Belt;

[@bs.module "./util"] external gets: string => Js.Promise.t(string) = "gets";

let solve = (cheatSheet, n) => {
  let lines = cheatSheet->String.trim->String.split_on_char('\n', _);

  lines
  //->MyList.takeExn(100) // further lines will cause integer parsing error
  ->List.keepMap(l => {
      switch (String.split_on_char(' ', l)) {
      | [_, num] => int_of_string_opt(num)
      | _ => None
      }
    })
  ->List.getBy(x => x > n);
};

let part2 = () => {
  let n = 312051;

  gets("https://oeis.org/A141481/b141481.txt")
  |> Js.Promise.then_(value => {
       let answer = solve(value, n);
       answer->Js.log;

       Js.Promise.resolve(answer);
     })
  |> Js.Promise.catch(e => {
       Js.log(e);
       Js.Promise.resolve(None);
     });
};

part2();

Day05.re

open Belt;

module Maze = {
  type t = {
    offsets: array(int),
    pos: int,
  };

  let make = offsets => {
    {offsets: Array.copy(offsets), pos: 0};
  };

  let step = (offsetFn, {offsets, pos}) => {
    let o = Array.getUnsafe(offsets, pos);
    Array.setUnsafe(offsets, pos, offsetFn(o));
    {offsets, pos: pos + o};
  };

  let isOutOfRange = ({offsets, pos}) => {
    pos < 0 || pos >= Array.length(offsets);
  };

  let run = (m, ~offsetFn=o => o + 1, ()): int => {
    let stepFn = step(offsetFn);
    let rec run' = (m, count) =>
      if (isOutOfRange(m)) {
        count;
      } else {
        stepFn(m)->run'(count + 1);
      };
    run'(m, 0);
  };
};

let input =
  Node_fs.readFileAsUtf8Sync("input/day05.in")
  ->Js.String2.trim
  ->Js.String2.split("\n")
  ->Array.map(int_of_string);
//let input = [|0, 3, 0, 1, (-3)|];

let part1 = () => {
  Maze.make(input)->Maze.run()->Js.log;
};

let part2 = () => {
  let offsetFn = o => o >= 3 ? o - 1 : o + 1;
  Maze.make(input)->Maze.run(~offsetFn, ())->Js.log;
};

part1();
part2();

Day06.re

open Belt;

let input =
  Node_fs.readFileAsUtf8Sync("input/day06.in")
  ->Js.String2.trim
  ->Js.String2.split("\t")
  ->Array.map(Pervasives.int_of_string);

let distributeUnsafe = banks => {
  let i = Garter.Array.maxIndex(banks);
  let length = Array.length(banks);
  let blocks = Array.getUnsafe(banks, i);
  Array.setUnsafe(banks, i, 0);
  let rec f = (blocks, j) =>
    if (blocks > 0) {
      Garter.Array.updateUnsafe(banks, j, (+)(1));
      f(blocks - 1, (j + 1) mod length);
    } else {
      banks;
    };
  f(blocks, (i + 1) mod length);
};

// [|0, 2, 7, 0|]->distributeUnsafe->Js.log; // => (2, 4)

module IntArrayCmp =
  Id.MakeComparable({
    type t = array(int);
    let cmp = Pervasives.compare;
  });

let findDupe = s => {
  let rec go = (history, idx) => {
    let v = Stream.next(s);
    switch (history->Map.get(v)) {
    | None => go(history->Map.set(v, idx), idx + 1)
    | Some(prevIdx) => Some((prevIdx, idx))
    };
  };

  go(Map.make(~id=(module IntArrayCmp)), 0);
};

// [[|0|], [|2|], [|3|], [|1|], [|3|], [|4|]]
// ->Stream.of_list
// ->findDupe
// ->Js.log;

let bankStream = init => {
  let state = ref(init);
  let next = _ => {
    let state' = Array.copy(state^);
    state := distributeUnsafe(state^);
    Some(state');
  };
  Stream.from(next);
};

// bankStream([|0, 2, 7, 0|])->Stream.npeek(10, _)->List.toArray->Js.log;

let (from, to_) = bankStream(input)->findDupe->Option.getExn;

Js.log(to_);
Js.log(to_ - from);


/**
 * Stream은 SICP의 스트림이 아니라 Java 스트림에 가까움! (뮤터블)
 * Stream에 들어가는 데이터 역시 Mutable Array다 보니까 주의가 필요합니다. npeek 결과가 모두 동일해버리는 실수라던가...
 * Map은 항상 Make를 해서 사용해야 하는데, 매번 펑터에 들어갈 모듈을 만드는게 번거로워요.
 */

Day07.re

open Belt;

module Program = {
  type t =
    | Internal(string, int)
    | External(string, int, array(string));

  let fromString = s => {
    let headBody = Js.String2.split(s, " -> ");

    // pares head

    let head = Array.getUnsafe(headBody, 0);
    let (name, weight) = {
      let r = [%re "/(\w+) \((\d+)\)/"]->Js.Re.exec_(head)->Option.getExn;
      let matches = Js.Re.captures(r)->Array.map(Js.Nullable.toOption);
      (
        Js.Array2.unsafe_get(matches, 1)->Option.getExn,
        Js.Array2.unsafe_get(matches, 2)->Option.getExn->int_of_string,
      );
    };

    switch (headBody[1]) {
    | None => Internal(name, weight)
    | Some(body) =>
      let children = Js.String2.split(body, ", ");
      External(name, weight, children);
    };
  };
};

let programs =
  Node_fs.readFileAsUtf8Sync("input/day07.in")
  ->Js.String2.trim
  ->Js.String2.split("\n")
  ->Array.map(Program.fromString);

/** Map<child, parent> */
let buildParentMap = programs => {
  programs->Array.reduce(Map.String.empty, (m, p) => {
    switch (p) {
    | Program.Internal(_) => m
    | Program.External(parent, _, children) =>
      children->Array.reduce(m, (m, child) =>
        Map.String.set(m, child, parent)
      )
    }
  });
};

let rec findRoot = (tree, node) => {
  switch (Map.String.get(tree, node)) {
  | None => node
  | Some(parent) => findRoot(tree, parent)
  };
};

let part1 = () => {
  buildParentMap(programs)->findRoot("llyhqfe")->Js.log;
};

Day08.re

open Belt;

module Instruction = {
  type t = {
    reg: string,
    v: int,
    condReg: string,
    condOp: (int, int) => bool,
    condV: int,
  };

  let fromString = s => {
    let ar = Js.String2.split(s, " ");

    let parseOp = o =>
      switch (o) {
      | "<" => (<)
      | ">" => (>)
      | "<=" => (<=)
      | ">=" => (>=)
      | "==" => (==)
      | "!=" => (!=)
      | _ => raise(Not_found)
      };

    let sign = Array.getUnsafe(ar, 1) == "inc" ? 1 : (-1);

    {
      reg: Array.getUnsafe(ar, 0),
      v: Array.getUnsafe(ar, 2)->int_of_string * sign,
      condReg: Array.getUnsafe(ar, 4),
      condOp: parseOp(Array.getUnsafe(ar, 5)),
      condV: Array.getUnsafe(ar, 6)->int_of_string,
    };
  };
};

module Cpu = {
  type t = {registers: Map.String.t(int)};

  let make = () => {registers: Map.String.empty};

  let get = (cpu, reg) => cpu.registers->Map.String.getWithDefault(reg, 0);
  let acc = (cpu, reg, v) => {
    registers:
      cpu.registers
      ->Map.String.update(reg, prev => {
          switch (prev) {
          | None => Some(v)
          | Some(u) => Some(u + v)
          }
        }),
  };

  let exec = (cpu, inst: Instruction.t) => {
    let lhs = get(cpu, inst.condReg);
    if (inst.condOp(lhs, inst.condV)) {
      acc(cpu, inst.reg, inst.v);
    } else {
      cpu;
    };
  };

  let getMaximum = cpu =>
    Map.String.valuesToArray(cpu.registers)->Js.Math.maxMany_int;
};

let input = Node_fs.readFileAsUtf8Sync("input/day08.in");
let insts = input->Js.String2.split("\n")->Array.map(Instruction.fromString);

let part1 = () => {
  Array.reduce(insts, Cpu.make(), Cpu.exec)->Cpu.getMaximum->Js.log;
};

let part2 = () => {
  let rec findHighest = (cpu, insts) => {
    switch (insts) {
    | [] => Cpu.getMaximum(cpu)
    | [inst, ...insts] =>
      max(Cpu.getMaximum(cpu), findHighest(Cpu.exec(cpu, inst), insts))
    };
  };

  findHighest(Cpu.make(), List.fromArray(insts))->Js.log;
};

part1();
part2();

Day10.re

open Belt;

module KnotHash = {
  type t = array(int);

  let reverseSub = (ar, offset, limit) => {
    let n = Array.length(ar);
    let swapIndices = (i, j) => {
      let x = Array.getUnsafe(ar, i);
      let y = Array.getUnsafe(ar, j);
      Array.setUnsafe(ar, i, y);
      Array.setUnsafe(ar, j, x);
    };

    Range.forEach(0, limit / 2 - 1, i =>
      swapIndices((offset + i) mod n, (offset + limit - i - 1) mod n)
    );
    ar;
  };

  let make = (knotSize, seq) => {
    let knot = Array.range(0, knotSize - 1);

    let rec pinch = (knot, seq, offset, skipSize) => {
      switch (seq) {
      | [] => knot
      | [x, ...xs] =>
        reverseSub(knot, offset, x)
        ->pinch(xs, (offset + x + skipSize) mod knotSize, skipSize + 1)
      };
    };

    pinch(knot, seq, 0, 0);
  };

  let makeSparse = input => {
    let postamble = [|17, 31, 73, 47, 23|];
    let pattern = Js.Array2.concat(input, postamble);

    let round = 64;
    let seq =
      Array.range(0, round - 1)
      ->Array.reduce([||], (acc, _) => Array.concat(acc, pattern));

    make(256, List.fromArray(seq));
  };

  let makeDense = knot => {
    let blocks =
      Array.range(0, 15)
      ->Array.map(i => {
          let offset = i * 16;
          Array.slice(knot, ~offset, ~len=16);
        });

    let xor = Array.reduce(_, 0, (lxor));

    Array.map(blocks, xor);
  };
};

let input = Node.Fs.readFileAsUtf8Sync("input/day09.in");

let part1 = () => {
  let seq =
    input->Js.String2.split(",")->Array.map(int_of_string)->List.fromArray;
  let knot = KnotHash.make(256, seq);
  Js.log(Array.getUnsafe(knot, 0) * Array.getUnsafe(knot, 1));
};

let part2 = () => {
  let toAscii = s =>
    Js.String2.castToArrayLike(s)
    ->Js.Array2.from
    ->Js.Array2.map(c => int_of_float(Js.String2.charCodeAt(c, 0)));

  let fromAscii = s => {
    let toHex = d => {
      let h = Js.Int.toStringWithRadix(d, ~radix=16);
      d < 16 ? "0" ++ h : h;
    };
    s->Array.map(toHex)->Js.String2.concatMany("", _);
  };

  input->toAscii->KnotHash.makeSparse->KnotHash.makeDense->fromAscii->Js.log;
};

part1();
part2();

Day11.re

open Belt;

module HexGrid = {
  /**
   * Axial coordinate
   * x + y + z = 0
   */
  type t = {
    x: int,
    y: int,
  };

  type dirs =
    | NW
    | N
    | NE
    | SW
    | S
    | SE;

  let origin = {x: 0, y: 0};

  let move = ({x, y}, dir) => {
    switch (dir) {
    | NW => {x, y: y + 1}
    | N => {x: x + 1, y: y + 1}
    | NE => {x: x + 1, y}
    | SW => {x: x - 1, y}
    | S => {x: x - 1, y: y - 1}
    | SE => {x, y: y - 1}
    };
  };

  let rec moveMany = (pos, moves) => {
    switch (moves) {
    | [] => pos
    | [m, ...moves] => move(pos, m)->moveMany(moves)
    };
  };

  let distanceFromOrigin = ({x, y}) => {
    let z = x - y;
    Js.Math.(abs_int(x) + abs_int(y) + abs_int(z)) / 2;
  };
};

let parse = text => {
  HexGrid.(
    text
    ->Js.String2.trim
    ->Js.String2.split(",")
    ->Array.map(x =>
        switch (x) {
        | "nw" => NW
        | "n" => N
        | "ne" => NE
        | "sw" => SW
        | "s" => S
        | "se" => SE
        | _ => raise(Not_found)
        }
      )
  );
};

let part1 = input => {
  let moves = parse(input)->List.fromArray;
  HexGrid.origin->HexGrid.moveMany(moves)->HexGrid.distanceFromOrigin;
};

assert(part1("ne,ne,ne") == 3);
assert(part1("ne,ne,sw,sw") == 0);
assert(part1("ne,ne,s,s") == 2);
assert(part1("se,sw,se,sw,sw") == 3);

let input = Node.Fs.readFileAsUtf8Sync("input/day11.in");
part1(input)->Js.log;

let part2 = input => {
  let moves = parse(input);

  Garter.Array.scan(moves, HexGrid.origin, HexGrid.move)
  ->Array.map(HexGrid.distanceFromOrigin)
  ->Js.Math.maxMany_int;
};

part2(input)->Js.log;

Day12.re

let input = "0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5";
let input = Node_fs.readFileAsUtf8Sync("input/day12.in");

let parse = s => {
  let%Opt res = [%re "/(\\d+) <-> (.*)/"]->Js.Re.exec_(s);
  let matches = Js.Re.captures(res)->Belt.Array.map(Js.Nullable.toOption);
  let%Opt lhs = matches[1];
  let%Opt rhs = matches[2];

  let neighbors = rhs->Js.String2.split(", ")->Belt.Array.map(int_of_string);

  Some((int_of_string(lhs), neighbors));
};

module Graph = {
  module V = Belt.Set.Int;
  module E = Belt.Map.Int;

  type vertices = V.t;
  type edges = E.t(array(int));

  let fromInput = (input): edges => {
    input
    ->Js.String2.trim
    ->Js.String2.split("\n")
    ->Belt.Array.keepMap(parse)
    ->E.fromArray;
  };

  let nodes = E.keysToArray;

  let dfs = (edges, startNode): vertices => {
    let rec visit = (curNode, visited: vertices) => {
      // Js.log(curNode);
      let neighbors = E.getExn(edges, curNode);
      neighbors->Belt.Array.reduce(
        V.add(visited, curNode), (visited, nextNode) => {
        V.has(visited, nextNode) ? visited : visit(nextNode, visited)
      });
    };

    visit(startNode, V.empty);
  };

  let groups = (edges): list(vertices) => {
    let rec visitAll = (unvisited: vertices): list(vertices) => {
      switch (unvisited->V.toList) {
      | [] => []
      | [u, ..._] =>
        let visited = dfs(edges, u);
        [visited, ...visitAll(unvisited->V.removeMany(visited->V.toArray))];
      };
    };

    let unvisited = edges->nodes->V.fromArray;
    visitAll(unvisited);
  };
};

let part1 = () => {
  Graph.fromInput(input)->Graph.dfs(0)->Graph.V.size->Js.log;
};

let part2 = () => {
  Graph.fromInput(input)->Graph.groups->Belt.List.size->Js.log;
};

part1();
part2();

Day13.re

open Belt;

module Walls = {
  type t = Map.Int.t(int);

  let fromString = text => {
    let parse = s => {
      let kv = s->Js.String2.split(": ")->Array.map(int_of_string);
      (Array.getUnsafe(kv, 0), Array.getUnsafe(kv, 1));
    };

    text
    ->Js.String2.trim
    ->Js.String2.split("\n")
    ->Array.map(parse)
    ->Map.Int.fromArray;
  };

  let severity = w => {
    w
    ->Map.Int.keep((k, v) => {
        let period = (v - 1) * 2;
        k mod period == 0;
      })
    ->Map.Int.reduce(0, (acc, k, v) => acc + k * v);
  };

  let wasCaught = (w, ~delay) => {
    w->Map.Int.some((k, v) => {
      let period = (v - 1) * 2;
      (k + delay) mod period == 0;
    });
  };
};

let input = Node.Fs.readFileAsUtf8Sync("input/day13.in");
let w = Walls.fromString(input);

let part1 = () => Walls.severity(w)->Js.log;

let part2 = () => {
  let rec firstUncaughtDelay = delay => {
    Walls.wasCaught(w, ~delay) ? firstUncaughtDelay(delay + 1) : delay;
  };
  firstUncaughtDelay(0)->Js.log;
};

part1();
part2();

Day15.re

module type Factor = {let factor: int;};

module Generator = {
  module Make = (F: Factor) => {
    type t = {n: Int64.t};
    let factor = F.factor->Int64.of_int;
    let m = 2147483647->Int64.of_int;

    let make = n0 => {
      {n: n0->Int64.of_int};
    };

    let next = g => {
      {n: g.n->Int64.mul(factor)->Int64.rem(m)};
    };

    let nextMultiple = (g, multiple) => {
      let m = multiple->Int64.of_int;
      let rec f = g => {
        Int64.equal(g.n->Int64.rem(m), Int64.zero) ? g : f(next(g));
      };
      f(next(g));
    };

    let lowest = g => {
      g.n->Int64.to_int land (1 lsl 16 - 1);
    };
  };
};

let bits = n => {
  (n lsr 0)->Js.Int.toStringWithRadix(~radix=2);
};

module GenA =
  Generator.Make({
    let factor = 16807;
  });
module GenB =
  Generator.Make({
    let factor = 48271;
  });

let part1 = () => {
  let rec findMatch = (gA, gB, count, found) => {
    if (count mod 1000000 == 0) {
      Js.log(count);
    };

    if (count > 40000000) {
      found;
    } else {
      let found' = GenA.lowest(gA) == GenB.lowest(gB) ? found + 1 : found;
      findMatch(GenA.next(gA), GenB.next(gB), count + 1, found');
    };
  };

  //assert(findMatch(GenA.make(65), GenB.make(8921), 0, 0) == 588);

  findMatch(GenA.make(618), GenB.make(814), 0, 0)->Js.log;
};

let part2 = () => {
  let rec findMatch = (gA, gB, count, found) => {
    if (count mod 1000000 == 0) {
      Js.log(count);
    };

    if (count > 5000000) {
      found;
    } else {
      let found' = GenA.lowest(gA) == GenB.lowest(gB) ? found + 1 : found;
      findMatch(
        GenA.nextMultiple(gA, 4),
        GenB.nextMultiple(gB, 8),
        count + 1,
        found',
      );
    };
  };

  //assert(findMatch(GenA.make(65), GenB.make(8921), 0, 0) == 309);

  findMatch(GenA.make(618), GenB.make(814), 0, 0)->Js.log;
};

part1();
part2();

Day17.re

open Belt

let step = 371

module SpinLock = {
  type t = {
    buffer: array<int>,
    pos: int,
  }

  let make = () => {
    buffer: [0],
    pos: 0,
  }

  let spin = ({buffer, pos}) => {
    let sz = Array.size(buffer)
    let step = mod(step, sz)
    let pos = mod(pos + step, sz)

    let buffer =
      Array.slice(buffer, ~offset=0, ~len=pos + 1)
      ->Array.concat([sz])
      ->Array.concat(Array.sliceToEnd(buffer, pos + 1))

    {buffer: buffer, pos: pos + 1}
  }

  let rec spinWithCount = (t, count) => {
    if mod(count, 100000) == 0 {
      Js.log(count)
    }
    count == 0 ? t : spinWithCount(spin(t), count - 1)
  }

  let identify = ({buffer, pos}) => {
    let sz = Array.size(buffer)
    Array.getUnsafe(buffer, mod(pos + 1, sz))
  }
}

let part1 = () =>
  SpinLock.make()->SpinLock.spinWithCount(2017)->SpinLock.identify->Js.log

let rec part2 = (~size, ~pos, ~identified) =>
  switch size {
  | 50000000 => identified
  | _ =>
    let step = mod(step, size)
    let pos = mod(pos + step, size)

    let identified = pos == 0 ? size : identified
    part2(~size=size + 1, ~pos=pos + 1, ~identified)
  }

part2(~size=1, ~pos=0, ~identified=-1)->Js.log

Garter.re

module List = {
  include Belt.List;

  let takeExn = (list, cnt) => {
    switch (Belt.List.take(list, cnt)) {
    | Some(l) => l
    | None => raise(Not_found)
    };
  };

  let dropExn = (list, cnt) => {
    switch (Belt.List.drop(list, cnt)) {
    | Some(l) => l
    | None => raise(Not_found)
    };
  };
};

module Array = {
  let scan = (xs, init, f) => {
    open Belt.Array;
    let ar = makeUninitializedUnsafe(length(xs));
    let cur = ref(init);
    Belt.Array.forEachWithIndex(
      xs,
      (idx, x) => {
        cur := f(cur^, x);
        setUnsafe(ar, idx, cur^);
      },
    );
    ar;
  };

  /** Returns (max_value, index). Array may not be empty. */
  let maxIndex = xs => {
    let init = (Belt.Array.getUnsafe(xs, 0), 0);
    Belt.Array.reduceWithIndex(
      xs,
      init,
      (acc, v, idx) => {
        let (curMax, curIdx) = acc;
        compare(v, curMax) > 0 ? (v, idx) : (curMax, curIdx);
      },
    )
    ->snd;
  };

  let updateUnsafe = (ar, i, f) => {
    let v = Belt.Array.getUnsafe(ar, i);
    Belt.Array.setUnsafe(ar, i, f(v));
  };

  include Belt.Array;
};