4 releases (breaking)

Uses old Rust 2015

0.4.0 Feb 12, 2018
0.3.0 Feb 6, 2018
0.2.0 Feb 6, 2018
0.1.0 Feb 4, 2018

#2006 in Algorithms

MIT license

41KB
842 lines

Packing PuzzleBuild StatusCoverage Statuspack on crates.io

Solver for packing problems.

installation

You can use this library by adding a dependency to your Cargo.toml

[dependencies]
pack = "*"

If you want to fix a specific version, feel free to enter a version number.

Slothouber-Graatsma Puzzle

The Slohouber-Graatsma puzzle asks for

packing six 1 × 2 × 2 blocks and three 1 × 1 × 1 blocks into a 3 × 3 × 3 box.

We are going to solve it with the pack library.

First we announce the use of the external crate.

extern crate pack;

We need to a few things before we can start solving the puzzle. One is a pack::puzzle::solver::Target. A target designates the volume to pack. A target is created with a vector of pack::puzzle::piece::Positions.

fn brick3x3x3() -> Target {
    Target::new(vec!(
        Position::new(0, 0, 0),
        Position::new(1, 0, 0),
        Position::new(2, 0, 0),
        Position::new(0, 1, 0),
        Position::new(1, 1, 0),
        Position::new(2, 1, 0),
        Position::new(0, 2, 0),
        Position::new(1, 2, 0),
        Position::new(2, 2, 0),

        Position::new(0, 0, 1),
        Position::new(1, 0, 1),
        Position::new(2, 0, 1),
        Position::new(0, 1, 1),
        Position::new(1, 1, 1),
        Position::new(2, 1, 1),
        Position::new(0, 2, 1),
        Position::new(1, 2, 1),
        Position::new(2, 2, 1),

        Position::new(0, 0, 2),
        Position::new(1, 0, 2),
        Position::new(2, 0, 2),
        Position::new(0, 1, 2),
        Position::new(1, 1, 2),
        Position::new(2, 1, 2),
        Position::new(0, 2, 2),
        Position::new(1, 2, 2),
        Position::new(2, 2, 2),
    ))
}

Because bricks are often used as targets, there is a utility pack::util::target::brick function that does exactly that. The above code could be replaced with brick(3, 3, 3).

One other thing we need is a pack::puzzle::pieces::Bag of pack::puzzle::piece:Templates. A template is a shape that can be oriented in different ways by iterating over them. A bag is a container to hold templates.

Templates are created by providing the vector of positions they occupy.

fn slothouber_graatsma_bag() -> Bag {
    Bag::new(vec!(
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
            Position::new(1, 0, 0),
            Position::new(0, 1, 0),
            Position::new(1, 1, 0),
        )),

        Template::new(vec!(
            Position::new(0, 0, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
        )),
        Template::new(vec!(
            Position::new(0, 0, 0),
        )),
    ))
}

Finally we need to tell the solve function what to do when they find a solution. This can be done by passing a clojure. For this example we will just print the solution.

Our main function could look like the following code.

fn main(){
    let target = brick(3, 3, 3);
    let bag = slothouber_graatsma_bag();

    solve(&target, bag, &mut |solution|{
        println!("{}", solution)
    });
}

Running it will print a solution to the Slothouber-Graatsma puzzle. The full source for this example can be found in examples/slothouber-graatsma.rs. For a more extensive documentation see the wiki.

Development

If you are interested in contributing to this library please read CONTRIBUTING.md.

Running clippy

Follow the installation instruction for clippy and run the following command.

cargo +nightly clippy

No runtime deps