001/*
002 * $Id: SolveRiddle20190628Task.html 4275 2019-07-08 16:14:31Z ball $
003 *
004 * Copyright 2019 Allen D. Ball.  All rights reserved.
005 */
006package ball.riddler538.ant.taskdefs;
007
008import ball.game.scrabble.Bag;
009import ball.game.scrabble.Tile;
010import ball.util.ant.taskdefs.AntTask;
011import java.io.BufferedReader;
012import java.io.InputStreamReader;
013import java.nio.file.Files;
014import java.nio.file.Path;
015import java.nio.file.Paths;
016import java.util.Arrays;
017import java.util.Collection;
018import java.util.Comparator;
019import java.util.LinkedList;
020import java.util.List;
021import java.util.Map;
022import java.util.Optional;
023import java.util.Set;
024import java.util.SortedSet;
025import java.util.TreeMap;
026import java.util.TreeSet;
027import java.util.stream.Stream;
028import lombok.NoArgsConstructor;
029import lombok.ToString;
030import org.apache.tools.ant.BuildException;
031
032import static java.lang.String.CASE_INSENSITIVE_ORDER;
033import static java.util.Comparator.comparing;
034import static java.util.Comparator.comparingInt;
035import static java.util.stream.Collectors.joining;
036import static java.util.stream.Collectors.toList;
037import static org.apache.commons.lang3.StringUtils.SPACE;
038import static org.apache.commons.lang3.StringUtils.isNotBlank;
039import static org.apache.commons.lang3.StringUtils.repeat;
040
041/**
042 * {@link.uri http://ant.apache.org/ Ant} {@link org.apache.tools.ant.Task}
043 * to solve a
044 * {@link.uri https://fivethirtyeight.com/features/whats-your-best-scrabble-string/ Riddler Classic}:
045 * <p>
046 * From Benjamin Danard, the Superstring Scrabble Challenge:
047 * </p>
048 * <p>
049 * The game of Scrabble has 100 tiles — 98 of these tiles contain a letter
050 * and a score, and two of them are wildcards worth zero points. At home on
051 * a lazy summer day with a bag of these tiles, you decide to play the
052 * Superstring Scrabble Challenge. Using only the 100 tiles, you lay them
053 * out into one long 100-letter string of your choosing. You look through
054 * the string. For each word you find, you earn points equal to its
055 * score. Once you find a word, you don’t get any points for finding it
056 * again. The same tile may be used in multiple, overlapping words. So
057 * ‘“theater” includes “the,” “heat,” “heater,” “eat,” “eater,” “ate,” etc.
058 * </p>
059 * <p>
060 * The super challenge: What order of tiles gives you the biggest score?
061 * (The blank tiles are locked into the letter they represent once you’ve
062 * picked it.)
063 * </p>
064 * <p>
065 * The winner, and inaugural Wordsmith Extraordinaire of Riddler Nation,
066 * will be the solver whose string generates the most points. You should use
067 * {@link.uri https://norvig.com/ngrams/enable1.txt this word list} to
068 * determine whether a word is valid.
069 * </p>
070 * <p>
071 * For reference, this is the distribution of letter tiles in the bag, by
072 * their point value:
073 * </p>
074<pre>
0750: ?×2
0761: E×12 A×9 I×9 O×8 N×6 R×6 T×6 L×4 S×4 U×4
0772: D×4 G×3
0783: B×2 C×2 M×2 P×2
0794: F×2 H×2 V×2 W×2 Y×2
0805: K
0818: J X
08210: Q Z
083</pre>
084 * {@ant.task}
085 * <p>
086 * The submitted solution:
087 * </p>
088<pre>
089CARBOXYMETHYLCELLULOSEHAND_RAFTSMANS_IPWIREDRAWERDINITROBENZENEPETTIFOGGINGJUDOKAEQUATEVIVAAIOESOOIU 912
090                          C         H
091----------------------------------------------------------------------------------------------------
092CARBOXYMETHYLCELLULOSE                                                                               46
093CARBO                                                                                                9
094CARB                                                                                                 8
095CAR                                                                                                  5
096 ARB                                                                                                 5
097 AR                                                                                                  2
098   BOXY                                                                                              16
099   BOX                                                                                               12
100   BO                                                                                                4
101    OXY                                                                                              13
102    OX                                                                                               9
103       METHYLCELLULOSE                                                                               25
104       METHYL                                                                                        14
105       METH                                                                                          9
106       MET                                                                                           5
107       ME                                                                                            4
108        ETHYL                                                                                        11
109        ETH                                                                                          6
110        ET                                                                                           2
111         THY                                                                                         9
112             CELLULOSE                                                                               11
113             CELL                                                                                    6
114             CEL                                                                                     5
115              ELL                                                                                    3
116              EL                                                                                     2
117                  LOSE                                                                               4
118                  LO                                                                                 2
119                   OSE                                                                               3
120                   OS                                                                                2
121                     EH                                                                              5
122                      HANDCRAFTSMANSHIP                                                              26
123                      HANDCRAFTSMAN                                                                  21
124                      HANDCRAFTS                                                                     16
125                      HANDCRAFT                                                                      15
126                      HAND                                                                           8
127                      HA                                                                             5
128                       AND                                                                           4
129                       AN                                                                            2
130                          CRAFTSMANSHIP                                                              18
131                          CRAFTSMAN                                                                  13
132                          CRAFTS                                                                     8
133                          CRAFT                                                                      7
134                           RAFTSMAN                                                                  13
135                           RAFTS                                                                     8
136                           RAFT                                                                      7
137                            AFT                                                                      6
138                                MANS                                                                 6
139                                MAN                                                                  5
140                                MA                                                                   4
141                                   SHIP                                                              5
142                                   SH                                                                1
143                                    HIP                                                              4
144                                    HI                                                               1
145                                       WIREDRAWER                                                    17
146                                       WIREDRAW                                                      15
147                                       WIRED                                                         9
148                                       WIRE                                                          7
149                                        IRED                                                         5
150                                        IRE                                                          3
151                                         REDRAWER                                                    12
152                                         REDRAW                                                      10
153                                         RED                                                         4
154                                         RE                                                          2
155                                          ED                                                         3
156                                           DRAWER                                                    10
157                                           DRAW                                                      8
158                                            RAWER                                                    8
159                                            RAW                                                      6
160                                             AWE                                                     6
161                                             AW                                                      5
162                                              WE                                                     5
163                                               ER                                                    2
164                                                 DINITROBENZENE                                      26
165                                                 DINITRO                                             8
166                                                 DIN                                                 4
167                                                  IN                                                 2
168                                                   NITROBENZENE                                      23
169                                                   NITRO                                             5
170                                                   NIT                                               3
171                                                    IT                                               2
172                                                      ROBE                                           6
173                                                      ROB                                            5
174                                                       OBE                                           5
175                                                        BENZENE                                      18
176                                                        BEN                                          5
177                                                        BE                                           4
178                                                         EN                                          2
179                                                             NE                                      2
180                                                               PETTIFOGGING                          20
181                                                               PETTIFOG                              14
182                                                               PETTI                                 7
183                                                               PET                                   5
184                                                               PE                                    4
185                                                                  TI                                 2
186                                                                   IF                                5
187                                                                    FOGGING                          13
188                                                                    FOG                              7
189                                                                       GIN                           4
190                                                                           JUDOKA                    18
191                                                                           JUDO                      12
192                                                                            UDO                      4
193                                                                             DO                      3
194                                                                              OKA                    7
195                                                                               KA                    6
196                                                                                AE                   2
197                                                                                 EQUATE              15
198                                                                                  QUATE              14
199                                                                                  QUA                12
200                                                                                    ATE              3
201                                                                                    AT               2
202                                                                                       VIVA          10
203                                                                                           AI        2
204                                                                                             OE      2
205                                                                                               SO    2
206</pre>
207 *
208 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
209 * @version $Revision: 4275 $
210 */
211@AntTask("solve-riddle-2019-06-28")
212@NoArgsConstructor @ToString
213public class SolveRiddle20190628Task extends AbstractTask {
214    private static final Path TMPDIR =
215        Paths.get(System.getProperty("java.io.tmpdir"));
216
217    private static final Comparator<CharSequence> COMPARATOR =
218        comparing(t -> t.toString(), CASE_INSENSITIVE_ORDER);
219
220    private final Wordlist wordlist = new Wordlist();
221    private final WordMap wordmap = new WordMap(wordlist.keySet());
222    private final StartsWithMap starts = new StartsWithMap(wordmap.keySet());
223    private final EndsWithMap ends = new EndsWithMap(wordmap.keySet());
224    private final Bag bag = new Bag();
225    private final List<Tile> solution = new LinkedList<>();
226    private final StringBuilder sequence = new StringBuilder();
227    private final LinkedList<TreeMap<CharSequence,Integer>> score =
228        new LinkedList<>();
229
230    @Override
231    public void execute() throws BuildException {
232        super.execute();
233
234        try {
235            while (! bag.isEmpty()) {
236                Optional<CharSequence> next = next();
237                CharSequence subsequence =
238                    next.orElseGet(() -> Tile.toString(bag));
239                List<Tile> tiles = draw(subsequence, bag);
240
241                play(subsequence, tiles);
242            }
243
244            int total =
245                score
246                .stream()
247                .flatMap(t -> t.values().stream())
248                .mapToInt(t -> t.intValue())
249                .sum();
250
251            log(Tile.toString(solution) + SPACE + total);
252
253            StringBuilder subheader = new StringBuilder();
254
255            for (int i = 0, n = solution.size(); i < n; i += 1) {
256                if (solution.get(i).getLetter() != sequence.charAt(i)) {
257                    subheader.append(sequence.charAt(i));
258                } else {
259                    subheader.append(SPACE);
260                }
261            }
262
263            log(subheader.toString());
264            log(repeat("-", solution.size()));
265
266            for (int i = 0, n = score.size(); i < n; i += 1) {
267                LinkedList<CharSequence> keys =
268                    new LinkedList<>(score.get(i).keySet());
269
270                keys.sort(comparingInt(CharSequence::length).reversed());
271
272                for (CharSequence key : keys) {
273                    StringBuilder line = new StringBuilder();
274
275                    line.append(repeat(SPACE, i));
276                    line.append(key);
277                    line.append(repeat(SPACE,
278                                       solution.size() - (i + key.length())));
279                    line.append(SPACE)
280                        .append(String.valueOf(score.get(i).get(key)));
281
282                    log(line.toString());
283                }
284            }
285
286            if (! bag.isEmpty()) {
287                log("Remaining: " + Tile.toString(bag));
288            }
289        } catch (BuildException exception) {
290            throw exception;
291        } catch (Throwable throwable) {
292            throwable.printStackTrace();
293            throw new BuildException(throwable);
294        }
295    }
296
297    private Optional<CharSequence> next() {
298        TreeMap<CharSequence,CharSequence> map = new TreeMap<>(COMPARATOR);
299
300        for (int i = 1, j = sequence.length(); i <= j; i += 1) {
301            String prefix = sequence.subSequence(i, j).toString();
302
303            starts.subMap(prefix + Character.MIN_VALUE,
304                          prefix + Character.MAX_VALUE)
305                .keySet()
306                .stream()
307                .max(comparingInt(t -> potential(t)))
308                .ifPresent(t -> map.put(prefix, t));
309        }
310
311        starts.keySet()
312            .stream()
313            .max(comparingInt(t -> potential(t)))
314            .ifPresent(t -> map.put("", t));
315
316        Optional<CharSequence> next =
317            map.entrySet()
318            .stream()
319            .max(comparingInt(t -> potential(t.getValue())))
320            .map(t -> t.getValue().toString().substring(t.getKey().length()));
321
322        return next;
323    }
324/*
325    private Optional<CharSequence> next() {
326        Optional<CharSequence> next =
327            wordmap.keySet()
328            .stream()
329            .max(comparingInt(CharSequence::length));
330
331        return next;
332    }
333*/
334    private int potential(CharSequence sequence) {
335        int potential = 0;
336
337        Collection<CharSequence> words = wordmap.get(sequence);
338
339        if (words != null) {
340            potential =
341                words.stream()
342                .mapToInt(t -> wordlist.getOrDefault(t, 0))
343                .sum();
344        }
345
346        return potential;
347    }
348
349    private void play(CharSequence subsequence, List<Tile> tiles) {
350        if (tiles.size() == subsequence.length()) {
351            solution.addAll(tiles);
352            sequence.append(subsequence);
353
354            while (score.size() < solution.size()) {
355                score.add(new TreeMap<>(COMPARATOR));
356            }
357
358            for (int j = 1; j <= sequence.length(); j += 1) {
359                for (int i = 0; i < j; i += 1) {
360                    String substring =
361                        sequence.subSequence(i, j).toString();
362
363                    if (wordmap.keySet().remove(substring)) {
364                        score.get(i)
365                            .put(substring,
366                                 solution.subList(i, j)
367                                 .stream()
368                                 .mapToInt(Tile::getPoints)
369                                 .sum());
370                    }
371                }
372            }
373
374            wordmap.keySet().removeIf(t -> (! isPlayable(t, bag)));
375
376            wordmap.values().forEach(t -> t.retainAll(wordmap.keySet()));
377            wordmap.values().removeIf(Collection::isEmpty);
378
379            starts.values().forEach(t -> t.retainAll(wordmap.keySet()));
380            starts.values().removeIf(Collection::isEmpty);
381
382            ends.values().forEach(t -> t.retainAll(wordmap.keySet()));
383            ends.values().removeIf(Collection::isEmpty);
384        } else {
385            throw new IllegalStateException();
386        }
387    }
388
389    private boolean isPlayable(CharSequence in, List<Tile> list) {
390        List<Tile> out = draw(in, list);
391        boolean isPlayable = (in.length() == out.size());
392
393        list.addAll(out);
394
395        return isPlayable;
396    }
397
398    private List<Tile> draw(CharSequence in, List<Tile> list) {
399        LinkedList<Tile> out = new LinkedList<>();
400
401        for (int character : in.codePoints().boxed().collect(toList())) {
402            Optional<Tile> tile =
403                list.stream()
404                .filter(t -> t.getLetter() == character)
405                .findFirst();
406
407            if (! tile.isPresent()) {
408                tile =
409                    list.stream()
410                    .filter(t -> t.getLetter() == '_')
411                    .findFirst();
412            }
413
414            if (tile.isPresent()) {
415                out.add(tile.get());
416                list.remove(tile.get());
417            } else {
418                break;
419            }
420        }
421
422        return out;
423    }
424
425    private class Wordlist extends TreeMap<CharSequence,Integer> {
426        private static final long serialVersionUID = 8504887435537639563L;
427
428        protected final Path path = TMPDIR.resolve(getClass().getSimpleName());
429
430        public Wordlist() {
431            super(COMPARATOR);
432
433            try {
434                if (Files.exists(path)) {
435                    for (String line : Files.readAllLines(path)) {
436                        String[] entry = line.split("=", 2);
437
438                        computeIfAbsent(entry[0],
439                                        k -> Integer.parseInt(entry[1]));
440                    }
441                } else {
442                    try (BufferedReader reader = new ResourceReader()) {
443                        Bag bag = new Bag();
444
445                        reader.lines()
446                            .map(t -> t.split("#", 2)[0])
447                            .map(t -> t.split(SPACE, 2)[0])
448                            .filter(t -> isNotBlank(t))
449                            .map(t -> t.trim().toUpperCase())
450                            .forEach(t -> put(t, null));
451
452                        keySet().removeIf(t -> (! isPlayable(t, bag)));
453                    }
454
455                    keySet().stream()
456                        .forEach(t -> computeIfAbsent(t,
457                                                      k -> draw(t, new Bag())
458                                                           .stream()
459                                                           .mapToInt(Tile::getPoints)
460                                                           .sum()));
461
462                    Stream<String> stream =
463                        entrySet().stream().map(String::valueOf);
464
465                    Files.write(path, (Iterable<String>) stream::iterator);
466                }
467            } catch (Exception exception) {
468                throw new ExceptionInInitializerError(exception);
469            }
470        }
471
472        private class ResourceReader extends BufferedReader {
473            public ResourceReader() {
474                super(new InputStreamReader(SolveRiddle20190628Task.class.getResourceAsStream("enable1.txt")));
475            }
476
477            @Override
478            public String toString() { return super.toString(); }
479        }
480    }
481
482    private static abstract class XREF extends TreeMap<CharSequence,SortedSet<CharSequence>> {
483        private static final long serialVersionUID = 3416903069379036321L;
484
485        protected final Path path = TMPDIR.resolve(getClass().getSimpleName());
486
487        protected XREF(Set<CharSequence> wordset) {
488            super(COMPARATOR);
489
490            try {
491                if (Files.exists(path)) {
492                    for (String line : Files.readAllLines(path)) {
493                        String[] entry = line.split("=", 2);
494
495                        computeIfAbsent(entry[0],
496                                        k -> new TreeSet<>(COMPARATOR))
497                            .addAll(Arrays.asList(entry[1].split(SPACE)));
498                    }
499                } else {
500                    compute(wordset);
501
502                    Stream<String> stream =
503                        entrySet().stream().map(t -> format(t));
504
505                    Files.write(path, (Iterable<String>) stream::iterator);
506                }
507            } catch (Exception exception) {
508                throw new ExceptionInInitializerError(exception);
509            }
510        }
511
512        protected abstract void compute(Set<CharSequence> wordset);
513
514        private String format(Map.Entry<CharSequence,SortedSet<CharSequence>> entry) {
515            return (String.valueOf(entry.getKey()) + "="
516                    + entry.getValue().stream().collect(joining(SPACE)));
517        }
518    }
519
520    private class WordMap extends XREF {
521        private static final long serialVersionUID = -1880844619250978768L;
522
523        public WordMap(Set<CharSequence> wordset) { super(wordset); }
524
525        @Override
526        protected void compute(Set<CharSequence> wordset) {
527            for (CharSequence key : wordset) {
528                key = key.toString();
529
530                for (int j = 1; j <= key.length(); j += 1) {
531                    for (int i = 0; i < j; i += 1) {
532                        String value = key.toString().substring(i, j);
533
534                        if (wordset.contains(value)) {
535                            computeIfAbsent(key,
536                                            k -> new TreeSet<>(COMPARATOR))
537                                .add(value);
538                        }
539                    }
540                }
541            }
542        }
543    }
544
545    private class StartsWithMap extends XREF {
546        private static final long serialVersionUID = -2944553722487812425L;
547
548        public StartsWithMap(Set<CharSequence> wordset) { super(wordset); }
549
550        @Override
551        protected void compute(Set<CharSequence> wordset) {
552            for (CharSequence word : wordset) {
553                for (int i = 0, j = word.length() - 1; j > 0; j -= 1) {
554                    String key = word.subSequence(i, j).toString();
555
556                    computeIfAbsent(key, k -> new TreeSet<>(COMPARATOR))
557                        .add(word);
558                }
559            }
560        }
561    }
562
563    private class EndsWithMap extends XREF {
564        private static final long serialVersionUID = -5078727815938269143L;
565
566        public EndsWithMap(Set<CharSequence> wordset) { super(wordset); }
567
568        @Override
569        protected void compute(Set<CharSequence> wordset) {
570            for (CharSequence word : wordset) {
571                for (int i = 1, j = word.length(); i < j; i += 1) {
572                    String key = word.subSequence(i, j).toString();
573
574                    computeIfAbsent(key, k -> new TreeSet<>(COMPARATOR))
575                        .add(word);
576                }
577            }
578        }
579    }
580}