Archive for June, 2008

Project Euler 10: Sum of First Primes

In the post about Project Euler 7, I described how to obtain a list of primes. These are not enough: the last one is 1,299,827, and we need all up to 2,000,000. The first 1,000,000 prime numbers can be found at the same site. Here is a ZIP file of the 1,000,000 first primes. Download the file, unzip it and format it as in problem 7.

Summing the first ones is fast and simple. This Perl script does it well:

1
2
3
4
5
6
7
8
9

my $sum = 0;
open( PRIMES, '<', 'dat/primes-1000000-first.txt' ) or die $!;
while ( <PRIMES> ) {
        chomp;
        last if $_ >= 2000000;
        $sum += $_;
}
close( PRIMES );
print $sum, "\n";

Project Euler 7: The 10001st Prime Number

This mission can be solved by calculating lots of prime numbers. However, we do not want to put extra effort into our solutions, do we? After a bit of searching, I found a list of the 100000 first prime numbers (100008, actually). I saved this file. Unfortunately, it is not in an optimal format. I wrote a short Perl script that creates a new file, in which each prime number is on a separate line:

1
2
3
4
5
6
7
8
9
10
11
12
13

# read the file from utm.edu
open( PRIMES, '<', 'dat/100000.txt' ) or die $!;
# this is the file that we will write to
open( TO, '>', 'dat/primes-100000-first.txt' ) or die $!;
while ( <PRIMES> ) { # for each line
        for ( split / +/ ) { # split, separating by spaces, and for each piece
                if ( m/^\d+$/ ) { # if it is a number
                        print TO "$_\n"; # print the number to the file
                }
        }
}
close( TO );
close( PRIMES );

Of course, you need to replace the filenames.

Now, it is a piece of cake to find the 10001st prime number. Just do:

head -10001 dat/primes-100000-first.txt | tail -1

Which finds the 10001 first primes and outputs the last one of them.

Or you could open it in notepad and start counting rows.

Project Euler 9: Pythagorean Triplets, Sum=1000

There is exactly one Pythagorean triplet (a^2+b^2=c^2) in which a+b+c=1000. Since all terms are positive, we can try all alternatives for 0 < a,b < 1000, which is less than 1000^2. This Perl script does it all:

1
2
3
4
5
6
7
8
9
10
11
12

# first, generate pairs of a and b
for ( my $a = 1; $a < 1000; $a++ ) {
        for ( my $b = $a; $b < 1000; $b++ ) {
                # c is then calculated from these
                my $c = sqrt( $a*$a + $b*$b );
                if ( $a+$b+$c == 1000 ) {
                        # print and exit if we found the answer
                        printf "%d*%d*%d=%d\n", $a, $b, $c, $a*$b*$c;
                        exit;
                }
        }
}

There is probably a faster solution without a square root, but this one is fast enough.

HBH Basic Web 7: Encrypt ASCII Cookie

Basic web hacking mission 7 of the Hellbound Hacker series is a prime example of why I dislike their “hacking challenges”. Some of them are not about hacking!

This time Mr. Deitry decided to make a cookie login script and he said he decrypted it from ASCII encryption, and for you to login you need to encrypt it. And after you login there is another login but its a Login that uses SQL databases, but he thinks that the SQL login page is vulnerable to a simple SQL injection, and when he gets back from his vacation he would fix it.

In this mission, whatever you do, don’t try to think by yourself! Instead, follow the instructions blindly. Upon inspecting the cookies set by this mission, for which I recommend the Firefox plugin Add N Edit Cookies, we find two of them:

username=sam
password=jillisdead

We are asked for the username. I tried a lot of methods on this one. I used the username “sam”, and I changed the value of the “username” cookie to my username. No matter what I tried, I could not solve it. So I read the mission description again. Mr. Deitry “decrypted it from ASCII encryption, and for you to login you need to encrypt it”.

For some reason, the value of the cookie set needs to be changed, regardless of who was logging in! Please disregard that this mission has no connection whatsoever to reality. What sane login system would require such actions from its users?

