Donald Knuths vennlige troll med lamper i den ene neven – rekursiv implementasjon

Det er mye rart man finner når man går gjennom gamle filer. Her er litt programkode som jeg knotta inn for 10 år siden. Denne fila var opprinnelig datert 4. januar 2003.

Her er link til artikkelen: http://www-cs-faculty.stanford.edu/~knuth/papers/p160.ps.gz.

/*
 rek-troll.c -- En rekursiv implementasjon av Donald Knuths
                vennlige troll med lamper i den ene neven.

 Se Donald E. Knuth og Frank Ruskeys artikkel som tidligere het
 "Deconstructing Coroutines", men som nå har fått tittelen
 "Efficient Coroutine Generation of Constrained Gray Sequences".
 Artikkelen er tilgjengelig på:
 http://www-cs-faculty.stanford.edu/~knuth/papers/p160.ps.gz.

 Copyright © 2003 Trond Endrestøl <Trond.Endrestol@ximalas.info>

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 MA 02111-1307, USA.
*/
#include <sys/time.h>

#include <stdio.h>
#include <unistd.h>

#ifndef N
#define N 8
#endif

enum bool_t { false, true } Vaken[N], Lampe[N];

/* Ting og tang i forbindelse med tidsstempling. */
struct timeval Starttid;

void InitTiming(void)
{
  gettimeofday(&Starttid, NULL);
} /* InitTiming */

double Timing(void)
{
  struct timeval MinTid;
  double Tidsstempel;

  gettimeofday(&MinTid, NULL);

  Tidsstempel = MinTid.tv_sec + (MinTid.tv_usec / 1.0E6);
  Tidsstempel -= Starttid.tv_sec + (Starttid.tv_usec / 1.0E6);

  /* Bruk formatet %.6f eller %.6g
     siden presisjonen bare er i hele mikrosekunder. */

  return Tidsstempel;
} /* Timing */

void SkrivStatus(void)
{
  size_t i;
  double Tidsstempel = Timing();

  /* Skrive ut status for hvert troll. */
#if 0 /* Skrive ut trollene forlengs. */
  for (i = 0; i < N; i++) {
    printf("Troll(%u):%.6f: %s, lampa er %s\n",
           i,
           Tidsstempel,
           (Vaken[i]) ? "våken" : "sover",
           (Lampe[i]) ? "på"    : "av");
    } /* for */
#else /* Skrive ut trollene baklengs. */
  i = N - 1;
  do {
    printf("Troll(%u):%.6f: %s, lampa er %s\n",
           i,
           Tidsstempel,
           (Vaken[i]) ? "våken" : "sover",
           (Lampe[i]) ? "på"    : "av");
    } while (i--); /* do-while */
#endif

  /* Skrive ut en vakker skillelinje. */
  puts("----");

  /* Tvinge buffret output på stdout ut på skjermen. */
  fflush(stdout);
} /* SkrivStatus */

void Troll(size_t i)
{
  if (Vaken[i]) { /* Jeg er våken. */
    Lampe[i] = !Lampe[i]; /* Skru på eller av lampa. */
    Vaken[i] = false; /* Sovne på grunn av overanstrengelse. */

    /* Mirakuløst klarer likevel dette trollet å fortelle
       omverdenen om tilstanden til alle trollene. */
    SkrivStatus();
    } /* if */
  else { /* Jeg sover. */
    Vaken[i] = true; /* Våkne opp. */

    if (i != 0) { /* Signalere naboen med mindre jeg er Troll(0). */
      Troll(i - 1);
      } /* if */
    else { /* Skrive status siden jeg er Troll(0). */
      SkrivStatus();
      } /* else */
    } /* else */
} /* Troll */

int main(void)
{
  size_t i;

  InitTiming();

  /* Initialisere arrayene. */
  for (i = 0; i < N; i++) {
    Vaken[i] = true;
    Lampe[i] = false;
    } /* for */

  /* Skrive ut den innledende tilstanden til trollene. */
  SkrivStatus();

  /* Holde simuleringen i gang. */
  while (1) {
    /* Signalere Troll(N - 1). */
    Troll(N - 1);

    /* Sove litt, ellers rekker vi ikke å følge med på skjermen. */
    sleep(1);
    } /* while */

  /* NOTREACHED */
  return 0;
} /* main */

/* rek-troll.c */

Her er et utdrag fra en runde med simulering:

----
Troll(7):508.507796: sover, lampa er på
Troll(6):508.507796: våken, lampa er på
Troll(5):508.507796: sover, lampa er av
Troll(4):508.507796: sover, lampa er av
Troll(3):508.507796: sover, lampa er av
Troll(2):508.507796: sover, lampa er av
Troll(1):508.507796: sover, lampa er av
Troll(0):508.507796: sover, lampa er av
----
Troll(7):509.508798: våken, lampa er på
Troll(6):509.508798: sover, lampa er av
Troll(5):509.508798: sover, lampa er av
Troll(4):509.508798: sover, lampa er av
Troll(3):509.508798: sover, lampa er av
Troll(2):509.508798: sover, lampa er av
Troll(1):509.508798: sover, lampa er av
Troll(0):509.508798: sover, lampa er av
----
Troll(7):510.509799: sover, lampa er av
Troll(6):510.509799: sover, lampa er av
Troll(5):510.509799: sover, lampa er av
Troll(4):510.509799: sover, lampa er av
Troll(3):510.509799: sover, lampa er av
Troll(2):510.509799: sover, lampa er av
Troll(1):510.509799: sover, lampa er av
Troll(0):510.509799: sover, lampa er av
----
Troll(7):511.510793: våken, lampa er av
Troll(6):511.510793: våken, lampa er av
Troll(5):511.510793: våken, lampa er av
Troll(4):511.510793: våken, lampa er av
Troll(3):511.510793: våken, lampa er av
Troll(2):511.510793: våken, lampa er av
Troll(1):511.510793: våken, lampa er av
Troll(0):511.510793: våken, lampa er av
----
Troll(7):512.511793: sover, lampa er på
Troll(6):512.511793: våken, lampa er av
Troll(5):512.511793: våken, lampa er av
Troll(4):512.511793: våken, lampa er av
Troll(3):512.511793: våken, lampa er av
Troll(2):512.511793: våken, lampa er av
Troll(1):512.511793: våken, lampa er av
Troll(0):512.511793: våken, lampa er av
----
Troll(7):513.512799: våken, lampa er på
Troll(6):513.512799: sover, lampa er på
Troll(5):513.512799: våken, lampa er av
Troll(4):513.512799: våken, lampa er av
Troll(3):513.512799: våken, lampa er av
Troll(2):513.512799: våken, lampa er av
Troll(1):513.512799: våken, lampa er av
Troll(0):513.512799: våken, lampa er av
----