001package ball.riddler538.ant.taskdefs;
002/*-
003 * ##########################################################################
004 * Solutions for the 538 Riddler
005 * %%
006 * Copyright (C) 2015 - 2022 Allen D. Ball
007 * %%
008 * Licensed under the Apache License, Version 2.0 (the "License");
009 * you may not use this file except in compliance with the License.
010 * You may obtain a copy of the License at
011 *
012 *      http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 * ##########################################################################
020 */
021import ball.swing.table.ArrayListTableModel;
022import ball.swing.table.SimpleTableModel;
023import ball.util.ant.taskdefs.AntTask;
024import java.net.URI;
025import java.nio.file.Files;
026import java.nio.file.Paths;
027import java.util.Collection;
028import java.util.Comparator;
029import java.util.List;
030import java.util.Map;
031import java.util.Set;
032import java.util.TreeMap;
033import java.util.stream.Stream;
034import lombok.NoArgsConstructor;
035import lombok.ToString;
036import org.apache.tools.ant.BuildException;
037
038import static java.util.stream.Collectors.toList;
039import static java.util.stream.Collectors.toSet;
040import static org.apache.commons.lang3.StringUtils.EMPTY;
041import static org.apache.commons.lang3.StringUtils.isNotBlank;
042
043/**
044 * {@link.uri http://ant.apache.org/ Ant} {@link org.apache.tools.ant.Task}
045 * to solve a
046 * {@link.uri https://fivethirtyeight.com/features/can-you-solve-the-vexing-vexillology/ Riddler Classic}:
047 *
048 * The New York Times recently launched some new word puzzles, one of which
049 * is Spelling Bee. In this game, seven letters are arranged in a honeycomb
050 * lattice, with one letter in the center. Here’s the lattice from December
051 * 24, 2019:
052 *
053 * Spelling Bee screenshot, with the required letter G, and the additional
054 * letters L, A, P, X, M and E.
055 * The goal is to identify as many words that meet the following criteria:
056 *
057 * The word must be at least four letters long.
058 * The word must include the central letter.
059 * The word cannot include any letter beyond the seven given letters.
060 * Note that letters can be repeated. For example, the words GAME and
061 * AMALGAM are both acceptable words. Four-letter words are worth 1 point
062 * each, while five-letter words are worth 5 points, six-letter words are
063 * worth 6 points, seven-letter words are worth 7 points, etc. Words that
064 * use all of the seven letters in the honeycomb are known as “pangrams” and
065 * earn 7 bonus points (in addition to the points for the length of the
066 * word). So in the above example, MEGAPLEX is worth 15 points.
067 *
068 * Which seven-letter honeycomb results in the highest possible game score?
069 * To be a valid choice of seven letters, no letter can be repeated, it must
070 * not contain the letter S (that would be too easy) and there must be at
071 * least one pangram.
072 *
073 * For consistency, please use this word list to check your game score.
074 *
075 * {@ant.task}
076 * <p>
077 * The solution:
078 * </p>
079<pre>
080List:           172820
081Scoring Words:  44585
082Honeycomb Sets: 7986
083Solutions:      55902
084
085      537           3898
086------------------------
087  T   REAGGREGATING 20
088A   E REINTEGRATING 20
089  R   ENTERTAINING  19
090N   G INTENERATING  19
091  I   REGENERATING  19
092      REINITIATING  19
093      AGGREGATING   18
094      GRATINEEING   18
095      INTEGRATING   18
096      ITINERATING   18
097      REATTAINING   18
098      REINTEGRATE   18
099      REITERATING   18
100      RETARGETING   18
101      ENTRAINING    17
102      ENTREATING    17
103      GARNIERITE    17
104      GENERATING    17
105      GREATENING    17
106      INGRATIATE    17
107      INTERREGNA    17
108      INTREATING    17
109      REGRANTING    17
110      RETRAINING    17
111      RETREATING    17
112      ARGENTINE     16
113      ARGENTITE     16
114      GARTERING     16
115      INTEGRATE     16
116      INTERGANG     16
117      ITERATING     16
118      NATTERING     16
119      RATTENING     16
120      REGRATING     16
121      RETAGGING     16
122      RETAINING     16
123      RETEARING     16
124      TANGERINE     16
125      TARGETING     16
126      TATTERING     16
127      AERATING      15
128      GNATTIER      15
129      GRATINEE      15
130      INTERAGE      15
131      TREATING      15
132      GRANITE       14
133      GRATINE       14
134      INGRATE       14
135      TANGIER       14
136      TEARING       14
137      REENGINEERING 13
138      INGRATIATING  12
139      ENGINEERING   11
140      ENTERTAINER   11
141      REAGGREGATE   11
142      REARRANGING   11
143      REINTERRING   11
144      TRINITARIAN   11
145      ARRAIGNING    10
146      ENGRAINING    10
147      GANGRENING    10
148      INGRAINING    10
149      INTENERATE    10
150      IRRIGATING    10
151      IRRITATING    10
152      REENGAGING    10
153      REENGINEER    10
154      REENTERING    10
155      REGENERATE    10
156      REGREENING    10
157      REGREETING    10
158      REGRETTING    10
159      REIGNITING    10
160      REINITIATE    10
161      RETREATANT    10
162      TRIGGERING    10
163      AGGREGATE     9
164      ARRANGING     9
165      ARREARAGE     9
166      ENTERTAIN     9
167      ENTRAINER     9
168      GARNERING     9
169      GETTERING     9
170      GINGERING     9
171      GREENGAGE     9
172      GREGARINE     9
173      INTERNING     9
174      INTERRING     9
175      INTRIGANT     9
176      ITINERANT     9
177      ITINERATE     9
178      NARRATING     9
179      NITRATING     9
180      REARRANGE     9
181      REEARNING     9
182      REENTRANT     9
183      REGAINING     9
184      REGEARING     9
185      REGRETTER     9
186      REITERATE     9
187      RENIGGING     9
188      RERIGGING     9
189      RETINTING     9
190      RETREATER     9
191      TEETERING     9
192      TENTERING     9
193      TITRATING     9
194      TITTERING     9
195      AGRARIAN      8
196      AGREEING      8
197      AIGRETTE      8
198      ANEARING      8
199      ANGERING      8
200      ANTEATER      8
201      ANTIARIN      8
202      ARGININE      8
203      ARRANGER      8
204      ATTAINER      8
205      ATTIRING      8
206      ENGINEER      8
207      ENRAGING      8
208      ENTERING      8
209      GANGRENE      8
210      GARAGING      8
211      GENERATE      8
212      GNARRING      8
213      GRAINIER      8
214      GRAINING      8
215      GRANTING      8
216      GREEGREE      8
217      GREENIER      8
218      GREENING      8
219      GREETING      8
220      GRINNING      8
221      GRITTIER      8
222      GRITTING      8
223      INERRANT      8
224      INERTIAE      8
225      INTERNEE      8
226      INTERTIE      8
227      IRRIGATE      8
228      IRRITANT      8
229      IRRITATE      8
230      NARRATER      8
231      RATTENER      8
232      REATTAIN      8
233      REENGAGE      8
234      REGAINER      8
235      REIGNING      8
236      REIGNITE      8
237      RENEGING      8
238      RENITENT      8
239      RETAINER      8
240      RETARGET      8
241      RETIARII      8
242      RETINENE      8
243      RETINITE      8
244      RETIRANT      8
245      RETIRING      8
246      TARTRATE      8
247      TEENAGER      8
248      TERRARIA      8
249      TITTERER      8
250      TRAINING      8
251      TRIAGING      8
252      TRIENNIA      8
253      TRIGGING      8
254      AGINNER       7
255      AIRTING       7
256      ANERGIA       7
257      ANGARIA       7
258      ANGRIER       7
259      ANTIAIR       7
260      ARENITE       7
261      ARIETTA       7
262      ARIETTE       7
263      ARRAIGN       7
264      ARRANGE       7
265      ATTRITE       7
266      EAGERER       7
267      EARNING       7
268      EARRING       7
269      ENGAGER       7
270      ENGRAIN       7
271      ENTERER       7
272      ENTRAIN       7
273      ENTRANT       7
274      ENTREAT       7
275      ETAGERE       7
276      GARRING       7
277      GEARING       7
278      GINNIER       7
279      GIRNING       7
280      GIRTING       7
281      GITTERN       7
282      GRAINER       7
283      GRANGER       7
284      GRANITA       7
285      GRANNIE       7
286      GRANTEE       7
287      GRANTER       7
288      GRATING       7
289      GREATEN       7
290      GREATER       7
291      GREEING       7
292      GREENER       7
293      GREENIE       7
294      GREETER       7
295      GRINNER       7
296      IGNITER       7
297      INERTIA       7
298      INGRAIN       7
299      INTEGER       7
300      INTERNE       7
301      INTRANT       7
302      INTREAT       7
303      ITERANT       7
304      ITERATE       7
305      NAGGIER       7
306      NARRATE       7
307      NATTIER       7
308      NEARING       7
309      NEGATER       7
310      NETTIER       7
311      NITERIE       7
312      NITRATE       7
313      NITRITE       7
314      NITTIER       7
315      RAGGING       7
316      RAINIER       7
317      RAINING       7
318      RANGIER       7
319      RANGING       7
320      RANTING       7
321      RATATAT       7
322      RATTEEN       7
323      RATTIER       7
324      RATTING       7
325      REAGENT       7
326      REARING       7
327      REENTER       7
328      REGATTA       7
329      REGINAE       7
330      REGNANT       7
331      REGRANT       7
332      REGRATE       7
333      REGREEN       7
334      REGREET       7
335      REINING       7
336      REINTER       7
337      RENEGER       7
338      RENTIER       7
339      RENTING       7
340      RETINAE       7
341      RETIREE       7
342      RETIRER       7
343      RETRAIN       7
344      RETREAT       7
345      RETTING       7
346      RIGGING       7
347      RINGENT       7
348      RINGGIT       7
349      RINGING       7
350      RINNING       7
351      TANAGER       7
352      TANTARA       7
353      TARRIER       7
354      TARRING       7
355      TARTANA       7
356      TARTING       7
357      TATTIER       7
358      TEARIER       7
359      TEENIER       7
360      TENTIER       7
361      TERGITE       7
362      TERNATE       7
363      TERRAIN       7
364      TERRANE       7
365      TERREEN       7
366      TERRENE       7
367      TERRIER       7
368      TERRINE       7
369      TERTIAN       7
370      TIERING       7
371      TINNIER       7
372      TITRANT       7
373      TITRATE       7
374      TRAINEE       7
375      TRAINER       7
376      TREATER       7
377      TREEING       7
378      TRIGGER       7
379      TRINING       7
380      AERATE        6
381      AERIER        6
382      AIGRET        6
383      AIRIER        6
384      AIRING        6
385      ANTIAR        6
386      ARGENT        6
387      ARRANT        6
388      ARREAR        6
389      ARTIER        6
390      ATTIRE        6
391      EARING        6
392      EARNER        6
393      EERIER        6
394      ENGIRT        6
395      ENRAGE        6
396      ENTERA        6
397      ENTIRE        6
398      ENTREE        6
399      ERGATE        6
400      ERRANT        6
401      ERRATA        6
402      ERRING        6
403      ETERNE        6
404      GAGGER        6
405      GAINER        6
406      GAITER        6
407      GANGER        6
408      GARAGE        6
409      GARGET        6
410      GARNER        6
411      GARNET        6
412      GARRET        6
413      GARTER        6
414      GENERA        6
415      GERENT        6
416      GETTER        6
417      GINGER        6
418      GINNER        6
419      GRANGE        6
420      GRATER        6
421      GRATIN        6
422      GREIGE        6
423      GRIGRI        6
424      INANER        6
425      INTERN        6
426      IRATER        6
427      NAGGER        6
428      NARINE        6
429      NATTER        6
430      NEARER        6
431      NEATER        6
432      NETTER        6
433      NIGGER        6
434      RAGGEE        6
435      RAGING        6
436      RAGTAG        6
437      RANGER        6
438      RANTER        6
439      RARING        6
440      RATINE        6
441      RATING        6
442      RATITE        6
443      RATTAN        6
444      RATTEN        6
445      RATTER        6
446      REAGIN        6
447      REARER        6
448      REEARN        6
449      REGAIN        6
450      REGEAR        6
451      REGENT        6
452      REGGAE        6
453      REGINA        6
454      REGRET        6
455      RENEGE        6
456      RENNET        6
457      RENNIN        6
458      RENTER        6
459      RETAIN        6
460      RETEAR        6
461      RETENE        6
462      RETINA        6
463      RETINE        6
464      RETINT        6
465      RETIRE        6
466      RIGGER        6
467      RINGER        6
468      RITTER        6
469      TAGGER        6
470      TAGRAG        6
471      TANNER        6
472      TANTRA        6
473      TARGET        6
474      TARING        6
475      TARTAN        6
476      TARTAR        6
477      TARTER        6
478      TATTER        6
479      TEARER        6
480      TEENER        6
481      TEETER        6
482      TENNER        6
483      TENTER        6
484      TERETE        6
485      TERRAE        6
486      TERRET        6
487      TERRIT        6
488      TETTER        6
489      TINIER        6
490      TINNER        6
491      TINTER        6
492      TIRING        6
493      TITTER        6
494      TRIAGE        6
495      TRIENE        6
496      TRITER        6
497      AERIE         5
498      AGGER         5
499      AGREE         5
500      AGRIA         5
501      AIRER         5
502      ANEAR         5
503      ANGER         5
504      ANTRA         5
505      ANTRE         5
506      AREAE         5
507      ARENA         5
508      ARETE         5
509      ATRIA         5
510      ATTAR         5
511      EAGER         5
512      EAGRE         5
513      EATER         5
514      EERIE         5
515      EGGAR         5
516      EGGER         5
517      EGRET         5
518      ENTER         5
519      GAGER         5
520      GARNI         5
521      GENRE         5
522      GNARR         5
523      GRAIN         5
524      GRANA         5
525      GRANT         5
526      GRATE         5
527      GREAT         5
528      GREEN         5
529      GREET         5
530      INERT         5
531      INNER         5
532      INTER         5
533      IRATE         5
534      IRING         5
535      NAIRA         5
536      NITER         5
537      NITRE         5
538      RAGEE         5
539      RANEE         5
540      RANGE         5
541      RARER         5
542      RATAN         5
543      RATER         5
544      REATA         5
545      REGNA         5
546      REIGN         5
547      RENIG         5
548      RENIN         5
549      RENTE         5
550      RERAN         5
551      RERIG         5
552      RETAG         5
553      RETIA         5
554      RETIE         5
555      RIANT         5
556      RIATA         5
557      TARGE         5
558      TARRE         5
559      TATAR         5
560      TATER         5
561      TERAI         5
562      TERGA         5
563      TERNE         5
564      TERRA         5
565      TETRA         5
566      TIARA         5
567      TIGER         5
568      TITER         5
569      TITRE         5
570      TRAGI         5
571      TRAIN         5
572      TRAIT         5
573      TREAT         5
574      TREEN         5
575      TRIER         5
576      TRINE         5
577      TRITE         5
578      AGAR          1
579      AGER          1
580      AIRN          1
581      AIRT          1
582      AREA          1
583      ARIA          1
584      EARN          1
585      EGER          1
586      ERNE          1
587      GEAR          1
588      GIRN          1
589      GIRT          1
590      GNAR          1
591      GRAN          1
592      GRAT          1
593      GREE          1
594      GRIG          1
595      GRIN          1
596      GRIT          1
597      NEAR          1
598      RAGA          1
599      RAGE          1
600      RAGI          1
601      RAIA          1
602      RAIN          1
603      RANG          1
604      RANI          1
605      RANT          1
606      RARE          1
607      RATE          1
608      REAR          1
609      REIN          1
610      RENT          1
611      RETE          1
612      RING          1
613      RITE          1
614      TARE          1
615      TARN          1
616      TART          1
617      TEAR          1
618      TERN          1
619      TIER          1
620      TIRE          1
621      TREE          1
622      TRET          1
623      TRIG          1
624</pre>
625 *
626 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
627 */
628@AntTask("solve-riddle-2020-01-03")
629@NoArgsConstructor @ToString
630public class SolveRiddle20200103Task extends AbstractTask {
631    private static final Character S = Character.valueOf('S');
632
633    @Override
634    public void execute() throws BuildException {
635        super.execute();
636
637        try {
638            URI uri = getClass().getResource("enable1.txt").toURI();
639            List<String> list =
640                Files.lines(Paths.get(uri))
641                .map(t -> t.split("#", 2)[0].trim())
642                .filter(t -> isNotBlank(t))
643                .map(t -> t.toUpperCase())
644                .collect(toList());
645            Set<String> words =
646                list.stream()
647                .filter(t -> t.indexOf(S) == -1)
648                .filter(t -> score(t) > 0)
649                .filter(t -> toCharacterSet(t).size() <= 7)
650                .collect(toSet());
651            Set<Set<Character>> sets =
652                words.stream()
653                .map(t -> toCharacterSet(t))
654                .filter(t -> t.size() == 7)
655                .collect(toSet());
656            Map<Set<Character>,Set<String>> map =
657                new TreeMap<>(Comparator.comparing(Object::toString));
658
659            for (Set<Character> key : sets) {
660                Set<String> value =
661                    words.stream()
662                    .filter(t -> key.containsAll(toCharacterSet(t)))
663                    .collect(toSet());
664
665                map.put(key, value);
666            }
667
668            Map<List<Character>,Set<String>> solutions = new TreeMap<>(Comparator.comparing(Object::toString));
669            Map<List<Character>,Integer> scores = new TreeMap<>(Comparator.comparing(Object::toString));
670
671            for (Map.Entry<Set<Character>,Set<String>> entry : map.entrySet()) {
672                for (int i = 0, n = entry.getKey().size(); i < n; i += 1) {
673                    List<Character> key = entry.getKey().stream().collect(toList());
674
675                    key.add(0, key.remove(i));
676
677                    Set<String> value =
678                        entry.getValue()
679                        .stream()
680                        .filter(t -> t.indexOf(key.get(0)) >= 0)
681                        .collect(toSet());
682
683                    solutions.put(key, value);
684                    scores.put(key, score(value));
685                }
686            }
687
688            log(new SimpleTableModel(new Object[][] { }, 2)
689                .row("List:", list.size())
690                .row("Scoring Words:", words.size())
691                .row("Honeycomb Sets:", sets.size())
692                .row("Solutions:", solutions.size()));
693
694            int maxScore =
695                scores.values()
696                .stream()
697                .mapToInt(Integer::intValue)
698                .max().getAsInt();
699
700            for (List<Character> key : scores.keySet()) {
701                if (scores.get(key).intValue() == maxScore) {
702                    log();
703
704                    List<String> solution = solutions.get(key).stream().collect(toList());
705
706                    solution.sort(Comparator
707                                  .<String>comparingInt(t -> score(t))
708                                  .reversed()
709                                  .thenComparing(Comparator.naturalOrder()));
710
711                    log(new SolutionTableModel(key, solution));
712                }
713            }
714        } catch (BuildException exception) {
715            throw exception;
716        } catch (Throwable throwable) {
717            throwable.printStackTrace();
718            throw new BuildException(throwable);
719        }
720    }
721
722    private int score(String string) {
723        int score = 0;
724
725        switch (string.length()) {
726        case 0:
727        case 1:
728        case 2:
729        case 3:
730            score = 0;
731            break;
732
733        case 4:
734            score = 1;
735            break;
736
737        default:
738            score = string.length();
739
740            if (string.length() >= 7) {
741                if (toCharacterSet(string).size() == 7) {
742                    score += 7;
743                }
744            }
745            break;
746        }
747
748        return score;
749    }
750
751    private int score(Collection<String> collection) {
752        return collection.stream().mapToInt(t -> score(t)).sum();
753    }
754
755    private List<Character> toCharacterList(String string) {
756        return (string.chars()
757                .mapToObj(c -> Character.valueOf((char) c))
758                .collect(toList()));
759    }
760
761    private Set<Character> toCharacterSet(String string) {
762        return toCharacterList(string).stream().collect(toSet());
763    }
764
765    private class SolutionTableModel extends ArrayListTableModel<String> {
766        private static final long serialVersionUID = -5945141277843892156L;
767
768        private final List<Character> honeycomb;
769
770        public SolutionTableModel(List<Character> honeycomb,
771                                  List<String> solution) {
772            super(solution,
773                  new String[] {
774                      EMPTY, EMPTY, EMPTY,
775                      String.valueOf(solution.size()),
776                      String.valueOf(score(solution))
777                  });
778
779            this.honeycomb = honeycomb;
780        }
781
782        @Override
783        public Object getValueAt(int y, int x) {
784            Object value = EMPTY;
785
786            if (y == 0 && x == 1) {
787                value = honeycomb.get(2);
788            } else if (y == 1 && x == 0) {
789                value = honeycomb.get(1);
790            } else if (y == 1 && x == 2) {
791                value = honeycomb.get(3);
792            } else if (y == 2 && x == 1) {
793                value = honeycomb.get(0);
794            } else if (y == 3 && x == 0) {
795                value = honeycomb.get(6);
796            } else if (y == 3 && x == 2) {
797                value = honeycomb.get(4);
798            } else if (y == 4 && x == 1) {
799                value = honeycomb.get(5);
800            } else {
801                value = super.getValueAt(y, x);
802            }
803
804            return value;
805        }
806
807        @Override
808        protected Object getValueAt(String row, int x) {
809            Object value = EMPTY;
810
811            switch (x) {
812            case 3:     value = row;            break;
813            case 4:     value = score(row);     break;
814            }
815
816            return value;
817        }
818    }
819}