title: Matrix in Range

text:
# Question
Title: Matrix in Range
# The Challenge

Given an integer `n>0` output a `n+1 X n+1` matrix containing all integers from `1` to `2n` as shown in the test cases bellow

# Test Cases

```
n=1

1  2
2  2

n=2

1   2   4
2   3   4
4   4   4

n=5

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

n=10

1   2   3   4   5   6   7   8   9   10  20
2   3   4   5   6   7   8   9   10  11  20
3   4   5   6   7   8   9   10  11  12  20
4   5   6   7   8   9   10  11  12  13  20
5   6   7   8   9   10  11  12  13  14  20
6   7   8   9   10  11  12  13  14  15  20
7   8   9   10  11  12  13  14  15  16  20
8   9   10  11  12  13  14  15  16  17  20
9   10  11  12  13  14  15  16  17  18  20
10  11  12  13  14  15  16  17  18  19  20
20  20  20  20  20  20  20  20  20  20  20

```

I think that the pattern is pretty easy, so let's see who will give the shortest answer in bytes.
This is

# Rules

**Input** must be an integer (**1-indexed**)

**Output** can be a **matrix** (as shown in the test cases) or a **list of lists**

# Answer
# , 53 bytes

```
function(n)rbind(cbind(outer(1:n,1:n,`+`)-1,2*n),2*n)

```

Uses the `outer` "product" to generate all sums of the range `1,...,n` as a matrix, subtracts `1` from each, then `bind`s `2*n` as a column on the right and a row on the bottom, recycling as needed, and returns a matrix as the result.

Try it online!

# , 78 bytes

More naive implementation.

```
function(n){m=matrix(2*n,n+1,n+1)
for(i in seq(n))m[1:n,i]=(0:(2*n))[1:n+i]
m}

```

Try it online!
> 10 votes

# Answer
# Mathematica, ~~61~~ 46 bytes

```
ArrayFlatten@{{##-1&~Array~{#,#},2#},{2#,2#}}&

```

thanx @alephalpha for -15 bytes
> 7 votes

# Answer
# MATL, ~~12~~ 10 bytes

```
:&+q,!GEYc

```

Try it online!

### Explanation

```
:       % Input n (implicit). Push range [1 2 ... n]
&+      % matrix of pairwise additions
q       % Subtract 1
,       % Do twice
  !     %   Transpose
  GE    %   Push 2*n
  Yc    %   Concatenate that value to all rows, thus extending the matrix
        % End (implicit). Display (implicit)

```
> 5 votes

# Answer
# Haskell, 48 bytes

```
f n=[[i..n-1+i]++[2*n]|i<-[1..n]]++[2*n<$[0..n]]

```

Try it online!
> 5 votes

# Answer
# Octave, ~~38~~ ~~37~~ 35 bytes

```
@(n)[(x=1:n)+x'-1 z=~x'+2*n;z' 2*n]

```

Try it online!

or

```
@(n)~(k=blkdiag((x=1:n)+x'-1,0))*2*n+k

```

Try it online!
> 5 votes

# Answer
# Jelly, 11 bytes

```
+þḶ;€Ḥ;ḤzḤG

```

Try it online!
> 4 votes

# Answer
## JavaScript (ES6), 64 bytes

```
f=
n=>[...Array(n+1)].map((_,i,a)=>a.map((_,j)=>n-i&&n-j?i-~j:n+n))
```

```
<input type=number min=0 oninput="t.innerHTML=f(+this.value).map(a=>`<tr>${a.map(b=>`<td>${b}</td>`).join``}</tr>`).join``"><table id=t>
```
> 4 votes

# Answer
# Java 8, 99 bytes

Lambda from `Integer` to `int[][]` (e.g. `Function<Integer, int[][]>`). Surprisingly resistant to golfing.

```
n->{int p=n+1,o[][]=new int[p][p],i=0,r,c;while(i<p*p)o[r=i/p][c=i++%p]=r<n&c<n?r-~c:2*n;return o;}

```

Try It Online

## Ungolfed lambda

```
n -> {
    int
        p = n + 1,
        o[][] = new int[p][p],
        i = 0,
        r, c
    ;
    while (i < p * p)
        o[r = i / p][c = i++ % p] =
            r < n & c < n ?
                r - ~c
                : 2 * n
        ;
    return o;
}

```

## Acknowledgments

* -1 byte thanks to Kevin Cruijssen
> 4 votes

# Answer
# Python 2, ~~64~~ ~~62~~ 61 bytes

*-3 bytes thanks to Mr. Xcoder.*

```
lambda n:[range(i+1,i-~n)+[n*2]for i in range(n)]+[[n*2]*-~n]

```

Try it online!

I'm probably missing a key pattern though.

# Python 2, 76 bytes

```
lambda n:[[[n*2,i-~j][n-i and n-j>0]for j in range(n+1)]for i in range(n+1)]

```

Try it online!
> 3 votes

# Answer
# Pyth, 18 bytes

```
+m+rd+QdyQSQ]*]yQh

```

Maybe I am missing an obvious pattern (cc @totallyhuman)...

**Test Suite.**

**"Pretty print" Test Suite.**
> 3 votes

# Answer
# Proton,  ~~48~~  44 bytes

*-4 bytes thanks to @totallyhuman!*

```
n=>[(i+1..i-~n)+[n*2]for i:0..n]+[[n*2]*-~n]

```

Try it online!
> 2 votes

# Answer
# Japt, ~~17~~ 16 bytes

```
õ_óU pU*2ÃpUô@*2

```

Try it online!
> 2 votes

# Answer
# , 54 ~~63~~ ~~67~~ bytes

```
function(n)cbind(rbind(sapply(1:n-1,'+',1:n),2*n),2*n)

```

Try it online!

Thanks to @Guiseppe for the pointer for sapply and the 9 bytes
> 2 votes

# Answer
# Recursiva, 50 bytes

* Only 10 bytes shorter than python and thus it is official, Recursiva is not a golfing-language at all... It is an esolang though. :D

```
|{Ba+++++'PJ"	"W+Z~}B+~}'Va'+}'Va'AD'VaJ"	"W*;aADa

```

Try it online!
> 2 votes

# Answer
# Dyalog APL, 29 bytes

Requires `⎕IO←0`

```
{(S,⍨1+¯1 ¯1↓∘.+⍨⍳⍵+1)⍪S←2×⍵}

```

Try it online!

## How?

* `1+¯1 ¯1↓∘.+⍨⍳⍵+1` the upper-left portion of the array
* `(S,⍨...)⍪S←2×⍵` the corner
> 1 votes

# Answer
# C (gcc), ~~119~~ ~~116~~ ~~115~~ 107 bytes

```
i,j;f(n){for(;j<n;j++,printf("%d\n",2*n))for(i=0;i++<n;printf("%d\t",j+i));for(;j=i--;printf("%d\t",n*2));}

```

Try it online!
> 1 votes

# Answer
# Röda, 44 bytes

```
f n{seq 1,n|[[seq(_,_1+n-1)]+2*n];[[2*n]*n]}

```

Try it online!

Explanation:

```
f n{seq 1,n|[[seq(_,_1+n-1)]+2*n];[[2*n]*n]}
f n{                                       } /* Function f(n)         */
    seq 1,n                                  /* Sequence 1..n         */
           |                                 /* For each _1:          */
              seq(_,_1+n-1)                  /*   Sequence _1.._1+n-1 */
             [             ]                 /*   As list             */
                            +2*n             /*   Append 2*n          */
            [                   ]            /*   Push to the stream  */
                                   [2*n]     /* List [2*n]            */
                                        *n   /* Multiplied by n       */
                                  [       ]  /* Push to the stream    */

```
> 1 votes

# Answer
# \>\<\>, 84+2 Bytes

+2 for -v flag

Prints with tabs between values, and newlines between rows. Also prints a trailing tab on the last line.

Try it online

```
1:r:&r&)?\0:r:&r&(?\~$:@2*nao1+!
a0./:r:0~<.17+1o9\ \$:@$:@+n9o1+
   \&r&)?;$:@2*n /

```

## Pre-golfing

```
1>:r:&r&)?\0>    :r:&r&(?\~$:@2*nao1+\
            \+1o9n+@:$@:$/
 \                                   /
          \~0>:r:&r&)?;$:@2*n9o1+\
             \                   /

```
> 1 votes

# Answer
# SOGL V0.12, 22 bytes

```
∫HA.∫a+}.«¹}¹.I.«r∙rο+

```

Try it Here!
leaves output on the stack, which you can view in the console
> 0 votes

# Answer
# Jelly, 14 bytes

```
R+’r@R;€Ḥz0;€Ḥ

```

Try it online!
> 0 votes

# Answer
# Perl 5, 56 bytes

```
$,=$";say($_..$_+$"-1,$"*2)for 1..($"=<>);say(($"*2)x$")

```

Try it online!
> 0 votes

# Answer
# J, 29 bytes

```
(}:@(][\1+i.@+:),]#+:),.>:#+:

```

## ungolfed

```
(}:@(] [\ 1+i.@+:) , ]#+:) ,. >:#+:

```

## explanation

```
(}:@(] [\ 1+i.@+:)                   NB. make the inner part of the matrix
          1+i.@+:                      NB. 1..2*n, where n is the input
    (] [\ 1+i.@+:)                     NB. fork: infixes (sliding window) of length n, over 1..2*n
(}:@                                   NB. remove last element
                   , ]#+:)           NB. add a row of 2*n to the end
                           ,. >:#+:  NB. add a column of 2*n to entire result above

```

Try it online!
> 0 votes

# Answer
# Kotlin, 59 bytes

```
Array(n+1){c->Array(n+1){r->when(n){c,r->n*2;else->1+c+r}}}

```

Try it online.
> 0 votes

# Answer
# Clojure, 153 135 bytes

List of lists? Yay, Lisp

```
(fn[n](loop[r[] i 0 d (* 2 n)](if(= i n)(conj r(conj(repeat n d)d))(recur(conj r(conj(vec(map #(+ i %)(range 1(inc n))))d))(inc i)d))))

```

Ungolfed:

```
(defn a[n]
  (loop [r[] i 0 d (* 2 n)]
    (if(= i n)
      (conj r(conj(repeat n d)d))
      (recur
        (conj r
            (conj (vec (map #(+ i %)(range 1(inc n)))) d))
        (inc i)
        d))))

```

Anonymous function that takes the input as argument and returns a list of lists.

Output of n=5:

```
[[1 2 3 4 5 10] [2 3 4 5 6 10] [3 4 5 6 7 10] [4 5 6 7 8 10] [5 6 7 8 9 10] (10 10 10 10 10 10)]

```
> 0 votes

# Answer
# 05AB1E, 17 bytes

```
FLN+I·¸«ˆ}·¸I>.×ˆ

```

Try it online!

**Explanation**

```
F                   # for N in [0 ... input-1]
 L                  # push range [1 ... input]
  N+                # add N to each
    I·¸«            # append input*2
        ˆ           # add to global list
         }          # end loop
          ·¸        # push [input*2]
            I>.×    # repeat it input+1 times
                ˆ   # add to global list
                    # implicitly output global list

```
> 0 votes

# Answer
# Actually, 23 bytes

```
;;Rnkp@;r♀+@;τ;(♀q)@α@q

```

Try it online!

Explanation:

```
;;Rnkp@;r♀+@;τ;(♀q)@α@q
;;                       two copies of input
  R                      range(1, input+1)
   n                     copy input times
    kp@                  push stack to list, remove first element
       ;r                push range(input)
         ♀+              pairwise addition (add the value in the range to each value in the corresponding list)
           @;            duplicate input again
             τ;          input*2, duplicate that
               (♀q)      append input*2 to each list
                   @α@q  append a row of input*2

```
> 0 votes

# Answer
# Clojure v1.8, 97 bytes

```
#(conj(mapv(fn[i](conj(vec(range i(+ % i)))(* 2 %)))(range 1(inc %)))(vec(repeat(inc %)(* 2 %))))

```

Try it online!

# Explanation

