Last active
June 30, 2018 13:52
-
-
Save taiju/13e860cf2e85608d6c2b144b69b5d714 to your computer and use it in GitHub Desktop.
This file contains 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 characters
(* | |
行列のできるラーメン屋 ESM オフラインどう書くの問題を OCaml で解いてみたやつ | |
記事: http://mtsmfm.github.io/2015/10/22/esm-doukaku.html | |
問題: https://gist.github.com/mtsmfm/4b8ffb53ffac055f5843 | |
*) | |
open Core | |
type state_t = Empty | Waiting | Eating | Resting | |
let seats = [(1, Empty); (2, Empty); (3, Empty); (4, Empty); (5, Empty); (6, Empty); (7, Empty); (8, Empty)] | |
let cycle seats = List.append (List.drop seats 1) (List.take seats 1) | |
let get_number = fst | |
let is_empty = function (_, Empty) -> true | _ -> false | |
let to_int_list num_str = String.to_list num_str |> List.map ~f:Char.get_digit_exn | |
let to_bin = function (_, Empty) -> 0 | _ -> 1 | |
let succ = function | |
| (n, Empty) -> (n, Empty) | |
| (n, Waiting) -> (n, Eating) | |
| (n, Eating) -> (n, Resting) | |
| (n, Resting) -> (n, Empty) | |
let rec rotate n seats = | |
let seats = List.map ~f:succ seats in | |
let rec loop n seats = | |
let parts = List.take seats n in | |
if (List.for_all ~f:is_empty parts) then | |
List.drop seats n |> | |
List.append (List.map ~f:(fun s -> ((get_number s), Waiting)) parts) |> | |
List.sort ~cmp:(fun x y -> get_number x - get_number y) | |
else | |
if (List.hd_exn parts |> get_number = 8) then | |
rotate n (cycle seats) | |
else | |
loop n (cycle seats) | |
in | |
loop n seats | |
let solve input = | |
to_int_list input |> | |
List.fold_left ~init:seats ~f:(Fn.flip rotate) |> | |
List.map ~f:to_bin |> | |
List.map ~f:Int.to_string |> | |
String.concat | |
let test input output = | |
assert (solve input = output) | |
let () = | |
test "3316" "11111110";; | |
test "3342153" "11111111";; | |
test "8" "11111111";; | |
test "232624" "11110110";; | |
test "1" "10000000";; | |
test "224673432" "11111000";; | |
test "123464334" "11111110";; | |
test "44372332" "11111111";; | |
test "2344" "11111111";; | |
test "6448476233" "11111100";; | |
test "4345174644" "11111111";; | |
test "77743" "11111110";; | |
test "2136524281" "10000000";; | |
test "344373" "11100000";; | |
test "434226" "11111111";; | |
test "7433223" "11111110";; | |
test "2246534" "11110111";; | |
test "634" "11111110";; | |
test "2222" "11111100";; | |
test "2442343238" "11111111";; | |
test "7243344" "11111111";; | |
test "26147234" "10111111";; | |
test "34424" "10011111";; | |
test "6334" "11011111";; | |
test "3828342" "11011110";; | |
test "4431" "11110000";; | |
test "2843212125" "11111111";; | |
test "333336482" "11000000";; | |
test "374" "11110000";; | |
test "4382333" "11100111";; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment