Attn: Math and CompSci experts

Casey Karp

Super Member
Registered
Joined
Sep 13, 2013
Messages
221
Reaction score
66
Website
koiscribblings.com
I've got a situation I've set up in a story as follows (simplified for the sake of asking this question):

I've got an irregularly-shaped three-dimensional object which has been shattered into a large number of pieces and my character has to reassemble it. The only method he has is to take one piece, and then randomly select a second piece and see if it fits the first. If it does, great, he attaches it, if not, he discards it. Select a third piece, etc.

My questions are: (1) for a total number of pieces N, is there a way to calculate how many comparisons he's going to have to make to reassemble the entire object? (2) Does the job speed up linearly with additional people working on it (for example, if he gets three buddies to work on it with him, will they finish in a quarter of the time?)

I've tried to reason this out logically, but I keep getting stuck at the realization that more than one piece is a match for any given piece, i.e. if the first piece is a cube, there could be as many as six other pieces that fit with it. My brain starts trickling out of my ears when I hit that point.

And let me make one thing clear here: I am NOT looking for suggestions for more efficient algorithms. There are story reasons why he has to use this approach. I'm just trying to get a feel for how long the job will take given the resources he can throw at it.

Thanks in advance!
 

Mark HJ

Cat whisperer
Super Member
Registered
Joined
Nov 5, 2013
Messages
188
Reaction score
17
Location
Cornwall, UK
Website
markhuntleyjames.wordpress.com
OK, physicist take on this:

I've got an irregularly-shaped three-dimensional object which has been shattered into a large number of pieces and my character has to reassemble it

Does it shatter into irregular pieces? That would be my assumption and I think it makes a practical difference.

My questions are: (1) for a total number of pieces N, is there a way to calculate how many comparisons he's going to have to make to reassemble the entire object?
In principal you have a combinatorial problem and it makes me think of statistical thermodynamics - modelling thermodynamic behaviour from collections of randomly moving particles. In practice, I suspect the best you can do is calculate the 'average' number of comparisons. So, the usual way of phrasing it would be something like: if your character attempts the problem X times (i.e. starting from a heap of bits each time) and X is a suitably large number then the average number of comparisons will be Y. Great if you're trying to predict behaviour of gases, but probably not a lot of help here.

HOWEVER... even if you could come up with a number, that doesn't really tell you how long it's going to take because you have to factor in the process of doing each comparison. So, if you have manage to shatter it into regular sized pieces then you can at least suggest how many face combinations have to be tried for each comparison. If the pieces are irregular, you have no way to tell.


(2) Does the job speed up linearly with additional people working on it (for example, if he gets three buddies to work on it with him, will they finish in a quarter of the time?)
Given the problems of estimating how long one person will take, I don't think it's easy to estimate the impact of adding extra hands. You now have a team who have to coordinate their efforts when the time for each comparison varies. My gut feeling is it ought to be faster, but you don't know how much time will be spent with people repeating a comparison already made.

My other observations:
1: It's a bit like trying to predict how long, or how many attempts, is needed to open a breifcase with a combination lock. If you get really lucky, you might hit the right answer the first time, or you might have to go through all the possibles and get it on the last one.

2: Irregular pieces might help since your character might be able to stare at the pile, have an 'Ah ha!' moment, and pick out two chunks that obviously go together.

3: Any surface pattern or decoration on the original item will presumably offer hints of what goes where and help reassembling it.

4: Go hunting for real-life versions of the problem. The main one I can think of off the top of my head of was a set of three Ming vases accidentally broken by a museum visitor and pieced back together over a period of about six months.
 

Casey Karp

Super Member
Registered
Joined
Sep 13, 2013
Messages
221
Reaction score
66
Website
koiscribblings.com
Mark, some good points there. I may have oversimplified the statement of the problem. And keep in mind that I'm looking for an "ideal world" answer, not a "real world", so the regularity/irregularity question doesn't really apply here. For what it's worth, I've been thinking about this as being similar to sorting multidimensional lists on a computer. I know there are ways to compare the efficiency of various sorting algorithms, and that's the kind of answer I'm hoping for.

Absolutely, an average would be what I'm looking for. Obviously, the minimum number of checks is one less than the number of pieces (i.e. he's incredibly lucky and each piece he picks up fits somewhere into his completed structure. And the maximum is roughly equal to the factorial of the number of pieces (if he's so unlucky that he has to check *every* piece to find a match each time. But there ought to be a sweet spot somewhere at the top of the bell curve--the most likely number of checks.

So let's add some additional data:
The time it takes to do one comparison is currently undefined. I have a lot of flexibility there, which is why I asked for a way to figure out the number of checks. I have some flexibility in terms of the number of pieces, which is why I'm hoping for a formulaic answer. I'd like to say "I need it to take X amount of time, so I'll set the time to do a comparison to Y, the number of pieces to N, and the number of comparers to Z.

Assume that all comparisons take the same amount of time. Rather than thinking of parallelism as adding more people, think of it in computer terms: adding CPUs so more comparisons can be done in each unit time.

And I agree that the number of adjoining pieces per piece is probably significant. Without digressing too far, he's going to have to solve several of these problems, and the number of adjoining pieces will vary from problem to problem. So if it does affect the answer, it would need to be part of the formula, so I can tweak it as necessary.
 

WeaselFire

Benefactor Member
Kind Benefactor
Super Member
Registered
Joined
May 17, 2012
Messages
3,539
Reaction score
429
Location
Floral City, FL
Simple math. Take the number of pieces and figure out the combinations they can potentially fit into and halve that to get an average. Its basic permutation except the number of objects and the number of selections is the same. Google permutations for the formula, I'll get it wrong if I try to type from memory (it's been thirty years since I did any statistics), but for five pieces it's something five to the fifth, halved.

That's an average. It could happen on one try or on the last possible combination. Time could be anything, depending on how much time each attempt takes. It's also going to be variable since some pieces will logically fit while others may not. That's what happens with puzzles. The last piece takes no time at all since there's only one to try and you can see where it fits.

What do you need for the story? Write it that way.

Jeff
 

Casey Karp

Super Member
Registered
Joined
Sep 13, 2013
Messages
221
Reaction score
66
Website
koiscribblings.com
I don't think it's quite that simple, WeaselFire.

Let's take an example here. Assume, say, 100 pieces and that the average piece connects to five others. So the first piece he checks has 5 chances in 99 of being a match. If it's not a hit, the next one has 5 chances in 98, and so on.

Eventually he finds a match. Now he's got a two piece combo. He does a comparison, and it's got 8 chances in 98 of connecting to one or the other of his two piece combo.

And so on. And when I start trying to account for the number of available slots increasing as pieces are added, but decreasing because adding pieces uses up slots and sooner or later pieces slots are going to be filled, my brain starts leaking out of my ears. Not to mention the complication of having multiple workers each building a combination. How many vacant slots are there on this ten piece combination? And does this three piece one fit into any of those slots?

And yes, I'm going to write it the way I need it. But the problem is that I need it to feel plausible. If I have him solving a problem with millions of combinations in five minutes, readers are going to say, "Yeah, right," and fling the book against the wall. I figure if I know the answers within an order of magnitude, I can shape my explanation so it slides past the reader without a hiccup.