R - gregorymorrison/euler1 GitHub Wiki

The R language, (http://www.r-project.org/), introduced in 1993, is one of the premiere languages for statistics and data analysis. It's an open source version of the earlier S language, and it features built-in functions like stats libraries and graphing tools. What does it looks like? Here's an imperative version of Euler1, which took me around 15 minutes of blundering around to write:

# Euler1 in R

euler1 <- function(size) {
    result <- 0
    for (x in 1:size) {
        if (x %% 3 == 0 || x %% 5 == 0)
            result <- result + x
    }
    result
}

euler1(999)

Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable assignment - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). R's default recursion limit is set pretty low, so I had to increase it here.

# Euler1 in R

#Increase recursion limit
options(expressions = 10000)

myInt <- function(n) ifelse (n%%3 == 0 || n%%5 == 0, n, 0)

euler <- function(n, acc) {
    ifelse (n == 0,
        acc,
        euler(n-1, acc+myInt(n)))
}

euler1 <- function(n) euler(n, 0)

euler1(999)

R's implementation of Functional programming puts a big smile on my face. It's so straightforward and clean, it couldn't really be any simpler. First-class functions, lambdas, map, filter, reduce... everything in its right place:

# Euler1 in R

myMap    <- function(n) n
myFilter <- function(n) ifelse(n%%3 == 0 || n%%5 == 0, n, 0)
myReduce <- function(m,n) m+n

euler1 <- function(n) {
    mapped   = Map(myMap, 1:n)
    filtered = Filter(myFilter, mapped)
    Reduce(myReduce, filtered)
}

euler1(999)

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler1() returns euler1() calculated on the half of the list before the pivot element, euler1() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together. Range creation is is easy as can be, and arrays are 1-based. R returns NA for elements that don't exist in the array, so we'll need to filter out any of those with the builtin na.omit():

# Euler1 in R

#Set recursion limit
options(expressions = 150)

euler1 <- function (L) {
    len = length(L)
    piv = ceiling(len / 2)
    l = L[piv]

      # Calculate the value of the first half of the list
    pre = ifelse( 1 <= piv-1, euler1( na.omit(L[1:piv-1]) ), 0)
      # Calculate the value of the last half of the list
    post = ifelse( piv+1 <= len,
        euler1( na.omit(L[piv+1:len])), 0)
      # Calculate the value of this element
    i = ifelse( l%%3==0 || l%%5==0, l, 0)

      # Return the sum of all three
    pre + post + i
}

euler1( 1:999 )

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation.

# Euler1 in R

mySum <- function (n, size) {
    n * (ceiling(size/n)**2 + ceiling(size/n)) / 2
}

euler1 <- function (size) {
    (mySum(3,size) + mySum(5,size) - mySum(15,size))
}

euler1(999)

I didn't find R the friendliest language to work with; its error messages didn't seem that helpful. It comes with a REPL and a debugger which you'll probably find useful when orienting yourself to how R does things. To get R for Fedora, yum-install R. The language is meant to be run as an interactive console session, though it can be invoked to simply execute a script and quit. To do that, use the following arguments shown here:

$ R --no-save --slave < euler1.r
[1] 233168
$