April 29,2001: Here's the third ACM
Programming Contest problem. In Chicken
Crossing you get a file with information about the size, speed,
lane, and time of arrival of some trucks and you must determine if
the chicken can safely cross the multi-lane highway or becomes a candidate
for a barbeque. This is the first, and probably the only, instance
of a console application that you'll find here. Console applications
run like the old DOS apps with text input and output, no mouse support ,
etc. All ACM contest programs run this way, for ease of scoring I
suppose. The only math required for this beginners program is
a little algebra and an understanding that speed=distance/time.
April 25, 2001: Time for another beginner's
program. Clock Angles has the
job of calculating and displaying the angle between the clock hands
given hour and minute values. 100 lines of code but only 60 user
written (20 to calculate and display the angles and 40 more to display a
clock face with the hands positioned properly.)
This program and the previous Token Flip program
are both based on ACM programming contest archives. What a great
source for programming problem material! ACM (Association for
Computing Machinery) and IBM sponsor the contest annually for college
students. Teams compete in regional competitions with winners going
on to the World Finals. A couple of thousand teams from a
thousand or so universities competed in the 2001 contest. 3-man teams have 5
hours to complete as many programmed solutions as possible from a set of
eight problems. Delphi was available for use at the World
Finals but I wasn't able to determine if any Delphi teams were
entered. I doubt it since academia remains hung up on C, C++, and
now Java. By the way, St. Petersburg University
(Russia, not Florida) finished first for the 2nd consecutive year and Virginia Tech. finished second. Way
to go guys, even if you didn't use the best
language. Flash! I just found a forum discussing
world champion St.
Petersburg University's wins and indicating that they are Pascal
programmers! Alright!
I wrote Clock Angles with a self imposed one
hour time limit to see if any of those old test taking skills
remained. I did OK but decided that a time limit does take
away a lot of the fun factor. The basic, non-visual solution
took 30 minutes so I guess it's time up the level and maybe do a
hard one in 2 1/2 hours.
April 20, 2001: We haven't had a game in a
while, so here's intermediate level Token
Flip. 16 tokens, black on one side and white on the other
arranged on a 4X4 square board. The objective is to flip the
fewest tokens to get all white sides up. The complication is that
when you select a token to flip, adjacent tokens above, below, left, or
right of the one selected also get flipped. User play and a
program solution are both implemented.
The puzzle auto-solve is implemented using the previously
posted TIntList integer list component to build a queue of
configurations for a breadth-first search. In the process, I
realized that the AddObject method had been omitted from the original
TIntList posting. A corrected version is included with Token Flip
source download and also on the original Delphi Techniques
page.
April 15, 2001: Here's a program I call Fences
and Traveling Salesmen. It illustrates
"connect-the-dot" graphics algorithms for
|
Simple Path - connect a set points with line
segments that do not overlap. |
|
Convex Hull - draw the smallest possible
fence around a set of points. |
|
Shortest Path - find the set of lines which
connects a set of points and has the shortest total
length. This is the "Traveling Salesman"
problem, a certified very hard problem to solve in the general
case. (The problem is to find a route for the traveling
salesman which minimizes the total distance traveled.)
This version checks 100,000 to 200,000 paths per second. about
a million times too slow to solve the problem for 15
"cities". Lots of PhD level work has
been done on this problem, mostly to find "good enough"
solutions in a reasonable amount of time. A few have been
proved to be optimal, including a route to visit all 13,900 major
cities in the U.S.A. |
Oh - a version of the Cannonballs
program that always knows when it hits the target was also posted
(See below for details of the problem). Also corrected
the coordinate calculations to move the ball more accurately.
The old version rounded each velocity increment to integers which
affected the path significantly in some cases.
April 12:2001: The math topic Intersecting
Lines is ready. A good algebra refresher with a downloadable
program that allows you to graphically define a couple of line
segments and then tells you if they intersect or not. Not very
impressive for 2 day's "work". Especially considering
that a frog has to do this in real time every time he catches a fly -
with the endpoint of one of the lines moving! Now that's
impressive! I wonder how long it takes the frog to learn the
trick. Does each frog have to write his own program? Or do their
little tadpole brains come pre-programmed? So many questions,
so little time. In any event, we're now prepared to fix the
Cannonballs program.
April 11: 2001: I posted a correction today
for the first of the bugs uncovered by granddaughter Kristen: In PrimeFactors1,
results will be invalid for numbers with prime factors exceeding 231
(around 2 billion). The problem was that the Factors array in
the U_Primes unit was defined as type integer (32 bit integers)
instead of int64 (64 bit integers). You can just change
that line in your source code, or download again.
A second bug is turning out to be more challenging.
She found that at certain angles in the Cannonballs program, the ball
would pass through the target without registering a hit. The problem
was easy to diagnose - the cannonball is moving a distance greater than
the width of the target in each time unit and so can pass
"through" the target between iterations. Saving the
previous position and checking when we get to the right of the target
would catch that case but I've decided to rewrite the whole
collision detection routine. Collision detection is a critical task
in robot path planning, ray tracing (for simulated lighting effects
in graphics) and in every action adventure game. It's also a
topic usually covered in senior and graduate level computer science
courses at universities, so there must be some interesting math in there
somewhere..
April 8, 2001: Here's the
Easter dates program just in time for this season. If you're a
Christian, or live in a country that gives you a day off on Good Friday,
you already know that Easter this year is next Sunday, April 15th.
But how about next year, or in 2010, or the year you were born?
It's a simple beginner's level program, even if a large
amount of labor has been spent in deriving the algorithms (not by
me).
April 5, 2001: We're back! Home
again after spending a couple of weeks with grandkids in Connecticut and
Alabama on spring break. I can report that precocious 11-year
olds can pick up on Delphi fairly quickly. In a few hours,
Kristen wrote "Hello World" and a version of the
"Cats and Mice" puzzle. I was setting over her
shoulder and providing vocabulary, but at the end she was diagnosing
"missing semicolon" and other simple error messages and was
using Object Inspector to modify properties on her own. We're
planning a Computer camp at Grandpa's for this summer. 11-year
olds also make good beta testers - I'll be posting some corrections in the
near future. (4-year olds on the other hand, are much more
interested in Hot Wheels Stunt Car Driver games)
For now, here's a
Word Ladder program that can change FLOUR to BREAD in 6 steps
and STONE to MONEY in 11. Another graph searching
program implemented with depth-first and breadth-first algorithms.
(Word Ladders are those change-one-letter-at-a-time puzzles so CAT to DOG
becomes CAT-COT-COG-DOG, for example).
|