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

Yay!

[webcowgirl.livejournal.com]

Nice to have you back. The pictures emarkienna had of you were stunning - you're so gorgeous in the shiny with your hair down! I was sitting at work with my mouth hanging open. Wish I'd been there.

Did ergotia and lilithmagna not make it there at all, or just not go out?

[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.

[sparklegoth.livejournal.com]

Bloody hell! That is some outfit!

[shevek.livejournal.com]

Trivial thought. It's bounded below by len(sequence) - count(shifts) - 2. There are local optimisations for both ends and for local alternations, but I don't think you ever need to consider a subsequence of length < 3 or 4. But I am rushing through on my way somewhere and will look later and prove it. Now am thinking that local optimisations give len(sequence) - (count(shifts) / 2) - 2 but have not proven that yet.

[biog.livejournal.com]

Super-nice outfit *drool*. Wish I could make it to Whitby more often, circumstances etc. Still, you look stunning :)

[mskala.livejournal.com]

At a glance this looks like a job for dynamic programming, but I think it can actually be done in linear time if you do this:

Compute, for the first k tiles, the optimal solution that DOES and the optimal solution that DOES NOT have a match in the last position.

From those two solutions it's easy to compute a similar pair of solutions for the first k+1 tiles.

Repeat until you've done all the tiles, then keep whichever of the two solutions you have, is better.

The big advantage: you can prove the above correct without needing to prove that a (potentially long and complicated) list of pattern-matching templates is correct and complete.

[grlleastlikely.livejournal.com]

i love the outfit. very becoming.