Skip to content

Instantly share code, notes, and snippets.

@willnet
Created September 12, 2011 04:10
Show Gist options
  • Save willnet/1210568 to your computer and use it in GitHub Desktop.
Save willnet/1210568 to your computer and use it in GitHub Desktop.
devquiz2011スライドパズル用コード
# -*- 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
#!/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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment