title: Parse a variable star designation

text:
# Question
Title: Parse a variable star designation
The **variable star designation** is an identifier for a variable star (a star that fluctuates in brightness). It consists of either a 1-2 letter code or (when the letter code is no longer sufficient) a 'V' followed by a number. This code is followed by the genitive of the star constellation the star is found in (eg. "RR Coronae Borealis", in short "RR CrB"), and each constellation has their own independent numbering.

The series of variable star designations inside one constellation is as follows:

1. start with the letter `R` and continue alphabetically through `Z`.
2. Continue with `RR`...`RZ`, then use `SS`...`SZ`, `TT`...`TZ` and so on until `ZZ`.
3. Use `AA`...`AZ`, `BB`...`BZ`, `CC`...`CZ` and so on until reaching `QZ`, always omitting `J` in both the first and second positions.
4. After `QZ` (the 334th designation) abandon the Latin script and start naming stars with `V335`, `V336`, and so on (`V` followed by the full numeric index).

Note: The second letter is never alphabetically before the first, ie. `BA` for example is an invalid designation. Single letters before `R` are unused. `J` never appears in the designation.

## Your Task

Parse a variable star designation and return its index in the series of variable star designations!

The input is a string of just the variable star designation (omitting the constellation reference that is usually included in a full variable star designation). It can be assumed to be a valid variable star designation; validation is not part of this challenge.

Output is a number representing at what index in the series the designation is. The index is 1-based.

Test cases:

* `QV` =\> `330`
* `U` =\> `4`
* `V5000` =\> `5000`
* `AB` =\> `56`

This is , so the shortest code wins. Standard rules and loopholes apply.

# Answer
# Jelly,  ~~23 22~~  20 bytes

```
ØAḟ”JŒċṙ280Ḋ€ḣ9;ƲiȯḊ

```

A full program which prints the index.

**Try it online!**

### How?

```
ØAḟ”JŒċṙ280Ḋ€ḣ9;ƲiȯḊ - Main Link: list of characters, V
ØA                   - upper-case alphabet characters
   ”J                - character 'J'
  ḟ                  - filter discard
     Œċ              - combinations with repetition = ["AA","AB",...,"AZ","BB",...]
       ṙ280          - rotate left by 280 = ["RR","RS",...,"RZ","SS",..."]
                Ʋ    - last four links as a monad:
           Ḋ€        -   dequeue each = ["R","S",...,"Z","S",...]
             ḣ9      -   head to index 9 = ["R","S",...,"Z"]
               ;     -   concatenate these together = ["R","S",...,"Z","RR","RS",...]
                 i   - first index of V in that (or 0 if not found)
                   Ḋ - dequeue V (i.e. "V5000" -> "5000")
                  ȯ  - logical OR
                     - implicit print

```
> 1 votes

# Answer
# Python 3, 121 bytes

```
lambda z,a='ABCDEFGHIKLMNOPQ',r='RSTUVWXYZ':int(z[1:])if z[2:]else[t+u for t in['',*r+a]for u in a+r if t<=u].index(z)-15

```

Try it online!

## Explanation

The list comprehension `[t+u for t in['',*r+a]for u in a+r if t<=u]` evaluates to these strings:

```
t='':   A  B  C  D  E  F  G  H  I  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
t='R':                                                 RR RS RT RU RV RW RX RY RZ
t='S':                                                    SS ST SU SV SW SX SY SZ
t='T':                                                       TT TU TV TW TX TY SZ
t='U':                                                          UU UV UW UX UY SZ
t='V':                                                             VV VW VX VY VZ
t='W':                                                                WW WX WY WZ
t='X':                                                                   XX XY XZ
t='Y':                                                                      YY YZ
t='Z':                                                                         ZZ
t='A': AA AB AC AD AE AF AG AH AI AK AL AM AN AO AP AQ AR AS AT AU AV AW AX AY AZ
t='B':    BB BC BD BE BF BG BH BI BK BL BM BN BO BP BQ BR BS BT BU BV BW BX BY BZ
...
...
...
t='Q':                                              QQ QR QS QT QU QV QW QX QY QZ

```

If there are any characters past the first two (`z[2:]`) then the result is `int(z[1:])`. Otherwise (i.e. if there are only one or two characters) we look the string up in the list we created and subtract 15 from the index.
> 8 votes

# Answer
# JavaScript (ES6),  ~~104 100 98~~  92 bytes

```
s=>+s.slice(1)||(n=parseInt(s,36))-((v=n/36|0)?250-v*~v/2+(n%36>18)+(v>18?v>26?360:35:v):26)

```

Try it online!

### How?

We first test whether removing the first character of the input string leads to a numeric value. If it does, we just return that. For instance, `V5000` gives \\$5000\\$.

Otherwise, we convert the whole string from base-36 to decimal and store the result in \\$n\\$.

The index \\$i\_n\\$ of the star is always less than \\$n\\$. What we want to do is find out the difference \\$d\_n\\$ such that:

$$i\_n=n-d\_n$$

Let \\$v\_n\\$ be the higher base-36 digit:

$$v\_n=\left\lfloor\frac{n}{36}\right\rfloor$$

If \\$v\_n=0\\$, it means that this is a single letter designation and we just need to subtract \\$d\_n=26\\$ from \\$n\\$ to get the correct index (`R=1`, `S=2`, etc.).

Otherwise, we compute:

$$d\_n=250+t\_n+k\_n+o\_n$$

\\$t\_n\\$ is the term reflecting the fact the designation is triangular (`ZZ`, `YY YZ`, `XX XY XZ`, etc.):

$$t\_n={v\_n+1 \choose 2}=\frac{v\_n\cdot(v\_n+1)}{2}$$

\\$k\_n\\$ is the correction term for the missing `J` for the second letter:

$$k\_n=\cases{0,&\text{$n\bmod36\le18$}\\ 1,&\text{$n\bmod36\>18$} }$$

Finally, \\$o\_n\\$ acts both as a correction term for the missing `J` for the first letter and as an offset for the 'wrapping' nature of the designation which goes first from `RR` to `ZZ` and then from `AA` to `QZ`:

$$o\_n=\cases{v\_n,&\text{$v\_n\le18$}\\ 35,&\text{$18\<v\_n\le26$}\\ 360,&\text{$v\_n\>26$} }$$
> 6 votes

# Answer
# Charcoal, 41 bytes

```
≔…R¦[η≔Φα⁻κ⁹ζＦ﹪⁻Ｅζκ⁹ＬζＦ✂ζι⊞η⁺§ζικＩ∨⊕⌕ηθΣθ

```

Try it online! Link is to verbose version of code. Explanation:

```
≔…R¦[η

```

Start building up a list of designations with the single letters `R` to `Z`.

```
≔Φα⁻κ⁹ζ

```

Get the alphabet without the letter `J`.

```
Ｆ﹪⁻Ｅζκ⁹Ｌζ

```

Loop over each possible first letter, but offset the value so it starts at the index of `R`, wraps around, and stops at the index of `Q`.

```
Ｆ✂ζι

```

Loop over each possible second letter.

```
⊞η⁺§ζικ

```

Push the letter pair to the list of designations.

```
Ｉ∨⊕⌕ηθΣθ

```

Output the index in the list, or if not found, the embedded number.
> 2 votes

# Answer
# Pyth, ~~35~~ 34 bytes

```
|hx-I#\J+Kr\R\[smr+dd+d\[+Kr\A\RQt

```

Try it online!

Uses string ranges to build a list of star designations, then finds the index of the input in that list.

**Explanation**

* `r\R\[` is the range from `R` to `[` (half-open range, so the range ends at `Z`) and `r\A\R` is the range from `A` to `R`
* `mr+dd+d\[` maps each character \\$d\\$ of a given list to the range from \\$dd\\$ to \\$d\\$`[`

(eg. "S" would map to the range "SS" to "S\[")

* Hence, `+Kr\R\[smr+dd+d\[+Kr\A\R` builds the following list:

```
['R',...'Z', 'RR',...'RZ', 'SS',...'SZ', 'TT',...'TZ',... 'ZZ', 'AA',... 'AZ', 'BB',... 'BZ',...'QZ']

```
* `-I#\J` filters out items that contain a `J`
* `x ... Q` gives the index of the input in that list. If the input is not in the list, -1 is returned.

+ `h` increments that result (so if the input was not in the list, we now have 0)
* `| ... t(Q)` catches the `Vxx` case. If the previous expression evaluated to 0 (meaning the input was not in the constructed list), this returns the "tail" of the input (ie. the number after the `V`)
> 2 votes

# Answer
# C (gcc),  ~~92 89~~  87 bytes

*Saved 2 bytes thanks to @ceilingcat*

Very similar to my JS answer, but without the constraint of working in base 36.

```
v;f(char*s){v=*s++-81;s=*s?s[1]?atoi(s):v*10+254+*s+v*~v/2-*s/74-(v>-8?v>0?334:9:v):v;}

```

Try it online!
> 1 votes

---
Tags: code-golf, parsing, astronomy
---


title: An infinite FTW

text:
# Question
Title: An infinite FTW
The infinite Fibonacci word is a specific, infinite sequence of binary digits, which are calculated by repeated concatenation of finite binary words.

Let us define that a *Fibonacci-type word sequence* (or *FTW sequence*) is any sequence **⟨Wn** that is formed as follows.

* Commence with two arbitrary arrays of binary digits. Let us call these arrays **W-1** and **W0**.
* For each **n \> 0**, let **Wn ≔ Wn-1 ∥ Wn-2**, where  denotes concatenation.

A consequence of the recursive definition is that **Wn** is always a prefix of **Wn+1** and, therefore, of all **Wk** such that **k \> n**. In a sense, this means the sequence **⟨Wn** converges to an infinite word.

Formally, let **W** be the only infinite array such that **Wn** is a prefix of **W** for all **n ≥ 0**.

We'll call any infinite word formed by the above process an *infinite FTW*.

### Task

Write a program or function that accepts two binary words **W-1** and **W0** as input and prints **W**, abiding by the following, additional, rules:

* You may accept the words in any order; as two arrays, an array of arrays, two strings, an array of strings, or a single string with a delimiter of your choice.
* You may print the digits of the infinite word either without a delimiter or with a consistent delimiter between each pair of adjacent digits.
* For all purposes, assume that your code will never run out of memory, and that its data types do not overflow.

In particular, this means that any output to STDOUT or STDERR that is the result of a crash will be ignored.
* If I run your code on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21) for one minute and pipe its output to `wc -c`, it must print at least one million digits of **W** for **(W-1, W0) = (1, 0)**.
* Standard rules apply.

### Example

Let **W-1 = 1** and **W0 = 0**.

Then **W1 = 01**, **W2 = 010**, **W3 = 01001**, **W4 = 01001010** … and **W = 010010100100101001010…**.

This is *the* infinite Fibonacci word.

### Test cases

All test cases contain the first 1,000 digits of the infinite FTW.

```
Input:  1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011

Input:  10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010

Input:  101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101

```

# Answer
# Pyth, 8 bytes

```
u,peGsGQ

```

Input in the form `"W-1", "W0"`.

Proof of completion:

```
$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

```

---

Proof of correctness:

Here is the series as internally generated. It is printed in concatenation by the program.

```
[0, 10, 010, 10010, 01010010, 1001001010010,...]

```

Compare to the following, printed in concatenation, which is simply the string added to the previous string on each step:

```
[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

```

We want to prove these are equivalent.

Clearly, they are the same through the first few steps. Let's compare them after a bit:

```
010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

```

We see that the pairs of strings are alternately of the forms:

```
01a 10b
a10 b01

```

Where a and b are arbitrary sequences on 0s and 1s. Let's continue the sequence for a bit, to prove is continues forever by induction:

```
01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

```

2 steps later, it is of the correct form.

```
10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

```

2 steps later, it is of the correct form.

So by induction, the strings always match once concatenated.
> 13 votes

# Answer
## Haskell, 15 bytes

```
v%w=w++w%(v++w)

```

The infix function `%` produces an infinite string, which Haskell prints forever because Haskell is cool like that.

```
>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

```

The recursive idea is similar to Zgarb's solution. Writing `f` for the function `%`, and `+` for string concatenation, it implements:

```
f(v,w) = w + f(w,v+w)

```

The infinite output string starts with `w`, and the remainder of it is the result for the Fibonacci-shifted strings `w` and `v+w`.

This has no problem generating a million characters in a minute.
> 17 votes

# Answer
## Haskell, 31 bytes

```
w#v=v++drop(length v)(v#(v++w))

```

This defines an infix function `#` that takes two strings and returns an infinite string. Usage:

```
> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

```

If I query the millionth element of the sequence defined by "1" and "0", even the online interpreter prints the result in less than a second:

```
> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

```

## Explanation

```
w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

```

Basically, we know that `w#v == v#(v++w)` and `w#v` begins with `v`, and use these facts to define the result. Since Haskell is lazy, this "magically" just works.
> 8 votes

# Answer
## CJam, ~~12~~ 11 bytes

```
llL{@_o+_}h

```

This takes the two words on separate lines, in the opposite order, e.g.

```
0
1

```

gives

```
0100101001001010010100100101001...

```

### Explanation

The idea is to build up the word naively (by remembering the current word and appending the previous one to it) and while we're doing that, we print whatever we just appended (in order not to repeat the prefix that was already printed). To avoid having to handle the starting point separately, we start from an empty word, such that W0 is the first thing we append (and print).

```
ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.
}h

```
> 4 votes

# Answer
# APL, ~~24~~ 18

```
{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞

```

Using xnor's formulation allowed to shave off few characters.

```
                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

```

On an infinite machine in infinite time it would actually print W thrice—first incrementally while running the loop, and then twice as a result of the whole expression when the `⍣≡` fixpoint operator finally returns.

It's not very fast but fast enough. In GNU APL:

```
$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010$
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system

```
> 4 votes

# Answer
# Pip, 8 bytes

Hey, tied with Pyth!

```
(fOba.b)

```

Straightforward recursive definition borrowed from xnor's Haskell answer. With spaces added for clarity:

```
(f Ob a.b)

```

Every program in Pip is an implicit function that takes the command-line args as its arguments (assigned to variables `a` through `e`) and prints its return value. `O` is an operator that outputs and then returns its operand, so the first thing that happens here is the second argument is displayed (sans trailing newline).

Now, the Lisp-inspired syntax `(f x y)` in Pip is a function call, equivalent to `f(x,y)` in C-like languages. The `f` variable refers to the current function--in this case, the top-level program. Thus, the program recursively calls itself with `b` and `a.b` as the new arguments.

I was pleasantly surprised to find that this approach is plenty fast:

```
dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

```

It takes about 30 seconds on my Ubuntu machine for the program to hit the max recursion depth, at which point it has printed out somewhere over a billion digits.

This iterative solution is slightly faster and hogs less memory, at the cost of one byte:

```
W1Sba.:Ob

```
> 4 votes

# Answer
## PowerShell, ~~97~~ 76 Bytes

```
param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

```

Edit - Umm, writing out `$e.substring($b.length)` after we just concatenated `$a` and `$b` together is equivalent to writing out just `$a` ... derp.

Wow, verbose. PowerShell will, by default, spit out a newline every time you output something. Really the only way to get around that is with `write-host -n` (short for `-NoNewLine`), and that absolutely kills the length here.

Essentially, this iterates through the sequence, building `$e` as the "current" Wn as we go. However, since we're wanting to build the infinite word instead of the sequence, we leverage our previous variables to print out the suffix `$a` that was populated in our previous loop. Then we setup our variables for the next go-round and repeat the loop. Do note that this expects the input to be explicitly delimited as strings, else the `+` operator gets used for arithmetic instead of concatenation.

### Example:

```
PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...

```
> 3 votes

# Answer
# Pure bash, 58

```
a=$1
b=$2
printf $b
for((;;)){
printf $a
t=$b
b+=$a
a=$t
}

```

