dtonhofer

dtonhofer

Functional Programming in Java, Second Edition: p 148 "An optimization problem" & "Plain-Vanilla Recursion" problems

On page 148, “An optimization problem” we read:

We’ll employ a solution for a company that buys rods at wholesale and sells them at retail. They figured that by cutting the rods into different sizes, they could maximize profits. The price that the company can charge for different lengths of rod changes often, so the company wants us to write a program to reveal what the maximum profit would be for a given size of rod. 

The above is not computing the profit, but computing the revenue. The profit is revenue - expenses, but we don’t know the expenses, it might include manpower costs, machine costs etc.

The problem would also be more interesting if a rod of length 1 could only be sold at price 0 (i.e. it is wastage), at price 2 it’s too easy.

More seriously, on page 149, “Plain-Vanilla Recursion”, we read:

Continuing with this approach, we find that the maximum profit [revenue] for an arbitrary length n is the maximum of the profits [revenues] from each of the possible 2^(n-1) cuts length. That is, max(no cut, cut(1, n - 1), cut(2, n - 2), …), for a given length n.

It don’t understand the max() notation here, there should probably at least be revenue(.) of a cut schedule in there :thinking:

In any case, the 2^(n-1) is imprecise Not considering symmetries, each cut point at marginal width 1 of which there are n-1, for example for width = 6:

≣|≣|≣|≣|≣|≣

can be switched on or off, giving us indeed 2^(n-1) “cut schedules.”

But considering all symmetries (to collapse similar “cut schedules”, consider only “cut schedules” where the width of a cut is monotonically (but not strictly) increasing from left to right), the number of possible “cut schedules” for width = n is then given by

[A000041 - OEIS] - the number of partitions of n (the partition numbers)

(I didn’t find this by myself, I first wrote the program to list the schedules, then duckduckgoed the sequence)

For example for width = 6, there are only 11 distinct ways to cut:

Number of ways of cutting for width = 6: 11
≣≣≣≣≣≣
≣|≣≣≣≣≣
≣≣|≣≣≣≣
≣≣≣|≣≣≣
≣|≣|≣≣≣≣
≣|≣≣|≣≣≣
≣≣|≣≣|≣≣
≣|≣|≣|≣≣≣
≣|≣|≣≣|≣≣
≣|≣|≣|≣|≣≣
≣|≣|≣|≣|≣|≣

Only increasing slowly:

|Width|Schedules|2^(n-1)|
|---|---|---|
|1|1|1|
|2|2|2|
|3|3|4|
|4|5|8|
|5|7|16|
|6|11|32|
|7|15|64|
|8|22|128|
|9|30|256|
|10|42|512|
|11|56|1024|
|12|77|2048|
|13|101|4096|
|14|135|8192|
|15|176|16384|
|16|231|32768|
|17|297|65536|
|18|385|131072|
|19|490|262144|
|20|627|524288|

Code to compute the above (unabashedly recursive, not memoizing/caching, slows down quickly with larger n. The SortedSet could be replaced by an array and “insertion sorting” if one wants “efficiency”)

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.IntStream;

import static java.util.stream.Collectors.joining;

class CutSchedule implements Comparable<CutSchedule> {

    public List<Integer> increasingWidths = new ArrayList<>();

    public boolean verify() {
        if (increasingWidths.isEmpty()) {
            return false;
        }
        if (increasingWidths.get(0) <= 0) {
            return false;
        }
        for (int i = 1; i < increasingWidths.size(); i++) {
            if (increasingWidths.get(i - 1) > increasingWidths.get(i)) {
                return false;
            }
        }
        return true;
    }

    private static String toRodString(int width, char ch) {
        StringBuilder buf = new StringBuilder();
        IntStream.range(0, width).forEach(i -> buf.append(ch));
        return buf.toString();
    }

    public String toString(boolean numeric) {
        if (numeric) {
            return increasingWidths.stream().map(width -> Integer.toString(width)).collect(joining(","));
        } else {
            return increasingWidths.stream().map(width -> toRodString(width, '≣')).collect(joining("|"));
        }
    }

    public String toString() {
        return toString(false);
    }

    public int totalWidth() {
        return increasingWidths.stream().mapToInt(width -> width).sum();
    }

    public int cutCount() {
        return increasingWidths.size() - 1;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || !(o instanceof CutSchedule)) {
            return false;
        }
        return this.compareTo((CutSchedule) o) == 0;
    }

    @Override
    public int compareTo(CutSchedule o) {
        assert o != null;
        int widthDelta = this.totalWidth() - o.totalWidth();
        if (widthDelta != 0) {
            // if total width is smaller, the CutSchedule is "smaller"
            return widthDelta;
        }
        int cutCountDelta = this.cutCount() - o.cutCount();
        if (cutCountDelta != 0) {
            // if cut count is smaller, the CutSchedule is "smaller"
            return cutCountDelta;
        }
        for (int i = 0; i < cutCount(); i++) {
            int deltaCutWidth = this.increasingWidths.get(i) - o.increasingWidths.get(i);
            if (deltaCutWidth != 0) {
                // the first having a smaller cut at position i is "smaller"
                return deltaCutWidth;
            }
        }
        return 0;
    }
}

public class RodCuttingOptimization {

