CodeGolf:找到独特的路径

Question

这是一个非常简单的想法,在这个pastebin我发布了一些数字.这些代表有向图的节点.输入stdin将是形式,(他们将是数字,我将在这里使用一个例子)

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

所以x y手段x连接到y(不是反之亦然)

该示例中有2条路径.a->b->c->d->e和p->q->r.

您需要打印该图表中的所有唯一路径.输出应为格式

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

笔记

1. 您可以假设选择的数字使得一条路径不与另一条路径相交(一个节点属于一条路径)
2. 这些对是随机顺序的.
3. 它们不止一条路径,它们可以有不同的长度.
4. 所有数字都小于1000.

如果您需要更多详细信息,请发表评论.我会按要求修改.

无耻插头

对于那些喜欢Codegolf的人,请在Area51上为自己的网站提交:)(对于那些不喜欢它的人,也请支持它,所以我们会让你不受欢迎...)

Answer 1

红宝石 - 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}

Answer 2

虽然不是答案,但以下Linux脚本绘制了输入文件的图形:

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

你需要为命令安装Graphvizdot,它eog是GNOME的图像查看器.

在输入文件上运行,图形如下所示:

旋转90°并按比例缩小(见原文)

如您所见,输入图只是单链表的集合,没有共享节点且没有循环.

Answer 3

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

Answer 4

蟒蛇

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

跑过面食箱样品的结果:

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