rikāmā — When you have no better things to do

Last week, I came across an interesting question:

Given a string “123456789 = 100”, insert as many ‘+’ and ‘–’ between the numbers on the LHS (left hand side) and satisfy the equation. How many such combinations are possible?

I wrote a program for this and it generated the following eleven such combinations:

1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100
12 + 3 – 4 + 5 + 67 + 8 + 9 = 100
1 + 23 – 4 + 56 + 7 + 8 + 9 = 100
1 + 2 + 34 – 5 + 67 – 8 + 9 = 100
1 + 23 – 4 + 5 + 6 + 78 – 9 = 100
12 + 3 + 4 + 5 – 6 – 7 + 89 = 100
123 – 4 – 5 – 6 – 7 + 8 – 9 = 100
12 – 3 – 4 + 5–6 + 7 + 89 = 100
123 + 4 – 5 + 67 – 89 = 100
123 + 45 – 67 + 8 – 9 = 100
123 – 45 – 67 + 89 = 100

I wondered, how many such combinations are possible for all the numbers from 0 to 100. Here is the result:

–100 to 100?

–1000 to 1000?

How about from –2000 to 2000 range?

Observations

It might be quite obvious to a mathematician but I was surprised to see how symmetric (almost) the graph is for the range –N to +N.

Another interesting observation is how it is peaking at the zero mark. I can’t reason out why would that be the case. Maybe one of the readers can help me with it.

And finally, it is amazing to see how the distribution of values of this function is normal. A function that seemed so random at the start is not so random after all.

Code

Here is my Java code that generated this result.

public class OneToTenEqualsHundred {

    public static void main(String[] args) {
        ValueRange range = ValueRange.of(-2000, 2000);
        System.out.println(getSumCounts("123456789", range));
    }

    private static Map<Integer, Integer> getSumCounts(String ip, 
                                            ValueRange range) {
        Set<String> combs = generateCombinations(ip);
        Map<Integer, Integer> ans = new TreeMap<>();
        for (String comb : combs) {
            int sum = evaluateExpression(comb);
            if (range.isValidIntValue(sum)) {
                ans.put(sum, ans.getOrDefault(sum, 0) + 1);
            }
        }
        return ans;
    }

    private static Set<String> generateCombinations(String s) {
        Set<String> ans = new TreeSet<>();
        if (s.length() == 1) {
            ans.add(s);
            return ans;
        }
        for (int i = 1; i < s.length(); i++) {
            String lhs = s.substring(0, i);
            Set<String> rhs = generateCombinations(s.substring(i));
            for (String rh : rhs) {
                ans.add(lhs + "+" + rh);
                ans.add(lhs + "-" + rh);
            }
        }
        ans.add(s);
        return ans;
    }

    private static int evaluateExpression(String s) {
        int ans = 0, num = 0;
        boolean isPositive = true;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= '1' && ch <= '9') {
                num = num * 10 + (ch - '0');
            } else {
                ans += (isPositive ? num : num * -1);
                num = 0;
                isPositive = ch == '+';
            }
        }

        ans += (isPositive ? num : num * -1);
        return ans;
    }
}