treasure.go

treasure.go

//google.com/+robertking

//One of my favorite code jam problems.
//solution to the Treasure problem from google code jam 2013:
//https://code.google.com/codejam/contest/dashboard?c=2270488#s=p3
//also wrote a solution in python: https://gist.github.com/robert-king/11139975

package main

import (
	"fmt"
	"container/list"
)

var chests *list.List
var keys Keys
var result []int

func main() {
	var T int
	fmt.Scan(&T)
	for i := 1; i <= T; i++ {
		var K, N int
		fmt.Scan(&K)
		fmt.Scan(&N)
		keys = make(Keys)
		enough_keys := make(Keys)
		chests = list.New()
		result = nil
		for k := 0; k < K; k++ {
			var key Key
			fmt.Scan(&key)
			keys[key]++
		}
		for n := 0; n < N; n++ {
			chest := Chest{}
			fmt.Scan(&chest.key)
			chest.idx = n + 1
			chest.keys = make(Keys)
			enough_keys[chest.key]++
			var L int
			fmt.Scan(&L)
			for l := 0; l < L; l++ {
				var k Key
				fmt.Scan(&k)
				chest.keys[k]++
				enough_keys[k]--
			}
			chests.PushBack(chest)
		}
		has_enough := true
		for key, count := range enough_keys {
			if count > keys[key] {
				has_enough = false
				break
			}
		}
		fmt.Printf("Case #%d:", i)
		if has_enough && can_solve() {
			for _, v := range result {
				fmt.Print(" ")
				fmt.Print(v)
			}
		} else {
			fmt.Print(" IMPOSSIBLE")
		}
		fmt.Println("")


	}
}

func can_solve() bool {
	for e := chests.Front(); e != nil; e = e.Next() {
		chest := e.Value.(Chest)
		if keys[chest.key] > 0  &&  will_stay_connected(chest) {
			keys[chest.key] -= 1
			keys.add_keys_from(chest)
			chests.Remove(e)
			result = append(result, chest.idx)
			can_solve()
			return true
		}
	}
	return false
}


func will_stay_connected(chest Chest) bool {
	needed := make(map[Key]bool)
	fringe := make(map[Key]bool)
	key_keys := make(map[Key]map[Key]bool) //keys accessible by key by opening chests
	for k := range keys {
		fringe[k] = true
	}
	for e := chests.Front(); e != nil; e = e.Next() {
		c := e.Value.(Chest)
		if c.idx != chest.idx {
			needed[c.key] = true
			_, has := key_keys[c.key]
			if !has {
				key_keys[c.key] = make(map[Key]bool)
			}
			for k := range c.keys {
				key_keys[c.key][k] = true
			}
		}
	}
	if keys[chest.key] == 1 {
		delete(fringe, chest.key)
	}
	for k := range chest.keys {
		fringe[k] = true
	}
	for k := range fringe {
		delete(needed, k)
	}
	for len(needed) > 0 {
		new_fringe := make(map[Key]bool)
		for k := range fringe {
			for k2 := range key_keys[k] {
				if needed[k2] {
					new_fringe[k2] = true
					delete(needed, k2)
				}
			}
		}
		if len(new_fringe) > 0 {
			fringe = new_fringe
		} else {
			if len(needed) == 0 {
				return true
			}
			return false
		}
	}
	return true
}

type Chest struct {
	idx int //chest index
	key Key //key type needed to open the chest
	keys Keys //keys inside the chest
}

func (keys Keys) add_keys_from(chest Chest) {
	for key, count := range chest.keys {
		keys[key] += count
	}
}

type Keys map[Key]int

type Key uint16