use "collections"
use "files"
use "format"
use "itertools"

// The cardinal directions
primitive U
primitive D
primitive L
primitive R
type Dir is (U | D | L | R)

// A basic two-dimensional point class
class val Point is Hashable
  let _x: I64
  let _y: I64

  new val create(__x: I64, __y: I64) =>
    _x = __x
    _y = __y

  fun x(): I64 => _x
  fun y(): I64 => _y

  // because we want to use this as a key in a hashmap
  fun hash(): USize =>
    // hey this is probably bad, huh?
    _x.hash() + _y.hash()

  fun eq(other: Point): Bool =>
    (x() == other.x()) and (y() == other.y())

  fun ne(other: Point): Bool => not eq(other)

  // return the point that is `amt` squares awy from this one in `d` direction
  fun in_direction(d: Dir, amt: I64): Point =>
    match d
      | U => Point(_x, _y-amt)
      | D => Point(_x, _y+amt)
      | L => Point(_x-amt, _y)
      | R => Point(_x+amt, _y)
    end

  // print prettily
  fun show(): String =>
    "(" + Format.int[I64](_x) + ", " + Format.int[I64](_y) + ")"



// An 'instruction': a direction and a distance to travel in that
// direction
class val Instr
  let _dir: Dir
  let _amt: I64

  // parse from the string repr
  new val from_str(s: String) ? =>
    _dir = match s(0)?
      | 'U' => U
      | 'D' => D
      | 'L' => L
      | 'R' => R
    else error
    end
    _amt = s.trim(1).i64()?

  // given a starting point, return the array of all the points that
  // would be covered by this instruction
  fun points(start: Point): Array[Point] =>
    var p = Array[Point]()
    for i in Range[I64](0, _amt) do
      p.push(start.in_direction(_dir, i+1))
    end
    p


// A representation of the 'plan' for a line: nothing more than a
//sequence of 'Instr's
class val LinePlan
  let _plan: Array[Instr]

  new val from_str(s: String) ? =>
    var p = Array[Instr]()
    for chunk in s.split(",").values() do
      p.push(Instr.from_str(chunk)?)
    end
    _plan = p

  // this just gives the rest of the world access to our plan
  // mwahahahaha
  fun plan(): this->Array[Instr] => _plan


// The value we stores in the map: a list of which wires exist at that
//grid square as well as their distance along the wire
class Wires
  let wires: Array[(U8, U64)]

  // we always create this with no wires initialized
  new create() => wires = Array[(U8, U64)]()

  // this adds a new wire, and if a different wire already exists at
  // this spot then return the combined distance from their respective
  // roots, otherwise return None
  fun ref add_wire(wire: U8, dist: U64): (U64 | None) =>
    wires.push((wire, dist))
    var min_dist: (U64 | None) = None
    for (w, d) in wires.values() do
      if wire != w then
        let new_dist = d + dist
        match min_dist
          | None => min_dist = new_dist
          | let old_min: U64 if new_dist < old_min => min_dist = new_dist
        end
      end
    end
    min_dist

  // for pretty-printing, return a character represents this specific
  //wire, using '*' for intersections
  fun char(): String =>
    var s = Set[U8]()
    for (w, _) in wires.values() do
      s.set(w)
    end
    if s.size() > 1 then "*" else
      try Format.int[U8](s.values().next()?) else "?" end
    end

// the actual grid type that contains our grid logic
class Grid
  // a map from point to wire content. we could use a 2d array or
  //something, but 1. this does not need to grow when we go off the
  //'sides' and 2. it is sparse
  var storage: Map[Point, Wires]
  // this lists the intersections, keyed by their distance
  var intersections: Array[(U64, Point)]

  new create() =>
    storage = Map[Point, Wires]()
    intersections = Array[(U64, Point)]()

  // print prettily
  fun show(env: Env) =>
    var min_x: I64 = 0
    var min_y: I64 = 0
    var max_x: I64 = 0
    var max_y: I64 = 0
    for p in storage.keys() do
      min_x = p.x().min(min_x)
      min_y = p.y().min(min_y)
      max_x = p.x().max(max_x)
      max_y = p.y().max(max_y)
    end
    for y in Range[I64](min_y, max_y + 1) do
      for x in Range[I64](min_x, max_x + 1) do
        if (y == 0) and (x == 0) then
          env.out.write("O")
        else
          try
            env.out.write(storage(Point(x, y))?.char())
          else
            env.out.write(".")
          end
        end
      end
      env.out.write("\n")
    end

  // set point `p` to include wire `l` at distance `dist` from its
  // origin. this will automatically record an intersection if point
  // `p` already includes a different wire
  fun ref set(p: Point, l: U8, dist: U64) =>
    storage.insert_if_absent(p, Wires.create())
    try
      let wire = storage(p)?
      match wire.add_wire(l, dist)
        | let n: U64 => intersections.push((n, p))
        | None => None
      end
    end

  // follow each `LinePlan` and adds the description of the wires to the grid
  fun ref addLines(plans: Array[LinePlan]) =>
    for (line_number, plan) in Iter[LinePlan](plans.values()).enum[U8]() do
      var start_point = Point(0, 0)
      var dist: U64 = 1
      for instr in plan.plan().values() do
        for ps in instr.points(start_point).values() do
          set(ps, line_number, dist)
          start_point = ps
          dist = dist + 1
        end
      end
    end

  // print all the intersection values along with the point they map to.
  fun show_intersections(env: Env) =>
    for (dist, p) in intersections.values() do
      env.out.print(Format.int[U64](dist) + ": " + p.show())
    end


actor Main
  new create(env: Env) =>
    let caps = recover val FileCaps.>set(FileRead).>set(FileStat) end
    try
      with file = OpenFile(FilePath(env.root as AmbientAuth, "input.txt", caps)?) as File do
        var line_plans = Array[LinePlan]()
        for line in file.lines() do
          try line_plans.push(LinePlan.from_str(consume line)?) end
        end

        var grid = Grid.create()
        grid.addLines(line_plans)
        grid.show_intersections(env)
      end
    else
      env.err.print("Couldn't read expected file `input.txt'")
      env.exitcode(99)
    end