A Tale of Two Languages

Recently I was talking to a colleague who is still in school and he mentioned a new blog post he had written about string search. He had implemented a brute force search and so I told him about faster algorithms that he should consider, specifically mentioning the Knuth-Morris-Pratt algorithm. He read up on it at Wikipedia and wrote a Perl implementation, but when we ran it I was shocked to discover that KMP was significantly slower than brute force! This made no sense. Further experimentation showed that Perl’s index function was even faster still!

When I wrote up an implementation of KMP and brute force in C, I got results that were in line with my expectations: KMP in C was much faster than brute force.

So what is going on?

What’s happening is a result of the way Perl implements it’s data types. They do not, after all, correspond to the primitive types available in C/C++, Java, or other languages. In particular a Perl “array” is actually a complex data structure that is manipulated by a set of non-trivial functions, while a string is a less complex (though still complex in it’s own right) structure, so it really makes sense that string processing would be faster than array processing in Perl. Furthermore, Perl’s index function implements the Boyer-Moore string search algorithm, which is even faster than KMP, so the speed of the index function should come as no real surprise.

The take away lesson here is that even when you know of a good algorithm for solving a problem, you should not rush to write it up. A lot of very smart people have spent their time creating and fine tuning the languages and libraries that we use, so it is quite likely that someone has already done the work you need, and there may be a better alternative to your own solution built right in to your language. Check it out before wasting your time reinventing the wheel!

Update, August 18, 2015

There is actually a second lesson here, which may be even more important. Just because the language you are using gives you a data structure that has an array like interface, that doesn’t mean it is actually an array, and if it isn’t an actual array, then standard algorithmic analysis techniques may not apply to it! This is the case for Perl’s “arrays”, and also for lists in Python, Lisp, and other languages. This is why KMP is slower than brute force in Perl: the assumptions made in the standard analysis of the algorithms is that we are working with real arrays – a group of primitive data elements stored in contiguous locations in memory which guarantees us constant time lookup of any arbitrary data element with a very small time per operation. Perl arrays fail on all counts, here.

kmp.c – Test program in C.
kmp.pl – Test program in Perl.
A Tale of Two Cities – Some sample data for searching.

Interview Questions: Call by reference and call by value

A common simple interview question is to explain the difference between “call by value” and “call by reference”. This refers to the way arguments are passed to functions.

In call by value, a copy of the argument is made and given to the function so that any changes made to the argument affect only the function itself. Once the function returns, the original variable passed as the argument is unchanged.

