What's New - April 2001


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).