Isn't B3 a bit too simple ?

[naholyr]

Don't you think B3 is too simple... I made the script in 3 hours. It finds the best solution (in the example, it solves it in 9 ms).
Whereas i did not have time to finish B2, this time i got it hardly it has begun...

Well anyway, for the ones who have ideas about great algorithms, take care of these two examples:

onebigword alittle smallword,
wodonbigalittlsmall.

washingmachine bigmachine washingcar,
washing machine bi ca.

you may find 36 if you are ok to compete.

Originally posted by naholyr@1-June 03, 02:25 PM
you may find 36 if you are ok to compete.

Sure, 36 is my result too, I just have to optimize speed now

[Mr. Sketch]

Originally posted by naholyr@1-June 03, 08:25 AM
Don't you think B3 is too simple... I made the script in 3 hours. It finds the best solution (in the example, it solves it in 9 ms).
Whereas i did not have time to finish B2, this time i got it hardly it has begun...

In short: NO!
I made a script in a short amount of time too to find the 'best' solution. However, the 'best' solution requires taking each word against all the remaining words to find the longest text. However, since taking one big word, could end up using letters that could be used by two smaller words and those two smallers words together could be bigger than the one big word. Consider the example:
class function objects hypertext preprocessor,
object hypetext prepocesor.
An algorithm that just picks the longest word it can make (and then next longest etc) would pick preprocessor, however if it picked hypertext and objects it would result in more letters. This yields an O(N!) algorithm and since we can have up to 20 words that's 20! which is ~2.4e18 which would take a while, so that algorithm is only scaleable up to about 9 words.

This problem is non-trivial and should not be easily dismissed as a simple algorithm. I've been working on this since the day it was posted (about two weeks or so) to get a sub-optimal algorithm but will work well in most cases and I think I've found an O(N^3) algorithm that should be sufficient for this contest.

[naholyr]

i got it in O(N!) (on the number of words) and in an example like:

onebigword alittle smallword washingmachine bigmachine washingcar string constant variable sausages class function objects hypertext preprocessor,
wodonbigalittlsmall washing machine bi ca tstnacon bleiangrav igtni ksiypappsle sslas nyyoitcf teztxrpyhre krtbhwopqowo jksksjajajahshshj.

it's solved in less than three seconds...
and it has 15 words...

http://naholyr.dyndns.org/~contest/index3.php

[stuart]

Originally posted by naholyr@3-June 03, 09:03 PM

onebigword alittle smallword washingmachine bigmachine washingcar string constant variable sausages class function objects hypertext preprocessor,
wodonbigalittlsmall washing machine bi ca tstnacon bleiangrav igtni ksiypappsle sslas nyyoitcf teztxrpyhre krtbhwopqowo jksksjajajahshshj.

it's solved in less than three seconds...
and it has 15 words...

http://naholyr.dyndns.org/~contest/index3.php

Just need to point out a small error wit h you example - the rules state that word should be ordered by character count, so you need to put the largest word first, and the smallest word last.

[Mr. Sketch]

Originally posted by naholyr@3-June 03, 03:03 PM
i got it in O(N!) (on the number of words) and in an example like:

onebigword alittle smallword washingmachine bigmachine washingcar string constant variable sausages class function objects hypertext preprocessor,
wodonbigalittlsmall washing machine bi ca tstnacon bleiangrav igtni ksiypappsle sslas nyyoitcf teztxrpyhre krtbhwopqowo jksksjajajahshshj.

it's solved in less than three seconds...
and it has 15 words...

I see. I've been trying to figure out how you could examine 1.5 trillion combinations in ~3 seconds, and it appears that your algorithm must be order dependant so you didn't really have to examine all 1.5 trillion combinations. After changing the order of my inputs, it easily did that one in 3 seconds. So, I bellieve you may still have some work to do. Try something like:

mozilla string constant variable sausages class function objects hypertext preprocessor php perl slashdot newsforge yahoo google odsn linux slackware mandrake,
string constant variable sausages class function objects hypertext preprocessor mozilla php perl slashdot newsforge yahoo google odsn linux slackware manke.

There's 20 words, but only 19 can be used, you should get at least 132 which is what I get with my sub-optimal algorithm in ~12 seconds (on a 600MHz).

[ciaccia]

Originally posted by Mr. Sketch@5-June 03, 03:28 AM

mozilla string constant variable sausages class function objects hypertext preprocessor php perl slashdot newsforge yahoo google odsn linux slackware mandrake,
string constant variable sausages class function objects hypertext preprocessor mozilla php perl slashdot newsforge yahoo google odsn linux slackware manke.

There's 20 words, but only 19 can be used, you should get at least 132 which is what I get with my sub-optimal algorithm in ~12 seconds (on a 600MHz).

To be honest I'm getting 135 on this...

[Mr. Sketch]

Originally posted by ciaccia@12-June 03, 11:53 AM
To be honest I'm getting 135 on this...

Yeah, after some tweaking I was getting 135 too but my first run on it was only getting 132, oh well. I guess in a few days, I'll get to see how it does against everyone else. /me crosses fingers

[cagrET]

>> Each line is at most 80 characters long.
>> Sentences may occupy more than one line, and are terminated
>> by a full stop.

ur examples are bad, cause u have to many words (80 characters long)

>> Just need to point out a small error wit h you example - the
>> rules state that word should be ordered by character count,
>> so you need to put the largest word first, and the smallest
>> word last.

i forgot about it too
wanted to send my submission in a few minutes

>> To be honest I'm getting 135 on this...

my script cant do this in 200 seconds
funny, i dont get idea how to speed it up :P

onebigword alittle smallword washingmachine bigmachine washingcar string constant variable sausages class function objects hypertext preprocessor,
wodonbigalittlsmall washing machine bi ca tstnacon bleiangrav igtni ksiypappsle sslas nyyoitcf teztxrpyhre krtbhwopqowo jksksjajajahshshj.

result: 82
right ?

Originally posted by cagrET@14-June 03, 11:42 PM
result: 82
right ?

I also get 82, but it takes some time on my PPro test server.

I have no time to optimize speed right now, I think I'll subit my script as-is-now