evan_tech

Previous Entry Share Next Entry
10:49 pm, 1 Dec 03

more ocaml, more to read

Tonight's project for better OCaml was Go Scoring. It's simplified by not needing to find dead stones, but it still was way too hard for me to solve. I saw how it would be solved pretty quickly, but I couldn't figure out the way to make it happen for a few hours. I wouldn't win any programming contests with that speed. :(


(* vim: set ts=2 sw=2 et : *)

type square = Unknown | NotYet | Black | White | Both

let name_from_square = function
  Unknown -> "Unknown" | NotYet -> "NotYet" | Black -> "Black"
| White -> "White" | Both -> "Both"

let read_board file =
  let board = Array.make_matrix 19 19 Unknown in
  for y = 0 to 18 do
    let line = input_line file in
    for x = 0 to 18 do
      let c = line.[x*2] in
      let newsquare = (match c with
                        '+' | '*' -> Unknown
                      | 'O' -> White
                      | '@' -> Black
                      | _ -> raise (Invalid_argument (Char.escaped c))) in
      board.(x).(y) <- newsquare;
    done;
  done;
  board
;;

let output_board board =
  for y = 0 to 18 do
    for x = 0 to 18 do
      let c = (match board.(x).(y) with
        Unknown -> "+"
      | Both -> "?"
      | White -> "O" | Black -> "@" | NotYet -> "#") in
      print_string (c ^ " ");
    done;
    print_newline ();
  done;
  print_newline ();
  ()
;;

let count (a,b,c,d) color =
  if a = color then 1 else 0 +
  if b = color then 1 else 0 +
  if c = color then 1 else 0 +
  if d = color then 1 else 0

let rec scan board x y =
  (*Printf.printf "scanning from %d %d\n" x y;
  output_board board;*)
  let s = board.(x).(y) in
  match s with
    Black | White | Both | NotYet -> s
  | Unknown ->
    board.(x).(y) <- NotYet;
    let l = if x > 0 then scan board (x-1) y else Unknown in
    let r = if y > 0 then scan board x (y-1) else Unknown in
    let u = if x < 18 then scan board (x+1) y else Unknown in
    let d = if y < 18 then scan board x (y+1) else Unknown in
    let both = count (l,r,u,d) Both in
    if both > 0 then Both
    else
      let white = count (l,r,u,d) White in
      let black = count (l,r,u,d) Black in
      if black > 0 && white = 0 then Black
      else if white > 0 && black = 0 then White
      else if white > 0 && black > 0 then Both
      else Unknown

let rec fill_area board x y s =
  match board.(x).(y) with
    Black | White | Both -> ()
  | Unknown | NotYet ->
    board.(x).(y) <- s;
    if x > 0 then fill_area board (x-1) y s;
    if y > 0 then fill_area board x (y-1) s;
    if x < 18 then fill_area board (x+1) y s;
    if y < 18 then fill_area board x (y+1) s;
    ()

let fixup_board board =
  for y = 0 to 18 do
    for x = 0 to 18 do
      if board.(x).(y) = Unknown then begin
        let s = scan board x y in
        fill_area board x y s;
      end;
    done;
  done;
  ()

let count_board board =
  let black = ref 0 and white = ref 0 in
  for y = 0 to 18 do
    for x = 0 to 18 do
      match board.(x).(y) with
        Black -> black := !black + 1
      | White -> white := !white + 1
      | _ -> ()
    done
  done;
  (!black, !white)
;;

let run_board file =
  try while true do
    let _ = input_line file in
    let board = read_board file in
    fixup_board board;
    let (black, white) = count_board board in
      Printf.printf "%d %d\n" black white
  done with End_of_file -> (); ()
;;

let file = open_in "input" in
  run_board file;
  run_board file


Er, and I need to fix that end to use a while loop and try..with on End_of_file, but I didn't save the file before I did the export. Whatever.


I realized I can search my history for "pdf" to find the URLs for stuff I've been reading.

Today: some basics on type inference. Doesn't look so bad so far! Constraint Generation, Type Inference, Implicit Polymorphism.
And a bit of Small-World Phenomenon (while I was bored in semantics class).