November 30: A palindromic number is one that
reads the same from either end, for example 12321 or
4554. Take any 2 digit number, reverse it
and add it to the original number. Is the number a
palindrome? If not, repeat the process until it
is. ((94+49=143, 143+341=484, a palindrome in 2 steps). Which
2 digit numbers require the most steps to a reach a Palindrome
Sum?
November 29: Three new clever logo
contest entries from Robert in South Africa were posted today.
Check them out and vote!
I also reposted 15 Puzzle #2 with a minor correction to the
hashing code. For very long solutions, when the hash tables
fill up, they are automatically expanded - in theory. Now it works in
practice too.
November 28: Whew! 15
Puzzle #2 is available. That was almost too much fun. It
solves most puzzles in some fashion, although optimal solutions turn out to
be very hard to calculate for large (5X5) boards. It was discouraging
to find a paper published in an Artificial Intelligence journal describing
the first 10 random 5X5 board optimal solutions ever found. Run times
were from hours to months and board configurations evaluated ranged from 8
billion to 8 trillion per case! I can guarantee that any
5X5's you solve with this program will not be optimal. But probably
still better than you can do by hand. In any event, after
50-100 hours of work, I'm ready to for a new (and simpler) problem.
November 16: I've been working on the auto-solve capabilities
for the 15 Puzzle all week. So far, it solves OK up to about 25
moves, but bogs down after that. The algorithm I'm using is one called A*
(AStar) which tries to find almost optimum solutions for hard
problems in a reasonable amount of time. I can't beat it in
terms of number of moves to solve - when it can find the solution.
But I can, by hand, at least always find a solution, optimum
or not, in a matter of minutes. I may add a 2nd
"Solve" button using more human-like techniques to handle
cases where AStar doesn't work well. I also need more work to
make sure that my current AStar implementation isn't buggy.
Fun, fun.
In the meantime, I posted the MinMax
problem today. It's a small mind bender, easy to answer with pencil
and paper, slightly more difficult to solve in your head. But
it does introduce a few coding techniques.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
November 11: The 15
Puzzle. This ancestor of the Rubik's Cube was popularized by Sam
Loyd, a well known puzzlist in 1870. Fifteen sliding tiles are moved
around a 4X4 board to produce a specified arrangement. The fact that
Loyd's set up instructions made the the puzzle unsolvable gave him lots of
press but no one ever claimed his $1000 reward for a correct
solution. What a surprise! This is version 1, with a
program smart enough to respond to your attempts to solve it, but too dumb
to solve the puzzle itself. I'm working to make it smarter
though. Maybe next week.
November 9: Seven
Coins is a little coin moving puzzle. The program is
probably more complicated than could be justified by the effort of
solving by hand. But it is an interesting exercise in how to
represent a graph in code.
I received an note from my son (an engineer) the other day
informing me of an error in the Knight's
Tour program. If you click the "Let me try" button
while the program is displaying its solution, bad things
happen. Engineers do make good beta testers. Corrected
code has been posted - instead of freeing and recreating the board
when the user clicks "Let me try", a flag is tested first and
flag is set to "manual mode". The auto-solving loop also
checks the manual-mode flag and stops solving if the user pressed
the button.
We have a new logo contest entry
from Rachel - a bright young lady whose father, James, runs the
excellent Delphi Programming Source Code site.
November 6: AirportSim,
an airport simulation program is available. It's a first step toward
future explorations of discrete event simulation (airports, banks,
gas stations, grocery stores, factories - anywhere people or things
show up for some service, get it, and leave). We
can even count the number of planes that run out of fuel while
waiting to land. (No lives were lost in the creation of this program.)
November 3: "Insert
+ and
- signs as necessary into the string 123456789 to form an expression that
evaluates to 100". I received this problem yesterday in
an e-mail from an 11 year old boy who says his teacher assigned it. I
told him that it would probably take me 2 hours to write the program, so if
he would spend 2 hours working on it and send me his closest solution, I'd
send him the program. I haven't heard back, but I couldn't resist coding it
anyway. How would you solve
it? Here's my solution, called
Expressions 100.
November 2: Uli from Switzerland, just let me
know that the Knight's Tour does not compile under Delphi 3.
Thanks Uli. Apparently D3 doesn't support dynamic arrays (arrays
that can change size at run time). I've made a version that
doesn't use dynamic arrays. If anyone else has the same problem, let
me know. There may be other programs posted that use dynamic
arrays or other features that didn't exist in earlier Delphi
versions. Please, let me know if you encounter problems using
downloaded source code.
November 1: Magic
Squares #1 generates Magic Squares of odd size (up to 51x51).
This a simple introduction to another interesting mathematical
niche. (Magic Squares, in case you have never seen them, are square
arrays of the integers from 1 to N2 arranged in an NxN matrix
so that each row, column, and corner-to-corner diagonal sums to the same
number. ) Another problem only made solvable because some
smart mathematicians developed an algorithm a few hundred years
ago.
|