#!/usr/local/bin/ruby

class Graph
  attr :vertices
  attr :edges

  def initialize(vertices = [], edges = Hash.new {|h, k| h[k] = Hash.new {0} })
    @vertices = vertices
    @edges = edges
  end

  def tie_exists?(a, b)
    true #edges[a].select {|k, v| a != k && v > 0 }.any? {|k| tie_exists?() }
  end
end

def grow(graph, a, b)
  vertices = graph.vertices.dup
  edges = graph.edges.dup
  edges.map {|k, v| edges[k] = v.dup }
  c = vertices.size

  vertices << c

  edges[a][c] += 1
  edges[c][b] += 1

  Graph.new(vertices, edges)
end

def progress(game)
  game.flat_map do |g|
    g.vertices.combination(2)
      .select {|a, b| g.edges[a][b] < 2 && g.tie_exists?(a, b) }
      .map {|a, b| grow(g, a, b) }
  end
end

game = [Graph.new([0, 1])]

game = progress game; p game.size
game = progress game; p game
game = progress game; p game.size