Kakuro solver considered too slow -- but now fixed. "They see me mowin'..."

Couldn't leave well enough alone, so I googled "hard kakuro" and clicked to an astonishingly difficult kakuro puzzle at http://www.bestkakuro.com/killer2.gif; it took my old solver something like 15 minutes on my desktop box. This seemed entirely too long, so I played with it, resulting in a speedup of better than 94:1 on said desktop box. Running the old vs. new Python programs on a G4 Powerbook gave a better than 100:1 speedup.

The secret? The old program would find all possible permutations of all possible combinations for each sum, then painstakingly remove all the impossible ones. It turns out that using a list comprehension, and removing in advance the permutations that are disallowed by just the first and last cells of the sum -- this one step -- gives almost an order of magnitude speedup. I suspect some of the savings is due to reduced demands on memory management.

Almost another order of magnitude can be gained by using the entire list of cells in the aforementioned pre-screening. It turns out that since the list of "possibles" is constant while we're screening out permutations, we can build a string like

"lambda vec: vec[0] in (1,2,3) and vec[1] in (1,2) and..."

then say mm=eval(that string), and then code the list comprehension as [x for x in permutes(...) if mm(x)]

I have to say Guido and the Python team were genius to give us list comprehensions and the "eval" function. That was a lot of fun, too! Oh -- I updated the website with the latest sources, as well as the steps from the old to new, for your code-reading pleasure. Enjoy!

3/29: took another 13-17% off the execution time!

What took 54:22 (yes, nearly an hour) on a powerbook G4 now takes under 23 seconds on the same box, roughly a 140:1 speedup. On a 2.6GHz Xeon 5150, the speedup was 5:54 down to under 5 seconds, better than 70:1. I really like Python.

Both daughters home!

Just around lunch time today, we were lounging around (I took the day off) and mentioned the seahorse exhibit at the Monterey Bay Aquarium.

That was not what I'd call a hard sale. "I haven't been there in a long time," the ex-teenager said wistfully. "I love spontaneous trips!" said the other. I grabbed dog food and we all headed off together, stopping at our neighborhood market to get some apples. And cash.

What a beautiful day! The teen-ager napped in the back seat for part of the drive. We parked in the garage at Foam and Prescott, and walked down to the beach. The sun was shining and the water was astonishingly blue. We took our shoes off and enjoyed the feel of the coarse sand. After looking at shells for a while we dried our feet, got our shoes back on, and went to the aquarium.

The aquarium is gorgeous, maybe even more so than I remember it. Seahorses are amazing creatures. I don't think I knew they were fishes. It's amazing how they move, using very thin fins. (These guys are not tunas.)

After 2–3 hours we're ready to look for dinner. We chose Sly McFly's, on Cannery Row at Prescott. Fish and chips, and clam chowder in a bread bowl -- not exactly health food but delicious and satisfying.

The drive home was uneventful. We talked some about college life, about some surprises and general thoughts as the ex-teenager is approaching graduation.

I'm a thankful man, to have both daughters home and to be able to enjoy this day with them and to hear their thoughts on life....

You socialist you

The oldest reference I can find (easily) to this essay is: http://newappeal.blogspot.com/2009/08/government-cant-do-anything-right.html; I'm going to tweak the first sentence before posting here:

"The Government can't do anything right"

This morning I was awakened by my alarm clock powered by electricity generated by the public power monopoly regulated by the U.S. Department of Energy.

I then took a shower in the clean water provided by a municipal water utility.

After that, I turned on the TV to one of the FCC-regulated channels to see what the National Weather Service of the National Oceanographic and Atmospheric Administration determined the weather was going to be like, using satellites designed, built, and launched by the National Aeronautics and Space Administration.

I watched this while eating my breakfast of U.S. Department of Agriculture-inspected food and taking the drugs which have been determined as safe by the U.S. Food and Drug Administration.

At the appropriate time, as regulated by the U.S. Congress and kept accurate by the National Institute of Standards and Technology and the U.S. Naval Observatory, I get into my National Highway Traffic Safety Administration-approved automobile and set out to work on the roads build by the local, state, and federal Departments of Transportation, possibly stopping to purchase additional fuel of a quality level determined by the Environmental Protection Agency, using legal tender issued by the Federal Reserve Bank.

On the way out the door I deposit any mail I have to be sent out via the U.S. Postal Service and drop the kids off at the public school.

After spending another day not being maimed or killed at work thanks to the workplace regulations imposed by the Department of Labor and the Occupational Safety and Health administration, enjoying another two meals which again do not kill me because of the USDA, I drive my NHTSA car back home on the DOT roads, to my house which has not burned down in my absence because of the state and local building codes and Fire Marshal's inspection, and which has not been plundered of all its valuables thanks to the local police department.

And then I log on to the internet -- which was developed by the Defense Advanced Research Projects Administration -- and post on Freerepublic.com and Fox News forums about how SOCIALISM in medicine is BAD because the government can't do anything right.

New Appeal to Reason
Politics from a democratic left perspective from the middle of the United States
Monday, August 10, 2009

The details aren't all quite correct (oh, and I think that's "Fire Marshall") but I certainly agree with the sentiment.

Discussing Jesus with Al Franken

In a sketch from "Lord Save Us From Your Followers", Al Franken describes his encounter with a zealous Jesus-follower. Mr. Franken didn't (and I suppose still doesn't) think Jesus is God, and his interlocutor said he was calling Jesus a liar.

Not knowing exactly what was said, I nevertheless can imagine someone being quite obnoxious about this issue. I don't even have to stretch very much because I've been that obnoxious myself in the past. But though I don't think my brother in Christ provided Mr. Franken with a winsome appeal to the facts, I nonetheless agree that Jesus really doesn't give us the option of thinking he's "just" a great teacher. He made it quite clear that he was claiming to be equal to God in a way that merely human beings like you and I are not.

Back to Mr. Franken's story: my brother in Christ apparently told him, "Jesus said, ‘When you look upon me you look upon the face of God.’ What do you make of that?"

Mr. Franken replied, "Well, maybe he was misquoted. Maybe he was saying that when you look upon any man you look upon the face of God." (These quotes are approximate, as I'm working from memory.) Nobody had a successful rejoinder to Mr. Franken, and I think this a shame.

It's a shame not because it would have been possible to "win" the argument -- nobody has ever come to hope in Christ because she or he "lost" an argument -- but because I think it important that we present our faith winningly and also intelligently. It doesn't really dishonor God if the world thinks Christians are silly ("We are fools for Christ" - 1 Corinthians 4:10, etc), but it doesn't honor him to present our faith as something we just made up.

As a matter of record, Jesus was not ambiguous at all in his claim to be special. Here's John's record of just one occasion:

"My sheep listen to my voice; I know them, and they follow me. I give them eternal life, and they shall never perish; no one can snatch them out of my hand. My Father, who has given them to me, is greater than all; no one can snatch them out of my Father's hand. I and the Father are one."

Again the Jews^[1] picked up stones to stone him, but Jesus said to them, "I have shown you many great miracles from the Father. For which of these do you stone me?"

"We are not stoning you for any of these," replied the Jews, "but for blasphemy, because you, a mere man, claim to be God."

John 10:27-33

1. ^ I should mention something here about John's use of the phrase "the Jews." It is a shock to some people, but Jesus grew up as a Jew; so were all the disciples. John himself was a Jew. What he means by "the Jews" is "the religious leaders." Really, John is really not anti-Semitic.)

Jesus is talking with religious leaders here, and they are quite clear about what he meant. Even if we don't have the exact words (this conversation most likely was in Aramaic, whereas the text is written in Greek), its import was unambiguous.

So Jesus really did claim to be equal to God, which leaves us, as Lewis said, with three possibilities:

1. He was some sort of nut-case, rather like someone who claims to be a poached egg;
2. He was a liar (or worse) -- claiming to be God when he wasn't;
3. He really was who he claimed to be.

Jesus doesn't leave us the option of thinking of him as a merely human philosopher or teacher; if he was merely human then #1 and #2 above are our only options. This line of thought won't, of course, convince anyone to follow Jesus, but I hope it can help people to be willing to take another look.

Maybe not the last kakuro post...

I discovered last night that my solver didn't work for puzzles like this one by Vegard Hanssen. So it took rather more thinking, and a little more coding (which Python makes easy) to get that one solved.

I've put the new one in place of the old one -- all visible at http://cpark.users.sonic.net/kakuro-python/. Besides the prettier HTML, which I got from Vegard Hanssen's site (see the above puzzle too), the new "k2.py" program has the following changes vs "k2-Mar_19_2255.py".

1. Trivially, the old code had "HTML=True" near the top and the printout routine would output HTML if the variable was true. Yup...
2. Almost as trivially (I don't think it made any difference), handle the process of setting a cell's determined value vs adjusting the content of its "possibles" list uniformly. There was one place we weren't doing that.
3. Once we start dealing with permutations (the 2nd bullet in this earlier posting), find undecided cells that have only two possible values. For each such cell, try out first one value, then the other, to see if it leads to a contradiction. If it does lead to an impossibility, remove that value from the list of "possibles" and thereby decide the value of that cell. For example, in the aforementioned very hard puzzle #345943, doing the elementary steps brought us to this point:

   	A	B	C	D	E	F	G	H
   0						17	22
   1				6	10 39
   2			19 38					3
   3		11				4	3	1
   4		20 16		3		6 23	4	2
   5	15			18
   6	12			21 4
   7		24
   8		8

   As you can see, the solver didn't get too far with this one; filled in 5 but left 27 cells blank. The new logic does this for example with cell 7D:
   • 7D can be either 1 or 3 (see http://cpark.users.sonic.net/kakuro-python/veryhard.html for a complete list). But if 7D=1 then
     • 8D=3 because of 6D_down, and
     • 8C=5 due to 8B_across.
     • Of the combinations allowed by 2C_down, there's only one allowing 8C=5: (6,9,8,3,7,5), which dictates for example that 7C=7.
     • This is a problem because 7B_across doesn't have any permutations starting (7,1,...).
   • Hence 7D cannot be 1.
   • Therefore 7D=3, 8D=1, 8C=7, etc.
   This same logic, combined with the permutation-checking code described earlier, handles this puzzle as well as puzzle #18999, which takes about 7 CPU-seconds (feels like forever) on this 1GHz Athlon3000+ box (bogomips 2009) running 32-bit 2.6.28-18-generic (Ubuntu 9.04) and Python 2.6.2

So unless I find any more kakuros that this solver can't handle, this will really be the last kakuro post.

Hugh Gallagher's college essay... and a novel

Going in backwards order, the debut novel of this American humorist was "Teeth"; you can see more about this 1999 book on amazon.com's description. I read an excerpt, which makes me want to read the rest.

But I heard of him because of an essay he wrote, which appeared in Rob Bell's Drops Like Stars (apparently now available in paperback). According to Wikipedia, it was written for a 1989 writing contest and later submitted to colleges. The full version is at http://www-users.cs.york.ac.uk/~susan/joke/essay.htm but here are a few lines from it:

I am a dynamic figure, often seen scaling walls and crushing ice. I have been known to remodel train stations on my lunch breaks, making them more efficient in the area of heat retention.
...

I woo women with my sensuous and godlike trombone playing, I can pilot bicycles up severe inclines with unflagging speed, and I cook Thirty-Minute Brownies in twenty minutes. I am an expert in stucco, a veteran in love, and an outlaw in Peru.
...

There's lots more. The essay also appears on http://saunderslog.com/2005/11/21/hugh-gallagher-man-of-many-talents/ along with 19 (currently) responses.

shrimp + garlic + asparagus = yum! in half an hour

No kidding, you can do this in less than 30 minutes. Here's the plan:

1. Oh, I forgot to tell you, you have to have on hand
   • maybe ½–¾ pound of shrimp, and
   • some fresh asparagus. A dozen spears wouldn't be too many.
2. Start the rice. Or a pot of water for pasta.
3. Put
   • 2 T olive oil
   into a skillet on medium-low heat while you shell and de-vein
   • ½–¾ pound of shrimp
   Add shrimp to the pan. After a minute or so, add:
   • 2 T vermouth or white wine

     I'm no gourmet, but here's what I think: white wine seems to me to bring out the flavor of seafood, whereas red seems to moderate it. I like this dish to be shrimpy, which is why I like the white.

   • a smashed clove of garlic
   • 2t or 1T of lemon juice
   • salt and pepper if you like
   • parsley if you have some
   Cover it and...
4. Take out and wash
   • fresh asparagus.
   I grabbed ten; a dozen would not be too many. (Could there be too many?) Now check on the shrimp. Flip them over maybe, cover, and let them sit for another minute.

   Pull the shrimp out and put them on a warm plate. Toss the asparagus spears into your skillet with

   • ¼ cup or so of water,
   and cover again. Flip them after a minute or so and remove them when tender enough (check with a fork).
5. Somewhere in there the rice was probably done, or the water boiled for your pasta.

That's it! Tasty, healthy (if you don't like "healthy," use 2-3T butter instead of olive oil) and easy. You can use brown rice or whole-grain pasta if you want to be healthier.