Свергнуть несколько домино!

22

Спасибо за этот вопрос для вдохновения

В этих проблемах мы будем представлять линию домино в виде строки |, /и \. Вам дадут строку домино в качестве входных данных, и вы должны определить, как они выглядят, когда они обосновались. Вот правила того, как домино падает

  • Постоянное домино, |оставленное левым упавшим домино \, также станет левым упавшим домино.

  • Постоянное домино, |справа от правого падшего домино /, также станет правым падшим домино.

  • Если стоящее домино находится между левым \и правым упавшим /домино, оно останется стоять.

Эти правила применяются неоднократно, пока договоренность больше не изменится.

Вот пример того, как один вход может прийти к своему выводу

|||||||\/|||||||\||\|||/||||||\|||||

||||||\\//|||||\\|\\|||//||||\\|||||
|||||\\\///|||\\\\\\|||///||\\\|||||
||||\\\\////|\\\\\\\|||////\\\\|||||
|||\\\\\////|\\\\\\\|||////\\\\|||||
||\\\\\\////|\\\\\\\|||////\\\\|||||
|\\\\\\\////|\\\\\\\|||////\\\\|||||

\\\\\\\\////|\\\\\\\|||////\\\\|||||

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

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

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

|||/||||  -> |||/////
|||\||||  -> \\\\||||
|/||||\|  -> |///\\\|
||/|||\|  -> ||//|\\|
||\|||/|  -> \\\|||//
Мастер пшеницы
источник
6
Обратная косая черта убегает! (Можем ли мы использовать другие символы?)
Арно
1
@Arnauld Нет, вы должны использовать косые черты.
Пшеничный волшебник
1
Я не могу ... понять, что убежать, а что нет.
полностью человек
Будет ли ввод когда-либо пустой строкой или одним символом?
Ручка двери
3
Меня беспокоит больше, чем следовало бы, чтобы такие вещи, как `//////// | \, считались стабильными.
MooseBoys

Ответы:

13

Сетчатка , 32 байта

+`(/.\\)|(/)\||\|(\\)
$1$2$2$3$3

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

объяснение

+Говорит Retina запустить замену в цикле до тех пор, пока не сможет изменить строку. Каждая замена вычисляет один шаг падающего домино. Сама замена - это три замены в одной, но это гарантирует, что они происходят одновременно:

(/.\\)...
$1

Это просто соответствует /|\(так же как /\\и /\\, но это не имеет значения) и вставляет его без изменений. Цель этого состоит в том, чтобы пропустить |падающие домино с обеих сторон, потому что это короче, чем исключение тех случаев с отдельными обходными путями в двух других случаях.

...(/)\|...
$2$2

Это соответствует /|и превращает это в //.

...\|(\\)
$3$3

Это соответствует |\и превращает это в \\.

Мартин Эндер
источник
Не могу сказать, что не ожидал этого. Сетчатка, безусловно, хороший инструмент для работы.
Пшеница Волшебник
@WheatWizard Это легко решить, но, вероятно, все еще слишком многословно со всеми побегами и тем, $1$2$2$3$3чтобы превзойти языки игры в гольф.
Мартин Эндер
5

Python 2 , 115 114 111 108 98 95 байт

-1 байт благодаря овсу

a=input()
for i in range(4)*len(a):a=a.replace('//|x||\ \\'[i::4],'/\/x|\/ \\'[3-i::4])
print a

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

прут
источник
114 байтов с использованием r-строк.
овс
Вы можете удалить b=0;и заменить вхождения b, idчтобы сохранить два байта!
Линн
4

V , 23 байта

òÓ¯À<!|¨Ü©ü¨¯©|ÜÀ!/±±²²

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

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

HexDump:

00000000: f2d3 afc0 3c21 7ca8 dca9 fca8 afa9 7cdc  ....<!|.......|.
00000010: c021 2fb1 b1b2 b2                        .!/....

Объяснение:

òговорит V запускаться до тех пор, пока строка не изменится. Остальное - сжатое регулярное выражение. Давайте преобразовать его в эквивалент vim ...

:s/\v\/@<!\|(\\)|(\/)\|\\@!/\1\1\2\2/g

:s/                                     " Substitute...
   \v                                   " Turn on magic (use less escaping)
          \|                            " A bar
            (\\)                        " Followed by a captured backslash
       @<!                              " That is not preceded by
     \/                                 " A forward slash
                |                       " OR...
                 (\/)                   " A captured forward slash
                     \|                 " Followed by a bar
                       \\@!             " That is not followed by a backslash
                           /            " Replace this with
                            \1\1        " Pattern 1 twice (will be empty if we matched the second path)
                                \2\2    " Pattern 2 twice (will be empty if we matched the first path)
                                    /g  " Replace every match on this line
