Datei Fix-it Codegolf (GCJ 2010 1B-A)
-
04-10-2019 - |
Frage
Letztes Jahr (2009) die Google Code Jam zeigte ein interessantes Problem als erstes Problem in Runde 1B: Entscheidungsbaum
Da das Problem auf Lisp-ähnliche Sprachen zugeschnitten schien, hatten wir spontan eine Aufregender Codegolf Hier zu SO, in dem es einigen Sprachen gelang, das Problem in weniger Charakteren zu lösen als jede Lisp -Sorte, wobei eine Reihe verschiedener Techniken verwendet wurden.
Das diesjährige Runde 1B -Problem A (Datei fix-it) scheint auch auf eine bestimmte Familie von Sprachen zugeschnitten zu sein, Unix -Shell -Skripte. Die Fortsetzung der "1B-A-Tradition" wäre also angemessen. : P Aber welche Sprache wird mit dem kürzesten Code enden? Lassen Sie uns CODEGOLF und sehen!
Problembeschreibung (angepasst von der offiziellen Seite):
Sie werden gegeben T Testfälle. Jeder Testfall enthält N Zeilen, die den vollständigen Pfad von auflisten alle derzeit auf Ihrem Computer vorhandene Verzeichnisse. Zum Beispiel:
/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie
Als nächstes werden Sie gegeben M Zeilen, die den vollständigen Pfad der Verzeichnisse auflisten, die Sie erstellen möchten. Sie sind im gleichen Format wie die vorherigen Beispiele. Sie können ein Verzeichnis mit dem erstellen mkdir
Befehl, aber Sie können dies nur tun, wenn das übergeordnete Verzeichnis bereits vorhanden ist. Zum Beispiel, um die Verzeichnisse zu erstellen /pyonpyon/fumufumu/yeahyeah
und /pyonpyon/fumufumu/yeahyeahyeah
, Sie müssten verwenden mkdir
vier Mal:
mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah
Geben Sie für jeden Testfall die Häufigkeit zurück, mit der Sie anrufen müssen mkdir
So erstellen Sie alle Verzeichnisse, die Sie erstellen möchten.
Eingang
Die Eingabe besteht aus einer Textdatei, deren erste Zeile die Ganzzahl enthält T, die Anzahl der Testfälle. Der Rest der Datei enthält die Testfälle.
Jeder Testfall beginnt mit einer Linie, die die Ganzzahlen enthält N und M, durch einen Raum getrennt.
Der nächste N Die Zeilen enthalten den Pfad jedes derzeit auf Ihrem Computer vorhandenen Verzeichnisses (ohne das Stammverzeichnis enthalten /
). Dies ist eine Verkettung eines oder mehrerer nicht leerer alphanumerischer Kleinkoffer, der jeweils eine einzelne vorangegangen ist /
.
Folgende M Zeilen enthalten den Pfad jedes Verzeichnisses, den Sie erstellen möchten.
Ausgabe
Drucken Sie für jeden Fall eine Zeile, die enthält Case #X: Y
, wo X
ist die Fallnummer und Y
ist die Lösung.
Grenzen
1 ≤ t ≤ 100.
0 ≤ n ≤ 100.
1 ≤ m ≤ 100.
Jeder Weg enthält höchstens 100 Zeichen.
Jeder Weg wird nur einmal in der Liste der Verzeichnisse auf Ihrem Computer oder in der Liste der gewünschten Verzeichnisse angezeigt. Auf beiden Listen kann jedoch ein Pfad angezeigt werden, wie in Beispiel für Fall Nr. 3 unten.
Wenn sich ein Verzeichnis in der Liste der Verzeichnisse auf Ihrem Computer befindet, wird auch das übergeordnete Verzeichnis aufgeführt, mit Ausnahme des Stammverzeichnisses /
.
Die Eingabedatei ist höchstens 100.000 Bytes lang.
Beispiel
Größere Beispieltestfälle können heruntergeladen werden hier.
Eingang:
3
0 2
/home/sparkle/pyon
/home/sparkle/cakes
1 3
/z
/z/y
/z/x
/y/y
2 1
/moo
/moo/wheeeee
/moo
Ausgabe:
Case #1: 4
Case #2: 4
Case #3: 0
Code Golf
Bitte veröffentlichen Sie Ihren kürzesten Code in jeder Sprache, die dieses Problem löst. Eingabe und Ausgabe können über STDIN und STDOut oder andere Dateien Ihrer Wahl behandelt werden. Bitte geben Sie einen Haftungsausschluss an, wenn Ihr Code das Potenzial hat, vorhandene Dateien bei der Ausführung zu ändern oder zu löschen.
Der Gewinner wird die kürzeste Lösung (nach Byte-Graf) in einer Sprache sein, in der eine Implementierung vor Beginn der Runde 1B 2010 vorhanden ist Lösung, es wird nicht zählen, und Sie werden wahrscheinlich Downvoten bekommen. ^_^
Wertung
- 65 Golfskript
- 100 Perl
- 121 Awk (ohne Interpreter -Optionen)
- 128 Verprügeln
- 144 Rubin
- 145 Python
- 158 PyonScript
- 159 J
- 172 Lua
- 182 PostScript
- 189 Scala
- 218 Haskell
- 284 Java
- 398 C#
Lösung
Golfskript, 74 69 65
Jetzt auf einer einzigen Linie!
Diese Lösung beträgt 63 Zeichen, wird jedoch nicht in angemessener Zeit für Testfälle mit Tausenden von Pfaden (über 8 Minuten) ausgeführt, sodass ich mich dafür entschieden habe, sie nicht zu zählen.
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/
Je schneller 65 Charakterlösung:
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/
Ein großes Lob an Marcog für den Algorithmus!
Andere Tipps
Python, 193 175 173 171 166 165 164 156 151 149 147 146 145
r=raw_input;c=0;r()
while 1:N,M=map(int,r().split());d={};c+=1;exec"e=r()\nwhile e:d[e]=e,_=e.rsplit('/',1)\n"*(N+M);print'Case #%d:'%c,len(d)-N
Diese Lösung wirft einen eoFerror aus, aber da dies an STDERR ausgegeben wird, liegt sie innerhalb der Regeln. Seit der Ausgabe, an der wir uns für alle interessieren, können wir das putzen und Stderr ignorieren.
Sie könnten das oben genannte (oder einige der anderen Beiträge) lesen und denken, dass es nicht funktionieren sollte. Es gibt einen kleinen Trick, warum, und ich werde das hier erklären. Wenn Sie die Frage sorgfältig lesen, werden wir für jedes Verzeichnis in der ersten Liste nur in der Liste enthalten (z. B. wenn /home /marcog vorhanden, so ist /home) [1]. Die Frage garantiert uns auch, dass jede Liste keine Duplikate hat [2]. Auf diese Weise können wir alle Verzeichnisse in die erste Liste in denselben Satz werfen, in dem wir die Verzeichnisse aus der zweiten Liste werfen. Da die Frage keine Duplikate pro Liste garantiert, wissen wir, dass die erste Liste zu genau N -Einträgen im Satz führt. Daher können wir die endgültige Antwort erhalten, indem wir N von der Größe des endgültigen Satzes abziehen.
1] "Die nächsten N -Zeilen geben jeweils den Pfad eines Verzeichnisses, das bereits auf Ihrem Computer vorhanden ist. Diese Liste enthält jedes Verzeichnis, das bereits auf Ihrem Computer außer dem Root -Verzeichnis ist."
2] "Kein Pfad wird zweimal in der Liste der Verzeichnisse auf Ihrem Computer oder in der Liste der Verzeichnisse angezeigt, die Sie erstellen möchten."
Perl, 111 106 100
perl -naE 'BEGIN{<>}++$i;($n,$m,%d)=@F;for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}say"Case #$i: ",keys(%d)-$n'
Wie immer wurden Golfprogramme, die von den Befehlszeilenoptionen der Interpreter abhängig sind, der ByteCount-Unterschied der Optionen in Bezug auf die Standardeinstellung zur tatsächlichen Codelänge hinzugefügt.
Eingerückt, kommentiert
#! perl -na # activate line mode and autosplit
BEGIN { <> } # skip test case count
# now for each test case:
++$i; # increment test counter
($n,$m,%d) = @F; # read N and M;
# clear out directory hash
for (1..$n+$m) { # for each expected pathname:
$_ = <>; # read it
$d{$`}++ # add to hash...
while /\w\K\b/g # ...all branches from root
}
say "Case #$i: ", keys(%d) - $n
Der größte Teil der Magie ist die Zweig-From-Root-Extraktion. Der Trick besteht darin, einen Regex zu verwenden, um die interessanten Schneidpunkte zu lokalisieren (nämlich: vor jedem Schrägstrich und das Ende der Zeichenfolge), aber die Zeichenfolge mit Perls extrahieren $PREMATCH
(Dollar-Backtick; Markdown lässt mich das nicht richtig einschließen) anstelle der üblichen Musteranpassungsmöglichkeiten.
\b
Findet eine Wortgrenze, die auf alle Wörter '(Verzeichnisse') beginnt und endet. Wir wollen nur ihr Ende, also bereiten wir a vor \w
. Aber das würde den letzten Charakter vom Weg abschneiden, was ein Problem ist, wenn wir beide bekommen /foo/bar
und /foo/baz
im selben Datensatz. Also schließen wir diesen Charakter aus dem Spiel mit aus \K
. Nichts davon wäre notwendig, wenn Perl a hätte \>
-ähnlich (EMACS Regexes) Metacharacter.
Als eigenständiges Programm (106)
for$i(1..<>){($n,$m,%d)=split$",<>;
for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}
say"Case #$i: ",keys(%d)-$n}
Newlines für die Lesbarkeit; Keiner von ihnen ist notwendig oder gezählt.
Es werden Funktionen verwendet, die nur in den neuesten Versionen von Perl gefunden wurden. Führen Sie also mit Perl -M5.010 oder höher aus.
LUA -Lösung, 172 Bytes:
r,n=io.read,"*n"for i=1,r(n)do a,c,s=r(n),0,{}for i=1,a+r()do k=""for x in r():gmatch"[^/]+"do k=k.."/"..x c=c+(s[k]or 1);s[k]=0 end end print("Case #"..i..": "..(c-a))end
C#, 489 442 400 398
Nur zum Spaß, keine Chance, natürlich jemals sehr kurz zu sein. Die Zählung ist nach dem Entfernen des nicht signifikanten weißen Raums, den ich hier zur Lesbarkeit verlassen habe.
namespace System
{
class P
{
static void Main(string[]a)
{
int c = 0, n, m, d, l = 1;
var f = IO.File.ReadAllLines(a[0]);
while (c < int.Parse(f[0]))
{
var o = f[l++].Split(' ');
n = int.Parse(o[0]);
m = int.Parse(o[1]);
var p = new Collections.Generic.HashSet<string>();
while (n-- > 0)
p.Add(f[l++]);
while (m-- > 0)
for (o = f[l++].Split('/'), d = 0; d++ < o.Length; )
if (p.Add(string.Join("/", o, 0, d)))
n++;
Console.Write("Case #{0}: {1}\n", ++c, n);
}
}
}
}
Diese neueste Version hat eine Eigenart. Es zählt fälschlicherweise das Root -Verzeichnis so, dass es einmal erstellt werden muss, um Variable N zu Beginn der Schleife zu kompensieren, anstatt der gewünschten 0. Es funktioniert, weil das Stammverzeichnis garantiert nicht in N ist.
Haskell, 218
import Data.List
main=interact$(!1).tail.lines
(l:j)!i=let{[n,m]=map read$words l;(p,k)=splitAt(n+m)j}in"Case #"++show i++": "++show(length(nub$(>>=s)p)-n)++"\n"++k!(i+1)
s(_:p)=map(flip take p)$elemIndices '/'(p++"/")
Ähnlich (aber viel kürzer: p) der anderen Haskell -Lösung.
Endet irrtümlich, und das wird erwartet. Ob dies die Regeln folgt oder nicht, ist etwas anfälliger für die Debatte als für andere Lösungen. Die Ausgangs- und Fehlerströme sind in der Tat nicht durcheinander. Wenn jedoch Stdout gepuffert ist, werden die Ergebnisse nie gesendet. Das ist in Ordnung für die interaktive Verwendung (dann kopieren Sie die Konsolenausgabe in eine Datei), aber es schließt die Umleitung hauptsächlich aus. Um es kurz zu machen, ./filefixit <input 2>/dev/null
macht den Trick.
Das Problem kann vermieden werden, indem Leitungsrauschen in Zeile 3 eingefügt wird: []!_=""
(8 weitere Bytes, insgesamt 226)
Aus Gründen der Klarheit, genau dieselbe Semantik mit vollem Eindrückung und aussagekräftigen Kennungen:
import Data.List
main = interact $ testsStartingAt 1 . tail . lines
testsStartingAt _ [] = "" -- this line optional
testsStartingAt i (l:ls) = testOutput ++ testsStartingAt (i+1) ls'
where [n,m] = map read $ words l
(paths,ls') = splitAt (n+m) ls
testResult = length (nub $ concatMap splitPath paths) - n
testOutput = "Case #" ++ show i ++ ": " ++ show testResult ++ "\n"
splitPath (_:p) = map (flip take p) $ elemIndices '/' (p ++ "/")
Verprügeln, 175 169 168 135 130 128
WARNUNG: Laufen Sie unbedingt in einem leeren Verzeichnis, da dies als erstes den Inhalt pro Test ausgelöscht wird.
read t
for((;x++<t;));do
rm -r *
read n m
for((i=n+m;i--;));do
read d
mkdir -p .$d
done
echo Case \#$x: $[`find|wc -l`-n-1]
done
Rubin, 151 149 144
Direkte Übersetzung zu Ruby von Marcogs Python -Lösung:
gets.to_i.times{|i|n,m=gets.split.map &:to_i
d={}
(n+m).times{gets.strip.split('/').inject{|a,p|d[a+='/'+p]=a}}
puts"Case ##{i+1}: #{d.size-n}"}
PostScript
182 212 247 262 278 Bytes
1[([){exch}/C{concatstrings}/R{(%lineedit)run}>>begin 1
R{(: )[(Case #)3{=only}repeat<<>>R 1 index add{()<<R]{99 string
cvs C<C>C dup 3 index[<>put}forall pop}repeat[length[sub =}for
Verwendungszweck: $ gs -q -dNODISPLAY -dNOPROMPT thisfile.ps <input >output
Haskell: 299
import Data.List
import Text.Printf
a[]=[]
a(x:z)=(r-n):next where{;[n,m]=map read$words x;t=n+m;r=length$nub$concatMap(f.reverse)$take t z;next=a$drop t z;f""=[];f y=y:f z where(a,b:z)=span(/='/')y}
main=do{z<-getContents;putStr$unlines[printf"Case #%d: %d"x v|(x::Int,v)<-zip[1..]$a$tail$lines z]}
Dies erfordert GHCs -XScopedTypeVariables
Schalter.
Lesbare Version:
import Data.List
import Text.Printf
a [] = []
a (x:xs) = (r-n) : next where
[n,m] = map read $ words x
t = n+m
r = length $ nub $ concatMap (f . reverse) $ take t xs
next = a $ drop t xs
f "" = []
f y = y : f bs where
(a,b:bs) = span (/= '/') y
cleanUp a = unlines [printf "Case #%d: %d" x v | (x::Int,v::Int) <- zip [1..] a]
main = do
z<-getContents
putStr$cleanUp$a$tail$lines z
Scala, 190 189
Noch eine Version von Marcogs Lösung, diesmal in Scala. Läuft mit scala
, müsste aber in eine Klasse gesteckt werden, um die Zusammenstellung mit scalac
.
for(c←1 to readInt){val I=readLine split" "map(_.toInt)
var d=Set("")
for(i←1-I(0)to I(1)){var a="";for(w←readLine split"/"){a+="/"+w;d+=a}}
printf("Case #%d: %d\n",c,d.size-I(0)-2)}
Awk - 123 121 Chars
Eine weitere Anpassung der Marcog Python -Version. Rennen mit awk -F'[ \]' -f fixit.awk
function p(){if(c++>1)print"Case #"c-2": "length(k)-n}
/\//{for(y=i=1;i<NF;)k[y=y"/"$++i];next}
{p();n=$1;delete k}
END{p()}
Es ohne die ausführen -F
Option, es wächst um 15 Chars, da es dann diesen Teil benötigt:
BEGIN{FS=" |/"}
PyonScript
158 159 Bytes
1({[([){exch}/R{(%lineedit)run}>>begin R{(: )[(Case #)3{=only}repeat<<>>R 1
index +{<><<R]{str cat<C>cat dup 3 index[<>put}forall pop}repeat[length[-
=}for}1)
Verwendungszweck: $ pyon thisfile.pyon <input >output
Basierend auf der Postscript -Lösung.
Da die Pyoncript -Entwicklung noch im Gange ist, arbeitet dieser Code an der Implementierung, wie er zu Beginn der Runde 1B 2010 existiert hat: http://github.com/kirarinsnow/pyoncript
J - 205 159 140 Zeichen
c=:0
f=:3 :0
c=:>:c
'a b'=:({.,+/)".>{.y
('Case #',(":c),': ',":a-~3 :'#~.,/>\"1<;.1"1 y'>(>:i.b){y)1!:2<2
(>:b)}.y
)
f^:_(}.<;._2 (1!:1)<3)
Lauf:
script.ijs < gcj-input
Trotzdem gibt es eine zusätzliche Linie aus:/
Java, 277
import java.util.*;enum A{_;{Scanner s=new Scanner(System.in);for(int
t=s.nextInt(),i=0,n,j;i++<t;){Set x=new
HashSet();n=s.nextInt();for(j=s.nextInt();j-->-n;){String b="";for(String
c:s.next().split("/"))x.add(b+=c+'/');}System.out.println("Case #"+i+": "+(x.size()-n-1));}}}
HINWEIS: Es gibt eine Fehlermeldung aus, funktioniert jedoch immer noch korrekt.