title: Smallest Bytecode Interpreter/VM

text:
# Question
Title: Smallest Bytecode Interpreter/VM
**Leaderboard - JIT Compiled (Lower is better)**

> 1. es1024 - 81.2 points (including a working compiler!)
> 2. Kieth Randall - 116 points
> 3. Ell - 121 points

**Leaderboard - Interpreted (Lower is better)**

> 1. Martin Büttner - 706654 points (somewhere around 2 hours).
> 2. criptych - 30379 points (97 seconds)

Your mission, should you choose to accept it, is to write the smallest possible bytecode interpreter/VM. The VM/interpreter uses a small CISC architecture (operations can vary in size), with the language specified below. Upon completion, you must print the value of the 3 CPU registers to prove that the correct output is printed (3,126,900,366).

**Compiler**

If you'd like to make your own tests, a compiler is posted below. Feel free to post your tests with your answer.

```
window.compile=function(){var e=$("#text").val().toLowerCase().match(/[^\r\n]+/g);var t=[];for(var n=0;n<e.length;n++)compileLine(e[n],t);var r="";for(var n=0;n<t.length;n++)if(typeof t[n]=="string")r+="\n";else r+="0x"+t[n].toString(16)+" ";$("#compiledArray").val(r)};window.compileLine=function(e,t){var n=e.split(" ");if(n[0]=="load"){t.push(0);t.push(getInt(n[1]));t.pushArr(getInt(n[2]))}if(n[0]=="rload"){t.push(1);t.push(getInt(n[1]));t.push(getInt(n[1]))}if(n[0]=="push"){t.push(2);t.push(getInt(n[1]))}if(n[0]=="pop"){t.push(3);t.push(getInt(n[1]))}if(n[0]=="add"){t.push(4);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="sub"){t.push(5);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="mul"){t.push(6);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="div"){t.push(7);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="jmp"){t.push(8);t.pushArr(getInt(n[1]))}if(n[0]=="cmp"){t.push(9);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="branchlt"){t.push(10);t.pushArr(getInt(n[1]))}if(n[0]=="brancheq"){t.push(11);t.pushArr(getInt(n[1]))}if(n[0]=="branchgt"){t.push(12);t.pushArr(getInt(n[1]))}if(n[0]=="branchne"){t.push(13);t.pushArr(getInt(n[1]))}t.push("NEW LINE")};window.getInt=function(e){if(e.trim().startsWith("<--"))return"COMMENT";if(e=="r0")return 0;if(e=="r1")return 1;if(e=="r2")return 2;if(e.startsWith("0x"))return parseInt(e,16);if(isNaN(parseInt(e)))alert(e);return getIntBytes(parseInt(e))};if(typeof String.prototype.startsWith!="function"){String.prototype.startsWith=function(e){return this.slice(0,e.length)==e}}Array.prototype.pushArr=function(e){this.push.apply(this,e)};window.getIntBytes=function(e){var t=[];var n=4;do{t[--n]=e&255;e=e>>8}while(n);return t}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<textarea id="text" cols="40" rows="10"></textarea>
<br/>
<button onclick="compile()">Compile</button>
<br/>
<textarea id="compiledArray"  cols="40" rows="10" readonly></textarea>
```

**"VM" Specifications**

The VM has 3 32 bit unsigned integral registers: R0, R1, R2. They are represented in hex as 0x00, 0x01, and 0x02.

The following operations must be supported:

The format is \[name\] \[...operands...\], \[hexadecimal op-code\] \[...operands repeated...\]

* LOAD \[register\] \[4 byte value\], 0x00 \[register\] \[4 byte value\]
* PUSH \[register\], 0x02 \[register\]
* POP \[register\], 0x03 \[register\]
* ADD \[register, 1 byte\] \[register, 1 byte\], 0x04 \[register\] \[register\]
* SUB \[register, 1 byte\] \[register, 1 byte\], 0x05 \[register\] \[register\]
* MUL \[register, 1 byte\] \[register, 1 byte\], 0x06 \[register\] \[register\]
* DIV \[register, 1 byte\] \[register, 1 byte\], 0x07 \[register\] \[register\]
* JMP \[code line, 4 bytes\], 0x08 \[4 byte code line number\]
* CMP \[register, 1 byte\] \[register, 1 byte\], 0x09 \[register\] \[register\]
* BRANCHLT \[code line, 4 bytes\], 0x0a \[4 byte code line number\]

Some notes:

* The above math operations add the values of 2 registers together, placing the output in the first register.
* CMP, the comparison operator, should compare the values of 2 registers and store the output in some internal flag (this can be implementation specific) for future use on branch instructions.
* If BRANCH is called before CMP, unless BRANCHEQ is called, the "VM" should not branch.
* PUSH/POP unsurprisingly push or pop numbers from the stack.
* Jump and Branch operators jump to a specific operation (line of code), not a binary address.
* Branch operations do not do the comparison. Rather, they take the output from the last comparison to execute.
* Branch and Jump operators use a zero based line number indexing system. (E.g. JMP 0 jumps to the first line)
* All operations are to be performed on unsigned numbers which overflow to zero and do not throw an exception on an integer overflow.
* Division by zero is not allowed and as such, the behavior of the program is not defined. You can (for example)...
    + Crash the program.
    + End execution of the VM and return it's current state.
    + Show a "ERR: Division by 0" message.
* Termination of the program is defined as when the instruction pointer reaches the end of the program (a non empty program can be assumed).

**Output** The output must be exactly this (newlines included)

```
R0 3126900366
R1 0
R2 10000

```

**Points** Points are calculated based on the following formula: `Number Of Characters * (Seconds Needed To Run / 2)`

To avoid hardware differences causing different times, each test will be run on my computer (i5-4210u, 8GB ram) in either ubuntu server or Windows 8, so try not to use some insane-exotic-runtime that only compiles on a Dual G5 Mac Pro with exactly 762.66 mb of free RAM.

If you are using a specialized runtime/language, please post a link to it.

**Test Program**

The idea came from here, so we'll use a somewhat modified version of their program.

The correct output for the program is: 3,126,900,366

In C:

```
int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
    for (j = 0; j < 10000; j++)
        s += (i * j) / 3;
}

```

In code: \[R0 is representative of s, R1 of j, R2 of i\]

```
LOAD R0 0
LOAD R2 0 <--outer loop value
LOAD R1 0 <--inner loop value
     --Begin inner loop--
PUSH R1 <--push inner loop value to the stack
MUL R1 R2 <--(i*j)
PUSH R2
LOAD R2 3
DIV R1 R2 <-- / 3
POP R2
ADD R0 R1 <-- s+=
POP R1
PUSH R2
LOAD R2 1
ADD R1 R2 <--j++
POP R2
PUSH R2
LOAD R2 10000
CMP R1 R2 <-- j < 10000
POP R2
BRANCHLT 3 <--Go back to beginning inner loop
--Drop To outer loop--
LOAD R1 1
ADD R2 R1 <--i++
LOAD R1 10000
CMP R2 R1 <-- i < 10000
LOAD R1 0 <--Reset inner loop
BRANCHLT 2

```

In binary/hex:

```
0x00 0x00 0x00 0x00 0x00 0x00
0x00 0x02 0x00 0x00 0x00 0x00
0x00 0x01 0x00 0x00 0x00 0x00
0x02 0x01
0x06 0x01 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x03
0x07 0x01 0x02
0x03 0x02
0x04 0x00 0x01
0x03 0x01
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x01
0x04 0x01 0x02
0x03 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x27 0x10
0x09 0x01 0x02
0x03 0x02
0x0a 0x00 0x00 0x00 0x03
0x00 0x01 0x00 0x00 0x00 0x01
0x04 0x02 0x01
0x00 0x01 0x00 0x00 0x27 0x10
0x09 0x02 0x01
0x00 0x01 0x00 0x00 0x00 0x00
0x0a 0x00 0x00 0x00 0x02

```

**Bonus Points** (Effects are applied multiplicatively) E.g. if you qualify for all three, it would be ((characters * 0.50) * 0.75) * 0.90

* 50% decrease if the interpreter is actually a JIT compiler
* 25% decrease if it applies any sort of loop unrolling/meaningful optimization.
* 10% decrease if you extend the VM with
    + BRANCHEQ \[code line, 4 bytes\] (Branch if equal - opcode 0x0b)
    + BRANCHGT \[code line, 4 bytes\] (Branch if greater than - opcode 0x0c)
    + BRANCHNE \[code line, 4 bytes\] (Branch if not equal - opcode 0x0d)
    + RLOAD \[register 1\] \[register 2\] (move the value of register 2 to register 1 - opcode 0x01).

**Disallowed**

* Precompiling the test case into the program is prohibited. You must either accept the bytecode from STDIN or from a file (Doesn't matter which).
* Returning the output without running the program.
* Any other way you can think of to cheat the VM requirement.

# Answer
> 8 votes
# C, 752 (589+163 for define flags) * 0.5 (JIT) * 0.9 (extensions) * (0.75 optimization) * (0.64 seconds/2) = 81.216

```
C[S],J[S],i,j,k,y,c,X,Y,Z;char*R,a,b[9];main(x){R=mmap(0,S,6,34,-1,0);N=85;while(scanf("%c%s%*[ R]%d%*[ R]%d",&a,b,&x,&y)&&~getchar())a-=65,a-1?a-15?a-9?a?a-2?a-3?a-11?a-12?a-17?(N=41,v):(N=137,v):(N=137,u,N=247,g(H,4),N=139,u):(y?N=189+x,s(y):(N=51,g(G,G))):(N=137,u,N=247,g(H,6),N=139,u):(N=57,v,s(0xFC8A9F),--j):(N=1,v):(N=233,J[k++]=i,s(x)):b[1]-80?N=85+x:(N=93+x):(c=b[5],s(0x0F9EE78A),N=(c-69?c-71?c-76?1:8:11:0)+132,J[k++]=i,s(x)),C[++i]=j;U(E8,X)U(F0,Y)U(F8,Z)s(50013);i=j;while(k--)j=C[J[k]]+1,R[j-1]-233&&(j+=4),s(C[*(int*)(R+j)]-j-4);((int(*)())R)();printf("%u %u %u\n",X,Y,Z);}

```

Takes code (`LOAD R0`, etc), no trailing characters, single space, no blank lines in the middle, no comments, etc. Trailing newline required.

This is then converted to 80386 bytecode and executed.

Loading `0` into a register is replaced by `xor`ing the register with itself instead of `mov`ing `0` into the register, which is three bytes shorter in the generated bytecode, and may be very marginally faster.

Compile with:

```
gcc -m32 -D"g(a,b)=(N=192|b<<3|a)"-D"s(b)=(*(int*)(R+j)=b,j+=4)"-DN=R[j++]-D"G=((x+1)|4)"
-D"H=((y+1)|4)"-DS=9999-D"u=g(0,G)"-D"v=g(G,H)"-D"U(b,c)=s(0xA3##b##89),--j,s(&c);"
bytecode.c -o bytecode

```

POSIX-compliant OS required.

Input is read from STDIN (use `./bytecode < file` to pipe from a file).

Resulting bytecode for the test program:

```
; start
 0:   55                      push   %ebp
; LOAD R0 0
 1:   33 ed                   xor    %ebp,%ebp
; LOAD R2 0
 3:   33 ff                   xor    %edi,%edi
; LOAD R1 0
 5:   33 f6                   xor    %esi,%esi
; PUSH $1
 7:   56                      push   %esi
; MUL R1 R2
 8:   89 f0                   mov    %esi,%eax
 a:   f7 e7                   mul    %edi
 c:   8b f0                   mov    %eax,%esi
; PUSH R2
 e:   57                      push   %edi
; LOAD R2 3
 f:   bf 03 00 00 00          mov    $0x3,%edi
; DIV R1 R2
14:   89 f0                   mov    %esi,%eax
16:   f7 f7                   div    %edi
18:   8b f0                   mov    %eax,%esi
; POP R2
1a:   5f                      pop    %edi
; ADD R0 R1
1b:   01 f5                   add    %esi,%ebp
; POP R1
1d:   5e                      pop    %esi
; PUSH R2
1e:   57                      push   %edi
; LOAD R2 1
1f:   bf 01 00 00 00          mov    $0x1,%edi
; ADD R1 R2
24:   01 fe                   add    %edi,%esi
; POP R2
26:   5f                      pop    %edi
; PUSH R2
27:   57                      push   %edi
; LOAD R2 10000
28:   bf 10 27 00 00          mov    $0x2710,%ed
; CMP R1 R2
2d:   39 fe                   cmp    %edi,%esi
2f:   9f                      lahf
30:   8a fc                   mov    %ah,%bh
; POP R2
32:   5f                      pop    %edi
; BRANCHLT 3
33:   8a e7                   mov    %bh,%ah
35:   9e                      sahf
36:   0f 8c cb ff ff ff       jl     0x7
; LOAD R1 1
3c:   be 01 00 00 00          mov    $0x1,%esi
; ADD R2 R1
41:   01 f7                   add    %esi,%edi
; LOAD R1 10000
43:   be 10 27 00 00          mov    $0x2710,%es
; CMP R2 R1
48:   39 f7                   cmp    %esi,%edi
4a:   9f                      lahf
4b:   8a fc                   mov    %ah,%bh
; LOAD R1 0
4d:   33 f6                   xor    %esi,%esi
; BRANCHLT 2
4f:   8a e7                   mov    %bh,%ah
51:   9e                      sahf
52:   0f 8c ad ff ff ff       jl     0x5
; copy R0 to X
58:   89 e8                   mov    %ebp,%eax
5a:   a3 28 5b 42 00          mov    %eax,0x425b
; copy R1 to Y
5f:   89 f0                   mov    %esi,%eax
61:   a3 38 55 44 00          mov    %eax,0x4455
; copy R2 to Z
66:   89 f8                   mov    %edi,%eax
68:   a3 40 55 44 00          mov    %eax,0x4455
; exit
6d:   5d                      pop    %ebp
6e:   c3                      ret

```

Ungolfed:

```
C[9999],J[9999],i,j,k,y,c,X,Y,Z;
char *R,a,b[9];
main(x){
    // 6 is PROC_WRITE|PROC_EXEC
    // 34 is MAP_ANON|MAP_PRIVATE
    R=mmap(0,'~~',6,34,-1,0);

    N=0x55;
    while(scanf("%c%s%*[ R]%d%*[ R]%d",&a,b,&x,&y)&&~getchar())
        a-=65,
        a-1? // B[RANCH**]
            a-15? // P[USH/OP]
                a-9? // J[MP]
                    a? // A[DD]
                        a-2? // C[MP]
                            a-3? // D[IV]
                                a-11? // L[OAD]
                                    a-12? // M[UL]
                                        a-17? // R[LOAD]
                                            // SUB
                                            (N=0x29,g(G,H))
                                        :(N=0x89,g(G,H))
                                    :(N=0x89,g(0,G),N=0xF7,g(H,4),N=0x8B,g(0,G))
                                :(y?N=0xBD+x,s(y):(N=0x33,g(G,G)))
                            :(N=0x89,g(0,G),N=0xF7,g(H,6),N=0x8B,g(0,G))
                        :(N=0x39,g(G,H),s(0xfc8a9f),--j)
                    :(N=0x1,g(G,H))
                :(N=0xE9,J[k++]=i,s(x))
            :b[1]-80?
                N=0x55+x // PUSH
            :(N=0x5D+x) // POP
        :(c=b[5],s(0x0f9ee78a),N=(
        c-69? // EQ
            c-71? // GT
                c-76? // LT
                    1 // NE
                :8
            :11
        :0
        )+0x84,J[k++]=i,s(x)),
        C[++i]=j
        ;
    // transfer registers to X,Y,Z
    s(0xA3E889),--j,s(&X);
    s(0xA3F089),--j,s(&Y);
    s(0xA3F889),--j,s(&Z);

    // pop and ret
    s(0xC35D);

    i=j;
    // fix distances for jmp/branch**
    while(k--)
        j=C[J[k]]+1,R[j-1]-0xE9&&(j+=4),
        s(C[*(int*)(R+j)]-j-4);

    // call
    ((int(*)())R)();

    // output
    printf("%u %u %u\n",X,Y,Z);
}

```

# Answer
> 8 votes
## C, Score = 854byte × (~0.8sec / 2) × 0.5 \[JIT\] × 0.9 \[Extensions\] = ~154byte sec

```
#define G getchar()
#define L for(i=0;i<3;++i)
#define N*(int*)
#define M(x)"P\x8a\xe7\x9e\xf"#x"    KL"
*T[1<<20],**t=T,*F[1<<20],**f=F,R[3],r[]={1,6,7};char*I[]={"L\xb8    GGJH","I\x8b\xc0HHGH","H\x50GG","H\x58GG","I\3\xc0HHGH","I\53\xc0HHGH","M\x8b\xc0\xf7\xe0\x8b\xc0IHLGJ","O\63\xd2\x8b\xc0\xf7\xf0\x8b\xc0IJNGL","L\xe9    KH","L\73\xc0\x9f\x8a\xfcHHGH",M(\x82),M(\x84),M(\x87),M(\x85)},C[1<<24],*c=C;main(i,o,l,g){N c=0xb7ec8b60;c[4]=70;c+=5;while((o=G)>=0){char*s=I[o];l=*s-'G';memcpy(c,s+1,l);for(s+=l+1;o=*s++;){o-='G';if(o<3){g=r[G];c[*s++-'G']|=g<<3*(o&1);if(o>1)c[*s++-'G']|=g<<3;}else{if(o>3)*f++=c+*s-'G';for(i=4;i;--i)c[*s-'G'+i-1]=G;++s;}}*t++=c;c+=l;}*t=c;while(f>F)--f,**f=(int)T[**f]-(int)*f-4;L N&c[7*i]=0x5893e|r[i]<<19,N&c[3+7*i]=R+i;N&c[21]=0xc361e58b;mprotect((int)C>>12<<12,1<<24,7);((void(*)())C)();L printf("R%d %u\n",i,R[i]);}

```

Compile with `gcc vm.c -ovm -m32 -w` on a x86 POSIX compliant OS.
Run with `./vm < program`, where `program` is a binary program file.

---

Going for the speed. The program performs a pretty straight-forward translation of the input program to x86 machine code and lets the CPU do the rest.

For instance, here's the translation of the test program. `ecx`, `esi` and `edi` correspond to `R0`, `R1` and `R2`, respectively; `bh` holds the status flags; `eax` and `edx` are scratch registers; the call-stack corresponds to the VM's stack:

```
# Prologue
     0:   60                      pusha
     1:   8b ec                   mov    ebp,esp
     3:   b7 46                   mov    bh,0x46
# LOAD R0 0
     5:   b9 00 00 00 00          mov    ecx,0x0
# LOAD R2 0 <--outer loop value
     a:   bf 00 00 00 00          mov    edi,0x0
# LOAD R1 0 <--inner loop value
     f:   be 00 00 00 00          mov    esi,0x0
#      --Begin inner loop--
# PUSH R1 <--push inner loop value to the stack
    14:   56                      push   esi
# MUL R1 R2 <--(i*j)
    15:   8b c6                   mov    eax,esi
    15:   f7 e7                   mul    edi
    19:   8b f0                   mov    esi,eax
# PUSH R2
    1b:   57                      push   edi
# LOAD R2 3
    1c:   bf 03 00 00 00          mov    edi,0x3
# DIV R1 R2 <-- / 3
    21:   33 d2                   xor    edx,edx
    23:   8b c6                   mov    eax,esi
    25:   f7 f7                   div    edi
    27:   8b f0                   mov    esi,eax
# POP R2
    29:   5f                      pop    edi
# ADD R0 R1 <-- s+=
    2a:   03 ce                   add    ecx,esi
# POP R1
    2c:   5e                      pop    esi
# PUSH R2
    2d:   57                      push   edi
# LOAD R2 1
    2e:   bf 01 00 00 00          mov    edi,0x1
# ADD R1 R2 <--j++
    33:   03 f7                   add    esi,edi
# POP R2
    35:   5f                      pop    edi
# PUSH R2
    36:   57                      push   edi
# LOAD R2 10000
    37:   bf 10 27 00 00          mov    edi,0x2710
# CMP R1 R2 <-- j < 10000
    3c:   3b f7                   cmp    esi,edi
    3e:   9f                      lahf
    3f:   8a fc                   mov    bh,ah
# POP R2
    41:   5f                      pop    edi
# BRANCHLT 4 <--Go back to beginning inner loop
    42:   8a e7                   mov    ah,bh
    44:   9e                      sahf
    45:   0f 82 c9 ff ff ff       jb     0x14
# --Drop To outer loop--
# LOAD R1 1
    4b:   be 01 00 00 00          mov    esi,0x1
# ADD R2 R1 <--i++
    50:   03 fe                   add    edi,esi
# LOAD R1 10000
    52:   be 10 27 00 00          mov    esi,0x2710
# CMP R2 R1 <-- i < 10000
    57:   3b fe                   cmp    edi,esi
    59:   9f                      lahf
    5a:   8a fc                   mov    bh,ah
# LOAD R1 0 <--Reset inner loop
    5c:   be 00 00 00 00          mov    esi,0x0
# BRANCHLT 3
    61:   8a e7                   mov    ah,bh
    63:   9e                      sahf
    64:   0f 82 a5 ff ff ff       jb     0xf
# Epilogue
    6a:   3e 89 0d 60 ac 04 09    mov    DWORD PTR ds:0x904ac60,ecx
    71:   3e 89 35 64 ac 04 09    mov    DWORD PTR ds:0x904ac64,esi
    78:   3e 89 3d 68 ac 04 09    mov    DWORD PTR ds:0x904ac68,edi
    7f:   8b e5                   mov    esp,ebp
    81:   61                      popa
    82:   c3                      ret

```

---

**Ungolfed**

```
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>

#define MAX_INST_COUNT (1 << 20)
#define MAX_CODE_SIZE (8 * MAX_INST_COUNT)
#define PAGE_SIZE (1 << 12)

uintptr_t *targets[MAX_INST_COUNT], **targets_ptr = targets;
int32_t *fixups[MAX_INST_COUNT], **fixups_ptr = fixups;
char code[MAX_CODE_SIZE], *code_ptr = code;
uint32_t R[3];

const char* inst_defs[] = {
    /* LOAD     */ "\5\xb8    \1\0\4\1",
    /* RLOAD    */ "\2\x8b\xc0\2\1\1\1",
    /* PUSH     */ "\1\x50\1\0",
    /* POP      */ "\1\x58\1\0",
    /* ADD      */ "\2\x03\xc0\2\1\1\1",
    /* SUB      */ "\2\x2b\xc0\2\1\1\1",
    /* MUL      */ "\6\x8b\xc0\xf7\xe0\x8b\xc0\3\1\5\1\3",
    /* DIV      */ "\x8\x33\xd2\x8b\xc0\xf7\xf0\x8b\xc0\3\3\7\1\5",
    /* JMP      */ "\5\xe9    \5\1",
    /* CMP      */ "\5\x3b\xc0\x9f\x8a\xfc\2\1\1\1",
    /* BRANCHLT */ "\x9\x8a\xe7\x9e\x0f\x82    \5\5",
    /* BRANCHEQ */ "\x9\x8a\xe7\x9e\x0f\x84    \5\5",
    /* BRANCHGT */ "\x9\x8a\xe7\x9e\x0f\x87    \5\5",
    /* BRANCHNE */ "\x9\x8a\xe7\x9e\x0f\x85    \5\5"
};

int main() {
    int i;

    {
        const char prologue[] =
            /* PUSHAD       */ "\x60"
            /* MOV EBP, ESP */ "\x8b\xec"
            /* MOV BH, 46h  */ "\xb7\x46"
        ;
        memcpy(code_ptr, prologue, sizeof(prologue) - 1);
        code_ptr += sizeof(prologue) - 1;
    }

    {
        const char reg[] = {1, 6, 7};
        char r;
        int op;
        while ((op = getchar()) != EOF) {
            const char* def = inst_defs[op];
            int len = def[0];
            memcpy(code_ptr, def + 1, len);
            for (def += len + 1; *def; ) {
                switch (*def++) {
                    case 1: code_ptr[*def++] |= reg[getchar()]; break;
                    case 2: code_ptr[*def++] |= reg[getchar()] << 3; break;
                    case 3:
                        r = reg[getchar()];
                        code_ptr[*def++] |= r; code_ptr[*def++] |= r << 3;
                        break;
                    case 5: *fixups_ptr = code_ptr + *def; ++fixups_ptr;
                    case 4:
                        for (i = 4; i; --i) code_ptr[*def + i - 1] = getchar();
                        ++def;
                        break;
                }
            }
            *targets_ptr = code_ptr; ++targets_ptr;
            code_ptr += len;
        }
        *targets_ptr = code_ptr; ++targets_ptr;

        while (fixups_ptr != fixups) {
            --fixups_ptr;
            **fixups_ptr = (char*)targets[**fixups_ptr] - (char*)*fixups_ptr - 4;
        }
    }

    {
        const char epilogue[] =
            /* MOV R[0], ECX */ "\x3e\x89\x0d    "
            /* MOV R[1], ESI */ "\x3e\x89\x35    "
            /* MOV R[2], EDI */ "\x3e\x89\x3d    "
            /* MOV ESP, EBP  */ "\x8b\xe5"
            /* POPAD         */ "\x61"
            /* RET           */ "\xc3"
        ;
        memcpy(code_ptr, epilogue, sizeof(epilogue) - 1);
        for (i = 0; i < 3; ++i) *(uintptr_t*)&code_ptr[3 + 7 * i] = &R[i];
        code_ptr += sizeof(epilogue) - 1;
    }

    mprotect(
        (uintptr_t)code / PAGE_SIZE * PAGE_SIZE, MAX_CODE_SIZE,
        PROT_READ | PROT_WRITE | PROT_EXEC
    );
    { void (*program)(void) = code; program(); }
    for (i = 0; i < 3; ++i) printf("R%d %u\n", i, R[i]);

    return 0;
}
```

# Answer
> 2 votes
# CJam, ~~222~~ ~~187~~ 185 bytes * (too slow / 2)

I just wanted to see how short I can get a bytecode VM by writing it in CJam. Less than 200 bytes seems pretty decent. It's damn slow though, because CJam itself is interpreted. It takes ages to run the test program.

```
304402480 6b:P;q:iD-);{(_P=@/(\L*@@+\}h;]:P;TTT]:R;{_Rf=~}:Q;{4G#%R@0=@t:R;}:O;{TP=("R\(\GG*bt:R;  ~R= R\~@t:R; Q+O Q4G#+-O Q*O Q/O ~(:T; Rf=~-:U; GG*bU0<{(:T}*;"S/=~T):TP,<}g3,{'R\_S\R=N}/

```

To run it, download the Java interpreter at this sourceforge link, save the code in `vm.cjam` and run it with

```
java -jar cjam-0.6.2.jar vm.cjam

```

The program expects the bytecode on STDIN. I haven't found a way yet to pipe binary data into a program, without PowerShell adding a trailing line break and converting `0x0a` to `0x0d 0x0a`, which is really annoying. The code includes 4 bytes to fix that (`D-);`), which I haven't included in the total count, because it's not something the program should need to do if it actually received the bytecode itself on STDIN, instead of some weirdly encoded version of it. If someone knows a fix for that, please let me know.

Slightly ungolfed:

```
304402480 6b:P; "Create lookup table for instruction sizes. Store in P.";
q:i             "Read program and convert bytes to integers.";
D-);            "Remove spurious carriage returns. This shouldn't be necessary.";
{(_P=@/(\L*@@+\}h;]:P; "Split into instructions. Store in P.";
"We'll use T for the instruction pointer as it's initialised to 0.";
"Likewise, we'll use U for the CMP flag.";
TTT]:R; "Store [0 0 0] in R for the registers.";
{_Rf=~}:Q; "Register lookup block.";
{4G#%R@0=@t:R;}:O; "Save in register block.";
{TP=("R\(\GG*bt:R;

~R=
R\~@t:R;
Q+O
Q4G#+-O
Q*O
Q/O
~(:T;
Rf=~-:U;
GG*bU0<{(:T}*;"N/=~T):TP,<}g "Run program.";
3,{'R\_S\R=N}/

```

I'll add a proper explanation tomorrow.

In short, I'm storing all the registers, the instruction pointer and the comparison flag in variables, so that I can keep CJam's stack free to use as the VM's stack.

# Answer
> 1 votes
## python/c++, score=56.66

1435 chars * .234/2 seconds * .5 \[JIT\] * .75 \[Optimization\] * .90 \[Extra instructions\]

Compiles the input program to c++, runs gcc on it, then runs the result. Most of the time is spent inside gcc.

The one optimization I do is reduce the stack operations to explicit variables if it is allowed semantically. It helps a lot, about 10x better runtime of the compiled code (about .056 sec to actually run the resulting binary). I'm not sure what gcc is doing that gets you that improvement, but it's good.

```
import sys,os
x=map(ord,sys.stdin.read())
w=lambda x:(x[0]<<24)+(x[1]<<16)+(x[2]<<8)+x[3]
I=[]
while x:
 if x[0]==0:f='r%d=%d'%(x[1],w(x[2:]));n=6
 if x[0]==1:f='r%d=r%d'%(x[1],x[2]);n=3
 if x[0]==2:f='P%d'%x[1];n=2
 if x[0]==3:f='O%d'%x[1];n=2
 if x[0]==4:f='r%d=r%d+r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==5:f='r%d=r%d-r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==6:f='r%d=r%d*r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==7:f='r%d=r%d/r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==8:f='goto L%d'%w(x[1:]);n=5
 if x[0]==9:f='a=r%d;b=r%d'%(x[1],x[2]);n=3
 if x[0]==10:f='if(a<b)goto L%d'%w(x[1:]);n=5
 if x[0]==11:f='if(a==b)goto L%d'%w(x[1:]);n=5
 if x[0]==12:f='if(a>b)goto L%d'%w(x[1:]);n=5
 if x[0]==13:f='if(a!=b)goto L%d'%w(x[1:]);n=5
 I+=[f];x=x[n:]
D=[]
d=0
for f in I:D+=[d];d+='P'==f[0];d-='O'==f[0]
J=[]
if all(d==D[int(f[f.find('L')+1:])]for f,d in zip(I,D)if f[0]in'gi'):
 H='uint32_t '+','.join('s%d'%i for i in range(max(D)))+';'
 for f,d in zip(I,D):
  if f[0]=='P':f='s%d=r'%d+f[1:]
  if f[0]=='O':f='r'+f[1:]+'=s%d'%(d-1)
  J+=[f]
else:
 H='std::vector<uint32_t>s;'
 for f,d in zip(I,D):
  if f[0]=='P':f='s.push_back(r'+f[1:]+')'
  if f[0]=='O':f='r'+f[1:]+'=s.back();s.pop_back()'
  J+=[f]
P='#include<vector>\n#include<cstdint>\nuint32_t r0,r1,r2,a,b;'+H+'int main(){'
for i,f in enumerate(J):P+='L%d:'%i+f+';'
P+=r'printf("R0 %u\nR1 %u\nR2 %u\n",r0,r1,r2);}'
c=open("t.cc", "w")
c.write(P)
c.close()
os.system("g++ -O1 t.cc")
os.system("./a.out")

```

Could certainly be golfed some more.

# Answer
> 1 votes
# Lua 5.2 (or LuaJIT), 740 bytes

First try, only minimally golfed. This version works (at least on the test program), and implements the extra opcodes, but doesn't uphold the unsigned math requirement and isn't particularly fast. As a bonus, though, it's a VM running in a VM, and is written such that it can be either interpreted (run with PUC-Lua) or sort-of-JIT (run with LuaJIT; still interpreted, but the interpreter is now JITted).

**EDIT:** Golfed better, still big.

**EDIT:** Fixed a major error, and now restricts arithmetic to `unsigned long` range. Somehow managed to keep the size from getting out of hand, though, but it's still giving the wrong answer.

**EDIT:** Turns out, the result was correct but the output wasn't. Switched to printing with `%u` instead of `%d` and all is well. Also switched out table-based registers for variables to improve the size *and* speed somewhat.

**EDIT:** Using Lua 5.2's `goto` statement (also available in LuaJIT) I've replaced the interpreter with "JIT-to-Lua," generating code which is run directly by the Lua VM itself. Not sure if this really counts as JIT, but it does improve the speed.

```
U,S,P,F=table.unpack,table.insert,table.remove,math.floor X,r0,r1,r2,p,m,s=2^32,0,0,0,1,0,{}C={{'r%u=%u',1,4},{'r%u=r%u',1,1},{'S(s,r%u)',1},{'r%u=P(s)',1},{'r%u=(r%u+r%u)%%X',1,0,1},{'r%u=(r%u-r%u)%%X',1,0,1},{'r%u=(r%u*r%u)%%X',1,0,1},{'r%u=F(r%u/r%u)%%X',1,0,1},{'goto L%u',4},{'m=r%u-r%u',1,1},{'if m<0 then goto L%u end',4},{'if m==0 then goto L%u end',4},{'if m>0 then goto L%u end',4},{'if m~=0 then goto L%u end',4}}t={io.open(arg[1],'rb'):read('*a'):byte(1,-1)}i,n,r=1,0,{}while i<=#t do c,i,x,a=C[t[i]+1],i+1,0,{}for j=2,#c do y=c[j]if y>0 then x=0 for k=1,y do i,x=i+1,x*256+t[i]end end S(a,x)end S(r,('::L%d::'):format(n))n=n+1 S(r,c[1]:format(U(a)))end load(table.concat(r,' '))()print(('R0 %u\nR1 %u\nR2 %u'):format(r0,r1,r2))

```

Here's the original, readable version.

```
U,S,P,F=table.unpack,table.insert,table.remove,math.floor

X,r0,r1,r2,p,m,s=2^32,0,0,0,1,0,{}

C={
    {'r%u=%u',1,4},
    {'r%u=r%u',1,1},
    {'S(s,r%u)',1},
    {'r%u=P(s)',1},
    {'r%u=(r%u+r%u)%%X',1,0,1},
    {'r%u=(r%u-r%u)%%X',1,0,1},
    {'r%u=(r%u*r%u)%%X',1,0,1},
    {'r%u=F(r%u/r%u)%%X',1,0,1},
    {'goto L%u',4},
    {'m=r%u-r%u',1,1},
    {'if m<0 then goto L%u end',4},
    {'if m==0 then goto L%u end',4},
    {'if m>0 then goto L%u end',4},
    {'if m~=0 then goto L%u end',4},
}

t={io.open(arg[1],'rb'):read('*a'):byte(1,-1)}
i,n,r=1,0,{}
while i<=#t do
    c,i,x,a=C[t[i]+1],i+1,0,{}
    for j=2,#c do
        y=c[j]
        if y>0 then
            x=0
            for k=1,y do
                i,x=i+1,x*256+t[i]
            end
        end
        S(a,x)
    end
    S(r,('::L%d::'):format(n))
    n=n+1
    S(r,c[1]:format(U(a)))
end
load(table.concat(r,' '))()
print(('R0 %u\nR1 %u\nR2 %u'):format(r0,r1,r2))

```

# Answer
> 1 votes
## C#

1505 1475 bytes

This is my version of the interpreter, written in C# could be optimized / golfed more I think, but I don't really know where ;)

golfed version:

```
using System;using System.Collections.Generic;using System.IO;using System.Linq;class M{static void Main(string[]a){if(a.Length==1&&File.Exists(a[0])){B.E(B.P(File.ReadAllLines(a[0])));Console.WriteLine(B.O);}}}class B{public enum I{L=0x00,P=0x02,Q=0x03,A=0x04,S=0x05,M=0x06,D=0x07,J=0x08,C=0x09,BL=0x0a,BE=0x0b,BG=0x0c,BN=0x0d}public enum R{A,B,C}enum C{N,L,E,G}public static Dictionary<R,uint>r=new Dictionary<R,uint>{{R.A,0},{R.B,0},{R.C,0}};public static Stack<uint>s=new Stack<uint>();static C c=C.N;public static string O{get{return string.Format("R0 {0}\nR1 {1}\nR2 {2}",r[R.A],r[R.B],r[R.C]);}}public static void E(byte[][]l){for(uint i=0;i<l.Length;i++){var q=l[i];switch((I)q[0]){case I.L:r[(R)q[1]]=U(q,2);break;case I.P:r[(R)q[1]]=s.Pop();break;case I.Q:s.Push(r[(R)q[1]]);r[(R)q[1]]=0;break;case I.A:s.Push(r[(R)q[1]]+r[(R)q[2]]);break;case I.S:s.Push(r[(R)q[1]]-r[(R)q[2]]);break;case I.M:s.Push(r[(R)q[1]]*r[(R)q[2]]);break;case I.D:s.Push(r[(R)q[1]]/r[(R)q[2]]);break;case I.J:i=U(q,1)-1;break;case I.C:{uint x=r[(R)q[1]],y=r[(R)q[2]];c=x<y?C.L:x>y?C.G:C.E;}break;case I.BL:if(c==C.L)i=U(q,1)-1;break;case I.BG:if(c==C.G)i=U(q,1)-1;break;case I.BE:if(c==C.E)i=U(q,1)-1;break;case I.BN:if(c!=C.E)i=U(q,1)-1;break;}}}public static byte[][]P(string[]c){return c.Where(l=>!l.StartsWith("#")).Select(r=>r.Split(' ').Where(b=>b.Length>0).Select(b=>Convert.ToByte(b,16)).ToArray()).Where(l=>l.Length>0).ToArray();}static uint U(byte[]b,int i){return(uint)(b[i]<<24|b[i+1]<<16|b[i+2]<<8|b[i+3]);}}

```

### edit

removed some unnecessary `public` and `private` modifiers:

```
using System;using System.Collections.Generic;using System.IO;using System.Linq;class M{static void Main(string[]a){if(a.Length==1&&File.Exists(a[0])){B.E(B.P(File.ReadAllLines(a[0])));Console.Write(B.O);}}}class B{enum I{L=0x00,P=0x02,Q=0x03,A=0x04,S=0x05,M=0x06,D=0x07,J=0x08,C=0x09,BL=0x0a,BE=0x0b,BG=0x0c,BN=0x0d}enum R{A,B,C}enum C{N,L,E,G}static Dictionary<R,uint>r=new Dictionary<R,uint>{{R.A,0},{R.B,0},{R.C,0}};static Stack<uint>s=new Stack<uint>();static C c=C.N;public static string O{get{return string.Format("R0 {0}\nR1 {1}\nR2 {2}\n",r[R.A],r[R.B],r[R.C]);}}public static void E(byte[][]l){for(uint i=0;i<l.Length;i++){var q=l[i];switch((I)q[0]){case I.L:r[(R)q[1]]=U(q,2);break;case I.P:r[(R)q[1]]=s.Pop();break;case I.Q:s.Push(r[(R)q[1]]);r[(R)q[1]]=0;break;case I.A:s.Push(r[(R)q[1]]+r[(R)q[2]]);break;case I.S:s.Push(r[(R)q[1]]-r[(R)q[2]]);break;case I.M:s.Push(r[(R)q[1]]*r[(R)q[2]]);break;case I.D:s.Push(r[(R)q[1]]/r[(R)q[2]]);break;case I.J:i=U(q,1)-1;break;case I.C:{uint x=r[(R)q[1]],y=r[(R)q[2]];c=x<y?C.L:x>y?C.G:C.E;}break;case I.BL:if(c==C.L)i=U(q,1)-1;break;case I.BG:if(c==C.G)i=U(q,1)-1;break;case I.BE:if(c==C.E)i=U(q,1)-1;break;case I.BN:if(c!=C.E)i=U(q,1)-1;break;}}}public static byte[][]P(string[]c){return c.Where(l=>!l.StartsWith("#")).Select(r=>r.Split(' ').Where(b=>b.Length>0).Select(b=>Convert.ToByte(b,16)).ToArray()).Where(l=>l.Length>0).ToArray();}static uint U(byte[]b,int i){return(uint)(b[i]<<24|b[i+1]<<16|b[i+2]<<8|b[i+3]);}}

```

call it with `executable.exe filename` where `filename` is the file containing the code to be interpreted

My "test program":

```
# LOAD R0 5
# CMP R0 R1
# BRANCHEQ 13
# LOAD R1 1
# LOAD R2 1
# CMP R0 R2
# MUL R1 R2
# LOAD R1 1
# ADD R2 R1
# PUSH R2
# PUSH R1
# BRANCHEQ 13
# JMP 5
# POP R2
# POP R0
# POP R1
# PUSH R0

0x0 0x0 0x0 0x0 0x0 0x5
0x9 0x0 0x1
0xb 0x0 0x0 0x0 0xd
0x0 0x1 0x0 0x0 0x0 0x1
0x0 0x2 0x0 0x0 0x0 0x1
0x9 0x0 0x2
0x6 0x1 0x2
0x0 0x1 0x0 0x0 0x0 0x1
0x4 0x2 0x1
0x2 0x2
0x2 0x1
0xb 0x0 0x0 0x0 0xd
0x8 0x0 0x0 0x0 0x5
0x3 0x2
0x3 0x0
0x3 0x1
0x2 0x0

```

Interpreter ungolfed with longer names variables, classes, ...

```
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        if (args.Length == 1 && File.Exists(args[0]))
        {
            var code = ByteCodeInterpreter.ParseCode(File.ReadAllLines(args[0]));
            ByteCodeInterpreter.Execute(code);
            Console.WriteLine(ByteCodeInterpreter.Output);
        }
    }
}

public static class ByteCodeInterpreter
{
    public enum Instruction : byte
    {
        LOAD = 0x00,
        PUSH = 0x02,
        POP = 0x03,
        ADD = 0x04,
        SUB = 0x05,
        MUL = 0x06,
        DIV = 0x07,
        JMP = 0x08,
        CMP = 0x09,
        BRANCHLT = 0x0a,
        BRANCHEQ = 0x0b,
        BRANCHGT = 0x0c,
        BRANCHNE = 0x0d
    }

    public enum Register : byte
    {
        R0 = 0x00,
        R1 = 0x01,
        R2 = 0x02
    }

    private enum CompareFlag : byte
    {
        NONE = 0x00,
        LT = 0x01,
        EQ = 0x02,
        GT = 0x03,
    }

    public static readonly Dictionary<Register, uint> register = new Dictionary<Register, uint>
    {
        {Register.R0, 0},
        {Register.R1, 0},
        {Register.R2, 0}
    };

    public static readonly Stack<uint> stack = new Stack<uint>();
    private static CompareFlag compareFlag = CompareFlag.NONE;

    public static string Output
    {
        get
        {
            return string.Format("R0 {0}\nR1 {1}\nR2 {2}", register[Register.R0], register[Register.R1],
                register[Register.R2]);
        }
    }

    public static void Execute(byte[][] lines)
    {
        for (uint i = 0; i < lines.Length; i++)
        {
            var line = lines[i];
            switch ((Instruction)line[0])
            {
                case Instruction.LOAD:
                    register[(Register)line[1]] = GetUint(line, 2);
                    break;
                case Instruction.PUSH:
                    register[(Register)line[1]] = stack.Pop();
                    break;
                case Instruction.POP:
                    stack.Push(register[(Register)line[1]]);
                    register[(Register)line[1]] = 0;
                    break;
                case Instruction.ADD:
                    stack.Push(register[(Register)line[1]] + register[(Register)line[2]]);
                    break;
                case Instruction.SUB:
                    stack.Push(register[(Register)line[1]] - register[(Register)line[2]]);
                    break;
                case Instruction.MUL:
                    stack.Push(register[(Register)line[1]] * register[(Register)line[2]]);
                    break;
                case Instruction.DIV:
                    stack.Push(register[(Register)line[1]] / register[(Register)line[2]]);
                    break;
                case Instruction.JMP:
                    i = GetUint(line, 1) - 1;
                    break;
                case Instruction.CMP:
                    {
                        uint v0 = register[(Register)line[1]], v1 = register[(Register)line[2]];
                        if (v0 < v1)
                            compareFlag = CompareFlag.LT;
                        else if (v0 > v1)
                            compareFlag = CompareFlag.GT;
                        else
                            compareFlag = CompareFlag.EQ;
                    }
                    break;
                case Instruction.BRANCHLT:
                    if (compareFlag == CompareFlag.LT)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHGT:
                    if (compareFlag == CompareFlag.GT)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHEQ:
                    if (compareFlag == CompareFlag.EQ)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHNE:
                    if (compareFlag != CompareFlag.EQ)
                        i = GetUint(line, 1) - 1;
                    break;
            }
        }
    }

    public static byte[][] ParseCode(string[] code)
    {
        return
            code.Where(line => !line.StartsWith("#"))
                .Select(line => line.Split(' ').Where(b => b.Length > 0).Select(b => Convert.ToByte(b, 16)).ToArray())
                .Where(line => line.Length > 0)
                .ToArray();
    }

    private static uint GetUint(byte[] bytes, int index)
    {
        return (uint)(bytes[index] << 24 | bytes[index + 1] << 16 | bytes[index + 2] << 8 | bytes[index + 3]);
    }
}

```

---
Tags: code-challenge, interpreter, stack
---


title: ASCII Odd/Even Cipher

text:
# Question
Title: ASCII Odd/Even Cipher
We'll define the **ASCII Odd/Even Cipher** via the below pseudocode:

```
Define 'neighbor' as the characters adjacent to the current letter in the string

If the one of the neighbors is out of bounds of the string, treat it as \0 or null

Take an input string

For each letter in the string, do
  If the 0-based index of the current letter is even, then
    Use the binary-or of the ASCII codes of both its neighbors
  Else
    If the ASCII code of the current letter is odd, then
      Use the binary-or of itself plus the left neighbor
    Else
      Use the binary-or of itself plus the right neighbor
  In all cases,
    Convert the result back to ASCII and return it
  If this would result in a code point 127 or greater to be converted, then
    Instead return a space

Join the results of the For loop back into one string and output it

```

For example, for input `Hello`, the output is `emmol`, since

* The `H` turns to `\0 | 'e'` which is `e`
* The `e` turns to `'e' | 'l'`, or `101 | 108`, which is `109` or `m`
* The first `l` also turns to `101 | 108` or `m`
* The second `l` turns to `108 | 111`, which is `111` or `o`
* The `o` turns to `108 | \0`, or `l`

### Input

* A sentence composed solely of printable ASCII characters, in any suitable format.
* The sentence may have periods, spaces, and other punctuation, but will only ever be one line.
* The sentence will be at least three characters in length.

### Output

* The resulting cipher, based on the rules described above, returned as a string or output.

### The Rules

* Either a full program or a function are acceptable.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

### Examples

Input on one line, output on the following. Blank lines separate examples.

```
Hello
emmol

Hello, World!
emmol, ww~ved

PPCG
PSWG

Programming Puzzles and Code Golf
r wogsmmoonpuu ~ meannncoooeggonl

abcdefghijklmnopqrstuvwxyz
bcfefgnijknmno~qrsvuvw~yzz

!abcdefghijklmnopqrstuvwxyz
aaccgeggoikkomoo qsswuww yy

Test 123 with odd characters. R@*SKA0z8d862
euutu133www|todddchizsscguwssr`jS{SK{z~|v66

```

# Answer
> 1 votes
# Jelly, ~~33~~ 31 bytes

```
2ịḂị|2\
|ṚḢ,Ç
O0,0jṡ3µÇ€⁸JḂ¤ị"Ọ

```

A straight-forward approach that can surely be made shorter.

Try it online!

# Answer
> 4 votes
# Perl, ~~63~~ 62 bytes

Includes +4 for `-lp`

Give input on STDIN

`oddeven.pl`:

```
#!/usr/bin/perl -lp
s%.%(--$|?$n|$':$&|(ord$&&1?$n:$'))&($n=$&,~v0)%eg;y;\x7f-\xff; ;

```

This works as shown, but to get the claimed score this must be put in a file ***without*** final `;` and newline and the `\xhh` escapes must be replaced by their literal values. You can do this by putting the code above in the file and running:

```
perl -0pi -e 's/\\x(..)/chr hex $1/eg;s/;\n$//' oddeven.pl

```

# Answer
> 3 votes
# Python 2, ~~138~~ 131 bytes

```
s="\0%s\0"%input();r=''
for i in range(len(s)-2):L,M,R=map(ord,s[i:i+3]);a=i%2and[R,L][M%2]|M or L|R;r+=chr(a*(a<127)or 32)
print r

```

**Try it online** (contains all test cases)

Less golfed:

```
def f(s):
    s="\0%s\0"%s
    r=''
    for i in range(1,len(s)-1):
        if i%2: # even (parity is changed by adding \x00 to the front)
            a=ord(s[i-1]) | ord(s[i+1])
        else:   # odd
            a=ord(s[i])
            if a%2: # odd
                a|=ord(s[i-1])
            else:   # even
                a|=ord(s[i+1])
        r+=chr(a if a<127 else 32)
    print r

```

**Try it online** (ungolfed)

I add `\x00` to both sides of the string so that I don't have to worry about that during bitwise or-ing. I loop along the string's original characters, doing bitwise operations and adding them to the result, following the rules for parity.

# Answer
> 2 votes
# Mathematica, 152 bytes

```
FromCharacterCode[BitOr@@Which[OddQ@Max@#2,#~Drop~{2},OddQ@#[[2]],Most@#,True,Rest@#]/._?(#>126&)->32&~MapIndexed~Partition[ToCharacterCode@#,3,1,2,0]]&

```

# Explanation

```
ToCharacterCode@#

```

Converts string to ASCII codes

```
Partition[...,3,1,2,0]

```

Partitions the ASCII codes to length 3, offset 1 partitions, with padded 0s.

```
...~MapIndexed~...

```

Applys a function for each partition.

```
Which[...]

```

`If...else if... else` in *Mathematica*.

```
OddQ@Max@#2

```

Checks whether the index (#2) is odd. (`Max` is for flattening); since *Mathematica* index starts at 1, I used `OddQ` here, not `EvenQ`

```
Drop[#,{2}]

```

Takes the ASCII codes of the left and right neighbors.

```
OddQ@#[[2]]

```

Checks whether the ASCII code of the corresponding character is odd.

```
Most@#

```

Takes the ASCII codes of the character and the left neighbor.

```
Rest@#

```

Takes the ASCII codes of the character and the right neighbor.

```
BitOr

```

Applys or-operation.

```
/._?(#>126&)->32

```

Replaces all numbers greater than 126 with 32 (space).

```
FromCharacterCode

```

Converts ASCII code back to characters and join them.

# Answer
> 2 votes
# Ruby ~~133~~ ~~128~~ ~~108~~ 106 bytes

Jordan helped me save 20 bytes and cia\_rana helped me save 2 bytes :)

```
->s{p s[-i=-1]+s.bytes.each_cons(3).map{|x,y,z|i+=1;a=i%2>0?x|z :y%2>0?y|x :y|z;a>126?' ':a.chr}*""+s[-2]}

```

`s` is taken as the input string.

Example output with `s="Test 123 with odd characters. R@*SKA0z8d862"`:

```
"euutu133www|todddchizsscguwssr`jS{SK{z~|v66"

```

---

**Explanation**

The above code is very unreadable so here is an explanation. The code is kind of hacky, I'm quit new to ruby so I bet there is a shorter way to do this :)

```
b=s[1] # for the first character we always use the right neighbour
       # because `\0 | x` will always return x any way. 0 is the
       # left neighbour and x is the right neigbour
s.bytes.each_cons(3).with_index{|c,i| # oh boy, first we convert the string to ascii with each_byte
                                          # we then traverse the resulting array with three elements at
                                          # a time (so for example if s equals "Hello", c will be equal
                                          # to [72, 101, 108])
  if (i+1) % 2 < 1 # if the middle letter (which is considered our current letter) is even
    a = c[0] | c[2] # we use the result of binary-or of its neighbours
  else
    if c[1] % 2 > 0 # if the code of the current letter is odd
      a = c[1] | c[0] # we use the result of binary-or of itself and its left neighbour
    else
      a = c[1] | c[2] # we use the result of binary-or of itself and its right neighbour
    end
  end
  if a>126
    b<<' ' # if the result we use is greater or equal to 127 we use a space
  else
    b<<a.chr # convert the a ascii value back to a character
  end
}
p b+s[-2] # same as the first comment but now we know that x | \0 will always be x
          # this time x is the last characters left neighbour

```

# Answer
> 2 votes
# C - 101 bytes

```
i,k;f(char*p){for(i=0;*p;++p,++i)putchar((k=i&1?*p&1?*p|p[-1]:*p|p[1]:i?p[-1]|p[1]:p[1])<127?k:' ');}

```

We don't even have to check if it's the last item in the string because strings in C are null-terminated.

# Explanation

Rather simple:

Use &1 to test for odd/evenness and ternary expressions to replace if/elses. Increment the char \*p to reduce the number of brackets required.

# Answer
> 1 votes
# J, 42 bytes

```
4:u:3({.OR{:)`((2|1&{){2:OR/\|.)\0,~0,3&u:

```

Uses the property that verbs in J can be applied in an alternating fashion using a gerund ``` for certain adverbs such as infix `\`.

## Usage

```
   f =: 4:u:3({.OR{:)`((2|1&{){2:OR/\|.)\0,~0,3&u:
   f 'Hello'
emmol
   f 'Hello, World!'
emmol,ww~ved
   f 'PPCG'
PSWG
   f 'Programming Puzzles and Code Golf'
rwogsmmoonpuu~meannncoooeggonl
   f 'abcdefghijklmnopqrstuvwxyz'
bcfefgnijknmno~qrsvuvw~yzz
   f '!abcdefghijklmnopqrstuvwxyz'
aaccgeggoikkomooqsswuwwyy
   f 'Test 123 with odd characters. R@*SKA0z8d862'
euutu133www|todddchizsscguwssr`jS{SK{z~|v66

```

## Explanation

```
4:u:3({.OR{:)`((2|1&{){2:OR/\|.)\0,~0,3&u:  Input: string S
                                      3&u:  Convert each char to an ordinal
                                    0,      Prepend 0
                                 0,~        Append 0
    3                           \           For each slice of size 3
     (      )`                                For the first slice (even-index)
          {:                                    Get the tail
      {.                                        Get the head
        OR                                      Bitwise OR the head and tail
             `(                )              For the second slice (odd-index)
                             |.                 Reverse the slice
                       2:   \                   For each pair
                         OR/                      Reduce using bitwise OR
                  1&{                           Get the middle value of the slice
                2|                              Take it modulo 2
                      {                         Index into the bitwise OR pairs and select
                                              Repeat cyclically for the remaining slices
4:u:                                        Convert each ordinal back to a char and return

```

# Answer
> 1 votes
## JavaScript (ES6), ~~125~~ ~~118~~ 114 bytes

Embarrassingly long, but `charCodeAt` and `String.fromCharCode` alone are 29 bytes. :-/

```
s=>[...s].map((_,i)=>String.fromCharCode((x=(C=i=>s.charCodeAt(i))((i-1)|1)|C(i+1-2*(C(i)&i&1)))>126?32:x)).join``

```

### How it works

Each character at position `i` is translated with the following formula, which covers all rules at once:

```
C((i - 1) | 1) | C(i + 1 - 2 * (C(i) & i & 1))

```

where `C(n)` returns the ASCII code of the n-th character of the input string.

### Demo

```
let f =

s=>[...s].map((_,i)=>String.fromCharCode((x=(C=i=>s.charCodeAt(i))((i-1)|1)|C(i+1-2*(C(i)&i&1)))>126?32:x)).join``

console.log(f("Hello"));
console.log(f("Hello, World!"));
console.log(f("PPCG"));
console.log(f("Programming Puzzles and Code Golf"));
console.log(f("abcdefghijklmnopqrstuvwxyz"));
console.log(f("!abcdefghijklmnopqrstuvwxyz"));
console.log(f("Test 123 with odd characters. R@*SKA0z8d862"));
```

# Answer
> 1 votes
# PHP, ~~107~~ 97 bytes

probably golfable.

```
for(;$i<strlen($s=$argv[1]);$i++)echo chr(ord($s[$i-1+$i%2])|ord($s[$i+1-2*($i&ord($s[$i])&1)]));

```

# Answer
> 1 votes
# C#, 145 bytes

```
s=>{var r=s[1]+"";int i=1,l=s.Length,c;for(;i<l;i++){c=i>l-2?0:s[i+1];c=i%2<1?s[i-1]|c:s[i]|(s[i]%2>0?s[i-1]:c);r+=c>'~'?' ':(char)c;}return r;};

```

Full program with ungolfed method and test cases:

```
using System;

namespace ASCIIOddEvenCipher
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<string,string>f= s=>
            {
                var r = s[1] + "";
                int i = 1, l = s.Length, c;
                for(;i < l; i++)
                {
                    c = i>l-2 ? 0 : s[i+1];
                    c = i%2<1 ? s[i-1]|c : s[i]|(s[i]%2>0 ? s[i-1] : c);
                    r += c > '~' ? ' ' : (char)c;
                }
                return r;
            };

            //test cases:
            Console.WriteLine(f("Hello"));  //emmol
            Console.WriteLine(f("Hello, World!"));  //emmol, ww~ved
            Console.WriteLine(f("PPCG"));   //PSWG
            Console.WriteLine(f("Programming Puzzles and Code Golf"));  //r wogsmmoonpuu ~ meannncoooeggonl
            Console.WriteLine(f("abcdefghijklmnopqrstuvwxyz")); //bcfefgnijknmno~qrsvuvw~yzz
            Console.WriteLine(f("!abcdefghijklmnopqrstuvwxyz"));    //aaccgeggoikkomoo qsswuww yy
            Console.WriteLine(f("Test 123 with odd characters. R@*SKA0z8d862"));    //euutu133www|todddchizsscguwssr`jS{SK{z~|v66
        }
    }
}

```

This turned out to be longer than I thought...

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


# Question
Title: Generate a 6 character string from a 15 character alphabet
In one of our projects at work, we recently discovered a particularly large method for generating a 6 character string from a 15 character alphabet. A few of us claimed "I bet we can get that in one line" which started a little internal game of code golf.

Your task is to beat us, which I have no doubt won't take long!

The original algorithm used the alphabet 0-9A-E, but we've experimented with other alphabets. There are therefore three subtasks.

1. Generate a `6` character string randomly selecting from an arbitrary hardcoded `15` character alphabet like `ABC123!@TPOI098`. (This is just an example, and should be customizable without affecting the byte count.)
2. Generate a `6` character string randomly selecting from a `15` character alphabet `0123456789ABCDE`.
3. Generate a `6` character string randomly selecting from a `15` character alphabet of your choice (printable characters only please).

Each character should have **equal chance** of selection and **repetition** should be possible.

The best we have been able to manage for each of the subtasks is:

* "ABC123!@TPOI098" - `24 bytes`
* "0123456789ABCDE" - `21 bytes`
* Custom alphabet - `13 bytes`

Your score is the sum of the bytes in each subtask's solution. i.e. our score is currently 58.

We've attempted using among others, CJam and Ruby. The original was in C#. Use any language you like, but we'll be interested to see solutions in these languages particularly

# Answer
# Jelly, 38 bytes

TryItOnline links **A**, **B**, and **C**.

: `ABC123!@£POI098`, 22 bytes

```
“ABC123!@£POI098”Wẋ6X€

```

(thinking about a compression to lessen this one)

: `0123456789ABCDE`, 8 bytes:

```
ØHṖWẋ6X€

```

:`123456789ABCDEF` (choice), 8 bytes:

```
ØHḊWẋ6X€

```

### How?

```
...Wẋ6X€ - common theme
   W     - wrap (string) in a list
    ẋ6   - repeat six times
      X€ - random choice from €ach

ØH...... - hexadecimal digit yield: "0123456789ABCDEF"

..Ṗ..... - pop: z[:-1] (B)

..Ḋ..... - dequeue: z[1:] (C)

```
> 6 votes

# Answer
## CJam (23 + 14 + 10 = 47 bytes)

Arbitrary alphabet: 23 bytes (online demo)

```
{"ABC123!@TPOI098"mR}6*

```

Hexadecimal alphabet: 14 bytes (online demo)

```
{FmrAbHb'0+}6*

```

Custom alphabet: `ABCDEFGHIJKLMNO`, 10 bytes (online demo)

```
{Fmr'A+}6*

```

### Dissection

The hexadecimal one is the interesting one:

```
{      e# Loop...
  Fmr  e#   Select a random number from 0 to 14
  AbHb e#   Convert to base 10 and then to base 17
       e#   (i.e. add 7 if the number is greater than 9)
  '0+  e#   Add character '0' (i.e. add 48 and convert from integer to character)
       e#   Note that 'A' - '0' = 17
}6*    e# ...six times

```

The six characters are left on the stack and printed automatically.
> 8 votes

# Answer
## Perl, 46 + 26 + 26 = 98 bytes

*A lot of the credit goes to @Dom Hastings for saving 13 bytes!*

The 3 programs are pretty much identical, except for the alphabet that changes.

* Hardcoded alphabet (`ABC123!@)POI098` in this example) -\> 46 bytes:

`say map{substr"ABC123!@)POI098",15*rand,1}1..6`
* Fixed alphabet `0123456789ABCDE` -\> 26 bytes:

`printf"%X",rand 15for 1..6`
* Custom alphabet `0123456789ABCDE` in that case -\> 26 bytes:

`printf"%X",rand 15for 1..6`

You can put them all in a file to run them :

```
$ cat 6chr_strings.pl
say map{substr"ABC123!@)POI098",15*rand,1}1..6;
say "";
printf"%X",rand 15for 1..6;
say "";
printf"%X",rand 15for 1..6;
say "";
$ perl -M5.010 6chr_string.pl
CB8!8!
24D582
9ED58C

```

(the `say "";` are just here to improve the output format)
> 6 votes

# Answer
## JavaScript (ES6), ~~167~~ ~~166~~ ~~164~~ 163 bytes

*Saved 1 byte thanks to Neil*
*Saved 2 bytes thanks to ETHproductions*
*Saved 1 byte thanks to premek.v*

**Hardcoded:** `"ABC123!@TPOI098"` (58 bytes)

```
f=(n=6)=>n?"ABC123!@TPOI098"[Math.random()*15|0]+f(n-1):''

```

**Fixed:** `"0123456789ABCDE"` (~~58~~ 57 bytes)

```
f=(n=6)=>n?f(n-1)+("ABCDE"[n=Math.random()*15|0]||n-5):''

```

**Custom:** `"()+.1=>?M[afhnt"` (~~51~~ ~~49~~ 48 bytes)

```
f=(n=6)=>n?(f+1)[Math.random()*15|0+5]+f(n-1):''

```
> 4 votes

# Answer
# R, 33+43+59 = 135 bytes

Arbitrary hard-coded alphabet (change the string to change the alphabet):

```
cat(sample(strsplit("ABC123!@TPOI098","")[[1]],6,1),sep="")

```

Alphabet of `[0-9A-E]`:

```
cat(sample(c(0:9,LETTERS[1:6]),6,1),sep="")

```

User-defined alphabet from stdin:

```
cat(sample(scan(,''),6,1),sep="")

```

All cases print the output word to stdout.
> 4 votes

# Answer
## JavaScript (ES6), 184 bytes

Custom alphabet: 66 bytes

```
_=>"......".replace(/./g,c=>"ABC123!@TPOI098"[Math.random()*15|0])

```

0-9A-E: 63 bytes

```
_=>"......".replace(/./g,c=>"ABCDE"[n=Math.random()*15|0]||n-5)

```

0-9a-e: 55 bytes

```
_=>(Math.random()*11390625+1e8|0).toString(15).slice(1)

```

(Subtract 6 bytes if date-based randomness is permissible.)
> 3 votes

# Answer
# q, 42 bytes

**A**

19 bytes

```
6?"ABC123!@TPOI098"

```

**B**

14 bytes

```
6?15#.Q.n,.Q.A

```

**C**

9 bytes

```
6?15#.Q.a

```

(uses the first fifteen letters of the alphabet)
> 3 votes

# Answer
# Julia (36+26+21 = 83)

```
join(rand(["ABC123!@TPOI098"...],6))

base(15,rand(15^6:15^7-1))

join(rand('a':'o',6))

```
> 3 votes

# Answer
## CJam, 48 bytes

Arbitrary alphabet, 23 bytes:

```
{"ABC123!@TPOI098"mR}6*

```

Try it online!

Hex digits, 15 bytes:

```
{A,'F,65>+mR}6*

```

Try it online!

Alphabet `ABCDEFGHIJKLMNO`, 10 bytes:

```
{Fmr'A+}6*

```

Try it online!
> 2 votes

# Answer
**Ruby 47 + 37 + 31 = 115**

Hardcoded: "ABC123!@TPOI098" (47)

```
(1..6).map{"5CABC123!@TPOI098".chars.sample}*''

```

Fixed: "0123456789ABCDE" (37)

```
(1..6).map{[*0..9,*?A..?E].sample}*''

```

Custom: "ABCDEFGHIJKLMNO" (31)

```
(1..6).map{[*?A..?O].sample}*''

```
> 2 votes

# Answer
# 05AB1E, 43 bytes

Arbitratry alphabet (`ABC123!@TPOI098`), 23 bytes Try it online

```
"ABC123!@TPOI098"6F.r¬?

```

Almost hexadecimal alphabet (`0123456789ABCDE`), 10 bytes Try it online

```
14Ýh6F.r¬?

```

Custom alphabet (`abcdefghijklmno`), 10 bytes Try it online

```
A15£6F.r¬?

```
> 1 votes

# Answer
# Python 2, 70 + 70 + 64 = 204 bytes

```
from random import*
s=""
exec"s+=choice('ABC123!@TPOI098');"*6
print s

from random import*
s=""
exec"s+=choice('0123456789ABCDE');"*6
print s

from random import*
s=""
exec"s+=chr(randint(65,80));"*6
print s

```

Unfortunately, the second example is easier with the first method than something like `choice([randint(48,57)),choice(65,69)])`
> 1 votes

# Answer
# Vitsy, 27 + ~~24~~ 22 + ~~13~~ 10 = ~~64~~ ~~62~~ 59 bytes

#1:

```
"ABC123!@TPOI098"6\[eR2+@O]

```

Try it online!

#2:

```
aH7+D4+H6\[eR2+@68*+O]

```

Try it online!

#3:

```
6\[eR5F-O]

```

Where the available characters are:

```
ﾖﾕﾔﾓﾒﾑﾐﾏﾎﾍﾌﾋﾊﾉﾈ

```

Try it online!
> 1 votes

# Answer
# J, 24 + 24 + ~~18~~ 10 = 58 bytes

*8 bytes saved thanks to miles!*

```
'ABC123!@TPOI098'{~?6#15
'0123456789ABCDE'{~?6#15
u:65+?6#15

```

Yeah, the second string isn't easily compressible in J:

```
u:47+23#.inv 12670682677028904639x
u:47+;(+i.@])/"1&.>1 10;18 5
('ABCDE',~1":i.10)
(toupper,hfd?6#15)
'0123456789ABCDE'

```

If a lowercase hex alphabet is fine, then there's `,hfd?6#15` for 9 bytes, as @miles noted.

Anyhow, `?6#15` is 6 random numbers between 0 and 15; `{~` is take-from. `u:` converts numbers to chars. The last example encodes `ABCDEFGHIJKLMNOP`.

## Bonus: general case

```
{~6?@##

```

`{~6?@##` is roughly:

```
{~6?@##  input: y
      #  length of y
  6  #   six copies of the length
   ?@    random numbers between 0 and the length
{~       taken from y

```
> 1 votes

# Answer
# PHP, 46+36+35=117 bytes

### Hardcoded (46 bytes)

```
for(;$i++<6;)echo"ABC123!@TPOI098"[rand()%15];

```

~~(47 bytes)~~

~~```
for(;$i++<6;)echo"ABC123!@TPOI098"[rand(0,14)];

```~~

### Hexadecimal (lowercase) (36 bytes)

```
for(;$j++<6;)echo dechex(rand()%15);

```

For uppercase, 46 bytes with Hardcoded version.

### Custom (A-O) (35 bytes)

```
for(;$k++<6;)echo chr(rand(65,79));

```
> 1 votes

# Answer
# Scala, 154 bytes

Hardcoded alphabet (54 bytes):

```
Seq.fill(6)("ABC123!@TPOI098"((math.random*14).toInt))

```

Hex alphabet (54 bytes):

```
Seq.fill(6)("0123456789ABCDE"((math.random*14).toInt))

```

Custom alphabet `ABCDEFGHIJKLMNO` (47 bytes):

```
Seq.fill(6)(('A'to'O')((math.random*14).toInt))

```

Explanation:

```
Seq.fill(6)(               //build a sequence of 6 elements, where each element is...
  "ABC123!@TPOI098"(         //from the string
    (math.random*14).toInt   //take a random char
  )
)

```

`'A'to'O'` creates a sequence of 15 chars, A to O
> 0 votes

# Answer
## Pip, 42 bytes

Hardcoded alphabet, 22 bytes:

```
L6ORC"ABC123!@TPOI098"

```

Hex digits, 11 bytes:

```
L6ORR15TB16

```

First 15 lowercase letters, 9 bytes:

```
L6Oz@RR15

```

### Explanation

All three programs start with `L6O`: loop 6 times and output the given expression.

* `RC"..."`: Random Choice of a character from the hard-coded string
* `RR15TB16`: RandRange(15), converted To Base 16
* `z@RR15`: lowercase alphabet `z`, indexed with RandRange(15)

Try it online!
> 0 votes

# Answer
# Skript/skQuery, 108 bytes

Hardcoded (43 bytes):

```
random 6 char string from `A@cD%F3h9JK{mN!`

```

0123456789ABCDE (34 bytes):

```
random 6 char string from `0-9A-E`

```

Choice (31 bytes):

```
random 6 char string from `A-M`

```
> 0 votes

# Answer
# Jolf, 26 + 14 + 13 = 51 bytes

```
Μ*S6d rG"ABC123!@TPOI098"E

```

Custom alphabet, 24 bytes. Try it here!

```
Μ*S6d r lp^0wά

```

0-9A-E alphabet, 14 bytes. Try it here! `lp^0wά` is `lp` (0-Z) sliced (`l`) from `0` to `15` ().

```
Μ*S6d r lp^1ά

```

1-9A-F alphabet, 13 bytes. Try it here! `lp^1ά` is the same as above, except from `1` to `16`.

---

General method:

```
Μ*S6d r
M*S6d      map six newlines over this function:
      r    select random element from array.

```

Other attempts (using string compression):

```
Μ*S6d rGμpwΞ $AE

```
> 0 votes

# Answer
## PowerShell v2+, 45 + 44 + 37 = 126 bytes

Fixed alphabet, 45 bytes

```
-join(0..5|%{'ABC123!@TPOI098'[(Random)%15]})

```

Nearly-hexadecimal alphabet, 44 bytes

```
-join[char[]](0..5|%{Random(48..57+65..69)})

```

Custom alphabet (A to O), 37 bytes

```
-join[char[]](0..5|%{Random(65..79)})

```

All of these follow the same pattern -- loop from `0` to `5`, each iteration selecting a `Random` character or ASCII value, casting that as a `char`-array if necessary, and `-join`ing it together into a string. That string is left on the pipeline, and output is implicit.

---

### Examples

```
PS C:\Tools\Scripts\golfing> -join(0..5|%{'ABC123!@TPOI098'[(Random)%15]})
32ATB3

PS C:\Tools\Scripts\golfing> -join(0..5|%{'ABC123!@TPOI098'[(Random)%15]})
III@B2

PS C:\Tools\Scripts\golfing> -join(0..5|%{'ABC123!@TPOI098'[(Random)%15]})
@302O@

PS C:\Tools\Scripts\golfing> -join[char[]](0..5|%{Random(48..57+65..69)})
74E117

PS C:\Tools\Scripts\golfing> -join[char[]](0..5|%{Random(48..57+65..69)})
09D7DD

PS C:\Tools\Scripts\golfing> -join[char[]](0..5|%{Random(65..79)})
COJDFI

PS C:\Tools\Scripts\golfing> -join[char[]](0..5|%{Random(65..79)})
EAKCNJ

```
> 0 votes

# Answer
## Pyke, 35 bytes

### Arbitary alphabet, 20 bytes

```
6V"ABC123!@TPOI098"H

```

Try it here!

### Hex alphabet, 8 bytes

```
6V~J15<H

```

Try it here!

```
~J15< - "0123456789abcdefghijklmno..."[:15]

```

### Custom alphabet, 7 bytes

```
6VG15<H

```

Try it here!

```
G15< - alphabet[:15]

```

Alphabet chosen: `abcdefghijklmno`

```
6V     - repeat 6 times:
  ...  -   get alphabet
     H -  choose_random(^)

```
> -1 votes

---
Tags: code-golf, generation
---


title: Determine if a coin system is Canonical

text:
# Question
Title: Determine if a coin system is Canonical
The Cashier's Algorithm is an algorithm for making change in the minimal number of coins that works quite well for most currency systems. However like most greedy algorithms it is not without its flaws. If a currency system is set up just right (or just wrong) there are certain values in which the Cashier's Algorithm will fail to find the optimal change.

Take the following example:

We have 4¢, 3¢, and 1¢ coins. We want to make 6¢.

The Cashier's Algorithm will first select as many of the largest coin (one 4¢ to start) and subtract and repeat. This will result in one 4¢ coin and two 1¢ coins, for a total of 3 coins.

Unfortunately for the Algorithm there is a way to make 6¢ with only two coins (two 3¢ coins).

A system of change will be considered canonical iff for all integer values the Cashier's Algorithm will find the optimal number of coins.

## Task

You task will be to take a system as a either an unordered container or sorted ordered container of integers representing coin values and output a truthy value if the system input is canonical and falsy otherwise.

Your program should work for all systems that can create any value. (i.e. all systems will have a 1¢ coin)

This is code golf least bytes wins.

## Test cases

*This list is by no means exhaustive, your program should work for all valid input*

```
1, 3, 4       -> 0
1, 5, 10, 25  -> 1
1, 6, 10, 25  -> 0
1, 2, 3       -> 1
1, 8, 17, 30  -> 0
1, 3, 8, 12   -> 0
1, 2, 8, 13   -> 0
1, 2, 4, 6, 8 -> 1

```

# Answer
# Haskell, ~~94~~ ~~87~~ 82 bytes

```
f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

```

this solution works by defining a function `j` which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number `i`, and let `k` be the biggest number in the list not bigger than `i`. assume that `i >= 2k` and the system is canonical for all numbers less than `i`.

take some optimal way to make `i` out of coins, and assume it doesn't contain the coin `k`. if we throw away one of the coins, the new sum of coins must be bigger than `k` and smaller than `i` \- but the cashier's algorithm on this number would use the `k` coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin `k`, and therefore there is a set of coins containing the coin `k` for the number `i`, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

Edit: five bytes off thanks to Ørjan Johansen!
> 9 votes

# Answer
# PHP, 323 Bytes

Same way as other count the coins until the sum of the two last elements in the array

```
<?function t($g){rsort($g);$m=array_slice($g,1);for($y=1,$i=$g[0];$i<$g[0]+$m[0];$i++){$a=$b=$i;$p=0;$r=$s=[];while($a||$b){$o=$n=0;$g[$p]<=$a?$a-=$r[]=$g[$p]:$o=1;($m[$p]??1)<=$b?$b-=$s[]=$m[$p]:$n=1;$p+=$o*$n;}$y*=count($r)<=count($s);}return$y;}for($i=0,$t=1;++$i<count($a=$_GET[a]);)$t*=t(array_slice($a,0,$i+1));echo$t;

```

# My best and longest answer I believe \>370 Bytes

I give only an expanded version cause it is longer then my answer before

```
for($x=1,$n=0,$f=[];++$n<count($a)-1;){
$z=array_slice($a,0,$n+1);
$q=$a[$n]-$a[$n-1];
$i=array_fill(1,$c=max($a[$n+1]??1,11),"X");#$q*$a[$n]
$f=range($a[$n],$c,$q);

$f[]=2*$a[$n];
for($d=[$z[$n]],$j=0;$j<$n;){
   $f[]=$a[$n]+$d[]=$z[$n]-$z[$j++];
}

while($f){
    $i[$t=array_pop($f)]="T";
    foreach($d as $g)
    if(($l=$t+$g)<=$c)$f[]=$l;
}

foreach($i as$k=>$v){
    if(in_array($k,$z))$i[$k]="S";
}
#var_dump($i);
if($i[$a[$n+1]]=="X")$x*=0;
}
echo$x;

```

## Explanation for this answer

Online Version

1. Set all in the array to false == X
2. Set all numbers in the array you control to S
3. Found differences between the last S and the other S or 0
4. Start at last S in the array
5. Set all number to D Where Last S+ one of all differences
6. Begin at all D
7. SET "T" to D values in the array
8. GOTO 5 Repeat it with all found D I did it not really in the code
9. If next item in the Array has X it is a false case else True

Additional Steps Difference is in the case in the snippet 3 Between 1 and 4 are 2 X This means you need the second D by Step 5. After this value in this case 10 are all cases true I could see so far that there is a relationship between difference and the count in the array you control to calculate how much D (Step 5) you need to get the point before you find the last false case.

You set multiple values from the last item directly to true. These Points can make a difference to decide if it could been that the greedy count of coins with the next value is same then the multiple of the last in the array. On the other way you can set enemy

1. Set first enemy at 1+Last S
2. From this Point add each value in the array to set the next enemies
3. Start with last enemy Goto 2

If you now have enemies and true cases in it the probability grows that the counts can be the same With more D the probability sinks.

```
table{width:80%}
td,th{width:45%;border:1px solid blue;}
```

```
<table>
  <caption>Working [1,4]</caption>
<tr><th>Number</th><th>Status</th></tr>
<tr><td>1</td><td>S</td></tr>
<tr><td>2</td><td>X</td></tr>
<tr><td>3</td><td>X</td></tr>
<tr><td>4</td><td>S</td></tr>
<tr><td>5</td><td>X</td></tr>
<tr><td>6</td><td>X</td></tr>
<tr><td>7</td><td>D3</td></tr>
<tr><td>8</td><td>D4</td></tr>
<tr><td>9</td><td>X</td></tr>
<tr><td>10</td><td>D3D3</td></tr>
<tr><td>11</td><td>D4D3</td></tr>
<tr><td>12</td><td>D4D4</td></tr>
<tr><td>13</td><td>D3D3D3</td></tr>
<tr><td>14</td><td>D4D3D3</td></tr>
<tr><td>15</td><td>D4D4D4</td></tr>
<tr><td>16</td><td>D4D4D3</td></tr>
</table>
<ul>
  <li>S Number in Array</li>
  <li>D Start|End point TRUE sum Differences from last S</li>
  <li>X False</li>
  </ul>
```

plus ? Bytes Thank You @JonathanAllan to give me wrong test cases
262 Bytes Nearly but not good enough 4 wrong testcase in the moment

test cases \[1,16,256\] before should true after false

```
<?for($q=[1],$i=0,$t=1,$w=[0,1];++$i<count($a=$_GET[v]);$w[]=$a[$i],$q[]=$m)($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])&&((($x)%2)==(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)||(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0||in_array($m,$w))?:$t=0;echo$t;

```

Ascending Order of the Array

## Explanation

```
for($q=[1],$i=0,$t=1,$w=[0,1] # $t true case $q array for modulos $w checke values in the array
;++$i<count($a=$_GET[v])   #before loop
;$w[]=$a[$i],$q[]=$m) # after loop $q get the modulo from the result and fill $w with the checked value

($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])
# First condition difference between $a[i] and $a[$i-1] is greater or equal $a[$i-1] and $a[$i-2]
# if $a[$-1] == 1 $a[$i-2] will be interpreted as 0
&&  ## AND Operator with the second condition
(
(($x)%2)==   # See if the difference is even or odd
(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)
# After that we multiply the result with the lower value *$a[$i-1]
    # for this result we calculate the modulo of the result with the greater value %$a[$i]
    # if the difference and the modulo are both even or odd this belongs to true
# and the modulo of the result must be greater as the sum of these before
    # Ask me not why I have make try and error in an excel sheet till I see this relation
||
(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0 # or differce modulator is even and difference $a[$i],$a[$i-1] is a multiple of half difference $a[$i-1],$a[$i-2]
||
in_array($m,$w) # if the modulo result is equal to the values that we have check till this moment in the array we can also neglect the comparison
)
?:$t=0; # other cases belongs to false
echo$t; #Output

```

It looks like that what I have seen the table contains values from \[1,2,3,4,5,6\] and I change only the last item until 9. for 2to3 and 4to5 we create the value of the lower value in the modulo calculation

```
table{width:95%;}th,td{border:1px solid}
```

```
<table><tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>35</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>45</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>3</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>3</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>8</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>55</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>7</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>4</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>9</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>65</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>2</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></table>
```
> 5 votes

# Answer
# Pyth, ~~18~~ 15 bytes

```
!x#eST.gsky_S*e

```

Test suite

A different sort of brute force. This starts by forming all collections of coins with up to k of each, where k is the largest coin, which is assumed to be the last coin. I believe this always sufficient to form two sets of coins with the same sum, one greedy and one shorter, whenever such a pair exists.

I then locate such a pair as follows:

The subsets are generated in order of increasing size, and lexicographically by position in the input secondarily. Group the coin collections by their sums, stably. Each coin collection is generated in descending order, so the greedy solution will be the first element of the group if and only if the greedy solution is optimal, and it will be the last element of the group lexicographically. Thus, we find the greedy solution, and filter on a nonzero index in the group. If the coin set is cannonical, this will filter out everything, so we simply logically negate the result and output.

Explanation:

```
!x#eST.gsky_S*e
!x#eST.gsky_S*eQQ   Variable introduction.
                    Q = eval(input()) - sorted list of coins.
              eQ    Greatest coin in the list
             *  Q   Repeat that many times.
            S       Sort the coins
           _        Reverse, so we have the coins in descending order.
          y         Form all subsets, in increasing size then
                    decreasing lexicographic order.
      .gsk          Group by sum
 x#                 Filter by the index in the group of
   eST              The last element lexicographically (greedy solution).
!                   Logically negate.

```
> 5 votes

# Answer
# Python, ~~218 211~~ 205 bytes

-1 byte thanks to @TuukkaX (a space could be deleted between `<3` and `or`)

```
from itertools import*
g=lambda x,c,n=0:x and g(x-[v for v in c if v<=x][0],c,n+1)or n
lambda c:len(c)<3or 1-any(any(any(x==sum(p)for p in combinations(c*i,i))for i in range(g(x,c)))for x in range(c[0]*2))

```

**repl.it**

Input in descending order.

Horribly brute force. Any set of a single unit coin and some other coin is canonical. For larger sets the smallest fail case, if one exists will be greater than or equal to the 3rd smallest coin (not sure myself how it could be equal!) and less than the sum of the two largest coins - see this paper (which actually references another but also gives an O(n^3) method).

`g` counts the coins used by the greedy method, and the unnamed function traverses the possible candidates (actually from 0 to one less than twice the largest coin to save bytes) and looks for any collection of less coins that also sum to that amount.

`g` works by performing what a cashier would, it recursively takes the largest coin less than or equal to the amount still to make up, `[v for v in c if v<=x][0]` away, and counts up the number of coins used, `n`.

The unnamed function returns 1 if `len(c)` is less than 3, and otherwise tests that it is not the case, `1-...`, that any values in the range of possibilities, `range(c[0]*2)))`, are possible with less coins, `i in range(g(x,c))`, by making a collection of that many of every coin, `c*i`, and examining all combinations of `i` coins, `combinations(c*i,i)`, to see if any sum to the same value.
> 4 votes

# Answer
# JavaScript (ES6), 116 ~~125 130~~

```
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

```

This needs the input array sorted in descending order. For each value from 2N downto 2 (N being the max coin value), it find the number of coins from the greedy algorithm and try to find a smaller set of coins.

*Less golfed*

```
l=>{
  // recursive function to to find a smaller set of coins
  // parameter k is the max coin limit
  r = (d,k) => d // check if difference is not 0
     ? --k // if not, and if the number of coins used will be less than limit
      && l.map(v => v>d || r(d-v, k))  // proceed with the recursive search
     : x=1 // if diff is 0, value found, set x to 1 to stop the loop
  for( x=l[0]*2; --x > 1; )
    g=0, h=x, l.map(v=>(g += h/v|0, h %= v)), // find g with the greedy algorithm
    r(x,g) // call with initial difference equal to target value
  return x
}

```

**Test**

```
f=
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

/* No eval
f=l=>{
  r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;
  for(x=l[0]*2;--x>1;r(x,g))
    g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));
  return x;
}*/

;[
 [[100,50,20,10,5,2,1],1], [[4,3,1],0],
 [[25,10,5,1],1], [[25,10,6,1],0],
 [[3,2,1],1], [[30,17,8,1], 0],
 [[12,8,3,1],0], [[13,8,2,1], 0]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),
      msg=((r==k)?'OK ':'KO ')+i+' -> '+r
      + (r==k?'':' (should be '+k+')')
  O.textContent += msg+'\n'
})

function test()
{
  var i=I.value.match(/\d+/g).map(x=>+x).sort((a,b)=>b-a)
  O.textContent = i+' -> '+f(i)+'\n'+O.textContent
 }
```

```
#I { width:50% }
```

```
<input id=I value='1 4 9'><button onclick='test()'>test</button>
<pre id=O></pre>
```
> 4 votes

# Answer
## JavaScript (ES6), ~~144~~ ~~132~~ ~~124~~ ~~122~~ 110 bytes

```
a=>![...Array(a[0]*2)].some((_,i)=>(g=(a,l=0,n=i)=>[a.filter(c=>c>n||(l+=n/c|0,n%=c,0)),-l*!n])(...g(a))[1]>0)

```

Requires the array to be sorted in descending order. Uses the observation in the linked paper that if the system is not canonical then there is at least one value less than 2a\[0\] which takes fewer coins when decomposed using the unused coins from the initial greedy algorithm.

Edit: Saved 12 bytes by realising that I could check all the coins even though I had already reached the target value. Saved 8 bytes by switching my intermediate output from `[l,b]` to `[b,-l]`; this allowed me to pass the first result directly as the parameter of the second call, plus also a small saving detecting whether the second call was successful. Saved 2 bytes by moving the definition of `g` into the `some` callback, allowing me to avoid unnecessarily passing in the loop variable twice. Saved 12 bytes by switching from my recursive helper function to a call to `filter` (made possible by my intermediate output switch).
> 2 votes

# Answer
# Jelly (fork), ~~15~~ 14 bytes

```
SRæFµS€Ṃ=$Ṫµ€Ȧ

```

This solution uses the bounds for counter-examples from this paper. There, the author uses a tight bound for the counter-example, but in the interests of golfing, the range of the sum of coin denominations is used which is larger and contains that bound.

This program computes all test cases in less than a second on my machine.

Unfortunately, this relies on a branch of Jelly where I was working on implementing a Frobenius solve atom so you cannot try it online.

## Usage

```
$ ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ' '1,2,4,6,8'
1

```

The performance is good and can solve all test cases at once in less than a second.

```
$ time ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ¶Ç€' '[[1,3,4],[1,5,10,25],[1,6,10,25],[1,2,3],[1,8,17,30],[1,3,8,12],[1,2,8,13],[1,2,4,6,8]]'
[0, 1, 0, 1, 0, 0, 0, 1]

real    0m0.793s
user    0m0.748s
sys     0m0.045s

```

# Explanation

```
SRæFµS€Ṃ=$Ṫµ€Ȧ  Input: list of integers C
    µ           Start a new monadic chain
S                 Sum
 R                Range, [1, 2, ..., sum(C)]
  æF              Frobenius solve for each X in the range using coefficients from C
                  This generates all vectors where the dot product of a
                  vector with C equals X, ordered by using values from the
                  start to end of C
           µ€   Start a new monadic chain that operates on each list of vectors
     S€           Sum each vector
         $        Monadic hook on the sums
       Ṃ            Minimum (This is the optimal solution)
        =           Vectorized equals, 1 if true else 0
          Ṫ       Tail (This is at the index of the greedy solution)
             Ȧ  All, returns 0 if it contains a falsey value, else 1

```
> 2 votes

# Answer
# Perl, 69 bytes

Includes +2 for `-pa`

Give coins in descending order on STDIN. You can optionally leave out the `1` coin.

```
coins.pl <<< "4 3 1"

```

`coins.pl`:

```
#!/usr/bin/perl -pa
$_=!map{grep$`>=$_&&($n=$G[$`-$_]+1)<($G[$`]||=$n),@F,/$/}1..2*"@F"

```

Builds up the number of coins used by the cashiers algorithm in `@G` for amounts 1 to twice the largest coin. For each amount checks that if that amount is reduced by 1 coin value the cashiers algorithm needs at most 1 less coin. If not this is a counterexample (or there was an earlier counterexample). I could stop at the first counterexample but that takes more bytes. So the time complexity is `O(max_coin * coins)` and space complexity is `O(max_coin)`
> 2 votes

---
Tags: code-golf, number, combinatorics, decision-problem
---


title: Letter-replacement challenge

text:
# Question
Title: Letter-replacement challenge
The idea is simple. You've to create a "visualised" letter-replacement, by providing 3 strings (input can be comma separated, separate inputs, or as an array). The first segment is the word you want to correct, and the second segment is the letters you want to replace, and the third segment is the replacement for the letters in segment 2.

For example:

```
|    | Input                       | Starting Word | Output      |
|----|-----------------------------|---------------|-------------|
| #1 | Hello world -wo -ld +Ea +th | Hello world   | Hello Earth |
| #2 | Hello World -wo -ld +Ea +th | Hello World   | Hello Worth |
| #3 | Hello -llo +y               | Hello         | Hey         |
| #4 | Red -R -d +Gr +en           | Red           | Green       |
| #5 | mississippi -is -i +lz +p   | mississippi   | mlzslzspppp |
| #6 | Football -o -a +a +i        | Football      | Fiitbill    |
| #7 | mississippi -is -i +iz +p   | mississippi   | mpzspzspppp |

```

### Explanation

The replacements are to be done step-by-step with their respective pair. Here's an illustration with an input of `mississippi -is -i +iz +p` to give the output `mpzspzsppp` (see example `#7` above)

```
| Step  | Input                         | Output        |
|------ |---------------------------    |-------------  |
| #1    | mississippi -is -i +iz +p     |               |
| #2    | mississippi -is +iz           | mizsizsippi   |
| #3    | mizsizsippi -i +p             | mpzspzspppp   |

```

### Rules

* Inputs are always in this order `<starting_string> <list_of_letters_to_replace> <replacement_letters>`.
* Letters to replace and replacement groups will never be mixed (ie: there will never be `-a +i -e +o`).
* Letters to replace are *always* prefixed with `-` and replacement letters are always prefixed with `+`. (The prefix is mandatory)
* There may be more than one set of letters to replace, so you'd need to look at the prefix.
* Assume the amount of letter groups to replace and the amount of replacement letter groups are always equal (ie: there will never be `-a -e +i`)
* Replacements are case-sensitive (see example `#1` and `#2`).
* Replacements are done in the order they were given in the input.
* Letter replacements can be replaced with other replacements. See example `#6`.
* The first segment (starting word) will *never* include `-` or `+` characters.
* This is code-golf so shortest bytes win.

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

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

```
# Language Name, N bytes

```

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

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

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=96473,OVERRIDE_USER=38505;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 6 votes
## JavaScript (ES6), ~~85~~ 83 bytes

```
f=(s,n=1,l=s.split(/ \W/))=>(r=l[n+l.length/2|0])?f(s.split(l[n]).join(r),n+1):l[0]

```

### Test cases

```
f=(s,n=1,l=s.split(/ \W/))=>(r=l[n+l.length/2|0])?f(s.split(l[n]).join(r),n+1):l[0]

console.log(f("Hello world -wo -ld +Ea +th"));
console.log(f("Hello World -wo -ld +Ea +th"));
console.log(f("Hello -llo +y"));
console.log(f("Red -R -d +Gr +en"));
console.log(f("mississippi -is -i +lz +p"));
console.log(f("Football -o -a +a +i"));
console.log(f("mississippi -is -i +iz +p"));
```

# Answer
> 6 votes
# 05AB1E, ~~15~~ 17 bytes

```
IIð¡€áIð¡€á‚øvy`:

```

Try it online!

**Explanation**

```
I                   # read starting string
 I                  # read letters to be replaced
  ð¡                # split on space
    €á              # and remove "-"
      I             # read replacement letters
       ð¡           # split on space
         €á         # and remove "+"
           ‚ø       # zip to produce pairs of [letters to replace, replacement letters]
             vy`:   # for each pair, replace in starting string

```

Or with a less strict input format

```
vy`:

```

Try it online

# Answer
> 5 votes
## Pyke, ~~13~~ 11 bytes

```
z[zdcmt)[.:

```

Try it here!

```
z           - input()
 [zdcmt)    - def func():
  zdc       -  input().split(" ")
     mt     -  map(>[1:], ^)
            - func()
        [   - func()
         .: - translate()

```

Or 2 bytes if in a different input format:

```
.:

```

Try it here!

# Answer
> 4 votes
## Perl, 58 bytes

**57 bytes code + 1 for `-p`.**

Requires first item on one line, then the replacements on the next. Big thanks to @Dada who came up with a different approach to help reduce by 4 bytes!

```
$a=<>;1while$a=~s%-(\S*)(.*?)\+(\S*)%"s/$1/$3/g;q{$2}"%ee

```

### Usage

```
perl -pe '$a=<>;1while$a=~s%-(\S*)(.*?)\+(\S*)%"s/$1/$3/g;q{$2}"%ee' <<< 'Football
-o -a +a +i'
Fiitbill

```

```
perl -pe '$a=<>;1while$a=~s%-(\S*)(.*?)\+(\S*)%"s/$1/$3/g;q{$2}"%ee' <<< 'mississippi
-is -i +iz +p'
mpzspzspppp

```

```
perl -pe '$a=<>;1while$a=~s%-(\S*)(.*?)\+(\S*)%"s/$1/$3/g;q{$2}"%ee' <<< 'mississippi
-ippi -i -mess +ee +e +tenn'
tennessee

```

# Answer
> 3 votes
# PHP, ~~98~~ 97 bytes

```
for($s=$argv[$i=1];$v=$argv[++$i];)$r[$v[0]>'+'][]=substr($v,1);echo str_replace($r[1],$r[0],$s);

```

This challenge describes the exact behaviour of str\_replace so for php it's all about making the arrays of replacements. I tried to do it using only one "substring" but that might not be the best solution. Use like:

```
php -r "for($s=$argv[$i=1];$v=$argv[++$i];)$r[$v[0]>'+'][]=substr($v,1);echo str_replace($r[1],$r[0],$s);" "mississippi" "-is" "-i" "+iz" "+p"

```

edit: 1 byte saved thanks to Titus

# Answer
> 3 votes
# GNU sed 86 Bytes

Includes +1 for -r

```
:;s,^([^-]*)(\w+)([^-]*-)\2( [^+]*\+)(\w*),\1\5\3\2\4\5,
t;s,-[^-+]*,,;s,\+[^-+]*,,;t

```

Try it online!

Example:

```
$ echo 'Hello world -wo -ld +Ea +th'|sed -rf replace.sed
Hello Earth

```

# Answer
> 2 votes
# Java 7, ~~153~~ 133 bytes

```
String c(String[]a){String r=a[0],z[]=a[1].split(" ?-");for(int i=0;i<z.length;r=r.replace(z[i],a[2].split(" ?[+]")[i++]));return r;}

```

**Ungolfed & test code:**

Try it here.

```
class M{
  static String c(String[] a){
    String r = a[0],
           z[] = a[1].split(" ?-");
    for(int i = 0; i < z.length; r = r.replace(z[i], a[2].split(" ?[+]")[i++]));
    return r;
  }

  public static void main(String[] a){
    System.out.println(c(new String[]{ "Hello world", "-wo -ld", "+Ea +th" }));
    System.out.println(c(new String[]{ "Hello World", "-wo -ld", "+Ea +th" }));
    System.out.println(c(new String[]{ "Hello", "-llo", "+y" }));
    System.out.println(c(new String[]{ "Red", "-R -d", "+Gr +en" }));
    System.out.println(c(new String[]{ "mississippi", "-is -i", "+lz +p" }));
    System.out.println(c(new String[]{ "Football", "-o -a", "+a +i" }));
    System.out.println(c(new String[]{ "mississippi", "-is -i", "+iz +p" }));
  }
}

```

**Output:**

```
Hello Earth
Hello Worth
Hey
Green
mlzslzspppp
Fiitbill
mpzspzspppp

```

# Answer
> 2 votes
# R, 98 94 bytes

Edit: saved 4 bytes thanks to @rturnbull

```
i=scan(,"");s=i[1];i=gsub("\\+|-","",i[-1]);l=length(i)/2;for(j in 1:l)s=gsub(i[j],i[l+j],s);s

```

**Ungolfed and test cases**

Because `scan` (reads input from stdin) doesn't work properly in R-fiddle I showcase the program by wrapping it in a function instead. Note that the function takes a vector as an input and can be run by e.g.: `f(c("Hello world", "-wo", "-ld", "+Ea", "+th"))`. The gofled program above would prompt the user to input using stdin whereby typing `"Hello world" -wo -ld -Ea +th` in the console would yield the same result.

Run the code on R-fiddle

```
f=function(i){
    s=i[1]                                   # Separate first element
    i=gsub("\\+|-","",i[-1])                 # Remove + and - from all elements except first, store as vector i
    l=length(i)/2                            # calculate the length of the vector i (should always be even)
    for(j in 1:l)s=gsub(i[j],i[l+j],s)       # iteratively match element j in i and substitute with element l+j in i
    s                                        # print to stdout
}

```

# Answer
> 2 votes
# PHP, 164 Bytes

```
preg_match_all("#^[^-+]+|-[\S]+|[+][\S]+#",$argv[1],$t);for($s=($a=$t[0])[0];++$i<$c=count($a)/2;)$s=str_replace(trim($a[+$i],"-"),trim($a[$i+$c^0],"+"),$s);echo$s;

```

# Answer
> 2 votes
# Vim, 25 bytes

`qq+dE+r-PdiW:1s<C-R>"-g<CR>@qq@q`

Assumes input in this format:

```
mississippi
-is -i
+lz +p

```
* `+dE+r-PdiW`: Combines `-` and `+` into single register, with the `+` turned into a `-`.
* `:1s<C-R>"-g`: Uses the register as a code snippet, inserted directly into the `:s` command, with `-` as the separator.

# Answer
> 2 votes
## Haskell, ~~85~~ 78 bytes

```
import Data.Lists
g=map tail.words
a#b=foldl(flip$uncurry replace)a.zip(g b).g

```

Usage example: `("mississippi" # "-is -i") "+lz +p"` -\> `"mlzslzspppp"`.

How it works:

```
g=map tail.words              -- helper function that splits a string into a
                              -- list of words (at spaces) and drops the first
                              -- char of each word

                zip(g b).g    -- make pairs of strings to be replaced and its
                              -- replacement
foldl(flip$uncurry replace)a  -- execute each replacement, starting with the
                              -- original string
                              -- -> "flip" flips the arguments of "uncurry replace"
                              --           i.e. string before pair of replacements
                              -- "uncurry" turns a function that expects two
                              --           lists into one that expects a list of pairs

```

Edit: @BlackCap found 6 bytes to save and I myself another one.

# Answer
> 2 votes
# Convex, 19 bytes

```
¶:äz{S*"-+"-ä~@\ò}/

```

Try it online!

# Answer
> 1 votes
# Python 3, 93 byte

```
def f(s):
  s,m,p=s
  for n,o in zip(m.split(),p.split()):s=s.replace(n[1:],o[1:])
  return s

```

Try it online!

Input is a list with strings, replacement strings are space separated.

Example input: `['mississippi','-is -i','+iz +p']`

# Answer
> 1 votes
## PowerShell v2+, 90 bytes

```
param($a,$b,$c)-split$b|%{$a=$a-creplace($_-replace'-'),((-split$c)[$i++]-replace'\+')};$a

```

Takes input as three arguments, with the `-` and `+` strings space-separated. Performs a `-split` on `$b` (the `-split` when acting in a unary fashion splits on whitespace), then loops `|%{...}` through each of those. Every iteration we're removing the `-`, finding the next `[$i++]` replacement string and removing the `+` from it, and using the `-creplace` (case-sensitive replacement) to slice and dice `$a` and store it back into `$a`. Then, `$a` is left on the pipeline and output is implicit.

```
PS C:\Tools\Scripts\golfing> .\letter-replacement-challenge.ps1 'mississippi' '-is -i' '+iz +p'
mpzspzspppp

PS C:\Tools\Scripts\golfing> .\letter-replacement-challenge.ps1 'Hello world' '-wo -ld' '+Ea +th'
Hello Earth

PS C:\Tools\Scripts\golfing> .\letter-replacement-challenge.ps1 'Hello World' '-wo -ld' '+Ea +th'
Hello Worth

```

# Answer
> 1 votes
# PHP, 106 bytes

```
for($s=($v=$argv)[$i=1];$i++<$n=$argc/2;)$s=str_replace(substr($v[$i],1),substr($v[$n+$i-1],1),$s);echo$s;

```

straight forward approach. Run with `php -r '<code> <arguments>`.

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