Grid Folding (#63)

[bbazzarrakk]

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz
   until
   48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Matthew M.

You have a square sheet of grid paper, 16 cells across by 16 down. A
number is
written in each cell, starting at 1 in the upper-left corner, going
across each
line then down the paper, ending with 256 in the lower-right corner.

Your task is write a Ruby function to fold the paper in half repeatedly
(along
the horizontal or vertical middle), until you are left with a single
cell, 256
layers thick, and report back on the order of those layers, top to
bottom.

The input to the function is a string containing the characters “T” (the
top
edge folded down to the bottom edge), “B” (bottom up to top), “R” (right
to
left) and “L” (left to right). Not every combination of those will be
valid, so
make sure you verify your input. Output will be an Array of Integers
from 1 to
256, arranged in the top-to-bottom layer order after all folds are done.

To help clarify, here’s a 2x2 example.

+-+-+
|1|2|
+-+-+
|3|4|
+-+-+

fold("RB") => [3, 4, 2, 1]
fold("TL") => [3, 1, 2, 4]
fold("LR") => raise exception for invalid input

Extra credit: Make your fold function take an additional input
parameter(s),
the dimensions of the paper; dimensions should be power-of-2 in order to
fold
down to one cell.

Extra extra credit: Write a method check_fold() that takes the
resulting Array
of Integers from the quiz and returns the transformation String argument
(i.e.
fold(check_fold(final_order)) == final_order).

[bbazzarrakk]

On Fri, Jan 20, 2006 at 10:57:03PM +0900, Ruby Q. wrote:
[…]
} The input to the function is a string containing the characters “T”
(the
} top edge folded down to the bottom edge), “B” (bottom up to top), “R”
} (right to left) and “L” (left to right). Not every combination of
those
} will be valid, so make sure you verify your input.
[…]
} To help clarify, here’s a 2x2 example.
}
} ±±+
} |1|2|
} ±±+
} |3|4|
} ±±+
}
} fold(“RB”) => [3, 4, 2, 1]
} fold(“TL”) => [3, 1, 2, 4]
} fold(“LR”) => raise exception for invalid input

Assuming it is only composed of [LRTB], is there any way in which the
string can be invalid other than too many folds in a particular
dimension?

–Greg

[bbazzarrakk]

Assuming it is only composed of [LRTB], is there any way in which the
string can be invalid other than too many folds in a particular dimension?

Yes… too few folds. The 16x16 (or MxN) paper should be reduced via
folding to a 1x1 stack. Knowing that the input dimensions should be
powers of 2, you can determine the exact number of folds. If the
paper is 16 wide, there should be exactly log2(16) == 4 horizontal
folds.

[bbazzarrakk]

The first extra credit (handling dimensions other than 16x16) is
pretty darn easy, so you may want to start out on a 2x2 to get yer
basics working and move up. With that in mind, here are a few tests
to help verify your work. The test_2x2 tests all possible folding
combinations.

(NOTE: The 16x16 test below is the result of my own solution. I’m
fairly certain it’s correct, but not 100%. So if you run this and
pass the other two tests but fail the 16x16 test, I’d be interested to
see your output and between us figure out what the expected solution
is.)

Oh, and if you have more tests, feel free to share.

require ‘test/unit’
require ‘test/unit/ui/console/testrunner’

class FoldTest < Test::Unit::TestCase
def test_2x2
folds = {“TR” => [4, 2, 1, 3],
“BR” => [2, 4, 3, 1],
“TL” => [3, 1, 2, 4],
“BL” => [1, 3, 4, 2],
“RT” => [1, 2, 4, 3],
“RB” => [3, 4, 2, 1],
“LT” => [2, 1, 3, 4],
“LB” => [4, 3, 1, 2]}

  folds.each do |cmds,xpct|
     assert_equal xpct, fold(2, 2, cmds)
  end

end

