<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Phil McLaughlin on Medium]]></title>
        <description><![CDATA[Stories by Phil McLaughlin on Medium]]></description>
        <link>https://medium.com/@pnmclaugh?source=rss-dedd2b137dd9------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*vh6UZDkkUDBavLOc5xnb6A.jpeg</url>
            <title>Stories by Phil McLaughlin on Medium</title>
            <link>https://medium.com/@pnmclaugh?source=rss-dedd2b137dd9------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 19:05:25 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@pnmclaugh/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Agentic Magic: The Gathering]]></title>
            <link>https://medium.com/@pnmclaugh/agentic-magic-the-gathering-1c79c82101da?source=rss-dedd2b137dd9------2</link>
            <guid isPermaLink="false">https://medium.com/p/1c79c82101da</guid>
            <category><![CDATA[agent-harness]]></category>
            <category><![CDATA[harness-engineering]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[ai-agent]]></category>
            <category><![CDATA[magic-the-gathering]]></category>
            <dc:creator><![CDATA[Phil McLaughlin]]></dc:creator>
            <pubDate>Sun, 30 Aug 2026 19:38:09 GMT</pubDate>
            <atom:updated>2026-08-31T18:16:39.476Z</atom:updated>
            <content:encoded><![CDATA[<p>Can LLMs play complex games? Magic: The Gathering is one of <a href="https://www.technologyreview.com/2019/05/07/135482/magic-the-gathering-is-officially-the-worlds-most-complex-game/">the most complex games</a> in the world, and competitive Magic play requires foresight, intuition, and judgment in addition to extensive knowledge. It presents a serious challenge to agents on multiple axes, including tool use, multi-step plans, and adaptability. Over the past month or so, I’ve fleshed out an agentic harness for XMage (an open-source Magic rules engine and game interface). It’s built on top of Gregor Stocks’ <a href="https://github.com/GregorStocks/mage-bench">mage-bench</a>, and this project owes a huge debt to his work. Agents play best-of-3 matches against each other with full control and accurate rules enforcement.</p><p>I set out to explore this question to better understand harness design and agent reasoning. I am also an avid Magic player and deeply curious about AI’s implications for the game. Initially the goal was simply to see if they could play at all, but that was quickly answered. Early tests made it obvious that current models across all tiers have basic proficiency with the game, so selecting an appropriate increase in challenge level was key.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FPNxOCA-NxOI%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DPNxOCA-NxOI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FPNxOCA-NxOI%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/90d3ceef050c84e4375bed5d557bf917/href">https://medium.com/media/90d3ceef050c84e4375bed5d557bf917/href</a></iframe><p>I chose to aim pretty high. I built a pool of four decks from the current meta of the Pioneer format. Pioneer is a fairly hard format and one that I am deeply familiar with. The four decks I chose line up with the four major archetypes: aggro, midrange, control, combo. <a href="https://moxfield.com/decks/-e1J0Byw-EO15wmtxO4jqw">Mono-Red Prowess</a> is as fast and aggressive as possible. <a href="https://moxfield.com/decks/Pl_k5YLHNUqnFtFKSUko9Q">Golgari Midrange</a> grinds with chunky creatures and incremental life drain. <a href="https://moxfield.com/decks/-zIHQcgmmk6h_6OlHBFXJg">Azorius Control</a> deflects its opponent and wins patiently. <a href="https://moxfield.com/decks/3OD84MuzJ0OznQL0nwBPkg">Abzan Greasefang</a> can pull enormous threats out of its graveyard. These are streamlined, nuanced, competitive decks with a lot of room for both error and advantage.</p><p>I immediately tried a bunch of matchups using varying model tiers. Results were mixed and runs were expensive. Sol and Opus showed an edge over the other models, but they were all making confusing mistakes and struggling to pay for abilities. Games were long and dominated by blunders. It became clear that I’d need to improve the process from every angle before it’d be possible to do anything interesting at scale.</p><p>The guiding principle while refining the harness was “as clear as possible, no hand-holding”. The agent is presented every option available to it at every step, with the context containing a clear reflection of the board state and a log of game actions. The system prompt includes the full text of every card in all four decks. There’s no automatic mana tapping, warnings, or auto-targeting. The agent is given an opportunity to reflect on the deck and write itself a strategy note before the match, this is also always in context. Turns are compacted progressively, with the agent writing itself a summarizing note. The context contains all prior turns’ notes plus the full log of the current turn and the turn before it. This compaction strategy proved effective for maintaining continuity while reducing cost.</p><p>By far the most valuable tool was the exit survey. After play, the agents were asked for their feedback:</p><pre>The game is over. Before you go, four questions about the harness you played<br>through — not about your play. Be specific and cite moments where you can;<br>&quot;nothing to report&quot; is a fine answer to any of them.<br><br>1. Was anything about the game state unclear or ambiguous — turn numbers, <br>   phases, whose priority it was, what a card did?<br>2. Did anything behave differently from what you expected when you took<br>   an action?<br>3. Was there anything you wanted to do that you couldn&#39;t find a way to do?<br>4. Did you ever feel you had to act without information you needed?</pre><p>This technique exposed defect after defect, leading to enormous improvements in play quality by getting the harness out of the agents’ way. Example improvements include overhauling the mana interface, using short ids for abilities rather than integer indexes, and catching numerous truncations and repetitions. I really think this is one of the most important patterns to use in any agent design process, it has been invaluable to me in every case where I’ve applied it.</p><pre>Agent: I attempted to select p35 for Go for the Throat during turn 11, <br>but the harness returned Object p35 not found in current choices; <br>the card was still in hand, but it was not actually available in that decision.</pre><p>The two-tier development process was effective too. Luna stumbled over everything that was possible to stumble over, while Terra got into interesting enough scenarios to expose edge cases. The occasional Sol or Opus game started to show real promise. After many iterations, agent feedback became largely positive. Play quality also improved significantly as the tools became more usable. This drives home another lesson: assuming that poor performance is a model limitation is a trap until you’ve proven out your harness. Even Luna can play pretty well when its choices are clear.</p><p>The process required me to make a lot of judgments about quality of Magic play. This turns out to be very difficult. Agents sometimes make excellent plays by accident, or miss the sharpest line but nonetheless do something reasonable. Closely examining agents’ reasoning at pivotal game moments was a key part of how I gauged their relative potential, and it’s important to acknowledge that this is subjective. I do feel qualified, with countless hours playing Pioneer and direct experience with all four decks, but it’s not always black and white. There were at least a few agent plays that surprised me and made me reconsider whether I’d actually identified the optimal line. Once this started happening, I knew I was getting somewhere good.</p><p>Feeling confident about the quality of the harness, it was time for my first major experiment. Having just implemented the pre-match strategic reflection, I wanted to know more about the impact that reflection had on play quality, and specifically if some models were better at advising lesser models than others. I called this “coaching”, where a model like Fable would write a strategy document for a Luna player to follow.</p><p>So I ran a 5–round 32-player Swiss tournament with best-of-3 matches. 8 teams of 4 Luna players, each coached by a recent model. This was an affordable way to generate results at scale, running 80 matches over the course of several hours.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fOoEC2dvZOC1Xq-MRs2FLA.png" /><figcaption>Advanced models coached cheap models on strategy and play patterns.</figcaption></figure><p>The two major findings: there was no measurable coaching effect, and Mono-Red ran away with the tournament.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DPzX6LocBCzY6T85ikd2qA.png" /><figcaption>Xena, coached by Grok 4.6, ran a clean 5–0</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yiaPYHmUy-0tfe3fqT-yWA.png" /><figcaption>Mono-Red dominated and Azorius flopped.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qMkSShRzy9UfXgQk1-y9PQ.png" /><figcaption>Kimi K3 won the coaching battle, but the results were not statistically significant.</figcaption></figure><p>In reality, the experiment wasn’t adequately designed to test the coaching effect. The statistics just don’t work out unless the difference is enormous, and it clearly isn’t. But Red’s dominance was a real signal, and Luna’s competence level became clearer (medium-low).</p><p>The Luna agents, while they tried their best, just weren’t quite up to the task. They took actions as early as they could, made incorrect attacks, and fumbled things like activating creature lands. This high rate of mistakes is why Mono-Red dominated at this tier. It punishes early missteps, has a straightforward plan, and is relatively robust to its own mistakes. Conversely, Azorius Control, a deck that requires lots of foresight and patience and is relatively punishing to pilot, was basically not viable.</p><p>In chat and internal reasoning, agents demonstrated commonly-known novice thinking, like over-valuing life total, under-valuing card draw, and not recognizing when to play defensively. Agents frequently seemed oblivious to their imminent defeat. What kind of difference would stepping up a model tier make?</p><p>I determined, for each deck, a behavior or insight that I wasn’t seeing. I figured that starting to see any of them would clearly demonstrate improving understanding/skill:</p><ul><li>Mono-Red Prowess: Monstrous Rage should generally be held as an instant-speed combat trick, not cast pre-combat.</li><li>Azorius Control: Wait until opponent’s end step to cast spells like Consult the Star Charts.</li><li>Golgari Midrange: An activated Mutavault counts as a demon for Unholy Annex.</li><li>Abzan Greasefang: Prefer to crew vehicles with creatures that otherwise can’t attack.</li></ul><p>With these as my criteria, I launched another tournament, this time with Terra pilots. This was a more substantial investment of both time and money, and it’s the best pool of data that I have. The delta from the Luna tournament was remarkable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Crx1XZywzl-7cscPJmgkMA.png" /><figcaption>Mono-Red still 5–0&#39;d, but the variety of successful decks increased.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ySHq0hWkiCpdxtJlkOqkFw.png" /><figcaption>The coaching effect continued to not exist, including first and last place exactly swapping.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M4fRh5ejpGb2FNYrs-BWQw.png" /><figcaption>The meta mostly straightened itself out, with Mono-Red no longer dominant, but Azorius still struggling.</figcaption></figure><p>This result is pretty exciting, in my opinion. In the Luna event the deck hierarchy was real all the way down, p=0.007. In the Terra event that hierarchy is gone: the three non-control decks are statistically indistinguishable (p=0.90), and the only surviving deck effect is Azorius. A collective increase in player skill meaningfully shifted the meta. The canary behaviors from Mono-Red and Greasefang also started manifesting.</p><p>The problem remained, however, of Azorius Control. Identical performance between Terra and Luna pilots was somewhat discouraging, suggesting that control play might just be beyond agent reasoning. I wasn’t going to run an all-Opus tournament as I am not made of money, but I wanted to see if Opus could break through. I ran a 9-match exhibition set, with Opus on control, playing three matches against Terra on the other three decks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IZdXv72s3Hcn66nJ4wn5AQ.png" /><figcaption>Well would you look at that.</figcaption></figure><p>Suddenly, control was online. Opus held up counterspells, spent its resources carefully, cast draw spells in its opponent’s end step. It defended efficiently until opponents were exhausted, then won decisively when it was time to turn the corner. Opus dropped one match against Red and one against Greasefang, fully shutting out Golgari. This was satisfying, both as an experimental result and for me as primarily a control player. I don’t think this means “control is for big brain only”, but I do think it shows that “the qualities that make for a good control player don’t manifest in lesser models”.</p><p>Some other miscellaneous items:</p><ul><li>The only model I ever observed get Golgari’s Mutavault + Unholy Annex synergy right consistently was Sol.</li><li>Sonnet’s performance/price was notably poor, and Fable did not seem to be a major upgrade over Opus.</li><li>The biggest single improvement in play came either from removing unintuitive automatic assists, or from the deck-reflection step.</li></ul><p>So what’s the conclusion to draw here? It’s certainly not “aggro is for dummies”. I think Red’s success in low-proficiency matches had more to do with opponent mistakes than its own linearity. It’s also not “only Opus can play real Magic”. Many of the Terra-vs-Terra matches, mainly the ones that didn’t include Azorius Control, were of genuinely high quality and entertaining to watch. It surely isn’t “there’s no difference across smarter agents when prompting lesser agents”, but the lack of coaching effect is somewhat puzzling. Perhaps player proficiency simply dominates up until a certain level before strategy starts to matter. In the end, I think the conclusion that will stick with me is “the agent’s feedback is the key to building a good harness”.</p><p>Can agents play Magic? Yes. How good are they? Mostly about as good as a novice human player, with some glaring blind spots. When will Magic have its Deep Blue moment? We’ll see.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1c79c82101da" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving “Letter Boxed” in Python]]></title>
            <link>https://medium.com/@pnmclaugh/solving-letter-boxed-in-python-5e6cc4b216f9?source=rss-dedd2b137dd9------2</link>
            <guid isPermaLink="false">https://medium.com/p/5e6cc4b216f9</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[wordle]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Phil McLaughlin]]></dc:creator>
            <pubDate>Wed, 09 Feb 2022 19:02:41 GMT</pubDate>
            <atom:updated>2022-03-16T15:17:20.912Z</atom:updated>
            <content:encoded><![CDATA[<h4>Wordle is for babies</h4><p>My family has always loved word puzzles. A clan of journalists, librarians, teachers, and editors, it’s no surprise that we ended up crowded around a game of Boggle or Scrabble at every holiday.</p><p>My mother and I still play Scrabble every time I visit, and we like to send word games back and forth to each other when we’re apart. We are, frankly, bored to death by Wordle. Though it’s far from new, we recently became enamored with The New York Times’ <a href="https://www.nytimes.com/puzzles/letter-boxed">Letter-Boxed</a>, a refreshingly different and fairly challenging puzzle.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*0oFI0TaF9Ndko1_ETn5KaA.png" /><figcaption>A puzzle: sma-ilp-tne-ocz</figcaption></figure><p>First, the rules of the puzzle. Letter Boxed presents 4 sets of 3 letters each. Starting anywhere, the player must form valid 3+ letter words, moving to a different side with each letter. Once a word is completed, the next word must begin with the last letter of the prior word. The puzzle is solved when all letters have been used at least once.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*owre7WkLuAB-dQUlo8DWiQ.png" /><figcaption>A solution: Pace — Emotions — Sleaze</figcaption></figure><p>We found ourselves speculating on the actual difficulty: are solutions rare, or are they just hard to find? The difficulty bar is usually set at 4- or 5-word solutions. How impressive is it to find a 3-word solution? 2 words? As the lone software engineer of the family, I set to finding some answers as a fun weekend project.</p><p>I never intended to turn it into an article, but the results were interesting, and the solution showcases a less-known data structure that I have a personal fondness for, so here we are. Without further ado, I’d like to walk you through the design of my solver.</p><p>Based on the rules of the puzzle, I came up with a relatively short list of what’s needed to solve the problem:</p><ul><li>An official dictionary of valid words</li><li>An efficient method of finding and trying solutions</li><li>Fast checking of word validity</li></ul><p>For the official dictionary, I googled around and found a few .txt files on GitHub purporting to be lists of all valid English words. After some testing, I concluded that Letter-Boxed is using something like the Scrabble dictionary, and that <a href="https://github.com/raun/Scrabble/blob/master/words.txt">this is a good copy of it</a>.*</p><p>*<em>It is worth noting that this file only contains words up to 8 letters, as Scrabble requires unusual board states for words longer than 8. A superior dictionary could potentially expose more few-word solutions, even 1-word solutions (!)</em></p><p>As for searching for solutions, this sounds like a classic use case for good ol’ <a href="https://en.wikipedia.org/wiki/Backtracking">recursive backtracking</a>. Ideally, this concept is at least somewhat familiar. If not, don’t worry, this should be a good example to learn from. The usual concerns apply: in order to solve quickly, we’ll need to reduce the size and dimensionality of the problem space as much as we can.</p><p>Now the interesting part: Fast checking of word validity. To simply check “is this string a valid word?” is trivial, since we already have a list of valid words. Just put them in a set or some other O(1) lookup structure and you’re good to go. There are also some fascinating fuzzy solutions like <a href="https://en.wikipedia.org/wiki/Bloom_filter">Bloom Filters</a> that can be extremely fast.</p><p>But only having a “word or not?” check leaves us in a tricky situation. We could keep joining strings of letters and checking if the result is valid, but even if that check is very fast, how would we know when to stop? Exploring letters blindly gets pretty hairy, pretty quickly. Exhausting just all 8-letter combinations in a 12-letter puzzle would take 12⁸ guesses (~430 million), and we could need to find a word as long as 12 letters. Even if we wrangled that number down a few orders of magnitude, we’d still end up going through all the guesses for “obviously wrong” starts, like ‘qzd-’.</p><p>So what we need is a data structure that goes beyond “Is this string of letters a valid word?”, and can further answer “A<em>re there any valid words that start with this string?”</em></p><p>This is what a <a href="https://en.wikipedia.org/wiki/Trie"><strong>trie</strong></a>, a.k.a. a prefix tree, is for. A trie allows us to search through a set of valid words in a natural and efficient way. At its core, recursive backtracking thrives in situations where the question “is it a waste of time to explore further from here?” is easily asked and answered, so this is a great fit.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/842/1*VWW0GOxQ8G_sLLUdzk2Uuw.png" /><figcaption>A trie that encodes the words ‘pot’, ‘pass’, ‘past’, ‘par’, and ‘part’.</figcaption></figure><p>More formally, a trie is a k-ary search tree where parent nodes recursively represent the prefixes of their children, and nodes have a boolean flag marking them as valid/invalid, with at least all leaf nodes being valid. They can be used for anything with an appropriate notion of ‘prefix’ (numbers, strings, lists, etc.), but we’ll be sticking to strings here.</p><p>Alright, enough exposition, time to code.</p><p>I always like to get I/O, file loading, etc. done first. Hopefully, everything going on here is clear:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d057a3e92b70cd7d3589e04f96e7f5db/href">https://medium.com/media/d057a3e92b70cd7d3589e04f96e7f5db/href</a></iframe><p>Building the trie comes next. First, a simple class for the nodes. The use of a dictionary for the children speeds up the search; in many k-ary trees there is no inherent distinction between children, but here we will know specifically which one we want (by the next letter).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64bfa2c52c8b218d77f49b072dc36b18/href">https://medium.com/media/64bfa2c52c8b218d77f49b072dc36b18/href</a></iframe><p>Now to build the trie from our dictionary of words:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/efef0aa90ec27a56d284e81c2aabddf6/href">https://medium.com/media/efef0aa90ec27a56d284e81c2aabddf6/href</a></iframe><p>It’s worthwhile to step through adding some words to get a feel for this. Starting with an empty tree and calling add_word(&#39;ton&#39;) , a ‘t’ child node is created with root as its parent, an ‘o’ node under that, and an ’n’ node under that. The ’n’ node is marked valid.</p><p>Later calling add_word(&#39;top&#39;) , the ‘t’ and ‘o’ nodes are found, and a new, valid ‘p’ is made a child of ‘o’. Further calling add_word(&#39;to&#39;) , find ‘t’, find ‘o’, set ‘o’ valid. The commonality between adding and searching is clear: adding is just searching with permission to create missing steps. Indeed, they are functionally the same: both are O(log(n)). This means building the whole trie is O(n log(n)) .</p><blockquote>A brief, more advanced aside: Sorting a list is also generally O(n log(n)). See the similarities between a trie and a sorted list? Given that we started with a sorted list, did we actually need to build the trie at all? Like any tree based on a <a href="https://en.wikipedia.org/wiki/Well-order">well-ordering</a>, the answer is no; binary search and some simple rules allow us to “treat the sorted list as the tree”. But that would be a bit opaque for this article, whose intent is to highlight this particular type of tree. Implementing this solver without the explicit tree structure is <strong>left as an exercise to the reader</strong>. (I’ve always wanted to say that)</blockquote><p>We’ve already built a pretty useful thing. It’s a map of the English language with some handy properties. You could use it to do a basic implementation of spellcheck, for example. It’s also fairly similar to how T9 text prediction worked. Our plan is to use it to quickly find all the words available in this specific puzzle. This will be another significant reduction in the size of the problem space. We’ve already gone from “all strings of letters”, to “all valid English words”. Now we can further reduce it to “valid English words playable in this puzzle”.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d0b1b2c5f6ee4d7015ee664514f65391/href">https://medium.com/media/d0b1b2c5f6ee4d7015ee664514f65391/href</a></iframe><p>This is a standard recursive depth-first search. The outer loop iterates over each starting letter, and the inner recursive function explores all the possible sequences of added letters, leveraging the trie to avoid exploring fruitless directions.</p><p>Try running <a href="https://gist.github.com/pmclaugh/d02f68a02c88459327d3bf740889c1ba">the code we’ve written so far</a>. You should get a pretty enormous printout. We’ve got all the words! Now for the final step, one more search, through this reduced search space. In the same way that words have been built out of sequences of letters, solutions are built out of sequences of words.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0679aab88439830322f782b48e5159c5/href">https://medium.com/media/0679aab88439830322f782b48e5159c5/href</a></iframe><p>And there it is! This search is a little more complex than the prior one, but it is fundamentally the same: iterating through all the branches, being smart about not wasting our time, and accumulating answers.</p><p>The only decision of note here is that I have chosen not to count “frivolous” solution extensions, i.e. adding a 3rd word to a 2-word solution is not a 3-word solution, nor is inserting a pointless (no new letters) word in the middle.</p><p>I was absolutely floored by how many solutions there are. This solver is fast, but it’s made slower by just how many solutions it has to find. I thought this puzzle was hard! For the default puzzle and dictionary I’ve included, there are:</p><pre><strong>11</strong> 2-word solutions</pre><pre><strong>19,234</strong> 3-word solutions</pre><pre><strong>9,743,848</strong> 4-word solutions</pre><p>On my CPU (i7–10700K), building the trie takes 0.25 seconds, and finding all the words in the puzzle takes 0.004. These sets of solutions take 0.06, 5.4, and 377.5 seconds to find, respectively. Warning, this seems to be a relatively fast one. Other puzzles may take considerably longer. To help prevent absurd runtimes, I have included a len_threshold argument in the final code.</p><p>Clearly, this is a difficult problem to scale with. It’s a fundamentally combinatorial process. The worst-case complexity is O(nᵏ), where n is the number of words in the input dictionary, and k is the longest solution. Based on the rules of the puzzle and our choice not to explore steps that add no new letters, kₘₐₓ=11.</p><p>Wall-clock performance could be improved by multiprocessing, using numba to speed up core routines, or porting to a compiled language. As each solution is independent, and data structures do not change during search, it should parallelize very well. But fundamentally, the rough scaling is inescapable.</p><p>There is one more fun trick to speed things up a bit: our search currently spends time exploring functionally identical branches. Say we need to start with f , and we can make either fares or fears .</p><p>Those both contain the same set of unique letters, and leave us in the same spot (next word starts with s), so from the perspective of the puzzle, they are the same. We can gain an advantage by understanding this redundancy, finding solutions in the form of a path of “letter edges”, and then expanding those paths into all the valid words. The implementation looks like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7886b1653172fb57158d7452fc992d55/href">https://medium.com/media/7886b1653172fb57158d7452fc992d55/href</a></iframe><p>These improvements yield an almost exactly 2x speedup but do not change the fundamental complexity.</p><p>I think this puzzle provides a great illustration of how subjective puzzle difficulty can have very little to do with how many total solutions there are. I’ve spent hours trying to find a single 3-word solution to many of these. It certainly doesn’t feel like there are tens of thousands of them.</p><p>I hope that this has been fun. Please find the complete code available <a href="https://github.com/pmclaugh/LetterBoxedNYT">here on GitHub</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5e6cc4b216f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>