# Question
Title: Build interpreter for non-existent language
Build an interpreter for a fake, stack-based language that gets an input, interprets it, and outputs the result as an array of numbers. It should iterate through each byte and perform a different function based on this table:

0000 (0): Concatenate (Combine top two numbers in a stack as if they were a string. ex: 12,5 -\> 125)
0001 (1): Increment (Add 1 to the number on the top of the stack)
0010 (2): Decrement (Subtract one from the number at the top of the stack)
0011 (3): Multiply (Multiply the top two numbers in the stack)
0100 (4): Divide (Divide the 2nd-to-top number by the top number on the stack)
0101 (5): Add (Add the top two numbers on the stack)
0110 (6): Subtract (Subtract the top number on the stack from the one below it)
0111 (7): Exponent (Calculate the second-to-top number to the power of the top number)
1000 (8): Modulus: (Find the second-to-top number modulo the top one)
1001 (9): Rotate Right (Shift the stack down one. The number on the bottom is now on the top)
1010 (A): Rotate Left (Shift the stack up one. The number on the top is now on the bottom)
1011 (B): Duplicate (Copy the top number so that it appears twice. ex: 4,1 becomes 4,1,1)
1100 (C): Double Duplicate (Copy the top two numbers on the stack. ex: 4,1,2 becomes 4,1,2,1,2)
1101 (D): Swap (Swap the top two numbers on the stack. ex: 4,1,2 becomes 4,2,1)
1110 (E): Double Swap (Swap the top two numbers with two below them.ex: 1,2,3,4,5 becomes 1,4,5,2,3)
1111 (F): Delete/Pop (Remove the number at the top of the stack)

For example, a file containing

```
1 1 B C 5 C 5 B 9 5    - Input (hex)
| | | | | | | | | |
1 2 2 2 4 4 6 6 2 8    - Stack
    2 2 2 2 4 6 6 6
      2 2 4 2 4 6 4
      2   2 2 2 4 2
          2   2 2

```

would output \[8,6,4,2\]

## Rules:

* Unicode/symbols are okay, but ASCII is best.
* Be creative! Shortness counts, but creativity is great!
* If bytes are too hard, use `"$iv*/+-^%><dtsz."` or `"0123456789ABCDEF"` instead of actual bytes.
* SPEED! The faster, the better.
* The score is based on reputation, but size is a huge factor.

## Bonus:

Try to complete this challenge using your newly made interpreter in as short of a string as possible.

## Note:

The thing that makes this challenging as opposed to other code-golfing challenges is that there is no code to go by with this. If, lets say, you had to write a brainf\*ck interpreter, you could look at other people's implementations. With this, you can't do that.

---

I forgot to put and ending date on this. I guess I'll make it one month from when I created this. Person with the highest votes at Feb. 22 wins!

# Answer
# Ruby, 67 lines of regex substitutions

I decided to write the interpreter in regex, while sticking to efficient algorithms.

I could have gone for plain bytes, but using symbols makes the code more readable in my opinion. Of course, if we could pack two instructions in one byte...

Concatenation of negative values results in ten's complement behavior, reflecting the internal representation.

Division is integer division and the remainder is never negative.

```
subs = [
  # stack expansion
  [/^ ?([$iv*\/+\-^%dtsz.])/,  ' 0 \1'  ],
  [/^ (\d+ [$*\/+\-^%tsz])/,   ' 0 \1'  ],
  [/^ ((\d+ ){2,3}z)/,         ' 0 \1'  ],
  [/ (0|9)\1+/,                ' \1'    ],
  # concatenation
  [/ (\d+) (?:0+|9+)(\d+) \$/, ' \1\2 ' ],
  [/ (\d+) (0|9) \$/,          ' \1\2 ' ],
  # swaps
  [/ ((?:\d+ )*)(\d+) </,      ' \2 \1' ],
  [/ (\d+)((?: \d+)*) >/,      '\2 \1 ' ],
  [/ (\d+) (\d+) s/,           ' \2 \1 '],
  [/ (\d+ \d+) (\d+ \d+) z/,   ' \2 \1 '],
  # dups
  [/ (\d+) d/,                 ' \1 \1 '],
  [/ (\d+ \d+) t/,             ' \1 \1 '],
  # pop
  [/ (\d+) \./,                ' '      ],

  # increment / decrement
  [/ (\d+) i/, ' \1I '], [/ (\d+) v/, ' \1V '],
  *(%w[0I 1I 2I 3I 4I 5I 6I 7I 8I 9I].zip [*?1..?9, 'I0']),
  *(%w[0V 1V 2V 3V 4V 5V 6V 7V 8V 9V].zip ['V9', *?0..?8]),
  [' 1', ' 01'], [' 8', ' 98'], [' I', ' '], [' V', ' '],
  # addition, subtraction
  [/ (\d+) (\d+) \+/,                ' \1P \2P '       ], #init addition
  [/ (\d+) (\d+) \-/,                ' \1S \2S '       ], #init subtraction
  [/ ([PS](\d)\w*) (\d+[PS]\w*) /,   ' \2\1 \3 '       ], #sign extend left
  [/ (\d+[PS]\w*) ([PS](\d)\w*) /,   ' \1 \3\2 '       ], #sign extend right
  [/ (\d*)(\d)P(\S*) (\d*)0P(0*) /,  ' \1P\2\3 \4P0\5 '], #advance addition
  [/ (\d*)(\d)S(\S*) (\d*)0S(0*) /,  ' \1S\2\3 \4S0\5 '], #advance subtraction
  [/ (\d+)P(\S*) (\d*[1-5])P(0*) /,  ' \1IP\2 \3VP\4 ' ], #transfer left
  [/ (\d+)P(\S*) (\d*[6-9])P(0*) /,  ' \1VP\2 \3IP\4 ' ], #transfer right
  [/ (\d+)S(\S*) (\d*[1-5])S(0*) /,  ' \1VS\2 \3VS\4 ' ], #decrement both
  [/ (\d+)S(\S*) (\d*[6-9])S(0*) /,  ' \1IS\2 \3IS\4 ' ], #increment both
  [/ [PS](\S+) [PS]0+ /,             ' \1 '            ], #finish

  # digitwise negation
  *(%w[9N 8N 7N 6N 5N 4N 3N 2N 1N 0N].zip [*'N0'..'N9']),
  #multiplication and division by 2
  *([*'H0'..'H9'].zip %w[0H 0F 1H 1F 2H 2F 3H 3F 4H 4F]),
  *([*'F0'..'F9'].zip %w[5H 5F 6H 6F 7H 7F 8H 8F 9H 9F]),
  *(%w[0T 1T 2T 3T 4T 5T 6T 7T 8T 9T].zip %w[T0 T2 T4 T6 T8 TI0 TI2 TI4 TI6 TI8]),
  ['H ', ' '], [' T', ' '],

  # sign correction for */%
  [/ (\d+) (9\d*) ([*\/%])/, ' \1NI \2NI \3'], [' N', ' '],
  # multiplication
  [/ (0+ \d+|\d+ 0+) \*/,     ' 0 '          ], #multiplication by zero
  [/ (\d+) (0\d*[02468]) \*/, ' \1T H\2 *'   ], #multiplication by an even number
  [/ (\d+) (0\d*[13579]) \*/, ' \1 \1 \2V *+'], #multiplication by an odd number
  # division / modulo
  [?/, 'r.'], [?%, 'rs.'],
  [/ (0|9)(\d*) (0\d+) r/,           ' \3 0 \1D\2 '          ], #init division
  [/ (\d+) (\d+) (0\d*)D(\d*) /,     ' \1 \2I \3SD\4 \1S '   ], #subtract divisor
  [/ (\d+) (\d+) (9\d*)D(\d)(\d*) /, ' \1 \2V0 \3P\4D\5 \1P '], #add divisor and advance
  [/ (\d+) (\d+) (9\d*)D /,          ' \2V \3P \1P '         ], #add divisor and finish

  #exponentiation
  [/ \d+ 0+ \^/,             ' 01 '          ], # case: zeroth power
  [/ 9\d+ 9+ \^/,            ' 9 '           ], # case: reciprocal of negative
  [/ \d+ 9\d+ \^/,           ' 0 '           ], # case: high negative power
  [/ 0\d+ 9\d+ \^/,          ' 0 '           ], # case: reciprocal of positive
  [/ (\d+) 0+1 \^/,          ' \1 '          ], # case: power of one
  [/ (\d+) (\d*[02468]) \^/, ' \1 \1 *H\2 ^' ], # case: even exponent
  [/ (\d+) (\d*[13579]) \^/, ' \1 \2V ^\1 *' ], # case: odd exponent
]

x = gets.tr '^$iv*/+\-^%><dtsz.', ''
until x =~ /^ (\d+ )*$/
  subs.each do |sub|
    x.sub!(*sub) # && (puts x; sleep 0.1)
  end
end

```

As for the bonus round, the shortest solution I've come up with (**13 characters**) is a clean solution:

```
iistisii$<$<$

```
> 14 votes

# Answer
## x86 assembly (on Win32)

“SPEED!” seems to be hugely important here, and we all know nothing beats assembly language in that regard. So, let’s do that in assembly!

This is an implementation of the language in x86 assembly language (in NASM syntax), with the numbers stored and interpreted as unsigned 32-bit integers, using the native x86 stack directly. Stack underflow, and overflow during any arithmetic operation (or division by zero) is a runtime error, terminating the program with an error message.

```
        global _start

        extern _GetCommandLineA@0
        extern _GetStdHandle@4
        extern _CreateFileA@28
        extern _GetFileSize@8
        extern _LocalAlloc@8
        extern _ReadFile@20
        extern _CloseHandle@4
        extern _WriteFile@20

section .text

; ---------------------------------------------------------------------------------------
; Initialization
; ---------------------------------------------------------------------------------------

_start:
        ; Retrieve command line
        CALL _GetCommandLineA@0

        ; Skip argv[0]
        MOV ESI, EAX
        XOR EAX, EAX
skipuntilspace:
        MOV AL, [ESI]
        INC ESI
        TEST EAX, EAX
        JE missingparam
        CMP EAX, ' '
        JNE skipuntilspace
        INC ESI

        ; Open the file
        PUSH 0
        PUSH 80h
        PUSH 3
        PUSH 0
        PUSH 1
        PUSH 80000000h
        PUSH ESI
        CALL _CreateFileA@28
        CMP EAX, -1
        JE  cannotopenfile

        ; Get its size
        PUSH EAX
        PUSH 0
        PUSH EAX
        CALL _GetFileSize@8

        PUSH EAX

        ; Allocate memory buffer
        PUSH EAX
        PUSH 0
        CALL _LocalAlloc@8
        TEST EAX, EAX
        MOV ESI, EAX
        JZ outofmemory

        POP ECX
        POP EAX
        PUSH EAX

        ; Store end-of-program pointer
        MOV [programend], ESI
        ADD [programend], ECX

        ; Read the file contents
        PUSH 0
        PUSH buff
        PUSH ECX
        PUSH ESI
        PUSH EAX
        CALL _ReadFile@20
        TEST EAX, EAX
        JZ cannotopenfile

        ; Close the file
        CALL _CloseHandle@4

; ---------------------------------------------------------------------------------------
; Main loop of the interpreter
; ---------------------------------------------------------------------------------------

        ; Store the end of stack into EBP
        MOV EBP, ESP

        ; Push an initial 0 onto the stack
        XOR EAX, EAX
        PUSH EAX

mainloop:
        ; Load the next opcode, if not end of program
        XOR EAX, EAX
        CMP ESI, [programend]
        MOV AL, [ESI]
        JAE endloop
        LEA ESI, [ESI+1]

        ; Check if the opcode is valid
        CMP EAX, (maxop - opcodetable) / 8
        JA  fault_invalidopcode

        ; Check for required stack space
        MOV ECX, [opcodetable + 8 * EAX + 4]
        LEA EDI, [ESP + ECX]
        CMP EDI, EBP
        JA  fault_stackunderflow

        ; Jump to the respective opcode handler
        MOV EAX, [opcodetable + 8 * EAX]
        JMP EAX

; ---------------------------------------------------------------------------------------
; Implementation of the specific operations
; ---------------------------------------------------------------------------------------

        ; ************** CAT 0000 (0): Concatenate (Combine top two numbers in a stack as if they were a string. ex: 12,5 -> 125)
op_concatenate:
        POP EBX
        POP EAX
        MOV ECX, EAX
        MOV EDI, 10
concat_loop:
        XOR EDX, EDX
        SHL EBX, 1
        DIV EDI
        LEA EBX, [4 * EBX + EBX]
        TEST EAX, EAX
        JNZ concat_loop

        ADD EBX, ECX
        PUSH EBX
        JMP mainloop

        ; ************** INC 0001 (1): Increment (Add 1 to the number on the top of the stack)
op_increment:
        POP EAX
        ADD EAX, 1
        PUSH EAX
        JNC mainloop
        JMP fault_intoverflow

        ; ************** DEC 0010 (2): Decrement (Subtract one from the number at the top of the stack)
op_decrement:
        POP EAX
        SUB EAX, 1
        PUSH EAX
        JNC mainloop
        JMP fault_intoverflow

        ; ************** MUL 0011 (3): Multiply (Multiply the top two numbers in the stack)
op_multiply:
        POP EAX
        POP EDX
        MUL EDX
        TEST EDX, EDX
        PUSH EAX
        JZ mainloop
        JMP fault_intoverflow

        ; ************** DIV 0100 (4): Divide (Divide the 2nd-to-top number by the top number on the stack)
op_divide:
        POP ECX
        TEST ECX, ECX
        POP EAX
        JZ fault_dividebyzero
        XOR EDX, EDX
        DIV ECX
        PUSH EAX
        JMP mainloop

        ; ************** MOD 0101 (5): Add (Add the top two numbers on the stack)
op_add:
        POP EAX
        ADD [ESP], EAX
        JNC mainloop
        JMP fault_intoverflow

        ; ************** SUB 0110 (6): Subtract (Subtract the top number on the stack from the one below it)
op_subtract:
        POP EAX
        SUB [ESP], EAX
        JNC mainloop
        JMP fault_intoverflow

        ; ************** EXP 0111 (7): Exponent (Calculate the second-to-top number to the power of the top number)
op_exponent:
        POP ECX
        POP EBX
        MOV EAX, 1
exploop:
        TEST ECX, 1
        JZ expnomult
        MUL EBX
        TEST EDX, EDX
        JNZ fault_intoverflow
expnomult:
        SHR ECX, 1
        JZ expdone
        XCHG EAX, EBX
        MUL EAX
        TEST EDX, EDX
        XCHG EAX, EBX
        JZ exploop
        JMP fault_intoverflow
expdone:
        PUSH EAX
        JMP mainloop

        ; ************** MOD 1000 (8): Modulus: (Find the second-to-top number modulo the top one)
op_modulus:
        POP ECX
        TEST ECX, ECX
        POP EAX
        JZ fault_dividebyzero
        XOR EDX, EDX
        IDIV ECX
        PUSH EDX
        JMP mainloop

        ; ************** ROR 1001 (9): Rotate Right (Shift the stack down one. The number on the bottom is now on the top)
op_rotright:
        MOV EAX, [EBP - 4]
        LEA ECX, [EBP - 4]
        SUB ECX, ESP
        MOV EDX, ESI
        SHR ECX, 2
        LEA EDI, [EBP - 4]
        LEA ESI, [EBP - 8]
        STD
        REP MOVSD
        MOV [ESP], EAX
        CLD
        MOV ESI, EDX
        JMP mainloop

        ; ************** ROL 1010 (A): Rotate Left (Shift the stack up one. The number on the top is now on the bottom)
op_rotleft:
        MOV EAX, [ESP]
        LEA ECX, [EBP - 4]
        SUB ECX, ESP
        MOV EDX, ESI
        SHR ECX, 2
        LEA ESI, [ESP + 4]
        MOV EDI, ESP
        REP MOVSD
        MOV [EBP - 4], EAX
        MOV ESI, EDX
        JMP mainloop

        ; ************** DUP 1011 (B): Duplicate (Copy the top number so that it appears twice. ex: 4,1 becomes 4,1,1)
op_duplicate:
        PUSH DWORD [ESP]
        JMP mainloop

        ; ************** DU2 1100 (C): Double Duplicate (Copy the top two numbers on the stack. ex: 4,1,2 becomes 4,1,2,1,2)
op_dblduplicate:
        PUSH DWORD [ESP+4]
        PUSH DWORD [ESP+4]
        JMP mainloop

        ; ************** SWP 1101 (D): Swap (Swap the top two numbers on the stack. ex: 4,1,2 becomes 4,2,1)
op_swap:
        POP EAX
        POP EDX
        PUSH EAX
        PUSH EDX
        JMP mainloop

        ; ************** SW2 1110 (E): Double Swap (Swap the top two numbers with two below them.ex: 1,2,3,4,5 becomes 1,4,5,2,3)
op_dblswap:
        POP EAX
        POP EBX
        POP ECX
        POP EDX
        PUSH EBX
        PUSH EAX
        PUSH EDX
        PUSH ECX
        JMP mainloop

        ; ************** POP 1111 (F): Delete/Pop (Remove the number at the top of the stack)
op_pop:
        POP EAX
        JMP mainloop

; ---------------------------------------------------------------------------------------
; End of the program: print out the resulting stack and exit
; ---------------------------------------------------------------------------------------

endloop:
        MOV ESI, ESP

printloop:
        CMP ESI, EBP
        JNB exit
        MOV EAX, [ESI]
        MOV EBX, ESI
        PUSH EBX
        CALL printnum
        POP EBX
        LEA ESI, [EBX + 4]
        JMP printloop

exit:
        MOV ESP, EBP
        ;POP EAX
        XOR EAX, EAX
        RET

; ---------------------------------------------------------------------------------------
; Faults
; ---------------------------------------------------------------------------------------

fault_invalidopcode:
        MOV EAX, err_invalidopcode
        JMP fault

fault_stackunderflow:
        MOV EAX, err_stackunderflow
        JMP fault

fault_dividebyzero:
        MOV EAX, err_dividebyzero
        JMP fault

fault_intoverflow:
        MOV EAX, err_intoverflow
        JMP fault

fault:
        CALL print
        MOV EAX, crlf
        CALL print

        MOV ESP, EBP
        MOV EAX, 1
        RET

missingparam:
        MOV EAX, err_missingparameter
        JMP fault

cannotopenfile:
        MOV EAX, err_cannotopenfile
        JMP fault

outofmemory:
        MOV EAX, err_outofmemory
        JMP fault

; ---------------------------------------------------------------------------------------
; Helper functions
; ---------------------------------------------------------------------------------------

printnum:
        MOV EBX, 10
        CALL printnumrec
        MOV EAX, crlf
        JMP print

printnumrec:
        PUSH EAX
        PUSH EDX
        XOR EDX, EDX
        DIV EBX
        TEST EAX, EAX
        JZ printnumend
        CALL printnumrec
printnumend:
        MOV EAX, EDX
        CALL printdigit
        POP EDX
        POP EAX
        RET

printdigit:
        ADD EAX, '0'
        MOV [printbuff], EAX
        MOV EAX, printbuff
        JMP print

print:
        MOV  ESI, EAX
        PUSH 0
        PUSH buff
        CALL strlen
        PUSH EAX
        PUSH ESI
        PUSH -11
        CALL _GetStdHandle@4
        PUSH EAX
        CALL _WriteFile@20
        RET

strlen:
        XOR ECX, ECX
strlen_loop:
        CMP BYTE [ESI+ECX], 0
        JE strlen_end
        LEA ECX, [ECX+1]
        JMP strlen_loop
strlen_end:
        MOV EAX, ECX
        RET

; ---------------------------------------------------------------------------------------
; Data
; ---------------------------------------------------------------------------------------

section .data

; Table of opcode handlers and required stack space (in bytes, i.e. 4*operands)
opcodetable:
        DD op_concatenate, 8
        DD op_increment, 4
        DD op_decrement, 4
        DD op_multiply, 8
        DD op_divide, 8
        DD op_add, 8
        DD op_subtract, 8
        DD op_exponent, 8
        DD op_modulus, 8
        DD op_rotright, 0
        DD op_rotleft, 0
        DD op_duplicate, 4
        DD op_dblduplicate, 8
        DD op_swap, 8
        DD op_dblswap, 16
        DD op_pop, 4
maxop:

crlf                    DB 13, 10, 0
err_invalidopcode       DB "Invalid opcode", 0
err_stackunderflow      DB "Stack underflow", 0
err_dividebyzero        DB "Division by zero", 0
err_intoverflow         DB "Integer overflow", 0

err_missingparameter:   DB "Missing parameter: Use nexlang file.bin", 0
err_cannotopenfile:     DB "Unable to open input file", 0
err_outofmemory:        DB "Not enough memory", 0

section .bss

programend      RESD 1
printbuff       RESD 1
buff            RESD 1

```

To compile this, use something like

```
nasm.exe -fwin32 nexlang.asm
ld -o nexlang.exe -e _start nexlang.obj -s -lkernel32

```

The program receives the name of the binary file containing the program on the command line (e.g. `nexlang.exe testprg.bin`). When finished, it prints the final contents of the stack to standard output in a human-readable format.

To help with testing, save the following into `nex.def`:

```
%define CAT DB 00h
%define INC DB 01h
%define DEC DB 02h
%define MUL DB 03h
%define DIV DB 04h
%define ADD DB 05h
%define SUB DB 06h
%define EXP DB 07h
%define MOD DB 08h
%define ROR DB 09h
%define ROL DB 0Ah
%define DUP DB 0Bh
%define DU2 DB 0Ch
%define SWP DB 0Dh
%define SW2 DB 0Eh
%define POP DB 0Fh

```

And then write your NEX (“non-existing”, as named in the question title) programs using the above-defined mnemonics, and compile with something like

```
nasm.exe -p nex.def -o prg.bin prg.nex

```

E.g. for the original test case, use the following `prg.nex`:

```
INC     ; 1
INC     ; 2
INC     ; 3
INC     ; 4
DUP     ; 4 4
DU2     ; 4 4 4 4
ADD     ; 8 4 4
DU2     ; 8 4 8 4 4
ADD     ; 12 8 4 4
DUP     ; 12 12 8 4 4
ROR     ; 4 12 12 8 4
ADD     ; 16 12 8 4

```

And finally, for the “2014” challenge, use the following 14-byte NEX program:

```
DUP     ; 0 0
DUP     ; 0 0 0
INC     ; 1 0 0
INC     ; 2 0 0
SWP     ; 0 2 0
CAT     ; 20 0
SWP     ; 0 20
INC     ; 1 20
DUP     ; 1 1 20
INC     ; 2 1 20
INC     ; 3 1 20
INC     ; 4 1 20
CAT     ; 14 20
CAT     ; 2014

```
> 11 votes

# Answer
# GolfScript, 64 chars

OK, so I decided to try and golf this. And what better language for golfing than GolfScript?

Conveniently, GolfScript itself is already a stack-based language with single-byte commands, and, as it happens, 11 out of your 16 commands map directly to built-in GolfScript commands. So all I really need to do to interpret your language is to implement the remaining five commands in GolfScript and build a translation table:

```
0\{'`+~
)
(
*
/
+
-
?
%
](+~
])\~
.
1$1$
\
[@]\+~\
;'n%=~}/]-1%`

```

The code looks kind of spread out, because I'm using newlines as delimiters for the translation table. The initial `0\` pushes a zero onto the stack and moves it below the input program. The `{ }/` loop, comprising most of the code, takes the input program off the stack and iterates the loop body over each of its characters, and the final `]-1%`` collects the stack into an array, reverses it (because your sample output starts from the top of the stack) and stringifies it.

The loop body starts with a 16-line single-quoted string. `n%` splits this string at line breaks, `=` looks up the substring corresponding to the input character, and `~` evaluates the substring as GolfScript code.

Finally, here are the GolfScript implementations of the 16 commands:

* 0 = ``+~`: concatenate two numbers as strings
* 1 = `)`: increment
* 2 = `(`: decrement
* 3 = `*`: multiply
* 4 = `/`: divide
* 5 = `+`: add
* 6 = `-`: subtract
* 7 = `?`: raise to power
* 8 = `%`: modulus
* 9 = `](+~`: rotate stack right
* A = `])\~`: rotate stack left
* B = `.`: duplicate
* C = `1$1$`: double duplicate
* D = `\`: swap
* E = `[@]\+~\`: double swap
* F = `;`: pop

I'm kind of unhappy with the double swap — it's ugly and much longer than any of the other commands. It feels like there ought to be a better way, but if so, I haven't found it yet. Still, at least it works.

For example, running the program above on the input (given as a GolfScript / Ruby / Perl / Python / etc. double-quoted string):

```
"\x01\x01\x0B\x0C\x05\x0C\x05\x0B\x09\x05"

```

yields the output:

```
[8 6 4 2]

```

---

**Edit:** I managed to save two more chars, for a total of **62 chars**, using a more compact encoding of the translation table. However, it kind of sacrifices readability:

```
0\{(')(*/+-?%'1/'](+~
])\~
.
1$1$
\
[@]\+~\
;
`+~'n/+=~}/]-1%`

```

Notable features of this version include the `(` at the beginning of the loop, which shifts the command indices from 0..15 to -1..14 so that I can put the long sequence of single-character commands from 1 to 8 at the beginning of the table. This allows me to store them in a separate string and eliminate the eight newlines delimiting them; alas, the extra complexity costs me six characters elsewhere.
> 9 votes

# Answer
# Haskell

Just for fun, I made a solution that uses no variables whatsoever, only combines functions together.

```
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Data.Function

type SM = State [Int]

pop :: SM Int
pop = state ((,) <$> head <*> tail)

push :: Int -> SM ()
push = modify . (:)

popN :: Int -> SM [Int]
popN = sequence . flip replicate pop

pushN :: [Int] -> SM ()
pushN = mapM_ push

rotL, rotR :: Int -> [a] -> [a]
rotL = (uncurry (flip (++)) .) . splitAt
rotR = (reverse .) . flip (flip rotL . reverse)

step :: Int -> SM ()
step 0x00 = push =<< ((read .) . on (++) show) <$> pop <*> pop
step 0x01 = push . (+ 1) =<< pop
step 0x02 = push . subtract 1 =<< pop
step 0x03 = push =<< (*) <$> pop <*> pop
step 0x04 = push =<< flip div <$> pop <*> pop
step 0x05 = push =<< (+) <$> pop <*> pop
step 0x06 = push =<< flip (-) <$> pop <*> pop
step 0x07 = push =<< flip (^) <$> pop <*> pop
step 0x08 = push =<< flip mod <$> pop <*> pop
step 0x09 = modify $ (:) <$> last <*> init
step 0x0A = modify $ rotL 1
step 0x0B = pop >>= pushN . replicate 2
step 0x0C = popN 2 >>= pushN . concat . replicate 2
step 0x0D = popN 2 >>= pushN . rotL 1
step 0x0E = popN 4 >>= pushN . rotL 2
step 0x0F = void pop

run :: [Int] -> [Int]
run = flip execState [0] . mapM_ step

```
> 9 votes

# Answer
# Ruby, ~~330~~ 316 characters

I decided to golf it. (Because that's always fun.)

```
s=[0]
o=->c{t=s.pop;s.push s.pop.send(c,t)}
gets.chop.each_char{|c|eval %w[t=s.pop;s.push"#{s.pop}#{t}".to_i s[-1]+=1 s[-1]-=1 o[:*] o[:/] o[:+] o[:-] o[:**] o[:%] s.rotate! s.rotate!(-1) s.push(s[-1]) s.concat(s[-2..-1]) s[-1],s[-2]=s[-2],s[-1] s[-1],s[-2],s[-3],s[-4]=s[-4],s[-3],s[-1],s[-2] s.pop][c.to_i 16]}
p s

```

The main part is this:

```
gets.chop.each_char{|c|eval [(huge array of strings)][c.to_i 16]}

```

It translates each hex digit into a base-10 integer, and then uses the `[(huge array of strings)]` to find the right string that represents that command. Then it `eval`s that string.

Note that `%w[x y z]` is equivalent to `['x','y','z']`.

I also like how you can find smiley faces in that line! Some of them are

* `:*`
* `:/`
* `:-]`
* `:%`

Sample run:

```
c:\a\ruby>random_cg_lang
11BC5C5B95
[2, 4, 6, 8]

```
> 6 votes

# Answer
# C - 642 634 characters

For the `$iv*/+-^%><dtsz.` dialect only (adds `q` as an ending character, along with `0`):

```
#define P s=*t;a=realloc(a,--w<<2);t=a+w-1;
#define H(n)a=realloc(a,(w+=n)<<2);
#define B(n)break;case n:
*a,*t,s,w=1,i;main(){t=a=calloc(4,1);while((i=getchar())&&i^'q')switch(i){B(36)P*t*=pow(10,((
int)log10(s))+1);*t+=s;B(105)++*t;B(118)--*t;B(42)P*t*=s;B(47)P*t/=s;B(43)P*t+=s;B(45)P*t-=s;
B(94)P*t=pow(*t,s);B(37)P*t%=s;B(62)s=*a;memcpy(a,a+1,(w-1)<<2);*t=s;B(60)s=*t;memcpy(a+1,a,(
w-1)<<2);*a=s;B(100)H(1)t=a+w-2;s=*t;t++;*t=s;B(116)H(2)t=a+w-1;t[-1]=t[-3];*t=t[-2];B(115)s=
*t;*t=t[-1];t[-1]=s;B(122)s=*t;*t=t[-2];t[-2]=s;s=t[-1];t[-1]=t[-3];t[-3]=s;B(46)P}putchar('[
');putchar(32);while(w)printf("%i ",a[--w]);putchar(']');}

```

Solution for the 2014 challenge: `dididiizs>`.
> 4 votes

# Answer
# C ~~924~~ ~~882~~ ~~622~~ ~~603~~ ~~587~~ ~~569~~ 562 chars

With obvious newlines removed (retained for readability).

```
#define A sbrk(8);signal(11,S);
#define W(x)write(1,x,1);
#define P (t>s?*--t:0)
#define U *t++
#define B(x,y)else if(b==(w=w+1 x)){w=P;y;U=w;}
*t,*s,w,a,d;char b;S(x){A}
p(x){if(x<0){W("-")x=-x;}if(x>9)p(x/10);b=48+x%10;W(&b)}
main(c){t=s=A U=0;
while(read(0,&b,1))if(!(w=47));
B(,w+=P*pow(10,w?ceil(log10(w)):1))
B(,++w)
B(,--w)
B(,w*=P)
B(,w=P/w)
B(,w+=P)
B(,w=P-w)
B(,w=pow(P,w))
B(,w=P%w)
B(,w=*s;memmove(s,s+1,t-s<<2))
B(+7,memmove(s+1,s,t++-s<<2);*s=w;w=P)
B(,U=w)
B(,a=P;U=a;U=w;U=a)
B(,a=P;U=w;w=a)
B(,a=P;c=P;d=P;U=a;U=w;U=c;w=d)
B(,w=P)
for(W("[")t>s;)p(P),W(" ")
W("]")}

```

This implements the "underflow pushes zero" interpretation from Jan Dvorak's comment.

The golfed version actually changed substantially compared to the ungolfed version here, under the (welcome) pressure of Oberon's fine answer.

I found that replacing the `switch` statement in favor of an `if`...`else` chain enabled me to factor-out all of the digits from my *cases*. Instead it initializes the `w` variable to 47 so one increment raises it to 48 (== ascii `'0'`) then each case increments `w` until we need to skip to `'A'` at which point we make use of the mostly empty first macro argument which adds an extra 7 to get up to 'A'. The ungolfed version *does* show my favorite `sbrk`/`SIGSEGV` trick to get "free" memory with no further allocations.

```
#include<math.h>
#include<signal.h>
void S(int x){signal(SIGSEGV,S);sbrk(8*8*8);}
int*s,*t,*i,w,a,c,d;    //stack top index working accumulator count data
u(x){*t++=x;}           //push()
o(){return t>s?*--t:0;} //pop()
#define W(x)write(1,&x,1);  //output a byte
p(x){                   //print()
    if(x<0){    //negative?
        W(*"-") //output '-'
        x=-x;   //negate
    }
    if(x>9)     //more than one digit?
        p(x/10); //recurse after integer-divide
    b=48+x%10;   //isolate and convert single digit to ascii
    W(b)         //output ascii digit
}
main(){
    char b[1];
    signal(SIGSEGV,S);  //auto-allocate memory for stack
    t=s=sbrk(8*8*8);  //get start of memory and allocate
    while(read(0,b,1)){
        write(1,b,1); //for debugging: echo the command being executed
        switch(*b){
            case '0': w=o(); a=o(); for(c=ceil(log10(w));c>0;c--) a*=10; u(a+w); break;
            case '1': u(o()+1); break;
            case '2': u(o()-1); break;
            case '3': w=o(); u(o()*w); break;
            case '4': w=o(); u(o()/w); break;
            case '5': u(o()+o()); break;
            case '6': w=o(); u(o()-w); break;
            case '7': c=o();a=1; for(w=o();c>0;c--) a*=w; u(a); break;
            case '8': w=o(); u(o()%w); break;
            case '9': w=*s; memmove(s,s+1,4*(t-s-1)); t[-1]=w; break;
            case 'A': w=t[-1]; memmove(s+1,s,4*(t-s-1)); *s=w; break;
            case 'B': w=o(); u(w); u(w); break;
            case 'C': w=o(); a=o(); u(a); u(w); u(a); u(w); break;
            case 'D': w=o(); a=o(); u(w); u(a); break;
            case 'E': w=o(); a=o(); c=o(); d=o(); u(a); u(w); u(d); u(c); break;
            case 'F': o(); break;
        }
    }
    write(1,"\n[",2);   //dump the stack
    i=t;
    do {
        p(*--i);
    } while(i>s && write(1,",",1));
    write(1,"]\n",2);
}

```
> 3 votes

# Answer
# k, 228

```
(,0){({(-7h$,/$2#x),2_x};@[;0;+;1];@[;0;-;1];{.[*;|2#x],2_x};{.[%;|2#x],2_x};
{.[+;|2#x],2_x};{.[-;|2#x],2_x};{.[xexp;|2#x],2_x};{.[mod;|2#x],2_x};{(*|x),-1_x};
{(1_x),*x};{(*x),x};{(2#x),x};{(|2#x),2_x};{,/(|2 2#x),4_x};1_)[y]x}/
0x01010b0c050c050b0905

8 4 6 2

```

There's a fair amount of repetition in the implementation of similar instructions, which can be probably be engineered away to some extent.
> 3 votes

# Answer
### R, 428 characters

```
f=function(I){s=0;for(i in strsplit(I,"")[[1]]){r=s[-(1:2)];s=switch(i,'0'=c(as.integer(paste0(s[2],s[1])),r),'1'=c(s[1]+1,s[-1]),'2'=c(s[1]-1,s[-1]),'3'=c(s[1]*s[2],r),'4'=c(s[2]%/%s[1],r),'5'=c(s[1]+s[2],r),'6'=c(s[1]-s[2],r),'7'=c(s[2]^s[1],r),'8'=c(s[2]%%s[1],r),'9'=c(s[length(s)],s[-length(s)]),'A'=c(s[-1],s[1]),'B'=c(rep(s[1],2),s[-1]),'C'=c(rep(s[1:2],2),r),'D'=c(s[2:1],r),'E'=c(s[3:4],s[1:2],s[-(1:4)]),'F'=s[-1])};s}

```

With indentations:

```
f=function(I){
    s=0
    for(i in strsplit(I,"")[[1]]){
        r=s[-(1:2)]
        s=switch(i,
                '0'=c(as.integer(paste0(s[2],s[1])),r),
                '1'=c(s[1]+1,s[-1]),
                '2'=c(s[1]-1,s[-1]),
                '3'=c(s[1]*s[2],r),
                '4'=c(s[2]%/%s[1],r),
                '5'=c(s[1]+s[2],r),
                '6'=c(s[1]-s[2],r),
                '7'=c(s[2]^s[1],r),
                '8'=c(s[2]%%s[1],r),
                '9'=c(s[length(s)],s[-length(s)]),
                'A'=c(s[-1],s[1]),
                'B'=c(rep(s[1],2),s[-1]),
                'C'=c(rep(s[1:2],2),r),
                'D'=c(s[2:1],r),
                'E'=c(s[3:4],s[1:2],s[-(1:4)]),
                'F'=s[-1])
        }
    s
    }

```

In action:

```
> f('11BC5C5B95')
[1] 8 6 4 2

```
> 1 votes

# Answer
## JavaScript, 685

Non-golfed version (gist):

```
var Token = {
  Concatenate: '0',
  Increment: '1',
  Decrement: '2',
  Multiply: '3',
  Divide: '4',
  Add: '5',
  Subtract: '6',
  Exponent: '7',
  Modulus: '8',
  RotateRight: '9',
  RotateLeft: 'A',
  Duplicate: 'B',
  DoubleDuplicate: 'C',
  Swap: 'D',
  DoubleSwap: 'E',
  Delete: 'F'
};

function parse(input, mem) {
  var a, b, c, d;
  var stack = mem ? mem.slice() : [0];
  for (var i = 0, n = input.length; i < n; i++) {
    switch (input[i]) {
      case Token.Concatenate:
        a = stack.pop();
        b = stack.pop();
        stack.push(parseInt([b] + a));
        break;

      case Token.Increment:
        a = stack.pop();
        stack.push(a + 1);
        break;

      case Token.Decrement:
        a = stack.pop();
        stack.push(a - 1);
        break;

      case Token.Multiply:
        a = stack.pop();
        b = stack.pop();
        stack.push(b * a);
        break;

      case Token.Divide:
        a = stack.pop();
        b = stack.pop();
        stack.push(b / a | 0);
        break;

      case Token.Add:
        a = stack.pop();
        b = stack.pop();
        stack.push(b + a);
        break;

      case Token.Subtract:
        a = stack.pop();
        b = stack.pop();
        stack.push(b - a);
        break;

      case Token.Exponent:
        a = stack.pop();
        b = stack.pop();
        stack.push(Math.pow(b, a));
        break;

      case Token.Modulus:
        a = stack.pop();
        b = stack.pop();
        stack.push(b % a);
        break;

      case Token.RotateRight:
        a = stack.shift();
        stack.push(a);
        break;

      case Token.RotateLeft:
        a = stack.pop();
        stack.unshift(a);
        break;

      case Token.Duplicate:
        a = stack[stack.length - 1];
        stack.push(a);
        break;

      case Token.DoubleDuplicate:
        a = stack[stack.length - 1];
        b = stack[stack.length - 2];
        stack.push(b, a);
        break;

      case Token.Swap:
        a = stack.pop();
        b = stack.pop();
        stack.push(a, b);
        break;

      case Token.DoubleSwap:
        a = stack.pop();
        b = stack.pop();
        c = stack.pop();
        d = stack.pop();
        stack.push(b, a, d, c);
        break;

      case Token.Delete:
        stack.pop();
        break;

      default:
        throw new SynxtaxError('Invalid token "' + input[i] + '"');
    }
  }

  return stack.reverse();
}

exports.Token = Token;
exports.parse = parse;

```

Golfed version:

```
function f(c){var b,d,e,f,a=[i=0],g=c.length;a.a=a.pop;for(a.b=a.push;i<g;i++)switch(c[i])
{case"0":b=a.a();a.b(parseInt([a.a()]+b));break;case"1":a[a.length-1]++;break;case"2":
a[a.length-1]--;break;case"3":a.b(a.a()*a.a());break;case"4":b=a.a();a.b(a.a()/b|0);break;
case"5":a.b(a.a()+a.a());break;case"6":b=a.a();a.b(a.a()-b);break;case"7":b=a.a();
a.b(Math.pow(a.a(),b));break;case"8":b=a.a();a.b(a.a()%b);break;case"9":a.b(a.shift());break;
case"A":a.a();a.unshift(a.a());break;case"B":a.b(a[a.length-1]);break;case"C":
a.b(a[a.length-2],a[a.length-1]);break;case"D":b=a.a();a.b(b,a.a());break;case"E":b=a.a();
d=a.a();e=a.a();f=a.a();a.b(d,b,f,e);break;case"F":a.a()}return a.reverse()}

```

Example:

```
> f('11BC5C5B95')
[ 8, 6, 4, 2]

```
> 1 votes

# Answer
# Haskell

```
import Data.List (elemIndex)

type Stack = [Integer]

u :: (Integer -> Integer) -> Stack -> Stack
u p (x:t) = p x : t -- unary operation

b :: (Integer -> Integer -> Integer) -> Stack -> Stack
b p (x:y:t) = p x y : t -- binary operation

encoding :: String
encoding = "$iv*/+-^%><dtsz."
-- encoding = "0123456789ABCDEF"

-- list of operations
ops :: [Stack -> Stack]
ops = [
 b (\x y -> read (show x ++ show y)),-- concatenation
 u (+1), -- increment
 u (subtract 1), -- decrement
 b (*), -- multiplication
 b div, -- division
 b (+), -- addition
 b (-), -- subtraction
 b (^), -- exponent
 b mod, -- modulus
 (\s -> last s : init s), -- rotate right
 (\(x:t) -> t ++ [x]), -- rotate left
 (\(x:t) -> x:x:t), -- duplicate
 (\(x:y:t) -> x:y:x:y:t), -- double duplicate
 (\(x:y:t) -> y:x:t), -- swap
 (\(x:y:x':y':t) -> x':y':x:y:t), -- double swap
 tail] -- pop

run :: String -> Maybe Stack
run code = run' code [0] where
  run' [] stack = Just stack
  run' (x:t) stack = elemIndex x encoding >>= run' t . ($stack) . (ops!!)

```

Running

```
λ: run "diidt^svz"
Just [2,0,1,4]

```
> 1 votes

# Answer
# Common Lisp - 589

Accepts hex input without spaces.

```
(setf w'(0))(defmacro u(&rest b)`(let((a(pop w))(b(pop w))),@b))(defmacro v(s)`(u(push(funcall ,s b a)w)))(setf i(list'(u(push(parse-integer(append(write-to-string b)(write-to-string a)))w))'(incf(car w))'(decf(car w))'(v #'*)'(v #'/)'(v #'+)'(v #'-)'(v #'expt)'(v #'%)'(let((a (car(last w))))(nbutlast w)(push a w))'(let((a(pop w)))(nconc w(list a)))'(push(car w)w)'(progn(push(cadr w)w)(push(cadr w)w))'(u(push a w)(push b w))'(u(push a(cdr(nthcdr 2 w)))(push b(cdr(nthcdr 2 w))))'(pop w)))(mapcar(coerce(read-line)'list)(lambda(a)(eval(nth(parse-integer(string a):radix 16)i)))(print w)

```

Ungolfed:

```
(defparameter *stack* '(0))

(defmacro topvalues (&rest body)
    `(let ((top1 (pop *stack*))
           (top2 (pop *stack*))) ,@body))

(defmacro simple-op (opsym &rest body)
    `(topvalues
        (push (funcall ,opsym top2 top1) *stack* )))

(defparameter *ops*
    (list
        ;concatenate
        '(topvalues
            (push
                (parse-integer (append (write-to-string b) (write-to-string a)))
                *stack*))

        ;increment
        '(incf (first *stack*))

        ;decrement
        '(decf (first *stack*))

        ;multiply
        '(simple-op #'*)

        ;divide
        '(simple-op #'/)

        ;add
        '(simple-op #'+)

        ;subtract
        '(simple-op #'-)

        ;exponent
        '(simple-op #'expt)

        ;modulus
        '(simple-op #'%)

        ;rotate right
        '(let ((a (car (last *stack*))))
            (nbutlast *stack*)
            (push a *stack*))

        ;rotate left
        '(let ((a (pop *stack*)))
            (nconc *stack* (list a)))

        ;duplicate
        '(push (first *stack*) *stack*)

        ;double duplicate
        '(progn
            (push (second *stack*) *stack*)
            (push (second *stack*) *stack*))

        ;swap
        '(topvalues
            (push top1 *stack*)
            (push top2 *stack*))

        ;double swap
        '(topvalues
            (push top1 (cdr (nthcdr 2 *stack*)))
            (push top2 (cdr (nthcdr 2 *stack*))))

        ;delete/pop
        '(pop *stack*)))

(mapcar
(lambda (a)
    (eval (nth (parse-integer (string a) :radix 16) *ops*)))
(coerce (read-line) 'list))

```
> 1 votes

# Answer
## PHP

it's not the prettiest one, but it works.

runs from shell, expects a filename as first argument. it accepts any of the 3 dialects (even mixed)

behaviour not defined for negatives or missing index

```
<?php
$f[0] = $f[48] = $f[36] = function(&$s){$v=array_shift($s);$s[0] .= $v;};
$f[1] = $f[49] = $f[105] = function(&$s){$s[0]++;};
$f[2] = $f[50] = $f[118] = function(&$s){$s[0]--;};
$f[3] = $f[51] = $f[42] = function(&$s){$v = array_shift($s); $s[0] *= $v;};
$f[4] = $f[52] = $f[47] = function(&$s){$v = array_shift($s); $s[0] = intval(floor($s[0] / $v));};
$f[5] = $f[53] = $f[43] = function(&$s){$v = array_shift($s); $s[0] += $v;};
$f[6] = $f[54] = $f[45] = function(&$s){$v = array_shift($s); $s[0] -= $v;};
$f[7] = $f[55] = $f[94] = function(&$s){$v = array_shift($s); $s[0] = pow($s[0], $v);};
$f[8] = $f[56] = $f[37] = function(&$s){$v = array_shift($s); $s[0] %= $v;};
$f[9] = $f[57] = $f[62] = function(&$s){$v = array_pop($s); array_unshift($s, $v);};
$f[10] = $f[65] = $f[60] = function(&$s){$v = array_shift($s); array_push($s, $v);};
$f[11] = $f[66] = $f[100] = function(&$s){array_unshift($s, $s[0]);};
$f[12] = $f[67] = $f[116] = function(&$s){$v = [$s[0], $s[1]]; array_unshift($s, $v[0], $v[1]);};
$f[13] = $f[68] = $f[115] = function(&$s){$v = $s[0]; $s[0] = $s[1]; $s[1] = $v;};
$f[14] = $f[69] = $f[122] = function(&$s){$v = $s[0]; $s[0] = $s[2]; $s[2] = $v; $v = $s[1]; $s[1] = $s[3]; $s[3] = $v;};
$f[15] = $f[70] = $f[46] = function(&$s){array_unshift($s);};

$stack = [0];
$file = fopen($argv[1], 'rb');
$size = filesize($argv[1]);
while($size--){
    $f[ord(fread($file, 1))]($stack);
}
fclose($file);
echo '['.implode(',',$stack)."]\n";

```
> 1 votes

# Answer
# PureBasic - 2821 891 chars

This is an interactive interpreter - no file, you just enter the codes given 0-9, A-F, and it will execute that command, and display as the example post displays it.

Use "X" or "Q" to quit.

This was really fun to do :)

```
Global NewList ProgramStack.q()
Global Num1.q, Num2.q

Macro Push(Value)
  LastElement(ProgramStack())
  AddElement(ProgramStack())
  ProgramStack() = Value
EndMacro

Macro Pop(Variable)
  LastElement(ProgramStack())
  Variable = ProgramStack()
  DeleteElement(ProgramStack())
EndMacro

Macro Peek(Variable)
  LastElement(ProgramStack())
  Variable = ProgramStack()
EndMacro

Push(0)

Procedure Concatenate()
  Pop(Num1)
  Pop(Num2)

  Push(Val( Str(Num2) + Str(Num1) ))
EndProcedure

Procedure Increment()
  LastElement(ProgramStack())
  ProgramStack() + 1
EndProcedure

Procedure Decrement()
  LastElement(ProgramStack())
  ProgramStack() - 1
EndProcedure

Procedure Multiply()
  Pop(Num1)
  Pop(Num2)

  Push( Num2 * Num1 )
EndProcedure

Procedure Divide()
  Pop(Num1)
  Pop(Num2)

  Push( Num2 / Num1 )
EndProcedure

Procedure Add()
  Pop(Num1)
  Pop(Num2)

  Push( Num2 + Num1 )
EndProcedure

Procedure Subtract()
  Pop(Num1)
  Pop(Num2)

  Push( Num2 - Num1 )
EndProcedure

Procedure Exponent()
  Pop(Num1)
  Pop(Num2)

  Push( Pow(Num2, Num1) )
EndProcedure

Procedure Modulus()
  Pop(Num1)
  Pop(Num2)

  Push( Mod(Num2, Num1) )
EndProcedure

Procedure RotateRight()
  FirstElement(ProgramStack())
  Num1 = ProgramStack()
  DeleteElement(ProgramStack(),1)
  Push(Num1)
EndProcedure

Procedure RotateLeft()
  Pop(Num1)
  FirstElement(ProgramStack())
  InsertElement(ProgramStack())
  ProgramStack() = Num1
EndProcedure

Procedure Duplicate()
  Peek(Num1)
  Push(Num1)
EndProcedure

Procedure DoubleDuplicate()
  Pop(Num1)
  Pop(Num2)
  Push(Num2)
  Push(Num1)
  Push(Num2)
  Push(Num1)
EndProcedure

Procedure SingleSwap()
  Pop(Num1)
  Pop(Num2)
  Push(Num1)
  Push(Num2)
EndProcedure

Procedure DoubleSwap()
  Protected Num3.q, Num4.q
  Pop(Num1)
  Pop(Num2)
  Pop(Num3)
  Pop(Num4)
  Push(Num2)
  Push(Num1)
  Push(Num4)
  Push(Num3)
EndProcedure

Procedure Delete()
  Pop(Num1)
EndProcedure

OpenConsole()
EnableGraphicalConsole(1)

Position = 0
Repeat
  ConsoleLocate(Position, 0)

  e.s = UCase( Inkey() )

  Select e
    Case "0"
      Concatenate()
    Case "1"
      Increment()
    Case "2"
      Decrement()
    Case "3"
      Multiply()
    Case "4"
      Divide()
    Case "5"
      Add()
    Case "6"
      Subtract()
    Case "7"
      Exponent()
    Case "8"
      Modulus()
    Case "9"
      RotateRight()
    Case "A"
      RotateLeft()
    Case "B"
      Duplicate()
    Case "C"
      DoubleDuplicate()
    Case "D"
      SingleSwap()
    Case "E"
      DoubleSwap()
    Case "F"
      Delete()
  EndSelect

  If e <> ""
    Print(e)
    ConsoleLocate(Position, 1)
    Print("|")
    yLoc.i = ListSize(ProgramStack()) + 1

    ForEach ProgramStack()
      ConsoleLocate(Position, yLoc)
      Print(Str(ProgramStack()))
      yLoc - 1
    Next

    Position + 2
  EndIf
Until e = "X" Or e = "Q"

```

edit: After sleeping, I figured I'd golf it - I've left the readable version though for referencce.

Everything works the same except I've taken out the Q or X to quit, just close the window to quit:

```
NewList S()
Macro P
Print
EndMacro
Macro G
ConsoleLocate
EndMacro
Macro LE
LastElement(S())
EndMacro
Macro U(V)
LE
AddElement(S())
S()=V
EndMacro
Macro O(V)
LE
V=S()
DeleteElement(S())
EndMacro
U(0)
OpenConsole()
EnableGraphicalConsole(1)
X=0
Repeat
G(X,0)
e.s=UCase(Inkey())
Select e
Case"0"
O(H)
O(J)
U(Val(Str(J)+Str(H)))
Case"1"
LE
S()+1
Case"2"
LE
S()-1
Case"3"
O(H)
O(J)
U(J*H)
Case"4"
O(H)
O(J)
U(J/H)
Case"5"
O(H)
O(J)
U(J+H)
Case"6"
O(H)
O(J)
U(J-H)
Case"7"
O(H)
O(J)
U(Pow(J,H))
Case"8"
O(H)
O(J)
U(Mod(J,H))
Case"9"
FirstElement(S())
H=S()
DeleteElement(S(),1)
U(H)
Case"A"
O(H)
FirstElement(S())
InsertElement(S())
S()=H
Case"B"
O(H)
U(H)
U(H)
Case"C"
O(H)
O(J)
U(J)
U(H)
U(J)
U(H)
Case"D"
O(H)
O(J)
U(H)
U(J)
Case"E"
O(H)
O(J)
O(K)
O(L)
U(J)
U(H)
U(L)
U(K)
Case"F"
O(H)
EndSelect
If e<>""
P(e)
G(X,1)
Y=ListSize(S())+1
ForEach S()
G(X,Y)
P(Str(S()))
Y-1
Next
X+2
EndIf
ForEver

```
> 1 votes

# Answer
# Common Lisp - 586

```
(defmacro n(s)(with-gensyms($)(labels((?()`(pop,$))(!(x)`(push,x,$))(@(~)(!(list ~(?)(?))))(r@(~)(@`(lambda(x y)(,~ y x)))))`(let((,$`(,0))),@(loop for p below(length s)collect(case(parse-integer s :start p :end(1+ p):radix 16)(0(@'(lambda(a b)(+(* a(expt 10(if(> b 0)(ceiling(log b 10))1)))b))))(1`(incf(car,$)))(2`(decf(car,$)))(3(@'*))(4(@'/)) (5(@'+))(6(@'-))(7(r@'expt))(8(r@'mod))(9`(setf,$(#1=rotate,$)))(10`(setf,$(#1#,$ -1)))(11`(push(car,$),$))(12`(setf,$(nconc(#2=subseq,$ 0 2),$)))(13`(reversef(#2#,$ 0 2)))(14`(setf,$(append(#1#(#2#,$ 0 4)2)(#2#,$ 4))))(15`(pop,$)))),$))))

```

# Ungolfed

Lexically binds a fresh stack in the macroexpanded code: no reference to a global variable. Also, it is compiled down to machine code.

```
(ql:quickload :alexandria)
(mapc #'use-package '(cl alexandria))
(defmacro n(s)
  (with-gensyms($)
    (labels ((?()`(pop,$))
             (!(x)`(push,x,$))
             (bop(op)(!(list op(?)(?))))
             (rbop(op)(bop`(lambda(x y)(,op y x)))))
      `(let((,$`(,0)))
         ,@(loop for p below(length s)
                 collect(case(parse-integer s :start p :end(1+ p):radix 16)
                           (#x0(bop'(lambda(a b)(+(* a(expt 10(if(> b 0)(ceiling(log b 10))1)))b))))
                           (#x1`(incf(car,$)))
                           (#x2`(decf(car,$)))
                           (#x3(bop'*))
                           (#x4(bop'/))
                           (#x5(bop'+))
                           (#x6(bop'-))
                           (#x7(rbop'expt))
                           (#x8(rbop'mod))
                           (#x9`(setf,$(rotate,$)))
                           (#xA`(setf,$(rotate,$ -1)))
                           (#xB`(push(car,$),$))
                           (#xC`(setf,$(nconc(subseq,$ 0 2),$)))
                           (#xD`(reversef(subseq ,$ 0 2)))
                           (#xE`(setf,$(append(rotate(subseq,$ 0 4)2)(subseq,$ 4))))
                           (#xF`(pop,$))))
         ,$))))

```

# Example

```
   (n "11bc5c5b95")
   => macroexpands into (8 6 4 2)

```
> 1 votes

# Answer
# Python 2, 508 bytes

```
s,d=[0],lambda:s.pop(1)
for C in raw_input():
 D=int(C,16)
 if D<1:s[0]=int(`s[0]`+`d()`)
 if D==1:s[0]+=1
 if D==2:s[0]-=1
 if D==3:s[0]*=d()
 if D==4:s[0]=d()/s[0]
 if D==5:s[0]+=d()
 if D==6:s[0]-=d()
 if D==7:s[0]=d()**s[0]
 if D==8:s[0]=d()%s[0]
 if D==9:s=s[-1:]+s[:-1]
 if D==10:s=s[1:]+s[:1]
 if D==11:s=s[:1]+s
 if D==12:s=s[0:2]+s
 if D==13:s=s[1:2]+s[:1]+s[2:]
 if D==14:s=s[2:4]+s[0:2]+s[4:]
 if D>14:s=s[1:]
print s

```

Uses "0123456789ABCDEF" encoding. I'm really proud in how this one turned out. It doesn't read file, it gets input from STDIN, but if that's a problem it could easily be changed.

2 solutions for the 2014 problem:

`B11CB3A1AED0A00` (~~16~~ 15 bytes) - Generic Concatenator.

`BB102CD11B513B3622E` (~~20~~ 19 bytes) - Much cooler - Evaluates to (5\*(10-1))^2-11
> 1 votes

# Answer
# Python 2, 955 bytes

```
import sys
global s
s=[0]
c=lambda x: x.append(str(x.pop())+str(x.pop()))
i=lambda x: x.append(x.pop()+1)
v=lambda x: x.append(x.pop()-1)
x=lambda x: x.append(x.pop()*x.pop())
q=lambda x: x.append(x.pop(-2)/x.pop())
a=lambda x: x.append(x.pop()+x.pop())
w=lambda x: x.append(x.pop(-2)-x.pop())
e=lambda x: x.append(x.pop(-2)**x.pop())
m=lambda x: x.append(x.pop(-2)%x.pop())
r=lambda x: x.append(x.pop(0))
l=lambda x: x.insert(0,x.pop())
d=lambda x: x.append(x[-1])
t=lambda x: x.extend(x[-2:])
s=lambda x: x.insert(-2,x.pop())
def z(x):
    for y in [0,1]:
        s.insert(-3,s.pop())
k={'$':c,'i':i,'v':v,'*':x,'/':q,'+':a,'-':w,'^':e,'%':m,'>':r,'<':l,'d':d,
   't':t,'s':s,'z':z,'.':lambda x: x.pop()}
if __name__=='__main__':
    with open(sys.argv[1],'r') as f:
        while 1:
            b=f.read(1)
            if not b or b not in k.keys():
                break
            else:
                n=k[b](s)
                for x in s: print s,

```

# What each function does

* **c:** concatenate ($)
* **i:** increment (i)
* **v:** decrement (v)
* **x:** multiply (\*)
* **q:** divide (/)
* **a:** add (+)
* **w:** subtract (-)
* **e:** exponent (^)
* **m:** modulo (%)
* **r:** right shift (\>)
* **l:** left shift (\<)
* **d:** duplicate (d)
* **t:** duplicate twice (t)
* **s:** swap top 2 values (s)
* **z:** double swap (z)
> 0 votes

---
Tags: popularity-contest, interpreter, stack
---


title: Can you find the villain's password?

text:
# Question
Title: Can you find the villain's password?
### Background

You work for the police force as a programmer.

A villain has planted a bomb in the city, luckily the police force has captured both him and the bomb. The bomb is really complicated to disarm, however it has a password input to disarm it.

The villain, being cocky, has told you that there was no way you'd find the password as you'd take X time to brute force it. You notice that the keyboard can only input english letters (lower and upper case) and digits.

### Task

Assuming you can try Y passwords per second, and that the brute force character order would be `a-z A-Z 0-9`, you are to create either a full program or a function that takes as input both X (in seconds) and Y (passwords/second) and outputs the villain's password.

X can be a float but Y will always be an integer.
**(X\*Y should always be an integer)**

Your code has to solve the problem using math instead of relying on trying several options or creating huge arrays and simply indexing them with X\*Y.

### Example in JS

```
var c="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
var b=62;
function num(x){
    var n=0;
    while(x>=0){
        x-=Math.pow(b,++n);
    }
    return n;
}
function reduce(x, n){
    while(--n>0){
        x-=Math.pow(b,n);
    }
    return x;
}
function pass(x, y){
    x=x*y;
    x--;
    var p=[];
    var n=num(x);
    x = reduce(x, n);
    do{
        var t=x%b;
        x=(x-t)/b;
        p.unshift(t);
    }while(x>0);
    return ("a".repeat(n)+p.map(f=>c[f]).join``).substr(-n);
}

```

Assuming my code is correct here are some example outputs.
**(If there are any errors please tell me so that I can correct them)**

```
pass(0.000, 1000); // "" or anything that won't be mistaken for a password
pass(0.001, 1000); // "a"
pass(0.002, 1000); // "b"
pass(0.027, 1000); // "A"

//A password that would take a year to brute force at 1000 passwords/second
pass(3600*24*365, 1000) // "HzmZmr"

```

My code is awful and ungolfed but it's only to serve as an example. Since this is code-golf shortest answer in bytes wins.

# Answer
> 4 votes
# Jelly, 9 bytes

```
×ḃ62ịØWŒs

```

**Try it online!**

### How?

```
×ḃ62ịØWŒs - Main link: X, Y
×         - multiply X by Y
 ḃ62      - convert to bijective base 62 (uses modulo arithmetic under the hood)
    ị     - index into (1-based)
     ØW   - word yield -> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_"
       Œs - swap case

```

# Answer
> 1 votes
# Python 2, 121 bytes

```
x,y=input()
r=range;b=map(chr,r(97,123)+r(65,91)+r(48,58))
i=int(x*y)
p=b[i%62]
while i/62>0:i=i/62-1;p=b[i%62]+p
print p

```

Try it online!

This basically calculate the `x*y` in base 62
For a recursive solution at 125 bytes

```
x,y=input()
r=range;b=map(chr,r(97,123)+r(65,91)+r(48,58))
f=lambda i:(f(i/62)if~-i/62>0else'')+b[i%62-1]
print f(int(x*y)+1)

```

Try it online!

---
Tags: code-golf
---


# Question
Title: For a given period, getting the smallest list of dates, using jokers
Consider a date formatted in `YYYY-MM-DD`. You can use the joker `*` at the end of the date string. E.g. `2016-07-2*` describes all the dates from `2016-07-20` to `2016-07-29`.

Now, consider a period represented by a start date and an end date.

The algorithm must find the smallest possible list of dates representing the period.

Let's use an exemple. For the following period:

* start date: `2014-11-29`
* end date: `2016-10-13`

The algorithm must return an array containing the following list of dates:

* `2014-11-29`
* `2014-11-30`
* `2014-12-*`
* `2015-*`
* `2016-0*`
* `2016-10-0*`
* `2016-10-10`
* `2016-10-11`
* `2016-10-12`
* `2016-10-13`

# Answer
# PHP, ~~541~~ 343 bytes

I wanted to get the algorithm working in the first place; but golfing it down was actually far more fun than I expected (especially browsing the supported date & time formats).

Three major actions saved about 130 bytes; but the 70 bytes from minor golfings
(which also rendered one of the large steps obsolete) carried a lot of fun.

```
for($a=($f=strtotime)($argv[1]);!$p=$a>$z=$f($argv[2]);$a+=86400){$x=$z<$e=$f(Dec31,$a);(101<$q=date(md,$a))?$q-1001|$x?:$a=$e+$p="1*":($x?($t=$f(IX30,$a))>$z?:$a=$t+$p="0*":$a=$e+$p="*");$p?:($q%100>1|$z<($t=$f(date(Ymt,$a)))?$q%10>0&$q%100>1|$z<($t=min($t,$a+777600))?:$a=$t+$p="m-$q[2]*":$a=$t+$p="m-*");echo date("Y-".($p?:"m-d"),$a),"
";}

```

takes input from command line arguments. Run with `-nr`or test it online.

**notes**

* prints `Y-m-3*` for `Y-m-30`; add 7 bytes to fix: Insert `|$a==$t` after `777600))`.
* throws warnings in PHP 7.1; add 5 bytes to fix: Replace `+$p` with `+!$p`.
* A breakdown and some golfings explained are ready to be posted;
but I´ll wait a bit to see if someone else submits before I spoil.
> 1 votes

---
Tags: code-golf, date
---


# Question
Title: Give me your tired, your poor, Your huddled masses yearning to breathe free
A bronze plaque in the pedestal of the Statue of Liberty displays the poem "The New Colossus" by Emma Lazarus, part of which reads:

> Give me your tired, your poor,
> Your huddled masses yearning to breathe free,
> The wretched refuse of your teeming shore.
> Send these, the homeless, tempest-tost to me,
> I lift my lamp beside the golden door!

To simplify this section of the poem for this challenge, we'll make it all uppercase and replace the newlines with slashes (`/`), keeping commas and other punctuation as is:

```
GIVE ME YOUR TIRED, YOUR POOR,/YOUR HUDDLED MASSES YEARNING TO BREATHE FREE,/THE WRETCHED REFUSE OF YOUR TEEMING SHORE./SEND THESE, THE HOMELESS, TEMPEST-TOST TO ME,/I LIFT MY LAMP BESIDE THE GOLDEN DOOR!

```

We'll call this string S. It has md5 hash `8c66bbb9684f591c34751661ce9b5cea`. You may optionally assume it has a trailing newline, in which case the md5 hash is `0928ff6581bc207d0938b193321f16e6`.

Write a program or function that takes in a single string. When the string is S, output *in order*, one per line, the six phrases that describe the type of people the poem depicts Lady Liberty asking for:

```
TIRED
POOR
HUDDLED MASSES YEARNING TO BREATHE FREE
WRETCHED REFUSE OF YOUR TEEMING SHORE
HOMELESS
TEMPEST-TOST

```

(This precise string, optionally followed by a single trailing newline, must be your output for input S.)

For *at least one* input string that is *not* S, your output should be any string other than the six lines above. This could be as simple as outputting only `TIRED` if the input is only `GIVE ME YOUR TIRED`. This rule is to prevent pure hardcoding. Otherwise, when the input string is not S, your code may do anything.

This is essentially a constant-output challenge where you are given an input that is relatively close to the output. You could of course mostly ignore the input and hardcode the output, but it may be better to, say, strip out the substrings of the input needed for the output.

For reference, here are the zero-based indices and lengths of the six output lines in S:

```
13 5, 25 4, 36 39, 81 37, 136 8, 146 12

```

**The shortest code in bytes wins.**

# Answer
> 9 votes
# Jelly, 19 bytes

```
Ẇ“©ØḌKAƑ⁶2ɼU’b8ȷ¤ịY

```

**Try it online!** or try it with some other text.

### How?

Indexes into the list of all non-empty contiguous slices of the input string and joins with line feeds.

```
Ẇ“©ØḌKAƑ⁶2ɼU’b8ȷ¤ịY - Main link: s
                ¤   - nilad followed by link(s) as a nilad
 “©ØḌKAƑ⁶2ɼU’       - base 250 number, 27003436588466956354336
              8ȷ    - 8 * 1e3 = 8000
             b      - convert to base, [824,635,7086,6796,1544,2336]
                 ị  - index into
Ẇ                   - all non-empty contiguous slices of s
                  Y - join with line feeds

```

---

Previous code, 22 bytes:

```
“ÇŒȷœ%LRw⁹ƊƓɠ‘ṬœṗµḊm2Y

```

Partitions the input string, takes every second element and joins with line feeds. `“ÇŒȷœ%LRw⁹ƊƓɠ‘` is a list of code page indexes,  makes a list of zeros with ones at those indexes, `œṗ` partitions the input at the truthy indexes of that list,  removes the first element, `m2` takes every second element, and `Y` joins with line feeds.

# Answer
> 7 votes
## JavaScript (ES6), ~~128~~ 69 bytes

May output empty lines or some garbage when the input is different from `S`.

```
let f =

s=>[837,1604,2343,5221,8712,9356].map(n=>s.substr(n>>6,n&63)).join`
`

console.log(f(`GIVE ME YOUR TIRED, YOUR POOR,
YOUR HUDDLED MASSES YEARNING TO BREATHE FREE,
THE WRETCHED REFUSE OF YOUR TEEMING SHORE.
SEND THESE, THE HOMELESS, TEMPEST-TOST TO ME,
I LIFT MY LAMP BESIDE THE GOLDEN DOOR!`))

console.log(f(`THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG`))
```

# Answer
> 7 votes
# Bash, ~~76~~ ~~65~~ 60 bytes

```
echo "TIRED
POOR
${1:36:39}
${1:81:37}
HOMELESS
${1:146:12}"

```

Try it online!

# Answer
> 3 votes
## *Mathematica*, 71

```
Column@StringTake[#,List@@@{14|18,26|29,37|75,82|118,137|144,147|158}]&

```

# Answer
> 2 votes
# PowerShell, 72 bytes

```
"$args"-split'[/,.]'-replace'^.*?(YOUR|\bTHE) |^ | TO ME'-match'^[^S G]'

```

Try it online!

### Explanation

This is a pretty crappy regex solution.

Splitting the string into an array on `/` or `.` or `,` and then replacing parts of each string that match the first pattern, which gives an array of `-replace`d strings, then use the `-match` operator to return an array of the elements that match the second pattern (which gets rid of the blank lines and 2 lines that didn't get filtered before).

# Answer
> 1 votes
# Mathematica, 86 bytes

```
Riffle[s=#;s~Take~#&/@{{14,18},{26,29},{37,75},{82,118},{137,144},{147,158}},"
"]<>""&

```

Unnamed function taking a list of characters as input and returning a string. Just extracts the relevant substrings of the input and concatenates with newlines.

# Answer
> 0 votes
# TI-Basic, 58 bytes

Very straightforward. `Disp` is like `println`, so there are newlines in between.

```
Disp "TIRED","POOR",sub(Ans,37,39),sub(Ans,82,37),"HOMELESS",sub(Ans,147,12

```

# Answer
> 0 votes
# Retina, 38 32 bytes

It can probably be improved, but this is a job for regexes!

```
!`(?<=R |HE ).*?(?=[,.])|\w+-\w+

```

Try it online!

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


title: Is it within the Cantor set?

text:
# Question
Title: Is it within the Cantor set?
# The Challenge

For this challenge, you are supposed to determine if a given number is in the Cantor set. So first, let's define the Cantor set.

First, start with the numbers between 0 and 1. Any numbers outside this range are not in the Cantor set. Now, let's divide the numbers into three equal parts: \[0,1/3\], \[1/3,2/3\], \[2/3, 1\]. Any numbers not inside the ranges of the first and last parts are not in the Cantor set. Now, you repeat this process for the segments \[0,1/3\] and \[2/3, 1\]. Then you repeat on what is leftover. You keep on doing this forever. In the end, all numbers that are remaining are in the Cantor set. Here is a diagram of the first six iterations:

---

# Input

Two integer `x` and `y`.
`0 < y < 2^15`
`0 <= x <= y`
The greatest common denominator of `x` and `y` is 1, unless `x == 0`.

---

# Output

Truthy if `x/y` is in the Cantor set.
Falsy if `x/y` is not in the Cantor set.

---

# Examples

Now, let's see some examples of numbers that are in the Cantor set.

```
1/3 -> true

```

It is on a boundary, and boundaries are never removed.

```
1/4 -> true

```

`1/4` is never in the middle third of a segment, though it is never on the boundary either. If you follow it's path, you will actually find that it alternates between being in the first and last thirds of a section.

```
1/13 -> true

```

`1/13` alternates between the first, first, and last sections.

```
1/5 -> false

```

`1/5` falls into the first empty block of the third row in the above diagram, between 1/9 and 2/9.

Other test cases:

```
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false

```

You can try other numbers with this snippet:

```
function isCantor(t,r){var n=new Set;if(0>r)return isCantor(-t,-r);if(0==r)return!1;if(0>t||t>r)return!1;for(;;){if(t%r===0)return!0;if(1===Math.floor(t/r))return!1;if(n.has(t))return!0;n.add(t),t=t%r*3}}$("#test").click(function(){var t=parseInt($("#x").val()),r=parseInt($("#y").val());if(isNaN(t)||isNaN(r)||0==r)return void $("#result").text("Invalid input");var n=isCantor(t,r),i=(n?"I":"Not i")+"n the Cantor set.";$("#result").text(i)});
```

```
input{width:30px}button{margin-left:7px}
```

```
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><input id=x>/<input id=y><button id=test>Test</button><p id=result>
```

---

# Objective

The person with the least bytes wins.

# Answer
# Mathematica, 54 bytes

```
If[Last@#===1,Most@#,#]&@RealDigits[#,3][[1]]~FreeQ~1&

```

Unnamed function taking a fraction `x/y` as input, where `y > 0` and `0 ≤ x ≤ y`, and returning `True` or `False`.

A real number between 0 and 1 is in the Cantor set precisely when none of the digits in its base-3 expansion equals 1; the exception is that a fraction whose denominator is a power of 3 (whose base-3 expansion therefore terminates) is allowed to end in a 1.

`RealDigits[#,3][[1]]` gives all of the digits in the base-3 expansion of the fractional input `#`, in a form like `{1, 0, 2, {0, 1, 0, 2}}`: the last list is the periodic part of the expansion, while the integers beforehand are the digits before the periodicity starts. If the base-3 expansion is periodic right away, the output is like `{{0, 1, 0, 2}}`; if the base-3 expansion terminates, the form is like `{1, 0, 2}`.

So we want to check, using `~FreeQ~1`, whether the list is free of `1`s or not. However, because of the terminating expansion thing, we want to delete the last element of the list if it equals `1`; that's what `If[Last@#===1,Most@#,#]` accomplishes. (The `===` is needed to compare a potential list with `1`: `==` alone remains unevaluated in that situation.)
> 13 votes

# Answer
# C (gcc), ~~61~~ ~~59~~ 58 bytes

```
f(x,y,i){for(i=y;i--&&x<y;)x=(y-x<x?y-x:x)*3;return x<=y;}

```

Exploits the symmetry of the Cantor set. Breaks after `y` iterations to avoid an infinite loop.

Try it online!
> 9 votes

# Answer
# Jelly, ~~22~~ ~~17~~ ~~16~~ 15 bytes

```
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ

```

Prints **3** for truthy, nothing for falsy.

Try it online!

### Background

A well-known property of the Cantor set is that it contains precisely those numbers between **0** and **1** that can be written without **1**'s in their ternary expansion.

Note that some numbers – precisely the right edges of the closed intervals involved in the set's construction – can be written either with a single (trailing) **1** or with an infinite amount of trailing **2**'s. For example, **1 = 13 = 0.22222…3** and **1/3 = 0.13 = 0.022222…3**, just as **0.510 = 0.499999…10**.

To avoid special-casing the right edges, we can check for **1**'s is the shortest decimal expansion in both **x/y** and **1 - x/y = (y - x)/y**, where **x/y** is a right edge iff **(y - x)/y** is a left edge. If at least one of them contains no **1**'s, **x/y** belongs to the Cantor set.

### How it works

```
,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ  Main link. Left argument: x. Right argument: y

 ạ               Absolute difference; yield y - x.
,                Pair; yield [x, y - x].
       µ         Begin a new, monadic chain with argument [a, b] := [x, y - x].
  µ     ÐĿ       Repeatedly execute the links in between until the results are no
                 longer unique, updating a and b after each execution. Return the
                 array of all unique results.
   %⁹              Compute [a % y, b % y].
     ×3            Compute [3(a % y), 3(b % y)].
                 This yields all unique dividends of the long division of x by y in
                 base 3.
          :⁹     Divide all dividends by y to get the corresponding ternary digits.
            Ḅ    Unbinary; turn [1, 1] into 3, other pairs into other numbers.
             3ḟ  Remove all occurrences of the resulting numbers from [3], leaving
                 an empty array if and only if one pair [a, b] is equal to [1, 1].

```
> 7 votes

# Answer
# JavaScript (ES6), 65 ~~67~~

**Edit** 2 bytes saved thx @Luke

```
n=>d=>(z=>{for(q=0;~-q*n*!z[n];n=n%d*3)z[n]=1,q=n/d|0})([])|q!=1|!n

```

*Less golfed*

```
n=>d=>{
  z = []; // to check for repeating partial result -> periodic number
  for(q = 0; q != 1 && n != 0 && !z[n]; )
    z[n] = 1,
    q = n / d | 0,
    n = n % d * 3
  return q!=1 | n==0
}

```

**Test**

```
f=
n=>d=>(z=>{for(q=0;~-q*n*!z[n=n%d*3];q=n/d|0)z[n]=1})([])|q!=1|!n

console.log(
'Truthy: 1/3 1/4 1/13 0/4 3/10 3/4 10/13 1/1\nFalsey: 1/5 12/19 5/17 3/5 1/7 1/2'.replace(/(\d+).(\d+)/g,(a,x,y)=>a+':'+f(x)(y))
)
```
> 3 votes

# Answer
## JavaScript (ES6), 55 bytes

```
y=>f=(x,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,z|q==1,n+1):1

```

Use by currying in the denominator first and the numerator second. The standard form is a byte longer:

```
f=(x,y,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,y,z|q==1,n+1):1

```

### Explanation

If a fraction is not in the Cantor set, it must fall into one of the middle sections at some point; therefore, its representation in base 3 must contain a 1 followed at some point by a non-zero digit. That's how this works:

* `z` keeps track of whether we've found a 1.
* `q` is the current digit in base 3.
* `!z|!q` is true if `z` is false (we have not found a 1) or `q` is false (the current digit is 0).

If `n` runs down to zero before we find a non-zero digit somewhere after a 1, the fraction is in the Cantor set and we return `1`.
> 2 votes

# Answer
# Bash \+ GNU utilities, 62 bytes

```
dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"

```

Try it online!

Pass it two integer arguments with arg1 \<= arg2 and 0 \< arg2.

The output is returned in the exit code (0 for falsy, 1 for truthy), as allowed by PPCG I/O methods.

I suspect the regex can be golfed further, maybe even eliminating the tr command in favor of using grep -z, but this is the shortest I've been able to come up with. (Unfortunately, grep -z is incompatible with grep -P, and the -P option to get perl-style regexes is required for the ?! syntax.)

Testbed program and output:

```
for x in '1 3' '1 4' '1 13' '1 5' '0 4' '3 10' '3 4' '10 13' '1 1' '12 19' '5 17' '3 5' '1 7' '1 2'
  do
    printf %-6s "$x "
    ./cantor $x >/dev/null && echo F || echo T
  done

1 3   T
1 4   T
1 13  T
1 5   F
0 4   T
3 10  T
3 4   T
10 13 T
1 1   T
12 19 F
5 17  F
3 5   F
1 7   F
1 2   F

```

---

**Explanation**

dc part (the arguments are x and y):

```
3o     Set output base to 3.
9      Push 9 on the stack.
d      Duplicate the top of the stack. (The extra 9 on the stack isn't actually used, but I need some delimiter in the code here so that the 9 doesn't run into the number coming up next.  If I used a space as a no-op, then I'd need to quote it for the shell, adding an extra character.)
$2^    Raise 9 to the y power. This number in base 3 is 1 followed by 2y 0's.
$1*$2/ Multiply the base-3 number 10....0 (with 2y 0's in it) by x and then divide by y (truncating). This computes 2y digits (after an implied ternary point) of x/y.  That's enough digits so that the repeating part of the rational number is there at least twice.
p      Print the result, piping it to tr.

```

tr and grep part:

A minor issue is that, although dc handles arbitrarily large integers, when dc prints a large number, it will break it up into 69-character lines, with each line except the last ending with a backslash, and with a newline after each line.

The tr command deletes any backslashes and newlines. This leaves just a single line.

The grep command then uses a perl-style regex (-P option, which is a GNU extension). The regex matches if the line contains a 1 not followed by at least y 0's or at least y 2's which then end the string.

This is exactly what's needed to identify x/y as not being in the Cantor set, because the repeating part of the base-3 representation of the rational number x/y can be viewed as starting at digit #y+1 after the ternary point, and is at most y digits long.
> 2 votes

# Answer
## CJam (19 bytes)

```
{_@3@#*\/3b0-W<1&!}

```

Online test suite

This is an anonymous block (function) which takes two arguments on the stack and leaves `0` or `1` on the stack. It works by base converting the fraction `x/y` into `y` base `3` digits and returning true iff they contain no `1` or the only `1` is part of a suffix `1 0 0 0 ...`.

```
{            e# Begin a block
  _@3@#*\/3b e#   Base conversion
   0-W<      e#   Remove all zeros and the final non-zero digit
   1&!       e#   True iff no 1s are left
}

```
> 1 votes

# Answer
# Pyth, 14 bytes

```
gu*3hS,G-QGQE0

```

Based on my C solution. `y` on first input line, `x` on second.

```
                Q = y
 u         QE   G = x
                loop y times
  *3                x = 3 *
    hS,G                min(x,
        -QG                 y-x)
g            0  return x >= 0

```

If `x/y` is within the Cantor set, `x` stays between `0` and `y`. Otherwise, `x` becomes greater than `y` at one point, then diverges to negative infinity in the remaining iterations.

Try it online!
> 1 votes

# Answer
## Batch, 91 bytes

```
@set/ai=%3+1,n=%1*3%%%2,f=%1*3/%2%%2,f^|=j=!((%2-i)*n)
@if %f%==0 %0 %n% %2 %i%
@echo %j%

```

Tests the first `y-1` base 3 digits of `x/y`. `i` is the count of digits tested. `n` is the next value of `x`. `j` is true if `n` reaches zero (because the expansion terminates) or we have tested `y-1` digits without finding a `1`. `f` is true if `j` is true or if the next digit is a `1`, at which point we stop looping and output `j`.
> 0 votes

---
Tags: code-golf, math, decision-problem, fractal, rational-numbers
---


# Question
Title: Average distance of two points in unit n-dimensional hypercube
An easy way to understand the unit n-dimensional hypercube is to consider the region of space in n dimensions that you can get if every coordinate component lies in \[0, 1\]. So for one dimension it's the line segment from 0 to 1, for two dimensions it's the square with corners (0, 0) and (1, 1), etc.

Write a program or function that given *n* returns the average Euclidean distance of two points uniformly random selected from the unit n-dimension hypercube. Your answer **must** be within 10-6 of the actual value. It's ok if your answer overflows your language's native floating point type for big n.

***Randomly* selecting a 'big' number of points and calculating the average does not guarantee such accuracy.**

Examples:

> 1 → 0.3333333333...
> 2 → 0.5214054331...
> 3 → 0.6617071822...
> 4 → 0.7776656535...
> 5 → 0.8785309152...
> 6 → 0.9689420830...
> 7 → 1.0515838734...
> 8 → 1.1281653402...

Data acquired from MathWorld.

This is , lowest byte-count wins.

# Answer
> 6 votes
# Mathematica, 68 bytes

```
NIntegrate[(1-((E^-u^2+u*Erf@u√π-1)/u^2)^#)/u^2,{u,0,∞}]/√π&

```

Implementation of the formula using `NIntegrate` to approximate its value.

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


# Question
Title: Convert a logical expression to conjunctive normal form
## Goal:

Write a complete program or function which takes a formula in propositional logic (henceforth referred to as a *logical expression* or *expression*) and outputs that formula in conjunctive normal form. There are two constants,  and  representing true and false, a unary operator `¬` representing negation, and binary operators , , , and  representing implication, equivalence, conjunction, and disjunction, respectively which obey all of the usual logical operations (DeMorgan's law, double negation elimination, etc.).

Conjunctive normal form is defined as follows:

1. Any atomic expression (including  and ) is in conjunctive normal form.
2. The negation of any previously constructed expression is in conjunctive normal form.
3. The disjunction of any two previously constructed expressions is in conjunctive normal form.
4. The conjunction of any two previously constructed expressions is in conjunctive normal form.
5. Any other expression is not in conjunctive normal form.

Any logical expression can be converted (non-uniquely) into a logically equivalent expression in conjunctive normal form (see this algorithm). You do not need to use that particular algorithm.

## Input:

You may take input in any convenient format; e.g., a symbolic logical expression (if your language supports it), a string, some other data structure. You do not need to use the same symbols for true, false, and the logical operators as I do here, but your choice should be consistent and you should explain your choices in your answer if it's not clear. You may not accept any other input or encode any additional information in your input format. You should have some way of expressing an arbitrary number of atomic expressions; e.g. integers, characters, strings, etc.

## Output:

The formula in conjunctive normal form, again in any convenient format. It need not be in the same format as your input, but you should explain if there are any differences.

## Test cases:

```
P ∧ (P ⇒ R) -> P ∧ R
P ⇔ (¬ P) -> ⊥
(¬ P) ∨ (Q ⇔ (P ∧ R)) -> ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R)))

```

## Notes:

1. If the input expression is a tautology,  would be a valid output. Similarly, if the input expression is a contradiction,  would be a valid output.
2. Both your input and output formats should have a well-defined order of operations capable of expressing all possible logical expressions. You may need parentheses of some sort.
3. You may use any well-defined choice of infix, prefix, or postfix notation for the logical operations. If your choice differs from the standard (negation is prefix, the rest are infix), please explain that in your answer.
4. Conjunctive normal form is not unique in general (not even up to reordering). You need only to output *a* valid form.
5. However you represent atomic expressions, they must be distinct from the logical constants, operators, and grouping symbols (if you have them).
6. Built-ins which compute conjunctive normal form are allowed.
7. Standard loopholes are forbidden.
8. This is ; shortest answer (in bytes) wins.

# Answer
> 3 votes
# Maxima, 4 bytes

```
pcnf

```

Try It Online!

You can use `implies`, `eq`, `and`, `or` operators for implication, equivalence, conjunction, and disjunction respectively.

# Answer
> 9 votes
You're going to hate me....

# Mathematica, 23 bytes

```
#~BooleanConvert~"CNF"&

```

The input will use `True` and `False` instead of  and , but otherwise will look very similar to the notation of the question: all of the characters `¬`, , , , and  are recognized in Mathematica (when input with UTF-8 characters 00AC, F523, 29E6, 2227, and 2228, respectively), and parentheses act as you would expect.

By default, the output will use Mathematica's preferred symbols: for example, the last test case will output `(! P || ! Q || R) && (! P || Q || ! R)` instead of `((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R)))`. However, changing the function to

```
TraditionalForm[#~BooleanConvert~"CNF"]&

```

will make the output look pretty and conforming to these usual symbols:

# Answer
> 3 votes
## JavaScript (ES6), 127 bytes

```
f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('+f(s.replace(r,1),t+'|'+p)+')&('+f(s.replace(r,0),t+'|!'+p)+')':eval(s)?1:0+t

```

I/O format is as follows (in order of precedence):

* `(`: `(`
* `)`: `)`
* : `1`
* : `0`
* `¬`: `!`
* : `<=`
* : `==`
* : `&`
* : `|`

Examples:

```
P&(P<=R) -> ((1)&(0|P|!R))&((0|!P|R)&(0|!P|!R))
P==(!P) -> (0|P)&(0|!P)
(!P)|(Q==(P&R)) -> (((1)&(0|P|Q|!R))&((0|P|!Q|R)&(1)))&(((1)&(1))&((1)&(1)))

```

The function is trivially rewritten to produce disjunctive normal form:

```
f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('f(s.replace(r,1),t+'&'+p)+')|('+f(s.replace(r,0),t+'&!'+p)+')':eval(s)?1+t:0

```

8 bytes could be saved from this version if I was allowed to assume the above precedence on output too, which would remove all the parentheses from the output examples:

```
P&(P<=R) -> ((1&P&R)|(0))|((0)|(0))
P==(!P) -> (0)|(0)
(!P)|(Q==(P&R)) -> (((1&P&Q&R)|(0))|((0)|(1&P&!Q&!R)))|(((1&!P&Q&R)|(1&!P&Q&!R))|((1&!P&!Q&R)|(1&!P&!Q&!R)))

```

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


title: ASCII Box rendering

text:
# Question
Title: ASCII Box rendering
# Task

Your task is to write a program that will output ASCII boxes at the locations specified by the input.

## Input

You will be given a list of numbers. The format here is a bit flexible, in that you can use any deliminator you want (e.g. `1,2,3,4`, `1 2 3 4`, `[1,2,3,4]`). The list is in groups of 4 and specifies the `xywh` of each box. The width and height of each box will be at least 2. `x` and `width` are left-to-right. `y` and `height` are top-to-bottom.

## Output

Rendering can be thought of as right to left, with the box on the right drawn first, and every box after that is over it. Trailing spaces are allowed, as well as one trailing newline.

## How to handle overlapping boxes

The box on the left of the input is the top box, and nothing will overlap it. Every box after it is rendered only in the space that is not contained in a box already and will not replace the border of a already rendered box.

## Style

The style of the boxes are fairly standard, with `+` used for corners, `-` used for horizontal lines, and `|` used for vertical lines.

# Examples:

(`>>>` denotes input)

```
>>>0 0 11 4 7 2 8 4 3 5 8 3
+---------+
|         |
|         |---+
+---------+   |
       |      |
   +---+------+
   |      |
   +------+

>>>0 3 11 4 7 5 8 4 3 8 8 3 4 0 13 5
    +-----------+
    |           |
    |           |
+---------+     |
|         |-----+
|         |---+
+---------+   |
       |      |
   +---+------+
   |      |
   +------+

>>>0 0 2 2
++
++

>>>2 2 5 3 1 1 7 5 0 0 9 7
+-------+
|+-----+|
||+---+||
|||   |||
||+---+||
|+-----+|
+-------+

>>>0 0 3 3 2 0 3 3
+-+-+
| | |
+-+-+

```

# Answer
> 4 votes
# APL, 116 bytes

```
{⎕IO←0⋄K←' '⍴⍨⌽+⌿2 2⍴⌈⌿↑⍵⋄K⊣{x y W H←⍵-⌊.5×⍳4⋄K[Y←y+⍳H;X←x+⍳W]←' '⋄K[Y;A←x+0 W]←'|'⋄K[B←y+0 H;X]←'-'⋄K[B;A]←'+'}¨⌽⍵}

```

This is a function that takes an array of arrays and returns a character matrix.

Tests:

```
      t1← (0 0 11 4)(8 2 8 4)(3 5 8 3)
      t2← (0 3 11 4)(8 5 8 4)(3 8 8 3)(4 0 13 5)
      t3← (⊂0 0 2 2)
      t4← (2 2 5 3)(1 1 7 5)(0 0 9 7)
      {⎕IO←0⋄K←' '⍴⍨⌽+⌿2 2⍴⌈⌿↑⍵⋄K⊣{x y W H←⍵-⌊.5×⍳4⋄K[Y←y+⍳H;X←x+⍳W]←' '⋄K[Y;A←x+0 W]←'|'⋄K[B←y+0 H;X]←'-'⋄K[B;A]←'+'}¨⌽⍵} ¨ t1 t2 t3 t4
┌───────────────────┬─────────────────────┬────┬───────────┐
│+---------+        │    +-----------+    │++  │+-------+  │
│|         |        │    |           |    │++  │|+-----+|  │
│|         |----+   │    |           |    │    │||+---+||  │
│+---------+    |   │+---------+     |    │    │|||   |||  │
│        |      |   │|         |-----+    │    │||+---+||  │
│   +----+------+   │|         |----+     │    │|+-----+|  │
│   |      |        │+---------+    |     │    │+-------+  │
│   +------+        │        |      |     │    │           │
│                   │   +----+------+     │    │           │
│                   │   |      |          │    │           │
│                   │   +------+          │    │           │
│                   │                     │    │           │
│                   │                     │    │           │
└───────────────────┴─────────────────────┴────┴───────────┘

```

Explanation:

* `⎕IO←0`: set the index origin to `0`.
* Create a matrix of the right size:
    + `⌈⌿↑⍵`: find the largest values for x, y, w, and h
    + `+⌿2 2⍴`: x+w and y+h
    + `K←' '⍴⍨⌽`: make a matrix of x+w\*y+h spaces and store it in `K`.
* Draw the boxes into it:
    + `{`...`}¨⌽⍵`: for each of the boxes, in reverse order,
        - `x y W H←⍵-⌊.5×⍳4`: assign the coordinates to `x`, `y`, `W`, and `H`, and subtract 1 from both `W` and `H`. (coordinates are exclusive, APL array ranges are inclusive.)
        - `K[Y←y+⍳H;X←x+⍳W]←' '`: fill the current box with spaces
        - `K[Y;A←x+0 W]←'|'`: draw the vertical sides
        - `K[B←y+0 H;X]←'-'`: draw the horizontal sides
        - `K[B;A]←'+'`: set the edges to '+'
    + `K⊣`: afterwards, return `K`.

# Answer
> 3 votes
## ES6, ~~228~~ ~~223~~ ~~217~~ ~~208 201~~ 198 bytes

Accepts an array of arrays of coordinates and returns a string.

```
a=>a.reverse().map(([x,y,w,h])=>[...Array(y+h)].map((_,i)=>(s=r[i]||'',r[i]=i<y?s:(s+' '.repeat(x)).slice(0,x)+(c=>c[0]+c[1].repeat(w-2)+c[0])(y-i&&y+h-1-i?'| ':'+-')+s.slice(x+w))),r=[])&&r.join`\n`

```

Where `\n` represents a newline character.

Edit: Saved 5 bytes by reversing my conditions. Saved a further 6 bytes by switching from an array of char arrays to an array of strings. Saved a further 9 bytes by introducing a temporary variable. Saved a further 7 bytes by introducing a helper function. Saved a further 3 bytes by undoing a previous saving!

# Answer
> 3 votes
# Ruby, ~~153~~ 143

```
->n{a=(0..m=3*n.max).map{$b=' '*m}
(*n,x,y,w,h=n
v=w-2
h.times{|i|a[y+i][x,w]=i%~-h<1??++?-*v+?+:?|+' '*v+?|}
)while n[0]
a.delete($b);puts a}

```

**Ungolfed in test program**

```
f=->n{                                #worst case width when x=w=large number, is max input*2+1
  a=(1..m=3*n.max).map{$b=' '*m}      #find m=max value in input, make an a array of 3*m strings of 3*m spaces
  (
    *n,x,y,w,h=n                      #extract x,y,w,h from the end of n, save the rest back to n
    v=w-2                             #internal space in rectangle is w-2
    h.times{|i|                       #for each row
      a[y+i][x,w]=                    #substitute the relevant characters of the relevant lines of a
      i%~-h<1?                        #i%~-h = i%(h-1). This is zero (<1) for first and last lines of the rectangle
      ?+ + ?-*v + ?+ :?| + ' '*v +?|  # +--...--+ or |  ...  | as required
    }
  )while n[0]                         #loop until data exhausted (n[0] becomes falsy as it does not exist)
a.delete($b);puts a}                  #delete blank rows ($b is a global variable) and display

```

# Answer
> 3 votes
# SmileBASIC, ~~128~~ 125 bytes

```
DEF B A
WHILE LEN(A)H=POP(A)W=POP(A)-2Y=POP(A)X=POP(A)FOR I=0TO H-1LOCATE X,Y+I?"+|"[M];"- "[M]*W;"+|"[M]M=I<H-2NEXT
WEND
END

```

### Screenshots (cropped)

### Explanation

```
DEF B A 'make a function and add 12 bytes :(
 WHILE LEN(A) 'repeat until array is empty
  H=POP(A):W=POP(A)-2 'get width/height
  Y=POP(A):X=POP(A) 'get x/y
  FOR I=0 TO H-1 'draw one row at a time
   LOCATE X,Y+I 'position the cursor
   PRINT "+|"[M]; 'draw left edge
   PRINT "- "[M]*W; 'draw middle
   PRINT "+|"[M] 'draw right edge
   M=I<H-2
  NEXT
 WEND
END

```

`M` stores whether it's on the first/last row of the box (`0`=`+--+`, `1`=`| |`). On the first pass through the loop, `M` is 0, and on all others until the last, it's 1.

# Answer
> 1 votes
# Pyth, ~~162~~ 145 bytes

```
J\+K*h.MZm+@d1@d3Q]*h.MZm+@d0@d2QdD:GHb XKHX@KHGb;V_QDlTR@NTVl3Vl2:+l0b+l1H?|qHtl3qH0\-?|qbtl2qb0\|d)):l0l1J:+l0tl2l1J:l0+l1tl3J:+l0tl2+l1tl3J;jK

```

You can try it here

Output of test suite:

```
+---------+
|         |
|         |----+
+---------+    |
        |      |
   +----+-+----+
   |      |
   +------+

++
++

+-------+
|+-----+|
||+---+||
|||   |||
||+---+||
|+-----+|
+-------+

+-+-+
| | |
+-+-+

```

Horrible solution! Just waiting for someone to beat it

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