WEEKEND PROGRAMMING CHALLENGE ISSUE-1 RESULTS


Image

We got 20 solutions of our first problem. Amazingly the first one come in 2 hours after we posted the problem!

Here is the ISSUE#1 recap:

Number of Languages used:  8

Fastest written solution: SOLUTION-1, done in less 2 hours after the problem posting

Smallest code solution: 7 lines (SOLUTION-15, Python)

Fastest execution solution: TBD we have to test these

All solutions are uploaded to GitHub: https://github.com/OLIMEX/WPC/tree/master/ISSUE-1

Now we will have really hard time to rise winner with so many submissions, we will try all solutions today and tomorrow will announce our winner.

You can help us! If you have favorite solution you can e-mail us with the arguments why do you think this is best solution, so more eyes can check better🙂

26 Comments (+add yours?)

  1. Hendrik Lipka
    Mar 25, 2013 @ 11:57:32

    I think you need to re-do your lines-of-code calculation to count only the real code, not test nor documentation. I know that at least my version is only 3 “real” lines (one for the function header, two for the calculation as such). Documentation and test are about 20 lines each…
    Apart from that I would have no real preference for a ‘best’ solution (even though I found the solution using GNU Octave somewhat cool)

    Reply

  2. Iain Cunningham (@IainIsm)
    Mar 25, 2013 @ 12:50:45

    Interesting to see how many of the entries don’t consider what happens if A=B or B=C or even A=B=C😉

    Reply

    • OLIMEX Ltd
      Mar 25, 2013 @ 13:32:51

      agree, then go figure why more and more programs we use every daily have so much bugs🙂

      Reply

    • Emiliano Daddario
      Mar 25, 2013 @ 14:15:20

      If B==C, then the distance is just 0.
      However, nice point (of discussion)😉
      If A==B, you are right, there exists an infinite number of lines passing through both A and B.
      In this case, does the user either prefer the line to be undefined, or multiply-defined? That is the question.
      So your program could either answer “multiply-defined value”, that is, the distance between C and one of those lines, or answer “undefined value”, which in this case is the same as “undefined line”, depending on the user requirements.
      Due to this uncertainty and an headache, my program just returns zero if A==B, I just worried about avoiding division by zero😀

      Reply

      • Emiliano Daddario
        Mar 25, 2013 @ 14:26:54

        “a headache”
        P.S.
        +1 to Iain Cunningham’s program for using free software

      • Iain Cunningham (@IainIsm)
        Mar 25, 2013 @ 16:37:28

        I can’t reply to your ‘PS’, but thank you!

        For A==B then another alternative approach (which I took) is that you can assume a ‘line’ is able to be defined with zero length and then return the distance between A and C (or B and C, which is the same thing).

        For the vector algebra method I employed this “just” places a constraint on the calculation of the unit vector: “When A=B, i.e. the unit vector is undefined, then the unit vector defining the line direction must contain zeros, and not ‘NaN’s” (to mean that its dot product with any other vector becomes zeros too).

        I actually left this constraint out of my in-line documentation for distPt2Line.m, which is very naughty of me as now there is nothing to prevent someone attempting to use some other unit vector function with my code other than this blog comment and the errors that will result if they try it and ever provide a zero length line! Hopefully the unit tests will save them though…

        A side-benefit of this approach is also to avoid having to make a decision over when a line expressed by floating-point (or fixed point) co-ordinates becomes a point and vice-versa.

      • Hendrik Lipka
        Mar 25, 2013 @ 16:56:38

        @Iain: the original problem description said explicitly: “Points A and B define endless line”, so it a) cannot be a zero-length-line (which btw. would then be called ‘a point’) and b) A and B must be distinct, because otherwise the line would not be defined.

      • Emiliano Daddario
        Mar 25, 2013 @ 17:04:42

        @Iain Cunningham: yes, I saw that your code returns norm(A-C) when A==B; this is because, as you said, you just substituted the null vector in the formula you used, that is, the one which is also on Wikipedia, to get along.
        I see you made the substitution at line 35 in getUnitVector.m

        myUnitVect = zeros(size(A));

        There are infinite lines passing through A and this way you are arbitrarily choosing the particular line among these which is perpendicular to AC segment. Or to put it another way, you are calculating the distance between A and C.
        One could even return a random number for the case A==B, that’d be enough for the challenge.🙂

      • Emiliano Daddario
        Mar 25, 2013 @ 17:08:58

        @Hendrik Lipka: I agree that A and B must be distinct, for the sake of the challenge, and I simply cared about avoiding division by zero. Let’s just don’t care about A == B🙂
        But he didn’t mean a “zero-length line”: he just meant that he substituted the null vector in place of the unit vector which defines the direction of the line (if any). I looked at his code.

      • Iain Cunningham (@IainIsm)
        Mar 25, 2013 @ 18:33:19

        @Hendrik I don’t want to get too much into the semantics, but points A and B define a segment of an endless line. I just chose that as a special case the segment could have zero length (and therefore undefined direction for the whole endless line). Of course, having made this argument then I accept that it’s probably true that returning “NaN” (or even “NA” in Octave) for the distance may be preferable to giving the distance from the point C to the point-segment-AB… but then again “any sufficiently advanced bug is indistinguishable from a feature”! So yes, I agree with Emiliano – let’s not care about this ‘special case’!

  3. Emiliano Daddario
    Mar 25, 2013 @ 13:36:52

    Oh no, I don’t have the time now to read the solutions of the other people, and tell which ones are my favourite!😦 I hope I’ll manage to write it later, before the winner is announced, so that I can help the best one to win🙂
    I’ll have to ask someone to explain the VBScript solution to me, because I don’t know that language🙂

    Reply

    • OLIMEX Ltd
      Mar 25, 2013 @ 13:59:15

      Most of MS Windows viruses are written in VBScript🙂 my first thing when I sit on Windows machine is to delete cscript.exe as usually none else than viruses use it (sorry Luca🙂 )

      Reply

    • Luca Dentella
      Mar 25, 2013 @ 21:53:49

      Ciao Emiliano,

      you’d be surprised by how many useful scripts Windows sysadmins write in the old-variant-typed vbScript😉

      Reply

  4. Emiliano Daddario
    Mar 25, 2013 @ 15:12:02

    My favourite solutions are Solution-15 for the original algorithm and the short code, and Solution-7 because it uses an algorithm similar to my solution (I’d like to ask him what algorithm did he use; I calculated the same determinant as him recursively with tail-call optimization just for fun, the absolute value of it is the volume of the parallelepiped which has OA, OB, OC as sides, where O is the origin, then I divided by 6 to get the volume of the associated tetrahedron ABCO, then I divided it by one-third of the height of the tetrahedron relative to base triangle ABC. That height is 1, that is why the matrix has 1’s, this is a dirty mathematical trick to obtain the area of the triangle ABC, then I divided it by one-half of the base AB, and I got the height of ABC relative to base AB, which is the required distance. I repeat, I complicated it just for fun, maybe mine is the worst solution in terms of shortness🙂 ).

    Reply

    • Emiliano Daddario
      Mar 25, 2013 @ 15:31:32

      P.S. I know that there are far faster formulas for determinant than the recursive one (not to mention that determinant is not needed to get the distance); I made tail call optimization as an exercise, not for performance reasons.🙂

      Reply

  5. Ian k Rolfe
    Mar 25, 2013 @ 18:22:21

    For the case A=B my routine (Solution 8) returns the result as if the line was vertical (i.e. line of the form x=). This was because I had to trap the special case anyhow to avoid divide by zero errors, and if A=B then any answer is as wrong as any other! If I was coding in a language with exceptions like Python, Java etc rather than C it would be more appropriate to raise an exception.
    And the challenge also explicitly mentioned that AB was a line, not a point or line segment!

    Reply

    • Emiliano Daddario
      Mar 25, 2013 @ 18:39:24

      If you coded in Scala, then you could also return an Option[Float], which can be assigned the special value of “None” for the case A==B. In C# you could use a nullable type which is a bit different. You could throw a custom exception in those languages as well.
      But I coded in Scala and I didn’t do it🙂 I only avoided divide by zero errors

      Reply

    • Iain Cunningham (@IainIsm)
      Mar 25, 2013 @ 18:47:40

      Yes, but in Euclidean space (or a Euclidean plane) with Cartesian coordinates the line AB must be finite for the coordinates defining it to be real and finite. So therefore AB can only be a segment of the “endless line” mentioned by the challenge. [At least if we only consider an answer assuming a Euclidean plane/space – if we break that assumption then some really ‘interesting’ answers and discussions become possible!]

      Reply

      • Emiliano Daddario
        Mar 25, 2013 @ 19:01:23

        If the problem didn’t say “endless line”, then your algorithm (return norm(A-C) if A==B) would be the most appropriate.

      • Iain Cunningham (@IainIsm)
        Mar 25, 2013 @ 19:34:52

        @Emiliano Oh, I agree, to an extent – see my reply to Hendrik above. I wasn’t clear in my reply who I was replying to though (I didn’t see your reply before I posted), I was just responding to Ian’s statement that “AB was a line, not a point or line segment”.

  6. Emilio Moretti
    Mar 25, 2013 @ 20:02:26

    @Emiliano, thanks for noticing I used sagemath (I thought I was the onlyone reading other people solutions).

    I found solution 15 very cool. But I wish more people knew about sagemath. It’s awesome.

    PS: I didn’t know how you were going to evaluate the solutions. Next time I’ll try to optimize it differently. I won’t pay attention to code readability. You have been warned!😛

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: