Created
May 18, 2013 00:58
-
-
Save keelerm84/5602815 to your computer and use it in GitHub Desktop.
3n + 1 Recursive Solution in Ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
# Consider the following algorithm to generate a sequence of numbers. Start | |
# with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and | |
# add 1. Repeat this process with the new value of n, terminating when n = 1. | |
# For example, the following sequence of numbers will be generated for n = 22: | |
# | |
# 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 | |
# | |
# It is conjectured (but not yet proven) that this algorithm will terminate at | |
# n = 1 for every integer n. Still, the conjecture holds for all integers up to | |
# at least 1,000,000. | |
# | |
# For an input n, the cycle-length of n is the number of numbers generated up | |
# to and including the 1. In the example above, the cycle length of 22 is 16. | |
# Given any two numbers i and j, you are to determine the maximum cycle length | |
# over all numbers between i and j, including both endpoints. | |
# | |
# Assume your program will be called like ./code-challenge i j | |
# | |
# The output should be i j max-cycle-length | |
# | |
# For example, | |
# | |
# ./code-challenge 1 10 | |
# 1 10 20 | |
# | |
# Sample Inputs and Outputs | |
# 1 10 => 1 10 20 | |
# 100 200 .=> 100 200 125 | |
# 201 210 => 201 210 89 | |
# 900 1000 => 900 1000 174 | |
class Algorithm | |
@@cache = Hash.new | |
def process(starting, ending) | |
max = 0 | |
(starting..ending).each do |number| | |
result = process_number(number) | |
max = result if result > max | |
end | |
max | |
end | |
protected | |
def process_number(number) | |
return 1 if number == 1 | |
return @@cache[number] if @@cache.has_key?(number) | |
@@cache[number] = 1 + process_number(number % 2 == 0 ? number / 2 : 3 * number + 1) | |
end | |
end | |
algorithm = Algorithm.new | |
printf "%s %s %d\n", ARGV[0], ARGV[1], algorithm.process(ARGV[0].to_i, ARGV[1].to_i) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment