19

これは非常に単純なアイデアです。このペーストビンにいくつかの数字のペアを投稿しました。これらは、有向グラフのノードを表します。への入力stdinは次の形式になります (数値になります。ここでは例を使用します)。

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

soは接続されていることx yを意味します(その逆ではない)xy

その例には 2 つのパスがあります。a->b->c->d->eとp->q->r。

そのグラフからすべての一意のパスを出力する必要があります出力は次の形式にする必要があります

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

ノート

  1. 1 つのパスが他のパスと交差しないように番号が選択されていると想定できます (1 つのノードが 1 つのパスに属します)。
  2. ペアの順番はランダムです。
  3. それらは複数のパスであり、長さが異なる場合があります。
  4. 数値はすべて 1000 未満です。

詳細が必要な場合は、コメントを残してください。必要に応じて修正します。

恥知らずのプラグ

Codegolf を楽しんでいる方は、Area51 で専用のサイトをコミットしてください:) (それを楽しんでいない方もサポートしてください。私たちはあなたの邪魔にならないようにします...)

4

9 に答える 9

6

ルビー — 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*'->'}

Nas Banov のアイデアを取り入れた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}
于 2010-12-28T20:20:00.890 に答える
5

パイソン

120文字

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

そして、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
于 2011-01-01T05:14:15.740 に答える
5

答えではありませんが、次の Linux スクリプトは入力ファイルのグラフを描画します。

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

このコマンドを実行するにはGraphvizをインストールする必要があります。これはGNOMEの画像ビューアーです。doteog

入力ファイルで実行すると、グラフは次のようになります。

代替テキスト

90°回転して縮小（原文参照）

ご覧のとおり、入力グラフは、共有ノードも循環もない単一リンク リストの集まりです。

于 2010-12-28T02:23:52.953 に答える
5

C89 - 212 204 文字

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

不要な改行はカウントされません。

指示：

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

出力：

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

きれいなバージョン:

#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;
}
于 2010-12-28T07:00:19.183 に答える
4

ルア、166バイト

そうそう、最後に Lua が吸わない codegolf です。おまけ: スペースで区切られたもの (どんなサイズの数字、文字列など) でも動作します。

非ゴルフバージョン:

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

ゴルフバージョン：

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
于 2010-12-28T23:13:21.217 に答える
3

Haskell — 174 142 137 133 文字

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

非ゴルフ:

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

以前よりもエレガントなアプローチではありませんが、より短くなります! Nas Banov のアイデアに触発されたh.keys-h.values

于 2010-12-29T05:12:01.427 に答える
1

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

ファイル全体は次のようになります。

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

走る：

$ php graph.php graph.txt

きれいなバージョン:

$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";
    }
}
于 2010-12-29T02:51:25.773 に答える
0

オカムル

402文字

基本的に Haskell バージョンの適応であり、その長さに驚かされます。Strおよび/または改訂された構文をより適切に使用する方法は確かにあります。

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

非ゴルフ:

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) [])
于 2010-12-30T21:48:44.747 に答える
0

ジャワ

372 337 304 バイト

更新：

  1. ジェネリックを削除しました。どうやら、クラスは public でなくてもできるようです (Thnx Sean)
  2. クラスを削除し、Enum に置き換えました。（コメントを参照してください、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);}}}
于 2010-12-29T06:09:45.667 に答える