Plastic bracelet making problem i dreamed up talking with my niece

[bonanz]

I think this belongs in set theory? I may be wrong though. I always enjoy a good math problem, and my niece made me think of something that I couldn't figure out an easy way to get an answer.

She likes making those plastic bracelets with that plastic chord with the different colors and weaving them into keychains and such (like the girl was selling on napoleon dynamite). she has a bunch of different spools with different colors she uses and makes a ton of them for her friends/family etc.

so as she was sitting there working on some i saw her measure out really long strands. one of the colors she wanted to use on the spool was too short so she tied two shorter pieces together. i was confused but i watched her work and she weaved it and when she got to the part with the knot, she just skipped over it and left a section of straight pieces and continued the weave below it so she had a long bracelet with a straight limp part in the middle where the knot was. so i was like...what are you going to do here. and then she cut out the knot and tied the ends off of the two resulting pieces and had 2 thingamabobs...I asked her why she did this, and she said when she's weaving, she doesn't like to stop and just gets in the groove and as long as it's about 4 inches that's good for a keychain.

so i was thinking about this over the weekend and it started bugging me and i was thinking how would she do it if she had multiple short pieces so different colors would have multiple knots, she'd have to try to line up where the knots landed if she could to get the most efficient use of her chord. and i was thinking there has to be some mathematical way to figure out the best way to use her remaining chord so she could tie it all and weave away, and then just cut out the knots, by having the knots line up as much as possible.

so i wrote it all out on a piece of paper thinking I'd figure out some efficient way to do this and quickly realized i stumped the crap out of myself...so it's been bugging me to the point where i want to take to the internets and see if it's even possible or did i just dream up some impossible scenario...

here's what i was trying to figure out.

spools (color, and amount of inches on each spool left)

yellow:15,25,8,6

red:19,15

blue: 12,25,11

green: 15, 16, 9


how can she figure out the best way to make like 30 inches of total gifts, but none being less than 4 inches?

and if she wanted to use 3 colors, or all 4...or if she had more colors...etc

so like she would have a 2 color weave and wants 34ish inches of weave, number of pieces doesn't matter, just must be longer than 4, and you can have leftover, but pieces less than 4 will be tossed...

r----19-----------x----15-----x
y--25(cut to 19)--x-8---x--6--x
------------------c-----c-----c

and her end result would be 3 jewelry pieces of 19, 8 and 6 with some loss around the cuts obviously but i think that can be ignored mainly would there be a way to figure out what the best layout is for a color combination to get the best lineup of cuts to make as much weave length as she can, not caring how many pieces as long as they're greater than 4 inches, just the length she's weaved?

is this even possible, I've stumped myself something serious thinking about it...like it seems like maybe you'd have to brute force it or something writing up something to try everything... but it seems like there may be multiple sets that can be acceptable answers and i wrote all this down like i was going to come up with some clever solution and put my niece to work in a bracelet factory, but i furrowed my brow and it hasn't unfurrowed since...

 

[viraltux]

is this even possible, I've stumped myself something serious thinking about it...like it seems like maybe you'd have to brute force it or something writing up something to try everything... but it seems like there may be multiple sets that can be acceptable answers and i wrote all this down like i was going to come up with some clever solution and put my niece to work in a bracelet factory, but i furrowed my brow and it hasn't furrowed since...

OK, if I understood your problem correctly it looks a lot like the classical knapsack problem, if this is so then your brow is going to be furrowed for a long long time

Check this http://en.wikipedia.org/wiki/Knapsack_problem

 

[bonanz]

OK, if I understood your problem correctly it looks a lot like the classical knapsack problem, if this is so then your brow is going to be furrowed for a long long time

thanks for the response. i think my brain broke reading the knapsack problem...

so are you saying my pieces of chord length and color relate to wieght and profit in the classic knapsack problem?

would this be a variation where each color is a knapsack? so I'd have multiple knapsacks?


essentially I have a set of Color spools with lengths, R sub n for Red, Y sub n for yellow etc.

