Computational complexity of jigsaw puzzles

During the pandemic, I started doing more jigsaw puzzles. Not real puzzles mind you—I found a jigsaw simulator on Steam that was fairly authentic to the real experience. And since I was doing jigsaw puzzles through the medium of video games, I couldn’t help but think about them in the context of puzzle video games. I realized, jigsaw puzzles are kind of weird! In your typical puzzle video game, the ideal is to have a set of levels, each of which require some crucial insight. In contrast, a jigsaw puzzle is more like a large task that you chip away at.

One way of thinking about this is through the lens of computational complexity. Take Sokoban, the classic block pushing puzzle upon which many puzzle video games are founded. In general, a Sokoban puzzle of size N requires exp(N) time to solve, in the worst case. However, the typical Sokoban puzzle does not present the worst case, it presents a curated selection of puzzles that can be solved more quickly. This gives the solver an opportunity to feel clever, rather than just performing a computation.

Jigsaw puzzles, on the other hand, are about performing a computation. And, if you wish to do a large jigsaw puzzle in a reasonable amount of time, you look for ways to perform that computation efficiently. This raises the question: what is the computational complexity of a jigsaw puzzle?

According to the open access paper, “No easy puzzles: Hardness results for jigsaw puzzles” by Michael Brand, realistic jigsaw puzzles require Θ(N2) steps both in the worst case and on average. On the other hand, this is not born out by my own statistics, which seem to fit a straight line.

[Read more…]

Review scores: a philosophical investigation

Normally, in the introduction to an article, I would provide a “hook”, explaining my interest in the topic, and why you should be too. But my usual approach felt wrong here, since I cannot justify my own interest, and arguably if you’re reading this rather than scrolling past the title, you should be less interested than you currently are.

So, review scores. WTF are they? I don’t have the answers, but I sure have some questions. Why is 0/10 bad, 10/10 good, and 5/10… also bad? What goals do people have in assigning a score, and do they align with the goals of people reading the same score? What does it mean to take the average of many review scores? And why do we expect review scores to be normally distributed?

Mathematical structure

Review scores are intuitively understood as a measure of the quality of a work (such as a video game, movie, book, or LP)–or perhaps a measure of our enjoyment of the work? Already we have this question: is it quality, or is it enjoyment, or are those two concepts the same? But we must leave that question hanging, because there are more existentially pressing questions to come. Review scores do more than just express quality/enjoyment, they assign a number. And numbers are quite the loaded concept.

[Read more…]

From the Archives: Evaluating FiveThirtyEight

This is a repost of a simple analysis I did in 2012, evaluating the presidential predictions of FiveThirtyEight.  What a different time it was.  If readers are interested, I could try to repeat the analysis for 2020.

The news is saying that Nate Silver (who does election predictions at FiveThirtyEight) got fifty states out of fifty. It’s being reported as a victory of math nerds over pundits.

In my humble opinion, getting 50 out of 50 is somewhat meaningless. A lot of those states weren’t exactly swing states! And if he gets some of them wrong, that doesn’t mean his probabilistic predictions were wrong. Likewise, if he gets them right, that doesn’t mean he was right.

[Read more…]

A 2D voting sim

I made a Monte Carlo voting simulation. No particular reason, I just think it’s neat.

Okay, so I was thinking about the Median Voter Theorem, which says that the winning position in an election is the position of the median voter. Of course, this conclusion only holds under certain assumptions, and none of those assumptions are actually true. And yet the conclusion is approximately correct in many situations. That’s why we care disproportionately about the median congress members (like Susan Collins), the median Supreme Court Justices (like Roberts), and the median “swing” states (like Pennsylvania).

But it should be obvious that the median voter fails in a lot of ways. In particular, it doesn’t predict the political polarization that occurs in US politics. And there are plenty of possible explanations: voter turnout, third parties, primary elections, politician’s charisma factors, multidimensional political spectra, and so on. But I’m not sure which among those explanations are most important.

The voting simulation won’t answer any of these questions, I’m just setting the context. One of the assumptions of the Median Voter Theorem is that political preferences exist along only one dimension. I thought I’d try running simulations with two dimensions to see what would happen, and to make some pretty graphs.

Plot showing all the voters and candidates along a two dimensional spectrum.

Voters and candidates in a 2D space

[Read more…]

A music theory analysis of SUNN O)))

I’ve complained before about music theory, and how it fails to actually address any of the music I actually like. One kind of music I have in mind is drone music. Consider, for instance, this reddit thread on the music theory of SUNN O)))

Honestly most drone is fifths and minor scales, it’s not really complicated.

The attitude being expressed is that drone music is too simple to require any music theory. This is a failure to engage with the music on its own terms. If that’s all there is, then what, pray tell, distinguishes different songs and artists? Are they just all interchangeable?

While it may be the case that drone music is particularly simple, I feel that this only makes the lack of a music theory all the more frustrating. Most music theory is frankly too complicated for me to understand, and it would actually be nice to have some simple music theory for once, if only music theorists didn’t think it was beneath them. In any case, I think the theory behind drone music is likely more complicated than they are making it out to be. Drone is highly preoccupied with texture (aka timbre)–a subject so difficult that music theory as a field has basically given up on it.

Anyway, in the spirit of being the change I want to see, I analyzed the spectrograms of a couple SUNN O))) songs.

[Read more…]

Moiré patterns with alternate shapes

A Moiré pattern is the interference pattern that emerges when you superimpose two grids that nearly line up. For instance, you could have two identical metal sheets with circular holes. If you put one in front of the other, and slightly rotate it, then you get a Moiré pattern.

Circular moire

Left: a Moiré pattern formed by two hexagonal grids of circular holes, one rotated by 5 degrees. Right: an artist’s (my) conception of the resulting Moiré pattern. This and all other images were drawn “by hand” (with Illustrator), so please accept some imperfection.

A reader expressed curiosity about what would happen if you replaced the circles with a different shape. As it happens, I am a former condensed matter physicist, which makes me a sort of expert in lattices. So I already know the answer, but let me walk you through with illustrations.

[Read more…]

Basic epidemic math

We are living in an epidemic of armchair epidemiology, and far be it for me to contribute by giving my own feverish take as an expert of an unrelated field. Therefore, I solemnly swear that I will make no predictions about the present pandemic. I am not paid enough to make such predictions–and if you did pay me I would consider it my professional duty to find you a better expert.

What I can do for free, is read up on basic epidemiology, and digest the maths for you, dear reader. My sources: Wikipedia’s article on mathematical modeling and compartmental models, and some lecture notes I found. My expertise: during my PhD in physics, I frequently worked models like the one I’m about to discuss, only with electrons instead of people.

The SIR Model

The very first epidemiological that one learns about, is the so-called SIR model. This model divides the population into three groups (“compartments”): susceptible (S), infected (I), and recovered (R). Susceptible people are those who could be infected; infected people are those who are currently infectious; recovered people are those who are no longer infectious, and are immune to infection. “Recovered” can be a bit euphemistic, since one method of “recovery” is dying. Another method of “recovery” is by developing symptoms strong enough that the victim knows to quarantine themself (becoming less infectious).

[Read more…]