After a lull yesterday, I could finally find time to solve the third puzzle in the Greplin Programming Challenge. At first the puzzle seemed tricky, considering my bad with combinatory logic with numbers. However after many trials and errors I could solve the puzzle. And now I can sit and relax, and look at my stupid face as to why I was writing over 100 lines of code to solve, when the solution was simply a few lines.

Anyways, am done with the challenge and I have my passcode now! Next steps involve dropping them a mail with my solutions.

For those interested, the code is available on my GitHub repository.

Happy Coding!

written by Sandeep Gupta

Thursday, December 8, 2011 at 4:57 PM

Yesterday evening I came across another programming challenge called Greplin Programming Challenge. The challenge presents three problems which requires one to write small pieces of code to solve, and provide the solution as the password to the next level. Something similar to Project Euler problems.

The challenge claims it may take from anywhere between 20 minutes and 2 hours. The first and second level are quite easy and should be completed within 15 minutes (including the time to fire up the IDE and keying in code, lazying around in bed). The third level requires some combinatory logic and thus may require a little extra time. I am done with the first 2 levels and planning for the third today evening.

For those interested, the code is available on my GitHub repository.

Looks like am developing a liking for coding problems... Anyone recommending another?

Have. Fun. Coding.

written by Sandeep Gupta

Wednesday, December 7, 2011 at 10:08 AM

In continuation of my earlier post about Instagram's Engineering Challenge on an Image Unshredder, I took some time out yesterday and completed the automatic strip width detection piece. The approach was easy, the euclidean distance on the strip edge will be too high than the normal values. For example the values may look like,

3, 4, 3, 5, 3, 2, 6, 22, 4, 3, 2, 3, 4, 3, 2, 27, 3, ...

One just needs to take the average of above values, then find the average of values greater than this average. Once you have the maxAverage, one can run a loop and find the value where the ratio of (value / minimum) is close to the ratio of (maxAverage / minimum). The first index where this happens is the strip width. To be doubly sure that we have chosen the right value, make sure the strip width divides the image width in whole.

I tested my code with many a free images from Flickr and it all worked. Though I did find a couple of issues with images that had a dark background and no front object - like a huge clear sky running in.

As the challenge was to unshred the shredded Tokyo image, it stands completed. The remaining improvements, I will leave for some other day.

I have also added an image shredder and a test suite that takes in images from a given folder, shreds and then unshreds them.

For those interested the code is posted on my GitHub repository at https://github.com/sangupta/image-unshred

written by Sandeep Gupta

at 9:48 AM

Three weeks ago, Instagram posted an engineering challenge: The Unshredder. The challenge presented an image that had been vertically shredded/spliced and then rejoined randomly, thus resulting in an image that looks like a puzzle. What one had to do was to write a script to take that image and unshred it - yes, reconstruct the original image.

From their blog,
Your challenge, if you choose to accept it, is to write a simple script that takes a shredded image in as input:

and outputs an unshredded and reconstituted image. That is, imagine if you took an image, divided it into an even number of columns and shuffled those columns randomly to produce a shredded image. Then, take that image into the script and output the original image:


I happened to read and pick up this challenge yesterday, and it was surprising to find that the solution was a very simple best-match function that had to place a given slice alongside another based on how close the left-pixels of one were to the right-pixels of another. I used Java and the built in AWT package to load the image and read the pixel colors at various coordinates. Reconstructing the image was again super easy using AWT. To test that the solution was a generic one, I sliced some 50 random images and then reconstructed them using my code for varying slice-widths - ranging from 4 pixel wide to 64 pixel wide.

My algorithm worked in the following way:
  1. Find out the number of stripes in the image (as the strip-width is known)
  2. Slice the image and store all sub-images in a given array
  3. Pick the first slice from the array
  4. Now for each other slice in the array (slices that have not yet been used) - compute the average Euclidean distance of the left edge of the given slice and the right edge of the test slice. Similarly, compute the average distance of the right edge of the given slice and the left edge of the test slice.
  5. Find the slices that have the least scores for left and right side
  6. Now, insert the one of the test slice to the left or to the right, depending on which test slice and edge had the lowest average distance
  7. Work this way to arrange each unused slice to the set of arranged slices
  8. At the end, you have all the slices in order resulting in the reconstructed image

For those interested the code is posted on my GitHub repository at https://github.com/sangupta/image-unshred

I haven't yet completed the bonus part of it due to lack of time, but hope to push it in a day or two.

Happy Coding!

written by Sandeep Gupta

Tuesday, December 6, 2011 at 9:00 AM