## Scare monster is busted in NetHack 3.6.1: a story

Originally posted to /r/nethack.

I, a thoroughly wiki-spoiled but not actually very good player, finally made it to Gehennom for the first time. I am doing pretty well so far in this game, all things considered. I made dragon scale mail from a silver dragon I killed back in the Castle. I got a silver saber out of polypiling and enchanted it to +5, then found another silver saber just lying around in one of the early Gehennom levels, and now my orcish Barbarian is dual-wielding those to cut through every demon in sight.

Heading down, I bribed my way past Asmodeus no problem. Juiblex’s swamp had no Juiblex because I had wand-of-digging-ed him previously after summoning him back in Orctown with my accidental same-race sacrifice of orcs.

## NetHack: More lessons learned the hard way

Originally posted to /r/nethack.

I just got to Medusa’s level. I wanted to follow the same strategy I’ve had success with previously: dig down to skip the water, magic map the maze to find the stairs quickly, blind myself, walk up the stairs, and apply an uncursed mirror at her to instantly turn her to stone.

The first thing I did was try to dig down on the starting island. I promptly learned that water fills in pits that you dig adjacent to water tiles. Now my armor is rusty and some of my scrolls got blanked.

After using a scroll of earth and pushing the boulders into the water to make enough land tiles to dig down on, I made it to the maze level. The magic mapping went fine and I walked up the stairs with my blindfold on and my mirror ready. I even had reflection this time so I shouldn’t even have needed the mirror according to the wiki.

## NetHack: My most annoying death yet

Originally posted to /r/nethack.

I’ve been trying on and off to ascend in NetHack for years now. I was just running one of my best games yet…

I started with a dwarven Valkyrie to make things easy. The RNG gave me 18/02 STR and 20 CON for my starting stats, so I had plenty of carrying space. This proved to be important when I ran into a huge general store early on. I purchased a leash from the shopkeeper and then used my little dog to rob him blind. By stealing high-level spellbooks and other expensive items and then selling them back to that same shopkeeper, I was able to build up enough cash to buy a plate mail from him. Together with some other armor, this brought my AC down to -5 by dungeon level 2. I was also able to identify lots of items in the process, including most notably an amulet of ESP which I again stole from the same shop.

## 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.

• 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
• Power steering

## Potato

Originally posted to /r/WritingPrompts.

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.

## 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.

## 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!)

## 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.

## 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.

## 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.