#!/usr/bin/env ruby

problem = 6
input = File.readlines("#{problem}.input").map(&:strip).map(&:chars)
#input = DATA.read.split("\n").map(&:chars)

DIRECTIONS = ["^", ">", "v", "<"]

def find_start(input)
  input.each_with_index do |row, x|
    y = row.index { DIRECTIONS.include?(_1) }
    return [x,y] unless y.nil?
  end
end

def movement(direction)
  [[-1, 0], [0, 1], [1, 0], [0, -1]][direction]
end

def out_of_bounds?(input, location)
  location.first >= input.size ||
    location.last >= input.first.size ||
    location.first < 0 ||
    location.last < 0
end

def obstructed?(input, location)
  ["O", "#"].include?(input[location.first][location.last])
end

def traverse(input, starting_location, starting_direction)
  location = starting_location.dup
  direction = starting_direction.dup
  visited = Hash.new { |h, k| h[k] = 0 }

  while
    visited[location] += 1

    next_location = []
    loop do
      movement = movement(direction)
      next_location = [
        location.first + movement.first,
        location.last + movement.last
      ]
      break if out_of_bounds?(input, next_location)
      break unless obstructed?(input, next_location)
      direction = (direction + 1) % 4
    end

    if out_of_bounds?(input, next_location)
      return visited.keys
    elsif visited[location] > 5
      return :loop
    else
      location = next_location
    end
  end
end

def find_obstructions(input, nodes, start_location, start_direction)
  last_value = "."
  nodes.select.with_index do |node, i|
    # undo last mark
    if i > 0
      last_location = nodes[i - 1]
      input[last_location.first][last_location.last] = last_value
    end
    # mark node a barrier
    last_value = input[node.first][node.last]
    input[node.first][node.last] = "O"

    # traverse
    traverse(input, start_location, start_direction) == :loop
  end
end

path = []
location = find_start(input)
direction = DIRECTIONS.index(input[location.first][location.last])

visited = traverse(input, location, direction)

start = Time.now
result_2 = find_obstructions(input, visited, location, direction)
finish = Time.now
puts "Finished in #{finish - start}"

result_1 = visited.uniq.size

p result_1
p result_2.uniq.size

__END__
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...