A Method for Producing a Uniform Shuffle with Dice

I ran across this problem as I was reading Root: The Roleplaying Game. The game takes place in The Woodland, which is made up of twelve clearings (i.e. towns). The game comes with a few different Woodland maps you can use as is, but there is also a method for procedurally generating your own unique Woodland. A couple of these steps require rolling to randomly pick values off a list. This is fairly standard in RPGs, but here there are uniqueness constraints where you have to reroll if you get a value twice, which begins to get annoying as you exhaust values. I thought, there has to be a better way.

In computer programs, the usual way of doing this would be to shuffle your list, and pick the first however many items. A lot of languages will have a library method you can call, and if not, the algorithm for a uniform shuffle is not complicated. But, I was using paper, pencil, and dice. Could I figure out a good method for a uniform shuffle using those tools?

The Method

Start by listing your items, in any order.

A
B
C
D
E
F
G

Next, roll a die for each item on the list and write down the result.

A    3
B    1
C    5
D    3
E    3
F    1
G    2

Continue this process until you have generated a unique number for each item on the list.

A    345
B    165
C    551
D    326
E    323
F    111
G    214

You can now sort the list using these randomly generated numbers, and you'll have a randomly shuffled list.

F    111
B    165
G    214
E    323
D    326
A    345
C    551

For a slightly more efficient method, you can continue to only generate digits for items on the list that have the same value. In the above example the generated numbers might look like this instead.

A    34
B    16
C    5
D    326
E    323
F    11
G    2

From here, you can sort lexicographically by the generated numbers.

Analysis

I've done some very basic Monte Carlo simulations, and if your goal is to shuffle a list, this method does seem to require fewer rolls than the naive method of rerolling. However, the improved efficiency is small-ish. To make things easy on myself, I simulated shuffling a 20 item list using a 20 sided die. The break even point, where it was more efficient to reroll was around 17. That is, if you're selecting fewer than 17 items off the list, you're likely better off selecting and rerolling, rather than shuffling the whole list.

Another drawback is that it becomes unwieldy if the list is too long. In the case of Root, the largest table you would need to sort is a list of eighteen town names. Sorting a typical table of one hundred items would be pretty tedious. However, this can be mitigated a bit by rolling a large number of dice at the same time.

So, while the utility of this method is somewhat limited, it does still have some nice properties. This should give you a statistically uniform random shuffle, where all permutations are equally likely to occur. Off the top of my head, it should even give you a statistically random shuffle if your dice are biased in some way. Another very nice property is that it works with any size list, and any size die.

In conclusion, all I really did here was nerd snipe myself with a fun little problem. 

You should use passkeys, but you should understand them first

If you've already heard of passkeys, you probably know that they are the technology that is supposed to replace passwords. But if you're not sure what passkeys are, or how they work, or how they're better than or different from passwords, don't get down on yourself. Most of the websites promoting passkeys do a terrible job of explaining them. I didn't understand them myself, so I decided to finally dig in and learn how they work. Now that I have a better understanding of passkeys, I can see how they fix certain problems with passwords. And I'd like to help you understand them, too.

One of the reasons I think most explanations of passkeys are confusing is that they fail to distinguish between two different aspects of how passkeys work, the authentication process, and key management. There are a couple prerequisites to understand the rest of this post. You will need to know just a bare minimum about how public and private keys work. You will also need to be familiar with password managers.

How does a password work?

Before we jump into explaining passkeys, it will be useful to review how passwords work. We'll break down passwords into the same two parts, authentication with passwords, and password management. Once we have passwords explained within this framework, understanding passkeys should be pretty straight forward.

Authentication with passwords

Alice decides that she wants to create an account on bob.com.

Alice: I'd like an account, please.
bob.com: Please give me a username and a password.
Alice: OK. I'd like my username to be "xXx4l1c3xXx" and password "hunter2".
bob.com: Great. You now have an account on bob.com.

Now that Alice has an account, what does the login flow look like?

Alice: I'd like to log in, please.
bob.com: OK. What is your username.
Alice: xXx4l1c3xXx
bob.com: OK. If you can prove to me you know the password for xXx4l1c3xXx, I will log you in.
Alice: My password is hunter2.
bob.com: Great. You're logged in.

This is the basic authentication flow for logging in with a password. There shouldn't be anything surprising here. One of the problems with this type of authentication is that to verify Alice's password, the website needs to know her password. This means, if an attacker gets ahold of bob.com's database, there is a possibility that they could discover Alice's password, and use it to take over her account. As we'll see later, passkeys solve this problem.

Password management

Now that Alice has created an account on bob.com, Alice has to keep track of that password somehow. She has a several options available to her. She could simply remember the password. She could write the password down on paper somewhere. She could use a password manager, like 1Password or BitWarden.

If you pay attention to these things, you probably know that using a password manager is the recommended method of keeping track of your passwords. If you rely on remembering your passwords, you are likely to take shortcuts like reusing passwords across multiple websites. This is insecure, because if an attacker gets your password from one website, they might be able to take over your account on other websites.

Writing passwords down can be insecure, because anyone with physical access to your password notebook will be able to compromise your account. A password manager stores your passwords in an encrypted format, to prevent unauthorized access. Password managers have other features to improve security, like helping you create a strong and unique password for each of your online accounts. There's a lot more to be said here, but there are many other good articles covering the benefits of using a password manager. If you don't already use a password manager, I encourage you to start.

How does a passkey work?

We'll follow roughly the same script with passkeys as we did with passwords, so you can see the similarities and differences between the two technologies.

Authentication with passkeys

Alice decides that she wants to create an account on bob.com.

Alice: I'd like an account, please.
bob.com: Please give me a username and a public key.

Alice generates a new public/private key pair locally on her computer.

Alice: I'd like my username to be "xXx4l1c3xXx", and here's my public key.
bob.com: Great. You now have an account on bob.com

Now that Alice has an account, what does the login flow look like?

Alice: I'd like to log in, please.
bob.com: OK. What is your username.
Alice: xXx4l1c3xXx
bob.com: OK. If you can prove to me you know the private key for xXx4l1c3xXx, I will log you in. Here is a blob of data. Please sign it with the private key and send it back to me.
Alice: OK, here's the blob of data with a digital signature.
bob.com: I've used the public key for xXx4l1c3xXx to verify the signature. You're logged in.

If you're familiar with how private and public keys work, this should be pretty simple to understand. For those not familiar, a digital signature is a way to prove you have the private key for a given public key. Bob.com challenges Alice to provide a valid signature, and if she can, she proves she has the private key she generated when creating the account.

One of the big benefits here is that the website only knows Alice's public key. If someone compromises bob.com's database and gets ahold of Alice's account information, there is no way for them to use the public key to log in to her account. To compromise Alice's account, they would have to get her private key, which she never shared with bob.com.

Passkey management

This is where, I think, things differ quite a lot from how passwords work. Instead of having to keep track of a relatively short bit of text, like "hunter2", you have to keep track of a cryptographic key that is something like a kilobyte of random-seeming data. It's not feasible for Alice to remember her private key, or write it down in a notebook somewhere. Even if it were feasible to remember the key, you have to use the key to calculate a digital signature in order to log in. That's not something you can really do by hand. If you use a passkey, you must use something like a password manager to store the key, and generate digital signatures.

