/
day17.go
98 lines (87 loc) · 2.53 KB
/
day17.go
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
package aoc2015
import (
"strconv"
"sync"
aoc "github.com/janreggie/aoc/internal"
"github.com/pkg/errors"
)
// eggnog represents an amount of eggnog.
type eggnog uint
// containerCount represents a number of containers
type containerCount uint
// contain tries to contain some amount of eggnog into containers
// that can hold a variable amount of eggnog
// and returns the number of possibilities.
func contain(amount eggnog, containers []eggnog) containerCount {
if amount < 0 {
return 0
}
if amount == 0 {
return 1 // there is only one arrangement: store nothing into no containers!
}
if len(containers) == 0 {
return 0 // there are no containers to store them to
}
return contain(amount, containers[1:]) + contain(amount-containers[0], containers[1:])
}
// containOnlyIn contains an amount of eggnog using only a set limit of containers
// and returns the number of possible ways this can be done.
func containOnlyIn(amount eggnog, limit containerCount, containers []eggnog) containerCount {
if amount < 0 {
return 0
}
if amount == 0 {
return 1 // there is only one arrangement: store nothing into no containers!
}
if len(containers) == 0 || limit == 0 {
return 0 // there are no containers to store them to
}
return containOnlyIn(amount-containers[0], limit-1, containers[1:]) +
containOnlyIn(amount, limit, containers[1:])
}
// Day17 solves the seventeenth day puzzle "No Such Thing as Too Much".
//
// Input
//
// A file containing 20 lines each of which describes
// a container and how much it contains.
// For example:
//
// 50
// 44
// 11
// 49
// 42
//
// There are no guarantees that the list in the input containers have been
// sorted. All containers should be non-negative integers no more than 150.
func Day17(input string) (answer1, answer2 string, err error) {
containers := make([]eggnog, 0)
for _, line := range aoc.SplitLines(input) {
size, e := strconv.ParseUint(line, 0, 32)
if e != nil {
err = errors.Wrapf(e, "could not parse %q", line)
return
}
containers = append(containers, eggnog(size))
}
var wg sync.WaitGroup
wg.Add(2)
go func() {
answer1 = strconv.FormatUint(uint64(contain(150, containers)), 10)
wg.Done()
}()
// now determine the least amount...
// This is a lazy solution and just iterates ii until we found an answer.
go func() {
for ii := containerCount(0); ii < containerCount(len(containers)); ii++ {
if counted := containOnlyIn(150, ii, containers); counted > 0 {
answer2 = strconv.FormatUint(uint64(counted), 10)
break
}
}
wg.Done()
}()
wg.Wait()
return
}