[Problem Solving #5] User-Friendly Manuals

[wolfsinner]

Problem #5 - User-Friendly Manuals

 

So here's Problem #5 of the series. I used a problem from the Portuguese Inter-University Programming Tournament.
Another graph problem! I hope you guys aren't sick of them.
 
Problem Description:
 
(This problem was a part of the 2012 edition of the Portuguese Inter-University Programming Tournament. You can download the original PDF file here.)

Manuals are often difficult to read because of the order in which new concepts appear. Let us assume that the part of the manuals we are interested in is a permutation of a set of entries.
An entry has a (unique) keyword and a description, which can explicitly refer to other entries. We say that an entry e₂ depends on an entry e₁ when the description of e₂ mentions e₁. If that is the case, e₁ must occur before e₂ in the permutation, that is, e₁ is printed before e₂. Remark that dependencies between entries are guaranteed to be cycle-free.
For the sake of readability, two additional rules are considered to define the user-friendliest permutation of a set of entries. Let then e₁ and e₂ be two entries that could be printed at some point according to the existent dependencies.

• (a) First, ties are broken by dependency proximity.
  For every entry e, let δ(e) be the set of entries on which e depends. Entry e₁ is printed before e₂ if there is an entry e'₁∈ δ(e₁) that occurs after any entry e'₂ ∈ δ(e₂) in the permutation.
   
• (b) Then, ties are broken by keyword order.
  If rule (a) was not decisive and there is still a tie between e₁ and e₂, e₁ is printed before e₂ provided the keyword of e₁ is less than the keyword of e₂.

Let us see an example with the entries and the dependencies depicted in the figure below.
From now on, entry descriptions are omitted and entry keywords are integers (and compared as integers in the context of rule (b)). An edge from e₁ to e₂ means that e₂ depends on e₁.
 

 
The following table shows that 0 1 2 6 is the beginning of the corresponding user-friendliest permutation. Since entries 0, 1, 3 and 8 do not depend on any entry, rule (a) cannot determine the first two selections, which are justified by rule (b). The third selection is entry 2 because 2 depends on 1, 1 was the previous selection, and all the entries on which 3 (repectively, 8) depends, which are none, appear before 1. Then, when dependencies allow 3, 6, 7 and 8 to be chosen, rule (a) eliminates entries 3 and 8, and the tie between 6 and 7 is broken by rule (b).
 

 
Task
Given the set of entries and the set of dependencies, the goal is to compute the user-friendliest permutation of the entries.
 
Input:
 
(You can download the zip file containing all of the input files here.)
 
The first line of the input contains two integers, E and D, separated by a single space. E is the number of entries and D is the number of dependencies. Entries are identified by integers, ranging from 0 to E - 1.
Each of the following D lines contains two integers, e₁and e₂, which indicate that entry e₂depends on entry e₁. The two integers are separated by a single space.

Input example
10 8
3 4
8 5
3 5
4 9
5 9
1 2
2 7
2 6
 
(All of the input data is too large to place here, so please use the zip file.)
 
Output:
The output has a single line with the user-friendliest permutation of the entries. Any two consecutive integers are separated by a single space.
The output must end with a line break.
The last number in the permutation should not have a space after it.

Output example
0 1 2 6 7 3 4 8 5 9
 
How to test your solution:
To submit your output solutions you need to run your code with each of the input files provided in the zip file, and place your output in the appropriate text box.
So your program's output with input from file "input1.txt" should be placed in the "Output 1" box.
 
I recommend downloading the zip file, and using command-line input redirection to send the file contents into the standard input stream of your program, and the output into the standard output stream. In Windows, Linux or Mac OS, you would do something like:
[command to run your program] < inputN.txt > outputN.txt
You can submit your output solutions through the problem solving gateway here.
 
Final notes:

• Create your account at the gateway with the same username as the one you use at the forums.
• Include your code in spoiler tags, so that the thread isn't cluttered with code.
• If you're having trouble solving the problem, ask the community for help! You may learn a lot from them.
• Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it.
• Please don't share the output solution if you've solved the problem.
• If the problem description isn't clear, please ask for further explanation!

[wolfsinner]

Rule (a) might sound confusing. I'll elaborate.

It formalizes the idea that if you've studied a certain topic recently, you should continue studying whatever depends on that first if possible, before moving to something else.

 

So if I've studied Programming 2, and Programming 3 depends on Programming 2, but all requirements are met for me to study Artificial Intelligence as well, I should still study Programming 3 first because Programming 2 is "still fresh in my memory". Hope that doesn't sound confusing.

[fizzlesticks]

Another stupid mistake when submitting...I think I copied my timing from one of the outputs, then 40 minutes of trying to figure out what I did wrong when there was nothing .

 

Code is kind of slow for the larger input, I'm pretty sure this can be done with a topological sort but I thought of that too late.

def ruleA(possibleChoices,readOrder,parents,children):    possible = []    if readOrder:        for n in reversed(readOrder):            possible.extend([x for x in children[n] if x not in readOrder and x in possibleChoices])            if possible:                break        if not possible:        possible = list(possibleChoices)    return possible    def ruleB(possibleChoices):    return min(possibleChoices)def main():    numEntries, numDependencies = [int(x) for x in input().split()]    entries = [x for x in range(0,numEntries)]    children = [set() for i in range(0,numEntries)]    parents = [set() for i in range(0,numEntries)]    read = set()    readOrder = []    for i in range(0,numDependencies):        entry, depends = [int(x) for x in input().split()]        parents[depends].add(entry)        children[entry].add(depends)    possibleChoices = [x for x in entries if not parents[x]]    while possibleChoices:        possible = ruleA(possibleChoices,readOrder,parents,children)        c = -1        if len(possible) > 1:            c = ruleB(possible)        else:            c = possible[0]        read.add(c)        readOrder.append(c)        entries.remove(c)                    possibleChoices = [x for x in entries if read.issuperset(parents[x])]    readOrder = [str(x) for x in readOrder]    print(" ".join(readOrder))if __name__ == "__main__":    from timeit import Timer    t = Timer(lambda: main())    print(t.timeit(number=1))

[Tigerbomb8]

Can you please do some beginner problems.. 

[wolfsinner]

Another stupid mistake when submitting...I think I copied my timing from one of the outputs, then 40 minutes of trying to figure out what I did wrong when there was nothing .

 

Code is kind of slow for the larger input, I'm pretty sure this can be done with a topological sort but I thought of that too late.

 

Yep, the optimal solution is done with topological sorting.

 

I removed your first submission since it was incorrect for a silly reason. hehe

 

 

Can you please do some beginner problems.. 

 

I might do a sub-series for simpler problems, but you should consider trying to solve these ones, they're not that hard. Most of them are graph theory based, and graph theory is awesome. It is also extremely important for a programmer to know. There are tips in the discussions topics, and if you read a bit on what is discussed you'll learn a lot.

[Nuluvius]

Can you please do some beginner problems.. 

 

I might do a sub-series for simpler problems, but you should consider trying to solve these ones, they're not that hard. Most of them are graph theory based, and graph theory is awesome. It is also extremely important for a programmer to know. There are tips in the discussions topics, and if you read a bit on what is discussed you'll learn a lot.

 

This may not be the most appropriate thread to discuss this in, it may be more appropriate to discuss it in the original suggestion thread instead?

 

That aside however I am going to play devil's advocate here and agree with @Tigerbomb8. There are a great many facets to programming and we have only been dealing with one so far, this being algorithms as I see it. Personally speaking, due to my own natural dispositions this particular area does not come easily to me by any means.

 

We are all unique and have come from unique circumstances which have shaped our current abilities, strengths and weaknesses. To state that it is not that hard is to subjectively address a specific area of strength perhaps? We may benefit our audience by diversifying our exploration of problems out into other areas as well; architecture and object design for example. Furthermore I also agree that we need some easier sub sections to further encourage and cultivate interest as we seem to be a little exclusive right now.

 

All of that said I feel I have benefited a huge amount both professionally and personally by facing my demons here with these particular problems. I have learned a great deal and as a result now have a number of extra tools to draw upon as well as understanding my own weaknesses a little better. I am also enjoying the community that has been brought together as a result of these endeavours. I am very grateful to @wolfsinner for all of this.

 

 

[wolfsinner]

Alright, I've continued this discussion in the index thread. Thanks everyone.

[fizzlesticks]

A much improved solution using a topological sort, went from taking 1 minute on input 6 to .06 seconds.

 

 

edit: Just for funsies I decided to see how much faster it would be in C++, turns out it's about 4x faster without trying to do any real optimization.

def toposort(entries,parents,children):    readOrder = []    possible = [x for x in entries if not parents[x]]    while possible:        n = possible.pop(0)        readOrder.append(n)        new = []        for c in children[n]:            parents[c].remove(n)            if not parents[c]:                new.append(c)        new = sorted(new,reverse=True)        for i in new:            possible.insert(0,i)    return readOrderdef main():    numEntries, numDependencies = [int(x) for x in input().split()]    entries = [x for x in range(0,numEntries)]    children = [[] for i in range(0,numEntries)]    parents = [[] for i in range(0,numEntries)]    for i in range(0,numDependencies):        entry, depends = [int(x) for x in input().split()]        parents[depends].append(entry)        children[entry].append(depends)    readOrder = toposort(entries,parents,children)    readOrder = [str(x) for x in readOrder]    print(" ".join(readOrder))if __name__ == "__main__":    from timeit import Timer    t = Timer(lambda: main())    print(t.timeit(number=1))

#include <iostream>#include <vector>#include <stack>#include <algorithm>#include "FEClock.h"using namespace std;struct greater{	bool operator()(const int& a, const int& b) const { return a > b; }};vector<int> toposort(vector<int>& entries, vector<vector<int>>& parents, vector<vector<int>>& children){	vector<int> readOrder;	stack<int> possible;	sort(entries.begin(), entries.end(), greater());	for (vector<int>::iterator it = entries.begin(); it != entries.end(); ++it)	{		if (parents[*it].empty())		{			possible.push(*it);		}	}	while(!possible.empty())	{		int n = possible.top();		possible.pop();		readOrder.push_back(n);		vector<int> newNodes;		for(vector<int>::iterator it = children[n].begin(); it != children[n].end(); ++it)		{			vector<int>::iterator pos = find(parents[*it].begin(), parents[*it].end(), n);			parents[*it].erase(pos);						if (parents[*it].empty())			{				newNodes.push_back(*it);			}		} 		sort(newNodes.begin(),newNodes.end());		for(vector<int>::reverse_iterator it = newNodes.rbegin(); it != newNodes.rend(); ++it)		{			possible.push(*it);		}	}	return readOrder;}int main(){	FEClock::init();	FEClock clock;	clock.update();	int numEntries, numDependencies;	cin >> numEntries >> numDependencies;	vector<int> entries(numEntries);	vector<vector<int>> parents(numEntries), children(numEntries);	for(int i=0; i<numEntries; ++i)	{		entries[i] = i;	}	int entry, depends;	for(int i=0; i<numDependencies; ++i)	{		cin >> entry >> depends;		parents[depends].push_back(entry);		children[entry].push_back(depends);	}	vector<int> readOrder = toposort(entries,parents,children);	for(vector<int>::iterator it = readOrder.begin(); it != readOrder.end(); ++it)	{		if(it != readOrder.begin())		{			cout << " ";		}		cout << *it;	}	cout << endl;	float dt = clock.update();	cout << dt << endl;	return 0;}

[Nuluvius]

All done! 

 

MainViewModel (one thread per file)

GraphWalker

EntryRelations

ListToStringConverter (converting the sorted list to a string is trivial and done at the view level using an IValueConverter with a StringBuilder)

        private void ProcessFiles()        {            IsBusy = true;            _cs = new CancellationTokenSource();            UpdateCommands();            Task.Run(                () => Task.WaitAll(Directory.GetFiles(InputDirectory, "*.txt").Select(f => Task.Run(                    () =>                    {                        var rawText = File.ReadAllText(f).Trim().Split(new[] { Environment.NewLine, "\n" }, StringSplitOptions.None).ToList();                        var result = new Result { Index = f };                        var gw = new GraphWalker(rawText);                        _cs.Token.ThrowIfCancellationRequested();                        result.Order = gw.ComputeOrdering();                        AddResult(result);                    }, _cs.Token)).ToArray()), _cs.Token).ContinueWith(                        _ =>                        {                            IsBusy = false;                            UpdateCommands();                        });        } 

    class GraphWalker    {        private const char Delimiter = ' ';        private readonly EntryRelations _entryRelations;        public GraphWalker(IList<string> rawData)        {            _entryRelations = new EntryRelations(int.Parse(rawData[0].Split(Delimiter)[0]));            rawData.RemoveAt(0);            foreach (var item in rawData.Select(line => line.Split(Delimiter)))            {                _entryRelations.AddRelation(int.Parse(item[0]), int.Parse(item[1]));            }        }        public List<int> ComputeOrdering()        {            return _entryRelations.Sort(                (entries, parents, children) =>                    {                        var result = new List<int>();                        var permutations = new Stack<int>();                        entries.Reverse();                        foreach (var i in entries.Where(e => parents[e].Count <= 0))                        {                            permutations.Push(i);                        }                        while (permutations.Count > 0)                        {                            var nextItems = new List<int>();                            var current = permutations.Pop();                            result.Add(current);                                                        foreach (var i in children[current])                            {                                parents[i].Remove(current);                                if (parents[i].Count <= 0)                                {                                    nextItems.Add(i);                                }                            }                            nextItems.Sort();                            nextItems.Reverse();                            foreach (var i in nextItems)                            {                                permutations.Push(i);                            }                        }                        return result;                    });        }    } 

    class EntryRelations    {        public EntryRelations(int limit)        {            Entries = Enumerable.Range(0, limit).ToList();            Parents = new Dictionary<int, List<int>>();            Children = new Dictionary<int, List<int>>();            for (var i = 0; i < limit; i++)            {                Parents.Add(i, new List<int>());                Children.Add(i, new List<int>());            }        }        public Dictionary<int, List<int>> Parents { get; set; }        public Dictionary<int, List<int>> Children { get; set; }        public List<int> Entries { get; set; }        public void AddRelation(int entry, int dependant)        {            Parents[dependant].Add(entry);            Children[entry].Add(dependant);        }        public List<int> Sort(Func<List<int>, Dictionary<int, List<int>>, Dictionary<int, List<int>>, List<int>> algorithm)        {            return algorithm(Entries, Parents, Children);        }    } 

    class ListToStringConverter : IValueConverter    {        public object Convert(object value, Type targetType, object parameter, CultureInfo culture)        {            var intList = (List<int>)value;                      var result = new StringBuilder();            for (var i = 0; i < intList.Count; i++)            {                result.Append(i <= 0 ? intList[i].ToString(CultureInfo.InvariantCulture) : string.Format(" {0}", intList[i]));            }            return result.ToString();        }        public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)        {            throw new NotImplementedException();        }    } 

[gauvinic]

Err... So, I finally completed it (at least I think...). Decided to try out a language I've never programmed in before, so I chose Python. 

Gave up after writing interpretFile() because I thought it wasn't storing the information correctly (turns out it was all along, but I wasn't

printing it out in a way that I could recognize that...) Came back to it today, and finally figured out that it worked. Finished with a 

topological sort, and ran it with the example input. Gave the correct output. I'm refraining from turning it in because I don't believe the

zip actually contains the correct files. (t1.txt isn't formatted correctly and the first two numbers listed are an impossible combination based

on the constraints) Also can't login to the gateway on my desktop bc I forgot the password I used there. Anyways, I'm glad I dived into python

with this. Taught me alot about lists and how its for loops work.

 

def interpretFile():    fileName = input("Enter filename without extension here: ")    fileName += ".txt"    with open(fileName, 'r') as f:        lines = f.readline()        numberOfManuals, numberOfDependancies = (int(x) for x in lines.split())        data = [[] for i in range(numberOfManuals)]        for i in range(numberOfDependancies):            lines = f.readline()            e1, e2 = (int(x) for x in lines.split())            data[e2].append(e1)        for x in data:            x.sort()    return datadef topoSort(data):    possibleChoices = []    sortedEntries = []    count = 0    for x in data:        if len(x) == 0:            possibleChoices.append(count)        count+=1    while len(possibleChoices) != 0:        pos = 0        element = possibleChoices.pop(0)        for x in range(len(data)):            if data[x].count(element) == 1:                data[x].remove(element)                if len(data[x]) == 0:                    possibleChoices.insert(pos, x)                    pos+=1        sortedEntries.append(element)    return sortedEntriesdef main():    finalOrder = topoSort(interpretFile())    finalOrderString = ""    for x in finalOrder:        finalOrderString += str(x) + " "    print(finalOrderString)if __name__ == "__main__":    main() 

[fizzlesticks]

I'm refraining from turning it in because I don't believe the

zip actually contains the correct files. (t1.txt isn't formatted correctly and the first two numbers listed are an impossible combination based

on the constraints)

The files are correct but were made in Linux so they don't have a \r. Open them in anything but notepad and it should be fine.

[gauvinic]

The files are correct but were made in Linux so they don't have a \r. Open them in anything but notepad and it should be fine.

Sure enough. Thanks!

[Ciccioo]

a bit late, but today i started working on this problem and... my first submission was incorrect

the sample input works fine... i'm afraid this is going to be a pain to debug

 

edit:

that "Incorrect." label is making me experience the trauma of rejection so hard

[Ciccioo]

well alright then, i don't understand

 

consider the sample input

11 100 10 21 31 42 52 63 73 84 94 10

what is the output?

 

edit: i took one of the correct implementations here above and ran the example, and apparently the solution is

0 1 3 7 8 4 9 10 2 5 6

but that breaks rule (a) imo, or at least it breaks the explaination that @wolfsinner gave in the second post

[Ciccioo]

alright, i thought i already tried this solution and it was invalid, but apparently i'm wrong

 

#include <iostream>#include <vector>#include <queue>class entry{        private:                static size_t entryCounter;                static bool first;                size_t n, dependencies;                size_t printed;                std::priority_queue<std::pair<size_t, entry*>> satisfies;                void satisfyDependencies(){                        while(!satisfies.empty()){                                auto e = satisfies.top();                                satisfies.pop();                                e.second -> dependencies--;                                e.second -> study();                        }                }                void print(){                        if(!first) std::cout << " ";                        else  first = false;                        std::cout << n;                        printed = true;                }                bool isValid() const{                        return dependencies == 0 && !printed;                }        public:                entry(): n{entryCounter++}, dependencies{0}, printed{false} {}                void addDependency(entry& e){                        e.satisfies.push(std::make_pair(n, this));                        dependencies++;                }                void study(){                        if(!isValid()) return;                        print();                        satisfyDependencies();                }};bool operator < (const std::pair<size_t, entry*>& lhs, const std::pair<size_t, entry*>& rhs){        return lhs.first > rhs.first;}size_t entry::entryCounter = 0;bool entry::first = true;int main(){        size_t E, D;        std::cin >> E >> D;        std::vector<entry> entries(E);        while(D--){                size_t e1, e2;                std::cin >> e1 >> e2;                entries[e2].addDependency(entries[e1]);        }        for(auto& e: entries)                e.study();        std::cout << std::endl;}

 

at least this ad-hoc solution seems to be very fast, i don't think that the topological sort beats it, so i can have that satisfaction after all this rage

 

but i insist that rule (a) is the devil