SIMILI - trouver le code secret

Olympiades mathématiques, énigmes et défis
Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

SIMILI - trouver le code secret

par Obwil » 13 Juil 2019, 17:26

Bonjour à tous,

Je viens vous présenter mon jeu de combinaisons SIMILI, qui fait appel essentiellement à la logique.

Ce jeu est une variante des carrés logiques type MasterMind, la différence étant surtout qu'un cherche la présence et non le bon positionnement.

Le but du jeu est de trouver une combinaison secrète, à partir d'autres combinaisons dites "utiles".

A chaque combinaison utile est associée un nombre qui correspond au nombre de chiffres présents dans la combinaison secrète ET dans cette combinaison. C'est le nombre de similitudes avec la combinaison secrète.

Quelques précisions :
- les combinaisons sont rangées par ordre croissant pour plus de lisibilité
- les similitudes ne tiennent compte que de la présence, pas de la position, et ne prennent en compte les multiples que s'ils sont dans la combinaison secrète ET la combinaison utile.

Exemple :

La combinaison secrète peut contenir (ou pas) les chiffres 1,2,3 et 4.

1-3-3-4 : 1 similitude
1-2-2-4 : 2 similitudes
1-1-2-4 : 2 similitudes
1-4-4-4 : 3 similitudes

La réponse est : 2-4-4-4

Je vous donne quelques grilles, amusez-vous bien et n'hésitez pas à me faire des retours de ce que vous en pensez, je serai ravi d'échanger avec vous sur vos méthodes de résolutions :)

(Les similitudes sont à droite de la grille, et les chiffres que peut contenir (ou pas) la combinaison secrète sont en bas de la grille.)

Image

Image

Image

Image

Image

Image

Image

Image
Cette dernière est assez coriace ;)



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 14 Juil 2019, 14:59

bj,

**la méthode ci-dessous est pas top à la main

pour
1,3,3,3
3,4,4,4
1,3,3,4
1,1,1,4

on peut représenter les nombres sous un vecteur v tq le ieme el de v correspond au nombre de "i" trouvés:
donc respectivement
1 0 3 0
0 0 1 3
1 0 2 1
3 0 0 1

l'idée est de générer des tuples de conditions pour toutes les lignes (layer)
de prendre le layer 0 et layer 1, de les merger en layer t
puis de prendre layer t et layer 2, de les merger en layer t
et ainsi de suite jusqu'à la fin.
à la fin le layer contient que les tuples qui satisfont toutes les lignes

pour générer un tuple condition, par ex pour le premier layer 1 0 3 0
comme on deux simil, prendre toutes les combi de deux el parmi 1 3 3 3, et on impose les conditions
0 _ 2 _
1+ 0 1 0

0 _ 2 _ signifie que le tuple contient deux "3" et donc necessairement aucun 1 (sinon ca ferait trois simi)
les underscore signifient que on peut mettre n'importe quoi dedans

1+ 0 1 0 signifie qu'on a dans le tuple solution strictement un "3" et au moins un "1" (potentiellement plus)

la règle de merge deux layers consiste à prendre le produit cartesien puis pour un tuple t1 et t2 (rsp du layer i et du layer i+1)
de conserver le tuple résultant que si il est valide:
Code: Tout sélectionner
t: tuple de retour
pour colonne à colonne c de t1/t2 (aka el1, el2)
    si el1 == _
        t[c] = el2
    //pareil dans lautre sens
    si el1 contient + && el1<=el2
        t[c] = el2
    //pareil dans lautre sens
    si el1==el2
        t[c] = el1
    retourner non valide



ex:
Code: Tout sélectionner
-----------
ref 1  0  3  0 
1+ _  0  _ 
0  _  1  _ 

-----------
ref 0  0  1  3 
_  _  1+ 1 
_  _  0  2 

-----------
ref 1  0  2  1 
1+ _  1  0 
1+ _  0  1+
0  _  2+ 0 
0  _  1  1+

-----------
ref 3  0  0  1 
3+ _  _  0 
2  _  _  1+

//ici process des layer <1  0  3  0> et <0  0  1  3>
incomp 1+ _  0  _   X _  _  1+ 1 
incomp 0  _  1  _   X _  _  0  2 
kept layer
1+ _  0  2 
0  _  1  1 

incomp 1+ _  0  2   X 1+ _  1  0 
incomp 1+ _  0  2   X 0  _  2+ 0 
incomp 1+ _  0  2   X 0  _  1  1+
incomp 0  _  1  1   X 1+ _  1  0 
incomp 0  _  1  1   X 1+ _  0  1+
incomp 0  _  1  1   X 0  _  2+ 0 
kept layer
1+ _  0  2 
0  _  1  1 

incomp 1+ _  0  2   X 3+ _  _  0 
incomp 0  _  1  1   X 3+ _  _  0 
incomp 0  _  1  1   X 2  _  _  1+
kept layer
2  _  0  2 
//ci dessus solution, on complete avec ce qu'on veut

2  0  0  2


dans l'ex ci-dessus une solution est
1 1 4 4
mais
1 1 2 4 4
1 1 2 2 2 ... 4 4
sont aussi solutions

**on a eleminé 11 tuples, pour la grille 9x9, on en élimine environ 2746...d'où le fait qu'à la main...
la vie est une fête :)

Avatar de l’utilisateur
Sa Majesté
Modérateur
Messages: 6275
Enregistré le: 23 Nov 2007, 16:00

Re: SIMILI - trouver le code secret

par Sa Majesté » 14 Juil 2019, 17:12

Ben moi j'ai trouvé ton petit jeu très sympa 8-)
J'ai tout fait à la main, le dernier m'a demandé un petit peu de temps mais j'en suis venu à bout.
C'est toi qui as inventé ce jeu ?

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 14 Juil 2019, 17:42

fatal_error a écrit:bj,

**la méthode ci-dessous est pas top à la main

[...]

**on a eleminé 11 tuples, pour la grille 9x9, on en élimine environ 2746...d'où le fait qu'à la main...


Merci pour ta réponse c’est super intéressant, il faut que j’arrive à tout décoder dans ton explication mais c’est une méthode que je pourrais décliner en algorithme pour générer toutes les solutions possibles.

J’ai utilisé le système des vecteurs pour générer toutes les combinaisons possibles, en fonction de la longueur et des valeurs utilisables.
Ensuite je vérifie si chaque combinaison peut résoudre la grille. C’est une méthode brute qui est gourmande en calcul et qui a ses limites, parce que je ne génère que les combinaisons de même longueur, et il arrive qu’il y ait des solutions de longueur differente.
Et mon but étant de générer des grilles à solution unique ET de même longueur que les combinaisons de la grille, mon algo ne permet pas de le faire.

Donc merci pour ta méthode je vais me pencher dessus.

ÉDIT: également pourquoi ne pas afficher les combinaisons par leurs vecteurs (changer 1144 par 2002). Ça complexifierait probablement la compréhension du jeu.
Modifié en dernier par Obwil le 14 Juil 2019, 18:03, modifié 1 fois.

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 14 Juil 2019, 17:55

Sa Majesté a écrit:Ben moi j'ai trouvé ton petit jeu très sympa 8-)
J'ai tout fait à la main, le dernier m'a demandé un petit peu de temps mais j'en suis venu à bout.
C'est toi qui as inventé ce jeu ?


Merci ça fait super plaisir :)
Oui j’ai eu l’idee de jeu en jouant aux dés avec ma copine, on a commencé par générer la grille et la combi secrète en lançant des dés et ça fonctionnait bien, puis je me suis mis à travailler sur le script qui permettrait de générer, avec tous les paramètres possibles, à coup sûr une solution unique.

Bravo pour les résolutions, je suppose que plus tu avançais en difficulté, plus tu utilisais la verification d’hypothèses « si tel chiffre est bon alors... ».

Je me rends compte qu’avec cette méthode on trouve à coup sûr même si ça prend un peu de temps. Le jeu a donc atteint une limite dans sa complexité.

J’aimerais l’ameliorer dans ce sens.

Si tu veux d’autres grilles tu me dis ^^

Avatar de l’utilisateur
Sa Majesté
Modérateur
Messages: 6275
Enregistré le: 23 Nov 2007, 16:00

Re: SIMILI - trouver le code secret

par Sa Majesté » 14 Juil 2019, 21:37

Obwil a écrit:Merci ça fait super plaisir :)
Oui j’ai eu l’idee de jeu en jouant aux dés avec ma copine, on a commencé par générer la grille et la combi secrète en lançant des dés et ça fonctionnait bien, puis je me suis mis à travailler sur le script qui permettrait de générer, avec tous les paramètres possibles, à coup sûr une solution unique.

Ben franchement bravo :P
C'est pas évident d'avoir une idée d'un nouveau jeu et de le mettre en oeuvre comme tu l'as fait.

Obwil a écrit:Bravo pour les résolutions, je suppose que plus tu avançais en difficulté, plus tu utilisais la verification d’hypothèses « si tel chiffre est bon alors... ».

Oui c'est ça.
Pour le dernier, j'ai été un peu plus méthodique : pour chaque chiffre, j'ai noté d'une part le nombre d'occurrences dans toute la grille, d'autre part le nombre de lignes dans lequel il apparaît. Puis je me suis dit que j'avais intérêt à faire des hypothèses sur ceux qui apparaissent le plus souvent et qui sont présents dans un maximum de lignes.
Ah oui au fait, je trouve (en couleur de police blanche pour ne pas spoiler, passer la souris dessus) : 124557778

Obwil a écrit:Je me rends compte qu’avec cette méthode on trouve à coup sûr même si ça prend un peu de temps. Le jeu a donc atteint une limite dans sa complexité.

Oui enfin ça fait quand même pas mal de cas et de sous-cas ... :mrgreen:

Obwil a écrit:Si tu veux d’autres grilles tu me dis ^^

Vas-y, publie ! 8-)

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 14 Juil 2019, 23:47

Bien joué pour le dernier, c'est ça !
En voici un bien prise de tête (peut-être plus que le dernier?) :

Image

Et j'en rajouterai quelques un plus cools à faire ^^.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 01:16

re,

je pense avoir une génération...(mais jai fait que un test pour 5x5...)

avec un vecteur <0,1,0,3> représentant 2,4,4,4
on sait que les tuples vont être engendrés par
<_,a,_,b> pour a = 0 a qqch et b=0 à qqch

à chaque ligne on a donc une famille de tuples générés.
<a_i,b_i,c_i,d_i> potentiellement a_i== 0 si dans la ligne ya pas l'élément 1, idem pour les autres b,c,..

A la fin, le but n'est plus d'avoir un vecteur de coeffs, mais un vecteur fixé par ex: X=<1,2,1,0>
qui signifie que ieme famille
<a_i,b_i,c_i,d_i> _doit_ satisfaire <1,2,1,0>
(donc en l'occurrence, a_i doit varier au moins jusqu'à 1, etc)

on peut représenter nos variables/familles sous une mat d'adjacence A(i,:) représentant <a_i,...,d_i> avec par ex A(1,4) = 0 si d_4 ==0
X est notre vecteur de coeffs dont on veut une valeur (pour avoir l'unicité de la solution) et B les coeffs de similitudes

on cherche alors X tq
AX=B

avec comme contrainte:
det(A)=+-1 (pour que inv(A) soit à coeff entier) et donc X aussi
X >= 0
B <= N (pour chaque el de B, N taille de A, idem nombre d'el différents). Ca assure que chaque el de X <= N

*pour une ligne de A donnée par ex:
1 1 1 0 1
et X = <1 3 1 1 0>

la ligne nécessairement contient 1 2 3 5 (et jamais de 4)
X impose qu'il faut au moins un 1, trois 2, un trois
idem 1 2 2 2 3 et on rajoute au moins un 5 et on peut rajouter des 1,2,3,5 (même si apres la taille de la grille augmente donc on préfère éviter...)

et construit les autres lignes de la même manière


on peut se limiter à une grille de taille 5 si on impose de plus une cond sur X:
Soit la rep "booléenne" de X Xu. (ici <1 1 1 1 0>)
pour satisfaire A, ya au moins un el à placer ("misplacés") qui tient pas compte de X...là ou X (j) vaut 0 et A(..,j) vaut 1), et pour satisfaire X il faut placer sum(X)==5 el + ces "misplacés"

Xu xor 1 1 1 1 1 le transforme en Xru = <0 0 0 0 1>
et sum(A(i,:) & Xru) donne le compte de ces "misplacés"

on cherche alors X tel que sum(A(i,:)) + sum(A(i,:) & Xru) <= N


toute la difficulté c'est donc de trouver la mat A et B tq le X trouvé satisfasse
0<=X<=N (el à el)
et sum(A(i,:)) + sum(A(i,:) & Xru) <= N pour i = 1 à N

j'intuite que qqsoit A pourvu que det(A)=1 on peut trouver un tel B, mais il se fait tard

j'essairai de générer qq grilles demain
la vie est une fête :)

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: SIMILI - trouver le code secret

par lyceen95 » 15 Juil 2019, 01:20

Sur le précédent, avec 9 cases par ligne, et 9 'lettres' (ou plutôt chiffres) dans l'alphabet, avoir seulement 3 bons chiffres de bons sur chaque ligne, c'est vraiment peu. Si on propose 9 chiffres au hasard, on doit en général avoir plutôt 5 chiffres communs que 3. Du coup, j'ai commencé à chercher en me disant : les 9 et les 6 sont très sur-représentés dans les différentes propositions, il ne doit pas y avoir de 6 ni de 9, ou éventuellement 1 des 2, grand maximum. C'était la base de ma recherche. Mais je n'ai pas eu le courage de chercher jusqu'au bout.

Sur le dernier exemple, c'est plus dur. On a moins de colonnes, et on a plus de chiffres. 3 Bons chiffres dans chaque ligne, ça doit pas être très loin de la normale. Donc on peut difficilement faire des hypothèses beaucoup plus plausibles que d'autres. Je commencerais quand même avec l'hypothèse : il n'y a pas de 9.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 13:32

en revoyant mon poste plus haut parce que overkill.

je peux pas trop dire si les solutions sont difficiles à trouver... mais pour la construction on peut s'en sortir ainsi:
on choisit au pif une matrice A booleenne et on bidouille jusqu'à ce que det(A) > 0
si on a un peu de chance (... j'aimerais prouver mais j'y suis pas), on trouve un X et un B
X est le vecteur de coeffs (dont la somme vaut N, taille de A), et B le vecteur de simi (dont chaque composante est inférieure à N)
parmi les solutions retournées, il suffit de choisir un triplet <A,X,B>
Code: Tout sélectionner
1;
A = [
   1 1 1 1 0 1 1 1 1;
   1 1 1 0 1 0 0 0 1;
   0 0 1 1 0 0 1 0 1;
   0 1 1 1 0 1 0 1 1;
   1 1 0 1 1 1 1 0 0;
   1 0 1 0 1 1 0 0 1;
   0 0 1 0 0 0 1 0 1;
   0 1 1 0 1 1 0 1 1;
   1 1 0 1 1 0 0 0 1;
];
if det(A)==0

    %we also want that for given B, only this X reaches B
    %that is A*X = B_i => A must be invertible
    return
end
function [X,B] = genB(A)
    N = length(A)
    cs=nchoosek(1:N+N-1, N-1);
    for i = 1:length(cs)
        c = cs(i,:);
        X=[];
        X(1) = c(1)-1;
        for j = 2:length(c)
            X(j) = c(j) - (c(j-1)+1);
        end
        X(N) = N+N-1 - c(end);
        B=A*X';
        if any(B>N)
            continue
        end

        Xru = X == 0;
        bu = A*Xru';
        if all(A*X'+bu <= N)
            X
            B
            A
        end
    end
    X = 0;
    B = 0;
endfunction
[X,B] = genB(A);

et pour ce triplet, on peut construire une grille (yen a plusieurs potentiellement) qui assure l'unicité (trouver X apres reso)
Code: Tout sélectionner
var txt = `
X =

   0   0   0   1   3   1   1   1   2

B =

   6
   5
   4
   5
   6
   6
   3
   7
   6

A =

   1   1   1   1   0   1   1   1   1
   1   1   1   0   1   0   0   0   1
   0   0   1   1   0   0   1   0   1
   0   1   1   1   0   1   0   1   1
   1   1   0   1   1   1   1   0   0
   1   0   1   0   1   1   0   0   1
   0   0   1   0   0   0   1   0   1
   0   1   1   0   1   1   0   1   1
   1   1   0   1   1   0   0   0   1


`
function parse(txt){
    var s = txt.trim();
    var xInd = s.indexOf('X');
    var bInd = s.indexOf('B');
    var aInd = s.indexOf('A');
    var x = s.substring(xInd, bInd);
    var b = s.substring(bInd, aInd);
    var a = s.substring(aInd);
    var xr = x.split('=')[1].trim().match(/\d/g).map(x=>parseInt(x))
    var br = b.split('=')[1].trim().match(/\d/g).map(x=>parseInt(x))
    var ar = a.split('=')[1].trim().match(/\d/g).reduce((acc,n,i)=>{
        if(i%xr.length == 0){
            var r = [];
            acc.push(r);
        }else{
            r = acc[acc.length-1];
        }
        r.push(parseInt(n));
        return acc;
    },[])
    return [ar,xr,br]
}

function buildGrid(a,x,b){
    var grid = a.map(row=>{
        var needed = [];
        row.forEach((y,i)=>{
            if(y){
                var times = x[i];
                if(times == 0){
                    times = 1; //variable must be impl
                }
                var iTimes = new Array(times).fill(i+1)
                needed.push(...iTimes);
            }
        });
        if(needed.length < b.length){
            var y = row.findIndex(x=>x)
            var times = b.length - needed.length;
            var iTimes = new Array(times).fill(y+1)
            needed.push(...iTimes);
        }
        return needed;
    })
    return grid;
}
var [a,x,b] = parse(txt);
console.log('a ', a)
var grid = buildGrid(a,x,b);
console.log(grid.map(r=>{
    var tpl = '    rrows.push_back({%X});';
    return tpl.replace('%X', r.sort((a,b)=>a-b))
}).join('\n'))
console.log('    std::vector<int> similis({ '+b+'});')
// rrows.push_back({1,2,3,4,6,7,8,9,9});
// rrows.push_back({1,1,2,3,5,5,5,9,9});
// rrows.push_back({3,3,3,3,3,4,7,9,9});
// rrows.push_back({2,2,2,3,4,6,8,9,9});
// rrows.push_back({1,1,2,4,5,5,5,6,7});
// rrows.push_back({1,1,3,5,5,5,6,9,9});
// rrows.push_back({3,3,3,3,3,3,7,9,9});
// rrows.push_back({2,3,5,5,5,6,8,9,9});
// rrows.push_back({1,1,2,4,5,5,5,9,9});
// std::vector<int> similis({ 6,5,4,5,6,6,3,7,6});

ici la solution étant 0 0 0 1+ 3+ 1+ 1+ 1+ 2+ (et pour respecter le nombre d'elem par grille, enlever les +)

edit2: pour l'existance:
|X| = N
donc pour tout A(i,:), |A(i,:)X| <= N donc il existe obligatoirement un B
(par ex) trivialement, prendre X=1...1
si on introduit un 0 dans X, j'intuite encore...
la vie est une fête :)

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 15 Juil 2019, 13:54

fatal_error a écrit:en revoyant mon poste plus haut parce que overkill.

je peux pas trop dire si les solutions sont difficiles à trouver... mais pour la construction on peut s'en sortir ainsi:
[...]
ici la solution étant 0 0 0 1+ 3+ 1+ 1+ 1+ 2+ (et pour respecter le nombre d'elem par grille, enlever les +)


Salut fatal_error,

Je t'ai envoyé un mp parce que j'aimerais bien qu'on travaille ensemble sur ces scripts que tu as faits ;)

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 15 Juil 2019, 13:58

lyceen95 a écrit:Sur le précédent, avec 9 cases par ligne, et 9 'lettres' (ou plutôt chiffres) dans l'alphabet, avoir seulement 3 bons chiffres de bons sur chaque ligne, c'est vraiment peu. Si on propose 9 chiffres au hasard, on doit en général avoir plutôt 5 chiffres communs que 3. Du coup, j'ai commencé à chercher en me disant : les 9 et les 6 sont très sur-représentés dans les différentes propositions, il ne doit pas y avoir de 6 ni de 9, ou éventuellement 1 des 2, grand maximum. C'était la base de ma recherche. Mais je n'ai pas eu le courage de chercher jusqu'au bout.

Sur le dernier exemple, c'est plus dur. On a moins de colonnes, et on a plus de chiffres. 3 Bons chiffres dans chaque ligne, ça doit pas être très loin de la normale. Donc on peut difficilement faire des hypothèses beaucoup plus plausibles que d'autres. Je commencerais quand même avec l'hypothèse : il n'y a pas de 9.


Je suis embêté... j'ai oublié d'enregistrer la solution pour la dernière grille. Je vais la faire résoudre par mon algo dès que j'ai le temps haha.

Sinon je suis d'accord avec tout ce que tu as dis, comme tout le monde trouvait la réponse à la grille de 9 chiffres en plus ou moins de temps, j'ai réfléchi à comment corser le jeu, et en équilibrant les proportions chiffres bons/ chiffres mauvais dans chaque grille on a plus de mal !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 16:41

voici un exemple de generation de grille quasi instant

Code: Tout sélectionner
function mmprod(A,B){
    var bw = B[0].length;
    var M = [];
    A.forEach((x,i)=>{
        var ab_i = [];
        for(var k = 0; k<bw; ++k){

            var ab_ik = x.reduce((s,xij, j)=>{
                return s+B[j][k]*xij;
            },0);
            ab_i.push(ab_ik%2);
        }
        M.push(ab_i);
    })
    return M;
}
function mvprod(A,v){
    return A.map((x,i)=>{
        return x.reduce((acc,xij,j)=>{
            return acc + xij*v[j];
        },0)
    })
}
function buildA(N, density=0.5){
    var build = function(lower){
        var A = new Array(N).fill(0).map((x,i)=>{
            return new Array(N).fill(0).map((y,j)=>{
                if(lower(i,j)){
                    return Math.random()>density?1:0;
                }
                if(i==j){
                    return 1;
                }
                return y;
            })
        });
        return A;
    }
    var L = build((i,j)=>j<i);
    var U = build((i,j)=>j>i);
    return mmprod(L,U);
}



function perms(v, cbk){
    v = v.slice(0).sort((a,b)=>a-b);
    //https://stackoverflow.com/questions/9960908/permutations-in-javascript
    const permute = (arr, m = []) => {
        if (arr.length === 0) {
            return cbk(m);
        }
        for (let i = 0; i < arr.length; i++) {
            if(i > 0 && arr[i]==arr[i-1])continue;
            let curr = arr.slice();
            let next = curr.splice(i, 1);
            var ok = permute(curr.slice(), m.concat(next));
            if(!ok) return ok;
        }
        return true;
    }
    return permute(v);
}

function doubletXB(A, x){
    const N = A.length;
    x = x.concat(new Array(N-x.length).fill(0));
    var Xg, Bg;
    perms(x, function(c){
        var X = c.slice(0);
        var x2 = c.slice(0);
        for(var i = 0; i<c.length; ++i){
            if(c[i]==0){
                x2[i]=1;
            }
        }
        if(mvprod(A,x2).map(y=>y<=N).every(x=>x)){
            Bg = mvprod(A,X);
            Xg = X;
            return false;
        }
        return true;
    })
    return [Xg,Bg];

}

function buildGrid(a,x,b){
    var grid = a.map(row=>{
        var needed = [];
        row.forEach((y,i)=>{
            if(y){
                var times = x[i];
                if(times == 0){
                    times = 1; //variable must be impl
                }
                var iTimes = new Array(times).fill(i+1)
                needed.push(...iTimes);
            }
        });
        if(needed.length < b.length){
            var y = row.findIndex(x=>x)
            var times = b.length - needed.length;
            var iTimes = new Array(times).fill(y+1)
            needed.push(...iTimes);
        }
        return needed;
    })
    return grid;
}
function toCpp(grid,b){
    console.log(grid.map(r=>{
        var tpl = '    rrows.push_back({%X});';
        return tpl.replace('%X', r.sort((a,b)=>a-b))
    }).join('\n'))
    console.log('    std::vector<int> similis({ '+b+'});') 
}
function randSum(N, zDensity=0.3){
    //https://stackoverflow.com/questions/1527803/generating-random-whole-numbers-in-javascript-in-a-specific-range
    //Returns a random integer between min (inclusive) and max (inclusive).
    function getRandomInt(min, max) {
        min = Math.ceil(min);
        max = Math.floor(max);
        return Math.floor(Math.random() * (max - min + 1)) + min;
    }
    //zeros between 1 and 40%
    var kz = Math.floor(N*zDensity);
    var a = new Array(N).fill(1);
    for(var i = 0; i<kz; ++i){
        a[i] = 0;//give that one somewhere
        var min = kz;
        var max = N-1;//wtf, N is reached otherwise..
        var iz = getRandomInt(min, max);
        a[iz]+=1;
    }
    return a;
}
function main(){
    const N = 10;
    var A = buildA(N);
    //choose yourself such that sum(x) is N
    var x;
    //x = [1, 2, 0, 2, 0, 4, 1];
    var [X, B] = doubletXB(A, x || randSum(N,0.5));
    if(!X)throw 'failed !!';
    var tg = require('./toGrid');
    var grid = buildGrid(A,X,B);
    console.log('expect solution:',X.join(' '))
    toCpp(grid, B);
}
main();


exemple de gen https://jsfiddle.net/w62zf80h/
edit: fix perms gen (1 2 3 0_1 0_2 == 1 2 3 0_2 0_1)
la vie est une fête :)

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 15 Juil 2019, 18:58

fatal_error a écrit:voici un exemple de generation de grille quasi instant

Code: Tout sélectionner
...


exemple de gen https://jsfiddle.net/w62zf80h/


C'est énorme !!! Je vais aller en faire quelques unes pour voir s'il y a des différences.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 20:38

Dans le cas de déterminant nul, par exemple pour l'exemple
2,2,3,3|2
2,3,4,4|2
1,2,2,3|2
1,2,3,4|2
(la mat d'adjacence est
0 1 1 0
0 1 1 1
1 1 1 0
1 1 1 1
)
l'unique solution est <0 1 1 0>
en fait les solutions du système AX=B sont données par
<0,a,2-a,0>
on remarque que pour <0,2,0,0> par exemple
la ligne <1 1 1 1> ne peut pas être satisfaite car
il faut placer un el partout + un autre el en b (pour b==2)


Dans l'ex ci-dessus, on peut prendre trivialement
<1, a, 2-a, 0> qui invalide tous les a, sauf a = 1
le vecteur solution devenant <1,1,1,0> et B=[2,2,3,3]

d'une manière plus générale,
on prend un X, on déduit B.
on sait qu'il y a une infinité de X_i solution (soit X_s l'ensemble des X_i).
On décrit X_s, on regarde que X_s n'a qu'une seule solution X_f satisfiant A(X_f+X_f==0)<=N (pour toute composante)

