Monday, December 3, 2012

CodeEval Ugly Numbers

// CodeEval Ugly Numbers

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

class Main {
    public static void main(String[] args) {
        ugly_numbers.main(args);
    }
}

class ugly_numbers {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                String[] lineArray = line.split(",");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    static long totUgly;

    private static void Process(String[] lineArray) {
        String s0 = lineArray[0].trim();
        long lastPart = Long.valueOf(s0.substring(0, 1));
        totUgly = 0;
        Generate('+', lastPart, s0, 1, lastPart);
        System.out.println(totUgly);
    }

    private static boolean IsUgly(long n) {
        if (n == 0 || n % 2 == 0 || n % 3 == 0
                || n % 5 == 0 || n % 7 == 0)
            return true;
        return false;
    }

    private static void Generate(char lastSign, long lastPart, String s, int xc,
            long currentSum) {
        if (xc == s.length()) {
            if (IsUgly(currentSum))
                totUgly++;
            return;
        }
        else {
            String firstChar = String.valueOf(s.charAt(xc));
            long newLastPart;
            long newCurSum;
            // concat
            newLastPart = (Math.abs(lastPart) * 10) + Long.valueOf(firstChar);
            if (lastSign == '+')
                newCurSum = currentSum - lastPart + newLastPart;
            else
                newCurSum = currentSum + lastPart - newLastPart;
            Generate(lastSign, newLastPart, s, xc + 1, newCurSum);
            // +
            newLastPart = Long.valueOf(firstChar);
            newCurSum = currentSum + newLastPart;
            Generate('+', newLastPart, s, xc + 1, newCurSum);
            // -
            newLastPart = Long.valueOf(firstChar);
            newCurSum = currentSum - newLastPart;
            Generate('-', newLastPart, s, xc + 1, newCurSum);
        }
    }
}

1 comment: