I remember having a lot of fun solving it, in Coffeescript (which was all the rage at the time), also with TSP but using the Pearson correlation coefficient as the similarity metric: https://gist.github.com/stevekrenzel/1505619
I like how unicorns can do such hiring challenges while normal companies are desperate for people to apply. I think my current company would hire anyone who can breath and write 3 lines of code per month, but no one fitting these criteria applies.
What's the work, and the pay? Those 2 things will play big roles more than a dearth of candidates. Told my son for years if you want to make more money, find something to do that no else wants to. Turns out the same is on the hiring side.
I think public hiring challenges like this are less of a barrier that filters out candidates, and more of an attractor that increases the number of applicants by "nerd sniping" people.
This gets spouted all the time on HN, and I find it rarely to be true, or at least a gross oversimplification.
In my experience what usually happens is a programmer's "worth" is hugely dependent on the scale of the organization, moreso than nearly every other individual contributor-level role, which means that smaller orgs have an extremely difficult time competing with larger orgs.
For example, suppose at some company there is a business process that generates $1 billion in annual revenue, and a programmer has implemented something that can increase that by, say, .2%. So the programmer's "worth" in that situation is 2 million dollars.
A much smaller company only does $10 million in annual revenue, so the commensurate .2% improvement is only worth 20k.
This is a gross oversimplification, of course, but it really gets to the heart of way the FAANGS can pay such huge salaries and suck up a lot of the best talent. It's not that all the other companies are being stingy, it's just that in many cases they can't pay a programmer anywhere near what a FAANG can because that programmer just can't generate that much business value at a smaller company.
It kinda goes the other way too though, no? A business generating $1 billion in revenue might have 10k employees. A smaller company doing $10 million in revenue might have 100. The commensurate value of a given employee is not that different.
And the number of employees also affects the types of efficiencies you can introduce; the likelihood of finding something that will increase revenue at a higher percentage for a large company is drastically lower than the likelihood of finding something that will increase revenue at a higher percentage for a small company. And that's if it's percentage based in the first place, rather than fixed savings.
Anyway, relatedly, it has more to do with the fact that a lot of the leading tech companies have a high amount of revenue -per employee-. That is, revenue/employee = big number. There's a few different reasons for that, but that's the main thing. Per the example above, it's really more like a company doing $1 billion in revenue has 10k employees, and another doing $100 million has 5k employees. Obviously the former has more to spend on employees, as they're generating more with fewer.
An annoying and more complicated (but perhaps not less accurate) heuristic is that the revenue of the company is related to the sum of prior work. For a product company, the number of features drives use more than the rate of new features being added.
Under that model taken as-is there are some interesting features:
- The company could fire all the engineers and coast if the product is "done". Mostly reasonable, though products are never done.
- More "solve for the equilibrium", engineers are paid for the present value of their contributions rather than some proportion of current revenues. Depends on the company either being well-funded, paying in stock, or being able to take on debt. Again, rings true-ish? Hard to measure so obviously expected present value will differ greatly from the actual value.
If there is a house shortage - prices will go up - the problem with the dev job market is that's its a market for lemons. You cant tell if someone is a good dev unless you yourself is a good dev.
Yeah, and even "good engineers" can take jobs that they don't do well at. It's weird how this works and seems in many cases not related only to the job or type of work, but many factors both on and off the job. I think this is the reason hiring is so hard, because there are factors not taken into account that have a real effect on how well a person does at some particular job.
This is quite similar to the early decryption of the analog Nagravision TV encryption system https://en.wikipedia.org/wiki/Nagravision worked.
Did it myself at the time, but on to slow hardware/to little optimized software. The decryption took much to long to be usable, but it was fun to see that it worked quite fine
This might even have an application for real documents. There are police cases where some suspects have tried to destroy evidence. Manually reconstructing the original takes a lot of effort. I expect that the CIA and NSA already have software for it, but I have never heard of it being used in a police case.
Germany has run a program for decades to recover the Stasi's paper documents, the bulk of which it shredded at the fall of the GDR. People can sometimes get their own Stasi files, if they're recovered.
Surprisingly, there's never been an HN thread about this (as far as I can tell).
From the Wired link: "Today, the study in Poppe's Berlin apartment is lined floor to 12-foot ceiling with bookshelves full of volumes on art, literature, and political science. But one shelf, just to the left of her desk, is special. It holds a pair of 3-inch-thick black binders — copies of the most important documents in Poppe's secret police files. This is her Stasi shelf."
The painstaking process to put back together shredded Stasi documents is mentioned at the end of The Lives of Others: https://www.imdb.com/title/tt0405094/
I really didn't like that movie, focusing on people who are wholly uninteresting politically; presenting a sort of a "shocked and chagrined" attitude to people being spied on by the government; and treating West Germany as some sort of paradise.
I would recommend Ken Loach's Fatherland instead; but - only until when Dritterman arrives in the UK (the end of the film is kind of messed up).
The political class is more than capable of looking after itself, thanks. It's the common people who have the most to fear, and the movie does a great job at underscoring that very point.
Current office shredders are almost all capable of double shredding but considering how easy it is to reverse by OP's project, it may be necessary to implement further measures for document destruction.
A laser or enzymic based method could work but neither are particularly office-friendly.
Once upon a time in Germany, I was put on several special duty assignments to guard documents overnight (with a machine gun!) prior to their destruction by companies like this.
Also, you generally have written correspondence, not images. I doubt that the similarity metric of OPs method produces reasonable results on text, and a good similarity metric for text would be much more complicated.
On the other hand physical shredders typically have other weaknesses, for example if you don't stir the shredded result you have a high correlation between original the current and original relative position of the individual pieces.
With written text, you would expect that at least some the letters from one shred would continue on its neighbors. I don't see why the similarity metric would not work. Also normally you have a pretty high contrast between the letter and the background, unlike the image that was used in the example.
Could someone invent a shredder that pre-analyses an image of what it's shredding and then shreds in a manner that makes reconstruction infeasible due to the increased likelihood of false positives? (e.g. the flipped and mirrored images in OP)
I think that would be a lot more complicated mechanically than adding a chemical process like bleaching the paper after it's been shredded. Or replacing the shredder with an off the shelf wood stove if you're in a city that doesn't have a ton of restrictions on what you can burn for heat
Would this algorithm allow for an image version of the Burrows-Wheeler transform? So, sorting image rows and columns using a compressibility criterion.
I wrote a program to do this two decades ago. I shredded a black and white text document (long shreds, not the new shredders that cut into confetti), scanned all the strips, front and back, and created a lookup value for each edge based on the pixel position. The biggest problem I had was the shredder blade removed too much material. This caused a continuous stroke to be fatter on one side than the other (imagine if the descender in a lowercase "p" was on the blade's path).
That's exactly what I started with. Well, not a scan but rather a digital picture since I didn't have a scanner (also my camera sucked). I also didn't do a very good job with boundary detection so I ended up snapping rectangles and extracting the 1-bit pixmaps manually.
I used TSP to optimally stack different types of bowls. I measured all the different pairs of bowls and searched for the shortest route through all the bowls we have. I found that you can split the stacks however you want, I also had an algorithm for that.
Is the algorithm different from a simple sorted order in this case? The difficulty with TSP is that you have to return to the start, which wouldn't seek to be the case with stacled bowls, unless you're stacking them in a ring somehow.
If you took a relatively smooth image like a picture of a sky with a lot of high frequency (e.g. sensor) noise I'd expect this method to fail to be exact.
Having a sparse representation in a DCT basis would be an even better metric. You want the unshredding which makes the (e.g.) 8-pixel wide horizontal DCT's have the lowest norm. Because this metric depends on more than just pairs of lines though it's not obvious how to construct an efficient TSP out of it.
One could easily take a TSP solution and post process using the DCT metric, testing out all possible swaps (or near ties in the TSP solution).
I don't suppose there's a way to process paper into 'pellets' fit for recycling that make this whole process untenable.
Paper fiber length dictates a lot about its reuse. The bigger the chunks the smaller the combinatorics for reversing the 'algorithm'. Big paper mache blobs might fare better. From a recycling standpoint a machine that tears the paper instead of cutting it would do better, but the uniqueness of the edges probably reduces the problem space.
If someone invents a fast paper pulping machine that can mount on a small truck that doesn't require a commercial vehicle license, I bet you could sell loads of them.
Whatever happened to that team who used microcavitation to blast the ink off of paper for reuse? Probably enough solvents left behind to read the text like invisible ink, but as a first pass it might be good.
Cool read! Though ordering the columns such that the cumulative cobsecutive dissimilaritiea are minimized is not what you really want. Think of a shredded image of a checkerboard: with this objective you would not obtain the original but rather a version where there are contigous black/white steps on the left and on the right, with a discontinuity in the middle.
That is to say: by reducing the objective to this you are assuming the image is continuous on the horizzontal axis, while in image processing images are usually supposed to be only piecewise continuous.
We don't shred digital images in RAM in that way, but we can scan & reconstruct physical images that have been shredded or torn.
You can paste together possible scenes to construct side-scrolling game scenery in realtime.
By applying a few insights we can phase one image into a hole that is in another image. This is similar to randomizing an array by creating a second array with random values, then sorting them in tandem, except we use the TSP with expected weightings.
In the virtual RAM accessible to the process the image might be continuous, but its physical representation could be different, as the operating system might use different areas from the physical RAM to expose it to the process. If you dump a computer's RAM e.g. in a forensic setting, you might attain such a state.
Same goes for file systems as well as the wear leveling layer of SSDs.
In the 90s and 00s analog pay tv used to be "encrypted" like this. IIRC software decryption relied on deriving the weak shuffling key by manually reordering image rows and then using that to reverse the key so the next frames could be decrypted more reliably. Doing that kind of video processing in realtime and in software was close to CPU limits.
Well, imagine someone dumpster diving at a bank/clinic/insurance provider that doesn't use a document destruction service. Probably plenty of PII/PHI could be reconstructed once the shredded fragments were singulated and scanned.
I remember having a lot of fun solving it, in Coffeescript (which was all the rage at the time), also with TSP but using the Pearson correlation coefficient as the similarity metric: https://gist.github.com/stevekrenzel/1505619
Here's a little demo of it in action: http://krenzel.org/files/insta/