Compute max population given a list of people's birth and death year

I recently came across a brief programming puzzle prompt (say that three times fast) which asked to return the year that population peaked.

The actual algorithm to compute it can be done several ways and is not particularly difficult, but I have recently been challenging myself to write .. ahem .. "more functional" code.

There are several tenets of FP, but a chief one is not producing what developers call "side effects". I'm hoping to get to a point where I do not rely as much on classic object-oriented patterns and feel more at ease diving right into the functional style. Of course this takes practice, so I decided to spend some extra time polishing up my code to meet my internal requirements:

val persons = Seq(
Person(2000, 2010),
Person(2000, 2005),
Person(1990, 2005)
)

// Create an array of population change.
val births = persons.groupBy(_.birthYear).mapValues(_.length)
val deaths = persons.groupBy(_.deathYear).mapValues(_.length)
val populationChanges = (births.keySet ++ deaths.keySet).map { year =>
(year, births.getOrElse(year, 0) - deaths.getOrElse(year, 0))
}.toMap

println("populationChanges", populationChanges)

val sortedYears = populationChanges.keys.toSeq.sorted
println(sortedYears)

// construct an array of total populations
val populations = populationChanges.toSeq
.sortBy(_._1)
.scanLeft(0) { (a, b) => a + b._2 }
.tail
.zip(sortedYears) // this is a bit hacky
.map{ case(count, year) => (year, count) }

println("pop", populations)
println("max pop", populations.maxBy(_._2)) // (2000, 3)


This is a demonstration of what I created after a few minutes of iteration.

I was readily able to produce a list of population changes and from there, performed further transformations to arrive at a list of total populations for each year. From there determining the year that population peaked was trivial.

However, I'm not fully satisfied with this solution. I could be being too dogmatic, but in my mind I would not be breaking scope of a map function to reference external values, even though it proved expedient in this case.

Your approach isn't bad if you want to do multiple analyses of the population over time. For programming puzzles I often find it useful to focus in on exactly what's being requested and leave the other interesting stuff for another day.

persons.flatMap(p => Seq((p.birthYear, 1), (p.deathYear, -1)))
.sorted
.foldLeft((0,0,0)){case ((mxYear,mxPop,curPop), (thisYear,dif)) =>
if (curPop+dif > mxPop) (thisYear, curPop+dif, curPop+dif)
else (mxYear, mxPop, curPop+dif)
}._1  //res0: Int = 2000


In this case the data is

• traversed once - to attach a 1 or -1
• sorted - to get all the years in order
• traversed a 2nd and final time - to count the population changes and save the maxes
• Great use of foldLeft! – Leo Romanovsky Jan 29 '18 at 5:35