001package ball.riddler538.ant.taskdefs;
002/*-
003 * ##########################################################################
004 * Solutions for the 538 Riddler
005 * $Id: SolveExpress20161021Task.html 5431 2020-02-12 19:03:17Z ball $
006 * $HeadURL: svn+ssh://svn.hcf.dev/var/spool/scm/repository.svn/hcf-dev/blog/2019-07-08-fivethirtyeight-best-scrabble-string/src/main/resources/javadoc/src-html/ball/riddler538/ant/taskdefs/SolveExpress20161021Task.html $
007 * %%
008 * Copyright (C) 2015 - 2020 Allen D. Ball
009 * %%
010 * Licensed under the Apache License, Version 2.0 (the "License");
011 * you may not use this file except in compliance with the License.
012 * You may obtain a copy of the License at
013 *
014 *      http://www.apache.org/licenses/LICENSE-2.0
015 *
016 * Unless required by applicable law or agreed to in writing, software
017 * distributed under the License is distributed on an "AS IS" BASIS,
018 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
019 * See the License for the specific language governing permissions and
020 * limitations under the License.
021 * ##########################################################################
022 */
023import ball.game.scrabble.Bag;
024import ball.game.scrabble.Tile;
025import ball.game.scrabble.WordList;
026import ball.swing.table.MapTableModel;
027import ball.util.ant.taskdefs.AntTask;
028import ball.util.ant.taskdefs.NotNull;
029import java.util.ArrayList;
030import java.util.Collection;
031import java.util.HashMap;
032import java.util.HashSet;
033import lombok.Getter;
034import lombok.NoArgsConstructor;
035import lombok.Setter;
036import lombok.ToString;
037import org.apache.tools.ant.BuildException;
038
039/**
040 * {@link.uri http://ant.apache.org/ Ant} {@link org.apache.tools.ant.Task}
041 * to solve
042 * {@link.uri http://fivethirtyeight.com/features/this-challenge-will-boggle-your-mind/ First, for Riddler Express, a Scrabble problem:}
043 * <p>
044 * What is the longest word you can build in a game of Scrabble one letter
045 * at a time? That is, starting with a valid two-letter word, how long a
046 * word can you build by playing one letter at a time on either side to form
047 * a valid three-letter word, then a valid four-letter word, and so on? (For
048 * example, HE could become THE, then THEM, then THEME, then THEMES, for a
049 * six-letter result.)
050 * </p>
051 * {@ant.task}
052 * <p>
053 * The generated solutions:
054 * </p>
055<pre>
056CLASSISMS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+M, CLASSISM+S]
057CLASSISTS [AS, AS+S, L+ASS, LASS+I, LASSI+S, C+LASSIS, CLASSIS+T, CLASSIST+S]
058RELAPSERS [LA, LA+P, LAP+S, LAPS+E, E+LAPSE, R+ELAPSE, RELAPSE+R, RELAPSER+S]
059GLASSIEST [AS, AS+S, L+ASS, LASS+I, LASSI+E, LASSIE+S, G+LASSIES, GLASSIES+T]
060SCRAPINGS [PI, PI+N, PIN+G, A+PING, R+APING, C+RAPING, S+CRAPING, SCRAPING+S]
061SHEATHERS [AT, E+AT, EAT+H, H+EATH, S+HEATH, SHEATH+E, SHEATHE+R, SHEATHER+S]
062UPRAISERS [IS, A+IS, R+AIS, RAIS+E, P+RAISE, PRAISE+R, PRAISER+S, U+PRAISERS]
063</pre>
064 *
065 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
066 * @version $Revision: 5431 $
067 */
068@AntTask("solve-express-2016-10-21")
069@NoArgsConstructor @ToString
070public class SolveExpress20161021Task extends AbstractTask {
071    @NotNull @Getter @Setter
072    private String list = null;
073    private WordList wordlist = null;
074
075    @Override
076    public void execute() throws BuildException {
077        super.execute();
078
079        try {
080            wordlist = (WordList) getClassForName(getList()).newInstance();
081
082            SolutionMap previous = new SolutionMap();
083            SolutionMap next = new SolutionMap();
084
085            wordlist.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);
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}