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

Tuesday, December 4, 2007

More Regex

When the problem of validating a date came up, it was regular expressions to the rescue.
The following will validate a date in the form of mm/dd/yyyy and could be modified for other forms:
^((0[13578]|1[02])\/([012]\d|3[01])\/(19|20)\d{2}|
(0[468]|11)\/([012]\d|30)\/(19|20)\d{2}|
02\/([01]\d|2[1-8])\/(19|20)\d{2}|
02\/29\/(2[048]00|(19|20)(0[48]|[2468][048]|[13579][26])))$

(note: join on a single line)

If you end up using this, keep in mind that it has to be mm/dd/yyyy that means
01/06/0045 will work
2/7/1932 will not

what does this check
checks that a month 01-12 is entered
for months 1,3,5,7,8,10, and 12 it checks that the day is 01-31
for months 4,6,9, and 11 it checks that the day is 01-30
for month 2 it checks that the day is 01-28
for the above it checks that the year is 1900-2099
if the month is 2 and the day is 29 it checks that the year is
2000, 2400, 2800, or divisible by 4 but not 100

Wednesday, November 14, 2007

The Joys of Regex

I had written a service as part of an application involving an old mainframe system. The mainframe would send me text that I was to turn into a pdf and save to database.

Shortly after the app went live, I started getting several transaction failures on my end. My logging displayed "FAILURE: Can't show character with Unicode value U+FFFD".

Since the data is stored in a varbinary field, I'm sure this was being generated when I was writing the pdf.

After talking to the mainframe guys, I found that they would sometimes send me strange unicode characters such as �.

I asked fro whichever would be easier, characters denied or characters allowed, and was sent:
~!@#$%^&*()_+`1234567890-=QWERTYUIOP{}|ASDFGHJKL:"ZXCVBNM<>?qwertyuiop[
]\asdfghjkl;'zxcvbnm,./

Well this looked like a job for Regular Expressions.
Now I am no regex expert having only used it for simple pattern matching, I began working at this in a similar manner. Match all of those characters and concatenate the matching strings with spaces.

After hammering away I came up with:

public static string SanatizeInput(string file)
{
Regex reg = new Regex("[\\r\\n\\sA-Za-z0-9~!@#$%^&*()_+`\\-={} |:\"<>?[\\]\\;',\\./]*", RegexOptions.Compiled);
Regex line = new Regex(".*");
Match lineMatch = line.Match(file);
string output = string.Empty;
while (lineMatch.Success)
{
string cleanLine = string.Empty;
Match m = reg.Match(lineMatch.Value);
while (m.Success)
{
foreach (Capture capture in m.Captures)
{
if(!string.IsNullOrEmpty(capture.Value))
cleanLine += capture.Value + " ";
}
m = m.NextMatch();
}
if(!string.IsNullOrEmpty(cleanLine))
output += cleanLine + "\n";
lineMatch = lineMatch.NextMatch();
}
return output;
}


Which grabbed each line, then would loop through all the matches and add them together and insert in newlines.
In the end it worked.

But I was unhappy. It was far too verbose, and just seemed wrong.
My first hint was using ^ to negate a collection of characters.
My second was using the regex replace as opposed to concatenating.

The better solution:
public static string SanatizeInput(string file){
return new Regex("[^A-Za-z0-9~!@#$%\\^&*()_+`\\-={} |:\"<>?[\\]\\;',./\\s]").Replace(file, " ");
}

Wednesday, July 11, 2007

Automate your build

Doing things manually sucks.
Thats why we develop software, because people are sick of doing things the hard way.
Seeing as our job is automation, it amazes me that so many people are still developing software the hard way.

What am I talking about? Builds.

Right now at my office, whenever a change is made and we need to update our test sever, we must produce a build. And right now, we're using the VS2005 IDE, cleaning the solution, building the solution, and publishing the website by hand.

Furthermore, once that is complete, we have to go in and delete certain files from our published site, and then copy it over.

There are several markup languages for a task like this with the main ones being MSBuild and Nant. However if you want to skip all that, the process can be easily automated with a batch file.


cd\
cd "program files\microsoft visual studio 8\common7\ide\"
devenv /clean release "C:\Dev\MyProject\Project.sln"
devenv /build release "C:\Dev\MyProject\Project.sln"
rd "C:\Dev\Precompiled Webs\MyProject" /s /q
cd\
cd "WINNT\Microsoft.NET\Framework\v2.0.50727"
aspnet_compiler -v /Website -p "C:\Dev\MyProject\Website" "C:\Dev\Precompiled Webs\MyProject"
cd\
cd "dev\precompiled webs\MyProject"
del *.log /f /s /q
del *.pdb /f /s /q


lets look at whats going on


cd\
cd "program files\microsoft visual studio 8\common7\ide\"
devenv /clean release "C:\Dev\MyProject\Project.sln"
devenv /build release "C:\Dev\MyProject\Project.sln"


this uses the devenv command line to clean and build your solution without using the IDE


rd "C:\Dev\Precompiled Webs\MyProject"


This deletes the folder where the compiled site will need to go


cd\
cd "WINNT\Microsoft.NET\Framework\v2.0.50727"
aspnet_compiler -v /Website -p "C:\Dev\MyProject\Website" "C:\Dev\Precompiled Webs\MyProject"


Here we use the aspnet_compiler utility to compile the site.
-v is the virtual path (the name of your website within the solution)
-p is the path to your website
and the last path is where the compiled site will end up


cd\
cd "dev\precompiled webs\MyProject"
del *.log /f /s /q
del *.pdb /f /s /q
del web.config /f /q


Lastly, I want to remove any pdb and log files, as well as the web.config because our test server has a different config file from the development machine

Here are a few links that may help you with your batch file:
aspnet_compiler info
devenv command line info
MS-DOS commands