Грабители: скрытая подстрока OEIS

23

Это вызов копов и грабителей. Это нить грабителя. В нитка полицейского здесь .

Полицейские выберут любую последовательность из OEIS и напишут программу p, которая напечатает первое целое число из этой последовательности. Они также найдут некоторую строку s . Если вы вставляете s где-то в p , эта программа должна вывести второе целое число из последовательности. Если вы вставите s + s в то же место в p , эта программа должна вывести третье целое число из последовательности. s + s + s в том же месте напечатает четвертый, и так далее, и так далее. Вот пример:

Python 3, последовательность A000027

print(1)

Скрытая строка составляет два байта .

Строка +1, потому что программа print(1+1)напечатает второе целое число в A000027, программа print(1+1+1)напечатает третье целое число и т. Д.

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

Если вы взломаете один из ответов полицейских, опубликуйте свое решение (с указанием скрытой строки и местоположения) и ссылку на ответ. Затем прокомментируйте ответ полицейских со ссылкой на ваш взлом здесь.

правила

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

  • Победивший грабитель - это пользователь, который взламывает большинство представлений, причем тай-брейк первым достигает этого количества взломов.

  • Победивший коп - это коп с самой короткой строкой s, который не взломан. Tiebreaker - самый короткий р . Если нет непроверенных представлений, полицейский, у которого было решение, не взломанное для самых длинных побед.

  • Для того чтобы ваше решение было объявлено безопасным, ваше решение должно оставаться открытым в течение 1 недели, а затем раскрываться скрытая строка (и место для ее вставки).

  • s не может быть вложенным, оно должно соединяться сквозным образом. Например, если бы s было 10, каждая итерация шла бы, 10, 1010, 101010, 10101010...а не10, 1100, 111000, 11110000...

  • Все криптографические решения (например, проверка хеша подстроки) запрещены.

  • Если s содержит символы не ASCII, вы также должны указать используемую кодировку.

DJMcMayhem
источник

Ответы:

13

Python 2 , последовательность A138147 от xnor

Оригинал:

print 10

Трещины:

print "1%s0"%10
      ^^^^^^^

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

Hobbs
источник
3
Ты получил это! Это решение, о котором я думал. Мне интересно, что это работает, учитывая, что %левые партнеры.
кнор
Да, но строка формата - это строка, и «1% s0»% «1% s0» - это «11% s00», что все еще делает то, что мы хотели, чтобы произошло.
Хоббс
10

Головоломка , A000984 от Nitrodon

({({}<>({}))<>}<>){({}<>)<>}<>

Это всего лишь 30 байтов, не совсем понятно, что имел в виду Нитродон.

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

объяснение

Я много чего перепробовал, но вот что сработало. Термины A000984 являются центральными элементами треугольника Паскаля.

Central elements

Теперь я понял, что могу получить их, сложив диагонали над ними:

Например:

1+3+6+10=20

Central sums

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

Итак, мы хотим программу, которая берет одну частичную сумму и производит следующую. К счастью, есть довольно аккуратный способ перехода от одного к другому. Каждый ряд - это дельты следующего ряда. То есть n й член в ряду - это разница между n м и n1 м членами в следующей строке.

Next row formula

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

1+3+6=10

Last member formula

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

Теперь для кода:

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

{({}<>({}))<>}<>

Который в основном перемещает элемент и добавляет (без удаления) то, что когда-либо было сверху. Однако это полностью меняет ситуацию, поэтому в следующий раз, когда мы получим строку, нам нужно ее вернуть.

{({}<>({}))<>}<>{({}<>)<>}<>

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

({({}<>({}))<>}<>){({}<>)<>}<>

Вот и все.

Мастер пшеницы
источник
1
Даже лучше того, что я имел в виду. Одна поправка к вашему объяснению: чтобы перейти от одной диагонали к другой, вы добавляете старое число к новому номеру (вычисляя кумулятивные суммы старой диагонали), а не добавляете два старых числа.
Нитродон
Объяснение @Nitrodon исправлено. Если бы я прочитал свой собственный код, я бы увидел, что это неправильно.
Пшеничный волшебник
6

Brain-Flak, A000290 , автор Sriotchilism O'Zaic

Оригинал:

((()))({}<>)

Трещины:

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

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

В качестве альтернативы:

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

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

jimmy23013
источник
Это моя скрытая строка! но это не то место, где я его размещал. Отличная работа!
Пшеничный волшебник
1
@ SriotchilismO'Zaic Тогда это должен быть оригинал.
jimmy23013
6

MATL , последовательность A005206 от Luis Mendo

Оригинал:

voOdoO

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

Трещины:

voOdoOdNq17L/k
      ^^^^^^^^

Я не эксперт по MATL, но насколько я понимаю, оригинал voOdoOсоздает два пустых массива и массив [0]в стеке. это [0]то, что печатается без скобок как первый элемент последовательности. Трещина / решение тогда делает следующее:

  • dудаляет элементы из стека и (при условии, что это число или массив размером 1) превращает их в пустой массив. Эти пустые массивы не печатаются, но влияют на размер стека
  • Nqсчитает размер стека и вычитает один. Это n+1термин при оценке функции (поскольку она начинается с 2 и увеличивается на одну каждую итерацию из-за dдобавления невидимых вещей в стек)
  • 17L это константа Phi = (1+sqrt(5))/2
  • /kэто выполняет, floor((n+1)/Phi)что является одной из формул, которая вычисляет элементы последовательности. Эта формула указана в OEIS, a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2за исключением того, что мы используем идентификационные данные(sqrt(5)-1)/2 = 1/Phi
SamYonnou
источник
Я не эксперт по MATL. Ну, я думаю, что вы стали одним из них :) Для справки, моя скрытая строка была \N17L/k&(обратите внимание на два различных использования &в середине и в конце кода), но ваше решение проще и более элегантно
Луис Мендо
5

Python 3 - A__

print(100+-1)

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

100 бутылок пива, добавьте, -1чтобы получить следующий номер, 99и т. Д.

Giuseppe
источник
Ударь меня на 7 секунд. :) Кроме того, в правилах сказано, что можно найти любую строку до этой длины, чтобы вы могли просто сделать это -1. Я сделаю это более явным.
DJMcMayhem
@DJMcMayhem Я прочитал это после того, как отправил, но более забавно установить дополнительные ограничения для такого простого взлома :-)
Джузеппе
5

Кег , последовательность A000045 , по A__

Оригинал:

0.

Трещины:

01":&+.
 ^^^^^

Обратите внимание, что проблема заключалась в поиске подстроки длиной <= 6, но найденная строка имеет длину 5.

Определение команд для тех, кому лень искать спецификацию бочонка: 0и 1поместить соответствующий номер в стек; "перемещает вершину стека к основанию стека (крен); &вставляет вершину стека в регистр, если он пуст, в противном случае регистр очищается в стеке; +добавляет два верхних значения стека.

Первоначальный 1"просто вставляет 1 в нижней части стека. Этот растущий список единиц играет роль только в первой итерации, где он позволяет нам предполагать, что стек начинается 1 0не просто, а просто 0. Действительно, программа 10:&+., где:&+ которой повторяется часть, ведет себя точно так же, как и решение, описанное выше, за исключением того, что у нее нет растущего списка единиц внизу.

Поскольку &в повторяющейся части используется только один раз и имеет переменное поведение, поведение 1":&+зависит от четности итерации.

Теперь эта программа на самом деле не печатает последовательность последовательности Фибоначчи, начиная с 0, 1 с начала; фактически она печатает последовательность Фибоначчи 1, 0 со второго места, то есть с 0. (Это приводит к той же последовательности.) Зная это, программа легко анализируется:

  • На первой, третьей, ... итерации, состояние начинается как [a, b]и заканчивается какa+b (&=b) .
  • Во второй, четвертой, ... итерации, состояние начинается как [b] (&=a)и заканчивается как [b, b+a].

Это действительно вычисляет последовательность как требуется.

tomsmeding
источник
1
Хорошо, теперь есть кто-то, кто использует Кег, как я.
@A__ Какой была ваша оригинальная 6-символьная строка? :)
Томсминг
На самом деле это очень похоже на вашу строку; единственное отличие состоит в том, что я добавил :команду в начале строки.
Это самая короткая возможная вставленная строка, которую вы можете найти?
2
Argh. Я нашел это, но назад, когда проблема была <= 4 байта.
Хулдрасет на'Барья
4

Пирет , последовательность А083420 , автор М.Лаврентьев

fold({(b,e):(2 * b) + 1},1,[list: 0,0,])
                                  ^^^^

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

Предоставленная функция игнорирует свой второй аргумент. Он удваивает свой первый и добавляет один, что сгенерирует необходимую 2^n - 1последовательность, необходимую здесь - все, что мне нужно сделать, это сказать, сколько раз выполнить эту операцию, изменяя длину сложенного списка. К счастью, Пирет не жалуется на эту запятую.

Хулдрасет на'Барья
источник
4

Python 3 , последовательность A268575 по NieDzejkob

Оригинал:

from itertools import product
S,F,D=lambda*x:tuple(map(sum,zip(*x))),lambda f,s:(v for x in s for v in f(x)),lambda s:{(c-48>>4,c&15)for c in map(ord,s)}
W=D("6@AQUVW")
print(len(W))

Трещины (100 байт):

from itertools import product
S,F,D=lambda*x:tuple(map(sum,zip(*x))),lambda f,s:(v for x in s for v in f(x)),lambda s:{(c-48>>4,c&15)for c in map(ord,s)}
W=D("6@AQUVW");A=-1,1,0;*X,=F(lambda a:(S(a,x)for x in product(A,A)),W);W={p for p in X if 2<X.count(p)<4+({p}<W)}
print(len(W))

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

Исходя из того, что я могу понять, исходный код устанавливает определения, чтобы сделать скрытую строку как можно более сокращенной, а затем определяет исходный шаблон игры жизни. Затем скрытая строка эквивалентна написанию итерации «Игры жизни» Конвея в 102 байта.

Для целей этого взлома Sэто функция, которая суммирует элементы в своих аргументах (которые являются итерируемыми) и Fприменяет функцию, возвращающую итерируемое значение для каждого элемента списка, и объединяет все результаты вместе.

  • ;A=-1,1,0;заканчивает предыдущее выражение и сокращает кортеж (-1,1,0) с помощью A, который используется для определения product(A,A)всех соседей относительно данной ячейки, а также самой ячейки.
  • *X,=F(lambda a:(S(a,x)for x in product(A,A)),W);создает новый список, Xсодержащий все соседние ячейки Wи сами ячейки W, добавляя относительные позиции соседей к каждой ячейке и объединяя их в список.
  • W={p for p in X if 2<X.count(p)<4+({p}<W)}просматривает этот список Xи определяет, принадлежит ли каждая ячейка Xв наборе ячеек на следующей итерации. Это было взято почти дословно из этого Game of Life golf .
Liresol
источник
Я был настолько поражен ответом NieDzejkob (скрытая строка 102 байта!), Что присоединился к StackExchange, чтобы попытаться взломать его, но оказалось, что моя новая учетная запись не может комментировать посты других людей, поэтому я не могу полностью соблюдать правила ( в этом моя вина)
Liresol
Добро пожаловать в CGCC! Я прокомментировал ответ полицейского для вас. Я надеюсь, что вы остаетесь вокруг!
Джо Кинг
Благодарность! Я на самом деле не пробовал подобные вызовы кода, но делать это было просто здорово.
Liresol
Good job! I'll reveal my intended string when I find the time.
NieDzejkob
3

Haskell, A014675 by Khuldraeseth na'Barya

Original code

main=print$uncurry(!!)([2],0)

With substring

main=print$uncurry(!!)                                   ([2],0)
                      $(\(a,n)->(a>>= \e->2:[1|e>1],n+1))

Try it online!

nimi
источник
That would do it! I had flip take[1,2] instead of that inner lambda. Otherwise identical.
Khuldraeseth na'Barya
1
@Khuldraesethna'Barya: (`take`[2,1]) is even one byte shorter
nimi
That stings. Perhaps coulda had this one safe for a touch longer had I realized that. (`take`) met a compilation error, so I figured (`take`[2,1]) would as well. :(
Khuldraeseth na'Barya
2

Desktop Calculator, A006125, by A__

Original:

1n

Cracked:

1 2lx1+dsx^*n
 ^^^^^^^^^^^

Try it online!

Straightforward implementation.

jimmy23013
источник
My original string is Sa2Lad1-*2/^, in case anyone asks me about it.
A̲̲
2

cQuents, sequence A003617 by Stephen

=10#2:pZ
  ^

Try it online!

Begin with the lowest n+1-digit number, a one followed by n zeroes. The #2 specifies that only the second term of the sequence, which is the sequence definition applied once to the seed, will be printed; this sequence definition simply finds and returns the next prime.

Khuldraeseth na'Barya
источник
2

Python 3 -- agtoever

from sympy import isprime, primerange
from itertools import count
r=1
r+=1
while isprime(r-2)or r&1<1and r>3:r+=1
print(r)

Try it online!

NieDzejkob
источник
2
The reason I asked about the Goldbach conjecture is that a solution like this this isn't correct if there is an even entry in the series besides 2. I think this works if you can't assume the conjecture, but it uses the same basic idea (feel free to leave this as the crack, I just want to be pedantic).
FryAmTheEggman
Nice solution. Shorter than mine. I'll post mine tomorrow (CET). I don't have my code at hand right now. My solution uses a generator expression and doesn't rely on the Gb conjecture, but that still leaves this as a well golfed (and in my opinion qualifying) answer.
agtoever
1
@FryAmTheEggman Yeah, the "formula" section of OEIS didn't mention that it depends on a conjecture... brb with a proof ;)
NieDzejkob
2

MATL, sequence A000796 by Luis Mendo

Original:

'pi'td1_&:_1)Y$J)

Try it online!

Cracked:

'pi'td1_&:|SQ_1)Y$J)
          ^^^

The original author sneakily created the array [-7:-1] and then extracted and negated the first element of it to get 7. He then used that to get the rounded 7'th digit of pi (which is 3) and presented it as the first digit of pi. Adding in |SQ makes the original array all positive, sorts it, and adds one to everything. This means that after everything instead of getting the index 7 it gets the index -2 after one application, -3 after two applications, and so on. The - is important because it tells the Y$ function to not round the digits.

SamYonnou
источник
My exact hidden string! Well done!
Luis Mendo
2

Forth (gforth), A000042, by NieDzejkob

.( 1)1 .
^^^^^

Try it online!

The trivial 1-byter is simply extending the literal. Problem is, that overflows 64 bits as early as the ninteenth digit. Easy fix is to print the single digit repeatedly, right? Yep, but it's not quite that easy. Though tacking 1 . onto the end will indeed print the additional digits we require, they'll be separated by spaces. That ain't gonna work.

Now, according to Wikipedia, ".( (dot-paren) is an immediate word that parses a parenthesis-delimited string and displays it." Fortunately, that displaying has no other weird characters, so using .( to print a single 1 should suffice. And it does. No space is needed after the close-paren, so these five characters (there's a space after the open-paren) can be repeated to our hearts' content. To demonstrate, I've included in TIO an example that would have overflowed a 64-bit int several times over. Works like a charm.

Khuldraeseth na'Barya
источник
Good job! That's exactly my string.
NieDzejkob
2

Unefunge-98 (PyFunge), sequence A000108, by NieDzejkob

1# 2g1+:2p4*6-*2g/.@
 ^^^^^^^^^^^^^^^^^

Try it online!

Repeated six times

Two bytes to spare of the nineteen allowed! What appears to be a space there is actually a 0x01 Start Of Header character.

Explanation:

This challenge is all about generating a(n) from a(n-1) and perhaps n. OEIS provides the explicit formula a(n) = (2n)!/(n!(n+1)!), which is easily enough converted to a(n) = a(n-1) * (4n-6) / n. Now to implement this in Funge.

I must be inserting code between the 1 and the .. That's half the puzzle done already. All that remains is what code to insert? Funge is notably lacking in stack manipulation tools, so the bottom of the stack is off-limits; I need to track both n and a(n) without growing the stack. And how better to do that than with Funge space?

That 0x01 character is my counter n. I keep a(n) on the stack, as it must be on the stack after my bit finishes executing.

1# 2g1+:2p4*6-*2g/.@
1                       Push 1. This is a(0).
 #                        Skip the next instruction. Without this, I believe the instruction pointer will reverse direction upon encountering 0x01.
   2g                     Push the third character in the source, which starts out as 1.
     1+                   Increment it...
       :                  ...copy it...
        2p                ...and put it back. One copy remains atop the stack.
          4*6-            Multiply by four. Subtract six.
              *           Multiply by a(n), leaving the result alone on the stack.
               2g         Push n again...
                 /        ...and divide our intermediate result by it. Ta-da!
                          At this point, the stack is the same as at the start of the indented block, except the one item has been advanced one place in the sequence.
                          The source of the program has changed; the third character holds the number of times this indented block has run.
                  .@    Print and terminate.
Khuldraeseth na'Barya
источник
2

V, A000290, by DJMcMayhem

é*Ä2é*Ø.
  ^^^^

yields the squares from 1.

Try it online!

The base é* inserts * and Ø. counts the number of non-newline characters in the entire buffer. The insertion Ä duplicates the top line to its own line, on which 2é* inserts **. Concatenations of the insertions yield successive odd numbers with the largest at the top. The final Ø. in effect sums the first n odd numbers, hence yielding the n-th square .

Kritixi Lithos
источник
Ahh, summing odd numbers, I didn't think about that. Nicely done :) I took the phrase square numbers much more literally with ÄÎé*<CR>
DJMcMayhem
@DJMcMayhem I thought similarly at first, but messed something up/got 6 bytes, so tried this other approach inspired by the brainflak wiki's square number construction via summing odd numbers.
Kritixi Lithos
2

AsciiDots, sequence A019523 by Alion

\+++/
//\/\

Once!

Twice!

Ten times!

While trying to figure out how the code/language works, I learned that the first two lines of the existing code does all the work of outputting the Fibonacci sequence infinitely. The code terminates when any dot hits the &, so I merely needed to add further delay in the remaining lines to allow for the appropriate number of entries to output.

After some trial, error, and observation, I discovered that the correct delay interval is 16 time units per number. Fitting enough characters in a single row seemed infeasible, so I would need to put the delay in 2 rows, leaving 10 characters for the actual delay. In order for the pattern to match up with itself, both rows had to have 5 characters, and since the middle three characters in a row can be traversed twice, this gives 16 time units as desired.

The requirement to match this up to the & in the eighth column seemed to make this impossible, until I realized that I could start with a newline in the interior of the third row. This makes the penultimate row the right length, and removes the now-redundant end of the third line.

Nitrodon
источник
1
The following also works: \v / v>-----)
SamYonnou
Great job, you two. @SamYonnou was closer to the intended solution. Additionally, I'm glad that the thought process was similar to the intended one, despite leading towards a different solution!
Alion
2

Brachylog, sequence A114018 by Unrelated String

Original program:

≜ṗ↔ṗb&w

String to insert:

≜ṗ↔ṗẹbb&w
    ^^

Try it online!

Explanation

Here is first the explanation of the original program (knowing that the sequence used is "least n-digit prime whose digit reversal is also prime")

≜         Assign an integer value to a variable named ? 
            (try 0, then 1, then -1, then 2, etc.)
 ṗ        ? must be prime
  ↔ṗ      The reverse of ? must be prime
    b     Remove the first element of ?
     &    Ignore that we removed that element
      w   Write ? to STDOUT

As you can see, the program is fairly straightforward except for one thing: there is a completely useless b - behead predicate call, that removes the first element of the reverse of our number, with which we don't do anything.

This is a definite clue as to how we can find the string. The idea is that, since we want to increase the length of the number by 1 digit each time we add the string, we need a string that "evaluates" the length of that number somehow, using that useless b.

The solution is to use ẹb: first, ẹ - elements will transform the number into a list of digits; then, b - behead will remove its first element. The trick is that b will fail if the list of digits is empty. So everytime we append a b, we will increase the length of the required number by 1 (because it will fail until the assigned value of ? is high enough to contain sufficiently many digits so that the last b is applied on a list of one digit).

Re-appyling each time has no effect because it's already a list of digits. We only need it once at the beginning because if we behead a number like 9001 instead of the list of its digits, we will get 001 = 1 which loses information about the number of digits.

Fatalize
источник
1
Very nicely done. I never even thought of the 9001b1 issue, it actually just turned out that although b will fail if the list of digits is empty, it won't fail if you never actually have a list, because single-digit numbers behead to 0, including 0 itself.
Unrelated String
1
@UnrelatedString In short: b is weird
Fatalize
2

VDM-SL, A000312, by Expired Data

let m={1|->{0}}in hd reverse[let x=x+1 in x**x|x in set m(1)&x<card m(1)]
                             ^^^^^^^^^^^^^

Since VDM-SL's let-expressions can re-bind variables which are already bound in an enclosing scope, x**x can be evaluated arbitrarily deeply nested in scopes in which x is one more than in the previous scope, while the original x is still less than the cardinality of m(1).

Unrelated String
источник
I tested it up to n=11 and it worked fine
Unrelated String
...it's only supposed to be one number. If you insert s somewhere into p, this program must print the second integer from the sequence. If you insert s + s into the same location in p, this program must print the third integer from the sequence. Note the behavior of the example print(1).
Unrelated String
Ah rip, understandable
Unrelated String
1
Don't think this is super trivial, it's still pretty cool!
Expired Data
1
Use ++ to map override
Expired Data
2

Haskell, A000045 (Fibonacci), by Rin's Fourier transform

f = head $(flip(:)<*>sum.take 2)[0, 1]
         ^^^^^^^^^^^^^^^^^^^^^^^

Try it online!

23 bytes exactly.

This one was fun and a bit tricky. The reversed 0 and 1 threw me off for a little bit before I realized that wasn't an issue. The lack of $ in the original had me trying sketchy stuff like $...$id (one byte too long) before it dawned on me that I could just wrap it all in parentheses. All in all, a nice little puzzle.

H.PWiz points out that pattern matching could have saved me at least five bytes: $(\[x,y]->[y,x+y]). That darn pointfree challenge has me thinking pointfree everywhere.

Khuldraeseth na'Barya
источник