16

昨年 (2009 年) のGoogle Code Jamでは、Round 1B の最初の問題として興味深い問題が取り上げられました:決定木

この問題は Lisp に似た言語に合わせて調整されているように見えたので、私たちは自発的にここ SO でエキサイティングなコードゴルフを作成しました。その中では、いくつかの言語が、かなり多くの異なる手法を使用して、どの Lisp の種類よりも少ない文字数で問題を解決することができました。

今年の Round 1B Problem A ( File Fix-it ) も、特定の言語ファミリーである Unix シェル スクリプト向けに調整されているようです。したがって、「1B-A の伝統」を継続することが適切でしょう。:p しかし、どの言語が最短のコードになるでしょうか? コードゴルフして見てみましょう！

問題の説明(公式ページから適応):

T個のテスト ケースが与えられます。各テスト ケースには、コンピュータに現在存在するすべてのディレクトリのフル パスをリストするN行が含まれます。例えば：

/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie

次に、作成するディレクトリのフル パスをリストするM行が表示されます。これらは、前の例と同じ形式です。コマンドを使用してディレクトリを作成できますmkdirが、親ディレクトリが既に存在する場合にのみ作成できます。たとえば、ディレクトリ/pyonpyon/fumufumu/yeahyeahとを作成するには、次のように4 回/pyonpyon/fumufumu/yeahyeahyeah使用する必要があります。mkdir

mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah

mkdirテスト ケースごとに、作成するすべてのディレクトリを作成するために呼び出す必要がある回数を返します。

入力

入力はテキスト ファイルで構成され、その最初の行には整数T (テスト ケースの数) が含まれます。ファイルの残りの部分には、テスト ケースが含まれています。

各テスト ケースは、スペースで区切られた整数NとMを含む行で始まります。

次のN行には、現在コンピューターに存在する各ディレクトリのパスが含まれています (ルート ディレクトリは含まれません/)。これは、1 つまたは複数の空でない小文字の英数字文字列を連結したもので、それぞれの前に単一の/.

次のM行には、作成する各ディレクトリのパスが含まれています。

出力

ケースごとに、 を含む 1 行を出力します。Case #X: YここXで、 はケース番号、Yはソリューションです。

限界

1 ≤ T ≤ 100。

0 ≤ N ≤ 100。

1 ≤ M ≤ 100。

各パスには最大 100 文字が含まれます。

すべてのパスは、コンピューターに既に存在するディレクトリのリスト、または目的のディレクトリのリストに一度だけ表示されます。ただし、以下のケース #3 のように、両方のリストにパスが表示される場合があります。

ディレクトリが既にコンピュータ上のディレクトリのリストにある場合、ルート ディレクトリを除いて、その親ディレクトリもリストされます/。

入力ファイルの長さは最大 100,000 バイトです。

例

より大きなサンプル テスト ケースは、ここからダウンロードできます。

入力：

3
0 2
/home/sparkle/pyon
/home/sparkle/cakes
1 3
/z
/z/y
/z/x
/y/y
2 1
/moo
/moo/wheeeee
/moo

出力：

Case #1: 4
Case #2: 4
Case #3: 0

コードゴルフ

この問題を解決する最短のコードを任意の言語で投稿してください。入力と出力は、stdin と stdout を介して、または選択した他のファイルで処理できます。コードが実行時に既存のファイルを変更または削除する可能性がある場合は、免責事項を含めてください。

勝者は、Round 1B 2010 の開始前に実装が存在する言語での (バイト カウントによる) 最短のソリューションになります。解決策、それはカウントされず、おそらく反対票を得るでしょう. ^_^

順位表

4

15 に答える 15

10

パイソン、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

このソリューションは EOFError をスローしますが、これは stderr に出力されるため、ルールの範囲内です。関心のある出力はすべて stdout に送られるため、それをパイプして stderr を無視できます。

上記 (または他のいくつかの投稿) を読んで、うまくいかないと思うかもしれません。その理由にはちょっとしたコツがあるので、ここで説明します。質問を注意深く読むと、最初のリストの各ディレクトリについて、その親ディレクトリもすべてリストに含まれていることがわかります (たとえば、/home/marcog が存在する場合、/home もそうです) [1]。この質問は、各リストに重複がないことも保証します [2]。これにより、最初のリストのすべてのディレクトリを、2 番目のリストのディレクトリをスローする同じセットにスローできます。質問はリストごとに重複がないことを保証するため、最初のリストはセット内に正確に N エントリになることがわかります。したがって、最終セットのサイズから N を引くことで、最終的な答えを得ることができます。

[1] 「次の N 行はそれぞれ、コンピューターに既に存在する 1 つのディレクトリのパスを示します。このリストには、ルート ディレクトリ以外のコンピューターに既に存在するすべてのディレクトリが含まれます。」

[2] 「コンピューターに既に存在するディレクトリのリスト、または作成するディレクトリのリストにパスが 2 回表示されることはありません。」

于 2010-05-23T15:31:53.380 に答える
8

ゴルフスクリプト、74 69 65

これで一行に！
このソリューションは 63 文字ですが、何千ものパス (8 分以上) があるテスト ケースでは妥当な時間では実行できないため、カウントしないことにしました。

n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/

より高速な 65 文字のソリューション:

n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/

アルゴリズムの marcog に称賛を！

于 2010-05-23T14:58:17.033 に答える
4

パール、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'

インタプリタのコマンドライン オプションに依存するゴルフ プログラムと同様に、デフォルトに対するオプションのバイト数の差が実際のコード長に追加されています。

インデント、コメント

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

魔法のほとんどは、ブランチからルートの抽出です。秘訣は、正規表現を使用して興味深い切断ポイント (つまり、各スラッシュの前、および文字列の末尾) を見つけることですが、Perl を使用して文字列を抽出すること$PREMATCHです (ドルバックティック; マークダウンではそれを適切に含めることはできません)。通常のパターンマッチング機能の代わりに。

\bすべての単語 (ディレクトリ) の開始と終了に解決される単語境界を見つけます。私たちは彼らの終わりだけが欲しいので、先頭に\w. しかし、それはパスから最後の文字を切り取ってしまいます。これは、同じデータセットで/foo/barとの両方を取得する場合に問題になります。/foo/bazしたがって、その文字を との一致から除外し\Kます。\>Perl が-like (Emacs 正規表現) メタ文字を持っていれば、これは必要ありません。

スタンドアロン プログラムとして (106)

for$i(1..<>){($n,$m,%d)=split$",<>;
for(1..$n+$m){$_=<>;$d{$`}++while/\w\K\b/g}
say"Case #$i: ",keys(%d)-$n}

読みやすさのための改行。それらのどれも必要ではなく、考慮されていません。

Perl の最新バージョンにのみ見られる機能を使用するため、perl -M5.010 以降で実行してください。

于 2010-05-24T00:42:33.800 に答える
3

Luaソリューション、172バイト：

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
于 2010-05-23T19:23:33.050 に答える
2

ハスケル、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++"/")

他の Haskell ソリューションに似ています (ただし、より短い:P)。

エラーで終了しますが、これは想定内です。それがルールに従っているかどうかは、他のソリューションよりも議論の余地が少しあります。実際、出力ストリームとエラー ストリームは混同されていません。ただし、stdout がバッファリングされている場合、結果は送信されません。インタラクティブな使用には問題ありませんが（コンソール出力をファイルにコピーアンドペーストするだけです）、ほとんどの場合、リダイレクトは除外されます. 短くするために./filefixit <input 2>/dev/null、トリックを行います。

この問題は、3 行目にライン ノイズを挿入することで回避できます: []!_=""(さらに 8 バイト、合計 226 バイト)

明確にするために、完全なインデントと意味のある識別子を使用したまったく同じセマンティクス:

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 ++ "/")
于 2010-05-23T23:40:23.857 に答える
2

ポストスクリプト

182 212 247 262 278バイト

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

使用法：$ gs -q -dNODISPLAY -dNOPROMPT thisfile.ps <input >output

于 2010-05-23T16:58:14.577 に答える
2

ルビー、151 149 144

marcog の Python ソリューションのRuby への直接翻訳:

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}"}
于 2010-05-23T21:21:38.210 に答える
2

バッシュ、175 169 168 135 130 128

警告:必ず空のディレクトリで実行してください。これにより、テストごとに最初に内容が消去されます。

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
于 2010-05-23T14:37:50.093 に答える
1

C＃、489 442 400 398

ただ楽しみのために、もちろん非常に不足する可能性はありません。カウントは、読みやすくするためにここに残した重要でない空白を削除した後です。

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

この最新バージョンには癖があります。ループの開始時に変数nが目的の0ではなく-1であることを補正するために、ルートディレクトリを1回作成する必要があると誤ってカウントします。これは、ルートディレクトリがNにないことが保証されているため機能します。

于 2010-05-23T16:31:38.263 に答える
0

J - 205159140 文字

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)

走る：

script.ijs < gcj-input

それでも、1行余分に出力します：/

于 2010-05-25T08:21:24.690 に答える
0

スカラ、190 189

今回はScalaで、marcogのソリューションのさらに別のバージョンです。で実行scalaされますが、でコンパイルできるようにクラスに入れる必要があります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)}
于 2010-05-24T14:19:18.967 に答える
0

ハスケル: 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]}

これには GHC の-XScopedTypeVariablesスイッチが必要です。

読み取り可能なバージョン:

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
于 2010-05-23T20:40:38.577 に答える
0

ジャワ、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));}}}

注: エラー メッセージが出力されますが、正常に動作します。

于 2010-05-23T16:48:11.723 に答える
0

ピョンスクリプト

158 159バイト

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)

使用法：$ pyon thisfile.pyon <input >output

PostScript ソリューションに基づいています。

PyonScript の開発はまだ進行中であるため、このコードは 2010 年のラウンド 1B の開始時に存在していた実装で機能します: http://github.com/KirarinSnow/PyonScript

于 2010-05-23T22:19:31.943 に答える
0

AWK - 123 121 文字

marcog python バージョンの別の適応。で実行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()}

オプションなしで実行すると、-F次の部分が必要になるため、15 文字増加します。

BEGIN{FS=" |/"}
于 2010-05-24T10:39:21.150 に答える