From: Elliot Temple <curi@...>
Date: 2006-08-14T00:52:41+09:00
Subject: [Solution] (2)  [QUIZ] Pen and Paper (#90)

Here is my second solution.

Timings are on bottom but include size=15000 in under 5min. The way  
this works is it starts with two solved 5x5 games with special  
properties (end in center, and start on either the middle of the top,  
or the middle of the left side -- pretty print them if that's  
confusing). it then places as many of those as needed to fill the  
entire board. it also has to deal with incrementing the numbers in  
the original 2 patterns. i included some test code which makes sure  
the final solution is valid.

The way placing the 5x5 pre-solved patterns works is i make a column  
with a "left" on top and all the rest are the "up" variety. moving  
from the middle of a 5x5 grid straight down takes you one square off  
the grid, to they line up and all connect. now we're in the middle of  
the bottom 5x5 pattern, so what we need is to move right and have  
that transition to the next pattern, and then go back up to the top,  
then back down again, etc to get the second variety of column which  
goes back up, i just reversed the rows in the first column. before  
combining the columns for the final solution, they are transposed to  
be rows so I can just use +

maybe a better way to get a feel for how it works is to set the size  
to 10 or 15 and pp the solution. then scan the answer for  
1,25,26,50,51,75 etc to see how it's laid out



require "pp"
s = ARGV[0].to_i

if s <= 0
   s = 165
end

if s % 5 != 0
   puts "Invalid Input. Must be multiple of 5."
   exit
end

Left = [[17, 9, 2, 18, 24], [4, 14, 22, 7, 13], [1, 19, 25, 10, 20],  
[16, 8, 3, 15, 23], [5, 11, 21, 6, 12]]

Up = [[17, 4, 1, 16, 5], [9, 14, 19, 8, 11], [2, 22, 25, 3, 21], [18,  
7, 10, 15, 6], [24, 13, 20, 23, 12]]

num = s / 5
$items_in_a_column = 25 * num

$inc_col_count = -$items_in_a_column
def inc_col m
   $inc_col_count += $items_in_a_column
   m.map { |e| e.map { |e2| e2 + $inc_col_count} }
end

$inc_count = 0
def inc m
   $inc_count += 25
   m.map { |e| e.map { |e2| e2 + $inc_count} }
end

col = Left
(num-1).times do |j|
   col += inc(Up)
end

col2 = col.reverse.transpose
col = col.transpose

sol = []

(num/2).times {sol +=  inc_col(col) + inc_col(col2)}

if num % 2 == 1
   sol += inc_col(col)
end

# pp sol

# =========
# = tests =
# =========



Connections = [
[3,0],
[-3,0],
[0,3],
[0,-3],
[2,2],
[2,-2],
[-2,2],
[-2,-2]
]

def check_valid_movement m
   flat = m.flatten
   n = flat.length
   rt_n = Math.sqrt(n).to_i
   1.upto(n-1) do |i|
     a = flat.index i
     b = flat.index i+1
     fail "num not found #{i}" if a.nil? or b.nil?
     x1 = a % rt_n
     y1 = a / rt_n
     x2 = b % rt_n
     y2 = b / rt_n
     move = [x1-x2, y1-y2]
     return false unless Connections.include? move
   end
   true
end

if true # warning: SLOW. took 9 minutes with size = 265. it's n^4 if  
you treat the input number as n.
   fail "dups" unless sol.flatten.uniq.length == sol.flatten.length
   fail "invalid moves" unless check_valid_movement(sol)
   puts "valid moves!"
end



__END__

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 10000

real    1m34.483s
user    1m29.471s
sys     0m3.695s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 15000

real    4m47.336s
user    4m30.390s
sys     0m11.935s

cg5:~/cs/rb/quizzes >time ruby 90take3.rb 25000

real    23m0.525s
user    21m47.343s
sys     0m50.721s

26700 = gave up after 45min, incomplete. 30000 = gave up after 3  
hours, incomplete.