// Beaver Elevator Challenge by Oma Falk // completed universal solution 17/Nov/2019 import java.util.List; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; /* Just a beaver. How complex could it be? */ class Beaver implements Comparable { // choice of names in constant array static final String[] names = new String[] {"Andy", "Barbie", "Charlie", "Darko", "Eaton", "Francis", "Gertrud", "Hugo", "Ivanhoe", "Judy", "Karl", "Louis", "Mike", "Neo", "Odette", "Priscilla", "Rudy", "Sergey", "Toby", "Ulrike", "Victor", "Wulfgar", "Zeta"}; // instance variables for single beaver private int weight; private String name; /* create one Beaver with random name */ public Beaver(int weight) { this.weight = weight; this.name = names[(int) (Math.random() * names.length)]; } /* printable form for easy output */ public String toString() { return String.format("%2d kg | %s", weight, name); } /* compare beavers by their weight, so we can sort them easily */ @Override public int compareTo(Beaver other) { return this.weight - other.getWeight(); } /* weight getter, as weight is private */ public int getWeight() { return this.weight; } } /* One elevator can contain a list of beavers */ class Elevator { private int capacity; private int filledWeight; private List refugees; /* create an empty elevator */ public Elevator(int capacity) { this.capacity = capacity; this.refugees = new ArrayList(); } /* load one beaver */ public void rescue(Beaver beaver) { refugees.add(beaver); this.filledWeight += beaver.getWeight(); } /* how many are on the elevator */ public int getSavedCount() { return this.refugees.size(); } /* total weight of saved beavers */ public int getFilledWeight() { return this.filledWeight; } /* check if elevator has specific beaver */ public boolean isOnBoard(Beaver beaver) { return this.refugees.contains(beaver); } /* show the contents */ public String toString() { // sort before printing Collections.sort(this.refugees); StringBuilder sb = new StringBuilder(); for (Beaver beaver: this.refugees) { sb.append(beaver); sb.append("\n"); } return sb.toString(); } } /* THE MAIN PROGRAM */ public class BeaverRescue { Beaver[] beavers; int sumWeight; int capacity; List candidates; Elevator left, right; // tricky way to define an array of lists... the compiler doesn't really like it // List[] lifts = (List[]) new ArrayList[2]; /* make random weights from headcount */ static int[] genRandomWeights(int count) { int[] randomWeights = new int[count]; for (int i = 0; i < count; i++) { randomWeights[i] = (int) (2 + Math.random() * 22); } return randomWeights; } /* make random capacity from weights */ static int genRandomCapacity(int[] weights) { int totalWeight = 0; for (int weight : weights) { totalWeight += weight; } return (int) (totalWeight * (0.3 + Math.random() * 0.15)); } /* random weights, only headcount given */ public BeaverRescue(int headcount) { // this() calls another constructor of the same class, // it must be the first statement here, // so the only way to pass correct arguments // is through a static method call this(genRandomWeights(headcount)); } /* if we have only the weights, we calculate a random capacity and call main constructor */ public BeaverRescue(int[] weights) { this(weights, genRandomCapacity(weights)); } /* the default constructor */ public BeaverRescue(int[] weights, int capacity) { this.capacity = capacity; beavers = new Beaver[weights.length]; for (int i = 0; i < weights.length; i++) { beavers[i] = new Beaver(weights[i]); this.sumWeight += weights[i]; } Arrays.sort(beavers); // in case the weights were not sorted showLineup(); selectRescuedBeavers(); showResult(); } /* print all starting conditions */ void showLineup() { System.out.printf("Beavers (%d):%n", beavers.length); for (Beaver b: beavers) { System.out.println(b); } System.out.printf("Total weight: %d kg%n", sumWeight); System.out.printf("Each elevator capacity: %d kg%n", capacity); } void selectRescuedBeavers() { // Beavers have been sorted by weight, // now the candidates are chosen in order of weight, // as long as they can possibly fit both elevators. // That ensures the most beavers saved candidates = new ArrayList(); int selectedWeight = 0; for (Beaver b : beavers) { if (selectedWeight + b.getWeight() > capacity * 2) break; candidates.add(b); selectedWeight += b.getWeight(); } System.out.printf("%s candidates' weight: %d kg%n", candidates.size(), selectedWeight); // initialize the elevators left = new Elevator(this.capacity); right = new Elevator(this.capacity); // Subset Sum problem: determine which // beavers fill the left elevator. // We try to fill it completely, but // if not possible, decrease the fill target int targetCapacity = capacity; while (!fillElevator(candidates.size()-1, targetCapacity)) { // keep trying until filled targetCapacity--; if (targetCapacity < selectedWeight / 2.0) { System.out.println("Not enough room for the fattest one!"); Beaver unlucky = candidates.get(candidates.size() - 1); selectedWeight -= unlucky.getWeight(); candidates.remove(unlucky); targetCapacity = capacity; } } // put all the non-rescued candidates // in the right elevator for (Beaver b: candidates) { if (!left.isOnBoard(b)) right.rescue(b); } } /* Recursive function to decide if a specific beaver should be selected or not, goal is to precisely fill LEFT elevator */ boolean fillElevator(int beaverIndex, int freeCapacity) { // iterate through the candidates, // starting with the last one. // First we deal with the exit conditions. if (freeCapacity == 0) { // success, we precisely filled the elevator: // wrap up the recursion tree by passing true return true; } else if (beaverIndex < 0) { // there are no more beavers left, this branch fails return false; } Beaver maybe = candidates.get(beaverIndex); int weight = maybe.getWeight(); if (weight > freeCapacity) { // this candidate is too fat return false; } else if (fillElevator(beaverIndex-1, freeCapacity-weight)) { // trying to include this beaver, // recurse to next index with reduced capacity. // If solution is reached, then we add beaver to left elevator. left.rescue(maybe); return true; } else if (fillElevator(beaverIndex-1, freeCapacity)) { // trying to exclude this beaver and move on to the next. // if successful, then we just wrap up return true; } // no conclusion, backtracking return false; } void showResult() { System.out.printf("Left Elevator (%d beavers, %d kg):%n%s", left.getSavedCount(), left.getFilledWeight(), left); System.out.printf("Right Elevator (%d beavers, %d kg):%n%s%n", right.getSavedCount(), right.getFilledWeight(), right); } /* Two predefined cases and one random */ public static void main(String[] args) { new BeaverRescue(new int[] {8, 5, 9, 7}, 10); new BeaverRescue(new int[] {2, 3, 5, 8, 9, 9, 12, 12, 22}, 30); new BeaverRescue((int) (5 + Math.random()*10)); } }

BeaverSort