Помогите, я в ловушке бесконечной фабрики!

26

Эта задача слабо вдохновлена ​​игрой Zachtronics Infinifactory .

Вам предоставляется вид сверху прямоугольной сетки конвейеров, представленной >v<^. Могут быть ячейки без конвейеров, представленные пробелами. Вот пример:

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Эта установка неявно окружена бесконечным числом пробелов.

Кроме того, вам даны размеры прямоугольного куска груза, который помещается на конвейеры в верхнем левом углу сетки. Ваша задача - выяснить, остановится ли груз когда-нибудь или он будет двигаться по кругу.

Конечно, груз может покрывать несколько конвейеров одновременно, поэтому вот правила для определения направления груза на каждом этапе:

  1. Противоположные конвейеры отменяют друг друга. Таким образом, если груз 3х2 покрывает любой из следующих патчей (для ясности обведен дефисами и трубками), результат будет таким же:

    +---+   +---+   +---+
    |>>^|   |  ^|   |v^^|
    |^<<|   |^  |   |^^v|
    +---+   +---+   +---+
    

    То же самое касается этих:

    +---+   +---+   +---+
    |v^<|   |   |   |><>|
    |>>>|   |>> |   |>><|
    +---+   +---+   +---+
    

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

    Эта отмена применяется раньше других правил. Следовательно, для других правил конвейеры будут использоваться не более чем в двух направлениях.

  2. Если груз не покрывает какие-либо конвейеры вообще (либо потому, что все конвейеры отменяются, потому что он охватывает только пространства или потому что он полностью сдвинулся с сетки), он останавливается.
  3. Если груз покрывает больше конвейеров в одном направлении, чем в другом, груз перемещается в этом направлении. Например, если груз 3х2 покрыл следующий патч

    >>
    ^>^
    

    он будет двигаться вправо, потому что есть больше, >чем ^. С другой стороны, если это покрыто

    >>^
      ^
    

    это правило не будет применяться, потому что между >и ^.

  4. Это оставляет только случаи, в которых есть связь между смежными направлениями (связь между противоположными направлениями была бы отменена). В этом случае груз продолжает двигаться вдоль оси, по которой он уже движется. Например, если груз 3х2, движущийся вправо или налево, теперь покрывает участок

    >>^
    ^  
    

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

Подробные примеры

Рассмотрим конвейерную решетку сверху и груз 3х2. Ниже приведена пошаговая визуализация процесса. Каждый шаг состоит из сетки с изображенным грузом #, небольшого прямоугольника, на котором показаны конвейеры, покрытые грузом, другого прямоугольника с конвейерами после отмены и правила, определяющего, куда перемещается груз:

 ###vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ###^ >v v     ###^ >v v      v ^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^    ###v^^>vv^    ###v^^>vv^     ###^^>vv^      ###^>vv^      >###>vv^
     ^>^ v         ^>^ v     ### ^>^ v      ###^>^ v       ###>^ v        ###^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+
|> <|  |   |  | v |  | v |  |  >|  |  >|  | >v|  | >v|  |>v^|  |> ^|  |v^^|  | ^^|
| v |  | v |  |  >|  |  >|  |   |  |   |  |   |  |   |  |  ^|  |   |  | ^>|  |  >|
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3        Rule 4        Rule 4        Rule 3

 ================================================================================

 > <vv    <    > <###   <    > <vv    <
  v ###v v      v ###v v      v ###v v 
   >###>vv^      >v^^>vv^      >###>vv^
     ^>^ v         ^>^ v         ^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+
|^ >|  |  >|  |vv |  | v |  |^ >|  |  >|
|v^^|  | ^^|  |^ >|  |  >|  |v^^|  | ^^|
+---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3

В этот момент груз входит в петлю между двумя последними кадрами.

Теперь рассмотрим груз 2х3:

 ##<vv    <    >##vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ## ^ >v v      ##^ >v v      ##^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
 ##>v^^>vv^     ##v^^>vv^     ##v^^>vv^     ##v^^>vv^      ##^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v      ## ^>^ v      ## ^>^ v       ##^>^ v       ##^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >##v<v  >>    > ##<v  >>    > ##<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        ## v<^  

 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+
 |> |  |> |    | <|  |  |    |v |  |v |    | >|  | >|    |>v|  |>v|    |  |  |  |
 | v|  | v|    |v |  |v |    | >|  | >|    |  |  |  |    |  |  |  |    | v|  | v|
 |  |  |  |    | >|  |  |    |  |  |  |    |  |  |  |    | v|  | v|    |>v|  |>v|
 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+

   Rule 4        Rule 3        Rule 4        Rule 3        Rule 3        Rule 3

 ================================================================================

 > <vv    <    > <vv    <    > <vv    <
  v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^      >v^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v         ^>^ v 
 > ##<v  >>    >  v<v  >>    >  v<v  >>
   ## v<^        ## v<^        >v v<^  
   ##            ##            ##
                 ##            ##
                               ##

 +--+  +--+    +--+  +--+    +--+  +--+
 | v|  | v|    |>v|  |>v|    |  |  |  |
 |>v|  |>v|    |  |  |  |    |  |  |  |
 |  |  |  |    |  |  |  |    |  |  |  |
 +--+  +--+    +--+  +--+    +--+  +--+

   Rule 3        Rule 4        Rule 2

На последнем шаге применяется правило 2, поскольку груз сместился с сетки, поэтому он останавливается и петли не будет.

Правила и предположения

Ваш вход будет сетка конвейера, как описано выше, а также ширина и высота груза. Вы можете взять эти три параметра в любом удобном порядке и формате. Для сетки это означает, что вы можете прочитать одну строку со строками, разделенными символами новой строки или другими символами, или массивом строк, или массивом массивов символов, если отдельные ячейки сетки все еще представлены символами>v<^ и пространства.

Вы должны вывести истинное значение, если установка приводит к циклу, по крайней мере, из двух кадров или ложному значение, если груз остановится.

Вы можете предположить, что сетка будет дополнена прямоугольником с пробелами, и груз будет изначально помещаться в сетку.

Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

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

Тестовые случаи сгруппированы по сеткам.

Grid (2x2):

>v
^<

Width  Height  Loop?
1      1       True
1      2       True
2      1       True
2      2       False

Grid (3x3):

> v

^ <

Width  Height  Loop?
1      1       False
1      2       False
1      3       False
2      1       False
2      2       True
2      3       True
3      1       False
3      2       True
3      3       False

Grid (4x3):

>^>v
v^v 
^ <<

Width  Height  Loop?
2      2       False

Grid (6x5):

>v>v>v
^v^v^v
^v^v^v
^>^>^v
^<<<<<

Width  Height  Loop?
1      1       True
1      2       False
2      1       True
2      2       True
2      4       True
2      5       False
3      1       False
3      2       True
3      3       True
3      5       True
6      2       False
6      3       True
6      5       False

Grid (10x6):

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Width  Height  Loop?
1      1       False
2      3       False
2      6       False
3      2       True
5      4       False
6      1       True
10     6       False

В качестве дополнительного набора тестовых случаев, учтите, что любой ввод, где сетка состоит исключительно из пробелов, должен давать ложный результат.

Я проверил все контрольные примеры вручную, поэтому дайте мне знать, если вы считаете, что я допустил ошибку.

Мартин Эндер
источник
4
@Fatalize Я получаю воспоминания Twitch Plays Pokemon ...
подземный
«В качестве входных данных будет использоваться сетка конвейера, как описано выше, а также ширина и высота груза. Вы можете выбрать эти три параметра в любом удобном порядке и формате». - означает ли это, что мы можем использовать конвейерную сетку как массив массивов? То есть сетка 2х2 с [^^/v<]становится [[0,1] [0,1];[0,-1] [-1,0]]? Или вы имеете в виду, что нам решать, будет ли это STDIN, строковый ввод, ввод массива char и т. Д., Но все равно он должен быть в форме ^, v,> и <?
Глен О,
@GlenO Вы можете взять строку, разделенную символом новой строки (или другим символом), массив строк или массив массивов символов, но каждая ячейка все равно должна быть представлена ​​символами ><^vили пробелом. Я уточню это.
Мартин Эндер
Так что же произойдет, если груз перейдет к конфликту, когда продолжение движения не является одним из вариантов? То есть, если он двигался вправо, а теперь нужно выбирать между верхом и влево.
Джошуа

Ответы:

7

Рубин, 306 298 251 204 198

->g,w,h{m=->y,x,d,v=[]{q=y,x
r=->s{([""]*h+g)[y+h,h].map{|l|(?x*w+l)[x+w,w]}.join.count s}
z=k=r[?v]-r[?^],j=r[?>]-r[?<]
q[d=[d,1,0][j*j<=>k*k]]+=z[d]<=>0
v&[q<<d]!=[]?q!=v[-1]:m[*q,v<<q]}
m[0,0,1]}

Редактировать: Большое спасибо Ventero, который значительно сократил код, применяя некоторые удивительные трюки!

Вход и выход

Код представляет собой функцию ruby, которая принимает три параметра:

  • сетка, представленная в виде массива строк (каждая строка представляет собой отдельную строку)
  • ширина груза
  • высота груза

Возвращает 1(правда), если есть цикл, илиnil (ложно), если груз отдыхает.

тесты

Здесь он проходит все тесты Мартина: http://ideone.com/zPPZdR

объяснение

В коде нет хитрых трюков; это довольно простая реализация правил.

В приведенном ниже коде moveэто рекурсивная функция, которая делает движение в соответствии с правилами, и:

  • возвращает правду в случае цикла
  • возвращает ложь в случае отдыха
  • в противном случае вызывает себя для выполнения следующего шага

Более читаемая версия доступна здесь .

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

Кристиан Лупаску
источник
Поскольку не имеет значения, rсодержит ли дополнительные записи помимо четырех направлений, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1следует сохранить несколько байтов.
Вентеро
Я взял на себя смелость играть в гольф немного дальше, надеюсь, вы не возражаете: ideone.com/k69BmH
Ventero
@ Ventero Wow, вы сделали удивительные вещи с кодом. Я бы никогда не подумал о превращении хеша в лямбду. Я опробовал некоторые из своих идей по сокращению программы, но это было далеко от того, что вы сделали. Большое спасибо!
Кристиан Лупаску,
2
Понизил это до 200 через немного более короткую обработку отрицательных индексов, думаю, я пока оставлю это на этом: ideone.com/k69BmH
Ventero
2
На самом деле, 198: ideone.com/ptKrzf :)
Ventero
8

Python 2, 207 байт

def f(L,w,h,u=0,v=0,D=1,S=[]):a,b,c,d=map(`[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`.count,"v^><");D=cmp(abs(a-b),abs(c-d))<D;T=u,v,D;return T in S or a-b|c-d and f(L,w,h,u+cmp(c,d)*D,v+cmp(a,b)*0**D,D,S+[T])

Введите сетку в виде списка строк, например

['>v>v>v', '^v^v^v', '^v^v^v', '^>^>^v', '^<<<<<']

следуют ширина и высота. Возвращает 0или Trueсоответственно.

объяснение

def f(L,          # Grid
      w,h,        # Width, height of cargo
      u=0,v=0,    # Position of top-left of cargo, initially (0, 0)
      D=1,        # Moving left/right = 1, up/down = 0
      S=[]        # Seen (pos, axis) pairs, initially empty
     ):     

     # Arrows under cargo - no need for "".join since we only need to count v^<>
     A = `[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`

     # Count for each arrow
     a,b,c,d=map(A.count,"v^><")

     # Golfed form of abs(a-b) < abs(c-d) or (abs(a-b) == abs(c-d) and D == 1)
     D=cmp(abs(a-b),abs(c-d))<D
     T=u,v,D

     return (T in S                # Return True if (pos, axis) previously seen
             or a-b|c-d               # Return 0 if all conveyors cancel
             and f(L,w,h,             # Otherwise, recurse
                   u+cmp(c,d)*D,      # Update u if moving left/right
                   v+cmp(a,b)*0**D,   # Update v if moving up/down
                   D,
                   S+[T]          # Add (pos, axis) to seen
                  )
            )
