RoboZZle переводчик

10

Ваша задача - написать интерпретатор RoboZZle. Если вы не знакомы с игрой, посмотрите видео на robozzle.com или прочтите мое описание ниже.

Робот живет на прямоугольной сетке из квадратов красного, зеленого, синего или черного цвета. Черные квадраты недоступны. Другие доступны, и некоторые из них содержат звезду. Цель состоит в том, чтобы собрать все звезды, не наступая на черные квадраты и не падая с карты. Робот занимает один квадрат и направлен в определенном направлении - влево, вправо, вверх или вниз. Он следует инструкциям, подобным сборке, сгруппированным в подпрограммы F1, F2, ..., F5. Инструкция - это пара предикатов («нет», «если на красном», «если на зеленом», «если на синем») и действия («идти вперед», «повернуть налево», «повернуть направо», «закрасить текущий квадрат красным», «закрасить его зеленым», «закрасить его синим», «ничего не делать», «вызвать F1», ..., «вызвать F5»). Вызовы подпрограмм используют стек и могут быть рекурсивными. Как и в обычном программировании, после того, как последняя инструкция подпрограммы завершена, выполнение продолжается с того места, где была вызвана подпрограмма. Выполнение начинается с первой инструкции F1 и продолжается до тех пор, пока робот не посетит все квадраты со звездами, или пока робот не выйдет на черный квадрат или за пределами карты, или пока не будет выполнено 1000 инструкций (неудачные предикаты и действия «ничего не делать») не в счет), или больше нет инструкций для выполнения (потеря стека).

Входы:

  • a- матрица символов 12x16 (как обычно представлено на вашем языке, например, массив строк), которая кодирует карту - '#'для недоступных (черных) квадратов, '*'для квадратов со звездочкой, '.'для остальных

  • c- матрица символов 12x16, описывающая цвета доступных квадратов - 'R'(красный), 'G'(зеленый) или 'B'(синий). Недоступные квадраты будут представлены произвольной буквой из трех.

  • yи x- строка и столбец робота на основе 0; a[y][x]гарантированно будет'.'

  • d- направление робот облицовочный: 0 1 2 3для правого, вниз, влево, вверх, то есть в направлении (y,x+1), (y+1,x), (y,x-1),(y-1,x)

  • f- одиночная строка, связанные реализации F1 ... F5. Каждая реализация представляет собой (возможно, пустую) последовательность пар предикат-действие (не более 10 пар на подпрограмму), оканчивающихся на '|'.

    • предикаты: '_'нет, 'r'красный, 'g'зеленый, 'b'синий

    • действия: 'F'идти вперед, 'L'повернуть налево, 'R'повернуть направо, 'r'покрасить красный, 'g'покрасить зеленый, 'b'покрасить синий, '1'вызвать F1, ..., '5'вызвать F5, '_'ничего не делать

Вам не нужно называть входные данные, как указано выше, но их значения должны быть такими, как указано.

Вывод: 1(или true) если робот собирает все звезды в соответствии с правилами, 0( false) в противном случае.

Пример :

a=["################","################","##*....*...*#.##","##.####.#####.##","##.####.#####.##","##.####*...*#.##","##.########.####","##*........*#.##","################","################","################","################"]
c=["RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRBBBBRGGGGRRRR","RRBRRRRGRRRRRRRR","RRBRRRRGRRRRRRRR","RRBRRRRRGGGBRRRR","RRBRRRRRRRRGRRRR","RRRBBBBGGGGBRBRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR"]
y=2; x=6; d=2

// and then depending on "f":
f="_FrLg2_1|_FbLrR_2||||" // result:1
f="_FrRg2_1|_FbLrR_2||||" // result:0 (stepped on a black square)
f="_FrLrL_1|_FbLrR_2||||" // result:0 (1000-step limit exceeded)
f="_FrLg2__|________||||" // result:0 (stack underflow)

Другой пример , включающий «рисование» инструкций:

a=["#***************","#*###*###*###*##","#*###*###*###*##","***#***#***#***#","***#***#***#***#","*###*###*###*###","***#***#***#***#","***#***#***#***#","***#***#***#***#","*###*###*###*###","*.*#***#***#***#","***#***#***#***#"]
c=["RGGGGGGGGGGGGGGG","RBRRRGRRRGRRRGRR","RBRRRGRRRGRRRGRR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BRRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BGRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR"]
y=10; x=1; d=0
f="_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||"
// result:1

Чтобы создать свой собственный тест, перейдите к головоломке из списка на robozzle.com , попробуйте решить ее (или не решить), нажмите F12 в браузере и введите консоль JS:

r=robozzle;s=JSON.stringify;with(r.level)console.log('a='+s(Items)+'\nc='+s(Colors)+'\ny='+RobotRow+'\nx='+RobotCol+'\nd='+RobotDir+'\nf='+s(r.encodeSolution()))

и переформатировать результат для вашего языка.

Кратчайшие победы. Нет лазеек.

code-golf grid interpreter СПП
источник
1
Можем ли мы использовать какие-либо отдельные символы для представления данных вместо предоставленных?
HyperNeutrino
1
Для ответа APL на задачу «Loop it» вы можете отсортировать последнее значение угла, уменьшив комплексную величину.
user202729
1
@ user202729 Э-э, я не ожидал комментариев об этой проблеме здесь :) Ваша идея работает, спасибо! Я постараюсь реализовать это, не делая подсчет персонажей слишком позорным.
НГН
1
Можем ли мы взять матрицы символов в виде списков пар местоположений и символов?
0
1
@ 0 'Принцип, которому я следовал здесь (см. Также комментарий HyperNeutrino), заключается в том, чтобы максимально приблизиться к формату ввода, фактически используемому на robozzle.com, поэтому, боюсь, это не должен быть список пар.
августа

Ответы:

5

Пролог (SWI) , 574 байта

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).
N^C^G^[P,I|R]^F^X^Y^D:-map_assoc(\=(74),G);N<1e3,get_assoc(X^Y,G,J),J>67,put_assoc(X^Y,G,78,H),T=N+1,((I\=95,(P=95;get_assoc(X^Y,C,P)))->(between(49,53,I),plus(48,M,I),nth1(M,F,Q),append(Q,R,S),T^C^H^S^F^X^Y^D;member(I,`RL`),E is(D-I//3)mod 4,T^C^H^R^F^X^Y^E;I=70,(D=0,U is X+1;D=1,V is Y+1;D=2,U is X-1;D=3,V is Y-1),(U=X;V=Y),T^C^H^R^F^U^V^D;I>97,put_assoc(X^Y,C,I,W),T^W^H^R^F^X^Y^D);N^C^H^R^F^X^Y^D).
A+C+F+L:-A*G,C*B,split_string(F,"|","",P),maplist(string_codes,P,[M|N]),0^B^G^M^[M|N]^L.

Попробуйте онлайн!

Это определяет предикат, который при вызове завершается успешно, если все звезды успешно собраны, и дает сбой в противном случае Предикат принимает аргументы как таковые a+c+f+x^y^d.. aи cдолжен быть списком строк в кавычках, в то время как fдолжен быть строкой в ​​двойных кавычках.

объяснение

Эта программа содержит три предиката, */2, ^/2, и +/2. В */2предиката , которое определено на первой линии несет ответственность за часть обработки входного сигнала. ^/2Предикат рекурсивно вычисляет , как робот движется , шаг за шагом , и успешно , если робот легально собирает все звезды и не иначе. +/2Предикат является основным предикатом программы и готовит материалы для ^/2предиката с некоторой помощью */2предиката. Обратите внимание, что каждый из этих предикатов технически принимает только два аргумента, но используя операторы и сопоставление с образцом, они могут вести себя так, как если бы у них было больше аргументов (я обсуждаю это явление более подробно здесь ).

*/2

Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).

Этот предикат принимает два аргумента. Первый - это список списков кодов символов (именно так Prolog анализирует строки в кавычках в кавычках). Вторая - это ассоциативная карта от точек на карте 12x16 (обозначается как X^Y) до 32 плюс код символа, сохраненный в этой точке в списке списков кодов символов. 32 добавляется к каждому из кодов символов, так что для цветовой матрицы он преобразует цветные символы в верхнем регистре в цветные символы в нижнем регистре.

То, как это происходит, генерирует список пар точек и кодов символов в этой точке, используя findall/3. Затем он используется list_to_assoc/2для создания соответствующей ассоциативной карты из точек в код символа в этой точке.

findall/3Предикат является встроенным принимает «шаблон» в качестве первого аргумента, цели в качестве второго аргумента и списка в качестве третьего аргумента. Предикат заполняет список всеми возможными значениями шаблона, которые приводят к достижению цели. Из-за приоритета оператора шаблон, который передается в findall/3in */2, анализируется как (X^Y)-D. -Оператор представляет собой пару из двух значений в Прологе поэтому шаблон представляет положение точки ( X^Y) в паре с кодом символа 32 плюс точки ( в D). Обратите внимание, что ^используемый в представлении точки никоим образом не связан с ^/2предикатом.

Давайте рассмотрим цель, которая передается findall/3предикату.

nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D) % Note that the O (oh) is not a 0 (zero)

Цель содержит три предиката, каждый из которых должен быть успешным для достижения цели. nth0/3Предикат , который используется дважды используется для получения значения в определенном индексе списка ( 0в его названии указывает на то она равна нулю проиндексированы). При первом вызове в него сохраняется Yth-я строка символьной матрицы, Oтогда как при втором вызове сохраняется Xth-й символ в этой строке C. Последний предикат plus/3завершается успешно, если его первые два аргумента суммируются с третьим аргументом. Это используется, чтобы сделать код символа в паре на 32 больше, чем код символа в матрице символов, который, как указано выше, превратит все заглавные буквы в строчные.

Наконец, findall/3сохраняет все X^Y-Dкомбинации, которые приводят к достижению цели в списке, из Lкоторого построена ассоциативная карта.

Продолжение следует...

0 '
источник
4

JavaScript (ES6), 298 276 264 байта

Сохранено 8 байтов благодаря @ngn

Вводит как (a,c,x,y,d,f), где aи cявляются массивами массивов символов. Возвращает 0или 1.

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

Контрольные примеры

Показать фрагмент кода

комментарии

(                                           // main function taking:
  a, c, x, y, d, f,                         //   - input variables
  k = 1e3                                   //   - k = instruction counter
) => (                                      //
  g = (                                     // g = recursive execution function, taking:
    F,                                      //   - F = subroutine id
    p = 0,                                  //   - p = instruction pointer
    s = f.split`|`[F],                      //   - s = instruction string
    r = a[y]                                //   - r = current row in a[]
  ) =>                                      //
    !k |                                    // if we've executed 1000 instructions
    !r | x & 16 ||                          // or we've felt out of the map
    r[x] < '$' ?                            // or we've reached a black square:
      2                                     //   exit with error code 2
    :                                       // else:
      /\*/.test(a) ? (                      //   if there are still some stars:
        r[x] = o = 0,                       //     mark the current cell as visited
        (I = s[p + 1], P = s[p]) &&         //     I = instruction, P = predicate
        (                                   //     if P is defined:
          P < 'b' |                         //       if the predicate is '_'
          P == c[y][x].toLowerCase()        //       or it matches the color of the cell
          && I != '_'                       //       and the instruction is not '_',
          && k-- ?                          //       then decrement k and:
            +I ?                            //         if I is '1' ... '5':
              o = g(I - 1)                  //           process call to subroutine
            :                               //         else:
              I == 'L' ?                    //           if I is 'L':
                d--                         //             turn left
              :                             //           else:
                I == 'R' ?                  //             if I is 'R':
                  d++                       //               turn right
                :                           //             else:
                  I < 'b' ? (               //               if I is not a color:
                    y += (                  //                 I must be 'F',
                      d &= 3,               //                 so make the bot advance
                      x -= ~-d % 2,         //                 by updating x
                      2 - d                 //                 and y
                    ) % 2                   //
                  ) :                       //               else:
                    c[y][x] = I             //                 paint the current cell
          :                                 //       else:
            0,                              //         do nothing
          o ||                              //       provided that o is equal to 0,
          g(F, p + 2)                       //       go on with the next instruction
        )                                   //     end of instruction execution
      ) :                                   //   else:
        1                                   //     success: return 1
  )(0) & 1                                  // initial call to the subroutine F1
Arnauld
источник
x+='2101'[d&3]-1,y+='1210'[d&3]-1->d&=3,x+=(1-d)%2,y+=(2-d)%2
ngn
1
xизменяется не более чем на 1, поэтому я думаю, что вы можете заменить x&~15наx&16
ngn
1

APL (Dyalog Classic) , 236 233 байта

-3 спасибо Эрику Аутгольферу

Теперь, когда я отдал бонус, я публикую пример решения для моей собственной задачи. Здесь есть возможности для улучшения - не стесняйтесь копировать и играть в гольф дальше.

a c r d f←⎕⋄c←819⌶c⋄F←0,('|'=¯1⌽f)/⍳≢f⋄t←n←0
{~(⊂r)∊⍳⍴a:0⋄'#'=r⌷a:0⋄p q←2↑f↓⍨⊃⌽t⋄(_←p≡'|')∧×≢t:0⋄_:∇t↓←¯1⋄(⊃⌽t)+←2⋄~p∊'_',r⌷c:∇0⋄n+←1⋄n>999:0⋄(r⌷a)←'.'⋄~'*'∊a:1⋄r+←(q≡'F')×11 9○0j1*d⋄d+←4|'.R.L'⍳q⋄q∊'rgb':∇(r⌷c)←q⋄q∊⎕d:∇t,←F[⍎q]⋄∇0}0

Попробуйте онлайн!

То же, что и выше, дополнено комментариями:

⎕io←0                   ⍝ 0-based indices (not counted in the score)
a c r d f←⎕             ⍝ decompose eval'ed input (⎕) into variables
c←819⌶c                 ⍝ make c lowercase
F←0,('|'=¯1⌽f)/⍳≢f      ⍝ split f at the '|'-s
t←n←0                   ⍝ t:stack, n:step counter
{                       ⍝ lambda
  ~(⊂r)∊⍳⍴a:0           ⍝ if the robot is off the map, return 0
  '#'=r⌷a:0             ⍝ if the robot is on a wall, return 0
  p q←2↑f↓⍨⊃⌽t          ⍝ current instruction - p:predicate, q:action
  (_←p≡'|')∧1≥≢t:0      ⍝ if at end of func and stack is empty, return 0
  _:∇t↓←¯1              ⍝ if at end of func, pop from stack and recurse
  (⊃⌽t)+←2              ⍝ increment program counter (top of stack)
  ~p∊'_',r⌷c:∇0         ⍝ if predicate doesn't match cell colour, recurse
  n+←1⋄n>999:0          ⍝ if too meany steps, return 0
  (r⌷a)←'.'             ⍝ consume star
  ~'*'∊a:1              ⍝ if no more stars left, return 1
  r+←(q≡'F')×11 9○0j1*d ⍝ if action is F, move forward
  d+←4|'.R.L'⍳q         ⍝ if action is L or R, turn left or right
  q∊'rgb':∇(r⌷c)←q      ⍝ if action is paint (r,g,b), do it
  q∊⎕d:∇t,←F[⍎q]        ⍝ if action is F1...F5, push on stack and recurse
  ∇0                    ⍝ action is nop (_), recurse
}0                      ⍝ call the lambda (argument will be ignored)
СПП
источник
233 байта
Эрик Outgolfer
@EriktheOutgolfer изменения применены, спасибо
ngn