let wire1 = ["R98" ; "U47" ; "R26" ; "D63" ; "R33" ; "U87" ; "L62" ; "D20" ; "R33" ; "U53" ; "R51"]
let wire2 = ["U98" ; "R91" ; "D20" ; "R16" ; "D67" ; "R40" ; "U7" ; "R15" ; "U6" ; "R7"]
         
type point = {
    x : float ;
    y : float
  }

type line = {
    p1 : point ;
    p2 : point
  }

type line_eq = {
    (* ax + by = c *)
    a : float ;
    b : float ;
    c : float
  }          

let as_line_eq (l1 : line)  =
  let a1 = l1.p2.y -. l1.p1.y and
      b1 = l1.p1.x -. l1.p2.x in
  let c1 = (a1 *. l1.p1.x) +. (b1 *. l1.p1.y) in
  {a = a1 ; b = b1 ; c = c1}

let on_segment (l : line) (p : point) =
  if p.x >= (min l.p1.x l.p2.x)
     && p.x <= (max l.p1.x l.p2.x)
     && p.y >= (min l.p1.y l.p2.y)
     && p.y <= (max l.p1.y l.p2.y)
  then
    true
  else
    false

let intersection_point (ll1 : line) (ll2 : line) =
  let l1 = as_line_eq ll1 and
      l2 = as_line_eq ll2 in
  let determinant = (l1.a *. l2.b) -. (l2.a *. l1.b) in
  if determinant = 0.0 then
    {x = 0.0 ; y = 0.0}
  else
    let x = (l2.b *. l1.c -. l1.b *. l2.c) /. determinant and
        y = (l1.a *. l2.c -. l2.a *. l1.c) /. determinant in
    {x = x ; y = y}
    
let is_intersect (l1 : line) (l2 : line) =
  let intr_pt = (intersection_point l1 l2) in
  if intr_pt.x = 0.0 && intr_pt.y = 0. then
    false 
  else
    if on_segment l1 intr_pt && on_segment l2 intr_pt then
      true
    else
      false
          
let magnitude {x ; y} =
  Float.sqrt (x ** 2.0 +. y ** 2.0) 

let length (ln : line) =
  Float.sqrt (((ln.p2.x -. ln.p1.x) ** 2.0) +. ((ln.p2.y -. ln.p1.y) ** 2.0))
  
let manhattan_distance {x ; y} =
  (Float.abs x) +. (Float.abs y)

let steps lns_lst pt =
  List.fold_left
    (fun (steps , reached) ln ->
      if reached then
        (steps, reached)
      else
        if on_segment ln pt then
          let new_ln = {p1 = ln.p1 ; p2 = pt} in
          (steps +. (length new_ln) , true)
        else
          (steps +. (length ln) , reached)
    )
    (0.0 , false)
    lns_lst

let path_to_line (start_pt : point) (path : string) =
  let path_lst = List.init (String.length path) (String.get path) and
      len_str = String.sub path 1 ((String.length path) - 1) in
  let path_len = float_of_string len_str in
  match path_lst with
  | 'R' :: _ -> { p1 = start_pt ; p2 = { x = start_pt.x +. path_len ; y = start_pt.y }}
  | 'L' :: _ -> { p1 = start_pt ; p2 = { x = start_pt.x -. path_len ; y = start_pt.y }}
  | 'U' :: _ -> { p1 = start_pt ; p2 = { x = start_pt.x ; y = start_pt.y +. path_len }}
  | 'D' :: _ -> { p1 = start_pt ; p2 = { x = start_pt.x ; y = start_pt.y -. path_len }}
  | _ -> {p1 = start_pt ; p2 = start_pt}
       
let paths_to_lines paths_lst =
  List.tl (
    List.rev (
      List.fold_left
        (fun acc (path : string) ->
          let last_ln = List.hd acc in
          let next_ln = path_to_line last_ln.p2 path in
          next_ln :: acc)
        [{p1 = {x = 0. ; y = 0.} ; p2 = {x = 0. ; y = 0.}}]
        paths_lst)
    )

let third_b w1 w2 =
  let lw1 = paths_to_lines w1 and
      lw2 = paths_to_lines w2 in
  List.fold_left
    (fun acc (ln : line) ->
      let acc_inner =
            (List.fold_left
               (fun acc1 (ln2 : line) ->
                 if is_intersect ln ln2  then
                   let intr_pt = intersection_point ln ln2 in
                   let (steps1 , reached1) = steps lw1 intr_pt and
                       (steps2 , reached2) = steps lw2 intr_pt in
                   if reached1 && reached2 then
                     steps1 +. steps2                     
                   else
                     acc1
                 else acc1)
               acc
               lw2) in
      if acc_inner < acc then
        acc_inner
      else acc)
    max_float
    lw1

let third_a w1 w2 =
  let lw1 = paths_to_lines w1 and
      lw2 = paths_to_lines w2 in
  List.fold_left
    (fun acc (ln : line) ->
      let acc_inner =
            (List.fold_left
               (fun acc1 (ln2 : line) ->
                 (* Printf.printf "inner min mag is %f ; outter min mag is %f \n" acc1 acc ;
                  * Printf.printf "  checking line [(%f,%f) - (%f,%f)] against line [(%f,%f) - (%f,%f)] \n"
                  *   ln.p1.x ln.p1.y ln.p2.x ln.p2.y ln2.p1.x ln2.p1.y ln2.p2.x ln2.p2.y ; *)
                 if is_intersect ln ln2  then
                   let intr_pt = intersection_point ln ln2 in
                   let intr_mag = manhattan_distance intr_pt in
                   (* Printf.printf "   - lines intersect at (%f,%f) ; manhattan_distance is %f\n"
                    *   intr_pt.x intr_pt.y intr_mag; *)
                   if intr_mag < acc1 then
                     intr_mag 
                   else acc1
                 else acc1)
               acc
               lw2) in
      if acc_inner < acc then
        acc_inner
      else acc)
    max_float
    lw1
  
let () =
  Printf.printf "Res: %f\n" (third_b wire1 wire2)