dfa.io | about | archive

Arranging keys on my key holder is NP-hard

This past summer, I bought this key-holding gadget. I’m a little paranoia about losing my keys, so I figured it’d be a good way to make sure I don’t lose any of them.

But god forbid you ever have to change what keys you carry with you.

I just bought a USB drive to put on it (I recently had a snafu with arch and had to chroot in. But I had to go a couple hours without my laptop because I didn’t have a boot USB on me. Never again).


30 minutes into the process of rearranging my keys so that the USB drive would fit on it, I thought to myself: “this has to be NP-hard.”

And indeed it is.

We reduce from PARTITION. (Really, they’re nearly the same problem). Take a second and gaze at the key holder on the linked amazon page to get a sense for the problem. We want to arrange the keys so that all keys fit on the keyring and there’s no “tangling” of keys in the middle.

Call the length of the key holder $l$.

Suppose I give you a bunch of keys to put on the key holder. Each key is very short - maybe $\frac{l}{3}$. So the length of the keys won’t be an issue - it’s mostly an issue of getting the heights to match. The keys are of varying heights.

Certainly, the key holder needs to have equal height on each end. Additionally, every key must be present (like, why would you even buy one of these things if you’re still going to have keys jangling around)?

So then, if the sum of the heights of the keys is $S$, each side of the key holder must have height $\frac{S}{2}$.

But this is just exactly PARTITION, which we know to be NP-complete.

Sigh. Wikipedia says that there’s a pseudo-poly time dynamic programming solution for PARTITION, which has led PARTITION to be called “The Easiest Hard Problem”.

Though to be frank, I don’t know if I consider that to be much condolence.

Heterological Adjectives

I stumbled across the following tidbit while reading Godel, Escher, Bach last night: heterological adjectives! It’s a formulation of Russell’s Paradox, but in the English language.

Suppose I present you with the following two adjectives:

autological: an adjective that describes itself

heterological: an adjective that does not describe itself

For example, ‘short’ is an autological word, but ‘long’ is not. I think my favorite autological word (and these are the far rarer of the two) is ‘attributive’ - the word itself attributes meaning to it’s modified noun.

And here’s the brain-teaser of the day. What if we ask the following question: “Is ‘heterological’ heterological?”

If ‘heterological’ is itself heterological, then it certainly describes itself. But that would make ‘heterological’ autological. But we just said it was heterological!

If ‘heterological’ is not heterological, then it is autological (they’re antonyms afterall). So then ‘heterological’ describes itself. So then ‘heterological’ is heterological. Contradiction!

So we wind up with the following: ‘heterological’ is heterological if and only if ‘heterological’ is not heterological.

Just a Wednesday morning’s musings.

MPD Recently Added Playlists

mpd (which stands for Music Player Daemon) is a commonly-used backend for playing music on Linux systems. I’ve been using it in conjunction with the ncmpcpp (ncurses-music-player-client-plus-plus) frontend for a while. It’s great for a number of reasons.

I’ve been looking for a way to emulate iTunes’s Recently Added playlists for a while and finally sat down to solve the problem.

mpd stores playlists as plain text, stored (on my system) in ~/.config/mpd/playlists as .m3u files. Since it’s plain text, we can simply redirect the output of some bash command to a new playlist file.

The command

find ~/Music -name "*.mp3" -mtime -30 | sort

does a nice approximation of the functionality for me. The -name flag followed by *.mp3 looks for mp3 files. The -mtime flag followed by -30 asks for files that have been modified in the last 30 days (note this can also mean getting added to the directory).

I chose to pipe this to sort, as I listen to music by album, and all my mp3 files start with their track number. So piping to sort sorts each album internally.

Feels like scratching a long-lasting itch :) This opens up a whole new world of “smart playlists!” You could write some giant, complicated python script, throw it on a cron job, and you have yourself a smart playlist :P

This is why I love mpd + ncmpcpp :)