5 typedef struct List List;
7 struct List { List* next; };
13 // It may be necessary to tinker with this value to keep rand() within
15 const int modifier = 16;
16 int a = rand() >> modifier,b = rand() >> modifier;
18 // a must be less than or equal to b
27 List* current = malloc(sizeof(List));
31 for(int i = 0; i < b; i++)
33 current->next = malloc(sizeof(List));
34 current = current->next;
36 if(i == a) cycle = current;
39 current->next = cycle;
44 // TODO Implement a function that frees the cycled list.
46 size_t tortoiseAndHare(List* list)
50 List* tortoise = list;
58 if(hare == NULL) return 0;
59 else if(tortoise == hare) return count;
62 if(hare == NULL) return 0;
63 else if(tortoise == hare) return count;
65 tortoise = tortoise->next;
69 size_t teleportingTurtle(List* list)
79 for(int i = 0; i < patience; i++)
83 rabbit = rabbit->next;
84 if(rabbit == NULL) return 0;
85 else if(turtle == rabbit) return count;
87 rabbit = rabbit->next;
88 if(rabbit == NULL) return 0;
89 else if(turtle == rabbit) return count;
91 turtle = turtle->next;
94 patience = patience << 1;
95 turtle = rabbit; // TELEPORT!
99 // TODO Instead of counting steps, take the time.
100 // TODO Research how to detect where the cycle starts (and if it is useful).
105 size_t th, thtotal = 0, tt, tttotal = 0;
107 for(int i = 0; i < limit; i++)
109 printf("Generating racetrack.\n");
110 List* cycle = generateCycle();
112 printf("Racing tortoise vs. hare.\n");
113 th = tortoiseAndHare(cycle);
115 printf("Racing teleporting turtle vs. rabbit.\n");
116 tt = teleportingTurtle(cycle);
122 printf("Tortoise and hare: %i\n",thtotal / limit);
123 printf("Teleporting turtle: %i\n",tttotal / limit);