Impression from NYC and the RC

Two months ago I was on a train going from Montreal to New York City. It’s a long ride, but I used the time on the train to triage all the coding project ideas I could work on while at the Recurse Center (RC). So many projects; so many ideas.

Today I’m on the same train heading back to Montreal and have another 10 hours to triage the thoughts, experiences, and observations about the big city and the social experiment that is RC. Here is my best shot at it—stream-of-consciousness-style—before I forget it all.

Continue reading “Impression from NYC and the RC”

No bullshit guide to programming

How does one learn to code? Students in computer science and software engineering will have a few first-year programming courses, with the first one introducing basics like variables, control flow, and loops. Autodidact programmers probably started with a tutorial somewhere, but eventually got a book on the subject. Regardless of the learner’s path, we’re talking about a book that teaches “the basics.”

Continue reading “No bullshit guide to programming”

Annual general update

It’s May. Winter is done now, so it’s time for spring cleaning! In addition to cleaning your living space, Spring is also a good time to clean out the “project plans” and focus on one or two key goals for the summer. This is what I intend to do in this post. Read on to learn about the recent developments, and the strategic plan for Minireference Co. for the coming year.

Continue reading “Annual general update”

Binary search in three languages

Hola! Regardons ensemble un peu de code. The binary_search algorithm. It will get a little technical, pero no es mucho complicado. A ver. En ingles. En anglais, parce que le code—ça va foule mieux en anglais.

Assume you’re given a array of integers sorted in increasing order [3,6,19,21,87]. You job is to write a “search” function that returns the 0-based index of query value, or -1 if val is not in array.

Binary search algorithm

The “usual” algorithm use the start and finish pointers in a weird way, which I found difficult to understand, so I wrote another one. The invariant “we’ve already checked the limits” feels more logical to me.

In JavaScript

In JavaScript the code for the binary search strategy is as follows:

SearchableArray.prototype.binary_search = function (val) {
    var data = this.data;

    if (data.length === 0) return -1;
    if (data[0] === val) return 0;
    if (data[data.length-1] === val) return data.length -1 ;

    var bin_search_limits = function(start,finish) {
        // invariant: data[start] and data[finish] have been checked already
        var mid;
        //console.log(start, finish);
        if (start === finish || start+1 === finish) 
            return -1;

        mid = start + Math.floor((finish-start)/2);

        if (data[mid]===val) {
            return mid;
        } else if (data[mid] < val) {
            return bin_search_limits(mid,finish);
        } else if (data[mid] > val) {
            return bin_search_limits(start,mid);
        }
    };
    return bin_search_limits(0, data.length-1);

};

The full javascript code (with tests;) is here.

In C

It was surprisingly easy to transform the JavaScript code into C. See the code and some basic tests here. The main functions essentially the same:

int bin_search_limits(int *data, int start, int finish, int val) {
      // invariant: data[start] and data[finish] have been checked already
      int mid;

      if (start == finish || start+1 == finish) 
          return -1;

      mid = start + (finish-start)/2;  

      if (data[mid]==val) {
          return mid;
      } else if (data[mid] < val) {
          return bin_search_limits(data,mid,finish, val);
      } else if (data[mid] > val) {
          return bin_search_limits(data,start,mid, val);
      }
  };

int binary_search(int *data, int length, int val) {
  if (length == 0) return -1;
  if (data[0] == val) return 0;
  if (data[length-1] == val) return length-1;

  return bin_search_limits(data,0,length-1, val);
};

In python

The pleasure of implementing binary search in python is left to the reader.


I’ve got to go code learn how to make a hash function to make the C test suite go faster 😉