blob: 84bbab63bcbd17eef5fc50258283558f8b4a5dc3 (
plain)
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
%!PS
% begin included library code
% see https://codeberg.org/Firedrake/postscript-libraries/
/map { % array proc -> array
2 dict begin
/p exch def
[ exch
{
p
} forall
]
end
} bind def
/cartesianproduct { % [ [ a b ] [ c d ] ] -> [ [ a c ] [ a d ] [ b c ] [ b d ] ]
5 dict begin
/pat exch def
/c [ pat length { 0 } repeat ] def
/cm [ pat { length 1 sub } forall ] def
/ex false def
[
{
ex {
exit
} if
[
0 1 c length 1 sub {
/i exch def
pat i get c i get get
} for
]
/ss c length 1 sub def
{
c ss c ss get 1 add put
c ss get cm ss get gt {
ss 0 eq {
/ex true def
exit
} if
c ss 0 put
/ss ss 1 sub def
} {
exit
} ifelse
} loop
} loop
end
]
} bind def
/test {
/test.count test.count 1 add def
{
/test.pass test.pass 1 add def
} {
( ) print
test.count (....) cvs print
(-fail) print
} ifelse
} bind def
/test.end {
( ) print
test.count 0 gt {
(Passed ) print
test.pass (...) cvs print
(/) print
test.count (...) cvs print
( \() print
test.pass 100 mul test.count idiv (...) cvs print
(%\)) print
(\r\n) print
} if
} bind def
/enumerate.array {
1 dict begin
/a exch def
[
0 1 a length 1 sub {
[ exch dup a exch get ]
} for
]
end
} bind def
/test.start {
print (:) print
/test.pass 0 def
/test.count 0 def
} bind def
% end included library code
/makingchange {
0 dict begin
/a exch def
/coins [ 1 5 10 25 50 ] def
/mx coins { a exch idiv } map def
/pat [
0 1 coins length 1 sub {
/i exch def
mx i get 0 gt {
[ 0 1 mx i get {} for ]
} {
exit
} ifelse
} for
] def
0
pat cartesianproduct {
/combo exch def
/t 0 def
combo enumerate.array {
aload pop
/c exch def
/i exch def
/t c coins i get mul t add def
t a gt {
exit
} if
} forall
t a eq {
1 add
} if
} forall
end
} bind def
(makingchange) test.start
9 makingchange 2 eq test
15 makingchange 6 eq test
% 100 makingchange 292 eq test
test.end
|
