The three brothers problem

lotus 4533a1c18d updated readme with badge 1 month ago
include c509c11762 build catch2 test runner, split files into include/tests 3 months ago
tests c509c11762 build catch2 test runner, split files into include/tests 3 months ago
.clang_complete 6afc40361a added more paths to clang_complete depending on your c++ lib version 2 months ago
.gitignore c509c11762 build catch2 test runner, split files into include/tests 3 months ago
.travis.yml 98261ac093 tweak travis 1 month ago
README.md 4533a1c18d updated readme with badge 1 month ago
main.cpp c509c11762 build catch2 test runner, split files into include/tests 3 months ago
makefile 9621c45dca Added asan and ubsan to debug target 2 months ago
three.cpp c509c11762 build catch2 test runner, split files into include/tests 3 months ago

README.md

Build Status

Three Brothers Problem:

3 brothers have to transfer 9 boxes from one place to another. These boxes weigh 1, 2, 4, 5, 6, 8, 9, 11, 14 kilos.

Every brother takes 3 boxes.

Make a program that would count the most optimal way to take boxes? The difference between one brother’s carrying boxes weight and other’s has to be as small as it can be.

Bonus: Allow for more boxes.

Since every brother has to take three boxes we cannot divide up the weight evenly. If there was not this requirement each brother could equally carry 20 kilos. Since each brother must carry three boxes they will not all carry the same total weight.

Given that the weights of the boxes are growing linearly and do not appear to be random we can divide up the boxes without checking the weights.

Since the weights of the boxes are predictable as long as we are consistent with our box assignment we can minimize the disparity between weight distribution.

Also, with the given pattern of weights in the problem, we can extrapolate this and accept any number of boxes to move.

This solution has a time complexity of O(n) since I only have to loop over my boxes once and can avoid comparing weights.

In the case where I am only given the first three weights, the time complexity goes up to O(2n) since I must go through and "put all my boxes in the room".

If the weights of the boxes changes to be something more random, or the boxes are unordered, this solution no longer works.

If the number of boxes in is not divisible by three than we move as many boxes as we can, leaving some left over.

Building

make          # regular release build
make debug    # build fast with debug symbols enabled
make opt      # build a optimized version

Usage

./three 24 1 3 5

# 24 boxes to move
# box 1 = 1 kilo
# box 2 = 3 kilos.
# box 3 = 5 kilos.