si je dis pas de conneries (...)
si k appartient à ker(A), Ak = 0
donc si on a pris un certain X_f, AX_f = B et A(X_f+k) = B
donc l'ensemble des solutions est généré par
X_f+ker(A)

on cherche alors un certain X_f, tq qqsoit k de ker(A), A*((X_f+k)+(X_f+k)==0>N pour au moins une composante

Dans l'exemple ci-dessus, ker(A)=(0,1,-1,0)
comme |X_f|<=N
les candidats sont {a*<0,1,-1,0> pour a = -4 à 4, a!=0}

par ex ci-dessous, les B (je les ai pas tous copiés) vérifient normalement que ya une seule solution
Code: Tout sélectionner
X =

   0   1   1   1

B =

   2
   3
   2
   3

---
X =

   1   0   0   0

B =

   0
   0
   1
   1

---
X =

   1   0   0   1

B =

   0
   1
   1
   2



la vie est une fête :)

Obwil
Membre Naturel
Messages: 49
Enregistré le: 13 Juil 2019, 17:14

Re: SIMILI - trouver le code secret

par Obwil » 15 Juil 2019, 22:49

Pour reprendre ton premier post dans lequel je n'avais pas tout saisi.

fatal_error a écrit:bj,

**la méthode ci-dessous est pas top à la main

pour
1,3,3,3
3,4,4,4
1,3,3,4
1,1,1,4

on peut représenter les nombres sous un vecteur v tq le ieme el de v correspond au nombre de "i" trouvés:
donc respectivement
1 0 3 0
0 0 1 3
1 0 2 1
3 0 0 1

fatal_error a écrit:l'idée est de générer des tuples de conditions pour toutes les lignes (layer)

Toutes les possibilités d’ensembles de chiffres, dans la combinaison, qui valident sa similitude.
fatal_error a écrit:de prendre le layer 0 et layer 1, de les merger en layer t
puis de prendre layer t et layer 2, de les merger en layer t
et ainsi de suite jusqu'à la fin.

Je ne comprends pas mais j'attends de voir les exemples après.
fatal_error a écrit:à la fin le layer contient que les tuples qui satisfont toutes les lignes

pour générer un tuple condition, par ex pour le premier layer 1 0 3 0
comme on deux simil, prendre toutes les combi de deux el parmi 1 3 3 3, et on impose les conditions
0 _ 2 _
1+ 0 1 0

0 _ 2 _ signifie que le tuple contient deux "3" et donc necessairement aucun 1 (sinon ca ferait trois simi)
les underscore signifient que on peut mettre n'importe quoi dedans

1+ 0 1 0 signifie qu'on a dans le tuple solution strictement un "3" et au moins un "1" (potentiellement plus)

Jusqu’ici tout va bien
fatal_error a écrit:la règle de merge deux layers consiste à prendre le produit cartesien puis pour un tuple t1 et t2 (rsp du layer i et du layer i+1)
de conserver le tuple résultant que si il est valide:

Toujours pas compris le merge, j'attends de voir l'exemple après.
fatal_error a écrit:
Code: Tout sélectionner
t: tuple de retour
pour colonne à colonne c de t1/t2 (aka el1, el2)
    si el1 == _
        t[c] = el2
    //pareil dans lautre sens
    si el1 contient + && el1<=el2
        t[c] = el2
    //pareil dans lautre sens
    si el1==el2
        t[c] = el1
    retourner non valide



Donc ça c'est le process de merge. Je comprends que tu procèdes valeur après valeur dans chaque tuple, mais sans un exemple directement associé je n'arrive pas bien saisir. Et je ne comprends pas le "+&&".
fatal_error a écrit:ex:
Code: Tout sélectionner
-----------
ref 1  0  3  0 
1+ _  0  _ 
0  _  1  _ 


Je m'attendais à trouver comme résultats 1 _ 1 _ et 0 _ 2 _ , pourquoi à chaque résultat il manque une valeur ? Et que signifie le + ?
fatal_error a écrit:
Code: Tout sélectionner
-----------
ref 0  0  1  3 
_  _  1+ 1 
_  _  0  2 

-----------
ref 1  0  2  1 
1+ _  1  0 
1+ _  0  1+
0  _  2+ 0 
0  _  1  1+

-----------
ref 3  0  0  1 
3+ _  _  0 
2  _  _  1+


Pareil pour les autres
fatal_error a écrit:
Code: Tout sélectionner

//ici process des layer <1  0  3  0> et <0  0  1  3>
incomp 1+ _  0  _   X _  _  1+ 1  // (1+ _ 1 _), (1+ _ 0 1), (_ _ 1 _), (_ _ 0 1)
incomp 0  _  1  _   X _  _  0  2      // (0 _ 0 _), (0 _ _ 2), (_ _ 1 _), (_ _ 1 2)
kept layer
1+ _  0  2 
0  _  1  1 


Que signifie incomp?
J'ai essayé de faire le résultat des deux produits cartésiens et j'ai obtenu ça...
(1+ _ 1 _), (1+ _ 0 1), (_ _ 1 _), (_ _ 0 1) et (0 _ 0 _), (0 _ _ 2), (_ _ 1 _), (_ _ 1 2)
Ca ne correspond pas à ce que tu as trouvé..

fatal_error a écrit:
Code: Tout sélectionner
incomp 1+ _  0  2   X 1+ _  1  0 
incomp 1+ _  0  2   X 0  _  2+ 0 
incomp 1+ _  0  2   X 0  _  1  1+
incomp 0  _  1  1   X 1+ _  1  0 
incomp 0  _  1  1   X 1+ _  0  1+
incomp 0  _  1  1   X 0  _  2+ 0 
kept layer
1+ _  0  2 
0  _  1  1 

incomp 1+ _  0  2   X 3+ _  _  0 
incomp 0  _  1  1   X 3+ _  _  0 
incomp 0  _  1  1   X 2  _  _  1+

kept layer
2  _  0  2 


Après je comprends les opérations successives, prendre le layer 0 et layer 1, de les merger en layer t
puis prendre layer t et layer 2, de les merger en layer t... mais dans le process j'ai les problèmes énoncés ci-dessus.

fatal_error a écrit:
Code: Tout sélectionner
//ci dessus solution, on complete avec ce qu'on veut

2  0  0  2


dans l'ex ci-dessus une solution est
1 1 4 4
mais
1 1 2 4 4
1 1 2 2 2 ... 4 4
sont aussi solutions

**on a eleminé 11 tuples, pour la grille 9x9, on en élimine environ 2746...d'où le fait qu'à la main...

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: SIMILI - trouver le code secret

par lyceen95 » 15 Juil 2019, 23:36

Obwil a écrit:Comme tout le monde trouvait la réponse à la grille de 9 chiffres en plus ou moins de temps, j'ai réfléchi à comment corser le jeu, et en équilibrant les proportions chiffres bons/ chiffres mauvais dans chaque grille on a plus de mal !

Je pense exactement l'inverse. Un jeu doit être amusant.
Pour moi, ce jeu ressemble plus au sudoku qu'au mastermind. Au mastermind, il y a 2 actions ?
- Quelle ligne vais-je proposer pour éclaircir le jeu ?
- Quelle est la solution ?
La phase la plus intéressante est probablement la première, et ici, tu as supprimé cette phase, pour ne garder que la 2ème. Bof.

Au Sudoku, c'est un peu la même logique, on cherche à trouver la seule disposition compatible avec un certain nombre d'informations. Et au Sudoku, contrairement au Mastermind, on a toutes les informations dès le début, on ne peut pas poser des questions au maitre du jeu. C'est donc la même logique que ton jeu.
Et tout le charme de la réflexion du Sudoku, c'est de chercher quelles sont les cases pour lesquelles on a le plus d'informations, pour avancer pas à pas.
Ici, la démarche utilisée, c'est la force brute. Avec la nouvelle orientation que tu vises, on va devoir tester tous les cas 1 par 1, en commençant par les 0 et en finissant par les 9. C'est triste à mourir. Le seul amusement à partir de ce jeu, ça devient : écrire un algorithme rapide de résolution, voire un algorithme rapide de génération de grille.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 23:50

ref 1 0 3 0
1+ _ 0 _
0 _ 1 _

la similitude est 1:
ca veut dire que tu vas avoir au moins un 1 ou strictement un trois.
si tu as au moins un 1, ton vecteur a la forme
1+ _ 0 _
le + signifie "au moins". Par exemple la combinaison solution peut être
1 1 0 3
ou bien
2 1 0 3 ...
ou bien
4 1 0 22 ...
il faut juste respecter le 0 imposé, ET au moins un 1.

Le deuxieme tuple candidat est celui qui contient strictement un 3.
0 _ 1 _


SI la similitude était 2:
tu as deux possibilités:
- soit (au moins) un 1 et strictement un 3.
1+ _ 1 _
Soit deux 3
0 _ 2 _

pour le merge:
la sémantique c'est: t'as deux tuples t1 et t2.
Tu as remarqué que le but c'est pour un tuple condition, de le "compléter". Idem, remplir les '_' et si possible quand ya +, par ex 2+ de savoir si c'est 2, 3, 4, ...

condition el1==el2
si t'as
1 _ _ _ et 2 _ _ _
ya aucune combinaison satisfaisante...parce qu'il faut en même temps strictement un 1 et strictement deux 1.

condition si el1 contient + && el1<=el2 (le && signifie AND)
si t'as
1+ _ _ _ et 2 _ _ _
alors vu que il faut au moins un 1 ET strictement deux 1, alors la combinaison sera de la forme
2 _ _ _
par exemple
1+ _ _ _ et 0 _ _ _ ne marche pas.
1+ _ _ _ et 0+ _ _ _ marche. (mais on le voit pas en pratique. Le tuple résultant serait de la forme 1+ _ _ _)

Pour le prod : 1030 et 0013
tu as
{
1+ _ 0 _
0 _ 1 _
}
X
{
_ _ 1+ 1
_ _ 0 2
}

####################
1+ _ 0 _
_ _ 1+ 1
---------- <= ces deux tuples sont INCOMPATibles
1+ _ KO
####################
1+ _ 0 _
_ _ 0 2
----------
1+ _ 0 2 <--- OK
####################
0 _ 1 _
_ _ 1+ 1
----------
0 _ 1 1 <--- OK (noter: strictement 1)
####################
0 _ 1 _
_ _ 0 2
---------- <= ces deux tuples sont INCOMPATibles
0 _ KO

au final, le layer résultant ne contient que les tuples compatibles:
{1+ _ 0 2, 0 _ 1 1}
la vie est une fête :)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: SIMILI - trouver le code secret

par fatal_error » 15 Juil 2019, 23:53

@lyceen95
Code: Tout sélectionner
Ici, la démarche utilisée, c'est la force brute. Avec la nouvelle orientation que tu vises, on va devoir tester tous les cas 1 par 1, en commençant par les 0 et en finissant par les 9

en fait non.
si tu ecris sous forme d'adjacence... ca revient à appliquer gauss jordan pour trouver X, donc tu es exempt de force brute. Il faut probablement une certaine gymnastique intellectuelle...
pe que le jeu va faire des monstres du calcul d'inversion :mrgreen:
la vie est une fête :)

Avatar de l’utilisateur
Sa Majesté
Modérateur
Messages: 6275
Enregistré le: 23 Nov 2007, 16:00

Re: SIMILI - trouver le code secret

par Sa Majesté » 16 Juil 2019, 17:44

Obwil a écrit:Bien joué pour le dernier, c'est ça !
En voici un bien prise de tête (peut-être plus que le dernier?) :

Image

Et j'en rajouterai quelques un plus cools à faire ^^.

Ma réponse : 1266788

Bon c'est sûr qu'à la main, il faut être sacrément courageux et méthodique (eh oui je me lance des fleurs :mrgreen: )

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 13 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite