# Tiling tilted tori

November 15th, 2016 by munizao | Print this post

A friend of mine recently complained about not being able to tile anything nice with the full set of polyominoes of size 1 though 5. (No, I didn’t make that up! I have weird friends. Who are not made up.) The area of these pieces is 89, which is prime. So our usual tactic of making a rectangle using divisors of the area won’t work.

But there is in fact something highly symmetrical that these pieces can tile. And its existence follows from the fact that while 89 may not be composite, it is the sum of two squares. 89 = 25 + 64 = 52 + 82.

Taking the sum of two squares may remind you of the Pythagorean Theorem, and that is exactly where I was headed. Make a right triangle where the legs have length 5 and 8, and the hypotenuse will have a length of sqrt(89). And then, naturally, if you make a square out of four sides with that length, it will have an area of 89:

So I have something that indeed has the desired area, but you might complain that having sides that slice obliquely to the square grid makes it entirely unsuitable for tiling with a set of polyominoes. But suppose we stitched the pairs of opposite sides together. That would turn the figure into a torus, which “unwraps” into a repeated, plane-filling pattern:

Which we can tile! If fact, tori are generally relatively easy to tile because they have no edges, and the edge is typically the hardest part of a pattern to tile. Having small pieces in the mix, as we do here, also tends to make tiling easier. So for a challenge, we could try something harder.

Problem #44:

Find a a tiling of the torus above with the 1–5-ominoes where none of the pieces of size 4 or smaller are adjacent to each other. Touching at corners is okay, but if you can find a solution without that, that’s even better. (Weird, it’s been three years since I’ve posed a numbered problem on this blog.)

This problem runs into a wall in my current setup for solving polyform tiling problems. I typically add ugly hacks to my copy of David Googer’s Polyform Puzzler. It’s reasonably handy because it’s open source and written in my language of choice, Python. But it doesn’t include a hook for pruning the search tree when you come to a configuration that doesn’t meet a desired condition. For problems with a small enough search space this doesn’t matter; you can just filter finished solutions as long as the time needed to run a complete search is reasonable. But here the high tilability is actually a curse: the solver starts in an area of the search space where the adjacency condition isn’t met, and because the pieces are so numerous and so tilable, it can stay there for an extremely long time before it decides to change out any of the tiles placed early on. (There are technical reasons why hacking in the hook I would need appears to be difficult, but I won’t get into those here.)

Coincidentally, the area of the 1–4-ominoes, 29, is also a sum of squares:

Any parallelogram can be used as the fundamental domain of a torus. Rectangle and rhombus shaped fundamental domains can have just as much symmetry as a tilted square. (Because the square is tilted, flipping it over isn’t a valid symmetry action, though rotating it still is.) But the tilted square tori still strike me as particularly pleasing and unexpected patterns for tiling.

# Faux Shu Follies

June 18th, 2016 by munizao | Print this post

The Lo Shu, or 3×3 magic square, was discovered in China in antiquity. It is the only way, (up to symmetry) to place the numbers 1 through 9 in a 3×3 grid such that the numbers in each row, column, and main diagonal add up to the same number (or magic sum). This fact seems to be universally known among recreational mathematicians. So when I had the chance to meet a number of them this spring at the fabulous 12th Gathering for Gardner conference, I told them that I knew a different way to do it. When they pronounced me mad, or a liar, I showed them one of these:

Mathematics is full of counterexamples that result when the simple way of understanding a conjecture is not exactly what the conjecture literally says, so this kind of cheating is totes legit.

If the fact of the uniqueness of the Lo Shu is new to you, a quick proof might be in order. First, let’s enumerate all of the sets of three numbers between 1 and 9 that sum to 15: {1, 5, 9}, {1, 6, 8}, {2, 4, 9}, {2, 5, 8}, {2, 6, 7}, {3, 4, 8}, {3, 5, 7}, {4, 5, 6}. There are eight sets, so we’ll need all of them to fill the eight lines in the magic square. The number 5 appears four times, the other odd numbers appear twice, and the even numbers appear three times. Therefore the center square, being part of four lines, must be 5, the corner squares, being part of three lines, must be the evens, and the side squares, being part of two lines, must be the other odds. Choose any corner, and put a 2 in it. That forces 8 into the opposite corner. Choose one the remaining corners, and put a 4 in it. After that, the rest of the numbers are forced. No matter what corners you choose, the result can be rotated or flipped to get the square formed by choosing any different pair of corners. Q. E. D.

Well, wait, you say, what if the magic sum isn’t 15? Quite right, 14 and 16 also both have eight sets of numbers between 1 and 9 that sum to them, so our proof is not done. I will leave it as an exercise to the reader to show that they cannot be used to form a 3×3 magic square.

And then, once the reader is satisfied, I’ll say: there is a way to place the numbers 1 through 9 in a 3×3 grid, with exactly one number in each cell, (you didn’t think I’d try the same shenanigans twice?) so that they occupy eight lines that each connect exactly three numbers that sum to 14. And having followed me this far, you are now enough of a recreational mathematician to be able to call me mad, or a liar. But you might want to have a look at this before you wager money on it:

This result was adapted from one discovered by Lee Sallows, which is described in his book, Geometric Magic Squares.

Well, clearly the problem here is that you’re allowing me to draw my own graphics. If you forced me to use physical number tiles as in the first image, I couldn’t get up to any fancy tricks. So if I told you that I could arrange those exact same nine number tiles in a block of three rows of three tiles each, and make it so that for every line that passes through the center of three tiles that form a connected group, the sum of those tiles is 14, I would have to be mad.

Mad as a loon.

# The Happiest and Saddest Tilings

June 15th, 2016 by munizao | Print this post

(Tagging under “A Polyformist’s Toolkit”, as I feel that series ought to have an entry on coloring, and this more or less says what I have to say about that.)

At Gathering for Gardner 11 in 2014, I gave a talk about crossed stick puzzles. It was the obvious thing to talk about, since I had been making a lot of interesting discoveries in that area. Unfortunately there was too much good stuff, and I couldn’t bear to trim very much of it out, so I made the classic mistake of going over on time and having to rush the last slides. (G4G talks are generally limited to 6 minutes.) When I looking for a subject for this year’s talk, there was nothing I felt an urgent desire to talk about. This would be the 12th Gathering for Gardner, and there is a tradition that using the number of the current Gathering, either in your talk or your exchange gift, is worth a few style points. Since I’m a polyformist, and Gardner famously popularized the twelve pentominoes, revisiting some of my pentomino coloring material seemed reasonable.

Finding interesting map colorings is a nice puzzle that we can layer on top of a tiling problem. A famous theorem states that all planar maps can be colored with four colors so no two regions of the same color touch. Since this can always be done, and fairly easily for small maps like pentomino tilings, we’ll want some properties of colorings that are more of a challenge to find. I know of three good ones:

1. Three-colorability. Sometimes we only need three colors rather than four. For sufficiently contrived sets of tiles we might only need two, but for typical problems that won’t work.
2. Strict coloring. For most purposes, (like the Four Color Theorem) we allow regions of the same color to touch at a vertex. If we do not allow same colored regions to touch at a vertex, we call the legal colorings strict. Notice that a 3-coloring of polyominoes is strict if and only if it contains no “crossroads”, i.e. corners where four pieces meet.
3. Color balance. If the number of regions of each color is equal, a coloring may be considered balanced. Conveniently, 3 and 4 are both divisors of 12, so we can have balanced 3-colorings and 4-colorings of pentomino tilings.

The above information would make up the introduction to my talk. It would also, suitably unpacked and with examples, take up most of the alloted time. That left little enough room to show off nifty discoveries. So whatever nifty discoveries I did show would serve the talk best if they could illustrate the above concepts without adding too many new ones. One that stood out was this simultaneous 3- and 4-coloring with a complete set of color combinations, discovered by Günter Stertenbrink in 2001 in response to a query I made on the Polyforms list:

This is the unique pentomino tiling of a 6×10 rectangle with this property where the colorings are strict. I used it to illustrate 3- vs. 4-coloring by showing the component colorings first, before showing how they combine. To my astonishment, the audience at G4G12 applauded the slide with the combined colorings. I mean I think it’s pretty cool, but I consider it rather old material.

I still wanted one more nifty thing to show off, and while my page on pentomino colorings had several more nifty things, none of them hewed close to the introductory material, and the clever problem involving overlapping colored tilings that I was looking at didn’t seem very promising. Setting that aside, I wrote some code to get counts of the tilings of the 6×10 rectangle with various types of colorings. That gave me the following table:

 Total Balanced 4-colorable, non-strict 2339 2338 4-colorable, strict 2339 2320 3-colorable, non-strict 1022 697 3-colorable, strict 94 53

What stood out to me was the 2338 tilings with balanced colorings. Since there are 2339 tilings in total, that meant that there was exactly one tiling with no balanced coloring:

Notice that the F pentomino on the left borders eight of the other pentominoes, and the remaining three border each other, so there can be at most two pentominoes with the color chosen for the F, and no balanced coloring can exist. A unique saddest tiling balancing out the unique happiest tiling was exactly what my talk needed. Now it had symmetry, and a cohesive shape. Having important examples all using the 6×10 rectangle removed the extraneous consideration of what different tiling problems were out there, and helped to narrow the focus to just the coloring problem. Anyway, I don’t want to go on any more about how awesome of a talk it was, (especially because video of it may eventually go up on the internet, which would show how non-awesome my delivery was) but it was my first G4G talk that I was actually proud of. The slides for the talk are here.

One thing I’m curious about that I didn’t mention in the talk: has anyone else found the saddest tiling before me? Looking through old Polyform list emails, I found that Mr. Stertenbrink enumerated the 3-colorable tilings of various types (essentially, the bottom half of the table above) but not the 4-colorable tilings. From the perspective of looking for the “best” colorings, it makes sense to focus on the 3-colorable tilings, but it meant missing an interesting “worst” coloring.

# Varying lengths in crossed stick puzzles

April 9th, 2016 by munizao | Print this post

So far, the crossed stick puzzles that I’ve looked at all have pieces of the same length, with slots in congruent positions. The puzzle aspect comes from the need to match slots by depth and direction. However, there is another possibility: can we come up with a puzzle where the lengths and positions of the slots are what vary? If the puzzle configuration is on a grid, we can use pieces with lengths and slot positions at unit multiples. The three slot pieces up to length seven with these properties have slot positions as shown:

If we take the focus of the puzzle away from slot types, it would be nice if slots always match. The simplest way to do this is to have slots that all point the same direction. As we’ve seen previously, this forces us into a bipartite puzzle configuration, where half of the pieces have slots pointing up, and the other half have slots pointing down. Conveniently, we have two twelve-piece bipartite puzzle configurations in the triangular grid:

Are there solutions? Joe DeVincentis found that there are no solutions to the first and exactly one solution (!) to the second:

As cool as it is to have a puzzle with a unique solution, with a set of this size, it would be rather difficult to find it manually. I’m still looking for a good set for manual solving. I tried using two copies of the pieces up to length 5. I eventually found this solution manually:

I don’t know if there are others, but it’s a little disappointing to have the identical pieces next to each other and parallel like this; finding the solution feels like cheating.

I have been mostly disregarding crossed stick configurations on the square grid to this point, because the possibilities are pretty boring when all of the pieces have the same length. But if we move away from pieces of the same length, new configurations become possible. One easy, almost trivial puzzle, would be to assemble a figure with two copies of the three shortest pieces. There are three ways to do so:

On the other hand, if you ask the solver to find all three, with no hints about what the assembled puzzle should look like, maybe it wouldn’t be completely trivial.

Finally, I hadn’t previously even considered the idea of two-slot puzzles, but with varied lengths, the notion might not be completely ridiculous. Suppose we allow length √2 pieces in addition to length 1 pieces, and allow slots to be either wide, to accommodate 45°/135° angles, or narrow, to accommodate 90° angles. There are then three different pieces possible of each length. With two copies of this set of six pieces, we may attempt to make a closed loop. Here is a solution with alternating pieces from each copy of the set:

Note that even though I had the square grid in mind when I was considering these pieces, it would be entirely possible to jump off the grid, by using short pieces as diagonals or long pieces in horizontal or vertical positions.

