title: Finding Factorials with Gamma

text:
# Question
Title: Finding Factorials with Gamma
# Introduction

We know that the factorial notation is valid for all natural numbers. However, Euler had extended it for all positive real numbers, as well as for complex numbers by defining a function, which is known as the Gamma Function. It is represented by Γ.

# Challenge

You will be given a non-negative floating point number, say 'n' (with a maximum of 2 decimal places in it), and you need to output the factorial of that number correct to at least 3 decimal places. Assume all inputs to be valid, and n \<= 7.

Now talking about Gamma function, there is an integral which can be used to find the value of any factorial. You may choose to use it. You can find more information here. The Gamma function is recursive in nature. One important property, which would probably be useful to you is:

Γ(n) = (n-1)! , which means that, n! = Γ(n) . n

Also note that we really do not need to know Γ(n) for all values of n. For instance, look at the number 4.5 - we can write its factorial as:

```
4.5! = 4.5 * 3.5 * 2.5 * 1.5 * 0.5! = 59.0625 * 0.5!

```

So here we need only the value of 0.5! , which means the value of Γ(1.5). Also, similarly, we can find the factorial of any decimal if we know the values of factorials of numbers between 0 and 1, i.e, values of gamma function of numbers between 1 and 2. You need it, so that is why there is a table below for your help:

Using this table, we can see that 0.5!, i.e, the value of Γ(1.5) = 0.88623, which gives our result: (4.5)! = 59.0625 * 0.88623 = 52.3429594 , which is indeed a good result. Similarly,

```
(5.7)! = (5.7)*(4.7)*(3.7)*(2.7)*(1.7)*(0.7)! = 454.97457 * 0.90864 = 413.408093

```

Also, if you do not wish to use the table for calculating the gamma function, here is a simple integral to help you out:

Remember that you can provide your answers only up to 3 decimal places if you want to. But the value should have minimum error. Like, +- 0.003 is acceptable.

You are free to decide in what way you want to compute the factorial - whether by the integral, or by the table, or using any other method.

# Examples

Please note that here the answer is correct to 3 decimal places.

```
2.4 -> 2.981
3.9 -> 20.667
2.59 -> 3.675
1.7 -> 1.545
0.5 -> 0.886

```

# Scoring

This is , so the shortest code wins!

# Answer
# Community wiki for built-in solutions

This answer is intended to collect answers that are simply built-ins. It's a community wiki, so anybody can edit in without approval. Go ahead and include any **built-in only** solution here, following xnor's proposal and according to our consensus.

## Jelly, 1 byte

```
!

```

Try it online!

## , 1 byte

```
!

```

Try it online!

## 2sable, 1 byte

```
!

```

Try it online!

## Pyth, 2 bytes

```
.!

```

Try it online!

## , 9 bytes

```
factorial

```

Try it online!

## Stax, 2 bytes

```
|F

```

Try and debug online!

## Wolfram Language (Mathematica), 3 bytes

```
#!&

```

Try it online!
> 1 votes

# Answer
# Perl 5, `-p` 40 bytes

Very slow. One run takes about 13 minutes for me.

```
#!/usr/bin/perl -p
$\=5e8**++$_/$_;$\/=1+$'/$_ for//..5e8}{

```

Try it online!

The TIO link uses `1e7` instead of `5e8` to avoid timeouts and is therefore not accurate enough

# Old version, `-p` 60 bytes, not accurate enough

Uses a Stirling approximation. But even with the first correction term that is pretty inaccurate for small n. So instead I approximate `(n+2)!/(n+2)/(n+1)`.

Notice that I don't bother trying to get the first 3 digits right, but the relative error seems to properly be `< 0.001` in the range `[0, 7]`. E.g. `0!` outputs `0.999481433067179` which would be `1.000` if rounded to 3 digits.

```
#!/usr/bin/perl -p
$_=(($_+=2)/exp 1)**$_*(2+1/6/$_)/$_/($_-1)*sqrt$_*atan2 1,0

```

Try it online!
> 1 votes

# Answer
# APL (Dyalog Unicode), 1 byte

```
!

```

Try it online!

In APL, the factorial primitive has always included the entire domain of the gamma function.
> 0 votes

---
Tags: code-golf, number, factorial, floating-point
---


# Question
Title: Random Golf of the Day #4: The Bertrand Paradox
# About the Series

First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

# Hole 4: The Bertrand Paradox

The Bertrand paradox is an interesting problem, which shows how different methods for picking random chords in a circle can yield different distributions of chords, their midpoints and their lengths.

In this challenge you are supposed to generate random chords of the unit circle, using the "right" method, i.e. one which produces a distribution of chords which is invariant under scaling and translation. In the linked Wikipedia article, "Method 2" is such a method.

Here are the exact rules:

* You should take **one positive integer `N`** which specifies how many chords should be returned. The output should be a list of `N` chords, each specified as two points on the unit circle, given by their polar angle in radians.
* Your code should **be able to return at least 220 different values for each of the two angles**. If your available RNG has a smaller range, you must either first build an RNG with a sufficiently large range on top of the built-in one or you must implement your own suitable RNG. This page may be helpful for that.
* The distribution of chords must be indistinguishable from the one produced by "Method 2" in the linked Wikipedia article. If you implement a different algorithm to choose chords, please include a proof of correctness. Whatever algorithm you choose to implement, it must **theoretically be able to generate any valid chord in the unit circle** (barring limitations of the underlying PRNG or limited-precision data types).
* Your implementation should use and return either **floating-point numbers (at least 32 bits wide)** or **fixed-point numbers (at least 24 bits wide)** and all arithmetic operations should be accurate within at most 16 ulp.

You may write a full program or a function and take input via STDIN (or closest alternative), command-line argument or function argument and produce output via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be in any convenient list or string format, as long as the individual numbers are clearly distinguishable and their total number is always even.

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

## Visualisation

You can use the following snippet to render the generated lines and inspect their distribution. Simply paste a list of pairs of angles into the text area. The snippet should be able to handle almost any list format, as long as the numbers are simple decimal numbers (no scientific notation). I recommend you use at least 1000 lines to get a good idea of the distribution. I've also provided some example data for the different methods presented in the article below.

```
function draw() {
  document.getElementById("output").innerHTML = svg
}

function drawLines() {
  lines = document.getElementById("lines").value;
  var e = prefix;
  //e += '<circle cx="' + offset + '" + cy="' + offset + '" r="' + radius + '" stroke="black" fill="white"/>';
  lines = lines.match(/-?(?:\d*\.\d+|\d+\.\d*|\d+(?!\.))/g);
  for (i = 0; i < lines.length; i+=2)
  {
    t1 = parseFloat(lines[i]);
    t2 = parseFloat(lines[i+1]);
    x1 = Math.cos(t1);
    y1 = Math.sin(t1);
    x2 = Math.cos(t2);
    y2 = Math.sin(t2);
    e += '<path stroke="black" stroke-opacity="0.2" d="M ' + (x1 * radius + offset) + ' ' + (y1 * radius + offset) + ' L ' + (x2 * radius + offset) + ' ' + (y2 * radius + offset) + '"/>';
  }
  e += suffix;
  svg = e;
  draw();
}
var prefix = '<svg height="450" width="450">',
  suffix = "</svg>",
  scale = 0.95,
  offset = 225,
  radius = scale*offset,
  svg = "";
```

```
svg {
  position: absolute;
}
```

```
Paste line specifications here
<br>
<input id="lines" type="textarea" size="60" oninput='drawLines()' />
<br>
<br>
<div id="output"></div>
```

*Example data generated with method 1.*

*Example data generated with **method 2.***

*Example data generated with method 3.*

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

*(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)*

# Answer
# IA-32 machine code, 54 bytes

Hexdump of the code:

```
68 00 00 00 4f 0f c7 f0 50 db 04 24 58 d8 34 24
f7 d9 78 f1 d9 c0 dc c8 d9 e8 de e1 d9 fa d9 c9
d9 f3 dc c0 d9 eb de ca d8 c1 dd 1a dd 5a 08 83
c2 10 e2 d1 58 c3

```

It uses a (slightly modified) algorithm that Wikipedia described. In pseudo-code:

```
x = rand_uniform(-1, 1)
y = rand_uniform(-1, 1)
output2 = pi * y
output1 = output2 + 2 * acos(x)

```

I use the range `-1...1` because it's easy to make random numbers in this range: the `rdrand` instruction generates an integer between `-2^31` and `2^31-1`, which can be easily divided by 2^31.

I should have used the range `0...1` for the other random number (x), which is fed into `acos`; however, the negative part is symmetric with the positive part - negative numbers produce chords whose span is greater than pi radians, but for the purpose of illustrating the Bertrand paradox, it doesn't matter.

Since the 80386 (or x87) instruction set doesn't have a dedicated `acos` instruction, I had to express the calculation using only the `atan` instruction:

```
acos(x) = atan(sqrt(1-x^2)/x)

```

Here is the source code that generates the machine code above:

```
__declspec(naked) void __fastcall doit1(int n, std::pair<double, double>* output)
{
    _asm {
        push 0x4f000000;        // [esp] = float representation of 2^32

    myloop:
        rdrand eax;             // generate a random number, -2^31...2^31-1
        push eax;               // convert it
        fild dword ptr [esp];   // to floating-point
        pop eax;                // restore esp
        fdiv dword ptr [esp];   // convert to range -1...1
        neg ecx;
        js myloop;              // do the above 2 times

        // FPU stack contents:  // x           | y
        fld st(0);              // x           | x   | y
        fmul st(0), st;         // x^2         | x   | y
        fld1;                   // 1           | x^2 | x | y
        fsubrp st(1), st;       // 1-x^2       | x   | y
        fsqrt;                  // sqrt(1-x^2) | x   | y
        fxch;                   // x           | sqrt(1-x^2) | y
        fpatan;                 // acos(x)     | y
        fadd st, st(0);         // 2*acos(x)   | y
        fldpi;                  // pi          | 2*acos(x) | y
        fmulp st(2), st;        // 2*acos(x)   | pi*y
        fadd st, st(1);         // output1     | output2
        fstp qword ptr [edx];   // store the numbers
        fstp qword ptr [edx + 8];

        add edx, 16;            // advance the output pointer
        loop myloop;            // loop

        pop eax;                // restore stack pointer
        ret;                    // return
    }
}

```

To generate two random numbers, the code uses a nested loop. To organize the loop, the code takes advantage of the `ecx` register (outer loop counter) being positive. It temporarily negates `ecx`, and then does it again to restore the original value. The `js` instruction repeats the loop when `ecx` is negative (this happens exactly once).
> 12 votes

# Answer
# Pyth, 25 23 22 bytes

A port of rcrmn's C++11 answer. This is my first usage of Pyth, and I've had plenty of fun!

```
VQJ,*y.n0O0.tOZ4,sJ-FJ

```

23-byte version:

```
VQJ*y.n0O0K.tOZ4+JK-JKd

```

Cut a byte by changing the program to use folds+sums and setting J to a tuple, removing K.

Original:

```
VQJ**2.n0O0K.tO0 4+JK-JKd

```

Cut off 2 bytes thanks to @orlp.

Explanation:

```
VQ                         loop as many times as the input number
  J,                       set J to the following tuple expression
    *y.n0O0                2 * .n0 (pi) * O0 (a random number between 0 and 1)
            .tOZ4          .tOZ 4 (acos of OZ (a random number))
                 ,sJ-FJ    print the sum of J and folding J using subtraction in parenthesis, separated by a comma, followed by another newline

```
> 7 votes

# Answer
# Julia, 48 bytes

```
n->(x=2π*rand(n);y=acos(rand(n));hcat(x+y,x-y))

```

This uses the method 2 algorithm, like most of the answers thus far. It creates a lambda function that takes an integer input and returns an n x 2 array. To call it, give it a name, e.g. `f=n->...`.

Ungolfed + explanation:

```
function f(n::Int64)
    # The rand() function returns uniform random numbers using
    # the Mersenne-Twister algorithm

    # Get n random chord angles
    x = 2π*rand(n)

    # Get n random rotations
    y = acos(rand(n))

    # Bind into a 2D array
    hcat(x+y, x-y)
end

```

I really like how the visualizations look, so I'll include one. It's the result of `f(1000)`.
> 6 votes

# Answer
# Pyth, 22 bytes

A port of the C++ answer. I had another 23 byte solution (Now 22!), but it was almost a copy of @kirbyfan64sos's pyth answer with optimizations, so I had to think outside the box a little and creatively (ab)use the fold operator.

```
m,-Fdsdm,y*.nZOZ.tOZ4Q

```

Note that this doesn't work right now because of a bug in the fold operator after the introduction of `reduce2`. I'm putting in a pull request.

```
m             Map
 ,            Tuple of
  -Fd         Fold subtraction on input
  sd          Fold addition on input
 m      Q     Map over range input
  ,           Tuple
   y          Double
    *         Product
     .nZ      Pi
     OZ       [0, 1) RNG
  .t  4       Acos
    OZ        [0, 1) RNG

```

For refence this was my other solution which works in the same way: `VQKy*.nZOZJ.tOZ4,+KJ-KJ`
> 5 votes

# Answer
# C++11, 214 bytes

```
#include<random>
#include<iostream>
#include<cmath>
int main(){using namespace std;int n;cin>>n;random_device r;uniform_real_distribution<> d;for(;n;--n){float x=2*M_PI*d(r),y=acos(d(r));cout<<x+y<<' '<<x-y<<';';}}

```

So this is a straight out implementation of the *right* algorithm from the wikipedia page. The main problem here in golfing is the oh-so-freaking-long names that the random generator classes have. But, in contrast to good ol' rand, it is at least properly uniform.

Explanation:

```
#include<random>
#include<iostream>
#include<cmath>
int main()
{
    using namespace std;
    int n;
    cin>>n; // Input number
    random_device r; // Get a random number generator
    uniform_real_distribution<> d;   // Get a uniform distribution of
                                     // floats between 0 and 1
    for(;n;--n)
    {
        float x = 2*M_PI*d(r),       // x: Chosen radius angle
              y = acos(d(r));        // y: Take the distance from the center and
                                     // apply it an inverse cosine, to get the rotation

        cout<<x+y<<' '<<x-y<<';';    // Print the two numbers: they are the rotation
                                     // of the radius +/- the rotation extracted from
                                     // the distance to the center
    }
}

```
> 4 votes

# Answer
# IDL, 65 bytes

Obviously this is the same algorithm as @rcrmn, even though I derived it independently before reading their answer.

```
read,n
print,[2,2]#randomu(x,n)*!pi+[-1,1]#acos(randomu(x,n))
end

```

IDL's randomu function uses the Mersenne Twister, which has a period of 219937-1.

EDIT: I ran 1000 chords through the visualizer above, here's a screenshot of the result:
> 4 votes

# Answer
# APL, 46 bytes

```
f←{U←⍵ 2⍴∊{(○2×?0)(¯1○?0)}¨⍳⍵⋄⍉2⍵⍴∊(+/U)(-/U)}

```

My first APL program ever! Surely it can be greatly improved (as my overall understanding of APL is lacking), so any suggestions would be fantastic. This creates a function `f` which takes an integer as input, computes the pairs of chord points using method 2, and prints each pair separated by a newline.

You can try it online!

Explanation:

```
f←{ ⍝ Create the function f which takes an argument ⍵

    ⍝ Define U to be an ⍵ x 2 array of pairs, where the first
    ⍝ item is 2 times a random uniform float (?0) times pi (○)
    ⍝ and the second is the arccosine (¯1○) of another random
    ⍝ uniform float.

    U ← ⍵ 2 ⍴ ∊{(○2×?0)(¯1○?0)}¨⍳⍵

    ⍝ Create a 2 x ⍵ array filled with U[;1]+U[;2] (+/U) and
    ⍝ U[;1]-U[;2] (-/U). Transpose it into an ⍵ x 2 array of
    ⍝ chord point pairs and return it.

    ⍉ 2 ⍵ ⍴ ∊(+/U)(-/U)
}

```

Note: My previous 19-byte solution was invalid since it returned (x, y) rather than (x+y, x-y). Sadness abounds.
> 4 votes

# Answer
# Java, 114 bytes

```
n->{for(;n-->0;){double a=2*Math.PI*Math.random(),b=Math.acos(Math.random());System.out.println(a+b+" "+(a-b));}};

```

Basic implementation in java. Use as a lambda expression.

Example usage
> 3 votes

# Answer
# Ruby, 72 bytes

My first golf here! I used the same code as everyone, I hope that's okay

```
gets.chomp.to_i.times{puts"#{x=2*Math::PI*rand},#{x+2*Math.acos(rand)}"}

```
> 3 votes

# Answer
# Java, 115 ~~123~~

This is basically the same as most others, but I need a Java score for this hole, so here it goes:

```
void i(int n){for(double x;n-->0;System.out.println(x+2*Math.acos(Math.random())+" "+x))x=2*Math.PI*Math.random();}

```

1000 sample chords can be found at pastebin, here are the first five from one run:

```
8.147304676211474 3.772704020731153
8.201346559916786 3.4066194978900106
4.655131524088468 2.887965593766409
4.710707820868578 3.8493686706403984
3.3839198612642423 1.1604092552846672

```
> 2 votes

# Answer
# R, ~~60~~ ~~56~~ ~~53~~ 49 bytes

An extra 4 bytes thanks to @JayCe and changing it to a function.

Using the same basic formula as the others. R uses the Mersenne-Twister method by default, but others can be set. Outputs a space separated list.

```
function(n,y=acos(runif(n)))runif(n)*2*pi+c(y,-y)

```

Try it online!
> 1 votes

# Answer
# CJam, ~~24~~ 22 bytes

Similar to other algorithms, here is a version in CJam.

```
{2P*mr_1dmrmC_++]p}ri*

```

An input of 1000 produces a distribution like:

**How it works**

The algorithm is simply `x = 2 * Pi * rand(); print [x, x + 2 * acos(rand())]`

```
{                 }ri*        e# Run this loop int(input) times
 2P*mr                        e# x := 2 * Pi * rand()
      _                       e# copy x
       1dmr                   e# y := rand()
           mC                 e# z := acos(y)
             _++              e# o := x + z + z
                ]             e# Wrap x and o in an array
                 p            e# Print the array to STDOUT on a new line

```

*Update*: 2 bytes saved thanks to Martin!

Try it here
> 1 votes

# Answer
# Python 3, ~~144~~ 117 bytes

(thanks to Blckknght for the `lambda` pointer)

Using the same method as others:

```
import math as m;from random import random as r;f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]

```

From the Python documentation:

> Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 219937-1.

## Output

```
>>> f(10)
[(4.8142617617843415, 0.3926824824852387), (3.713855302706769, 1.4014527571152318), (3.0705105305032188, 0.7693910749957577), (1.3583477245841715, 0.9120275474824304), (3.8977143863671646, 1.3309852045392736), (0.9047010644291349, 0.6884780437147916), (3.333698164797664, 1.116653229885653), (3.0027328050516493, 0.6695430795843016), (5.258167740541786, 1.1524381034989306), (4.86435124286598, 1.5676690324824722)]

```

And so on.

## Visualization
> 1 votes

# Answer
# Perl, 60

```
#!perl -l
use Math::Trig;print$x=2*pi*rand,$",$x+2*acos rand for 1..<>

```
> 1 votes

# Answer
# SmileBASIC, 62 bytes

```
INPUT N
FOR I=1TO N
X=PI()*2*RNDF()Y=ACOS(RNDF())?X+Y,X-Y
NEXT

```
> 0 votes

---
Tags: code-golf, geometry, random
---


# Question
Title: Create this "String Mix-Up" function in as few bytes as possible
This is my first time here at Code Golf SE so feel free to add your input/advice/suggestions to improve my post if necessary. The week after my computer science exam, the solutions were publicly published. One problem had a 45 line example solution but my solution was only 18 lines, (which I was very proud of), but I bet you guys here at code golf SE can do better.

**Here are the requirements:**

* Takes two inputs, string1 and string2.
* Delete the first occurrence of string2 found in the string1.
* Add string2 in reverse order to the beginning of string1, and
* Add string2 in reverse order to the end of the string1.
* If string2 does not occur in string1, do not modify string1.
* Output the modified string1

**Example:**

Input:

```
batman
bat

thebatman
bat

batman
cat

```

Output:

```
tabmantab

tabthemantab

batman

```

**Note:** The problem was intended to handle basic inputs. Assume all expected inputs are restricted to characters A-Z, numbers, or other special characters visible on your keyboard. It does not need to handle tabs or newlines.

Submissions with shortest byte counts in each language win.

# Answer
> 5 votes
# Stax, 16 11 bytes

```
ÄE┘¢8·╦Ωb•∩

```

Run and debug it online

The corresponding ascii representation of the same program is this.

```
Y#xyz|eyr|Sx?

```

This fixes the bugs in original version. It uses conditionals and stuff.

```
Y                   Save 2nd input in y.  Now the two inputs are x and y.
 #                  Occurrences of y in x. (a)
  xyz               x, y, ""
     |e             replace first occurrence
       yr|S         surround with y reversed. (b)
           x        first input. (c)
            ?       a ? b : c

```

The result is printed implicitly.

# Answer
> 3 votes
# C#, 148 bytes

```
using System.Linq;using System.Text.RegularExpressions;(a,b)=>a==(a=new Regex(Regex.Escape(b)).Replace(a,"",1))?a:(b=string.Concat(b.Reverse()))+a+b

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 36 bytesSBCS

Look ma, no regex!

Anonymous infix lambda, taking string2 as left argument and string1 as right argument. Assumes `⎕IO` (**I**ndex **O**rigin) to be `0`, which is default on many systems.

```
{r,⍵[(⍳≢⍵)~(f⍳1)+⍳≢⍺],r←⌽⍺/⍨∨/f←⍺⍷⍵}

```

Try it online!

`{``}` "dfn";  is left argument,  is right argument; e.g. `"bat"` and `"manbatmanbat"`:

`⍺⍷⍵` find where string2 begins in string1; `[0,0,0,1,0,0,0,0,0,1,0,0]`

`f←` assign to `f` (**f**ind)

`∨/` OR-reduction (does string2 occur at all?); `1`

`⍺/⍨` use that to compress string2 (`""` if not found); `"bat"`

reverse that; `"tab"`

`r←` assign to `r` (**r**everse)

`⍵[``],` prepend string2 indexed by the following indices:

`≢⍵` the length of string2; `3`

the indices of that; `[0,1,2]`

`(``)+` add the following to that:

`f⍳1` index of first 1 in `f`; `3`

Now we have the indices to be removed; `[3,4,5]`

`(``)~` the following indices except those indices:

`≢⍵` length of string2; `12`

the indices of that; `[0,1,2,3,4,5,6,7,8,9,10,11]`

Now we have the indices we want to keep; `[0,1,2,6,7,8,9,10,11]`

This gives us the remaining parts of string1 followed by a reversed string2; `"manmanbattab"`

`r,` prepend `r` to that; `"tabmanmanbattab"`

# Answer
> 3 votes
# Python, 55 bytes

```
lambda s,t:s.replace(t,'',1).join(2*[t[::-1]*(t in s)])

```

Try it online!

Using `join` to get the `a+b+a` pattern. This lets us write expression for `a` only once while still using a `lambda`. Compare:

**Python 2, 57 bytes**

```
def f(s,t):r=t[::-1]*(t in s);print r+s.replace(t,'',1)+r

```

Try it online!

# Answer
> 3 votes
# Ruby, ~~39~~ ~~38~~ 35 bytes

-3 bytes due to a neat trick by Asone Tuhid

```
->x,y{(x[y]&&="")?y.reverse!+x+y:x}

```

Try it online!

# Answer
> 2 votes
# Python 3, 56 bytes

```
lambda s,t:[s,t[::-1]+s.replace(t,'',1)+t[::-1]][t in s]

```

Try it online!

# Answer
> 2 votes
# Java 8, ~~126~~ 113 bytes

```
(a,b)->a.equals(a=a.replaceFirst(java.util.regex.Pattern.quote(b),""))?a:(b=new StringBuffer(b).reverse()+"")+a+b

```

Port of *@lee*'s C# .NET answer, so make sure to upvote him!

Try it online.

**Old 126 byte answer:**

```
a->b->{Object r=new StringBuffer(b).reverse();return a.contains(b)?r+a.replaceFirst(java.util.regex.Pattern.quote(b),"")+r:a;}

```

Try it online.

**Explanation:**

```
a->b->{                    // Method with two String parameters and String return-type
  Object r=new StringBuffer(b).reverse();
                           //  2nd input reversed
  return a.contains(b)?    //  If the 1st input contains the 2nd:
    r                      //   Output the reversed 2nd input
     +a.replaceFirst(java.util.regex.Pattern.quote(b),"")
                           //   Removed the first occurrence of the 2nd in the 1st input,
                           //   escaping any characters like dots, pluses, etc.
                           //   and then append that to the result
     +r                    //   appended with the reversed 2nd input again
   :                       //  Else:
    a;}                    //   Simply output the 1st input

```

# Answer
> 2 votes
# Retina, 35 bytes

```
^(.*)¶(.*?)\1(.*)
¶$^$1$2$3$^$1
0A`

```

Try it online! `$^` is new in Retina 1 and reverses its argument which is just what's needed here.

# Answer
> 1 votes
# Perl 5 \+ `-pl`, ~~38~~ 34 bytes

```
$s=<>;s/\Q$s//&&s/^|$/reverse$s/ge

```

*-4 thanks to Ton Hospel*

Try it online!

# Answer
> 1 votes
# 05AB1E, 12 bytes

```
DIåiIõ.;IR.ø

```

Try it online!

**Explanation**

```
D             # duplicate 1st input
 Iåi          # if 2nd input is in first input
    Iõ.;      # replace the first occurrence of 2nd input with the empty string
        IR.ø  # surround with 2nd input reversed

```

# Answer
> 1 votes
# Javascript, ES6 - 73 bytes

```
b=x=>y=>{v=[...y].reverse().join``;u=x.replace(y,"");alert(u==x?x:v+u+v)}

```

# Answer
> 1 votes
# Javascript (ES6), ~~69~~ ~~65~~ 64 bytes

```
x=>y=>x.match(y)?(k=[...y].reverse().join``)+x.replace(y,'')+k:x

```

Try it online!

# Answer
> 1 votes
# Jelly, 18 bytes

```
œṣ⁹Ḣ;jɗ⁹ṭṚ};Ṛ}ðẇ@¡

```

Try it online!

Full program.

# Answer
> 1 votes
# K4, 36 bytes

**Solution:**

```
{$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]}

```

**Examples:**

```
q)k){$[#s:x ss y;r,x_/(#y)#*s,r:|y;x]}["batman";"bat"]
"tabman"
q)k){$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]}["batman";"bat"]
"tabmantab"
q)k){$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]}["thebatman";"bat"]
"tabthemantab"
q)k){$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]}["batman";"cat"]
"batman"
q)k){$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]}["batbatbat";"bat"]
"tabbatbattab

```

**Explanation:**

If string 2 (y) is found in string 1 (x) then drop first indices of first occurrence.

```
{$[#s:x ss y;r,(x_/(#y)#*s),r:|y;x]} / the solution
{                                  } / lambda with implicit x,y
 $[         ;                   ; ]  / $[condition;true;false]
      x ss y                         / string-search for y in x
    s:                               / save result as s
   #                                 / count length
                              |y     / reverse (|) y
                            r:       / save as r
                           ,         / join with
               (          )          / do this together
                        *s           / first (*) s
                       #             / take
                   (#y)              / length of y
                x_/                  / drop (_) over (/)
             r,                      / join with r
                                 x   / (else) return x

```

# Answer
> 1 votes
## Javascript 85 bytes

```
a=>b=>a.includes(b)?[...b].reverse().join``+a.replace(b,'')+[...b].reverse().join``:a

```

If someone knows how to avoid using `split('').reverse().join('')` for reversing string, please let me know

```
f=a=>b=>a.includes(b)?[...b].reverse().join``+a.replace(b,'')+[...b].reverse().join``:a

console.log(f('batman')('bat'))

console.log(f('thebatman')('bat'))

console.log(f('batman')('cat'))
```

# Answer
> 0 votes
# Jelly, ~~21~~ 20 bytes

```
œṣµḢ;j⁹$ɓ;;@ðU}
ç¹w?

```

Try it online!

---

Ouch! Why can other languages get 11~12 bytes? Am I doing something wrong?

And *finally*, I *think* I know how chain separators works...

```
œṣµḢ;j⁹$ɓ;;@ðU}   Helper link (dyadic). General structure:
œṣ                <dyad>                    - given x and y, split x at
                                              sublists equal to y.
   Ḣ;j⁹$                <monad>             - given x, join with y except at
                                              first index.
         ;;@                   <dyad>       - given x and y, return y+x+y.
                                              Note that this link is flipped.
             U}                      <dyad> - reverse right argument.

ç¹w?    Main link. Evaluate the last link if the second input is a substring
        of the first input, otherwise - apply identity (do nothing).

```

# Answer
> 0 votes
# Python 2, 62 Bytes

```
def f(a,b):b*=b in a;a=a.replace(b,"",1);b=b[::-1];print b+a+b

```

# Answer
> 0 votes
# SNOBOL4 (CSNOBOL4), 73 bytes

```
	S =INPUT
	T =INPUT
	S T =	:F(O)
	T =REVERSE(T)
	S =T S T
O	OUTPUT =S
END

```

Try it online!

What's a regular expression?

# Answer
> 0 votes
# Python 3, 58 bytes

```
def f(a,b):z=(b in a)*b[::-1];return z+a.replace(b,'',1)+z

```

# Answer
> 0 votes
# AWK, 85 bytes

```
{for(;x++<N=split($0,a,"");)p=a[x]p;$0=NR%2?L=$0:sub($0,"",L)?p L p:L}!(NR%2)

```

Try it online!

Input is: primary string on odd-lines, replacement on even lines. Replacement is case sensitive.

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


# Question
Title: Random Golf of the Day #8: Shuffle an infinite list
# About the Series

First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.

# Hole 8: Shuffle an infinite list

You should write a function or program which takes an infinite list as input and returns a shuffled version of that list.

## About infinite I/O

There are several ways you can take input and produce output for this challenge:

* You can either take a list of positive integers, or a string representation thereof, or a string or list of printable ASCII characters (0x20 to 0x7E, inclusive). The output format must match the input format. I'll just refer to the data as "the list" from now on, regardless of which option you choose.
* You can read the list from an infinite standard input stream and write the output continuously to an infinite standard output stream. The solution should not depend on any particular value or sequence of values to ensure that the output stream is regularly written and flushed (e.g. you can't just write output whenever there's a `5` in the input list). Of course, if you read a string representation of a list, it's fine to wait until encountering the list separator.
* In languages that support them, you can write a function that takes and returns a lazy infinite list or string.
* In languages that support them you may implement an infinite generator that takes another generator as input.
* Alternatively, you can write a function which takes no arguments and returns one output value each time it is called. In this case, you can assume that a function has been defined which takes no arguments and returns the next input value each time it is called. You may freely choose that function's name.

You may assume that your program runs forever and that infinite memory is available. (It's possible to solve this with a finite amount of memory, but what this means is that you're allowed to leak memory.)

## About the randomness

For any value **v** which is read at a position **i** of the infinite input, there must be a positive probability for it to end up in any of the positions **i-9** to **i+9** of the infinite output (unless that position would be negative). These probabilities don't have to be the same for different output positions or even for different input positions. It's fine if your solution can also shuffle the values to other position that are further away.

Hence, it's not necessary that your solution can shuffle the first value very far down the list, or that it can shuffle a very late value up to the first position, although it's fine if it does, as long as all positions 9 steps from the input are possible.

E.g. if you took the following string as input, the `___` indicates all the positions the `X` must be able to end up in the output:

```
                  ___________________
 abcdefghijklmnopqrstuvwxyzXabcdefghijklmnopqrstuvwxyz...

```

If your language lacks a built-in random number generator or you don't want to use it, you may take an additional seed value as input, and implement your own suitable RNG using the seed. This page may be helpful for that.

Regardless of the actual distribution your solution uses, it must almost surely produce the next value after a finite (but arbitrary) time.

Please include a short explanation about how your implementation satisfies these requirements.

## Scoring

This is , so the shortest valid answer – measured in *bytes* – wins.

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

*(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)*

# Answer
# Python 3, 78 bytes

```
from random import*
l=[]
while[shuffle(l)]:l[9:]and print(l.pop());l+=input(),

```

Try it online!

Takes input from STDIN (one per line), prints to STDOUT.

Keeps a buffer `l` of up to 10 elements. The buffer is shuffled with each step. When its length is 10, the last element is printed and removed.

If an element happens to be printed as soon as it was inserted, it has skipped ahead of 9 other elements waiting in the buffer, so it appears 9 spots left. An element can wait in the buffer arbitrarily long, so its position can move any amount right.

There doesn't seem to be a nice way to produce and remove a random element from a list. Shuffling seems like overkill. It's 2 bytes longer to use `l.pop(randint(0,9))` (which uses that the list has 10 elements).

```
from random import*
l=[]
while 1:l+=input(),;l[9:]and print(l.pop(randint(0,9)))

```

It's no better to do `x=choice(l);l.remove(x)`.A language with `poprandom` like

```
poprandom = lambda l:l.pop(randrange(len(l)))

```

could very cleanly do

```
from random import*
l=[]
while 1:l+=input(),;l[9:]and print(poprandom(l))

```
> 13 votes

# Answer
# Befunge (quirkster flavor), 4 bytes

```
?,?~

```

`,` reads a character from the stream and pushes it onto the stack. `~` pops the top character from the stack (if present) and prints it. `?` randomizes which command is executed next. So the algorithm here is "In an infinite loop, with equal probability either push a character or pop a character." I think this satisfies the requirements: a character can see arbitrarily many characters added above it in the stack, so it can move arbitrarily far to the right, and it can be printed when the stack is arbitrarily big, so it can move arbitrarily far to the left.
> 9 votes

# Answer
# C (gcc), 94 bytes

```
L;i;f(s){srand(s);int B[9]={0};for(L=0;;)L>9&&putchar(B[i=rand()%10]),B[L>9?i:L++]=getchar();}

```

Try it online!

Ok, a TIO link doesn't make much sense. For ease of testing, I created the following C program that will output random ascii characters, or repeat an string infinitely.

```
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char** argv){
    srand(time(NULL));
    if(argc < 1) {
        for(;;){
            printf("%c", rand() % 95 + 32);
        }
    } else {
        char* s = argv[1];
        int i = 0;
        for(;;){
            if(s[i] == 0)
                i = 0;
            printf("%c", s[i++]);
        }
    }
}

```

This program will be referred to as `iro`.

## Program correctness

What I do here is read `9` values into a buffer. After this, random indices are chosen from this array and are outputted, then replaced by the next character in the stream.
> 4 votes

# Answer
# S.I.L.O.S, 149 bytes

```
b=1
lbla
x=15+b*15
b=1
lblb
readIO
queue 0 i
x-1
if x b
a=0
lblx
x=rand*2
queuePop 0
if x X
printInt m
a+1
b=15-a
if b x
GOTO a
lblX
queue 0 m
GOTO x

```

Try it online!

Essentially it keeps taking input (on the online interpreter through arguments, but on the offline official interpreter it will allow you type into the console (infinitely)) in blocks of 15 at a time (30 the first block).

It loads the input into a temporary queue and picks a lucky 15 (randomly, but not equally distributed in terms of probablity or distribution).

The rest remain in as new inputs fill the queue, the first input could be shuffled all the way to the end, (basically I think the characters follow a normal distribution). It's interesting to note that this program is only twice as verbose as python and perhaps "golfier" than Java.

---

To better see the results I have a non-compliant version which takes input as a string (however it can only take in 8,000 or so characters).

Try it online!

Just for fun, here is this post fed through the string version.

```
 [.L.Ooy" 9beS.I.S],"14 ts  b1
 nly

  =ll
   x=1b 15   1
5b  a*b=  lb  rd#  + lb eaI O    e
 x
 ifquu
1 0x b
   =

    e
0
   i lblxa -d*2
    quu   x=rn
   x Xea p0
   pnInt o r   a
   mf =   iePit
  ba 1
   GTO  1 f b x+ Oa

 qe -lblX u0 m    GOOue
[rlT

 tnn5 !I.STii][S.LO ie

htpsgthyx]:iub.om/jhujh.. tcraa.I.O.o /TytonieSu:wl/.L lnn!:tt/iS
[ in hsto.un/nuslprxRUCoDsio/]:e#NzZn6j4c/2xNQFnF7y0aLzkrosd9Dov2yxJNx774HBrgPUdi9CySI09sCLw5TJwB7jlB1XVeQFE7m1VMsIQvDOjBmdtME3umNzYXs9unFbqRamVDfUDw@RT3NHoL7/i04bz16DCoP4eulOU7jPD8OmYjATpynkuMDuBPYmtnIJzseyyhaNkMyQgXG2R782vqMDIiUm6Kq4Q3mJkxlUsR1rrldPw./l28Z SL.XS – IONuscOT "
senallyxMz.stiitkp ingN"
 eestaint on heeInliinrprt (oe e  toghr tetgpnmntuon eruEuut r h ofi off,bhenecil inretea.atr  ialoks tirilw upeitfleptly ty  honso (e oote cenfine iwllbc 15 atly) nitloo  aim( te)nikfte3 firs bck)
hs 0It te
 lodshipo alauttt.mpra quuet i reanicks a lck eooy d  randomyn p 15( u o equl,unbtty drbutedaynistinems oftrly ordisrprob ill abition h  ibttmin.Tet ri)
 a nwit u ree nusfil th queusen
pte ftip,ae uldsfuesis ob hl rlelth weual  t tc hdyoend,f tbaaly thi an elnkhecarcthe(sc h o  noreiItrolwaaldibtio  lmiru.t' iereaf ) tsng tetntiottssht prasnon  hogIms only twieatisi s vroscpythonadprs a hbapolfi" e r n e ehanava.
 tte s/"gt
obterelIe  tsvea non-omhTrehs  a plntvesion hcahihk ine teuts sriprics at rwvritcaw aa g(hoee n onl kein n00 orscat ,0  cter).

[Tyauoas  it onine!hrhrys:.ru]p//o/lsslo#jVd(tinnexi3E@KDpit/LrhtwXwVEUuscxPmJjFFCaNimMzlHiQEcMmdVIT7vqs8mNgxU3mD/J1AwX q/ivbao1j@nb4I6/m93655bThmb4cy5TUX3xvI018cZzrXItuO5B@NX5JD/HzyE@G@D5eqrGem3l0HPGRutZfpi2PzVA@d3CVRTm4zJxnZdcFSTEO0JOT9KhDI6byjnLhS0cNmGz7hJrTdAgORT8Ndvv7DgZSbJdkp9v5al8qMyNCb9tXe0ChrShXRTOt@7fFgV3zTkbVbsD@JpKina2oKgNVakjsjLCpD29u7l0XVRWalVTyArF1FqypQAxXb/BedqUqpJGOPVyxOjLj0jXup8cE277L2I6@lSowK5pA7nGldRBiJwyKxF6z2c3kW/sJ4EYBbbpSuBxs55nyI9sdnu@nJJeGqtKprGEUbc6NDGMjjO2tN/KuKTWh2WWbbRRLVaq/P6KqkoMNWGRgTQZLlbXfQI050bY0rz0xmzCVZ4vowjpV0dCmkDFq0VNa5GSDzVn5Qw7idwPTxu5xTAtLQCDN/YIApfAn4dsDmYksCqUU27sRggpzRK4SmdjmPUPQO4j5FmgHMFRWS2eI1CfA2YIcf7JlylFjdZypVTH0IJu4ZJHiUviyBFKqhrkCjgXAAB8d710NhHgDwcJksuvPPprcfzHPTaJGFX8OIExW/cBZjaPiY7a4WD6rTYmOouBVucROlwvuBJiHWdJQjjbobNGTd7M1P6z8dw/A@GU02hgjCcrjjQHkAdS6r7UjQ6wAPqB@sIgxkKcbZDixeWS6mn160CKQpn7aUwGLK22u9I0oX6YIwPMhFVaX5uYon0AyoNTCZvnmtilVhV3/pgTGc7r39lIS5PmqM/NGnUSLnTw9eTJ7qqrNQKsJHz@Tt8mDZVWKCKTkBro1PuQAksDdN1yaVGiVXElRW9i5M11cINmxNGYAg9TD7sxtEDI2OkKMaBXgvO5dOplUQQIdpb2w66NePBScMmEnAX8ydGSiiHlss@hOLZzInnIoTevRtEm/TGHWOkly5ljMK4FkgDDSWCWBW3YwmEVYCIBV@GMIg3TZtGwMFWXVxQwBb5iD6PfS7h7Sric1ib5ZYIvW6n3tlaK7/6@3OAHy4LjOuW@tzaBP3@mFbJpHsVsQKPfeui/o1@aBcbZ4TK96T8tp3QjeA1vDXMKBIqdK@HZs2vsMlQE36YmrBEnVRUvAGNuCt44e0RB0sL0MkNu1Q5wOwliTT2JQzVrOnHAmSXIU//sqjdG6jdT2r1v@@lGjouzkGWoD4zhnzJBxo0OT6OTbBDgeDFRnY8TMXZbMPdxsCtbXeUxIBqST4VRwkpbgwChBcJxMx6hLIVZhfuylDvF1l26Nbl3xRLgQnatSCMigx@PCT6lcG1ebdk/86UBUFp9UkxjoCGSJnlxMtUdHf6IjkMnil5aua9L@xXsdHEKW@8JpVqlgKsr12bAKG2Typfv@Yy4CkUydETWphcdmdpWq7egtxqP8pYI2rSaSuYBwW0tNTdXn4qcjnZ9JKhuVwaWRycwCWt247LSflsCHsB3u0KoLTQJzL1uMl0duij/IF7LCc5FSpIPW7gcjOYj@jQdpQHv0WUz/IbMhS0XmFiWm1i0cTbxXjsjLxt6nGmQNQoKfREklc8pTFyHub7jUg8TR4QrZ2w3YjaLWNi@FFerCnNgY0LqgrA6qkWg8H/7Pv6YhtqeZzvoB0yD5Wm1eLL1Vf/SouI0Q/fox7eQlXieZB1F1v2/in/btqyVPtubWhDIKH8WaTlry43N6HgOEzX5HOjv1@lamBeZlJpqJnG3B2LZe8sXUafdAcVvVjBBlqxbEThCdjpelc7YVuYXOqM8MyVV3iPxbqYu@nmbHnoKpK1Eww11sA9aiwN8kMe0ioVO7qnucL1A8wHJ4wTsdltrm3CC4bpCd5hMhyDGXSdGgdKvnCKUpNB9nH@wXLgu5iUEcfJbDKZFjx6gI9i8fCcUFiQXxeSbKnwhT6@v/I6yS/Ew9k@tgI68/lO@4jjx0PZBpSo5vWLCDi4zb@TJejQQPtvlgde98MDGJ4vUW3T@iJTA89gGhUJIgy@MDBpaz3s7PT2ZIwStVANsxpCmhghh68huncD0VdumQt0lT/Su6HW3kMLFfo/FphQ0QhtoZ5iRN/@hZ/DmHq8UZEgiblprekkw1I366fMhePmDclSxirOlYH2Hwe3fom3aoe1@yaQYwi5ZPd2FcITXO7cu9@6tiHZJc7lKSB8e3/mXx34xYH/8F@TUxx/5vs5yHsYBL4ekscycqT1BnuV19/ "SFE/iRAIL.O NqUXAm. T3zDreu).S –IOxs."d

```
> 3 votes

# Answer
# Ruby, 43 bytes

```
l=[];loop{l<<gets;l[9]&&$><<l.shuffle!.pop}

```

My original answer used a lazy-evaluated infinite list, but this is shorter. Oh well.
> 3 votes

# Answer
# Aceto, 24 bytes, non-competing

*Non-competing because I had to fix a bug in the interpreter.*

```
^

OYpO
r^`!
?d0=   >

```

Takes an infinite stream of lines and yields them in a random order. Every element has a chance of occurring at any random point.

We start with a `?` in the bottom left corner, which moves us in a random direction. If that is down or left, we get pushed right back.

If we're moved upwards, we `r`ead a value, shuffle the stack (`Y`), and jump back to the `O`rigin.

If we're moved to the right, we `d`uplicate the top stack value, push a `0` and test for equality (since we're reading strings, we can't ever have the integer 0). If the values are equal, that means we've reached the bottom of the stack (from which we don't want to print). We *negate* the comparison (`!`), and `p`rint only if (```) the things were not equal. Then we also jump back to the `O`rigin.
> 3 votes

# Answer
# MATL, 11 bytes

```
`rEkN*?D}iT

```

Try it online!

Port of histocrat's Befunge answer.

Explanation: (Thanks to Luis Mendo for -1 byte)

```
`         T % Start do-while (`) .... true (T)
 rEk        % 50-50 chance of outputting or inputting:
            %   Random number between 0...1, multiplied by 2 and converted to logical.
    N       % Check if there is anything on the stack to output
     *?     % If there is anything on the stack and (*) we want to output:
       D    % Output. Sadly, D errors when the stack is empty, requiring the N*
        }i  % Else, input.

```

This outputs almost surely in finite time, and almost surely requires only finite memory.

For completeness, here is a 15-byte version which keeps a 10-element buffer and outputs a random element from that:

```
`htnt9>?Yr&)wDT

```

I like this version for the very idiomatic (as far as golfing languages can be idiomatic) `tn...Yr&)`, which pops a random element from the list and returns the list without that element. However, the particular logistics of this challenge add a lot of bytes (the required `w` for the display, the `t9>?` to check if the list is full enough...).
> 2 votes

# Answer
# Alice, 7 bytes

```
a&IdU,O

```

Try it online!

This should work on an infinite input with infinite time and memory, but it's not so easy to test in practice :)

### Explanation

```
a&I         Push 10 characters from the input to the stack.
     d        Push the depth of the stack.
      U       Pop a number (d), push a random number in [0,d)
        ,       Pop a number (n), move the element which is n elements below the top to the top of the stack.
         O    Output the character on top of the stack.

                Execution loops back to the beginning of the line.

```

At each iteration 10 characters are read from input and only one goes to the output, so memory usage increases linearly during execution. With a finite input this quickly reaches EOF, from which ten -1 will be pushed to the stack at each iteration. Trying to output -1 as a character has no effect, but it's unlikely that all the characters of the input will be printed in a reasonable amount of time.

Position *i* of the output can be taken by any character in the input up to position *10i*, this complies with the challenge requiring at least a range from *i-9* to *i+9*.
> 2 votes

# Answer
# C, 214 bytes

```
c;i;char B[19]={0};char*I;
S(p,q){if(B[p]-B[q])B[p]^=(B[q]^=(B[p]^=B[q]));}
R(n){while(n--)putchar(B[c]),B[c]=*I,c=++i%19,I++;}
main(c,v)char**v;{srand(time(0));I=v[1];R(19);i=9;for(;;){S(i,rand()%19);R(1);i=++i%19;}}

```

**How it works**

**Try Online (UNIX)**

```
#include <stdio.h>
#include <unistd.h>

// animation speed
#define ANIMATION_SLOW 600000
#define ANIMATION_NORMAL 400000
#define ANIMATION_FAST 200000

c;i;char Buffer[19]={0};char*input;
Swap(p,q){if(Buffer[p]!=Buffer[q])Buffer[p]^=(Buffer[q]^=(Buffer[p]^=Buffer[q]));}
Read(n){while(n-->0)putchar(Buffer[c]),Buffer[c]=*input,c=++i%19,input++;}

main(int argc, char**argv)
{
    // initialization
    srand(time(0));
    input=argv[1];
    Read(19);i=9;

    // shuffle machine
    while(1)
    {
        usleep(ANIMATION_NORMAL);
        Swap(i,rand()%19);
        Read(1);
        i=++i%19;
    }
}

```
> 2 votes

# Answer
# 05AB1E, 13 bytes

```
[I)˜¼¾T›i.rć,

```

Try it online! (modified to take 20 elements)

```
[             # Infinite loop
 I)˜          # Add the next element from input to the array
    ¼         # Increment the counter variable
     ¾T›i     # If the counter variable is greater than 10...
         .r   #   Get a random permutation of the array
           ć, #   Print and remove the first element

```
> 2 votes

# Answer
# Bash, 17 bytes

```
xargs -n9 shuf -e

```

Try it online!

xargs continuously takes 9 letters from STDIN and sends them to shuffle

an infinite list can be generated by:

```
yes {a..z}

```

which prints a b c d e .. z infinite times.

Test could be done by:

```
yes {a..z} | xargs -n9 shuf -e

```
> 1 votes

# Answer
# Javascript, 78 bytes

```
for(l=[];;){l.push(prompt());l.length==10&&alert(l.splice(Math.random()*9,1))};x.sort(()=>Math.random()<0.5);alert(x)}

```

Uses the same method as xnor's answer.
> 1 votes

# Answer
# R, 70 bytes

```
x=NULL;repeat{x=sample(c(x,scan()));if(sum(x|1)>9){cat(x[1]);x=x[-1]}}

```

Starts with an empty vector `x`. In an infinite loop, it takes a new value from STDIN, then shuffles the vector. Then it checks if the length of the built up list is 10 or higher. If it is, it can start printing. This way the vector has a buffer of 10 inputs, each getting shuffled in every iteration. So it is possible for input to be printed 10 places earlier, and infinitely many places later (following a geometric distribution with `p=1/10`). When the buffer is long enough, the first element is printed and removed from the vector.
> 1 votes

# Answer
# Perl 5, 39 bytes

38 bytes of code + `-n` flag.

```
print splice@F,rand 10,1if 9<push@F,$_

```

Try it online!

Add each element to `@F` array (with `push@F,$_`). When `@F` contains 10 elements (`push` returns the number of elements in the array, hence `9<push...`), a random element is removed and printed (`splice@F,rand 10,1` to remove the element, `print` to print it).
The output starts happening after then 10th element has been read. Hence, each element can start appearing at least 9 positions before its original one, and can be shifted to the right infinitely.
> 0 votes

# Answer
# SmileBASIC, ~~61~~ 58 bytes

```
@L
B$=B$+R()IF I>8THEN R=RND(9)?B$[R];:B$[R]="
I=I+1GOTO@L

```

Each character of the infinite list is added to the end of the buffer. When the buffer length is 11, a random character is printed and removed.

Function `R` generates the next character.
> 0 votes

# Answer
# Prolog, 70 bytes

```
s(L):-get0(C),(length(L,9)->random_select(H,L,R),put(H);L=R),s([C|R]).

```
> -1 votes

---
Tags: code-golf, array, random, permutations
---


title: MarGolf Meets Langton's Anthill

text:
# Question
Title: MarGolf Meets Langton's Anthill
```
This is Markov.
Markov's golf ball rolls around randomly.
Markov's ball will hole however he strikes it.
Markov is smart.
Be like Markov.

```

And this:
is an anthill in Langton's backyard.
The anthill is big enough to hold Markov's golfball, MarGolf. However, the anthill moves and changes direction depending on the surrounding terrain.

## The Task

**Take an input of a 10x20 field:**

* `*` MarGolf
* `O` Lanton's Anthill
* `,` Anthill turns 90 degrees clockwise
* `.` Anthill turns 90 degrees counterclockwise
* `0` MarGolf in Langton's Anthill

A field looks like this:

```
,...,.,,..,...,.,,..
..,.,,,..,...,..,.,.
.,,*.,....,.,,,.,,,.
,.,,.,...,,.,.,,,,,.
.,..,....,,.....,,.,
,.,.,...,..,.,,,,..,
....,,,,,,,,,.......
........,,.,...,...,
,,,,,,,,,,,,....,O.,
,.,.,.,.....,,.,,,,,

```

**Game rules:**
The configuration of the input field is called tick 0. Your program needs to evaluate and print out the configuration of the next tick, in which both MarGolf and Langton's Anthill will move to another cell. The the item in the current cell will become the item currently in the target cell. If both MarGolf and the anthill move to the same cell in the next tick, the game ends.

**Movement rules:**

* **MarGolf** moves randomly. All nine cells in the 3x3 area around MarGolf has equal chance of being selected. This becomes a choice among 6 cells at an edge of the field, and 4 cells at a corner.
* **Langton's Anthill** needs to remember its movement direction of either up, down, left, or right (NSEW or whatever equivalent). It moves one cell in its direction each tick, and the original content of the cell changes its direction clockwise or anti-clockwise, as specified above. Initial direction at tick 0 is random, each direction has an equal chance of being the initial.

## Notes

* The program needs to print the configuration of each tick, until the game ends.
* The tick number precedes the field configuration of each tick.
* You may assume the input is always valid.
* The shortest program is bytes wins.

---

**Update:** forgot to mention anthill reverses direction before moving if it would otherwise go off the field. Credit to user81655 for reminding.

# Answer
> 3 votes
# Java 10, ~~611~~ ~~609~~ ~~607~~ ~~593~~ 591 bytes

```
m->{int x=0,y=0,X=0,Y=0,r=10,c,d=4,e;for(d*=Math.random();r-->0;)for(c=20;c-->0;){if(m[r][c]<43){x=r;y=c;}if(m[r][c]>48){X=r;Y=c;}}for(;;d=m[r][c]<45?d<2?d+2:d<3?1:0:d>1?d-2:d>0?2:3){p(m);for(e=4;e==4;e*=Math.random())e=9;m[r=x][c=y]=m[x+=e/3<1?x>0?-1:1:e/3>1?x<9?1:-1:0][y+=e%3<1?y>0?-1:1:e%3>1?y<19?1:-1:0];if(m[x][y]>48){m[x][y]=48;m[r][c]=0;p(m);e/=0;}m[x][y]=42;m[r=X][c=Y]=m[X+=d<1?X<9?1:-1:d==1?X>0?-1:1:0][Y+=d==2?Y<19?1:-1:d>2?Y>0?-1:1:0];if(m[X][Y]<43){m[r][c]=48;m[X][Y]=0;p(m);e/=0;}m[X][Y]=79;}}void p(char[][]m){var p="";for(var a:m)p+=p.valueOf(a)+"\n";System.out.println(p);}

```

-4 bytes thanks to *@ceilingcat*.

Assumes the final swap of `*` and `O` will empty the cell where `*` is coming from.

**Explanation:**

Try it online.

```
m->{                        // Method with character-matrix parameter and no return-type
  int x=0,y=0,              //  [x,y] coordinates of MarGolf
      X=0,Y=0,              //  [X,Y] coordinates of Langton's Anthill
      r=10,c,               //  Temp [x,y] coordinates
      d=4,                  //  Direction Langton's Anthill
      e;                    //  Direction MarGolf
  for(d*=Math.random();     //  Set the direction Langton's Anthill randomly [0,3]
      r-->0;)               //  Loop over the rows:
    for(c=20;c-->0;){       //   Inner loop over the columns:
      if(m[r][c]<43){       //    If '*' is found:
        x=r;y=c;}           //     Set MarGolf's [x,y] coordinates
      if(m[r][c]>48){       //    If 'O' is found:
        X=r;Y=c;}}          //     Set Langton's Anthill's [X,Y] coordinates
  for(;                     //  Loop indefinitely:
       ;                    //    After every iteration:
        d=                  //     Change the direction of Langton's Anthill:
          m[r][c]<45?       //      If the swapped cell contained a comma:
           d<2?d+2:d<3?1:0  //       Change the direction clockwise
          :                 //      Else (the swapped cell contained a dot):
           d>1?d-2:d>0?2:3){//       Change the direction counterclockwise
  p(m);                     //  Pretty-print the matrix
  for(e=4;e==4;e*=Math.random())e=9;
                            //  Change direction MarGolf randomly [0-9] (excluding 4)
  m[r=x][c=y]               //  Save the current MarGolf coordinates
   =m[x+=e/3<1?x>0?-1:1:e/3>1?x<9?1:-1:0]
     [y+=e%3<1?y>0?-1:1:e%3>1?y<19?1:-1:0];
                            //  And change that cell to the content in direction `e`
                            //  0 to 9 (excl. 4) is NW,N,NE,W,n/a,E,SW,S,SE respectively
                            //  If `e` would go out of bounds, it moves opposite instead
  if(m[x][y]>48){           //  If MarGolf reached Langton's Anthill:
    m[x][y]=48;             //   Set that cell to '0'
    m[r][c]=0;              //   And empty the swapped cell
    p(m);                   //   Print the final status of the matrix
    e/=0;}                  //   And stop the loop with an error to exit the program
  m[x][y]=42;               //  Change the cell in the new coordinate to '*'
  m[r=X][c=Y]               //  Save the current Langton's Anthill coordinates
   =m[X+=d<1?X<9?1:-1:d==1?X>0?-1:1:0]
      [Y+=d==2?Y<19?1:-1:d>2?Y>0?-1:1:0];
                            //  And change that cell to the content in direction `d`
                            //  0 to 3 is E,W,S,N respectively
                            //  If `d` would be out of bounds, it moves opposite instead
  if(m[X][Y]<43){           //  If MarGolf reached Langton's Anthill:
    m[r][c]=48;             //   Set that cell to '0'
    m[X][Y]=0;              //   And empty the swapped cell
    p(m);                   //   Print the final status of the matrix
    e/=0;}                  //   And stop the loop with an error to exit the method
  m[X][Y]=79;}}             //  Change the cell in the new coordinate to 'O'

void p(char[][]m){          // Separated method to print the given matrix
  var p="";                 //  String to print, starting empty
  for(var a:m){             //  Loop over the rows:
    p+=p.valueOf(a)         //   Convert the character-array to a String line and append,
                     +"\n"; //   including a trailing newline
  System.out.println(p);}   //  Print the String with trailing newline as separator

```

---
Tags: code-golf, random
---


# Question
Title: Given a number, print out its "collective sum"
Given a number as input, print out its **collective sum**

What is a collective sum?

Consider the number `13214`, the input

Looping through each of the digits starting from the left, we will be able to obtain its collective sum.

`1` means look at the first digit, and add it to the sum, sum = 1

`3` means look at the "first 3 digits" and add it to the sum, sum = 1 + 132

`2` means look at the "first 2 digits" and add it to the sum, sum = 1 + 132 + 13

`1` means look at the first digit, and add it to the sum, sum = 1 + 132 + 13 + 1

`4` means look at the "first 4 digits" and add it to the sum, sum = 1 + 132 + 13 + 1 + 1321

Total sum = `1468` and this is your output

---

> Special cases:

If we encounter a `0`, then clearly we keep the sum the same

```
The number 1301 would have a sum = 1 + 130 + 1 = 132

```

If we encounter a number that is larger then the length of the input, we add it all

```
The number 251 would have a sum = 25 + 251 + 2 = 278

```

---

> Test cases:

```
collectiveSum(0) = 0

collectiveSum(2) = 2

collectiveSum(2315) = 23 + 231 + 2 + 2315 = 2571

```

---

Shortest amount of bytes wins. Happy golfing!

# Answer
> 7 votes
# 05AB1E,  ~~4~~  3 bytes

-1 thanks to Kevin Cruijssen (use of  avoiding a `}`)

```
€£O

```

**Try it online!**

### How?

```
€£O - implicit input   e.g. 2315
€   - map with:
 £  -   head to             23, 231, 2, 2315
  O - sum                   2571

```

# Answer
> 5 votes
# Python 2, 43 bytes

```
lambda n:sum(int('0'+n[:int(x)])for x in n)

```

Try it online!

# Answer
> 4 votes
# Python 2, 72 bytes

First submission! Thanks to @DestructibleLemon for the help!

```
import sys;d=sys.argv[1];s=0;for e in d:s+=int(d[:int(e)]);print str(s)

```

# Answer
> 3 votes
## Haskell, ~~43~~ 37 bytes

```
f l=sum[read$'0':take(read[d])l|d<-l]

```

Try it online!

The input number is taken as a string.

```
   [        |d<-l]      -- for every digit d in the input string
        read[d]         -- convert to a number
      take     l        -- and take that many digits from l
     0:                 -- prepend a 0 (to handle 0s)
   read                 -- convert to a number
sum                     -- sum all numbers

```

# Answer
> 3 votes
# Ruby, 36 bytes

```
->n{n.sum{|x|n[0,x.to_i].join.to_i}}

```

Try it online!

# Answer
> 3 votes
# JavaScript, ~~42~~ 40 bytes

Thanks @Shaggy for golfing off 2 bytes

```
f=
x=>[...x].map(y=>a+=+x.slice(0,y),a=0)|a

console.log(f("2315"))
console.log(f("0100"))
console.log(f("2"))
console.log(f("01025"))
```

Receives input as a string and returns an integer. As currently written, this code leaves leading zeroes on any integers.

# Answer
> 3 votes
# R, 57 bytes

saved one more thanks to @Vlo

```
sum(strtoi(substring(i<-scan(,""),1,el(strsplit(i,"")))))

```

was: Saved 4 bytes thanks to @Robert Hacken's suggestion.

```
i=scan(,"");sum(strtoi(substring(i,1,el(strsplit(i,"")))))

```

A simple string approach.

# Answer
> 2 votes
# C (gcc), 106 bytes

```
j,k,c,t;f(char*S){for(t=j=0;S[j];j++)c=S[k=S[j]-48<(c=strlen(S))?S[j]-48:c],S[k]=0,t+=atoi(S),S[k]=c;S=t;}

```

Try it online!

# Answer
> 2 votes
# Jelly,  ~~7~~  5 bytes

-2 thanks to Dennis (head vectorises \>.\<)

4 if we may take lists of digits\*

```
Dḣ`ḌS

```

**Try it online!**

* `ḣ`ḌS`

### How?

```
Dḣ`ḌS - Link: integer, n   e.g. 2315
D     - to decimal list         [2,3,1,5]
  `   - repeat left as right    [2,3,1,5]
 ḣ    - head                    [2,3], [2,3,1], [2], [2,3,1,5]
   Ḍ  - from decimal lists      23, 231, 2, 2315
    S - sum                     2571

```

# Answer
> 2 votes
# Charcoal, 10 bytes

```
ＩΣＩＥθ✂θ⁰Ｉι

```

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

```
   Ｅθ       Map over input string
        Ｉι  Cast current character to integer
     ✂θ⁰    Slice input string to that length
 ΣＩ         Cast slices to integer and take the sum
Ｉ           Cast result to string and implicitly print

```

# Answer
> 2 votes
# Octave, 56 bytes

```
@(n)sum(str2num(['' 32+char(n.*(find(n)<=(n'-48))-32)]))

```

Anonymous function that takes a string as input argument and returns a number as output.

**Try it online!**

The shorter version

```
@(n)sum(str2num(['' char(n.*(find(n)<=(n'-48)))]))

```

works in Matlab, because `char(0)` is treated as a space.

# Answer
> 2 votes
# Perl 6, 27 bytes

```
{sum $_ X[&substr]^«.comb}

```

Test it

## Expanded:

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

  sum

    $_           # the input

      X[&substr] # crossed using &substr sub as if it was an infix operator

    ^«\          # upto ｢^｣ for each of the following ｢«｣ (creates Range objects)
    .comb        # the input split into digits (implicit method call on ｢$_｣
}

```

# Answer
> 2 votes
# C (gcc), ~~77~~ 75 bytes

Has to be compiled with the `-lm` switch or GCC doesn't recognize the math functions.

```
r,q,i;f(n){for(r=0,i=n;i;i/=10)q=log10(n)+1-i%10,r+=n/pow(10,q>0?q:0);n=r;}

```

Try it online!

# Answer
> 2 votes
# dc, 55 bytes

```
[0*]sq?dsfZ1-se[lfddZrIle^/I%-d0>qIr^/+led1-se0<a]dsaxp

```

No strings nor arrays! Indeed, the required digits are acquired solely through mathematical manipulation.

Try it online!

# Answer
> 1 votes
# Husk, 6 bytes

```
ṁd´M↑d

```

Try it online!

### Explanation

```
ṁd´M↑d  -- example input: 1301
     d  -- decimal digits: [1,3,0,1]
  ´M    -- map over it using it as argument (example with 3):
    ↑   -- | take: [1,3,0]
        -- : [[1],[1,3,0],[],[1]]
ṁ       -- map and then sum the result (example on [1,3,0]):
 d      -- | as decimal: 130
        -- : 1 + 130 + 0 + 1 = 132

```

# Answer
> 1 votes
# Japt, 5 bytes

Takes input as a string.

```
¬x@¯X

```

Try it

---

## Explanation

```
          :Implicit input of integer string U
¬         :Split to an array of characters/digits
  @       :Pass each X through a function
   ¯X     :Slice U from the first to the Xth character
 x        :Reduce by addition

```

# Answer
> 1 votes
# , 18 bytes

```
[:+/"."0".@{."0 1]

```

## Explanation

Takes a string as input

```
           {."0 1  - take
    "."0           - current char as int items
                 ] - from the argument
         ".        - and convert them to an integer
[:+/               - add them up

```

Try it online!

# Answer
> 1 votes
# Stax, 6 bytes

```
ç╫&º±å

```

Run and debug it online

The corresponding ascii representation of the same program is this.

```
EZFy(e+

E        get array of digits
 Z       push 0 under array of digits
  F      for each digit, run the rest of the program
   y     input as a string
    (    get start of string for specified number of characters
     e   evaluate substring as integer
      +  add

```

# Answer
> 0 votes
# Actually, 10 bytes

```
╝ß⌠≈╛H≈⌡MΣ

```

Try it online!

# Explanation

```
╝          Push input to register 1
 ß         Push n-th input (0 by default)
        M  Map
  ⌠    ⌡   Function
   ≈       Cast current character of input to int
    ╛      Get value of register 1 (input)
     H     Push input[:current character]
      ≈    Cast to int
         Σ Sum

```

# Answer
> 0 votes
# JavaScript, 43 bytes

It's well after 3 in the morning, why am I still golfing?!

Takes input as a string.

```
s=>(g=x=>s[x]?+s.slice(0,s[x])+g(++x):0)(0)

```

Try it online

# Answer
> 0 votes
# Perl 5, 26 bytes

Includes `+1` for `p`

```
perl -pE 's%.%/.{0,$&}/;$\+=$&%eg}{' <<< 2315; echo

```

# Answer
> 0 votes
# K4, 22 bytes

**Solution:**

```
+/10/:'(x&#x)#\:x:10\:

```

**Examples:**

```
q)k)+/10/:'(x&#x)#\:x:10\:13214
1468
q)k)+/10/:'(x&#x)#\:x:10\:1301
132
q)k)+/10/:'(x&#x)#\:x:10\:251
278
q)k)+/10/:'(x&#x)#\:x:10\:2315
2571

```

**Explanation:**

Break into base-10, take min of each number and the length of list from this. Convert back and sum up.

```
+/10/:'(x&#x)#\:x:10\: / the solution
                  10\: / to base 10, 123 => 1 2 3
                x:     / save as x
             #\:       / take (#) each left
       (    )          / the left
          #x           / count (#) length of x
        x&             / min of x and the length
  10/:'                / from base 10 each
+/                     / sum up the results

```

# Answer
> 0 votes
# Java 8, 92 bytes

```
n->n.chars().map(c->(c-=48)>0?new Integer(n.substring(0,c<n.length()?c:n.length())):0).sum()

```

**Explanation:**

Try it online.

```
n->                                  // Method with String parameter and int return-type
  n.chars()                          //  Loop over the characters
   .map(c->(c-=48)                   //   Convert character to digit
        >0?                          //    And if it's larger than 0
         new Integer(n.substring(0,  //     Take the first `x` digits, where `x` is:
          c<n.length()?              //      If the digit higher than the total a.o. digits
           c                         //       Take the first `c` digits
          :                          //      Else:
           n.length()))              //       Take all digits
         :                           //    Else:
          0)                         //     Take 0
   .sum()                            //   And sum everything

```

# Answer
> 0 votes
**REXX 118 bytes**

```
pull n
l=length(n)
a=0
j=1
do while (j<=l)
if substr(n,j,1)==0 then m=0;
else m=substr(n,1,substr(n,j,1));
a=a+m
j=j+1
end
say a

```

Try it here
Provide Input value in the STDIN tab.

# Answer
> 0 votes
# Python 3, 66 bytes

```
lambda n:sum([int(str(n)[:int(i)])if i!='0'else 0for i in str(n)])

```

Try it online!

# Answer
> 0 votes
# Jelly, 6 bytes

```
DµḣµVS

```

Try it online!

Get the `D`igits of the input, then get the first \[each digit\] elements of the input (ead), then e`V`al each sum to make it a number again and `S`um.

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


title: Tips for golfing in Underload

text:
# Question
Title: Tips for golfing in Underload
Underload is a stack-based semi-functional tarpit created by ais523. I've recently been trying to golf in it, as it's a surprisingly elegant language.

What tips do you have for golfing in Underload? (One tip per answer)

# Answer
## Use `*` for output

Because you can output by leaving a string on the stack, it might be useful to accumulate the string by using `*` rather than outputting with `S`. Say your challenge was "take a string and append a space", the way to do it with output would be:

```
S( )S

```

The way to do it with `*`, on the other hand is one byte shorter:

```
( )*

```

The problem is that if your output has a lot of accumulation, it might cost bytes to deal with the output element on the stack.
> 4 votes

# Answer
## "Dirty" Decrement

The functionally-pure way to decrement a Church numeral is to use the lambda calculus predecessor function:

```
\n.n(\p.\z.z($(pT))(pT))(\z.z0[whatever you define the predecessor of 0 to be])

```

Where 0 = \x.\y.y, T = \x.\y.x, and $ is the successor.

Rewritten in Underload, this is 28 bytes:

```
(!())~(!())~(!:(:)~*(*)*~)~^!

```

This is alright, but we can exploit some of Underload's useful properties, namely that `:!` and `()*` do are no-ops. This means that, for a number `n`, `:ⁿ!!()()*ⁿ` (where `cⁿ` is `c` repeated `n` times) yields n-1. For example doing this for the Church numeral 3 yields this:

```
:::!!()()***

```

Removing no-op pairs, we get:

```
:*

```

Which is 2.

So this is the new and shorter predecessor operation:

```
:(:)~^(!!()())*~(*)~^*

```

This is 7 bytes shorter.
> 3 votes

# Answer
# Use a dictionary of repeatedly reused functions

If you need to use a piece of code a lot, it makes sense to store that code on the stack and duplicate-and-eval it every now and then. So far, that's just normal Underload programming. Unfortunately, keeping a value around on the stack for a long time is difficult and tends to cause your code to become verbose, and that's true even if the value is a function rather than data. This gets a lot worse if you have multiple functions that need to be reused repeatedly.

In the sort of larger program that might benefit from several reused functions, a solution you can use is to instead make one large function that can fulfil any of their purposes depending on the way it's called (either based on what's underneath it on the stack, or via using longer calling sequences than just `^`; a carefully written function can distinguish `^^` from `^:^` from `^*^` from `^~^`, giving you four distinct, fairly short sequences). You can also store other useful things, such as strings that you use multiple times, in this "dictionary". Note that if you use the dictionary heavily, it may make sense to make it a kind of quine, pushing a copy of itself back onto the stack, so that you don't need to manually copy it with `:` to be able to use it without losing the ability to use it in the future.
> 2 votes

# Answer
# Choose data formats specialized to the operations the problem needs

As a simple example, the most commonly seen implementation of booleans are `!()` for false (i.e. integer 0), and the null string for true (i.e. integer 1), but if you have a problem that's heavily based around logical XOR, it might make more sense to use the null string for false, and `~` for true (this data format can be converted into any other boolean format using `(false)~(true)~^!`, and allows the very terse implementation `*` for XOR.

It's possible to take this general principle even further and use functions that your program will need later as part of your data values; that saves having to store the functions and data separately on the stack. This can make the control flow rather more confusing, but when golfing, maintainability often has to take a back seat, and it's not like Underload is all that usable anyway.
> 2 votes

# Answer
# Put Unneeded Stack Values into the Program Space

Underload actually has two stacks—the stack of strings, and the stack of commands that make up the source code. Underload's `^` instruction lets us move strings from the former stack to the latter. By doing this, we can save a lot of unnecessary stack manipulation.

For example, say we have `(a)(b)(c)` on the main stack and we'd like to concatenate the bottom two elements, ignoring `(c)`, to get `(ab)(c)`. The naïve way to do this is to rotate the stack to get `(c)(a)(b)` and then concantenate and swap back:

```
a~a~*~a*^*~

```

This is bad. Using `a~a~*~a*^` to rotate the stack like this is extremely costly, and should be avoided when possible. By putting `(c)` into the program space instead, this can be made four bytes shorter:

```
a(*)~*^

```

The idea is to take the instructions you'd like to execute and then add an instruction to push `(c)` back at the end, and then evaluate the result. This means that we don't have to worry about `(c)` until it's pushed back after we've finished.
> 1 votes

---
Tags: code-golf, tips, underload
---


title: Convergence of a Markov Process

text:
# Question
Title: Convergence of a Markov Process
# Challenge

Given a left- or right-stochastic matrix where the limit as x approaches infinity of the matrix to the power of x approaches a matrix with all finite values, return the matrix to which the matrix converges. Basically, you want to keep multiplying the matrix by itself until the result no longer changes.

# Test Cases

```
[[7/10, 4/10], [3/10, 6/10]] -> [[4/7, 4/7], [3/7, 3/7]]
[[2/5, 4/5], [3/5, 1/5]] -> [[4/7, 4/7], [3/7, 3/7]]
[[1/2, 1/2], [1/2, 1/2]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/3, 2/3], [2/3, 1/3]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/10, 2/10, 3/10], [4/10, 5/10, 6/10], [5/10, 3/10, 1/10]] -> [[27/130, 27/130, 27/130], [66/130, 66/130, 66/130], [37/130, 37/130, 37/130]]
[[1/7, 2/7, 4/7], [2/7, 4/7, 1/7], [4/7, 1/7, 2/7]] -> [[1/3, 1/3, 1/3], [1/3, 1/3, 1/3], [1/3, 1/3, 1/3]]

```

# Rules

* Standard Loopholes Apply
* You may choose whether you want a right- or a left-stochastic matrix
* You may use any reasonable number type, such as floats, rationals, infinite precision decimals, etc
* This is , so the shortest submission in bytes for each language is declared the winner for its language. No answer will be accepted

# Answer
# ,  ~~44~~  43 bytes

```
function(m){X=m
while(any(X-(X=X%*%m)))0
X}

```

Try it online!

Just keeps multiplying until it finds a fixed matrix. Apparently `X!=(X=X%*%m)` does the comparison, then reassigns `X`, so that's neat.

Thanks to @Vlo for shaving off a byte; even though crossed out 44 is still regular 44.
> 7 votes

# Answer
# Octave, ~~45~~ ~~42~~ 35 bytes

```
@(A)([v,~]=eigs(A,1))/sum(v)*any(A)

```

Try it online!

Saved 3 bytes thanks to Giuseppe, and 7 more thanks to Luis Mendo!

This uses that the eigenvector corresponding to the eigenvalue 1 (also the maximum eigenvalue) is the column vector that is repeated for each value of the limiting matrix. We have to normalise the vector to have sum 1 for it to be stochastic, then we simply repeat it to fill out the matrix. I'm not too well versed in golfing Octave, but I haven't been able to find a functional way to do repeated multiplication, and a full program seems like it will always be longer than this.

We can use `any(A)` since from the restrictions we know that the matrix must describe an irreducible Markov chain, and so each state must be reachable from the other states. Therefore at least one value in each column must be non-zero.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 14 bytes

Output floats:

```
N@#//.x_:>x.#&

```

Try it online!

---

# Wolfram Language (Mathematica), 30 bytes

Output fractions:

```
Limit[#~MatrixPower~n,n->∞]&

```

Try it online!
> 4 votes

# Answer
# Jelly, 6 bytes

```
æ×³$ÐL

```

This is a full program.

Try it online!
> 3 votes

# Answer
# APL (Dyalog), ~~18~~ 6 bytes

*12 bytes saved thanks to @H.PWiz*

```
+.×⍨⍣≡

```

Try it online!
> 3 votes

# Answer
# C (gcc), ~~207~~ ~~192~~ ~~190~~ ~~181~~ 176 bytes + 2 flag bytes `-lm`

* Saved ~~fifteen~~ ~~seventeen~~ twenty-two bytes thanks to ceilingcat.
* Saved nine bytes; removing `return A;`.

```
float*f(A,l,k,j)float*A;{for(float B[l*l],S,M=0,m=1;fabs(m-M)>1e-7;wmemcpy(A,B,l*l))for(M=m,m=0,k=l*l;k--;)for(S=j=0;j<l;)m=fmax(m,fdim(A[k],B[k]=S+=A[k/l*l+j]*A[k%l+j++*l]));}

```

Try it online!
> 3 votes

# Answer
# k/q, 10 bytes

k/q because the program is identical in both languages. The code is really just idiomatic k/q.

```
{$[x]/[x]}

```

### Explanation

`{..}` is out lambda syntax, with `x` as an implicit parameter

`$[x]` has $ as the binary matrix multiplication operator, providing only one parameters creates a unary operator that left multiplies by the Markov Matrix

`/[x]` applies the left multiplication until convergence, starting with x itself.
> 3 votes

# Answer
# Python 3, ~~75~~ 61 bytes

```
f=lambda n:n if allclose(n@n,n)else f(n@n)
from numpy import*

```

Try it online!

In test cases there are float inaccuracies, so the values may differ by a bit from the exact fractions.

PS. `numpy.allclose()` is used because `numpy.array_equal()` is longer and prone to float inaccuracies.

-14 bytes Thanks HyperNeutrino ;) Oh yes I forgot the @ operator ;P
> 2 votes

# Answer
# Java 8, ~~356~~ 339 bytes

```
import java.math.*;m->{BigDecimal t[][],q;RoundingMode x=null;for(int l=m.length,f=1,i,k;f>0;m=t.clone()){for(t=new BigDecimal[l][l],i=l*l;i-->0;)for(f=k=0;k<l;t[i/l][i%l]=(q!=null?q:q.ZERO).add(m[i/l][k].multiply(m[k++][i%l])))q=t[i/l][i%l];for(;++i<l*l;)f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?f:1;}return m;}

```

-17 bytes thanks to *@ceilingcat*.

Definitely not the right language.. Damn floating point precision..

**Explanation:**

Try it online.

```
import java.math.*;     // Required import for BigDecimal and RoundingMode
m->{                    // Method with BigDecimal-matrix as both parameter and return-type
  BigDecimal t[][],q;   //  Temp BigDecimal-matrix
  RoundingMode x=null;  //  Static RoundingMode value to reduce bytes
  for(int l=m.length,   //  The size of the input-matrix
          f=1,          //  Flag-integer, starting at 1
          i,k;          //  Index-integers
      f>0;              //  Loop as long as the flag-integer is still 1
      m=t.clone()){     //    After every iteration: replace matrix `m` with `t`
    for(t=new BigDecimal[l][l],
                        //   Reset matrix `t`
        i=l*l;i-->0;)   //   Inner loop over the rows and columns
      for(f=k=0;        //    Set the flag-integer to 0
          k<l           //    Inner loop to multiply
          ;             //      After every iteration:
           t[i/l][i%l]=(q!=null?q:q.ZERO).add(
                        //       Sum the value at the current cell in matrix `t` with:
             m[i/l][k]  //        the same row, but column `k` of matrix `m`,
             .multiply(m[k++][i%l])))
                        //        multiplied with the same column, but row `k` of matrix `m`
        q=t[i/l][i%l];  //     Set temp `q` to the value of the current cell of `t`
    for(;++i<l*l;)      //   Loop over the rows and columns again
      f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?
                        //    If any value in matrices `t` and `m` are the same:
         f              //     Leave the flag-integer unchanged
        :               //    Else (they aren't the same):
         1;}            //     Set the flag-integer to 1 again
  return m;}            //  Return the modified input-matrix `m` as our result

```
> 2 votes

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


title: Output the HTML colors

text:
# Question
Title: Output the HTML colors
The 16-color CGA palette (also known as the HTML colors) is a set of 16 colors used by early graphics adapters. The goal of this challenge is to output all 16 of them, in hex format (`RRGGBB`), in ascending order by hex value, separated by newlines. Thus, the output should be exactly this:

```
000000
000080
0000FF
008000
008080
00FF00
00FFFF
800000
800080
808000
808080
C0C0C0
FF0000
FF00FF
FFFF00
FFFFFF

```

A single trailing newline is allowed, but not required.

# Answer
# Jelly, ~~31~~ ~~29~~ 27 bytes

```
“×Ɗ¡‘ŒP»Ṫ¦209ṗ€3Fd⁴ịØHs3ṢQY

```

Try it online!

### How it works

`“×Ɗ¡‘` yield the code points of the characters between the quotes in Jelly's SBCS, which are **0x11 = 17**, **0x91 = 145**, and **0x00 = 0**.

`ŒP` constructs the powerset of the array of code points, yielding

```
[[], [17], [145], [0], [17, 145], [17, 0], [145, 0], [17, 145, 0]]

```

The last two entries correspond to combinations that contain both **80** and **FF**, so we have to discard them.

`»Ṫ¦209` consists of three parts:

* (tail) removes the last array of code points, i.e., **\[17, 145, 0\]**.
* `»209` takes the maximum of each integer in the remainder of the powerset and **0xD1 = 209**, replacing all of them with **209**.
* `¦` (sparse) iterates over the elements of the remainder of the powerset. If the corresponding index is found in **\[17, 145, 0\]**, the element is replaced with all **209**'s. If not, it is left untouched.

`¦` isn't modular, so this modifies only the last array (index **0**) in the remainder of the powerset. The indices **17** and **145** are too large and have no effect.

The result is as follows.

```
[[], [17], [145], [0], [17, 145], [17, 0], [209, 209]]

```

`ṗ€3` computes the third Cartesian power of each array, i.e., the array of all 3-tuples of elements of each array.

`Fd⁴` flattens the result and computes quotient and remainder of each integer divided by **16**.

`ịØH` indexes (1-based) into **"0123456789ABCDEF**, so **0x11**, **0x91**, **0x00**, and **0xD1** get mapped to **"00"**, **"80"**, **"FF"**, and **"C0"** (resp.).

`s3ṢQ` splits the character pairs into 3-tuples, sorts the tuples, and deduplicates.

Finally, `Y` joins the unique tuples, separating by linefeeds.
> 13 votes

# Answer
# Bash + GNU Utilities, 67

* 2 bytes saved thanks to @manatwork
* 2 bytes saved thanks to @zeppelin

```
a={00,80,FF}
eval echo $a$a$a|fmt -w9|sed '16iC0C0C0
/F0*8\|80*F/d'

```
* The brace expansion `{00,80,FF}{00,80,FF}{00,80,FF}` gives all need combinations in the right order (excluding `C0C0C0`), along some extras. The extras are the ones that contain both `F` and `8` characters.
* The result of the brace expansion is a single space-separated line. `fmt` puts each entry on its own line
* The 1st line of the `sed` expression inserts `C0C0C0` in the appropriate line
* The 2nd line of the `sed` expression filters out the "extras" described above.

Ideone.
> 11 votes

# Answer
# Jelly, ~~38~~ 31 bytes

```
“mạ9ṣṃwɠƁ,¡ẓw’b4µża1$ị“08CF”s3Y

```

**TryItOnline!**

Base 250 compression of a number (`“...’`),
converted to base 4 (`b4`),
zipped (`ż`) with a copy of itself after a vectorised logical-and with 1 (`a1$`)\*,
indexed () into the four characters used (`“08CF”`),
split into chunks of length 3 (`s3`),
and joined with line feeds (`Y`).

* Thus pairing each zero digit with another zero and each of any other digits with a one. Along with the following indexed fetch this means `'F'` becomes paired with another `'F'` while `'0'`,`'8'`, and `'C'` each pair with a `'0'`.
> 6 votes

# Answer
# Python 3, ~~134~~ ~~129~~ ~~125~~ ~~108~~ ~~91~~ 90 bytes

I think there is still a lot of golfing to do here. Golfing suggestions welcome!

**Edit:** -9 bytes and many thanks to Mego for helping with the string formatting. -17 bytes from figuring out a better way to print the string in the first place. -17 bytes from figuring out a better way to write the for loop in the first place. -1 byte thanks to xnor's tip to use `i%3//2*"\n"` instead of `"\n"*(i%3<2)`.

```
for i in range(48):print(end="F0C8F000"[0x10114abf7f75c147d745d55//4**i%4::4]+i%3//2*"\n")

```

**Ungolfing**

```
z = 0
a = [0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 2, 2, 2, 3, 3, 3, 1, 3, 3, 3, 1, 3, 1, 1, 3, 0, 0, 1, 1, 0, 1, 3, 3, 1, 1, 3, 1, 0, 1, 1, 3, 1, 1, 1, 1, 1]
for i in range(len(a)):
    z = (z + a[i]) * 4
z //= 4                   # we multiplied by 4 one too many times
for i in range(48):
    m = z // 4**j % 4
    s = "F0C8F000"[c::4]
    if i % 3 == 2:
        s += "\n"
    print(s, end="")

```
> 3 votes

# Answer
## JavaScript (ES6), ~~109~~ 107 bytes

*Saved 2 bytes, thanks to Neil*

This is ~~7~~ 9 bytes shorter than just returning the raw string in backticks.

```
_=>[...'1121173113106393'].map(v=>[4,2,0].map(x=>'08CF'[x=n>>x&3]+'000F'[x],n+=+v||21).join``,n=-1).join`
`

```

### Test

```
let f =

_=>[...'1121173113106393'].map(v=>[4,2,0].map(x=>'08CF'[x=n>>x&3]+'000F'[x],n+=+v||21).join``,n=-1).join`
`

console.log(f())
```
> 2 votes

# Answer
## PowerShell, ~~113~~ 106 bytes

```
'777
7780
77FF
7807
78080
7FF7
7FFFF
8077
80780
80807
808080
C0C0C0
FF77
FF7FF
FFFF7
FFFFFF'-replace7,'00'

```

~~Yeah, I haven't found anything shorter than just printing the literal string...~~ Thanks to @Martin Smith for shaving down 7 bytes using a simple replacement (which I completely overlooked). So, we're at least 7 bytes shorter than simply hardcoding it. Yay!

***But that's boring!***

So instead ...

## PowerShell v4, 128 bytes

```
[consolecolor[]](0,7+9..15)+-split'Lime Maroon Navy Olive Purple Silver Teal'|%{-join"$([windows.media.colors]::$_)"[3..8]}|sort

```

The `[system.consolecolor]` namespace defines the console colors (natively) available to the PowerShell console. If we reference them via an integer array like this, the default value is the name (e.g., `Black` or `White` or the like). We combine that with a string that has been `-split` on spaces, so now we have an array of strings of color names.

We loop through those `|%{...}` and each iteration pull out the corresponding `[system.windows.media.colors]` value. The default stringification for those objects is the color in `#AARRGGBB` format as a hex value, so we leverage that by encapsulating that call in a string with a script block `"$(...)"`. But, since we don't want the alpha values or the hash, we take the back end `[3..8]` of the string, and need to `-join` that resulting `char`-array back into a string. Then, a simple `Sort-Object` to put them in the right order.
> 2 votes

# Answer
# Pyth - ~~64~~ ~~48~~ 44 bytes

Super simple base compression.

```
jcs@L"FC80"jC"ÿÿûÿ¿û¿ðÿ¿»¿»·wðð\0ð\0"4 6

```

Try it online here.
> 1 votes

# Answer
# MATL, 39 bytes

```
'80FFC000'2e'3na:1Fswv1=`uIn'F4:ZaZ)6e!

```

Try it online!

```
'80FFC000'         % Push this string
2e                 % Reshape with 2 rows. So 1st column contains '80', 2nd 'FF' etc
'3na:1Fswv1=`uIn'  % Push this string
F4:Za              % Convert from base 95 to alphabet [1 2 3 4]
Z)                 % Use as column indices into the first string
6e!                % Reshape with 6 rows and transpose.
                   % Implicitly display

```
> 1 votes

# Answer
# 05AB1E, 57 bytes

```
•P{Ætg7«r¨ëÅ,…}ù¢Ý%Vt®£8ãøÚ$0óDÛY²Zþ…ð7ê‘Ó{òìàYëØU¥•hR6ô»

```

Try it online!

What we need to output is basically (reversed and split):

```
FFFFFF00FFFFFF00FF0000FF0C0C0C080808000808080008000008FFFF0000FF00080800000800FF0000080000000000

```

Which, in decimal is:

```
39402003857025890357721060524755992261661062099432941475272448103296644696683709026793043150430945208910007869898752

```

Which in Base-214 is:

```
P{Ætg7«r¨ëÅ,…}ù¢Ý%Vt®£8ãøÚ$0óDÛY²Zþ…ð7ê‘Ó{òìàYëØU¥

```

This is the simplest solution I could come up with, because there's no way in hell I'm beating Dennis. Spent an hour trying and nothing beat his idea.
> 1 votes

# Answer
# PHP, 92 Bytes

```
<?=strtr("000
001
002
010
011
020
022
100
101
110
111
333
200
202
220
222",["00",80,FF,CO]);

```

Try it online!

simply replacement from the digits as key in the array with the values strtr
> 1 votes

# Answer
## Batch, 137 bytes

```
@for %%c in (000000 000080 0000FF 008000 008080 00FF00 00FFFF 800000 800080 808000 808080 C0C0C0 FF0000 FF00FF FFFF00 FFFFFF)do @echo %%c

```

Yes, it's that boring. Previous 148-byte attempt:

```
@if "%2"=="" (call %0 000000 80&call %0 C0C0C0 FF)|sort&exit/b
@echo %1
@for %%c in (0000%2 00%200 00%2%2 %20000 %200%2 %2%200 %2%2%2)do @echo %%c

```

Unfortunately you can't pipe the output of a `for` or a `call:` command, so I have to invoke myself recursively.
> 0 votes

# Answer
## Pyke, 42 bytes

```
"80FF"2c8DF3"00"]F3+b2tRT`_R.:(s}"C0"3*+SJ

```

Try it here!
> 0 votes

# Answer
# Befunge, ~~83~~ 69 bytes

```
<v"UVTYZQPefij?EDA@"
v>>9\:4/:\4/>4%:3g,0`
<^_@#:,+55$_^#!-9:,g3
F08C

```

Try it online!

The colours are encoded in the string you see on the first line, two bits per colour component, with an additional high bit set to force each value into the ASCII range (except in the case of 63, which would be out of range as 127).

The list of colours on the stack is then processed as follows:

```
9\          9 is pushed behind the current colour to serve as a marker.
:4/:\4/     The colour is repeatedly divided by 4, splitting it into 3 component parts.

>           The inner loop deals with each of the 3 components.
 4%         Modulo 4 masks out the 2 bits of the colour component that we care about.
 :3g,       That is used as an index into the table on line 4 to get the character to output.
 0`3g,      For component values greater than 0 the second char is a '0', otherwise an 'F'.
 :9-!       Check if the next component is our end marker.
^           If not, repeat the inner loop.

55+,        Output a newline.
:_          Repeat the outer loop until there are no more colours on the stack.

```
> 0 votes

# Answer
# C#, 195 bytes

```
void n(){string a="000000\r\n000080\r\n0000FF\r\n008000\r\n008080\r\m00FF00\r\n00FFFF\r\n800000\r\n800080\r\n808000\r\n808080\r\nC0C0C0\r\nFF0000\r\nFF00FF\r\nFFFF00\r\nFFFFFF";Console.Write(a);}

```

Sadly this beats, by a huge margin, the more interesting albeit incredibly convoluted (I had tons more fun writing it) **C#, 270 bytes**

```
void n(){string a,b,c,d;a="00";b="80";c="C0";d="FF";for(int i=0;i<16;i++){Console.WriteLine((i<7?a:i<11?b:i>11?d:c)+(i<3?a:i<5?b:i<7?d:i<9?a:i<11?b:i==11?c:i<14?a:d)+(i==0||i==3||i==5|i==7||i==9||i==12||i==14?a:i==1||i==4||i==8||i==10?b:i==2||i==6||i==13||i==15?d:c));}}

```
> 0 votes

# Answer
# C (gcc), 99 bytes

```
f(i){for(i=48;i--;)printf("%.2s%s","FFC08000"+("#&/28MNQRSV]^_ab"[i/3]-35>>i%3*2&3)*2,"\n\0"+i%3);}

```

Try it online!

After having made an attempt involving creating a list of numbers and outputting them while sorting, I compared to the naïve solution, which was sobering:

```
f(){puts("000000\n000080\n0000FF\n008000\n008080\n00FF00\n00FFFF\n800000\n800080\n808000\n808080\nC0C0C0\nFF0000\nFF00FF\nFFFF00\nFFFFFF");}

```

That one clocks in at 140 bytes compared to my try at 200 and change.

The solution was to think of it as text like any other, albeit with a small alphabet. Each colour could be thought of as a triplet of 2-bit indices into the alphabet {0xff, 0xc0, 0x80, 00}. The process of colour -\> triplet -\> number -\> character (with offset +35 to make them all printable and avoid any need for escapes) can be illustrated as such:

```
000000  333     63  b
000080  332     62  a
0000FF  330     60  _
008000  323     59  ^
008080  322     58  ]
00FF00  303     51  V
00FFFF  300     48  S
800000  233     47  R
800080  232     46  Q
808000  223     43  N
808080  222     42  M
C0C0C0  111     21  8
FF0000  033     15  2
FF00FF  030     12  /
FFFF00  003     3   &
FFFFFF  000     0   #

```

Then it's just a matter of iterating over the resulting string and cutting out the appropriate parts of the alphabet string.
> 0 votes

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