Эффективное печатание на Game Boy

26

Многие старые игры Game Boy часто требовали ввода строки пользователем. Однако клавиатуры не было. Это было сделано путем предоставления пользователю «экрана клавиатуры» следующим образом:

Pokemon Ruby Keyboard

«Указатель на символ» будет начинаться на букву А. пользователя будет перемещаться к каждому нужному символу с D-Pad «s четыре кнопки ( UP, DOWN, LEFTи RIGHT), затем нажмите кнопку , BUTTON Aчтобы добавить его в конечную строку.

Пожалуйста, обратите внимание:

  • Сетка оборачивается , поэтому нажатиеUPна букву А приведет вас к T.
  • «Указатель на символ» остается на месте после добавления буквы

Соревнование

Вышеуказанная клавиатура имеет опции для изменения регистра и имеет неправильную форму. Итак, для простоты в этой задаче мы будем использовать следующую клавиатуру (справа внизу - ASCII char 32, пробел):

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 .

Печатание на таких клавиатурах чрезвычайно медленное, поэтому, чтобы упростить эту задачу, вы должны написать программу, которая сообщает пользователю самый быстрый способ ввода заданной строки. Если есть несколько быстрых способов, вам нужно показать только один.

Выходной ключ должен быть:

  • > для RIGHT
  • < для LEFT
  • ^ для UP
  • v для DOWN
  • .для BUTTON A(добавить текущее письмо в строку)

Например, когда дана строка DENNIS, решение будет выглядеть так:

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

Правила / Детали

  • Пожалуйста, помните, сетка оборачивается!
  • Вы можете отправить полную программу или функцию, если она принимает начальную строку и создает строку решения. Пробелы / завершающие символы новой строки не имеют значения, если вывод правильный.
  • Можно предположить, что ввод будет состоять только из символов, набираемых на указанной клавиатуре, но он может быть пустым.
  • Это , поэтому выигрывает самый короткий код. Применяются стандартные лазейки для игры в гольф.

Тестовые случаи

Обычно есть несколько решений одинаковой длины. Для каждого теста я включил оптимальную длину и пример. Вам не нужно печатать длину в вашем ответе, только решение.

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)

Вы можете просмотреть мой генератор тестовых файлов на repl.it - пожалуйста, сообщите мне, если есть какие-либо ошибки.

Спасибо всем за представления! Пользователь ngn в настоящее время является победителем с 61 байтом, но если кто-то может найти более короткое решение, маленький зеленый тик может быть перемещен;)

FlipTack
источник
Обратите внимание, что это было в песочнице, и была найдена похожая проблема , но обсуждение в чате и песочнице привело к выводу, что это не обман, просто тесно связаны :)
FlipTack
Я думал, что это кажется очень знакомым, но это не дубликат этого тоже.

Ответы:

4

Дьялог АПЛ , 61 байт

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

предполагает ⎕IO←0

⎕a,'.' алфавит с последующей остановкой

⍵⍳⍨найдите там символы аргумента в виде индексов 0..26 ( ' 'а все остальные будут 27)

⍺⊤закодировать в базе 7 (обратите внимание, что левый аргумент связан с 4 7), получить матрицу 2 × n

0, ставить нули влево

2-/ различия между соседними столбцами

разбить матрицу на пару векторов

a←⍺| возьмите их по модулю 4 и 7 соответственно, присвойте a

b←a⌊⍺-aсделать bменьше из aи его модульной обратной

'^v' '<>'⌷¨⍨⊂¨a>bвыберите ^или vдля первого вектора и <или >для второго, в зависимости от того, где aотличается отb

b⍴¨¨повторить каждый из тех bвремен

⍉↑ смешать два вектора в одну матрицу и транспонировать ее, получить матрицу n × 2

'.',⍨добавить .-s справа

расплющить

СПП
источник
6

JavaScript (ES6), 147 байт

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)

Интересным поведением substringявляется то, что он обменивается аргументами, если второе меньше первого. Это означает, что если я вычислю оптимальное количество нажатий влево / вправо как число от -3 до 3, я могу добавить 3 и взять подстроку, <<<>>>начинающуюся с 3, и получу правильное количество стрелок. Между тем, нажатия вниз / вверх просто обрабатываются путем поиска массива с использованием побитового алгоритма и разницы в строках с 3; этот путь немного короче, так как элементов массива меньше.

Нил
источник
4

Рубин, 107 байт

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

Неуправляемый в тестовой программе

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      
Уровень реки St
источник
1

Mathematica, 193 байта

Гольф

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

Удобочитаемый

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."
ngenisis
источник
1

Python 2, 298 байт

Это длиннее, чем должно быть, но ...

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

Любая помощь будет принята с благодарностью!

Вводит в кавычки.

l возвращает местоположение символа на клавиатуре.

Два ifоператора в середине dпредназначены для проверки того, будет ли оптимальным «обтекание» вокруг клавиатуры.

Ввода, sимеет "A"предваряется к нему , поскольку начальное положение курсора A.

Мы перебираем строку попарно, отбрасывая последнюю (которая не является парой :) [:-1], и находим минимальное расстояние между двумя половинами пары.

Спасибо Flp.Tkc за сообщение, что я могу делать, a=absа не говорить absкаждый раз!

Даниил
источник
0

Java 8, 1045 байт

Гольф

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

Удобочитаемый

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

объяснение

Решение - прямой подход: плохо оптимизированная грубая сила. Метод g(...)представляет собой базовый поиск глубины, проходящий каждую перестановку (вверх, вниз, влево, вправо). С некоторыми небольшими изменениями в заказе для тестовых случаев я получаю вывод:

<<.v<.v<<<.v<<<.^.^<<.^<.
v<<.v>>.v>>>.^^>.^.^<<.
<<.<..^^<.>.>>.^<.
v<<.^<.>>.^^>.
.^<.v>>>.<<.^^<<.
>.^^<.^^>.
^<.
// new line for the last
Bobas_Pett
источник