|
|
Sun Mon Tue Wen Thu Fri Sat
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31
It's a really fun one to work out. Unless, of course, you happen to be in the circle. ;)
I found this page through the 2H home page with IQ, personality and entrepreneurial tests.
I am tempted to conclude from this that I live in a country that discriminates bright people, just because they are intelligent. The whole scholing system pays alot of energy in the low 5% of the students, but seems to be totally unaware of the upper 5%, as if it is a crime to be bright.
........................................................................... Notice To: Newsgroup Moderators, Managers or Vested Interest Subscribers. Due to HLD PUBLISHING limited list of Newsgroups, it is not our policy to remove a newsgroup from our list free of charge. To be removed from our list of future commericial postings by HLD PUBLISHING COMPANY an Annual Charge of Ninety Five dollars is required. Just send $95.00 with your Name, Address and Name of the Newsgroup to be removed from our list. Mail to: HLD PUBLISHING COMPANY, 1680 NORTH VINE STREET SUITE 1103, LOS ANGELES, CALIFORNIA 90028. ............................................................................ Furthermore, HLD PUBLISHING COMPANY reserves the right to cancel its own postings. Cancellations of our postings performed by outside parties will be charged a Ninety Five dollar fee per cancellation. A bill with proof of cancellations made will be sent to all parties involved, plus, it will automatically be sent to Attorneys Specializing in Collections nationwide and worldwide. HLD PUBLISHING COMPANY will protect and maintain its interest.I wonder who owns this newsgroup. Or should I charge them for posting unwanted commercial ads? (Was announced as spam)
|
For those of you interested in using programs to solve problems,
here is one I first saw a number of years ago in Games Magazine.
It is a fact that: 1^2 + 2^2 + ... + 24^2 = 70^2 Treat these as squares of size 1x1, 2x2, ..., 23x23, and 70x70. Place as many of the smaller squares into the 70x70 square to fill as much of the 70x70 square as possible without the smaller squares overlaying one another. What is the maximum area of the 70x70 square that can be filled? The idea is to write a program to solve this problem. I really don't have any good ideas about how to solve this problem using C or any other language. I would like to see any solutions posted to this group.
|
If you want to do this through a program it should be a program which tries to fit in the squares one by one, and uses a back-tracking algorithm.
But as there are so many ways to fit in the squares, it is impossible to find the maximum by trying all possibilities. Still I think it is possible to find a solution which comes close to the maximum.
Obviously you should start with the biggest squares, as that square takes up the most space. From there on you will try one smaller and so on.
For each square you want to place, you have to decided whether you are going to place it or not. It might be possible that with leaving out the 23x23 square you can place all the other sqaures, whereas putting it in, will force you to leave other squares out which might have a greater surface then 23x23. (If it is impossible to place a square at all you are forced to skip it.)
If you have decided to place a square, there are still many positions left, at which you could place it. Of course, you want to place it at a good position. A good place would be a position which would allow most of the other squares to be placed.
Now you have to come up with an algorithm for determing which is a good place to put the square. You do this by placing the square, and for all of the smaller squares you are going to check all the positions at which they can be placed. For each of this positions you add up some value depending on the size. The total sum of this gives you a rating. I would use x^2 (where x equals the size) as the way of calculating the value to be added.
After you have calculated the rating for all possible placings, you are going to try them one by one. This program will return many solutions. You just have to let it run as long as possible, and only keep the best solutions found so far.
Emmanuel Gaillot found the following formulea for this (as posted on rec.puzzles):
____ n
\
\ p!
/ -----------
/ i! (p - i)!
----
i = 0
In which n stands for the dimenstion, and p for the
number of cuts.
It was a very nice evening with some philosophical discussion (Meindert just got his philosophy (master) degree a few months ago, and one of the other friends is doing his Ph.D in philosophy, and the third friend is an artist, who made the art work (not: illustrations) for Meindert's master thesis), and drank some Belgium beer from a 3 liter bottle that Meindert had bought 3 years ago. The cork came out with a mild plop, and the beer had a very nice taste. Li-Xia and Meindert discussed some Chinese recepies, as Meindert loves cooking.
( follow-up)
We also bought an additional suitcase yesterday evening, which has a not-so-bright red colour.
The program uses a back-tracking algorithm, but is simpler than the solution I described before. It only tries to place squares in corners (made by the other squares and the outside of the big square). To test whether a square can be placed, it is sufficient to check whether the corner positions are free, because the squares are placed in decending order. The algorithm also has a cut-off build in which prevents the program to try solution for which it is known that they cannot result in a better solution than the one found sofar.
This problem is rather old. The first mention I know of is by Martin Gardner in the Sept. 1966 issue of "Scientific American". 24 of his readers found the 4851 solution - given that this was way back in '66, I guess they found these solutions without the help of a computer!
The basic 4851 solution is the following:
+----------------+-------------+----------------------+---------------------+ | | | | | | | | | | | | 11 | | | | | | | | | 16 | | | | | +-----+--+----+ 22 | 21 | | | | 2| | | | | | 5 +--+----+ | | | | | | | | +----------------+--+--+ 6 | | | | | 3| | | | | ++-+-------+ | | | || | ++--------------------+ | || 8 +----------------------++ | | 18 || | | | | || | | | | ++---------+ | | | | | | 20 | | | 9 | | | +------------------++ | 23 | | | || | | | | ++----------+ | | | | | +---++---------------+ | | | | || | | 17 | 10 | | 4 || | | | +---------------+-------+---++ | | +-+---------+---------------+ | 15 | | | | | | | | | | | 12 | | +------------------+-+ | +-+-------------+ | | | |1| | | | +------------+-+ | | | 24 | | | | | | | | | 19 | | 13 | 14 | | | | | | | | | | | | | | | | +--------------------+-------------------------+--------------+-------------+Variations on this can be found by swapping squares 17 and 18 and rearranging squares 1 to 10 (except 7, of course). He got this solution from the geometry section of the rec.puzzles archive.
The modification is basically to prune the search tree by also computing space wasted due to narrow corridors on the board. For instance, if we place two squares like this:
+----------+x+--------------+
| |x| |
| |x| |
| |x| |
| |x| |
| |x| |
+----------+x| |
| |
+--------------+
all the spaces marked by "x" are wasted (except one, where we might place
the 1x1 square.)
However, I implemented this corridor computation in an overly pessimistic way (i.e., what I compute as wasted due to corridors is <= what is really wasted), so the program still tries too many possibilities.
Yet it found a fairly good solution. After 1 hour and 3'218'177 different positions, it found the following 4836 solution, using all but the 8x8 square:
+-----------------------+----------------------+---------------------++ | | | ++ 1 | | | | | | | | | | | | | | | | | | 23 | 22 | | 24 | | | | | | | | | | | | | | | | | | | | | +-+-------------------++ | +----+-----------------+-+ | +------------+----------+----+ | | | | | | | | | | | | | 14 | 15 | | | | | | | 21 | | | | 20 | | | | | | | +-----------++ | | | | ++----------+----+ | | | | | 4 | | | | 13 | +----+----+-----+-+------+---+----------------+ | | 12 | | 6 |2| | | | | | | +-+ | | | | | 9 +--+--+-+ 11 | | +-----------+-----+-----+ | 3| 5 | | | | +-----+---------+--+ | | 17 | | | +----+----------+ | | | | | | | | | | | | | | | | | 19 | | +---------+------+ | | 18 | 16 | | | | | | | | 7 | | | | | 10 | | | | | | +------+ | | | | | +-----------------+------------------+---------------+---------+After that, it didn't find a better solution for 14 hours. It's still running... up to now, it has checked some 36'000'000 positions.
As you can see, my placement strategy still has a few bugs: it should never have placed the 22x22 square as it did. The only correct way to place it would have been in the upper right corner. (Not that it makes a difference for this solution, but clearly this makes the program try far too many positions.)
Also, I'll have to make my corridor computation more accurate, since this tremenduously cuts down the number of positions to be tried once a fairly good solution had been found. It seems to me that it still would be a good strategy to first try those placements which do not create any narrow corridors. Also, because we know a good solution, we good force the program only to search to solutions that are equally good or better, creating a stronger cut-off.
After seen the best known solution, I have been thinking about a different strategy. Maybe the program should not start with the biggest square first, but fill up empty squares from the inside to the outside, and for each empty (1x1) square try to find the best fitting square.
Thomas Wolf also created a page about this problem.
We have been busy some days with packing the suit-cases. If you travel to relatives in China, it means you have to bring a lot of presents. If we didn't take any diapers with us, probably half of our load would have been presents.
Tomorrow we are flying to China. Our suitcases are packed, yesterday evening we checked all the papers (including the money and travel cheques).
We haven't gone outside, but from our car trip from the airport to home, I know that many things have changed compared to our previous trip in 1993, when we came here on our honeymoon. Many things look more mordern, but I get the feeling that much of the rubbish remains. The distance between poor and rich is becoming more obvious. Just on the otherside of the street outside the compound we are staying on they are building a sky-scraper of 36 floors.
Xuan Xuan, my 7 year old nephew is watching me type this on the T1000 laptop I have brought with me.