Lua Wood cutter lua

[roriscrave]

I need to check the minimum amount of wood for cutting.
each trunk is 12 meters long, need to cut (10 pieces of 3.5m + 8 pieces of 4.5m + 15 pieces of 5m)

exemple, if i cut 12m in 4,5 + 4,5 there will be 3m left, which will be "lost", as it cannot be used in any other cut
if i cut 1x 5 + 2x3.5 there will be 0m left, and rest 0m "lost".

what is the minimum amount of trunk I can use?
I need the solution that always finds the least amount of "wood scraps"

local trunk = 12 -- (each wood have 12 meters)

local cuts = {
        -- ex: he need to cut 10 pieces, with 3,5meters each cut
[1] = {count = 10, meter_each = 3.5},
        -- ex: he need to cut 8 pieces, with 4,5meters each cut
[2] = {count = 8, meter_each = 4.5},
        -- ex: he need to cut 15 pieces, with 5meters each cut
[3] = {count = 15, meter_each = 5},

}
function onUse(player, item, fromPosition, target, toPosition, isHotkey)
    player:sendTextMessage(22, "The minimum for cutting is X woods and Y meters.")  
    return true
end

 

[Akela]

I think it will be quite difficult to find a generally optimal solution. Do you need it to be perfect, or want it to be perfect?

 

[roriscrave]

I think it will be quite difficult to find a generally optimal solution. Do you need it to be perfect, or want it to be perfect?

as over time i will add more woods, the solution can be close to ideal.
90/80% close to ideal is enough

@fabian766
@Cjaker
@Infernum
@kondra
@Nekiro
@oen432
@Mkalo​

 

[Akela]

80% might be achievable if you keep the amount of variation down, but the complexity will grow very fast with additioinal sizes of the logs and sawn timber. Finding an ok solution won't be hard - knowing it's the best showing it's the best will be difficult. And if you don't kniow what the best solution is, you don't have a numerical "stopping rule".

Try (1) finding a solution to the example yourself, and then (2) proving it's the best solution.

I got 22 meters of waste timber. I'm not going to try to prove it's the best answer though - as I said above, that's the hard part
I don't know of a better way than going through every possible solution.

 

[Sarah Wesker]

function getCuts(meters, each)
    local cuts = math.floor(meters / each)
    return cuts, meters - (each*cuts)
end

local cuts, residue = getCuts(12, 3.5)
print(string.format("You have %d cut's with 3.5 meters each of a trunk of 12 meters, residue: %s meters.", cuts, residue))

output:

You have 3 cut's with 3.5 meters each of a trunk of 12 meters, residue: 1.5 meters.

 

[roriscrave]

function getCuts(meters, each)
    local cuts = math.floor(meters / each)
    return cuts, meters - (each*cuts)
end

local cuts, residue = getCuts(12, 3.5)
print(string.format("You have %d cut's with 3.5 meters each of a trunk of 12 meters, residue: %s meters.", cuts, residue))

output:

You have 3 cut's with 3.5 meters each of a trunk of 12 meters, residue: 1.5 meters.

but you have to cut 10x 3.5m, 8 x 4.5m, 15x 5m, in order to generate the smallest residue

each trunk for cutting have12 meters, you will need how many trunk to cut this above, and what will be the residue?

 

[Akela]

My quick heuristic solution was:

• 5 x ( (2 x 3.5) + (1 x 5) ) => zero waste
• 5 x (2 x 5) => 5 x 2 waste = 10 waste
• 4 x (2 x 4.5) => 4 x 3 = 12 waste
• total 22 waste

There are two others I'd test next that might be better, but that's not really the point.

• It's easy to make the example more difficult.
• It's relatively easy to create a heuristic solution generator
• I think it's hard to create a "non-brute-force" algorithm that produces the best solution - which, if true, means it's hard to know how good any given heuristic solution is.

FWIW it's possible there's an "Integer Programming" solution to this, but they require considerable skill to specify, and the tech to perform the calculations is complex.

 

[Sarah Wesker]

I'm still not sure what you want, but this is a good example to start with.

function getCuts(meters, each, count)
    local cuts = math.min(count, math.floor(meters / each))
    return cuts, meters - (each*cuts)
end

local config_cuts = {
    { count = 10, meters = 3.5 },
    { count = 7, meters = 1.5 },
    { count = 5, meters = 0.5 }
}

-- in case the table is messy.
table.sort(config_cuts, function(a, b) return a.meters > b.meters end)

local trunkMeters = 120
local cuts, residue = 0, trunkMeters
local totalCuts = {}

for i = 1, #config_cuts do
    local config = config_cuts[i]
    cuts, residue = getCuts(residue, config.meters, config.count)
    totalCuts[config.meters] = (totalCuts[config.meters] or 0) + cuts
end

for k, v in pairs(totalCuts) do
    print(string.format("You have %d cut's with %s meters each.", v, k))
end

print(string.format("residue: %s meters of a trunk with %s meters.", residue, trunkMeters))

output:

You have 10 cut's with 3.5 meters each.
You have 7 cut's with 1.5 meters each.
You have 5 cut's with 0.5 meters each.
residue: 72.0 meters of a trunk with 120 meters.

 

[roriscrave]

My quick heuristic solution was:

• 5 x ( (2 x 3.5) + (1 x 5) ) => zero waste
• 5 x (2 x 5) => 5 x 2 waste = 10 waste
• 4 x (2 x 4.5) => 4 x 3 = 12 waste
• total 22 waste

There are two others I'd test next that might be better, but that's not really the point.

• It's easy to make the example more difficult.
• It's relatively easy to create a heuristic solution generator
• I think it's hard to create a "non-brute-force" algorithm that produces the best solution - which, if true, means it's hard to know how good any given heuristic solution is.

FWIW it's possible there's an "Integer Programming" solution to this, but they require considerable skill to specify, and the tech to perform the calculations is complex.

is this kind of solution that I need, is it possible to be done by lua? the code to solve the problem demonstrating the most economical way (less waste)

@Sarah Wesker you didn't get it right.
imagine: you have several 12 meter trunks.
what is the best way to cut with the sizes defined in the code, without too much wast?

ex: if you cut 3 pieces of 3.5, you used 10.5m of the trunk, 1.5m left (will be wast), because there is no piece with this dimension.
if you cut 2 pieces of 3.5 and one of 5m, you cut 12m (there were no losses).
I need the solution that gives less losses

 

[Akela]

Sarah

I think he has a supply of large pieces that are 12 meters long, and a set of shorter lengths that have to be cut from 12-meter pieces.
He wants to minimize waste for the 12-meter pieces that are used.

Treating the 12-meter pieces as one large piece is a different problem.

My approach was to loop on selecting the set of available smaller pieces that's closest to 12 meters, and making as many of those as I can.
It's a standard "first try" at a heuristic for this kind of problem, and can produce acceptable results if there aren't too many "confounding factors"

If I was doing it manually, I'd also try

• Start with 3 x 3.5 = 10.5 meters and continue to the end.
• Start with 2 x 5 = 10 meters and loop to the end.

The problem is that if you have say 11 different shorter lengths, mutually prime numbers required for each one, and less convenient lengths (ending in x.0 and x.5 simplifies things) simple heuristics are less useful.

Post automatically merged: Dec 16, 2020

roriscrave

My heuristic is easy to code. But you can never know how good the solution is, and the problem can get too complex for the simple heuristic rather easily.

On the other hand it's a game - if you control the problem so it's not so hard, a simple heuristic can be used



PS. I think this is what you're asking:

Cutting stock problem - Wikipedia

en.wikipedia.org

This is the next step up - it's known to be computationally complex in many cases:

Knapsack problem - Wikipedia

en.wikipedia.org

 

[Sarah Wesker]

Here you have another similar example, I was not very careful, but it seems to work as you want, this code probably fits 90% in what you want

function getCuts(meters, each, count)
    local cuts = math.min(count, math.floor(meters / each))
    return cuts, meters - (each*cuts)
end

local config_cuts = {
    { count = 20, meters = 3.5 },
    { count = 80, meters = 1.5 },
    { count = 50, meters = 4.2 }
}

table.sort(config_cuts, function(a, b) return a.meters > b.meters end)

local trunk = { count = 14, meters = 12 }
local totalResidue = trunk.count * trunk.meters
local cuts, residue = 0, trunk.meters
local totalCuts = {}

for t = 1, trunk.count do
for i = 1, #config_cuts do
    local config = config_cuts[i]
    cuts, residue = getCuts(residue, config.meters, config.count)
    config_cuts[i].count = config_cuts[i].count - cuts
    totalCuts[config.meters] = (totalCuts[config.meters] or 0) + cuts
end
if trunk.count > 0 then
    residue = trunk.meters
    trunk.count = trunk.count - 1
end
end

for k, v in pairs(totalCuts) do
    totalResidue = totalResidue - (v * k)
    print(string.format("You have %d cut's with %s meters each.", v, k))
end

print(string.format("total residues: %s meters adding all the pieces of excess wood, |o.o|", totalResidue))

output:

 

[roriscrave]

@Sarah Wesker
I liked you for trying to help, but the code is not correct.
Try to read @Akela explanation just above, he explained how it works, it’s exactly as he explained

 

[Sarah Wesker]

@roriscrave you're welcome, I was just trying to do something fast while I was listening to music and resting in the comfort of my bed, anyway, I hope I gave you some ideas, or at least trying was fun.

 

[Xikini]

I assume there is a better solution...

But my solution would be to manually find all the different possibilities...
And then just loop downwards from most efficient to least efficient, and get a pretty decent result?

I have no idea how you'd code this to automatically find all the different possibilities. xD

--[[
5 + 3.5 + 3.5 = 12 -> 0
4.5 + 3.5 + 3.5 = 11.5 -> 0.5
3.5 + 3.5 + 3.5 = 10.5 -> 1.5
5 + 5 = 10 -> 2
5 + 4.5 = 9.5 -> 2.5
4.5 + 4.5 = 9 -> 3
5 + 3.5 = 8.5 -> 3.5
3.5 + 4.5 = 8 -> 4
3.5 + 3.5 = 7 -> 5
5 = 5 -> 7
4.5 = 4.5 -> 7.5
3.5 = 3.5 -> 8.5
]]--

local function calculateCuts(woodA, woodB, woodC) -- woodA = 5, woodB = 4.5, woodC = 3.5
    local cuts = {0, 0, 0}
    local waste = 0
    local trunksCut = 0
  
    while woodA + woodB + woodC > 0 do
        if woodA >= 1 and woodC >= 2 then
            woodA = woodA - 1
            woodC = woodC - 2
            cuts[1] = cuts[1] + 1
            cuts[3] = cuts[3] + 2
        elseif woodB >= 1 and woodC >= 2 then
            woodB = woodB - 1
            woodC = woodC - 2
            cuts[2] = cuts[2] + 1
            cuts[3] = cuts[3] + 2
            waste = waste + 0.5
        elseif woodC >= 3 then
            woodC = woodC - 3
            cuts[3] = cuts[3] + 3
            waste = waste + 1.5
        elseif woodA >= 2 then
            woodA = woodA - 2
            cuts[1] = cuts[1] + 2
            waste = waste + 2
        elseif woodA >= 1 and woodB >= 1 then
            woodA = woodA - 1
            cuts[1] = cuts[1] + 1
            woodB = woodB - 1
            cuts[2] = cuts[2] + 1
            waste = waste + 2.5
        elseif woodB >= 2 then
            woodB = woodB - 2
            cuts[2] = cuts[2] + 2
            waste = waste + 3
        elseif woodA >= 1 and woodC >= 1 then
            woodA = woodA - 1
            cuts[1] = cuts[1] + 1
            woodC = woodC - 1
            cuts[3] = cuts[3] + 1
            waste = waste + 3.5
        elseif woodB >= 1 and woodC >= 1 then
            woodB = woodB - 1
            cuts[2] = cuts[2] + 1
            woodC = woodC - 1
            cuts[3] = cuts[3] + 1
            waste = waste + 4
        elseif woodC >= 2 then
            woodC = woodC - 2
            cuts[3] = cuts[3] + 2
            waste = waste + 5
        elseif woodA >= 1 then
            woodA = woodA - 1
            cuts[1] = cuts[1] + 1
            waste = waste + 7
        elseif woodB >= 1 then
            woodB = woodB - 1
            cuts[2] = cuts[2] + 1
            waste = waste + 7.5
        elseif woodC >= 1 then
            woodC = woodC - 1
            cuts[3] = cuts[3] + 1
            waste = waste + 8.5
        end
        trunksCut = trunksCut + 1
    end
    return cuts, waste, trunksCut
end

local cuts, waste, trunks = calculateCuts(15, 8, 10)

print(trunks .. " trunks were cut to receive (" .. cuts[1] .. ") 5m, (" .. cuts[2] .. ") 4.5m and (" .. cuts[3] .. ") 3.5m cuts of wood.")
print("A total of " .. (trunks * 12) .. "m wood was cut, with " .. waste .. "m of waste. (" .. ((math.floor(((waste / (trunks * 12)) * 10000) + 0.5))/100) .. "% waste)")

result

14 trunks were cut to receive (15) 5m, (8) 4.5m and (10) 3.5m cuts of wood.
A total of 168m wood was cut, with 22m of waste. (13.1% waste)

 

[Akela]

I'm not set up to write LUA code at the moment (haven't done it in more than 5 years), but I'm going to install LUA and find a development environment (hopefully there's Eclipse support).