DJMcMayhem
источник
4

SNOBOL4 (CSNOBOL4) , 117 115 112 111 байт

	D =INPUT
S	D '/|\' ='_'	:S(S)
	E =D
	D '/|' ='//'
	D '|\' ='\\'
	D E	:F(S)
R	D '_' ='/|\'	:S(R)
	OUTPUT =D
END

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

Благодарим Питона за ответ Родона за идею условия остановки со второй переменной, чтобы увидеть изменения, а не тестирование D '/|' | '|\'.

	D =INPUT		;* read input
S	D '/|\' ='_'	:S(S)	;* replace '/|\' with '_', recursively
	E =D			;* set E to D, this is the while loop
	D '/|' ='//'		;* topple right
	D '|\' ='\\'		;* topple left
	D E	:F(S)		;* if D doesn't match E, goto S
R	D '_' ='/|\'	:S(R)	;* replace '_' with '/|\' (inverse of statement S)
	OUTPUT =D		;* output
END
Giuseppe
источник
3

Haskell , 114 107 байт

until=<<((==)=<<)$g
g s=t<$>zip3('|':s)s(tail s++"|")
t(l,'|',r)|l<'0',r/='\\'=l|r=='\\',l>'/'=r
t(_,e,_)=e

Попробуйте онлайн! Первая строка определяет анонимную функцию.

Объяснение:

  • until=<<((==)=<<)$gявляется функцией фиксированной точки (см. здесь для объяснения), которая применяет функцию gк входной строке, пока результат больше не изменяется.
  • zip3('|':s)s(tail s++"|")создает для каждого домино, то есть символа в строке s, тройку с пре- и последующим домино с отступами |по краям. Например, /\|становится [(|,/,\),(/,\,|),(\,|,|)](игнорируя побег).
  • Затем функция tприменяется к каждой из троек, чтобы вычислить новую позицию центральной части тройки.
Laikoni
источник
2

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

+[]-->[].
+[47,124,92|T]-->"/|\\",+T.
+[47,47|T]-->"/|",+T.
+[92,92|T]-->"|\\",+T.
+[X|T]-->[X],+T.
X+Y:- +(N,X,[]),!,(X=N,Y=N;N+Y).

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

Эта программа определяет предикат, +/2который является истинным, если второй аргумент является установленной версией первого. Оба аргумента являются списками кодов символов.

объяснение

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

DCG

+[]-->[].
+[47,124,92|T]-->"/|\\",+T.
+[47,47|T]-->"/|",+T.
+[92,92|T]-->"|\\",+T.
+[X|T]-->[X],+T.

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

+[]-->[].

Эта строка представляет базовый вариант +правила. В нем просто говорится, что если в настоящее время нет домино, то на следующем шаге все еще не будет домино.

+[47,124,92|T]-->"/|\\",+T.

Поскольку эта программа имеет дело исключительно со списками кодов символов, важно отметить , что коды символов для /, \и |в 47, 92 и 124 соответственно. Этот случай +правила обрабатывает /|\строку.

+[47,47|T]-->"/|",+T.

Этот случай обрабатывает правильное падение домино, опрокидывая домино справа от него. Так как он идет после случая для обработки, /|\он не будет использоваться для этой возможности.

+[92,92|T]-->"|\\",+T.

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

+[X|T]-->[X],+T.

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

Предикат

X+Y:- +(N,X,[]),!,(X=N,Y=N;N+Y).

Основной предикат принимает два аргумента, первый - начальная настройка домино, второй - установленное домино. Поскольку это Пролог, второе может быть неопределенным, и программа его вычислит. Сам по себе предикат довольно прост, +(N,X,[])вызывает DCG и вычисляет следующий шаг домино, в котором он хранится N. (X=N,Y=N;N+Y)проверяет, совпадает ли следующий шаг домино с текущим и устанавливает Yли он его, поскольку домино должно быть установлено, и если это не так, повторяется, вызывая тот же предикат со следующим шагом домино Nвместо X.

0 '
источник
1

лицо , 166 байт

\|/,cm_/o>AvI[IIcP/+PP|m_/m*/Sl*Im1/11:~-_I|'|?_1-_P|?_1`I-III_|+II|'I.C:1-_I|?_C'|-_P|?_C_|'I-_I|`I?_!'I.C:!'|'|-III+II|'I:C_|-PPP+PPI'I?I~_I-PPP+PP|-**1?*~Sl*Iw*I*>

Принимает ввод в качестве аргумента командной строки и выводит в STDOUT. Это работает только в коммите 86494f6 и выше из-за исправления в этом коммите.

Обернутый для эстетики:

\|/,cm_/o>AvI[IIcP/+PP|m_/m*/Sl*Im1/11:~-_I|'|?_1-_P|?_1`I
-III_|+II|'I.C:1-_I|?_C'|-_P|?_C_|'I-_I|`I?_!'I.C:!'|'|-III
+II|'I:C_|-PPP+PPI'I?I~_I-PPP+PP|-**1?*~Sl*Iw*I*>

И разглазил / прокомментировал:

\|/,cm_/o>              ( setup )

AvI[II                  ( store input into I )
cP/+PP|m_/              ( store 92, ascii for \, into P, meaning prev char )
m*/Sl*Im1/11            ( store length of input into counter variable * )

( main loop: )
:~

    -_I|'|?_1           ( branch to 1 if the character is not \ )
    -_P|?_1             ( also branch to 1 if the previous character wasn't | )
    `I-III_|+II|'I      ( we have a sequence |\ so prev needs to be toppled )
    .C                  ( jump to C, the "continue" label at end of loop )

    :1
    -_I|?_C             ( branch to C if the character is not | )
    '|-_P|?_C           ( also branch to C if the previous character wasn't / )
    _|'I-_I|`I?_!       ( branch to ! if the next character isn't \ )
    'I.C:!              ( otherwise, skip the next \ and branch to continue )
    '|'|-III+II|'I      ( if all conditions hold we have /|| or /|/ so topple )

    :C
    _|                  ( reset pointer to source )
    -PPP+PPI            ( update prev variable )
    'I                  ( step through data )

?I~

_I-PPP+PP|-**1          ( reset input/prev and decrement counter )
?*~                     ( repeat main loop as many times as there are chars )

Sl*Iw*I*>               ( output final string to stdout )

Здесь есть несколько тонких уловок, которые сбрасывают несколько дополнительных байтов, таких как

  • именование переменных | и /, чьи значения ASCII доступны через интроспекцию позже в коде

  • в '|первой строке основного цикла, которая вызывается там, а не во второй строке, чтобы установить | указатель для использования во втором разделе основного цикла

Дверная ручка
источник
1

Perl 5 , 52 + 1 (-p) = 53 байта

-6 байт благодаря мику

Наверное, не лучший вариант для Perl, но это то, что я мог придумать.

0while(s/(?<!\/)\|(?=(\\))|(?<=(\/))\|(?!\\)/$1$2/g)

объяснение

while(
  s/
    (?<!\/)\|(?=(//)) # If there's a | that precedes a \ but doesn't follow a /, capture /
      | # Or
    (?<=(\/))\|(?!//)/ # If there's a | that follows a / doesn't precede a \, capture /
  /$1$2/ # Replace all | with capture group 1 or 2, as one of the two will always be empty
  g # Repeat as much as possible for this string
)

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

Джеффри Х.
источник
-pвместо того, чтобы -aустранить необходимость в print;; используя в whileкачестве суффикса к выражению манекена (например 0) сохранит еще 2 байта
МИК
Спасибо @mik, я не знал этих трюков. Я также понимаю, что мог бы ограничить регулярное выражение чем-то другим, чтобы сэкономить несколько байтов. Возможно, дойдем до этого позже.
Джеффри Х.
1

Perl 5 , 44 (код) + 1 ( -p) = 45 байт

1while s,(/)\|(?!\\)|(?<!/)\|(\\),$1$1$2$2,g

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

объяснение

1while s,                        ,        ,g   while anything found substitute globally
         (/)\|(?!\\)              $1$1         /| that is not followed by \ to //
                    |                          or
                     (?<!/)\|(\\)     $2$2     |\ that is not preceded by / to \\
МИК
источник
0

Рубин , 83 байта

Технически читерство 9.times, или даже просто, 999.timesно я не чувствую себя дешевым :)

По-прежнему имеет огромный гольф-потенциал. (Примечание: y while undoneгораздо дольше, чем x.size.times)

->x{x.size.times{x.gsub! /\/\|\\?|\|\\/,'/|\\'=>'/|\\','/|'=>'//','|\\'=>'\\\\'}
x}

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

Unihedron
источник
0

R , 114 байт

function(d){g=gsub
for(i in 1:nchar(d))d=g("/|","//",g("|\\","\\\\",g("/|\\","_",d,f=T),f=T),f=T)
g("_","/|\\",d)}

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

Возвращает экранированную строку.

Giuseppe
источник
0

C (gcc) , 183 байта

D,i;f(char*S){char*s=malloc(-~strlen(S));for(D=1;D--;strcpy(S,s))for(strcpy(s,S),i=0;s[i];i++)s[i]>92&&(S[-~i]==92&&S[~-i]!=47&&(s[i]=92,D=1)||S[~-i]==47&&S[-~i]!=92&&(s[i]=47,D=1));}

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

Джонатан Фрех
источник