脳log[2019-02-02～]

最終更新: 2019-04-12T22:44+0900

♪ [ProjectEuler] Problem 158

「解けなくて飛ばした問題の中で一番最初の問題」シリーズ。今は 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

♪ [ProjectEuler] Problem 29

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

普通に手続き的に書けば一瞬で答えが出る問題だったのに、前回も今回も(同じ)プログラムのバグのために答えが出なくて、でも素因数分解して漏れなく重複なく数えることもできなくて困っていた。バグが取れたので答えを出すのはコンピュータに任せる。

#!rubyw
# coding: utf-8

h = {}
(2..100).each{|b|
	(2..100).inject(b){|_,|
		_ *= b
		h[_] = _
	}
}
p h.size

最終更新: 2019-01-16T18:40+0900

♪ [ProjectEuler] Problem 32

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

(そういえば以前も何度となく同じことを書いていたなと思い出しながら)泥臭く手を動かしただけ。

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

♪ [ProjectEuler] Problem 33

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

ただ手を動かしただけ。

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

♪ [ProjectEuler] Problem 35

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

以前は 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

♪ [ProjectEuler] Problem 36

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

例によって手を動かしただけ。

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

♪ [ProjectEuler] Problem 37

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

手を動かしただけ。

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

♪ [ProjectEuler] Problem 38

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

手を動かしただけ。

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

♪ [ProjectEuler] Problem 41

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。

素数って実はありふれてるので９桁までの素数を列挙するだけで許容時間(１分間)をオーバーしてしまう。９桁の順列(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

♪ [ProjectEuler] Problem 54

面倒くさくて飛ばした問題にチャレンジ。

poker.txt の内容は本当にランダムなのか３番目までの高い役が１個も入ってなくて、コーディングの苦労が報われない。

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

♪ [ProjectEuler] Problem 27

解けなくて飛ばした問題の中で一番最初の問題に再チャレンジ。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
}