Dandův houmwork

dynamic-prg.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Pair<First,Second> {
    First first;
    Second second;

    Pair(First f, Second s) {
        first = f;
        second = s;
    }

    First getFirst() { return first; }
    Second getSecond() { return second; }
}

interface Task<T extends Task<T,S,W>, S extends Solution<T,S,W>, W extends Comparable<W>> {
    Set<S> getPossibleSolutions();
    // TUHLE METODU JSEM PRIDAL
    // jinak to nevyresis - neni jak ukoncit rekurzi
    // Machine ma jen genericky typ W a ten nemuzes instancovat
    W getNullValue();
}

interface Solution<T extends Task<T,S,W>, S extends Solution<T,S,W>, W extends Comparable<W>> {
    W getWorth(Machine<T,S,W> m);
}

class Machine<T extends Task<T,S,W>, S extends Solution<T,S,W>, W extends Comparable<W>> {
    Map<T, Pair<S,W>> cache = new HashMap<T,Pair<S,W>>();

    Pair<S,W> solve(T task) {
        // if cached value - return it
        if (cache.containsKey(task)) {
            return cache.get(task);
        }

        // find the best solution
        Pair<S, W> bestSolution = null;
        for (S solution: task.getPossibleSolutions()) {
            W worth = solution.getWorth(this);
            if (bestSolution == null || worth.compareTo(bestSolution.getSecond()) > 0) {
                bestSolution = new Pair<S, W>(solution, worth);
            }
        }

        // task has no solution - end of recursion
        if (bestSolution == null) {
            bestSolution = new Pair<S, W>(null, task.getNullValue());
        }

        // store best solution in cache
        cache.put(task, bestSolution);
        return bestSolution;
    }
}

/* Ukazka pouziti predchoziho frameworku. */

class RodTask implements Task<RodTask,RodSolution,Integer> {
    final int length;
    final int[] table;
    final Set<RodSolution> sols = new HashSet<RodSolution>();

    RodTask(int length, int[] table) {
        this.length = length;
        this.table = table;
        // TOHLE JSEM ZMENIL (OPRAVIL)
        // jinak by to pristupovalo k neexistujicimu prvku a hazelo exception
        for (int i = 0; i < length; i++)
            sols.add(new RodSolution(i, length - i - 1, table));

    }
    public Set<RodSolution> getPossibleSolutions() {
        return sols;
    }
    public int hashCode() {
        int code = length;
        for (int i: table) code += 3 * i;
        return code;
    }
    public boolean equals(Object o) {
        if (! (o instanceof RodTask)) return false;
        RodTask other = (RodTask) o;
        if (length != other.length || table.length != other.table.length)
            return false;
        for (int i = 0; i < table.length; i++)
            if (table[i] != other.table[i]) return false;
        return true;
    }
    public Integer getNullValue() {
        return new Integer(0);
    }
}

class RodSolution implements Solution<RodTask,RodSolution,Integer> {
    final int first;
    final int rest;
    final int[] table;

    RodSolution(int first, int rest, int[] table) {
        this.first = first;
        this.rest = rest;
        this.table = table;
    }

    public Integer getWorth(Machine<RodTask,RodSolution,Integer> m) {
        return table[first] + m.solve(new RodTask(rest, table)).getSecond();
    }
}

class Test {
    public static void main(String[] args) {
        Machine<RodTask, RodSolution, Integer> m = new Machine<RodTask, RodSolution, Integer>();
        RodTask t = new RodTask(3, new int[] {3, 5, 7});
        System.out.println(m.solve(t).getSecond());
    }
}