logo Homepage
+  NewbieContest
|-+  Général» Defouloir» Enigme du soir, Bonsoir !
Username:
Password:
Pages: 1 ... 6 7 [8] 9 10 11
  Imprimer  
Auteur Fil de discussion: Enigme du soir, Bonsoir !  (Lu 131004 fois)
harvey

Profil challenge

Classement : 12/54605

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #105 le: 05 Mars 2017 à 01:16:18 »

J'ai fait un programme pour générer une solution. L'approche est naïve, mais ça marche...
Il faudrait potasser la théorie des codes cycliques pour améliorer ça.

Code:
#usr/bin/python
#encoding:utf8


#ceci

#est

#un

#script

#en

#python

#youpi


import itertools
import random

def hamming(a,b):
    return bin(a^b).count("1")

"""
On cherche à générer 2**12 vecteurs distants deux à deux d'au moins 7
(en distance de Hamming).
On pose que le mot nul (poids de hamming = 0) est valide,
et on cherche à générer un ensemble de mots valides de poids 7
(les plus proches).
Chaque mot de poids 4 doit correspondre à un unique mot valide
de poids 7. On peut donc faire un brute-force sur les mots de poids
4, suivi (chaque fois qu'on en trouve un encore non-couvert) d'un bf
sur les triplets susceptibles de le compléter.
"""
u7 = set()
for _v4 in itertools.combinations(range(23),4):
    v4 = sum(1<<i for i in _v4)
    if any(hamming(v4,v)<=3 for v in u7):
        continue
    for _v3 in itertools.combinations(range(_v4[-1]+1,23),3):
        v3 = sum(1<<i for i in _v3)
        if all(hamming(v4|v3,v)>=7 for v in u7):
            u7.add(v4|v3)
            break

"""
Les mots valides d'un code forment un espace vectoriel.
En effet, soit un espace dont les éléments sont {e_1, ... e_n},
et tel que hamming(e_i, e_j)>=7  (i!=j).
On y introduit un nouveau vecteur V qui respecte la même condition.
L'ensemble devient:
{e_1, ..., e_n, e_1^V, ..., e_n^V}
La condition se propage à toutes les nouvelles combinaisons:
hamming(e_i, e_j^V) = hamming(e_i^e_j, V)
qui est >=7 par hypothèse.

On peut générer l'ensemble des mots valides en partant
de l'espace trivial {0} et en combinant avec les mots de poids 7.
"""

u23 = set([0])
base = []
for v in sorted(u7):
    smp = random.sample(u23,1)[0]
    if smp^v not in u23:
        u23.update([v^w for w in u23])
        base.append(v)

assert(len(u23)==4096 and len(base)==12)
print "Base:"
for v in base:
    print format(v,"023b")

#for v in sorted(u23):print format(v, "023b")

#vérification
hamdict=dict()
for i,j in itertools.combinations(u23,2):
    h=hamming(i,j)
    hamdict[h]=hamdict.get(h,0)+1
assert(min(hamdict.values())>=7)
print hamdict

Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 14/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #106 le: 06 Mars 2017 à 04:30:44 »

Voici une épreuve de logique que j’ai proposée il y’a plus d’un an mais qui n’a pas été acceptée car ”trop de solutions alternatives possibles“, et car ”on ne veut plus de suites logiques". Et pourtant, je ne crois pas que les testeurs aient eux-même trouvé de solution alternative .

Si quelqu’un arrive à la résoudre et la trouve sympa, peut-être que ça convaincra les admins de la publier:

Trouvez le nombre suivant dans cette suite:
1, 10, 100, 1000, 101, ?, ...

Indice: La réponse n'est pas 1001.
Journalisée
pixis
Administrateur

Profil challenge

Classement : 17/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #107 le: 06 Mars 2017 à 07:17:54 »

102 ?
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
BAAL

Profil challenge

Classement : 14/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #108 le: 06 Mars 2017 à 18:34:46 »

Avec quelle logique?
Il faudrait que la "solution alternative" tienne debout pour tous les éléments quand même, et sans considérer tous les premiers comme éléments d'initialisation arbitraire  .
Journalisée
pixis
Administrateur

Profil challenge

Classement : 17/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #109 le: 06 Mars 2017 à 19:48:15 »

Soit N un entier positif, si on prend un la suite des entiers entre 1 et N ordonnés alphabétiquement, alors pour N = 101 on a :

u0 = 1
u1 = 10
u2 = 100
u3 = 101
u4 = 11
u5 = 12
u6 = 13
...
u100 = 999

Ou en d'autre mots : ["1", "2", ... ,"N"].sorted()

