signpost.rb

# https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/signpost.html
# This should work on every single puzzle generated,
# because this solver uses the same reasoning as that used by the generator to check for solvability:
# check for cells with only a single possible successor or a single possible predecessor.
#
# There are other techniques that can be used:
# * Search with distance > 1, for example check which cell will eventually allow 24 to connect to 27.
# * Naked groups and hidden groups:
#   * If N preds have N succs as their only possible succs, discard all other possible preds from those succs
#   * If N succs have N preds as their only possible preds, discard all other possible succs from those preds
# However, since they have not proven to be necessary, will not write them at this time.
#
# https://www.janko.at/Raetsel/Pfeilpfad/index.htm

require 'set'

class Grid
  ARROW = {
    [-1, 0] => ?↑,
    [-1, 1] => ?↗,
    [0, 1] => ?→,
    [1, 1] => ?↘,
    [1, 0] => ?↓,
    [1, -1] => ?↙,
    [0, -1] => ?←,
    [-1, -1] => ?↖,
  }.each_key(&:freeze).each_value(&:freeze).freeze

  def self.from_link(link)
    link.include?('janko.at') ? from_janko(link) : from_sgtatham(link)
  end

  def self.from_sgtatham(link)
    # Example string:
    # (url)#5x5:1cee8egccfgh20ccbehechgaach9b25a
    # since each grid cell must have an arrow,
    # there must be one letter for each cell.
    # It's prefixed by a number if there is one.
    l, str = link.split(?#, 2)
    str ||= l
    size_str, grid_str = str.split(?:, 2)
    w_str, h_str = size_str.split(?x, 2)
    width = Integer(w_str)
    height = Integer(h_str)
    size = width * height
    letters = grid_str.scan(/(\d+)?([a-h])/)
    raise "bad letters #{letters.size}, need #{size} "if letters.size != size

    # a is up, subsequent letters go clockwise around
    # expressed as dy, dx
    dir = {
      ?a => [-1, 0],
      ?b => [-1, 1],
      ?c => [0, 1],
      ?d => [1, 1],
      ?e => [1, 0],
      ?f => [1, -1],
      ?g => [0, -1],
      ?h => [-1, -1],
    }.each_value(&:freeze).freeze

    Grid.new(letters.map.with_index { |(number, letter), i|
      number = number && Integer(number)
      Cell.new(number && Integer(number), dir.fetch(letter), i.divmod(width), last: number == size)
    }.each_slice(width).to_a.each(&:freeze).freeze)
  end

  def self.from_janko(link)
    lines = `curl #{link}`.lines
    problem = false
    side_length = nil
    grid = []

    dir = {
      ?n => [-1, 0],
      'ne' => [-1, 1],
      ?e => [0, 1],
      'se' => [1, 1],
      ?s => [1, 0],
      'sw' => [1, -1],
      ?w => [0, -1],
      'nw' => [-1, -1],
    }.each_value(&:freeze).freeze

    regexp = /(\d+)?(#{Regexp.union(*dir.keys)})?\b/

    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.chomp == 'problem'
        problem = true
        next
      elsif l.chomp == 'solution'
        break
      end

      grid << l.scan(regexp).select { _1.any? }.map.with_index { |(number, letter), x|
        n = number && Integer(number)
        # Ending square has no direction, just choose any one
        direction = n == side_length * side_length ? [-1, 0] : dir.fetch(letter)
        Cell.new(n, direction, [grid.size, x], last: n == side_length * side_length)
      }.freeze if problem
    }

    Grid.new(grid.freeze)
  end

  def initialize(grid)
    @grid = grid.each(&:freeze).freeze
    @height = grid.size
    @width = grid[0].size
    @size = @height * @width

    @grid.each_with_index { |row, y|
      row.each_with_index { |cell, x|
        dy, dx = cell.direction
        ny = y + dy
        nx = x + dx
        while (0...@height).cover?(ny) && (0...@width).cover?(nx)
          neigh = @grid[ny][nx]
          cell.possible_succ(neigh)
          # OPT: Can simply not make these links,
          # but doesn't seem necessary; let Cell#legal_succ? handle it.
          #if (na = cell.number) && (nb = neigh.number) && na + 1 != nb
          #  puts "debug: #{na} + 1 isn't #{nb}, no link"
          #else
          #  cell.possible_succ(neigh)
          #end
          ny += dy
          nx += dx
        end
      }
    }

    @flat_cells = @grid.flatten
    @flat_cells.each(&:freeze_possibilities)

    @by_number = {}

    @flat_cells.each { |cell|
      @by_number[cell.number] = cell if cell.number
    }

    (1..@size).each_cons(2) { |a, b|
      next unless (ca = @by_number[a])
      next unless (cb = @by_number[b])
      ca.succ = cb
    }

    @by_group_name = {}
    @highlight_cells = []

    @stat = Hash.new(0)
  end

  def stat
    @stat.dup
  end

  def solved?
    @flat_cells.all?(&:number)
  end

  def step(verbose: false)
    @flat_cells.each { |cell|
      next unless (succ = cell.deduce_succ(nil))
      puts "new succ #{cell.pos} -> #{succ.pos}" if verbose
      @stat[:single_succ_1] += 1

      bookkeep_links(cell, succ)

      return true
    }

    @flat_cells.each { |cell|
      next unless (pred = cell.deduce_pred(nil))
      puts "new pred #{pred.pos} -> #{cell.pos}" if verbose
      @stat[:single_pred_1] += 1

      bookkeep_links(pred, cell)

      return true
    }

    @flat_cells.each { |cell|
      next unless cell.number
      next if cell.number == @size

      next unless (succ = cell.deduce_succ(closest_succ(cell)))
      puts "new succ #{cell.pos} -> #{succ.pos} (took closest into account)" if verbose
      @stat[:single_succ_1_closest] += 1

      bookkeep_links(cell, succ)

      return true
    }

    @flat_cells.each { |cell|
      next unless cell.number
      next if cell.number == 1

      next unless (pred = cell.deduce_pred(closest_pred(cell)))
      puts "new pred #{pred.pos} -> #{cell.pos} (took closest into account)" if verbose
      @stat[:single_pred_1_closest] += 1

      bookkeep_links(pred, cell)

      return true
    }

    false
  end

  def closest_succ(cell)
    num = ((cell.number + 1)..@size).find(&@by_number)
    @by_number[num]
  end

  def closest_pred(cell)
    num = (cell.number - 1).downto(1).find(&@by_number)
    @by_number[num]
  end

  def bookkeep_links(pred, succ, highlight: true)
    pred_had_number = !!pred.number
    succ_had_number = !!succ.number

    g1, g2 = [pred.group, succ.group]
    @highlight_cells = [pred, succ] if highlight
    pred.succ = succ
    new_group = succ.group
    @by_group_name.delete(g1.name) if g1.can_free_name?
    @by_group_name.delete(g2.name) if g2.can_free_name?
    new_group.name = unused_group_name if !new_group.number && !new_group.name
    @by_group_name[new_group.name] = new_group if new_group.name

    pred.succs.each { @by_number[_1.number] = _1 } if pred_had_number && !succ_had_number
    succ.preds.each { @by_number[_1.number] = _1 } if succ_had_number && !pred_had_number

    if new_group.number
      if (succ = @by_number[new_group.last.number + 1]) && succ.group != new_group
        bookkeep_links(new_group.last, succ, highlight: false)
      end
      if (pred = @by_number[new_group.first.number - 1]) && pred.group != new_group
        bookkeep_links(pred, new_group.first, highlight: false)
      end
    end
  end

  def unused_group_name
    (?a..).find { !@by_group_name[_1] }
  end

  GROUP_COLOUR = [
    '216;30',
    '48;30',
    '14;30',
    '93',
    '202;30',
    '74;30',
    '11;30',
    '224;30',
    '144;30',
    # Really hard to tell the difference between j and b
    '79;30',
    # Really hard to tell the difference between k and f
    '32',
    '94',
    # Colours past here (l) are mostly untested
    # Really hard to tell the difference between m and i
    '180;30',
    '155;30',
    '228;30',
    # Starting with p, it loops back to a's colour
  ].each(&:freeze).freeze

  def to_s
    max_num_size = (@height * @width).to_s.size
    # no support for > z letters, so just one letter
    # x + n
    cell_to_s_size = max_num_size + 4

    highlight_poses = Set.new(@highlight_cells.map(&:pos))

    lines = @grid.map.with_index { |row, y|
      cell_strs = row.map.with_index { |cell|
        colour = if cell.number
          '30;47'
        elsif cell.group.name
          idx = cell.group.name.ord - ?a.ord
          "48;5;#{GROUP_COLOUR[idx % GROUP_COLOUR.size]}"
        else
          40
        end
        n = "\e[#{colour}m%#{cell_to_s_size}s\e[0m" % cell
        "#{n} #{cell.need_pred? ? ?P : ' '}#{cell.need_succ? ? ?S : ' '}\e[1m#{cell.number == @size ? '★' : ARROW.fetch(cell.direction)}\e[0m"
      }
      # intersperse dividing bars, possibly highlighted
      dividing_bars = (@width + 1).times.map { |x|
        if highlight_poses.include?([y, x]) || highlight_poses.include?([y, x - 1])
          " \e[1;32m|\e[0m "
        else
          ' | '
        end
      }
      lines = dividing_bars.zip(cell_strs).join
      lines[1..]
    }
    # plus space, arrow, PS indicators
    # plus one space of padding on each side, plus the vertical bar
    cell_size = cell_to_s_size + 7
    # intersperse dividing lines, possibly highlighted
    dividing_lines = (@height + 1).times.map { |y|
      @width.times.map { |x|
        div = ?- * (cell_size - 1)
        if highlight_poses.include?([y, x]) || highlight_poses.include?([y - 1, x])
          "-\e[1;32m#{div}\e[0m"
        else
          ?- + div
        end
      }.join + ?-
    }
    lines = dividing_lines.zip(lines).flatten
    lines.pop
    lines.join("\n")
  end
end

class Cell
  attr_reader :number, :direction, :pos
  attr_reader :pred, :succ
  attr_reader :group, :offset

  def initialize(number, direction, pos, last: false)
    @number = number
    @direction = direction.freeze
    @pos = pos.freeze
    @group = Group.new(self)
    @offset = nil
    # pred and succ:
    # if known, singular form non-nil.
    # if not known, singular form nil, possible_Xs contains the possibilites
    @pred = nil
    @succ = nil
    @possible_preds = Set.new
    @possible_succs = Set.new
    @possibilities_frozen = false
    @last = last
  end

  def possibilities_frozen?
    @possibilities_frozen
  end

  def need_pred?
    @pred.nil? && @number != 1
  end

  def need_succ?
    @succ.nil? && !@last
  end

  def to_s
    @number&.to_s || "#{@group.name}#{"+#{@offset}" if @offset &.> 0}"
  end

  def deduce_pred(closest_pred, dist = 1)
    return unless need_pred?
    raise "dist other than 1 not supported yet" if dist != 1
    # OPT: Can remember false answers to legal_succ? and remove them permanently.
    legal_preds = @possible_preds.select { _1.legal_succ?(self, closest_pred: closest_pred) }
    raise "no legal pred for #{self}" if legal_preds.empty?
    return legal_preds.first if legal_preds.size == 1
  end

  def deduce_succ(closest_succ, dist = 1)
    return unless need_succ?
    raise "dist other than 1 not supported yet" if dist != 1
    # OPT: Can remember false answers to legal_succ? and remove them permanently.
    legal_succs = @possible_succs.select { legal_succ?(_1, closest_succ: closest_succ) }
    raise "no legal succ for #{self}" if legal_succs.empty?
    return legal_succs.first if legal_succs.size == 1
  end

  def legal_succ?(succ, closest_pred: nil, closest_succ: nil)
    return false unless need_succ?
    return false unless succ.need_pred?
    return false if (na = @number) && (nb = succ.number) && na + 1 != nb
    # Creating a closed loop
    return false if @group == succ.group

    if closest_pred && succ.number
      # Example: Evaluate whether 3 (succ) can connect to potential 2 (self) when 1 (closest_pred) is known.
      # Example: Evaluate whether 4 (succ) can connect to chain of size two (self = potential 3) when 1 (closest_pred) is known.
      potential_number = succ.number - @group.size
      return false if potential_number <= closest_pred.number
      return false if potential_number == closest_pred.number + 1 && !closest_pred.possible_succs.include?(@group.first)
    end
    if closest_succ && @number
      # Example: Evaluate whether 1 (self) can connect to potential 2 (succ) when 3 (closest_succ) is known.
      # Example: Evaluate whether 1 (succ) can connect to chain of size two (self = potential 2) when 4 (closest_succ) is known.
      potential_number = @number + succ.group.size
      return false if potential_number >= closest_succ.number
      return false if potential_number + 1 == closest_succ.number && !closest_succ.possible_preds.include?(succ.group.last)
    end

    true
  end

  def succ=(x)
    return if x && @succ == x
    raise "#{self} already has succ #{@succ}, can't set to #{x}" if @succ
    raise "#{self} doesn't have #{x} as possible succ" unless @possible_succs.include?(x)

    @succ = x

    x.pred = self
    merged_group = @group.merge(x.group)

    pred_had_number = !!@number
    succ_had_number = !!succ.number

    curr_num = @number
    succs.each { |curr_cell|
      curr_cell.number = curr_num += 1 if pred_had_number && !succ_had_number
      curr_cell.group = merged_group
    }

    curr_num = x.number
    x.preds.each { |curr_cell|
      curr_cell.number = curr_num -= 1 if !pred_had_number && succ_had_number
      curr_cell.group = merged_group
    }

    group.cells.with_index { |cell, offset| cell.offset = offset } unless group.number
  end

  def preds
    curr_cell = self
    Enumerator.new { |y|
      while (curr_cell = curr_cell.pred)
        y << curr_cell
      end
    }
  end

  def succs
    curr_cell = self
    Enumerator.new { |y|
      while (curr_cell = curr_cell.succ)
        y << curr_cell
      end
    }
  end

  def possible_succ(cell)
    raise "possibilities of #{self} are frozen" if @possibilities_frozen
    raise "possibilities of #{cell} are frozen" if cell.possibilities_frozen?
    cell.possible_preds << self
    @possible_succs << cell
  end

  def rm_succ(cell)
    @possible_succs.delete(cell)
  end

  def rm_pred(cell)
    @possible_preds.delete(cell)
  end

  def freeze_possibilities
    @possibilities_frozen = true
  end

  protected

  attr_reader :possible_succs, :possible_preds
  attr_writer :number
  attr_writer :group, :offset

  def pred=(x)
    return if x && @pred == x
    raise "#{self} already has pred #{@pred}, can't set to #{x}" if @pred
    raise "#{self} doesn't have #{x} as possible pred" unless @possible_preds.include?(x)

    @pred = x
    # Do not need to do the other steps of succ=,
    # since external callers only get to call succ=
  end
end

# A little unsatisfied with the visibility of group:
# Cell is exclusively responsible for managing groups,
# but it exposes the group to the outside.
# Maybe the cell should expose the appropriate readers that read the appropriate values of group.
class Group
  attr_accessor :name
  attr_reader :first, :last, :size

  def initialize(first, last = nil, size = 1, name = nil)
    @name = name.freeze
    @first = first
    @last = last || first
    @size = size
    @can_free_name = false
  end

  def can_free_name?
    @can_free_name
  end

  def number
    @first.number
  end

  def merge(succ)
    return self if succ == self

    # If either side has a number, no name needed
    # If only one side has a name, use that one.
    # If both sides have a name, take the name of the larger side.
    new_name = if @first.number || succ.first.number
      @can_free_name = true
      succ.can_free_name = true
      nil
    elsif @name && !succ.name
      @name
    elsif succ.name && !@name
      succ.name
    elsif @size < succ.size
      @can_free_name = true
      succ.name
    else
      succ.can_free_name = true
      name
    end

    self.class.new(@first, succ.last, @size + succ.size, new_name)
  end

  def to_s
    "group size #{size} #{first.number} - #{last.number}"
  end

  def cells
    Enumerator.new { |y|
      curr_cell = @first
      while curr_cell
        y << curr_cell
        curr_cell = curr_cell.succ
      end
    }
  end

  protected

  attr_writer :can_free_name
end

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

link = ARGV[0]

grid = Grid.from_link(link)
puts grid

while grid.step(verbose: verbose)
  puts grid if verbose
end

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

if interactive
  grid = Grid.from_link(link)
  while grid.step(verbose: true)
    puts grid
    _ = STDIN.gets
  end
end

puts grid.stat