Wallify, a more functional-ish version

[dlandauer]

(For those who missed tonight's meeting: Dick Wall brought in an
interesting problem that we worked on: Given a list of long
integers: for each element, find the product of all of the other
elements. Sum those products.)

I took the approach of making one big sum, and then dividing. The big
product is zero if any of the elements is zero, so I treat that case
separately. I didn't quite get it right, though -- the two-zeros case
is left as an exercise :-)



object Wallify extends Application {

type llist = List[Long]
def wallify(ll : llist) : Long = {
val big_prod = ll.foldLeft(1L) {_*_}
def mult_nonZ(a:Long, b:Long) : Long = b match {
case 0L => a
case bok => a * bok
}

big_prod match {
case 0L => ll.foldLeft(1L)(mult_nonZ)
case bp => (0L /: ll.map( bp / _ ) ) {_+_}
}
}

for ( val test_list : llist <- List( List(101L,102L,103L,104L,
105L),
List(9L,8L,7L,6L,5L),
List(111111L,111111L,111111L,
111111L,111111L),
List(9L,8L,0L,6L,5L),
List(9L,8L,0L,6L,0L) ) ) {
println("Result is " + wallify(test_list))
}
}

[Jorge Ortiz]

I'll throw in my version for consideration.

The algorithm counts the number of zeros in the list.

If there are no zeros, it finds the product of the entire list and
divides it by each element in the list.

If there is one zero, it finds the product of all the numbers except
zero. It returns a list of all zeros, except for the position that
originally had a zero, where it puts the calculated product.

If there are two or more zeros, it returns a list of all zeros.

The functions: multiply, lst.count, lst.map and lst.filter are all
O(N) time-complexity where N is the length of the list. The functions
lst.map and lst.filter are also O(N) space-complexity where N is the
size of the resulting list. Therefore wallify is O(N) time and O(N)
space.

(An optimal solution would be O(N) time and O(1) space if the input
was an Array[Long] and we could destructively modify the input. If the
input was an Array[Int], or we couldn't destructively modify the
input, then the optimal solution is also O(N) space, since we'd need
to copy over the input to a new Array[Long].)

--j

def multiply(lst: List[Long]): Long =
(1L /: lst)(_ * _)

def wallifyLong(lst: List[Long]): List[Long] = {
val numZeros = lst.count(_ == 0)
numZeros match {
case 0 =>
val product = multiply(lst)
lst.map(product / _)
case 1 =>
val withoutZeros = lst.filter(_ != 0)
val product = multiply(withoutZeros)
lst.map(x => if (x == 0) product else 0)
case _ =>
// numZeros >= 2
lst.map(x => 0)
}
}

def wallify(lst: List[Int]): List[Long] =
wallifyLong(lst.map(_.toLong))

[dlandauer]

Cool. I had a similar thought during the drive home, and came up with
this when I got home:

object Wallify extends Application {

type llist = List[Long]

def wallify(ll : llist) : Long = {

// The product of all non-zeros in our list.
val prod_nzs = ll.foldLeft(1L) {
(a,b) => a * (if(b==0L) 1L else b )
}

// Count the zeros in our list.
val nr_zeros = ll.foldLeft(0L) {
(a,b) => a + (if(b==0L) 1 else 0)
}

nr_zeros match {

// No zeros ==> all the divides will succeed.
// To pick this apart:
// map returns a list of the "products of others", i.e.,
our
// entire list product, divided by each element in
turn.
// (0L /: that_list ) {_+_} is a sum of those products.
// Could be written as
// that_list.foldLeft(0L){_+_}
// or even
// that_list.foldLeft(0L){(a,b) => a+b}
case 0 => (0L /: ll.map( prod_nzs / _ ) ) {_+_}

// Exactly one zero implies that the answer is just the
product
// of all of the non-zeros from our original list.
case 1 => prod_nzs

// More than 1 zero ==> the answer is zero.
case _ => 0

}
}

for ( val test_list : llist <- List( List(101L,102L,103L,104L,
105L),
List(9L,8L,7L,6L,5L),
List(111111L,111111L,111111L,
111111L,111111L),
List(9L,8L,0L,6L,5L),
List(9L,8L,0L,6L,0L) ) ) {
println("Result is " + wallify(test_list))
}
}

I guess it'd be a little cleaner if I had found "count".

My driving-home thoughts on the efficiency concerns centered around
the size of the numbers you'll end up with when you multiply a bunch
of Longs together. They'll get really big really fast. So we'd
probably have to use BigIntegers, and the efficiency concerns become
very data-dependent -- on the sizes of the numbers themselves. So (it
being near midnight), I'd leave that analysis for another day :-)

-- Doug L.

[Michael]

Here is my version that I started last night and finished today. I
think it is pretty similar to Jorge's, but less functional and more
imperative.

def wallify(list:List[Int]):List[BigInt] ={
val one = BigInt.int2bigInt(1)
val noZeroes = list.filter(_ != 0)
if (noZeroes.length == list.length){
val prod = list.foldLeft(one){(p,e) => p*BigInt.int2bigInt(e)}
list.map(prod/_)
} else if (list.length - noZeroes.length == 1){
list.map((el) => if (el == 0) noZeroes.foldLeft(one){(p,e) =>
p*BigInt.int2bigInt(e)} else 0)
} else {
list.map((el) => 0)

[liesen]

I wasn't at the meeting, but as far as I can tell the problem is to:

Given a list of n elements, produce a new list of n elements where
each element is the product of all elements before it and after it in
the original list. Then return the sum of that list.

So, the naïve solutions are already there: calculate the full product
= p, at each element, i, divide p with the number at i and the sum up.

I'd try to not do any divisions by first scanning the list from left
to right and from right to left accumulating the product "both ways",
then index those list to produce the new one (new[i] = fromleft[i - 1]
* fromright[i + 1])

In Haskell (with ints):

wallify :: [Int] -> Int
wallify as = let
ls = 1 : init (scanl1 (*) as)
rs = tail (scanr1 (*) as) ++ [1]
in
sum $ zipWith (*) as bs

The algorithm runs with four passes over the list, thus it's O(n).

You can do the same in Scala with some effort or just get
http://projects.workingmouse.com/public/scalaz/tags/latest/src/main/scalaz/LList.scala

[liesen]

I took the time to put the code in Scala, and also to optimize it as
best as I could.

def wallify(as: List[Int]): Int = {
var zeros = 0
var sum = 0
var p = 1
var scanL = p :: Nil

// Build reverse scanL (prepend instead of append to the linked
list)
for (a <- as) {
if (a == 0)
zeros += 1
else {
p = p * a
scanL ::= p
}
}

// Optimize for zeros
if (zeros == 1)
return p
else if (zeros > 1)
return 0

// Combine sum by scanning as from the right add multiplying with
elements
// from scanL
p = 1

for ((a, b) <- scanL.tail zip (1 :: as.reverse)) {
p = p * b
sum += a * p
}

sum
}

Here's a quite short version of the naïve algorithm:

def naiveWallify(as: List[Int]): Int = {
val zeros = as count (_ == 0)

if (zeros == 1)
return as reduceLeft ((p, a) => if (a == 0) p else p * a)
else if (zeros > 1)
return 0

val product = as reduceLeft (_ * _)

as map (product / _) reduceLeft (_ + _)
}


--
johan

On Jun 19, 9:38 am, liesen <johanlie...@gmail.com> wrote:
> I wasn't at the meeting, but as far as I can tell the problem is to:
>
> Given a list of n elements, produce a new list of n elements where
> each element is the product of all elements before it and after it in
> the original list. Then return the sum of that list.
>
> So, the naïve solutions are already there: calculate the full product
> = p, at each element, i, divide p with the number at i and the sum up.
>
> I'd try to not do any divisions by first scanning the list from left
> to right and from right to left accumulating the product "both ways",
> then index those list to produce the new one (new[i] = fromleft[i - 1]
> * fromright[i + 1])
>
> In Haskell (with ints):
>
> wallify :: [Int] -> Int
> wallify as = let
>     ls = 1 : init (scanl1 (*) as)
>     rs = tail (scanr1 (*) as) ++ [1]
>   in
>     sum $ zipWith (*) as bs
>
> The algorithm runs with four passes over the list, thus it's O(n).
>

> You can do the same in Scala with some effort or just gethttp://projects.workingmouse.com/public/scalaz/tags/latest/src/main/s...