A fun problem: given a menu with items and associated costs, and some desired combination of items, find the optimal choice of items on the menu to minimize the total cost. This is an optimization problem for which we may use boolean satisfiability. This solution is brute force, and there are clearly some optimizations one could take. In any cas…

menuPicker.go

// menupicker.go
package main

import (
	"fmt"
	"strconv"
	"strings"
)

const MAX_COST = 1 << 20

type MenuItem struct {
	item string
	cost int
}

func (m MenuItem) String() string {
	return fmt.Sprintf("{%v: %v}", m.item, m.cost)
}

func (v *MenuItem) satisfies(desire string) bool {
	return strings.ContainsAny(desire, v.item)
}

func (v *MenuItem) satisfy(desire string) string {
	items := strings.Split(v.item, "")
	for _, p := range items {
		desire = strings.Replace(desire, p, "", 1)
	}
	return desire
}

func findMinCombo(desire string, menu []*MenuItem, index int) ([]*MenuItem, int) {
	//test if the desire has been met
	if desire == "" {
		fmt.Println("desire fulfilled at index", index)
		return make([]*MenuItem, 0, len(desire)), 0
	}
	//test if no more items to inspect
	if index >= len(menu) {
		fmt.Println("Desire unrequited at index", index)
		return nil, MAX_COST
	}

	item := menu[index]
	fmt.Printf("try leaving %v out\n", item)
	orderLeave, costLeave := findMinCombo(desire, menu, index+1)
	fmt.Printf("Cost if leaves %v: %v\n", item, costLeave)

	//can the current item satisfy any part of the desire? if so, try adding it
	fmt.Println("try taking ", item)
	orderTake, costTake := make([]*MenuItem, 0), MAX_COST
	if item.satisfies(desire) {
		orderTake, costTake = findMinCombo(item.satisfy(desire), menu, index+1)
	}
	costTake += item.cost
	fmt.Printf("Cost if takes %v: %v\n", item, costTake)

	if costTake < costLeave {
		fmt.Printf("cost of taking %v is less\n", item)
		return append(orderTake, item), costTake
	}
	//else
	fmt.Printf("Cost of leaving %v is less\n", item)
	return orderLeave, costLeave
}

func FindMinCombo(desire string, menu []*MenuItem) ([]*MenuItem, int) {
	return findMinCombo(desire, menu, 0)
}

func MakeMenu(menuString string) []*MenuItem {
	menuItems := strings.Split(menuString, ", ")
	menu := make([]*MenuItem, len(menuItems))
	for i, v := range menuItems {
		parts := strings.Split(v, ":")
		cost, _ := strconv.ParseInt(strings.TrimSpace(parts[1]), 10, 32)
		item := &MenuItem{strings.TrimSpace(parts[0]), int(cost)}
		menu[i] = item
	}
	return menu
}

func main() {
	menu := MakeMenu("A: 2, B: 3, C: 7, AB: 4, BC: 9, AC: 10")
	desire := "ABC"

	fmt.Println("Menu: ", menu)
	fmt.Println("Desire: ", desire)

	order, cost := FindMinCombo(desire, menu)
	fmt.Println("cost: ", cost)
	fmt.Println("Best combo:")
	for _, v := range order {
		fmt.Println(v)
	}

}