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