But this means I can't write any code at the moment.
If someone else wants to implement it I can explain how to implement the heuristic I used as a generic program.

Note: this isn't the same thing as a program that can find the best solution (see below). It would probably be a useful starting point though.

As for finding the best solution: That's possible by a variant of this heuristoc ... and if you don't mind the program possibly taking a long time (tens of minutes) it might be possible to run it in LUA. But please don't underestimate the complexity issue: computation for problems like this grows much faster than the number of extra elements that are added to the specific problem - e.g. they run its "big brother", the Knapsack Problem, for hours on supercomputers.

Anyway we can move forward now if someone else wants to play a bit with LUA. I'll explain the steps for a generic implementation here.

I'm not sure it will be practical to hack a program that runs inside OT that always find the optimal solutuion, but I suppose we could make a version of the heuristic that enumerates every possible solution, and perhaps has some logic to reject obviously bad ones (to improve efficiency a bit.
If an optimal solution is required for an open-ended version of your objective, it will almost certainly be smarter to study the techniques used by commercial solutions, starting with the first wikipedia article I linked above.

All that said, the first step is just to write some logic to enumerate all the possible combinations of the smaller pieces that, in total, are less than or equal to the larger piece.

An aside: this becomes computationally inefficient with a large number of distinct longer pieces and/or a larger number of distinct shorter pieces. On the other hand, with a forest worth of trees and lots of smaller pieces, an easier approach (a different heuristic) can be used.

So: the enumeration can e.g. start with the longest cut piece, and go through the possibilities like this (using the initial example):

Start with the largest: 5, then continue in order:

• 5 < 12, 2 x 5 is less than 12, 3 x 5 is > 12; => (1 x 5) and (2 x 5) are a possible cuts
• 5 + 4.5 < 12 , (5 + (2x4.5)) > 12, 5 + 4.5 + 3.5 > 12 => 5 + 4.5 is a possible cut
• 5 + 3.5 < 12, 5 + (2 x 3.5) = 12 => (5 + 3.5) and (5 + (2 x 3.5)) are possible cuts
• -----
• 4.5 < 12, 2 x 4.5 < 12, 3 x 4.5 > 12, so (1 x 4.5) and (2 x 4.5) are possible cuts
• etc

Edit:
The next bit generates a solution.
It turns out the approach I used even has a wikipedia page

Greedy algorithm - Wikipedia

en.wikipedia.org

It's probably a good place to start looking for better algorithms, but I'm hoping that won't be necessary

Given the knows variables (Original size(s): 12 m in our example, and useful output sizes and numbers (10x3.5, 8x4.5, 15x5)).
Keep looping on this until all useful outputs have been produced:

• Fully allocate the "best fit" possible cuts: in this case only 5 + 3.5 + 3.5 = 12 (no waste)
  • This can be done 5 times before the 3.5's are fully cut
• Step to the next available best fit, which is 2 x 5 = 10 (2 waste) and fully allocate that
• Loop until you have a solution.

Important: by starting with (5 + (2 x 3.5) ) we lose some possibilities.
This is why we can't get an optimal solution just with this particular heuristic. Each early selection is likely to remove some options, such as 3 x 3.5 = 10.5).

This can be handled by another simple heuristic: try multiple different starting points, starting with the best one(s) (i.e. zero waste), and e.g. moving down through a fixed number, or until efficiency is too low (e.g. 40% waste) or something like that.
This is where my earlier comment:

There are two others I'd test next that might be better

came from. The two other obvious starting points were:

• 3 x 3.5
• 5 + 4.5

A programmed solution might also try starting at (4.5 +(2 x 3.5)) and (2 x 4.5).

Trying different starting points could be added in version 0.3 (0.1 being the enumeration, 0.2 adding the first solution).

NB: even trying all the different starting points doesn't guarantee an optimal solution: starting with (3 x 3.5), but then applying "fully allocate the next best fit" could also remove some options.

 

[roriscrave]

@Xikini @Akela, thank you, thought it wouldn't be that hard xD
I’ll take the topic open, if anyone can contribute it will be welcome

 

[Akela]

This is easy to specifiy, but not as easy to implement.
It's also a different kind of logic than I've seen so far on OTLand, so there may not be many (or any) reusable fragments available.

If you can find someone who wants to do it I'll help them, but you shouldn't expect it to "code itself"

FWIW - this is a potentially useful "learning opportunity" for someone who enjoys LUA coding. But of course, like any learning opportunity it will be difficult/inefficient at first.

 

[Akela]

roriscrave

I did this in Java as an exercise (needed a warm-up because I haven't done any coding in a while).

It implements the "Greedy Algorithm", and given your example parameters, it produces my original solution (with 22 meters of waste).

It's about 400 lines of active code (800 with comments and blanks). I write for readability, not compactness (that's the compiler's job so it could perhaps be reworked to 300 lines. At a guess I'd say 300 +/- 100 lines of LUA if coded similarly to the examples I see here (in LUA support questions).

NB: Logic is logic, but data structures are implemented very differently in Java (at least compared to anything I've seen here). It's probably not practical to "port" my Java code to LUA, nor to give it to someone who doesn't know Java as starting point.

 

[roriscrave]

roriscrave

I did this in Java as an exercise (needed a warm-up because I haven't done any coding in a while).

It implements the "Greedy Algorithm", and given your example parameters, it produces my original solution (with 22 meters of waste).

It's about 400 lines of active code (800 with comments and blanks). I write for readability, not compactness (that's the compiler's job so it could perhaps be reworked to 300 lines. At a guess I'd say 300 +/- 100 lines of LUA if coded similarly to the examples I see here (in LUA support questions).

NB: Logic is logic, but data structures are implemented very differently in Java (at least compared to anything I've seen here). It's probably not practical to "port" my Java code to LUA, nor to give it to someone who doesn't know Java as starting point.

i also know how to write in java, would there be any problem if you send me the code so i can read it? and i`ll try to transcribe it to the LUA

 

[Akela]

Sure - you can have a copy. I'll probably zip it and attach it here if that's ok for you? Though that means everyone gets to see I'm a terrible Java coder /lol.

I'll need to clean the code up (the structure isn't right, and it's full of comments reminding me how to use newer Java features) but it should be ready in a week or two.


Here's the output for your example:

Required Cuts:
    5.0:  Cut [cutLength=5.0, numberRequired=15, cutCount=0]
    4.5:  Cut [cutLength=4.5, numberRequired=8, cutCount=0]
    3.5:  Cut [cutLength=3.5, numberRequired=10, cutCount=0]


All valid Cut partitions:
    0:  CutPartition [cutList=[5.0, 3.5, 3.5], totalLength=12.0, count=0]
    1:  CutPartition [cutList=[4.5, 3.5, 3.5], totalLength=11.5, count=0]
    2:  CutPartition [cutList=[3.5, 3.5, 3.5], totalLength=10.5, count=0]
    3:  CutPartition [cutList=[5.0, 5.0], totalLength=10.0, count=0]
    4:  CutPartition [cutList=[5.0, 4.5], totalLength=9.5, count=0]
    5:  CutPartition [cutList=[4.5, 4.5], totalLength=9.0, count=0]
    6:  CutPartition [cutList=[5.0, 3.5], totalLength=8.5, count=0]
    7:  CutPartition [cutList=[4.5, 3.5], totalLength=8.0, count=0]
    8:  CutPartition [cutList=[3.5, 3.5], totalLength=7.0, count=0]
    9:  CutPartition [cutList=[5.0], totalLength=5.0, count=0]
    10:  CutPartition [cutList=[4.5], totalLength=4.5, count=0]
    11:  CutPartition [cutList=[3.5], totalLength=3.5, count=0]


Final outputCutsTrackerMap (for debug/verification):
    5.0:  Cut [cutLength=5.0, numberRequired=0, cutCount=15]
    4.5:  Cut [cutLength=4.5, numberRequired=0, cutCount=8]
    3.5:  Cut [cutLength=3.5, numberRequired=0, cutCount=10]


Final cutPartitionsTrackerMap (used elements only):
    0:  CutPartition [cutList=[5.0, 3.5, 3.5], totalLength=12.0, count=5]        Waste: 0.0
    3:  CutPartition [cutList=[5.0, 5.0], totalLength=10.0, count=5]        Waste: 10.0
    5:  CutPartition [cutList=[4.5, 4.5], totalLength=9.0, count=4]        Waste: 12.0

Total waste: 22.0

The solution generator currently starts with the first CutPartition (Map Key 0) and keeps going by Key in ascending numerical order until it's done.
I can vary the evaluation sequence by varying the Key <-> Valid CutPartition relationships, but I haven't written any logic for that, and probably won't.

FWIW, in this case the first valid solution is probably the best, or close to it. Proving that would be a matter of either trying everything (perhaps with some simple pruning for efficiency), or writing some very complex logic. With more possible cuts and e.g. multiple stock (log) lengths "trying everything" could require a lot of processing.