title: I like Pythagorean trees

text:
# Question
Title: I like Pythagorean trees
...so this is a challenge to make me a tree.

Produce a program or function called tree which takes a single integer argument, N and draws a Pythagorean Tree N levels deep, where level 0 is just the trunk.

Each junction of the tree should place the vertex of the triangle at a random point on the perimeter (this point should be uniformly distributed over at least 5 equally spaced points, or uniformly over the whole semicircle).

Optionally your tree may be 3d, be colourful, or be lit according to the time of day. However, this is code-golf, so the smallest file wins.

EDIT: I'll shut the contest and accept the smallest answer when it's a week old

# Answer
> 15 votes
## Mathematica, ~~246~~ ~~234~~ 221 characters

```
g[n_,s_:1]:={p=RandomReal[q=Pi/2],r=##~Rotate~(o={0,0})&,t=Translate}~With~If[n<0,{},Join[#~t~{0,s}&/@(#~r~p&)/@g[n-1,s*Cos@p],t[#,s{Cos@p^2,1+Sin[2p]/2}]&/@(r[#,p-q]&)/@g[n-1,s*Sin@p],{Rectangle[o,o+s]}]]
f=Graphics@g@#&

```

This is certainly not the most elegant/shortest way to do this.

Usage: `f[8]`

And here are example outputs for `f[6]` and `f[10]` respectively.

Somewhat ungolfed:

```
g[n_, s_:1] := With[{p},
  r = Rotate;
  t = Translate;
  p = RandomReal[q = Pi/2];
  If[n < 0, {},
   Join[
    (t[#, {0, s}] &) /@ (r[#, p, {0, 0}] &) /@ g[n - 1, s*Cos[p]],
    (t[#, s {Cos[p]^2, 1 + Sin[2 p]/2}] &) /@ (r[#, p - q, {0, 0}] &) /@
       g[n - 1, s*Sin[p]],
    {Rectangle[{0, 0}, {s, s}]}
    ]
   ]
  ]
f = Graphics@g[#] &

```

# Answer
> 21 votes
## CFDG, 134 characters

This one isn't exactly valid, because you cannot limit the recursion depth. But the problem just calls for a solution in this one. :)

```
startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5]t[trans 0 1 c(w) d(w)]t[trans c(w) d(w) 1 1]}

```

The results look something like this

For another 46 characters (**180 characters** in total), you can even colour it in:

```
startshape t
c(q)=cos(q/2)^2
d(q)=1+sin(q)/2
p=acos(-1)
shape t{w=rand(p)
SQUARE[x .5 .5 h 25 sat 1 b .2]t[trans 0 1 c(w) d(w) b .08 .8 h 2.2]t[trans c(w) d(w) 1 1 b .08 .8 h 2.2]}

```

# Answer
> 5 votes
## Mathematica, 122 characters

```
Graphics[Polygon/@ReIm@NestList[Join@@({##3}+Cos[t=Random[]Pi/2]E^(I t){I Tan@t(#2-{##}),{##}-#}&)@@@#&,{{0,1,1+I,I}},#]]&

```

Ungolfed version:

```
Clear["`*"];
next=Compile[{{z,_Complex,1},t},{z[[4]]-E^(I t) (z[[1]]-z) Cos[t],z[[3]]+I E^(I t) (z[[2]]-z) Sin[t]},RuntimeAttributes->{Listable}];
n=15;
list=ReIm@NestList[next[#,Random[]Pi/2]&,N@{{0,1,1+I,I}},n];
poly=MapIndexed[With[{i=Tr@#2},{ColorData["Rainbow",i/(n+1)],Polygon@Flatten[#,i-1]}]&,list];
Graphics[{Antialiasing->True,poly},PlotRange->{{-7,7},{-1,10}},ImageSize->Large,Background->Black]

```

3D version, refer to https://mathematica.stackexchange.com/questions/213727/how-to-draw-a-pythagoras-tree-like-this/213827#213827, render by POV-Ray

# Answer
> 4 votes
# Coffeescript ~~377B~~ 352B

I feel dirty writing coffeescript but I can't find a decent drawing package for python3 :-/

```
Q=(n)->X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=400;M=Math;T=[[175,400,50,i=0]];S=M.sin;C=M.cos;while [x,y,l,a]=T[i++]
 X.save();X.translate x,y;X.rotate -a;X.fillRect 0,-l,l,l;X.restore();T.push [e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2] if i<2**n

```

# Javascript ~~393B~~ 385B

Slightly prettier in javascript and I'm much happier with the for-loop but without the \[x,y,z\]=A syntax I just can't make it short enough to beat coffeescript

```
function Q(n){X=(D=document).body.appendChild(C=D.createElement('Canvas')).getContext('2d');C.width=C.height=600;M=Math;T=[[275,400,50,i=0]];while(A=T[i++]){X.save();X.translate(x=A[0],y=A[1]);X.rotate(-(a=A[3]));X.fillRect(0,-(l=A[2]),l,l);X.restore();S=M.sin;C=M.cos;i<M.pow(2,n)&&T.push([e=x-l*S(a),f=y-l*C(a),g=l*C(b=M.random()*M.PI/2),d=a+b],[e+g*C(d),f-g*S(d),l*S(b),d-M.PI/2])}}

```

Got to say I'm a bit galled this is almost twice as long as the mathematica solution :-/ see it in action: http://jsfiddle.net/FK2NX/3/

# Answer
> 4 votes
## Postscript, ~~322~~ 270

**Edit:** It appears that `realtime` can't be used as proper random generator seed. Therefore, we'll use environment variable for this purpose and run the program like that:

```
gs -c 20 $RANDOM -f tree.ps

```

or

```
gswin32c -c 20 %RANDOM% -f tree.ps

```

Now our trees are less predictable. 14 bytes are added to total count. Other changes: 1) Program argument is now passed on command line. 2) No explicit iteration counter - stack size serves for this purpose (left branch rotation angle is stored on stack, to draw right branch, later). 3) There's no named variable for required depth - stack size is its offset, on stack. It's left there on exit, i.e. it is not consumed.

```
srand
250 99 translate
50 50 scale
/f{
    count
    dup index div dup 1 le{
        0 exch 0 setrgbcolor
        0 0 1 1 rectfill
        0 1 translate
        rand 5 mod 1 add 15 mul
        gsave
        dup rotate
        dup cos dup scale
        f
        grestore
        dup cos dup dup mul
        exch 2 index sin mul translate
        dup 90 sub rotate
        sin dup scale 1
        f
        pop
    }{pop}ifelse
}def
f

```

I think it's pretty obvious - graphics state is prepared and `f` procedure is called recursively for each consecutive level of depth, twice - for 'left' and 'right' branches. Working with rectangle of `1x1` size (see original scale) saves the trouble of multiplying by side length. Angle of rotation of left branch is randomized - one of 5 random equally spaced divisions is used - I think it prevents possible ugly cases for uniform randomness.

It might be slow for required depth of more than 20 or so.

Next is golfed version, using ASCII-encoded binary tokens (see luser droog's answer from linked topic). Note, `cos`, `sin`, `rand` can not use this notation.

```
/${{<920>dup 1 4 3 roll put cvx exec}forall}def srand 250 99<AD>$ 50 50<8B>$/f{count(8X68)$ 1 le{0(>)$ 0<9D>$ 0 0 1 1<80>$ 0 1<AD>$ rand 5 mod 1 add 15<~CecsG2u~>$ cos<388B>$ f(M8)$ cos(88l>)$ 2(X)$ sin<6CAD38>$ 90<A988>$ sin<388B>$ 1 f pop}{pop}(U)$}def f

```

.

```
/${{<920>dup 1 4 3 roll put cvx exec}forall}def
srand
250 99<AD>$
50 50<8B>$
/f{
count(8X68)$
1 le{
0(>)$ 0<9D>$
0 0 1 1<80>$
0 1<AD>$
rand 5 mod 1 add 15
<~CecsG2u~>$
cos<388B>$
f
(M8)$
cos(88l>)$
2(X)$ sin<6CAD38>$
90<A988>$ sin<388B>$
1
f
pop
}{pop}(U)$
}def
f

```

---
Tags: code-golf, graphical-output
---


# Question
Title: Prime decimal representations of prime binary numbers
**Problem Statement**: Consider a number `n` in base-10. Find the smallest base-10 integer `i` greater than `n`, such that both the decimal and binary representations of `i` are prime (when viewed in decimal).

---

**Input**: a number in decimal
**Output**: The smallest base-10 number greater than `n`, which when viewed in both binary and decimal, is prime.

---

**Examples**:
*Input*:

* 1
* 3
* 100
* 1234567

*Output*:

* 3
* 5
* 101
* 1234721

*Explanations*:

* 3 is prime. 3 in binary is 11, which is also prime. 3 is the smallest number larger than 1 which satisfies these properties.
* 5 is prime. 5 in binary is 101, which is also prime. 5 is the smallest number larger than 3 which satisfies these properties.
* 101 is prime. 101 in binary is 1100101, which is also prime. 101 is the smallest number larger than 100 which satisfies these properties.
* 1234721 is prime. 1234721 in binary is 100101101011100100001, which is also prime. 1234721 is the smallest number larger than 1234567 which satisfies these properties.

---

Here are your test cases, ordered in ascending difficulty according to my own naive implementation. Please include a Try it online! in your answer:

*Input*:

* `n = 1325584480535587277061226381983816`, a.k.a. `(((((((1 + 2) * 3) ** 4) + 5) * 6) ** 7) + 8) * 9`
* `n = 1797010299914431210413179829509605039731475627537851106401`, a.k.a `((3^4)^5)^6`
* `n = 2601281349055093346554910065262730566475782`, a.k.a `0^0 + 1^1 + 2^2 + ... + 28^28 + 29^29`
* `n = 20935051082417771847631371547939998232420940314`, a.k.a. `0! + 1! + ... + 38! + 39!`
* `n = 123456789101112131415161718192021222324252627282930`

*Output*:

* `1325584480535587277061226381986899`
* `1797010299914431210413179829509605039731475627537851115949`
* `2601281349055093346554910065262730566501899`
* `20935051082417771847631371547939998232420981273`
* `123456789101112131415161718192021222324252627319639`

If you manage to get the correct outputs for these 5 test cases in under 3 seconds total, your code can be considered. This is , the shortest code in bytes wins.

# Answer
# 05AB1E, 7 bytes

I saw in the comments that you may remove the time limit, so **consider this as an answer only in case you are removing the time limit**, since it times out even for `1234567`.

```
[ÅNDbp#

```

Explanation:

```
[ÅNDbp#
           Input is at the top of the stack
[          Infinite loop
 ÅN        Next prime
   D       Duplicate that
    b      Binary representation
     p     Is it a prime number?
      #    Break the loop if it is, printing the top of the stuck, which is the next number that match both conditions.

```

Try on online!
> 2 votes

# Answer
# Jelly, 9 bytes

```
‘ÆnBḌẒ¬Ʋ¿

```

A monadic Link accepting an integer, `n`, that yields a list conting just one element, the next prime above `n` which is prime and has a decimal-read binary representation which is prime.

As a full program the integer is implicitly printed to STDOUT.

**Try it online!** Or see the test-suite.

### How?

```
‘ÆnBḌẒ¬Ʋ¿ - Link: n
‘         - increment n -> k=n+1
        ¿ - while...
       Ʋ  - ...condition: last four links as a monad - f(k):
   B      -      int to binary list
    Ḍ     -      decimal list to int
     Ẓ    -      is prime?
      ¬   -      NOT
 Æn       - ...do: (k=) next prime
          - yield k

```
> 1 votes

# Answer
# SageMath, 61 bytes

```
f=lambda n,p=is_prime:p(n+1)and p(f'{n+1:b}')and n+1or f(n+1)

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 68 bytes

```
(t=NextPrime)[#//.x_/;!PrimeQ@FromDigits@IntegerDigits[t@x,2]:>x+1]&

```

Try it online!
> 0 votes

# Answer
# Python 3 (145 bytes)

I am the author of this question; this is a non-golfed example if anyone doesn't understand the task. You don't need to upvote this.

```
from sympy import isprime
for case in range(5):
  n = int(input())
  i = n + 1
  while True:
    if isprime(int(bin(i)[2:])) and isprime(i):
      print (i)
      break
    i += 1

```

It runs in approx. 2.79 seconds on Try on online!
> -1 votes

---
Tags: code-golf, primes
---


title: Cut a triangle into equal-sized parts!

text:
# Question
Title: Cut a triangle into equal-sized parts!
Similar in spirit to Number of distinct tilings of an n X n square with free n-polyominoes and Partition a square grid into parts of equal area, this challenge will have you count ways of partitioning a triangle in a triangular grid. The goal of this challenge is to write a program that outputs \\$ a(n,m)\\$, the number of ways to partition a triangle of side length \\$n\\$ into equal parts containing \\$m\\$ cells each. The parts must contiguous, where two cells are considered touching if they share a side.

# Examples

Up to rotation and reflection, there are two ways to partition the size-\\$4\\$ triangle into equal parts of size \\$8\\$, so \\$a(4,8) = 2\\$:

Up to rotation and reflection, there are three ways to partition the size-\\$4\\$ triangle into four parts of size \\$4\\$, so \\$a(4,4) = 3\\$:

# Table

```
 n |  m | a(n,m)
---+----+-------
 1 |  1 | 1
 2 |  1 | 1
 2 |  2 | 0
 2 |  4 | 1
 3 |  1 | 1
 3 |  2 | 0
 3 |  3 | 1
 3 |  9 | 1
 4 |  1 | 1
 4 |  2 | 0
 4 |  3 | 0
 4 |  4 | 3
 4 |  8 | 2
 4 | 16 | 1

```

(I've made this table by hand, so comment if you spot any mistakes.)

# Challenge

Write a program that takes an input \\$n\\$, which is the size of a triangle, and a parameter \\$m\\$, which is the size of each region, and return the number of ways to partition the size \\$n\\$ triangle into \\$n^2/m\\$ parts of size \\$m\\$ *up to the rotations and reflections of the triangle.* Your code should be able to handle the inputs in the table on TIO, and it should be able to handle larger inputs in principle.

This is a challenge, so the shortest code wins.

# Answer
# JavaScript (ES7),  ~~367 362 359~~  357 bytes

*Saved 1 byte thanks to @Shaggy*

Expects `(n)(m)`.

```
n=>m=>(T=Array(n*n).fill(N=0),g=(A,P=[-1],k=T.findIndex(v=>!v),B=[...A,P[S='sort']()][S]())=>g[B]?0:~[1,1,0,1,1,0][M='map'](r=>g[B=B[M](P=>P[M](i=>~i?(y=i**.5|0)*y-i-(r?1-((~y*~y+~i>>1)-n)**2:y*~-~y):i)[S]())[S]()]=1)/P[m]?~k?g(B):++N:T[M]((v,j)=>v||(~P?P.every(i=>(y=i**.5|0)^j**.5|(i-j)**2-1&&j-i+2*(i+y&1?y:~y)):j-k)||T[T[j]++,g(A,[...P,j]),j]--))([])&&N

```

Try it online!

## How?

### TL;DR

This is a recursive search that keeps track of all the patterns that were already tried, transformed in all possible ways, in order to prune the search as soon as possible when a collision is found. This allows it to perform at a decent speed on small triangles despite an otherwise inefficient piece-building method.

### Triangle description and cell indexing

A size-\\$n\\$ triangle is simply stored as an array of \\$n^2\\$ binary values. Empty cells are marked with \\$0\\$'s and occupied cells are marked with \\$1\\$'s.

JS initialization:

```
T = Array(n * n).fill(0)

```

By convention, the cells are numbered from \\$0\\$ to \\$n^2-1\\$, from left to right and top to bottom.

Below are some basic formulas:

* The 0-indexed row of the cell \\$c\\$ is \\$y\_c=\lfloor\sqrt{c}\rfloor\\$
* The 0-indexed position of the cell \\$c\\$ within its row is \\$c-{y\_c}^2\\$
* The 0-indexed distance of the cell \\$c\\$ from the last cell in its row is \\${(y\_c+1)}^2-c-1\\$

### Testing whether 2 cells are neighbors

Two cells \\$c\\$ and \\$d\\$ are horizontal neighbors if \\$y\_c=y\_d\\$ and \\$|c-d|=1\\$ (e.g. \\$c=10\\$ and \\$d=11\\$, or the other way around).

Two cells \\$c\\$ and \\$d\\$ are vertical neighbors if either:

* \\$c+y\_c\\$ is even and \\$d=c+2\times(y\_c+1)\\$ (e.g. \\$c=3\\$ and \\$d=7\\$)
* \\$c+y\_c\\$ is odd and \\$d=c-2\times y\_c\\$ (e.g. \\$c=7\\$ and \\$d=3\\$)

Hence the following JS expression which is truthy if the cells `i` and `j` are ***not*** neighbors:

```
(y = i ** .5 | 0) ^ j ** .5 | (i - j) ** 2 - 1 && j - i + 2 * (i + y & 1 ? y : ~y)

```

### Reflections

A vertical reflection is applied by doing:

$$d=2\times y\_c\times (y\_c+1)-c$$

**Examples:**

$$2\times y\_{10}\times (y\_{10}+1)-10=2\times 3\times 4-10=14\\ 2\times y\_{14}\times (y\_{14}+1)-14=2\times 3\times 4-14=10$$

### Rotations

A 120° rotation is applied by doing:

$$d=\left(n-\left\lfloor\dfrac{(y\_c+1)^2-c-1}{2}\right\rfloor\right)^2+{y\_c}^2-c-1$$

**Examples:**

* \\$c=0\\$ is turned into \\$d=15\\$
* \\$c=7\\$ is turned into \\$d=12\\$

### Combining reflections and rotations

In the JS implementation, both formulas are combined into the following expression. This code applies a reflection to the cell `i` when `r = 0` or a rotation when `r = 1`.

```
(y = i ** .5 | 0) * y - i - (
  r ?
    1 - ((~y * ~y + ~i >> 1) - n) ** 2
  :
    y * ~-~y
)

```

To get all possible transformations of a tiling, we apply 2 rotations, followed by a reflection, followed by 2 rotations, followed by a reflection.

Hence the loop:

```
[1, 1, 0, 1, 1, 0].map(r =>
  /* ... apply the transformation to each cell of each piece of the tilling ... */
)

```

### Describing the tiling

Each piece of the tiling is stored in an array of \\$m+1\\$ entries consisting of a leading `-1` followed by \\$m\\$ indices corresponding to the cells it contains.

The current piece is stored in `P[]`. The array `A[]` contains the previous pieces. The array `B[]` contains the previous pieces and the current piece, with all pieces sorted in lexicographical order and all indices also sorted in lexicographical order within each piece.

**Example:**

The following tiling:

would be described with:

```
B = [
  [ -1, 0, 1, 2, 3 ],
  [ -1, 10, 11, 4, 9 ],
  [ -1, 12, 5, 6, 7 ],
  [ -1, 13, 14, 15, 8 ]
]

```

Once coerced to a string, this gives a unique key that allows us to detect whether a similar configuration was already encountered and prune the search.

```
"-1,0,1,2,3,-1,10,11,4,9,-1,12,5,6,7,-1,13,14,15,8"

```

The purpose of the `-1` markers is to make sure that an incomplete piece followed by another piece in the key is not mixed up with another complete piece.

The keys are stored in the underlying object of the function `g`.

### Main algorithm

The recursive search function goes as follows:

* find the position `k` of the first empty cell in the triangle
* update `B[]`
* abort if `B[]` was already encountered
* apply all transformations to `B[]` and mark them as encountered
* if `P[]` is complete:
    + if the triangle is full (`k` is set to `-1`): we've found a new valid tiling, so increment the number of solutions `N`
    + otherwise, append `P[]` to `A[]` and start building a new piece
* if `P[]` is not yet complete:
    + if `P[]` does not contain any tile, append `k` to it
    + otherwise, try to append the index of each tile that has at least one neighbor in `P[]`
> 16 votes

# Answer
# Scala 3, ~~526~~...~~358~~ 357 bytes

```
n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

```

Try it in Scastie!

Dotty's tupled parameter destructuring save a few bytes, but it's pretty much the same as the approach below.

# Scala 2, ~~548~~...~~362~~ 361 bytes

```
n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{case(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

```

Try it online

Ungolfed version

To see the individual triangles

## Explanation

Each point is represented by an x-y pair `(Int,Int)`. The x-position starts out at 1 at the left and increases as it goes to the right. The y-position starts out at 1 at the top and increases as it goes to the bottom. A piece of the triangle is represented as a set of points (`Set[(Int,Int)]`), and a triangle (possible solution) is represented as a set of those pieces (`Set[Set[(Int,Int)]]`)

The first line defines `c`, a `Set` which will hold all possible solutions (and currently just holds a single partially completed triangle that holds a single piece that holds a single point (\\$(1,1)\\$, the top of the triangle)). `d` says how many of those triangles are completed. This is the variable that will be returned at the very end.

The bulk of the function is taken up by a while loop that runs as long as `d` is 0 and `c` is not empty (if `d` is more than 0, it means we've found all the triangles we're ever going to find, and if `c` is empty, it means there aren't any possible solutions).

Each iteration, `d` is set to the number of triangles in `c` that have has \\$\frac{n\*n}{m}\\$ pieces and all their pieces are of size `m`. For that, the expression `c.count{t=>t.size*m==n*n&t.forall(_.size==m)}` can be used.

Then, we find the next value of `c`. The code creates new triangles by adding neighbors to the old triangles in `c`, and to ensure only unique triangles are kept, it first creates a set of all 6 permutations for each of the new triangles. Because `c` is a `Set`, it removes duplicates by default without us having to do any work. After the permutations have been generated and the duplicates remove, it's simple to extract a single permutation with `<all_permutations>map(_.head)`.

When the while loop ends, we simply return `d`.

### Specifics:

**Generating new triangles**

For every shape in a triangle, we take all its neighbors, and remove the ones that are already in the triangle. Then, if the shape already has \\$m\\$ cells, we make a new shape containing only the neighbor and add it to the triangle, otherwise we add the neighbor to the shape. For comprehensions make this part easy:

```
for {
  t <- c              //For every triangle t in c
  s <- t              //For every piece/shape s in t
  a -> b <- s         //For every point (a, b) in s
  e = a % 2 * 2 - 1   //This is just to reuse
  //The cell to the left, the cell to the right, and the cell above/below
  neighbors <- Set( (a - 1, b) , (a + 1, b) , (a + e, b + e) )
  //x and y are the coordinates of the neighbor
  x -> y <- neighbors -- t.flatten //Remove neighbors already in the triangle
  //Make sure the neighbor is within bounds of the triangle
  if 0 < y & y <= n & 0 < x & x < y * 2
} yield (
  if (s.size < m) t - s + (s + (x -> y)) //If s is not full, add the neighbor to s
  else t + Set(x -> y) //Otherwise, make a new shape containing just (x, y)
)

```

The new triangles are not directly yielded, this is just an example.

**Generating all permutations**

Each triangle has 6 different permutations, which can be found by alternating between reflecting over the y-axis and rotating 60 degrees clockwise + reflecting it over the y-axis. We can `scanLeft` over a range of numbers, doing the first transformation when the element is even, and the second when it's odd.

Assuming we already have a triangle `<new_triangle>`, we can scan left over a range of 5 numbers, leaving us with 6 triangles:

```
0.to(4).scanLeft(<new_triangle>){
  (t, i) => //i is the current index/element, t is the triangle to transform
  t.map { s => //Transform every shape s in t
    s.map {
      case (x, y) => //Transform every point in s (x, y)
        //If i is even, it will rotate+reflect, if it's odd, it will reflect
        Seq( (x, n + 1 - y + x / 2) , (y * 2 - x, y) )(i%2)
    }
  }
}

```

**Reflecting a point over the y-axis**:

For a point \\$(x,y)\\$, the y-coordinate stays the same after reflecting, and the x-coordinate becomes \\$y * 2 - x\\$, since \\$y * 2\\$ is the biggest possible x-coordinate for a given y-coordinate.

**Rotating a point 60 degrees clockwise + reflecting it over the y-axis**:

You can rotate and reflect a point at once if you keep the x-coordinate the same and set the y-coordinate to \\$n + 1 - y + x / 2\\$.

## Commented:

//Take n and m, curried
n => m => {
  val S = Set //The Set companion object, to reuse later
  //c holds all our possible solutions/triangles as we build them
  //d holds how many of the triangles in c are complete
  var (c, d) = S(S(S(1 -> 1))) -> 0

  //While we haven't found any complete triangles and
  //the set of possible solutions is nonempty, keep going
  while (d < 1 & c != S()) {
    //Count how many of c's triangles have n*n/m pieces, each with m cells
    d = c.count { t => t.size * m == n * n & t.forall(_.size == m) }
    //This for comprehension adds a cell to each triangle and
    //generates all permutations of each new triangle
    c = (for {
      t <- c
      s <- t
      a -> b <- s
      c = a % 2 * 2 - 1
      x -> y <- S(a - 1 -> b, a + 1 -> b, (a + c, b + c)) -- t.flatten
      if 0 < y & y <= n & 0 < x & x < y * 2
    } yield
      S(0 to 4:_*).scanLeft(
         if (s.size < m) t - s + (s + (x -> y))
         else t + Set(x -> y)
      ) { (t, i) =>
         t.map(_.map { case (x, y) =>
           Seq((x, n + 1 - y + x / 2), y * 2 - x -> y)(i % 2)
         })
      }
      //Convert the Seq of permutations to a set so duplicates can be compared out of order and removed
     )  //End of massive for-comprehension
     map (_.head) //Extract only the first permutation from each set of permutations
  }
  d
}
```

> 11 votes

---
Tags: code-golf, geometry, combinatorics, hexagonal-grid
---


title: GCD / LCM Polyglots!

text:
# Question
Title: GCD / LCM Polyglots!
Your challenge is to make a program or function that outputs the GCD of its inputs in one language and the LCM of its inputs in another. Builtins for GCD or LCM (I'm looking at you, Mathematica) are allowed but not encouraged. There will be 2 inputs, which will always be positive integers, never greater than 1000.

## Test Cases

Each line is one test case in the format `x y => GCD(x,y) LCM(x,y)`:

```
1 1 => 1 1
1 2 => 1 2
4 1 => 1 4
3 4 => 1 12
7 5 => 1 35
18 15 => 3 90
23 23 => 23 23
999 1000 => 1 999000
1000 999 => 1 999000
1000 1000 => 1000 1000

```

See this pastebin for all possible inputs with `0 < x, y < 31`. Note that different versions of the same languages count as different languages.

# Answer
> 23 votes
# Jelly / Actually, 2 bytes

```
00000000: 1e 67                                            .g

```

This is a hexdump (xxd) of the submitted program. It cannot be tested online because TIO doesn't support the CP437 encoding. @Mego was kind enough to verify that this works on Cygwin, which implements CP437 as intended for Actually.

## Jelly: GCD

Jelly uses the Jelly code page, so it sees the following characters.

```
œg

```

Try it online!

### How it works

`œ` is an incomplete token and thus ignored. `g` is the GCD built-in.

## Actually: LCM

Actually uses CP 437, so it sees the following characters.

```
▲g

```

Try it online!

### How it works

is the LCM input. Since `g` (GCD) requires *two* integer inputs, it isn't executed.

# Answer
> 27 votes
# C / C++, ~~79~~ ~~78~~ 73 bytes

*Thanks to @ETHproductions for saving a byte!*

```
int f(int a,int b){int c,d=a*b;for(;a;b=c)c=a,a=b%a;auto e=.5;c=e?d/b:b;}

```

C calculates the GCD: Try it online!

C++ calculates the LCM: Try it online!

In C, `auto e=.5` declares an integer variable with the auto storage class (which is the default), which is then initialized to 0, whereas in C++11 it declares a double, which is initialized to 0.5. So the variable's value will be truthy in C++ and falsy in C.

The function calculates the GCD with Euclid's algorithm, and the LCM by dividing the product of a and b by the GCD.

Omitting the return statement works at least on GCC. The 78 byte solution below should work with any compiler:

```
int f(int a,int b){int c,d=a*b;for(;a;b=c)c=a,a=b%a;auto e=.5;return e?d/b:b;}

```

# Answer
> 16 votes
# Actually / Jelly, 3 bytes

```
00000000: 11 1c 67                                         ..g

```

This is a hexdump (xxd) of the submitted program.

Try it online!1

## Actually: GCD

Actually uses CP 437, so it sees the following characters.

```
◄∟g

```

Try it online!

### How it works

```
     (implicit) Read a and b from STDIN and push them on the stack.
◄    Unassigned. Does nothing.
 ∟   Unassigned. Does nothing.
  g  Pop a and b and push gcd(a,b).
     (implicit) Write the result to STDOUT.

```

## Jelly: LCM

Jelly uses the Jelly code page, so it sees the following characters.

```
×÷g

```

Try it online!

### How it works

```
×÷g  Main link. Left argument: a. Right argument: b

×      Multiply; yield ab.
  g    GCD; yield gcd(a,b).
 ÷     Division; yield ab/gcd(a,b) = lcm(a,b).

```

**Note:** The formula **gcd(a,b)lcm(a,b) = ab** holds because **a** and **b** are positive.

---

1 TIO actually uses UTF-8 for Actually. Since both the ASCII characters and the CP437 characters **0x11** and **0x1c** are unassigned, the program works nevertheless.

# Answer
> 8 votes
## Alice and Jelly, 9 bytes

Alice computes the LCM:

```
//L
oi@g

```

Try it online!

What looks like a space is really `0x7F`, the `DEL` control character.

Jelly computes the GCD. Since Jelly uses its own code page which is only compatible with printable ASCII, the linefeed and DEL character turn into `½` and linefeed, respectively:

```
//L½oi@
g

```

Try it online!

### Explanations

Jelly is trivial: the first line defines a nonsensical helper link, the second line is the actual program and it simply contains the GCD built-in.

Alice is a little bit trickier, but it also uses a built-in:

```
/   Reflect to SE. Switch to Ordinal.
    While in Ordinal mode, the IP bounces diagonally up and down through the grid.
i   Read all input as a single string.
L   Compute the shortest common superstring of an empty string and the input. That
    is simply the input itself, so this does nothing.
    After two more bounces, the IP hits the top right corner and turns
    around, continuing to bounce up and down while moving west.
L   Still does nothing.
i   Try to read more input, but this simply pushes an empty string.
/   Reflect to W. Switch to Cardinal.
    The IP wraps to the last column.
L   Implicitly discard the empty string and convert the input to two integers.
    Compute their LCM.
/   Reflect to NW. Switch to Ordinal.
    The IP immediately reflects off the top boundary to move SW instead.
o   Implicitly convert the LCM to a string and print it.
    Reflect off the bottom left corner and move back NE.
/   Reflect to S. Switch to Cardinal.
i   Try to read a byte, but we're at EOF, so this pushes -1 instead. Irrelevant.
    The IP wraps back to the first line.
/   Reflect to NE. Switch to Ordinal.
    The IP immediately reflects off the top boundary to move SE instead.
@   Terminate the program.

```

# Answer
> 6 votes
# Octave / MATLAB, ~~66~~ 61 bytes

```
@(x,y)gcd(x,y)^(1-2*any(version==82))*(x*y)^any(version==82))

```

Saved 5 bytes thanks to Foon. `(x*y)^any()` was of course shorter than `1+(x*y-1)*any()`.

---

Well, at least it doesn't use the builtin for `lcm`.

**Explanation:**

This uses the builtin `gcd` to calculate the Greatest common divisor.

In Octave, this is raised to the power of `1-2*any(version==82)`. `any(version==82)` is `0` in Octave, so this is simply `gcd(x,y)^1`. It's multiplied by `(x*y)^any(version==82)`, or `(x*y)^0 = 1`.

For MATLAB, `gcd` is raised to the power of `1-2*any(version==82)`. `any(version==82)` is `1` in MATLAB, so this is `gcd(x,y)^-1`. It multiplied by `(x*y)^any(version==82)`, or `(x*y)^1 = x*y`. This gives the Least common multiple, since `lcm(x,y) == x*y/gcd(x,y)` for positive numbers.

# Answer
> 5 votes
# Julia 0.4 / Julia 0.5, 18 bytes

```
log.(1)==0?lcm:gcd

```

Evaluates to `gcd` in Julia 0.4 (Try it online!) and to `lcm` in Julia 0.5 (Try it online!).

### How it works

In Julia 0.4, `log.(1)` is a shorthand for `getfield(log,1)`, which returns the memory location of the `log` builtin, e.g., the pointer `Ptr{Void} @0x00007f2846cb6660`. The result is thus non-zero, the comparison is false, and the expression evaluates to `gcd`.

In Julia 0.5, a new function vectorization syntax was introduced. `log.(1)` is now a shorthand for `broadcast(log,1)`, which – since `1` is not iterable – simply evaluates `log(1)`. The result is thus zero, the comparison is true, and the expression evaluates to `lcm`.

# Answer
> 4 votes
# Jelly and MATL, ~~6~~ 5 bytes

```
ZmD
g

```

This is a full program in either of the two languages. It computes the GCD in Jelly (Try it online!) and the LCM in MATL (Try it online!). The MATL program exits with an error (allowed by default) after producing the correct output.

Only ASCII characters are used, so they correspond to the same encoded bytes in the two languages.

### Explanation of GCD in Jelly

```
ZmD    Unused link
g      Main link (gets called automatically). Builtin GCD function (g)

```

### Explanation of LCM in MATL

```
ZmD    Compute LCM (builtin function Zm) and display immediately (D)
g      Tries to implicitly take input to do something with it (depending
       on the type of the input). Since there is no input, it errors out

```

# Answer
> 2 votes
# Octave / MATLAB, ~~44~~ ~~42~~ 41 bytes

```
eval(['@' 'lcm'-[5 0 9]*all(version-82)])

```

This defines an anonymous function for GCD (`@gcd`) in Octave, and for LCM (`@lcm`) in MATLAB.

Example in Octave (or Try it online!):

```
>> eval(['@' 'lcm'-[5 0 9]*all(version-82)])
warning: implicit conversion from numeric to char
ans = @gcd
>> ans(12,16)
ans =  4

```

Example in MATLAB:

```
>> eval(['@' 'lcm'-[5 0 9]*all(version-82)])
ans =
    @lcm
>> ans(12,16)
ans =
    48

```

# Answer
> 1 votes
# JS (ES6), CGL (CGL Golfing Language), 31 bytes (non-competing)

The LCM feature of CGL was added after this challenge.

```
 g=(a,b)=>b?g(b,a%b):a
//-LⓍ

```

What looks like a space is actually a non-breaking space, a comment for CGL. JS computes the GCD:

```
g=(a,b)=>b?g(b,a%b):a

```

And CGL computes the LCM:

```
//  does nothing
- decrements the current stack number, resulting in it pointing to input
L computes the LCM of the first and second stack items and pushes it to the stack
Ⓧ prints out the last stack item

```

Try it out:

```
Snippetify( g=(a,b)=>b?g(b,a%b):a
//-LⓍ
);
```

```
<script src="https://programmer5000.com/snippetify.min.js"></script>
<input type = "number">
<input type = "number">
```

# Answer
> 1 votes
# Whispers v1/Whispers v2, 51 bytes

```
> Input
> Input
>> R1
>> 1⊓2
>> 1⊔2
>> Output 4

```

Try it online! (Whispers v1)

Try it online! (Whispers v2)

## How it works

The pivotal line is interestingly the only line that isn't executed by either language:

```
>> R1

```

In Whispers (both versions), lines which don't match one of a certain set of regex are completely ignored. As a result, lines containing invalid commands are simply skipped over by the interpreter. `R` is a command that returns the magnitude and angle of a vector, which was added in version 2. In version 1 however, it's an invalid command, so that line is removed.

In both versions, the execution pattern is the same: output the value on line **4**, which is either the GCD or LCM of the inputs, depending on the version. In version 1, we remove the 3rd line, so line **4** is

```
>> 1⊔2

```

which simply runs the LCM command on the inputs. In version 2 however, the program is unchanged, meaning that line **4** is

```
>> 1⊓2

```

which is the GCD builtin applied to the two inputs.

Finally, in both versions, the value on line **4** is outputted and the program ends

---
Tags: code-golf, math, polyglot
---


# Question
Title: Are they connected by a Brussels choice?
## Background

Two numbers, \\$a\\$ and \\$b\\$, are said to be connected by a Brussels choice operation* if \\$b\\$ can be reached from \\$a\\$ by doubling or halving (if even) a substring (the substring must not be empty and may not contain any leading 0s but it can be 0) in the base-10 representation of \\$a\\$

*This operation is slightly different from the one defined on this paper mainly that the operation defined in the paper allows empty substrings and does not allow choosing the substring "0"

For example, all the number that can be reached from `5016`:

```
508     (50[16] half   -> 50[8])
2508    ([5016] half   -> [2508])
2516    ([50]16 half   -> [25]16)
5013    (501[6] half   -> 501[3])
5016    (5[0]16 half   -> 5[0]16)
        (5[0]16 double -> 5[0]16)
5026    (50[1]6 double -> 50[2]6)
5032    (50[16] double -> 50[32])
10016   ([5]016 double -> [10]016)
        ([50]16 double -> [100]16)
10026   ([501]6 double -> [1002]6)
10032   ([5016] double -> [10032])
50112   (501[6] double -> 501[12])

```

## Task

Write a program/function that when given two positive integers as input outputs a truthy value if they can reach each other with a single Brussels choice operation and a falsey value otherwise.

## Scoring

This is so shortest bytes wins.

## Sample Testcases

```
2, 4       -> Truthy
4, 2       -> Truthy
101, 101   -> Truthy
516, 58    -> Truthy
58, 516    -> Truthy
516, 5112  -> Truthy
5112, 516  -> Truthy

1, 3       -> Falsey
123, 123   -> Falsey
151, 252   -> Falsey
112, 221   -> Falsey
101, 999   -> Falsey
999, 1001  -> Falsey
101, 1001  -> Falsey

```

---

*Inspired by The Brussels Choice - Numberphile*

# Answer
> 6 votes
# Retina, 38 bytes

```
L$w`0|[1-9]\d*
$`$.(*2*)$'
m`^(.+),\1$

```

Try it online! Link includes test cases. Outputs `0` for Falsey, non-zero for Truthy. Explanation:

```
L$w`0|[1-9]\d*

```

Match all integer substrings of both inputs, including `0` but not integers beginning with `0`.

```
$`$.(*2*)$'

```

List the result of doubling that substring only.

```
m`^(.+),\1$

```

Check to see whether this produces any pairs of equal integers.

# Answer
> 6 votes
# Python 2, ~~180~~ \\$\cdots\\$ ~~121~~ 111 bytes

Saved 2 bytes thanks to Mukundan314!!!
Saved a whopping 16 bytes thanks to an idea from Dominic van Essen!!!
Saved 7 bytes thanks to Kevin Cruijssen!!!
Saved 10 bytes thanks to Neil!!!

```
def f(*p):a=`min(p)`;return max(a[:i]+`2*int(a[i:j])`+a[j:]==`max(p)`for j in range(len(a)+1)for i in range(j))

```

Try it online!

Returns either `True` or `False`.

# Answer
> 6 votes
# Brachylog, ~~13~~ 12 bytes

```
p{~c↺×₂ʰ↻c}ᵈ

```

Try it online!

*-1 byte thanks to Zgarb*

Takes input as a list `[a, b]` through the input variable and outputs through success or failure.

```
p               Permute the input.
 {        }ᵈ    For the first element of the input:
  ~c            take some partition of it,
     ×₂         double
    ↺  ʰ↻       the second element of the partition,
         c      and re-concatenate it.
 {        }ᵈ    It's possible for the result to be the second element of the input.

```

# Answer
> 3 votes
# , ~~120~~ ~~117~~ ~~112~~ 106 bytes

*Edit: -5 bytes thanks to Giuseppe (again)*

*Edit2: -6 bytes by using vectorized arguments to `substring` and `paste` and so avoiding any loops*

```
function(v,m=min(v),`[`=substring,b=rep(1:m,e=m))max(v)%in%paste0(m[0,b-1],as.double(m[1:m,b])*2,m[1:m+1])

```

Try it online!

**How?**

```
is_brussels=
function(v,             # v is vector of 2 input values
 m=min(v),              # m is smaller input value
 s=substring)           # s is alias to substring function.
 max(v) %in%            # Main function : Is larger input value present in ...
  sapply(1:m,           # the results of applying all combinations of 1..m ...
   function(b)          # to the 'brussels' function with beginning b ...
    paste0(s(m,0,b-1),  # which pastes together m (up to b)...
     as.numeric(s(m,b,1:m))*2,
                        # onto 2x m (from b to all values of e from 1:m) ...
     s(m,2:m)           # onto m (from e onwards)?
    )
  )

```

# Answer
> 3 votes
# 05AB1E, ~~31~~ ~~27~~ 23 bytes

```
{R`.œv3FyDNè·Nyg%ǝ])Jćå

```

-4 bytes as bug-fix - thanks to *@ovs* for noticing. (Decreasing the bytes as bug-fix doesn't happen often, haha. :D)

Input as a pair of integers.

Try it online or verify all test cases.

**Explanation:**

```
{R                 # Sort the (implicit) input-pair from highest to lowest
  `                # Pop and push both values separated to the stack
   .œ              # Get all partitions of the top lowest integer
     v             # Loop over each partition `y`:
      3F           #  Inner loop `N` in the range [0, 3):
        yD         #   Push partition `y` twice
          Nè       #   Get the `N`'th item of the partition (modulair 0-based)
            ·      #   Double it
             N     #   Push index `N` again
              yg%  #   Modulo the length of the current partition `y`
                   #   (since builtin `ǝ` doesn't index modulair)
                 ǝ #   Insert the doubled substring back into the partition at that index
     ]             # Close both loops
      )            # Wrap all values on the stack into a list
       J           # Join each partition back to a single string
        ć          # Extract the head; pop and push the remainder-list and first item
                   # separated to the stack (which is the highest value that was still on
                   # the stack)
         å         # Check if the list contains this highest integer
                   # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Raku, 48 bytes

```
{;*eq[|] m:ex/.+/>>.&{.replace-with($_/(2|.5))}}

```

~~Try it online!~~ Oops, TIO doesn't have an up to date version of Raku, which means it doesn't have `replace-with`. I guess we'll have to go with repl.it online! instead.

# Answer
> 2 votes
# JavaScript (ES9), 102 bytes

Returns either `false` or `1`.

```
f=(a,b,i)=>(g=r=>a.replace(o=RegExp('(?<='+r),n=>o=n*2)==b&++o||o&&g('.'+r)|g(r+'.'))`)`||!i&&f(b,a,1)

```

Try it online!

### How?

We recursively build all possible regular expressions matching the first occurrence of \\$p\\$ digits preceded by \\$q\\$ digits, using a lookbehind assertion. The matched string is coerced to an integer, doubled and coerced back to a string.

Example:

```
"123456".replace(/(?<=..).../, n => n * 2) // -> "12[345]6" -> "12[690]6"

```

We stop the recursion when no replacement occured (failure) or the result is equal to the other number (success). We try to turn either `a` into `b` or `b` into `a`.

### Commented

```
f = (                     // f is a recursive function taking:
  a, b,                   //   the input numbers a and b
  i                       //   a flag i telling if the numbers were already swapped
) => (                    //
  g = r =>                // g is a recursive function taking a pattern r
    a.replace(            // replace in a:
      o =                 //   initialize o to a non-numeric value
      RegExp('(?<=' + r), //   turn r into a regular expression of the form /(?<=..)../
      n =>                //   if something is matched: replace the substring n with
        o = n * 2         //   2 * n and assign the result to o
    ) == b                // end of replace(); success if the result is equal to b
    & ++o                 // and o is an even number, which becomes odd when incremented
    || o &&               // otherwise, if o is not equal to NaN:
      g('.' + r) |        //   try again with 1) another leading '.' in r
      g(r + '.')          //   and 2) with another trailing '.' in r
)`)`                      // initial call to g with r = ')'
|| !i && f(b, a, 1)       // if i is not set, try again with a and b exchanged

```

# Answer
> 1 votes
# Python 3.8 (pre-release), 115 bytes

```
lambda*x:(a:=str(min(x)))and{str(max(x))}&{a[:i]+str(2*int(a[i:j]))+a[j:]for j in range(len(a)+1)for i in range(j)}

```

Try it online!

---

# Python 3, ~~139~~ 116 bytes

~~A golf of Noodle9's answer.~~ Outputs a set containing `b` if there is a Brussels choice, an empty set otherwise.

```
def f(*x):a,b=map(str,sorted(x));return{b}&{a[:i]+str(2*int(a[i:j]))+a[j:]for j in range(len(a)+1)for i in range(j)}

```

Try it online!

# Answer
> 1 votes
# perl -Mfeature=say -na, 68 bytes

```
($_,$n)=@F;m[.+(?{say$=if$n eq$`.($&/2).$'||$n eq$`.($&*2).$'})(?!)]

```

Try it online!

Reads two numbers from the input, and prints 60 if there's a way to connect the numbers, and nothing otherwise.

## How does it work?

We take every possible, non-empty, substring of the first number; this will be in available in `$&`. The part of the first number which proceeds the current substring is in `$`` , the part after it is in `$'`. We then create two new strings, by either multiplying the substring by 2, or dividing it by 2, and sandwiching it between `$``  and `$'`. We then compare this with the second number, and print `$=` if there is a match (`$=` by default contains 60). Note that if the substring is odd, the resulting string will contain a decimal point, and hence, will not match with the second number.

# Answer
> 0 votes
# Perl 5 `-pl`, 122 bytes

```
$t=<>;for$a(1..y///c){for$b(0..y///c){$z||=/(.{$b})(.{$a})/&&$2!~/^0./&&grep$t==$_,$2%2==0&&$1.$2/2 .$',$1.$2*2 .$'}}$_=$z

```

Try it online!

---
Tags: code-golf, decision-problem
---


title: First-n Fibonacci sequence elements

text:
# Question
Title: First-n Fibonacci sequence elements
There is a well known question here that asks for a short (least characters) fibonacci sequence generator.

I would like to know if someone can generate the first N elements only, of the fibonacci sequence, in very short space. I am trying to do it in python, but I'm interested in any short answer, in any language. Function F(N) generates the first N elements of the sequence, either returns them as the return of the function or prints them.

Interestingly it seems that the code-golf answers start with `1 1 2`, instead of `0 1 1 2`. Is that a convention in code-golf or programming-in-general? (Wikipedia says the fibonacci sequence starts with zero.).

Python Sample (First 5 Elements):

```
def f(i,j,n):
    if n>0:
        print i;
        f(j,i+j,n-1)
f(1,1,5)

```

# Answer
## C

Didn't bother counting, but here's a fun example:

```
f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}

```

Proof it works.

---

I'm quite proud of this: I got bored, so I rearranged my code (with a few small additions) to make it where each line represents a value in the Fibonacci sequence.

```
                         #                                // 1
                         f                                // 1
                         //                               // 2
                        (n)                               // 3
                       {/**/                              // 5
                      return n                            // 8
                    <2 ? 1:f(--n)                         // 13
                +f(--n); } main(a, b)                     // 21
          {a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55

```

Proof it works.
> 40 votes

# Answer
## Haskell (26)

Surprisingly, this is only *one* character longer than the J solution.

```
f=(`take`s)
s=0:scanl(+)1s

```

I shave off a few characters by:

1. Using `take` as a binary operator;
2. Using `scanl` instead of the verbose `zipWith`.
> 7 votes

# Answer
Here's a one-liner Python. It uses floating-point, so there may be some `n` for which it is no longer accurate.

```
F=lambda n:' '.join('%d'%(((1+5**.5)/2)**i/5**.5+.5)for i in range(n))

```

`F(n)` returns a string containing the first `n` Fibonacci numbers separated by spaces.
> 5 votes

# Answer
## GolfScript, 16 characters

```
~0 1@{.2$+}*;;]`

```

**Example output:**

```
$ ruby golfscript.rb ~/Code/golf/fib.gs <<< "12"
[0 1 1 2 3 5 8 13 21 34 55 89]

```
> 5 votes

# Answer
## Perl, 50 characters

```
sub f{($a,$b,$c)=@_;$c--&&say($a)&&f($b,$a+$b,$c)}

```
> 4 votes

# Answer
### Scala 71:

```
def f(c:Int,a:Int=0,b:Int=1):Unit={println(a);if(c>0)f(c-1,b,a+b)};f(9)

```

prints

```
0
1
1
2
3
5
8
13
21
34

```
> 4 votes

# Answer
# Python(55)

```
a,b=0,1

for i in range(int(input())):a,b=b,a+b;print(b)

```
> 3 votes

# Answer
# Perl, ~~29~~ 28 bytes

```
perl -E'say$b+=$;=$b-$;for-pop..--$;' 8
1
1
2
3
5
8
13
21

```

## Explanation

This is based on the classic `$b += $a = $b-$a` recurrence which works as follows:

* At the start of each loop `$a` contains `F(n-2)` and `$b` contains `F(n)`
* After `$a = $b-$a` `$a` contains `F(n-1)`
* After `$b += $a` `$b` contains `F(n+1)`

The problem here is the initialization. The classical way is `$b += $a = $b-$a || 1` but then the sequence goes `1 2 3 5 ...`

By extending the fibonacci sequence to the left:

```
... 5 -3 2 -1 1 0 1 1 2 3 5 ...

```

you see that the proper starting point is `$a = -1` and `$b = 0`. Initializing $a can be combined with setting up the loop

Finally replace `$a` by `$;` to get rid of the space before the `for`
> 3 votes

# Answer
I can give you a two line Python solution. This will return them as a list.

```
f = lambda n: 1 if n < 2 else f(n-1) + f(n-2)
g = lambda m: map(f, range(0,m))

print g(5)

```

You could have it print them out by adding another map to make them strings and then adding a join, but that just seems unnecessary to me.

Unfortunately I don't know how to put a recursive lambda into `map`, so I'm stuck at two lines.
> 2 votes

# Answer
## Python (78 chars)

I used Binet's formula to calculate the fibonacci numbers -

> \[(1+sqrt(5))^n-(1-sqrt(5)^n\]/\[(2^n)sqrt(5)\]

It's not as small some of the other answers here, but boy it's fast

```
n=input()
i=1
x=5**0.5
while i<=n:
    print ((1+x)**i-(1-x)**i)/((2**i)*x)
    i+=1

```
> 2 votes

# Answer
# Scheme

This is optimized using tail-recursion:

```
(define (fib n)
  (let fib ([n n] [a 0] [b 1])
    (if (zero? n) (list a)
        (cons a (fib (- n 1) b (+ a b))))))

```
> 2 votes

# Answer
## Haskell

```
fib n = take n f
f = 0:1:zipWith (+) f (tail f)

```

Proof that it works.
> 2 votes

# Answer
## J, 25 characters

I realise that J solutions are probably not what you're after, but here's one anyway. :-)

```
0 1(],+/&(_2&{.))@[&0~2-~

```

Usage:

```
    0 1(],+/&(_2&{.))@[&0~2-~ 6
0 1 1 2 3 5
    0 1(],+/&(_2&{.))@[&0~2-~ 10
0 1 1 2 3 5 8 13 21 34

```

How it works:

Starting from the right (because J programs are read from right to left),

`2-~ 6` The `~` operator reverses the argument to the verb so this is the same as `6-2`

Ignoring the section in brackets for now, `0 1(...)@[&0~ x`takes the verb in the brackets and executes it `x` times using the list `0 1` as its input - `~` again reverses the arguments here, giving `x (...)@[&0 ] 0 1`, meaning I can keep the input at the end of the function.

Within the brackets is a fork `],+/&(_2&{.)` which is made up of three verbs - `]`, `,` and `+/&(_2&{.)`.

A fork takes three verbs `a b c` and uses them like this: `(x a y) b (x c y)` where `x` and `y` are the arguments to the fork. The `,` is the centre verb in this fork and joins the results of `x ] y` and `x +/&(_2&{.) y` together.

`]` returns the left argument unaltered so `x ] y` evaluates to `x`.

`+/&(_2&{.)` takes the last two items from the given list `(_2&{.)` \- in this case `0 1` \- and then adds them together `+/` (the `&`s just act as glue).

Once the verb has operated once the result is fed back in for the next run, generating the sequence.
> 2 votes

# Answer
## TI-Basic, 43 characters

```
:1→Y:0→X
:For(N,1,N
:Disp X
:Y→Z
:X+Y→Y
:Z→X
:End

```

This code can be directly inserted into the main program, or made into a separate program that is referenced by the first.
> 2 votes

# Answer
### APL (33)

```
{⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}

```

Usage:

```
   {⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}7
0 1 1 2 3 5 8

```
> 2 votes

# Answer
# Powershell - 35 characters

Powershell accepts pipeline **input**, so I'm of the belief that the `n |` in `n | <mycode>` shouldn't be against my count, but instead is just a part of initiating a "function" in the language.

The first solution assumes we start at 0:

```
%{for($2=1;$_--){($2=($1+=$2)-$2)}}

```

The second solution assumes we can start at 1:

```
%{for($2=1;$_--){($1=($2+=$1)-$1)}}

```

Example invocation: `5 | %{for($2=1;$_--){($1=($2+=$1)-$1)}}`

Yields:

```
1
1
2
3
5

```

Interestingly, attempts to avoid the overhead of the `for()` loop resulted in the same character count: `%{$2=1;iex('($1=($2+=$1)-$1);'*$_)}`.
> 1 votes

# Answer
# FALSE, 28 bytes

```
0 1- 1 10[$][@@$@+$." "@1-]#

```
> 1 votes

# Answer
## Python, 43 chars

Here are three fundamentally different one-liners that don't use Binet's formula.

```
f=lambda n:reduce(lambda(r,a,b),c:(r+[b],a+b,a),'.'*n,([],1,0))[0]
f=lambda n:map(lambda x:x.append(x[-1]+x[-2])or x,[[0,1]]*n)[0]
def f(n):a=0;b=1;exec'print a;a,b=b,a+b;'*n

```

I've never abused `reduce` so badly.
> 1 votes

# Answer
# dc, 32 characters:

This will actually always show the two first 1's, so the function only work as expected *for N \>= 2*.

```
?2-sn1df[dsa+plarln1-dsn0<q]dsqx

```

# C, 75 characters:

Not as cool as the accepted answer, but shorter and way faster:

```
main(n,t,j,i){j=0,i=scanf("%d",&n);while(n--)t=i,i=j,printf("%d\n",j+=t);}

```
Extra:

# CL, 64 characters:

One of my most used bookmarks this semester has an interesting example which is shorter than many some of the other ones here, and it's just a straight-forward invocation of the `loop` macro -- basically just one statement! Stripped it for all the whitespace I could:

```
(loop repeat n for x = 0 then y and y = 1 then(+ x y)collect y)

```

Quite short, and nice and readable! To read input, `n` (including surrounding whitespaces) can be replaced with `(read)`, adding 3 characters.
> 1 votes

# Answer
# Python 2, 38 Bytes

An improvement on a previously posted solution:

```
a=b=1
exec'print a;a,b=b,a+b;'*input()

```

This uses `exec` and string multiplication to avoid loops.

# Python 3, 46 Bytes

Not quite as efficient in Python 3:

```
a=b=1
exec('print(a);a,b=b,a+b;'*int(input()))

```
> 1 votes

# Answer
# C99, 58 characters

The following function fills an array of integers with the first `n` values from the Fibonacci sequence starting with 0.

```
void f(int*a,int n){for(int p=0,q=1;n--;q+=*a++)*a=p,p=q;}

```

Test harness, taking `n` as a command line argument:

```
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
     int n = (argc > 1) ? atoi(argv[1]) : 1;
     int a[n];
     f(a, n);
     for (int i = 0; i < n; ++i)
          printf("%d\n", a[i]);
}

```
> 0 votes

# Answer
# Lua, 85 bytes

I am learning Lua so I would like to add this language to the pool.

```
function f(x)
    return (x<3) and 1 or f(x-1)+f(x-2)
end
for i=1,io.read() do
    print(f(i))
end

```

and the whole thing took 85 characters, with the parameter as a command line argument. Another good point is that is easy to read.
> 0 votes

# Answer
## Q 24

```
f:{{x,sum -2#x}/[x;0 1]}

```

First n fibonacci numbers
> 0 votes

# Answer
## CoffeeScript, 48

```
f=(n,i=1,j=1)->(console.log i;f n-1,j,i+j)if n>0

```

65 in js:

```
function f(n,i,j){if(n>0)console.log(i),f(n-1,(j=j||1),(i||1)+j)}

```
> 0 votes

# Answer
## PHP, 87

```
function f($n,$a=array(0,1)){echo' '.$a[0];$n>0?f(--$n,array($a[1],array_sum($a))):'';}

```

Uses `array_sum` and recursive function to generate series.

Eg:

```
 $ php5 fibo.php 9
 0 1 1 2 3 5 8 13 21 34

```
> 0 votes

# Answer
**F#, 123**

```
let f n = Seq.unfold(fun (i,j)->Some(i,(j,i+j)))(0,1)|>Seq.take n
f 5|>Seq.iter(fun x->printfn "%i" x)

```
> 0 votes

# Answer
**Scala, 65 characters**

```
(Seq(1,0)/:(3 to 9)){(s,_)=>s.take(2).sum+:s}.sorted map println

```

This prints, for example, the first 9 Fibonacci numbers. For a more useable version taking the sequence length from console input, 70 characters are required:

```
(Seq(1,0)/:(3 to readInt)){(s,_)=>s.take(2).sum+:s}.sorted map println

```

Beware the use of a Range limits this to Int values.
> 0 votes

# Answer
# FALSE, 20 characters

```
^1@[1-$][@2ø+$.\9,]#

```

Input should be on the stack before running this.
> 0 votes

# Answer
# Pyt, 3 bytes

```
ř⁻Ḟ

```

Try it online!

```
ř creates an array [1, 2, 3, ..., x]
⁻ decrements every item once (as Ḟ is 0 indexed)
Ḟ for every item in x converts it to it's fibonacci equivalent

```
> 0 votes

# Answer
# x86 machine code - 379 bytes

The version with ELF headers scoring 484 bytes:

```
00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0100 0000 c080 0408 3400 0000  ............4...
00000020: 0000 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
00000030: 0000 0000 0100 0000 0000 0000 0080 0408  ................
00000040: 0000 0000 e401 0000 0010 0000 0500 0000  ................
00000050: 0010 0000 0100 0000 0000 0000 0090 0408  ................
00000060: 0000 0000 0000 0000 0000 1000 0600 0000  ................
00000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
00000080: 51b9 0090 0408 8801 31c0 ba01 0000 00eb  Q.......1.......
00000090: 0351 89c1 31c0 89c3 43b0 04cd 8031 c099  .Q..1...C....1..
000000a0: 4259 c300 0000 0000 0000 0000 0000 0000  BY..............
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000c0: 31c0 9942 b903 9004 08c6 4101 0ac6 4102  1..B......A...A.
000000d0: 01c6 4103 013a 7103 0f84 ff00 0000 3a71  ..A..:q.......:q
000000e0: 0374 2680 4103 050f b641 036b c008 0041  .t&.A....A.k...A
000000f0: 048a 4104 e887 ffff ff80 6904 30c6 4103  ..A.......i.0.A.
00000100: 0183 e903 3a71 0375 da8a 4104 e86f ffff  ....:q.u..A..o..
00000110: ff3a 7106 0f84 ba00 0000 0fb6 4105 8841  .:q.........A..A
00000120: 060f b641 0788 4105 0fb6 4107 0041 06c6  ...A..A...A..A..
00000130: 4107 003a 7106 0f84 8800 0000 c641 0701  A..:q........A..
00000140: fe49 063a 7106 0f84 7800 0000 c641 0702  .I.:q...x....A..
00000150: fe49 063a 7106 0f84 6800 0000 c641 0703  .I.:q...h....A..
00000160: fe49 063a 7106 0f84 5800 0000 c641 0704  .I.:q...X....A..
00000170: fe49 063a 7106 744c c641 0705 fe49 063a  .I.:q.tL.A...I.:
00000180: 7106 7440 c641 0706 fe49 063a 7106 7434  q.t@.A...I.:q.t4
00000190: c641 0707 fe49 063a 7106 7428 c641 0708  .A...I.:q.t(.A..
000001a0: fe49 063a 7106 741c c641 0709 fe49 063a  .I.:q.t..A...I.:
000001b0: 7106 7410 fe41 08fe 4109 fe49 060f b641  q.t..A..A..I...A
000001c0: 0688 4107 c641 0601 83c1 033a 7106 0f85  ..A..A.....:q...
000001d0: 46ff ffff 3a71 030f 8501 ffff ffb3 0031  F...:q.........1
000001e0: c040 cd80                                .@..

```

Headerless version (that is the one to be graded):

```
00000000: 67c6 4101 0a67 c641 0201 67c6 4103 0167  g.A..g.A..g.A..g
00000010: 3a71 030f 842a 0167 3a71 0374 2e67 8041  :q...*.g:q.t.g.A
00000020: 0305 6667 0fb6 4103 666b c008 6700 4104  ..fg..A.fk..g.A.
00000030: 678a 4104 e80d 0167 8069 0430 67c6 4103  g.A....g.i.0g.A.
00000040: 0166 83e9 0367 3a71 0375 d267 8a41 04e8  .f...g:q.u.g.A..
00000050: f200 673a 7106 0f84 df00 6667 0fb6 4105  ..g:q.....fg..A.
00000060: 6788 4106 6667 0fb6 4107 6788 4105 6667  g.A.fg..A.g.A.fg
00000070: 0fb6 4107 6700 4106 67c6 4107 0067 3a71  ..A.g.A.g.A..g:q
00000080: 060f 84a3 0067 c641 0701 67fe 4906 673a  .....g.A..g.I.g:
00000090: 7106 0f84 9200 67c6 4107 0267 fe49 0667  q.....g.A..g.I.g
000000a0: 3a71 060f 8481 0067 c641 0703 67fe 4906  :q.....g.A..g.I.
000000b0: 673a 7106 0f84 7000 67c6 4107 0467 fe49  g:q...p.g.A..g.I
000000c0: 0667 3a71 0674 6167 c641 0705 67fe 4906  .g:q.tag.A..g.I.
000000d0: 673a 7106 7452 67c6 4107 0667 fe49 0667  g:q.tRg.A..g.I.g
000000e0: 3a71 0674 4367 c641 0707 67fe 4906 673a  :q.tCg.A..g.I.g:
000000f0: 7106 7434 67c6 4107 0867 fe49 0667 3a71  q.t4g.A..g.I.g:q
00000100: 0674 2567 c641 0709 67fe 4906 673a 7106  .t%g.A..g.I.g:q.
00000110: 7416 67fe 4108 67fe 4109 67fe 4906 6667  t.g.A.g.A.g.I.fg
00000120: 0fb6 4106 6788 4107 67c6 4106 0166 83c1  ..A.g.A.g.A..f..
00000130: 0367 3a71 060f 8521 ff67 3a71 030f 85d6  .g:q...!.g:q....
00000140: fe00 0000 6651 66b9 7801 0000 6788 0166  ....fQf.x...g..f
00000150: 31c0 66ba 0100 0000 eb05 6651 6689 c166  1.f.......fQf..f
00000160: 31c0 6689 c366 43b0 04cd 8066 31c0 6699  1.f..fC....f1.f.
00000170: 6642 6659 c300 0000 0000 00              fBfY.......

```

Calculates (possibly) \\$ \infty \\$ fibonacci numbers.
> 0 votes

# Answer
# Japt `-m`, ~~4~~ 3 bytes

Starts from `0`.

```
MgU

```

Try it
> 0 votes

# Answer
### x86 machine code - 23 bytes

```
08048060 <_start>:
 8048060:       6a 01                   push   0x1
 8048062:       59                      pop    ecx
 8048063:       6a 02                   push   0x2
 8048065:       5f                      pop    edi

08048066 <_start.loop>:
 8048066:       89 da                   mov    edx,ebx
 8048068:       89 c8                   mov    eax,ecx
 804806a:       01 d0                   add    eax,edx
 804806c:       89 c6                   mov    esi,eax
 804806e:       89 c3                   mov    ebx,eax
 8048070:       89 f0                   mov    eax,esi
 8048072:       89 c1                   mov    ecx,eax
 8048074:       47                      inc    edi
 8048075:       eb ef                   jmp    8048066 <_start.loop>

```

You can assembling and debug it using GDB, in debugger set a breakpoint at `_start` label (NASM style) and type `s` (mean `single-step`) command, see the output in register `eax`.

Output : `0 1 1 2 ...`
> 0 votes

# Answer
# JavaScript (V8), 37 bytes

```
f=(n,i=0,j=1)=>--n?i+' '+f(n,j,i+j):i

```

Try it online!
> 0 votes

# Answer
# Python 3, 45 bytes

```
f=lambda n,i=0,j=1:n and[i,*f(n-1,j,i+j)]or[]

```

Try it online!

A similar implementation to my JavaScript answer.
> 0 votes

# Answer
# Neim, 3 bytes

```
f   # Fibonacci list
 I  # First line of input
   # Get first b elements of a

```

Try it online!
> 0 votes

---
Tags: code-golf, fibonacci
---


# Question
Title: Exponentially Slimy Programming: Stacking Minecraft Slimes
Slimes are cube shaped enemies in Minecraft that break into multiple smaller versions of themselves when killed. For the purposes of this challenge we'll depict them as an 8×8 pixel image with 3 colors:

← True 8×8 version.

The precise RGB colors are:

* `0, 0, 0` for the eyes and mouth
* `110, 170, 90` for the central, darker green
* `116, 196, 96` for the outer, lighter green

# Challenge

Write a program or function that takes in a positive integer N and outputs an image of N sizes of slimes packed into a rectangle. Going from left to right, the image should follow the pattern of having:

* A stack of 2(N-1) 8×8 slimes.
* A stack of 2(N-2) 16×16 slimes.
* A stack of 2(N-3) 32×32 slimes.
* And so on until the stack only contains one slime.

The slime images larger than the 8×8 version () are generated by nearest-neighbor upsampling (i.e. just doubling all the pixels). Note that you must use the exact slime design and colors given here.

The final image will contain 2N-1 slimes and be 2(N+3)-8 pixels wide and 2(N+2) pixels tall.

The image may be output in any common image file format, saved to a file or printed/returned as a raw data stream, or directly displayed during runtime.

**The shortest code in bytes wins.**

# Examples

Your program should produce these exact results.

N = 1:

N = 2:

N = 3:

N = 4:

N = 5:

N = 6:

Larger N should work just as well.

# Answer
# MATL, ~~77~~ ~~76~~ 74 bytes

```
:"')^.,9&Xze`}+.E=p'F3ZaQ8e@qWt3$Y"G@-W1X"]&h[OOO;11 17E]5*29 7U24hhE&vEYG

```

The code works in this commit, which is earlier than the challenge.

You can try it in **MATL online**. This interpreter is still experimental. If it doesn't work, try refreshing the page and pressing "Run" again.

Here's an example run in the offline interpreter:

### Explanation

```
:                     % Input N implicitly. Generate range [1 2 ... N]
"                     % For each k in [1 2 ... N]
  ')^.,9&Xze`}+.E=p'  %   Compressed string
  F3Za                %   Decompress with target alphabet [0 1 2]
  Q                   %   Add 1
  8e                  %   Reshape into 8×8 array containing values 1, 2, 3
  @qW                 %   Push 2 raised to k-1
  t                   %   Duplicate
  3$Y"                %   Repelem: interpolate image by factor 2 raised to k-1
  G@-W                %   Push 2 raised to N-k
  1X"                 %   Repmat: repeat the array vertically. Gives a vertical strip
                      %   of repeated subimages
]                     % End for each
&h                    % Concatenate all vertical strips horizontally. This gives a big
                      % 2D array containing 1, 2, 3, which represent the three colors
[OOO;11 17E]5*        % Push array [0 0 0; 11 17 9] and multiply by 5
29 7U24hhE            % Push array [29 49 24] and multiply by 2
&vE                   % Concatenate the two arrays vertically and multiply by 2.
                      % This gives the colormap [0 0 0; 110 170 90; 116 196 96]
YG                    % Take the array and the colormap and display as an image

```
> 21 votes

# Answer
# Dyalog APL, ~~118~~ 113 bytes

`('P3',⌽∘⍴,255,∊)(3↑(116 196 96)(110 170 90))[⊃,/i{⊃⍪/⍵⍴⊂⍺⌿⍺/8 8⍴∊22923813097005 926134669613412⊤¨⍨⊂32⍴3}¨⌽i←2*⍳⎕]`

assuming `⎕IO=0`

From right to left:

`i←2*⍳⎕` powers 1 2 4 ... 2n-1

`i{ }¨⌽i` iterate over powers (with ) and reversed powers ()

`⊤¨⍨⊂32⍴3` decode each of the numbers on the left as 32 ternary digits

`8 8⍴∊` flatten and reshape to 8×8

`⍺⌿⍺/` replicate each row and column  times

`⍵⍴⊂` take  copies

`⊃⍪/` and stack them vertically

`⊃,/` join all results horizontally

`3↑(116 196 96)(110 170 90)` colours; `3↑` extends them with `(0 0 0)`

`[ ]` index the colours with each element of the matrix; result is a matrix of RGBs

`('P3',⌽∘⍴,255,∊)` is a "train" - a function that returns `'P3'` followed by the reversed shape of the argument, `255`, and the argument flattened.
> 15 votes

# Answer
# JavaScript (ES7), 326 ~~327~~ bytes

```
n=>{x=(d=document).body.appendChild(c=d.createElement`canvas`).getContext`2d`;c.width=2*(c.height=4*(p=2**n)));for(i=0;i<n;i++){c=-1;for(j of[...'0001000001111110022112200221122011111110011121110111111000010000'])for(x.fillStyle=['#74c460','#6eaa5a','#000'][j],c++,k=0;k<p;)x.fillRect(c%8*(_=2**i)+_*8,~~(c/8)*_+_*8*k++,_,_)}}

```

**Ungolfed ES6 Version**

Try it yourself.

```
(n=>{
    x=(d=document).body.appendChild(c=d.createElement`canvas`).getContext`2d`;
    c.width=2*(c.height=4*(p=Math.pow(2,n)));
    for(i=0;i<n;i++){
        c=-1;
        for(j of[...'0001000001111110022112200221122011111110011121110111111000010000'])
            for(x.fillStyle=['#74c460','#6eaa5a','#000'][j],c++,k=0;k<p;)
                x.fillRect(c%8*(_=Math.pow(2,i))+_*8,~~(c/8)*_+_*8*k++,_,_)
    }
})(4);

```

The only difference between the ES7 and ES6 version is using `**` instead of `Math.pow()`. You can also see, how you can invoke the function – in this example with `n=4`.

**Result**

---

**Edits**

* saved *1 byte* \- found an unnecessary trailing semicolon `;`

---

This is pretty slow and might take some time for numbers greater 10.
> 12 votes

# Answer
# C, 220 bytes

```
x,y,r;f(n){
printf("P3 %d %d 255 ",(8<<n)-8,4<<n);
for(y=0;y<4<<n;++y)for(r=0;r<n;++r)for(x=0;x<8<<r;++x)
puts("110 170 90\0 116 196 96\0 0 0 0"+12*
(117-"` t5L\rL\ru5tst5` "[x>>r+2|(y>>r)%8*2]>>(x>>r)%4*2&3));}

```

I added useless newlines for readability, score is without these newlines.

Defines a function `f(n)` that outputs a plain PPM image on stdout.
> 7 votes

# Answer
# Mathematica, ~~267~~ ~~255~~ ~~254~~ ~~225~~ 212 bytes

```
G=10{11,17,9};Image@Join[##,2]&@@Table[Join@@Table[ImageData@ImageResize[Image[{t={g=G+{6,26,6},g,g,G,g,g,g,g},f={g,a=##&[G,G,G],a,g},e={g,b=0g,b,G,G,b,b,g},e,{a,a,G,g},{g,a,b,a},f,t}/255],4*2^j],2^(#-j)],{j,#}]&

```

*Saved ~~29~~ 42 bytes thanks to Martin Ender*

Golfing suggestions welcome, especially for constructing the 8 by 8 (by 3) array `s`. Unfortunately, there is no "`ArrayResize`" analogue for `ImageResize`, so the array needs to be converted to an image (`Image`) before resizing, and then back to an array (`ImageData`) to do the `Join`ing.

Ungolfed:

```
(* dark green, light green, black *)
G = 10 {11, 17, 9};
g = G + {6, 26, 6};
b = 0 g;

(* abbreviation for triple G sequence, top row, forehead, eye level *)
a = ##&[G, G, G];
t = {g, g, g, G, g, g, g, g};
f = {g, a, a, g};
e = {g, b, b, G, G, b, b, g};

(* slime *)
s =
  {
    t,
    f,
    e,
    e,
    {a, a, G, g},
    {g, a, b, a},
    f,
    t
  }/255;

(* jth column *)
c[n_, j_] := Join @@ Table[ImageData@ImageResize[Image[s], 4*2^j], 2^(n - j)]

(* final program *)
Image@Join[##, 2] & @@ Table[c[#, j], {j, #}] &

```
> 7 votes

# Answer
# Python 2.7: ~~424~~ ~~412~~ ~~405~~ ~~376~~ 357 Bytes

I'm a bit new to golfing.... here we go

```
from numpy import*
import PIL
def c(n,col):e=log2((col+8)/8)//1;r=2**e;t=2**(n-e-1);return tile(repeat(array([0x2df0777ca228b9c18447a6fb/3**i%3for i in range(64)],dtype=int8).reshape([8,8])[:,(col-(8*r-8))//r],r),t)
n=input();i=PIL.Image.fromarray(column_stack([c(n,col) for col in range(2**(n+3)-8)]),mode='P');i.putpalette('t\xc4`n\xaaZ'+' '*762);i.show()

```

ungolfed and length tested..

```
from numpy import*
import PIL

def c(n,col): #creates array for a given column
    s = array([0x2df0777ca228b9c18447a6fb/3**i%3for i in range(64)],dtype=int8).reshape([8,8]) #slime template (golfed inline)
    e=log2((col+8)/8)//1 #exponent for tiles and repititions
    r=2**e #number of repitions (scale factor)
    t=2**(n-e-1) #number of tiles (vertically)
    return tile(
            repeat(
             s[:,(col-(8*r-8))//r] #select appropriate column from template
              ,r) #repeat it r times
               ,t) #tile it t times

n = input()
arr = column_stack([c(n,col) for col in range(2**(n+3)-8)]) #create image array by stacking column function
i=PIL.Image.fromarray(arr,mode='P'); #colormap mode
i.putpalette('t\xc4`n\xaaZ'+' '*762); #set colormap
i.show()

s = r'''from numpy import*
import PIL
def c(n,col):e=log2((col+8)/8)//1;r=2**e;t=2**(n-e-1);return tile(repeat(array([0x2df0777ca228b9c18447a6fb/3**i%3for i in range(64)],dtype=int8).reshape([8,8])[:,(col-(8*r-8))//r],r),t)
n=input();i=PIL.Image.fromarray(column_stack([c(n,col) for col in range(2**(n+3)-8)]),mode='P');i.putpalette('t\xc4`n\xaaZ'+' '*762);i.show()'''

print len(s)

```

edit1: removed `sys.argv[1]` in favor of `raw_input()` to save extra import statement

edit2: shortened PIL import: removed `from Image` added `PIL.`

edit3: Thanks @Sherlock9 for the hex encode of the slime template

edit4: didn't need function def and used `input()` instead of `raw_input()`
> 5 votes

# Answer
# R, ~~378~~ ~~356~~ ~~346~~ 334 bytes

```
f=function(n){r=rep;k=r(0,4);m=r(1,6);L=c();for(i in 1:n)L=cbind(L,r(max(L,0)+2^(n-i):1,e=2^(i-1)));png(w=sum(w<-4*2^(1:n)),h=sum(h<-r(8,2^(n-1))));layout(L,w,h);for(i in 1:max(L)){par(mar=k);image(matrix(c(0,0,0,1,k,0,m,0,0,1,1,1,2,r(1,10),0,0,r(r(c(2,1,2,0),e=2),2),m,k,1,k),nr=8),col=c("#74C460","#6EAA5A",1),ax=F,an=F)};dev.off()}

```

Saves as a png file. Indented, with linefeeds:

```
f=function(n){
    r=rep
    k=r(0,4)
    m=r(1,6)
    L=c()
    for(i in 1:n)L=cbind(L,r(max(L,0)+2^(n-i):1,e=2^(i-1)))
    png(w=sum(w<-4*2^(1:n)),h=sum(h<-r(8,2^(n-1))))
    layout(L,w,h)
    for(i in 1:max(L)){
        par(mar=k)
        image(matrix(c(0,0,0,1,k,0,m,0,
                       0,1,1,1,2,r(1,10),0,
                       0,r(r(c(2,1,2,0),e=2),2),
                       m,k,1,k),
                     nr=8),
              col=c("#74C460","#6EAA5A",1),ax=F,an=F)
    }
    dev.off()
}

```

N=2:
N=3:
N=4:

Some explanations:

Here's the matrix that's being plotted (0 represent lightgreen, 1 darkgreen and 2 black; the matrix is tilted because columns are the y-axis and rows the x-axis):

```
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0    0    0    1    0    0    0    0
[2,]    0    1    1    1    2    2    1    0
[3,]    0    1    1    1    2    2    1    0
[4,]    1    1    1    1    1    1    1    1
[5,]    0    1    2    1    1    1    1    0
[6,]    0    1    1    1    2    2    1    0
[7,]    0    1    1    1    2    2    1    0
[8,]    0    0    1    0    0    0    0    0

```

Each call to `image` plot that matrix (with each integer corresponding to a color). For N=4, here is L (the layout matrix, each unique number represents one single plot), w (the widths of the matrix columns) and h (the heights of the matrix rows):

```
> L
     [,1] [,2] [,3] [,4]
[1,]    8   12   14   15
[2,]    7   12   14   15
[3,]    6   11   14   15
[4,]    5   11   14   15
[5,]    4   10   13   15
[6,]    3   10   13   15
[7,]    2    9   13   15
[8,]    1    9   13   15
> w
[1]  8 16 32 64
> h
[1] 8 8 8 8 8 8 8 8

```
> 1 votes

# Answer
# Java 8, 512 bytes

```
import java.awt.*;n->new Frame(){{add(new Panel(){public void paint(Graphics g){for(int N=n,o=0,p=1,t,q,u;N-->0;o+=8*p,p*=2)for(t=(int)Math.pow(2,N);t-->0;g.setColor(new Color(116,196,96)),g.fillRect(o,q=u*t,u,u),g.setColor(new Color(110,170,90)),g.fillRect(p+o,p+q,6*p,6*p),g.fillRect(o,4*p+q,p,p),g.fillRect(3*p+o,q,p,p),g.fillRect(7*p+o,5*p+q,p,p),g.fillRect(3*p+o,7*p+q,p,p),g.setColor(Color.BLACK),g.fillRect(p+o,2*p+q,2*p,2*p),g.fillRect(5*p+o,2*p+q,2*p,2*p),g.fillRect(4*p+o,5*p+q,p,p))u=8*p;}});show();}}

```

**Results for \\$n=4,5,6\\$:**

**Explanation:**

```
import java.awt.*;       // Required import for almost everything
n->                      // Method with integer parameter and Frame return-type
  new Frame(){           //  Create the Frame
   {                     //   In an inner code-block:
     add(new Panel(){    //    Add a Panel we can draw on:
       public void paint(Graphics g){
                         //     Overwrite its paint method:
         for(int N=n,    //      Create a copy of the (effectively final) input
                 o=0,    //      Offset integer, starting at 0
                 p=1,    //      Power integer, starting at 1
                 t,      //      Inner loop integer, starting uninitialized
                 q,u;    //      Temp integers, starting uninitialized
             N-->0       //      Loop `N` in the range (`n`, 0]:
             ;           //        After every iteration:
              o+=8*p,    //         Increase the offset by 8 times the power
              p*=2)      //         And go to the next power by doubling it
           for(t=(int)Math.pow(2,N);
                         //       Set `t` to 2^`N`
               t-->0     //       Inner loop `t` in the range (2^`N`, 0]:
               ;         //         After every iteration:
                g.setColor(new Color(116,196,96)),
                         //          Set the color to the lighter green
                g.fillRect(o,q=u*t,u,u),
                         //          Draw the background rectangle,
                         //          and set `q` to `u*t` to save bytes
                g.setColor(new Color(110,170,90)),
                         //          Change the color to the darker green
                g.fillRect(p+o,p+q,6*p,6*p),
                         //          Draw the inner rectangle
                g.fillRect(o,4*p+q,p,p),
                         //          Draw the left dot
                g.fillRect(3*p+o,q,p,p),
                         //          Draw the top dot
                g.fillRect(7*p+o,5*p+q,p,p),
                         //          Draw the right dot
                g.fillRect(3*p+o,7*p+q,p,p),
                         //          Draw the bottom dot
                g.setColor(Color.BLACK),
                         //          Change the color to black
                g.fillRect(p+o,2*p+q,2*p,2*p),
                         //          Draw the left eye
                g.fillRect(5*p+o,2*p+q,2*p,2*p),
                         //          Draw the right eye
                g.fillRect(4*p+o,5*p+q,p,p))
                         //          Draw the mouth
             u=8*p;}});  //        Set `u` to `8*p` to save bytes
     show();}}           //    And afterwards show the Frame

```
> 1 votes

---
Tags: code-golf, graphical-output, recursion
---


title: De-interleave log lines: HARD MODE

text:
# Question
Title: De-interleave log lines: HARD MODE
In the face of some regrettable rules that turned the original into a glorified sorting task, I am posting a more challenging variant. Shout out to Luis Mendo for the suggestion of how to improve the original challenge.

---

You've inherited a server that runs several apps which all output to the same log.

Your task is to de-interleave the lines of the log file by source. Fortunately for you, the person who wrote all the apps was nice enough to leave tags indicating their source.

## Logs

Each line will look something like this:

```
[app_name] Something horrible happened!

```
* App tags are always between square brackets and will contain only alphanumeric characters and underscores.
* App tags are nonempty
* There may be other square brackets later on any given line, but none will form a valid tag.
* There will always be at least one non-space character after a tag.
* The log as a whole may be empty.
* There is no limit to how many unique app tags will be present in the file.

In some cases, an app tag may be missing. When this is the case, the log line belongs to the most recently logged app.

* The first line of the log will always begin with an app tag
* A line beginning with `[` is not necessarily tagged. If there is an invalid character between the initial square brackets or no `]`, then the line is not tagged.
* No empty lines appear in the log

## Expected Output

You should output several fully-separated logs with the app tags removed from each log line where they were present. You do not need to preserve leading whitespace on any log line.

Output logs must be in some sort of key-value mapping or reasonable equivalent. A non-exhaustive list of valid output formats:

* A file named after the app tag for each app
    + You may assume that the output files do not already exist in the output directory in this case.
* A dictionary/map/hash/whatever that uses app tags as keys and a newline-separated string of the log lines as values.
* A long concatenated string separated by blank lines and preceded by app tags
* A list of \[key, value\] lists
* A JSON string with app tags as keys and arrays of log lines as values
* A Markdown document with app tags as headers and leading `#`s of any line escaped with backslashes.
* A Javascript function that takes a string as input and outputs the associated log as a newline-separated string.

Basically, if you can't tell which app the log lines came from, the output is invalid.

## Example

An entire log might look like this:

```
[weather] Current temp: 83F
[barkeep] Fish enters bar
Fish orders beer
[stockmarket] PI +3.14
[PI announced merger with E]
[barkeep] Fish leaves bar
[weather] 40% chance of rain detected
[ I have a lovely bunch of coconuts

```

Which should output three different logs:

weather:

```
Current temp: 83F
40% chance of rain detected
[ I have a lovely bunch of coconuts

```

barkeep:

```
Fish enters bar
Fish orders beer
Fish leaves bar

```

stockmarket:

```
PI +3.14
[PI announced merger with E]

```

You are not given the names of the app tags ahead of time. You must determine them only by analyzing the log file.

## Rules and Scoring

* This is , so shortest code wins.
* Standard rules and loopholes apply
* Use any convenient IO format, provided that each input line is represented as a string, not a pre-parsed tag + message. *Parsing is part of this challenge*.
* Output log lines for each app must appear in the same order that they did in the original log.
* You may assume that the input log contains only ASCII characters.

# Answer
> 2 votes
# Python 3.8, 95 bytes

```
import re
lambda x:[((t:=re.match(r'\[(\w*)\]',s)or t)[1],s.split(t[0])[-1].strip())for s in x]

```

Try it online!

(Expanded TIO example with input)

### Explanation:

Python 3.8 is required for the `:=` operator. This takes a list of strings as input, and outputs a list of `(tag, body)` tuples. First, it uses a Regex match to get the tag:

```
t:=re.match(r'\[(\w*)\]',s)or t)

```

This matches any initial sequence of word characters (alphanumeric + underscore) enclosed in square brackets, with the words as a capturing group. If the string does match this regex, `t` will be a `match` object with two elements: the full match and the group. For example, if the string is `[tag] body`, the `match` will have the elements `[tag]` and `tag`.

If the string does not match this regex, then `re.match()` returns None. The code becomes `t = None or t`, which is just `t = t`, so the tag keeps its value from the previous line. If the first line didn't have a match, this would cause an error, but we don't need to worry about that!

The code then constructs the tuple `t[1], s.split(t[0])[-1].strip()`, where `t[1]` is the capturing group (the tag without square brackets) and `t[0]` is the tag *with* square brackets. Splitting the string on the full tag isolates the body, whether or not the tag actually exists in the string.

# Answer
> 2 votes
# Retina 0.8.2, 95 bytes

```
+m`^(\[\w+] ).*¶(?!\[\w+])
$&$1
O$`(\w+).*
$1
¶
¶¶
rm`(?<=^\1.*¶)¶(.\w+].)

(?<=(^|¶¶).\w+]).
¶

```

Try it online! Explanation:

```
+m`^(\[\w+] ).*¶(?!\[\w+])
$&$1

```

Tag all untagged lines.

```
O$`(\w+).*
$1

```

Sort the lines, taken from my answer to the original challenge.

```
¶
¶¶

```

Double-space the lines.

```
rm`(?<=^\1.*¶)¶(.\w+].)

```

Remove duplicate tags and the empty line before them. This means that the only empty lines left are those that delimit the separate tags.

```
(?<=(^|¶¶).\w+]).
¶

```

Move the tag to its own line.

# Answer
> 2 votes
# perl -Mfeature=say -n, 47 46 bytes

(Saved one byte courtesy of @Dom Hastings)

```
$;=$1 if s/^\[(\w+)\] +//;$;{$;}.=$_}{say for%;

```

Try it online!

## How does this work?

First, the effect of the `-n` switch. This causes Perl to wrap the program in a loop, which reads the input and executes the body for each line. But it does so in a very unsophisticated way, it wraps the body in the loop before doing any parsing, as follows:

```
perl -ne 'TEXT'

```

gets turned into

```
LINE: while (defined($_ = readline ARGV)) {
    TEXT;
}

```

But that means if your `TEXT` is of the form `LOOP_BODY}{FINAL_STATEMENT`, you end up with the program:

```
LINE: while (defined($_ = readline ARGV)) {
    LOOP_BODY
}
{
    FINAL_STATEMENT;
}

```

We're using this trick just to save a few bytes over an `END` block.

In the program itself, we're using two variables to do our bookkeeping. `$;` will contain the current tag, and in the hash `%;`, we track the lines for each tag. Now, for each line of the input, we check to see if it starts with a tag, and if so, we strip it off from the line, and remember the tag:

```
$; = $1 if          # Remember the tag if,
s/^\[(\w+)\] +//;   # we can strip of a tag

```

We then concatenate the current line (stripped from a tag, if present) to the set of lines already collected for that tag -- if there are no such lines, we effectively concatenate it with the empty string:

```
$;{$;}.=$_   # Remember the current line

```

Finally, after reading all lines, we print the hash. Perl conveniently flattens a hash to a simple list if you treat it as a list, alternating the keys and values. This gives us output where each section is separated by a newline, and is headed by the tag.

```
say for%;    # Print the flattened hash

```

# Answer
> 1 votes
# 05AB1E, 22 bytes

```
vyD']¡н¦DžjÃÊi‚»]).¡#н

```

Input as a list of lines, output as a list of lists of multi-line strings.

Try it online (pretty-printed; feel free to remove the footer to see the actual output).

**Explanation:**

```
v                 # Loop `y` over each string of the (implicit) input-list:
 yD               #  Push line `y` twice
   ']¡           '#  Split the copy on "]"
      н           #  Only leave the first part
       ¦          #  Remove the leading character (the potential "[")
        D         #  Duplicate it
         žj       #  Push builtin string "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_"
           Ã      #  Only keep those characters in the string we duplicated
            Êi    #  If it is NOT equal to the string:
              ‚   #   Pair it with the previous line
               »  #   And join that pair with a newline delimiter
]                 # Close both the if-statement and loop
 )                # Wrap all values on the stack into a list
  .¡              # Group all strings by:
    #             #  Split the string on spaces
     н            #  And only leave the first part (the tag)
                  # (after which the result is output implicitly)

```

# Answer
> 1 votes
# AWK`-F]`, ~~122~~ ~~123~~ 113 bytes

Added a byte to fix a bug kindly pointed out by water\_ghosts.

Saved 10 bytes thanks to Giuseppe!!!

```
/^\[\w+\]/{a[l=$1][i++]=$2;next}{a[l][i++]=$0}END{for(k in a){print"\n",substr(k,2);for(j in a[k])print a[k][j]}}

```

Try it online!

# Answer
> 1 votes
# SimpleTemplate, 142 bytes

Well, this wasn't too hard.

This answer is a slightly modified version of: De-interleave log lines

```
{@callexplode intoL EOL,argv.0}{@eachL}{@if_ matches"@^(\[\w+\]) ?(.+)$@"M}{@setX"#{M.1} "}{@set_ M.2}{@/}{@setS.[X]S.[X],X,_,EOL}{@/}{@echoS}

```

---

**Ungolfed:**

Since this is quite unreadable, below is a readable version:

```
{@call explode into lines EOL, argv.0}
{@set storage null}
{@each lines as line}
    {@if line matches "@^(\[\w+\]) ?(.+)$@" match}
        {@set last "#{match.1} "}
        {@set line match.2}
    {@/}
    {@set storage.[last] storage.[last], last, line, EOL}
{@/}
{@echo storage}

```

---

**Changes:**

Some changes had to be done to work properly, with the new requirements. Below is a copy of the linked answer:

```
{@call explode into lines EOL, argv.0}
{@set storage null}
{@each lines as line}
    {@if line matches "@^(\[.*\])@" match}
        {@set storage.[match.1] storage.[match.1], line, EOL}
    {@/}
{@/}
{@echo storage}

```

Below is a full list of the changes:

* The regular expression was changed to match the remaining content, without a space, if present. (Quoting: "There will always be at least one non-space character after a tag.")
* Stores the "app" with an extra space, for later use and to normalize the lines (which may or may not have a space right after the "tag").
* Stores the remaining content, without the first space, into the `line` (`_` for the golfed version) variable
* Adds the "tag" before the `line` variable, which used to be part of the `line` variable.

As you can see, the changes aren't that significant. Move code, add extra space, add a variable to an output.

---

You can try this on: http://sandbox.onlinephpfunctions.com/code/eb5380ba1826530087fd92fa71d709c0b2d6de39

# Answer
> 0 votes
# Scala, 127 bytes

```
l=>((("",List[(String,String)]())/:l){case((p,m),s"[$t] $b")=>(t,(t,b)::m)case((p,m),b)=>(p,(p,b)::m)})._2.groupMap(_._1)(_._2)

```

Try it in Scastie (doesn't work in TIO)

Wow, this is long.

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