<p>You are given a string <code>s</code> that contains digits <code>0-9</code>, addition symbols <code>&#39;+&#39;</code>, and multiplication symbols <code>&#39;*&#39;</code> <strong>only</strong>, representing a <strong>valid</strong> math expression of <strong>single digit numbers</strong> (e.g., <code>3+5*2</code>). This expression was given to <code>n</code> elementary school students. The students were instructed to get the answer of the expression by following this <strong>order of operations</strong>:</p>

<ol>
	<li>Compute <strong>multiplication</strong>, reading from <strong>left to right</strong>; Then,</li>
	<li>Compute <strong>addition</strong>, reading from <strong>left to right</strong>.</li>
</ol>

<p>You are given an integer array <code>answers</code> of length <code>n</code>, which are the submitted answers of the students in no particular order. You are asked to grade the <code>answers</code>, by following these <strong>rules</strong>:</p>

<ul>
	<li>If an answer <strong>equals</strong> the correct answer of the expression, this student will be rewarded <code>5</code> points;</li>
	<li>Otherwise, if the answer <strong>could be interpreted</strong> as if the student applied the operators <strong>in the wrong order</strong> but had <strong>correct arithmetic</strong>, this student will be rewarded <code>2</code> points;</li>
	<li>Otherwise, this student will be rewarded <code>0</code> points.</li>
</ul>

<p>Return <em>the sum of the points of the students</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/17/student_solving_math.png" style="width: 678px; height: 109px;" />
<pre>
<strong>Input:</strong> s = &quot;7+3*1*2&quot;, answers = [20,13,42]
<strong>Output:</strong> 7
<strong>Explanation:</strong> As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,<u><strong>13</strong></u>,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [<u><strong>20</strong></u>,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;3+5*2&quot;, answers = [13,0,10,13,13,16,16]
<strong>Output:</strong> 19
<strong>Explanation:</strong> The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [<strong><u>13</u></strong>,0,10,<strong><u>13</u></strong>,<strong><u>13</u></strong>,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,<strong><u>16</u></strong>,<strong><u>16</u></strong>]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;6+0*1&quot;, answers = [12,9,6,4,8,6]
<strong>Output:</strong> 10
<strong>Explanation:</strong> The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 31</code></li>
	<li><code>s</code> represents a valid expression that contains only digits <code>0-9</code>, <code>&#39;+&#39;</code>, and <code>&#39;*&#39;</code> only.</li>
	<li>All the integer operands in the expression are in the <strong>inclusive</strong> range <code>[0, 9]</code>.</li>
	<li><code>1 &lt;=</code> The count of all operators (<code>&#39;+&#39;</code> and <code>&#39;*&#39;</code>) in the math expression <code>&lt;= 15</code></li>
	<li>Test data are generated such that the correct answer of the expression is in the range of <code>[0, 1000]</code>.</li>
	<li><code>n == answers.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= answers[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        # for the expression do it right and do it wrong

        # right
        current_num = int(s[0])
        remaining_elems = []

        for i in range(1, len(s), 2):
            op = s[i]
            if op == "+":
                remaining_elems.append(current_num)
                current_num = int(s[i+1])
            else:
                next_num = int(s[i+1])
                current_num = current_num * next_num
        correct_answer = sum(remaining_elems) + current_num

        # wrong
        parsed_exp = [int(s[i]) if i % 2 == 0 else s[i] for i in range(len(s)) ]

        # access w/ pair a, b where a is starting num of num and b is ending num of num
        num_nums = int((len(parsed_exp) + 1) / 2)
        cached_values = [[None] * num_nums for _ in range(num_nums)]

        def get_results_ptr(a, b):
            # for c in cached_values:
            #     print(c)
            # print("")


            if cached_values[a][b] is not None:
                return cached_values[a][b]
            if (b-a) == 0:
                result = [parsed_exp[2 * a]]
                cached_values[a][b] = result
                return result
            all_vals = []

            for i in range(a, b):
                left_vals = get_results_ptr(a, i)
                right_vals = get_results_ptr(i + 1, b)

                if parsed_exp[2 * i + 1] == "+":
                    for l in left_vals:
                        for r in right_vals:
                            all_vals.append(l+r)
                else:
                    for l in left_vals:
                        for r in right_vals:
                            all_vals.append(l*r)
            
            all_vals = [a for a in set(all_vals) if a <= 1000]
            cached_values[a][b] = all_vals
            return all_vals



        def get_possible_results(list_vals):
            # print(list_vals)
            if len(list_vals) == 1:
                return list_vals
            
            all_vals = []

            for i in range(1, len(list_vals), 2):
                # print(list_vals[:i], list_vals[i+1:])
                left_vals = get_possible_results(list_vals[:i])
                right_vals = get_possible_results(list_vals[i+1:])

                if list_vals[i] == "+":
                    for l in left_vals:
                        for r in right_vals:
                            all_vals.append(l+r)
                else:
                    for l in left_vals:
                        for r in right_vals:
                            all_vals.append(l * r)

            return list(set(all_vals))
        
        # wrong_answers = get_possible_results(parsed_exp)
        wrong_answers = get_results_ptr(0, num_nums - 1)
        # print(wrong_answers)
        # print(cached_values)
        
        # # horrifically slow but probably right
        # wrong_answers = []
        # possible_expressions = [[int(s[i]) if i % 2 == 0 else s[i] for i in range(len(s)) ]]

        # while len(possible_expressions) > 0:
        #     # print(possible_expressions)
            
        #     current_expression = possible_expressions.pop(0)
        #     # print("current", current_expression, len(current_expression))
        #     if len(current_expression) == 1:
        #         # print("wrong", current_expression)
        #         wrong_answers.append(current_expression[0])
        #         continue
        #     for i in range(1, len(current_expression), 2):
        #         first_half = current_expression[:i-1]
        #         second_half = current_expression[i+2:]
        #         if current_expression[i] == "*":
        #             middle_num = current_expression[i-1] * current_expression[i+1]
        #         else:
        #             middle_num = current_expression[i-1] + current_expression[i+1]
        #         complete_expression = first_half + [middle_num] + second_half
        #         if complete_expression not in possible_expressions:
        #             possible_expressions.append(complete_expression)
        


        # print(correct_answer, wrong_answers)        
        total_points = 0

        for a in answers:
            if a == correct_answer:
                total_points += 5
            elif a in wrong_answers:
                total_points += 2
        # print(correct_answer, wrong_answer)

        return total_points

23300