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

Yasukoyataghan

Great golf. Unfortunately, I’m busy so I can’t participate. So here’s a hint: this is an all-pairs shortest path problem which can be solved in four lines of pseudocode (using the very elegant algorithm of Floyd and Warshall). Matrix multiplication could also be used but this doesn’t preserve the path, it just saves whether there is one. – Multistage

Since when are CodeGolf questions not allowed on stackoverflow? – Backplate

Do you have a solution for us to check against? – Breann

Well, Jeff change its mind. Code golf is welcome on SO again, at least for now. meta.stackexchange.com/questions/73332/… – Conferee

FYI this was migrated back from programmers. Apologies for the confusion: Code Golf belongs on SO, until such time as the Area 51 Code Golf proposal gets traction, and we've clarified all the public statements on this. – Centurion

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}

Misapply

You should annotate the code a little bit. It's practically impossible to follow. – Cayman

@davidk01, it's rather simple task and solution. I really don't know, what to annotate here ) – Laundryman

@Nakilon: Can you explain *$<, please? It seems to grab the STDIN contents and split it by new lines, but I can't work out how it does it? – Misapply

@Ashley Williams, thanks for uncompressing my code, because I'm too lazy to do it ) I can't explain with details, how does [*$<] work. $< by default is STDIN, and I've found it once on SO in some question about golf tricks. BTW, what anonymous guy and why gave minus to my answer? ) – Laundryman

@Nakilon: No problem, sorry for hijacking your submission! :P And I figured out how [*$<] works, see above. It's pretty cool really, albeit a little cryptic, but absolutely perfect for code-golf! ;) – Misapply

Answer 2

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

Blameless

Answer 3

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;
}

Larianna

@Joey, The Numbers are less than 1000, never equal to it. So replace 1001 by 1e3. Saves 1 byte. :) – Yasukoyataghan

@Joey, I'm not sure about C89, but if you made those arrays global, wont they be initialized to zero by default. – Yasukoyataghan

@st0le: I'm using 0 as a "null" position, and I increment numbers on input so they will be 1 <= n <= 1000 rather than 0 <= n <= 999. You didn't specify a lower bound, so I assumed it was 0. If it were 1, the solution could be shorter. In any case, I don't have much competition, it seems :-) – Larianna

@Joey, I'd give it some time...I'll try posting a solution of my own this weekend. – Yasukoyataghan

Answer 4

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.

Larianna

It would be nice for you to upload the full size image somewhere and link to it from here. – Radford

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

Countermove

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

Interlock

i've asked the mods to close this question, would you please post your anwer on the other question, sorry for the trouble. thank you :) – Yasukoyataghan

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";
    }
}

Breann

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

Paterson

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

Yasukoyataghan

Here's the same class reduced to 345 chars (if you rename Main to M): ideone.com/jNjjP – Mutualism

@Sean, Updated. Thanks :) If you have more suggestions, You're welcome to edit it yourself, if you please. Also, ideone can do with M class, i discovered. – Yasukoyataghan

enum M{M;{code}} tends to work too, and is significantly shorter. – Decapitate

@Nabb, without main, won't it just crash with an exception? – Yasukoyataghan

@st0le: ideone.com/uJSC5 -- It's a non-zero exit code, but it still prints the expected output. – Decapitate