CODEWITHSUNDEEP
algorithm
akash
akash

Reputation: 1801

Re-arrange the picture

This question was asked in a recent interview. please suggest something:

A picture of 16x16 is divided into pieces with sizes of 4x4 (16 pieces) and shuffled. Suggest an algorithm to rearrange it back.

Upvotes: 0

Views: 201

Answers (4)

Sanjeev Satheesh
Sanjeev Satheesh

Reputation: 424

Assuming nothing is available expect the pixels of the pieces, this is a great approach at solving it probabilistically

http://people.csail.mit.edu/taegsang/JigsawPuzzle.html

Upvotes: 0

Dinesh P.R.
Dinesh P.R.

Reputation: 7236

I hope each of these pieces will have a identification (like a number to order/rearrange them). I can think this problem as a analogy to Reception of UDP Packets(Usually UDP Packets might get received out of order and then we need to order them.)

So any sorting algorithm should work.

Please correct me if I have misunderstood the question.

Upvotes: 0

user1168577
user1168577

Reputation: 1973

Without going into the Pixel matching algorithms, I think I would take a Dynamic Programming bottom up approach here. First find 8 sets of 2 pieces which are most likely adjacent and then try to build the whole thing from the smaller subsets.

Upvotes: 0

Alex
Alex

Reputation: 694

If it's a software engineering type of problem and you divide it yourself you can cheat and store each location with each piece. ;)

They're probably looking for some pattern-matching solution though. Perhaps compare the last row of pixels on each side (top/bottom/left/right) with the other (horizontal/vertical) sides (with a certain tolerance). Each side will get a certain score against the others, progressively matching until all are done.

Upvotes: 1

Related Questions