A Hexagon Problem

Another week, another riddler. This one was from Zach Wissner-Gross:

The New York Times recently launched some new word puzzles, one of which is Spelling Bee. In this game, seven letters are arranged in a honeycomb lattice, with one letter in the center. Here’s the lattice from December 24, 2019:

The goal is to identify as many words that meet the following criteria:

1. 1. The word must be at least four letters long.
   2. The word must include the central letter.
   3. The word cannot include any letter beyond the seven given letters.

Note that letters can be repeated. For example, the words GAME and AMALGAM are both acceptable words. Four-letter words are worth 1 point each, while five-letter words are worth 5 points, six-letter words are worth 6 points, seven-letter words are worth 7 points, etc. Words that use all of the seven letters in the honeycomb are known as “pangrams” and earn 7 bonus points (in addition to the points for the length of the word). So in the above example, MEGAPLEX is worth 15 points.

Which seven-letter honeycomb results in the highest possible game score? To be a valid choice of seven letters, no letter can be repeated, it must not contain the letter S (that would be too easy) and there must be at least one pangram.

For consistency, please use this word list to check your game score.²

This problem was very fun. The methodology was simple — brute force every letter combination for the set of 6 “ring letters” and every letter for the “hub”.

Getting something that worked, however, was the fun part. Initially, the first iteration was very slow to work. It took something along the lines of 15s to run through each combination. Given that there are 3,364,900 (25 * nCr(24,6)) combinations to test, this is would have taken 584 days to run which is infeasible.

Through a host of improvements we got the checks to take ~10ms which made the entire process take a few hours. This was run overnight and led us to the solution:

Hub: r     Ring: aegint

 

This honeycomb will result in 3898 points from the words listed here.

The code used to generate this is located here.