open Types
open Board
open Printer

type alert =
    OTHERS_HERE		(* Other robots and yours are at the same position. *)
  | YOU_CAN_BE_KILLED	(* Other robots can kill you. *)
  | YOU_CAN_BE_PUSHED_TO_WALL
  | YOU_CAN_BE_PUSHED
  | ADJACENT_ROBOTS

let print_alert = function
    OTHERS_HERE -> "others_here"
  | YOU_CAN_BE_KILLED -> "you_can_be_killed"
(*  | YOU_CAN_KILL_OTHER -> "you_can_kill_others" 
  | YOU_MAY_BE_BLOCKED -> "you_may_be_blocked" *)
  | ADJACENT_ROBOTS -> "adjacent_robots"
  | YOU_CAN_BE_PUSHED_TO_WALL -> "you_can_be_pushed_to_wall"
  | YOU_CAN_BE_PUSHED -> "you_can_be_pushed"

let print_alert_list l =
    let rec continue = function
	[] -> ""
      |	a::[] -> print_alert a
      |	a::l -> (print_alert a)^", "^(continue l)
    in
    continue l

let print_direction_option = 
  function
      None -> "X"
    | Some N -> "N"
    | Some E -> "E"
    | Some W -> "W"
    | Some S -> "S"

(*****************************************************************)

(* bids *)

let max_bids() = max (!money / 40) 5 (* 2.5% *)

let normal_bids() = max (!money / 100) 2 (* 1.0% *)

let random_bid n =
    Random.int (n / 2 + 1) + n / 2 + 1

let compute_bids others_here alert_list =
    if List.mem YOU_CAN_BE_KILLED alert_list then
	random_bid (max_bids())
    else if others_here then
	random_bid (max_bids())
    else if List.mem YOU_CAN_BE_PUSHED_TO_WALL alert_list then
	random_bid (normal_bids())
    else if List.mem YOU_CAN_BE_PUSHED alert_list then
	2
    else
	1

(*****************************************************************)

let approx_relevant_robots cutoff loc = 
  let approx_dist (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2) in
  let robots =
    IntMap.fold
      (fun id robot acc ->
	if id != !my_id && approx_dist loc robot.robot_loc <= cutoff then
	  robot.robot_loc :: acc
	else
	  acc)
      !robots
      []
  in robots

let exist_others ~dtable p time = 
  Dijkstra.earray dtable p <= float time

let is_walkable (x,y) =
  match !board.(y).(x) with
    Wall | Water -> false
  | _ -> true

let imagine ?exc_dir ~dtable time pos = 
(*  Printf.printf "[DEBUG] imagine: time=%d pos=%s edir=%s" time (print_loc pos) (print_direction_option exc_dir);*)
  let status = ref [] in
  let forced_pos = ref [] in
  let add_stat a =
    if not (List.mem a (!status)) then
      status := a::!status
  in
  let add_pos a = 
    if not (List.mem a (!forced_pos)) then
      forced_pos := a::!forced_pos
  in
  List.iter
    (fun dir ->
      let odir = invert_dir dir in
      let npos = move_pos pos dir in
      let skip = match exc_dir with
	None -> false
      | Some s -> s = dir
      in
      if not skip && is_walkable npos && exist_others ~dtable npos time then
	let ox, oy as opos = (move_pos pos odir) in
	match (!board).(oy).(ox) with
	  Water -> add_stat YOU_CAN_BE_KILLED;
	| Wall -> add_stat YOU_CAN_BE_PUSHED_TO_WALL;
	    add_pos pos
	| _ -> add_stat YOU_CAN_BE_PUSHED;
	    add_pos opos
    )
    [N; E; W; S];
(*  Printf.printf " -> %s\n" (print_alert_list !status); *)
  !status, !forced_pos

let alert_to_cost l = 
  if List.mem YOU_CAN_BE_KILLED l then -50
  else if List.mem YOU_CAN_BE_PUSHED l then -1
  else 1

let max_depth = 2

let move_may_be_blocked ~dtable pos dir time =
  let d1 = move_pos pos dir in
  if exist_others ~dtable pos time then
    let (d2x, d2y) = move_pos d1 dir in
    !board.(d2y).(d2x) = Wall
  else false


let rec list_unify = function
    [] -> []
  | hd::tl ->
      if List.mem hd tl 
      then list_unify tl
      else hd::(list_unify tl)

let rec merge_worst nlist cost = function
    [] -> nlist, cost
  | (alert, posl) :: rest ->
      let c = alert_to_cost alert in
      merge_worst (posl @ nlist) (min c cost) rest

let merge_worst l = 
  let l, c = merge_worst [] max_int l
  in
  list_unify l, c

let rec list_take_worst worst = function
    [] -> worst
  | h::t ->
      list_take_worst (min h worst) t

let list_take_worst = list_take_worst max_int

let rec tableau_take_best best = function
    [] -> best
  | (_,h)::t ->
      tableau_take_best (max best h) t

let tableau_take_best = tableau_take_best min_int

let rec cost_of_move ~dtable pos time dir = 
  (* 先行できた場合 *)
(*   Printf.printf "[DEBUG] cost_of_move: time=%d pos=%s dir=%s" time (print_loc pos) (print_direction_option dir);*)

  let new_pos = 
    match dir with
      None -> pos
    | Some d -> move_pos pos d
  in
  if 
    not (is_walkable new_pos) then begin
(*     Printf.printf " -> noway\n";*)
    (false, min_int)
  end 
  else begin
    let is_blocked = 
      match dir with
	None -> false
      | Some d -> move_may_be_blocked ~dtable pos d time
    in
    let alert_this_turn_f0, forced_pos_f0 as imagine_f0 = 
      imagine ~dtable time ?exc_dir:dir new_pos
    in
    let pos_opt, (forced_pos_f, cost_this_turn_f) = 
      if is_blocked then
	let imagine_f1 = imagine ~dtable time pos in
	[pos], merge_worst [imagine_f0; imagine_f1]
      else
	[], (forced_pos_f0, (alert_to_cost alert_this_turn_f0))
    in
    let pos_at_next_f = new_pos :: (pos_opt @ forced_pos_f) in
    
    (* 後攻した場合 *)
    let cost_this_turn_s, forced_pos_s =
      imagine ~dtable time pos in
    let cost_this_turn_s = alert_to_cost cost_this_turn_s in
    
    let pos_at_next_s = new_pos :: forced_pos_s in
    
    let prefer_slower = cost_this_turn_s > cost_this_turn_f in
    
    let cost_after_this_turn = 
      list_take_worst 
	(List.map (cost_of_turn ~dtable (time + 1)) (list_unify (pos_at_next_s @ pos_at_next_f))) in
    
    let p, c = prefer_slower, cost_after_this_turn / 3 + min cost_this_turn_f cost_this_turn_s in
(*    Printf.printf "[DEBUG] cost_of_move: time=%d pos=%s dir=%s" 
   time (print_loc pos) (print_direction_option dir); *)
(*    Printf.printf "-> slower=%s, cost=%d\n" (string_of_bool p) c; *)
    p, c
  end

and cost_of_turn ~dtable time pos = 
  if time > max_depth then
    alert_to_cost (fst (imagine ~dtable time pos))
  else
    let t = tableau_of_this_turn ~dtable time pos in
    tableau_take_best t

and tableau_of_this_turn ~dtable ?(prefer_dir=None) ?(prefer_ofs=(-10)) time pos = 
    let l = 
      List.map
	(fun d -> 
	  let pd, cd = cost_of_move ~dtable pos time d
	  in
	  pd, if prefer_dir=d then cd + prefer_ofs else cd)
	[None; Some N; Some E; Some W; Some S] in
    l

let make_dtable robots = 
  let dists, dtable =
    Dijkstra.dijkstra_list
      ~adjustment:Dijkstra.adjustment_simple
      ~d_limit:4.
      robots in
  dists

let idx_of_dir = function
    None -> 0
  | Some N -> 1
  | Some E -> 2
  | Some W -> 3
  | Some S -> 4

let get_score table dir = 
  snd (List.nth table (idx_of_dir dir))

let continuous_pass = ref 0

let get_best_command ~pass_requested table = 
  let score = ref min_int in
  let dir = ref None in
  for i = 0 to 4 do
    let ns = snd (List.nth table i) in
    let ns = 
      if i = 0 && not pass_requested then
	let p = !continuous_pass * 10 in
	ns - p
      else
	ns
    in
    if ns >= !score then begin
      dir := List.nth [None; Some N; Some E; Some W; Some S] i;
      score := ns;
    end
  done;
  !dir

let get_importance is_robot_overlaped table dir ~dtable loc = 
  let alerts,_ = (imagine ~dtable 0 loc) in
  let bid = compute_bids is_robot_overlaped alerts in
  let start_special_p =
    if is_robot_overlaped then
      match dir with
	None -> true
      | Some dir ->
	  let rec check l = 
	    let x, y = l in
	    Printf.printf "%s...\n" (print_loc l);
	    flush stdout;
	    match !board.(y).(x) with
	      Water -> false
	    | Wall -> true
	    | _ -> check (move_pos l dir)
	  in
	  check loc
    else
      false
  in
  if fst (List.nth table (idx_of_dir dir)) && not start_special_p then
    -bid
  else
    bid

let select_command cmd = 
  let cmd_dir = match cmd with
    Move s -> Some s | _ -> None
  in
  let loc = my_loc () in
  let robots = approx_relevant_robots 4 loc in
  if robots = [] then
    1, cmd
  else begin
    let dtable = make_dtable robots in
    let table = tableau_of_this_turn ~prefer_dir:cmd_dir ~prefer_ofs:10 ~dtable 0 loc in
    let is_robot_overlaped = 
      List.mem loc robots in
    if get_score table cmd_dir >= 0 then
      (get_importance is_robot_overlaped table cmd_dir ~dtable loc), cmd
    else begin
      let dir = get_best_command ~pass_requested:(cmd_dir=None) table in
      if cmd_dir = None || dir <> None then begin
	if !continuous_pass <> 0 then
	  print_endline "reset continuous_pass counter.";
	continuous_pass := 0;
      end
      else begin
	print_endline ("added continuous_pass counter "^(string_of_int !continuous_pass)^".");
	incr continuous_pass
      end;
      let cmd =
	match dir with
	  Some s -> Move s
	| None -> Pick []
      in
      (get_importance is_robot_overlaped table dir ~dtable loc), cmd
    end
  end

let _ = 
    Random.init (int_of_float (Unix.gettimeofday()))