Skip to content

Instantly share code, notes, and snippets.

@nathanl
Created February 21, 2015 13:08
Show Gist options
  • Save nathanl/672b6315f28afb465fbb to your computer and use it in GitHub Desktop.
Save nathanl/672b6315f28afb465fbb to your computer and use it in GitHub Desktop.
How long it takes to solve the Traveling Salesman problem by brute force
def factorial(n)
(1..n).reduce(:*)
end
SECONDS_PER_STEP = 0.001
def total_seconds(n)
factorial(n) * SECONDS_PER_STEP
end
def seconds_to_years(seconds)
seconds / 60.0 / 60.0 / 24.0 / 365.0
end
puts "Factorial of 5 is #{factorial(5)} steps"
puts "If one step takes #{SECONDS_PER_STEP} seconds, #{factorial(5)} steps takes #{total_seconds(5)} seconds"
puts "Factorial of 22 is #{factorial(22)} steps"
puts "If one step takes #{SECONDS_PER_STEP} seconds, #{factorial(22)} steps takes #{total_seconds(22)} seconds"
puts "#{total_seconds(22)} seconds is #{seconds_to_years(total_seconds(22))} years"
@nathanl
Copy link
Author

nathanl commented Feb 23, 2015

Output:

Factorial of 5 is 120 steps
If one step takes 0.001 seconds, 120 steps takes 0.12 seconds
Factorial of 22 is 1124000727777607680000 steps
If one step takes 0.001 seconds, 1124000727777607680000 steps takes 1.1240007277776077e+18 seconds
1.1240007277776077e+18 seconds is 35641829267.42795 years

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment