Delphi For Fun Newsletter #51
December 9, 2008
It’s time, past time, for our “quarterly” newsletter updating subscribers about what has been happening here at DelphiForFun. As usual, we’ve had a good variety of problems to work on these past few months. Cracking the complete solution to “Kirkman’s Schoolgirl Problem” in September was a high point for me since it had been nagging me since I first worked on it in 2004. The low point was no doubt when our host site, EasyCGI.com, did a deplorable job of migrating DFF and hundreds of other sites to a new server system in November. You can read a summary below.
On the personal side, we have our deer in the freezer for another year. Grandson Jeff came down from Connecticut and got his first deer on the 2nd morning of hunting. We were both happy. I’m not sure his sister will be so happy when she comes home from college for Christmas and finds a deer “souvenir” hanging from the rear view mirror of the car they share !
Here is a summary of and links to programs posted since the previous newsletter.
August 11, 2008: The Delphi StringGrid control is handy for displaying table data and game boards on the screen. Unfortunately, printing them is either easy but not very flexible (Form Print procedure) or flexible but not very easy (my PrintPreview unit), depending on the method chosen. Today's posting, PrintGridTest in the Delphi techniques section of DFF introduces PrintGrid procedure that is somewhere in between.
August 19, 2008: A couple of updates this week:
Our CuttingStock application designs a strategy to minimize costs for cutting parts of specified lengths from stock of specified lengths. CutStock Version 3 sorts the input parts list by input part length before solving and improves the graphics rod display when a large number of short parts are cut from long stock. These changes allowed a solution to be found for a user submitted case with a large number of different part lengths (19) and wide range of part lengths (134 to 6004).
ReactionStats Version 2 adds some Student's T-Test statistics to the output display along with more text explaining the results. This program analyzes results from our reaction time measuring program. I'm excited because a biology instructor at a community college is interested in using the program to introduce students to statistical analysis of sample data. What a novel approach! I'll be supporting in any way I can to help her get the concepts across. The attached sample data file used for testing indicates that my mean response times have increased by 0.03 seconds in the last 4 years. Worse, there is a 95% chance that the difference is significant and that I am indeed slowing down! I was hoping that it was just my imaginationJ.
August 22, 2008: Viewer Sadanand wrote recently challenging a statement I had made about there being only one tie game for the 6x6 version of Martin Gardner's game of "HIP". (First to form a square loses, and "squares" are not "Hip")
Actually the statement was Gardner's and he later modified to "essentially" only one tie game based on additional feedback to his Scientific American column which introduced the game. The game appears in his Dover book My Best Mathematical and Logical Puzzles available from Amazon.
found three additional tie games, one of which matched Gardner's by
rotating and reversing colors. The others cannot be so transformed. We
settled on three essentially different tie games.
HIP Version 3 replays the three tie games as well as adding
5x5 and 7x7 game sizes and the ability to retract moves.
August 27, 2008: While updating the game of HIP last week, I ran across a note about a suggested rules variation that would make the game more interesting. In the original game, with players A and B alternating moves, player B has a large advantage because he can often play symmetrically opposite to A's move and guarantee that A will complete a square first and lose. In the variation, posted as HIP Version 4, each player, after the initial move by player A, must select two points and still avoid forming a square. It appears to make the game, especially the 6x6 version, much more fair.
September 3, 2008: Kirkman's Schoolgirl Problem asks how to line up15 girls in 5 rows of 3 for each day for a week in such a way that no girl walks in a group with the same girl more than once during the week.
I coded a solution to the problem several years ago but it had two defects. It was slow, and it did not identify the 7 essentially unique solutions to the problem. Two solutions are considered to be the same if one could be converted to the other by rearranging the girls within one or more days or the sequence of daily arrangements could be changed.
A recent paper introduced me to the Tabu search technique and led to today's Kirkman Tabu program which finds solutions at the rate of a couple per second. I also incorporated some old but previously un-posted code that searches for isomorphic cases and now finds the 7 distinct solutions in a few minutes.
September 9, 2008: For what it's worth, I spent the last 6 days working on the algorithm which checks two solutions to Kirkman's Schoolgirl problem to see if one is really a disguised version of the other (“isomorphic” is the mathematicians word). There are only 7 distinct cases and all of the other millions of solutions map to one of the these. I didn't improve it much, but I did add a page to Kirkman_Tabu V3 which helps understand how it works. It probably won't solve global warming, but it was a fun and challenging way to spend some spare hours.
September 25, 2008: I spent a few days this week thinking about applying the "tabu" search used in the Kirkman's Schoolgirl problem to the "Cutting Stock" problem (determine the best way to cut parts of required lengths from stock with given lengths and cost). As a preliminary to help study the process, program "Manual Cutting Stock" was posted today. It allows the user to select from all possible cutting patterns and specify how many of each pattern to cut. The objective of course is to get all the required parts at the lowest cost. So far I have not been able to beat the original "Cutting Stock" program available from the same web page. Both programs read and save test cases in the same format, so checking the quality of a result is easy. My main conclusion to date is that the manual version would make a challenging puzzle game!
September 29, 2008: Numbrix™ is a puzzle currently (September, 2008) being published in the "Ask Marilyn" column of the weekly Parade Magazine and daily in the "Fun and Games" section of the Parade Magazine website.
board is a square array of cells, 7x7, 8x8, or 9x9 in puzzles seen so
far. For a puzzle with N cells per side, the objective is to fill the
cells with integers from 1 to NxN contiguously with each number after
the first adjoining the next lower number vertically or horizontally.
Some of the numbers are pre-filled and the user's additions must
interface with those to keep the entire number chain in proper order.
Numbrix programming exercise posted today, saves paper and your
eraser as you solve the puzzle, and provides hints or solves the entire
puzzle for you.
A Numbrix Puzzle
October 4, 2008: Here's an update to our program that calculates the shortest distance between two given points on the earth's surface. Lat-Long Distance Version 2 adds an implementation of Vincenty's algorithm (Vincenty's Inverse) that calculates distances with an error of less than 0.001 inch! More significantly, the program also implements the original version of the algorithm (Vincenty's Direct) that calculates end point coordinates for a great circle route given a point together with an initial bearing and a distance.
October 9, 2008: Last week's Numbrix™ posting led to this week's project, a Numbrix™ Puzzle Generator. This link is to the Numbrix™ page; the generator is available as a separate download links at the bottom of the page. The program implements a "connect the dots" generator which finds random paths connecting all points in a square array with all turns at right angles and no crossings. By numbering the dots and pre-defining those to be shown a clues, a file can be saved in the format expected by our Numbrix™ solver.
October 16, 2008: The "Josephus problem" requires that the player position himself so that he is last selected in a circle of N soldiers when every Kth "soldier" is eliminated starting the count at some known position 1. Josephus Version 2, posted today, adds the ability to solve the inverse problem. The final position is known along with N and K, and we must calculate where to begin the count for the selection process.
make position 6 the final selection in a circle of 7 Smileys when
selecting every 4th, start counting at position 5. So far numbers 1, 5,
and 3 have been eliminated. in that order The rest of the elimination
sequence is 2, 4, 7, and 6.)
October 21, 2008: I try to average posting a new program or version each week. Other chores have limited my spare time this week, but yesterday's "Puzzler" from the PBR radio show, "Cartalk", came to the rescue with a problem that could be solved in a couple of hours of programming. It would probably take less than that to solve it manually, but programming is more fun! Here's the puzzle:
Sally invited 17 guests to a dance party at her estate in the Hamptons. She assigned each guest a number from 2 to 18, keeping 1 for herself. At one point in the evening, Sally noticed the sum of each couple's numbers was a perfect square. Everyone was wearing their numbers on their clothing. The question is, what was the number of Sally's partner?
Go to the Perfect Square Dance page to download the source or executable that solves the problem or to read about my approach to solving it.
November 1, 2008:
How many times does the digit 1 appear in all of the integers from 0 through 999,999? More times than I thought when I tried to answer the question manually. Here is a simple 30 line Beginners Delphi program, HowManyOnes, that illustrates two ways to answer the more general question (How many occurrences of any given digit within any given range?). By the way, if you download the source file, you'll find about 90 lines of code but 1/3 are blank or comment lines and 1/3 are generated by Delphi itself as controls used were dropped on the form.
November 10, 2008: A couple of utility program updates were posted today to satisfy user requests:
Copy Folder Test Version 2, copies files matching a file mask from a given input folder to a given output folder. It is now possible to ignore the folder structure for files from sub-folders of the selected input folder and to copy all files directly to the same single output folder.
Large Files Version 3 lists the 100 (or other number) largest files on specified disk drive. This version adds date modified information and the ability to save the list to a CSV text file for importing to Excel or elsewhere. .
November 11, 2008: (11:00AM EST) Our host site, Easycgi.com, is migrating DFF to a new server. In the process, email has stopped working, temporarily I hope. They are working to fix it, but in the meantime, if you get "Recipient rejected message" errors, try again later (or tomorrow). It also appears that some website formatting has been lost. I'll post again when things get back to normal.
November 12, 2008: Email appears to be working again but the web pages that execute programs (the "feedback" page, the Newsletter "subscribe" page and the Booksearch "Search" pages) are broken. I have set up temporary email addresses for use for feedback and subscriptions, but I do not have a workaround for the AR Booksearch pages. I think it just a matter of our host, EasyCGI.com, setting the correct permissions to allow the programs to run . I have submitted a trouble ticket for them to do so. Hopefully we can get it resolved today.
November 16, 2008: It appears that the booksearch application and my form email applications will never run again on our current host ,EasyCGI.com. Those apps represent my few forays into online programming a few years ago. They used Delphi Internet components which ran as executable files. Executables represent some hazards to host servers and so it is difficult to find hosts willing to run them. I don't blame them - I do blame EasyCGI for not vetting my applications before migrating and breaking them without prior warning.
In the long run, I doubt that I'll be motivated to learn .NET, ADO, ASP.NET, CDONTS, and a bunch of other acronyms and concepts that hold little interest for me. If anyone out there knows this stuff and wants to volunteer to convert them to one of the "safe" technologies, I would be grateful. Until then, I am trying to get EasyCGI to fix a FrontPage parameter problem that would let the Newsletter and Feedback pages work again. I have written a version of the AR Booksearch program that will run on user's PCs after they download the searchable file for a school. And I have a really neat version of an Accordion Solitaire card game program which was interrupted by the migration mess that I would like to get back to.
November 22, 2008: After 10 days of work, most of the items broken by EasyCGI's migration of the website are working again, albeit not as satisfactorily as before. They seem not to have spent much time considering, and zero time testing, the impact of the migration on users in spite of the promises otherwise. A few examples,
1. Besides not checking or notifying me about the policy change to stop allowing CGI executables, they:
2. Changed log file location and format without notice breaking my internal application that tracks website downloads. They are still saving the log files zipped with ".gz" suffix and with every archived log file having the same file name! I can't make them understand that ".zip" is the format supported natively by Windows and, if they must use some Linux program format, they should at least use unique file names!
3. Eliminated "email pointing" which required setting up a new email addresses with no way to forward emails from old to new mailboxes ,
4. Changed the "last modified" dates all of the migrated files to the migration date (November 11), so I can longer tell when my last real changes were made.
All-in-all a very disappointing experience which appears to have been "planned" and implemented by the technicians. Nothing against the technicians, I suppose I am one, just one with 40 or 50 years of experience on most of those guys. (Check http://www.vistainter.com/reviews/E/easycgi.com/ or a number of other sites for reviews by people who much worse off than I; people trying to make a living using EasyCGI. People who depended on them are being driven out of business with migration horror stories worse than mine.)
November 23, 2008: Back to the fun stuff after our web-site woes. Here is one for Delphi programmers - a Fast Highlighting demo program which avoids modifying the formatting attributes of a rich edit control by hooking into the windows procedure which paints the visible window and adding the highlighting as each window is displayed. Since we only repaint highlighted portions of the window, we can't change the width of the text, but within that constraint, it has the advantage of being very fast.
November 25, 2008: Time for one more little "Delphi Techniques" entry before Thanksgiving holiday here on Thursday. Here's a program which knows how to Play MP3 Files based on which sentence within an Rich Edit control is clicked.
December 3, 2008: A small change to the Intersecting Lines test program today. Version 3.1 fixes a problem where lines with large X values were not redrawn correctly. We now have 7 updates posted since the original version in 2001, probably more updates that any other program on the site. It's a good example of how competent our visual image processing system is compared to digital processing.
December 5, 2008: Today I posted Version 3 of our CopyFolder program which copies all or selected mask files from one location to another. There's an option to replace files in the destination only if the source date is newer, but the date test was based on file creation dates. Today's update changes the test to use "Last modified date" which makes more sense in most cases. I also corrected a situation where the chosen destination folder was a subfolder of the source folder and the option was set to copy subfolder files. Oops - this set up a loop situation treating newly copied files as source files and copying them over (and over and over ...). A test now ignores the destination folder file when selecting files to copy.
December 8, 2008: Grandson Nathan, who's now 4, is into mazes During his visit over the Thanksgiving holiday, I generated some simple and some not-so-simple mazes for him using my Maze Generator Program. One was the "NATHAN" maze made up of the 6 letters connected into one long maze with a solution path over 600 rooms long. He hasn't solved it yet; in fact I discovered that rooms were too small when scaled onto a single printed page and it did not print very well across multiple pages. Version 3 posted today improves the printing and scrolling of large mazes. Grandma just pasted up and mailed him an 8 x 30 inch version!
added support for keyboard arrow keys in addition to mouse click/drag
movement to trace out a solution path. Keys work better for 4-year
I know the price of success: dedication, hard work, and an unremitting devotion to the things you want to see happen: Frank Lloyd Wright (Architect)
Let me tell you the secret that has led me to my goal: my strength lies solely in my tenacity. Louis Pasteur (Scientist)
To subscribe or unsubscribe from this newsletter, visit http://delphiforfun.org/newsletter.htm
259,000 home page visitors since Sept 2000. 346,000 program downloads in the past 12 months!