Last active
April 20, 2022 16:32
-
-
Save mununki/3b656a9228c0bd9ffc8d2c38695e98fe to your computer and use it in GitHub Desktop.
Revisions
-
mununki revised this gist
Apr 20, 2022 . 1 changed file with 6 additions and 5 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -49,10 +49,11 @@ module QuadTree = { 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)) } @@ -64,7 +65,7 @@ module QuadTree = { let calculateBlack = t => { let rec calculateBlackAux = (t, pixels, sum) => { switch t { | Empty | White => 0 | Black => pixels | P(ne, nw, sw, se) => -
Apr 20, 2022 . 1 changed file with 2 additions and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -18,11 +18,12 @@ module QuadTree = { 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 } -
Apr 20, 2022 . 1 changed file with 23 additions and 80 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -3,14 +3,13 @@ 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" { @@ -19,87 +18,31 @@ module QuadTree = { Empty } let isFull = t => switch t { | White | Black | P(White | Black, White | Black, White | Black, White | Black) => 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) => { @@ -109,8 +52,8 @@ module QuadTree = { | (t1', White | Empty) => t1' | (Black, _) => Black | (White | Empty, t2') => t2' | (P(ne1, nw1, sw1, se1), P(ne2, nw2, sw2, se2)) => P(sumAux(ne1, ne2), sumAux(nw1, nw2), sumAux(sw1, sw2), sumAux(se1, se2)) } } @@ -123,7 +66,7 @@ module QuadTree = { | Empty => 0 | White => 0 | Black => pixels | P(ne, nw, sw, se) => calculateBlackAux(ne, pixels / 4, sum) + calculateBlackAux(nw, pixels / 4, sum) + calculateBlackAux(sw, pixels / 4, sum) + -
Apr 18, 2022 . No changes.There are no files selected for viewing
-
Apr 18, 2022 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,151 @@ open Belt module QuadTree = { exception Invalid_Operation(string) // P(ne, nw, sw, se) type rec t = P(t, t, t, t, full) | White | Black | Empty and full = bool let empty = () => Empty let fromString = s => if s == "p" { P(Empty, Empty, Empty, Empty, false) } else if s == "w" { White } else if s == "b" { Black } else { Empty } let fullify = t => { let rec fullifyAux = t => switch t { | P( (P(_, _, _, _, true) | White | Black) as ne, (P(_, _, _, _, true) | White | Black) as nw, (P(_, _, _, _, true) | White | Black) as sw, (P(_, _, _, _, true) | White | Black) as se, false, ) => P(ne, nw, sw, se, true) | White | Black | Empty => t | P(ne, nw, sw, se, full) => P(fullifyAux(ne), fullifyAux(nw), fullifyAux(sw), fullifyAux(se), full) } t->fullifyAux } let add = (t, node) => { let rec addAux = t => { switch t->fullify { | P(_, _, _, _, true) | White | Black | P( P(_, _, _, _, true) | White | Black, P(_, _, _, _, true) | White | Black, P(_, _, _, _, true) | White | Black, P(_, _, _, _, true) | White | Black, _, ) => raise(Invalid_Operation("Cann't add the node")) | Empty => node | P(P(_, _, _, _, false) as ne, nw, sw, se, false) => P(addAux(ne), nw, sw, se, false) | P(Empty, nw, sw, se, false) => P(node, nw, sw, se, false) | P((P(_, _, _, _, true) | White | Black) as ne, P(_, _, _, _, false) as nw, sw, se, false) => P(ne, addAux(nw), sw, se, false) | P((P(_, _, _, _, true) | White | Black) as ne, Empty, sw, se, false) => P(ne, node, sw, se, false) | P( (P(_, _, _, _, true) | White | Black) as ne, (P(_, _, _, _, true) | White | Black) as nw, P(_, _, _, _, false) as sw, se, false, ) => P(ne, nw, addAux(sw), se, false) | P( (P(_, _, _, _, true) | White | Black) as ne, (P(_, _, _, _, true) | White | Black) as nw, Empty, se, false, ) => P(ne, nw, node, se, false) | P( (P(_, _, _, _, true) | White | Black) as ne, (P(_, _, _, _, true) | White | Black) as nw, (P(_, _, _, _, true) | White | Black) as sw, P(_, _, _, _, false) as se, false, ) => P(ne, nw, sw, addAux(se), false) | P( (P(_, _, _, _, true) | White | Black) as ne, (P(_, _, _, _, true) | White | Black) as nw, (P(_, _, _, _, true) | White | Black) as sw, Empty, false, ) => P(ne, nw, sw, node, false) } } addAux(t)->fullify->fullify // FIXME 자식 노드를 fullify 한 뒤 자식 -> 부모 방향으로 체크 필요. } let sum: (t, t) => t = (t1, t2) => { let rec sumAux = (t1, t2) => { switch (t1, t2) { | (_, Black) => Black | (t1', White | Empty) => t1' | (Black, _) => Black | (White | Empty, t2') => t2' | (P(ne1, nw1, sw1, se1, full1), P(ne2, nw2, sw2, se2, full2)) => P(sumAux(ne1, ne2), sumAux(nw1, nw2), sumAux(sw1, sw2), sumAux(se1, se2), full1 || full2) } } sumAux(t1, t2) } let calculateBlack = t => { let rec calculateBlackAux = (t, pixels, sum) => { switch t { | Empty => 0 | 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 } This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,5 @@ // 더하기가 가능한 ADT로서의 쿼드트리(QuadTree)를 구현하고, // p, w, b 문자열을 읽어서 쿼드트리를 생성할 수 있어야 한다. // 더하는 규칙은 한쪽의 노드가 하나라도 black 인 경우 black let solution: (string, string) => int