tradziej / paint-shop Goto Github PK

This is a solution for this problem.

Solution was implemented in Ruby language. You need to have a Ruby interpreter installed.

Clone this repository and run:

./bin/paint-shop

Program ships with a command line single executable called paint-shop. You could download it from here:

wget -O /usr/local/bin/paint-shop https://github.com/tradziej/paint-shop/releases/download/0.0.1/paint-shop-x86_64-linux

or here:

wget -O /usr/local/bin/paint-shop https://github.com/tradziej/paint-shop/releases/download/0.0.1/paint-shop-x86_64-apple-darwin

depending on your platform.

Give it permissions to execute:

chmod +x /usr/local/bin/paint-shop

You need to have bundler installed.

gem install bundler

To run all tests:

./bin/test

Paint shop problem is a example of boolean satisfiability problem.

For given example:

5
1 M 3 G 5 G
2 G 3 M 4 G
5 M

We could represent every paint as x1, x2, x3, ..., xn where n is a paint number. If xn = 1 it means that n paint is "gloss" and if xn = 0 it is "matte" finish.

So every customer preferences could be written as a set of clauses: (not(x1), x3, x5), (x2, not(x3), x4), (not(x5))

Customer is satisfied if at least one paint from his preferences is providen. It could be represented as boolean equation, eg. for first customer it is: (not(x1) or x3 or x5) = 1.

To satisfy all customers we need to find a solution for logical and operation.

To solve given example we need to find a solution for a boolean formula: (not(x1) or x3 or x5) and (x2 or not(x3) or x4) and (not(x5)) = 1

I have implemented two solutions:

• Naive solver which generate all possible solutions, iterate over them and select solutions that satisfying all customers. Chosen solutions are sorted and the best one is returned.
• Backtracking method.