プロジェクト・オイラー

プログラムで解く数学の問題集です。

サイト：　https://projecteuler.net/
日本語訳サイト：　http://odz.sakura.ne.jp/projecteuler/index.php?Project%20Euler

参考になるサイト：　桃の天然水

以下は自分用の覚え書きです。

class Array
  def count_same_objects
    h = {}
    each do |ob|
      a = count(ob)
      h[ob] = a if a > 1
    end
    h
  end
end
 
class String
  def to_intg
    Value.find_index(self) + 2
  end
end

class PokerHands
  def initialize(data)
    a = eval("%w(#{data})")
    hd = []
    a.each {|h| b = h.split(""); hd << [b[0].to_intg, b[1]]}
    @hand = hd.transpose
  end
  
  def hi    #Hash inverted
    @hand[0].count_same_objects.invert
  end
  
  def high_card?
    @hand[0].sort {|a, b| b <=> a}
  end
  
  def one_pair?
    return false unless @hand[0].count_same_objects.values.count(2) == 1
    a = @hand[0].count_same_objects.keys
    a + (@hand[0].uniq - a).sort {|a, b| b <=> a}
  end
  
  def two_pairs?
    return false unless @hand[0].count_same_objects.values.count(2) == 2
    c = @hand[0].count_same_objects.keys.sort
    d = [c[-1], c[-2]]
    d + (@hand[0].uniq - d)
  end
  
  def three_of_a_kind?
    return false unless @hand[0].count_same_objects.values.include?(3)
    c = (@hand[0] - [hi[3]]).sort
    [hi[3], c[1], c[0]]
  end
  
  def straight?
    a = @hand[0].sort
    a.each_with_index {|v, i| return false unless v == a[0] + i}
    a[-1]
  end
  
  def flush?
    a = @hand[1].count_same_objects
    a.each_key {|k| return @hand[0].sort {|a, b| b <=> a} if a[k] == 5}
    false
  end
  
  def full_house?
    a = @hand[0].count_same_objects
    return false unless a.values.include?(3) and a.values.include?(2)
    [hi[3], hi[2]]
  end
  
  def four_of_a_kind?
    return false unless @hand[0].count_same_objects.values.include?(4)
    [hi[4], (@hand[0].uniq - [hi[4]])[0]]
  end
  
  def straight_flush?
    return false unless (a = straight?) and flush?
    a
  end
  
  def royal_flush?
    straight? == 14 and flush?
  end
  
  def open_hand
    Fn.each_with_index do |mthd, i|
      a = send(mthd)
      return i, a if a
    end
  end
end

def player1_won?(hand1, hand2)
  i1, a1 = hand1.open_hand
  i2, a2 = hand2.open_hand
  puts "hand1: #{Fn[i1][0..-2]},  hand2: #{Fn[i2][0..-2]}"
  return true if i1 < i2
  return false if i1 > i2
  a1.size.times do |j|
    return true if a1[j] > a2[j]
    return false if a1[j] < a2[j]
  end
  raise "error"
end

Value = %w(2 3 4 5 6 7 8 9 T J Q K A)
Fn = %i(royal_flush? straight_flush? four_of_a_kind? full_house?
            flush? straight? three_of_a_kind? two_pairs? one_pair? high_card?)
counter = 0
File.open("p054_poker.txt") do |io|
  io.each_line do |hand|
    hand.chomp!
    hand1 = PokerHands.new(hand[0..13])
    hand2 = PokerHands.new(hand[15..28])
    counter += 1 if player1_won?(hand1, hand2)
  end
end
puts counter

自然数の分割についてはこちら。

フォーラムのutkarsh_23氏の Python コードです。数式
　　　　　
を使っています（参照）。

def pent(n):
    return (n * (3 * n - 1)) / 2
    
def dyf(num):
    if num < 0:
        return 0
    elif num in memo:
        return memo[num]
    else:
        f = 0
        for a in range(len(L)):
            f += L[a][0] * dyf(num - L[a][1])
    memo[num] = f
    return f
    
global L,memo
memo = {0:1}
number = 100
n = 1
L = []
while True:
    sign = 1
    if n % 2 == 0:
        sign = -1
    if number - pent(n) >= 0:
        L.append((sign , pent(n)))
    else:
        break
    if number - pent(-1 * n) >= 0:
        L.append((sign , pent(-1 * n)))
    else:
        break
    n += 1
L = L[::-1]
print (dyf(number) - 1)

上を Ruby で書き直しました。

def pent(n)
  (n * (3 * n - 1)) / 2
end

def dyf(num)
  return 0 if num < 0
  return @memo[num] if @memo.has_key?(num)
  f = 0
  @l.size.times {|a| f += @l[a][0] * dyf(num - @l[a][1])}
  @memo[num] = f
end

#main
@memo = {0=>1}
number = 100
n = 1
@l = []
loop do
  sign = n.even? ? -1 : 1
  break unless number >= (a = pent(n))
  @l << [sign , a]
  break unless number >= (a = pent(-1 * n))
  @l << [sign , a]
  n += 1
end
@l.reverse!
puts dyf(number) - 1    #=>190569291

BigDecimalライブラリを使えば簡単です。

require 'bigdecimal'
require 'utils'

co = 0
for i in 1..100
  next if Math.sqrt(i).integer?
  BigDecimal(i).sqrt(100).to_s[2..101].each_char {|s| co += s.to_i}
end
puts co    #=>40886