最終更新: 2019-04-12T22:44+0900
「解けなくて飛ばした問題の中で一番最初の問題」シリーズ。今は Problem 66 なんだけど……解けない。気を取り直してテキトーに興味の持てる問題に取りかかってみたのが Problem 158。Difficulty Rating は Problem 66 が 25 % で、Problem 158 が 55 %。100 % に近い方が難しいっぽい。
#!rubyw # coding: utf-8 # Classified identity # # * p-value. # * the number of characters that will increment p-value. # ・ the number of characters that will not increment p-value. (can be calculated) # ・ length. (counted externally) # ・ string value and its rightmost character. (no use) p1, p0 = [0] * 26, [0] * 26 ("a".."z").each{|ch| p0["z".ord - ch.ord] += 1 } 2.upto(26){|length| q1, q0 = [0] * (27 - length), [0] * (27 - length) # increment p0.each.with_index{|sum, number| number.times{|n| q1[n] += sum } } # not increment p0.each.with_index{|sum, number| not_number = 27 - length - number not_number.times{|n| q0[n + number] += sum } } p1.each.with_index{|sum, number| not_number = 27 - length - number not_number.times{|n| q1[n + number] += sum } } puts "p(%2d) = %12d"%[length, q1.inject(&:+)] p1, p0 = q1, q0 }
過去に Problem 191 を解いた経験が生きている。ちなみに Problem 191 の Difficulty Rating は 35 %。
最終更新: 2019-01-15T14:13+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
普通に手続き的に書けば一瞬で答えが出る問題だったのに、前回も今回も(同じ)プログラムのバグのために答えが出なくて、でも素因数分解して漏れなく重複なく数えることもできなくて困っていた。バグが取れたので答えを出すのはコンピュータに任せる。
#!rubyw # coding: utf-8 h = {} (2..100).each{|b| (2..100).inject(b){|_,| _ *= b h[_] = _ } } p h.size
最終更新: 2019-01-16T18:40+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
(そういえば以前も何度となく同じことを書いていたなと思い出しながら)泥臭く手を動かしただけ。
#!rubyw # coding: utf-8 Digits = *1..9 found = {} (1..2).each{|_| Digits.combination(_){|l_cmb| l_cmb.permutation{|l| l = l.join('').to_i Digits.combination(5-_){|r_cmb| r_cmb.permutation{|r| r = r.join('').to_i p = l * r found[p] = "#{l} * #{r} = #{p}" if /^(?:([1-9])(?!.*\1)){9}$/ =~ "#{l}#{r}#{p}" } } } } } p found.keys.inject(&:+)
最終更新: 2019-01-15T16:36+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
ただ手を動かしただけ。
#!rubyw # coding: utf-8 require 'mathn' found = [] (1..9).each{|numer| (1..9).each{|denom| frac = numer / denom (numer+1..9).each{|cancel/| found.push("#{numer}#{cancel/}/#{cancel/}#{denom}") if frac == (numer*10 + cancel/) / (cancel/*10 + denom) (1..denom-1).each{|cancel\| found.push("#{cancel\}#{numer}/#{denom}#{cancel\}") if frac == (cancel\*10 + numer) / (denom*10 + cancel\) }} }} p found p found.map(&:to_r).inject(&:*).denominator
最終更新: 2019-01-15T17:32+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
以前は require 'prime'
を避けてた気がするけど、今回は使ってる。そうすると、ただコードに落とすだけ。
#!rubyw # coding: utf-8 require 'prime' require 'set' primes = Prime.each(1_000_000).to_set primes = primes.select{|p| s = "#{p}#{p}" l = s.length/2 (1..l-1).all?{|i| primes.include? s[i, l].to_i(10) } } p primes p primes.size
最終更新: 2019-01-15T21:09+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
例によって手を動かしただけ。
#!rubyw # coding: utf-8 PalindromeGen = lambda{|digits| return Enumerator.new{|y| _next = lambda{|a| return digits.map{|_| a.map{|p10| "#{_}#{p10}#{_}" } }.flatten } odd = *digits even = digits.zip(digits).map{|_| _.join('') } yielder = lambda{|p| y << p} loop { odd = _next[odd.each(&yielder)] even = _next[even.each(&yielder)] } } } p10gen = PalindromeNGen["0".."9"] p2gen = PalindromeNGen["0".."1"] found = {} loop { p10 = p10gen.next.to_i(10) break if 1_000_000 < p10 p2gen.next while p2gen.peek.to_i(2) < p10 found[p10] = p10 if p2gen.peek.to_i(2) == p10 } p found.keys.map{|_| [_.to_s(10), _.to_s(2)] } p found.keys.inject(&:+)
最終更新: 2019-01-15T23:54+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
手を動かしただけ。
#!rubyw # coding: utf-8 require 'prime' require 'set' primes = Set.new found = {} Prime.each{|p| p = p.to_s(10) primes << p next if p.length == 1 next unless (1..(p.length-1)).all?{|w| primes.include? p[0,w] } next unless (1..(p.length-1)).all?{|i| primes.include? p[i,p.length-i] } p found[p] = p break if found.size == 11 } p found.keys.map(&:to_i).inject(&:+)
最終更新: 2019-01-16T18:01+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
手を動かしただけ。
#!rubyw # coding: utf-8 found = {} i = 1 9.downto(2){|n| loop { s = (1..n).map{|_| _*i }.join('') break if 9 < s.length i += 1 next if s.length < 9 next if s.index "0" found[s.to_i] = [i-1, 1..n] unless /(.).*\1/ =~ s } } p found p found.keys.sort.reverse
最終更新: 2019-01-16T00:54+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。
素数って実はありふれてるので9桁までの素数を列挙するだけで許容時間(1分間)をオーバーしてしまう。9桁の順列(362880通り)を列挙して素数判定する方が早い。
#!rubyw # coding: utf-8 require 'prime' found = ("1".."9").map{|n| ("1"..n).to_a.permutation.map{|_| _.join('').to_i }.select(&:prime?) }.flatten p found.sort.reverse
最終更新: 2019-01-16T03:47+0900
面倒くさくて飛ばした問題にチャレンジ。
poker.txt の内容は本当にランダムなのか3番目までの高い役が1個も入ってなくて、コーディングの苦労が報われない。
#!rubyw # coding: utf-8 Order = "23456789TJQKA" flush = lambda{|cards| # p ["flush", cards] if (cards.match(/^ .(.)(?: .\1){4}/)||[])[1] (cards.match(/^ .(.)(?: .\1){4}/)||[])[1] } straight = lambda{|cards| # p ["straignt", cards] if cards.scan(/ (.)/).map{|_,| Order.index _ }.sort.tap{|_| break _ == (_[0].._[0]+4).to_a ? Order[0] : nil } cards.scan(/ (.)/).map{|_,| Order.index _ }.sort.tap{|_| break _ == (_[0].._[0]+4).to_a ? Order[0] : nil } } four = lambda{|cards| p ["four", cards] if cards.scan(/ (.)/).sort.join('').scan(/(.)\1{3}/).map{|_,| _ }[0] cards.scan(/ (.)/).sort.join('').scan(/(.)\1{3}/).map{|_,| _ }[0] } three = lambda{|cards| # p ["three", cards] if cards.scan(/ (.)/).sort.join('').scan(/(.)\1{2}/).map{|_,| _ }[0] cards.scan(/ (.)/).sort.join('').scan(/(.)\1{2}/).map{|_,| _ }[0] } pairs = lambda{|cards| # p ["pairs", cards] unless cards.scan(/ (.)/).sort_by{|_,| - Order.index(_) }.join('').scan(/(.)\1/).map{|_,| _ }.empty? cards.scan(/ (.)/).sort_by{|_,| - Order.index(_) }.join('').scan(/(.)\1/).map{|_,| _ } } highcards = lambda{|cards| # p ["highcards", cards] cards.scan(/ (.)/).sort.join('').gsub(/(.)\1+/, '').split(//).sort_by{|_| - Order.index(_) } } fullhouse = lambda{|cards| # p ["fullhouse", cards] if pairs[cards].length == 2 and three[cards] pairs[cards].length == 2 and three[cards] } straightflush = lambda{|cards| suit = flush[cards] first = straight[cards] p ["straightflush", cards] if suit and first suit and first } royalflush = lambda{|cards| first = straightflush[cards] p ["royalflush", cards] if first and first == 'T' first and first == 'T' } compare = lambda{|h| h.map{|_| Array(_).map{|_| _ ? Order.index(_)||-1 : -2 } }.tap{|h| break h.first.length != h.last.length ? h.first.length <=> h.last.length : h.first <=> h.last } } contest = lambda{|c| [royalflush, straightflush, four, fullhouse, flush, straight, three, pairs, highcards ].each{|ranktest| h = c.map(&ranktest) return compare[h] if h.any?{|_| _ and not _.empty? } } raise "no contest" } p DATA.lines.map{|ln| p1 = " " + ln[0, 15] p2 = ln[14, 15] + " " contest[[p1, p2]] }.count(1) __END__ content of poker.txt here.
最終更新: 2019-01-14T23:35+0900
解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。a の定義、b の定義、b が限界を定める、というところから、あとは計算。15 秒くらいかかってもいいでしょう。
#!rubyw # coding: utf-8 require 'prime' a = *-1000..0 b = Prime.each(1000).reject {|_| _ < 80 } remains = a.product b (0..1000).each {|n| remains.reject! {|a, b| n == b or n + a == -b or (n * (n + a) + b) <= 0 or not (n * (n + a) + b).prime? } puts "remains #{remains.size}" puts "a = %d; b = %d; n = %d" % [*remains[0], n] if remains.size == 1 break if remains.size <= 1 }