# Magic figures from crossed stick configurations

July 1st, 2015 by munizao | Print this post

When I was working on finding configurations to use in crossed stick puzzles, it occurred to me that the same configurations would make good bases for magic figures. Since each piece is a line segment with the same number of intersections, you could put numbers at intersection sites, trying to arrange them so that the numbers on each segment add up to the same magic sum. Since I had already figured out how to use Numberjack to solve magic figure problems in the context of magic dice, it was simple enough to adapt the code to solve other magic figures.

The puzzle that I’m selling as Grand Hex can form two different figures. Since they each have 24 intersection points, it seemed reasonable that one could use the numbers from 1 to 24 on the intersections, and get a magic figure with a magic sum of 50. And here’s one for each configuration:

The gold lines aren’t part of the original puzzle configurations, but they were the obvious places to add a few constraints, since the solver otherwise finds a very large number of solutions for the figures with just the black lines.

# Introducing Quimby: Context sensitive keyboard chording in a GTK input method

June 21st, 2015 by munizao | Print this post

A number of years ago, I found myself wanting to be able to use a greater variety of compose sequences than were generally available for Linux users. Compose sequences are great, and let you enter lots of different accented characters that occur in various languages that use the Latin alphabet. For example, you could type [compose] + e + ‘ to get “é”, and [compose] + c + , to get “ç”. But if you wanted to type “ǫ” you were out of luck. (It’s used in Old Icelandic, and I actually did want to type it once, to input a song title.)

The way to I found to fix this problem was to write a GTK input method module. This is the chunk of code that takes input from the keyboard handler system (xkb) and performs alchemy upon it to produce the characters that show up on the screen when you enter some text in a box. Not every Linux application would use my module. GTK is just one of a number of GUI toolkits used by Linux applications, but it’s a very common one, and it’s the one used by all of the applications I use frequently.

Over time the stock GTK input method has improved somewhat in the range of compose sequences it supports, but since I had input method code of my own, from time to time I found features to add to it. For example, it annoyed me that there was no keyboard shortcut for directly pasting selected text, so I made [compose] + [insert] do just that. (In Linux you can paste selected text (without explicitly copying it) with a middle mouse button click, but in GTK apps you can’t normally do that with the keyboard.)

More recently, I was trying to think of a way to do something about the problem of the inefficiency of typing English. One spends quite a bit of time typing common words. For example, whenever you type “the”, it takes four keystrokes, counting the space after the word. Stenography allows users to reach much faster speeds of text input by pressing multiple buttons at the same time. Most common words can be input using a single chord of button presses.

People who have mastered stenography are typically able to input text at three times their typing speed. The downside is that stenography has an extremely steep learning curve. One can spend months or years in intensive study to reach that plateau, and it can take quite a while just to break even. It’s also a system that has been designed for natural language text input, but computer keyboards have been designed to perform other sorts of tasks as well, like performing commands in applications, and writing code, where punctuation is used in a very different way from how it is used in natural language. (I should note that some efforts have been made to remedy this situation in Plover, an open source stenography implementation.)

Intrigued as I was by the possibilities of stenography, I felt rather daunted by the learning curve, and the expense and/or trouble required to buy or make the specialized hardware required. But what if there were some way to use chorded strokes on a regular keyboard to represent the most common words? Then we could have a system where the learning curve could be relatively modest, as normal typing would always be available. The ceiling of the speed increase would be modest as well, but it looked like an increase of about 10% to 15% might be possible. That’s not nothing. And my GTK input method was just the place to put the code that was needed to make it happen.

The space bar, being the easiest key on the keyboard to hit, was very tempting to use to signify that we are typing a chord that we want expanded. For example, we could use [space] + t to expand to “the “, saving two keystrokes. Since those keystrokes occur simultaneously, it’s almost as good as saving a third. Conveniently, we normally type [space] once per word anyway, so this should feel fairly natural. But simply expanding chorded keystrokes wouldn’t work. The problem is that in normal typing, it will frequently happen that the key press event for one key will occur before the key release event for the previously pressed key. You could be typing “hat rack”, and get “hathe rack” if you typed too quickly.

Fortunately, there was a simple solution. The key insight was that the only time you want a chord to expand into a whole word is when you are at the start of typing a word. And you can detect that, through the context that the input method supplies: GTK input methods allow you to access the text around the cursor. If the cursor is after a space, you are at the beginning of a word. (It’s more complicated than that; you can also be at the start of a word after certain punctuation, and sometimes you are at the start of a sentence, and we should detect that, and automatically capitalize the word we are expanding. But that was enough to get me started.) The problem of mistaken expansions wasn’t entirely banished. You could type “a tree”, and accidentally chord a + [space] + t, which expands to “at “. That’s unfortunate, but if you train yourself to always type the word “a” with an “a” + [space] chord, you can avoid the problem.

The choice of chords to represent common words is an intriguing puzzle in itself, and a matter for a future post. If you run GTK apps, (which means you are probably running Linux) and are interested in trying out Quimby, (short for “Questionably Useful Input Method? But Yes.”) the code is available on GitHub. I make no guarantees about its stability. It’s quite possible that it will crash and make you lose data! But the current iteration has been stable for me of late, and I used it to write this very post. The available chords aren’t documented yet and are still very much in flux; to see what they are currently, read the source. (src/chording.c) Eventually, I want to have the chord list be user extensible, but I’m not there yet. There is still more work to be done, adding more chords, detecting better when we are at the start of a word or a sentence, and supplying a few more features that will make using chording more convenient. But it’s ready to be shown off, and I am interested in hearing what people think about it.

# This is how I roll: Sicherman dice with doubles

June 12th, 2015 by munizao | Print this post

Here are a few mostly functionally equivalent things:

The first is a pair of perfectly normal dice. The second is a “Merged d6”, a 36-sided die I bought through a crowdfunding campaign. Each of the sides is labeled with a sum of the results of rolling two normal dice. One of each of the even numbers between two and twelve is colored green. These let you simulate rolling doubles, as is required for games like Monopoly: each roll of two of the same number is represented. (The small print size of the numbers and the fact that it takes a moment to figure out which number is on top make this somewhat less practical than the normal dice, but I collect dice for mathematical interest rather than practicality.)

The blue and green dice are Sicherman dice. They are numbered a bit oddly. One of them has faces numbered 1, 2, 2, 3, 3, 4. The other’s faces are numbered 1, 3, 4, 5, 6, 8. The distribution of sums of die rolls is nevertheless the same as that of a normal pair of dice. In fact, it is the only non-standard numbering for a pair of dice with this property where the numbers are all positive integers.

Unfortunately, Sicherman dice don’t work for games that distinguish doubles rolls. Could we design a version of the Sicherman dice that does work for such games? The specially colored faces of the Merged d6 suggested a direction to take. We might color the faces of the Sicherman dice differently, and call a roll a doubles roll if the colors match. How many different ways are there to color the faces so as to produce exactly one match for every even number between two and twelve?

I posed this question on Google+. Joe DeVincentis found that there are sixteen essentially different solutions, of which two are the most interesting to me for designs that I might be interested in having made at some point:

### 122334 — 134568

This has the advantage of only requiring three colors, and all of the faces that never match are on the same die. It also has an easy mnemonic that you could use even without coloring the faces: one on low die, odd on high die; four on low die, even on high die. Variations where some subset of the never-matching faces are a different color from the others are considered essentially similar here.

### 122334 — 134568

Here the colors can be ordered from low to high, and have the same order on each die.

The rest of the solutions follow. For clarity, I’ve colored all of the numbers that never match black even when they exist on both dice. We may define a rule that black is not considered to match itself.

# How I made a laptop

May 29th, 2015 by munizao | Print this post

I suppose I should preface this by saying that I don’t recommend that anyone do what I did, nor do I recommend that anyone, having chosen to do what I did, should do it the way that I did it. But I learned some things in the process of doing it, and maybe somebody else will find these things interesting. What did I do? I made a laptop:

Why did I do it? Well, my last (real) laptop died last year. When I was considering a replacement, I decided that I’d probably get more use out of a tablet, since it would be portable enough that I could take it more places. I found a good deal on a refurbished Samsung Galaxy Note 8, and bought one.

But there are some circumstances where I would prefer to have a laptop, with a real keyboard. Programming and writing are a couple of my hobbies, and I’d like to be able to do them away from my desk. I found the on-screen keyboard on the tablet adequate for tasks that require a small amount of typing, like entering data on web forms, but not for more serious text entry. The germ of the idea then took root: if I had a keyboard to use with the tablet, I could connect them together in some way to make a laptop. (The process would have to be reversible; I would sometimes only want a tablet with me.)

Now, there are tablet cases with integrated keyboards that are made for just this purpose. But these keyboards typically require some compromise in typing comfort, compared to a standard keyboard. For my desktop keyboard, I use a mechanical keyboard without a tenkey, since I find that I never use it anyway, and its absence allows me to place my mouse closer to the keyboard, which is ergonomically advantageous. (If you are a particular sort of keyboard geek, you may be interested in knowing that it uses Cherry MX Brown switches.) But for the fake laptop I wanted to make, I wanted something more compact than my desktop keyboard.

There are some highly compact keyboards out there, but I did not want to lose the standard arrow key block. Keyboards that are more compact than a tenkeyless keyboard, but that retain the arrow key block, are a rarer breed. But a good deal on just such a keyboard, a Keycool 84, popped up on MassDrop, and I sprang for it. (You may notice a pattern. I am a sucker for a deal.) I might have preferred a keyboard without a function key row, but this was close enough.

Now I had the tablet and the keyboard, and was left with the task of connecting them together. I knew that I needed hinges, but I didn’t know anything about what the particular hinges I needed were called, or how to get them. I knew that they needed to stick in place when acted on by a small force, (like gravity acting on the tablet) but move when acted upon by a larger force (like me setting the angle of the tablet to the keyboard.) (The process of getting information out of search engines when you are starting from a position of complete ignorance of basic terminology is interesting in itself. My initial flailing led me to forums where artists were discussing making pochade boxes. That didn’t immediately teach me what I needed, but at least I had a relevant term to search.)

Having determined that I wanted what were called either “friction hinges” or “torque hinges”, the next problem was the matter of exactly how sticky the hinges needed to be. The stickiness of a particular hinge is rated according to the torque required to move it. This brought back memories of high school physics, but I wasn’t entirely confident that I could calculate the proper value for the torque of the hinge, given the weight and dimensions of the tablet. An online torque calculator was helpful. Both adjustable torque hinges and constant torque hinges are available; the former appealed to me because they would provide some leeway in case I wasn’t quite right about the proper stickiness for the hinge. Adjustable torque hinges are also the cheaper option, and I found a deal on ebay for a set of four Southco E6-10-301-20 hinges at a better price than I could get for one hinge of that model anywhere else.

Unfortunately, the leaves of the hinges weren’t long enough to be able to attach directly to the keyboard and the tablet. I needed a couple of extension pieces. I settled on lasercut plastic for these. (I ordered the laser cutting though Ponoko, as usual.) In the past, I’ve mostly used acrylic for my lasercut puzzles, but for this project I used delrin. Acrylic can break under compression; it seems that delrin is better when you are using screws and nuts to fasten things.

Which I was. The screws and nuts were actually the last pieces I acquired. As with hinges, this was an area where a dizzying array of options are available, and I lacked the vocabulary going in to specify what I wanted. On top of that, I wanted a much smaller quantity than is typically purchasable, either online or at large chain hardware stores. Fortunately, a friend of mine recommended Parkrose Hardware in Portland, which sells individual screws of a large variety of types. Being able to pick them out by hand and see which ones fit properly into the hinges helped me make the right choice. (In this case, #8-32 3/8″ pan head machine screws.)

At this point what remains to be discussed is how I attached the delrin pieces to the keyboard and the tablet. As I said before, the tablet had to be able to be attached and unattached. I decided to use Velcro for that. I placed four adhesive-backed Velcro squares (loop side) on the tablet, and the matching hook squares on the delrin piece. On the keyboard side, I didn’t care if the delrin piece was attached permanently, and I wanted something that would make a stronger connection than Velcro, so I used a piece of 3M automotive super strength molding tape, which I had lying around. I got the placement of the delrin piece very slightly off, but I was stuck with it, as the super strength tape was indeed as advertised.

And that’s it. Of course, none of this would be at all useful if I couldn’t connect the keyboard to the tablet. I used a USB On The Go adapter for that, which works fine, although I might at some point see if I can find a shorter keyboard USB cable, since the one that came with the keyboard is quite a bit too long for this purpose. The one other thing I am a little unhappy with is that the hinges won’t close as far as I would like. Slightly thinner delrin might have fixed this problem, but if it were too much thinner, it wouldn’t hold up the tablet without bending.

# This is how I roll: Magic dice, part 2

April 11th, 2015 by munizao | Print this post

One formulation of a magic cube simply numbers the vertices of a cube from one to eight, and requires that, for each face, the set of vertices that frame it have the same sum. There are three distinct magic cubes of this type:

Now, first of all, in applying this to a design of dice, it seems that the ideal application would be octahedral dice, since the octahedron is the dual of the cube, and thus the numbers could simply be printed on different faces. The sets of faces with magic sums would then be the ones surrounding a vertex of the octahedron. But I don’t have an order for custom d8’s, I have one for custom d6’s. Given that, what is the best way to represent one of these figures on a cube? As before, we can use a bold font to highlight the number that is used as the result of a roll. This time, since we can’t print directly on the vertices, the numbers will be repeated on each face that borders a vertex.

I have two answers. The first places the numbers on their traditional faces (with opposite faces summing to seven.) Only the middle numbering above can be used in this manner.

The second is suggested by the figure on the right. Since the numbers we aren’t using (that is, 7 and 8) appear at opposite vertices, we can highlight a diagonal ring around the cube and catch all of the numbers from 1 to 6. This is nicely symmetrical, but it does not put the numbers in their traditional positions.

# This is how I roll: Magic dice, part 1

March 29th, 2015 by munizao | Print this post

A while back I supported a Kickstarter campaign for custom laser-engraved dice. I figured there had to be lots of mathy designs out there waiting to be found, and being able to make physical copies of them would inspire me to find some of them. And I have.

One of the first ideas i had was to use magic cubes. I didn’t know what sorts of magic cubes had been discovered, but I knew it was an obvious enough variation on the idea of magic squares that something had to be out there. In general, most magic cubes aren’t good for printing on dice, because they contain numbers in the interior of the cube, and one typically is only able to engrave the exterior. I did however find a couple of promising variations on the page on Unusual Magic Cubes at the late Harvey Heinz’s magic-squares.net site.

That page shows a cube found by Mirko Dobnik where each face is divided into a 2×2 grid. The faces sum to 50, and the rings around the cube sum to 100. In order to turn Dobnik’s cube into a usable six-sided die, I would need to find a solution that placed the numbers 1 to 6 on different faces of the cube, ideally on the same faces that they would occupy on a standard die. Then I could set these numbers in boldface to show that they represent the result of a die roll for a given side.

I decided this was a good time to learn how to use a constraint solver. I picked Numberjack because it uses Python, which is the language I am most comfortable with, and there was a magic square example that I could tweak. With face sum and ring sum constraints, and constraints to put the numbers 1 to 6 on the proper faces, (plus symmetry breaking constraints) I was getting at least hundreds of thousands of solutions. So I added constraints to make the four diagonals that traverse all six faces to sum to 75, and I fixed the positions of the numbers 1-6. The most symmetrical ways to pick corners of the faces of a die are to take all of the ones on one diagonal ring, or to take the corners that meet at antipodal vertices of the die. The first would violate the diagonal sum constraint, and the second bunched the relevant numbers up more than I liked, so I picked an arrangement that still has rotational symmetry about one of the axes through antipodal vertices, but that doesn’t have reflection symmetry. Then there are four ways to pick the axis of symmetry. At first I chose one at random, and came up with just eight solutions, one of which had odds and evens in a checkered pattern. Then I tried again with the axis going through the [1,2,3] and [4,5,6] vertices, and there were two parity-checkered solutions out of six, one of which is shown above.

I know it’s a bit strange to disappear from blogging for nearly a year, and then promise a multipart post that is itself part of a series, but yes, that is just what I’m doing. There are more magic dice to come, and then more mathematically inspired dice that are less magic. Hopefully there will also be some posts that are not about dice, not too far off.

# World Cup Group Scores, and “Birthday Paradox” Paradoxes

June 23rd, 2014 by munizao | Print this post

Here’s an article from the BBC about the so-called “Birthday Paradox” applied to the teams of the 2014 FIFA World Cup. The Birthday Paradox is the term for a common failure of intuition. It’s rather unlikely for two people to share a birthday, and people usually expect it to remain unlikely for any two people in a group of moderate size to share a birthday. In fact, the number of pairs of people grows quadratically, so the probability that there is at least one pair sharing a birthday hits 50% more quickly than people often assume.

It turns out that the tipping point for the size of the group is 23, which is exactly the size of a World Cup soccer team roster. And the teams this year illustrate the balance perfectly: exactly half of them have players that share a birthday. As Ξ points out on the math blog 360, even though 50% is the proportion of teams we would expect to have birthday-sharing-players, it’s actually pretty unexpected to hit the expected value exactly. That might be a “Birthday Paradox” Paradox.

But not the one that I set out to write about! Situations like the Birthday Paradox can come up in all sorts of contexts. Four years ago I noticed an interesting fact: all of the groups in the first round of the 2010 World Cup had different score results. This seemed unlikely to me, but was it really? I’d need to do some more investigation to find out. 2010 was indeed the first time that all of the scores had been different since the World Cup expanded to eight groups in 1998, but there had only been a total of four World Cups to that point, not enough for a good statistical sample.

A bit of background: In the group stage of the World Cup, there are eight groups of four teams; in each group all of the teams play each other in a round-robin mini-tournament. Each team receives three points per victory and one point per draw. The top two teams in each group advance into the next stage, a four round single elimination tournament. (There are tiebreaker rules for determining who advances when the second and third teams tie; I won’t get into those here.)

You can model group results with with oriented graphs: directed edges correspond here to a victory for the team that the edge points away from, and absent edges stand for ties. There are 42 distinct oriented graphs with four vertices, but only 40 different group scores; in two cases the same score can be achieved with two different graphs.

For the sake of mathematical simplicity, let us assume that every game that is played has an equal probability of being a tie, a win for team A, or a win for team B. This makes the problem easier to model at the expense of some realism. In the real World Cup, there are better teams and worse teams, and the teams are seeded into groups such that there is approximately one team belonging to each quartile in each group. (Concerns like geographical distribution may interfere with this ideal.) This means that results with cycles of victories are probably a little less likely in the real world than in our model, as they would require a team that is worse on paper to defeat one that is better. Upsets do happen, but their unlikelihood is what makes them upsets. Additionally, the actual proportion of ties may diverge from 1/3, although this is not in fact a terrible estimate. In 2010, 14 of the 48 group matches were draws.

Complicating matters, the graphs are not equally likely to appear. Notice that a graph with no symmetry (such as the 9-6-3-0 graph in the upper left corner) can occur in in as many ways as there are permutations of the four teams. (There are 24.) At the other extreme, the most symmetrical graph belongs to the group with all ties in the lower right, which can occur in exactly one way. In general, the graphs with more symmetry can be made in a smaller number of different ways. Counting the scores that can be achieved with two graphs, there are 2 scores that can be reached 36 ways, 21 that can be reached 24 ways, 9 that can be reached 12 ways, 3 that can be reached 8 ways, 2 that can be reached 6 ways, 2 that can be reached 4 ways, and 1 that can be reached 1 way. We can check that we’ve got them all by noting that this adds up to 729, or 36, which is the number of different ways six games can go.

I wrote a Python program that found the above counts and then used them to determine the probability that no two groups would have the same score in our model. But before I did that, I wrote another program to simulate the results of a group stage by randomly picking the results of each game. Even though this simulation couldn’t give an exact answer to the problem, I’m glad I wrote it. It was a much simpler program than the one I wrote to get the exact answer, so it was easier to convince myself that it was performing correctly. In the process of writing the final program, I made a number of mathematical and programming errors that led to incorrect results; if I did not have a good idea of the approximate value of the answer, I might have stopped without knowing there was an error.

The end result? The probability of all eight groups having different scores in my model is 393101879398962298880/984770902183611232881, or about .39918. So I was right that all groups having different scores was the less likely case, but wrong to think that it was particularly unlikely. I think a big part of why I was wrong was that I knew about the Birthday Paradox. It primed me to think that no two items in a group sharing a property would be unlikely, in a more general sense than is actually the case. This is the “Birthday Paradox” Paradox that I fell into.

Some puzzles:

Which is more likely to have all different group scores? The men’s World Cup, or the women’s World Cup? The women’s World Cup has had four groups since 1999. (This is a trickier question than it seems, and may illustrate the limitations of the random result model.)

What proportion of ties would maximize the probability that all group scores are different?

We might explore the probability of all group scores being different in various past and hypothetical tournament setups. What if there were more or fewer groups? What if wins counted for two points, as was once the case? What if there were five teams per group? In the cases with four teams per group where there are two different graphs that give the same score, the sets of team records are the same. (For example, in the 7-4-4-1 groups, the records are set of team records for both (expressed as wins-losses-ties) are 2-0-1, 1-1-1, 1-1-1, and 0-2-1.) With 5 or 6 teams, is it possible to come up with a group score that can be formed by two different sets of team records?

(Thanks to Joe DeVincentis, who took up the main puzzle when I posed it on gplus. Also, I should note that the correspondence between World Cup group results and oriented graphs is not original to me; here’s another exploration of the connection.)

# A Magic Dart Puzzle

April 16th, 2014 by munizao | Print this post

Recently I was looking at the following figure, in the context of trying to find useful configurations to make crossed stick puzzles with:

Now, a four piece crossed stick puzzle seems likely to be rather trivial to solve, but it sparked a question: could there be a good, non-trivial puzzle that uses this dart configuration? I recalled that I had in the past made such a figure with craft popsicle sticks:

This assemblage of sticks suggests some sort of puzzle where there will be some figures printed on the sticks at the intersections between the pieces, and there will be some goal concerning the figures that are showing on the sticks that are on top at the intersections. With four sticks, there are 4! permutations of the sticks, and if each stick can be flipped over or rotated 180°, there are 4!·44 = 6144 possible arrangements of the sticks. (Because we can flip over the entire assembly, there are only half as many physical arrangements of the sticks, but it seems reasonable to consider either side of an assembly to represent a different arrangement, since we will probably want a goal for the puzzle that is only concerned with what is visible on one side.)

In the crossed stick puzzles that I have looked at thus far, the only sites that vary have been the intersections between pieces. However, if we allow rotating the pieces, there will be sites that can either be at intersections or not, depending on how the piece is rotated.

I first toyed with using colored marks at the variable sites, possibly with holes in the pieces that could reveal the color of the piece behind it. However, I made more progress when I turned to the idea of putting numbers at the sites. Since there are eight sites on the two sides of a piece, I thought of putting each number between 1 and 8 on one of them. This suggested to me a puzzle along the lines of a magic square, where the goal would be to make a figure where the sums along the four lines all matched. I noticed that there are exactly four ways to partition the numbers 1 to 8 into two sets of four, such that each set has the same sum (18):

```1 2 7 8 | 3 4 5 6
1 3 6 8 | 2 4 5 7
1 4 5 8 | 2 3 6 7
1 4 6 7 | 2 3 5 8

```

That would give me an elegant way to place numbers on each side of the four pieces, but I still needed to find a way to arrange the numbers. The simplest way would be to place them in order from smallest to largest. I wrote a short Python program to output the solutions. Unfortunately, there weren’t any! After that I tried other orderings. (Note: due to a bug in my program, what I previously had here was incorrect.) If we number the sites from smallest to largest as 0 through 3, ordering the sites as [0, 2, 3, 1] gives a single unigue solution:

Ordering the sites as [0, 3, 1, 2] gives four solutions with a magic sum of 18, and four solutions with a magic sum of 17. Notice that magic figures like this have a numerical “reflection” symmetry. Given a solution, you can generally obtain another by replacing every numeral n with 9 – n. This means that the orderings [2, 3, 0, 1] and [3, 0, 2, 1] will behave basically like the orderings mentioned above. Other distinct orderings with solutions are [0, 1, 3, 2] (7 solutions), and [1, 0, 3, 2] (2 solutions).

I’ve only started looking into how I could physically produce such a puzzle. Custom printed and die cut PVC looks promising; I think the marginal cost of a piece would come to under 10¢; the real problem would be in the setup cost, and in the unlikelihood of minimum orders of less than 500 for each piece being feasable.

As an aside, once I was looking at those partitions of the integers 1-8 into eight subsets with equal sums, the obvious thing to do with them was to make a 4×4 “magic square” where each of the subsets occurs once as a row or column. Here’s one where the diagonals also have a sum of 18:

This seems like the sort of idea that would have to have been looked at before, but I have no idea how to find out where it may have been previously discussed.﻿

# Stop! In the name of Octagons!

March 29th, 2014 by munizao | Print this post

In the spirit of the flexible rhombic cell polyominoes that I posted about previously, here’s a hexiamond tiling of eight triangular segments squashed into an octagon:

Of course, octagons can also be used as base cells for polyforms. In fact, any regular polygon (and quite a lot of other things) can be used in this way, but octagons are special. They don’t tessellate the plane by themselves like equilateral triangles, squares, and hexagons, but they do form a semi-regular tessellation of the plane along with squares. This makes polyocts behave fairly well; you won’t be able to tile something convex and hole-free with them, but you can tile something that’s reasonably symmetrical at least. For example, here’s a tiling of the 1-, 2-, 3-, and 4-octs:

That’s not the most symmetry that polyocts are capable of, (full octagonal symmetry is possible) but it’s the most we’re going to get with this set of pieces. See this page by George Sicherman for some figures with full symmetry that can be tiled with various individual polyocts.

# Towards a Python Based Domain Specific Language for Interactive Fiction

March 1st, 2014 by munizao | Print this post

Several years ago I wrote an Interactive Fiction game. (To be clear, I mean the sort of game where you type things like TAKE ROCK, or GO NORTH, and the game obligingly responds by allowing (or not allowing) the player character to do so, and then reports the results in prose.) Since then, I have not written another. There are quite a few reasons for this, but one of them is that there really aren’t any IF authoring systems that I like. In particular, Inform 7, the system that has received the majority of the mind share for IF in recent years, uses syntax that approximates English text as nearly as possible, which makes it very easy for a newbie to understand, but can seem frustratingly verbose and unstructured to an experienced programmer. While there are other systems around, most of them use languages that were built from scratch for the purpose of IF authoring. I personally would prefer to be using a general purpose language; Python is my favorite, and the one I have the most experience with in recent years. A system that used Python could leverage the existing skills of programmers, and allow the use of code libraries that have already been written.

As it happens, there is already at least one IF authoring system that uses Python. In 2011 Nick Montfort released Curveship, an IF development system that was mostly intended as a testbed for some of Montfort’s ideas about dynamic text generation. Unfortunately, reading the code of a sample game written with Curveship reveals what should have been obvious to me: Python, as a general purpose interpreted language, is actually pretty poorly suited for the task of IF authorship. The contortions that it takes to write a game using Curveship are in fact pretty reasonable under the circumstances, but in my opinion they are bad enough to keep it from being a respectable option for writing an IF game of any length.

Nevertheless, reading that sample game code prompted me to consider what syntax I would want to see in a Python based IF development system. I recognized that it might take some tricky hacks to make that syntax achievable, and in some cases there might need to be compromises with what the language “wants”. But I’ve come to the position that we can get to a language syntax that is reasonably concise and readable. In outlining my proposed syntax, I was guided by the constructs present in Inform 6, (which, despite sharing a name and a lead developer with Inform 7, is a very different system, and more like a traditional programming language.) In my opinion, Inform 6 does a lot of things right, in that the sorts of things you want to write as an IF programmer can be done concisely. Unfortunately, many of the actual symbol characters you type in Inform 6 are different from the ones you would use in any language in the whose syntax falls into the same lineage as C, so for a programmer, it can give a feeling of being a “crazy moon language” until you get used to it.

The sample game code that I mentioned previously was an implementation of Roger Firth’s Cloak of Darkness, a short game that has been translated into many IF languages so that prospective authors can judge their features and syntaxes. Here is an excerpt of Cloak of Darkness in my proposed syntax:

```class Foyer(Room):
name = "Foyer of the Opera House"
desc = "You are standing in a spacious hall, splendidly decorated in red \
and gold, with glittering chandeliers overhead. The entrance from \
the street is to the north, and there are doorways south and west."
dirs = {
west: cloakroom,
south: bar
}
```

The first thing to notice is that here, as for every unique object or thing in the game, we will be defining a class. One of the unusual things that distinguishes IF programming is that the vast majority of objects that are written are one-offs. We won’t be creating multiple Foyer objects; we can assume that we will only ever need one. Because of this Inform 6 does not require a separate step to instantiate an object. (You can create classes that are not automatically instantiated, but this is not the usual case.) Python, by contrast, does not autoinstantiate. But we can get around that using Python’s metaclass mechanism, which allows us to change how classes work at class definition time.

```class Cloakroom(Room):
desc = "The walls of this small room were clearly once lined with hooks, \
though now only one remains. The exit is a door to the east."
dirs = {
east: foyer
}
```

A couple of things to notice here: first, the `Foyer` class refers to the `cloakroom` object before we have even defined it. This is not actually possible in Python. But allowing forward references like this is quite desirable! IF games usually contain a web of objects that can interact with each other in various ways, and having to arrange code so that it contains no forward references would be a real hindrance. Can we get around the problem? I’m pretty sure we can, actually. Python’s ast (abstract syntax tree) module allows you to modify parsed Python code before you run it. It should be possible to scan for classes and make dummy objects for each class, so the illegal forward references will actually be perfectly legal backward references, which should, if we can pull this off, turn into forward references again when we define the referenced object. (We may still need to be careful that we don’t access variables and methods of later objects at initialization time, but this should be doable.)

The second important thing to point out here is that the “cloakroom” object was named in lowercase, while the `Cloakroom` class was upper case. I wanted the autoinstantiator to give a name for the object that does not interfere with the name for the class, so I’m having it take the lowercase of the class name. You might well be wanting to refer to either the object or the class later. (This does mean that lowercase names for game object classes will be illegal.) Moving along:

```class Cloakroom(Room):
desc = "The walls of this small room were clearly once lined with hooks, \
though now only one remains. The exit is a door to the east."
dirs = {
east: foyer
}

class Hook(Thing):
name = "small brass hook"
nouns = ["peg"]
def desc(self):
"It's just a small brass hook, "
if cloak.parent == self:
"with a cloak hanging on it."
else:
"screwed to the wall."
```

Notice that the hook is meant to be an object in the Cloakroom. Since it is natural for us to list the things in a room after describing the room itself, we will automatically put each `Thing` into the last `Room` in the code. Sometimes you won’t want that. For those cases, there will be a `location` attribute that you can set. In addition to being able to explicitly set the location, I want one to be able to set it to a dummy object called `Above` that would cause an object to be contained in the last mentioned thing. I’ll probably want some more tricks for placing things in the object containment tree. This is going to take some careful thought.

The other thing that’s going on here is that I’m borrowing the automatic printing of bare string expressions from Inform 6. Bare strings are perfectly legal in Python; they just don’t do anything. I’m actually changing the semantics from how it works in Inform 6. In inform 6, bare strings automatically print a newline, and then return True. I’m not convinced this is a win. It means you have to use print statements instead of bare strings half of the time, and you frequently get burned if you pick the wrong one. The implicit return saves you the effort of typing “else” if you use a bare string in an if clause, but at the cost of making the code more difficult to understand. Since we aren’t outputting newlines in the places where we would usually be implicitly doing so in Inform 6, we’ll have to be careful that the system does it for us. Getting newlines right is actually a more non-trivial problem than you would think, but I think it’s doable. (Turning bare string expressions into calls to a printing function would require another ast hack.)

Finally, I’ll skip a bit ahead to get to another language feature I would want:

```class Cloak(Clothing):
name = "velvet cloak"
location = player
containment = worn
nouns = ["handsome", "dark", "black", "satin"]
desc = "A handsome cloak, of velvet trimmed with satin, and slightly \
spattered with raindrops. Its blackness is so deep that it \
almost seems to suck light from the room."
used = False
def enact(self):
if +cloakroom:
if +drop or (+put and +on):
bar.lit = True
if self.used == False:
score += 1
self.used = True
if +take:
bar.lit = False
```

Notice the presence of the unary plus operator. This is used as an implicit comparison. For any given built in class of objects, there will be a variable whose value corresponds to the “obvious” instance of that class that one might currently want to check against. The implicit comparison will return `True` if it is being applied to that object, otherwise `False`. For rooms, the implicit comparison checks the player’s location. For actions, it checks the current action. For things, it checks the indirect object of the action, (the assumption being that we are most likely in a method belonging to the direct object) and for prepositions, it checks the current preposition object. (Sometimes you will be in a method belonging to the indirect object and you will want to check the direct object. I’m still not sure whether making the implicit comparator work in this case is reasonable, or whether we should fall back to an explicit comparison.)

This feature is based on the implicit switch feature in Inform 6, but it works in any context, and should feel like less of a kludge. Since we used unary plus for the explicit comparison, it seems elegant to use unary minus for the negation of the comparison. In terms of implementation, operator overloading should work in a pretty straightforward manner here.

Finally, I want to point out what’s going on with the `name` and `nouns` attributes. The `name` attribute is what the system would print out, when listing an item in your inventory, or when outputting the result of an action, e.g., “You take the velvet cloak.” The `nouns` attribute contains the words that the parser will accept as referring to an object. Notice that the words in the `name` are not present in the `nouns`; we’ll automatically put them there at load time, since you will pretty much always want them there. Inform 7 goes a step farther, making the identifier in the code the same as the printed name and the list of words accepted by the parser. If you’re a programmer, you’re probably shrieking in horror at the notion of identifiers containing spaces. So we won’t go there.

I should stress that none of this actually exists. The tricks required to get Python to accept my syntax modifications would be fairly trivial compared to the work of writing, from scratch, an IF library capable of parsing commands, manipulating a world model, and being extensible by game authors in ways that they will need. A front end that displays the game being played in an attractive fashion would also need to be written, although for that purpose, the existing code base of libraries written in Python would be very helpful. I don’t know that I will actually follow through with this. But whether I do or not, I hope some people will find this a useful thought experiment in the realm of what an IF language syntax could look like.

After the cut, for the curious, is the complete code for Cloak of Darkness in my proposed syntax:
» Read more: Towards a Python Based Domain Specific Language for Interactive Fiction

# Some Contributed Solutions

October 2nd, 2013 by munizao | Print this post

I’ve had a few solutions sent in recently, so I wanted to share them with you all.

First, Abaroth noticed that my rhombic-cell pentomino tiling had just enough space to fill out into a five pointed star if the tetrominoes were also included:

But that was just the beginning! He then proceeded to produce an entire collection of tilings with these pieces, which he calls flexominoes. One problem that can come up in tilings of this sort is that if there is a vertex with three rhombi around it, a polyomino containing all three rhombi has an ambiguous identity, since there is more than one way to “unglue” the polyomino at that point. I contributed an ambiguity-free solution to one of the patterns Abaroth found:

Speaking of rhombuses, Abaroth has been investigating color-matching puzzles using rhombic tiles. His puzzle page has more interesting material on color matching puzzles and symmetrical polyhex tilings.

Next up, George Sicherman sent in a symmetrical tiling for the flexible tetrarhombs:

What’s interesting here is that although the outline of the tiling is symmetrical, the pattern of the cells isn’t. The lesson here is that being able to trade off some cell-level symmetry for more pattern-outline symmetry can give us a little variety in our choices of what we can tile.

Finally, Bryce Herdt provided a de Bruijn sequence of invertible length 5 binary words. (That is, a cyclic sequence where each word occurs once as a substring.) Since he did so in text format, I made a visualization: