title: Half, Half Half, and, Half

text:
# Question
Title: Half, Half Half, and, Half
Consider the following number sequence:

> \\$ 0, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}, \frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}, \frac{9}{16}, \frac{11}{16}, \frac{13}{16}, \frac{15}{16}, \frac{1}{32}, \frac{3}{32}, \frac{5}{32}, \dots \\$

It enumerates all binary fractions in the unit interval \\$ \[0, 1) \\$.

(To make this challenge easier, the first element is optional: You may skip it and consider the sequence starts with 1/2.)

### Task

Write a program (complete program or a function) which...

Choose one of these behaviors:

* Input n, output nth element of the sequence (0-indexed or 1-indexed);
* Input n, output first n elements of the sequence;
* Input nothing, output the infinite number sequence which you can take from one by one;

### Rule

* Your program should at least support first 1000 items;
* You may choose to output decimals, or fractions (built-in, integer pair, strings) as you like;
    + Input / Output as binary digits is not allowed in this question;
* This is , shortest codes win;
* Standard loopholes disallowed.

### Testcases

```
input output
1     1/2     0.5
2     1/4     0.25
3     3/4     0.75
4     1/8     0.125
10    5/16    0.3125
100   73/128  0.5703125
511   511/512 0.998046875
512   1/1024  0.0009765625

```

These examples are based on 0-indexed sequence with the leading 0 included. You would need to adjust the input for fitting your solution.

### Read More

* **OEIS A006257**
    + Josephus problem: \\$ a\_{2n} = 2a\_n-1, a\_{2n+1} = 2a\_n+1 \\$. (Formerly M2216)
    + 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
* **OEIS A062383**
    + \\$ a\_0 = 1 \\$: for \\$ n\>0 \\$, \\$ a\_n = 2^{\lfloor log\_2n+1 \rfloor} \\$ or \\$ a\_n = 2a\_{\lfloor \frac{n}{2} \rfloor} \\$.
    + 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...
* > A006257(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval \[0, 1). - Fredrik Johansson, Aug 14 2006

# Answer
# Haskell, 25 bytes

```
pred.until(<2)(/2).(+0.5)

```

Try it online!

Outputs decimals, one-indexed without the initial zero term.

Adds 0.5 to the input, then halves until the results is below 2, then subtracts 1. Using a pointfree expression saves 1 bytes over

```
f n=until(<2)(/2)(n+0.5)-1

```
> 22 votes

# Answer
# Java 10, ~~68~~ 64 bytes

First try at code golf!

Option 1: find the *n*-th element (1-indexed)

-4 bytes thanks to @Kevin Cruijssen

```
n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);}

```

This is an anonymous method that finds the *n*-th term by removing the most significant bit from *n*, doubling it and adding one, then dividing by the next highest power of 2.

Try it online!

Code walkthrough:

```
n->{                      // builds anonymous function with input n
int x=0;                  // stores floor of log(n) (base 2) for most significant digit
for(;n>>++x!=1;);         // calculates floor of log(n) by counting right shifts until 1
return((~(1<<x)&n)        // removes most significant digit of n
*2.+1)                     // multiplies 2 and adds 1 to get the odd numerator
/(1<<x+1);}               // divides by the next highest power of 2 and returns`

```

Will edit if it's necessary to print the final value instead of returning it.
> 11 votes

# Answer
# MathGolf, ~~5~~ 4 bytes

```
╫\╨]

```

Try it online!

## How it would look like with the operator working correctly

```
╫\)╨]   (")" adds 1 to TOS, making rounding behave as expected)

```

Try it online!

## Explanation

```
╫     Left-rotate all bits in input
 \    Swap top two elements on stack, pushing the input to the top
  ╨   Round up to nearest power of 2
   ]  Wrap in array (just for pretty printing)

```

I took my inspiration from this question to solve the problem, my "own" solution was around 10-12 bytes I think.

I had intended for the round up to closest power of 2 to return the number itself if it was a number of two, but due to a mistake it rounds to the next power of two (e.g. 4 -\> 8 instead of 4 -\> 4). This will have to be fixed later, but now it saves me one byte.
> 9 votes

# Answer
# Java 10, ~~89~~ ~~85~~ ~~70~~ ~~69~~ 68 bytes

```
v->{for(float j,t=2;;t*=2)for(j=1;j<t;j+=2)System.out.println(j/t);}

```

Port of *@Emigma*'s 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to *@Arnauld*.

Try it online.

**Explanation:**

```
v->{                      // Method with empty unused parameter and no return-type
  for(float j,t=2;;       //  Loop `t` from 2 upwards indefinitely,
                   t*=2)  //  doubling `t` after every iteration
    for(j=1;j<t;          //   Inner loop `j` in the range [1, `t`),
                j+=2)     //   in steps of 2 (so only the odd numbers)
      System.out.println( //    Print with trailing new-line:
        j/t);}            //     `j` divided by `t`

```
> 8 votes

# Answer
# Perl 6, 19 bytes

```
{($_+.5)/2**.msb-1}

```

Try it online!
> 8 votes

# Answer
# Java (JDK 10), 30 bytes

```
n->(n+.5)/n.highestOneBit(n)-1

```

Try it online!

Returns the nth item in the sequence.

This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-)

Intermediate golfs were:

```
n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);} // 64 bytes (TCFP's answer when I started golfing)
n->{int x=0;for(;n>>++x!=1;);x=1<<x;return((~x&n)*2.+1)/x/2;}    // 61 bytes
n->{int x=n.highestOneBit(n);return((~x&n)*2.+1)/x/2;}           // 54 bytes
n->{int x=n.highestOneBit(n);return((~x&n)+.5)/x;}               // 50 bytes
n->((n&~(n=n.highestOneBit(n)))+.5)/n                            // 37 bytes
n->(n-(n=n.highestOneBit(n))+.5)/n                               // 34 bytes
n->(n+.5)/n.highestOneBit(n)-1                                   // 30 bytes, current score

```
> 8 votes

# Answer
# Python 3, 33 bytes

```
lambda n:(8*n+4)/2**len(bin(n))-1

```

Try it online!

Outputs decimals, one-indexed without the initial zero term.
> 7 votes

# Answer
# 05AB1E, ~~11~~ 8 bytes

Saved 3 bytes thanks to *Kevin Cruijssen*.

```
∞oDÅÉs/˜

```

Try it online!

**Explanation**

```
∞         # start an infinite list [1...
 o        # calculate 2**N
  D       # duplicate
   ÅÉ     # get a list of odd numbers up to 2**N
     s/   # divide each by 2**N
       ˜  # flatten

```
> 6 votes

# Answer
# Jelly, 9 bytes

```
Bṙ1Ḅ,æċ2$

```

Try it online!
> 5 votes

# Answer
# PowerShell, 40 bytes

```
for($i=2;;$i*=2){1..$i|?{$_%2}|%{$_/$i}}

```

Try it online!

Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.

Starts by setting `$i=2`, then enters a `for` loop. Each iteration, we construct a range from `1..$i` and pull out the odd values with `|?{$_%2}`. Those are fed into their own inner loop, where we divide each to get the decimal `|%{$_/$i}`. Those are left on the pipeline and output when the pipeline is flushed after every `for` iteration. Each iteration we're simply incrementing `$i` by `$i*=2` to get the next go-round.
> 5 votes

# Answer
## Haskell, ~~35~~ 32 bytes

Edit: -3 bytes thanks to @Delfad0r.

```
[(y,2^x)|x<-[1..],y<-[1,3..2^x]]

```

This is an infinite list of integer pairs.

Try it online!
> 5 votes

# Answer
# Haskell, 40 bytes

```
s=(1,2):[(i*2+u,j*2)|(i,j)<-s,u<-[-1,1]]

```

Try it online!

Infinite sequence as pairs of integers (starting from `(1,2)`).

Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway.

This solution is based on the following observation.

Consider the infinite sequence $$ \left\\{\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\\} $$ and apply the following steps.

* Replace every number \\$\frac{i}{j}\\$ in the sequence with the list \\$\left\\{\frac{2i-1}{2j},\frac{2i+1}{2j}\right\\}\\$: $$ \left\\{\left\\{\frac{1}{4},\frac{3}{4}\right\\},\left\\{\frac{1}{8},\frac{3}{8}\right\\},\left\\{\frac{5}{8},\frac{7}{8}\right\\},\left\\{\frac{1}{16},\frac{3}{16}\right\\},\ldots\right\\} $$
* Join all the lists into a single sequence: $$ \left\\{\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\\} $$
* Add \\$\frac{1}{2}\\$ at the beginning of the sequence: $$ \left\\{\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\\} $$

Notice how you get back to the sequence you started with!

The solution exploits this fact (together with Haskell's laziness) to compute the sequence `s`.
> 5 votes

# Answer
# , ~~42~~ 41 bytes

```
function(n)2*c(y<-2^(log2(n)%/%1),n-y+.5)

```

Try it online!

*-1 byte thanks to Robin Ryder*

Returns a pair `Denominator,Numerator`. Uses the formula \\$\begin{equation}N = 2\times\left(n-2^{\lfloor \log\_2(n)\rfloor}\right)+1\end{equation}\\$ from the Josephus sequence and \\$\begin{equation}D = 2^{\lfloor \log\_2(n)\rfloor+1}\end{equation}\\$ from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common!
> 5 votes

# Answer
# Python 2 - ~~68~~ 66 bytes

*-2 bytes thanks to Kevin*

```
from math import*
def g(n):a=2**floor(log(n,2));print(n-a)*2+1,2*a

```

Try it Online!
> 4 votes

# Answer
# Python 3, ~~53~~ 51 bytes

* Saved two bytes thanks to mypetlion; reusing default parameters to reset `n`.

```
def f(m=2,n=1):n<m and print(n/m)&f(m,2+n)or f(m+m)

```

Try it online!
> 4 votes

# Answer
# Racket, ~~92~~ 91 bytes

```
(define(f k(m 2)(n 1))(if(> k 0)(if(=(+ n 1)m)(f(- k 1)(+ m m))(f(- k 1)m(+ n 2)))(/ n m)))

```

Try it online!

* Saved a byte thanks to Giuseppe -- removing superfluous whitespace.
> 3 votes

# Answer
# MATL, 8 bytes

```
BnWGEy-Q

```

Try it online!

Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient.

Explanation, with input `5`:

```
           # implicit input 5
B          # convert to array of bits
           # STACK: [[1 0 1]]
n          # length (place of Most Significant Bit)
           # STACK: [3]
W          # elementwise raise 2^x
           # STACK: [8]
G          # paste input
           # STACK: [8, 5]
E          # double
           # STACK: [8, 10]
y          # copy from below
           # STACK: [8, 10, 8]
-          # subtract
           # STACK: [8, 2]
Q          # increment
           # STACK: [8, 3]
           # implicit end of program, display stack contents

```
> 3 votes

# Answer
# Factor, 52 bytes

```
{ 1/2 } [ dup stack. dup 1 v+n append 2 v/n t ] loop

```

Try it online!

Prints each fraction on its own line forever. Keeps track of the array of all terms with equal denominator.

```
{ 1/2 }         ! Push the initial array
[ ... t ] loop  ! Loop forever:
  dup stack.    !   Print all fractions separated by a newline
  dup 1 v+n     !   Copy and add 1 to all fractions
  append 2 v/n  !   Join and halve all fractions

```
> 3 votes

# Answer
# Shakespeare Programming Language, 426 bytes

```
,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You be the sum ofyou a cat.Ford:You cat.Scene V:.Ford:Is twice you nicer I?If solet usScene X.You be twice you.Let usScene V.Scene X:.Ford:Remember twice you.You be the sum oftwice the remainder of the quotient betweenI you a cat.Open heart.You big big big big big cat.Speak thy.Recall.Open heart.You be twice the sum ofa cat a big big cat.Speak thy.Let usAct I.

```

Try it online!

Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline.
> 2 votes

# Answer
# Excel ~~48~~ 28 Bytes

Saved 20 bytes (!) thanks to tsh

```
=(A1+0.5)/2^INT(LOG(A1,2))-1

```

~~=MOD(A1+0.5,2^(INT(LOG(A1,2))))/2^INT(LOG(A1,2))~~

Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction.

**Explanation:** Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input.

I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift).

```
=MOD(A1                        Use MOD for finding what the right digits are
       +0.5                    this will later add the left "1" to the right digits
           ,2^INT(LOG(A1,2)))) Take Log base 2 number of digits on the right
                               this creates the numerator divided by 2 (explained later)
/ 2^INT(LOG(A1,2))             The denominator should be 2^ (Log2 + 1) but instead of
                               adding a 1 here, we cause the numerator to be divided by 2 instead
                               This gives us a fraction.  In the numerator, we also added .5
                               instead of 1 so that we wouldn't need to divide it in both the
                               numerator and denominator
Then tsh showed how I could take the int/log out of the mod and remove it from numerator/denominator.

```

Examples:
> 2 votes

# Answer
# Python 2, 44 bytes

```
def f(n):m=2**len(bin(n))/4;return 2*n-m+1,m

```

Try it online!

Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional).
> 2 votes

# Answer
## C++, ~~97~~ ~~75~~ 71 bytes

-26 bytes thanks to tsh, ceilingcat, Zacharý

```
float f(int i){float d=2,n=1;while(--i)n=d-n==1?d*=2,1:n+2;return n/d;}

```

Testing code :

```
std::cout << "1\t:\t" << f(1) << '\n';
std::cout << "2\t:\t" << f(2) << '\n';
std::cout << "3\t:\t" << f(3) << '\n';
std::cout << "4\t:\t" << f(4) << '\n';
std::cout << "10\t:\t" << f(10) << '\n';
std::cout << "100\t:\t" << f(100) << '\n';
std::cout << "511\t:\t" << f(511) << '\n';
std::cout << "512\t:\t" << f(512) << '\n';

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 22 bytes

```
2^Mod[Log2[2#+1],1]-1&

```

Try it online!
> 2 votes

# Answer
# Husk, 13 bytes

```
ṁz*İ1zR:1İ2İ½

```

Try it online!

Abuses the built in sequences to the fullest.

Outputs an infinite list.

## Explanation

```
ṁz*İ1zR:1İ2İ½
           İ½ powers of ½
       :1İ2   powers of 2, with 1 prepended
     zR       zip replicate the second by the first
 z*           then zip multiply that with:
   İ1         odd numbers
ṁ             map to each of the power arrays, and concatenate into single list

```
> 2 votes

# Answer
# Factor, ~~68~~ 66 bytes

Saved 2 bytes thanks to @chunes

```
[ 1 2 [ 2dup / . [ 2 + ] dip 2dup > [ 2 * 1 swap ] when t ] loop ]

```

Try it online!

Outputs the sequence infinitely.

```
[
  1 2                    ! First numerator and denominator
  [                      ! Loop body
    2dup /               ! Divide to get next element of sequence
    .                    ! Print the element
    [ 2 + ] dip          ! Add 2 to the numerator
    2dup >               ! If numerator > denominator
    [
      2 *                ! Multiply denominator by 2
      1 swap             ! Set numerator to 1
    ]
    when                 ! Functions like an if statement
    t                    ! Push true on the stack so the loop doesn't stop
  ]
  loop                   ! Run while top of stack is true (which is forever)
]

```
> 2 votes

# Answer
# C (gcc), 63 bytes

No input, prints infinite sequence:

```
f(i,j){for(i=1,j=2;;i+=2,i>j&&(j*=2,i=1))printf("%d/%d ",i,j);}

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 44 bytes

Returns the \\$n\\$-th term, 1-indexed.

```
f=(n,p=q=1)=>n?f(n-1,p<q-2?p+2:!!(q*=2)):p/q

```

Try it online!
> 1 votes

# Answer
# Ruby, 42 bytes

```
1.step{|i|(1..x=2**i).step(2){|j|p [j,x]}}

```

Try it online!

Prints integer pairs infinitely, starting from 1/2.
> 1 votes

# Answer
# JavaScript (Node.js), 30 bytes

```
f=(n,d=.5)=>d>n?n/d:f(n-d,d*2)

```

Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of \\$\frac{1}{2}\\$ which saved several bytes.
> 1 votes

# Answer
# Ruby, 31 bytes

```
->x{(2r*x+1)/2**x.bit_length-1}

```

Try it online!
> 1 votes

# Answer
# \>\<\>, ~~19~~ 18 bytes

Using xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the `!` was superfluous and `;` is not required.

```
2*1+\1-n
2:,2/?(

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog Unicode), 15 bytes

```
1-⍨.5∘+÷2*∘⌊2⍟⊢

```

Try it online!

Anonymous prefix lambda.

Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.

### How:

```
1-⍨.5∘+÷2*∘⌊2⍟⊢ ⍝ Anonymous lambda, argument ⍵ → 10
            2⍟⊢ ⍝ Log (⍟) of ⍵ in base 2. 2⍟10 → 3.32192809489...
           ⌊     ⍝ Floor. ⌊3.32192809489... → 3
        2*∘      ⍝ Take that power of 2. 2³ → 8
       ÷         ⍝ Use that as denominator
   .5∘+          ⍝ ⍵ + 0.5 → 10.5. Using that as numerator: 10.5÷8 → 1.3125
1-⍨              ⍝ Swap the arguments (⍨), then subtract. 1-⍨1.3125 → 1.3125-1 → 0.3125

```
> 1 votes

# Answer
# Stax, 8 bytes

```
▀`Ö²╬─}t

```

Run and debug it

This program uses stax's rational type. It takes a 1-based integer index as input, and produces that sequence element.

Unpacked, ungolfed, and commented, it looks like this.

```
Hc  double the input and copy it
:GY unset all but the highest bit, and store in register Y
-^  subtract (leaving all the other bits), then increment
yu* push the value in register Y, then multiply by its reciprocal

```

Run this one
> 1 votes

# Answer
# C# (.NET Core), 69 bytes

```
a=>{int b=1,c=2;while(a-->1){b+=2;if(b>c){b=1;c*=2;}}return b+"/"+c;}

```

Try it online!

Ungolfed:

```
a=> {
    int b = 1, c = 2;   // initialize numerator (b) and denominator (c)
    while (a-- > 1)     // while a decrements to 1
    {
        b += 2;         // add 2 to b
        if (b > c)      // if b is greater than c:
        {
            b = 1;      // reset numerator to 1
            c *= 2;     // double denominator
        }
    }
    return b + "/" + c; // return fraction as string
}

```
> 1 votes

# Answer
# x86 machine code, 36 bytes

```
00000000: 4389 de46 5653 6800 0000 00e8 fcff ffff  C..FVSh.........
00000010: 83c3 0239 f37e edd1 e631 db43 ebe6 2564  ...9.~...1.C..%d
00000020: 2f25 6420                                /%d

```

Prints the sequence infinitely.

The hexdump is unlinked, e.g. the address for `printf` is a placeholder.

Assembly:

```
section .text
	global func
	extern printf
func:
	inc ebx			;set numerator to 1
	mov esi, ebx
	inc esi			;set denominator to 2
	loop:
		push esi
		push ebx
		push fmt
		call printf
		add ebx, 2	;increment numerator by 2
		cmp ebx, esi
		jle loop	;if numerator<denominator (eg ebx/esi<1), repeat loop
		shl esi, 1	;double the denominator
		xor ebx, ebx
		inc ebx		;reset numerator to 1
		jmp loop
section .data
	fmt db '%d/%d '

```

Try it online!
> 1 votes

# Answer
# Zephyr, 82 bytes

```
set d to 2
while 1=1
for n from 1 to d/2
print((2*n)-1)/d
next
set d to d*2
repeat

```

Try it online!

Iterate over denominators 2, 4, 8, 16, ... forever. For each `d` (e.g. 8), iterate `n` from 1 up to `d/2` (e.g. 1, 2, 3, 4). The desired odd-number numerators are then `2*n-1`. Zephyr's built-in rational numbers mean we just do the division and print the result.

(I really think more languages should have built-in rational numbers!)
> 0 votes

# Answer
## Batch, 73 bytes

```
@set/an=%1*2,d=1
:l
@if %d% leq %1 set/an-=d,d*=2&goto l
@echo %n%/%d%

```

Outputs `0/1` for an input of 0. Explanation: `n` is the numerator and `d` is the denominator. `d` is doubled each time until it exceeds the input, and the previous value of `d` is subtracted from `n` as it goes. This is slightly golfier than calculating `n=%1*2+1-d` separately.
> 0 votes

# Answer
# Appleseed, 76 bytes

```
(def s(lambda((d 2)(n 1))(if(> n d)(s(* d 2))(cons(list n d)(s d(+ n 2))))))

```

Defines a function `s` that, when called without arguments, returns an infinite list of `(<numer> <denom>)` pairs. Try it online!

### Ungolfed

```
(def sequence
  (lambda ((denom 2) (numer 1))
    (if (less? denom numer)
      (sequence (* denom 2))
      (cons
        (list numer denom)
        (sequence denom (+ numer 2))))))

```

Same idea as Jonathan Frech's Python function (right down to the order of the default arguments being important), except here we `cons` each result onto the (infinite) recursive call instead of printing it.
> 0 votes

# Answer
# Perl 5 `-a`, 53 bytes

```
map{say"$_/$.";--$F[0]||exit}grep$_%2,1..$.while$.*=2

```

Try it online!

1-indexed. First element is 1/2. Outputs the first n elements.
> 0 votes

# Answer
# Perl 6, 38 bytes

```
(0,{(1,3...2**@_-1)X/2**@_}...*)>>.say

```

Try it online!

Outputs elements infinitely, starting from 0.

An infinite sequence itself ends up at 40 bytes

```
.5,{$/=.nude;($1-$0-1??$0+2!!.5)/$1}...*

```

Try it online!
> 0 votes

# Answer
# Python 3, 71 bytes

```
n,d=0,1
for t in range(int(input())):
    n+=2
    if n>d:n=1;d*=2
print(n/d)

```

Index starts with 0 at 0.0 and 1 at 0.5 and so on.

Try it online!
> 0 votes

# Answer
# APL(NARS), 30 chars, 60 bytes

```
{⍵=0:0⋄(1+2×⍵-2*k)÷2*1+k←⌊2⍟⍵}

```

test:

```
f←{⍵=0:0⋄(1+2×⍵-2*k)÷2*1+k←⌊2⍟⍵}
  f¨0 1 2 3 4 5 6 7 8
0 0.5 0.25 0.75 0.125 0.375 0.625 0.875 0.0625
  f¨511 512  10023
0.998046875 0.0009765625 0.2235717773

```
> 0 votes

# Answer
# , 66 bytes

```
T f(T)(T i){T d=2,n=1;while(--i)n=d-n==1?(d*=2)/d:n+2;return n/d;}

```

Try it online!

Port of @HatsuPointerKun's C++ answer.

*grumble* Comma expressions are pretty worthless in D *grumble*
> 0 votes

# Answer
# J, 20 bytes

```
(>:@+:@#.@}.,2^#)@#:

```

This verb take `n` and gives us the nth number in the list. `n = 1` produces 1/2, etc...

## explanation

```
(>:@+:@#.@}. , 2 ^ #)@#:
                     @#:  NB. The arg as list of binary digits, feed that to...
             ,            NB. the concatenation of... (first doing the left side)
         @}.              NB. remove the highest order bit and...
      @#.                 NB. convert back to decimal and...
   @+:                    NB. double it and...
 >:                       NB. add one (now we have the numerator)
               2 ^        NB. (now doing the right side) 2 raised to the...
                   #      NB. number of binary digits (the denominator)

```

Try it online!
> 0 votes

---
Tags: code-golf, number, sequence, integer, rational-numbers
---


title: Reverse Zip Bomb

text:
# Question
Title: Reverse Zip Bomb
A zip bomb is a compressed file, designed so that unpacking it yields the biggest file possible. These are fairly well known, and there are examples of 42 KB files which expand into multiple petabytes of data.

In this challenge, the goal is reversed. Instead of providing a compressed file which is then unpacked, the goal is to provide an uncompressed file which is compressed in an unreasonably inefficient manner, ideally becoming larger than the original.

**Rules:**

You should provide a file between **10 KB** and **1 GB**, which will be compressed by your chosen algorithm. You should also specify a compression algorithm, such as gzip or PNG. If the algorithm allows things like a compression level to be set, different configurations count as different algorithms. The algorithm can be lossless or lossy, and can be application specific (like PNG or MP3).

Submissions are scored based on the ratio of \\$\frac{\text{compressed}}{\text{original}}\\$. For example, an 80 KB file that "compresses" to 88 KB would get a score of \\$1.1\\$. The highest scoring solution, **per algorithm**, wins.

# Answer
> 27 votes
# FFmpeg `-crf 0 -preset ultrafast -tune film -vf format=yuv444p`, score 198.7425

Input is a 65535 × 1 PBM file:

```
P4 65535 1 IEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEIEI

```

This image consists of repetitions of the following 16-pixel pattern:

The input file is exactly 10,000 bytes: the first 8203 bytes encode the image (one bit per pixel plus the 11 byte header); the last 1797 bytes are padding.

The input is 'compressed' into a single-frame lossless H.264 video using FFmpeg, yielding a 1,987,425 byte MP4 file as output. The following Ruby script generates both files:

```
#!/usr/bin/env ruby
raw = 'raw.pbm'
cmp = 'compressed.mp4'
File.write(raw, 'P4 65535 1 ' + 'IE'*4994 + 'I')
system("ffmpeg -i #{raw} -crf 0 -preset ultrafast -tune film -vf format=yuv444p -frames 1 #{cmp}")
puts File.size(raw)
puts File.size(cmp)

```

The compression/quality options passed to FFmpeg are:

* `-crf 0` (constant rate factor 0). From the docs: 'You can use `-crf 0` to create a lossless video . . . Note that lossless output files will likely be huge'.
* `-preset ultrafast` 'A slower preset will provide better compression', so I chose the fastest one. (The next fastest option, `superfast`, reduces the file size more than fivefold.)
* `-tune film` Adding this option ('use for high quality movie content; lowers deblocking') increased the file size by 2 bytes.
* `-vf format=yuv444p` Adding this option (no chroma subsampling) increased the file size by 1 byte.

For comparison, with the default compression/quality settings (`ffmpeg -i raw.pbm -frames 1 compressed.mp4`) the compression ratio is 4.44558. With maximum compression and lowest quality (`ffmpeg -i raw.pbm -crf 51 -preset veryslow -frames 1 compressed.mp4`) the compression ratio is 1.4147.

### Pattern selection

Images encoded only by repetitions of one of `I`, `E`, `)`, `%`, `0x15`, or `Q` result in MP4 files that are at least 9.5 % larger than for any other byte. These six patterns all have a white:black pixel ratio of 5:3 with no two black pixels adjacent to each other. I tested all repeated permutations of these six bytes up to size six, finding that the pattern encoded by repetitions of `IE` yielded the largest file size.

One might guess that a random image would result in a larger MP4 file than a regular pattern. I have found no such image. Across 10,000 trials with images encoded by random combinations of the six bytes identified above, the maximum file size was 1,961,715 bytes (average 1,961,005). Across 10,000 trials with completely random images, the maximum file size was only 1,514,853 bytes (average 1,499,010).

---

In an older version of this answer I used `-filter:v fps=10000000` instead of `-frames 1`, resulting in a much higher compression ratio, without realising that the output contained thousands of frames (thanks to @MT0 for the comment). This seemed like an unfair advantage, as more frames containing the same image could be added to increase the file size at will.

# Answer
> 23 votes
# JPEG (4:4:4 Chroma subsampling), ~1584.35

Asking Redwolf about what the input file type for a PNG is, we hear that it's

> Any file you can get an implementation of a PNG converting program to accept.

I realized that this means we're essentially looking for a file which compresses really well in one format but really horribly in another. I initially looked for something PNG couldn't compress well but JPEG could, but I soon realized it was easier to go the other way around.

To construct my image, I started with this 8x8 pattern:

Here, horizontal rows are either full green or no green, and vertical rows are either full red or no red. PNG's two compression steps are both *perfect* for this kind of pattern. The filter uses color data from the left and top pixels, while the interlacing groups into even-dimensioned checkerboard patterns. Better yet, this means that PNG will repeat this sequence for a while with relatively small changes to file size compared to image size. My final PNG is 3840x3840:  This takes up 11,198 bytes and has a CRC-32 of 4979FF24. I converted this to a JPEG in Paint.net, with 100% quality to make sure the exact same image came out and 4:4:4 chroma subsampling so it couldn't cheat a little with the colors, and received a 17,741,541 byte file with a CRC-32 of B6B4AC7D. The overall ratio between these two files is about 1584.35.

# Answer
> 15 votes
# BSD Compress, 1.4746

Unlike `gzip`, compress doesn't check whether it would be cheaper to store an uncompressed block, so its worst case performance is much worse than `gzip`'s. If you give it a file of completely random bytes, without any patterns or redundancies to take advantage of, `compress` fails miserably.

```
python3 -c 'from numpy import random; random.seed(29597); f=open("raw_file","wb"); f.write(random.bytes(1024*10))' && cat raw_file | compress > compressed_file && wc -c *_file

```

This doesn't work on Try It Online, since the TIO shell doesn't have `compress` installed, but my Macbook has it installed by default. When I run this, I get the following file sizes:

```
15100 compressed_file
10240 raw_file

```

For a ratio of 1.474609375

# Answer
> 12 votes
# BSD Compress, 1.5721

The following Python script constructs a file which compresses worse than a random file. It continually extends the current file by a random byte, samples 20 different random choices and continues with the file which compresses the worst. Running the script took 1.5 hours on my machine, because it tries the compression on more than 200 000 different files.

I used the implementation ncompress 5.0 on Windows.

```
import random as rnd
import subprocess as sp
import numpy as np

FILE_LEN = 10 * 1024  # 10 KiB
BYTE_RANGE = 256
SAMPLES = 20

rnd.seed(0)
with open("file.txt", 'wb+') as f:
    for pos in range(FILE_LEN):
        arr = np.zeros(BYTE_RANGE, dtype=np.int_)
        random_bytes = rnd.sample(range(BYTE_RANGE), SAMPLES)
        for b in random_bytes:
            f.seek(pos)
            f.write(bytes([b]))
            f.flush()
            result = sp.run(["compress.exe", "-fc", "file.txt"],
                            capture_output=True)
            arr[b] = len(result.stdout)
        b_opt = np.argmax(arr)
        f.seek(pos)
        f.write(bytes([b_opt]))

```

Here are the stats:

`raw - 10240 Bytes`
`compressed - 16099 Bytes`

# Answer
> 7 votes
# gzip (RFC 1952), 10kb/9.976kb ≈ 1.0024057739

RFC 1952 represents the length of the name of the original file as a null-terminated string. Therefore, we can just use the following gzip of a 0-byte file with an arbitrarily long name:

```
1F 8B 08 08 A7 53 62 60 04 FF 41 41 41 41 41 41 41 41 41 41...
...41 41 41 41 41 41 00 01 00 00 FF FF 00 00 00 00 00 00 00 00

```

with enough As (0x41) to pad out our file to 10kb. Note that some header flags and settings can be modified as you please.

I'm not certain if any programs handle this correctly. After a certain length, longer than the Windows file name limit but shorter than this, 7zip declares the archive invalid, likely due to some kind of technical limitations. The Linux utility `gz` successfully returns a 0-byte file, but uses the name of the gzipped file rather than the specified name. I didn't bother to look more into it, since I'm confident that this is a valid gzip by the simple and straightforward wording of RFC 1952.

# Answer
> 6 votes
# PCX (run length encoding of images). Ratio of 12 or 1131 depending on whether using uncompressed (though stored more efficiently) or compressed via different algorithm (e.g. png)

Using the PNG attached (because imgur supported it), I go from: 4860 bytes to 5500128 bytes for a ratio of 1131.7. Using a portable bitmap file (which imgur doesn't support), I lose color but now go from actually uncompressed 12059 bytes to 1500897 bytes for a ratio of about 12. (What I had hoped to do was get it to have worst case RLE (basically: it works by storing each pixel as a 1 byte symbol but does run length encoding, but if the pixel in question is \>= 192, you have to store the run length of 1 so the parsing can determine what is a run length indicator (high 2 bits set to 1, lower 6 bits determine the run length from 0 to 63) and what is a pixel, so each pixel would require 2 bytes (and then there's the metadata)... didn't quite do that but will take this for now)

# Answer
> 3 votes
# 10196469/10240=995.74892578125

wav source https://paste.ubuntu.com/p/DfRCHqWBXC/ . There's no absolute reason the data look like this.

compress command: `ffmpeg -i a.wav b.mp3`

ffmpeg create 8kbps mp3 even for 8bps wav

---
Tags: code-challenge, compression
---


title: Pretty printing JSON

text:
# Question
Title: Pretty printing JSON
I want format a JSON string into human-readable form. A string like this:

```
'{"foo":"hello","bar":"world","c":[1,55,"bye"]}'

```

would be formatted as:

```
{
  "foo": "hello",
  "bar": "world",
  "c": [
    1,
    55,
    "bye"
  ]
}

```

**Rules:**

1. For objects and arrays properties and items should be starting in new line with indent of +2 as you see in the above mentioned example.
2. Space after colon is mandatory
3. This is `code-golf`. Shortest code in bytes wins!

please be aware that json string should be part of the answer (but we will omit that from number of bytes, example:

```
echo '{"foo":"hello","bar":"world","c":[1,55,"bye"]}'|npx json

```

will be counted as 14 bytes =\> `echo |npx json` after omitting the string

# Answer
> 3 votes
# APL (Dyalog Unicode), 18 bytes (SBCS)

Anonymous tacit prefix function.

```
⎕JSON⍠'Compact'0⍣2

```

Try it online!

`⎕JSON` is the built-in to/from JSON converter

sets options, here:

`'Compact'` is switched off (`0`)

`⍣2` does the conversion twice (JSON string to APL array, from APL array to JSON string)

# Answer
> 2 votes
# Python 3, 11 bytes

```
-mjson.tool

```

Try it online! Note that due to the way TIO works, the code goes in the command line options area and the input goes in the code area.

# Answer
> 1 votes
# JavaScript, 24 bytes

```
o=>JSON.stringify(o,0,2)

```

Try it online!

# Answer
> 1 votes
# JavaScript, ~~39~~ 35 bytes

```
s=>JSON.stringify(eval('_='+s),0,2)

```

*Saved 4 bytes thanks to Arnauld.*

```
f=
s=>JSON.stringify(eval('_='+s),0,2)

console.log(f('{"foo":"hello","bar":"world","c":[1,55,"bye"]}'))
```

# Answer
> 0 votes
# Java + Android, 41 bytes

```
s->new org.json.JSONObject(s).toString(2)

```

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


title: Print all digits of an integer

text:
# Question
Title: Print all digits of an integer
## Challenge

Given a positive integer, find the fastest way to iterate over its digits. Bytecode size doesn't matter as much as speed of execution.

## Examples

For 6875, the program would output `6 8 7 5`.

For 199182, it would output `1 9 9 1 8 2`.

For 0, it would output `0`.

# Answer
> 2 votes
# Python 3, 15 bytes (Courtesy of @Makonede)

```
print(*input())

```

Try it online!

# Python 3, 24 bytes (~0.03s)

```
print(' '.join(input()))

```

Try it online!

Should be compact and fast

# PowerShell, 23 bytes

```
("$args"|% t*y)-join' '

```

Try it online!

This dosen't deserve seperate answer

---
Tags: integer, fastest-code, fastest-algorithm
---


# Question
Title: Sample space of n consecutive coin flips
Taking a positive integer `n` as input, print the sample space of `n` consecutive coin flips. The coin is fair, with two sides `H` and `T`, each with probability `0.5`.

For example,

Input - `3`

Output -

```
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

```

**Rules**

* Standard loopholes apply
* You may print the elements out of order, but all of them should be present.
* You may use any form of output, as long as heads and tails are displayed as 'H' and 'T', and all elements are distuinguishable.

This is `code-golf`, so the shortest code in bytes wins. Good luck!

# Answer
> 3 votes
# Jelly, 4 bytes

```
⁾HTṗ

```

A monadic Link accepting a non-negative integer which yields a list of characters.

**Try it online!** (footer calls the Link and joins with newline characters)

### How?

```
⁾HTṗ - Link: integer, n
⁾HT  - list o characters = ['H', 'T']
   ṗ - (that) Cartesian power (n)

```

# Answer
> 3 votes
# Python 3, 50 bytes

```
lambda x:product(*["HT"]*x);from itertools import*

```

Try it online!

I like my recursive approach better, but unfortunately, using module built-ins is shorter lol.

# Python 3, 54 bytes

```
f=lambda x:x and[y+q for y in f(x-1)for q in"HT"]or" "

```

Try it online!

-1 byte thanks to Jonathan Allan

# Answer
> 1 votes
# Bash, 41 40 39 bytes

```
eval echo $(printf \{H,T}%.0s `seq $1`)

```

Try it online!

*-1 thanks to pxeger*

*-1 thanks to Digital Trauma*

## Alternative, also 41 bytes

```
(($1))&&f $[$1-1] $2'{H,T}'||eval echo $2

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 52 bytes

```
f=(x,a=[''])=>x?f(--x,a.flatMap(n=>[n+'H',n+'T'])):a

```

Try it online!

A pretty simple recursive approach.

# Answer
> 0 votes
# Excel, 62 bytes

```
=IF(MOD((INT(SEQUENCE(2^A1)/2^(SEQUENCE(1,A1)-1))),2),"T","H")

```

Answer is spilled into a 2^n by n array of cells. Starts to get slow around 19.

## Alternative, 65 bytes

```
=SUBSTITUTE(SUBSTITUTE(DEC2BIN(SEQUENCE(2^A1)-1,A1),1,"T"),0,"H")

```

Slightly longer and only works for n\<=10.

Spreadsheet

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


title: Summon the sevens

text:
# Question
Title: Summon the sevens
You are given a \\$3\times3\\$ square matrix where each cell is any digit between \\$0\\$ and \\$9\\$ except \\$7\\$. Your task is to figure out the *minimum* number of digits that must be replaced with \\$7\\$'s so that the sums of the digits in each row and each column are the same.

**NB:** There is no constraint whatsoever on the diagonals, so we end up with a semi-magical square.

## Examples

Here is a matrix where three digits need to be turned into \\$7\\$'s so that all sums are \\$20\\$:

$$\begin{pmatrix}8&6&6\\1&5&8\\6&9&5\end{pmatrix}\rightarrow\begin{pmatrix}\color{red}7&6&\color{red}7\\\color{red}7&5&8\\6&9&5\end{pmatrix}$$

In this one, only one digit needs to be replaced with a \\$7\\$ so that all sums are \\$13\\$:

$$\begin{pmatrix}9&2&2\\0&9&4\\4&2&9\end{pmatrix}\rightarrow\begin{pmatrix}9&2&2\\0&9&4\\4&2&\color{red}7\end{pmatrix}$$

And for this one, our only option is to replace all digits with \\$7\\$'s:

$$\begin{pmatrix}0&6&8\\3&6&1\\8&4&0\end{pmatrix}\rightarrow\begin{pmatrix}\color{red}7&\color{red}7&\color{red}7\\\color{red}7&\color{red}7&\color{red}7\\\color{red}7&\color{red}7&\color{red}7\end{pmatrix}$$

So the expected outputs for the above examples are \\$3\\$, \\$1\\$ and \\$9\\$ respectively.

## Rules

* Because the size of the matrix is fixed, you may take input as a flattened array or 9 distinct arguments.
* Because we're dealing with digits exclusively, you may also take a string of 9 characters.
* The input matrix may already fulfill the sum constraints, in which case the expected answer is \\$0\\$.
* This is .

## Test cases

```
[[9,4,3],[3,4,9],[4,8,4]] -> 0
[[5,1,3],[3,1,5],[1,2,1]] -> 1
[[3,9,6],[8,5,5],[8,4,0]] -> 2
[[5,3,5],[1,9,5],[3,3,3]] -> 2
[[8,3,0],[8,0,8],[0,8,4]] -> 3
[[1,5,2],[5,9,5],[6,5,3]] -> 4
[[3,0,8],[1,8,0],[1,3,8]] -> 4
[[3,3,0],[5,1,9],[9,9,5]] -> 5
[[2,4,5],[5,3,4],[4,4,8]] -> 6
[[3,0,3],[8,3,5],[8,3,4]] -> 9

```

# Answer
> 10 votes
# Brachylog, 29 bytes

```
∧ℕ≜.&{|∧7}ᵐ²{+ᵛS&\+ᵛS&c{7}ˢl}

```

Try it online!

Or the much faster version with the last two constraint flipped for +2 bytes:

```
∧ℕ≜.&{|∧7}ᵐ²{c{7}ˢl.&+ᵛS&\+ᵛS∧}

```

Try it online!

A problem for Brachylog is that the usual way to try the different 7s `{|∧7}²` would lead to the following search sequence:

```
[[5,3,5],[1,9,5],[3,3,3]]
[[5,3,5],[1,9,5],[3,3,7]]
[[5,3,5],[1,9,5],[3,7,3]]
[[5,3,5],[1,9,5],[3,7,7]]

```

so it would try two 7s before every possible one 7. So we could either just try them all, sort them, and be happy. Or we do something more fancy:

* `∧ℕ≜.` we try a natural number (starting with 0). This will be our output `.`. Also we label it . So instead of back-unification ("later the square has two 7s, so the output must have been 2"), we already fix the value of the output.
* `{|∧7}ᵐ²` for every value in the square: try it unmodified or replaced by a 7.
* `c{7}ˢl` all digits concatenated, with only the 7s selected, have the length equal to the output.
* `+ᵛS&\+ᵛS` the sum of each row must unify with the sum of each column.

# Answer
> 8 votes
# , ~~131~~ ~~130~~ ~~118~~ 113 bytes

*Edit: -1 byte thanks to pajonk, and -4 bytes thanks to Giuseppe, which led to another -1 byte too.*

```
function(x,`-`=rowSums,j=expand.grid(rep(list(0:1),9)))min(-j[apply(j,1,function(k)!sd(c(-t(m<-7*k+x*!k),-m))),])

```

Try it online!

**How?**
`j=expand.grid(rep(list(0:1),9))` generates a matrix `j` with 512 rows, corresponding to all possible placements of `7`s in a 9-element matrix.
We then `apply` the function `!sd(c(-t(m<-7*k+x*!k),-m))` to each row, to determine which ones would yield a semi-magic square if `7`s were placed at those positions in the input matrix `x`.
From these rows, output the minimum row sum, which was the number of `7`s we needed to place.

(Note that for golfing motives, the short `-` operator is re-assigned to the longer-named `rowSums` function to save bytes, making the code a little difficult to read...)

# Answer
> 6 votes
# Jelly, 19 bytes

```
JŒPµ³7⁸¦s3§;SEƲµƇḢL

```

Try it online!

Takes a flattened list.

Unfortunately, it's not possible to test this with all test cases at once because it uses `³`.

## Explanation

```
JŒPµ³7⁸¦s3§;SEƲµƇḢL   Main monadic link
J                     Indices ([1..9])
 ŒP                   Power set, ordered by length
                Ƈ     Filter by
   µ                  (
    ³                   The input
       ¦                At indices
      ⁸                   given by the argument,
     7                    replace the element with a 7
        s3              Split into groups of 3
              Ʋ         (
          §               Sum of each row
           ;              Join with
            S               Sum of rows (i.e. sum of each column)
             E            All equal?
              Ʋ         )
               µ      )
                 Ḣ    First element
                  L   Length

```

# Answer
> 5 votes
# Haskell, ~~157~~ ~~143~~ ~~136~~ ~~134~~ 132 bytes

```
f z=minimum[sum[1|7<-v]|v<-foldr((<*>).(:[(7:)]).(:))[[]]z,e[sum$(v!!).((4-d)*x+).(d*)<$>l|d<-[1,3],x<-l]]
l=[0..2]
e(x:z)=all(x==)z

```

Try it online!

Takes a flat list of nine numbers.

Shortened by 11 bytes thanks to ovs (143 should have been 147).

Shortened additionally by 4 bytes.

### Explanation

```
f z=minimum[sum[1|7<-v]|              -- count 7s for all solutions and take minimum
  v<-foldr((<*>).(:[(7:)]).(:))[[]]z, -- generate squares with all possible substitutions
  e                                   -- all sums must be equal
    [sum$                             -- compute sums of rows and columns
      (v!!).((4-d)*x+).(d*)<$>l|      -- transform [0..2] to index list and apply to v
        d<-[1,3],x<-l]]               -- parameters for index lists
l=[0..2]                              -- abbreviation, used in two places
e(x:z)=all(x==)z                      -- check whether all numbers in list are equal

```

# Answer
> 4 votes
# Java, ~~257~~ ~~246~~ ~~210~~ ~~200~~ ~~195~~ ~~190~~ ~~188~~ ~~186~~ 181 bytes

```
a->{int r=9,i=512,j,e,s,k,x,z,b,c=9;for(;i-->0;r=e!=0|r<c?r:c)for(j=s=e=0;j<3;s=j++<1?x:s,e|=x-s)for(k=x=c=0;k<9;z=b>0?7:a[k],x+=k/3==j?z:0,x+=k++%3==j?30*z:0)c+=b=i>>k&1;return r;}

```

*Saved 11 bytes thanks to ceilingcat.*

*Saved 46 bytes thanks to Olivier Grégoire.*

*Saved 19 bytes thanks to Donat.*

Takes a flat array as input. This method tries all 512 (29) possibilities by using the binary representations of the integers from `0` to `511`. On each iteration, it sets the values at all indexes where `i` has a set bit to `7`. Then, it checks if the current array is valid, in which case the answer is updated.

Try it online!

# Answer
> 4 votes
# Python 3.8 (pre-release), ~~159~~ ~~152~~ 140 bytes

-7 bytes thanks to Donat
-4 bytes thanks to Donat

```
lambda l:min(i.count(7)for j in range(512)if 2>len({sum((i:=[(7,L)[M<'1']for L,M in zip(l,f'{j:9b}')])[k%7::k//6])for k in[-5,6,21,22,23]}))

```

Try it online!

Takes input as a flat list. Solves by brute-forcing each possible set of 7's. When checking the sums of rows/columns, skips the last row.

```
f=lambda l:                     # l is flat list (9 elements)
  min(                          #
    i.count(7)                  # what we're trying to minimize (the number of 7's used)
    for j in range(512)         # 512=2^9
    if 2>len({                  # check if the len of the set of row/column sums is 1 (it's at least 1 for sure)
      sum(                      # get the sum of a row/column
        (i:=[(7,L)[M<'1']       # Choose the original number or 7 based on whether the binary digit is 1
                                #     (the alternative for the digit is ' ' or '0', which are both < '1')
          for L,M in zip(l,     #
            f'{j:9b}')])        # gets length 9 binary string
        [k%7::k//6])            # Slice the array to get a row or column
      for k in                  #
      [-5,6,21,22,23]}))        # corresponding slices are i[2::-1] i[6::1] i[0::3] i[1::3] i[2::3]

```

# Answer
> 3 votes
# MATL, 23 bytes

```
nW:qB!"G7@(t!hsd~?@svX<

```

Try it online! Or verify all test cases.

### Explanation

```
n         % Implicit input. Number of elements: gives 9
W         % 2 raised to that
:q        % Range, minus 1 element-wise. Gives the 1×512 vector [0 1 2 ... 511]
B!        % Binary, transpose. Gives a 9×512 matrix where each colum is the binary
          % expansion of a number in the above vector
"         % For each column, c (9×1 vector of zeros and ones)
  G       %   Push input
  7       %   Push 7
  @       %   Push current c
  (       %   Write 7 in the input at the entries specified by ones in c
  t!h     %   Duplicate, transpose, concatenate horizontally. Gives a 3×6 matrix
  s       %   Sum of each column
  d~      %   Consecutive differences, negate. Gives a 1×5 vector containing zeros
          %   and ones. If all values are one we have found a solution
  ?       %   If all entries are nonzero
    @s    %     Push c, sum. This is the number of sevens that were written
    vX<   %     Concatenate with any previous results and take the minimum
          %   End (implicit)
          % End (implicit)
          % Display (implicit)

```

# Answer
> 3 votes
# Charcoal, 48 bytes

```
Ｆφ«≔⭆θ⎇＆ιＸ²λ7κη≔⁺⪪η³Ｅ³⭆⪪η³§μκζ≦Σζ¿⁼⌈ζ⌊ζ⊞υ№η7»Ｉ⌊υ

```

Try it online! Link is to verbose version of code. Takes input as a string of 9 digits. Explanation:

```
Ｆφ«

```

Loop over all possible replacements of digits with `7`, and then some.

```
≔⭆θ⎇＆ιＸ²λ7κη

```

Get the next possible replacement of digits with `7`.

```
≔⁺⪪η³Ｅ³⭆⪪η³§μκζ

```

Split into rows and concatenate with the transpose.

```
≦Σζ

```

Sum the rows and columns.

```
¿⁼⌈ζ⌊ζ

```

If they are all the same, then...

```
⊞υ№η7

```

... save the number of `7`s.

```
»Ｉ⌊υ

```

Print the minimum number of `7`s required.

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

```
q0//.k_/;!Or@@(Equal@@Tr/@Join[w=MapAt[7&,q,#],w]&/@{1,2,3}~Tuples~{k,2}):>k+1

```

Try it online!

-30 bytes from @att

# Answer
> 2 votes
# Retina 0.8.2, 97 bytes

```
^
:
+`:(.)
$1:$%'¶$%`7:
%(`:
$`$`
6`...
$&¶
8O$#`.
$.%`
18`.
$*
)`¶
,
G`\b(1+,)\1{5}
%M`7
O`.
¶.

```

Try it online! Takes input as a string of 9 digits, but link includes test suite that splits on newlines and deletes non-digits for convenience. Explanation:

```
^
:
+`:(.)
$1:$%'¶$%`7:

```

Create all possible combinations of replacing a digit with a `7`.

```
%(`
)`

```

Process each combination separately.

```
:
$`$`

```

Triplicate the string of digits.

```
6`...
$&¶

```

Split the first two copies into rows.

```
8O$#`.
$.%`

```

Transpose the first three columns into rows.

```
18`.
$*

```

Take the sum of each column or row.

```
¶
,

```

Concatenate the results.

```
G`\b(1+,)\1{5}

```

Keep only those that are semimagic.

```
%M`7

```

Count the number of `7`s used.

```
O`.

```

Sort by number of `7`s used.

```
¶.

```

Keep only the smallest number of `7`s used.

# Answer
> 2 votes
# Pyth, 23 bytes

```
lhf!t{ssMMCBc:JQT7 3yU9

```

Test suite

Takes input as a flattened list.

Translation of xigoi's Jelly answer.

# Answer
> 2 votes
# Python 3, ~~200~~ \\$\cdots\\$ ~~183~~ 181 bytes

```
def f(a,R=range):
 for b,n in sorted((bin(i).count('1'),i)for i in R(512)):
  c=[[a[i],7][n>>i&1]for i in R(9)]
  if len({(sum(c[3*i:3*i+3]),sum(c[i:9:3]))for i in R(3)})<2:return b

```

Try it online!

Inputs a flat list of \\$9\\$ integers and returns the minimum number of elements that must be replaced with \\$7\\$s so that the sums of the rows and columns of the corresponding \\$3\times3\\$ matrix are the same.

# Answer
> 2 votes
# Ruby, ~~126 123~~ 116 bytes

```
->m{(0..510).map{|x|[120,345,678,360,147,258].map{|a|a.digits.sum{|z|x[z]>0?7:m[z]}}.uniq[1]?9:x.digits(2).sum}.min}

```

Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), ~~151~~ ~~148~~ ~~145~~ ~~142~~ 140 bytes

```
a=>{r=9;for(i=512;i--;r=e|r<c?r:c)for(j=e=0;j<3;a.map((z,k)=>x+=(i>>k&1&&++c?7:z)*(!(~~(k/3)-j)+30*!(k%3-j))),j++?e|=x-s:s=x)c=x=0;return r}

```

Try it online!

2 byte reduced thanks to Arnauld

### Explanation:

```
a=>{r=9;                 // initial value for minimum
for(i=512;i--;           // i is a bitmask for indexes to replace by 7
 r=e|r<c?r:c)            // minimum of valid squares, e is false if valid
  for(j=e=0;j<3;         // for three rows/columns
   a.map((z,k)=>         // body: compute sum(row) + 30*sum(column)
    x+=                  // current partial sum
      (i>>k&1&&++c?7:z)* // number in current cell, maybe replaced by 7
                         // ++c is always true, here only for counting 7s
      (!(~~(k/3)-j)+     // 1 for current row, else 0
       30*!(k%3-j))),    // 30 for current column, else 0
   j++?e|=x-s:s=x)       // compare sums (s is sum in first iteration)
  c=x=0;                 // initialize number of 7s and sums
return r}                // result

```

Note: We compare the sums of rows and columns only separately. But if the sums of all rows are equal and the sums of all columns are equal, they must be all equal to each other. The sum of the sums of all rows equals the sum of the sums of all columns.

# Answer
> 1 votes
# APL(Dyalog Unicode), 53 bytes SBCS

```
⌊/+/¨7=,¨a/⍨1=≢¨(∪+/,+⌿)¨a←⎕∘{3 3⍴7@(⍸⍵⊤⍨9/2)⊢⍺}¨⍳512

```

Try it on APLgolf!

A tradfn submission which takes a flat array as input from STDIN.

loops over 512 combinations and finds the minimum.

# Answer
> 1 votes
# Stax, 25 bytes

```
ü+üF∙░╔┴!╜U╙],wøT╥B╠╓l6â°

```

Run and debug it

yet another powerset answer

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

```
f=(a,m)=>[b=0,1].map(d=>a.map((r,i)=>b|=r.map((n,j)=>s+=d?n:a[j][i],s=0)|1<<s))|b&b-1&&a.map(r=>r.map((n,x)=>r[n-7&&(r[x]=7,v=f(a),v>m?0:m=v),x]=n))|m+1

```

*-8 bytes thanks to @Arnauld!*

Try it online!

Takes a matrix of numbers.

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

```
p=(m,l=0)=>(q=l=>([a,b,c,d,e,f,g,h,i]=m,l)?m.some((v,j)=>q(l-1,m[j]=7)||(m[j]=v,0)):new Set([a+b+c,d+e+f,g+h+i,a+d+g,b+e+h,c+f+i]).size<2)(l)?l:p(m,l+1)

```

Try it online!

Take input as a flatten array.

# Answer
> 1 votes
# Perl 5, 138 bytes

```
sub{(sort map{$i=$_;%e=map{//;$c=$x=$k=0;$x+=($i>>$k&1&&++$c?7:$_)*(!(~~($k/3)-$')+30*!($k++%3-$'))for@_;($x,1)}0..2;%e>1?9:$c}0..511)[0]}

```

Try it online!

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

```
lMin[Pick[#~t~2,t[w=l+7#-l#]⋃t/@w,{_}]&/@{0,1}~Tuples~{3,3}]
t=Total

```

Try it online!

Input a 3x3 matrix.

# Answer
> 1 votes
# Haskell, ~~100~~ 95 bytes

* -5 bytes thanks to Donat.

```
f m=minimum[sum[1|7<-n]|n<-g m,a$sum.(g n!!)<$>[7,56,73,146,448]]
g=mapM(:[7])
a(x:y)=all(==x)y

```

Try it online!

The relevant function is `f`, which takes the flattened matrix `m` as input as list of `Int`'s.

## How?

The real star of this answer is `g=mapM(:[7])`. What is this Haskell magic? Let's start by describing what `mapM` does. `mapM` takes as input a function `f::a->[b]` and a list `l::[a]`, applies `f` to every element of `l` (thus obtaining a list of lists `::[[b]]`), and then returns the cartesian product of these lists. To get a better intuition, consider what happens when we call `mapM(:[7])[2,3,4]`. First we apply `(:[7])` to each element of `[2,3]`, getting `[[2,7],[3,7],[4,7]]` as a result; then we take the cartesian product, resulting in

```
[[2,3,4],[2,3,7],[2,7,4],[2,7,7],[7,3,4],[7,3,7],[7,7,4],[7,7,7]]

```

It should be clear from this example that the function `g`, applied to a list `l`, returns all the lists that can be obtained from `l` by replacing some elements with a `7`. Unsurprisingly, this is exactly what we need for the first step of the solution (i.e. applying `g` to the flattened input matrix `m`); however, a bit more surprisingly, the function `g` will also come in handy later.

---

Now that we know how to *summon the sevens*, we need a way to check if the rows and columns of a given matrix all have the same sum. Dealing with row/column sums in a flattened matrix can be surprisingly cumbersome in Haskell, so we'll have to be somewhat creative. The relevant piece of code is

```
a$sum.(g n!!)<$>[7,56,73,146,448]

```

`a` is simply a function to check whether all the elements of a list are the same (defined later as `a(x:y)=all(==x)y`, not particularly exciting). The interesting part of the code is

```
a$sum.(g n!!)<$>[7,56,73,146,448]

```

, which is basically finding the sum of some specific lists in `g n` (namely, the one in position `7`, the one in position `56` and so on). What's so special about these positions? Assuming `n≡[n0,n1,...,n7,n8]`, the `7`-th element of `g n` is `[n0,n1,n2,n3,n4,n5,7,7,7]`. Similarly, here is a list of the elements of `g n` we are considering.

| `i` | `i`-th element of `g n` |
| --- | --- |
| `7` | `[n0,n1,n2,n3,n4,n5,7 ,7 ,7 ]` |
| `56` | `[n0,n1,n2,7 ,7 ,7 ,n6,n7,n8]` |
| `73` | `[n0,n1,7 ,n3,n4,7 ,n6,n7,7 ]` |
| `146` | `[n0,7 ,n2,n3,7 ,n5,n6,7 ,n8]` |
| `448` | `[7 ,7 ,7 ,n3,n4,n5,n6,n7,n8]` |

With some algebra, it's easy to see that the sums of these five lists are all equal if and only if the sums of all the rows and columns of `n` are equal.

---

Sorry, the clever part is over, the definition of `f` is moderately boring.

```
f m=                                    -- f is a function that takes a flattened matrix m
    minimum[                            -- and returns the minimum of
    sum[1|7<-n]|                        -- the numbers of 7's in n (sum 1 for each 7 in n), where
    n<-g m,                             -- n is an element of g m
    a$sum.(g n!!).fromEnum<$>"?ÛŭƶǇǸ"]  -- all the sums of rows and columns of n are equal

```

To compensate, here is a fun fact: most of the other solutions posted here have a time complexity of \\$O(2^{n^2})\\$ (up to a polynomial in \\$n\\$), while this answer runs in \\$O(4^{n^2})\\$, where \\$n\\$ is the number of rows/columns of the input matrix.

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


title: How often will this test fail?

text:
# Question
Title: How often will this test fail?
### Preamble

There was a unit test in our codebase which was shuffling a string of length \\$52\\$ formed from the set of letters \\$\[A-Z\]+\[A-Z\]\\$ and then using the first \\$20\\$ characters of that shuffled string.
It failed quite a while after being written due to no repeated character being present in those twenty and we wondered how often such a test would be likely to fail. (A little more than one in five hundred and twenty-two times it turns out).

### Challenge

Given an alphabet size (\\$a\\$), a number (\\$n\\$) of occurrences of each letter, and a prefix length (\\$p\\$), output the probability that a (uniformly chosen) random permutation of the \\$a\times n\\$ letters begins with \\$p\\$ distinct letters.

You may assume that:

* There will be enough letters to make the prefix: \\$p \le n\times a\\$
* Each of the three inputs will be non-negative integers: \\$p,n,a\in\Bbb{Z}\_{\ge 0}\\$

Output in any reasonable format - e.g. a float, a fraction, a pair containing the numerator and denominator (no requirement to simplify); if you're unsure, just ask!

### Potential method

This is the method we used to calculate the result we were interested in (from the preamble).

If one thinks of the \\$n\times a\\$ elements as a bag from which one repeatedly picks the next element of the prefix, then the probability of extending the prefix by one element such that it remains fully distinct is the number of elements remaining in the bag which do not yet appear in the prefix divided by the total number of elements remaining in the bag. As such the probability that the final length \\$p\\$ prefix will be fully distinct is the product of these probabilities starting with a full bag and an empty prefix:

$$ \prod\_{i=0}^{p-1}\frac{n\times(a-i)}{n\times a-i} $$

### Test cases

Floating point inaccuracy is acceptable; fractions, if used, do not need to be in simplest form.
Ideally these test cases will all be runnable in a reasonable amount of time, but if golf means crazy inefficiency so be it!

```
 a   n   p    output                          (as a fraction)
 2   1   0    1                               (1/1)
 2   1   1    1                               (1/1)
 2   1   2    1                               (1/1)
50   1  50    1                               (1/1)
 3   2   0    1                               (1/1)
 3   2   1    1                               (1/1)
 3   2   2    0.8                             (4/5)
 3   2   3    0.4                             (2/5)
 3   2   4    0                               (0/1)
26   2   0    1                               (1/1)
26   2   1    1                               (1/1)
26   2   2    0.9803921568627451              (50/51)
26   2  13    0.13417306435734888             (77824/580027)
26   2  20    0.001916063061695329            (2097152/1094510949)
32   8  11    0.1777403166811693              (31138512896/175191051065)
32   8  22    0.00014139946994082153          (3477211257894250479616/24591402353555723779476075)
32   8  33    0                               (0/1)

```

# Answer
# Wolfram Language (Mathematica), 32 bytes

```
#3~b~#/b[#2#3,#]#2^#&
b=Binomial

```

Try it online!

Input `[p, n, a]`.

The formula can be rewritten \\$\dfrac{a\choose p}{an\choose p}n^p\\$.

---

Incidentally, this is fairly trivial using Mathematica's statistics built-ins:

### Wolfram Language (Mathematica), 69 bytes

```
CDF[MultivariateHypergeometricDistribution[#~Max~1,a=Table@##2],1^a]&

```

Try it online!

Unfortunately, 38-character name aside (the longest name in the default namespace), `MultivariateHypergeometricDistribution` doesn't handle a nonpositive prefix length, and overall this approach is quite slow for this particular problem.
> 6 votes

# Answer
# Haskell, ~~41~~ 40 bytes

```
(a#n)p|p<1=1|i<-p-1=(a-i)/(a-i/n)*(a#n)i

```

Try it online!

Someone's got to post the trivial solution, right? ...Right?

The only reason I don't feel too ashamed is that I managed to save 2 bytes by using the formula `(a-i)/(a-i/n)` instead of the more obvious `n*(a-i)/(n*a-i)`
> 5 votes

# Answer
# Jelly, 9 bytes

```
×\c÷/×Ṫ*¥

```

Try it online!

Uses att's formula. Takes `[a, n]` on the left and `p` on the right

Uses the formula

$$\frac {\binom a p} {\binom {an} p} n^p$$

Unfortunately, the more elegant version of this formula

$$\frac {a!} {(an)!} \frac {(an - p)!} {(a - p)!} n^p$$

takes a lot more bytes in Jelly due to its poor handling of 3 variables

## How it works

```
×\c÷/×Ṫ*¥ - Main link. Takes [a, n] on the left and p on the right
×\        - Scan multiply. Yield [a, a×n]
  c       - Binomial with p. Yield [aCp, (a×n)Cp]
   ÷/     - Reduce by division; aCp ÷ (a×n)Cp
        ¥ - Previous 2 links as a dyad f([a, n], p):
      Ṫ   -   Extract n
       *  - Raise it to the power p
     ×    - Multiply aCp ÷ (a×n)Cp by nᵖ

```
> 5 votes

# Answer
# Python 3, ~~48~~ 47 bytes

Saved a byte thanks to xnor!!!

```
f=lambda a,n,p:p<1or(p+~a)/(~-p/n-a)*f(a,n,~-p)

```

Try it online!

Straightforward calculation of the given formula. Returns either a float or an int or `True` (for \\$1\\$).
> 3 votes

# Answer
# Excel, 48 bytes

```
=IFERROR(COMBIN(A2,C2)*B2^C2/COMBIN(A2*B2,C2),0)

```

Using att's formula. 37 bytes if an error is acceptable when p \> a.

Spreadsheet
> 3 votes

# Answer
# JavaScript (ES6), 35 bytes

A trivial recursive function expecting `(a)(n)(p)`. May return **true** instead of **1**.

```
a=>n=>g=p=>!p--||(a-p)/(a-p/n)*g(p)

```

Try it online!

### Commented

```
a =>            // 1st function taking a
n =>            // 2nd function taking n
g = p =>        // 3rd recursive function taking p
  !p-- ||       //   if p = 0, stop and yield true (coerced to 1)
                //   (decrement p afterwards)
                //   otherwise:
  (a - p) /     //     compute (a - p) / (a - p / n)
  (a - p / n) * //     (same formula as Delfad0r)
  g(p)          //     and multiply by the result of a recursive call

```
> 2 votes

# Answer
# C (gcc), ~~66~~ ~~59~~ 54 bytes

```
f(a,n,p,r)float*r,n;{for(*r=1;p--;)*r*=(a-p)/(a-p/n);}

```

Try it online!

Calculates the given formula. Returns a `float` through its last parameter (which is a pointer to an uninitialized float).
> 1 votes

# Answer
# Retina, ~~116~~ 114 bytes

```
.+,(.+),
*_,$'*$1*_,$1*_,
["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)
$.($4*$3)/$.2
+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

```

Try it online! Link includes test cases. Takes input in the order `p,a,n`. Explanation:

```
.*,(.*),
*_,$'*$1*_,$1*_,

```

Convert `p`, `na` and `a` to unary.

```
["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)

```

Loop `i` from the maximum of `a` and `p-1` down to `0`, also prefix a dummy `1/1` fraction in case `p` is `0`. Calculate `na-i` and `a-i`. (If `p>a`, there will always be an entry where `i=a` so the final result is zero anyway.)

```
$.($4*$3)/$.2

```

Create the fraction `n(a-i)/(na-i)` in decimal.

```
+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

```

Multiply all of the fractions together.

Previous 116-byte solution:

```
\d+,
*_,
["1/1¶"Lv$`_(_*),(_*),(.+)
$3*$1,$3*$2/$1,$3*$2
+`_,_
,
+`(/.+)¶(.+)/
$2$1
_*,(_*)
,$.1
+`\d+,(\d+)
$.($1**

```

Try it online! Link includes test suite that reduces the output fraction to its lowest terms. Takes input in the order `p,a,n`. Explanation:

```
\d+,
*_,

```

Convert `p` and `a` to unary.

```
["1/1¶"Lv$`_(_*),(_*),(.+)

```

Loop `i` from `p-1` down to `0`, also prefix a dummy `1/1` fraction in case `p` is `0`.

```
$3*$1,$3*$2/$1,$3*$2

```

Start calculating `(na-ni)/(na-i)`.

```
+`_,_
,

```

Perform the subtractions.

```
+`(/.+)¶(.+)/
$2$1

```

Collect all the numerators and denominators together.

```
_*,(_*)
,$.1

```

Convert all the positive values to decimal. (Other values are converted to zero, but there is always at least one zero if there are any negative values, so extra zeros makes no difference.)

```
+`\d+,(\d+)
$.($1**

```

Take the products of all the numerators and denominators.
> 1 votes

---
Tags: code-golf, combinatorics
---


title: Un-pipe an Elixir expression

text:
# Question
Title: Un-pipe an Elixir expression
Elixir is a programming language with a feature called the pipe operator, `|>`, similar to the pipe in Bash and other languages. It passes the result of an expression on the left as the first parameter of a given function on the right.

To clarify, here are some examples.

```
2 |> myFunction()

```

is equivalent to

```
myFunction(2)

```

Here, the expression `2` is passed as the first parameter of the function `myFunction()`.

Now, consider how an expression with multiple pipes is evaluated. Multiple pipes are evaluated left to right, so all of these lines are equivalent:

```
other_function() |> new_function() |> baz() |> bar() |> foo()
new_function(other_function()) |> baz() |> bar() |> foo()
baz(new_function(other_function())) |> bar() |> foo()
bar(baz(new_function(other_function()))) |> foo()
foo(bar(baz(new_function(other_function()))))

```

Here, in each line the leftmost pipe is calculated, which takes the first expression and passes it to the second expression (which is a function).

## Challenge

Your challenge will be to write a program or function which, when given an Elixir expression with one or more pipes, will return or output an equivalent expression with no pipes. In real Elixir code the functions may have multiple parameters but to keep this challenge simpler, you may assume all functions will take only one parameter.

## Examples

```
Input                                                       -> Output
2 |> myFunction()                                           -> myFunction(2)
otherfunction() |> newfunction() |> baz() |> bar() |> foo() -> foo(bar(baz(newfunction(otherfunction()))))

```

## Rules

* Function names will only contain ASCII letters and underscores, and end in `()`
* The leftmost expression will only contain alphanumeric ASCII, underscores, and parentheses
* You may assume there is no whitespace in the input (the examples here have spaces for readability)
* You may also assume there are spaces surrounding the pipe operators like in the examples, if you wish
* All functions only take one parameter
* Leading or trailing whitespace is allowed in output
* Whitespace around parentheses is allowed in output
* Any reasonable form of input/output is allowed
* No standard loopholes
* Shortest code in bytes for each language wins

# Answer
> 12 votes
# , ~~23~~ 22 bytes

```
(];/:')'=;)&|._2{.\cut

```

Try it online!

```
                    cut    split by space
               _2{.\       only odds
             |.            reverse
   ;/:')'=;                join and sort by equality with ')'

```

# Answer
> 9 votes
# Stax, 8 bytes

```
ßN¶e╣╨j,

```

Run and debug it

## Explanation(unpacked)

```
.|>/kNas++
.|>/       split the string on "|>"
    k      reduce the list by:
     N     push the 2nd string with the last element popped, then push the last element
      a    put the previous iteration on top of the stack
       s   swap the bracket with the prev iteration
        ++ concatenate into one string

```

# Answer
> 8 votes
# Excel VBA (Immediate Window), ~~85~~ 75 bytes

*-10 bytes thanks to @TaylorScott*

```
For Each s In Split([A1],"|>"):o=IIf(o="",s,Left(s,len(s)-1)+o+")"):Next:?o

```

## Excel, ~~165~~ 154 bytes

*-11 bytes rethought the Excel based on changes to VBA*

```
=LET(x,FILTERXML("<a><b>"&SUBSTITUTE(A1,"|>","</b><b>")&"</b></a>","//b"),n,ROWS(x),a,n+1-SEQUENCE(n),CONCAT(INDEX(LEFT(x,LEN(x)-(a<n)),a),REPT(")",n-1)))

```

Spreadsheet

```
=LET(                                                 'define variables
                                                          return last parameter
    "<a><b>"&SUBSTITUTE(A1,"|>","</b><b>")&"</b></a>" 'Convert piped string to XML
x,FILTERXML(                                  ,"//b") 'x = XML converted to array
n,ROWS(x)                                             'n = # rows in x
a,n+1-SEQUENCE(n)                                     'a = n .. 1
CONCAT(INDEX(LEFT(x,LEN(x)-(a<n)),a),REPT(")",n-1))   'final calculation
       INDEX(                    ,a)                  'x in reverse order
             LEFT(x,LEN(x)-(a<n))                     'if not first element delete
                                                          rightmost char
                                     REPT(")",n-1)    'n-1 ")"
CONCAT(                                           )   'concatenate everything

```

## Original

```
=LET(s,SUBSTITUTE(A7,")",""),x,FILTERXML("<a><b>"&SUBSTITUTE(s,"|>","</b><b>")&"</b></a>","//b"),n,ROWS(x),CONCAT(INDEX(x,n+1-SEQUENCE(n)),REPT(")",LEN(A7)-LEN(s))))

```

# Answer
> 7 votes
# Jelly, ~~11~~ 9 bytes

```
Ḳm2ɓṪṭ;µ/

```

Try it online!

-2 bytes thanks to Jonathan Allan!

The `|>` must be surrounded by spaces

## How it works

```
Ḳm2ɓṪṭ;µ/ - Main link. Takes a string S on the left
Ḳ         - Split S on spaces
 m2       - Take every second element, ignoring the "|>" elements
   ɓ   µ  - Create a new dyadic chain f(a, b):
    Ṫ     -   Remove the trailing ")" from a and yield it
      ;   -   Concatenate the modified a and b
     ṭ    -    Tack the ")" to the end
        / - Reduce the split S by this. The ɓ in the chain tells
             the quick to reduce from the left with arguments reversed

```

# Answer
> 7 votes
# SNOBOL4 (CSNOBOL4), ~~105~~ ~~98~~ ~~87~~ 78 bytes

```
	I =INPUT
S	I ARB . L '|>' ARB . F ')' REM . R =F L ')' R	:S(S)
	OUTPUT =I
END

```

Try it online!

Thanks to Razetime for -2 bytes.

### Explanation:

```
	I =INPUT	;* read input, assign to I
S			;* label S
	I [lhs] = [rhs]	;* replace the part of I matching the following pattern:
	ARB . L '|>'	;* something followed by '|>' (assign to L)
	ARB . F ')'	;* followed by something followed by a ')' (assign to F)
	REM . R		;* and the rest of the string (assign to R)
			;* with:
	F L ')' R	;* F, L, ')', and R concatenated together
		:S(S)	;* on SUCCESS (a match was found), goto S
	OUTPUT =I	;* on FAILURE, proceed to output and end the program
END

```

# Answer
> 5 votes
# Elixir, 64 bytes

```
&Macro.to_string Macro.expand Code.string_to_quoted!(&1),__ENV__

```

Try it online!

Well, this looks a bit longish for a solution relying on built-in functionality, but I guess we need a "reference" implementation with Elixir doing it itself.

# Answer
> 5 votes
# , ~~94~~ ~~92~~ 86 bytes

*Edit: -2 bytes thanks to Giuseppe*

```
function(s,t=el(strsplit(s,"[)]?(.>|$)")))Reduce(paste,c(rev(t),")"[+grepl("[(]",t)]))

```

Try it online!

# Answer
> 5 votes
# Retina 0.8.2, ~~30~~ ~~23~~ 22 bytes

```
+`^(.+?).>(.+?\()
$2$1

```

Try it online! Link includes test cases. Edit: Saved ~~7~~ 8 bytes thanks to @tsh. Explanation:

```
+`

```

Repeat until all pipes have been processed.

```
+`^(.+?).>(.+?\()

```

Match the first two terms up to the second term's opening bracket.

```
$2$1

```

Move the first term into the second term's argument.

# Answer
> 4 votes
# JavaScript (Node.js), 60 bytes

```
s=>s.match(/\w+\(?/g).reverse().join``+s.match(/\)/g).join``

```

Try it online!

This would fail if there were no pipes (not possible according to challenge rules) but here's an alternative version which can also handle that:

## JavaScript (Node.js), 61 bytes

```
s=>(f=a=>a[1]?a.pop().slice(0,-1)+f(a)+')':a[0])(s.split`|>`)

```

Try it online!

# Answer
> 4 votes
# Charcoal, 20 bytes

```
≔⪪Ｓ|>θ⭆⮌θ…ι⊖Ｌι⭆θ✂ι±¹

```

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

```
≔⪪Ｓ|>θ

```

Split the input on `|>`.

```
⭆⮌θ…ι⊖Ｌι

```

Print the strings in reverse order without their last character.

```
⭆θ✂ι±¹

```

Print the last characters of the strings. This means that the first term gets reunited, while the remaining terms have their brackets moved to the end.

# Answer
> 4 votes
# Python 2, 54 bytes

```
lambda s:reduce(lambda r,x:x[:-1]+r+')',s.split('|>'))

```

Try it online!

For each function going to left to right, insert the string `r` we have so far between the parens of the function `x`.

```
string |> new_function() = new_function(string)

```

This is done by removing the last character (a close paren), appending the string, then adding back the close paren. Because `reduce` starts the accumulator at the first element by default, we don't need any special handling if it's not a function.

This is longer in Python 3, which lacks `reduce` but can use a starred assignment to extract the initial value.

**Python 3, 59 bytes**

```
r,*l=input().split('|>')
for x in l:r=x[:-1]+r+')'
print(r)

```

Try it online!

Alternatively:

**Python 3, 59 bytes**

```
r=''
for x in input().split('|>'):r=x[:-1]+r+x[-1]
print(r)

```

Try it online!

# Answer
> 3 votes
# Zsh, 41 bytes

```
for a (${(s:|>:)1})x=${a//\()/($x)}
<<<$x

```

Try it online!

* `${1}` \- take the input
* `(s:|>:)` \- split on `|>`
* `for a ()` \- for each element:
    + `${a}` \- take the element
    + `///` \- replace:
        - `\()` \- empty parentheses
        - `($x)` \- with the current value of `$x`, in more parentheses
    + `x=` and assign that to `$x` (it starts as an empty string by default)
* `<<<$x` \- print `$x`

# Answer
> 3 votes
# Jelly, 9 bytes

Port of FrownyFrog's clever J answer!

```
Ḳm2ṚF=Þ”)

```

A monadic Link accepting and yielding a list of characters (with the `|>` surrounded by a space on each side like the examples).

**Try it online!**

### How?

```
Ḳm2ṚF=Þ”) - Link: list of characters, S
Ḳ         - split at spaces
 m2       - modulo-2 slice [1st, 3rd, 5th, ...]
   Ṛ      - reverse
    F     - flatten
      Þ   - sort by:
     = ”) -   equals ')'?

```

# Answer
> 3 votes
# C (gcc), 90 bytes

```
f(s,l,t)char*s;{for(t=0;--l&&s[l-1]-62;t++);s=printf("%.*s",t+!l,s+l)-t||f(")",f(s,l-2));}

```

Try it online!

Expects no spacing.

# Answer
> 3 votes
# V (vim), 11 bytes

```
òf|xxd0f(pò

```

Try it online!

ò…ò repeats the commands until the first error, the rest are normal Vim commands.

# Answer
> 2 votes
# Java, ~~103~~ ~~84~~ ~~80~~ 77 bytes

```
s->{var p="";for(var c:s.split("\\|>"))p=c.replace("()","("+p+")");return p;}

```

*Saved 19 bytes thanks to 79037662.*

*Saved 4 bytes thanks to pxeger.*

Try it online!

A positive lookahead can be used for a solution of the same length.

```
s->{var p="";for(var c:s.split("\\|>"))p=c.replaceAll("(?=\\))",p);return p;}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 13 bytes

```
„|>¡Å»¨ì')«}θ

```

Try it online! The annoying thing here is  only reduces by the first command after it, not a `}` or `]`-terminated function. And macros don't exist, so… ¯\\\_(ツ)\_/¯

```
„|>¡Å»¨ì')«}θ  # full program
            θ  # last element of...
    Å»         # cumulatively reduced...
               # implicit input...
   ¡           # split by...
„|>            # literal...
     »         # to the right by...
        ')     # literal...
          «    # concatenated to...
      ¨        # all characters of...
               # (implicit) second element in current reduction step...
      ¨        # excluding the last...
       ì       # prepended to...
               # (implicit) first element in current reduction step
           }   # end cumulative reduce
               # implicit output

```

`')` can also be , , or `¹θ`, `}` can also be `]`, and `θ` (only the one at the end) can be `¤` with no change in functionality.

# Answer
> 2 votes
# PowerShell Core, 81 bytes

```
-join($t=$args|% Sp* "|>"|% *m ')')[($l=$t.Count)..0]+")"*($l-!($t[0]|% e*h '('))

```

Try it online!

Thanks to @Julian!

# PowerShell, 108 bytes

```
param($s)$n=$s.split("|>");$k=(($n|%{$n[--$q]})|%{$_-replace"\)$"})-join"";$k+")"*($k-replace"[^\(]").length

```

Try it online!

* Take a string
* Split it by `|>`
* Save ^ to an array
* Reverse the array
* Loop on each element
* Remove trailing `)`
* Join array
* Append number of `(` in the joined string amount `)`
* Print and bye bye!

# Answer
> 2 votes
# JavaScript (Node.js), 49 bytes

```
f=a=>a.replace(/(.*).>(.*)./,(_,x,y)=>y+f(x)+')')

```

Try it online!

Only works if no extra spaces are there.

---

# JavaScript (Node.js), 50 bytes

```
a=>a.split`|>`.reduce((p,q)=>q.replace('(','('+p))

```

Try it online!

This works if the input does not contais `"$"` character. Otherwise, `'('+` need to be replaced by `x=>x+` with +1 byte cost.

# Answer
> 2 votes
# Red, 85 bytes

```
func[s][t: take s: split s"|>"forall s[t: rejoin[replace s/1"()"""mold to-paren t]]t]

```

Try it online!

# Answer
> 2 votes
# PowerShell Core, ~~67~~ ~~57~~ ~~45~~ 44 bytes

```
$args-split'.>'|%{$r=$_|% rep* '(' "($r"}
$r

```

Try it online!

The `rep*` is the shortcut for the `replace` method.

# Answer
> 2 votes
# Python 3, 84 79 bytes

```
import re;r=re.findall;i=input()
print(''.join(r('[\w(]+',i)[::-1]+r('\)*',i)))

```

Try it online!

* Seems to be a complete solution: works whether there are spaces around the functions/constants/pipes or not, works whether first position contains constant or function.
* Doesn't technically look for pipes, so you could replace |\> with |\< and it would return the same output. Could add a positive lookforward to the regex but that would eat another ~10 bytes and the contest didn't specify.
* Pays a 27-byte 22-byte penalty just for importing one regex method. Thanks Python.
* Edited for small improvement.

# Answer
> 1 votes
# Japt, ~~15~~ 12 bytes

```
q"|>" rÏiXJÉ

```

Try it

* saved 3 by assuming no whitespaces as suggested by OP @79037662

```
 q"|>"    - split on pipe
 r        - reduce by
 ÏiXJÉ    - inserting before )
```

# Answer
> 1 votes
# Python 3, 70 bytes

```
*a,b=input().split("|>")[::-1]
print(*[f[:-1]for f in a],b,")"*len(a))

```

The program first `split`s the `input` into a list using the pipe operator, `"|>"`, as the separator. Using multiple assignment, `b` is set equal to the last element of the list (previously the first element prior to being reversed). `b` contains a string of the first element in the pipe, which may or may not be a function. The rest of the list is assigned to `a`. All of the elements of `a` are strings of functions. Next, the program outputs all the elements of `a` with `)` removed from each, `b`, and `")"*len(a)`.

Try it online!

If we're allowed to require that only the first item in the pipe has a space after it, but none of others, we can save **1 byte**.

# 69 bytes

```
a=input().split("|>")[::-1]
print(*[f[:-1]for f in a],")"*(len(a)-1))

```

Try it online!

# Answer
> 1 votes
# Pyth, 13 bytes

```
.UXtlZZbcQ"|>

```

Test suite

---

Explanation:

```
.U      cQ"|> | Reduce the input split at "|>" on the following lambda, where b is the current value and Z is the next item:
  XtlZZb      |  Insert b into Z at index len(Z)-1

```

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

```
#//.{a__,"|",_,b__,"(",c___}:>{b,"(",a,c}&

```

Try it online!

Takes and returns a list of characters. Requires no spacing.

# Answer
> 1 votes
# Twue, 123 bytes

```
@::>*
^()::=()!
^_ ::=_ !
^_::=_^
!()::=!
!_::=_!
$!::=$;
 |> $;::= $#(;%
##_::~_
 $#::= $##
 $::=$
_$::=$#_
%::~)
::=
^ @$
```

Try it on the website!

---

Twue is a spiritual successor to Thue I made. I initially tried answering this challenge in Thue, and had to manually describe moving each character one byte to the left, individually, so the byte count came out to ~1kb. Then, I realize I didn't properly handle constants and abandoned the code, not wanting to rewrite that mess from scratch. Enter Twue, which allows wildcards to be used (`_`) to refer to generic characters. Furthermore, it removes the random rule selection from the language, and creates a better standard for input/output.

The language is still a bit of a work in progress, but most of the bugs have been ironed out, and most of the spec has been implemented.

## Explanation

```
@::>*

```

This replaces all `@` in the workspace with a line of input. Basically: readline. For an input of `1234 |> foo() |> bar()`, this populates the workspace with:

```
^ 1234 |> foo() |> bar()$

```

`^` and `$` are characters we'll be using as pointers, of sorts, for iterating forward and backward through the code.

```
^()::=()!
^_ ::=_ !
^_::=_^

```

This section moves the `^` pointer after the first expression, which may or may not contain parentheses. We want to preserve these. This inserts `!` after the first expression, and we are ready to parse.

```
!()::=!
!_::=_!
$!::=$;!

```

Now, for every expression afterwards, we want to strip the `()` from it. So, we move `!` character by character through the input, removing `()` in front of it as we go. After these steps, the input will look like this:

```
 1234 |> foo |> bar$;!

```

Now we are ready for the second stage of parsing. We will use `!` later in the final stages of printing. Now, we have two pointers, `$` and `;`, which will define the range we're operating on.

```
 |> $;::= $#(;%
##_::~_
 $#::= $##
 $::=$
_$::=$#_

```

`_$::=$#_` simply moves every character in front of a `$` after it, prepending a `#` to it. This signifies we want to print that character. We repeat this until the `$` pointer is at the leftmost part of the word, after a space. Since we are at the beginning of the word, we start printing the characters after `$#`, by first duplicating the `#`, and printing the character after `#__`. This allows us to only print when we want to—if we didn't duplicate, we'd print the strings in reverse, or lose track of the `$` pointer. If we find the string `|> $;`, we've printed all the characters we could, and we still have more things to parse. We remove the `|>` and append a `%`, signifying we need to print a corresponding closing parenthesis.

These replacements repeat until they can't anymore.

```
%::~)

```

If there are no other substitutions we can possibly make, we simply take each `%` and output a corresponding `)`.

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