Sunday, December 17, 2017

Life imitates code

Sometimes life imitates art, as they say; this is a case where life imitates code.

It started a half-century ago at least (the story, not the code). Way back when I was in elementary school, Dad gave me the idea of making “Soma cube”s out of wood. I don’t know how many of these I made back in grade school, but a few years ago I started doing it again.

Then about this time last year, I wondered what it would be like to write a program to solve the puzzle. This page has links to the source code for a solver written in C++; I couldn’t run it because I don’t do Windows. I soon decided to keep the data representation but otherwise write a new solver in Python.

The solver places the “T” piece in the only way possible (as explained here in the wikipedia article), then places the “L” piece in one of 28 unique positions. Here “unique” means never having to say “that’s a reflection of a previously-described solution”; ask me for details or see the code if you’re hungry for details. Anyway, the other pieces—V, Z, A, B, P (wikipedia’s nomenclature)— get placed after T and L.

Consulting a recent output, I discovered that the “V” has 103 possible placements (by “possible” I mean given the position of “T”), whereas the “P” has only 42. For some reason I had the intuition that placing the “P” first would use less CPU time.

I ended up coding a sort step so that the solver would place the “hardest” piece (the “P”) first, and then the pieces with increasing numbers of possible placements, and finally the “V” last. How much of a difference does it make? I don’t recall, but I’ll just try it now on a 2.4GHz Intel Q6600:

$ time ./soma2-unsorted.py > s2-unsorted.out

real 3m46.587s
user 3m46.564s
sys 0m0.004s
$ time ./soma2.py > s2-sorted.out

real 0m38.732s
user 0m38.720s
sys 0m0.008s
$ 
That’s 226.6 seconds vs. 38.7 seconds, a nontrivial difference.

Fast-forward to earlier this month. I was thinking again about wooden puzzles and wikipedia told me about the “diabolical cube”, with only 13 solutions, and it’s here that life imitates code.

Because of my experience with the Soma cube solver, I immediately started by placing the “hard”est-to-place pieces first, and then try to place the easier ones. By proceeding that way, I figured out the first several solutions. But to get the rest of them, I modified the Soma cube solver… after a few tries it worked, completing in about a second. Here’s an actual run on the same box as above:

$ time ./diacube.py  > d.out

real 0m0.978s
user 0m0.976s
sys 0m0.000s
$
The 7-cube piece must be placed parallel to a face of the desired 3x3 cube; it can be
  • actually on a face—in this case, the rest of the pieces determine a unique solution; or
  • between two faces—in this case, it’s possible to create solutions that are reflections of each other. I could have avoided this by coding for placement of the second piece (I would have done this to the 6-cube piece) but instead opted to write a little code to keep only one solution out of a pair of reflections.
There wouldn’t be many of these, because my program produced 17 solutions, whereas Wikipedia told me there were only 13. So it computed only 4 redundant solutions, and it would take longer to think about unique placements than it would be to write the code to find reflections.

Or so I thought. I goofed up the code that looked for reflections, because I had forgotten that my solutions contained references to each polycube’s placement. In computing a reflection, I trashed the original polycube. A rookie error.

Anyway, if you ever get your hands on a “Diabolical cube,” it’ll be a lot easier to solve if you place the 7-cube piece and the 6-cube piece and the 5-cube piece first.

For reference, I’ll give you the 13 solutions, after some blank space if you want to avoid the spoiler :)

solution 1:
6 6 6
4 4 2
4 4 2
7 6 6
7 7 7
7 7 7
3 3 6
5 3 5
5 5 5
solution 2:
6 6 6
4 4 2
4 4 2
7 6 6
7 7 7
7 7 7
5 5 6
5 3 3
5 5 3
solution 3:
6 6 6
2 4 4
2 4 4
7 6 6
7 7 7
7 7 7
3 3 6
5 3 5
5 5 5
solution 4:
6 6 6
2 4 4
2 4 4
7 6 6
7 7 7
7 7 7
5 5 6
5 3 3
5 5 3
solution 5:
6 5 5
6 6 3
6 6 6
4 4 5
4 4 3
2 2 3
7 5 5
7 7 7
7 7 7
solution 6:
6 5 5
6 6 3
6 6 6
2 2 5
4 4 3
4 4 3
7 5 5
7 7 7
7 7 7
solution 7:
4 6 2
4 6 2
5 6 5
4 6 3
4 6 3
5 5 5
7 6 3
7 7 7
7 7 7
solution 8:
4 6 3
4 6 3
5 6 5
4 6 2
4 6 3
5 5 5
7 6 2
7 7 7
7 7 7
solution 9:
4 5 5
4 3 2
3 3 2
4 5 6
4 6 6
6 6 6
7 5 5
7 7 7
7 7 7
solution 10:
4 5 5
4 3 3
2 2 3
4 5 6
4 6 6
6 6 6
7 5 5
7 7 7
7 7 7
solution 11:
3 5 5
4 4 2
4 4 2
3 5 6
3 6 6
6 6 6
7 5 5
7 7 7
7 7 7
solution 12:
2 5 5
3 4 4
3 4 4
2 5 6
3 6 6
6 6 6
7 5 5
7 7 7
7 7 7
solution 13:
3 5 5
2 4 4
2 4 4
3 5 6
3 6 6
6 6 6
7 5 5
7 7 7
7 7 7

Sunday, December 10, 2017

A few thoughts from when my home was invaded by adolescents

That was a long time ago, but I'm thinking now about a couple of specific things we heard at the girls’ school in those days.

One was a seminar titled something like “When an Adolescent Invades Your Home”—I mentioned it in this post (written when both girls were in college). The presenter said that for quite a few years, children live largely unconsciously, with the lights off (he turned off the classroom lights to illustrate). Then, he said, a wonderful thing starts to happen: the lights come on (he flipped the switch to on) for a while (he turned the lights off). He didn't play with the switch much longer, but we got the idea.

This rang true, as I remembered doing really stupid things when I was younger, and yes I do feel very fortunate to be alive. Even today, the lights aren’t on for me all the time… but enough about me :). The point, though, is that for junior high kids (and even high school kids), the lights aren’t always on.

Another thing from that seminar iirc is that the onset of puberty has been happening earlier and earlier in the United States. One guess is that it's related to the hormones we feed to livestock to get them to mature faster. Anyway, the lights aren’t coming on necessarily sooner, but the hormones are raging earlier. So it’s more challenging now than it was a half-century ago.

The other thing that stuck in my mind was something their junior-high school Principal said in a graduation speech (probably in 2005). As parents, we have many roles with our kids. We supervise, guide, teach them, coach them, and so on. But what stuck in my mind was his comment that from here on out it’s mostly cheerleading; by now their habits are largely already set. From here on out (this was 8th grade graduation), we are not going to change their minds about many things, or get them to develop or drop many habits.

In other words, the time for most (key word, that: most) of that has already passed. Which is actually kind of scary, considering that the lights are still off a fair amount of the time and that their hormones are probably raging more than ours were at their age.

But then nobody said it would be easy.