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...
Sunday, December 25, 2011
DNA
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!
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!
Tuesday, December 20, 2011
Lacing Shoes
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:
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?
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
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...
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...
Monday, December 19, 2011
A Puzzling Year
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...
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.
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...
Thursday, December 8, 2011
Double CalcuDoku #2
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.
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.
Friday, December 2, 2011
Double CalcuDoku
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?
Subscribe to:
Posts (Atom)