<commit_before>description = r"""
<div>
Is it possible to assign + and - signs to the numbers
<pre>
1434 3243 343 5 293 3408 123 487 93 12 2984 29
</pre>
so that the sum is 0? With recursion, we can try all possible combinations
of + and - for each number to find out. We will in fact solve a slightly more
general problem with an arbitrary target.
Write a recursive static method
<pre>boolean canMake(int target, int[] nums, int startIndex)</pre>
which sees if any assignment of +/- signs to the numbers
<pre>nums[startIndex], nums[startIndex+1], &hellip;, nums[nums.length-1]</pre> gives the total 
<code>target</code>. To do this, it should:
<ul>
<li>return true if startIndex is the same 
as nums.length (we examined all numbers) and target is zero, this means we hit the target
for this guessed choice of signs</li>
<li>return false if startIndex is the same
as nums.length (we examined all numbers) and target is not zero, this means we missed the target
for this guessed choice of signs</li>
<li>otherwise, recursively call <code>canMake</code> on 
<code>target &pm; nums[startIndex]</code> with <code>startIndex+1</code>
and if return true if <i>either one</i> returns true
</li>
</ul>
(Using startIndex is simpler and more efficient than trying to
shrink the array
in every step.)
"""

source_code = r"""
public static boolean canMake(int target, int[] nums, int startIndex) {
\[
   // we've given a sign to all numbers
   if (startIndex == nums.length) {
      if (target == 0) 
         return true;  // hit the target
      else
         return false; // missed the target
   }

   // try both possibilities, propagating any hit
   if (canMake(target + nums[startIndex], nums, startIndex+1))
      return true;

   if (canMake(target - nums[startIndex], nums, startIndex+1))
      return true;

   // neither recursive call found a solution
   return false;
]\
}

public static void main(String[] args) {
   int[] testArr = {1434, 3243, 343, 5, 293, 3408, 123, 487, 93, 12, 2984, 29};
   // should print true because
   // -1434+3243-343-5-293-3408-123-487-93-12+2984-29 = 0
   StdOut.println(canMake(0, testArr, 0)); // true
   testArr = new int[] {1, 2};
   // no way to make zero
   StdOut.println(canMake(0, testArr, 0)); // false
}
"""

tests = r"""
testMain();
test("canMake", 0, new int[] {1, 1, 1, 1, 1, 1}, 0);
test("canMake", 0, new int[] {1, 1, 1, 1, 1, 1, 1}, 0);
test("canMake", 0, new int[] {1, 2, 3, 4, 5, 6}, 0);
test("canMake", 0, new int[] {1, 2, 3, 4, 5, 6, 7}, 0);
test("canMake", 0, new int[] {1000, 100000, 100, 111111, 10, 1, 10000}, 0);
test("canMake", 0, new int[] {9, 16, 25}, 0);
test("canMake", 0, new int[] {0, 0, 0}, 0);
test("canMake", 0, new int[] {1435, 3243, 343, 5, 293, 3408, 123, 487, 93, 12, 2984, 29}, 0);
"""
<commit_msg>make ZeroSum clearer<commit_after>description = r"""
<div>
Is it possible to assign + and &ndash; signs to the numbers
<pre>
1434 3243 343 5 293 3408 123 487 93 12 2984 29
</pre>
so that the sum is 0? With recursion, we can try all possible combinations
of + and &ndash; for each number to find out. There are $2^n$ ways to assign
+ or &ndash; signs to $n$ numbers, and recursion can accomplish this by making
two recursive calls (one for +, one for &ndash;) at each of $n$ levels.
Each branch of the recursive call tree will keep a running sum of the numbers
it has assigned signs so far. To implement this in Java,
write a recursive static method
<pre>boolean testAllCombs(int runningSum, int[] nums, int seenSoFar)</pre>
which tries every assignment of +/&ndash; signs to the numbers
<pre>nums[seenSoFar], nums[seenSoFar+1], &hellip;, nums[nums.length-1]</pre> and adds each sum of signed numbers to
<code>runningSum</code>. To do this and acheieve the overall goal, your method should:
<ol>
<li>return true if <tt>seenSoFar</tt> is the same 
as nums.length (we examined all numbers) and runningSum is zero, this means we got 0 as the sum
for the choice of signs on this leaf of the recursive call tree</li>
<li>return false if <tt>seenSoFar</tt> is the same
as nums.length (we examined all numbers) and runningSum is not zero, this means we missed 0 as the sum for the choice of signs
on this leaf of the recursive call tree</li>
<li>otherwise, recursively call <code>testAllCombs</code> on 
<code>runningSum &pm; nums[seenSoFar]</code> and with <code>seenSoFar+1</code> in place of <code>seenSoFar</code>;
return true if <i>either one</i> of the two recursive calls returns true
</li>
</ol>
Using seenSoFar is analogous to the level of a fractal, to control 
the recursion depth and ensure that each number is included (as + or 
&ndash;) exactly once
in each branch.
Other than this, how is this recursive method used to achieve our goal?
To test if <tt>int[] arr</tt> has a zero-sum signing, 
we make an initial call with <tt>testAllCombs(0, arr, 0)</tt>.
If there is some 0-sum signing, then some call
on the bottom level (seenSoFar = nums.length) has a runningSum of 
0 and by rule 1, returns
true. By rule 2, this true value is propagated up the recursive call tree 
to return true at the top.
"""

source_code = r"""
public static boolean testAllCombs(int runningSum, int[] nums, int seenSoFar) {
\[
   // we've given a sign to all numbers
   if (seenSoFar == nums.length) {
      if (runningSum == 0) 
         return true;  // hit the runningSum
      else
         return false; // missed the runningSum
   }

   // try both possibilities, propagating any hit
   if (testAllCombs(runningSum + nums[seenSoFar], nums, seenSoFar+1))
      return true;

   if (testAllCombs(runningSum - nums[seenSoFar], nums, seenSoFar+1))
      return true;

   // neither recursive call found a solution
   return false;
]\
}

public static void main(String[] args) {
   int[] testArr = {1434, 3243, 343, 5, 293, 3408, 123, 487, 93, 12, 2984, 29};
   // should print true because
   // -1434+3243-343-5-293-3408-123-487-93-12+2984-29 = 0
   StdOut.println(testAllCombs(0, testArr, 0)); // true
   testArr = new int[] {1, 2};
   // no way to make zero
   StdOut.println(testAllCombs(0, testArr, 0)); // false
}
"""

tests = r"""
testMain();
test("testAllCombs", 0, new int[] {1, 1, 1, 1, 1, 1}, 0);
test("testAllCombs", 0, new int[] {1, 1, 1, 1, 1, 1, 1}, 0);
test("testAllCombs", 0, new int[] {1, 2, 3, 4, 5, 6}, 0);
test("testAllCombs", 0, new int[] {1, 2, 3, 4, 5, 6, 7}, 0);
test("testAllCombs", 0, new int[] {1000, 100000, 100, 111111, 10, 1, 10000}, 0);
test("testAllCombs", 0, new int[] {9, 16, 25}, 0);
test("testAllCombs", 0, new int[] {0, 0, 0}, 0);
test("testAllCombs", 0, new int[] {1435, 3243, 343, 5, 293, 3408, 123, 487, 93, 12, 2984, 29}, 0);
test("testAllCombs", 0, new int[] {1434, 3253, 343, 5, 293, 3408, 123, 487, 93, 22, 2984, 29}, 0);
"""

{'fraction_non_alphanumeric': 0.1355327686134641, 'fraction_numerical': 0.07549412988556992, 'mean_word_length': 3.8592057761732854, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5731865', 'n_tokens_mistral': 2734, 'n_tokens_neox': 2267, 'n_words': 982}