This is a code-challenge with a custom scoring system, where the lowest score wins.
Many smartphones allow to enter text by swiping your finger across the 2D virtual keyboard. This technology is usually combined with a prediction algorithm that outputs a list of guessed words, sorted from most likely to least likely.
In this challenge:
- We are going to swipe across a one-dimensional keyboard restricted to a subset of the 26 letters.
- There will be no prediction algorithm: we want each word to be uniquely identified by its 'swipe sequence'.
- We want the keyboard to be optimized in such a way that the total number of moves for a given list of words is minimized.
Swiping in one dimension
Below is a lexicographically sorted 1D keyboard with all letters:
NB: This may be displayed on several rows if you're browsing from mobile. Please think of it as a single row.
To enter the word 'GOLF' on such a keyboard, we will:
- start at G
- swipe to the right to O
- swipe to the left to F
Because L is located between O and F, we just go on swiping without stopping there.
So the swipe sequence of 'GOLF' on this keyboard is GOF.
- The first and last letters are always included.
- Other letters are included if and only if a direction change is required just after them.
Repeated letters must be treated the same way as single letters. For instance, on the above keyboard:
- 'LOOP' would be encoded as LP (with no stop on O)
- 'GOOFY' would be encoded as GOFY (the O is included because there's a direction change there -- not because it's doubled)
Let's consider the following list of words: ['PROGRAMMING', 'PUZZLES', 'AND', 'CODE', 'GOLF'].
We need 16 distinct letters to type these words, so we just need a 16-letter keyboard. The following one is -- again -- lexicographically sorted:
With this keyboard, the words will be encoded this way:
- PROGRAMMING: PRGRAMING (9 moves)
- PUZZLES: PZES (4 moves)
- AND: AND (3 moves)
- CODE: CODE (4 moves)
- GOLF: GOF (3 moves)
That's a total of 23 moves for all words.
But we can do much better with this keyboard:
- PROGRAMMING: PGMG (4 moves)
- PUZZLES: PS (2 moves)
- AND: AD (2 moves)
- CODE: CE (2 moves)
- GOLF: GF (2 moves)
for a total of only 12 moves.
For a given list of \$n\$ words, the score of a keyboard is given by:
where \$m_k\$ is the number of moves for the \$k\$-th word.
For instance, the two keyboards described in the previous paragraph would be scored \$9^2+4^2+3^2+4^2+3^2=131\$ and \$4^2+2^2+2^2+2^2+2^2=32\$ respectively.
The lower, the better.
- Given a list of words, your code must output a valid keyboard for this list. A keyboard is considered valid if each word generates a unique swipe sequence.
You'll be given 11 independent lists of words. Your score will be equal to:
$$S + L$$ where \$S\$ is the sum of the scores of your keyboards for all lists and \$L\$ is the length of your code in bytes.
You can use this script to check your score. The
score()function expects your code length as first parameter and an array of 11 keyboard strings as second parameter (the case doesn't matter).
The submission with the lowest score wins. In case of a tie, the submission that was submitted first wins.
- Your code must be deterministic (i.e. it must always return the same output for a given input).
- You must either A) provide a test link (e.g. on TIO) that does not time out, or B) include the generated keyboards within the body of your answer.
- You may take the words in either full uppercase or full lowercase. Mixed cases are forbidden.
- The input is guaranteed to have at least one solution.
- All words are made of at least 2 distinct letters.
- Your code must work for any valid input. It will be tested with an undisclosed list of words to make sure that it's not relying on hard-coded results.
- I reserve the right to increase the size of the test suite at any time to make sure that the submissions are not optimized for the initial test cases.
1) Sanity check #1 (only 4 valid solutions: HES, SEH, ESH or HSE) SEE, SHE 2) Sanity check #2 (16 valid solutions, of which 4 are optimal: COLD, DOLC, DLOC or CLOD) COLD, CLOD 3) Sanity check #3 ACCENTS, ACCESS 4) Warm-up RATIO, NATION, NITRO, RIOT, IOTA, AIR, ART, RAT, TRIO, TRAIN 5) Pangram THE, QUICK, BROWN, FOX, JUMPS, OVER, LAZY, DOG 6) Common prepositions TO, OF, IN, FOR, ON, WITH, AT, BY, FROM, UP, ABOUT, INTO, OVER, AFTER 7) Common verbs BE, HAVE, DO, SAY, GET, MAKE, GO, KNOW, TAKE, SEE, COME, THINK, LOOK, WANT, GIVE, USE, FIND, TELL, ASK, WORK, SEEM, FEEL, TRY, LEAVE, CALL 8) Common adjectives GOOD, NEW, FIRST, LAST, LONG, GREAT, LITTLE, OWN, OTHER, OLD, RIGHT, BIG, HIGH, DIFFERENT, SMALL, LARGE, NEXT, EARLY, YOUNG, IMPORTANT, FEW, PUBLIC, BAD, SAME, ABLE 9) Common nouns TIME, PERSON, YEAR, WAY, DAY, THING, MAN, WORLD, LIFE, HAND, PART, CHILD, EYE, WOMAN, PLACE, WORK, WEEK, CASE, POINT, GOVERNMENT, COMPANY, NUMBER, GROUP, PROBLEM, FACT 10) POTUS ADAMS, ARTHUR, BUCHANAN, BUREN, BUSH, CARTER, CLEVELAND, CLINTON, COOLIDGE, EISENHOWER, FILLMORE, FORD, GARFIELD, GRANT, HARDING, HARRISON, HAYES, HOOVER, JACKSON, JEFFERSON, JOHNSON, KENNEDY, LINCOLN, MADISON, MCKINLEY, MONROE, NIXON, OBAMA, PIERCE, POLK, REAGAN, ROOSEVELT, TAFT, TAYLOR, TRUMAN, TRUMP, TYLER, WASHINGTON, WILSON 11) Transition metals SCANDIUM, TITANIUM, VANADIUM, CHROMIUM, MANGANESE, IRON, COBALT, NICKEL, COPPER, ZINC, YTTRIUM, ZIRCONIUM, PLATINUM, GOLD, MERCURY, RUTHERFORDIUM, DUBNIUM, SEABORGIUM, BOHRIUM, HASSIUM, MEITNERIUM, UNUNBIUM, NIOBIUM, IRIDIUM, MOLYBDENUM, TECHNETIUM, RUTHENIUM, RHODIUM, PALLADIUM, SILVER, CADMIUM, HAFNIUM, TANTALUM, TUNGSTEN, RHENIUM, OSMIUM