devquiz2011スライドパズル用コード

ext_array.rb

# -*- coding: utf-8 -*-
class Array

  def point(x, y)
    self[y][x]
  end

  def set_point(x, y, char)
    self[y][x] = char
    self
  end

  def find_zero
    each_with_index do |ary, y|
      x = ary.find_index '0'
      if x
        return [x, y]
      end
    end
  end

  def find_char(char)
    each_with_index do |ary, y|
      x = ary.find_index char
      if x
        return [x, y]
      end
    end
    nil
  end

  def up
    zero_x, zero_y = find_zero
    return false if zero_y == 0
    char = point(zero_x, zero_y - 1)
    return false if char == '='
    ary = Marshal.load(Marshal.dump(self))
    ary.set_point(zero_x, zero_y, char)
    ary.set_point(zero_x, zero_y - 1, '0')
    ary
  end

  def down
    zero_x, zero_y = find_zero
    return false if zero_y >= self.size - 1
    char = point(zero_x, zero_y + 1)
    return false if char == '='
    ary = Marshal.load(Marshal.dump(self))
    ary.set_point(zero_x, zero_y, char)
    ary.set_point(zero_x, zero_y + 1, '0')
    ary
  end

  def right
    zero_x, zero_y = find_zero
    return false if zero_x >= self.first.size - 1
    char = point(zero_x + 1, zero_y)
    return false if char == '='
    ary = Marshal.load(Marshal.dump(self))
    ary.set_point(zero_x, zero_y, char)
    ary.set_point(zero_x + 1, zero_y, '0')
    ary
  end

  def left
    zero_x, zero_y = find_zero
    return false if zero_x == 0
    char = point(zero_x - 1, zero_y)
    return false if char == '='
    ary = Marshal.load(Marshal.dump(self))
    ary.set_point(zero_x, zero_y, char)
    ary.set_point(zero_x - 1, zero_y, '0')
    ary
  end

  def check
    valid_row = '123456789' + ('A'..'Z').to_a.join
    str = self.flatten.join
    if str[-1] == '0'
      str.chop!
    else
      return false
    end

    (0...str.length).all? do |i|
      str[i] == '=' || str[i] == valid_row[i]
    end
  end

  def check_top
    valid_row = '123456789' + ('A'..'Z').to_a.join
    str = self[0].join
    (0...str.length).all? do |i|
      str[i] == '=' || str[i] == valid_row[i]
    end
  end

  def check_left
    valid_row = '123456789' + ('A'..'Z').to_a.join
    w = self[0].length
    str = map {|ary| ary[0] }.join
    (0...str.length).all? do |i|
      str[i] == '=' || str[i] == valid_row[i*w]
    end
  end

  def calc
    counter = 0
    valid_row = ('1'..'9').to_a + ('A'..'Z').to_a
    w = self[0].length
    h = self.length
    (0...h).each do |y|
      (0...w).each do |x|
        if po = find_char(valid_row.shift)
          sx = po[0]
          sy = po[1]
          counter += ((x-sx).abs + (y-sy).abs)
        end
      end
    end
    counter
  end

  def cleanup
    c = self.map {|q| q[1].calc }
    border = (c.max + c.min) / 2
    self.delete_if {|q| q[1].calc > border }
    self
  end

end

slide.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

require_relative 'ext_array'
require 'pp'
require 'timeout'

class Slide
  def init
    @problems = File.read 'problems.txt'
    first_line, second_line, @problems = @problems.split("\n", 3)
    @lx, @rx, @ux, @dx = first_line.split(' ').map(&:to_i)
    n = second_line.to_i
  end

  def solve(body)
    @queue = []
    @cache = []
    seek_and_enq '', body
    begin
      timeout(30) do
      loop do
        if answer = seek_and_enq(*deq)
          pp answer
          return answer
        end
        if @queue.size >= 5000
          @queue.cleanup
          # puts '--------------------------------clean up!-----------------------------------------'
        end
      end
      end
    rescue Timeout::Error
      puts 'timeout'
    end
    ''
  end

  def seek_and_enq(str, body)
    # puts "#{str} queue size:#{@queue.size}"

=begin
    if @cache.include? body
      puts 'hit cache'
      return false
    end

    @cache.push body

    if @cache.size > 10_000_000
      @cache.shift
    end
