cresjoy - 6 months ago 26

Javascript Question

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`

each input has two events, where of for

`event1 event2`

`event1`

`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`

`eventTwo's`

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

`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);

`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>
```