Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Your task is to write an interpreter for the malbolge programming language. To keep with the spirit of the language, this is not necessarily code golf. The winner will be the one who provides the most obfuscated/hard to understand interpreter that works.

Official language spec is here. Reference implementation is here. In cases where the spec and the interpreter differ, give preference to the spec. Namely, there is a bug in the 'official' interpreter that allows non-printing characters to be put into memory unchecked. Do not replicate this.

Official test programs: Hello World:

('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=<M:9wv6WsU2T|nm-,jcL(I&%$#"
 `CB]V?Tx<uVtT`Rpo3NlF.Jh++FdbCBA@?]!~|4XzyTT43Qsqq(Lnmkj"Fhg${z@>

99 Bottles of Beer: found here

'Cat' Program: found here

share|improve this question
    
Since there is an "Interpret Brainfuck" question and a "Brainfuck Golfer" question, and there is now an "Interpret Malbolge" question, we should make a "Malbolge Golfer" question. –  PhiNotPi Apr 12 '12 at 16:01
    
@PhiNotPi that would be incredibly difficult! –  leftaroundabout Apr 12 '12 at 16:02
1  
@CMP, there should be a bootstrapping bonus. –  boothby Apr 13 '12 at 0:39
    
What do you mean by that? –  CMP Apr 13 '12 at 17:53
1  
If you can do that I will award you 4 internets for awesomeness. –  CMP May 23 '12 at 22:50
show 1 more comment

1 Answer 1

up vote 4 down vote accepted

This code challenge seems impossible. I believe that a Malbolge interpreter cannot both implement the spec and pass the test programs. This is because the test programs seem wrong.

The spec uses < for input and / for output. Malbolge at Esolang claims that the reference interpreter reverses these two instructions and uses / for input and < for output.

The code challenge says:

In cases where the spec and the interpreter differ, give preference to the spec.

Any Malbolge program, performing input or output, working with the reference interpreter, will not work with the interpreter for this code challenge.

Here is Hello World:

('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=<M:9wv6WsU2T|nm-,jcL(I&%$#"
 `CB]V?Tx<uVtT`Rpo3NlF.Jh++FdbCBA@?]!~|4XzyTT43Qsqq(Lnmkj"Fhg${z@>

Here is Hello World after normalization:

jjjjpp<jjjj*p<jjjpp<<jjjj*p<jj*o*<i<io<</<<oo<*o*<jvoo<<opj<*<<<<<
 ojjopjp<jio<ovo<<jo<p*o<*jo<iooooo<jj*p<jji<oo<j*jp<jj**p<jjopp<i

Hello World has many < for input and only one / for output, so it can output only one character, unless it can create more / in memory. When my interpreter runs Hello World, it reads many characters, outputs nothing, and exits. When my interpreter runs Cat, it outputs gg and exits. I did not test 99 Bottles of Beer.

If I reverse < and /, so that my interpreter disagrees with the spec, then Hello World outputs Hello World! and exits. Cat reads 2 characters, outputs nothing, and exits. There might be a bug in my interpreter, or another bug in Cat.

With this evidence, I believe that Hello World and Cat cannot work in a Malbolge interpreter that follows the spec.

The following programs require Ruby 1.8.7 or Ruby 1.9.x.

Here is my normalizer:

# Show a Malbolge program in normalized form. The output can only
# contain whitespace and the 8 instructions 'ji*p</vo'.

Box1 = ('+b(29e*j1VMEKLyC})8&m#~W>qxdRp0wkrUo[D7,XTcA"lI' \
        '.v%{gJh4G\\-=O@5`_3i<?Z\';FNQuY]szf$!BS/|t:Pn6^Ha')

index = 0
ARGF.each_byte do |byte|
  if byte.chr =~ /\s/
    putc byte
  else
    index < 59049 or abort "Program too long"
    instr = (byte.between? 33, 126 and Box1[(byte - 33 + index) % 94])
    if 'ji*p</vo'.include? instr
      putc instr
      index += 1
    else
      abort "Illegal instruction #{instr} from #{byte.chr}"
    end
  end
end

Here is my Malbolge interpreter:

# 'terp 1.
# This Ruby program interprets the Malbolge language. It implements the
# Malbolge Specification <http://www.lscheffer.com/malbolge_spec.html>.

# P[trit from D][trit from A] is a trit operation.
P = {?0 => {?0 => ?1, ?1 => ?0, ?2 => ?0},
     ?1 => {?0 => ?1, ?1 => ?0, ?2 => ?2},
     ?2 => {?0 => ?2, ?1 => ?2, ?2 => ?1}}

# These substitution boxes come from the Malbolge Specification.
# Each box is a table of 94 characters.
Box1 = ('+b(29e*j1VMEKLyC})8&m#~W>qxdRp0wkrUo[D7,XTcA"lI' \
        '.v%{gJh4G\\-=O@5`_3i<?Z\';FNQuY]szf$!BS/|t:Pn6^Ha')
Box2 = ('5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1C' \
        'B6v^=I_0/8|jsb9m<.TVac`uY*MK\'X~xDl}REokN:#?G"i@')

# Reads instruction at _address_. Returns a character from Box1. If
# _address_ does not contain an instruction, returns +nil+.
def instruction(address)
  word = Memory[address]
  word.between? 33, 126 and Box1[(word - 33 + address) % 94]
end

# Converts integer to ternary string of 10 digits.
def tern(i)
  (i + 59049).to_s(3)[1, 10]
end

# Performs a tritwise operation.
def op(a, d)
  a3 = tern(a)
  d3 = tern(d)
  (0..9).inject("") {|s, i| s << P[d3[i]][a3[i]]}.to_i(3)
end

# Load program into memory.
Memory = []
ARGF.each_line do |line|
  line.each_byte.with_index do |byte, byte_index|
    # Ignore whitespace.
    next if byte.chr =~ /\s/

    index = Memory.length
    index < 59049 or abort "Program too long"
    Memory << byte

    # Each character must be any of 8 legal instructions. Otherwise,
    # the Malbolge Specification requires to reject the file.
    unless 'ji*p</vo'.include?(instr = instruction(index))
      abort("Illegal instruction #{instr} from #{byte.chr} " \
            "at line #{ARGF.lineno}, column #{byte_index}")
    end
  end
end

# Initialize remainder of memory.
Memory.length.upto(59048) do |i|
  # Memory[i - 2] and Memory[i - 1] might be in the wrong order, because
  # of ambiguity in the Malbolge Specification.
  a = Memory[i - 2] || rand(59049)
  d = Memory[i - 1] || rand(59049)
  Memory[i] = op(a, d)
end

# Initialize registers to zero.
a = 0       # accumulator
c = 0       # code pointer
d = 0       # data pointer

# Enter main interpreter loop.
loop do
  case instruction(c)
  when ?j
    d = Memory[d]
  when ?i
    c = Memory[d]
  when ?*
    # Rotate right. There is an error in the Malbolge Specification,
    # where 9 trits 'move one position to the left'. For consistency,
    # those 9 trits must move one position to the *right*.
    d3 = tern(Memory[d])
    a = (d3[9, 1] << d3[0, 9]).to_i(3)
    Memory[d] = a
  when ?p
    # Perform tritwise op. The Malbolge Specification omits where to
    # store the result. This interpreter stores it in the accumulator.
    a = op(a, Memory[d])
  when ?<
    a = $stdin.getbyte || 59048
  when ?/
    putc a
  when ?v, nil
    # 'v' or any non-instruction ends the program.
    exit
  else
    # 'o' or any other instruction does nothing.
  end

  word = Memory[c]
  unless word.between? 33, 126
    # The Malbolge Specification requires to access Box2 with an index
    # that is out of range, but this interpreter refuses to do so.
    abort "Index out of range: Memory[C = #{c}] = #{Memory[c]}"
  end
  Memory[c] = Box2[word - 33].ord

  c = (c + 1) % 59049
  d = (d + 1) % 59049 
end
share|improve this answer
    
So... even after switching the problematic operands, you still have a bug? Also... this is well-commented, and easy to read -- were you going to obfuscate? –  boothby Apr 15 '12 at 2:54
1  
Considering this is the only answer so far, I'd say it's obfuscated enough to win. –  Gaffi May 15 '12 at 3:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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