This is, in my opinion, the biggest factor that improves security for the average user. You must use some sort of passkey manager. Since every passkey user uses a passkey manager of some kind, secure procedures can be programmed into the passkey managers to prevent attacks like phishing. You know that blob of data that bob.com sends to you and asks you to sign? Your passkey manager can check whether that blob of data actually came from bob.com. If Alice accidentally finds herself on evil-bob.com, a phishing website, and tries to log in, her passkey manager will see that evil-bob.com is not bob.com, and refuse to sign the request.

Most mainstream password managers, such as 1Password and BitWarden, already support the use of passkeys. If you are interested in trying out passkeys, I recommend using one of these password managers to experiment with passkeys. Before messing with login credentials for one of your real accounts, try creating an account on a passkey demo website, like passkeys.io. Passkeys.io just consists of a login screen, and nothing else, so you can safely experiment with creating an account and logging in.

In terms of using your password manager to log in with a passkey, the user experience is most similar to logging in with a password using the auto-fill feature of your password manager. On a website's login screen, you will click the "login with a passkey" button, unlock your password manager, select which account you want to log in with, then the password manager will perform the cryptographic operations outlined earlier in this post to complete the login process.

What's the deal with bluetooth/biometrics/MFA/etc.?

Lots of videos about passkeys make a big deal about logging in with your fingerprint, or connecting your phone to your laptop with bluetooth. Why haven't I mentioned any of that yet? Because they are not strictly necessary. Not necessarily a bad idea, but not central to how passkeys work.

Earlier, I said passkeys force you to use "something like a password manager." There are actually a number of different options for storing and managing your private keys. The technical term here is "authenticator." "Authenticator" is an umbrella term that just means, "the thing that stores your keys, and creates digital signatures." A password manager is just one specific style of authenticator.

Lately, operating systems have begun to offer built-in authenticators to manage your passkeys. These have pros and cons. For example, they may store your passkey in a special bit of secure hardware, but then you may not be able to copy that key to be used on another device. This is why if you store a passkey in this way on your phone, in order to log in on your laptop, your laptop and phone have to talk to each other over bluetooth. This offers a higher level of security, but less convenience, and maybe the danger of losing your passkeys if something happens to your phone. I won't go into much more depth here, because I don't feel I have a good enough understanding to talk about this without misspeaking. The pros and cons of different types of authenticators is also worth a whole article on its own.

If this last section of the post is at all confusing, don't worry too much about it right now. The main point here is that, for the most part, what kind of authenticator you use is up to you. If you want to try out using passkeys, start by using a password manager. While there are pros and cons to different kinds of authenticators, at the very least, using passkeys with a password manager is probably a step up from using passwords with a password manager. And it's definitely a step up from not using a password manager at all. Once you're comfortable with using passkeys with a password manager, start looking into the other types of authenticators and see if they're right for you.

At the very least, I hope this post helped you understand passkeys a little better. And now that you understand passkeys, and see how they can keep your accounts safe, maybe you'll give them a try.

Ironsworn - Handling Combat with Multiple Foes

Ironsworn is a table top role playing game that takes heavy inspiration from the family of games known as Powered by the Apocalypse. Compared to more well known games, like Dungeons and Dragons, these games are based on simpler, more abstract game mechanics with the intent of allowing more narrative freedom, and allowing narrative decisions to be the primary driving factor of the game.

Combat is one example of where Ironsworn's mechanics are more abstract than other games. Many table top games use hit points to determine who wins a combat. When someone has zero hit points, they die, and combat is over. In Ironsworn, only the player characters have hit points, which are called "health". Combat with an enemy is instead modeled using what's known as a progress track.

A progress track is ten boxes. As combat proceeds, you fill in the boxes of the progress track when you successfully hit your enemy. A progress track during combat could look something like this.

To end combat, you make what is known as a progress roll. You roll two d10s, or ten-sided dice, and compare each of them to the number of fully filled boxes. In the above image, there are six boxes that have been fully filled, so this track has six progress. If both d10s are less than your progress, that is known as a strong hit. If only one d10 is less than your progress, that's called a weak hit. If neither d10 is less than your progress, that's a miss. This is known as the End the Fight move, and it has the following outcomes.

On a strong hit, this foe is no longer in the fight. They are killed, out of action, flee, or surrender as appropriate to the situation and your intent (Ask the Oracle if unsure).

On a weak hit, as above, but you must also choose one.

• It’s worse than you thought: Endure Harm.
• You are overcome: Endure Stress.
• Your victory is short-lived: A new danger or foe appears, or an existing danger worsens.
• You suffer collateral damage: Something of value is lost or broken, or someone important must pay the cost.
• You’ll pay for it: An objective falls out of reach.
• Others won’t forget: You are marked for vengeance.

On a miss, you have lost this fight. Pay the Price.

To summarize, on a strong or weak hit, you win, on a miss, you lose.

This is all very straight forward when the combat is effectively one-on-one. When you roll your dice to end the fight, the fight is over one way or another. But combat isn't always so simple. What happens when you have more than one player character, and more than one enemy?

Let's say our two player characters, Alice and Bob, are fighting two bad guys, Xena and Yondu. When there are multiple enemies, you can assign each enemy a progress track. This results in one combat with two progress tracks. We'll fast forward through the combat to where both Xena's and Yondu's progress tracks are somewhat full, and Alice tries to end the fight with Xena.

Alice will roll her progress move, and the result will be a strong hit, weak hit or miss. On a strong hit or weak hit, the outcome is fairly straight forward, "this foe is no longer in the fight." Xena is incapacitated in some way, and the fight continues with Alice and Bob versus Yondu.

But what happens if Alice rolls a miss? The rules say, "On a miss, you have lost this fight." Who is "you" and what exactly does "this fight" mean? Does that mean Alice is out of the fight and the fight continues with Bob vs. Xena and Yondu? Does Bob then get a second chance to end the fight against Xena? Fortunately, Shawn Tomkin, the author of Ironsworn, has answered this on Twitter.

When you End the Fight against a progress track, that track is done hit or miss. If it's a miss, you'll need to decide if it also means an end to to the larger scene represented by any other tracks, or if that PC is out of the fight, etc.

— Shawn Tomkin (@ShawnTomkin) July 9, 2020

What this means is that the only thing the progress roll concretely determines is Xena's ultimate fate in this fight. If Alice rolls a miss, it means Xena must escape from this fight victorious in some manner. All options are on the table with respect to what happens to Alice in this moment. Also, it's possible for combat to continue, and either Alice or Bob can eventually try to end the fight with Yondu, as well.

In many of my conversations discussing this problem, many people suggest grouping the multiple enemies together and representing them with one progress track. Ironsworn explicitly allows this, and calls this a pack of enemies. This will often be the right thing to do at the table, but all it does is side step the issue of dealing with multiple progress tracks in a single combat. Since Ironsworn allows for the possibility of multiple progress tracks, it's important to explore and understand fully how that will work, even if it's rarely encountered in the game.

There are Three Actions!

In the rule books for Fate Core and Fate Accelerated, they list four actions: Overcome, Create an Advantage, Attack and Defend. If you look closely, one of these things is not like the other. The first three actions are all proactive, and happen as a result of a character declaring that they do something. The Defend action is always reactive, and only happens in response to an Attack, or Create an Advantage. Defend has an additional quirk in that it cannot be used to oppose an Overcome action. The equivalent would be providing "active opposition" to an Overcome. But couldn't we colloquially call that a sort of defense?

Fate is meant to be a quick, streamlined system, and it is, but I think we can do a bit better. This blog post is not intended as a change to the rules of Fate. Rather, this should be viewed as a reorganization of the mechanics that surround rolling dice to make them a bit more straight forward. If this reorganization makes sense to you, go ahead and use it. If this makes things more confusing, then disregard it.

The Core SRD states...

You’ll notice that the defend action has outcomes that mirror some of the outcomes in attack and create an advantage. For example, it says that when you tie a defense, you grant your opponent a boost. Under attack, it says that when you tie, you receive a boost.

That doesn’t mean the attacker gets two boosts—it’s the same result, just from two different points of view. It was written that way so that the results were consistent when you looked up the rule, regardless of what action you took.

This is my main motivation in reorganizing how Defend works. I've seen this cause at least a little bit of confusion for people new to Fate. By eliminating Defend as a first class action, we can unify these two different views of the Attack action, and make it look similar to any other opposed roll.

However, there is one small wrinkle that we have to deal with first. The Attack and Defend actions each have four outcomes, but they do not match up one-to-one.

Attack Shifts	Attack Outcome	Defend Outcome
+3 or more	Success with Style	Failure
+1, +2	Success	Failure
+0	Tie	Tie
-1, -2	Failure	Success
-3 or more	Failure	Success with Style

If an Attack fails, it's possible for the Defend action to either succeed, or succeed with style. If we're going to combine these into a single table of outcomes, we're going to need one more possible outcome beyond the standard four. Just as we have success with style which is an amped up version of success, we will need an amped up version of failure. Let's call it a dramatic failure. That gives us this table.

Shifts	Attack Outcome	Mechanical Result
+3 or more	Success with Style	You have the option of reducing the result by two shifts and taking a boost.
+1, +2	Success	The target of your attack must absorb the shifts as stress or consequences or be taken out.
+0	Tie	You gain a boost.
-1, -2	Failure	The target of your attack avoids any stress or consequences.
-3 or more	Dramatic Failure	The target of your attack gains a boost.

Now, all an Attack action has is "active opposition" just like an Overcome.

We can do the same thing with Create and Advantage. A dramatic failure is what happens when the Create an Advantage fails, and the Defend succeeds with style. Failure to Create an Advantage creates the aspect, but gives your opponent a free invoke. Succeeding with style on a Defend grants the opponent a boost. To my mind, it doesn't make much sense to create a new aspect, then also create a separate boost. It's much simpler to grant an extra free invoke to the opposition. So, we end up with the following outcomes.

Shifts	CaA Outcome	Mechanical Result
+3 or more	Success with Style	Create an aspect with two free invokes.
+1, +2	Success	Create an aspect with one free invoke.
+0	Tie	You gain a boost.
-1, -2	Failure	Create the aspect with one free invoke for the opposition.
-3 or more	Dramatic Failure	Create the aspect with two free invokes for the opposition.

It's possible I'm misinterpreting things here, so if you like, you can make a dramatic failure have the same outcome as a failure. Since the goal here is to not change the rules of the game, dramatically failing on an Overcome action would have the same mechanical outcome as a normal failure. Or, you could apply the Silver Rule and grant the opposition a boost if it makes sense.

At this point, we've eliminated the Defend action entirely and replaced it with active opposition. Now, each of the three actions, Overcome, Create and Advantage and Attack, have five outcomes, and can go up against active or passive opposition.

The Core rule book doesn't cover what it might mean to have passive opposition to an Attack. What might that look like? When would it be appropriate to invoke the Silver Rule and make that happen? Perhaps someone is trapped behind an armored door, and during a conflict you're trying to break it open to free them. The obvious approach might be to make the door a scene aspect and make an Overcome roll to open it, but what if the door is really strong, and you want to heighten the drama by making it take extra effort to open. You could give the door a stress track, and a passive opposition to attacks. If it has stress boxes of 2 and 4, then a single attack dealing 5 shifts would take out the door. Or, two attacks of 3 shifts would take it out, or three attacks of 1 shift.

I hope this has been helpful, or at the very least, thought provoking.

Doing NaNoWriMo my own way

NaNoWriMo is something I've been vaguely aware of for several years now. I've seen it mentioned online, and my brother even participated in it once.

If you're not familiar with NaNoWriMo, it stands for National Novel Writing Month. The goal of the event is to write about 1600 words every day during the month of November. If you keep up your pace, you will have written a 50,000 word novel by the end of the month.

I've never had a huge appetite for literature. I rarely make it past the first hundred pages of a book, and have very little interest in writing fiction. But I do program. And there are projects that I've wanted to work on, but never gotten around to. So, instead of writing a novel, I'm going to spend every day in November working on a programming project.

Introducing, HamBot.

HamBot will be a Twitch chat bot intended to be run from a Raspberry Pi on your home network.

Twitch chat bots come in two basic flavors. There are chat bots like the StreamLabs chat bot that you run from your personal computer. The other flavor is a bot hosted and run by other people, like NightBot. The benefit of a hosted bot is that it is always on, even when you are not streaming. The downside is that you relinquish a lot of control. A streamer friend complained to me recently that the chat bot she uses has no way to export data, such as channel quotes or stream currency (fake internet points by viewers the longer they watch the stream).

HamBot's goal is to provide the benefits of a hosted solution, while leaving the streamer in full control of their chat bot. HamBot will be "hosted" on an inexpensive Raspberry Pi that a streamer can connect to their home router, do a bit of configuration, and then leave on 24/7.

The main design problem here will be to make installation and administration user friendly to the average streamer. This is the main thing I intend to solve by the end of November. HamBot itself will not have many advanced features. Those are fairly easy to add once the basic installation problem has been solved.

If you like, you can follow along here: https://github.com/haydenmuhl/hambot

Fate and the Elusive Mental Conflict

This post assumes familiarity with the Fate role-playing game. The rules are available to read online for free if you'd like to learn more about it.

One part of Fate that has never sat well with me is mental conflicts. I love that the game supports a combat mechanic besides the typical brawl, but I've never been able to figure out where it would actually fit in to a game. Even when watching examples of mental conflicts in actual play videos, they felt off in a way I couldn't put my finger on, until recently. I think the key to all this is that we're applying the wrong mechanic. Instead of using conflicts, we should be using contests.

Let's look at a concrete example. Reddit user ParamedicAntic posted a thread with an example of a mental conflict between Spider-Man and Aunt May. The background is, Peter agreed to volunteer at the soup kitchen with Aunt May, then forgot and promised Mary Jane that he would spend time with her. Aunt May calls Peter to ask where he is, and the conflict ensues as Peter tries to get out of his obligation at the soup kitchen.

Right away, something feels wrong. As this phone conversation drags on, Spider-Man is going to be filling up his stress and consequence boxes as Aunt May guilts him into coming to the soup kitchen. Those consequences are the same consequences that would get filled if Spider-Man were in a fist fight with the Sandman or Doc Ock. This seems entirely incongruous. How could a phone conversation with Aunt May be as damaging or debilitating as getting body slammed by a super villain?

The short answer is, it wouldn't be, and we can turn to the rules to see why. Here's how the Fate Core rule book describes a conflict.

In a conflict, characters are actively trying to harm one another. It could be a fist fight, a shootout, or a sword duel. It could also be a tough interrogation, a psychic assault, or a shouting match with a loved one. As long as the characters involved have both the intent and the ability to harm one another, then you’re in a conflict scene.

That last sentence is the key. The characters involved need to have "both the intent and ability to harm one another" for this to be a conflict. I don't think Aunt May wants to hurt Peter. She just wants him to come help her at the soup kitchen. Peter doesn't want to hurt Aunt May, either. He just wants to go spend time with Mary Jane. No intent to harm means it's not a conflict.

So, let's look at contests instead.

Whenever two or more characters have mutually exclusive goals, but they aren’t trying to harm each other directly, they’re in a contest. Arm wrestling matches, races or other sports competitions, and public debates are all good examples of contests.

This really describes the situation perfectly. Aunt May and Peter have mutually exclusive goals (where Peter will spend the day), and they aren't trying to hurt each other.

If that's the case, then what is a mental conflict? The key ingredient is intent to harm. This could take a lot of different forms. The most obvious would be a direct insult ("You're ugly"). Maybe it's a lie ("I never loved you"). Maybe it's the truth ("I am your father"). Maybe it's poking an old wound ("It's your fault your partner died"). It could be destroying a beloved object ("No, not my collector's edition Fallout bobble head!").

I think the neat thing about this is that it also removes the need to strictly divide mental and physical conflicts. In the middle of a fist fight, you could decide to smash the bobble head instead of going for another punch. You could also have a conflict between something like a barbarian and a politician where one side is physical and the other side is mental. The barbarian is trying to smash his opponent's face, but the politician attacks by saying things like, "Your friends are already dead and it's your fault."

I think the culprit here is the use of the word "conflict." In colloquial terms, Aunt May and Spider-Man are absolutely in conflict with each other. But they're not in a Fate conflict, because they lack the intent to harm one another. I think by carefully inspecting the characters' motivations, it will allow us to better utilize the contest mechanic, and have richer conflicts by including mental or psychological attacks into what might otherwise be entirely physical brawl.

D&D 5e: What does the d20 do?

The main use of the twenty sided die in Dungeons and Dragons is to determine whether something does or does not happen. A d20 roll would determine the answer to these questions:

• I shoot my bow at the dragon. Do I hit it?
• I try to scale the wall of the castle. Do I climb it successfully?
• The vampire tries to charm me. Do I resist the effect and retain my wits?

Now, there is a bit of nuance beyond simply using the d20 to answer yes/no questions. Each of these three examples represents one of the three different types of rolls you will make with your d20: attack rolls, ability checks and saving throws.

So, what's the difference between these three types of rolls? They apply in different circumstances.

Attack Rolls

Attack rolls are the easiest to understand. You make an attack roll when you are trying to physically hurt someone else. Trying to stab a goblin with a dagger? Attack roll. Trying to shoot a giant spider with a crossbow? Attack roll.

Some spells spells also require you to make an attack roll to see if you hit. The spell will say if that's the case. If the spell doesn't mention an attack roll, then the spell automatically hits.

Ability Checks

Ability checks are when your character is trying to accomplish a goal. Trying to push over a statue? Athletics check. Trying to follow the tracks of an owlbear? Survival check. Trying to stabilize a fallen comrade? Medicine check. Trying to threaten information out of someone? Intimidation check.

Saving Throws

Saving throws are when your character is trying to avoid a negative consequence. The negative consequence could be any number of things. Perhaps you've accidentally set off a trap, and you're trying to avoid getting caught in its steel jaws. Perhaps a medusa tried to turn you to stone, and you're trying to resist the effect. Perhaps you're walking through a desert and you're trying to resist the exhaustion of not having enough water. Perhaps you are mortally wounded, and you're trying to stave off death itself.

In each of these situations, you're trying to avoid something. Each of these will call for a saving throw.

For many spells that do not require attack rolls, instead, the target of the spell will have to make a saving throw. Spells that have an area of effect tend to work this way. Just like with attack rolls, the spell will explain who needs to make what kind of saving throw.

The Yelverton

I was playing computer games and drinking whiskey gingers one weekend, when I ran out of ginger beer. I needed something else to mix with my whiskey. Of all the things I had on hand, Earl Grey tea was the least crazy. I gave it a shot (ha!), and it ended up being pretty amazing.

Here are the official ingredients of a Yelverton:

• Tea, Earl Grey, hot
• Irish whiskey

I realize I'm not the first person to come up with this, but I liked it enough, I decided it needed a name. After some digging around, I finally happened across the Wikipedia page of the Yelverton case. The Yelverton case was an important legal dispute in the 19th century that helped lead to the legal recognition of Irish and English intermarriage. Seemed fitting, given the ingredients.

Hollywood doesn't know how to computer

I thought I would share a funny clip from "Law and Order: SVU" I found.

In this clip, computer tech Reuben Morales shows detectives Benson and Stabler how he discovered a hidden message on a flash drive belonging to a pedophile. He finds "computer code hidden in a pixel" of a picture of a rainbow. He "cracks" the computer code to find a "hidden file" with thousands of pornographic images. In other pixels, he finds PDFs listing the names of the people in the pictures.

What's so disappointing about this scene is that the writers were a hair's breadth away from real methods for hiding information. There is a form of steganography where you use the low order bit of each pixel to hide a message. In an uncompressed image using 24-bit color, each pixel is encoded with three bytes, one byte each for red, green and blue. The human eye is not sensitive enough to distinguish colors that are adjacent to each other in this color space. That means an image with a message encoded into the lowest bit of each byte should not look strange when viewing it in a normal image viewer.

If the writers had consulted an actual engineer, they could have made some very minor tweaks to make that scene actually make sense. First, the hidden message should have been spread across multiple pixels. Steganography works by breaking up the secret message into tiny parts and sprinkling it throughout whatever message you're hiding your payload in.

The next mistake they made was to say that the thousands of images were actually stored within the one rainbow picture. One large image could probably hold a fair amount of data, but you are not going to hide a thousand images inside one image (let alone one pixel). It would have made more sense to hide something like a cryptographic key. Cryptographic keys are on the order of a couple hundred bytes and could easily be hidden, even in very small images. The cryptographic key could then be used to decrypt a hidden volume containing all the images and PDFs.

There you have it. Two small changes that could have made the world of difference. The writers could have even thrown in the word steganography to make themselves look extra smart. Instead, we have this.

Fixing a bonehead mistake in Solr

I was poking around in one of our Solr cores at work when I got this output from a query.

{
  "responseHeader": {
    "status": 0,
    "QTime": 248,
    "params": {
      "indent": "true",
      "q": "*:*",
      "_": "1391802519673",
      "wt": "json"
    }
  },
  "response": {
    "numFound": 36529751,
    "start": 0,
    "docs": [
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3304997"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645477"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645478"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645479"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645480"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3496486"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645481"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645482"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645484"
      },
      {
        "userId": "ERROR:SCHEMA-INDEX-MISMATCH,stringValue=3645485"
      }
    ]
  }
}

The reason for the error is that I reworked the schema of the core. I changed this field from a string to a long, and I forgot to delete all the existing records before reindexing.

