«

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Quiz 2 by submitting ideas as often as you can!
Visit <http://splatbang.com/rubyquiz/>.

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion. Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Befunge (#184)

Since next week is the Thanksgiving holiday here in the U.S., and
since I will be away visiting family, this quiz has a duration of two
weeks. It will be summarized on/about Thurs, December 4th.

Your task for these two weeks is to write a [Befunge-93][1]
interpreter. Befunge-93 is an esoteric programming language created by
Chris Pressey. Its features:

* two-dimensional program space (i.e. 80x25 ASCII grid)
* a program counter capable of moving through the program in four
directions
* an integer stack for performing RPN-type calculations
* can be self-modifying

Basically, the program counter (PC) starts in the upper-left cell of
the program, initially moving to the right. At each cell, the command
(i.e. a single character) in that cell is executed. Some commands can
change the PC's direction of movement; some commands put values on the
stack or operate on the stack, and a few commands accept input or
print output.

The [specification][2], at the bottom, contains a summary of commands.
Note that the digits 0-9, not mentioned in the table of command but
mentioned earlier in the spec, push themselves onto the stack. To get
other values on the stack, you have a couple options. Mathematical
operations is one way:

562**5+

Assuming the PC is moving right and starting at the left side, this
will leave 65 on the stack. Another way is stringmode, initiated and
terminated by quotes. The following also puts 65 on the stack:

"A"

At the [Befunge-93 examples page][3], there are plenty of sample
programs for you to test, documented with the program's intent. Some
programs were re-written by various developers in an attempt to shrink
programs as much as possible. In particular, the "rand" series
(generate a random number from 1 to 16) went through 16 revisions,
going from 144 cells (12x12) to a mere 16 cells (16x1). My own
submission was king for barely an hour, and looked like this:

> v <
vv # <
14 >0^
+*v?1^
+ >2^p
. > 3^1
@>"<"1^

Some of the most interesting (i.e. insane) Befunge programs include
life.bf, mandel.bf, pi2.bf, and wumpus.bf.


[1]: http://catseye.tc/projects/befunge93/
[2]: http://catseye.tc/projects/befunge93/doc/befunge93.html
[3]: http://catseye.tc/projects/befunge93/eg/INDEX.html
[4]: http://catseye.tc/projects/funge98/

Hopefully the quiz isn't intimidating... It's a fairly simple language
to implement. It took me about 30 minutes to get a simple,
straightforward version working (my submission, shown below), and I
may do some revisions later to try shrinking the code and making it
more Ruby-ish. (Also to handle some conditions not currently handled
well...) I mostly want to revise the run and step methods to be less
case-y.

Feel free to steal this and make it better, or just to look at to get
an idea of how to implement your own.


#!/usr/bin/env ruby

class Befunge93

def self.load_and_run(filename)
self.new(File.read(filename)).run
end

def initialize(text)
rows = text.split(/[\r\n]+/) # split
input into rows
@hgt = rows.size # find
program height
@wid = rows.max { |a, b| a.size <=> b.size }.size # find
program width
@code = rows.map { |row| row + " " * (@wid - row.size) } # pad
rows, store code (r, c)
@pc, @dir = [0, 0], :east
@stack = []
@stringmode = false
end

def run
loop do
if @stringmode
case curr
when ?"
@stringmode = false
else
push curr
end
else
case curr
when ?0..?9
push (curr - ?0)
when ?+, ?-, ?*, ?/, ?%
b, a = pop, pop
push a.send(curr.to_sym, b)
when ?!
push (pop.zero? ? 1 : 0)
when ?`
b, a = pop, pop
push (a > b ? 1 : 0)
when ?.
puts pop
when ?>
@dir = :east
when ?<
@dir = :west
when ?^
@dir = :north
when ?v
@dir = :south
when ??
@dir = [:east, :west, :north, :south][rand(4)]
when ?_
@dir = pop.zero? ? :east : :west
when ?|
@dir = pop.zero? ? :south : :north
when ?"
@stringmode = true
when ?:
push top
when ?\\
a = pop # what about underflow?
b = pop
push a
push b
when ?$
pop
when ?.
print pop
when ?,
print pop.chr
when ?#
step
when ?g
r, c = pop, pop
push @code[r][c]
when ?p
r, c, v = pop, pop, pop
@code[r][c] = v
when ?&
print "int?> "
push gets.to_i
when ?~
print "chr?> "
push gets[0] # Ruby 1.8, maybe not 1.9?
when ?@
break
end
end
step # move program counter
end
end

private

def curr
@code[ @pc[0] ][ @pc[1] ]
end

def step
case @dir
when :north
@pc[0] = (@pc[0] - 1 + @hgt) % @hgt
when :south
@pc[0] = (@pc[0] + 1) % @hgt
when :east
@pc[1] = (@pc[1] + 1) % @wid
when :west
@pc[1] = (@pc[1] - 1 + @wid) % @wid
end
end

def push(val)
@stack.push(val)
end

def pop
@stack.pop || 0
end

def top
@stack.last || 0
end
end

if __FILE__ == $0
Befunge93.load_and_run(ARGV.shift)
end

On Mon, Nov 24, 2008 at 11:01 PM, Matthew Moss <> wrote:
> Hopefully the quiz isn't intimidating...
No but the debugger is so much work, and without the debugger there is
nothing my code does more than your's , but I have two weeks to
finish it
I guess you have some small typos here
> when ?.
> puts pop
I guess this has to go
> when ?.
> print pop
shouldn't there be a space printed too?
> when ?~
> print "chr?> "
> push gets[0] # Ruby 1.8, maybe not 1.9?
x=3D gets
push( x.bytes.first rescue x[0] )
> when :north
> @pc[0] =3D (@pc[0] - 1 + @hgt) % @hgt
I guess the + @hgt is a nop but ok it makes the reader more
comfortable with the code , OTOH it took me
some time to work it's purpose out.

Cheers
Robert
--=20
Ne baisse jamais la t=EAte, tu ne verrais plus les =E9toiles.

Robert Dober

>> when :north
>> @pc[0] = (@pc[0] - 1 + @hgt) % @hgt
> I guess the + @hgt is a nop but ok it makes the reader more
> comfortable with the code , OTOH it took me
> some time to work it's purpose out.


I tend to do (-1 + h) % h when I don't recall a language's particular
rules for dealing with negative mod.

In other words, if I don't know that (0-1)%h is safe, I do know that
(0-1+h)%h is safe and gets me what I want.

Matthew Moss <> wrote:
> def run
> loop do
> if @stringmode
> case curr
> when ?"
> @stringmode = false
> else
> push curr
> end
> else
> case curr
> when ?0..?9
> push (curr - ?0)
> when ?+, ?-, ?*, ?/, ?%
> b, a = pop, pop
> push a.send(curr.to_sym, b)

My first thought was a big case statement like that, but wanted
something a bit more "fun". My next thoughts were to try something
with lambda or define_method. Here's a really rough, partial (and
almost entirely untested) implementation built around define_method:

class Befunge93
instance_methods.each { |m| undef_method m unless (m =~ /^__|send/) }

attr_accessor :stack, :memory, osition, :direction

def initialize
@stack = []
@memory = {}
@position = [0,0]
@direction = [1,0]
end

def move
@position[0] = (@position[0] + @direction[0]) % 80
@position[1] = (@position[1] + @direction[1]) % 25
end

def run
loop do
send @memory[@position]
move
end
end

(0..9).each do |d|
define_method :"#{d}" do
@stack.push d
end
end

%w{ + - * / }.each do |o|
define_method :"#{o}" do
a, b = @stack.pop, @stack.pop
@stack.push a.send(:"#{o}", b)
end
end

[
[ '^', [ 0,-1] ],
[ 'v', [ 0, 1] ],
[ '<', [-1, 0] ],
[ '>', [ 1, 0] ]
].each do |d|
define_method :"#{d[0]}" do
@direction = d[1]
end
end

define_method :"." do
print @stack.pop
end

define_method :"@" do
puts
exit
end
end

bf = Befunge93.new

bf.memory = {
[0,0] => "v", [1,0] => " ", [2,0] => " ", [3,0] => " ", [4,0] => " ",
[0,1] => "1", [1,1] => "v", [2,1] => "<", [3,1] => " ", [4,1] => " ",
[0,2] => "1", [1,2] => "3", [2,2] => "2", [3,2] => " ", [4,2] => " ",
[0,3] => ">", [1,3] => "+", [2,3] => "^", [3,3] => " ", [4,3] => " ",
[0,4] => " ", [1,4] => "-", [2,4] => " ", [3,4] => " ", [4,4] => " ",
[0,5] => " ", [1,5] => ".", [2,5] => " ", [3,5] => " ", [4,5] => " ",
[0,6] => " ", [1,6] => "@", [2,6] => " ", [3,6] => " ", [4,6] => " ",
[0,7] => " ", [1,7] => " ", [2,7] => " ", [3,7] => " ", [4,7] => " ",
[0,8] => " ", [1,8] => " ", [2,8] => " ", [3,8] => " ", [4,8] => " ",
}

bf.run #=> 3

On Nov 25, 2008, at 11:07 AM, wrote:
> Matthew Moss <> wrote:
>> def run
>> loop do
>> if @stringmode
>> case curr
>> when ?"
>> @stringmode = false
>> else
>> push curr
>> end
>> else
>> case curr
>> when ?0..?9
>> push (curr - ?0)
>> when ?+, ?-, ?*, ?/, ?%
>> b, a = pop, pop
>> push a.send(curr.to_sym, b)
>
> My first thought was a big case statement like that, but wanted
> something a bit more "fun". My next thoughts were to try something
> with lambda or define_method. Here's a really rough, partial (and
> almost entirely untested) implementation built around define_method:
>
> class Befunge93
> instance_methods.each { |m| undef_method m unless (m =~ /^__|send/) }
>
> attr_accessor :stack, :memory, osition, :direction
>
> def initialize
> @stack = []
> @memory = {}
> @position = [0,0]
> @direction = [1,0]
> end
>
> def move
> @position[0] = (@position[0] + @direction[0]) % 80
> @position[1] = (@position[1] + @direction[1]) % 25
> end
>
> def run
> loop do
> send @memory[@position]
> move
> end
> end
>
> (0..9).each do |d|
> define_method :"#{d}" do
> @stack.push d
> end
> end
>
> %w{ + - * / }.each do |o|
> define_method :"#{o}" do
> a, b = @stack.pop, @stack.pop
> @stack.push a.send(:"#{o}", b)
> end
> end
>
> [
> [ '^', [ 0,-1] ],
> [ 'v', [ 0, 1] ],
> [ '<', [-1, 0] ],
> [ '>', [ 1, 0] ]
> ].each do |d|
> define_method :"#{d[0]}" do
> @direction = d[1]
> end
> end
>
> define_method :"." do
> print @stack.pop
> end
>
> define_method :"@" do
> puts
> exit
> end
> end
>
> bf = Befunge93.new
>
> bf.memory = {
> [0,0] => "v", [1,0] => " ", [2,0] => " ", [3,0] => " ", [4,0] => " ",
> [0,1] => "1", [1,1] => "v", [2,1] => "<", [3,1] => " ", [4,1] => " ",
> [0,2] => "1", [1,2] => "3", [2,2] => "2", [3,2] => " ", [4,2] => " ",
> [0,3] => ">", [1,3] => "+", [2,3] => "^", [3,3] => " ", [4,3] => " ",
> [0,4] => " ", [1,4] => "-", [2,4] => " ", [3,4] => " ", [4,4] => " ",
> [0,5] => " ", [1,5] => ".", [2,5] => " ", [3,5] => " ", [4,5] => " ",
> [0,6] => " ", [1,6] => "@", [2,6] => " ", [3,6] => " ", [4,6] => " ",
> [0,7] => " ", [1,7] => " ", [2,7] => " ", [3,7] => " ", [4,7] => " ",
> [0,8] => " ", [1,8] => " ", [2,8] => " ", [3,8] => " ", [4,8] => " ",
> }
>
> bf.run #=> 3

Seems like this program is:

1 1 + 2 3 + - .

Which seems to be -3, not 3. I think you have your args out of
order. Look at how the non-commutative ops are defined.

-Rob

Rob Biedenharn http://agileconsultingllc.com

On Tue, Nov 25, 2008 at 11:42 AM, Rob Biedenharn
<> wrote:
> On Nov 25, 2008, at 11:07 AM, wrote:
>> almost entirely untested) implementation built around define_method:
>>
>> bf.run #=> 3
>
> Seems like this program is:
>
> 1 1 + 2 3 + - .
>
> Which seems to be -3, not 3. I think you have your args out of order. Look
> at how the non-commutative ops are defined.

Yeah, that would be part of the entirely untested stuff

%w{ + * }.each do |o|
define_method :"#{o}" do
a, b = @stack.pop, @stack.pop
@stack.push a.send(:"#{o}", b)
end
end
%w{ - / }.each do |o|
define_method :"#{o}" do
b, a = @stack.pop, @stack.pop
@stack.push a.send(:"#{o}", b)
end
end

or, maybe some would prefer:
%w{ - / }.each do |o|
define_method :"#{o}" do
a, b = @stack.pop, @stack.pop
@stack.push b.send(:"#{o}", a)
end
end

On Nov 25, 2008, at 11:15 AM, wrote:

> On Tue, Nov 25, 2008 at 11:42 AM, Rob Biedenharn
> <> wrote:
>> On Nov 25, 2008, at 11:07 AM, wrote:
>>> almost entirely untested) implementation built around define_method:
>>>
>>> bf.run #=> 3
>>
>> Seems like this program is:
>>
>> 1 1 + 2 3 + - .
>>
>> Which seems to be -3, not 3. I think you have your args out of
>> order. Look
>> at how the non-commutative ops are defined.
>
> Yeah, that would be part of the entirely untested stuff
>
> %w{ + * }.each do |o|
> define_method :"#{o}" do
> a, b = @stack.pop, @stack.pop
> @stack.push a.send(:"#{o}", b)
> end
> end
> %w{ - / }.each do |o|
> define_method :"#{o}" do
> b, a = @stack.pop, @stack.pop
> @stack.push a.send(:"#{o}", b)
> end
> end

If you're going to fix the arg order of - and /, why wouldn't you do
the same for + and *?

Popping b first, then a, isn't a workaround; it's the correct method
according to spec. Why make + and * an exception to that?

>
> I guess you have some small typos here
>> when ?.
>> puts pop
> I guess this has to go

Oops, yeah, handling . twice.

>
>> when ?.
>> print pop
> shouldn't there be a space printed too?

No. The following code (I think) outputs a null-terminated string
(view with monospace font):

0"elloH"#v _@
>.^

You wouldn't want spaces between every character.


>
>> when ?~
>> print "chr?> "
>> push gets[0] # Ruby 1.8, maybe not 1.9?
> x= gets
> push( x.bytes.first rescue x[0] )
>>

Nice, thanks.

> No. The following code (I think) outputs a null-terminated string
> (view with monospace font):
>
> 0"elloH"#v _@
> >.^

This one works a bit better (that is, it actually works):

037+"olleH":#v_@
,:
>^