The Daily WTF: Curious Perversions in Information Technology

2010-01-20 Reply Admin

Subtext: Alex is doing some remodeling (rennovating) and can't be bothered doing the calculations himself.

2010-01-20 Reply Admin

So who's taking into account the ~1/8" lost at each cut due to the width of the saw blade?

2010-01-20 Reply Admin

Jamiec:
So for all thge wisdom of the metric system, it seems that we sell boards in quasi-imperial, metrically measured lengths.
Genius.

Not just wood, either. In British supermarkets, beer in bottles is often sold in units of 568ml.

That's "pints" to old farts like me.

(Real pints, mind, not yer (bad word)y little American ones.)

aptent: 3rd person plural present indicative of the hypothetical French verb apter, "to be apt", j'apte, tu aptes, il/elle/on apte, nous aptons, vous aptez, ils/elles aptent, rarely used outside the 3rd person forms.

RussJudge · 2010-01-20 Reply Admin

"So who's taking into account the ~1/8" lost at each cut due to the width of the saw blade?"

Ah--I had forgotten about that. Okay, here's my modified code which accounts for the width of the saw blade, again not tested:

using System.Collections.Generic; using System;

namespace WTF_BYOC_AvoidTheSplice { public class BoardCalculator { decimal BladeWidth{ get; set; } Dictionary<decimal, int> BoardQuantities { get; set; } ///

/// Initializes a new instance of the <see cref="BoardCalculator"/> class. ///

public BoardCalculator(decimal bladeWidth) { BladeWidth = bladeWidth; BoardQuantities = new Dictionary<decimal, int>(); //Always add 16' by default as always available.

        SetBoardQuantities(16 * 12, int.MaxValue);

    }
    
    Dictionary<decimal, int> workingQuantities = null;
    /// <summary>
    /// Gets the minimum required boards.
    /// </summary>
    /// <param name="Measurements">The measurements in inches.</param>
    /// <returns></returns>
    public int GetMinimumRequiredBoards(decimal[] Measurements)
    {
        Array.Sort(Measurements);
        int currentCount = 0;
        workingQuantities = new Dictionary<decimal, int>(BoardQuantities);
        scraps = new Dictionary<decimal, int>();
        //process from largest to smallest, so that scraps can be used, if a
        // measurement will fit in the scrap.
        for (int i = Measurements.Length - 1; i >= 0;i-- )
        {
            decimal matchedBoard = FindSmallestMatch(Measurements[i]);
            if (!scraps.ContainsKey(matchedBoard))
            {
                currentCount++;
            }
        }
        return currentCount;
    }
    private Dictionary<decimal, int> scraps;
    private decimal FindSmallestMatch(decimal measurement)
    {
        decimal matchedSize = 16 * 12;
        decimal scapamount = 0;
        foreach (decimal size in workingQuantities.Keys)
        {
            if (size < matchedSize && size > measurement)
            {
                matchedSize = size;
            }
        }

        workingQuantities[matchedSize]--;
        if (workingQuantities[matchedSize] <= 0)
        {
            workingQuantities.Remove(matchedSize);
        }
        if (scraps.ContainsKey(matchedSize))
        {
            scraps[matchedSize]--;
            if (scraps[matchedSize] < 0)
            {
                scraps.Remove(matchedSize);
            }
        }

        scapamount = matchedSize - measurement - BladeWidth;
        if (workingQuantities.ContainsKey(scapamount))
        {
            workingQuantities[scapamount]++;
        }
        else
        {
            workingQuantities.Add(scapamount, 1);
        }
        if (scraps.ContainsKey(scapamount))
        {
            scraps[scapamount]++;
        }
        else
        {
            scraps.Add(scapamount, 1);
        }
        return matchedSize;
    }
    /// <summary>
    /// Gets the minimum required boards using scrap.
    /// </summary>
    /// <param name="Measurements">The measurements in inches.</param>
    /// <returns></returns>
    public int GetMinimumRequiredBoardsUsingScrap(decimal[] Measurements)
    {
        decimal totallength = 0;
        foreach (decimal measure in Measurements)
        {
            totallength += measure;
        }
        return (int)(totallength / (16 * 12));
    }
    public class BoardCuts
    {
        public BoardCuts(decimal boardSize, decimal makeCutAt)
        {
            BoardSize = boardSize;
            MakeCutAt = makeCutAt;
        }
        /// <summary>
        /// Gets or sets the size of the board.
        /// </summary>
        /// <value>The size of the board in inches.</value>
        public decimal BoardSize { get; private set; }
        /// <summary>
        /// Where the make cut, in inches.
        /// </summary>
        /// <value>Where to make cut, in inches.</value>
        public decimal MakeCutAt { get; private set; }
    }
    /// <summary>
    /// Gets the cuts.
    /// </summary>
    /// <param name="Measurements">The measurements in inches.</param>
    /// <returns></returns>
    public BoardCuts[] GetCuts(decimal[] Measurements)
    {
        Array.Sort(Measurements);
        List<BoardCuts> cuts = new List<BoardCuts>();
        workingQuantities = new Dictionary<decimal, int>(BoardQuantities);
        //process from largest to smallest, so that scraps can be used, if a
        // measurement will fit in the scrap.
        for (int i = Measurements.Length - 1; i >= 0;i-- )
        {
            cuts.Add(new BoardCuts(FindSmallestMatch(Measurements[i]), Measurements[i]));

        }
        return cuts.ToArray();
    }
    /// <summary>
    /// Sets the board quantities.  use int.MaxValue for infinite quantity.
    /// </summary>
    /// <param name="size">The size in inches.</param>
    /// <param name="quantity">The quantity.</param>
    public void SetBoardQuantities(decimal size, int quantity)
    {
        if (BoardQuantities.ContainsKey(size))
        {
            BoardQuantities[size] = quantity;
        }
        else
        {
            BoardQuantities.Add(size, quantity);
        }
    }
}

}

2010-01-20 Reply Admin

This seems to me to be the "greedy algorithm", if you leave out lengths lost to cuts/miters.

Suppose you have a number of files to copy to CDs. To minimize the number of CDs: Iterate: -- Insert a Cd. Pick the largest file (that is not already copied) that will fit on the remaining space of the cd and put it on the CD. Repeat until the CD is full ,or none of the files left will fit on the CD.

Boards are like files; and walls are like CDs. The difference is that you cut the boards to fit and put the remainder back into your pile.

Start with a pile of an infinite number of 8' and 16' boards. Iterate: -- pick the longest bare wall section. If possible, choose from your pile the shortest board that is (same length as, or longer than) the bare wall section. Trim the board to fit, return the remainder to the pile. Otherwise, choose the longest board that will fit into the space (that is, if the space is 9', you choose an 8' board, not a 16' board).

That minimizes the number of boards. If instead, you want to minimize the number of splices, then you change the above to say "Otherwise, choose a 16' board".

2010-01-20 Reply Admin

def numplanks(to_cut, plank_types):
    """
        `to_cut` is a list of cuts in inches
        `plank_types` is a list of planks in feet
    """
    plank_types = sorted(map(lambda x: x * 12, plank_types), reverse=True)
    planks, scraps = [], []

    def find_piece(needed_cut):
        for cut in scraps:
            if cut >= needed_cut:
                scraps.remove(cut)
                return cut

        for plank in plank_types:
            if plank > needed_cut:
                planks.append(plank)
                return plank

    for cut in sorted(to_cut, reverse=True):
        piece = find_piece(cut)
        leftover = piece - cut
        if leftover:
            scraps.append(leftover)

    return planks


cuts = [84, 32, 84] * 16 * 2 # [list of cuts in inches] * 16 doors * 2 sides
planks = [16, 8] # [list of planks in feet]
result = numplanks(cuts, planks)
print len(result) # 38

2010-01-20 Reply Admin

Since when were Imperial measurements referred to as US measurements? I don't recall the USA inventing them, or ever admitting to having an empire.

2010-01-20 Reply Admin

Sounds like a lazy but functional carpenter.

People should get extra points for using a functional language with lazy evaluation (e.g. Haskell) :-P

Cheers,

Daniel

2010-01-20 Reply Admin

Here's a quick-and-dirty solution using a simple algorithm without much optimization:

if the wall is longer than the longest board, use the longest board
if the wall/segment is equal to a board, buy that size board
if the wall/segment can use a leftover, use that leftover
if all those options fail, take the next longest available board and cut it.

http://pastebin.com/f564a4a16

It is unit-less, and works with decimals.

The second step fails to consider that the stated length of the bought board is not likely to be exactly the length of the cut you want to make for the wall.

And, related to the 1/8" or so missing due to the kerf of the saw blade, also consider that most of these cuts will be on a miter - for corners and splices. There will be a number of little triangular pieces left over that will could throw of the calculation.

Now, back to real work...

2010-01-20 Reply Admin

RussJudge:
Simple and easy, with all requirements, written in C#.

I have only browsed your code, but I'm guessing you have implemented a heuristic version. Does your program report 2 as the minimum for a set like {6, 6, 5, 5, 5, 3, 2}?

That is, {{6, 5, 5}, {6, 5, 3, 2}}. If it's a greedy algorithm it will report something like {{6, 6, 3}, {5, 5, 5}, {2}} which is not an optimal solution.

This is a known NP complete problem, so it's not a big deal: finding an optimal solution is difficult in general.

2010-01-20 Reply Admin

And don't forget to deduct the width of the saw blade whenever you make a cut. This is a quite common mistake.

2010-01-20 Reply Admin

"It's far more of a maths challenge than a coding challenge."

Actually, there is a question of optimality, which is interesting. Sure, you could write code that says for every separate measurement, get a single 16' length (or more if the length is greater than 16'). But for a given set of inputs, can you guarantee that your program will give you the measurements of the LEAST amount of moldings to purchase?

To make it even more interesting, what if for the "Hard" version, a 16' board costs $20, and an 8' board costs $12 (or whatever)? Then making your program find the optimal COST becomes slightly more tricky!

DaveE

2010-01-20 Reply Admin

biozinc:
If the goal is to minimise the number of boards, then you'll never use a board other than of the maximum length! What's should we be optimising for in the Medium and Hard case?
-- Note from Alex: Longer boards are usually cheaper by the foot; a 16' length might cost $30, while a 8' could be $16. But if you only need a 8', then no sense in buying a 16'.

You've got it exactly backwards. The long boards are more expensive per foot because of the need of having high quality pieces. A given supply of raw lumber will produce more total footage of 8' boards than 16' boards.

(Note: I'm looking at the costs at the builder level, not the DIY level--I used to work for a cabinet manufacturer.)

2010-01-20 Reply Admin

TT:
And don't forget to deduct the width of the saw blade whenever you make a cut. This is a quite common mistake.

And don't forget to read the existing comments before you duplicate someone else's post. This is a quite common mistake.

2010-01-20 Reply Admin

TRWTF is that the US still uses feet and inches instead of what makes much more sense and is therefore used by the rest of the world.

2010-01-20 Reply Admin

A couple people mentioned miter cuts. Having just reno'd my basement and added all the trim, here's the complication:

When you measure the door, the measurements around the frame are the inside measurements of the cuts - the length needed for it will actually be longer - to be precise, the height of the trim longer, for each miter that is needed.

Consider around a door, the two vertical pieces each have one miter, while the top horizontal piece has two miters:

__________
\        /

|\ ______/ /| | \ ______ / | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | door | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

so your algorithm should account for that.

You'll have the same issue with baseboard for bevel cuts, though only based on the thickness: in an inside corner, it's fine, but for an outside corner, you have to add the thickness of the board to the length.

Also, typically 'casing' is used around doors/windows, while 'baseboard' is used along the floor. The only real difference is (especially with MDF) the bottom of the baseboard (against the floor) is typically unfinished and/or has a sharper edge, while on casing, it will be finished/primed, and typically have a rounded edge.

So your algorithm should account for the difference between the two types of material.

2010-01-20 Reply Admin

Damn proportional fonts...

    __________
    \        /
|\   \______/   /|
| \   ______   / |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
|  | | door | |  |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
|  | |      | |  |
---- -------- ----

alegr · 2010-01-20 Reply Admin

You know what a contractor would do? Just take some more boards, and when he needs a particular length, just go through a pile of offcuts and find the most fitting one.

2010-01-20 Reply Admin

To make things interesting, keep in mind that each cut is going to result in 1/8" of wasted material from the saw blade's "kerf". (The amount of wood removed by the saw blade during the cut)

Each time you make a cut you are going to loose 1/8" of the remaining board, so if you make 8 cuts in a 16' board you only end up able to use 15' 11" of the board.

Captcha: bene - Molto Bene!

2010-01-20 Reply Admin

easy version in Python: (no time for anything longer, and not including the saw blade width)

# individual measurements
spans = [500, 84, 32, 84]

board_length = 192 # 16 feet * 12 inches

# sort the list from smallest measurement to largest
spans = sorted(spans)

print 'You need trim for the following measurements: ', spans

while 1:
    if not all([x <= board_length for x in spans]):
        # pop the largest measurement
        longest = spans.pop(-1)
        print '%s measurement longer than %s inches...splitting' % (longest, board_length)
        longest = longest - board_length
        spans.append(longest)
        spans.append(board_length)
        spans.sort()
        print spans
    else:
        break
    
boards = []
while spans:

    board_sum = 0
    new_board = []
    new_board.append(spans.pop(-1))
    board_sum = sum(new_board)
    if board_sum < board_length:
        for meas in reversed(spans):
            if board_sum + meas <= board_length:
                    new_board.append(meas)
                    spans.remove(meas)
                    board_sum = sum(new_board)
                    break

    boards.append(new_board)

print 'You will need %s boards.' % len(boards)
print 'With the following cuts: ', boards

2010-01-20 Reply Admin

Ramses So let it be written so let it be done:
Solution used in most American produced housing: Don't give the customer stained wood trim or charge them way extra so they don't want to pay for it. Force painted wood on them because most carpenters can't afford a computer and are too dumb to figure it out manually and rely on the lumber yard to figure it out for them and the lumber yard is usually wrong. You see, with painted wood trim you can splice whereever you want and hide it by caulking the joint in the wood and painting over it so the customer will never see it. In a past life I was a construction manager and these were the tricks of the trade.

I always found it cheaper and more efficient to order the right amount of wood than to spend the time and money chalking, sanding, and pissing off customers with junk fees. If you build the cost to do it right into the price, the customer is none the wiser.

amischiefr · 2010-01-20 Reply Admin

Anonymous:
Subtext: Alex is doing some remodeling (rennovating) and can't be bothered doing the calculations himself.

That's what this sounds like, a "let me see if I can get these suckers to do this for me!!! Haha watch this guys, these dumbasses will write our code for us!"

2010-01-20 Reply Admin

You could also save the time by instead of using 45 degree miters, use plinth blocks at each corner to fancy it up a bit. The labor savings would probably cover the cost of the extra materials. Also I didn't see where windows were to be accounted for. The only rooms I have ever been in with no windows are on a cruise ship and in my office at work.

2010-01-20 Reply Admin

It's interesting to me that the "lazy" carpenter is the one doing all these splices.

Wouldn't it be considerably lazier to avoid splices? If your wall is longer than any of your already-cut scraps, just grab another 16-footer?

2010-01-20 Reply Admin

Without adding the complication of price, you also could define your ideal solution as the minimum number of splices, and the minimum amount of scrap (in inches of board).

avflinsch · 2010-01-20 Reply Admin

Matthias:
TRWTF is that the US _still_ uses feet and inches instead of what makes much more sense and is therefore used by the rest of the world.

In some respects using feet & inches actually makes more sense than going metric. Feet divide nicely by 2,3,4,6 which makes scaling something to 1/2, 1/3, or 1/4 of the original size easy, on the other hand, going to 1/10 is a bit of a bitch.

avflinsch · 2010-01-20 Reply Admin

ClutchDude:
For those not sure
For instance....we have a 4x 12'(3.67m) walls. I COULD only buy 3x 16'(4.88m) boards and use the scrap to finish the other wall. BUT....then I end up with a crappy looking seam @ 4ft & 8ft.

A good contractor would buy 4x 16'(4.87m) boards and do it right.

A good contractor would buy 4 x 12' boards and not bother cutting.

2010-01-20 Reply Admin

Haskell, not sure of its running time, not extensively tested (although it passes the example mentioned in the statement of the problem), doesn't account for cuts. But hey, I'm learning haskell so it was fun.

import Control.Applicative
import IO
import System.Environment
import Text.Regex
import List (group)

hasPlace :: [Int] -> Int -> Int -> Int
hasPlace (b:boards) this u
         | u+this < b*12 = b
         | otherwise = hasPlace boards this u
hasPlace [] _ _ = 0

findMakePlace :: [Int] -> Int -> [(Int,Int)] -> [(Int,Int)]
findMakePlace boards this [] = [(hasPlace boards this 0,this)]
findMakePlace boards this ((s,u):used) = let b = hasPlace boards this u
                                          in if b > 0 then (b,u+this):used
                                           else (s,u):findMakePlace boards this used

fillBoards :: [Int] -> [Int] -> [(Int,Int)]
fillBoards needs boards = foldr (findMakePlace boards) [] needs

avoidSplices :: [Int] -> [Int] -> [(Int,Int)]
avoidSplices needs boards = let gs = group (map fst (fillBoards needs boards))
                             in zip (map length gs) (map head gs)

output :: [(Int,Int)] -> [IO ()]
output [] = []
output ((count,board):results) = (putStrLn ((show count) ++ " boards of length " ++ (show board) ++ "'")):output results

main :: IO ()
main = do args <- getArgs
          let needs:boards:[] = map read <$> map (splitRegex $ mkRegex ",") args
           in sequence $ output $ avoidSplices needs boards
          return ()

2010-01-20 Reply Admin

Should have put "(sort boards)" in calling fillBoards, otherwise when boards are specified in descending order it wastes a lot of wood.

2010-01-20 Reply Admin

Ok, Alex has officially made me feel stupid. I couldn't understand a word of this post...

2010-01-20 Reply Admin

Solution: Use cheap, white trim. Caulk the seams. Paint it all white.

No maths be needed. Arrrggghhh!

2010-01-20 Reply Admin

With the (sort boards) modification of my haskell, it does seem to give reasonable results for the hard case:

runhaskell avoiding_the_splice.hs 84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,84,32,84,24,12,24,24,12,24 19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1
1 boards of length 18'
31 boards of length 17'
1 boards of length 10'

2010-01-20 Reply Admin

Longer boards are usually cheaper by the foot; a 16' length might cost $30, while a 8' could be $16.

Depends on what kind of wood you're buying (and I don't mean high end hard-to-get). Often, a 16' length of unspliced stainable wood will be noticeably more than the cost of two 8' foot boards just because its harder to get a good quality long piece of unblemished wood...

