-
Notifications
You must be signed in to change notification settings - Fork 0
/
day07.mod
115 lines (108 loc) · 3.12 KB
/
day07.mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
MODULE Day07;
(*
Day #7: nice tree search...
- had to carefully adjust the record size so that the input just fits in memory!!!
- reading the input in two passes because of forward references
*)
IMPORT Texts,Strings;
CONST N=1098;
TYPE Cell = RECORD (* 28 bytes *)
name : ARRAY [0..7] OF CHAR;
weight : LONGINT;
nbSons : CARDINAL;
sons : ARRAY [1..7] OF CARDINAL;
END;
VAR cells : ARRAY [1..N] OF Cell;
node : CARDINAL;
PROCEDURE FindName(name : ARRAY OF CHAR) : CARDINAL;
VAR i : CARDINAL;
EXCEPTION NameNotFound;
BEGIN
FOR i:=1 TO N DO
IF name=cells[i].name THEN RETURN i END;
END;
RAISE NameNotFound;
END FindName;
PROCEDURE Parent(node : CARDINAL) : CARDINAL;
VAR i, n : CARDINAL;
BEGIN
FOR i:=1 TO N DO
FOR n:=1 TO cells[i].nbSons DO
IF cells[i].sons[n]=node THEN RETURN i END;
END;
END;
RETURN 0;
END Parent;
PROCEDURE Weight(node : CARDINAL) : LONGINT;
VAR i : CARDINAL;
sum : LONGINT;
BEGIN
sum := cells[node].weight;
FOR i:=1 TO cells[node].nbSons DO
sum := sum + Weight(cells[node].sons[i]);
END;
RETURN sum;
END Weight;
PROCEDURE SearchUnbalanced(node : CARDINAL);
VAR i, j, nbSons, nbDiffs, son, brother : CARDINAL;
weights : ARRAY [1..7] OF LONGINT;
BEGIN
nbSons := cells[node].nbSons;
IF nbSons <> 0 THEN
FOR i:=1 TO nbSons DO weights[i]:=Weight(cells[node].sons[i]) END;
FOR i:=1 TO nbSons DO
nbDiffs := 0;
FOR j:=1 TO nbSons DO
IF weights[i] <> weights[j] THEN INC(nbDiffs) END
END;
IF nbDiffs > 1 THEN
son := cells[node].sons[i];
brother := 1;
IF i=1 THEN brother:=2 END;
WRITELN(cells[son].name,' is unbalanced, and weights ',weights[i],' instead of ',weights[brother]);
SearchUnbalanced(son);
RETURN
END;
END;
END;
WRITELN('All sons of ',cells[node].name,' are balanced, and its own weight is ',cells[node].weight);
END SearchUnbalanced;
PROCEDURE ReadData;
VAR n, length, nbSons : CARDINAL;
input : Texts.TEXT;
dummy : CHAR;
name : ARRAY [0..7] OF CHAR;
EXCEPTION FileNotFound;
BEGIN
IF NOT Texts.OpenText(input,"DAY07.IN") THEN RAISE FileNotFound END;
FOR n:=1 TO N DO
Texts.ReadString(input,cells[n].name);
Texts.ReadLn(input);
END;
Texts.CloseText(input);
IF NOT Texts.OpenText(input,"DAY07.IN") THEN RAISE FileNotFound END;
FOR n:=1 TO N DO
Texts.ReadString(input,name);
Texts.ReadChar(input,dummy); (* left parenthesis *)
Texts.ReadLong(input,cells[n].weight); (* ReadLong reads until the next whitespace! *)
nbSons := 0;
IF NOT Texts.EOLN(input) THEN
Texts.ReadString(input,name); (* '->' *)
WHILE NOT Texts.EOLN(input) DO
INC(nbSons);
Texts.ReadString(input,name);
length := Strings.Length(name);
IF name[length-1]=',' THEN name[length-1]:=0C END;
cells[n].sons[nbSons] := FindName(name);
END;
END;
cells[n].nbSons := nbSons;
END;
END ReadData;
BEGIN
ReadData;
node := 1;
WHILE Parent(node)<>0 DO node:=Parent(node) END;
WRITELN('Root : ',cells[node].name);
SearchUnbalanced(node);
END Day07.