codeiq.rb

#! /bin/sh
exec ruby -S -x "$0" "$@"
#! ruby
# 迷路のマス
class Cell
  def initialize(value)
    @value = value

    # どのマスからくるか
    @prev_value = case value
                  when 'A' then 'C'
                  when 'B' then 'A'
                  when 'C' then 'B'
                  end

    # 到達済みか
    @reached = false

    # 探索済みか
    @searched = false
  end

  # あるマスからこのマスに進む
  def walk_from(value)
    if value == @prev_value
      # 到達
      @reached = true
      true
    else
      false
    end
  end

  attr_writer :reached, :searched

  attr_reader :reached, :searched, :value
end

# 迷路
class Maze
  def initialize(lines)
    @lines = lines.map do |line|
      line.map { |cell| Cell.new cell }
    end
    # スタート地点
    self.get_cell(0, 0).reached = true
  end

  def resolve
    self.walk_through
    self.finish? ? 'possible' : 'impossible'
  end

  def walk_through
    self.walk_around 0, 0
    search_points = self.get_reached_cell_around 0, 0

    until search_points.size == 0
      search_points = search_points.map { |xy|
          self.walk_around xy[0], xy[1]
          self.get_reached_cell_around xy[0], xy[1]
        }
        .flatten(1)
        .uniq
      if self.finish?
        return
      end
    end
  end
  protected :walk_through

  # 上下左右に進めるかフラグをたてる
  def walk_around(x, y)
    me = get_cell(x, y)
    me.searched = true
    self.get_adjacent_points(x, y)
      .map { |xy| self.get_cell xy[0], xy[1] }
      .compact
      .each { |cell| cell.walk_from(me.value) }
  end
  protected :walk_around

  def finish?
    @lines.last.last.reached
  end
  protected :finish?

  def get_cell(x, y)
    return nil if x < 0 or y < 0
    if line = @lines[y]
      line[x]
    elsif
      nil 
    end
  end
  protected :get_cell

  def get_adjacent_points(x, y)
    [
      [x + 1, y    ],
      [x - 1, y    ],
      [x    , y + 1],
      [x    , y - 1],
    ]
  end
  protected :get_adjacent_points

  def get_reached_cell_around(x, y)
    self
      .get_adjacent_points(x, y)
      .select { |xy|
        cell = self.get_cell xy[0], xy[1]
        cell and cell.reached and not cell.searched
      }
  end
  protected :get_reached_cell_around

  def output
    @lines.each do |line|
      line.each do |cell|
        if cell.reached
          print "\e[31m"
        end
        if cell.searched
          print "\e[32m"
        end
        print cell.value
        print "\e[0m"
      end
      print "\n"
    end
  end

  def clear_output
    printf "\e[#{@lines.size}A"
    printf "\e[#{@lines[0].size}D"
  end
  protected :clear_output
end

class Resolver
  def get_from_file(file_name)
    inputs = []
    File.open(file_name, 'r') do |io|
      inputs = io.readlines.map {|line| line.chomp.split ''}
    end
    inputs
  end

  def resolve
    file_name = ARGV[0]
    inputs = self.get_from_file file_name
    maze = Maze.new inputs
    puts maze.resolve
  end

  def resolve_all
    %w( case1.in.txt
        case2.in.txt
        case3.in.txt
        case4.in.txt
        case5.in.txt
        case6.in.txt
        case7.in.txt
    ).each do |file_name|
      inputs = self.get_from_file file_name
      maze = Maze.new inputs
      puts "#{file_name}: #{maze.resolve}"
    end
  end
end

Resolver.new.resolve_all

Maze#walk_around でshould_search がtrueになった者だけ探索するようにしたらもっと早くできる。そのさい無限ループに気をつける

再帰的にかけそう。

walked -> searched, should_walk -> reached とかにすべき

walk は配列のメソッドチェーンで書けそう