The Puzzle (v1)
Lloyd woke, his head throbbing, and glanced at the clock. Ten-thirty. Closing his eyes, he massaged his temples with his fingers. Then, reluctantly, he swung his legs out of the bed, his feet feeling for the floor. The room swayed and span around him; he felt it heaving and lurching in the pit of his stomach.
“What did I do last night to deserve this?” he thought.
Slowly pulling himself up to a seated position at the side of the bed, his forehead pounding in protest, Lloyd patted himself down, searching for clues. He was still wearing the clothes from the day before: dirty jeans, a red-checked flannelette shirt, unbuttoned to reveal a white t-shirt that declared “YOUR FAVOURITE BAND SUCKS”, and a pair of threadbare sneakers.
Lloyd rose and stumbled across the room to wash his face in the basin, feeling a day’s worth of stubble on his chin. He studied his reflection in the small, oval mirror, which was tacked to the wall and thoroughly splattered with so much dried toothpaste that he found it hard to focus on his own reflection. He quickly brushed his teeth, contributing another layer of peppermint splashes to the grime that obscured his view in the process.
A satchel sat in the corner of the room. Grabbing it, he gathered up the things he would need for the day and stuffed them inside, then checked its various pockets to make sure he was carrying a sufficient supply of ibuprofen and modafinil. It turned out that he was running low on the latter; it was time to ask Rob to source another batch. Prepared for the day ahead, he left his dwelling, grabbing his board on the way out.
Lloyd rolled across the campus, passing through the shadowed archways that connected its austere buildings, manoeuvring around throngs of undergraduate students on their way between classes, making his way to the coffee shop.
It was busy when he got there; a long line snaked out of the doorway and into the rose garden. The sun blared down. He needed the caffeine, so he resigned himself to wait. Time passed slowly, the line moving forward by a couple of steps every few minutes. The students in front of him, freshers mostly, seemed happy and cheerful, chatting about things that had happened to people they knew.
Boring, everyday stuff.
Lloyd turned to look behind himself and found that the line had been growing; he was now in the middle of a procession of a few dozen people, perhaps more. He did a quick head-count. Thirty-three people visible outside. There could be no more than seven or eight people queueing up inside; the coffee shop wasn’t that large. So perhaps forty-two altogether? A lucky number.
To kill time, he fumbled around in his satchel and pulled out a dog-eared issue of a magazine he had pilfered from the waiting room of a dental surgery weeks before. The cover was bright and pastel, featuring photographs of tanned celebrities with perfect teeth and trumped-up headlines promising scandal and gossip. Oblivious to the surprised looks and stifled giggles he was now attracting, Lloyd flipped through to the “Puzzles and Brainteasers” section toward the back, and considered the “Crossword Jumble” with deep interest.
The puzzle offered a monthly cash prize of two-thousand dollars to whomever could construct the best crossword from a blank grid and a long list of supplied words. There were far too many words in the list to fill the grid, which was only fifteen-by-fifteen squares in size. The trick was to select the right ones, and to then lay them out in the best possible way. The score could then be calculated by adding up the individual scores of all the letters that fell at an intersection between words, according to a table printed alongside the word list. It was a classic maximisation problem; Lloyd’s bread-and-butter. The pages of the magazine were filled with spidery handwriting and neatly-drawn diagrams that recorded his meticulous observations and well-considered theories.
“Your order, please?”
Lloyd looked up, surprised to find himself inside the coffee shop and standing in front of the counter. A pretty blonde girl with bright blue eyes was staring at him over the top of her thin, rectangular glasses, her tightly pressed lips struggling to suppress a smile.
“Quad-shot, no milk or sugar, please.”
Lloyd sat alone at a small table in a secluded corner of the coffee shop, the room noisy with excited conversation and laughter. The magazine was flattened out on the table in front of him. He had retrieved a couple of pills of ibuprofen and a lone modafinil tablet from his satchel. Cupping them in his palm, he rattled them like a gambler shaking dice for luck, then threw his head back, slammed the drugs into his mouth, and downed the coffee in a single gulp to wash it all down.
He knew that there were a vast number of possible crossword puzzles that could be created from the list of words supplied by the magazine. That ruled out a brute-force approach; if he wrote a computer program that could create all possible crossword puzzles and check the score of each in order to select the winner, it would take thousands of years to run. And the entry was due in only a few days. No, he would have to devise a technique that would allow him to hone in on the best solution much more quickly.
He imagined a vast landscape of crossword puzzles before him, reaching out as far as the eye could see, with similar puzzles situated in the same region of the landscape. Puzzles that just swapped the positions of two words but were otherwise identical, for example, would be laying right next to each other, while those that used a different set of words altogether would be separated by a great distance. He imagined that the landscape rose and fell according to the score of each puzzle lain upon it, with the mountains home to high-scoring puzzles and their kin.
All he had to do was wander around the landscape, find the highest mountain, and climb to its summit.
The problem was, he had to do this completely blind. Examining a single point of the undulating landscape would cost time and effort. Beholding the entire landscape was precisely equivalent to brute-forcing the solution. Instead, he needed a strategy that minimised the number of examinations required while giving a high likelihood of finding the highest point.
Perhaps he could begin with a random puzzle, and modify it just a little bit in every possible direction, yielding all of its neighbouring puzzles? These could be examined in turn, and he could then re-centre his view on the neighbour with the highest score and repeat the process. This was akin to a blind man in Paris feeling the ground around him with a stick, stepping onto the highest point, and expecting that by continuing in that fashion he would eventually find himself standing at the top of Mount Everest.
Clearly that approach would have a low chance of success.
Perhaps he could start with two random puzzles and breed them together, their offspring combining properties of each of its parents, along with a few random mutations? The strongest offspring, in terms of their score, could then be mated, and the process repeated down the generations. A classic evolutionary approach. But no, Lloyd realised, that analogy was cute, but it broke down when one thought about the problem spatially. Each puzzle was just a point on the landscape. The offspring of two points would just be another point that lay somewhere between them. That would be like trying to climb Everest by choosing two random cities and measuring the height of the ground — or ocean, for that matter — half-way between them. A folly.
He was getting nowhere. Perhaps Dan and Rob, his fellow postgraduate students, had made better progress? They’d been hunched over a computer when he’d last seen them, discussing candidate algorithms with palpable excitement. He grabbed his satchel and his board, folding up the magazine and stuffing it into the back pocket of his jeans as he did so, and then pushed through the queue of undergraduates, keen to see what the guys had been up to.
Lloyd rolled past the main library, following the curved pathway as it spiralled downwards, bursting out near the entrance of the Department of Physics and coasting from there onwards and downwards towards the Faculty of Mathematics.
He smelled cigar smoke.
“Lloyd,” came a yell from above him. “Up here.”
He came to a stop, putting one foot onto the ground to steady himself, and looked up toward the first-floor balcony of the Mathematics building. Mike, his supervisor, was standing above him, arms planted on the railing as if about to deliver an uplifting speech to crowds of admiring plebeians below.
“Hey Mike,” yelled Lloyd in return. “What’s up?”
“Your mid-semester presentation is in a few weeks. What are you going to speak about? Have you got any results?”
Lloyd sighed. His research was getting nowhere.
“Oh yeah, I’ve been going through the Gutenberg Corpus with the guys. It’s really great stuff, I should have some exciting findings to talk about.”
He had nothing to report. He hadn’t even looked at the corpus yet.
Mike gave him a thumbs-up, chewing on the cigar at the corner of his mouth.
“Good man. I expect big things!”
Lloyd walked down the brown-carpeted hallway to the door of the research lab. Dull, irregular thuds were emanating from within. Perhaps Dan and Rob were performing some kind of new experiment? The thuds stopped, and the sudden silence was broken by laughter.
Swiping his security pass to unlock the lab door, he entered.
“Twenty-six,” Rob said, sweeping his long black hair back behind his ears. “A new record?”
Dan dropped to a swivel chair and rolled to a nearby computer, where he started typing. Lloyd could see a long column of numbers. Dan tapped a few keys and a chart appeared.
“No, no,” he said. “Oh, hullo Lloyd. No, not an all-time record, but the best we’ve done in the last forty-five minutes or so.”
The room smelled hot and sweaty. Lloyd bent down to retrieve a crumpled, battered object from the floor.
“How long have you two been playing hackey-sack in here with this,” he said, holding the misshapen chocolate milk carton at arm’s length.
“We got here at, what, nine this morning?” Rob looked at Dan, who nodded in return, the two of them taking the question literally.
Lloyd shook his head, and lobbed the carton toward a bin in the corner of the room. Quick as a flash, Dan leaped from his chair, his leg outstretched, barely managing to make contact with the carton before it fell into the receptacle.
“One,” said Rob. “Way to bring down the average, Lloyd.”
Later the three of them stood around a computer, watching numbers slowly scroll up the screen. Four thousand, three hundred and twenty nine. Four thousand, three hundred and thirty two. Four thousand, three hundred and thirty three. Four thousand, three hundred and thirty seven.
“How long has this been running?” Lloyd asked.
“About two weeks,” Dan replied. “We reckon we can let it go for another forty-eight hours before we need to send off our entry.”
“Two-thousand smackaroos,” said Rob excitedly, rubbing his hands together with anticipation. “What are we going to do with all that cash?”
“What do you think the final score will be?” asked Lloyd.
“At the current rate, which is slowing, probably no more than five thousand,” said Dan. “If that. It’s converging on a local optima.”
“Could Schrödinger help, do you think?”
Dan considered this; he had been toying around with the department’s new quantum computer, which had been nicknamed after the Austrian physicist, spending his evenings and weekends evaluating its capabilities with interest.
“I just wouldn’t have time to encode the word grids; I’ve only implemented a simple Goodman Delete for balanced binary trees so far, and that was a tonne of work.”
Rob, losing interest, snatched the magazine from Lloyd’s back pocket and sat down in a chair, leafing slowly through its pages.
“Remind me how that works?” asked Lloyd.
“Well, you have a binary tree, and you want to efficiently delete one its nodes while keeping it balanced, you know how to do that, right?”
Lloyd nodded. It was a classic computer science algorithm.
“Yeah, didn’t we have an assignment to implement that? Back in second-year or something?”
“We did! You remember Yuval Goodman? His delete routine corrupted memory and crashed his program, and he couldn’t figure out how to fix it. So in a fit of desperation he replaced it with a routine that just created a new tree, identical to the first, but missing the one node that was supposed to be removed.”
“Haha, hence the Goodman Delete, I remember! But why would you want to code that up for Schrödinger, of all things?”
Dan crossed the room to the whiteboard, quickly erasing a few of their scribblings from the previous day, and began sketching out a diagram.
“Using a quantum computer is like searching every single possibility at the same time, almost as if you’re tuning in to the multiverse, with the wave function collapsing onto the solution. It’s elegant and fast, but you need to encode the search space first, which is the complicated part.”
“Hey guys, check this out,” Rob called from across the room. He swivelled in his chair, holding up the magazine. “Behold our main rival!”
He arose and crossed the room so Lloyd and Dan could take a closer look at the page, which announced the winner of the crossword competition from the previous month. It was accompanied by a photograph of a frail old lady, in her seventies at least, accepting a large cheque from a professionally dressed young woman. Lloyd grabbed the magazine from Rob to read the announcement out loud.
“We congratulate Edith N… for her winning entry in last month’s Crossword Jumble, with a score of seven thousand, eight hundred and sixty two.”
Rob and Dan slumped and stared at the floor, defeated.
“We’ve got the most powerful computers, the best algorithms, the brightest minds,” reflected Dan. “And we still can’t beat an old granny fuelled by hot tea and biscuits.”
Rob looked at Dan slyly. “If only we could harness that power!”
“We’d conquer the world! Bwahaha!”
The three of them spent the next half hour at the whiteboard, sketching out the design of a massively-parallel granny computer, milking the situation for every last skerrick of comedic value. They then broke for lunch.