boxes.go

// My solution to Reddit /r/dailyprogrammer challenge #200
// http://www.reddit.com/r/dailyprogrammer/comments/2v0tx4/20150206_challenge_200_hard_box_in_a_box/

package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"sort"
	"time"
)

type Box struct {
	w, h, d int
}

func (b Box) FitsInside(other Box) bool {
	return b.w <= other.w && b.h <= other.h && b.d <= other.d
}

type BoxList []Box

func (bl BoxList) String() string {
	s := ""
	for _, box := range bl {
		s += fmt.Sprintf("%d, %d, %d\n", box.w, box.h, box.d)
	}
	return s
}

// Random sorting for the BoxList
func (l BoxList) Len() int           { return len(l) }
func (l BoxList) Less(i, j int) bool { return rand.Float64() < rand.Float64() }
func (l BoxList) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }

func Run(w, h, d int, src BoxList, res chan BoxList) {
	// Clone boxes
	boxes := make(BoxList, len(src))
	copy(boxes, src)

	for {
		// Setup containers (starts with the initial w,h,d)
		containers := BoxList{Box{w, h, d}}

		// Reset our result
		result := BoxList{}

		// Sort the boxes into a new random permutation
		sort.Sort(boxes)

		// Find a new result which fits into container
		for _, box := range boxes {
			for cidx, container := range containers {
				if box.FitsInside(container) {
					// Add the box
					result = append(result, box)

					// Split the container into new containers
					// Imagine placing your box in front-left corner

					// The first new container is the space left above the box
					// You are left with a space with width equal to the box,
					// height equal to the space left above the box (container height - box height)
					// and depth equal to the box
					nw, nh, nd := box.w, container.h-box.h, box.d

					// The second split container is the space left behind the box
					// Width equal to the boxes width, height equal to the containers height
					// and depth equal to the space left behind the box (container depth - box depth)
					nw2, nh2, nd2 := box.w, container.h, container.d-box.d

					// The last split container is the space to the right of the placed box
					// Height and depth are both equal to the containers height and depth
					// Width is the space left to the right of the box (container width - box width)
					nw3, nh3, nd3 := container.w-box.w, container.h, container.d

					// Now remove the container we just used and append the new ones
					containers = append(containers[:cidx], containers[cidx+1:]...)
					containers = append(containers, Box{nw, nh, nd}, Box{nw2, nh2, nd2}, Box{nw3, nh3, nd3})
					break
				}
			}
		}

		// Send the result back on the channel
		res <- result
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())

	scanner := bufio.NewScanner(os.Stdin)

	// Read container dimensions
	var w, h, d int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d %d %d", &w, &h, &d)

	// Read number of boxes
	var n int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &n)

	// Read the boxes
	boxes := BoxList{}
	for i := 0; i < n; i++ {
		var bw, bh, bd int
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d %d %d", &bw, &bh, &bd)
		boxes = append(boxes, Box{bw, bh, bd})
	}

	fmt.Printf("\nCalculating how many boxes we can fit into the %d %d %d...\n\n", w, h, d)

	// Results channel
	ch := make(chan BoxList)

	// Just 100 goroutines
	for i := 0; i < 100; i++ {
		go Run(w, h, d, boxes, ch)
	}

	bestResult := 0
	for {
		res := <-ch
		if len(res) > bestResult {
			bestResult = len(res)
			fmt.Printf("Filled %d boxes into the %d %d %d:\n", bestResult, w, h, d)
			fmt.Println(res)
		}
	}
}

example-run.txt

☁  go  go run boxes.go
10 10 10
13
4 4 4
5 5 1
4 5 1
7 7 7
5 5 5
3 3 3
5 5 5
9 8 7
4 5 1
5 5 1
4 4 4
3 3 3
4 4 4

Calculating how many boxes we can fit into the 10 10 10...

Filled 11 boxes into the 10 10 10:
5, 5, 5
4, 5, 1
5, 5, 5
4, 4, 4
5, 5, 1
4, 4, 4
5, 5, 1
4, 5, 1
4, 4, 4
3, 3, 3
3, 3, 3

input.txt

10 10 10
13
4 4 4
5 5 1
4 5 1
7 7 7
5 5 5
3 3 3
5 5 5
9 8 7
4 5 1
5 5 1
4 4 4
3 3 3
4 4 4