• Round One
• Round Two
• Round Three
• Round Four
• Round Five
• Round Six

Let me give round one a try... There must be a better way of doing this...


use strict;
use warnings;
use Algorithm::Loops qw/ NestedLoops /;
use Data::Dumper;

my @patterns = (
        [ 0, 1, 2 ],
        [ 0, 3, 6 ],
        [ 0, 4, 8 ],
        [ 1, 4, 7 ],
        [ 2, 5, 8 ],
        [ 2, 4, 6 ],
        [ 3, 4, 5 ],
        [ 6, 7, 8 ],
    );

while (<DATA>) {
    chomp(my @input = split /\s+/, $_);
    my @combinations = ();

    NestedLoops([ [@input],
            ( sub {
                my %used;
                @used{@_}= (1) x @_;
                return [ grep !$used{$_}, @input ];
              } ) x (2),
            ],
            sub {
                push @combinations, [ @_ ];
                return 1;
            });

    my @output = map { Validate(\@input, $_) ? $_ : () } @combinations
+;
    print "@input:\n", @output ? Dumper(\@output) : "Not possible", "\
+n\n";
}

sub Validate
{
    my ($input, $c) = @_;
    my %p = map { $_ => 1 } @$c;
    my @diff = map { $p{$_} ? () : $_ } @$input;

    foreach (@diff) {
        return 0 if !Canfit($c, $_);
    }
    return 1
}

sub Canfit
{
    my ($c, $e) = @_;
    my @l = map { split //, $_ } @$c;

    foreach (@patterns) {
        my $text = join '', @l[ @$_ ];
        return 1 if $text eq $e || $text eq reverse $e;
    }

    return 0;
}

__DATA__
tan are nan tom men ora
tan are soo and hen oar
tom soo san sop hen ora
[download]


Output:


tan are nan tom men ora:
$VAR1 = [
          [
            'tan',
            'ora',
            'men'
          ],
          [
            'tom',
            'are',
            'nan'
          ]
        ];


tan are soo and hen oar:
Not possible

tom soo san sop hen ora:
Not possible
[download]

-aln $$_=()=/[aeiou]/gi for@F;print"$$_ $_"for sort{$$b<=>$$a||$a cmp$
+b}@F
[download]

3 strokes sh?aved.

#!perl -aln
$$_=y/aAeEiIoOuU//for@F;print"$$_ $_"for sort{$$b-$$a||$a cmp$b}@F
[download]

Using a G-R transform (and assuming less than 9 vowels per word) saves 8 more.

#!perl -an
print+map{/./;9-$&.$'}sort map{9- y/aAeEiIoOuU//." $_\n"}@F
[download]

/-\

Oh, man I'm rusty. Here are a few minor tweaks. For the full version, one less:

$$_=lc=~y/aeiou//for@F;print"$$_ $_"for sort{$$b-$$a||$a cmp$b}@F
[download]

For the "less than ten vowels" version, you can also lose one by getting rid of that space after the "map{9-".

Finally, if they meant increasing order of vowel count and less than nine vowels, then we can do much better ;)

-an print sort map y/aAeEiIoOuU//." $_\n",@F
[download]

Having played in the ACM Collegiate International Programming Contest once in the late 90's, I believe the allowed languages were C++, Java, and maybe Fortran. No one ever used Fortran. Few of us new Perl at the time, but it would have been a tremendous edge.

Our team placed 30th in the region. There was like a 200 way tie for 30th. Yeah, that bad. The regional winning team, I think, solved 3 out of the 6. Do you want to know why? All of those languages are very bad at "glue". Well, ok, that, and our team really didn't study at all -- but that's another point. Good thing was, they had lots of free snickers bars and chips. Free food in college is like gold :)

Perl would have opened up a can of you-know-what on that contest. Half the time we spent doing things that Java or C++ was very poor at, like file I-O and parsing. I think we actually used C++ at the time, since Java was relatively new to us and we wanted to be able to build more complex (specialized) data structures without a lot of casting and so on. That contest was heavy on graph theory, recursion, map traversal, that sort of thing.

I'm an algorithms guy, and I naturally flow to whatever language I can quickly get at the algorithm without having to write a lot of code that isn't related to the problem space.

I'm still kicking myself for not getting question #1. Couldn't code up the intersection of three spheres correctly. Well, at least I've grown smarter over the years.

Anyhow, when you get into college, check out the ACM's ICPC if it's still around. Those programs will blow your head off. Join up with your local ACM or IEEE chapter if you can too -- great for job contacts and learning what the industry is up to.

I've participated twice in the European ACM programming contest (finished one time near the bottom, the other time, we missed being send to the World finals because while we made the "cut" (I think the top 6 or top 8 were to be send), there were too many teams from the same country that finished before us), and those times, the only allowed language was Pascal.

I've also organized regional contests in later years (writing most of the scoring software in AWK - but this was the first time a Perl book appeared on my desk). From what I remember from those times (late 80s, early 90s), the most important aspect in being succesful is terminal time management. You have 4 team members, 6 to 10 problems, and just one terminal. Another, very important, aspect is being able to handle the input border cases correctly. It's very frustrating to get your submission rejected time after time (with no reason or error message other than whether it compiled or not), only to find out the vague wording of the problem allowed for a different input format than you were programming for.

It's a bit easy to say "well, if only we were allowed Perl, then we could have done all the problems with time to spare". That's like saying "if we could make use of a bicycle, we could do the marathon in world record time". A programming contest that allows for Perl to be used can be as hard as one that allows C or Pascal. You just have to adapt the problems. Parsing problems that are tricky to do right in C or Pascal might be easy in Perl. On the other hand, there's much to say for not allowing Perl. You want a contest to be 'all-round', so it should problems that might involve parsing, or searching for strings in a large set. Using tools that already have solved those problems is kind of pointless.

Abigail

I viewed the contest as an algorithmic challenge, not a language challenge. If it were a language challenge, yes, adaptation is crucial -- but, at least to me, Computer Science is about algorithms, not languages. It's important to know your memcpy() and your pointers, but that isn't what computer science is about, per se. Folks are supposed to be able to learn and use any language, and to use them well.

I think you're right about Pascal though. It was Pascal, not Fortran. I had learned Pascal as my first non-BASIC language, though there is no real point of using a language that dogmatic without any decent library functions! Today remember "use crt;" and that's about all the Pascal I know at this point.

The terminal access aspect really stunk. The way our teams were parititioned, I ended up drawing on the whiteboards more than anything, but we suffered at the terminal because other folks could not translate my ideas into code well. So, yes, there was a huge social/time-management aspect to it as well. It's hard working with people that don't work well with you ... a good life lesson, I suppose, if you are into that. (I'm not!)

I kind of liked the impartial rejection messages though. "WRONG!" was all you ever got back from the judges ...

While I agree "using tools that solved the problems already is kind of pointless", I don't see anythign wrong with attacking algorithmic problems with say, just the standard Perl installation (no CPAN).

Though I wasn't ever involved, I particularly liked the race car problem at the ICFP: here. ... language essentially doesn't matter in the contest, thought does.

Heh. The last year I competed in the ACM, we had 4 students in the club, so there were two teams - three freshmen/sophomores on one and me (a third-semester senior) on the other. I placed 12th in my region. :-)

What really annoyed me was that this was after I'd learned Perl and I had to go back to using C++. ICK!

Of course, a few years before me, someone else from my school had his own scribe. He would write the problems out on paper and she would go type them in. (I think he solved 5 problems that year, 4 without errors.)

------
We are the carpenters and bricklayers of the Information Age.

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

Given a sentence, print out each word and the number of vowels it contains. Print them out in order by number of vowels and them alphabetical if same number of vowels.

Didn't we just see an SoPW node about that sort of problem a little while back?

Probably. There was probably also a JAPH posted based on this idea in the Obfuscated Code section recently. Either that or somebody was playing golf with it, trying to get it under 60 characters for a signature without messing up under scrictures and warnings.

In other words, it's a textbook example of the sort of thing that's cosmically easy to do in Perl, because it's exactly the sort of thing Perl was designed to do easily.

---

;$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}} split//,".rekcah lreP rehtona tsuJ";$\=$;[-1]->();print