Oops.

Okay, so how to fix it? I was able to determine that searching on the userId field with a numerical value would not return any of the corrupted records. A query like userId:[0 TO *] would select all valid records and exclude all corrupted records. I could invert that by doing *:* -userId:[0 TO *] to select all the corrupted records. A quick delete by query, and all the corrupted records disappeared.

Orange-ginger cranberry sauce

I think a lot of people don't realize how easy it is to make cranberry sauce from scratch. Here is my paraphrase of the cranberry sauce recipe that you will find on most packages of fresh cranberries.

• 1 pound fresh cranberries
• 1 cup sugar
• 1 cup water

1. Combine all ingredients in a sauce pan.
2. Simmer until it looks like cranberry sauce.

This recipe is foolproof and will result in a solid, tasty cranberry sauce. However, it can be improved upon. I've been experimenting for the past few years, and I've finally hit on a really wonderful cranberry sauce recipe. It is a bit more involved, but I think it is well worth it.

• 1 pound fresh cranberries
• 3/4 cup sugar
• 1 orange
• 1/2 cup boiling water
• 1 tablespoon grated fresh ginger

1. Steep the grated ginger in the boiling water for 5 minutes. Strain the ginger and discard. Reserve the ginger water.
2. Zest and juice the orange. Combine the orange juice with the ginger water. If the combined liquids are less than 1 cup in total, add water to bring it to 1 cup.
3. Combine the orange zest, orange juice mixture, sugar and cranberries in a sauce pan.
4. Simmer until it looks like cranberry sauce.

The addition of the orange and the ginger make a subtle, but tangible difference in the flavor of the sauce. The orange-ginger sauce has a brighter and tangier flavor. In a side by side comparison, most people should be able to tell that there is something different about the sauce, but I think it would take a discerning palate to be able to identify the specific flavors.

In my recipe, I've cut the sugar a bit, because I enjoy a tart cranberry sauce. This can be adjusted to taste. Steeping the ginger is a trick I learned from making ginger ale at home. I really wanted the fresh ginger flavor, but didn't want fibrous bits of ginger mixed into the sauce itself. The extra step of making a sort of ginger tea accomplishes this with minimal extra effort.

Losing is Fun: A minimal tutorial for maximum Fun

Dwarf Fortress is an incredible game, but the menu system presents a significant hurdle for newbies. I recently got started and had to rely on the wealth of information available at the Dwarf Fortress Wiki, but in the end I think I regret using it too much.

The motto of Dwarf Fortress is "Losing is Fun." You cannot "win" this game. Your fortress will fall eventually. Seeing how your fortress falls is all part of the Fun of Dwarf Fortress. This way, you learn from your mistakes, so hopefully each fortress will be less disastrous more spectacular than the last. If you read too much about game mechanics before you start playing, you miss a lot of this Fun. This tutorial is meant to give you a minimal boost, to get you over the initial non-Fun of learning how to navigate the arcane set of menus, without giving away any Fun ruining spoilers.

Just to give you a taste of some of the problems with the menu system, scrolling through menu options is very inconsistent and haphazard. Sometimes you use arrow keys. Sometimes you use the number pad. Sometimes you use (+) and (-). Sometimes you use (u, h, k, m). You will have to pay attention to the on screen instructions for using each menu.

Worldgen

The first step in Dwarf Fortress is creating the world your dwarves are going to inhabit. Select the Create New World! option. The world generation menu is pretty straight forward. To begin with, use the default settings. World generation takes a few minutes to complete, so go look at cat pictures or something while your computer does its thing.

World generation is a one time thing. When your first fortress falls, don't generate a new world. Just set up a new fortress somewhere else in the same world. One of the coolest aspects of Dwarf Fortress is that the world is persistent, and incredibly detailed. That means that you can go back later to reclaim the ruins of an old fortress.

Embark!

Embarking just means choosing where to stake your claim. Select the Start Playing menu, and the Dwarf Fortress option. These menus are pretty straight forward, too. Use the commands across the bottom of your screen to select a location.

There are a couple keys to finding a good site. You want a site rich in raw materials, like wood, rock, metals and animals. Aquifers are bad. Flux is good. Once you've found a place that looks good you can Embark (e). Learning where to embark is Fun.

Once you have embarked, you will see a screen full of incomprehensible characters. You can get information about what each symbol means by using the Look (k) command. When you place the cursor over a square of the map, you will see information about what is occupying that square on the right hand side of your screen. Take some time to get a basic idea of what your surroundings look like.

If you ever get lost somewhere in the menu system, just keep hitting Esc repeatedly until you get back to the main screen. If you hit Esc too many times, it will just toggle between the main screen and the options menu.

To avoid ambiguity, all menu options will be given as a series of keystrokes as if you were navigating there from the main screen.

Strike the Earth!

One of the most important activities is mining. To start mining, open the Designation menu and select Mine (d, d). Use the arrow keys to mark sections of the map you would like to excavate. Parts of the map that you can mine are going to be solid black. If you don't see any solid black areas of the map, skip ahead to the section on Z-Levels, then come back here.

If you accidentally mark an area for excavation that you didn't mean to, you can use the Remove Designation (d, x) option to unmark these areas. When you unpause the game (space bar), your dwarves will get to work carrying out your wishes.

You should notice that while marking places for excavation, you never issued an order to a dwarf. In Dwarf Fortress, you only have indirect control over your dwarves. All you can do is issue a general order that this or that should be done. If a dwarf with that particular skill is available, then he or she will do the job. If no dwarf has the skill you need, then the job doesn't get done. This puts Dwarf Fortress about half way between a game like SimCity and The Sims. SimCity does not simulate the actions of individual people. The Sims does, but you have to micromanage every action that your Sims take. The game play of Dwarf Fortress presents some interesting challenges, because your dwarves will sometimes act in Fun and unpredictable ways.

Buildings

One of the more confusing things about Dwarf Fortress is what does and does not count as a "building". Things like tables and chairs count as "buildings", and are in the same menu as wells and bridges. Even more confusing is the error message you get when you try to build some of these "buildings". If you open up the Building menu and try to "build" a table (b, t), you will get the error message "Needs table". WTF does that mean?

For an object like a table, "building" the table really means placing a fully constructed table somewhere for use. Before you can place a table somewhere for use, you must "construct" the table in the first place.

Some of the most important buildings in the game are Workshops (b, w). Workshops are where your dwarves turn raw materials into useful objects. You will need workshops, but figuring out which workshops you need, and for what can lead to a lot of Fun.

Most buildings don't do anything on their own. In order for them to be useful, you have to designate tasks to be carried out by your dwarves at the buildings. You can interact with a building using the Set Building Tasks/Prefs command (q). In this mode, when you move your cursor near a building, you will get a menu of what you can do with that building. This will be very important with your workshops early in the game.

Z-Levels

The world of Dwarf Fortress is a three dimensional one. The map that the game presents to you is really just a horizontal cross section of this three dimensional world. One single cross section is called a Z-level. That's because typically a flat plane is represented with two coordinates, X and Y. Three dimensions are represented by X, Y and Z, where Z denotes the vertical dimension. I like to think of Z-levels as the pictures that an MRI or CT scan produces. Horizontal cross sections that you have to visualize stacked on top of each other.

