public
Created

40lb stone problem

  • Download Gist
stones.hs
Haskell
1 2 3 4 5 6 7 8 9 10
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

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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.