Danie Roux

People person, change agent. Journeyer through problem and solution space. Interested in being interested.

Danie Roux header image 2

Small programming challenge

September 18th, 2009 · 9 Comments · general

A friend sent me a small programming challenge.

Problem: Given a list of numbers, get the sum of the overlapping pairs.

Thus: [1, 2, 3, 4, 5] reduces to [3, 5, 7, 9].

My Haskell solution:

zipWith (+) x (tail x)

I was going to use the same trick with Erlang and was surprised to find that Erlang expects the two lists to be the same length. This is my Erlang solution:

sumpairs([X,Y|T]) -> [X+Y | sumpairs([Y|T])];
sumpairs([_]) -> [].

See more solutions here: http://github.com/apauley/RandomHacks/tree/master/CodeSnippets/SumPairs/

Tags: ··

9 responses so far ↓

  • 1 Leon Messerschmdit // Sep 18, 2009 at 10:12

    Try Scala. Your example will be simpler and shorter. Still learning Scala, so I can’t give you an example from the top of my head ;-)

  • 2 Gabriel Fortuna // Sep 18, 2009 at 14:36

    I did mine in perl in 4 lines… woulda made it 3, but I added a check to modify the array with a 0 as the last element if it’s an odd number of elements. Thanks for the fun exercise. :)

    #!/usr/bin/perl

    use strict;
    use warnings;
    use Data::Dumper;

    my @array = (1, 2, 3, 4, 5, 6, 7, 8, 9);
    push @array, 0 if scalar @array % 2;
    my %hash = @array;
    my @sum = map { $hash{$_}+$_ } sort keys %hash;

    print Dumper(\@sum);

  • 3 Gabriel Fortuna // Sep 18, 2009 at 14:52

    Oh wait… it’s 3 lines if you don’t count the array assignment. I could probably make it more concise at the expense of readability, but I strongly dislike Perl Golf (http://en.wikipedia.org/wiki/Perl_golf#Perl_golf)

  • 4 danieroux // Sep 18, 2009 at 14:57

    I will be suitably impressed if Scala will be even simpler and shorter than the Haskell version! Beating this for expressibility will be admirable:

    zipWith (+) x (tail x)

  • 5 Andreas Pauley // Sep 19, 2009 at 13:21

    Gabriel,

    The Perl solution above returns [3, 7, 11, 15, 9] when I execute it.

    According to my calculations it should rather return
    [3, 5, 7, 9, 11, 13, 15, 17]

    (on an array from 1 to 9)

  • 6 Andreas Pauley // Sep 19, 2009 at 13:22

    Danie,

    I like the Haskell solution!
    It is just as elegant as the Clojure example, and probably much faster.

  • 7 Frank Shearar // Sep 19, 2009 at 20:38

    In Common Lisp:

    (defun pairwise-add (l)
    (mapcar #’+ l (rest l)))

    I had tried to solve the problem with a fold, before I realised (upon googling zipWith) that I was using the wrong hammer!

    Also, please someone improve this Prolog version:

    sumpairs([X,Y|T],Out) :- Z is X + Y, sumpairs([Y|T], Tail), append([Z],Tail,Out).
    sumpairs(_,[]).

    (Yes, I did rampantly steal Danie’s very clever solutions.)

  • 8 Andreas Pauley // Sep 20, 2009 at 21:04

    Frank,

    Thanks for the Prolog, interesting to see the similarities with Erlang.

    My Lisp attempt used cdr where your’s used rest (like Clojure). Cool, I thought Common Lisp was stuck with the cryptic cdr.

  • 9 Frank Shearar // Sep 21, 2009 at 12:54

    Hey Andreas,

    Ja, REST is CDR, basically (and FIRST is CAR). The Common Lisp HyperSpec says “rest is often preferred stylistically over cdr when the argument is to being subjectively viewed as a list rather than as a cons.”

    The similarities between Prolog and Erlang are to be expected, of course, given Erlang’s history as starting out as a hacked up concurrent Prolog.

    It’s the lack of the notion of a function that returns something that makes my implementation look so yuck. It’s pretty much a straight-up translation of the Erlang version.

    And Danie, kudos for the clever insight! I spent too long thinking how to do the obvious and tedious iterate-over-list way of summing before realising how your Haskell implementation worked.

Leave a Comment