CodeGolf: Trova le percorsi univoci

Question

Ecco una bella idea semplice, in questo pastebin ho postato qualche coppia di numeri. Questi rappresentano nodi di un grafo orientato. L'ingresso al stdin sarà di forma, (saranno numeri, sarò con un esempio qui)

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

così mezzi x y x è collegato ad y ( non viceversa)

Ci sono 2 percorsi in quell'esempio. a->b->c->d->e e p->q->r.

È necessario stampare tutti i percorsi unici da quello grafico L'uscita dovrebbe essere del formato

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

Note

1. Si può assumere i numeri sono scelti in modo tale che un percorso non fa intersecano l'altro (un nodo appartiene ad un percorso)
2. Le coppie sono in ordine casuale.
3. Sono più di 1 percorsi, che possono essere di diverse lunghezze.
4. Tutti i numeri sono meno di 1000.

Se avete bisogno di ulteriori informazioni, si prega di lasciare un commento. Io modificare come richiesto.

Shameless plug

Per chi ama Codegolf, si prega di Commit a Area51 per un proprio sito :) (per coloro che non godono di esso, si prega di sostenerlo e, in modo resteremo fuori strada ...)

Answer 1

Rubino - 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*'->'}

Ha preso l'idea di Nas Banov di 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 caratteri

#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("");}}

a capo non necessari non sono contati.

Comando:

$ 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

---

Versione Piuttosto:

#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

Anche se non è la risposta, il seguente script Linux traccia un grafico del file di input:

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

Graphviz installato per il comando dot, e eog è GNOME 's visualizzatore di immagini

Esegui nel file di input, gli sguardi grafico come questo:

ruotata di 90 ° e ridimensionati ( vedere originale )

Come si può vedere, il grafico di ingresso è solo un insieme di liste singolarmente-linked senza nodi condivisi e senza cicli.

Answer 4

Python

120 caratteri

Mi piace come senza sforzo si legge 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

E il risultato di correre sul campione di pasta-bin:

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 sì, finalmente una codegolf dove Lua non aspira. goodie Extra: funziona su tutto ciò che è lo spazio separato (i numeri di qualsiasi dimensione, le stringhe, ...)

La versione non golfed:

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

La versione golfed:

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 caratteri

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

Meno approccio elegante rispetto a prima, ma più corto! Ispirato da un'idea di Nas Banov di 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";}

sguardi intero file come:

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

Per eseguire:

$ php graph.php graph.txt

Versione Piuttosto:

$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

O'Caml

402 caratteri

In pratica un adattamento della versione Haskell, la cui lunghezza mi stupisce. C'è sicuramente un modo per fare meglio con Str e / o la rivisto sintassi .

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 byte

Aggiorna :

1. Generics rimossi. E a quanto pare, classe può fare con senza essere `public` (Thnx Sean)
2. Rimosso Class, sostituito da Enum. (Vedi commenti, 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);}}}