Delphi For Fun Newsletter #27
Wednesday June 19, 2002
Seven weeks have flown by since the last newsletter. We have managed to crank out several interesting programs and grandkid visits are start tomorrow, so I guess it's time to send a newsletter update. A black bear wandered across our yard earlier this week - it was the day after returning from a week's absence so the place was starting to look abandoned. Only the second time in 10 years that we have seen bears around the house. Anyway, we'll have to schedule a few bear etiquette sessions with the kids when they arrive, and make sure they take the dog along for company when they go exploring. So there are a few negative features of life on a mountain, just not many.
Search engines are indexing many DFF site items these days - we get 500 hits per day with 100-200 coming as search engine referrals. Home page visits have passed 20,000! This week we added Bonny Kate Elementary School in Knoxville to our Accelerated Reader Book Search pages. Bonny Kate - what a cool name!
All in all, life is good and we're still having fun!
Here are the "What's New" items since last time:
May 1, 2002: Someone asked me the other day if 8 solutions to the standard Eight Queens problem could be placed on a chessboard so as to occupy all 64 squares. I didn't know the answer, but I do now. Even better, I got to implement the clever Niklaus Wirth algorithm while solving the problem. Wirth's technique is one of those "lateral thinking" solutions that makes you say "Wow! I wish I had thought of that". The source code for EightQueens_Wirth is now available on the previously published EightQueens Plus page. Just scroll down to the addendum section
May 3,2002: Macro Cantu, Delphi guru and author of several excellent books, has just made an introductory text, Essential Delphi, available as a free PDF file download from http://www.marcocantu.com/edelphi/. There is also a downloadable file of associated Delphi source code. I haven't been through the entire book yet, but if you're a beginner, and maybe even if you are not, it's definitely worth a look.
May 6, 2002: Here is the first version of Four In A Row - an extended version of Tic-Tac-Toe that is played on a 7 by 6 board, requires 4 markers in a row to win, and has the added restriction that columns must be filled from the bottom up. This is the human vs. human version. If things work out, we'll build on this framework to add computer play in a week or two.
May 9, 2002: This year's World Championship ACM Programming Competition was won by a team from China. Three man teams had five hours to work on eight problems sharing one computer. I glanced at the problems and decided I might get the easiest one (problem #1 I think). The competitors were the best 64 out of 3000 teams from 1300 universities, so they are some pretty sharp cats. I'll be interested in seeing detailed results when they are available. Here's a link to more info.
May 10, 2002: Here's a beginner's level program that solves a problem with a stack of cannonballs, technically a square pyramidal pentahedron. (A pentahedron is a solid with 5 surfaces.) How big would the stack have to be before you could rearrange the balls into a single square layer? Pentahedral Cannonball Stacks will give you the answer with a dozen lines of user written code. (I've included Version 2, about 50 lines longer, which also draws a larger copy of the picture you see here.)
Also, I ran across a well written article at delphi.about.com discussing considerations and techniques when resizing forms for various monitor resolutions. When possible, I've tried to avoid the problem here by restricting form sizes to 640 by 480 pixels. It would be nice to seamlessly scale the forms up to larger screen sizes and there are components that apparently do the job. They just aren't a standard part of Delphi (yet).
May 14, 2002: Thanks to Francis M. for catching a couple of bugs in the source code for posted programs. Towers of Hanoi 2 and Towers of Hanoi 3 both used the integer edit component, TIntEdit, but it wasn't included. I've since decided that, in general, it's not a good idea to require specialized components in other distributed programs and I have generally stopped using them. I just changed TIntEdit components back to TEdits in the two tower programs and reposted them. While at it, I changed the ring animation in Tower 3 so that rings now move up off of a peg, across to the receiving peg and then down. Previous animation had used magic rings that could pass right through the pegs as they moved in a straight line from one position to the next.
Also the beginner's Cannon simulation program had a reference to Unit1 in its Uses clause, even though Unit1 was not referenced or required. I had renamed Unit1, but somehow the Uses clause hadn't been updated. So that program has been corrected and reposted also.
Thanks again Francis. for taking the time to email me. To all viewers - you can help make this site better if you emulate Francis and let me know when you find something that doesn't work. I'll appreciate it.
May 26, 2002: It has been a long "one or two weeks", but here at last is Version 2 of Four In A Row that was promised back on May 4th.
This version adds a number of features including:
The program looks for good moves using the "Knuth/Moore NegMax variation of the alpha-beta minimax game tree search algorithm ". Whew! I pretty much understand it now, but I 'd be embarrassed to tell you how many hours were spent debugging those crucial 75 or so lines of code. The result is a fairly playable game that still leaves plenty of room for enhancement. Would-be Computer Science students, have at it. I'm going to work on beating the program when its IQ is set to 120.
May 30, 2002:
We're taking a break after last week's marathon to
finish the Four In A Row program. Let's build another
of our number t-shirt series. Here's,
T-Shirt #4, which finds the "smallest prime that
remains prime when added to its reversal". Only 30
lines of user Delphi code here!
May 31, 2002: A viewer from the Netherlands, informed me today about a possible enhancement to the Expressions100 program originally posted in November ,2000. The problem was to: Insert + and - signs as necessary into the string 123456789 to form an expression that evaluates to 100. Mark pointed out that allowing a leading minus sign generates one extra solution. Sure enough, with this change, there are 12 ways instead of 11. This is equivalent to specifying the digit string 0123456789 in the problem definition, so it's not exactly the same problem. But still interesting enough that I've replaced the original version with Expressions100B that has this "feature".
June 3, 2002: Here's an Equation Search program that can be quite challenging to play. Given four sets of four numbers each, find an arrangement of the numbers combined with two operators to form an equation of the form (N1 op1 N2) op2 N3 = N4 that is satisfied by each of the sets of numbers. Operator choices may be restricted to from1-4 operator types chosen from +, -, ×, and ÷. Problems are randomly generated by the program. Use all four operations and allow number values up to 99 and it can take a while to "unlock the code".
June 18, 2002: The Traveling Salesman Problem is interesting because it is easy to state but hard to solve. Given a set of cities, plan a roundtrip for our salesman that visits all the cities and minimizes the total distance traveled. This turns out to be a very hard problem because of the explosion of possible paths as the number of cities increases. Examining all paths is probably only practical up to 13 or 14 cities. Above that number we need heuristic algorithms that give pretty good results. Lots of academics are spending lots of time finding better solving techniques with some success, but you won't find that code here. You can try your hand at beating the heuristics in my Traveling Salesman Program. Or benchmark your computer by timing an exhaustive search for a 13 city path.
"I care not what others think of what I do, but I care very much about what I think of what I do! That's character!" -- Theodore Roosevelt
"The truth of the matter is that you always know the right thing to do. The hard part is doing it." -- General H. Norman Schwarzkopf
"You can't build a reputation on what you're going to do." -- Henry Ford
To subscribe or unsubscribe from this newsletter, visit http://delphiforfun.org/newsletter.htm
20,020 home page visitors!