I have a min cut length of Lf =4, and a total weave length of Lt (assume sums of Rn and Yn are always greater than Lt respectively, in other words I always have enough length on any random number of spools to cover the total amount i want to weave, dispite having to tie neglible knots to make a "long" enough piece, but each roll is limited, and shorter than the total length so each color will need at least 2 pieces to be spliced)

so I must order the y1, y2, y3 side by side with r1, r2, r3 (and G1,G2,G3, etc) so that their lengths line up so when I cut out the knot pieces, I'll always have pieces >Lf, the number of pieces doesn't matter, but I need to have Lt total length of bracelets, and none can be shorter than Lf.

so you can cut r1, r2, y1 etc to make them fit slightly better cause the knots have to line up.

i made a picture below in paint (i can make prints available for framing if i get enough requests ;) ) in the pic below you take your sets of colors and order them so their splices line up approximately, and for example say you had to trim a couple of inches off of R4 to make that fit and maybe Y2 was long so it was trimmed, but the end result is like the black line where the solid line is the nice weaved bracelet and the C's are the areas where the knots are cut out leaving you 5 weaved trinkets that all must be longer than Lf.

is this the knapsack? i think being able to change the length of the individual pieces is different. and it seems each color is a knapsack of sorts? I'm trying in my mind to shoehorn it into knapsack, but I'm not sure if it is the same.

Thanks for the help, I appreciate the response, you gave me some more paths to investigate.
The pic is uploaded below...you'll have to copy and paste because although I've lurked for 2+ years, my lack of posts prevents me the privilege of posting links.

i45.tinypic.com/5xoob6.jpg

 

[viraltux]

is this the knapsack? i think being able to change the length of the individual pieces is different. and it seems each color is a knapsack of sorts? I'm trying in my mind to shoehorn it into knapsack, but I'm not sure if it is the same.

Well, if you can change the length of the pieces at will now looks more like a linear programming problem, but let me ask you a question cause I think I'm missing something, why don't you just tie together all the pieces and then cut them in Lf> lengths?

 

[bonanz]

well i guess you could cut them first, but the problem still remains of lining up up the "cut ponts" so you get the longest pieces out of the lengths of each color you have. my niece just did it that way, but i guess that really doesn't matter if she arranged them in the optimal way, pre-cut them, and weaved each piece individually, she was just weaving one long piece and then cutting it. but really the problem lies in the best way to configure whatever lengths of each color you have to try to line up without cutting or cutting the least.

 

[viraltux]

well i guess you could cut them first, but the problem still remains of lining up up the "cut ponts" so you get the longest pieces out of the lengths of each color you have. my niece just did it that way, but i guess that really doesn't matter if she arranged them in the optimal way, pre-cut them, and weaved each piece individually, she was just weaving one long piece and then cutting it. but really the problem lies in the best way to configure whatever lengths of each color you have to try to line up without cutting or cutting the least.

Yeah, the problem is a combinatorial optimization one, but I guess that what you want/need is a simple heuristic for your niece since I don't think she will appreciate much applied mathematic solutions :tongue:

I'd say though the best heuristic for her is the one she enjoys the most because, after all, that's the purpose of the whole thing . Nonetheless, problem wise, my heuristic would be something as follows; instead you adapting to the problem, you adapt the problem to you. So I would keep a box (let's call it resource box) with a collection of lengths for each color.

For instance the resource box initial lengths for one color would be 30,30,30,30. As time goes by, and your nice cuts the lengths she needs to align the knots, the lengths will start to shrink something like 15,6,20,19. Then she needs to update the resource box with 30,30,30,30 again, then, when a new problem comes up, if she needs a length of 19, she does not need to cut one 30 but pick the 19 one. The only rule she has to follow is to chose the appropriate length from the resource box to avoid more cuts. She can also add every leftover to the resource box in the appropriate length section.

So by keeping up to date the resource box you will always have perfect solutions having all knots aligned at all times... though maybe not so much fun