- Feature Articles
- CodeSOD
- Error'd
- Forums
-
Other Articles
- Random Article
- Other Series
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Admin
[quote user="Johnny Mac"][quote]Basically: If the 16' board costs less than two 8' boards, it's never advantageous to buy more than one 8' board--you could instead buy 16' boards and cut them in two, if for whatever reason you wanted 8' boards.[/quote]Doesn't that at least partially depend on how much your carpenter charges to saw the 16' board into two 8' boards?
Admin
Buying material for curtains, etc, in the UK is very strange: the width is Imperial, and the length is metric...
Admin
It is not that most carpenters are too stupid to figure it out. How big are the rosettes and the plinth blocks ? Or are we too assume that there aren't any, therefore having to add whatever width the actual molding is to account for each 45 degree join ? I know this is indeed just a exercise in programming, but it leaves out a lot of the delicacies of real world carpentry.
Admin
The following python code works by brute force comparing all partitions of the input list.
Give it a minute to finish... ;-)
Note: I found the partitions() function here: http://compprog.wordpress.com/2007/10/15/generating-the-partitions-of-a-set/
Admin
A made a quick Python solution for each level of difficulty. Easy: First Fit Decreasing Medium: FFD for the longest board length, then check for a board that's longer than necessary and substitute a shorter one Hard: FFD for the longest board length, then check for all boards longer than necessary and substitute shorter ones
The medium solution is certainly as close to optimal as the easy one. I have no idea how good my hard solution is.
Admin
question is....how many of those boards do you need? one for every splice? or can you optimize it? ie. you can cut some of those 16 foot boards into required lengths eg, if you find 4 4 foot splices you only need 1 16' for that.
Admin
Surely the most obvious solution would be to buy one single 534 foot board, which you could then cut as needed.
Admin
This kinda reminds me of trying to buy speaker wire for my home theatre.
If you cut a piece of wire too short then it's basically wasted, since you're not going to want to splice another piece onto it.
Admin
I just remodeled a room in our old house. Walls & ceiling are framed with 2x4's. 2"x4", 1 3/4"x3 3/4", 1 5/8" x 3 5/8", 1 1/2"x3 1/2". Yep, all 2x4's. And not all 16 inches on center; varied from 6 to 22 inches.
Admin
So you want me to solve the famously NP-complete bin-packing problem and send you the code?
Admin
Don't carpenters use optimisation software for this? I'm only a hobby carpenter and I use cut and quantity optimisation software. Saves on costs and waste.
I'll plug your example numbers into it when I get home and see what it says.
Admin
Also, GLPK should be able to do this easily.
Admin
I remember when these Byoc articles actually had some solutions written. Yes this is an NP space problem, yes it is easily searched for on the internet(what isn't?), and yes the problem details aren't that great. The point id to have fun coding, I coded a solution in about 10 minutes in python then posted it. It is not optimal, but I did get a chance to play in Python while on my lunch break. I wish there was one of these weekly, but unfortunately with all the flack about things like the 1/8 for the saw blade I don't get to see solutions of others in languages I don't know. Solutions that may give me insight into the problem, or find a new language that I may love more than Python. Instead I get a semantic pissing contest from a bunch of people petulant to have fun and code. It's Bring Your Own Code, not bitch about metric, saw cut outs, or that this is just a rephrasing of an NP problem. BRING YOUR CODE!!!!!
Admin
Is Alex going to resell the best reader's solution to his lazy carpenter :P
Admin
Do what I do: measure it, estimate, add 30% or so, go to Home Depot, buy it and return what you don't use for a full refund. It's cheaper to make a return trip at your leisure than have to rush to buy more because you screwed a cut up or dented a piece.
Admin
Blagh. NP Complete problems are no fun - at least for me...
Agreed. Just use millimeters. :pAdmin
the WTF here is that:
1cup = 8 oz = 1/2 pint 2 cups = 16 oz = 1 pint = 1/2 qt 4 cups = 32 oz = 2 pints = 1 qt (4 qt/gal = 8 pts/gal =16 cups/gal) 16 cups = 4 qts = 1 GALLON!!
same for distances and lengths...
Admin
So, is this the answer?
Admin
Here in the UK, we are in a constant dither about what units to use: Market stalls have been prosecuted for persisting in selling vegetables by the pound (against EU legislation), we still measure height in feet and inches, and if you tried to sell beer in anything other than a pint glass there would be a riot. Ditto miles rather than kilometres. However, attitudes towards the Metric system are changing with the generations. My father still thinks uniquely in Imperial; I (age 45) have a good grasp of both; I suspect my nephew would understand feet and inches, but not stones and pounds. (Aside, I also remember pounds, shillings and pence, but that's a different horror). One feature of this that I discovered recently is that, when estimating the amount of wood required to build a bookshelf, I did the rough work in feet ( 6' high, 4' shelves ), then the fine work in mm, as calculating feet and inches sucks.
Admin
No, but when the US decided to redefine a few of the British Imperial measurements, they created their own system. vis. a 44 gallon drum and a 40 gallon drum are the same size.
The vast majority of the measures in the two systems are interchangeable, with exception.
As long as no-one mentions the US Survey Foot, we should be fine when talking about lengths.
If course, we never use those measures here in New Zealand except when talking to people about a person's height, or a baby's birth weight.
Admin
Admin
Admin
TRWTF (other than Alex's unitophobia) is all the whining about NP-completeness.
Repeat after me:
NP-complete problems are not difficult to solve. NP-complete problems are not difficult to solve. NP-COMPLETE PROBLEMS ARE NOT DIFFICULT TO SOLVE.
They just take a long time for large values of N, that's all.
Consider how small N is going to be for even the largest, most oddly-shaped house.
Now consider the power of your CPU. How long will a brute-force search take?
Admin
Ok, I said I'd post this, so here it is. It's sub-optimal but runs in constant time. I've had it work for all both Alex's example, and Finknottle's
(note that these numbers are in feet, therefore {72,72,60,60,60,18,12})
For better accuracy (and processing time), you can increase the number of iterations in the main for loop.
Addendum (2010-01-21 06:00): For: 72,72,60,60,60,18,12 16,8
For Alex's Example: ({84,32,84} * 32), 16 (no that's not valid syntax :P)
Addendum (2010-01-21 06:23): Yes that 71 is a typo. Windows 7 command line windows aren't fans of copy/paste.
Admin
TRWTF is that "s" is an SI unit.
"2.7 gigaseconds ago our forefathers brought forth..."
Admin
Hhmm, I had to do something similar for a factory production program once. But it was in meters/ millimetres, so I can't help you with this problem. :-). What we used, was an extra property called "cut size". It approximated the width of the blade used for cutting + the actual amount of material lost when cut using the default machine used for that cut (it was different per material type and per machine used for cutting). This cut size had to be included in calculating the material list needed for meeting the order.
I am not going through all of that again!
Admin
TRWTF is measuring in feet and thumbs and elbows and toes and noses and what do I know. One should refuse to solve the problem just for that.
CAPTCHA: dolor. That's what I get looking at the way feet and thumbs go together on a 12 based (sometimes, since 3 feet make a yard, btw what comes after? the kyard and Myard???) measuring system.
Admin
Admin
Bottled beer, however, has worked on a "metric pint" (my term, not official) of 550ml for a long time; the most common sizes are 330ml and 275ml. European bottled beers are usually in 500ml bottles, i.e. not adapted for the UK.
Metric works better for people's height and weight when calculating body-mass index, otherwise feet & inches are indeed the thing for height, and stones & pounds for weight - did I mention about the stones? Eight stones make one hundredweight, i.e. 112lb. Simple. ;)
Admin
Why do we not get prices to the boards as well? As an earlier commenter mentioned, there's no reason to NOT use a 16' board unless price is involved.
Admin
We're all environmentally friendly here, and are trying to minimise waste!
Admin
Wow, I must say I really like this idea. I hope this becomes a running theme. When I get home I plan on solving this. Now back to writing tedious data entry forms.
Admin
Should the cut list on the output include which way the 45-degree miters should be cut, for the corners of the room/door casing? :)
Admin
You're estimate is going to be off. If you miter an outside corner (Where the 39.5" and 27" pieces meet in your picture) you'll need to add the thickness of your baseboard material to get the length right.
If your baseboard is 1/2" thick you'll actually need to cut one piece to 40" and the other to 27.5".
You're also not allowing for the saw kerf, figure another 1/8" for every cut, but I'd use 1/4". And that's for every cut end.
Admin
Personally I can't be bothered to overanalyse this. The problem will be difficult enough for most people following the "Hard" spec. That said, increasing the number of available board sizes doesn't really add a great deal more code.
Admin
Wow! That's a genetic algorithm style approach. It's nice to see someone striving for the best way to (quickly, reasonably) solve this problem.
About your O(1) time analysis: It's probably something more like O(n) because testing the total board length can depend on the number of boards which can depend on n. Of course this is still a good worst case time.
Admin
TRWTF is that you don't use metric in your country. Feet & Inches? ugh. so clumsy.
Admin
Note from another Alex: basicly the US do use metric but they successfully hide that from their people. e.g.: Screws in cars are metric, lengths too. Even the speeds internally calculated and used are!
Display converts.
Admin
What the heck is this text about? The article is too American-centric and too non-native-English-speaker-unfriendly.
Admin
I'm from the UK (predominantly metric) but I'm still amazed at how many otherwise intelligent people have this utter inability to work with imperial units. What is so confusing about there being 12 inches to a foot? How can you possibly work in hex (base 16) without being able to handle a simple base 12?
Admin
Thanks :)
And yes, I see your point. The fitness function for the mutation will depend upon the number of boards in the two states. I missed that when taking a guess.
Also removing the empty boards will from the state will also depends upon n, as the List class in .NET is array-based.
I'm from the UK, have recently graduated from University with a 2:1 in Computer Science and am from the 'metric generation' and I still managed fine working in imperial units. At University there were various occasions where they made us work in other bases (usually 2, 8 or 16) So it's not just you who is amazed :D
Admin
This looks like a version of the bin packing problem which is NP hard if you want to do it entirely without splices. Of course an interesting coding task. Then for smallish instances you can of course brute force it and get an optimal solution.
Admin
having converted from the original US
Baseboard = skirting Crown = coving casing = architrave
i figured that I'd go down B&Q buy extra and take the remainder back - like most people do. After all even if you do calculate exactly what you need, there's a fair chance you'll cut some mitre arse-about-face, or measure the wrong edge and have to do it again. Or a knot will fall out or appear at the mitre.
captch enim - whay its mine
Admin
In a previous incarnation ia was a diver in the oil industry; a Particular day a colleague was sent in to measure a widget on a platform so that something could be made to fit it. Unfortunately he dropped the measuring tape, not a problem on a building site but in 300ft un-retrievable. He was asked to use somehthing else; he chose his diving knife as the widget "was exactly the same lenght". On the surface we produced our knifes - all the same length - measurement made and passed off to manufacturing. When diver eventually made it back to surface (decompression etc) his knife was checked. Naturally it was different. This was nothing to do with him being American and the rest of us European.
Admin
Should be using longer boards where possible, but smaller ones when you don't need the huge excess. Like:
[byoc]$ ./calctrim.rb 6x 84 3x32 You will need: 3x16', 1x8' Scrap: 24", 24", 24"
So the 16' boards are cut 84", 84", and 32", and the last 8' board is used for the final 32" section.
Admin
Btw, how may square feet are in one acre?
Google says 5280**2 / 640 = 43560.
For those unaccustomed to English system dementia, that's 5280 feet in a statute mile squared divided by 640 acres in a square mile. You live around here, you get used to this whackiness.
Admin
Nope, gypsum ain't wood, it's a mineral, a calcium compound.
Christians in their bible call it alabaster.
Admin
What about the issue of a wall that is like one inch longer than a standard board length? You shouldn't use a 1-inch piece, you should recalculate to see if you can use any other pieces to make a more rational configuration. Also you have to allow for the width of the saw blade, and for 45 degree cuts.
Admin
Who the fuck cares about units of measurement? I don't understand enough carpentry/home renovation lingo (at least in English) to understand the damn basic geometry of the setup being described here!