Thursday, December 6, 2012

Credit Bubble Stocks "Job Interview" Question

How does the amount of time it takes to solve a jigsaw puzzle scale with the number of pieces?

Promotion to Credit Bubble Stocks correspondent First Class to whomever posts the best answer in the comments.

23 comments:

JamesDavid said...

Depends on the algorithm.

http://www4.gu.edu.au:8080/adt-root/uploads/approved/adt-QGU20041101.085937/public/04Chapter3.pdf

Jason said...

Assuming the length of time to complete the puzzle is a function of the number of possible combinations of pieces, we can come up with a multiple fairly easily.

Use (old pieces) = number of pieces in the base puzzle

Use (new pieces) = number of pieces in puzzle we are looking to compare against the base puzzle

The number of possible combinations will increase (decrease) by a multiple equal to ((new pieces! - old pieces!)/old pieces!) + 1

Stagflationary Mark said...

In my opinion, a good solution would factor in three separate scaling problems.

1. Sort the pieces into edge and non-edge pieces. This scales according to the number of pieces. One pass. Easy sort.

2. Placing the edge pieces scales according to the length of the perimeter.

3. Placing the interior pieces scales according to the area of the interior.

I could also sort by color to speed the process up but I'm not sure I should assume that I can. A jigsaw puzzle is not required to have colored pieces and the problem doesn't specify it.

That's my attempt for what it's worth.

CP said...

Thanks everyone. I'm ready to declare a winner - I think Jason is correct.

My thought process was the same: solving a jigsaw puzzle is a matter of making edge comparisons between pieces. You're asking the same question as Metcalfe's law: http://en.wikipedia.org/wiki/Metcalfe%27s_law

So the number of connections is scaling faster than the number of pieces, and since the edge comparisons are the same speed the puzzle is taking longer to solve.

This makes intuitive sense: you can solve a two piece puzzle instantly, and I think that a puzzle on the order of 100k pieces would be unsolvable.

One objection I heard is that when solving a puzzle you start by color sorting before making edge comparisons.

That is true, but then each group of colors is its own set that needs comparing. And for a puzzle n times as big, each color set will probably be n times as big also.

CP said...

http://www.thegreenhead.com/2012/08/keith-haring-double-retrospect-worlds-largest-jigsaw-puzzle.php

Stagflationary Mark said...

Seriously?

New pieces = 1000
Old pieces = 500

((1000! - 500!) / (500!) + 1

3.3x10^1433

Good luck on that one.

CP said...

I think he wrote the wrong formula, I believe the correct one is n(n − 1)/2 which is ~n^2.

So if you double the pieces the puzzle is 4x as hard, etc.

Stagflationary Mark said...

CP,

Yes, that's what I wrote in my answer. It goes as the area of the interior.

Width x Height

I also added extra precision since the edges can be done faster.

Width x 2 + Height x 2

Stagflationary Mark said...

I should add that I kept it more general than that though, since I did not assume that the puzzle was square.

I've done circular puzzles in the past.

Stagflationary Mark said...

One more thought.

I can see a problem with my solution as well.

2. Placing the edge pieces scales according to the length of the perimeter.

That's still an n-squared problem where n is the length of the perimeter.

It's just an easier/faster n-squared problem since there are generally far fewer edge pieces than interior pieces.

Stagflationary Mark said...

I can see a problem with my solution as well.

I take it back. My original solution was mostly fine.

The time to complete an edge grows linearly as the number of pieces grows (for puzzles mostly square and/or circular, not a thin strip).

That's because the perimeter is generally proportional to the square root of the number of pieces (for puzzles mostly square and/or circular).

For example, a square 1000x1000 puzzle has 1 million pieces but only has a perimeter of 3996 pieces.

portland_allan said...

Well, since it was a job interview and not a dissertation on puzzle theory, I think Mark gets the hire. He's showing an aggressive desire to be part of the team, and a flexibility to keep working at a problem until it is satisfactorily solved.

Of course, like they say be careful what you wish for. Now that you're part of the CBS team you're required to hedge 50% of your 20yr TIPS AUM by shorting a ladder of sub-5yrs with their negative real rates. The cash received from the short should be rolled (heh) into nickels.

Stagflationary Mark said...

portland_allan,

I can't seem to stop. Perhaps that should make me first to be fired, lol.

The edge of the puzzle should definitely be done first and that should be factored in. It's linear in how long it takes (based on total # of pieces) but n-squared too (based on the number of actual edge pieces). That's interesting to me.

Here's something else to think about. As the number of pieces increase, the differences between pieces decreases. It therefore takes more and more time to determine if two pieces are supposed to connect together.

I have a 3000 piece puzzle. There are a lot of pieces that almost fit together. Definitely adds time! In fact, I never did finish it.

There appeared to be one missing blue sky piece and I stopped at that point. It may have scarred me for life, lol.

Stagflationary Mark said...

As for nickel hoarding, I suspect that many investors can and will do worse!

Stagflationary Mark said...

Note that I'm still not done. I apologize! What can I say? I love puzzles.

I think the bucket sort is very much related to how most people solve jigsaw puzzles. We group similar pieces together in buckets.

Its average case is much better than n^2.

Its worst case is still n^2 though. For example, it is difficult to bucket sort the pieces by color if the puzzle is a night scene of an underground coal mine.



Stagflationary Mark said...

One more thought. I'm really not happy with the way I worded my original answer. I was thinking in terms of n^2 when I spoke of area (r^2). I was thinking that the puzzles tend to get 4x harder when the number of pieces double.

That's not how it came out. Double the number of pieces and you only get 2x the area though. That's not what I intended and that's not what was going on in my head. My bad. I should have stuck to piece counts instead.

I therefore must retract what I said earlier.

"Yes, that's what I wrote in my answer. It goes as the area of the interior."

It was what I was thinking but it was not what I wrote in my answer. D'oh!


Stagflationary Mark said...

This is why I'm generally an insomniac.

If we don't use edge pieces or color/pattern sorting to speed things up then I think the following formulas work.

T = Time to Solve
k = Time to attempt to place a piece (rotating if necessary)
N = Number of Pieces

Worst Case: T = k(N(N-1)/2+1)
Average Case: T = k(N(N+1)/4+0.5)
Best Case: kN

I think I'm done unless someone can see a flaw. If it takes one second to place a piece then all cases take one second for one piece, two seconds for two pieces, and then things begin to diverge.

At three pieces it takes 4 seconds in worst case mode, 3.5 seconds average case, and 3 seconds best case. The first piece of three is a no brainer, as is the last piece of three. The 2nd piece potentially required two pieces to be tested though.

At 5 pieces, worst case becomes 11 seconds, average case becomes 8 seconds, and best case is 5 seconds.

I hope this was a 24 hour interview process.

Once again, I apologize for hogging the thread like a rabid weasel. I just can't help it. Puzzles!!

Stagflationary Mark said...

Just so the formulas make some sense...

Take the worst case for 5 pieces.

The first piece takes a second. Just plop it down.

The second takes 4 seconds. You've got 4 left. It is the last one you try.

The third takes 3 seconds.

The fourth takes two seconds.

The fifth takes one second. It's the only one left.

1+4+3+2+1

That's 11 seconds.

The formula for average case assumes that you find each piece at the midway point.

1+2.5+2+1.5+1

That's 8 seconds. Note that the midway point for 4 seconds is not 2 seconds (it's 2.5, the midway point between 4 seconds and 1 second).

CP said...

PDX allan, that was hilarious.

Mark, at this point I'm confident that the difficulty increases faster than the number of pieces. I think a puzzle of ~100k pieces would be almost impossible to finish.

Did you guys look at that 32k piece puzzle? Comes with it's own dolly for moving the huge box. Ravensburger!

Stagflationary Mark said...

CP,

Mark, at this point I'm confident that the difficulty increases faster than the number of pieces.

Absolutely!

I think a puzzle of ~100k pieces would be almost impossible to finish.

Somebody needs to write a massively multiplayer jigsaw puzzle game.

I'm picturing 100k people playing. Everyone gets one unique piece to place!

Wouldn't that be a hoot, lol.

CP said...

My favorite massively multiplayer game is the credit markets.

Jason said...

I beg to differ with Allan. In my opinion interviewers that ask these types of questions are looking for the 'elegant' answer rather than the 'brute force'.

My answer clearly ignores many facts about common jigsaw puzzles and makes many assumptions. But I believe the question is geared toward deciphering how the possible combinations grows exponentially when adding more pieces. How much more "difficult" a puzzle becomes is obviously much more subjective.

It's late now. I will elaborate on how I came to my answer tomorrow or on Monday.

Check out the book "Heard on the Street." This question is very similar to what you will see in this book.

CP said...

Jason,

I really think ~n^2 is the right scaling rule. I'll be interested to see if you have come up with something different.

CP