#!/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