require_relative 'util'
require_relative '10'

# --- Day 14: Disk Defragmentation ---

# Suddenly, a scheduled job activates the system's disk
# defragmenter. Were the situation different, you might sit and watch
# it for a while, but today, you just don't have that kind of
# time. It's soaking up valuable system resources that are needed
# elsewhere, and so the only option is to help it finish its task as
# soon as possible.

# The disk in question consists of a 128x128 grid; each square of the
# grid is either free or used. On this disk, the state of the grid is
# tracked by the bits in a sequence of knot hashes.

# A total of 128 knot hashes are calculated, each corresponding to a
# single row in the grid; each hash contains 128 bits which correspond
# to individual grid squares. Each bit of a hash indicates whether
# that square is free (0) or used (1).

# The hash inputs are a key string (your puzzle input), a dash, and a
# number from 0 to 127 corresponding to the row. For example, if your
# key string were `flqrgnkx`, then the first row would be given by the
# bits of the knot hash of `flqrgnkx-0`, the second row from the bits
# of the knot hash of `flqrgnkx-1`, and so on until the last row,
# `flqrgnkx-127`.

# The output of a knot hash is traditionally represented by 32
# hexadecimal digits; each of these digits correspond to 4 bits, for a
# total of 4 * 32 = 128 bits. To convert to bits, turn each
# hexadecimal digit to its equivalent binary value, high-bit first: 0
# becomes `0000`, 1 becomes `0001`, e becomes `1110`, f becomes
# `1111`, and so on; a hash that begins with `a0c2017...` in
# hexadecimal would begin with `10100000110000100000000101110000...`
# in binary.

# Continuing this process, the first 8 rows and columns for key
# `flqrgnkx` appear as follows, using `#` to denote used squares, and
# `.` to denote free ones:

#     ##.#.#..-->
#     .#.#.#.#
#     ....#.#.
#     #.#.##.#
#     .##.#...
#     ##..#..#
#     .#...#..
#     ##.#.##.-->
#     |      |
#     V      V

# In this example, 8108 squares are used across the entire 128x128 grid.

# Given your actual key string, how many squares are used?

# Your puzzle input is `jxqlasbh`.

def knothash(string)
  hasher = KnotHash.new(256, string.bytes + [17, 31, 73, 47, 23])
  64.times { hasher.round }
  hasher.hash
end

def hash_to_bits(string)
  explode(string).map { |c| c.to_i(16).to_s(2).rjust(4, '0') }.join
end

def grid(keystring)
  (0..127).map { |i| hash_to_bits(knothash("#{keystring}-#{i}")) }.join("\n")
end

def easy(keystring)
  grid(keystring).count('1')
end

input = 'jxqlasbh'

assert(hash_to_bits('a0c2017') == '1010000011000010000000010111')
assert(easy('flqrgnkx') == 8108)
puts "easy(input): #{easy(input)}"

# --- Part Two ---

# Now, all the defragmenter needs to know is the number of regions. A
# region is a group of used squares that are all adjacent, not
# including diagonals. Every used square is in exactly one region:
# lone used squares form their own isolated regions, while several
# adjacent squares all count as a single region.

# In the example above, the following nine regions are visible, each
# marked with a distinct digit:

#     11.2.3..-->
#     .1.2.3.4
#     ....5.6.
#     7.8.55.9
#     .88.5...
#     88..5..8
#     .8...8..
#     88.8.88.-->
#     |      |
#     V      V

# Of particular interest is the region marked 8; while it does not
# appear contiguous in this small view, all of the squares marked 8
# are connected when considering the whole 128x128 grid. In total, in
# this example, 1242 regions are present.

# How many regions are present given your key string?

require 'set'

class Grid
  attr_accessor :grid

  def initialize(input)
    @grid = input.split.map do |line|
      explode(line).map(&:to_i)
    end
  end

  def to_s
    @grid.map(&:join).join("\n")
  end

  def each
    @grid.each_with_index do |line, y|
      line.each_with_index do |char, x|
        yield(x, y, char)
      end
    end
  end

  def used
    result = Set.new
    each { |x, y, c| result << [x, y] if c == 1 }
    result
  end

  def at(x, y)
    return nil if x < 0 || y < 0
    row = @grid[y]
    return nil unless row
    [x, y, row[x]]
  end

  def neighbors(xy)
    result = []
    offsets = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    offsets.each do |xo, yo|
      x, y, char = at(xy[0] + xo, xy[1] + yo)
      result << [x, y] if char == 1
    end
    result
  end

  def component(start, seen = Set.new)
    seen << start
    neighbors(start).each do |coord|
      component(coord, seen) unless seen.include?(coord)
    end
    seen
  end

  def components
    used = self.used
    components = []
    until used.empty?
      component = component(used.first)
      components << component
      used = used.difference(component)
    end
    components
  end
end

def hard(input)
  grid = Grid.new(grid(input))
  grid.components.length
end

assert(hard('flqrgnkx') == 1242)
puts "hard(input): #{hard(input)}"