News for hackers. Stuff that matters.

A comment on Instagram Engineering Challenge: The Unshredder. Parent comment

Re:Instagram Engineering Challenge: The Unshredder by webfuel on Saturday November 12, 2011 @12:21PM (#3228250)
Minor spoiler/hint:

My algorithm, given a strip, would tell you which strip was on the right and also gave a certainty. The last strip would have a "next strip" value shared with an earlier strip (thus wrongly attached) but with less certainty.

Edit: Or (worst case) the last strip would have a high degree of uncertainty.

[ Parent | on HN ]
Re:Instagram Engineering Challenge: The Unshredder by asharp on Monday November 14, 2011 @04:46AM (#3233472)
That's what stable marriage is for. With some reasonable heuristic it should just give you the best partial ordering, which when flattened into a total ordering should give you the most likely picture.

How do you calculate your certainty?

[ Parent | on HN ]
Re:Instagram Engineering Challenge: The Unshredder by Luyt on Saturday November 12, 2011 @01:50PM (#3228513)
Currently I'm using a matrix to determine adjacency, but I'll give this graph idea a try. Thanks for the tip!

PS. Have you actually realized a succesful implementation? (Just curious)

[ Parent | on HN ]
Re:Instagram Engineering Challenge: The Unshredder by webfuel on Saturday November 12, 2011 @02:42PM (#3228683)
No problem! Yes, I have this working:

http://webfuel.org/instaunshredderv2.php

It also works on the test images I created:

http://webfuel.org/a.png http://webfuel.org/b.png http://webfuel.org/c.png

[ Parent | on HN ]
Re:Instagram Engineering Challenge: The Unshredder by s3ththompson on Saturday November 12, 2011 @04:23PM (#3228954)
This is exactly how I implemented my solution. The worst case scenario is important because some images have last strips that have a unique "next strip" value.
[ Parent | on HN ]