Resistance is futile

It's a matter of Faith

2012-02-28T09:36:00.000+11:00

Yesterday, a friend of mine who defines himself as a creation-believing-Christian suggested that I attend a lecture titled Creation: The Missing Link. I couldn't resist replying with a tirade against Creationism. Here it is.

The results in Molecular Biology have demonstrated beyond any reasonable doubt that evolution is sufficient to explain the variety of species that exist (or have gone extinct). Last December, I read a very detailed and documented book that demonstrates just that: The Making of the Fittest - DNA and the ultimate forensic record of evolution, by Sean B. Carroll ().

Faith and Science are two different things. Creationism and Intelligent Design can explain everything. I know. But the best proofs they can count on are tautological.

Peer-reviewed published Science is not infallible, but when the body of evidence grows over decades and no measure, experiment, or discovery invalidates a theory, the probability that the theory is false vanishes. Relativity, for example, is a theory and, as such, it could be refined in future, exactly as Relativity itself refined Newtonian Mechanics. But, after so many confirmations, it cannot ever be invalidated, exactly as Newtons theories have not been.

The Global Positioning System only works because the clocks on the satellites are adjusted to take into account Relativity. The Cosmological Constant introduced and then repudiated by Einstein to avoid divergence of his formulae has been re-introduced to be able to avoid contradiction with the fact that the universe is expanding at an accelerated rate. Dark Energy and the Cosmological Constant are ad-hoc solutions to explain (without actually explaining anything) the expansion of the universe. This is a clear indication the Relativity as we know it is part of a more general theory that will explain the universe without fudging the formulae. But that doesn't invalidate Relativity at all.

All theories go through successive refinements and generalisations.

Another "fudge" in Science that I know of is the "renormalisation" used in Quantum Field Theory to get rid of infinities (a bit like saying that 0/0 = 1!). Again, it means that the theory will probably be refined in future (unless it becomes a particular case of a more general theory that doesn't need renormalisation). Meanwhile, Quantum Theory has explained to us semiconductors, superconductivity, superfluidity, and a host of other useful stuff.

Evolution is yet another theory and, like Newtonian Mechanics, Relativity, and Quantum Mechanics, will probably be refined in future. But meanwhile, it explains the diversity of Nature without need for any external intervention. And the aim of any explanation must be to be parsimonious: don't do anything more than necessary to achieve a certain result. The fewer the ad-hoc factors invoked to explain something, the better (Occam's Razor).

This does not (and I don't see why it should) prevent you from believing that the laws of Physics are what they are because Somebody invented them and then set the universal constants exactly to the value they currently have. But, as I said, it is then a matter of Faith, not of Science.

Sometimes (but very very very seldom! ;-) I wish I believed in God. I know it can be of great help. But I don't believe, and don't think I ever will (although, obviously, the future cannot be really predicted...)

My wife is reading the book "Religion for Atheists", written by the Philosopher Alain De Botton. You can see an interview with him on the 7.30 Report's website. She loves it, and I will also read it. Although he is a staunched Atheist, he claims that we should respect Religion and try to learn from it, rather than dismiss it. He says that Religion does certain thing very well and that we miss some of them in our modern secular world. I just watched the interview on the web and it is absolutely worth watching. I strongly encourage you to do so. Alain is not just brilliant and articulate. He is also caring. I can tell you this: if everybody thought like him, religious or atheist, I doubt that there would be any religious persecution in this world.

Board Games

2012-02-26T15:15:00.002+11:00

Years ago, I played some board games like Monopoly, Diplomacy, and Halma. But then, for whatever reason, I stopped. Earlier this year, I was talking with Glen of Mind Games about numeric puzzles and he suggested that I attend Cancon 2012, Canberra's biggest gaming convention, organised by the Canberra Games Society.

I was there all three days and looked at several games, like Carcassonne, Dominion, Tanto Cuore, and Alien Frontiers.

I discovered that:

Some games, like Tanto Cuore and Alien Frontiers have very complex rules. Certainly, they create an almost unlimited number of different situations. But they also make it necessary to play quite a bit before becoming proficient and exploiting all possibilities. Too many things to remember, especially for an impatient person like me.
All games have an element of randomness, realised by drawing cards, rolling dice, or picking tiles.
All games make possible to develop strategies to improve your chances of winning. Sometimes it is realised by letting the players buy other cards (like in Dominion and Tanto Cuore). Or by choosing between different playing options (like in Alien Frontiers), or deciding where to lay a tile (like in Carcassonne).
Most games hev extensions. Their purpose clearly is twofold: keep the game new and stimulating, and make more money for the game developer and publisher!

Pretty obvious, really. The randomness gives you the thrill of the unexpected and, when you are not doing so well, the hope that a lucky turn of events will let you recover. And the possibility of strategising lets you be, at least to a certain extent, in control of your own future. You can perceive most victories as resulting from your shrewdness and most defeats as due to bad luck.

Anyhow, the visit to the Convention made me itchy. I wanted to buy a game and play it. But they are so expensive, and none of them was completely right for me. And my wife, who was going to be my most regular adversary, is even more choosy then me...

I ended up not buying any game and deciding to develop one. For one thing, I didn't want to have to learn thick manuals before being able to play.

My first attempt was an abstract game named "Beeing About".

You start with the following 112 tiles that you lay on a board.

The board consists of 169 hexagonal cells and 48 half-cell edges, arranged to form a large hexagon. Half of the edges are marked to 'connect' the two adjacent cells. Seven of the cells are 'crossroads' marked in such a way that all six sides are connected with each other:

The game preparation is trivial: Each player draws a number of tiles from the bag and places them face up on the table, where they are visible to all players. The number of tiles drawn by each player is 6 with two players, 5 with three or four players, and 4 with five of six players.

The whole rule book is as follows.

Each player in turn plays a tile by laying it on one of the hexagons of the board. For a play to be valid, the following rules must be respected:

The played tile must be in contact with at least one of the tiles that are already on the board. Alternatively, the tile can be laid adjacent to a crossroad cell, but only if the crossroad is already in contact with one or more tiles. The only exception to this rule is when the first player plays his very first tile. In that case, he lays the tile in contact with the crossroad in the middle of the board.
The paths of the played tile must continue the paths of the tiles (and possibly of a crossroad or an edge) to which it comes into contact. Note that the colours of the paths are different only to easily distinguish the tiles with different numbers of contact points.

Here are examples of correctly played tiles:

And here are examples of incorrectly laid tiles, because not all adjacent paths connect:

After laying a tile, a player draws a new tile from the bag, unless the bag has been emptied.

If a player cannot lay any of his tiles, he can replace one or more of his tiles with tiles from the bag. To do so, he places his tiles into the bag and gives it a good shake before drawing from it the same number of tiles. This obviously means that, especially towards the end of the game, he could draw the same tiles he has just discarded. If, after replacing tiles, the player still cannot play any of them, he sits his turn. That is, a player can only exchange tiles once before each one of his turns, and only if he cannot play any of the tiles he is holding.

Instead of exchanging tiles, a player can also decide to sit a turn. If the bag is empty, the player obviously cannot exchange tiles and is forced to sit the turn.

A tile can be laid on a crossroad cell, but only if its paths connect to the paths of all tiles adjacent to the crossroad.

That's it.

I played it a few times, and it turned out that strategising was not really possible, because the players couldn't plan beyond their second next move. In Carcassonne, you draw a tile at a time, but the mix of tiles and their meaning make possible for you to roughly plan some moves ahead. Carcassonne is a tile-laying game with very simple rules and very smartly designed. That's why it is so successful.

I could have worked on "Beeing About" and improve its strategising possibilities, but the game had another problem: it was too abstract. The most successful new board games don't only tickle your intellect. They also stimulate your imagination through nice sceneries and dazzling graphics. And I suddenly had the urge to develop a successful board game.

For the graphics, I will have to find a partner, but I feel that "Beeing About" is not so suitable anyway. I am now working on a different game, based in space. More about that in a future article. For now, I shall only say that it also has a board of hexagonal cells. Hexagons are much more exciting than squares or triangles. Don't you agree?

Before I end this article, here are some further reflections on the tiles of "Beeing About".

I wanted to draw all possible combinations of connections between the sides of hexagons. The tiles with 1 point of contact (the black dead end) and with 2 (green) and 3 (blue) points do just that. But if you carefully look at the tiles with 4 points of contact (red), you will notice that several of them are redundant. In the game, the only thing that matters is the distribution of points of contacts on the edge of the hexagons. How they are connected within the tile is irrelevant. For example, the following three tiles:

have the same points of contact among themselves. And the following ones too:

and these:

Only three combinations of four points of contacts are functionally distinct:

It makes sense, because having four points of contacts means that you leave two of the six sides free. And we know from the tiles with green paths that there are only three ways in which you can choose two sides...

Similarly, the tiles with five points of contacts (magenta) are all functionally identical, because there is only one way of leaving a side of the hexagon free of contacts.

But the different patterns looked nice...

Banks!

2012-02-05T10:33:00.000+11:00

This morning, I saw an interesting advertisement in the window of a bank. It offered an interest rate of 5.6% for a three-month term deposit (yes. In Australia we have high interest rates. This is one of the reasons why people pump up the value of the AUD by investing in it). Then, on the same ad, with the figures well aligned, it offered to pay 5.10% for a six-month term deposit.

Do you get it?

5.6%
5.10%
They expect the interest rates to decrease. Therefore, they offer a lower interest rate for six months than for three months. But, by writing 5.10 instead of 5.1, they make it look as if the interest rate for six months were higher than that for three months. They play on the ignorance of people who see 10 greater than 6 even if it is after a decimal period.

I hate banks... Almost as much as insurances...

US Troops

2012-01-26T09:46:00.000+11:00

I was reading the article "The Strategist" in the current issue (Monday, Jan. 30, 2012) of Time Magazine and found some information that I would like to share. As it is a small amount of data hidden inside a figure, I am confident I am not violating any copyright law (one cannot ever be careful enough these days...)

I find it interesting because it answers the question: in which country are US troop present and how many?

Here is the list of troops presence (with the countries listed in no particular order):

> 50,000 U.S. (not surprisingly), Afghanistan (again, a well known fact), and Germany.

1,000 .. 50,000 Spain, UK, Belgium, Italy, Turkey, Iraq, South Korea, Japan, Bahrain.

100 .. 1,000 Australia, The Philippines, Thailand, Singapore, Saudi Arabia, Djibouti, Egypt, Greece, Portugal, Panama, Cuba (of course: Guantanamo), and Canada.

None (at least, not officially ;-) North Korea, Papua New Guinea, Malaysia, Iran, Albania, Belarus, Iceland, Eritrea, Somalia, Malawi, Swaziland, Lesotho, Namibia, Equatorial Guinea, Central African Republic, Benin, Burkina Faso, Guinea Bissau, Gambia, Western Sahara.

All other countries have a presence of between 1 and 100 U.S. troops.

I thought: perhaps Time counted as troops the few marines attached to U.S. embassies. But this is not the case because, according to Wikipedia, sixteen of the twenty countries that Time lists as not having any military presence do have a U.S. embassy (excluded are "the usual suspects": North Korea, Iran, Somalia, and Western Sahara).

This means that U.S. soldiers are present almost everywhere (101,000 further troops are at sea).

I find this amazing. Don't you?

End-of-year Cleanup

2012-01-08T18:12:00.004+11:00

I should have published this story on January 1st, but better late than never.

As you perhaps know, I grew up in Rome (Italy). On the last day of each year, the busses stopped running a few hours before midnight and retreated to their depots. But it wasn't simply to give to drivers and conductors the opportunity to celebrate the coming of the new year with their families. It was to ensure their safety.

Yes. Their safety, because when I was a boy, it was a Roman tradition to dispose of unwanted stuff by throwing it out of the window. Literally.

Why bring junk to the tip when you can simply throw it out? Beside being simpler and more economical, at a time when the majority of people could not afford to buy a car, it was fun!

Can you imagine the impact of an old easy chair when it hits the sidewalk after a "jump" from the fourth or the sixth floor?

You could throw out everything, including old sinks and toilet bowls, with seat and all. A walk in the early hours of the new year, before the teams of garbage collectors started the thankless task of cleaning up the streets, was a unique experience. In some quarters you literally had to walk in the middle of the street in order to negotiate your way through. At least, with all the broken glass and empty cans littering the streets, there was no chance that a car would be around to hit you.

I lived with my parents, sister, and grandmother, on the third floor of Via Alessandria 119, just outside the high wall that the Romans built around the city some two thousand years ago. It was quite central, and very near the place where the troops of the Kingdom of Italy breached the wall on 20 September 1870 to "liberate" Rome from the Vatican.

Anyhow, here is a nice snapshot of the street "borrowed" from Google's street view. You can see the entrance door and the windows.

From one of those windows, my family and I enjoyed the view of the "new-year dumping" and, sometimes, threw something away ourselves, although I don't remember that we ever got rid of very bulky items.

One year, when I was between four and seven years old, we had a carton of persimmons who had become a bit too ripe. Who knows why we had it, but I remember that at midnight of December 31st we used them to bombard a car that somebody, very imprudently, had left parked on the other side of our street. The fruits were very soft, and I am sure that we didn't do any damage to the car, but I can only imagine what its owner must have thought when he saw it completely covered by a orangey sticky goo.

I wouldn't do it now, and I cannot imagine (but don't know it) that Romans still throw rubbish out of the window on the last night of the year. Still, at a time when very few families had a TV set or money to spend on fireworks, it was of great entertainment.

Italy is much more civilised these days...

Montana, where are you?

2011-12-25T12:13:00.002+11:00

This blog gave me two nice surprises for Christmas: the first visitor from Algeria and the first visitor from North Dakota.

Now, I am only missing visitors from one of the United States: Montana.

If any of you knows somebody who lives in Montana or happens to make a trip to the headwaters state and connects to the Internet, it would be nice to have the remaining US-state flag...

DNA

2011-12-25T11:08:00.000+11:00

Some days ago, I started reading the book "The Making of the Fittest" by Sean B. Carroll and I cannot put it down. Finally, a book that explains how the study of DNA proves beyond any doubt that Darwin was right with his theory of evolution. A clear and uncluttered explanation of how DNA works. In fact, I like it so much that I will try to summarise it (!) here.

DNA consists of a double chain (or "strand") of compounds called "Nucleotides" (although, to be precise, not all compounds called nucleotides are to be found in DNA). A nucleotide (also called "Base") is a simple molecule with one or two dozen atoms. Four bases exist: Adenosine (A), Cytidine (C), Guanosine (G), and Thymidine (T).

Each base in a strand is linked via a Hydrogen bond to a base in the other strand: the As are linked with Ts and the Gs are linked with Cs. That's how the two strands of DNA are kept together. This means that for every A in one strand, there is a corresponding T in the other strand, for each C a G, for each G a C, and for each T an A. Therefore, each strand contains the same information. In other words, a DNA molecule contains the same information twice, once in each strand. That's why you will find in the literature the description of DNA as consisting of "base pairs". The Human DNA consists of about three billion base pairs.

A "gene" is a sequence of about 1200 base pairs that contain the information to build a protein, and humans have something between 20,000 and 25,000 genes.

A chromosome is only the name given to a portion of DNA. That is, the fact that we have twenty-three chromosomes only tells you that our Genome (collective name for all our genes) is not contained in a single molecule of DNA but in a series of separate double-strands. Chromosomes are important but, somehow, I don't find them very interesting, although, I might change my mind. You can find a list of the number of genes and base pairs in each human chromosome here: http://en.wikipedia.org/wiki/Chromosome.

When a cell wants to generate a protein (don't ask me when and why that happens), it "transcribes" the sequence of one of the DNA strands of the corresponding gene into a single strand of what is called "messenger RNA", or mRNA. mRNA is a sequence of nucleotides similar to a DNA strand, and repeats the DNA sequence of the gene but with an A for each T, a C for each G, a G for each C, and a U (Uracil, another nucleotide) for each A.

Proteins are chains of simpler compounds called "Amino Acids", which are quite simple molecules containing nitrogen.

The cell "translates" the strand of mRNA into the corresponding protein, one amino acid at a time. To do so, it scans the nucleotide sequence of the mRNA in groups of three, and each triplet (which is called a "codon") of nucleotides identifies a particular amino acid.

Let's see: there are four different nucleotides in mRNA (A, C, G, and U). Therefore, a group of three nucleotides can identify 4 x 4 x 4 = 64 amino acids. In fact, there are only 20 amino acids (which is very convenient, because they can be identified by a single letter of the alphabet, as shown in http://en.wikipedia.org/wiki/Aminoacid). This means that several triplets of nucleotides identify the same amino acid. Note that pairs of nucleotides (instead of triplets) would have not been enough, because they could have only identified 4 x 4 = 16 amino acids. In any case, there are also some codons that are used to "stop" a sequence. When the molecule encounters a stop codon, it stops building up the protein.

Obviously, as each gene has on average some 1200 bases and three bases are needed to identify an amino acid, the average protein contains 1200 / 3 = 400 amino acids.

It turns out that about half of our DNA is "junk", left behind by genes that were no longer needed and have decayed due to natural mutation or resulting from the random duplications that often occur.

As you might have heard, evolution is due to variations (i.e., DNA mutations), selection, and time. DNA frequently mutates for various reasons (for example, when a nucleotide is replaced by a different one), but it can also happen that entire sequences of base pairs are either duplicated or lost. If the "new" gene is viable, the corresponding protein sometimes turn out to be advantageous for the carriers of the mutated gene. In those cases, if the gene is passed on to enough new members of the species, even a little advantage can, after enough time, cause a complete replacement of the "old" gene.

Even minute advantages due to the presence (or absence) of a gene have, on the long run, significant effects. Einstein (I believe) compared them to compound interest: even a small percentage, over many years, can result in substantial figures. And evolutionary periods are measured in centuries and millennia, when not in millions of years.

If the mutation is damaging, the same mechanism of natural selection "purges" the DNA. That's how some genes have remained unchanged for, literally, billions of years and can be found in almost all species.

It can also happen that, due to mutated environmental conditions, a particular gene ceases to be advantageous. In those cases, natural selection no longer operates. With time, as the gene mutates, there is no longer a mechanism to purge the DNA of those mutations that make the gene unviable. As a result, eventually, all genes that cease to be advantageous decay and become irrelevant. These fossil genes contribute to the junk base pairs in our DNA.

The fact that genes disappear is a big blow to the proponents of "Intelligent Design". Isn't it?

There are genes that provide the material needed for our organs, and genes that regulate how those proteins are organised. How these regulating genes do their job depends on a series of base-pair sequences in our DNA (called "Switches"), like a computer program depends on its parameters. Changes in those switches can result in dramatic differences at the macroscopic level, because they also set things like the number of limbs.

Fascinating!

Lacing Shoes

2011-12-20T15:32:00.002+11:00

Almost one and a half years ago, I posted an article about how to fold toilet paper (Toilet paper woes). Today, I would like to write about another simple task that often doesn't receive much attention (except by me, that is): how to lace shoes.

After deciding to write about this neglected subject, I discovered a great website entirely dedicated to the different techniques for lacing up shoes: Ian's Shoelace Site. Very thorough a professional.

Perhaps not surprisingly, the discovery of Ian's site didn't deter me from writing here my reflections on the subject. Ian shows diagrams for 36 different ways to lace shoes, but I will concentrate on the three methods that, as far as I can see, are used by the vast majority of people.

Here is the first method, in which one side of the lace spirals through all eyelets and the other side goes through to one of the two top holes:

The advantage of this method is that, if the two sides can come close together, the loops are parallel to each other. This appeals to many, and I have often found that this method is applied by salespeople. Perhaps they do it because, with this method, you don't need to count holes.

I hate this method. After a while, it tends to skew the holes, as one of the bottom ones is strongly pulled towards the top. It is also somewhat more difficult to open up the shoe, and the side of the lace that loops through tends to remain loose in the middle. Besides, I like symmetry.

One variation of this method is as follows:

As you can see, both sides loop through each second pair of holes. The loops remain parallel in front, while the skewing effect is significantly reduced. But I still don't like it, because it remains asymmetrical and (don't ask me why) somewhat unnatural.

The third method I would like to show you is completely symmetrical. Here it is:

In the example shown, the lace always go through the eyelets from the outside to the inside. This is in fact a variation of the most common technique, in which the lace starts from the inside and always go through from the inside to the outside. The result is a zip-like pattern that is quite pleasing. Like in the previous cases, it doesn't require you to count the holes. But it has two disadvantages. The first one is that you cannot bring the two sides of the shoe completely together. It is not a problem in the example, but I had sometimes shoes in which the two sides even overlapped. The second disadvantage is that the two sides of the lace rub against each other, thereby making it somewhat more difficult to open and close the shoe.

The final method is the one that I consistently use. Although, for the best effect, it requires you to count the holes (in, out, in, ...), it represents in my opinion the most pleasing solution in terms of symmetry, low friction, and applicability.

It is also nice to see the Xs formed by the laces inside. Or not?

A Puzzling year indeed

2011-12-20T12:18:00.001+11:00

In yesterday's article, I forgot to say that in 2011 I also developed a CalcuDoku-solving game for the iPad (search iTunes for CalcuDokus and you'll find it in your local iTunes store).

I first made a $0.99 version with 100 puzzles, and then a free version with 17 puzzles and advertisements.

Despite my attempts at getting some review sites to look at it, the results were quite disappointing. Apple's AppStore is saturated with applications, and it has become very difficult to get noted. Big games-developing companies systematically hit jackpots, but nanodevelopers like me have close to no chance.

Far from me the idea that my application is exceptionally good and overlooked. But I am pretty sure that a couple of years ago, it would have sold reasonably well. So, why did I wait for 2011 and a saturated market before developing for the iPhone/iPad? Because I am stupid. That's why. I did the same with the Web: in the early nineties, instead of being one of the first web developers on the market, I developed an application for the Mac (MacDOS) that went nowhere.

Another missed opportunity...

A Puzzling Year

2011-12-19T21:41:00.003+11:00

This has been a year during which I have concentrated on developing puzzles and writing about it. I had always been interested more in developing programs to generate and solved numeric puzzles than to solve the puzzles themselves. Towards the end of 2010, I finally dedicated myself to it.

The first thing I did was to write two programs to generate and solve Sudoku Classic puzzles. I also added to the Generator the code necessary to create pattern Sudokus (i.e., puzzles in which the initial clues are arranged in a pre-determined way). Once I was done with Sudoku Classics, I wrote a program to combine five pattern Sudokus into a Samurai Sudoku puzzle.

This work on Sudoku resulted in my first puzzle book, Sudoku Programming, which I self published at the beginning of April. 365 pages of strategy explanations, walk-throughs of "C" code, and examples.

Shortly after that, I thought that a book describing in detail the strategies to solve Sudoku Classic puzzles could be useful, and wrote Sudoku Explained, a booklet of 94 pages that I published at the end of May. I offered it to the game shop Mind Games, that has since sold some copies. Forget what they say about eBooks. In terms of satisfaction, nothing compares with seeing your printed books on the shelves of a physical, old fashion, shop.

I had designed the head with the "Sudoku Brain" for my first book, and had the idea of placing small heads on the two sides of my name. But, after flipping the small head to place on the right-hand side of the cover, given my perfectionism, I flipped each digit inside the brain back to its original direction, so that they could be read. The devil is indeed in the details...

At that point, I decided that "C", after all, was less popular than Java, and decided to rewrite all my Sudoku programs in Java. This took a few months during the middle of the year. After that, it seemed natural to rewrite "Sudoku Programming" for Java. This time, I chose the more catchy title How to Create Your Own Sudokus with Java. I contacted some publishers and also some agents, but nobody was interested in publishing it. They all claimed that it was a very difficult book to place. As a result, once more, I decided to publish it myself.

But while I was looking for a publisher for my Java book, I started working on another puzzle: CalcuDoku (see several recent articles in this blog).
I developed a program to generate and solve CalcuDokus, but this time I decided not to write books that explain how the programs work. Similarly to what I had done with Sudokus, I wrote a program to compose CalcuDokus into larger puzzles.

Over the past couple of months, I have published three books of puzzles: 200 Puzzling Hearts, with 200 heart-patterned easy Sudokus, 200 Puzzling Shamrocks, with 200 difficult Sudokus patterned like four-leafed clover, and 100 Double CalcuDokus.

I am currently publishing what is going to be my last puzzle book (at least, that's what I am thinking now): 50 Samurai CalcuDokus. This book has a larger format because the samurai puzzles are LARGE!

Next year, I will have to work on something else. I confess that I feel a bit saturated with puzzle programming. Perhaps, I will resume writing my historical novel Ciao Biondina. But also a crime novel or an alternate history might inspire me. We shall see...

Double CalcuDoku #2

2011-12-08T16:52:00.000+11:00

I can now generate Double CalcuDokus with any overlapping, although, at least for the time being, the overlapping region can only be a square. Here is an example of a 6x6 overlap:

I find puzzles with large overlaps more interesting. It makes it easier to exploit the fact that the cells of each row and columns that are not share must coincide. For example, in the above example, the three bottom cells of the middle column of the right puzzle include two singles: a 4 and a 2. This means that also the top three cells of the same column must include a 4 and a 2. As the 2-cell cage "9x" cannot possibly contain an even digit, it means that the they must be in the other two cells.

And here is an example of a 7x7 overlap:

The "edge effect" is particularly strong when the overlapping is 7x7, and makes the solution of the overall puzzle easier. To keep the difficulty at a challenging level, I have therefore tweaked the configuration parameters and made the individual puzzles a bit more difficult. Notice that in the above example there are three 5-cell cages and seven 4-cell cages.

I have just published a book with one hundred puzzles:

You can buy it in print from Lulu for US$9.99 or in several eBook formats from Smashwords for US$0.99.

Double CalcuDoku

2011-12-02T18:04:00.001+11:00

I imagine that you are familiar with the double Sudokus like the following one:

I though: wouldn't it be nice to make overlapping CalcuDokus? Well, here is the first one I generated:

As you can see, I overlapped a 3x3 area. To explain how this works, I have coloured the puzzle, which is normally in B&W. The two squares are two normal CalcuDokus, but the green area belongs to both the yellow and the blue puzzles.

Notice that cages can cross the boundary. For example, the right-side cell of the 2-cell cage "2:" belongs to both puzzles, while its left-side cell only belongs to the yellow puzzle.

As I don't like puzzles that admit multiple solutions, I ensured that the program delivers a unique solution. The interesting thing with overlapping CalcuDokus is that they can overlap by any amount of rows and/or columns, while Sudokus, to maintain the integrity of the boxes, can only overlap by 3 or 6 rows and/or columns.

For the time being, my program only supports an overlapping of 3 rows and 3 column, but I am going to parameterise it. Then problem is not in generating and solving the puzzle, but in displaying it.

Concerning the name to give to these puzzles, I thought that Niken would be a nice possibility. This is because "Ni" means "two" in Japanese and KenKen (which is a registered trademark of Nextoy LLC) is much more widely known than CalcuDoku. In any case, "CalcuDoku", as a name, is quite long on its own. As "Ken" is a normal Japanese word (which, as you probably know, means "wisdom"), I don't believe that Nextoy could accuse me of infringing their trademark. I could also call it KenTwo or TwoKen but, somehow, it doesn't seem right. Also Kenni is not good. What do you think?

KenKen and CalcuDoku

2011-11-26T22:52:00.000+11:00

I found three websites that let you play daily KenKen (® Nextoy LLC) /CalcuDoku puzzles: kenken.com, calcudoku.org, and my website zambon.com.au.

While the other two websites include puzzles of different sizes, and calcudoku.org also includes variants, my website only includes 9x9 puzzles. KenKen and CalcuDoku are the same puzzle, but their implementation is done by different people. Each implementation has a different feel and, on average, different levels of difficulty.

I know how my puzzles are developed, but, obviously, I have no idea what algorithms the other developers use. I thought it would be interesting to identify some of the differences from a statistical point of view.

For this purpose, I analysed 10 puzzles taken from each website. I know that 10 is too small a sample to make good statistics, but it was a lot of counting...

Anyhow, what follows is a summary of what I came up with. To avoid repeating the domain names, I will use K to identify kenken.com, Z for zambon.com.au, and C for calcudoku.org. ‘A’ indicates values obtained by averaging all. The triplets of numbers indicate minimum, average, and maximum values.

Number of cages: K=[31, 33.2, 38]; Z=[32, 34.3, 37]; C=[33, 34.2, 35]; A=[32.0, 33.9, 36.7].

The average number of cages is for everyone around 34. But it is interesting to note that K's spread is 7, Z's is 5, and C's only 2. This might indicate that, while K and Z do not set any limits to the number of cages, C determines the cages not completely as a result of random choices. This might be consistent with the fact that C sometimes presents puzzles that have the cages arranged in particular patterns (although none of the puzzles I randomly picked belonged to that group). It would be interesting to know what Patrick (C's developer) would have to say about this.

With larger samples, I expect that Z's (i.e., my) number of cages would turn out to be normally (i.e., randomly) distributed. Actually, as I generate the puzzles, I don't need to do the counting, because the computer automatically lists for the number of cages. I can check it out right now.

...

It turns out that the number of cages calculated for 100 Z's puzzles is [32, 34.83, 38].

The following image shows how the normal distribution (the magenta squares) fits to the measured values (the blue diamonds; these are the default of Excel and I didn't bother to change them). The vertical bars represent a standard deviation from the normally distributed values. In other words, if the distribution reflects reality, there is a 68.2% probability for each measurement to fall within the bars. At the very least, the plot confirms that the number of cages in my puzzles is not in disagreement with a normal distribution. I confess I would have been shocked if it had not been so, because the distribution is the result of several [pseudo]random choices...

The following table summarises the counts of operation codes and cage sizes.

C has about 6 times the number of 1-cell cages that K and Z have, and half the number of 2-cell cages. I will go out on a limb and say I believe that such differences are not due to statistical fluctuations within the samples. C also seems to have fewer divisions (1.3 vs. 3.5 and 5.5) and more cages with more than 3 cells (6.4 vs. 3.1 and 3.9). It seems reasonable to assume that the lower number of divisions (and perhaps subtractions) is due to the lower numbers of 2-cell cages.

In general, I have the impression that C's puzzles are more difficult than those of K and Z, and it seems reasonably safe to assume that the higher number of large cages is a contributing factor.

To deduce more from such a small sample would be inappropriate.

Catholic Church? No Thanks!

2011-11-13T21:33:00.000+11:00

I just published with Smashwords a short book titled Catholic Church? No Thanks!.

It collects a series of short pieces about the Catholic Church that I wrote over a period of time. They describe some events that occurred to me and some of my reflections on how the Church operates. I was never a fervent Catholic, but this booklet explains some of the events that contributed to my Atheism.

You can buy CalcuDoku for the iPad

2011-11-01T15:54:00.001+11:00

My application to play CalcuDoku on the iPad is finally available in the iTunes App Store:

You can also check it out on itunes.apple.com

What are you waiting for?

Same-sex Marriage

2011-10-23T13:03:00.002+11:00

Yesterday I talked about boat people. Today, I feel compelled to write a short note about another issue that is being hotly debated in Australia.

All those who oppose same-sex marriage claim that their objections have nothing to do with religion. This is obviously (at least to me) nonsensical. The fact is that marriage is still seen by many as a “holy matrimony”, a union sealed by God.

For me, to limit marriage to people of opposite sexes is an act of discrimination, as absurd as if there were the requirement of a minimum difference in weight or age or colour of the skin.

In Australia, almost one third of people never marry and one third of marriages end up in divorce. Furthermore, there are more de-facto relationships than married couples. The idea that marriage is one of the pillars of our society is therefore a bit outdated.

A marriage is a contract. It spells out duties and rights like any other contract. As such, it should be accessible to everyone who accept some obligations in order to enter a recognised form of relationship.

The discrimination against same-sex marriages is a relic of the past that should be disposed of without so much fussing about. I understand the value of traditions, but marriage exclusively between a man and a woman should be confined to the history books exactly like the ius primae noctis.

Boat People

2011-10-22T18:41:00.004+11:00

Every year, some thousand people are desperate enough to attempt the dangerous crossing from Indonesia to Australia on rickety boats. They pay thousands of dollars to the unscrupulous operators who own the boats, in the hope that they will be allowed to remain in Australia as refugees.

Most of them get recognition for their refugee status and, slowly and painfully, find their place in our society.

Unfortunately, these people, who leave behind a life full of violence, abuse, and fear, have become a virtual ball that the two major Australian parties (Labour and Liberal) play to score political points.

In Australia, if you enter the country illegally (i.e., without a valid visa) and apply for refugee status, you are kept in detention until your application is processed. This would be acceptable if the processing took, say, one month. I am sure that everyone, after years of deprivation and a perilous journey, would be happy to relax for a short while in a comparatively comfortable place with plenty of food, clear water, and medical assistance. I know I would.

But the processing can take YEARS!

Often the problem is that the Australian Security Intelligence Organisation (ASIO) encounters difficulties in determining the identity of the applicants and in ensuring that they do not represent a threat to national security (i.e., that they are not terrorists or criminals in disguise). This is understandable, but what is wrong with letting them out, with some form of control, like regular reporting or perhaps, if you really are paranoid, GPS ankle-bands?

As a result of this mandatory detention policy, families are split for years, and cases of self-arm and suicide are more frequent among detainees than in the rest of the population. What a shame, for such an affluent society. Besides, if these people were allowed to live a reasonably normal life and to look for work, beside being the humane thing to do, it couldn’t possibly cost to the taxpayers more than maintaining detentions facilities scattered throughout the country.

According to both major parties and the Australian newspapers, the Australian public is very sensitive to the integrity of Australian borders. This might be true, but then, rather than encourage alarmism every time a boat is intercepted, they should point out that every year some fifty-thousand people fly into the country legally and then overstay their visas. It would take longer than a decade of boat people (estimated on the average of arrivals during the past 2.5 years) to make up the same number of travellers that in any single year overstay their visa.

These people who come by boat could have not even applied for a passport in their country. It is inhumane to lock them up as soon as they reach our shores. Who bloody cares about a couple of thousand people more or less? I say: let them in and treat them with dignity. Show them, the Australian public, and the world that we care. But perhaps we don’t. Not enough.

Then there is the myth of deterrence. It was Paul Keating who, as a Labour Prime Minister, introduced the policy of “mandatory detention”, to discourage people from coming by boat.

Then, John Howard, some years later, as a Liberal prime minister, introduced “offshore processing” for the same reason. Asylum seekers were transported to Manus Island in Papua New Guinea and Nauru while their application was being processed. Also, towards the end of 1999, the Howard government introduced the Temporary Protection Visas (TPVs). Refugees were given a three-year visa rather than a permanent one.

The Liberals claim that their TPVs worked as a deterrent, because the number of refugees trickled to almost nothing. It is true that in 1999 there were 3721 arrivals by boat and in 2002 only 1 (yes: a single person), but the arrivals in 2000 were 2939, and in 2001 the number of arrivals reached 5516! (see http://www.aph.gov.au/library/pubs/bn/sp/boatarrivals.htm). If the TPVs had been effective, it would have not taken two years to see a reduction of arrivals.

The Liberals contradict themselves. They explain the 2849 arrivals of 2009 with the fact that the Labour prime minister Rudd abolished the TPVs in 2008. But then, why should it have take two years to see the opposite effect when the TPVs were introduced?

Some months ago, the current Labour government came up with the concept of “regional processing centres”. They said: refugees are a regional issue, not just an Australian one. Therefore, we should set up regional centres where all refugees of the region can be processed. Very innovative (although not in agreement with the Geneva Convention). But East Timor didn’t agree to take the centre. The Liberals pushed for Nauru, whose government would have welcomed such a centre.

The government stated that Nauru was impossible because it was not a signatory of the Geneva Convention. But they remained unmoved in their position when Nauru did sign the convention on refugees. It seems obvious to me that the government rejected the idea of a regional centre in Nauru because the Liberals had been pushing for it. That’s all. The convention was just an excuse.

Things seemed to be moving ahead on the deterrence front when the Labour government of Julia Gillard signed an agreement with Malaysia (which, incidentally, is not a signatory of the convention, and apparently treats its refugees in an appalling way, with beatings and unjustified arrests). Australia would take from Malaysia four thousand recognised refugees and send there in exchange the first eight hundred boat people that would reach Australia after the signing the agreement.

It certainly would have been a deterrent for people to try to reach Australia by boat from Indonesia knowing that they would be immediately flown to Malaysia.

But somebody applied to the High Court of Australia on behalf of some of the people who were going to be deported to Malaysia to have the agreement reviewed, and the High Court ruled that it was in violation of Australia’s international agreements and therefore illegal. In fact, it wrote such a ruling that all offshore processing became impossible.

The government formulated a law that would have allowed them to establish national policies in violation of international agreements, but the Greens, who support the current minority government, disagreed. They had always been in favour of onshore processing and didn't change their mind. And the Liberals were happy to score a point against the government by opposing the law, despite the fact that they had invented offshore processing in 2001.

In any case, I question the morality of cajoling refugees so that they are dissuaded from coming. I don’t find it acceptable to put under pressure people who are already so desperate.

Earlier today, I talked about this subject with my local member of parliament. He said that Labour’s goal is to prevent people from taking such a desperate journey. Fair enough, but we are not responsible for them. We should work with the neighbouring countries and try to catch the criminals that cash on people’s desperation, but once somebody decides to take the journey and arrives on our shores, we should treat them with compassion, not throw them into jail or fly them off to Malaysia...

The CalcuDoku application for the iPad is ready

2011-10-22T16:44:00.000+11:00

I have just uploaded the CalcuDoku application for the iPad to Apple’s application store. They could still find something I didn’t do right and reject it, but I think (and hope) that everything will go smoothly. I don’t know how long it will take before it will appear in the AppStore, though...

Unfortunately, I am also not sure that it will be available in the Australian Apple store. The problem is that I am not registered for GST (for the non-Australians: GST stands for Goods and Services Tax and is Australia’s 10% value-added tax). It is only compulsory to register for GST if your Australian business revenue exceeds 75 kAUD, and it is such a bureaucracy that you don’t really want to get into it unless you do have such an income and/or incur significant GST-deductible expenses.

It is not clear to me whether Apple will simply not pay me when they sell my application in Australia or (more likely) the Australian residents will be unable to buy the application locally. In any case, they should still be able to buy it from the US store for USD 0.99 instead AUD 0.99 (actually a cent or two cheaper). We shall see.

Now that this application is done, I will go back writing fiction. I confess I am a bit fed up with programming. As I said in a previous article, Apple’s development environment is great, but not bug-free. In a couple of occasions, I had to find some workarounds to get done what I needed.

Why a bladder?

2011-10-17T17:16:00.002+11:00

I have always had some of my most interesting ideas during the periods of drowsiness that precede and follow sleep.

A couple of days ago, during one of those periods, the following question popped into my mind: “Why do we need a bladder?” Or, better said: “What evolutionary advantage has led to the development in mammals of a bladder?”

Reptilians and birds don’t have it. They free themselves of their excreta via a single orifice, while mammals developed separate “way outs”. But my early-morning question was more specific than that: we could still have two separate tracts and no bladder.

Googling around, I discovered that a couple of other people had already asked the same question, but the answers were not pertinent at all. In fact, they were a clear indication of how stupid some of the people who answer questions on the Internet are. There seemed to be a consensus that you need the bladder otherwise you cannot free yourself of substances that, on the long run, would kill you. That obviously answers the question “why do we need to urinate”, not “why do we need to store urine rather than just letting it go”.

Understand me: I am very happy to have a bladder, otherwise I would be condemned to cope with a frequent trickle of urine. Perhaps, without a bladder, humans would have developed a very different type of society. At the very least, clothes would have been made in such a way as to allow an unhindered flow of urine, or perhaps with a built-in waterproof container.

The presence of the bladder allows mammals not to leave traces behind them (unless they want, for example to mark territories). And that is perhaps where the evolutionary advantage is: big saurians could track proto-mammals (if there is such a thing, a doubt which reveals my ignorance in species evolution) by following their trickle of urine. To avoid being easily chased down, mammals learned to “hold it” as long as they could and, obviously, those that could do it longer were more likely to shake off their hunters. Over many thousands of years, this might have resulted in the evolution of a bladder, so that mammals could wander about for long periods without leaving behind persistent scents.

There is obviously no proof that my hypothesis is correct, but I am happy to have found a possible (and to me quite convincing) explanation.

Disappointingly, I remain completely at a loss concerning why it was evolutionary advantageous to separate solid and liquid excreta...

The CalcuDoku application for the iPad is almost done!

2011-10-07T22:29:00.003+11:00

Hopefully, in the next week or two, you will see the application in the Apple Store. There will be a version with ten puzzles for free and a version with one hundred puzzles for a few dollars. This is obviously to allow people to try out the game for free, and then, if they like what they see, buy the version with many puzzles to play.

Since the last article on this blog, I added a tool bar and a menu to select the puzzles, as shown in the following snapshot.

Let’s look at the tool bar first. The button “Dismiss” is normally “Puzzles” and becomes “Dismiss” only after you have touched it in order to display the puzzle menu. When you touch “Get hint”, the application suggest an action that you can perform to progress towards a solution; more about that later in this article. “Reset puzzle” returns the current puzzle (“007” in the snapshot) to its initial state, with no cells solved and no candidates removed. “Reveal puzzle” shows the solved puzzle (but then, where is all the fun? :-)

As you can see, you have a couple of segmented controls to select a subset of the puzzles. Not really useful with ten puzzles, but absolutely necessary when you have one hundred of them. The “difficulty” value that you see in the puzzle summary is calculated on the basis of the number and type of strategies needed to solve it. I’ll tell you how I calculate it in a moment, when I explain the “Get hint” function.

Still in the puzzle summary, “8 actions” is the total number of times you have “touched” inside the action menu (see the previous article) to remove a candidate or solve a cell.

“3 cells solved” counts all the cells solved, regardless of how they were solved (and who solved them). Cells can be solved in a number of ways. Two of them are obvious: you can touch a green “This cell contains” button in the action menu, or the red button marked “Show cell solution”. Perhaps less obvious is that you can solve a cell by touching one of the “Remove candidate” blue buttons. This can occur because the application automatically marks as solved the cells that remain with a single candidate. If, for example, one cell whose solution is 2 shows the candidates 1 and 2, you can solve it either by pressing the green 2 or the blue 1. The two actions are completely equivalent.

There is a fourth way of solving cells, and that is by letting the application automatically perform one of its hints. The following snapshot shows an example of what happens when you press the “Get hint” button:

Below the tool bar you see the hint, which in the snapshot says: “You can remove the 6s from all the cells of row I that don’t belong to cage 30x in I4”. It doesn’t say why, but if you look at the puzzle, you will notice that cage 30x in I4 only admits two solutions: 56 and 65 (obvious, as 6x5 is the only product of two numbers between 1 and 9 that results in 30). But then, you know that 6 cannot possibly solve I8.

Now, if you touch the big button “Go ahead and do it!”, the application removes for you the 6 in I8, without you having to click on the cell to bring up the action menu and then touch the blue 6. In this example, it is not a big deal, but in some cases there are a handful of cells containing the candidate to be removed.

I am not suggesting that you use the hints, but you might find them useful as a training exercise, to learn how to apply the strategies.

I have implemented five strategies to provide the hints, each requiring an average of 130 lines of objective-C code. The application tries the strategies in order of complexity, so that it only resorts to a particular strategy when all the simpler ones have failed.

So far, I haven’t encountered a puzzle that those five strategies cannot solve. This means that the application will always be able to give you a hint when you request it. In fact, I use the hint mechanism to calculate the difficulty of the puzzles as: n5 * 25 + n4 * 5 + n3, where nX is the number of times the application needs to apply strategy X to solve the puzzle. Note that the application starts searching for a hint from the last cell you have touched. Therefore, you might find it a bit tricky to reproduce the difficulty I calculate, because I always do it with a freshly started application and a freshly loaded puzzle. Only by starting from the same conditions it makes some sense to use my grading mechanism to compare puzzles.

Before I forget, although it goes almost without saying, you can also play the game in landscape mode if you like.

I still need to do a few things before I can release it:

Generate and grade some 93 puzzles, so that both applications (free and not) are released at the same time.
Modify the hint message to include the level of complexity of the strategy, just because you might like to know it.
Make a page attached to the “About” button of the tool bar.
Add to my web site zambon.com.au some pages of information associated with the application.
Prepare a good ad page for the Apple Store.

Progress on the CalcuDoku application for the iPad

2011-09-27T14:47:00.004+10:00

This is to report on my progress on the development of the application I announced in my previous article. Here a snapshot that gives you an idea on some of the functionality:

As you can see by comparing this image with the image in the previous article, I have added some important feature.

First of all, each cell is now identifiable by its row/column coordinates like those used in chessboards. This also lets you identify each cage by giving the coordinates of its cell that contains result and operation code. For example, you can use G4 to identify the 3/ cage.

The most visible improvement is that each cell now shows its candidates. I found that without candidates, solving the puzzle was incredibly more difficult than solve the same puzzle with paper and pencil. The advantage of having the application determine the candidates for you, is that now you can concentrate on finding conflicts and solving cells. To take full advantage of the candidates, you have to check the cage combinations.

For example, in the 3/ cage you find in F4 of the following example

you see that the two cells have candidates 13 and 139, but when you consider that the two possible combinations are 13 (with two permutations) and 39, you realise that a 3 is always present in either F4 or G4. This means that any other 3 in the other cells of column 4 are not possible. Every such a small step gets you closer to solving the puzzle. In the example, I have already removed the 3s from column 4, because I want to use it to show you another possible strategy. Notice that the cell A4 only has a 1 and a 9. As cage F4 can only contain either 13/31 or 39, it means that if the correct solution for cell A4 is 1, the solution for cage F4 can only be 39. Alternatively, if 9 is the correct solution for A4, F4 will be solved with either 13 or 31. In either case, the other six cells of colun 4 cannot contain any 1 or 3. This lets you discard as possible candidates the 1s in cells H4 and I4.

These type of reasoning is what makes CalcuDoku appealing and a very good excercise for the brain.

Another extension I have introduced is the list of permutations, which you see at the bottom of the image. They are sometimes useful in figuring out how to solve a cell, but, in any case, they give you an indication of how close you are to solving the cage. There is not much point in analysing at length a cage when it contains more than a handful of permutations. Note that a single combination can result in many permutations.

Obviously, the application keeps the lists of candidates, combinations, and permutations up to date as the solution progresses. While the candidates are always visible, combinations and permutations of a cage are only displayed when you touch a cell of the cage. When you do so, what I have decided to call ‘action menu’ appears, as shown in the following snapshot.

As you can see from the description below the puzzle, the menu of this particular example appeared when I touched one of the two cells of cage 3/ in A8. I didn’t bother to make it more complicated and confusing by also writing which one of the two cells I had touched. I assume that you always know what cell you have touched.

The cage can only contain the combination 26. Notice that the application always orders the digits from the largest to the samllest (e.g., 62 instead of 26). This has to do with the logic of the application itself. I got used to it and I don’t think it is worth wasting effort and processing time to swapt them around.

Anyhow, the menu lets you choose or remove a candidate among those possible for the cell you have touched. It also lets you ask the application to tell you the solution of the cell or of the entire puzzle.

This is going to change, as I am going to move the possibility to reveal the whole puzzle to a toolbar. The menu should only let you do something with an individual cell.

I generate the puzzles offline and load them into the iPad application as resources. Initially, I thought that I would provide a service with daily puzzles, but I have changed my mind. One of the reasons is that I don’t actually like to have to provide the service. It is much simpler to sell an application with, say, one hundred built-in puzzles.

There is also another more critical reason: a few percent of the puzzles my program generates are too difficult to be solved with the iPad application, and I don’t want to deliver puzzles that cannot in all honesty be solved. So far, I have been able to solve all puzzles with pencil and paper, but sometimes I had to use complex ‘what if’ analyses that are not possible on the screen (or, to put it bluntly, that would make the application too complex).

Finally, in a few percent of the cases, different pseudorandom seeds result in identical puzzles. This is due to the many restrictions that I impose on the puzzle generator in order to make puzzles that can be solved analytically.

As a result, I solve all the puzzles with the iPad application before permanently loading them into it. This ensures that they can be solved. You might argue that a more skilled puzzler might solve puzzles I cannot solve, but, after solving hundreds of CalcuDokus, I have become quite good at it, and even the most adept puzzlers will find my puzzles challenging!

One thing I still want to do before releasing the application is provide a ‘hint’ button. This will be a toolbar button, not associated with any cell. For example, in a puzzle including the following couple of rows:

the hint could be that no 4s or 5s are possible in cells D1 to D6 because they certainly appear in D7 to D9. Indeed, cage 7+ in D7 can only contain either 43 or 52/25, thereby forming an exclusing pair with the 4 and 5 of cell D9. The challenge is to make the application recognise these occurrences and formulate intelligible hints. I will start working on it as soon as I post this article to the blog. I have half an idea of how I should be able to do it.

Ultimately, I want to be able to solve the puzzles exclusively by using hints. And this is the test that I will do before releasing each new puzzle. It will ensure that the application will not run out of hints. To road-test the algorithm, I will try it out on the puzzles I have solved by hand.

The number of hints necessary to solve a puzzle will also provide a rough measure of its difficulty.

Now I am eager to get started on the hint functionality. My apologies for the typos I have left in this article because of my haste...

A CalcuDoku application for the iPad

2011-09-14T21:55:00.001+10:00

Perhaps you have visited my DailyCalcuDoku page. There, I provide interactivity with JavaScript, but all the work is done offline by a C application that runs on my server. Every day, a few minutes after midnight AEST (Australian Eastern Standard Time), the system launches the application, which uses the current date as a pseudorandom seed, and generates an HTML file with the daily CalcuDoku.

Actually, I have just realised that if you attempt to play immediately after my midnight, the program will fail. I have to fix it. It’s not nice when a program fails with no explanation. It might not seem a serious problem, but midnight here is 10 AM in Boston and 6 PM in Moscow...

Anyhow, after developing the Daily CalcuDoku software, I thought: wouldn’t it be nice to create an application for the iPad that does a similar thing? I started on 1 September, and the following snapshot gives you a taste of it:

So far, the application reads a file with the list of cages and, when you click on (ahem... when you touch!) one of the cells, it shows the combinations of digits that provide the correct results. For the multiplication, as you can see in the snapshot, it also lists the prime factors.

OK. It doesn’t sound much, yet. But I had to modify the original application to write the cages in a file. Then, after familiarising myself with the development environment on the Mac and with the peculiarities of Objective-C, I wrote from scratch the code for the iPad to display the cages and to calculate the combinations.

Next, I will develop the code to identify the candidates for each cell, and a context menu to let the player interact with the application. Obviously, I will also have to develop the functionality to save and retrieve the context when the player switches the iPad off and back on. And, not to be forgotten, a setup screen and/or a toolbar to choose playing options.

I would like the application to provide hints when requested, but I still have to look into it. I haven’t clear yet what hints would be possible.

I intend to create two applications: one will be free and will contain a limited number of puzzles. The other one, at a low price, will connect to my server to access a new puzzle every day. Also, the full application will be able to download more puzzles, which you can then play offline. Perhaps I should also provide a training mode, in which the player can see different strategies in action. Not sure about that.

Years ago, when Macintoshes were still running on Motorola Chips, before the advent of System X, I developed applications for the Mac. The documentation from Apple was excellent, and the APIs smart. But with the iPhone/iPad, the Apple developers have really surpassed themselves. Sometimes, the interfaces are so well designed and intelligent that they make me smile. This truly is promamming Nirvana! Perhaps it is because, after decades of programming and system design, I can fully appreciate all the thought that went into them.

Sorry for the lyric digression.

I have decided that, in any case, the application will only be available for the iPad, because the screen of the iPhone is too small for so many numbers. Also, the orientation will be fixed to portrait.

I will still need weeks (or longer...) to complete the application. I’ll keep you posted.

How to identify some email scams

2011-09-12T13:44:00.002+10:00

Some days ago, I received the following email (with my email address removed and the links disabled):

Subject: Your package has arrived!

From: UPS Shipments

Date: Wed, 7 Sep 2011 21:42:50 +0900 (KST)

To:

Dear client

Your package has arrived.

The tracking # is : 16B9159622A040A2 and can be used at :

http://www.ups.com/tracking/tracking.html

The shipping invoice can be downloaded from :

http://www.ups.com/tracking/invoices/download.aspx?invoice_id=16B9159622A040A2

Thank you,

United Parcel Service

*** This is an automatically generated email, please do not reply ***

It looked reasonable, but I was not expecting any parcel. Note that the time zone in the date is KST (Korea Standard Time). Per se not suspicious when considering our globalised communication system.

Perhaps, if I had been expecting parcels, I would have clicked on the second link to see what item the email was about. It would have been easier than looking up my outstanding invoices to compare the numbers. But, if I had done so (although at the time I didn’t know it yet), I would have actually downloaded (and possibly launched) an application. Who knows what it would have done...

As I was not expecting any parcel, I saved the email to my desktop as an HTML file. I then opened it in a text editor and discovered that the two links it contained pointed to URLs different from those shown. The first one pointed to

http://wwwapps-ups.com/track.php?page=16b9159622a040a2

and the second one to

http://track.wwwapps-ups.com/invoice040A2.JPG.exe

This ‘faking’ of URLs was highly suspicious, even if the actual domain name included the string “ups”. Besides, why should my invoice be and EXEcutable file rather than a PDF?

I was not in any danger, because I read my mail on a Mac and the security settings of my email client are at maximum, but many might have been penetrated without even realising it.

I searched the Whois database by typing

http://www.whois.net/whois/wwwapps-ups.com

and came up with the following entry:

WHOIS information for wwwapps-ups.com :

[Querying whois.verisign-grs.com]

[Redirected to grs-whois.hichina.com]

[Querying grs-whois.hichina.com]

[grs-whois.hichina.com]

Domain Name ..................... wwwapps-ups.com

Name Server ..................... dns27.hichina.com

dns28.hichina.com

Registrant ID ................... hc048483736-cn

Registrant Name ................. wan shen

Registrant Organization ......... wan shen

Registrant Address .............. shanghaishihong kouquchangshalu125hao

Registrant City ................. hongkouqu

Registrant Province/State ....... HA

Registrant Postal Code .......... 200102

Registrant Country Code ......... CN

Registrant Phone Number ......... +86.02152312352 -

Registrant Fax .................. +86.02152312352 -

Registrant Email ................ sdfdsgfdf@126.com

Administrative ID ............... hc048483736-cn

Administrative Name ............. wan shen

Administrative Organization ..... wan shen

Administrative Address .......... shanghaishihong kouquchangshalu125hao

Administrative City ............. hongkouqu

Administrative Province/State ... HA

Administrative Postal Code ...... 200102

Administrative Country Code ..... CN

Administrative Phone Number ..... +86.02152312352 -

Administrative Fax .............. +86.02152312352 -

Administrative Email ............ sdfdsgfdf@126.com

Billing ID ...................... hc048483736-cn

Billing Name .................... wan shen

Billing Organization ............ wan shen

Billing Address ................. shanghaishihong kouquchangshalu125hao

Billing City .................... hongkouqu

Billing Province/State .......... HA

Billing Postal Code ............. 200102

Billing Country Code ............ CN

Billing Phone Number ............ +86.02152312352 -

Billing Fax ..................... +86.02152312352 -

Billing Email ................... sdfdsgfdf@126.com

Technical ID .................... hc048483736-cn

Technical Name .................. wan shen

Technical Organization .......... wan shen

Technical Address ............... shanghaishihong kouquchangshalu125hao

Technical City .................. hongkouqu

Technical Province/State ........ HA

Technical Postal Code ........... 200102

Technical Country Code .......... CN

Technical Phone Number .......... +86.02152312352 -

Technical Fax ................... +86.02152312352 -

Technical Email ................. sdfdsgfdf@126.com

Expiration Date ................. 2012-09-07 08:17:10

HiChina Zhicheng Technology Ltd. is an ISP based in Beijing, and I have no reason to suspect that they are involved in the scam. But this Wan Shen based in Hong Kong doesn’t look to have anything to do with UPS.

Now, if you search for "wan shen" shanghaishihong, you find out two things:

1. They also own the domain name micr0supdates.com.

2. micr0supdates.com is listed in a database of malware URLs
(http://www.malwareurl.com/listing.php?domain=micr0updates.com).

As a last interesting point, notice that the expiration date of wwwapps-ups.com is 2012-09-07, exactly one year after the date of the scam email. It seems that this Wan Shen registered the domain name and put it immediately to work...

Giza-IQ Test - Solution 20

2011-08-30T13:21:00.000+10:00

This is the last posting concerning my Giza-IQ test.

Regardless of what numbers are drawn, there are 5! = 120 ways in which they can be ordered. As there is only one way for the five numbers to be in increasing order, the probability is 1/120 = 0.00833...

Giza-IQ Test - Solution 19

2011-08-30T13:19:00.002+10:00

The answer is: 95. They are the decimal digits of Π/5.

Giza-IQ Test - Solution 18

2011-08-25T18:02:00.001+10:00

We have to consider corners, sides and middles separately. Out of a total of 5*4 = 20 positions, there are 4 corners, (3+2)*2 = 10 sides, and 20-4-10 = 6 middles.

Therefore, the probabilities of hitting a particular type of position by choosing a position at random are:
Pc = 4/20 = 1/5
Ps = 10/20 = 1/2
Pm = 6/20 = 3/10

=== Corners
A corner position is adjacent to 3 positions. In order for all 3 to be occupied by mines, it is necessary that the remaining 7 mines are distributed in the remaining 20-4 = 16 positions. The number of ways in which this can be done is given by:

Nc3 = 16! / [(16-7)! * 7!] =
    = 16*15*14*13*12*11*10 / (7*6*5*4*3*2) =
    = 11440

The total number of ways in which 10 mines can be placed in 20 positions is given by:

N = 20! / [(20-10)! * 10!] =
= 20*19*18*17*16*15*14*13*12*11 / (10*9*8*7*6*5*4*3*2) =
= 184756

Therefore, the probability of being surrounded by mines in a corner position is given by:

Pc3 = Nc3/N = 11440 / 184756 = 0.061919504643963

=== Sides

A side position is adjacent to 5 positions. In order for all 5 to be occupied by mines, it is necessary that the remaining 5 mines are distributed in the remaining 20-6 = 14 positions. The number of ways in which this can be done is given by:

Ns5 = 14! / [(14-5)! * 5!] =
    = 14*13*12*11*10 / (5*4*3*2) =
    = 2002

Therefore, the probability of being surrounded by mines in a side position is given by:

Ps5 = Ns5/N = 2002 / 184756 = 0.010835913312693

=== Middles

A middle position is adjacent to 8 positions. In order for all 8 to be occupied by mines, it is necessary that the remaining 2 mines are distributed in the remaining 20-9 = 11 positions. The number of ways in which this can be done is given by:

Nm8 = 11! / [(11-2)! * 2!] =
    = 11*10 / 2 =
    = 55

Therefore, the probability of being surrounded by mines in a middle position is given by:

Pm8 = Nm8/N = 55 / 184756 = 0.000297689926173

=== Result

P = Pc*Pc3 + Ps*Ps5 + Pm*Pm8 =
= 1/5 * 0.061919504643963 + 1/2 * 0.010835913312693 +
    + 3/10 * 0.000297689926173 =
= 0.012383900928793 + 0.005417956656347 + 0.000089306977852 =
= 0.017891164562991 =
= 1.789%

Giza-IQ Test - Solution 17

2011-08-25T18:00:00.001+10:00

Although the items appear to be binary numbers (i.e., numbers expressed in base 2), they are not.

1011, 1001, 1011, and 1010 are 31, 28, 31, and 30 expressed in base 3. They are the number of days in January, February (not a leap-year), March, and April.

The four months that follow (May, June, July, and August) have 31, 30, 31, and 31 days. Therefore, the correct answer is 1011, 1010, 1011, 1011.

Giza-IQ Test - Solution 16

2011-08-20T11:24:00.002+10:00

The buses of line 23 always come shortly after the buses of line 37.
More precisely, (T₂₃ - T₃₇) / (T₃₇- T₂₃) = 7.

Giza-IQ Test - Solution 15

2011-08-20T11:20:00.003+10:00

ONE

TWO

THREE

FOUR

FIVE

SIX

SEVEN

EIGHT

NINE

TEN

ELEVEN

O W R O F I V I N E E

Daily CalcuDoku

2011-08-18T16:08:00.006+10:00

On July 10th, I missed the first anniversary of this blog, but I have just discovered that with the previous article I passed the 100-article mark. Not too bad, even if the visitors are thousands instead of millions.

Anyhow, I invite you to solve my daily CalcuDoku by clicking on the following picture of a partially solved puzzle

A word of warning: these puzzles are very hard!

Then, you can tell me whether you like my implementation better than the Flash application you find in the original KenKen website kenken.com.

Checks on Senior Law-Enforcement Agents

2011-08-16T11:46:00.002+10:00

Yesterday, I watched Four Corners (http://www.abc.net.au/4corners/stories/2011/08/15/3291474.htm), one of Australia’s leading current affairs programs (without advertising), and feel compelled to reflect on it.

It was about Mark Standen, assistant director of the NSW Crime Commission or, to say it plainly, the top lawman in drug-laws enforcement of the most populous Australian state.

To summarise what happened, I will just copy a paragraph from Australian ABC’s website (http://www.abc.net.au/4corners/stories/2011/08/15/3291474.htm ): “On Thursday 11th August, after a five month trial, a jury found Mark Standen guilty of conspiring to import and supply 300 kilograms of pseudo-ephedrine, a chemical that could produce $60 million worth of "ice", or crystal meth. He was also found guilty of perverting the course of justice.”

After a thirty-year career in law enforcement, Standen let himself be corrupted. It probably didn’t help that he had some gambling debts, but for me an important question is: how can an honest man get involved with crimes that literally contribute to killing young people?

My answer is that he must have had in himself enough selfishness to commit a crime regardless of the consequences.

Although obviously I cannot be sure, I don’t think I could ever get involved with drug trafficking. Respect for other human being drives all my relationships, from the most fleeting to those that have remained with me for the largest part of my adult life.

What arrogance to think that, although you earn 250 AU$/year, you are justified in contributing to waste other people’s lives to feed your gambling habits or to buy jewellery from Tiffany for your girl friend.

We know that crooks can be everywhere. In a country like Australia, the vast majority of people at worst only indulge themselves in some tax cheating or driving above the speed limit. Not acceptable activities, for sure, although somehow tolerated by many. But drug trafficking is something else.

I don’t think he became a criminal for some ten thousand dollars. As I said above, he must have held a seed of criminality inside himself well before the opportunity to smuggle synthetic-drug precursors presented itself.

Therefore, a key question for me is: how could such a latent criminal reach the top echelons of law enforcement?

Certainly, Standen must have gone through several levels of vetting checks, specifically design to weed out potential crooks. And yet, he was clever enough to pass them all.

That’s why I support the idea of instituting an independent commission of enquiry into his career in law enforcement.

We know that good networking is essential to progress within any organisation, and we also know that there is solidarity within the ranks of organisations that sometimes have to face popular criticism or opposition, like the armed forces, the fire brigades, the police, the judiciary, etc.

Still, to what scrutiny was Standen subjected before and after reaching senior positions in the NSW Crime Authority? Was he checked at all once he became assistant director? Perhaps not. Perhaps it was thought that if he was there he must have been OK.

Standen’s misdeed were only discovered because the Dutch police found out that an English “drug facilitator” (an interesting item to put on a CV!), was in contact with Bill Jalalaty, an Australian businessman. When the Australian Federal Police, on request of the Dutch, placed Jalalaty’s mobile phone under surveillance, they discovered that he was having suspicious conversations with none other than the top drug-cop of NSW.

Were Standen’s gambling problems known within the Agency and, if yes, why wasn’t he considered to be a risk?

A wide-scoped investigation should ascertain whether the vetting process applied within law-enforcement agencies, especially concerning seniors officials, is sound. Perhaps they are, and Standen was only an exceptional deceiver who managed to slip through the net. An almost-impossible feat never to be repeated for decades to come.

But perhaps the vetting process has shortcomings that should be fixed.

I believe that there should be regular checks on the presence of risk factors, like gambling, medication, and drinking problems. And not only on the subject, but also on his immediate family. I know: right to privacy and all that... But if you want to be a commissioner in a crime authority, you should be prepared to forfeit some of those rights.

There are jobs in law enforcement and intelligence that are too sensitive to be left in the hands of potential crooks. Any risk factor should be carefully considered.

Some criminal will always manage to escape detection. Ultimately, it is the prevailing culture of a nation that determines whether the authorities are honest or not. But checks are better than trust, when so much is at stake.

Giza-IQ Test - Questions 15 to 20

2011-08-12T14:42:00.001+10:00

Here are the last six numeric questions. As usual, I will post the answers one by one in the near future.

2.05 ? W R O F ? V I N E ?

2.06 John has two girlfriends, Linda and Iris. Just in front of John’s place, there is a bus stop for the lines 23 and 37. Line 23 takes him to Linda, while line 37 takes him to Iris. The buses come equally often. Every day, John visits one of his girlfriends. Without looking at his watch, he takes the first bus that comes. After a few weeks though, Linda calls him crying and tells him that she doesn’t want to see him anymore. If he cared about her, she says between sobs, he would visit her more often than once a week. How can it be?

2.07 1011, 1001, 1011, 1010, ?, ?, ?, ?

2.08 Minesweeper is a computer game included in all versions of Microsoft Windows. If 10 mines are placed at random within a field of 5 x 4 positions and you start a round of the game by clicking on a position at random, what is the probability that all the positions adjacent to the one you have clicked on are occupied by mines? Provide the answer as a percentage with three digits after the decimal period.

2.09 628318530717??

2.10 In a game of Bingo with 90 numbers, what is the probability that the first five numbers drawn are in increasing order? (e.g., 2 6 25 72 83 or 50 53 77 82 89)

Giza-IQ Test - Solution 14

2011-08-10T13:08:00.001+10:00

The four-digit numbers divisible by 1892 are:

1892

3784

5676

7568

9460

The numbers that cannot be changed to one of the multiples of 1892 by replacing up to three digits must have all four digits different from those of the multiples. Therefore, the following digits are acceptable:

2 0 0 1

4 1 1 3

6 2 2 5

8 3 3 7

  9 4 9

5

--------

4*5*6*5 = 600

Giza-IQ Test - Solution 13

2011-08-10T13:06:00.001+10:00

1. 25 of the participants solve at least one problem each.

25 = a + b + c + ab + ac + bc + abc

2. Of all those who don’t solve problem A, the number who solve B is twice the number who solve C.

b + bc = 2*(c + bc)  => bc = b - 2c

3. The number of participants who solve only problem A is one more than the number of those who solve A and at least one other problem.

a = 1 + ab + ac + abc  => ab + ac + abc = a - 1

4. Of all participants who solve just one problem, half do not solve problem A.

b + c = 1/2 * (a + b + c)  => 1/2 * b + 1/2 * c = 1/2 * a  => a = b + c

If we substitute 2, 3, and 4 into 1, we are left with an equation in b and c:

2,3 => 1: a + b + c + a - 1 + b - 2c = 25  => 2a + 2b - c = 26

4 => 1: 2b + 2c + 2b - c = 26  => c = 26 - 4b

As both b and c must be positive integers, here are all possible combinations:

b   c

1  22

2  18

3  14

4  10

5   6

6   2

But from 2 we know that b = bc + 2c

Therefore, b must be at least equal to 2c. From the table above, it is clear that this is only possible when b is 6.

I cannot get over it

2011-08-08T13:38:00.003+10:00

This story of Patrizio Galli (see the posting of the 6th) is affecting me more than I would have thought.

I knew four people who committed suicide, and two of them quite well, and in two other occasions, I discovered somebody who had attempted to commit suicide. Also, a very close friend of mine died in a car accident when she was barely thirty years old. Therefore, it is not new for me to have to accept the violent death of somebody I know. And yet, this time it is different.

Somehow, I can understand suiciders. People don’t fall into depression in a fraction of a second. In a sense, you prepare yourself to the eventuality that one day they might try it seriously enough to succeed, despite the best efforts of everyone who cares about them.

And car accidents, unfortunately, are a possibility that is always present in the back of our mids. At least, they are in mine.

But a murder is something else. I know that it did happen, but I still cannot imagine the Patrizio I know raising a monster of a gun and kill Catia. And he had to load it first. And then he fired at her five times, when I am sure that a single shot would have been enough. He just left in the drum a single bullet, to terminate his own life without having to reload.

This throws my perception of humanity into disarray. I had seen on TV similar cases, but I had thought that, somehow, I could have not had anything in common with those perpretators. I implicitly believed that I could have not possibly befriended them.

Then Patrizio.

Does it mean that everybody can do what he did? Almost certainly not. Could I do what he did? I don’t think so. And yet perhaps everybody, pushed strongly enough, can do unimaginable things. It is a disturbing thought. I hope and trust that one day I will be able to shake it off, but not yet.

Giza IQ-Test - Solution 12

2011-08-08T12:19:00.001+10:00

Because we know from the first condition that A cannot finish in the first place, B in the second, etc., we can easily list all the remaining combinations:

BADEC BAECD BCAED BCDEA BCEAD BDAEC BDEAC BDECA BEACD BECAD

BEDAC BEDCA CABED CADEB CAEBD CDAEB CDEAB CDEBA CEABD CEBAD

CEDAB CEDBA DABEC DAEBC DAECB DCAEB DCBEA DCEAB DCEBA DEABC

DEACB DEBAC DEBCA EABCD EADBC EADCB ECABD ECBAD ECDAB ECDBA

EDABC EDACB EDBAC EDBCA

The first condition also eliminates combinations containing one or more of the following pairs of consecutive contestants:

AB BC CD DE

This is what is left:

~~BADEC~~ ~~BAECD~~ ~~BCAED~~ ~~BCDEA~~ ~~BCEAD~~ BDAEC ~~BDEAC~~ ~~BDECA~~ ~~BEACD~~ BECAD

BEDAC BEDCA ~~CABED~~ ~~CADEB~~ CAEBD ~~CDAEB~~ ~~CDEAB~~ ~~CDEBA~~ ~~CEABD~~ CEBAD

~~CEDAB~~ CEDBA ~~DABEC~~ ~~DAEBC~~ DAECB DCAEB DCBEA ~~DCEAB~~ DCEBA ~~DEABC~~

~~DEACB~~ ~~DEBAC~~ ~~DEBCA~~ ~~EABCD~~ ~~EADBC~~ EADCB ~~ECABD~~ ECBAD ~~ECDAB~~ ~~ECDBA~~

~~EDABC~~ EDACB EDBAC ~~EDBCA~~

or:

BDAEC BECAD BEDAC BEDCA CAEBD CEBAD CEDBA DAECB DCAEB DCBEA

DCEBA EADCB ECBAD EDACB EDBAC

The second condition requires that exactly two of the contestant finish in the order DAECB.

D A E C B

BDAEC

BECAD

BEDAC

BEDCA *

CAEBD * *

CEBAD

CEDBA

DAECB * * * * *

DCAEB * *

DCBEA *

DCEBA * *

EADCB * *

ECBAD

EDACB * *

EDBAC

This leaves the following six combinations:

CAEBD DCAEB DCEBA EADCB EDACB

We need to find the combination in which two disjoint pairs of students predicted to finish consecutively actually do so. The pairs are: DA AE EC CB

The solution is EDACB, where the two pairs are DA and CB

Giza IQ-Test - Solution 11

2011-08-08T12:17:00.001+10:00

day k:

m_k = k + 1/5*(m - k - [Sum(m_j) j = 1..k-1])

day k+1:

m_k+1 = k + 1 + 1/5*(m - k - 1 - [Sum(m_j) j = 1..k]) =

= k + 1 + 1/5*(m - k - 1 - m_k - [Sum(m_j) j = 1..k-1]) =

= 1 - 1/5 - m_k/5 + k + 1/5*(m - k - [Sum(m_j) j = 1..k-1]) =

= 1 - 1/5 - m_k/5 + m_k =

= 4/5*(m_k + 1)

Therefore, all (m_k + 1) must be a multiple of 5.

If (m₁ + 1) = 5 => m₁ = 4, m₂ = 4, and all other m_k = 4

That works. From

m₁ = 1 + 1/5*(m - 1)

you can calculate that m = 16. Therefore, n = 4.

If (m₁ + 1) = 10 => m₁ = 9, m₂ = 8, but m₃ = 7.2

If (m₁ + 1) = 15 => m₁ = 14, m₂ = 12, but m₃ = 10.4

If (m₁ + 1) = 20 => m₁ = 19, m₂ = 16, but m₃ = 13.6

If (m₁ + 1) = 25 => m₁ = 24, m₂ = 20, but m₃ = 16.8

If (m₁ + 1) = 30 => m₁ = 29, m₂ = 24, m₃ = 20, but m₄ = 16.8

If (m₁ + 1) = 35 => m₁ = 34, m₂ = 28, but m₃ = 23.2

Increasing the factor that multiplies 5 sometimes pushes the fractional m_ks to higher values of k, but doesn’t eliminate them.

This is not foolproof, but a spreadsheet calculation has verified that there are no other solutions for m₁ up to more than 800.

Patrizio Galli

2011-08-06T12:03:00.006+10:00

Only yesterday I discovered that Patrizio died almost one year ago, on August 20, 2010. I had lost contact with him some years ago and, until yesterday, my Internet searches had found nothing about him.

He was a colleague and a friend. The picture was taken in the Summer of 1983, on the Via Appia Antica, near Rome. I know, it's a bit old, but it is the only one I have of him. He is the one sitting on the column. The nice lady standing beside me is Monika, my wife.

He was a larrikin with an unstoppable sense of humour and an irreverent view on everything. I like to remember him as he appears on this picture, with a smile on his face.

But last August a side of him emerged that would have better remained buried in the deepest recesses of his mind. In the hallway of his two-storey house near Rome, while his two teenage boys were sleeping upstairs, he armed his Smith & Wesson .44 Magnum revolver and shot five times his wife of twenty-six years, Catia. He then directed the gun towards himself and put an end to his own life. He was sixty-two. Catia was forty-seven.

It was the children, awoken by the gun shots, who discovered them. They immediately called for help, but it was too late. I cannot begin to imagine how they felt and how they could inform their three older sisters.

That morning, like many other times in the recent past, a heated argument had exploded between Catia and Patrizio. They were separating. Perhaps some financial difficulties didn’t help, but I can only speculate on the reasons for the conflicts that ultimately led to such a tragedy.

Before Patrizio met Catia, he had had many fleeting relationships and seemed destined to remain an eternal bachelor. But Catia changed him. He became a devoted husband and a patient father, who never laid a hand on any member of his family.

He couldn’t face the prospect of losing the love of his life. But how could he possibly do what he did, knowing that his children would have to live with this tragedy for the rest of their lives? Ultimately, every homicide/suicide is an act of selfishness and an affirmation of power. And yet, I only feel sadness and pain. I cannot bring myself to hate him for what he did. I feel as if he had been hit by a sudden sickness that in a second wiped out his rational mind.

The last time I saw him was in 2003. He showed me his collection of weapons, including the S&W. I still cannot grasp the fact that I held in my hand the weapon that a few years later would be used to kill. It was the revolver made famous by Clint Eastwood in the “Dirty Harry” movies. When it was built, it was claimed to be the most powerful hand gun in existence, and it was a monster. I have fired a .38 and a nine-millimetre, but they felt like toys compared to that .44 Magnum.

Besides being a fun person to be with, Patrizio was also one of the two or three best computer programmers I have ever met. Writing programs is like authoring prose: some people come up with lines that need little editing, sharp and clean. Patrizio was one of those. He was also one of the very few people I have ever met capable of reading a computer manual from cover to cover. And he was a natural, as he had never had any formal training in computer science.

Death is always shocking, but these deaths will accompany me for a while. I don’t believe in an afterlife, but I still feel compelled to say: Farewell my friend. Suffering is over.

Giza-IQ Test - Questions 13 and 14

2011-08-05T12:00:00.000+10:00

2.03 In a contest, three problems, A, B, and C are posed. 25 of the participants solve at least one problem each. Of all those who don’t solve problem A, the number of those who solve B is twice the number of those who solve C. The number of participants who only solve problem A is one more than the number of those who solve A and at least one other problem. Of all participants who solve just one problem, half do not solve problem A. How many participants solve only problem B?

2.04 How many four-digit integers (i.e., between 1000 and 9999) cannot be changed to multiples of 1892 by replacing up to three of their digits?

Giza-IQ Test - Questions 11 and 12

2011-08-01T11:40:00.000+10:00

New month, new questions. I have already posted all my geometrical questions. This month, I have numerical and combinatorial questions for you.

2.01 In a sport contest lasting n days (with n > 1), m medals are awarded. On the first day, one medal and 1/5 of the remaining m-1 medals are awarded; on the second day, two medals and 1/5 of the then remaining medals are awarded; and so on. On the last day, the remaining n medals are awarded. How many days does the contest last and how many medals are awarded altogether?

2.02 Five students, A,B,C,D, and E take part in a contest. One prediction was that the contestants would finish in the order ABCDE. In fact no contestant finishes in the position predicted, and no two contestants predicted to finish consecutively actually do so. A second prediction had the contestants finishing in the order DAECB. This prediction was better: Exactly two of the contestants finish in the places predicted, and two disjoint pairs of students predicted to finish consecutively actually do so. Determine the order in which the contestants finish.

Giza-IQ Test - Solution 10

2011-07-28T22:41:00.001+10:00

Each of the two ants has 4 edges to choose. This gives a total of 4² = 16 possible choices. Of those choices, we have to discard the four cases in which the ants choose the same edge, because then they would meet between their starting vertices after walking 1/2 edge each.

We are left with 12 possible choices. This result can also be obtained by noting that if we let one of the ants choose the edge it likes, then the second ant is only left with three possible choices: 4*3 = 12.

After walking their first edge, in 4 of the 12 possible cases, the ants find themselves still on opposite vertices, while in the other 8 cases, they are at two ends of the same edge.

Now, if they are at the two ends of an edge, it is for them impossible to meet after walking exactly a further edge without one of them having to walk back to its vertex of origin. As the question states that the ants never double back, these possibilities have to be discarded.

As a result of the considerations above, the only cases that satisfy all the conditions are those in which the ants move from a pair of opposite edges to a different pair of opposite edges. The probability is 4/16 = 1/4.

In its new position, each ant can choose one of 3 possible edges (not 4, because ants never double back). Therefore, there are 3² = 9 possibilities. Of these, only 2 lead to a meeting satisfying the required conditions: those in which both ants walk to one of the two vertices that were so far unoccupied by either one of them. The probability is therefore 2/9.

The total probability is given by the product of the probabilities calculated for the two edges: P = 1/4 * 2/9 = 1/18 = 0.0555 .

Giza-IQ Test - Solution 9

2011-07-28T22:35:00.002+10:00

It is a regular Octahedron.

Giza-IQ Test - Solution 8

2011-07-24T18:19:00.001+10:00

If you lie the octahedron on its ADE face, its top view is as follows:

The area of the smallest enclosing rectangle is given by BC, which is 1, multiplied by the projection of DF onto the horizontal plane, which is twice the distance between the centre of a face and one of its vertices = 2 * 2/3 * sqrt(3)/ 2 = 2/3 * sqrt(3)

The height of our box coincides with the distance between the faces ADE and BCF, which is twice the radius of the inscribed sphere.

Using the coordinate axes shown in the figure below, I write the equation of the sphere centred in the origin that has on its surface the centre of one of the faces. If you find a better method for calculating the radius, I’d be happy to hear from you. I just use the first method that comes to mind.

Considering that CDEF is a square of side 1, the distance of each vertex from the centre of the octahedron is sqrt(2)/2. Therefore, the coordinates of the vertices B, C, and F are:

B: (0, 0, sqrt(2)/2)

C: (0, sqrt(2)/2, 0)

F: (sqrt(2)/2, 0, 0)

To calculate the coordinates of the centre of the BCF face, I just average the coordinates of its vertices:

centre of BCF: (sqrt(2)/6, sqrt(2)/6, sqrt(2)/6)

The equation of a sphere centred in the origin is simply x² + y² + z² = r², and r turns out to be sqrt(6)/6.

We can finally calculate the volume of our box as:

V = area of base * height = [2/3 * sqrt(3)] * [sqrt(6) / 3] = 2/3 * sqrt(2)

Giza-IQ Test - Solution 7

2011-07-24T18:14:00.002+10:00

The cubic root of 2 is 1.259921049894873 = ~1.26

The following table shows how many 2-cubes (i.e., cubes of volume 2) fit side-by-side into the length occupied by a given number of 1-cubes:

1-cubes    2-cubes

     1      0

     2                 1   1.26

     3                 2   2.52

     4                 3      3.78

     5                 3   3.78

     6                 4   5.04

     7                 5   6.30

     8                 6   7.56

     9                 7   8.82

   10                 7   8.82

   11                 8    10.08

For example, six 2-cubes need just a bit less space than eight 1-cubes.

To solve the problem, we only need try possible box dimensions starting from the smallest one that can contain a 2-cube. We can afford to do so, because we expect to find a solution pretty soon.

1-cubes     1-vol     2-cubes      2-vol      ratio

2x2x2             8         1x1x1             2           1/4

2x2x3            12         1x1x2              4           1/3

2x3x3           18          1x2x2              8            4/9

3x3x3          27          2x2x2            16         16/27

2x2x4            16         1x1x3             6           3/8

2x3x4            24          1x2x3            12           1/2

3x3x4           36     2x2x3            24            2/3

3x4x4            48     2x3x3            36           3/4

4x4x4            64     3x3x3            54          27/32

2x2x5            20         1x1x3              6            3/10

2x3x5            30     1x2x3            12           2/5   ***

Giza-IQ Test - Solution 6

2011-07-19T11:21:00.000+10:00

If you open the icosahedron, you can easily see that the shortest line between the geometrical centres of two opposite faces is the straight line. This is the geodesic line, which you would obtain in absence of friction if you stretched between the two points an elastic band. If you establish the Cartesian axes as shown in the figure, the coordinates of the two points are (0, 1/3) and (5/2, 2/3).

Therefore, the solution is given by:

d = sqrt((5/2)² + (1/3)²) = sqrt(226) / 6 = 2.505549396395485.

Giza-IQ Test - Solution 5

2011-07-19T11:19:00.000+10:00

The volume of a tetrahedron is baseArea * height / 3. If we extend exactly two edges, they can only be adjacent. If you choose two that are not part of the base, the maximum height is obtained when the rotating edge is perpendicular to the base.

Then, the height coincides with the length of the edge.

The area of the base is sqrt(3)/4. Therefore, the maximum volume of the tetrahedron is:

Vmax = sqrt(3) / 4 * 1/3 = sqrt(3) / 12 = 0.144337567297406.

Giza-IQ Test - Solution 4

2011-07-18T11:05:00.000+10:00

The volume of a tetrahedron is baseArea * height / 3. If we only extend one of the edges that don’t form the base, as shown in the figure, the maximum height is obtained when the rotating face is perpendicular to the base.

Then, the height coincides with that of an equilateral triangle of side 1: sqrt(3)/2.

The area of the base is sqrt(3)/4. Therefore, the maximum volume of the tetrahedron is:

Vmax = sqrt(3)/4 * sqrt(3)/2 / 3 = 1/8 = 0.1250.

Just for fun, we can compare this volume with that of a regular tetrahedron. Its height can be calculated as follows:

h = sqrt( 1² - (2/3)²) = sqrt(5)/3

Therefore, the volume of the regular tetrahedron of unitary edge is

sqrt(3)/4 * sqrt(5)/3 / 3 = 1/12 * sqrt(5/3) = 0.1076...

Giza-IQ Test - Solution 3

2011-07-18T10:55:00.000+10:00

Cut the cone along the line formed by the vertical segment of the string, and open it onto a flat surface. You obtain a triangle with a rounded base. The string slips off the cone when the angle at the top of the opened surface of the cone reaches 180 degrees. That is, when the opened cone looks like a semicircle.

If we take the radius R of the semicircle to be 1, the circumference of the cone base is given by:
C = 2*pi*R / 2 = pi

The radius of the cone base is then given by
r = C/(2*pi) = 1/2

The aperture α of the cone is easily calsulated as follows:
α = 2*arcsin(r/R) = 2*arcsin(1/2) = 60 degrees.

Giza-IQ Test - Questions 9 and 10

2011-07-17T12:02:00.002+10:00

Three more geometrical puzzles. Don’t you like polyhedra? These are the last two geometrical questions. Then, I will have for you numerical ones.

1.09 Four regular tetrahedrons are placed inside a regular tetrahedron that has edges of double length. This is done in such a way that each vertex of the large tetrahedron coincides with one of the vertices of the small tetrahedrons, so that an empty space is left in the middle of the large tetrahedron. Please describe in words the shape of the empty space.

1.10 Two ants are on the opposite vertices of a regular octahedron. They choose at random one of the edges and walk on it at the same uniform speed. Every time each of the ants encounters a vertex, it immediately chooses at random a new edge (that is, it never doubles back onto the edge it has just come from) and walks on it. What is the probability that the two ants meet after each ant has walked on exactly two edges?

Giza-IQ Test - Solution 2

2011-07-16T16:03:00.005+10:00

This is the solution to the second of the two problems I posted on July 11.

1.02 The billiard balls are centred on the vertices of a regular tetrahedron. Their points of contact with each other are in the middle of the edges and, as the radius of the balls is 1, the length of the edges is 2.

To determine the radius of the small ball, we need to subtract 1 (which is the radius of the billiard balls) from the distance between the centre of the tetrahedron (S in the figure) and one of the tetrahedron vertices.

Point A, which is the base of the tetrahedron height, is located at 1/3 of the bottom-face height, while the centre of the tetrahedron is at 1/4 of its height. These two facts are obvious when one considers that A and S are the barycentres respectively of the tetrahedron bottom face and of the whole tetrahedron.

face height = sqrt(2² – 1²) = sqrt(3)

=> 2/3 of face height = 2 / sqrt(3)

tetrahedron height = sqrt(2² – (2 / sqrt(3))²) = 2 * sqrt(2/3)

=> 3/4 of tetrahedron height = sqrt(3/2)

=> small radius = sqrt(3/2) – 1 = 0.2247..

Giza-IQ Test - Solution 1

2011-07-16T15:03:00.005+10:00

Today, instead of proposing more puzzles, I have decided to begin giving you solutions.

This is the solution to the first of the two problems I posted on July 11.

1.01 In the figure the height is not 2/3 of the width, but it doesn’t matter.

We indicate with rs the radius of the sphere and with hc and rc the height and radius of the cone. Further, we can set rc = 1 without any loss of generality. We can then write:

BE = hc - rs = 4/3 - rs

DE = rs

AB = sqrt(hc²+rc²) = sqrt(16/9 + 1) = sqrt(16+9) / 3 = 5/3

AC = rc = 1

The angles EDB and ACE are right angles, and the triangle ABC is similar to EBD. We can therefore write:

BE/DE = AB/AC

If we substitute the lengths of the segments, we obtain:

(4/3 - rs) / rs = 5/3

which, resolved in rs, gives us the radius of the sphere:

r = 1/2

Vc = pi * rc² * hc / 3 = pi * (4/3) / 3 = 4 * pi / 9

Vs = (4/3) * pi * r³ = pi * (4/3) * (1/8) = pi / 6

Vs/Vc = pi / 6 * 9 / (4 * pi) = 3/8

Giza-IQ Test - Questions 7 and 8

2011-07-15T13:58:00.000+10:00

Today’s puzzles are about fitting regular polihedra into boxes.

1.07 A rectangular box can be filled completely with cubes of dimensions 1 x 1 x 1. When the unit cubes are removed and larger cubes, each having a volume of 2, are placed in the box with their edges parallel to the edges of the box, it turns out that they can only fill 40% of the box. What is a possible set of dimensions for such a box?

1.08 What are the dimensions of the smallest rectangular box that can contain a regular octahedron with unitary edge length?

Giza-IQ Test - Questions 5 and 6

2011-07-14T14:13:00.001+10:00

To all French visitors: Happy Bastille Day! For those who don’t know, on July 14th of 222 years ago, the French Revolution exploded. That’s why today is the French equivalent of U.S.A’s July 4th. I wonder what fraction of such momentous events occurred during summer. The Russian national day is (was?) October 25th, and the Chinese one is October 1st, but Italy’s is June 2nd, and the Australian one January 26th (which is during the southern summer)...

Anyhow, today I am going to propose two more of my mathematical puzzles. These two are about Platonic solids: a Tetrahedron and an Icosahedron. Wikipedia says that many viruses, including the herpes virus, have icosahedral shells. Fascinating (as an old friend with pointy ears would say)!

1.05 In a regular tetrahedron with unitary edge length, two (and exactly two) edges are increased in length, thereby increasing the volume of the solid. What is the maximum volume that can be obtained in this way?

1.06 An ant walks on a regular icosahedron with unitary edge length. It goes from the geometric centre of one face to the geometric centre of the opposite face (the geometric centre of a triangle is the centre of the circumscribed circle). What is the minimum distance that the ant needs to cover?

Java - Formatting a Sudoku for the Web

2011-07-13T18:08:00.003+10:00

I just wrote a small method in Java that somebody might find useful. It converts a Sudoku string into HTML.
That is, it converts something like this:

074000610695802743310764089730040025560000034049000870007406300000179000000050000

into something like this:

Here is the code of the method:

I am sorry, but I can only display the source code as an image, because blogspot gets confused with the HTML tags. This shouldn't happen, because I am pasting the HTML code in compose mode. Their application should be able to escape the critical characters, but it doesn't. Very annoying. I wasted at least half an hour trying to escape the greather-than signs manually, but it doesn't let me do it...

In any case, the method creates an HTML file that conforms to W3C’s XHTML 1.0 and CSS level 2.1.

To do the formatting of the output, it defines a different style class for each cell of a box, from top-left (c0, with thick top and left borders) to bottom right (c8, with thick right and bottom borders). It then determines the correct style class by calculating the position of each cell (from 0 to 8) with the formula (kR % 3 * 3 + kC % 3).

I know: it is nothing special for somebody who is familiar with stylesheets and Java. Still...

Giza-IQ Test - Questions 3 and 4

2011-07-12T16:14:00.003+10:00

Here are two more questions to test your intelligence with mathematical and geometrical problems. The first problem I propose to you today was one of the problems I encountered when in 1967 I attended in Rome the selections for the Italian National Math championship. I qualified for the national championship and there I reached the fifth place, thanks to which I became part of the Italian team sent to the IX International Mathematics Olympiad.

1.03 A string is looped around the tip of a cone and pulled down with a weight, so that it hangs on the cone as shown in the figure below.

The aperture of the cone is indicated in the figure with the greek letter α. Assuming that the contact between the string and the surface of the cone is frictionless, what is the minimum value of α in degrees for which the loop slips off the cone?

1.04 In a regular tetrahedron with unitary edge length, one (and only one) edge is increased in length, thereby increasing the volume of the solid. What is the maximum volume that can be obtained in this way?

Giza-IQ Test - Questions 1 and 2

2011-07-11T13:04:00.002+10:00

As you might know, in 2010 I joined several High-IQ societies. half a year later, I started working on an Intelligence Test. After developing twenty-three questions, as it often happens to me, I lost interest and left it unfinished. As I don’t think I will ever complete it, I will publish the questions in this blog. To see the correct answers, you will have to send me an email or comment online.

The following guidelines apply to all questions.

Giza-IQ Test – Solving Guidelines

The name of this test has nothing to do with the Egyptian pyramids. It has only to do with the fact that my name is Giulio Zambon. But it sounds exotic, doesn’t it?

The problems require the level of Math normally acquired during the first couple of years of high school, and also some knowledge of Statistics. Calculus and more advanced Math are not needed.

To answer the questions, you can use whatever resources you find appropriate, but work on your own, and avoid discussing the solutions with anybody else. Failure to do so, will sooner or later compromise the test and possibly invalidate your score.

If a numeric result has more than four digits after the decimal period, unless otherwise requested, ignore in your answer the decimal digits after the fourth one. Alternatively, when possible, you can answer with a simplified expression that, when calculated, provides the result. Radicals don’t need to be above the fraction line. For example, if you wanted to answer √3/3 to one of the questions, you could also express it as 0.5773 or 1/√3.

A fully correct answer receives a score of 1, an answer with a minor error receives a 0.75, a partly-answered question receives a 0.50, and some ideas of how a question could be answered receive a 0.25. The scorer decides how much each answer is worth, and you only get a total score.

Some of the questions are adaptations of or have been inspired by problems of the International Mathematics Olympiads. This might give a small advantage to those who took part in those contests. Nevertheless, the list of participants of each Olympiad is publicly available...

Send your answers via email to giulio(at)good(dot)at(dot)it as a list formatted more or less as follows:
1.01: answer
1.02: answer
...
Together with the list, you should provide the details of your completed and non-completed solutions. It is not strictly necessary, but it will make possible for you to get some credit for partially correct solutions. Keep the details separate from the list of answers. Append them to the email or send them as an attachment. Whatever you find most convenient.

Also, please provide the list of all I.Q. tests you have already done, each one with the result you have achieved. This will make possible to calculate the correlation between the Giza Test and the other tests.

And here are the first two questions:

1.01 A cone of revolution has a height that is 2/3 of the diameter of its base. Consider the largest sphere that you can fit inside the cone. What is the ratio between the volume of the sphere and the volume of the cone?

1.02 Three billiard balls rest on a table in contact with each other. A further billiard ball is placed on top of the three balls and comes therefore in contact with all three of them. Assume that none of the balls moves or rolls away when the fourth ball is put into place. If the radius of the billiard balls is 1 unit, what is the radius of the largest possible sphere that would fit in the space between the billiard balls?

Testing for Rare Medical Conditions

2011-06-27T18:15:00.003+10:00

I am not a Medical Doctor, but I know enough about statistics to talk about the validity of [some of] the tests currently used to screen for prostate cancer.

Two parameters are key to understand how useful medical tests are: sensitivity and specificity. Sensitivity measures what fraction of the affected people that the test successfully identifies, so that the complement to 1 of the sensitivity measures the false negatives. Specificity is the complement to 1 of the fraction of healthy people that the test erroneously flags as affected (i.e., the false positives).

Clearly, a test is better when both sensitivity and specificity are high. A high sensitivity means that few affected people go through the test undetected, while a high specificity means that few healthy people get the scare of a positive test result.

When a test for prostate cancer gives a positive result, doctors recommend a biopsy, which is an invasive and often uncomfortable procedure. Regarding prostate biopsies, Wikipedia says: Biopsies detect prostate cancer in about 25% of men with abnormal screening tests. However a negative biopsy does not ensure the absence of disease. Repeat prostate biopsies are positive in about 25-30% of patients whose initial biopsy was negative. Now, Wikipedia is not always reliable, but I have read from other sources that prostate biopsy is not particularly dependable. To complicate the picture, I have also read (don’t remember where) that many prostate cancers are not malignant, and people can live with them without consequences.

I know: my last paragraph is just hand-waving. Without references to original sources, my statements have no scientific value whatsoever. But, now that I have written it, I don’t like to remove it. Let me leave it at that and go back to statistical analysis.

For the purpose of this post, I will consider two tests: PSA (Prostate-Specific Antigen) and PCA3 (Prostate Cancer Antigen 3). PSA measure the level in urine of a protein produced by the prostate gland. PCA3 checks for the presence of a gene.

The following table for PSA comes from an article on the website of the Prostate Cancer Research Institute (www.prostate-cancer.org/pcricms/node/122):

PSA (ng/mL)	Sensitivity	Specificity
1.1	83.4	38.9
1.6	67.0	58.7
2.1	52.6	72.5
2.6	40.5	81.1
3.1	32.2	86.7
4.1	20.5	93.8
6.1	4.6	98.5
8.1	1.7	99.4
10.1	0.9	99.7

The study was conducted (if I understand it correctly) on 5,587 subjects, of whom 4,362 had no cancer of any type. The Symbion Laverty Pathology Lab that conducted my PSA test a few months ago stated that a level below 4.5 ng/mL is considered ‘normal’ (although, to be picky, the correlation between PSA and prostate cancer actually changes with the age of the subject).

If you (linearly) interpolate the table, you find that the specificity for a PSA of 4.5 is 94.7%. Considering that specificity as a function of PSA ‘flattens up’, we can be generous and say that the cut-off is around 95%. This means that 5% of healthy subjects will be encouraged to take a biopsy if their PSA is 4.5 ng/mL or higher. Similarly, the interpolated sensitivity for a PSA of 4.5 is 17.3%, which I am happy to generously round up to 18% to be on the safe side.

The following data, relative to PCA3, comes from an article published by Reviews in Urology and accessible via the website of the American National Institute of Health (www.ncbi.nlm.nih.gov/pmc/articles/PMC2556484/):

PCA3 Cut-off	Sensitivity (%)	Specificity (%)
5	96	14
20	71	56
35	54	74
50	40	83
65	32	91
90	20	95

The study was conducted on 570 men, of whom 36% tested positive. But what does it mean ‘positive’? It was decided to use a PCA3 cut-off of 35 (whatever that means...), because that score (I quote) combined the greatest cancer sensitivity and specificity. Indeed, 35 is the value that maximises both the sum and the product of sensitivity and specificity.

Notice that, like with PSA, higher specificity is associated with lower sensitivity. This obviously makes a lot of sense: the price you pay to reduce false positives is to get more false negatives.

To summarise, the two major tests used to diagnose prostate cancer (if we exclude the practice of sticking a finger up your anus to check whether your prostate is too enlarged to be considered healthy) have sensitivities respectively of 17% and 54% and specificities of 95% and 74%.

Let set these figure aside for a moment to concentrate on the incidence of prostate cancer. I will use the figures provided by the Prostate Cancer Foundation of Australia (www.prostate.org.au/articleLive/pages/Prostate-Cancer-Statistics.html), but I am very confident that my conclusions will be applicable worldwide.

54 out of 1000 men in their sixties are on average diagnosed to have prostate cancer (1/1000 for the 40s, 12/1000 for the 50s, and 80/1000 for the 70s). This formulation is in my opinion a bit ambiguous, because it is not clear to me whether all those with a positive diagnosis actually had the cancer. And it doesn’t say how many men had a cancer that remained undiagnosed. But let’s move on, because it will not significantly affect the result of my analysis.

OK. If I assume that 54/1000 measures the ‘real’ number of Australian men in their 60s with prostate cancer, I now have all the information I need to calculate the number of PSA and PCA3 tests that give a positive result.

	Sensitivity	Specificity	Positive (1000 subjects)
	Sensitivity	Specificity	Sick (54)	healthy (946)
PSA	18%	95%	10	47
PCA3	54%	74%	29	246

All in all, more than 82% (obtained as 47/(10+47)) of the men that might subject themselves to a biopsy because of a positive PSA test wouldn’t need to do it at all. And the figure rises to 89% with the PCA3 test. And imagine the shock of being diagnosed with cancer! Furthermore, if you happen to have prostate cancer, PSA will only detect it with a probability of 18%, while PCA3 will detect it with a probability just above fifty-fifty.

I might be too analytical, but to me, a test for prostate cancer doesn’t seem worth doing.

Then, you might ask, why did I decide to get a PSA test done? Well, I did it and I didn’t... My doctor decided to do it against my expressed desire not to have it done. Fortunately, it came back with 0.31 ng/mL. That is, the result was so low that the sensitivity was off the lower end of the scale, probably 90% of better. But next time I am going to insist. No more PSA test for me!

In general, the statistical problems with medical tests occur when the disease being tested is rare, even if the test is very good. To explain why, let’s look at two very good tests, one for a hypothetical disease that affects 1% of the population and one for an equally hypothetical rare disease that affects 0.01% of the population. Further, let’s assume that both tests have a sensitivity of 100% (actually impossible, because there are always cases that remain undiagnosed, but bear with me) and a specificity of 99.99%.

With the more common disease, when screening 10,000 subjects, the test correctly identifies the 100 sick people and gives a positive result for 9900 * 0.01% = 0.99 ≈ 1 person who is in fact healthy.

With the rarer disease, when screening 10,000 subjects, the test, as in the previous case, identifies all sick people and picks 9999 * 0.01% = 0.9999 ≈ 1 person who is healthy. But this time, the number of sick people is also 1. Therefore, half of the people for whom the test gives a positive result are in fact healthy.

Next time your doctor suggests that you take a test, perhaps you should check whether it is worth the effort. I wonder what the sensitivity and specificity of the many tests the doctor prescribe for check-ups actually are. And how rare are the pathologies being tested for? MMmmm...

Equinoxes in Canberra

2011-06-26T14:53:00.001+10:00

I noticed a discrepancy in Canberra equinoxes that I cannot explain. Perhaps one of you will be able to shed some light on this puzzle.

At an equinox, day and night have the same duration and, if you are in the middle of your [theoretical] timezone, you see the Sun rise at 0600 and set at 1800.

Canberra is almost in the middle of its timezone, but not exactly. It would be smack in the middle if it were located at a latitude of 150° East, but it is only 149° 8’ east of Greenwich. As 24h correspond to 360°, that degree of difference means that sunrise and sunset at the equinoxes are theoretically delayed by approximately four minutes. Consequently, on March 23rd and September 20th, the Sun should rise at 0604 (plus daylight saving in March) and set at 1804.

What I cannot explain is that the delay, instead of the expected four minutes, is between nine and ten minutes in March and between two and three minutes in September. The discrepancy in September could perhaps be explained with roundings and with the fact that equinoxes actually happen at different times of the day. But, considering that the times of sunrise and sunset only change very slowly, at a rate of around a minute per day, the difference of five to six minutes in March remains unexplained.

Any idea?

Just for fun, I calculated how far from its current position should Canberra be in order to be exactly 10 h ahead of Greenwich. The length of the equator is 40,075 km. As Canberra’s longitude is 35° 15’ South, it means that the parallel passing through Canberra ihas a length of approximately 40075 * cos(35° 15’) = 32,727 km. Therefore, to be in the middle of the +10 time zone, Canberra should be 32727 / 360 ≈ 91 km more to the East. But, I suppose, that didn’t figure very high on the founders’ priority list. In any case, it would have been on a mountain range. Not easily accessible...

Arrays of Functions in Java

2011-06-22T17:12:00.002+10:00

A couple of months ago, shortly after publishing the book Sudoku Programming (also see the post in this blog), I asked myself whether I should have written the programs in Java instead of classic C.

I had chosen C because I thought it would be easier for non-programmers to deal with a procedural language rather than with Object Oriented programming, with its class inheritance and operator overloading. But, looking at the number of functions I needed for the C implementation, I began thinking that in Jva the implementation would probably have been simpler. I simply had to re-develop Solver and Generator in Java. I simply had to do it.

One of the first problems I encountered was how to implement in Java an array of function pointers.
I needed it in order to execute in sequence all the puzzle-solving strategies. In C, I had defined a pointer to a function as follows:

typedef void (*f_ptr_t)(void);

This allowed me to define an array of pointers to strategy functions:

f_ptr_t strats[] = {a_strat, another_strat, a_third_strat};

int n_strats = sizeof(strats)/sizeof(f_ptr_t);

All I needed to do to execute the strategies in sequence was then to write a for-loop as follows:

for (int k_strat = 0; k_strat < n_strats; k_strat++) {

   strat[k]();

}

To do the same in Java, I defined a Strategy class containing the following method:

public void execute() {

     System.out.println("*** " + this.getClass().getName()

           + " does not redefine the method execute()"

);

}

Then, I defined all strategies to be subclasses of Strategy and to implement the execute() method. For example:

class aStrat extends Strategy {

   public void execute() {

       //...

}

}

Finally, I defined a StrategyArray class as follows:

class StrategyArray {

   protected static final Strategy STRATS[] = {

        new aStrat, new anotherStrat(), new aThirdStrat()

};

   public static void executeStrategies() {

       for (int kStrat = 0; kStrat < STRATS.length; kStrat++) {

          STRATS[k].execute();

}

}

}

In reality, I grouped the strategies according to their level of complexity and implemented STRATS as a two-dimensional array, with the first index being the level of complexity of the strategies, ranging from 0 to 3. Also, obviously, STRATS didn’t need to be static, but that allowed me to execute the strategies with:

StrategyArray.executeStrategies();

Instead of having to create a StrategyArray object as in:

StrategyArray strats = new StrategyArray();

strats.executeStrategies();

You might wonder why I didn’t define the Strategy class and its execute method to be abstract, instead of defining a method that displays an error message on the console if it is not overriden. The reason is that I defined in Strategy other methods that need to be overridden, but not all subclasses (i.e., strategies) need them all. The alternative solution of defining more than one interface and have each strategy implement only the relevant interfaces seemed cumbersome.

Sudoku Explained

2011-05-29T16:17:00.001+10:00

I have just released the book “Sudoku Explained”.

This book tells you in a very practical way how to solve Sudoku puzzles. First, it describes in detail and with examples fourteen solving strategies, from the very simple to the very complex. Then, it explains how to apply the strategies you have learned to forty puzzles of increasing levels of difficulty. No other book will teach you how to solve Sudoku puzzles as effectively as this one, but be warned: after reading it, you will discover that the puzzles in your local paper are not so challenging after all!

For now, it is only available on Lulu, either in print for US$9.99 or as an eBook in PDF format for US$4.99.

Introduction

Welcome to Sudoku Explained. The purpose of this book is to help you become a Sudoku champion. Not everyone has the pattern-recognition abilities to become a champion, and I cannot guarantee that you will succeed, but I can point you in the right direction. The rest is up to you.

The WorldWide Web is full of explanations about Sudoku. You can find the description of many strategies and lots of examples. What I believe you will only find in this book is a systematic and consistent description of all significant strategies coupled with commented solutions of puzzles.

For this book, I have chosen forty Sudokus I generated with the program described in my first Sudoku book (Sudoku Programming). They all have thirty-three clues and look like medieval crosses, because the central row and the central column are always already solved.

Their difficulties range from easy to diabolical, measured as the number and complexity of the solving strategies they require. It is true that, in general, puzzles with fewer clues are easier, but what is true statistically, doesn't apply to each individual puzzle. I have seen very easy puzzles with only seventeen clues, while the last puzzles in this book, despite their thirty-three clues, are as challenging as they come.

Chapter 1 describes the terminology I use throughout the book.

Chapter 2 explains in detail fifteen strategies grouped in four levels of complexity, from 0 to 3.

Chapter 3 presents the Sudokus. Puzzles 1 to 10 can be solved with level 0 strategies; 11 to 20 require level 1 strategies; 21 to 30 are at level 2, and 31 to 40 are at level 3.

Chapter 4 provides the solutions of the puzzles shown in Chapter 3. For the puzzles at level 1, I also list a sequence of strategies capable of solving them, while for the puzzles at level 2 and 3, I explain the application of the more complex strategies in detail.

Have fun with Sudoku!

As an example of how I describe strategies, here is the description of ‘naked pair’

If two cells in the same unit only contain the same two candidates, it means that one of those candidates will solve one of the two cells, and the other candidate will solve the other cell. Therefore, the same candidates can be removed from all other cells of the unit.

For example, suppose that box 3 has reached the point shown in Figure 2-2.

Figure 2-2: A naked pair

The two cells (4,0) and (4,2) contain the naked pair 8 and 9. If 8 solves (4,0), then 9 must solve (4,2). If, on the other hand, 8 solves (4,2), then 9 must solve (4,0). In either case, both 8 and 9 are used. Therefore, the 8s in cells (5,0), (5,1), and (5,2) as well as the 9s in cells (3,1) and (3,2) can be removed.

Example of how I explain a solution in detail (excerpt)

'unique': 5 in (2,8) is unique within the column

remove 3 and 6 from (2,8)

solved (2,8) with 5

'unique': 9 in (0,0) is unique within the row

remove 1 and 2 from (0,0)

solved (0,0) with 9

'unique': 6 in (0,5) is unique within the box

remove 3 from (0,5)

solved (0,5) with 6

At this point, 53 cells have been solved and many candidates removed, but it is not possible to proceed further with level 0 strategies. Applying ‘naked pair’ twice does the trick:

‘naked pair’: (1,3) and (1,5) in row 1 contain the pair 35

remove 3 from (1,1)

remove 3 from (1,2)

‘naked pair’: (1,1) and (6,1) in column 1 contain the pair 28

remove 2 from (7,1)

solved (7,1) with 1

'cleanup' of row 7: remove 1 from (7,7)

solved (7,7) with 2

Example of how I describe the application of a complex strategy

Puzzle 22 after level 1 strategies

To solve the puzzle, you can apply ‘Y-wing’ to the three cells (6,7), (8,6), and (8,5), containing respectively the pairs 81, 19, and 98. The cells (6,3), (6,4), (6,5), (8,7), and (8,8) are ‘visible’ from both (6,7) and (8,5). Therefore, the candidates for the digit 8 can be removed from them. This boils down to removing a single 8 from (6,5), but that is enough to ‘unlock’ the puzzle, which you can then solve by applying a series of ‘cleanup’s.

Casualties

2011-05-24T13:43:00.001+10:00

Another Australian soldier has died in Afghanistan. It saddens me to think that a hail of nails and ball bearings on a dusty road killed a young, strong, and courageous man. Like most people, I know what it means to lose somebody you care about, and my thoughts go to Sergeant Wood’s wife.

Still, as sorry as I was to hear of Brett Wood’s death, I was amazed to hear radio commentators ask whether the Australian presence in Afghanistan will be affected by it. At risk of appearing cynical, one more death doesn’t change anything. I don’t even understand why anybody would raise the issue at all. Of course the Australian policy concerning Afghanistan will not change. And rightly so. With a dangerous operation involving thousands of soldiers and civilians, we can be happy that only twenty-four have died. There will be more casualties. For sure.

Should we be in Afghanistan at all? I will answer with another question: if you saw a bully humiliate a weaker child on a schoolyard or a violent man assault a woman, should you intervene? To what extent do you try to reason with somebody who bases his existence on violence and abuse? It comes to a point where you cannot simply look on and enjoy your peaceful corner of the world.

I am not so naive as to think that interventions in countries like Afghanistan and Libya are purely for humanitarian reasons. And the proof of that is that many/most/all governments have a history of supporting tyrants as long as their actions suit the perceived interests of western countries, like when the USA armed Saddam Hussein because he was at war with Iran.

Nevertheless, I think there would be less suffering in our world if the Taliban were prevented from practising their medieval beliefs.

To make another parallel, I don’t like antibiotics and heavy drugs, but sometimes they are necessary. A healthy diet and some placebos like Homeopathic medicines and food supplements are not always enough. The Taliban and groups like Al Qaeda are like tumours and drug-resistant viruses. If what it takes to keep them in check is chemotherapy, then so be it.

And now that I have started with this tirade, I feel compelled to talk about Israel as well. No idea why. The Israelis think that the centuries of prosecution culminating with the Holocaust give them the right to do what they want. They reject criticism directed towards their policies by saying that it is a manifestation of anti-Semitism. And most governments let them get away with it for fear of upsetting significant parts of their electorates.

This is nonsense. Israel is an arrogant little state that has been oppressing the Palestinian people for decades. They feel threatened by the countries that surround them. I understand that. And we shouldn’t forget the Holocaust. But it is time that we look at the Israeli for what they are and what they do right now, rather than feel sorry for what Hitler did to their grandparents.

Refugees

2011-05-04T15:59:00.001+10:00

The members of Mensa Australia exchange ideas via a mailing list.

On May 1^st, one of the members posted the following message, under the heading “cost-benefit of refugees”:

To an Economist, cost and benefit is everything.

I am under no doubt that the benefits of the Royal wedding clearly outweigh the costs.

There is another Government made decision that I believe is costing the Australian Taxpayers far more than has yet been revealed.

The decision by the Rudd Government to scrap temporary visas has resulted in an additional 3,000 illegal immigrants arriving at our processing centres each year.

How much extra has this single decision cost Australian taxpayers?

Let's look at the costs: (Assume illegal/refugee stays in detention for four years)

Basic legal costs per refugee applicant: $200,000

Housing at Christmas Island: $400 million per year, so $150,000 per refugee for the four years.

Welfare payments: $50,000 per year = $200,000

Offshore Management $156 million per year. $50,000 per refugee.

Christmas Island infrastructure improvements: $120 million over 4 years: $10,000 per refugee

Additional patrolling costs: $100 million over 4 years. $10,000 per refugee

Regional costs to assist handling refugees coming here: $33 million per year. $10,000 per refugee

Each additional refugee will cost us around $630,000 over the period of his stay in detention. With an extra 3000 refugees coming in as a result of that policy, that is costing taxpayers and additional $2 billion per year.

Is this where you want your taxes to go, or can you see better ways to utilize your money?

The refugee program in total (13,500 per year) could well be costing four times this amount, particularly when you factor in the low employment skills and high crime rates of the people coming in here.

On May 3^rd, the former State Representative for the Australian Capital Territory replied with the following (I took the liberty of correcting a couple of trivial typos and removing the name of the member who posted the original message). Note that I have interspersed the comments provide by the original member in a subsequent message.

I believe there is a lot of unwarranted bias here.

I too am an economist, but I believe that there is more to life than cost-benefit analysis.

This concept was very popular in the 60s especially, and is the basis of many decisions in our economy.

But..... it is not always appropriate.

Apart from the question whether 's calculations [...] are an accurate reflection of what it costs our government to admit refugees;

and apart from the fact that fails to introduce even one benefit (over a 40-50 year period of residency in Australia?),

is blaming the refugees. Why.....

I am not blaming the refugees. I blame the decision makers who are inviting people here who have little hope of fitting in. Refugees are acting in their own best interests. They look for the easiest targets in first world countries and exploit any loophole to get here and to stay here.

If the Western alliance of which we are a member, had not started fighting in Iraq, Afghanistan, and before that the English meddling in the Middle East, there would not be many refugees from these countries.

Our government is not only complicit (even if inherited from previous governments) in the reasons refugees come here thru our military actions, but our trade practices too influence the situation of people living in these countries. And while some come for economic reasons, most are trying to escape violence.

Their countries have cultures of violence that sometimes date back hundreds of years.

What we need to do, is not locking them up for years till ASIO has finally figured out that they cannot find anything against a certain refugee, we need to put these people in schools.

The refugee camps need to become schools where we teach them how to live in a modern western society. Teach them not only our language, but our laws, customs, and culture.

And indoctrinate them concerning our abhorrence of the use of arms. Make sure they understand that peace and non-violence is our way of life.

This may not be foolproof, but it should make them fit into our society a lot easier.

Have you tried teaching Lebanese in schools? About half of them are hyperactive and have no respect for authority. I would dread trying to contain in a classroom someone who has been roaming around with an AK47 eliminating anyone who crossed his path.

After all, how can we expect an 18-yr old, who grew up in a desert surrounded by marauders, to fit in with the peaceful side of Australian Society if we keep them incarcerated in a remote, semi-violent environment for a year or more before we let them loose in our cities?

This would probably increase 's “cost” side of the equation. But the Benefits side would increase enormously.

In my twenty years of teaching, I learned that the cast is set before the child enters Primary School. Trouble makers in grade one are trouble makers all the way through. One year of deportment classes will have zero impact I am afraid. Wouldn't you prefer to see the billions of dollars we spend on assimilating refugees in Australia spent to the benefit of hundreds of thousands of people in countries of need rather than the few thousand here who have jumped the queues?

At this point, I felt I couldn’t let it rest, and posted the following message:

Money, money, money...

I seriously question the current policy of keeping boat people interned for years. It is inhumane and makes no sense. People who manage to obtain a passport and come to Australia by plane are not forced into a camp. But some people are not so lucky. To escape their place of birth, they feel forced to risk the life of their children and place themselves in the hands of unscrupulous smugglers. Why should we treat these two groups of refugees so differently? Why can refugees who come by air freely move in our society while boat people cannot? As I said, it doesn't make any sense. Immigration and ASIO should process and check out boat people exactly as they do with 'plane people'.

AND THERE IS NO QUEUE! There are just desperate people coming into our country however they can. Or should we think that some people prefer to risk their life on rickety boats and endure years of confinement rather than fly in on a commercial jet? Come on... If anything, from a humane point of view, it would make sense to process the boat people more swiftly than those who come by plane. And a passage on a boat easily costs more than an economy-class aeroplane ticket. That alone should tell you how desperate some of these people are.

Modern economy ignores everything it cannot put a price on. That leads to apparently logical but in reality inhumane conclusions. Hitler's final solution was logical when seen from the perspective of Nazi-Germany racism; forced repatriation of Chinese was logical in the context of the white-Australia policy; and the slogan 'stop the boats' is logical in a context of an uncaring political party that manipulates fears in the less educated among us.

To be honest, I only care about the money spent on boat people because, and I agree with , we should invest it in educating them rather than wasting it on keeping them locked up.

Besides, if everybody in this country only focussed on money, we couldn't function as a society. That is, if all the volunteers and carers that supplement our 'official' welfare expected to be paid for their work, we would become a ruthless and uncaring society. This goes a long way to prove that we shouldn't look at money as the only thing that matters.

There might be further postings on this subject, but I felt that many non-Mensans would be interested in confirming that a high-IQ has nothing to do with being a humane and caring person.

Sudoku Programming

2011-04-24T11:59:00.005+10:00

I have finally completed my book “Sudoku Programming”.

The purpose of this book is to teach you how to write computer programs to solve and generate Sudoku puzzles. If you love Sudoku and have some knowledge of computer programming, you will have no problem in understanding the code of my Sudoku Solver and Sudoku Generator.

I have included in the book the full listings of both programs and an explanation of each C module, with walk-throughs and examples. To make your life easier, I have also included a description in detail of the sixteen solving strategies implemented in the Solver and a summary of the C language.

By following the instructions contained in this book, you will be able to create a practically unlimited number of original Sudokus. To stimulate your creativity, I have also added a chapter about Samurai Sudokus, and a program to help you generate them.

This is a practical book that will provide you with everything you need to write your own books of Sudoku Classic and Samurai puzzles.

It includes 365 pages, 107 figures, and 111 listings. Inside the book, you will also find the URL from which you can obtain the source files. And here is the top-level table of contents:

Table of Figures

Table of Listings

About the Author

Introduction

1. Modelling a Sudoku Puzzle in C

2. The Strategies

3. Main Program & Utilities

4. Implementing ‘unique’

5. Implementing ‘naked’ Strategies

6. Implementing ‘hidden’ Strategies

7. Implementing ‘box-line’

8. Implementing ‘pointing-line’

9. Implementing ‘lines’ Strategies

10. Implementing ‘Y-wing’

11. Implementing ‘XY-chain’

12. Implementing ‘rectangle’

13. Implementing ‘backtrack’

14. Solving Thousands of Puzzles

15. Generating Sudokus

16. Puzzle Statistics

17. Puzzles

18. Samurai Sudokus

A. Introduction to C

B. Development Environment

C. Puzzle Solutions

D. Abbreviations & Acronyms

Strategy Index

After talking with some possible publishers, I arrived to the conclusion that it would be almost impossible to find for it a suitable “home” and decided to self-publish it. For now, it is only available on Lulu, either in print for US$30.00 or as an eBook in PDF format for US$4.99.

It will become available on Amazon and other online retailers, but it is unlikely that you will see it in a brick-and-mortar bookstore. Bookshops are very reluctant to buy books printed on demand because they cannot return unsold copies.

What are you waiting for?

Code Red

2011-04-16T17:09:00.000+10:00

I haven’t been posting anything for a while. I thought, perhaps I can entertain you with a micro-story I wrote last year. It is a slightly modified version of a story that was shortlisted in the “Positive Words” mini-competition of February 2010, open to stories not longer than 100 words. I tell you, it wasn't easy to write a story with a character and a plot in 100 words...

I clench my teeth. The cockpit is a cacophony of beeping sounds. The instrument panel a kaleidoscope of flashing red lights.

“Captain...”

I nod, without taking my eyes off the angry sea of grey before me. With all the checklists exhausted, there is nothing more to say.

Few seconds later, the plane hammers onto the tarmac, its frame jarred by the impact. The engines scream in reverse.

A lineup of fire trucks emerges from the fog on the right side of the runway. This time they will not be needed.

In the back, the passengers erupt into applause.

KenKen - One more case

2011-03-07T14:24:00.002+11:00

Here is one more interesting strategy I discovered when solving one of my CleverClever puzzles.

The four-cell cage on the right shows all possible candidates of each cell. We can discard the 1 of (5,8) because the sum must be even and the three other cells only have even candidates. Then, as the 1 of row 5 can only be in (5,1), we can remove all other candidates from that cell and the corresponding candidates in the other cell of the cage.

KenKen - A non-trivial case

2011-03-06T16:10:00.000+11:00

Solving one of my CleverClever puzzles, I encountered the following configuration:

Suppose that the 112x cage is solved by the combination [8 7 2 1]. Then, the 8 must be in (7,5), because there is already an 8 in either (3,6) or (4,6). But if that is the case, then the remaining three cells of the cage, all in column 6, must contain 7, 2, and 1. This leads to a contradiction, because it would force us to remove the 1s in (2,6) and (8,6), thereby leaving both cells with a 9 as the only possible candidate. Therefore, the 112x cage must be solved with [7 4 2 2] (which, incidentally, means that (7,5) must contain a 2).

I don’t have a name for this strategy, but it is a nice example of a technique that does not (and cannot) occur in Sudoku.

KenKen Strategies

2011-03-05T16:38:00.002+11:00

Most of the strategies used to solve Sudoku rely on the interplay of boxes and lines. Therefore, it is not surprising that they are not transferable to KenKen^® (registered trademark of Nextoy LLC).

To see what Sudoku strategies do apply to KenKen, I will first define the concept of segment. A segment is a collection of cells belonging to a cage that are also on the same line (row or column). In the following example with four cages, the horizontal segments (along a row) are: A, BC, DE, F, G, H, IJ, KLM, and N, while the vertical segments (along a column) are: AF, B, CH, DI, EJN, GL, K, and M.

What follows is a list of Sudoku strategies adapted to KenKen.

‘Naked single’: If a cell only has a single candidate, that candidate must solve the cell. This is obvious: if there are no other possible candidates in a cell, the only one present must be it.

‘Unique’: If a candidate for a particular number is found in a single cell of a line (row or column), it must solve the cell.

‘Cleanup’: When you solve a cell, the digit that solves it cannot be a candidate anywhere else in any of the lines to which the cell belongs.

‘Naked pair’: If two cells in the same line but belonging to different cages only contain the same two candidates, it means that one of those candidates will solve one of the two cells, and the other candidate will solve the other cell. Therefore, the same candidates can be removed from all other cells of the line.

And now a couple of KenKen-specific strategies.

‘Pointing segment’: If you know one or more digits of a segment, even if you don’t know which cells they individually solve, you can remove candidates for the same digits from all other cells of the line to which the segment belongs.

‘Solving order’: Solve first all the cages that only contain one cell. Then write down the candidates of the cages with two cells that can only be solved by one, two, three, or four pairs. As next, look at cages with high totals obtained by multiplication, because they are likely to have a low number of possible combinations. Straight cages are always easier to solve than cages with bends.

Look for example at the following puzzle:

You can immediately write 8 in cell (0,4) and 4 in cell (8,5). Then, notice that the cages [(1,8) (2,8)], [(2,5) (3,5)], [(3,8) (4,8)], [(4,7) (5,7)], [(6,2) (7,2)], and [(7,3) (8,3)] all admit only one pair of combinations. You can therefore fill them with the pairs of alternatives [9 1], [9 8], [8 5], [9 8], [8 1], and [7 3].

At this point, also the cage [(5,8) (6,8)] can only be filled with a single pair of alternatives. Normally, to obtain a total sum of 13 you can add any of the pairs [9 4], [8 5], and [7 6], but in this case, as the digits 9 and 8 have already been allocated to other segments of the same column, only the pair [7 6] remains. As an example of a pair with more alternatives, I filled in the cage [(4,5) (5,5)} with the possible alternatives [6 1], [3 2], [2 3], and [1 6].

The square cage at the top [(0,5) (0,6) (1,5) (1,6)] requires a product of 200. The prime factors of 200 are 2 2 2 5 5. This means that the four cells must hold either [8 5 5 1] or [5 5 4 2].

The cage [(7,4) (7,5) (7,6)] can only contain [9 7 5], because the factors 0f 315 are 3 3 5 7. This means that the 7 that we had considered possible for the cell (7,3) has become impossible.

Similarly, the cage [(4,1) (4,2) (5,1)] can only contain [1 7 7], because 49 only admits the two factors 7 7. As a result, we can remove the pair [1 6] from the cage [(4,5) (5,5)].

At this point, the puzzle looks as follows:

Incidentally, I have found out how to make my CleverClever puzzles solvable analytically. At least, I have managed to solve the first ten I generated, although in a couple of cases only on the second attempt.

KenKen

2011-02-23T16:56:00.005+11:00

Some weeks ago, I discovered the Sudoku-like puzzle KenKen^® (registered trademark of Nextoy LLC). In Japanese, Ken means ‘clever’. I say ‘Sudoku-like’ because it consists of a grid to be filled with digits. Like with Sudoku, every digit can only appear once within its row and once within its column. But, instead of square boxes, KenKen^® contains cages, which can hold between one and seven (the largest cage I have encountered) contiguous cells. There are no initial clues, but for every cage, the puzzle provides a number and an operation with which the number is to be achieved.

Here is an example of an empty KenKen^® grid:

For example, the cage marked 36x and located smack in the middle of the puzzle must be filled with two numbers whose product is 36. As the side of the puzzle has a side length of nine cells, it means that the numbers must be between 1 and 9 (you can make puzzles of any size). Clearly, there are only two possible pairs that can solve the cage: (4 9) and (9 4). Another example: the 4-cell cage marked with 162x in the top row can only contain one of the combinations (1 3 6 9) and (2 3 3 9). It can contain two 3s because they can be placed in such a way that they don’t share either row or column. A third (and last) example: the two cells close to the bottom-left corner marked 4: can contain any of the combinations (1 4), (2 8), (4 1), and (8 2).

If you are interested in trying it out, you will find a new daily puzzle posted at www.kenken.com/playnow.html.

Some strategies are similar to those used to solve Sudoku, but the more complex Sudoku strategies don’t play any role with KenKen^®.

Obviously, as soon as I discovered KenKen^®, I decided at once to write a program to generate my own puzzles. The puzzle you see in this post is one of those I generated. Note that I cannot call it KenKen^® because that name is trademarked. It was not an easy task to generate a KenKen^®-like puzzle and I am quite proud of the result.

A tricky hurdle was to ensure that the puzzles I generated only admitted a single solution. Look for example at the following partial puzzle:

You could swap the 8 and 2 in the two cages and obtain a valid solution. I did fix this problem with a specific check, but I then realised that it was not sufficient to guarantee unicity. Here is an example that shows why checking for pair swaps is not enough:

Clearly, you can solve the puzzle by placing in the three pairs of cells either one of the two permutations [(2 3) (3 8) (8 2)] and [(3 2) (8 3) (2 8)].

Further, you can also imagine much more complex permutations of several cells. The only way to ensure the unicity of the solution was a brute approach rather than an analytical one: try all possible permutations of all cages.

Implemented the check for unicity, I was able to generate CleverClever puzzles. Unfortunately, the fact that the puzzles were correct and admitted a single solution didn’t make them enjoyable. When I tried to solve the puzzle you see at the beginning of this post, I discovered that there were too many combinations that remained after applying all analytical strategies I had practised on the puzzles made available by kenken.com over a period of a few weeks.

That’s when I decided to give it a rest and go back to it in a while, with a fresh mind. I have to understand how the cages interact with each other to reduce the number of possible combinations. I can generate valid CleverClever puzzles, but they are not fun to solve because they require backtracking (i.e., trial and error).Actually, to be precise, *I* have not fun in solving them because *I* am not able to solve them analytically...

Watch Your Language!

2011-02-20T18:34:00.000+11:00

Intelligent Design is an affirmation of a belief, not a scientific theory. To maintain that Nature is too complex to have evolved on its own and then deduce from such an arbitrary concept that a Creator/Designer must exist is an affirmation of faith, not a scientific statement.

It is important that magazines focussed on popularising Science maintain the highest standards of objectivity, not just in what they say but also in how they say it. Statements that purport to be scientific but are formulated with elements of superstition can have deleterious effects on the minds of the younger readers.

What prompted this tirade is the article by Lauren Monaghan titled “Grand Delusions” that appeared in Cosmos (self proclaimed “Australia’s #1 Science Magazine”) Issue 28 of Aug/Sep 2009. On page 46, it contained the following sentence:

“...we always have — and always will — want to believe in the fantastic. In fact, many scientists believe we are even programmed to do so.” (my italics)

In the same article was also the following statement made by an experimental psychologist:

“Humans are born with brains designed to make sense of the world, and that sometimes leads to beliefs that go beyond natural explanations.” (again, my italics)

Do you see what I mean? The words “programmed” and “designed” imply the existence of a Programmer and a Designer. They should have never appeared in a Science magazine.

Bah...

GLUT in C with Eclipse on the Mac

2011-02-06T14:20:00.002+11:00

For the past couple of months, for my book on Sudoku, I have been writing C programs with Eclipse running under Mac OS.

OpenGL (Open Graphics Library) is allegedly “the premier environment for developing portable, interactive 2D and 3D graphics applications”. I simply had to try it out. I quickly discovered that, beside the generic OpenGL libraries, I also needed GLUT (OpenGL Utility Toolkit, pronounced as in gluttony).

As it turned out, every Macintosh comes with everything you need (Windows systems don’t include GLUT). Therefore, the only thing I needed to do was to tell Eclipse where to find the libraries.

I hit at once a little problem: when you tell Eclipse to use a library (I’ll tell you in a moment how to do it), Eclipse actually looks for it after attaching to its name the string lib at the beginning and the extension .dylib at the end. So, for example, if you tell Eclipse to use the library named GLUT, Eclipse looks for libGLUT.dylib. The problem arises because on the Mac the GLUT library is simply named GLUT.

To fix it, you need to go to the GLUT directory:

cd /system/Library/Frameworks/GLUT.framework/

and then, as root, create the following soft link:

ln –s GLUT libGLUT.dylib

To tell Eclipse where to look for the openGL libraries, open the Project Properties dialogue and select Settings item of the MacOS X C Linker category, as shown in the following figure.

Then, as shown, add the following two entries to the Library search path (-L):

/System/Library/Frameworks/OpenGL.framework/Libraries

/System/Library/Frameworks/GLUT.framework

and the following three entries to the Libraries (-l):

GLU

GLUT

After telling Eclipse where the OpenGL/GLUT libraries are, before you can use them in your programs, you still need to tell Eclipse where to find the corresponding header files. For this, still within the same dialogue, select the Includes item of the GCC C Compiler category, as shown below.

When you are there, add the two following entries in the field Include paths (-l):

/System/Library/Frameworks/OpenGL.framework/Headers

/System/Library/Frameworks/GLUT.framework/Headers

That’s it. Now you can use the graphics package in C within Eclipse. Here is the small program I used to test the package, copied directly from Eclipse:

#include

#define SIDE 306

#define CELL SIDE/9

#define EDGE 8

char *arg;

int use_arg = 0;

void tick(void) {

glutPostRedisplay();

}

void output(int k, int j, char c) {

int x = EDGE + CELL * k + (CELL >> 1) - 5;

int y = EDGE + CELL * j + (CELL >> 1) + 7;

glRasterPos2f(x, y);

glutBitmapCharacter(GLUT_BITMAP_HELVETICA_18, c);

}

void display(void) {

glClear(GL_COLOR_BUFFER_BIT);

if (use_arg) {

for (int k = 0; k < 81; k++) {

int kR = k / 9;

int kC = k-kR*9;

if (arg[k] != '0') {

output(kR, kC, arg[k]);

}

else {

for (int k = 0; k < 9; k++) {

for (int j = 0; j < 9; j++) {

output(k, j, '0'+k);

}

for (int k = 0; k <= 9; k++) {

if (k % 3 == 0) {

glLineWidth (1.5);

}

else {

glLineWidth (0.5);

}

glBegin (GL_LINES);

glVertex2f (EDGE, EDGE+CELL*k);

glVertex2f (EDGE+SIDE, EDGE+CELL*k);

glEnd ();

glBegin (GL_LINES);

glVertex2f (EDGE+CELL*k, EDGE);

glVertex2f (EDGE+CELL*k, EDGE+SIDE);

glEnd ();

}

glutSwapBuffers();

}

void reshape(int w, int h) {

glViewport(0, 0, w, h);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(0, w, h, 0);

glMatrixMode(GL_MODELVIEW);

}

int main(int argc, char **argv) {

arg = argv[1];

glutInit(&argc, argv);

glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);

glutInitWindowSize(SIDE+EDGE+EDGE, SIDE+EDGE+EDGE);

use_arg = (argc > 0);

glutCreateWindow((argc > 1) ? argv[2] : "Sudoku");

glClearColor(1, 1, 1, 1);

glColor3f(0, 0, 0);

glutDisplayFunc(display);

glutReshapeFunc(reshape);

glutIdleFunc(tick);

glutMainLoop();

return EXIT_SUCCESS;

}

It accepts a string of 81 characters as the first argument and displays it within a Sudoku-like grid. Here is an example of what you get:

Obviously, as there are no events (e.g. user inputs) to trigger any change, this program is pretty dull. But it proves that you can use GLUT in the C programs you develop with Eclipse.

Multiculturalism

2011-01-28T20:05:00.000+11:00

In 1970, the German film director and producer Rosa von Praunheim made the film Die Bettwurst. The word Bettwurst, invented by Rosa, means bed sausage, and refers to somebody who never gets out of bed.

Anyhow, I saw the film decades ago, but I still remember the words of the following little song:

Die ganze Welt ist nur ein Arsch

und wir sind seine Fürze.

Ein Jeder stinkt nach seiner Art.

Das gibt dem Leben Würze.

Here is my best translation of it:

The whole world is just an arse

and we are its farts.

Each one stinks in its own way.

This gives spices to our lives.

Sudoku - A Handsome Samurai

2011-01-19T17:09:00.002+11:00

I have almost completed my book Sudoku Programming (if I have ever seen a plug...) about how to write C applications that can solve and generate Sudokus. As part of it, I have decided to explain how to generate Samurai Sudokus. I had noticed that they often have the shared boxes completely empty and wanted to do better than that. I am very happy with the result, and would like to share it with you. Here it is:

I can generate as many as I like and not necessarily fully symmetrical, even if I think that they are just beautiful. Each one of the five puzzles I used to ‘assemble’ the Samurai requires some non-trivial strategies like Y-wing, XY-chain, and X-wing. The presence of the intersections might/should reduce the overall difficulty of the puzzle, but I still expect it to be reasonably (whatever that means) difficult.

Obviously, I have got the solution, but you don’t expect me to give it to you, do you?

Fortran and Eclipse on the Mac - Addendum

2011-01-11T11:08:00.002+11:00

This is about updating Eclipse, PTP, and the Fortran compiler to their latest versions. Beth Tibbitts of the Eclipse Parallel Tools Platform (http://eclipse.org/ptp) told me how to do it via the Photran Information mailing list (photran[a t]eclipse.org).

Here is how she explained it to me:

Your description uses the original versions of Helios (and PTP, and Photran) instead of the SR1 release in September.

That URL should be

http://www.eclipse.org/downloads/packages/eclipse-ide-cc-developers/heliossr1

Or even better: Tell them to go to http://eclipse.org/downloads/ and click on "Eclipse IDE for C/C++ Developers" which will always get the latest version. (Now it's Helios SR1.)

Using your update site instructions *will* correctly install PTP and Photran at 4.0.3 and 6.0.3 versions.

Then if you do a Help > Check for Updates -- it will update things to the SR1 level.

In fact, PTP itself had some slight updates even since then.

Perhaps not critical, but handy to know how to do:

See http://wiki.eclipse.org/PTP/FAQ#update_ptp_specific

Your PTP should then be at 4.0.5 and Photran at 6.0.5 (your instructions show 4.0.0 and 6.0.0)

And here are some snapshots I took while I was following her instructions: