Bir robot bir başlangıç noktasından hareketle, durduğu noktada dönmemek ve sonuçta aynı noktaya gelmek üzere, saat yönünde ya da saatin ters yönünde çizilen 1/5 lik tam açılar (72° lik yay) serisi şeklinde hareket ediyor.
Kuzeye dönük şekilde başlatılan 25 yaydan oluşan olası 70932 kapalı yoldan biri aşağıda veriliyor:
Kuzeye dönük şekilde duran bir robot, 70 yaydan oluşan kaç farklı kapalı yol izleyebilir?
Cevap: 331951449665644800
Java:
import java.util.Map;
import java.util.TreeMap;
public class Euler208 {
public class Path implements Comparable <Path>
{
// number of steps to take in each direction till at origin
public byte[] steps = new byte[5];
// direction, 0-4
public int rotation;
public Path(){}
public Path(Path p2){ set(p2); }
// compare function for map
public int compareTo(Path p2) {
if( rotation != p2.rotation ) return rotation - p2.rotation;
for( int i=0; i<5; i++ )
if( steps[i] != p2.steps[i] ) return steps[i] - p2.steps[i];
return 0;
}
// copy value from existing instance
public void set( Path p2 ){
for( int i=0; i<5; i++ )steps[i] = p2.steps[i];
rotation = p2.rotation;
}
// extend path by a left turn
public void growLeft(){
steps[rotation]--;
rotation = rotation==0 ? 4 : rotation-1;
reduce();
}
// extend path by a right turn
public void growRight(){
rotation = rotation==4 ? 0 : rotation+1;
steps[rotation]--;
reduce();
}
// keep all distance counts positive - add one step in each direction if not
private void reduce(){
if( steps[0]<0 || steps[1]<0 || steps[2]<0 || steps[3]<0 || steps[4]<0 )
{
++steps[0];
++steps[1];
++steps[2];
++steps[3];
++steps[4];
}
}
// check that can still solve it within d steps
public boolean solvableIn( int d ){
return d - (steps[0]+steps[1]+steps[2]+steps[3]+steps[4]) >= 0;
}
}
final int size = 70;
Euler208(){
// paths of current length, each type with a count number
Map <Path,Long> map1 = new TreeMap <Path, Long>();
// One path of zero length
map1.put(new Path(), 1L);
// lengthened paths
Map <Path,Long> map2 = new TreeMap <Path, Long>();
Path temp = new Path(); // temporary path instance
for( int i=0; i<size; i++ ){ // lengthen up to size times
// for each path
for (Map.Entry <Path,Long> pair : map1.entrySet() ) {
temp.set(pair.getKey());
// if solvable
if( temp.solvableIn(size-i)){
// extend it with left curve, and add to map2
temp.growLeft();
addPath( map2, temp, pair.getValue() );
// extend it with right curve, and add to map2
temp.set(pair.getKey());
temp.growRight();
addPath( map2, temp, pair.getValue() );
}
}
// clear out old length paths
map1.clear();
// swap maps, so that will next use longer paths
Map <Path,Long> map3 = map1;
map1 = map2;
map2 = map3;
System.out.println(map1.size());
}
// print result
long count = map1.get(new Path());
System.out.println("Total: "+count);
}
// Add c paths of type p to the map
private void addPath( Map <Path,Long> map, Path p, long c ){
Long old = map.get(p);
if( old ==null ){
map.put( new Path(p), c);
}else{
map.put( p, c+old );
}
}
} C++:#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.141592653589793238462643383
#define eps 1e-6
#define n 70
typedef struct
{
long long int offset;
long long int count;
}List;
int compare (const void* source, const void* dest)
{
List* listSource = (List*) source;
List* listDest = (List*) dest;
if((listSource->offset)>(listDest->offset)) return 1;
return -1;
}
double ABS(double x) {
if(x<0.0) return -x;
return x;
}
int main() {
int i,i2,I,NUM,j,dir,dir2,num,angle,angle2,A[5];
long long int offset,total,pow256[8];
double x,y;
List* myList;
List* myList2;
pow256[0]=1;
for(i=1;i<8;i++) pow256[i]=pow256[i-1]<<8;
myList=(List*)(malloc)(1*sizeof(List));
num=1;
myList[0].count=1;
myList[0].offset=2+127*pow256[2]+128*pow256[3]+128*pow256[4]+128*pow256[5]+128*pow256[6];
for(I=0;I<n;I++) {
myList2=(List*)(malloc)(2*num*sizeof(List));
for(i=0;i<num;i++) {
offset=myList[i].offset;
dir=(offset&255)-1;
offset>>=8;
angle=offset&255;
i2=i<<1;
angle2=(angle+2*dir+10)%10;
myList2[i2].offset=myList[i].offset+((angle2-angle)<<8);
myList2[i2].count=myList[i].count;
dir2=-dir;
angle2=(angle+5+2*dir2)%10;
myList2[i2+1].offset=myList[i].offset+(dir2-dir)+((angle2-angle)<<8);
if(angle<5) myList2[i2+1].offset+=2*pow256[angle+2];
else myList2[i2+1].offset-=2*pow256[angle+2-5];
myList2[i2+1].count=myList[i].count;
}
free(myList);
num<<=1;
qsort(myList2,num,sizeof(List),compare);
NUM=0;
for(i=1;i<num;i++) {
if(myList2[i].offset==myList2[NUM].offset) {
myList2[NUM].count+=myList2[i].count;
}
else {
NUM++;
myList2[NUM].offset=myList2[i].offset;
myList2[NUM].count=myList2[i].count;
}
}
num=NUM+1;
myList=(List*)(malloc)(num*sizeof(List));
for(i=0;i<num;i++) {
myList[i].offset=myList2[i].offset;
myList[i].count=myList2[i].count;
}
free(myList2);
}
total=0;
for(i=0;i<num;i++) {
offset=myList[i].offset;
dir=(offset&255)-1;
offset>>=8;
angle=offset&255;
for(j=0;j<5;j++) {
offset>>=8;
A[j]=(offset&255)-128;
}
if(angle<5) A[angle]++;
else A[angle-5]--;
x=0.0;
y=0.0;
for(j=0;j<5;j++) {
x+=(double) A[j]*cos((double) j*2.0*PI/10.0);
y+=(double) A[j]*sin((double) j*2.0*PI/10.0);
}
if((ABS(x)<eps)&&(ABS(y)<eps)) total+=myList[i].count;
}
printf("%I64d\n",total);
return 0;
} Basic:Public Class Euler208
Private Const Max As Long = 14
Private Mul(4) As Long
Private Const SPN = (Max + 1) ^ 5 - 1
Private R(4, SPN - 1) As Long
Private Sub Euler208_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load
Dim t As New System.Diagnostics.Stopwatch
t.Start()
Dim L As Long, I As Long
For L = 0 To (SPN - 1)
For I = 0 To 4
R(I, L) = -1
Next
Next
For I = 0 To 4
Mul(I) = (Max + 1) ^ I
Next
tResult.Text = Solve(0, 0)
Me.Text = "Solved Euler 208 in " & (t.ElapsedMilliseconds / 1000) & "s"
End Sub
Private Function Solve(ByVal Num As Long, ByVal d As Integer) As Long
If Num = SPN Then
If d = 0 Then Return 1 Else Return 0
End If
If R(d, Num) <> -1 Then Return R(d, Num)
Dim NumB As Long, I As Long, db As Integer
Solve = 0
For I = 4 To 6 Step 2
db = (d + I) Mod 5
If (Num \ Mul(db)) Mod Mul(1) < Max Then
NumB = Num + Mul(db)
Solve = Solve + Solve(NumB, db)
End If
Next
R(d, Num) = Solve
End Function
End Class Mathematica:n = 4;
Clear[F,x];
For[i=0,i<=n,i++,
e[i]=PadRight[CoefficientList[PolynomialRemainder[
x^i,Cyclotomic[n,x],x],x],EulerPhi@n];
];
zero=Array[0&,EulerPhi@n];
F[m_,A_,i_]:= F[m, A, i] = If[m==0,
If[A==zero && i==0, 1, 0],
Expand[x F[m-1,A+e[i+1],Mod[i+1,n]] + F[m-1,A+e[i],Mod[i-1,n]]]
]; Matlab:n=14;
nsteps=n*5;
npos=5;
nvec=zeros(npos,n+1,n+1,n+1,n+1,n+1);
nvec(1,2,1,1,1,1)=1;
for i=2:nsteps
nvecnew=zeros(npos,n+1,n+1,n+1,n+1,n+1);
for l=1:n
for j=1:npos
if j==1
nvecnew(j,l+1,:,:,:,:)=nvec(5,l,:,:,:,:);
nvecnew(j,l+1,:,:,:,:)=nvecnew(j,l+1,:,:,:,:)+nvec(j+1,l,:,:,:,:);
elseif j==2
nvecnew(j,:,l+1,:,:,:)=nvec(j-1,:,l,:,:,:);
nvecnew(j,:,l+1,:,:,:)=nvecnew(j,:,l+1,:,:,:)+nvec(j+1,:,l,:,:,:);
elseif j==3
nvecnew(j,:,:,l+1,:,:)=nvec(j-1,:,:,l,:,:);
nvecnew(j,:,:,l+1,:,:)=nvecnew(j,:,:,l+1,:,:)+nvec(j+1,:,:,l,:,:);
elseif j==4
nvecnew(j,:,:,:,l+1,:)=nvec(j-1,:,:,:,l,:);
nvecnew(j,:,:,:,l+1,:)=nvecnew(j,:,:,:,l+1,:)+nvec(j+1,:,:,:,l,:);
else
nvecnew(j,:,:,:,:,l+1)=nvec(j-1,:,:,:,:,l);
nvecnew(j,:,:,:,:,l+1)=nvecnew(j,:,:,:,:,l+1)+nvec(1,:,:,:,:,l);
end
end
end
nvec=nvecnew;
end
2*nvec(5,n+1,n+1,n+1,n+1,n+1)