ここからの続きです。
ここからの続きです。
a = b = 1
counter = 0
ans = []
while counter < 11
a, b = b, a + b
sum = b.to_s.chars.inject(0) {|r, j| r += j.to_i}
if (b % sum).zero?
ans << b
counter += 1
end
end
p ans[-5..-1]
#=>[2584, 14930352, 86267571272, 498454011879264, 160500643816367088]
def contain?(st)
for i in 0..9
return false unless st.include?(i.to_s)
end
true
end
def main(fn)
i = 2
min = 100
begin
st = fn[i]
10.upto(st.length) do |j|
if contain?(st[0, j]) and j < min
puts "#{i}: #{j}桁"
min = j
break
end
end
return if min == 10
end while (i += 1)
end
f = ->(i) {Math.sqrt(i).to_s.split(".")[1]}
g = ->(i) {Math.sqrt(i).to_s.gsub(/\./, "")}
main(f) #結果は143（少数部分のみ）
puts
main(g) #結果は1362（整数部分を含む）
#13: 14桁
#22: 12桁
#44: 11桁
#143: 10桁
#13: 15桁
#22: 13桁
#44: 12桁
#143: 11桁
#1362: 10桁
覆面算。READ + WRITE + TALK = SKILL。
class Array
def num
i = sum = 0
ar = dup
while (a = ar.pop)
sum += a * (10 ** i)
i += 1
end
sum
end
end
counter = 0
(0..9).to_a.permutation(10) do |ar|
r, e, a, d, w, i, t, l, k, s = ar
next if r.zero? or w.zero? or t.zero? or s.zero?
read = [r, e, a, d].num
write =[w, r, i, t, e].num
talk = [t, a, l, k].num
skill = [s, k, i, l, l].num
if read + write + talk == skill
puts "#{ar}"
counter += 1
end
end
puts counter #=>10
#[1, 6, 3, 2, 4, 9, 7, 8, 0, 5]
#[2, 5, 4, 3, 7, 0, 6, 9, 1, 8]
#[4, 9, 0, 5, 2, 6, 8, 1, 7, 3]
#[5, 0, 9, 4, 7, 3, 1, 6, 2, 8]
#[5, 0, 9, 6, 3, 7, 1, 8, 2, 4]
#[5, 1, 8, 0, 6, 9, 2, 4, 3, 7]
#[5, 2, 7, 0, 8, 1, 3, 6, 4, 9]
#[7, 0, 9, 2, 3, 5, 1, 8, 6, 4]
#[7, 0, 9, 2, 4, 3, 1, 8, 6, 5]
#[9, 7, 2, 8, 1, 4, 6, 0, 5, 3]
#user 0m9.076s
手製のTreeクラスを使ってみました。下の国名しりとりで、いちばん長く続くのは何カ国かという問題です。
require 'utils'
require './tree'
class String
def head; self[0].downcase; end
def tail; self[-1].downcase; end
end
class Array
def choose(country)
select {|c| c.name.head == country.name.tail}
end
def contain?(a)
each {|x| return true if a.name == x.name}
false
end
end
class Country
def initialize(name)
@name = name
end
attr_reader :name
def to_s; @name; end
end
def add_branches(c, ar)
cos = $countries.choose(c) - ar
if cos.empty?
return
end
cos.each do |c1|
next if $t.get_nodes(:root, c)[1..-1].contain?(c1)
begin
$t.add(c, c1)
rescue
a = c1
$t.add(c, c1 = c1.dup)
$countries.map! {|i| (i.name == a.name) ? c1 : i}
ar.map! {|i| (i.name == a.name) ? c1 : i}
end
add_branches(c1, ar + [c1])
$countries = $countries.deep_copy
end
end
#main
data = ["Brazil", "Cameroon", "Chile", "Greece", "Uruguay", "Italy", "France",
"Bosnia and Herzegovina", "Germany", "USA", "Russia", "Croatia", "Spain",
"Australia", "Cote d'lvoire", "Costa Rica", "Switzerland", "Honduras",
"Iran", "Portugal", "Belgium", "Korea Republic", "Mexico", "Netherlands",
"Colombia", "Japan", "England", "Ecuador", "Argentina", "Nigeria", "Ghana", "Algeria"]
$countries = data.map {|name| Country.new(name)}
$t = Tree.new(:root)
$countries.dup.each do |country|
$t.add(:root, country)
add_branches(country, [country])
$countries = $countries.deep_copy
end
$t.put_out
puts $t.max_depth(:root) #=>8
結果。
別解。 こちらの別のTree実装を使ってみました。こちらの方がかなりシンプルに書けています。もちろん答えは同じです。
require './tree1'
def add_branches(c, ar)
countries = Country - ar
loop do
return if countries.empty?
co = countries.shift
if c.value[-1].downcase == co[0].downcase
$t.add_node(new_c = Node.new(co, c))
add_branches(new_c, ar + [co])
end
end
end
#main
Country = ["Brazil", "Cameroon", "Chile", "Greece", "Uruguay", "Italy", "France",
"Bosnia and Herzegovina", "Germany", "USA", "Russia", "Croatia", "Spain",
"Australia", "Cote d'lvoire", "Costa Rica", "Switzerland", "Honduras",
"Iran", "Portugal", "Belgium", "Korea Republic", "Mexico", "Netherlands",
"Colombia", "Japan", "England", "Ecuador", "Argentina", "Nigeria", "Ghana", "Algeria"]
$t = Tree.new(Root = Node.new(:root, nil))
Country.each do |country|
$t.add_node(co = Node.new(country, Root))
add_branches(co, [country])
end
$t.put_out
puts $t.max_depth(Root) #=>8
問題がわかりにくい。これでは、AさんもBさんも必ず動かねばならないのかわからない。
自分に見落としがあって苦労した。
N = 500
ans = []
12.step(N, 4) do |l|
a = l / 4
1.upto(a - 1) do |b1|
b1.upto(a - 1) do |c1|
b2 = a * 2 - b1
c2 = a * 2 - c1
if a * a == b1 * b2 + c1 * c2
f = lambda {
ans.each do |ar|
r = ar[0] / a.to_f
return false if r == ar[1] / b1.to_f and r == ar[2] / c1.to_f
end
true
}
ans << [a, b1, c1] if f.call
end
end
end
end
p ans
puts ans.size #=>20
簡単。
require 'bundler/setup'
require 'utils'
a = 0
(0..15).each {|i| a += Utils.combination(31 - i, i)}
puts a #=>2178309
これでは時間がかかりすぎてまったく実用的ではない。実際にこれで求めることは不可能。書籍の模範解答はすごい。1.5秒程度の瞬殺。
def check(n, cutted)
0.upto(n) do |i|
return false unless Sqr.include?(cutted[i - 1] + cutted[i])
end
true
end
Sqr = (2..100).to_a.map {|i| i * i}
n = 1
while (n += 1)
print "\e[1G#{n}"
(2..n).to_a.permutation do |cutted|
cutted.unshift(1)
if check(n, cutted)
puts "\n#{n}"
exit
end
end
end
模範解答も載せておく。じつに短い。
def check(n, pre, log, square)
if n == log.size
if square.include?(1 + pre)
puts n
p log
return true
end
else
((1..n).to_a - log).each do |i|
if square.include?(pre + i)
return true if check(n, i, log + [i], square)
end
end
end
false
end
n = 2
loop do
square = (2..Math.sqrt(n * 2).floor).map{|i| i ** 2}
break if check(n, 1, [1], square)
n += 1
end
#=>32
#=>[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
元の自分のコード。
table = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 13, 14, 14, 15]
h = {}
for i in 1..16
table.combination(i) do |ar|
sum = ar.inject(:+)
h[sum] = 0 unless h.has_key?(sum)
h[sum] += 1
end
end
puts h.invert[h.values.max] #=>66
模範解答を参考にした修正版。ハッシュのデフォルト値の指定と、ハッシュの値のソートによる最大値の求め方について修正。
table = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 13, 14, 14, 15]
h = Hash.new(0)
for i in 1..16
table.combination(i) do |ar|
h[ar.inject(:+)] += 1
end
end
p h.max {|a, b| a[1] <=> b[1]} #=>[66, 1364]
上のどちらでやっても瞬殺は変わらない。
require 'bundler/setup'
require 'utils'
counter = 0
row = [1, 1]
loop_with_index(3) do |i|
n_row = Array.new(i)
n_row[0] = n_row[-1] = 1
for j in 1..(i - 2)
if (n_row[j] = row[j - 1] ^ row[j]).zero?
counter += 1
if counter == 2014
puts i
exit
end
end
end
row = n_row
end
#=>75
動的計画法…。模範解答はすごいです。
素直な再帰。if文の順序をまちがえていて（3行目と4行目）計算が合わなかった。これがちゃんと結果に効いてくるのだな。勉強になりました。
def play(coin, depth) count = 0 return 1 if depth.zero? return 0 if coin.zero? count += play(coin + 1, depth - 1) count += play(coin - 1, depth - 1) end puts play(10, 24) #=>16195220 #real 0m3.166s
メモ化して高速化。
def play(coin, depth)
return @memo[[coin, depth]] if @memo.has_key?([coin, depth])
count = 0
return 1 if depth.zero?
return 0 if coin.zero?
count += play(coin + 1, depth - 1)
count += play(coin - 1, depth - 1)
@memo[[coin, depth]] = count
end
@memo = {}
puts play(10, 24) #=>16195220
#real 0m0.083s
約0.3秒。二抜きの回数によって場合分けしている。#<Set: ...>は二抜きのパターン。
一応自力で解けたのだが、模範解答はメモ化を使って極めてシンプルです。すごいなあ。
require 'bundler/setup'
require 'set'
require 'utils'
def check(try, board)
try.each {|x| return false unless board.include?(x)}
board - try
end
def throw(table, board, process, num, co)
if co == num
@list << process.sort
return
end
table.each do |try|
next unless (a = check(try, board))
throw(table - [try], a, process + [Table.index(try)], num, co + 1)
end
end
#main
counter = 0
Table = [[1, 2], [2, 3], [3, 6], [6, 9], [9, 8], [8, 7], [7, 4], [4, 1]]
@list = Set.new
throw(Table, [1, 2, 3, 4, 6, 7, 8, 9], [], 3, 0)
counter += @list.size * 6.factorial
@list = Set.new
throw(Table, [1, 2, 3, 4, 6, 7, 8, 9], [], 2, 0)
counter += @list.size * 7.factorial
counter += 9.factorial + 8 * 8.factorial + 2 * 5.factorial
puts counter #=>798000
#<Set: {[0, 2, 4], [0, 2, 5], [0, 2, 6], [0, 3, 5], [0, 3, 6], [0, 4, 6], [1, 3, 5], [1, 3, 6],
# [1, 3, 7], [1, 4, 6], [1, 4, 7], [1, 5, 7], [2, 4, 6], [2, 4, 7], [2, 5, 7], [3, 5, 7]}>
#<Set: {[0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 4],
# [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [4, 6], [4, 7], [5, 7]}>