Re: [QUIZ] Pen and Paper (#90)

On Aug 12, 2006, at 5:15 PM, James Edward Gray II wrote:

> In all fairness, I really would love to go back and add the solver,  
> but I am very, very busy this weekend.  :(  We will see if I can  
> steal the time.

I found the time.  Here are some fun timings with it:

$ time ruby grid_fill.rb -s 19
------------------------------------------------------------------------ 
-----
| 203 229 224 204 230 223 209 233 220 210 234 219 211 235 160 194 236  
161 167 |
| 268 174 201 34  173 200 35  172 199 352 171 198 312 170 197 163 169  
196 164 |
| 227 205 38  228 225 60  231 222 69  232 221 70  159 218 71  238 166  
193 237 |
| 202 33  269 207 36  55  208 353 54  213 311 351 212 310 313 195 309  
162 168 |
| 267 175 226 61  39  89  84  59  216 81  68  217 72  75  240 348 74   
239 165 |
| 270 206 37  56  97  65  53  98  66  354 99  79  158 350 78  307 314  
192 308 |
| 49  32  40  90  85  58  215 88  83  214 156 82  241 361 73  242 333  
347 243 |
| 266 176 110 62  52  111 128 64  116 80  67  355 100 76  319 349 77   
306 315 |
| 271 91  50  57  96  134 86  107 155 87  342  3  157 343  4  360 317  
191 334 |
| 48  31  41  112 129 63  115 130 127 17  119 104 320  1  103 303 332  
346 244 |
| 265 177 109 135 51  108 136 133 117 106 154 356 101  6  318 344  5   
305 316 |
| 272 92  45  28  95  143 126 18  148 131 341  2  120 302 331 359 283  
190 335 |
| 47  30  42  113 124 138 114 123 137 16  118 105 321 357 102 304 329  
345 245 |
| 264 178 26  144 44  27  149 132 340 11  153 293 338  7  284 301 336  
250 282 |
| 273 93  46  29  94  142 125 19  147 122 322 15  121 297 330 358 254  
189 328 |
| 182 24  43  290 25  139 291 12  150 292 339 10  285 294 337 251 281  
300 246 |
| 263 179 21  145 261 20  146 141 323 14  152 296 325  8  257 298 327  
249 255 |
| 274 289 183 275 288 184 276 287 185 277 286 186 278 252 187 279 253  
188 280 |
| 181 23  262 180 22  140 260 13  151 259 324  9  258 295 326 248 256  
299 247 |
------------------------------------------------------------------------ 
-----

real    0m0.013s
user    0m0.007s
sys     0m0.005s
$ time ruby grid_fill.rb -s 19
------------------------------------------------------------------------ 
-----
| 282 308 303 283 309 302 288 312 299 289 313 298 290 314 239 273 315  
240 246 |
| 347 253 280 113 252 279 114 251 278 70  250 277 30  249 276 242 248  
275 243 |
| 306 284 117 307 304 139 310 301 148 311 300 149 238 297 150 317 245  
272 316 |
| 281 112 348 286 115 134 287 71  133 292 29  69  291 28  31  274 27   
241 247 |
| 346 254 305 140 118 168 163 138 295 160 147 296 151 154 319 66  153  
318 244 |
| 349 285 116 135 176 144 132 177 145 72  178 158 237 68  157 25  32   
271 26  |
| 128 111 119 169 164 137 294 167 162 293 235 161 320 79  152 321 51   
65  322 |
| 345 255 189 141 131 190 207 143 195 159 146 73  179 155 37  67  156  
24  33  |
| 350 170 129 136 175 213 165 186 234 166 60  82  236 61  83  78  35   
270 52  |
| 127 110 120 191 208 142 194 209 206 96  198 183 38  80  182 21  50   
64  323 |
| 344 256 188 214 130 187 215 212 196 185 233 74  180 85  36  62  84   
23  34  |
| 351 171 124 107 174 222 205 97  227 210 59  81  199 20  49  77   1   
269 53  |
| 126 109 121 192 203 217 193 202 216 95  197 184 39  75  181 22  47   
63  324 |
| 343 257 105 223 123 106 228 211 58  90  232 11  56  86   2  19  54   
329 361 |
| 352 172 125 108 173 221 204 98  226 201 40  94  200 15  48  76  333  
268 46  |
| 261 103 122  8  104 218  9  91  229 10  57  89   3  12  55  330 360  
18  325 |
| 342 258 100 224 340 99  225 220 41  93  231 14  43  87  336 16  45   
328 334 |
| 353  7  262 354  6  263 355  5  264 356  4  265 357 331 266 358 332  
267 359 |
| 260 102 341 259 101 219 339 92  230 338 42  88  337 13  44  327 335  
17  326 |
------------------------------------------------------------------------ 
-----

real    0m0.012s
user    0m0.007s
sys     0m0.005s
$ time ruby grid_fill.rb -s 19
------------------------------------------------------------------------ 
-----
| 139 165 160 140 166 159 145 169 156 146 170 155 147 171 96  130 172  
97  103 |
| 204 110 137 331 109 136 332 108 135 288 107 134 248 106 133 99  105  
132 100 |
| 163 141 335 164 161 357 167 158  5  168 157  6  95  154  7  174 102  
129 173 |
| 138 330 205 143 333 352 144 289 351 149 247 287 148 246 249 131 245  
98  104 |
| 203 111 162 358 336 25  20  356 152 17   4  153  8  11  176 284 10   
175 101 |
| 206 142 334 353 33   1  350 34   2  290 35  15  94  286 14  243 250  
128 244 |
| 346 329 337 26  21  355 151 24  19  150 92  18  177 297  9  178 269  
283 179 |
| 202 112 46  359 349 47  64  361 52  16   3  291 36  12  255 285 13   
242 251 |
| 207 27  347 354 32  70  22  43  91  23  278 300 93  279 301 296 253  
127 270 |
| 345 328 338 48  65  360 51  66  63  314 55  40  256 298 39  239 268  
282 180 |
| 201 113 45  71  348 44  72  69  53  42  90  292 37  303 254 280 302  
241 252 |
| 208 28  342 325 31  79  62  315 84  67  277 299 56  238 267 295 219  
126 271 |
| 344 327 339 49  60  74  50  59  73  313 54  41  257 293 38  240 265  
281 181 |
| 200 114 323 80  341 324 85  68  276 308 89  229 274 304 220 237 272  
186 218 |
| 209 29  343 326 30  78  61  316 83  58  258 312 57  233 266 294 190  
125 264 |
| 118 321 340 226 322 75  227 309 86  228 275 307 221 230 273 187 217  
236 182 |
| 199 115 318 81  197 317 82  77  259 311 88  232 261 305 193 234 263  
185 191 |
| 210 225 119 211 224 120 212 223 121 213 222 122 214 188 123 215 189  
124 216 |
| 117 320 198 116 319 76  196 310 87  195 260 306 194 231 262 184 192  
235 183 |
------------------------------------------------------------------------ 
-----

real    0m0.012s
user    0m0.007s
sys     0m0.005s

It even always gets the bonus points for the circular solution.   
<laughs>

OK, I admit finding circular solutions on the big boards sucks.  ;)

Here's the code:

#!/usr/bin/env ruby -w

require "enumerator"

class PenAndPaperGame
   def self.circular_solutions
     @circular ||= if File.exist?("circular_solutions.dump")
       File.open("circular_solutions.dump") { |file| Marshal.load 
(file) }
     else
       Array.new
     end
   end

   def initialize(size)
     @size    = size
     @largest = @size * @size

     @grid = Array.new(@largest)
   end

   def solve
     if self.class.circular_solutions[@size].nil?
       solve_manually
     else
       @grid  = self.class.circular_solutions[@size]
       offset = @grid[rand(@grid.size)]
       @grid.map! { |n| (n + offset) % @largest + 1 }
       to_s
     end
   end

   def solve_manually
     x, y  = rand(@size), rand(@size)
     count = mark(x, y)

     loop do
       to = jumps(x, y)
       return self.class.new(@size).solve_manually if to.empty?

       scores    = rate_jumps(to)
       low       = scores.min
       next_jump = to.enum_for(:each_with_index).select do |jump|
         scores[jump.last] == low
       end.sort_by { rand }.first.first

       count = mark(*(next_jump + [count]))
       x, y  = next_jump

       if count > @largest
         if circular?
           self.class.circular_solutions[@size] = @grid
           File.open("circular_solutions.dump", "w") do |file|
             Marshal.dump(self.class.circular_solutions, file)
           end
           return to_s
         else
           puts "Found this solution:"
           puts to_s
           puts "Continuing search for a circular solution..."
           return self.class.new(@size).solve_manually
         end
       end
     end
   end

   def to_s
     width  = @largest.to_s.size
     border = " -" + (["-" * width] * @size).join("-") + "- \n"

     border +
     @grid.enum_for(:each_slice, @size).inject(String.new) do |grid,  
row|
       grid + "| " + row.map { |n| n.to_s.center(width) }.join(" ") +  
" |\n"
     end +
     border
   end

   private

   def at(x, y)
     x + y * @size
   end

   def mark(current_x, current_y, mark = 1)
     @grid[at(current_x, current_y)] = mark
     mark + 1
   end

   def jumps(from_x, from_y, grid = @grid)
     [ [-3,  0],
       [3,   0],
       [0,  -3],
       [0,   3],
       [2,   2],
       [-2,  2],
       [2,  -2],
       [-2, -2] ].map do |jump|
       [from_x + jump.first, from_y + jump.last]
     end.select do |jump|
       jump.all? { |to| (0...@size).include? to } and grid[at 
(*jump)].nil?
     end
   end

   def rate_jumps(choices)
     choices.map { |jump| jumps(*jump).size }
   end

   def circular?
     grid = @grid.dup
     grid[grid.index(@largest)] = nil

     x, y = grid.index(1).divmod(@size).reverse

     not jumps(x, y, grid).empty?
   end
end

if __FILE__ == $PROGRAM_NAME
   size = ARGV.first && ARGV.first =~ /\A-s(?:ize)?\Z/ ?  
ARGV.last.to_i : 5
   puts PenAndPaperGame.new(size).solve
end

__END__

James Edward Gray II