To navigate down to lower Z-levels use the (>) key. To navigate to higher Z-levels use the (<) key. In order to dig between Z-levels, you will need to construct stairs or ramps. The various flavors of stairs and ramps can be found in the Designations menu along side the Mine command. These will need to be placed correctly in order for your dwarves to gain access to other Z-levels. You should experiment and have some Fun with this.

Miscellaneous Tips and Hints

Here are a couple more menus you should familiarize yourself with early on. Zones (i) and Stockpiles (p) are important. Play around with them to see what they do. Create a stockpile and see how your dwarves react to it. If it didn't seem to do anything, try creating a different type of stockpile. Do the same with zones.

The View Units (v) menu is also very important. In this mode, when you move your cursor near a creature, you will see some of the creatures stats and characteristics. Of particular importance is the Labor menu (v, p, l). It lets you designate which types of tasks a particular dwarf will perform.

My last advice is to not get too frustrated. Remember, "Losing is Fun." If your fortress falls, just start a new one. In my own process of learning the game, I try to focus on learning one thing at a time. For example, focus on how to acquire a particular raw material. Once you've acquired the raw material, see if you can figure out what that raw material is useful for. Nearly everything in this game has a use of some type.

On to the Fun

That should be enough information to at least get you started. I've deliberately left out a lot of key information that will hopefully result in a lot of Fun in your early fortresses. Once you've learned where to embark and familiarized yourself with the menus in this tutorial, you should be able to put together a fairly successful fortress. The key is to learn from your mistakes so you have a completely new and unexpected type of Fun in your next fortress.

To recap, these are the key menus you need to be familiar with to get your first fortress off (in?) the ground.

• Look (k) - See what stuff is on a particular tile.
• Designations (d) - Important commands like Mine can be found here
• Building (b) - Used to erect buildings and place furniture around your fortress
• Set Building Tasks/Prefs (q) - Interact with finished buildings
• Zones (i) - Designate areas for certain uses
• Stockpiles (p) - Designate areas for certain other uses
• View (v) - View and set your dwarves' characteristics

And finally, access the third dimension by navigating Z-levels using (<) and (>).

Have Fun. :-)

Compiling a custom dictionary for Kuromoji and Solr

The user dictionary functionality of Solr's Kuromoji tokenizer is extremely useful and easy to use, but it isn't always the right tool for the job. In my case, I'm migrating our system off of the MeCab tokenizer. MeCab also allows you customize the tokenization, but the two models are completely different. In Kuromoji's user dictionary, you take an untokenized phrase and provide the custom tokenization. In MeCab, you just supply a list of words to augment its dictionary. The only way to migrate MeCab's custom dictionary to Kuromoji's user dictionary is by hand.

Fortunately, Kuromoji uses the same base data set as MeCab to build its statistical model for tokenization, and all the data in the base data set is in the same format as the custom MeCab dictionary. Getting Kuromoji to use the custom MeCab dictionary just requires recompiling Kuromoji's dictionary. Figuring out how to do this was surprisingly painless.

In order to compile your new dictionary, you will need...

1. A copy of the MeCab-IPADIC data
2. A copy of the Solr source code
3. A Solr distribution of the same version as your source code
4. A servlet container in which to run Solr

Download MeCab-IPADIC

A tarball of the MeCab dictionary can be downloaded from SourceForge at the following link.

http://sourceforge.net/projects/mecab/files/mecab-ipadic/2.7.0-20070801/

Unpack the tarball to a directory of your choice. From now on I will be referring to this directory as the "dictionary source" directory, or as $DICTSRC in code examples. If you look inside the dictionary source directory, you will see several CSV files. These files use the EUC-JP character encoding scheme. Any custom dictionary will need to be in the same format.

If you open up one of the CSV files, you will see something like this.

いっぽう,555,555,5224,接続詞,*,*,*,*,*,いっぽう,イッポウ,イッポー

そもそも,555,555,4784,接続詞,*,*,*,*,*,そもそも,ソモソモ,ソモソモ

では,555,555,5262,接続詞,*,*,*,*,*,では,デハ,デワ

そういや,555,555,5420,接続詞,*,*,*,*,*,そういや,ソウイヤ,ソーイヤ

かたや,555,555,5368,接続詞,*,*,*,*,*,かたや,カタヤ,カタヤ

The data in each field is roughly as follows.

Field 1 - A word to be used for tokenization

Field 2 - Left cost

Field 3 - Right cost

Field 4 - Word cost

Fields 5-10 - Part of speech

Field 11 - Base form

Field 12 - Reading

Field 13 - Pronunciation

Fields 2, 3, and 4 have to do with the statistical model for tokenization. For the purposes of constructing your custom dictionary, treat fields 2 and 3 as magic numbers mapping to part of speech. Column 4 is the "cost" of the word itself. The lower the cost of the word, the more likely it is to be used in a tokenization. Fields 5-10 should be copied from the appropriate MeCab CSV files. I don't know enough about Japanese to know the differences between fields 11, 12, and 13.

Once you have your custom dictionary ready, drop it into the dictionary source directory along with the rest of the MeCab CSV files.

Set up Solr

Set up your servlet container and deploy the Solr WAR file. Make sure that your servlet container expands the war file so that you can access its contents. The expanded Solr webapp directory will be referred to as $WEBAPP. If the directory $WEBAPP/WEB-INF/classes does not exist, create it.

Open a terminal and find the Solr source code you downloaded. This directory will be referred to as $SOLRSRC. Run the following commands.

> cd $SOLRSRC/lucene/analysis/kuromoji

> ant compile-tools

Compile your dictionary

At this point, we should have everything necessary to compile the custom dictionary. Run the following commands.

> cd $SOLRSRC/lucene/build/analysis/kuromoji/classes/tools/
> java -cp ".:$WEBAPP/WEB-INF/lib/*" \
org.apache.lucene.analysis.ja.util.DictionaryBuilder \
ipadic $DICTSRC $WEBAPP/WEB-INF/classes euc-jp false

Once this completes, you can inspect the files that it created in $WEBAPP/WEB-INF/classes. There will be a deep hierarchy of directories, and then nine binary files that make up your dictionary. One of the JAR files in the lib directory contains a set of files with the same names as these, but the Java servlet spec says that the servlet container should first look in the classes directory, then look in the lib directory. Having your dictionary in the classes directory will override the dictionary packaged with your Solr distribution.

You should now have a Solr instance with a custom Japanese dictionary for tokenization. Start up your servlet container and test it out.

Custom Japanese tokenization in Solr 4.0

Solr 4.0 (really, it's been there since 3.6) has a new analysis module for handling Japanese, called Kuromoji. Kuromoji was developed by Atilika, Inc., who donated it to Solr. I don't speak Japanese myself, but I've been doing some preliminary tests with a Japanese coworker, and it seems to work fairly well.

However, it's not perfect. It will miss an occasional phrase, and is especially problematic with domain specific phrases. To get around this, the Japanese tokenizer accepts a user dictionary, where you can list custom tokenizations. Unfortunately, I couldn't find any documentation on the format for the user dictionary. Fortunately, there is a sample user dictionary in the unit tests for the Japanese tokenizer.


# Custom segmentation for long entries
日本経済新聞,日本 経済 新聞,ニホン ケイザイ シンブン,カスタム名詞
関西国際空港,関西 国際 空港,カンサイ コクサイ クウコウ,テスト名詞

# Custom reading for sumo wrestler
朝青龍,朝青龍,アサショウリュウ,カスタム人名

# Silly entry:
abcd,a b cd,foo1 foo2 foo3,bar
abcdefg,ab cd efg,foo1 foo2 foo4,bar


It's a fairly straight forward CSV format. A hash character (#) starts a comment that continues to the end of a line. Empty lines are ignored. Each non-empty line has four fields separated by commas. After some testing, I was able to figure out what each field in the CSV was.

1. Untokenized phrase
2. Tokenized phrase
3. Reading, or pronunciation
4. Part of speech

There are a couple particulars you need to be aware of when putting together your user dictionary.

Every field is required - If you do not have all four fields your core will not load properly.

Tokenized phrase and reading - These fields are lists of words delimited by spaces. It is important that both the tokenized phrase and the reading have the same number of words. If you don't have this, your core will not load properly.

Spaces around commas - The CSV parser is very picky about format. You should never have any spaces surrounding the commas separating fields. Your core may or may not load, but can get other strange errors during tokenization.

I haven't tested this extensively, but I don't believe there is any way to escape a comma or a hash character. The CSV parser will accept fields surrounded by quote marks, but putting a comma or hash inside a quoted string does not seem to change how it is interpreted. Fortunately, this seems like it would be a very rare use case.

Grokking Solr Trie Fields

I've been trying to wrap my head around Solr's trie field types for the past week, and finally made a break through.

Trie

The first thing you need to understand is the idea of a trie data type. Here's a basic outline of the data structure. Let's say you want to index the following list of words.

bad

bag

bar

bin

bit

We can arrange these words in a tree structure as follows.

b--a--d

|  |

|  |--g

|  |

|  \--r

|

\--i--n

   |

   \--t

To reconstruct one of the words you start at the root node of the tree, and work your way towards a leaf node, keeping track of the letters you encounter along the way. Depending on what you're using the trie data structure for, you may store some piece of data in one of the leaf nodes. If you want more information about the trie data structure, I will refer you to the Wikipedia page, which is fairly complete and easy to understand.

Solr's version of the trie

Another term for a trie is a "prefix tree". Solr uses this idea of prefixes to index numbers so that it can perform range queries efficiently. Just like we can organize words into tries, we can also organize numbers into tries.

Let's say I want to index the integer 3735928559. For clarity, let's rewrite that in hexadecimal, 0xDEADBEEF. When we index this using a TrieIntField, Solr stores the integer four times at different levels of precision.

0xDE000000

0xDEAD0000

0xDEADBE00

0xDEADBEEF

What Solr is doing here is constructing numbers with different length prefixes. This would be equivalent to a trie with this structure.

DE--AD--BE--EF

The reason that this allows for fast range queries is because of what the prefixes represent. The prefixes represent a range of values. It might be better to think of them indexed like this, instead.

0xDExxxxxx

0xDEADxxxx

0xDEADBExx

0xDEADBEEF

Each "x" represents an unset digit. That means the entry 0xDEADxxxx represents every number from 0xDEAD0000 to 0xDEADFFFF. You can get a better feel for this if you play around in the analysis section of the Solr admin console.

Precision Step

The option to set the precision step was the part that I understood the least. The available documentation is rather dense and unhelpful. The precision step lets you tune your index, trading range query speed for index size. A smaller precision step will result in a larger index and faster range queries. A larger precision step will result in a smaller index and slower range queries.

In the example above, I was using a precision step of 8, the default. What the precision step means is how many bits get pruned off the end of the number. Let's see what would happen if we indexed 0xDEADBEEF with a precision step of 12.

0xDExxxxxx

0xDEADBxxx

0xDEADBEEF

And here with a precision step of 4.

0xDxxxxxxx

0xDExxxxxx

0xDEAxxxxx

0xDEADxxxx

0xDEADBxxx

0xDEADBExx

0xDEADBEEx

0xDEADBEEF

As you can see, compared to the default precision step of 8, a precision step of 4 doubled the number of entries in the index. The way it speeds up range searches is by allowing better granularity. If I wanted to search for the documents matching the range 0xDEADBEE0 to 0xDEADBEEF with the default precision step, I would have to check all 16 records in the index and merge the results. With the precision step of 4, I can check the one record for 0xDEADBEEx and get the results I want.

That's a bit of a cherry picked example, but arbitrary range queries will be faster. How that works is left as an exercise for the reader.

May 5, 2015 - I originally thought that the trie data type was not supported directly by Lucene, but this is incorrect. Tokenization of numeric types into the various prefixes is the default behavior of Lucene when indexing numbers.

Custom Solr token filter factories with arguments

Many of the token filter factories, tokenizer factories, and char filter factories that come bundled with Solr accept parameters from a schema.xml. The documentation for writing your own filters and tokenizers doesn't include any details for how to access these parameters, but it's pretty easy to figure out by inspecting the source code for one of the included factories.

The MappingCharFilterFactory takes a path to a file as a parameter. The Javadoc for the MappingCharFilterFactory shows the declaration to put in schema.xml.

<charFilter class="solr.MappingCharFilterFactory" mapping="mapping.txt"/>

In the source code for the MappingCharFilterFactory we can find the following line.

mapping = args.get("mapping"); 

Looking through the class hierarchy, all token filter factories, tokenizer factories, and char filter factories are descendants of AbstractAnalysisFactory where args is declared as a protected variable. All you have to do access the parameters passed from schema.xml is access the args map. args can also be accessed via the getArgs() function.

Solr 4.0 and the BaseTokenFilterFactory

At work, we're upgrading from an ancient version of Lucene to the shiny new Solr 4.0. Unfortunately, the documentation on the Lucene wiki hasn't quite caught up with the most recent version of the software. I would fix omissions like this as I found them, but the wiki does not seem to accept public edits.

There were three classes in Solr 3.6 for creating custom analyzers. Those classes were the BaseCharFilterFactory, BaseTokenizerFactory, and the BaseTokenFilterFactory. These three classes were in the documented package, org.apache.solr.analysis, through Solr 4.0 ALPHA, but as of the BETA release, they have been moved and renamed.

In Solr 4.0, the new classes are the CharFilterFactory, TokenizerFactory, and TokenFilterFactory. They can be found in the org.apache.lucene.analysis.util package, which is part of Lucene's analyzers-common project

Handy links:

• Javadocs
• Source code

Thanks to comment 7 for pointing this out.

Close, but no cigar

Anita Sarkeesian is the author of Feminist Frequency, a blog where she writes and makes videos about the portrayal of women in popular culture. She has made a couple of posts analyzing movies using the Bechdel Test. The Bechdel Test first appeared in the comic Dykes to Watch Out For by Alison Bechdel. The test lays out three simple rules as follows. To pass the test, a movie must...

1. Have two female characters...
2. Who talk to each other...
3. About something other than a man.

The good parts

In Sarkeesian's latest post about the Bechdel test, The Oscars and the Bechdel Test, she uses the test on the 2011 Oscar nominees. On the whole, Sarkeesian does a good job of analyzing the movies and applying the test in a sensible manner. For example, she notes that the Bechdel Test was not originally conceived of as a serious metric.

Let’s remember that this was made as a bit of a joke to make fun of the fact that there are so few movies with significant female characters in them. The reason the test has become so important in recent years is because it actually does highlight a serious and ongoing problem within the entertainment industry.

I also agree with her analysis of how application of the Bechdel Test can be useful.

Again, to be clear this test does not gauge the quality of a film, it doesn’t determine whether a film is feminist or not, and it doesn’t even determine whether a film is woman centered. Some pretty awful movies including ones that have stereotypical and/or sexist representations of women might pass the test with flying colours. Where really well made films that I would highly recommend might not.

She goes on to note that the Bechdel Test is most informative used in aggregate when applied to a group of films. Her choice to use the 2011 Oscar nominees is also good, as it lessens the chance of selection bias.

The Rest

Unfortunately, with all the good things she has to say, her post has one major flaw that undermines any conclusions that can be drawn from her analysis.

In response to the Bechdel Test, I’m often asked, well, what about the reverse? “Why isn’t there also a test to determine if two men talk to each other about something other then a woman”. The answer to that is simple, the test is meant to indicate a problem, and there isn’t a problem with a lack of men interacting with one another.  The Bechdel test is useful because it can point out an institutional pattern and since there’s no problem with men and men’s stories being underrepresented in films, the reverse test is not useful or relevant.

Her dismissal of a Reverse Bechdel Test is very misguided. In fact, not only is the Reverse Bechdel Test relevant, I'll go even further and say that the Bechdel Test is useless without it. To demonstrate this, let me give you a similarly flawed analysis of labor statistics.

Historically, women have been under represented in technical positions, such as engineers and medical doctors. Unfortunately, these problems persist even today. According to the United States Bureau of Labor Statistics, in 2011 there were only 198,000 female software developers in the United States. There are similarly paltry numbers in psychology, with only 140,000 female psychologists during 2011.

Anyone should be able to see the obvious flaw in this paragraph. I've omitted the number of men working in these disciplines. Let's apply the same logic here that Sarkeesian used to dismiss the Reverse Bechdel Test.

What about the number of men in these disciplines? The answer to that is simple, these statistics are meant to indicate a problem, and there isn't a problem with lack of men in these fields. These statistics are useful because it can point out an institutional pattern, and since there's no problem with men being underrepresented in these fields, the number of men in these fields is not useful or relevant.

Unfortunately, this reasoning fails to support its conclusions when you look at all the relevant data. It is true that women are underrepresented among software developers. Compared to the 198,000 women working as software developers, there are over 840,000 men working as software developers. However, it is not the case at all that women are underrepresented among psychologists. While there are 140,000 female psychologists, there are only 56,000 male psychologists. That comes to women making up 19% and 71% of these fields respectively.

"Ah, ha!" you might say, "But Sarkeesian has already accounted for this. She notes that 2 out of 9 movies clearly pass the Bechdel test. That's only 22%."

The problem here is that she is comparing the wrong things. That 22% is a ratio between those movies that pass the test and those that do not. This would be equivalent to comparing the number of women who are psychologists and the number that are not. Of course, this is silly, which is why we compare the number of psychologists that are women to the number of psychologists that are men. Similarly, to make sense of the Bechdel Test, we need to compare the number of movies that pass the test against the number of movies that pass same test with the genders reversed.

If you are still not conviced that the Reverse Bechdel Test is relevant, then I have one simple question for you. What percentage of movies should pass the Bechdel Test, and how do you arrive at that number?

Postscript

For the sake of clarity, I'd like to follow up with a couple points.

First, the two employment statistics I selected were clearly cherry picked. I selected one where women were in the clear minority, and another where they were in the clear majority. This was so I could demonstrate that while a flawed analysis can't affirm a position, neither can it disprove it either. My use of these statistics should not be misconstrued to say anything about representation of women in the work force in general. If you look at all the statistics, it's clear that women are still underrepresented in STEM fields. It certainly took a while for me to find a suitable statistic with women in the majority.

Second, this post is only to point out that Sarkeesian's conclusion is unsupported by her methods, not that her conclusion is necessarily wrong. In fact, I expect that her conclusion is entirely correct. However, without a proper analysis we have no way to accurately assess whether progress towards equality is being made, and if so, how much. We also won't have a good way of determining when the problem has been fixed.

Update: It seems I'm not the first to notice this problem. Ryan over at Mad Art Lab already covered this several months ago.

Another shell script to share

At home I get a lot of use out of the tree command line utility. It gives me a quick and easy way to look at a nested directory structure without having to leave the command line. The computers at work don't have the tree utility, and every so often I really miss it.

So, I wrote my own.

Here's a bash script that is a simplified version of the tree utility.

#!/bin/bash

tree() {
    local prefix=$1
    local dir=$2
    local count=`ls -l $dir | wc -l`
 
    if [[ $count -eq 0 ]]
    then
        return
    fi
 
    local i=1
    local bar="|"
    local nextPrefix="|   "
 
    for file in "$dir"/*
    do
        i=$(($i + 1))
        if [[ $i -eq $count ]]
        then
            bar="\`"
            nextPrefix="    "
        fi
        filename=$(basename $file)
        echo "$prefix$bar---$filename"
        if [[ -d $file ]]
        then
            tree "$prefix$nextPrefix" $file
        fi
    done
}


if [[ -z $1 ]]
then
    dir=`pwd`
else
    dir=$1
fi

if [[ ! -e $dir ]]
then
    echo "Directory $dir does not exist"
    exit 1
elif [[ ! -d $dir ]]
then
    echo "$dir is not a directory"
    exit 2
fi

basename $dir
tree "" $dir

Back to school

I've started taking classes as part of the Embedded Systems Engineering certificate offered through UC Irvine Extension. Just last week I finished up my first course in the certificate program. It was the requisite software engineering course that I imagine every such program has. Overall, the course was fairly dull, and I can't say I got much out of it.

The deliverables for the course consisted of a five question multiple choice quiz every week, and four larger assignments. Two of these assignments were research papers, which were little more than book reports based on our assigned reading. The other two assignments were demonstrations of the Hatley-Pirbhai Methodology (HPM). HPM is mostly just a repackaged waterfall workflow, but with a requirements document following a specific structure. None of these were particularly interesting, challenging or fun.

Although the course was rather disappointing on the whole, I can't say I got nothing out of it. Much of the required reading had very little to do with software engineering and instead was more a survey of common hardware found in embedded systems. Not having an extensive background in hardware, there was a lot of new information for me. I now have a much better appreciation for things like system bus protocols, and the details of how DMA works. This was also my first exposure to a digital signal processor architecture, when previously I only was familiar with MIPS and x86 type instruction sets.

Unfortunately, I only got to read about all this, and not actually get my hands dirty, but that's going to change. My second class* starts up this week, which is an intro to embedded programming, and my dev board just arrived in the mail. I haven't had a chance to play with it very much, but I can already tell this class is going to be much better than the last. The AVR board we are using has fun blinky LEDs, but sadly no piezo buzzer to annoy the roommates with.

* You may think it's odd to have the first class in a curriculum to be software engineering, and you would be right. My "first" and "second" classes should have been reversed in order. I ended up taking them out of order because I started the program at an odd time with regards to class schedules. In the end, I think this will turn out for the best. I have accidentally eaten my vegetables first, which means now there's nothing left for me but dessert.