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
|
#! /usr/bin/lua
-- from https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists#Lua
-- support:
function T(t) return setmetatable(t, {__index=table}) end
table.clone = function(t) local s=T{} for k,v in ipairs(t) do s[k]=v end return s end
table.reduce = function(t,f,acc) for i=1,#t do acc=f(t[i],acc) end return acc end
-- implementation:
local function cartesian(sets)
local temp, prod = T{}, T{}
local function descend(depth)
for _,v in ipairs(sets[depth]) do
temp[depth] = v
if (depth==#sets) then prod[#prod+1]=temp:clone() else descend(depth+1) end
end
end
descend(1)
return prod
end
function makingchange(a)
local coins = {1, 5, 10, 25, 50}
local pat = {}
for _, x in ipairs(coins) do
local max = math.floor(a / x)
if max > 0 then
local t = {}
for i = 0, max do
table.insert(t, i)
end
table.insert(pat, t)
else
break
end
end
local ct = 0
for _, combo in ipairs(cartesian(pat)) do
local t = 0
for i, c in ipairs(combo) do
t = t + c * coins[i]
if t > a then
break
end
end
if t == a then
ct = ct + 1
end
end
return ct
end
if makingchange(9) == 2 then
io.write("Pass")
else
io.write("FAIL")
end
io.write(" ")
if makingchange(15) == 6 then
io.write("Pass")
else
io.write("FAIL")
end
io.write(" ")
if makingchange(100) == 292 then
io.write("Pass")
else
io.write("FAIL")
end
print("")
|
