-
Notifications
You must be signed in to change notification settings - Fork 0
/
solutions.rb
435 lines (410 loc) · 16.3 KB
/
solutions.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
require 'Prime'
require 'matrix'
require 'benchmark'
if __FILE__ == $0
end
def run(&problem)
result = ""
time = Benchmark.measure do
result = problem.call
end
"The answer is: #{result}, executed in #{time.real}."
end
# assuming we don't have a built in function
def prime?(input)
(2..(input ** 0.5 + 1).to_i).each do |x|
return false if (input % x).zero?
end
true
end
# assuming we don't have a built in function
def next_prime(last_prime=2)
next_prime = last_prime + 1
until prime?(next_prime)
next_prime += 1
end
return next_prime
end
def palindrome?(input)
input_s = input.to_s
input_s.reverse == input_s
end
# intended for numbers, doesn't work with spaces
def palindrome_no_reverse?(input)
input_s = input.to_s
(1...(input_s.length/2+1)).each do |i|
return false if input_s[i-1] != input_s[-i]
end
return true
end
def divisible?(value, divisors)
divisors.each do |d|
return false if value % d != 0
end
return true
end
# Largest palindrome product
# Problem 4
# A palindromic number reads the same both ways. The largest palindrome made
# from the product of two 2-digit numbers
# is 9009 = 91 99.
# Find the largest palindrome made from the product of two 3-digit numbers.
def p4
array = (800..999).to_a
array = array.map{|x| array.map{|y| x * y}}.flatten.uniq
array = array.select{|x| palindrome?(x)}
array.max
end
# Smallest multiple
# Problem 5
# 2520 is the smallest number that can be divided by each of the numbers from
# 1 to 10 without any remainder.
# What is the smallest positive number that is evenly divisible by all of the
# numbers from 1 to 20?
def p5
divisors = (1..20).to_a
num = divisors[-1]
loop do
break if divisible?(num, divisors)
num += divisors[-1]
end
return num
end
# Sum square difference
# Problem 6
# The sum of the squares of the first ten natural numbers is,
# 12 + 22 + ... + 102 = 385
# The square of the sum of the first ten natural numbers is,
# (1 + 2 + ... + 10)2 = 552 = 3025
# Hence the difference between the sum of the squares of the first ten
# natural numbers and the square of the sum is 3025 385 = 2640.
# Find the difference between the sum of the squares of the first one hundred
# natural numbers and the square of the sum.
def p6
range = (1..100).to_a
square_of_sum = range.reduce(:+) ** 2
sum_of_square = (range.map{|x| x ** 2}).reduce(:+)
square_of_sum - sum_of_square
end
# 10001st prime
# Problem 7
# By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
# that the 6th prime is 13.
# What is the 10001st prime number?
# assuming there is no built in method
def p7
primes = [2]
(1...10001).each do
prime = next_prime(primes[-1])
primes << prime
end
primes[-1]
end
# Largest product in a series
# Problem 8
# Find the greatest product of five consecutive digits in the 1000-digit number.
# 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
def p8
value = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
value_array = value.to_s.split('').map(&:to_i)
products = []
(0...value_array.length-5).each do |i|
product = value_array[i...i+5].reduce(:*)
products << product
end
products.max
end
# Special Pythagorean triplet
# Problem 9
# A Pythagorean triplet is a set of three natural numbers, a b c, for which,
# a^2 + b^2 = c^2
# For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
# There exists exactly one Pythagorean triplet for which a + b + c = 1000.
# Find the product abc.
def p9
a, x = 1, 1000
loop do
b = (2.0 * x * a - x ** 2.0) / (2.0 * a - 2.0 * x)
if (b % 1).zero?
c = (a ** 2 + b ** 2) ** 0.5
puts triplet = [a,b,c].to_a
return triplet.reduce(:*)
end
a += 1
end
end
# Summation of primes
# Problem 10
# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
# Find the sum of all the primes below two million.
def p10
primes = []
Prime.each do |prime|
break if prime >= 2000000
primes << prime
end
# puts primes
primes.reduce(:+)
end
# Largest product in a grid
# Problem 11
# In the 2020 grid below, four numbers along a diagonal line have been marked in red.
# The product of these numbers is 26 63 78 14 = 1788696.
# What is the greatest product of four adjacent numbers in the same direction
# (up, down, left, right, or diagonally) in the 2020 grid?
def p11
grid = Matrix[
[8, 2, 22,97,38,15,0, 40,0, 75,4, 5, 7, 78,52,12,50,77,91,8],
[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4, 56,62,0],
[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3, 49,13,36,65],
[52,70,95,23,4, 60,11,42,69,24,68,56,1, 32,56,71,37,2, 36,91],
[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],
[24,47,32,60,99,3, 45,2, 44,75,33,53,78,36,84,20,35,17,12,50],
[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],
[67,26,20,68,2, 62,12,20,95,63,94,39,63,8, 40,91,66,49,94,21],
[24,55,58,5, 66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
[21,36,23,9, 75,0, 76,44,20,45,35,14,0, 61,33,97,34,31,33,95],
[78,17,53,28,22,75,31,67,15,94,3, 80,4, 62,16,14,9, 53,56,92],
[16,39,5, 42,96,35,31,47,55,58,88,24,0, 17,54,24,36,29,85,57],
[86,56,0, 48,35,71,89,7, 5, 44,44,37,44,60,21,58,51,54,17,58],
[19,80,81,68,5, 94,47,69,28,73,92,13,86,52,17,77,4, 89,55,40],
[4, 52,8, 83,97,35,99,16,7, 97,57,32,16,26,26,79,33,27,98,66],
[88,36,68,87,57,62,20,72,3, 46,33,67,46,55,12,32,63,93,53,69],
[4, 42,16,73,38,25,39,11,24,94,72,18,8, 46,29,32,40,62,76,36],
[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4, 36,16],
[20,73,35,29,78,31,90,1, 74,31,49,71,48,86,81,16,23,57,5, 54],
[1, 70,54,71,83,51,54,69,16,92,33,48,61,43,52,1, 89,19,67,48]
]
products = []
(0...grid.row_count).each do |row|
(0...grid.column_count).each do |col|
right = col + 3 < grid.row_count
down = row + 3 < grid.column_count
left = col - 3 >= 0
if right
set = grid.minor(row..row,col..col+3)
products << set.reduce(:*)
end
if down and right
diagonal = []
(0..3).each do |x|
diagonal << grid.minor(row+x..row+x,col+x..col+x).component(0,0)
end
products << diagonal.reduce(:*)
end
if down
set = grid.minor(row..row+3,col..col)
products << set.reduce(:*)
end
if down and left
diagonal = []
(0..3).each do |x|
diagonal << grid.minor(row+x..row+x,col-x..col-x).component(0,0)
end
products << diagonal.reduce(:*)
end
end
end
products.max
end
# Highly divisible triangular number
# Problem 12
# The sequence of triangle numbers is generated by adding the natural numbers.
# So the 7th triangle number
# would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
# 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
# Let us list the factors of the first seven triangle numbers:
# 1: 1
# 3: 1,3
# 6: 1,2,3,6
# 10: 1,2,5,10
# 15: 1,3,5,15
# 21: 1,3,7,21
# 28: 1,2,4,7,14,28
# We can see that 28 is the first triangle number to have over five divisors.
# What is the value of the first triangle number to have over five hundred divisors?
class Integer
# def factors()
# (1..self).select { |n| (self % n).zero? }
# end
# def factors()
# 1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}
# end
def factors()
# [[0,2][1,10]] => [0,2,0]
# i^2 == self
1.upto(Math.sqrt(self)).select {|i| (self % i).zero?}.inject([]) do |f, i|
f << i
f << self/i unless i == self/i
f
end.sort
end
end
def p12
i = 1
sums = [0]
loop do
sums << i + sums.last
break if sums.last.factors.length >= 500
i += 1
end
return sums.last
end
# Large sum
# Problem 13
# Work out the first ten digits of the sum of the following one-hundred 50-digit
# numbers.
def p13
numbers = [
37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690,
]
sum = numbers.reduce(:+)
sum.to_s[0..9].to_i
end
# Longest Collatz sequence
# Problem 14
# The following iterative sequence is defined for the set of positive integers:
# n -> n/2 (n is even)
# n -> 3n + 1 (n is odd)
# Using the rule above and starting with 13, we generate the following sequence:
# 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
# It can be seen that this sequence (starting at 13 and finishing at 1) contains
# 10 terms. Although it has not been proved yet (Collatz Problem), it is thought
# that all starting numbers finish at 1.
# Which starting number, under one million, produces the longest chain?
# NOTE: Once the chain starts the terms are allowed to go above one million.
def next_collatz(n)
n.even? ? n / 2 : 3 * n + 1
end
def collect_collatz(list)
list = [list] unless list.kind_of?(Array)
return list if list.last == 1
list << next_collatz(list.last)
collect_collatz(list)
end
def p14
cache = {1 => 1}
(1...1000000).each do |n|
unless cache.has_key?(n)
collatz_list, stored_count = [n], 0
until collatz_list.last == 1
collatz_list << next_collatz(collatz_list.last)
if cache.has_key?(collatz_list.last)
stored_count = cache[collatz_list.last]
break
end
end
(0..collatz_list.length).each do |i|
cache[collatz_list[-1-i]] = i + stored_count
end
end
end
max_value = cache.values.max
cache.select {|k,v| v == max_value}
end
# Lattice paths
# Problem 15
# Starting in the top left corner of a 2x2 grid, and only being able to move to
# the right and down, there are exactly 6 routes to the bottom right corner.
# How many such routes are there through a 20x20 grid?
def p15
end