Thursday, February 7, 2008

Project Euler #5 and number theory

There is a site (ProjectEuler.net) which posts numerous mathematical challenges for programmers and math nerds such as myself.

Problem #5 is ranked as one of the easiest problems on the site:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?


Its an easy problem in any programming language.
start at 1 and keep incrementing. Every step of the way check the number modulo 2-20, if they all come out to 0, you've got the answer.
Thats the fastest program to write, however it'll take more than 4.6 billion steps before you reach it.

There are several optimizations one could do to speed things up as demonstrated in this blog post:
http://www.fsharp.it/2008/02/07/project-euler-in-f-problem-5/
showing how to find the solution in around 25 seconds using F#.

After looking at the code I was impressed with F# and the author's optimization abilities and techniques. But it does show a glaring problem in post optimizations and fundamental shift in computer science away from field of number theory and mathematics which it came from.

25 seconds isn't too bad for something that could take 4.6 billion steps, but using some simple number theory and prime factorization I can give you the answer in about as much time. Here's the solution for 1-10 as I don't want to give the final answer away.

Before we start here's something to think about, if a number is divisible by 8, then it is divisible by 4 and 2 so why do the redundant checking.

here are our numbers omitting 1:
2, 3, 4, 5, 6, 7, 8, 9, 10
and the prime factorizations:
2
3
2, 2
5
2, 3
7
2, 2, 2
3, 3
2, 5

back the being divisible by 8, thats: 2, 2, 2
so lets go through and knock out any number of 2s less than 3 for a given factorization

2
3
2, 2
5
2, 3
7
2, 2, 2
3, 3
2, 5

and we repeat that with nine's: 3, 3

2
3
2, 2
5
2, 3
7
2, 2, 2
3, 3
2, 5

and lastly with five:

2
3
2, 2
5
2, 3
7
2, 2, 2
3, 3
2, 5

which leaves you with 7, 2, 2, 2, 3, 3, 5
7*2*2*2*3*3*5 = 2520

A similar method would be to start with 2 and 3. find the lcm(2, 3) = 6.
then find the lcm(6, 4) = 12
lcm(12, 5) = 60
lcm(60, 6) = 60
lcm(60, 7) = 420
lcm(420, 8) = 840
lcm(840, 9) = 2520
lcm(2520, 10) = 2520

Tuesday, January 29, 2008

DSLs in Ruby

There's been a lot of talk about DSLs in programming. Even more so if you're keen on talking about Ruby.
At first, being primarily a .Net developer at the time, I didn't grasp the full potential of DSLs, nor the idea that I could get non-technical testers to start programming their own tests without some hard to write interpreter. Then I made my attempt.
The site I've been working with has several large forms for different products. Each field on these forms have server side validation rules that must be run. Once validated there is a possibility of other fields being changed, as well as validation messages popping up in their own tab.

Since it is a website and I want to do testing in ruby, I chose to use watir to interface with IE. Watir has a fantastic easy to use API.

my first step was setting up a way to change fields. The first problem I ran into was using watir to just grab an element and give me more information on. It turns out theres no method for getting an element, you have to get a specific type of element. On further inspection I found that something like a text_field inherits from element, so I can grab anything as a text_field and get mroe information about its type from that.

def set field, value
case @ie.text_field(:id, field.to_s).type.to_s
when 'text'
@ie.text_field(:id, field).set(value.to_s)
when 'checkbox'
@ie.checkbox(:id, field).set(value[0])
when 'select-one'
@ie.select_list(:id, field).set(value.to_s)
else
raise "ERROR - Could not set #{field}"
end
log "Setting #{field} to #{value}"
end

so in my tests I can write:
set 'FACE_AMOUNT', 50000
and it will find the FACE_AMOUNT element and set its value to 50000
I can also set a checkbox to true and false
and set a select field using the text of an option

My next goal was to write a method to check the value of a field.
I was able to get the value similar to how I did with the set.

def check field, value
actual_val = case @ie.text_field(:id, field).type
when 'text'
@ie.text_field(:id, field).value
when 'checkbox'
@ie.checkbox(:id, field).checked?
when 'select-one'
@ie.select_list(:id, field).getSelectedItems
else
raise "ERROR - Could not check #{field}"
end
if value.to_s == actual_val.to_s
break
end
raise "ERROR - #{field} expected to be #{value}, actual value #{actual_val}" unless actual_val.to_s == value.to_s
log "#{field} is #{value}"
end


