Skip to content

Instantly share code, notes, and snippets.

@edw
Last active July 8, 2020 14:49
Show Gist options
  • Save edw/e67ce76b80555cea7b87d0018d13e910 to your computer and use it in GitHub Desktop.
Save edw/e67ce76b80555cea7b87d0018d13e910 to your computer and use it in GitHub Desktop.
Coins solutions
package main
import "fmt"
func main() {
fmt.Printf("%d\n", iter(36, []int{25, 10, 5, 1})) // descending order, reverse of naive.
}
type Cache map[string]int
func (c Cache) Put(n int, coins []int, v int) {
c[fmt.Sprintf("%d %v", n, coins)] = v
// fmt.Println("put")
}
func (c Cache) Get(n int, coins []int) (int, bool) {
v, ok := c[fmt.Sprintf("%d %v", n, coins)]
// if ok {
// fmt.Printf("hit (%d, %v)\n", n, coins)
// } else {
// fmt.Printf("miss(%d, %v)\n", n, coins)
// }
return v, ok
}
var cache = make(Cache)
func iter(n int, coins []int) int {
if n == 0 {
return 1
}
if v, ok := cache.Get(n, coins); ok {
return v
}
if len(coins) == 1 {
if n%coins[0] == 0 {
cache.Put(n, coins, 1)
return 1
} else {
cache.Put(n, coins, 0)
return 0
}
}
c := coins[0]
accum := 0
for m:=n; m>=0; m -=c {
accum += iter(m, coins[1:])
}
cache.Put(n, coins, accum)
return accum
}
package main
import "fmt"
func main() {
fmt.Printf("%d\n", iter(10, []int{1, 5, 10, 25}))
}
type Combo []int
type ComboSet map[string]Combo
func (cs ComboSet) Add(c Combo) {
cs[fmt.Sprintf("%v", c)] = c
}
func (cs ComboSet) Elems() *[]Combo {
out := make([]Combo, len(cs))
i:=0
for _, c := range cs {
out[i] = c
i++
}
return &out
}
func iter(n int, coins []int) int {
nCoin := len(coins)
cache := make([]ComboSet, n+1)
for i:=0; i<=n; i++ {
cache[i] = make(ComboSet)
if i == 0 {
cache[i].Add(make(Combo, nCoin))
continue
}
for j, c := range coins {
if c > i {
break
}
for _, way := range *cache[i-c].Elems() {
combo := make(Combo, nCoin)
copy(combo, way)
combo[j]++
cache[i].Add(combo)
}
}
}
return len(cache[n])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment