Instantly share code, notes, and snippets.

# scsibug/stones.hs Created Feb 24, 2012

What would you like to do?
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
Owner

### 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).