title: Draw diagonal positions of me squared

text:
# Question
Title: Draw diagonal positions of me squared
Based on the interpretation user @ThePirateBay made from the **first version** of my own challenge

### Output diagonal positions of me squared

now I challenge you to make ASCII art that draws diagonal lines based on a square character matrix based on a given number `n`.

# Input

A number n.

# Output

A square matrix of size `n^2` which outputs diagonals represented by the adequate one of the `\ X /`chars. All other positions are to be fulfilled with `#` chars.

# Examples:

```
1
X

2
\/
/\

3
\#/
#X#
/#\

4
\##/
#\/#
#/\#
/##\

5
\###/
#\#/#
##X##
#/#\#
/###\

```

There will be no accepted answer. I want to know the shortest code for each language.

# Answer
# Jelly, 14 bytes

```
⁼þµḤ+Ṛị“/\X#”Y

```

A monadic link taking a number and returning a list of characters; or a full program printing the result.

**Try it online!** or see \[1-12\] in one go.

### How?

```
⁼þµḤ+Ṛị“/\X#”Y - Link: number, n
 þ             - outer product (implicit range build on left AND right from n) with:
⁼              -   is equal (yields a table of 0s except the main diagonal is 1s)
  µ            - monadic chain separation, call that I
   Ḥ           - double (change all the 1s to 2s)
     Ṛ         - reverse I (a table of 0s with 1s as the anti-diagonal)
    +          - add (vectorises to make a table of zeros with 2s on the diagonal,
               -      1s on the anti-diagonal and, if the meet, a 3 at the centre)
       “/\X#”  - literal list of characters ['/','\','X','#']
      ị        - index into (replaces... 1:'/'; 2:'\'; 3:'X'; and 0:'#')
             Y - join with newline characters
               - as a full program: implicit print

```
> 4 votes

# Answer
# Python 2, 83 bytes

```
n=input()
for i in range(n):l=['#']*n;l[i],l[~i]='\X/X'[i-~i==n::2];print''.join(l)

```

Try it online!

-3 thanks to Jonathan Frech and G B.
> 4 votes

# Answer
# Ruby, ~~73 61~~ 59 bytes

```
->n{(0...n).map{|x|w=?#*n;w[x],w[~x]=?\\,n==1+x*2??X:?/;w}}

```

Try it online!
> 2 votes

# Answer
# Charcoal, 21 bytes

```
ＵＢ#Ｎν↗∕ν²×X﹪ν²‖ＢＯL﹪ν²

```

Try it online! Verbose version.
> 1 votes

# Answer
# SOGL V0.12, 16 bytes

```
.↔╝Ζ #ŗ.2%?╬3←╬¡

```

Try it Here!

Finally got use out of the fact that palindromizating `/` or `\` on the edge creates `X` (but this could be ~5 bytes less with a couple features I have had in mind for a while (e.g. that overlapping would overlap slashes too and palindomizating commands have the option to choose the overlap amount from the remainder of ceiling dividing))

Explanation:

```
.↔                push input ceiling-divided by 2 (. is required because SOGLs input is taken lazily)
  ╝               create a diagonal of that length
   Ζ #ŗ           replace spaces with hashes
       .2%?       if the input % 2 isn't 0
           ╬3       palindromize with 1 overlap
             ←      stop program
              ╬¡  [else] palindromize with 0 overlap

```
> 1 votes

# Answer
# , 68 bytes

```
write(c("#","\\","/","X")[(d=diag(n<-scan()))+d[n:1,]*2+1],"",n,,"")

```

Try it online!

Reads `n` from stdin. Creates a matrix of indices `(d=diag(n))+d[n:1,]*2+1` to index into the vector of characters to print, which results in a vector of characters. `write` writes it as a matrix to `""` (stdout) with `n` columns and separator `""`.
> 1 votes

# Answer
# MATL, 14 bytes

```
'\/X#'iXytPE+)

```

Try it online!

Explanation: suppose the input is 3

```
'\/X#'               push this character string.
i                    read in input. stack is ['\/X#';3]
Xy                   push nxn identity matrix.
                     stack is ['\/X#'; [1 0 0 ; 0 1 0 ; 0 0 1]]
tP                   duplicate and flip left-right
                     stack is ['\/X#'; [1 0 0 ; 0 1 0 ; 0 0 1];
                                       [0 0 1 ; 0 1 0 ; 1 0 0]]
E+                   double TOS and add top 2 stack elements
                     stack is ['\/X#'; [1 0 2 ; 0 3 0 ; 2 0 1]]
)                    index; 1-based modular, so
                     1 -> \, 2 -> /, 3 -> X, 0 -> #
                     implicit output.

```
> 1 votes

# Answer
# Javascript, 103 bytes

```
n=>{for(let i=n,j,s;i--;){s="";for(j=n;j--;)s+=i==j?n-j-1==j?"X":"\\":n-j-1==i?"/":"#";console.log(s)}}

```

Try it online!

A more readable version with spaces and breaks added:

```
n => {
  for (let i = n, j, s; i--;) {
    s="";
    for (j = n; j--;)
      s += i == j
        ? n - j - 1 == j
          ? "X"
          : "\\"
        : n - j - 1 == i
          ? "/"
          : "#";
    console.log(s)
  }
}

```
> 1 votes

# Answer
# Husk, 20 bytes

```
´Ṫ§o!"¦/X#"+=ȯD=←¹+ŀ

```

Try it online!
> 1 votes

# Answer
# , 24 bytes

```
Àé#ÀÄòr\jlò|òr/klòÇÜ/ãrX

```

Try it online!
> 0 votes

# Answer
# Python 2, 133 bytes

```
def f(k,h="#"):s=[h*i+"\\"+h*(k-i*2-2)+"/"+i*h for i in range(k/2)];print"\n".join(s+k%2*[k/2*h+"X"+k/2*h]+[e[::-1]for e in s[::-1]])

```

Try it online!

A beautiful mess done on mobile :-). If you have golfing suggestions, you are welcome to edit in yourselves (and credit you!), because I will be sleeping :P.
> 0 votes

# Answer
# Python 2, 122 bytes

```
def f(n):s='\\'+'#'*(n-2)+'/';return['x'][:n]if n<2else[s]+['#'+l+'#'for l in f(n-2)]+[s[::-1]]
print'\n'.join(f(input()))

```

Try it online!

A recursive aproach
> 0 votes

# Answer
# Mathematica, 114 bytes

```
(s=#;F[x_]:=DiagonalMatrix[Table[x,s]];z=F@"\\"+Reverse@F@"/"//. 0->"#";If[OddQ@s,z[[t=⌈s/2⌉,t]]="X"];Grid@z)&

```
> 0 votes

# Answer
# Perl 5, 81 bytes

```
for$i(0..($n=<>)-1){$_='#'x$n;s|.{$i}\K.|\\|;s%.(.{$i})$%/$1%;s%/%X% if!/\\/;say}

```

Try it online!
> 0 votes

# Answer
## Canvas, 15 bytes

```
：：#×＊；＼：↔１１╋１１╋

```

Try it online!

could get it to 11 bytes if canvas's overlap function had a default setting but it doesn't so...
> 0 votes

# Answer
# Mathematica, 99 bytes

```
FromCharacterCode[(2#+Reverse@#+2)&@DiagonalMatrix[45~Table~#]/.{2->35,137->88}]~StringRiffle~"\n"&

```

This uses a somewhat different technique from the other Mathematica solution. Also, we should probably start calling it the Wolfram Language at some point.
> 0 votes

---
Tags: code-golf, math, ascii-art, matrix
---


title: Hide the buildings

text:
# Question
Title: Hide the buildings
Shorter version of Skyscrapers Challenge

### Task

Given an array of building heights and a positive integer `k`, find all the permutations(without duplicates) of the heights such that exactly `k` buildings are visible.

Any building will hide all shorter or equal height buildings behind it.

Any format for input and output is valid.

Input array will never be empty.

In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.

### Examples:

(Length of output is shown for very long outputs,but your output should be all possible permutations)

```
input:[1,2,3,4,5],2
output: 50

input:[5,5,5,5,5,5,5,5],2
output: []

input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.

input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]

input:[1,2,3,4,5,6,7,8,9],4
output:67284

input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]

input:[3,4,1,2,3],2
output:31

```

**This is code-golf so shortest code wins**

*Optional: If possible, can you add something like `if length is greater than 20: print length else print answer`. In the footer, not in the code.*

# Answer
> 6 votes
# 05AB1E, ~~10~~ 9 bytes

```
œÙʒη€àÙgQ

```

Try it online or verify (almost) all test cases (test case `[1,2,3,4,5,6,7,8,9],4` times out).
Footer of the TIO does what OP asked at the bottom:

> *Optional: If possible, can you add something like `if length is greater than 20: print length else print answer`. In the footer, not in the code.*

**Explanation:**

```
œ            # Permutations of the (implicit) input-list
             #  i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
 Ù           # Only leave the unique permutations
             #  i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
             #   → [[1,2,2],[2,1,2],[2,2,1]]
  ʒ          # Filter it by:
   η         #  Push the prefixes of the current permutation
             #   i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
    €à       #  Calculate the maximum of each permutation
             #   i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
      Ù      #  Only leave the unique maximums
             #   i.e. [1,2,2] → [1,2]
       g     #  And take the length
             #   i.e. [1,2] → 2
        Q    #  And only leave those equal to the second (implicit) input
             #   i.e. 2 and 2 → 1 (truthy)

```

# Answer
> 5 votes
## Haskell, 73 bytes

```
import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations

```

Try it online!

# Answer
> 5 votes
# Jelly, ~~12~~ 10 bytes

```
Œ!Q»\QL=ʋƇ

```

Try it online!

*-2 bytes by @Erik the Outgolfer*

This is a dyadic function taking the building heights and `k` in that order.

```
Œ!                All permutations of first input
Œ!Q               Unique permutations of first input
   »\              Running maximum
     Q             Unique values
      L            Length of this array
       =           Equals k
        ʋ        Create a monad from these 4 links
   »\QL=ʋ        "Are exactly k buildings visible in arrangement x?"
         Ƈ     Filter if f(x)
Œ!Q»\QL=ʋƇ     All distinct perms of first input with k visible buildings.

```

# Answer
> 4 votes
# Pyth, ~~18~~ 16 bytes

```
fqvzl{meSd._T{.p

```

Try it here.

Note that the online version of the Pyth interpreter throws a memory error on the largest test case.

```
f                       Filter lambda T:
  q                       Are second input and # visible buildings equal?
    v z                     The second input value
    l {                     The number of unique elements in
        m                   the maximums
          e S d             ...
          ._ T              of prefixes of T
    { .p                  over unique permutations of (implicit first input)

```

# Answer
> 2 votes
# Perl 6, ~~81~~ 63 bytes

*-18 bytes thanks to nwellnhof!*

```
{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [\max] @_}}

```

Try it online!

Anonymous code block that takes input curried, e.g. `f(n)(list)`. That `.unique(:with(*eqv*))` is annoyingly long though `:(`

### Explanation:

```
{;                                                            }  # Anonymous code block
  *.permutations.unique(:with(*eqv*))  # From all distinct permutations
                                     .grep:{                 }  # Filter where
                                                set [\max] @_   # Visible buildings
                                            $_==      # Equals num

```

# Answer
> 2 votes
# Japt, 11 bytes

```
á f_åÔâ Ê¥V

```

Try it online!

For the longer outputs, adding `} l` to the end will output the length instead. The online interpreter times out for the `[1,2,3,4,5,6,7,8,9],4` test case, regardless of outputting the length or the list.

Explanation:

```
á              :Get all permutations
  f_           :Keep only ones where:
    åÔ         : Get the cumulative maximums (i.e. the visible buildings)
      â Ê      : Count the number of unique items
         ¥V    : True if it's the requested number

```

# Answer
> 1 votes
# JavaScript (ES6), ~~108~~ 107 bytes

Takes input as `(k)(array)`. Prints the results with `alert()`.

```
k=>P=(a,p=[],n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)

```

Try it online!

### Commented

```
k =>                        // k = target number of visible buildings
  P = (                     // P = recursive function taking:
    a,                      //   a[] = list of building heights
    p = [],                 //   p[] = current permutation
    n = k,                  //   n = counter initialized to k
    h = 0                   //   h = height of the highest building so far
  ) =>                      //
    a.map((v, i) =>         // for each value v at position i in a[]:
      P(                    //   do a recursive call:
        a.filter(_ => i--), //     using a copy of a[] without the i-th element
        [...p, v],          //     append v to p[]
        n - (v > h),        //     decrement n if v is greater than h
        v > h ? v : h       //     update h to max(h, v)
      )                     //   end of recursive call
    )                       // end of map()
    + a ||                  // unless a[] was not empty,
    n ||                    // or n is not equal to 0,
    P[p] ||                 // or p[] was already printed,
    alert(P[p] = p)         // print p[] and store it in P

```

# Answer
> 1 votes
# Husk, 9 bytes

```
fȯ=⁰Lü≤uP

```

Try it online!

# Answer
> 0 votes
# Python 2, ~~114~~ 113 bytes

```
lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*

```

Try it online!

<sub>-1 byte, thanks to ovs</sub>

---

# Python 3, 113 bytes

```
lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*

```

Try it online!

# Answer
> 0 votes
# J, ~~43~~ 38 bytes

*-5 bytes after incorporating an optimization from Kevin's O5AB13 answer*

```
(]#~[=([:#@~.>./\)"1@])[:~.i.@!@#@]A.]

```

Try it online!

## ungolfed

```
(] #~ [ = ([: #@~. >./\)"1@]) ([: ~. i.@!@#@] A. ])

```

## explanation

we're merely listing all possible perms `i.@!@#@] A. ]`, taking uniq items thereof with `~.`, then filtering those by the number of visible building, which must equal the left input.

the key logic is in the parenthetical verb which calcs the number of visible buildings:

```
([: #@~. >./\)

```

Here we use a max scan `>./\` to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.

---
Tags: code-golf, permutations
---


title: Repeating pattern of empty lines

text:
# Question
Title: Repeating pattern of empty lines
Write the shortest program or function that takes some text as input, and outputs either it or an empty line in a repeating pattern:

```
some text
some text

some text
some text

some text
some text

...

```

This must continue indefinitely, or until some unpreventable limitation occurs (stack size, memory, etc.). It must be newline separated, and you can assume the inputted text is made up of non-newline printable ASCII characters. Note that it doesn't have to follow the pattern text-text-empty, and text-empty-text would be equally valid.

The ratio of text lines and empty lines will also be specified by input. There are various ways you can do this (though you only need to support one):

* A fraction represented as a floating point number (this can represent the fraction which do OR do not have text in them, but it must be consistent)
* A ratio of lines with text to lines without (represented as two integer inputs)
* A fraction of lines which do OR do not have text in them (represented as an integer numerator and denominator)

Example:

Text: `Hello, world!`
Ratio: `2:3`

```
Hello, world!
Hello, world!

Hello, world!
Hello, world!

...

```

Text: `fraction`
Fraction: `1/3`

```
fraction

fraction

fraction

...

```

Text: `decimal decimal decimal`
Input: `0.6`

```
decimal decimal decimal
decimal decimal decimal
decimal decimal decimal

decimal decimal decimal
decimal decimal decimal
decimal decimal decimal

...

```

Text: `example with a different pattern` Fraction: `2/5`

```
example with a different pattern

example with a different pattern

example with a different pattern

example with a different pattern

...

```

This is code golf, so the shortest answer in bytes, per language, wins.

# Answer
> 6 votes
## Pip, ~~26~~ 12 bytes

```
T0{LbPaLcPx}

```

-14 bytes after taking ratio as two arguments.

### Explanation:

```
T0           Till 0 (infinite loop)
  {Lb        Loop b(second argument) number of times
     Pa      Print a(first argument) with newline
       Lc    Loop c(third argument) number of times
         Px} Print x(empty string) with newline

```

Try it online!

# Answer
> 5 votes
# C (gcc), ~~67 ..~~ 38 bytes

```
i;f(s,a,t){for(;puts(i++%t<a?s:""););}

```

Try it online!

* Thanks to @att for 11 byte saved and to @ErikF for 7 bytes saved!

Takes input as string, number of printed lines, total lines.

~~We flush buffer at every iteration.~~

puts() returns non negative if no error occours, hope it doesn't return 0 either!

# Answer
> 5 votes
# Python 2, 44 bytes

```
def f(t,a,b,n=0):print(n%b<a)*t;f(t,a,b,n+a)

```

Try it online!

Prints until exceeding max recursion depth, which the challenge seems to allow. As a program:

**45 bytes**

```
t,a,b=input()
n=0
while 1:print(n%b<a)*t;n+=a

```

Try it online!

The idea is to to use a counter `n` that cycles through values modulo `b`, and only print the text if this is from `0` to `a-1`, and otherwise print a blank line. We could also do `n+=1` in place of `n+=a` to get a different pattern where the text and blank lines come in clumps rather than mixed throughout.

It almost works to use a float input for the density as below:

**40 bytes** (not working)

```
def f(t,p,n=0):print(n%1<p)*t;f(t,p,n+p)

```

Try it online!

The issue is float imprecision -- a number like `12.6` might have its decimal part be very slightly bigger or smaller than `0.6`. This method would work for irrational densities as well, limited precision aside.

# Answer
> 4 votes
# APL (Dyalog Unicode), 10 bytes (SBCS)

Full program. Prompts for text, then for ratio of lines with text to lines without (as two integers). Runs forever.

```
⎕←⍣≢↑⎕/⍞''

```

Try it online!

`⍞''` prompt for text and juxtapose with an empty string

`⎕/` prompt for replication factors and replicate

stack them on top of each other

`⍣≢` repeat until the value changes (i.e. never):

`⎕←` output

# Answer
> 3 votes
# Python 3.8 (pre-release), ~~48~~ 47 bytes

Saved a byte thanks to Dion

```
def f(t,a,b):
 while 1:print((t+'\n')*a+'\n'*b)

```

Try it online!

`t` is the text to print, `a`:`b` is the ratio of lines of text to empty lines.

# Answer
> 3 votes
# , 17 16 bytes

```
$:,[echo@#'',:~]

```

Try it online!

Note: If the empty lines cannot have spaces, then `$:,[echo@>@#a:;~]` works for 17 bytes.

## how

Uses a kind of "fork bomb" recursion:

* `$:` \- calls entire verb again
* `,` \- then append...
* `[echo@#` \- the echo of the left argument applied as a line-wise multiplier to...
* `'',:~]` \- the right argument catted line-wise with an empty string

# Answer
> 3 votes
# Japt, 13 bytes

Runs until the stack overflows. More golfing to follow ...

```
ÆOpWÃVÆOpPÃ©ß

```

Try it

# Answer
> 3 votes
# x86-16 machine code, IBM PC DOS, ~~34~~ 33 bytes

Binary:

```
00000000: be82 00ad 2d30 3092 52fe ca7c 0956 ac3c  ....-00.R..|.V.<
00000010: 0dcd 2975 f95e b00a cd29 fece 75eb 5aeb  ..)u.^...)..u.Z.
00000020: e7                                       .

```

Listing:

```
BE 0082     MOV  SI, 82H        ; SI to command line tail
AD          LODSW               ; load first two chars
2D 3030     SUB  AX, '00'       ; ASCII convert
92          XCHG AX, DX         ; DL = numerator, DH = denominator
        PATT_LOOP:
52          PUSH DX             ; save original numerator/denominator
        FRAC_LOOP:
FE CA       DEC  DL             ; decrement numerator
7C 09       JL   LF             ; if less than 0, just display LF
56          PUSH SI             ; save start of input string
        CHAR_LOOP:
AC          LODSB               ; load next char of string
3C 0D       CMP  AL, 0DH        ; is it a CR?
CD 29       INT  29H            ; write to console
75 F9       JNZ  CHAR_LOOP      ; if not a CR, keep looping
5E          POP  SI             ; restore start of input string
        LF:
B0 0A       MOV  AL, 0AH        ; LF char
CD 29       INT  29H            ; write to console
FE CE       DEC  DH             ; decrement denominator
75 EB       JNZ  FRAC_LOOP      ; if not 0, keep looping
5A          POP  DX             ; restore numerator/denominator
EB E7       JMP  PATT_LOOP      ; start over and loop indefinitely

```

Standalone DOS executable, input via command line. First two chars are numerator / denominator, followed by input string.

*(note: program slightly altered to only repeat 3 times for screenshots)*

# Answer
> 3 votes
# Jelly, 9 bytes

```
Ø.x⁹ẋṄ€1¿

```

A full program accepting the ratio as a list `[empty, full]` and the string which prints forever.

**Try it online!**

### How?

```
Ø.x⁹ẋṄ€1¿ - Main Link: list of integers, ratio ([empty, full]); list of characters, text
                                e.g.: [3, 2]; "Hello, world!"
Ø.        - bits                      [0, 1]
  x       - times (ratio)             [0, 0, 0, 1, 1]
   ⁹      - chain's right argument    "Hello, world!"
    ẋ     - repeat (vecorises)        ["", "", "", "Hello, world!", "Hello, world!"]
        ¿ - while...
       1  - ...condition: 1 (always)
      €   - ...do: for each:
     Ṅ    -          print with trailing newline

```

# Answer
> 3 votes
# Java (JDK), 58 bytes

```
(s,n,d)->{for(int i=0;;)System.out.println(i++%d<n?s:"");}

```

Try it online!

## Credits

# Answer
> 2 votes
# SNOBOL4 (CSNOBOL4), ~~100~~ ~~88~~ 87 bytes

```
	T =INPUT
	CODE('N' DUPL(';	OUTPUT =T',INPUT) DUPL(';	OUTPUT =',INPUT) ':(N)')	:(N)
END

```

Try it online!

Takes input as `TEXT`, `M`, `N` on separate lines.

Using the `CODE` function, this generates an infinite loop of

```
N; OUTPUT =T; OUTPUT =T ...; OUTPUT =; OUTPUT =; ... :(N)
```

Or equivalently (with `;` being replaced by newlines):

```
N
 OUTPUT =T
 OUTPUT =T
 ...
 OUTPUT =
 OUTPUT =
 ...
 OUTPUT =:(N)
```

Which it then enters with the final `:(N)` and never leaves.

# Answer
> 2 votes
## Batch, 87 bytes

```
@set f=@for /l %%i in (1,1,
@set/ps=
:g
%f%%1)do @echo(%s%
%f%%2)do @echo(
@goto g

```

Takes the text and blank line counts as command line arguments and the text to repeat on standard input. Explanation:

```
@set f=@for /l %%i in (1,1,

```

Define what is effectively a macro for two very similar loops.

```
@set/ps=

```

Input the text.

```
:g

```

Begin an infinite loop.

```
%f%%1)do @echo(%s%

```

Print the text the desired number of times.

```
%f%%2)do @echo(

```

Print the desired number of blank lines.

```
@goto g

```

Rinse and repeat.

# Answer
> 2 votes
# , ~~48~~ 47 bytes

*Edit: -1 byte thanks to Giuseppe*

```
function(t,c)repeat cat(rep(c(t,''),c),sep='
')

```

Try it online!

Function with arguments specifying text `t` and vector `c` of counts of text & blank lines.

# Answer
> 2 votes
# 05AB1E, 8 bytes

```
[s`¶×?F=

```

First input is the text, second input is a pair `[amount_of_nonempty_lines, amount_of_empty_lines]`; outputs the empty lines before the non-empty lines.

Try it online.

**Explanation:**

```
[         # Start an infinite loop:
 s        #  Swap the two (implicit) inputs, so the pair it at the top of the stack
  `       #  Pop and push its contents to the stack
   ¶×     #  Repeat a newline character "\n" the top value amount of times as string
     ?    #  Pop and output it without trailing newline
      F   #  Pop and loop the top value amount of times:
       =  #   And output the top string with trailing newline (without popping)

```

# Answer
> 2 votes
# Husk, 8 bytes

```
~o¢+RøR⁰

```

Try it online! This program takes the string, the number of lines with text, and the number of lines without text as three separate arguments.

# Answer
> 1 votes
# JavaScript (V8), 40 bytes

Expects `(p, q)(s)`, where \\$p/q\\$ is the fraction of lines that have the string \\$s\\$ in them.

This runs until the call stack overflows.

```
(p,q,t=0)=>g=s=>print(t++%q<p?s:'')&g(s)

```

Try it online!

# Answer
> 1 votes
## Assembly (MIPS, SPIM), 236 bytes, 6 * 23 = 138 assembled bytes

Full program that takes the input in the order (`input string, numerator, denominator`). Output is to STDOUT.

```
.data
m:
.text
main:li$v0,8
la$a0,m
li$a1,99
syscall
li$v0,5
syscall
move$t0,$v0
li$v0,5
syscall
move$t1,$v0
s:li$t2,0
li$v0,4
la$a0,m
l:syscall
add$t2,$t2,1
blt$t2,$t0,l
li$t2,0
li$a0,10
li$v0,11
p:syscall
add$t2,$t2,1
blt$t2,$t1,p
b s

```

Try it online!

## Explanation

```
.data
msg:                            # Here's the string input buffer (dynamically allocated)

.text
main:
    li $v0, 8                   # Set syscall code 8
    la $a0, msg                 # The first operand is the input buffer
    li $a1, 99                  # The second is the maximum length of input

    syscall                     # Read a line of characters from input

    li $v0, 5                   # Set syscall code 5
    syscall                     # v0 = integer from input
    move $t0, $v0               # t0 = v0

    li $v0, 5                   # Re-set syscall code 5
    syscall                     # v0 = integer from input
    move $t1, $v0               # t1 = v0

    start:                      # Main loop:
        li $t2, 0               #     t2 = 0 (our counter)

        li $v0, 4               #     Set syscall code 4
        la $a0, msg             #     First operand: the inputted message at msg
        loop:                   #     loop:
            syscall             #         Print the message at msg
            add $t2, $t2, 1     #         Increment counter
            blt $t2, $t0, loop  #         If t2 < t0, jump back

        li $t2, 0               #     Clear counter

        li $v0, 11              #     Set syscall code 11
        li $a0, 10              #     First operand: '\n'

        lop:                    #     second loop:
            syscall             #         Print character in a0
            add $t2, $t2, 1     #         Increment counter
            blt $t2, $t1, lop   #         if t2 < t1, jump back

        b start                 #     Jump back to the main loop

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 35 bytes

```
Do[Print@If[i>#2,#,""],∞,{i,#3}]&

```

Try it online!

Takes `[text, num, denom]`, where `num/denom` is the ratio of lines *without* text.

# Answer
> 1 votes
# SimpleTemplate 0.84, 99 bytes

Yes, it is quite long, but it works!

```
{@callexplode intoM":",argv.1}{@while1}{@forfrom 1toM.0}{@echolargv.0}{@/}{@forfrom 1toM.1}{@echol}

```

Takes input in the form of an array with the format `['text', '1:1']`.

---

If taking input as 2 separate numbers (`['text', 1, 1]`) is acceptable, the code can be reduced to this (66 bytes):

```
{@forfrom 1toargv.1}{@echolargv.0}{@/}{@forfrom 1toargv.2}{@echol}

```

---

**Ungolfed:**

Below is a more readable version of the top code:

```
{@call explode into ratio ":", argv.0}
{@while true}
    {@for i from 1 to ratio.0}
        {@echo argv.0, EOL}
    {@/}
    {@for i from 1 to ratio.1}
        {@echo EOL}
    {@/}
{@/}

```

Notice that `{@echol}` and `{@echo EOL}` do the same thing: output whatever, ending with a newline.

---

You an try it on: http://sandbox.onlinephpfunctions.com/code/abf48bd44a808e91f130d4a390fcb8a18d6ded39

# Answer
> 1 votes
# PHP, ~~52~~ 51 bytes

```
for($a=$argv;;)echo($i++%$a[3]<$a[2]?$a[1]:"")."
";

```

Try it online!

Nothing new under the sun: PHP arguments and vars prefix eating bytes.. Will go on "forever" (until it overflows the max integer value, and starts using floats for `$i`, then probably the legendary precision for big floats will cause inconsistent results)

EDIT: newline replaced by.. a newline to save 1 byte

---
Tags: code-golf, string
---


title: Clockwise matrix rotation

text:
# Question
Title: Clockwise matrix rotation
The title pretty much describes it all. Given as input a \\$n \times m\\$ matrix and an integer \\$i\\$ create a complete function/program that returns the matrix \\$i\\$ times clockwise rotated by \\$90^\circ\\$.

**Rules:**

* as matrix you can use any convenient representation you like e.g. *a list of lists etc...*
* matrix values can be positive and/or negative integer numbers
* \\$n\\$ and \\$m\\$ are of course always positive integers between 1 and 10
* \\$i\\$ can be any valid integer which belongs in the following range: \\${0...10^5}\\$
* Standard rules & winning criteria apply but no "winning" answer will be chosen.

**EDIT:** I had to edit the initial question because for some programming languages it takes too long to compute the result for \\$i\in\\{0...10^7\\}\\$. There is a workaround to it but since it's a code-golf just make sure that it simply runs successfully for at least \\$i\in\\{0...10^5\\}\\$.

**Some test cases:**

<pre><code>==== example 1 ====
Input:
5
[[1, 3, 2, 30,],
 [4, 9, 7, 10,],
 [6, 8, 5, 25 ]]

Expected Output:
[[ 6  4  1],
 [ 8  9  3],
 [ 5  7  2],
 [25 10 30]]

==== example 2 ====
Input:
100
[[1]]

Expected Output:
[[1]]

==== example 3 ====
Input:
15
[[150,    3,  2],
 [  4, -940,  7],
 [  6, 8000,  5]]

Expected Output:
[[   2    7    5],
 [   3 -940 8000],
 [ 150    4    6]]

==== example 4 ====
Input:
40001
[[1, 3, 9]]

Expected Output:
[[1],
 [3],
 [9]]
```
</code></pre>

# Answer
> 9 votes
# APL (Dyalog Unicode), 7 bytes

```
⌽∘⍉⍣⎕⊢⎕

```

Try it online!

prompt for matrix expression from stdin

yield that

prompt for \\$i\\$ expression from stdin

do the following that many times

transpose

and then

mirror

# Answer
> 5 votes
# Pyth, 7 6 bytes

```
uC_GQE

```

Try it online!

-1 Thanks to @FryAmTheEggman

Rotates the matrix by reversing the order of rows and taking the transpose. Takes and returns lists of lists.

## How it works

```
uC_GQE
u    E - Reduce the second input
  _G   - By reversing the order of rows
 C     - And transposing
    Q  - An amount of times equal to the first input

```

# Answer
> 5 votes
# , 7 bytes

```
|:@|.^:

```

Try it online!

An adverb train. Right argument is the matrix, left argument is the repetition count.

### How it works

```
|:@|.^:
     ^:  Repeat the function:
   |.      Reverse vertically
  @        and then
|:         Transpose
         Absent right argument to `^:`:
           bind to the left argument (repeat count)

```

# Answer
> 5 votes
# Jelly, 4 bytes

Naive implementation. There might be a shorter way I'm not aware of.

```
ṚZ$¡

```

Try it online!

# Answer
> 5 votes
# Haskell, 50 bytes

```
(!!).iterate(foldr(zipWith$flip(++).pure)e)
e=[]:e

```

Try it online!

# Answer
> 5 votes
# Ruby, 39 bytes

```
->m,n{n.times{m=m.reverse.transpose};m}

```

Try it online!

# Answer
> 5 votes
# K (oK), 6 bytes

```
(+|:)/

```

Try it online!

# Answer
> 4 votes
# Japt `-R`, 2 bytes

```
zV

```

Try it

```
Rotate matrix by 90 degrees 2nd input times

```

# Answer
> 4 votes
# Python 2, 44 bytes

```
f=lambda A,i:i%4and f(zip(*A[::-1]),i-1)or A

```

Try it online!

Input/output is a `list` of `tuples`. (The `%4` is a workaround for Python's recursion limit; could save a byte otherwise).

# Answer
> 4 votes
# 05AB1E (legacy), 3 bytes

```
Føí

```

Takes \\$i\\$ as first input; matrix the second.

Try it online or verify all test cases.

**Explanation:**

```
F    # Loop the (implicit) input-integer amount of times:
 ø   #  Zip/transpose the matrix; swapping rows/columns
     #  (this will take the (implicit) input in the first iteration)
  í  #  Reverse each row
     # (after the loop, the resulting matrix is output implicitly)

```

NOTE: Uses the legacy version only because of performance. The last test case times out in the rewrite version. Both the legacy and rewrite versions would be the same, though.

# Answer
> 3 votes
# Julia 1.0, 6 bytes

Kind of cheating, but Julia has a built in `rotl90` function, that does exactly that.

```
rotl90

```

Try it online!

# Answer
> 2 votes
# JavaScript (ES6), 58 bytes

Takes input as `(i)(matrix)`.

```
i=>g=m=>i--?g(m[0].map((_,x)=>m.map(r=>r[x]).reverse())):m

```

Try it online!

**Note**: The last test case was edited to prevent a recursion error. We can obviously use `i--&3` (60 bytes) to support much larger values.

# Answer
> 2 votes
# Octave, 17 bytes

Unfortunately `rot90` rotates the input *counterclockwise*.

```
@(x,i)rot90(x,-i)

```

Try it online!

# Answer
> 2 votes
# MATL, ~~5~~ 3 bytes

-2 bytes thanks to @LuisMendo!

```
_X!

```

Try it online!

# Answer
> 2 votes
# Java 8, ~~141~~ ~~138~~ ~~131~~ 130 bytes

```
(m,i)->{for(int t[][],a,b,j;i-->0;m=t)for(t=new int[b=m[0].length][a=m.length],j=a*b;j-->0;)t[j%b][j/b]=m[a-j/b-1][j%b];return m;}

```

-7 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Code explanation:**

```
(m,i)->{                 // Method with int-matrix and int parameters and int-matrix return
  for(int t[][],         //  Temp int-matrix as replacement
          a,b,           //  Temp integers used for the dimensions
          j;             //  Temp integer for the inner loop
      i-->0;             //  Loop the input `i` amount of times:
      m=t)               //    After every iteration: replace the input-matrix `m` with `t`
    for(t=new int[b=m[0].length][a=m.length],
                         //   Create a new temp-matrix `t` with dimensions `b` by `a`,
                         //   where `b` & `a` are the amount of columns & rows of matrix `m`
        j=a*b;           //   Set `j` to the product of these dimensions
        j-->0;)          //   And inner loop in the range [`j`, 0):
      t                  //  Replace the value in `t` at position:
       [j%b]             //   `j%b` (let's call this row A),
            [j/b]        //   `j/b` (let's call this column B)
        =m               //  And replace it with the value in `m` at position:
          [a-j/b-1]      //   `a-j/b-1` (which is the reversed column B as row,
                         //     so it both transposes and reverses at the same time),
                   [j%b];//   `j%b` (which is row A as column)
  return m;}             //  And finally return the new int-matrix

```

**To save bytes**, the inner loop is a single loop and uses `j/a` and `j%a` as cell positions. So a loop like this:

```
for(r=a;r-->0;)for(c=b;c-->0;)t[c][r]=m[b-r-1][c];

```

Has been golfed to this:

```
for(j=a*b;j-->0;)t[j%b][j/b]=m[a-j/b-1][j%b];

```

to save 5 bytes.

# Answer
> 2 votes
# , 64 bytes

```
r=function(x,i){o=x;n=0;while(n<i){o=t(apply(o,2,rev));n=n+1};o}

```

Try it online!

Not really efficient...

Uses rotation approach proposed by Matthew Lundberg

# Answer
> 2 votes
# Husk, 7 bytes

```
~!→¡oT↔

```

Try it online! I've always found it odd that the only real way to iterate a function a set number of times in Husk is to index into the infinite list of that function's iterates.

# Answer
> 1 votes
# Pari/GP, 37 bytes

```
f(m,n)=for(i=1,n,m=Mat(Vecrev(m~)));m

```

Try it online!

# Answer
> 1 votes
# GolfScript, 10 bytes

```
~{-1%zip}*

```

Try it online!

```
~{      }*   # Repeat i times
  -1%        # Reverse the array
     zip     # Zip

```

When the program finishes, only the elements of the matrix are displayed. To see how it actually was outputted, use this.

# Answer
> 1 votes
# Arn, ~~8~~ 7 bytes

```
Ç├Úe↑Î(

```

Try it!

# Explained

Unpacked: `&.{.@@.<` ELABORATE HERE

```
&. Mutate N times
  { Block, key of `_`
        _ Implied variable
      .@ Transposed
    @ Binded map
      .< Reverse
  } End block; implied

```

Input is two lines, the first being an array and the second a number. `&.` supports both 2 separate inputs and one as an array, and as `_` is automatically the STDIN separated on newlines and parsed, this code is valid.

# Answer
> -1 votes
# Mathematica, 32 bytes

```
a = {{3, 4, 5}, {5, 6, 7}, {8, 9, 10}, {11, 12, 13}};

Nest[Reverse /@ Transpose[#] &, a, i]

```

---
Tags: code-golf, array, matrix
---


title: Convert to Bibi-binary

text:
# Question
Title: Convert to Bibi-binary
Bibi-binary is a numeric system invented by Boby Lapointe in order to represent numbers in letters which pronunciation seems funny.

Your task is to convert decimal numbers into Bibi-binary!

## Conversion

A number is converted to base 16 (hexadecimal) and each character is replaced by its Bibi-binary name:

```
0 = HO
1 = HA
2 = HE
3 = HI
4 = BO
5 = BA
6 = BE
7 = BI
8 = KO
9 = KA
A = KE
B = KI
C = DO
D = DA
E = DE
F = DI

```

Let `N` be a positive integer (between 1 -\> 2^31-1). For every character in the hexadecimal representation of `N`, replace the character by its according Bibi-binary pair (the table above contains all the pairs).

## Example

* `N` = 156
* `H` = (hexadecimal representation of `N`) --\> 9C
* 9 --\> KA, C --\> DO

Thus the output is KADO.

## Input & output

You will receive an positive 32-bit integer `N`, which you will have to turn into Bibi-binary.

You may (return, print, etc...) in any convenient format, **but the pairs have to be connected**! So `KA DO` wouldn't be okay, but `KADO` would.

Both, **lowercase and uppercase** are allowed.

## Rules

* No loopholes.
* This is code-golf, so the shortest code wins.

## Testcases

```
2048 -> KOHOHO
156 -> KADO
10000 -> HEBIHAHO
12 -> DO

```

# Answer
# 05AB1E, ~~20~~ ~~18~~ 16 bytes

```
hv…Ã‚kdžM¨ÁâyHèJ

```

**Explanation**

```
h                     # convert input to hex
 v                    # for each
  …Ã‚kd               # string of the possible first Bibi-binary letters
       žM¨Á           # string of the possible second Bibi-binary letters
           â          # cartesian product to produce list of Bibi-binary pairs
            yH        # convert hex char to base 10
              è       # use this to index into the list
               J      # join

```

Try it online!

Saved 2 bytes thanks to Adnan
> 12 votes

# Answer
# Python 2, 58 bytes

```
f=lambda n:(n>15and f(n/16)or"")+"HBKD"[n/4%4]+"OAEI"[n%4]

```

A recursive solution. Try it on Ideone.
> 12 votes

# Answer
# Python 2, ~~81~~ 76 bytes

```
lambda n:''.join('HBKD'[int(x,16)/4]+'OAEI'[int(x,16)%4]for x in hex(n)[2:])

```

Chooses the bibi-digit to represent each hex digit based on the patterns in the bibi-digits.
> 4 votes

# Answer
## Javascript (ES6), ~~58~~ ~~53~~ 43 bytes

```
f=n=>n?f(n>>4)+'HBKD'[n/4&3]+'OAEI'[n&3]:''

```

*Saved 10 bytes (no support for n = 0 anymore)*

### Demo

```
var f=n=>n?f(n>>4)+'HBKD'[n/4&3]+'OAEI'[n&3]:''

console.log(f(2048));   // -> KOHOHO
console.log(f(156));    // -> KADO
console.log(f(10000));  // -> HEBIHAHO
console.log(f(12));     // -> DO
```
> 4 votes

# Answer
# Jelly, 17 bytes

```
b⁴d4ị"€“BKDH“AEIO

```

Try it online! or verify all test cases.

### How it works

```
b⁴d4ị"€“BKDH“AEIO  Main link. Argument: n

b⁴                 Convert n to base 16.
  d4               Divmod 4; map each base-16 digit k to [k / 4, k % 4].
       “BKDH“AEIO  Yield ["BKDH", "AEIO"].
      €            For each quotient-remainder pair [q, r]:
    ị"               Yield "BKDH"[q] and "AEIO"[r] (1-based indexing).

```
> 4 votes

# Answer
# Pyth, 28 bytes

```
L+?>b15y/b16k@*"HBKD""OAEI"b

```

Defines a function `y`. Basically the same algorithm as my Python answer.

Explanation:

```
L                            # Define a function, y, with an argument, b.
  ?>b15                      # If b > 15, then:
       y/b16                 # Call y with b / 16, else:
            k                # The empty string.
 +                           # Append with
              *"HBKD""OAEI"  # The Cartesian product of "HBKD" and "OAEI". Gives all the letter pairs in order
             @             b # Get the b'th number from that list. Because @ in Pyth is modular, we don't need to take b % 16.

```

Try it here! (The extra two chars at the end is just to call the function)
> 3 votes

# Answer
# Ruby, ~~55~~ 51 bytes

A recursive anonymous function:

```
f=->i{(i>15?f[i/16]:'')+'HBKD'[i%16/4]+'OAEI'[i%4]}

```

Call it for example with `f[156]` and it returns `"KADO"`
> 3 votes

# Answer
# PHP ,63 Bytes

contribution by @Titus Thank You

```
for($n=$argv[1];$n;$n>>=4)$r=HBKD[$n/4&3].OAEI[$n&3].$r;echo$r;

```

72 Bytes works also with zero

```
do$r=OAEIHBKD[$t*4+($n=&$argv[1])%4].$r;while(($t=!$t)|$n=$n>>2);echo$r;

```

76 Bytes alternative Version

```
for($i=2*strlen(dechex($n=$argv[1]));$i;)echo HBKDOAEI[$i%2*4+$n/4**--$i%4];

```
> 3 votes

# Answer
# J, ~~35~~ 33 bytes

```
[:,(,/'HBKD',"0/'OAEI'){~16#.inv]

```

Generates the table of bibi-binary values for integers \[0, 16), then converts the input *n* to a list of base 16 digits and selects the corresponding bibi-binary name for each hex digit.

Saved 2 bytes thanks to @randomra.

## Usage

```
   ,/'HBKD',"0/'OAEI'
HO
HA
HE
HI
BO
BA
BE
BI
KO
KA
KE
KI
DO
DA
DE
DI

```

This part generates a 16 x 2 array of characters for the bibi-binary name of each hex digit.

```
   f =: [:,(,/'HBKD',."0 1'OAEI'){~16#.inv]
   f 156
KADO
   f 2048
KOHOHO

```

## Explanation

```
,/'HBKD',"0/'OAEI'
  'HBKD'    'OAEI'  Constant char arrays
        ,"0/        Form the table of joining each char with the other
,/                  Join the rows of that table

[:,(,/'HBKD',."0 1'OAEI'){~16#.inv]  Input: n
                                  ]  Identity function, get n
                           16#.inv   Performs the inverse of converting an array of
                                     hex digits meaning it converts a value to a list of
                                     hex digits
   (,/'HBKD',."0 1'OAEI')            Create the bibi-binary names of each hex digit
                         {~          For each hex digit, select its bibi-binary name
[:,                                  Join the names to form a single string and return

```
> 3 votes

# Answer
# Perl, ~~52~~ 51 bytes

Includes +1 for `-p`

Run with the number on STDIN

```
bibi.pl <<< 156

```

`bibi.pl`:

```
#!/usr/bin/perl -p
1while$\=(<{H,B,K,D}{O,A,E,I}>)[$_%16].$\,$_>>=4}{

```
> 3 votes

# Answer
# Ruby, ~~85~~ 83 bytes

```
->x{x.to_s(16).chars.map{|d|"HOHAHEHIBOBABEBIKOKAKEKIDODADEDI"[2*d.to_i(16),2]}*''}

```

Just a quick and simple solution without encoding the string.
> 2 votes

# Answer
# Pyth, 21 bytes

```
sm@*"HBKD""OAEI"djQ16

```

A program that takes input of an integer from STDIN and prints the result.

Try it online

**How it works**

```
sm@*"HBKD""OAEI"djQ16  Program. Input: Q
                 jQ16  Yield decimal digits of the base-16 representation of Q as a list
    "HBKD"              Possible first letters
          "OAEI"        Possible second letters
   *                    Cartesian product of those two strings
  @                     Index into the above
 m              d      Map that across the digits list
s                      Concatenate
                       Implicitly print

```
> 2 votes

# Answer
# PHP, 93 bytes

```
$a=HBKDOAEI;$h=dechex($argv[1]);while($h{$i}!=''|$c=hexdec($h{$i++}))echo$a{$c/4}.$a{4+$c%4};

```

This basically leverages the integrated hexadecimal functions and a little trick in the while statement to save on curly braces.
> 2 votes

# Answer
# Java, 224 bytes

```
class N{public static void main(String[]a){String x="0HO1HA2HE3HI4BO5BA6BE7BI8KO9KAaKEbKIcDOdDAeDEfDI";for(int c:Long.toHexString(Long.valueOf(a[0])).toCharArray()){c=x.indexOf(c)+1;System.out.print(x.substring(c++,++c));}}}

```

Using some lookup table trickery Usage of Long type was to shave off a few bytes compared to Integer
> 2 votes

# Answer
# Dyalog APL, 19 bytes

Requires `⎕IO←0` which is default on many systems.

```
∊(,'HBKD'∘.,'OAEI')[16⊥⍣¯1⊢⎕]

```

enlist (make completely flat)

`(`...

`,` the raveled

`'HBKD'∘.,'OAEI'` concatenation table (i.e. all combos)

`)[` indexed by...

`16⊥⍣¯1` the inverse of base-16 to base 10 (i.e. base-10 to base 16) representation

of

the numeric input

`]`

TryAPL online!
> 2 votes

# Answer
## CJam, 20 bytes

```
qiGb"HBKD""OAEI"m*f=

```

Try it online! (As a linefeed-separated test suite.)

### Explanation

```
qi      e# Read input and convert to integer.
Gb      e# Get hexadecimal digits.
"HBKD"  e# Push this string.
"OAEI"  e# Push this string.
m*      e# Cartesian product, yields ["HO" "HA" "HE" "HI" "BO" ... "DE" "DI"].
f=      e# For each digit, select the corresponding syllable.

```
> 2 votes

# Answer
# Lua, 196 Bytes

```
function(n)s=""t={"H","B","K","D"}p={"O","A","E","I"}while n>0 do s=n%4 ..s n=math.floor(n/4)end s=("0"):rep(#s%2)..s o=nil return s:gsub(".",function(s)o=not o return o and t[s+1]or p[s+1]end)end

```

Lua is annoying for this sort of a task, as it doesn't per default contain a hex or binary conversion method. Most of the flesh is converting it to base 4. After that we force a 0 behind it if we need to using `s=("0"):rep(#s%2)`, then we using gsub replace all the didgets with with their BIBI counterpart.
> 1 votes

# Answer
# K (ngn/k), ~~30~~ 27 bytes

```
,/(,/"HBKD",/:\:"OAEI")@16\

```

Try it online!

Quite similar to the J solution by @miles and the APL solution by @adám.
> 1 votes

# Answer
# Japt, 13 bytes

```
s"HBKD"ï"OAEI

```

Try it

Or, with string compression:

```
s`baki`ó rï

```

Try it
> 1 votes

# Answer
# Haskell, 76 bytes

```
(until(\x->x<="HO"||x>="HP")(drop 2)`map`mapM id([1..8]>>["HBKD","OAEI"])!!)

```

Try it online!

Since the input is guaranteed to fit in 32 bits, we can generate a list of all \\$16^8 = 2^{32}\\$ strings and index into it, after removing `HO` (zeroes) from the start.

(Haskell's Prelude has no good tools for base conversion, but Cartesian products are real easy with `mapM`.)

To strip superfluous `HO`s from the start of each string, we `drop 2` characters from the front `until` the string either *equals* `HO` (0), or does not start with `HO`.

The obvious way to write this is `x=="HO"||take 2x/="HO"`, but `x<="HO"||x>="HP"` is a little shorter.
> 1 votes

# Answer
# Haskell, 50 bytes

```
(l!!)
l=[]:tail[x++[a,b]|x<-l,a<-"HBKD",b<-"OAEI"]

```

Try it online!

Recursively defines the infinite list `l` of all encoded numbers starting from 0.

---

# Haskell, 54 bytes

```
f n=mapM id([1|i<-[0..8],16^i<=n]>>["HBKD","OAEI"])!!n

```

Try it online!

Based off of Lynn's solution. The new idea is to avoid leading "zeroes" (`HO`'s) by predicting the number of digits in advance and only generating that many copies for `mapM`. A number has one digit in base 16 for each number in `1,16,256,4096,...` that is no greater than it. This gives the empty string for zero, but we could change it to `HO` like this:

**56 bytes**

```
f n=mapM id(0:[1|i<-[1..8],16^i<=n]>>["HBKD","OAEI"])!!n

```

Try it online!

A variant where we compute the number of digits directly:

**60 bytes**

```
f n=mapM id([0..until(\i->16^i>n)(+1)0]>>["HBKD","OAEI"])!!n

```

Try it online!

---

# Haskell, 54 bytes

```
f 0=""
f n=f(div n 16)++mapM id[cycle"HBKD","OAEI"]!!n

```

Try it online!
> 1 votes

# Answer
# Chip, 174 bytes

```
 z---.
!+ZZZ^~s
Axxx])~-vv/c
Ex]xx' ,x]/b
Bxxx])~^}~/d
Fx]xx'g*-}^a
Cxx])v]--/c
G]xx'>x~v/d
Dxx])x+-]/a
H]xx'`}--/b
 )x)-----'
Axx].zv~S
Bxx]+^'
Cxx]<
Dxx]<
E]v-'
F]<
G]<
H]'

```

Try it online! TIO includes a Bash wrapper that converts an integer string to an actual 32-bit integer value.

The top half prints out the letters corresponding to the binary data, once the bottom half has detected that we've reached the interesting data (in other words, we skip leading zeroes. To print all leading zeroes, remove the second line that starts with `A` and down.
> 0 votes

# Answer
# C (gcc), 206 bytes

```
#include<stdio.h>
#include<unistd.h>
int main(){int a=0;char c;while(read(0,&c,1)){a*=10;a+=c-'0';}c=8;while(c--)if(a&15<<c*4)break;if(c!=7)c++;while(c--)printf("%c%c","HBKD"[a>>c*4+2&3],"OAEI"[a>>c*4&3]);}

```

Uses as requested input, no check done on read return.

```
int a=0;char c;                                                                                // declares accumilator and input char
               while(read(0,&c,1)){a*=10;a+=c-'0';}                                                                                // read input in accumulator
                                                   c=8;while(c--)if(a&15<<c*4)break;if(c!=7)c++;                                                              // goto first not null byte
                                                                                while(c--)printf("%c%c",                                      // print for each byte
                                                                                "HBKD"[a>>c*4+2&3],                   // fetching right consonant
                                                                                "OAEI"[a>>c*4&3]); // fetching right vowel

```

Try it online!
> 0 votes

# Answer
# Husk, 20 bytes

```
ṁ!ṙ1*"HBKD""OAEI"B16

```

Try it online!

Similiar to the APL answer.

# Husk, 22 bytes

```
ṁz!e"BKDH""AEIO"m‰4B16

```

Try it online!

Idea from Dennis' answer.
> 0 votes

---
Tags: code-golf, conversion, hexadecimal
---


title: Ambiguous Locations on a Grid

text:
# Question
Title: Ambiguous Locations on a Grid
You have a little robot with four distance sensors. It knows the layout of a room, but it has no sense of orientation other than being able to lock onto the grid orientation. You want to be able to find out where the robot is based on the readings, but it can be ambiguous because of the limited sensors.

## Challenge Explanation

You will be given a room layout and four clockwise distance readings giving the number of cells between you and a wall. There can be walls in the middle of the room and the edges of the grid are also walls. The robot cannot be placed on top of a wall.

Your objective is to list all of the locations within the room that the robot could be in that would give the given readings. Keep in mind that the robot has no sense of orientation (other than being locked to 90 degree angles on the grid- i.e. the robot will never be oriented diagonally or some other skew angle), so a reading of \[1, 2, 3, 4\], for example, is the same as reading \[3, 4, 1, 2\].

## Examples

For these examples, cell coordinates will be given as 0-indexed (x, y) pairs from the top-left cell. Readings will be given in clockwise order in a square bracketed list. Layouts will use pound signs for walls and other characters (usually dots) to represent empty cells.

### Case 1

```
. . . .
. . . .
. . # .
. . . .

```
* \[1, 0, 2, 3\] ==\> (1, 0), (3, 1)
* \[0, 0, 3, 3\] ==\> (0, 0), (3, 0), (0, 3), (3, 3)
* \[2, 1, 1, 0\] ==\> (0, 2), (2, 1)
* \[1, 1, 2, 2\] ==\> (1, 1)

### Case 2

```
# a . # a .
a # . . # a
. . # . . #
# . . # . .
a # . . # a
. a # . a #

```
* \[0, 0, 1, 1\] ==\> every position on the grid that is a dot
* \[1, 0, 0, 0\] ==\> all of the a's on the grid

### Case 3

```
.

```
* \[0, 0, 0, 0\] ==\> (0, 0)

### Case 4

```
. # #
. . .

```
* \[1, 2, 0, 0\] ==\> (0, 1)
* \[0, 1, 2, 0\] ==\> (0, 1)
* \[0, 0, 1, 0\] ==\> (0, 0)
* \[1, 0, 1, 0\] ==\> (1, 1)
* \[0, 1, 0, 1\] ==\> (1, 1)

### Case 5

```
. # . .
. . . .
. . # .
. . . .

```
* \[2, 1, 1, 0\] ==\> (0, 2), (2, 1)
* \[0, 2, 2, 1\] ==\> (1, 1)
* \[1, 0, 2, 2\] ==\> (1, 1)
* \[0, 3, 0, 0\] ==\> (0, 0)
* \[1, 0, 1, 1\] ==\> (1, 2)

## Other Rules

* Input may be in any convenient format. Input is a grid of walls and spaces and a list of four distances in clockwise order.
* Output may either be a list of all cells that satisfy the reading or a modified version of the grid showing which cells satisfy the reading. The exact format of the output doesn't matter as long as it is reasonable and consistent. Valid output formats *include, but are not limited to*:
    + Printing a line for each cell coordinate as an ordered pair
    + Printing the grid with `.`, `#`, and `!` for space, walls, and possible locations, respectively.
    + Returning a list of ordered pairs
    + Returning a list of indexes
    + Returning a list of lists using different values for spaces, walls, and possible locations
    + Return/print a matrix of 0s and 1s, using 1s to represent cells where the reading would occur. (It is not necessary to include walls)
    + Once again, this list is not exhaustive, so other representations are valid as long as they are consistent and show every possible valid location in a grid or list. If you are unsure, leave a comment and I will be happy to clarify.
* You may assume that a reading corresponds to at least one location on the grid.
* You may assume that the input grid is at least 1x1 in size and has at least one empty space.
* You may assume that the input grid is no larger than 256 cells in each dimension.
* You may assume that the input grid is always a perfect rectangle and not jagged.
* There is no penalty or bonus if your program happens to give sane outputs for invalid inputs.
* This is code golf, so shortest code wins.

# Answer
# JavaScript (ES6),  ~~130 128 126~~  125 bytes

Takes input as \\$(m)(l)\\$ where \\$m\\$ is a binary matrix describing the room layout (\\$0\\$ = wall, \\$1\\$ = empty) and \\$l\\$ is the list of distances.

Returns another binary matrix where each valid position is marked with \\$1\\$.

```
m=>l=>m.map((r,y)=>r.map((v,x)=>v&!!([...'3210321'].map(d=>(g=X=>(m[Y+=~-d%2]||0)[X+=(d-2)%2]?1+g(X):0)(x,Y=y))+g).match(l)))

```

Try it online! (with post-processed output for readability)

### Commented

```
m => l =>                         // m[] = layout matrix; l[] = list of distances
  m.map((r, y) =>                 // for each row r[] at position y in m[]:
    r.map((v, x) =>               //   for each cell v at position x in r[];
      v &&                        //     yield 0 if v = 0
      !!(                         //     otherwise, test whether we can find l[] within a
        [...'3210321']            //     list containing twice the results of the sensors
        .map(d =>                 //       for each direction d:
          (g = X => (             //         g = recursive function taking X
              m[Y += ~-d % 2]     //         add dy[d] to Y
              || 0                //         use a dummy object if we're out of the board
            )[X += (d - 2) % 2] ? //         add dx[d] to X; if (m[Y] || 0)[X] is equal to 1:
              1 +                 //           add 1 to the final result
              g(X)                //           and do a recursive call
            :                     //         else:
              0                   //           yield 0 and stop recursion
          )(x, Y = y)             //         initial call to g with X = x and Y = y
        )                         //       end of map() over directions
        + g                       //       coerce the result to a comma-separated string,
                                  //       followed by harmless garbage
      ).match(l)                  //     test whether l[] can be found in this string
                                  //     (l[] is implicitly coerced to a string as well)
    )                             //   end of map() over r[]
  )                               // end of map() over m[]

```
> 3 votes

# Answer
# Python 2, ~~234~~ ~~202~~ ~~200~~ 191 bytes

```
lambda m,a:[(i,j)for j,l in e(m)for i,c in e(l)if('#'<c)*[(''.join(L)[::-1]+'#').find('#')for L in l[:i],zip(*m)[i][:j],l[:i:-1],zip(*m)[i][:j:-1]]in[a[q:]+a[:q]for q in 0,1,2,3]]
e=enumerate

```

Try it online!
> 1 votes

# Answer
# Charcoal, 42 bytes

```
ＰθＦθ¿⁼¶ι⸿¿№Ｅ⁴Ｅ⁴⊖⌕⁺⪫ＫＤ⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#η!ι

```

Try it online! Link is to verbose version of code. Charcoal seems to add some padding to the output for some reason; I'm assuming it's a bug in Charcoal. Explanation:

```
Ｐθ

```

Print the map without moving the cursor.

```
Ｆθ

```

Loop over each character in the map.

```
¿⁼¶ι⸿

```

If it's a newline then move the cursor to the start of the next line.

```
⊖⌕⁺⪫ＫＤ⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#

```

Find the distance to the wall in direction `k+m`.

```
¿№Ｅ⁴Ｅ⁴...η!ι

```

Loop over all four starting directions `k`, peek in all four clockwise directions `m`, and if the result includes the second input then print a `!` otherwise print the current character.
> 1 votes

# Answer
# , 61 bytes

Takes in the grid with infinity `_` for empty tiles, `1` for walls. Returns the grid with either 0 or 1, with the latter indicating a possible position.

```
e."1 2]]0 1|:i.@4|."{_2+((,-)|.=i.2)([:<./(1+|.!.1)^:(<_))"$]

```

Try it online!

Can probably further be golfed by trying other arrangements of the different axes.

* `((,-)|.=i.2)` 4 directions in clockwise order: `0 1, 1 0, 0 _1, _1 0`
* `(…)^:(<_)"$` for each direction and the grid
* `^:(<_)` until the output does not change, return all intermediate steps:
* `1+|.!.1` shift the grid, pushing new 1 in at the borders, incrementing each cell.
* `[:<./` take the minimum of each cell over all steps.
* `_2+` Minus 2. We now have the 4 grids, representing each direction, with the cell representing the distance.
* `i.@4|."{` get all possible rotations of the 4 grids.
* `0 1|:` transpose so that each cell has 4 lists: the possible arrangements of the sensors.
* `e."1 2]]` set cells to 1 if the given sensor input is in the 4 lists, otherwise to 0.
> 0 votes

---
Tags: code-golf, grid
---


title: Tatamibari solver

text:
# Question
Title: Tatamibari solver
## Background

**Tatamibari** is a logic puzzle designed by Nikoli.

A Tatamibari puzzle is played on a rectangular grid with three different kinds of symbols in it: `+`, `-`. and `|`. The solver must partition the grid into rectangular or square regions according to the following rules:

* Every partition must contain exactly one symbol in it.
* A `+` symbol must be contained in a square.
* A `|` symbol must be contained in a rectangle with a greater height than width.
* A `-` symbol must be contained in a rectangle with a greater width than height.
* Four pieces may never share the same corner. (This is how Japanese tatami tiles are usually placed.)

The following is an example puzzle, with a solution:

## Task

Solve the given Tatamibari puzzle.

## Input & output

The input is a 2D grid that represents the given Tatamibari puzzle. Each cell contains one of the four characters: `+`, `-`, `|`, and a character of your choice to represent a non-clue cell. In the test cases, an asterisk `*` is used.

You can choose any suitable output format which can unambiguously represent any valid solution to a Tatamibari puzzle. This includes, but is not limited to: (if in doubt, ask in comments.)

* A list of 4-tuples, where each tuple includes the top index, left index, width and height of a rectangle (or any equivalent representation)
* A numeric grid of the same shape as the input, where each number represents a rectangle
* A list of coordinate sets, where each set includes all the coordinates of the cells in a rectangle

If a puzzle has multiple solutions, you can output any number (one or more) of its valid solutions. The input is guaranteed to have at least one solution.

## Test cases

```
Puzzle:
|-*
*+|
*-*
Solution:
122
134
554
=====
Puzzle:
+***
**|*
*+**
***-
Solution:
1122
1122
3322
3344
======
Puzzle:
|*+*+
*****
****-
***+|
+****
Solution:
12233
12233
44444
55667
55667
=======
Puzzle:
****-**
**-**|*
*|*****
****-**
*******
**+*|**
*****+*
One possible solution:
1122222
1133344
1155544
1155544
6667744
6667788
6667788
===========
Puzzle:
*-****|+**
+*-******|
****+*****
*-******||
**++|*****
+****-|***
-****-**+*
********-*
|*+*+|****
*-*--**+*+
Solution:
1111122334
5666622334
7777822994
7777A2299B
CCDEA2299B
CCFFFFGGHH
IIIIJJGGHH
KLLMMNGGOO
KLLMMNGGPP
QQRRSSSTPP

```

## Rules

Standard rules apply. The shortest code in bytes wins.

# Answer
# Python 2, ~~417~~ ~~374~~ 366 bytes

Input is list of lines, `~` for non-clue. Outputs a single solution to stderr in the format `(x_start, width, y_start, height)`.

```
R=range
k=input()
X,Y=len(k[0]),len(k)
W,H=R(X),R(Y)
Q=[[]]
for q in Q:C=[(x,y)for(a,b,c,d)in q for x in(a,a+b)for y in(c,c+d)];max(map(C.count,C+W))<4>0<all(sum(w>x-s>-1<y-t<h<[c for r in k[t:t+h]for c in r[s:s+w]if'~'>c]==['+|-'[cmp(h,w)]]for(s,w,t,h)in q)==1for x in W for y in H)>exit(q);Q+=[q+[(s,w+1,t,h+1)]for s in W for w in R(X-s)for t in H for h in R(Y-t)]

```

Try it online! This is too inefficient for the suggested test cases.

---

## Ungolfed

```
grid = input()
total_width = len(grid[0])
total_height = len(grid)

partitions = [[]]

for partition in partitions:
    # list the corners of all rectangles in the current partition
    corners = [(x, y)
               for (start_x, width, start_y, height) in partition
               for x in (start_x, start_x + width)
               for y in (start_y, start_y + height)]
    # if no corners appears more than three times ...
    if corners != [] and max(map(corners.count, corners)) < 4:
        # .. and all fields are covered by a single rectangle ...
        if all(
                sum(width > x - start_x > -1 < y - start_y < height
                    for (start_x, width, start_y, height) in partition) == 1
                for x in range(total_width)
                for y in range(total_height)):
            # ... and all rectangles contain a single non-~
            # symbol that matches their shape:
            if all(
                [char for row in grid[start_y: start_y + height]
                    for char in row[start_x:start_x + width] if '~' > char]
                == ['+|-'[cmp(height, width)]]
                    for (start_x, width, start_y, height) in partition):
                # output the current partition and stop the program
                exit(partition)

    # append each possible rectangle in the grid to the current partition,
    # and add each new partition to the list of partitions.
    partitions += [partition + [(start_x, width + 1, start_y, height + 1)]
                   for start_x in range(total_width)
                   for width in range(total_width - start_x)
                   for start_y in range(total_height)
                   for height in range(total_height - start_y)]

```

Try it online!
> 5 votes

# Answer
# , 193 bytes

Returns all possible solutions as grids with -1, -2 … indicating rooms. There is room for improvements, but the `((((((` started to confuse me. :-)

```
[:(#~0=0(e.,)"2])'*+-|'([:,/(([(<./@,@:<:@[`]`[}{.<@:+"1,/@(#:i.)@{:)"2((((({(0,=/,</,>/)@$)~0({.*(1=#)*0<{.)@-.~,);.0~*[:*/0<1{])"2#]){.([,:-~)"1/>:))[(#~0<:,)~,/@(#:i.)@$)"2)^:(1#.*@,)@,:@i.]

```

Try it online! For the larger test cases I provided `ff` that has a filter `[:(#~1*@#.|@,"2)` for intermediate steps, where empty grids got added because of padding.

### How it works

* `'*+-|' … i.]` Map `*+-|` to `0 1 2 3`.
* `,/@(#:i.)@$` From all the tiles
* `[(#~0<:,)~` that aren't part of a room,
* `{.([,:-~)"1/>:` starting from the most top-left tile, that isn't part of a room yet, try every possible rectangle spanning down-right.
* `…"2#]` For that rectangle to be valid for the next step,
* `[:*/0<1{]` 0.) it must have a positive size in each dimension
* `0({.*(1=#)*0<{.)@-.~,` 1.) no tile must be part of a room, 2.) exactly one symbol must be within the rectangle,
* `(({(0,=/,</,>/)@$)~` 3.) the dimension of the rectangle fulfill the constraint of the symbol.
* `(<./@,@:<:@[`\]`[}{.<@:+"1,/@(#:i.)@{:)"2` For every valid rectangle, copy the current grid and place the next room.
* `^:(1#.*@,)@,:` We need to do this `n` times, where `n` is the number of symbols.
* `[:(#~0=0(e.,)"2])` After this there might be grids that have `n` rooms, but still empty tiles; those must be filtered out.
> 2 votes

---
Tags: code-golf, grid, puzzle-solver
---


title: Recursive 2x2 determinant

text:
# Question
Title: Recursive 2x2 determinant
The determinant of a 2 by 2 matrix

```
a b
c d

```

is given by `ad - bc`.

Given a matrix of digits with dimensions 2n by 2n, n ≥ 1, output the result obtained by recursively computing the determinant of each 2 by 2 sub-block until we reach a single number.

For example, given the input

```
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

```

After one step, we obtain:

```
(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

```

And iterating once more, we get:

```
(22*-57 - 22*8) = -1430

```

Hence, the output should be `-1430`.

### Rules

* The elements of the matrix will always be single digit integers, i.e. 0 to 9.
* You may take input in any convenient list or string format, as long as no preprocessing of data is done. Since the matrix is always square, you may take input as a single 1D list instead of a 2D list if you wish.
* Input can be via function input, STDIN, command-line argument or closest alternative.
* Output should be a single integer to function output, STDOUT or closest alternative. You may not output the single integer in a list or matrix.
* You may use builtin determinant and matrix manipulation methods if your language happens to support them.
* Your algorithm must work in theory for any valid input.
* Standard rules apply.

### Test cases

The following test cases are given as Python-style lists:

```
[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

```

*(Thanks to @MartinBüttner for help with this challenge)*

# Answer
> 8 votes
# J, ~~21~~ 25 bytes

```
0{0{(_2(_2-/ .*\|:)\])^:_

```

Usage:

```
   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

```

At every step we cut up the matrix to 2-by-2's and compute each ones determinant resulting in the next step's input matrix. We repeat this process until the result doesn't change (the final element is the determinant itself). We convert the final result to a scalar with `0{0{`.

Try it online here.

# Answer
> 5 votes
# Mathematica, ~~52~~ 40 bytes

*Thanks to Martin Büttner for saving 12 bytes.*

```
Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&

```

---

**Explanation**

`BlockMap[f,expr,n]` split `expr` into sublists of size `n` and map `f` on every sublists. `BlockMap[Det,#,{2,2}]&` split the input array into 2\*2 blocks and calculate their determinants.

---

**Test case**

```
%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)

```

# Answer
> 3 votes
# Jelly, ~~20~~ 17 bytes

```
s€2s2U×¥/€ḅ-µL¡SS

```

Try it online! or verify all test cases at once.

### How it works

```
s€2s2U×¥/€ḅ-µL¡SS  Main link. Input: M (matrix)

s€2                Split each row of M into pairs.
   s2              Split the result into pairs of rows.
        /€         Reduce each pair...
       ¥             by applying the following, dyadic chain:
     U                 Reverse each pair of the left argument (1st row).
      ×                Multiply element-wise with the right argument (2nd row).
          ḅ-       Convert each resulting pair from base -1 to integer.
                   This maps [a, b] -> b - a.
            µ      Turn the previous links into a monadic chain. Begin a new one.
             L     Yield the length of the input.
              ¡    Execute the previous chain L times.
                   log2(L) times would do, but who's counting?
               SS  Sum twice to turn the resulting 1x1 matrix into a scalar.

```

# Answer
> 2 votes
# MATL, ~~30~~ 26 bytes

```
`tnX^teHHhZC2Ih2#Y)pwp-tnq

```

Input is a 2D array with rows separated by `;`, that is,

```
[3 1 4 1; 5 9 2 6; 5 3 5 8; 9 7 9 3]

