Fabian huddled in the darkness, hyperventilating through his fist as he tried to calm himself down. He’d found a small alcove after running through the dungeons for what felt like forever. Hopefully, though, he’d not been on the run for more than fifteen minutes. Last time he’d escaped—five years ago—the guard had helped him leave through the front door. It was a different guard now (and Fabian felt a twinge of guilt wondering about the fate of that first kind soul), so the front doors were kind of ruled out this time. Basil and he had both assumed there would be a rear exit somewhere (even dungeons had fire codes, you know) but they hadn’t considered that the dungeon might not be exactly small, nor well-lit.
Fabian cursed between gasps. He had no idea which way he was heading. Even had the halls been lit, he didn’t think he’d have much luck. No wonder his parents had never let the Curmudgeon boys play down here. They’d have never seen them again.
His breathing slowed, and he began listening for footsteps, shouts, any sign of pursuit. Nothing. He began to think that “phase one” of the plan might just have succeeded. That is, if being hopelessly turned around in the dark could qualify as any kind of success.
He told himself he’d have some very earnest words to say to Basil the next time he saw him. Basil’s plan (such as it was) had involved “accidentally” leaving the cell door unlocked, and Fabian subsequently finding his way out. They intended to meet up just outside the mazes in a few days. Knowing that Fabian wouldn’t be able to escape the same way he had before, Basil had started to explain how to summon Nigel—the diminutive demon with a penchant for path-finding—to escort him through the dungeons. He said they should at least get a new contract hammered out.
Only just at that moment the guard had returned, wondering what was keeping the wizard. Basil had tossed a few surprisingly inventive insults at Fabian to reinforce his original reason for visiting, and made his exit, leaving Fabian alone in his cell once more.
Somehow Basil had managed to leave the door unlocked, as promised. Fabian still wasn’t sure how his master had done it, but he had. This meant that the rest was up to Fabian.
So, here he was. In the dark. Lost, in his family’s ancestral dungeons. He’d tried wall-following, once he realized he was getting turned around, but he had a suspicion that it had just led him in circles. He really had no idea where he was now. Hopefully, that meant the guard didn’t know, either.
“Well, Fabian,” he said to himself. “That’s cows for you.”
He realized he was in a fetal position, and slowly uncurled himself to take stock of his situation. He still had his twig, and his wits were slowly returning. Combining the two, the only thing he could think to try was Dijkstra’s…but that required summoning Nigel.
He had no idea if he could do it, but he had to try.
He pulled the battered twig from his pocket and paused, considering. Basil hadn’t ever actually told him how to do the spell, but Fabian had seen it done. True, he’d also seen the illusion spell done, multiple times, and that hadn’t exactly been helpful, but… He racked his brain, trying to recall every detail of the previous summoning. Had Basil used any special wording? Any particular gesture? Fabian didn’t think so.
Which suggested it must work like the illusion spell, in that it simply required you to focus your mind and believe.
Fabian took a deep, resigned breath and exhaled slowly. Then, twig held before him (though it was so dark he couldn’t even see that much), he pictured Nigel as he remembered him: small, pink, and floral. He focused on the name. He concentrated on his need. He brought it all together in one spot in his mind, one clear spot on his mental desk, and nailed it down firmly with a quick flick of his twig.
Nothing. And then—
There was a boom, a flash of red light that felt like it was going to sear his eyes, and then the hallway was flooded with that familiar acrid smoke. He choked, waving the smoke away, desperately trying to listen to see if the thunder had summoned more than the demon. Like, for instance, the guard.
All he heard, though, was a voice. A familiar, deep, grating voice, which boomed to beat the thunder and seemed to fill the entire dungeon with echoes.
“WHO SUMMONS ME? ANSWER, MORTAL, OR FEEL MY WRATH!”
“Shh!” Fabian hissed desperately. “It’s me! Fabian! Hush, please, or you’ll give me away!”
“FABIAN?” boomed the voice again, and then, more quietly, “ah, I mean ahem Fabian? That apprentice of Basil’s? Ah, hmm.” A pause, then, quieter still: “Tell me more about why we have to be quiet? And, for that matter…why is it so dark, here? This is blacker than the eighth heart of Hocthhhpu.” The last was pronounced messily.
Fabian, unsure he even wanted to know what “Hocthhhpu” was, shook his head in bewilderment. “I’m lost,” he explained, “in the dungeons under Curmudgeon castle. I’m trying to escape, you see. Only, I’m lost…as, I guess, I said.”
There was a long pause before Nigel answered. “Where’s Basil?”
“Who?” Fabian asked, startled by the question. “Basil? I…I don’t know. Upstairs somewhere? Probably?”
“Hmm,” said the demon. “I see. So, uh…” His voice became dangerously casual. “You’re here alone, huh? Just you? No Basil?”
Little alarm bells began sounding in Fabian’s head. He backed up a bit and encountered the wall. “Uh…” His voice cracked. “Yes?” He suddenly wondered about all the things that Basil hadn’t been able to tell him about this whole summoning business.
A small light flared just a few feet in front of Fabian, dazzling him and revealing the diminutive Nigel in his distinctive floral shirt. The little man’s jet black goatee was so sharp and glistening that Fabian felt self-conscious about his own. “Good. Then let’s get down to business.” Nigel sat down on the ground, the light seeming to surround him like a halo. He glanced up at Fabian. “Sit down, you. If you make me crick my neck to stare up at you, you can bet this negotiation will go poorly.”
Fabian sat down hesitantly. “Negotiation?”
Nigel blinked. “Well, duh. Yes, ‘negotiation’. What, did you think I’d just appear and do your bidding?” He scoffed. “You’ve got a lot to learn, kid. I’m no genie, that’s for sure.” He held his hand out and what seemed to be an entire ream of paper materialized there.
Fabian looked worriedly at the stack of paper, and then glanced up and down the passage, though he could only see a few feet in either direction. “Um, you know,” he whispered as Nigel licked a finger and begin riffling through the papers, “there is a little bit of a time issue here. Guards might be looking for me, and—”
Nigel nodded absently as he compared two pages. “Noted. Expedited negotiation will cost extra.” He extracted another page and held it up with the other two, squinting. “Yes, there it is.” The other papers all disappeared in a small sulfuric pop. “Here,” he said, handing the remaining pages up to Fabian. “Read through these. You’ll need to initial the bottom of each page, and then sign where indicated on the last one.”
Fabian, bewildered, took the papers and squinted at them. He could see the lines where his initials and signature would go, but the writing itself was beyond minuscule. He doubted he’d be able to read it with a magnifying glass.
Nigel seemed to misunderstand his difficulty. He rolled his eyes. “You really are something special, aren’t you? You can’t even read!”
“I can too read,” Fabian said, eyes crossed as he considered the tiny text. “At least, when what I’m reading is halfway legible.”
Nigel sighed and reached out a hand. “Give me the papers. I’ll summarize.”
Fabian gratefully handed the forms back.
Nigel turned to the first page and ran a finger down as he scanned it. “Blah, blah, blah…whereas the Summoner has particular need…yadda, yadda, yadda…the Summoned shall be obliged to perform as requested… It’s all pretty standard boilerplate until you reach article two…which says…ah! Yes. The relevant bits mostly involve payment for services rendered. Here.” He jabbed the paper with a tiny finger. “Paragraph two. ‘The Summoned shall receive remuneration, previously and mutually approved, for services rendered, two percent, net 30.’ We just need to agree on what that ‘remuneration’ ought to be.” He glanced up at Fabian and blinked. “What do you propose?”
Fabian looked blankly back. “Who, me?”
Nigel grunted. “Well, who else? Really, where did Basil find you? Yes, you. What do you propose to pay me for the work I do?” He tapped his fingers on his knee impatiently.
Fabian took a deep breath. “Ah, well.” He wondered what demons typically expected in payment, but suddenly feared to ask. He cast about, trying to think of what he might possibly have access to back at Basil’s house on the hill. Cleaning supplies? He had those in spades, but he doubted Nigel would appreciate a good squeegee as much as he ought to. Baked goods? That somehow felt too friendly, more like what you’d do for a sick neighbor than for a fiend you’d just summoned.
Something… He remembered the pastures near the town. “Maybe…a…goat?”
Nigel raised an eyebrow. “A goat.”
Fabian nodded, trying to sound more confident. “A goat, yes.”
“What would I do with a goat?”
Fabian shrugged uncomfortably. “I…don’t know. Whatever it is that…demons…like yourself do…with goats?” He paused, waiting for some sign from Nigel. The silence grew awkward. “Maybe you could…Oh, I don’t know!” He sighed in exasperation. “Maybe you could drink its blood or something? Isn’t that what you demons do?”
Nigel looked disgusted. “What kind of monster do you think I am?” he asked. “Do you have any idea how useful goats are? How intelligent? How much bigger than me they are? Even if I were inclined to drink the blood of a goat—and I assure you, I’m not—do you have any idea how much blood a goat contains?”
Fabian, sure he did not want to know, but unable to express anything other than revulsion, shrugged.
“SIX LITERS!” the little man shouted.
Fabian looked horrified. “I don’t even want to know how you know that.”
“Have you ever,” Nigel continued, “tried to drink SIX LITERS of something?”
Fabian mutely shook his head.
“That’s right, you haven’t! You’d probably die trying. So, no, you sicko, I would not like to drink the blood of a goat.” He folded his arms and shook his head. “Kids these days.”
The silence grew awkward again.
“Well?” Nigel finally asked, impatiently.
Fabian swallowed. “Well…what?”
The little man rolled his eyes. “What will you pay me for services rendered?”
Fabian shrugged. “How should I know? Maybe you tell me what you want to be paid.”
Nigel raised an eyebrow. “Really?”
The eager look in Nigel’s eye made Fabian uncomfortable for some reason, but he nodded anyway. “Go ahead.”
Nigel considered Fabian searchingly for a long moment, and then nodded. “All right.” He grinned and rubbed his hands together. “For services rendered, I will require…”
He raised an eyebrow and paused dramatically. Fabian began to wonder seriously just where this had all started to go wrong.
“I will require,” Nigel repeated, “one (1) Monte Cristo sandwich, made with still-warm whole wheat bread you’ve baked yourself. It must use the finest doux Gruyère—certified organic!—with a robust Dijon mustard and fresh raspberry jam. And it must be battered with two corn-fed free-range eggs, each gathered on a moonless night using nothing but your wits, your bare hands, and a borrowed ukulele.”
“Oh,” Nigel added. “And for the expedited negotiation, the sandwich will require fresh ham, from a pig whose last meal included corn taken from the same cob that was used to feed the chickens that provided the eggs.” He thought a moment, licking his lips, and then nodded. “Those are my terms,” he said. “Do you accept?”
Fabian shook himself and cleared his throat. “Ah, ahem, well…” He quickly went over the list in his head. “I can manage the ukulele, I think, and the mustard, and the cheese… Raspberries aren’t usually found on our hill, though. Would strawberry jam do?”
Nigel scowled. “Bah, you drive a merciless bargain, sir. A fellow’s got to live, hasn’t he? But fine. Strawberry jam, then. Deal?”
Fabian nodded, dazed by the absurdity of it. “Deal.”
Nigel made a quick notation on the papers and then handed them to Fabian, along with a tiny little pen. Fabian looked curiously at it. “So, I just use this, then? To sign my name?”
Nigel sighed. “Do I even want to know why you’re surprised about that?”
Fabian shrugged. “I just thought these kinds of contracts were supposed to be signed in…you know…blood, or something.”
“What is it with you and blood?” Nigel asked incredulously. “Go on, just sign the papers.”
Fabian initialed and signed where requested, and handed them back to Nigel. He looked them over quickly, nodded his approval, and then made them disappear with another little pop.
“There,” Nigel said. “That wasn’t so bad, was it? I mean, aside from your odd little blood fetish. But anyway, to business. What did you need?”
Fabian was so distracted by the whole negotiation that it took him a few moments to remember his predicament. “Ah, right,” he said. “So, I’m lost in this dungeon, and I need to get out before the guards discover I’m missing. I was wondering… Can you do that Dijkstra’s thing to find the shortest path to the exit? Preferably the rear exit, so I don’t have to talk my way past an angry guard.”
Nigel considered. “Probably. How large is this dungeon?”
“I’m actually not sure,” Fabian said. “I never did spend much time down here.”
Nigel shook his head. “Amateurs,” he said, disgusted. “Fine, whatever, I’ll just guess. Dijkstra’s then. You’ll want to get comfortable.”
“Yeah, it’s going to take awhile. If this dungeon is anywhere near as large as I’m thinking it is, it might take at least a half hour for me to work my way through it all.”
“A half hour?!” Fabian was horrified. “They’ll discover I’m missing long before that. Can’t you do it any faster?”
Nigel eyed Fabian disgustedly. “Not and still call it ‘Dijkstra’s’. I mean, naively, Dijkstra’s has a big O of n squared, right? With optimizations I can work that down to almost logarithmic time, but—”
“Is there another algorithm that goes faster?”
Nigel shrugged. “Well, faster, yes. A greedy best-first search could go quite a bit faster, but—”
“How much faster?”
Nigel eyed Fabian with annoyance. “Are you going to interrupt me all evening?”
Fabian tried to look apologetic. “I’m sorry. I’m just a little…anxious.”
Nigel’s brow furrowed. “I could run a greedy algorithm here in under a minute, probably, but—”
“Less than a minute? That’s perfect! Let’s do that!”
The homunculus sighed. “Fine. Greedy it is. I’ll be right back.”
True to his word, Nigel returned shortly. Very shortly. So shortly, in fact, that Fabian at first wondered if the algorithm had even worked, but Nigel assured him that it had. He’d found a path.
They meandered through the darkened dungeon for a good ten minutes before finally reaching a small door. It opened reluctantly—and loudly—on ancient hinges and revealed a rickety staircase that spiraled upward into the gloom. Nigel took them several landings before finally passing through a door into one of the upper levels of the keep. From there they moved through a little-used wing, past mothballed guest rooms, dining rooms, and even an entire ballroom that Fabian scarcely remembered. The walls were adorned with timeworn portraits of Fabian’s ancestors, most of whom—judging by their expressions—looked to be suffering from acute indigestion. Then, down a flight of stairs, and up a flight of stairs, and through a series of narrow hallways before descending yet another flight of stairs.
Fabian couldn’t believe their luck. It was a miracle they’d not yet encountered anyone. Or maybe the castle was just mostly empty these days. He remembered the mazes and decided those were probably a very effective deterrent for most potential visitors.
“Where are we?” he finally asked as they were walking. “Why aren’t you taking us to an exit? I’m sure we passed several passages that would have been faster.”
Nigel shrugged, not bothering to look back at Fabian. “Yeah, probably. I guarantee the path we’re taking will get you to an exit, but you wanted greedy, so…”
“So…what?” Fabian asked, a feeling of dread growing in the pit of his stomach.
“So you got a greedy path,” Nigel said. “It was quick to find, but it’s not necessarily going to be a short path. In fact, I think we managed to hit on a pretty pathologically long path here.” Fabian couldn’t see his face, but it sounded like he was smiling.
Fabian groaned. “I’m going to die,” he said dolefully.
“Possibly,” Nigel said, stopping and turning to face Fabian. “In which case, though, I won’t get my sandwich, so it’s in my best interest to keep you not dead. And the best way for that to happen, right now, is to keep going. Yes?” He gestured impatiently forward.
Fabian conceded the point, and followed. More passages. More empty rooms. More galleries, more mothballed dining rooms. And, most dreaded of all, more stairs. For some reason the path was tending upward now, spiraling further and further toward the pinnacle of the keep.
They climbed until the stairs ended, all the way to a narrow wooden landing where they were greeted by an intimidatingly sturdy iron door. A rectangular metal label was bolted to it, which read “MEAT PROCESSING—RESTRICTED ACCESS”, and a large keyhole suggested all too clearly that the door was not going to open easily.
Fabian hesitantly touched the door. “What—?” He looked around in confusion. “Where are we? These upper levels were always storage, before…?” He glanced at Nigel. “Can you open the door?”
Nigel laughed. “Don’t you wish! Sorry, kid. I find paths. If the path happens to have an obstacle, like a locked door…well…that’s how these things go.”
Fabian sat down at the top of the stairs, his back to the door. “So, what do we do?”
“‘We’?” Nigel asked. “I don’t know about you, but I’m going to sit here and wait for you to figure out how to open that door.” He paused, eyeing Fabian. “Don’t you know some spell for opening doors or something? Seems like that would be a ‘Wizarding 101’ kind of thing.”
Fabian shrugged. “I haven’t learned one yet. I’ve…actually only been an apprentice for less than a day.”
Nigel raised an eyebrow. “Oh, really? And yet you summoned me?” His gaze took on a considering quality as he regarded Fabian. “If you make it out of here, kid, you might just go far. Especially if you can ditch that Smockwhitener fellow. He’s kind of a drag.”
Fabian sighed. “At this rate—”
Just then the door behind him rattled as if someone were turning a key in it. Fabian jumped away and looked frantically for a hiding spot. Nothing. Not even a suit of armor to cower behind.
He thought to run for it, but too late. The door opened. As he turned to flee he caught a glimpse of the man coming through the door.
“Fabian?” the man said, sounding surprised.
Fabian looked at the other man. “Monsanto?” he asked. “What…what are you doing here?”
The man—Monsanto—seemed worried, flashing a look back through the door and quickly closing it. Fabian caught a glimpse of a large room with several tables and a variety of glass implements on them. “I could ask the same of you,” Monsanto said. “Aren’t you supposed to be…I mean…weren’t you…you know…”
“Locked up?” Fabian asked, smiling. “Well, yes, but I—” He suddenly remembered Nigel, and looked around. The homunculus was nowhere to be seen. He shrugged. “I escaped,” he said simply.
“I can see that,” Monsanto said.
Fabian shook his head. “But what are you doing here?” he asked. “At Curmudgeon castle? After that mess with Anathema, I figured Fergus would have booted you out for being an accomplice. I…was actually a little worried he might have done worse. I’m glad to see you’re okay.”
Monsanto looked uncomfortable. “Well…”
Fabian’s eyes widened in sudden comprehension. “You never told him you were in on it, did you? He never found out!” He laughed. “You old trickster!”
Monsanto grinned sheepishly.
“What ever happened to that guard that helped me escape?” Fabian asked. “Fergus didn’t hurt him at all, did he?”
Monsanto coughed. “Don’t worry about him,” he said. “But you—if you’re caught out here, you’ll get it for sure. Come on, follow me. I’ll find a place for you to hide until you can sneak out.”
Monsanto quickly led Fabian back down the stairs, and down a narrow hallway. “Here,” he said, opening the door of a small broom closet. “You can hide in here. I’ll come back and let you know when it’s all clear.”
Fabian smiled gratefully. “Thank you!” he said. “I owe you.” He climbed in and got as comfortable as he could among the mops and brooms and buckets. “When you can, it’d be good to sit down and chat,” he said. “About old times, I mean.”
“Sure,” Monsanto said distractedly, glancing up the passage. “Old times.” He looked back to Fabian and hesitated. “Comfortable?”
Fabian nodded, and the door closed. He listened until Monsanto’s footsteps grew too faint to hear.
And that’s where the guards found him, just fifteen minutes later.
Fabian sat in his cell, once again grateful that his brother had at least left the torch lit in the hallway. He’d had enough of the dark for one day. He held his twig in his hand, and considered the bald, pink homunculus across the room.
“Bum luck, that,” said Nigel. He was idly flipping a bit of rock up in the air and catching it. “Kind of wild, how the guards managed to find you in that closet.”
Fabian shook his head. “That’s not the point, and you know it.”
“I mean, just after your old pal Monsanto hid you so well, too.”
“Not the point, Nigel.”
“Isn’t it? Seems pretty relevant to me—”
“No,” Fabian said. “The point is this: why didn’t you just take me to one of the exits? Why in the world would you take me on such a roundabout path, especially when I told you that time was so precious?”
Nigel shrugged. “I told you already. You asked for a greedy path, and you got a greedy path.” He paused. “I did try to warn you, you’ll recall. But you kept interrupting me. And I get very annoyed when I’m interrupted.”
Fabian sighed. “Yes, you’re right, I guess. I should have listened. Or asked better questions. Seems like I’ve got plenty of time for that now, though. So, what’s the deal with the greedy algorithm? You found the path so quickly—why was it such a horrible path?”
Nigel seated himself on the floor, legs crossed. “Well, if you’re actually going to listen this time…”
Fabian nodded contritely. “Yes, I will.”
“Good.” Nigel cocked his head, thinking. “You remember how Dijkstra’s works, right?”
Fabian nodded again. “Right. Like water flooding the maze. You split yourself at each intersection and stop when one of you reaches the exit.”
Nigel smiled. “Ah, so you do pay attention! Such a good little apprentice you are.” He mimed patting Fabian on the head. “So, the greedy best-first search can be seen like that, too, but instead of only moving the copy that has currently moved the least, you move the copy that is currently nearest to the exit.”
Fabian looked confused. “I don’t follow.”
“Here.” Nigel traced a simple maze in the grime on the floor. “Look. Assume we’re here.” He indicated a point on one side of the maze. “And assume the exit is over here.” He pointed at the other side of the maze. “Then I’d go in here, just like in Dijkstra’s, and immediately begin walking until the passage branches.” He walked his fingers from the entrance to the first branching, and then looked up at Fabian. “Okay so far?”
“Right. So once I reach the intersection, I split myself—just like I do with Dijkstra’s. Except this time all but one of me just cools their heels and dreams of sandwiches. For now. The question is: which one of me keeps walking?” He pointed at the two locations where his doppelgangers were ostensibly waiting. “Easy. I choose the one that is closest to the exit—as the bat flies—and that’s the lucky clone.”
Fabian tentatively nodded. “…Okay.”
“So, this fellow just goes walking—doop-dee-doop-dee-doop—until he reaches a branching, and the process starts all over again. Split, choose the guy closest to the exit, and have him walk.”
Fabian scratched his head. “Okay, I think I follow that. But why split yourself at all? Won’t your other clones just sit there while the guy closest to the exit does all the walking?”
Nigel shook his head. “No, look. If this guy walks to this point, he’ll run into a dead-end, right? At that point, he has to stop—just like in Dijkstra’s. When that happens, he’s out. No longer playing the game. So we have to jump to one of the other clones.”
Fabian nodded. “Ah! I see. You’d jump to the clone who was next closest to the exit.”
Nigel tapped his head and winked at Fabian. “Eh, see? You can turn those gears when you really try! But keep in mind that it’s not just dead-ends that can cause this. If the passage that was so promising at first suddenly twists and turns and winds up going far away from the exit, then as soon as the current clone is no longer the closest one to the exit, we switch. The new closest clone takes over and starts walking.”
Fabian nodded again. “That makes sense.” He paused, thinking. “But then, why doesn’t this give a more direct route? If you’re always choosing the path closest to the exit…”
Nigel smiled. It looked particularly devious on his ruddy face. “Ah! So we come to it at last! Look here.” He traced a path through the maze on the floor. “Let’s say we get to this point. See how we’d have gotten here by always choosing the path closest to the exit?”
“Good. Now, the passage actually curves away from the exit here, doesn’t it? We have to loop all the way around here, because the algorithm only looks for the path closest to the exit. It totally misses this little short cut right here!” He indicated a passage that cut across the loop entirely.
Fabian’s eyes widened. “Ah! I see! So, the algorithm runs quickly, because it doesn’t have to consider as many locations. But…”
“Exactly!” Nigel’s eyes flashed. “But! The path it finds may not be a very good one.” He hesitated a moment, as if considering something. “Here,” he finally said, rubbing out his maze and drawing a new one. “You try it, now. Start here”—he tapped a spot in the maze—“and try to get here”—he tapped another spot—“using a greedy best-first search.”
Fabian leaned forward and went to work. Each time he’d finish one, Nigel would rub it out and give him another, then another, and another.
Finally, Fabian sat back and leaned his head against the wall. He sighed. “Alright, I’ll say it. ‘I wish I’d listened the first time.’”
Nigel laughed. “Ah, the sweet, succulent flavor of crow! Enjoying it, are you? I know I am!”
Fabian smiled and shook his head. “Anyway, how do you improve on this? How do you get something that runs quickly, and still gives you a decent path to the exit?”
“Well,” Nigel said, settling comfortably against the wall with a wink. “Sneak out of this little box again, and I might just show you.”