# Functional Programming in Java, Second Edition: p 148 "An optimization problem" & "Plain-Vanilla Recursion" problems **URL:** \ **Category:** PragProg Customers\ **Tags:** book-functional-programming-in-java-second-edition, errata\ **Created:** [26 April 2023 12:58 UTC](https://forum.devtalk.com/t/functional-programming-in-java-second-edition-p-148-an-optimization-problem-plain-vanilla-recursion-problems/106571 "2023-04-26T12:58:59Z")\ **Posts on this page:** 2\ **Page:** 1
**Author:** ![dtonhofer](https://forum.devtalk.com/user_avatar/forum.devtalk.com/dtonhofer/32/3389_2.png) [@dtonhofer](https://forum.devtalk.com/u/dtonhofer)\ **Post date:** [26 April 2023 12:58 UTC](https://forum.devtalk.com/t/functional-programming-in-java-second-edition-p-148-an-optimization-problem-plain-vanilla-recursion-problems/106571/1 "2023-04-26T12:58:59Z")
On page 148, “An optimization problem” we read: ```auto 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 🤔 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: ```txt ≣|≣|≣|≣|≣|≣ ``` 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](https://oeis.org/A000041)] - 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: ```txt Number of ways of cutting for width = 6: 11 ≣≣≣≣≣≣ ≣|≣≣≣≣≣ ≣≣|≣≣≣≣ ≣≣≣|≣≣≣ ≣|≣|≣≣≣≣ ≣|≣≣|≣≣≣ ≣≣|≣≣|≣≣ ≣|≣|≣|≣≣≣ ≣|≣|≣≣|≣≣ ≣|≣|≣|≣|≣≣ ≣|≣|≣|≣|≣|≣ ``` Only increasing slowly: ```txt |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”) ```auto 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 { public List 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 csSetForSmallerWidth, final int width, final int firstCutWidth, final Set 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 generateAllCutsSchedulesForGivenNumCutsAndWidth(final int numCuts, final int width, final int minCutWidth) { assert numCuts >= 0; assert width > 0; assert minCutWidth > 0; SortedSet 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 csSetForSmallerWidth = Collections.unmodifiableSortedSet( generateAllCutsSchedulesForGivenNumCutsAndWidth( numCuts - 1, width - firstCutWidth, firstCutWidth )); extendToFullWidthAndCollect(csSetForSmallerWidth, width, firstCutWidth, res); }); } return res; } private static void verifyAll(final Set csSet, int width, final Set mustNotContain) { csSet.stream().forEach(cs -> { assert cs.verify(); assert cs.totalWidth() == width; assert !mustNotContain.contains(cs); }); } private static SortedSet tryingAllCutsForWidth(final int width) { final int minNumCuts = 0; final int maxNumCuts = width - 1; SortedSet res = new TreeSet<>(); IntStream.rangeClosed(minNumCuts, maxNumCuts).forEach(numCuts -> { Set 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 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))); } }); } } ``` ---
**Author:** ![venkats](https://forum.devtalk.com/user_avatar/forum.devtalk.com/venkats/32/508_2.png) [@venkats](https://forum.devtalk.com/u/venkats)\ **Post date:** [31 May 2023 20:03 UTC](https://forum.devtalk.com/t/functional-programming-in-java-second-edition-p-148-an-optimization-problem-plain-vanilla-recursion-problems/106571/2 "2023-05-31T20:03:25Z")
We can assume the given values are profit instead of revenue. The exponential time complexity also comes from the worst case scenario.