Author Archives: Jason Swett

My Second Attempt at a Genetic Algorithm

Leave a reply

In my previous post I tried to create a genetic algorithm (GA). The idea was that the GA would slap together some numbers and symbols to try to hit a target number. For example, some conceivable expressions would be 5 + 9, 5 * 2 or even something halfway nonsensical like - - 3.

I was able to write a program that would generate these random expressions and see if their results hit my target number. For example, if my target number was 15, an expression of 3 * 5 would be recognized as a success and my program would stop executing. This was mildly amusing but it was not yet a genetic algorithm. I hadn’t yet fully understood what my GA was supposed to be.

The crucial thing my GA was missing was some form of evolution via sexual reproduction and/or mutation. What I needed was a program that would create a generation of chromosomes, then let that generation create a new generation of fitter offspring, then let that new generation create yet another generation of even fitter offspring, and so on. In this particular case, fitness would be determined by how close each chromosome got to the target number.

After some fiddling I arrived at the following bit of code.

class Chromosome
  GENE_MAP = {
    '0000' => '0',
    '0001' => '1',
    '0010' => '2',
    '0011' => '3',
    '0100' => '4',
    '0101' => '5',
    '0110' => '6',
    '0111' => '7',
    '1000' => '8',
    '1001' => '9',
    '1010' => '+',
    '1011' => '-',
    '1100' => '*',
    '1101' => '/',
  }

  GENE_LENGTH = 4
  GENE_COUNT = 8
  TARGET_NUMBER = 100
  CHROMOSOME_LENGTH = GENE_COUNT * GENE_LENGTH

  attr_accessor :encoding

  def initialize(encoding = nil)
    if encoding
      @encoding = encoding
    else
      @encoding = CHROMOSOME_LENGTH.times.collect { rand(2) }.join
    end
  end

  def expression
    pattern = /.{#{GENE_LENGTH}}/

    self.encoding.scan(pattern).collect { |gene|
      GENE_MAP[gene]
    }.join(' ')
  end

  def result
    eval_expression(self.expression)
  end

  def fitness_score
    return unless self.result
    1 / ((TARGET_NUMBER - self.result).abs + 1).to_f
  end

  def first_part_of_encoding(grab_length)
    @encoding[0..(grab_length - 1)]
  end

  def second_part_of_encoding(grab_length)
    @encoding[grab_length..(CHROMOSOME_LENGTH - 1)]
  end

  def mate_with(chromosome)
    grab_length = rand(1..(GENE_COUNT - 1)) * GENE_LENGTH

    self.class.new(
      first_part_of_encoding(grab_length) +
      chromosome.second_part_of_encoding(grab_length)
    )
  end
end

class Generation
  GENERATION_SIZE = 30
  attr_accessor :chromosomes

  def initialize(chromosomes = [])
    number_of_attempts = 0
    @chromosomes = chromosomes

    if chromosomes.any?
      return
    end

    while number_of_attempts <= GENERATION_SIZE
      chromosome = Chromosome.new

      if chromosome.result
        number_of_attempts += 1
        @chromosomes << chromosome
      end
    end

    @chromosomes.sort_by!(&:fitness_score).reverse!
  end

  def fittest
    @chromosomes.first
  end

  def reproduce
    chromosomes = @chromosomes.drop(1).collect { |chromosome|
      [fittest.mate_with(chromosome), chromosome.mate_with(fittest)]
    }.flatten
     .select { |c| c.result != nil }
     .sort_by!(&:fitness_score)
     .reverse![0..(GENERATION_SIZE - 1)]

    Generation.new(chromosomes)
  end
end

def print_generation(generation)
  generation.chromosomes.each do |chromosome|
    print "#{chromosome.encoding} | "
    print "#{chromosome.expression.ljust(20, ' ')}| "
    print "#{chromosome.result.to_s.rjust(4, ' ')} | "
    print "#{chromosome.fitness_score.to_s.rjust(4, '  ')}"
    puts
  end

  nil
end
alias :pg :print_generation

def eval_expression(expression)
  begin
    value = eval(expression)

    if value.is_a? Numeric
      value
    else
      nil
    end
  rescue SyntaxError, NoMethodError, ZeroDivisionError, TypeError
    nil
  end
end

Here’s the first generation of chromosomes my program created.

10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304          
10001100100010110011110101011111 | 8 * 8 - 3 / 5       |   64 | 0.02702702702702703           
10101110010111101110110011110111 | +  5   *  7         |   35 | 0.015151515151515152          
01001100001011111100101110110011 | 4 * 2  * - - 3      |   24 | 0.012987012987012988          
01101110110000101111101010011111 | 6  * 2  + 9         |   21 | 0.0125                        
01011010101110111001101110110110 | 5 + - - 9 - - 6     |   20 | 0.012345679012345678          
10001010010110111011011110110011 | 8 + 5 - - 7 - 3     |   17 | 0.011904761904761904          
11101111101011101010100010101000 |   +  + 8 + 8        |   16 | 0.011764705882352941          
00111101101001111010010010101001 | 3 / + 7 + 4 + 9     |   13 | 0.011363636363636364                                                                                                         
01101110111011111111110010100010 | 6     * + 2         |   12 | 0.011235955056179775                                                                                                         
10011010010110110101111110100011 | 9 + 5 - 5  + 3      |   12 | 0.011235955056179775                                                                                                         
01111110101000011111111011000100 | 7  + 1   * 4        |   11 | 0.011111111111111112                                                                                                         
01111011111010101010011010101001 | 7 -  + + 6 + 9      |   10 | 0.01098901098901099                                                                                                          
10001010111000001100111110011110 | 8 +  0 *  9         |    8 | 0.010752688172043012                                                                                                         
01111010111000011110111011010100 | 7 +  1   / 4        |    7 | 0.010638297872340425                                                                                                         
10001111101100011010001010110100 | 8  - 1 + 2 - 4      |    5 | 0.010416666666666666                                                                                                         
00111010111111100111111011000000 | 3 +   7  * 0        |    3 | 0.01020408163265306                                                                                                          
10111010001011010111101011110010 | - + 2 / 7 +  2      |    1 | 0.01                                                                                                                         
11111010000011011011001111010111 |  + 0 / - 3 / 7      |    0 | 0.009900990099009901                                                                                                         
11110001110101001101010011010110 |  1 / 4 / 4 / 6      |    0 | 0.009900990099009901                                                                                                         
00111111111111010101110110110110 | 3   / 5 / - 6       |    0 | 0.009900990099009901          
01101111110111101010111110001111 | 6  /  +  8          |    0 | 0.009900990099009901          
10110001110010110001111110110010 | - 1 * - 1  - 2      |   -1 | 0.00980392156862745           
00111010010010101011100110100000 | 3 + 4 + - 9 + 0     |   -2 | 0.009708737864077669          
00111101111000101101010010110100 | 3 /  2 / 4 - 4      |   -4 | 0.009523809523809525          
10100001101011100111110010110001 | + 1 +  7 * - 1      |   -6 | 0.009345794392523364          
10001101011010111010111010011110 | 8 / 6 - +  9        |   -8 | 0.009174311926605505          
01011100000111001001110110110011 | 5 * 1 * 9 / - 3     |  -15 | 0.008620689655172414
01001010010010110100111011001001 | 4 + 4 - 4  * 9      |  -28 | 0.007751937984496124
01101101001111101011011011000111 | 6 / 3  - 6 * 7      |  -40 | 0.0070921985815602835
11111001110010110110111110110010 |  9 * - 6  - 2       |  -56 | 0.006369426751592357

The columns are 1) the chromosome encoding, 2) the expression, 3) the expression’s result, and 4) the chromosome’s fitness score. The fitness score is determined by how close the result is to the target number. Since my target number in this case is 100 and the top chromosome spit out 68, the score in this case is 1 / ((100 – 68) + 1) = 0.0303. (You can see that a result of 100 would be 1 / ((100 – 100) + 1) = 1)

The way the next generation is created is to take the fittest chromosome (8 / 1 * 8 + 4) and let it bang all the other chromosomes to produce offspring. Here’s the result from that:

10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571           
10001101000111001000101010101000 | 8 / 1 * 8 + + 8     |   72 | 0.034482758620689655          
10001101000111001000101011100111 | 8 / 1 * 8 +  7      |   71 | 0.03333333333333333           
10001101000111001000101011100111 | 8 / 1 * 8 +  7      |   71 | 0.03333333333333333           
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304          
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304          
10001101000111001000101011100010 | 8 / 1 * 8 +  2      |   66 | 0.02857142857142857           
10001100100010110011101011100100 | 8 * 8 - 3 +  4      |   65 | 0.027777777777777776          
10001101000111001000101010110011 | 8 / 1 * 8 + - 3     |   61 | 0.025                         
10001101000111001000101010110011 | 8 / 1 * 8 + - 3     |   61 | 0.025                         
10001101000111001010011010101001 | 8 / 1 * + 6 + 9     |   57 | 0.022727272727272728          
01101101000111001000101011100100 | 6 / 1 * 8 +  4      |   52 | 0.02040816326530612           
01101101000111001000101011100100 | 6 / 1 * 8 +  4      |   52 | 0.02040816326530612           
01011100000111001001101011100100 | 5 * 1 * 9 +  4      |   49 | 0.019230769230769232          
00111010010011001000101011100100 | 3 + 4 * 8 +  4      |   39 | 0.016129032258064516          
00111010111111100111111011000100 | 3 +   7  * 4        |   31 | 0.014285714285714285          
10100001101011100111110011100100 | + 1 +  7 *  4       |   29 | 0.013888888888888888          
00111101000111001000101011100100 | 3 / 1 * 8 +  4      |   28 | 0.0136986301369863            
00111111111111001000101011100100 | 3   * 8 +  4        |   28 | 0.0136986301369863            
10001010010110111011011110110011 | 8 + 5 - - 7 - 3     |   17 | 0.011904761904761904          
10001010010110111011011110110100 | 8 + 5 - - 7 - 4     |   16 | 0.011764705882352941          
10001101000111111111110010100010 | 8 / 1   * + 2       |   16 | 0.011764705882352941          
10001101101001111010010010101001 | 8 / + 7 + 4 + 9     |   14 | 0.011494252873563218          
10011010010110110101101011100100 | 9 + 5 - 5 +  4      |   13 | 0.011363636363636364          
10001110101000011111111011000100 | 8  + 1   * 4        |   12 | 0.011235955056179775          
11101111000111001000101011100100 |   1 * 8 +  4        |   12 | 0.011235955056179775          
01011010101110111001101111100100 | 5 + - - 9 -  4      |   10 | 0.01098901098901099           
10101110010111101110101011100100 | +  5   +  4         |    9 | 0.010869565217391304          
10001101000110110011110101011111 | 8 / 1 - 3 / 5       |    8 | 0.010752688172043012          
01111010111000011110111011010100 | 7 +  1   / 4        |    7 | 0.010638297872340425

As you can see, the average fitness has gone up. The fittest member of this generation is also fitter than the fittest member of the previous generation. Let’s run it again.

10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010101000 | 8 / 1 * 8 + + 8     |   72 | 0.034482758620689655
10001101000111001000101011100111 | 8 / 1 * 8 +  7      |   71 | 0.03333333333333333
10001101000111001000101011100111 | 8 / 1 * 8 +  7      |   71 | 0.03333333333333333
10001100100010110011101010011110 | 8 * 8 - 3 + 9       |   70 | 0.03225806451612903
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100100 | 8 / 1 * 8 +  4      |   68 | 0.030303030303030304
10001101000111001000101011100010 | 8 / 1 * 8 +  2      |   66 | 0.02857142857142857
10001101000111001000101010110011 | 8 / 1 * 8 + - 3     |   61 | 0.025
10001101000111001000101010110100 | 8 / 1 * 8 + - 4     |   60 | 0.024390243902439025
10001101000111001000101111100100 | 8 / 1 * 8 -  4      |   60 | 0.024390243902439025
01101101000111001000101010011110 | 6 / 1 * 8 + 9       |   57 | 0.022727272727272728
10001101000111001010011010101001 | 8 / 1 * + 6 + 9     |   57 | 0.022727272727272728
10101110010111001000101010011110 | +  5 * 8 + 9        |   49 | 0.019230769230769232
01011100000111001000101010011110 | 5 * 1 * 8 + 9       |   49 | 0.019230769230769232
01011101000111001000101010011110 | 5 / 1 * 8 + 9       |   49 | 0.019230769230769232

This time the fittest member is no fitter than the fittest member of the previous generation but the average fitness has gone up. If we run the code again, all the chromosomes end up with equal fitness.

10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001100000111001000101010011110 | 8 * 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571
10001101000111001000101010011110 | 8 / 1 * 8 + 9       |   73 | 0.03571428571428571

At this point no more evolution is possible without mutation, and since my program doesn’t involve mutation, no more evolution is possible with my program. So 73 is as close to 100 as we’re going to get on this try.

What Next?

I originally embarked upon this exercise because I had been vaguely curious for years about how GAs work. This exercise has given me enough understanding to satisfy that curiosity.

I can imagine some interesting places to go next. First, it seems like a flaw that there’s a less-than-100% chance of my program generating a 100%-fit chromosome for this relatively simple case. Maxing out at 73 seems like a pretty weak result.

Second, it would be interesting to apply a GA to something more entertaining than finding a number close to 100. It would be cool to hook a GA up to some sort of physics engine and create organisms that walk or slither or swim.

My First Attempt at a Genetic Algorithm

1 Reply

What Led Up to This

I’ve been vaguely interested in AI for a long time but I’ve never really done anything with it. I remember in 2008 or so a co-worker mentioned something to me called “genetic algorithms”. That sounded interesting to me.

As someone who’s also interested in biology and paleontology I’m intrigued by the idea of creating little virtual organisms that somehow reproduce and evolve on their own, creating new lifeforms that the programmer could not have anticipated.

I realize that the image conjured up by my mind is not exactly a typical application of genetic programming. But that’s the image that makes the idea appealing to me.

My Program

Well, finally, about ten years later, I’ve decided to finally mess around with genetic algorithms. I somehow stumbled upon a great tutorial called Genetic Algorithms in Plain English which I’ve decided to use as the basis for my work.

I’ll let you read the tutorial if you want the full background but I’ll also provide a little bit of background here. And before I proceed, I should let you know that I have absolutely no idea what I’m doing. So don’t take anything I say here as fact.

I decided to program my genetic algorithm in Ruby. I didn’t want to have to learn genetic algorithms and some new programming language on top of each other, so I decided to use a language I was already quite comfortable with.

The idea with this program is that it will generate an expression and the goal is for the expression to add up to the number 15.

The expression my program generates could be something valid like 3 + 2 or 8 * 3, or it could be something invalid like / + 9 or even * /. If the expression is valid, it gets evaluated and the result is checked to see if it’s 15. If the expression is not valid, it gets skipped.

Here’s the content of my program.

CHARACTER_MAP = {
  '0000' => '0',
  '0001' => '1',
  '0010' => '2',
  '0011' => '3',
  '0100' => '4',
  '0101' => '5',
  '0110' => '6',
  '0111' => '7',
  '1000' => '8',
  '1001' => '9',
  '1010' => '+',
  '1011' => '-',
  '1100' => '*',
  '1101' => '/',
}

TARGET_NUMBER = 15

def random_binary_string
  12.times.collect { rand(2) }.join
end

def binary_string_into_expression(starting_string)
  starting_string.scan(/.{4}/).collect { |character_string|
    CHARACTER_MAP[character_string]
  }.join(' ')
end

def eval_expression(expression)
  begin
    eval(expression)
  rescue SyntaxError, NoMethodError, ZeroDivisionError
    nil
  end
end

def run
  result = nil
  number_of_attempts = 0

  while result != TARGET_NUMBER
    number_of_attempts += 1
    binary_string = random_binary_string
    expression = binary_string_into_expression(binary_string)
    result = eval_expression(expression)

    if result
      puts "#{binary_string} | #{expression.ljust(8, ' ')}| #{result}"
    end
  end

  puts "Got target number #{TARGET_NUMBER} in #{number_of_attempts} attempts"
end

Here’s the tail of a few sample outputs.

101110111000 | - - 8   | 8
011111001000 | 7 * 8   | 56
010010110111 | 4 - 7   | -3
000110111000 | 1 - 8   | -7
101110110110 | - - 6   | 6
011111010100 | 7 / 4   | 1
000011000101 | 0 * 5   | 0
011111001001 | 7 * 9   | 63
000011010001 | 0 / 1   | 0
101011100001 | +  1    | 1
001010110101 | 2 - 5   | -3
000111000001 | 1 * 1   | 1
011110101000 | 7 + 8   | 15
Got target number 15 in 936 attempts
000111001001 | 1 * 9   | 9
111011100010 |   2     | 2
011111010011 | 7 / 3   | 2
011011010011 | 6 / 3   | 2
010011000010 | 4 * 2   | 8
110111011111 | / /     | (?-mix: )
011110111001 | 7 - 9   | -2
011011000001 | 6 * 1   | 6
000010111001 | 0 - 9   | -9
011010110000 | 6 - 0   | 6
000010110000 | 0 - 0   | 0
010110100111 | 5 + 7   | 12
101011100110 | +  6    | 6
011010101001 | 6 + 9   | 15
Got target number 15 in 1736 attempts
011110110100 | 7 - 4   | 3
010011011001 | 4 / 9   | 0
101010100000 | + + 0   | 0
001011010100 | 2 / 4   | 0
101001001110 | + 4     | 4
000010110000 | 0 - 0   | 0
100011111110 | 8       | 8
100010110101 | 8 - 5   | 3
000011000000 | 0 * 0   | 0
100010101000 | 8 + 8   | 16
101001011110 | + 5     | 5
101110111000 | - - 8   | 8
010010101000 | 4 + 8   | 12
010011010001 | 4 / 1   | 4
001111000101 | 3 * 5   | 15
Got target number 15 in 167 attempts
111001111111 |  7      | 7
010110110011 | 5 - 3   | 2
011111001000 | 7 * 8   | 56
100111010110 | 9 / 6   | 1
010010110011 | 4 - 3   | 1
011011010010 | 6 / 2   | 3
101111110110 | -  6    | -6
011111000111 | 7 * 7   | 49
101101111111 | - 7     | -7
011111010100 | 7 / 4   | 1
011110100110 | 7 + 6   | 13
101010100110 | + + 6   | 6
111111110100 |   4     | 4
111010011111 |  9      | 9
011011101110 | 6       | 6
000010110101 | 0 - 5   | -5
011110110101 | 7 - 5   | 2
011110101000 | 7 + 8   | 15
Got target number 15 in 285 attempts

Is it Really a Genetic Algorithm?

This is an amusing program but I’m not really sure it’s a genetic algorithm. What would the “genetic” part be? Seems like there should be some swapping of chromosomes happening at some point. These numbers should be banging the hell out of each other. Unfortunately, my program seems pretty G-rated.

My next step will be to examine the genetic algorithm tutorial a little more closely to see how I might be able to make this genetic algorithm a little more legit.

Next Steps

After this I got a real genetic algorithm working.

My Favorite Debugging Techniques

Leave a reply

Tracking down the source of a bug can sometimes be really tough, especially when it’s somebody else’s bug in somebody else’s codebase.

The heart of my debugging approaches is the principle that it’s much easier to find out what piece of code introduced the bug than it is to actually understand the flow of execution around that bug. Whenever there are two ways of doing something, I choose the path that requires the smallest application of brainpower.

git bisect

One of my favorite debugging techniques is to use git bisect, a form of diff debugging.

If you’re not familiar with git bisect, here’s how it works. You basically tell Git, “Okay, Git, I know that the bug is present now, I know that the bug was not present as of a month ago. Can you help me find out exactly which commit introduced the bug?”

Git will then take you back in time. Let’s say you happen to know that as of 32 days ago, your bug did not exist. In this case git bisect would take you back to 16 days ago, halfway between now and when the code was good. You then tell Git whether the codebase was “good” or “bad” as of 16 days ago.

Let’s say that, as of 16 days ago, your code was good. Now we know that the bug was introduced sometime within the last 16 days. We’ve narrowed down the “mystery space” from 32 days to 16 days. The next step is that git bisect will take you to 8 days ago, halfway between now and the most recent good state. This process repeats until you’ve identified the commit that introduced the bug. Git keeps bisecting history until there’s nothing left to bisect. This, in case you didn’t know, is called a binary search.

Once the bad commit is identified, it’s usually much easier to figure out what exactly is going wrong than it would have been to just stare at today’s code and try to ponder its innerworkings.

git revert –no-commit

I use git revert --no-commit less frequently than git bisect but I still use it a fair amount. I often use git revert --no-commit in conjunction with git bisect after I’ve nailed down the offending commit.

The challenge with git bisect is that sometimes the bad commit is a really big one. (Big commits are a bad idea, by the way. One reason big commits are bad is that it’s easier for a bug to hide in a big commit than in a small one.) What if 20 files changed in the bad commit? How do you know where the bug lies?

This is where git revert --no-commit comes in. I of course assume you know that git revert will add a new commit to your history that’s the exact opposite of whatever commit you specify. That works out great when a commit introduces a bug and nothing else. But what if there’s a commit that introduces both a bug and a set of really important features that can’t be discarded?

Doing a git revert --no-commit <SHA of bad commit> will undo all the changes of the bad commit, but it won’t actually make a new commit. (Minor note: after a git revert --no-commit, the changes will be staged. I always do a git reset to unstage the changes.)

Once I’ve done my revert and git reset, I test my application to verify that the bug I’m investigating is not present. Remember, the revert commits the reverse of the bad commit, so undoing the bad commit should make the bug go away. It’s important to verify that the bug did in fact go away or else we’d be operating off of bad premises.

After I’ve verified that the bug is not present, I do a git diff to see what exactly the commit changed. I usually discover that there are some changes that are clearly superficial or cosmetic and don’t have anything to do with the bug. If there’s a whole file that contains irrelevant changes, I git checkout that file.

Let’s say that I have 20 modified files after I do my git revert --no-commit, and let’s say that 15 of them contained clearly superficial changes. I would git checkout all 15 of the irrelevant files and then verify again that the bug is not present. Now my “mystery space” has been narrowed down to 5 files.

Let’s say that this is a codebase I don’t understand at all, so studying the code is fairly useless to me, or at least a very slow way to make progress. Out of these 5 files that might contain the bad code (which we’ll call files A, B, C, D and E), I would probably do git checkout A and see if the bug is still not present. If the bug is still not present, I’d do git checkout B and see if that brought the bug back or not. I’d continue to do this until I found which file contains the bug-introducing code.

Let’s say that after all my investigation I’ve determined that file E contains the code that introduced the bug, but I still don’t know exactly which part. I’d then do a manual micro-bisect. I’d comment out half the file and test for the bug. Then I’d uncomment half of what’s commented. Then I’d uncomment half of that, and so on, until I found the offending code.

By this process I can usually identify and fix a bug, even if I have no understanding of the codebase.

How to Find Programming Job Leads on Craigslist

1 Reply

Hunting vs. farming

There are two general strategies you can use to find programming job leads: hunting and farming.

“Hunting” can get results quickly but it only has a short-term benefit. Hunting includes things like scanning job boards and connecting with recruiters.

“Farming” methods can take longer to bear fruit (to continue the analogy) but the results are more permanent in nature. Farming can include things like building a technical blog, writing a book and giving technical talks.

In this post I’m going to talk about hunting, specifically using craigslist. But before that, let me describe a more general job board strategy.

Job board strategy

Geography and money

If you want to get a job that pays a lot, you should work for a company that has a lot of money. Companies that have a lot of money tend to be in big cities. So if you don’t live in a big city, your options are either to move to a big city or get a remote job working for a company in a big city. Either way, the geographic scope of your job search will be big cities.

The goal of a job ad response

When you respond to a job ad, your goal should not be to sell the employer on hiring you. Your goal should be to sell the employer on responding to you. The job of the first email is to get on the phone. The job of the phone call is to get an in-person interview. The job of the in-person interview is to get the offer. Don’t make the (extremely common) mistake of selling them on hiring you in the first email.

Volume

Most people apply to way too few jobs. You should apply to a lot of jobs. I recommend you shoot for a minimum of 5 per weekday or 25 per week. Also, don’t pin your hopes on any one particular job. And don’t let your foot off the gas just because you’re starting to get calls back. That’s the time to step on the gas more because what you want is as many concurrent conversations as possible, leading to as many concurrent job offers as possible, meaning you have more power and options at the time of the offer.

When to apply, when to wait

How do decide whether or not you’re qualified for a particular job? The answer is don’t worry about it. Just apply. I hate to invoke the “You miss 100% of the shots you don’t take” quote but it’s true. Applying to a job you’re not qualified for has very little potential downside but a huge potential upside. You should of course prioritize the jobs that look like better fits over the jobs that look like worse fits. But if you’ve given yourself a quota of 5 applications per day and you’re only at 3, fill the remaining 2 with jobs you’re not qualified for. Think about the worst that could happen vs. the best that could happen.

And what if you have no programming experience at all? What if you’re trying to get your first programming job? The same principle applies. Just fucking apply. They might ignore your application. So what? They might call you back for an interview, and you might go down in flames during that interview. So what? Now you have some interview practice. Do enough of those interviews and eventually somebody will neglect to ask you any technical questions and you’ll get the job. You can count on this. It probably won’t happen on your first, third or twentieth try, but if you try enough times, getting an offer is inevitable.

How to get job leads using craigslist

Historically, most of the job interviews I’ve gotten have been from job boards, and the job board I’ve used the most is craigslist.

Which craigslists to use

Earlier I said that it makes sense to geographically scope your job search to big cities. The best big cities for tech jobs are probably San Francisco, New York, Seattle, Boston, Austin and Portland, in roughly that order. Let’s call these “Tier 1” cities.

Then we can list all the “Tier 2” cities. We can even just pull up a List of United States Cities by population entry on Wikipedia. The ones we haven’t listed in Tier 1 include LA, Chicago, Houston, Phoenix, Philadelphia…you get the idea of course. What you want to do is make a list of all these cities and put them in a file somewhere.

You can prioritize this list any way you like. For me, I live in West Michigan, so I prioritize Chicago and Detroit high on the list because they’re easy to get to. It really doesn’t matter a ton which cities are on the list and how you prioritize them. The point is that there should be a lot of them.

What to do once you’ve chosen your cities

For my list I do kind of a foreach loop. For each city on my list:

  1. Visit the craigslist for that city, e.g. https://sfbay.craigslist.org/
  2. Visit /sof and /web
  3. For both /sof and /web, search for my competencies (e.g. “rails”, “ruby”, “javascript”, “angular” – all separate searches)
  4. Start applying to stuff

How to respond

A deep discussion of how to respond to a job ad is outside the scope of this article but I’ll say this: Keep it short. Don’t write a commercial for yourself. Just invite the other person to have a conversation. Make it easy to respond.

In my mind, the fewer details I include about myself, the fewer excuses the recipient has to disqualify me. If I say I have 3 years of experience and the job ad says 5, then that’s a reason to disqualify me. But if I leave out my years of experience, then the recipient doesn’t know, and has to ask me in order to know. And by the time we get to that part of the conversation, the interviewer may no longer care about years of experience because my other strengths compensate. So my email responses are very short. I don’t even attach a resume unless specifically directed.

Be upfront about geography. If the job posting says “REMOTE WORKERS NEED NOT APPLY!” respect that and refrain from applying. If you’re willing to relocate, say so. If you want to work remotely but the ad seems to expect local applicants, address the matter.

By the way, just by following the instructions in the job ad, you’ll already be ahead of 90% of the applicants. I’ve been on the receiving end of job applications. It’s amazing how sloppy and careless so many people are.

Lastly, you might hear other people talking about how they’ve “tested” different email subject lines, etc. when responding to job board ads. That kind of claim is pure bullshit. There are way too many variables involved, and way too small of a sample size, to be able to test the effectiveness of various email tactics when responding to job ads. The best you can do is to gain an understanding of human psychology and apply what you’ve learned to your email tactics.

Persistence

I want to leave you with some advice regarding persistence. One of my favorite quotes, attributed to Ben Franklin, is “Energy and persistence conquer all things.” The shortened version I chant in my head is, “Persistence conquers all things.”

When you’re early on in your job search, it will all feel like a waste of time. You’ll apply to what feels like hundreds of jobs and hear nothing back. You’ll probably feel very discouraged. But then, all of a sudden, you’ll get a flood of activity. It always works that way.

And depending where you’re starting from, it will take shorter or longer to get to where you want to be. If you’re an experienced developer and you just want to relocate, it might take you as little as a few weeks to find a new job. (I’ve heard of job searches that began and concluded inside of one day.) If you’re just starting out, it might take you multiple years to get your first programming job. But however long it takes, don’t let any excuse allow you to cease your forward motion. Do something to move yourself forward every single day.

If you’re persistent and you keep moving no matter what, eventually something will work.

Most Programmers Prepare for Interviews Backwards

Leave a reply

In my mind there’s one single key to interviewing successfully. Most job seekers are not only ignorant of the importance of this idea but they actually have it exactly backwards.

Most job seekers think they need to come to an interview prepared with answers. That’s true to an extent but it’s actually far more important to come prepared with questions. I’ll explain why.

Why It’s Smart to Ask Questions

Whoever is asking the questions in a conversation is the one who has the power in that conversation. If you’re controlling the conversation, you can steer it toward your strengths and the reasons why you’d be a good fit. If you let the interviewer control the conversation, you’re leaving it to chance.

Some companies really have their interview process down but from what I’ve seen, most companies don’t. It’s super common for an interviewer to sit down with an interviewee and not even have a single question prepared. They just ask whatever questions come to mind. Or even worse, they ask dumb questions like “What’s your proudest accomplishment?” because they presumably heard somebody else ask that question before and so figured it was a standard interview question. In my mind there’s no good reason to roll the dice by letting the other person ask all the questions when it’s totally possible to for you to take control.

Doing the Interviewer a Favor

By taking control, you’re actually doing your interviewer a favor. Often, the person interviewing you is a developer who sees your interview as a distraction from his or her regular priorities and for that reason has underprepared or not prepared at all. By taking control of the conversation, you’re lifting the burden of thinking of things to talk about from that person and putting it on yourself. You’re making the other person’s job easier. For this reason I pretty much never encounter resistance when I attempt to take control of the conversation.

How to Show Interest

There’s another reason it’s good to ask questions. Employers want to hire candidates who appear interested in the job. You might think “duh”, but you’d be surprised how many interview candidates don’t actually express strong interest in the job they’re being interviewed for. One way of showing interest is to actually say, “I’m really interested in working together.” I think that’s a good thing to say but I think asking thoughtful, intelligent questions is an even stronger way to express interest.

You might wonder what kinds of questions are good to ask.

Personal Questions

The best kinds of questions to ask in an interview are personal questions. This is because you don’t get interviewed by a company, you get interviewed by a person. It’s an individual person (or group of people) you have to win over in order to get hired.

Before the interview you should find out who will be interviewing you. (It’s totally normal to ask who will be interviewing you when you’re in the process of setting it up.) At best you’ll get a list of first and last names. At worst you’ll get nothing. Either way, there’s something you can do.

If you’re able to get the names of the people with whom you’re interviewing, google their names and see what comes up. You’ll also definitely want to check out their LinkedIn profiles. What are their roles? What are their work backgrounds? Where did they go to school? See if you can find anything interesting to comment on. See if you can find any commonalities. Take notes of all this stuff as you go.

If you can’t get actual names, you can make some guesses. You can try to go to the “About” page on the company’s website and see if there’s information listed there about their team. These links are often buried on the footer of the site. If you see some people there who might possibly be the people who are interviewing you, go through the research steps listed above.

How to be Interesting

I attended the Windy City Rails conference in, I believe, 2012. I was bored and antsy during one of the talks so I stepped out in the hall and started talking with the sponsors.

I met a guy named Mark who seemed pretty cool. I asked him question after question about himself and the company he worked for. After about 30 minutes into our conversation I had said almost nothing. I had only asked questions. Then Mark said, “You know, this is the most interesting conversation I’ve had at this conference.” The conversation was interesting to him because I allowed him to talk about the topic that interests him most: himself.

There’s a quote in How to Win Friends and Influence People that’s pretty relevant here: “To be interesting, be interested.”

There’s another relevant quote I’ll share here as well. Olivia Fox Cabane said in The Charisma Myth, “Don’t try to impress people. Let them impress you and they’ll love you for it.”

This is something else I think most interviewees have backwards. They go in thinking their goal should be to impress the people interviewing them. In reality your goal should be to make your interviewers like you, and one of the most effective ways I know of to get someone to like you is to show genuine interest in them.

So the takeaway here is to ask thoughtful, intelligent personal questions about the people interviewing you.

General Questions

Sometimes it’s too hard to come up with personal questions or the timing in the conversation isn’t right. In this case you can fall back on more general questions. Below are some of my go-tos.

Why do you want to hire a developer right now? What triggered this? This question is a good one not because it necessarily reveals some mind-blowing answer but it’s just a good question to lead with. It sounds natural to ask. “So, why are we talking right now?”

Can you tell me about your development team? Every company that hires developers of course has a development team. Or you’re their first developer. Either way, the question is relevant.

If you could wave a magic wand and make one thing happen right now, what would it be? This question reveals the biggest perceived problems and challenges in the organization right now.

Action Items

Make a list of questions you could ask at your next interview. And next time you have an interview actually scheduled, come up with a list of questions specifically for that interview.

Don’t Ace the Technical Interview, Circumvent It

Leave a reply

I’m a fairly lazy person. I also value my time dearly. For these two reasons, I’m always looking for how I can get the biggest possible results for the lowest amount of time and effort.

Below I’ll share how I’ve applied this philosophy to technical interviews.

The One Answer That Interviewers Are After

Why do employers interview prospective employees before hiring them? It might seem like a silly question because the answer is so obvious but I think the question is worth putting a precise answer on.

If you want to get really good at interviewing, it seems worthwhile to me to try to gain a deep understanding of everything to do with interviews, right down to the reason interviews exist. Here’s what I think the answer is.

Employers interview prospective employees because they’re looking for an answer to the question: Can we trust this person to do the job?

Just to making things extra clear, let’s take a quick second to define “trust”. Let’s say my car needs a brake job and a friend of mine offers to do it for me because he needs some extra cash. In order to let my friend do my brake job, I’d need to trust him in two different ways. First, I’d need to trust him not to just steal my car. Second, I’d need to trust that my friend actually knows what he’s doing so he doesn’t fuck up my car.

A job interview is mostly concerned with the “do you actually know what you’re doing?” kind of trust as opposed to the “are you going to steal my car?” kind of trust.

The way I see it, there are at least three ways to get an employer to trust you enough to hire you. One way is to get rigorously interviewed and answer a whole bunch of technical questions. The other two I’ll describe below.

“Anybody Dave Likes Must Be Good”

One way to get “auto-trusted” is to get referred to an employer by somebody who already works there.

Let’s say you have a friend named Dave who works at a company called CodeFuckers. Dave’s boss says, “Hey guys, if you know of any good engineers could you let me know? We really need some help around here.” Later that week, you and Dave talk as you occasionally do, and Dave says, “Oh hey, CodeFuckers is looking for more developers. Do you think you might be interested?” You say yes, and Dave passes your contact info along to his boss along with his endorsement of you.

Trust has an interesting way of being extensible. Because Dave’s boss trusts Dave and Dave trusts you, Dave’s boss automatically trusts you to a certain extent. Dave’s boss calls you in for an interview and, when you meet him, he says, “Hey [your name here], nice to meet you. Dave has said some great things about you. We think Dave is awesome and anybody Dave likes must be good.”

So without talking to you or asking you a single question, Dave’s boss already has a positive opinion of you.

How to Meet People Who Can Refer You

You might say, “That’s great, Jason, but I don’t know a lot of people who could refer me.” That’s a fixable problem. The solution is what some people might call “networking”. Don’t be put off by that word, though. I think you’ll find my form of networking to be fairly palatable.

Whole books have been written about networking, and a thorough discussion is outside the scope of this article, but I’ll give you a few quick tips.

One of the easiest and most effective ways to meet developers who could refer you is to attend local user groups. You’re probably aware that such user groups can be found on meetup.com.

In order to form relationships out of these user groups, you’ll have to actually talk to people. If that’s not your strong suit, I’d recommend picking up the book How to Win Friends and Influence People by Dale Carnegie. Don’t just show up at the start of the talks and leave immediately after. Show up a little early and stay late. Get to know the organizer.

The most effective way to take advantage of local user groups is to give presentations. If you give presentations, you’ll be seen as an expert. You’ll go from being an anonymous face in the crowd to a trusted member of the community. Important tip: don’t put off presenting until you feel ready. Just start now. You don’t have to be an expert before you can teach the group something they don’t know.

One time I found myself having a conversation with a prospective freelancing client. He told me he didn’t plan to give me a technical drilling since all his employees knew me from technical meetups and gave me the thumbs up. If you do the same thing, you can have the same experience.

“Obviously You Know What You’re Doing. You Wrote the Book.”

The other way I know of to “grease the chute” on trust is to build an Authority Piece.

The absolute best type of Authority Piece is a technical book published by an actual publisher (as opposed to, e.g., a self-published e-book).

It’s actually not as hard to get a book deal as you might imagine, but it’s definitely still a lot of work to write a technical book. If you don’t feel quite ready to go down that path right now, I completely understand. I personally have no plans to ever write a published technical book.

One of the next best types of Authority Piece is a self-published e-book. I’ve done this myself. I wrote an e-book called Angular for Rails Developers.

Being the author of an e-book hasn’t attracted a lot of prospective employers or freelancing clients to me but it has certainly helped in the situations where I found myself already having a conversion with a prospective freelancing client. (You can replace “freelancing client” with “prospective employer” and all the principles are still the same.)

Once I was having a phone call with a prospective client. He told me he wasn’t going to ask me a bunch of questions. He said, “Obviously you know your shit on Angular. You wrote a whole book about it.” I never had to claim I was an expert or sell myself in any way. My prospect just assumed that I was an expert because I had written an e-book.

An e-book can be relatively easy to produce compared to a published book. People expect a published book to be hundreds of pages but an e-book can be pretty short. I think the first version of Angular for Rails Developers was something like 50 pages. No one complained about the length.

But maybe even an e-book seems a little too big an undertaking to consider right now. That’s okay. You have more options.

Probably the next best thing after an e-book is a focused technical blog. Notice that I say focused technical blog. A lot of developers maintain blogs that are all over the map technology-wise, thus not capable of seizing the interest of any particular person.

The content on AngularOnRails.com is almost 100% Angular + Rails. (A very small portion of it is just Angular or just Rails. None of it is, for example, Java.) For that reason, if someone is working on an Angular + Rails project, everything on the site has a shot at being interesting to them. That’s what you should be shooting for.

The last Authority Piece I’ll mention is speaking. Speaking is of course not a “thing” but an activity. Each individual talk you give is its own authority piece. Some talks are more valuable Authority Pieces than others, and some talks’ value is longer-lasting than others.

For example, an off-the-cuff tech talk at a local meetup has a relatively small amount of value and its value is fairly fleeting. It won’t be remembered two years from now. But if you give a talk at a national conference that seriously strikes a chord with people and ends up being widely shared, then that talk is going to be a hugely valuable Authority Piece for years to come.

A Final Note About Technical Competence

I feel compelled to say a certain something to pre-empt the dumbass Hacker News commenters. (Important side note: I’m not saying that all Hacker News commenters are dumbasses, just a large number of them.)

I’m not advocating these tactics as a substitute to actual technical competence. Yes, you should know what you’re doing.

My perception is that technical interviews are often a test at how good you are at technical interviews, not a test of how good you actually are as a developer. So if employers are trying to make you play a dumb game that doesn’t make any sense, my opinion is that it’s totally okay to try to bypass that game.