Lonpos Pyramid

lonpos.rb

class Piece
  def self.from_strs(*strs, **opts)
    new strs.map { |s| s.chars.map { |c| c == "*" } }, **opts
  end

  attr_reader :rows, :graphic

  def initialize(rows, graphic:)
    @graphic, @rows = graphic, rows.map do |row|
      row.map { |cell| cell == true ?  graphic : (cell || nil) }
    end
  end

  def solve(pieces, &block)
    position = first_empty_position
    return self unless position
    raise "wtf?" if pieces.empty?
    pieces.each do |piece|
      new_pieces = pieces.dup
      new_pieces.delete piece
      piece.each_orientation do |oriented|
        next unless can_lay? oriented, oriented.y_offset, position
        board = lay oriented, oriented.y_offset, position
        block.call board, new_pieces if block
        solved = board.solve new_pieces, &block
        return solved if solved
      end
    end
    nil
  end

  def inspect
    rows.map { |row|
      row.map { |graphic| "\e[0m" << (graphic || ".") << " " }.join("") << "\e[0m\n"
    }.join("")
  end

  def first_empty_position
    rows.first.size.times do |x|
      rows.size.times do |y|
        return({ x: x, y: y }) unless rows[y][x]
      end
    end
    nil
  end

  def each_square
    return to_enum __method__ unless block_given?
    rows.each_with_index do |row, y|
      row.each_index { |x| yield x: x, y: y }
    end
  end

  def can_lay?(piece, y_offset, position)
    base_x = position[:x]
    base_y = y_offset + position[:y]
    piece.each_block.all? do |x:, y:|
      x += base_x
      y += base_y
      next false if y < 0 || rows.size <= y
      row = rows[y]
      next false if row.size <= x
      !row[x]
    end
  end

  def y_offset
    rows.each_with_index.each { |row, y| return -y if row[0] }
    raise "uhm..."
  end

  def each_block
    return to_enum __method__ unless block_given?
    each_square { |position| yield position if self[position] }
  end

  def [](x:, y:)
    rows[y][x]
  end

  def lay(piece, y_offset, x:, y:)
    new_rows = rows.map(&:dup)
    base_x = x
    base_y = y + y_offset
    piece.each_block { |x:, y:| new_rows[base_y + y][base_x + x] = piece.graphic }
    new new_rows
  end

  def each_orientation
    return to_enum __method__ unless block_given?
    @orientations ||= begin
      flip   = lambda { |rows| rows.map { |row| row.reverse } }
      rotate = lambda { |rows| flip[rows.transpose] }
      [ rows,
        rotate[rows],
        rotate[rotate[rows]],
        rotate[rotate[rotate[rows]]],
        flip[rows],
        rotate[flip[rows]],
        rotate[rotate[flip[rows]]],
        rotate[rotate[rotate[flip[rows]]]],
      ].uniq
    end
    @orientations.each { |oriented| yield new oriented }
  end

  def new(rows, graphic: graphic())
    self.class.new rows, graphic: graphic
  end
end

board480 = Piece.from_strs(
  "***********",
  "__*______*_",
  "___________",
  "___________",
  "___________",
  graphic: "\e[48;2;0;0;0;37m.",
)

board21 = Piece.from_strs(
  "*******____",
  "*****______",
  "****_______",
  "****_______",
  "******_____",
  graphic: "\e[48;2;0;0;0;37m.",
)

pieces = [
  Piece.from_strs(
    "***",
    "*  ",
    "*  ",
    graphic: "\e[48;2;0;255;255;30mG",
  ),
  Piece.from_strs(
    "****",
    "*   ",
    graphic: "\e[48;2;0;0;255;37mC",
  ),
  Piece.from_strs(
    " * ",
    "***",
    " * ",
    graphic: "\e[48;2;200;200;200;30mL",
  ),
  Piece.from_strs(
    "**",
    "**",
    graphic: "\e[48;2;100;255;0;30mK",
  ),
  Piece.from_strs(
    "***",
    "** ",
    graphic: "\e[48;2;255;0;0;37mB",
  ),
  Piece.from_strs(
    " **",
    "** ",
    "*  ",
    graphic: "\e[48;2;255;100;200;37mH",
  ),
  Piece.from_strs(
    "**",
    "* ",
    graphic: "\e[48;2;255;255;255;30mF",
  ),
  Piece.from_strs(
    "***",
    "* *",
    graphic: "\e[48;2;255;255;0;30mI",
  ),
  Piece.from_strs(
    "*** ",
    "  **",
    graphic: "\e[48;2;0;150;0;37mE",
  ),
]

def show_solution(description, board, pieces)
  start = Time.new
  count = 0
  solved = board.solve pieces do |intermediate_board, pieces|
    count += 1
    next
    inspections = pieces.map(&:inspect)
    num_lines = inspections.map { |i| i.lines.size }.max
    inspected_lines = inspections.map! do |inspections|
      lines = inspections.lines.map(&:chomp)
      width = lines.first.gsub(/\e\[[^m]*m/, '').size
      lines << "\e[0m "*width while lines.size < num_lines
      lines
    end
    puts inspected_lines.transpose.map { |segments| segments.join(" | ") }.join("\n")
    p intermediate_board
    gets
  end
  duration = Time.new - start

  printf "===== Solved %s in %0.2f seconds in %d steps =====\n", description, duration, count
  puts solved.inspect.gsub(/^/, "  ")
end


show_solution 'board #21', board21, pieces.take(6)
show_solution 'board #480', board480, pieces