I run out of memory before 1 minute, but have plenty of digits by then - after 10 seconds I have 100 million digits:

```
$ ./ftw.sh 1 0 | head -c100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010ubuntu@ubuntu:~$
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c
102334155
$

```
> 3 votes

# Answer
# C, 76 (gcc)

```
main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

```

This is a fairly straightforward recursive printer, implemented as a nested function (a GNU C extension not supported by clang) to avoid having to pass `v` around. `p(n)` prints **Wn-2**, where **W-1** and **W0** must be provided in `v[1]` and `v[2]`. This initially calls `p(4)` to print **W2**. It then loops: it calls `p(3)` to print **W1**, making the complete output **W2W1**, which is **W3**. It then calls `p(4)` to print **W2**, making the complete output **W4**, etc. Performance is slightly better than my earlier answer: I'm seeing 1875034112 values in a minute.

---

# C, 81 (clang)

This is a completely different approach from the above that I feel is worth keeping up, even though it scores worse.

```
s[],*p=s;main(c,v)char**v;{for(++v;;)for(puts(v[*++p=*++p!=1]);*p+1==*--p;++*p);}

```

This has all kinds of undefined behaviour, mainly for fun. It works with clang 3.6.2 on Linux and with clang 3.5.2 on Cygwin for the test cases in the question, with or without special command-line options. It doesn't break when optimisations are enabled.

It doesn't work with other compilers.

> You may accept the words in any order; as two arrays, an array of arrays, two strings, an array of strings, or a single string with a delimiter of your choice.

I accept the words as command-line arguments in string format.

> You may print the digits of the infinite word either without a delimiter or with a consistent delimiter between each pair of adjacent digits.

I use newline as the consistent delimiter.

> For all purposes, assume that your code will never run out of memory, and that its data types do not overflow.
>
> In particular, this means that any output to STDOUT or STDERR that is the result of a crash will be ignored.

I access `s` out of bounds. This must surely end with a segfault or an access violation at some point. `s` happens to get placed at the end of the data segment, so it shouldn't clobber other variables and give wrong output before that segfault. Hopefully.

> If I run your code on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21) for one minute and pipe its output to `wc -c`, it must print at least one million digits of **W** for **(W-1, W0) = (1, 0)**.

Testing using `{ ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c`, I get 1816784896 digits in one minute on my machine when the program was compiled with `-O3`, and 1596678144 when it was compiled with optimisations diabled.

---

Ungolfed, no UB, with explanation:

```
#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    puts(argv[word]);
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
      --ptr;
      ++ptr[-1];
    }
  }
}

```
> 2 votes

# Answer
# Mathematica, 56 bytes

```
$IterationLimit=∞;#0[$Output~WriteString~#2;#2,#<>#2]&

```
> 2 votes

# Answer
# Dyalog APL, 9

```
{⍵∇⍺,⍞←⍵}

```

This one uses  to define a recursive function. It's a direct translation of this xnor's Python 3 answer. It takes W0 as right, and W−1 as its left argument, both should be character vectors.
> 2 votes

# Answer
## Python 2, 67 bytes

```
a,b=input()
print'\n'.join(b+a)
while 1:a,b=b,b+a;print'\n'.join(a)

```

Accepts input as a comma-separated pair of strings: `"1","0"`, for the example in the question.

No online interpreter because infinite loops are bad. ~~Buffered output made me gain a lot of bytes. :(~~ Thanks Dennis for pointing out that 1 digit per line is valid.

Timing on my (significantly-weaker) machine:

```
$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s

```
> 1 votes

# Answer
## Perl 5, ~~45~~ ~~55~~ 49 bytes

44 bytes, plus 1 for `-E` instead of `-e`

```
sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}

```

Use as e.g.

```
perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

```

This prints successive approximations to W and thus, if you wait long enough, prints, on its last line of output, W to any desired length, as required. The digits of the word are concatenated without a delimiter.

Since I'm on Windows, I tested it for the "at least one million digits of W" requirement by running it with output redirected to a file and killing it after about 59 seconds, then running GnuWin32's `wc -L`, which printed 701408733.

---

## Update:

The OP clarified in a comment on this answer (and probably I should have realized anyway) that the extra output preceding W disqualifies the above. So instead here's a 55-byte solution that prints *only* W:

```
sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}

```

Used the same way, but *with the arguments in reverse order*, and doesn't require `-E`:

```
perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

```

Doubtless it can be golfed further, but I don't see how to do so right now.

---

## Further update:

Dennis shaved five bytes by using `-a` (thus reading `<>` to remove `sub`) and reassigning the parameter passed to `print` at the end of the `redo` block:

With `-ane` and reading from `<>` (both inputs on one line, space-separated, in reverse order); 48 + 2 bytes:

```
$_=$F[0];{print;unshift@F,$F[0].($_=$F[1]);redo}

```

And, based on that, I shaved one more byte (same as above, but now the inputs are in the correct order); 47+2 bytes:

```
$_=$F[1];{print;push@F,$F[-1].($_=$F[-2]);redo}

```
> 1 votes

# Answer
# Javascript (53 bytes)

```
(a,c)=>{for(;;process.stdout.write(a))b=a,a=c,c=b+a;}

```

Input should be string and not number (`'0'` and not just `0`).
> 1 votes

# Answer
## Python 3, 32

```
def f(a,b):print(end=b);f(b,a+b)

```

The same recursive idea as my Haskell answer, except the prefix is printed because Python can't handle infinite strings.

Used a trick from Sp3000 to print without spaces by putting the string as the `end` argument in Python 3
> 1 votes

# Answer
## REXX, 48

```
arg a b
do forever
b=a||b
say b
a=b||a
say a
end

```

*ftw.rex*
exec ftw.rex 0 1

Currently can't test performance because I used an online compiler to write it. The "forever" can be replaced with any number where as the printed ftw numbers are (number + 2).

I also wrote a small (messy) solution in Prolog. Didn't figure how to test performance with this one but its probably atrocious anyway.

```
f(A,B,C):-atom_concat(B,A,D),(C=D;f(B,D,C)).

:- C='0';C='1';(f(1,0,C)).

```
> 1 votes

# Answer
## Minkolang 0.11, 62 bytes

```
(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

```

Try it here. Expects input in the order **W0**, **W-1** with a space in between.

### Explanation

```
(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

```

Meta-explanation for the following is that at this point in time, we have two numbers followed by a string of "0"s and "1"s with no separation. If the lengths of **W0** and **W-1** are `a` and `b`, respectively, then the two numbers at the front of the stack are `<a+b>` and `<a>`, in that order. The word formed by concatenating **Wi+1** and **Wi**, i.e. **Wi+1** \+ **Wi**, is equal to 2 * **Wi+1** \- **Wi**. So the following code duplicates the stack (2 * **Wi+1**), pops off the top `<a>` elements (- **Wi**), and then replaces `<a+b>` and `<a>` with their successors, `<a+2b>` and `<b>`.

```
(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")

```
> 1 votes

# Answer
# Perl, 32 bytes

```
#!perl -pa
$#F=3}for(@F){push@F,$F[-1].$_

```

Counting the shebang as two, input is taken from stdin, space separated as *W0*, *W-1*. Output for 1MB times at ~15ms, most of which can be attributed to interpreter launch.

---

**Sample Usage**

```
$ echo 0 1 | perl inf-ftw.pl
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001...

$ echo 110 101 | perl inf-ftw.pl
1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101...

```
> 1 votes

# Answer
# Prolog, 69 bytes

```
q(A,B):-atom_concat(B,A,S),write(A),q(B,S).
p(A,B):-write(B),q(A,B).

```

**Example input:** p('1','0')
Haven't found a way to remove the extra write.
Should be able to improve on this if I figure out how to do that.
> 1 votes

# Answer
# , 22 bytes including 6 for input chars

similar to Dyalog APL solution

```
'1'((]stdout@])$:,)'0'

```

Try it online!
> 0 votes

---
Tags: code-golf, math, sequence, fibonacci
---