=end

    if @w > 3 && body.check_top
      puts 'top is complete'
      @queue = []
      @w = 3
    elsif @h > 3 && body.check_left
      puts 'left is complete'
      @queue = []
      @h = 3
    end

    if str[-1] != 'D' && up = body.up
      if up.check
        pp up
        return str + 'U'
      else
        @queue.push([str + 'U', up])
      end
    end

    if str[-1] != 'U' && down = body.down
      if down.check
        pp down
        return str + 'D'
      else
        @queue.push([str + 'D', down])
      end
    end

    if str[-1] != 'L' && right = body.right
      if right.check
        pp right
        return str + 'R'
      else
        @queue.push([str + 'R', right])
      end
    end

    if str[-1] != 'R' && left = body.left
      if left.check
        pp left
        return str + 'L'
      else
        @queue.push([str + 'L', left])
      end
    end
    false
  end

  def deq
    @queue.shift
  end

  def start
    counter = 1
    open('answer.txt', 'w') do |answer|
      @problems.each_line do |line|
        @w, @h, b = line.split(',')
        @w = @w.to_i
        @h = @h.to_i
        body = b.scan(/[0-9A-Z=]{#{@w}}/).map { |string| string.split('') }
        puts "trying w:#{@w}, h:#{@h}"
        as = solve(body)
        unless as.empty?
          puts "solved number:#{counter}"
          @ux -= as.count('U')
          @dx -= as.count('D')
          @rx -= as.count('R')
          @lx -= as.count('L')
          puts "U:#{@ux}, D:#{@dx}, R:#{@rx}, L:#{@lx}"
          counter += 1
        end
        answer.puts(as)
      end
    end
  end
end

slide = Slide.new
slide.init
slide.start

test_ext_array.rb

require 'test/unit'
require_relative 'ext_array'

class Test_Array < Test::Unit::TestCase

  def test_point
    ary = [['1', '8', '3'],
           ['4', '2', '5'],
           ['9', '0', '7']]
    assert_equal ary.point(1, 2), '0'
  end

  def test_set_point
    ary = [['1', '8', '3'],
           ['4', '2', '5'],
           ['9', '0', '7']]
    assert_equal(ary.set_point(1, 2, '='), [['1', '8', '3'],['4', '2', '5'],['9', '=', '7']])
  end

  def test_find_zero
    ary = [['1', '8', '3'],
           ['4', '2', '5'],
           ['9', '0', '7']]
    assert_equal ary.find_zero, [1, 2]
  end

  def test_find_char
    ary = [['1', '8', '3'],
           ['4', '2', '5'],
           ['9', '0', '7']]
    assert_equal ary.find_char('5'), [2, 1]
  end

  def test_find_char_when_nothing
    ary = [['2', 'B', '3', '='],
           ['=', '6', '7', '8'],
           ['=', '1', 'A', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal ary.find_char('5'), nil
  end


  def test_up
    ary = [['1', '4', '3'],
           ['=', '2', '5'],
           ['8', '0', '7']]
    assert_equal(ary.up, [['1', '4', '3'],
                          ['=', '0', '5'],
                          ['8', '2', '7']])
  end

  def test_up_when_zero_is_top
    ary = [['1', '0', '3'],
           ['4', '2', '5'],
           ['9', '8', '7']]
    assert_equal(ary.up, false)
  end

  def test_up_when_equal_is_above_zero
    ary = [['1', '4', '3'],
           ['=', '2', '5'],
           ['0', '8', '7']]
    assert_equal(ary.up, false)
  end

  def test_down
    ary = [['1', '4', '3'],
           ['=', '0', '5'],
           ['8', '2', '7']]
    assert_equal(ary.down, [['1', '4', '3'],
                            ['=', '2', '5'],
                            ['8', '0', '7']])
  end

  def test_down_when_zero_is_bottom
    ary = [['1', '8', '3'],
           ['4', '2', '5'],
           ['9', '0', '7']]
    assert_equal(ary.down, false)
  end

  def test_up_when_equal_is_under_zero
    ary = [['1', '4', '3'],
           ['0', '2', '5'],
           ['=', '8', '7']]
    assert_equal(ary.down, false)
  end

  def test_right
    ary = [['1', '4', '3'],
           ['=', '0', '5'],
           ['8', '2', '7']]
    assert_equal(ary.right, [['1', '4', '3'],
                            ['=', '5', '0'],
                            ['8', '2', '7']])
  end

  def test_right_when_zero_is_right_edge
    ary = [['1', '8', '3'],
           ['4', '2', '0'],
           ['9', '5', '7']]
    assert_equal(ary.right, false)
  end

  def test_up_when_equal_is_right_of_zero
    ary = [['1', '4', '3'],
           ['0', '=', '5'],
           ['2', '8', '7']]
    assert_equal(ary.right, false)
  end

  def test_left
    ary = [['1', '4', '3'],
           ['9', '0', '5'],
           ['8', '2', '7']]
    assert_equal(ary.left, [['1', '4', '3'],
                            ['0', '9', '5'],
                            ['8', '2', '7']])
  end

  def test_left_when_zero_is_left_edge
    ary = [['1', '8', '3'],
           ['0', '2', '4'],
           ['9', '5', '7']]
    assert_equal(ary.left, false)
  end

  def test_up_when_equal_is_left_of_zero
    ary = [['1', '4', '3'],
           ['=', '0', '5'],
           ['2', '8', '7']]
    assert_equal(ary.left, false)
  end

  def test_check_when_array_is_valid
    ary = [['1', '2', '3', '='],
           ['=', '6', '7', '8'],
           ['=', 'A', 'B', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.check, true)
  end

  def test_check_when_array_is_invalid1
    ary = [['0', '2', '3', '='],
           ['=', '4', '5', '6'],
           ['=', '7', '8', '9'],
           ['A', 'B', '=', '1']]
    assert_equal(ary.check, false)
  end

  def test_check_when_array_is_invalid2
    ary = [['A', '2', '3', '='],
           ['=', '4', '5', '6'],
           ['=', '7', '8', '9'],
           ['1', 'B', '=', '0']]
    assert_equal(ary.check, false)
  end

  def test_check_top_when_valid
    ary = [['1', '2', '3', '='],
           ['=', '7', '6', '8'],
           ['=', 'A', 'B', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.check_top, true)
  end

  def test_check_top_when_invalid
    ary = [['2', '1', '3', '='],
           ['=', '6', '7', '8'],
           ['=', 'A', 'B', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.check_top, false)
  end

  def test_check_left_when_valid
    ary = [['1', '2', '3', '='],
           ['=', '7', '6', '8'],
           ['=', 'A', 'B', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.check_left, true)
  end

  def test_check_left_when_invalid
    ary = [['2', '1', '3', '='],
           ['=', '6', '7', '8'],
           ['=', 'A', 'B', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.check_left, false)
  end

  def test_calc
    ary = [['2', 'B', '3', '='],
           ['=', '6', '7', '8'],
           ['=', '1', 'A', 'C'],
           ['D', 'E', '=', '0']]
    assert_equal(ary.calc, 8)
  end

end