FiveThirtyEight “What’s Your Best Scrabble String?” Solution

Introduction

FiveThirtyEight presented a challenge to order Scrabble tiles to generate the largest score.

Complete javadoc is provided with the solution implemented in SolveRiddle20190628Task.

Solution

CARBOXYMETHYLCELLULOSEHAND_RAFTSMANS_IPWIREDRAWERDINITROBENZENEPETTIFOGGINGJUDOKAEQUATEVIVAAIOESOOIU 912
                          C         H
----------------------------------------------------------------------------------------------------
CARBOXYMETHYLCELLULOSE                                                                               46
CARBO                                                                                                9
CARB                                                                                                 8
CAR                                                                                                  5
 ARB                                                                                                 5
 AR                                                                                                  2
   BOXY                                                                                              16
   BOX                                                                                               12
   BO                                                                                                4
    OXY                                                                                              13
    OX                                                                                               9
       METHYLCELLULOSE                                                                               25
       METHYL                                                                                        14
       METH                                                                                          9
       MET                                                                                           5
       ME                                                                                            4
        ETHYL                                                                                        11
        ETH                                                                                          6
        ET                                                                                           2
         THY                                                                                         9
             CELLULOSE                                                                               11
             CELL                                                                                    6
             CEL                                                                                     5
              ELL                                                                                    3
              EL                                                                                     2
                  LOSE                                                                               4
                  LO                                                                                 2
                   OSE                                                                               3
                   OS                                                                                2
                     EH                                                                              5
                      HANDCRAFTSMANSHIP                                                              26
                      HANDCRAFTSMAN                                                                  21
                      HANDCRAFTS                                                                     16
                      HANDCRAFT                                                                      15
                      HAND                                                                           8
                      HA                                                                             5
                       AND                                                                           4
                       AN                                                                            2
                          CRAFTSMANSHIP                                                              18
                          CRAFTSMAN                                                                  13
                          CRAFTS                                                                     8
                          CRAFT                                                                      7
                           RAFTSMAN                                                                  13
                           RAFTS                                                                     8
                           RAFT                                                                      7
                            AFT                                                                      6
                                MANS                                                                 6
                                MAN                                                                  5
                                MA                                                                   4
                                   SHIP                                                              5
                                   SH                                                                1
                                    HIP                                                              4
                                    HI                                                               1
                                       WIREDRAWER                                                    17
                                       WIREDRAW                                                      15
                                       WIRED                                                         9
                                       WIRE                                                          7
                                        IRED                                                         5
                                        IRE                                                          3
                                         REDRAWER                                                    12
                                         REDRAW                                                      10
                                         RED                                                         4
                                         RE                                                          2
                                          ED                                                         3
                                           DRAWER                                                    10
                                           DRAW                                                      8
                                            RAWER                                                    8
                                            RAW                                                      6
                                             AWE                                                     6
                                             AW                                                      5
                                              WE                                                     5
                                               ER                                                    2
                                                 DINITROBENZENE                                      26
                                                 DINITRO                                             8
                                                 DIN                                                 4
                                                  IN                                                 2
                                                   NITROBENZENE                                      23
                                                   NITRO                                             5
                                                   NIT                                               3
                                                    IT                                               2
                                                      ROBE                                           6
                                                      ROB                                            5
                                                       OBE                                           5
                                                        BENZENE                                      18
                                                        BEN                                          5
                                                        BE                                           4
                                                         EN                                          2
                                                             NE                                      2
                                                               PETTIFOGGING                          20
                                                               PETTIFOG                              14
                                                               PETTI                                 7
                                                               PET                                   5
                                                               PE                                    4
                                                                  TI                                 2
                                                                   IF                                5
                                                                    FOGGING                          13
                                                                    FOG                              7
                                                                       GIN                           4
                                                                           JUDOKA                    18
                                                                           JUDO                      12
                                                                            UDO                      4
                                                                             DO                      3
                                                                              OKA                    7
                                                                               KA                    6
                                                                                AE                   2
                                                                                 EQUATE              15
                                                                                  QUATE              14
                                                                                  QUA                12
                                                                                    ATE              3
                                                                                    AT               2
                                                                                       VIVA          10
                                                                                           AI        2
                                                                                             OE      2
                                                                                               SO    2

Theory of Operation

A number of Maps are generated from the word list.

    private final Wordlist wordlist = new Wordlist();
    private final WordMap wordmap = new WordMap(wordlist.keySet());
    private final StartsWithMap starts = new StartsWithMap(wordmap.keySet());

wordlist is a Map<CharSequence,Integer> mapping a valid “word” to its potential point value, wordmap is a Map<CharSequence,SortedSet<CharSequence>> mapping a word to all its “included” words, and starts is also a Map<CharSequence,SortedSet<CharSequence>> mapping all words to its respective prefix. After each iteration of selecting a subsequence to play, the wordmap keySet() is updated by removing any sequences that can no longer be played for points:

            wordmap.keySet().removeIf(t -> (! isPlayable(t, bag)));

            wordmap.values().forEach(t -> t.retainAll(wordmap.keySet()));
            wordmap.values().removeIf(Collection::isEmpty);

            starts.values().forEach(t -> t.retainAll(wordmap.keySet()));
            starts.values().removeIf(Collection::isEmpty);

The next() method chooses the next highest valued sequence of tiles to play:

    private Optional<CharSequence> next() {
        TreeMap<CharSequence,CharSequence> map = new TreeMap<>(COMPARATOR);

        for (int i = 1, j = sequence.length(); i <= j; i += 1) {
            String prefix = sequence.subSequence(i, j).toString();

            starts.subMap(prefix + Character.MIN_VALUE,
                          prefix + Character.MAX_VALUE)
                .keySet()
                .stream()
                .max(comparingInt(t -> potential(t)))
                .ifPresent(t -> map.put(prefix, t));
        }

        starts.keySet()
            .stream()
            .max(comparingInt(t -> potential(t)))
            .ifPresent(t -> map.put("", t));

        Optional<CharSequence> next =
            map.entrySet()
            .stream()
            .max(comparingInt(t -> potential(t.getValue())))
            .map(t -> t.getValue().toString().substring(t.getKey().length()));

        return next;
    }

Previous Challenge

The ball.game.scrabble package was initially developed to solve a previous Scrabble problem. The implementation is SolveExpress20161021Task giving the solution:

CLASSISMS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+M, CLASSISM+S]
CLASSISTS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+T, CLASSIST+S]
RELAPSERS [LA, LA+P, LAP+S, LAPS+E, E+LAPSE, R+ELAPSE, RELAPSE+R, RELAPSER+S]
GLASSIEST [AS, AS+S, L+ASS, LASS+I, LASSI+E, LASSIE+S, G+LASSIES, GLASSIES+T]
SCRAPINGS [PI, PI+N, PIN+G, A+PING, R+APING, C+RAPING, S+CRAPING, SCRAPING+S]
SHEATHERS [AT, E+AT, EAT+H, H+EATH, S+HEATH, SHEATH+E, SHEATHE+R, SHEATHER+S]
UPRAISERS [IS, A+IS, R+AIS, RAIS+E, P+RAISE, PRAISE+R, PRAISER+S, U+PRAISERS]