Re: Programming Contest

[Al Christians <alc@PublicPropertySoftware.com>]

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