euler

I bumped into a site that has mostly mathematical computer problems to solve. The site says that you can use any tools you want to come up with solutions. I use whatever i have at hand. That has included C, Perl, the shell, and my 25 year old HP-28C calculator. The problems are genearlly designed to require some computer programming. But some people have managed to solve some of the problems by hand(!). I have not, as yet, looked for hints elsewhere on the Internet, even though this is encouraged. The site suggests that computer programs can be written which take less than a minute to run.

At the time of this post, i've solved 36 of the over 300 puzzles. I don't attempt to limit computer time. If i get a solution, it's a solution. I expect that once i have a correct solution, it's code that will never run again, so there's not much point in optimizing the code. However, i like optimizing code...

Sometimes i make mistakes. But the system allows you to guess again if you get a wrong answer. One of the solutions i was writing had an estimated run time of a few hours. I ran it over night. But in the morning, it was still running. It turned out that there was an error, and it would never have finished. Opps. When i fixed it, i also noticed a way to speed it up, and the final version took about a minute. However, it took me a half hour to get the speed up working. I'm really just trying to get the total time spent down, except that i value my time over my computer's time.

One of the puzzles asks how many months start on Sunday in the 20th century. I could have done some calendar arithmetic (i've done it before). I could have narrowed it down with some math. But Unix (and Linux) have a calendar function, and it produces text, so how hard could it be in a shell script?

#!/bin/sh
for y in `cnt 1901 2000`; do
 for m in `cnt 1 12`; do
  cal $m $y | grep "^ 1"
 done
done

I ran this script with the output into "wc -l". The "wc" program is the Unix word count program. The "-l" option makes it count lines. So here's how it works. The "for y" loop counts years from 1901 to 2000, inclusive. That's the 20th century. The 20th century is almost the 1900's. That's because the 1st century is the first hundred years, from year 1 through year 100, inclusive. The 2nd century is from 101 to 200. Anyway, the "for m" loop counts the 12 months. "cal" is the Unix calendar program. It can take two arguments, the month ($m) and year ($y). The "|" (vertical bar) symbol tells the shell to direct the output of "cal" into the next program. The "grep" bit is the Unix search program. It stands for "General Regular Expression and Print". The regular expression is the "^ 1" bit. This expressions tells grep to only pass lines that start with a space and the number 1. It turns out that the calendar format for a month has dates right justified. If a date is "10", then there's no space before it. The default calendars have Sunday at the far left. So this little script spits out a line like this:

 1  2  3  4  5  6  7

for each month that starts with a Sunday. I run the output of the script into the word count program, having it count lines. The number of lines is the number of months that start on Sunday.

There's just one more little thing to describe. In the line "for y in `cnt 1901 2000`; do" there's a bit of syntax and a program. The syntax is the back quotes - the first just before the word cnt. The stuff in between the back quotes is a program with it's options, in this case cnt. This program is expected to print out a list, and the variable y gets set to each value on each loop. But the program cnt is something i wrote in the 1980's. It knows how to count up or down, with skips, with leading zeroes or spaces, with small functions taking the initial integer for a start, and can output in roman numerals and other formats. There must be solutions like it for other people, but this is what i've used. I've not released it to the public, for various reasons. So, if you want to use my solution, you'll have to solve this bit of the puzzle yourself.

Anyway, this solution produced an answer really quickly. It took more time to write this post than to write and run this program.

The site has a forum for each problem. Early solvers often post hints on how to solve or optimize solutions. And, often, these hints help you solve later problems. For example, there are a bunch of problems involving prime numbers. Having a good prime number test can be really handy. I peruse these and see if there's anything of interest.

This whole site is about education. A million years ago, i looked at the book 101 BASIC Games. These were games, written in the computer language BASIC. Not all of them worked. There were lots of different variants of BASIC when it was written. The programs were submitted by lots of different people using most of those variants. I studied a bunch of them to see how they worked. But it wasn't really a curriculum. The interesting thing about Project Euler is that it's more like a curriculum. Each of the problems requires a new skill or skills. The result is inductive chain learning. This can be an efficient way to learn. And, it's free.