```
(range 1(inc %))                           Numbers from 1 to 'n'
(mapv ... (range 1(inc %)))                For each one of these numbers
(fn[i](conj(vec(range i(+ % i)))(* 2 %)))  Create the numbers from 'i' to (n+i-1), convert to vector and insert '2*n' to the vector
#(conj ... (vec(repeat(inc %)(* 2 %))))    Insert to the previous vector a vector of repeated '2*n's

```
> 0 votes

# Answer
# Fortran (GFortran), 93, 82 bytes

```
SUBROUTINE M(n)
PRINT*,(CHAR(10),(i-1+j,i=1,n),2*n,j=1,n)
PRINT*,(2*n,j=1,n+1)
END

```

Try it online!
> 0 votes

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


title: The Final Number

text:
# Question
Title: The Final Number
# Challenge

Write a program that takes an array of 4 integers (*which represents a sequence of numbers generated by a certain algorithm*) and returns the next integer that would follow.

We will only be using simple addition, subtraction, multiplication and division algorithms with a constant (i.e non-variable) variation.

For division we will use the `floor` integer values: `133/4 = 33` and `33/4 = 8`

**You can assume that there will always be one single valid return value**

# Test cases

`[14,24,34,44]` should return 54 (addition Algorithm)

`[105,45,-15,-75]` should return -135 (subtraction algorithm)

`[5,25,125,625]` should return 3125 (multiplicative algorithm)

`[256,64,16,4]` should return 1 (division algorithm)

# General rules

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

```
D¥¬QPi`+s-ë`r/s\*î

```

**Explanation**

```
D                   # duplicate
 ¥                  # delta's
  ¬Q                # compare first delta to the other deltas
    P               # product (1 if all deltas are equal, otherwise 0)
     i              # if 1 (we're dealing with addition or subtraction)
      `+s-          # add the difference between the elements to the last element
          ë         # else (we're dealing with multiplication or division)
           `r/      # divide the 2nd element by the 1st
              s\*   # multiply with the 4th element
                 î  # round up

```

Try it online!
> 6 votes

# Answer
## Javascript (ES6),  ~~44~~   ~~42~~  44 bytes (fixed)

```
(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0)|0:d+c-b

```

*Saved 2 bytes, following IsmaelMiguel's advice.*
*Fixed version for `[2,1,0,0]` and `[1,0,0,0]` as suggested by edc65*

### 30 bytes version

For the record, my first attempt was ~~32~~ 30 bytes but was lacking floor() support for the division. It also fails for special cases such as `[2,1,0,0]` and `[1,0,0,0]`.

```
(a,b,c,d)=>c-2*b+a?d*c/b:d+c-b

```

### Demo

```
var f =
(a,b,c,d)=>a-b+d-c?d/(a<b?a/b:a/b|0)|0:d+c-b

var test = [
  [ 14, 24, 34, 44 ],     // should return 54 (addition Algorithm)
  [ 105, 45, -15, -75 ],  // should return -135 (subtraction algorithm)
  [ 5, 25, 125, 625 ],    // should return 3125 (multiplicative algorithm)
  [ 256, 64, 16, 4 ],     // should return 1 (division algorithm)
  [ 260, 65, 16, 4 ],     // should return 1 (division algorithm with floor())
  [ 2, 1, 0, 0 ],         // should return 0 (special case of division algorithm)
  [ 1, 0, 0, 0 ]          // should return 0 (special case of division algorithm)
];

test.forEach(l => console.log('[' + l.join`, `+ '] => ' + f(...l)));
```
> 14 votes

# Answer
# Brachylog, ~~37~~ ~~33~~ 27 bytes

```
b:[E]cL,?:Iz{:+a|:*a|:/a}Lt

```

Try it online! or verify all test cases.

*Saved 10 bytes thanks to @LeakyNun*.

### Explanation

```
Input = [A:B:C:D]

b:[E]cL,     L = [B:C:D:E]
?:Iz         Create the list [[B:I]:[C:I]:[D:I]:[E:I]]
{            Either…
    :+a          Sum all couples of that list
|            or…
    :*a          Multiply all couples of that list
|            or…
    :/a          Integer divide all couples of that list
}L          The result is L
t           Output is the last element of L

```

As LeakyNun pointed out, we don't need the subtraction case because `I` can be any integer.
> 11 votes

# Answer
# Haskell, 65 bytes

```
f l@[a,b,c,d]|[a,b..d]==l=d+b-a|z<-b+0^b=div(d*b)$a-mod(max b a)z

```
> 6 votes

# Answer
# Python 2, 40 bytes

```
lambda(a,b,c,d):[d+c-b,d*c/b][c-2*b+a>0]

```

It's literally the JS answer ported into Python (thanks @LeakyNun!). My previous approach was ridiculously long, but here it is:

## Python 2, ~~169~~ 166 bytes

The second and third levels are a raw tab and a raw tab plus a space, respectively, which plays *really* badly with Markdown, so the tabs have been replaced by 2 spaces.

```
x=input()
q='%d%s%d'
for i in range(max(x)):
 for o in'+-*/':
  a=1
  for e,n in zip(x,x[1:]):
   try:1/(eval(q%(e,o,i))==n)
   except:a=0
  if a:print eval(q%(x[-1],o,i))

```

Pretty simple; tries every constant and operator it thinks could be the constant, then if the constant/operator combination works for every element in the list (using a `try`/`except` pair to avoid `ZeroDivisionError`s), it prints the result for the last element in the list.

I'm sure there's a better method here, this is the naive method.
> 5 votes

# Answer
# TSQL, 55 bytes

This script is trying adding and subtraction in the same check, then it tries to multiply, if that fails, it must be division.

```
DECLARE
@1 INT=6561,
@2 INT=729,
@3 INT=81,
@  INT=9

PRINT IIF(@2-@1=@-@3,@*2-@3,IIF(@1*@2=@3,@*@1,sqrt(@)))

```

**Fiddle**
> 3 votes

# Answer
# C#, 63 bytes

```
int f(int[]x)=>2*x[1]-x[0]==x[2]?x[3]+x[1]-x[0]:x[3]*x[1]/x[0];

```

Checks whether the difference between the first and second element is the same as the difference between the second and third element. If so, it does addition/subtraction, otherwise it does multiplication/division.
> 3 votes

# Answer
## R, ~~68~~ 74

Array: 68 bytes

```
function(x)if(x[2]-x[1]==x[3]-x[2])x[4]+x[2]-x[1]else x[4]%/%(x[1]%/%x[2])

> (function(x)if(x[2]-x[1]==x[3]-x[2])x[4]+x[2]-x[1]else x[4]*x[2]/x[1])(c(14,24,34,44))
[1] 54

```

4 inputs: 45 bytes

```
function(a,b,c,d)if(b-a==c-b)d+b-a else d*b/a

```

Bonus solution with `log`, `exp`, `var`, 71 bytes

```
if(var(v<-diff(x<-scan(,1)))==0)x[4]+v[1]else x[4]*exp(diff(log(x)))[1]

```

update: integer division
> 2 votes

# Answer
# JavaScript, 73 bytes

```
(a,b,c,d)=>(x=b-a,c-b==x&&d-c==x)?d+x:(x=b/a,b*x|0==c&&c*x|0==d)?d*x|0:-1

```

**Tests**:

```
console.log(s.apply(null,[14,24,34,44]), 54);
console.log(s.apply(null,[105,45,-15,-75]), -135);
console.log(s.apply(null,[5,25,125,625]), 3125);
console.log(s.apply(null,[256,64,16,4]), 1);

console.log(s.apply(null,[2,1,0,0]),0);
console.log(s.apply(null,[1,0,0,0]),0);
console.log(s.apply(null,[-325,-82,-21,-6]),-1);

console.log(s.apply(null,[-1,-1,-1,-1]),-1);
console.log(s.apply(null,[0,0,0,0]),0);

```

Works for them all.
> 2 votes

# Answer
# GameMaker Language, 70 bytes

```
a=argument0;If a[3]+a[1]=a[2]*2return a[4]*2-a[3]return a[4]*a[4]/a[3]

```
> 2 votes

# Answer
# Python 2, ~~75 66 65~~ 61 bytes

```
lambda(a,b,c,d):d*2-c if d-c==b-a else d*b/a or b and d/(a/b)

```

Much longer than my previous 38 byte entry which did not cater for the division series correctly (just as most others didn't).

Test cases and more edge cases are on **ideone**

*Note: integer division for a negative here is defined as having a remainder with the same sign as the divisor, so `-81/4` would be `-21` with a remainder of `3` and `-81/-4` would be `20` with a remainder of `-1`.*
> 1 votes

# Answer
# Java, ~~125~~ 123 bytes

Golfed:

```
int m(int[]a){int r=(a[1]>a[0])?a[1]/a[0]:a[0]/a[1];return(a[0]-a[1]==a[1]-a[2])?a[3]-a[0]+a[1]:(a[0]<a[1])?a[3]*r:a[3]/r;}

```

Ungolfed:

```
int m(int[] a)
{
    int r = (a[1] > a[0]) ? a[1] / a[0] : a[0] / a[1];
    return (a[0] - a[1] == a[1] - a[2]) ? a[3] - a[0] + a[1] : (a[0] < a[1]) ? a[3] * r : a[3] / r;
}

```

This code surely has some issues since it doesn't handle division by zero and such things. It also won't work of course if there are more (or less) than 4 integers in the input array `a`. Which makes it beyond stupid, but I had fun :)

Try it out: https://ideone.com/nELH5I
> 1 votes

# Answer
# TI-Basic, 37 bytes

*Works on any TI-83/84 calculator*

```
Input L1                     gets input into an array
L1(4)²/L1(3                  calculate the fifth number in a geometric series
If not(sum(ΔList(ΔList(L1    if ΔList(ΔList(L1)) yields an array of all zeroes
L1(4)2-L1(3                  calculate the fifth number in an arithmetic series
                             Ans is implicitly returned

```
> 1 votes

# Answer
# Jelly, 14 bytes

```
ṪḤ_ṪµṪ²:ṪµIE$?

```

Try it online!

```
ṪḤ_ṪµṪ²:ṪµIE$?  Main Link =
             ?  If
          IE$   [condition]
          I     The differences between consecutive elements
           E    Is equal
ṪḤ_Ṫ            [then]
Ṫ               The last element
 Ḥ              Doubled
  _             Minus
   Ṫ            The last element (second-last of original list)
    µṪ²:Ṫµ      [else]
     Ṫ          The last element
      ²         Squared
       :        Divided by
        Ṫ       The last element (second-last of original list)

```
> 1 votes

# Answer
# Pyth, 18 Bytes

```
?-+vzJEyQ/^E2J-yEJ

```

Accepts input as a newline-separated list of values.

Try it online!

Explanation:

```
?                         If
 -                          the following are not equal:
  +vzJE                      the sum of first and third values (and call the third value J)
       yQ                    and the second value * 2;
                            (i.e. if it is not an additive or subtractive formula)
          ^E2             Then: square the fourth value
         /   J              and divide by the third
?                         Else:
               yE           double the fourth value
              -  J          and subtract the third

```
> 0 votes

---
Tags: code-golf, number
---


title: Microgravity Ball

text:
# Question
Title: Microgravity Ball
You are on an advanced intergalactic space station. A friend of yours who is minoring in the Study of Gravity just created a game that involves using microgravity as a way to move a ball around.

She hands you a small controller with four directional arrows on it and a maze like structure with a ball sitting to the left. She begins to explain how the game works.

* You have 2 directional buttons, left `<` and right `>`.
* You also have 2 gravity buttons, up `^` and down `v` (at least from your frame of reference)
* You will use these arrow buttons to move the ball around on your screen.

"Now there are some rules that need to be followed." she says

1. All platforms must be traversed before getting to the cup `\ /`
2. Arrows `< > ^ v` will be used to specify movement of the ball
3. Gravity is `^ v` (up & down). This moves the ball all the way to the next platform in that direction. (Distance is not calculated for up and down)
4. Losing the ball is bad! Don't fall over the edge, and don't switch gravity too soon such that your ball never reaches a platform
5. Movement is counted in steps of `< >`
6. The ball can enter the cup from any direction as long as Rule 1 is followed
7. You must specify direction of gravity so your ball doesn't float away
8. Movement may be random as long as Rule 1 and Rule 4 is followed
9. For cases that cannot be solved output False or Invalid

## Simple Example of a ball, platform, and cup:

```
v
o
---\ /

```

---

```
v>

 o
---\ /

```

---

```
v>>

  o
---\ /

```

---

```
v>>>

   o
---\ /

```

---

```
v>>>>

---\o/

```

## Example of traversing over the same platform again.

```
v

 o
 ----

\ /-------

```

---

```
v>

  o
 ----

\ /-------

```

---

```
v>>

   o
 ----

\ /-------

```

---

```
v>>>

    o
 ----

\ /-------

```

---

```
v>>>>

 ----
     o
\ /-------

```

---

```
v>>>>>

 ----
      o
\ /-------

```

---

```
v>>>>>>

 ----
       o
\ /-------

```

---

```
v>>>>>>>

 ----
        o
\ /-------

```

---

```
v>>>>>>>>

 ----
         o
\ /-------

```

---

```
v>>>>>>>><<<<<<<< # move all the way to the left to get to the cup

 ----

\o/-------

```

---

## Example of switching gravity

```
v
   --/ \

o
----

```

---

```
v>
   --/ \

 o
----

```

---

```
v>>
   --/ \

  o
----

```

---

```
v>>>
   --/ \

   o
----

```

---

```
v>>>^
   --/ \
   o

----

```

---

```
v>>>^>
   --/ \
    o

----

```

---

```
v>>>^>>
   --/ \
     o

----

```

---

```
v>>>^>>>
   --/o\

----

```

## Task

Your task is to create a program that will take an ASCII representation of a course as input. And output a string of arrows `<>^v` representing the direction and gravitational pull to move a ball `o` across all `platforms` into a cup.

Standard code golf rules apply

## Test Cases

Input (A situation where gravity is being switched)

```
         ----   --/ \
---    --
o

  ------    -----

```

Output

```
^>>v>>>>>^>>>>>v>>>>^>>>

```

---

Input (A situation where direction is being switched)

```
       ---
o
----
    ---

     -----

    --\ /

```

Output

```
v>>>>>>^>>>v<<<<<v>>>

```

---

Input (A situation where you need to traverse over the same platform twice)

```
 o
 ------

  ------

 ------

\ /------

```

Output

```
v>>>>>><<<<<<>>>>>>><<<<<<

```

---

## Bad Cases, Program should output Falsy for these

No way for the ball to get to the next platform

```
o
--- ---

```

Ball would float off into space

```
---
o
   ---

```

A situation where the ball gets to the cup, but all platforms don't get traversed.

```
o
----
    ----
        \ /----

```

# Answer
# Pyth, 431 bytes

This is my first Pyth program (actually this is my first program in any code-golf language), which means it can be probably still improved.

```
Jmmck\:cd\%c.Z"xÚU±Ã@DÅ W,J áDPáÒV`ýüw{g$ÍÀÞÇr§o.÷å8èÝÇr{øºy{~1åõ:noßÃú/.yçíäÂ'ëL¢êF¸èÆ\ka´QÒnÒ@tãÒÁµÆ¾õö»bÍH¥¦$¨%5Eyîÿ}ó§ûrh³oÄåËÄqõ XÔHû"\_KYDrGHFN@JGIn=bm:d.*NHHRb)RHDiNTR.turNG.tT;M:jH)hh@JG0DXGHN=Ti+3qG\^HI!},GTK aK,GT aY+eKNI&!g5T}\EjT)N.q;D(GHNT)INIqHhT=ZrGhtTInZhtTXHZ+eTN))).?I&nHhTgGhtTXHhtT+eTH; aK,di2i1r0.z aY+eKk#=N.(Y0(6\vkN)(7\^kN)(8\v\<N)(9\v\>N)(10\^\<N)(11\^\>N

```

Try it here (the last testcase needs too long, it must be tested with a local Pyth installation).

Hex dump of the code (use `xxd -r <filename>` to decode):

```
00000000: 4a6d 6d63 6b5c 3a63 645c 2563 2e5a 2278  Jmmck\:cd\%c.Z"x
00000010: da55 8eb1 8ac3 400c 447f c58d 2057 2c99  .U....@.D... W,.
00000020: 4aa0 e144 50e1 d2ad 5660 87fd 84fc 7f77  J..DP...V`.....w
00000030: 7b67 1f24 cdc0 8319 de1c c772 a76f 2ef7  {g.$.......r.o..
00000040: e538 e8dd c772 7bf8 9eba 797b 7e31 e5f5  .8...r{...y{~1..
00000050: 8e3a 6e8f 6fdf c3fa 2f2e 0c79 e717 ede4  .:n.o.../..y....
00000060: c21f 27eb 8395 189a 4c15 140b a28d ea82  ..'.....L.......
00000070: 46b8 e8c6 5c05 1b6b 1d61 b490 0251 d28c  F...\..k.a...Q..
00000080: 6ed2 4087 74e3 1ad2 c1b5 c6be f5f6 1cbb  n.@.t...........
00000090: 6286 cd48 a5a6 24a8 2535 4579 eeff 7df3  b..H..$.%5Ey..}.
000000a0: 8a8a 1613 a7fb 7204 68b3 6fc4 e51b 160c  ......r.h.o.....
000000b0: 1304 cbc4 8a71 f57f 2058 d448 fb22 5c5f  .....q.. X.H."\_
000000c0: 4b59 4472 4748 464e 404a 4749 6e3d 626d  KYDrGHFN@JGIn=bm
000000d0: 3a64 2e2a 4e48 4852 6229 5248 4469 4e54  :d.*NHHRb)RHDiNT
000000e0: 522e 7475 724e 472e 7454 3b4d 3a6a 4829  R.turNG.tT;M:jH)
000000f0: 6868 404a 4730 4458 4748 4e3d 5469 2b33  hh@JG0DXGHN=Ti+3
00000100: 7147 5c5e 4849 217d 2c47 544b 2061 4b2c  qG\^HI!},GTK aK,
00000110: 4754 2061 592b 654b 4e49 2621 6735 547d  GT aY+eKNI&!g5T}
00000120: 5c45 6a54 294e 2e71 3b44 2847 484e 5429  \EjT)N.q;D(GHNT)
00000130: 494e 4971 4868 543d 5a72 4768 7454 496e  INIqHhT=ZrGhtTIn
00000140: 5a68 7454 5848 5a2b 6554 4e29 2929 2e3f  ZhtTXHZ+eTN))).?
00000150: 4926 6e48 6854 6747 6874 5458 4868 7454  I&nHhTgGhtTXHhtT
00000160: 2b65 5448 3b20 614b 2c64 6932 6931 7230  +eTH; aK,di2i1r0
00000170: 2e7a 2061 592b 654b 6b23 3d4e 2e28 5930  .z aY+eKk#=N.(Y0
00000180: 2836 5c76 6b4e 2928 375c 5e6b 4e29 2838  (6\vkN)(7\^kN)(8
00000190: 5c76 5c3c 4e29 2839 5c76 5c3e 4e29 2831  \v\<N)(9\v\>N)(1
000001a0: 305c 5e5c 3c4e 2928 3131 5c5e 5c3e 4e    0\^\<N)(11\^\>N

```

## Explanation

The main idea for this program was to use regular expressions to modify the input. To save space all these regular expressions are contained in a compressed string. The first step in the program is to decompress the string and to split it int single regular expression and the corresponding replacement strings.

```
            .Z"..."     Decompress the string
           c       \_   Split the result into pieces (separator is "_")
  m    cd\%             Split all pieces (separator is "%")
 m ck\:                 Split all sub-pieces (separator is ":")
J                       Assign the result to variable J

```

The contents of variable `J` are then:

```
[[['\\\\ /', '=M='], ['/ \\\\', '=W=']],
 [[' (?=[V6M=-])', 'V'], ['o(?=[V6M=-])', '6']],
 [['(?<=[A9W=-]) ', 'A'], ['(?<=[A9W=-])o', '9'], ['(?<=[X0W=-])V', 'X'], ['(?<=[X0W=-])6', '0']],
 [['6V', 'V6'], ['0X', 'X0'], ['6-', '6='], ['0-', '0='], ['6M', 'VE'], ['0M', 'XE']],
 [['A9', '9A'], ['X0', '0X'], ['-9', '=9'], ['-0', '=0'], ['W9', 'EA'], ['W0', 'EX']],
 [['[MW-]']],
 [['[60]']],
 [['[90]']],
 [['V6', '6V'], ['V0', '6X'], ['X6', '0V'], ['X0', '0X']],
 [['6V', 'V6'], ['0V', 'X6'], ['6X', 'V0'], ['0X', 'X0']],
 [['A9', '9A'], ['A0', '9X'], ['X9', '0A'], ['X0', '0X']],
 [['9A', 'A9'], ['0A', 'X9'], ['9X', 'A0'], ['0X', 'X0']]]

```

---

```
KY   Set the variable K to an empty list

```

---

The function `r` applies regex substitutions from the list stored in `J` at the index `G` to all strings in the list `H`. It returns as soon as any of the strings was changed.

```
DrGH                         Define the function r(G,H)
    FN@JG              )     Loop for all entries in J[G]
             m:d.*NH         Regex substitution, replace N[0] with N[1] in all strings in list H
           =b                Store the result in variable b
         In         HRb      If b != H return b
                        RH   Return H

```

---

The function `i` is similar to function `r` with 2 differences. It applies the substitutions on a transposed list (vertical instead on horizontal). It also performs the substitutions repeatedly as long as anything is changed.

```
DiNT          ;   Define the function i(N,T)
           .tT    Transpose the list T
       urNG       Apply r(N,...) repeatedly as long as something changes
    R.t           Transpose the result back and return it

```

---

The function `g` checks if the regex from the list stored in `J` at the index `G` can by found in any string in the list `H`.

```
M             Define the function g(G,H)
     hh@JG    Get the single regex stored in J[G]
  jH)         Join all strings in H
 :        0   Check if the regex is found anywhere in the joined string

```

---

The rest of the code contains the actual program logic. It performs a breadth-first search for the possible movements until a solution is found. The position in the search tree is uniquely defined by the direction of the gravity and a modified copy of the program input. To avoid the processing of the same position again and again, processed positions are stored in the global list `K`. Positions which still have to be processed are stored together with the corresponding part of the solution in the list `Y`.

The modification of the input and initialization of `K` and `Y` is performed by the following code:

```
           .z          Get all input as a line list
     i2i1r0            Apply the regular expressions stored in J[0] horizontally, and the the ones from J[1] and J[2] vertically
   ,d                  Create a list with " " (represents "no gravity set") and the modifed input
 aK                    Append the result to the list K
                 eK    Retrieve the appended list again
                +  k   Append "" to the list (represents the empty starting solution)
              aY       Append the result to the list Y

```

The input modification does something like the following. The input:

```
         ----   --/ \
---    --
o

  ------    -----

```

is transformed to:

```
VVVVVVVVV----VVV--=W=
---VVVV--AAAXVVVXAAAA
9AXVVVVXAAAAXVVVXAAAA
AAXVVVVXAAAAXVVVXAAAA
AA------AAAA-----AAAA

```

The values have the following meaning:

* `-` Platform which must be still visited
* `=` Platform which doesn't need to be visited anymore
* `M` Cup which can be entered with gravity set to "down"
* `W` Cup which can be entered with gravity set to "up"
* `V` Safe to move to this place with gravity set to "down"
* `A` Safe to move to this place with gravity set to "up"
* `X` Safe to move to this place regardless of the gravity setting
* `6` Ball on a place which would be marked as `V`
* `9` Ball on a place which would be marked as `A`
* `0` Ball on a place which would be marked as `X`

The logic is using regular expressions to perform the movements. In the example above, if the gravity would be set to "up", we can replace "9A" with "A9" with an regex to move the ball to the right. This means by trying to apply the regex we can find all possible movements.

---

The function `X` performs vertical ball movements based on the current gravity setting, stores the result in global lists `K` and `Y`, and checks if a solution was found.

```
DXGHN                                             ;   Define the function X(G,H,N)
        +3qG\^                                        Select the correct set of regular expressions based on the current gravity setting G (3 for "v" and 4 for "^")
     =Ti      H                                       Apply i(...,H) and store the result in T
               I!},GTK                                If [G,T] not in K
                       aK,GT                          Store [G,T] in K
                             aY+eKN                   Store [G,T,N] in Y
                                   I&!g5T}\EjT)       If J[5] not found in T and T contains "E" (all platforms visited and ball in cup)
                                               N.q    Print N and exit

```

---

The function `(` implements checks for the 4 directional/gravity buttons. The gravity buttons can be pressed only if the current gravity would change and if the ball is in a safe place to change the gravity. The directional buttons can be pressed only if it is safe to move to the corresponding place.

```
D(GHNT)                                                    ;   Define the function ( (G,H,N,T)
       IN                           )                          If N is not empty (contains either "<" or ">" representing directional buttons)
         IqHhT                     )                           If H (gravity setting for which this test is performed) is equal T[0] (the current gravity)
              =ZrGhtT                                          Apply r(G,T[1]) and store the result in Z (G is the appropriate regex index for the combination of gravity and directional button, T[1] is the current modified input)
                     InZhtT       )                            If Z != T[1] (the regex operation changed something, meaning we found a valid move)
                           XHZ+eTN                             Call X(H,Z,[T[2],N])
                                     .?                        Else (gravity button pressed)
                                       I                       If ...
                                         nHhT                  H (new gravity setting) is not equal T[0] (current gravity setting)
                                        &                      ... and ...
                                             gGhtT             J[G] found in T[1] (ball is in an appropriate place to switch gravity)
                                                  XHhtT+eTH    Call X(H,T[1],[T[2],H])

```

---

Finally the main loop. The first element of `Y` is removed repeatedly, and checks for all possible moves are performed.

```
#                                                        Loop until error (Y empty)
 =N.(Y0                                                  Pop first element of Y and store it in the variable N
       (6\vkN)                                           Call ( (6,"v","",N)
              (7\^kN)                                    Call ( (7,"^","",N)
                     (8\v\<N)                            Call ( (8,"v","<",N)
                             (9\v\>N)                    Call ( (9,"v",">",N)
                                     (10\^\<N)           Call ( (10,"^","<",N)
                                              (11\^\>N   Call ( (11,"^",">",N)

```
> 12 votes

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


title: Piles and Piles of Pebbles

text:
# Question
Title: Piles and Piles of Pebbles
My job is stacking pebbles into triangular piles. I've only been doing this for a century and it is already pretty boring. The worst part is that I label every pile. I know how to decompose pebbles into piles of maximal size, but I want to minimize the number of piles. Can you help?

# Task

Given an integer, decompose it into the minimum number of triangular numbers, and output that minimum number.

### Triangular Numbers

A triangular number is a number which can be expressed as the sum of the first `n` natural numbers, for some value `n`. Thus the first few triangular numbers are

```
1 3 6 10 15 21 28 36 45 55 66 78 91 105

```

# Example

As an example, let's say the input is `9`. It is not a triangular number, so it cannot be expressed as the sum of `1` triangular number. Thus the minimum number of triangular numbers is `2`, which can be obtained with `[6,3]`, yielding the correct output of `2`.

As another example, let's say the input is `12`. The most obvious solution is to use a greedy algorithm and remove the largest triangular number at a time, yielding `[10,1,1]` and an output of `3`. However, there is a better solution: `[6,6]`, yielding the correct output of `2`.

# Test Cases

```
in out
1 1
2 2
3 1
4 2
5 3
6 1
7 2
8 3
9 2
10 1
11 2
12 2
13 2
14 3
15 1
16 2
17 3
18 2
19 3
20 2
100 2
101 2
5050 1

```

# Rules

* The input integer is between 1 and the maximum integer of your language.
* I can emulate any language with my pebbles, and I want your code as small as possible because I have nothing but pebbles to keep track of it. Thus this is , so the shortest code **in each language** wins.

# Answer
# Retina, ~~57~~ 49 bytes

```
.+
$*
(^1|1\1)+$
1
(^1|1\1)+(1(?(2)\2))+$
2
11+
3

```

Try it online! Based on my answer to Three triangular numbers. Change the third line to `^(^1|1\1)*$` to support zero input. Edit: Saved 8 (but probably should be more) bytes thanks to @MartinEnder.
> 3 votes

# Answer
# Mathematica, 53 bytes

```
Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&

```

This code is very slow. If you want to test this function, use the following version instead:

```
Min[Plus@@@Table[$($+1)/2,{$,√#+1}]~FrobeniusSolve~#]&

```

Try it on Wolfram Sandbox

### Explanation

```
Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&  (* input: n *)

           Table[$($+1)/2,{$,#+1}]                     (* Generate the first n triangle numbers *)
                                  ~FrobeniusSolve~#    (* Generate a Frobenius equation from the *)
                                                       (* triangle numbers and find all solutions. *)
    Plus@@@                                            (* Sum each solution set *)
Min                                                    (* Fetch the smallest value *)

```
> 1 votes

# Answer
# Jelly (fork), 9 bytes

```
æFR+\$S€Ṃ

```

This relies on a fork where I implemented an inefficient Frobenius solve atom. Can't believe it's already been a year since I last touched it.

## Explanation

```
æFR+\$S€Ṃ  Input: n
æF         Frobenius solve with
     $     Monadic chain
  R          Range, [1, n]
   +\        Cumulative sum, forms the first n triangle numbers
      S€   Sum each
        Ṃ  Minimum

```
> 1 votes

# Answer
# , ~~69~~ 58 bytes

```
function(n)3-n%in%(l=cumsum(1:n))-n%in%outer(c(0,l),l,"+")

```

Try it online!

Explanation:

```
function(n){
 T <- cumsum(1:n)             # first n triangular numbers  [1,3,6]
 S <- outer(c(0,T),T,"+")     # sums of the first n triangular numbers,
                              # AND the first n triangular numbers [1,3,6,2,4,7,4,6,9,7,9,12]
 3 - (n %in% S) - (n %in% T)  # if n is in T, it's also in S, so it's 3-2: return 1
                              # if n is in S but not T, it's 3-1: return 2
                              # if n isn't in S, it's not in T, so 3-0: return 3
}

```
> 1 votes

# Answer
# Kotlin, ~~176~~ 154 bytes

## Submission

```
{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

```

## Beautified

```
{
    // Make a mutable copy of the input
    var l=it
    // Keep track of the number of items removed
    var n=0
    // While we still need to remove pebbles
    while (l > 0) {
        // Increase removed count
        n++
        // BEGIN: Create a list of triangle numbers
        val r= mutableListOf(1)
        var t = 3
        var i = 3
        while (t<= l) {
            // Add the number to the list and calculate the next one
            r.add(t)
            t+=i
            i++
        }
        // END: Create a list of triangle numbers
        // Get the fitting pebble, or the biggest one if none fit or make a perfect gap
        l -= r.lastOrNull {l==it|| r.contains(l-it)} ?: r[0]
    }
    //Return the number of pebbles
    n
}

```

## Test

```
var r:(Int)->Int =
{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

data class TestData(val input:Int, val output:Int)

fun main(args: Array<String>) {
    val tests = listOf(
            TestData(1,1),
            TestData(2,2),
            TestData(3,1),
            TestData(4,2),
            TestData(5,3),
            TestData(6,1),
            TestData(7,2),
            TestData(8,3),
            TestData(9,2),
            TestData(10,1),
            TestData(11,2),
            TestData(12,2),
            TestData(13,2),
            TestData(14,3),
            TestData(15,1),
            TestData(16,2),
            TestData(17,3),
            TestData(18,2),
            TestData(19,3),
            TestData(20,2),
            TestData(100,2),
            TestData(101,2),
            TestData(5050,1)
    )
    tests.map { it to r(it.input) }.filter { it.first.output != it.second }.forEach { println("Failed for ${it.first}, output ${it.second} instead") }
}

```

TryItOnline
> 0 votes

# Answer
# MATL, 15 bytes

```
`G:Ys@Z^!XsG-}@

```

**Try it online!**

### Explanation

```
`         % Do...while
  G:      %   Push range [1 2 3 ... n], where n is the input
  Ys      %   Cumulative sum: gives [1 3 6 ... n*(n+1)/2]
  @Z^     %   Cartesian power with exponent k, where k is iteration index
          %   This gives a k-column matrix where each row is a Cartesian tuple
  !Xs     %   Sum of each row. Gives a column vector
  G-      %   Subtract input from each entry of that vector. This is the loop
          %   condition. It is truthy if it only contains non-zeros
}         % Finally (execute before exiting the loop)
  @       %   Push iteration index, k. This is the output
          % End (implicit). Proceeds with next iteration if the top of the
          % stack is truthy

```
> 0 votes

# Answer
# Jelly, 15 bytes

```
0rSƤṗ⁸S⁼¥Ðf⁸ḢTL

```

Try it online!
> 0 votes

# Answer
# JavaScript (ES6), ~~75~~ ~~63~~ 61 bytes

```
f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

```

### How?

We use the following properties:

* According to Fermat polygonal number theorem, any positive integer can be expressed as the sum of at most 3 triangular numbers.
* A number ***t*** is triangular if and only if ***8t+1*** is a perfect square (this can easily be proven by solving ***t = n(n+1) / 2***).

Given a positive integer ***n***, it's enough to test whether we can find:

* ***x \> 0*** such that ***8n+1 = x²*** (***n*** itself is triangular)
* or ***x \> 0*** and ***y \> 0*** such that ***8n+2 = x²+y²*** (***n*** is the sum of 2 triangular numbers)

If both tests fail, ***n*** must be the sum of 3 triangular numbers.

```
f = (n, x = y = 0) =>                 // given n and starting with x = y = 0
  y < n + 2 ?                         // if y is less than the maximum value:
    x * x + y * y - 8 * n - 2 + !y ?  //   if x² + y² does not equal 8n + 2 - !y:
      f(                              //     do a recursive call with:
        n,                            //       - the original input n
        x < n + 2 ? x + 1 : ++y       //       - either x incremented or
      )                               //         y incremented and x set to y
    :                                 //   else:
      2 - !y                          //     return either 1 or 2
  :                                   // else:
    3                                 //   return 3

```

### Test cases

```
f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

;[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 100, 101, 5050 ]
.forEach(n => console.log(n + ' --> ' + f(n)))
```
> 0 votes

---
Tags: code-golf, optimization
---


title: Code Golf - Covfefe on tap

text:
# Question
Title: Code Golf - Covfefe on tap
As we all know, negative press covfefe has been conspiring to bring down the American president for some months now.

There's also, definitely, an algorithm in play in that word. Covfe is a refreshing caffeinated beverage, and following the president's remarks it's clear the word can now be appended with successive f's and e's, so long as they are not adjacent to their own letters.

So I wrote some code to generate the inevitable covfefe triangle. The output looks like this:

```
covfefe
covfefef
covfefefe
covfefefef
covfefefefe
covfefefefef
covfefefefefe
covfefefefefef
covfefefefefefe
covfefefefefefef
covfefefefefefefe
covfefefefefefefef
covfefefefefefefefe
covfefefefefefefefef
covfefefefefefefefefe
covfefefefefefefefefef
covfefefefefefefefefefe
covfefefefefefefefefefef
covfefefefefefefefefefefe
covfefefefefefefefefefefef
covfefefefefefefefefefefefe

```

So here are the rules:

* Output 21 lines, the first of which should be 'covfefe'.
* Each line must be one character longer than the previous line.
* No f can be horizontally adjacent to another f.
* No e can be horizontally adjacent to another e.

Oh, and have fun!

(I'm also interested to see any other nifty covfefe-related snippets)

# Answer
# Charcoal, 13 bytes

```
Ｅ²¹⁺cov…fe⁺⁴ι

```

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

```
            Implicitly print joined with newlines
Ｅ²¹         the implicit range 0..21 mapped to
   ⁺cov     the concatenation of "cov" with
    …fe     the characters "fe" repeated until their length is exactly
     ⁺⁴ι    4 more than the value

```
> 3 votes

# Answer
# 05AB1E, ~~17~~ 16 bytes

```
„fe12×η¦¦¦…covì»

```

Try it online!

**Explanation**

```
„fe               # push the string "fe"
   12×            # repeat it 12 times
      η           # get the prefixes of this string
       ¦¦¦        # drop the first 3
          …covì   # prepend the string "cov" to each
               »  # join on newline

```
> 3 votes

# Answer
# Japt, ~~17~~ 16 bytes

```
4o25_îeif)i`¬v

```

Test it online! 14 bytes of code, +2 for `-R` flag. If we can output as an array, simply remove the `-R` and subtract 2 bytes.

### Explanation

```
4o25              Generate the range [4, 5, ..., 24].
    _             Map each item in this range to
      eif           "fe" (really weird hack, but it works and saves a byte)
     î   )          repeated to length <item>
          i`¬v      with "cov" inserted at the beginning.
                  Implicit: output result of last expression, joined with newlines (-R)

```

Alternatively, you could do `7o28_îfie)h"cov`, which does the same thing, except overwriting `cov` onto the beginning of the string instead of inserting it at the beginning.
> 3 votes

# Answer
# Python 2, 37 bytes

```
s='covfef'
exec"s+=s[-2];print s;"*21

```

Try it online!

Matches the text shown.

---

# Python 2, 36 bytes

```
s='covfefe'
exec"print s;s+='?';"*21

```

Try it online!

Prints:

```
covfefe
covfefe?
covfefe??
covfefe???
covfefe????
covfefe?????
covfefe??????
covfefe???????
covfefe????????
covfefe?????????
covfefe??????????
covfefe???????????
covfefe????????????
covfefe?????????????
covfefe??????????????
covfefe???????????????
covfefe????????????????
covfefe?????????????????
covfefe??????????????????
covfefe???????????????????
covfefe????????????????????

```
> 2 votes

# Answer
## Pyth, 29 bytes

```
Vr4 25+"cov"+*/N2"fe"?%N2"f"k

```

Explanation:

```
Vr 4 25      Loops variable N from 4 to 24 (excludes 25)
    */N2"fe"     Repeats string "fe" N / 2 number of times
        ?%N2"f"k     Concatenates "f" if N % 2 is 1 (odd), or an empty
                     string if it is even (N % 2 is 0)
            +            Concatenates strings

```

Try it online!
> 2 votes

# Answer
# SOGL V0.12, ~~16~~ 15 bytes

```
4'⁷Ν{ņcoļvƧfemo

```

Try it Here!

Explanation:

```
4'⁷Ν             push inclusive range from 4 to 24
    {            for each do
     ņcoļv         output in a new line "cov" (split into 2 commands of "output 2 chars in a new line" and "output next char" for a byte save)
          Ƨfemo    output "fe" molded into the length of the current item

```
> 1 votes

# Answer
# Python 2, ~~53~~ 52 bytes

```
f=lambda n=21:n*' 'and'\ncovf'+('ef'*12)[:-n]+f(n-1)

```

Try it online!
> 1 votes

# Answer
Totally valid answer which matches the specs/rules.

# PowerShell, 25 Bytes. Try it online!

```
"covfefe";8..28|%{'?'*$_}

```

OR (same byte count)

```
0..21|%{'covfefe'+'?'*$_}

```

As intended answer which matches the example output.

# PowerShell, 44 Bytes. Try it online!

```
$c="covfef";0..20|%{($c=$c+('e','f')[$_%2])}

```

Ugly assignment at the beginning, i'm sure there's some that can be saved here.
> 1 votes

# Answer
# C# (Mono), 132 bytes

```
using System.Linq;_=>{for(int i=0;i<21;)System.Console.WriteLine("cov"+string.Concat(new int[4+i++].Select((n,j)=>j%2<1?"f":"e")));}

```

Try it online!
> 1 votes

# Answer
# Japt, ~~20~~ 18 bytes

```
`¬vfef`
21ÆU±gJÉÃ·

```

Test it

16 bytes, if we can return an array.

```
`¬vfef`
21ÆU±gJÉ

```
> 1 votes

# Answer
# Jelly, 17 bytes

```
⁾feẋ12“cov”;;\ṫ7Y

```

Try it online!
> 1 votes

# Answer
# Husk, 15 bytes

```
↑21↓7ḣ+¨¢√¨¢"fe

```

Try it online!

NB: `¨¢√¨` is the compressed strind `"cov"`
> 1 votes

# Answer
# Pyth, 33 bytes

`V21+++"cov"*"fe"2*"fe"s/N2*\f%N2`

Try it here: http://pyth.herokuapp.com
> 1 votes

# Answer
# Retina, 27 bytes

```

covf12$*
1
ef
.
$`¶
G`.{7}

```

Try it online! Explanation:

```
covf12$*

```

Add `covf` plus 12 `1`s.

```
1
ef

```

Change each `1` to `ef`. This results in the last line of the desired output, but with an extra `f`.

```
.
$`¶

```

Replace the string with a list of all of its proper prefixes.

```
G`.{7}

```

Delete the prefixes that are too short.
> 1 votes

# Answer
# C (gcc), ~~77~~ ~~75~~ 74 bytes

```
f(i,j){for(i=4;i++<25;)for(printf("\ncov"),j=i;--j;)putchar("ef"[i-j&1]);}

```

Try it online!
> 1 votes

# Answer
# Python 3, 61 bytes

```
def f(n=20):
	print(' '*n+('covf'+'ef'*12)[:~n])
	if n:f(n-1)

```

not the shortest, but prints triangle without e/f vertical adjacency

Try it online!
> 1 votes

# Answer
# Perl 5, 45 bytes

```
$_="covfef
";eval's/((.).)$/$1$2/;print;'x 20

```

Try it online!
> 1 votes

# Answer
# Perl 5, 39 bytes

```
$b=covfef;say$b.=substr$b,-2,1for 1..21

```

Try it online!
> 1 votes

# Answer
**Ruby - 53 chars**

```
s='covfef';21.times{|i|puts s +=(i.odd? ? 'f' : 'e')}

```

*Note:* This is the OP's answer, there must be better one's out there.
> 0 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: Measuring a pile of logs

text:
# Question
Title: Measuring a pile of logs
## Introduction

This is a log of length 5:

```
#####

```

I want to pile a bunch of these logs on top of each other. How I do this is that I slide a new log onto the topmost one from the right, and stop sliding when their left or right ends align (don't ask why). If the new log is longer, it slides all the way to the left end of the topmost log:

```
########  <-
#####

```

If it is shorter, it only slides until their right ends align:

```
  ######  <-
########
#####

```

As I slide more logs into the pile, their positions are determined by the current topmost log:

```
           ##
       ######
       ###
      ####
      ##
  ######
########
#####

```

This looks physically impossible, but let's pretend it works.

## The task

Your input shall be a non-empty list of positive integers, representing the lengths of my logs. The leftmost number is the first log I put to the pile, so it ends up at the bottom. In the above example, the input would be `[5,8,6,2,4,3,6,2]`. Your output shall be, for each column of the resulting pile, the number of logs that cross that column. In the above example, the correct output would be `[2,2,3,3,3,2,4,6,3,3,1,2,2]`.

## Rules and scoring

Input and output can be in any reasonable format. The output can only contain positive integers, i.e. it must not have leading or trailing `0`s. Normal code-golf rules apply: you can write a full program or a function, the lowest byte count wins, and standard loopholes are forbidden.

## Test cases

```
[1] -> [1]
[4] -> [1,1,1,1]
[3,2] -> [1,2,2]
[2,3] -> [2,2,1]
[2,2,2] -> [3,3]
[2,3,2] -> [2,3,2]
[3,2,3] -> [1,3,3,1]
[1,3,2,2,1,3,1] -> [2,3,5,1,2]
[4,3,4,2,4,3,4,2] -> [1,3,3,5,5,3,4,2]
[5,8,6,2,4,3,6,2] -> [2,2,3,3,3,2,4,6,3,3,1,2,2]
[5,10,15,1,1,1,1,1,2] -> [3,3,3,3,3,2,2,2,2,2,1,1,1,1,7,1]
[13,12,2,10,14,12] -> [1,2,2,2,2,2,2,2,2,2,2,5,5,3,3,3,3,3,3,3,3,2,2,2,2]
[12,14,3,6,13,1,1] -> [2,2,2,2,2,2,2,2,2,2,2,5,4,4,2,2,2,1,1,1,1,1,1,3]
[7,5,12,5,1,10,14,5] -> [1,1,3,3,3,3,3,1,1,2,2,2,2,5,2,2,2,2,2,2,2,2,3,2,2,2,2]
[14,5,1,3,12,6,2,2,1,7,9,15] -> [1,1,1,1,1,1,1,1,1,2,2,2,2,5,2,2,1,1,1,2,2,2,2,4,8,3,3,3,3,3,3,2,2,1,1,1,1,1,1]

```

# Answer
# Jelly, ~~19~~ 13 bytes

```
IN0»0;+\+"RṬS

```

Try it online!

Saved 2 bytes thanks to @Jonathan Allan.

## Explanation

```
IN0»0;+\+"RṬS  Input: array A
I              Increments
 N             Negate
  0»           Max with 0
    0;         Prepend 0
      +\       Cumulative sum
        +"     Vectorized add with
          R    Range, vectorizes over each integer
           Ṭ   Create a list with 1's at the specified indices
            S  Sum

```
> 7 votes

# Answer
# Jelly,  ~~18~~  16 bytes

-2 bytes prompted by help from miles

Maybe there is a quicker way using mathematics rather than construction like this does?

```
IN0;»0+\0ẋ;"1ẋ$S

```

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

### How?

```
IN0;»0+\0ẋ;"1ẋ$S - Link: list of positive integers, logLengths  e.g. [4, 3, 3, 1, 4, 3]
I                - incremental differences                            [-1, 0,-2, 3,-1]
 N               - negate (vectorises)                                [ 1, 0, 2,-3, 1]
  0;             - zero concatenated with that                      [0, 1, 0, 2,-3, 1]
    »0           - maximum (vectorises) of that and zero            [0, 1, 0, 2, 0, 1]
      +\         - cumulative reduce with addition                  [0, 1, 1, 3, 3, 4]
        0ẋ       - zero repeated (vectorises)    [[],[0],[0],[0,0,0],[0,0,0],[0,0,0,0]]
              $  - last two links as a monad (right is implicitly logLengths):
            1ẋ   -   one repeated     [[1,1,1,1],[1,1,1],[1,1,1],[1],[1,1,1,1],[1,1,1]]
           "     - zip with:
          ;      -   concatenation
              [[1,1,1,1],[0,1,1,1],[0,1,1,1],[0,0,0,1],[0,0,0,1,1,1,1],[0,0,0,0,1,1,1]]
              ... this is an upside-down version of the logs like those in the OP
                  with 0 for spaces and 1 for # with any right-hand-side spaces missing.
               S - sum                                           [1, 3, 3, 5, 2, 2, 2]

```
> 7 votes

# Answer
# Python 3, 114 109 bytes

**Edit:** Saved 5 bytes thanks to @Mr.Xcoder

```
f=lambda x,i=1:x[i:]and x[i]>=x[~-i]and f(x,i+1)or[i]+f([q-(e<i)for e,q in enumerate(x)if(e<i)<q])if x else[]

```

Try it online!
> 3 votes

# Answer
# Husk, 16 bytes

```
Fż+Ṡzo`Ṙ↔ḋ2eo∫Ẋ<

```

Try it online!

### Explanation

```
              Ẋ    For all adjacent pairs, x y
               <   return max(0,x-y)
            o∫     Cumulative sum, with an extra 0 at the start
   Ṡz              Zip the input list and ^ with ...
           e         Make a two element list
        ↔ḋ2          The list [0,1]
     o`Ṙ             Repeat each in ^ by ^^
Fż+               Sum the columns

```
> 3 votes

# Answer
# Perl 5, 64 + 1 (`-a`) = 65 bytes

```
for(@F){$e<$s+--$_?$e=$s+$_:($s=$e-$_);$_++for@r[$s..$e]}say"@r"

```

Try it online!
> 1 votes

# Answer
# Mathematica, ~~76~~ ~~60~~ ~~58~~ 57 bytes

```
#2&@@@Tally[l=j=0;##&@@(Range@#+(j+=Ramp[l-(l=#)]))&/@#]&

```

Try it on Wolfram Sandbox
> 0 votes

# Answer
# Kotlin 1.1, ~~113~~ 103 bytes

```
{var l=0
var r=0
it.flatMap{l=maxOf(l,r-it+1)
r=l+it-1
(l..r).toList()}.groupBy{it}.map{it.value.size}}

```

## Beautified

```
{
    // Current row leftmost value
    var l = 0
    // Current row rightmost value
    var r = 0
    // For each log
    it.flatMap {
        // Work out the new leftmost point
        l = maxOf(
                l,
                r - it+1)
        // Use it to work out the new rightmost point
        r = l + it-1
        // Record the used columns
        (l..r).toList()}
            // Group the column numbers together
            .groupBy { it }
            // Count the amount of times each column is used
            // Put the results into a list
            .map { it.value.size }
}

```

## Test

```
var z:(List<Int>)->List<Int> =
{var l=0
var r=0
it.flatMap{l=maxOf(l,r-it+1)
r=l+it-1
(l..r).toList()}.groupBy{it}.map{it.value.size}}

fun main(args: Array<String>) {
    println(z(listOf(5, 8, 6, 2, 4, 3, 6, 2)))
    println(listOf(2,2,3,3,3,2,4,6,3,3,1,2,2))
}

```
> 0 votes

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


title: Build the Trinity Hall Prime

text:
# Question
Title: Build the Trinity Hall Prime
Based on this challenge and this Math.SE question. Idea originally come from a Numberphile video. The goal is to reproduce the *logic* of Professor McKee when he builds this prime.

Your task is to build the Trinity Hall Prime, at a much lower scale. You are given a single number N greater than 2, representing the length of the prime we need.

# Rules

* N is decomposed into a rectangle W(idth) x H(eight). W and H must be close, so 12 is 4x3 and 16 is 4x4 with W \>= H
* The first line got only 8's
* The next lines have 8's in the outer and 1's in the middle
* Each lines have 2 more 1's and 2 less 8's than the previous, except if W is odd, then the second line have only one 1 in the middle
* Once you got your emblem, find the first prime greater than the emblem.
* 2 \<= N \<= 16
* This is , so newlines must be part of the output.
* This is , so shortest code, in bytes, wins.

# Test cases:

```
I   Emblem    O
================
2   88        89

3   888       907

4   88        88
    11        19

6   888       888
    818       827

8   8888      8888
    8118      8133

9   888       888
    818       818
    111       159

10  88888     88888
    88188     88213

16  8888      8888
    8118      8118
    1111      1111
    1111      1159

```

# Answer
> 3 votes
# Python 3, 194 bytes

```
n=int(input())
R=range
w=n//max(i*(i*i<=n>1>n%i)for i in R(1,n))
m=0
for i in R(n):m=m*10+1+7*(abs(i%w*2-w+1)//2*w>i-w)
while any(m%p<1for p in R(2,m)):m+=1
m=str(m)
while m:print(m[:w]);m=m[w:]

```

Try it online!

too slow for most inputs, especially `x > 8`

-6 bytes thanks to Jonathan Frech
-98 bytes thanks to Leaky Nun

# Answer
> 2 votes
# Jelly,  ~~57~~  56 bytes

```
ŒgṖḊ$€2¦j8
Æd:2‘ịÆDðL€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ðFḌÆnDṁ⁸Gḟ⁶

```

A monadic link taking a number and returning a list of characters. As a full program it prints the result.

**Try it online!**

### How?

```
ŒgṖḊ$€2¦j8 - Link 1, previous 8-padded-row builder: list current 8-padded-row
           -                                         e.g. [8,8 , 1,1,1 , 8,8]
Œg         - group runs of equal elements                [[8,8],[1,1,1],[8,8]]
       ¦   - sparse application:
      2    - ...to indices: 2
    $€     - ...do: last two links as a monad for €ach:
  Ṗ        -   pop                                       [[8,8],[1,1  ],[8,8]]
   Ḋ       -   dequeue                                   [[8,8],[  1  ],[8,8]]
        j8 - join with eights                             [8,8, 8, 1, 8, 8,8]
           -   (note: from ...818... this yields an extra 8 - dealt with by ḣ€ in Main)

Æd:2‘ịÆDð... - Main link: number, N
Æd           - divisor count of N
  :2         - integer divided by 2
    ‘        - increment
      ÆD     - divisors of N
     ị       - index into (yields W)
        ð    - start a new dyadic chain with W on the left and N on the right...

...L€©8,8jÇÐĿḊ€ḣ€⁸Ṛ;®ẋ€⁸¤ḣ:@ð... - Main link (continued): W, N
   L€                            - length of €ach of implicit range(W) = list of W 1s
     ©                           - (copy to register for later reuse)
      8,8                        - literal [8,8]
         j                       - join -> [8,1,1,...,1,8] with W 1s
           ÐĿ                    - collect inputs until fixed point:
          Ç                      -   call the last link (1) as a monad
             Ḋ€                  - dequeue €ach (remove the leading 8 from each)
                 ⁸               - chain's right argument, N
               ḣ€                - head €ach to index (remove the trailing 8(s))
                  Ṛ              - reverse
                        ¤        - nilad followed by link(s) as a nilad:
                    ®            -   recall the [1,1,...W times...,1] from the register
                       ⁸         -   chain's left argument, W
                     ẋ€          -   repeat €ach (making W more rows of W 1s)
                   ;             - concatenate
                          :@     - integer division (sw@p arguments) = N:W = H
                         ḣ       - head to index (gets the first H rows - the mask, M)
                            ð    - start a new dyadic chain with arguments M, N

...FḌÆnDṁ⁸Gḟ⁶ - Main link (continued): M, N
   F          - flatten M
    Ḍ         - from decimal list to number
     Æn       - next prime
       D      - to decimal list
         ⁸    - chain's left argument, M
        ṁ     - mould like (reshape like the mask)
          G   - format as a grid (all digits to characters, add spaces and newlines)
            ⁶ - literal space character
           ḟ  - filter discard (Gḟ⁶ instead of Y as single row results are possible)
              - as a full program: implicit print

```

---
Tags: code-golf, ascii-art, primes
---


title: Create an auto-cucumber program

text:
# Question
Title: Create an auto-cucumber program
> Oops, Auto-correct.

You have a word. But it's wrong. You wonder what word it would be. Thankfully, being a code golfer, You can make a code to take a rough guess.

# I/O

You will be given a (wrong, all lowercase) word, and a '(All lowercase)Dictionary list'. You have to output the word with the least Levenshtein distance to the wrong word. If there are multiple words of the same levenshtein distance, use the last one in the list.

# Examples

```
Input => Output
(["apple", "banana", "orange", "pineapple"], "baenanae") => "banana"
(["zeal", "zealot", "zealotry", "zealots", "zealous", "zealously", "zealousness"], "zealousl") => "zealously"
(["abductors", "abducts", "abe", "abeam", "abel"], "") => "abe"

```

# Answer
# 05AB1E, 6 bytes

```
Σ.L(}¤

```

**Try it online!** (note: the trailing newline on the input is necessary for the empty string case.)

### How?

```
Σ.L(}¤ - implicitly push the first input (the dictionary list)
Σ   }  - sort the list by:
       -   implicitly push second input (the misspelled word)
 .L    -   Levenshtein distance
   (   -   negated
     ¤ - tail the sorted list  and place the entry on the top of the stack
       - implicitly print top of stack

```
> 1 votes

# Answer
# Python 3 + pylev, 77 bytes

```
lambda m,s:min({levenshtein(x,s):x for x in m}.items())[1]
from pylev import*

```

Try it on repl.it!
> 1 votes

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


title: Vending Machine

text:
# Question
Title: Vending Machine
# The Task

Build a function that takes a string of coins ending with an item index, and generates change as a string of coins using the least amount of coins possible.

The following are the items that can be bought (0-indexed):

`[0.45, 0.60, 0.75, 0.95, 1.10, 1.25, 1.40, 1.50, 1.75, 2.00]`

The following are the coins that can be used, with their abbreviations:

```
n = 0.05
d = 0.10
q = 0.25
D = 1.00

```

If an invalid item is selected, or the coins supplied are not enough to purchase the item, all $ is returned in the least number of coins possible.

If exact change is given, an empty string should be returned

# Test Cases

```
Dq4 = dn
qqqq4 = D
qqddddd10 = D
qqn0 = d
Dddd5 = n
qq0 = n
DD3 = Dn
Dd4 =
DDnn9 = d

```

Assume that input will only contain valid coin characters and will always terminate in an integer.

This is my first posted question, so be please be gentle when telling me how I screwed up asking it. :)

# Answer
### Python 3 - 219 213 Bytes

Fixed whitespace...

So this is awful as of right now....

```
def x(s):
 v={'n':.05,'d':.1,'q':.25,'D':1}
 r=sum([v[c]for c in s[:-1]])-[.45,.6,.75,.95,1.1,1.25,1.4,1.5,1.75,2.0][int(s[-1])]
 o=''
 for x in'Dqdn':
    r=round(r, 2)
    while v[x]<=r:
     r-=v[x]
     o+=x
 return o

```

I'll go back to see if I can't get it golfed down at all...
> 2 votes

# Answer
# Java (OpenJDK 8), ~~281~~ 271 bytes

-10 bytes thanks to Jonathan Allan

```
p->{int d[]={9,12,15,19,22,25,28,30,35,40},v[]={20,5,2,1},s=0,t;String m="Dqdn",n="";for(char c:p.toCharArray())s+=(t=m.indexOf(c))<0?0:v[t];t=p.charAt(p.length()-1)-48;s-=p.matches(".*\\d\\d")|s<d[t]?0:d[t];for(t=0;s>0;)if(s>=v[t++]){n+=m.charAt(--t);s-=v[t];}return n;}

```

Lambda that takes and returns a String

Try it online!

Ungolfed:

```
p->{
    int d[]={9,12,15,19,22,25,28,30,35,40},
        v[]={20,5,2,1},
        s=0,
        t;

    String m="Dqdn",
           n="";

    for(char c:p.toCharArray())
        s+= (t=m.indexOf(c))<0 ? 0 : v[t];

    t=p.charAt(p.length()-1)-48;
    s-= p.matches(".*\\d\\d") | s<d[t] ? 0 : d[t];
    for(t=0;s>0;)
        if(s>=v[t++]){
            n+=m.charAt(--t);
            s-=v[t];
        }
    return n;
}

```
> 2 votes

# Answer
# Python 2, ~~192~~ 176 bytes

*-16 bytes thanks to @JonathanAllan*

```
s=input()
v=0
while s[0]in'qndD':v+=[1,2,20,5][ord(s[0])%11];s=s[1:]
x=int(s)
v-=x<10and x<=v and[9,12,15,19,21,25,28,30,35,40][x]
print v/20*'D'+v%20/5*'q'+v%5/2*'d'+v%5%2*'n'

```

Try it online!
> 2 votes

# Answer
# PHP, 258 Bytes

```
$i=array(45,60,75,95,110,125,140,150,175,200);$c=array(D=>100,q=>25,d=>10,n=>5);$a=str_split($argv[1]);$p=$i[array_pop($a)];foreach($a as $x){$t+=$c[$x];$p=$c[$x]?$p:0;}$p=$t<$p?0:$p;while($t>$p){foreach($c as $n=>$x){if($t-$p>=$x){$t-=$x;echo $n;break;}}}

```

Ungolfed:

```
$i=array(45,60,75,95,110,125,140,150,175,200);
$c=array(D=>100,q=>25,d=>10,n=>5);
$a=str_split($argv[1]);
$p=$i[array_pop($a)];
foreach($a as $x){
  $t+=$c[$x];
  $p=$c[$x]?$p:0;
}
$p=$t<$p?0:$p;
while($t>$p){
  foreach($c as $n=>$x){
    if($t-$p>=$x){
      $t-=$x;
      echo $n;
      break;
    }
  }
}

```
> 1 votes

# Answer
# JavaScript (ES6), ~~230~~ 219 bytes

*-10 bytes thanks to @JonathanAllan's idea of dividing all values by 5.*
*-1 byte by moving `b="Dqdn"` into the empty `s.pop()` function call.*

```
s=>(a=[20,5,2,1],s=s.match(/\D|\d+/g),i=[9,12,15,19,22,25,28,30,35,40][s.pop(b="Dqdn")]||0,p=s.map(c=>a[b.search(c)]).reduce((y,z)=>y+z,0),(c=p-i)<0&&(c=p),a.map(v=>(x=c/v|0,c-=x*v,x)).map((v,j)=>b[j].repeat(v)).join``)

```

## Ungolfed

```
input => {
    values = [20,5,2,1];
    coins = "Dqdn";
    input = input.match(/\D|\d+/g);
    item = [9,12,15,19,22,25,28,30,35,40][input.pop()] || 0;
    payment = input.map(c => values[coins.search(c)]).reduce((y,z) => y+z, 0);
    change = payment - item;
    if (change < 0) change = payment;
    return values.map(val => {
        count = change/val | 0;
        change -= count * val;
        return count;
    }).map((count,j) => coins[j].repeat(count))
    .join``
}

```

## Test Snippet

```
f=
s=>(a=[20,5,2,1],s=s.match(/\D|\d+/g),i=[9,12,15,19,22,25,28,30,35,40][s.pop(b="Dqdn")]||0,p=s.map(c=>a[b.search(c)]).reduce((y,z)=>y+z,0),(c=p-i)<0&&(c=p),a.map(v=>(x=c/v|0,c-=x*v,x)).map((v,j)=>b[j].repeat(v)).join``)
```

```
Input<br><input oninput="O.value=/\D+\d+/.test(I.value)?f(I.value)||`<empty>`:``" id="I"><br>Result<br><input id="O" disabled>
```
> 1 votes

# Answer
## C++, ~~375~~ ~~371~~ 370 bytes

-5 bytes thanks to Zacharý

```
#include<map>
#include<vector>
#include<string>
std::map<int,int>c={{'n',1},{'d',2},{'q',5},{68,20}};void v(std::string&e){int m=0,i=0,h=0;for(;i<e.size();++i)h+=e[i]>47&&e[i]<58;m=i=0;for(;i<e.size()-1;++i)m+=c[e[i]];if(h==1){i=std::vector<int>{9,12,15,19,22,25,28,30,35,40}[e[e.size()-1]-48];m-=(m>=i)*i;}e="";for(auto&g:{68,113,100,110})while(m>=c[g]){m-=c[g];e+=g;}}

```
> 1 votes

# Answer
# Jelly,  ~~68~~  64 bytes

```
Vị“€ÐŒæı÷œ#(µ‘
ḟ®µL⁼1ȧÇ
“Þ¦£‘ɓ“Dqdn”©iÐ€ị⁹;1,0¤S¹_<?⁸Ç¤;%\:⁹®żŒṙ

```

A monadic link taking and returning lists of characters.

**Try it online!** or see the test suite.

### How?

```
Vị“€ÐŒæı÷œ#(µ‘ - Link 1, item price / 5: list of digit characters, d  e.g."4"   or "10"
V              - evaluate d as Jelly code                                  4        10
  “€ÐŒæı÷œ#(µ‘ - code page indexes = [12,15,19,22,25,28,30,40,9]
 ị             - index into (1-indexed and modular)                       22        12

ḟ®µL⁼1ȧÇ - Link 2, item price / 5: list of characters, s              e.g."Dq4" or "Dq10"
 ®       - recall register value = "Dqdn" (see Main)
ḟ        - filter discard from s                                          "4"      "10"
  µ      - monadic chain separation, call that d
   L⁼1   - length equals 1?                                                1         0
       Ç - call last link as a monad                                      22        12
      ȧ  - logical and                                                    22         0

“Þ¦£‘ɓ“Dqdn”©iÐ€ị⁹;1,0¤S¹_<?⁸Ç¤;%\:⁹®żŒṙ - Main link: list of chars, s    e.g."Dqqqq4"
“Þ¦£‘                                    - code page indexes = [20,5,2]
     ɓ                                   - dyadic chain separation, left=s right=that
      “Dqdn”                             - literal = "Dqdn"
            ©                            - copy to register and yield
              Ð€                         - map across c in s:
             i                           -   1st index (0 if not found)  [1,2,2,2,2,0]
                      ¤                  - nilad followed by link(s) as a nilad:
                 ⁹                       -   chain's right argument = [20,5,2]
                   1,0                   -   1 pair 0 = [1,0]
                  ;                      -   concatenate = [20,5,2,1,0]
                ị                        - index into (1-indexed)       [20,5,5,5,5,0]
                       S                 - sum                                    40
                              ¤          - nilad followed by link(s) as a nilad:
                            ⁸            -   chain's left argument = s
                             Ç           -   call last link as a monad(s)         22
                           ?             - if:
                          <              -          less than (coins not enough?)  0
                        ¹                - ...then: identity (do nothing, would be 40)
                         _               - ...else: subtract                      18
                               ;         - concatenate with right          [18,20,5,2]
                                 \       - cumulative reduce by
                                %        -   modulo                        [18,18,3,1]
                                   ⁹     -   chain's right argument = [20,5,2]
                                  :      - integer division                [ 0, 3,1,1]
                                    ®    - recall register value = "Dqdn"
                                     ż   - zip       [['D',0],['q',3],['d',1],['n',1]]
                                      Œṙ - run-length decode                   "qqqdn"

```
> 0 votes

---
Tags: code-golf
---


title: Generate all brace-strings of length n

text:
# Question
Title: Generate all brace-strings of length n
A brace string is defined as a string consisting of the characters `*()[]` in which braces match correctly:

```
[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

```

This is a valid brace-string:

```
((())***[]**)****[(())*]*

```

But these are not:

```
)(
**(**[*](**)
**([*)]**

```

Your task is to write a program (or function) that, given a positive integer `n`, takes a number as input and outputs (or returns) all valid brace strings of length `n`.

## Specifications

* You may output the strings in any order.
* You may output as a list or a string separated by a different character.
* Your program must handle 0 correctly. There is 1 possible brace-string of length 0, which is the empty string `""`.
* This is , so the shortest valid answer – measured in *bytes* – wins.

## Test Cases

```
0.
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*

```

# Answer
> 3 votes
# Jelly, 29 bytes

-3 bytes thanks to @JonathanAllan

*Please*, alert me if there are any problems/bugs/errors or bytes I can knock off!

```
“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

```

Try it online!

The previous solution(s) I had:

```
“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

```

Explanation (My best attempt at a description):

```
Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter

```

# Answer
> 15 votes
# Prolog, 69 bytes

```
s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

```

One of the most interesting properties of Prolog is that in many cases it's capable of running a program backwards; for example, instead of testing to see if something's true, you can generate all solutions for which it's true, and instead of checking the length of a string, you can generate all strings with a given length. (Another nice property of Prolog is that it requires whitespace after the end of each predicate definition, and a newline can be inserted as cheaply as a space; thus even golfed programs are often fairly readable.)

The above defines a predicate (the equivalent of a function) `b` which tests to see if a string has a given length and is a "brace string" as defined in the question. Specifically, it does this via Prolog's grammar/regex/pattern-match support that gives some nice, short sugar for defining this sort of expression (apparently this is standard/portable, but I was unaware of this while originally writing the answer, and thus assumed the answer would work on only one Prolog implementation; it seems it works on every implementation that complies with the standards, though). The program can be translated into English fairly directly; the first two lines say "an *s* is an empty string, or an *e* followed by an *s*; an *e* is an asterisk, or an *s* in parentheses, or an *s* in square brackets". The third line can be interpreted as "The *b* of *N* can be *A* if *A* is a list with length *N* and *A* is an *s* followed by a null string."

I took some care to write `s` (and thus `b`) so that they match each "brace string" in exactly one way (which is the reason that both `s` and `e` have to exist, rather than grouping them into one predicate). This makes them both entirely reversible; thus `b` can be used to generate all "brace strings" of a given length, in addition to testing if a string is a brace string of a given length (it can also be used a third way round, to figure out the length of a brace string, but that is almost certainly its least useful mode of operation). The implementation is recursive, e.g. to generate an *s*, the code will generate all possible *e*s that are no longer than the required length of the output, and append all possible *s*s that fit in the remaining space to them; because I specified the length of the argument in advance (within *b*), the Prolog engine knows that it can't generate output that's longer than the given length, which allows the recursion to terminate.

Here's an example of the program in operation:

```
| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

```

# Answer
> 5 votes
## Haskell, ~~101~~ 94 bytes

7 bytes saved by Zgarb!

```
b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

```

Almost straightforward, following the definition, but with the `""` case moved.

Use:

```
*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

```

(The second computation takes less than a second on a slow machine.)

I'd also like to share the result of another approach I came up with while thinking about generating functions. It defines a *list* `b` of lists of strings such that `b!!n` contains all brace-strings of length `n`. Similarly, `u!!n` contains all atoms of size `n-1`. One nice thing is that the code is not using any numbers. It is not completely golfed: `u` and `i` could be inlined, and it certainly misses a few other golfing opportunities. Unfortunately, it doesn't look like it can be made shorter than the first version, but it computes `length $ b !! 10` even faster.

```
b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)

```

# Answer
> 4 votes
# Mathematica, 116 bytes

```
#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

```

# Explanation

```
Characters@"*([)]"

```

Find the characters of the string `"*([)]"`, giving the `List` `{"*", "(", "[", ")", "]"}`.

```
... ~Tuples~#

```

Find the tuples of the above list with length `n`.

```
(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

```

Unnamed Boolean function to find whether the tuple is balanced:

```
#/."*"->Nothing

```

Delete all `"*"` in the input.

```
... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

```

Repeatedly delete all consecutive occurrences of `"("` and `")"` or `"["` and `"]"` until the input does not change.

```
... =={}

```

Check whether the result is an empty `List`.

```
Select[ ... , ... ]

```

Find the tuples that give `True` when the Boolean function is applied.

```
#<>""&/@

```

Convert each `List` of characters into `String`s.

# Answer
> 4 votes
# Python 2, 128 bytes

```
n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

```

Screw recursive regexes – we’re using Python’s parser! In order to verify that, for example, `*(**[])*` is a brace-string, we do the following:

1. Make a string like `"*", (0,"*","*", [0,0] ,0) ,"*"`, where every second character of four is a character from the brace-strings, and the remaining characters are *glue* to make this a potential Python expression.
2. `eval` it.
3. If that doesn’t throw an error, print `s[1::4]` (the brace-string characters).

The *glue* characters are picked so that the string I make is a valid Python expression if and only if taking every second character out of four yields a valid brace-string.

# Answer
> 2 votes
# PHP, 149 bytes

```
for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

```

Uses the good old generate all possible and then filter method. Use like:

```
php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4

```

# Answer
> 1 votes
# Python 3.5, 146 bytes

```
import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

```

Very long compared to other answers, but the shortest one I could currently find. It is in the form of an anonymous lambda function and therefore must be called in the format

`print(<Function Name>(<Integer>))`

Outputs a Python *set* of *unordered* strings representing all possible brace-strings of the input length.

For example, assuming the above function is named `G`, invoking `G(3)` would result in the following output:

```
{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

```

Try It Online! (Ideone)

---

However, if, like me, you aren't really a fan of simplifying things using built-ins, then here is my own *original* answer *not* using *any* external libraries to find permutations, and currently standing at a whopping **~~288~~ 237 bytes**:

```
import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

```

Again, like the competing answer, this one is in the form of a lambda function and therefore must also be called in the format

`print(<Function Name>(<Integer>))`

And outputs a Python *list* of *unsorted* strings representing all brace-strings of the input length. For example, if the lambda were to be invoked as `G(3)`, this time the output would be the following:

```
['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

```

Also, this one is also a lot faster than my other answer, being able to find all brace-strings of length `11` in about **115 seconds**, those of length `10` in about **19 seconds**, those of length `9` in about **4 seconds**, and those of length `8` in about **0.73 seconds** on my machine, whereas my competing answer takes *much* longer than 115 seconds for an input of `6`.

Try It Online! (Ideone)

# Answer
> 1 votes
# Python, 134 bytes

```
from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

```

**repl.it**

Unnamed function that returns a list of valid strings of length `n`.
Forms all length `n` tuples of the characters `*()[]`, joins them into strings using `map(''.join,...)` and filters for those that have balanced brackets by removing the "pairs" `"*"`, `"()"`, and `"[]"` in turn `n` times and checking that the result is an empty string (`n` times is overkill, especially for `"*"` but is golfier).

# Answer
> 1 votes
## Retina, 78 bytes

Byte count assumes ISO 8859-1 encoding.

```
.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

```

Try it online!

### Explanation

I'm generating all possible strings of length 5 and then I filter out the invalid ones.

```
.+
$*

```

This converts the input to unary, using `1` as the digit.

```
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

```

This repeatedly (`+`) replaces the first (`1`) one in each line (`%`) in such a way that it makes five copies of the line, one for each possible character. This is done by using the prefix and suffix substitutions, `$`` and `$'` to construct the remainder of each line.

This loop stops when there are no more 1s to replace. At this point we've got all possible strings of length `N`, one on each line.

```
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

```

These two stages are executed for each line separately (`%`). The first stage simply duplicates the line, with a `;` to separate the two copies.

The second stage is another loop (`+`), which repeatedly removes `[]`, `()` or `*` from the first copy of the string, *or* removes a semicolon at the beginning of the line (which is only possible after the string has vanished completely).

```
A`;

```

Valid strings are those that no longer have a semicolon in front of them, so we simply discard all lines (`A`) which contain a semicolon.

# Answer
> 0 votes
# 05AB1E, 23 bytes

```
…[(*.∞sãʒ'*м„()„[]‚õ:õQ

```

Some of these features might have been implemented after the question was posted. Any suggestions are welcome!

Try it online!

# How?

```
…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string

```

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


title: ASCII L-system renderer

text:
# Question
Title: ASCII L-system renderer
## Background

An L-system (or Lindenmayer system) is a parallel rewriting system that, among other things, can be easily used to model fractals. This question concerns **deterministic, context-free L-systems**. These consists of an alphabet of symbols, an initial axiom string and a set of rewrite rules mapping each alphabet symbol to a new string. The rules are applied to the axiom in parallel, generating a new string. This process is then repeated.

For example, the system with the axiom "A" and the rules A=ABA;B=BBB generates the sequence of strings "ABA", "ABABBBABA", "ABABBBABABBBBBBBBBABABBBABA", etc. For conciseness, we don't explicitly mention the alphabet when defining the L-system. Furthermore, any symbol without an explicit rewrite rule is assumed to be unchanged (i.e. the default rule for a symbol A is A=A).

L-systems can be visualised using a form of turtle graphics. By convention, the turtle starts facing to the right. A string is then drawn by iterating over its symbols: an F means "draw forward one unit", a G means "move forward one unit", a + means "turn left one angle unit" and a - means "turn right one angle unit". All other symbols in the string are ignored. For the purpose of this question, the angle units are assumed to always be 90°.

## Task

Given a specification of any L-system and a number of iterations, your program should output an ASCII rendering of the resulting string (as described above) using box-drawing characters.

* The parameters are passed in as a space-separated string comprising the axiom, rewrite rules (as a ;-separated list of equations) and number of rewrite iterations. For example, the input "F F=FGF;G=GGG 2" generates the string "FGFGGGFGF" and hence draws four lines with appropriate gaps.
* The symbols used by the L-system can be any ASCII character apart from space and semicolon. There is at most one explicit rule specified per symbol (with the default rewrite rule being the identity mapping as described above).
* You can assume that the output will always contain at least one F.
* The output should use the following UNICODE box-drawing characters to represent the visualization: ─ (U+2500), │ (U+2502), ┌ (U+250C), ┐ (U+2510), └ (U+2514), ┘ (U+2518), ├ (U+251C), ┤ (U+2524), ┬ (U+252C), ┴ (U+2534), ┼ (U+253C), ╴ (U+2574), ╵ (U+2575), ╶ (U+2576) and ╷ (U+2577). See below for examples.
* The output should not contain empty lines above the topmost box character or below the bottommost one. It should also not contain any spaces to the left of the leftmost box characer or to the right of the rightmost one. Lines with trailing spaces that don't extend beyond the rightmost box character are allowed.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative), saved to a file or returned as a string.

## Examples

```
# Cantor dust
>> "F F=FGF;G=GGG 0"
╶╴
>> "F F=FGF;G=GGG 1"
╶╴╶╴
>> "F F=FGF;G=GGG 2"
╶╴╶╴  ╶╴╶╴
>> "F F=FGF;G=GGG 3"
╶╴╶╴  ╶╴╶╴        ╶╴╶╴  ╶╴╶╴

# Koch curve
>> "F F=F+F−F−F+F 1"
 ┌┐
╶┘└╴
>> "F F=F+F-F-F+F 2"
    ┌┐
   ┌┘└┐
  ┌┘  └┐
 ┌┼┐  ┌┼┐
╶┘└┘  └┘└╴

```

Other examples to test your program with include:

```
# Dragon curve
>> "FX X=X+YF+;Y=-FX-Y n"

# Hilbert curve
>> "A A=-BF+AFA+FB-;B=+AF-BFB-FA+ n"

# Sierpinski carpet
>> "F F=F+F-F-F-G+F+F+F-F;G=GGG n"

```

The first two of which look as follows (produced using @edc65's answer):

You can test out any of the systems at this page.

## Scoring

Shortest code (in bytes) wins. Standard rules apply.

## Miscellania

This challenge was inspired by Draw a Random Walk with Slashes. In fact, it's possible to represent a random walk as an L-system if we extend the system to allow multiple rules per symbol, with the expansion chosen *non-determistically* during rewriting. One formulation is:

```
"F F=FF;F=F+F;F=F++F;F=F+++F"

```

Another common extension, often used when modeling plants, is to interpret the \[ and \] characters as pushing and popping the current position and angle. Most plants use angles smaller than 90°, but here is one example that doesn't:

```
"FAX X=[-FAX][FAX][+FAX];A=AFB;B=A"

```

Neither of these examples need to be supported in this challenge.

This challenge is also similar to "Sorry, young man, but it's Turtles all the way down!". However, that challenge used line rendering rather than ASCII and allowed a more flexible syntax.

# Answer
> 7 votes
# JavaScript (ES6), 440 bytes (410 chars)

```
F=p=>([a,r,n]=p.split(' '),t=>{r.split(';').map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join('');u=x=y=0,g=[];for(c of a)c=='+'?[t,u]=[u,-t]:c=='-'?[u,t]=[t,-u]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join('')).join('\n')

```

*Less golfed*

```
F=p=>{
  [a,r,n]=p.split(' '),
  r.split(';').map(x=>r[x[0]]=x.slice(2),r={}); // set rules
  for(;n--;)a=[...a].map(c=>r[c]||c).join(''); // build string
  t=1,u=x=y=0, // start pos 0,0 start direction 1,0
  g=[[]]; // rendering in bitmap g
  for(c of a)
    c=='+'?[t,u]=[u,-t] // left turn
    :c=='-'?[u,t]=[t,-u] // right turn
    :c=='F'|c=='G'?(     // move or draw
      (y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[], // move vertical, enlarge grid if needed
      (x+=t)<0?(g=g.map(r=>[,...r]),++x):0, // move horizontal, enlarge grid if needed
      c=='F'&&( // draw: set bits
        f=t?0.5:2,
        g[y][x]|=(3+t-u)*f,
        g[y-u][x-t]|=(3+u-t)*f
      )
    ):0;
  // render bits as box characters
  return g.map(r=>[' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]for(c of r)].join('')).join('\n')
}

```

**Test** Code snippet to test (in Firefox)

```
F=p=>([a,r,n]=p.split(' '),t=>{r.split(';').map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join('');u=x=y=0,g=[];for(c of a)c=='+'?[t,u]=[u,-t]:c=='-'?[u,t]=[t,-u]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)' ╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join('')).join('\n')

fs=18;(Z=d=>(Result.style.fontSize=(fs+=d)+'px',Result.style.lineHeight=fs+'px'))(0)
```

```
#Result { font-size: 10px }
#Param { width: 400px }
```

```
Param: <input type=text id=Param />
<button onclick="Result.innerHTML=F(Param.value)">Start</button><br>
Output <button onclick="Z(-2)">Z-</button> <button onclick="Z(2)">Z+</button>
<br>
<pre id=Result></pre>
```

# Answer
> 6 votes
# Haskell, 568 bytes

```
import Data.List.Split
p=splitOn
l=lookup
m=maximum
n=minimum
o[h,x]=(h,x)
Just x#_=x
_#x=x
g[s,r,i]=iterate((\c->lookup[c](map(o.p"=")(p";"r))#[c])=<<)s!!read i
u v@(a,x,y,d,e)c|c=='+'=(a,x,y,-e,d)|c=='-'=(a,x,y,e,-d)|c=='G'=(a,x+d,y+e,d,e)|c=='F'=(s(x,y)(d%e)a:s(x+d,y+e)(d?e)a:a,x+d,y+e,d,e)|1<2=v
s p n a=(p,n+(l p a)#0)
1%0=2;0%1=8;-1%0=1;0%(-1)=4
1?0=1;0?1=4;-1?0=2;0?(-1)=8
f z=unlines[[" ╴╶─╷┐┌┬╵┘└┴│┤├┼"!!(l(x,y)q#0)|x<-[n a..m a]]|y<-[m b,m b-1..n b]]where a=map(fst.fst)q;b=map(snd.fst)q;(q,_,_,_,_)=foldl u([],0,0,1,0)$g$p" "z

```

Test run:

```
*Main> putStr $ f "F F=F-F+F+F-F 3"
╶┐┌┐  ┌┐┌┐        ┌┐┌┐  ┌┐┌╴
 └┼┘  └┼┼┘        └┼┼┘  └┼┘
  └┐  ┌┼┼┐        ┌┼┼┐  ┌┘
   └┐┌┼┘└┘        └┘└┼┐┌┘
    └┼┘              └┼┘
     └┐              ┌┘
      └┐┌┐        ┌┐┌┘
       └┼┘        └┼┘
        └┐        ┌┘
         └┐┌┐  ┌┐┌┘
          └┼┘  └┼┘
           └┐  ┌┘
            └┐┌┘
             └┘

```

How it works:

* rewriting (function `g`): I parse the rules into an association list (letter -\> replacement string) and repeatedly map it over the axiom.
* creating the path (function `u` for a single step): I do not store the path in a matrix but in another association list with (x,y) positions as the keys and bit patterns of the 4 basic blocks (,, and ) as values. Along the way I keep track of the current position and direction.
* drawing the path (function `f`): first I calculate the max/min dimensions from the path list and then I iterate over \[max y -\> min y\] and \[min x -\> max x\] and lookup the blocks to draw.

# Answer
> 0 votes
# ES7, 394 chars, 424 bytes

```
F=p=>([a,r,n]=p.split` `,t=>{r.split`;`.map(x=>r[x[0]]=x.slice(2),r={});for(;n--;)a=[...a].map(c=>r[c]||c).join``;u=x=y=0,g=[];for(c of a)c=='+'||c=='-'?[t,u]=[u,-t]:c<'F'|c>'G'?0:((y+=u)<0?(g=[[],...g],++y):g[y]=g[y]||[],(x+=t)<0?(g=g.map(r=>[,...r]),++x):0,c>'F'?0:g[g[f=t?0.5:2,y][x]|=(3+t-u)*f,y-u][x-t]|=(3+u-t)*f)})(1)||g.map(r=>[for(c of r)'╶╴─╵└┘┴╷┌┐┬│├┤┼'[~~c]].join``).join`
`

```

---
Tags: code-golf, string, ascii-art, fractal
---