프로그래머스 코테 - 쿼드트리

quadTree.res

open Belt

module QuadTree = {
  exception Invalid_Operation(string)
  // P(ne, nw, sw, se)
  type rec t = P(t, t, t, t) | White | Black | Empty

  let empty = () => Empty

  let fromString = s =>
    if s == "p" {
      P(Empty, Empty, Empty, Empty)
    } else if s == "w" {
      White
    } else if s == "b" {
      Black
    } else {
      Empty
    }

  let rec isFull = t =>
    switch t {
    | White
    | Black
    | P(White | Black, White | Black, White | Black, White | Black) => true
    | P(ne, nw, sw, se) if isFull(ne) && isFull(nw) && isFull(sw) && isFull(se) => true
    | _ => false
    }

  let add = (t, node) => {
    let rec addAux = t => {
      switch t {
      | White | Black => raise(Invalid_Operation("Cann't add the node"))
      | Empty => node
      | P(ne, nw, sw, se) =>
        switch (ne->isFull, nw->isFull, sw->isFull, se->isFull) {
        | (false, _, _, _) => P(addAux(ne), nw, sw, se)
        | (true, false, _, _) => P(ne, addAux(nw), sw, se)
        | (true, true, false, _) => P(ne, nw, addAux(sw), se)
        | (true, true, true, false) => P(ne, nw, sw, addAux(se))
        | (true, true, true, true) => raise(Invalid_Operation("Cann't add the node"))
        }
      }
    }

    addAux(t)
  }

  let sum: (t, t) => t = (t1, t2) => {
    let rec sumAux = (t1, t2) => {
      switch (t1, t2) {
      | (_, Black)
      | (Black, _) =>
        Black
      | (t', White | Empty)
      | (White | Empty, t') => t'
      | (P(ne1, nw1, sw1, se1), P(ne2, nw2, sw2, se2)) =>
        P(sumAux(ne1, ne2), sumAux(nw1, nw2), sumAux(sw1, sw2), sumAux(se1, se2))
      }
    }

    sumAux(t1, t2)
  }

  let calculateBlack = t => {
    let rec calculateBlackAux = (t, pixels, sum) => {
      switch t {
      | Empty
      | White => 0
      | Black => pixels
      | P(ne, nw, sw, se) =>
        calculateBlackAux(ne, pixels / 4, sum) +
        calculateBlackAux(nw, pixels / 4, sum) +
        calculateBlackAux(sw, pixels / 4, sum) +
        calculateBlackAux(se, pixels / 4, sum)
      }
    }

    t->calculateBlackAux(1024, 0)
  }
}

let solution = (s1, s2) => {
  let s1 = s1->Js.String2.split("")->Array.map(QuadTree.fromString)
  let s2 = s2->Js.String2.split("")->Array.map(QuadTree.fromString)

  let empty1 = QuadTree.empty()
  let empty2 = QuadTree.empty()

  let qt1 = s1->Array.reduce(empty1, (qt, s) => qt->QuadTree.add(s))
  let qt2 = s2->Array.reduce(empty2, (qt, s) => qt->QuadTree.add(s))

  let qt = QuadTree.sum(qt1, qt2)

  qt->QuadTree.calculateBlack
}

quadTree.resi

// 더하기가 가능한 ADT로서의 쿼드트리(QuadTree)를 구현하고,
// p, w, b 문자열을 읽어서 쿼드트리를 생성할 수 있어야 한다.
// 더하는 규칙은 한쪽의 노드가 하나라도 black 인 경우 black

let solution: (string, string) => int