Source code

001package ball.game.crossword;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * %%
006 * Copyright (C) 2010 - 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.util.Coordinate;
022import ball.util.CoordinateMap;
023import ball.util.DispatchSpliterator;
024import java.io.BufferedReader;
025import java.io.FileInputStream;
026import java.io.IOException;
027import java.io.InputStream;
028import java.io.InputStreamReader;
029import java.io.OutputStream;
030import java.io.OutputStreamWriter;
031import java.io.PrintWriter;
032import java.io.UncheckedIOException;
033import java.io.Writer;
034import java.util.ArrayList;
035import java.util.Collection;
036import java.util.Comparator;
037import java.util.IdentityHashMap;
038import java.util.LinkedHashMap;
039import java.util.LinkedList;
040import java.util.List;
041import java.util.Map;
042import java.util.Objects;
043import java.util.Set;
044import java.util.Spliterator;
045import java.util.TreeMap;
046import java.util.TreeSet;
047import java.util.function.Supplier;
048import java.util.regex.Pattern;
049import java.util.stream.Stream;
050import java.util.stream.StreamSupport;
051import lombok.ToString;
052
053import static java.nio.charset.StandardCharsets.UTF_8;
054import static java.util.Collections.copy;
055import static java.util.Collections.disjoint;
056import static java.util.Collections.indexOfSubList;
057import static java.util.Collections.unmodifiableList;
058import static java.util.Collections.unmodifiableMap;
059import static java.util.stream.Collectors.joining;
060import static java.util.stream.Collectors.toCollection;
061import static java.util.stream.Collectors.toList;
062import static java.util.stream.Collectors.toMap;
063import static org.apache.commons.lang3.StringUtils.EMPTY;
064import static org.apache.commons.lang3.StringUtils.SPACE;
065import static org.apache.commons.lang3.StringUtils.isBlank;
066import static org.apache.commons.lang3.StringUtils.isNotBlank;
067
068/**
069 * Crossword {@link Puzzle}.
070 *
071 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
072 */
073@ToString
074public class Puzzle extends CoordinateMap<Cell> implements Cloneable {
075    private static final long serialVersionUID = 5580701146811926874L;
076
077    private static final List<String> BOUNDARY = List.of(EMPTY, EMPTY);
078
079    private static final String COLON = ":";
080    private static final String DOT = ".";
081    private static final String TILDE = "~";
082
083    /** @serial */
084    private final Puzzle parent;
085    /** @serial */
086    private final Map<String,String> headers;
087    /** @serial */
088    private final List<Coordinate> indices;
089    /** @serial */
090    private final Map<Label,Solution> solutions;
091    /** @serial */
092    private final IdentityHashMap<Solution,List<Solution>> xref;
093    /** @serial */
094    private final Map<Label,String> clues;
095    /** @serial */
096    private final List<String> notes;
097
098    /**
099     * Private constructor for {@link Spliterator} implmentation.
100     *
101     * @param   parent          The source {@link Puzzle}.
102     * @param   solution        The {@link Solution} to update.
103     * @param   sequence        The {@link CharSequence} for the
104     *                          {@link Solution}.
105     */
106    private Puzzle(Puzzle parent, Solution solution, CharSequence sequence) {
107        this(parent);
108
109        try {
110            for (var coordinate : solution) {
111                put(coordinate, parent.get(coordinate).clone());
112            }
113
114            solution.setSolution(this, sequence);
115        } catch (Exception exception) {
116            throw new ExceptionInInitializerError(exception);
117        }
118    }
119
120    /**
121     * Private constructor for {@link #clone()}.
122     *
123     * @param   parent          The source {@link Puzzle}.
124     */
125    private Puzzle(Puzzle parent) {
126        this(parent,
127             parent.headers,
128             parent.indices, parent.solutions, parent.xref,
129             parent.clues, parent.notes);
130
131        this.putAll(parent);
132    }
133
134    /**
135     * Private constructor for {@link #load(String)}.
136     *
137     * @param   headers         The {@link List} of header {@link String}s.
138     * @param   grid            The {@link List} of grid row
139     *                          {@link String}s.
140     * @param   clues           The {@link List} of clue {@link String}s.
141     * @param   notes           The {@link List} of note {@link String}s.
142     */
143    private Puzzle(List<String> headers, List<String> grid, List<String> clues, List<String> notes) {
144        this(null,
145             new OrderedHeaders(headers),
146             new ArrayList<>(), new TreeMap<>(), new IdentityHashMap<>(),
147             new TreeMap<>(), (notes != null) ? notes : new LinkedList<>());
148        /*
149         * Populate the grid.
150         */
151        for (var line : grid) {
152            var row = Cell.getRowFrom(line.trim());
153
154            if ((getColumnCount() * getRowCount()) > 0) {
155                if (getColumnCount() != row.size()) {
156                    throw new IllegalArgumentException(line + " does not have " + getColumnCount() + " columns");
157                }
158            }
159
160            resize(getRowCount() + 1, row.size());
161            copy(row(getRowCount() - 1).asList(), row);
162        }
163        /*
164         * Find the Coordinate groups that represent solutions.
165         */
166        List<CoordinateMap<Cell>> groups = new LinkedList<>();
167        var stream = Stream.concat(rows().stream(), columns().stream());
168
169        for (var line : (Iterable<CoordinateMap<Cell>>) stream::iterator) {
170            groups.add(new CoordinateMap<Cell>());
171
172            for (var entry : line.entrySet()) {
173                if (! entry.getValue().isBlock()) {
174                    groups.get(groups.size() - 1)
175                        .put(entry.getKey(), entry.getValue());
176                } else {
177                    groups.add(new CoordinateMap<Cell>());
178                }
179            }
180        }
181
182        groups.removeIf(t -> ! (t.size() > 1));
183        /*
184         * Calculate the Label indices.
185         */
186        var indices =
187            groups.stream()
188            .map(t -> t.firstKey())
189            .collect(toCollection(TreeSet::new));
190
191        this.indices.addAll(indices);
192        /*
193         * Populate the solutions and xref maps.
194         */
195        var solutions =
196            groups.stream()
197            .collect(toMap(k -> labelFor(k), v -> new Solution(v.keySet()), (v0, v1) -> v0, TreeMap::new));
198
199        this.solutions.putAll(solutions);
200
201        var values = this.solutions.values();
202        var xref =
203            values.stream()
204            .collect(toMap(k -> k,
205                           v -> (values.stream()
206                                 .filter(t -> t != v)
207                                 .filter(t -> (! disjoint(t, v)))
208                                 .collect(toList())),
209                           (v0, v1) -> v0, IdentityHashMap::new));
210
211        this.xref.putAll(xref);
212        /*
213         * Populate the clues map.
214         */
215        if (clues != null) {
216            clues.stream()
217                .filter(t -> isNotBlank(t))
218                .map(t -> t.split("[. ]+", 2))
219                .forEach(t -> this.clues.put(Label.parse(t[0]), t[1]));
220        }
221
222        var labels = this.clues.keySet().stream().collect(toList());;
223
224        labels.removeAll(this.solutions.keySet());
225
226        for (var label : labels) {
227            throw new IllegalArgumentException("`" + label + "' not found in grid'");
228        }
229
230        for (Map.Entry<Label,String> entry : this.clues.entrySet()) {
231            var strings = entry.getValue().split("[~]", 2);
232
233            if (strings.length > 1) {
234                entry.setValue(strings[0].trim());
235
236                if (isNotBlank(strings[1])) {
237                    solutions.get(entry.getKey()).setSolution(this, strings[1].trim());
238                }
239            }
240        }
241
242        this.solutions.keySet().stream()
243            .forEach(t -> this.clues.computeIfAbsent(t, k -> "TBD"));
244    }
245
246    private Puzzle(Puzzle parent, Map<String,String> headers, List<Coordinate> indices, Map<Label,Solution> solutions, IdentityHashMap<Solution,List<Solution>> xref, Map<Label,String> clues, List<String> notes) {
247        super();
248
249        this.parent = parent;
250        this.headers = headers;
251        this.indices = indices;
252        this.solutions = solutions;
253        this.xref = xref;
254        this.clues = clues;
255        this.notes = notes;
256    }
257
258    private Label labelFor(CoordinateMap<Cell> map) {
259        return new Label(Direction.of(map), indices.indexOf(map.firstKey()) + 1);
260    }
261
262    /**
263     * Method to get the "seed" of this {@link Puzzle}.
264     *
265     * @return  {@link.this} if {@link #parent()} is {@code null}; the
266     *          ultimate (first) {@link #parent()} otherwise.
267     */
268    public Puzzle seed() {
269        Puzzle seed = this;
270
271        while (seed.parent() != null) {
272            seed = seed.parent();
273        }
274
275        return seed;
276    }
277
278    /**
279     * Method to get the parent of this {@link Puzzle}.
280     *
281     * @return  The parent of {@link.this} {@link Puzzle} (may be
282     *          {@code null}).
283     */
284    public Puzzle parent() { return parent; }
285
286    public Map<String,String> headers() { return unmodifiableMap(headers); }
287
288    public Map<Label,Solution> solutions() {
289        return unmodifiableMap(solutions);
290    }
291
292    public Map<Label,String> clues() { return unmodifiableMap(clues); }
293
294    public List<String> notes() { return unmodifiableList(notes); }
295
296    /**
297     * Method to set the solution in a {@link Puzzle}.
298     *
299     * @param   coordinate      The {@link Coordinate} of the {@link Cell}..
300     * @param   character       The solution {@link Character}.
301     *
302     * @throws  IllegalArgumentException
303     *                          If any of the {@link Cell}s are already with
304     *                          a different {@link Character} than specified
305     *                          in the {@link String}.
306     */
307    public void setSolution(Coordinate coordinate, Character character) {
308        var cell = get(coordinate);
309
310        if (cell == null) {
311            throw new IllegalStateException();
312        }
313
314        if (! cell.isSolved()) {
315            cell.setSolution(character);
316        } else {
317            if (! character.equals(cell.getSolution())) {
318                throw new IllegalArgumentException(coordinate.toString() + ": " + cell.toString()
319                                                   + " -> " + character.toString());
320            }
321        }
322    }
323
324    /**
325     * Method to determine if {@link.this} {@link Puzzle} is solved.
326     *
327     * @return      {@code true} if the {@link Puzzle} is complete;
328     *              {@code false} otherwise.
329     */
330    public boolean isSolved() {
331        return values().stream().allMatch(Cell::isSolved);
332    }
333
334    /**
335     * Method to write {@link Puzzle} to an {@link OutputStream} in
336     * {@link.uri https://github.com/century-arcade/xd target=newtab .xd}
337     * format.
338     *
339     * @param   out             The {@link OutputStream}.
340     *
341     * @throws  IOException     If the {@link Puzzle} cannot be written.
342     */
343    public void writeTo(OutputStream out) throws IOException {
344        writeTo(new OutputStreamWriter(out, UTF_8));
345    }
346
347    /**
348     * Method to write {@link Puzzle} to a {@link Writer} in
349     * {@link.uri https://github.com/century-arcade/xd target=newtab .xd}
350     * format.
351     *
352     * @param   out             The {@link OutputStream}.
353     *
354     * @throws  IOException     If the {@link Puzzle} cannot be written.
355     */
356    public void writeTo(Writer out) throws IOException {
357        writeTo((out instanceof PrintWriter) ? ((PrintWriter) out) : new PrintWriter(out));
358    }
359
360    /**
361     * Method to write {@link Puzzle} to a {@link PrintWriter} in
362     * {@link.uri https://github.com/century-arcade/xd target=newtab .xd}
363     * format.
364     *
365     * @param   out             The {@link OutputStream}.
366     *
367     * @throws  IOException     If the {@link Puzzle} cannot be written.
368     */
369    public void writeTo(PrintWriter out) throws IOException {
370        for (var entry : headers().entrySet()) {
371            if (isNotBlank(entry.getValue())) {
372                out.println(entry.getKey() + COLON + SPACE + entry.getValue());
373            }
374        }
375
376        out.println(EMPTY);
377        out.println(EMPTY);
378
379        for (var row : rows()) {
380            for (var cell : row.values()) {
381                out.print(cell);
382            }
383
384            out.println();
385        }
386
387        out.println(EMPTY);
388
389        Direction last = null;
390
391        for (var entry : clues.entrySet()) {
392            if (! entry.getKey().getDirection().equals(last)) {
393                out.println(EMPTY);
394            }
395
396            last = entry.getKey().getDirection();
397
398            out.println(entry.getKey().toString() + DOT + SPACE + entry.getValue()
399                        + SPACE + TILDE + SPACE + solutions.get(entry.getKey()).getSolution(this));
400        }
401
402        if (! notes.isEmpty()) {
403            out.println(EMPTY);
404            out.println(EMPTY);
405
406            notes.stream().forEach(out::println);
407        }
408    }
409
410    /**
411     * Method to solve a {@link Puzzle}.
412     *
413     * @param   dictionary      The {@link Set} of possible solutions.
414     *
415     * @return  A {@link Stream} of possible solutions.
416     */
417    public Stream<Puzzle> solve(Set<CharSequence> dictionary) {
418        return StreamSupport.stream(new Solver(this, dictionary), false);
419    }
420
421    private boolean isChanged(Coordinate coordinate) {
422        return (parent == null || (get(coordinate) != parent.get(coordinate)));
423    }
424
425    private Map<Coordinate,Cell> changed() {
426        var map =
427            entrySet().stream()
428            .filter(t -> parent != null)
429            .filter(t -> t.getValue() != parent.get(t.getKey()))
430            .collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (v0, v1) -> v0, TreeMap::new));
431
432        return map;
433    }
434
435    @Override
436    public Puzzle clone() throws CloneNotSupportedException {
437        return new Puzzle(this);
438    }
439
440    /**
441     * Static method to load an
442     * {@link.uri https://github.com/century-arcade/xd target=newtab .xd}
443     * resource or {@link FileInputStream File} into a {@link Puzzle}.
444     *
445     * @param   path            The resource path.
446     *
447     * @return  The {@link Puzzle}.
448     *
449     * @throws  IOException     If the path cannot be parsed.
450     */
451    public static Puzzle load(String path) throws IOException {
452        Puzzle puzzle = null;
453        InputStream in = null;
454
455        try {
456            in = Puzzle.class.getResourceAsStream(path);
457
458            if (in == null) {
459                in = new FileInputStream(path);
460            }
461
462            var lines =
463                new BufferedReader(new InputStreamReader(in, UTF_8)).lines()
464                .map(t -> t.trim())
465                .collect(toList());
466            TreeMap<Integer,List<String>> sections = new TreeMap<>();
467
468            while (! lines.isEmpty()) {
469                var index = indexOfSubList(lines, BOUNDARY);
470
471                if (! (index < 0)) {
472                    sections.put(sections.size(), lines.subList(0, index));
473                    lines = lines.subList(index + BOUNDARY.size(), lines.size());
474                } else {
475                    sections.put(sections.size(), lines);
476                    break;
477                }
478            }
479
480            puzzle = new Puzzle(sections.get(0), sections.get(1), sections.get(2), sections.get(3));
481        } catch (UncheckedIOException exception) {
482            throw exception.getCause();
483        } finally {
484            if (in != null) {
485                in.close();
486            }
487        }
488
489        return puzzle;
490    }
491
492    private static class OrderedHeaders extends LinkedHashMap<String,String> {
493        private static final long serialVersionUID = -6640158167374093950L;
494
495        private static final List<String> HEADERS =
496            List.of("Title", "Author", "Editor", "Special", "Rebus", "Date");
497
498        public OrderedHeaders(Collection<String> lines) {
499            super();
500
501            HEADERS.stream().forEach(t -> put(t, EMPTY));
502
503            if (lines != null) {
504                lines.stream()
505                    .filter(t -> isNotBlank(t))
506                    .map(t -> t.split(Pattern.quote(COLON), 2))
507                    .filter(t -> isNotBlank(t[0]))
508                    .forEach(t -> put(t[0].trim(), (t.length > 1) ? t[1].trim() : EMPTY));
509            }
510
511            values().removeIf(t -> isBlank(t));
512        }
513    }
514
515    /**
516     * {@link Puzzle} {@link Solution Solution}.
517     */
518    public static class Solution extends ArrayList<Coordinate> {
519        private static final long serialVersionUID = -146821930642639986L;
520
521        private Solution(Collection<Coordinate> collection) {
522            super(collection);
523        }
524
525        /**
526         * Method to get the {@link CharSequence} of a {@link Puzzle}
527         * {@link Solution Solution}.
528         *
529         * @param       puzzle  The {@link Puzzle}.
530         *
531         * @return      The {@link Solution} {@link CharSequence}.
532         */
533        public CharSequence getSolution(Puzzle puzzle) {
534            return (stream()
535                    .map(t -> puzzle.get(t))
536                    .map(Object::toString)
537                    .collect(joining()));
538        }
539
540        private void setSolution(Puzzle puzzle, CharSequence solution) {
541            if (solution.length() != size()) {
542                throw new IllegalArgumentException();
543            }
544
545            for (var i = 0; i < size(); i += 1) {
546                puzzle.setSolution(get(i), solution.charAt(i));
547            }
548        }
549
550        /**
551         * Method to determine if {@link.this} {@link Solution Solution} is
552         * solved.
553         *
554         * @param       puzzle  The {@link Puzzle}.
555         *
556         * @return      {@code true} if the {@link Solution} is complete;
557         *              {@code false} otherwise.
558         */
559        public boolean isSolved(Puzzle puzzle) {
560            return stream().map(t -> puzzle.get(t)).allMatch(Cell::isSolved);
561        }
562
563        private Pattern asPattern(Puzzle puzzle) {
564            var string = getSolution(puzzle).toString().toUpperCase();
565
566            return Pattern.compile(string);
567        }
568
569        private List<Coordinate> unsolved(Puzzle puzzle) {
570            return (stream()
571                    .filter(t -> (! puzzle.get(t).isSolved()))
572                    .collect(toList()));
573        }
574    }
575
576    @ToString
577    private static class Solver extends DispatchSpliterator<Puzzle> {
578        private final Puzzle parent;
579        private final Set<CharSequence> dictionary;
580
581        public Solver(Puzzle parent, Set<CharSequence> dictionary) {
582            super(Integer.MAX_VALUE, Spliterator.NONNULL);
583
584            this.parent = Objects.requireNonNull(parent);
585            this.dictionary = Objects.requireNonNull(dictionary);
586        }
587
588        public Comparator<Solution> prioritization() {
589            var comparator =
590                Comparator
591                .<Solution>comparingInt(t -> (t.stream()
592                                              .map(c -> parent.get(c))
593                                              .anyMatch(Cell::isSolved) ? +1 : -1))
594                .thenComparingInt(t -> t.unsolved(parent).size())
595                .thenComparingInt(Solution::size)
596                .reversed();
597
598            return comparator;
599        }
600
601        @Override
602        protected Spliterator<Supplier<Spliterator<Puzzle>>> spliterators() {
603            List<Supplier<Spliterator<Puzzle>>> list = new LinkedList<>();
604            var solution =
605                parent.solutions().values().stream()
606                .filter(t -> (! t.isSolved(parent)))
607                .sorted(prioritization())
608                .findFirst().orElse(null);
609
610            if (solution != null) {
611                var pattern = solution.asPattern(parent);
612                var sequences =
613                    dictionary.stream()
614                    .filter(t -> pattern.matcher(t).matches())
615                    .collect(toList());
616                var used =
617                    parent.solutions().values().stream()
618                    .filter(t -> t.isSolved(parent))
619                    .map(t -> t.getSolution(parent))
620                    .collect(toList());
621
622                sequences.removeAll(used);
623
624                for (var sequence : sequences) {
625                    var child = new Puzzle(parent, solution, sequence);
626                    var changed = child.changed().keySet();
627                    var verified =
628                        child.xref.get(solution).stream()
629                        .filter(t -> (! disjoint(t, changed)))
630                        .filter(t -> t.isSolved(child))
631                        .allMatch(t -> dictionary.contains(t.getSolution(child)));
632
633                    if (verified) {
634                        list.add(() -> new Solver(child, dictionary));
635                    }
636                }
637            }
638
639            if (list.isEmpty()) {
640                list.add(() -> Stream.of(parent).spliterator());
641            }
642
643            return list.spliterator();
644        }
645    }
646}