Skip to content

Instantly share code, notes, and snippets.

@adrienjoly
Created June 12, 2011 19:44
Show Gist options
  • Save adrienjoly/1021923 to your computer and use it in GitHub Desktop.
Save adrienjoly/1021923 to your computer and use it in GitHub Desktop.
My solution to @code_of_duty challenge
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