Monthly Archives: June 2017

Computer cipher solving – Lesson 10: Genetic algorithms

I’ve discussed hill-climbing and its variants like simulated annealing in earlier lessons. They work well for most cipher types, at least most American Cryptogram Association (ACA) types.However, they don’t always work so well on certain types. For me Myszkowskis fall in that category. Thankfully, I learned about another technique that works better for Mysz ciphers: the genetic algorithm. It tends to improve its solutions more slowly than hill-climbing, but in the end it is usually more reliable.

So how does it work? Just like its name implies. You create a large population and continue to mate the individual members and their offspring until one of the children is the solution. Sounds simple, and from a programming standpoint, it is.

Let’s take the Myszkowski for an example. First, to create the population  you need to know, or assume, a key length. I’ll use 10 for the example. A Myszkowski uses a numeric key that has at least one doubled number (otherwise it would be a columnar, not a Mysz). That means the 10 columns can be keyed by any digit from 1 to 9. I use a data base of 100,000 keys. This may be larger or smaller than the ideal number, but it seems to work. I populate the database with 100,000 random 10-digit numbers using only the digits 1-9. If you want to get fancy and take advantage of Bayes’s Theorem you could weigh the distribution more heavily toward the lower end of that number range. I don’t bother with that, as there is a correcting step later in the algorithm.

Next you start the repeating loop by choosing two of these keys at random. One is arbitrarily chosen as the left (male) parent, and the other right (female) parent. Decipher the ciphertext with each parent, score the output for how well it resembles your target language, and keep track of the scores. Then choose a spot near the middle of of the key length. For key length 10, it should be a number from 4 through 7, say. I’ll use 5 for the example. Take the 5 left key digits of the male and the 5 rightmost digits of the female to make a new, 10-digit key. Decipher with that and score the output. If it scores worse than either parent, discard it and go back to the beginning of the loop to choose two new parents. If it outscores both parents, replace both with the child. If it only outscores one, replace that one with the child, but leave the other parent. Whenever a new best decryption results, display that or save it to a file. Repeat in an endless loop until you’re satisfied with the solution.

That’s pretty much all there is.  I have been told that every so often, just like in real life biology, you need to introduce a random variation – a mutation. My own very limited experiments have not proven this to be true, and in fact it is counterproductive. Perhaps it is more important when the key is longer. The theory is that your original population only contained 100,000 individuals. Yet there are 9^10 possible 10-digit Mysz keys, or almost 3.5 billion. The correct key has only about 1 chance in 3500 of being in that population at first (although there are usually quite a few equivalent keys using other digits). It may not be possible to produce the exact correct key by mixing parents’ genes if none of the parents have the necessary components. So at intervals when you are moving through the loop, in addition to mixing the two parents’ digits, make a random change of one or two digits and test that, keeping it if it improves the score. In effect this step is a form of hill-climbing, but since it is only occasional, not the primary altering step of each cycle, this is a fundamentally different algorithm.  Let me know if you have done any testing and can provide good data on optimization.

If the Mysz period is longer than 11 you have to use letters instead of digits for the keys. For other cipher types, like the Columnar, this method can be used, but you would have to insert an extra step to convert the child keys because there could be duplicate digits or letters. Obviously there are various adaptations that would be necessary for other cipher types, and it would not be suitable for many types at all.

Author rank

Those of you who are self-published or are thinking of self-publishing may find this author rank chart interesting. It shows how well (or badly) various events affect sales. This six months chart shows the sales performance of all my books combined (7 Cliff Knowles mysteries). The comparison is to all Kindle ebooks in the Mysteries and Thrillers categories, both self-published and major publishing house titles. I don’t know how many authors there are in that category, but I know it’s over 100,000.  It’s possible to break down the mystery category farther into Police Procedurals, etc., and of course my rank gets higher in the smaller categories because there are fewer books, but the overall trend is about the same.

I have marked three points where sales spiked. The labels are pretty self-explanatory. The April spike occurred when I lowered the price on all my books to the minimum $2.99 and posted about it on my blog, on various Facebook groups, etc. That spike didn’t last long. The May spike came when I made Cached Out free for a weekend. Amazon only allows that for a limited number of days and only if the book is enrolled in a program they have where it’s exclusive to Amazon (i.e. no iTunes, Barnes & Noble, etc.) I did publicize that through various commercial sites (only free ones this time) as well as the usual Facebook groups and my own mailing list. Surprisingly, that spike has lasted longer. It seems counterintuitive that making a book free increases its sales, but it does. It makes sense about the other books in the series. I’ve noticed that you can’t do that too often, though. Although sales have not stayed all that high after the free promotion, the borrowing of my books through Kindle Unlimited and Amazon Prime has remained quite high since the promotion, which helps to keep my rank up.

Dragon Teeth by Michael Crichton

Dragon TeethDragon Teeth by Michael Crichton
My rating: 5 of 5 stars

How refreshing to read a thriller without the excessive gore, foul language, and thinly disguised porn. Crichton is in top form in this one, a story based on real-life adventures into the Badlands of Montana and the Dakotas by two paleontologists in the late 1800s. Marsh and Cope were historical figures who made great fossil discoveries, including the first brontosaurus, but whose lives were marred by their vicious competition and slanderous attacks on each other.

The protagonist in this tale is William Johnson, a fictitious student at Yale, who begins as a dissolute layabout of questionable character. He makes an unwise bet with a rival student and then must follow through by accompanying Marsh on his summer expedition west. Needless to say, the trip is filled with excitement and surprises. Crichton is at his best when he combines history, science, and good story-telling. I thoroughly enjoyed this book.

View all my reviews

The Dark Room by Jonathan Moore.

The Dark RoomThe Dark Room by Jonathan Moore
My rating: 1 of 5 stars

I tried mightily to get into this because I considered Moore’s The Poison Artist to be a five-star read, but it wasn’t worth the effort. It made no sense. As ex-FBI who worked right there in federal plaza where this takes place I’m perhaps overly sensitive to jurisdictional issues, but this one was egregious. A San Francisco police detective is interrupted in a night investigation in Monterey to be flown by helicopter in the middle of the night to SF City Hall over a supposed blackmail letter that had come to the mayor. C’mon, really? The letter arrives during business hours and they wait until the middle of the night and then fly this guy in a helicopter, which lands in front of City Hall in order to be discreet?

Then it seems the FBI is in charge of the case. Why? The letter suggests that four photographs will be made public. They show a woman in apparent distress and she is handcuffed to a bed in one of them. But there is no crime described in the letter or shown in the photos. So far as the photos show, it’s a posed actress. The mayor isn’t in the photos and claims not to know anything about her or the photos. So it’s not even blackmail since there is no threat to reveal a crime. The mayor would have to admit some involvement with a crime or something embarrassing that could ruin him for that to be a crime. Not only that, but it’s only FBI jurisdiction if the crime that will be revealed is a federal crime. If the mayor admitted that he had transported the woman interstate during a kidnapping, or sent child porn in the U.S. mail, for example, and explained that he believed this letter was threatening to reveal that, then you would have FBI jurisdiction, but the FBI would be more interested in the mayor’s crimes than in the blackmail. Use of the mail to send a threat is a federal violation, but that’s Postal Inspectors, not FBI, jurisdiction and this isn’t really a threat. Publicizing a picture of a handcuffed woman isn’t a crime or harmful to the mayor, at least that’s not indicated at this point in the story. I see similar pictures all the time on book covers, movie trailers, and the like. No crime there.

Then the FBI agent tells the detective that identifying the woman is a local matter. What?! If there were FBI jurisdiction, they would take over the whole thing, I guarantee you that. Not only that, but identifying the woman is probably the one thing the FBI would be better at than the SFPD, so that makes no sense. Meanwhile the case the detective was working on when he was yanked off it takes a bizarre and unlikely turn. The whole plot became farcical, so I gave up at that point. Maybe zombies will show up next. Life is too short to waste on stuff like this.

View all my reviews

The Skeleton Crew by Deborah Halber

The Skeleton Crew: How Amateur Sleuths Are Solving America’s Coldest CasesThe Skeleton Crew: How Amateur Sleuths Are Solving America’s Coldest Cases by Deborah Halber
My rating: 4 of 5 stars

The subtitle of this book is accurate after a fashion, but a bit misleading. I expected a book about forensic experts, computer hackers, and similar civilians who consult voluntarily for police to solve crimes and bring about arrests and convictions. There is almost none of that. Rather, this book focuses on those people who try to match unidentified human remains with missing persons. It is a crew that quite literally is obsessed with skeletons and partially decomposed bodies. It sounds rather ghoulish and at times it reads that way, but it would be a mistake to dismiss the book for that reason.

The emergence of the Internet into every home allowed the public suddenly to become involved in investigating crimes. There arose a small cadre of individuals who became completely immersed in cases of missing persons, or of unidentified remains. The people with this intense interest were often friends or relatives of the missing person, or someone who came upon the remains. In some cases it was a retired detective or police chief who couldn’t stop thinking about the case they couldn’t crack. Several organizations arose consisting at first of amateurish websites, often competing. These frequently drew wackos and indeed, the police often called these civilians Doe nuts. The website owners or adherents would trash or troll other sites or claim that someone stole “their” case. The unidentified remains also acquired colorful names in many cases: The Lady of the Dunes, Tent Girl, Old Joe.

Make no mistake. Despite the creepiness of the obsession, these amateurs have indeed in many cases helped identify remains by matching them with missing persons. The word closure seems trite, but it is real for those heartbroken about a missing child and whose decades-long suffering is ended. For many, giving the relative a proper burial and real headstone is enough to bring peace. Many of the web sleuths, as they came to be known, have genuine skills appreciated by enlightened detectives. One woman had incredible facial recognition abilities. Others often memorize astounding amounts of trivia about particular cases.

Since this is a book review, not a critique of those who pursue this cause, I’ll stop there and simply say the book is fascinating. I kept wanting to get back to it to find out what happened next. If you have a queasy stomach about such things perhaps you should skip this one, as the descriptions are sometimes graphic, but there are no gory pictures.

This is not to say the book was without flaws. The author and editor made some odd and irritating stylistic choices. The clothing, home, and physical description is detailed ad nauseam for every single person the author met, no matter how irrelevant. Everyone reminded her of some actor or celebrity. Every story is chopped up into non-sequential pieces. A chapter may begin describing how person A finds body B. Then it turns to A’s personal biography, then to the police detective or coroner C who took over the investigation. Next it jumps to Person D, the web sleuth who became obsessed with the case, which may be years after the discovery. Then it jumps to B again and tells the story of B’s life before he or she went missing, and all the people associated with B – childhood, family, lovers, and so on decades earlier. Then back to D and how D got interested in web sleuthing, which started with a totally unrelated case of person E. That story is told, then it goes back to A, then B then D then C, and so on for four or five iterations. I wanted to scream at the the author to just tell one story straight through for once, pleeease. Despite these anomalies, I enjoyed the book and appreciate the macabre draw of this sort of web sleuthing and of the good work that has been accomplished. I’m pleased to say that the federal government eventually became involved and the whole endeavor is now largely professionalized, but still uses volunteer web sleuths to good effect. Need a hobby? If you’re stuck in a single-wide in East Podunk with nothing but a PC to entertain you, you too could find this hobby rewarding and you might just help police solve a murder case or help a family put their child to rest after many years. Visit the Doe Network.

View all my reviews

Free crosswords!

Do you enjoy free crosswords? I just posted two more on my crosswords page. It’s been quite a while, but I hope to do more in the coming days. You can download a PDF version, too, if you prefer to print them out and work on paper.

Click above link for main crosswords page or click image to solve this one

 

Ratagrams revisited

Last fall I proposed a new type of word game I called Ratagrams, a particular type of anagram. The rules are here. Here are some more, ones I hope are more challenging.

  1. Hereafter, out room, whore!
  2. Staffed peg convicts Viennese poets’ theater
  3. Haven seize finer festivity

Two of the three contain proper nouns (names). Good luck.

Edit to clarify: per Rule 5, the original punctuation has been removed, so the punctuation shown may be misleading. I’ve modified Rule 4 to allow proper names this time because at least one popular anagram site is so comprehensive (over 15 million phrases and quotes) that I’ve had a hard time finding ones that cannot be solved by pasting in there. Numbers 1 and 3 are the ones with names in them. Here’s an additional hint: The last one is a product slogan and the second one became a well-known quote only this year.

P.S. Please don’t post answers here or on social media, but do feel free to let me know if you’ve solved them. If I don’t get any solutions in three weeks, I’ll post the answers.

Edit 6/26/17: I have not had any valid solutions submitted, so I have put the answers in the comments. Scroll down to see them.

F-bomb

I was running at the park today and overheard a young woman use the F-bomb while talking to her friend. This is the first time in years that I’ve heard it in real life, at least as far as I can remember, other than people who repeat offensive language they heard in movies or TV as a complaint about it. I hear or see it all the time on TV, in movies, and books, but not from actual people. I still don’t know why writers do that. The purpose of using offensive language is to offend. That’s tautologically true. So why do writers intend to offend their customer base? I don’t get it. It’s so far removed from reality it’s like having all your characters float six inches off the ground instead of walking. What’s the point? Maybe I live in a relatively insulated slice of society, but I don’t think so. Most decent people just don’t talk like that.