There is an excellent article over on the Red Artisan blog about using DTrace with Ruby on Mac OS X. I look forward to trying this out and applying it towards Project Euler solutions. Should be interesting!

# Tag Archives: ruby

# Working with Binary in Ruby

This post is mainly for my own information, but hopefully someone else will find it useful as well. I was struggling a little to find solid information on how to handle binary files in Ruby. I appreciate that a String can double as a binary data buffer, and actually depend on that quite a bit. In order to make something “useful” that helped me learn I created a simple version of the popular tool **xxd**. The code can be found below.

** Note: This is most deffinately prototype code that needs to be refined. I’m also of the opinion that several parts within it are “ugly”*

[sourcecode language=“ruby”]

#!/usr/bin/env ruby

class Hexdemo

def initialize filename

@filename = filename

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
remaining = idx-line+1
if remaining <= 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 output from running it against Google’s logo.gif
[sourcecode 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

Problem two steps things up just a smidgen.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting 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 challenge of this problem is to accurately calculating the Fibonacci sequence while summing only the even-valued terms. Ruby allows us to treat arrays like stacks, so I can easily push a value onto the stack after calculating 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 element in an array. I did not need to keep an entire array of Fibonacci values, but chose to since I wanted to print a list of all the values at the end. It was initially for debugging, and then because I was curious as to what last the Fibonacci number before 4 million was. You’ll see again that I wrote my code for the general case for the sum of even Fibonacci values under N with a default of 4,000,000.

[sourcecode language=“ruby”]

#!/usr/bin/env ruby

class Problem

# Create the object

def initialize (n)

@n = n.to_i

end

# Solve it

def solve

puts “Solving for sum of even numbers in fib sequence under 4 million“

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
# Initialize the program
p = Problem.new ARGV[0] || 4000000
p.solve
end
[/sourcecode]

# Project Euler: Problem 1

The first problem of Project Euler is very straight forward.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This problem is basically making sure that the site user has a computer language at their disposal and a basic grasp of common operations such as looping, if/else, and the modulo operator.

My straight forward Ruby code is below. Note that I write every Ruby program so that it can be run as an executable script that takes a value from the command line. This value is typically assigned to @n within my code. It’s used for problems that solve a general case. The general case of this problem is to find the sum of all the multiples of 3 or 5 below N.

[sourcecode language=“ruby”]

#!/usr/bin/env ruby

class Problem

# Create the object

def initialize (n = 10)

@n = n.to_i

@sum = 0

end

# Solve it

def solve

puts “Find sum of all numbers under #{@n} disivible by 3 and 5″

@n.times do |k|

@sum += k if k % 3 == 0 || k % 5 == 0

end

puts “Solution: #{@sum} is solution for n = #{@n}“

end

end

if __FILE__ == $0

# Initialize the program

p = Problem.new ARGV[0] || 10

p.solve

end

[/sourcecode]

# Thinking in Code vs. Thinking in Mathematics

Lately I’ve been hooked on the website Project Euler. Today I sat down to solve Problem #15:

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there in a 20x20 grid?

My initial thought with this was “recursion!” So I sat down and thought about graphs and trees from previous CS classes, debated creating a node class with down and right attributes that would be check off after they were used, etc. Then I realized that it could be solved with a single recursion function, given two arguments (the x and y position). My initial code in ruby is below:

[sourcecode language=“ruby”]

#!/usr/bin/env ruby

class Problem

# Constructor

def initialize (n = 10)

@n = n.to_i

@paths = 0

end

# Solve it

def solve

node(0,0)

puts “Found #{@paths} paths“

end

# Recursively check for paths

def node(x, y)

# First, are we the end node?

if x == @n &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
# Initialize the program
p = Problem.new ARGV[0] || 2
p.solve
end
[/sourcecode]
This works quite well for small values of n. The issue is that it’s basically a brute force method, and performance of this falls off rather quickly as n increases.

============================

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 problem. If I approach it from a mathematical viewpoint I can see that there is definitely a pattern. To get from the top left to the bottom right we must always go N moves to the right, and N moves downward. If we call the left and right positions X and the up and down positions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the positions of the 2x2 grid. Another would be XYYX. And so forth. What this is representing is the permutation of indistinguishable objects, where (x+y)!/(x!y!) gives the number of permutations.

My code for this is below:

[sourcecode language=“ruby”]

#!/usr/bin/env ruby

class Problem

# Create the object

def initialize (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

# Factorial of n

def f(n)

n == 1 ? 1 : n*f(n-1)

end

end

if __FILE__ == $0

# Initialize the program

p = Problem.new ARGV[0] || 2

p.solve

end

[/sourcecode]

This is much quicker. It actually is able to calculate the number of paths for a give NxN grid in just a couple milliseconds. It takes 5ms for N up to 115. Thats what I call improvement!

The lesson learned from this problem is that even though a “coding” solution is readily apparent (and works!) it may not necessarily be the best or most efficient solution to the problem. That is why a good understanding of math will never hurt ;)