• Grandpa is Famous (from Bryan)​

• Table Legs (from Jorge) Do you understand this problem? Given n table legs of differing lengths how much total must be cut from some of the legs so that the table sits level. Presumably the answer requires that the three longest legs be the same length. The first example has lengths of 2000, 3000, 4000. The given answer is 3000. That makes sense if all the legs must be cut to length 2000. But the second example has legs of 2000, 2000, 1999, 2001. Why isn't the answer 1? [The given answer is 4.] Why can't the table sit level if three legs are of length 2000? (Not all legs are required to be the same length.) The third example has legs of length 2000, 2000, 1999, 2001, 1999. It would seem that the answer here should also be 1, which is the given answer. So I'm confused about the second example. Why does the addition of an additional short leg change the answer from example 2 to example 3?

I thought Sticks would be an interesting problem to work on. I have what seems to be a solution, but it's not very clean or very clever. (It's in my Sticks package.)  Here are the two examples provided by the problem.

  "\n" ++ sticks(Vector(5, 2, 1, 5, 2, 1, 5, 2, 1)).mkString("\n")
                                                  //> res2: String = "
                                                  //| {1, 5}
                                                  //| {1, 5}
                                                  //| {1, 5}
                                                  //| {2, 2, 2}"

  "\n" ++ sticks(Vector(1, 2, 3, 4)).mkString("\n")
                                                  //> res6: String = "
                                                  //| {1, 4}
                                                  //| {2, 3}"

The solution to the first example is four sets: {1, 5}, {1, 5}, {1, 5}, {2, 2, 2}. The solution to the second problem is two sets: {1, 4}, {2, 3}. The code works as follows.

1. It first finds the sum of the length of all the pieces. (24 in the first case; 10 in the second)
2. Then it finds the divisors of that sum—on the grounds that the sticks have to be divided into sets, each of which has the same length. Hence that length is a divisor of the total.
3. Then for each divisor—from smallest to largest—it tries to find ways to subdivide the sticks into sets so that each set has that total length and there are no sticks left over. That's the hard part. My approach was fairly brute force.

I thought that a MultiSet would be a useful collection. (A MultiSet is a set with possible repetitions.) But Scala doesn't have a MultiSet class. While looking that up I found a suggestion to use a TreeMap instead. The TreeMap keys are the (unique) set elements. The TreeMap values are the number of times that element appears in the set. So I decided to implement a MultiSet by using a TreeMap to keep track of the element counts. The MultiSet is in its own file.  That wasn't too difficult.

The really complex part was searching for the sets. The problem is that there may be many ways to make a set with a certain total. They must all be considered. The method buildTree (embedded in Sticks in the Sticks object) does the search.

    def buildTree(goal: Int, pieces: MultiSet): Option[Seq[MultiSet]] 

It takes a goal (the desired total for each subset) and a MultiSet of pieces. It returns Some(Seq[MultiSet]) if it can find subsets that add up to goal. The subsets are the Seq of MultiSets. If it can't find subsets that add to goal (while using all the pieces) it returns None. It builds a rather involved tree of possibilities.  If you can find a simpler way to do it, that would be great.