CodeGolf: Trouver les chemins d'accès uniques

StackOverflow https://stackoverflow.com/questions/4551054

Question

Voici une idée assez simple, dans cette pastebin J'ai posté une paire de chiffres. Ceux-ci représentent des noeuds d'un graphe orienté. L'entrée à stdin sera de la forme, (ils seront chiffres, je vais utiliser un exemple ici) 

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

so moyens de x y x est connecté à y ( pas viceversa)

Il y a 2 chemins dans cet exemple. a->b->c->d->e et p->q->r.

Vous devez imprimer tous les chemins d'accès uniques à partir de ce graphique La sortie devrait être du format 

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

Remarques

  1. Vous pouvez supposer les chiffres sont choisis de telle sorte qu'un chemin ne pas recoupé l'autre (un noeud appartient à un chemin)
  2. Les paires sont dans un ordre aléatoire.
  3. Ils sont plus de 1 chemins, ils peuvent être de différentes longueurs.
  4. Tous les chiffres sont inférieurs à 1000.

Si vous avez besoin de plus de détails, s'il vous plaît laisser un commentaire. Je modifierons au besoin.

Shameless Plug

Pour ceux qui aiment Codegolf, s'il vous plaît engager à Area51 pour son propre site :) (pour ceux qui ne bénéficient pas, s'il vous plaît soutenir aussi bien, donc nous allons rester sur votre chemin ...)

Était-ce utile?

La solution

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

A pris l'idée de Nas Banov de 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}

Autres conseils

C89 - 212 204 caractères 

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

les nouvelles lignes inutiles ne sont pas comptés.

Commande: 

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

Sortie: 

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

Version Jolie: 

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

Bien que pas la réponse, le script Linux suivant dessine un graphique du fichier d'entrée: 

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

Vous aurez besoin Graphviz installé pour la commande dot et eog est GNOME 's visionneuse d'images

Exécuter sur le fichier d'entrée, le look graphique comme celui-ci:

pivotées de 90 ° et mis à l'échelle vers le bas ( voir originale)

Comme vous pouvez le voir, le graphique d'entrée est juste une collection de listes simplement liées sans noeuds partagés et pas de cycles.

Python

120 caractères

Je aime la façon dont il lit sans effort en 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

Et le résultat de l'exécution sur l'échantillon-bac à pâtes: 

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

Lua, 166 octets

Ow oui, un codegolf où finaly Lua ne suce pas. goodie supplémentaire: fonctionne sur tout ce qui est séparés par un espace (nombre de toute taille, chaînes, ...)

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

Haskell - 174 142 137 133 caractères 

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

approche moins élégante que jamais, mais plus court! Inspiré par l'idée de Nas Banov de h.keys-h.values

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

ressemble fichier entier comme: 

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

Pour exécuter: 

$ php graph.php graph.txt

Version Jolie: 

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

Ocaml

402 caractères

En fait une adaptation de la version Haskell, dont la longueur me stupéfie. Il y a certainement un moyen de faire mieux avec Str et / ou la syntaxe révisée . 

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

Java

372 337 304 octets

Mise à jour :

  1. Génériques RETIRE. Et apparemment, la classe peut faire avec sans être `public` (Thnx Sean)
  2. Removed classe, remplacé par Enum. (Voir les commentaires, 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);}}}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top