24 Game

We can use a recursive function to consider all possible ways to apply the operators between the cards, and check if any of these combinations result in 24.

Here’s a Python code that does this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:

        def dfs(nums):
            # Base case: if there is only one number left, check if it is 24
            if len(nums) == 1:
                return abs(nums[0] - 24) < 1e-6

            # Consider all possible pairs of numbers in the current list
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i != j:
                        # Store the numbers that are not being considered in this step
                        remaining = [nums[k] for k in range(len(nums)) if k != i and k != j]
                        # Apply all possible binary operators to the chosen pair of numbers
                        for op in ['+', '-', '*', '/']:
                            if op != '/' or nums[j] != 0:  # Avoid division by zero
                                if (op == '+' and i < j) or (op == '*' and i < j): # Avoid duplicate cases
                                    continue
                                if op == '+':
                                    new_num = nums[i] + nums[j]
                                elif op == '-':
                                    new_num = nums[i] - nums[j]
                                elif op == '*':
                                    new_num = nums[i] * nums[j]
                                else:
                                    new_num = nums[i] / nums[j]
                                # Continue with the next step of the recursion
                                if dfs(remaining + [new_num]):
                                    return True
            return False

        return dfs(cards)

Explanation:

  • The dfs function is a recursive depth-first search that takes a list of numbers (initially the cards) and tries all possible combinations of binary operations.
  • In each step, we choose a pair of numbers and apply one of the four operators to them, then call the dfs function recursively on the remaining numbers, along with the result of the chosen operation.
  • If at any point we reach a list with a single number that is equal to 24 (allowing for a small tolerance due to floating-point arithmetic), we return True.
  • If we exhaust all possibilities without finding 24, we return False.

This code checks all possible combinations and returns True if any of them result in 24, False otherwise. The time complexity of this solution is O(4! * 4^4) since we have to consider all permutations and combinations of the four numbers and four operations.

10 Prerequisite LeetCode Problems

“679. 24 Game” requires knowledge of recursion, backtracking, and combinatorics. Here are some simpler problems to prepare for this problem:

  1. 78. Subsets: This problem involves generating all possible subsets of a set, which is a good introduction to the concept of recursion and backtracking.

  2. 22. Generate Parentheses: This problem requires generating all valid combinations of parentheses, which helps in understanding backtracking.

  3. 39. Combination Sum: This problem requires finding all combinations in an array that sum up to a target, which is a good problem for understanding recursion and backtracking.

  4. 216. Combination Sum III: This problem extends the previous one by adding the constraint that you must use exactly k numbers, which adds another level of complexity to the backtracking process.

  5. 46. Permutations: This problem asks you to generate all permutations of a sequence of numbers. It helps to understand how to traverse all possible combinations in a sequence.

  6. 77. Combinations: This problem is about generating all combinations of a certain size from a sequence of numbers. It’s good for understanding recursion and backtracking in a combinatorial context.

  7. 241. Different Ways to Add Parentheses: This problem requires you to find different ways to compute a mathematical expression by changing the order of operations. It’s good practice for dealing with mathematical expressions in recursion.

  8. 131. Palindrome Partitioning: This problem asks for all possible ways to partition a string into substrings that are palindromes, which is another form of combinatorial problem.

  9. 40. Combination Sum II: This problem, similar to Combination Sum, requires finding all unique combinations in an array that sum up to a target.

  10. 47. Permutations II: This problem requires generating all permutations of a sequence of numbers, considering there could be duplicates.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import itertools as it

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return round(nums[0], 4) == 24
        else:
            for (i, m), (j, n) in it.combinations(enumerate(nums), 2):
                    new_nums = [x for t, x in enumerate(nums) if i != t != j]
                    inter = {m+n, abs(m-n), n*m}
                    if n != 0: inter.add(m/n)
                    if m != 0: inter.add(n/m)
                    
                    if any(self.judgePoint24(new_nums + [x]) for x in inter):
                        return True
            
            return False

Problem Classification

This problem falls under the domain of combinatorics and mathematical expressions.

Components of the problem:

  1. Input: An array of four integers, each representing the number on a card. Each integer is between 1 and 9 inclusive.

  2. Output: A boolean value - true if it’s possible to arrange the numbers on the cards using mathematical operators to get a total of 24, and false otherwise.

  3. Constraints:

    • The division operation is real division, not integer division.
    • All operations are binary, i.e., between two numbers.
    • Unary operators are not allowed.
    • Concatenation of numbers is not allowed.

Based on these components, this problem can be classified as a “Search problem” where the objective is to search through all possible combinations and permutations of numbers and mathematical operations to check if any of them result in a specific value (24 in this case).

Furthermore, given the constraints of the problem (such as no unary operations and no concatenation of numbers), it also touches upon the subdomain of “Parsing and Evaluating Mathematical Expressions”, although in a more limited and specific context than general problems in that subdomain.

The ‘how’ part of the solution likely involves generating all permutations of the numbers and combinations of the operations and then evaluating these expressions to check if any of them equals 24. This is an exhaustive search approach, which is feasible due to the relatively small input size. The problem also likely requires some understanding of the order of operations in mathematics to correctly evaluate the expressions.

Based on the problem statement, the problem can be classified as follows:

  1. Combinatorial Problem: The problem deals with all possible combinations of the given numbers and their various operations. Hence, it involves combinatorics.

  2. Recursion: The problem involves checking each possibility and then recursing on the remaining possibilities.

  3. Number Theory: The problem requires a good understanding of arithmetic operations and the numbers themselves.

  4. Decision Problem: At its core, this problem asks a yes-or-no question: Can we obtain a certain number (24 in this case) by performing a sequence of operations on the given numbers?

  5. Depth-First Search (DFS): The recursive nature of the problem also suggests a depth-first traversal of the tree of all possible combinations of operations and number choices.

The above classifications are based on the conceptual and computational tasks required to solve the problem, not on specific implementation details.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

The problem “24 Game” (#679 on LeetCode) involves using any of the 4 operations (+, -, *, /) to manipulate 4 numbers to achieve the final value of 24. You can use parentheses to change the priority of the operations.

An isomorphic problem to this could be “Basic Calculator” (#224 on LeetCode). In this problem, you are given a string s representing a valid expression and you are asked to evaluate this expression and return its value. The string s contains only non-negative integers, ‘+’, ‘-’, ‘*’, ‘/’, ‘(’, and ‘)’. It is guaranteed that the expression is a valid one.

Both problems deal with the manipulation of numbers using arithmetic operations and respecting the priority of operations by considering the use of parentheses. The primary difference is that “24 Game” has a fixed target (24), and you are manipulating specific numbers to reach that target, while “Basic Calculator” is more general, involving the calculation of an arbitrary arithmetic expression.

“24 Game” is more complex because it involves more operations and combinations, and the task of trying to reach a specific target adds an additional layer of challenge. “Basic Calculator” is simpler in that it involves the straightforward evaluation of an arithmetic expression.

Language Agnostic Coding Drills

This Python code uses recursion and combinatorics to solve the problem. Here are the learning units:

  1. Understanding Basic Python Syntax and Control Flow: The basic building block of any program. This includes understanding of for loops, if-else conditions, function definitions, and calling a function.

  2. Data Types and Variables: Understanding of basic data types in Python, such as lists, integers, floating-point numbers, and Boolean. How to define variables and manipulate them.

  3. Understanding itertools and Combinations: The itertools module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination. Understanding combinations is crucial here, as the code uses the combinations function from the itertools module to generate all possible pairs of indices and their corresponding values.

  4. Enumerate Function: Understand how to use the enumerate function, which is used for iterating over indices and items of a list.

  5. List Comprehensions: Understanding of how list comprehensions work, and how to create and use them. List comprehensions provide a concise way to create lists.

  6. Understanding Sets and Operations: Understand how to define and manipulate sets. The set is a built-in data type in Python, and here it is used to keep the intermediate results.

  7. Recursion: Understanding the concept of recursion and how to use it in functions. This is used in the function judgePoint24, where the function calls itself.

  8. Problem-Solving Approach and Algorithm Design: Understanding how to approach a problem and design a solution. The key here is recognizing the need to try every possible combination of operations on all pairs of numbers.

The problem-solving approach here is to apply all possible combinations of basic operations (addition, subtraction, multiplication, division) to all pairs of numbers, and to repeat this process on the results until we have only one number left, which we check against the target (24 in this case). The key is to understand that the solution requires us to try all possible operations, on all possible pairs, and to repeat this until we reach the target or exhaust all possibilities. This can be achieved by combining all of the above-mentioned drills.

Targeted Drills in Python

Drill 1: Understanding Basic Python Syntax and Control Flow

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# This drill is to get comfortable with Python syntax and control flow.

def basic_control_flow():
    for i in range(5):
        if i % 2 == 0:
            print(f"{i} is even")
        else:
            print(f"{i} is odd")

basic_control_flow()

Drill 2: Data Types and Variables

1
2
3
4
5
6
7
8
9

# This drill is to understand Python basic data types and variable usage.

def data_types():
    my_int = 10
    my_float = 20.5
    my_bool = True
    print(f"Integer: {my_int}, Float: {my_float}, Boolean: {my_bool}")

data_types()

Drill 3: Understanding itertools and Combinations

1
2
3
4
5
6
7
8
9

# This drill is to understand the use of itertools and combinations

import itertools

def combinations_example():
    for combo in itertools.combinations('1234', 2):
        print(''.join(combo))

combinations_example()

Drill 4: Enumerate Function

1
2
3
4
5
6
7

# This drill is to understand the use of the enumerate function.

def enumerate_example():
    for i, letter in enumerate('abcde'):
        print(f"Index: {i}, Letter: {letter}")

enumerate_example()

Drill 5: List Comprehensions

1
2
3
4
5
6
7

# This drill is to understand the use of list comprehensions.

def list_comprehension_example():
    squares = [x**2 for x in range(10)]
    print(squares)

list_comprehension_example()

Drill 6: Understanding Sets and Operations

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# This drill is to understand the use of sets and set operations.

def sets_example():
    s = {1, 2, 3, 4, 5, 2, 3}
    print(s)  # Observe the removal of duplicate values
    s.add(6)  # Add an element
    print(s)
    s.remove(1)  # Remove an element
    print(s)

sets_example()

Drill 7: Recursion

1
2
3
4
5
6
7
8
9

# This drill is to understand the concept of recursion.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

Each of these drills represents a unit of learning necessary to understand and implement the final solution. By combining these elements, one can approach solving the problem by iteratively applying operations on combinations of numbers, storing intermediate results in a set, and recursively trying until a solution is found or all options are exhausted.

Python Basics

any

The any() function in Python 3 is a built-in function that takes an iterable (like a list, tuple, dictionary etc.) and returns True if any of the elements in the iterable are truthy (i.e., they evaluate to True in a Boolean context), otherwise it returns False.

In other words, any() returns True if at least one element in the iterable is True.

Here’s an example:

1
2
3

print(any([False, False, False, True]))  # Outputs: True
print(any([False, False, False, False]))  # Outputs: False
print(any([0, "", None]))  # Outputs: False

In the first example, any() returns True because there’s at least one True in the list. In the second example, all elements are False, so any() returns False. In the third example, all elements are falsy (they all evaluate to False in a Boolean context), so again any() returns False.

Note that any() stops processing as soon as it encounters the first True element, a property known as short-circuiting. This can be an advantage in terms of performance when dealing with large iterables.

abs

The abs() function in Python3 returns the absolute value of a number. The absolute value of a number is its distance from 0 on the number line, regardless of the direction. So, the absolute value of both 10 and -10 is 10.

Here’s how you might use it:

1
2
3

print(abs(-5))  # Outputs: 5
print(abs(10))  # Outputs: 10
print(abs(-3.14))  # Outputs: 3.14

The abs() function works with integers, floating-point numbers, and complex numbers:

1
2
3

print(abs(-3))  # Outputs: 3, works with integers
print(abs(-3.5))  # Outputs: 3.5, works with floating point numbers
print(abs(3 + 4j))  # Outputs: 5.0, works with complex numbers, returning the magnitude

In the case of complex numbers, the abs() function calculates the magnitude (length of the vector from the origin to the point) using the Pythagorean theorem. For a complex number z = a + bj, the absolute value is calculated as sqrt(a**2 + b**2).