What is meant by “ASCII encryption” is the corresponding, binary ASCII values for each character. This would be the same as “Unicode encryption”, since the first 128 characters are the same for both ASCII and Unicode. To find what “sam” is when ASCII encrypted, google for things like [ascii to binary]. When you have found that, edit the “username” cookie to the encrypted value, e.g. 101010101010101010101010. When that has been done, you can login with the previous username.

To bypass the next field, you must only remember that the mission text talked about an SQL injection. First, check what error message you get when putting an apostrophe in the field.

Congratulations! The server-side check for successful SQL injections isn too advanced.

Reading AdSense CSV in Perl (UTF-16 Problems)

I was trying to write a Perl script for analyzing a CSV file. It was generated by Google AdSense and contained lots of statistics. Naturally, I started by reading the file:

open( CSV, '<', 'adsense-report.csv' );
while ( CSV ) {
    # handle each line
}
close( CSV );

However, upon trying to match each line with a regular expression, I found that it was not possible to match several characters in a row. Only very simple regexps such as m/5/ worked! After some research, I found the problem:

$ file adsense-report.csv
adsense-report.csv: \012- Unicode text, UTF-16, little-endian

Apparently, Perl assumed some other encoding. I changed the second argument of open():

open( CSV, '<:encoding(utf-16)', 'adsense-report.csv' );
while ( CSV ) {
    # handle each line
}
close( CSV );

It now works well. Unfortunately, I receive two errors of “UTF-16:Partial character”, which I cannot seem to solve.

Scrabble Analysis with Perl

A while ago, I started playing lots of scrabble. The scrabble game in the Ubuntu repository (by Brian White) records all games in the file ~/.scrabble-games. The following perl script analyzes the file and creates statistics for your games.

#!/usr/bin/perl
 
use strict;
 
my $mode = shift @ARGV;
unless ( $mode ) {
        print "arg: (freq|gen|score|size)\n";
        exit;
}
 
chdir;  
open( LOG, '<scrabble-games' ) or die $!;
 
my $yourwords = 0; 
my ( %wfreq, %wscore );
my $numgames = 0;
 
while ( <LOG> ) {
        chomp;
        if ( m/^level #(\d); computer rack: "([A-Z]*)"; player rack: "([A-Z]*)"$/ ) {
                $numgames++;
        } 
        if ( m/My Words/ ) {
                $yourwords = 0;
        } elsif ( m/Your Words/ ) {
                $yourwords = 1;
        } elsif ( $yourwords ) {
                while ( m/[^a-z]([a-z]+)\((\d+)\)/g ) {
                        $wfreq{$1}++ if length $1 > 2;
                        $wscore{$1} = $2 if length $1 > 2;
                }
        }
}
close( LOG );
 
my @freq = sort { $wfreq{$a} <=> $wfreq{$b} } keys %wfreq;
my @size = sort { length $a <=> length $b } keys %wfreq;
my @score = sort { $wscore{$a} <=> $wscore{$b} } keys %wscore;  # TODO: no hash needed; calculate score from word and ignore bonuses
 
if ( $mode eq 'gen' ) {
        printf "No of games:\t%d\n", $numgames;
        printf "Longest:\t%s\n", join( ', ', &liststart( reverse @size ) );
        printf "Most used:\t%s\n", join( ', ', &liststart( reverse @freq ) );
        printf "Highest score:\t%s\n", join( ', ', &liststart( reverse @score ) );
} elsif ( $mode eq 'score' ) {
        for ( @score ) {
                printf "%d\t%s\n", $wscore{$_}, $_;
        }
} elsif ( $mode eq 'freq' ) {
        for ( @freq ) {
                printf "%d\t%s\n", $wfreq{$_}, $_;
        }
} elsif ( $mode eq 'size' ) {
        for ( @size ) {
                printf "%d\t%s\n", $wfreq{$_}, $_;
        }
}
 
sub liststart {
        my @t;
        for ( 1..5 ) {
                push @t, shift;
        }
        return @t;
}

Call it with one of the arguments freq (for most frequently used words), score (for best-scoring words), size (for longest words) or gen (for a summary). Note that only your words are counted, not your opponent’s.