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
