Codegolf: Finden Sie die eindeutigen Pfade
-
13-10-2019 - |
Frage
Hier ist eine ziemlich einfache Idee, darin Pastebin Ich habe ein paar Zahlen gepostet. Diese repräsentieren Knoten eines gerichteten Diagramms. Die Eingabe an stdin
wird von der Form sein (sie werden Zahlen sein, ich werde hier ein Beispiel verwenden)
c d
q r
a b
b c
d e
p q
Also x y
meint x
ist verbunden mit y
(nicht und umgekehrt)
In diesem Beispiel gibt es 2 Pfade. a->b->c->d->e
und p->q->r
.
Sie müssen alle eindeutigen Pfade aus diesem Diagramm drucken. Die Ausgabe sollte aus dem Format sein
a->b->c->d->e
p->q->r
Anmerkungen
- Sie können annehmen, dass die Zahlen so ausgewählt werden, dass ein Pfad den anderen nicht schneidet (ein Knoten gehört zu einem Pfad).
- Die Paare sind in zufälliger Reihenfolge.
- Sie sind mehr als 1 Pfade, sie können unterschiedliche Längen haben.
- Alle Zahlen sind weniger als 1000.
Wenn Sie weitere Details benötigen, hinterlassen Sie bitte einen Kommentar. Ich werde nach Bedarf ändern.
Schamloser Plug
Für diejenigen, die Codegolf genießen, verpflichten Sie sich bitte bei Bereich51 Für seine eigene Seite :) (Für diejenigen, die es nicht genießen, unterstützen Sie es bitte auch, also bleiben wir Ihnen aus dem Weg ...)
Lösung
Rubin - 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*'->'}
Nahm Nas Banovs Idee von 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}
Andere Tipps
C89 - 212 204 Zeichen
#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("");}}
Unnötige Neulinge werden nicht gezählt.
Befehl:
$ wget -O - http://pastebin.com/download.php?i=R2PDGb2w | ./unique-paths
Ausgabe:
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
Hübsche 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;
}
Obwohl nicht die Antwort, zeichnet das folgende Linux -Skript ein Diagramm der Eingabedatei:
cat FILE | (echo "digraph G {"; awk '{print "\t" $1 "-> " $2;}'; echo "}") \
| dot -Tpng > out.png && eog out.png
Du brauchst Graphviz installiert für die dot
Befehl und eog
ist Gnom'S Image Viewer.
Wenn Sie in der Eingabedatei ausgeführt werden, sieht die Grafik so aus:
90 ° gedreht und skaliert (nach unten skaliert (Siehe Original)
Wie Sie sehen können, ist das Eingabetrat nur eine Sammlung von einzelnen Listen ohne gemeinsame Knoten und ohne Zyklen.
Python
120 Zeichen
Mir gefällt, wie mühelos es in Python liest:
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
Und das Ergebnis aus dem Pasta-Bin-Beispiel:
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 Bytes
Ja, endgültig ein Codegolf, in dem Lua nicht saugt. Extra Goodie: funktioniert an allem, was Platz getrennt ist (Anzahl der Größe, Strings, ...)
Die nicht gewaltige 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
Die Golfversion:
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 Zeichen
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
Fehlend:
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
Weniger eleganter Ansatz als zuvor, aber kürzer! Inspiriert von der Idee von NAS Banov von 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";}
Ganze Datei sieht aus:
<?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";}
Laufen:
$ php graph.php graph.txt
Hübsche 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";
}
}
Ocaml
402 Zeichen
Grundsätzlich eine Anpassung der Haskell -Version, deren Länge mich überrascht. Es gibt sicherlich einen Weg, mit Str
und/oder die überarbeitete 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)[])
Fehlend:
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 Bytes
Aktualisieren :
- Generika entfernt. Und anscheinend kann die Klasse mit "öffentlich" tun (Thhnx Sean)
- Klasse entfernt, durch Enum ersetzt. (Siehe Kommentare, 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);}}}