pebbles.a68
1 COMMENT
2
3 @section Synopsis
4
5 Edsger Dijkstra's pebble problem.
6
7 This program originates from the legacy "REVISED MC ALGOL 68 TEST SET":
8
9 Dick Grune, The Revised MC ALGOL 68 Test Set, IW XX/79,
10 Mathematical Centre, Amsterdam.
11
12 The Mathematical Centre ("Stichting Mathematisch Centrum" or SMC) was a Dutch
13 non-profit institution aiming at the promotion of pure mathematics and its
14 applications.
15
16 SMC is now "Stichting Centrum Wiskunde & Informatica" (CWI). The test set
17 is available as an open access publication from the CWI repository:
18
19 https://ir.cwi.nl/pub/
20
21 Selected (modified) "Revised MC ALGOL 68 Test Set" programs are distributed
22 with Algol 68 Genie with kind permission of Dick Grune.
23
24 COMMENT
25
26 BEGIN # 1. Sets in ALGOL 68;
27 2. Pebble problem of E.W. Dijkstra
28 #
29
30 MODE RED = REF STRUCT (RED red),
31 WHITE = REF STRUCT (WHITE white),
32 BLUE = REF STRUCT (BLUE blue);
33
34 MODE STONE = UNION (RED, WHITE, BLUE);
35
36 PROC sort = (REF [] STONE st) VOID:
37 (INT pr := 1, pw := 1, pb := UPB st;
38
39 PRIO EXCH = 1;
40 OP EXCH = (REF STONE a, b) VOID: (STONE c = b; b := a; a := c);
41
42 TO UPB st
43 DO CASE st[pw]
44 IN (RED): (st[pr] EXCH st[pw]; pr +:= 1; pw +:= 1),
45 (WHITE): pw +:= 1,
46 (BLUE): (st[pw] EXCH st[pb]; pb -:= 1)
47 ESAC
48 OD
49 );
50
51 OP PRINT = (REF [] STONE st) VOID:
52 FOR i TO UPB st
53 DO print ((st[i] | (RED): "r", (WHITE): "w", (BLUE): "b"))
54 OD;
55
56 INT n = 20;
57 [1 : n] STONE stone;
58
59 FOR i TO UPB stone
60 DO stone[i] := (ENTIER (random * 3) + 1 | RED (NIL), WHITE (NIL), BLUE (NIL))
61 OD;
62
63 PRINT stone;
64 newline (standout);
65 sort (stone);
66 PRINT stone;
67 newline (standout)
68
69 END
