CodeGolf: Find the Unique Paths

Question

Here's a pretty simple idea, in this pastebin I've posted some pair of numbers. These represent Nodes of a directed graph. The input to stdin will be of the form, (they'll be numbers, i'll be using an example here)

c d
q r
a b
b c
d e
p q

so x y means x is connected to y (not viceversa)

There are 2 paths in that example. a->b->c->d->e and p->q->r.

You need to print all the unique paths from that graph The output should be of the format

a->b->c->d->e
p->q->r

Notes

1. You can assume the numbers are chosen such that one path doesn't intersect the other (one node belongs to one path)
2. The pairs are in random order.
3. They are more than 1 paths, they can be of different lengths.
4. All numbers are less than 1000.

If you need more details, please leave a comment. I'll amend as required.

Shameless-Plug

For those who enjoy Codegolf, please Commit at Area51 for its very own site:) (for those who don't enjoy it, please support it as well, so we'll stay out of your way...)

Answer 1

Ruby — 132 125 87

h=Hash[a=[*$<].map(&:split)]
1000.times{a.map!{|i|i+[h[i[-1]]]-[nil]}}
puts a.sort_by{|i|-i.size}.uniq(&:last).map{|i|i*'->'}

Took Nas Banov's idea of h.keys-h.values:

h=Hash[[*$<].map &:split]
puts (h.keys-h.values).map{|i|s=i
s+='->'+i=h[i]while h[i];s}

Answer 2

C89 - 212 204 characters

#define M 1001
int t[M],r[M],a,b;main(){while(scanf("%d%d",&a,&b)>0)t[a+1]=r[a+1]=b+1;
for(a=1;a<M;a++)r[t[a]]=0;for(a=1;a<M;a++)if(r[a]){printf("%d",a-1);
for(b=t[a];b;b=t[b])printf("->%d",b-1);puts("");}}

Unnecessary newlines are not counted.

Command:

$ wget -O - http://pastebin.com/download.php?i=R2PDGb2w | ./unique-paths

Output:

477->4->470->350->401->195->258->942->263->90->716->514->110->859->976->104->119->592->968->833->731->489->364->847->727
784->955->381->231->76->644->380->861->522->775->565->773->188->531->219->755->247->92->723->726->606
821->238->745->504->99->368->412->142->921->468->315->193->674->793->673->405->185->257->21->212->783->481->269

---

Pretty version:

#include <stdio.h>

int main(void)
{
    /* Note: {0} initializes all items to zero. */
    int target[1001] = {0}; /* If a → b, then target[a+1] == b+1. */
    int root[1001]   = {0}; /* If a is a root, then root[a+1] != 0. */
    int a, b, i, next;

    /* Read input numbers, setting the target of each node.
       Also, mark each source node as a root. */
    while (scanf("%d %d", &a, &b) == 2)
        target[a+1] = root[a+1] = b+1;

    /* Mark each node that is pointed to as not a root. */
    for (i = 1; i <= 1000; i++)
        root[target[i]] = 0;

    /* For each root node, print its chain. */
    for (i = 1; i <= 1000; i++) {
        if (root[i] != 0) {
            printf("%d", i-1);
            for (next = target[i]; next != 0; next = target[next])
                printf("->%d", next-1);
            printf("\n");
        }
    }

    return 0;
}

Answer 3

Although not the answer, the following Linux script draws a graph of the input file:

cat FILE | (echo "digraph G {"; awk '{print "\t" $1 "-> " $2;}'; echo "}") \
   | dot -Tpng > out.png && eog out.png

You'll need Graphviz installed for the dot command, and eog is GNOME's image viewer.

Run on the input file, the graph looks like this:

Rotated 90° and scaled down (see original)

As you can see, the input graph is just a collection of singly-linked lists with no shared nodes and no cycles.

Answer 4

Python

120 characters

I like how effortless it reads in Python:

import sys
d=dict(map(str.split,sys.stdin))
for e in set(d)-set(d.values()):
    while e in d:print e,'->',;e=d[e]
    print e

And the result from running over the pasta-bin sample:

784 -> 955 -> 381 -> 231 -> 76 -> 644 -> 380 -> 861 -> 522 -> 775 -> 565 -> 773 -> 188 -> 531 -> 219 -> 755 -> 247 -> 92 -> 723 -> 726 -> 606
821 -> 238 -> 745 -> 504 -> 99 -> 368 -> 412 -> 142 -> 921 -> 468 -> 315 -> 193 -> 674 -> 793 -> 673 -> 405 -> 185 -> 257 -> 21 -> 212 -> 783 -> 481 -> 269
477 -> 4 -> 470 -> 350 -> 401 -> 195 -> 258 -> 942 -> 263 -> 90 -> 716 -> 514 -> 110 -> 859 -> 976 -> 104 -> 119 -> 592 -> 968 -> 833 -> 731 -> 489 -> 364 -> 847 -> 727

Answer 5

Lua, 166 bytes

Ow yea, finaly a codegolf where Lua doesn't suck. Extra goodie : works on anything that is space separated (numbers of whatever size, strings, ...)

The Non-golfed version:

-- Read in a file from stdout filled with pairs of numbers representing nodes of a (single-)directed graph.
-- x y means x->y (but not y->x)
g={}t={}w=io.write
i=io.read"*a" -- read in numbers from stdin
for x,y in i:gmatch"(%w+) (%w+)" do -- parse pairs 
    t[y]=1 -- add y to destinations (which never can be a starting point)
    g[x]=y
end
for k,v in pairs(g) do -- go through all links
    if not t[k] then   -- only start on starting points         
        w(k)           -- write the startingpoint
        while v do     -- as long as there is a destination ...
            w('->',v)  -- write link
            v=g[v]     -- next destination
        end
        w'\n'
    end
end

The golfed version:

g={}t={}w=io.write for x,y in io.read"*a":gmatch"(%w+) (%w+)"do t[y]=1 g[x]=y end for k,v in pairs(g)do if not t[k]then w(k)while v do w('->',v)v=g[v]end w'\n'end end

Answer 6

Haskell — 174 142 137 133 characters

import List
a#m=maybe[](\x->"->"++x++x#m)$lookup a m
q[f,s]=f\\s>>=(\a->a++a#zip f s++"\n")
main=interact$q.transpose.map words.lines

Ungolfed:

import Data.List

type Node = String

follow :: Node -> [(Node,Node)] -> String
follow node pairs = maybe "" step $ lookup node pairs
    where step next = "->" ++ next ++ follow next pairs

chains :: [[Node]] -> String
chains [firsts,seconds] = concatMap chain $ firsts \\ seconds
    where chain node = node ++ follow node pairs ++ "\n"
          pairs = zip firsts seconds

process :: [String] -> String
process = chains . transpose . map words

main :: IO ()
main=interact $ process . lines

Less elegant approach than before, but shorter! Inspired by Nas Banov's idea of h.keys-h.values

Answer 7

PHP - 155

foreach(file($argv[1])as$x){$x=explode(' ',$x);$g[$x[0]+0]=$x[1]+0;}
foreach($g as$a=>$b)if(!in_array($a,$g)){echo$a;while($b=$g[$b])echo"->$b";echo"\n";}

Whole file looks like:

<?php
error_reporting(0);
foreach(file($argv[1])as$x){$x=explode(' ',$x);$g[$x[0]+0]=$x[1]+0;}
foreach($g as$a=>$b)if(!in_array($a,$g)){echo$a;while($b=$g[$b])echo"->$b";echo"\n";}

To run:

$ php graph.php graph.txt

Pretty version:

$lines = file($argv[1]);
foreach ($lines as $line) {
    $vertexes = explode(' ',$line);
    $graph[$vertexes[0]+0] = $vertexes[1]+0; // the +0 forces it to an integer
}
foreach ($graph as $a => $b) {
    //searches the vertexes that are pointed to for $a
    if (!in_array($a,$graph)) {
        echo $a;
        for ($next = $b; isset($graph[$next]); $next = $graph[$next]) {
            echo "->$next";
        }
        //because the loop doesn't run one last time, like in the golfed version
        echo "->$next\n";
    }
}

Answer 8

Ocaml

402 characters

Basically an adaptation of the Haskell version, the length of which amazes me. There's certainly a way to do better with Str and/or the revised syntax.

open List;;open String;; let q(a,b,p)=print_string(p^b^"\n")in let rec f(a,b,p)=function []->[a,b,p]|(x,y,q)::l when x=b->f(a,y,p^q)l|(x,y,q)::l when y=a->f(x,b,q^p)l|h::t->h::(f(a,b,p)t)in let t s=let i=index s ' 'in let h=sub s 0 i in h,sub s (i+1) ((length s) -i-1),h^"->"in let s=ref []in try while true do let l=read_line ()in s:=l::!s done with End_of_file->List.iter q(fold_right f(map t !s)[])

Ungolfed:

open List;;
open String;;
let print (a,b,p) = print_string (p^b^"\n") in
let rec compose (a,b,p) = function
   [] -> [a,b,p]
  |(x,y,q)::l when x=b->compose (a,y,p^q) l
  |(x,y,q)::l when y=a->compose (x,b,q^p) l
  |h::t->h::(compose(a,b,p) t) in
let tokenize s = let i = index s ' ' in
          let h =  sub s 0 i in
          h,sub s (i+1) ((length s) -i-1),h^"->" in
let lines = ref [] in
try
  while true do
    let l = read_line () in
    lines := l::!lines
  done
with
    End_of_file-> List.iter print (fold_right compose (map tokenize !lines) [])

Answer 9

Java

372 337 304 bytes

Update :

1. Removed Generics. And apparently, class can do with without being `public` (Thnx Sean)
2. Removed Class, replaced by Enum. (See Comments, Thnx Nabb)

import java.util.*;enum M{M;{Scanner s=new Scanner(System.in);final Map g=new HashMap();while(s.hasNext()){g.put(s.nextInt(),s.nextInt());}for(int a:new HashSet<Integer>(g.keySet()){{removeAll(g.values());}}){while(g.containsKey(a)){System.out.print(a+"->");a=(Integer)g.get(a);}System.out.println(a);}}}