"Letter Boxed" puzzle statistics
You might wonder, for a fully random "letter boxed" puzzle, what proportion are unsolveable?
I modified my solver from the previous post to also generate random puzzles, and analyzed the results of 100,000 runs. For these runs, I used a dictionary from github that claimed to be "the scrabble dictionary", though I have no way of verifying it. It contained 178691 words which I had to convert to lowercase due to the way my search program is implemented.
To the statistics:
- About 37% of puzzles did not result in a solution of up to 12 words
- The most frequent number of letters in a solution was 18; the least was 13 and the most was 38
- The median frequent number of letters in a solution was 19
- The most frequent and median number of words in a solution was 4; the least was 2 and the most was 10
- About 5% of puzzles with a solution had a 2-word solution; about 30% had a 3-word solution.
I haven't played enough official puzzles to know, but I suspect that there are additional constraints on the letters (For example, no Q without U; vowels on at least 3 edges), or puzzles are constrained by having at least one "relatively short" answer, or the puzzle is fully human curated.
Here's the worst puzzle I found, using that dictionary from above. It has a shortest solution of 10 words & 39 characters: fysvzhcplgim
puzzle answer for fys / vzh / cpl / gim
ghi - ich - hip - phiz - zips - shiv - vivific - chili - ism - myc
Not all of those seem like words to me, but that is how scrabble dictionaries are.
NYT "Letter Boxed" solver in C++
My wife and I regularly solve the NYT crossword in the app.
Lately it's been trying to get me to solve a puzzle called "Letter Boxed".
In this puzzle, there are 12 letters arranged with 3 on each side of a square. Valid words have to be made from the letters, with the additional constraint that two consecutive letters may not be on the same side of the square. For example if the edges are "xoy", "tws", "apv" and "kri" then "air" is not a valid word because the consecutive letters "ir" come from the same side. "vow" is. The last constraint is that each consecutive word starts with the last letter of the previous word, so "vow" can be followed by "wok" but not "sat". (Words of any length are permitted, not just 3 letters)
There is no particular scoring to the game, though you're suggested to "try to solve it in # words"; you can also view the previous day's suggested solution.
To me, it seems that the best answer is in the fewest words, with ties broken by the fewest number of characters.
The following program (which assumes that there's a standard unix-style dictionary at /usr/share/dict/words) can find what appear to be "optimal" solutions in only a few milliseconds. Simply supply it with the 12 letters as the first commandline argument, and it will perform a breadth-first search (BFS) with up to 5 words in length. Each candidate printed is better scoring (shorter) than the previous one, so the last line is the best score.
$ ./a.out xoytwsavpkri 228 candidate words proviso - oaks - sixty - yaw provisos - sixty - yaw - wk vow - warps - sixty - yak Checked 3027570 sequences
I originally wrote a program in Python, but memory usage was high and speed was low. This version uses an efficient structure where each word is reduced to a 32-bit quantity that tracks the letters present, the word length, and the word's terminal character. A particular game play is characterized by a fixed-size data structure that includes the characters used so far, the number of words, the number of total characters, and an array of up to 5 words. The deque is initialized with one entry for each possible word. In the main loop, the item is taken from the front of the deque. Then, based on the terminal letter of the last word played it tries each word starting with that letter. If this potential solution is not lower-scoring than the best one, then it stops evaluating. Otherwise, if this word completes the puzzle, the solution is printed and the best known score values are updated. Otherwise, this puzzle state is added to the end of the deque. The program loops until all possibilities have been evaluated.
A dynamic-programming approach would probably beat the BFS but BFS is quite fast enough for the published puzzles I've solved. It might also be possible to work from both ends towards the middle.
I don't have enough experience with the puzzle to know if 5 words always suffice for published puzzles, but it seems likely. The two real puzzles I have tried have 2-word solutions from this program (13 characters, the minimum possible length for 2 words), while they were suggested to be solvable in 5 and 6 steps.
When it comes to randomly selected puzzles, there are possible boards for which I find a best answer of 7 words (using a modified version of the program)
knezcuvamybx 68 candidate words zany - yak - kc - can - numb - beaux - xv 7/23 zany - ye - exec - cab - bevy - yuk - km 7/22 zany - yuk - km - me - eve - exec - cab 7/21 Checked 3516880 sequences
and other sequences which have no solutions up to 7 words and use a lot of RAM and time before giving no solution (11GB peak resident size, 16 seconds):
mtijacfshpwk 194 candidate words Checked 636279365 sequences
I didn't go full dynamic-programming but I did track the best way to each each of the 12*4096 states and stop recursing if the new candidate doesn't reach a known state faster. This runs much faster and uses less memory; the 11GB & 16s example with no solution above is now <4MB and <.01s! Runs below are with that version. (and apparently using a different dictionary, some runs were on debian oldstable and some on debian stable)
mtijacfshpwk 214 candidate words Checked 1944 sequences
I also found that there are 8-word puzzles:
kmujpocaziqh 69 candidate words jam - ma - aqua - ah - ho - oz - zip - pick 8/22 Checked 854 sequencesand 9+-word but I don't like some of the words (and the app doesn't accept 2-letter words):
dnijzaexkyrc 153 candidate words jerk - kc - ca - ax - xi - icky - yd - dz - zen 9/23 Checked 1038 sequences
Source code (GPL-3.0 license) (build with g++ -std=c++20 -O2):
Faster version:
Original version:
Conservation of Experience
If the universe were just, Loretta Gupta, Ph.D. would be forever remembered as the discoverer of Qualium, the researcher who shattered the hard problem of consciousness. Sadly, the universe is not just.
Dr. Gupta's discovery began with the observation that after interacting with Large Language Models (LLMs), her postdoctoral research assistants were listless and bored; hardly their usual energetic young selves. Not to mention useless for doing theoretical physics research. Most likely she was noticing a spurious correlation, but Gupta was intrigued and set up an informal experiment to disprove the link.
Experimental Group A directly interacted with LLM software and had the strongest effect. Control groups C (interacting with non-LLM software), D (non-LLM software in use, non-interactive) and E (no software) were unaffected. Most startling was the outcome for Experimental Group B, who were in a room with a computer executing LLM software, but with no inputs and outputs. For members of Group B, the degree of flattened affect was indistinguishable from group A.
Amused, she published her findings on arXiv under a pseudonym and moved on. That is, until it was cited by Emi Suzuiki in a paper that found that the performance of a synthetic nematode connectome was measurably degraded when it occupied the same shared hosting server as LLM software.
Gupta and the Suzuki collaborated on their next paper, establishing a causal relationship between LLM software usage and impaired neural activity, both in natural and simulated neurons. After use of LLM software was discontinued the neural activity initially appeared to return to baseline after a period of time. The problem was that Suzuki measured a higher baseline than Gupta, even for the identical synthetic connectome on identical hardware.
Gupta's lab, as it turns out, was in a building shared with the business school. The MBAs had long since incorporated use of LLMs into every aspect of their work: writing business plans, evaluating business plans, drafting e-mails, summarizing e-mails, generating dataing profiles, sifting through dating profiles for good matches. You name it, they were doing it with LLMs.
The evidence gathered by Gupta and Suzuki soon became crystal clear: neural activity and deep learning software both use, and potentially exhaust, some physical feature of spacetime not previously identified. Their next paper coined the term "Qualium", detailed construction of a 7-neuron device to measure the ambient level, and clearly showed that the Earth's baseline level of Qualium had been depleted by 2% since Suzuki's paper.
The fact is, we now face two ecological catastrophes: anthropogenic climate change ,and now Qualium exhaustion. World leaders have spent the last few decades saying much and doing little about the former. What, if anything, will they do about the impending Qualium shortage? In both cases, taking real action seems to risk the "line go up" nature of the global economic system. Well, I for one hope that we run out of Qualium before we cook in an atmosphere of CO2. By all acccounts the ego-death of Qualium deprivation is a painless one. I just regret that my animated corpse will probably continue serving the ends of capitalism until it, too, dies. I'm just glad I won't be there to experience it.
Xerox 820 & CP/M
My friend Steve was at an estate sale that had some pretty cool old computing stuff. (there had been an IMSAI priced at $300 but someone else bought it) He invited me to go back out the next day, when things were 50% off. I said "sure", mostly because I wanted a chance to hang out with Steve. No plans to buy anything, no way!
(this article is part narrative, part notes for myself, so it'll be rambling and updated as I think of things to say)
Welcome to the Polity
(CW: Dysphoria, suicide)
Good news, Citizen!
Your connectome is among those archived from your ancestral homeworld, Earth. Galactic Polity \ufffd has chosen to instantiate it, and grants you full citizenship, with all the attendant rights and obligations.
How to fix pip in debian
Well meaning folks have broken pip: PEP 668 -- now, pip install whatever will fail with "error: externally-managed-environment" even if the intent is to install to the user's local "site-packages" area.
If it hasn't affected you yet, it'll affect you with the system python packages in debian testing.
The rationale is solid (-ish) but I prefer things to work as they do now, without changing EVERY pip install line in EVERYthing I cut and paste from the internet (to add --break-system-packages to the commandline).
The solution, at least until a "super PEP 668", is to remove the marker file EXTERNALLY-MANAGED. However, just doing a "sudo rm" won't stick when the package is updated by apt.
Here's one way to durably put aside the 'EXTERNALLY-MANAGED' marker of your system Python installation:
dpkg-divert --divert /usr/lib/python3.11/NOT-EXTERNALLY-MANAGED --rename /usr/lib/python3.11/EXTERNALLY-MANAGEDThis "diverts" (renames) the file, in a way that is respected by dpkg.
A quick example of transforming Python with libcst
I had occasion to encounter a Python library that used assert with a side effect:
assert initialize_hardware(), "hardware failed to initialize"looking a bit more widely, this idiom was apparently used hundreds of times across a family of Python libraries.
"Aha", I said, "I bet I can fix this with an automated tool". In this round of investigation, I found LibCST and set about creating a program that would do what was needed, namely, to turn at assert into if not initialize_hardware(): raise RuntimeError("hardware failed to initialize").
While LibCST has an explicit facility for "codemodding", I didn't notice it at first and wrote in terms of transformers, with my own command-line driver program.
Unfortunately, while my transformer succeeded, attempting to format the CST back into code would result in an error without very many matches on my favorite search engine: Unexpected keyword argument 'default_semicolon'. That linked issue didn't provide an answer, but my further investigation did.
In the Python grammer as represented by LibCST, an assert statement is part of a SimpleStatementLine, while an if statement is not wrapped in a SimpleStatementLine. So if the transformation of an Assert node into an If node is done alone, the new If node lies inside a SimpleStatementLine node, and that is not valid. The problem is not detected until rendering the CST back into code. (It may be possible that using type checking would have found a problem, as this is essentially a type error)
The solution that I arrived at was to also transform any SimpleStatementLine which ended up containing an If node, by using the FlattenSentinel to do it. I think it might have been even more correct to directly perform the transformation within SimpleStatementLine, but what I ended up works now.
Local coordinate systems in OpenSCAD
Here's a small snippet for setting a local coordinate system. You need to know the location to treat as origin as well as the direction vectors to treat as X and Y.
// Take a position vector (p) and 3 direction vectors (uvw)
// and create a transformation matrix. The origin is transformed to p,
// and xyz point along uvw.
// Normally, the caller will ensure that uvw are orthogonal unit vectors
function puvw(p, u, v, w) = [
[u[0], v[0], w[0], p[0]],
[u[1], v[1], w[1], p[1]],
[u[2], v[2], w[2], p[2]]];
// Take a position vector (p) and 2 direction vectors (uv) which should be
// orthogonal but need not be unit vectors. Calculate the unit vectors as well
// as the third vector and return the resulting matrix
function puv(p, u, v) =
let(nu = u / norm(u), nv = v / norm(v), nw = cross(nu, nv))
puvw(p, nu, nv, nw);
// Operate in a local coordinate system where the origin is the point p,
// x points along u, y points along v, and z points along the normal vector
// to uv. x and y should be orthogonal but need not be unit vectors.
module puv(p, u, v) {
multmatrix(puv(p, u, v)) children();
}
For instance, suppose you want to lay out some feature relative to a cone 100mm in diameter and 500mm tall. It's convenient to set the origin to the intersection of the cone base with the +x axis, +x be the direction from the base of the cone to the tip, +y be the direction tangential to the cone, and +z be the direction 'out' from the cone. You might invoke puv like so (corr is a factor to make the flats of the faceted cone exactly touch the 100mm diameter circle):
effen = 16; // 16, 32, 64, ... corr = 1 / cos(180/effen); for(i=[0:45:360]) rotate(i) puv([100,0,0], [-100, 0, 500], [0, -1, 0]) linear_extrude(height=1) square([25, 4], center=true); %rotate(45/4) cylinder(d1=200*corr, d2=0, h=500, $fn=effen);
Recent keyboard deeds
Don't wreck your system with miniconda/anaconda
Generate the 64 GCR values used by Apple DOS 3.3 and ProDos
An interesting finding about Apple DOS 3.3 diskettes
An interesting Disk ][ Interface Card Fault
Stuff I did in 2021...
Where should CircuitPython go in 2022?
The Most Surprising Optimization I've Seen Lately
All older entries
Website Copyright © 2004-2021 Jeff Epler