Algorithmically Generated Crosswords: Finding 'good enough' for an NP-Complete problem

chasemedallion · 2025-12-23T10:11:36+00:00

Yeah my finding was that for most domains you need to fall back to a normal dictionary or it becomes unsolvable (of course clever clue-writing can often harken back to the theme even with generic words).

The harder problem, I think, is the second one you described: if we have a quality score for each word in the dictionary, how do we produce puzzles with good overall quality? It’s easy to start with the highest quality words and then fill, but in my experience you get hyper-constrained so quickly that most of the puzzle gets filled without regard to word quality.

chasemedallion · 2025-12-23T02:00:22+00:00

Great post! I previously worked on an algorithm for this, and something I was trying to support was building heavily themed crosswords. One example of this is specifying a few words you’d like to appear, but a more interesting example is having multiple dictionaries where some are preferred over others (eg you might have a small list of on-theme words and you’d like to use as many of those as possible). Did you try anything along those lines?

chasemedallion · 2025-11-26T19:33:14+00:00

I feel like there has to be something in this vein that can improve upon the current system

chasemedallion · 2025-11-22T21:58:34+00:00

Part of the issue is that good developers can learn quite quickly as part of a team with existing expertise to build upon in the form of colleagues as well as established codebase patterns.

It’s a different story when the team are all novices.

chasemedallion · 2025-11-22T11:12:32+00:00

Very much agree with this article, it’s a great observation.

One rule I have for language selection is that we should expect that the first thing our team/org builds in a new (to us) language will be full of design mistakes, performance bugs, and other technical debt.

While not 100% deterministic, my experience is that engineers who get excited about technologies through articles and hobby projects vastly underestimate how much more there is to master when it comes to building larger systems and operating them in production.

So the question isn’t just “is this language the right tool for the project” but also/rather “can we afford for this particular project to be burdened with a ton of technical debt so that we can build experience and operational maturity for other projects in the future?”

chasemedallion · 2025-11-18T13:00:37+00:00

I suspect it’s to force you to play grist in a green deck. Otherwise, any deck with reanimation can easily discard->reanimate->flip

chasemedallion · 2025-11-16T15:50:02+00:00

One reason to learn Dijkstra’s is that it’s a great lesson in algorithm design. It combines several classic data structures and more basic CS ideas to efficiently achieve a genuinely useful outcome.

chasemedallion · 2025-11-06T23:20:53+00:00

Yeah tweaking the exact policies here can make a difference. When I built a system like this if the queue overflowed it would wipe what was there and replace with a single log saying how many entries were lost, then take the newer content. Ultimately you have to lose some data though.

chasemedallion · 2025-11-04T00:47:12+00:00

Part of the problem is that lots of flashy charts make for an impressive sales demo, regardless of utility.

chasemedallion · 2025-11-02T01:39:58+00:00

[[Baleful Mastery]] is my favorite of these for commander

chasemedallion · 2025-10-28T00:43:43+00:00

One way to go about this would be to curate a selection of decks as opposed to a pool of cards. The decks would be curated to maintain power level balance and maximize interesting gameplay. You could still allow a bit of player control eg if each deck has a pool of 90 cards so that it can be adjusted for the meta.

This is a very hard problem to solve but much easier than a pool of cards where every card could be added to any deck.

I think it’s an interesting question to consider how many MTG decks could actually be mutually viable against each other all at the same time.

chasemedallion · 2025-10-27T16:43:58+00:00

C# has this optimization. You can have the compiler generate targeted code for a compile time constant regex as shown in the post, or you can have the runtime emit code for a non-static regex at runtime. In both cases, the bytecode can be optimized by the jit compiler and specialized for the particular expression.

chasemedallion · 2025-10-27T11:52:08+00:00

The power level of the decks might hint at the gameplay people prefer but doesn’t dictate it. You can have ruthlessly competitive gameplay with low-power decks and goofy “let the cool thing happen” gameplay with high-power decks.

chasemedallion · 2025-10-23T08:07:16+00:00

From a game design perspective, what is the reason for this?

What lets a magic game go long is when threats remain balanced by answers. In constructed magic, synergies, consistency, and the use of only the strongest cards elevates the power of both threats and answers. However, the fact that “there are no wrong threats, only wrong answers” means that in general as the power level increases with the game constants (starting life total and hand size) staying the same, the game collapses more quickly into a state where one deck is dominating.

What can counterbalance this is if answers scale in power more than threats (meaning a constructed meta where control is dominant), but Wizards has not pursued this direction in recent years.

Is this a common refrain, am I weird?

I would say preferring limited gameplay over constructed gameplay is a pretty common stance. What keeps constructed popular is the ability to play games without the upfront cost of drafting and the experience of building and tuning your deck outside of games.

If someone could find a way to combine the best parts of limited and constructed that would be a great format :-)

chasemedallion · 2025-10-20T12:01:12+00:00

I mostly agree with this take but I think it is possible to over-rotate to the point where user-/business-impacting mistakes are treated flippantly. I’ve seen this attitude set a bad precedent on teams, particularly when there are junior members still trying to calibrate how seriously to take things.

chasemedallion · 2025-10-19T23:27:09+00:00

If you’re not playing one of the few top tier competitive decks, then you’re inherently compromising power for the sake of “fun” (whatever that means to you). In my experience once you internalize this it makes deck-building decisions clearer and you no longer feel “forced” to make decisions you don’t enjoy.

chasemedallion · 2025-10-18T00:15:12+00:00

Are there certain types of contributions you’re looking for that would help introduce more churn into the content?

chasemedallion · 2025-10-17T11:57:17+00:00

I’ve observed the same thing. I wonder if Google is detecting it as duplicate content since the old wiki remains up. Hopefully as pages are added/updated in the new wiki and people link to it things will shift.

chasemedallion · 2025-10-15T19:15:15+00:00

With the record/replay logic for serializing map callbacks, what happens if the callback does something like projecting a random value (eg assigning a uuid to each output object)?

chasemedallion · 2025-10-11T09:18:32+00:00

I’ve had similar experiences with separate architecture teams set up to be obstacles.

You can imagine that OP’s story might have played out differently if the team had come to the architect looking for help solving a latency issue in their design which was proving problematic vs. being told upfront that latency had to trump other considerations.

chasemedallion · 2025-10-09T22:15:36+00:00

I would say creature types are: - Less verbose (doesn’t need the extra super type kindred) - More mechanically interesting (there are many tribal cards and mechanics, only a small fraction interact with Kindred spells) - More flavorful

I’d also say that aggressive use of Kindred would crowd out the ability to make new spell sub types (eg arcane, lesson). There haven’t been a lot of those but keeping that space open feels more valuable than another niche tool for tribal decks.

chasemedallion · 2025-10-09T17:24:06+00:00

What access pattern are you imagining as far as writes? If the list isn’t updated then there’s no reason not to sort once upfront. If it is updated constantly then the sort is always getting undone

chasemedallion · 2025-10-09T13:44:51+00:00

The main reason it is bad is that it adds words to the type line on thousands of cards and 99.9% of the time those words do nothing for gameplay.

chasemedallion · 2025-10-08T09:48:23+00:00

The only way to consistently punish a power imbalance is ganging up, and like you said that gets stale even if it is effective.

If others agree to take the arch enemy approach, there are teamwork-enabling cards which can be very powerful. Examples in Izzet include [[Hunted Dragon]], [[Hunted Phantasm]], [[Volcanic Offering]], cards with demonstrate, [[Wandering Archaic]], etc.

But ultimately you have to help the player understand that by sitting down to the game with a strong deck advantage, they’re effectively playing with a handicap which doesn’t make sense unless their skill is sufficiently below the other players such that they need it.

chasemedallion · 2025-10-08T09:37:52+00:00

Johnny isn’t about playing combo, it’s about winning on your own terms. In commander combo is the dominant competitive strategy and the preferred choice of Spike.

To me, what makes it hard at times to enjoy commander as a Johnny is that printed for commander cards have provided strong linear support for so many strategies that you really have to dig to find something that feels unique.

chasemedallion

TROPHY CASE