pvik · December 5, 2019 13:38 · Dec 5, 2019
diff --git a/aoc_3.ml b/aoc_3.ml
@@ -0,0 +1,159 @@
+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)