15 puzzle solver: Difference between revisions
Content added Content deleted
No edit summary |
(→{{header|C++}}: Imperative solution < 1 sec) |
||
Line 35:
</pre>
=={{header|C++}}==
===Staying Functional (as possible in C++)===
====The Solver====
{{trans|FSharp}}
<lang cpp>
Line 107 ⟶ 108:
</lang>
====The Task====
<lang cpp>
int main (){
Line 121 ⟶ 122:
user 0m2.887s
sys 0m0.008s
</pre>
===Time to get Imperetive===
====The Solver====
<lang cpp>
// Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017
class fifteenSolver{
const int Nr[16]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[16]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}, i{1}, g{8}, e{2}, l{4};
int n{},_n{}, N0[80]{},N1[80]{},N3[81]{},N4[80];
unsigned long N2[80]{};
bool fU(){
if (N2[n]==0x123456789abcdef0) return true;
if (N4[n]<=_n) return fN();
return false;
}
bool fZ(const int w){
int a = n;
if ((w&i)>0){fI(); if (fU()) return true; n=a;}
if ((w&g)>0){fG(); if (fU()) return true; n=a;}
if ((w&e)>0){fE(); if (fU()) return true; n=a;}
if ((w&l)>0){fL(); return fU();}
return false;
}
bool fN(){
switch(N0[n]){case 0: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(i);
case 'u': return fZ(e);
default : return fZ(i+e);}
case 3: switch(N3[n]){case 'r': return fZ(i);
case 'u': return fZ(l);
default : return fZ(i+l);}
default: switch(N3[n]){case 'l': return fZ(i+l);
case 'r': return fZ(i+e);
case 'u': return fZ(e+l);
default : return fZ(l);}}
case 3: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(g);
case 'd': return fZ(e);
default : return fZ(e+g);}
case 3: switch(N3[n]){case 'r': return fZ(g);
case 'd': return fZ(l);
default : return fZ(g+l);}
default: switch(N3[n]){case 'l': return fZ(g+l);
case 'r': return fZ(e+g);
case 'd': return fZ(e+l);
default : return fZ(g+e+l);}}
default: switch(N1[n]){case 0: switch(N3[n]){case 'l': return fZ(i+g);
case 'u': return fZ(g+e);
case 'd': return fZ(i+e);
default : return fZ(i+g+e);}
case 3: switch(N3[n]){case 'd': return fZ(i+l);
case 'u': return fZ(g+l);
case 'r': return fZ(i+g);
default : return fZ(i+g+l);}
default: switch(N3[n]){case 'd': return fZ(i+e+l);
case 'l': return fZ(i+g+l);
case 'r': return fZ(i+g+e);
case 'u': return fZ(g+e+l);
default : return fZ(i+g+e+l);}}}
}
void fI(){
int g = (11-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]+1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n++]?0:1);
}
void fG(){
int g = (19-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]-1; N1[n+1]=N1[n]; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n++]?0:1);
}
void fE(){
int g = (14-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]; N1[n+1]=N1[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N1[n++]?0:1);
}
void fL(){
int g = (16-N1[n]-N0[n]*4)*4;
unsigned long a = N2[n]&((unsigned long)15<<g);
N0[n+1]=N0[n]; N1[n+1]=N1[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N1[n++]?0:1);
}
public:
fifteenSolver(int n, int i, unsigned long g){N0[0]=n; N1[0]=i; N2[0]=g; N4[0]=0;}
void Solve(){
while (not fN()){n=0;++_n;}
std::cout<<"Solution found in "<<n<<" moves: "; for (int g{0};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl;
}
};
</lang>
====The Task====
<lang cpp>
int main (){
fifteenSolver start(2,0,0xfe169b4c0a73d852);
start.Solve();
}
</lang>
{{out}}
<pre>
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
real 0m0.795s
user 0m0.794s
sys 0m0.000s
</pre>
| |||