Stampcalculator - Given a set of stamps, what combinations are there to reach a certain amount?

Question

Background

My mother has a hobby of buying and reselling books via online trading sites. After a price is agreed on, the books have to be put into an envelope for mailing. On this envelope, stamps have to be applied to pay for postage (mailing fee). My mother buys stamps in bulk at various prices, varying from 75 to 90% of face value. As the postage prices change every year, new stamp combinations have to be calculated that will satisfy the postage fee with a minimum amount of hassle.

My mother is not all that good with calculations. And having to manually recalculate what stamp combinations are best to get to the postage required for a 250 - 500 gram package takes a lot of time. Therefore, she calculates a few options via trial and error - sometimes overshooting the postage amount by a few cents - and just uses those.

Some stamps are preferred to be used, whereas others aren't, due to the cost not always being the face value of a stamp. Asking my mother about the stamp prices individually would have taken too much time, so I just made a program that generates a list of options. It requires recompilation when you need to add different stamps or want to get to a different limit, but that's okay. The whole point of this was to not spend too much time on it (the goal is to save time!) - which is why I wrote it in the total time of 1 hour (from idea to solution).

Problem description

Given a target amount, a set of stamp denominations, and a maximum amount of usable stamps, print a list of stamp combinations that will get to the target amount.

Programmed in 1 hour. I have placed everything in one file to ensure that it can run in Ideone, so that she could theoretically make the changes herself, if needed.

How it works

Using a list of stamps, make partial combinations that are at or below the target amount. For each combination, make a new combinations via duplicating the current combination and adding a stamp with a value equal to or below the last added stamp. Combinations that go past the goal are discarded. Combinations that meet the goal are added to a solutions list.

After all this, the solutions list is printed. The resulting output can easily be sifted through by searching for solutions that focus on using a lot of a particular stamp.

Code

//VOOR GEBRUIK IN IDEONE, plaats '//' voor "package stampcalculator" - zo dus:
//package stampcalculator;

package stampcalculator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 *
 * @author Pim
 */
public class Main {

    private static final int GOAL = 292;//365;

    private static final int STAMP_LIMIT = 10;

    private static final int[] stamps = {73, 64, 44, 39, 34, 10, 5, 3, 2};

    static class StampCollection {

        private Deque<Integer> stamps;
        private int sum;

        public StampCollection() {
            stamps = new LinkedList<>();
        }

        public StampCollection(int stamp) {
            this();
            addStamp(stamp);
        }

        public StampCollection(StampCollection collection, int stamp) {
            stamps = new LinkedList<>(collection.getStamps());
            for (int s : stamps) {
                sum += s;
            }
            addStamp(stamp);
        }

        public Deque<Integer> getStamps() {
            return stamps;
        }

        public int getLastStampValue() {
            return stamps.peekLast();
        }

        public int getSum() {
            return sum;
        }

        public void addStamp(int stamp) {
            sum += stamp;
            stamps.add(stamp);
        }

        @Override
        public String toString() {
            List<String> strings = new ArrayList<>();

            int numberLookingFor = 0;
            int count = 0;
            for (int stamp : stamps) {
                if (stamp != numberLookingFor) {
                    if (numberLookingFor != 0) {
                        if (count == 1) {
                            strings.add("" + numberLookingFor);
                        } else {
                            strings.add(count + "*" + numberLookingFor);
                        }
                    }
                    count = 0;
                    numberLookingFor = stamp;
                }
                count++;
            }
            if (count == 1) {
                strings.add("" + numberLookingFor);
            } else {
                strings.add(count + "*" + numberLookingFor);
            }
            return strings.stream().collect(Collectors.joining(", "));
        }
    }



    private static List<StampCollection> solutions;

    private static List<StampCollection> inProgress;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        solutions = new ArrayList<>();
        inProgress = new ArrayList<>();

        System.out.println("Looking for stamps that will total " + GOAL + "...");
        System.out.println("Stamp limit: " + STAMP_LIMIT);
        String stampList = (Arrays.asList(stamps).stream().map(i -> Arrays.toString(i)).collect(Collectors.joining(", ")));
        System.out.println("Using stamps: " + stampList);

        for (int i = 0; i < stamps.length; i++) {
            inProgress.add(new StampCollection(stamps[i]));
        }

        while (!inProgress.isEmpty()) {
            List<StampCollection> nextWave = new ArrayList<>();
            for (StampCollection collection : inProgress) {
                if (collection.getSum() == GOAL) {
                    solutions.add(collection);
                    continue;
                }
                if (collection.getStamps().size() >= STAMP_LIMIT) {
                    continue;
                }
                for (int i = 0; i < stamps.length; i++) {
                    int stamp = stamps[i];
                    if (stamp > collection.getLastStampValue() || (collection.getSum() + stamp) > GOAL) {
                        continue;
                    }
                    StampCollection newOne = new StampCollection(collection, stamp);
                    if (newOne.getSum() == GOAL) {
                        solutions.add(newOne);
                    } else {
                        nextWave.add(newOne);
                    }
                }
            }
            inProgress = nextWave;
        }
        System.out.println("Found " + solutions.size() + " solutions");

        for (StampCollection solution : solutions) {
            if (solution.getSum() == GOAL) {
                System.out.println(solution);
            } else {
                System.out.println("WTF: " + solution);
            }
        }
    }

}

I am mainly looking for...

• Better algorithms
• Missed opportunities to replace a large part of the code with library functions

Answer 1

                if (collection.getSum() == GOAL) {
                    solutions.add(collection);
                    continue;
                }

and

                    if (newOne.getSum() == GOAL) {
                        solutions.add(newOne);
                    } else {

are redundant. The only time that the first one triggers is if you can meet the solution with a single stamp. So you could do without the second one and just always add to inProgress, or you can move the first one.

        for (int i = 0; i < stamps.length; i++) {
            inProgress.add(new StampCollection(stamps[i]));
        }

could be

        for (int stamp: stamps) {
            StampCollection collection = new StampCollection(stamp);
            if (stamp == GOAL) {
                solutions.add(collection);
            } else if (stamp < GOAL) {
                inProgress.add(collection);
            }
        }

Then you don't have to check for that on each iteration of the other loop.

I would prefer this form of for loop, since you only use i as an array index.

But you don't actually need to do that. Instead, you could replace that section with

        inProgress.add(new StampCollection());

and change getLastStampValue to

        public int getLastStampValue() {
            return stamps.isEmpty() ? Integer.MAX_VALUE : stamps.peekLast();
        }

So that it doesn't try to compare a null.

    private static List<StampCollection> solutions;

    private static List<StampCollection> inProgress;

These don't need to be class fields. They could just be local variables.

        System.out.println("Found " + solutions.size() + " solutions");

        for (StampCollection solution : solutions) {
            if (solution.getSum() == GOAL) {
                System.out.println(solution);
            } else {
                System.out.println("WTF: " + solution);
            }
        }

could be

        List<StampCollection> solutions = calculateSolutions(stamps, 292);

        System.out.println("Found " + solutions.size() + " solutions");
        for (StampCollection solution : solutions) {
            System.out.println(solution);
        }

This would move most of the logic out of main, and it reduces the code, as the else never happens.

    public static List<StampCollection> calculateSolutions(int[] stamps, int goal) {
        List<StampCollection> solutions = new ArrayList<>();
        List<StampCollection> inProgress = new ArrayList<>();

        inProgress.add(new StampCollection());

        while (!inProgress.isEmpty()) {
            List<StampCollection> nextWave = new ArrayList<>();
            for (StampCollection collection : inProgress) {
                if (collection.getStamps().size() >= STAMP_LIMIT) {
                    continue;
                }

                for (int stamp : stamps) {
                    if (stamp > collection.getLastStampValue() || (collection.getSum() + stamp) > goal) {
                        continue;
                    }

                    StampCollection newOne = new StampCollection(collection, stamp);
                    if (newOne.getSum() == goal) {
                        solutions.add(newOne);
                    } else {
                        nextWave.add(newOne);
                    }
                }
            }

            inProgress = nextWave;
        }

        return solutions;
    }

Now if you want, you could call this method from another class in the same package. And you could call the method multiple times with different goals.