Skip to content

Instantly share code, notes, and snippets.

@elben
Last active September 15, 2015 01:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save elben/67db0bee7ad6128969a5 to your computer and use it in GitHub Desktop.
Save elben/67db0bee7ad6128969a5 to your computer and use it in GitHub Desktop.
Fundamental programming exercises. Happens to be in Ruby.

This is a principled approach to programming. We use Ruby as the delivery language, but the things you learn here applies to all programming languages. What you learn will be important in your day-to-day Ruby programming, but my primary goal is for you to understand common, important concepts of computation.

Ruby made unfortunate mistakes in its design—mistakes that we Ruby programmers have to deal with on a daily basis. Of course, we get used to those mistakes and start to think of them as "features" or "that's just how those things work." I will often "ignore" those mistakes at first so that you will understand the fundamental idea. The mistakes are edge cases that we have to worry about, but they should not get in your way of learning. Hence why some people (mainly people with exposure to Ruby) will consider the order of things very odd.

Type the examples into IRB and complete every exercise. Merely reading will not give you true understanding.

Important vocabulary are in bold.

1. Functions

Let's go back to elementary school math. We are used to math functions like f(x) = x + 1. We know that f(0) = 1, f(1) = 2, and so on. f is the function name, and it takes one argument named x.

In Ruby, this looks like:

# In math: f(x) = x + 1
f = ->(x) { x + 1 }

# In math: f(0)
f.call(0)
# => 1

# In math: f(1)
f.call(1)
# => 2

If you have any prior knowledge of Ruby, the syntax above may seem weird. Understand the syntax, but let's focus on the concepts. What you have to realize is that a function is a thing that takes arguments and returns new values. You apply a function by giving it its arguments (e.g. f(0) is the application of f to its argument 0).

In the case of f(x) = x + 1, the function takes a number and increments it by one. Note I could have named the function anything. In high school math, we often use f, but I could have as easily written potatoes(x) = x + 1. The name is separated from what the function actually does.

Here is an anonymous function (so-called anonymous because it is un-named; to describe it in English, you would say "the function that adds one to the argument"):

->(x) { x + 1 }

We can use the function, just like before:

(->(x) { x + 1 }).call(0)
# => 1

Or consider this function with two arguments: f(x,y) = x^2 + y. In Ruby:

f = ->(x,y) { x * x + y }

f.call(2,10)
# => 14

(->(x,y) { x * x + y }).call(2,10)
# => 14

Exercises

Exercise 1.1. Implement the function f(x,y,z) = (x * y) + y + (z - x).

Exercise 1.2. Implement the function g(x,y) = f(x,y,x) + x, where f(x,y,z) = (x * y) + y + (z - x).

Exercise 1.3. Implement the function h(f,g,x) = f(x) + g(x), where f and g are also functions. Example:

f = ->(x) { x * 10 }
g = ->(x) { x * 100 }

h.call(f, g, 3)
# => 330

# We turn `f` and `g` into anoymous functions:
h.call(->(x) { x * 10 }, ->(x) { x * 100 }, 3)
# => 330

2. Variables

In mathematics, we know variables as a way to name things like numbers and functions. In the section above, we use f and g to name our functions. Think of f and g as variables. In reality, Ruby does not consider them as regular Ruby variables, but they are. Ruby made a mistake.

Another way to think about variables is this analogy: a variable named f is a box with a big fat f written on it. The box starts empty, and you can put stuff in the box. For example:

f = 1

Above, we put 1 in the box marked f. What about this:

f = ->(x) { x + 1 }

Of course, we have seen this before. Here, we put the function ->(x) { x + 1 } in the box marked f (overriding the previous thing in the box).

But what about the x? That is also a variable! But note that x lives only in the function. Just like in math, when you see f(x) = x + 1, and you calculate f(0) for your (very easy) exam, you don't go home and still think that x = 0. Observe:

f = ->(x) { x + 1 }

f.call(0)
# => 1

x
# ERROR!

We call this idea scoping. Variables should only be scoped to the context that makes sense for them, namely the code body they are in. Ruby screws this up in some places, but we will ignore those for now.

Aside: Methods in Ruby

So I have been calling things like f = ->(x) { x + 1 } functions. In Ruby, you mostly see the other way of defining functions (also called methods) like this (if you have prior Ruby knowledge, this is what you're probably familiar with):

def f(x)
  x + 1
end

f(0)
# => 1

def g(x, y)
  x * x + y
end

g(2,10)
# => 14

I put off these "regular" Ruby methods because Ruby got it wrong. Ruby, in its internals, differentiates anonymous functions with named methods. Many languages do not, and it is better for you to think of functions as un-named entities. Think of methods as a special form of functions that gets the special def syntax.

One unfortunate thing about "regular" Ruby methods is that when you name a method, the name you choose is not a regular variable. It is a special "method" variable. For example:

f = 100

def f(x)
  x + 1
end

f
# => 100

f(0)
# => 1

This is for the worse.

Exercises

Exercise 2.1. Consider this:

f = ->(x) { x + 1 }
g = f
h = g

g and h are variables. What's in their box? Does g and h hold copies of the function ->(x) { x + 1 }?

It turns out, they don't hold copies. All three variables point to the same function. This is where the box analogy falls down. In pictures, what's happening is this:

    +---+ +---+ +---+
    | f | | g | | h |
    +---+ +---+ +---+
      |     |     |
       \    |    /
        \   |   /
         v  v  v
   +-----------------+
   | ->(x) { x + 1 } |
   +-----------------+

Now, let's re-consider the snippet of code:

f = ->(x) { x + 1 }
g = f
h = g

i = ->(x) { x - 1 }
h = i

What is h.call(0)? What is g.call(0)?

Exercise 2.2. Write a function that takes three arguments: two functions and one number. This function should then apply the first function to the number, and apply the second function to the result. In math, this may look like:

h(f,g,x) = f(g(x))
f(x) = x + 1
g(x) = x + 2

h(f,g,0) = 3

In Ruby:

h = ->(f,g,x) { fill in the blank }

f = ->(x) { x + 1 }
g = ->(x) { x + 2 }

h.call(f,g,0)
# => 3

3. Strings

We have seen how integers work, above. It is a data type for whole numbers. Another data type is a string. A string is a sequence of characters. In Ruby, you can create strings like this:

"Hello world"

You can also "add" strings together, just like numbers:

"Hello " + "world"

This returns a new string, namely "Hello world".

Exercises

Exercise 3.1. Write a function named repeat3 that takes a string a repeats it three times. Your function should do this:

repeat3("Hello")
# => "HelloHelloHello"

Exercise 3.2. Write a function that takes a string a repeats it three times, adding a comma-and-space between each repetition, and end with a period. Example:

repeat3("Hello")
# => "Hello, Hello, Hello."

4. Arrays

An array is a list of boxes that you can put things into.

[1, 2, 3]
[1, "Hello", 3]
[]

You can "add" arrays together, returning a new array:

[1, 2, 3] + [4, 5]
# => [1, 2, 3, 4, 5]

[] + []
# => []

You can also reverse an array:

[1, 2, 3].reverse
# => [3, 2, 1]

What is up with the [1, 2, 3].reverse syntax? "Under the hood", think of it like this, the Ruby language provides a function called reverse_array that takes one argument, an array, and reverses it: reverse_array([1, 2, 3]).

Exercises

Exercise 4.1. Following the same pattern as above, reverse a string.

Exercise 4.2. Write a function that takes two arrays, adds them together, and reverses them. Example:

add_and_reverse([1,2,3], [4,5,6])
=> [6,5,4,3,2,1]

5. Equality

In mathematics, if x = 3 and y = z = 3, are x = y = z?

We have a similar concept of equality in programming. In mathematics, we use = to denote equality. In Ruby, we use == (because x = 3 is taken; it assigns 3 to the variable x).

For example, to ask whether numbers equal each other:

1 == 1
# => true

1 == 2
# => false

Notice that Ruby returns true or false when you "ask" if two things are equal. More examples:

"hello" == "hello"
# => true

1 + 2 == 3
# => What should this return? Think.

"hello " + "world" == "hello world"
# => What should this return? Think.

[1,2,3] == [1,2,3]
# => true

[1,2,3].reverse == [1,2,3]
# => false

[1,2,3].reverse + [1,2,3] == [3,2,1,1,2,3]
# => What should this return? Think.

Exercises

Exercise 5.1. Write a function that takes two arrays. Check to see if the reverse of the first array is equal to the second array. Example:

equal_reversed?([1,2,3],[1,2,3])
# => false

equal_reversed?([1,2,3],[3,2,1])
# => true

equal_reversed?([1,2,3]+[4,5,6],[3,2,1,4,5,6])
# => What should this return?

Note that in Ruby, function names can end with a ?. It is common practice to append an ? to functions that return boolean values (true or false).

6. Conditionals

In your high school math, you learned about piecewise functions, or functions that require some conditional logic. Here's an example:

f(x) = 0 if x < 3
       1 if x = 3
       2 if x = 4
       3 otherwise

We can do the same thing in Ruby.

def f(x)
  if x < 3
    0
  elsif x == 3
    1
  elsif x == 4
    2
  else
    3
  end
end

Exercises

Exercise 6.1. Write a method that takes three arguments: two functions and an integer. If the results of applying the integer to the two functions are equal, return the string "they're the same!". Otherwise, return "they differ". Example:

def compare(f,g,x)
  # Your code here
end

compare(->(x) { x + 1 ], ->(x) { x + 1 }, 3)
# => "they're the same!"

compare(->(x) { x + 2 ], ->(x) { x + 1 }, 3)
# => "they differ"

Exercise 6.2. Write a method that takes two arguments: a function and an integer. If the integer is greater than 10, return that integer unchanged. Otherwise, apply the given function and return the value. Example:

def apply_only_if_small(f,x)
  # Your code here
end

f = ->(x) { x * 1000 }

apply_only_if_small(f, 11)
# => 11

apply_only_if_small(f, 9)
# => 9000

Exercise 6.3. Write a method that takes one argument, an integer. The function should return true if the integer is less than 10. Return false otherwise. Do not use an if statement. Your function body should be only a single line, without using semi-colons. Example:

def less_than_10?(x)
  # Write your single line of code here
end

less_than_10?(10)
# => false

less_than_10?(4)
# => true
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment