14.3 Solve 24

Let’s first review the helper functions we created.

# single step operation
cal <- function(x, y, op) {
    switch(op, x + y, x - y, x * y, x/y, y - x, y/x)
}
# multi-step operations
num_op <- function(num, op, n_nums = length(num)) {
    sol <- num
    for (step in 1:(n_nums - 1)) sol[step + 1] <- cal(sol[step], num[step + 1], op[step])
    return(sol)
}
# print a single step
print_op <- function(x, y, z, op) {
    switch(op, paste(x, "+", y, "=", z), paste(x, "-", y, "=", z), paste(x, "*",
        y, "=", z), paste(x, "/", y, "=", z), paste(y, "-", x, "=", z), paste(y,
        "/", x, "=", z))
}
# print multi-steps (the solution)
print_sol <- function(nums, sol, op) {
    sol <- round(sol, 3)  #Only keep 3 digits to make it better looking.
    n_nums <- length(sol)
    for (step in 1:(n_nums - 1)) {
        cat(print_op(sol[step], nums[step + 1], sol[step + 1], op[step]), "\n")
    }
}

With all the preparations, we are ready to present the final function to solve 24. In the solve_24() function, the first argument nums contains the numbers, goal is the target value with default 24, and n_sols_max represents the maximum number of solutions to search for, with a default value of 3.

solve_24 <- function(nums, goal = 24, n_sols_max = 3){
require(gtools)
n_nums <- length(nums)

nums_perm <- unique(permutations(n_nums, n_nums, nums, set = FALSE))  #generate all number permutations 

n_ops <- 6
op_mat <- permutations(n_ops, n_nums-1, repeats.allowed = TRUE) #generate all operator sequences
op_mat <- op_mat[op_mat[,1]<=4, ] #remove redundant ones
n_sols <- 0  #initialize the number of solutions to be 0
for(i in 1:nrow(nums_perm))  #loop over all possible permutations
for(j in 1:nrow(op_mat)){ #loop over all possible operator sequences
  num_cur <- nums_perm[i, ] #get the current permutation
  op_cur <- op_mat[j, ] #get the current operator sequence
  sol <- num_op(num_cur, op_cur) #get the steps
  if(abs(sol[n_nums] - goal) < 1e-5 & all(sol >= 0)){ #check if it is a solution
    n_sols <- n_sols + 1 #increase the solution counter
    cat("Solution #", n_sols, "\n")
    print_sol(num_cur, sol, op_cur) #print the solution
  } 
  if(n_sols >= n_sols_max){
    return(invisible(NULL))
  }
  }
if(n_sols == 0){ #fail to find a solution
  cat("Solution not exist!")
}

}

Now, we are reading to look at some examples.

solve_24(1:4)
#> Solution # 1 
#> 1 + 2 = 3 
#> 3 + 3 = 6 
#> 6 * 4 = 24 
#> Solution # 2 
#> 1 * 2 = 2 
#> 2 * 3 = 6 
#> 6 * 4 = 24 
#> Solution # 3 
#> 1 / 2 = 0.5 
#> 0.5 / 3 = 0.167 
#> 4 / 0.167 = 24
solve_24(c(1, 5, 5, 5))
#> Solution # 1 
#> 1 / 5 = 0.2 
#> 5 - 0.2 = 4.8 
#> 4.8 * 5 = 24
solve_24(c(3, 7, 3, 7))
#> Solution # 1 
#> 3 / 7 = 0.429 
#> 0.429 + 3 = 3.429 
#> 3.429 * 7 = 24
solve_24(c(3, 8, 3, 8))
#> Solution # 1 
#> 8 / 3 = 2.667 
#> 3 - 2.667 = 0.333 
#> 8 / 0.333 = 24
solve_24(c(2, 5, 5, 5))
#> Solution not exist!

Note that the function is more powerful than merely solving 24. It contains two extensions.

  1. The target value can be any number, for example, 25, or 100.
  2. The input can contain more or less than 4 numbers.

Let’s look at two interesting examples.

solve_24(c(12, 13, 23, 25, 25), n_sols_max = 1)
#> Solution # 1 
#> 12 + 13 = 25 
#> 25 * 23 = 575 
#> 575 + 25 = 600 
#> 600 / 25 = 24
solve_24(11:16, 100, n_sols_max = 1)
#> Solution # 1 
#> 11 * 12 = 132 
#> 132 + 13 = 145 
#> 145 - 14 = 131 
#> 131 - 15 = 116 
#> 116 - 16 = 100

There are other possible extensions of the function we wrote. For example, you can add additional possible operators (e.g. the exponentiation ^, the factorial !) by changing the cal() and print_op as well as some constants in the solve_24() function.