12

C'est un défi de flics et de voleurs . Le fil des flics à ce défi est ici

Une question intéressante à considérer est la suivante:

Si j'ai une séquence de nombres, combien dois-je fournir avant de savoir de quelle séquence je parle?

Par exemple, si je veux parler des entiers positifs dans l'ordre à partir de $1$ , je pourrais dire $1,2,3, \dots$ , mais est-ce vraiment suffisant?

J'ai une façon de répondre à cette question, et d'être un golfeur de code Cela implique le golf de code. Vous avez fourni suffisamment de termes d'une séquence si le code le plus court qui produit ces termes produit tous les termes de la séquence. Si nous pensons à cela en termes de code-golf, cela signifierait que vous avez fourni suffisamment de cas de test pour que le code le plus court qui réussit les cas de test fasse la tâche souhaitée.

Défi

Ce défi est un défi de flics et de voleurs . Dans lequel les flics présenteront des cas de test et les voleurs devront trouver un moyen plus court d'usurper les cas de test autres que la séquence prévue. Les flics présenteront les choses suivantes:

Un morceau de code qui prend un entier positif en entrée et produit un entier en sortie. Ce code peut être zéro ou un indexé, mais il doit être clair ce qu'est l'indexation. Ce code définira votre séquence.
Toute exigence de plate-forme ou de langue pertinente pouvant affecter la sortie, par exemple la taille de l'entier long.
Un nombre , ainsi que les premiers termes de la séquence tels que calculés par le code. Ceux-ci serviront de "cas de test". $n$ $n$

Les voleurs trouveront un programme dans le même langage qui est plus court que celui présenté et réussit tous les cas de test (produit la même sortie pour les premières entrées que le code du flic). Le code du voleur doit également différer en sortie du programme du flic pour un nombre supérieur à . $n$ $n$

Notation

Les voleurs seront notés dans le nombre de fissures qu'ils trouvent, plus il y a de fissures, mieux c'est. Une réponse peut être craquée à nouveau en trouvant une réponse valide plus courte que la fissure d'origine. Si une réponse est crackée une deuxième fois, le point est donné au deuxième cracker plutôt qu'au premier.

sequence cops-and-robbers Ad Hoc Garf Hunter
la source

2

Ne laissons-nous pas les voleurs se battre pour avoir trouvé une réponse (c'est-à-dire le plus court crack dans la langue gagnante)

fəˈnɛtɪk

@ Sons fəˈnɛt Soundk, bon j'ai ajouté ça.

Ad Hoc Garf Hunter

6

cQuents , réponse de Stephen , 3 octets

z~$

Essayez-le en ligne!

Comment ça fonctionne

z     Last item in the sequence
 ~    Concat
  $   Current index

On dirait que les séquences doivent être identiques, mais cela donne 12345678910pour n = 10tout "::$donne 1234567891.

Bubbler
la source

5

JavaScript, la réponse de fəˈnɛtɪk (17 octets)

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

Eh bien, il était facile de coder en dur pour obtenir un score beaucoup plus faible ... Diffère de l'implémentation de référence pour toute entrée , indexée 0. Cela utilise une astuce de golf JS très connue: l'indexation dans une séquence avec un entier qui dépasse les limites de celle-ci renvoie une valeur fausse ( ), donc elle peut simplement être contrainte à une valeur par défaut en utilisant OU logique ( ), dans ce cas , gestion du dernier terme de la séquence mais aussi de ceux à suivre. $x\ge 6$ undefined||22

Essai

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

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

Développer l'extrait

Alternativement, essayez-le en ligne!

M. Xcoder
la source

4

Haskell , réponse de Laikoni , 15 octets

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

Essayez-le en ligne!

Je pointerais habituellement quelque chose comme ça dans un commentaire, mais ensuite je pensais que les flics et les voleurs étaient un peu plus acharnés.

Ceci est juste la réponse de BMO moins le cas spécial pour b 42. Parce que l'original de Laikoni passe par une virgule flottante, ce n'est pas nécessaire: il suffit de trouver un nombre suffisamment grand pour donner des erreurs d'arrondi, mais pas dans l' Integerarithmétique exacte . Par exemple:

a 100000000000000000000000 = 4999999999999999580569600000000000000000000000
b 100000000000000000000000 = 5000000000000000000000000000000000000000000000

Ørjan Johansen
la source

J'ai pensé que cela pourrait être possible (c'est pourquoi j'ai écrit qu'il peut être réécrit pour les termes requis), mais je n'ai pas trouvé de valeur pour laquelle cela fonctionne .. Bien joué!

2018

4

Python 2 , réponse de xnor , 43 octets

$n = 69$

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

Essayez-le en ligne!

Crédits

Une grande partie du mérite de cette fissure doit aller à @ Mr.Xcoder qui a d'abord publié un commentaire sur une éventuelle attaque utilisant cette méthode, et à @PoonLevi qui a trouvé une solution de 44 octets.

Comment?

Théorie

$p$ $a$ $p$

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

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

En particulier, pour : $a=2$

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

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

Il existe donc un entier positif tel que: $k$

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

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

Qui conduit à:

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}$

Cette dernière formule est celle dont le code Python est dérivé et vaut maintenant pour , même si n'est pas relativement premier avec lui-même. $p=2$ $2$

Maintenant, pour la partie la plus importante: l'inverse du petit théorème de Fermat n'est pas vrai. Nous pouvons avoir pour un certain nombre composite . Ces nombres sont appelés pseudoprimes de Fermat pour fonder . Les pseudoprimes de Fermat à la base 2 sont également appelés nombres de Poulet . $a^{n-1}\equiv 1 \pmod n$ $n$ $a$

Le premier pseudoprime de Fermat à base (ou premier nombre de Poulet) est , pour lequel nous avons: $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}$

Cela signifie que notre algorithme va retourner au lieu du 69 ^e nombre attendu . $341$ $347$

la mise en oeuvre

@PoonLevi a trouvé la solution de 44 octets suivante, qui est directement basée sur : $(2)$

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

En utilisant <2au lieu de ==1, nous économisons 1 octet mais nous introduisons dans la séquence, car : $1$ $2^1-1\equiv 0 \pmod 1$

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

Essayez-le en ligne!

En commençant par , nous obtenons les termes attendus de 1 car nous faisons une itération de moins: $p=2$

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

Essayez-le en ligne!

La dernière astuce consiste à utiliser à la n<1orplace de n and. C'est tout aussi long, mais la dernière itération renvoie True au lieu de 0 , ajoutant ainsi le décalage manquant à chaque terme.

Arnauld
la source

Félicitations à vous tous! C'est la solution que j'avais en tête. Je pense que c'est drôle que, d'après la motivation du défi "Si j'ai une séquence de nombres, combien dois-je fournir avant de savoir de quelle séquence je parle?", Les 50 premiers nombres premiers ne sont apparemment pas suffisants - un extraterrestre jouant au golf sur Python supposerait que vous parliez d'une séquence différente.

xnor

@xnor J'adore l'idée d'un "extraterrestre

golfeur de

3

Python 3 , crashoz , 45 octets

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

Essayez-le en ligne!

L'expression x*60-x**3*10+x**5/2-x**7/84est la série de Taylor pour jusqu'au terme , multipliée par 60. C'est assez précis sur les entrées utilisées, mais pour des valeurs plus élevées, les deux divergent à mesure que les termes tronqués deviennent plus pertinents. $sin(x)$ $x^7$

xnor
la source

3

JavaScript (ES6), la réponse d'Arnauld (10 octets)

n=>8*n*n|n

Essayez-le en ligne!

ngn
la source

2

Haskell , réponse de Laikoni , 26 22 octets

_{-4 octets en n'utilisant pas infix div, grâce à Laikoni !}

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

Essayez-le en ligne!

Explication

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

b 42=0

ბიმო
la source

Ah, je n'y ai pas pensé. J'ai une approche différente qui conduit à une fissure de 20 octets au cas où vous voudriez un peu plus réfléchir. Aussi ((n+1)`div`2)-> div(n+1)2.

Laikoni

@Laikoni: Ouais, ne le révèle pas tout de suite! Oups, ouais ça fait pas mal de temps que j'ai joué au golf, je vais le mettre à jour.

ბიმო

2

> <> , réponse de crashoz 203 octets

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





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

Essayez-le en ligne!

J'allais faire quelque chose d'intelligent avec le fait que les nombres pairs / impairs ci n=20- dessus étaient les mêmes, sauf pour un élément répété au centre, mais il était plus facile de coder en dur chaque élément.

L'entrée se fait via le -vdrapeau. N'imprime rien pour les éléments supérieurs à 34.

Jo King
la source

2

Pascal (FPC) , réponse d'AlexRacer , 80 octets

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

Essayez-le en ligne!

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

Cela semble une réponse tardive, mais de toute façon merci @AlexRacer pour un bon puzzle!

r_64
la source

1

Wow, c'est encore plus court que ce que j'avais. Bienvenue chez PPCG!

AlexRacer

1

JavaScript, la réponse de fəˈnɛtɪk (12 octets)

$x=6$

x=>2.72**x|0

Essai

g=
x=>2.72**x|0

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

Développer l'extrait

Alternativement, essayez-le en ligne!

M. Xcoder
la source

1

JavaScript, la réponse de fəˈnɛtɪk (17 octets)

$15$

x=>2.7182819**x|1

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

Essai

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(","))

Développer l'extrait

Alternativement, essayez-le en ligne!

M. Xcoder
la source

1

Husk , déchiffrant 5 octets de BMO avec 3 2 octets

-1 grâce à BMO ( LdΣ-> LΣpuisque, une fois donné un Tnum, Leffectue "la représentation de la longueur de chaîne")

LΣ

Essayez-le en ligne!

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

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

Jonathan Allan
la source

Félicitations, c'était ma solution exacte! Cependant, je viens de noter que pour TNum s Let Ld sont équivalents, vous économisez un octet;)

ბიმო

Ah, j'ai cherché "digit" dans le wiki pour essayer de trouver la longueur numérique, mais je n'ai pas repéré ce qui Lremplace comme "la longueur de la représentation des chaînes" Tnum.

Jonathan Allan

(Notez qu'ils ne sont équivalents que pour les entiers non négatifs - assez bien pour cela.)

Jonathan Allan

1

> <> , Réponse d'Aiden F. Pierce , 36 octets

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

Essayez-le en ligne!

Une autre solution avec chaque valeur codée en dur par ligne. Étant donné que la réponse originale était également principalement codée en dur, je ne me sens pas trop coupable à ce sujet.

Jo King
la source

0

JavaScript, réponse de fəˈnɛtɪk , 23 octets

$0$ $n\ge 14$

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

Essayez-le en ligne!

Comment?

L'expression se `${73211e9}`développe dans la chaîne "73211000000000", fournissant une table de recherche de 14 valeurs qui sont soustraites de 14, ce qui donne la séquence attendue.

$n\ge 14$

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

21 octets

NaN $n\ge 14$

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

Essayez-le en ligne!

Arnauld
la source

Codage en dur des flics et des voleurs (voleurs)

Défi

Notation

Réponses:

cQuents , réponse de Stephen , 3 octets

Comment ça fonctionne

JavaScript, la réponse de fəˈnɛtɪk (17 octets)

Essai

Haskell , réponse de Laikoni , 15 octets

Python 2 , réponse de xnor , 43 octets

Crédits

Comment?

Théorie

la mise en oeuvre

Python 3 , crashoz , 45 octets

JavaScript (ES6), la réponse d'Arnauld (10 octets)

Haskell , réponse de Laikoni , 26 22 octets

Explication

> <> , réponse de crashoz 203 octets

Pascal (FPC) , réponse d'AlexRacer , 80 octets

JavaScript, la réponse de fəˈnɛtɪk (12 octets)

Essai

JavaScript, la réponse de fəˈnɛtɪk (17 octets)

Essai

Husk , déchiffrant 5 octets de BMO avec 3 2 octets

> <> , Réponse d'Aiden F. Pierce , 36 octets

JavaScript, réponse de fəˈnɛtɪk , 23 octets

Comment?

21 octets