I've now solved over 70 of the Project Euler site i mentioned a couple months ago. One of the problems i just solved was to generate solutions to 50 Sudoku puzzles. People solve these sorts of puzzles by hand all the time. I could have done it that way. I started by solving the first one by hand. It was pretty easy. I really only used one rule to make it happen. I thought about the rule for a bit, and decided it would be easy enough to code into a program, and that might be quicker than doing 50 by hand. And this first version solved some 29 of the 50. My program showed how far it had gotten. I used that to tackle the next unsolved puzzle by hand. And, indeed, i found an easy rule to code, and that version managed 39. From there, it might have been quicker to solve the last 11 by hand. Eventually, there were five ideas, and 46 problems were solved. One of the problems could be easily solved by hand from there if a guess was made of one of the two remaining possibilities for the cell. I decided to code in guesses. After making a guess, it would use it's previous system to see if it could get a solution. It continued to make a single guess until it either solved the puzzle, or it ran out of single guesses. All fifty puzzles were solved.
Total run time was difficult to get. What you'd like is the amount of time it takes to solve each puzzle. So, if you had a thousand puzzles to solve, you could multiply your time by a thousand and get a good estimate for how long that would take. But the total time was much less than a second. It's unlikely that the time would scale. It's quite possible that a thousand puzzles would also take less than a second.
Of notable interest is that nearly five thousand people have solved this problem. There are tons of programs that have been published that also solve this problem. So at least one person in a million, world wide, has written a Sudoku solver. That's a good deal more than i'd have expected.
Showing posts with label computer savvy. Show all posts
Showing posts with label computer savvy. Show all posts
Thursday, August 25, 2011
Wednesday, June 29, 2011
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?
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:
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.
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.
Wednesday, March 14, 2007
Passwords
Computer people (that's me) try very hard (sometimes with miserable results) to make software allow people to do things easily. That sometimes makes it easy for people to do things unreliably. If you don't know what you're doing, you still don't know what you're doing.
Security is one of those things you simply have to know. My advise: write all your passwords down on sticky notes and put them on your monitor. Sure, from a security standpoint, this is terrible. Anyone looking over your shoulder (even if your shoulder isn't there) could get into anything you can. But at least you'd know what you're doing.
I mean, are you really going to do what i do? I keep my passwords encrypted on my Palm Pilot. Not only is my Palm backed up, but i have an identical Palm that i periodically restore to. If the Palm is lost, no one will be able to get my passwords. If my Palm breaks (computers are not immortal, and portable computers are particularly mortal), then i can use my backup unit. If both are lost, i can buy a new one, restore to it, and get back on the air. If my backup computer is stolen, i can buy a new computer, restore from my off site backup, buy a Palm, restore to it, and i'm back on the air. When the Universe (Murphy) is out to get you, paranoid is just good sense.
Security is one of those things you simply have to know. My advise: write all your passwords down on sticky notes and put them on your monitor. Sure, from a security standpoint, this is terrible. Anyone looking over your shoulder (even if your shoulder isn't there) could get into anything you can. But at least you'd know what you're doing.
I mean, are you really going to do what i do? I keep my passwords encrypted on my Palm Pilot. Not only is my Palm backed up, but i have an identical Palm that i periodically restore to. If the Palm is lost, no one will be able to get my passwords. If my Palm breaks (computers are not immortal, and portable computers are particularly mortal), then i can use my backup unit. If both are lost, i can buy a new one, restore to it, and get back on the air. If my backup computer is stolen, i can buy a new computer, restore from my off site backup, buy a Palm, restore to it, and i'm back on the air. When the Universe (Murphy) is out to get you, paranoid is just good sense.
Subscribe to:
Posts (Atom)
Posts