def test_16x16
xpct = [189, 77, 68, 180, 196, 52, 61, 205,
204, 60, 53, 197, 181, 69, 76, 188,
185, 73 , 72, 184, 200, 56, 57, 201,
208, 64, 49, 193, 177, 65, 80, 192,
191, 79, 66, 178, 194, 50, 63, 207,
202, 58, 55, 199, 183, 71, 74, 186,
187, 75, 70, 182, 198, 54, 59, 203,
206, 62, 51, 195, 179, 67, 78, 190,
142, 126, 115, 131, 243, 3, 14, 254,
251, 11, 6, 246, 134, 118, 123, 139,
138, 122, 119, 135, 247, 7, 10, 250,
255, 15, 2, 242, 130, 114, 127, 143,
144, 128, 113, 129, 241, 1, 16, 256,
249, 9, 8, 248, 136, 120, 121, 137,
140, 124, 117, 133, 245, 5, 12, 252,
253, 13, 4, 244, 132, 116, 125, 141,
157, 109, 100, 148, 228, 20, 29, 237,
236, 28, 21, 229, 149, 101, 108, 156,
153, 105, 104, 152, 232, 24, 25, 233,
240, 32, 17, 225, 145, 97, 112, 160,
159, 111, 98, 146, 226, 18, 31, 239,
234, 26, 23, 231, 151, 103, 106, 154,
155, 107, 102, 150, 230, 22, 27, 235,
238, 30, 19, 227, 147, 99, 110, 158,
174, 94, 83, 163, 211, 35, 46, 222,
219, 43, 38, 214, 166, 86, 91, 171,
170, 90, 87, 167, 215, 39, 42, 218,
223, 47, 34, 210, 162, 82, 95, 175,
176, 96, 81, 161, 209, 33, 48, 224,
217, 41, 40, 216, 168, 88, 89, 169,
172, 92, 85, 165, 213, 37, 44, 220,
221, 45, 36, 212, 164, 84, 93, 173]
assert_equal xpct, fold(16, 16, “TLBLRRTB”)
end

def test_invalid
assert_raise(RuntimeError) { fold(2, 2, “LR”) } # too many horz
folds
assert_raise(RuntimeError) { fold(2, 2, “TRB”) } # too many folds
assert_raise(RuntimeError) { fold(3, 2, “LR”) } # bad input
dimensions
end

end

Test::Unit::UI::Console::TestRunner.run(FoldTest)

[bbazzarrakk]

On Jan 21, 2006, at 12:47 PM, Chris Turner wrote:

On 1/20/06, Matthew M. [email protected] wrote:

def test_16x16
# …
assert_equal xpct, fold(16, 16, “TLBLRRTB”)
end

Is this right? I was under the impression that the above fold string
is invalid. You shouldn’t be able to fold “RR” or “TB”, as you must
always fold in half. My solution, at least, tells me that.

You can fold a 4x8 sheet of paper in half four ways. Two of them
produce a dimensions 2x8, and two of them produce dimensions 4x4.
You seem to imply that ‘folding in half’ means always produce a
square result, unless the paper is already square.

[bbazzarrakk]

On 1/20/06, Matthew M. [email protected] wrote:

def test_16x16
# …
assert_equal xpct, fold(16, 16, “TLBLRRTB”)
end

Is this right? I was under the impression that the above fold string
is invalid. You shouldn’t be able to fold “RR” or “TB”, as you must
always fold in half. My solution, at least, tells me that.

Chris

[bbazzarrakk]

That’s how I read it. Looking back at the requirements, however, I now
see that the reason “LR” in a 2x2 paper is invalid is for a completely
different reason. Oops.

[bbazzarrakk]

Chris Turner wrote:

That’s how I read it. Looking back at the requirements, however, I now
see that the reason “LR” in a 2x2 paper is invalid is for a completely
different reason. Oops.

I wrote a solution for this quiz yesterday (this will be my first
submission, by the way) and can assure everyone that the tests provided
by Matthew are 100% correct, as I have the same results.

This was a good task, and somewhat hard for me too (I’m a total newbie
after all :-). Maybe that’s because I didn’t find a simple solution and
was forced to just model the situation roughly, without any hacks.

Thanks, Matt!

[bbazzarrakk]

here is my solution, it uses a 3d array to keep track of the stack of
numbers in every location.

class Array
def reverse_each
map {|x| x.reverse}
end
end

def fold(str,w=8,h=8)
grid = Array.new(h) {|y| Array.new(w) {|x| [w*y+x+1] } }
str.each_byte {|c|
grid = case c
when ?R then rightFold(grid)
when ?L then rightFold(grid.reverse_each).reverse_each
when ?B then rightFold(grid.transpose).transpose
when ?T then rightFold(grid.reverse.transpose).transpose.reverse
end
}
raise “invalid folding instructions” unless grid.length == 1 &&
grid[0].length == 1
return grid[0][0]
end

def rightFold(grid)
grid.map { |row|
for ix in 0…row.length/2
row[ix] = row[-ix-1].reverse + row[ix]
end
row[0…row.length/2]
}
end

p fold(“RB”,2,2)
p fold(“TLRBB”,4,8)
p fold(“TLBLRRTB”,16,16)

i tried to use map(&:reverse) for the reverse_each function but that
doesn’t seem to work
irb(main):001:0> require ‘extensions/symbol’
irb(main):002:0> [[1,2,3]].map(&:reverse)
NoMethodError: undefined method `reverse’ for 1:Fixnum

[bbazzarrakk]

Here’s my newbie solution:

class SquareSheet
def initialize(dim_power)
@dim = @cols = @rows = 2**dim_power
@power = dim_power
@order = [] #desired number order
@layers = [[0,0]] #array of layer coordinates
#(relative to the top left corner of the whole sheet)
@origin = [[:top, :left]] #array of layer spatial orientations
end

def opposite(dir)
case dir
when :bottom: :top
when :bottom
when :left: :right
when :right: :left
end
end

def fold(sequence)
raise “Invalid sequence”
unless (sequence.count(“TB”) == @power) &&
(sequence.count(“LR”) == @power)
sequence.split(//).each do |char|
len = @layers.length
case char
when “T”, “B”:
@rows /= 2
for i in 0…len-1 do #in such cases ‘for’ perfoms better than
‘each’
#calculate new orientations and coordinates of each layer
@origin[2len-i-1] = [opposite((@origin[i])[0]),
(@origin[i])[1]]
@layers[2len-i-1] = [(@layers[i])[0], (@layers[i])[1]]
if (@origin[i])[0] == :bottom: (@layers[2len-i-1])[0] +=
@rows
else (@layers[i])[0] += @rows; end
end
@layers.reverse! if char==“B”
when “L”, “R”:
@cols /= 2
for i in 0…len-1 do
@origin[2len-i-1] = [(@origin[i])[0],
opposite((@origin[i])[1])]
@layers[2len-i-1] = [(@layers[i])[0], (@layers[i])[1]]
if (@origin[i])[1] == :right: (@layers[2len-i-1])[1] += @cols
else (@layers[i])[1] += @cols; end
end
@layers.reverse! if char==“R”
end
end
@layers.each {|coord| @order << coord[0]*@dim+coord[1]+1}
return @order.reverse
end
end

#example usage:
#sheet = SquareSheet.new(4) #creates 24 x 24 sheet
#p sheet.fold(“TLBLRRTB”)

[bbazzarrakk]

Here’s my (first ever) solution. For the extra-extra credit, my
sincere thanks go out to Tristan Allwood, who’s solution to the
Numeric Maze I used to check_fold. It is incredibly slow, as it has to
try every possible unfold, but it ends up working.

Chris Turner

folding.rb

---

A few helper methods

def try
begin
yield
rescue
end
end

class Object
def deep_dup
Marshal::load(Marshal.dump(self))
end
end

module Math
def Math.log2(num)
Math.log(num) / Math.log(2)
end
end

class Fixnum
def power_of_2?
power_of_two = 2
begin
return true if power_of_two == self
end while((power_of_two = power_of_two*2) <= self)
false
end
end

First part of solution (plus first extra credit)

class Paper
attr_reader :paper
def initialize(size=16)
raise “Paper size must be power of 2” unless size.power_of_2?
@paper = []
(1…size).each do |h|
@paper.push((((h-1)*size)+1…(((h-1)*size)+size)).to_a)
@paper[-1].map! {|x| [x]}
end
@size = size
self
end

def fold(commands)
size = commands.size
folds_req = Math.log2(@size).to_i*2
raise “Need #{folds_req-size} more folds” if folds_req > size
raise “Have too many folds (by #{size-folds_req})” if folds_req <
size

directions = parse_fold_commands(commands)
directions.each do |direction|
  send(direction)
end
@paper[0][0]

end

def fold_bottom
fold_vert(false)
end

def fold_top
fold_vert(true)
end

def fold_left
fold_horiz(true)
end

def fold_right
fold_horiz(false)
end

private
def parse_fold_commands(commands)
commands.split("").map do |d|
case d.downcase
when “r”
:fold_right
when “l”
:fold_left
when “t”
:fold_top
when “b”
:fold_bottom
else
raise “Invalid command: #{d}”
end
end
end

def fold_two_halves(new_half, old_half)
new_half.each_with_index do |new_row, r_index|
old_row = old_half[r_index]
new_row.each_with_index do |new_col, c_index|
old_col = old_row[c_index]
new_col.unshift(old_col.reverse).flatten!
end
end
end

def fold_vert(top_to_bottom)
check_foldable(:v)
top_half, bottom_half = get_top_and_bottom
new_half, old_half = if top_to_bottom
[bottom_half, top_half]
else
[top_half, bottom_half]
end
old_half = old_half.reverse
fold_two_halves(new_half, old_half)
(@paper.size/2).times do
if top_to_bottom
@paper.shift
else
@paper.pop
end
end
self
end

def fold_horiz(left_to_right)
check_foldable(:h)
left_half, right_half = get_left_and_right
new_half, old_half = if left_to_right
[right_half, left_half]
else
[left_half, right_half]
end
old_half = old_half.map { |x| x.reverse }
fold_two_halves(new_half, old_half)
@paper.each do |row|
(row.size/2).times do
if left_to_right
row.shift
else
row.pop
end
end
end
self
end

def get_top_and_bottom
new_size = @paper.size/2
[@paper[0,new_size], @paper[new_size,new_size]]
end

def get_left_and_right
new_size = @paper[0].size/2
[@paper.map {|x| x[0,new_size]}, @paper.map {|x|
x[new_size,new_size]}]
end

def check_foldable(direction)
if (@paper.size % 2 != 0) || (@paper[0].size % 2 != 0)
raise “Must be foldable” if @paper.size != 1 && @paper[0].size !=
1
end

if direction == :v
  raise "Can't fold this direction" if @paper.size == 1
elsif direction == :h
  raise "Can't fold this direction" if @paper[0].size == 1
end

end
end

def fold(command, size=16)
Paper.new(size).fold(command)
end

if FILE == $0
paper_size = ARGV[0] || 16
p fold(STDIN.gets.chomp, paper_size.to_i)
end

Begin extra extra

credit-----------------------------------------------------------------------------------

class Paper
def unfold(commands)
directions = parse_unfold_commands(commands)
directions.each do |direction|
send(direction)
end
self
end

def reset_to(new_paper)
@paper = new_paper
self
end

def at_start?
if @paper.size == @size and @paper[0].size == @size
catch(:not_correct) do
(0…@size-1).each do |row|
(0…@size-1).each do |col|
throw :not_correct if(@paper[row][col][0] !=
(row*@size)+col+1)
end
end
return true
end
false
end
end

def unfold_to_bottom
check_unfoldable(:v)
@paper.reverse.each do |row|
new_row = []
row.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
new_row.push(new_col)
end
@paper.push(new_row)
end
self
end

def unfold_to_top
check_unfoldable(:v)
me = @paper.dup
me.each do |row|
new_row = []
row.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
new_row.push(new_col)
end
@paper.unshift(new_row)
end
self
end

def unfold_to_left
check_unfoldable(:h)
@paper.each do |row|
row_dup = row.dup
row_dup.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
row.unshift(new_col)
end
end
self
end

def unfold_to_right
check_unfoldable(:h)
@paper.each do |row|
row.reverse.each do |col|
new_col = []
(col.size/2).times { new_col.unshift(col.shift) }
row.push(new_col)
end
end
self
end

private
def parse_unfold_commands(commands)
commands.split("").map do |d|
case d.downcase
when “r”
:unfold_to_right
when “l”
:unfold_to_left
when “t”
:unfold_to_top
when “b”
:unfold_to_bottom
else
raise “Invalid command: #{d}”
end
end
end

def check_unfoldable(direction)
if (@paper.size % 2 != 0) || (@paper[0].size % 2 != 0)
raise “Must be foldable” if @paper.size != 1 && @paper[0].size !=
1
end

raise "Already unfolded" if (@paper[0][0].size == 1)

end
end

def check_fold(ary)
raise “Invalid solution” unless ary.size.power_of_2?
answer_size = Math.sqrt(ary.size).to_i
paper = Paper.new(answer_size).reset_to([[ary.deep_dup]])
try_all(paper, [""])
end

def try_all(start, directions)
n = []
directions.each do |sol|
new_sol = start.deep_dup.unfold(sol)
ufl = ufr = uft = ufb = nil

try { ufl = new_sol.deep_dup.unfold_to_left }
try { ufr = new_sol.deep_dup.unfold_to_right }
try { uft = new_sol.deep_dup.unfold_to_top }
try { ufb = new_sol.deep_dup.unfold_to_bottom }

return (sol + "l").reverse if ufl and ufl.at_start?
return (sol + "r").reverse if ufr and ufr.at_start?
return (sol + "t").reverse if uft and uft.at_start?
return (sol + "b").reverse if ufb and ufb.at_start?

n << (sol + "l") if ufl
n << (sol + "r") if ufr
n << (sol + "t") if uft
n << (sol + "b") if ufb

end
try_all(start, n) if directions.size != 0
end

[bbazzarrakk]

My solution is at
http://users.adelphia.net/~showaltb/rubyquiz/63/fold.rb, made without
peeking at other solutions.

I only did the first extra credit. The extra extra credit looks hard!

[bbazzarrakk]

I didn’t use multidimensional arrays for my solution. I keep track of
where each number is (row, col, position in paper stack) during the
folds and just insert it directly into the final array. The folding code
isn’t as succinct as I’d like it to be with quite a bit of duplication.
Any thoughts on that?

The unfolding function is just magic. I know that’s bad, but I’ll give
my theory as to why it works. So my original plan was to start in the
middle and look at the numbers on the joint of the fold. Check if
they’re in the same row or column to determine if it was a vertical or
horizontal fold and check which number is bigger to determine if it
which side was folded onto the other. This mostly works, but breaks if
there are two folds of the same orientation in a row (ie horizontal
folds: RR, RL, LL, LR). If you look at the end I have it rerun unfold on
the stack generated from folding the new string. This creates the
correct string. As an example lets say we have a 4x1 paper. The valid
folds are:

cmds => stack => unfold(stack)
RR => 2341 => RL
RL => 1432 => RR
LL => 3214 => LR
RL => 4132 => LL

So in this little set we can see that there are pairs of inputs that
give each other as outputs to the unfold section. This happens to also
work for larger paper stacks. I haven’t proved this, but I added this to
the unit tests to make sure:

def random_string(len)
    vert_folds = ['T', 'B']
    horiz_folds = ['L', 'R']
    folds = []
    (len/2).times do folds << vert_folds[rand(2)] end
    (len/2).times do folds << horiz_folds[rand(2)] end
    folds.sort{rand}.join
end

def test_random_unfold
    100.times do |i|
        side_pow = rand(7)+1
        side = 2**side_pow
        s = random_string(side_pow*2)
        assert_equal s, unfold(fold(s, side))
    end
end

No failures yet. I’d bet that there is a simple way to fix the
algorithm, but I need to just sit down an figure it out. I can probably
just be able to do a global replace on the string instead of rerunning
fold and unfold. Well, thanks for the quiz!

-----Horndude77

#!/usr/bin/ruby -w

module Math
def Math.lg(n) log(n)/log(2) end
end

def fold(s, n)
#validate inputs
pow = Math.lg(n)
raise “Bad dimension” if pow != pow.round
raise “Bad string length” if s.length != (pow*2).round
horiz, vert = 0, 0
s.downcase.split(’’).each do |orient|
case orient
when ‘r’, ‘l’
vert += 1
when ‘t’, ‘b’
horiz += 1
end
end
raise “Unbalanced folds” if horiz != vert

#do the folding
max = n**2
stack = Array.new(max)
1.upto(max) do |i|
    row, col, pos, height = (i-1)/n, (i-1)%n, 0, 1
    x, y = n, n
    s.each_byte do |move|
        pos += height
        height *= 2
        case move
        when ?L
            x /= 2
            if col < x then
                col = x-col-1
                pos = height - pos - 1
            else
                col -= x
            end
        when ?R
            x /= 2
            if col >= x then
                col = x*2 - col - 1
                pos = height - pos - 1
            end
        when ?T
            y /= 2
            if row < y then
                row = y-row-1
                pos = height - pos - 1
            else
                row -= y
            end
        when ?B
            y /= 2
            if row >= y then
                row = y*2 - row - 1
                pos = height - pos - 1
            end
        end
    end
    stack[pos] = i
end
stack

end

def same_row?(a,b,n)
(a-1)/n == (b-1)/n
end

def same_col?(a,b,n)
(a-1)%n == (b-1)%n
end

def unfold(stack, recurse = :yes)
pow = Math.lg(stack.length)
raise “Bad dimension” unless pow == pow.round && (pow.round % 2) ==
0
side = Math.sqrt(stack.length).round
s = “”
while stack.length > 1
half = stack.length/2
a, b = stack[half-1], stack[half]
if same_row? a, b, side then
if a<b then s << ‘L’ else s << ‘R’ end
elsif same_col? a, b, side then
if a<b then s << ‘T’ else s << ‘B’ end
else
raise “Stack not generated from folding”
end
stack = stack[half, half]
end

s.reverse!
if(recurse == :yes) then
    unfold(fold(s, side), :no)
else
    s
end

end

[bbazzarrakk]

In article [email protected],
“asplake” [email protected] writes:

Matthew, thank you for sharing your results (and in the form of test
cases). Pleased to report that mine are identical (and pass!).

me too

BTW it’s not hard to work out (and - hint to Chris - validate) the grid
dimensions from the folds so my function takes just the one argument.

Good hint.

But doesn’t that imply that any input is valid? E.g. LR is ok for
a 4x1 sheet (giving 4,1,2,3).
Or did you introduce a rule that the input has to be a square?

I suggest other tests based on my solution
def test_1024_1024
xpct = ‘b5319b3045af0ab0f931dacca739d90a’
md5 = MD5.new(fold(1024,1024,‘TRTRTRTRTRTRTRTRTRTR’).join(’ ‘))
assert_equal xpct, md5.hexdigest
end
def test_2048_2048
xpct = ‘8e046199eee20b097e4948a5ea503516’
md5 = MD5.new(fold(2048,2048,‘TRTRTRTRTRTRTRTRTRTRTR’).join(’ '))
assert_equal xpct, md5.hexdigest
end
(you need to add a ‘require “md5”’ to the test skript, the array itself
is a bit lengthy ;-))

For larger sheets my system (512M) starts to swap too much.
Probably I should have used a singe array instead of three dimensional
arrays of arrays…

Morus

[bbazzarrakk]

Matthew, thank you for sharing your results (and in the form of test
cases). Pleased to report that mine are identical (and pass!).

BTW it’s not hard to work out (and - hint to Chris - validate) the grid
dimensions from the folds so my function takes just the one argument.

Regards, Mike

[bbazzarrakk]

Thanks for the test, passed.

“Finished in 182.372 seconds.” - quite long for my 2Ghz P4. I wonder
how much it takes to pass the test for the other participants.

[bbazzarrakk]

Or did you introduce a rule that the input has to be a square?

Sorry, I missed this earlier, but as per my submission a few minutes
ago I raise an exception if it’s non-square, but only to pass the unit
tests. Otherwise I see no problem with this.

For larger sheets my system (512M) starts to swap too much.
Probably I should have used a singe array instead of three dimensional
arrays of arrays…

Very interesting to see other solutions. So far I seem to be the only
one not to have modelled the grid explicitly, allocating an array only
for the output. Tried 1024x1024 just now (took 4 minutes - how about
you?) and I’ll give your tests a try. Mine seems to be the most
verbose though…

Mike Burrows

[bbazzarrakk]

Not 100% surprised, and it’s longer than others too. For the large
(e.g. 1024x1024) runs it’s now about twice as fast, just by
preallocating the results array and using ‘for’ instead of ‘each’
loops. Oh well. Still the slowest. Perhaps mine uses less memory

[bbazzarrakk]

Mike, you have an interesting concept for this quiz, but the script is
very slow (3 times slower than the nearest neighbour) - I just tested
it on my machine along with others.

[bbazzarrakk]

Excuse me for a dumb question, but how do you preallocate the array?