Skip to content

Instantly share code, notes, and snippets.

@qickstarter
Created February 3, 2014 18:52
Show Gist options
  • Save qickstarter/8789914 to your computer and use it in GitHub Desktop.
Save qickstarter/8789914 to your computer and use it in GitHub Desktop.
require 'singleton'
class Question
include Singleton
include Enumerable
attr_accessor :answer, :question
def initialize
@statement = [
{
q: [
'8',
'B depends on A',
'C depends on B',
'C depends on E',
'D depends on C',
'D depends on F',
'E depends on A',
'F depends on E',
'G depends on F',
'B F',
],
a: 'B C D F G',
},
{
q: [
'3',
'2 1',
'B depends on A',
'C depends on B',
'B',
],
a: 'B C'
},
{
q: [
'5 2',
'P depends on Q',
'P depends on S',
'Q depends on R',
'R depends on T',
'S depends on T',
'Q S',
],
a: 'P Q S',
},
{
q: [
'8 2',
'B depends on A',
'C depends on B',
'C depends on E',
'D depends on C',
'D depends on F',
'E depends on A',
'F depends on E',
'G depends on F',
'B F',
],
a: 'B C D F G',
}
]
end
def each(&block)
until @statement.empty?
build_question
self.instance_exec(@answer, &block)
end
end
def gets
build_question unless @question && @answer
@question.shift
end
def build_question
@question, @answer = @statement.shift.values_at(:q, :a)
end
module STDIN
def self.gets
Question.instance.gets
end
end
$stdin = STDIN
end
module Treerable
include Enumerable
attr_accessor :parent, :key
def each(&block)
children.each &block
end
def find_node(project_name)
self.each do |node|
return node if node.key == project_name
target = node.find_node(project_name)
return target if target
end
nil
end
def make_node(key, depends_on = nil)
parent_node = find_node(depends_on) || Node.new(depends_on)
child_node = (find_node(key) || Node.new(key))
parent_node << child_node
[parent_node, child_node].each do |node|
self << node if node.parent.empty?
end
end
def <<(node)
if node.is_a?(Node)
node.parent << self if node.parent
children << node
else
new_node = Node.new(node, self)
children << new_node
end
end
def children
@children ||= []
end
def parent
@parent ||= []
end
end
class Node
include Treerable
def initialize(key, parent_node = nil)
@key = key
parent << parent_node if parent_node
@accident = false
end
def accidented_nodes
if accident?
[self] + self.children
else
self.children.map { |v| v.accidented_nodes }.flatten
end
end
def accident!
@accident = true
end
def accident?
!!@accident
end
end
class Tree
include Treerable
def accidents!(*project_names)
project_names.each do |name|
if node = find_node(name)
node.accident!
end
end
end
def extent_of_the_impact
self.map do |node|
node.accidented_nodes
end.flatten
end
def parent
nil
end
end
class Solver
def initialize
@tree = Tree.new
gets.chomp.to_i.times do |i|
/(?<var1>.) depends on (?<var2>.)/ =~ gets.chomp
@tree.make_node(var1, var2)
end
end
def solve
@tree.accidents!(*gets.chomp.split(' '))
@tree.extent_of_the_impact.map { |v| v.key }.uniq.sort
end
end
if Object.const_defined?(:Question)
Question.instance.each do |expected|
puts Solver.new.solve == expected.split(' ')
end
else
puts Solver.new.solve
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment