C: Carrol’s Scrabble Source file name: carrol.c, carrol.cpp, carrol.java, or carrol.py Author: Mario Sánchez In the Christmas Eve of 1877, Lewis Carroll invented a game called Word Links (it was later renamed to Doublets when Vanity Fair published it in 1879). In Word Links, a player is given a challenge consisting of two words with the goal of finding a sequence of valid English words that starts from the first word and ends with the second word. Two words can be linked in such a sequence if and only if they have the same number of letters and they either differ by a single letter or are anagrams of each other. For example, the following is a valid sequence from iron to lead with length 7: iron icon (replace c for r in iron to get icon) coin (reorganize the letters in icon to obtain coin) corn (replace r for i in coin to get corn) cord (replace d for n in corn to get cord) lord (replace l for c in cord to get lord) load (replace a for r in lord to get load) lead (replace e for o in load to get lead). In Carroll’s version of the game, the solution of a challenge is the shortest sequence between the two given words. It is possible to have multiple solutions, namely, different sequences of the same length can have the same initial and final words. With the idea of Scrabble in mind, the World Links game can become Carroll’s Scrabble and be more interesting. A solution to a Carroll’s Scrabble challenge is a shortest sequence that maximizes the sum of the values of the words in it (when ignoring the two words given in the challenge). The value of each word is obtained by summing the value of its letters by the following rules (capitalization is ignored): • Letterswith1point: e,a,i,o,n,r,t,l,s,u. • Letters with 2 points: d, g. • Letters with 3 points: b, c, m, p. • Letters with 4 points: f, h, v, w, y. • Letters with 5 points: k. • Letters with 8 points: j, x. • Letters with 10 points: q, z. For example, the total value of the previous sequence from iron to lead is 35: 6 points for icon, 6 points for coin, 6 points for corn, 7 points for cord, 5 points for lord, and 5 points for load. Note that the values of iron and lead have been omitted. Given a dictionary of valid words that can be used in Carroll’s Scrabble, you are asked to compute the value of optimal solutions to several challenges of the game.
2018 ACIS REDIS - XXXII Colombian Programming Contest - ACM ICPC 5 Input The input provides a dictionary and challenges to solve. The input begins with a line containing an integer N (0 < N < 10 000) representing the number of words in the dictionary; you can assume that no word is repeated in the dictionary. Each of the next N lines provides a word available from the dictionary: each line has a single non-empty word with at most 20 lower case letters. The next line contains an integer Q (0 < Q < 200) representing the number of challenges to solve. Each of the next Q lines follows the pattern word1 TO word2 where word1 and word2 are words in the dictionary. The input must be read from standard input. Output Output a single line for each challenge. If the challenge has a solution, use the format word1 TO word2 NS Val where word1 and word2 are the words in the given challenge, NS is the minimum number of steps required to go from word1 to word2, and Val is the maximum value of the words in such an optimal sequence. Remember that the values of word1 and word2 must not be included in the total value Val of the sequence. If the challenge does not have a solution, use the format word1 TO word2 IMPOSSIBLE The output must be written to standard output. Sample Input 14 hot iron icon coin corn cord lord load lead lion cold gold worm warm 5 iron TO lead lead TO gold iron TO icon warm TO hot warm TO cold Sample Output iron TO lead 7 35 lead TO gold 5 24 iron TO icon 1 0 warm TO hot IMPOSSIBLE warm TO cold IMPOSSIBLE