Programming Contest

Programming Contest

[Al Christians]

I received the following by email this a.m.

> Hello, everyone.  While the MSO programming contests are on hiatus, I
> started one of my own.  It only awards $100 and it isn't nearly as 
> prestigious, but it'll keep your gray cells (and your silicon ones) in > practice.

> Visit http://members.aol.com/DrMWEcker/REC.html and then, in the 
> column on  he left, click on the fifth link ("NEW Prize Contest!").

Is this problem worthy of Ada?


Al

Re: Programming Contest

[Larry Kilgallen]

In article <3B59BF1E.DB25E3DC@PublicPropertySoftware.com>, Al Christians <alc@PublicPropertySoftware.com> writes:
> I received the following by email this a.m.
> 
>> Hello, everyone.  While the MSO programming contests are on hiatus, I
>> started one of my own.  It only awards $100 and it isn't nearly as 
>> prestigious, but it'll keep your gray cells (and your silicon ones) in > practice.
> 
>> Visit http://members.aol.com/DrMWEcker/REC.html and then, in the 
>> column on  he left, click on the fifth link ("NEW Prize Contest!").
> 
> Is this problem worthy of Ada?

If they will announce the name of the winning language, yes.

Re: Programming Contest

[David C. Hoos]

The conjecture is false.

----- Original Message ----- 
From: "M. A. Alves" <maa@liacc.up.pt>
To: <comp.lang.ada@ada.eu.org>
Sent: Monday, January 11, 1999 2:29 PM
Subject: Re: Programming Contest


> Conjecture: Solution (greatest possible smallest unattainable score)  =
> Greatest_Attainable_Score + 1, i.e. the set of attainable scores
> associated with Solution has no holes (i.e. all scores below Solution are
> attainable).
> 
> Is anyone sure this conjecture is false? (No proof asked :-)
> 
> -- 
>    ,
>  M A R I O   data miner, LIACC, room 221   tel 351+226078830, ext 121
>  A M A D O   Rua Campo Alegre, 823         fax 351+226003654
>  A L V E S   P-4150 PORTO, Portugal        mob 351+939354002
> 
> 
> 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
> 

Re: Programming Contest

[AlZimmerma]

Mario,

Thank you for your interest in the Darts Contest.

> ". . . the 5 areas have values (1, 2, 4, 7, 11). Then the smallest
>  unattainable score is 27."
>  
>  I don't get it.  If the three darts hit 11, isn't the (attained) score 33?
>  
>  And isn't the smallest unattainable score = largest attainable + 1?
>  
>  And so wouldn't values (Infinity, ...) be a trivial solution to any N?
>  
>  What am I missing?

It isn't true that smallest unattainable score is exactly one more than the 
largest attainable.

In the example, you are correct that 33 is the largest attainable score.  But 
there are a few scores smaller than 33 which cannot be attained.  And 27 is 
the smallest of these.

To see this, observe that scores from 1 through 26 are demonstrably 
attainable:

    1 = 1
    2 = 2
    3 = 1 + 2
    4 = 2 + 2
    5 = 1 + 4
    6 = 2 + 4
    7 = 7
    8 = 1 + 7
    9 = 2 + 7
    10 = 1 + 2 + 7
    11 = 11
    12 = 4 + 4 + 4
    13 = 2 + 4 + 7
    14 = 7 + 7
    15 = 4 + 11
    16 = 1 + 4 + 11
    17 = 2 + 4 + 11
    18 = 7 + 11
    19 = 4 + 4 + 11
    20 = 2 + 7 + 11
    21 = 7 + 7 + 7
    22 = 11 + 11
    23 = 1 + 11 + 11
    24 = 2 + 11 + 11
    25 = 7 + 7 + 11
    26 = 4 + 11 + 11

But there's no way to attain 27.

Please let me know if this doesn't answer your question.

Al Zimmermann
  

Re: Programming Contest

[Al Christians]

AlZimmerma@aol.com wrote:
> 
> Mario,
> 
> Thank you for your interest in the Darts Contest.
> 
> > ". . . the 5 areas have values (1, 2, 4, 7, 11). Then the smallest
> >  unattainable score is 27."
> >
> >  I don't get it.  If the three darts hit 11, isn't the (attained) score 33?
> >
> >  And isn't the smallest unattainable score = largest attainable + 1?
> >
> >  And so wouldn't values (Infinity, ...) be a trivial solution to any N?
> >
> >  What am I missing?
> 
> It isn't true that smallest unattainable score is exactly one more than the
> largest attainable.
> 
> In the example, you are correct that 33 is the largest attainable score.  But
> there are a few scores smaller than 33 which cannot be attained.  And 27 is
> the smallest of these.
> 
> To see this, observe that scores from 1 through 26 are demonstrably
> attainable:
> 
>     1 = 1
>     2 = 2
>     3 = 1 + 2
>     4 = 2 + 2
>     5 = 1 + 4
>     6 = 2 + 4
>     7 = 7
>     8 = 1 + 7
>     9 = 2 + 7
>     10 = 1 + 2 + 7
>     11 = 11
>     12 = 4 + 4 + 4
>     13 = 2 + 4 + 7
>     14 = 7 + 7
>     15 = 4 + 11
>     16 = 1 + 4 + 11
>     17 = 2 + 4 + 11
>     18 = 7 + 11
>     19 = 4 + 4 + 11
>     20 = 2 + 7 + 11
>     21 = 7 + 7 + 7
>     22 = 11 + 11
>     23 = 1 + 11 + 11
>     24 = 2 + 11 + 11
>     25 = 7 + 7 + 11
>     26 = 4 + 11 + 11
> 
> But there's no way to attain 27.
> 
> Please let me know if this doesn't answer your question.
> 
> Al Zimmermann
> 

It looks to me like this is a problem of searching a huge search
space for a good solution.  Anyone have any idea if there is any 
non-brute-force way to construct or find the solutions? 

Has anyone in this group used Ada to solve such problems?   Any
features of Ada that made it particularly well-suited?  

I'm guessing that Lisp and similar languages might be better for
writing a program, but that Ada would run a little faster so you
could search more in a given time.  In particular, Ada is probably
much better at pulling a slice out of a list (array) than most of
the functional languages, and this might make Ada much faster at
generating and evaluating solutions.  

Any ideas what would work best -- genetic algorithm, simulated 
annealing, or ???


Al

Re: Programming Contest

[tmoran]

>It looks to me like this is a problem of searching a huge search
>space for a good solution.
  But the contest asks for a solution for any N.  That sounds more
like an algorithm or method than a particular programmed implementation.

Re: Programming Contest

[Tucker Taft]

Al Christians wrote:

>
> It looks to me like this is a problem of searching a huge search
> space for a good solution.  Anyone have any idea if there is any
> non-brute-force way to construct or find the solutions?

This looks like a problem ripe for "dynamic programming" solution.

>
> Has anyone in this group used Ada to solve such problems?   Any
> features of Ada that made it particularly well-suited?

Dynamic programming can be implemented in almost any language.

>
>
> I'm guessing that Lisp and similar languages might be better for
> writing a program,

Actually, probably most dynamic programming systems are programmed
in Fortran!  In any case, in this kind of system, I don't think Lisp has
anything over Ada.  The place where a language like Lisp shines is where
you actually want to manipulate bits of program within the language itself.
This problem seems like one which just needs a good data structure to support
the dynamic programming solution.  Basically, you start with a very simple
problem,
solve that by a smple search, and then build up solutions of more complicated
problems using results saved away for solutions to smaller problems.

> but that Ada would run a little faster so you
> could search more in a given time.  In particular, Ada is probably
> much better at pulling a slice out of a list (array) than most of
> the functional languages, and this might make Ada much faster at
> generating and evaluating solutions.
>
> Any ideas what would work best -- genetic algorithm, simulated
> annealing, or ???

As mentioned above -- dynamic programming.


>
>
> Al

-Tucker Taft  stt@avercom.net

Re: Programming Contest

[Al Christians]

Tucker Taft wrote:
> This problem seems like one which just needs a good data structure to > support the dynamic programming solution.  Basically, you start with a > very simple problem, solve that by a simple search, and then build up 
> solutions of more complicated problems using results saved away for 
> solutions to smaller problems.
> 

That's what I'd hope would work.  But is there any logical reason to 
suggest that hope will actually lead us to a good solutions for this 
particular problem?  If I have an optimal solution for a board with n 
regions, how do I know that there is any similarity between that
solution and an optimal solution for a board with n+1 regions?  My
intuition gives me a strong maybe on that question.

I suppose that for small numbers of regions a complete search is
not beyond possible, and that maybe if we saw similarity of 
successive solutions when the number of regions is small, we could
extrapolate that the similarity continues up to n=25.  

I don't have time for this, but it looks like too much fun to pass
up.


Al

Re: Programming Contest

[Larry Kilgallen]

In article <3B5B8A53.837D8384@PublicPropertySoftware.com>, Al Christians <alc@PublicPropertySoftware.com> writes:
> Tucker Taft wrote:
>> This problem seems like one which just needs a good data structure to > support the dynamic programming solution.  Basically, you start with a > very simple problem, solve that by a simple search, and then build up 
>> solutions of more complicated problems using results saved away for 
>> solutions to smaller problems.
>> 
> 
> That's what I'd hope would work.  But is there any logical reason to 
> suggest that hope will actually lead us to a good solutions for this 
> particular problem?

Given that the original premise was to get some publicity for Ada,
this may be a situation where "good enough" will do.  If many have
the reservations expressed in the previous paragraph, it could be
that the best entry will be the only entry :-).

Re: Programming Contest

[Al Christians]

Tucker Taft wrote:
> 
> This problem seems like one which just needs a good data structure to > support the dynamic programming solution.  Basically, you start with a > very simple problem,  solve that by a smple search, and then build up > solutions of more complicated problems using results saved away for > solutions to smaller problems.
> 

From my simple testing, this looks like a dead end.  By brute force
search for the optimum solution, I find, for example, that the fourth
lowest board region scores 8 when there are 4 regions, 14 when
there are five regions, 9 when there are 6 regions, and 15 when there
are seven regions, 10 when there are eight regions.  Knowing the answer
for six is not much help for finding the answer to seven, etc.  

Six regions takes about 1 second to figure out, seven takes about 20
seconds to figure out, eight takes about 10 minutes.  So, I don't think
that brute force is going to solve this one up to 25 regions.


Al

Re: Programming Contest

[Tucker Taft]

Al Christians wrote:

> Tucker Taft wrote:
> >
> > This problem seems like one which just needs a good data structure to > support the dynamic programming solution.  Basically, you start with a > very simple problem,  solve that by a smple search, and then build up > solutions of more complicated problems using results saved away for > solutions to smaller problems.
> >
>
> From my simple testing, this looks like a dead end.  By brute force
> search for the optimum solution, I find, for example, that the fourth
> lowest board region scores 8 when there are 4 regions, 14 when
> there are five regions, 9 when there are 6 regions, and 15 when there
> are seven regions, 10 when there are eight regions.  Knowing the answer
> for six is not much help for finding the answer to seven, etc.

Dynamic programming does not generally require that the optimal
solution for N is always part of the optimal solution for N+1.  However,
it is certainly the case that *some* solution for N is part of the optimal
solution for N+1.  The challenge is to retain as few solutions as possible
from the "N" level to still guarantee that the optimal solution for
the N+1, N+2, ... levels can be composed from it.

In this case, the trick is to throw away some of the N solutions because
they are so obviously "bad" that they couldn't possible appear in
an optimal solution for more than N areas.

For what it is worth, my initial attempt is not selective enough.  Although
I can get up to eight areas in a minute or so, I have yet to get past there.

>
>
> Six regions takes about 1 second to figure out, seven takes about 20
> seconds to figure out, eight takes about 10 minutes.  So, I don't think
> that brute force is going to solve this one up to 25 regions.
>
> Al

-Tucker Taft stt@avercom.net

Programming contest

[Martin Dowie]

We walk the walk but can we talk the talk...

http://cristal.inria.fr/ICFP2001/prog-contest/

Re: Programming contest

[Ehud Lamm]

Martin Dowie <martin.dowie@nospam.baesystems.com> wrote in message
news:3b4c3608$1@pull.gecm.com...
> We walk the walk but can we talk the talk...
>
> http://cristal.inria.fr/ICFP2001/prog-contest/
>

Yeah. Notice that the machine used for running the contest entries, has Gnat
3.13 installed.


--
Ehud Lamm   mslamm@mscc.huji.ac.il
http://purl.oclc.org/NET/ehudlamm <==  Me!

Re: Programming contest

[Cailean Nicholas Pól Gloucester]

Martin Dowie wrote "We walk the walk [..]".

Actually I was thinking of taking a train to the multi-language
infrastructure and 
interoperability workshop Babel
(http://research.microsoft.com/~nick/babel01.htm) in 
Firenze (connected to the contest) but the local organisers in Italy (not
Nick in Microsoft) have not proven to be very good at caring after somebody who 
asked repeatedly about becoming a delegate.