An Interesting Little Problem

Saturday June 14th • Challenges, F#, Functional Programming, Google, Haskell Category

vals :: [Int]
vals = [ 4, 3, 2, 1, 2 ]
 
answers :: [Int]
answers = [ front !! (x-1) * back !! (x+1) | x <- [1..length vals] ]
  where
    front = scanl1 (*) temp
    back = scanr1 (*) temp
    temp = [1] ++ vals ++ [1]

Prelude> :l google.hs
[1 of 1] Compiling Main             ( google.hs, interpreted )
Ok, modules loaded: Main.
*Main> answers
[12,16,24,48,24]
*Main>

#light
 
let vals = [ 4; 3; 2; 1; 2; ]
 
let mul a b = a * b
let (++) = List.append
 
let answers = 
  let temp = [1] ++ vals ++ [1]
  let front = List.scan1_left mul temp |> List.to_array
  let back = List.scan1_right mul temp |> List.to_array
  seq { for x in [1 .. vals.Length] -> front.[x-1] * back.[x+1] }

-- by lf
scanm f z xs = zipWith f (scanl f z xs) (tail $ scanr f z xs)
main = print $ scanm (*) 1 [4,3,2,1,2]
 
-- by Henning
answers :: [Int] -> [Int]
answers vals = zipWith (*) front (drop 1 back)
	where
	front = scanl (*) 1 vals
	back = scanr (*) 1 vals
 
-- by desp
problem input = zipWith (*) front back where
  front = init (scanl (*) 1 input)
  back = tail (scanr (*) 1 input)
 
-- by foobar
foo [] _ = ([], 1)
foo (x:xs) acc = let (l, m) = foo xs (acc*x)
                 in ((m*acc):l , m*x)

2 Trackbacks/Pingbacks

1. Pingback: some blog » Programming challenge on June 17, 2008
2. Pingback: Problem with an interesting little problem « Antimatroid’s Weblog on August 8, 2008

65 Comments

1. Rob G
   June 15, 2008

   Hmmm…I don’t see why you don’t just multiply every item in the list together (= full product) and then for each i in the input array, the corresponding output[i] is equal to the full product divided by the input[i] value.

   Oh wait - but then I see you’ve got that silly note at the bottom telling me not to use the division operator. OK firstly, that’s extremely stupid since it’s the best way, but never mind, there’s more than one way to skin a quotient!

   output[i] = fullProduct * input[i]^(-1)

   Nice! ;-P

2. OJ
   June 15, 2008

   That doesn’t work

3. Rob G
   June 15, 2008

   It’s pseudo code you numpty caret = “raised to the power of”

4. OJ
   June 15, 2008

   Ah ha! So what you meant was:

   output[i] = fullProduct * pow(input[i], -1);

   where pow(x, y) is x to the power of y.

   Yup, that’s cheating And you know damned well that’s what the question was trying to avoid

5. Rob G
   June 15, 2008

   True - but the question “didn’t” say it - how do you know for sure it didn’t want them to be creative about division itself? Lateral thinking and all that stuff that’s supposed to be at the core of every GoogleBot

6. OJ
   June 15, 2008

   Lateral thinking: yes.
   Cheating: no.

   You know damned well that the problem was worded to make you think outside the box

7. Rob G
   June 15, 2008

   I’ll give you out the box!
   output[i] = Math.Pow(10, Math.Log(10, fullProd) - Math.Log(10, input[i]))

8. lf
   June 16, 2008

   I think your Haskell solution is n^2 (the !! operator takes linear time).

   You want something like

   scanm f z xs = zipWith f (scanl f z xs) (tail $ scanr f z xs)
   main = print $ scanm (*) 1 [4,3,2,1,2]

9. Logan Capaldo
   June 16, 2008

   Assuming F# is close enough to OCaml, (op *) should work in place of mul.

10. web design company
    June 16, 2008

    I may be missing something, but I don’t think that’s O(n). The !! operator is the list index operator, and since Haskell’s lists are singly-linked lists, that’s an O(n) operation. If you do this for every item in the “array” of integers, that’s O(n^2). It looks like it can be fixed easily, though, just by converting “front” and “back” into arrays after they’ve been built.

11. Jason H
    June 16, 2008

    # How’s about ….

    _set = [4, 3, 2, 1, 2]
    
    answer = [0] * len(_set)
    
    x = 1
    for i in range(len(_set)):
        answer[i] = x
        x *= _set[i]
    
    x = 1
    for i in range(len(_set) - 1, -1, -1):
        answer[i] *= x
        x *= _set[i]
    
    print answer

12. desp
    June 16, 2008

    Here’s my Haskell solution:

    problem input = zipWith (*) front back where
      front = init (scanl (*) 1 input)
      back = tail (scanr (*) 1 input)

13. foobar
    June 16, 2008

    my code looks like this:

    foo [] _ = ([], 1)
    foo (x:xs) acc = let (l, m) = foo xs (acc*x)
                     in ((m*acc):l , m*x)

14. Jude
    June 16, 2008

    Well that’s simple . Each element in output[i] can be written as the cumulative product of all the numbers to its left and right.

    result = 1
    for i in range(0,len(A[i])):
      output[i] = result
      result = a[i]
    result = 1
    for i in range(len(A[i]),0,-1):
      output *= result
      result *= a[i] 

    This algo runs on O(n)

15. Chris
    June 16, 2008

    Jude’s code doesn’t, technically, work, here’s a version that does:

    A = [4,3,2,1,2]
    output = []
    result = 1
    for n in A:
    	output.append(result)
    	result *= n
    result = 1
    for i, n in reversed(list(enumerate(A))):
    	output[i] *= result
    	result *= n
    print output
    

16. Buffi
    June 16, 2008

    Here’s a ugly python one-liner

    def doit(l): return [reduce(lambda x,y: x*y, l[0:i]+l[i+1:]) for i in range(len(l))]

17. Andy
    June 16, 2008

    Here’s the solution in C#:

    int[] input = { 4, 3, 2, 1, 2 };
    int[] forwardLookUp = new int[input.Length];
    int[] backwardLookUp = new int[input.Length];
    
    forwardLookUp[0] = input[0];
    backwardLookUp[input.Length - 1] = input[input.Length - 1];
    
    for (int i = 1, j = input.Length - 2; i < input.Length; i++, j--)
    {
      forwardLookUp[i] = input[i] * forwardLookUp[i - 1];
      backwardLookUp[j] = input[j] * backwardLookUp[j + 1];
    }
    
    int[] output = new int[input.Length];
    for (int i = 0; i  0 ? forwardLookUp[i - 1] : 1;
      output[i] *= i < input.Length - 1 ? backwardLookUp[i + 1] : 1;
    }

18. Oleg
    June 16, 2008

    Chris, your code it O(n^2), because of this line:

    for i, n in reversed(list(enumerate(A))):

    reversed itself is O(n)

19. Palindrom
    June 16, 2008

    “for i, n in reversed(list(enumerate(A))):” is not O(n^2), it’s O(2n).

20. John thomas
    June 16, 2008

    Wow, now I have a headache. Aspirin anyone?

    JT

21. Ray
    June 16, 2008

    How about:

    let p = A[1] * A[2] … A[N]

    Output[i] = p / A[i]

22. Henning
    June 16, 2008

    Your Haskell solution is not O(n), but O(n^2). You generate a list “front”, which has n-1 elements, so each index operation(!!) takes O(n). Since you’re doing this n times, the complexity is O(n*n). In fact, it’s a little less than that, but certainly not O(n).
    Here’s a solution that uses no nasty operations (like ++) and runs in O(n):

    answers :: [Int] -> [Int]
    answers vals = zipWith (*) front (drop 1 back)
    	where
    	front = scanl (*) 1 vals
    	back = scanr (*) 1 vals

23. Ray
    June 16, 2008

    Sorry, ignore my comment above. Forgot to finish reading the constraints.

24. Kate
    June 16, 2008

    Here’s the solution in C.

    #include <stdio.h>
    
    int main(void)
    {
      int array[5] = {4, 3, 2, 1, 2};
      int arraylen = 5;
      int newarray[5] = {1, 1, 1, 1, 1};
      int i;
      int ii;
      int temp = 1;
      int tempt = 1;
    
      ii = arraylen - 2;
      for(i = 1; i < arraylen; i  )
        {
          temp*=array[i - 1];
          newarray[i]*=temp;
          tempt*=array[ii   1];
          newarray[ii]*=tempt;
          ii--;
        }
    
      for(i = 0; i < arraylen; i  )
        {
          printf("%d ", newarray[i]);
        }
      printf("\n");
    
      return 0;
    }

25. ben
    June 16, 2008

    oleg: while ‘reversed’ is o(n) - its only called once, so it is still o(n) (instead of o(n^2)).

26. OJ
    June 16, 2008

    Wow! An influx of responses overnight. How exciting

    @Rob: Man, constant use of Math.Log() and Math.Pow().. sounds expensive to me! Technically O(n), but hardly quick. You should know better young fella-my-lad!

    @lf: I had no idea that the !! operator wasn’t O(1). I was under the impression that it indexed in the same way an array was indexed. Thanks for the heads up, seems like I need to do some more reading. Thanks for pointing it out!

    @Logan: I shall give that a shot mate. Thanks for pointing it out. Seems a little strange that this problem would appear in F#. I wonder what the motivator was to use (* … *) for comments?!

    @Jude: Yup, the problem is simple, but writing a nice functional version isn’t as simple — particularly when you’re still not 100% with the languages you’re using I’m not familiar with the syntax of the code you’ve written. Is that OCaml? Python?

    @Chris: Thanks for clearing that up. I’ve added the pre tags for you. I still am yet to add a comment plugin that lets you put code/html tags in. Should get that sorted out soon as I’m hoping to get more code submissions in comments.

    @Andy: As you probably saw, for some reason this comment plugin is chewing up the plus symbols. I’ve fixed that up too. Thanks for the submission. C and C# are my babies, so I tried to avoid writing a solution in either of those. Is C# your general language of choice? Have you done much with functional programming at all?

    @Henning: Thanks for the clarification. I was under the impression that !! wasn’t O(n) itself. My bad lf has already pointed that out too. Thanks for the submission. It’s great to get the chance to learn some of this stuff from other Haskellers. I guess I should have made sure that !! was O(1) before using it. Assumptions….

    @Ray: Hehe No worries.

    @Kate: Is C your language of choice? Are you familiar with functional programming at all? I have fixed your comment up for you

    @Everyone: I shall revamp the comment system on here so that it supports code tags and allows you to edit your comments if you make a mistake. Thanks to all for commenting

27. Jason
    June 16, 2008

    My feedback is, if you’re going to make a blog post about algorithms, use a common language or common pseudo-code instead of these esoteric languages that are hard for newcomers to follow.

28. OJ
    June 16, 2008

    @Jason: Interesting feedback. There are a few reasons that I posted what I did. I’m currently playing around with functional languages (Haskell and F# in particular) and was interested in solving the problem using both of those languages. This post was supposed to be a mixture of algorithm and language.

    I personally find psuedo-code horrible. Yes it’s great for generalising, but I much prefer concrete examples, and from past experience many other people do too.

    Using the word “esoteric” when referring to functional languages might start another religious war I can certainly understand how the concept of functioal programming can be really tough to grasp if you’re an imperative programmer. I can see how examples might be confusing for newcomers to functional programming. I don’t agree with functional programming being estoric though
    Do you think that a quality imperative example would suffice in a language like C or C#?

    Your feedback is greatly appreciated

29. OJ
    June 16, 2008

    Woah! I just checked the comment moderation queue and found another stack of comments. Sorry for the omissions!

    @web design: Yup, you’re right. My bad I have learned my lesson.

    @Jason H: I know this will sound like a n00b question, but is that Python?

    @desp: nice and succinct mate
    @Buffi: I have fixed up your comment for ya mate.

30. Dan
    June 16, 2008

    Here’s another C solution using recursion that I’ve come up with:

    int foo(const int *input, const int size, int index, int lproduct, int *output)
    {
      if (index >= size)
        return 1;
      else
      {
        int rproduct = foo(input, size, index 1, lproduct * input[index], output);
        output[index] = lproduct * rproduct;
        return input[index] * rproduct;
      }
    }

    Called by:
    foo(input, SIZE, 0, 1, output);

31. Jason
    June 16, 2008

    @OJ:

    I think any Haskell programmer could understand a C or C# example, but comparatively few people understand a Haskell example. Rather than immediately understanding your approach, the non-Haskell-programmer must research, e.g., what the “!!” operator does.

    Algorithms courses are usually language-neutral, as the algorithm is the lesson, not the implementation of it.

32. OJ
    June 16, 2008

    @Dan: Have added pre tags to your code for you

    @Jason: That’s true. Functional coders will have no problem reading imperative code, and yes there are some “strange” (for want of a better expression) operators in Haskell/F# that aren’t necessarily standard. They can definitely aid in the confusion. I guess with my focus on functional programming I have really not thought too much about imperative examples to stuff that I’m doing. Perhaps in cases such as this where the purpose is a mixture of algorithm and code I should provide both imperative and functional solutions. I could also make more of an effort to cover those things which aren’t necessarily obvious when using languages that aren’t “mainstream”.

    I will take your feedback on board mate. I’ll be sure to make more effort to avoid potential confusion and
    provide more examples down the track. Cheers.

33. OJ
    June 16, 2008

    Hi all, I’ve just added a new comment plugin which should allow you to at least add <pre></pre> tags around your code. It doesn’t support syntax highlighting, but it’s better than nothing!

    I’ve also added a comment editing plugin which should let you change your comment for up to 30 mins after posting. I hope it helps.

    Thanks all

34. boomi
    June 16, 2008

    There is a straightforward recursive solution that works the same way in most languages:

    main = do putStrLn $ show products_of_peers
      where (_, products_of_peers) = multiply_peers 1 [4, 3, 2, 1, 2]
              where multiply_peers _ [] = (1, [])
                    multiply_peers l (x:xs) = (r * x, l * r : ps)
                      where (r, ps) = multiply_peers (l * x) xs

    (Returns [1] for lists with one element)

    There are actually good reasons not to multiply all numbers first and divide afterwards:
    1. The result would be incorrect for lists containing exactly one zero and at least one non-zero number
    2. The full product may overflow even if the values to be returned are in range
    3. You might have associative multiplication but no division for your datatype

35. Michael
    June 16, 2008

    OJ, just ignore the people whining about your language choices. You wanted to try your hand at the problem in Haskell and F#. That is your choice to make, not your readers’. If they can’t read Haskell or F# (I can read the former and can decode the latter to get the gist) that is their problem. They can either choose to expand their horizons or they can choose to not be a part of your target audience.

    What’s next? Blog comments left on a Chinese-language blog complaining about how they can’t read all those funny little pictures? Sheesh!

36. OJ
    June 16, 2008

    @Boomi: That was a really insightful comment The overflow issue has been biting programmers in the butt for yonks and yet they still haven’t learned their lesson. Good to see that someone is mindful of it. Cheers!

    @Michael: Thanks for the backup mate. I do get mixed feelings when I read that kind of feedback. On one hand I don’t want to make it hard for readers to understand the content, but at the same time I want to post whatever I feel like posting. It’s a hard one to nail. At the end of the day I post what I feel like posting in the hope that I can learn from it, and that other people might learn too. If that means I write a Haskell snippet instead of C#, then so be it Your comment is greatly appreciated. Cheers!

37. grahamf
    June 16, 2008

    Division won’t work since there might be a “0″ in the list.  The easiest way is, sweep from left to right, storing the cumulative product in the output array. Then sweep right-to-left with a fresh cumulative product, and multiply the value in the output cell by said cumulative product.  It’s easy and it doesn’t require any extra storage.  This technique is actually used for computing surface areas of bounding boxes during construction of acceleration data structures for ray tracing, so it’s not just an abstract problem

38. OJ
    June 16, 2008

    @Graham: That’s true! I have seen similar implementations of this kind of thing in quite a few areas of graphics/rendering. For some reason I hadn’t made the connection until you mentioned it. Cheers!

39. Kate
    June 16, 2008

    @OJ: I do some functional programming. I’m actually working on a big website right now in C# and linq. I like C because it’s a very simple language, and I was just interested in what a C solution would look like. Functional programming is great for working with large data structures, but you got to be careful when using too much. If you rely on your hammer too much, every problem starts to look like a nail.

40. OJ
    June 16, 2008

    @Kate: C# and LINQ are pretty nifty hey I’m head down in some C# stuff at the moment, but unfortunately we’re using .NET 2.0, so I can’t use LINQ.

    I’m not sure I agree with your point about using Functional Programming “too much”. What is too much? You could use the same argument for Imperative languages, and yet they’re used almost everywhere to drive massive systems end-to-end without any Functional coding at all. Is that too much?

    There are certain things that are easier to write in imperative languages, and same goes for functional. But that doesn’t mean to say that you shouldn’t use one or the other for a certain class of problems.

    I would actually argue that given that the nature of programming is going more towards multithreading due to the number of cores/processors on the desktop increasing, you’re better off using Functional wherever possible. It does a much better job of allowing you to write code that is easier to handle across threads than Imperative languages.

    The thing I really like about F# is the ability to do both where it makes sense without having to write code in two different languages.

    Either way, our points are really the same: make sure you use the right tool for the job

41. Kate
    June 16, 2008

    @OJ: You wrote, “There are certain things that are easier to write in imperative languages, and same goes for functional.” You’re absolutely right. That’s all I meant by my statement. I have heard some people state that we should all move to functional languages and eliminate all loops from our code. I’m not sure how much I agree with that. You mention that functional programming is better for multithreaded applications. I never knew that. Could you explain a little further? Does using functional programming techniques reduce the risks of race conditions and collisions? I would actually think using mutexes and semaphores in a functional language would be as big of a pain as in other iterative languages.

42. OJ
    June 16, 2008

    @Kate: I personally believe that it’s very hard to make a sweeping statement like “We should move to Functional programming and remove all loops”. Anyone brave enough to make that statement better have some really solid arguments to back it up I’m currently in no position to make a statement like that. I hope that whoever said it to you made it clear as to why!

    As far as what I said regarding the use of Functional languages being better for multithreading, I am basing on the the inherent immutability of data in Functional languages. From my experience, most (if not all) of the problems that come out of handling multiple threads is all around access to shared state. Imperative languages are all about shared state and code which has side-effects. Functional programming is all about code that doesn’t have side-effects or mutable state, and hence managing that state across threads isn’t a problem because if it’s shared, it’s not writable. Hence you don’t have race conditions or collisions. Hence, you don’t actually have to use mutexes or semaphores when writing purely Functional code. When you step out of Functional and back into the Imperative world that has side-effects, that’s when you have to start worrying about managing your state again — mutexes and semaphores also come back into play.

    Aside from the issue of threading and managing mutable state, Functional programming is also great as far as testing is concerned. The theory here is that due to the nature of Functional programming, you’re able to mathematically prove that your functions are behaving correctly. This is a topic I’ll be blogging about down the track as I’m still rather scant on the details, but it’s quite exciting! I hope you’re still browsing this site when I get round to that post, as I’d be very keen to get your thoughts.

    Having said all that I don’t think that Functional is a catch all, and most applications do require some level of mutable state. Right now I personally feel that the ideal solution is a mixture of Imperative and Functional — where the former is just a high-level layer over the latter. This is why I’m currently quite excited about the prospect of using F# where mixing the two ideas is very easy. Whether or not it’s a good thing is still yet to be confirmed in my eyes though Cheers!

43. Max
    June 16, 2008

    front,back,n=[1],[1],len(values)for i in range(n-1): front.append(front[i]*values[i]) back.insert(0,back[0]*values[-i-1])output=[front[i]*back[i] for i in range(n)]

44. OJ
    June 16, 2008

    @Max: That’s gotta be python

45. Josh
    June 17, 2008

    I wasn’t able to check every line of every solution, but it seemed like some of these depend on there not being a zero in the original array. For example, the “sweep left, then sweep right” idea fails when there is a single zero (though it works for 2 or more zeros). This is extremely relevant because I just interviewed with a large software company and they asked a variation of this question as part of the interview. The twist was that in their question you were given 2 arrays, the 2nd array being an array of indexes which you were supposed to remove from the result at that position. Example:[1,2,3,4] and [3,1,0,2]gives[6,12,24,8]and [0,2,3,4] and [3,1,0,2] gives[0,0,24,0]Because of who I was interviewing with, I wrote my solution in C#. It centered around first counting the zeros in the first array. If there are none, you sweep left then right as described above. If there is 1 zero, you find the position of that zero, and set it equal to the product of the other numbers, and all other entries are zeros. If you have 2 zeros, you give back a correctly dimensioned all zeros array. My solution looked like this in C#:

    static int[] op(int[] a, int[] b)
    {
      int[] res = new int[a.Length];
      int zeroCount = 0;
      int zeroPosition = -1;
      for (int i = 0; i < a.Length; i++)
        if (a[i] == 0)
        {
          zeroCount++;
          zeroPosition = i;
        }
      for (int i = 0; i < a.Length; i++)
        res[i] = 0;
      if (zeroCount == 0)
      {
        int total = 1;
        for (int i = 0; i < a.Length; i++)
          total *= a[i];
        for (int i = 0; i < a.Length; i++)
            res[i] = total / a[b[i]];
      }
      else if (zeroCount == 1)
      {
        int nonZeroTotal = 1;
        for (int i = 0; i < a.Length; i++)
          if (a[i] != 0)
            nonZeroTotal *= a[i];
        for (int i = 0; i < a.Length; i++)
            if (b[i] == zeroPosition) res[i] = nonZeroTotal;
      }
      return res;
    }

    This is probably not the most elegant solution, but it passed all my test cases.

46. OJ
    June 17, 2008

    @Josh: Thanks for your post! I am a little intruiged by it

    I’m not sure your assumption is correct. The sweep left/right works just fine because the results are accumulated and stored as generated.

    So if you have [4, 3, 0, 1, 2] your “left” and “right” arrays are:
    [4, 12, 0, 0, 0] and [0, 0, 0, 2, 2] respectively.

    For each index you multiply the previous value in the left array, and the next value in the right array (except of course for end-cases where they just have the one value), so your multiplications go: [0, 4 * 0, 12 * 2, 0 * 2, 0], resulting in [0, 0, 24, 0, 0]. This is exactly as expected. It works fine for multiple zeros, and no zeros as well.

    Is there any chance you can point out the flaw in this method? Cheers!

47. OJ
    June 17, 2008

    @Jason: I just thought I’d point you at the real esoteric languages. I can’t see evidence of Haskell or F# in there

48. droz
    June 17, 2008

    C#

    int[] A = { 4, 3, 2, 1, 2 };
    int[] L = new int[A.Length], R = new int[A.Length];
    
    for (int n = 0, m = A.Length - 1; n < A.Length && m >= 0; n++, m-- ) {
    	L[n] = n == 0 ? 1 : A[n - 1] * L[n - 1];
    	R[m] = m == A.Length - 1 ? 1 : R[m + 1] * A[m + 1];
    }
    
    for (int n = 0; n < A.Length; n++)
    	Console.Write("{0} ", L[n] * R[n]);
    Console.WriteLine();

49. ashish
    June 17, 2008

    implementation in python langauge , it can’t get shorter than this.input = [4, 3, 2, 1, 2]output = [ reduce(lambda x,y : x*y , input)/i for i in input],

50. OJ
    June 17, 2008

    @ashish: You haven’t read the question properly. It states that you are not allowed to use division in your answer. Since you’re using division, your solution doesn’t count.

    Also, you should read the comments in the thread regarding the use of division and the issues around it. You end up with issues in the case where one of the items in the list is zero (among others).

51. Ant K
    June 17, 2008

    Sorry I’m not too math minded - what does 0n mean?
    C#

    int[] arr = new int[] {4, 3, 2, 1, 2};
    int[] output = new int[arr.Length];
    for (int i = 0; i < arr.Length; i++)
    {
      int tally = 1;
      for (int j = 0; j < arr.Length; j++)
        tally *= j == i ? 1 : arr[j];
      output[i] = tally;
    }
    return output;

52. Akhil Ravidas
    June 17, 2008

    MUL = 1 ; for ( i from n to 1 ) OUTPUT[i] = MUL , MUL *= A[i]
    MUL = 1 for ( i frm 1 to N ) OUTPUT[i] = A[i] * MUL , MUL *= A[i]

53. OJ
    June 17, 2008

    @Antk & @Ankhil: I’ve fixed up your formatting issues

    I have installed a comment editing plugin, can you please let me know if it’s working for you?

    @Antk: O(n) is an indication of the computational complexity of the algorithm. Check out this page at Wikipedia for a full run-down on Big O notation.

    Cheers

54. OJ
    June 17, 2008

    OK guys, theme changed for a bunch of reasons. Comments now stop stripping + symbols Thanks again for all the great feedback.

55. Ant K
    June 17, 2008

    There’s a load more of these google questions here:-
    http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html

    Something to while away the hours/days/weeks!

56. truth machine
    June 20, 2008

    You people make simple things so complicated:

    #include <stdio.h>
    
    static int in[] = { 4,3,2,1,2 };
    #define N (sizeof(in)/sizeof(*in))
    
    int main(void)
    {
     int l[N] = {1};
     int r[N] = {1};
    
     for( int i = 0; ++i < N; ){
     l[i] = l[i-1] * in[i-1];
     r[i] = r[i-1] * in[N-i];
     }
    
     for( int i = 0; i < N; i++ )
     printf("out[%d] = %d\n", i, l[i] * r[N-1-i]);
    
     return 0;
    }

57. truth machine
    June 20, 2008

    “Sorry I’m not too math minded - what does 0n mean?”

    It means that your solution is too slow, because the number of operations it performs is a (constant) multiple of N*N, i.e., O(N^2), but the problem is to do in in a number of operations that is a (constant) multiple of N, i.e., O(N).

58. truth machine
    June 20, 2008

    “For example, the “sweep left, then sweep right” idea fails when there is a single zero (though it works for 2 or more zeros).

    That’s silly. You really need to sharpen your mathematical intuition.

59. truth machine
    June 20, 2008

    Simpler yet, per grahamf’s “in place” suggestion (except that this sweeps right to left and then left to right, so the results can be output in order without a separate print loop):

    #include <stdio.h>

    static int in[] = { 4,3,2,1,2 };
    #define N (sizeof(in)/sizeof(*in))

    int main(void)
    {
    int out[N];

    for( int p = 1, i = N; –i >= 0; p *= in[i] )
    out[i] = p;

    for( int p = 1, i = 0; i < N; p *= in[i++] )
    printf(”out[%d] = %d\n”, i, out[i] *= p);

    return 0;
    }

60. OJ
    June 20, 2008

    @truth machine: You need to ease up on your tone. People are just having a go at solving the problem themselves. So what if their solutions are “so complicated”? This is a learning experience for all. It’s what blogging is all about. I can’t see how your solution is any more or less simple than many others that have been posted. Get off your high horse mate

61. Keef
    June 21, 2008

    This sounds like the kind of problem that could quite neatly be solved using C++ template trickery or even entirely using the pre-processor in some (nasty) macro.  If I get chance between nappy changes and feeds I’ll give it a go, just for the fun of it.

62. OJ
    June 21, 2008

    Ah yes, finding the time between nappy changes. I remember saying that too It took nearly 4 months to find it!

63. truth machine
    June 21, 2008

    “So what if their solutions are “so complicated”? This is a learning experience for all.”

    I was providing some education.

    “I can’t see how your solution is any more or less simple than many others that have been posted.”

    On;y if you mix apples and oranges. There are some ridiculously complicated C solution. Your own Haskel solution was ridiculously complicated compared to others.

64. Ant K
    June 25, 2008

    @Truth machine - thanks for the 0n explanation - I’ve been looking into it.

    Also, doesn’t your solution use the division operator?

65. qhfgva
    July 17, 2008

    a = [4, 3, 2, 1, 2]
    
    foo = [1]+([1] * len(a))
    goo = [1]+([1] * len(a))
    
    for i, x in enumerate(a):
        foo[i+1] = x * foo[i]
    
    for i, x in enumerate(reversed(a)):
        goo[i+1] = x * +goo[i]
    
    goo.reverse()
    
    print [foo[i] * goo[i+1] for i in range(len(a))]