So-net無料ブログ作成

CodeIQ GemString問題のコード [いくらなんでも]

結城浩さんのCodeIQ「The Essence of Programming」

https://codeiq.jp/ace/yuki_hiroshi/

のGemString問題の解答用のrubyのコードです。

# abbbbcddddeefggg = [1,4,1,4,2,1,3] # eagcdfbe <== goal # ---------------------------------------------------------------- # ---------------------------------------------------------------- # allcomb([3,1,2],4) => [[3,1,0],[3,0,1],[2,1,1],[2,0,2],[1,1,2]] # 重複するものも含む素材個数リストstlから、計sum個の素材セットを選んで列挙する。 def allcomb(stl,sum) if sum<0 [] elsif stl.length<=1 if stl[0]<sum [] elsif sum==0 [[0]] else [[sum]] end else ans=[] l=stl.length-1 for i in (0..stl[0]) j=stl[0]-i sans=allcomb(stl[1..l],sum-j) if sans!=[] sans.each{|x| ans << [j]+x } else [] end end ans end end # ---------------------------------------------------------------- # fact(n)=n! 階乗 def fact(n) if n<=1 1 else n*fact(n-1) end end # ---------------------------------------------------------------- # allperm([2,1,2],5) => "aabcc"から5個以下を選んでの順列の総数を返す。 def allperm(stl,mxn) ans=0 for i in (0..mxn) allcomb(stl,i).each{|x| div=1 x.each{|m| div=div*fact(m) } ans=ans+fact(i)/div } end ans end # allperms([2,1,2]) => "aabcc"から部分順列の総数を返す。 def allperms(stl) maxl=0 stl.each{|x| maxl=maxl+x } allperm(stl,maxl) end # ---------------------------------------------------------------- # 素材から、素材集と素材個数リストを返す。 def pattlst(gems) p gems glst=[] gcnt=[] gems.each_char{|c| if !glst.include?(c) glst<<c gcnt<<gems.count(c) end } [glst,gcnt] end </pre> <pre> # ---------------------------------------------------------------- def gemsindex(gem,pat,gal) if gal.length<1 0 else cars=gal[0] cdrs=gal[1..-1] cidx=gem.index(cars) p [cars,cdrs,cidx] ans=0 if cidx>0 for i in (0..cidx-1) tmpat=pat.clone tmpat[i]=tmpat[i]-1 ans=ans+allperms(tmpat) end end ans=ans+1 pat[cidx]=pat[cidx]-1 ans+gemsindex(gem,pat,cdrs) end end # ---------------------------------------------------------------- # 走らせるとこ。サンプルと本題と # ---------------------------------------------------------------- gems='aaabcc' goal='caba' gpat=pattlst(gems) gemm=gpat[0] pats=gpat[1] p gemm,pats p gemsindex(gemm,pats,goal) # ---------------------------------------------------------------- gems='abbbbcddddeefggg' goal='eagcdfbe' gpat=pattlst(gems) gemm=gpat[0] pats=gpat[1] p gemm,pats p gemsindex(gemm,pats,goal) # 実行結果 # 〜------------------------------------ results 10:15:48 u "aaabcc" ["a", "b", "c"] [3, 1, 2] ["c", "aba", 2] ["a", "ba", 0] ["b", "a", 1] ["a", "", 0] 144 "abbbbcddddeefggg" ["a", "b", "c", "d", "e", "f", "g"] [1, 4, 1, 4, 2, 1, 3] ["e", "agcdfbe", 4] ["a", "gcdfbe", 0] ["g", "cdfbe", 6] ["c", "dfbe", 2] ["d", "fbe", 3] ["f", "be", 5] ["b", "e", 1] ["e", "", 4] 5578864439
nice!(0)  コメント(0)  トラックバック(0) 
共通テーマ:学問

2009年の作品を一つ備忘録代わりに [TeX-metapost]

わりと上手に出来てるやんとか、今更思う。 poincareD02.jpg
nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:学問
メッセージを送る

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。

×

この広告は1年以上新しい記事の更新がないブログに表示されております。