Category:Jq/fibonacci.jq

module {
  "name": "fibonacci",
  "description": "Fibonacci sequence and Fibonacci coding of positive integers",
  "version": "0.0.1",
  "homepage": "https://rosettacode.org/w/index.php?title=Category:Jq/fibonacci.jq",
  "license": "MIT",
  "author": "pkoppstein at gmail dot com",
};

# If $n is a non-negative integer, then
# fibonacci($n) generates the stream of integers F(0), F(1), F(2), ... F($n)
# where F(0) = 0, F(1) = F(2) = 1 and F(i) = F(i-1) + F(i-2) for i>1.
# Thus F(i) == [fibonacci($n)][i] if 0 <= i <= $n
def fibonacci($n):
  # input: [f(i-2), f(i-1), countdown]
  def fib: (.[0] + .[1]) as $sum
           | if .[2] == 0 then $sum
             else $sum, ([ .[1], $sum, .[2] - 1 ] | fib)
             end;
  [-1, 1, $n] | fib;

# Efficient Fibonacci-encoding as an array of 0s and 1s ending in [1,1].
# If n is a positive integer, then n|fibencode is the Fibonacci encoding of n as an array
# such that join("") yields the string representation of the encoding.
# E.g.      11 | fibencode | join("")  #=> "001011"
# Note that there is no check that n is a positive integer, and in particular that
#            0 | fibencode  #=> [1]
def fibencode:
  # `n|fibs` returns an array of Fibonacci numbers [1, 2, 3, ... m] where m <= n.
  def fibs:
    . as $n
    # input: [f(i-2), f(i-1)]
    | [1,1]
    | [recurse(select(.[1] < $n) | [.[1], add])
       | .[1] | select(. <= $n)];

  fibs as $fibs
  # Traverse $fibs from right to left to avoid calling reverse
  | [foreach range($fibs|length -1 ; -1; -1) as $ix ({n: .};
       $fibs[$ix] as $fib
       | if .n >= $fib then .n -= $fib | .out = 1
         else .out = 0
         end)
     | .out]
  | reverse + [1];


# Efficient Fibonacci-decoding of a Fibonacci-encoded number
# as produced by `fibencode`  or `fibencode | join("")`.
# Input: a Fibonacci-encoded number as a 0-1 string ending in "11", or
# as the corresponding 0-1 array.
# So "11" | fibdecode #=> 1
def fibdecode:
  if type == "string" then explode | map(. - 48) else . end
  | length as $n
  | . as $x
  | reduce fibonacci($n) as $F ({i:-2, ans:0};
      if .i < 0 then . else .ans += $F * $x[.i] end
      | .i += 1)
  | .ans ;