balance.rb

Download

# balance.rb
# 2006 David Baird
# License: Public Domain ^_^
#
# This program tries various combinations of instructions
# to execute on the Balance computer architecture.  The
# goal is to bring Balance from some given initial state
# to a desired final state.  But doing this is kind of
# like solving the rubics cube.
#
# The $weasel and $rabbites global variables are just some
# data used to initialize the search process (so it doesn't
# have to search *all* possibilities).
#
# This program really needs to be re-written to make more
# complicated searches easier to perform.
 
require 'scanf'
require 'weasel'
 
$rabbites = [[1, 2, 28, 1], [1, 4, 29, 1], [1, 5, 29, 1], [1, 6, 29, 1],
[1, 27, 5, 31], [1, 27, 7, 31], [1, 27, 9, 30], [1, 27, 11, 30], [1, 27,
13, 30], [1, 27, 15, 30], [1, 29, 2, 28], [1, 29, 3, 28], [1, 29, 31,
1], [1, 29, 31, 5], [1, 29, 31, 9], [1, 29, 31, 13], [1, 29, 31, 17],
[1, 29, 31, 21], [1, 29, 31, 25], [1, 29, 31, 29], [2, 4, 4, 24], [2,
4, 5, 24], [2, 8, 8, 20], [2, 8, 9, 20], [2, 8, 12, 20], [2, 8, 13, 20],
[2, 12, 4, 16], [2, 12, 5, 16], [2, 28, 1, 28], [18, 1, 28, 28]]
 
class Execute
end
 
class Instruction
  @@NAMES = [:science, :math, :logic, :physics, :die, :die, :die, :die]
  attr_accessor :opcode, :imm, :d, :s1, :s2, :raw
  def Instruction.math(d, s1, s2)
    x = new; x.opcode = 1; x.d = d; x.s1 = s1; x.s2 = s2; return x
  end
  def Instruction.logic(d, s1, s2)
    x = new; x.opcode = 2; x.d = d; x.s1 = s1; x.s2 = s2; return x
  end
  def Instruction.science(imm)
    x = new; x.opcode = 0; x.imm = imm; return x
  end
  def Instruction.physics(imm)
    x = new; x.opcode = 3; x.imm = imm; return x
  end
  def Instruction.die
    x = new; x.opcode = 4; x.d = d; x.s1 = s1; x.s2 = s2; return x
  end
  def name() @@NAMES[opcode] end
  def imm?()  [:science, :physics].include? name end
  def d1() (d + 1) % 2 end
  def s11() (s1 + 1) % 4 end
  def s21() (s2 + 1) % 4 end
  def raw
    p name
    return opcode << 5 | imm if imm?
    return opcode << 5 | d << 4 | s1 << 2 | s2
  end
  def raw=(x)
    opcode = x >> 5
    imm = x & 31
    d =  (x >> 4) & 1
    s1 = (x >> 2) & 3
    s2 = (x >> 0) & 3
  end
  def to_i() raw end
end
 
class Fixnum
  def as_int5
    return self if self < 0x10 or self < 0
    return -(32 - self)
  end
end
 
class Array
  def to_hex_s
    flatten.map { |x| '%02x' % x.to_i }.join('')
  end
  def to_umodem(filename)
    ("rm %s\n" % filename) +
    ("/bin/umodem %s STOP\n" % filename) +
    to_hex_s + "\nSTOP"
  end
  def mask_select(mask)
    select { |x| x = ((mask & 1) == 1); mask >>= 1; x }
  end
  def physics_prerotate(i)
    x = self[1..-1].mask_select(i)
    y = [self[0]]
    y + x
  end
  def physics_rotate(i)
    x = self[1..-1].mask_select(i)
    y = [self[0]]
    x + y
  end
end
 
class Register
  attr_accessor :d0, :d1, :s0, :s1, :s2, :s3
  include Comparable
  def to_a
    [@s0, @d1, @d0, @s3, @s2, @s1]
  end
  def a=(x)
    @s0, @d1, @d0, @s3, @s2, @s1 = x
  end
  def dR=(x)
    @d0, @d1 = x
  end
  def dR
    [@d0, @d1]
  end
  def sR=(x)
    @s0, @s1, @s2, @s3 = x
  end
  def sR
    [@s0, @s1, @s2, @s3]
  end
  def <=>(other)
    to_a <=> other.to_a
  end
  def physics(i)
    x = [0, 1, 2, 3, 4, 5]
    a = x.physics_rotate i
    b = x.physics_prerotate i
    t1 = self.to_a
    t2 = self.to_a
    t1[0] += i.as_int5
    a.each_index do |j|
      t2[a[j]] = t1[b[j]]
    end
    y = Register.new
    y.a = t2
    y
  end
  def to_s
    "{ %s, %s, %s, %s } { %s, %s }" % [@s0, @s1, @s2, @s3, @d0, @d1]
  end
  def swap?(other)
    x = self.to_a
    y = other.to_a
    (0..4).each do |a| ((a+1)..5).each do |b|
        return true if x[a] == y[b] and x[b] == y[a]
      end
    end
    return false
  end
end
 
x = Register.new
x.sR, x.dR = [0, 1, 2, 3], [4, 5]
y = x.dup
y.s0 = 44
p y == x
puts x.physics(31).physics(31).physics(31).physics(2)
 
def bruteforce_swapreg(foo = [0,1,2,3,4,5])
  x = Register.new
  x.sR, x.dR = foo[0..3], foo[4..5]
  x.dR = [4, 5]
  result = []
  (1..31).each do |a|
    #puts "%d..." % [a]
    (1..31).each do |b|
      #(1..31).each do |c|
        #(1..31).each do |d|
          y = x.physics(a).physics(b) #.physics(c).physics(d)
          #puts 'yay %d %d %s %s' % [a, b, x, y] if x.swap?(y)
          result << [a, b] if x.swap?(y)
        #end
      #end
    end
  end
  result
end
 
def bruteforce_swapreg3(foo = [0,1,2,3,4,5], combos=nil)
  x = Register.new
  x.sR, x.dR = foo[0..3], foo[4..5]
  result = []
  if combos == nil then
    puts "Constructing combos"
    combos = []
    (1..31).each do |a|
      #puts "%d..." % [a]
      (1..31).each do |b|
        (1..31).each do |c|
          (1..31).each do |d|
            combos << [a,b,c,d]
          end
        end
      end
    end
    puts "Done constructing combos"
  end
  combos.each do |(a,b,c,d)|
    y = x.physics(a).physics(b).physics(c).physics(d)
    #puts 'yay %d %d %s %s' % [a, b, x, y] if x.swap?(y)
    result << [a, b, c, d] if x.swap?(y)
  end
  result
end
 
def bruteforce_addmem2(foo = [0,1,2,3,4,5], combos=nil)
  x = Register.new
  x.sR, x.dR = foo[0..3], foo[4..5]
  result = []
  if combos == nil then
    puts "Constructing combos"
    combos = []
    (1..31).each do |a|
      #puts "%d..." % [a]
      (1..31).each do |b|
        (1..31).each do |c|
          (1..31).each do |d|
            combos << [a,b,c,d]
          end
        end
      end
    end
    puts "Done constructing combos"
  end
  combos.each do |(a,b,c,d)|
    y = x.physics(a).physics(b).physics(c).physics(d)
    #puts 'yay %d %d %s %s' % [a, b, x, y] if x.swap?(y)
    result << [a, b, c, d, y] if (y.sR.include? 0 and
                                  y.sR.include? 1 and
                                  y.dR.include? 2 and
                                  y.dR[0] == 2 and
                                  y.dR[1] == 2)
  end
  result
end
 
def bruteforce_swapmem(foo = [0,1,2,3,4,5], combos=nil)
  x = Register.new
  x.sR, x.dR = foo[0..3], foo[4..5]
  result = []
  if combos == nil then
    puts "Constructing combos"
    combos = []
    (1..31).each do |a|
      #puts "%d..." % [a]
      (1..31).each do |b|
        (0..0).each do |c|
          (0..0).each do |d|
            combos << [a,b,c,d]
          end
        end
      end
    end
    puts "Done constructing combos"
  end
  combos.each do |(a,b,c,d)|
    y = x.physics(a).physics(b).physics(c).physics(d)
    #puts 'yay %d %d %s %s' % [a, b, x, y] if x.swap?(y)
    result << [a, b, c, d, y] if (y.sR.include? 1 and
                                  y.sR.include? 3 and
                                  y.dR[0] != y.dR[1])
  end
  result
end
 
def swapreg2_hackt
  result = bruteforce_swapreg3 [0,1,2,3,4,5], $weasel
  p result.size
  (1..5).each do |foo|
    p foo
    v = (0..5).map { |x| rand 100 }
    result &= bruteforce_swapreg3 v, result
    p result.size
  end
  p result[0]
end
 
#p bruteforce_swapreg()[0]
#swapreg2_hackt
#x = bruteforce_addmem2()[0]
#p x
#puts x[4]
# >>>
# [2, 28, 0, 0, #<Register:0xb7f629b0 @s3=0, @d0=2, @s1=2, @d1=5, @s2=3, # @s0=1>]
# { 1, 2, 3, 0 } { 2, 5 }
 
#x = bruteforce_addmem2([0,1,2,3,4,5], $rabbites)[0]
#p x
#puts x[4]
# >>>
#[2, 28, 1, 28, #<Register:0xb7f6ce4c @d0=2, @s1=3, @d1=2, @s2=0, @s0=2, @s3=1>]
#{ 2, 3, 0, 1 } { 2, 2 }
 
#x = bruteforce_swapmem()
#p x
#puts x[0][4]
# >>>
# [1, 30, 0, 0, #<Register:0xb7f663bc @d0=3, @s1=2, @d1=1, @s2=3, @s0=1, @s3=4>]
# { 1, 2, 3, 4 } { 3, 1 }
 
 
#getc
 
rotate_madness = ['sR[0]', 'dR[1]', 'dR[0]', 'sR[3]', 'sR[2]', 'sR[1]']
(0..31).each do |x|
  puts "%2d: %s" % [x, rotate_madness.physics_prerotate(x)]
  puts "    %s" % [rotate_madness.physics_rotate(x)]
end
 
I = Instruction
tight_loop = I.science 0 # ...only if M[ sR[0] ] == 0
 
p_stop = [
  (I.physics 16),
  tight_loop,
]
puts p_stop.to_umodem "p_stop"
"
rm p_stop
/bin/umodem p_stop STOP
7000
STOP
step_balance stop p_stop
certify stop p_stop
"
 
p_stop127 = [
  (I.physics 1),
  tight_loop,
]
puts p_stop127.to_umodem "p_stop127"
"
rm p_stop127
/bin/umodem p_stop127 STOP
6100
STOP
certify stop127 p_stop127
"
 
#p_copymem = [
#]
#puts p_stopmem.to_umodem "p_copymem"
#"
#"
 
p_copyreg = [
  (I.physics 1),
  (I.physics 2),
  tight_loop,
]
puts p_copyreg.to_umodem "p_copyreg"
"
"
 
p_swapmem = [
  (I.physics 1),
  (I.physics 30),
  #(I.logic 1),
  tight_loop,
]
puts p_swapmem.to_umodem "p_swapmem"
"
"
 
p_swapreg = [
  (I.physics 1),
  (I.physics 19),
  tight_loop,
]
puts p_swapreg.to_umodem "p_swapreg"
"
rm p_swapreg
/bin/umodem p_swapreg STOP
617300
STOP
"
 
p_swapreg2 = [
  (I.physics 1),
  (I.physics 1),
  (I.physics 31),
  (I.physics 7),
  tight_loop,
]
puts p_swapreg2.to_umodem "p_swapreg2"
"
rm p_swapreg2
/bin/umodem p_swapreg2 STOP
61617f6700
STOP
"
 
p_addmem2 = [
  (I.physics 2),
  (I.physics 28),
  (I.physics 1),
  (I.physics 28),
  (I.math 0, 2, 3),
  tight_loop,
]
puts p_addmem2.to_umodem "p_addmem2"
"
rm p_addmem2
/bin/umodem p_addmem2 STOP
627c617c2b00
STOP
"
 
 
 

Hell is other programming languages. -- Sartran
Hell is that programming language! -- Dan

Ordinarily, one would enrich this language with more powerful means of computation. Instead I take a different tack... -- Harmonious Monk