Hone logo
Hone
Problems

Infinite Sequence Generator in Go

The generator pattern allows you to produce a sequence of values on demand, rather than storing the entire sequence in memory. This is particularly useful when dealing with potentially infinite sequences or very large datasets. This challenge asks you to implement a generator in Go that produces an infinite sequence of Fibonacci numbers.

Problem Description

You are tasked with creating a generator function in Go that yields Fibonacci numbers indefinitely. A Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, 8, ...). Your generator should produce these numbers one at a time, allowing the caller to consume them as needed.

Key Requirements:

  • Generator Function: Create a function that returns a channel of int64. This channel will be used to stream the Fibonacci numbers.
  • Infinite Sequence: The generator should produce Fibonacci numbers indefinitely (until the channel is closed by the caller).
  • Correct Sequence: The generated sequence must accurately represent the Fibonacci sequence.
  • Efficiency: The generator should be efficient in terms of memory usage, as it should not store the entire sequence.

Expected Behavior:

When the generator function is called, it should start producing Fibonacci numbers and sending them to the returned channel. The caller can then read from this channel to receive the numbers. The generator should continue producing numbers indefinitely.

Edge Cases to Consider:

  • The generator should handle the initial values (0 and 1) correctly.
  • The generator should avoid integer overflow as the Fibonacci numbers grow large. Using int64 helps mitigate this, but be mindful of potential overflow with very large numbers.

Examples

Example 1:

Input: (No direct input - the generator runs indefinitely)
Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... (and continues indefinitely)
Explanation: The generator produces the Fibonacci sequence starting from 0 and 1.

Example 2:

Input: (No direct input)
Output: (After consuming the first 10 numbers) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Explanation: The caller reads the first 10 numbers from the channel returned by the generator.

Example 3: (Edge Case - Handling large numbers)

Input: (No direct input)
Output: (Eventually, very large numbers will be generated) ... 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, ...
Explanation: The generator continues to produce Fibonacci numbers, even as they become very large.  The use of `int64` allows for a larger range of numbers before overflow.

Constraints

  • The generator function must return a channel of int64.
  • The generator must produce the Fibonacci sequence indefinitely (or until the channel is closed).
  • The Fibonacci sequence must start with 0 and 1.
  • The generator should be reasonably efficient in terms of memory usage. Avoid storing the entire sequence.
  • The generated numbers should fit within the int64 range as much as possible.

Notes

  • Consider using a goroutine to run the generator function, as it will be producing values indefinitely.
  • Channels are a key part of implementing the generator pattern in Go. Use them to communicate the generated values to the caller.
  • Think about how to handle potential integer overflow. While int64 provides a larger range than int, it's still possible to overflow with very large Fibonacci numbers. For this challenge, focus on producing the sequence correctly within the int64 range.
  • The caller is responsible for closing the channel when they are finished consuming the values.
Loading editor...
go