Эта задача слабо вдохновлена игрой Zachtronics Infinifactory .
Вам предоставляется вид сверху прямоугольной сетки конвейеров, представленной >v<^
. Могут быть ячейки без конвейеров, представленные пробелами. Вот пример:
> <vv <
v ^ >v v
>v^^>vv^
^>^ v
> v<v >>
>v v<^
Эта установка неявно окружена бесконечным числом пробелов.
Кроме того, вам даны размеры прямоугольного куска груза, который помещается на конвейеры в верхнем левом углу сетки. Ваша задача - выяснить, остановится ли груз когда-нибудь или он будет двигаться по кругу.
Конечно, груз может покрывать несколько конвейеров одновременно, поэтому вот правила для определения направления груза на каждом этапе:
Противоположные конвейеры отменяют друг друга. Таким образом, если груз 3х2 покрывает любой из следующих патчей (для ясности обведен дефисами и трубками), результат будет таким же:
+---+ +---+ +---+ |>>^| | ^| |v^^| |^<<| |^ | |^^v| +---+ +---+ +---+
То же самое касается этих:
+---+ +---+ +---+ |v^<| | | |><>| |>>>| |>> | |>><| +---+ +---+ +---+
Поскольку точное положение конвейера под грузом не имеет значения, не имеет значения, какие пары вы отменяете.
Эта отмена применяется раньше других правил. Следовательно, для других правил конвейеры будут использоваться не более чем в двух направлениях.
- Если груз не покрывает какие-либо конвейеры вообще (либо потому, что все конвейеры отменяются, потому что он охватывает только пространства или потому что он полностью сдвинулся с сетки), он останавливается.
Если груз покрывает больше конвейеров в одном направлении, чем в другом, груз перемещается в этом направлении. Например, если груз 3х2 покрыл следующий патч
>> ^>^
он будет двигаться вправо, потому что есть больше,
>
чем^
. С другой стороны, если это покрыто>>^ ^
это правило не будет применяться, потому что между
>
и^
.Это оставляет только случаи, в которых есть связь между смежными направлениями (связь между противоположными направлениями была бы отменена). В этом случае груз продолжает двигаться вдоль оси, по которой он уже движется. Например, если груз 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
В качестве дополнительного набора тестовых случаев, учтите, что любой ввод, где сетка состоит исключительно из пробелов, должен давать ложный результат.
Я проверил все контрольные примеры вручную, поэтому дайте мне знать, если вы считаете, что я допустил ошибку.
источник
[^^/v<]
становится[[0,1] [0,1];[0,-1] [-1,0]]
? Или вы имеете в виду, что нам решать, будет ли это STDIN, строковый ввод, ввод массива char и т. Д., Но все равно он должен быть в форме ^, v,> и <?><^v
или пробелом. Я уточню это.Ответы:
Рубин,
306 298 251 204198Редактировать: Большое спасибо Ventero, который значительно сократил код, применяя некоторые удивительные трюки!
Вход и выход
Код представляет собой функцию ruby, которая принимает три параметра:
Возвращает
1
(правда), если есть цикл, илиnil
(ложно), если груз отдыхает.тесты
Здесь он проходит все тесты Мартина: http://ideone.com/zPPZdR
объяснение
В коде нет хитрых трюков; это довольно простая реализация правил.
В приведенном ниже коде
move
это рекурсивная функция, которая делает движение в соответствии с правилами, и:Более читаемая версия доступна здесь .
Примечание: код для игры в гольф претерпел несколько изменений и больше не похож на читаемую версию.
источник
r
содержит ли дополнительные записи помимо четырех направлений,r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1
следует сохранить несколько байтов.Python 2, 207 байт
Введите сетку в виде списка строк, например
следуют ширина и высота. Возвращает
0
илиTrue
соответственно.объяснение
источник
cmp
переменную?D
к позиции ключа должно сделать это.Юлия -
394300246214 байтВозвращает 1, если груз зацикливается, и 0, если он останавливается. Это не «строго» правда / ложь, поскольку Юлия не допускает 0 и 1 в логических контекстах ... но я рассматриваю значения,
x
для которыхbool(x)==true
правдива иbool(x)==false
ложны.Ввод
A
должен быть в форме массива символов. Если вы копируете / вставляете конвейерную сетку, вам нужно привести ее в соответствующую форму. Чтобы избавить вас от необходимости обрабатывать его вручную, используйте следующее:Где, очевидно,
(PASTE GRID HERE)
следует заменить саму сетку. Дважды проверьте пробелы в конце каждой строки, чтобы убедиться, что на самом деле в ней есть все пробелы (не проверяется, чтобы убедиться, что все строки имеют одинаковую длину). Обратите внимание, что эта строка не является частью реального кода решения, а просто является удобным фрагментом кода, который упрощает использование кода решения.Ungolfed:
Примечание:
1-[19 8]i%82%3
был выбран для сопоставления пяти возможных символов с соответствующими парами координат наиболее эффективным способом, который я смог найти. Это также причина использования 5 для заполнения пробелов при созданииG
- это однозначный символ, который отображается на[0 0]
.Пример использования:
источник
f(A,x,y)=
короче чемf=(A,x,y)->
.f=
и сделаю это анонимной функцией, когда закончу играть в гольф.f()=
по сравнению с()->
.