Effizientes Tippen auf einem Game Boy

26

Viele alte Game Boy- Spiele erforderten häufig Zeichenfolgeneingaben vom Benutzer. Es gab jedoch keine Tastatur. Dies wurde erreicht, indem dem Benutzer ein "Tastaturbildschirm" wie folgt präsentiert wurde:

Pokemon Ruby Keyboard

Der ‚Zeichenzeiger‘ würde auf Buchstaben A beginnt , der Benutzer zu jedem gewünschten Zeichen mit der Ebene würde D-Pad ‚s vier Tasten ( UP, DOWN, LEFTund RIGHT) und drückt BUTTON Aes auf die endgültige Zeichenfolge angehängt.

Bitte beachten Sie:

  • Das Gitter ist umlaufend.UP Wenn Sie also auf Buchstabe Adrücken, gelangen Sie zu T.
  • Der 'Zeichenzeiger' bleibt nach dem Anhängen eines Buchstabens gesetzt

Die Herausforderung

Die obige Tastatur bietet Optionen zum Ändern der Groß- / Kleinschreibung und weist eine unregelmäßige Form auf. Der Einfachheit halber verwenden wir in dieser Herausforderung die folgende Tastatur (unten rechts steht ASCII-Zeichen 32, ein Leerzeichen):

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 .

Das Schreiben auf solchen Tastaturen ist extrem langsam. Um dies zu vereinfachen, müssen Sie ein Programm schreiben, das dem Benutzer den schnellstmöglichen Weg zur Eingabe einer bestimmten Zeichenfolge weist . Wenn es mehrere schnellste Wege gibt, müssen Sie nur einen zeigen.

Der Ausgabeschlüssel sollte sein:

  • > zum RIGHT
  • < zum LEFT
  • ^ zum UP
  • v zum DOWN
  • .for BUTTON A(aktuellen Buchstaben an String anhängen)

Wenn beispielsweise die Zeichenfolge angegeben wird DENNIS, sieht die Lösung folgendermaßen aus:

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

Regeln / Details

  • Bitte denken Sie daran, das Gitter wickelt sich um!
  • Sie können ein vollständiges Programm oder eine Funktion einreichen, solange die ursprüngliche Zeichenfolge verwendet wird und eine Lösungszeichenfolge erstellt wird. Leerzeichen / abschließende Zeilenumbrüche sind irrelevant, solange die Ausgabe korrekt ist.
  • Sie können davon ausgehen, dass die Eingabe nur aus Zeichen besteht, die auf der angegebenen Tastatur eingegeben werden können, sie kann jedoch leer sein.
  • Das ist , also gewinnt der kürzeste Code. Standard Code-Golf-Lücken gelten.

Testfälle

In der Regel gibt es mehrere Lösungen gleicher Länge. Ich habe für jeden Testfall die optimale Länge und ein Beispiel angegeben. Sie müssen nicht die Länge in Ihrer Antwort drucken, sondern nur die Lösung.

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)

Sie können meinen Testfallgenerator auf repl.it anzeigen - bitte benachrichtigen Sie mich, wenn Fehler auftreten.

Vielen Dank an alle für die Einsendungen! User ngn ist momentan der Gewinner mit 61 Bytes, aber wenn jemand eine kürzere Lösung findet, kann das kleine grüne Häkchen verschoben werden;)

FlipTack
quelle
Beachten Sie, dass dies durch die Sandbox gegangen ist und eine ähnliche Herausforderung gefunden wurde, aber die Diskussion in Chat und Sandbox führte zu der Schlussfolgerung, dass es sich nicht um einen Betrüger handelt, sondern nur um eine enge Beziehung :)
FlipTack
Ich fand es sehr vertraut, aber es ist auch kein Duplikat von diesem .

Antworten:

4

Dyalog APL , 61 Bytes

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

geht davon aus ⎕IO←0

⎕a,'.' das Alphabet gefolgt von einem Punkt

⍵⍳⍨finde die Zeichen des Arguments dort als Indizes 0..26 ( ' 'und alle anderen werden 27 sein)

⍺⊤codiere in Basis 7 (beachte, dass das linke Argument gebunden ist 4 7), erhalte eine 2 × n Matrix

0, Stellen Sie links Nullen voran

2-/ Unterschiede zwischen benachbarten Spalten

Teilen Sie die Matrix in ein Paar von Vektoren

a←⍺| nimm sie modulo 4 bzw. 7, ordne zu a

b←a⌊⍺-amachen Sie bdas kleinere aund sein modulares Inverse

'^v' '<>'⌷¨⍨⊂¨a>bWählen Sie ^oder vfür den ersten Vektor und <oder >für den zweiten, je nachdem, wo sich dieser aunterscheidetb

b⍴¨¨Wiederholen Sie jede dieser bZeiten

⍉↑ Mischen Sie die beiden Vektoren zu einer einzigen Matrix und transponieren Sie diese. Sie erhalten eine n × 2-Matrix

'.',⍨hängt .-s auf der rechten Seite an

ebnen

ngn
quelle
6

JavaScript (ES6), 147 Byte

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)

Ein interessantes Verhalten von substringist, dass es die Argumente austauscht, wenn das zweite kleiner als das erste ist. Das bedeutet, wenn ich die optimale Anzahl von Links- / Rechtsdrücken als Zahl zwischen -3 und 3 berechne, kann ich 3 addieren und die Teilzeichenfolge von <<<>>>ab 3 nehmen, und ich erhalte die richtige Anzahl von Pfeilen. Währenddessen werden die Abwärts- / Aufwärtspressen einfach gehandhabt, indem ein Array bitweise nach oben geschaut wird und der Zeilenunterschied mit 3 angegeben wird. Dieser Weg ist etwas kürzer, da weniger Array-Elemente vorhanden sind.

Neil
quelle
4

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 im Testprogramm

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      
Level River St
quelle
1

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"<>#]])&

Lesbar

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."
Genisis
quelle
1

Python 2, 298 Bytes

Das ist länger als es sein sollte, aber ...

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]])

Jede Hilfe wäre sehr dankbar!

Nimmt Eingaben in Anführungszeichen vor.

l Gibt die Position eines Zeichens auf der Tastatur zurück.

Die beiden ifAussagen in der Mitte vond dienen dazu, zu überprüfen, ob es optimal wäre, die Tastatur zu umschließen.

Die Eingabe swurde "A"vorangestellt, da die Anfangsposition des Cursors istA .

Wir durchlaufen die Zeichenkette paarweise, wobei wir die letzte (die kein Paar ist:) verwerfen [:-1]und den Mindestabstand zwischen den beiden Hälften des Paares ermitteln.

Vielen Dank an Flp.Tkc, dass Sie mir gesagt haben, dass ich das tun kann, a=absanstatt es absjedes Mal zu sagen !

Daniel
quelle
0

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);}

Lesbar

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);
}

Erläuterung

Die Lösung ist ein direkter Ansatz: schlecht optimierte Brute Force. Die Methode g(...)ist eine grundlegende Tiefensuche, die jede Permutation durchläuft (oben, unten, links, rechts). Mit einigen geringfügigen Änderungen in der Bestellung für die Testfälle erhalte ich die Ausgabe:

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