Producing uniform lists in Scala

Question

When writing an answer to another question here, I came across the problem of producing lists of integers having a certain total and only consisting of a certain number and an optional rest. So for total 21 and number 5 you would get List(5, 5, 5, 5, 1).

Solving the problem is obviously not hard. However, I have the feeling that it can be written more concisely than this:

def uniformList(sum: Int, num: Int): List[Int] = {
  val rest = sum % num
  List.fill(sum / num)(num) ::: (if (rest == 0) Nil else List(rest))
}

Of course I could inline the rest but I don't think it makes it more readable. I'm not looking for a performant solution but a more concise one. My feeling is that there should be a solution that is as easy to grasp as the concrete example I gave in the first paragraph.

Answer 1

Here are few more ways to produce your uniform lists:

def f0(a: Int, b: Int) = {
  val c = a % b
  val d = a / b
  val n = if (c == 0) d else d + 1
  (1 to n).toList map (i => if (i * b <= a) b else c)
}

def f1(a: Int, b: Int) = {
  val c  = a % b
  val d  = a / b
  val xs = List.fill(d)(b)
  if (c == 0) xs
  else        xs ::: c :: Nil
}

def f2(a: Int, b: Int) = {
  val r = a % b
  val n = a / b
  if (r == 0) List.fill(n)(b) 
  else        List.tabulate(n + 1)(i => if ((i + 1) * b <= a) b else r)
}

• f0 is a different/interesting way to derive your lists but to my mind is harder to parse that f1

• f1 is very similar to what you have already but instead of redundantly concatenating Nil when rest == 0 we simply return the list as is

• f2 is quite ugly but utilizes tabulate so I thought I'd include it

You'll notice that in each of the four functions considered so far we calculate rest = sum % nums and then branch based on the result of this calculation. While I can think of other ways to derive a value for rest they aren't as intuitive as the % operator and in the end I think we would still have a conditional statement which decided the final element of the list.

Other than adopting the small change suggested by function f1 I think your code is as concise / understandable as it can be.

Answer 2

Three short lines of code for something that requires two full lines of natural language explanation is already quite short. Further shortening it would not serve purposes outside code-golf. Vertere's more verbose suggestions are actually better quality code, IMHO.

Answer 3

Since I posted the question, I have thought about the problem again. I tried to use recursion to solve it more elegantly:

def uniformList(total: Int, el: Int): List[Int] =
  if (total <= el) List(total)
  else el :: uniformList(total-el, el)

This is pretty close to what I had in mind. What I like about it is that there are no expression being used in several places, so we don't need any variables to capture and reuse them.

I also found another solution:

def uniformSum(total: Int, el: Int): List[Int] =
  List.fill(total/el)(el) ::: List(total % el).filter(_ > 0)

This is my favorite so far. The call to filter feels a little bit like a hack. However, in my opinion the main advantage is that you can actually see how the list is structured. without having to introduce new variables. Maybe the code would be clearer with extra variables such as mainPart and optionalRest. It looks clear now, but maybe not if I saw the function for the first time.