Towers

grid.rb

# https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html
# Should be able to do Hard,
# which is listed in latin.c as diff_set_0,
# handled by checking all permutations for all rows + columns,
# and can do Extreme,
# which is listed in latin.c as both diff_set_1 and diff_forcing,
# which are implemented as xwing and forcing_chain
#
# https://www.janko.at/Raetsel/Wolkenkratzer/index.htm
# Have not yet determined whether any puzzle on janko.at actually has diagonal labels,
# but some have a diagonal restriction where diagonals can't contain repeated numbers

class Grid
  attr_reader :side_length

  def self.from_link_or_file(s)
    s.include?('http') ? from_link(s) : from_janko(File.readlines(s))
  end

  def self.from_link(link)
    link.include?('janko.at') ? from_janko(`curl #{link}`.lines) : from_sgtatham(link)
  end

  def self.from_sgtatham(link)
    # Example string:
    # (url)#6:2/2/3/2/1/3/4/2/2/1/3/3/4/1/2/2/2/3/2/3/3/1/2/3,a4h3a3l3b2f1
    l, str = link.split(?#, 2)
    str ||= l
    side_length_str, heights_str = str.split(?:, 2)
    side_length = Integer(side_length_str)
    heights_str, known_str = heights_str.split(?,, 2)
    # sadly but understandably, split removes all trailing elements,
    # so in the case of something like 3//, I need to add one element and remove it after.
    heights = (heights_str + '/0').split(?/).map { |x| x.empty? ? nil : Integer(x) }
    raise "popped off something weird from #{heights_str}" if heights.pop != 0
    raise "bad heights #{heights} #{heights.size}, need #{side_length * 4}" if heights.size != side_length * 4
    heights = heights.each_slice(side_length).to_a

    knowns = Array.new(side_length) { Array.new(side_length, nil) }

    nonzero_digit = (?1..?9)
    i = 0
    known_str&.each_char { |c|
      if nonzero_digit.cover?(c)
        y, x = i.divmod(side_length)
        knowns[y][x] = Integer(c)
        i += 1
      elsif c == ?_
        # Seems to be used to separate two consecutive digits,
        # which isn't currently useful since only up to 9x9 is supported,
        # but maybe useful if one day two-digit numbers are allowed.
        next
      else
        i += 1 + c.ord - ?a.ord
      end
    }

    new(knowns, *heights)
  end

  def self.from_janko(lines)
    labels = false
    problem = false
    diagonals = false
    side_length = nil
    max_height = nil
    heights = []
    knowns = []

    conv = ->l { l.split.map { _1 == ?- ? nil : Integer(_1) } }

    lines.each { |l|
      if l.start_with?('size')
        raise "already know side_length #{side_length}" if side_length
        side_length = Integer(l.split.last)
        next
      elsif l.start_with?('depth')
        raise "already know max_height #{max_height}" if max_height
        max_height = Integer(l.split.last)
      elsif l.chomp.match?(/puzzle\s+skyscrapers,\s+diagonals/)
        diagonals = true
      elsif l.chomp == 'clabels'
        labels = true
        next
      elsif l.chomp == 'rlabels'
        next
      elsif l.chomp == 'problem'
        problem = true
        labels = false
        next
      elsif l.chomp == 'solution'
        break
      end

      heights << conv[l] if labels
      knowns << conv[l] if problem
    }

    knowns = Array.new(side_length) { Array.new(side_length, nil) } if knowns.empty?

    new(knowns, *heights, max_height: max_height, diagonals: diagonals)
  end

  # top and bottom are left-to-right
  # left and right are top-to-bottom
  # knowns is a 2d array that must be square
  # int for a known height, nil for unknown
  def initialize(knowns, top, bottom, left, right, max_height: nil, diagonals: false)
    @side_length = knowns.size
    @diagonals = diagonals
    sizes = knowns.map(&:size)
    raise "bad sizes #{sizes}" if sizes.any? { _1 != @side_length }

    @max_height = max_height || @side_length
    heights = (1..@max_height).to_a
    raise "too many heights #{heights}" if heights.size > @side_length
    heights.unshift(0) until heights.size == @side_length
    @heights = heights.freeze
    @bit_position_of = heights.uniq.each_with_index.to_h.freeze
    @num_unique_heights = @bit_position_of.size
    @num_zeroes = @heights.index(1)

    @top = top.freeze
    @bottom = bottom.freeze
    @left = left.freeze
    @right = right.freeze

    # Helps not do unnecessary work for the larger sizes such as 8 and 9.
    # Try commenting out the unless @row_dirty / unless @col_dirty for those sizes to compare.
    @row_dirty = Array.new(@side_length) { |i| left[i] || right[i] }
    @col_dirty = Array.new(@side_length) { |i| top[i] || bottom[i] }
    @diag_dirty = {
      falling: false,
      rising: false,
    }

    reset_changed
    # Pencil marks:
    #
    # Each element of the array is a row of the grid.
    #
    # Within each row:
    # Least-significant side_length bits are the leftmost cell of that row
    # Most-significant side_length bits are the rightmost cell of that row
    #
    # Within each chunk of side_length bits:
    # Least-significant bit is whether 1 is possible
    # Most-significant bit is whether side_length is possible
    # 1 if possible, else 0
    @pencil_marks = Array.new(@side_length, (1 << @num_unique_heights * @side_length) - 1)

    # this might make some rows/cols dirty that have no number
    # but I guess that's fine? if it reveals any hidden/naked groups
    knowns.each_with_index { |known_row, y|
      # e.g 111111
      full_cell = (1 << @num_unique_heights) - 1
      known_row.each_with_index { |known, x|
        next unless known

        # eg 111011
        except_known = full_cell & ~(1 << @bit_position_of[known])
        clear_cell(y, x, except_known)
      }
    }

    # Cache possible permutations for each row/col,
    # so that we don't repeatedly generate ones we've previously eliminated.
    @row_perms = @pencil_marks.map { |row|
      self.class.permutations_for_group(row, @heights, @bit_position_of).to_a
    }.freeze
    @col_perms = @side_length.times.map { |x|
      self.class.permutations_for_group(col_mask(x), @heights, @bit_position_of).to_a
    }.freeze

    if diagonals
      @diag_perms = {
        falling: self.class.permutations_for_group(diag_mask(:falling), @heights, @bit_position_of).to_a,
        rising: self.class.permutations_for_group(diag_mask(:rising), @heights, @bit_position_of).to_a,
      }.freeze
    end
  end

  def col_mask(x)
    # 0 (top row) least significant bit
    @pencil_marks.each_with_index.sum { |row, y|
      row[x * @num_unique_heights, @num_unique_heights] << (@num_unique_heights * y)
    }
  end

  def diag_mask(dir)
    # 0 (top row) least significant bit

    x0, dx = self.class.diag_xs(dir, side_length)

    @pencil_marks.each_with_index.sum { |row, y|
      x = x0 + dx * y
      row[x * @num_unique_heights, @num_unique_heights] << (@num_unique_heights * y)
    }
  end

  def self.diag_xs(dir, side_length)
    # 0 (top row) least significant bit

    case dir
    when :falling
      [0, 1]
    when :rising
      [side_length - 1, -1]
    else
      raise "unknown diag dir #{dir}"
    end
  end

  def solved?
    @pencil_marks.all? { |row|
      row.digits(1 << @num_unique_heights).all? { self.class.power_of_two?(_1) }
    }
  end

  def possible?(y, x, n)
    @pencil_marks[y][x * @num_unique_heights + @bit_position_of[n]] != 0
  end

  # If change, returns the resulting union of masks.
  # If no change, returns nil.
  def self.step_for_group(perms, original_mask, bit_position_of, forward, reverse, type)
    union_of_masks = 0

    #puts ?- * 40 if type == :col

    # Possible but a bit slow for larger grids.
    #(1..side_length).to_a.permutation { |perm|
    #permutations_for_group(original_mask, side_length).each { |perm|

    num_unique_heights = bit_position_of.size

    perms.select! { |perm|
      # Note that when making a bitfield this way,
      # element 0 will be the least significant bit.
      bits = perm.each_with_index.sum { |x, i|
        1 << (bit_position_of[x] + num_unique_heights * i)
      }
      next unless original_mask.allbits?(bits)
      #puts 'Yes: %s %036b is allowed by %036b' % [perm, bits, original_mask] if type == :col
      # TODO: heights_ok? only ever needs to happen once per group, since height clues don't change.
      # only the bit masks change.
      next unless heights_ok?(perm, forward, reverse)
      #puts 'Yes: %s %036b is allowed by %036b and height' % [perm, bits, original_mask] if type == :col

      union_of_masks |= bits
    }

    union_of_masks if union_of_masks != original_mask
  end

  def self.permutations_for_group(mask, heights, bit_position_of)
    unique_heights = bit_position_of.keys
    num_unique_heights = bit_position_of.size

    unknown_num = (1 << num_unique_heights) - 1
    pos = -1

    # known_or_not becomes an array of:
    # negative number N: at that position is -N
    # non-negative number N: at that position is permutation's Nth element.
    #
    # For example, Grid.permutations_for_group(0b1111111101001111, a = [1, 2, 3, 4], a.each_with_index.to_h)
    # unknown_num = [1, 2, 4]
    # known_or_not = [0, -3, 1, 2]
    # so we'll generate permutations of [1, 2, 4], and insert 3 in the correct position.
    known_or_not = heights.size.times.map { |i|
      cell = mask[i * num_unique_heights, num_unique_heights]
      if power_of_two?(cell)
        unknown_num &= ~cell

        # which bit is set?
        # cell = 100 -> bit = 2
        bit = 0
        until cell == 1
          bit += 1
          cell >>= 1
        end

        # I guess I could handle it by shifting it so that:
        # non-positive N: at that position is -N
        # positive N: at that position is perm's N-1th element.
        # but no need to do that yet.
        raise "sorry, can't handle known 0 yet since negative numbers represent known numbers..." if bit == 0 && unique_heights.first == 0

        -unique_heights[bit]
      else
        pos += 1
      end
    }

    unknown_num = bit_position_of.select { |_digit, pos| unknown_num[pos] != 0 }.keys
    unknown_num.unshift(0) until unknown_num.count(0) == heights.count(0)

    Enumerator.new { |y|
      unknown_num.permutation { |perm|
        y << known_or_not.map { _1 < 0 ? -_1 : perm[_1] }
      }
    }
  end

  def self.xwing(pencil_marks, num_unique_heights, num_zeroes)
    side_length = pencil_marks.size
    # cols_in_row[i][y] is bitfield telling in which cols digit i can occur in row y.
    cols_in_row = Array.new(side_length) { Array.new(side_length, 0) }
    rows_in_col = Array.new(side_length) { Array.new(side_length, 0) }

    pencil_marks.each_with_index { |row, y|
      i = 0
      until row == 0
        if row & 1 != 0
          x, digit = i.divmod(num_unique_heights)
          cols_in_row[digit][y] |= 1 << x
          rows_in_col[digit][x] |= 1 << y
        end
        row >>= 1
        i += 1
      end
    }

    cols_in_row.each_with_index { |cir, digit|
      next if num_zeroes > 1 && digit == 0
      next unless (xwing_rows, xwing_cols = xwing_find_internal(cir))
      return [digit, :cols_in_row, xwing_rows, xwing_cols]
    }
    rows_in_col.each_with_index { |ric, digit|
      next if num_zeroes > 1 && digit == 0
      next unless (xwing_cols, xwing_rows = xwing_find_internal(ric))
      return [digit, :rows_in_col, xwing_rows, xwing_cols]
    }

    nil
  end

  def self.xwing_find_internal(group)
    side_length = group.size
    (1 << side_length).times { |selected_bitfield|
      popcount = selected_bitfield.to_s(2).count(?1)
      # 1 would just be a hidden single in this dimension, covered by permutations.
      next if popcount <= 1
      # n - 1 would just be a hidden single in the other dimension, covered by permutations.
      next if popcount >= side_length - 1

      in_xwing = 0
      not_in_xwing = 0
      has_known = false
      group.each_with_index { |g, group_idx|
        if selected_bitfield[group_idx] != 0
          if power_of_two?(g)
            # no point because a known will already have eliminated in its row and column.
            has_known = true
            break
          end
          in_xwing |= g
        else
          not_in_xwing |= g
        end
      }

      next if has_known
      affected = in_xwing & not_in_xwing
      next if affected == 0
      next if in_xwing.to_s(2).count(?1) > popcount

      return [selected_bitfield, in_xwing]
    }

    nil
  end

  # TODO: A few more cases to take into account:
  #
  # On a diagonal for an odd-sized grid, centre square and two corners see the other two corners,
  # so max size can go up to three if those three specific squares are involved.
  #
  # Rows and columns can use this logic as well if one of the cells is on a diagonal.
  #
  # Further, if it's an edge row or column,
  # Centre square of that row/column and two corners will see centre of the entire grid,
  # so another case where max size would be three.
  def self.two_in_diag(pencil_marks, num_unique_heights, num_zeroes)
    side_length = pencil_marks.size

    %i(falling rising).each { |dir|
      possible_pos = Array.new(side_length) { [] }

      x0, dx = diag_xs(dir, side_length)

      pencil_marks.each_with_index { |row, y|
        x = x0 + dx * y
        cell = row[x * num_unique_heights, num_unique_heights]
        num_unique_heights.times { |digit|
          next if num_zeroes > 1 && digit == 0
          possible_pos[digit] << [y, x] if cell[digit] != 0
        }
      }

      possible_pos.each_with_index { |poses, digit|
        next if poses.size != 2

        good_targets = visible_to_all_with_digit(pencil_marks, num_unique_heights, poses, digit, diagonals: true)
        return {
          targets: good_targets,
          digit: digit,
          cells: poses,
        } unless good_targets.empty?
      }
    }

    nil
  end

  def self.visible_to_all_with_digit(pencil_marks, num_unique_heights, poses, digit, diagonals:)
    raise "duplicate cells in #{poses}" if poses.uniq.size != poses.size

    side_length = pencil_marks.size

    targets = poses.map { visible_to(side_length, *_1, diagonals: diagonals) }.reduce(:&)

    targets.select { |ty, tx|
      # TODO: Oops, repeated code w/ inst method possible?
      # except no lookup of bit_position_of here
      pencil_marks[ty][tx * num_unique_heights + digit] != 0
    }
  end

  def self.visible_to(side_length, y, x, diagonals:)
    row = ((0...side_length).to_a - [x]).map { |vx| [y, vx] }
    col = ((0...side_length).to_a - [y]).map { |vy| [vy, x] }
    diag1 = diagonals && y == x ? ((0...side_length).to_a - [y]).map { |vy| [vy, vy] } : []
    diag2 = diagonals && y + x == side_length - 1 ? ((0...side_length).to_a - [y]).map { |vy| [vy, side_length - 1 - vy] } : []
    row + col + diag1 + diag2
  end

  def self.forcing_chain(pencil_marks, num_unique_heights, num_zeroes, diagonals: false)
    side_length = pencil_marks.size

    cells = pencil_marks.map.with_index { |row, y|
      side_length.times.map { |x|
        cell = row[x * num_unique_heights, num_unique_heights]
        next if cell.to_s(2).count(?1) != 2
        # zeroes can't participate in forcing chains if there are too many of them.
        next if num_zeroes > 1 && cell & 1 != 0
        {
          y: y,
          x: x,
          bits: bits = num_unique_heights.times.select { cell[_1] != 0 }.freeze,
          opp: {bits[0] => bits[1], bits[1] => bits[0]},
          neigh: Hash.new { |h, k| h[k] = [] }
        }.freeze
      }
    }

    connect_pairs = ->candidates {
      candidates.compact.combination(2) { |a, b|
        (a[:bits] & b[:bits]).each { |samebit|
          a[:neigh][samebit] << b
          b[:neigh][samebit] << a
        }
      }
    }

    cells.each { |row| connect_pairs[row] }

    side_length.times { |x|
      col = cells.map { _1[x] }
      connect_pairs[col]
    }

    %i(falling rising).each { |dir|
      x0, dx = diag_xs(dir, side_length)
      diag = cells.map.with_index { |row, y| row[x0 + dx * y] }
      connect_pairs[diag]
    } if diagonals

    side_length.times { |x|
      cells.map { _1[x] }.compact.combination(2) { |a, b|
        (a[:bits] & b[:bits]).each { |samebit|
          a[:neigh][samebit] << b
          b[:neigh][samebit] << a
        }
      }
    }

    cells = cells.flatten.compact
    cells.each {
      _1[:neigh].default_proc = nil
      _1[:neigh].freeze
    }

    cells.flatten.compact.each { |cell|
      if (c = forcing_chain_find_internal(pencil_marks, num_unique_heights, cells, cell, *cell[:bits], diagonals: diagonals))
        return c
      end
      if (c = forcing_chain_find_internal(pencil_marks, num_unique_heights, cells, cell, *cell[:bits].reverse, diagonals: diagonals))
        return c
      end
    }

    nil
  end

  def self.forcing_chain_find_internal(pencil_marks, num_unique_heights, cells, cell, left, right, diagonals:)
    gen = -1
    q = [[cell, left]]
    prev = {cell => nil}

    until q.empty?
      gen += 1
      nq = []

      while (cand, cands_left = q.shift)
        cands_right = cand[:opp][cands_left]

        if cands_right == left
          poses = [cell, cand].map { _1.values_at(:y, :x) }
          good_targets = visible_to_all_with_digit(pencil_marks, num_unique_heights, poses, left, diagonals: diagonals)
          return {
            targets: good_targets,
            digit: left,
            cells: reconstruct_path(prev, cand),
          } unless good_targets.empty?
        end

        cand[:neigh][cands_right]&.each { |neigh|
          next if prev.has_key?(neigh)
          prev[neigh] = cand
          # candidate's right is the new left
          nq << [neigh, cands_right]
        }
      end

      q = nq
    end

    nil
  end

  def self.reconstruct_path(prevs, n)
    path = [n]
    current = n
    while (current = prevs[current])
      path.unshift(current)
    end
    path
  end

  def step
    reset_changed

    @side_length.times { |y|
      next unless @row_dirty[y]

      # Recall that @pencil_marks rows are stored such that element 0 is on the left.
      #
      # For generated row permutations: element 0 is also on the left.
      # so forward is left, reverse is right.
      next unless (changed_row = self.class.step_for_group(@row_perms[y], @pencil_marks[y], @bit_position_of, @left[y], @right[y], :row))

      changed, new_known = self.class.compare(@pencil_marks[y], changed_row, @side_length, @num_unique_heights)
      @pencil_marks[y] = changed_row
      changed.each_key { |x|
        mark_cell_changed(y, x, dirty_row: false)
      }

      @row_dirty[y] = false

      return {
        type: :row,
        y: y,
        changed: changed.size,
        new_known: new_known.size,
      }
    }

    @side_length.times { |x|
      next unless @col_dirty[x]

      # 0 (top row) least significant bit
      col_mask = col_mask(x)

      # For generated col permutations: element 0 is on the top,
      # which matches how col_mask is generated above.
      # so forward is top, reverse is bottom.
      next unless (changed_col = self.class.step_for_group(@col_perms[x], col_mask, @bit_position_of, @top[x], @bottom[x], :col))

      changed, new_known = self.class.compare(col_mask, changed_col, @side_length, @num_unique_heights)
      changed.each { |y, new_cell|
        set_cell(y, x, new_cell, dirty_col: false)
      }

      @col_dirty[x] = false

      return {
        type: :col,
        x: x,
        changed: changed.size,
        new_known: new_known.size,
      }
    }

    if @diagonals
      %i(falling rising).each { |dir|
        next unless @diag_dirty[dir]

        diag_mask = diag_mask(dir)
        next unless (changed_diag = self.class.step_for_group(@diag_perms[dir], diag_mask, @bit_position_of, nil, nil, :diag))

        changed, new_known = self.class.compare(diag_mask, changed_diag, @side_length, @num_unique_heights)

        x0, dx = self.class.diag_xs(dir, side_length)

        changed.each { |y, new_cell|
          x = x0 + y * dx
          set_cell(y, x, new_cell, dirty_diag: false)
        }

        @diag_dirty[dir] = false

        return {
          type: :diag,
          dir: dir,
          changed: changed.size,
          new_known: new_known.size,
        }
      }

      if (forced_diag = self.class.two_in_diag(@pencil_marks.dup, @num_unique_heights, @num_zeroes))
        mask = 1 << forced_diag[:digit]
        forced_diag[:targets].each { |targ|
          clear_cell(*targ, mask)
        }

        return {
          type: :two_in_diag,
          targets: forced_diag[:targets],
          digit: forced_diag[:digit] + 1,
          cells: forced_diag[:cells],
        }
      end
    end

    if (digit, dir, xwing_rows, xwing_cols = self.class.xwing(@pencil_marks.dup, @num_unique_heights, @num_zeroes))
      mask = 1 << digit
      case dir
      when :cols_in_row
        # Look for the designated columns in other rows and clear that digit.
        @side_length.times { |y|
          next if xwing_rows[y] != 0
          @side_length.times { |x|
            next if xwing_cols[x] == 0
            clear_cell(y, x, mask)
          }
        }
      when :rows_in_col
        # Look for the designated rows in other columns and clear that digit.
        @side_length.times { |y|
          next if xwing_rows[y] == 0
          @side_length.times { |x|
            next if xwing_cols[x] != 0
            clear_cell(y, x, mask)
          }
        }
      else raise "unknown dir #{dir}"
      end
      bits_in_num = ->n { (0...@side_length).select { n[_1] != 0 } }

      return {
        type: :xwing,
        xwing_dir: dir,
        digit: digit + 1,
        rows: bits_in_num[xwing_rows],
        cols: bits_in_num[xwing_cols],
      }
    end

    if (chain = self.class.forcing_chain(@pencil_marks.dup, @num_unique_heights, @num_zeroes, diagonals: @diagonals))
      mask = 1 << chain[:digit]
      chain[:targets].each { |targ|
        clear_cell(*targ, mask)
      }

      return {
        type: :forcing_chain,
        targets: chain[:targets],
        digit: chain[:digit] + 1,
        len: chain[:cells].size,
        cells: chain[:cells].map { |cell|
          {
            pos: [cell[:y], cell[:x]],
            digits: cell[:bits].map(&:succ),
          }
        },
      }
    end

    false
  end

  def self.power_of_two?(x)
    x != 0 && x & (x - 1) == 0
  end

  def self.compare(old, new, side_length, num_unique_heights)
    changed = {}
    new_known = []

    side_length.times { |x|
      old_cell = old[0, num_unique_heights]
      new_cell = new[0, num_unique_heights]
      if old_cell != new_cell
        changed[x] = new_cell
        if power_of_two?(old_cell)
          raise "why changing a known cell? #{old_cell} to #{new_cell}"
        elsif power_of_two?(new_cell)
          new_known << x
        end
      end

      old >>= num_unique_heights
      new >>= num_unique_heights
    }

    [changed, new_known]
  end

  def self.heights_ok?(heights, forward, reverse)
    if forward
      min = 0
      forward_sum = heights.count { |h| min = h if h > min }
      return false if forward_sum != forward
    end

    if reverse
      min = 0
      reverse_sum = heights.reverse.count { |h| min = h if h > min }
      return false if reverse_sum != reverse
    end

    true
  end

  def reset_changed
    @changed = Array.new(@side_length) { Array.new(@side_length, false) }
  end

  def clear_neigh_of_known(y, x)
    known_bit = @pencil_marks[y][x * @num_unique_heights, @num_unique_heights]
    raise "bad clear! #{y} #{x} is #{known_bit}" unless self.class.power_of_two?(known_bit)

    # If there are multiple zeroes, don't clear
    # Actually we could clear if the number of zeroes in the group has met the quota,
    # but I think I'll just let permutation checking check that.
    return if @num_zeroes > 1 && known_bit == 1

    # Don't dirty the same dimension as that being cleared.
    # It's just been checked, since presumably that's what resulted in this known.

    # Clear the row (same y, different x)
    @side_length.times { |xx|
      next if xx == x
      clear_cell(y, xx, known_bit, dirty_row: false)
    }

    # Clear the column (same x, different y)
    @side_length.times { |yy|
      next if yy == y
      clear_cell(yy, x, known_bit, dirty_col: false)
    }

    return unless @diagonals

    if y == x
      @side_length.times { |yy|
        next if yy == y
        clear_cell(yy, yy, known_bit, dirty_diag: false)
      }
    end

    if y + x == @side_length - 1
      @side_length.times { |yy|
        next if yy == y
        clear_cell(yy, @side_length - 1 - yy, known_bit, dirty_diag: false)
      }
    end
  end

  def clear_cell(y, x, mask, **dirty_args)
    shift = @num_unique_heights * x
    current = @pencil_marks[y] >> shift
    # Cell already does not have this digit
    return if current & mask == 0
    raise "why setting #{y} #{x} from #{current} to 0? mask #{mask}" if current & ~mask == 0

    @pencil_marks[y] &= ~(mask << shift)
    mark_cell_changed(y, x, **dirty_args)
  end

  def set_cell(y, x, new_cell, **dirty_args)
    full_cell = (1 << @num_unique_heights) - 1
    shift = @num_unique_heights * x
    @pencil_marks[y] &= ~(full_cell << shift)
    @pencil_marks[y] |= new_cell << shift
    mark_cell_changed(y, x, **dirty_args)
  end

  def mark_cell_changed(y, x, dirty_col: true, dirty_row: true, dirty_diag: true)
    @changed[y][x] = true
    @col_dirty[x] = true if dirty_col
    @row_dirty[y] = true if dirty_row
    if dirty_diag
      @diag_dirty[:falling] = true if x == y
      @diag_dirty[:rising] = true if x + y == @side_length - 1
    end
    clear_neigh_of_known(y, x) if self.class.power_of_two?(@pencil_marks[y][x * @num_unique_heights, @num_unique_heights])
  end

  def to_sgtatham
    page = 'https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html'
    heights = (@top + @bottom + @left + @right).join(?/)

    knowns = ''
    gap_char = ->gap {
      (gap == 0 ? (knowns.empty? ? '' : ?_) : ?a.ord - 1 + gap)
    }

    gap = 0
    @pencil_marks.each { |row|
      @side_length.times { |x|
        cell = row[x * @num_unique_heights, @num_unique_heights]
        if self.class.power_of_two?(cell)
          knowns << gap_char[gap]
          knowns << @bit_position_of.find { |_digit, pos| cell[pos] != 0 }.first.to_s
          gap = 0
        else
          gap += 1
        end
      }
    }

    knowns << gap_char[gap] if gap != 0 && !knowns.empty?

    "#{page}##{@side_length}:#{heights},#{knowns}"
  end

  def to_s
    rows = @pencil_marks.zip(@left, @right, @changed).map { |row, left, right, changed|
      stuff = changed.map.with_index { |cell_changed, cell_id|
        cell = row[cell_id * @num_unique_heights, @num_unique_heights]
        digits = @bit_position_of.select { |_digit, pos| cell[pos] != 0 }.keys.join

        "\e[#{cell_changed ? 1 : 0};#{digits.size == 1 ? 32 : 37}m%#{@num_unique_heights}s\e[0m" % digits
      }.join(' | ')
      "#{left || ' '} | #{stuff} | #{right}"
    }

    rows.unshift(head_foot_to_s(@top))
    rows << head_foot_to_s(@bottom)
    rows.join("\n  #{?- * (@side_length * (@num_unique_heights + 3) + 1)}\n")
  end

  def head_foot_to_s(row)
    '  | ' + row.map { _1 ? "%#{@num_unique_heights}d" % _1 : ' ' * @side_length }.join(' | ') +  ' |'
  end
end

pencil.rb

require_relative 'grid'

def up_left(size)
  size.times {
    `xdotool key Up`
    `xdotool key Left`
  }
end

def fill(digits, size, grid)
  puts "about to fill cells with #{digits.join} in 2 seconds (make sure cursor in hint mode)"
  s = digits.join
  sleep 2
  up_left(size)

  size.times { |y|
    size.times { |xi|
      x = y.even? ? xi : size - 1 - xi
      s = digits.select { |d| grid.possible?(y, x, d) }.join if grid
      # if empty, xdotool will say not enough args
      `xdotool type #{s}` unless s.empty?
      `xdotool key #{y.even? ? :Right : :Left}`
    }
    `xdotool key Down`
  }
end

if (size = Integer(ARGV[0], exception: false))
  grid = nil
else
  grid = Grid.from_link_or_file(ARGV[0])
  size = grid.side_length
  unless ARGV[0].include?('http') && ARGV[0].include?('sgtatham')
    puts grid.to_sgtatham
    puts "press enter when ready for #{size}"
    _ = STDIN.gets
  end
end

fill([size], size, grid)

s = (1...size).to_a
puts "press enter when ready for #{s}"
_ = STDIN.gets

fill(s, size, grid)

towers.rb

require_relative 'grid'

verbose = ARGV.delete('-v')
interactive = ARGV.delete('-i')

grid = Grid.from_link_or_file(ARGV[0])

puts grid

stat = Hash.new(0)

while (r = grid.step)
  stat[r[:type]] += 1
  if verbose
    p r
    puts grid
  end
end

# If verbose, we've already printed out the final state.
puts grid if !verbose && !interactive
puts grid.solved? ? 'solvable' : 'unsolvable'
puts stat

if interactive
  grid = Grid.from_link_or_file(ARGV[0])
  while (r = grid.step)
    p r
    puts grid
    _ = STDIN.gets
  end
end