#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

module Dunber
  M = 2     # 点はM次以下の隔たりで繋がっていなければならない
  N = 4     # 点から出る辺の数は最大N本
  NUM = 15  # ノードの数NUMの場合の解を求める
  POP = 400 # 一度に扱うtreeの数。population。
  
  class Node
    attr_reader :id, :edges
    attr_accessor :dist
    
    def initialize(id)
      @id = id
      @edges = []
      @dist = 0
    end
    
    def add(x)
      @edges.push(x)
    end

    def cut(x)
      @edges.delete(x)
    end
    
    def addable?(x)
      if full?
        return false
      elsif @id == x
        return false
      else
        not @edges.include?(x)
      end
    end
    
    def full?
      @edges.size >= N
    end
    
    def to_s
      "#{@id}:#{@edges}"
    end
  end
  
  class Tree
    attr_reader :nodes
    
    def initialize
      @nodes = []
      (0...NUM).each do |i|
        @nodes.push Node.new(i)
      end
    end

    def shuffle
      @nodes.each do |node|
        arr = (node.id...NUM).to_a
        next if arr.size == 0
        
        arr = arr.select do |i|
          @nodes[i].addable?(node.id)
        end
        arr = arr.sort_by{|a| rand}
        
        (N - node.edges.size).times do
          add(node.id, arr.pop) if arr.size > 0
        end
      end
      self
    end
    
    def add(a, b)
      @nodes[a].add(b)
      @nodes[b].add(a)
    end
    
    def score
      return @score if @score
      
      @score = 0
      @nodes.each do |node|
        @score += score_sub?(node)
      end
      return @score
    end
    
    def score_sub?(node)
      clear_dists
      paint(node, M+1)
      count_dist(node.id)
    end
    
    def count_dist(start)
      rst = 0
      @nodes.each do |node|
        if node.dist == 0
          rst += 1
        end
      end
      rst
    end
    
    def paint(node, m)
      if node.dist < m
        node.dist = m
        node.edges.each do |edge|
          paint(@nodes[edge], m-1)
        end
      end
    end
    
    def clear_dists
      @nodes.each do |node|
        node.dist = 0
      end
    end
    
    def dup
      copy = super
      @nodes = Marshal.load(Marshal.dump(@nodes))
      copy
    end
    
    def to_s
      str = "#{@nodes.size}個のノード。\n"
      str += "#{count_edges}本のエッジ。\n"
      str += "#{score}のスコア。\n"
      @nodes.each do |node|
        str += "#{node.to_s}\n"
      end
      str
    end

    def count_edges
      count = 0
      @nodes.each do |node|
        count += node.edges.size
      end
      count /= 2
    end
    
    def cut(a, b)
      @nodes[a].cut(b)
      @nodes[b].cut(a)
    end
    
    def step
      @score = nil
      
      2.times do
        id = rand(NUM)
        unless @nodes[id].edges.empty?
          index = rand(@nodes[id].edges.size)
          cut(id, @nodes[id].edges[index])
        end
      end
      
      shuffle
    end
  end
  
  class Forest
    attr_reader :trees
    attr_reader :step, :size
    
    def initialize(size)
      @step = 0
      @trees = []
      size.times do
        @trees.push Tree.new.shuffle
      end
      sort
    end
    
    def valid?
      @trees[0].score == 0
    end
    
    def to_s
      str = "スコア範囲#{@trees[0].score}から#{@trees[-1].score}\n"
    end
    
    def sort
      @trees = @trees.sort_by{|tree| tree.score}
    end
    
    def step
      @step += 1
      @trees.each do |tree|
        tree.step
      end
      sort
      
      @trees = @trees[0, POP/4]
      
      2.times do
        trees_new = []
        @trees.each do |tree|
          trees_new.push tree.dup
        end
        @trees.concat trees_new
      end
    end
  end
  
  def self.main
    forest = Forest.new(POP)
    puts forest.to_s
    loop do
      forest.step
      puts forest.to_s
      if forest.valid?
        tree = forest.trees.shift
        puts "解を発見しました！！"
        puts "#{tree}"
        exit
      end
    end
    
  end
  
end

Dunber.main