Last active
December 25, 2015 16:08
-
-
Save jimmitt/7003069 to your computer and use it in GitHub Desktop.
Trapezoid Walkway problem from ACM competition qualification
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Created by James Trimble (on Twitter @jamestrimble) | |
| // View the original problem here, https://icpc-qual-13.contest.scrool.se/problems/walkway | |
| import java.util.LinkedList; | |
| public class trapezoidwalkway { | |
| public static Integer iterations = 0; | |
| public static Double memo[]; | |
| public static void main(String[] args) { | |
| Integer backPorch, gazebo; | |
| Integer stones[][]; | |
| int problem = 5; | |
| switch (problem) { | |
| case 0: | |
| backPorch = 120; | |
| gazebo = 240; | |
| stones = new Integer[][]{{120,350,60},{120,150,95},{240,300,60},{240,350,220},{150,300,100},{300,350,120}}; | |
| break; | |
| case 1: | |
| backPorch = 140; | |
| gazebo = 100; | |
| stones = new Integer[][]{{100,140,50},{100,140,80}}; | |
| break; | |
| case 2: | |
| backPorch = 140; | |
| gazebo = 100; | |
| stones = new Integer[][]{{240,50,50},{50,100,40},{240,140,80}}; | |
| break; | |
| case 3: | |
| backPorch = 140; | |
| gazebo = 100; | |
| stones = new Integer[][]{{240,50,50},{240,50,40},{50,100,40},{240,140,80}}; | |
| break; | |
| case 4: | |
| backPorch = 140; | |
| gazebo = 100; | |
| stones = new Integer[][]{{240,60,50},{60,70,10},{70,80,19},{80,50,19},{10,50,40},{10,20,20},{30,20,30},{30,40,40},{40,50,23},{50,100,40},{240,140,80}}; | |
| break; | |
| case 5: | |
| backPorch = 191; | |
| gazebo = 494; | |
| stones = new Integer[][]{{191,782,2},{782,337,3},{337,708,29},{708,888,6},{888,482,30},{482,788,22},{788,650,9},{650,205,10},{205,843,27},{843,631,45},{631,267,45},{267,618,25},{618,30,11},{30,644,44},{644,909,15},{909,360,41},{360,318,29},{318,958,1},{958,267,32},{267,989,50},{989,996,5},{996,300,33},{300,282,22},{282,397,25},{397,464,43},{464,724,45},{724,697,4},{697,401,22},{401,494,4},{494,325,49}}; | |
| break; | |
| default: | |
| backPorch = 150; | |
| gazebo = 150; | |
| stones = new Integer[][]{{150,250,100},{150,250,60}}; | |
| break; | |
| } | |
| memo = new Double[1000]; | |
| for (int i = 0; i < 1000; i++) { | |
| memo[i] = -1.0; | |
| } | |
| iterations = 0; | |
| try { | |
| //System.out.println("Naive = "+naive(backPorch,gazebo,stones.length-1,stones,0)+", "+iterations+" iterations"); | |
| } | |
| catch (StackOverflowError e) { | |
| System.out.println("Naive = Stackoverflow, >"+iterations+" iterations"); | |
| } | |
| iterations = 0; | |
| try { | |
| System.out.println("TopDown = "+memoize(backPorch,gazebo,stones.length-1,stones,0)+", "+iterations+" iterations"); | |
| } | |
| catch (StackOverflowError e) { | |
| System.out.println("TopDown = Stackoverflow, >"+iterations+" iterations"); | |
| } | |
| iterations = 0; | |
| try { | |
| System.out.println("BottomUp = "+bottomup(backPorch, gazebo, stones.length - 1, stones, 0)+", "+iterations+" iterations"); | |
| } | |
| catch (StackOverflowError e) { | |
| System.out.println("BottomUp = Stackoverflow, >"+iterations+" iterations"); | |
| } | |
| } | |
| public static Double cost(Integer a, Integer b, Integer h) { | |
| return .02*.5*h*(b+a); | |
| } | |
| public static Double naive(Integer backPorch, Integer gazebo, Integer stoneIndex, Integer stones[][], Integer length) { | |
| iterations++; | |
| /*if (stoneIndex >= 0) { | |
| System.out.println("naive("+backPorch+","+gazebo+","+ | |
| stoneIndex+"=["+ | |
| stones[stoneIndex][0]+","+ | |
| stones[stoneIndex][1]+","+ | |
| stones[stoneIndex][2]+"]"+ | |
| ",stones[][],"+length+")"); | |
| } | |
| else { | |
| System.out.println("naive("+backPorch+","+gazebo+","+stoneIndex+",stones[][],"+length+")"); | |
| }*/ | |
| Integer start = 0, stop = 1, height = 2; | |
| Integer currentStone[]; | |
| Double currentStoneCost; | |
| // If the starting and stopping sizes are the same or there are no stones available, return | |
| if (backPorch.compareTo(gazebo)==0) { | |
| return 0.0; | |
| } | |
| if (stoneIndex < 0 || length > stones.length) { | |
| return 99999999.0; | |
| } | |
| currentStone = stones[stoneIndex]; | |
| currentStoneCost = cost(currentStone[start], currentStone[stop], currentStone[height]); | |
| // If the current stone won't fit with our current beginning, try the next stone | |
| if (currentStone[start].compareTo(backPorch) != 0 && currentStone[stop].compareTo(backPorch) != 0) { | |
| return naive(backPorch, gazebo, stoneIndex-1, stones, length); | |
| } | |
| // Otherwise return the minimum of the cost of building the path with the current stone or without it | |
| else { | |
| Double costWithout = naive(backPorch, gazebo, stoneIndex-1, stones, length); // The cost for not using the stone | |
| Double costWith; | |
| if (currentStone[start].compareTo(backPorch)==0) { | |
| costWith = naive(currentStone[stop], gazebo, stones.length-1, stones, ++length); | |
| return Math.min( | |
| currentStoneCost+costWith, | |
| costWithout); | |
| } else { | |
| costWith = naive(currentStone[start], gazebo, stones.length-1, stones, ++length); | |
| return Math.min( | |
| currentStoneCost+costWith, | |
| costWithout); | |
| } | |
| } | |
| } | |
| public static Double topdown(Integer backPorch, Integer gazebo, Integer stoneIndex, Integer stones[][], Integer length) { | |
| /*if (stoneIndex >= 0) { | |
| System.out.println("topdown("+backPorch+","+gazebo+","+ | |
| stoneIndex+"=["+ | |
| stones[stoneIndex][0]+","+ | |
| stones[stoneIndex][1]+","+ | |
| stones[stoneIndex][2]+"]"+ | |
| ",stones[][],"+length+")"); | |
| } | |
| else { | |
| System.out.println("topdown("+backPorch+","+gazebo+","+stoneIndex+",stones[][],"+length+")"); | |
| }*/ | |
| Integer start = 0, stop = 1, height = 2; | |
| Integer currentStone[]; | |
| Double currentStoneCost; | |
| // If the starting and stopping sizes are the same or there are no stones available, return | |
| if (backPorch.compareTo(gazebo)==0) { | |
| return 0.0; | |
| } | |
| if (stoneIndex < 0 || length > stones.length) { | |
| return 99999999.0; | |
| } | |
| currentStone = stones[stoneIndex]; | |
| currentStoneCost = cost(currentStone[start], currentStone[stop], currentStone[height]); | |
| // If the current stone won't fit with our current beginning, try the next stone | |
| if (currentStone[start].compareTo(backPorch) != 0 && currentStone[stop].compareTo(backPorch) != 0) { | |
| return memoize(backPorch, gazebo, stoneIndex-1, stones, length); | |
| } | |
| // Otherwise return the minimum of the cost of building the path with the current stone or without it | |
| else { | |
| Double costWithout = memoize(backPorch, gazebo, stoneIndex-1, stones, length); // The cost for not using the stone | |
| Double costWith; | |
| if (currentStone[start].compareTo(backPorch)==0) { | |
| costWith = memoize(currentStone[stop], gazebo, stones.length-1, stones, ++length); | |
| return Math.min( | |
| currentStoneCost+costWith, | |
| costWithout); | |
| } else { | |
| costWith = memoize(currentStone[start], gazebo, stones.length-1, stones, ++length); | |
| return Math.min( | |
| currentStoneCost+costWith, | |
| costWithout); | |
| } | |
| } | |
| } | |
| public static Double memoize(Integer backPorch, Integer gazebo, Integer stoneIndex, Integer stones[][], Integer length) { | |
| iterations++; | |
| if (memo[backPorch] == -1.0) { | |
| memo[backPorch] = topdown(backPorch, gazebo, stoneIndex, stones, length); | |
| } | |
| return memo[backPorch]; | |
| } | |
| public static Double bottomup(Integer backPorch, Integer gazebo, Integer stoneIndex, Integer stones[][], Integer length) { | |
| /*if (stoneIndex >= 0) { | |
| System.out.println("topdown("+backPorch+","+gazebo+","+ | |
| stoneIndex+"=["+ | |
| stones[stoneIndex][0]+","+ | |
| stones[stoneIndex][1]+","+ | |
| stones[stoneIndex][2]+"]"+ | |
| ",stones[][],"+length+")"); | |
| } | |
| else { | |
| System.out.println("topdown("+backPorch+","+gazebo+","+stoneIndex+",stones[][],"+length+")"); | |
| }*/ | |
| Integer start = 0, stop = 1, height = 2; | |
| Integer currentStone[]; | |
| Double currentStoneCost; | |
| Double costs[] = new Double[1001]; | |
| LinkedList <Integer> needsUpdating = new LinkedList<Integer>(); | |
| Integer currentUpdate; | |
| Double tempCost; | |
| for (int i = 0; i < costs.length; i++) { | |
| costs[i] = 9999999.0; | |
| } | |
| costs[backPorch] = 0.0; | |
| needsUpdating.addLast(backPorch); | |
| while (!needsUpdating.isEmpty()) { | |
| currentUpdate = needsUpdating.removeFirst(); | |
| for (int j = 0; j < stones.length; j++) { | |
| iterations++; | |
| tempCost = cost(stones[j][start],stones[j][stop],stones[j][height]); | |
| if (currentUpdate.compareTo(stones[j][start])==0) { | |
| if (costs[currentUpdate]+tempCost < costs[stones[j][stop]]) { | |
| costs[stones[j][stop]] = costs[currentUpdate]+tempCost; | |
| needsUpdating.addLast(stones[j][stop]); | |
| //System.out.println("Added "+stones[j][stop]); | |
| } | |
| } | |
| else if (currentUpdate.compareTo(stones[j][stop])==0) { | |
| if (costs[currentUpdate]+tempCost < costs[stones[j][start]]) { | |
| costs[stones[j][start]] = costs[currentUpdate]+tempCost; | |
| needsUpdating.addLast(stones[j][start]); | |
| //System.out.println("Added "+stones[j][start]); | |
| } | |
| } | |
| } | |
| } | |
| /*for (int i = 0; i < costs.length; i++) { | |
| if (costs[i] < 999) System.out.println("costs["+i+"]="+costs[i]); | |
| } */ | |
| return costs[gazebo]; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment