2 ms·

Thanks for the helpful critique. Your proposed algorithm is reasonable and much, much faster than simulated annealing, and I appreciate the live demo. It looks

by nayuki 10y ago

Thanks for the helpful critique. Your proposed algorithm is reasonable and much, much faster than simulated annealing, and I appreciate the live demo. It looks like your algorithm is deterministic (except for tie-breaking of a pair of columns that have the same difference?), so it doesn't matter which way the image is shuffled. You are also correct that I overstated how hard the problem is; in retrospect it isn't that hard at all to unshred clean digital images (as opposed to paper scans). On your web page: > It takes roughly the same amount of time to run but correctly reconstructs all of the images. This is not true, but is very close to correct. The image "Blue Hour in Paris" has some disturbances in the lower part of the sky, "Alaska Railroad" has a single wrong column on one side of the image, and "Abstract Light Painting" sometimes has a few incorrect columns on the edge. At least that's what I could spot by eye at a glance; I didn't rigorously compare them against the original images.

foob 10y ago
First off, thanks a lot for posting this and you did a great job with it! It was fun to play around with and it obviously inspired me enough to dig into the code and try my own variation. You're right about them not matching exactly; I did it in a hurry and wasn't looking closely enough. I removed that incorrect statement (though it does seem to generally outperform the simulated annealing). The tie breaking for pairs with equal differences and the parity of the image is essentially random. It is deterministic in the code, because it won't replace a candidate unless it's strictly better, but it's totally arbitrary which is found first.