void foo ( int x ) {
    x = x + 1;
    printf( "In foo x is now %d\n", x );

int a = 0;
printf( "Before foo a is %d\n", a );
foo( a );
printf( "After foo a is %d\n", a );


This code snippet will produce the following output:

Before foo a is 0
In foo x is now 1
After foo a is 0

The value of a is unchanged because a is passed by value, and in the function foo(), x merely holds a copy of the value of a so that changes to x do not affect a.

Call by reference does things differently, however. In call by reference, the function argument refers to the exact same variable as the one passed by the caller, so changes made in the function are visible to the caller.

void foo ( int &x ) {
    x = x + 1;
    printf( "In foo x is now %d\n", x );

int a = 0;
printf( "Before foo a is %d\n", a );
foo( a );
printf( "After foo a is %d\n", a );


This code snippet will produce the following output:

Before foo a is 0
In foo x is now 1
After foo a is 1

Notice the subtle change to the definition of foo(). Now the argument is defined as “int &x“. In C++ this tells the compiler that the argument is a reference parameter instead of a value parameter. Therefore x becomes an alias for a when we call foo()

Different languages support different conventions. C++, for example, supports both call by value (the default) and call by reference (when you define an argument as a reference parameter as I did in the second example above). C, on the other hand, is purely call by value. To achieve the effect of call by reference in C you have to declare your argument as a pointer to something, in which case the pointer is passed by value, but you can dereference the pointer to change the thing it points at.

void foo ( int *x ) {
    *x = *x + 1;
    printf( "In foo *x is now %d\n", *x );

int a = 0;
printf( "Before foo a is %d\n", a );
foo( &a );
printf( "After foo a is %d\n", a );


Before foo a is 0
In foo x is now 1
After foo a is 1

Again, this is actually an example of call by value – x contains a memory address that is a copy of the address of a and if you change x then you are only changing what x points to – a is unchanged, and so is it’s address in memory. Some people refer to this idiom as “call by pointer”, though in my opinion that is really a misnomer since the language is not actually providing you with another calling convention, rather you are simply using a programming idiom to achieve the affect you want.

There are languages that are neither call by reference nor call by value. Python, for instance. You can read a nice writeup about that in “Is Python call-by-value or call-by-reference? Neither.

Perl is an interesting case to me in that it is actually a call by reference language, but the most idiomatic way of using it makes it seem like it is call by value. Consider the following sample.

sub foo {
    my $x = shift;
    $x = $x + 1;
    print "In foo $x\n";

my $a = 0;
print "Before foo $a\n";
print "After foo $a\n";


This produces the following output, which makes it look like Perl is passing the argument by value.

Before foo 0
In foo 1
After foo 0

But what is really going on is that you, the programmer, are making a copy of the argument as the first thing in your function. The line my $x = shift; actually makes a copy of the first element of the @_ argument array (and removes the first element afterwards). Look what happens when you avoid the shift:

sub foo {
    $_[0] = $_[0] + 1;
    print "In foo ".$_[0]."\n";

my $a = 0;
print "Before foo $a\n";
print "After foo $a\n";


Before foo 0
In foo 1
After foo 1

Now it is clear that Perl is really passing the variable $a by reference.

Interview Questions: Detecting Palindromes

This problem is almost too simple to mention, but it has actually been asked of me in an interview, so I’ll go ahead and address it.

Problem: detect if a given string is a palindrome. Be sure to ignore case, spaces, and punctuation characters.

Solution: Start by setting references to the first and last characters. Now while the two references don’t cross each other, compare the characters at each reference, being sure to skip over any non alphabetic characters, and to ensure both characters are compared using the same case. Here’s a worked solution in C++ that takes both null terminated strings and C++ string objects.

#include <cstring>
#include <cctype>
#include <iostream>
#include <string>

bool is_palindrome( const char *s ) {
    const char * first = s;
    const char * last = s + strlen(s)1;
    while ( first < last ) {
        while ( ! isalpha( *first ) && *first != 0 )
        while ( ! isalpha( *last ) && last >= s )
        if ( toupper( *first ) != toupper( *last ) ) {
            return false;
    return true;

bool is_palindrome( std::string s ) {
    return is_palindrome( s.c_str() );

int main ( int argc, char **argv ) {
    for ( int i = 1; i < argc; ++i ) {
        std::string s(argv[1]);
        std::cout << is_palindrome( s ) << std::endl;

    return 0;


There’s not much to say about this. It is O(N) in running time and O(1) in space (unless you have an older C++ compiler, where it could be O(N) in space when called on a string object due to the way std::string::c_str() works).

Any professional programmer should be able to write this off the cuff without even thinking about it.

Interview Questions: Two Sum

In interviews for programming positions, it is common for the interviewer to present a small programming problem and see what kind of solution the candidate comes up with. These problems help to reveal how the candidate thinks about solving problems, and also provide a chance to show basic coding competency. These problems can also be fun to work in their own right as exercises in the craft of software design.

The two sum problem is simple version of the more general (and NP complete!) subset sum problem. Two sum can be stated as follows:

Given an input array of numbers, and a target value, find all pairs of numbers in the input which sum to the target value.

There are various solutions possible, of course.  Naively, one might consider iterating over all elements of the array, and for each element, iterating over the other elements to see if the pair add up to the sum. This leads to a solution that runs in O(N2) running time, though, which is clearly not desirable for large inputs.

A first pass at improving the performance would be to consider sorting the data.  We can then use binary search to quickly see if a number’s compliment is also in the set.

Solution: Sort the input data.  For each value in the array, use binary search to see if (target – value) is also in the array, and if so print the pair of numbers.  We need not consider values greater that target/2 since the the data is sorted, and (target – value) would have already been checked.

Time performance is O(N log N) for the lookup, and varies for the sort, though typically it is also O(N log N) giving O(N log N) overall performance. Space complexity if O(1), though, since no extra space is needed for the operations.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
    while ( max >= min ) {
        long mid = min + (max – min) / 2;
        if ( vec[mid] == lookfor )
            return mid;
        else if ( vec[mid] > lookfor )
            max = mid – 1;
            min = mid + 1;
    return -1;

void two_sum( std::vector<long> vec, long target ) {
    std::sort( vec.begin(), vec.end() );

    long lookfor;
    long i = 0;
    while ( vec[i] <= target/2 ) {
        lookfor = target – vec[i];
        long pos = binary_search( vec, lookfor, 0, vec.size()-1 );
        if ( pos != -1 && pos != i ) {
            std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;

int main( int argc, char **argv ) {
    char *endptr = NULL;
    long target = strtol( argv[1], &endptr, 10);

    std::vector<long> vec;
    long num;
    std::string s;

    while ( std::cin >> s ) {
        num = strtol( s.c_str(), &endptr, 10);

    two_sum( vec, target );



This is good, but if we are willing to use more memory, we can improve the speed of processing in a classic time-memory trade off.

Solution: Add the input numbers to a hash with the number as the hash key, and it’s index position in the input as the hash value. For each value in the array, check to see if (target – value) is also in the hash and if so print the pair of numbers.  We need not consider values greater than target/2 since this would generate a duplicate pair when we eventually come across (target – value) itself in the array.

We are using an extra O(N) amount of memory for the hash table, but doing so gives us O(1) lookup time to see if (target – value) is also in the array, so once the hash is built in O(N) time we need only another O(N) amount of time to find all pairs, yielding an overall O(N) running time.

#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

void two_sum( std::vector<long> vec, long target ) {
    std::map<long, long> hash;

    for ( long i=0; i < vec.size(); i++ ) {
        hash[vec[i]] = i;

    long lookfor;
    long i = 0;
    std::map<long, long>::iterator it;
    while ( i < vec.size() ) {
        if ( vec[i] <= target/2 ) {
            lookfor = target – vec[i];
            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).second != i ) ) {
                std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;

int main( int argc, char **argv ) {
    // Same as above.


If you’d rather not read C++, here is a Perl version of the hash based algorithm that stops after finding the first matching pair of numbers.

#!/bin/env perl

use strict;
use warnings;
use Data::Dumper;

# Usage: Pass the target value as a command line option, and the number array as
# values on stdin, one item per line.

my $target = $ARGV[0];
my $lookfor;
my $num;
my $i = 0;
my %h;
while () {
    $num = $_;
    $lookfor = $target$num;
    if ( exists $h{$lookfor} ) {
        print "$num $lookfor (indices $i, ".$h{$lookfor}.")\n";
    $h{$num} = $i;



Shelter 2

I just finished my first play through of Shelter 2 and I’m almost afraid to play it again. It’s a good game, but it hit me emotionally hard and made me cry enough that I don’t want to repeat the experience again too soon. In this game from Might and Delight you play the role of a lynx, and specifically a mother lynx trying to raise her cubs to adulthood. The premise is simple, the game is short, and it’s fairly easy to play, as well, but you will probably at some point find that one or more of your four kittens dies.

I lost 2 of them.

That really hit me hard, especially the first one. I thought I had been doing well – I dutifully hunted rabbits and fed my babies, and when they were old enough to follow me outside, I took them to the river where they could feast on eggs from the nests of ground nesting birds. Everything seemed to be going so well! But I didn’t understand the time scale of the game. I thought I could afford to take a moment to just sit and relax in the sun and watch my precious kittens playing. Then one of them started meowing loudly. I didn’t know what was going on, but I figured we’d had a long day, and I thought the game was about to give us a night cycle, so I started us walking slowly back to our den.

Then one of the kittens collapsed on the ground and could not move. And she was meowing so pitifully! That’s when I realized that she was starving. I panicked! I picked her up by her scruff and started running back towards the den. Then a second kitten collapsed! I didn’t know what to do! I put the first kitten in the den and then ran back to get the second one, and while taking her to the den, a third kitten collapsed. Now I was frantic. With the kittens safely in the den I tore across the fields to where there were rabbits and managed to bring one down quickly and grabbed it to take back to the den, but before I arrived a kitten had died!

I was mortified. I brought two more rabbits to back to feed the rest of the kittens and get them back to health, but after that I was shaken and I had to log out for the night.

Losing that kitten really hurt!

It was a couple of days later before I could bring myself to play the game again, and when I did I was determined to hunt continuously to ensure my familys survival. Unfortunately, the season in the game had cycled back to winter and I chose the wrong place to go hunting. There was no food to be found, and a kitten collapsed from hunger. I picked it up and began racing over to the rabbit fields again where I knew there would at least be something to eat, but on my way there a second kitten collapsed. I could not carry two kittens at once, so I had to make the decision to abandon one of them and hope that I would be able to catch a rabbit and get back to it in time to save it’s life. I failed.

Now I was down to only two kittens, with two of my babies dead. At this point, though, I was surrounded by rabbits, so I began stalking and hunting furiously. I became a killing machine, reaping the lapine community for my own survival and the survival of my family. My remaining kittens grew into cubs. And then they grew more into young adults, which immensely helped, because now they were able to participate in the hunting and help gather food. Together the three of us walked among the rabbits as goddesses of death until one fall day, my cubs grew to maturity. They looked at me with confidence in their eyes, and gratitude, and then they walked off into the wilderness to lead lives of their own.

I returned to the empty den, but I was restless that night, and went in search of a new mate to begin the cycle once again.


This was a short game, but it was really intense! It gave me a sense of the desperation and determination that must come from being a wild animal, constantly struggling to survive. I do look forward to playing again – you get to continue the story by playing your own offspring in the next generation – but the emotional intensity is something that I need to step back from for a bit. I need a breather before I take on the struggle of motherhood once more.

Avatar Wanted: Inquire Within

I’m a long time fan of the Ultima series of games, a really incredible fantasy RPG series from Origin Systems in the 80’s and 90’s These games established many of the conventions of modern computer RPGs, and even spawned the first MMO – Ultima Online. I wrote this brief bit of fan fic as a depiction of the famous character creation scene that started many of the Ultima games, wherein the soon-to-be hero encounters a strange gypsy woman who begins the process of setting the hero’s feet upon the path of virtue. If, like me, you feel a deep sense of nostalgia when you think of these games, then perhaps you will enjoy my writing. And don’t forget to listen to the “familiar tune” the gypsy hums at one point.

“Come in, come in,” she said with a smile. “I was just about to make tea. Would you like to join me?”

The young man looked warily through the curtains at the interior of the gypsy caravan wagon. You expected to see such things at a renaissance faire, but this one had a strangeness to it that set it apart from the others. For one thing it was a real wagon, while the others were obviously decorative affairs set up purely for the tarot card readers and other hucksters working the faire, but this was a proper full sized wagon that could easily be hitched up to a team of horses. It was large, too, perhaps fifteen feet long and six feet wide, with a wooden shell over it giving just enough room to stand up in. There were colorful, gauzy curtains over the entrance in the rear, reached by steps that could be raised up for travel, while heavy canvas was rolled and tied up above the door ready to be let down during bad weather or when the wagon was moving. The outside was painted brightly, like the fake wagons but with much more care and attention to detail, with intricate arabesque patterns bordering each of the wooden panels making up the walls and arched roof.

Inside the wagon there was an explosion of the senses. Old tapestries and decorative fabrics hung from the walls giving the eyes a feast of colors to gorge themselves on, and many fragrant herbs hung drying from the ceiling: lavender, rosemary, juniper, cedar, mints, and peppers hung there among other things more exotic and difficult to identify. On the floor was a worn but soft Persian rug with a delicate tracery of flowers woven into it. There was a low, dark wooden table to one side upon which a cool blue cloth was spread, as well as a small teapot sitting over a candle warmer. Cushions beside the table provided the only places to sit down, and curtains about half way through the wagon obscured the front area.

On one of the cushions, facing the entrance, sat the old woman offering tea. She had a kindly look to her face, but the wrinkles at her eyes showed more than her smile. They seemed to betray years of strain and worry, as if she had long borne some heavy burden that had left its mark upon her. The clothing she wore gave evidence of this too, for while it certainly fit the theme of the renaissance faire, it was obviously well worn everyday wear of a practical nature to this woman, and no mere weekend costume.

The young man looked around for a moment, unsure of himself, but then he blinked and said “I’m sorry, I thought this was one of the attractions. I didn’t know this was your campsite.”

“Oh it’s quite alright” she replied. “I’ll admit I don’t get many visitors coming back to see me, but you’re more than welcome here. I’ll even do a reading for you if you’d like. Why don’t you sit down and chat with me and keep an old woman company for a while?”

Hesitantly he stepped in and sat down on the cushions. “Thank you” he said. “I was hoping to find someone who could tell me my fortune, and I get the feeling that you’re probably the real deal.”

“Oh I am, dearie, you can be sure of that. In fact, I’d like to give you a special reading today, one that I reserve for rare occasions.” She pulled out a deck of tarot cards from a pocket in her dress and began shuffling them as she hummed a familiar tune. He couldn’t name it, but he must have heard it somewhere in the fairgrounds earlier in the day.

As she shuffled she spoke. “I’ll be showing you eight cards. Each card has a story associated with it, but the ending of the story is uncertain. Only you can choose how it ends, and the choices you make will determine your fortune, just as they do it your daily life. Are you ready to begin?”

“I suppose so,” he replied.

The woman turned up the first card: the five of pentacles. “Do you see the man in the card, how he sits upon his chair guarding his wealth? He is a merchant, and he has charged you with delivering a purse of coins to his bank. You know that the coins have not yet been counted so that if a few of them were to be lost no one would ever know of it. Along the way to the bank, you meet a desperately poor man in the streets begging for help. Do you show compassion and give the beggar a coin, or do you honestly deliver the bag intact to the bank?”

The young man sat silently for a moment: this was not the kind of card reading he’d expected. He had certainly never been asked questions like this before. But the old woman had a look in her eyes that was both sincere and … seeking. Yes, she was looking for an answer to something beyond her stated question, and she needed him to help her find it. “I give the beggar a few coins. They won’t be missed.”

“Interesting,” she said. “Oh dear, I mustn’t neglect the teapot!” She reached up and took a pinch of some herb and put it in the pot still warming over the candle.

She drew another card, the five of swords. “This young man seems to be celebrating the defeat of his foes, but now he also bears a burden for it, for he has yet to decide the fate of his mortal enemy of many years who is now disarmed and at his mercy. Should he show compassion and let his enemy live, or slay the foe as expected of a valiant warrior? What would you do?”

“I’m not sure,” said the youth. “I suppose the enemy deserves to die, but I don’t think I could really kill him if he is defenseless like that. I’d let him live I guess.”

“You are very kind hearted I see,” she said while adding another pinch of herbs to the teapot.

The next card drawn was the five of wands, showing five young men fighting each other. The old woman spoke of it. “Your friends are fighting in a close pitched battle, as you see on the card, but your absent lord had ordered that you not join them. What would you do in this circumstance, valorously join the fray knowing you can deny it later, or remain where you are so that you can honestly claim obedience later?”

These questions continued to strike the youth as odd, but he played along anyway. “I would stay out of the battle,” he said. “Honesty is important to me.”

“It is generally a wise policy, of course,” remarked the woman as she placed a bit of a different herb in the teapot. “The fourth card is … the seven of swords. See the man sneaking over the wall? He is your fellow soldier, but during an intense battle you see him desert his post, endangering many lives. But as he flees he is set upon by several enemies. How would you respond to this? Would you let him face them alone knowing that he has met justice for his desertion, or would you risk sacrificing your own life to aid him?”

The young man was starting to feel a little irritated at the unusual card reading and its questions, but he answered quickly anyway. “I would help him. Everyone’s courage fails at some point, but that’s no reason to let him die.”

She smiled warmly as she put another herb in the teapot. By now the steeping leaves were beginning to give off an earthy and pleasant aroma that was quickly filling the small room. It would have been pleasant and relaxing if not for the strange circumstances.

Another card was drawn. “We’re half way done now. Here is the five of cups and you see someone who has lost something and yet retains something as well. It is a bounty hunter who has captured a wanted man, but now the bounty hunter believes the man innocent. What do you think will happen? Will the man go free and the bounty be sacrificed, or will the oath to capture the man be honored? How would you choose if you were the bounty hunter?”

“I’d let him go. I won’t hurt an innocent man.”

“I see that you are a virtuous person,” she responded as she added yet another herb to the teapot, sending more heady fumes into the air.

“That’s quite a strange tea you’re making,” the young man said.

“Yes, I suppose it is. It has plain tea in it, of course, since that’s always a good start, but I like to add a pinch of this and a smidgen of that to give it a nice flavor and scent. It smells lovely already, don’t you think?”

He had to agree that it did, but all he said in reply was “let’s move on.”

“The six of wands. A hero rides triumphantly down the street to the adoration of the crowds, but who is he? It was you who slew a great dragon, but a penniless warrior has stepped forward to claim the reward instead. Do you justly claim the reward yourself, or let the other receive the acclaim while you go about your life with humility?”

The young man finally lost his patience. “Look, these questions don’t make any sense to me. None of the other card readers do this. Why don’t you just do a regular reading like they do?”

The woman gazed at him searchingly for a moment. “Perhaps you are right. Perhaps this is not the kind of reading you need – there are few who really fit it. Would you like me to start over?” She held her hands over the table ready to pick up the cards and begin again, and really the young man wanted to say yes, but looking in her face he could see disappointment and sadness and maybe even a little weariness as if she’d been in this situation many times before. Staring into that face he just could not bring himself to let her down.

“No, let’s keep going. We’re almost done, I suppose. I would claim the reward myself. If I slew the dragon it’s only right that I get the reward.”

With an audible sigh, the woman relaxed and added yet another of her herbs to the bizarre tea she was making.

“Next we have the eight of cups, and a man walking away from his worldly things, for he is on a sacred quest. But when he was younger he pledged to marry his sweetheart, and now she calls for him to uphold his vow and return to her. Does he honor his vow, or does he continue his spiritual crusade?”

The youth paused in thought, for this was not as straightforward he preferred. “I suppose there’s no easy answer here. If he marries her she might then be willing to join his quest, but she might also need him to stay home. If he goes on she might be willing to wait longer for him, but she might not. I think he’d have to go on with his quest and hope for the best.”

“Sometimes that’s all we can do,” she replied and added more the the fuming brew in the pot, it’s odors now permeating everything and beginning to affect the young man – it was such a powerful scent and it made him feel relaxed and a bit drowsy.

“Here is the final card. It is the three of pentacles. Ah, the decisions of a youth in choosing a path in life, much as you face right now. Your parents wish you to become an apprentice and two positions are available. The first is to become a humble cobbler making shoes for your village. The second is to take the vows of a new acolyte in a spiritual order. Which do you choose?”

Slowly the young man blinked as he considered the choices, though really he knew his answer. “I would join the order and take vows. It seems the most balanced way of life to me.”

The woman nodded slowly and smiled as she added one final bit to her teapot.

“Tea’s ready!” she said cheerily and began pouring a cup.

“But what is my fortune?” asked the young man as he fought growing sleepiness.

“Ah, your path lies chosen before you, but it is a path that is fraught with danger and there will be many more choices ahead of you.” She passed him the cup and absent-mindedly he drank deeply from it, the warmth filling his body and the exotic flavors washing over his tongue leaving him with the sensation that he had just tasted another world, and another life.

“Listen carefully to what I now say. As you begin your journey, seek friends and companions – they are there for you – and keep in mind the questions you have heard today and the answers you have given. Let them guide you in a life of virtue.”

He slumped down to the floor and she put a pillow under his head.

“Always keep in mind the principles of truth, love, and courage and they will keep you upon the path of virtue. Mayhap thou wilt even be the avatar we seek.”

And he knew no more on these shores.

Terry Pratchett has died

Today I read with great sorrow that my favorite living author is no longer living. Terry Pratchett, creator of the wonderful, satirical Discworld books has passed on from this turtle to the afterlife. I do hope Death let Terry ride on Binky at the end.

I’ll be wearing lilac (at least in my thoughts) today.

Addendum – if you notice a new response header from my web server, this is what’s going on.


Thirty minutes left before impact. The ship’s main engines had been destroyed when the last of the separatists rammed them in a suicide attack, so there was no hope of repair. The lifeboats were gone – some from getting the passengers off and others from damage during the battle. Now there were a handful of crew members left and no way to get off the doomed vessel as it followed its trajectory according to the inexorable laws of gravity, a course that would see it soon crash into the surface of Mars.

The comm system still worked, though, so the crew had gathered on the bridge to send their final farewells to the relay station in Cydonia. There were five of them there, mostly senior officers, but also a cabin boy. His name was Ibrahim and he was the most out of place among them. He was only 19 and this was just his second voyage as part of the crew. Being attacked by Marsies was not what he’d expected when he signed up to work on a transport ship ferrying people and cargo to and from Earth. He was nervous – the captain could see it in his eyes and his hands were shaking a little bit.

She turned to the view screen. “Are you recording this Cydonia?”

“Roger, Rosy Dawn, you guys can start when you are ready” came the reply.

“My name is Cynthia Fellows, captain of the transport MSS Rosy Dawn, Sirtis registry T75A6N. We were about to leave orbit for Earth when a flight of separatist interceptors decloaked and attacked us. We defeated them after an intense fight, but our damage has left us drifting out of control with a rapidly decaying orbit. Special commendation for specialist Emile LePen who shot down two of the enemy before being killed. Special Commendation for Ibrahim Sawalha who greatly assisted in the orderly evacuation of the passengers and who gave up his own spot on a lifeboat for a fellow crewman. Would you like to go next Ibrahim?”

The young man had looked up when his name was first mentioned and he seemed bewildered at being singled out for special mention like that, but he smiled weakly and seemed to lose some of the nervousness that been haunting him, a small hint of pride creeping over his face instead. “Thank you, Captain”. He faced the view screen.

“My name is Ibrahim Sawalha and I’m just a cabin boy. I haven’t even been part of the crew very long, but it’s been an honor to work here. I’ve learned so much and I really want to move up … ” He paused. “Anyway, Mum, dad, Ayesha, Salah – I love you all. I wish I could come home to you – I even have presents for you from Mars! But now, well, just remember me, OK? Remember the good times, like when we all went to Tahrir for the centenary celebration. Do you remember me carrying you on my shoulders Salah? Do you remember seeing the parade and the fireworks? We had such a good time…”

Executive officer Fergueson spoke up. “You need to keep it short so everyone has a chance to speak, son.”

“Right. Sorry. Well, I love you guys. Always remember that. Allahu Akbar!”

A sandy haired man went next. “I’m the ships purser, Steve Hackett. I can’t say that I ever expected an end like this – I’d always assumed I’d work in merchant shipping another ten years or so and then retire somewhere, but I guess that isn’t meant to be. I don’t really have any family to speak of, but I’d like to send a message to an old friend, Egon Ramis, the supply chief on the USS Lexington. Have a drink for me, Egghead! I’ll miss our next reunion, so I won’t get a chance to have my revenge on you for that last game night. Oh well. Hmmm … I don’t have a will, so I guess give all my money to the ZG Veterans Association. Keep ’em Flying!”

There was a pause. Captain Fellows looked at the chief engineer who was busy working at the navigation console. The captain could guess what she was doing. “Alicia, do you want to go next?”

“I’m busy” came the terse reply.

Fergueson stepped up next. “I am the executive officer of the Rosy Dawn, a position I’ve held for the past 14 months. It has been an honor and privilege to serve with her crew, and with Captain Fellows. To my wife, Stella, all I can say is I love you very much. I’d hoped to see you next month when we reached Earth, but I guess that isn’t happening now. I … really love you.

“Lillian, you be a good girl and take care of yourself. Daddy loves you and I’m really, really sorry about this. I want so much to see you grow up”. His voice became strained. “I want to see you go to school, and grow up and get married, and have children of your own. I just want so much to hold you in my arms right now! Remember me, Lily. Remember Daddy, and take care of Mommy, OK? She’s going to need you to be a big girl now, OK? Bye, bye.”

The XO stepped back. Only the engineer remained, but she was still working furiously at the nav console.

“Alicia?” asked the captain.

“I’m busy. I don’t have anyone to say goodbye to anyway. And I’m busy.”

Captain Fellows looked over the console. It showed the ships current orbit – well it’s descent, really. The ship was already in the upper reaches of the atmosphere and the autopilot had started making slight attitude adjustments to keep the ship from spinning as air resistance tried to turn it. Displayed on the screen were several other courses, too – all of them still crashing, but some faster, some slower, and some at shallower angles.

“What do you have?”

The engineer finally turned around to face the others, the sweat glistening off the dark skin of her forehead. “I’m almost certain we can use the maneuvering thrusters to slow our descent enough to allow us to come down intact. We’ll hit hard, make no mistake, and everyone should be in pressure suits because I’m sure the hull will crack, but I’m also sure we can survive.”

“Those projections on the screen don’t look very survivable.”

“I still haven’t figured out the details. I need just a bit more time. Everyone get suited up while I work it out!”

A voice came over the comm system from Cydonia. “Rosy Dawn, did I hear right? Are you going to try for a soft landing? We’ve got rescue teams standing by.”

Everyone turned to look at the captain with hope and fear on their faces. There were tears in the XO’s eyes, and a terrible sadness in Ibrahim’s face. Only Alicia seemed different, with her fierce and defiant look.

“Yes, Cydonia”, said the Captain, “we are going to try for a soft landing. As soft as can be, at least. Everyone get suited up.”

Four of them left the bridge to go aft to the crew common room, where they normally relaxed when off duty. There was a small galley for preparing snacks and light meals, several entertainment consoles, corridors leading off to other parts of the ship, and here was also where the lifeboats for the bridge crew were accessed. They were gone now, but there were still a few pressure suits in storage lockers next to the boat hatches. Fergueson, Hackett, and Sawalha began suiting up while Captain Fellows took two suits and went back forward into the bridge. She shut the door behind her.

“Tell me what our chance are. Realistically.”

Alicia turned and stared at her captain hard for a moment. “Not good. It’s a long shot. Really long, in fact, but we do have a chance. We lost a lot of forward velocity from maneuvering during the fight, which is why we’re going down in the first place, but if we can kill the rest of our forward v then all we have to worry about is slowing our free fall enough. After that it’s really just a matter of trusting the hull to hold up on impact. It’s not made for it, but it is a good, solid design. We do have a chance!”

The captain had been pulling on the pressure suit while listening – a single piece jumpsuit design with a detachable helmet. The skin of the suit was designed to tighten up once you had everything on and you activated the controls. It wasn’t comfortable or very functional if you had to move around much, but it could save your life in an emergency, and that was all it really needed to do.

Sealing the front of her suit she said “get suited up now and I’ll take the controls and get us slowing down.”

“OK” said Alica as she got up, “just use the forward thrusters to drop as much speed as you can, but watch the fuel gauge. We lost pressure in two tanks during the attack and we’re going to need at least 70% of our remaining reserves for the descent.”

The captain keyed the all-ship intercom “Everyone grab hold of something – I’m about to engage the thrusters and you’ll experience G towards the front of the ship. Once you’re suited up get back to the bridge and strap in to a chair. Thrust in 5… 4… 3… 2… 1… now.”

The forward maneuvering thrusters, normally used only in short bursts to make tiny adjustments in position, now came on at full power and stayed there, pushing the ship backwards to slow it’s speed around the planet. Even though they weren’t made for much force, they still managed to create about 1/4 G, and the crew found themselves using the handholds on the walls as the now climbed “down” into the bridge.

A minute passed. Two. Three. Everyone was seated now except Alicia who was still getting into her suit while working against the oddly directed weight. Finally the captain shut off the thrusters “We’re at the fuel reserve limit now.” Alicia looked at the console – not enough! They still were going a little too fast. At this rate they’d have a ground speed of about 125 km/hr when they touched down. She glanced at the captain who merely gave a little sardonic grin and ordered everyone to get their helmets on and rebreathers activated.

“Eight minutes until we land” she said.

“Land? That sounds optimistic” said Fergueson.

“Maybe it is, but I’ll take it” she replied. There really wasn’t anything to do at this point but hope for a miracle, so she might as well be optimistic no matter what. She turned the ship into a belly flop to maximize their air resistance, and brought the landing thrusters online. These had more kick than the maneuvering thrusters, and the crew found themselves pressed into their seats with more than 1.3 G of force as the thrust reached maximum output. Still, they were coming in awfully fast.

The tension among the crew was palpable as the ship began its final descent. Ibrahim quietly muttered a prayer while the captain piloted the ship and the XO monitored the various status boards. The engineer kept a constant check on the course and made occasional comments to the captain to increase or decrease thrust. The purser sat silently and stared at the cockpit window.

We’re getting a lot of heat buildup in main engineering and on the upper deck” said the XO.

“Not surprising” said Alicia, “we took a lot of damage to those areas in the fight, so there’s bound to be hull damage. I’m sealing the interior bulkheads in case something happens.”

“Has anyone noticed the glow outside the window?” asked the purser. “It almost looks like we’re on fire.”

“Well in a sense we are”, said the captain. “Normally we reenter nice and slow and fly down to the surface under power, but now we’re coming in way too fast and friction is heating up the hull.”

“Is that bad?” he asked nervously.

“Yes, but there’s nothing we can do that we aren’t already doing.”

They were starting to hear noises now too. A rushing sound as air sped past the hull, and metallic groans and strains from the ship itself as it reacted to the unaccustomed stresses of the rapid descent. Suddenly there was a dull crashing noise and the whole ship shuddered as an alarm went off.

“What was that?” asked the purser, a hint of panic in his voice.

The XO replied “we’ve lost atmosphere in the engine room. Bulkheads are holding, though.”

“I guess the cactus on my desk isn’t going to like that” said Alicia.

“That’s not funny” snarled the purser!

“Focus people” ordered the captain. “We’re half way down. What’s our trajectory looking like?”

The engineer looked at the console. “We’re still coming in too fast, forward velocity.”

“OK, I’m going to realign and hit the forward thrusters again.” They felt the forces around them shift again as the ship turned nose first into its dive and the front engines came on again to slow it’s speed.

“What’s that red light?” asked Ibrahim.

“It’s the overheat warning on the forward thrusters” said the XO. “You might want to back off on them, Captain.”

“Keep monitoring them. I need to ride them as long as I can to cut our speed, otherwise…”

There was a flash and boom as something exploded outside on the front of the ship. Everyone was jerked in their seats as the thrusters cut out.

“TF1 is out. TF2 has shut down automatically”. I’ll see if I can override it” said the XO.

“We’re going to die” said the purser quietly, “that’s all there is to it.” He turned and looked at the cabin boy and repeated a little louder “we’re going to die.”

“Shut the fuck up, Steve” said Alicia.

“Don’t worry Mr Hackett” said Ibrahim. “Allah is watching over us and nothing happens save by his will. Put your faith in God and let Him guide us down.”

“Captain, I’ve got a yellow light on 3 of the landing thrusters” said the XO.

“Roger” she replied”. “We’re almost down now.”

“It doesn’t matter because we’re going to die!”

“Shut up, Steve! V 312 vertical, 175 horizontal. Altitude 1.2 klicks.”

“Screw it. Override thruster safeties”

“I don’t want to die!”

“Can it!”

“Ya sin. By the wise Qur’an surely you are one of the Messengers upon the straight path…”

“Thruster TL4 offline. TL5 offline.”

“Brace for impact in 5… 4… 3… 2…”