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.

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.

Python 2, 300 bytes (optimal solution)

302 308 315 319 324 327 328 430 432 bytes

-4 bytes thanks to mypetlion

from networkx import*

i,q=input(),' '*12

M,j,z=q+'qwertyuiop  asdfghjkl   zxcvbnm'+q,1,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]])

while j<len(i):

	y=i[j-1]

	if y==i[j]:i[j:j]=list(G[y])[0]

	z+=shortest_path(G,y,i[j])[1:];j+=1

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

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

JavaScript (ES6), 70 bytes

Same strategy as TFeld.

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

Try it online!

05AB1E, 43 bytes

ü)Jε©žVćRs`.ιJ«D«Œʒg≠yн®нQyθ®θQ**}yªн¨}JIθ«

Not the right language for this challenge, since it cannot use regex like the other answers did..

Try it online or verify all test cases.

Explanation:

ü)               # Split the input into overlapping pairs

                 #  i.e. "poll" → ["p","o"],["o","l"],["l","l"]]

  J              # Join each inner list together

                 #  i.e. ["p","o"],["o","l"],["l","l"]] → ["po","ol","ll"]

   ε             # Map each to:

    ©            #  Store the current value in the register

    žV           #  Push ["qwertyuiop","asdfghjkl","zxcvbnm"]

    ćR           #  Extract the head, and reverse it

                 #   i.e. ["qwertyuiop","asdfghjkl","zxcvbnm"] → "poiuytrewq"

    s`           #  Swap to take the remainder, and push them to the stack

      .ι         #  And then interweave them with each other

                 #   i.e. ["asdfghjkl","zxcvbnm"]

                 #    → ["a","z","s","x","d","c","f","v","g","b","h","n","j","m","k","l"]

        J        #  Join the list to a single string

                 #   i.e. → "azsxdcfvgbhnjmkl"

         «       #  Merge them together

                 #   i.e. "qwertyuiop" and "azsxdcfvgbhnjmkl"

                 #    → "poiuytrewqazsxdcfvgbhnjmkl"

          D«     #  Duplicate it, and append it to itself

                 #   i.e. "poiuytrewqazsxdcfvgbhnjmkl"

                 #    → "poiuytrewqazsxdcfvgbhnjmklpoiuytrewqazsxdcfvgbhnjmkl"

            Π   #  Get all substrings of this strings

                 #   i.e. → ["p","po","poi",...,"k","kl","l"]

ʒ              } #  Filter this list by:

 g≠              #   Where the length is NOT 1 (otherwise pair "ll" would result in "l")

              *  #   and

   yн®нQ         #   Where the first character of the substring and pair are the same

             *   #   and

        yθ®θQ    #   Where the last character of the substring and pair are the same

                 #    i.e. "po" → 

                 #    i.e. "ll" → ["lazsxdcfvgbhnjmkl"]

yª               #  After filtering, append the current pair to the filtered list

                 #   i.e.  → ["po"]

                 #   i.e. ["lazsxdcfvgbhnjmkl"] → ["lazsxdcfvgbhnjmkl","ll"]

  н              #  Get the first item

                 #   ["po"] → "po"

                 #   ["lazsxdcfvgbhnjmkl","ll"] → "lazsxdcfvgbhnjmkl"

   ¨             #  Remove the last character

                 #   i.e. "po" → "p"

                 #   i.e. "lazsxdcfvgbhnjmkl" → "lazsxdcfvgbhnjmk"

}                # Close the map

 J               # Join everything together

                 #  i.e. ["p","o","lazsxdcfvgbhnjmk"] → "polazsxdcfvgbhnjmk"

  Iθ«            # And append the last character of the input

                 # (and output the result implicitly)

                 #  i.e. "polazsxdcfvgbhnjmk" and "poll" → "polazsxdcfvgbhnjmkl"

Charcoal, 48 bytes

≔”&⌈″⌊5ＥWＸＶＮa…-εW¶ζR”η≔⌕η§θ⁰ζＦθＦ⊕﹪⁻⌕ηιζ²⁶«§ηζ≦⊕ζ

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

≔”&⌈″⌊5ＥWＸＶＮa…-ε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.

Ｆθ

Loop over each character.

Ｆ⊕﹪⁻⌕ηιζ²⁶«

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.