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.game.scrabble.Bag;
022import ball.game.scrabble.Tile;
023import ball.game.scrabble.WordList;
024import ball.swing.table.MapTableModel;
025import ball.util.ant.taskdefs.AntTask;
026import ball.util.ant.taskdefs.NotNull;
027import java.util.ArrayList;
028import java.util.Collection;
029import java.util.HashMap;
030import java.util.HashSet;
031import lombok.Getter;
032import lombok.NoArgsConstructor;
033import lombok.Setter;
034import lombok.ToString;
035import org.apache.tools.ant.BuildException;
036
037/**
038 * {@link.uri http://ant.apache.org/ Ant} {@link org.apache.tools.ant.Task}
039 * to solve
040 * {@link.uri http://fivethirtyeight.com/features/this-challenge-will-boggle-your-mind/ First, for Riddler Express, a Scrabble problem:}
041 * <p>
042 * What is the longest word you can build in a game of Scrabble one letter
043 * at a time? That is, starting with a valid two-letter word, how long a
044 * word can you build by playing one letter at a time on either side to form
045 * a valid three-letter word, then a valid four-letter word, and so on? (For
046 * example, HE could become THE, then THEM, then THEME, then THEMES, for a
047 * six-letter result.)
048 * </p>
049 * {@ant.task}
050 * <p>
051 * The generated solutions:
052 * </p>
053<pre>
054CLASSISMS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+M, CLASSISM+S]
055CLASSISTS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+T, CLASSIST+S]
056RELAPSERS [LA, LA+P, LAP+S, LAPS+E, E+LAPSE, R+ELAPSE, RELAPSE+R, RELAPSER+S]
057GLASSIEST [AS, AS+S, L+ASS, LASS+I, LASSI+E, LASSIE+S, G+LASSIES, GLASSIES+T]
058SCRAPINGS [PI, PI+N, PIN+G, A+PING, R+APING, C+RAPING, S+CRAPING, SCRAPING+S]
059SHEATHERS [AT, E+AT, EAT+H, H+EATH, S+HEATH, SHEATH+E, SHEATHE+R, SHEATHER+S]
060UPRAISERS [IS, A+IS, R+AIS, RAIS+E, P+RAISE, PRAISE+R, PRAISER+S, U+PRAISERS]
061</pre>
062 *
063 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
064 */
065@AntTask("solve-express-2016-10-21")
066@NoArgsConstructor @ToString
067public class SolveExpress20161021Task extends AbstractTask {
068    @NotNull @Getter @Setter
069    private String list = null;
070    private WordList wordlist = null;
071
072    @Override
073    public void execute() throws BuildException {
074        super.execute();
075
076        try {
077            wordlist =
078                (WordList)
079                getClassForName(getList()).getDeclaredConstructor()
080                .newInstance();
081
082            SolutionMap previous = new SolutionMap();
083            SolutionMap next = new SolutionMap();
084
085            wordlist.keySet().stream()
086                .filter(t -> t.length() == 2)
087                .forEach(t -> next.add(new Solution(t)));
088
089            while (! next.isEmpty()) {
090                previous.clear();
091                previous.putAll(next);
092
093                next.clear();
094
095                for (Solution solution : previous.values()) {
096                    next.addAll(solution.solutions());
097                }
098            }
099
100            log(new MapTableModel(previous));
101        } catch (BuildException exception) {
102            throw exception;
103        } catch (Throwable throwable) {
104            throwable.printStackTrace();
105            throw new BuildException(throwable);
106        }
107    }
108
109    private class Solution implements Cloneable {
110        private Bag bag = new Bag();
111        private ArrayList<CharSequence> list = new ArrayList<>();
112        private StringBuilder builder = new StringBuilder();
113
114        public Solution(CharSequence sequence) { append(sequence); }
115
116        public Collection<Solution> solutions() throws Exception {
117            SolutionMap map = new SolutionMap();
118
119            for (Tile tile : new ArrayList<Tile>(bag)) {
120                map.add(clone().prepend(tile.toString()));
121                map.add(clone().append(tile.toString()));
122            }
123
124            map.keySet().retainAll(wordlist.keySet());
125
126            return map.values();
127        }
128
129        private Solution prepend(CharSequence sequence) {
130            if (! list.isEmpty()) {
131                list.add(sequence + "+" + builder);
132
133                for (int i = 0, n = sequence.length(); i < n; i += 1) {
134                    char letter = sequence.charAt(i);
135                    Tile tile = bag.draw(letter);
136
137                    builder.insert(0, tile.getLetter());
138                }
139            } else {
140                append(sequence);
141            }
142
143            return this;
144        }
145
146        private Solution append(CharSequence sequence) {
147            if (! list.isEmpty()) {
148                list.add(builder + "+" + sequence);
149            } else {
150                list.add(sequence);
151            }
152
153            for (int i = 0, n = sequence.length(); i < n; i += 1) {
154                char letter = sequence.charAt(i);
155                Tile tile = bag.draw(letter);
156
157                builder.append(tile.getLetter());
158            }
159
160            return this;
161        }
162
163        @Override
164        public Solution clone() throws CloneNotSupportedException {
165            Solution clone = (Solution) super.clone();
166
167            clone.bag = this.bag.clone();
168            clone.list = new ArrayList<>(this.list);
169            clone.builder = new StringBuilder(this.builder);
170
171            return clone;
172        }
173
174        @Override
175        public String toString() { return list.toString(); }
176    }
177
178    private class SolutionMap extends HashMap<CharSequence,Solution> {
179        private static final long serialVersionUID = -5105125984399633023L;
180
181        public SolutionMap() { super(); }
182
183        public SolutionMap(SolutionMap map) { super(map); }
184
185        public void add(Solution solution) {
186            put(solution.builder.toString(), solution);
187        }
188
189        public void addAll(Iterable<Solution> iterable) {
190            for (Solution solution : iterable) {
191                add(solution);
192            }
193        }
194    }
195}