Whitby goodness

[ciphergoth]

I had a lovely Whitby - a little more muted than usual, partly because of colds at our end and partly because of colds very sadly keeping ergotia and lilithmagna from joining us, but very nice all the same. My Friday night outfit was particularly well received, and will no doubt be reprised.

Now I'm obsessing with trying to get a paper ready by November 25 for FSE 2006. I have to keep a little quiet about what I'm doing until January 27th, since submissions are anonymous, but, it's cool.

Update with a geek puzzle: here's a simple game. I lay out a set of tiles that say Y or N; say I lay out

NYYNYNN

You lay the same number of tiles underneath:

NYYNYNN
NNYYNNN

The rules are: (1) if a tile is the same as the one above, you have to lay the same tile to the right. So you're not allowed to lay

NYYNYNN
NYYYNNN
-^- not allowed: because the first column is N N, you must lay N as your second tile.

(2) you get a point every time you lay a tile which is the same as the one above.

NYYNYNN
NNYYNNN
1010011 - four points

The least you can score is always zero: it's always a legal move to lay tiles which differ in every place from the ones above. What's the best you can score for NYYNYN, and how many ways can you do it? Can anyone give an algorithm which determines the highest you can score, or which generates all of the possibilities which give you a given score?

Comments

[drdoug.livejournal.com]

Is the number of tiles fixed - i.e. is it always seven?

The least you can score is always zero: it's always a legal move to lay tiles which differ in every place from the ones above

Err ... isn't it always one? You can always score one by laying tiles which differ in every place but the right-hand one.


It looks like the problem ought to be related to adding but I can't make the connection.

If the number of tiles we play with is always seven (or even just small), my first choice for an algorithm to find the highest score would be simple brute force, sad to say! With only a little bit-twiddling for each instance it's not going to take long, and I'm usually more confident in the completeness of brute force algorithms than more subtle ones.

[ciphergoth.livejournal.com]

No, you can have any number of tiles, so brute force isn't enough. I've implemented a brute force solution to experiment with it, but I need something faster.

You can always score zero with the strategy I describe; you can always score 1 with the strategy you describe. Actually I think you can always score at least ceil(n/2): choose the letter which appears most often above, and lay that down in every place below. If the tiles are alternating then that's the best you can do.

There is a connection with adding, but it's pretty longwinded.

[drdoug.livejournal.com]

No, you can have any number of tiles, so brute force isn't enough.

Shame.

You can always score zero with the strategy I describe; you can always score 1 with the strategy you describe.

Agreed.

Actually I think you can always score at least ceil(n/2): choose the letter which appears most often above, and lay that down in every place below. If the tiles are alternating then that's the best you can do.

Reckon so. That's a nice strategy - it does well in lots of circumstances. Presumably you want a solution that'll outperform that when possible? I'm not finding any immediately to hand.

[ciphergoth.livejournal.com]

It's definitely possible to do better: consider

NNNNNNNNNNYYYYYYYYYY
NNNNNNNNNNnYYYYYYYYY

(using a lowercase "n" to mark a choice where you don't score a point)

I think a greedy strategy (if you're forced to put a letter, put that, else put what's above) does pretty well - it may even be optimal. But I haven't proven it yet, and even if it is, it only finds one best solution, not all of them.

[emarkienna.livejournal.com]

The greedy strategy is what I was thinking too.

My reasoning was to break the sequence up into blocks of "one or more Ys followed by an N", and "one or more Ns followed by a Y" (any remaining Ys or Ns treat as a special case), and then show that in the first case an optimal sequence for that block is all Ys, and similarly therefore for the second case an optimal sequence is all Ns. Since you've ended with a different letter, you are free to choose the first letter for the next block, so it should be possible to treat the blocks independently. Though I may have missed something or made some assumptions.

The only time an alternative solution is possible if the block is either NY or YN - we can try YY or NN, but that constrains us to keep the same letter for the next choice ... So it can be seen that a block of NYY can have YYY as a solution instead of NNY (and similarly YNN can have NNN instead of YYN). I think that shevek's solution is the greedy solution except with these two substitutions made.

I'm not sure how to prove that these are the only possible substitutions. If they are, then it ought to be possible to find all possible solutions by spotting sequences of NYY and YNN and writing all possible combinations with each of these sequences having either of the two solutions?

So for NYYNYNN, the best would be NNYYYYN (score 4). There is 1 sequence of NYY and 1 of YNN given 3 other solutions: YYYYYYN, NNYYNNN and YYYYNNN.

And you were looking very beautiful at Whitby!