```

**Try it online!**

```
`             % do...while loop
  tnX^te      %   reshape into square matrix. Implicitly asks for input the first time
  HHhZC       %   transform each 2x2 block into a column
  2Ih2#Y)     %   push matrix with rows 2,3, and also matrix with remaining rows (1,4)
  pwp-        %   multiplications and subtraction to compute the 2x2 determinants
  tnq         %   condition of do...while loop: is number of elements greater than 1?
              % implicitly end loop
              % implicitly display

```

# Answer
> 2 votes
# Haskell, ~~93~~ 86 bytes

EDIT: Thanks to @Laikoni for shortening this a whole 7 bytes!

```
f[[a,b],[c,d]]=a*d-b*c
f m|let l=[take,drop]<*>[div(length m)2]=f[f.($b<$>m)<$>l|b<-l]

```

I didn't know you could put a let statement before the = and I've never gotten used to those monad operators. Thanks again @Laikoni

Old version:

```
f[[a,b],[c,d]]=a*d-b*c
f m=f[[f$a$map b m|a<-l]|b<-l]where h=length m`div`2;l=[take h,drop h]

```

Try it online!

This is a function that recurs on itself in two different ways. First the pattern matching catches the the base case: a 2x2 matrix and it does the calculation. I use this to do the calculation in the recursive case by calling the function with a 2x2 matrix I generate that has the recursive solutions in it. That matrix is generated by iterating twice over an array of functions that each chop a list in half. I apply it to rows with a simple call and apply it to columns using `map`.

# Answer
> 1 votes
# Python, 166 bytes

```
def f(m):l=len(m)/2;g=lambda x,y:[(s[:l],s[l:])[x]for s in(m[:l],m[l:])[y]];return f(g(0,0))*f(g(1,1))-f(g(0,1))*f(g(1,0)) if l>1 else m[0][0]*m[1][1]-m[1][0]*m[0][1]

```

This passes all the test cases provided. m has to be a 2D array (like in the test cases), g selects the sub matrix.

# Answer
> 1 votes
# Pyth, 26

```
M-F*VG_HhhumgMCcR2dcG2llQQ

```

Test Suite

This has two parts: `M-F*VG_H` redefines the function `g` to calculate the determinant of a two by two matrix. This saves bytes even though we only use it once because it unpacks the two rows.

The other part is a large reduce statement that we call `log_2( len( input() ) )` times. Unfortunately, performing a step in the reduction on a 1 by 1 matrix causes the result to be wrapped in a list, so we don't get a fixed point. The reduce is mostly just splitting up the matrix to get 2 by 2 matrices and then applying `g`.

# Answer
> 1 votes
# Perl 5, 120 + 1 (`-a`) = 121 bytes

```
while($#F){@r=();for$i(@o=0..($l=sqrt@F)/2-1){push@r,$F[$k=$i*$l*2+2*$_]*$F[$k+$l+1]-$F[$k+$l]*$F[$k+1]for@o}@F=@r}say@F

```

Try it online!

Takes the input as a list of space separated numbers.

# Answer
> 0 votes
## ES6, 91 bytes

```
(a,x=0,y=0,w=a.length)=>(w>>=1)?f(a,x,y,w)*f(a,x+w,y+w,w)-f(a,x,y+w,w)*f(a,x+w,y,w):a[x][y]

```

Straightforward recursive solution.

# Answer
> 0 votes
# , 111 bytes

```
f=function(m)"if"((n=nrow(m))-2,f(matrix(c(f(m[x<-1:(n/2),x]),f(m[y<-x+n/2,x]),f(m[x,y]),f(m[y,y])),2)),det(m))

```

Try it online!

Takes input as an R matrix (which is converted by the function in the header).

# Answer
> 0 votes
# Groovy, ~~221~~ 189 bytes (At this point, could've used Java)

```
f={x->b=x.size();c=b/2-1;a=(0..c).collect{i->(0..c).collect{j->z=x.toList().subList(i*2,i*2+2).collect{it.toList().subList(j*2,j*2+2)};z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

```

---

***Old crappy version, which might as well be Java (221 bytes):***

```
f={x->b=x.size();a=new int[b/2][b/2];for(i=0;i<b-1;i+=2){for(j=0;j<b-1;j+=2){z=x.toList().subList(i,i+2).collect{it.toList().subList(j,j+2)};a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

```

Ungolfed code:

```
f=
{x->
  b=x.size();
  int[][]a=new int[b/2][b/2];
  for(i=0;i<b-1;i+=2) {
    for(j=0;j<b-1;j+=2) {
      z=x.toList().subList(i,i+2).collect{
        it.toList().subList(j,j+2)
      };
      a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];
    }
  }
  a.size()==1
    ?
      a:f(a)
}

```

# Answer
> 0 votes
# Husk, 25 bytes

```
ω(m(moF`-Fz*C2z*:1İ_)TmC2

```

Try it online!

The testcases in this one are great.

---
Tags: code-golf, arithmetic, linear-algebra, matrix
---


title: Sum the First n Even Fibonacci Numbers

text:
# Question
Title: Sum the First n Even Fibonacci Numbers
There seems not to be a contest for this one yet.

The task is simple. Add the first `n` numbers of the Fibonacci sequence that are even and output the result.

This is given by OEIS A099919, except that sequence is shifted by one, starting with `fib(1) = 0` instead of `fib(1) = 1`.

This is code golf. Lowest byte count wins.

# Examples

```
n sum
1 0
2 2
3 10
4 44
5 188
6 798
7 3382
8 14328
9 60696

```

---

Related

# Answer
# Oasis, ~~8~~ ~~7~~ 5 bytes

*1 byte saved thanks to @ETHProductions and 2 more saved thanks to @Adnan!*

```
zc»+U

```

Try it online!

### Explanation:

This uses the same recurrence formula as my MATL answer.
> 10 votes

# Answer
## Python, 33 bytes

```
c=2+5**.5
lambda n:(7-c)*c**n//20

```

Try it online

Magic formula!
> 17 votes

# Answer
## JavaScript (ES6), 27 bytes

```
f=x=>x>1&&4*f(x-1)+f(x-2)+2

```

Recursion to the rescue! This uses one of the formulas on the OEIS page:

> f(n \< 1) = 0, f(n) = 4\*a(n+1)+a(n)+2

(but shifted by one because the challenge shifts it by one)
> 7 votes

# Answer
# Python 2, 35 bytes

```
f=lambda n:n/2and 4*f(n-1)+f(n-2)+2

```

Try it online!
> 7 votes

# Answer
# Actually, 6 bytes

```
r3*♂FΣ

```

Try it online!

Explanation:

Every third Fibonacci number (starting from `F_0 = 0`) is even. Thus, the first `n` even Fibonacci numbers are `F_{i*3}` for `i` in `[0, n)`.

```
r3*♂FΣ
r       [0, n)
 3*     multiply each element by 3
   ♂F   retrieve the corresponding element in the Fibonacci sequence
     Σ  sum

```
> 7 votes

# Answer
## Pyke, 6 bytes

```
3m*.bs

```

Try it here!

```
3m*    -   map(i*3, range(input))
   .b  -  map(nth_fib, ^)
     s - sum(^)

```
> 6 votes

# Answer
# Perl 6,  ~~38 35~~  32 bytes

```
{[+] grep(*%%2,(1,&[+]...*))[^($_-1)]}

```

Try it

```
{[+] grep(*%%2,(0,1,*+*...*))[^$_]}

```

Try it

```
{[+] (0,1,*+*...*)[3,6...^$_*3]}

```

Try it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  [+]                       # reduce with ｢&infix:<+>｣

    ( 0, 1, * + * ... * )\  # fibonacci sequence with leading 0

    [ 3, 6 ...^ $_ * 3 ]    # every 3rd value up to
                            # and excluding the value indexed by
                            # the input times 3

}

```
> 4 votes

# Answer
## Mathematica, 27 21 bytes

*Thanks to xnor for pointing out an alternate formula, alephalpha for correcting for starting index*

```
Fibonacci[3#-1]/2-.5&

```
> 3 votes

# Answer
# Octave, ~~36~~ ~~35~~ 33 bytes

```
@(n)filter(2,'FAD'-69,(1:n)>1)(n)

```

Try it online!

### Explanation

This anonymous function implements the difference equation `a(n) = 4*a(n-1)+a(n-2)+2` as a recursive filter:

> `Y = filter(B,A,X)` filters the data in vector `X` with the filter described by vectors `A` and `B` to create the filtered data `Y`. The filter is a "Direct Form II Transposed" implementation of the standard difference equation:
>
> `a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb) - a(2)*y(n-1) - ... - a(na+1)*y(n-na)`

In our case `A = [1 -4 -1]`, `B = 2`, and the input `x` should be a vector of ones, with the result appearing as the last entry of the output `y`. However, we set to `0` the first value of the input so that an initial `0` appears in the output, as required.

`'FAD'-69` is just a shorter way to produce the coefficient vector `A = [1 -4 -1]`; and `(1:n)>1` produces the input vector `x = [0 1 1 ... 1]`.
> 3 votes

# Answer
# dc, ~~25~~ 22 bytes

```
9k5v1+2/3?*1-^5v/0k2/p

```

Try it online!

Or save the program in a file and run it by typing

```
dc -f *filename*

```

The program accepts a non-negative integer *n* on stdin, and it outputs the sum of the first *n* even Fibonacci numbers on stdout. (The Fibonacci sequence is taken to start with 0, as per the OP's examples.)

---

This program uses the formula (F(3n-1)-1)/2 for the sum of the first n even Fibonacci numbers, where F is the usual Fibonacci function, given by F(0) = 0, F(1) = 1, F(n) = F(n-2) + F(n-1) for n \>= 2.

---

dc is a stack-based calculator. Here's a detailed explanation:

```
9k  # Sets the precision to 9 decimal places (which is more than sufficient).

5v  # Push the square root of 5

1+  # Add 1 to the number at the top of the stack.

2/  # Divide the number at the top of the stack by 2.

```

At this point, the number (1+sqrt(5))/2 is at the top of the stack.

```
3   # Push 3 on top of the stack.

?   # Read a number from stdin, and push it.

\*  # Pop two numbers from the stack, multiply them, and push the product

1-  # Subtract 1 from the number at the top of the stack.

```

At this point, 3n-1 is at the top of the stack (where n is the input), and (1+sqrt(5))/2 is second from the top.

```
^   # Pop two numbers from the stack (x, then y), compute the power y^x, and push that back on the stack.

5v/ # Divide the top of the stack by sqrt(5).

```

At this point, the number at the top of the stack is (((1+sqrt(5))/2)^(3n-1))/sqrt(5). The closest integer to this number is F(3n-1). Note that F(3n-1) is always an odd number.

```
0k # Change precision to 0 decimal places.

2/ # Divide the top of the stack by 2, truncating to an integer.

p # Print the top of the stack on stdout.

```
> 3 votes

# Answer
# Forth (gforth), 38 bytes

```
: f 1 1 rot 1 ?do tuck 4 * + loop 2/ ;

```

Try it online!

Wins over existing Forth answer by porting this formula:

$$ G(0)=G(1)=1, G(n+2)=4G(n+1)+G(n) \\ a(n) = \left\lfloor \frac{G(n)}2 \right\rfloor $$

```
: f ( n -- a_n )  \ Take single number n and return a_n
  1 1 rot 1       \ g0 g1 n 1
  ?do             \ loop n-1 times
    tuck 4 * +    \ gn-1 gn -> gn gn+1=4gn+gn-1
  loop            \ end loop; top is gn
  2/              \ an = gn/2 (floor division)
;

```
> 3 votes

# Answer
# MATL, ~~15~~ 14 bytes

```
OOi:"t4*b+2+]x

```

Try it online!

### Explanation

This uses one of the recurrence formulas from OEIS:

> a(n) = 4\*a(n-1)+a(n-2)+2

For input *N* the code iterates *N* times, which is 2 more times than necessary. This is compensated for by setting `0`, `0` (instead of `0`, `2`) as initial values, and by deleting the last obtained value and displaying the previous one.

```
OO      % Push two zeros as initial values of a(n-2), a(n-1)
i       % Input N
:"      % Do this N times
  t     %   Duplicate a(n-1)
  4*    %   Multiply by 4
  b+    %   Bubble up a(n-2) and add to 4*a(n-1)
  2+    %   Add 2. Now we have 4*a(n-1)+a(n-2)+2 as a(n), on top of a(n-1)
]       % End
x       % Delete last value, a(n). Implicitly display the remaining value, a(n-1)

```
> 2 votes

# Answer
## Batch, 80 bytes

```
@set/at=x=0,y=1
@for /l %%i in (2,1,%1)do @set/az=x+y,y=z+x,t+=x=y+z
@echo %t%

```

Uses the fact that every third Fibonacci number is even, and just calculates them three at a time (calculating more than one at a time is actually easier as you don't have to swap values around). I tried the `(Fibonacci(3*n+2)-1)/2` formulation but it's actually a few bytes longer (`t+=` turns out to be quite efficient in terms of code size).
> 2 votes

# Answer
# C, 82 38 36 bytes

*2 bytes saved thanks to @BrainSteel*

The formulas at the OEIS page made it much shorter:

```
a(n){return--n<1?0:4*a(n)+a(n-1)+2;}

```

Try it online!

82 bytes:

```
x,s,p,n,c;f(N){s=0;p=n=1;c=2;while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

```

The first version is 75 bytes but the function is not reusable, unless you always call `f` with greater `N` than the previous call :-)

```
x,s,p=1,n=1,c=2;f(N){while(n<N){if(~c&1)s+=c,n++;x=p+c;p=c;c=x;}return s;}

```

My first answer here. Didn't check any other answers nor the OEIS. I guess there are a few tricks that I can apply to make it shorter :-)
> 2 votes

# Answer
# APL (Dyalog Unicode), 22 21 bytes

-1 byte thanks to Adám

```
(2+5*.5)∘(⌊20÷⍨*×7-⊣)

```

Try it online!

Uses xnor's magic formula

```
(2+5*.5)∘(⌊20÷⍨*×7-⊣)

(2+5*.5)               ⍝ constant c
        ∘(           ) ⍝ joined to
                 7-⊣  ⍝ 7-c
                ×      ⍝ multiplied by
               *       ⍝ input^c
           20÷⍨        ⍝ all over 20
          ⌊            ⍝ floor

```

# Or with APL (Dyalog Extended), 19 bytes

(Thanks to Adám)

```
(2+√5)∘(⌊20÷⍨*×7-⊣)

```

Try it online!
> 2 votes

# Answer
# APL (Dyalog Unicode), 16 bytesSBCS

```
⌊⊃⌽(4∘⊥,⊃)⍣⎕÷2 2

```

Try it online!

A full program.

### How it works: the math

Uses `a(n) = (Fibonacci(3*n + 2) - 1)/2` from the OEIS page, but we have offset 1 in `a(n)`, so the actual formula is:

$$ a(n) = \frac{F(3 n - 1) - 1}{2} = \Bigl\lfloor \frac{F(3 n - 1)}{2} \Bigr\rfloor $$

And using \\$ F(2) = F(-1) = 1 \\$ and \\$ F(n+3) = 4F(n) + F(n-3) \\$, we define a derived sequence \\$ G(n) \\$ such that

$$ G(0)=G(1)=\frac12, G(n+2)=4G(n+1)+G(n) $$

Then the desired value is \\$ a(n) = \lfloor G(n) \rfloor \\$.

### How it works: the code

```
⌊⊃⌽(4∘⊥,⊃)⍣⎕÷2 2  ⍝ Input: n
            ÷2 2  ⍝ 2-element vector [.5 .5] i.e. [G(1) G(0)]
   (4∘⊥,⊃)⍣⎕      ⍝ Derive [G(x+2) G(x+1)] from [G(x+1) G(x)] n times:
    4∘⊥           ⍝   G(x+2) = 4×G(x+1) + G(x)
        ⊃         ⍝   G(x+1) as first element of the vector
       ,          ⍝   Concatenate
 ⊃⌽               ⍝ Get the last element of the result vector, i.e. G(n)
⌊                 ⍝ Floor

```
> 2 votes

# Answer
## Mathematica, ~~32~~ 27 bytes

```
Fibonacci[3Input[]-1]/2-1/2

```

*Credit to **xnor**. Saved 5 bytes thanks to JungHwan Min.*
> 1 votes

# Answer
## Haskell (~~32~~ 31 bytes)

Saved one byte thanks to @ChristianSievers.

Using the formula given in OEIS: `a(n) = 4*a(n-1)+a(n-2)+2, n>1` by Gary Detlefs

`a n|n>1=4*a(n-1)+a(n-2)+2|n<2=0`
> 1 votes

# Answer
## Japt, 10 bytes

```
Uo@MgX*3Ãx

```

Try it online!

Thanks ETHproductions :)
> 1 votes

# Answer
# R, ~~42~~ 41 bytes

```
sum(DescTools::Fibonacci(3*(scan():2-1)))

```

> `scan()` : take `n` from stdin.
>
> `scan():2-1` : generate integers from `n` to `2`, decrement by `1`, yielding `n-1` through `1`.
>
> `3*(scan():2-1)` : multiply by 3, as every third fibonacci number is even.
>
> `DescTools::Fibonacci(3*(scan():2-1))` : Return these fibonacci numbers (i.e. `3` through `(n-1)*3`).
>
> `sum(DescTools::Fibonacci(3*(scan():2-1)))` : Sum the result.

Previously, I had this uninteresting solution using one of the formulae from OEIS:

```
a=function(n)`if`(n<2,0,4*a(n-1)+a(n-2)+2)

```
> 1 votes

# Answer
# PHP, ~~73~~ 70 bytes

```
for(${0}=1;$i++<$argv[1];$$x=${0}+${1})${$x^=1}&1?$i--:$s+=$$x;echo$s;

```

showcasing variable variables. O(n). Run with `-nr`.

**breakdown**

```
for(${0}=1;         # init first two fibonaccis (${1}=NULL evaluates to 0 in addition)
                    # the loop will switch between $0 and $1 as target.
    $i++<$argv[1];  # loop until $i reaches input
    $$x=${0}+${1}       # 3. generate next Fibonacci
)
    ${$x^=1}            # 1. toggle index (NULL => 1 => 0 => 1 ...)
    &1?$i--             # 2. if current Fibonacci is odd, undo increment
    :$s+=$$x;           #    else add Fibonacci to sum
echo$s;             # print result

```

Numbers are perfectly valid variable names in PHP.
But, for the literals, they require braces; i.e. `${0}`, not `$0`.

**36 bytes, O(1)**

```
<?=(7-$c=2+5**.5)*$c**$argv[1]/20|0;

```

port of xnor´s answer
> 1 votes

# Answer
# R, 42 bytes

Non-recursive solution, as contrast to the earlier solution by @rtrunbull here.

```
for(i in 1:scan())F=F+gmp::fibnum(3*i-3);F

```

Uses the property that each third value of the Fibonacci sequence is even. Also abuses the fact that `F` is by default defined as `FALSE=0`, allowing it as a basis to add the values to.
> 1 votes

# Answer
# Forth (gforth), 47 bytes

```
: f 3 * 1- 0 1 rot 0 do tuck + loop d>s 1- 2/ ;

```

Try it online!

Uses the first formula for OEIS `a(n) = (Fibonacci(3*n + 2) - 1)/2`, since the code for Fibonacci is relatively small in forth.

```
: f              \ start a new word definition
  3 * 1-         \ multiply by 3 and subtract 1 (simplified form of 3*(n-1) + 2 )
  0 1 rot 0      \ create starting Fibonacci values and set up loop parameters
  do tuck + loop \ Fibonacci code - iteratively copy top value add top 2 stack values
  d>s            \ drop the top stack value
  1- 2/          \ subtract 1 and divide result by 2
;                \ end word definition

```
> 1 votes

# Answer
# Husk, 8 bytes

```
Σ↑Θnİ0İf

```

Try it online!

painfully slow due to intersecting two infinite lists.
> 1 votes

# Answer
# PARI/GP, 21 bytes

```
n->fibonacci(3*n-1)\2

```

`\` is the integer quotient.
> 0 votes

# Answer
# Excel (Version 1911), 119 Bytes

Using iterative calculations (Maximum iteration 1024)

```
A1 'Input
B1 =IF(B1=4^5,1,B1+1)
C1 =SEQUENCE(A1*3-1)-1
D1 =IF(B1=1,N(C1#>0),IF(C1#=B1,SUM(INDEX(D1#,B1-{0,1})),D1#))
E1 =SUM(D1#*(MOD(D1#,2)=0)) 'Output

```

Tests
> 0 votes

# Answer
# GolfScript, 46 bytes

```
(:m;5 2 -1??:i 3*5\- 2i-m?*3i*5+2i+m?*+-10+20/

```

Ignore the floating point, TIO isn't perfect.

Yeah, yeah. I cheated. This is just a fancy arithmetic equation to calculate the result. Works in O(1) time, though, assuming a^n can be calculated in O(1) time, which might not be true.

```
(:m;5 2 -1??:i 3*5\- 2i-m?*3i*5+2i+m?*+-10+20/ #Sum the first n even F
(:m;                                           #Set m to our input minus one, pop the value from the list.
    5 2 -1??:i                                 #Set i to sqrt(5), but don't pop it since we're gonna use it (saves 1 byte)
               3*5\-                           #5-3sqrt(5)
                     2i-m?                     #[2-sqrt(5)]^m
                          *                    #Multiply those two together
                           3i*5+2i+m?*         #Same as the above lines, but + instead of -.
                                      +        #Add the left part with the right part
                                       -10+    #Add -10 (-10+20/ and 10- 20/ are the same size)
                                           20/ #Divide by twenty.

```

Try it online!
> 0 votes

# Answer
# GolfScript, 15 bytes

```
0.@{.4*@2++}\*;

```

This one actually does the "operation" using a neat little trick I found. The sum is actually just a 0, 0 leading sequence, with a(n) = 4a(n-1) + a(n-2) + 2. So I do that.

```
0.@{.4*@2++}\*; #Print the sum of the first n even F
0.              #Add two 0s to the stack. [n 0 0]
  @             #Bring the n up front. [0 0 n]
   {       }    #A block of "do something" [0 0 n {}]
   {       }\   #Bring n to the front again [0 0 {} n]
   {       } *  #Perform the block n times on the stack below it [0 0]
   {.      }    #Duplicate our top element (a[n-1] a[n-1])
   { 4*    }    #Multiply the dupe by 4 (a[n-1] 4a[n-1])
   {   @   }    #Bring up our bottom element (a[n-1] 4a[n-1] a[n-2])
   {    2++}    #4a[n-1]+a[n-2]+2 = a[n]
   {       }    #Stack is now a[n-1] a[n], so we dop the loop until our n is right!
              ; #The stack has a[n-1] a[n], but our "n" in question is 1 too high
                #So we pop the top element, leaving a[n-1], W5.

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 7 bytes

```
L<3*ÅfO

```

Try it online!
> 0 votes

# Answer
# Jelly, 6 bytes

```
Ḷ×3ÆḞS

```

Try it online!

Uses the formula

$$a(n) = \sum\_{i=0}^{n-1}f(3i)$$

where \\$f(n)\\$ is the \\$n\\$-th Fibonacci number

## How it works

```
Ḷ×3ÆḞS - Main link. Take n on the left
Ḷ      - [0, 1, 2, ..., n-1]
 ×3    - [0, 3, 6, ..., 3n-3]
   ÆḞ  - n'th Fibonacci number for each
     S - Sum

```
> 0 votes

# Answer
# CJam, 15 bytes

```
1_{_4*@+}qi*;2/

```

Try it online!

Uses Bubbler's wonderful formula.
> 0 votes

---
Tags: code-golf, sequence, number-theory, fibonacci
---