advent_1.R

fun_for <- function(x, target, n) {
  if (!n %in% c(2, 3)) stop("The accounting Elves are crazy!")
  if (n == 2) {
    out <- x[(target - x) %in% x]
  } else if (n == 3) {
    out <- numeric(0)
    for (i in seq_along(x)) {
      s1 <- x + x[i]
      for (j in seq_along(s1)) {
        s2 <- s1 + x[j]
        if (any(s2 == target)) out <- c(out, x[which(s2 == target)])
      }
    }
    out <- unique(out)
  }
  out
}

fun_eg <- function(x, target, n) {
  a <- expand.grid(replicate(n, x, FALSE))
  unlist(a[rowSums(a) == target, ][1, ], use.names = FALSE)
}

fun_cj <- function(x, target, n) {
  a <- do.call(data.table::CJ, replicate(n, x, FALSE))
  unlist(a[rowSums(a) == target, ][1, ], use.names = FALSE)
}

fun_combn <- function(x, target, n) {
  all_combinations <- combn(x, n)
  all_combinations[, colSums(all_combinations) == target]
}

fun_RcppAlgos <- function(x, target, n) {
  a <- RcppAlgos::comboGeneral(x, n)
  a[which(rowSums(a) == target), ]
}

x <- c(1956, 1994, 457, 1654, 2003, 1902, 1741, 1494, 1597, 1129, 
       1146, 1589, 1989, 1093, 1881, 1288, 1848, 1371, 1508, 1035, 1813, 
       1335, 1634, 1102, 1262, 1637, 1048, 1807, 1270, 1528, 1670, 1803, 
       1202, 1294, 1570, 1640, 1484, 1872, 1140, 1207, 1485, 1781, 1778, 
       1772, 1334, 1267, 1045, 1194, 1873, 1441, 1557, 1414, 1123, 1980, 
       1527, 1591, 1665, 1916, 1662, 1139, 1973, 1258, 1041, 1134, 1609, 
       1554, 1455, 1124, 1478, 1938, 1759, 1281, 1410, 1511, 930, 1319, 
       1302, 1827, 1216, 1404, 1460, 2002, 1590, 1817, 1341, 1631, 1608, 
       1382, 1158, 1594, 1049, 1804, 1555, 1753, 447, 1021, 1079, 609, 
       1766, 1327, 1851, 1052, 1737, 1175, 1043, 1945, 1573, 1113, 1724, 
       1203, 1856, 1682, 1623, 1135, 1015, 1423, 1412, 1315, 1375, 1895, 
       1351, 1530, 1758, 1445, 1518, 1819, 1567, 1305, 1919, 1952, 1432, 
       1099, 1476, 1883, 1871, 1900, 1442, 1393, 1214, 1283, 1538, 1391, 
       1008, 1109, 1621, 1876, 1998, 1032, 1324, 1927, 481, 1732, 1370, 
       1683, 1199, 1465, 1882, 1293, 1671, 1456, 1197, 1506, 1381, 1469, 
       1830, 1957, 1850, 1184, 1564, 1170, 1943, 1131, 1867, 1208, 1788, 
       1337, 1722, 1760, 1651, 1069, 1574, 1959, 1770, 66, 1190, 1606, 
       1899, 1054, 980, 1693, 1173, 1479, 1333, 1579, 1720, 1782, 1971, 
       1438, 1178, 1306)

set.seed(1)
y <- c(x, sample(2020:2030, 200, TRUE))
system.time(fun_combn(x, 2020, 3))
##    user  system elapsed 
##   1.014   0.000   1.014 
system.time(fun_combn(y, 2020, 3))
##    user  system elapsed 
##   7.731   0.076   7.807 

## check = FALSE because the combn approach returns results
## in the reverse order of the other approaches
bench::mark(fun_for(x, 2020, 2), 
            fun_eg(x, 2020, 2), 
            fun_cj(x, 2020, 2), 
            fun_combn(x, 2020, 2),
            fun_RcppAlgos(x, 2020, 2), 
            check = FALSE)
## # A tibble: 5 x 13
##   expression                     min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc
##   <bch:expr>                <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>
## 1 fun_for(x, 2020, 2)         8.83µs   9.88µs   95133.     9.37KB     9.51  9999     1
## 2 fun_eg(x, 2020, 2)          1.71ms   1.89ms     521.      2.6MB    11.0    236     5
## 3 fun_cj(x, 2020, 2)          2.02ms   2.23ms     432.     1.89MB     6.36   204     3
## 4 fun_combn(x, 2020, 2)      13.11ms  14.44ms      69.7  622.07KB     9.62    29     4
## 5 fun_RcppAlgos(x, 2020, 2) 241.61µs 261.25µs    3632.   627.05KB    15.7   1622     7
## # … with 5 more variables: total_time <bch:tm>, result <list>, memory <list>, time <list>,
## #   gc <list>


bench::mark(fun_for(y, 2020, 2), 
            fun_eg(y, 2020, 2), 
            fun_cj(y, 2020, 2), 
            fun_combn(y, 2020, 2), 
            fun_RcppAlgos(x, 2020, 2), 
            check = FALSE)
## # A tibble: 5 x 13
##   expression                     min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc
##   <bch:expr>                <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>
## 1 fun_for(y, 2020, 2)        15.11µs  16.52µs   57629.     18.4KB     5.76  9999     1
## 2 fun_eg(y, 2020, 2)          5.55ms   5.89ms     168.     10.4MB    17.0     69     7
## 3 fun_cj(y, 2020, 2)         12.62ms  15.77ms      66.7    8.68MB     9.53    28     4
## 4 fun_combn(y, 2020, 2)      57.13ms  57.76ms      17.3    2.44MB    17.3      4     4
## 5 fun_RcppAlgos(x, 2020, 2) 241.08µs 264.03µs    3623.   627.05KB    18.2   1596     8
## # … with 5 more variables: total_time <bch:tm>, result <list>, memory <list>, time <list>,
## #   gc <list>

bench::mark(fun_for(x, 2020, 3), 
            fun_eg(x, 2020, 3), 
            fun_cj(x, 2020, 3), 
            fun_combn(x, 2020, 3),
            fun_RcppAlgos(x, 2020, 3), 
            check = FALSE)
## # A tibble: 5 x 13
## expression                     min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc
## <bch:expr>                <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>
##   1 fun_for(x, 2020, 3)        52.47ms  71.25ms    15.1      95.5MB     9.46     8     5
## 2 fun_eg(x, 2020, 3)        687.34ms 687.34ms     1.45    702.1MB     5.82     1     4
## 3 fun_cj(x, 2020, 3)        474.86ms 479.16ms     2.09    488.3MB     4.17     2     4
## 4 fun_combn(x, 2020, 3)        1.14s    1.14s     0.879    50.1MB     7.03     1     8
## 5 fun_RcppAlgos(x, 2020, 3)  21.87ms   22.5ms    35.5      50.1MB     3.95    18     2
## # … with 5 more variables: total_time <bch:tm>, result <list>, memory <list>, time <list>,
## #   gc <list>