Make 10 from the numbers 1,1,5 and 8 using the 4 operations, by brute force I tried to calculate the following problem by brute force using R (under the assumption that a single pair of parenthesis would suffice).


  Make 10 from the numbers 1, 1, 5, 8. You can use the operations + – *
  / ().  You have to use all the numbers, and use each number exactly
  once. The operations can be repeated (like 1 + 1 + 5 + 8) and you
  don’t have to use each operation.


I did the following and got the correct answer, but I would like your ideas for better ways of addressing that problem.

## Helper functions for inserting characters into strings
# http://stackoverflow.com/questions/13863599/insert-a-character-at-a-specific-location-in-a-string/25416334#25416334

  split_str_by_index &lt;- function(target, index) {
    index &lt;- sort(index)
    substr(rep(target, length(index) + 1),
           start = c(1, index),
           stop = c(index -1, nchar(target)))
  }

  #Taken from https://stat.ethz.ch/pipermail/r-help/2006-March/101023.html
  interleave &lt;- function(v1,v2)
  {
    ord1 &lt;- 2*(1:length(v1))-1
    ord2 &lt;- 2*(1:length(v2))
    c(v1,v2)[order(c(ord1,ord2))]
  }

  insert_str &lt;- function(target, insert, index) {
    insert &lt;- insert[order(index)]
    index &lt;- sort(index)
    paste(interleave(split_str_by_index(target, index), insert), collapse="")
  }

  # insert_str("1+1+5+8", c("(", ")"), c(2, 3))

  #################

  library(gtools)
  library(dplyr)

  symbols &lt;- expand.grid(data.frame(matrix(rep(c("+","-","*","/"),3),ncol=3)))

  numbers &lt;- unique(permutations(4,4,c(1,1,5,8),set=FALSE))

  # Insert symbols between the numbers
  lst &lt;- lapply(1:nrow(numbers) , function(i) mapply(paste0,numbers[i,],symbols))
  res1 &lt;- data.frame(do.call(rbind, lst))


  # paste strings omitting the trailing symbol
  res2 &lt;- res1 %&gt;%
    transmute(expr=do.call(paste0,.)) %&gt;%
    transmute(expr=substr(expr,1,7))

  # positions of opening and closing bracket
  x&lt;-expand.grid(c(1,3,5),c(4,6,8))
  x&lt;-x[x[1]&lt;x[2]-1,]

  # Generate x rows for each row of res2
  res3 &lt;- as.data.frame(matrix(rep(NA,nrow(res2)*nrow(x)),ncol=1))
  for (i in seq(nrow(res2))){
    temp &lt;- res2[i,]
    res3[((i-1)*nrow(x)+1):(i*nrow(x)),] &lt;- sapply(1:6, function(j) insert_str(temp,c("(", ")"),x[j,]))
  }

  res3  %&gt;%
    rowwise() %&gt;%
    mutate(result=eval(parse(text=V1))) %&gt;%
    filter(result==10)
I like your code but don't have a solution that improves on brute force. Just a few comments:

(1) You can eliminate your for loop assigning to res3 like so:

res3 = data.frame(V1 = unlist(lapply(res2$expr, function(temp) sapply(1:6, function(j) insert_str(temp,c("(", ")"),x[j,])))))


Whether this is a good idea is debatable, but it's slightly faster when I test it as compared to the for loop (a difference of about 10%). Perhaps lapply would become more advantageous as you increased the number of digits or operations to be explored.

(2) The obvious speed-related comment is to use data.table. This is another change that will more noticeably improve performance as you move to a larger-scale problem since you can benefit from the in-place operations.

(3) You are working with a manageable set of numbers here, but in the future you might want to seek solutions in parts. For example, check half the possibilities and only check the other half if you don't find a solution. Similarly, you don't have to assume there's only one set of parentheses but could make the choice to check the second set if your first search yielded no results.

(4) When you know the numbers in advance or you're coding to a specific set of numbers, it might be helpful to eliminate all rows that have a certain combo that couldn't possibly be in a correct answer. For example, I'd get rid of anything with 8*5 or 5*8 since nothing you can do with the 1's can bring that expression down to anything close to 10. Similarly I'd get rid of anything with 1/1 and 1*1 since these also can't lead to a solution.  Doing this would eliminate 1152 out of 4608 possibilities. (Note that I'm relying on standard order of operations rules.) 



I don't feel any of these comments are super helpful but wanted to write since I enjoyed reading your code and since Code Review doesn't always give much feedback to us R users. Hopefully others will add more interesting things.