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

jimmykiang
This test is broken right out of the box… — FAIL: TestAgent (7.82s) agent_test.go:77: Error Trace: agent_test.go:77 agent_test.go:...
New
New
jeffmcompsci
Title: Design and Build Great Web APIs - typo “https://company-atk.herokuapp.com/2258ie4t68jv” (page 19, third bullet in URL list) Typo:...
New
Alexandr
Hi everyone! There is an error on the page 71 in the book “Programming machine learning from coding to depp learning” P. Perrotta. You c...
New
mikecargal
Title: Hands-On Rust (Chap 8 (Adding a Heads Up Display) It looks like ​.with_simple_console_no_bg​(SCREEN_WIDTH*2, SCREEN_HEIGHT*2...
New
HarryDeveloper
Hi @venkats, It has been mentioned in the description of ‘Supervisory Job’ title that 2 things as mentioned below result in the same eff...
New
alanq
This isn’t directly about the book contents so maybe not the right forum…but in some of the code apps (e.g. turbo/06) it sends a TURBO_ST...
New
gilesdotcodes
In case this helps anyone, I’ve had issues setting up the rails source code. Here were the solutions: In Gemfile, change gem 'rails' t...
New
brunogirin
When running tox for the first time, I got the following error: ERROR: InterpreterNotFound: python3.10 I realised that I was running ...
New
New

Other popular topics Top

Devtalk
Hello Devtalk World! Please let us know a little about who you are and where you’re from :nerd_face:
New
AstonJ
poll poll Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
New
PragmaticBookshelf
Create efficient, elegant software tests in pytest, Python's most powerful testing framework. Brian Okken @brianokken Edited by Kat...
New
Maartz
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
New
AstonJ
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New
First poster: bot
zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig. General-purpose programming language and toolchain for maintaini...
New
PragmaticBookshelf
Build modern server-driven web applications using htmx. Whatever programming language you use, you’ll write less (and cleaner) code. ...
New
AstonJ
This is cool! DEEPSEEK-V3 ON M4 MAC: BLAZING FAST INFERENCE ON APPLE SILICON We just witnessed something incredible: the largest open-s...
New
pragdave
Build robust LLM-powered apps, chatbots, and agents while mastering AI engineering principles that will help you outlast the tools and th...
New
xiji2646-netizen
Woke up to this today: Claude Code’s complete source code exposed via npm source map. Not a snippet. All 512,000 lines. 1,900 TypeScript ...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal ❯

Sub Categories: