title: Decompose a number!

text:
# Question
Title: Decompose a number!
Your task is to decompose a number using the format below.

This is similar to base conversion, except that instead of listing the `digits` in the base, you list the `values`, such that the list adds up to the input.

If the given base is \\$n\\$, then each number in the list must be in the form of \\$k\times n^m\\$, where \\$0\le k\<n\\$ and \\$m\\$ is unique throughout the list.

# Specs

* Any reasonable input/output format. Your program/function takes 2 inputs and outputs a list.
* Output list can be in any order.
* `0` can be excluded or included.
* Leading `0`s are allowed.
* Built-ins are **allowed**.

# Testcases

```
number base   converted list
input1 input2 output
123456 10     [100000,20000,3000,400,50,6] or [6,50,400,3000,20000,100000]
11     2      [8,2,1] or [0,0,0,0,8,0,2,1]
727    20     [400,320,7]
101    10     [100,1] or [100,0,1]

```

# Scoring

This is . Shortest solution in bytes wins.

# Answer
> 7 votes
# Jelly, 7 bytes

```
lr0⁹*×b

```

Try it online! or verify all test cases.

### How it works

```
lr0⁹*×b  Main link. Arguments: x (integer), n (base)

l        Compute the logarithm of x to base n.
 r0      Range; yield all non-negative integers less than the logarithm, in
         decreasing order.
   ⁹*    Elevate n to all integers in that range.
      b  Yield the list of base-n digits of x.
     ×   Multiply each digit by the corresponding power of n.

```

# Answer
> 5 votes
## JavaScript (ES6), 47 bytes

```
f=(n,b,p=1,q=b*p)=>[...n<q?[]:f(n,b,q),n%q-n%p]
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(...c)).join`\n`)
```

# Answer
> 4 votes
# Pyth - ~~12~~ 11 bytes

Just a FGITW, can be shorter.

```
.e*b^Qk_jEQ

```

Test Suite.

# Answer
> 4 votes
## Jelly, 12 bytes

```
bLR’*@€U
b×ç

```

Can be waaaay shorter...

Try it online!

# Answer
> 4 votes
# J, ~~20~~ 19 bytes

```
[(]*(^<:@#\.))#.inv

```

## Usage

```
   f =: [(]*(^<:@#\.))#.inv
   10 f 123456
100000 20000 3000 400 50 6
   2 f 11
8 0 2 1
   20 f 727
400 320 7
   10 f 101
100 0 1

```

## Explanation

```
[(]*(^<:@#\.))#.inv
              #.      Given a base and list of digits in that base,
                      converts it to an integer in base 10
                inv   Power conjunction by -1, creates an inverse
                      Now, this becomes a verb that given a base and an integer in base 10,
                      creates a list of digits in that base representing it
[                     Select the base and pass it along
         #\.          Tally each suffix of the list of base digits,
                      Counts down from n to 1
      <:              Decrements each value
        @             More specifically, decrement is composed with the tally and applied
                      together on each suffix
     ^                Raises each value x using base^x
  ]                   Selects the list of base digits
   *                  Multiply elementwise between each base power and base digit

```

# Answer
> 3 votes
## CJam, 16 bytes

```
{1$b\1$,,f#W%.*}

```

An unnamed block that expects the base and the number on top of the stack (in that order) and replaces them with the digit list (including internal zeros, without leading zeros).

Test it here.

### Explanation

```
1$  e# Copy base b.
b   e# Compute base-b digits of input number.
\   e# Swap digit list with other copy of b.
1$  e# Copy digit list.
,   e# Get number of digits M.
,   e# Turn into range [0 1 ... M-1].
f#  e# Map b^() over this range, computing all necessary powers of b.
W%  e# Reverse the list of powers.
.*  e# Multiply each digit by the corresponding power.

```

# Answer
> 3 votes
# TSQL, 68 bytes

```
DECLARE @ INT=123456,@z INT=10
DECLARE @l INT=1WHILE
@>0BEGIN PRINT @%@z*@l SELECT @/=@z,@l*=@z END

```

# Answer
> 3 votes
# Mathematica, 46 bytes

```
DiagonalMatrix@IntegerDigits@##~FromDigits~#2&

```

**Explanation:**

```

In[1]:= IntegerDigits[123456,10]

Out[1]= {1, 2, 3, 4, 5, 6}

In[2]:= DiagonalMatrix@IntegerDigits[123456,10] // MatrixForm

Out[2]//MatrixForm= 1   0   0   0   0   0

                    0   2   0   0   0   0

                    0   0   3   0   0   0

                    0   0   0   4   0   0

                    0   0   0   0   5   0

                    0   0   0   0   0   6

In[3]:= DiagonalMatrix@IntegerDigits[123456,10]~FromDigits~10

Out[3]= {100000, 20000, 3000, 400, 50, 6}

```

# Answer
> 3 votes
# Mathematica, 12 bytes

I wonder whether Wolfram Research created this function after seeing the OP's challenge!

```
NumberExpand

```

This was introduced in version 11.0 (August, 2016).

# Answer
> 3 votes
# Jelly, 8 bytes

```
bḅ²×¥@b×

```

Try it online!

`²×¥@` seems too long for what it does. I hope there is a shorter way.

### Explanation

```
b             Convert A (the input number) to base B (the input base).
 ḅ²×¥@        Convert from base A×B²
      b×      Convert to base A×B

```

# Answer
> 3 votes
# Regex (ECMAScript), 76 bytes

```
(?=.*,(x(x*)))(?=.*?(((?=(?=\1*,)(x(x*))(?=\5*,)(?=\2+,)(\2\6*),)\7)*x),)\3+

```

Takes its input in unary, as the length of two string of `x`s delimited by a `,` (number first, then base). Returns its result as the list of matches (each is also a string of `x`s whose length is the value).

Try it online!

It's a good thing the challenge allows `0` to be excluded or included, because this solution excludes it, and it would not be possible to include it! (The only way to include it would be either to use .NET with the result returned via a capture's stack, or PCRE with a callout.)

The division algorithm is explained in my Division and remainder post.

```
# If this is the first match, tail = N = input number. Otherwise
# tail = N = current intermediate value, which is the input number
# after having the previous return values all subtracted from it.
(?=
    .*,(x(x*))             # \1 = number base; \2 = \1 - 1
)
(?=
    .*?                    # Decrease tail by the minimum necessary to satisfy
                           # the following assertion:
    # Assert tail is a power of \1; \3 = tail = the largest power of \1 that is
    # less than or equal to N.
    (                      # \3 = tail
        (
            (?=
                # Calculate \5 = tail / \1
                (?=\1*,)   # Assert tail is divisible by \1
                (x(x*))    # \5 = quotient - find the largest that matches the
                           #      following assertions; \6 = \5-1; tail -= \5
                (?=\5*,)   # assert tail is divisible by quotient
                (?=\2+,)   # assert tail is positive and divisible by divisor-1
                (\2\6*),   # assert tail-(divisor-1) is divisible by quotient-1;
                           # \7 = tool to make tail = \5
            )\7            # tail = \5
        )*                 # Iterate the above as many times as possible
        x                  # tail -= 1
    )
    ,                      # Assert tail == 0
)
\3+                        # Return value = M = tail - (tail % \3); tail -= M

```

# Answer
> 2 votes
## Python 2, 44 bytes

```
lambda n,b:[n/b**i%b*b**i for i in range(n)]

```

Outputs from least significant to most, with many extra zeroes.

To output most significant to least:

```
f=lambda n,b,c=1:n*[1]and f(n/b,b,c*b)+[n%b*c]

```

Recurse, repeatedly taking digits off of `n` with divmod while scaling up the place value multiplier `c`.

# Answer
> 2 votes
# Ruby, ~~35~~ 34 bytes

This is a port of xnor's Python answer, but it prints `n` times so the test case `727 20` prints `7`, `320`, `400`, and 724 `0`s. Golfing suggestions welcome.

**Edit:** 1 byte thanks to Jordan.

```
->n,b{n.times{|i|p n/b**i%b*b**i}}

```

# Answer
> 2 votes
## Pip, 13 bytes

```
Wa-:Pa%oo*:b

```

Doing it the old-fashioned way turned out to be shorter than using the `TB` base-conversion operator. The code runs a while loop until `a` (the number) is `0`. At each iteration, it prints `a%o` and subtracts it from `a`. `o` is preinitialized to `1` and gets multiplied by `b` (the base) each iteration. (This approach keeps all `0`s and also adds a leading `0`.)

Try it online!

# Answer
> 2 votes
# Vyxal `r`, 7 bytes

```
τ:ẏṘ⁰e*

```

Try it Online!

A nice little answer. Takes `value` then `base`

## Explained

```
τ:ẏṘ⁰e*
τ       # Convert value from base 10 to input base
 :ẏṘ    # Duplicate that and push the range [len(that) - 1, 0]
    ⁰e  # Raise base to the power of each item in that
      * # Multiply that by the list of digits of the converted value

```

# Answer
> 2 votes
# JavaScript (V8), 44 bytes

```
b=>g=n=>n?[...g(~~(n/b)).map(i=>i*b),n%b]:[]

```

Try it online!

Takes curried input in the form `function(base)(number)`.

# Answer
> 2 votes
# Desmos, 57 bytes

```
k=b^{[floor(log_b(n+0^n))...0]}
f(n,b)=mod(floor(n/k),b)k

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 2 votes
# BQN, 18 bytes

```
-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+

```

Tacit function; takes the base as left argument and the number as right argument. Try it at BQN online!

### Explanation

Call the left argument `b` and the right argument `n`.

```
-⟜»⊢|˜⊣⋆1+·↕∘⌈⊣⋆⁼+
                ⋆⁼   Inverse exponential (i.e. logarithm)
               ⊣     with base b
                  +  of b + n
              ⌈       Round up to nearest integer
                     This number is at least as large as the number of base-b digits n has
            ↕∘       Range (0-based, exclusive)
         1+·         Add 1 to each
       ⊣⋆            Raise b to each of those exponents
    ⊢|˜              Take n mod each of those powers of b
   »                 Shift a copy of that list right, prepending a 0
-⟜                  and subtract it from the unshifted list

```

For example, with a base of 3 and a number of 17, we have

```
+       20
⊣⋆⁼     2.726833027860842
1+·↕∘⌈   ⟨ 1 2 3 ⟩
⊣⋆      ⟨ 3 9 27 ⟩
⊢|˜     ⟨ 2 8 17 ⟩
»       ⟨ 0 2 8 ⟩
-⟜     ⟨ 2 6 9 ⟩

```

# Answer
> 1 votes
# Racket, 82 bytes

```
(define(d n b[a'()])(if(< n 1)a(d(/ n b)b(cons(*(modulo(floor n)b)(length a))a))))

```

*I'm a winner (!)*

# Answer
> 1 votes
# JavaScript (ES7), 68 bytes

```
n=>b=>(c=[...n.toString(b)]).map(d=>b**--p*parseInt(d,b),p=c.length)

```

## Test

Test uses `Math.pow` for browser compatibility.

```
f=n=>b=>(c=[...n.toString(b)]).map(d=>Math.pow(b,--p)*parseInt(d,b),p=c.length)
document.write("<pre>"+
[ [ 123456, 10 ], [ 11, 2 ], [ 727, 20 ], [ 101, 10 ] ]
.map(c=>c+" => "+f(c[0])(c[1])).join`\n`)
```

# Answer
> 1 votes
# JavaScript, 75 bytes

```
(a,b)=>[...a.toString(b)].reverse().map(($,_)=>Math.pow(b,_)*parseInt($,b))

```

Just for fun :) It could be golfed more, but I'm not too sure how.

## ES7, 66 bytes

If ES7 is allowed then:

```
(a,b)=>[...a.toString(b)].reverse().map(($,_)=>b**_*parseInt($,b))

```

# Answer
> 1 votes
# , 17 bytes

```
jQb`S/l{#Qn^*p}d

```

Two notes:

1. **The third test case does not work due to a bug with base conversion.** See phase/o#68.
2. This does not work in the online interpreter. `b` hadn't been implemented yet.

# Answer
> 1 votes
# \>\<\>, 28 bytes

```
:&\
&*>:{:}$%:n$}-:0=?;ao$&:

```

Expects the input values to be present on the stack at program start.

As \>\<\> doesn't have list objects, the output is presented as a newline-separated list of values, with the 'units' on the first line. An example run:

```
Input:
11 2

Ouput:
1
2
0
8

```

@OP, if this isn't an acceptable output format, let me know and I'll edit the answer accordingly.

# Answer
> 1 votes
# PHP, 55 bytes

Uses Windows-1252 encoding.

```
for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó;

```

Run like this (`-d` added for aesthetics only):

```
php -d error_reporting=30709 -r 'for($n=$argv[1];$d+$n-=$d=$n%$argv[2]**++$i;)echo$d,~Ó; echo"\n";' 123056 10

```

# Answer
> 1 votes
## C#, 77 bytes

```
IEnumerable _(int n,int b){int m=1;while(n>0){yield return n%b*m;n/=b;m*=b;}}

```

# Answer
> 1 votes
## Actually, 17 bytes

```
;a¡;lrR(♀ⁿ@♂≈♀*;░

```

Try it online!

Explanation:

```
;a¡;lrR(♀ⁿ@♂≈♀*;░
                   initial stack: [b n] (b = base, n = number)
;                  dupe b
 a                 invert stack
  ¡                n as a base-b integer
   ;lrR            dupe, length, range, reverse
       (♀ⁿ         raise b to each power in range
          @♂≈      create list of integers from base-b string
             ♀*    pairwise multiplication
               ;░  filter out zeroes

```

# Answer
> 1 votes
# C++, 82 Bytes

```
int*f(int n,int b){int*a,o[n]{b,n%b};for(a=o+1;*a=(n-=*a++)%(b*=*o););return o+1;}

```

The main loop is pretty trivial (keep taking modulos and subtracting the lower part). The main savings come from doing lots of calculations in-place and the loop condition being the actual assigned value (which will eventually become 0, after all meaningful output is written to the array)

I haven't been able to figure out why, but ideone throws a runtime error if I try to have the function return `o` instead of `o+1`, so I use the extra index to store the powers of b.

---
Tags: code-golf, number, sequence, number-theory, base-conversion
---


title: Weighted coin flip strings

text:
# Question
Title: Weighted coin flip strings
Given n, k, and p, find the probability that a weighted coin with probability p of heads will flip heads at least k times in a row in n flips, correct to 3 decimal digits after decimal point (changed from 8 because I don't know how to estimate the accuracy of double computation for this (was using arbitrary precision floating points before)).

Edits:

Examples:

```
n, k, p     -> Output
10, 3, 0.5  -> 0.5078125
100, 6, 0.6 -> 0.87262307
100, 9, 0.2 -> 0.00003779

```

# Answer
> 10 votes
# 05AB1E, ~~40~~ ~~39~~ ~~18~~ 17 bytes

**Brute-force approach:**

```
0Lα1Ý²ãʒγOà³@}èPO

```

Byte-count more than halved by porting *@JonathanAllan*'s Jelly answer, which uses a similar approach as @DominicVanEssen's top R answer, so make sure to upvote them as well!

Inputs in the order \\$p,n,k\\$.
Very slow, so use small \\$n\\$ in order to run it on TIO.

Try it online.

**Original mathematical ~~40~~ 39 bytes approach:**

```
÷L®s©>m²®¹*-D>®/$-*I+s®<cI®¹*m$-®<m)øPO

```

Inputs in the order \\$k,n,p\\$.

Try it online.

**General explanation of the larger original program:**

Even though the challenge description was just a single sentence, it lead me on a chase down the rabbit hole. After quite a long search, I came across this MathExchange answer: Probability for the length of the longest run in *n* Bernoulli trials, for which the accepted answer contains the generalized formula for this challenge, originally solved by *de Moivre* in 1738:

$$\mathbb{P}(\ell\_n \geq k)=\sum\_{j=1}^{\lfloor n/k\rfloor} (-1)^{j+1}\left(p+\left({n-jk+1\over j}\right)(1-p)\right){n-jk\choose j-1}p^{jk}(1-p)^{j-1}$$

Where \\$\mathbb{P}(\ell\_n \geq k)\\$ is the probability that a consecutive run of the same unfair coin result with a length \\$\ell\_n\\$ is at least \\$k\\$ flips. \\$p\\$, \\$k\\$, and \\$n\\$ are as given by the challenge description, with \\$p\\$ being a decimal probability (e.g. 0.70 for 70%), and \\$k\\$ and \\$n\\$ being integers.

**Code explanation:**

```
0L              # Push pair [1,0]
  α             # Get the absolute difference with the first (implicit) input p:
                #  [1-p,p]
   1Ý           # Push pair [0,1]
     ²ã         # Get the second input n'th cartesian product
                # (creating all n-sized lists with 0s/1s)
       ʒ        # Filter this list by:
        γ       #  Group the 0s/1s into consecutive adjacent items
         O      #  Sum each group
          à     #  Pop and push the maximum
           ³@   #  Check if this largest group of 1s is >= the third input k
       }è       # After the filter: (0-based) index each 0/1 into pair [1-p,p]
         P      # Take the product of each inner list
          O     # Take the sum of all values
                # (after which the result is output implicitly)

```

```
÷               # Integer divide the first two (implicit) inputs: n//k
 L              # Pop and push a list in the range [1,n//k] (its values are j)
  ®             # Push -1
   s            # Swap so the list is at the top
    ©           # Store it in variable `®` (without popping)
     >          # Increase each j in the list by 1
      m         # Pop both, and calculate -1**(j+1) for each
  ®             # Push the list `®` containing j again
   ¹*           # Multiply each j by the first input k
 ²   -          # Subtract each from the second input n
      D         # Duplicate this n-jk list, since we need it again later
       >        # Increase each by 1
        ®/      # Divide each by j
          $     # Push 1 and the third input p
           -    # Subtract: 1-p
            *   # Multiply this to each (n-jk+1)/j
             I+ # And add the third input p to each
 s              # Swap so the n-jk list is at the top again
  ®             # Push list `®` containing j again
   <            # Decrease each j by 1
    c           # Calculate the binomial coefficients of n-jk and j-1
 I              # Push the third input p again
  ®             # Push list `®` containing j again
   ¹*           # Multiply each j by the first input k again
     m          # Pop both, and calculate p**(jk)
 $              # Push 1 and the third input p again
  -             # Subtract again: 1-p
   ®            # Push list `®` containing j again
    <           # Decrease each j by 1 again
     m          # Calculate (1-p)**(j-1)
 )              # Wrap these five lists on the stack into a list of lists
  ø             # Zip/transpose; swapping rows/columns
   P            # Get the product of each inner list
O               # And finally sum everything together
                # (which is output implicitly as result)

```

# Answer
> 7 votes
# Jelly,  ~~19~~  15 bytes

```
Ø.ṗṣ1ZṫɗƇ_⁵AP€S

```

A full program accepting `n`, `k`, and `p` that prints the result.

**Try it online!** (`n=100` is too big for such an inefficient program.)

### How?

Creates all \\$2^{n}\\$ possible outcomes, filters them to those containing a run of at least \\$k\\$ heads and then sums the probability of each occurrence.

The probability of a given occurrence is the product of `p`'s and `(1-p)`s identified by heads and tails respectively. For example the chance of `[tails, tails, heads, heads, heads]` is the product of `[(1-p), (1-p), p, p, p]` i.e. \\$p^3(1-p)^{2}\\$.

```
Ø.ṗṣ1ZṫɗƇ_⁵AP€S - Main Link: integer n, integer k (p is accessed later)
Ø.              - [0,1]
  ṗ             - ([0,1]) Cartesian power (n)
                  -> all length-n tosses with 0 as heads and 1 as tails
        Ƈ       - filter keep those for which:
       ɗ        -   last three links as a dyad - f(Outcome, k):
   ṣ1           -     split at 1s -> runs of heads
     Z          -     transpose
      ṫ         -     tail from index k -> empty (falsey) if longest run < k
          ⁵     - third program argument, p
         _      - subtract -> valid outcomes with heads: -p; tails: 1-p
           A    - absolute values -> valid outcomes with heads: p; tails 1-p
            P€  - product of each -> valid outcome probabilities
              S - sum -> total probability of any valid outcome

```

---

If we could take the probability of tails (\\$1-p\\$) instead of heads (\\$p\\$) 14 byes taking `1-p`, `n`, `k`:

```
C©Ƭṗṣ®ZṫɗƇ⁵P€S

```

Try it online!

# Answer
> 7 votes
# Python, 66 bytes (-1 @xnor)

```
f=lambda n,k,p:n>=k and(1-p*(n>k))*(1-f(n+~k,k,p))*p**k+f(n-1,k,p)
```

Attempt This Online!

Adapted from my answer to a similar challenge. Note that I add memoization in the footer. This in theory doesn't change the result but it greatly accelerates the recursion.

### How?

Uses the recurrence

\\$f(n,k,p)=f(n-1,k,p)+p^k(1-p)(1-f(n-k-1,k,p))\\$

(valid for *n*\>*k*) which is obtained by accounting for words that have k consecutive heads somewhere in the first n-1 tosses, words that end in a tail followed by k heads and the overlap of these two groups.

# Answer
> 5 votes
# , ~~129~~ ~~122~~ 116 bytes

*Edit: -2 bytes thanks to pajonk (which led to -4 more...)*

```
function(n,k,p)sum(apply(which(array(T,rep(2,n)),T)-1,1,function(v,r=rle(v))prod(p*v+(1-p)*!v)*(max(r$l[!r$v])>=k)))

```

Try it online!

Exact solution: calculates the probability of every possible outcome of `n` coin flips, and sums those that contain at least `k` heads-in-a-row.

**How?**

```
function(n,k,p){
    a=expand.grid(rep(list(1:0),n)) # a is a matrix of all possible outcomes of n flips
                                    # with heads represented as 0, tails as 1
    pvals=apply(a,1,function(v)prod(p*v+(1-p)*!v))
                                    # pvals are the probabilities of each outcome
                                    # by multiplying the probability of each single flip
    itsarun=apply(a,1,function(v)max(rle(v)$l[!rle(v)$v])>=k)
                                    # itsarun is TRUE if the longest run of 0s in each row is >=k
                                    # (rle(v)$l = length of each run, rle(v)$v = value of each run)
    return(sum(pvals*itsarun))      # return the sum of all the pvals for successful outcomes
}

```

---

# , 98 bytes

```
function(n,k,p){while((T=T+1)<1e19)F=F+(max((r=rle(sample(1:0,n,T,c(1-p,p))))$l[!r$v])>=k);F/1e19}

```

Try it online with a low-accuracy version

Brute-force approach: performs `1e19` series of `n` flips, and counts the number of times we get `k` heads-in-a-row. With this number of repetitions, the answer has a very high chance of being accurate to 8 decimal places, but there is a low-but-finite chance that this won't be the case...

We need to do them one-after-the-other in a `while` loop (rather than the more idiomatic vectorized  approach of building a matrix and checking the rows) since the number of iterations needed to obtain 8 decimal places of accuracy is too big to be contained in an  matrix.
The test link substitutes `1e5` in place of `1e19`, for a lower-accuracy output without timing-out. Feel free to run the high-accuracy version on your own computer if you have the time to wait.

---

# , 83 bytes

```
function(n,k,p,m=cbind(rbind(1-p,diag(k)*p),!k:0))Reduce(`%*%`,rep(list(m),n))[k+1]

```

Try it online!

Port of dancxviii's Markov method \- upvote that one - but sadly still longer than pajonk's R answer...

# Answer
> 4 votes
# JavaScript (ES7), 106 bytes

Quickly computes the probability, using the formula found by Kevin Cruijssen.

```
(n,k,p,q=1-p)=>(g=s=>(x=n-(y=j*k))<0?0:s*(p-~x/j*q)*(h=k=>--k?h(k)*(x-k+1)/k:p**y*q**~-j++)(j)+g(-s))(j=1)

```

Try it online!

---

# JavaScript (ES12), 58 bytes

Using loopy walt's recursive formula is much shorter and much slower. This version uses a cache to speed it up (-7 bytes without the cache).

Expects `(k)(p)(n)`.

```
k=>p=>g=n=>g[n]||=n>=k&&p**k*(1-p*(n>k))*(1-g(--n-k))+g(n)
//         \_____/
//          cache
```

Attempt This Online!

# Answer
> 4 votes
# Vyxal , 23 bytes

```
2$ÞẊ'2€vLG›¹>;⁰⌐⁰"$İvΠ∑

```

Try it Online!

Port of Jelly. Really slow.

Previous answer (much faster):

# Vyxal , 41 bytes

```
ḭɾ:£›u$e¹¥□h*-:›¥/⁰⌐*⁰+$¥‹ƈ?¥?*e⁰⌐¥‹eWƒ*∑

```

Try it Online!

Port of 05AB1E.

# Answer
> 4 votes
# PARI/GP, 53 bytes

```
k->p->g(n)=if(n>=k,p^k*(1-p*(n>k))*(1-g(n---k))+g(n))
```

Attempt This Online!

A port of loopy walt's Python answer. Takes input in the the form `(k)(p)(n)`

---

# PARI/GP, 56 bytes

```
f(n,k,p)=Pol((1-y=p*x)/(t=1-x)/(t/y^k+x-y)+O(x^n*x))\x^n
```

Attempt This Online!

The generation function of the sequence (for given \\$p, k\\$) is \\$\frac{p^k\ x^k\ (1-p\ x)}{(1-x)(1-x+(1-p)\ p^k\ x^{k+1})}\\$.

---

This generation function can be derived from loopy walt's recurrence formula:

\\$f(n,k,p)=f(n-1,k,p)+p^k(1-p)(1-f(n-k-1,k,p))\\$.

This recurrence formula is valid when \\$n\>k\\$. In addition, when \\$n=k\\$, we have \\$f(n,k,p)=p^k\\$ when \\$n=k\\$, and \\$f(n,k,p)=0\\$ when \\$n\<k\\$.

Let \\$F(k,p)\\$ be the generation function (for given \\$p, k\\$), we have

\\$\begin{align} F(k,p) &= \sum\_{n=0}^{\infty}f(n,k,p)\ x^n \\ &= p^k\ x^k+\sum\_{n=k+1}^{\infty}f(n,k,p)\ x^n \\ &= p^k\ x^k+\sum\_{n=k+1}^{\infty}(f(n-1,k,p)+p^k(1-p)(1-f(n-k-1,k,p)))\ x^n \\ &= p^k\ x^k+\sum\_{n=k+1}^{\infty}f(n-1,k,p)\ x^n+p^k(1-p)\sum\_{n=k+1}^{\infty}(x^n-f(n-k-1,k,p)x^n) \\ &= p^k\ x^k+x\sum\_{n=0}^{\infty}f(n,k,p)\ x^n+p^k(1-p)\sum\_{n=0}^{\infty}(x^{n+k+1}-f(n,k,p)x^{n+k+1}) \\ &= p^k\ x^k+x\ F(k,p)+p^k(1-p)(\frac{x^{k+1}}{1-x}-x^{k+1}F(k,p)) \end{align}\\$.

Solving this equation, we have \\$F(k,p)=\frac{p^k\ x^k(1-p\ x)}{(1-x)(1-x+(1-p)\ p^k\ x^{k+1})}\\$.

# Answer
> 3 votes
# PARI-GP, 75 bytes

Port of below solution (can run n ~ 1000000000, k ~ 150)

```
f(n,k,p)=(matrix(k++,k,a,b,(a-1==b)*p+(a<2)*(b<k)*(1-p)+(a+b==k+k))^n)[k,1]

```

# Python (Numpy), 104 bytes

Noone has the markov method yet:

The states are the number of consecutive heads starting at state 0, with the final state as state k. State i (i \< k) goes to state i+1 with probability p and state 0 with probability 1-p. State k always goes to state k. The matrix is:

\\$ \begin{bmatrix} 1 - p & 1 - p & 1 - p & \dots & 1 - p & 0 \\ p & 0 & 0 & \dots & 0 & 0 \\ 0 & p & 0 & \dots & 0 & 0 \\ \dots & \dots & \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \\ 0 & 0 & 0 & \dots & p & 1 \\ \end{bmatrix} \\$

Taking this matrix to the nth power and multiplying it by the vector \\$\left\[1, 0, 0, \dots, 0 \right\]^T \\$ gives the answer.

This solution is not an clean mathematical sum but it is much more computationally efficient then the sum.

```
m=zeros((k+1,k+1))
for i in range(k):
    m[0][i]=1-p
    m[i+1][i]=p
m[k][k]=1
print(matrix_power(m,n)[k][0])

```

# Answer
> 2 votes
# Desmos, 80 bytes

```
P(p,k,n)=∑_{j=1}^{n/k}-(-1)^j(p+(n-jk+1)(1-p)/j)nCr(n-jk,j-1)p^{jk}(1-p)^{j-1}

```

Try it on Desmos or prettified.

Thanks to Kevin Cruijssen for finding this formula.

# Answer
> 2 votes
# Factor \+ `math.combinatorics math.unicode`, 133 bytes

```
[| n k p | n k /i [1,b] [| j | -1 j 1 + ^ n j k * - :> z z 1 + j
/ 1 p - * p + z j 1 - nCk p j k * ^ * 1 p - j 1 - ^ * * * ] map Σ ]

```

Try it online!

Translation of the formula given in Kevin Cruijssen's 05AB1E answer.

# Answer
> 2 votes
# Husk, ~~30~~ ~~19~~ 17 bytes

```
ṁoΠm≠²fö≥⁰▲mΣgπḋ2

```

Try it online!

Port of my R answer.
Input is arg1=p, arg2=k, arg3=n.

```
                πḋ2     # cartesian arg-3-th power of binary digits of 2
                        # so: all possible combinations of n heads/tails;
        fö              # now consider only those with runs: filter by
            ▲           # the maximum of
             mΣg        # the sums of each group of identical elements
          ≥⁰            # is greater than or equal to arg-2;
                        # now convert the 1s & 0s to probabilities:
   mo -²                # subtract the probability of heads from each
     a                  # and get the absolute values
                        # so 1s become (1-p) and 0s become p;
ṁo                      # finally map across each group & sum the result
  Π                     # product of the probabilities

```

# Answer
> 2 votes
# Charcoal, 35 bytes

```
ＮθＮηＮζＩΣＥΦＥＸ²θ⍘ι²№ι×1η×ＸζΣιＸ⁻¹ζ⁻θΣι

```

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

```
ＮθＮηＮζ

```

Input `n`, `k` and `p`.

```
ＥＸ²θ⍘ι²

```

Get all of the binary numbers up to `2ⁿ`.

```
Φ...№ι×1η

```

Keep only those with `k` consecutive heads, I mean `1`s.

```
Ｅ...×ＸζΣιＸ⁻¹ζ⁻θΣι

```

Compute their probabilities, which is `pⁱ(1-p)ⁿ⁻ⁱ`, where `i` is the number of `1`s in each relevant row.

```
ＩΣ...

```

Output the grand total.

A 40-byte port of @dancxviii's approach is much more efficient:

```
Ｎθ≔Ｅ⊕Ｎ¬ιηＦＮ«≔⊟ηζ≔⁺⟦×Ση⁻¹θ⟧×ηθη⊞η⁺ζ⊟η»Ｉ⊟η

```

Try it online! Link is to verbose version of code. Takes inputs in the order `p`, `k`, `n`. Expects `k>1` (+1 byte to support `k=1`). Explanation:

```
Ｎθ

```

Input `p`.

```
≔Ｅ⊕Ｎ¬ιη

```

Create an array of `1` `1` and `k` `0`s.

```
ＦＮ«

```

Repeat `n` times.

```
≔⊟ηζ

```

Remove the last entry of the array.

```
≔⁺⟦×Ση⁻¹θ⟧×ηθη

```

Multiply the array by `p`, then prefix the sum of the array multiplied by `1-p`.

```
⊞η⁺ζ⊟η

```

Add the previous last entry to the current last entry.

```
»Ｉ⊟η

```

Output the last entry in the array.

I had been planning on working out how to solve the problem using dynamic programming but I'm pretty sure it would have resulted in the same algorithm.

# Answer
> 2 votes
# , 70 bytes

```
`[`=function(k,n,p)`if`(n<k,0,(1-p*(n>k))*(1-k[n-k-1,p])*p^k+k[n-1,p])

```

Try it online!

Port of @loopy walt's Python answer.

For different approaches in  see @Dominic van Essen's answer.

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

```
kpIf[#>=k,(1-Boole[#>k]p)(1-#0[#-k-1])p^k+#0[#-1],0]&

```

Try it online!

Port of Python. Takes `f(k)(p)(n)`.

# Answer
> 0 votes
# , 49 bytes

```
1 :'0{_1{[:+/ .*^:(u-1)~(1,~]#0:),.~(*=@i.),~1-['

```

Try it online!

Almost identical to dancxviii's Markov chain approach.

---
Tags: code-golf, math, probability-theory
---


title: Collect data on mushroom forests

text:
# Question
Title: Collect data on mushroom forests
In these previous challenges\[1\]\[2\] I've been dealing with "mushroom forests". To help with these I draw little diagrams of the forests to help. In this challenge we are going to reverse engineer the data from these diagrams.

To recap *ha!* mushroom forests are a list of pairs of non-negative integers. Each pair represents a mushroom whose center is at that horizontal coordinate. The only part of the mushroom we care about is the cap (the flat bit at the top).

The first integer in each pair represents which row the cap is placed in. i.e. the height of the mushroom.

The second integer represents the radius of the cap. If it's zero then there just isn't a mushroom in that position. Other for size \\$n\\$ a total of \\$2n-1\\$ spaces are occupied centered at the index of the pair. For example `1` means that its cap only occupies a space above it, a `2` means it occupies a space above it and the spaces one unit to the left and right.

To draw the data I represent rows using lines of text separated by newlines. There are twice as many lines as there are rows with the even rows being used for spacing. I draw the caps using the `=` and I only draw caps on *odd* numbered lines. If a mushroom cap is present at coordinate \\$(x,y)\\$ I draw an `=` at \\$(2x,2y+1)\\$. Here's an example:

```
                  =

= = = = = = = = = = = = = = = = =

          = = = = =

          = = =       =

          [ 2,3,9,1,0,1 ] <- Widths
          [ 0,1,2,3,2,1 ] <- Heights

```

Then between `=`s of the same height I add an extra `=` if they belong to the same mushroom.

```
                  =

=================================

          =========

          =====       =

          [ 2,3,9,1,0,1 ] <- Widths
          [ 0,1,2,3,2,1 ] <- Heights

```

Then I draw stalks extending from the bottom row up to the cap the correspond to. If there's already a `=` in a space I leave it alone. I don't draw any stalks for mushrooms with width `0`.

```
                  =
                  |
=================================
                | |
          =========
              | | |
          ===== | |   =
            | | | |   |
          [ 2,3,9,1,0,1 ] <- Widths
          [ 0,1,2,3,2,1 ] <- Heights

```

## Task

Your task is to take as input a string of an ascii diagram as described above and output the list of widths used to draw that diagram. We don't care about the heights at all.

You may output trailing and leading zeros in your result, as they don't change the diagram. You may also assume that the input is padded to a perfect rectangle enclosing the bounding box of the art. You may assume that there is always a valid solution to the input and you do not have to handle malformed input.

This is so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

Test cases are provided with all leading and trailing zeros trimmed in the output, however the output is aligned to the input for clarity.

```
                  =
                  |
=================================
                | |
          =========
              | | |
          ===== | |   =
            | | | |   |
           [2,3,9,1,0,1]

  = =
  | |
 [1,1]

=====     =====
  |         |
 [2,0,0,0,0,2]

===== ============= =
  |         |       |
  | =====   |   =====
  |   |     |     | |
  =====     =========
  | | |     |   | | |
 [2,2,2,0,0,4,0,3,2,1]

  ===== =
    |   |
===== =========
  | |   | |
 [2,2,0,1,3]

    =============
          |
  =============
        | |
    ===== |
      | | |
    = | | |
    | | | |
===== | | |
  | | | | |
 [2,1,2,4,4]

```

# Answer
> 6 votes
# Python, 125 bytes

```
import re
def f(s):
 o=[0]*len(s[0])
 for l in s:
  for m in re.finditer("=+",l):o[sum(m.span())//4]=len(m[0])//4+1
 return o
```

Attempt This Online!

Bad, terrible, no good.

Need variable-length lookbehind.

# Answer
> 4 votes
# Jelly, ~~23~~ ~~20~~ 16 bytes

```
OḂŒgÄ=U×ƊF€Sm2HĊ

```

Try it online!

*-3 thanks to Jonathan Allan, also opening up another -1 (`×=¥UFƊ€` -\> `=U×ƊF€`)*

```
    Ä   Ɗ           Consider the cumulative sums of
  Œg                the runs in each row of
OḂ                  whether or not each character is an equals sign
 Ḃ                  (ones bit of
O                   the codepoints).
     =              For each element of each cumsummed run, is it equal to
      U             the corresponding element of the run backwards?
       ×            Multiply it by the result.
         F€         Flatten each row,
           S        Sum each column,
            m2      remove alternating elements,
              H     halve,
               Ċ    and ceiling.

```

# Answer
> 3 votes
# Retina, 39 bytes

```
^
¶
(=*)=\1
$1!$1
{*.\Cm`^!|\G==
m`^..

```

Try it online!

## Explanation

`^`, : Add a line feed at the start of the string.

`(=*)=\1`, `$1!$1`: Match each mushroom, and change the centre character to a `!`.

`{`: Repeat until no change:

* `*.\Cm`^!|\G==`:
    + `C`: Count matches of `^!|\G==`: `!` at the start of a line (`m` makes `^` match the start of each line), or `==` immediately after the previous match (`\G`). This gives the size of a half-mushroom with its centre at the start of a line, if there is one, or 0 if there is none.
    (The added empty line at the start of the string makes sure `\G==` does not match at the start of the string.)
    + `\`: Output the result of the above.
    + `*`: Do not change the working string. (According to the documentation, this should not be necessary as "output stages are purely used for their side effect and will never affect the working string themselves", but that doesn't seem to be what actually happens?)
    + `.`: Disable implicit output.
* `m`^..` (with an empty second source): Remove the first two characters of each line. (This is implicitly a Replace stage.)

# Answer
> 2 votes
# 05AB1E, 21 bytes

```
'=QεγεƶÐÅsQ*}˜}øOιн;î

```

Port of *@UnrelatedString*'s Jelly answer, since it's shorter than any monstrosity I was attempting..

Input as a (right-padded) matrix of characters. Output as a list of doubles with leading/trailing 0s.

Try it online or verify all test cases. (Footer `0Úï` is to pretty-print the output; feel free to remove it to see the actual output.)

**Explanation:**

```
'=Q         '# Check for each character in the (implicit) input-matrix if it's a "="
   ε         # Map over each row of 0s/1s:
    γ        #  Split it into groups of adjacent equal elements
     ε       #  Inner map over each group:
      ƶ      #   Multiply each value by its 1-based index
       Ð     #   Triplicate this list
        Ås   #   Pop one, and push the middle item
          Q  #   Pop another, and check which values are equal to this middle
           * #   Multiply each at the same positions to the remaining list
     }˜      #  After the inner map: flatten the list of groups
   }ø        # After the outer map: zip/transpose; swapping rows/columns
     O       # Sum each inner list (the columns)
      ι      # Uninterleave it into two parts
       н     # Pop and only leave the first part
        ;    # Halve each value
         î   # Ceil each value
             # (after which the result is output implicitly)

```

`ÐÅmQ*` could alternatively be `Z>;Qƶ` for the same byte-count:

```
       Z     #   Push the maximum (without popping the list)
        >    #   Increase it by 1
         ;   #   Halve it
          Q  #   Check which values are equal to this middle
           ƶ #   Multiply each value by its 1-based index

```

# Answer
> 2 votes
# Haskell, ~~161~~ 160 bytes

*-1 bytes thanks to @Unrelated String*

```
p[]=[]
p(x:y:z)=map(`div`4)[y-x+3,x+y]:p z
m=map(=='=')
f a=[sum[w|[w,x]<-concat[p[j|(j,x,y)<-zip3[0..](m$' ':b)$m$b++" ",x/=y]|b<-a],x==y]|y<-[1..length$a!!0]]
```

Attempt This Online!

# Answer
> 1 votes
# Vyxal, 18 bytes

```
C∷ƛĠv¦ƛṘ=*;f;∑y_½⌈

```

Try it Online!

Port of Jelly.

# Answer
> 0 votes
# Charcoal, 36 bytes

```
ＷＳ⊞υιＩΦＥＥθ⌕⭆υ§λκ=|∧⊕ι⊕⊘Ｌ⊟⪪…§υικ ¬﹪κ²

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

```
ＷＳ⊞υι

```

Input the forest.

```
Ｅθ⌕⭆υ§λκ=|

```

Find the first positions of all of the substrings `=|` in the columns, if any.

```
Ｅ...∧⊕ι⊕⊘Ｌ⊟⪪…§υικ

```

For each column, if the substring was not found then return `0` otherwise truncate the row containing the mushroom at the column, split on spaces, and take the incremented halved length of the last substring, which will be the row of `=`s to the left of the middle of the mushroom.

```
ＩΦ...¬﹪κ²

```

Output alternate columns, since we're not interested in the other columns.

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


title: Draw the Archimedean Spiral

text:
# Question
Title: Draw the Archimedean Spiral
## Overview

I was playing with Desmos and discovered a really cool spiral:

Doing some research, I discovered that this spiral was the Archimedian spiral. Every point on the spiral is exactly \\$\theta\\$ away from the origin, where \\$\theta\\$ is the angle from the origin. That is, any point on the spiral has the polar coordinates \\$(\theta, \theta)\\$. This also has the consequence that the shortest distance between 2 arms of the spiral is exactly \\$2\pi\\$ if using radians or \\$360\\$ if using degrees.

## The Challenge

The basic spiral can be defined by the following formula in the polar coordinate system: $$ r = a\theta $$ Where \\$a\\$ is the multiplier of the distance between the arms. Your job is, given a floating point input for \\$a\\$, draw this spiral with *at least one* full rotation. You may output the image according to any image I/O defaults.

## Scoring

This is , shortest answer in bytes wins.

# Answer
> 10 votes
# Minecraft Command Blocks, 599 bytes

## Commands

Left column (bottom block 0, 4, -2)

```
scoreboard objectives add c dummy
scoreboard players set m c 1
summon armor_stand 0 0 0
setblock 0 3 0 redstone_block

```

Middle column (bottom block 0, 4, 0)

```
execute at @e[type=armor_stand] run setblock ~ ~ ~ stone
tp @e[type=armor_stand] 0 0 0
execute as @e[type=armor_stand] at @s run tp @s ~ ~ ~ ~5 ~
scoreboard players reset d
scoreboard players add m c 1
setblock 0 3 1 air
setblock 0 3 1 redstone_block

```

Right column (bottom block 0, 4, 1)

```
execute as @e[type=armor_stand] at @s run tp @s ^ ^ ^<Input>
scoreboard players add d c 1
setblock 0 3 1 air
setblock 0 3 0 air
execute unless score d c = m c run setblock 0 3 1 redstone_block
execute if score d c = m c run setblock 0 3 0 redstone_block

```

The distance multiplier is set in the first command block in the right column. Hardcoding inputs is not allowed by codegolf rules, but there isn't any other way to take input in Minecraft.

When ran for an hour with an input of 0.1 it produced this. It starts skipping blocks after a little over one rotation but it does complete one full rotation.

# Answer
> 7 votes
# Desmos, 14 bytes

```
r=\ans_1\theta

```

Well...

Try it on Desmos!

# Answer
> 5 votes
# GFA-Basic 3.51 (Atari ST), 68 bytes

A manually edited listing in .LST format. All lines end with `CR`, including the last one.

```
PRO d(a)
F t=0TO 251
PL 160+t*COS(t/20)*a,100-t*SIN(t/20)*a
N t
RET

```

which expands to:

```
PROCEDURE d(a)
  FOR t=0 TO 251
    PLOT 160+t*COS(t/20)*a,100-t*SIN(t/20)*a
  NEXT t
RETURN

```

NB: We use \\$251\\$ as the upper bound so that the curve stops on the x-axis rather than at some random position (because \\$251/20\approx 4\pi\\$).

### Example output

# Answer
> 4 votes
# Wolfram Language (Mathematica), 22 bytes

```
PolarPlot[y#,{y,0,7}]&

```

Try it online!

I picked 7 for the plot range because it's a one-digit number that is close to \\$2\pi\\$ (so we get just around 1 rotation, slightly more).

Example result for input = 1:

Example when we replace 7 with 50 (makes it more accurate to the image in the original post, but is one byte longer):

# Answer
> 4 votes
# , 28 bytes

```
plot@(**r.@o.@])(%~8*i.)@1e5

```

Try it online!

a=1

a=2

# Answer
> 3 votes
# , 49 bytes

```
function(a)plot(cos(t<-0:9e3/1e3)*t*a,sin(t)*t*a)

```

Try it on rdrr.io!

# Answer
> 3 votes
# MATL, 13 bytes

```
9W:9/tJ*Ze*XG

```

Try it at MATL online!

### Explanation

```
9W    % Push 9. 2 raised to that. Gives 512
:     % Range. Gives [1 2 ... 512]
9/    % Divide each entry by 9
t     % Duplicate
J*    % Multiply each entry by imaginary unit
Ze    % Exponential of each entry
*     % Multiply each pair of entries
XG    % Plot

```

# Answer
> 3 votes
# BQN, 50 bytesSBCS

```
(•math.Sin•Plot○(⊢×↕∘≠)•math.Cos)-2×π×999⥊99÷˜↕100

```

Run online!

The JS version of BQN has a plotting builtin, which I used for the same rosetta code task. This is just a golf of that.

# Answer
> 2 votes
# Excel & VBA, 144 bytes

```
Cell B1 = SEQUENCE(90)/9*PI()
Cell C1 = B1#*COS(B1#)*A1
Cell D1 = B1#*SIN(B1#)*A1
VBA Immediate Window Set x=activesheet.Shapes.AddChart2(,73,,,,360):x.Chart.SetSourceData Source:=Range("C1:D96")

```

Could cut the `,,,,360` if the plot doesn't have to be square.

# Answer
> 2 votes
# SageMath, ~~69~~ 68 bytes

```
lambda a,t=var('t'):parametric_plot((a*t*cos(t),a*t*sin(t)),(t,0,9))

```

Try it online!

*Saved a byte thanks to Seggan!!!*

### Original graph using 42 instead of 9

# Answer
> 2 votes
## SVG(HTML5) + JavaScript (ES6), ~~77~~ 76 + 96 = 172 bytes

```
f=a=>s.setAttribute("points",[...Array(9e3)].map((_,i)=>[Math.sin(i/=100)*i*a,Math.cos(i)*i*a]))
;f(.1)
```

```
<input value=.1 oninput=f(+value)><br>
<svg viewBox=-4,-4,8,8><polyline id=s fill=none stroke=red stroke-width=.05>
```

Edit: Saved 1 byte thanks to @Kaiido.

# Answer
> 2 votes
# , 42 bytes\*

```
function(a,x=0:6e3/1e3)plot(a*x*pi*1i^x/2)

```

Try it at rdrr.io

Calculates the the points of the spiral as the real and imaginary parts of complex numbers, which is conveniently displayed directly as points on the complex plane by the  `plot` function.

\*The `*pi`...`/2` bit here is to scale the image so that the angle is in *radians* and achieve a distance between arms of exactly `2*pi`. If we use an alternative unit of angular measurement, such as *quadrants*, we could drop this for 37 bytes: `function(a,x=0:6e3/1e3)plot(a*x*1i^x)`.

Note also that the choice of `1e3` plotted points per quadrant was chosen to allow direct competition with pajonk's R answer; however, `99` plotted points per quadrant also gives a satisfactory output (the points overlap) and saves another byte: `function(a,x=0:999/99)plot(a*x*1i^x)`.

---

# \+ pracma library, 39 bytes

```
function(a)pracma::polar(r<-0:99/9,a*r)

```

Try it at rdrr.io

Using a dedicated `polar` function doesn't save much, if anything at all.

# Answer
> 1 votes
## Applesoft BASIC, 73 bytes

```
0GR
1COLOR=7
2INPUTR
3I=0
4PLOTCOS(I)*I*R+20,SIN(I)*I*R+20
5I=I+.1
6GOTO4

```

# Answer
> 1 votes
**Clojure, 344 bytes**

```
(defn s[a](doto(JFrame."")(.setPreferredSize(Dimension. 500 500))(.add(doto(proxy[JPanel][](paintComponent[g](.drawPolyline g (into-array Integer/TYPE(map #(+ 250(* a(/ % 20)(Math/cos(Math/toRadians %))))(range 3600)))(into-array Integer/TYPE(map #(- 250(* a(/ % 20)(Math/sin(Math/toRadians %))))(range 3600)))3600))))).pack(.setVisible true)))

```

**Output for `(s 1)`:**

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


title: Draw the Progress Pride flag

text:
# Question
Title: Draw the Progress Pride flag
## Challenge

Create the image of a progress pride flag.

## Output

## Dimensions

## Rules

* Your program must create the image and not just load it from a website
* The colours can be just your language's default if it is very difficult / impossible to load RGB values, else they should be: `red: (255,0,0)`, `orange: (255,140,0)`, `yellow: (255,240,0)`, `green: (0,138,40)`, `(dark) blue: (0,80,255)`, `purple: (120,0,140)`, `black: (0,0,0)`, `brown: (100,50,20)`, `(light) blue: (110,220,240)`, `pink: (255,180,200)`, `white: (255,255,255)`
* The flag can be a scaled up version of the one shown, but the dimensions given are the smallest size allowed. An error of 1 pixel is allowed.
* Please include an image of the output of your program.

This post was (somewhat) inspired by this one.

# Answer
> 5 votes
# C (GCC), ~~192~~ 176 bytes

```
char*r="binary stuff (see ATO)";i,j;main(x){write(1,"P6 1059 672 255 ",16);for(;i<672;++i)for(j=0;j<1059;++j)write(1,r+((x=abs(i-336)+j)<504?6+x/84:i/112)*3,3);}
```

*-16 bytes thanks to @ceilingcat*

Attempt this online! (you must set encoding to Base64)

Outputs a PPM image.

# Answer
> 4 votes
# Java 17, 475 bytes

```
import java.awt.*;v->new Frame(){public void paint(Graphics g){int i=0;for(;i<6;g.fillRect(168,i++*112+25,891,112))g.setColor(new Color(i<3?255:i/5*120,i%5<1?0:i<3?140+i/2*100:i<4?138:80,i<3?0:i<4?40:i<5?255:140));for(i=0;i<4;g.fillPolygon(new int[]{0,0,(i+2)*84,i/3*84,i<1?0:~-i*84,(i+3)*84},new int[]{109-i*84,193-i*84,361,(i<3?6+i:8)*84+25,i++<1?613:697,361},6))g.setColor(new Color(i<1?255:i<2?110:i<3?100:0,i<1?180:i<2?220:i<3?50:0,i<1?200:i<2?240:i<3?20:0));}{show();}}

```

**Explanation:**

*TODO: Will try to golf it some more first.*

# Answer
> 3 votes
# BBC Basic  ~~210~~  190 bytes

Golfing mainly comprises removal of unnecessary whitespace and use of abbreviations for keywords. At one point `VDU25,0` is condensed to a single 16-bit value `V.25;` (the `;` delimiter denotes that the preceding value is a 16-bit value instead of 8-bit.). At another, `VDU25,101` is replaced with the higher level command `PLOT101`

```
MODE27h=672F.i=1TO33j=i MOD3IFj=1V.19,7,16
V.(ASCM."8 < 0S o(SP S< S     4*$6LPSDHSSS",i,1)-32)*5MOD257
IFj N.
IFi<19PLOT101,i MOD2*1782+336;h*i/9ELSEV.25;h;-h;25,81,-h;-h;25,97,-168;h*2;
N.

```

Download interpreter at https://www.bbcbasic.co.uk/bbcwin/download.html

This interpreter has certain features not included in the original BBC basic. It allows for larger screen modes and more colours. `MODE 27` is 1280x960 pixels but the coordinate system is double that at 2560x1920.

The original BBC basic had (depending in screen mode) a maximum of 16 logical colours displayed at one time (to save memory) but there was facility to change these colours to any 18-bit physical colour using `VDU19`. This would instantaneously change the colour of all pixels of that colour on the screen (which was useful for fast animation.) This interpreter works differently. On execution of a `VDU19` colours of existing pixels do not change, only newly drawn ones, and full 24-bit colour is supported.

Selecting the colour is a major part of this code, with 33 different RGB values. Most of them are divisible by 5, so I compressed them into printable ASCII by dividing by 5 and adding 32. The one exception is `138` for the green, which is taken as a larger number mod `257`

Stripes are drawn using absolute coordinates with `x=1059*2=2118` at the right and `x=168*2=336` at the left. This leaves the graphics cursor in the correct position at the top right of the black chevron. `19VDU25,101,i MOD2*1782+336` causes the graphics cursor to zigzag from the default location in the bottom left corner of the screen to the top left corner of the red bar. The code 101 is for a rectangle defined by its opposite corners.

Chevrons are drawn using relative coordinates as a house-shape rotated 90 degrees, comprising a triangle and a rectangle. Subsequent chevrons overdraw the house shape to produce the correct chevron shape.

The graphics cursor is already at top right from the previous operation. It moves diagonally to the centre right point `VDU25,0,h;-h;`, then a triangle is drawn linking the last two positions of the graphics cursor to the bottom right `VDU25,81,-h;-h;`. The shape is completed by drawing a rectangle to the top left `VDU25,97,-168;h*2;` which leaves the cursor in the correct position for the next chevron.

After the brown chevron, certain parts of the final three chevrons are off the left side of the screen and are therefore not plotted.

**First working version**

```
MODE27
h=672
FORi=1TO33
j=i MOD3
IFj=1VDU19,7,16
VDU(ASCMID$("8 < 0S o(SP S< S     4*$6LPSDHSSS",i,1)-32)*5MOD257
IFj NEXT
IFi<19VDU25,101,i MOD2*1782+336;i/9*h;ELSEVDU25,0,h;-h;25,81,-h;-h;25,97,-168;h*2;
NEXT

```

**Commented Code**

```
MODE27                         :REM select screen mode with 2560x920 logical coordinates, 1280x960 pixels
h=672                          :REM half the logical height of the flag
FORi=1TO33                     :REM iterate R,G,B through 11 colours
j=i MOD3                       :REM if i MOD 3 = 1 tell VDU controller to expect a redefiniton of default logical colour 7
IFj=1VDU19,7,16                :REM (below) extract R,G or B value from 1-indexed string, send to VDU controller
VDU(ASCMID$("8 < 0S o(SP S< S     4*$6LPSDHSSS",i,1)-32)*5MOD257
IFj NEXT                       :REM if i MOD 3 is not 0 draw nothing yet
IFi<19VDU25,101,i MOD2*1782+336;i/9*h;ELSEVDU25,0,h;-h;25,81,-h;-h;25,97,-168;h*2;
NEXT                           :REM (above) if i MOD 3 = 0 draw a bar if i<19, otherwise draw a chevron.

```

# Answer
> 2 votes
## PostScript, ~~156~~ ... 115 bytes

```
00000000: 3020 3087 6101 3232 3492 7f28 ffff ffff  0 0.a.224..(....
00000010: b4c8 6edc f064 3214 0000 00ff 0000 ff8b  ..n..d2.........
00000020: 00ff f000 0089 4800 50ff 7800 8b29 7b32  ......H.P.x..){2
00000030: 3535 9236 7d92 4936 7b92 9d30 2030 8761  55.6}.I6{..0 0.a
00000040: 0133 3892 8030 8870 3392 3692 ad7d 9283  .38..0.p3.6..}..
00000050: 3136 3888 9092 ad31 3335 9288 357b 929d  168....135..5{..
00000060: 3020 3087 e703 9238 9280 8814 3230 92ad  0 0....8....20..
00000070: 7d92 83                                  }..

```

Before tokenization:

```
0 0 353 224 rectclip
<FFFFFFFFB4C86EDCF0643214000000FF0000FF8B00FFF0000089480050FF78008B>{255 div}forall
6{setrgbcolor 0 0 353 38 rectfill 0 112 3 div translate}repeat
168 -112 translate 135 rotate
5{setrgbcolor 0 0 999 dup rectfill 20 20 translate}repeat

```

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


# Question
Title: Print all lexicographically increasing numbers under 10000
A lexicographically increasing number is an integer whose digits are in strictly increasing order. Print all lexicographically increasing numbers under 10000.

Here are lines of the expected output:

```
0
1
2
3
4
5
6
7
8
9
12
13
14
15
16
17
18
19
23
24
25
26
27
28
29
34
35
36
37
38
39
45
46
47
48
49
56
57
58
59
67
68
69
78
79
89
123
124
125
126
127
128
129
134
135
136
137
138
139
145
146
147
148
149
156
157
158
159
167
168
169
178
179
189
234
235
236
237
238
239
245
246
247
248
249
256
257
258
259
267
268
269
278
279
289
345
346
347
348
349
356
357
358
359
367
368
369
378
379
389
456
457
458
459
467
468
469
478
479
489
567
568
569
578
579
589
678
679
689
789
1234
1235
1236
1237
1238
1239
1245
1246
1247
1248
1249
1256
1257
1258
1259
1267
1268
1269
1278
1279
1289
1345
1346
1347
1348
1349
1356
1357
1358
1359
1367
1368
1369
1378
1379
1389
1456
1457
1458
1459
1467
1468
1469
1478
1479
1489
1567
1568
1569
1578
1579
1589
1678
1679
1689
1789
2345
2346
2347
2348
2349
2356
2357
2358
2359
2367
2368
2369
2378
2379
2389
2456
2457
2458
2459
2467
2468
2469
2478
2479
2489
2567
2568
2569
2578
2579
2589
2678
2679
2689
2789
3456
3457
3458
3459
3467
3468
3469
3478
3479
3489
3567
3568
3569
3578
3579
3589
3678
3679
3689
3789
4567
4568
4569
4578
4579
4589
4678
4679
4689
4789
5678
5679
5689
5789
6789

```

This is a code golf challenge! Shortest answer wins!

(P.S. looking for a python solution)

# Answer
> 32 votes
# Python 2, 56 bytes

```
for n in range(9999):
 if eval('<'.join(`n`))**n:print n

```

Try it online!

Converts each number like `124` to an expression `1<2<4` and evaluates it to check if the digits are sorted,

A hiccup happens for one-digit numbers giving an expression that just is the number itself. This causes `0` to evaluate to a Falsey value even though it should be printed. This is fixed by a trick suggested by Erik the Outgolfer of doing `**n`, which gives truthy value `0**0` for `n=0` and doesn't affect the truth value otherwise.

# Answer
> 14 votes
# Python 2, 55 bytes

```
i=0
exec"print i\ni+=1\nif eval('<'.join(`i`)):1;"*7000

```

Try it online!

# Answer
> 11 votes
# Haskell, 50 bytes

```
unlines[s|s<-show<$>[0..6^5],s==scanl1(max.succ)s]

```

Try it online!

Outputs a multiline string. We check that the number `s` increasing using `s==scanl1(max.succ)s`, a variant of the usual sortedness check `s==scanl1 max s` that ensures strict sortedness by incrementing each digit character before taking the maximum of it and the next digit.

Ourous saved a byte by using `6^5` as the upper bound in place of a 4-digit number.

# Answer
> 9 votes
# Jelly, 7 bytes

```
9ŒPḌḣ⁹Y

```

Try it online!

### How it works

```
9ŒPḌḣ⁹Y  Main link. No arguments.

9        Set the return value to 9.
 ŒP      Powerset; promote 9 to [1, ..., 9] and generate all subsets.
   Ḍ     Undecimal; map the subsets of digits to the integers they represent.
     ⁹   Yield 256.
    ḣ    Dyadic head; take the first 256 elements of the integer list.
      Y  Separate the result by linefeeds.

```

# Answer
> 8 votes
# Japt `-R`, ~~12~~ ~~11~~ 8 bytes

```
L²Ç¶ìüÃð

```

Test it

```
L            :100
 ²           :Squared
  Ç          :Map the range [0,L²)
    ì        :  Split to a digit array
     ü       :  For the sake of simplicity*, let's say: Sort & deduplicate
             :  Implicitly rejoin to an integer
   ¶         :  Test for equality with original number
      Ã      :End map
       ð     :Get 0-based indices of truthy elements
             :Implicitly join with newlines and output

```

\*Or, to offer a better explanation: the `ü` method sorts an array and splits it into equal elements (e.g., `[8,4,8,4].ü() -> [[4,4],[8,8]]`) and then, in what seems to be a strange quirk and hopefully not a bug, the `ì` method, when converting the array back to a number, takes the first element of each nested array, rather than first flattening the array, which is what I expected when I tried this trick (e.g., `[[4,4],[8,8]].ì() -> 48`).

# Answer
> 6 votes
# , ~~62~~ 49 bytes

```
`[`=write;0[1];for(i in 1:4)combn(1:9,i)[1,i,,""]

```

Try it online!

Because `combn` iterates through its input in the order given, it's easy to create all the lexicographically increasing integers, printing them out in order. `write` prints them each `i`-digit number in lines of width `i`, neatly fulfilling the newline requirement as well.

# Answer
> 6 votes
# Perl 6, 25 bytes

```
[<](.comb)&&.say for ^1e4

```

*-1 byte thanks to nwellnhof*

Try it online!

`.comb` produces a list of the digits of each number, and `[<]` does a less-than reduction on that list, equivalent to: *digit1* \< *digit2* \< ... \< *digitN*.

# Answer
> 5 votes
# PowerShell, ~~42~~ 40 bytes

```
0..1e4|?{-join("$_"|% t*y|sort -u)-eq$_}

```

Try it online!

Loop from `0` to `1e4` (i.e., `10000`). Pull out those objects where `|?{...}` the number as a string `$_` is `-eq`ual to the number cast `t`oCharArra`y` and then `sort`ed with the `-u`nique flag. In other words, only numbers that are the same as their sorted and deduplicated strings. Each of those are left on the pipeline and output is implicit.

# Answer
> 5 votes
## Haskell, ~~56~~ 55 bytes

Edit: -1 byte thanks to @Ourous

```
mapM print$filter(and.(zipWith(<)<*>tail).show)[0..6^5]

```

Try it online!

# Answer
> 4 votes
# Pyth, 10 bytes

```
jiRThc2yS9

```

Try it online!

### How it works

```
jiRThc2yS9
        S9  Yield [1, 2, 3, 4, 5, 6, 7, 8, 9].
       y    Take all 512 subsets.
     c2     Split the array of subsets into 2 pieces (256 subsets each).
    h       Head; take the first piece.
 iRT        Convert each subset from base 10 to integer.
j           Separate by newlines.

```

# Answer
> 3 votes
# Common Lisp, ~~74~~ 72 bytes

```
(dotimes(i 7e3)(format(apply'char<(coerce(format()"~d"i)'list))"~d~%"i))

```

Try it online!

-2 bytes thank to @Shaggy!

# Answer
> 3 votes
# J, 26 bytes

```
,.(#~(-:/:~@~.)@":"0)i.1e4

```

Try it online!

## explanation

```
,. (#~ (-: /:~@~.)@":"0) i.1e4
                         i.1e4  NB. list 0 to 9999
                     "0         NB. for each number in the input list
                  @":"0         NB. convert it to a string and
   (#~ (         )              NB. remove any not passing this test:
        -:                      NB. the string of digits matches
              @~.               NB. the nub of the digits (dups removed)
           /:~                  NB. sorted
,.                              NB. ravel items: take the result of all that
                                NB. and turn it into a big column

```

# Answer
> 3 votes
# Perl 5, 47 bytes

```
map{$_&&s/.(?=(.))/$1-$&/gre=~/0|-/||say}0..1E4

```

Try it online!

Older:

52 bytes

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

```
4°ÝD€êÃ»

```

Try it online!

Works in the new version of 05AB1E as well but is painfully slow for some reason.

### How?

```
4°ÝD€êÃ» – Full program.
4°Ý      – Push [0 ... 10000].
   D€ê   – Push each integer in [0 ... 10000] sorted and deduplicated at the same time.
      Ã» – And join the interection of the two lists by newlines.

```

# Answer
> 3 votes
# Regenerate `-a`, ~~36~~ 34 bytes

```
0|(([2-9])$4{$1/$2}|$3![1-9]()){4}

```

Attempt This Online!

This was directly inspired by the language's creator's answer, but I figured this big optimization building on that idea was worth its own post.

```
    0              # Zero must be matched as a special case, because no other
                   # numbers have a leading '0' digit.
|
    (
        ([2-9])    # \2 = a digit intended to be greater than the previous
                   #      one ($1), but until being validated below, it can
                   #      be any digit in [2-9].
                   # We could actually do ([0-9]) here and it'd generate the
                   # same output, but would run slightly less efficiently.
        $4{$1/$2}  # Repeat a nonexistent group $1/$2 number of times. $1 and $2
                   # are the literal contents of those captures interpreted as
                   # numeric values upon which arithmetic can be done in a
                   # quantifier, which we do here. $1/$2 will evaluate to
                   # zero iff $2 is greater than $1, which is the only thing
                   # that will allow it to match, because if it repeats more
                   # than zero times, it tries to match the nonexistent group
                   # $4 which can't match.
    |
        $3         # If the above fails to match, due to $1 containing the
                   # digit '9', the regex engine will try other matches, even
                   # if they use short-circuiting alternation. So we put a
                   # dummy match here, which can only match on iterations
                   # other than the first one. Once this matches, it will be
                   # the only thing that can match in all subsequent
                   # iterations, because the attempted math "$2-$1-1" will
                   # fail still - now due to $1 no longer being a number (it
                   # will be blank).
    # Short-circuiting alternation - never try the following unless the all of
    # the above failed to match.
    !
        [1-9]      # Match the first digit. This can only happen on the first
                   # iteration, thanks to the short-circuiting alternation.
        ()         # $3 = empty capture - lets subsequent iterations know that
                   #      they are no longer the first iteration
    )              # $1 = whatever digit was matched above, for use by the next
                   #      iteration
    {4}            # Repeat the above loop for exactly 4 iterations. This
                   # allows a variable number of digits, due to the "$3" dummy
                   # alternative.

```

Alternative 34 bytes:

```
0|(([2-9])$3{$1/$2}|{#1}![1-9]){4}

```

Attempt This Online!

It might not be intended that this is possible, but Regenerate allows a quantifier to be preceded by nothing. This is what's happening with `{#1}` \- it's impossible for it to match on the first iteration because `$1` hasn't been captured yet and doesn't have a length. On subsequent iterations, a match of nothing gets repeated one time (the length of `$1`).

# Answer
> 2 votes
# Jelly, ~~13~~ ~~9~~ 8 bytes

*Saved 5 bytes thanks to @Dennis*

```
9œcⱮ4ẎŻY

```

Try it online!

### Explanation

Generates all lexicographically increasing numbers below 10000 by taking the digits \[1...9\] and finding all combinations of length ≤ 4.

```
9œcⱮ4ẎŻY    Main link. Arguments: none
9           Yield 9.
   Ɱ4       For each n in [1...4]:
 œc           Yield the combinations of the range [1...9] of length n.
     Ẏ      Tighten; dump each of the 4 lists generated into the main list.
      Ż     Prepend a 0 to the list.
       Y    Join on newlines.

```

---

# Jelly, ~~11~~ ~~10~~ 9 bytes

*Saved a byte thanks to @EriktheOutgolfer*

```
ȷ4Ḷ<ƝẠ$ƇY

```

Try it online!

### Explanation

Filters through the range, keeping the numbers that are lexicographically increasing.

```
ȷ4Ḷ<ƝẠ$ƇY    Main link. Arguments: none
ȷ4           Yield 10^4 (10000).
  Ḷ          Generate the range [0...10000).
       Ƈ     Filter; yield only the numbers where this link return a truthy value.
      $        Run these two links and yield the result.
    Ɲ            For each pair of items (digits) in the number:
   <               Check whether the left digit is less than the right digit.
     Ạ           All; check that every comparison yielded true.
               This yields whether the digits are strictly increasing.
        Y    Join the filtered list on newlines.

```

# Answer
> 2 votes
# Python 2, ~~64~~ 61 bytes

```
lambda:[x for x in range(9999)if sorted(set(`x`))==list(`x`)]

```

Try it online!

Gets the unique characters of the integer's string representation, sorts them, and compares the result to the original number.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 36 bytes

After I wrote this, it was clarified that each number must be on a new line, so +7 bytes for the `Print/@`.

This method takes advantage of the fact that the `Subsets` function 1) doesn't replicate any digits and 2) sorts the output by set size and set contents. `FromDigits` assembles each list of digits.

-1 byte thanks to @Mr.Xcoder

```
Print/@FromDigits/@Range@9~Subsets~4

```

Try it online!

# Answer
> 2 votes
# Python 2, 61 bytes

```
for i in range(9999):
 if list(`i`)==sorted(set(`i`)):print i

```

Try it online!

# Answer
> 2 votes
# , 41 bytes

```
7000ïÎaÛ
Îy$úúP
Ç^¨ä*©±$/d
ÎãlD
çˆ±/d
HO0

```

Try it online!

Hexdump:

```
00000000: 3730 3030 efce 61db 0ace 7924 fafa 500a  7000..a...y$..P.
00000010: c75e a8e4 2aa9 b124 2f64 0ace e36c 440a  .^..*..$/d...lD.
00000020: e788 b12f 640a 484f 30                   .../d.HO0

```

# Answer
> 2 votes
# Charcoal, 19 bytes

```
ΦＥＸχ⁴Ｉι¬Φι∧μ¬‹§ι⊖μλ

```

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

```
   χ                Predefined variable 10
  Ｘ                 To the power
    ⁴               Literal 4
 Ｅ                  Map over implicit range
      ι             Current value
     Ｉ              Cast to string
Φ                   Filter over strings where
         ι          Current string
        Φ           Filtered over characters
           μ        Character index (is nonzero)
          ∧         And
                 μ  Character index
                ⊖   Decremented
              §     Indexed into
               ι    Current string
            ¬       Is not
             ‹      Less than
                  λ Current character
       ¬            Results in an empty string
                    Implicitly print matches on separate lines

```

# Answer
> 2 votes
# JavaScript REPL, 64 bytes

A bit of pub golf so probably far from optimal.

```
(f=n=>n&&f(n-1)+([...n+``].every(x=>y<(y=x),y=0)?`
`+n:``))(7e3)

```

Try it online

Yes, doing it without an IIFE would be a few bytes shorter but that throws an overflow error when called, which would normally be fine as we can assume infinite memory for the purposes of code golf but, to me, doesn't seem to be in the spirit of KC challenges.

# Answer
> 2 votes
# K (ngn/k) / K (oK), ~~32~~ ~~30~~ 26 bytes

**Solution:**

```
`0:$&&/'1_'>':'" ",'$!9999

```

Try it online!

**Explanation:**

```
`0:$&&/'1_'>':'" ",'$!9999 / the solution
                     !9999 / range 0..9998 (could use !6890)
                    $      / string
               " ",'       / prepend " " to each (lower than "0" in ascii)
            >:'            / greater-than each-previous?
         1_'               / drop first result from each
      &/'                  / max (&) over (/)
    &                      / indices where true
   $                       / convert to string
`0:                        / print to stdout

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), ~~102~~ ~~101~~ ~~73~~ ... 72 bytes

-12 **and** -4 thanks @Dennis!

```
for(var i=0;i<7e3;i++)if((i+"").Aggregate((a,b)=>a<b?b:':')<58)Print(i);

```

Try it online!

Each integer from 0 to 7k tested by first converting it into a string. Leveraging the fact that C# treats strings as character enumerables and LINQ, an aggregate is calculated for each character enumerable as follows:

* compare the accumulated value with the current character
* if the current character is greater than the accumulation, return the current character
* otherwise return `:` which is greater than `9`

If the result of this is less than `:` (ASCII 58), then the number has lexicographically increasing digits.

# Answer
> 2 votes
# C (gcc), ~~97~~ ~~89~~ 81 bytes

Thanks to ceilingcat for -8 bytes.

Another -8 thanks to Dennis

```
g(n){n=!n||n/10%10<n%10&&g(n/10);}f(i){for(i=-1;++i<7e3;g(i)&&printf("%u\n",i));}

```

Try it online!

# Answer
> 2 votes
# Regenerate `-a`, 72 bytes

```
0|([1-9])(([2-9])(){$3-$1-1}(([3-9])(){$6-$3-1}(([4-9])(){$9-$6-1})?)?)?

```

Appropriately, outputs the numbers in lexicographic order. Attempt This Online!

### Explanation

```
0|

```

Match 0, or:

```
([1-9])

```

Match a digit 1 through 9 (capture group 1).

```
(...)?

```

Either stop there, or continue:

```
([2-9])

```

Match a digit 2 through 9 (capture group 3), and:

```
(){$3-$1-1}

```

Match an empty group X times, where X equals the second digit minus the first digit minus 1. If the second digit is not larger than the first digit, this quantity is negative, and using a negative number as a repetition count causes the match to fail. Thus, only matches where the second digit is larger than the first digit are included.

```
(...)?

```

Either stop there, or continue:

```
([3-9])

```

Match a digit 3 through 9 (capture group 6), and:

```
(){$6-$3-1}

```

Match an empty group Y times, where Y equals the third digit minus the second digit minus 1 (ensuring that the third digit is larger than the second digit).

```
(...)?

```

Either stop there, or continue:

```
([4-9])

```

Match a digit 4 through 9 (capture group 9), and:

```
(){$9-$6-1}

```

Match an empty group Z times, where Z equals the fourth digit minus the third digit minus 1 (ensuring that the fourth digit is larger than the third digit).

# Answer
> 1 votes
# Python 2, 63 bytes

```
for i in range(6790):
 if`i`=="".join(sorted(set(`i`))):print i

```

Try it online!

# Answer
> 1 votes
# T-SQL, ~~188~~ 185 bytes

```
WITH a AS(SELECT 0n UNION ALL SELECT n+1FROM a WHERE n<9)
SELECT CONCAT(a.n,b.n,c.n,d.n)+0
FROM a,a b,a c,a d
WHERE(a.n<b.n OR a.n+b.n=0)
AND(b.n<c.n OR b.n+c.n=0)
AND(c.n<d.n OR c.n+d.n=0)

```

Line breaks are for readability only.

I'm certain there must be more efficient ways to do this in SQL, but this was the first thing I thought of. Explanation:

1. Declare an in-memory table with values 0 to 9
2. Cross-join 4 copies of this table for all possible values from 0000 to 9999
3. Messy `WHERE` clause to ensure the digits are strictly increasing (or both 0)
4. Smash the digits together (`CONCAT`) and convert to integer (`+0`)
5. The resulting rows may or may not be sorted, but the challenge doesn't appear to require that.

# Answer
> 1 votes
# Stax, 8 bytes

```
¬ ▬A♥¶N∙

```

Run and debug it

# Answer
> 1 votes
# MATLAB, 52 bytes

```
arrayfun(@(n)disp(n(all(diff(num2str(n))>0))),0:1e4)

```

# Answer
> 1 votes
# Clean, 90 bytes

```
import StdEnv
Start=(0,[('
',n)\\n<-[1..6^5]|(\l=removeDup l==sort l)[c\\c<-:toString n]])

```

Try it online!

# Answer
> 1 votes
# Red, 59 bytes

```
repeat n 9999[if(d: n - 1)= do sort unique form d[print d]]

```

Try it online!

# Answer
> 1 votes
# Jelly, 7 bytes

```
<ƝẠ$⁹#Y

```

**Try it online!**

### How?

```
<ƝẠ$⁹#Y - Main Link: no arguments (implicit z=0)
    ⁹   - literal 256
     #  - count up from n=z (0) finding the first 256 for which this is truthy:
   $    -   last two links as a monad:
 Ɲ      -     neighbours (implicitly gets digits of n):
<       -       less than?
  Ạ     -     all truthy? (N.B. yields 1 for an empty list)
      Y - join with newlines

```

# Answer
> 1 votes
# Ruby, 39 bytes

```
puts (?0..?9*4).grep /^#{[*0..9]*??}?$/

```

Try it online!

# Answer
> 1 votes
## JavaScript, 83 bytes

Borrowed some ideas from @Shaggy, but without recursion.

```
[...Array(1e4)].reduce((s,_,n)=>s+=([...n+''].every(x=>y<(y=x),y=0))?'\n'+n:'','0')

```

Try it online!

# Answer
> 1 votes
# MathGolf, 10 bytes

```
♫rgÆ▒_s▀=n

```

Try it online!

## Explanation

```
♫            push 10000
 r           range(0, n)
  g          pop a, (b), pop operator from code, filter
   Æ         start block of length 5
    ▒        split to list of chars/digits
     _       duplicate TOS
      s      sort(array)
       ▀     unique elements of string/list
        =    pop(a, b), push(a==b)
         n   newline char, or map array with newlines

```

# Answer
> 1 votes
# Brachylog, 12 bytes

```
7jj⟦{ẹ<₁cẉ}ˢ

```

Try it online!

```
         ẉ      Write on its own line
    {     }ˢ    every
        c       concatenated
      <₁        strictly increasing
     ẹ          list of digits of
   ⟦            numbers from the range from 0 to
7jj             7777.

```

`7jj⟦{ṫ⊆Ị&ẉ}ˢ` also works.

# Answer
> 1 votes
# Vyxal `jM`, 5 bytes

```
k2'Þ⇧

```

Try it Online!

Flagless:

# Vyxal, 7 bytes

```
k2ʀ~Þ⇧⁋

```

Try it Online!

# Answer
> 1 votes
# Julia, 44 bytes

```
0:6^5 .|>x->issorted("$x",lt=<=)&&println(x)
```

\\$(6^5 = 7776)\\$

Attempt This Online!

# Answer
> 0 votes
# Retina 0.8.2, 38 bytes

```

9999$*
.
$.`¶
.
$*_$&
A`(_*)\d\1\d
_

```

Try it online! Explanation:

```

9999$*

```

Insert 9999 characters.

```
.
$.`¶

```

Convert into a list of numbers 0..9998

```
.
$*_$&

```

Prefix each digit with its value in `_`s.

```
A`(_*)\d\1\d

```

Delete lines containing nonincreasing digits.

```
_

```

Remove the now unnecessary `_`s.

# Answer
> 0 votes
# Pyth, 15 bytes

```
jf.A<V`Tt`TU^T4

```

Try it here!

# Answer
> 0 votes
# Bash + GNU Core Utilities, 57 bytes

```
seq 1e4|grep -vP `seq 0 9|sed 's/./(&[0-&])/'|tr '
' \|`p

```

Uses some meta-regex-generation shit

# Answer
> 0 votes
# K4, 19 bytes

**Solution:**

```
-1@$&&/'>':'$!9999;

```

**Explanation:**

```
-1@$&&/'>':'$!9999; / the solution
             !9999  / range 0..9998
            $       / string
        >':'        / greater-than (>) each-previous (':) each (')
     &/'            / max (&) over (/)
    &               / indices where true
   $                / string
  @                 / apply
-1                ; / print to stdout and swallow return value (-1)

```

# Answer
> 0 votes
# Kotlin, ~~132~~ 131 bytes

Edit: -1 Byte thanks to @Giuseppe

```
fun main(){(0..9999).forEach{it.toString().let{var b=1;it.forEachIndexed{i,c->if(i>0&&it[i-1]<c)b++};if(b==it.length)println(it)}}}

```

Try it online!

# Answer
> 0 votes
# Oracle SQL, 163 bytes

Various ways to generate combinations

```
with a(n)as(select level-1 from dual connect by level<11),r(i,x,s)as(select 1,n,n||''from a union all select i+1,n,s||n from r,a where(x<n or n+x=0)and i<4)select s+0 from r where i=4;

with a(n)as(select level-1 from dual connect by level<11)select a.n||b.n||c.n||d.n+0 from a,a b,a c,a d where(a.n<b.n or a.n+b.n=0)and(b.n<c.n or b.n+c.n=0)and(c.n<d.n or c.n+d.n=0);

with a(n)as(select level from dual connect by level<11)select unique replace(sys_connect_by_path(n-1,'#'),'#')+0 from(a)connect by level<5and prior n<n order by 1;

```
1. Rec with (CTE), 184 bytes
2. Self joins, 182 bytes
3. Connect by, 163 bytes

**Just for fun**

```
with t(c)as(select ku$_vcnt(1,2,3,4,5,6,7,8,9) from dual)
select listagg(value(z)) within group (order by 0) + 0 n
  from (select rownum r, value(r) v
          from t, table(powermultiset(c)) r),
       table(v) z
 where cardinality(v) < 5
group by r union select 0 from dual

```

.

```
with a(n)as(select decode(level,10,null,level) from dual connect by level<11)
select nvl(a.n || b.n || c.n || d.n + 0, 0) n
  from a, a b, a c, a d
 where nvl2(b.n, sign(b.n - a.n), 1) = 1
   and nvl2(c.n, sign(c.n - b.n), 1) = 1
   and nvl2(d.n, sign(d.n - c.n), 1) = 1
 order by 1

```

# Answer
> 0 votes
# PHP, 51 bytes

```
while($n<1e4)count_chars($n,3)-$n++||print~-$n."
";

```

Run with `-nr` or try it online.

---

`count_chars($string,$mode=3)` returns a string of all used characters in ascending order.
This equals the input if, and only if, its characters (in this case: digits) are strictly increasing.

$n is `NULL` in the first iteration; `count_chars` returns an empty string; `NULL-""` is evaluated as `0-0`.

# Answer
> 0 votes
# Tcl, 116 bytes

```
set i 0
time {set m -1;lmap n [split $i ""] {if $n>$m {set m $n} {set m X;break}}
if \$m!="X" {puts $i}
incr i} 9999

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog Extended), 28 bytes

```
{(⍵≡∪⍵)∧⍵≡∧⍵:⎕←⍵⋄⍬}∘⍕¨⍳10000

```

Try it online!

Explanation:

```
{(⍵≡∪⍵)∧⍵≡∧⍵:⎕←⍵⋄⍬}∘⍕¨⍳10000 ⍝ Full program
                          ⍳10000 ⍝ Generate integers from 1 to 10000
                      ∘⍕¨       ⍝ For each number, convert to string and apply left function
         ⍵≡∧⍵                   ⍝ If the string equals itself sorted...
 (⍵≡∪⍵)∧                        ⍝ ...and the string contains only unique elements...
               ⎕←⍵              ⍝ ...print the string to output with trailing newline
                   ⋄⍬            ⍝ Otherwise, do nothing

```

# Answer
> 0 votes
# C++ (gcc), 113 bytes

```
bool y(int a){return(a==0||a%10>(a/=10)%10&&y(a))?true:false;}void z(int i){while(++i<7e3)if(y(i))cout<<i<<endl;}

```

Try it online!

**Pretty Layout:**

```
#include<iostream>
using namespace std;

bool y(int a){
    return(a==0||a%10>(a/=10)%10&&y(a))?true:false;
}

void z(int i){
    while(++i<7e3){
        !y(i)?:cout<<i<<endl;
    }
}

int main(){
    z(-1);
}

```

# Answer
> 0 votes
# Java 8

Full program: 186 bytes

```
interface M{static void main(String[]a){for(int i=-1;i++<9999;System.out.print((i+"").chars().distinct().sorted().mapToObj(c->(c-48)+"").reduce("",(x,y)->x+y).equals(i+"")?i+"\n":""));}}

```

Function: 149 bytes

```
v->{for(int i=-1;i++<9999;System.out.print((i+"").chars().distinct().sorted().mapToObj(c->(c-48)+"").reduce("",(x,y)->x+y).equals(i+"")?i+"\n":""));}

```

# Answer
> 0 votes
# Burlesque, 11 bytes

```
1e4qsoFO:U_

```

Equivalently

```
1e4ro:so:U_

```

Try it online!

```
1e4 # 10000
qso # Boxed is sorted?
FO  # Filter from 1..10000 if sorted
:U_ # Filter for unique digits

```

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


title: Find the capacity of 2D printed objects

text:
# Question
Title: Find the capacity of 2D printed objects
In a fictional 2D world, a set of 2D printing instructions for an object can be represented by a list of integers as follows:

```
1 4 2 1 1 2 5 3 4

```

Each number represents the height of the object at that particular point. The above list translates to the following object when printed:

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

```

We then fill it with as much water as we can, resulting in this:

```
      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

```

We define the *capacity* of the object to be the units of water the object can hold when completely full; in this case, 11.

Strictly speaking, a unit of water (`~`) can exist at a location if and only if it is surrounded by two solid blocks (`#`) in the same row.

## Challenge

Take a list of positive integers as input (in any format), and output the capacity of the object printed when the list is used as instructions.

You can assume the list contains at least one element and all elements are between 1 and 255.

## Test Cases

```
+-----------------+--------+
|      Input      | Output |
+-----------------+--------+
| 1               |      0 |
| 1 3 255 1       |      0 |
| 6 2 1 1 2 6     |     18 |
| 2 1 3 1 5 1 7 1 |      7 |
| 2 1 3 1 7 1 7 1 |      9 |
| 5 2 1 3 1 2 5   |     16 |
| 80 80 67 71     |      4 |
+-----------------+--------+

```

# Answer
## Haskell, 53 bytes

```
f l=sum(zipWith min(scanl1 max l)$scanr1 max l)-sum l

```

*Thanks to Wheat Wizard for saving 1 byte. See also their shorter 48-byte solution.*

The expressions `scanl1 max l` and `scanr1 max l` compute the running maximum of the list reading forwards and backwards, i.e. the profile of the water plus land if water would go flow one direction.

Orig:

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

```

Left:

```
      #~~
 #~~~~#~#
 #~~~~###
 ##~~####
#########

```

Right:

```
~~~~~~#
~#~~~~#~#
~#~~~~###
~##~~####
#########

```

Then, the profile of the overall picture is the minimum of these, which corresponds to where the water does not leak either direction.

Minimum:

```
      #
 #~~~~#~#
 #~~~~###
 ##~~####
#########

```

Finally, the amount of water is the sum of this list, which contains both water and land, minus the sum of the original list, which contains only land.
> 17 votes

# Answer
## Jelly, 10 bytes

```
U»\U«»\S_S

```

While APL requires multiple parentheses, and J two-character symbols, the algorithm is beautiful in Jelly.

```
     »\          Scan maximums left to right
U»\U             Scan maximums right to left
    «            Vectorized minimum
       S_S       Sum, subtract sum of input.

```

Try it here.
> 10 votes

# Answer
# MATL, 14

My Matlab answer translated to MATL. xnor's algorithm.

```
Y>GPY>P2$X<G-s

```

## Explanation

`Y>`: `cummax()` (input is implicitly pushed on the stack)

`G`: push input (again)

`P`: `flip()`

`Y>`: `cummax()`

`P`: `flip()`

`2$X<`: `min([],[])` (two-argument minimum)

`G`: push input (again)

`-`: `-`

`s`: `sum()`
> 4 votes

# Answer
# Haskell, 48 bytes

```
q!u@(x:t)=q-x+maximum u`min`max q x!t
q!_=q

```

```
(0!)

```

Attempt This Online!
> 4 votes

# Answer
## Dyalog APL, 17 bytes

```
+/⊢-⍨⌈\⌊⌽∘(⌈\⌽)

```

This is a monadic train that takes the input array on the right.

The algorithm is pretty much the same as xnor's, although I found it independently. It scans for the maximum in both directions (backwards by reversing the array, scanning, and reversing again), and finds the vectorized minimum of those. Then it subtracts the original array and sums.

The other way to do this would be to split the array at each location, but that's longer.

Try it here.
> 3 votes

# Answer
# Matlab, 47

Also using xnor's algorithm.

```
@(x)sum(min(cummax(x),flip(cummax(flip(x))))-x)

```
> 2 votes

# Answer
## MATLAB, ~~116~~ ~~113~~ ~~109~~ 106 Bytes

```
n=input('');s=0;v=0;l=nnz(n);for i=1:l-1;a=n(i);w=min([s max(n(i+1:l))]);if a<w;v=v+w-a;else s=a;end;end;v

```

This works by storing the high point on the left, and while iterating through each next point, finds the highest point to the right. If the current point is less than both the high points, then it adds the minimum difference to the cumulative volume.

Ungolfed code:

```
inputArray = input('');
leftHighPoint = inputArray(1);
volume = 0;
numPoints = nnz(inputArray);

for i = 1:numPoints-1
    currentPoint = inputArray(i); % Current value
    lowestHigh = min([max(inputArray(i+1:numPoints)) leftHighPoint]);

    if currentPoint < lowestHigh
        volume = volume + lowestHigh - currentPoint;
    else
        leftHighPoint = currentPoint;
    end
end
volume

```

First time I've tried to golf anything, MATLAB doesn't seem the best to do it in....
> 1 votes

# Answer
# Python 2, 68 bytes

```
lambda l:sum(min(max(l[:i+1]),max(l[i:]))-v for i,v in enumerate(l))

```

Try it online!
> 1 votes

# Answer
# Pip `-l`, 19 bytes

```
$+J(ST0XgZD1`0.*0`)

```

Takes input numbers as command-line arguments. Or, add the `-r` flag to take them as lines of stdin: Try it online!

### Explanation

Unlike all the other answers, in Pip it was actually shorter to construct (a modified version of) the ASCII-art and count the water units.

We start with `g`, the list of arguments.

```
[1 4 2 1 5 2 3]

```

`0Xg` produces a list of strings of *n* zeros for each *n* in `g`.

```
[0 0000 00 0 00000 00 000]

```

`ZD1` then zips these strings together, using `1` to fill in any gaps in the resulting rectangular nested list:

```
[[0 0 0 0 0 0 0] [1 0 0 1 0 0 0] [1 0 1 1 0 1 0] [1 0 1 1 0 1 1] [1 1 1 1 0 1 1]]

```

`ST` converts this list to a string. The `-l` flag specifies that lists are formatted as follows: every nested list is joined together without a separator, and at the top level the separator is newline. So we get this multiline string--essentially, the diagram of the object, but upside down:

```
0000000
1001000
1011010
1011011
1111011

```

We then find all matches of the regex ``0.*0``. This matches the two outermost walls and everything between them on each line.

```
[0000000 001000 011010 0110]

```

`J` joins these strings together into one big string, and `$+` sums it, giving the number of `1`s--which is equal to the amount of water the object can hold.

```
6

```
> 1 votes

# Answer
# Rust, 112 bytes

```
|l:&[u8]|{(0..).zip(l).scan(0,|a,(b,c)|{*a=(*a).max(*c);Some((*a).min(*l[b..].iter().max()?)-c)}).sum::<u8>()};

```

Playground Link

Basically `min(max(..index),max(index..)-value`
> 1 votes

# Answer
## ES6, 101 bytes

```
a=>(b=[],a.reduceRight((m,x,i)=>b[i]=m>x?m:x,0),r=m=0,a.map((x,i)=>r+=((m=x>m?x:m)<b[i]?m:b[i])-x),r)

```

Another port of @xnor's alghorithm.
> 0 votes

# Answer
# Vyxal, 11 bytes

```
Ṙɖ∴Ṙ?ɖ∴Þ∵ε∑

```

Try it Online!
> 0 votes

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


title: Reverse odd runs

text:
# Question
Title: Reverse odd runs
Inspiration.

### Task

Reverse runs of odd numbers in a given list of 2 to 215 non-negative integers.

### Examples

`0 1` → `0 1`
`1 3` → `3 1`
`1 2 3` → `1 2 3`
`1 3 2` → `3 1 2`
`10 7 9 6 8 9` → `10 9 7 6 8 9`
`23 12 32 23 25 27` → `23 12 32 27 25 23`
`123 123 345 0 1 9` → `345 123 123 0 9 1`

# Answer
> 8 votes
# Python 2, ~~75~~ ~~68~~ 63 bytes

5 bytes thanks to Dennis.

And I have outgolfed Dennis.

Credits to Byeonggon Lee for the core of the algorithm.

```
o=t=[]
for i in input():o+=~i%2*(t+[i]);t=i%2*([i]+t)
print o+t

```

Ideone it!

Old version: 75 bytes

# Answer
> 6 votes
# APL, ~~21~~ 20 bytes

```
{∊⌽¨⍵⊂⍨e⍲¯1↓0,e←2|⍵}

```

Try it || All test cases

Explanation:

```
                  2|⍵ Select all the odd numbers
                e←    Save that to e
              0,      Append a 0
           ¯1↓        Delete the last element
         e⍲           NAND it with the original list of odd numbers
     ⍵⊂⍨             Partition the list: (even)(even)(odd odd odd)(even)
  ⌽¨                 Reverse each partition
 ∊                    Flatten the list

```

*Edit: Saved a `~` thanks to De Morgan's laws*

# Answer
> 6 votes
# Haskell, ~~46~~ 44 bytes

```
h%p|(l,r)<-span(odd.(h*))p=l++h:r
foldr(%)[]

```

Thanks to @xnor for recognizing a fold and saving two bytes.

# Answer
> 5 votes
# Python 2, ~~79~~ ~~75~~ 73 bytes

```
def f(x):
 i=j=0
 for n in x+[0]:
    if~n%2:x[i:j]=x[i:j][::-1];i=j+1
    j+=1

```

This is a function that modifies its argument in place. Second indentation level is a tabulator.

Test it on Ideone.

# Answer
> 4 votes
# Jelly, 10 bytes

```
Ḃ¬ðœpUżx@F

```

Try it online! or verify all test cases.

### How it works

```
Ḃ¬ðœpUżx@F  Main link. Argument: A (array)

Ḃ           Bit; return the parity bit of each integer in A.
 ¬          Logical NOT; turn even integers into 1's, odds into 0's.
  ð         Begin a new, dyadic link.
            Left argument: B (array of Booleans). Right argument: A
   œp       Partition; split A at 1's in B.
     U      Upend; reverse each resulting chunk of odd numbers.
       x@   Repeat (swapped); keep only numbers in A that correspond to a 1 in B.
      ż     Zipwith; interleave the reversed runs of odd integers (result to the
            left) and the flat array of even integers (result to the right).
         F  Flatten the resulting array of pairs.

```

# Answer
> 4 votes
## Python3, 96 bytes

Saved a lot of bytes thanks to Leaky Nun!

```
o=l=[]
for c in input().split():
 if int(c)%2:l=[c]+l
 else:o+=l+[c];l=[]
print(" ".join(o+l))

```

# Answer
> 4 votes
# Python 2, 78 75 bytes

```
def r(l):
 def k(n):o=~n%2<<99;k.i+=o*2-1;return k.i-o
 k.i=0;l.sort(key=k)

```

Super hacky :)

# Answer
> 3 votes
# C, 107 bytes

```
i;b[65536];f(){for(;i;)printf("%d ",b[--i]);}main(n){for(;~scanf("%d",&n);)n%2||f(),b[i++]=n,n%2||f();f();}

```

# Answer
> 3 votes
# MATL, 20 bytes

```
TiodgvYsG8XQ!"@gto?P

```

Input is a column array, using `;` as separator.

**Try it online!**

### Explanation

Consider as an example the input array `[1;2;3;5;7;4;6;7;9]`. The first part of the code, `Tiodgv`, converts this array into `[1;1;1;0;0;1;0;1;0]`, where `1` indicates a *change of parity*. (Specifically, the code obtains the parity of each entry of the input array, computes consecutive differences, converts nonzero values to `1`, and prepends a `1`.)

Then `Ys` computes the *cumulative sum*, giving `[1;2;3;3;3;4;4;5;5]`. Each of these numbers will be used as a *label*, based on which the elements of the input will be *grouped*. This is done by `G8XQ!`, which splits the input array into a cell array containing the groups. In this case it gives `{[1] [2] [3;5;7] [4;6] [7;9]}`.

The rest of the code *iterates* (`"`) on the cell array. Each constituent numeric array is pushed with `@g`. `to` makes a copy and *computes its parity*. If (`?`) the result is truthy, i.e. the array contents are odd, the array is *flipped* (`P`).

The stack is *implicitly displayed* at the end. Each numeric vertical array is displayed, giving a list of numbers separated by newlines.

# Answer
> 3 votes
# Pyth, 14 bytes

```
s_McQshMBx0%R2

           %R2Q   Take all elements of the input list modulo 2
         x0       Get the indices of all 0s
      hMB         Make a list of these indices and a list of these indices plus 1
     s            Concatenate them
   cQ             Chop the input list at all those positions
 _M               Reverse all resulting sublists
s                 Concatenate them

```

Test cases

# Answer
> 3 votes
# Desmos, 167 bytes

```
k=mod(l,2)
K=l.length
a=[K...1]
L=a[k[a]=1]
g(q)=∑_{n=1}^{[1...q.length]}q[n]
A=g(join(1,sign(L-L[2...]-1)))
f(l)=l[\{k>0:\sort(L,A.\max+1-A)[g(k)],k\}+[1...K](1-k)]

```

Hooooly crap, this was pretty challenging to do in Desmos given its limited list functionalities, but after lots of puzzling and scratched ideas, I finally managed to pull together something that actually works.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 3 votes
# Desmos, ~~94~~ 93 bytes

```
g(M,j)=j-max([1...j]0^{mod(M,2)})
f(L)=L[[i+g(L[n...1],n+1-i)-g(L,i)fori=[1...n]]]
n=L.length

```

Try it on Desmos!

\*-1 byte thanks to @AidenChow (remove space after `for`)

## How it works

`g(M,j)` gives the difference between `j` and the greatest index less than (or equal to) `j` of an even entry in `M`. For example, `g([0,2,4,1,3,5,7,6,8],6) = 3` because the 6th element in the list is 5, and the last even entry before it is 4, which is 3 elements earlier.

`f(L)` is the solution to the challenge. It's of the form `L[[h(i)for i=[1...n]]]`, which is a list indexing: `h(i)` gives the index of the value in `L` that should be at index `i` in the result list.

The main difficulty lies in `h(i)`, defined as `h(i) = i+g(L[n...1],n+1-i)-g(L,i)`. Note that `g(M,j) = 0` whenever `M[j]` is even, so `h(i)=i` if `L[i]` is even (this corresponds to even entries not moving) since `L[n...1][n+1-i]=L[i]=even`

If `L[i]` is odd then we have a more complicated story: `g(L,i)` gives the distance to the element before the start of the odd run, and `g(L[n...1],n+1-i)` gives the distance to the element after the end of the odd run. Then `g(L[n...1],n+1-i)-g(L,i)` says how much closer the element is to the end of the run than the start of the run. For example, for `L=[0,2,4,1,3,5,7,6,8]` and `i=6`, this difference is `-1`, so `L[6]` has to move 1 element to the left, to where the `3` is currently.

In general regarding the difference `g(L[n...1],n+1-i)-g(L,i)`:

* if the difference is positive, then the element is closer to the left than the right, and it needs to move right by the value of the difference
* if the difference is negative, then the element is closer to the right than the left, and it needs to move left by the negative of the difference
* if the difference is zero, then the element is at the center of an odd-length run, so it doesn't need to move at all.

# Answer
> 2 votes
# , ~~33~~ ~~31~~ 30 bytes

```
[:;]<@(A.~2-@|{.);.1~1,2|2-/\]

```

## Usage

```
   f =: [:;]<@(A.~2-@|{.);.1~1,2|2-/\]
   f 0 1
0 1
   f 1 3
3 1
   f 1 2 3
1 2 3
   f 1 3 2
3 1 2
   f 10 7 9 6 8 9
10 9 7 6 8 9
   f 23 12 32 23 25 27
23 12 32 27 25 23
   f 123 123 345 0 1 9
345 123 123 0 9 1

```

# Answer
> 2 votes
# JavaScript (ES6) ~~70~~ 66 bytes

**Edit** 4 bytes saved thx @Neil

```
a=>[...a,[]].map(x=>x&1?o=[x,...o]:r=r.concat(o,x,o=[]),r=o=[])&&r

```

# Answer
> 2 votes
# C#, ~~179~~ ~~178~~ 177 bytes

```
s=>{var o=new List<int>();var l=new Stack<int>();foreach(var n in s.Split(' ').Select(int.Parse)){if(n%2>0)l.Push(n);else{o.AddRange(l);o.Add(n);l.Clear();}}return o.Concat(l);}

```

I use a C# lambda. You can try it on .NETFiddle.

The code less minify:

```
s => {
    var o=new List<int>();var l=new Stack<int>();
    foreach (var n in s.Split(' ').Select(int.Parse)) {
        if (n%2>0)
            l.Push(n);
        else {
            o.AddRange(l);
            o.Add(n);
            l.Clear();
        }
    }
    return o.Concat(l);
};

```

Kudos to Byeonggon Lee for the original algorithm.

# Answer
> 2 votes
# Clojure, 86 bytes

```
#(flatten(reduce(fn[a b](if(odd? b)(conj(pop a)(conj[b](last a)))(conj a b[])))[[]]%))

```

Here is the ungolfed version

```
#(flatten ; removes all empty vectors and flattens odd sequences
    (reduce
        (fn[a b]
            (if(odd? b) ; if we encounter odd number in the seq
                (conj(pop a)(conj[b](last a))) ; return all elements but last and the element we encountered plus the last element of current result
                (conj a b[])) ; else just add the even number and the empty vector
            )
        [[]] ; starting vector, we need to have vector inside of vector if the sequence starts with odd number
        %    ; anonymous function arg
    )
)

```

Basically it goes through the input sequence and if it encounters even number it adds the number and the empty vector otherwise if it's an odd number it replaces the last element with this number plus what was in the last element.

For example for this seq `2 4 6 1 3 7 2` it goes like this:

* `[]<=2`
* `[2 []]<=4`
* `[2 [] 4 []]<=6`
* `[2 [] 4 [] 6 []]<=1`
* `[2 [] 4 [] 6 [1 []]]<=3`
* `[2 [] 4 [] 6 [3 [1 []]]]<=7`
* `[2 [] 4 [] 6 [7 [3 [1 []]]]]<=2`
* `[2 [] 4 [] 6 [7 [3 [1 []]]] 2 []]`

And then flattening this vector gives the correct output. You can see it online here: https://ideone.com/d2LLEC

# Answer
> 2 votes
# Husk, 7 bytes

```
ṁ↔ġ¤&%2

```

Try it online!

## Explanation

```
ṁ↔ġ¤&%2  Implicit input, a list of integers.
  ġ      Group by equality predicate:
   ¤ %2   Arguments modulo 2
    &     are both truthy.
ṁ        Map and concatenate
 ↔       reversing.

```

# Answer
> 2 votes
# Ruby, 51 bytes

```
->l{l.chunk(&:odd?).flat_map{|i,j|i ?j.reverse: j}}

```

Try it online!

Some slight variations:

```
->l{l.chunk(&:odd?).flat_map{|i,j|i&&j.reverse||j}}
->l{l.chunk(&:odd?).flat_map{|i,j|!i ?j:j.reverse}}
->l{l.chunk(&:even?).flat_map{|i,j|i ?j:j.reverse}}

```

### Ruby 2.7, 48 bytes

```
->l{l.chunk{_1%2}.flat_map{_1>0?_2.reverse: _2}}

```

Unsupported by TIO :(

# Answer
> 1 votes
# Pyth, ~~29~~ 28 bytes

```
JYVQ=+J*%hN2+YN=Y*%N2+NY;+JY

```

Test suite.

Direct translation of my python answer (when has translating from python to pyth become a good idea?)

# Answer
> 1 votes
# TSQL 118 bytes

```
DECLARE @ TABLE(i int identity, v int)
INSERT @ values(123),(123),(345),(0),(1),(9)

SELECT v FROM(SELECT sum((v+1)%2)over(order by i)x,*FROM @)z
ORDER BY x,IIF(v%2=1,max(i)over(partition by x),i),i desc

```

**Fiddle**

# Answer
> 1 votes
# Stax, ~~15~~ 10 bytesCP437

```
Çⁿ╜"}☻≥º╚(

```

Try it online!

**Tied Jelly!** So sad that packing only saved one byte.

Unpacked version with 11 bytes:

```
{|e_^*}/Frm

```

## Explanation

`{|e_^*}` is a block that maps all even numbers `n` to `n+1`, and all odd numbers `n` to `0`.

```
{|e_^*}/Frm
{     }/       Group array by same value from block
 |e            1 if the element is even, 0 if odd.
   _^          Get another copy of the current element and increment by 1
     *         Multiply them
        F      For each group execute the rest of the program
         r     Reverse the group
          m    Print elements from the group, one element per line.

```

# Answer
> 1 votes
## Perl 5 with `-p`, 42 bytes

```
map{$_%2?$\=$_.$\:print$\.$_,$\=""}$_,<>}{

```

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~11~~ 9 bytes

```
.γÈN>*}í˜

```

Try it online or verify all test cases.

**Explanation:**

```
.γ    }    # Adjacent group the (implicit) input-list by:
  È        #  Check if the value is even (1 if even; 0 if odd)
   N>*     #  Multiply it by the 1-based index
           # (adjacent odd values will be grouped together, and every even
           # value is in its own separated group)
       í   # After the adjacent group-by: reverse each inner list
        ˜  # Flatten the list of lists
           # (after which the result is output implicitly)

```

# Answer
> 1 votes
# , 27 bytes

```
[:;]<@(|.^:{.);.1~1,2|2-/\]

```

Try it online!

A minor improvement over miles' J answer.

### How it works

```
[:;]<@(|.^:{.);.1~1,2|2-/\]  NB. Input: an integer vector V
                  1,2|2-/\]  NB. Pairwise difference modulo 2 and prepend 1
                             NB. giving starting positions for same-parity runs
   ]          ;.1~  NB. Cut V at ones of ^ as the starting point and
      (|.^:{.)      NB. reverse each chunk (head of the chunk) times
                    NB.   (effectively, reverse odd chunks only)
    <@              NB. and enclose it
[:;                 NB. Finally, flatten the result

```

# Answer
> 1 votes
# JavaScript (Node.js), 53 bytes

```
a=>a.map((c,k)=>o.splice(n=c&1?+n:k+1,0,c),o=n=[])&&o

```

Try it online!

# JavaScript (Node.js), 54 bytes

```
a=>a.map((c,k)=>o.splice(n=c&1?n:k+1,0,c),o=[],n=0)&&o

```

Try it online!

# Answer
> 1 votes
# , 69 bytes

```
v=scan();ifelse(o<-v%%2,v[rep(2*cumsum(r<-rle(o)$l)-r+1,r)-seq(v)],v)

```

Try it online!

Ungolfed, commented version:

```
o=v%%2              # get the odd numbers in the list
r=rle(o)$l          # find the run lengths of odd/even numbers

# reverse the indices of all the runs:
e=cumsum(r)         # the indices of the ends of each run
ie=rep(e,r)         # for each index in v, the index of the end of its run
is=rep(e-r+1,r)     # for each index in v, the index of the start of its run
irev=is+(ie-seq(v)) # reverses all runs

# the above 4 steps can be combined as:
irev=rep(2*cumsum(r)-r+1,r)-seq(v)

# so: use the reversed indices for odd numbers, and leave the even numbers unchanged
ifelse(o,v[irev],v)

```

# Answer
> 1 votes
# Clojure, 66 bytes

```
#(mapcat(fn[x](if(some odd? x)(reverse x)x))(partition-by odd? %))

```

Try it online!

# Answer
> 1 votes
# Factor \+ `grouping.extras`, 62 bytes

```
[ [ odd? ] group-by [ last2 swap [ reverse ] when ] map-flat ]

```

Attempt This Online!

# Answer
> 1 votes
# Vyxal, 10 bytes

```
λ&›₂¥*;ḊRf

```

Try it Online!

Port of 05AB1E.

Another 10-byter that I produced independently: `⁽₂Ḋƛh∷ßṘ;f`

---
Tags: code-golf, number-theory, sorting, subsequence, search
---