Ruby: #8 关于 Project Euler,解决方案似乎不起作用,但我感觉很接近
Ruby: #8 on Project Euler, solution doesn't seem to work, but I feel so close
问题是:
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。但显然,这是错误的。我不知道为什么。请帮忙!
我认为您应该多尝试使用 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)
并接收
40824
作为答案。然后你解决了一个比 '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}
希望对您有所帮助!
你让自己的生活变得比你需要的更艰难。 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
问题是:
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。但显然,这是错误的。我不知道为什么。请帮忙!
我认为您应该多尝试使用 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)
并接收
40824
作为答案。然后你解决了一个比 '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}
希望对您有所帮助!
你让自己的生活变得比你需要的更艰难。 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