TopCoder Problem Statement - Dragons

Divide food up among 6 hungry Dragons.

001: /* 002: TopCoder 003: Single Round Match: 147 004: Division: 1 005: Level: 2 006: Points: 500 007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1520 008: */ 009: 010: import java.math.BigDecimal; 011: 012: public class Dragons { 013: 014: // The side of the cube we'll be returning. 015: private static final int SNAUGS_SIDE = 2; 016: 017: public String snaug(int[] initialFood, int rounds) { 018: 019: /* 020: Any two sides are neighbors if their numbers do not add up to 7. 021: */ 022: int[] neighbors = {1, 6, 2, 5, 3, 4}; 023: 024: // Copy the initialFood amounts into the currentRound. 025: Fraction[] currentRound = new Fraction[6]; 026: for (int i = 0; i < currentRound.length; i++) { 027: currentRound[i] = new Fraction(initialFood[i]); 028: } 029: 030: // Loop for the given number of rounds. 031: for (int round = 1; round <= rounds; round++) { 032: 033: // Create an array of fractions to hold the results. 034: Fraction[] nextRound = new Fraction[6]; 035: for (int j = 0; j < nextRound.length; j++) { 036: nextRound[j] = new Fraction(0); 037: } 038: 039: // Loop through all size sides. 040: for (int side = 0; side < 6; side++) { 041: 042: // Loop for all neighboring sides. 043: for (int neighbor = 0; neighbor < 6; neighbor++) { 044: 045: /* 046: The side is a neighbor if, and only if, side != neighbor, 047: and their two values in the neighbors array do not add 048: up to 7. 049: */ 050: if ((neighbor == side) || (neighbors[side] + 051: neighbors[neighbor] == 7)) { continue; } 052: 053: // Add the neighbors value. 054: nextRound[side] = nextRound[side].add 055: (currentRound[neighbor]); 056: } 057: 058: // At the end of the round divide by 4 to get 1/4. 059: nextRound[side] = nextRound[side].div(4); 060: } 061: 062: // Set currentRound to prepare for the next loop. 063: currentRound = nextRound; 064: } 065: 066: return currentRound[SNAUGS_SIDE].toString(); 067: } 068: 069: /* 070: This class handles all the fraction operations that we'll need. The 071: tests like to overflow even longs, so the internals are stored as 072: BigDecimals. 073: */ 074: public class Fraction { 075: 076: // Used in several places, so let's just have one copy. 077: final BigDecimal Zero = new BigDecimal(0); 078: 079: BigDecimal numerator; 080: 081: BigDecimal denominator; 082: 083: Fraction(BigDecimal num, BigDecimal den) { 084: this.numerator = num; 085: this.denominator = den; 086: reduce(); 087: } 088: 089: Fraction(long num) { 090: this.numerator = new BigDecimal(num); 091: this.denominator = new BigDecimal(1); 092: } 093: 094: /* 095: Adds another fraction to this fraction. Return a new instance. 096: */ 097: public Fraction add(Fraction f) { 098: 099: BigDecimal num; 100: BigDecimal den; 101: 102: // If the denominators are equal, just add the numerators. 103: if (this.denominator.equals(f.denominator)) { 104: den = this.denominator; 105: num = this.numerator.add(f.numerator); 106: 107: // Otherwise, cross-multiply. 108: } else { 109: num = (this.denominator.multiply(f.numerator)).add( 110: (this.numerator.multiply(f.denominator))); 111: 112: den = (this.denominator).multiply(f.denominator); 113: } 114: 115: return new Fraction(num, den); 116: } 117: 118: /* 119: Divides this fraction by an int. Returns a new instance. 120: */ 121: public Fraction div(int x) { 122: 123: // Division is done by multiplying the denominator by x. 124: return new Fraction( 125: this.numerator, 126: this.denominator.multiply(new BigDecimal(x)) 127: ); 128: } 129: 130: public String toString() { 131: 132: /* 133: If the denominator divides the numerator evenly, 134: return a whole number. 135: */ 136: if ((this.numerator.remainder(this.denominator)).equals(Zero)) { 137: return "" + this.numerator.divide(this.denominator); 138: 139: // Otherwise, display as a fraction. 140: } else { 141: return this.numerator + "/" + this.denominator; 142: } 143: } 144: 145: /* 146: Reduces the fraction by dividing the numerator and denominator by 147: their greatest common multiple. 148: */ 149: private void reduce() { 150: BigDecimal gcm = greatestCommonMultiple(this.numerator, 151: this.denominator); 152: this.numerator = this.numerator.divide(gcm); 153: this.denominator = this.denominator.divide(gcm); 154: } 155: 156: // Returns the greatest common multiple of two numbers. 157: private BigDecimal greatestCommonMultiple(BigDecimal x, BigDecimal y) { 158: if (y.equals(Zero)) { 159: return x; 160: } else { 161: return greatestCommonMultiple(y, x.remainder(y)); 162: } 163: } 164: } 165: }

The algorithm for solving this problem is very easy. Each round, the dragons steal 1/4 of the food available from each of their neighbors. The sum becomes their food for the start of the next round. The real difficulty lies in dealing with the fractions.

I used an inner class Fraction to encapsulate all of the work that needs to be done, including adding fractions, dividing, and printing them out in a canonical form. The tricky part here is that the numerators and denominators can get really big - like 61,572,651,155,457 / 17,592,186,044,416. After struggling with Longs that kept overflowing, I switched all the internals of the Fraction class over to BigDecimals.

Probably the most useful thing from the Fractions class is the greatestCommonMultiple() method. This is a good method to save since it comes up time and time again.

I believe lines 22 and 51 provide a good way for determining the neighbors on the cube. If you think of the cube as standard six-sided die , then the sum of any two opposite sides is 7. 1 is opposite 6, 2 is opposite 5, and 3 is opposite 4. Since the neighboring sides are any that are not yourself, or your opposite, we can use this array to skip any side / neighbor pairs where side == neighbor, or neighbors[side]+ neighbors[neighbor] == 7.

## No comments:

## Post a Comment