Sp3000
источник
Вы не можете сократить его, присвоив cmpпеременную?
Голубой
Достаточно ли обнаружить циклы, проверяя уже посещенные позиции? На основании правила 4 на следующий шаг также может влиять предыдущее направление. Таким образом, кажется возможным, что вы могли бы прибыть в одну и ту же позицию дважды, но не иметь цикла, потому что вы двигаетесь в разных направлениях, основываясь на разных предыдущих направлениях.
Рето Коради
@muddyfish Это просто безубыточно
Sp3000
@RetoKoradi Надеюсь исправлено
Sp3000
Да, добавление Dк позиции ключа должно сделать это.
Рето Коради
8

Юлия - 394 300 246 214 байт

f(A,x,y)=(Z=sign;(S,T)=size(A);X=x+1;Y=y+1;G=fill(5,S+2y,T+2x);G[Y:S+y,X:T+x]=A;C=0G;D=1;while C[Y,X]!=D C[Y,X]=D;i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1]);D=Z(2i^2-2j^2+(i!=0)D);X+=Z(i+D*i);Y+=Z(j-D*j)end;D^2)

Возвращает 1, если груз зацикливается, и 0, если он останавливается. Это не «строго» правда / ложь, поскольку Юлия не допускает 0 и 1 в логических контекстах ... но я рассматриваю значения, xдля которых bool(x)==trueправдива иbool(x)==false ложны.

Ввод Aдолжен быть в форме массива символов. Если вы копируете / вставляете конвейерную сетку, вам нужно привести ее в соответствующую форму. Чтобы избавить вас от необходимости обрабатывать его вручную, используйте следующее:

A=foldl(hcat,map(collect,split("""(PASTE GRID HERE)""","\n")))'

Где, очевидно, (PASTE GRID HERE) следует заменить саму сетку. Дважды проверьте пробелы в конце каждой строки, чтобы убедиться, что на самом деле в ней есть все пробелы (не проверяется, чтобы убедиться, что все строки имеют одинаковую длину). Обратите внимание, что эта строка не является частью реального кода решения, а просто является удобным фрагментом кода, который упрощает использование кода решения.

Ungolfed:

function f(A,x,y)
  # Determine size of grid for use later
  (S,T)=size(A)
  # Initialise starting position (performed here to save characters)
  X=x+1
  Y=y+1
  # Create an expanded field that is functionally "spaces" (to provide
  # spaces at edges for the cargo to stop in)
  G=fill(5,S+2y,T+2x)
  # Put the conveyor grid into centre of the expanded field
  G[Y:S+y,X:T+x]=A
  # Create an array storing the most recent movement direction:
  # will use 1=horizontal, -1=vertical, 0=stopped
  C=0G
  # Initialise current direction (same system as C)
  D=1
  # Loop until it finds itself repeating a coordinate/direction pair
  while C[Y,X]!=D
    # Mark current coordinate/direction pair in array
    C[Y,X]=D
    # Determine the net coordinate pairing, stored in two variables
    # for golf purposes *SEE NOTE*
    i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1])
    # Determine new movement axis (if D=0, cargo stopped)
    D=sign(2i^2-2j^2+(i!=0)D)
    # Update X or Y depending on signs of D and the appropriate direction
    X+=sign(i+D*i)
    Y+=sign(j-D*j)
  end
  # if D=±1, return 1 (cargo is still moving), otherwise return 0
  return D^2
end

Примечание: 1-[19 8]i%82%3был выбран для сопоставления пяти возможных символов с соответствующими парами координат наиболее эффективным способом, который я смог найти. Это также причина использования 5 для заполнения пробелов при создании G- это однозначный символ, который отображается на [0 0].

Пример использования:

julia> A=foldl(hcat,map(collect,split(""">v>v>v
       ^v^v^v
       ^v^v^v
       ^>^>^v
       ^<<<<<""","\n")))';

julia> f(A,2,1)
true

julia> f(A,3,3)
true

julia> f(A,5,2)
false
Глен О
источник
f(A,x,y)=короче чем f=(A,x,y)->.
Алекс А.
@AlexA. - правда, но тогда я, вероятно, удалю f=и сделаю это анонимной функцией, когда закончу играть в гольф.
Глен O
1
Это будет той же длины, если это именованная функция по сравнению с анонимной функцией, когда есть несколько параметров. f()=по сравнению с ()->.
Алекс А.