Avec cette logique, les éléments donnés ici permettent de savoir exactement que N = 1000 et que le terme suivant est 102
(Si on avait N > 1000 alors on aurait 1001 après 1000, et non pas 101, donc N <= 1000 et si N < 1000 alors on n'aurait pas 1000 dans les données, donc N = 1000)

Aucun élément n'est en trop, et il ne manque aucun élément
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
BAAL

Profil challenge

Classement : 14/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #110 le: 07 Mars 2017 à 01:03:39 »

Pas mal en effet! J'accepterais presque ça comme solution alternative.
Cela dit tu n'as pas utilisé l'indice. Alors oui techniquement tu n'as pas trouvé 1001, mais tu devrais pouvoir expliquer pourquoi l'indice est là.

Ah, et aurais-je oublié de préciser?: la suite est infinie. Au temps pour moi (/me hides).
Journalisée
pixis
Administrateur

Profil challenge

Classement : 17/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #111 le: 07 Mars 2017 à 07:06:29 »

Très bien je vais continuer mes recherches alors. Pour moi l'indice était là parce que quand j'ai vu la suite, j'ai tout de suite pensé à 1001 (pour je ne sais quelle raison) et l'indice m'a dissuadé de faire des recherches dans ce sens. Un moyen d'éliminer une solution alternative, en somme.

Mais du coup ok pour les infos. J'espérais que je n'avais pas raison, et que la solution était plus intéressante
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
the lsd
Administrateur

Profil challenge

Classement : 191/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 3096

poulping for fun & profit


Voir le profil WWW
« #112 le: 07 Mars 2017 à 11:35:53 »

je ne crois pas que les testeurs aient eux-même trouvé de solution alternative

:p

Enjoy

The lsd
Journalisée

Newbie Contest Staff :
The lsd - Th3_l5D (IRC)
Statut :
Administrateur
Citation :
Cartésien désabusé : je pense, donc je suis, mais je m'en fous !
pixis
Administrateur

Profil challenge

Classement : 17/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #113 le: 07 Mars 2017 à 12:09:47 »

Pour sa défense, on n'en avait pas dans le log beta de l'épreuve. Mais pour sa pas-défense, on n'a pas refusé l'épreuve pour cette raison, mais plutôt (en modifiant un peu les propos)

Citation
Déjà beaucoup de logiques de type "suite".
Pas souvent motivant à résoudre et (d'apparence) vraiment guessing.

Bon après, quand c'est BAAL qui propose, je pense qu'il y a une méthode intelligente à adopter pour attaquer cette épreuve, et je ne pense pas que ce soit une suite 'alakon' avec un truc introuvable sauf si tu tombes sur le PDF de l'étude du truc.

A voir
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
BAAL

Profil challenge

Classement : 14/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #114 le: 07 Mars 2017 à 14:45:35 »

J'ai bien dit "presque". J'avoue que la réponse de pixis n'est pas mal, ça m'apprendra à faire le malin. Cela dit ça ne répond pas au fait que la suite doit être infinie (ainsi que l'indice).

L'épreuve est loin d'être comparable aux meilleurs épreuves de NC, ça n'est qu'une suite logique après tout, il ne faut pas aller chercher trop loin. C'est d'ailleurs pour ça que je n'ai pas trop insisté pour qu'elle soit publiée. Je ne suis pas d'accord avec l'argument des logiques alternatives, mais je suis plus ou moins d'accord avec le fait qu'on ne veuille plus de suites. Cela dit elle est meilleur que la plupart de celles qui sont déjà là.
Journalisée
flob
Administrateur

Profil challenge

Classement : 20/54605

Membre Junior
*****
Hors ligne Hors ligne
Messages: 74


Voir le profil WWW
« #115 le: 07 Mars 2017 à 23:12:40 »

Trouvez le nombre suivant dans cette suite:
1, 10, 100, 1000, 101, ?, ...

Indice: La réponse n'est pas 1001.

Salut,

Mmmm je proposerais bien 11 avec une logique un peu tordue mais qui semble fonctionner, voici les 18 premiers éléments que je peux proposer :

10000 0001
20000 0010
30000 0100
40000 1000
50000 0101
60000 0011
70000 0111
80000 1011
90001 0000
100001 0001
110001 0010
120001 0100
130001 1000
140001 0101
150001 0011
160001 0111
170001 1011
180010 0000

Une sorte d'incrémentation binaire par lots de 4 bits avec un règle étrange. Les 0 barrés sont là uniquement pour mieux illustrer la logique, comme si il y avait 8 bits, on pourrait cependant continuer la suite indéfiniment.

Voici les règles :
  • A chaque élément de la suite on déplace le 1 soit vers la gauche soit vers la droite dans un bloc de 4 emplacements.
  • La direction du déplacement au départ de la suite est de la droite vers la gauche.
  • Le 1 peut se déplacer uniquement sur un emplacement contenant un 0.
  • Lorsque le 1 ne peut plus se déplacer dans sa précédente direction il change de direction et un nouveau 1 est ajouté après le déplacement à la place du premier 0 disponible en partant de la droite (ce qui permet d'expliquer l'élément 7 par exemple).
  • Lorsque les règles précédentes ne peuvent plus être respectées sur le bloc en cours (sur l'élément 9 par exemple) on bascule sur le bloc de 4 suivant et on réinitialise le bloc en cours avec des 0 puis on reprend les règles normalement.

Mon exemple des 18 premiers éléments me semble juste uniquement si la chaine commence à 0. Si ce n'est pas le cas alors il suffit de supprimer les éléments 9 et 18 de mon exemple et d'adapter la dernière règle pour réinitialiser le bloc en cours avec 0001 au lieu de 0000, ça me semble également correct.

Est-ce une solution alternative valable ?
Journalisée

Newbie Contest Staff :
Flob
Statut :
Administrateur
Citation :
...
Blog :
elrindel.github.io
pixis
Administrateur

Profil challenge

Classement : 17/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #116 le: 07 Mars 2017 à 23:18:18 »

Bien tordue cette réponse ... Mais du coup

Citation
Indice: La réponse n'est pas 1001.

Comment l'indice est-il utilisé ?
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
flob
Administrateur

Profil challenge

Classement : 20/54605

Membre Junior
*****
Hors ligne Hors ligne
Messages: 74


Voir le profil WWW
« #117 le: 07 Mars 2017 à 23:42:55 »

Bien tordue cette réponse ... Mais du coup

Citation
Indice: La réponse n'est pas 1001.

Comment l'indice est-il utilisé ?

Sur un raisonnement similaire on aurait pu avoir 1001 comme réponse.
En modifiant la règle du changement de direction de sorte que la direction soit toujours de la droite vers la gauche sauf si on ne peut plus aller à gauche alors on tombe sur 1001 puis 0111 puis 1011 etc...
Mais puisque la réponse n'est pas 1001 alors j'ai juste arrangé la règle pour que ça colle
Journalisée

Newbie Contest Staff :
Flob
Statut :
Administrateur
Citation :
...
Blog :
elrindel.github.io
BAAL

Profil challenge

Classement : 14/54605

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #118 le: 08 Mars 2017 à 03:25:28 »

Bien tenté ! Mais je ne considère pas ça comme une alternative valable non plus, le choix des règles est complètement arbitraire, ainsi que la taille du bloc (4) qui est clairement là juste pour trouver le terme 101. Tu le montres toi-même en disant que tu aurais pu modifier les règles pour obtenir 1001.

Tu aurais aussi pu dire "une fois qu'on a un nombre pair de 1, le nombre suivant est 1337".

Journalisée
flob
Administrateur

Profil challenge

Classement : 20/54605

Membre Junior
*****
Hors ligne Hors ligne
Messages: 74


Voir le profil WWW
« #119 le: 08 Mars 2017 à 08:30:50 »

Dommage, ma solution me semblait plutôt élégante ^^

Tu aurais aussi pu dire "une fois qu'on a un nombre pair de 1, le nombre suivant est 1337".

Il est effectivement possible d'énoncer des règles totalement arbitraires mais mes règles me semblent bien respecter la structure du début de la suite tout en permettant de la continuer indéfiniment (je vois ça comme un compteur binaire, l'ajout d'un nombre tel que 1337 ou de tout autre nombre différent de 1 ou 0 aurait rendu ma solution beaucoup moins élégante) .
Le bloc de 4 est effectivement là pour rester cohérent dans la suite à cause du terme 101 qui vient après 1000, il fallait donc trouver une règle qui permettait au 1 de repartir en arrière.

Ceci dit, ma solution est tellement tordue que je peux concevoir qu'elle ne soit pas considérée comme valable, peut-on vraiment se permettre de réinventer la façon d'incrémenter un nombre en binaire ? ^^

Je vais chercher une autre solution.
Journalisée

Newbie Contest Staff :
Flob
Statut :
Administrateur
Citation :
...
Blog :
elrindel.github.io
Pages: 1 ... 6 7 [8] 9 10 11
  Imprimer  
 
Aller à: