title: Write a brainfuck compiler

text:
# Question
Title: Write a brainfuck compiler
Write a program that takes a brainfuck program and compiles it to executable machine code. You can target x86, x86\_64, jvm (java bytecode) or armv6, and use one of the following executable formats: ELF, a.out, class file, exe, com. The executable should work in Linux or Windows (or Java on either).

Neither your program nor the generated executable may run any external program (such as another compiler, assembler or interpreter).

Shortest code wins.

# Answer
> 5 votes
# C, ~~866~~ 783 bytes

Since my code outputs 32 bit ELF executable I can't promise that it will work on everyones setup. It took enough tweaking to get the executable to stop segfaulting on my computer.

For anyone trying to run this:

```
$ uname --all
Linux 4.4.0-24-generic #43-Ubuntu SMP Wed Jun 8 19:27:37 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

```

A Brainfuck program is read from stdin and the compiled ELF is written to stdout.

```
#define P *(t++)
#define C case
#define B break
char a[30000],b[65535],f,*t=b;*c[100];**d=c;main(g){P=188;t+=4;while((f=getchar())!=-1)switch(f){C'>':P=68;B;C'<':P=76;B;C'+':P=254;P=4;P=36;B;C'-':P=254;P=12;P=36;B;C'.':P=187;t+=4;P=137;P=225;P=186;P=1;t+=3;P=184;P=4;t+=3;P=205;P=128;B;C',':P=187;P=1;t+=3;P=137;P=225;P=186;P=1;t+=3;P=184;P=3;t+=3;P=205;P=128;B;C'[':P=138;P=4;P=36;P=133;P=192;P=15;P=132;t+=4;*d=(int*)t-1;d++;B;C']':P=138;P=4;P=36;P=133;P=192;P=15;P=133;t+=4;d--;g=((char*)(*d+1))-t;*((int*)t-1)=g;**d=-g;B;}P=184;P=1;t+=3;P=187;t+=4;P=205;P=128;*(int*)(b+1)=0x8048054+t-b;long long z[]={282579962709375,0,4295163906,223472812116,0,4297064500,4294967296,577727389698621440,36412867248128,30064779550,140720308490240};write(1,&z,84);write(1,b,t-b);write(1,a,30000);}

```

# Ungolfed

In the ungolfed version of the code, you can get a better idea of what's going on. The character array at the end of the golfed code is an encoding of the ELF and program header in the ungolfed code. This code also show how each Brainfuck instruction is translated into bytecode.

```
#include <linux/elf.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>

#define MAX_BIN_LEN 65535
#define MAX_JUMPS 100

unsigned int org = 0x08048000;

unsigned char move_right[] = {0x44};                              /*inc   esp         */

unsigned char move_left[]  = {0x4c};                              /*dec   esp         */

unsigned char inc_cell[]   = {0xfe,0x04,0x24};                    /*inc   [esp]       */

unsigned char dec_cell[]   = {0xfe,0x0c,0x24};                    /*dec   [esp]       */

unsigned char read_char[]  = {0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x03,0x00,0x00,0x00,           /*mov   eax,  3     */
                              0xcd,0x80};                         /*int   0x80        */

unsigned char print_char[] = {0xbb,0x01,0x00,0x00,0x00,           /*mov   ebx,  1     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x04,0x00,0x00,0x00,           /*mov   eax,  4     */
                              0xcd,0x80};                         /*int   0x80        */

unsigned char loop_start[] = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x84,0x00,0x00,0x00,0x00};     /*je    int32_t     */

unsigned char loop_end[]   = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x85,0x00,0x00,0x00,0x00};     /*jne   int32_t     */

unsigned char call_exit[]  = {0xb8,0x01,0x00,0x00,0x00,           /*mov   eax,  1     */
                              0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0xcd,0x80};                         /*int   0x80        */
unsigned char prelude[]    = {0xbc,0x00,0x00,0x00,0x00};          /*mov   esp, int32_t*/

unsigned char tape[100];

int main(){
    unsigned char text[MAX_BIN_LEN];
    unsigned char *txt_ptr = text;

    int32_t *loop_jmps[MAX_JUMPS];
    int32_t **loop_jmps_ptr = loop_jmps;

    Elf32_Off entry;

    entry = org + sizeof(Elf32_Ehdr) + 1 * sizeof(Elf32_Phdr);

    memcpy(txt_ptr,prelude,sizeof(prelude));
    txt_ptr += sizeof(prelude);
    char input;
    while((input = getchar()) != -1){
        switch(input){
            case '>':
                memcpy(txt_ptr,move_right,sizeof(move_right));
                txt_ptr += sizeof(move_right);
                break;
            case '<':
                memcpy(txt_ptr,move_left,sizeof(move_left));
                txt_ptr += sizeof(move_left);
                break;
            case '+':
                memcpy(txt_ptr,inc_cell,sizeof(inc_cell));
                txt_ptr += sizeof(inc_cell);
                break;
            case '-':
                memcpy(txt_ptr,dec_cell,sizeof(dec_cell));
                txt_ptr += sizeof(dec_cell);
                break;
            case '.':
                memcpy(txt_ptr,print_char,sizeof(print_char));
                txt_ptr += sizeof(print_char);
                break;
            case ',':
                memcpy(txt_ptr,read_char,sizeof(read_char));
                txt_ptr += sizeof(read_char);
                break;
            case '[':
                memcpy(txt_ptr,loop_start,sizeof(loop_start));
                txt_ptr += sizeof(loop_start);
                *loop_jmps_ptr = (int32_t*) txt_ptr - 1;
                loop_jmps_ptr++;
                break;
            case ']':
                memcpy(txt_ptr,loop_end,sizeof(loop_end));
                txt_ptr += sizeof(loop_end);
                loop_jmps_ptr--;
                int32_t offset = ((unsigned char*) (*loop_jmps_ptr + 1)) - txt_ptr;
                *((int32_t*)txt_ptr - 1) = offset;
                **loop_jmps_ptr = -offset;
                break;
        }
    }

    memcpy(txt_ptr,call_exit,sizeof(call_exit));
    txt_ptr += sizeof(call_exit);

    *(int32_t*)(text + 1) = entry + (txt_ptr - text);

    Elf32_Ehdr ehdr = {
        {0x7F,'E','L','F',ELFCLASS32,ELFDATA2LSB,EV_CURRENT,0,0,0,0,0,0,0,0,0},
        ET_EXEC,
        EM_386,
        EV_CURRENT,
        entry,
        sizeof(Elf32_Ehdr),
        0,
        0,
        sizeof(Elf32_Ehdr),
        sizeof(Elf32_Phdr),
        1,
        0,
        0,
        SHN_UNDEF,
    };

    Elf32_Phdr phdr = {
        PT_LOAD,
        0,
        org,
        org,
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        PF_R | PF_X | PF_W,
        0x1000,
    };

    int out = open("a.out",O_CREAT|O_TRUNC|O_WRONLY,S_IRWXU);
    write(out,&ehdr,sizeof(Elf32_Ehdr));
    write(out,&phdr,sizeof(Elf32_Phdr));

    write(out,text,txt_ptr-text);
    write(out,tape,sizeof(tape));
    close(out);
}

```

---

# Self Modifying BrainFuck

In order to save on bytes, the tape for my compiler isn't allocated in a `.bss` section or anything fancy like that. Instead, the tape is 30,000 null bytes written directly after the compiled byte code of the Brainfuck program. Knowing this, and being aware of what byte code is generated by my compiler means that you can generate or modify byte code at runtime. A simple illustration of this 'feature' is a Brainfuck program that sets its own exit value.

```
 <<<<<<+

```

The program goes off the left edge of the tape into the byte code to the point that the exit code is normally set 0. Incrementing this byte causes the exit code to be set to 1 instead of 0 when the program eventually exits. With persistence, this could be used to do system level programming in Brainfuck.

# Answer
> 13 votes
## Python, 1974 chars

```
import sys
s='\x11\x75\x30\xbc\x08\x4b\x03\x3c'
k=[]
for c in sys.stdin.read():
 if'>'==c:s+='\x84\x01\x01'
 if'<'==c:s+='\x84\x01\xff'
 if'+'==c:s+='\x2a\x1b\x5c\x33\x04\x60\x91\x54'
 if'-'==c:s+='\x2a\x1b\x5c\x33\x04\x64\x91\x54'
 if'['==c:k+=[len(s)];s+='\x2a\x1b\x33\x99\x00\x00'
 if']'==c:a=k[-1];k=k[:-1];d=len(s)-a;s=s[:a+4]+'%c%c'%(d>>8,d&255)+s[a+6:]+'\xa7%c%c'%(-d>>8&255,-d&255)
 if','==c:s+='\x2a\x1b\xb2\x00\x02\xb6\x00\x03\x91\x54'
 if'.'==c:s+='\xb2\x00\x04\x59\x2a\x1b\x33\xb6\x00\x05\xb6\x00\x06'
s+='\xb1'
n=len(s)
sys.stdout.write('\xca\xfe\xba\xbe\x00\x03\x00-\x00+\n\x00\x08\x00\x13\t\x00\x14\x00\x15\n\x00\x16\x00\x17\t\x00\x14\x00\x18\n\x00\x19\x00\x1a\n\x00\x19\x00\x1b\x07\x00\x1c\x07\x00\x1d\x01\x00\x06<init>\x01\x00\x03()V\x01\x00\x04Code\x01\x00\x0fLineNumberTable\x01\x00\x04main\x01\x00\x16([Ljava/lang/String;)V\x01\x00\nExceptions\x07\x00\x1e\x01\x00\nSourceFile\x01\x00\x06B.java\x0c\x00\t\x00\n\x07\x00\x1f\x0c\x00 \x00!\x07\x00"\x0c\x00#\x00$\x0c\x00%\x00&\x07\x00\'\x0c\x00(\x00)\x0c\x00*\x00\n\x01\x00\x01B\x01\x00\x10java/lang/Object\x01\x00\x13java/io/IOException\x01\x00\x10java/lang/System\x01\x00\x02in\x01\x00\x15Ljava/io/InputStream;\x01\x00\x13java/io/InputStream\x01\x00\x04read\x01\x00\x03()I\x01\x00\x03out\x01\x00\x15Ljava/io/PrintStream;\x01\x00\x13java/io/PrintStream\x01\x00\x05write\x01\x00\x04(I)V\x01\x00\x05flush\x00!\x00\x07\x00\x08\x00\x00\x00\x00\x00\x02\x00\x01\x00\t\x00\n\x00\x01\x00\x0b\x00\x00\x00\x1d\x00\x01\x00\x01\x00\x00\x00\x05*\xb7\x00\x01\xb1\x00\x00\x00\x01\x00\x0c\x00\x00\x00\x06\x00\x01\x00\x00\x00\x03\x00\t\x00\r\x00\x0e\x00\x02\x00\x0b\x00\x00'+'%c%c'%((n+60)>>8,(n+60)&255)+'\x00\x04\x00\x03\x00\x00'+'%c%c'%(n>>8,n&255)+s+'\x00\x00\x00\x01\x00\x0c\x00\x00\x00*\x00\n\x00\x00\x00\x05\x00\x06\x00\x06\x00\x08\x00\t\x00\x0b\x00\x0b\x00\x13\x00\r\x00\x1d\x00\x0f\x00&\x00\x11\x00,\x00\x12\x002\x00\x14\x008\x00\x15\x00\x0f\x00\x00\x00\x04\x00\x01\x00\x10\x00\x01\x00\x11\x00\x00\x00\x02\x00\x12')

```

Below are the translations to java bytecode. local 0 is a byte array representing the tape, local 1 is the data pointer.

```
>  iinc 1,+1
<  iinc 1,-1
+  aload_0;iload_1;dup2;baload;iconst_1;iadd;i2b;bastore
-  aload_0;iload_1;dup2;baload;iconst_1;isub;i2b;bastore
[  aload_0;iload_1;baload;ifeq xx xx
]  goto xx xx
,  aload_0;iload_1;getstatic #2;invokevirtual #3;i2b;bastore
.  getstatic #4;dup;aload_0;iload_1;baload;invokevirtual #5;invokevirtual #6

```

The `xx xx` are offsets to reach the matching bracket. #2 is `System.in`, #3 is `read()`, #4 is `System.out`, #5 is `write()`, and #6 is `flush()`.

The preamble allocates a 30000 byte array and initializes the tape position to 0.

The giant wrapper at the end was generated by compiling a dummy `B.java` file with code for one of each opcode (to induce generation of the correct constant tables and other junk), then performing delicate surgery on it.

Run it like

```
python bfc.py < input.b > B.class
java B

```

Disassemble with

```
javap -c B

```

I'm sure it could be golfed some more. I'm just happy it works...

# Answer
> 3 votes
## 16-bit x86 assembly code, 104 bytes

This code is from 2014, but I just found the task.

```
;compliant version, non-commands are ignored, but 104 bytes long

[bits 16]
[org 0x100]
; assume bp=091e used
; assume di=fffe
; assume si=0100
; assume dx=cs (see here)
; assume cx=00ff
; assume bx=0000
; assume ax=0000 used (ah)
; assume sp=fffe
start:
        mov al, code_nothing - start
code_start:
        mov ch, 0x7f ; allow bigger programs
        mov bx, cx
        mov di, cx
        rep stosb
        mov bp, find_right + start - code_start ;cache loop head for smaller compiled programs
        jmp code_start_end
find_right:
        pop si
        dec si
        dec si ;point to loop head
        cmp [bx], cl
        jne loop_right_end
loop_right:
        lodsb
        cmp al, 0xD5 ; the "bp" part of "call bp" (because 0xFF is not unique, watch for additional '[')
        jne loop_left
        inc cx
loop_left:
        cmp al, 0xC3 ; ret (watch for ']')
        jne loop_right
        loop loop_right ;all brackets matched when cx==0
        db 0x3c ;cmp al, xx (mask push)
loop_right_end:
        push si
        lodsw ; skip "call" or dummy "dec" instruction, depending on context
        push si
code_sqright:
        ret
code_dec:
        dec byte [bx]
code_start_end:
        db '$' ;end DOS string, also "and al, xx"
code_inc:
        inc byte [bx]
        db '$'
code_right:
        inc bx ;al -> 2
code_nothing:
        db '$'
code_left:
        dec bx
        db '$'
code_sqleft:
        call bp
        db '$'
; create lookup table
real_start:
        inc byte [bx+'<'] ;point to code_left
        dec byte [bx+'>'] ;point to code_right
        mov byte [bx+'['], code_sqleft - start
        mov byte [bx+']'], code_sqright - start
        lea sp, [bx+45+2] ;'+' + 4 (2b='+', 2c=',', 2d='-', 2e='.')
        push (code_dec - start) + (code_dot - start) * 256
        push (code_inc - start) + (code_comma - start) * 256
pre_write:
        mov ah, code_start >> 8
        xchg dx, ax
; write
        mov ah, 9
        int 0x21
; read
code_comma:
        mov dl, 0xff
        db 0x3d ; cmp ax, xxxx (mask mov)
code_dot:
        mov dl, [bx]
        mov ah, 6
        int 0x21
        mov [bx], al
        db '$'
        db 0xff ; parameter for '$', doubles as test for zero
; switch
        xlatb
        jne pre_write
  ; next two lines can also be removed
  ; if the program ends with extra ']'
  ; and then we are at 100 bytes... :-)
the_end:
        mov dl, 0xC3
        int 0x21
        int 0x20
```

---
Tags: code-golf, brainfuck, compiler
---


# Question
Title: Sum of indices of second least significant bit
This is a pure code-golf question.

**Input:** A non-negative integer n

**Output:** Sum of the indices of the second least significant set bit in the binary representation of the integers 0...n. If the number doesn't have two set bits then the contribution to the sum should be zero.

Your code should be runnable on a standard linux machine using free software and shouldn't take more than n+1 seconds to run.

Sample answers for `n` from `0..20`

```
0 0 0 1 1 3 5 6 6 9 12 13 16 18 20 21 21 25 29 30

```

Here is some sample ungolfed python code.

```
def get_2nd_least_bit(x):
    sum = 0
    for i in range(0,x.bit_length()):
        sum += (x >> i) & 1
        if sum == 2 :
            return i
    return 0
for x in xrange(20):
    print sum(get_2nd_least_bit(i) for i in xrange(x+1)),

```

# Answer
> 3 votes
# k \[21 chars\]

```
{+/{(&|0b\:x)1}'!x+1}

```

### Example

```
{+/{(&|0b\:x)1}'!x+1}[3]
1

{+/{(&|0b\:x)1}'!x+1}[7]
6

{+/{(&|0b\:x)1}'!x+1}[10]
12

{+/{(&|0b\:x)1}'!x+1}[500]
1410

```

# Answer
> 2 votes
## GolfScript (31 chars)

```
,{)2base-1%.,,\`{=}+,1=}%0+{+}*

```

This takes input on the stack and leaves output on the stack. Online demo which wraps it in a loop to output the first 12 values.

That implementation does the obvious thing of computing the base-2 representation of the integers in range. A more interesting approach, which sadly I haven't been able to golf as far, is to analyse the sequence. It's a sum of indices: let `i2(n)` be the index of the second LSB of `n`. We have `i2(2^x) = 0` (given as a special case). What can we say about the values which `i2` takes between `2^x` and `2^(x+1)`?

* Case 1: `2^x < k < 2^x + 2^(x-1)`. Then `k ^ (2^x + 2^(x-1)) = k - 2^(x-1)`. If `i2(k - 2^(x-1)) < x-1` then `i2(k) = i2(k - 2^(x-1))`; otherwise `i2(k) = x = 1 + i2(k - 2^(x-1))`.
* Case 2: `k = 2^x + 2^(x-1)`. Obviously `i2(k) = x` since there are two bits set.
* Case 3: `2^x + 2^(x-1) < k < 2^(x+1)` has bit `x-1` set and at least one less significant bit set, so `i2(k) = i2(k - 2^x)`.

In other words: the sequence of indices between consecutive powers of two can be found by splicing together three sequences: the previous sequence under the substitution `s/x-1/x/`; the sequence `[x]`; and the previous sequence unmodified.

* `[]`
* `[] + [1] + [] = [1]`
* `[2] + [2] + [1] = [2 2 1]`
* `[3 3 1] + [3] + [2 2 1] = [3 3 1 3 2 2 1]`
* `[4 4 1 4 2 2 1] + [4] + [3 3 1 3 2 2 1] = [4 4 1 4 2 2 1 4 3 3 1 3 2 2 1]`
* etc.

This leads to (40 chars)

```
([]{,2$<}{..0+0=:x+{.x=+}%\+}/1,*<0+{+}*

```

(Note for GS aficionados: a rare use for unfold!)

# Answer
> 2 votes
## J (and mathematics), way too much (aka. 45 chars), cubic memory and terrible runtime

```
+/,(*v>(2&^*1+a*2:)+/2^i.)"0]a=.i.v=.".1!:1]1

```

If I wanted to aim for length, I could of course do it the obvious, straightforward way and get something considerably shorter... however, I found it more interesting to investigate the properties of "index of second least significant set bit".

The J program above is an instance of the formula derived below. The idea is to build a huge table of numbers per bit index, then filter out those below the number we seek, then multiply by the bit index, then sum it all up.

---

So, I started with the slightly different case "index of *the* least significant set bit" (LSSB), because it's always best to start simple when looking for patterns... I plotted the index of the LSSB for numbers \[0..40\]:

```
          1111111111222222222233333333334
01234567890123456789012345678901234567890
-0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   =  2k + 1
  1   1   1   1   1   1   1   1   1   1    =  4k + 2
    2       2       2       2       2      =  8k + 4
        3               3               3  = 16k + 8
                4
                                5

```

(Here, `-` means N/A.) Well, that's a very obvious pattern. Joining the cases together we get `2^v * (2k + 1)` for row `v`, for integers `k` (or, `2^v * m` for odd `m`, if you prefer). This is sequence A007814 in OEIS.

Okay, so, back to our real case of the *second* least significant set bit (2LSSB). Let's do a similar plot for this case and see if there's any pattern here too, and if so, how it relates to the previous pattern.

```
          1111111111222222222233333333334
01234567890123456789012345678901234567890
--- -   -       -               -
   1   1   1   1   1   1   1   1   1   1
     22      22      22      22      22
         33 3            33 3
                 44 4   4
                                 55 5   5

```

Well... huh. That looks a bit strange, but there's still some sort of repetition going on. Let's take a look at what numbers get assigned which indices.

```
0: 0 1 2 4 8 16 32             ...  2^k
1: 3 7 11 15 19 23 27 31 35 39 ...  4k +  2 + {1}           =  2*(2k + 1) + 2^{0}
2: 5 6 13 14 21 22 29 30 37 38 ...  8k +  4 + {1,2}         =  4*(2k + 1) + 2^{0,1}
3: 9 10 12 25 26 28            ... 16k +  8 + {1,2,4}       =  8*(2k + 1) + 2^{0,1,2}
4: 17 18 20 24                 ..? 32k + 16 + {1,2,4,8}     = 16*(2k + 1) + 2^{0,1,2,3}
5: 33 34 36 40                 ..? 64k + 32 + {1,2,4,8,16}  = 32*(2k + 1) + 2^{0,1,2,3,4}

```

Okay, yeah, definitely a pattern. The general case here is `2^v * (2k + 1) + 2^j`, `j < v`. While we're at it, let's do one more just to see how this all generalises for the n:th least significant set bit.

```
                                                                                111111111111111111111111111111
          111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999000000000011111111112222222222
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
 01 012 4       012 4   8      16                               012 4   8      16              32   ...
  012   012 4   8               012 4   8      16              32                                   ...
------- --- -   --- -   -       --- -   -       -               --- -   -       -               -                                       =   2^k + 2^l, l < k                                 0
                                                                                1
       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2        =   8*k +  4 + {3}                                   2
           3 33            3 33            3 33            3 33            3 33            3 33            3 33            3 33         =  16*k +  8 + {3,5,6}                               3
                   4 44  44 4                      4 44  44 4                      4 44  44 4                      4 44  44 4           =  32*k + 16 + {3,5,6,9,10,12}                       4
                                   5 55  55 5    55 5   5                                          5 55  55 5    55 5   5               =  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
                                                                   6 66  66 6    66 6   6        66 6   6       6                       = 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

```

Phew. 40 digits didn't cut it for finding patterns here, so I had to extend it a bit. Sorry about that horizontal scrollbar. Here's the table to the far right again, to spare you from having to scroll back and forth.

```
   2^k + 2^l, l < k                                 0
                                                    1
   8*k +  4 + {3}                                   2
  16*k +  8 + {3,5,6}                               3
  32*k + 16 + {3,5,6,9,10,12}                       4
  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

```

Huh. That's weird, what are *those* numbers? They're certainly not powers of two... maybe I should've been able to guess it from the earlier two tables, but instead I went to OEIS and found it's actually the set of sums of two distinct powers of two. So it seems like a qualified guess to generalise this by taking the sum of `n` distinct powers of two for the index of the n:th least significant set bit. All in all, the final expression looks like so:

# Answer
> 1 votes
## Ruby, 64

Here's a regex-based solution. I hope it's correct, the spec could use some test cases...

```
p (0..gets.to_i).inject{|s,n|n.to_s(2)=~/10*10*$/?s+$&.size-1:s}

```

Examples:

```
>echo 3 | ruby sum-of-indices.rb
1
>echo 7 | ruby sum-of-indices.rb
6
>echo 10 | ruby sum-of-indices.rb
12
>echo 500 | ruby sum-of-indices.rb
1410

```

# Answer
> 0 votes
## **Postscript**, 179

Not to compete in golf, just for fun. I like it, that `1`'s indexes (which are *post-match* lengths in a string scanned left to right starting with *most* significant bits) are accumulated on stack and so to find second least significant, one operand is popped, next added to sum, the rest are discarded (stack cleared).

```
/s 0 def 0 1(%stdin)(r)file token pop {2 32 string cvrs mark exch {(1)search{pop pop dup}{pop exit}ifelse}loop counttomark 2 ge{pop length s add/s exch def}if cleartomark}for s =

```

Un-golfed, and with timer attached:

```
/s 0 def
0 1
(%stdin) (r) file
token pop
realtime 4 1 roll
{
    2 32 string cvrs
    mark exch
    {
        (1) search
        {pop pop dup}{pop exit}ifelse
    } loop
    counttomark 2 ge {pop length s add /s exch def} if
    cleartomark
} for
s =
realtime
(Time elapsed, s: )=
exch sub 1000 div =

```

And:

```
echo 10 | gs -q -dBATCH sum.ps
12
Time elapsed, s:
0.0

echo 500 | gs -q -dBATCH sum.ps
1410
Time elapsed, s:
0.0

echo 1000000 | gs -q -dBATCH sum.ps
2999655
Time elapsed, s:
3.218

```

# Answer
> 0 votes
# Smalltalk (Smalltalk/X) (105 chars)

```
(0 to:20)
    injectAndCollect:0
    into:[:sumSoFar :n |
            sumSoFar +
            (([(n clearBit:n lowBit) lowBit] ifError:0) - 1 max:0)
         ]

```

-\> 0 0 0 1 1 3 5 6 6 9 12 13 16 18 20 21 21 25 29 30 34

injectAndCollect:into: is not part of Ansi Smalltalk, though.

# Answer
> 0 votes
# JavaScript, 69 68

```
for(s=k=prompt(r=0);k--;r=k&k+1)for(s-=!r;r*!(r&2);r/=2)s++;alert(s)

```

The approach is to strip the lowest bit (the result is stored in `r`) then count the trailing zeroes.

*Longer alternate, 79 chars*

```
for(k=prompt(s=0);k--;s+=/.(0*)$/.exec((k&k+1).toString(2))[1].length);alert(s)

```

The takes the `r` from above, converts it to a binary string, and uses a regular expression to count the trailing zeroes. I include it because I like the idea of doing the counting with string processing.

# Answer
> 0 votes
## 32-bit x86 assembly code, 22 bytes

Accepts input in ecx register, output is in eax register.

```
00000000 33 c0    xor   eax, eax
00000002 e3 11    jecxz 00000015
00000004 51       push  ecx
00000005 0f bc d1 bsf   edx, ecx
00000008 0f b3 d1 btr   ecx, edx
0000000B 0f bc d1 bsf   edx, ecx
0000000E 74 02    je    00000012
00000010 03 c2    add   eax, edx
00000012 59       pop   ecx
00000013 e2 ef    loop  00000004
00000015 c3       ret
```

---
Tags: code-golf
---


title: Garden architecture - ASCII style

text:
# Question
Title: Garden architecture - ASCII style
We have a square 10x10 meter garden outside our house. We want to plant grass and make a terrace. We have decided *how* to divide the garden, but we haven't decided the ratio between amount of grass vs terrace.

We need help visualizing it, and ASCII-art is clearly the best way to do so.

---

### Challenge:

Take an integer in the inclusive range **\[0, 100\]** (or optionally decimal \[0, 1\]) representing how many percent of the garden should be terrace.

One square meter of terrace will be represented by either a dash `-` or a bar `|`. One square meter of grass will be represented by a hash mark `#`.

* If the amount of terrace is less than or equal to 50%, then the garden should be covered with bars, starting in the bottom left corner, and fill vertically, then horizontally.
* If the amount of terrace is more than 50% then we want the decking to be the other way (dashes instead of bars), and starting in the bottom left corner, and fill horizontally, then vertically.

**Examples:**

```
N = 25%
||########
||########
||########
||########
||########
|||#######
|||#######
|||#######
|||#######
|||#######

N = 75%
##########
##########
-----#####
----------
----------
----------
----------
----------
----------
----------

N = 47%
||||######
||||######
||||######
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####

N = 50%
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####
|||||#####

N = 51%
##########
##########
##########
##########
-#########
----------
----------
----------
----------
----------

N = 0%
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

N = 100%
----------
----------
----------
----------
----------
----------
----------
----------
----------
----------

```

This is so the shortest code in bytes win. Standard rules regarding I/O. This is ASCII-art, so the output should look like the examples above. I.e. outputting `["|", "|" ...]` is not OK.

Explanations are encouraged as always :)

# Answer
> 7 votes
# APL (Dyalog), 34 bytes

Anonymous prefix function expecting integer in range 0–100. Assumes `⎕IO` (**I**ndex **O**rigin) to be `0`, which is default on many systems.

```
{'#-|'[⊖⍉⍣s⊢10 10⍴100↑⍵⍴1+s←50≥⍵]}

```

Try it online!

`{``}` lambda;  is argument:

`'#-|[``]` index the string with the following array:

`50≥⍵` 1 if 50 is greater than or equal to argument, else 0

`s←` store in s (for **s**mall)

`1+` increment

`⍵⍴` cyclically **r**eshape to argument-length

`100↑` take the first hundred of that, padding with zeros

`10 10⍴`**r**eshape to ten rows and ten columns

yield that (separates `s` from `10 10`)

`⍉⍣s` transpose if small

flip upside-down

# Answer
> 5 votes
# , 39, 38 37 bytes

```
[:|.>&50|:'#-|'"0{~_10]\100{.]$1+51>]

```

How it works:

```
                     _10]\100{.]$1+51>] - prepares a 10x10 array of 0, 1 or 2
                                 1+51>] - 1 if N<=50 otherwise 2
                               ]$       - list of N copies of the above (1 or 2)
                          100{.         - the above list filled to 100 items with 0
                     _10]\              - reshape the list to a 10x10 array
           '#-|'"0                      - constant array of chars
                   {~                   - replaces each digit 0, 1 or 2 with #, - or |
     >&50                               - is N>50 ?
         |:                             - if not, transpose the array
                                          (in fact |: here is rearrange axes
                                           0 - transpose
                                           1 - leave it intact)
 |.@                                    - reverse the order ot the rows

```

Try it online!

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

Takes input as an integer in **\[0...100\]**.

```
n=>(y=9,g=x=>~y?'|-#'[[x,y][k=n/51|0]*9+x+y<n?k:2]+[`
`[x-9]]+g(x++-9?x:!y--):'')(0)

```

### Test cases

```
let f =

n=>(y=9,g=x=>~y?'|-#'[[x,y][k=n/51|0]*9+x+y<n?k:2]+[`
`[x-9]]+g(x++-9?x:!y--):'')(0)

;[25, 75, 47, 50, 51, 0, 100]
.forEach(n => O.innerText += n + '%:\n' + f(n) + '\n')
```

```
<pre id=O></pre>
```

### Formatted and commented

```
n => (                          // given the terrace percentage n
  y = 9,                        // and starting with y = 9
  g = x =>                      // g = recursive function taking x:
    ~y ?                        //   if y is greater than or equal to 0:
      '|-#'[                    //     pick the relevant character:
        [x, y][k = n / 51 | 0]  //       using k = 1 if n > 50, 0 otherwise
        * 9 + x + y             //       and comparing either 10 * x + y or 10 * y + x
        < n ?                   //       with n; if we're located over the terrace area:
          k                     //         append either '|' or '-'
        :                       //       else:
          2                     //         append '#'
      ] +                       //     end of character insertion
      [`\n`[x - 9]] +           //     append a linefeed if x == 9
      g(x++ - 9 ? x : !y--)     //     update (x, y) and do a recursive call
    :                           //   else:
      ''                        //     stop recursion
)(0)                            // initial call to g with x = 0

```

# Answer
> 4 votes
# Python 2, ~~121~~ ~~117~~ 116 bytes

```
def f(n):
 s=[('-|'[n<51]*n+'#'*100)[i*10:][:10]for i in range(10)]
 for l in[s,zip(*s)][n<51][::-1]:print''.join(l)

```

Try it online!

# Answer
> 4 votes
# Jelly, 23 bytes

```
<©51ị⁾|-ẋḷ"”#ẋ³¤s⁵Z®¡ṚY

```

Try it online!

Change the number before `Ç` in the footer to change the input. Works as a monadic link in a program without command-line arguments, which is allowed.

# Answer
> 3 votes
# MATL, 26 bytes

```
'|-#'100:i>~o10eG50>?!E]P)

```

Try it online! Or verify all test cases.

### Explanation

```
'|-#'     % Push this string
100:      % Push array [1 2 ... 100]
i         % Input a number and push it
>~        % Less than or equal (element-wise)? This transforms the
          % array into [true ... true false ... false]
o         % Convert to double. True becomes 1, false becomes 0
10e       % Rehaspe into 10-row matrix, in column-major order
G         % Push input
50>       % Greater than 50?
?         % If so
  !       %   Transpose
  E       %   Multiply by 2 (element-wise). So 0 remains as 0, and
          %   1 becomes 2
]         % End
P         % Flip vertically
)         % Index into string, modularly. So 1 corresponds to '|',
          % 2 to '-', and 0 to '#'
          % Implicitly display

```

# Answer
> 3 votes
# SWI Prolog, 249 bytes

```
p(X):-write(X).
r(X,Y,G):-G=<50,10*X-Y+1=<G,p('|').
r(_,_,G):-G=<50,p('#').
r(X,Y,G):-(10-Y)*10+X>G,p('#').
r(_,_,_):-p('-').
l(_,11,_):-nl.
l(X,Y,G):-r(Y,X,G),Z is Y+1,l(X,Z,G).
a(10,G):-l(10,1,G).
a(Y,G):-l(Y,1,G),Z is Y+1,a(Z,G).
s(G):-a(1,G),!.

```

The solution is pretty straightforward. Procedure `a` creates rows, `l` writes chars to columns in a row and `r` decides what character should be printed out.

# Answer
> 3 votes
# Python 2, 85 bytes

```
T=j=10
n=input()+T
while j:print([(n-j)/T*'|',min(n-T*j,T)*'-'][n>60]+'#'*T)[:T];j-=1

```

Try it online!

In both cases each line is padded on the right by `#` to length 10, which lets us share that code between the two cases. The number 10 was used often enough that aliasing `T=10` saved a decent number of bytes.

# Answer
> 2 votes
# Charcoal, 25 bytes

```
ＮθＧTχ#↶Ｆ÷θχ⟦χ⟧﹪θχ¿›θ⁵⁰‖Ｔ↖

```

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

```
Ｎθ                          Input integer into q
  Ｇ                         Draw filled polygon
   T                        Directions Right, Down, Left
    χ                       Size 10
     #                      Filled with `#`
      ↶                     Rotate cursor left (now points up)
       Ｆ÷θχ                 Repeat q/10 times (integer divide)
           ⟦χ⟧              Print 10 `|`s and move to the next column
              ﹪θχ           Print (q mod 10) `|`s
                 ¿›θ⁵⁰      If q > 50
                      ‖Ｔ↖   Reflect diagonally

```

# Answer
> 2 votes
# Ruby, ~~92~~ 82 bytes

```
->n{puts (r=0..9).map{|y|r.map{|x|n>(n>50?100-y*10+x:x*10+9-y)?"|-"[n/51]:?#}*''}}

```

Try it online!

## How it works:

Every cell in the grid has a progressive number starting from the bottom left corner and proceeding horizontally or vertically depending on the value of n:

If `n>50`, the number is `100-y*10+x` otherwise it's `x*10+9-y`

# Answer
> 2 votes
# Husk, 24 bytes

```
↔?T†▼'-≤50⁰S↑C10+R⁰'|∞'#

```

Try it online!

## Explanation

```
↔?T†▼'-≤50⁰S↑C10+R⁰'|∞'#  Input is a number, say n=12
                     ∞'#  Infinite string of #s: "#######...
                +         Prepend to it
                   '|     the character |
                 R⁰       repeated n times: "||||||||||||####...
             C10          Cut to pieces of length 10: ["||||||||||","||##########","##..
           S↑             Take first 10 pieces.
 ?     ≤50⁰               If n is at most 50,
  T                       then transpose,
   †▼'-                   else take minimum with '-' for each character.
↔                         Reverse, implicitly print separated by newlines.

```

# Answer
> 1 votes
# SOGL V0.12, 21 bytes

```
┐* #M*+Mm√H.M»>?H§┐┌ŗ

```

Try it Here!

Explanation:

```
┐*                     push a vertical bar repeated input times
   #M*                 push "#" repeated 100 times
      +                add the two together
       Mm              mold to a length of 100
         √             convert to a square
          H            rotate clockwise
           .M»>?       if the input is greater than 50
                H        rotate the array clockwise again
                 §       reverse it horizontally
                  ┐┌ŗ    replace "|" with "-"

```

# Answer
> 1 votes
# dc, <sub>~~210~~</sub> 197 bytes

```
[256r^1-255/]sx?dddI/dsT9r-sYI%ddIr-sqdsesm-I/sN[[lNlxx124*PIlN-lxx35*PIPlq1-dsq0<o]dsoxlN1+sNledsq0<oq]sJ50!<J[Ilxx35*PIPlY1-dsY0<E]sElY0<E[lmlxx45*PIlm-lxx35*PIP]sClTI>C[Ilxx45*PIPlT1-dsT0<Z]dsZx

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Classic), 33 bytes

```
f←{'#-|'[⊖(⍉+⍨)⍣(⍵≤50)⊢⍵>⍎¨∘.,⍨⎕d]}

```

Try it online!

based on Adám's answer

`⎕d` is the string `'0123456789'`

`∘.,` Cartesian product

with itself

`⍎¨` evaluate each - get a 10x10 matrix of 0..99

`⍵>` boolean matrix for where the argument  is greater

acts as separator

`(⍉+⍨)⍣(⍵≤50)` if ⍵≤50 double the matrix (`+` with itself) and transpose ()

vertical reverse

`'#-|'[ ]` index the string `'#-|'` with each element of the matrix

# Answer
> 1 votes
# , 51 bytes

```
{-1@'reverse$[i;::;flip]10 10#@[100#"#";til x;:;"|-"i:x>50];}

```

# Answer
> 1 votes
# Retina, ~~72~~ 62 bytes

```
.+
$*|
T`|`-`.{51,}
$
100$*#
M!10`.{10}
O$s`(?<!-.*)\S
$.%`
O`

```

Try it online! Link includes test cases. Edit: Saved 10 bytes with some help from @MartinEnder. Explanation:

```
.+
$*|

```

Repeat `|` the given number of times

```
T`|`-`.{51,}

```

But if the input was at least 51, change them to `-`s.

```
$
100$*#

```

Append 100 `#`s.

```
M!10`.{10}

```

Split into 10 groups of 10, discarding anything left over.

```
O$s`(?<!-.*)\S
$.%`

```

If the the input was at least 51, transpose the result.

```
O`

```

Sort the result.

Alternative solution, also 62 bytes:

```
.+
$*|
T`|`-`.{51,}
$
100$*#
M!10`.{10}
O`
O$^s`\S(?!.*-)
$.%`

```

Sorting before transposing allows a byte saving on the condition for the transposition but costs a byte to get the result in the correct order.

# Answer
> 0 votes
# Python 2, ~~106~~ 103 bytes

```
n=input();x=n>50;k=x*81+10
while k>0:s='';exec"s+='|-##'[x::2][n<k];k+=x or 10;"*10;print s;k+=x*81-101

```

Try it online!

# Answer
> 0 votes
# PHP, 119+1 bytes

```
$r=str_pad("",100,"#");for($x=50<$n=$argn;$n--;)$r[90+($x?$n%10*2-$n:$n/10-$n%10*10)]="|-"[$x];echo chunk_split($r,10);

```

Run as pipe with `-nR` or try it online.

# Answer
> 0 votes
# Jelly, 24 bytes

```
³<51
ȷ2Ḷ<s⁵ZḤ$Ç¡Ṛị“-|#”Y

```

Try it online!

## How it works

I use too many superscripts...

```
³<51 ~ Helper link.

³    ~ The input.
 <   ~ Is smaller than
  51 ~ 51?
     ~ Yields 1 for truthy, 0 for falsy.

ȷ2Ḷ<s⁵ZḤ$Ç¡Ṛị“-|#”Y ~ Main link.

ȷ2                  ~ 1e2 (i.e compressed 100).
  Ḷ                 ~ Lowered range. Yields [0, 100) ∩ ℤ.
   <                ~ Is smaller than the input? (element-wise).
    s⁵              ~ Split into sublists of length 10.
         Ç¡         ~ Repeat <last link as a monad> times (either 1 or 0 times).
      ZḤ$           ~ Zip (transpose) and unhalve element-wise.
           Ṛ        ~ Reverse.
            ị       ~ Modular, 1-based indexing into...
             “-|#”  ~ The literal string "-|#".
                  Y ~ Join by newlines.

```

# Answer
> 0 votes
# , 102 bytes

```
n=scan();m=matrix("#",y<-10,y);m[0:n]="if"(n<51,"|","-");write("if"(n>50,m[,y:1],t(m[y:1,])),"",y,,"")

```

Try it online!

Reads `n` from stdin and prints the garden to stdout.

Explanation:

```
n=scan()               # read from stdin
m=matrix("#",10,10)               # create 10x10 matrix of "#"
m[0:n]="if"(n<51,"|","-")         # set the first n entries in m to the appropriate character
m="if"(n>50,                      # prepare for printing using `write`
       m[,10:1],                  # reverse m left to right
       t(m[10:1,]))               # flip m top to bottom and transpose
write(m,"",10,,"")                # write m to stdout in 10 columns with no separator

```

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


title: Find the password

text:
# Question
Title: Find the password
An ordinary N-digit combination lock consists of N rotating discs. Each disc has digits 0-9 inscribed in order, and you need to turn them to the correct password to open it. Obviously, if you don't know the password, you will need to try at most 10N times before unlocking it. That's not interesting.

So let's consider a variant of combination lock, name it distance-revealing lock.

In every unsuccessful attempt to open an distance-revealing lock, it will respond the minimum number of movements to unlock.

One movement is defined as a rotation by one position, for example it needs 1 movement from `890` to `899`, and 9 movements from `137` to `952`.

# The Challenge

Given a distance-revealing lock with its password unknown, try to open the lock with a minimal number of **attempts** (not movements), while keeping the program from getting too long.

# Rules & Scorings

* You should write a full program which inputs from stdin and outputs to stdout. The program should do input/output as following:

```
Start
    Input an integer N (number of digits) from stdin
    Do
        Output a line containing decimal string of length N (your attempt) to stdout
        Input an integer K (response of the lock) from stdin
    While K not equal 0
End

```
* Your program should handle up to N = 200, and should run less than 5 seconds on any input.
* Leading zeros in output shouldn't be omitted.
* The are 5 testdata for every length, so the total number of testdata is 1000. The testdata are randomly generated.
* **The final score will be (total number of guesses in all testdata) * ln(code length in bytes + 50).** Lowest score wins. (ln is natural log)
* **I will score the program for you.** If you want to know how I will score your program, or you want to score it by yourselves, take a look at previous edits on this post.
* This challenge will end at 2017/12/07 14:00 UTC. I will post my solution then.

# Running Example

Lines starting with `>` represent input, and others represent program output.

**You can have a password in your mind and interact with your program to test it.**

```
> 3   # 3-digit lock. The hidden password is 746
000   # 1st guess (by program)
> 11  # response to the 1st guess
555   # 2nd guess
> 4   # ...
755
> 2
735
> 2
744
> 2
746   # finally the correct answer! The program attempts 6 times.
> 0   # this is not necessary

```

# Sample Program

**EDIT:** Maybe the input/output format above was not clear. Here's a sample program in Python.

**Python, 369 bytes, total number of attempts = 1005973, score = 6073935**

```
import sys

N = int(input()) # get the lock size

ans = ''
for i in range(N): # for each digit
    lst = []
    for j in range(10): # try all numbers
        print('0' * i + str(j) + '0' * (N - i - 1)) # make a guess
        result = int(input()) # receive the response
        lst.append(result)
    ans += str(lst.index(min(lst)))
print(ans) # output the final answer

```

*Thanks to Jonah for simplifying the challenge.*

# Answer
# C, ~~388~~ ~~374~~ 368 bytes, total attempts = 162751, score = 982280

```
char s[999];i;G;H;t;n;h;e;R(x){scanf("%d",x);}W(i,x,a){printf((i-n?0:4)+"%0*d%0*d\n",i,x,n-i,0);R(a);}S(k,i){if(!(t=e=k>4?s[i]=48:k<1?s[i]=53:!G?H=k,G=i:0)){for(;t++<n;)putchar(48|t==i|t==G);puts("");R(&t);t==h?W(G,e=1,&t):0;s[G]=t>h?53+H:53-H,s[i]=t>h^e?53+k:53-k;G=0;}}main(){R(&n);for(W(n,0,&h);i++<n;S(t-h+5>>1,i))W(i,5,&t);s[G]=53+H,puts(s+1),s[G]=53-H,puts(s+1);}

```
> 3 votes

# Answer
# C# (.NET Core), 617 bytes, total attempts = 182255, score = 1185166

```
using System;namespace p{class C{static void Main(){var l=Console.ReadLine();int L=int.Parse(l);var g=new int[L];var p=n(g);for(int i=0;i<L;i++){g[i]=5;var d=n(g);var f=d-p;var s=f;switch(s){case 5:g[i]=0;d-=5;break;case-5:break;case 3:g[i]=1;d=n(g);f=d-p;if(f>0){g[i]=9;d-=2;}break;case 1:g[i]=2;d=n(g);f=d-p;if(f>0){g[i]=8;d-=4;}break;case-1:g[i]=3;d=n(g);f=d-p;if(f>0){g[i]=7;d-=4;}break;case-3:g[i]=4;d=n(g);f=d-p;if(f>-3){g[i]=6;d-=2;}break;}p=d;}n(g);}static int n(int[] g){foreach(var i in g){Console.Write(i);}Console.WriteLine();var s=Console.ReadLine();var d=int.Parse(s);if(d<1) Environment.Exit(0);return d;}}}

```

Hopefully C# in this format works for you. It is in the form of a complete program, so there should be a way to compile to an executable. Let me know if there's anything I can do to make it easier. Bytes are part of the scoring even though the Code Golf tag is removed so my official submission removes all the unneeded whitespace and useful names. My explanation below will use fragments of the ungolfed code:

### Explanation

This program uses only a single helper method:

```
static int newGuess(IEnumerable<int> guess)
        {
            foreach (var item in guess)
            {
                Console.Write(item);
            }
            Console.WriteLine();
            var distanceString = Console.ReadLine();
            var distance = int.Parse(distanceString);
            if (distance < 1) System.Environment.Exit(0);
            return distance;
        }

```

This writes the guess to stdout, then reads the distance from stdin. It also immediately ends the program if a guess is the exact combination. I call it a lot. Next the initial setup:

```
var lengthString = Console.ReadLine();
int length = int.Parse(l);
var guess = new int[length];
var prevDistance = newGuess(guess);

```

This gets the length of the combination, then starts guessing with all 0s. Afterwards, it iterates through each digit in a `for` loop.

```
guess[i] = 5;
var distance = newGuess(guess);
var difference = distance - prevDistance;
var switchVar = difference;
switch (switchVar)

```

For each digit, it guesses 5, then decides on the next step based on how the distance changed since the previous guess (where that digit was 0).

```
case 5:
    guess[i] = 0;
    distance -= 5;
    break;

```

If the distance increased by 5, then 0 was correct for that distance. Adjust that digit back to 0. Altering the recorded distance manually prevents an extra guess.

```
case -5:
    break;

```

If the distance decreased by 5, then 5 is the correct digit and we move to the next digit immediately.

After that things are tricky. Using `5` and `0` for my initial guesses means that the remaining difference possibilities are `3, 1, -1, -3` with 2 possibilities for each, which need 1 additional guess to distinguish. Each of these cases takes a similar form

```
case 3:
    guess[i] = 1;
    distance = newGuess(guess);
    difference = distance - prevDistance;
    if (difference > 0)
    {
        guess[i] = 9;
        distance -= 2;
    }

```

Some of the numbers change, but essentially we try one of the two possibilities, and check whether the change was the correct one for that digit. If it wasn't, then the other digit is correct so we set that digit then adjust the difference manually.

This method means we should require, at most, 1 guess for the initial 0s, 2 guesses per digit, and then 1 final guess to ensure the last digit doesn't fall through.

~~It might be buggy though, it works as far as I've checked manually but that's no guarantee.~~ Bug found and squashed thanks to Colera Su
> 3 votes

# Answer
# Python 2 and 3: 175 bytes, total attempts = 1005972, score = 5448445

This program takes ceil(log(n))\*10 attempts per combination or every single digit takes 10 attempts (so, `333` takes 30 attempts).

```
N=int(input());o=0
def c(a):
 print("0"*(N-len(str(a)))+str(a))
 return int(input())
for j in range(N):m={c(i):i for i in reversed(range(0,10**(j+1),10**j))};o+=m[min(m)]
c(o)

```

Huge thanks to Colera Su for helping me with the input/output functionality.

# Python Version of Challenge (Modified by OP).

I wrote a version of the lock code inside of Python. You can go ahead and use if you're trying to solve this in Python (like me). The following works in Python 2 and 3. It made a lot more sense just to implement lock as a class you can test against and I decided to create a generator function for guessing the inputs.

```
import sys

class Lock:
    def __init__(self, number):
        self.lock = str(number)
    def l(self): #lengthOfNumber
        return len(self.lock)
    def c(self, guess): #check a guess
        guess = str(guess)
        guess = "0" * (len(self.lock) - len(guess)) + guess
        difference = 0
        for i in range(len(self.lock)):
            d1 = abs(int(self.lock[i]) - int(guess[i]))
            d2 = 10 - d1
            difference += d1 if d1 < d2 else d2
        return difference

def masterLock():
    testdata = ["000","555","755","735","744","746"]
    for answer in testdata:
        yield Lock(answer)

class LockIO:
    def __init__(self):
        self.lock = int(input())
    def l(self):
        return self.lock
    def c(self, guess):
        guess = str(guess)
        guess = "0" * (self.lock - len(guess)) + guess
        print(guess)
        sys.stdout.flush()
        return int(input())

for l in masterLock():
    # Write your code here that tries to guess it
    #   When you're done testing you can unindent your code,
    #   replace "for l in masterLock():" with "l = LockIO()"
    #   and submit the code.
    #
    # Examples:
    #  l.l()      # returns the length of the lock
    #  l.c("952") # returns the distance to the lock
    #  l.c(952)   #  number also works
    pass

```
> 2 votes

# Answer
# , ~~277 bytes (score=1175356)~~ 258 bytes, total attempts = 202999, score = 1163205

```
f=file("stdin","r")
w=function(b=1,A=X){cat(A,"\n",sep="");if(b){b=scan(f,n=1)};b}
M=0:9
s1=c(-5,-3,-1,1,3,5,3,1,-1,-3)
s2=s1+rep(c(1,-1),,,5)
L=w(1,"")
X=S=rep(0,L)
v0=w()
for(i in 1:L){X[i]=5
v1=v0-w()
X[i]=4
v2=v0-w()
S[i]=M[s1==v1&s2==v2]
X=0*S}
b=w(0,S)

```

Try it online!

Stdin-stdout version, as requested by the OP, no boilerplates. Thanks to Colera Su for fixing an initial bug. This is a marginally shorter version than the one in the comments.

---

Here below the TIO submission to run a batch of tests within TIO

# , 189 bytes

```
M=0:9
s1=c(-5,-3,-1,1,3,5,3,1,-1,-3)
s2=c(-4,-2,0,2,4,4,2,0,-2,-4)
f=function(L){S=rep(0,L)
v0=v(S)
X=S
for(i in c(1:L)){X[i]=5
v1=v0-v(X)
X[i]=4
v2=v0-v(X)
S[i]=M[s1==v1&s2==v2]
X[i]=0}
S}

```

Try it online!

Let's consider a vector of zeros as the initial guess. Let's call V the distance between the current guess and the solution. For each position you only need to check the changes in V when you replace 0 with 5 and with 4. In fact, the differences between changing 0 with 5 are listed in my vector s1. The differences between changing 0 with 4 are listed in my vector s2. As you see these two vectors uniquely map the digits of the solution.

The total number of tests is thus ~~3\*L~~ 2\*L + 1, where L is the length of the code: an initial check against all zeros, then two checks for each digit, one against 5 and one against 4.

The improvement from a factor 3 to a factor 2 was inspired by Kamil Drakari's submission.

The rest of the TIO submission is boilerplate for R. The TIO submission showcases the running time and the total number of operations for 1000 runs with L=1...200, 5 replicates for each value of L.
> 2 votes

---
Tags: code-challenge, atomic-code-golf
---


title: Basic sort, with annoying bug

text:
# Question
Title: Basic sort, with annoying bug
Your input is a list/sequence/vector/array of 5-255 positive integers, not necessarily unique. You may assume whatever input format is most suitable, and that each integer (as well as the quantity of integers) is chosen uniformly at random from the range 5-255.

The goal is to output the same list, in the same (or equivalent) format, but sorted into increasing (nondecreasing) order. A common early exercise in learning a language. Submissions to include:

1. An answer which works correctly and achieves the goal; and
2. A second answer which contains an annoying bug. Between 1% and 10% of the time, the output needs to be a list in the correct format and containing the correct elements, but *in the wrong order* (any order except correctly sorted). The rest of the time, the program must work correctly and achieve the goal.

The two answers must have Levenshtein distance one; that is, we can get one from the other by deleting one byte, or adding one byte, or changing one byte.

Scoring as usual in code-golf (based on the shorter of your two answers), with usual loopholes forbidden.

10% bonus (decrease to score) if the annoying bug is input-independent, i.e. using the same input again doesn't reproduce the bug (except between 1% and 10% of the time).

# Answer
# Python 3, 36 bytes

## Bug-free version, 37 bytes

```
lambda l:sorted(l,reverse=l[-9:]==[])

```

Try it online!

## Annoying version, 36 bytes

```
lambda l:sorted(l,reverse=l[9:]==[])

```

Try it online!

This depends on the input and therefore does not qualify for the bonus.
It has a probability of around 2% to fail. It fails when the input length is lower then 10.

Combined with LyricLy's answer this gets 34 bytes:

```
lambda l:sorted(l)[::l[9:]>[]or 1]
lambda l:sorted(l)[::l[9:]>[]or-1]

```
> 9 votes

# Answer
# 05AB1E, 5\*0.9 = 4.5 bytes

**Working solution**

```
{TLΩi

```

Try it online!

**Explanation**

```
{      # sort input
 TL    # push the range [1 ... 10]
   Ω   # pick a random number in the range
    i  # if true (equal to 1), do nothing

```

**Solution containing the bug**

Gives the wrong solution 10% of the time (independent on input).

```
{TLΩiR

```

Try it online!

**Explanation**

Same as the working solution, except it reverses the list if the number picked is true.
> 9 votes

# Answer
# Jelly, 7 * (100% - 10%) = 6.3 bytes

```
Ṣ¹⁵X:¤¡

```

Try it online!

Buggy version:

```
ṢẊ⁵X:¤¡

```

Try it online!

In both links, there's a test harness that will run the code 100 times, each time with the list you give as the argument, and then return the results.

The probability of each input length is:

```
0.1 - 0.1/(length!)

```

So for length 1 there's a 0% probability, for length 2 5%, for length 3 8.83̅%, for length 4 9.583̅% etc. until length ∞ which has a 10% probability.
> 7 votes

# Answer
# Python 3, score ~~58~~ 57 - 10% = 51.3

Saved a byte thanks to ovs.

### Bug-free version, 57 bytes

```
lambda m:sorted(m)[::random()>.1or 1]
from random import*

```

Try it online!

### Bugged version, 57 bytes

```
lambda m:sorted(m)[::random()>.1or-1]
from random import*

```

Try it online!

I decided to try a solution that uses the bonus. It doesn't beat the other Python answer, but I had fun thinking it up.
> 6 votes

# Answer
# C, 71\*0.9 = 63.9 bytes

**Bug-free:**

```
c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%1<9)qsort(a,n,4,c);}

```

Try it online!

**Buggy:**

```
c(int*a,int*b){return*a-*b;}f(a,n)int*a;{if(rand()%10<9)qsort(a,n,4,c);}

```

Try it online!
> 5 votes

# Answer
# Groovy, 31 bytes

**Bugged solution:**

```
{a->a.sort()[a[9]?0..-1:-1..0]}

```

**Working solution:**

```
{a->a.sort()[a[0]?0..-1:-1..0]}

```

The Groovy subscript operator (the `getAt` method) returns null for lists if the index is bigger than the size. So if there's a ninth element it'll stay the same as the sorted list, but if not (1.99203187% chance) it'll be reversed. However there will always be a first element because the list's size is always bigger than or equal to 5. So the 0 in `a[0]` could be swapped with 1, 2, 3 or 4.
> 4 votes

# Answer
# Pyth, score 8 * 0.9 = 7.2

First snippet (correct one):

```
h.uSNT.S

```

**Try it here!**

Second snippet (bugged one):

```
O.uSNT.S

```

**Try it here!**

Saved two bytes (and 1.8 score) thanks to isaacg!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 29 bytes

This is 26.1 bytes with the bonus, but I'm not entirely sure I earn the bonus; on already-sorted input, both versions always produce sorted output.

## Bug-free version (29 bytes)

```
If[RandomReal[]<0.,#,Sort@#]&

```

Try it online!

## Annoying version (30 bytes)

```
If[RandomReal[]<0.1,#,Sort@#]&

```

Try it online!
> 3 votes

# Answer
# PHP, 70 bytes

## Bug-free version, 70 bytes

```
<?unset($argv[0]);((rand(1,9)?"":r).sort)($argv);echo join(" ",$argv);

```

Try it online!

## Bugged version, 70 bytes

```
<?unset($argv[0]);((rand(0,9)?"":r).sort)($argv);echo join(" ",$argv);

```

Try it online!

The bugged version sorts in reverse order 10% of the time (based on a random number generator).
> 3 votes

# Answer
# Python 2, 26 bytes

Buggy:

```
lambda l:l[9:]and l.sort()

```

Try it online!

Outputs by modifying the input list. Sorts the list only if its length is at least 10. The non-buggy version replaces the `9` with a `0` to always sort.

Working:

```
lambda l:l[0:]and l.sort()

```

Try it online!

We can modify the function to return the list at the cost of 4 bytes, for 30 bytes total:

```
lambda l:l[9:]and l.sort()or l

```

Try it online!

---

25 bytes with some stretches of the rules:

```
[list,sorted][id(0)%17>0]

```

Try it online!

Outputs a function literal that either sorts or is the identity, using `id(0)` as a random source. Change `>` to `>=` to fix, or `0` to `~0`.
> 3 votes

# Answer
# Husk, 6 bytes

Buggy version:

```
?OIV¦9

```

Try it online!

Correct version:

```
?OIVK9

```

Try it online!

## Explanation

These programs are completely deterministic. In fact, Husk has currently no support at all for random numbers.

```
?  V    If any element
    ¦9  is divisible by 9 (in buggy version),
    K9  is truthy when replaced by 9 (in correct version),
 O      sort the list,
  I     otherwise return it unchanged.

```

I claim that the output of the buggy program is not sorted with a probability between 1% and 2%. Denote by **N = 251** the number of possible values of the elements. The probability that a random list of length **L** contains no multiples of 9 is **((N-K)/N)^L**, where **K** is the number of values divisible by 9 (in our case **K = 28**). The total probability is the average of this for **5 ≤ L ≤ 255**, which is about 1.98%. Some of these lists are false positives, since they are already sorted. The probability of a random list of length **L** to be sorted is at most **((N+N\*(N-1)/2)/N^2)^⌊L/2⌋**: if we break the list into chunks of length 2, each of the **⌊L/2⌋** chunks must be sorted. The total probability of a list being sorted is bounded by the average of the above for **5 ≤ L ≤ 255**, which is about 0.30%. Thus the probability of the function returning a non-sorted list is between 1.67% and 1.98%.
> 3 votes

# Answer
# Bash, 26 bytes

## Correct version

```
s=n
sort -${s:RANDOM%20<0}

```

Try it online! or check the probabilities.

## Bugged version

```
s=n
sort -${s:RANDOM%20<1}

```

Try it online! or check the probabilities.

Takes input as newline-separated numbers. Uses the builtin variable `RANDOM`, which always returns a (pseudo)random number in the range 0 - 32767. Using `%20` results in about a 5% failure rate (thanks @Titus for clarifying issues with `%10`).

This randomness means the failure rate is independent of the input, but this does require that the input array includes at least one number with more than one digit, because the failure output is sorted lexicographically.

## Alternate version, 27 bytes

```
((RANDOM+20))||cat&&sort -n

```

Bugged version replaces the `+` with a `%`. Try it online or try it bugged.
> 3 votes

# Answer
## JavaScript (ES6), 24 bytes

Bug-free version (at least for integers in the range 0-2147483647, so anything in the given range):

```
a=>a.sort((a,b)=>a-b>>0)

```

Buggy version:

```
a=>a.sort((a,b)=>a-b>>1)

```

Depends on a) the engine's sorting algorithm and b) the input list containing two values in the wrong order that differ by 1. (If the probability of that turns out to be too low then the `1` can be increased, but by the time you get to `8` it simply won't sort anything in the range `5-255`.)
> 2 votes

# Answer
# MATL, ~~7\*0.9 = 6.3~~ 6\*0.9 = 5.4 bytes

Buggy version:

```
Gr.9<?S

```

Try it online!

**Explanation:**

```
G        % Grab input
 r       % Push a random number between 0 and 1
  .9     % Push 0.9
    <    % Check if the random number is smaller than 0.9
     ?   % If true
      S  % Sort input
         % Implicit output

```

Bug-free version:

```
Gr9<?S

```

Try it online!

**Explanation:**

```
G       % Grab input
 r      % Push a random number between 0 and 1
  9     % Push 9
   <    % Check if the random number is smaller than 9 (always true)
    ?   % If true
     S  % Sort the input
        % Implicit output

```
> 2 votes

# Answer
# PHP, 62 bytes

inspired by Jo´s solution (and I just noticed: it´s a port of Justin Mariner´s):

working (sorts ascending):

```
unset($argv[0]);(r[rand()+20].sort)($argv);echo join(_,$argv);

```

buggy (approx. 5% chance of descending sort):

```
unset($argv[0]);(r[rand()%20].sort)($argv);echo join(_,$argv);

```

Run with `-nr`
> 2 votes

# Answer
# Pushy, 9 bytes - 10% = 8.1

**Bugged Solution:**

```
g0TUn?};_

```

**Try it online!**

**Working Solution:**

```
g1TUn?};_

```

**Try it online!**

The bugged code does the following:

```
g0TUn?};_

g          \ Sort the stack correctly
 0TU       \ Generate random(0, 10)
    n? ;   \ If this is zero:
      }    \    Cyclically shift the stack right once
        _  \ Print the result

```

The fixed code simply changes `0` to `1`. As `random(1, 10)` will never be `0`, the if statement will never be executed.
> 2 votes

# Answer
# Octave, 36\*0.9 = 32.4 bytes

Buggy version:

```
@(x)sort(x)(shift(1:end,+(rand<.1)))

```

Try it online!

Bug-free version:

```
@(x)sort(x)(shift(1:end,+(rand<.0)))

```

Try it online!

This sorts the vector, then shifts all numbers one to the right if a random number is less than 0.1.
> 1 votes

# Answer
# Jq 1.5, 42 bytes

Buggy

```
sort|if length%13<=0then reverse else. end

```

Working (delete the =)

```
sort|if length%13<0then reverse else. end

```

Assuming line lengths are uniform in range \[5,255\] about 7% will trigger the bug

Try it online!
> 1 votes

# Answer
# J, 22.5 bytes (25 bytes - 10%)

### with bug:

```
[:]`(1&A.)@.(0.1>?@0:)/:~

```

### without bug:

```
[:]`(0&A.)@.(0.1>?@0:)/:~

```

Try it online!
> 1 votes

# Answer
# , 30\*.9 = 27 bytes

(buggy)

```
function(l)sort(l,runif(1)<.1)

```

Try it online!

(not buggy)

```
function(l)sort(l,runif(1)<.0)

```

The buggy version sorts in `decreasing=T` 10% of the time, sampling from a uniform(0,1) distribution. The un-buggy version is always `decreasing=F`
> 1 votes

# Answer
# Röda, 42 bytes - 10% = 37.8

Bug-free:

```
{sort key={|i|currentTime|[_%20//19*0+i]}}

```

Buggy:

```
{sort key={|i|currentTime|[_%20//19*i+i]}}

```

Try it online!

This uses the `currentTime` function to create random numbers. It seems that their distribution varies a little between machines. The ratio `20//19` can be adjusted to get different results for no byte penalty (unless it is smaller than `99//98`).
> 1 votes

# Answer
# Java 8, ~~45~~ 34.2 (~~50~~ 38 - 10%) bytes

**Normal version:**

```
a->{if(Math.random()>0.)a.sort(null);}

```

**Explanation:**

Try it here.

```
a->{                    // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.)  //  If the random 0-1 double is larger than 0:
    a.sort(null);       //   Sort the input-List
}                       // End of method

```

---

**Bugged version (~~51~~ 39 bytes):**

```
a->{if(Math.random()>0.1)a.sort(null);}

```

LD of 1: `1` added.

**Explanation:**

Try it here.

```
a->{                     // Method with ArrayList<Integer> parameter and no return-type
  if(Math.random()>0.1)  //  If the random 0-1 double is larger than 0.1:
    a.sort(null);        //   Sort the input-List
}                        // End of method

```
> 1 votes

# Answer
JavaScript, 25\*0.9=22.5

```
new Date%25?x:x.sort()

```

input x
> 0 votes

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


# Question
Title: Compute the result of an equation, but with selectable operator precedence
Forget BIDMAS! Write a program that takes an equation *and* an operator precedence order, and prints the result.

Example input format:

```
1.2+3.4*5.6/7.8-9.0 */+-

```

Rules & guidelines:

* The only operators that are defined are addition (+), subtraction (-), multiplication (\*), and division (/). No parentheses, no exponentiation.
* Associativity is always left-to-right. For example, `10/4/2` is to be interpreted as `(10/4)/2` with a result of 1.25, rather than `10/(4/2)`.
* The input format is as follows:
    + An equation, followed by a space, followed by the operator precedence specification (or two string arguments, one for the equation and the other for the precedence).
    + The equation comprises base-10 decimal numbers separated by operators, with no spaces. Integer values do not have to contain a period character, i.e. both `5` and `5.0` are to be accepted values.
    + For simplicity, negative numbers may not be included in the input, e.g. `6/3` is valid but `6/-3` is not. Input also may not contain a leading or trailing operator, so `-6/3` isn't considered valid, nor is `6-3+`.
    + The precedence specification string is always 4 characters long and always contains the characters `+`, `-`, `/`, and `*` once each. Precedence is read as left-to-right, e.g. `*/+-` specifies multiplication with the highest precedence, division next, then addition, and finally subtraction. **EDIT:** It is acceptable to take the precedence string in reverse order (lowest to highest) as long as you specify this in your answer.
* Input is a string to be taken via command line arguments, STDIN, or the default input format in programming languages that do not support these input methods.
* You are free to assume that the given input will be in the correct format.
* Output is via STDOUT or your language's normal output method.
* The printed result should be in base-10 decimal.
* Results must be computed to at least 4 decimal points of accuracy when compared to a correct implementation that uses double precision (64-bit) floating point arithmetic. This degree of freedom is designed to allow for the use of fixed-point arithmetic in languages that have no floating-point support.
* Divide by zero, overflow, and underflow are undefined behaviour. Your code is free to assume that no inputs will be given that will trigger these cases.
* You may not call out to any external services (e.g. Wolfram Alpha)
* You may not call out to any programs whose primary function is to solve these types of problems.

Test cases:

1. `6.3*7.8` followed by any operator precedence specification prints 49.14
2. `2.2*3.3+9.9/8.8-1.1 */+-` is parsed as `((2.2*3.3)+(9.9/8.8))-1.1` and should print 7.285
3. `2.2*3.3+9.9/8.8-1.1 +*/-` is parsed as `((2.2*(3.3+9.9))/8.8)-1.1` and should print 2.2
4. `10/2+5-1 +-/*` is parsed as `10/((2+5)-1)` and the printed result should be 1.6666666...
5. `2147480/90+10*5 +/-*` is parsed as `(2147480/(90+10))*5` and the printed result should be 107374
6. `3*55-5/8/4+1 -/+*` is parsed as `3*((((55-5)/8)/4)+1)` should print 7.6875
7. An input containing one thousand instances of the number `1.015` separated by multiplier operators (i.e. the expanded multiplicative form of `1.015^1000`), followed by any operated precedence specification, should print a number within 0.0001 of 2924436.8604.

Code golf, so shortest code wins.

# Answer
> 6 votes
# JavaScript (ES6), 94 bytes

Not particularly short, but fun. Adding parentheses all over the place...

```
s=>([e,o]=s.split` `,[...o].map(x=>e=e.split(x).join((a+=')')+x+(b+='(')),a=b=''),eval(b+e+a))

```

### Test cases

```
let f =

s=>([e,o]=s.split` `,[...o].map(x=>e=e.split(x).join((a+=')')+x+(b+='(')),a=b=''),eval(b+e+a))

console.log(f("6.3*7.8 +-*/"))              // 49.14
console.log(f("2.2*3.3+9.9/8.8-1.1 */+-"))  // 7.285
console.log(f("2.2*3.3+9.9/8.8-1.1 +*/-"))  // 2.2
console.log(f("10/2+5-1 +-/*"))             // 1.6666
console.log(f("2147480/90+10*5 +/-*"))      // 107374
console.log(f("3*55-5/8/4+1 -/+*"))         // 7.6875
```

### Historical note

A similar method was used in early FORTRAN compilers. Here is a link from archive.org to a relevant article written by Donald E. Knuth in a 1962 book called *Computers and automation*.

### Examples

Let's consider the expression `2.2*3.3+9.9/8.8-1.1`.

With operator precedence `*/+-`, it will expand to:

```
((((2.2)*(3.3)))+(((9.9))/((8.8))))-((((1.1))))

```

With operator precedence `+*/-`, it will now expand to:

```
((((2.2))*((3.3)+(9.9)))/(((8.8))))-((((1.1))))

```

Removing all redundant parentheses, we get:

```
((2.2*3.3)+(9.9/8.8))-1.1 = 7.285

```

and:

```
((2.2*(3.3+9.9))/8.8)-1.1 = 2.2

```

# Answer
> 4 votes
## JavaScript (ES6), ~~174~~ 133 bytes

Saved 41 bytes thanks to Arnauld.

```
i=>([e,o]=i.split` `,e=e.split(/([+*/-])/),[...o].map(x=>{while(~(b=e.indexOf(x)))e.splice(--b,3,eval(e.slice(b,b+3).join``))}),e[0])

```

First golf! This is probably terribly unoptimized.

### Ungolfed:

```
f = input => {
    [equation, output] = input.split(" ");
    equation = equation.split(/([+*/-])/);
    [...output].map(x => {
        while (~(b = equation.indexOf(x))) {
            equation.splice(--b, 3, eval(equation.slice(b, b + 3).join("")));
        }
    });
    return equation[0];
};

```

This splits the input equation into tokens of numbers and operators, then iterates through operators in the specified order and collapses pairs of numbers using `eval()` until there's only one left.

JavaScript rounding error trash means that test case 3 results in `2.1999...` instead of `2.2`. I'm not sure if that disqualifies this answer, but oh well.

### Test cases:

```
f=i=>([e,o]=i.split` `,e=e.split(/([+*/-])/),[...o].map(x=>{while(~(b=e.indexOf(x)))e.splice(--b,3,eval(e.slice(b,b+3).join``))}),e[0])

console.log(f("6.3*7.8 +-/*"));
console.log(f("2.2*3.3+9.9/8.8-1.1 */+-"));
console.log(f("2.2*3.3+9.9/8.8-1.1 +*/-"));
console.log(f("10/2+5-1 +-/*"));
console.log(f("2147480/90+10*5 +/-*"));
console.log(f("3*55-5/8/4+1 -/+*"));
console.log(f((new Array(1000)).fill("1.015").join("*") + " +-*/"));
```

# Answer
> 4 votes
## JavaScript (ES6), 59 bytes

```
f=(s,[o,...a])=>eval(o?s.split(o).map(e=>f(e,a)).join(o):s)

```

Port of my golf of @HyperNeutrino's Python answer. Takes lowest precedence first.

# Answer
> 2 votes
# Python 3, 77 bytes

```
f=lambda a,b:eval(b and b[0].join(str(f(A,b[1:]))for A in a.split(b[0]))or a)

```

Try it online!

-23 bytes thanks to Neil (takes operator precedence in reverse)
-1 byte thanks to Mr. Xcoder

# Answer
> 1 votes
# Proton, 87 bytes

```
x=>y=>eval((f=b=>a=>b?"(#{e.join(map(f(b[to-1]),a.split(e=b[-1])))})":a)(y)(x)).evalf()

```

Try it online!

+19 bytes to accommodate for the unnecessarily restrictive output format. seriously? the restriction is actually making the answers *less* accurate because now instead of precise fractional output it's giving inaccurate IEEE floating points... think about it...

# Answer
> 1 votes
# Jelly, 21 bytes

```
ṣ⁹ḊṪ¤ñ€⁹Ṗ¤j⁹ḊṪ¤ŒVµ¹⁹?

```

Try it online!

# Explanation

```
ṣ⁹ḊṪ¤ñ€⁹Ṗ¤j⁹ḊṪ¤ŒVµ¹⁹?  Main Link
                    ?  Ternary:
                   ⁹   If the right argument is truthy:
ṣ                      Split it by
  ḊṪ                   The last element of
 ⁹  ¤                  The right argument
      €                For each element
     ñ                 Call the next link as a dyad (wraps around so this calls the current link as a dyad)
       ⁹Ṗ¤             With right argument as `right_argument[:-1]`
          j            Join with
            ḊṪ         The last element of
           ⁹  ¤        The right argument
               ŒV      Evaluate as Python code
                 µ     Start a new monadic chain. If the right argument is falsy:
                  ¹    Identity: Return the left argument unmodified

```

# Answer
> 1 votes
# Perl 5, 64 + 1 (`-p`) = 65 bytes

```
s/ .*//;for$i(map"\\$_",$&=~/./g){s/[\d.]*$i[0-9.]*/$&/ee&&redo}

```

Try it online!

# Answer
> 0 votes
# JavaScript (ES6), 96 bytes

```
f=(o,s)=>o?f(o.slice(s!=(s=s.replace(eval(['/','\\'+o[0],'/'].join`(\\d+\\.?\\d*)`),eval))),s):s

```

A non-recursive attempt was first made for this technique, but it came up at 101:

```
(s,o)=>[...o].map(x=>[...s].map(_=>s=s.replace(eval(['/','\\'+x,'/'].join`(\\d+\\.?\\d*)`),eval)))&&s

```

# Answer
> 0 votes
## Clojure, 167 bytes

```
(defn f [i O](eval(read-string(or(first(filter some?(for[o O](let[[x y](clojure.string/split i(re-pattern(str \\ o))2)](when y(str" ("o\ (f x O)\ (f y O)")"))))))i))))

```

Whoa, long function names strike again! Operation precedence `O` is taken in "reverse" order.

# Answer
> 0 votes
# C (gcc) , 276 bytes

```
A,B,u,i,j,k;double g(){double a,b,f[1000];char o[999],p[5];for(i=k=0;o[i++]^32&&scanf("%lf%c",&f[i],&o[i]););for(gets(p);k<4;k++)for(A=B=0;B<i;A=B){for(;!f[B++]&&i/B;);if(A&&o[--A]==p[k])u=p[k],a=f[A],b=f[--B],f[B]=u^42?u^43?u^45?a/b:a-b:a+b:a*b,f[A]=0,o[A]=o[B++];}a=f[i-1];}

```

Try it online

Slightly longer solution using NAN

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


# Question
Title: Who will win a Rock, Paper, Scissors, Lizard, Spock game?
There are several questions regarding this game, even a contest here. But I think all those challenges and contests need a way to automatically determine the winner of a game. So:

**Challenge**

Given two inputs in the range `["rock", "paper", "scissors", "lizard", "spock"]` representing the selections for player 1 and player 2, determine the winner of the match.

**Rules**

```
[Winner] [action]    [loser]
-----------------------------
scissors cut         paper
paper    covers      rock
rock     crushes     lizard
lizard   poisons     spock
spock    smashes     scissors
scissors decapitates lizard
lizard   eats        paper
paper    disproves   spock
spock    vaporizes   rock
rock     crushes     scissors

```

**Restrictions**

* Input will be a pair of strings in the given range (no other strings can be used). You can use arrays of chars if you want, as long as they represent any of the mentioned values.
* You can choose whether to use lowercase, uppercase (`"ROCK"`) or camel case (`"Rock"`) for the input strings, as long as the chosen case is the same for all inputs.
* Output will be a trio of values that determine the winner, which can be anything you want as long as the answers are consistent. Example: `1` if the first input wins, `2` if the second input wins, `0` if there is a tie. Or maybe `A` if the first input wins, `B` if the second input wins, `<empty string>` if there is a tie.

**Goal**

This is , so may the shortest program/method/function/lambda for each language win!

**Tests**

```
[Input 1] [Input 2] [Output: 1/2/0]
-----------------------------------
 rock      paper     2
 rock      scissors  1
 lizard    spock     1
 spock     rock      1
 spock     paper     2
 rock      rock      0

```

# Answer
> 25 votes
# Python 3, ~~68~~ ~~50~~ 48 bytes

EDIT: Thanks to 3 tricks from Neil, and 2 from Mr. Xcoder

Each input string has a distinct fourth character, so I'm using that to distinguish them. If you arrange the elements in the cycle (scissors, paper, rock, lizard, spock), then each element beats the element directly after it and the element 3 spots to the right, cyclically. So we subtract the inputs' positions in the cycle. If that number is 0, it's a tie. If it's 1 or 3, it's a win for the first player. In my original solution, the cycle difference would index into the string "210100" to distinguish the results of the game. Neil somehow figured out this can be accomplished without indexing by adding 7 and taking the modulus by 3. Edit: Originally I used the second character to identify the string, but if you use the fourth and reverse the cycle, you get cake. And we could all use more cake.

```
lambda x,y,z="cake".find:(7+z(y[3])-z(x[3]))%5%3

```

Try it online!

Older version:

```
lambda x,y,z="caoip".index:(7+z(y[1])-z(x[1]))%5%3

```

Try it online!

Original version:

```
b="caoip"
def r(x,y):return"210100"[(b.index(y[1])-b.index(x[1]))%5]

```

Try it online!

# Answer
> 14 votes
# JavaScript (ES6), 56 bytes

Takes input in currying syntax `(a)(b)`. Returns `0` if A wins, `1` if B wins, or `false` for a tie.

```
a=>b=>a!=b&&a>b^614>>((g=s=>parseInt(s,31)%9)(a)^g(b))&1

```

### Demo

```
let f =

a=>b=>a!=b&&a>b^614>>((g=s=>parseInt(s,31)%9)(a)^g(b))&1

console.log('[Tie]');
console.log(f("paper"   )("paper"   ))

console.log('[A wins]');
console.log(f("scissors")("paper"   ))
console.log(f("paper"   )("rock"    ))
console.log(f("rock"    )("lizard"  ))
console.log(f("lizard"  )("spock"   ))
console.log(f("spock"   )("scissors"))
console.log(f("scissors")("lizard"  ))
console.log(f("lizard"  )("paper"   ))
console.log(f("paper"   )("spock"   ))
console.log(f("spock"   )("rock"    ))
console.log(f("rock"    )("scissors"))

console.log('[B wins]');
console.log(f("paper"   )("scissors"))
console.log(f("rock"    )("paper"   ))
console.log(f("lizard"  )("rock"    ))
console.log(f("spock"   )("lizard"  ))
console.log(f("scissors")("spock"   ))
console.log(f("lizard"  )("scissors"))
console.log(f("paper"   )("lizard"  ))
console.log(f("spock"   )("paper"   ))
console.log(f("rock"    )("spock"   ))
console.log(f("scissors")("rock"    ))
```

### How?

We define the hash function **H()** as:

```
H = s => parseInt(s, 31) % 9

```

This gives:

```
s          | H(s)
-----------+-----
"rock"     |  2
"paper"    |  8
"scissors" |  1
"lizard"   |  3
"spock"    |  4

```

Given two inputs **a** and **b**, we consider the following statements:

1. do we have **a \> b**? (in lexicographical order)
2. does **b** win the game?
3. what's the value of **N = H(a) XOR H(b)**?

From (1) and (2), we deduce whether the result of **a \> b** should be inverted to get the correct winner and we store this flag in the **N-th** bit of a lookup bitmask.

```
a        | H(a) | b        | H(b) | N  | a > b | b wins | invert
---------+------+----------+------+----+-------+--------+-------
rock     |   2  | paper    |   8  | 10 | Yes   | Yes    | No
rock     |   2  | scissors |   1  |  3 | No    | No     | No
rock     |   2  | lizard   |   3  |  1 | Yes   | No     | Yes
rock     |   2  | spock    |   4  |  6 | No    | Yes    | Yes
paper    |   8  | rock     |   2  | 10 | No    | No     | No
paper    |   8  | scissors |   1  |  9 | No    | Yes    | Yes
paper    |   8  | lizard   |   3  | 11 | Yes   | Yes    | No
paper    |   8  | spock    |   4  | 12 | No    | No     | No
scissors |   1  | rock     |   2  |  3 | Yes   | Yes    | No
scissors |   1  | paper    |   8  |  9 | Yes   | No     | Yes
scissors |   1  | lizard   |   3  |  2 | Yes   | No     | Yes
scissors |   1  | spock    |   4  |  5 | No    | Yes    | Yes
lizard   |   3  | rock     |   2  |  1 | No    | Yes    | Yes
lizard   |   3  | paper    |   8  | 11 | No    | No     | No
lizard   |   3  | scissors |   1  |  2 | No    | Yes    | Yes
lizard   |   3  | spock    |   4  |  7 | No    | No     | No
spock    |   4  | rock     |   2  |  6 | Yes   | No     | Yes
spock    |   4  | paper    |   8  | 12 | Yes   | Yes    | No
spock    |   4  | scissors |   1  |  5 | Yes   | No     | Yes
spock    |   4  | lizard   |   3  |  7 | Yes   | Yes    | No

```

Hence the bits:

```
bit | value
----+-----------
 0  | 0 (unused)
 1  | 1
 2  | 1
 3  | 0
 4  | 0 (unused)
 5  | 1
 6  | 1
 7  | 0
 8  | 0 (unused)
 9  | 1
10  | 0
11  | 0
12  | 0

```

Reading this from bottom to top and ignoring leading zeros, this gives **1001100110**, or **614** in decimal.

# Answer
> 5 votes
# 05AB1E, 16 bytes

```
ε'³²s3èk}Æ7+5%3%

```

Try it online! or as a Test Suite

**Explanation**

Uses the very nice `cake`-trick from user507295

```
ε       }          # apply to each in the input pair
    s3è            # get the 4th letter
 '³²   k           # get its cake-index
         Æ         # reduce by subtraction
          7+       # add 7
            5%3%   # mod by 5 and then 3

```

# Answer
> 4 votes
## JavaScript (ES6), ~~63~~ ~~54~~ ~~53~~ 49 bytes

```
f=
(l,r,g=s=>"cake".search(s[3]))=>(7+g(r)-g(l))%5%3
```

```
<div onchange=o.textContent=`RLT`[f(a.selectedOptions[0].value,b.selectedOptions[0].value)]>L: <select id=a><option>Rock<option>Paper<option>Scissors<option>Lizard<option>Spock</select> R: <select id=b><option>Rock<option>Paper<option>Scissors<option>Lizard<option>Spock</select> Winner: <span id=o>T
```

Port of my golf to @WhatToDo's answer. Note: the snippet decodes the numeric result into something slightly less unreadable. Edit: Saved 1 byte thanks to @Arnauld. Saved 4 bytes thanks to @ovs.

# Answer
> 3 votes
# Ruby, 36 bytes

```
->a,b{(2+a.sum%88%6-b.sum%88%6)%5%3}

```

Returns `0` if 1st player wins, `1` if 2nd player wins, and `2` for a draw.

Based on user507295's answer but uses a mathematical formula to perform the hash. `a.sum` is the sum of all ASCII codes of the string `a`, mod `1<<16` and is intended as a rudimentary checksum. The hash was found using the following code:

```
1.upto(99){|j|p j,["scissors","paper","rock","lizard","spock"].map{|i|i.sum%j%6}}

```

This produced two values of `j` that gave a suitable hash for lowercase letters, namely 88 and 80, both of which gave the descending sequence `[3,2,1,0,4]` (or `[4,3,2,1,0]` if spock is cycled round to the beginning.)

As explained in other answers, a hash which gives a constant difference modulo 5 for consecutive elements in the above sequence is needed to make the `(h[a]-h[b])%5`formula work. Each element beats the element 1 or 3 places to the right and loses to the element 2 or 4 places to the right.

Try it online!

# Answer
> 3 votes
## C, 53bytes

```
a="FÈ..J..ÁE";
z=*++y==*++x?0:a[*y&47>>1]>>*++x&7&1+1;

```

I've treated this problem as a state machine, of which there are 25 states as defined by the two, five state inputs.

By defining the results of the states within an an array of bits. I look the results up within by using unique markers within the inputs.

As noted in other solutions, characters 2, 3 and 4 are unique between the possible inputs. I have concentrated use on characters 2 and 3 which I use to select the appropriate bit within my answer array.

Within Character 2, bits 1 thru 4 clearly identify the input. By masking these bits and shifting appropriately \[that's the "\*y&47\>\>1"\], the input can be noted as 0, 1, 4, 7 or 8. Hence my answer string has 9 characters. (separated interesting bits)

```
character 2:
a 61   011 0000 1
c 63   011 0001 1
i 69   011 0100 1
p 70   011 1000 0
o 6f   011 0111 1

```

Within character 3, bits 0, 1 and 2 clearly identify the input. By Masking these bits (shifting not required) \[that's the "\*x&7"\], the input can be noted as 0, 1, 2, 3 or 7 . (separated interesting bits)

```
character 3
p 70   01110 000
i 69   01101 001
z 7a   01111 010
o 6f   01101 111
c 63   01100 011

```

The answer string can then be calculated by simply filling in the bits for the appropriate characters.

```
0th char represents X=paper
1st char represents X=scissors
4th char represents X=Lizard
7th char represents X=Rock
8th char represents X=Spock

0th bit represents Y=Paper
1st bit represents Y=Scissors
2nd bit represents Y=Lizard
3rd bit represents Y=Rock
7th bit represents Y=Spock

```

So, set bit in char where Y wins

```
char  7654 3210   in hex    in ascii
0     0100 0110    46         F
1     1100 1000    c8         È
2     0100 0000    d/c        .
3     0100 0000    d/c        .
4     0100 1010    4a         J
5     0100 0000    d/c        .
6     0100 0000    d/c        .
7     1100 0001    c1         Á
8     0100 0101    45         E

```

Then the logic is simply: if second char is same then draw, otherwise, get ascii char based on y's second character and shift bits by x's third character and add one. This makes the answers 0 for draw, 1 for x win and 2 for y win.

# Answer
> 1 votes
# Clojure, ~~130~~ 118 bytes

-12 bytes by getting rid of my weird usage of `comp`.

```
(fn[& m](let[[p q](map #(apply +(map int(take 2 %)))m)d(- p q)](cond(= d 0)0(#{5 -16 12 -14 13 1 4 -18 2 11}d)1 1 2)))

```

I thought I was being clever, but this ended up being naïve compared to some other answers, and *much* longer.

Takes the first 2 letters of each move string, gets the char codes, and sums them. It then subtracts the sums to get `d`. If `d` is 0, its a tie (0), if it's in the set of `#{5 -16 12 -14 13 1 4 -18 2 11}`, p1 wins (1), else, p2 wins (2).

```
(defn decide [& moves] ; Using varargs so I don't need to duplicate the steps.
  ; Pop the first 2 chars of each string, convert them to their ASCII code, and sum them.
  (let [[p1 p2] (map #(apply + (map int (take 2 %))) moves)
        d (- p1 p2)]

    (cond
      (= d 0) ; A tie
      0

      (#{5 -16 12 -14 13
         1 4 -18 2 11} d) ; P1 Wins
      1

      :else ; P2 Wins
      2)))

```

To get the "magic numbers" that define if P1 wins, I ran

```
(let [ms ["rock", "paper", "scissors", "lizard", "spock"]]
  (for [p1 ms
        p2 ms]

    ; Same as above
    (let [[p q] (map #(apply + (map int (take 2 %))) [p1 p2])
          d (- p q)]

      [p1 p2 d])))

```

Which generates a list of `d` values for each possible scenario:

```
(["rock" "rock" 0]
 ["rock" "paper" 16]
 ["rock" "scissors" 11]
 ["rock" "lizard" 12]
 ["rock" "spock" -2]
 ["paper" "rock" -16]
 ["paper" "paper" 0]
 ["paper" "scissors" -5]
 ["paper" "lizard" -4]
 ["paper" "spock" -18]
 ["scissors" "rock" -11]
 ["scissors" "paper" 5]
 ["scissors" "scissors" 0]
 ["scissors" "lizard" 1]
 ["scissors" "spock" -13]
 ["lizard" "rock" -12]
 ["lizard" "paper" 4]
 ["lizard" "scissors" -1]
 ["lizard" "lizard" 0]
 ["lizard" "spock" -14]
 ["spock" "rock" 2]
 ["spock" "paper" 18]
 ["spock" "scissors" 13]
 ["spock" "lizard" 14]
 ["spock" "spock" 0])

```

Then I compared the win chart against this output. Luckily there weren't any "collisions" other than 0.

---
Tags: code-golf, game
---


title: Draw boxes from box drawing characters

text:
# Question
Title: Draw boxes from box drawing characters
In the old DOS operating system, a number of characters were provided to draw boxes. Here is a selection of these characters and their code points:

```
B3 B4 BF C0 C1 C2 C3 C4 C5 D9 DA
│  ┤  ┐  └  ┴  ┬  ├  ─  ┼  ┘  ┌

```

You can use these characters to draw boxes like this:

```
┌─────────┐
│         │
└─────────┘

```

Boxes can be attached to each other:

```
        ┌───┐
        │   │
┌───┬───┤   │
│   │   │   │
│   ├───┴───┘
│   │
└───┘

```

or intersect each other:

```
┌─────┐
│     │
│  ┌──┼──┐
│  │  │  │
└──┼──┘  │
   │     │
   └─────┘

```

or overlap each other partially or completely:

```
┌─────┐
├──┐  │
│  │  │
├──┘  │
└─────┘

```

## Challenge description

Write a program that receives a series of positive decimal integers separated by whitespace from standard input. The number of integers you receive is a multiple of four, each set of four integers *x*1 *x*2 *y*1 *y*2 is to be interpreted as the coordinates of two points *x*1 *y*1 and *x*2 *y*2 forming opposing corners of a box. You may assume that for each set of coordinates, *x*1*x*2 and *y*1*y*2.

The coordinate system originates in the top left corner with *x* coordinates progressing to the right and *y* coordinates progressing downwards. You can assume that no *x* coordinate larger than 80 and no *y* coordinate larger than 25 appears.

Your program shall output in either UTF-8, UTF-16, or Codepage 437 a series of whitespace, carriage returns, line feeds, and box drawing characters such that the output shows the boxes described in the input. There may be extraneous whitespace at the end of lines. You may terminate lines either with CR/LF or just LF but stick to one, stray CR characters are not allowed. You may output any number of lines filled with an arbitrary amount of whitespace at the end of the output.

## Examples

The following input draws the first diagram from the question:

```
1 11  1 3

```

The second diagram is offset a little bit, the leading whitespace and empty lines must be reproduced correctly:

```
17 13   3  7
 9  5   5  9
 9 13   5  7

```

The third diagram also tests that input is parsed correctly:

```
1 7 1
5 4 10
3 7

```

The fourth diagram:

```
11 5 2 6
5 8 3 5

```

As a final test case, try this fifth diagram:

```
    ┌─────┬─────┐
┌───┼───┬─┼─┬───┴───┐
│   │   │ │ │       │
└───┼───┴─┼─┴───┬───┘
    └─────┴─────┘

```

Which looks like this:

```
9 21 2 4 1
13 4 2 11 5
1 5 17 11 1
2 11 17 4 5

```

## Winning condition

This is code golf. The shortest solution in octets (bytes) wins. Standard loopholes apply, (worthless) bonus points for writing a solution that works on DOS.

# Answer
> 3 votes
# CJam, 129

```
0a80*a25*[q~]4/{:(2/:$_::-+e_534915808 6b3/\ff=C2b.+{):A;)z{_A)+\[A!A].+_A)4*+\}*;}%{~:A;_3$=@_2$=A|tt}/}/"   ┌ ─┐┬ └│├┘┴┤┼"ff=N*

```

Try it online

Notes:

* If the boxes don't look quite right, it's possible that your browser is using a fallback font for box drawing characters.
* CJam doesn't specify an encoding for source files. In UTF-8, this code has 151 bytes, but you can save it using CP437 or CP850 instead (and run it with the same encoding), then it will use 1 byte/character.

**Overview:**

`0a80*a25*` creates a matrix of 80×25 zeros
`[q~]4/` reads the input, converts to numbers and splits into quadruplets
`:(2/:$_::-+e_` converts an \[x1 x2 y1 y2\] quadruplet to \[xmin xmax ymin ymax -width -height\] (negative values will be corrected later)
`534915808 6b3/` generates \[\[1 2 5\] \[0 2 5\] \[0 3 4\] \[0 2 4\]\], to be used as indices in the previous array for extracting data about the 4 sides of the current box
`\ff=` extracts the data for each side, e.g. \[1 2 5\] -\> \[xmax ymin -height\] for the right side
`C2b.+` appends 1, 1, 0, 0 respectively to the arrays for the 4 sides (right, left, bottom, top); this number indicates the direction (0=horizontal, 1=vertical)
`):A;)z{_A)+\[A!A].+_A)4*+\}*;` generates line pieces for a side, as \[x y bitmask\] triplets; each piece is a line going from the center of the cell to one of 4 directions: 1=right, 2=bottom, 4=left, 8=top; e.g. \[4 2 -3 0\] (a horizontal line of length 3 starting at x=4, y=2) results in \[4 2 1\] \[5 2 4\] \[5 2 1\] \[6 2 4\] \[6 2 1\] \[7 2 4\]
`{~:A;_3$=@_2$=A|tt}/` bitwise-OR's all these line pieces into the matrix, resulting in bitmasks from 0..15
`" ┌ ─┐┬ └│├┘┴┤┼"ff=` converts these bitmasks to the corresponding box-drawing characters
`N*` joins with newlines for display

# Answer
> 4 votes
# PHP\>=7.1, 820 Bytes

```
<?preg_match_all("#(\d+(\s+\d+){3})#s",$_GET[0],$t);$r=($w="array_fill")(1,25,$w(1,80," "));function u($n,$y,$x){global$r;$u=[$z=[" ","│",$c="┤","┐","└",$d="┴",$e="┬",$b="├","─","┘","┌",$a="┼"],["│",$c,$b,$a],[$c,$a],["┐",$c,$e,$a],["└",$d,$b,$a],[$d,$a],[$e,$a],[$b,$a],["─",$d,$e,$a],["┘",$c,$d,$a],["┌",$e,$b,$a],[$a]];$o=$r[$y][$x];$s=array_intersect($u[($k="array_search")($n,$z)],$u[$k($o,$z)]);$r[$y][$x]=reset($s);}foreach($t[1]as$e){[$a,$b,$c,$d]=explode(" ",preg_replace("#\s+#"," ",$e));u("┌",$h=min($c,$d),$f=min($a,$b));u("┐",$h,$g=max($a,$b));u("└",$i=max($c,$d),$f);u("┘",$i,$g);foreach(($l="array_slice")(range($f,$g),1,-1)as$x){u("─",$h,$x);u("─",$i,$x);}foreach($l(range($h,$i),1,-1)as$y){u("│",$y,$f);u("│",$y,$g);}}foreach($r as$v)echo join($v)."\n";

```

-6 Bytes for use `"array_fill"`,`"array_search"`, `"array_slice"` without `"`

+19 Bytes `echo ltrim(rtrim(join($v))."\n","\n");` instead of `echo join($v)."\n";` to print only the necessary Chars

Online Version

Expanded

```
preg_match_all("#(\d+(\s+\d+){3})#s",$_GET[0],$t); # find all rects
$r=($w="array_fill")(1,25,$w(1,80," ")); # fill a empty 2 D array with spaces
function u($n,$y,$x){ # Char , Y Coordinate, X Coordinate as parameter
global$r; # result array must be global to make changes
# The following array based on Set Theory
$u=[
$z=[" ","│",$c="┤","┐","└",$d="┴",$e="┬",$b="├","─","┘","┌",$a="┼"],
["│",$c,$b,$a],
[$c,$a],
["┐",$c,$e,$a],
["└",$d,$b,$a],
[$d,$a],
[$e,$a],
[$b,$a],
["─",$d,$e,$a],
["┘",$c,$d,$a],
["┌",$e,$b,$a]
,[$a]];
$o=$r[$y][$x]; # old value for YX
$s=array_intersect($u[($k="array_search")($n,$z)],$u[$k($o,$z)]); # make the Cut quantity
$r[$y][$x]=reset($s); # Take the first value Cut quantity and set it as new value
}
foreach($t[1]as$e){ # for each rect
[$a,$b,$c,$d]=explode(" ",preg_replace("#\s+#"," ",$e)); #split the four coordinates
# next 4 rows make edges and set minimum and maximum for X an Y values
u("┌",$h=min($c,$d),$f=min($a,$b));
u("┐",$h,$g=max($a,$b));
u("└",$i=max($c,$d),$f);
u("┘",$i,$g);
foreach(($l="array_slice")(range($f,$g),1,-1)as$x){u("─",$h,$x);u("─",$i,$x);} # make the X lines
foreach($l(range($h,$i),1,-1)as$y){u("│",$y,$f);u("│",$y,$g);} # make the  Y lines
}
foreach($r as$v)echo join($v)."\n"; # Output

```

## Order of the array Set Theory

```
foreach($u as $k0=>$v0)
foreach($u as $k1=>$v1)
echo "\n\n'".$z[$k0]."' + '".$z[$k1]."' = '". join("','",array_intersect($v0,$v1))."'";

```

Examples Set Theory all possible values

The array without the use of variables to short it

```
$u=[
$z=[" ","│","┤","┐","└","┴","┬","├","─","┘","┌","┼"],
["│","┤","├","┼"],
["┤","┼",],
["┐","┤","┬","┼"],
["└","┴","├","┼"],
["┴","┼"],
["┬","┼"],
["├","┼"],
["─","┴","┬","┼"],
["┘","┤","┴","┼"],
["┌","┬","├","┼"]
,["┼"]];');

```

# Answer
> 3 votes
# Haskell, ~~399~~ ~~340~~ 398 bytes

-59 (!) bytes thanks to Ørjan Johansen

```
import Data.Bits
import Data.Array
(&)=(,)
z=maximum
r x=[minimum x..z x-1]
l=map(+1).r
e(a:b:c:d:q)=[x&y&n|(n,(f,g))<-zip[0..][id&l,id&r,l&id,r&id],x<-f[a,b],y<-g[c,d]]++e q;e[]=[]
f a|m<-z a=unlines[[" UD│L┘┐┤R└┌├─┴┬┼"!!(accumArray setBit 0(1&1,m&m)(e a)!(x,y))|x<-[1..m]]|y<-[1..m]]
main=interact$f.map read.words

```

Try it online!

**Ungolfed**

```
import Data.Bits
import Data.Array
import Data.List.Split

(&) = (,) -- Alias for tuples

-- Given [a,b], returns a list of all x: a <= x < b
halfOpenLeft x = [minimum x..maximum x-1::Int]

-- Same as above, but for all x: a < x <= b
halfOpenRight = map(+1).halfOpenLeft

up    = ((id, halfOpenRight), 0) -- Coordinates that should have a line upwards
down  = ((id, halfOpenLeft),  1) -- Coordinates that should have a line downwards
left  = ((halfOpenRight, id), 2) -- Coordinates that should have a line leftwards
right = ((halfOpenLeft, id),  3) -- Coordinates that should have a line rightwards

-- Create a map between coordinates and line-segments. Each coordinate can have multiple line-segments.
lineSegments :: [[Int]] -> [((Int,Int),Int)]
lineSegments rects = [ ((x,y),n) | [x1,x2,y1,y2] <- rects, ((f,g),n) <- [up,down,left,right], x <- f [x1,x2], y <- g [y1,y2]]

-- Convert an array of bit-fields into a list of lines.
printBitfieldArray :: Int -> Array (Int,Int) Int -> [String]
printBitfieldArray size a = [[" UD│L┘┐┤R└┌├─┴┬┼"!!(a!(x,y))|x<-[1..size]]|y<-[1..size]]

-- Merge all the line-segments for each coordinate into a bitfield
createBitFieldArray :: Int -> [((Int,Int),Int)] -> Array (Int,Int) Int
createBitFieldArray m = accumArray setBit 0 ((1,1),(m,m))

-- First split the input for each rectangle,
-- then create a list of pairs of coordinates and directions,
-- then merge all directions for each coordinate into a bitfield
-- and finally use the bitfield as an index to find out which shape to draw.
drawRectangles :: Int -> [Int] -> [String]
drawRectangles m=printBitFieldArray m.createBitFieldArray m.lineSegments.chunksOf 4

-- Parse the input, solve the problem and format the output. Use the largest number as both width and height.
main=interact$unlines.(drawRectangles=<<maximum).map read.words

```

## Explanation

1. First, `lineSegments` (or `d` in the golfed version) will loop over all rectangles, all directions and all coordinates that should have a line-segment in that direction from that rectangle and create a list of coordinates paired with directions.
2. Then `createBitFieldArry` merges all entries with identical coordinates into an array of bitfields. Here, the 0th bit means up, 1st means down, 2nd means left and the 3rd means right. In other words, 5 is rendered as "┘", 0 is " " and 15 is "┼".
3. Lastly, `printBitFieldArray` (or `p`) converts the bitfields into box-drawing characters by using them as indices.

# Answer
> 1 votes
# Python 3, 632 bytes

```
i=input()
j=''
while i:j+=i+' ';i=input()
c=[int(k)-1for k in j.split()]
c=[c[k:k+4]for k in range(0,len(c),4)]
for q in c:
    for v,w in[(0,1),(2,3)]:
        if q[w]<q[v]:t=q[w];q[w]=q[v];q[v]=t
d=list(zip(*c))
w=max(d[1])+1
h=max(d[3])+1
g=[0]*w*h
def i(a,b,f):
    for k in b:
        for l in a:g[k*w+l]|=f[0];f=f[1:]
def p(k,l,m,n,o,j=0):
    for i in range(m,n,o):l[i]|=k
    if j:p(k,l,m+j,n+j,o)
for q in c:i(q[:2],q[2:],[6,12,3,9]);p(10,g,q[0]+1+q[2]*w,q[1]+q[2]*w,1,(q[3]-q[2])*w);p(5,g,q[0]+q[2]*w+w,q[0]+q[3]*w,w,q[1]-q[0])
print('\n'.join(map(lambda k: ''.join(map(lambda x: '   └ │┌├ ┘─┴┐┤┬┼'[x], k)),[g[x:x+w]for x in range(0,len(g),w)])))

```

# Answer
> 1 votes
## Node, 536 bytes

```
s=''
with(process.stdin){setEncoding('utf8')
on('readable',_=>s+=read()||'')
on('end',_=>{a=s.match(/(\d+\s+){3}\d+/g).map(s=>s.match(/\d+/g).map(m=>+m)).map(([m,n,o,p])=>[m>n?n:m,m>n?m:n,o>p?p:o,o>p?o:p])
m=i=>[...Array(Math.max(...a.map(a=>a[i])))]
console.log(m(3).map((_,y)=>m(1).map((_,x)=>' ??┘?│┐┤?└─┴┌├┬┼'[x++,a.some(([m,n,o,p])=>x==m|x==n&&y>o&y<=p)+2*a.some(([m,n,o,p])=>y==o|y==p&&x>m&x<=n)+4*a.some(([m,n,o,p])=>x==m|x==n&&y>=o&y<p)+8*a.some(([m,n,o,p])=>y==o|y==p&&x>=m&x<n)],y++).join``).join`\n`)})}

```

Directly calculates the correct character at each coordinate. Input is annoying to perform in Node...

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


title: Implement BCD Arithmetic

text:
# Question
Title: Implement BCD Arithmetic
Write the shortest function you can that takes two binary-coded decimal integers and a character indicating an arithmetic operation to perform and return the result.

**Input Specification**
You will be passed two 32-bit bit patterns representing unsigned BCD integers. In C or Java, for example, you would be passed an `int` (`unsigned`, if you prefer). The third argument to your function will be a single character denoting what operation to perform. If your language requires fixed return sizes, return a 32-bit result and ignore overflow. Your return value should also be encoded as a BCD.

You should support `+`, `-`, `*`, `/`, and `%`. For subtraction, the first argument is the minuend and the second argument is the subtrahend. For division and modulo, the first argument is the quotient and the second is the divisor.

**Example**

```
bcd(0x00000127, 0x00000003, '+') => 0x00000130 // NOT 0x0000012A

```

# Answer
> 1 votes
# Python - 47 chars

```
bcd=lambda*a:"0x%08d"%eval("%x%s%x"%(a*2)[::2])

```

tests

```
>>> print bcd(0x00000127, 0x00000003, '+')
0x00000130
>>> print bcd(0x00000127, 0x00000003, '*')
0x00000381
>>> print bcd(0x00000127, 0x00000003, '/')
0x00000042
>>> print bcd(0x00000127, 0x00000003, '-')
0x00000124

```

# Answer
> 1 votes
# Windows PowerShell, 54 ~~56~~ ~~69~~

```
filter f($a,$b,$o){'0x'+("{0:x}$o{1:x}"-f+$a,+$b|iex)}

```

A bit cheating, I guess, but the output very well works as input again. I.e., PowerShell doesn't care whether it's a string or actual numeric literal there.

Test:

```
> f 0x127 0x3 +
0x130

```

History:

* 2011-02-11 10:35 (69) – First attempt.
* 2011-02-11 10:36 (56) – Going easy on the extra zeroes.
* 2011-02-11 10:41 (54) – `filter` is shorter.

# Answer
> 0 votes
# JavaScript ES6, 61 bytes

```
(a,b,y)=>0|'0x'+~~eval([a,b].map(t=>+t.toString(16)).join(y))

```

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