15 puzzle solver: Difference between revisions
Content added Content deleted
No edit summary |
(→{{header|C++}}: Imperative solution < 1 sec) |
||
Line 35: | Line 35: | ||
</pre> |
</pre> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
===Staying Functional (as possible in C++)=== |
|||
===The Solver=== |
|||
====The Solver==== |
|||
{{trans|FSharp}} |
{{trans|FSharp}} |
||
<lang cpp> |
<lang cpp> |
||
Line 107: | Line 108: | ||
</lang> |
</lang> |
||
===The Task=== |
====The Task==== |
||
<lang cpp> |
<lang cpp> |
||
int main (){ |
int main (){ |
||
Line 121: | Line 122: | ||
user 0m2.887s |
user 0m2.887s |
||
sys 0m0.008s |
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> |
</pre> |
||