Efficient Typing on a Game Boy

Question

Many old Game Boy games often required string input from the user. However, there was no keyboard. This was handled by presenting the user with a "keyboard screen" like so:

The 'character pointer' would begin on letter A. The user would navigate to each desired character with the D-Pad's four buttons (UP, DOWN, LEFT and RIGHT), then press BUTTON A to append it to the final string.

Please note:

• The grid wraps around, so pressing UP whilst on letter A would take you to T.
• The 'character pointer' stays put after appending a letter

The Challenge

The above keyboard has options to change case and is an irregular shape. So, for simplicity, in this challenge we will use the following keyboard (the bottom right is ASCII char 32, a space):

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 .

Typing on keyboards like this is extremely slow - so, to make this easier, your task is to write a program which tells the user the fastest possible way to type a given string. If there are multiple fastest ways, you only need to show one.

The output key should be:

• > for RIGHT
• < for LEFT
• ^ for UP
• v for DOWN
• . for BUTTON A (append current letter to string)

For example, when given the string DENNIS, the solution would look like this:

>>>.>.>>v..>>.>>>v.

Rules / Details

• Please remember, the grid wraps around!
• You may submit a full program or a function, as long as it takes the initial string and produces a solution string. Whitespace / trailing newlines are irrelevant as long as the output is correct.
• You can assume input will only consist of characters typable on the specified keyboard, but it may be empty.
• This is code-golf, so the shortest code wins. Standard code-golf loopholes apply.

Test Cases

There are usually multiple solutions of the same length. For each test case, I've included the optimum length, and an example. You don't need to print the length in your answer, just the solution.

FLP.TKC  ->  25 steps:  <<.<v.<<<v.<<<v.^.<<^.<^.
MOYLEX   ->  23 steps:  <<v.>>v.>>>v.>^^.^.<<^.
FEERSUM  ->  18 steps:  <<.<..<vv.>.>>.<^.
MEGO     ->  14 steps:  <<v.<^.>>.>vv.

A CAT    ->  17 steps:  .<^.>>>v.<<.<<vv.
BOB      ->  10 steps:  >.<vv.>^^.

(space)  ->  3 steps:   <^.
(empty)  ->  0 steps:   (empty)

You can view my testcase generator on repl.it - please notify me if there are any bugs.

Thank you everyone for the submissions! User ngn is currently the winner with 61 bytes, but if anyone can find a shorter solution, the little green tick can be moved ;)

Answer 1

Dyalog APL, 61 bytes

4 7∘{∊'.',⍨⍉↑b⍴¨¨'^v' '<>'⌷¨⍨⊂¨a>b←a⌊⍺-a←⍺|↓2-/0,⍺⊤⍵⍳⍨⎕a,'.'}

assumes ⎕IO←0

⎕a,'.' the alphabet followed by a full stop

⍵⍳⍨ find the argument's chars there as indices 0..26 (' ' and all others will be 27)

⍺⊤ encode in base 7 (note the left arg ⍺ is bound to 4 7), get a 2×n matrix

0, prepend zeros to the left

2-/ differences between adjacent columns

↓ split the matrix into a pair of vectors

a←⍺| take them modulo 4 and 7 respectively, assign to a

b←a⌊⍺-a make b the smaller of a and its modular inverse

'^v' '<>'⌷¨⍨⊂¨a>b choose ^ or v for the first vector and < or > for the second, based on where a differs from b

b⍴¨¨ repeat each of those b times

⍉↑ mix the two vectors into a single matrix and transpose it, get an n×2 matrix

'.',⍨ append .-s on the right

∊ flatten

Answer 2

JavaScript (ES6), 147 bytes

s=>s.replace(/./g,c=>(q=p,p="AHOVBIPWCJQXDKRYELSZFMY.GNU ".indexOf(c),"<<<>>>".substring(3,((p>>2)+10-(q>>2))%7)+["","v","vv","^"][p-q&3]+"."),p=0)

An interesting behaviour of substring is that it exchanges the arguments if the second is less than the first. This means that if I calculate the optimal number of left/right presses as a number between -3 and 3, I can add 3, and take the substring of <<<>>> starting at 3 and I will get the correct number of arrows. Meanwhile the down/up presses are simply handled by looking up an array using a bitwise and of the difference in rows with 3; this way is slightly shorter as there are fewer array elements.

Answer 3

Ruby, 107 bytes

->s{c=0
s.tr(". ","[\\").bytes{|b|b-=65
print ["","^","^^","v"][c/7-b/7],(d=(c-c=b)%7)>3??>*(7-d):?<*d,?.}}

Ungolfed in test program

f=->s{                                 #Input in s.
  c=0                                  #Set current position of pointer to 0.
  s.tr(". ","[\\").                    #Change . and space to the characters after Z [\
  bytes{|b|                            #For each byte b,
    b-=65                              #subtract 65 so A->0 B->1 etc.
    print ["","^","^^","v"][c/7-b/7],  #Print the necessary string to move vertically.
    (d=(c-c=b)%7)>3?                   #Calculate the horizontal difference c-b (mod 7) and set c to b ready for next byte.
       ?>*(7-d):?<*d,                  #If d>3 print an appropriate number of >, else an appropriate number of <.
    ?.                                 #Print . to finish the processing of this byte.
  }
}

#call like this and print a newline after each testcase
f["FLP.TKC"];puts  
f["MOYLEX"];puts   
f["FEERSUM"];puts  
f["MEGO"];puts     
f["A CAT"];puts    
f["BOB"];puts      

Answer 4

Python 2, 298 bytes

This is longer than it should be, but...

def l(c):i="ABCDEFGHIJKLMNOPQRSTUVWXYZ. ".index(c);return[i%7,i/7]
def d(f,t,a=abs):
 v,h=l(t)[1]-l(f)[1],l(t)[0]-l(f)[0]
 if a(h)>3:h=h-7*h/a(h)
 if a(v)>2:v=v-4*v/a(v)
 return'^v'[v>0]*a(v)+'<>'[h>0]*a(h)
s="A"+input()
print''.join([d(p[0],p[1])+'.'for p in[s[n:n+2]for n in range(len(s))][:-1]])

Any help would be greatly appreciated!

Takes input in quotation marks.

l returns the location of a character in the keyboard.

The two if statements in the middle of d are for checking if it would be optimal to 'wrap' around the keyboard.

The input, s has "A" prepended to it because the initial position of the cursor is A.

We loop through the string in pairs, discarding the last one (which is not a pair: [:-1]), finding the minimum distance between the two halves of the pair.

Thanks to Flp.Tkc for telling me that I can do a=abs instead of saying abs every time!

Answer 5

Mathematica, 193 bytes

Golf

StringJoin@@(StringTake[">>><<<",Mod[#〚2〛,7,-3]]<>StringTake["vv^",Mod[#〚1〛,4,-1]]<>"."&/@Differences[FirstPosition[Partition[ToUpperCase@Alphabet[]~Join~{"."," "},7],#]&/@Characters["A"<>#]])&

Readable

In[1]:= characters = ToUpperCase@Alphabet[]~Join~{".", " "}

Out[1]= {"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", ".", " "}

In[2]:= keyboard = Partition[characters, 7]

Out[2]= {{"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", ".", " "}}

In[3]:= characterPosition[char_] := FirstPosition[keyboard, char]

In[4]:= xToString[x_] := StringTake[">>><<<", Mod[x, 7, -3]]

In[5]:= yToString[y_] := StringTake["vv^", Mod[y, 4, -1]]

In[6]:= xyToString[{y_, x_}] := xToString[x] <> yToString[y] <> "."

In[7]:= instructionsList[input_] := xyToString /@ Differences[characterPosition /@ Characters["A" <> input]]

In[8]:= instructions[input_] := StringJoin @@ instructionsList[input]

In[9]:= instructions["DENNIS"]

Out[9]= ">>>.>.>>v..>>.>>>v."

Answer 6

Java 8, 1045 bytes

Golf

staticchar[][]a={{'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','.',''}};staticintm=Integer.MAX_VALUE;staticStringn="";staticboolean[][]c(boolean[][]a){boolean[][]r=newboolean[4][];for(inti=0;i<4;i)r[i]=a[i].clone();returnr;}staticvoidg(inti,intj,boolean[][]v,chard,Stringp){v[i][j]=true;if(a[i][j]==d&&p.length()<m){m=p.length();n=p;}if(i-1<0){if(!v[3][j])g(3,j,c(v),d,p"^");}elseif(!v[i-1][j])g(i-1,j,c(v),d,p"^");if(i1>3){if(!v[0][j])g(0,j,c(v),d,p"v");}elseif(!v[i1][j])g(i1,j,c(v),d,p"v");if(j-1<0){if(!v[i][6])g(i,6,c(v),d,p"<");}elseif(!v[i][j-1])g(i,j-1,c(v),d,p"<");if(j1>6){if(!v[i][0])g(i,0,c(v),d,p">");}elseif(!v[i][j1])g(i,j1,c(v),d,p">");}publicstaticvoidmain(String[]args){boolean[][]v=newboolean[4][7];Scannerx=newScanner(System.in);Strings=x.next();Stringpath="";intp=0;intq=0;for(inti=0;i<s.length();i){chart=s.charAt(i);g(p,q,c(v),t,"");path=n".";n="";m=Integer.MAX_VALUE;for(intj=0;j<4;j){for(intk=0;k<7;k){if(a[j][k]==t){p=j;q=k;}}}}System.out.println(path);}

Readable

static char[][] a = {
        {'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','.',' '}
};
static int m = Integer.MAX_VALUE;
static String n="";


static boolean[][] c(boolean[][] a){
    boolean [][] r = new boolean[4][];
    for(int i = 0; i < 4; i++)
        r[i] = a[i].clone();
    return r;
}

static void g(int i, int j,boolean[][] v,char d,String p) {

    v[i][j] = true;
    if (a[i][j]==d && p.length()<m){
        m=p.length();
        n=p;
    }

    if (i-1<0) {
        if(!v[3][j])
            g(3, j, c(v), d, p + "^");
    }
    else if (!v[i-1][j])
        g(i-1, j, c(v), d, p + "^");


    if (i+1>3) {
        if(!v[0][j])
            g(0, j, c(v), d, p + "v");
    }
    else if(!v[i+1][j])
        g(i+1, j, c(v), d, p + "v");


    if (j-1<0) {
        if(!v[i][6])
            g(i, 6, c(v), d, p + "<");
    }
    else if (!v[i][j-1])
        g(i, j-1, c(v), d, p + "<");


    if (j+1>6) {
        if (!v[i][0])
            g(i, 0, c(v), d, p + ">");
    }
    else if (!v[i][j+1])
        g(i, j+1, c(v), d, p + ">");

}

public static void main(String[] args) {
    boolean[][] v = new boolean[4][7];
    Scanner x = new Scanner(System.in);
    String s = x.next();
    String path="";
    int p=0;
    int q=0;
    for(int i=0;i<s.length();i++){
        char t=s.charAt(i);
        g(p,q,c(v),t,"");
        path+=n+".";
        n="";
        m=Integer.MAX_VALUE;
        for(int j=0;j<4;j++){
            for(int k=0;k<7;k++){
                if(a[j][k]==t) {
                    p=j;
                    q=k;
                }
            }
        }

    }
    System.out.println(path);
}

Explanation

The solution is a direct approach: poorly optimized brute force. The method g(...) is a basic depth first search going through each permutation (up, down, left, right). With some slight modifications in ordering for the test cases I get the output:

<<.v<.v<<<.v<<<.^.^<<.^<.
v<<.v>>.v>>>.^^>.^.^<<.
<<.<..^^<.>.>>.^<.
v<<.^<.>>.^^>.
.^<.v>>>.<<.^^<<.
>.^^<.^^>.
^<.
// new line for the last