最短ヌクレオチド連鎖問題

require 'bundler/setup'
require 'kaki/utils/nest_loop'

class Codon
  include Comparable
  
  def initialize(st)
    @cd = st
  end
  attr_reader :cd
  
  def <=>(a)
    x, y = @cd, a.cd
    l = r = 0 
    l = if x[1..2] == y[0..1]
      2
    elsif x[2] == y[0]
      1
    else
      0
    end
    r = if y[1..2] == x[0..1]
      2
    elsif y[2] == x[0]
      1
    else
      0
    end
    r - l
  end
  
  def inspect
    @cd
  end
  alias :to_s :inspect
end

def calc(x, y)
  if x.cd[1..2] == y.cd[0..1]
    2
  elsif x.cd[2] == y.cd[0]
    1
  else
    0
  end
end

a = [*0..3]
codon = [a, a, a].nest_loop {|x| x.join}.map {|x| Codon.new(x)}
max = 0

loop do
  c = codon.shuffle.sort
  20.times do
    co = 0
    c.each_cons(2) {|x, y| co += calc(x, y)}
    if max < co
      max = co
      puts 64 * 3 - max
      p c
    end
    c1 = c.sort
    break if c1 == c
    c = c1
  end
end

　
これまでの最小値。

105
[123, 231, 113, 132, 320, 200, 001, 120, 201, 010, 211, 100, 003, 033, 002, 023,
 013, 133, 333, 330, 303, 031, 313, 332, 102, 021, 101, 012, 223, 232, 203, 321,
 301, 331, 311, 112, 322, 220, 202, 212, 210, 230, 030, 300, 000, 020, 011, 111,
 110, 130, 302, 122, 032, 323, 233, 312, 022, 222, 221, 121, 213, 131, 310, 103]