    private static void extendToFullWidthAndCollect(final SortedSet<CutSchedule> csSetForSmallerWidth, final int width, final int firstCutWidth, final Set<CutSchedule> res) {
        for (CutSchedule subCs : csSetForSmallerWidth) {
            assert subCs.verify();
            assert subCs.totalWidth() == width - firstCutWidth;
            CutSchedule cs = new CutSchedule();
            cs.increasingWidths.add(firstCutWidth);
            cs.increasingWidths.addAll(subCs.increasingWidths);
            res.add(cs);
        }
    }

    private static SortedSet<CutSchedule> generateAllCutsSchedulesForGivenNumCutsAndWidth(final int numCuts, final int width, final int minCutWidth) {
        assert numCuts >= 0;
        assert width > 0;
        assert minCutWidth > 0;
        SortedSet<CutSchedule> res = new TreeSet<>();
        if (numCuts == 0) {
            CutSchedule cs = new CutSchedule();
            cs.increasingWidths.add(width);
            res.add(cs);
        } else {
            // Make the first cut at increasingly larger positions. It must be the smallest cut made!
            IntStream.rangeClosed(minCutWidth, width / 2).forEach(firstCutWidth -> {
                SortedSet<CutSchedule> csSetForSmallerWidth =
                        Collections.unmodifiableSortedSet(
                                generateAllCutsSchedulesForGivenNumCutsAndWidth(
                                        numCuts - 1,
                                        width - firstCutWidth,
                                        firstCutWidth
                                ));
                extendToFullWidthAndCollect(csSetForSmallerWidth, width, firstCutWidth, res);
            });
        }
        return res;
    }

    private static void verifyAll(final Set<CutSchedule> csSet, int width, final Set<CutSchedule> mustNotContain) {
        csSet.stream().forEach(cs -> {
            assert cs.verify();
            assert cs.totalWidth() == width;
            assert !mustNotContain.contains(cs);
        });
    }

    private static SortedSet<CutSchedule> tryingAllCutsForWidth(final int width) {
        final int minNumCuts = 0;
        final int maxNumCuts = width - 1;
        SortedSet<CutSchedule> res = new TreeSet<>();
        IntStream.rangeClosed(minNumCuts, maxNumCuts).forEach(numCuts -> {
            Set<CutSchedule> csSetForWidth = generateAllCutsSchedulesForGivenNumCutsAndWidth(numCuts, width, 1);
            verifyAll(csSetForWidth, width, res);
            res.addAll(csSetForWidth);
        });
        return res;
    }

    private final static boolean withPrintout = false;

    @Test
    public void loopOverWidths() {
        final int minWidth = 1;
        final int maxWidth = 100;
        IntStream.rangeClosed(minWidth, maxWidth).forEach(width -> {
            SortedSet<CutSchedule> all = tryingAllCutsForWidth(width);
            System.out.println("Number of ways of cutting for width = " + width + ": " + all.size());
            if (withPrintout) {
                all.stream().forEach(cs -> System.out.println(cs.toString(false)));
            }
        });
    }

}

First Post!

venkats

venkats

Author of Programming Kotlin, Rediscovering JavaScript (and 6 other titles)

We can assume the given values are profit instead of revenue. The exponential time complexity also comes from the worst case scenario.

Where Next?

Popular Pragmatic Bookshelf topics Top

jon
Some minor things in the paper edition that says “3 2020” on the title page verso, not mentioned in the book’s errata online: p. 186 But...
New
telemachus
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
New
jesse050717
Title: Web Development with Clojure, Third Edition, pg 116 Hi - I just started chapter 5 and I am stuck on page 116 while trying to star...
New
mikecargal
Title: Hands-on Rust: question about get_component (page 295) (feel free to respond. “You dug you’re own hole… good luck”) I have somet...
New
jeremyhuiskamp
Title: Web Development with Clojure, Third Edition, vB17.0 (p9) The create table guestbook syntax suggested doesn’t seem to be accepted ...
New
jgchristopher
“The ProductLive.Index template calls a helper function, live_component/3, that in turn calls on the modal component. ” Excerpt From: Br...
New
jskubick
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
New
dsmith42
Hey there, I’m enjoying this book and have learned a few things alredayd. However, in Chapter 4 I believe we are meant to see the “&gt;...
New
dachristenson
@mfazio23 Android Studio will not accept anything I do when trying to use the Transformations class, as described on pp. 140-141. Googl...
New
roadbike
From page 13: On Python 3.7, you can install the libraries with pip by running these commands inside a Python venv using Visual Studio ...
New

Other popular topics Top

Exadra37
I am thinking in building or buy a desktop computer for programing, both professionally and on my free time, and my choice of OS is Linux...
New
dasdom
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
brentjanderson
Bought the Moonlander mechanical keyboard. Cherry Brown MX switches. Arms and wrists have been hurting enough that it’s time I did someth...
New
Margaret
Hello content creators! Happy new year. What tech topics do you think will be the focus of 2021? My vote for one topic is ethics in tech...
New
PragmaticBookshelf
Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
New
gagan7995
API 4 Path: /user/following/ Method: GET Description: Returns the list of all names of people whom the user follows Response [ { ...
New
AstonJ
Biggest jackpot ever apparently! :upside_down_face: I don’t (usually) gamble/play the lottery, but working on a program to predict the...
New
PragmaticBookshelf
Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
New
hilfordjames
There appears to have been an update that has changed the terminology for what has previously been known as the Taskbar Overflow - this h...
New
PragmaticBookshelf
Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: