25
\$\begingroup\$

Given a word (or any sequence of letters) as input, you must interpolate between each letter such that each adjacent pair of letters in the result is also adjacent on a QWERTY keyboard, as if you typed the input by walking on a giant keyboard. For example, 'yes' might become 'ytres', 'cat' might become 'cxzawert'.

Rules:

  • This is the keyboard format you should use:

    qwertyuiop
    asdfghjkl
      zxcvbnm

    Any pair of keys which is touching in this layout is considered adjacent. For instance, 's' and 'e' are ajacent, but 's' and 'r' are not.

  • The input "word" will consist of any sequence of letters. It will have only letters, so you don't have do deal with special characters.
  • The input can be in any convenient form: stdin, a string, a list, etc. Letter case does not matter; you can take whatever is more convenient.
  • The output can be in any convenient form: stdout, a string, a list, etc. Letter case does not matter, and it does not need to be consistent.
  • Any path across the keyboard is valid, except that you cannot cross the previous letter again before getting to the next letter. For example, 'hi' could become 'hji' or 'hjnbgyui', but not 'hbhui'.
  • A letter is not ajacent with itself, so 'poll' cannot become 'poll'. Instead it would need to become something like 'polkl'.
  • No output letters are allowed before or after the word. For example, 'was' cannot become 'trewas' or 'wasdfg'.

This is code golf, the shortest answer in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ So we're outputting any valid 'walk' per input? This seems like it'd be better as given two inputs, determine if it's a valid walk. \$\endgroup\$
    – Veskah
    Dec 6, 2018 at 21:17
  • \$\begingroup\$ It seems like dewqwerty is a valid path for dy. Could you confirm that? \$\endgroup\$
    – Arnauld
    Dec 6, 2018 at 21:27
  • \$\begingroup\$ @Arnauld yes, it is. \$\endgroup\$
    – Vaelus
    Dec 6, 2018 at 21:47
  • \$\begingroup\$ @Veskah That's right; output any valid walk for an input. This is to allow for optimizations which might not be possible if, for instance, it had to be a shortest walk. \$\endgroup\$
    – Vaelus
    Dec 6, 2018 at 21:48

7 Answers 7

16
\$\begingroup\$

Python 2, 83 bytes

lambda s:re.findall('.*?'.join(s),'qwertyuioplkmnjhbvgfcxdsza'*len(s))[0]
import re

Try it online!

Walks the entire keyboard until the word is written.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ How come the import re comes after the code, not before? \$\endgroup\$
    – BruceWayne
    Dec 7, 2018 at 20:44
  • \$\begingroup\$ @BruceWayne The re.findall would be evaluated when the lambda runs, so importing after the lambda's definition is ok. That being said, it is clearer to import before, there's just no need to \$\endgroup\$
    – pushkin
    Dec 7, 2018 at 23:17
  • \$\begingroup\$ @pushkin ah, I didn't know that thanks for clarifying! Did you import after just as a personal preference/choice or does it help with byte count at all? \$\endgroup\$
    – BruceWayne
    Dec 7, 2018 at 23:25
  • 2
    \$\begingroup\$ @BruceWayne It's a bit of a convention for this forum. It's just so that it works with the way the TiO site organizes the code. Try clicking on the "Try it online!" link to see what I mean. \$\endgroup\$
    – mypetlion
    Dec 7, 2018 at 23:27
  • 1
    \$\begingroup\$ @Makonede Doesn't work for the second case ("cat") \$\endgroup\$
    – TFeld
    Jan 27 at 8:53
9
\$\begingroup\$

Python 2 + NetworkX, 274 bytes (optimal solution)

296 300 302 308 315 319 324 327 328 430 432 bytes

-4 bytes thanks to mypetlion

from networkx import*
i=input()
M,z='qwertyuiop  asdfghjkl   zxcvbnm'.center(55),i[:1]
G=from_edgelist([(M[e],M[e+h])for h in[-1,1,11,12,-11,-12]for e in range(44)if' '!=M[e]and' '!=M[e+h]])
for y,x in zip(i,i[1:]):z+=[shortest_path(G,y,x)[1:],list(G[y])[0]+y][x==y]
print z

Try it online!

This solution gives the shortest possible output. The keyboard is transformed into a graph used to find the shortest path to compute the output string:

puzzles     --> poiuhbvcxzazxcvbhjklkiuytres
programming --> poiuytrtyuioijhgtresasdcvbnmkmkijnbg
code        --> cvbhjioijhgfde
golf        --> ghjiolkjhgf
yes         --> ytres
hi          --> hji
poll        --> polpl
\$\endgroup\$
2
  • \$\begingroup\$ 274 bytes: Try it online! \$\endgroup\$
    – mypetlion
    Dec 11, 2018 at 20:17
  • 1
    \$\begingroup\$ @mypetlion u made an important reduction, u can update the answer :) \$\endgroup\$
    – mdahmoune
    Dec 11, 2018 at 20:56
