CODE
go run pick8.go
Found it in 96181218 tries
2445
1572.19
2260.78
2270
1962.93
1514
2600
1004.24
Quick hack, sorry the messy stuff. Run time is
CODE
real 1m41.097s
user 2m17.709s
sys 0m7.243s
UPDATE: Doing things a little more intelligently and reducing the number of checks:CODE
go run pick8.go
Found it in 43369955 tries
1004.24
1572.19
1950
1951
2000
2190.93
2260.78
2700
real 0m18.630s
user 0m19.583s
sys 0m1.034s
(yes, there's more than one solution, and we just output the first one we see and get out -- we're not looking for optimal solutions ala knapsack)
https://gist.github.com/angch/ea9cea934ee8ca6cab6aAttachment contains the source, and binaries for Linux (64bit), OS X (64 bit), and Windows (64bit? dunno).
IPB messed up my formatting, use link above to preview properly.
CODE
// https://forum.lowyat.net/topic/3852732
// Quick and Dirty hack
// angch's go kata
// Original idea was to scale up and use Go channels, but we can't do
// priority queue that way.
package main
import (
"container/heap"
"fmt"
"sort"
)
// Current picks, and their sum so far
type Picks struct {
priority float32 // The priority of the item in the queue.
index int // The index of the item in the heap.
idx []int // Not to be confused with idx, which is a set of the items we picked
sum float32 // sum so far
}
// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Picks
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Picks)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}
func initTestItems() []float32 {
items := make([]float32, 0, 0)
items = append(items, 1.0)
items = append(items, 2.0)
items = append(items, 3.0)
items = append(items, 4.0)
items = append(items, 2.2)
items = append(items, 0.5)
items = append(items, 0.5)
return items
}
func initItems() []float32 {
i := []float64{20, 100, 500, 100, 100, 1900, 100.13, 200, 200, 300, 140, 100, 2700, 967.93, 100, 100, 4000, 100, 100, 100, 1000, 100, 200, 300, 100, 200, 100, 3000, 508.47, 20, 100, 100, 100, 100, 2445, 462.96, 195, 1000, 300, 100, 100, 20, 595.17, 250, 10, 10, 3000, 668, 113.29, 1374.68, 204.39, 697.98, 1572.19, 253, 500, 700, 500, 1100, 142.37, 2000, 475, 1850, 495, 2700, 2260.78, 500, 1270, 362.82, 1951, 444.03, 1460, 2700, 425, 2208.98, 2700, 500, 1950, 1400, 500, 2060, 2270, 1837, 2053, 751.63, 1000, 450, 1800, 1962.93, 465, 250, 2045, 300, 480, 462.87, 2470, 1514, 518.17, 3000, 2190.93, 2600, 500, 500, 500, 1004.24, 1625, 500, 2400, 2450, 780}
sort.Sort(sort.Float64Slice(i))
items := make([]float32, len(i))
for k, v := range i {
items[k] = float32(v)
}
return items
}
func search(items []float32, target float32, targetNumber int) {
checks := 0
// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
pq := make(PriorityQueue, len(items))
i := 0
for idx, number := range items {
priority := float32(0)
if target > number {
priority = number - target // yes, it's negative
}
pq[i] = &Picks{
priority: priority,
index: idx,
idx: []int{idx},
sum: number,
}
i++
checks++
}
heap.Init(&pq)
for pq.Len() > 0 {
picks := heap.Pop(&pq).(*Picks)
if picks.sum == target &&
len(picks.idx) == targetNumber {
fmt.Println("Found it in", checks, "tries")
for _, v := range picks.idx {
fmt.Println(items[v])
}
return
}
lastIdx := picks.idx[len(picks.idx)-1]
if len(picks.idx) >= targetNumber {
continue
}
for lastIdx++; lastIdx < len(items); lastIdx++ {
number := items[lastIdx]
priority := float32(0)
if target > number {
priority = number - target // yes, it's negative
}
if target < number {
continue
}
indices := make([]int, len(picks.idx)+1)
copy(indices, picks.idx)
indices[len(picks.idx)] = lastIdx
newPick := &Picks{
priority: priority,
idx: indices,
sum: picks.sum + number,
}
heap.Push(&pq, newPick)
checks++
}
}
fmt.Println("Give up after", checks, "tries")
}
func main() {
//items := initTestItems()
items := initItems()
//search(items, 5.0, 3)
search(items, 15629.14, 8)
}
This post has been edited by angch: Jan 26 2016, 10:52 PM Attached File(s)
pick8.zip ( 1.56mb )
Number of downloads: 2