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

31

Есть 95 печатных символов ASCII :

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

В шрифте Consolas (по умолчанию блок кода Stack Exchange) некоторые символы имеют зеркала вокруг вертикальной оси симметрии:

  • Эти пары символов являются зеркалами друг друга: () [] {} <> /\
  • Эти символы являются зеркалами самих себя: ! "'*+-.8:=AHIMOTUVWXY^_ovwx|(Обратите внимание, что пробел один.)
  • У них нет зеркал: #$%&,012345679;?@BCDEFGJKLNPQRSZ`abcdefghijklmnpqrstuyz~

( i, l, 0, #, И , возможно , другие персонажи являются их собственные зеркала в некоторых шрифтах , но мы будем придерживаться формы Consolas.)

Строка называется зеркалом сама по себе, если она состоит только из 39 зеркальных символов , расположенных так, что строка имеет центральную вертикальную линию симметрии. Так ](A--A)[зеркало само по себе, но ](A--A(]это не так.

Напишите однолинейную программу четной длины, которая сама по себе является зеркалом. Когда к нему добавлено N копий его левой половины, и к нему добавлено N копий его правой половины, он должен вывести N + 1. N является неотрицательным целым числом.

Например, если программа была ](A--A)[(левая половина:, ](A-правая половина:) -A)[, то:

  • Бег ](A--A)[должен выводить 1. (N = 0)
  • Бег ](A-](A--A)[-A)[должен выводить 2. (N = 1)
  • Бег ](A-](A-](A--A)[-A)[-A)[должен выводить 3. (N = 2)
  • Бег ](A-](A-](A-](A--A)[-A)[-A)[-A)[должен выводить 4. (N = 3)
  • , , ,
  • Бег ](A-](A-](A-](A-](A-](A-](A-](A-](A-](A--A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[должен выводить 10. (N = 9)
  • и т.п.

правила

  • Выведите на стандартный вывод или ближайшую альтернативу вашего языка. Там может быть необязательный завершающий перевод строки. Вклад не должен быть взят.
  • Процесс должен теоретически работать для N до 2 15 с -1 или выше, при условии достаточной памяти и вычислительной мощности.
  • Требуется полная программа, а не просто команда REPL .

Самая короткая начальная программа (N = 0) в байтах побеждает.

Кальвин Хобби
источник
В некоторых шрифтах #тоже есть свое отражение, но, вы правы, не в консолах.
SuperJedi224
1
Использование repls разрешено? Другими словами: мы должны написать полную действительную программу или достаточно выражения? Я думаю о записи в Haskell, которая будет работать при запуске в ghci, но не является полноценной программой.
Бакуриу
@Bakuriu Требуется полная программа. Ответ на Haskell неверен.
Увлечения Кэлвина
4
Почему «b» и «d» являются зеркалами друг друга? Это делает мой план невозможным: П
Тийс тер Хаар
1
@ThijsterHaar Я на самом деле не учел это, но похоже, что их формы «Консоласа» немного отличаются, извините: P
Увлечения Кэлвина

Ответы:

20

Пип, 12 8 4 байта

Теперь на 66% меньше байтов!

x++x
  • xпеременная, предварительно инициализированная в "". В числовом контексте это становится 0.
  • Первая половина, без финала +, является выражением формы x+x+...+x. Это верное утверждение, которое ничего не делает.
  • Вторая половина, включая финал +первой половины, является выражением формы ++x+x+...+x. ++xприращения xк 1, а остальное добавляет его к себе N раз. Поскольку выражения оцениваются слева направо в Pip, приращение гарантированно произойдет первым, а результат будет равен количеству уровней отражения.
  • В конце значение этого выражения печатается автоматически.

К сожалению, Pip плохо обрабатывает огромные выражения: это решение вызывает maximum recursion depth exceededошибку для N больше 500 или около того. Вот предыдущее решение, которое не для 8 байтов :

x++oo++x

Больше на Пипе

DLosc
источник
Хорошо, если кто-то не отправит 2-байтовый ответ, похоже, что у вас есть этот в сумке. Кстати, я не знаю, запускали ли вы его с N = 32767 , но на самом деле это результат Fatal error: maximum recursion depth exceeded while calling a Python object.
Деннис
@ Деннис Да, я столкнулся с этим на самом деле - это начинается довольно рано, около 600, если не раньше. Причина в том, что выражения оцениваются сначала путем рекурсивной оценки всех подвыражений, поэтому x+x+...+xгенерирует O (N) глубину рекурсии. Может быть, это лишает законной силы этот ответ. Я добавлю заметку.
DLosc
Предел рекурсии легко настраивается в Python, не так ли?
Деннис
@ Денис Да, хотя есть ужасные предупреждения о том, что он сделает с вашей системой, если вы установите слишком высокое значение, поэтому я никогда не пробовал. ;) Кроме того, настроить его изнутри Пипа невозможно , так что мне это кажется обманом. Если вы хотите попробовать это, мне было бы интересно услышать результаты.
DLosc
Я пробовал. На моей машине увеличение предела рекурсии до 20000 уже сегфоултс. Но поскольку ответ должен работать только при условии достаточной памяти и вычислительной мощности , это не должно быть проблемой.
Деннис
34

GolfScript, 10 байт

!:{)::(}:!

Попробуйте онлайн с помощью Web Golfscript: N = 0 , N = 1 , N = 2 , N = 3 , N = 41

Web GolfScript имеет ограничение в 1024 символа, но интерпретатор Ruby прекрасно обрабатывает N = 32767 :

$ curl -Ss http://www.golfscript.com/golfscript/golfscript.rb > golfscript.rb
$ echo '"!:{):"32768*":(}:!"32768*' | ruby golfscript.rb > mirror-level-32767.gs
$ ruby golfscript.rb mirror-level-32767.gs
32768

Как это работает

Без какого-либо ввода у GolfScript изначально есть пустая строка в стеке.

В первой левой половине происходит следующее:

  • !применяет логическое НЕ к пустой строке. Это подталкивает 1.

  • :{сохраняет целое число в стеке в переменной {.

    Да, это действительный идентификатор, хотя нет способа извлечь сохраненное значение.

  • ) увеличивает целое число в стеке

  • : это неполная инструкция

В последующих левых половинах происходит следующее:

  • :!(где :остаток от предыдущего) сохраняет целое число в стеке в переменной !.

    Да, это также действительный идентификатор. Это нарушает !команду, но мы ее больше не используем.

  • :{, )И :работа , как и раньше.

В первой правой половине происходит следующее:

  • ::(где :остаток от предыдущего) сохраняет целое число в стеке в переменной :.

    Да, даже это действительный идентификатор. Как и в случае с {, нет способа извлечь сохраненное значение.

  • ( уменьшает целое число в стеке, получая количество левых половинок.

  • }, поскольку он не имеет аналогов и немедленно прекращает выполнение.

    Это недокументированная функция. Я называю их суперкомментариями .

Оставшийся код просто игнорируется.

Деннис
источник
Кажется действительно странным иметь непревзойденную }во второй половине вашего кода в зеркальном конкурсе.
ballesta25
Это обычная уловка в палиндромных вариантах. В "\""/"четвертой двойной кавычке также не будет совпадений, так как второй был экранирован.
Деннис
27

Машинный код Z80, 8 6 байтов *

<8ww8> * Предполагает определенные условия, введя из Amstrad BASIC

<   INC A         // A=A+1
8w  JR C, #77     ## C is unset unless A has overflowed, does nothing

w   LD (HL), A    // Saves A to memory location in HL (randomly initialised)
8>  JR C, #3E     ## C is still unset, does nothing

Aизначально 0 при вводе из бейсика. Он увеличивает A n раз, а затем записывает его n раз в одну и ту же ячейку памяти (которую BASIC устанавливает в слегка случайную позицию)! Операция JRJump Relative никогда не делает ничего, поскольку Cфлаг всегда не установлен, поэтому используется для «закомментирования» следующего байта! Эта версия слегка обманывает, предполагая определенные условия входа, а именно, вход из BASIC гарантирует, что Aвсегда 0. Местоположение (HL)не гарантируется безопасным, и фактически, вероятно, опасное местоположение. Приведенный ниже код намного надежнее, поэтому он намного длиннее.

Машинный код Z80, 30 байтов

Как ASCII: o!.ww.!>A=o>{))((}<o=A<!.ww.!o

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

o   LD L, A       ## 
!.w LD HL, #772E  // Load specific address to not corrupt random memory!
w   LD (HL), A    ## Save random contents of A to memory
.!  LD L, #21     ## 
>A  LD A, #41     // A=#41
=   DEC A         // A=#40
o   LD L, A       // L=#40
>{  LD A, #7B     ## 
)   ADD HL, HL    // HL=#EE80
)   ADD HL, HL    // HL=#DD00. L=#00 at this point

((  JR Z, #28     ## 
}   LD A, L       // A=L
<   INC A         // A=L+1
o   LD L, A       // L=L+1
=   DEC A         // A=L
A   LD B, C       ## 
<   INC A         // A=L+1
!.w LD HL, #772E  // Load address back into HL
w   LD (HL), A    // Save contents of A to memory
.!  LD L, #21     ## 
o   LD L, A       // L=A

Разбивка разрешенных инструкций:

n   op    description
--  ----  -----------
28  LD    LoaD 8-bit or 16-bit register
3   DEC   DECrement 8-bit or 16-bit register
1   INC   INCrement 8-bit or 16-bit register
1   ADD   ADD 8-bit or 16-bit register

Available but useless instructions:
3   JR    Jump Relative to signed 8-bit offset
1   DAA   Decimal Adjust Accumulator (treats the A register as two decimal digits
          instead of two hexadecimal digits and adjusts it if necessary)
1   CPL   1s ComPLement A
1   HALT  HALT the CPU until an interrupt is received

Из 39 разрешенных инструкций 28 являются операциями загрузки (все блоки от 0x40 до 0x7F являются однобайтовыми LDинструкциями), большинство из которых здесь не помогут! Единственная разрешенная инструкция загрузки в память - LD (HL), Aэто значит, что я должен хранить значение в A. Поскольку Aэто единственный регистр с разрешенной INCинструкцией, это на самом деле очень удобно!

Я не могу загрузить Aс 0x00, чтобы начать с, потому что ASCII 0x00 не разрешенный символ! Все доступные значения далеки от 0, и все математические и логические инструкции запрещены! За исключением ... Я все еще могу сделать ADD HL, HL, добавить 16-битный HLсебе! Помимо прямой загрузки значений (здесь нет смысла!), INCrementing Aи DECrementing A, Lили HLэто единственный способ изменить значение регистра! На самом деле есть одна специальная инструкция, которая может быть полезна в первой половине, но во второй половине боль обходится, и инструкция с одним дополнением, которая здесь почти бесполезна и просто займет место.

Итак, я нашел наиболее близкое значение к 0, которое я мог: 0x41. Как это близко к 0? В двоичном виде это 0x01000001. Поэтому я уменьшаю его, загружаю Lи делаю ADD HL, HLдважды! Lтеперь ноль, который я загружаю обратно A! К сожалению, код ASCII для ADD HL, HLэто , )так что я теперь нужно использовать (дважды. К счастью, (это JR Z, e, где eнаходятся следующие байты. Таким образом, он поглощает второй байт, и мне просто нужно убедиться, что он ничего не делает, будучи осторожным с Zфлагом! Последней инструкцией, влияющей на Zфлаг, была DEC A(нелогично, ADD HL, HLне меняет ее), и, поскольку я знаю, что Aв тот момент это было 0x40, гарантируется, что Zона не установлена.

Первая инструкция во второй половине JR Z, #28ничего не будет делать первые 255 раз, потому что флаг Z может быть установлен только в том случае, если A переполнился с 255 до 0. Однако после этого выходной сигнал будет неправильным, поскольку в любом случае он сохраняет только 8-битные значения, не должно иметь значения. Код не должен быть расширен более 255 раз.

Код должен быть выполнен как фрагмент кода, поскольку все доступные способы возврата полностью запрещены. Все инструкции RETurn превышают 0x80, и несколько разрешенных операций перехода могут переходить только к положительному смещению, поскольку все 8-битные отрицательные значения также запрещены!

CJ Деннис
источник
6
ЧТО. ЧТО ЭТО.
облачные ноги
4
Теперь я видел этот ответ, используя GolfScript / J / etc. просто кажется обманом. : p
cloudfeet
Существуют ли Z80-совместимые процессоры с 16-битным регистром А? Я спрашиваю, так как вопрос требует, чтобы код работал для N = 32767 .
Деннис
1
@Dennis Чтобы программа работала для N = 32767, она должна быть длиной не менее 2 x 32767 или 65534 байта. Z80 может адресовать только 65536 байт памяти, что делает эту задачу невозможной, поскольку я не верю, что смогу сделать программу меньше 6 байт! AРегистр всегда 8 бит, в противном случае процессор не будет совместим с Z80. Я бы сказал, что при наличии достаточного количества памяти и вычислительной мощности здесь это было закрыто!
CJ Деннис
1
@ Dennis Вы понимаете, почему ни один Z80-совместимый процессор не будет иметь Aрегистр чего-либо, кроме 8 бит? Изменение его до 16-бит нарушило бы код , опираясь на 255 + 1 = 0, например. Вам придется изобрести процессор, назовем его Z160, который использует 16-битный регистр по умолчанию, но все еще использует тот же 8-битный набор команд из Z80. Weird!
CJ Деннис
19

J 16 16 байт

(_=_)]++[(_=_)

Обычаи:

   (_=_)]++[(_=_)
1
   (_=_)]+(_=_)]++[(_=_)+[(_=_)
2
   (_=_)]+(_=_)]+(_=_)]++[(_=_)+[(_=_)+[(_=_)
3

Объяснение:

  • J оценивает справа налево.

  • (_=_)is inf equals infis true, имеет значение 1, поэтому выражение становится 1+]...[+1. ( (8=8)также будет работать, но это выглядит круче. :))

  • [и ]вернуть их левый и правый аргументы соответственно, если у них есть 2 аргумента. Если они получают только 1, они возвращают это.

  • +добавляет 2 аргумента. Если он получает только 1, он возвращает это.

Теперь давайте оценим выражение уровня 3 (идущее справа налево):

(_=_)]+(_=_)]++[(_=_)+[(_=_)  NB. (_=_) is 1

1]+1]+1]++[1+[1+[1  NB. unary [, binary +

1]+1]+1]++[1+[2  NB. unary [, binary +

1]+1]+1]++[3  NB. unary [, unary +

1]+1]+1]+3  NB. unary +, binary ]

