--Wf1wk1t+okM/SedwJ7S
Content-Type: text/plain
Content-Transfer-Encoding: 7bit

Here is my Galaxy implementation. It seems to do everything it needs to
do, but I didn't go overboard with extra stuff since I don't know what
kind of stuff might be useful for the Galaxy to do...

The easiest way to use this with the GalaxyLoader seems to be to remove
the 'require galaxy' from GalaxyLoader and do it the other way around.
Then you can run the tests including the dump test with:

	ruby -rgalaxy_loader galaxy.rb

There are some naive benchmarks I used to make the obvious
optimizations, run them with:

	ruby galaxy.rb -bm

One additional thing I did consider was multiplayer - it's fairly easy
to get a galaxy working over DRb, and I did work up a basic multiplayer
version like this but had one overriding problem - all output ends up on
the server, or the game ends up useless because of constantly
marshalling sectors to send down the wire. I toyed with routing output
through the Player but still had problems... Ho hum.

Finally, I need to thank a couple of people: Dominik Bathon's solution
to Ruby Quiz 31 ( see
http://www.ruby-talk.org/cgi-bin/scat.rb/ruby/ruby-talk/141783 ) gave me
a much-needed start with Dijkstra's shortest path algorithm (in fact
it's only very slightly modified from his original) and Mauricio
Fernandez's WeakHash class let's me cache stuff irresponsibly (see
http://eigenclass.org/hiki.rb?weakhash+and+weakref )

-- 
Ross Bamford - rosco / roscopeco.REMOVE.co.uk

--Wf1wk1t+okM/SedwJ7S
Content-Disposition: attachment; filename=galaxy.rb
Content-Type: text/plain; name=galaxy.rb; charset=utf-8
Content-Transfer-Encoding: 7bit

require 'singleton'

unless $0 __FILE__
  require 'sector'
  require 'planet'
  require 'station'
end

# The implementation of Dijkstra's shortest path algorithm I use for 
# find_path and find_reachable was lifted directly from Dominik Bathon's
# solution to quiz 31 (thanks!) and only modified very slightly to suit 
# our purpose. This Hash modification comes with that.
class Hash #:nodoc: all
  # find the key for with the smallest value, delete it and return it
  def delete_min_value
    return nil if empty?
    minkeynl
    each { |k, v|
      min, minkey k if !min || v<min
    }
    delete(minkey)
    minkey
  end
end

module SpaceMerchant #:nodoc:
  #  alaxy for Ruby Quiz 71.
  #
  # Requires:
  # * Sector.new(name, location  il)
  # * Sector#link(to_sector)
  # * Sector#links [Sector:1, ..., Sector:N]
  # * Sector#planets [Planet:1, ..., Planet:N]
  # * Sector#stations [Station:1, ..., Station:N]
  # * Sector#add_planet(planet)
  # * Sector#add_station(station)
  #   
  # * Planet.new(name, location  il)
  # * Station.new(name, location  il)
  #
  # * All classes need #name String
  # * All classes should define in terms of name *at* *least*
  #   
  # Extra features:
  # * Simplistic galaxy generation
  # * Galaxy codes allow whole galaxy to be regenerated
  # * Support for long-distance route availablility by distance
  # * Compatible with Jacob Fugal's GalaxyLoader
  # * Able to dump galaxies in GalaxyLoader format
  #   
  class Galaxy
    include Singleton

    # internal stuff
    TRUEBLOCK  ambda { true }   #:nodoc:
    ATOZ  'A'..'Z').to_a        #:nodoc:
    
    class << self
      # tired of writing 'Galaxy.instance' in tests...
      def method_missing(sym, *args, &blk) #:nodoc: 
        instance.send(sym, *args, &blk)
      end
    end

    # This WeakHash implementation is by Mauricio Fernandez. I
    # just added support for a default, and full key reclaimation
    # to suit our need to have the default block run as and when 
    # (but only when) necessary.
    # 
    # See: http://eigenclass.org/hiki.rb?weakhash+and+weakref 
    class WeakHash #:nodoc: all
      attr_reader :cache
      def initialize( cache  ash.new, &initializer )
        @cache  ache
        @initializer  nitializer
        @key_map  }
        @rev_cache  ash.new{|h,k| h[k]  }}
        @reclaim_value  ambda do |value_id|
          if @rev_cache.has_key? value_id
            @rev_cache[value_id].each_key{|key| @cache.delete key}
            @rev_cache.delete value_id
          end
        end
        @reclaim_key  ambda do |key_id|
          if @key_map.has_key? key_id
            @cache.delete @key_map[key_id]
            @key_map.delete key_id
          end
        end
      end

      def []( key )
        value_id  cache[key.hash]

        if value_id.nil? && @initializer
          self[key]  initializer.call(self, key)
          value_id  cache[key.hash]
        end
        
        return ObjectSpace._id2ref(value_id) unless value_id.nil?
        nil
      end

      def []key, value )
        case key
        when Fixnum, Symbol, true, false
          key2  ey
        else
          key2  ey.hash
        end
        @rev_cache[value.object_id][key2]  rue
        @cache[key2]  alue.object_id
        @key_map[key.object_id]  ey2

        ObjectSpace.define_finalizer(value, @reclaim_value)
        ObjectSpace.define_finalizer(key, @reclaim_key)
      end
    end
      
    attr_reader :sectors, :code
    
    def initialize #:nodoc:
      @sectors  ]

      @pathcache  eakHash.new do |h, key|
        start, avoid  ey
        h[key.freeze]  uild_prev_hash(start, avoid)
      end

      @code  il
    end

    # Change the code for the galaxy. This will cause the
    # whole galaxy to be regenerated, from the specified code,
    # with the current galaxy lost, so be careful.
    #
    # Pretty much equivalent to +generate+
    def code
ode)
      generate(code)
    end

    # Add a sector.
    def add_sector(sector)
      sectors << sector
    end

    # Get the starting location for this galaxy. If a galaxy
    # hasn't been generated (or loaded), this will have a
    # random one generated.
    def starting_location
      generate if @sectors.empty?
      sectors.first
    end

    # select sectors with the supplied block
    def find_sectors(&blk)
      sectors.select(&(blk || TRUEBLOCK)) || []
    end

    # select stations with the supplied block
    def find_stations(&blk)
      sectors.inject([]) do |a, e|
        a.push(*e.stations.select(&(blk || TRUEBLOCK)))
      end
    end

    # select planets with the supplied block
    def find_planets(&blk)
      sectors.inject([]) do |a, e|
        a.push(*e.planets.select(&(blk || TRUEBLOCK)))
      end
    end

    # find the shortest path between start and finish (sectors).
    # Optionally supply an array of sectors to avoid. Returns
    # an array of sectors or nil if no path can be found.
    def find_path(start, finish, *avoid_sectors)
      shortest_path(start, finish, avoid_sectors.flatten)
    end

    # find all sectors reachable from start, optionally avoiding
    # specified sectors, and imposing a maximum journey 'cost'
    # (in terms of number of steps from start).
    def find_reachable(start, avoid_sectors  il, maxcost  il)
      all_paths(start,avoid_sectors,maxcost)
    end

    # Generation is very simple, basically making up a tangled
    # mess of randomly connected sectors. You can pass in a code
    # that specifies some parameters used for the generator, 
    # allowing the same galaxy to be generated again by supplying
    # the same code.
    #
    # You should call this manually before using the galaxy, or
    # let +starting_location+ handle that for you if you don't
    # want to load a galaxy or anything.
    #
    # Returns the new galaxy code.
    def generate(code  il)
      # bit odd but gives us a good seed - one call to randomize,
      # one to get the value of that previous random seed, and
      # then set to that.      
      size, max_links, max_planets, seed              decode(code) || [(500 + rand(500)), 5, 5, srand && srand]
   
      clear 
      srand(seed)      
      @sectors  en_bodies(max_planets, gen_sectors(size, max_links))
      
      # seed rand again, don't want to affect rand in game
      srand     
      @code  ncode(size, max_links, max_planets, seed)
    end

    # Vape the galaxy, clears everything.
    def clear
      initialize
    end
        
    # Dump this galaxy to a string in the same format as used by 
    # Jacob Fugal's GalaxyLoader. 
    def dump
      locs  ectors.inject({}) { |h,s| (h[s.location || nil] || ]) << s; h }

      dump  galaxy {\n"
      locs.each do |loc, sectors|
        dump << "  region(#{loc.inspect}) {\n" if loc
        sectors.each do |sector|
          dump << "    sector(#{SpaceMerchant::Galaxy.sectors.index(sector) + 1}) {\n"
          sector.planets.each do |planet|
            dump << "      planet #{planet.name.inspect}\n"
          end
          sector.stations.each do |station|
            dump << "      station #{station.name.inspect}\n"
          end
          unless sector.links.empty?
            dump << "      neighbors "
            dump << sector.links.map { |s| Galaxy.sectors.index(s) + 1 }.join(', ')
            dump << "\n"
          end
          dump << "    }\n"
        end
        dump << "  }\n" if loc
      end
      dump << "}\n"
    end

    alias :to_a :sectors

    private

    # these handle the galaxy codes
    def decode(code)
      if code /^(\d{4})(\d)(\d)([\da-fA-F]+)$/
        [$1.to_i, $2.to_i, $3.to_i, $4.hex]
      end
    end

    def encode(size, max_links, max_planets, seed)
      size.to_s.rjust(4,'0') << 
        max_links.to_s[0,1] << 
        max_planets.to_s[0,1] << 
        sprintf('%x',seed)
    end

    # This whole generation bit is currently sloppy and slow 
    def gen_sectors(size, max_links)        
      sectors  0...size).map { |i| Sector.new("Sector #{i}") }
      avail  ectors.dup
      
      sectors.each do |sector|
        rand(max_links).times do
          to  vail[rand(avail.length)]
          sector.link(to)
          to.link(sector)
          avail.delete(to) if to.links.length > ax_links
        end
      end

      unlinked  ectors.select { |e| e.links.empty? }

      # just makes sure the last few sectors are reachable. Gives
      # a nice varying density to space I think :)
      unless unlinked.empty?
        remain  ectors - unlinked
        unlinked.each do |sector|          
          break unless to  emain[rand(remain.length)] # to hell with it then
          sector.link(to)
          to.link(sector)
        end
      end

      sectors
    end

    def gen_body_name
      (0..(rand(3)+1)).inject("") { |s,i| s << ATOZ[rand(26)] } + 
        rand(5000).to_s + 
        ATOZ[rand(26)]
    end
    
    def gen_bodies(max_planets, sectors)     
      avail  ectors.dup
      ((avail.length / 3) + rand(avail.length / 2)).to_i.times do
        sect  vail.delete_at(rand(avail.length))

        station  and > 0.5
        planets  and(max_planets)

        sect.add_station(Station.new(sect, gen_body_name)) if station
        planets.times { sect.add_planet(Planet.new(sect, gen_body_name)) }
      end       

      sectors 
    end
    
    # returns a hash that associates each reachable (from start)
    # position p, with the previous position on the shortest path
    # from start to p and the length of that path.
    # example: if the shortest path from 0 to 2 is [0, 1, 2], then
    # prev[2]1, 2], prev[1]0, 1] and prev[0]nil, 0].
    # so you can get all shortest paths from start to each reachable
    # position out of the returned hash.
    # stop_at isn't taken into account here, since it's better for us
    # to build full sets we can cache for future use, rather than
    # cutting short and having a lot of less useful path sets.
    def build_prev_hash(start, avoid_sectors  il)
      avoid_sectors || ]
      prevtartnil, 0]} # hash to be returned
    
      # positions which we have seen, but we are not yet sure about
      # the shortest path to them (the value is length of the path,
      # for delete_min_value):
    
      activetart}
      until active.empty?
        # get the position with the shortest path from the
        # active list
        curive.delete_min_value
        newlengthev[cur][1]+1 # path to cur length + 1
    
        # for all reachable neighbors of cur, check if we found
        # a shorter path to them
        cur.links.each { |n|
          # skip sectors we're avoiding
          next if avoid_sectors.include?(n)
          
          if oldev[n] # was n already visited
            # if we found a longer path, ignore it
            next if newlength>d[1]
          end
    
          # (re)add new position to active list
          active[n]
    
          」     
          ロン
ャ ン
        
      
    
      
    
    
     ゜ィャ ャ ゜ゥ
        ロロャ ゜ンン

      」     ャ      
       
         ロン
          」  ャ        
          」 「「  「「
          ン
          ョィゥ  ロンローン
          
        
          
        
      
    
    
     ゜ィャ ゜ャ ゥ
        ロロャ ゜ンン
        ョ  ャ ィャ ゥ  セ    
      ョ  ャ ィャ ゥ ロャ ン 
    
  

   、ー ゜゜ニノフナ゜゜
    」 ヤ        ャ
    」   ヌ  ョ  
     ホ 」ココ 
       ィャ ゥサ タ  ョ゜サ 
       サ タサ 
       コ゜ コ
       サ 「」ョョコ」タ「サ 
       ゥサ  ョサ 
       シゥサ  ショ゜サ 
    
    
     モ シ ホ 」ココ 
       ィャ   ゥ
        ィャ ゥ
        タャ タャ タャ タ  ャ ロンャ ロンャ ロン
      
      ゜ コャ コャ コャ コ
       ゜ィゥサ タ シシ サ 
       ゜ィゥサ タ シシ サ 
       ィゥサ タ シシ サ 
       ゥ
        
           ョ ヲヲ 
             ョ ヲヲ 
             ョ ヲヲ 
            ョ ョョ
         ホヘナ
          
        
      
    
    
     ミ シ ホ 」ココ 
    
    
     モ シ ホ 」ココ 
    
    
     チメヌヨョソ ァュァ
      」」」」
       ァァ

       「」」」 ヌコ「
      ツョ  
        ョ  ヌョ 
      
      
        ョョィーゥ  ャ  ォ ョョ 
       「ヌ  」ヌョョ  ィ」 ゥ「
      
       「ワ」」」 ニ サ ア 「
      ツョ  
          
        ョ    ョ゜ィヌョロウンャャアゥ 
         「」ョッ」ヌョョョ  「
      
      
       「ワ」」」 ニ サ ウ 「
      ツョ  
          
        ョ    ョ゜ィヌョロウンャャウゥ 
         「」ョッ」ヌョョョ  「
      
      
       「ワ」」」 ニ サ  「
      ツョ  
          
        ョ    ョ゜ィヌョロウンゥ 
         「」ョッ」ヌョョョ  「
      
      
       「ワ」」」 ニ サ ウ ャ  」イ「
      ツョ  
          
        ョ    ョ゜ィヌョロウンャロヌョロインンャ ウゥ 
         「」ョッ」ヌョョョ  「
      
      
       「ワ」」」 ニ サ  ャ  」イ「
      ツョ  
          
        ョ    ョ゜ィヌョロウンャロヌョロインンゥ 
         「」ョッ」ヌョョョ  「
      
      
       「ワ」」」 ニ  ロウン  ロュアン「
      ツョ  
          ョ
        ョ  ヌョ゜ィロウンャロュアンゥ 
      
      
       「ワ」」」 ニ  ロウン   ロュアーン「
      ツョ  
          ョ
        ョ  ヌョ゜ィロウンャロュアーンゥ 
      
      
       「ワ」」」 ニ  ロアン  ロュアン「
      ツョ  
          ョ
        ョ  ヌョ゜ィロアンャロュアンゥ 
      
      
       「ワ」」」 ニ  ロアン  ロュオン「
      ツョ  
          ョ
        ョ  ヌョ゜ィロアンャロュオンゥ 
      
      」」」」
    
       ァッァ
     
       ヤヌ シ ヤココユココヤテ
         
          」 モ   
          タア  ョィァアァゥ
          タイ  ョィァイァゥ
          タウ  ョィァウァゥ
          タエ  ョィァエァゥ
          タオ  ョィァオァゥ
          タカ  ョィァカァゥ
          タキ  ョィァキァゥ
          タク  ョィァクァゥ
          
          タアョ  タウン
          タイョ  タアャ タウャ タオン
          タウョ  タイャ タカン
          タエョ  ン
          タオョ  タイン
          タカョ  タキン
          タキョ  タオン
          タクョ  タエャタイン
          
          タアョ  ォ タアア  ョィタアャァアアァゥャ
                           タアイ  ョィタアャァアイァゥン
          タイョ  ォ タイア  ョィタイャァイアァゥャ
                           タイイ  ョィタイャァイイァゥン
          タイョ シシ タイア  ョィタイャァイアァゥ
          タウョ シシ タウア  ョィタウャァウアァゥ
              
          ヌョョ゜   
          ヌョョ シシ タア シシ タイ シシ タウ シシ タエ シシ タオ シシ タカ シシ タキ シシ タク
        
      
         ゜
          ゜ ロンャ ヌョ゜   ョ
        

         ゜゜
            ョ゜   
           ョョソ
            ョ゜
           。ョョソ
          ゜ ャ ョローン
        

         ゜゜
          ゜ ロンャ ヌョ゜    
          ゜ ロタウャ タエャ タオャ タカャ タキャ タクンャ 
              ヌョ゜   ョョソ 
          ゜ ロタアャ タインャ ヌョ゜   ョョ イ 
          ゜ ヌョ゜   ャ ヌョ゜
        

         ゜゜
          ゜ ロンャ ヌョ゜    
          ゜ ロタイアンャ ヌョ゜   ョ ァイアァ 
          ゜ ロタイアャ タイインャ ヌョ゜   ョ ッイョッ 
          ゜ ヌョ゜   ャ ヌョ゜
        

         ゜゜
          ゜ ロンャ ヌョ゜    
          ゜ ロタイアンャ ヌョ゜   ョ ァイアァ 
          ゜ ロタイアャ タウアンャ ヌョ゜    
          ゜ ヌョ゜   ャ ヌョ゜
        

         ゜゜
          」   オ  エ
          ゜ ャ ヌョ゜ィタオャ タエゥ
          ゜ ロタアンャ ヌョ゜ィタアャ タアゥ
          ゜ ロタアャ タウンャ ヌョ゜ィタアャ タウゥ
          ゜ ロタオャ タイャ タアンャ ヌョ゜ィタオャ タアゥ

          」  
          ゜ ロタアャ タウャ タイャ タオンャ ヌョ゜ィタアャ タオゥ
          ゜ ロタアャ タウャ タカャ タキャ タオンャ ヌョ゜ィタアャ タオャ タイゥ
          ゜ ロタアャ タウャ タカャ タキャ タオンャ ヌョ゜ィタアャ タオャ ロタインゥ
        

         ゜゜ 
          」  エ    エ
          ゜ ロロタエャ ーンンャ ヌョ゜ィタエゥ
          ゜ィロロタアャ ーンャ ロタイャ インャ ロタウャ アンャ ロタオャ ウンャ ロタカャ インャ ロタキャ ウンンャ 
                       ヌョ゜ィタアゥョゥ
          ゜ィロロタアャ ーンャ ロタイャ インャ ロタウャ アンャ ロタカャ インンャ
                       ヌョ゜ィタアャャイゥョゥ

          」  
          ゜ィロロタアャ インャ ロタイャ アンャ ロタウャ インャロタエャ アンャロタオャ インャ ロタカャ ウンャ ロタキャ エンャ ロタクャ ーンンャ
                       ヌョ゜ィタクゥョゥ
          ゜ィロロタエャ アンャ ロタクャ ーンンャ
                       ヌョ゜ィタクャロタインャゥョゥ
        

         ゜
          」       
          ヌョ
          ゜ ヌョ

          」   ャ   
            ョ
            ョョ
          ゜ ャ ヌョ

          」   ャ   ソ
          ゜ ヌョャ ヌョ
          ゜゜ ャ ヌョ
          ゜゜ ャ ヌョ

          」     ャ   ソ
          ヌョィゥ
          ゜ ャ ヌョ

          」       
          ゜ ヌョョャ ヌョ゜ィヌョョゥョ

          」        ョ
           。ヌョ゜ョソ
           。ヌョ゜ョソ
        

         ゜          
          ヌョ

            ョ
            ョョ

          ヌョ  ーアーーウウ「 ォ ィァ・ァャ ヤョョ゜ゥ

          ゜゜ ャ ヌョ          
          ゜゜ ャ ヌョ

          ゜ アーーャ ヌョョ

          ヌョ  
          ゜ ャ ヌョ
        

         ソィヌフゥ
           ゜          
            
                ョョ

              ニョィァョァャ ァォァゥ  
                 シシ ヌョ 
              

              ヌョ

              ゜゜ ャ ヌョ

              ヌョ
              ヌョィァョァゥ

              ゜ ャ ヌョ
                          
              ニョィァョァゥ  ニョソィァョァゥ
            
          
        
           「ヌ」   ィヌフ ゥ「
        
      
    
  



ュュラアアォヘッモハキモュュ