Cherche algorithme de devinette
ycochard
Messages postés
1
Date d'inscription
samedi 6 octobre 2007
Statut
Membre
Dernière intervention
1 mai 2008
-
1 mai 2008 à 17:54
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 3 mai 2008 à 05:59
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 3 mai 2008 à 05:59
8 réponses
malalam
Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Membre
Dernière intervention
2 mars 2010
25
2 mai 2008 à 11:01
2 mai 2008 à 11:01
Hello,
tu devrais demander à akinator directement. Il y a un lien "contact". Ceci dit, je doute qu'ils partagent...
Toujours est-il que leur bidule est impressionnant! Je suis resté sur le cul, pour parler impoliment. J'ai essayé 2 fois et ça a marché les 2 fois, et très vite. Leur algo cerne vraiment vite...vraiment bien foutu. Je suis impressionné lol...
tu devrais demander à akinator directement. Il y a un lien "contact". Ceci dit, je doute qu'ils partagent...
Toujours est-il que leur bidule est impressionnant! Je suis resté sur le cul, pour parler impoliment. J'ai essayé 2 fois et ça a marché les 2 fois, et très vite. Leur algo cerne vraiment vite...vraiment bien foutu. Je suis impressionné lol...
malalam
Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Membre
Dernière intervention
2 mars 2010
25
2 mai 2008 à 11:07
2 mai 2008 à 11:07
En tous cas, ce qui est sûr, c'est qu'ils s'appuient sur une sacrée base de données (3 sur 3 là... : ma copine d'abord, mon chat, puis Teddy Rinner...pour ce dernier je ne pensais pas que le site trouverait...grosse base de données très à jour...nan, décidément, je suis impressioné! Merci pour le lien ;-)).
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
44
2 mai 2008 à 15:29
2 mai 2008 à 15:29
quand il te pose une question, j'imagine qu'il pose celle qui te permet d'eloigner le plus de "suspects".
imagine, t'as :
questionX : - R1 - R2 - R3
il y a encore N1 personnes qui correspondent a la reponse R1 (et aux autres questions repondues evidement), N2 pour R2, et N3 pour R3.
plus Max(N1, N2, N3) est petit, plus la question est pertinente (en effet, moins elle laisse de suspects...)
J'ai mis ici des valeurs bool : le personnage correspond il a la reponse R1 : oui ou non, a la reponse R2, oui ou non. Cet algo n'est pas forcement correct parce-qu'on a parfois des gens qui se trompent en entrant quelqu'un.
Ensuite, leur algo n'est peut-etre pas construit comme ca : en effet, tu peux construire un arbre de questions reponses en "live" qui amene a chaque personne : je m'explique : au debut, t'entres une question, et une personne par reponse. C'est ton arbre de depart. Ensuite, chaque fois que le site ne trouve pas la personne, il demande une question supplementaire qu'il ajoute alors a cet emplacement, pour separer son erreur de la vraie reponse.
Cet algo peut-etre sujet, plus facilement, a des doublons et des erreurs par contre.
imagine, t'as :
questionX : - R1 - R2 - R3
il y a encore N1 personnes qui correspondent a la reponse R1 (et aux autres questions repondues evidement), N2 pour R2, et N3 pour R3.
plus Max(N1, N2, N3) est petit, plus la question est pertinente (en effet, moins elle laisse de suspects...)
J'ai mis ici des valeurs bool : le personnage correspond il a la reponse R1 : oui ou non, a la reponse R2, oui ou non. Cet algo n'est pas forcement correct parce-qu'on a parfois des gens qui se trompent en entrant quelqu'un.
Ensuite, leur algo n'est peut-etre pas construit comme ca : en effet, tu peux construire un arbre de questions reponses en "live" qui amene a chaque personne : je m'explique : au debut, t'entres une question, et une personne par reponse. C'est ton arbre de depart. Ensuite, chaque fois que le site ne trouve pas la personne, il demande une question supplementaire qu'il ajoute alors a cet emplacement, pour separer son erreur de la vraie reponse.
Cet algo peut-etre sujet, plus facilement, a des doublons et des erreurs par contre.
malalam
Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Membre
Dernière intervention
2 mars 2010
25
2 mai 2008 à 15:36
2 mai 2008 à 15:36
Moi je pense en effet qu'ils fonctionnent plutôt par chemin.
Ce qui me fait dire ça, c'est que vers la fin du jeu, quand le site a en fait déjà trouvé, il pose quelques questions totalement hors sujet : je pense qu'il apprend et complète son chemin au fur et à mesure, éloigne les réponses sans rapport. Je pense que c'est une sorte d'arbre, mais un très gros...c'est de la recherche opérationnelle.
Ce qui me fait dire ça, c'est que vers la fin du jeu, quand le site a en fait déjà trouvé, il pose quelques questions totalement hors sujet : je pense qu'il apprend et complète son chemin au fur et à mesure, éloigne les réponses sans rapport. Je pense que c'est une sorte d'arbre, mais un très gros...c'est de la recherche opérationnelle.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
44
2 mai 2008 à 15:46
2 mai 2008 à 15:46
si c'etait un simple arbre, il n'y aurait qu'un chemin de la racine a une personne.
chaque question decrit des ensembles de personnes (ceux qui ont leurs caracteristiques)
je pense que les questions additionelles servent a vraiment faire un graph, quand il ne connait pas le lien entre une personne et une reponse.
chaque question decrit des ensembles de personnes (ceux qui ont leurs caracteristiques)
je pense que les questions additionelles servent a vraiment faire un graph, quand il ne connait pas le lien entre une personne et une reponse.
malalam
Messages postés
10839
Date d'inscription
lundi 24 février 2003
Statut
Membre
Dernière intervention
2 mars 2010
25
2 mai 2008 à 15:51
2 mai 2008 à 15:51
Un arbre n'implique pas qu'un seul chemin de la racine à la personne. Regarde l'algo su scrabble, je pensais plutôt à un truc de ce genre.
Mais ça peuit-être beaucoup de choses en fait...tjrs est-il que l'algo est rapide...mais s'il est rapide c'est parce que la bdd derrière est grosse.
Néanmoins, les questions sont très générals au départ, puis se précisent : cela ressemble vraiment à un arbre.
mais bon...difficile de savoir.
Mais ça peuit-être beaucoup de choses en fait...tjrs est-il que l'algo est rapide...mais s'il est rapide c'est parce que la bdd derrière est grosse.
Néanmoins, les questions sont très générals au départ, puis se précisent : cela ressemble vraiment à un arbre.
mais bon...difficile de savoir.
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
44
2 mai 2008 à 16:16
2 mai 2008 à 16:16
je ne sais pas de quel algo tu parles
Personellement, je trouve l'inclusion d'ensemble plus seduisante. (ma premiere idee revient a une inclusion d'ensembles)
Personellement, je trouve l'inclusion d'ensemble plus seduisante. (ma premiere idee revient a une inclusion d'ensembles)
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
44
3 mai 2008 à 05:59
3 mai 2008 à 05:59
code fait rapidement, a l'arrache, c'est moche, c'est lent, mais ca a le merite de te donner quelques indices
<?php
function newQuestion(){
return '
reponse
';
}
function insertName($nom){
$nom=strtolower(htmlentities($nom));
$nom=strtoupper($nom[0]).substr($nom, 1);
$a=mysql_query('INSERT INTO personnes SET nom="'.$nom.'"');
if ($a===false){
$a=mysql_query('SELECT id FROM personnes WHERE nom="'.$nom.'"') or die(mysql_error());
$data=mysql_fetch_assoc($a);
if ($data===false){
echo 'Personne a ce nom !';
return false;
}
$id=$data['id'];
echo $id;
}else{
$id=mysql_insert_id();
}
foreach ($_SESSION['reponses'] as $r){
mysql_query('INSERT INTO link SET id_personne='.$id.', id_reponse='.$r);
}
return true;
}
session_start();
mysql_connect('', '', '') or die(mysql_error());
//met ici tes identifiants de connections...
//mysql_query('DROP DATABASE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE DATABASE IF NOT EXISTS QuestionsReponses') or die(mysql_error());
mysql_query('USE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS question(
id int unsigned auto_increment,
question text,
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS reponse(
id int unsigned auto_increment,
id_question int unsigned,
reponse varchar(200),
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS personnes(
id int unsigned auto_increment,
nom varchar(200),
primary key(id),
unique(nom)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS link(
id_personne int unsigned,
id_reponse int unsigned,
unique(id_personne, id_reponse)
)') or die(mysql_error());
echo '
<html>
<head>
<style>
input[type="text"]{
width:80%;
border:0px solid;
border-bottom:1px solid #000;
background: #EEE;
}
.plusmoinsbox{
width:10%;
border:1px solid #AAA;
text-align:center;
margin:10px;
}
#reponsesBox{
width:90%;
border:1px solid #AAA;
margin-left:auto;
margin-right:auto;
padding:10px;
margin-top:10px;
margin-bottom:10px;
}
</style>
<script type="text/javascript">
var counter=1;
function add(id){
var e=document.getElementById(id);
var fc=e.firstChild;
while (fc.nodeName!="DIV") fc=fc.nextSibling;
var clfc = fc.cloneNode(true);
e.appendChild(clfc);
counter++;
}
function del(id){
if (counter==1) return;
var e=document.getElementById(id);
var fc=e.lastChild;
while (fc.nodeName!="DIV") fc=fc.previousSibling;
e.removeChild(fc);
counter--;
}
</script>
</head>
<form action="questionsreponses.php" method="post">
';
if (!isset($_SESSION['reponses']))
$_SESSION['reponses']=array();
if (!isset($_SESSION['questions']))
$_SESSION['questions']=array();
if (isset($_POST['autre_question'])){
$_SESSION['questions'][]=intval($_POST['idq']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}else if (isset($_POST['clean'])){
$_SESSION['reponses']=array();
$_SESSION['questions']=array();
}else if (isset($_POST['reponse'])){
if (isset($_POST['question'])){
mysql_query('INSERT INTO question SET question="'.htmlentities($_POST['question']).'"')
or die(mysql_error());
$qid=mysql_insert_id();
$_SESSION['questions'][]=$qid;
foreach ($_POST['reponse'] as $i=>$q){
mysql_query('INSERT INTO reponse SET reponse="'.htmlentities($q).'", id_question='.$qid)
or die(mysql_error());
if (isset($_POST['is'][$i])){
$_SESSION['reponses'][]=mysql_insert_id();
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if(isset($_POST['idq'])){
$_SESSION['questions'][]=intval($_POST['idq']);
foreach ($_POST['reponse'] as $i=>$on){
$_SESSION['reponses'][]=$i;
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if (isset($_POST['nom'])){
insertName($_POST['nom']);
}else if (isset($_POST['autre_nom'])){
insertName($_POST['autre_nom']);
}
$List=implode(', ', $_SESSION['reponses']);
$QList=implode(', ', $_SESSION['questions']);
if ($List!=''){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
HAVING '.count($_SESSION['reponses']).'=count
') or die(mysql_error());
$nombre_suspects = mysql_num_rows($suspects);
}else{
$suspects=false;
$nombre_suspects=-1;
$List='0';
$QList='0';
}
if ($nombre_suspects==1){
$data=mysql_fetch_assoc($suspects);
echo ''.$data['nom'].'
';
}else if ($nombre_suspects==0){
echo '
';
}else{
$req=mysql_query('
SELECT
id, question,
(
SELECT MAX((SELECT COUNT(*) FROM link WHERE id_reponse=reponse.id
AND id_personne IN
(SELECT id_personne FROM link WHERE id_reponse IN ('.$List.') )
/*ici, il manque une notion d\'ordre, c\'est mauvais,*/
/*mais ca devrait fonctionner a peu pres correctement*/
))
FROM reponse
WHERE id_question = question.id
) as max
FROM question
WHERE id NOT IN ('.$QList.')
ORDER BY max DESC
') or die(mysql_error());
if (mysql_num_rows($req)==0){
echo newQuestion();
}else{
$data=mysql_fetch_assoc($req);
echo '
'.$data['question'].' ('.$data['max'].')
';
$req=mysql_query('SELECT reponse, id FROM reponse WHERE id_question='.$data['id']) or die(mysql_error());
while ($data=mysql_fetch_assoc($req)){
echo '
'.$data['reponse'].'
';
}
echo '';
}
}
echo '
</form>';
if ($suspects!==false){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) * 100 / '.count($_SESSION['reponses']).' as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
') or die(mysql_error());
echo '
';
while ($data=mysql_fetch_assoc($suspects)){
echo '<li>'.$data['nom'].' ('.intval($data['count']).' %)</li>';
}
echo '';
}
echo '
</html>
';
?>
<?php
function newQuestion(){
return '
reponse
';
}
function insertName($nom){
$nom=strtolower(htmlentities($nom));
$nom=strtoupper($nom[0]).substr($nom, 1);
$a=mysql_query('INSERT INTO personnes SET nom="'.$nom.'"');
if ($a===false){
$a=mysql_query('SELECT id FROM personnes WHERE nom="'.$nom.'"') or die(mysql_error());
$data=mysql_fetch_assoc($a);
if ($data===false){
echo 'Personne a ce nom !';
return false;
}
$id=$data['id'];
echo $id;
}else{
$id=mysql_insert_id();
}
foreach ($_SESSION['reponses'] as $r){
mysql_query('INSERT INTO link SET id_personne='.$id.', id_reponse='.$r);
}
return true;
}
session_start();
mysql_connect('', '', '') or die(mysql_error());
//met ici tes identifiants de connections...
//mysql_query('DROP DATABASE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE DATABASE IF NOT EXISTS QuestionsReponses') or die(mysql_error());
mysql_query('USE QuestionsReponses') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS question(
id int unsigned auto_increment,
question text,
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS reponse(
id int unsigned auto_increment,
id_question int unsigned,
reponse varchar(200),
primary key(id)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS personnes(
id int unsigned auto_increment,
nom varchar(200),
primary key(id),
unique(nom)
)') or die(mysql_error());
mysql_query('CREATE TABLE IF NOT EXISTS link(
id_personne int unsigned,
id_reponse int unsigned,
unique(id_personne, id_reponse)
)') or die(mysql_error());
echo '
<html>
<head>
<style>
input[type="text"]{
width:80%;
border:0px solid;
border-bottom:1px solid #000;
background: #EEE;
}
.plusmoinsbox{
width:10%;
border:1px solid #AAA;
text-align:center;
margin:10px;
}
#reponsesBox{
width:90%;
border:1px solid #AAA;
margin-left:auto;
margin-right:auto;
padding:10px;
margin-top:10px;
margin-bottom:10px;
}
</style>
<script type="text/javascript">
var counter=1;
function add(id){
var e=document.getElementById(id);
var fc=e.firstChild;
while (fc.nodeName!="DIV") fc=fc.nextSibling;
var clfc = fc.cloneNode(true);
e.appendChild(clfc);
counter++;
}
function del(id){
if (counter==1) return;
var e=document.getElementById(id);
var fc=e.lastChild;
while (fc.nodeName!="DIV") fc=fc.previousSibling;
e.removeChild(fc);
counter--;
}
</script>
</head>
<form action="questionsreponses.php" method="post">
';
if (!isset($_SESSION['reponses']))
$_SESSION['reponses']=array();
if (!isset($_SESSION['questions']))
$_SESSION['questions']=array();
if (isset($_POST['autre_question'])){
$_SESSION['questions'][]=intval($_POST['idq']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}else if (isset($_POST['clean'])){
$_SESSION['reponses']=array();
$_SESSION['questions']=array();
}else if (isset($_POST['reponse'])){
if (isset($_POST['question'])){
mysql_query('INSERT INTO question SET question="'.htmlentities($_POST['question']).'"')
or die(mysql_error());
$qid=mysql_insert_id();
$_SESSION['questions'][]=$qid;
foreach ($_POST['reponse'] as $i=>$q){
mysql_query('INSERT INTO reponse SET reponse="'.htmlentities($q).'", id_question='.$qid)
or die(mysql_error());
if (isset($_POST['is'][$i])){
$_SESSION['reponses'][]=mysql_insert_id();
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if(isset($_POST['idq'])){
$_SESSION['questions'][]=intval($_POST['idq']);
foreach ($_POST['reponse'] as $i=>$on){
$_SESSION['reponses'][]=$i;
}
$_SESSION['reponses']=array_unique($_SESSION['reponses']);
$_SESSION['questions']=array_unique($_SESSION['questions']);
}
}else if (isset($_POST['nom'])){
insertName($_POST['nom']);
}else if (isset($_POST['autre_nom'])){
insertName($_POST['autre_nom']);
}
$List=implode(', ', $_SESSION['reponses']);
$QList=implode(', ', $_SESSION['questions']);
if ($List!=''){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
HAVING '.count($_SESSION['reponses']).'=count
') or die(mysql_error());
$nombre_suspects = mysql_num_rows($suspects);
}else{
$suspects=false;
$nombre_suspects=-1;
$List='0';
$QList='0';
}
if ($nombre_suspects==1){
$data=mysql_fetch_assoc($suspects);
echo ''.$data['nom'].'
';
}else if ($nombre_suspects==0){
echo '
';
}else{
$req=mysql_query('
SELECT
id, question,
(
SELECT MAX((SELECT COUNT(*) FROM link WHERE id_reponse=reponse.id
AND id_personne IN
(SELECT id_personne FROM link WHERE id_reponse IN ('.$List.') )
/*ici, il manque une notion d\'ordre, c\'est mauvais,*/
/*mais ca devrait fonctionner a peu pres correctement*/
))
FROM reponse
WHERE id_question = question.id
) as max
FROM question
WHERE id NOT IN ('.$QList.')
ORDER BY max DESC
') or die(mysql_error());
if (mysql_num_rows($req)==0){
echo newQuestion();
}else{
$data=mysql_fetch_assoc($req);
echo '
'.$data['question'].' ('.$data['max'].')
';
$req=mysql_query('SELECT reponse, id FROM reponse WHERE id_question='.$data['id']) or die(mysql_error());
while ($data=mysql_fetch_assoc($req)){
echo '
'.$data['reponse'].'
';
}
echo '';
}
}
echo '
</form>';
if ($suspects!==false){
$suspects=mysql_query('
SELECT id_personne, COUNT(*) * 100 / '.count($_SESSION['reponses']).' as count,
(SELECT nom FROM personnes WHERE personnes.id=link.id_personne) AS nom
FROM link WHERE id_reponse IN ('.$List.')
GROUP BY id_personne
') or die(mysql_error());
echo '
';
while ($data=mysql_fetch_assoc($suspects)){
echo '<li>'.$data['nom'].' ('.intval($data['count']).' %)</li>';
}
echo '';
}
echo '
</html>
';
?>
