small Math + Computer Science challenge

  • Hey - turns out IRC is out and something a little more modern has taken it's place... A little thing called Discord!

    Join our community @ https://discord.gg/JuaSzXBZrk for a pick-up game, or just to rekindle with fellow community members.

DaTeL

DaTeL

=]DoG[=Food
Oct 23, 2002
2,659
48
Holland
Heyo, little challenge I have for you all to solve together :) (not my challenge, but mine to solve :P)

To transport palmtops, they're mass-packed into boxes without their retail packing. These palmtops are of size 2x8x12 cm (dxwxh). In the larger box, the palmtops are all aligned in the same direction. Inbetween the palmtops and between a palmtop and the 'wall' needs to be 2cm of polystyrene foam in all directions. We're trying to find the best size for the box given an amount N of palmtops. The 'best' size is the one that has the least volume.

mathematically, we're trying to minimize
V(D,W,H) = (2+4D) * (2+10W) * (2+14H) = 8 + 16D + 40W + 28H + 80DW + 112DH + 280WH + 560DWH
with D,W,H being integer values
such that D*W*H >= N and D>=1 and W>=1 and H>=1

example:
given: N = 10
best size = V(5,2,1) = 22*22*16 = 7744 cm^2

ok, so we're trying to make an algorithm that efficiently finds the best values (worst way is trying all combinations of W,H,D in the range [1,N] :P)

approach I had in mind was starting out with V(D,W,H)=V(N,1,1) and then raising W and H while lowering D.... but which one to raise and when to stop?

any help appreciated (other approaches welcome too of course)

one thing I noticed:
V(x,y,z) > V(y,x,z)
40y+16x+280yz+112xz > 40x+16y+280xz+112yz
24y+168yz > 24x+168xz
y(24+168z) > x(24+168z)
y>x
in words: its best to have D>=W, because the volume decreases by swapping them if its not the case
analogously: its best to have W>=H
such that we only need to search values for which:
D>=W>=H
 
Last edited:
DaTeL said:
Heyo, little challenge I have for you all to solve together :) (not my challenge, but mine to solve :P)

To transport palmtops, they're mass-packed into boxes without their retail packing. These palmtops are of size 2x8x12 cm (dxwxh). In the larger box, the palmtops are all aligned in the same direction. Inbetween the palmtops and between a palmtop and the 'wall' needs to be 2cm of polystyrene foam in all directions. We're trying to find the best size for the box given an amount N of palmtops. The 'best' size is the one that has the least volume.

mathematically, we're trying to minimize
V(D,W,H) = (2+4D) * (2+10W) * (2+14H) = 8 + 16D + 40W + 28H + 80DW + 112DH + 280WH + 560DWH
with D,W,H being integer values
such that D*W*H >= N and D>=1 and W>=1 and H>=1

example:
given: N = 10
best size = V(5,2,1) = 22*22*16 = 7744 cm^2

ok, so we're trying to make an algorithm that efficiently finds the best values (worst way is trying all combinations of W,H,D in the range [1,N] :P)

approach I had in mind was starting out with V(D,W,H)=V(N,1,1) and then raising W and H while lowering D.... but which one to raise and when to stop?

any help appreciated (other approaches welcome too of course)

one thing I noticed:
V(x,y,z) > V(y,x,z)
40y+16x+280yz+112xz > 40x+16y+280xz+112yz
24y+168yz > 24x+168xz
y(24+168z) > x(24+168z)
y>x
in words: its best to have D>=W, because the volume decreases by swapping them if its not the case
Click to expand...

Just ring DHL, smartarse.
 
Bart said:
i rly miss the time where chit&chat posts were nonsense spam and mindless flames. :\
Click to expand...

ok here's a special reply just for u.... very ontopic! :P
L01-sense.jpg


dont suppose this thread is gonna catch on then? where should i've posted it? :rolleyes:
 
Tbh that picture would make less sense if he were pouring the water into a can of tuna fish... or pouring the tuna fish into a water thingy
 
ok here's a semi-decent solution
want better ones though! :)

note: fixed a typo

Code: 
// Pseudo-code

initialize championVolume, championD, championB, championH

Loop h = 1 to n^(1/3) // round down    
    Loop b = h to (n/h)^(1/2) // round down
        d = n / (h*b) // round up

        if (volume(d,b,h) < championVolume)
            championVolume = championVolume
            championD = d
            championB = b
            championH = h
    end
end

return results
// end pseudo-code
 
Last edited:
Datel, are you sure your formulation is correct?

I've not got time to work it out myself, but it doesn't look right somehow. Have you taken into account you'd have n+1 packaging panels in any direction (where there are n boxes stacked in that direction).. also you'd have gaps where the packing overlaps.. maybe it is right :S
 
DaTeL said:
ok here's a semi-decent solution
want better ones though! :)

Code: 
// Pseudo-code

initialize championVolume, championD, championB, championH

Loop h = 1 to n^(1/3) // round down    
    Loop b = d to (n/h)^(1/2) // round down
        x = n / (h*b) // round up

        if (volume(d,b,h) < championVolume)
            championVolume = championVolume
            championD = d
            championB = b
            championH = h
    end
end

return results
// end pseudo-code
Click to expand...
summin missing:
on error resume next


:sofa:
 
eheh fixed some typos in the pseudo

uZi said:
Datel, are you sure your formulation is correct?

I've not got time to work it out myself, but it doesn't look right somehow. Have you taken into account you'd have n+1 packaging panels in any direction (where there are n boxes stacked in that direction).. also you'd have gaps where the packing overlaps.. maybe it is right :S
Click to expand...

ye the n+1 story is taken into account in the volume-calculation and the equation in post 1:
these imaginairy palmtops are 12cm in height, that means if you have an amount of H palmtops in that direction/dimension, u'd have a total size of 2+(12+2)*H = 2+14H in that direction
(2+4D) * (2+10W) * (2+14H)

not sure what u mean by the gaps?

Bart said:
summin missing:
on error resume next
Click to expand...
it doesnt make errors ;)

seas_ said:
sounds interesting but cba this is chit chat here!
Click to expand...

so where do i post it next time? :)
 
By gaps, I mean between the packaging above/below where the other packaging is put in.. although I think your (2 + (2+2)*D) etc account for it.

One alogorithm may be to start with all in a line (such that you get the shortest edge used in that line, so.. the 2's), then half the number and bring them side by side so that the length due to the 8s is then multiplied too.. this should bring the volume down.. could then try stacking.

Guess that would be a bit like the bisection rule, but in 3 dimensions. I would think about it more, but I got stuff to do :)
 
You must log in or register to reply here.
Top Bottom
Back