code.kerkeslager.com Git - sandbox/blob - cycles.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4
   5 typedef struct List List;
   6
   7 struct List { List* next; };
   8
   9 List* generateCycle()
  10 {
  11         srand(time(NULL));
  12
  13         // It may be necessary to tinker with this value to keep rand() within
  14         // reasonable bounds.
  15         const int modifier = 16;
  16         int a = rand() >> modifier,b = rand() >> modifier;
  17
  18         // a must be less than or equal to b
  19         if(a > b)
  20         {
  21                 int t = a;
  22                 a = b;
  23                 b = t;
  24         }
  25
  26         List* cycle;
  27         List* current = malloc(sizeof(List));
  28
  29         List* r = current;
  30
  31         for(int i = 0; i < b; i++)
  32         {
  33                 current->next = malloc(sizeof(List));
  34                 current = current->next;
  35
  36                 if(i == a) cycle = current;
  37         }
  38
  39         current->next = cycle;
  40
  41         return r;
  42 }
  43
  44 // TODO Implement a function that frees the cycled list.
  45
  46 size_t tortoiseAndHare(List* list)
  47 {
  48         size_t count = 0;
  49
  50         List* tortoise = list;
  51         List* hare = list;
  52
  53         while(1)
  54         {
  55                 count++;
  56
  57                 hare = hare->next;
  58                 if(hare == NULL) return 0;
  59                 else if(tortoise == hare) return count;
  60
  61                 hare = hare->next;
  62                 if(hare == NULL) return 0;
  63                 else if(tortoise == hare) return count;
  64
  65                 tortoise = tortoise->next;
  66         }
  67 }
  68
  69 size_t teleportingTurtle(List* list)
  70 {
  71         size_t count = 0;
  72
  73         List* turtle = list;
  74         List* rabbit = list;
  75         int patience = 1;
  76
  77         while(1)
  78         {
  79                 for(int i = 0; i < patience; i++)
  80                 {
  81                         count++;
  82
  83                         rabbit = rabbit->next;
  84                         if(rabbit == NULL) return 0;
  85                         else if(turtle == rabbit) return count;
  86
  87                         rabbit = rabbit->next;
  88                         if(rabbit == NULL) return 0;
  89                         else if(turtle == rabbit) return count;
  90
  91                         turtle = turtle->next;
  92                 }
  93
  94                 patience = patience << 1;
  95                 turtle = rabbit;                        // TELEPORT!
  96         }
  97 }
  98
  99 // TODO Instead of counting steps, take the time.
 100 // TODO Research how to detect where the cycle starts (and if it is useful).
 101
 102 int main()
 103 {
 104         int limit = 256;
 105         size_t th, thtotal = 0, tt, tttotal = 0;
 106
 107         for(int i = 0; i < limit; i++)
 108         {
 109                 printf("Generating racetrack.\n");
 110                 List* cycle = generateCycle();
 111
 112                 printf("Racing tortoise vs. hare.\n");
 113                 th = tortoiseAndHare(cycle);
 114
 115                 printf("Racing teleporting turtle vs. rabbit.\n");
 116                 tt = teleportingTurtle(cycle);
 117
 118                 thtotal += th;
 119                 tttotal += tt;
 120         }
 121
 122         printf("Tortoise and hare: %i\n",thtotal / limit);
 123         printf("Teleporting turtle: %i\n",tttotal / limit);
 124 }