1]+1]+3  NB. unary +, binary ]

1]+3  NB. unary +, binary ]

3

Как мы видим, правая половина из 1's' добавляется, а левая часть 1'' s 'опускается, в результате чего получается целое число N, уровень зеркала.

Попробуйте это онлайн здесь.

randomra
источник
12

Haskell, 42 байта

(8-8)-(-(8-8)^(8-8))--((8-8)^(8-8)-)-(8-8)

К счастью, --строковый комментарий в Haskell (-> ) является зеркальным, а половина (-> -) является допустимой функцией. Остальное - математика, чтобы получить числа 0и 1. В основном мы имеем (0)-(-1)с комментариями N=0и prepend (0)-(-1)-на каждом шаге.

Если числа с плавающей запятой разрешены для вывода, мы можем построить 1из 8/8и обойтись с 26 байтами:

Haskell, 26 байтов

(8-8)-(-8/8)--(8\8-)-(8-8)

Выходы 1.0, 2.0и т.д.

Ними
источник
2
Это технически неверно, так как это должна быть полная программа.
Увлечения Кэлвина
@ Calvin'sHobbies: Понятно. Есть ли у нас консенсус в отношении минимальных требований для полной программы? Я искал мета, но нашел только обсуждение функций, а не программ. В зависимости от определения полной программы, я мог бы исправить свое решение.
Ними
Я бы назвал это полной программой, если вы можете сохранить ее в файл, program.hsа затем запустить $ runhaskell program.hsиз командной строки и посмотреть результат. Я не знаю Хаскелла, поэтому не могу точно сказать, что нужно изменить.
Увлечения Кэлвина
2
@ Calvin'sHobbies: runhaskellэто сценарий оболочки, который устанавливает некоторое окружение и, наконец, вызывает ghcкомпилятор Haskell. Вы можете запустить свой код непосредственно ghc: ghc -e "(8-8)-(-8/8)--(8\8-)-(8-8)". Это запускает, ghcкоторый оценивает код, предоставленный в качестве аргумента, печатает результат и завершает работу. Нет REPL, нет взаимодействия. Конечно, это добавило бы +1 к числу байтов для -e.
Ними
@nimi: -eне влияет на счет в этом случае. Мы не считаем байт для perl -Eили gcc -std=c99ни.
Деннис
11

CJam, 14 байтов

]X+:+OooO+:+X[

Попробуйте онлайн в интерпретаторе CJam: N = 0 , N = 1 , N = 2 , N = 3 , N = 41

Обратите внимание, что этот код заканчивается сообщением об ошибке. Используя интерпретатор Java, это сообщение об ошибке может быть подавлено закрытием или перенаправлением STDERR. 1

Как это работает

В левой половине происходит следующее:

  • ] оборачивает весь стек в массив.

  • Xдобавляет 1к этому массиву.

  • :+ вычисляет сумму всех элементов массива.

  • Oo печатает содержимое пустого массива (т.е. ничего)

В первой правой половине происходит следующее:

  • o печатает целое число в стеке, которое является желаемым выводом.

  • O+ пытается добавить пустой массив к самому верхнему элементу стека.

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

Оставшийся код просто игнорируется.

1 Согласно мета-опросу Должны ли быть разрешены выходы с ошибкой? это разрешено

Деннис
источник
Я скептически отношусь к тому, чтобы принять это из-за ошибки, но так как это не победа, я не слишком обеспокоен
Увлечения Кэлвина
Задачи, подобные этой, на удивление сложны в CJam, учитывая, что это язык игры в гольф. Даже синтаксическая ошибка (например, неопределенный оператор) в неисполненном блоке будет препятствовать выполнению всей программы. Я все еще пытаюсь избавиться от ошибки.
Деннис