ZJU the Champions of ACM-ICPC World Finals 2011!

Finally, finally, congratulations ~ Rankings

Evolutionary algorithm example in Ruby

#!/usr/bin/ruby -w

# This program is based on this evolutionar computation introduction:
# http://blog.uncommons.org/2009/01/20/practical-evolutionary-computation-an-introduction/
#
# usage: ruby evolution.rb [generations] [goal]
# example: ruby evolution.rb
#          ruby evolution.rb 100
#          ruby evolution.rb 100 "I make the universe"

# We can set a goal(string) for evolution, and the Evolution object
# will evolute towards the goal you set.
class Evolution
  attr_accessor :set

  # The goal(string) can contain only upcase characters and space
  # CHARSET in fact is gene pool
  CHARSET = ('A'..'Z').to_a + [' ']
  CHARSET_LENGTH = CHARSET.length

  # goal: evolution goal is a string, like 'hello world'
  # population: the population of the society. default to 100, means
  #             there're 100 parents in the initial environment. And
  #             the environment can only support 100 livings.
  # mutation_rate: the possibility of gene mutation. default to 0.01,
  #                means a gene 'A' in one generation has 1/100 possibility
  #                to mutate to random gene in CHARSET
  def initialize(goal,population=100,mutation_rate=0.01)
    @goal = goal
    @population = population
    @mutation_rate = mutation_rate

    # @set is the environment all livings live in
    @set = []
    @strlen = goal.length

    # fill the environment with livings
    population.times {|i|
      str = ""
      @strlen.times {|j| str << CHARSET[rand(CHARSET_LENGTH)] }
      @set << str
    }
  end

  # evolution function
  # reproduce: how many generations should the evolution have
  def run(reproduce=1000)
    reproduce.times {|i| generation }
    sort_and_cut(@set).each {|s| puts "#{s} : #{score s}" }
  end

  private

  # one generation
  def generation
    score_set
    pick
    crossover
    mutation
  end

  # give mutation chance to every living in our environment
  def mutation
    k = 1/@mutation_rate
    for str in @set
      str.length.times {|i|
        str[i] = CHARSET[rand(CHARSET_LENGTH)] if rand(k) == 0
      }
    end
  end

  # choose two parent
  # produce offspring
  def crossover
    set = @set.uniq

    offsprings = []
    if set.length == 1
      offsprings = @set
    else
      (set.length-1).times {|i|
        (i+1).upto(set.length-1) {|j|
          pivot = rand(@strlen) + 1
          par1_a, par1_b = set[i][0,pivot], set[i][pivot,@strlen]
          par2_a, par2_b = set[j][0,pivot], set[j][pivot,@strlen]
          offsprings << "#{par1_a}#{par2_b}"
          offsprings << "#{par2_a}#{par1_b}"
        }
      }
    end

    @set = sort_and_cut(offsprings)
  end

  # pick the good candicates (high score)
  # score 2 candicate will have high possiblity to be choosen than score
  # 1 candicate
  def pick
    pool = []
    @score_map.each {|str,score|
      score.times {|i|
        pool << str
      }
    }
    pool.sort! {|a,b| rand(3) - 1} # shuffle
    pool_len = pool.length
    
    @set = []
    @population.times {|i|
      @set << pool[rand(pool_len)]
    }
  end

  # compute score for every candicates
  def score_set
    @score_map = {}
    for str in @set
      @score_map[str] = score(str)
    end
    @score_map
  end

  # score will tell us the simliarity between the str and goal
  # score = the same character on the correct position with goal
  def score(str)
    score = 0
    @strlen.times {|i|
      score += 1 if str[i] == @goal[i]
    }
    score
  end

  # sort livings by score and only the livings with highest score
  # will left. They're the selection of nature.
  def sort_and_cut(set)
    set.sort_by {|s| -(score s)}[0,@population]
  end

end

if __FILE__ == $0
  times = ARGV[0] ? ARGV[0].to_i : 20
  goal = ARGV[1] ? ARGV[1].upcase : 'HELLO WORLD'
  e = Evolution.new(goal)
  e.run times
end

Bloom filter

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with an even distribution.

To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.

To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have been set to 1 during the insertion of other elements.

False positive is possible, false negative is impossible for bloom filter.

False Positive can be understanded as a "failed positive assertion", e.g. If I report to teacher you cheated in the last exam but in fact you didn't. In bloom filter case, it means the filter may report you the keyword 'd' exists in the set {'a','b','c'}, but the filter will never tell you 'a' or 'b' or 'c' not exists in the same set.

igvita provides a ruby implementation.