Owner’s Manual

Originally posted to /r/WritingPrompts.

Prompt by me:

“Before purchasing a dragon, make sure to check the safety ratings from the National Dragon Transport Safety Administration.”


Thank you for purchasing the 2019 Volksdrachen Puk®! The stylish, compact, and efficient Puk sets a new standard in serpentine design.

Your dragon features:

  • All-wing drive
  • Tail-mounted backup camera
  • Pitot tube airspeed indicator
  • 11.5 inch bio-electrical touchscreen with Bluetooth support
  • Sail-fin antenna
  • Air lane-keeping assist
  • Parking claw suitable for most surfaces
  • Ten airbags with bronchial inflation
  • Adaptive cruising altitude control
  • Power steering

Continue reading Owner’s Manual

Potato

Originally posted to /r/WritingPrompts.

Prompt by /u/ElectronicLoad:

You’ve developed telekinesis, but to your dismay you can barely manage to lift a pound, with no hope of becoming any stronger


The potato wobbled. I concentrated, contorting my face. Lift. Lift.

Nothing. It was too heavy.

Zapped by lightning and dipped in radioactive sludge at the same time, and this is all I got. The ability to make vegetables wiggle.

Could I lift my own hand? No. I couldn’t even feel my own hand with my power. Apparently it didn’t work on living matter. No ripping the heart out of someone’s chest.

Continue reading Potato

B Movies

Originally posted to /r/WritingPrompts.

Prompt by /u/BronzeHeart92:

Your roommate is a supervillain with the ambitions to take over the city. Nothing out of ordinary, right? Thankfully, he prefers to spend the time watching b-movies and munching on popcorn.


“So, Mike, what’s on for tonight?”

Hearing my name caught my attention just enough for me to realize I had heard my name. I was sitting on the couch, and the sound came from behind me. “Did you say something?”, I asked, craning my head around.

Alex hauled his old laptop out of its case. The thing weighed like ten pounds without any cables or peripherals—I knew from past experience, from that time I had to lug it through the airport. The laptop clunked as he set it down on the fake wood surface of the kitchen table.

“Yeah”, Alex said. “I said, ‘what’s on for tonight?’.” He repeated the words slowly, enunciating each sound like he was talking over a bad phone connection. I hated when people did that. I wasn’t listening the first time; I was listening now. He didn’t have to act like he was talking to a toddler with a learning disability. Condescending.

Continue reading B Movies

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