Algorithm X
Literary Alfabet Soupe (Revisited)
Puzzle: Literary Alfabet Soupe
Author: @David Augusto Villa
Published Difficulty: Medium
Algorithm X Complexity: Is Algorithm X Really Needed?
Strategy
In the original discussion for this puzzle, I wrote:
Let’s assume you are at a point where you have some number of “candidate” languages for each excerpt. Some excerpts might have just one candidate language while others might have 2, 3, 4 or more candidate languages.
Can you do any problem-space reduction before running Algorithm X? Of course you can! Assume you have identified the following candidate languages for the first 3 excerpts:
| Excerpt | Candidate Languages |
|---|---|
| 1 | Finnish, French, German, Irish |
| 2 | German |
| 3 | French, German, Spanish |
Do you see the opportunity for problem-space reduction? The only option for excerpt 2 is German. Since each language can only be used one time, German can be removed from the candidate lists for excerpts 1 and 3.
Once you have a list of candidate languages for each excerpt, your problem-space reduction can be similar to what was covered a few pages back using Sudoku. This puzzle is not meant to be a complex exact cover problem, so keep your reduction algorithm simple. If you create a loop to reduce the candidate lists wherever possible, you might find that full solutions appear for each test case before you even begin setting up Algorithm X.