Re: cutting sticks problem

[James Dow Allen]

On May 7, 11:24 pm, sophia <sophia.ag...@g mail.comwrote:

The cutting sticks problem---given a stick of length L and a set of
points where it has to be cut. If the cost of making a cut is equal to
the length of the stick, what is the best algorithm to find the
optimal sequence of cuts(giving minimum cost)

Contrary to a suggestion in this thread,
the straightforward solution to this puzzle
is not of exponential complexity, but rather N^3/3.
Yes, I know O(N^3) = O(N^3/3) but I show the constant
divisor to emphasize that the iterative structure is
related to the volume of a pyramid.

I'm enclosing my source code (and cross-posting to
comp.lang.c) for critique. The program is *not*
thoroughly tested; I estimate it still has 1.84 bugs.
(Certain peculiar code layout details are to ensure
short lines for Usenet.)

/* begin bestcutter.c */
#include <stdlib.h>
#include <stdio.h>

#define MAXPIECE 100

/* Sol[a][b] describes substick [a ... a+b+1] */
struct {
double cost, leng;
int cutpt;
} Sol[MAXPIECE-1][MAXPIECE];

int bestcut(int xbeg, int xend)
{
int x, bstc;
double xcost, cheapest = 99999999;

for (x = xbeg + 1; x < xend; x++) {
xcost =
Sol[xbeg][x - xbeg - 1].cost
+ Sol[x][xend - x - 1].cost;
if (xcost < cheapest)
cheapest = xcost, bstc = x;
}
return bstc;
}

double mkcuts(int xbeg, int ncut)
{
int cutpt;
double tcost;

if (ncut < 1)
return 0;
cutpt = Sol[xbeg][ncut].cutpt;
tcost = Sol[xbeg][ncut].leng;
printf("Making cut at mark %d cost = %f\n",
cutpt, tcost);
return tcost
+ mkcuts(xbeg, cutpt - xbeg - 1)
+ mkcuts(cutpt, xbeg + ncut - cutpt);
}

int main(int argc, char **argv)
{
int ncut, ix1, bstc;

if (MAXPIECE + 1 < argc || argc < 2) {
printf("Usage: cutstick #L1 #L2 ... #LN\n");
printf(" where #Lk is the distance from k-1'th");
printf(" mark to k'th mark.\n (0'th and N'th");
printf(" marks are stick ends.) N <= %d.\n",
MAXPIECE);
return EXIT_FAILURE;
}
for (ix1 = 0; ix1 < argc - 1; ix1++)
Sol[ix1][0].leng = atof(argv[ix1 + 1]);
for (ncut = 1; ncut < argc - 1; ncut++)
for (ix1 = 0; ix1 < argc - ncut + 1; ix1++)
if (ncut == 1) {
Sol[ix1][ncut].cutpt = ix1 + 1;
Sol[ix1][ncut].cost =
Sol[ix1][ncut].leng =
Sol[ix1][0].leng
+ Sol[ix1 + 1][0].leng;
} else {
Sol[ix1][ncut].leng =
Sol[ix1][0].leng
+ Sol[ix1 + 1][ncut - 1].leng;
Sol[ix1][ncut].cutpt =
bstc = bestcut(ix1, ix1 + ncut + 1);
Sol[ix1][ncut].cost =
Sol[ix1][ncut].leng
+ Sol[ix1][bstc - ix1 - 1].cost
+ Sol[bstc][ncut - bstc + ix1].cost;
}
printf("Total cost = %f\n", mkcuts(0, argc - 2));
return EXIT_SUCCESS;
}
/* end bestcutter.c */
/* Sample execution:
* % bestcutter 2 3 1 5
* Making cut at mark 3 cost = 11.000000
* Making cut at mark 1 cost = 6.000000
* Making cut at mark 2 cost = 4.000000
* Total cost = 21.000000
*/

James Dow Allen

[rossum]

Re: cutting sticks problem

On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
<jdallen2000@ya hoo.comwrote:

>On May 7, 11:24 pm, sophia <sophia.ag...@g mail.comwrote:

>The cutting sticks problem---given a stick of length L and a set of
>points where it has to be cut. If the cost of making a cut is equal to
>the length of the stick, what is the best algorithm to find the
>optimal sequence of cuts(giving minimum cost)

>
>Contrary to a suggestion in this thread,
>the straightforward solution to this puzzle
>is not of exponential complexity, but rather N^3/3.
>Yes, I know O(N^3) = O(N^3/3) but I show the constant
>divisor to emphasize that the iterative structure is
>related to the volume of a pyramid.
>
>I'm enclosing my source code (and cross-posting to
>comp.lang.c) for critique. The program is *not*
>thoroughly tested; I estimate it still has 1.84 bugs.
>(Certain peculiar code layout details are to ensure
>short lines for Usenet.)
>
>/* begin bestcutter.c */

[snip code]

>
>James Dow Allen

I think that you could use a better algorithm. You are repeatedly
calculating the cost of the same sticks as part of your subproblems.
If there is a stick with marks at a, b, c, ... x, y, z then if you
make the first cut as a and the second cut at z you are left with a
stick of length z-a with cuts at b, c, ... x, y. If you make the
first cut at z and the second cut at a then you will have exactly the
same subproblem to solve. Saving the result and retrieving it would
be much faster than re-solving a problem you had already solved. This
needs more memory than the simple algorithm of course.

It would probably not be worthwhile storing intermediate results for
0, 1 or 2 cuts since there is no choice possible for 0 or 1 cuts and
there is an obvious algorithm for 2 cuts (cut off the longer
end-piece). I am not sure if there is an easy algorithm for three
cuts, not having thought about it at any length.

rossum

[James Dow Allen]

Re: cutting sticks problem

On May 11, 3:49 pm, rossum <rossu...@coldm ail.comwrote:

On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
<jdallen2...@ya hoo.comwrote:

the straightforward solution to this puzzle
is not of exponential complexity, but rather N^3/3.

>

I'm enclosing my source code (and cross-posting to
comp.lang.c) for critique.

I think that you could use a better algorithm.  You are repeatedly
calculating the cost of the same sticks as part of your subproblems.

No. Reread the source to see that the code calculates and saves the
intermediate results exactly as you describe. It is the caller of
bestcut()
rather than bestcut() itself that saves these results -- is that
where your confusion lies?

My algorithm is O(N^3). Are your comments intended to suggest
existence of a less complex algorithm?

James

[rossum]

Re: cutting sticks problem

On Sun, 11 May 2008 02:51:38 -0700 (PDT), James Dow Allen
<jdallen2000@ya hoo.comwrote:

>On May 11, 3:49 pm, rossum <rossu...@coldm ail.comwrote:

>On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
><jdallen2...@y ahoo.comwrote:

>the straightforward solution to this puzzle
>is not of exponential complexity, but rather N^3/3.

>>

>I'm enclosing my source code (and cross-posting to
>comp.lang.c) for critique.

>

>I think that you could use a better algorithm.  You are repeatedly
>calculating the cost of the same sticks as part of your subproblems.

>
>No. Reread the source to see that the code calculates and saves the
>intermediate results exactly as you describe.

It does indeed, my mistake. Thankyou for the correction.

>It is the caller of
>bestcut()
>rather than bestcut() itself that saves these results -- is that
>where your confusion lies?

Probably because I am more used to Java rather than C, and your
solution is expressed in procedural rather than OO terms.

>
>My algorithm is O(N^3). Are your comments intended to suggest
>existence of a less complex algorithm?

No. Since I thought you were recalculating intermediate results I
thought there was an obvious speed improvement that wasn't actually
there.

Apologies for my mistake.

rossum

>
>James

[James Dow Allen]

Re: cutting sticks problem

On May 11, 6:44 pm, rossum <rossu...@coldm ail.comwrote:

On Sun, 11 May 2008 02:51:38 -0700 (PDT), James Dow Allen wrote
>

No.  Reread the source to see that the code calculates and saves the
intermediate results exactly as you describe.

>
It does indeed, my mistake.  Thankyou for the correction.

Thank *you* for bringing closure to this subthread.
Everyone can (and does) make mistakes. *Acknowledging*
a mistake, especially in these newsgroups, is as rare
as spotting a beautiful butterfly on a stormy day.

Apologies for my mistake.

I think mine was the bigger mistake. A few well chosen
comments in the source would have prevented any
confusion.

James

[Greg Herlihy]

Re: cutting sticks problem

On May 11, 2:51 am, James Dow Allen <jdallen2...@ya hoo.comwrote:

>
My algorithm is O(N^3).  Are your comments intended to suggest
existence of a less complex algorithm?

I'm unclear why the program has a complexity of N^3 instead of N!
(which is the number of ways in which the stick can be cut.)

Greg

[rossum]

Re: cutting sticks problem

On Sun, 11 May 2008 23:27:41 -0700 (PDT), Greg Herlihy
<greghe@mac.com wrote:

>On May 11, 2:51 am, James Dow Allen <jdallen2...@ya hoo.comwrote:

>>
>My algorithm is O(N^3).  Are your comments intended to suggest
>existence of a less complex algorithm?

>
>I'm unclear why the program has a complexity of N^3 instead of N!
>(which is the number of ways in which the stick can be cut.)
>
>Greg

I am sure James has a more detailed answer, but basically James'
algorithm saves intermediate results so that duplicates among your N!
possibilities are saved and not recalculated. For example on a stick
with cuts at a, b, c, ... x, y, z there will be at some point the need
to calculate the best way to cut the substick f, g, h, i , j. Once
that substick has been calculated for the first time, if the result is
stored then that result can be retrieved in constant time (array
access in James' program) which reduces the run time of the algorithm
greatly. The 5 cut substick is encountered 21! times, only one of
which needs to be calculated.

rossum