Created
June 12, 2011 19:44
-
-
Save adrienjoly/1021923 to your computer and use it in GitHub Desktop.
My solution to @code_of_duty challenge
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
import java.io.BufferedReader; | |
import java.io.FileReader; | |
import java.io.IOException; | |
import java.io.PrintStream; | |
/** | |
* Proposed solution to Code of Duty | |
* @author adrienjoly | |
* This program is dedicated to Anouck ^^ | |
**/ | |
public class Cod { | |
protected static PrintStream os = System.out; | |
protected int vect[]; | |
protected int i = 0, sum = 0, iter = 0; | |
/** | |
* Initialize a vector of given size | |
* @param size | |
*/ | |
public Cod (int size) { | |
vect = new int[size]; | |
} | |
/** | |
* Add n as the next number of the vector | |
* @param n | |
*/ | |
public void feed (int n) { | |
vect[i++] = n; | |
sum += n; | |
} | |
/** | |
* Print the current state of the vector | |
*/ | |
public void printVect() { | |
os.print((iter++) + " : ("); | |
for (int i=0; i<vect.length-1; ++i) | |
os.print(vect[i] + ", "); | |
os.println(vect[vect.length-1] + ")"); | |
} | |
/** | |
* Process the vector, and print iterations | |
*/ | |
public void printIterations() { | |
if (sum % vect.length != 0) // check if the vector is balanced | |
os.println(-1); | |
else { | |
// build a difference vector | |
int diff[] = new int[vect.length-1]; | |
int goal = sum / vect.length; // goal is the expected value for all items | |
int prev = 0, iterations = 0; | |
for (int i=0; i<diff.length; ++i) { | |
prev = diff[i] = vect[i] - goal + prev; | |
iterations = Math.max(iterations, Math.abs(diff[i])); | |
} | |
os.println(iterations); | |
printVect(); | |
// process the vector | |
for (int remain = iterations; remain > 0; --remain) { | |
// process left-to-right transfers, for positive diff values | |
for (int i=0; i<diff.length; ++i) { | |
if (diff[i] > 0 && vect[i] > 0) { | |
--vect[i]; | |
++vect[i+1]; | |
--diff[i]; | |
} | |
} | |
// process right-to-left transfers, for negative diff values | |
for (int i=diff.length-1; i>=0; --i) { | |
if (diff[i] < 0 && vect[i+1] > 0) { | |
--vect[i+1]; | |
++vect[i]; | |
++diff[i]; | |
} | |
} | |
printVect(); | |
}; | |
} | |
os.println(); | |
} | |
public static void main(String[] args) throws NumberFormatException, IOException { | |
BufferedReader reader = new BufferedReader(new FileReader("input.txt")); | |
os = new PrintStream("output.txt"); | |
String line; | |
Cod current = null; | |
while ((line = reader.readLine()) != null) { | |
if (null == current) // initialize a new vector, given its length | |
current = new Cod (Integer.parseInt(line)); | |
else if (line.length() == 0) { // empty line => process the vector | |
current.printIterations(); | |
current = null; | |
} | |
else // in between: feed the vector with sequence of int | |
for (String n : line.split(" ")) | |
current.feed(Integer.parseInt(n)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment