title: 8bit virtual machine

text:
# Question
Title: 8bit virtual machine
### Background

I like my old 8-bit 6502 chip. It's even fun to solve some of the challenges here on PPCG in 6502 machine code. But some things that should be simple (like, read in data or output to stdout) are unnecessarily cumbersome to do in machine code. So there's a rough idea in my mind: Invent my own 8-bit virtual machine that's inspired by the 6502, but with the design modified to be more usable for challenges. Starting to implement something, I realized this might be a nice challenge itself if the design of the VM is reduced to a bare minimum :)

### Task

Implement an 8-bit virtual machine conforming to the following specification. This is , so the implementation with the fewest bytes wins.

### Input

Your implementation should take the following inputs:

* A single unsigned byte `pc`, this is the initial program counter (the address in memory where the VM starts execution, `0`-based)
* A list of bytes with a maximum length of `256` entries, this is the RAM for the virtual machine (with its initial contents)

You may take this input in any sensible format.

### Output

A list of bytes which are the final contents of the RAM after the VM terminates (see below). You can assume you only get input that leads to terminating eventually. Any sensible format is allowed.

### Virtual CPU

The virtual CPU has

* an 8-bit program counter,
* an 8-bit accumulator register called `A` and
* an 8-bit index register called `X`.

There are three status flags:

* `Z` \- the zero flag is set after some operation results in `0`
* `N` \- the negative flag is set after some operation results in a negative number (iow bit 7 of the result is set)
* `C` \- the carry flag is set by additions and shifts for the "missing" bit of the result

Upon start, the flags are all cleared, the program counter is set to a given value and the contents of `A` and `X` are indeterminate.

The 8-bit values represent either

* an *unsigned* integer in the range `[0..255]`
* a *signed* integer, 2's complement, in the range `[-128..127]`

depending on context. If an operation over- or underflows, the value *wraps around* (and in case of an addition, the carry flag is affected).

### Termination

The virtual machine terminates when

* A `HLT` instruction is reached
* A non-existing memory address is accessed
* The program counter runs outside the memory (note it doesn't wrap around even if the VM is given the full 256 bytes of memory)

### Adressing modes

* *implicit* -- the instruction has no argument, the operand is implied
* *immediate* -- the operand is the byte directly after the instruction
* *relative* -- (for branching only) the byte after the instruction is signed (2's complement) and determines the offset to add to the program counter if the branch is taken. `0` is the location of the following instruction
* *absolute* -- the byte after the instruction is the address of the operand
* *indexed* -- the byte after the instruction plus `X` (the register) is the address of the operand

### Instructions

Each instruction consists of an opcode (one byte) and, in the addressing modes *immediate*, *relative*, *absolute* and *indexed* a second argument byte. When the virtual CPU executes an instruction, it increments the program counter accordingly (by `1` or `2`).

All opcodes shown here are in hex.

* `LDA` -- load operand into `A`

+ Opcodes: immediate: `00`, absolute: `02`, indexed: `04`
    + Flags: `Z`, `N`
* `STA` -- store `A` into operand

+ Opcodes: immediate: `08`, absolute: `0a`, indexed: `0c`
* `LDX` -- load operand into `X`

+ Opcodes: immediate: `10`, absolute: `12`, indexed: `14`
    + Flags: `Z`, `N`
* `STX` -- store `X` into operand

+ Opcodes: immediate: `18`, absolute: `1a`, indexed: `1c`
* `AND` -- bitwise *and* of `A` and operand into `A`

+ Opcodes: immediate: `30`, absolute: `32`, indexed: `34`
    + Flags: `Z`, `N`
* `ORA` -- bitwise *or* of `A` and operand into `A`

+ Opcodes: immediate: `38`, absolute: `3a`, indexed: `3c`
    + Flags: `Z`, `N`
* `EOR` -- bitwise *xor* (exclusive or) of `A` and operand into `A`

+ Opcodes: immediate: `40`, absolute: `42`, indexed: `44`
    + Flags: `Z`, `N`
* `LSR` -- logical shift right, shift all bits of operand one place to the right, bit 0 goes to carry

+ Opcodes: immediate: `48`, absolute: `4a`, indexed: `4c`
    + Flags: `Z`, `N`, `C`
* `ASL` -- arithmetic shift left, shift all bits of the operand one place to the left, bit 7 goes to carry

+ Opcodes: immediate: `50`, absolute: `52`, indexed: `54`
    + Flags: `Z`, `N`, `C`
* `ROR` -- rotate right, shift all bits of operand one place to the right, carry goes to bit 7, bit 0 goes to carry

+ Opcodes: immediate: `58`, absolute: `5a`, indexed: `5c`
    + Flags: `Z`, `N`, `C`
* `ROL` -- rotate left, shift all bits of the operand one place to the left, carry goes to bit 0, bit 7 goes to carry

+ Opcodes: immediate: `60`, absolute: `62`, indexed: `64`
    + Flags: `Z`, `N`, `C`
* `ADC` -- add with carry, operand plus carry is added to `A`, carry is set on overflow

+ Opcodes: immediate: `68`, absolute: `6a`, indexed: `6c`
    + Flags: `Z`, `N`, `C`
* `INC` -- increment operand by one

+ Opcodes: immediate: `78`, absolute: `7a`, indexed: `7c`
    + Flags: `Z`, `N`
* `DEC` -- decrement operand by one

+ Opcodes: immediate: `80`, absolute: `82`, indexed: `84`
    + Flags: `Z`, `N`
* `CMP` -- compare `A` with operand by subtracting operand from `A`, forget result. Carry is cleared on underflow, set otherwise

+ Opcodes: immediate: `88`, absolute: `8a`, indexed: `8c`
    + Flags: `Z`, `N`, `C`
* `CPX` -- compare `X` -- same as `CMP` for `X`

+ Opcodes: immediate: `90`, absolute: `92`, indexed: `94`
    + Flags: `Z`, `N`, `C`
* `HLT` -- terminate

+ Opcodes: implicit: `c0`
* `INX` -- increment `X` by one

+ Opcodes: implicit: `c8`
    + Flags: `Z`, `N`
* `DEX` -- decrement `X` by one

+ Opcodes: implicit: `c9`
    + Flags: `Z`, `N`
* `SEC` -- set carry flag

+ Opcodes: implicit: `d0`
    + Flags: `C`
* `CLC` -- clear carry flag

+ Opcodes: implicit: `d1`
    + Flags: `C`
* `BRA` -- branch always

+ Opcodes: relative: `f2`
* `BNE` -- branch if `Z` flag cleared

+ Opcodes: relative: `f4`
* `BEQ` -- branch if `Z` flag set

+ Opcodes: relative: `f6`
* `BPL` -- branch if `N` flag cleared

+ Opcodes: relative: `f8`
* `BMI` -- branch if `N` flag set

+ Opcodes: relative: `fa`
* `BCC` -- branch if `C` flag cleared

+ Opcodes: relative: `fc`
* `BCS` -- branch if `C` flag set

+ Opcodes: relative: `fe`

### Opcodes

The behavior of the VM is undefined if any opcode is found that doesn't map to a valid instruction from the above list.

As per Jonathan Allan's request, you **may** choose your own set of opcodes instead of the opcodes shown in the **Instructions** section. If you do so, you **must** add a full mapping to the opcodes used above in your answer.

The mapping should be a hex file with pairs `<official opcode> <your opcode>`, e.g. if you replaced two opcodes:

```
f4 f5
10 11

```

Newlines don't matter here.

### Test cases (official opcodes)

```
// some increments and decrements
pc:     0
ram:    10 10 7a 01 c9 f4 fb
output: 10 20 7a 01 c9 f4 fb

// a 16bit addition
pc:     4
ram:    e0 08 2a 02 02 00 6a 02 0a 00 02 01 6a 03 0a 01
output: 0a 0b 2a 02 02 00 6a 02 0a 00 02 01 6a 03 0a 01

// a 16bit multiplication
pc:     4
ram:    5e 01 28 00 10 10 4a 01 5a 00 fc 0d 02 02 d1 6a 21 0a 21 02 03 6a 22 0a 22 52
        02 62 03 c9 f8 e6 c0 00 00
output: 00 00 00 00 10 10 4a 01 5a 00 fc 0d 02 02 d1 6a 21 0a 21 02 03 6a 22 0a 22 52
        02 62 03 c9 f8 e6 c0 b0 36

```

I might add more testcases later.

### Reference and testing

To help with own experiments, here's some (totally not golfed) reference implementation -- it can output tracing information (including disassembled instructions) to `stderr` and convert opcodes while running.

Recommended way to get the source:

```
git clone https://github.com/zirias/gvm --branch challenge --single-branch --recurse-submodules

```

Or checkout branch `challenge` and do a `git submodule update --init --recursive` after cloning, to get my custom build system.

Build the tool with GNU make (just type `make`, or `gmake` if on your system, the default make isn't GNU make).

**Usage**: `gvm [-s startpc] [-h] [-t] [-c convfile] [-d] [-x] <initial_ram`

* `-s startpc` -- the initial program counter, defaults to `0`
* `-h` -- input is in hex (otherwise binary)
* `-t` -- trace execution to `stderr`
* `-c convfile` -- convert opcodes according to a mapping given in `convfile`
* `-d` -- dump resulting memory as binary data
* `-x` -- dump resulting memory as hex
* `initial_ram` -- the initial RAM contents, either hex or binary

**Note** the conversion feature will fail on programs that modify opcodes while running.

**Disclaimer:** The rules and specs above are authorative for the challenge, not this tool. This especially applies to the opcode conversion feature. If you think the tool presented here has a bug wrt the specs, please report in a comment :)

# Answer
# C (gcc), ~~1381~~ ~~1338~~ ~~1255~~ 1073 bytes

Huge improvement thanks to ceilingcat and Rogem.

```
#include<stdio.h>
C*F="%02hhx ";m[256],p,a,x,z,n,c,e;g;*I(){R++p+m;}*A(){R*I()+m;}*X(){R*I()+m+x;}C*Q(){W(printf,m[g],1)exit(a);}C*(*L[])()={I,Q,A,Q,X,Q,Q,Q};l(C*i){R 254/p?*i=*L[m[p]&7]():*Q();}s(i){R 254/p?*L[m[p]&7]()=i:*Q();}q(){p>254?Q():++p;}C*y(){p+=e;}B(U,z)B(V,!z)B(_,n)B(BM,!n)B(BC,c)B(BS,!c)C*(*b[])()={Q,Q,y,Q,U,Q,V,Q,_,Q,BM,Q,BC,Q,BS,Q};j(){z=!l(&a);v}o(){s(a);}t(){z=!l(&x);n=x&H;}D(){s(x);}f(K(&=)h(K(|=)i(K(^=)J(E;c=e&1;z=!(e/=2);s(e);w}k(E;c=w;z=!e;s(e*=2);}T(E;g=e&1;z=!(e=e/2|H*!!c);c=g;s(e);w}M(E;g=w z=!(e=e*2|H*!!c);c=g;s(e);}N(E;z=!(a=g=a+e+!!c);c=g>>8%2;G}P(E;z=!~e;--p;s(g=e+1);G}u(E;g=e-1;z=!g;--p;s(g);G}r(E;g=a-e;z=!g;c=G}S(E;g=x-e;z=!g;c=G}Y(){z=!(x=g=1-m[p]%2*2);n=x&H;}Z(){c=~m[p]&1;}d(){p<255||Q();e=m[++p];b[m[p-1]&15]();}(*O[])()={j,o,t,D,Q,Q,f,h,i,J,k,T,M,N,Q,P,u,r,S,Q,Q,Q,Q,Q,Q,Y,Z,Q,Q,Q,d,d};main(){scanf(F,&p);W(scanf,&m[g],0)for(;;q())O[m[p]/8]();}

```

Try it online!

A lot of defines moved to compiler flags.

Explanation (VERY ungolfed):

```
#include<stdio.h>

// useful defines
#define C unsigned char
#define H 128 // highest bit
#define R return

// code generator for I/O
#define W(o,p,q)for(g=-1;++g<256&&((q)||!feof(stdin));)(o)(F,(p));

// code generator for branching instruction handlers
#define BB(q)(){(q)||Y();}

// frequent pieces of code
#define NA n=a&H;
#define NE n=e&H;
#define NG n=g&H;
#define E l(&e)

// printf/scanf template
C * F = "%02hhx ";

// global state: m=memory, pax=registers, znc=flags
// e and g are for temporaries and type conversions
C m[256],p,a,x,z,n,c,e;g;

// get the pointer to a memory location:
C * I() {R &m[++p];} // immediate
C * A() {R &m[m[++p]];} // absolute
C * X() {R &m[m[++p]+x];} // indexed

// terminate the VM (and dump memory contents)
C * Q() { W(printf,m[g],1) exit(a);}

// an array of functions for accessing the memory
// They either return the pointer to memory location
// or terminate the program.
C * (*L[])()={I,Q,A,Q,X,Q,Q,Q};

// load a byte from the memory into the variable pointed by i
// terminate the program if we cannot access the address byte
l (C * i) {return 254 / p ? *i = *L[m[p]&7] () : *Q ();}

// save a byte i to the memory
// terminate the program if we cannot access the address byte
s (C i) {return 254 / p ? *L[m[p]&7]() = i : *Q ();}

// advance the instruction pointer (or fail if we fall outside the memory)
q () {p > 254 ? Q () : ++p;}

// branch
C * Y() {p += e;}

// generated functions for conditional branches
C * BN BB(z)
C * BZ BB(!z)
C * BP BB(n)
C * BM BB(!n)
C * BC BB(c)
C * BS BB(!c)

// a list of branch functions
C * (*B[])() = {Q,Q,Y,Q,BN,Q,BZ,Q,BP,Q,BM,Q,BC,Q,BS,Q};

// Instruction handling functions

OA () {z = !l (&a); NA} // lda
OB () {s (a);} // sta
OC () {z = !l (&x); n = x & H;} // ldx
OD () {s (x);} // stx
OG () {E; z = !(a &= e); NA} // and
OH () {E; z = !(a |= e); NA} // ora
OI () {E; z = !(a ^= e); NA} // eor
OJ () {E; c = e & 1; z = !(e /= 2); s (e); NE} // lsr
OK () {E; c = NE; z = !e; s (e *= 2);} // asl
OL () {E; g = e & 1; z = !(e = e / 2 | H * !!c); c = g; s (e); NE} // ror
OM () {E; g = e & H; z = !(e = e * 2 | H * !!c); c = g; s (e); NE} // rol
ON () {E; z = !(a = g = a + e + !!c); c = !!(g & 256); NG} // adc
OP () {E; z = !~e; --p; s (g = e + 1); NG} // inc
OQ () {E; g = e - 1; z = !g; --p; s (g); NG} // dec
OR () {E; g = a - e; z = !g; c = NG} // cmp
OS () {E; g = x - e; z = !g; c = NG} // cpx
OY () {z = !(x = g = ~m[p] & 1 * 2 - 1); n = x & H;} // inx/dex
OZ () {c = ~m[p] & 1;} // sec/clc
Od () {p < 255 || Q (); e = m[++p]; B[m[p-1]&15] ();} // branching

// list of opcode handlers
(*O[]) () = {OA,OB,OC,OD,Q,Q,OG,OH,OI,OJ,OK,OL,OM,ON,Q,OP,OQ,OR,OS,Q,Q,Q,Q,Q,Q,OY,OZ,Q,Q,Q,Od,Od};

// main function
main ()
{
    // read the instruction pointer
    scanf (F, &p);

    // read memory contents
    W(scanf, &m[g], 0)

    // repeatedly invoke instruction handlers until we eventually terminate
    for (;; q())
        O[m[p]/8] ();
}

```
> 17 votes

# Answer
# C (gcc), ~~487~~, ~~480~~, ~~463~~, ~~452~~, ~~447~~, 438 bytes

Uses this instruction mapping. The update to the instructions shaved off 9 bytes, and potentially more in the future. Returns by modifying the memory pointed to by the first argument (`M`). Thanks to @ceilingcat for shaving off some bytes.

Must be compiled with flags `-DO=*o -DD=*d -DI(e,a,b)=if(e){a;}else{b;} -Du="unsigned char"` (already included in bytes).

```
e(M,Z,C)u*M,C;{for(u r[2],S=0,D,O,c,t;o=C<Z?M+C++:0;){I(c=O,d=r+!(c&4),break)I(o=c&3?C<Z&&C?M+C++:0:d,o=c&2?O+c%2**r+M:o,break)t=(c/=8)&7;I(c<24&c>4&&t,t&=3;I(c&8,I(c&4,c&=S&1;S=O>>7*!(t/=2);O=t=O<<!t>>t|c<<7*t,t=O+=t%2*2-1),I(c&4,D=t=t?t&2?t&1?O^D:O|D:O&D:O,I(c&1,S=D>(t=D+=O+S%2),t=D-O;S=t>D)))S=S&1|t>>6&2|4*!t,I(c&8,C+=!(t&~-t?~t&S:t&~S)*O,I(t,S=S&6|c%2,O=D)))I(C,,Z=0)}}

```

Try it online!

### Preprocessor

```
-DO=*o -DD=*d

```

These two provide a shorter way to dereference the pointers.

```
-DI(e,a,b)=if(e){a;}else{b;} -Du="unsigned char"

```

Reduce the number of bytes needed for if-elses and type declarations.

### Code

The below is a human-readable version of the code, with the preprocessor directives expanded, and variables renamed for readability.

```
exec_8bit(unsigned char *ram, int ramSize, unsigned char PC)
{
  for(unsigned char reg[2], SR=0, // The registers.
                                  // reg[0] is X, reg[1] is A.
                                  // SR contains the flags.
      *dst, *op, opCode, tmp;
      // Load the next instruction as long as we haven't gone out of ram.
      op = PC < ramSize ? ram + PC++ : 0;)
  { // Check for HLT.
    if(opCode=*op)
    { // Take a pointer to the register selected by complement of bit 3.
      dst = reg+!(opCode&4);
    } else break;
    // Load operand as indicated by bits 0 and 1. Also check that we don't
    // go out of bounds and that the PC doesn't overflow.
    if(op = opCode&3 ? PC<ramSize && PC ? ram + PC++ : 0 : dst)
    {
      op = opCode&2 ? *op + opCode%2 * *reg + ram: op
    } else break;

    // Store the bits 3-5 in tmp.
    tmp = (opCode/=8) & 7;
    if(opCode<24 & opCode>4 && tmp)
    { // If not HLT, CLC, SEC or ST, enter this block.
      tmp &= 3; // We only care about bits 3&4 here.
      if(opCode&8) // Determine whether the operation is binary or unary.
      { // Unary
        if(opCode&4)
        { // Bitshift
          opCode &= SR&1; // Extract carry flag and AND it with bit 3 in opCode.
          SR=*op >> 7*!(tmp/=2);// Update carry flag.
          // Shift to left if bit 4 unset, to right if set. Inclusive-OR
          // the carry/bit 3 onto the correct end.
          *op = tmp = *op << !tmp >> tmp | opCode << 7*tmp;
        } else tmp=*o+=tmp%2*2-1;
      } else if(opCode&4) {
        // Bitwise operations and LD.
        // Ternary conditional to determine which operation.
        *dst = tmp = tmp? tmp&2? tmp&1? *op^*dst: *op|*dst: *op&*dst: *op
      } else if(opCode&1) {
        // ADC. Abuse precedence to do this in fewer bytes.
        // Updates carry flag.
        SR = *dst > (tmp = *dst += *op + SR%2);
      } else tmp=*dst-*op; SR = tmp > *dst; // Comparison.
      SR = SR&1 | tmp >> 6&2 | 4*!tmp; // Update Z and N flags, leaving C as it is.
    } else if(opCode&8) {
      // Branch.
      // tmp&~-tmp returns a truthy value when tmp has more than one bit set
      // We use this to detect the "unset" and "always" conditions.
      // Then, we bitwise-AND either ~tmp&SR or tmp&~SR to get a falsy value
      // when the condition is fulfilled. Finally, we take logical complement,
      // and multiply the resulting value (`1` or `0`) with the operand,
      // and add the result to program counter to perform the jump.
      PC += !(tmp & ~-tmp? ~tmp&SR : tmp&~SR) * *op;
    } else if (tmp) { // SEC, CLC
      SR = SR&6 | opCode % 2;
    } else {
      *op = *dst; // ST
    }
    if(!PC){ // If program counter looped around, null out ramSize to stop.
           // There's likely a bug here that will kill the program when it
           // branches back to address 0x00
      ramSize=0;
    }
  }
}

```

### Instructions

The instructions are structured as follows:

* Bits 6-7 indicate the arity of the instruction (`00` Nullary, `01` Unary, `10` Binary, `11` Binary)
* Bits 0-2 determine the operand(s): `R=0` selects `A` and `R=1` selects `X`. `OP=00` uses the register as an operand, `OP=01` selects immediate operand, `OP=10` selects absolute operand and `OP=11` selects indexed operand.

+ As you may have noticed, this allows for any operations to be performed on either register (although you can still only index from `X`) even when they normally couldn't be used per specification. E.g. `INC A`, `ADC X, 10` and `ASL X` all work.
* Bits 3-5 determine the condition for branching: having one of the bits indicates which flag to test (bit 3-\>C, bit 4-\>N, bit 5-\>Z). If only one bit is set, the instruction tests for a set flag. To test for an unset flag, take the complement of the bits. For example `110` tests for unset carry and `001` for set carry. `111` and `000` branch always.
* You can also branch to an address offset stored in a register, allowing you to write functions, or you can use the standard indexing modes. `OP=01` behaves like specification branch.

```
+-----+----------+-------+-----------------------------------------------+
| OP  | BINARY   | FLAGS | INFO                                          |
+-----+----------+-------+-----------------------------------------------+
| ST  | 10000ROP |       | Register -> Operand                           |
| LD  | 10100ROP | Z N   | Operand -> Register                           |
| AND | 10101ROP | Z N   | Register &= Operand                           |
| XOR | 10111ROP | Z N   | Register ^= Operand                           |
| IOR | 10110ROP | Z N   | Register |= Operand                           |
| ADC | 10011ROP | Z N C | Register += Operand + Carry                   |
| INC | 01011ROP | Z N   | Operand += 1                                  |
| DEC | 01010ROP | Z N   | Operand -= 1                                  |
| ASL | 01100ROP | Z N C | Operand <<= 1                                 |
| LSR | 01110ROP | Z N C | Operand >>= 1                                 |
| ROL | 01101ROP | Z N C | Operand = Operand << 1 | Carry                |
| ROR | 01111ROP | Z N C | Operand = Operand >> 1 | Carry << 7           |
| CMP | 10010ROP | Z N C | Update ZNC based on Register - Operand        |
| BR  | 11CNDROP |       | PC += Condition ? Operand : 0      |
| SEC | 00011000 |     C | Set carry                                     |
| CLC | 00010000 |     C | Clear carry                                   |
| HLT | 00000000 |       | Halt execution.                               |
+-----+----------+-------+-----------------------------------------------+

```
> 10 votes

# Answer
# APL (Dyalog Classic), ~~397~~ ~~332~~ 330 bytes

thanks @Adám for -8 bytes

```
f←{q←2⍴a x c←≡B←256⋄{0::m
⍺←(∇q∘←)0∘=,B≤+⍨
30≤u←⌊8÷⍨b←p⊃m:∇p+←129-B|127-1⊃p↓m×⊃b⌽2/(,~,⍪)1,q,c
p+←1
u=25:⍺x⊢←B|x+¯1*b
u=26:∇c⊢←~2|b
p+←≢o←m⊃⍨i←⍎'p⊃m+x'↑⍨1+8|b
⍎u⊃(,⍉'⍺ax⊢←o' '∇m[i]←ax'∘.~'xa'),5 4 2 3 2/'⍺⌽⊃'∘,¨'a⊢←2⊥(⍕⊃u⌽''∧∨≠'')/o a⊤⍨8⍴2' 'c(i⊃m)←u⌽d⊤(⌽d←u⌽2B)⊥u⌽o,c×u>10' 'c a⊢←2B⊤a+o+c' 'm[i]←B|o-¯1*u' 'c⊢←⊃2B⊤o-⍨⊃u⌽x a'}p m←⍵}

```

Try it online!

```
p  program counter
m  memory
a  accumulator register
x  index register
q  flags z (zero) and n (negative) as a length-2 vector
c  flag for carry
⍺  function to update z and n
b  current instruction
u  highest 5 bits of b
o  operand
i  target address in memory

```
> 9 votes

# Answer
# JavaScript (ES6), 361 bytes

Takes input as `(memory)(program_counter)`, where `memory` is an `Uint8Array`. Outputs by modifying this array.

```
M=>p=>{for(_='M[\u0011\u0011A]\u0010\u0010=\u000fc=\u000e,\u0011p]\f(n=\u000b128)\t=\u0010\b&=255\u0007,z=!(n\u0007),n&=\t;\u0006\u0006\u000b\u0005-\u0010,\u000en>=0\u0005\u0004\u0011c\b>>7,A]*2\u0005\u0003\u0011c\b&1,A]/2\u0005\u000f\u0002&&(p+=(\u0010^\t-\t;\u0001for(a=n=z=\u000ex=0;a\u0007,x\u0007,A=[i=\u0011p++],p\f\f+x][i&3],i&3&&p++,i&&A<256;)eval(`\u000ba\b\u0006\u000fa;\u000bx\b\u0006\u000fx;\u000ba&\b\u0005a|\b\u0005a^\b\u0005\u000f\u0002\u0003\u000fc*128|\u0002c|\u0003a+\b+c,\u000ea>>8\u0005++\u0010\u0005--\u0010\u0005a\u0004x\u0004++x\u0005--x\u0006\u000e1;\u000e0;1\u0001!z\u0001z\u0001!n\u0001n\u0001!c\u0001c\u0001`.split`;`[i>>2])';G=/[\u0001-\u0011]/.exec(_);)with(_.split(G))_=join(shift());eval(_)}

```

*NB: The code is compressed with RegPack and contains a lot of unprintable characters, which are all escaped in the above representation of the source.*

Try it online!

## Opcode mapping and test cases

The virtual machine uses this opcode mapping.

Below are the translated test cases, along with the expected outputs.

### Test case #1

```
00 - LDX #$10  09 10
02 - INC $01   32 01
04 - DEX       44
05 - BNE $fb   55 fb

```

Expected output:

$$\text{09 }\color{red}{\text{20}}\text{ 32 01 44 55 fb}$$

### Test case #2

```
00 - (DATA)    e0 08 2a 02
04 - LDA $00   02 00
06 - ADC $02   2e 02
08 - STA $00   06 00
0a - LDA $01   02 01
0c - ADC $03   2e 03
0e - STA $01   06 01

```

Expected output:

$$\color{red}{\text{0a 0b}}\text{ 2a 02 02 00 2e 02 06 00 02 01 2e 03 06 01}$$

### Test case #3

```
00 - (DATA)    5e 01 28 00
04 - LDX #$10  09 10
06 - LSR $01   1e 01
08 - ROR $00   26 00
0a - BCC $0d   65 0d
0c - LDA $02   02 02
0e - CLC       4c
0f - ADC $21   2e 21
11 - STA $21   06 21
13 - LDA $03   02 03
15 - ADC $22   2e 22
17 - STA $22   06 22
19 - ASL $02   22 02
1b - ROL $03   2a 03
1d - DEX       44
1e - BPL $e6   5d e6
20 - HLT       00
21 - (DATA)    00 00

```

Expected output:

$$\color{red}{\text{00 00 00 00}}\text{ 09 10 1e 01 }\dots\text{ 44 5d e6 00 }\color{red}{\text{b0 36}}$$

## Unpacked and formatted

Because the code is compressed with an algorithm that replaces frequently repeated strings with a single character, it is more efficient to use the same code blocks over and over than defining and invoking helper functions, or storing intermediate results (such as `M[A]`) in additional variables.

```
M => p => {
  for(
    a = n = z = c = x = 0;
    a &= 255, x &= 255,
    A = [i = M[p++], p, M[p], M[p] + x][i & 3],
    i & 3 && p++,
    i && A < 256;
  ) eval((
    '(n = a = M[A], z = !(n &= 255), n &= 128);'                                + // LDA
    'M[A] = a;'                                                                 + // STA
    '(n = x = M[A], z = !(n &= 255), n &= 128);'                                + // LDX
    'M[A] = x;'                                                                 + // STX
    '(n = a &= M[A], z = !(n &= 255), n &= 128);'                               + // AND
    '(n = a |= M[A], z = !(n &= 255), n &= 128);'                               + // ORA
    '(n = a ^= M[A], z = !(n &= 255), n &= 128);'                               + // EOR
    '(n = M[A] = M[c = M[A] & 1, A] / 2, z = !(n &= 255), n &= 128);'           + // LSR
    '(n = M[A] = M[c = M[A] >> 7, A] * 2, z = !(n &= 255), n &= 128);'          + // ASL
    '(n = M[A] = c * 128 | M[c = M[A] & 1, A] / 2, z = !(n &= 255), n &= 128);' + // ROR
    '(n = M[A] = c | M[c = M[A] >> 7, A] * 2, z = !(n &= 255), n &= 128);'      + // ROL
    '(n = a += M[A] + c, c = a >> 8, z = !(n &= 255), n &= 128);'               + // ADC
    '(n = ++M[A], z = !(n &= 255), n &= 128);'                                  + // INC
    '(n = --M[A], z = !(n &= 255), n &= 128);'                                  + // DEC
    '(n = a - M[A], c = n >= 0, z = !(n &= 255), n &= 128);'                    + // CMP
    '(n = x - M[A], c = n >= 0, z = !(n &= 255), n &= 128);'                    + // CPX
    '(n = ++x, z = !(n &= 255), n &= 128);'                                     + // INX
    '(n = --x, z = !(n &= 255), n &= 128);'                                     + // DEX
    'c = 1;'                                                                    + // SEC
    'c = 0;'                                                                    + // CLC
    ' 1 && (p += (M[A] ^ 128) - 128);'                                          + // BRA
    '!z && (p += (M[A] ^ 128) - 128);'                                          + // BNE
    ' z && (p += (M[A] ^ 128) - 128);'                                          + // BEQ
    '!n && (p += (M[A] ^ 128) - 128);'                                          + // BPL
    ' n && (p += (M[A] ^ 128) - 128);'                                          + // BMI
    '!c && (p += (M[A] ^ 128) - 128);'                                          + // BCC
    ' c && (p += (M[A] ^ 128) - 128);')                                           // BCS
    .split`;`[i >> 2]
  )
}

```
> 7 votes

# Answer
# PHP, ~~581 585 555~~ 532 bytes (not -yet- competing)

```
function t($v){global$f,$c;$f=8*$c|4&$v>>5|2*!$v;}$m=array_slice($argv,2);for($f=0;$p>-1&&$p<$argc-1&&$i=$m[$p=&$argv[1]];$p++)$i&3?eval(explode(_,'$a=$y_$a&=$y_$a|=$y_$a^=$y_$a+=$y+$c;$c=$a>>8_$x=$y_$c=$y&1;$y>>=1_$c=($y*=2)>>8_$y+=$y+$c;$c=$y>>8_$y+=$c<<8;$c=$y&1;$y>>=1_$y--_$y++_$z=$a-$y,$c=$a<$y_$z=$x-$y,$c=$x<$y_$y=$a_$y=$x_'.$y=&$m[[0,++$p,$g=$m[$p],$g+$x][$i&3]])[$i>>=2].'$i<14&&t(${[aaaaaxyyyyyyzz][$i]}&=255);'):($i&32?$p+=($f>>$i/8-4^$i)&1?($y=$m[++$p])-($y>>7<<8):1:($i&8?$f=$f&7|8*$c=$i/4:t($x+=$i/2-9)));print_r($m);

```

takes PC and and OP codes as base 10 integers from command line arguments,
prints memory as a list of `[base 10 address] => base 10 value`.

This is **not tested thoroughly yet**; but there is a breakdown.

There´s the code map and here´s an overview for my mapping:

```
3-mode instructions:
00: LDA     04: AND     08: ORA     0C: EOR
10: ADC     14: LDX     18: LSR     1C: ASL
20: ROL     24: ROR     28: DEC     2C: INC
30: CMP     34: CPX     38: STA     3C: STX

+1: immediate
+2: absolute
+3: relative

implicit:
00: HLT
10: DEX 14: INX
18: CLC 1C: SEC

relative:
20: BRA         (0)
28: BNE 2C: BEQ (Z)
30: BPL 34: BMI (N)
38: BCC 3C: BCS (C)

```

side note:
code `24` results in a `BNV` (branch never = 2 byte `NOP`);
`04`, `08`, `0C` are aliases for `INX`, `CLC` and `SEC`
and anything above `3F` is either a two byte `NOP` or an alias for the single mode instructions.
> 2 votes

---
Tags: code-golf, interpreter, assembly
---


title: Self Scoring Program

text:
# Question
Title: Self Scoring Program
We have a challenge to output your own score, but it seems like all the answers there just hardcode the output and that's *boring*1. So lets have a new challenge. Your program must output its own length in bytes followed by the string `" bytes"`, but in order to prevent hardcoded solutions if we reduce its size by removing *any* one byte, the new program must also output it's new byte count, still followed by `" bytes"`. Output does not need to be case sensitive. You may also choose to output a trailing newline.

Your answers will be scored in bytes with fewer bytes being better.

---

1: I actually like some of the answers there.

# Answer
> 16 votes
# Backhand, ~~40 36~~ 29 bytes

```
vv""sseettyybb  ""jjHHOO]

```

Try it online! Verification!

When in doubt, double up on everything. This uses Backhand's ability to move more than one step at a time to implement the redundancy. The unprintables all have the byte value 28.

## Explanation:

### Non-irradiated program:

```
v       Reduce step count to 2
  "    Start string literal
    s e t y b        Push the " bytes" part of the output
                  " Push 28 twice and end the string literal
                       j    Jump to the 28th position (0 indexed)
                             ]   Increment the 28 to 29
                           O     Print the 29
                         H       Halt and output the entire stack

```

### Irradiated program:

If any character is deleted, every character after that is shifted down.

```
vv"sseettyybb
v " s e t y b     The same instructions are still executed

```

However, instead of jumping to the `]`, it instead reflects off the end of the program and lands on the `O` instead.

```
                             v  28th character (0 indexed)
vv""sseettyybb       ""jjHHOO]
v""sseettyybb       ""jjHHOO]OOHHjj"".....
                             ^ 28th character, reflecting off the end of the code

```

# Answer
> 3 votes
# Runic Enchantments, 47 bytes

```
>>yyLL     @"setyb 64"/
"47 bytes"@"setyb 64"L\

```

Try it online!

Which is more or less a port of my Geiger Counter answer, but with different output (which is, itself, a port of a Klein answer).

`>>yyLL` is required for Runic to generate (at least) one IP, merge two IPS, and reflect back to the left, so that all variations result in a single left-moving IP. Could be replaced by `yy<<` but it doesn't save any bytes.

The reflectors on the right force the IP to the lower left string, so the removal of top right one of them allows the IP into the top right string. Removing a byte anywhere else along the top line adjusts the top reflector to sit above the L (allowing the program into the lower right). The removal of a byte along the bottom adjusts that reflector (or removes it) so that the last character gets implicitly filled with a space, which allows the IP to bounce off both sides of the top right reflector and into the top right string.

The excess spaces are disappointing, though. But all attempts to reduce them have resulted in either larger programs, same size programs, or programs that are not 100% radiation proof. Both the Klein and \>\<\> answers here use features not available in Runic.

# Answer
> 2 votes
# \>\<\>, ~~43~~ 39 bytes

```
||vn-{"' bytes"-10/
 o>o<"38 bytes"[0/0

```

Try it online! Verification!

In the un-irradiated program, we add `0` to the `'` (39), and in the irradiated program we skip the 0 and add `-1` to it instead. If something is removed from the top row, we shift to the bottom row instead and just output `38 bytes`.

# Answer
> 2 votes
# Klein 000, 41 bytes

```
<<@"setyb "$"4"+"0"/
..@"setyb 04"(....<1

```

Try it online! JoKing's Verifier

I think this answer is similar to JoKing's \>\<\> answer, but I don't read \>\<\> so I can't be sure.

There are 4 different types of byte removals here

1. **A byte is removed from the first line before `/`.** In this case the slash is effectively moved left one space, deflecting it onto the bottom line and preventing the modified part of the code from being executed. This causes us to run the code `("40 bytes"@`, which outputs `40 bytes`.
2. **The first `/` is removed from the first line.** In this case we run the code `"0"+"4"$" bytes"@`, which is a convoluted way or printing `40 bytes`.
3. **The newline is removed.** This makes us start from the end of the second line and the resulting code (with noops removed) is `1("40 bytes"@`, which just prints `40 bytes`.
4. **A byte from the last line is removed.** This causes the `1` at the end of the first line to be moved left and prevents it from being added to the stack when the pointed is deflected by `/`. The code `"0"+` for that reason pushes `0` instead of `1`, the rest of the code turns the `0` into `40 bytes`.

# Klein 001, 41 bytes

```
\("40 bytes"@......1
..@"setyb "$"4"+"0"/

```

Try it online! JoKing's Verifier

Here's an answer using a different topology. It's the same size but I think there is room for improvement.

# Answer
> 2 votes
# Hexagony, 71 bytes

```
//.........||.>e;s;@..\;t;y;b<>}F"+!P0;/|/F!P0$@;<...t;ye;bs/.........)

```

Try it online! Verification!

I spent way too long trying to get this into a size 5 hexagon, but I had to settle for a subpar size 6 instead `:(`.

### Expanded:

```
      / / . . . .
     . . . . . | |
    . > e ; s ; @ .
   . \ ; t ; y ; b <
  > } F " + ! P 0 ; /
 | / F ! P 0 $ @ ; < .
  . . t ; y e ; b s /
   . . . . . . . . .
    ) . . . . . . .
     . . . . . . .
      . . . . . .

```

I initially made this with the `)` one row lower, *but* it turns out that's exactly where the divide between size 5 and size 6 hexagons are. This means when a byte is removed, the size all shifts down and ruins the pathways. I'm definitely sure that a size 5 is possible.

---
Tags: code-golf, radiation-hardening, self-referential
---


title: Different combinations possible

text:
# Question
Title: Different combinations possible
**Problem**

Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0). There musn't be white spaces between slopes and also the mountain musn't descend below the x axis. The problem to be solved is: given n (which defines the size of the landscape) and the number k of peaks (k always less than or equal to n), how many combinations of mountains are possible with k peaks?

**Input**

n who represents the width of the landscape and k which is the number of peaks.

**Output**

Just the number of combinations possible.

**Example**

Given n=3 and k=2 the answer is 3 combinations.

**Just to give a visual example, they are the following:**

```
   /\     /\      /\/\
/\/  \   /  \/\  /    \

```

are the 3 combinations possible using 6 (3\*2) positions and 2 peaks.

Edit: \- more examples -

```
n  k  result
2  1  1
4  1  1
4  3  6
5  2  10

```

**Winning condition**

Standard rules apply. The shortest submission in bytes wins.

# Answer
# Python, 40 bytes

```
f=lambda n,k:k<2or~-n*n*f(n-1,k-1)/~-k/k

```

Try it online!

Uses the recurrence \\$a\_{n,1} = 1\\$, \\$a\_{n,k} = \frac{n(n-1)}{k(k-1)}a\_{n-1,k-1}\\$.
> 7 votes

# Answer
# Jelly, 7 bytes

```
cⱮṫ-P÷⁸

```

Try it online!

Takes input as `n` then `k`. Uses the formula

\\$N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}\\$

which I found on Wikipedia.

```
cⱮṫ-P÷⁸
c        Binomial coefficient of n and...
 Ɱ       each of 1..k
  ṫ-     Keep the last two. ṫ is tail, - is -1.
    P    Product of the two numbers.
     ÷   Divide by
      ⁸  n.

```

**7 bytes**

Each line works on it's own.

```
,’$c@P÷
c@€ṫ-P÷

```

Takes input as `k` then `n`.

**7 bytes**

```
cⱮ×ƝṪ÷⁸

```
* Thanks to Jonathan Allan for this one.
> 6 votes

# Answer
# JavaScript (ES6), ~~33~~ 30 bytes

*Saved 3 bytes thanks to @Shaggy*

Takes input as `(n)(k)`.

```
n=>g=k=>--k?n*--n/-~k/k*g(k):1

```

Try it online!

Implements the recursive definition used by Anders Kaseorg.

---

# JavaScript (ES7), ~~59~~ ~~58~~ ~~49~~ 45 bytes

Takes input as `(n)(k)`.

```
n=>k=>k/n/(n-k+1)*(g=_=>k?n--/k--*g():1)()**2

```

Try it online!

Computes:

$$a\_{n,k}=\frac{1}{k}\binom{n-1}{k-1}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+1}$$

Derived from A001263 (first formula).
> 4 votes

# Answer
# Wolfram Language (Mathematica), 27 bytes

Three versions, all the same length:

```
(b=Binomial)@##b[#,#2-1]/#&

Binomial@##^2#2/(#-#2+1)/#&

1/(Beta[#2,d=#-#2+1]^2d##)&

```

Try it online! (Just the first version, but you can copy and paste to try the others.)

All of these are some sort of variant on $$\frac{n!(n-1)!}{k!(k-1)!(n-k)!(n-k-1)!}$$ which is the formula that's been going around. I was hoping to get somewhere with the Beta function, which is a sort of binomial reciprocal, but then there was too much division happening.
> 3 votes

# Answer
# APL(Dyalog), ~~19~~ ~~18~~ ~~16~~ 12 bytes

```
⊢÷⍨!×⊢!⍨¯1+⊣

```

*Thanks to @Galen Ivanov for -4 bytes*

Uses the identity in the OEIS sequence. Takes k on the left and n on the right.

TIO
> 2 votes

# Answer
# , 17 11 bytes

```
]%~!*<:@[!]

```

Try it online!

Takes `n` as the right argument, `k` as the left one. Uses the same formula as dylnan's Jelly answer and Quintec's APL solution.

## Explanation:

```
            ] - n
           !  - choose
       <:@[   - k-1
      *       - multiplied by
     !        - n choose k
   %~         - divided by
  ]           - n

```
> 2 votes

# Answer
# Ruby, 50 bytes

```
->l,n{eval [[*n..l]*2*?*,l,n,[*1..l-=n]*2,l+1]*?/}

```

Try it online!
> 1 votes

# Answer
# Perl 6, 33 bytes

```
{[*] ($^n-$^k X/(2..$k X-^2))X+1}

```

Try it online!

Uses the formula

$$a\_{n,k}=\binom{n-1}{k-1}\times\frac{1}{k}\binom{n}{k-1}=\prod\_{i=1}^{k-1}(\frac{n-k}{i}+1)\times\prod\_{i=2}^{k}(\frac{n-k}{i}+1)$$

### Explanation

```
{[*]                            }  # Product of
     ($^n-$^k X/                   # n-k divided by
                (2..$k X-^2))      # numbers in ranges [1,k-1], [2,k]
                             X+1   # plus one.

```

### Alternative version, 39 bytes

```
{combinations(|@_)²/(1+[-] @_)/[/] @_}

```

Try it online!

Uses the formula from Arnauld's answer:

$$a\_{n,k}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+1}$$
> 1 votes

# Answer
# Common Lisp, 76 bytes

```
(defun x(n k)(cond((= k 1)1)(t(*(/(* n(1- n))(* k(1- k)))(x(1- n)(1- k))))))

```

Try it online!
> 1 votes

# Answer
# Jelly, 8 bytes

```
,’$c’}P:

```

A dyadic Link accepting `n` on the left and `k` on the right which yields the count.

**Try it online!**
> 0 votes

# Answer
# Stax, 9 bytes

```
ÇäO╪∙╜5‼O

```

Run and debug it

I'm using dylnan's formula in stax.

Unpacked, ungolfed, and commented the program looks like this.

```
        program begins with `n` and `k` on input stack
{       begin block for mapping
  [     duplicate 2nd element from top of stack (duplicates n)
  |C    combinatorial choose operation
m       map block over array, input k is implicitly converted to [1..k]
O       push integer one *underneath* mapped array
E       explode array onto stack
*       multiply top two elements - if array had only element, then the pushed one is used
,/      pop `n` from input stack and divide

```

Run this one
> 0 votes

# Answer
# APL(NARS), 17 chars, 34 bytes

```
{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}

```

test:

```
  f←{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}
  (2 f 1)(4 f 1)(4 f 3)(5 f 2)
1 1 6 10

```
> 0 votes

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


# Question
Title: Concatenate 2 numeric type values to a fixed size number
You have 2 numbers, both stored separate as **numeric data type**.

First number is always 6 digits long.

Second number can vary between 1 and 4 digits. If it's less than 4 digits, it needs to be padded with numeric value 0.

End result always needs to be 10 digits number.

Order has to be respected. n1|n2

**Example #1:**

```
n1 = 111111
n2 = 2222
result = 1111112222

```

**Example #2:**

```
n1 = 333333
n2 = 44
result = 3333330044

```

The **rule** is that you can only use **numeric data types** (number, int, float, decimal) to get the desired result.

# Answer
> 3 votes
# MathGolf, 3 bytes

```
♫*+

```

Try it online!

### Explanation:

```
      Implicit input
 ♫*   Multiply first argument by 10000
   +  Add the two arguments
      Implicit output

```

# Answer
> 2 votes
# MATL, 5 bytes

```
1e4*+

```

Uses only addition and multiplication.

Try it online!

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
4°*+

```

Try it online!

# Answer
> 1 votes
# Ruby, 14 bytes

```
->a,b{a*1e4+b}

```

# Answer
> 1 votes
# brainfuck, 45 bytes

```
,.,.,.,.,.,.,[-->+++>+++>+++<<<],[<,]>>>>[.<]

```

Try it online!

Assumes the inputted numbers are separated by a single space

---
Tags: math, number
---


title: Compute the superset

text:
# Question
Title: Compute the superset
Your task here is simple:

Given a list of integer sets, find the set union. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:

```
[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4

```

Sets are notated using range notation: `[1,4]` means the integers `1,2,3,4`. Sets can also be unbounded: `[3,]` means all of the integers `>= 3`, and `[,-1]` means all of the integers `<= -1`. It is guaranteed that the first element of the range will not be greater than the second.

You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. You can use two distinct constants to represent the infinite upper bound and the infinite lower bound. For example, in Javascript, you could use `[3,{}]` to notate all integers `>= 3`, as long as you consistently used `{}` across all test cases.

Test cases:

```
[1,3]                     => [1,3]
[1,]                      => [1,]
[,9]                      => [,9]
[,]                       => [,]
[1,3],[4,9]               => [1,9]
[1,5],[8,9]               => [1,5],[8,9]
[1,5],[1,5]               => [1,5]
[1,5],[3,7]               => [1,7]
[-10,7],[1,5]             => [-10,7]
[1,1],[2,2],[3,3]         => [1,3]
[3,7],[1,5]               => [1,7]
[1,4],[8,]                => [1,4],[8,]
[1,4],[-1,]               => [-1,]
[1,4],[,5]                => [,5]
[1,4],[,-10]              => [1,4],[,-10]
[1,4],[,]                 => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]

```

This is , so make your answer as short as possible!

# Answer
# \+ `intervals`, ~~90 87~~ 81 bytes

```
function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)
library(intervals)

```

Try it online!

Input is a list of intervals. `-Inf` and `Inf` are R built-ins for minus/plus infinity. Output is a matrix of columns of intervals.

Not usually a fan of using non-standard libraries but this one was fun. TIO doesn't have `intervals` installed. You can try it on your own installation or at https://rdrr.io/snippets/

The `intervals` package supports real and integer (`type = "Z"`) intervals and the `reduce` function is a built-in for what the challenge wants, but the output seems to default to open intervals, so ~~`close_intervals`~~ `+c(1,-1)` is needed to get the desired result.

Old version had examples in list of lists which might be convenient so I've left the link here.
> 7 votes

# Answer
# JavaScript (ES6), 103 bytes

*Saved 1 byte thanks to @Shaggy*
*Saved 1 byte thanks to @KevinCruijssen*

Expects `+/-Infinity` for infinite values.

```
a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<M+2?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=[]),b[0]=[m,M],b)

```

Try it online!

### How?

We first sort the intervals by their lower bound, from lowest to highest. Upper bounds are ignored.

We then iterate over the sorted intervals \\$\[p\_n,q\_n\]\\$, while keeping track of the current lower and upper bounds \\$m\\$ and \\$M\\$, initialized to \\$p\_1\\$ and \\$q\_1\\$ respectively.

For each interval \\$\[p\_n,q\_n\]\\$:

* If \\$p\_n\le M+1\\$: this interval can be merged with the previous ones. But we may have a new upper bound, so we update \\$M\\$ to \\$\max(M,q\_n)\\$.
* Otherwise: there is a gap between the previous intervals and this one. We create a new interval \\$\[m,M\]\\$ and update \\$m\\$ and \\$M\\$ to \\$p\_n\\$ and \\$q\_n\\$ respectively.

At the end of the process, we create a last interval with the current bounds \\$\[m,M\]\\$.

### Commented

```
a => (                  // a[] = input array
  a.sort(([p], [P]) =>  // sort the intervals by their lower bound; we do not care about
    p - P)              // the upper bounds for now
  .map(m = M =          // initialize m and M to non-numeric values
    ([p, q]) =>         // for each interval [p, q] in a[]:
    p < M + 2 ?         //   if M is a number and p is less than or equal to M + 1:
      M = q > M ? q : M //     update the maximum M to max(M, q)
    : (                 //   else (we've found a gap, or this is the 1st iteration):
      b.push([m, M]),   //     push the interval [m, M] in b[]
      m = p,            //     update the minimum m to p
      M = q             //     update the maximum M to q
    ),                  //
    b = []              //   start with b[] = empty array
  ),                    // end of map()
  b[0] = [m, M], b      // overwrite the 1st entry of b[] with the last interval [m, M]
)                       // and return the final result

```
> 6 votes

# Answer
# Python 2, ~~118~~ ~~113~~ ~~112~~ ~~111~~ ~~106~~ ~~105~~ ~~104~~ 101 bytes

```
x=input()
x.sort();a=[];b,c=x[0]
for l,r in x:
 if l>c+1:a+=(b,c),;b,c=l,r
 c=max(c,r)
print[(b,c)]+a

```

Saved one byte thanks to Mr.Xcoder, one thanks to Jonathan Frech, and three thanks to Dead Possum.
Try it online!
> 4 votes

# Answer
# Ruby, ~~89~~ 76 bytes

```
->a{[*a.sort.reduce{|s,y|s+=y;y[0]-s[-3]<2&&s[-3,3]=s.max;s}.each_slice(2)]}

```

Try it online!

Sort the array, then flatten by appending all the ranges to the first: if a range overlaps the previous one, discard 2 elements from the last 3 (keeping only the max).

Unflatten everything at the end.
> 2 votes

# Answer
# Stax, ~~46~~ ~~39~~ 38 bytes

```
├&P◙╛╛ΘΩ¿σa○♦◘♣┐¬≥∩ó¬îî◙k]∙♣•╘○π≡¡jN<♀

