Метод для заказа списка с зависимостями

Question

Условия: Необходимо использовать веб-решение (HTML/CSS), использовать Ruby on Rails, без использования базы данных.

Представьте, что у нас есть список заданий, каждый из которых представлен персонажем. Поскольку определенные задания должны выполняться перед другими, работа может иметь зависимость от другой работы. Например, a может зависеть от b, то есть конечная последовательность заданий должна помещать b перед a. Если а не имеет зависимости, то положение а в конечной последовательности не имеет значения. Эти рабочие места будут вводиться с помощью простого текстового поля (также как делает один магазин несколько переменных)

Учитывая следующую структуру работы:

• а =>
• Ь =>
• с =>

Результатом должна быть последовательность, содержащая все три задания abc в значительном порядке.

Учитывая следующую структуру работы:

• а =>
• Ь => с
• с => F
• г => а
• е => б
• f =>

Результат должен быть таким же equence, что позиции f до c, c до b, b до e и a до d, содержащие все шесть заданий abcdef.

Учитывая следующую структуру работы:

• а =>
• Ь => с
• с => F
• г => а
• е =>
• е => b

Результат должен быть ошибка, указывающая, что задания не могут иметь круговые зависимости.

Answer 1

Это должно работать:

module JobDependenciesResolver  

    def self.organize(dependencies) 
    unresolved_dependencies = dependencies.dup 
    sorted_jobs = [] 

    until unresolved_dependencies.empty? do 
     doable_jobs = get_doable_jobs unresolved_dependencies, sorted_jobs 
     raise Exception.new("Not able to resolve dependencies") if doable_jobs.empty? 
     sorted_jobs += doable_jobs 
     unresolved_dependencies.delete_if {|key,value| sorted_jobs.include? key} 
    end 

    sorted_jobs 
    end 

    private 

    def self.get_doable_jobs(dependencies, job_array) 
    dependencies.select {|job, dependency| ([*dependency]-job_array).empty? }.keys   
    end 
end