×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

$50,000 To Solve the Most Complicated Puzzle Ever

samzenpus posted more than 2 years ago | from the gather-the-edge-pieces dept.

Math 180

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"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

180 comments

only 50k for a problem that complex? (5, Insightful)

Anonymous Coward | more than 2 years ago | (#38080972)

only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.

Re:only 50k for a problem that complex? (0)

Anonymous Coward | more than 2 years ago | (#38081064)

agreed ...

Fifty cents a person (3, Insightful)

tomhudson (43916) | more than 2 years ago | (#38081096)

To complete this new challenge, it could take as many as 100,000 people

So, it's essentially worth less than a pack of gum.

Re:only 50k for a problem that complex? (1)

TaoPhoenix (980487) | more than 2 years ago | (#38081126)

This is almost the same as the DOD $50,000 "challenge" to recover shredded docs remember?

So what did they do, spin it from the "Bad Dept of Defense" to "a college group"?

AC nailed it, tech that can do that is "worth" billions in lifetime revenue, so what's with this $50,000 a piece?

Re:only 50k for a problem that complex? (5, Informative)

Yaur (1069446) | more than 2 years ago | (#38081320)

It is exactly the same. This is just a team attempting to solve that challenge by crowd sourcing document assembly.

Re:only 50k for a problem that complex? (1)

icebraining (1313345) | more than 2 years ago | (#38081226)

Copyright is automatic. What prevents them from taking the $50000 and then making millions off of it?

Re:only 50k for a problem that complex? (2)

History's Coming To (1059484) | more than 2 years ago | (#38081312)

Copyright is irrelevant, this is a patent situation. And if the technique (in this case crowdsourcing) is obvious and pre-existing then you can't patent it.

This solution is a bit of a hack - it's not what the $50,000 is actually meant for, they're looking for an everyday computer-based method. Fair play to them and all though.

Re:only 50k for a problem that complex? (0)

Anonymous Coward | more than 2 years ago | (#38082028)

Even the patent is worthless in terms of protecting it. The customer that would find the most use of the code would be the US Government. They get a free ride when it comes to patents. I know from first hand experience in a device I - nevermind, I better stfu now and post AC....

Re:only 50k for a problem that complex? (2)

gumbi west (610122) | more than 2 years ago | (#38082352)

The US Government does not get a free ride when it comes to patents. They may disregard a patent for national security purposes. For example, when the antrhrax attacks were underway the maker of the patented first line drug did not have sufficient quantities of the drug and the USG basically said, "then make them or we will do it for you and not give you a licensing fee." They did not do this, but that is the type of situation where they can override a patent, not like, "hey, nice shiny thing... I'll just take that then."

Re:only 50k for a problem that complex? (1)

Forbman (794277) | more than 2 years ago | (#38081388)

Better send the $50K to Iran, as they were able to do it in 1978...Oh, wait, that involved computors, not computers.

Doesn't IBM have some algorithmic tech that can help with this? I imagine it involves scanning each strip, and figuring out a way to do some sort of edge analysis of each strip, for each side. Do some sort of FFT or DCT for the edges, and then come up with a way to join similar strips' edges for each side of the strip together. Then, run the joined images of likely sets of strips through an OCR to see if any letters come off of the strips. Then, join further sets of those strips together, perhaps a few more times, before you probably run things in front of people to accept or reject.

Perhaps more than one strip could be scanned at once and digitally "separated" from that initial image...

Are there possible clues to doing this in "Rainbow's End", by Vernor Vinge?

Re:only 50k for a problem that complex? (2)

Relayman (1068986) | more than 2 years ago | (#38082460)

You've got the method, now implement it. My understanding is that you are provided with TIFF files of the scans. However, there may be smudges and oil from the shredder.

Re:only 50k for a problem that complex? (1)

stephanruby (542433) | more than 2 years ago | (#38081434)

I'm not sure copyright would give you the protection you'd want. Copyrighting an algorithm is almost impossible, depending on which national legal jurisdiction you're in. And patenting could be expensive, and that too is not full-proof either (especially for a little guy like myself).

Personally, I'd offer this as a paid service online, and I'd let whichever government had jurisdiction over me -- buy me out (before they just confiscate it away from me without proper compensation).

Re:only 50k for a problem that complex? (1)

stephanruby (542433) | more than 2 years ago | (#38081512)

On second thought, if I had the software for doing that, I'd offer it as a paid service online, but then I'd pretend I had a thousand low wage workers in India printing out each little strip of paper and reassembling it painstakingly by hand. This way I could count each worker as a separate contractor on my invoices and charge a corresponding large commission for each.

Re:only 50k for a problem that complex? (2)

Fluffeh (1273756) | more than 2 years ago | (#38081616)

Copyrighting an algorithm is almost impossible, depending on which national legal jurisdiction you're in. And patenting could be expensive

Oh yes, we developed this lovely little algorithm, we want to patent it. Can someone spot us $50k to pay for patent bills?

Hey, maybe that's where you could use that $50k in prize money?

Re:only 50k for a problem that complex? (0)

Anonymous Coward | more than 2 years ago | (#38081730)

Fool-Proof. Not full-proof.

It's a pet-peeve, sorry.

Re:only 50k for a problem that complex? (1)

Sulphur (1548251) | more than 2 years ago | (#38082026)

only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.

Or it could be like a paper on pursuit curves that gets classified quickly.

In Falcon and Snowman, there was a scene of paper and water being put in a blender to shred the paper.

Re:only 50k for a problem that complex? (1)

fluffy99 (870997) | more than 2 years ago | (#38082282)

Except crowdsourcing isn't really an algorithm. You're just getting thousands of eyeballs helping to mix/match the piece like a giant jigsaw puzzle. Not exactly something you can sell as a product.

Re:only 50k for a problem that complex? (1)

Relayman (1068986) | more than 2 years ago | (#38082454)

Actually, the rules say that you do not have to reveal your method or give up any intellectual property to claim the prize.

To be shared? Shared with who... (1)

Adult film producer (866485) | more than 2 years ago | (#38080980)

Make it $5 million and then I might be interested.

Re:To be shared? Shared with who... (2)

fsckmnky (2505008) | more than 2 years ago | (#38081080)

$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."

Call me paranoid (1)

Anonymous Coward | more than 2 years ago | (#38080986)

But with how our government has been acting lately, I'm REALLY worried this would somehow be used to further spy on US citizens...

Re:Call me paranoid (1, Insightful)

Anonymous Coward | more than 2 years ago | (#38081694)

It would be used against US citizens, and against people in foreign countries who just wish to live their own lives peacefully and who are fighting the US military invasion of their country. I'm thinking Iraq mostly here: while at first the war was against Saddam and his supporters, today the war is being fought against average Iraqi people who have lost too many relatives as 'collateral damage' and who are so fed up with the USA that they decided to join the insurgents to avenge their lost family and boot the USA out so that 'collateral damage' stops once and for all.

Over 100,000 civilians have died in the war one way or another (compare this to 24000 Insurgent deaths and 4500 US military deaths). Whether they were killed by suicide bombings or US troops, they'd be alive today if the war had not happened. So I'm sure everyone can understand that some of these people are pissed of enough to fight the US military.

And frankly, I think the USA are responsible for every single death. They wanted to start a war, fine, but they needed to guarantee some damage control. It was easy to predict how civilians would be endangered. None of the reasons for the war provided by the USA justify such a huge civilian death toll (unless you only care about the interests of the USA of course, but I like to think even the average American can think of the greater good).
Helping the US military in any way is criminal and should not be done. Shame on those who will participate in this "contest".

Re:Call me paranoid (0)

Genda (560240) | more than 2 years ago | (#38082166)

Excuse me... who modded this parent? Dick Cheney? We had no sane justification being in Iraq (save making Dick and his baby HELL-iburton a couple Peta-Bucks.) There wasn't a single insurgent or Al-Quaida member in Iraq before 2001, the Sunnis were in charge and keeping the Iranian Shiites at bay and we had a whole host of tools at our disposal to enforce global justice while we pursued only the criminals and stomped all over Global Terrorism.

Instead we became the world's largest terrorist state (even going so far as to spy on our own people and gut the Bill of Rights.) We made Iraq a wholly owned subsidiary of Iran. We killed thousands of innocent bystanders going all gansta on a country that had nothing to do with 9-11. We got our own kids all blown to hell, so Dick and his good buddies could get even wealthier than they already were. If we aren't responsible for the disaster that Iraq is, who the hell is???

For the love-o-Jebus will someone please mod the parent up!

Re:Call me paranoid (2)

Raiford (599622) | more than 2 years ago | (#38082092)

Hardly of any concern for a citizenry that post everything about themselves on facebook.

Doesn't scale (4, Insightful)

Anonymous Coward | more than 2 years ago | (#38080992)

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.

Get CmdrDildo to do it (-1, Flamebait)

Anonymous Coward | more than 2 years ago | (#38081022)

I hear that bitch is crying about not having a job. "Boohoo.... I don't know what to do with my life since I have no real skills. Boo hoo.... I'm a cunt who no one wants around."

Re:Get CmdrDildo to do it (1)

TheVelvetFlamebait (986083) | more than 2 years ago | (#38081432)

CmdrDildo

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.

Shredding vs. burning (3, Interesting)

Anonymous Coward | more than 2 years ago | (#38081040)

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?

Re:Shredding vs. burning (2)

ZeroSumHappiness (1710320) | more than 2 years ago | (#38081404)

Really, you could do both. And you should use a setup similar to a cremation device instead.

Re:Shredding vs. burning (3, Interesting)

GumphMaster (772693) | more than 2 years ago | (#38081604)

Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

Re:Shredding vs. burning (2)

Black Parrot (19622) | more than 2 years ago | (#38081908)

Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

I bought a cheap home shredder about a year ago, and it crosscuts. Makes reassembly unimaginably more difficult. (I think mine produces more like 2mm wide, but still.)

And if you don't have an incinerator, just pour the crosscut confetti into a recycle bin where all your other documents go. If you think reassembling one document would be difficult, consider starting from a bucket where the scraps of dozens or hundreds of documents are mixed indiscriminately.

Re:Shredding vs. burning (2)

dakohli (1442929) | more than 2 years ago | (#38082072)

Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

Actually, a quick check of online regs [doe.gov] states that the maximum size must be 1mm x 5mm. When you use an approved shredder, the pieces are very small, producing thousands of bits per page. The magnitude of this challenge is huge.

In some cases the challenge will be to determine just which side is up. If the document was double sided, then the order of difficulty will increase greatly.

Re:Shredding vs. burning (4, Informative)

arth1 (260657) | more than 2 years ago | (#38081422)

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.

What happens is that the top and botom pages and edges get scorched, but the middle part with the print remains largely intact.

Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

Thus speaks someone who hasn't tried to burn more than a couple of sheets of paper.
It takes time to burn more than a few pages at a time. Or an extremely hot fire. Sorry, Mr Bradbury, 451 F won't do it, unless you can wait for weeks.

Re:Shredding vs. burning (1)

dakohli (1442929) | more than 2 years ago | (#38082104)

I have operated a purpose built incinerator designed to burn documents. We collected the material in burn bags, operators were encouraged to crumple up the paper. Each night, the bags were fed into the incinerator, which used diesel fuel to start the burn. A couple of time per hours, the ashes were mixed, and more bags introduced. It took time, but I can assure you, that all of the docs were destroyed each night.

Eventually, environmental issues shut down the incinerators, and we moved to shredding. It was a real pain, each of the operators would collect and shred their own stuff. You had to break the habit of crumpling up the waste paper. When we shut down the station, we ran the burner again, because we had to destroy so much, that it would have taken too long to shred.

Re:Shredding vs. burning (4, Informative)

DRJlaw (946416) | more than 2 years ago | (#38081732)

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?

1. Burning is inconvenient for small volumes of paper.
2. Burning is essentially illegal for large volumes of paper (business scale; Clean Air Act permits).
3. Fireplaces are not as common as they used to be; outdoor burning is illegal in most cities.
4. People can be idiots [insweb.com] when using fire outside of a fireplace or permanent fire pit.
5. DIOXIN! [ny.gov]

Shredding is like a residential door lock -- good enough to discourage a casual person who is too curious for their own good. Secure commercial shredders rely upon sheer volume and decent mixing (300 "particles" per page x 3 tons of paper dumped at a recycler is a decent level of obscurity) or "hydro-pulping" for the demanding (shred then pulp at paper mill -- good luck reassembling the fibers even if you get to them before bleaching).

Re:Shredding vs. burning (1)

bistromath007 (1253428) | more than 2 years ago | (#38081792)

You know what makes paper alot easier to burn? Shredding it. :V

Re:Shredding vs. burning (0)

Anonymous Coward | more than 2 years ago | (#38082242)

I've tried it. It works better with a leaf blower, assuming you have a desert to play in. However, shred doesn't burn well. Approved shred doesn't burn worth a damn. However, shred blown around the desert is probably impossible to recover in a meaningful volume. The local firefighters were unimpressed with that stunt.

Re:Shredding vs. burning (1)

0100010001010011 (652467) | more than 2 years ago | (#38081836)

Why not roll a group of documents up as tight as possible into a cylinder and somehow automatically feed that against some 40 grit sand paper.

Re:Shredding vs. burning (1)

DigiShaman (671371) | more than 2 years ago | (#38082178)

A bit slow. But yes, tightly bound paper pressed up against a belt sander should do the job well.

Re:Shredding vs. burning (0)

Anonymous Coward | more than 2 years ago | (#38082298)

Shred then wash with water. The pieces will stick together making remaining print illegible.

Why are the documents shredded to begin with? (4, Insightful)

damn_registrars (1103043) | more than 2 years ago | (#38081056)

Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

Re:Why are the documents shredded to begin with? (-1)

Anonymous Coward | more than 2 years ago | (#38081146)

another question is why the reward is only $50,000?

Re:Why are the documents shredded to begin with? (1)

Meshach (578918) | more than 2 years ago | (#38081166)

Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors. Shredding provides a way to dispose of any document in any circumstance.

Re:Why are the documents shredded to begin with? (2)

arth1 (260657) | more than 2 years ago | (#38081306)

Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors.

And rules like that are so important to follow when the enemy is at the gates. Make sure you wipe your feet too, so they won't come to a dirty floor.

Re:Why are the documents shredded to begin with? (1)

damn_registrars (1103043) | more than 2 years ago | (#38081986)

Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors. Shredding provides a way to dispose of any document in any circumstance.

If we're talking about warlords and other such types, who don't see a problem with using rape as a tool for war, I don't think they would be that worried about lighting a fire in a place where others might think it to be less-than-kosher. Hell if a warlord is trying to run away from something, they may well just set the entire building alight in hopes that the documents and everything else inside will go up in smoke.

SHHH!! (4, Funny)

jensend (71114) | more than 2 years ago | (#38081172)

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.

Re:SHHH!! (4, Funny)

jensend (71114) | more than 2 years ago | (#38081198)

See also United States v. Prometheus for more about the penalties for divulging such classified information.

Re:SHHH!! (1)

Namarrgon (105036) | more than 2 years ago | (#38082034)

Geez, the penalties are steep.. "not less than an eternity of eagle-based liver removal" for a first offence :-/

Re:Why are the documents shredded to begin with? (1)

artor3 (1344997) | more than 2 years ago | (#38081288)

Only if you do it right. A sloppy burn job leads to entire pages of recoverable data. A confetti cut shredder will make the data damn near unrecoverable no matter how the paper is fed in.

Re:Why are the documents shredded to begin with? (0)

Anonymous Coward | more than 2 years ago | (#38081318)

Why not burn your shredded documents?

Re:Why are the documents shredded to begin with? (1)

arth1 (260657) | more than 2 years ago | (#38081356)

Why not burn your shredded documents?

Time.
But tossing the shred out the window ought to do it. With even a small percentage of the shred unrecoverable, the puzzle becomes a lot harder.

Re:Why are the documents shredded to begin with? (4, Informative)

mollymoo (202721) | more than 2 years ago | (#38081710)

I burn my old bank statements etc. and it's actually pretty time consuming and labour intensive to completely burn anything more than a few sheets. Just throwing a stack of papers on a fire doesn't work - the middle pages don't burn and are completely legible. Even when burnt, undisturbed paper ash still has legible text on it. You need to do a lot of stirring and separating of sheets to ensure complete destruction. It's much more time consuming than shredding.

Re:Why are the documents shredded to begin with? (0)

Anonymous Coward | more than 2 years ago | (#38081750)

Don't worry, the next contest will involve a $75,000 prize to reverse entropy

Re:Why are the documents shredded to begin with? (3, Funny)

ShakaUVM (157947) | more than 2 years ago | (#38081796)

>>Don't worry, the next contest will involve a $75,000 prize to reverse entropy

I hear students from UCSD have already summoned a demon to solve this puzzle.

Name's Maxwell, something like that...

Re:Why are the documents shredded to begin with? (0)

Anonymous Coward | more than 2 years ago | (#38081866)

I take cash only. My body reverses entropy daily when I eat. The Sun powers this. Oh, non-locally?

Re:Why are the documents shredded to begin with? (3, Funny)

Trevorm7 (1082535) | more than 2 years ago | (#38081954)

Or just run it through an HP printer, the process of trying to rip it out after it jams should do the trick.

Anything sensitive... (0)

Anonymous Coward | more than 2 years ago | (#38081128)

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 (0)

Anonymous Coward | more than 2 years ago | (#38081130)

darpa should team up with mensa and the scientologists
and just when things could not get any stupider

so who owns the IP? (0)

Anonymous Coward | more than 2 years ago | (#38081138)

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.

Doesn't sound too hard (0)

Anonymous Coward | more than 2 years ago | (#38081244)

Get Professor Layton on the case, provide some tea and scones, and he'll have it solved in one hour.

Confused? (4, Insightful)

wisnoskij (1206448) | more than 2 years ago | (#38081276)

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).

Re:Confused? (2)

wvmarle (1070040) | more than 2 years ago | (#38081702)

If it were so easy to computise, why haven't you done it yet and taken the prize?

My guess it's not that easy. And that it also doesn't have to do with computing horsepower as such.

Then about the text recognition and analyses: don't forget that there are more languages than just English. As a matter of fact most people in this world use a language other than English in their daily life. I for one use four languages, of which three daily and the fourth at least weekly. And English is my second language. You can not just assume the document you try to piece back together is written in English, you can't even assume it's written in Latin script, or that it is text to begin with: it may be drawings or maps.

Re:Confused? (1)

wagnerrp (1305589) | more than 2 years ago | (#38081834)

I think the idea is that you use the software to churn out tons of small patches of potential matches, which then get passed out to the humans for verification. If the humans score the patch highly, those used pieces are considered spent, and down-weighted from any further matches, while the software bumps up to the next level and starts weaving together the larger patches.

Since the software is only making small patches, the number of combinations stays within manageable levels, and the humans are better at spotting patterns and words to suggest the patch is a valid match.

Re:Confused? (2)

Nemyst (1383049) | more than 2 years ago | (#38081884)

I'm fairly sure this problem is NP-complete, which makes it anything BUT trivial to compute. It might be easy to represent computationally, but to actually calculate the result is extremely hard. In fact, finding an efficient algorithm for it would make you incredibly rich and possibly dead.

Re:Confused? (1)

wisnoskij (1206448) | more than 2 years ago | (#38081930)

It very well might be NP-complete (but probably more of a fuzzy NP complete as there a certain assumptions you can make about the content and it cannot be compressed down to a purely simple mathematical problem) but I think that if that were so that it would be NP-complete for humans as well as there is no best guess and good enough solution. And no human could even hold enough of the puzzle in their head to attempt any kind of effective solution.
So yes it might be hard to solve in a reasonable time with a computer, but even a every day computer should be millions of times faster at solving it then a human.

Or I might be comprehending the problem incorrectly.

Re:Confused? (1)

Intropy (2009018) | more than 2 years ago | (#38082048)

It's not NP-complete. You can determine whether two pieces fit together in constant time so you can find a match for a given piece in O(n) time. The paper is planar, so the number of "matchings" is linear in n. Find a match in O(n) time O(n) times and you got yourself a quadratic problem.

Re:Confused? (0)

Anonymous Coward | more than 2 years ago | (#38082320)

Doubtful. The subset of problems that are solvable by a greedy algorithm are probably O(n^2), but this isn't the full set. Consider what happens when you have multiple matches for a given edge or a puzzle with a number of solutions other than 1. When you start looking at the extreme edge cases NP-Complete (if not harder) seems likely.

Re:Confused? (1)

edgr (781723) | more than 2 years ago | (#38081900)

A lot of research has been done on the second step of this algorithm in bioinformatics. When sequencing a genome, generally all you get are millions of short sequences that need to be stuck together. The algorithms work by calculating probability scores for various pieces to be adjacent and then doing some funky statistics. It's a non-trivial problem to calculate those probabilities for the document reconstruction problem, and then the reconstruction is in 2d instead of 1d, but the bioinformatics algorithms could provide some interesting approaches.

Re:Confused? (1)

westyvw (653833) | more than 2 years ago | (#38082214)

Would it be possible to get information from the scan beyond that of the text itself? Perhaps each cut has a unique edge, so you could line up the columns of likely candidates. Or maybe the grain in the paper could be revealed, adding another potential edge. Maybe thickness of the paper could be compared or opaqueness. Put all this extra information together and maybe a computer could then work on the construction of the actual text.

Re:Confused? (1)

fluffy99 (870997) | more than 2 years ago | (#38082386)

I agree some computer pre-sorting is needed to pare the problem down a bit first.

If this involves multiple pages, perhaps the computer can distinguish which pieces belong to which pages based on the angle of cut versus the font? Or top face versus bottom face. I doubt every piece goes through the shredder exactly the same angle. You'd need pieces large enough to determine the font angle with respect to the edges

Each cutting blade and cross-cut tooth isn't identical. It may be possible to distinguish what horizontal position or multiple of vertical position a piece belongs to based on how the edges are torn. For example a chipped cross-cut tooth could reveal info about where on the page the piece came from by grouping pieces that came from the same vertical strip. A particular cross cut tooth would hit every xx mm of spacing going down the page as well.apart

Printers are never perfectly consistent in printing across the page either. Perhaps there is some systemic printing error that would allow grouping, like the kerning is slightly tighter to one side or the inkjet dots are slightly bigger on one side, or the laserjet has a little shading difference to one side, etc. Now we are getting closer to how people solve a real jigsaw puzzle.

I thought it was (0)

Anonymous Coward | more than 2 years ago | (#38081430)

Why women always go for the bad guy until he starts beating her,THEN she goes to the good guy she rejected before...

10000 pieces? (0)

Anonymous Coward | more than 2 years ago | (#38081458)

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."

Re:10000 pieces? (1)

Nidi62 (1525137) | more than 2 years ago | (#38081488)

If you add them up, it comes out to slightly over 9500 pieces....

Re:10000 pieces? (1)

fluffy99 (870997) | more than 2 years ago | (#38082410)

If you add them up, it comes out to slightly over 9500 pieces....

Well they didn't say all the pieces would be there. What's the likely hood that the shred bag you grabbed has every single pieces? How many are stuck in the cutter or got vacuumed off the floor (I've never seen a 1x5mm shredder that didn't leave a mess of chaff all around itself.

What about 100,000 pieces? (0)

Anonymous Coward | more than 2 years ago | (#38081474)

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.

ruin USCD? (0)

Anonymous Coward | more than 2 years ago | (#38081476)

anyone else want to write a bot to constantly click and drag randomly on the flash app? keep that shit scrambled.

The answer is... (0)

Anonymous Coward | more than 2 years ago | (#38081562)

... 42

Crowdsourcing works (0)

Anonymous Coward | more than 2 years ago | (#38081714)

It seems that there have solve the first two puzzles already!

I know how to do it... (0)

Anonymous Coward | more than 2 years ago | (#38081728)

...but it's going to cost someone more like 5K X 50K.

Occupy Wall Street (2)

robow (1609129) | more than 2 years ago | (#38081810)

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.

False inference (0)

Anonymous Coward | more than 2 years ago | (#38081958)

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.

Patent this. (0)

Anonymous Coward | more than 2 years ago | (#38082142)

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.

Statistics Fail (2)

MSTCrow5429 (642744) | more than 2 years ago | (#38082190)

"The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great[.]"

Ask Iran (1)

ExtremeSupreme (2480708) | more than 2 years ago | (#38082210)

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.

Most Complicated Ever? (1)

cosm (1072588) | more than 2 years ago | (#38082552)

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.

solution to shredding doesn't help (1)

holophrastic (221104) | more than 2 years ago | (#38082562)

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.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...