-
Notifications
You must be signed in to change notification settings - Fork 2
/
cutlist.go
159 lines (129 loc) · 3.03 KB
/
cutlist.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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
package main
import (
"fmt"
"log"
"math/rand"
"os"
"sort"
"strconv"
"strings"
"time"
)
func main() {
stockLength, parts := parseInputs()
fmt.Println("stock length:", stockLength)
fmt.Println(len(parts), "parts")
// try out a lot of random variants of arranging the parts into stock pieces
variants := tryVariants(stockLength, parts)
// the variant with the least amount of offcut is the winner
best, offcut := findBest(stockLength, variants)
printList(stockLength, best)
fmt.Println("total offcut:", offcut)
}
func parseInputs() (stockLength int, parts []int) {
if len(os.Args) < 2 {
log.Fatal("need args")
}
stockLength, err := strconv.Atoi(os.Args[1])
if err != nil {
log.Fatal(err)
}
// parse all parts
for _, v := range os.Args[2:] {
args := strings.Split(v, "x")
if len(args) != 2 {
log.Fatal("argument error:", v)
}
count, err := strconv.Atoi(args[0])
if err != nil {
log.Fatal(err)
}
length, err := strconv.Atoi(args[1])
if err != nil {
log.Fatal(err)
}
for i := 0; i < count; i++ {
parts = append(parts, length)
}
}
return stockLength, parts
}
// brute-force all parts into the stock
// computing time is cheaper than brain time for a one-time computation
func tryVariants(stockLength int, parts []int) [][][]int {
var variants [][][]int
for i := 0; i < 100000; i++ {
// randomize parts order
shuffle(parts)
var stocks [][]int
stock := []int{}
sum := 0
for _, p := range parts {
// if the part doesn't fit, start a new stock
if sum+p >= stockLength {
stocks = append(stocks, stock)
stock = []int{}
sum = 0
}
// add the part to stock
stock = append(stock, p)
sum += p
}
// append the last stock piece - this won't be full
stocks = append(stocks, stock)
// pile up all the variants
variants = append(variants, stocks)
}
return variants
}
// shuffle elements of a slice randomly
func shuffle(in []int) {
rand.Seed(time.Now().UnixNano())
for i := range in {
j := rand.Intn(len(in))
in[i], in[j] = in[j], in[i]
}
}
func findBest(stockLength int, variants [][][]int) (best [][]int, offcut int) {
minOffcut := stockLength
for _, v := range variants {
// if all the parts fit on one stock piece, we can't do any better
if len(v) < 2 {
best = v
break
}
// use all but the last stock piece for offcut calculation
c := v[:len(v)-1]
totalOffcut := 0
// calculate offcut for every stock piece
for _, s := range c {
// sum of parts in stock piece
sum := 0
for _, p := range s {
sum += p
}
offcut := stockLength - sum
totalOffcut += offcut
}
// less offcut is more better :)
if totalOffcut < minOffcut {
minOffcut = totalOffcut
best = v
}
}
return best, minOffcut
}
// finally print that perfect cut list
func printList(stockLength int, list [][]int) {
fmt.Println("cut list:")
for i, s := range list {
sort.Ints(s)
fmt.Println("stock", i+1)
offcut := stockLength
for _, p := range s {
offcut -= p
fmt.Printf(" %d", p)
}
fmt.Printf("\n offcut %d\n", offcut)
}
}