A Scheme Code Kata

https://logicgrimoire.files.wordpress.com/2012/02/wpid-scheme-kata-paper-quilt.jpg

Reader beware! This is a meta-creature, a post about a post about a post. By way of comp.lang.scheme, the musings of the great jao (who incidentally is the Wizard behind Geiser (which is the way to Scheme with Emacs these days)), and finally, this humble blag, I present my (straight R^5RS!) solution to the Scheme kata described in the above links:

(define (plist->alist p)
  (cond ((null? p) '())
        ((symbol? (car p))
         (cons (list (car p)
                     (gather-next-batch number? (cdr p)))
               (plist->alist (cdr p))))
        (else (plist->alist (cdr p)))))

(define (gather-next-batch pred seq)
  (cond ((null? seq) '())
        ((pred (car seq))
         (cons (car seq)
               (gather-next-batch pred (cdr seq))))
        (else '())))

(Image courtesy Mélisande* under Creative Commons license.)

What is the Highest Sum of a Number Triangle?

https://logicgrimoire.files.wordpress.com/2012/02/wpid-paper-triangles.jpg

A Description of the Problem

We are given a triangle of numbers, and we are asked to write a program that computes the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

Some additional restrictions:

  • Each step can go diagonally down to the left or the right.
  • The number of rows in the triangle will be between 1 and 100, inclusive.
  • The numbers that populate the triangle are integers between 0 and 99.

(Read the original description here.)

What are our Inputs and Outputs?

Our initial input data will live in a file called triangle-input.txt, which contains the following:

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Note that the first line of the file is not part of the triangle itself; it’s there to tell us how many levels deep the triangle goes.

30

We’ll place our output in a file called triangle-output.txt, which will contain a single integer. We’ll place the names of our input and output files in the program constants INPUT_FILE and OUTPUT_FILE, respectively.

Reading the Input, Writing the Output

First, we’ll need to get the values out of triangle-input.txt and store them in a convenient structure. In this case, an array of arrays should do.

We begin by creating an empty array, tmp, which will act as a temporary storage space for the lines of triangle-input.txt.

We’ll read the lines of the file one at a time. For each line, we split the string, e.g., “1 2 3 4 5\n”, into a list, and push that line onto our array tmp.

tmp = []

File.open(INPUT_FILE, "r") do |f|
  f.lines.each do |line|
    tmp.push line.split
  end
end

Unfortunately, we’re pushing an array of strings onto tmp, since

"4 5 2 6 5\n".split

returns this:

["4", "5", "2", "6", "5"]

Therefore, we’ll take a second pass through and convert those arrays of strings into arrays of numbers. The resulting array will allow us to – finally! – begin our real work. Notice that this is a nested call to map, best read from the inside out. The value returned by the inner map is returned to the outer, with the results stored in variable tri, since the return value of map is always an array.

tri = tmp.map { |array| array.map { |elem| elem.to_i } }

We’ll wrap everything here up in a method, read_triangle_input, which will show up in the complete program listing below. We’ll also leave the write_triangle_output method for the listing; it requires little explanation.

Solving our Actual Problem

Now that the housekeeping chores are out of the way, we can jump in and begin the real work of finding the highest sum in our triangle.

We’d like to write a method, triangle_sum, which, given an array of arrays like the one we’ve just constructed, returns an integer representing the highest sum calculated on its imagined path “down through the triangle.”

Since our route through the triangle is restricted to “steps” that can “go diagonally down to the left or the right,” the most natural representation of this data is as a tree. We’ll simulate this in a crude way using an array of arrays.

The Inner Loop

Since our fundamental data structure is an array, we’ll need to choose a looping construct; we’ll stick with the “C-style” iterative constructs here since they map well onto this problem (no pun intended). We’ll use an index variable to keep track of where we are in the iteration.

Inside the loop, we want to know three things (among others):

  • Where am I?
  • Where is the element to my upper left?
  • Where is the element to my upper right?

We’ll denote the answers to these questions with the variables this, upleft, and upright in our program listing below.

Remember the problem description: Starting at the root of the tree, we’ll keep a running sum of all the numbers we’ve seen thus far on this particular path through the tree.

Visualizing Our Movement Down the Triangle

In order to solve this problem, we started with some hand-simulation of what would eventually become the final algorithm. The example below shows how it works: given where we are in the array of arrays, we look “up and to the left” and “up and to the right” of where we are. In the following diagrams, we denote our position in the algorithm with a lovely text arrow.

Index: 1

[7] <---
[3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]

When index is 1, there isn’t anything to do, since we can’t look “up” at anything. Therefore, move on.

Index: 2

[7]
[10, 15] <---  Was: [3, 8]
[8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]

When index is 2, we look up and to the left (7), and up and to the right (also 7). Each time through the loop, we create a new temporary array called next_row, in which to store the running sums. In this case, we create a new array [10, 15] by adding 7 to each of [3, 8]. We then replace the old array with the new.

Index: 3

[7]
[10, 15]
[18, 11, 16, 15] <--- Was: [8, 1, 0]
[2, 7, 4, 4]
[4, 5, 2, 6, 5]

index is now 3. We perform the same operations as above: first, create an empty array. Then, for each element in the old array [8, 1, 0], we add the value of the element (which we’ll call this in our program code) to the values of upleft and upright (these are obviously our variable names for the “up and to the left” and “up and to the right” values we’ve already mentioned). In each case we push the results of these additions onto the new temporary array. Once we’ve finished, we replace the existing array with the new, as before.

Index: 4

[7]
[10, 15]
[18, 11, 16, 15]
[20, 25, 18, 15, 20, 20] <--- Was: [2, 7, 4, 4]
[4, 5, 2, 6, 5]

Index: 5

[7]
[10, 15]
[18, 11, 16, 15]
[20, 25, 18, 15, 20, 20]
[24, 25, 30, 27, 20, 24, 21, 20] <--- Was: [4, 5, 2, 6, 5]

Result: 30

Here we show two steps more of the process, and its completion. We can easily see that 30 is the largest sum in the last array, and our answer.

We notice that the “new” interior arrays we’re creating on each turn through the loop are longer than the originals they replace, so we’re not being as efficient with memory as we’d like. At least Array expansion is an O(n) operation!

The Complete Program Listing of triangle.rb

This essay is over 1200 words long already according to wc -w. Therefore, since this algorithm can be described very succinctly in code, I’ll break the rules of literate programming and simply end with the program listing itself. Note the temporary variables next_row, this, upleft, and upright, which are described in the section “Visualizing Our Movement Down the Triangle” above.

As always, the contents of this literate program are available at Github.

(Update: better solutions and discussion over at the Ruby Reddit)

#!/usr/bin/env ruby

require 'test/unit'

INPUT_FILE  = "triangle-input.txt"
OUTPUT_FILE = "triangle-output.txt"

def read_triangle_input
  tmp = []

  File.open(INPUT_FILE, "r") do |f|
    f.lines.each do |line|
      tmp.push line.split
    end
  end

  tri = tmp.map { |array| array.map { |elem| elem.to_i } }
end

def write_triangle_output(result)
  File.open(OUTPUT_FILE, "w") do |f|
    f.print result
  end
end

def triangle_sum(tri)
  a = Array.new(tri)
  index = 1
  len = a.shift[0]-1
  while index <= len
    next_row = []
    for i in 0..index
      this = a[index][i]
      upleft = a[index-1][i-1]
      upright = a[index-1][i]

      if i == 0
        next_row.push this + upright
      elsif i == index
        next_row.push this + upleft
      else
        next_row.push this + upleft
        next_row.push this + upright
      end
    end
    a[index] = next_row
    index += 1
  end
  a[index-1].max
end

tri = read_triangle_input
highest_sum = triangle_sum(tri)
write_triangle_output(highest_sum)  

class TestTriangleSum < Test::Unit::TestCase
  def test_01
    tri = read_triangle_input
    expected = triangle_sum(tri)
    assert_equal expected, 30
  end
end

(Image courtesy Mélisande* under Creative Commons license.)

Finding the Equilibrium Index of an Array

The Problem Description

A zero-indexed array A consisting of N integers is given. An
equilibrium index of this array is any integer P such that 0 <=
P < N and the sum of elements of lower indices is equal to the sum
of elements of higher indices, i.e.,

A[0] + A[1] + ... + A[P-1] =
A[P+1] + ... + A[N-2] + A[N-1].

The sum of zero elements is assumed to be equal to 0.

Write a function that, given a zero-indexed array A consisting of
N integers, returns any of its equilibrium indices. The function
should return -1 if no equilibrium index exists.

  • Expected worst-case time complexity is O(N)
  • Expected worst-case space complexity is O(N), beyond input storage

(not counting the storage required for input arguments).

The above is taken from the problem description by Codility; they discuss one solution (written in C) here.

Notes on this Implementation

First things first: we’ll avoid the return -1 “C-ism,” as it’s more natural to return nil in Ruby. In fact, Ruby sees -1 as True, so returning it will break many common predicates, whereas nil won’t.

Experienced programmers will observe that this implementation does not meet the O(n) time and space complexity requirements as listed above. Absolute simplicity of implementation is the focus right now, but that may change in a future version.

Finally, notice that this short essay is itself a literate program, implemented using the wonderful Org-mode capabilities which are included with the Emacs text editor.

The Inner Loop

Since most of the program’s work is done inside a single while loop, we’ll begin there.

Let A be the Ruby array

[-7, 1, 5, 2, -4, 3, 0].

The equilibrium index of A can be computed by hand, so it’s a good place to start. It’s also our first test case (see below).

We’ve chosen to implement the iteration over A using a while loop rather than the more idiomatic Array#each method since we need to keep track of our current index into the array.

As we begin the loop, the variable index is initialized as the length of the array minus one. This is required because Ruby’s arrays are zero-based, but the value returned by its Array#length method is not.

while index > 0
  left  = a[0..index-1].reduce(:+)
  right = a[index+1..len].reduce(:+)
  if left == right
    return index
  end
  index -= 1
end

We’ll iterate backwards through the array from the end. At each value of index, we’ll split A into two smaller arrays, left and right. This requires allocating two new arrays in memory, reading the values of the desired “slices” of A, and copying them into left and right, respectively. This operation provides for an implementation that is simple to visualize and understand, but it’s also the reason why we fail to meet the requirements for O(n) space and time complexity. A more efficient implementation would avoid these unnecessary allocation and copying steps, and we might change this program at some point to achieve that.

Visualizing the Iteration

Let’s look at left and right at each stage of the iteration:

https://logicgrimoire.files.wordpress.com/2012/02/wpid-equi.png

We can see that when we split A at index, we always leave a “gap” in between, and it’s this gap which will provide us with the answer we seek: the equilibrium index (provided that the equilibrium index is defined for the given array, that is). At every iteration in the diagram above, we sum the values within left and right using the Array#reduce method. If left and right are equal, index is defined as the equilibrium index, and we return index. Otherwise, we’ll end up escaping the loop and returning nil.

The equi Function

Looking briefly at the entire equi function, we can see that it’s just a wrapper for the while loop. First we set the value of index and len as bookkeeping measures. We then enter the while loop as described above. If the loop completes without returning a value, the program returns to the next outer context and returns the nil value, which lets our caller know that this array doesn’t have an equilibrium index.

def equi(a)
  index = a.length-1
  len   = a.length-1
  while index > 0
    left  = a[0..index-1].reduce(:+)
    right = a[index+1..len].reduce(:+)
    if left == right
      return index
    end
    index -= 1
  end
  nil
end

Test Cases

Over the course of developing the program, a number of test cases have come to mind. We’ll begin with the given array A that we started with.

def test_random
  sample_array = [-7, 1, 5, 2, -4, 3, 0]
  expected = equi(sample_array)
  assert_equal expected, 3
end

Here we’ve defined a trivial `pyramid’ array of values that ascend and descend symmetrically.

def test_trivial_pyramid
  sample_array = [1, 2, 3, 4, 3, 2, 1]
  expected = equi(sample_array)
  assert_equal expected, 3
end

This test checks the case where the first value is equal to the sum of all the rest (save the equilibrium index, of course).

 def test_biggest_first
  sample_array = [99, 0, 66, 32, 1]
  expected = equi(sample_array)
  assert_equal expected, 1
end

Similarly, we check for the case where the last value alone is equal to the sum of left.

def test_biggest_last
  sample_array = [66, 32, 1, 0, 99]
  expected = equi(sample_array)
  assert_equal expected, 3
end

We should return nil for an array with a single element, since the equilibrium index is not defined in that case.

def test_single_element
  sample_array = [0]
  expected = equi(sample_array)
  assert_equal expected, nil
end

The same is true of an array containing a single nil.

def test_single_nil
  sample_array = [nil]
  expected = equi(sample_array)
  assert_equal expected, nil
end

The Complete Program Listing

Finally, we have the complete program listing for the tangle‘d file literate-equi.rb. Since we’ve included our tests by subclassing the Test::Unit class, Ruby will run them for us when we invoke the program. Running ruby literate-equi.rb at the command shell should return the following output:

~/Desktop/Dropbox/current/logicgrimoire $ ruby literate-equi.rb 
Loaded suite literate-equi
Started
......
Finished in 0.002195 seconds.

6 tests, 6 assertions, 0 failures, 0 errors

The program itself:

#!/usr/bin/env ruby

require 'test/unit'

def equi(a)
  index = a.length-1
  len   = a.length-1
  while index > 0
    left  = a[0..index-1].reduce(:+)
    right = a[index+1..len].reduce(:+)
    if left == right
      return index
    end
    index -= 1
  end
  nil
end


class TestEqui < Test::Unit::TestCase
  def test_random
    sample_array = [-7, 1, 5, 2, -4, 3, 0]
    expected = equi(sample_array)
    assert_equal expected, 3
  end

  def test_trivial_pyramid
    sample_array = [1, 2, 3, 4, 3, 2, 1]
    expected = equi(sample_array)
    assert_equal expected, 3
  end
   def test_biggest_first
    sample_array = [99, 0, 66, 32, 1]
    expected = equi(sample_array)
    assert_equal expected, 1
  end
  def test_biggest_last
    sample_array = [66, 32, 1, 0, 99]
    expected = equi(sample_array)
    assert_equal expected, 3
  end
  def test_single_element
    sample_array = [0]
    expected = equi(sample_array)
    assert_equal expected, nil
  end
  def test_single_nil
    sample_array = [nil]
    expected = equi(sample_array)
    assert_equal expected, nil
  end

end

First Post

https://logicgrimoire.files.wordpress.com/2012/09/wpid-sierpinski-molecule-cp.jpg

“Imagination is more important than knowledge.”
— Albert Einstein

At the age of 30, I finally started learning Calculus. If that sounds crazy to you, you’re not alone. It sounded pretty crazy to me too. It still does, in fact. I was never much good at math in school, as my transcripts would show anyone who cared to look. I failed New York State’s Course II on geometry in tenth grade, and ended up taking it again the next year. I barely passed, even the second time around — with a 68, I believe. As for Course III in trigonometry, I failed outright. In short, I was not considered one of the bright mathematical lights at my high school.

It was some years later, in college, that I discovered computers. Up to that point, I’d used them mostly to write term papers for my classes, but as time went on, I became more interested in how they worked. In my travels on the web, I stumbled across a few message boards frequented by programmers, and discovered another world. It was amazing; there were people who actually just wrote computer programs all day long. In return, people paid them money. This seemed hard to believe at the time.

I soon found out what drove these people to do what they did: it was a whole lot of fun. Before long, I was writing my own little programs. There was something really neat about giving a computer a set of instructions and then standing back and seeing what happened. Sometimes, I could get it to do what I was imagining. Most of the time, I couldn’t. Slowly, I got better at talking to the computer in ways it could understand. In its own language.

There comes a point in the life of any programmer, however, when a lack of math skills starts to really hold her back. Once I reached that point, my historical disinterest in math disappeared. I couldn’t wait to get started. I bought a book from the local bookstore that promised to “demystify” trigonometry and worked on it almost every day after work, carefully reading through descriptions of terms like “vector” and “parallax,” all the while amazed that here I was, actually doing what I never thought I could: I was teaching myself the math I never learned in school, and what’s more, I began to look forward to those sessions as the best part of my day.

Why does any of this matter? It matters because I know that there are lots of kids out there like I was. They may think they aren’t any good at math, or that it’s boring. They may even believe that they hate it. What they’re lacking is a fun way to apply it. After all, memorizing trigonometric formulas is only fun if you have a reason.

That is exactly what I aim to do with this blog: give people a reason to care about math, and help them to understand that math isn’t just about some abstract notion of “intellectual enrichment,” but that it can help us do cool things, whether we’re interested in programming computers, experimenting with model rocketry, or building our own robots.

I don’t consider myself an expert in math or programming, of course. I’m just another PC hobbyist with an itch to scratch, and in many ways, I’ve spent the last few years learning just how little I really know. That doesn’t matter — if something I write here helps even one other person out there achieve their dream, I’ll consider the time well spent.

Bottom line: whatever this strange way of thinking that makes a computer programmer is, I’m determined to keep going until I master it. It doesn’t matter how long it takes me to get there, since I consider the journey itself to be a labor of love, and it’s something that I know I will enjoy for the rest of my life.

What activities can you say that about?

(Image courtesy Melisande under Creative Commons license.)