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
-----------
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
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...
Sa Majesté a écrit:Ben moi j'ai trouvé ton petit jeu très sympa
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 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.
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... ».
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é.
Obwil a écrit:Si tu veux d’autres grilles tu me dis ^^
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);
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});
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 +)
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.
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();
fatal_error a écrit:voici un exemple de generation de grille quasi instant
- Code: Tout sélectionner
...
exemple de gen https://jsfiddle.net/w62zf80h/
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
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)
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.
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)
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:
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
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+
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
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
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...
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 !
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
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?) :
Et j'en rajouterai quelques un plus cools à faire ^^.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 13 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :