Problem 287

[elr]

is the picture at the problem page represent D2 ?

[jaap]

No, D2 has a different pattern of white/black pixels. The picture is only to explain the coding scheme.

[elr]

oh,it would have been much more useful if D2 was displayed instead of some arbitrary picture

[elr]

could someone please verify for me that a minimal sequence for D5 having a length of 499 ?

[jaap]

could someone please verify for me that a minimal sequence for D5 having a length of 499 ?

Yes, I think that's correct.

[Fogmeister]

I'm not going to beat any speed records with my program but it's going to get the right answer (I think). It does for smaller values of N anyway. (My only problem might be overflow issues).

For anyone else who has solved it what kind of run times do you get? I've been trying to think of a more efficient algorithm than the one I have but struggling to think how it can be done any other way?!

I've searched for quad tree stuff but nothing has jumped out at me yet.

Lol, will be interesting to read the other solutions.

[Marcus_Andrews]

Without any sort of optimizations other than the "crucial" one, it shouldn't take more than a minute or two in C++. There are other optimizations you can use that'll bring total runtimes down to less than a second.

[Fogmeister]

OK, when I said I wasn't going to break any speed records I really wasn't joking.

By iterating up through N I've just calculated how long it's likely to take for N = 24...

485... days.

I think I need a better solution.

[Fogmeister]

Without any sort of optimizations other than the "crucial" one, it shouldn't take more than a minute or two in C++. There are other optimizations you can use that'll bring total runtimes down to less than a second.

Thanks, I'll need to re-think my strategy.

ATM, it uses a very human strategy to work it out.

I calculates N=5 in 0.003 seconds (ish) and then N=13 takes 9 seconds, N=14 about 40 seconds, N=15 takes 171 seconds.

So I'm looking at an approximate increase of about 2^2 each time. Which makes perfect sense looking at the problem.

[Marcus_Andrews]

Try outputting intermediate steps of your program and see if there's anything you can exploit.

[tomboy]

This problem really vexes me. I am convinced my solution is correct (and it runs nicely in ~10 seconds in Haskell for D24), yet my solution for D5 varies extraordinarily from the 499 that were posted here earlier.

So I followed my algorithm by hand - and got the same solution of 128 for D5 that my algorithm spits out.
Hence I reckon my method of counting is flawed.

Could someone confirm the following counts for me for D5 for the first 4 subquadrants: 30, 44, 23, 30 + 1 = 128 - or give me the correct numbers?

[thundre]

Could someone confirm the following counts for me for D5 for the first 4 subquadrants: 30, 44, 23, 30 + 1 = 128 - or give me the correct numbers?

156 + 128 + 128 + 86 + 1 = 499

Your numbers for those (2⁴)² quadrants match mine for some of the (2³)² quadrants in D5.

[tomboy]

okay, was a stupid typo. i checked for <= 2^(N-2) instead of <= 2^(2N-2).

But now the performance went down. Takes 8minutes for D20. Now let's see how we can optimize that...

[yourmaths]

Hmm...

It seems like each encoding can refer to different images. For example, 011101010 could refer to both:

ox
xx

as well as

ooxx
ooxx
xxxx
xxxx

(here o represents white and x represents black squares). The larger image could be enforced by splitting one of the 2x2 squares but then that encoding could also represent an 8x8 image and so on.

Does this matter?

[sjhillier]

I think you're right that if you were using this as a genuine image encoding scheme, you'd also have to specify the size, which is not contained in the code itself as described here. However, for the purposes of this problem, we do know N, so the problem is completely determined, even if the encoding scheme is not complete for practical purposes.