Problem 14

hosiawak · March 20, 2009, 9:10am

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.

teamon · March 20, 2009, 3:01pm

[code=ruby]class EndOfSequence < ArgumentError; end

class Fixnum
def collatz_next
raise EndOfSequence if self == 1
self.even? ? self/2 : 3*self+1
end

def collatz_sequence_size
c = [self]
loop do
c.push c.last.collatz_next
end
rescue EndOfSequence
c.size
end

def even?
self % 2 == 0
end
end

p (2…1_000_000).map { |n| [n, n.collatz_sequence_size] }.max {|a,b| a.last <=> b.last}[/code]
Jeszcze mieli ;p

hosiawak · March 20, 2009, 3:06pm

“Each problem has been designed according to a “one-minute rule”, which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.”

oraz tłumaczenie na miarę 21 wieku

“Każdy problem został zaprojektowany zgodnie z “zasadą jednej minuty”, co oznacza, że chociaż to może potrwać kilka godzin projektowania pomyślnego algorytm z trudniejszych problemów, sprawnego wykonania pozwoli na rozwiązanie, które mają być uzyskane na skromnie powered komputer w mniej niż jedna minuta.”

teamon · March 20, 2009, 3:15pm

Musze spylac ale jak by ktos chcial - wrzucic w rekurencje i memoize ;]

teamon · March 20, 2009, 7:15pm

Wersja z memoize

[code=ruby]require “rubygems”
require “memoize”
include Memoize

class Integer
def collatz_next
return 0 if self == 1
self.even? ? self/2 : 3*self+1
end

def even?
self % 2 == 0
end
end

def sequence_size(n)
c = n.collatz_next
if c == 0
1
else
sequence_size© + 1
end
end

memoize :sequence_size

p (2…1_000_000).map { |n| [n, sequence_size(n)] }.max {|a,b| a.last <=> b.last}

[teamon ~] time ruby d.rb
[837799, 525]

real 0m24.266s
user 0m23.380s
sys 0m0.431s[/code]

luckboy · March 22, 2009, 9:04pm

Ten problem da się rozwiązać w mniej nisz jedną sekundę wykorzystując C++ :lol:.
Wiem piszemy w ruby.

Anonymous · March 22, 2009, 9:23pm

Ruby to język skryptowy, więc nie będzie tak wydajny jak C++. Jednak można to odpalić w czasie < 4 sek (virtualbox ubuntu na vista e6300@3.4 6gb ram). Więc nie jest źle.

[code=terminal]projecteuler: Problem 14

  user     system      total        real

3.710000 0.340000 4.050000 ( 4.229409)

Q:Which starting number, under one million, produces the longest chain?
A: 837799[/code]
bez VB jest chyba szybciej ale nie mam obecnie dostępu

ps. to nie mój skrypt odpaliłem, mój wykonywał się dłużej.

skrypt znajduje się tu:

http://blog.thequeue.net/euler-14-f-c-ruby-and-a-geriatric-gerbil/

luckboy · March 22, 2009, 9:32pm

Iteresujace że w rubym tez da sie do szybko zrobic jeśli ma się odpowiedni sprzęd .
Jaki procesor i jaka częstliwość w tym virtualbox?

Anonymous · March 22, 2009, 9:35pm

processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 15 model name : Intel(R) Core(TM)2 CPU 6300 @ 1.86GHz stepping : 6 cpu MHz : 1865.548 cache size : 2048 KB fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 2 wp : yes flags : fpu vme de pse tsc msr mce cx8 apic mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 constant_tsc up pni monitor bogomips : 3731.09 clflush size : 64 power management:
ram: 512 MB

ps. gdzie się podziało moje OC?
ps2. ruby 1.9.1 p0

luckboy · March 22, 2009, 9:39pm

Po za tym chciałem sprawdzić jak te problemy rozwiązuje się C++ i porównać z rozwiązaniami w ruby.

Anonymous · March 22, 2009, 9:40pm

ja też właśnie przegrzebuje net z rozwiązaniami względem wydajności takich skryptów

dla przykładu skrypt teamona z memoize na VB:

real 0m51.109s user 0m49.407s sys 0m0.932s

luckboy · March 22, 2009, 10:21pm

Jaka wersja skryptu teamona? Czy jest to wersja z memoize?

Anonymous · March 22, 2009, 10:24pm

tak,
i tak >2 razy szybciej niz na samym Windowsie

radarek · March 23, 2009, 12:54am

[quote=luckboy]Ten problem da się rozwiązać w mniej nisz jedną sekundę wykorzystując C++ :lol:.
Wiem piszemy w ruby.[/quote]
Daj mi troszkę szybszy procek i ruby też wyciągnie…

Oto moje 2 rozwiązanie: pierwsze szybsze (brzydsze), drugie wolniejsze, ale za to jakie…

cache = Array.new(1_000_000) cache[0] = cache[1] = 1 max_len = 1 max_i = 1 len = 0 stack = [] 1_000_000.times do |i| next if cache[i] while cache[i].nil? stack.push(i) i = i % 2 == 0 ? (i >> 1) : (3 * i + 1) end len = cache[i] while i = stack.pop len += 1 cache[i] = len if i < 1_000_000 if (len > max_len && i < 1_000_000) max_len = len max_i = i end end end

[quote]$ ruby1.9.1 014_2.rb
1.520000 0.000000 1.520000 ( 1.526740)
1.460000 0.010000 1.470000 ( 1.477437)
1.470000 0.000000 1.470000 ( 1.472472)
1.460000 0.000000 1.460000 ( 1.473524)
1.460000 0.010000 1.470000 ( 1.472257)[/quote]

cache = Hash.new {|h, k| h[k] = 1 + (k.even? ? h[k >> 1] : h[3 * k + 1]) } cache[1] = 1 puts (2...1_000_000).to_a.max_by {|e| cache[e] }

[quote]$ ruby1.9.1 014_1.rb
3.770000 0.090000 3.860000 ( 3.865477)
4.710000 0.060000 4.770000 ( 4.765707)
4.660000 0.030000 4.690000 ( 4.679302)
4.530000 0.020000 4.550000 ( 4.552189)
4.510000 0.040000 4.550000 ( 4.545524)[/quote]

hosiawak · March 23, 2009, 12:57am

W Ruby można to policzyć szybciej dodając cache i sprawdzając tylko liczby nieparzyste (liczba musi być nieparzysta aby wywołać sekwencję, inaczej jest tylko n/2 aż do 1):

[code=ruby]$cache = { }

def collatz(n)
if f = $cache[n]
return f
end
i = 1
while n > 1
if f = $cache[n]
return $cache[n] + i
end
i += 1
n%2==0 ? n /= 2 : n = 3*n+1
end
i
end

i = 0
max = 0

(1…999_999).step(2) do |x|
j = collatz(x)
max, i = x, j if j > i
$cache[x] = j
end

p max[/code]
Wynik na moim (wolnym) sprzęcie:

ruby 1.8.6 - 12 sek
ruby 1.9 - 6 sek

Nie mogę porównać czasu wersji teamon’a bo memoize-1.2.3 wysypuje się zarówno na 1.8.6 (stack level too deep) jak i 1.9 (implicit argument passing of super from method defined by define_method() is not supported) przynajmniej u mnie.

radarek · March 23, 2009, 1:01am

Nie do końca, tak będzie tylko dla potęgi 2.

14/2 = 7 i pójdzie już inną ścieżką.

hosiawak · March 23, 2009, 1:12am

Fakt, który o dziwo można łatwo przeoczyć o 1 w nocy (zyskałem i tak tylko marną 1 sekundę), Twoje rozw. 2 jest krótko mówiąc imponujące i w dodatku o 1 sek, szybsze od mojego rozw. 1 wysypuje się na moim ruby 1.9.1 (2008-12-30 patchlevel-0 revision 21203) bignum too big to convert into `long’ (RangeError) - konieczny update

kiwi · March 23, 2009, 7:41am

[code=ruby]$t = Array.new(1_000_000)
$t[1],$t[2] = 0,1
def collantz(n)
if n>1000000
return n.even? ? collantz(n/2)+1 : collantz(3n+1)+1
end
if $t[n] != nil
elsif n.even?
$t[n] = collantz(n/2)+1
else
$t[n] = collantz(3n+1)+1
end
return $t[n]
end

for a in 3…1_000_000
$t[a] = collantz(a)
end

$t.collect! {|b| b.nil? ? 0 : b }

p $t.index($t.max)[/code]
Niespodziewałem się, że ruby1.9 jest tak szybki.

Mógłby ktoś zbenchmarkować to na szybkim sprzęcie? U mnie na celeronie 2.4Ghz jest 4.42s

Anonymous · March 23, 2009, 9:56am

co do pierwszego skryptu Radarka

cache = Array.new(1_000_000)

a następnie:

while cache[i].nil? stack << i i = i % 2 == 0 ? (i >> 1) : (3 * i + 1) print "cache[#{i}].nil? \n" end
w efekcie daje:

"cache[1654740 898].nil? " "cache[827370449].nil? " "cache[2482111348].nil? " 14rad.rb:24:in `[]': bignum too big to convert into `long' (RangeError) from 14rad.rb:24:in `block in <main>' from 14rad.rb:19:in `times' from 14rad.rb:19:in `<main>'
samo uruchomienie:

[code=terminal]irb(main):003:0> p cache[2482111348].nil?

RangeError: bignum too big to convert into `long’ (RangeError)[/code]
Do tej pory myślałem, że wskaźnik tablicy da sie zrobić z 11 cyfrowej liczby, ale nigdy nie miałem z tym doczynienia.

Efekt dostaje ten sam w 1.8.6 i 1.9.1 p0 niezależnie od systemu. To jest jakiś bug?

ps. Kiwi wypas, na moim VB:

[code=terminal]wojak@wojak-desktop:~/Pulpit/railsapps$ time ruby 14kiwi.rb
837799

real 0m2.797s
user 0m2.644s
sys 0m0.072s[/code]

timmy · November 6, 2009, 9:56am

Przy wykorzystaniu tablicy i korzystaniu z danych historycznych obliczenia zajęły mi około 15 sekund.

[code=Ruby]a = [0, 1]
(2…999999).each {|n|
i = 0
s = n
while n >= s
i += 1
if n % 2 == 0
n = n / 2
else
n = 3 * n + 1
end
end
a[s] = a[n] + i
}
l = a.sort.last
p “element=#{a.index(l)}, długość=#{l}”

=> element=837799, długość=525[/code]