Pjukern:
Ok, skal prøve. Men husk på at jeg ikke er noen C++ guru selv da. Har knotet med det litt for noen år siden riktignok, men ikke så mye. Og så nå da, selvsagt. Tenkte det var en god anledning til å prøve seg litt igjen.
En annen ting er at du må ikke bli overveldet av en annens kode
Ser alltid forvirrende ut spør du meg, og så klarte jo code-boksen i forumet her å fjerne alle innrykkene da... ser jo mer spaghetti ut enn spaghetti!
Ang. outputs:
Hvis du setter konstanten DEBUGINFO til 1 (ca øverst i progget), så ser du noen ekstra linjer med info som spyttes ut, bl.a. resultat av "guesset", på linja "RES=". Aller øverst, per. gjetning/guess, er det en låne-tabell som ikke brukes i denne versjonen.. så kommer selve guesset, deretter RES, og så en tabell som inneholder antall løsninger som er igjen for akkurat den plassen/tallet (space-linja). Skrevet i, eh, "uberhex", hehe. dvs, F=15 som vanlig, og så videre, G=16, H =17... (dog vil det aldri bli 17.. er kun 16 til å begynne med med base=16).
(Noe av infoen er et trinn på etterskudd btw.. dvs det helt til høyre om antall funnede tall.. vet hvorfor, fikser det kanskje senere)
Det er ca linje 128 i koden ovenfor (som skriver ut resultatene) hvis du limer inn i en editor (Testet det nå og så at innrykkene kom med igjen, de vises visst tydeligvis ikke her i forumet).
Konstanten OUTPUT skriver ut hvert forsøk på alle spill. og konstanten GAMERUNS bestemmer da hvor mange spill som kjøres. Lønner seg å ha OUTPUT=0 for å teste f.eks. mange runs. Da skrives bare gjennomsnitlig antall forsøk etterpå.
Gjort sånn for enkelhets skyld, men kunne sikkert brukt argv også.
Effektiviseringen jeg snakket om gjaldt bare rutinen helt til slutt ( i "makeaguess"-funskjonen), dvs den som plukker ut nye tall å gjette på. Den plukker ut mest mulig forskjellige tall, og jeg testet da alle mulige kombinasjoner... fant bare ut at jeg kunne stoppe etter å ha funnet flest mulig forskjellige (åltså 5 forskjellige)... hehe. Akkurat det var ganske enkelt egentlig. Men slet litt med den algoritmen ellers..
Litt angående FEEDBACK-funksjonen:
Kode
// Get current guess result. 1 = found key.
// result[digit]
// 0 = value dosn't exist anywere
// 1 = correct value at wrong position(digit)
// 2 = correct value at correct position
int feedback(int guesskey[], int key[], int result[])
{
int res = 1;
for(int k=1;k<=DIGITS;k++)result[k]=0; // resetter RESULT-tabellen til 0 for alle elementer
// Løkker for å teste hva RESULTatet ble:
for(int g=1;g<=DIGITS;g++)
{
for(int k=1;k<=DIGITS;k++)
{
if(key[k]==guesskey[g])
{
if(k==g)result[g]=2;else if(result[g]!=2)result[g]=1; HER gis resultatet for et siffer
}
}
}
for(int i=1;i<=DIGITS;i++)
{
if(result[i]!=2)res=0;
}
return res;
}
Det er åltså setningen:
if(k==g)result[g]=2;else if(result[g]!=2)result[g]=1;
som er kjernen her.
guesskey[] er en tabell, fra guesskey[1] til [5] (egentlig fra 0, men bruker ikke den).
Det samme med result[] og key[], selvsagt.
Vet ikke hva jeg trenger å forklare, men:
Hvis et siffer(digit) programmet gjettet på er det samme på samme posisjon (k==g), så blir resultatet 2, hvis det er likt siffer men forskjellig posisjon, så blir resulatet 1, dersom det ikke er 2 fra før (else if(result[g]!=2)result[g]=1)
Ny kode:
(Obs, tok med "borrow"-delen, men den er kommentert ut da den ikke virker...)
Endret litt på koden nå, så nå kommer både resultat og guess ved at OUTPUT-konstanten =1, og det andre med DEBUGINFO-konstanten..
Kode
/* KEYFINDER
Sort of MasterMind-like
To guess the combination of a key of <DIGIT> nr. of digits of base <BASE>
author: 10goto10 @ nFF
dates: 2007.08.28 - 2007.08.31
v0.07 - simple elimination method works
v0.09 - refined elimination method a bit
v0.18 - refined guess-selection method considerably (I think.. but at a big time-penalty...)
v0.19 - small esthetic touch-up.
v0.20 - Made the guess-selection more effective!
*/
#include <iostream>
#include <time.h>
using namespace std;
const int GAMERUNS = 1; // nr. of games to run to calculate average from
const int OUTPUT = 1; // 1 = Outputs guesses for each game. 0 = no output (for averaging lots of games..)
const int DEBUGINFO = 0; // 1 = additional info.. beware info is one step behind
const int DIGITS = 5; // nr. of digits to guess
const int BASE = 16; // nr. of possibilities pr digit
const int MAXGUESSES = 20; // insurance...
void resetgame(int& guesses, int& dcount, int borrowed[], int result[], int dmark[], int dfound[], int remposs[], int poss[][BASE]);
void think(int guesses, int& dcount, int& borrows, int borrowed[], int dfound[], int dmark[], int guesskey[], int result[], int remposs[], int poss[][BASE]);
void makeaguess(int guesses, int dcount, int mostdiffs, int dfound[],int dmark[], int guesskey[], int result[], int remposs[], int poss[][BASE]);
int feedback(int guesskey[], int key[], int result[]);
int foundcount(int dmark[]);
char uberhex(int tall);
int main()
{
int guesses;
int totguesses;
int games; // games played
int gresult;
float average;
int key[DIGITS+1]; // gidder ikke knote med element null
int guesskey[DIGITS+1];
int result[DIGITS+1]; // guess result
int dfound[DIGITS+1]; // found digits
int dcount; // number of found digits
int borrows; // nr of borrows
int dmark[DIGITS+1]; // which digits are found? 0 = not this 1 = this (sort of boolean)
int poss[DIGITS+1][BASE] ; // possibilities-array. BASE start at 0...
int remposs[DIGITS+1]; // number of remaining possibilites for a digit
int borrowed[DIGITS+1]; // borrowed position to minimize guesses (boolean-ish)
int mostdiffs;
games = 0;
totguesses = 0;
average = 0.0;
cout << "KEYFINDER 0.20. \n\n Games to run: " << GAMERUNS << ". Digits to find: " << DIGITS << ". Base: " << BASE << "\n";
// randomize random seed
time_t seconds;
time(&seconds);
srand((unsigned int) seconds);
// cout << "random seed: " << seconds << endl;
mostdiffs=0;
for(int i=1;i<DIGITS;i++)mostdiffs+=i;
do
{
resetgame(guesses, dcount, borrowed, result, dmark, dfound, remposs, poss);
// make a random key
for(int i=1;i<=DIGITS;i++)key[i] = rand()%BASE;
if(OUTPUT==1)
{
cout << "\nKEY: ";
for(int i=1;i<=DIGITS;i++) // write the key
{
if(i!=1)cout << " ";
cout << uberhex(key[i]);
}
cout << endl << "=================" << endl;
cout << "Guesses:" << endl;
}
do
{
think(guesses,dcount,borrows,borrowed,dfound,dmark,guesskey,result,remposs,poss);
makeaguess(guesses,dcount,mostdiffs,dfound,dmark,guesskey,result,remposs,poss);
guesses += 1;
gresult = feedback(guesskey,key,result);
// Output stuff (how to make spaghetti without GOTO :-)
if(DEBUGINFO==1)
{
// output borrow flags
cout << " Borrow ";
for(int i=1;i<=DIGITS;i++)
{
cout << borrowed[i];
cout<<" ";
}
}
if(OUTPUT==1)
{
cout << endl;
// output guesses
cout << " Nr." << guesses << " : ";
for(int i=1;i<=DIGITS;i++)
{
//if(dmark[i]) cout << uberhex(dfound[i]); else cout << uberhex(guesskey[i]);
cout << uberhex(guesskey[i]);
cout<<" ";
}
}
if(DEBUGINFO==1)
{
cout << " - found:" << foundcount(dfound);
}
if(OUTPUT==1)
{
cout << "\nRES " << guesses << " : ";
for(int i=1;i<=DIGITS;i++)cout << result[i] << " ";
cout << "\n";
}
if(DEBUGINFO==1)
{
cout << " space: ";
for(int i=1;i<=DIGITS;i++)cout << uberhex(remposs[i]) << " ";
cout << "\n\n";
}
} while(!gresult and guesses<MAXGUESSES);
if(OUTPUT==1)cout << "\n\nGuesses: " << guesses << "\n\n";
totguesses += guesses;
games += 1;
if(OUTPUT==0 and DEBUGINFO==0)cout << "."; // original progressbar
} while(games<GAMERUNS);
average = totguesses / (float)games;
cout << "\n\n Finished. Games run: " << games << "\n Average solve-steps(guesses): " << average << "\n";
//cin.ignore();
cin.get();
return 1;
}
// Reset for new gamerun...
void resetgame(int& guesses, int& dcount, int borrowed[], int result[], int dmark[], int dfound[], int remposs[], int poss[][BASE])
{
guesses = 0;
dcount = 0;
for(int d=1;d<=DIGITS;d++)
{
for(int b=0;b<BASE;b++)poss[d][b]=b;
dfound[d]=0;
dmark[d]=0;
remposs[d]=BASE;
result[d]=0;
borrowed[d]=0;
}
}
// Get current guess result. 1 = found key.
// result[digit]
// 0 = value dosn't exist anywere
// 1 = correct value at wrong position(digit)
// 2 = correct value at correct position
int feedback(int guesskey[], int key[], int result[])
{
int res = 1;
for(int k=1;k<=DIGITS;k++)result[k]=0;
for(int g=1;g<=DIGITS;g++)
{
for(int k=1;k<=DIGITS;k++)
{
if(key[k]==guesskey[g])
{
if(k==g)result[g]=2;else if(result[g]!=2)result[g]=1;
}
}
}
for(int i=1;i<=DIGITS;i++)
{
if(result[i]!=2)res=0;
}
return res;
}
// make hex characters, 0-9 A-F or higher..
char uberhex(int tall)
{
char dig;
if(tall<10) dig=(char)(tall+48) ; else dig = (char)(tall+55);
return dig;
}
void think(int guesses, int& dcount,int& borrows, int borrowed[], int dfound[], int dmark[], int guesskey[], int result[], int remposs[], int poss[][BASE])
{
// Evaluate possible solutions left
if(guesses>0)
{
for(int r=1;r<=DIGITS;r++)
{
if(borrowed[r]==0)
{
if(result[r]==2)
{
dcount += 1; // deprecated
dfound[r] = guesskey[r]; // save value
dmark[r] = 1; // mark as found
remposs[r] = 1; // the only possibility left
poss[r][0] = guesskey[r]; // save value
}
if(result[r]==1) // remove from this position(digit)
{
int f=0;
for(int i=0;i<remposs[r];i++)
{
if(guesskey[r]==poss[r][i])
{
for(int rem=i;rem<remposs[r];rem++)
{
poss[r][rem] = poss[r][rem+1];
}
remposs[r] -= 1;
if(remposs[r]<1)remposs[r]=1; // just in case
f=1;
}
if(f==1)break;
}
}
}
if(result[r]==0) // remove from all positions
{
for(int d=1;d<=DIGITS;d++)
{
for(int b=0;b<remposs[d];b++)
{
if(poss[d][b]==guesskey[r])
{
remposs[d] -= 1;
if(remposs[d]<0)remposs[d]=0; // again;just in case
for(int rem=b;rem<remposs[d];rem++)
{
poss[d][rem]=poss[d][rem+1];
}
}
}
}
}
}
}
// borrows
// borrows = 0;
// for(int i=1;i<=DIGITS;i++)
// {
// if(dmark[i])borrows++;
// }
//
// // borrows = foundcount(dmark);
// if(borrows>0 and borrows<DIGITS)
// {
// int unfounds=0;
// int lendfrom[DIGITS+1][2];
// int borrowto[borrows+1];
// for(int i=1;i<=DIGITS;i++) // copy the unsorted remposs-array
// {
// if(!dmark[i] and remposs[i]>1) // only the unfound digits and if more than 1 solutions left
// {
// unfounds++;
// lendfrom[unfounds][1]=remposs[i];
// lendfrom[unfounds][2]=i;
// }
// }
// if(unfounds>1) // sort if more than one
// {
// for(int i=1;i<unfounds;i++)
// {
// for(int s=i+1;s<=unfounds;s++)
// {
// if(lendfrom[s][1]>lendfrom[i][1]) // sort it descending
// {
// int temp1=lendfrom[i][1];
// int temp2=lendfrom[i][2];
// lendfrom[i][1]=lendfrom[s][1];
// lendfrom[i][2]=lendfrom[s][2];
// lendfrom[s][1]=temp1;
// lendfrom[s][2]=temp2;
// }
// }
// }
// }
// for(int b=1;b<=DIGITS;b++)
// {
// int unfound=0;
// if(dmark[b]) // borrow found position
// {
// unfound++;
// if(unfound>unfounds)unfound=1; //wrap
// {
// remposs[b]=lendfrom[unfound][1];
// for(int bor=0;bor<remposs[b];bor++)
// {
// poss[b][bor]=poss[lendfrom[unfound][2]][bor];
// }
// borrowed[b]=1;
// result[b]=0; //reset result for this digit
// }
// }
// }
// }
//
}
// the guessing game
void makeaguess(int guesses, int dcount, int mostdiffs, int dfound[], int dmark[], int guesskey[], int result[], int remposs[], int poss[][BASE])
{
int step;
int biggest=0;
int comb[DIGITS+1]; // saved path with most different combination
int scan[DIGITS+1]; // current tested path
// if found all...
if(foundcount(dmark)>=DIGITS)
{
for(int i=1;i<=DIGITS;i++)
{
guesskey[i] = dfound[i];
}
}
else // Guess a new code
{
// Find the combination with the most nr of differences
// The uber-supah scan-algorithm
biggest = 0;
int temp;
for(int i=1;i<=DIGITS;i++)scan[i]=0;
int ende;
do
{
temp=0;
for(int a=1;a<DIGITS;a++)
{
for(int b=a+1;b<=DIGITS;b++)
{
if(abs(poss[a][scan[a]]-poss[b][scan[b]])>0)temp++;
}
}
if(temp>biggest)
{
biggest=temp;
for(int s=1;s<=DIGITS;s++)
{
comb[s]=scan[s]; // save path
}
}
scan[DIGITS]++; //increment last pointer
for(int s=DIGITS-1;s>0;s--)
{
if(scan[s+1]>=remposs[s+1])scan[s]++;
}
ende=1;
for(int s=1;s<=DIGITS;s++)
{
if(scan[s]<remposs[s])ende=0;
if(scan[s]>=remposs[s])scan[s]=0;
}
}while(!ende and biggest<mostdiffs);
// }while(!ende);
// the new guess
for(int s=1;s<=DIGITS;s++)guesskey[s]=poss[s][comb[s]];
}
}
int foundcount(int dmark[])
{
int jall = 0;
for(int i=1;i<=DIGITS;i++)
{
if(dmark[i])jall++;
}
return jall;
}
(Fikk en bug som gjorde at i noen tilfeller, så kaster den bort tall som den skulle ha brukt, en gang trengte den til og med 25 forsøk pga. denne feilen)
