Weekend Programming Challenge ISSUE #4 – Solutions


Image

This Weekend Programming Challenge have record submissions, either the problem was very easy either WPC gain popularity.

Whatever the reason is I’m glad so many people like this challenge and spent time to solve it.

I count total 30 solutions, some of them very elegant, some of them very short (I still bang my head to understand what this one line AWK shell script solution does )

I learned, while reading some of these solutions, hopefully you will enjoy them too.

The first solution was submitted again by Dylan in less than hour after the problem posting, he does this second time and appear one of the fastest programmer I’ve seen! He wrote that to write the code took him 6 minutes, then to find the isogram code scanned the text for 12 minutes 🙂
Looking at his code I’m telling myself that it’s about time to learn Python. What my embedded nature deny to accept is that he uses enumerate which doubles the used memory (variable i is never used) but who cares for memory when Alice in the wonderland is less than 150KB

the code successfully finds the longest Isogram in the text ‘curtseying’

Dylan seems didn’t stop there as some hours later he sent me longest Isogram he found on other text: altnorwegisch, bildvorschauen, komplizenschaft, uncopyrightables, unproblematisch, so I guess he is scanning the web now to find longest Isogram on the Internet

These solutions catch my attention:

Solution-4 is made in pure C and tolerate any files, scanning for ASCII, you can run it on binary files too

Solution-10 is only 7 lines in Python, I wish I could understand why Python allows such language constructions,  after all it appears it’s not only C where you can write obfuscated code

Solution-12 is in Ruby and only 4 rows of code

Now here are the exotic languages:

Solution-6 is written in CoffeScript, this is my first encounter with this language, very small and compact code, obviously no file operations to the input was embedded in the source

Solution-9 is written in Rebol

Solution-11 written in Linux Bash scripting

Solution-15 written in Flex C

Solution-21 written in Snobol – text processing language from 1970s

Solution-24 AWK – 1 line solution WOW

Solution-29 x86 assembler(!)

Solution-30 Scala

the ISSUE#4 recap: 30 solutions

Python 9
Java 2
C 2
C++ 2
CoffeScript 2
C# 1
PHP 1
Rebol 1
Bash 1
Ruby 1
Clojure 1
Flex C 1
Snobol 1
AWK 1
Assembler 1
Scala 1

19 Comments (+add yours?)

  1. Dirk Porsche
    Apr 15, 2013 @ 11:03:32

    Just for clarification. File operations are possible and easy. CoffeeScript is basically translated to JavaScript and runs on Node.js. That’s a full blown environment.

    I omitted file operations because of simplicity.

    I was even more tempted to scrape a web page, whose URL would be the programs command line parameter, for the longest isogram, then to actually access files. Which would have made the program about three lines longer.

    Reply

  2. Trackback: Free Online eBook – How to Think Like a Computer Scientist (Learning with Python 3) | olimex
  3. Emiliano Daddario
    Apr 15, 2013 @ 11:08:31

    Actually, there are two solutions in Scala, and not one as you stated. My second solution is the same as the first but rewritten in only 1 line (without semicolons) and roughly ten times smaller. Thanks.

    Reply

  4. luke4oxnet
    Apr 15, 2013 @ 12:35:07

    I like #4, upper-case conversion. Btw: don’t you think.that adding the rule about the input format accepted by the solutions, may help in testing them ? Maybe it is good idea to ask either for standard input or the file name with input vector as the argument? I try to test and compare few of the solutions, but it is not so easy now, I have to check the code to see what input format is accepted.

    Reply

  5. Ian k Rolfe
    Apr 15, 2013 @ 13:28:25

    Lesson 1 I learned from the programming challenge was to read the question properly! My SNOBOL lists all the isograms, missed the whole “longest” bit from the question. Which is a shame, because it could have been a whole lot shorter….
    Hey Ho – theres always next week….

    Reply

  6. Trackback: The language of our ancestors | Few words about Linux and embedded devices
  7. frafra
    Apr 15, 2013 @ 16:17:53

    About solution #10: it’s not obfuscated, just a bit compressed.
    Line 9: substitute with a space if the character is in punctuation (list comprehensions – PEP 202 – with an inline little if condition)
    Line 10: “”.join(clean).lower().split() means: transform the list into a string, put everything lowercase, and then split. It’s like a = “”.join(clean); b = a.lower(); c = b.split(), nothing more.

    Reply

  8. ignisf
    Apr 15, 2013 @ 17:08:19

    Clojure is written with a “j” 🙂
    http://clojure.org/

    Reply

  9. Emiliano Daddario
    Apr 15, 2013 @ 23:27:45

    My favourite is solution #12 (actually he wrote two versions, a short one and a longer one), because only two lines of code do the real work and it’s still legible. Solution #24, though being the shortest in terms of character count, is not one line long. In fact if a one-liner program contains semicolons, it’s like it had more lines, since semicolons with or without newlines after them are treated the same by many languages.

    Reply

  10. Dylan
    Apr 15, 2013 @ 23:58:00

    I’m looking forward to challenge #5 already but I’m sure many can match my speed, but simply started the challenge later.

    That said, despite using Python – which I am relatively new to – my algorithm was actually a straight translation from Pascal (which does ‘set of char’), and rather lazy (in non-technical CS terminology).

    An assembler or C program scanning over the entire string in order could use a single 32 bit word to store the set ‘a’-‘z’ using bitwise shift operations. My Python solution imitated setting a bit. Clearly that bit can be tested too 😉 In asm or C the logic should be to pass on when two identical characters are detected.

    Finally, I’m not very experienced in Python, but the reason it is lovely for this kind of “quick solution” is similar to the way Pascal reads so easily as pseudocode compare to the C group.

    Reply

  11. notzed
    Apr 20, 2013 @ 06:36:30

    Aren’t there actually 6 “longest” words? Curtseying is just the first one at that length.

    complained
    croqueting
    curtseying
    educations
    flamingoes
    scrambling

    I wrote up a couple of solutions but didn’t send them for various reasons. First was in Java as I just use that lately, which downloaded the html file via http, ignored tags, supports utf8, prints all words of the same maximum length (in sorted order) and removes duplicates. And a local-text-file only version in perl because I thought that should fit the problem, but my perl is rather rusty so it was a bit ugly and slow (and c-like), but it’s just short enough to include below.

    #!/usr/bin/perl

    sub match {
    my $c = shift(@_);
    my $word = shift(@_);
    my @matches = $word =~ m/($c)/g;

    $#matches == 0 ? “” : “1”;
    }

    $best = “”;
    %bests = ();
    while () {
    #print;
    chop;
    for $word (lc =~ m/([[:alnum:]]+)/g) {
    my $tmp = $word;
    $tmp =~ s/(.)/match($1,$word)/ge;
    if ($tmp == “”) {
    if (length($word) == length($best)) {
    $bests{$word} = $word;
    } elsif (length($word) > length($best)) {
    $best = $word;
    %bests = ($best => $best);
    }
    }
    }
    }

    print “longest:\n”;
    for $best (sort keys %bests) {
    print ” $best\n”;
    }

    Reply

  12. Trackback: Weekend Programming Challenge ISSUE #4 – Solutions | olimex | A Pressed World

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: