with: result = Array.new(orig_width * orig_height)
and if “preallocate” was the wrong word, I apologise!
Thanks. I don’t know how to apply it to my code, though. Lets say I
have an array of symbol pairs such as: [[:top, :left], [:bottom,
:left], [:top, :right]] … ], and there’s an N of them.
Replacing “@origin = []” with something like “@origin = Array.new(2*N)”
gives out an error about accessing nil later in the code.
In article [email protected],
“Vladimir A.” [email protected] writes:
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.
502.175 (~90 for the 1024x1024 and 411 for the 2048x2048)
on a AMD Athlon XP 1600+ (1400 MHz).
Pretty slow I guess.
So I redid that using a single array instead of arrays of arrays of
arrays.
I’m still accessing each cell indidually. But that turned out to be even
slower (I used a Array3d class and the additional method lookup is
obviously
too expensive, especially since I access each point individually).
So here’s my solution:
#! /usr/bin/ruby
class Sheet
attr_reader :width, :height, :depth
def check(dim)
n = Math.log(dim)/Math.log(2) # ’ /x
if n != n.to_i
raise “dimension must be power of 2”
end
end
def initialize(width, height)
check(width)
check(height)
sheet = []
0.upto(height-1) do | y |
sheet[y] = []
0.upto(width-1) do | x |
sheet[y][x] = [ width*y + x ]
end
end
set_sheet(sheet)
end
def set_sheet(sheet)
@sheet = sheet
@width = sheet[0].size
@height = sheet.size
@depth = sheet[0][0].size
end
def output()
0.upto( height-1 ) do | y |
0.upto( width-1 ) do | x |
(depth-1).downto( 0 ) do | z |
print "%3d " % (@sheet[y][x][z]+1)
end
print " "
end
puts “”
end
puts “”
end
def result
@sheet[0][0].reverse.collect { | i | i+1 }
end
ok, here comes the ugly part…
for each folding direction a new (stacked) sheet is calculated
def fold(dir)
new_sheet = []
if dir == “T”
s2 = height/2 # i’d really liked to know why xemacs has problems
with foo/2; probably it’s confused with a regex
raise “cannot fold” if s2 == 0
0.upto( s2-1 ) do | y |
new_sheet[y] = @sheet[y + s2]
0.upto( width-1 ) do | x |
0.upto( depth-1 ) do | z |
new_sheet[y][x][depth+depth-1-z] = @sheet[s2-1-y][x][z]
end
end
end
elsif dir == “B”
s2 = height/2 #‘/x
raise “cannot fold” if s2 == 0
0.upto( s2-1 ) do | y |
new_sheet[y] = @sheet[y]
0.upto( width-1 ) do | x |
0.upto(depth-1) do | z |
new_sheet[y][x][depth+depth-1-z] = @sheet[s2+s2-1-y][x][z]
end
end
end
elsif dir == “L”
s2 = width/2 #’/x
raise “cannot fold” if s2 == 0
0.upto( height-1 ) do | y |
new_sheet[y] ||= []
0.upto( s2-1 ) do | x |
new_sheet[y][x] ||= []
0.upto( depth-1 ) do | z |
new_sheet[y][x][z] = @sheet[y][x+s2][z]
new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2-1-x][z]
end
end
end
elsif dir == “R”
s2 = width/2 #'/x
raise “cannot fold” if s2 == 0
0.upto( height-1 ) do | y |
new_sheet[y] ||= []
0.upto( s2-1 ) do | x |
new_sheet[y][x] ||= []
0.upto( depth-1 ) do | z |
new_sheet[y][x][z] = @sheet[y][x][z]
new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2+s2-1-x][z]
end
end
end
else
raise “unknown edge #{dir}”
end
set_sheet(new_sheet)
end
def folds(dirs)
dirs.split(//).each do | dir |
fold(dir)
end
end
end
def fold(width, height, cmds)
sheet = Sheet.new(width, height)
sheet.folds(cmds)
raise “to few folds…” if sheet.width > 1 || sheet.height > 1
return sheet.result
end
if ARGV[0]
cmds = ARGV[0]
width = (ARGV[1] || 16).to_i
height = (ARGV[2] || width).to_i
digits = (Math.log(width*height)/Math.log(10)).ceil
puts fold(width, height, cmds).collect { | i | “%#{digits}d” % i
}.join(", ")
end
In article [email protected],
“asplake” [email protected] writes:
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.
I don’t see a problem, I was just curious how you understand validation
if you get the sizes from the folding instructions, since I’d say any
instruction is valid then. But that’s just a question of interpretation
of the task.
Morus
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.
Well, sure… That’s like setting the speed limit to 300mph and
suddenly there are no more speeders. 
But since this is rubyquiz
and not traffic school, that’s cool.
On 1/24/06, Vladimir A. [email protected] wrote:
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.
My solution took only 143 seconds to do all the tests… of course,
my machine is a 3.2GHz P4, so it the solution ain’t that fast.
In article [email protected],
[email protected] (Morus W.) writes:
I did another solution doing an unfold of the final stack.
It’s much cleaner than the first one.
Unfortunately it’s still pretty slow for large grids.
So I did a third one, based on the second one replacing the calculation
by C. The drawback is that it isn’t portable anymore, though it should
run on any unix environment having a gcc compiler 
— second one —
#! /usr/bin/ruby
def fold(width, height, cmds)
size = width * height
horz = cmds.count(“RL”)
vert = cmds.count(“BT”)
raise “illegal width” if 2horz != width
raise “illegal height” if 2vert != height
func = “def unfold(z)\n(x,y,z) = [ 0,0,z ]\n”
w = 1
h = 1
d = size
cmds.split(//).reverse.each do | dir |
if dir == ‘R’
func += "(x,z) = (z < #{d/2}) ? [ #{2w-1}-x, #{d/2-1}-z ] : [ x,
z-#{d/2} ]\n"
w=2
elsif dir == ‘L’
func += “(x,z) = (z < #{d/2}) ? [ #{w-1}-x, #{d/2-1}-z ] : [
x+#{w}, z-#{d/2} ]\n”
w*=2
elsif dir == ‘B’
func += "(y,z) = (z < #{d/2}) ? [ #{2h-1}-y, #{d/2-1}-z ] : [ y,
z-#{d/2} ]\n"
h=2
elsif dir == ‘T’
func += “(y,z) = (z < #{d/2}) ? [ #{h-1}-y, #{d/2-1}-z ] : [
y+#{h}, z-#{d/2} ]\n”
h*=2
end
d/=2
end
func += “x + y * #{width} + 1\n”
func += “end\n”
eval func
(0…size-1).collect { | i | unfold(i) }
end
if ARGV[0]
dirs = ARGV[0]
width = (ARGV[1] || 16).to_i
height = (ARGV[2] || width).to_i
res = fold(width, height, dirs)
puts res.join(", ")
end
— third one —
#! /usr/bin/ruby
def fold(width, height, cmds)
size = width * height
horz = cmds.count(“RL”)
vert = cmds.count(“BT”)
raise “illegal width” if 2horz != width
raise “illegal height” if 2vert != height
func = “#include <stdio.h>\n#include <stdlib.h>\n”
func += “int unfold(int z) { \n int x=0; int y=0;\n”
w = 1
h = 1
d = size
cmds.split(//).reverse.each do | dir |
if dir == ‘R’
func += "x = (z < #{d/2}) ? #{2w-1}-x : x;\n"
func += “z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n”
w=2
elsif dir == ‘L’
func += “x = (z < #{d/2}) ? #{w-1}-x : x+#{w};\n”
func += “z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n”
w*=2
elsif dir == ‘B’
func += "y = (z < #{d/2}) ? #{2h-1}-y : y;\n"
func += “z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n”
h=2
elsif dir == ‘T’
func += “y = (z < #{d/2}) ? #{h-1}-y : y+#{h};\n”
func += “z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n”
h*=2
end
d/=2
end
func += “return x + y * #{width} + 1; }\n”
func += “int main(int argc, char**argv) {\n”
func += “int i=0;\nint max=atoi(argv[1]);for (i=0;i<max;i++) {
printf("%d ",unfold(i)); } }\n”
File.open(“unfold.c”, “w”) do | fh |
fh.puts func
end
gcc -O2 -o unfold unfold.c
IO.popen(“./unfold #{size}”).readline.split(" ").collect { | i |
i.to_i }
end
if ARGV[0]
dirs = ARGV[0]
width = (ARGV[1] || 16).to_i
height = (ARGV[2] || width).to_i
res = fold(width, height, dirs)
puts res.join(", ")
end
I was waiting to clean up my solution, but it’s Thursday, so here it
is. It’s too late for the summary, I’m just looking to get my first
successful RubyQuiz up. I also used this as my first TDD “project,”
which explains why it’s so verbose in places. I’ve also included the
tests, can’t hurt.
class String
def each_char
for i in 0…length
yield(self[i,1])
end
end
end
class Array
alias_method :old_eq, :==
def ==(arg)
return arg == self if arg.kind_of?(Grid)
old_eq(arg)
end
end
class Range
def middle
(first+last)/2
end
def flip(i)
last-1-(i-first)
end
def flip_doubled(i)
(last*2)-1-(i-first)
end
end
module DiscreteMethod
def make_disc_meth(sym)
define_method(sym) do |*args|
temp_var = clone
temp_var.send(sym.to_s + “!”,*args)
temp_var
end
end
end
class Grid
extend DiscreteMethod
attr_accessor :size, :rows, :cols, :vert, :cells
def initialize(n = 0)
@size = n
@rows = 0…n
@cols = 0…n
@vert = 0…1
@cells = {}
init_cells if n > 0
end
def init_cells
num = 1
for r in 0…size
for c in 0…size
@cells[[r,c,0]] = num; num += 1;
end
end
end
make_disc_meth “fold”
def fold!(str)
if str.length > 1
str.each_char { |c| fold!© }
return
end
raise “bad attempted fold” unless [“R”,“T”,“L”,“B”].include?(str)
raise “bad attempted fold” if (str == “R” or str == “L”) and
cols.first == cols.last-1
raise “bad attempted fold” if (str == “B” or str == “T”) and
rows.first == rows.last-1
@cells.keys.find_all { |k| k[1] >= cols.middle }.each { |k|
self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == “R”
@cells.keys.find_all { |k| k[1] < cols.middle }.each { |k|
self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == “L”
@cells.keys.find_all { |k| k[0] >= rows.middle }.each { |k|
self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == “B”
@cells.keys.find_all { |k| k[0] < rows.middle }.each { |k|
self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == “T”
update_boundaries!(str)
end
make_disc_meth “update_boundaries”
def update_boundaries!(d)
@vert = (0…vert.last*2)
@rows = (rows.first…rows.middle) if d == “B”
@rows = (rows.middle…rows.last) if d == “T”
@cols = (cols.first…cols.middle) if d == “R”
@cols = (cols.middle…cols.last) if d == “L”
end
def []=(r,c,v,n)
@cells[[r,c,v]] = n
end
def clone
g = Grid.new
g.rows,g.cols,g.vert = rows.clone,cols.clone,vert.clone
@cells.each_key do |k|
g[k[0],k[1],k[2]] = @cells[k]
end
g
end
def ==(g)
return to_a == g if g.kind_of? Array
return false if @cells.keys.size != g.cells.keys.size
return false if size != g.size or cols != g.cols or rows != g.rows
or vert != g.vert
@cells.keys.each { |k| return false if @cells[k] != g.cells[k] }
true
end
def sorted_keys
@cells.keys.sort { |a,b| x = b[2] <=> a[2]; (x = a[0] <=> b[0]) if
x==0; (x = a[1] <=> b[1]) if x==0; x }
end
def to_a
a = []
sorted_keys.each { |k| a << @cells[k] }
a
end
end
def fold(r,c,str)
raise “Bad Input Dimensions” if r != c or
![1,2,4,8,16,32,64,128].include?®
g = Grid.new®
g.fold!(str)
g.to_a
end
require ‘test/unit’
require ‘…/grid.rb’
class TestGridFold < Test::Unit::TestCase
def setup
@two = Grid.new(2)
@two_folded_rb = Grid.new
@two_folded_rb.rows = (0…1)
@two_folded_rb.cols = (0…1)
@two_folded_rb.vert = (0…4)
@two_folded_rb[0,0,3] = 3
@two_folded_rb[0,0,2] = 4
@two_folded_rb[0,0,1] = 2
@two_folded_rb[0,0,0] = 1
@st = Grid.new(16)
end
def test_size
assert @two.size == 2
end
def test_get
assert @two[0,0,0] == 1
assert @two[0,1,0] == 2
assert @two[1,0,0] == 3
assert @two[1,1,0] == 4
end
def test_out_bounds
assert @two[2,2,2].nil?
end
def test_full_fold
g = @two.fold(“RB”)
assert g == @two_folded_rb,g.to_a
#assert @two.fold(“TL”) == [3,1,2,4]
end
def test_one_fold
g = @two.fold(“R”)
assert g == [2,4,1,3],g.to_a
g = g.fold(“B”)
assert g == @two_folded_rb
end
def test_fold_not_modify
@two.fold(“R”)
test_get
end
def test_fold_exc
assert @two.fold(“RB”) == @two_folded_rb
end
def test_init_boundaries
assert @two.rows == (0…2)
assert @two.cols == (0…2)
assert @two.vert == (0…1)
end
def test_boundaries_after_fold
assert @two.fold(“R”).cols == (0…1)
assert @two.fold(“L”).cols == (1…2)
assert @two.fold(“R”).rows == (0…2)
assert @two.fold(“L”).rows == (0…2)
end
def test_update_boundaries_r
g = @two.update_boundaries(“R”)
assert g.rows == (0…2)
assert g.cols == (0…1),g.cols
assert g.vert == (0…2)
end
def test_update_boundaries_t
assert @two.update_boundaries(“T”).rows == (1…2)
assert @two.update_boundaries(“T”).cols == (0…2)
assert @two.update_boundaries(“T”).vert == (0…2)
end
def test_update_boundaries_l
g = @two.update_boundaries(“L”)
assert g.rows == (0…2)
assert g.cols == (1…2),g.cols
assert g.vert == (0…2)
end
def test_update_boundaries_ll
g = @st.update_boundaries(“L”).update_boundaries(“L”)
assert g.rows == (0…16)
assert g.cols == (12…16),g.cols
assert g.vert == (0…4)
end
def test_update_boundaries_llrbt
g =
@st.update_boundaries(“L”).update_boundaries(“L”).update_boundaries(“R”).update_boundaries(“B”).update_boundaries(“T”)
assert g.rows == (4…8)
assert g.cols == (12…14),g.cols
assert g.vert == (0…32)
end
def test_update_boundaries_no_update
@two.update_boundaries(“R”)
assert @two.cols == (0…2)
end
def test_update_boundaries_exc_update
@two.update_boundaries!(“R”)
assert @two.cols == (0…1)
end
def test_clone
g = @two.clone
assert g[0,0,0] == 1
assert g[1,1,0] == 4
g[0,0,0] = 9
assert g[0,0,0] == 9
assert @two[0,0,0] == 1
end
def test_set
@two[0,0,0] = 9
assert @two[0,0,0] == 9
end
def test_equality_grid
assert @two == Grid.new(2)
assert Grid.new(2).fold(“R”) == Grid.new(2).fold(“R”)
assert Grid.new(2).fold(“RB”) == Grid.new(2).fold(“RB”)
end
def test_equality_array
assert @two_folded_rb == [3,4,2,1]
end
def test_to_a
a = @two_folded_rb.to_a
assert a == [3,4,2,1],a
end
end