7
\$\begingroup\$

Japt -g, 23 bytes

;D·ÎÔ+D·Årí)pUl)fUq".*?

Try it online!

Takes input as an array of capital letters. Very similar to the other answers otherwise.

Explanation:

;                          :Set D to the keyboard layout
 D·Î                       :Get the first row of keys
    Ô                      :Reversed
     +                     :Concat
      D·Å                  :The other two rows
         rí)               :Interleaved
            p              :Repeat that string
             Ul)           : A number of times equal to the length of the input
                f          :Get the substrings that match
                 U         : The input
                  q".*?    : joined with ".*?"
                           :Implicitly output just once of the matches
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 70 bytes

Same strategy as TFeld.

s=>'qazsxdcfvgbhnjmklpoiuytrew'.repeat(s.length).match(s.join`.*?`)[0]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ -3 by outputting a singleton list (remove [0]). \$\endgroup\$
    – Makonede
    Jan 26 at 21:56
4
\$\begingroup\$

Charcoal, 48 bytes

≔”&⌈″⌊5EWXVNa…-εW¶ζR”η≔⌕η§θ⁰ζFθF⊕﹪⁻⌕ηιζ²⁶«§ηζ≦⊕ζ

Try it online! Link is to verbose version of code. Explanation:

≔”&⌈″⌊5EWXVNa…-εW¶ζR”η

Get the string qwertyuioplkmjnhbgvfcdxsza.

≔⌕η§θ⁰ζ

Find the position of the first character of the word. This index is normally one past the character just reached, but this value fakes out the first iteration of the loop to print the first character of the word.

Fθ

Loop over each character.

F⊕﹪⁻⌕ηιζ²⁶«

Compute how many characters to print to include the next character of the word and loop that many times.

§ηζ≦⊕ζ

Print the next character cyclically indexed and increment the index.

\$\endgroup\$
2
  • \$\begingroup\$ Have you tried rotating the string “qwertyuioplkmjnhbgvfcdxsza” and seeing if any of the rotations happen to be more compressible? I'm not familiar with charcoal's compression; maybe this isn't possible. \$\endgroup\$
    – Vaelus
    Dec 8, 2018 at 0:06
  • \$\begingroup\$ @Vaelus I don't know either so I tried all 26 rotations but they all compress to 20 bytes. Of course, those aren't all of the possible walks... \$\endgroup\$
    – Neil
    Dec 8, 2018 at 1:04
4
\$\begingroup\$

05AB1E, 43 33 31 bytes

ü2εUžV`.ιJsRìD«Œ.ΔнÅ?XyθÅ¿}¨}JIθ«

Not the right language for this challenge, since it cannot use regex like the other answers did.. EDIT: proven wrong by @Makonede's 05AB1E answer using the Elixir eval builtin .E.

Try it online or verify all test cases.

Explanation:

ü2             # Split the input into overlapping pairs
               #  i.e. "poll" → ["po","ol","ll"]
  ε            # Map each to:
   U           #  Pop and store the current pair in variable `X`
   žV          #  Push ["qwertyuiop","asdfghjkl","zxcvbnm"]
     `         #  Pop and push all three separated to the stack
      .ι       #  Interweave the top two with each other
        J      #  Join the list of characters to a single string
               #   → "azsxdcfvgbhnjmkl"
         s     #  Swap so "qwertyuiop" is at the top
          R    #  Reverse it to "poiuytrewq"
           ì   #  Prepend it in front of the earlier string
               #   → "poiuytrewqazsxdcfvgbhnjmkl"
            D« #  Duplicate it, and append it to itself
               #   → "poiuytrewqazsxdcfvgbhnjmklpoiuytrewqazsxdcfvgbhnjmkl"
   Π          #  Get all substrings of this strings
    .Δ         #  Find the first substring which is truthy for:
      Á        #   Rotate the current string once towards the right
       2£      #   Only leave the first 2 letters
         R     #   Reverse it
          XQ   #   Check if it's equal to pair `X`
     }¨        #  After the find_first, remove the last character
  }            # Close the map
   J           # Join everything together
    Iθ«        # Append the last character of the input
               # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 51 39 38 bytes

-1 thanks to Kevin Cruijssen.

gžV`.ιJsRì×s….*?ý’RŽ½™«.‡Ð~r/ÿ/,"ÿ"’.E

Try it online! Takes input as a list of lowercase letters and outputs as a singleton list.

This answer exists to prove Kevin Cruijssen wrong; you can use regex in 05AB1E.

\$\endgroup\$
1
  • \$\begingroup\$ Nice answer! I didn't knew you could use the Elixir eval to use Regex like that. I need to remember that for sure. :) (PS: My answer was posted before the new 05AB1E version was live. But I assume using the Python eval .E in the legacy version should be possible as well.) I've also just golfed my answer a bit, and one golf can also be applied to your answer: žVćRs`.ιJ« to žV`.ιJsRì for -1. \$\endgroup\$ Jan 27 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.