StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POScala: idiomatic way to merge list of maps with the greatest value of each key?
text
Body
copied!<p>I have a List of Map[Int, Int], that all have the same keys (from 1 to 20) and I'd like to merge their contents into a single Map[Int, Int]. </p> <p>I've read <a href="https://stackoverflow.com/questions/1262741/scala-how-to-merge-a-collection-of-maps">another post</a> on stack overflow about merging maps that uses <code>|+|</code> from the scalaz library.</p> <p>I've come up with the following solution, but it seems clunky to me. </p> <pre><code>val defaultMap = (2 to ceiling).map((_,0)).toMap val factors: Map[Int, Int] = (2 to ceiling). map(primeFactors(_)). foldRight(defaultMap)(mergeMaps(_, _)) def mergeMaps(xm: Map[Int, Int], ym: Map[Int, Int]): Map[Int,Int] = { def iter(acc: Map[Int,Int], other: Map[Int,Int], i: Int): Map[Int,Int] = { if (other.isEmpty) acc else iter(acc - i + (i -> math.max(acc(i), other(i))), other - i, i + 1) } iter(xm, ym, 2) } def primeFactors(number: Int): Map[Int, Int] = { def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = { if (i > number) factors else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i) else iter(factors, rem, i + 1) } iter((2 to ceiling).map((_,0)).toMap, number, 2) } </code></pre> <p>Explanation: <code>val factors</code> creates a list of maps that each represent the prime factors for the numbers from 2-20; then these 18 maps are folded into a single map containing the greatest value for each key.</p> <h2>UPDATE</h2> <p>Using the suggestion of @folone, I end up with the following code (a definite improvement over my original version, and I don't have to change the Maps to HashMaps):</p> <pre><code>import scalaz._ import Scalaz._ import Tags._ /** * Smallest Multiple * * 2520 is the smallest number that can be divided by each of the numbers * from 1 to 10 without any remainder. What is the smallest positive number * that is evenly divisible by all of the numbers from 1 to 20? * * User: Alexandros Bantis * Date: 1/29/13 * Time: 8:07 PM */ object Problem005 { def findSmallestMultiple(ceiling: Int): Int = { val factors = (2 to ceiling).map(primeFactors(_).mapValues(MaxVal)).reduce(_ |+| _) (1 /: factors.map(m => intPow(m._1, m._2)))(_ * _) } private def primeFactors(number: Int): Map[Int, Int] = { def iter(factors: Map[Int,Int], rem: Int, i: Int): Map[Int,Int] = { if (i > number) factors.filter(_._2 > 0).mapValues(MaxVal) else if (rem % i == 0) iter(factors - i + (i -> (factors(i)+1)), rem / i, i) else iter(factors, rem, i + 1) } iter((2 to number).map((_,0)).toMap, number, 2) } private def intPow(x: Int, y: Int): Int = { def iter(acc: Int, rem: Int): Int = { if (rem == 0) acc else iter(acc * x, rem -1) } if (y == 0) 1 else iter(1, y) } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload