Iterare su una sequenza infinita in Ruby

Question

Sto cercando di risolvere il problema del progetto Euler n. 12:

La sequenza dei numeri del triangolo viene generata aggiungendo i numeri naturali. Quindi il 7 ° numero triangolare sarebbe 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. I primi dieci termini sarebbero:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Elenchiamo i fattori dei primi sette numeri del triangolo:

 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

Possiamo vedere che 28 è il primo numero di triangolo ad avere oltre cinque divisori. Qual è il valore del primo numero triangolare ad avere oltre cinquecento divisori?

Ecco la soluzione che mi è venuta in mente usando Ruby:

triangle_number = 1
(2..9_999_999_999_999_999).each do |i|
  triangle_number += i
  num_divisors = 2 # 1 and the number divide the number always so we don't iterate over the entire sequence
  (2..( i/2 + 1 )).each do |j|
    num_divisors += 1 if i % j == 0
  end
  if num_divisors == 500 then
    puts i
    break
  end
end

Non dovrei usare un numero enorme arbitrario come 9_999_999_999_999_999. Sarebbe meglio se avessimo una sequenza di matematica come alcuni linguaggi funzionali. Come posso generare una pigra sequenza infinita in Ruby?

Answer 1

In Ruby> = 1.9, puoi creare un oggetto enumeratore che produce qualunque sequenza ti piaccia. Eccone uno che produce una sequenza infinita di numeri interi:

#!/usr/bin/ruby1.9

sequence = Enumerator.new do |yielder|
  number = 0
  loop do
    number += 1
    yielder.yield number
  end
end

5.times do
  puts sequence.next
end

# => 1
# => 2
# => 3
# => 4
# => 5

O:

sequence.each do |i|
  puts i
  break if i >= 5
end

Programmazione Ruby 1.9 (aka "The Pickaxe Book"), 3 °. ed., p. 83, ha un esempio di enumeratore per numeri triangolari. Dovrebbe essere facile modificare l'enumeratore sopra per generare numeri triangolari. Lo farei qui, ma ciò riprodurrebbe l'esempio alla lettera, probabilmente più che "uso equo" lo consente.

Answer 2

Diverse risposte sono vicine, ma in realtà non vedo nessuno che usi gamme infinite. Ruby li supporta bene.

Inf = Float::INFINITY # Ruby 1.9
Inf = 1.0/0 # Ruby before 1.9
(1..Inf).include?(2305843009213693951)
# => true
(1..Inf).step(7).take(3).inject(&:+)
# => 24.0

Nel tuo caso

(2..Inf).find {|i| ((2..( i/2 + 1 )).select{|j| i % j == 0}.count+2)==42 }
=> 2880

Il tuo metodo di forza bruta è grezzo e, potenzialmente, impiegare molto tempo per finire.

Answer 3

L'infinito è definito su galleggiante (Ruby 1.9)

a = Float::INFINITY
puts a #=> Infinity
b = -a
puts a*b #=> -Infinity, just toying

1.upto(a) {|x| break if x >10; puts x}

Answer 4

Currrent Versioni dei generatori di supporto Ruby pesantemente:

sequence = 1.step

Answer 5

Questo sarebbe meglio come un semplice ciclo.

triangle_number = 1
i  = 1
while num_divisors < 500
  i += 1
  triangle_number += i
  # ...
end
puts i

Answer 6

Come ha detto Amadan, puoi usare le chiusure:

triangle = lambda { t = 0; n = 1; lambda{ t += n; n += 1; t } }[]
10.times { puts triangle[] }

Non pensare davvero che sia molto più lento di un ciclo. Puoi salvare anche lo stato in classe, ma avrai bisogno di più digitazione:

class Tri
  def initialize
    @t = 0
    @n = 1
  end

  def next
    @t += n
    @n += 1
    @t
  end
end

t = Tri.new
10.times{ puts t.next }

Aggiunto:

Per coloro a cui piacciono i longjmps:

require "generator"

tri =
  Generator.new do |g|
    t, n = 0, 1
    loop do
      t += n
      n += 1
      g.yield t
    end
  end

puts (0..19).map{ tri.next }.inspect

Answer 7

In Ruby 2.6 questo diventa molto più facile:

(1..).each {|n| ... }

Fonte: https://bugs.ruby-lang.org/issues/12912

Answer 8

Baselando sull'eccellente risposta di Wayne e nello spirito di Ruby di fare le cose con il minimo numero di personaggi qui è una versione leggermente aggiornata:

sequence = Enumerator.new { |yielder| 1.step { |num| yielder.yield num } }

Ovviamente, non risolve il problema originale di Euler ma è utile per generare una sequenza infinita di numeri interi. Funziona sicuramente per Ruby> 2.0. Divertiti!

Answer 9

Il giorno di Natale 2018, Ruby ha introdotto il gamma infinita, fornendo un nuovo approccio semplice a questo problema.

Questo è implementato per esempio il carattere finale dall'intervallo:

(1..)
(1...)
(10..)
(Time.now..)

O per aggiornare utilizzando la soluzione di Jonas Elfström:

(2..).find { |i| ((2..( i / 2 + 1 )).select { |j| i % j == 0 }.count + 2) == 42 }

Spero che questo si riveli utile per qualcuno!

Answer 10

Credo che le fibre (aggiunte in Ruby 1.9 credo) potrebbero essere vicine a ciò che vuoi. Vedere qui Per alcune informazioni o semplicemente cerca le fibre di Ruby