1
\$\begingroup\$

I've some questions for an exam and wondered if somebody could take a look at my Fibonacci sequence that is supposed to answer this question:

"select the element out of the array if its index is a Fibonacci number"


def fibonacci_sequence(max_num)
  sequence = [1, 2]
  loop do
    fibonacci = sequence[-2] + sequence[-1]
    break if fibonacci >= max_num
    sequence << fibonacci
  end
  sequence
end

# array size
max_num = 100
numbers = []
1.upto(max_num) { |num| numbers << num }
fibonacci = fibonacci_sequence(max_num)

# select fibonacci numbers and assign array to variable
fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }

My thoughts were that I had to work out what the Fibonacci sequence was before I could select numbers out of the array that were Fibonacci. The thing is I already answer the question by assigning these numbers to the Fibonacci variable. I've then used a select method on the original numbers array even though I already know what the output is going to be.

Have I gone about this the right way? I'm thinking no!

\$\endgroup\$

closed as off-topic by nhgrif, 23fc9a62-56de-47fb-97b4-737890, Quill, holroy, SuperBiasedMan Feb 29 '16 at 0:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – nhgrif, 23fc9a62-56de-47fb-97b4-737890, Quill, holroy, SuperBiasedMan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ if its index is a Fibonacci number you are checking if the number itself is a fibonacci number. \$\endgroup\$ – Caridorc Feb 28 '16 at 21:18
  • \$\begingroup\$ Whoops. Let me rethink this one. \$\endgroup\$ – Joe Ainsworth Feb 28 '16 at 22:10
  • \$\begingroup\$ Based on the comments, it appears this code is not working as intended and the question should be deleted or put on hold. \$\endgroup\$ – nhgrif Feb 28 '16 at 22:42
  • \$\begingroup\$ @JoeAinsworth: numbers.select.with_index { |num, idx| fibonacci.include?(idx) } \$\endgroup\$ – tokland Feb 28 '16 at 22:46
  • \$\begingroup\$ @JoeAinsworth, it's a pity you let this die, it was an interesting question. \$\endgroup\$ – tokland Mar 4 '16 at 9:12
2
\$\begingroup\$

Some notes:

  • fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }. Array#include? is O(n), this will be very slow. With this approach, fibonacci should be a set.

  • Since you have to store a the fibonacci values, the space complexity won't be nice for big inputs.

  • Your algorithm only works for arrays, it would be nice if it worked with enumerables.

I'd write:

def remove_fib_indexes(xs)
  Enumerator.new do |yielder|
    fib_a, fib_b = [0, 1]
    xs.each.with_index do |x, idx|
      if idx == fib_a
        # skip the repeated 1 in the sequence [0, 1, 1, 2, 3, 5, ...]
        fib_a, fib_b = (fib_b == 1) ? [1, 2] : [fib_b, fib_a + fib_b] 
      else
        yielder.yield(x)
      end
    end
  end
end

xs = (0..Float::INFINITY).lazy.map(&:to_s)    
remove_fib_indexes(xs).take(10).to_a
#=> ["4", "6", "7", "9", "10", "11", "12", "14", "15", "16"]
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.