Mathematicians in the forum?

My maths are bad. I are not capable to compute maximal posible score in the crossword puzzle contest

If the 20x20 grid is fit with 40 words of 20 letters each:

40 words * 5 points = 200 points
400 connectors * 3 points = 1200 points
400 filled in spaces = 400 points
Total score: 1800 points

But scores can be better... If one of these 400 letters in the center of grid is reemplaced with a space, then:

42 words * 5 points = 210 points
399 connectors * 3 points = 1197 points
399 filled in spaces = 399 points
total 1806 points

With more spaces, they are more words, and then the score can be better... Just for curiosity, can anyone calculate the theorical best posible score?

Àngel

I think this is correct:
242 words = 1210
260 connectors = 780
280 filled spaces = 280
total = 2270
If that's not it, it's very close.

B

on further review I believe the answer to be this:

244 words = 1220
267 connectors = 801
280 filled = 280
total = 2301

This is what it would look like:
O = letter
X = blank

OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OXOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OOOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OOOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OOOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OOOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
XOOXOOXOOXOOXOOXOOOO
OOOOXOOXOOXOOXOOXOOX
OOXOOXOOXOOXOOXOOXOO
OOOXOOXOOXOOXOOXOOOO

This makes me think that the score schema was not very good.
The best crossword should have the least unfilled squares, so the 40 20 letter words should have the best possible score.
The '5 points per word' schema gives more points to the more words, thus leading to a 'word-ladder' solution more than a crossword.

Thanks bakertrg. Really looks optimal. I know i myself had been able to solve this problem with a little patience and plotting paper, but I am not able to verify if the solution is really optimal, for that, a maths knowledge is need.

And also, if all the rules of original Matt's contest must be applyed, this is a much more hard problem... Remember: a max of 200 words in wordlist.txt is in the rules...

With 200 max words, this can be the a solution:

0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 .
. 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0
0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 .
. 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0
0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 .
. 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0
0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 .
. 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0
0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 .
. 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0
0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0
0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0 0 . 0 0

200 words * 5 = 400
284 connectors * 3 = 852
300 filleds *1 = 300
total 2152 points

but again, i am not able to verify if this is optimal...

quoting gatopeich


I agree.

Àngel

bakertrg:
all the words have to be connected. your example doesnt qualify.

All the words are connected. If you look close you'll see that there is one missing X in every row of blanks (X's)running NW to SE. The code I wrote to figure this out verified that every NON X square can be reached from every other NON X in a contiguous path.

Incidently I don't have the math skill to figure this out either but I intuitively knew what the layout would look like based upon the scoring so it was easy to write some code to maximize the outcome. The first time I didn't tell the code to look for a maximal value when removing 1 X from each row so it came upa little short. It still could be off by a small margin because I didn't do this mathmatically I just told the script to draw a grid based upon OOX, phase shift every row one space, then go back and remove an X from every angular row and compute the total score.

To verify all words are connected I told the script to compare the vertical and horizontal neighbors of every O and trace a path back to the top left square stopping as soon as it found a square that had already been verified.

B

oops.. didnt see that
my sincere apologies