6

I've been playing Letterpress a lot lately.

The aim of the game is pretty much to score as many blue tiles as possible by making words out of the letters on the board. When you play your word, letters composing the word will turn blue unless the letter was surrounded by red tiles.

A regular Letterpress board looks like this:

I realised that the letters on the board must be generated with some sort of rules, otherwise it will be really hard to play the game with some boards. I could only think of the rule where there must be a number of vowels. I wonder if there are other rules in place.

Additionally, I wonder if this will be anything similar to generating Boggle dices.

Ben
  • 51,770
  • 36
  • 127
  • 149
Enrico Susatyo
  • 19,372
  • 18
  • 95
  • 156
  • 7
    I wouldn't be surprised if it was "just" random following a [histogram of letters](http://www.google.com/?q=english%20letter%20histogram) (as found in English or whatever) words. Likewise, the red tiles are just random. Of course, you'd have to inspect the source code, have some other insight *or* run some analysis on the generated board to say more. Sometimes random is a !@#$, but who knows, perhaps the algorithm tips the odds with a digram bias. –  Nov 04 '12 at 06:02

2 Answers2

4

I decided to hack together a solution based on user166390's suggestion. The frequencies you see are for the English language, taken from Wikipedia. Running the program a few times and just eyeballing the results, they look pretty playable to me. I can generally find a few four- or five-letter words at least, and I'm not even very good at the game! Anyway, here's the code:

#!/usr/bin/env python

from random import random
from bisect import bisect_left

letters = [c for c in "abcdefghijklmnopqrstuvwxyz"]
frequencies = [8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966,
               0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987,
               6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074]

cumulative_frequencies = [sum(frequencies[0:i+1]) for i in xrange(len(frequencies))]

for i in xrange(5):
    line = ""
    for j in xrange(5):
        line += letters[bisect_left(cumulative_frequencies, random() * cumulative_frequencies[-1])] + " "
    print line

The idea is, for each letter to be generated, use the roulette wheel algorithm to choose it randomly with probability proportional to the frequencies given.

Community
  • 1
  • 1
Imre Kerr
  • 2,388
  • 14
  • 34
  • It's more subtle than this. For example, if a `Q` is "chosen", there is logic in the code to ensure that a valid word using `Q` is possible. Etc. – jason Jun 24 '13 at 08:58
  • Ok, so in general it will always be possible to use all the letters in the board for at least one word? In that case I'm completely stumped. – Imre Kerr Jun 24 '13 at 08:59
  • Hang on, in the example board the OP posted, there's a `C` in the top right corner. How on earth are you supposed to use that? Unless acronyms are allowed of course. – Imre Kerr Jun 24 '13 at 09:04
  • You can play "cave", "peace", etc. – jason Jun 24 '13 at 09:25
  • In that case I've misunderstood the rules of the game. – Imre Kerr Jun 24 '13 at 09:48
1

I've heard Loren Brichter, the dev, talk about it, bit I can't for the life of remember where. I think it was on Guy Ritchie's Debug podcast, but I'm not sure. I remember a few things.

He guarantees at least a certain number of vowels.

The consonants are generated separately from the vowels. This implies separate letter distributions.

He did his own analysis of the dictionary behind the game to come up with the letter distribution.

If a Q is chosen an I is guaranteed so a word is always possible with the Q.

I play a lot. I have never had a game end for any reason but all letters being used. I don't know if it's guaranteed a word is always possible with every letter, but it sure seems it's practically true even if not enforced.

jason
  • 236,483
  • 35
  • 423
  • 525
  • I've listened to this podcast too. Pretty sure it's Debug. I think he said that he generates at most 7 vowels. If that's the case I wonder what the minimum is, and how did he came up with that number as the maximum. – Enrico Susatyo Jun 25 '13 at 07:59
  • Wait, if a Q is chosen, an I is also guaranteed to be chosen? In that case the algorithm is not a simple distribution. – Enrico Susatyo Jun 25 '13 at 08:10
  • I remember playing games with a Q and no I or U. You can still make QAT or a few others. If anything, it just checks to make sure *any* Q word is playable. – cobbzilla Jun 05 '16 at 00:14