Solution to the FiveThirtyEight Riddler Classic puzzle for March 23, 2018

FiveThirtyEight’s weekly Riddler column has a really nice problem today:

From Joseph Converse, a puzzle of digital manipulation:

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)

Here is the solution… (spoiler warning!)

Continue reading Solution to the FiveThirtyEight Riddler Classic puzzle for March 23, 2018

More problems that seem easy but are actually NP-hard

In the last post, I illustrated how the 0-1 integer linear programming problem can be reduced to solving a multivariate system of linear and quadratic polynomials over the complex numbers, demonstrating that the latter problem is NP-hard. Let’s see what other problems we can prove are NP-hard by reduction from 0-1 integer programming.

Continue reading More problems that seem easy but are actually NP-hard

How hard is determining whether an algebraic set is nonempty?

Suppose we are given a system of polynomial equations in \(n\) variables, where each polynomial has degree at most \(d\), and the coefficients are integers given as binary. We want to determine whether this system of equations has any solutions over the complex numbers. In other words, we want to determine whether the algebraic set specified by the system of polynomial equations is nonempty.

What computational complexity class class does this problem fall into? Can we do it in polynomial time if we take the degree \(d\) to be a fixed constant?

As it turns out, this problem is NP-hard, even for \(d = 2\). The proof is straightforward and requires no algebraic geometry or other “hard” math—you just have to know the trick.

Continue reading How hard is determining whether an algebraic set is nonempty?

String blacklists for filtering blog spam

There are a lot of methods people have devised for identifying spam. Some of these techniques are very sophisticated: Bayesian methods, neural networks, etc. The method I use for filtering spam on this blog, however, is very simple: string blacklists.

There are obvious downsides to this approach, such as the potential for false positives (good comments that are incorrectly classified as spam, perhaps due to the infamous Scunthorpe problem) as well as the high rate of false negatives (spam comments that are not recognized as such and have to be deleted manually). However, word blacklists are available as a built-in feature of WordPress, so I don’t have to use a paid subscription blog spam filtering service such as Akismet. Also, the simplicity and controllability of the approach are nice.

In the rest of this post, I will list and describe all of the string filters I use, so that other bloggers can copy them if so desired.

Continue reading String blacklists for filtering blog spam

I found a javac bug

JDK-8178701: Compile error with switch statement on protected enum defined in parent inner class

I discovered this bug when I wrote some code that compiled in Eclipse, committed it, and then got an email a few minutes later from our Jenkins continuous integration server saying that the build failed. From the error message, I managed to track it down to a specific section of code that compiled in Eclipse but gave a compile error in javac.

This isn’t the first time I’ve ran into a Java compiler or standard library bug while developing CertSAFE, nor is it the first time that I’ve submitted a bug report via the Oracle web form. However, it is the first time that I’ve had a report accepted and published as a verified OpenJDK bug.

I’m always happy when I find a compiler bug, because it makes me feel better about bugs in my code to know that the platform developers screw up too.

A plausible-sounding data structure that probably doesn’t exist

Here is a description of an abstract data type: a confluently persistent set data type containing a subset of the integers in a range \([1..n]\) and supporting \(O(\log(n)^c)\) time creation, \(O(\log(n)^c)\) time size query, \(O(n \log(n)^c)\) time conversion to a duplicate-free list, and \(O(\log(n)^c)\) time merging, for some constant \(c\). Here, “creation” takes as arguments the range of the element domain \([1..n]\) and an optional single element in this range, and “merging” takes two sets with the same domain and returns a new set representing the union of the two input sets. In Haskell, the type signatures for these operations might look like this:

Seems fairly reasonable, right? I’m going to show that it is likely that no such data structure exists.

Continue reading A plausible-sounding data structure that probably doesn’t exist

Making ByteString and Text instances of Foldable… almost

I just noticed you can do this:

And then use it like this:

Notice that those are the polymorphic Foldable functions maximum and mapM_, not Text-specific functions. I don’t know if this has any real-world applications, but it’s kind of neat…

Update: As pointed out by lfairy on Reddit, the FMList type works kind of like this.

Exact (integer arithmetic only) capsule intersection test

The capsule (also called a “pill”) is one of a few common types of shape used for collision detection in games and other applications. A 3-D capsule is a cylinder capped by hemispheres. The 2-D equivalent, a rectangle capped by semicircles, is technically called a stadium, but they are commonly just called capsules as well.

Capsules used for collision detection in Super Smash Bros. Melee.
Capsules used for collision detection in Super Smash Bros. Melee. From here.

Capsules are nice because they can form both spherical and elongated shapes in any direction. The animation above shows how Super Smash Bros. Melee uses spherical hitboxes that are “stretched” across frames into capsules to prevent fast-moving attacks from going through opponents without hitting them. (Marvel vs. Capcom 3 uses the same trick.) What really makes capsules useful is that they have a very simple mathematical description: a capsule is the set of all points less than a certain radius from a line segment. This means you can check whether two capsules intersect each other by just finding the shortest distance between the two line segments and checking whether it is less than the sum of the radii.

Calculating the distance between two line segments is a well-known problem. This StackOverflow answer gives the code to do that with floating-point arithmetic. Sometimes, though, approximating the correct answer with floating-point isn’t good enough. What if we want an exact intersection test for capsules using only integer arithmetic?
Continue reading Exact (integer arithmetic only) capsule intersection test

Interactive WebGL Demo: Screen-Space Subsurface Scattering

Screen-space subsurface scattering (also known by the amusing acronym SSSSS) refers to a class of techniques for approximating subsurface scattering effects in 3D graphics as a fast postprocessing pass, rather than attempting to accurately model light passing through a translucent material. The original article on screen-space subsurface scattering used a series of blur passes modulated by the depth buffer to fake the detail-blurring effects of subsurface scattering in real time. The diffuse and specular components of reflection in the scene are rendered out to separate textures; only the diffuse layer is blurred, and then the sharp specular shading is composited in afterwards. This is designed to model the multi-layered behavior of many materials, like human skin in the original paper, where light rays either reflect off the surface immediately on contact or penetrate into the material and bounce around before exiting.

I took the sample shader code from that page and translated it into a simple WebGL demo. You need to have a browser that supports WebGL and the WEBGL_depth_texture extension. (Chrome should work, at least.) There are two sliders that let you control the subsurface scattering effect:

  • One slider controls that simulated scattering radius by adjusting the distance between samples for the blur operation. If you turn this parameter up very high, you can get wave-like artifacts near sharp transitions in depth due to the way the depth buffer is factored into the blur operation. Increasing the number of Gaussian blur samples would reduce this effect at the cost of performance.
  • The other slider controls how sharp a depth difference has to be before the shader will stop blurring across that area. If you turn this up to a large value, disconnected areas of the mesh will start blurring into each other, but if you turn it down too low the scattering effect will disappear completely.