ACM-ICPC 2013 South Africa Regionals ProblemD Solution

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package problemd;

import java.util.ArrayList;
import java.util.Scanner;

/*
 * NumberType represents a possible representation of a single
 * number or figure in a char array
 */
class NumberType
{
    public NumberType(int start, int stop, final char[] array)
    {
        this.start = start;
        this.stop = stop;
        this.data = array;
    }
    public final int start;
    public final int stop;
    public final char[] data;
}

/**
 *
 * @author WhiZTiM
 */
public class ProblemD {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ProblemD wahala = new ProblemD();
        wahala.run_main();
    }


    private void run_main()
    {
        Scanner sc = new Scanner(System.in);

        //Store answers as boolean value
        ArrayList<Boolean> answers = new ArrayList<>();
        while(true)
        {
            String[] values = sc.nextLine().split("[ ]+"); //inputs

            if(values.length < 44)
                break;

            //convert to character array
            char[] inputs = new char[44];
            for(int i = 0; i < values.length; i++)
            {
                inputs[i] = values[i].charAt(0);
            }

            answers.add(check_validity(inputs));
        }

        //Print answers
        for(Boolean bool : answers)
        {
            if(bool.booleanValue())
                System.out.println("valid");
            else
                System.out.println("invalid");
        }
    }

    private boolean check_validity(final char[] input_sequence)
    {
        boolean succeded = false;

        //a copy of input_sequence for validation
        char[] inputs = new char[44];
        System.arraycopy(input_sequence, 0, inputs, 0, 44);

        NumberType na1 = new NumberType(0, 7, inputs);
        NumberType na2 = new NumberType(7, 14, inputs);
        NumberType nb1 = new NumberType(16, 23, inputs);
        NumberType nb2 = new NumberType(23, 30, inputs);
        NumberType nc1 = new NumberType(30, 37, inputs);
        NumberType nc2 = new NumberType(37, 44, inputs);

        // outer loop to remove a stick, inner loop to place a stick
        // Runtime ... O(n^2) . .. . estimated: 44 x 44 = 1936 loop count
        // Worst case = 44 * 44 * 7 = 14,000 approx... really cheap!!!
        for(int i = 0; i < 44; i++)
        {
            if(inputs[i] == '0')    // if theres no stick here
                continue;
            // take away the stick and use it in the inner loop
            inputs[i] = '0';

            //attempt placing the loop
            for(int j = 0; j < 44; j++)
            {
                //The rule says a matchstick must move so, don't operate on self
                if( i == j )
                    continue;

                if(inputs[j] == '1')    // if theres a stick
                    continue;
                // put the stick here
                inputs[j] = '1';

                //Find out arithmetic operation, refer to question
                boolean IsAddition = false;
                if(inputs[14] == '1' && inputs[15] == '1')
                    IsAddition = true;
                //a vertical stick alone; or no-stick is an invalid operand
                if((inputs[14] == '1' && inputs[15] == '0') ||
                   (inputs[14] == '0' && inputs[15] == '0') )
                {
                    inputs[j] = '0';  // revert the changes
                    continue;
                }
                succeded = try_computation(na1, na2, IsAddition,
                        nb1, nb2, nc1, nc2);
                if(succeded)
                    break;

                inputs[j] = '0';     // revert the changes
            }

            if(succeded)
                break;

            inputs[i] = '1';        // revert the changes
        }

        return succeded;
    }

    /*
     * Attempts to recognise number fields and then compute
     * returns true if the 44 sticks represents a valid math equation
     * else, returns false
     */
    private static boolean try_computation(NumberType na1, NumberType na2,
                           boolean isAddition, NumberType nb1, NumberType nb2,
                           NumberType nc1, NumberType nc2)
    {
        int ka1 = get_representation(na1);
        int ka2 = get_representation(na2);
        int kb1 = get_representation(nb1);
        int kb2 = get_representation(nb2);
        int kc1 = get_representation(nc1);
        int kc2 = get_representation(nc2);

        if( !( is_valid(ka1) && is_valid(ka2) && is_valid(kb1) &&
               is_valid(kb2) && is_valid(kc1) && is_valid(kc2)) )
                return false;
        int A = concatenate_numbers(ka1, ka2);
        int B = concatenate_numbers(kb1, kb2);
        int C = concatenate_numbers(kc1, kc2);

        if(isAddition)
            return ((A + B) == C);
        return ((A - B) == C);
    }

    /*
     * Gets the type system's int representation of NumberType
     * i.e from the range of 7 sticks, the possible int value NumberType num represents
     * returns the integer value if recognized, else
     * returns -1
     */
    private static int get_representation(final NumberType num)
    {
        if(equivalent(num, n0))
            return 0;
        if(equivalent(num, n1))
            return 1;
        if(equivalent(num, n2))
            return 2;
        if(equivalent(num, n3))
            return 3;
        if(equivalent(num, n4))
            return 4;
        if(equivalent(num, n5))
            return 5;
        if(equivalent(num, n6))
            return 6;
        if(equivalent(num, n7))
            return 7;
        if(equivalent(num, n8))
            return 8;
        if(equivalent(num, n9))
            return 9;
        return -1;
    }

    /*
     * Compares NumberType num with the char sequence in field
     * returns true if they are EXACTLY the same match
     * else, returns false!
     */
    private static boolean equivalent(NumberType num, char[] field)
    {
        assert(num.data.length >= field.length);
        for(int i = 0; i < field.length; i++)
            if(num.data[ num.start + i ] != field[i])
                return false;
        return true;
    }

    private static boolean is_valid(int a)
    {
        return a >= 0;
    }

    private static int concatenate_numbers(int a, int b)
    {
        return (10 * a) + b;
    }

    //final static char[] xx = {'0', '1', '2', '3', '4', '5', '6'};
    final static char[] n0 = {'1', '0', '1', '1', '1', '1', '1'};
    final static char[] n1 = {'0', '0', '0', '1', '1', '0', '0'};
    final static char[] n2 = {'1', '1', '1', '1', '0', '0', '1'};
    final static char[] n3 = {'1', '1', '1', '1', '1', '0', '0'};
    final static char[] n4 = {'0', '1', '0', '1', '1', '1', '0'};
    final static char[] n5 = {'1', '1', '1', '0', '1', '1', '0'};
    final static char[] n6 = {'1', '1', '1', '0', '1', '1', '1'};
    final static char[] n7 = {'1', '0', '0', '1', '1', '0', '0'};
    final static char[] n8 = {'1', '1', '1', '1', '1', '1', '1'};
    final static char[] n9 = {'1', '1', '0', '1', '1', '1', '0'};
}