Mathstream

I read an interesting article on ABC News (Australia) about Wordle, it’s worth checking out. The author stated:

I use “share” as my first guess because it includes the two most common vowels, “s” which is the third most common letter and most common final letter in English words, while “h” and “r” are common individually and even more common in consonant clusters, so their presence or absence instantly knocks out a range of possibilities. But I admire people who play with less strategy. Lots of people guess on a whim

So, I decided to write a little Python code and test this hypothesis. The first step was to download a 100,000 English word vocabulary, read it into a Python list and keep only the 5-letter words (with apostrophes / hyphens / etc) stripped out.

Here’s a sample output for solving, the hidden word is “cents“:

Search for: cents
Guess=share, Match=_____, Avoid=har, DiffSpot=['s', '', '', '', 'e']
Guess=times, Match=____s, Avoid=harim, DiffSpot=['st', '', '', 'e', 'e']
Guess=poets, Match=___ts, Avoid=harimpo, DiffSpot=['st', '', 'e', 'e', 'e']
Guess=cents, Match=cents, Avoid=harimpo, DiffSpot=['st', '', 'e', 'e', 'e']

Some notes on the search algorithm:

• The “Match” shows which letters are in the correct spot (the green square in Wordle)
• “Avoid” are the letters we know can’t be in the word
• “Diff Spot” corresponds to the yellow boxes, the letters we know are in the word, but not in this position, i.e. Need to be used, but in a different spot
• It’s a little brute-force, no clever search algorithms and doesn’t avoid string concatenation and other GC abuses
• I didn’t spend any time on statistical significance tests, etc
• The code takes about 10-12ms per puzzle, on my Macbook Pro (M1 Pro chip)

I tried a couple of strategies for the initial word, tested by playing 1000 games that start with a random word from the vocabulary

The reasonable guess was done by searching 100 random words from the list and scoring each word based on the number of letters is has from this list “eariot“, then picking the best one. If you’ve solved simple ciphers by hand, you might recognize this as the start of the letter frequency list. For example, “share” would score 3, whereas “xylem” would score 1 point

Some observations:

• Using “share” or even a reasonable guess is better than random
• A bad guess with less frequent letters is worse than random, but not hugely so

Well, if I get the time, I might let it run all night and find a list of best words. There might also be a way to use n-gram frequencies or some information theoretic approach to guess the best starting word, or to improve the intermediate guesses. Could be fun 🙂

Wishing everybody a wonderful celebration. A friend sent me this Christmas math joke, just had to share…

Last night I was briefly watching the news, and they interviewed Susan Hansen as a “test prep expert” talking about the new SAT.  She made a comment that the 1/4 point penalty for a wrong answer doesn’t reward guessing.

Actually, it’s a little more complicated than this and the penalty for wrong answers is quite interesting.  If you can cross out a couple of obviously wrong answers, then you should just guess between the remaining choices.  Let’s take a look at the College Board SAT Question Of The Day ** for today:

“Troy was ——- when he wasn’t elected class president: his spirits were so low that there was nothing we could say or do to cheer him up.”

• (A) unctuous
• (B) disconsolate
• (C) ebullient
• (D) inscrutable
• (E) tenacious

Now, suppose you don’t know the correct answer, but you do know what “tenacious” and “inscrutable” mean.  Cross these two off the list and pick one of the remaining three answers at random.  One third of the time you’ll be correct and get one point, two thirds of the time you’ll be wrong and lose a quarter point.

Expected score = (1/3 * 1) – (2/3 * 1/4) = 1/6

So, the expectation is positive, so you’re better off guessing between the three remaining options than leaving it blank.  If you can narrow it down to two possible answers, then:

Expected score = (1/2 * 1) – (1/2 * 1/4) = 3/8

So you get 3/8 point by guessing.  The system rewards you for what you do know, even if you don’t have the exact answer.

I tested out of a third of my undergraduate degree, via the CLEP exams.  In every test that had multiple choice answers, I used this strategy.  It works!

** http://sat.collegeboard.org/practice/answered-question-of-the-day

Oh, I thought I might publish the code.  I haven’t done much in Python – but the interface to Gurobi is really nice and makes great use of list comprehensions.  I would rather use Python for mathematical programming than AMPL or OPL, as Python is a much more complete language and I can get help and extensions on the web…

#
# Futoshiki puzzle, using Gurobi
#
from gurobipy import *
# Data
dim = [1,2,3,4,5]
greater = [
  (1,1, 1,2),
  (2,3, 2,4),
  (3,2, 2,2),
  (3,3, 2,3),
  (3,4, 3,3),
  (4,3, 5,3),
  (4,5, 5,5),
  (5,2, 4,2),
  (5,3, 5,2),
  (5,3, 5,4)
  ]

try:
  # Create a new model
  m = Model("plan1")

  # Create variables
  x = {}
  for row in dim:
    for col in dim:
      x[row,col] = m.addVar(lb=1, ub=5,vtype=GRB.INTEGER, name='x_%s_%s' % (row, col))

  # Integrate new variables into the model
  m.update()

  # Relationship constraints
  for row1,col1, row2,col2 in greater:
    m.addConstr(x[row1,col1] >= 1 + x[row2,col2], 'gt_%s_%s_%s_%s' % (row1,col1,row2,col2))

  # Each digit appears only once per row
  for i in dim:
    m.addConstr(quicksum(x[i,col] for col in dim) == 15, 'row_%s' % (i))
    m.addConstr(quicksum(x[row,i] for row in dim) == 15, 'col_%s' % (i))
  m.addConstr(quicksum(x[i,j] for i,j in x) == 15*5, 'total')

  # Solve it
  m.optimize()

  # Display the solution
  for v in m.getVars():
    print v.varName, v.x

  print 'Obj:', m.objVal

except GurobiError:
  print 'Error reported'