require_relative 'util'

# --- Day 13: A Maze of Twisty Little Cubicles ---

# You arrive at the first floor of this new building to discover a
# much less welcoming environment than the shiny atrium of the last
# one. Instead, you are in a maze of twisty little cubicles, all
# alike.

# Every location in this area is addressed by a pair of non-negative
# integers `(x,y)`. Each such coordinate is either a wall or an open
# space. You can't move diagonally. The cube maze starts at `0,0` and
# seems to extend infinitely toward positive x and y; negative values
# are invalid, as they represent a location outside the building. You
# are in a small waiting area at `1,1`.

# While it seems chaotic, a nearby morale-boosting poster explains,
# the layout is actually quite logical. You can determine whether a
# given `x,y` coordinate will be a wall or an open space using a
# simple system:

# - Find `x*x + 3*x + 2*x*y + y + y*y`.
# - Add the office designer's favorite number (your puzzle input).
# - Find the binary representation of that sum; count the number of
#   bits that are 1.
#   - If the number of bits that are 1 is even, it's an open space.
#   - If the number of bits that are 1 is odd, it's a wall.

# For example, if the office designer's favorite number were 10,
# drawing walls as `#` and open spaces as `.`, the corner of the building
# containing `0,0` would look like this:

#       0123456789
#     0 .#.####.##
#     1 ..#..#...#
#     2 #....##...
#     3 ###.#.###.
#     4 .##..#..#.
#     5 ..##....#.
#     6 #...##.###

# Now, suppose you wanted to reach `7,4`. The shortest route you could
# take is marked as O:

#       0123456789
#     0 .#.####.##
#     1 .O#..#...#
#     2 #OOO.##...
#     3 ###O#.###.
#     4 .##OO#OO#.
#     5 ..##OOO.#.
#     6 #...##.###

# Thus, reaching `7,4` would take a minimum of 11 steps (starting from
# your current location, `1,1`).

# What is the fewest number of steps required for you to reach 31,39?

test_input = 10
input = 1352

def popcount(n)
  n.to_s(2).count('1')
end

def keep(ary)
  result = nil
  ary.each do |item|
    break if (result = yield(item))
  end
  result
end

class Cubicles
  def initialize(n)
    @grid = Hash.new do |h, k|
      x, y = k
      f = x**2 + 3 * x + 2 * x * y + y + y**2
      h[k] = popcount(f + n).odd? ? '#' : '.'
    end
  end

  def show(w, h, xy)
    (0..h).each do |y|
      (0..w).each do |x|
        print [x, y] == xy ? 'X' : @grid[[x, y]]
        print ' '
      end
      puts
    end
  end

  def bfs(from, to, acc = 0)
    offsets = [[1, 0], [0, 1], [0, -1], [-1, 0]]
    queue = [[from, 1]]
    until queue.empty?
      xy, acc = queue.shift
      return acc if xy == to
      @grid[xy] = 'O' if @grid[xy] == '.'
      x, y = xy
      offsets.each do |xo, yo|
        next if x + xo < 0
        next if y + yo < 0
        next unless @grid[[x + xo, y + yo]] == '.'
        return acc if [x + xo, y + yo] == to
        queue << [[x + xo, y + yo], acc + 1]
      end
    end
  end
end

def easy(input, to)
  c = Cubicles.new(input)
  c.bfs([1, 1], to)
end

assert(easy(test_input, [7, 4]) == 11)
puts "easy(input, [31, 39]): #{easy(input, [31, 39])}"

# --- Part Two ---

# How many locations (distinct x,y coordinates, including your
# starting location) can you reach in at most 50 steps?

require 'set'

class Cubicles
  def locations(from, limit)
    offsets = [[1, 0], [0, 1], [0, -1], [-1, 0]]
    queue = [[from, 0]]
    result = Set.new
    until queue.empty?
      xy, acc = queue.shift
      result << xy
      next if acc == limit
      @grid[xy] = 'O' if @grid[xy] == '.'
      x, y = xy
      offsets.each do |xo, yo|
        next if x + xo < 0
        next if y + yo < 0
        next unless @grid[[x + xo, y + yo]] == '.'
        queue << [[x + xo, y + yo], acc + 1]
      end
    end
    result.length
  end
end

def hard(input, limit)
  c = Cubicles.new(input)
  c.locations([1, 1], limit)
end

puts "hard(input, 50): #{hard(input, 50)}"