Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
40lb stone problem
import Data.List
-- Return all combinations of 4 weights that can be used to weigh objects from 1 to 40 pounds.
weights = [(a,b,c,d) | a <- r, b <- r, c <- r, d <- r, -- generate 4 weights
(a+b+c+d) == 40, a <= b, b <= c, c <= d, -- sum exactly 40, weights in order
(canMeasure [a,b,c,d]) == [1..40]] -- can measure from 1 to 40 lbs
where r = [1..37] -- each stone must be at least 1 pound, so the max weight of each is 37.
-- Determine what a list of stones with given weights can themselves be used to weigh.
canMeasure s = sort . nub . filter (>0) $ foldl' (\a b -> concatMap (\c -> [c-b,c,c+b]) a) [0] s
@scsibug
Owner

A bit more explanation for 'canMeasure'. The sort/nub/filter just normalizes the list to be sorted, positive, and removes duplicates.
The foldl starts with being able to weigh nothing ([0]), and then for each additional weight considered (the list 's'), it adds the weight on the left side of the scale (c-b), leaves it off the scale (c) (maintaining the values from the previous recursion), and adds it to the right side (c+b). concatMap runs this function over every value of the list, returning a new list of weights (preventing nesting of lists).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.