Then I ran into a problem. Sometimes the script would run too fast and outpace the ajax causing a test to fail. To fix this I added a try_for method. You call this, pass in how long you intend to try, and a block of what you want to try. It will run your code, if it fails, it'll keep running it until either time runs out or the test passes.
def try_for time
stop = Time.now + time
loop do
yield
break if stop < Time.now
end
end


and I changed my check to
def check field, value
actual_val = ''
try_for CHECK_TIME do
actual_val = case @ie.text_field(:id, field).type
when 'text'
@ie.text_field(:id, field).value
when 'checkbox'
@ie.checkbox(:id, field).checked?
when 'select-one'
@ie.select_list(:id, field).getSelectedItems
else
raise "ERROR - Could not check #{field}"
end
if value.to_s == actual_val.to_s
break
end
end
raise "ERROR - #{field} expected to be #{value}, actual value #{actual_val}" unless actual_val.to_s == value.to_s
log "#{field} is #{value}"
end


and I added a CHECK_TIME constant in a settings file.

I was able to easily write some methods to check validation messages and validation count by checking the rows and number of rows of my validation table.
In the end I was able to get a test that looks like:

require 'eConnectionsTester'

launch_econnections
set_product 500

set 'FACE_AMOUNT', 49999
validations_contain? 'Entered face amount is less than the minimum required face amount (50000).'
validation_count? 1
check 'FACE_AMOUNT', 50000
set 'FACE_AMOUNT', 50001
validation_count? 0
set 'FACE_AMOUNT', 50000
validation_count? 0


Things were starting to look nice. I saw some code that I felt a non-technical tester could pick up after a few minutes of training.

But it didn't seem finished. I saw rspec in action a couple weeks back and I really liked its format. I wanted something that behaves the same way, but only for defining the tests.
The was almost trivial to accomplish using blocks and yields. I added
def test what
validation_count? 0
puts "Test: #{what}"
begin
yield
puts 'Passed'
rescue
$stderr.puts $!
puts 'Failed'
end
end


def tests_for what
puts "Testing: #{what}"
begin
yield
rescue
$stderr.puts $!
end
puts 'Press any key to continue'
gets
end


and now the tests take this form
tests_for 'Product 500' do
launch_econnections
set_product 500

test 'Minimum Face Amount is 50000' do
set 'FACE_AMOUNT', 49999
validations_contain? 'Entered face amount is less than the minimum required face amount (50000).'
validation_count? 1
check 'FACE_AMOUNT', 50000
set 'FACE_AMOUNT', 50001
validation_count? 0
set 'FACE_AMOUNT', 50000
validation_count? 0
end
end


and now we have nicely formatted tests, which also print out to console what is being tested, any errors, and waits once the tests are finished.

I was looking over the final version and feeling really good about myself. After turning it over in my head, I felt there was a lot of repetition in the sets and the checks, and I didn't like the quotes.

I turned to the global method_missing, and I rewrote it. I also added a set_check method that takes a field and two values. It sets it to the first one, and checks that it is changed to the second one from a validation rule.
Using Ruby's ! and ? for methods, I was easily able to map missing methods to the set, check, and set_check where no suffix mapped to set, ? mapped to check, and ! mapped to set_check
def method_missing(val, *args, &action)
val = val.to_s
case val
when /\?$/
check(val.chop, args)
when /\!$/
set_check(val.chop, args)
else
set(val, args)
end
end


And once I was done with all this, I can have my testers write:
tests_for 'Product 500' do
launch_econnections
set_product 500

test 'Minimum Face Amount is 50000' do
FACE_AMOUNT! 49999, 50000
validations_contain? 'Entered face amount is less than the minimum required face amount (50000).'
validation_count? 1
FACE_AMOUNT 50001
validation_count? 0
FACE_AMOUNT 50000
validation_count? 0
end

test 'Maximum age for Juvenile is 17' do
AGE1 45
UND_CLASS1! 'Juvenile Standard', 'Preferred Plus'
validation_count? 1
validations_contain? 'Class invalid for age and has been changed'
UND_CLASS1 'Preferred Non-Tobacco'
validation_count? 0
AGE1 17
UND_CLASS1? 'Juvenile Standard'
validation_count? 1
validations_contain? 'Class invalid for age and has been changed'
UND_CLASS1 'Preferred Plus'
validation_count? 1
UND_CLASS1? 'Juvenile Standard'
AGE1 18
UND_CLASS1? 'Preferred Plus'
validation_count? 1
UND_CLASS1 'Preferred Non-Tobacco'
validation_count? 0
end
end