Fairune

I beat this Android game app called Fairune yesterday. There's actually a 3DS version (which has some extra stuff), but the app was free so I went with that.

It's worth mentioning for a couple of reasons. First, it was pretty cool. It's a simplistic adventure game, in which battle takes place by simply touching enemies. If they're too strong, you'll take damage and bounce off. If they're weaker than you, they'll be defeated but give you no experience. If they're evenly matched or a bit stronger, you'll defeat them and take some damage yourself, and you'll gain experience points, which eventually raise the amount of health you have and allow you to fight stronger monsters. It's mostly a puzzle game, where you find items and figure out how to use them to advance. It has retro-style graphics and sound, and amusing-looking enemies.

The second reason is that my daughter is a huge fan. She doesn't like video games in general, but this one is fairly adorable. I think the narrator at the start hooked her with this proclamation: "Even monsters won't attack girls in cute dresses!" What's not to like?

There were a few times I had to look up what to do online. None of these situations were necessarily unreasonable, but you really have to pay attention to the pixel art to catch some of the clues. The boss battles gave me trouble also. It would have been much easier on the 3DS (i.e. with a real controller); it was hard to have precise timing with the onscreen buttons. But it was pretty satisfying when I beat it.

Please don't ask how you're supposed to pronounce the title.

Non-stupid dragon rider travel algorithm

I'm not a fan of Eragon - see the Books page for details. One (not the largest) of my complaints involves a moment where a couple of people (or maybe three) have a horse to carry their baggage, and of course they're traveling with a dragon. Since the dragon can't carry everyone, they decide to walk from one town to a distant one.

Stupid.

Of course the most straightforward thing would be for the dragon to carry one person (or however much she can carry) in one trip, then return for the next load, and so forth. Presumably a dragon could make several trips between towns in less time than it could take a person to walk. But for some reason I found myself thinking a little harder about this - specifically, how to optimize things for the shortest possible trip.

I started with a few constraints, which may or may not be valid in the book, but that's fine. For the sake of simplicity, let's say that on a given trip the dragon can carry one human, or all of the luggage, or the horse. (Granted, the horse would weigh more than two humans, so the dragon should be able to carry them both, but maybe the humans don't feel comfortable being dangled by just one set of claws or something. Or maybe the dragon can't carry the horse, but that makes this problem less interesting.) Another possible constraint is to ensure that you don't leave the luggage or the horse unattended. If it's okay to leave the luggage alone, and if there are two humans, then we have a fairly simple way of shortening the time even more:

1. The dragon carries the luggage to the end point. At the same time, one human starts off on the horse while the other starts walking.
2. When the dragon drops off the luggage, it returns to pick up the walking human. 
3. The dragon drops the human off with the luggage and returns for the horse. (By this time, the horse and remaining human have covered a lot of distance, so the dragon doesn't have nearly as far to go.)
4. The dragon drops off the horse and goes back for the final human.

We can optimize things a little further, because at step 3, the dragon doesn't have to carry the human all the way to the luggage - just close enough that the human can reach it before the final trip is over.
It might be possible to advance things even further,  if we can assume that extra trips for the dragon are offset by less time spent with a human on foot. At step 3, the dragon drops the first human off at an even farther distance from the end. Then at step 4, the dragon carries the horse from the second person to the first, then goes back for the second person. This way, more time is spent with the slowest traveler on horseback rather than walking. Like I said, this might (depending on relative speeds and distances) offset the need for some extra partial trips for the dragon.

Things get even more complex if we add the constraint that the luggage must always be in the company of a human or dragon. (Maybe there are lots of thieves around.) In this case, the luggage becomes the limiting factor. Again, assuming two humans:

1. The dragon takes human #1 far ahead, but not quite to the goal. The human starts walking. At the same time, the other human begins walking the the laden horse.
2. The dragon takes the luggage to human #1's position. That human must now stop. But human #2 can now ride the horse and move faster.
3. The dragon takes the horse to human #1, who can now move. Human #2 continues on foot.
4. The dragon takes human #2 very near the end point
5. The dragon takes the luggage to the end point, arriving at the same time as human #2. Human #1 can now ride.
6. The dragon takes the horse to the end point. (Unfortunately, the horse's extra speed is now wasted.)
7. The dragon takes human #1 to the end point.

Again, we might be able to optimize this by having the drop-off point for the luggage at step 5 some distance from the end point. That way human #2 can continue with the horse and luggage while the dragon goes back for human #1. But this would also mean that the human is stationary in-between receiving the luggage and receiving the horse, which might offset this. Of course, adding a third person would really free things up and allow the horse to continue running right up until the end, similar to the first scenario. (Although of course that would also add additional trips.)

You'll notice that I've left the math out of this completely, which is why it's not possible to come up with a definitive optimal solution. I guess this would be a good interview question if math were relevant. Maybe someday I'll write a program to simulate the situation - it would be pretty cool to have little icons representing the different elements and let you tell the dragon which thing to pick up and when to drop off. In the meantime, though, please don't make stupid choices like walking somewhere you're in a hurry to get to when there's fast and free transportation available.

Return of the King

[Spoiler alerts] I finished reading Return of the King the other day. (Well I've read it before of course, but not in the last fifteen years or so.) It's pretty epic. By this point, I guess I know Tolkien's world well enough that even the rambling details seemed pretty relevant to me this time through. And again, the parts about Mordor seemed extremely vivid to me. I think that's because the experience that Sam in particular goes there resonates with me. He doesn't do very many things that are outright heroic, other than fighting off Shelob (which was in the previous book), but the author switches to Sam's perspective for that journey and makes it clear that his constant dedication to Frodo is as much a pillar of the quest's success as anything else. Not surprising that I would connect with the consistent, loyal guy more than the dynamic warriors and royalty that make up the other plot line - I guess most people would, and that's probably intentional on the author's part. In addition to Sam as character, the journey through Mordor itself is a lot like life I think. You keep putting putting one foot in front of another, half the time not necessarily knowing where you're headed or what you'll do when you get there. (Fortunately Frodo did have some sense of direction for most of the time he was conscious.) Sometimes you only succeed because things have been arranged for you (like Sam rescuing Frodo from the Cirith Ungol tower). Sometimes your trials are what propel you forward, like how Golumn covers the Hobbits' tracks so the orcs can't follow. Somehow things are just outright painful for no good reason, but you keep moving forward anyway. And while Frodo and Sam get rescued by eagles when their work is done, the book still would have been valid (if not as satisfying) if they had perished in the eruption of Mount Doom, because they succeeded. I guess it's also relevant that following their world-changing feats, most of the characters end up going back to normal life. Fortunately they're humble enough to see the value in that rather than trying to live in the past and make everyone see them for what they have accomplished. The ending is really wistful and poignant and all that stuff. I know the "Scouring of the Shire" bit was cut from the movies because it was deemed anti-climactic (not to mention time), but it really does a lot to tie things back together, showing how the Hobbit characters have changed, and that Hobbits in general have character even when things aren't peaceful. Incidentally, it's also the part about Sam that I relate to least, in some ways (besides gardening) - that he becomes a leader as restoring the Shire becomes the new quest. It's fitting that the book ends with him coming home to his family, since I guess the point of any defensive war: to make sure that families can raise children in peace. But more than that, the reader once again connects with Sam in that the epic journey and magical world have passed for him, and the reader has to close the book and go back to the real world. I guess I can't really say I've finished the book, since I think the chronology in the appendix is nice - I remember it telling how the different characters visit each other and stuff. Not to mention that it once again underscores the fact that Tolkien had a whole world apart from the story. It's amazing. Go read it if you haven't already.