language shootout / the phonecode study

[Dennis Haupt]

i stumbled upon this:

http://page.mi.fu-berlin.de/prechelt/phonecode/

the results:

http://page.mi.fu-berlin.de/prechelt/Biblio/jccpprt_computer2000.pdf

summary: concise languages bashed c, c++ and java if you look at the time needed to complete the program. however, in 1999, there were no good ides, and there was no lisp implementation. and no scala one, obviously. i intend to see for myself how long i need to solve this using currently available tools and am asking around if anyone would like to participate in my little study. the more, the merrier.

if enough people volunteer i'll set something up

[David Nolen]

Let me know if you want to see a ridiculously concise solution using core.logic ;)

David 

[Dennis Haupt]

what i am really interested in is the time necessary to finish the task.

i'll probably need to modify the requiremet so the participants cannot cheat - or i'll allow cheating deliberately and say "this is the result under optimal conditions" (meaning the raw coding time is measured, no debugging, fixing and so on)

i'll have to think about that

2012/9/20 David Nolen <dnolen...@gmail.com>

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en

[Jules]

This problem would be ideally suited for core.logic except because of the "hint" (http://page.mi.fu-berlin.de/prechelt/phonecode/hint2.html) you'd need to do something far more ugly.

[David Nolen]

On Thu, Sep 20, 2012 at 1:19 PM, Jules <jules...@gmail.com> wrote:

This problem would be ideally suited for core.logic except because of the "hint" (http://page.mi.fu-berlin.de/prechelt/phonecode/hint2.html) you'd need to do something far more ugly.

The solution I came up with doesn't attempt to encode the entire solution in core.logic. Also I admit the solution I came up with was a response to Odersky's neat version for the Scala Days 2011 Keynote and not the original problem.

David 

[Dennis Haupt]

gaaah you almost made me read it

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--

[Dennis Haupt]

i came to a correct solution without that hint :)
just like in reality, i started coding without reading the spec. a few
surprises came along the way ("what? they want it like this? they just
added this to mock me!")

i spent about 50% of the time writing code and 50% thinking about it.
i'll tell my times anyone who solves it as well.
and i'm definately not going to rewrite this in java.... this is crazy....

[Dennis Haupt]

here's my solution:
https://gist.github.com/3766508

the original (done in 2 hours) solution is commented out. i made some
improvements and solved the whole thing in 39 lines (counting only the
content of "main"). doing it in the minimal amount of lines was not my
goal. i was trying to minimize the logic. shorter code was just a side
effect.

try to beat it :). let's see how that looks in clojure.

Am 20.09.2012 19:30, schrieb David Nolen:

[David Nolen]

On Sat, Sep 22, 2012 at 11:27 AM, Dennis Haupt <d.ha...@gmail.com> wrote:

here's my solution:
https://gist.github.com/3766508

the original (done in 2 hours) solution is commented out. i made some
improvements and solved the whole thing in 39 lines (counting only the
content of "main"). doing it in the minimal amount of lines was not my
goal. i was trying to minimize the logic. shorter code was just a side
effect.

try to beat it :). let's see how that looks in clojure.

Looks pretty convoluted ;)

Here's Odersky's Scala version and mine that uses core.logic http://gist.github.com/1107653.

I'm headed to StrangeLoop so I don't have time to verify that the Scala or my version fully satisfies the original problem description. But my guess is that Odersky did really solve the original problem.

David 

[Dennis Haupt]

nice... he approximately does with for loops what i do without the
sugar, hence all the chained calls. i noticed i do a bit more than
necessary (the reverse thing is a remainder of an early
misinterpretation of the spec), but who cares, it works :)

however, odersky's short version doesn't solve the problem ;)
it doesn't:
* handle the - / and " chars
* handle the fallback-case (print a number if no word fits)
* format the output correctly

removing all this from my code, just 2/3 of the current implementation
remain.

i updated my solution, it's a bit more elegant now.

[Jules]

As far as I can see, Odersky also doesn't follow the "hint", and hence does not pass the test cases provided with the original problem. The hint is not really a hint but rather a change to the problem. The original problem is elegant and essentially consists of inverting a clearly defined function that maps word+number sequences to phone numbers. That's why logic programming (and for comprehensions which is a poor man's logic programming) is so good at it. Unfortunately, implementing the problem plus hint pretty much forces you to use the exact same imperative algorithm as he did to generate his test cases. The people in the study also had to do the same, so if you want your code to be comparable with the results in the study that's what you have to do...

Jules

[Mark Engelberg]

I agree that Odersky's version doesn't match the spec.  Hint or no hint, it doesn't look like he even attempts to address the issue of inserting single digits into the encoding.  He's solving a different, somewhat simpler problem.

I don't agree that the hint changes the problem statement.  The original spec is relatively clear about the conditions under which you are allowed to insert a plain digit in the encoding.  I can see how someone might interpret it differently, but it stresses that it's meant to be treated as a local decision -- you can only insert a digit if no word from the dictionary is a leftmost substring of the remaining letters.  The hint simply clarifies what is already in the spec.

Has anyone tried running Nolen's core.logic version yet to see if it works?  At first glance, it looks like it only finds combinations of exactly two words that combine to encode the number, which isn't even the version that Odersky did.

--Mark

[Dennis Haupt]

i did not need the hint to develop a correct solution. the hint just
clarifies what could have been misunderstood.

[Jules]

The spec says if "there is no word in the dictionary that can be used in the partial encoding starting at digit k+1" then a digit can be used. Some people interpreted that as "no word from the dictionary can be used in a solution". Others interpreted that as "no word from the dictionary can be used for a single word addition" :)

Are there other challenges like this study?