Ruby: #8 关于 Project Euler，解决方案似乎不起作用，但我感觉很接近

Question

问题是：
1000位数字中乘积最大的四个相邻数字是9 × 9 × 8 × 9 = 5832。

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

找出 1000 位数字中相邻的 13 个数字的乘积最大。 这个产品的价值是多少？

sequence = "73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"

rows = sequence.each_line("\n").to_a # Split string at each new line, convert to array
products = []
num = 1

# Split each array in rows to an array of chars, while deleting the newline element.
(0...rows.length).each do |row|
  rows[row] = rows[row].split("")
  rows[row].delete("\n")
end

# Change every element in rows to an integer.
(0...rows.length).each do |row|
  (0...50).each do |i|
   rows[row][i] = rows[row][i].to_i
  end
end

# This is where the magic happens
n = 0

while n <= 19
  row = rows[n]
 while row.length >= 13
   for i in (0...13)
     num = num * row[i]
   end
   products.push(num)
   num = 1
   row = row.drop(1)
 end
 n += 1
end

print products.max

想法是为每行 50 位数字创建一个整数数组，遍历每个数组，将前 13 位数字相乘，将每个产品存储在名为产品的数组中。前 13 位相乘后，50 位数组的第一个索引被删除，只有 49 位，重复前 13 位相乘的过程，直到数组只剩下 13 个或更少的整数，所有的乘积被存储在产品中。

然后打印出products中的max number，应该是该序列中相邻13位数字的最大乘积，5377010688。但显然，这是错误的。我不知道为什么。请帮忙！

Answer 1

我认为您应该多尝试使用 Ruby 中的 String 方法。请看this page here.

您可以使用此处更简单的代码获得相同的结果：

sequence = "73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"

## This will remove all \n
seq = sequence.tr("\n","")

def multiply_arr(a)
  prod = 1
  a.each do |f|
    prod = prod * f.to_i    
  end
  prod
end


def max_product(s,n)
  max = -1
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    max = (prod > max) ? prod : max 
  end
  max
end

puts max_product(seq,4)
puts max_product(seq,13)

我运行它在这里得到了以下输出

5832
23514624000

如您所见，第一个产品与您得到的一样。还没有验证第二个，但这对你来说很容易。

顺便说一句，这种代码确实更通用。现在你可以这样写

puts max_product(seq,5)

并接收

作为答案。然后你解决了一个比 'calculate it for 4' 和 'calculate it for 13'.

更普遍的问题

顺便说一句！如果您想知道什么序列产生这个最大值，您可以轻松地将代码重写为

def max_product(s,n)
  max = -1
  maxarr = []
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    if (prod > max) 
      max = prod
      maxarr = arr
    end
  end
  { "array" => maxarr, "prod" => max }
end

然后你会得到这个

{"array"=>["9", "9", "8", "9"], "prod"=>5832}
{"array"=>["5", "5", "7", "6", "6", "8", "9", "6", "6", "4", "8", "9", "5"], "prod"=>23514624000}

希望对您有所帮助！

Answer 2

你让自己的生活变得比你需要的更艰难。 Ruby 核心库已经很全了（还有更全的标准库，但其实对于这个问题核心库已经绰绰有余了），何乐而不为呢？

def max_product_subsequence(sequence, subsequence_length)
  sequence.
    gsub(/\s+/, '').                   # remove whitespace
    each_char.                         # split into characters
    map(&:to_i).                       # convert to integers
    each_cons(subsequence_length).     # sliding window of subsequences
    map {|subseq| subseq.reduce(:*) }. # map each subsequence to its product
    max                                # get the maximum
end

Ruby: #8 关于 Project Euler，解决方案似乎不起作用，但我感觉很接近

Ruby: #8 on Project Euler, solution doesn't seem to work, but I feel so close

ruby

project