cresjoy cresjoy - 4 months ago 11
Javascript Question

Finding order between many events

Currently solving a puzzle and looking for some tips on sorting by events ordered. I would like to know what exactly is the procedure I should be following. Consider this

I input a number, then there

n
inputs
each input has two events, where of for
event1 event2
, and
event1
happens before
event2
.

Consider the input

6
Eatfood Cuthair
Eatfood BrushTeeth
School EatFood
School DoHair
DoHair Meeting
Meeting Brushteeth


The output will be

school -> dohair-> eatfood -> meeting -> cuthair -> brushteeth


In that order. Since if we write everything down, school is indeed the first thing that occurs, and then dohair is second. If more than one possible ordering exists simply output one. You may assume that all events are connected in some way, and no circular dependencies exist.

What I am thinking about doing is making two arrays, one which has all
eventOne's
and all
eventTwo's
. I'm not really sure where to go from here though. I would like to do this in javascript. Thanks! Any hints or algorithms are suggested

Another Input

6
vote_140_prof announce_140_prof
vote_140_prof first_day_of_classes
dev_shed_algo vote_140_prof
dev_shed_algo do_hair
do_hair big_meeting
big_meeting first_day_of_classes


Output

dev_shed_algo do_hair vote_140_prof big_meeting announce_140_prof first_day_of_classes


I found the solution file on my computer, its in python which I don't know, but hopefully this will help others understand the problem

from collections import defaultdict

def toposort(graph, roots):
res = [i for i in roots]
queue = [i for i in roots]
while queue:
for i in graph[queue.pop(0)]:
if i not in res:
res.append(i)
queue.append(i)
return res

graph = defaultdict(set)
a_set = set()
b_set = set()

for i in range(int(input())):
a, b = input().split()
a_set.add(a)
b_set.add(b)
graph[a].add(b)

print(" ".join(i for i in toposort(graph, a_set - b_set)))


My attempt

var words =
'vote_140_prof announce_140_prof vote_140_prof first_day_of_classes devshed_algo vote_140_prof dev_shed_algo do_hair do_hair big_meeting big_meeting first_day_of_classes';

var events = words;

events = events.split(/\s+/);
console.log(events);

var obj = {};
for (var i = 0 ; i < events.length ; i++)
{
var name = events[i];
if(obj[name] === undefined )
{
obj[name] = [];
}

obj[name].push(events[i%2 === 1 ? i-1 : i+1]);
}
console.log(obj);


FORMATING

function sequenceEvents(pairs){
var edges = pairs.reduce(function(edges,pair){
edges.set(pair[0],[]).set(pair[1],[]);
new Map();
});

pairs.forEach(function(edges,pair){

edges.set(pair[0],[]).set(pair[1],[]);

});

var result = [];

while(edges.size){
var children = new Set([].concat.apply([],[...edges.value()]));
var roots = [...edges.keys()].filter(function(event){
!children.has(event);
});

if(!roots.length) throw "Cycle detected";
roots.forEach(function(root){
result.push(root);
edges.delete(root);

});

}

return result;

}

Answer

The Python algorithm is not correct. It will fail for this input:

3
A B
A C
C B

It will output:

A, B, C

...which conflicts with the last rule. This is because it wrongly assumes that the children of any root-event can be safely added to the result, and depend on no other events. In the above case, it will identify A as root, and B and C as its children. Then it will pop of C from that list, and add it to the result, without seeing that C depends on B, which is not in the result yet.

As others have noted, you need to make sure the capitalisation is consistent. Brushteeth and BrushTeeth are considered different events. The same is true for EatFood and Eatfood.

I provide here a solution. I hope the inline comments explain well enough what is happening:

function sequenceEvents(pairs) {
    // Create a Map with a key for each(!) event, 
    // and add an empty array as value for each of them.
    var edges = pairs.reduce(
        // Set both the left and right event in the Map 
        //   (duplicates get overwritten)
        (edges, pair) => edges.set(pair[0], []).set(pair[1], []),
        new Map() // Start with an empty Map
    );
    // Then add the children (dependent events) to those arrays:
    pairs.forEach( pair => edges.get(pair[0]).push(pair[1]) );

    var result = [];
    // While there are still edges...
    while (edges.size) {
        // Get the end points of the edges into a Set
        var children = new Set( [].concat.apply([], [...edges.values()]) );
        // Identify the parents, which are not children, as roots
        var roots = [...edges.keys()].filter( event => !children.has(event) );
        // As we still have edges, we must find at least one root among them.
        if (!roots.length) throw "Cycle detected";
        roots.forEach(root => {
            // Add the new roots to the result, all events they depend on
            // are already in the result:
            result.push(root);
            // Delete the edges that start with these events, since the
            // dependency they express has been fulfilled:
            edges.delete(root);
        });
    }
    return result;
}


// I/O
var input = document.querySelector('#input');
var go = document.querySelector('#go');
var output = document.querySelector('#output');

go.onclick = function() {
    // Get lines from input, ignoring the initial number
    // ... then split those lines in pairs, resulting in
    // an array of pairs of events
    var pairs = input.value.trim().split(/\n/).slice(1)
                     .map(line => line.split(/\s+/));
    var sequence = sequenceEvents(pairs);
    output.textContent = sequence.join(', ');
}
Input:<br>
<textarea id="input" rows=7>6
EatFood CutHair
EatFood BrushTeeth
School  EatFood
School  DoHair
DoHair   Meeting
Meeting BrushTeeth
</textarea>
<button id="go">Sequence Events</button>
<div id="output"></div>

Comments