Quickie: Paper Pong

I was brows­ing Red­dit this evening and came across Paper Pong. It’s a paper based ver­sion of pong that is based on the idea of the Choose Your Own Adven­ture books I read and loved as a kid. It’s not very fun, but it did get me think­ing about most sim­ple games are noth­ing but a series of pre­de­fined states with tran­si­tions from one to another based on the rules of the game. To make a paper ver­sion, all that’s needed is to draw out all pos­si­ble states and then link them with page num­bers. The part that made me smile the most was the mes­sage on page 25. “To quit, close this book.”

You can play Paper Pong here in a new win­dow (popup).

Quickie: DTrace and Ruby

There is an excel­lent arti­cle over on the Red Arti­san blog about using DTrace with Ruby on Mac OS X. I look for­ward to try­ing this out and apply­ing it towards Project Euler solu­tions. Should be interesting!

Working with Binary in Ruby

This post is mainly for my own infor­ma­tion, but hope­fully some­one else will find it use­ful as well. I was strug­gling a lit­tle to find solid infor­ma­tion on how to han­dle binary files in Ruby. I appre­ci­ate that a String can dou­ble as a binary data buffer, and actu­ally depend on that quite a bit. In order to make some­thing “use­ful” that helped me learn I cre­ated a sim­ple ver­sion of the pop­u­lar tool xxd. The code can be found below.

* Note: This is most def­fi­nately pro­to­type code that needs to be refined. I’m also of the opin­ion that sev­eral parts within it are “ugly”

[source­code language=“ruby”]
#!/usr/bin/env ruby

class Hexdemo

def ini­tial­ize file­name
@filename = file­name
end

def print_file

string = File.read(@filename)

arr = data_string_to_hex_array string
print_hex_array arr

end

def data_string_to_hex_array data
tmp = []
data.each_byte { |byte| tmp.push byte.to_s(16) }
(0..(tmp.length-1)).each do |idx|
if tmp[idx].length == 1
tmp[idx] = “0” « tmp[idx] end end return tmp end def print_hex_array arr line = 0; ascii = [] print “0\t“ (0..(arr.length-1)).each do |idx| print ”][ ” if idx % 8 == 0 && idx % 16 != 0 if idx % 16 != 0 || idx == 0 print arr[idx] « ” “ if arr[idx].hex >= 32 && arr[idx].hex <= 126 ascii.push arr[idx].hex.chr else ascii.push ‘.‘ end else print “\t” « ascii.join(”) print “\n“ line += 16 ascii = [] print line.to_s « “\t“ print arr[idx] « ” “ if arr[idx].hex >= 32 && arr[idx].hex <= 126 ascii.push arr[idx].hex.chr else ascii.push ‘.‘ end end if idx == arr.length-1 remain­ing = idx-line+1 if remain­ing <= 8 print ’ ‘*3 end print ’ ‘*(16-remaining) print “\t” « ascii.join(”) end end puts ““ end end if __FILE__ == $0 h = Hexdemo.new ARGV[0] || “data.bin“ h.print_file end [/sourcecode] Below you’ll find some lovely out­put from run­ning it against Google’s logo.gif [source­code language=“html”] [email protected]:~/code/ruby$ ./hex.rb logo.gif 0 47 49 46 38 39 61 14 01 ][ 6e 00 f7 00 00 f7 f7 f7 GIF89a..n.…… 16 ff fb ff e7 e7 e7 d6 d3 ][ d6 ef eb ef ce cb ce ad .….….….… 32 14 00 de db de 18 45 ad ][ 18 49 b5 10 34 84 10 3c .…..E..I..4..< 48 94 c6 18 00 b5 b2 b5 f7 ][ f3 f7 8c 10 00 c6 be bd .….….….… 64 bd ba bd 18 4d c6 e7 e3 ][ e7 ef ef ef c6 c3 c6 f7 .…M.….…… 80 f3 ef bd be bd c6 c7 c6 ][ 08 51 08 ce cf ce 08 24 .….….Q.….$ 96 63 21 59 d6 d6 24 08 d6 ][ d7 d6 18 51 ce 9c 9e 9c c!Y..$.….Q.… 112 ef ba 00 de df de 00 65 ][ 00 d6 ae 00 63 96 ef 31 .……e.…c..1 128 65 d6 4a 7d e7 08 3c a5 ][ b5 b6 b5 9c 9a 9c 73 a2 e.J}..<.……s. 144 ef de df e7 39 71 de 6b ][ 0c 00 00 7d 08 ff cf 00 .…9q.k…}.… 160 bd b6 bd ad a6 ad a5 a2 ][ a5 e7 49 31 29 51 b5 ff .….…..I1)Q.. 176 75 63 bd 96 00 5a 8a ef ][ a5 a6 a5 10 45 b5 ad aa uc…Z.…..E… 192 ad c6 9e 00 ad ae ad f7 ][ 69 52 e7 3c 21 fd fd fd .….…iR.<!… 208 ef 59 42 63 d3 63 de 30 ][ 18 5a cb 5a b5 24 10 84 .YBc.c.0.Z.Z.$.. [/sourcecode]

Project Euler: Problem 2

Prob­lem two steps things up just a smidgen.

Each new term in the Fibonacci sequence is gen­er­ated by adding the pre­vi­ous two terms. By start­ing with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

The chal­lenge of this prob­lem is to accu­rately cal­cu­lat­ing the Fibonacci sequence while sum­ming only the even-valued terms. Ruby allows us to treat arrays like stacks, so I can eas­ily push a value onto the stack after cal­cu­lat­ing it as the next term. Using the last method on an array is a neat trick in Ruby to get the value of the last ele­ment in an array. I did not need to keep an entire array of Fibonacci val­ues, but chose to since I wanted to print a list of all the val­ues at the end. It was ini­tially for debug­ging, and then because I was curi­ous as to what last the Fibonacci num­ber before 4 mil­lion was. You’ll see again that I wrote my code for the gen­eral case for the sum of even Fibonacci val­ues under N with a default of 4,000,000.

[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (n)
@n = n.to_i
end

# Solve it
def solve
puts “Solv­ing for sum of even num­bers in fib sequence under 4 mil­lion“
fib = [0,1]
sum = 0
while(fib.last < @n) tmp = fib.last + fib[fib.length — 2] if tmp % 2 == 0 && tmp < @n puts “Adding #{tmp} + #{sum} = #{tmp+sum}“ sum += tmp end fib.push tmp end puts fib.join(“, ”) puts “Sum: #{sum}“ end end if __FILE__ == $0 # Ini­tial­ize the pro­gram p = Problem.new ARGV[0] || 4000000 p.solve end [/sourcecode]

Project Euler: Problem 1

The first prob­lem of Project Euler is very straight forward.

If we list all the nat­ural num­bers below 10 that are mul­ti­ples of 3 or 5, we get 3, 5, 6 and 9. The sum of these mul­ti­ples is 23.

Find the sum of all the mul­ti­ples of 3 or 5 below 1000.

This prob­lem is basi­cally mak­ing sure that the site user has a com­puter lan­guage at their dis­posal and a basic grasp of com­mon oper­a­tions such as loop­ing, if/else, and the mod­ulo operator.

My straight for­ward Ruby code is below. Note that I write every Ruby pro­gram so that it can be run as an exe­cutable script that takes a value from the com­mand line. This value is typ­i­cally assigned to @n within my code. It’s used for prob­lems that solve a gen­eral case. The gen­eral case of this prob­lem is to find the sum of all the mul­ti­ples of 3 or 5 below N.

[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (n = 10)
@n = n.to_i
@sum = 0
end

# Solve it
def solve
puts “Find sum of all num­bers under #{@n} disivi­ble by 3 and 5″

@n.times do |k|
@sum += k if k % 3 == 0 || k % 5 == 0
end

puts “Solu­tion: #{@sum} is solu­tion for n = #{@n}“
end
end

if __FILE__ == $0

# Ini­tial­ize the pro­gram
p = Problem.new ARGV[0] || 10
p.solve

end
[/sourcecode]

Thinking in Code vs. Thinking in Mathematics

Lately I’ve been hooked on the web­site Project Euler. Today I sat down to solve Prob­lem #15:

Start­ing in the top left cor­ner of a 2×2 grid, there are 6 routes (with­out back­track­ing) to the bot­tom right cor­ner.
How many routes are there in a 20x20 grid?

My ini­tial thought with this was “recur­sion!” So I sat down and thought about graphs and trees from pre­vi­ous CS classes, debated cre­at­ing a node class with down and right attrib­utes that would be check off after they were used, etc. Then I real­ized that it could be solved with a sin­gle recur­sion func­tion, given two argu­ments (the x and y posi­tion). My ini­tial code in ruby is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Con­struc­tor
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
node(0,0)
puts “Found #{@paths} paths“
end

# Recur­sively check for paths
def node(x, y)
# First, are we the end node?
if x == @n &amp;amp;&amp;amp; y == @n
@paths += 1
return
end

# Lets go “right“
node(x+1,y) if x < @n # Lets go “down“ node(x,y+1) if y < @n end end if __FILE__ == $0 # Ini­tial­ize the pro­gram p = Problem.new ARGV[0] || 2 p.solve end [/sourcecode] This works quite well for small val­ues of n. The issue is that it’s basi­cally a brute force method, and per­for­mance of this falls off rather quickly as n increases.

n   ms  paths
============================
2   5   6
3   5   20
4   5   70
5   6   252
6   8   924
7   17  3432
8   57  12870
9   176 48620
10  668 184756
11  2513    705432
12  9401    2704156

This forced me to take another look at the prob­lem. If I approach it from a math­e­mat­i­cal view­point I can see that there is def­i­nitely a pat­tern. To get from the top left to the bot­tom right we must always go N moves to the right, and N moves down­ward. If we call the left and right posi­tions X and the up and down posi­tions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the posi­tions of the 2x2 grid. Another would be XYYX. And so forth. What this is rep­re­sent­ing is the per­mu­ta­tion of indis­tin­guish­able objects, where (x+y)!/(x!y!) gives the num­ber of permutations.

My code for this is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
@paths = f(@n*2)/(f(@n)**2)
puts “Found #{@paths} paths“
end

# Fac­to­r­ial of n
def f(n)
n == 1 ? 1 : n*f(n-1)
end

end

if __FILE__ == $0

# Ini­tial­ize the pro­gram
p = Problem.new ARGV[0] || 2
p.solve

end
[/sourcecode]

This is much quicker. It actu­ally is able to cal­cu­late the num­ber of paths for a give NxN grid in just a cou­ple mil­lisec­onds. It takes 5ms for N up to 115. Thats what I call improvement!

The les­son learned from this prob­lem is that even though a “cod­ing” solu­tion is read­ily appar­ent (and works!) it may not nec­es­sar­ily be the best or most effi­cient solu­tion to the prob­lem. That is why a good under­stand­ing of math will never hurt ;)