```

Run and debug it

This program takes input in the originally specified string notation.
> 2 votes

# Answer
# Pascal (FPC), ~~367~~ ~~362~~ 357 bytes

```
uses math;type r=record a,b:real end;procedure d(a:array of r);var i,j:word;t:r;begin for i:=0to length(a)-1do for j:=0to i do if a[i].a<a[j].a then begin t:=a[i];a[i]:=a[j];a[j]:=t;end;j:=0;for i:=1to length(a)-1do if a[j].b>=a[i].a-1then begin a[j].a:=min(a[i].a,a[j].a);a[j].b:=max(a[i].b,a[j].b)end else j:=j+1;for i:=0to j do writeln(a[i].a,a[i].b)end;

```

Try it online!

A procedure that takes a dynamic array of records consisting of 2 range bounds, modifies the array in place and then writes it on standard output, one range per line. (Sorry for that twisted sentence.) Uses `1/0` for ubounded up and `-1/0` for unbounded down.

Readable version

It would be nice to just return the array with corrected number of elements, but the dynamic array passed to function/procedure is not dynamic array anymore... First I found this, then there is this excellent, mind-boggling explanation.

This is the best data structure I could found for shortening the code. If you have better options, feel free to make a suggestion.
> 1 votes

# Answer
# C (clang), ~~346~~ 342 bytes

Compiler flags `-DP=printf("(%d,%d)\n"`,`-DB=a[i+1]`, and `-DA=a[i]`

```
typedef struct{int a,b;}t;s(t**x,t**y){if((*x)->a>(*y)->a)return 1;else if((*x)->a<(*y)->a)return -1;}i;f(t**a){for(i=0;A;)i++;qsort(a,i,sizeof(t*),s);for(i=0;B;i++){if(B->a<=A->b+1){A->b=B->b;if(B->a<A->a)A->a=B->a;else B->a=A->a;}}for(i=0;A;i++){if(!B)break;if(A->a!=B->a)P,A->a,A->b);}P,A->a,A->b);}

```

Try it online!
> 1 votes

# Answer
# 05AB1E (legacy), ~~88~~ ~~79~~ 78 bytes

```
g≠i˜AKïDW<UZ>VIøεAXY‚Nè:}ïø{©˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàDYQiA}V®нßDXQiA}Y‚

```

Infinity is input as the lowercase alphabet (`'abcdefghijklmnopqrstuvwxyz'`).

Try it online or verify all test cases.

**Important note:** If there was an actual `Infinity` and `-Infinity`, it would have been **~~43~~ 42 bytes** instead. So ~~little over 50%~~ around 30% is as work-around for the lack of `Infinity`..

```
{©Dg≠i˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàV®нßY‚

```

Try it online (with `Infinity` replaced with `9999999999` and `-Infinity` replaced with `-9999999999`).

Can definitely be golfed substantially. In the end it turned out very, very ugly full of workarounds. But for now I'm just glad it's working.

**Explanation:**

```
Dg≠i          # If the length of the implicit input is NOT 1:
              #   i.e. [[1,3]] → length 1 → 0 (falsey)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → length 8 → 1 (truthy)
    ˜         #  Take the input implicit again, and flatten it
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
     AK       #  Remove the alphabet
              #   i.e. [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
              #    → ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
       ï      #  Cast everything to an integer, because `K` turns them into strings..
              #   i.e. ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
              #    → [1,4,-5,3,7,38,40,8,9,11,20,25,15,23]
        D     #  Duplicate it
         W<   #  Determine the min - 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → -5
           U  #  Pop and store it in variable `X`
         Z>   #  Determine the max + 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → 40
           V  #  Pop and store it in variable `Y`
Iø            #  Take the input again, and transpose/zip it (swapping rows and columns)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
  ε       }   #  Map both to:
   A          #   Push the lowercase alphabet
    XY‚       #   Push variables `X` and `Y`, and pair them into a list
       Nè     #   Index into this list, based on the index of the mapping
         :    #   Replace every alphabet with this min-1 or max+1
              #   i.e. [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
              #    → [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
ï             #  Cast everything to integers again, because `:` turns them into strings..
              #   i.e. [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
              #    → [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
 ø            #  Now zip/transpose back again
              #   i.e. [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
              #    → [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
  {           #  Sort the pairs based on their lower range (the first number)
              #   i.e. [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
              #    → [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
   ©          #  Store it in the register (without popping)
˜             #  Flatten the list
              #   i.e. [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
 ¦            #  And remove the first item
              #   i.e. [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
  2ô          #  Then pair every two elements together
              #   i.e. [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
    í         #  Reverse each pair
              #   i.e. [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
              #    → [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
     Æ        #  Take the difference of each pair (by subtracting)
              #   i.e. [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
              #    → [6,-1,1,2,-5,2,-3,40]
      1›      #  Determine for each if they're larger than 1
              #   i.e. [6,-1,1,2,-5,2,-3,40] → [1,0,0,1,0,1,0,1]
.œ            #  Create every possible partition of these values
              #   i.e. [1,0,0,1,0,1,0,1] → [[[1],[0],[0],[1],[0],[1],[0],[1]],
              #                             [[1],[0],[0],[1],[0],[1],[0,1]],
              #                             ...,
              #                             [[1,0,0,1,0,1,0],[1]],
              #                             [[1,0,0,1,0,1,0,1]]]
  ʒ         } #  Filter the partitions by:
   í          #   Reverse each inner partition
              #    i.e. [[1],[0,0,1],[0,1],[0,1]] → [[1],[1,0,0],[1,0],[1,0]]
    ε     }   #   Map each partition to:
     ć        #    Head extracted
              #     i.e. [1,0,0] → [0,0] and 1
              #     i.e. [1] → [] and 1
              #     i.e. [1,0,1] → [1,0] and 1
      s       #    Swap so the rest of the list is at the top of the stack again
       O      #    Take its sum
              #     i.e. [0,0] → 0
              #     i.e. [] → 0
              #     i.e. [1,0] → 1
        _     #    And check if it's exactly 0
              #     i.e. 0 → 1 (truthy)
              #     i.e. 1 → 0 (falsey)
         *    #    And multiply it with the extracted head
              #    (is only 1 when the partition has a single trailing 1 and everything else a 0)
              #     i.e. 1 and 1 → 1 (truthy)
              #     i.e. 1 and 0 → 0 (falsey)
           P  #   And check if all mapped partitions are 1
н             #  Take the head (there should only be one valid partition left)
              #   i.e. [[[1],[0,0,1],[0,1],[0,1]]] → [[1],[0,0,1],[0,1],[0,1]]
 €g           #  Take the length of each inner list
              #   i.e. [[1],[0,0,1],[0,1],[0,1]] → [1,3,2,2]
   ®          #  Push the sorted pairs we've saved in the register earlier
    £         #  Split the pairs into sizes equal to the partition-lengths
              #   i.e. [1,3,2,2] and [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
ε             #  Map each list of pairs to:
 ø            #   Zip/transpose (swapping rows and columns)
              #    i.e. [[1,4],[3,7],[8,9]] → [[1,3,8],[4,7,9]]
              #    i.e. [[25,41],[38,40]] → [[25,38],[41,40]]
  ©           #   Store it in the register
   θ          #   Take the last list (the ending ranges)
              #    i.e. [[25,38],[41,40]] → [41,40]
    à         #   And determine the max
              #    i.e. [41,40] → 41
     DYQi }   #   If this max is equal to variable `Y`
              #     i.e. 41 (`Y` = 41) → 1 (truthy)
         A    #    Replace it back to the lowercase alphabet
           V  #   Store this max in variable `Y`
  ®           #   Take the zipped list from the register again
   н          #   This time take the first list (the starting ranges)
              #    i.e. [[25,38],[41,40]] → [25,38]
    ß         #   And determine the min
              #    i.e. [25,38] → 25
     DXQi }   #   If this min is equal to variable `X`
              #     i.e. 25 (`X` = -6) → 0 (falsey)
         A    #    Replace it back to the lowercase alphabet
           Y‚ #   And pair it up with variable `Y` (the max) to complete the mapping
              #    i.e. 25 and 'a..z' → [25,'a..z']
              #  Implicitly close the mapping (and output the result)
              #   i.e. [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
              #    → [['a..z',-5],[1,9],[11,23],[25,'a..z']]
              # Implicit else (only one pair in the input):
              #  Output the (implicit) input as is
              #   i.e. [[1,3]]

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 57 bytes

```
List@@(#-{0,1}&/@IntervalUnion@@(Interval[#+{0,1}]&/@#))&

```

Try it online!

Takes input as a list of lists `{a,b}` representing the interval `[a,b]`, where `a` can be `-Infinity` and `b` can be `Infinity`.

Uses the built-in `IntervalUnion`, but of course we have to massage the intervals into shape first. To pretend that the intervals are integers, we add 1 to the upper bound (making sure that the union of `[1,3]` and `[4,9]` is `[1,9]`). At the end, we undo this operation, and turn the result back into a list of lists.

There's also a completely different approach, which clocks in at **73 bytes**:

```
NumericalSort@#//.{x___,{a_,b_},{c_,d_},y___}/;b+1>=c:>{x,{a,b~Max~d},y}&

```

Here, after sorting the intervals, we just replace two consecutive intervals by their union whenever that would be a single interval, and repeat until there is no such operation left to be done.
> 1 votes

---
Tags: code-golf, set-theory
---


title: String subtraction

text:
# Question
Title: String subtraction
## Objective

Create a function to reverse string concatenation

## Input

Two strings (alphanumeric + spaces), where one should be subtracted for the other.

* You can assume that the string to be subtracted will never be larger than the other one.

## Output

The result from the subtraction

## Subtraction

You should remove one string from the start or the end of another string. If the string is present in the start and in the end, you can only remove one, which one will be removed is up to you.
If the string isn't in the start or in the end, or isn't an exact match, it is an invalid subtraction and you should output the original string.

## Test Cases

### Valid Subtraction

```
'abcde','ab' -> 'cde'
'abcde','cde' -> 'ab'
'abab','ab' -> 'ab'
'abcab','ab' -> 'abc' or 'cab'
'ababcde','ab' -> 'abcde'
'acdbcd','cd' -> 'acdb'
'abcde','abcde' -> ''
'abcde','' -> 'abcde'
'','' -> ''

```

### Invalid Subtraction (returns original string)

```
'abcde','ae' -> 'abcde'
'abcde','aa' -> 'abcde'
'abcde','bcd' -> 'abcde'
'abcde','xab' -> 'abcde'
'abcde','yde' -> 'abcde'

```

### Invalid Input (don't need to be handled)

```
'','a' -> ''

```

This is , so the shortest code in bytes wins!

# Answer
> 18 votes
# Java 8, ~~46~~ ~~45~~ ~~44~~ 40 bytes

-1 byte thanks to TheLethalCoder

-1 byte because I'm dumb (thanks Rod!)

-4 bytes thanks to Kevin Cruijssen

```
a->b->a.replaceFirst("^"+b+"|"+b+"$","")

```

Try it online! (includes all test cases)

A Java answer actually beats a few other practical languages. *Smiles. (and now it beats JS!)*

# Answer
> 9 votes
# Brachylog (Try It Online!), 12 bytes

```
~cpĊh.∧Ċtw|w

```

Try it online!

Takes the string to subtract from from standard input, and the string to subtract as a command line argument.

## Explanation

```
~cpĊh.∧Ċtw|w
~c            Split {the input} into pieces
  p           and (possibly) rearrange those pieces
   Ċ          such that there are two pieces
    h         and the first
     .        matches the command line argument
      ∧       then
         w    print
        t     the last
       Ċ      piece.
          |   If all else fails,
           w  print {the input}.

```

# Answer
> 8 votes
# JavaScript (ES6), 41 bytes

```
s=>t=>s.replace(eval(`/^${t}|${t}$/`),'')

```

Takes input via currying syntax, i.e. `f("abab")("ab")`.

# Answer
> 6 votes
# Retina, 21 bytes

1 byte thanks to Martin Ender.

```
(.*);(\1|(.*)\1$|)
$3

```

Try it online!

# Answer
> 5 votes
# JavaScript (ES6), ~~76~~ ~~70~~ ~~45~~ 41 bytes

```
s=>t=>s.replace(RegExp(`^${t}|${t}$`),"")

```

---

## Try It

```
f=
s=>t=>s.replace(RegExp(`^${t}|${t}$`),"")
o.innerText=f(i.value="abcde")(j.value="ab")
i.oninput=j.oninput=_=>o.innerText=f(i.value)(j.value)
```

```
<input id=i><input id=j><pre id=o>
```

# Answer
> 4 votes
# Japt, ~~11~~ 9 bytes

```
k"^|$"¬qV

```

Try it online!

# Answer
> 4 votes
# Perl 6, 21 bytes

```
->$_,$b {S/^$b|$b$//}

```

Try it

## Expanded:

```
-> $_, $b {   # pointy block lambda

  S/          # Str replace and return (implicitly against ｢$_｣)

  |   ^ $b    # starting with the second argument
  |     $b $  # or ending with the second argument

  //          # replace with nothing.

}

```

# Answer
> 3 votes
# TI-Basic (TI-84 Plus CE), 63 bytes

```
Prompt Str0,Str2
inString(Str0,Str2
If Ans
sub(Str0,1,Ans-1)+sub(Str0,Ans+length(Str2),length(Str0)-Ans+1-length(Str2→Str0
Str0

```

# Answer
> 3 votes
# APL (Dyalog), ~~31~~ 30 bytes

-1 thanks to Zacharý.

This actually uses reverse (i.e. the inverse of) concatenation! Takes original string as left argument, and what to subtract as right argument.

```
{0::⍺{0::⍺⋄,∘⍵⍣¯1⊢⍺}⍵⋄⍵,⍣¯1⊢⍺}

```

Try it online!

Ungolfed:

```
{
    0::⍺{         ⍝ if an error happens, apply the following function on the arguments
        0::⍺          ⍝ if an error happens, return the left argument unmodified
        ,∘⍵⍣¯1⊢⍺      ⍝ inverse-append right argument on left argument
        }⍵
    ⍵,⍣¯1⊢⍺      ⍝ inverse-prepend the right argument on the left argument
}

```

Legend:

`{``}` anonymous function

left argument of the current function

right argument of the current function

`0::`… if any error happens, execute this, else…

`⍣¯1⊢` inverse

`,∘⍵` concatenate  on the right

`⍵,` concatenate  on the left

# Answer
> 3 votes
# Bash, ~~66~~ ~~61~~ 49 bytes

```
case $1 in *$2)echo ${1%$2};;*)echo ${1#$2};;esac

```

Try it online!

less golfed:

```
a=$1;
case $1 in
    *$2)  c=${a%$2};;
    $2*)  c=${a#$2};;
      *)  c=$1;;
esac;
echo $c

```

Uses case to test begining or end, and array prefix/suffix (% / #) substraction

# Answer
> 3 votes
# Python, ~~69~~ ~~68~~ ~~64~~ ~~57~~ ~~51~~ 45 bytes

This ended up being a completely different solution with Regex.

*Thanks to Value Ink for -2 bytes!*
*and Felipe Nardi Batista for the massive -6 bytes!*

```
import re
lambda s,c:re.sub(c+'$|^'+c,'',s,1)

```

Try it online!

# Answer
> 3 votes
## Mathematica, 162 bytes

```
(c=Characters;a=c@#;b=c@#2;l=Length;t={};If[l@Intersection[a,b]==l@b,If[MemberQ[Partition[a,l@b,1],b],t=a;Table[t=DeleteCases[t,b[[i]],1,1],{i,l@b}]],t=a];""<>t)&

```

test input style \["abcde","ab"\]

# Answer
> 2 votes
# PHP, 54 Bytes

```
[,$x,$y]=$argv;echo preg_replace("#^$y|$y$#","",$x,1);

```

Testcases

# Answer
> 2 votes
# Python 2, ~~72~~ 65 bytes

```
a,b=input()
l=len(b)
print[[a,a[:-l]][b==a[-l:]],a[l:]][b==a[:l]]

```

Try it online!

-7 bytes thanks to @FelipeNardiBatista

# Answer
> 2 votes
# Python 2, 68 bytes

```
def f(s,c):v=len(c);print[s[v:],s[:-v],s][[s[:v],s[-v:],c].index(c)]

```

**Try it online!**

# Answer
> 2 votes
# Haskell, 49 bytes

```
f s a b|s==b=a|a/=b,h:t<-a=f(s++[h])t b|1<3=s
f""

```

Try it online! Usage: `f"" "abcdef" "ab"`. Alternatively, define `(-)=f""`and use like `"abcdef" - "ab"`.

This regex-free solution works by recursively splitting the string in all its pre- and postfixes and checking whether the string to be substracted matches one of them.

# Answer
> 1 votes
# C#, 88 bytes

```
s=>r=>s.StartsWith(r)?s.Substring(r.Length):s.EndsWith(r)?s.Substring(0,s.IndexOf(r)):s;

```

Compiles to a `Func<string, Func<string, string>>`.

# Answer
> 1 votes
# R, ~~20~~ ~~42~~ 41 bytes

```
pryr::f(sub(sprintf('^%s|%s$',b,b),'',a))

```

*-1 byte thanks to MickyT!*

Returns an anonymous function (which has arguments in the order `b,a`). Computes the string difference `a-b`. `sub` is a simple substitution that swaps the first occurrence of the pattern with, in this case, the empty string `''`. Constructs the regex with `sprintf` to match only at the beginning and end of string. Requires the `pryr` package to be installed.

On the TIO link, uses the more verbose `function(a,b)` definition for the function for four more bytes.

Try it online!

# Answer
> 1 votes
### Ruby (lambda expression), 29 bytes

```
->a,b{a.sub /^#{b}|#{b}$/,""}

```

Yay for regex interpolation! Requires regex-safe subtrahends, but that's okay as per the challenge.

# Answer
> 1 votes
# Tcl, 37 bytes

```
proc s {a b} {regsub "^$b|$b$" $a {}}

```

Try it online! (now running all tests)

Tcl is straightforward. `proc s {a b}` defines a function named `s` which takes parameters `a` and `b`. `regsub` substitutes `{}`, which is an empty string, for the value of `b` when it's at the start or end of `a`. The return is implicit.

# Answer
> 1 votes
# AWK, ~~21~~ 32 bytes

```
{sub("^"$2"|"$2"$",z,$1);$0=$1}1

```

Try it online!

Original submission naively replaced text within first string, not just at beginning or end.

```
{sub($2,z,$1);$0=$1}1

```

Try it online !

Originally tried without the braces, but it required tricks to print out empty lines and or no-matches which ended up adding more bytes than this version.

# Answer
> 1 votes
# C, 96 bytes

It's common knowledge that string manipulation in C is cumbersome, as an extension golfing would be borderline masochistic. Sounds alright to me.

```
f(a,b,t,l)char**a,*b,*t;{t=*a;l=strlen(b);bcmp(t,b,l)?bcmp(t+=strlen(t)-l,b,l)||(*t=0):(*a+=l);}

```

One of the less readable programs I've written. Takes two inputs (despite how the function looks), a `char**` pointing to the string to deconcatenate and a `char*` which is the string to remove. The input pointer is edited in place and becomes the output (who cases about memory leaks anyway).

Example usage:

```
char *a = malloc(6);
strcpy(a, "abcde");
char *b = malloc(4);
strcpy(b, "abc");
f(&a,b);
printf("%s\n", a); // "de"

```

# Answer
> 1 votes
# Common Lisp, 121 bytes

```
(lambda(x y)(cond((equal(#1=subseq x 0 #3=(length y))y)(#1#x #3#))((equal(#1#x #2=(-(length x)#3#))y)(#1#x 0 #2#))(t x)))

```

Try it online!

The usual wordy Common Lisp!

Ungolfed version:

```
(defun f(x y)
  (cond ((equal (subseq x 0 (length y)) y)               ; if x starts with y
         (subseq x (length y)))                          ; return rest of x
        ((equal (subseq x (- (length x) (length y))) y)  ; if x ends with x
         (subseq x 0 (- (length x) (length y))))         ; return first part of x
        (t x)))                                          ; else return x

```

# Answer
> 1 votes
# Kotlin, 91 bytes

```
{a,b->val v=b.length
if(a.startsWith(b))a.drop(v)else if(a.endsWith(b))a.dropLast(v)else a}

```

Try it online!

# Answer
> 1 votes
# Powershell, ~~34~~ 40 bytes

*+6 bytes when `Invalid Subtraction` test cases added*

```
param($s,$t)$s-replace"^$t(?!.*$t$)|$t$"

```

Comment:

The regexp expression `^$t|$t$` does not work as expected: it replaces both matches instead one (flag `g` always on). So, we are forced to use the negative lookahead group.

Test script:

```
$f = {
    param($s,$t)$s-replace"^$t(?!.*$t$)|$t$"
}

@(
    ,('abcde','ab', 'cde')
    ,('abcde','cde', 'ab')
    ,('abab','ab', 'ab')
    ,('abcab','ab', 'abc', 'cab')
    ,('ababcde','ab', 'abcde')
    ,('acdbcd','cd', 'acdb')
    ,('abcde','abcde', '')
    ,('abcde','', 'abcde')
    ,('','', '')

    ,('abcde','ae', 'abcde')
    ,('abcde','aa', 'abcde')
    ,('abcde','bcd', 'abcde')
    ,('abcde','xab', 'abcde')
    ,('abcde','yde', 'abcde')

    ,('','a', '')
) | % {
    $s,$t,$e = $_
    $r = &$f $s $t
    "$($r-in$e): $r"
}

```

Output:

```
True: cde
True: ab
True: ab
True: abc
True: abcde
True: acdb
True:
True: abcde
True:

```

# Answer
> 0 votes
## QBIC, 57 bytes

Whegh, this is a mess in QBIC/QBasic...

```
B=@ `+B┘x=instr(;,;)~x|?_t_sB,x-1|+_sB,x+_lC|,_lB|||\?B

B=@ `+B          Prepend a string to B$. Thisis a hack to avoid errors with
                 removing substrings stating at index 1
┘                Line-break in QBasic output
       (;,;)     Read the string (B$) and the to-be-removed substring (C$)
x=instr          And make x to be the starting index of the first C$ in B$
~x|              IF X <> 0 (ie C$ is present in B$)
?                PRINT
 _t                trimmed version (drops the prepended space)
  _sB,x-1|+        of a substring from 1 to x (the start of C$) -1
  _sB,x+_lC|,_lB   and the rest of the string, starting after C$
                     _l takes the length of a string
  |||              End TRIM, end Substring, end Length
\?B              When missing C$, just print B$

```

# Answer
> 0 votes
I initially misread the instructions. Thanks, Ørjan Johansen for pointing out my mistake!

# PowerShell, 46 51 bytes

```
Function F($o,$a){([regex]"^$a").replace($o,'',1);}

```

Try it online!

# Answer
> 0 votes
# Lua, ~~71~~ 65 bytes

Accepting suggestions

```
a,b=...p='(.*)'print(a:match('^'..b..p)or a:match(p..b..'$')or a)

```

Try it online!

# Answer
> 0 votes
# Excel, 129 bytes

```
=IFERROR(IF(FIND(B1,A1)=1,SUBSTITUTE(A1,B1,"",1),IF(FIND(B1,A1,LEN(A1)-LEN(B1))>LEN(A1)-LEN(B1),LEFT(A1,LEN(A1)-LEN(B1)),A1)),A1)

```

# Answer
> 0 votes
# sed, ~~56~~ 53 bytes

```
s/^(.*),(.*)\1$/\2/
s/^(.*),\1(.*)$/\2/
s/.*,(.*)/\1/

```

Try it online!

# Answer
> 0 votes
# Pip, 19 bytes

```
Y'^.X:baRyNa?yb.'$x

```

Try it online!

Kinda sad this isn't shorter. The main problem is that Pip's `R` operator replaces *all* matches, not just the first one; otherwise, `aR"^|$"J Xbx` would work for 12 bytes.

```
                     a, b are command-line args; x is empty string (implicit)
    X:b              Convert b to a regex in-place
 '^.                 Prepend ^
Y                    and yank that regex into the y variable
       aR         x  In a, replace the following expression with the empty string:
         yNa?         Is there a match of y in a? I.e., does b match at the beginning of a?
             y        If so, replace y (b at the beginning of a)
              b.'$    If not, replace b with $ appended (b at the end of a)

```

# Answer
> 0 votes
# Kotlin, ~~62~~ ~~42~~ 56 bytes

*+12 bytes I think that type definitions are mandatory in the Kotlin lambda with 2 arguments*

```
{a:String,b:String->Regex("^$b|$b$").replaceFirst(a,"")}

```

Test script:

```
var f = {a:String,b:String->Regex("^$b|$b$").replaceFirst(a,"")}

fun main(args: Array<String>) {
    println(f("abcde","ab"))
    println(f("abcab","ab"))
    println(f("abcde","bcd"))
}

```

Output:

```
cde
cab
abcde

```

## Kotlin (without Regex), ~~62~~ 76 bytes

```
{a:String,b:String->var c=a.removePrefix(b)
if(a==c){c=a.removeSuffix(b)}
c}

```

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


title: Monte Carlo estimator of Pi

text:
# Question
Title: Monte Carlo estimator of Pi
Happy Pi Day everyone! For no reason at all, I'm trying to construct a Monte Carlo estimator of Pi that is as short as possible. Can we construct one that can fit in a tweet?

To clarify, what I have in mind is the typical approach of drawing random points from the unit square and calculating the ratio that fall within the unit circle. The number of samples can be hard coded or not. If you hardcode them, you must use at least 1000 samples. The result may be returned or printed as a floating point, fixed point or rational number.

No trig functions or Pi constants, must be a Monte Carlo approach.

This is code golf, so the shortest submission (in bytes) wins.

# Answer
# 80386 machine code, 40 38 bytes

Hexdump of the code:

```
60 33 db 51 0f c7 f0 f7 e0 52 0f c7 f0 f7 e0 58
03 d0 72 03 83 c3 04 e2 eb 53 db 04 24 58 db 04
24 58 de f9 61 c3

```

How to get this code (from assembly language):

```
    // ecx = n (number of iterations)
    pushad;
    xor ebx, ebx; // counter
    push ecx; // save n for later
myloop:
    rdrand eax; // make a random number x (range 0...2^32)
    mul eax; // calculate x^2 / 2^32
    push edx;
    rdrand eax; // make another random number y
    mul eax; // calculate y^2 / 2^32
    pop eax;
    add edx, eax; // calculate D = x^2+y^2 / 2^32 (range 0...2^33)
    jc skip; // skip the following if outside the circle
    add ebx, 4; // accumulate the result multiplied by 4
skip:
    loop myloop;
    push ebx; // convert the result
    fild dword ptr [esp]; // to floating-point
    pop eax;
    fild dword ptr [esp]; // convert n to floating-point
    pop eax;
    fdivp st(1), st; // divide

    popad;
    ret;

```

This is a function using MS `fastcall` calling convention (number of iterations is passed in register `ecx`). It returns the result in the `st` register.

Fun things about this code:

* `rdrand` \- just 3 bytes to generate a random number!
* It uses (unsigned) integer arithmetic until the final division.
* The comparison of squared distance (`D`) with squared radius (`2^32`) is performed automatically - the carry flag contains the result.
* To multiply the count by 4, it counts the samples in steps of 4.
> 17 votes

# Answer
# Matlab/Octave, 27 bytes

I know there already is a Matlab/Octave answer, but I tried my own approach. I used the fact that the integral of `4/(1+x^2)` between 0 and 1 is pi.

```
mean(4./(1+rand(1,1e5).^2))

```
> 12 votes

# Answer
# CJam, ~~27 23~~ 22 or 20 bytes

```
4rd__{{1dmr}2*mhi-}*//

```

*2 bytes saved thanks to Runner112, 1 byte saved thanks to Sp3000*

It takes the iteration count from STDIN as an input.

This is as straight forward as it gets. These are the major steps involved:

* Read the input and run the Monte Carlo iterations that many times
* In each iteration, get sum of square of two random floats from 0 to 1 and see if it is less than 1
* Get the ratio of how many times we got less than 1 by total iterations and multiply it by 4 to get PI

**Code expansion**:

```
4rd                     "Put 4 on stack, read input and convert it to a double";
   __{            }*    "Take two copies, one of them determines the iteration"
                        "count for this code block";
      {1dmr}2*          "Generate 2 random doubles from 0 to 1 and put them on stack";
              mh        "Take hypot (sqrt(x^2 + y^2)) where x & y are the above two numbers";
                i       "Convert the hypot to 0 if its less than 1, 1 otherwise";
                 -      "Subtract it from the total sum of input (the first copy of input)";
                    //  "This is essentially taking the ratio of iterations where hypot";
                        "is less than 1 by total iterations and then multiplying by 4";

```

Try it online here

---

If average value of `1/(1+x^2)` is also considered as Monte Carlo, then this can be done in 20 bytes:

```
Urd:K{4Xdmr_*)/+}*K/

```

Try it here
> 7 votes

# Answer
# R, 40 (or 28 or 24 using other methods)

```
mean(4*replicate(1e5,sum(runif(2)^2)<1))

mean(4*sqrt(1-runif(1e7)^2))

mean(4/(1+runif(1e7)^2))

```

# Python 2, 56

Another Python one, if numpy is allowed, but pretty similar to Matlab/Octave:

```
import numpy;sum(sum(numpy.random.rand(2,8e5)**2)<1)/2e5

```
> 7 votes

# Answer
# Mathematica, ~~42~~ ~~40~~ 39 bytes (or 31/29?)

I've got three solutions all at 42 bytes:

```
4Count[1~RandomReal~{#,2},p_/;Norm@p<1]/#&
4Tr@Ceiling[1-Norm/@1~RandomReal~{#,2}]/#&
4Tr@Round[1.5-Norm/@1~RandomReal~{#,2}]/#&

```

They are all unnamed functions that take the number of samples `n` andd return a rational approximating π. First they all generate `n` points in the unit square in the positive quadrant. Then they determine the number of those samples that lie within the unit circle, and then they divide by the number of samples and multiply by `4`. The only difference is in how they determine the number of sampples inside the unit circle:

* The first one uses `Count` with the condition that `Norm[p] < 1`.
* The second one subtracts the norm of each point from `1` and then rounds up. This turns numbers inside the unit circle to `1` and those outside to `0`. Afterwards I just sum them all up with `Tr`.
* The third one does essentially the same, but subtracts the from `1.5`, so I can use `Round` instead of `Ceiling`.

Aaaaaand *while* writing this up, it occurred to me that there is indeed a shorter solution, if I just subtract from `2` and then use `Floor`:

```
4Tr@Floor[2-Norm/@1~RandomReal~{#,2}]/#&

```

or saving another byte by using the Unicode flooring or ceiling operators:

```
4Tr@⌊2-Norm/@1~RandomReal~{#,2}⌋/#&
4Tr@⌈1-Norm/@1~RandomReal~{#,2}⌉/#&

```

Note that the three rounding-based solutions can also be written with `Mean` instead of `Tr` and without the `/#`, again for the same bytes.

---

If other Monte Carlo based approaches are fine (specifically, the one Peter has chosen), I can do 31 bytes by estimating the integral of `√(1-x<sup>2</sup>)` or 29 using the integral of `1/(1+x<sup>2</sup>)`, this time given as a floating point number:

```
4Mean@Sqrt[1-1~RandomReal~#^2]&
Mean[4/(1+1~RandomReal~#^2)]&

```
> 6 votes

# Answer
# Commodore 64 Basic, 45 bytes

```
1F┌I=1TO1E3:C=C-(R/(1)↑2+R/(1)↑2<1):N─:?C/250

```

PETSCII substitutions:  = `SHIFT+E`, `/` = `SHIFT+N`,  = `SHIFT+O`

Generates 1000 points in the first quadrant; for each, adds the truthness of "x^2+y^2\<1" to a running count, then divides the count by 250 to get `pi`. (The presence of a minus sign is because on the C64, "true" = -1.)
> 6 votes

# Answer
# Python 2, ~~77~~ 75 bytes

```
from random import*;r=random;a=0;exec"a+=r()**2+r()**2<1;"*4000;print a/1e3

```

Uses 4000 samples to save bytes with `1e3`.
> 5 votes

# Answer
# J, 17 bytes

Computes the mean value of `40000` sample values of the function `4*sqrt(1-sqr(x))` in the range `[0,1]`.

Handily `0 o.x` returns `sqrt(1-sqr(x))`.

```
   1e4%~+/0 o.?4e4$0
3.14915

```
> 5 votes

# Answer
# Java, 108 bytes

```
double π(){double π=0,x,i=0;for(;i++<4e5;)π+=(x=Math.random())*x+(x=Math.random())*x<1?1e-5:0;return π;}

```

Four thousand iterations, adding 0.001 each time the point is inside the unit circle. Pretty basic stuff.

*Note:* Yes, I know I can shed four bytes by changing `π` to a single-byte character. I like it this way.
> 4 votes

# Answer
**Matlab or Octave 29 bytes** (thanks to flawr!)

```
mean(sum(rand(2,4e6).^2)<1)*4

```

(I am no quite sure if \<1 is OK. I read it should be \<=1. But how big is the probability to draw exactly 1...)

**Matlab or Octave 31 bytes**

```
sum(sum(rand(2,4e3).^2)<=1)/1e3

```
> 4 votes

# Answer
## \>\<\> (Fish), 114 bytes

```
:00[2>d1[   01v
1-:?!vr:@>x|  >r
c]~$~< |+!/$2*^.3
 .41~/?:-1r
|]:*!r$:*+! \
r+)*: *:*8 8/v?:-1
;n*4, $-{:~ /\r10.

```

Now, \>\<\> doesn't have a built-in random number generator. It does however have a function that sends the pointer in a random direction. The random number generator in my code:

```
______d1[   01v
1-:?!vr:@>x|  >r
_]~$~< |+!/$2*^__
 __________
___________ _
_____ ____ _______
_____ ____~ ______

```

It basically generates random bits that make up a binary number and then converts that random binary number to decimal.

The rest is just the regular points in the square approach.

Usage: when you run the code you must make sure to prepopulate the stack (-v in python interpreter) with the number of samples, for example

```
pi.fish -v 1000

```

returns

```
3.164

```
> 4 votes

# Answer
## **Javascript: 62 Bytes**

```
for(r=Math.random,t=c=8e4;t--;c-=r()**2+r()**2|0);alert(c/2e4)

```

I used the previous (now deleted) javascript answer and shaved 5 bytes.
> 3 votes

# Answer
# Python 2, ~~90~~ ~~85~~ 81 bytes

```
from random import*;r=random;print sum(4.for i in[0]*9**7if r()**2+r()**2<1)/9**7

```

returns `3.14120037157` for example. The sample count is 4782969 (9^7). You can get a better pi with 9^9 but you will have to be patient.
> 2 votes

# Answer
## GolfScript (34 chars)

```
0{^3?^rand.*^.*+/+}2000:^*`1/('.'@

```

Online demo

This uses fixed point because GS doesn't really have floating point. It slightly abuses the use of fixed point, so if you want to change the iteration count make sure that it's twice a power of ten.

Credit to xnor for the particular Monte Carlo method employed.
> 2 votes

# Answer
# Ruby, 39 bytes

```
p (1..8e5).count{rand**2+rand**2<1}/2e5

```

One of the highlight is that this one is able to use `8e5` notation, which makes it extendable up to ~8e9 samples in the same program byte count.
> 2 votes

# Answer
# Perl 6, 33 bytes

```
{4*sum((1>rand²+rand²)xx$_)/$_}

```

Try it online!

This is a function that takes the number of samples as an argument.
> 2 votes

# Answer
# Scala, 87 77 66 bytes

```
def s=math.pow(math.random,2);Seq.fill(1000)(s+s).count(_<1)/250d

```
> 1 votes

# Answer
# dc, 59 characters (whitespace is ignored)

```
[? 2^ ? 2^ + 1>i]su
[lx 1+ sx]si
[lu x lm 1+ d sm ln>z]sz

5k
?sn
lzx
lx ln / 4* p
q

```

I tested this on Plan 9 and OpenBSD, so I imagine it will work on Linux (GNU?) `dc`.

## Explanation by line:

1. Stores code to \[read and square two floats; execute register `i` if 1 is greater than the sum of their squares\] in register `u`.
2. Stores code to \[increment register `x` by 1\] in register `i`.
3. Stores code to \[execute register `u`, increment register `m`, and then execute register `z` if register `m` is greater than register `n`\] in register `z`.
4.
5. Set the scale to 5 decimal points.
6. Read the number of points to sample from the first line of input.
7. Execute register `z`.
8. Divide register `x` (the number of hits) by register `n` (the number of points), multiply the result by 4, and print.
9. Quit.

## However, I cheated:

The program needs a supply of random floats between 0 and 1.

```
/* frand.c */
#include <u.h>
#include <libc.h>

void
main(void)
{
    srand(time(0));

    for(;;)
        print("%f\n", frand());
}

```

## Usage:

```
#!/bin/rc
# runpi <number of samples>

{ echo $1; frand } | dc pi.dc

```

## Test run:

```
% runpi 10000
3.14840

```

# Now with less cheating (100 bytes)

Someone pointed out that I could include a simple prng.
http://en.wikipedia.org/wiki/RANDU

```
[lrx2^lrx2^+1>i]su[lx1+sx]si[luxlm1+dsmln>z]sz[0kls65539*2 31^%dsslkk2 31^/]sr?sn5dksk1sslzxlxlm/4*p

```

## Ungolfed

```
[
Registers:
u - routine : execute i if sum of squares less than 1
i - routine : increment register x
z - routine : iterator - execute u while n > m++
r - routine : RANDU PRNG
m - variable: number of samples
x - variable: number of samples inside circle
s - variable: seed for r
k - variable: scale for division
n - variable: number of iterations (user input)
]c
[lrx 2^ lrx 2^ + 1>i]su
[lx 1+ sx]si
[lu x lm 1+ d sm ln>z]sz
[0k ls 65539 * 2 31^ % d ss lkk 2 31 ^ /]sr
? sn
5dksk
1 ss
lzx
lx lm / 4*
p

```

## Test run:

```
$ echo 10000 | dc pigolf.dc
3.13640

```
> 1 votes

# Answer
# Joe, 20 19 bytes

Note: this answer is non-competing, because version 0.1.2, which added randomness, was released after this challenge.

Named function F:

```
:%$,(4*/+1>/+*,?2~;

```

Unnamed function:

```
%$,(4*/+1>/+*,?2~;)

```

These both take the sample count as an argument and return the result. How do they work?

```
%$,(4*/+1>/+*,?2~;)
   (4*/+1>/+*,?2~;) defines a chain, where functions are called right-to-left
               2~;  appends 2 to the argument, giving [x, 2]
              ?     create a table of random values from 0 to 1 with that shape
            *,      take square of every value
          /+         sum rows, giving a list of (x**2+y**2) values
        1>           check if a value is less than 1, per atom
      /+             sum the results
    4*               multiply by four
%$,                  divide the result by the original parameter

```

Example runs:

```
   :%$,(4*/+1>/+*,?2~;
   F400000
3.14154
   F400000
3.14302

```
> 1 votes

# Answer
# Pure Bash, 65 bytes

```
for((;i++<$1*4;a+=RANDOM**2+RANDOM**2<32767**2));{ :;}
echo $a/$1

```

Takes a single command-line parameter which is multiplied by 4 to give the number of samples. Bash arithmetic is integer-only, so a rational is output. This may be piped to `bc -l` for the final division:

```
$ ./montepi.sh 10000
31477/10000
$ ./montepi.sh 10000|bc -l
3.13410000000000000000
$

```
> 1 votes

# Answer
# Pyth, 19

```
c*4sm<sm^OQ2 2*QQQQ

```

Give the desired number of iterations as input.

Demonstration

Since Pyth doesn't have a "Random floating number" function, I had to improvise. The program choose two random positive integers less than the input, squares, sums, and compared to the input squared. This performed a number of times equal to the input, then the result is multiplied by 4 and divided by the input.

In related news, I will be adding a random floating point number operation to Pyth shortly. This program does not use that feature, however.

---

If we interpret "The result may be returned or printed as a floating point, fixed point or rational number." liberally, then printing the numerator and denominator of the resulting fraction should be sufficient. In that case:

# Pyth, 18

```
*4sm<sm^OQ2 2*QQQQ

```

This is an identical program, with the floating point division operation (`c`) removed.
> 1 votes

# Answer
# Julia, 37 bytes

```
4mean(1-floor(sum(rand(4^8,2).^2,2)))

```

The number of samples is 65536 (=4^8).

A sligthly longer variant: a function with number of samples `s` as the only argument:

```
s->4mean(1-floor(sum(rand(s,2).^2,2)))

```
> 1 votes

# Answer
# C, 130 bytes

```
#include<stdlib.h>f(){double x,y,c=0;for(int i=0;i<8e6;++i)x=rand(),y=rand(),c+=x*x+y*y<1.0*RAND_MAX*RAND_MAX;printf("%f",c/2e6);}

```

Ungolfed:

```
#include <stdlib.h>
f(){
 double x,y,c=0;
 for(int i=0; i<8e6; ++i) x=rand(), y=rand(), c+=x*x+y*y<1.0*RAND_MAX*RAND_MAX;
 printf("%f",c/2e6);
}

```
> 1 votes

# Answer
## Racket 63 bytes

Using method of R language answer by @Matt :

```
(/(for/sum((i n))(define a(/(random 11)10))(/ 4(+ 1(* a a))))n)

```

Ungolfed:

```
(define(f n)
   (/
    (for/sum ((i n))
      (define a (/(random 11)10))
      (/ 4(+ 1(* a a))))
    n))

```

Testing:

```
(f 10000)

```

Output (fraction):

```
3 31491308966059784/243801776017028125

```

As decimal:

```
(exact->inexact(f 10000))

3.13583200307849

```
> 1 votes

# Answer
# Haskell, ~~116~~ ~~114~~ ~~110~~ 96 bytes

```
d=8^9
g[a,b]=sum[4|a*a+b*b<d*d]
p n=(sum.take(floor n)$g<$>iterate((\x->mod(9*x+1)d)<$>)[0,6])/n

```

Because dealing with `import System.Random; r=randoms(mkStdGen 2)` would take too many precious bytes, I generate an infinite list of random numbers with the linear congruential generator that some say is almost cryptographically strong: `x↦x*9+1 mod 8^9`, which by the Hull-Dobell Theorem has the full period of `8^9`.

`g` yields `4` if the random number point is inside the circle for pairs of random numbers in `[0..8^9-1]` because this eliminates a multiplication in the formula used.

Usage:

```
> p 100000
3.14208

```

Try it online!
> 1 votes

# Answer
# Actually, 14 bytes

```
`G²G²+1>`nkæ4*

```

Try it online!

The number of samples is given as input (rather than hard-coded).

Explanation:

```
`G²G²+1>`nkæ4*
`G²G²+1>`n      do the following N times:
 G²G²+            rand()**2 + rand()**2
      1>          is 1 greater?
          kæ    mean of results
            4*  multiply by 4

```
> 1 votes

# Answer
# Fortran (GFortran), ~~84~~ 83 bytes

```
CALL SRAND(0)
DO I=1,4E3
X=RAND()
Y=RAND()
IF(X*X+Y*Y<1)A=A+1E-3
ENDDO
PRINT*,A
END

```

Try it online!

This code is very bad wrote. It will fail if gfortran decide to initialize variable `A` with other value then 0 (which occurs 50% of the compilations, approximately) and, if `A` is initialized as 0, it will always generate the same random sequence for the given seed. Then, the same value for Pi is printed always.

This is a much better program:

# Fortran (GFortran), ~~100~~ 99 bytes

```
A=0
DO I=1,4E3
CALL RANDOM_NUMBER(X)
CALL RANDOM_NUMBER(Y)
IF(X*X+Y*Y<1)A=A+1E-3
ENDDO
PRINT*,A
END

```

Try it online!

(One byte saved in each version; thanks Penguino).
> 1 votes

# Answer
# Japt, 26 or 18 bytes

```
o r_+ÂMhMr p +Mr p <1Ã*4/U

```

Try it online!

Analogous to Optimizer's answer, mainly just trying to learn Japt.
Takes the number of iterations to run for as the implicit input `U`.

```
o                           Take the input and turn it into a range [0, U),
                            essentially a cheap way to get a large array.
  r_                        Reduce it with the default initial value of 0.
    +Â                      On each iteration, add one if
      MhMr p +Mr p          the hypotenuse of a random [0,1)x[0,1) right triangle
                   <1       is smaller than one.
                     Ã*4/U  Multiply the whole result by four and divide by input.

```

If `1/(1+x^2)` is allowed (instead of two separate randoms), then we can achieve 18 bytes with the same logic.

```
o r_Ä/(1+Mr pÃ*4/U

```
> 1 votes

# Answer
# F#, 149 bytes

```
open System;
let r=new Random()
let q()=
 let b=r.NextDouble()
 b*b
let m(s:float)=(s-Seq.sumBy(fun x->q()+q()|>Math.Sqrt|>Math.Floor)[1.0..s])*4.0/s

```

Try it online!

As far as I can make out, to do this kind of running total in F# it's shorter to create an array of numbers and use the `Seq.sumBy` method than use a `for..to..do` block.

What this code does it that it creates a collection of floating-point numbers from 1 to `s`, performs the function `fun x->...` for the number of elements in the collection, and sums the result. There are `s` elements in the collection, so the random test is done `s` times. The actual numbers in the collection are ignored (`fun x->`, but `x` is not used).

It also means that the application has to first create and fill the array, and then iterate over it. So it's probably twice as slow as a `for..to..do` loop. And with the array creation memory usage is in the region of O(f\**k)!

For the actual test itself, instead of using an `if then else` statement what it does is it calculates the distance (`q()+q()|>Math.Sqrt`) and rounds it down with `Math.Floor`. If the distance is within the circle, it'll be rounded down to 0. If the distance is outside the circle it'll be rounded down to 1. The `Seq.sumBy` method will then total these results.

Note then that what `Seq.sumBy` has totalled is not the points *inside* the circle, but the points *outside* it. So for the result it takes `s` (our sample size) and subtracts the total from it.

It also appears that taking a sample size as a parameter is shorter than hard-coding the value. So I am cheating a little bit...
> 1 votes

# Answer
# Perl 5, 34 bytes

```
$_=$a/map$a+=4/(1+(rand)**2),1..$_

```

The number of samples is taken from stdin. Requires `-p`.

Works because:

Try it online!
> 1 votes

# Answer
# MathGolf, 11 bytes

```
0♫ô4ƒ²)/+♫/

```

Try it online!

## Explanation

```
0            Push 0 (used for the sum)
 ♫           Push 10000
  ô          Start block of length 6
   4         Push 4
    ƒ²       Push random float in range [0,1) and square
      )      Increment by 1
       /     Divide
        +    Add result to the total sum (last instruction of block)
         ♫/  Divide by 10000

```

I'll add an explanation tomorrow. It performs 10000 iterations using the same integral as many other languages.

Assuming number of iterations as input:

# MathGolf, 10 bytes

```
ô4ƒ²)/+\/(

```

Try it online!

## Explanation

```
ô           Start block of length 6
 4          Push 4
  ƒ²        Push random float in range [0,1) and square
    )       Increment by 1
     /      Divide
      +     Add result to the total sum (last instruction of block)
            The first iteration, this adds the result to the implicit input, meaning that if the input is 10000 and the result is 3.1, 10003.1 is pushed on the stack. The end result is 10000 too large.
       \    Swap the top two elements on the stack (pushes the implicit input to the top)
        /   Divide (Since the sum is wonky, this is around 4.14159...)
         (  Decrement by one, resulting in 3.14159...)

```
> 1 votes

# Answer
# APL(NARS), 79 chars, 158 bytes

```
r←q;f;i
   f←{1e8÷⍨?1e8}⋄i←r←0
A: i←i+1⋄r←r+1>(f*2)+f*2⋄→A×⍳i<1e5
   r←4×r÷1e5

```

%pi=3.1415926535897932385... test:

```
  q
3.14284
  q
3.14256
  q
3.13832

```
> 1 votes

# Answer
# Go, ~~130~~ 116 bytes

```
import."math/rand";func p(){r,c,i:=Float64,0,1e6;for;i>0;i--{a,b:=r(),r();if a*a+b*b<1{c+=4}};print(float64(c)/1e6)}

```

No real tricks here, other than aliasing `rand.Float64` and `float64` to save a few bytes.

Run it here: http://play.golang.org/p/F5YniIncor

Please note that random on play.golang.org cannot be seeded by time (since the date is always the same) so you need to change the seed manually.

1e6 is used since the run time is too long for play.golang.org if I set it higher.

*Edit*: No longer takes an input, outputs the computed value itself.
> 0 votes

# Answer
# Python 3, 69 bytes

Apparently shorter than the other python entries, save one that uses ~~sympy~~ numpy (misremembered)

```
from random import*
print(eval(('+(1>('+2*'+random()**2)')*2000)/500)

```

**Try it online!**

Wow, it's been a while since I posted a multiline answer on this site... I've been using Turtlèd too much for that

Explanation:

```
from random import*    We can use random.random now as random
print(                 Print the result of the following
      eval(            evaluate the value of the expression in the string
           ('+(1>('+2*'+random()**2)')*2000    the string construction
                                           )/500) divide by 500 and print

```

Explanation of the string expression:

```
                             *2000  repeat this 2000 times
    '+(1>('                         have each section joined by a +,
                                    and the first item have the unary +. (nop, essentially)
                                    check if the section is less than 1, if so,
                                    evaluate to 1, else 0
           +2*'+random()**2)'        sum two random numbers squared, close both parens.

                                   [Evaluate the sum]

```

This is about the max accuracy, because 3000 samples gives a recursion error.

(I'll improve this explanation real soon actually.)
> 0 votes

# Answer
# Pyt, 22 bytes

```
Đ0⇹`⇹ṛ²ṛ²+1≤+⇹⁻łŕ⇹ᵮ/4*

```

Try it online!

Explanation:

```
          Implicit input [the number of random points to be sampled]
Đ         Duplicate input
0         Push zero
⇹         Swap the top two items on the stack
`...(ł)   Do ... (while the top of the stack is not 0)
⇹         Swap the top two items on the stack
ṛ²ṛ²+     Add the squares of two random floats (between 0 and 1)
1≤        Is the sum less than or equal to 1?
+         Add the top two items on the stack [auto-converts boolean to int]
⇹         Swap the top two items on the stack
⁻         Decrement the top of the stack by 1
(`)...ł   (Do ...) while the top of the stack is not 0
ŕ         Remove the top of the stack
⇹         Swap the top two items on the stack
ᵮ         Cast the top of the stack to a float
/         Divide
4*        Multiply by 4
          Implicit output

```
> 0 votes

---
Tags: code-golf, random, pi, approximation
---