Копы и грабители: отредактированная первичность (нить грабителей)

9

Это нить грабителей. Нить полицейских здесь .

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

MD XF
источник

Ответы:

6

бред , Джо Кинг

>>>>>+>,[>++++++[-<-------->]<+>,]<[-[█<█<]++++++++++<]>[-]>>██[>█>>█>]+[<]<<[<]>█<<+>>[>]█>[>]█+[<]<<[<]>-█>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<█]>]>[>]<[[█]<]<<<<<[<]<<██>>[>]<█[->+<]<█>>[>]<[-[[<]<]++++++++++<]>███>[<<]>[[[>]>████[<]<[-[[<]<]++++++++++<]>[-]>[█<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>███████>[[█]>]<]<[[<]<]<[█]>]>>>[[>]<->>]]>[[>]>]<<[[[█]<]<]<<<[█]<<█>>>[>]█[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.
>>>>>+>,[>++++++[-<-------->]<+>,]<[-[[<]<]++++++++++<]>[-]>>[[[>]>>[>]+[<]<<[<]>[<<+>>[>]>>[>]<+[<]<<[<]>-]>]>>[->]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]<]<<<<<[<]<<[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]>[>]<[[-]>+[>]<-<[<]<]+<<<<<[<]>[[>]+[[>]>]>[>]>[-<+>]<[<]<[>+[<]>>-<<<<<[[<]<]>>[[-]+>]>[[>]>]<]<[[<]<]<[<]>]>>>[[>]<->>]]>[[>]>]<<[[[-]<]<]<<<[<]<<]>>>[>]<[-[[<]<]++++++++++<]>>[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]>[>]+[------->++<]>++.++.---------.++++.--------.

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

Это реализует сито Эратосфена.

Начальные >>>>>+>,[>++++++[-<-------->]<+>,]вводят каждую цифру в виде кода символа и вычитают 47, чтобы поместить ее в диапазон 1-10. Это позволяет значению ячейки 0 обозначать интервал между числами. В +>начале этого раздела число должно быть не менее двух цифр, что будет важно в ближайшее время.

Следующее, и первое, что я понял, это раздел <[-[[<]<]++++++++++<]>[-]>. Это встречается в коде несколько раз, каждый с различными шаблонами редактирования, но было нетрудно догадаться, что все эти экземпляры, вероятно, были одним и тем же кодом. Этот код требует три нуля слева от десятичного числа на ленте, и его эффект заключается в уменьшении числа. Последняя итерация цикла помещает значение 10 в две ячейки слева от числа, но [-]очищает его.

Если десятичное число было 0, посторонние 10 не создаются, а обнуляемая ячейка [-]является самой значимой цифрой. В этом случае головка ленты занимает вторую по значимости цифру (поэтому необходимы как минимум две цифры). За большинством экземпляров этого фрагмента сразу же следует [<<]>, что помещает головку в ненулевую ячейку в нормальных условиях и нулевую ячейку, если исходное десятичное число было равно нулю. Похоже, что в этой программе десятичное представление n-1используется для обозначения n, так что уменьшение до 0улавливается вместо уменьшения до -1.

Следующая часть помещает числа от n-1 (n) до 0 (1) на ленте:

>[                      until the number reaches zero:
  [                     for each digit:
    [>]>>[>]+[<]<<[<]>  create a placeholder for the next copy
    [                   while the original value of the digit is nonzero:
      <<+               add 1 to copy two cells left (to keep one copy)
      >>[>]>>[>]<+      go to new copy and increment that cell
      [<]<<[<]>-        go back to original digit and decrement
    ]                   (this is effectively the same as [<+>>+<-] but with the cells at variable locations)
  >]                    next digit
  >>[->]                cancel the placeholder 1s that were used for the new copy
  <[-[[<]<]++++++++++<]>[-]>[<<]> decrement
]
>[>]<[[-]<]      clean up the trash 10s on the tape while ending at a known location relative to the last number

Теперь эти числа находятся на ленте с двумя нулевыми ячейками, разделяющими их. <<<<<[<]<<помещает нас в последнюю ячейку предпоследнего числа на ленте, где мы будем находиться на каждой итерации цикла. Цикл завершается, когда обрабатываются все числа, кроме оригинала.

В начале цикла мы перемещаем текущее число (последнее еще на ленте) на одну ячейку вправо, чтобы иметь место для уменьшения, а затем продолжаем и уменьшаем:

[>>>[>]<[[->+<]<]>>[>]<[-[[<]<]++++++++++<]>[-]>[<<]>

Если это уменьшение не уменьшилось, мы переходим к преобразованию числа в унарное:

[[[>]>[>]+[<]<[-[[<]<]++++++++++<]>[-]>[<<]>]

Обратите внимание, что этот отрубленный имеет открытый [. В результате остальная часть этого цикла пропускается, если число было 0 (представляющее 1). После преобразования в унарный, мы убираем оставшиеся 10 с, перетаскивая унарное представление с нами влево:

>[>]<[[-]>+[>]<-<[<]<]+

Я не замечал, пока только что написал это, но +конец этого фрагмента отделен от унарного представления одним 0. Это также является частью унарного представления: последовательность 1011...11будет представлять 0 mod k. Следующее <<<<<[<]>ставит нас в начале числа k+1, начиная новый цикл.

Внутренний цикл здесь «помечает» каждое число на ленте с 1 на ячейке сразу справа и использует унарное представление в качестве часов, чтобы определить, какие числа кратны k.

[
  [>]+             mark the current decimal number
  [[>]>]           move to end of decimal part of tape
  >[>]             move to 0 in middle of unary "clock"
  >[-<+>]          move the following 1 to the left if possible
  <[<]<            if a 1 was moved this will bring us back to a zero before the start of this "clock";
                   otherwise the looped move command doesn't move us at all and we are at the final 1
  [                if there was no gap (happens every kth iteration):
    >+[<]>>-       reset to original position
    <<<<<[[<]<]>>  go to number that was just marked
    [[-]+>]        replace digits with 0s (cell value 1)
    >[[>]>]<       go back to where we would be without this conditional
  ]
  <[[<]<]<[<]>     return to first unmarked number
]

В [[-]+>]этом разделе была последняя часть, которую я понял. До этого я предполагал, что программа просто делала пробные разделы, но я не мог видеть, где был использован результат.

Этот цикл завершает две ячейки слева от крайнего левого числа и >>>[[>]<->>]]удаляет маркеры, размещенные на ленте, и возвращает нас к концу ленты снова. После этого >[[>]>]<<[[[-]<]<]удаляются либо одинарные часы, либо, если весь этот сегмент был пропущен, оставшиеся 10 с. Цикл устанавливается в исходное состояние с помощью <<<[<]<<].

После этого просто читаем, был ли введенный номер заменен на 1 в любой момент:

>>>[>]<[-[[<]<]++++++++++<]>>                      do the check
[[>]+[------->++<]>.+.+++++.[---->+<]>+++.>>]      conditionally print "not "
>[>]+[------->++<]>++.++.---------.++++.--------.  unconditionally print "prime"

К счастью, фактический вывод не был отредактирован вообще.

Nitrodon
источник
«Ночь длинна, что никогда не находит день». Это все еще сегодня вечером? : P
Стьюи Гриффин
@ StewieGriffin Я не смог сделать это в ту ночь, а потом это просто ускользнуло от меня. Спасибо за напоминание.
Nitrodon
Я не думаю, что мог бы объяснить свой собственный код так же, как вы сделали здесь. Очень хорошая работа.
Джо Кинг,
5

Wolfram Language (Mathematica)

Взламывает этот ответ .

f[x_]:=(p=ToString@Boole@PrimeQ@x;StringMatchQ[p&@@Infinity,RegularExpression@"(\
\n{}\b+, )?1"])

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

user202729
источник
Для чтения кода не требуется прокрутка :)
user202729
Ницца! Совершенно отличается от предполагаемого решения, поэтому я пока не буду раскрывать это.
Павел
@Pavel А как насчет этого ? Или все же "принципиально то же самое"?
user202729
Вот подсказка: это большой двоичный объект не содержит ни Booleне PrimeQ.
Павел
5

Brain-Flak, MegaTom

(({████){██[████)█>(({}))<>}<>{}███{}((██({}))█████{}]██)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})██[██()██(()█[()]██{}██}{}<>{})
(({})<>){([[]]{})<>(({}))<>}<>{}{}{{}(([]({}))[({}[{}])])({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})}([][()])((){[()](<{}>)}{}<>{})

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

Эта программа выполняет пробное деление от n-2 до 1, затем выводит 1 тогда и только тогда, когда это заканчивается с коэффициентом 1.

Nitrodon
источник
4

8086 DOS COM Джошуа

xxd представление, из-за кодировок и нулевых байтов и других страшных вещей:

00000000: 31c0 b90a 0031 dbbe 8100 ac3c 0d74 3c3c  1....1.....<.t<<
00000010: 2075 f7ac 3c0d 7410 2c30 7c2f 3c09 7f2b   u..<.t.,0|/<..+
00000020: 93f7 e193 01c3 ebeb 83fb 027c 19c6 0653  ...........|...S
00000030: 0159 b902 0039 d974 1289 d831 d2f7 f109  .Y...9.t...1....
00000040: d274 0341 ebef c606 5301 4eb4 09ba 5301  .t.A....S.N...S.
00000050: cd21 c341 0d0a 24                        .!.A..$

Сначала разобрали мента вручную, затем собрали с помощью yasm. Некоторые байты были искажены тем, что использовал Джошуа, но я только что обработал их как отредактированные байты. Я на 99,72% уверен в их фактическом содержании. Хотя это не займет много времени, чтобы исправить это, если я ошибаюсь. Наслаждаться:

; A COM file is just a 16-bit flat binary
; loaded at 0x100 in some segment by DOS

org 0x100
bits 16

; Unsurprisingly, we start by converting
; the commandline string to a number. During
; the conversion, SI is a pointer to the
; string, CX is the base, and BX holds the
; partial result
parse_input:
; We'll read the input character by character
; into AL, but we need the resulting digit as
; a 16-bit number. Therefore, initialise AX to
; zero.
    xor ax, ax
    mov cx, 10
    xor bx, bx
; When a DOS program is loaded, it's preceded
; in memory by the Program Segment Prefix,
; which holds the commandline arguments at
; offset 0x81, terminated by a carriage return
    mov si, 0x81

.skip_prog_name:
; Load a character and move the pointer
    lodsb
; If we find the terminator here, the program
; was not given any arguments.
    cmp al, 13
    je finish

    cmp al, ' '
    jne .skip_prog_name

.input_loop:
    lodsb
    cmp al, 13
    je got_input

; If the ASCII value of the character is less
; than the one of '0', error out. Adjust the
; value in AL so that it holds the digit
; itself. This exploits the fact that the
; comparison instruction is just a subtraction
; that throws away the actual result.
    sub al, '0'
    jl finish

; If we have a value larger than 9, this
; character wasn't a digit.
    cmp al, 9
    jg finish

; Multiply the intermediate result by 10 and
; add the new digit to it.

    xchg ax, bx
    mul cx
    xchg ax, bx
    add bx, ax
    jmp .input_loop

got_input:
; The loop below would go haywire when given a
; zero or a one, so make them a special case.
    cmp bx, 2
    jl composite

; Patch the output string to say that it's
; prime
    mov byte[outstr], 'Y'

; BX = number being checked
; CX = loop counter, potential divisor of BX
    mov cx, 2

.loop:
; If CX = BX, we looked everywhere and couldn't
; find a divisor, therefore the number is prime
    cmp cx, bx
    je finish

; DIV takes DX:AX as a 32-bit number for the
; dividend. We don't want nor need the extra
; precision, so we set DX to 0.
    mov ax, bx
    xor dx, dx
    div cx

; DX now contains the remainder. To check if
; it's 0, we perform some noop operation, that
; happens to set the flags appropriately. AND
; and OR are commonly used for this purpose.
; Because of what's presumably a bug in the
; encoder used by Joshua, I do not yet know
; which for certain. However, I can make an
; educated guess. All other instances of the
; bug happened with a codepoint below 32.
; Moreover, no other bytes from that range
; occur in the code. Because an AND would be
; encoded as an exclamation mark, while OR -
; - as a tab, I am highly confident that Joshua
; used an OR.
    or dx, dx
    jz composite

; Increment the counter and loop again!
    inc cx
    jmp .loop

composite:
    mov byte[outstr], 'N'

finish:
    mov ah, 9
    mov dx, outstr
    int 0x21
    ret

outstr:
    db 'A', 13, 10, '$'
NieDzejkob
источник
Единственная разница между моими заключалась в том, bx < 2чтобы закончить, а не составлять К вашему сведению, искажение было связано с тем, что изначально в качестве символа маски использовалось X, а не все исправлялось при переключении на █.
Иисус Навин
@Joshua Сначала я тоже использовал финиш, но потом вспомнил, что требуется корректная обработка 1. О коррупции - это один из сценариев, которые я себе представлял
NieDzejkob
3

Желе

Взламывает этот ответ.

25██26█966836897364918299█0█1█65849159233270█02█837903312854349029387313█ị██v
250126,9668368973649182994001,658491592332700020837903312854349029387313ṖịØJv

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


Объяснение:

Глядя на и vя думаю о создании списка чисел, ndex его в некоторый список и оценивать его.

«Тривиальный» способ проверки первичности в желе ÆP (если он может взломать представление):

  • Список для индексации должен содержать Æ и P.
  • Список индексов должен быть сравним по модулю 256с [14, 81].

Итак ... список в начале программы совпадает с [14, 81, 49]модом 256 ( TIO ) и выскакивает последний элемент.

user202729
источник
3

sh + coreutils

Взламывает этот ответ .

eecs c "██████WyAkKHNoIC1jICJg█WNobyBabUZqZEc5eWZIUnlJQ2█2SnlBblhHNG5m██JoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K█b█se6███d`"
exec sh -c "`echo WyAkKHNoIC1jICJgZWNobyBabUZqZEc5eWZIUnlJQ2M2SnlBblhHNG5mSFJoYVd3Z0t6SjhkMk1nTFhjSyB8YmFzZTY0IC1kYCIpIC1lcSAxIF0K|base64 -d`"

Нет Попробуйте онлайн! на этот раз из-за некоторых проблем . Однако вы можете использовать jdoodle .

Возвращает по коду выхода. 0(успех) для простого, 1(ошибка) для составного.

Фактическая команда выполнена

factor|tr ':' '\n'|tail +2|wc -w

Как взломать

  1. Посмотри код, узнай Base64.
  2. Узнайте, как использовать base64команду.
  3. Знайте, что +это действительный символ base64.
  4. Попробуйте расшифровать .
  5. Примените оболочку sh -c "`echo ...|base64 -d`"к исходной программе .
  6. Генерация вложенных base64 из команд .
user202729
источник
Правильный метод. «Некоторые проблемы», оказывается, не все машины знают о tail +n. Когда я попробовал твой треск на машине на работе, он пожаловался на это. Вы действительно сняли маску с правильного кода ... :(
Джошуа
3

Октава , 86 байт, Стьюи Гриффин .

@(x)eval([(str2num(cell2mat([cellstr(reshape('0█1███1█0█0█00',████))])')'█')','(x)'])
@(x)eval([(str2num(cell2mat([cellstr(reshape('04141113040800',2,[]))])')+'e')','(x)'])

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

Это было весело! Я боролся с этим в течение хорошей пары дней.

Первым признаком было распознавание eval([...,'(x)'])как конструкции, создающей вызов isprimeфункции, как конкатенации intsи charнеявного преобразования массива в char, так что ...необходим либо один из них, isprimeлибо массив, который имеет значения ASCIIisprime ,[105, 115, 112, 114, 105, 109, 101] .

Остальное было просто пролистывать документацию, чтобы выяснить, что reshapeможет принять одно неизвестное измерение [], хотя, полагаю, я мог бы сделатьreshape(...,2, 7) с тем же количеством байтов.

Использование +'e'(101) вместо +'d'(100) было приятным прикосновением, которое тянуло меня еще на несколько минут, пока я не заметил, что последние цифры (необъясненные) были, 00а не 01, и с этим это было легко.

Giuseppe
источник
2

JavaScript

x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=████;--y-1;(p=x/y%1)████if(██&&(███))break████return(███)}
x=>{if(x<4)return(!0);for(y=x>>>Math.log10(p=2-1);--y-1;(p=x/y%1)){;;if(!p&&(1<2))break;;;}return(!!p)}

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

Я почему-то сомневаюсь, что это именно то, что вы имели в виду, но это работает.

MegaTom
источник
2

> <> , Esolanging фрукты

:1@v>~~:?1n;█$-1<█?=2:}*{█@:$@:

в

:1@v>~~:?1n;
$-1</?=2:}*{%@:$@:

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

Умное использование редактирования новой строки немного смутило меня. Кажется, не работает на 1 или 2, хотя.

Джо Кинг
источник
Ницца. Любой из ^, v, /или \ для второй заготовки мог бы работать там. Теперь я хотел бы, чтобы я покрыл *вместо /.
Esolanging Fruit
2

Java (OpenJDK 8) , Волшебная Урна Осьминога

class X{public static void main(String[]args){System.out.println(new String(████████[Integer.parseInt(args[0])]).matches("█████████████")?███);}}
class X{public static void main(String[]args){System.out.println(new String(new char[Integer.parseInt(args[0])]).matches(".?|(..+?)\\1+")?0:1);}}

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

Код взят из RosettaCode и объяснен на SO .

овс
источник
Не знал, что это так популярно, ха! Было это в моем заднем кармане в течение длительного времени. Я честно украл его из служебного файла, который у меня был с тех пор как ... Боже ... 2014?
Волшебная Урна Осьминога
2

Python 3 , 44 байта, osuka_

p=lambda x,i=2:i>=x or(x%i and p(x,i+1))or 0

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

Не работает, когда х <2. or 0Может быть заменен >0{2 spaces}или даже 4 пробела

Для проблемы x <2, так как i>=xдолжен быть помещен впереди (иначе будет бесконечный цикл), и i>=xвозвращает true немедленно, когда x <2, так что я думаю, что это не исправить.

Сиеру Асакото
источник
Как оказалось, мой код тоже не работает с x <2. К сожалению. (Я, вероятно, только что проверил это с диапазоном (2, ...), потому что я глуп)
osuka_
2

М, Дилнан

ÆPø“;;“»VOḣ2S⁵++3Ọ;”Pv

Это, вероятно, не было намеченным решением.

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

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

ÆP это встроенный тест на простоту

øсущества новая, ниладическая цепь. Поскольку предыдущее возвращаемое значение (результат ÆP) выходит из области видимости, это печатает его неявно.

“;;“»оценивает список строк ["< Aalst" ""]и Vпытается их оценить . sпытается разбить свой аргумент на куски длиной 0 , что приводит к сбою интерпретатора M, подавляя дальнейший вывод.

Деннис
источник
Не задуманное решение, но приятно. Скоро обновлю пост на взломанный. Если бы я сказал слово «зоопарк», это привело бы вас к другому возможному решению?
Дилнан
Хм, это звучит как сложная бесконечность.
Деннис
1

Python 3 , пользователь71546

import random
def f(z):
 if z<4:return z>>1
 d,s,n,e,c=~-z,0,z,0,50
 while not d&1:d//=2;s+=1
 while n>0:n//=2;e+=1
 random.seed()
 while c>0:
  a=0
  while a<2or a>z-1:
   a,b=0,e
   while b>0:a=a*2+random.randint(0,1);b-=1
  x,r=pow(a,d,z),~-s
  if ~-x and x!=~-z:
   while r>0:
    x,r=pow(x,2,z),~-r
    if not ~-x:return 0
    elif x==~-z:break
   else:return 0
  c-=1
 else:return 1

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

Nitrodon
источник