12

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

Интересный вопрос для размышления:

Если у меня есть последовательность чисел, сколько из них я должен предоставить, прежде чем станет ясно, о какой последовательности я говорю?

Например, если я хочу поговорить о натуральных числах по порядку, начиная с , я могу сказать , но достаточно ли этого? $1$ $1,2,3, \dots$

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

Вызов

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

Кусок кода, который принимает положительное целое число в качестве входных данных и производит целое число в качестве выходных данных. Этот код может быть либо нулевым, либо индексированным, но должно быть понятно, что такое индексирование. Этот код будет определять вашу последовательность.
Любые соответствующие требования платформы или языка, которые могут повлиять на вывод, например размер longint.
Число вместе с первыми членами последовательности, рассчитанной по коду. Они будут действовать как «контрольные примеры». $n$ $n$

Грабители будут находить программу на том же языке, которая короче представленной и проходит все тестовые случаи (выдает тот же вывод для первых входов, что и код полицейского). Код грабителя должен также отличаться в выходных данных от программы полицейского для некоторого числа, большего чем . $n$ $n$

счет

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

sequence cops-and-robbers Специальный охотник за гарфами
источник

2

Разве мы не позволяем грабителям избивать друг друга за то, что они

взломали

@ fəˈnɛtɪk Звучит, хорошо, что я добавил это.

Специальный охотник за

6

cQuents , ответ Стивена , 3 байта

z~$

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

Как это устроено

z     Last item in the sequence
 ~    Concat
  $   Current index

Похоже , последовательности должны быть одинаковыми, но это дает 12345678910для в n = 10то время как "::$дает 1234567891.

фонтанчик для питья
источник

5

JavaScript, ответ fəˈnɛtɪk (17 байт)

x=>"11237"[x]||22

$x\ge 6$ undefined||22

тестирование

let f=x=>"11237"[x]||22

for (x of [1,2,3,4,5,6,7]) {
  console.log(x + ' -> ' + f(x))
}

Развернуть фрагмент

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

Мистер Xcoder
источник

4

Хаскель , ответ Лайкони , 15 байт

b n=n*div(n+1)2

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

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

Это всего лишь ответ BMO за исключением особого случая b 42. Поскольку оригинал Лайкони проходит через число с плавающей запятой, в этом нет необходимости: просто найдите число, достаточно большое, чтобы в нем были ошибки округления, но не в точной Integerарифметике. Например:

a 100000000000000000000000 = 4999999999999999580569600000000000000000000000
b 100000000000000000000000 = 5000000000000000000000000000000000000000000000

Орджан Йохансен
источник

Я подумал, что это возможно (поэтому я написал, что это можно переписать для требуемых терминов), но не нашел значения, для которого это работает .. Отлично сделано!

მოიმო

4

Python 2 , ответ xnor , 43 байта

$n = 69$

f=lambda n,p=2:n<1or-~f(n-(~-2**p%p<2),p+1)

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

кредиты

Большая заслуга этого взлома должна достаться @ Mr.Xcoder, который первым опубликовал комментарий о возможной атаке с использованием этого метода, и @PoonLevi, который нашел 44-байтовое решение.

Как?

теория

$p$ $a$ $p$

\begin{matrix} (1) & a^{p - 1} \equiv 1 (\mod p) \end{matrix}

$a^{p-1}\equiv 1 \pmod p\tag{1}$

$a=2$

2^{p - 1} \equiv 1 (\mod p)

$2^{p-1}\equiv 1 \pmod p$

$k$

2^{p - 1} = k p + 1

$2^{p-1}=kp+1$

Что приводит к:

2^{p} = 2 k p + 2

$2^p=2kp+2$

2^{p} - 1 = 2 k p + 1

$2^p-1=2kp+1$

\begin{matrix} (2) & 2^{p} - 1 \equiv 1 (\mod p) \end{matrix}

$2^p-1\equiv 1 \pmod p\tag{2}$

$p=2$ $2$

$a^{n-1}\equiv 1 \pmod n$ $n$ $a$

$2$ $n = 341=11\times 31$

2^{341 - 1} \equiv 1 (\mod 341)

$2^{341-1}\equiv 1 \pmod{341}$

2^{341} - 1 \equiv 1 (\mod 341)

$2^{341}-1\equiv 1 \pmod{341}$

$341$ $347$

Реализация

$(2)$

f=lambda n,p=1:n and-~f(n-(~-2**p%p==1),p+1)

<2==1 $1$ $2^1-1\equiv 0 \pmod 1$

f=lambda n,p=1:n and-~f(n-(~-2**p%p<2),p+1)

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

$p=2$

f=lambda n,p=2:n and-~f(n-(~-2**p%p<2),p+1)

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

Последний трюк должен использовать n<1orвместо n and. Это так же долго, но последняя итерация возвращает True вместо 0 , что добавляет недостающее смещение к каждому члену.

Arnauld
источник

Поздравляю всех вас! Это решение, которое я имел в виду. Я думаю, это забавно, что из мотивации вызова «Если у меня есть последовательность чисел, сколько из них я должен предоставить, прежде чем станет ясно, о какой последовательности я говорю?», Первых 50 простых чисел явно недостаточно - иностранец, играющий в гольф на питоне, предположил бы, что вы говорите о другой последовательности.

xnor

@xnor Мне нравится идея «инопланетянина,

играющего в питон

3

Python 3 , crashoz , 45 байт

lambda n:int(60*math.sin(n/10-2))
import math

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

x*60-x**3*10+x**5/2-x**7/84 $sin(x)$ $x^7$

XNOR
источник

3

JavaScript (ES6), ответ Арно (10 байт)

n=>8*n*n|n

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

СПП
источник

2

Хаскель , ответ Лайкони , 26 22 байта

_{-4 байта, не используя инфикс div, благодаря Laikoni !}

b 42=0;b n=n*div(n+1)2

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

объяснение

$0 \leq n \leq 20$ ceiling(realToFrac n/2)div(n+1)2 $n > 20$

b 42=0

ბიმო
источник

Ах, я не думал об этом. У меня другой подход, который приводит к трещине в 20 байт на случай, если вы захотите немного больше разгадать. Также ((n+1)`div`2)-> div(n+1)2.

Лайкони

@Laikoni: Да, пока не раскрывай! Упс, да, прошло довольно много времени с тех пор, как я немного поиграл в гольф, я обновлю его.

მოიმო

2

> <> , ответ крашоза 203 байта

:l2-$g:0=?;n:





M
-
B
"
BM
",
7M
!"
BBM
!",
7CM
!"-
BBBM
!!",
7BBMM
!!,,
7BBBMM
!!,,
7BBBMM
!!!,,
7BBBBMM
!!!,,
7BBBBMM
!!!!,,
7BBBBBMM
!!!!,,
7BBBBBMM
!!!!!,,
7BBBBBBMM

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

Я собирался сделать что-то умное с тем фактом, что нечетные / четные числа выше n=20были одинаковыми, за исключением повторяющегося элемента в центре, но было проще просто жестко кодировать каждый элемент.

Ввод осуществляется через -vфлаг. Ничего не печатает для элементов выше 34.

Джо Кинг
источник

2

Паскаль (FPC) , ответ AlexRacer , 80 байт

var n,m:word;begin read(n);while n<>0 do begin n:=n div 2;m:=m+n;end;write(m)end.

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

$0\le n\le 120$ $n=128$ $127$ $126$

Это кажется запоздалым ответом, но в любом случае спасибо @AlexRacer за хорошую головоломку!

r_64
источник

1

Вау, это даже короче, чем у меня было. Добро пожаловать в PPCG!

AlexRacer

1

JavaScript, ответ fəˈnɛtɪk (12 байт)

$x=6$

x=>2.72**x|0

тестирование

g=
x=>2.72**x|0

tmp=[0,1,2,3,4]
console.log(tmp.map(g).join(','))

Развернуть фрагмент

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

Мистер Xcoder
источник

1

JavaScript, ответ fəˈnɛtɪk (17 байт)

$15$

x=>2.7182819**x|1

$n\le 14$ $15$ x=>Math.exp(x)|1

тестирование

f=x=>2.7182819**x|1
g=x=>(3-(5/63)**.5)**x|1

tmp=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
console.log(tmp.map(f).join(","))
console.log(tmp.map(g).join(","))

Развернуть фрагмент

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

Мистер Xcoder
источник

1

Шелуха , взламывая 5 байтов BMO с 3 2 байтами

-1 благодаря BMO ( LdΣ->, LΣтак как, когда дано Tnum, Lвыполняет "длину представления строки")

LΣ

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

$a(0)\cdots a(23)$ $a(24)$
LΣ $3$ ←d+16 $4$

_{$T(0)=0$ $1$ $0$}

Джонатан Аллан
источник

Поздравляю, это было мое точное решение! Однако я только что заметил, что для TNum s Lи Ld эквивалентно сэкономить вам байт;)

ბიმო

Ах, я искал "цифру" в вики, чтобы попытаться найти цифровую длину, но не обнаружил, что она Lпереопределяется как "длина представления строки" Tnum.

Джонатан Аллан

(Обратите внимание, что они эквивалентны только для неотрицательных целых чисел - достаточно для этого.)

Джонатан Аллан

1

> <> , Ответ Эйдена Ф. Пирса , 36 байт

v101786
i5844
419902
%
>l{:}g:0=?;o:

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

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

Джо Кинг
источник

0

JavaScript, ответ fəˈnɛtɪk , 23 байта

$0$ $n\ge 14$ .

x=>14-`${73211e9}`[x]|0

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

Как?

Выражение `${73211e9}`расширяется до строки"73211000000000" , предоставляя таблицу поиска из 14 значений, которые вычитаются из 14, что дает ожидаемую последовательность.

$n\ge 14$

(14 - undefined) | 0
=== NaN | 0
=== 0

21 байт

NaN $n\ge 14$

x=>14-`${73211e9}`[x]

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

Arnauld
источник

Жесткое кодирование копов и грабителей (грабителей)

Вызов

счет

Ответы:

cQuents , ответ Стивена , 3 байта

Как это устроено

JavaScript, ответ fəˈnɛtɪk (17 байт)

тестирование

Хаскель , ответ Лайкони , 15 байт

Python 2 , ответ xnor , 43 байта

кредиты

Как?

теория

Реализация

Python 3 , crashoz , 45 байт

JavaScript (ES6), ответ Арно (10 байт)

Хаскель , ответ Лайкони , 26 22 байта

объяснение

> <> , ответ крашоза 203 байта

Паскаль (FPC) , ответ AlexRacer , 80 байт

JavaScript, ответ fəˈnɛtɪk (12 байт)

тестирование

JavaScript, ответ fəˈnɛtɪk (17 байт)

тестирование

Шелуха , взламывая 5 байтов BMO с 3 2 байтами

> <> , Ответ Эйдена Ф. Пирса , 36 байт

JavaScript, ответ fəˈnɛtɪk , 23 байта

Как?

21 байт