Datei Fix-it Codegolf (GCJ 2010 1B-A)

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

  •  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

War es hilfreich?

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.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top