brill · 2010-01-20 Reply Admin

Actually, you still might not have enough moulding because you failed to take into account the width of the moulding.

For example the door dimensions are the dimensions of the door jam, but when doing moulding you are going to join two pieces a the corner (hopefully your going to miter the corners, but it will apply even if you don't) and door mouldings are almost always laid flat, so you need to take into account the width of the moulding as <dimension> + 2(pythagorean theorem using moulding width for sides).

So, for example if the moulding is 3" wide and the jam is 32" then: 32+2(sqrt(3^2+3^2)) or 32+2*4.25 (<= note, rounded to nearest easy fraction)

so you moulding length needs to be ~40.5".

brill · 2010-01-20 Reply Admin

Crap... overanalyzed!

... and screwed that up... I added the length of the diagonal cut... which would not be correct... you simply need to add 2*[moulding width].

so for the example above it would be: 32+2*3.

2010-01-20 Reply Admin

Finknottle:
This is a known NP complete problem, so it's not a big deal: finding an optimal solution is difficult in general.

Actually, an algorithm for calculating the optimal solution isn't usually too hard to come up with. But it is going to be slow, because it involves comparing all possible solutions. For instance, the travelling salesman problem has an easily understood algorithm that solves the problem, but the algorithm takes a long time to run and gets vastly slower as you add more input data.

In this case, I believe an accurate solution would be to calculate all combinations of wall lengths adding up to all combinations of under 8 and 16 feet, and then compare all these combinations for which is considered optimal. I think the constraints here suggest that "the fewest number of boards" would be considered optimal, but perhaps if the costs of 8 and 16 foot boards were known, the comparison would be total cost and possibly result in different outcomes in some cases.

2010-01-20 Reply Admin

I hang with a lot of Canadians.

They all still use Imperial measurements for woodworking anyway.

2010-01-20 Reply Admin

This is the "packing" problem in computer science, and can't be solved optimally without investigating every possible combination, which is exponential in the number of cases.

2010-01-20 Reply Admin

Sigivald:
I hang with a lot of Canadians.
They all still use Imperial measurements for woodworking anyway.

Yup, I can confirm this one. For whatever reason (perhaps something to do with where building supplies are produced?) we (Canadians) use metric for pretty much everything except construction.

We also use about a 50/50 mix of metric and imperial for recipes and wrench sizes just to keep things confusing.

avflinsch:

Feet divide nicely by 2,3,4,6 which makes scaling something to 1/2, 1/3, or 1/4 of the original size easy, on the other hand, going to 1/10 is a bit of a bitch.

I'd never really realized this before. As someone who has grown up using the metric system I always wondered what possible advantage having 12 inches in a foot gave, but I'd never put any serious thought into it, so thanks for the info.

kramthegram · 2010-01-20 Reply Admin

I wrote a python version that assumes longer boards are cheaper. It also makes sure you don't buy a board that is way too long for the project. Example: buying a 16 foot board for 5 inches needed when you have 16 and eight to choose from.


def the_splice(measurements,board_lengths):
	#sort measurements larget to smallest
	measurements.sort()
	measurements.reverse()
	#convert boards to inches, then sort largest to smallest
	board_lengths = map(lambda x: x * 12, board_lengths)
	board_lengths.sort()
	board_lengths.reverse()
	print measurements,board_lengths
	#set up lists for scraps, and purchased wood
	scraps=[]
	purchased=[]
	prune_board_lengths(measurements,board_lengths)
	for needed in measurements:
		find_board(needed,board_lengths,scraps,purchased)
	return map(lambda x: x / 12, purchased),scraps

def find_board(desired,boards,scraps,purchased):
	#try scrap
	print "finding board"
	print "need atleast", desired
	piece=find_from_scrap(desired,scraps)
	if(piece):#testing if we got a piece
		print piece
		piece=piece-desired
		#append remaining to scraps
		scraps.append(piece)
	else: #we didn't find a scrap, try a whole piece
		print "scrap unusable, buying a new piece"
		piece=find_from_board(desired,boards)
		print piece
		purchased.append(piece)
		piece=piece-desired
		#append remaining to scraps
		scraps.append(piece)
		
	
def find_from_scrap(desired_length,scrap_lengths):
	"""this is a special case for scraps, we want to you the scrap that leaves the least remainder"""
	print "searching scrap"
	scrap_lengths.sort()
	for length in scrap_lengths:
		if(desired_length<length):
			scrap_lengths.remove(length)
			return length

def find_from_board(desired_length,board_lengths):
	"""removing from boards, in this case we like to buy big boards first for cost savings, note this logic fails if you only need one small piece"""
	print "finding new piece"
	for length in board_lengths:
		if(desired_length<length):
			return length

def prune_board_lengths(measurements,board_lengths):
	"""to make sure we don't over purchase we remove any board_lengths that are way to long"""
	total=0
	for measurement in measurements:
		total=total+measurement
	long_lengths=[]
	for length in board_lengths:
		if(length>total):
			long_lengths.append(length)
	long_lengths.sort()
	#now we have a list lof all lengths largest than we need
	#we want to remove all but the first one from the potential boards
	long_lengths.remove(long_lengths[0])
	for length in long_lengths:
		board_lengths.remove(length)

measurements=[23,15,18,18,13,13,38]
board_lengths=[8,16,32]

purchased,scrap = the_splice(measurements,board_lengths)

print "For the measurements:",measurements
print "and board lengths:", board_lengths
print "The suggested purchase is:", purchased, "(in feet)"
print "with scrap:", scrap, "(in inches)"

2010-01-20 Reply Admin

I can't really see a way to code the easy part without also coding the hard bits.

Easy = only 16' boards Say you need a 10' piece You need to store the remaining 6' piece somewhere The next piece you need, you check if you can supply it with either the single 6' piece you have or with one of your infinite supply of 16' pieces.

So even in the easy option, you'd need to find the best possible fit from a list of available lengths, some of which were in limited supply and some of which were available in infinite amounts. It seems to me that the only real difference in the three tiers is the initial state of this list.

2010-01-20 Reply Admin

I found a Wikipedia page about this problem: http://en.wikipedia.org/wiki/Cutting_stock_problem

2010-01-20 Reply Admin

That sounds like a linear optimisation problem to me. There are programs where you can enter such problems and they solve it. I don't like to do things that even computers can solve. I want to do things that computers cannot (yet) do and teach them to the computer. ;)

2010-01-20 Reply Admin

10 if (not trimmed) hire carpenter 20 if (screwed up) hire lawyer.

100 goto 10

2010-01-20 Reply Admin

Ramses So let it be written so let it be done:
Solution used in most American produced housing: Don't give the customer stained wood trim or charge them way extra so they don't want to pay for it. Force painted wood on them because most carpenters can't afford a computer and are too dumb to figure it out manually and rely on the lumber yard to figure it out for them and the lumber yard is usually wrong. You see, with painted wood trim you can splice whereever you want and hide it by caulking the joint in the wood and painting over it so the customer will never see it. In a past life I was a construction manager and these were the tricks of the trade.

Bullshit. Splices are almost impossible to hide. It's not worth the massive effort to try to hide them. Just better to buy more paint grade MDF and rip out the previous work.

Zolcos · 2010-01-20 Reply Admin

I once saw an RFP to solve this problem in 3D -- that is, the pallet packing problem. Given fixed dimensions of 3d space you can use atop each pallet, the algorithm must take a collection of arbitrarily sized (and shaped) items and arrange them onto the least number of pallets where each load is physically possible to pack, supports itself without an outer container, and has a sufficiently low center of gravity.

2010-01-20 Reply Admin

If you hire a carpenter with sufficient skill you can't see the join when she splices two boards together. I doubt she would get away with door and window casings but the skirting boards are excellent.

2010-01-20 Reply Admin

In practice, there is another constraint you failed to mention; you want to start with the longest piece first and work your way down so that a damaged or wrongly cut piece can be used for something shorter. This constraint results in the usual algorithm that people actually use:

buy more than you think you will need (like 10% more)
find the longest wall
cut a piece to fit out of the shortest piece you can
repeat until done
return the unused pieces

I know this is not ideal, but carpenters don't have time to write code. :)

2010-01-20 Reply Admin

This is the same as the classic "bin problem":

http://en.wikipedia.org/wiki/Bin_packing_problem

The analogy is that the bin size represents the max length of an uncut board (say, 16 feet if you've got a big truck). A naive solution works like this:

// array of boards we'll need. Each element represents one uncut board. The value of each element is the number of inches of board remaining. int[] Boards

// Spans that we need to cut. int[] Spans

while(Spans.Count>0) { int thisSpan=Spans[0];

for(int i=0;i<boards.Count;i++) { if(boards[i]>=thisSpan) { boards[i]-=thisSpan; continue; } // add a new board 16 feet long boards[boards.length]=16*12; }

}

Now, the number of elements in Boards is the number of 16 foot boards you'll need.

This isn't a perfect solution, but it's pretty darn close and is correct for almost every situation.

2010-01-20 Reply Admin

You could solve this problem using an evolutionary algorithm. There's no guarantee it'll return the optimal result (but usually will) and will run in unit time.

Start by taking any initial valid layout of cuts, do an arbitary number of mutations, keeping track of the best result found so far. The mutation could simply be to move a cut to another board.

I'll give it a go and post my solution later.

Avoiding the Splice

Leave a comment on “Avoiding the Splice”