Craptastic Program Search

Question

A certain well-known cable company has a somewhat clumsy 'Search for Program' feature that works through the remote. It takes muchly much button pushing; so, being an admirer of economy of motion, I thought I'd seek out a programmer's help to minimize the number of finger movements I have to make.

The Craptastic Search Feature features a layout of selectable cells, 1 row of 3 cells followed by 6 rows of 6 cells, that looks like this:

del spa sav
A B C D E F
G H I J K L
M N O P Q R
S T U V W X
Y Z 0 1 2 3
4 5 6 7 8 9

There are cells for each of the letters A-Z, and spa which is used to add a space to the search string. del is supposed to be used to delete a character; and sav is meant to be used to save the search string. We'll ignore these actual functions for this challenge; but the cells are otherwise still selectable for our purposes.

We start with an empty search string and the A cell selected; and we use left, right, up and down arrow buttons to change the selected cell. When the central 'OK' key is pushed, the character in the selected cell is added to the search string. For convenience, we'll use <,>,^,v and _ for left,right,up,down and OK, respectively.

For the letters and numbers, the action of the directional buttons is straightforward. There is no 'wrap-around'; for example, if the current cell is G, then < has no effect.

So to enter the search string BIG, we could use the sequence

>_>v_<<_

(the initial > is required to move us from the default starting cell A to the cell B). Alternatively, we could of course instead use >_v>_<<_; but note there is no shorter sequence than 8 keys that can do the job.

Now since the top row has only three cells, the action there is slightly different and complicates things a little:

First, if the selected cell is in the top letter row A-F, the ^ key moves the selected cell directly above; so A,B go to del, C,D go to spa and E,F go to sav.

One the other hand, if the selected cell is 'del', the v key moves the selected cell to A, and the > key makes the selected cell spa. Similarly v key moves the selected cell from spa to C, and sav to E.

This means that for example, if you are currently at the B cell, the sequence ^v does not return you to the B cell; instead it takes you to the A cell.

And starting at the A cell, the sequence v>>^moves us to the C cell; while the sequence ^>>v moves us to the the E cell.

The Challenge

Given a TV show or movie title s, consisting solely of characters in A-Z, 0-9 and space, your program/function should output one of the sequences of keypresses of minimal length to enter s as the search string from the starting state in Craptastic fashion.

Your output should be a string or a list of distinct values representing a sequence of up, down, right, left, and OK; so you are not restricted to the charset <>^v_ (e.g., udrl* or a list with integer elements 0,1,2,3,4 would be acceptable alternatives, so long as you articulate what your schema is).

This is code-golf; the usual loophole taboos apply. May the odds be ever in your favor for each language.

Test Cases

Below are inputs and an example acceptable answer (other different sequences will be correct as well, but must be of at most the length of the examples provided).

(I re-post the keypad here so one can more easily play along visually, if that is one's wont...)

del spa sav
A B C D E F
G H I J K L
M N O P Q R
S T U V W X
Y Z 0 1 2 3
4 5 6 7 8 9

BIG         >_>v_<<_
THE OFFICE  >vvv_^^_>>>^_^<_vvv_>>>^^__<<<v_^_>>_
FARGO       ^>>v>_^<<v_^>>v>vv_<<<<<^_>>v_
BUFFY       >_>vvv_>>>^^^__^<<vvvvv_
DALLAS      >>>_<<<_^>>v>v__^^<<v_vvv_
THX1138     >vvv_^^_>>>>vv_<<v__>>_<v_
ON DEMAND   >>vv_<_^^^>_v>_>_<<<<vv_^^_>vv_>>^^_
NEWS RADIO  >vv_>>>^^_vvv_<<<<_^^^^>_>vvv>_^^^<<v_>>>_<v_v_
ROOM 909    ^>>v>vv_<<<__<<_^^^>_>vvvvvv>_<<<^_>>>v_

Answer 1

JavaScript (ES6), 196 bytes

Golfing this code below 200 bytes was basically a nightmare (but it was fun). I'm really looking forward a simpler and shorter implementation.

f=(s,p=(i=0,6),x=(p-=p&(p<6))%6,X=(P=(parseInt(c=s[i],36)+26)%36+6||2)%6)=>c?'^<>v_'[(d=p-P?p<6?x<(X&6)?40:X-1&&x^X&6?20:60:P<6+(x>4)|p==11&!X?0:x<X?39:x>X?21:p<P&&60:++i&&70)>>4]+f(s,p+d%16-6):''

Try it online!

How?

Variables

• s is the input string
• i is a pointer in s, initialized to 0
• c is the next target character (aka s[ i ])

• p is the current position on the keypad according to the following mapping and initialized to 6 (the "A" key)

  del spa sav      00 -- 02 -- 04 --
  A B C D E F      06 07 08 09 10 11
  G H I J K L      12 13 14 15 16 17
  M N O P Q R  ->  18 19 20 21 22 23
  S T U V W X      24 25 26 27 28 29
  Y Z 0 1 2 3      30 31 32 33 34 35
  4 5 6 7 8 9      36 37 38 39 40 41
  

• P is the position of the target character c

• x is the column of the current character (p % 6)
• X is the column of the target character (P % 6)

Move encoding

There are 7 possible moves. We encode each of them as a 7-bit integer. The 4 least significant bits hold the displacement value V + 6 and the 3 most significant bits hold the symbol ID S.

move                       | symbol | S |  V | V + 6 | S << 4 | (V + 6)
---------------------------+--------+---+----+-------+-----------------
one position to the left   |   <    | 1 | -1 |   5   |       21
two positions to the left  |   <    | 1 | -2 |   4   |       20
one position to the right  |   >    | 2 |  1 |   7   |       39
two positions to the right |   >    | 2 |  2 |   8   |       40
upwards                    |   ^    | 0 | -6 |   0   |        0
downwards                  |   v    | 3 |  6 |  12   |       60
don't move (press the key) |   _    | 4 |  0 |   6   |       70

Alignment with function keys

At the beginning of each iteration, we execute the following code to make sure that p is aligned with the current function key if we're located in the first row:

p -= p & (p < 6)

Move logic

The move is chosen with a (too) long chain of ternary operators which is detailed below.

p - P ?               // if we're not yet located over the target character:
  p < 6 ?             //   if we're currently located in the first row:
    x < (X & 6) ?     //     if x is less than the column of the function key holding the target character:
      40              //       move 2 positions to the right
    :                 //     else:
      X - 1 &&        //       if the target character is not located in the 2nd column
      x ^ X & 6 ?     //       and x is not equal to the column of the function key holding the target character:
        20            //         move two positions to the left
      :               //       else:
        60            //         move downwards
  :                   //   else:
    P < 6             //     if the target key is space (P is either greater than 5 or equal to 2)
          + (x > 4) | //     or the target key is A and we're currently in the rightmost column
    p == 11 & !X ?    //     or we're currently over F and the target key is in the leftmost column:
      0               //       move upwards
    :                 //     else, this is a standard move:
      x < X ?         //       if x is less than X:
        39            //         move one position to the right
      :               //       else:
        x > X ?       //         if x is greater than X:
          21          //           move one position to the left
        :             //         else:
          p < P && 60 //           move either upwards or downwards
:                     // else:
  ++i && 70           //   don't move and advance the pointer in s

Answer 2

Python 2, 294 293 289 bytes

r='';l=[(ord(c)-59)%43-14*(c<'0')for c in input()]
for a,b in zip([6]+l,l):x,y,X,Y=a%6,a/6,b%6,b/6;A=(a<6)*(X!=1);x=[x,X/2*2][A];r+='< >'[X/2]*A+('^'*y+['<<'+'v'*Y,'> <'[x/2]][b<6]if(b,x)in[(6,5),(2,x)]or(a,X)==(11,0)else('^v'[Y>y]*abs(y-Y)+'<>'[X>x]*abs(x-X)))+'_'
print r.replace(' ','')

Try it online!

Answer 3

JavaScript, 311 bytes

f=n=>(parseInt(n,36)+26)%36+1||'S'
g=n=>(t=+n)?[t-(t%6!=1),t%6?t+1:t,t>30?t:t+6,t<7?' DDSSVV'[t]:t-6]:{D:'DS1',S:'DV3',V:'SV5'}[n]||[]
h=(p,q,t={[p]:''})=>([...g(p)].map((n,i)=>n in t&&t[n].length<t[p].length+1||h(n,q,t,t[n]=t[p]+'<>v^'[i])),t[q])
F=s=>[...s].map(f).map((c,i,a)=>h(a[i-1]||1,c)+'_').join``

<input id=i oninput=o.value=F(i.value)><br><output id=o>

Not sure how to golf this...

• f: convert 'A-Z0-9' to 1-36, space to "S"
• g: get 4 sibling of given key
• h: find shortest path from p to q
• F: the answer