Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Goal

Sort a list of items ensuring that each item is listed after its specified dependencies.

Input

An array of arrays of integers, where each integer specifies the 0-based or 1-based index of another item that this item must come after. The input may be an array or string or anything else human readable.

For example, a 0-based input:

[
  [ 2 ],    // item 0 comes after item 2
  [ 0, 3 ], // item 1 comes after item 0 and 3
  [ ],      // item 2 comes anywhere
  [ 2 ]     // item 3 comes after item 2
]

Assume there are no circular dependencies, there is always at least one valid order.

Output

The numbers in order of dependency. An ambiguous order does not have to be deterministic. The output may be an array or text or anything else human readable.

Only one order should be given in the output, even where there are multiple valid orders.

Possible outputs for the above input include:

[ 2, 3, 0, 1 ]
[ 2, 0, 3, 1 ]

Scoring

A function or program that completes this in the least number of bytes wins the glory of acceptance. The deadline is in 6 days.

share|improve this question
4  
This is called Topological Sorting for the curious. – Robert Fraser Mar 18 at 2:58
    
The input may be an array or string or anything else human readable Just to make sure: can it be a 2D array with zeros and ones, where one indicates dependency and zero indicates no dependency? – Luis Mendo Mar 18 at 15:03
    
@DonMuesli, sorry for the late reply, but no. The idea came from code dependencies. If you added another code module, it would be irresponsible to have to modify irrelevant code modules to declare they were not dependant on this new module. – Hand-E-Food Mar 27 at 13:09
    
That totally makes sense. Shouldn't Dennis be the winner? – Luis Mendo Mar 27 at 13:25
    
Yes, he is. Sorry, late stressful night and rushing based on assumptions. – Hand-E-Food Mar 27 at 21:23
up vote 3 down vote accepted

Jelly, 8 bytes

ịÐL³ŒḊ€Ụ

This is based on the (unimplemented) depth approach from @xnor's Python answer.

Try it online!

How it works

ịÐL³ŒḊ€Ụ  Main link. Input: A (list of dependencies)

 ÐL       Apply the atom to the left until a loop is reached, updating the left
          argument with the last result, and the right argument with the previous
          left argument.
ị         For each number in the left argument, replace it with the item at that
          index in the right argument.
   ³      Call the loop with left arg. A (implicit) and right arg. A (³).
    ŒḊ€   Compute the depth of each resulting, nested list.
       Ụ  Sort the indices of the list according to their values.
share|improve this answer
    
Would these 8 characters actually be 19 bytes? – Hand-E-Food Mar 27 at 13:05
    
@Hand-E-Food Jelly uses a custom encoding (not UTF 8), so each character is a byte – Luis Mendo Mar 27 at 13:26
    
@Hand-E-Food Don Muesli is correct. Jelly uses this code page by default, which encodes all characters it understands as one byte each. – Dennis Mar 27 at 14:20
    
Thanks for clearing that up! – Hand-E-Food Mar 27 at 21:22

Pyth, 21 bytes

hf.A.e!f>xYTxkTbQ.plQ
                    Q  input
                   l   length of input array
                 .p    all permutations of [0, 1, ..., lQ-2, lQ-1]
hf                     find the first permutation for which...
    .e          Q        map over the input array with indices...
       f       b           find all elements in each input subarray where...
        >xYT                 index of dependency is greater than...
            xkT              index of item
      !                    check whether resulting array is falsy (empty)
  .A                     is the not-found check true for [.A]ll elements?

Test:

llama@llama:~$ echo '[[2],[0,3],[],[2]]' | pyth -c 'hf.A.e!f>xYTxkTbQ.plQ' 
[2, 0, 3, 1]
share|improve this answer

Python 2, 73 bytes

l=input()
f=lambda n:1+sum(map(f,l[n]))
print sorted(range(len(l)),key=f)

Sorts the vertices by their descendant count, which f computes recursively. If a vertex points to another vertex, its descendants include the pointed vertex and all of that vertex's descendants, so it has strictly more descendants. So, it is placed later than the pointed vertex in the ordering, as desired.

The descendant count of a vertex is one for itself, plus the descendant counts of each of its children. Note that a descendant can be counted multiple times if there are multiple paths leading to it.

It would have also worked to used depth rather than descendant count

f=lambda n:1+max(map(f,l[n]))

except the max would need to give 0 on an empty list.

share|improve this answer
2  
Beautiful algorithm. This would score 12 bytes in both Pyth and Jelly. – Dennis Mar 18 at 21:00

Pyth, 19 bytes

hf!s-V@LQT+k._T.plQ

Try it online: Demonstration

Explanation:

hf!s-V@LQT+k._T.plQ   implicit: Q = input list
               .plQ   all permutations of [0, 1, ..., len(Q)-1]
 f                    filter for permutations T, which satisfy:
      @LQT               apply the permutation T to Q
                         (this are the dependencies)
            ._T          prefixes of T
          +k             insert a dummy object at the beginning
                         (these are the already used elements)
    -V                   vectorized subtraction of these lists
   s                     take all dependencies that survived
  !                      and check if none of them survived
h                    print the first filtered permutation
share|improve this answer

Bash, 35 bytes

perl -pe's/^$/ /;s/\s/ $. /g'|tsort

Example run

I/O is 1-indexed. Each array goes on a separate line, with whitespace as item separator.

$ echo $'4\n1\n\n3\n1 3 2' # [[4], [1], [], [3], [1, 3, 2]]
4
1

3
1 3 2
$ bash tsort <<< $'4\n1\n\n3\n1 3 2'
3
4
1
2
5

How it works

tsort – which I learned about in @DigitalTrauma's answer – reads pairs of tokens, separated by whitespace, that indicate a partial ordering, and prints a total ordering (in form of a sorted list of all unique tokens) that extends the aforementioned partial ordering.

All numbers on a specific line are followed by either a space or a linefeed. The s/\s/ $. /g part of the Perl command replaces those whitespace characters with a space, the line number, and another space, thus making sure that each n on line k precedes k.

Finally, if the line is empty (i.e., consists only of a linefeed), s/^$/ / prepends a space to it. This way, the second substitution turns an empty line k into k k, making sure that each integer occurs at least once in the string that is piped to tsort.

share|improve this answer
    
Right, ok. I think you groked tsort better/faster than I did :) Thanks for the extra explanation. – Digital Trauma Mar 18 at 18:24

Bash + coreutils, 20 80

nl -v0 -ba|sed -r ':;s/(\S+\s+)(\S+) /\1\2\n\1 /;t;s/^\s*\S+\s*$/& &/'|tsort|tac

Input as space-separated lines, e.g.:

2
0 3

2
  • nl adds zero-based indices to all lines
  • sed splits depedency lists into simple dependency pairs, and makes incomplete dependencies dependent on themselves.
  • tsort does the required topological sort
  • tac puts the output reverse order

Ideone. Ideone with @Dennis' testcase

share|improve this answer

Python 2, 143 118 116 bytes

A slightly more random approach.

from random import*
l=input()
R=range(len(l))
a=R[:]
while any(set(l[a[i]])-set(a[:i])for i in R):shuffle(a)
print a

Edits:

  • fixed it, and actually saved some bytes too.
  • Saved 2 bytes (thanks @Dennis)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.