Slashdot Mirror
$50,000 To Solve the Most Complicated Puzzle Ever
An anonymous reader writes "A team from UC San Diego is using crowd-sourcing as a tool to solve the most complicated puzzle ever attempted, which involves piecing together roughly 10,000 pieces of different documents that have been shredded. (The challenge is designed to reveal new techniques for reconstructing destroyed documents, which are often confiscated by troops in war zones). The prize for solving this jigsaw puzzle is $50,000, which the UCSD team has decided to share among the people who participate. If they win, you would also receive cash for every person you recruit to the effort! The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great"
only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.
Make it $5 million and then I might be interested.
But with how our government has been acting lately, I'm REALLY worried this would somehow be used to further spy on US citizens...
The rules should require that the same method that solved the initial puzzle be successfully applied to 10 more shredded documents, to weed out methods that don't scale.
If there is an offline version of this, it involves a garbage bag full of shredded 5$ bills and some scotch tape.
God spoke to me
I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too. Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?
Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...
Damn_registrars has no butt-hole. Damn_registrars has no use for a butt-hole.
$5 million is closer to the actual effort required to solve the problem, at least for the software, and personally, as a software engineer, I believe the problem to be solvable. Maybe tack on a few more million(s) if you want reliable hardware to scan in the shreds with minimal human effort.
That said, the whole "Hey guys, we're having a contest!" strategy has paid off in the past, the X-prize and Lindburgs flight being prime examples. Hell, Googles "Summer of Code" seems to work out for them nicely. They get a cheap, motivated, enthusiastic labor force.
Being older, wiser, and less motivated, when I hear "contest" I immediately think "I'm busy already, do it yourself."
So, it's essentially worth less than a pack of gum.
Is pulped and / or incinerated. At least, it's supposed to.... few organizations think that shredding is actually an effective way to destroy documents. Unless it is to prepare it for the bonfire.
darpa should team up with mensa and the scientologists
and just when things could not get any stupider
If I come up with a new patentable method (presumably worth a large amount of money), do I retain the IP ownership of it? The FAQ is awfully sparse.
Everyone in the civilized world is worried about what will happen if terrorists gain access to this technology. That's why most nations have signed the Fire Non-Proliferation Treaty, and it's why the International Combustive Energy Agency is working round-the-clock to keep this technology from falling into the wrong hands (while somehow also promoting civilian use of combustive energy).
You've got to be a lot more careful about talking about such restricted technology and its possible uses.
Get Professor Layton on the case, provide some tea and scones, and he'll have it solved in one hour.
Is it just me or does this make little to no sense.
You cannot scale putting together puzzle pieces because the same person needs to both see two pieces that go together and recognize that they match.
So yes more people help, but if there are 10 million pieces then the average person would have to look at over 1 million pieces before they have even seen two that go together.
And this seems like a very easy thing to computise.
You digitize the shredded documents.
You run a program that looks for similarities around the edges.
You stick likely candidates together and either ask for human confirmation or run a text recognition algorithm to see if the result makes sense.
Now this becomes harder if the direct edge of many of the shredded parts are blank, but still more then doable if you use spacing recognition(calc how big a space is in this document and look for the correspond amount of missing space on the other side), line up the text rows, and some basic word statistic (if you see "he ...", for example you are likely looking for a "T" on the right side of another strip).
Troll is not a replacement for I disagree.
...remember the days when /. had actual editors that could catch related or duplicate summaries and either tie them together or throw them out? No? Me either.
Why women always go for the bad guy until he starts beating her,THEN she goes to the good guy she rejected before...
Yeah it's funny, but I wonder, is it's a bit too subtle and edgy. We want people to get it, you know? Maybe you could slightly dumb it down? For the masses, you understand.
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
Where did he get the 10,000 pieces number. From DARPA's website http://www.darpa.mil/NewsEvents/Releases/2011/11/02.aspx, DARPA lists significantly less pieces. "While the first two problems, containing 224 and 373 pieces, were solved manually, automated techniques may be needed to solve problems 3, 4, 5 with 1,115; 2,340; and 6,068 pieces respectively."
This is actually a plot to increase our deficit even more. Imagine...what if the payout was 10 trillion dollars to discover an answer? When does the challenge become so ridiculous that spending time solving a problem that has an adequate substitute like fire, putting it on a hard drive and destroying the drive.
anyone else want to write a bot to constantly click and drag randomly on the flash app? keep that shit scrambled.
... 42
So if i shredded a piece of paper into 10,001 pieces - would *that* then be the most complex puzzle?
It seems that there have solve the first two puzzles already!
And there seems to be another team in the competition: http://www.r-i-software.com/Darpa2/
Just another example of college kids not getting paid enough for their skills. A puzzle solver fresh out of college should be making three times that at least.
Is that a word?
Perhaps "automate" would work.
more cowbell
The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great
No they aren't. It doesn't follow that simply because someone can use crowd-sourcing to solve the problem of finding some stationary weather balloons parked over the USA, that they can also use it to solve (insert arbitrary unrelated problem such as document reassembly here). That's a non-sequitur combined with a fallacy of reference to authority.
On the other hand I'd love to be your bookie if you really think like that.
Didn't even ask to set up a password after clicking "sign up"
What about 600 million shreds from 45 million documents?
Questions raise, answers kill. Raise questions to stay alive.
1. Scan in the fragments
2. Arrange all the fragments in the same direction (the shredder used makes ^ tips)
3. Arrange all the fragments so that everything with paper lines line up
4. Find the edges
5. Start edge matching by luminosity.
The end result should reasonably figure out where the fragments belong, but may still require shuffling the fragments horizontally to get a more accurate picture.
I'd try my hand at coding something that does this, but guess what, DARPA challenge isn't open to non-Americans.
"The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great[.]"
Slashdot: Playing Favorites Since 1997
They figured out just how much America and Britain were fucking them over by "reverse-engineering" all of the incriminating evidence that the Americans furiously shredded before getting the boot from the country they were occupying.
Didn't DARPA offer an exact same reward for solving the exact same problem? If I didn't know any better, I'd say Professor Scammy S. Scamson from the UC San Diego crowdsources the effort, sends it to DARPA, keeps half for himself, half for "contributors", at absolutely no effort.
Perhaps the most complicated puzzle ever in the board-game sense, but for a real puzzle will somebody solve the Riemann Hypothesis so we can all enjoy the beauty of the solution in our lifetime. Now that would be amazing.
'We are trying to prove ourselves wrong as quickly as possible, because only in that way can we find progress.' RPF
it takes less effort, and less time, and less technology, to burn documents than to shred them. If shredding ceases to become useful, it'll take eight seconds before the new fangled algorithm will be useless.
Wasn't the Human Genome Project a much more complicated puzzle with a bigger reward?
...reconstructing destroyed documents, which are often confiscated by troops in war zones...
Or documents recovered from shady businesses.... ENRON anyone?
"That's right...I said it."
Rumor has it that when Iranian revolutionaries captured the then US Embassy in Tehran, they collected the shredded documents and assigned a crack team to try to reassemble them.
Apparently, they're still working on it to this very day :-)
It's all about who has the fastest gun^W lawyer in the West these days. The right team of lawyers will make any patent or copyright, no matter how insane it is, hold up in court. Yes, sure, SCO made a booboo there, but there are plenty of examples to support this.
I was promised a flying car. Where is my flying car?
I'll pay $50,000 to whoever removes all the fucking javascript so I don't have to click on every single post to turn them black so I can read them.
In order to reconstruct shredded Stasi files Germany funded research to find a solution.
http://www.spiegel.de/international/germany/a-482136.html
>> which are often confiscated by troops in war zones
Translation: confiscated by the IRS when visiting your office.
Always keep some bogus lookalike documents together with the real ones,
and shredding them blends them to a real mess too large and too complex to reassemble.
(Perhaps i've said too much...)
As far as I know, German Fraunhofer Institute has a solution for this kind of problem: http://www.ipk.fraunhofer.de/component/content/category/167-autsicherheitstechnikstasischnipsel (p.8ff, German language).
Looks like they have few problems assembling torn pages, and geometrically correct results for shredded paper (yet not necessarily correct content).
"Too hard for computers, let's turk it out for 50 cents per person." Guess what, Fraunhofer have been doing this for years.
http://www.erosionpollution.com/small-scale-incinerators.html
No, this is not my Grandpa's burning barrel, but it sure looks like it.
The machine we have at home shred the paper in fine line, throw it on a fire, it burns very VERY well. Maybe I should patent that : a portal incinerator connected to a shredder.
C. Sagan : A demon haunted world:
http://www.amazon.com/gp/product/0345409469/
visit randi.org
The real problem the government is trying to solve is of course putting together the shredded pieces in such a way that suits them most :)
I guess that will be the next challenge.
If Pandora's box is destined to be opened, *I* want to be the one to open it.
unless the shredded pieces are thoroughly mixed, there is a /lot/ of information contained in the location of the pieces relative to each other in the pile of shredded pieces. If someone captures shredded documents, every effort should be made to avoid disturbing the pile, or at least to bag it with some order.
A German company solved this exact problem years ago, when trying to find a way to reconstruct documents of the former East German Staatssicherheit that had been shredded.
Oh, and they're not dealing 10000 pieces various documents, they're dealing with 10000 bags full of pieces of shredded documents. Crowd-source that.
It's easy. Just find the person that shredded the document, lock them in a room at Guantanamo, and torture them until they re-assemble it.
.... that can be solved by a good script?
(reconstructing software like that must already exist within forensics, no?
Obviously shredding isn't safe anymore...
My girlfriend lives about 1.5 blocks from Warren Buffet, so if you take the per capita for the two blocks between Warren and her, she's a billionaire! :)
Unfortunately, she's having a hard time coming up with the money for a transmission for her Kio Rio. So statistics suck and are very misleading...
...why don't folks just burn the documents instead of shredding them? Think of the advantages - you don't need a shredder, you don't need electricity to run a shredder, and most important, if you burn your secret docs, then there is a much lower chance that someone can come along and reconstruct them after the fact.
The problem is only peripherally like a jigsaw puzzle. While it is possible to attack certain portions of the assembly problem using automated methods (namely breaking the chads into individually manipulatable pieces and - perhaps - suggesting pieces), the basic problem is serial in nature. In the latter puzzles such as #4 an #5, the primary issues are:
- the chads are offset with respect to one another
- the pages have been shredded slightly skewed
- the edges are poorly defined
- the top and bottom edges often overlap slightly due to the cut/rip angle that chops the strips into chads
- the shape of the chads have often been warped during the scanning process
But worst of all, given a particular chad, a human or computer must predict the appearance of the adjacent chad and then find it among thousands of possible candidates. Even after narrowing down the search by categorizing the chads into whatever groups seem useful, you often end up with multiple chads that will *exactly* fit in place. By that I mean that the writing appears - pixel for pixel - to continue onto the next chad. While one would think that human handwriting documents would be highly random, they aren't. We tend to use the same line angles when connecting cursive letters, crossing our t's or other writing gestures and this causes a high degree of commonality in the graphics at the magnified level of the chads at which we are working.
But wait, it gets worse - if you misplace a chad, you have actually created *two* errors in the document - the misplaced chad and the (now missing) chad where it *should* have gone. In a crowd sourced solution with many inexperienced eyes working part-time, it is my opinion that many of these types of errors will be introduced, preventing a solution. For this reason - and for this particular challenge - I think it will actually be won by some masochistic puzzler with some image-manipulation skills.
Genome sciences laughs at your cereal box puzzle.
All bets are off if the shredding is crosscut.