ファイル Fix-it codegolf (GCJ 2010 1B-A)
https://stackoverflow.com/questions/2892126
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
昨年（2009年）、 Google コードジャム ラウンド 1B の最初の問題として興味深い問題が取り上げられました。 デシジョンツリー
この問題は Lisp のような言語に合わせて調整されているように見えたので、私たちは自発的に次のような問題を抱えていました。 エキサイティングなコードゴルフ SO では、いくつかの言語が、かなり多くの異なるテクニックを使用して、どの Lisp よりも少ない文字数で問題を解決することができました。
今年のRound 1B 問題A (ファイル修正) は、特定の言語ファミリーである Unix シェル スクリプトにも合わせて調整されているようです。したがって、「1B-A の伝統」を継続することが適切でしょう。:p しかし、最終的に最も短いコードになるのはどの言語でしょうか?コードゴルフをして見てみましょう!
問題の説明 (公式ページより抜粋):
あなたには与えられています T テストケース。各テスト ケースには次の内容が含まれます N のフルパスをリストする行 全て コンピュータ上に現在存在するディレクトリ。例えば：
/home
/home/awesome
/home/awesome/wheeeeeee
/home/awesome/wheeeeeee/codegolfrocks
/home/thecakeisalie
次に、あなたに与えられるのは、 M 作成するディレクトリの完全なパスをリストする行。これらは前の例と同じ形式です。を使用してディレクトリを作成できます。 mkdir コマンドを使用できますが、親ディレクトリがすでに存在する場合にのみ実行できます。たとえば、ディレクトリを作成するには /pyonpyon/fumufumu/yeahyeah そして /pyonpyon/fumufumu/yeahyeahyeah, を使用する必要があります mkdir 四回：
mkdir /pyonpyon
mkdir /pyonpyon/fumufumu
mkdir /pyonpyon/fumufumu/yeahyeah
mkdir /pyonpyon/fumufumu/yeahyeahyeah
テスト ケースごとに、呼び出す必要がある回数を返します。 mkdir 作成したいすべてのディレクトリを作成します。
入力
入力は、最初の行に整数が含まれるテキスト ファイルで構成されます。 T, 、テストケースの数。ファイルの残りの部分にはテスト ケースが含まれています。
各テスト ケースは、整数を含む行で始まります。 N そして M, 、スペースで区切ります。
次は N 行には、コンピュータ上に現在存在する各ディレクトリのパスが含まれます (ルート ディレクトリは含まれません)。 /）。これは、1 つ以上の空ではない小文字の英数字文字列の連結であり、それぞれの前に 1 つの文字列が続きます。 /.
次の M 行には、作成する各ディレクトリのパスが含まれます。
出力
それぞれのケースについて、次の内容を 1 行出力します。 Case #X: Y, 、 どこ X はケース番号であり、 Y が解決策です。
限界
1 ≤ T ≤ 100。
0 ≤ N ≤ 100。
1 ≤ M ≤ 100。
各パスには最大 100 文字が含まれます。
すべてのパスは、コンピュータ上にすでに存在するディレクトリのリスト、または目的のディレクトリのリストに 1 回だけ表示されます。ただし、以下の例 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 を介して、または選択した他のファイルによって処理できます。 コードの実行時に既存のファイルが変更または削除される可能性がある場合は、免責事項を含めてください。
勝者は、2010 年のラウンド 1B の開始前に実装が存在した言語で最も短いソリューション (バイト数による) となります。したがって、0 バイトのソリューションを提出するために作成したばかりの言語を自由に使用することはできますが、それはカウントされず、おそらく反対票を獲得することになります。^_^
順位表
解決
GolfScript、 74 69 65
今一つの行に！
このソリューションは63文字ですが、数千のパスを持つテストケース（8分以上）で合理的な時間で実行されないため、カウントしないことを選択しました。
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]|}/}*,@-n@}/
より速い65文字ソリューション：
n%(~,{'Case #'\)@': '\(~1$+@[]@{\('/':!%@\{[n!++:!]+}/.&}*,@-n@}/
アルゴリズムのためのMarcogへの称賛！
他のヒント
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
このソリューションはeoferrorを投げますが、これはstderrへの出力であるため、ルール内にあります。出力はすべてに興味があるので、Stdoutに行くので、それをパイプしてStderrを無視できます。
上記（または他の投稿のいくつか）を読んで、それが機能しないはずだと思うかもしれません。その理由には少しトリックがあります。ここで説明します。質問を注意深く読むと、最初のリストの各ディレクトリについて、すべての親ディレクトリがリストに含まれていることがわかります（例：if /home /marcogが存在するので、 /home）[1]。また、各リストには重複がないことも保証されています[2]。これにより、最初のリストのすべてのディレクトリを同じセットに投げ込むことができます。質問はリストごとに複製を保証しないため、最初のリストがセットに正確にnエントリになることがわかっています。したがって、最終セットのサイズからnを差し引くことで最終回答を得ることができます。
1]「次のn行はそれぞれ、コンピューターに既に存在する1つのディレクトリのパスを提供します。このリストには、ルートディレクトリ以外のコンピューターに既に既にすべてのディレクトリが含まれます。」
2]「すでにコンピューターのディレクトリのリスト、または作成したいディレクトリのリストに2回登場することはありません。」
パール、 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 (ドルバッククォート;markdown では、通常のパターン マッチング機能の代わりに、これを適切に含めることができません。
\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 以降で実行してください。
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
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);
}
}
}
}
この最新バージョンには癖があります。ルートディレクトリを1回作成する必要があると誤ってカウントし、目的の0ではなく、ループの開始時に変数nが-1であることを補正します。ルートディレクトリがNにないことが保証されているために機能します。
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++"/")
他の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 ++ "/")
バッシュ、 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
ルビー、 151 149 144
Rubyへの直接翻訳 MarcogのPythonソリューション:
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}"}
ポストスクリプト
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
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]}
これには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
スカラ、 190 189
Marcog's Solutionのさらに別のバージョン、今回はScalaで。一緒に走ります 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)}
awk- 123 121 chars
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枚のcharが成長します。
BEGIN{FS=" |/"}
pyonscript
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
J- 205 159 140文字
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つの追加の行を出力します：/
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));}}}
注：エラーメッセージが出力されますが、それでも正しく機能します。
