-
Notifications
You must be signed in to change notification settings - Fork 4
/
3.rb
53 lines (44 loc) · 2.56 KB
/
3.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
# My logic unit indicates that you must have a math coprocessor. Loading question 3...
#
# The following sequence of digits sums to 5824. Break up the sequence into the LARGEST
# number of contiguous subsequences such that the sums of each of the subsequences are
# equal. Enter the number of subsequences below to continue.
class DigitQueue
def initialize(chars)
@size = chars.size
@chars = chars.each_char
end
def empty?
@size.zero?
end
def next
@size -= 1
@chars.next.to_i
end
end
# Splits input into consecutive contiguous subsequences that
# add up to the subsequence_sum. Returns nil if can't be
# evenly split in this manner, otherwise returns the cardinality
# of the subsequence set.
def num_subsequences(input, subsequence_sum)
digits = DigitQueue.new input
num = 0
until digits.empty?
crnt_sum = 0
while crnt_sum < subsequence_sum && !digits.empty?
crnt_sum += digits.next
end
return nil unless crnt_sum == subsequence_sum
num += 1
end
num
end
input = DATA.read.strip
input.each_char.inject(0) { |sum, char| sum + char.to_i } # => 5824
subsequence_sum = (9..5824).find do |size|
num_subsequences input, size
end
subsequence_sum # => 91
num_subsequences input, subsequence_sum # => 64
__END__
2298163507642079319714044011236386616537514556458624876361063538594523631728704374833046762730571781372667347996722877761242458964516235987144911867899093570411259125272325950690385718016406645948728247900092493610635939061585125579278248678382561153927262068997135688096479833275438059003000577156030985752302737572142995389102392941277376055589936729467932043612276625158946842268530893693249010877756556663809256430403075836704397788157103267683082146557414910592210694688897583745853279150372366550265606245942901619641524394840947123797093291647952437507481770581519782926025000309975240809176732086412721877283182868239907386563436552684713604652833551208756316179487399401951895977814655415305700855625446129108900687384799001387951671104621436799720362491054813946856845126233235524710982837568591533011593761372364447069814628293634127437282262501219295880363659562599465416237996647317561877859528573985271179776400465798163016446475504146022123819119158936569549701762530276146646914630937941723419963811828693735274888334852800116766879328915880099767105948195091109555590581643322251908783026670007080972249010100892419108486345305849353679974424946961324819560021379840782224833262895740825258961195814695840112138347952831118547888120194142040782810626793593