The Big Programming Thread - Page 787

public static void main (String[] args)  {
    import java.util.Arrays;

    int[] testArr = {5, 2, 3};
    int[] testArr2 = {5, 1, 4};
    int[] testArr3 = {5, 1, 2};
    String t1 = Arrays.toString(testArr);
    String t2 = Arrays.toString(testArr2);
    String t3 = Arrays.toString(testArr3);

    System.out.println("Can"
        + (canSplit(testArr, new int[testArr.length], 0)  ? " " : "'t ")
        + "split "
        +  t1
    );
    System.out.println("Can"
        + (canSplit(testArr2, new int[testArr2.length], 0)  ? " " : "'t ")
        + "split "
        +  t2
    );
    System.out.println("Can"
        + (canSplit(testArr3, new int[testArr3.length], 0)  ? " " : "'t ")
        + "split "
        +  t3
    );
}

public static int arraySum(int[] arr, int idx, int sum) {
    if (idx == arr.length) {
        return sum;
    }

    return arraySum(arr, idx + 1, sum + arr[idx]);
}
 
public static Boolean arrayCompare(int[] a, int[] b) {
    return arraySum(a, 0, 0) == arraySum(b, 0, 0);
}
 
public static Boolean canSplit(int[] a, int[] b, int idx) {
    if (idx == 0 && arraySum(a, 0, 0) % 2 != 0) {
        return false;
    }

    if (idx == a.length) {
        return false;
    }

    if (arrayCompare(a, b)) {
        return true;
    }

    b[idx] = a[idx];
    a[idx] = 0;
 
    return canSplit(a, b, idx + 1);
}

public static bool subsetMatch(int[] arr) {
    if (arr.length < 2) {
        return false;
    }
    ArrayList<int> subset1 = new ArrayList<int>();
    ArrayList<int> subset2 = new ArrayList<int>();
    return subsetMatchHelper(arr, 0, subset1, subset2);
}

public static bool subsetMatchHelper(int[] arr, index, ArrayList<int> subset1, ArrayList<int> subset2) {
    if (arr.length == index) {
        return arraySum(subset1, 0, 0) == arraySum(subset2, 0, 0);
    }
    else {
        return (subsetMatchHelper(arr, index + 1, subset1.add(arr[index]), subset2) ||  
                 subsetMatchHelper(arr, index + 1, subset1, subset2.add(arr[index]));
    }
}

f :: [Int] -> Bool
f [] = True                            -- is this the intended behavior?
f xs = f_internal xs [] []

f_internal :: [Int] -> [Int] -> [Int] -> Bool
f_internal []     ys zs = sum ys == sum zs
f_internal (x:xs) ys zs = f_internal xs (x:ys) zs || f_internal xs ys (x:zs)

import Test.HUnit


testFinternal = TestCase (do
        -- base case
        assertBool "" (f_internal [] [] []
        assertBool "" (f_internal [] [4] [2,2]
        assertBool "" (not $ f_internal [] [1] []
        assertBool "" (not $ f_internal [] [2,7] [3,2,1]
        -- success
        assertBool "" (f_internal [1] [3] [4]
        assertBool "" (f_internal [1] [4] [3]
        -- fail
        assertBool "" (not $ f_internal [1] [] []
        assertBool "" (not $ f_internal [2] [5,3] [8,1]
    )

testF = TestCase (do
        assertBool "example1" (f [2,2]
        assertBool "example2" (f [2,3,2,3]
        assertBool "example3" (not $ f [2,3]
        assertBool "example4" (f [5,2,3]
        assertBool "example5" (not $ f [5,2,4]
        assertBool "example6" (f [2,6,2,2]
    )


------------------------------------------------------------------------------

tests = TestList [
        TestLabel "testFinternal" testFinternal,
        TestLabel "testF" testF
    ]

------------------------------------------------------------------------------

main :: IO Counts
main = runTestTT $ tests

f :: [Int] -> Bool
f xs = f_internal xs 0 0

f_internal :: [Int] -> Int -> Int -> Bool
f_internal []     y z = y == z
f_internal (x:xs) y z = f_internal xs (x+y) z || f_internal xs y (x+z)

star :: String -> String
star "" = ""
star (x:"") = (x:"")
star (x:y:rest)
 | x == y    = x:'*':star (y:rest)
 | otherwise = x:star (y:rest)

bool HasTwoSubArraysWithSameTotal(int[] values){
	return HasTwoSubArraysWithSameTotal(values, 0, 0, 0);
}

bool HasTwoSubArraysWithSameTotal(int[] values, int sumA, int sumB, int index){
	return values.Length == index ? sumA == sumB :
		 HasTwoSubArraysWithSameTotal(values, sumA + values[index], sumB, index + 1) ||
		 HasTwoSubArraysWithSameTotal(values, sumA, sumB + values[index], index + 1);
}