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()

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;

}
``````

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], []),
);
// 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);
// 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>``````

Source (Stackoverflow)