groups, tree

example.rb

require 'pry'
require './groups'

def p(*args)
  Pry::ColorPrinter.pp(*args)
end

matrix = Matrix.new([
  { vehicle: :car },
  { vehicle: :truck },
  { vehicle: :bike },
])

puts "\noriginal matrix:"
matrix.show
puts "\nresumed matrix:"
matrix.implode.show
# [{:vehicle=>[:bike, :car, :truck]}]

matrix = Matrix.new([
  { vehicle: :car, color: :red },
  { vehicle: :car, color: :blue },
  { vehicle: :car, color: :yellow },
  { vehicle: :truck, color: :green },
  { vehicle: :truck, color: :blue },
  { vehicle: :bike, color: :yellow },
  { vehicle: :bike, color: :red },
])

puts "\noriginal matrix:"
matrix.show
puts "\nresumed matrix:"
matrix.implode.show
# [{ vehicle: [:bike, :car],  color: [:red, :yellow] },
#  { vehicle: [:car, :truck],  color: :blue },
#  { vehicle: :truck,  color: :green }]

matrix = Matrix.new([
  { kind: :cookie, color: :brown, flavor: :chocolate },
  { kind: :cookie, color: :white, flavor: :chocolate },
  { kind: :cookie, color: :white, flavor: :banana },
  { kind: :cake, color: :green, flavor: :chocolate },
  { kind: :cake, color: :blue, flavor: :chocolate },
  { kind: :cake, color: :red, flavor: :strawberry },
  { kind: :cake, color: :red, flavor: :raspberry },
  { kind: :macaron, color: :yellow, flavor: :banana },
  { kind: :macaron, color: :red, flavor: :strawberry },
  { kind: :macaron, color: :red, flavor: :raspberry },
])

puts "\noriginal matrix:"
matrix.show
puts "\nresumed matrix:"
matrix.implode.show
# [{:kind=>:cookie, :color=>[:brown, :white], :flavor=>:chocolate},
#  {:kind=>:cookie, :color=>:white, :flavor=>:banana},
#  {:kind=>:cake, :color=>[:blue, :green], :flavor=>:chocolate},
#  {:kind=>:macaron, :color=>:yellow, :flavor=>:banana},
#  {:kind=>[:cake, :macaron], :color=>:red, :flavor=>[:raspberry, :strawberry]}]

puts





matrix = Matrix.new([
  { user: "Rogue", feature1: 0, feature2: 1 },
  { user: "Rogue", feature1: 0, feature2: 2},
  { user: "Rogue", feature1: 0, feature2: 4 },
  { user: "Rogue", feature1: 0, feature2: [15, 18] },
  { user: "Nick Fury", feature1: 0, feature2: 4 },
  { user: "Nick Fury", feature1: 0, feature2: [15, 18] },
])

puts "\noriginal matrix:"
matrix.show
puts "\nresumed matrix:"
matrix.implode.show


require "csv"
pokes_db = CSV.foreach("pokemon.csv", headers: true).map(&:to_h)

pokes = Matrix.new(pokes_db.map { |row| row.slice("name" ,"generation" , "type1", "type2") }.uniq )
pokes.show
pokes.implode.show


pokes = Matrix.new(pokes_db.map { |row| row.slice("generation", "type1", "type2") }.uniq )
pokes.show
pokes.implode.show

pokes = Matrix.new(pokes_db.map { |row| row.slice("type1", "type2") }.uniq )
pokes.show
pokes.implode.show


matrix = Matrix.new([
  { user: "Rogue", feature1: 0, feature2: 1 },
  { user: "Rogue", feature1: 0, feature2: 2},
  { user: "Rogue", feature1: 0, feature2: 4 },
  { user: "Rogue", feature1: 0, feature2: [15, 18] },
  { user: "Nick Fury", feature1: 0, feature2: 4 },
  { user: "Nick Fury", feature1: 0, feature2: [15, 18] },
])


# rating_db = CSV.foreach("rating.csv", headers: true)#.map(&:to_h)

# matrix = Matrix.new(rating_db)
# p matrix.show
# matrix.implode.show
# puts "-----"



db = CSV.foreach("Greene.csv", headers: true).map(&:to_h)
matrix = Matrix.new(db.map { |row| row.slice("judge","nation","rater","decision","language","location") } )
matrix.show
matrix.implode.show

db = CSV.foreach("Migration.csv", headers: true).map(&:to_h)
matrix = Matrix.new(db.map { |row| row.slice("source","destination") } )
matrix.show
matrix.implode.show

matrix = Matrix.new(db.map { |row| row.slice("destination", "source") } )
m = matrix.implode
Matrix.new(m.map { |row| row.slice("source","destination") } ).show

db = CSV.foreach("HairEyeColor.csv", headers: true).map(&:to_h)
matrix = Matrix.new(db.map { |row| row.slice("Hair","Eye", "Sex", "Freq") }.uniq )
matrix.show
matrix.implode.show

# db = CSV.foreach("USRegionalMortality.csv", headers: true).map(&:to_h)
# matrix = Matrix.new(db.map { |row| row.slice("Region","Status","Sex","Cause") }.uniq )
# matrix.show
# matrix.implode.show

Gemfile

# frozen_string_literal: true

source "https://rubygems.org"

group :development, :test do
  gem "pry"
end

Greene.csv

groups.rb

require 'delegate'

class Matrix < SimpleDelegator
  def without(key)
    Matrix.new(map { |hash| hash.clone.tap { |hsh| hsh.delete(key) } })
  end

  def to_tree key = nil
    if all_keys.size == 1
      Trees.new(map { |e| [e, nil] })
    else
      Trees.new(tree_by_key(key || all_keys.first))
    end
  end

  def implode
    all_keys.reverse.inject(self){ |matrix, key| matrix.implode_by_key(key) }
  end

  def explode
    flat_map(&method(:explode_hash))
  end

  def show
    headers = flat_map(&:keys).uniq
    sizes = headers.map { |h| [map { |row| simple_to_s(row[h]).size }.max, h.size].max }
    tmpl = sizes.map { |s| "%-#{s}s" }.join("  ")

    puts
    puts format(tmpl, *headers)
    puts sizes.map { |s| "-" * s }.join ("  ")
    each do |row|
      puts format(tmpl, *headers.map{|h| simple_to_s(row[h])})
    end
    puts
  end

  def simple_to_s(elem)
    if Array === elem
      "[" + elem.map { |e| simple_to_s(e) }.join(",") + "]"
    elsif elem == nil
      "∅"
    else
      elem.to_s
    end
  end

  protected

  def implode_by_key(key = nil)
    Matrix.new(to_tree(key).squash.to_matrix)
  end

  private

  def merge_explodes(first, second)
    first.flat_map do |f|
      second.flat_map do |s|
        f.merge(s)
      end
    end
  end

  def explode_hash(hash)
    return [{}] if hash == {}
    return hash.flat_map { |k, vs| Array(vs).map { |v| { k => v } } } if hash.size == 1
    hash = hash.clone
    k, v = hash.shift
    merge_explodes(explode_hash(k => v), explode_hash(hash))
  end

  def tree_by_key(key)
    group_by_key(key).map do |(value, submatrix)|
      [{ key => value }, Matrix.new(submatrix).without(key).to_tree]
    end
  end

  def group_by_key(key)
    group_by { |hash| hash[key] }
  end

  def all_keys
    @keys ||= flat_map(&:keys).uniq
  end
end

class Trees < SimpleDelegator
  def to_matrix
    Matrix.new(flat_map do |(elem, children)|
      children ? children.to_matrix.flat_map(&elem.method(:merge)) : [elem]
    end)
  end

  def squash
    Trees.new(group_by(&:last).map do |(children, subtrees)|
      [union_all(subtrees.map(&:first)), children && children.squash]
    end)
  end

  private

  def union(hash, other)
    other.inject(hash) do |acc, (key, value)|
      acc.merge(key => acc.include?(key) ? [*acc[key], *value].uniq.sort : value)
    end
  end

  def union_all(elems)
    elems.inject({}, &method(:union))
  end
end

HairEyeColor.csv

Migration.csv

pokemon.csv

tests.rb

require 'minitest/autorun'
require './groups'

class TestMatrix < Minitest::Test
  def setup
    @m1 = Matrix.new([
      {a: :b, c: :d},
      {a: :c, c: :d}
    ])

    @m2 = Matrix.new([
      {a: :a, c: :b},
      {a: :a, c: :c}
    ])

    @t1_1 = [[{a: :b}, [[{c: :d}, nil]]],
             [{a: :c}, [[{c: :d}, nil]]]]

    @t1_2 = [[{c: :d}, [[{a: :b}, nil],
                        [{a: :c}, nil]]]]

    @t2_1 = [[{a: :a}, [[{c: :b}, nil],
                        [{c: :c}, nil]]]]

    @t2_2 = [[{c: :b}, [[{a: :a}, nil]]],
             [{c: :c}, [[{a: :a}, nil]]]]
  end

  def test_without
    assert_equal @m1.without(:a) , [{c: :d}, {c: :d}]
    assert_equal @m1.without(:c) , [{a: :b}, {a: :c}]

    assert_equal @m2.without(:a) , [{c: :b}, {c: :c}]
    assert_equal @m2.without(:c) , [{a: :a}, {a: :a}]
  end

  def test_to_tree
    assert_equal @m1.to_tree , @t1_1
    assert_equal @m2.to_tree , @t2_1

    assert_equal @m1.to_tree(:a) , @t1_1
    assert_equal @m2.to_tree(:a) , @t2_1

    assert_equal @m1.to_tree(:c) , @t1_2
    assert_equal @m2.to_tree(:c) , @t2_2
  end

  def test_implode
    assert_equal @m1.implode , [{:a=>[:b, :c], :c=>:d}]
    assert_equal @m2.implode , [{:a=>:a, :c=>[:b, :c]}]

    matrix = Matrix.new([
          {a: 0, b: 0, c: 1},
          {a: 0, b: 0, c: 0},
          {a: 0, b: 1, c: 1},
          {a: 0, b: 1, c: 0},
          {a: 1, b: 0, c: 1},
          {a: 1, b: 0, c: 0},
          {a: 1, b: 1, c: 1},
          {a: 1, b: 1, c: 0},
    ])

    imploded = [{:a=>[0, 1], :b=>[0, 1], :c=>[0, 1]}]

    assert_equal matrix.implode , imploded

    matrix = Matrix.new([
          { a: 2, b: 1, c: 0, d: 0 },
          { a: 2, b: 0, c: 2, d: 2 },
          { a: 2, b: 1, c: 1, d: 1 },
          { a: 0, b: 1, c: 2, d: 2 },
          { a: 1, b: 2, c: 1, d: 0 },
          { a: 1, b: 1, c: 2, d: 0 },
          { a: 0, b: 2, c: 1, d: 2 },
          { a: 1, b: 2, c: 0, d: 2 },
          { a: 0, b: 0, c: 2, d: 0 },
          { a: 2, b: 2, c: 1, d: 1 },
          { a: 0, b: 0, c: 1, d: 2 },
          { a: 2, b: 0, c: 1, d: 0 },
          { a: 0, b: 0, c: 2, d: 2 },
          { a: 1, b: 0, c: 0, d: 1 },
          { a: 1, b: 1, c: 1, d: 1 },
          { a: 1, b: 0, c: 2, d: 0 },
          { a: 1, b: 1, c: 0, d: 1 },
          { a: 2, b: 2, c: 2, d: 2 },
          { a: 0, b: 1, c: 1, d: 1 },
          { a: 0, b: 0, c: 0, d: 1 },
          { a: 2, b: 1, c: 1, d: 0 },
          { a: 1, b: 0, c: 2, d: 2 },
          { a: 0, b: 1, c: 0, d: 1 },
          { a: 2, b: 1, c: 0, d: 2 }].uniq)

    imploded = [
      { a: 2,      b: 1,      c: [0, 1], d: 0},
      { a: 2,      b: 1,      c: 0,      d: 2},
      { a: 2,      b: 0,      c: 1,      d: 0},
      { a: 2,      b: [1, 2], c: 1,      d: 1},
      { a: 2,      b: [0, 2], c: 2,      d: 2},
      { a: [0, 1], b: 1,      c: [0, 1], d: 1},
      { a: [0, 1], b: 0,      c: 0,      d: 1},
      { a: 0,      b: 1,      c: 2,      d: 2},
      { a: 0,      b: 0,      c: 2,      d: 0},
      { a: 0,      b: 0,      c: [1, 2], d: 2},
      { a: 0,      b: 2,      c: 1,      d: 2},
      { a: 1,      b: 0,      c: 2,      d: 2},
      { a: 1,      b: 2,      c: 1,      d: 0},
      { a: 1,      b: 2,      c: 0,      d: 2},
      { a: 1,      b: [0, 1], c: 2,      d: 0}
    ]

    assert_equal matrix.implode , imploded

    matrix = Matrix.new([
      { a: :a, b: :b, c: :a },
      { a: :a, b: :a, c: :a },
      { a: 0, b: 0, c: 0 },
      { a: 0, b: 0, c: 1 },
      { a: 0, b: 1, c: 0 },
      { a: 0, b: 1, c: 1 },
      { a: 1, b: 0, c: 0 },
      { a: 1, b: 0, c: 1 },
      { a: 1, b: 1, c: 0 },
      { a: 1, b: 1, c: 1 },
      { a: 1, b: 1, c: 3 },
      { a: 3, b: 1, c: 3 }
    ].uniq)

    imploded = [
      { a: :a,     b: [:a, :b], c: :a },
      { a: [0, 1], b: [0, 1],   c: [0, 1] },
      { a: [1, 3], b: 1,        c: 3 }
    ]

    assert_equal matrix.implode, imploded
  end

  def test_explode
    assert_equal @m1.explode , [{:a=>:b, :c=>:d}, {:a=>:c, :c=>:d}]
    assert_equal @m2.explode , [{:a=>:a, :c=>:b}, {:a=>:a, :c=>:c}]

    assert_equal Matrix.new([{:a=>[:b, :c], :c=>:d}]).explode , @m1
    assert_equal Matrix.new([{:a=>:a, :c=>[:b, :c]}]).explode , @m2
  end

end


class TestTrees < Minitest::Test
  def setup
    @t1 = Matrix.new([
      {a: :b, c: :d},
      {a: :c, c: :d}
    ]).to_tree

    @t2 = Matrix.new([
      {a: :a, c: :b},
      {a: :a, c: :c}
    ]).to_tree
  end

  def test_to_matrix
    assert_equal @t1.to_matrix , [{a: :b, c: :d}, {a: :c, c: :d}]
    assert_equal @t2.to_matrix , [{a: :a, c: :b}, {a: :a, c: :c}]
  end

  def test_squash
    assert_equal @t1.squash , [[{a: :b}, [[{c: :d}, nil]]], [{a: :c}, [[{c: :d}, nil]]]]
    assert_equal @t2.squash , [[{a: :a}, [[{c: [:b, :c]}, nil]]]]
  end
end