Skip to content
Create a gist now

Instantly share code, notes, and snippets.

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 commented Feb 24, 2012

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.