18
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ If you’re saying the winner is decided by votes, it’s a popularity-contest, not a code-golf. \$\endgroup\$ – Ry- Jan 22 '14 at 21:37
  • 8
    \$\begingroup\$ It's not non-existent anymore, is it? :) \$\endgroup\$ – Kendall Frey Jan 22 '14 at 21:37
  • 1
    \$\begingroup\$ Technically, a language doesn't need an interpreter or compiler to be a language. :P \$\endgroup\$ – Kendall Frey Jan 22 '14 at 21:43
  • 2
    \$\begingroup\$ IIUC, we should start with an empty stack and treat underflows as zeroes? \$\endgroup\$ – John Dvorak Jan 23 '14 at 7:29
  • 2
    \$\begingroup\$ You should start with a single 0 on the stack (As there's no way to do anything if there isn't a number to begin with). I'll leave the underflow thing up to you. Whatever's easier. \$\endgroup\$ – Taconut Jan 23 '14 at 14:50

17 Answers 17

14
\$\begingroup\$

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$<$<$
\$\endgroup\$
  • \$\begingroup\$ It seems to me your bonus solution is missing an initial d (after ii, the stack contains only 2, nothing to swap with), and the final rotates (well, at least the first one, the second one is just a swap in disguise...) should be to the left, not to the right. \$\endgroup\$ – Mormegil Jan 24 '14 at 22:46
  • \$\begingroup\$ @Mormegil I'm using the interpretation that the stack auto-expands with zeroes as needed. Thus no need to dup the leading zero. As for the rotation direction, I'll recheck... \$\endgroup\$ – John Dvorak Jan 24 '14 at 22:48
  • \$\begingroup\$ @Mormegil rotation direction fixed, thanks. \$\endgroup\$ – John Dvorak Jan 24 '14 at 22:54
  • \$\begingroup\$ Oh, yeah, I missed the comment about the underflow interpretation, and my solution unfortunately cannot do that. \$\endgroup\$ – Mormegil Jan 25 '14 at 18:45
11
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Why LEA ESI, [ESI+1] rather than INC ESI? \$\endgroup\$ – Score_Under Jan 24 '14 at 23:06
  • \$\begingroup\$ Actually, in the final result, no real reason; generally, speed/size/affected flags might be important. But I did not really optimize the result, it is basically just a first attempt. \$\endgroup\$ – Mormegil Jan 25 '14 at 18:50
  • 1
    \$\begingroup\$ This one's definitely the coolest. I had a lot of fun playing around with it :). \$\endgroup\$ – Taconut Jan 27 '14 at 14:10
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You could drop + in ])\+~ \$\endgroup\$ – John Dvorak Jan 25 '14 at 8:55
  • \$\begingroup\$ @JanDvorak: Ah, yes, that should've been obvious. Thanks! \$\endgroup\$ – Ilmari Karonen Jan 25 '14 at 10:18
8
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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 evals 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]
\$\endgroup\$
4
\$\begingroup\$

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>.

\$\endgroup\$
  • \$\begingroup\$ I think you can lose free(a);. And, shouldn't it be <<2 in the realloc calls? \$\endgroup\$ – luser droog Jan 25 '14 at 7:43
  • \$\begingroup\$ @luserdroog True, thanks. I'm just used to free() memory :P \$\endgroup\$ – Oberon Jan 25 '14 at 16:45
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I keep finding the same thing to be true of mine. \$\endgroup\$ – luser droog Jan 26 '14 at 8:59
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ crap! I did not consider negatives in concatenation. I think log is not even defined. \$\endgroup\$ – luser droog Jan 24 '14 at 9:20
  • \$\begingroup\$ The golfed version will have a big slow-down once it hits a page-boundary, it will segfault repeatedly, allocating 8-bytes in the handler, retrying the memory access, segfaulting again, over and over for each 8-byte span until the memory becomes valid. The ungolfed one uses a larger constant and should not be as slow, but the algorithm is the same. \$\endgroup\$ – luser droog Jan 25 '14 at 9:06
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ "As for the 2014 challenge it's obviously impossible as we can only get copies of zeroes in the stack with operations A-F" -- WAT? Incrementing a zero produces... a nonzero, doesn't it? \$\endgroup\$ – John Dvorak Jan 25 '14 at 8:57
  • \$\begingroup\$ @JanDvorak But we need to write '1' for incrementation, digits are forbidden, right? \$\endgroup\$ – swish Jan 25 '14 at 8:58
  • \$\begingroup\$ That's the tragedy of that choice of encoding. If you map the punctuation-heavy set (maybe with tr?) then it becomes possible. \$\endgroup\$ – luser droog Jan 25 '14 at 9:01
1
\$\begingroup\$

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))
\$\endgroup\$
1
\$\begingroup\$

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";
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Seeing as this isn't code golf (it's a popularity-contest) and your code is barely golfed, I don't think you need to include the byte count. \$\endgroup\$ – FlipTack Jan 29 '17 at 8:11
  • \$\begingroup\$ @FlipTack I just include the byte count because someone might want to know. \$\endgroup\$ – ckjbgames Jan 29 '17 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.