Let's share your RGSS3 algorithm challenges here

[DoubleX]

This post aims to incite you to share some algorithm challenges, so we can learn from those challenges, seek for answers for difficult problems we're facing, and hopefully apply their answers in case we encounter similar issues

Let's start by sharing mine:

Challenge 1: Eliminating Repeated Executions

Spoiler

Intended difficulty level - 3(Some scripting proficiency)

Situation - Consider the below piece of code:

module CustomObjManager attr_reader :custom_objs # An array of all custom objects attr_reader :active_custom_objs # An array of all active custom objects # Eliminates repeated do_something execution for all custom objects def self.do_something_once(obj) return unless do_something_cond # Write your codes here only # end # do_something_onceend # CustomObjManagerclass CustomObj def do_something do_something_part_1 CustomObjManager.do_something_once(self) do_something_part_2 end # do_somethingend # CustomObj

It's given that:

- All custom objects are instances of CustomObj.

- @custom_objs and @active_custom_objs will always 100% correctly store all custom objects and all active custom objects respectively.

- Everything's run by 1 single thread only(i.e.: no multithreading, concurrent computing, parallel programming, etc, so there's no need to worry about race conditions).

- When 1 special event starts, each active custom object will call do_something, but any other custom object(i.e., non active custom object) will only call do_something via do_something_once, which can only be called via do_something.

- do_something_cond will always return the same result during any such special event.

Goal - Ensures that no active custom object will call do_something more than once during any such special event, and each non active custom object will also call do_something exactly once during that special event if and only if do_something_cond returns a TrueClass.

Condition - Your codes must always be 100% correct in this situation.

Constraint - You can only add new codes in parts specified by do_something_once(although you can add anything whenever you want).

My Hint -

Spoiler

Use 1 array instance variable called @custom_obj_lock with its elements always being custom objects.

My Solution -

Spoiler

# Eliminates repeated do_something execution for all custom objects def self.do_something_once(obj) return unless do_something_cond # Write your codes here only @custom_obj_lock ||= [] return @custom_obj_lock.delete(obj) if @custom_obj_lock.include?(obj) @custom_obj_lock = @custom_objs - [obj] (@custom_objs - @active_custom_objs).each { |obj| obj.do_something } # end # do_something_once

It achieves the goal, meets the conditions and conform to the constraint.

Proof:

Case 1 - do_something_cond returns a TrueClass

- As everything's run by 1 single thread only, only 1 custom object will be within do_something_once at a time.

- When a custom object becomes the 1st one entering do_something_once, @custom_obj_lock will be an empty array.

- That custom object will then push every other custom objects into @custom_obj_lock, and ask all non active custom objects to call do_something.

- When any other custom object enters do_something_once, it'll delete itself from @custom_obj_lock and exit that method.

- It means no other active custom object will call do_something more than once, and all non active custom object will only call do_something once.

- When the special event ends, @custom_obj_lock will become an empty array again, as all custom objects have called do_something_once exactly once.

Case 2 - do_something_cond returns a FalseClass

- Every active custom object will call do_something_once and then immediately return to do_something.

- It means no active custom object will call do_something more than once, and no non active custom object will ever call do_something.

Combining these 2 cases, this solution's always 100% correct in the specified situation.



I'll continue to post more and more. Let's share yours, so we can all benefit from each other here

Edit: The intended difficulty level of Challenge 1: Eliminating Repeated Executions changed from 4(Decent scripting proficiency) to 3(Some scripting proficiency), as it turned out to be much easier than what I've initially thought lol

 

[DoubleX]

Challenge 2: Finding Array Elements

Spoiler

Intended difficulty level - 2(Little scripting proficiency)

Situation - Consider the below piece of code:

# Returns nil if array's empty# Returns the element in array with the smallest attribute num that's just# larger than num if sign equals to 1# Returns the element in array with the largest attribute num that's just# smaller than num if sign equals to -1# If there's more than 1 such elements, return any of them# If there's no such elements, return the element in array with the smallest# attribute num if sign equals to 1# If there's no such elements, return the element in array with the largest# attribute num if sign equals to -1# No argument will be mutated */def find_min_max_num_attr(array, num, sign) # Writes your codes here only #end # find_min_max_num_attr

It's given that:

- array is an Array

- num is a Numeric

- sign is always either 1 or -1

- Every element in array has an attribute num, which is a Numeric

Goal -

Returns nil if array's empty

Returns the element in array with the smallest attribute num that's just larger than num if sign equals to 1.

Returns the element in array with the largest attribute num that's just smaller than num if sign equals to -1.

If there's more than 1 such elements, return any of them.

If there's no such elements, return the element in array with the smallest attribute num if sign equals to 1.

If there's no such elements, return the element in array with the largest attribute num if sign equals to -1.

No argument will be mutated.

Condition - Your codes must always be 100% correct in this situation.

Constraint - You can only add new code in find_min_max_num_attr(although you can add anything you want).

My Hint -

Spoiler

Sort array first.

My Solution -

Spoiler

# Returns nil if array's empty# Returns the element in array with the smallest attribute num that's just# larger than num if sign equals to 1# Returns the element in array with the largest attribute num that's just# smaller than num if sign equals to -1# If there's more than 1 such elements, return any of them# If there's no such elements, return the element in array with the smallest# attribute num if sign equals to 1# If there's no such elements, return the element in array with the largest# attribute num if sign equals to -1# No argument will be mutated */def find_min_max_num_attr(array, num, sign) # Writes your codes here only return nil if array.empty? temp_array = array.sort { |a, b| a * sign <=> b * sign } temp_array.each { |element| return element if element.num * sign > num * sign } temp_array[o] #end # find_min_max_num_attr

It achieves the goal, meets the condition and conform to the constraint.

Proof:

It doesn't mutate any passed argument as temp_array is the only mutated variable, which isn't linked to any passed ones.

It's always 100% correct because -

It returns nil if array's empty.

temp_array's num attributes are always sorted in ascending and descending order if sign's equal to 1 and -1 respectively.

If the ith element's num attribute's larges/smaller than num for sign being 1/-1, so do all the (i + j)th elements' num attributes.

So it's sure that that ith element's num attribute's the smallest/largest one that's just larger/smaller than num for sign begin 1/-1.

If no such element's found, the 1st element, which must be the one having the smallest/largest num attribute for sign being 1/-1, will be returned.



Challenge 3: Implementing Linked Battlers

Spoiler

Intended difficulty level - 4(Decent scripting proficiency)

Situation - Consider the notetag info and configuration part of DoubleX RMVXA Linked Battlers:

#  * State Notetags:                                                           |#    1. <linked battlers: LBCX, LBSX, LBWX>                                    |#       - Sets the owners of this state meeting LBCX to share stats included in|#         LBSX with weight LBWX applied to each of them when any included stat |#         of any included battler changes                                      |#       - Only the 1st applicable notetag of the state with the highest        |#         priority will be applied to the stat change of the linked battler    |#       - If a linked battler can't take all of that battler's share due to    |#         hitting the minimum or maximum stat value, thost not being taken by  |#         that battler will be shared by the rest of the linked battlers also  |#       - The battler having a stat to be changed is the last linked battler   |#         taking that battler's share                                          |#       - LBCX can be set in Linked Battler Condition Notetag Values           |#       - LBSX can be set in Linked Battler Stat Notetag Values                |#       - LBWX can be set in Linked Battler Weight Notetag Values              |

Spoiler

    #--------------------------------------------------------------------------|    #  Linked Battler Condition Notetag Values                                 |    #  - Setups LBCX used by this script's notetags                            |    #--------------------------------------------------------------------------|    # LBCX are used in methods included in LINKED_STAT    # LBCX are strings of RGSS3 codes    # LBCX names can only use alphanumeric characters    # The battler having a stat to be changed can be referenced by target    # Each of the rest of the linked battlers can be referenced by battler    # The below LBCX are examples added to help you set your LBCX    # You can freely use, rewrite and/or delete these examples    # Sets the linked battler condition to include all linked battlers    LBC1 = %Q(true)    # Sets the linked battler condition to include all and no linked battlers if    # switch with id x is on and off respectively    LBC2 = %Q($game_switches[x])    # Sets the linked battler condition to include all linked battlers that are    # opponents of the battler having a stat to be changed    LBC3 = %Q(target.opposite?(battler))    # Adds new LBCX here        #--------------------------------------------------------------------------|    #  Linked Battler Stat Notetag Values                                      |    #  - Setups LBSX used by this script's notetags                            |    #--------------------------------------------------------------------------|    # LBSX are used in methods included in LINKED_STAT    # LBSX are strings of RGSS3 codes    # LBSX names can only use alphanumeric characters    # It must return an array, which should include strings of a getter method    # of each stat to be included    # The below LBSX are examples added to help you set your LBSX    # You can freely use, rewrite and/or delete these examples    # Sets the linked battler stat to include hp, mp and tp    LBS1 = %Q(["hp", "mp", "tp"])    # Sets the linked battler stat to always include hp and mp, and include tp    # only if it's displayed in battle    LBS2 = %Q(["hp", "mp", $data_system.opt_display_tp ? "tp" : nil])    # Sets the linked battler stat to include nothing    LBS3 = %Q([])    # Adds new LBSX here        #--------------------------------------------------------------------------|    #  Linked Battler Weight Notetag Values                                    |    #  - Setups LBWX used by this script's notetags                            |    #--------------------------------------------------------------------------|    # LBWX are used in methods included in LINKED_STAT    # LBWX are strings of RGSS3 codes    # LBWX names can only use alphanumeric characters    # It must return a real number    # The battler having a stat to be changed can be referenced by target    # Each of the rest of the linked battlers can be referenced by battler    # The below LBWX are examples added to help you set your LBWX    # You can freely use, rewrite and/or delete these examples    # Sets the linked battler weight to be the same for all linked battlers    LBW1 = %Q(1)    # Sets the linked battler weight to be multiplied by x if the linked battler    # is the one having a stat to be changed    LBW2 = %Q(battler == target ? x : 1)    # Sets the linked battler weight to be 0 for all linked battlers    LBW3 = %Q(0)    # Adds new LBWX here        # Sets the battler methods to be used by linked battlers    # Its keys must be the battler stat getter method string    # Its values must be an array containing the battler stat setter method,    # its argument list, the one being modified, and the minimum and maximum    # value of that battler stat of each linked battler    # The methods returning those minimum and maximum values must be referenced    # by battler    # Methods with name method_name will be aliased to    # linked_battlers_method_name    LINKED_STATS = {      # General form:      # [:def_class, :super_class] => {      #   "getter" => ["setter", "args", "mod arg", "stat_min", "stat_max"]      # }      [:Game_BattlerBase] => {        # General form:        # "getter" => ["setter", "args", "mod arg", "stat_min", "stat_max"]        "hp" => ["hp=", "hp", "hp", "0", "battler.mhp"],        "mp" => ["mp=", "mp", "mp", "0", "battler.mmp"],        "tp" => ["tp=", "tp", "tp", "0", "battler.max_tp"]        # Adds new methods here              }      # Adds new classes here          }

The notetag reading and helper parts are already implemented:

Spoiler

class << DataManager # Edit alias load_database_linked_battlers load_database def load_database(*argv, &argb) load_database_linked_battlers(*argv, &argb) $data_states.each { |obj| obj.load_notetags_linked_battlers if obj } # Added end # load_databaseend # DataManagerclass RPG::State < RPG::BaseItem # Edit #----------------------------------------------------------------------------| # New public instance variable | #----------------------------------------------------------------------------| attr_accessor :linked_battlers # An array of all linked battler notetag values def load_notetags_linked_battlers # New @linked_battlers = [] lb = "DoubleX_RMVXA::Linked_Battlers::" @note.split(/[\r\n]+/).each { |line| case line when /<linked battlers:\s*(\w+)\s*,\s*(\w+)\s*,\s*(\w+)\s*>/ @linked_battlers << [eval("-> battler, target { target.instance_exec { #{eval("#{lb}#{$1}")} } }"), eval("-> target { target.instance_exec { #{eval("#{lb}#{$2}")} } }"), eval("-> battler, target { target.instance_exec { #{eval("#{lb}#{$3}")} } }")] end } end # load_notetags_linked_battlersend # RPG::State

Spoiler

#------------------------------------------------------------------------------|#  *  Adds helper methods used by methods used by linked battlers              |#------------------------------------------------------------------------------|class Game_BattlerBase # Edit  # state_id: The id of the state to be included by all linked battlers  # cond: The conditions for a linked battlers to be included  def get_linked_battlers(state_id, &cond) # New    ($game_party.alive_members + $game_troop.alive_members).select! { |mem|      mem.state?(state_id) && cond.call(mem, self)    }  end # get_linked_battlers  # stat: The stat of a linked battler to be changed  def linked_battler_state_id(stat) # New    @states.each { |state_id|      $data_states[state_id].linked_battlers.each { |lb|        return [lb, state_id] if lb[1].call(self).include?(stat)      }    }    nil  end # linked_battler_state_idend # Game_BattlerBase

Goal - Finish the rest of the script implementations to make this script works as intended.

Condition - Your implementations must always be 100% correct for this script alone except for bugs coming from the default RMVXA codebase itself.

Constraint - This script must be able to be completely standalone.

My Hint -

Spoiler

# Aliases methods used by linked battlersDoubleX_RMVXA::Linked_Battlers::LINKED_STATS.each { |klass, defs| klass_def = %Q(class #{klass[0].id2name}#{klass[1] ? " < #{klass[1].id2name}" : ""}) defs.each { |get, stat| klass_def += %Q( # Finish the rest of the script implementations # ) } eval(klass_def + %Q(end))}

My Solution -

Spoiler

# Aliases methods used by linked battlersDoubleX_RMVXA::Linked_Battlers::LINKED_STATS.each { |klass, defs| klass_def = %Q(class #{klass[0].id2name}#{klass[1] ? " < #{klass[1].id2name}" : ""}) defs.each { |get, stat| klass_def += %Q( alias linked_battlers_#{stat[0]} #{stat[0]} def #{stat[0]}(#{stat[1]}) lb_si = linked_battler_state_id("#{get}") return self.linked_battlers_#{stat[0]}(#{stat[1]}) unless lb_si get_linked_battlers_#{get}(#{stat[1]}, lb_si[0], lb_si[1]) end def get_linked_battlers_#{get}(#{stat[1]}, linked_battler, state_id) battlers = get_linked_battlers(state_id, &linked_battler[0]) index = battlers.index(self) battlers[index], battlers[-1] = battlers[-1], battlers[index] weights = battlers.collect { |b| linked_battler[2].call(b, self) } return if (sum = weights.inject+)) == 0 diff = #{stat[2]} - self.#{get} set_linked_battlers_#{get}(#{stat[1]}, battlers, diff, sum, weights) end def set_linked_battlers_#{get}(#{stat[1]}, battlers, diff, sum, weights) battlers.each_with_index { |battler, index| change = diff * (weight = weights[index]) / sum if (new_stat = battler.#{get} + change) < min = #{stat[3]} change = battler.#{get} - min #{stat[2]} = min elsif new_stat > max = #{stat[4]} change = max - battler.#{get} #{stat[2]} = max else #{stat[2]} = new_stat end battler.linked_battlers_#{stat[0]}(#{stat[1]}) diff -= change sum -= weight } end) } eval(klass_def + %Q(end))}

It achieves the goal, meets the condition and conform to the constraint.

Proof:

This script's completely standalone as it assumes nothing from any other custom script, including their existences.

It's always 100% correct because for this script alone except for bugs coming from the default RMVXA codebase itself because -

The new setter methods first checks if the battler's linked with any other battler via any linking states, and calls the aliased ones if there's none.

If that's not the case, then the new get_linked_battlers_#{get} method will first collect all linked battlers for the stat using the setter, then the current battler will be swapped to be the last battler among all the linked ones.

Next, the array of all weights among all linked battlers as well as their sum, and the difference between the would be new stat and the current stat will be calculated and used.

After that, each linked battler will take the (weight / weight sum) * 100% of the stat difference and check if the new stat of that battler would break its min or max.

If that's the case, the portion exceeding those boundaries will be redistributed to the rest of the linked battlers, otherwise that battler will take the original share entirely.

As the battler originally undergoing stat change is the last linked battler, all the undistributed stat change will be taken by that battler.

It means all the below requirements are satisfied:

Spoiler

#       - Sets the owners of this state meeting LBCX to share stats included in|#         LBSX with weight LBWX applied to each of them when any included stat |#         of any included battler changes                                      |#       - Only the 1st applicable notetag of the state with the highest        |#         priority will be applied to the stat change of the linked battler    |#       - If a linked battler can't take all of that battler's share due to    |#         hitting the minimum or maximum stat value, those not being taken by  |#         that battler will be shared by the rest of the linked battlers also  |#       - The battler having a stat to be changed is the last linked battler   |#         taking that battler's share                                          |

 

[DoubleX]

Challenge 4: Building Object Subtrees

Spoiler

Intended difficulty level - 4(Decent scripting proficiency)

Situation - Consider the script function, example(somehow outdated but still showing what the script can do), script call and configuration parts of DoubleX RMVXA Object Trace:

#------------------------------------------------------------------------------|# * Functions |# Traces all objects meeting some conditions linked to the queried object |# Designed as a bug diagnosis tool used by scripters with debug experience |#------------------------------------------------------------------------------|# * Example |# obj.inspect |# - http://pastebin.com/kb1q1Dru |# obj.trace_obj(Proc); obj.obj_trace[Proc].inspect |# - http://pastebin.com/PZ4KNbHv |#------------------------------------------------------------------------------|

Spoiler

#==============================================================================|#  ** Script Call Info                                                         |#     A path in the object trace will stop if it'd be cyclic                   |#------------------------------------------------------------------------------|#  * Object manipulations                                                      |#    1. trace_obj(cond, label)                                                 |#       - Traces all objects meeting cond method linked to this object         |#       - Labels all traced objects using label method                         |#       - cond and label are method symbols in Object Trace Condition Method   |#         and Object Trace Label Method respectively                           |#    2. obj_trace[cond]                                                        |#       - Returns all traced objects meeting cond method linked to this object |#       - cond is a method symbol in Object Trace Condition Method             |#    3. (v1.01a+)trace_idef                                                    |#       - Traces all instance methods linked to this object                    |#    4. (v1.01a+)idef_trace                                                    |#       - Returns the trace of all instance methods linked to this object      |#==============================================================================|

Spoiler

    #--------------------------------------------------------------------------|    #  Object Trace Condition Method                                           |    #  - Setups cond used by trace_obj(cond, label)                            |    #--------------------------------------------------------------------------|    # cond must be the symbol of a method taking the currently traced object as    # the only arguement    # The below examples are added to help you setup your own cond methods    # Checks if the currently traced object belongs to klass    def self.cond_klass(obj)        obj.is_a?(klass)    end # cond_klass    # Add your own cond methods here        #--------------------------------------------------------------------------|    #  Object Trace Label Method                                               |    #  - Setups label used by trace_obj(cond, label)                           |    #--------------------------------------------------------------------------|    # label must be the symbol of a method taking the currently traced object as    # the only arguement    # The below examples are added to help you setup your own label methods    # Labels all traced objects using their class symbol    def self.label_klass(obj)        :"#{obj.class}"    end # label_klass    # Add your own label methods here

The following parts are already implemented:

Spoiler

class Object # Edit #----------------------------------------------------------------------------| # New public instance variables | #----------------------------------------------------------------------------| attr_reader :idef_trace # (v1.01a+)The trace of all linked instance methods attr_reader bj_trace # The traces of all objects linked to this object # (v1.01a+)The list of symbols of all instance variables added by this script OBJ_TRACE_IVAR = [:"@idef_trace", :"@obj_trace"] def trace_idef # v1.01a+; New # Fills this method's contents # end # trace_idef def trace_instance_idef # v1.01a+; New # Fills this method's contents # end # trace_instance_idef def trace_array_idef # v1.01a+; New # Fills this method's contents # end # trace_array_idef def trace_hash_idef # v1.01a+; New # Fills this method's contents # end # trace_hash_idef def trace_range_idef # v1.01a+; New # Fills this method's contents # end # trace_range_idef def trace_struct_idef # v1.01a+; New # Fills this method's contents # end # trace_struct_idef # Adds new methods here if you wants to # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_obj(cond, label) # New # Fills this method's contents # end # trace_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_instance_obj(cond, label) # New # Fills this method's contents # end # trace_instance_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_array_obj(cond, label) # New # Fills this method's contents # end # trace_array_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_hash_obj(cond, label) # New # Fills this method's contents # end # trace_hash_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_range_obj(cond, label) # v1.00b+; New # Fills this method's contents # end # trace_range_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_struct_obj(cond, label) # v1.00b+; New # Fills this method's contents # end # trace_struct_obj # Adds new methods here if you wants to end # Object

Goal - Finish the rest of the script implementations to make this script works as intended except for new data structures that are neither Array, Hash, Range nor Struct.

Condition - Your implementations must always be 100% correct for this script alone except for bugs coming from the default RMVXA codebase itself.

Constraint - This script must be able to be completely standalone.

My Hint -

Spoiler

def trace_idef # v1.01a+; New # Adds some codes here # trace_instance_idef return trace_array_idef if is_a?(Array) return trace_hash_idef if is_a?(Hash) return trace_range_idef if is_a?(Range) trace_struct_idef if is_a?(Struct) end # trace_idef def trace_instance_idef # v1.01a+; New # Adds some codes here # end # trace_instance_idef def trace_array_idef # v1.01a+; New each_with_index { |val, index| traverse_idef_tree(index, val) } end # trace_array_idef def trace_hash_idef # v1.01a+; New each { |key, val| traverse_idef_tree(key, val) } end # trace_hash_idef def trace_range_idef # v1.01a+; New index = -1 each { |val| traverse_idef_tree(index += 1, val) } end # trace_range_idef def trace_struct_idef # v1.01a+; New each_pair { |key, val| traverse_idef_tree(key, val) } end # trace_struct_idef #----------------------------------------------------------------------------| # Label and use all nonempty subtrees to form the original object trace tree| #----------------------------------------------------------------------------| # iks: The index/key/symbol of the object trace # val: The object to be traced def traverse_idef_tree(iks, val) # v1.01a+; New # Fills this method's contents # end # traverse_idef_tree # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_obj(cond, label) # New # Adds some codes here # trace_instance_obj(cond, label) return trace_array_obj(cond, label) if is_a?(Array) return trace_hash_obj(cond, label) if is_a?(Hash) return trace_range_obj(cond, label) if is_a?(Range) trace_struct_obj(cond, label) if is_a?(Struct) end # trace_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_instance_obj(cond, label) # New (instance_variables - OBJ_TRACE_IVAR).each { |ivar| trace_all_obj(cond, label, ivar, instance_variable_get(ivar)) } end # trace_instance_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_array_obj(cond, label) # New each_with_index { |val, index| trace_all_obj(cond, label, index, val) } end # trace_array_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_hash_obj(cond, label) # New each { |key, val| trace_all_obj(cond, label, key, val) } end # trace_hash_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_range_obj(cond, label) # v1.00b+; New # Embeds the klass traces of all ranges linking to this object index = -1 each { |val| trace_all_obj(cond, label, index += 1, val) } # end # trace_range_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_struct_obj(cond, label) # v1.00b+; New each_pair { |key, val| trace_all_obj(cond, label, key, val) } end # trace_struct_obj #----------------------------------------------------------------------------| # Label and use all nonempty subtrees to form the original object trace tree| #----------------------------------------------------------------------------| # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument # iks: The index/key/symbol of the object trace # val: The object to be traced def trace_all_obj(cond, label, iks, val) # v1.01a+; New # Fills this method's contents # end # trace_all_obj

My Solution -

Spoiler

def trace_idef # v1.01a+; New # Stop tracing the object if the object trace path would be cyclic @idef_trace ? return : @idef_trace = {} # trace_instance_idef return trace_array_idef if is_a?(Array) return trace_hash_idef if is_a?(Hash) return trace_range_idef if is_a?(Range) trace_struct_idef if is_a?(Struct) end # trace_idef def trace_instance_idef # v1.01a+; New (instance_variables - OBJ_TRACE_IVAR).each { |ivar| traverse_idef_tree(ivar, instance_variable_get(ivar)) } end # trace_instance_idef def trace_array_idef # v1.01a+; New each_with_index { |val, index| traverse_idef_tree(index, val) } end # trace_array_idef def trace_hash_idef # v1.01a+; New each { |key, val| traverse_idef_tree(key, val) } end # trace_hash_idef def trace_range_idef # v1.01a+; New index = -1 each { |val| traverse_idef_tree(index += 1, val) } end # trace_range_idef def trace_struct_idef # v1.01a+; New each_pair { |key, val| traverse_idef_tree(key, val) } end # trace_struct_idef #----------------------------------------------------------------------------| # Label and use all nonempty subtrees to form the original object trace tree| #----------------------------------------------------------------------------| # iks: The index/key/symbol of the object trace # val: The object to be traced def traverse_idef_tree(iks, val) # v1.01a+; New # Recursively traverse the object trace tree using Depth First Search unless (idefs = val.instance_methods).empty? @idef_trace[iks] = [idefs] end val.trace_idef return if (trace = val.idef_trace).empty? (@obj_trace[iks] ||= []) << trace # end # traverse_idef_tree # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_obj(cond, label) # New # Stop tracing the object if the object trace path would be cyclic (@obj_trace ||= {})[cond] ? return : @obj_trace[cond] = {} # trace_instance_obj(cond, label) return trace_array_obj(cond, label) if is_a?(Array) return trace_hash_obj(cond, label) if is_a?(Hash) return trace_range_obj(cond, label) if is_a?(Range) trace_struct_obj(cond, label) if is_a?(Struct) end # trace_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_instance_obj(cond, label) # New (instance_variables - OBJ_TRACE_IVAR).each { |ivar| trace_all_obj(cond, label, ivar, instance_variable_get(ivar)) } end # trace_instance_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_array_obj(cond, label) # New each_with_index { |val, index| trace_all_obj(cond, label, index, val) } end # trace_array_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_hash_obj(cond, label) # New each { |key, val| trace_all_obj(cond, label, key, val) } end # trace_hash_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_range_obj(cond, label) # v1.00b+; New # Embeds the klass traces of all ranges linking to this object index = -1 each { |val| trace_all_obj(cond, label, index += 1, val) } # end # trace_range_obj # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument def trace_struct_obj(cond, label) # v1.00b+; New each_pair { |key, val| trace_all_obj(cond, label, key, val) } end # trace_struct_obj #----------------------------------------------------------------------------| # Label and use all nonempty subtrees to form the original object trace tree| #----------------------------------------------------------------------------| # cond: The object trace condition method symbol taking the object as argument # label: The object trace label method symbol taking the object as argument # iks: The index/key/symbol of the object trace # val: The object to be traced def trace_all_obj(cond, label, iks, val) # v1.01a+; New # Recursively traverse the object trace tree using Depth First Search ot = DoubleX_RMVXA:bj_Trace @obj_trace[cond][iks] = [ot.send(label, val)] if ot.send(cond, val) val.trace_obj(cond, label) return if (trace = val.obj_trace[cond]).empty? (@obj_trace[cond][iks] ||= []) << trace # end # trace_all_obj

It achieves the goal, meets the condition and conform to the constraint.

Proof:

Only the proof of the instance variable case will be shown, as that of the instance methods is basically the same.

This script's completely standalone as it assumes nothing from any other custom script, including their existences.

It's always 100% correct because for this script alone except for bugs coming from the default RMVXA codebase itself because -

1. Neither new instance variable, @idef_trace nor @obj_trace, will be traced by the script, as instance_variables is always subtracted by OBJ_TRACE_IVAR before tracing any remaining instance variables.

2. The trace will always be finite as no object will contain an infinite number of objects, and this:

(@obj_trace ||= {})[cond] ? return : @obj_trace[cond] = {}ensures the trace will never be ever cyclic.

3. Every instance variable other than those added by the script will be traced for the currently traced object, and every element/value/attribute of that object will be traced as well if it's an Array/Hash/Range/Struct.

4. The original object trace tree can always be formed by combining all the nonempty subtrees of all objects directly linked to the originally queried object.

5. As the 1st instance variable/element/value/attribute of the currently traced object's always traced first, the recursive tree traversal uses Depth First Search, meaning that all objects linked to that object will be traced.

6. Eventually, the trace will reach an object containing no other object.

7. If an object contains no labeled object, its object trace tree will be empty, otherwise it'll only contain all labeled ones.

8. An object trace tree of an linked object will be embedded to that of the currently traced one if and only if the former isn't empty or that linked object is itself labeled.

Combining, an object's trace tree will only embed all subtrees containing all labeled objects indirectly linked to that object, and all labeled objects directly linked to that object.

When the recursion goes back to the originally traced object, the entire object trace tree containing all labeled objects directly or indirectly linked to that object will be formed.

As similar analysis also applies to tracing instance methods, it means all the below script calls are always 100% correctly implemented:

Spoiler

#    1. trace_obj(cond, label)                                                 |#       - Traces all objects meeting cond method linked to this object         |#       - Labels all traced objects using label method                         |#       - cond and label are method symbols in Object Trace Condition Method   |#         and Object Trace Label Method respectively                           |#    2. obj_trace[cond]                                                        |#       - Returns all traced objects meeting cond method linked to this object |#       - cond is a method symbol in Object Trace Condition Method             |#    3. (v1.01a+)trace_idef                                                    |#       - Traces all instance methods linked to this object                    |#    4. (v1.01a+)idef_trace                                                    |#       - Returns the trace of all instance methods linked to this object      |

 

[DoubleX]

Challenge 5: Ranking Player Scores

Spoiler

Intended difficulty level - 2(Little scripting proficiency)

Situation - Consider the below piece of code:

# players: All players to have their ranks made based on their scoresdef make_player_ranks(players) # Writes your codes here only #end # make_player_ranks

It's given that:

- players is an Array, where every element always has Numeric attributes id, rank and score, each having its own accessor.

- The id of each element in players is always unique.

- players is always sorted in ascending order according to its element's id before being passed into make_player_ranks.

Goal -

Does nothing if players is empty.

Sets rank of each element in players as i if score of that element's the ith largest one.

Elements in players having the same score shall also have the same rank.

Right after calling make_player_ranks, only rank of each element in players can be different from what it's right before calling make_player_ranks.

Condition - Your codes must always be 100% correct in this situation except for bugs coming from Ruby itself.

Constraint - You can only add new code in make_player_ranks although you can add anything you want.

My Hint -

Spoiler

Simply sorting players according to their elements' score won't be enough as their id also do have their uses.

My Solution -

Spoiler

# players: All players to have their ranks made based on their scoresdef make_player_ranks(players)  return if players.empty?  block = -> a, b { b.score <=> a.score }  players.sort!(&block)  # Sets rank of all elements with the ith highest score as i  min = max = 0  rank = 1  score = nil  size = players.size  set_rank = -> index { players[index].rank = rank }  block = -> player, index {    next score = player.score unless score    if score == player.score      max = index      break (min..max).each(&set_rank) if index == size - 1      next    end    (min..max).each(&set_rank)    min = max = index    rank += 1    score = player.score    player.rank = rank if index == size - 1  }  players.each_with_index(&block)  #  block = -> a, b { a.id <=> b.id }  players.sort!(&block)end # make_player_ranks

It achieves the goal, meets the condition and conforms to the constraint.

Proof:

Right after calling make_player_ranks, only rank of each element in players can be different from what it's right before calling make_player_ranks, because -

1. id and score of each element in players are never changed.

2. The orderings among elements in players are initially changed, but will be restored back to the original orderings, as both the initial and final state of players in this method is sorted in ascending order according to their elements' id, each of which is unique, meaning the orderings among elements in players will always be the same outside make_player_ranks.

It's always 100% correct in this situation because -

1. It always does nothing if players is empty.

2. It first sorts players in descending order according to their elements' score.

3. It then uses rank to mark the currently lowest unmarked rank, score to mark all consecutive elements having the same score, and min and max to mark the smallest and largest index among all those elements.

4. Once all those consecutive elements are found for the currently lowest unmarked rank, their rank will be set as that currently lowest unmarked rank.

5. After that, the currently lowest unmarked rank will be increased by 1, and the loop will continue until all elements are looped through.

6. Now rank of each element in players are always 100% correct.

7. Finally, players will be sorted back in ascending order according to their elements' id, meaning nothing else's different from what's passed into make_player_ranks.

 

[DoubleX]

Challenge 6: Controlling RNG Randomness

Spoiler

Intended difficulty level - 2(Little RGSS3 scripting proficiency)


Situation - Consider the below piece of code:








module RNG_Controller

  # The number of equally-sized partitions of the range of return values of rand
  # The ith partition is [(i - 1) / FLOAT_NUM_PARTS, i / FLOAT_NUM_PARTS)
  # If the result of a rand call lies within a partition, that partition is said
  # to be used
  # No rand calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand is called, all those
  # partitions will be reset to be unused to let that rand call return a Numeric
  # lying within 1 of those partitions
  # If FLOAT_NUM_PARTS is set as nonpositive, FLOAT_NUM_PARTS will become 1 for
  # all rand calls
  FLOAT_NUM_PARTS = 10

  # The number of equally-sized partitions of the range of return values of
  # rand(a)
  # The ith partition is [a(i - 1) / INT_NUM_PARTS, ai / INT_NUM_PARTS)
  # If the result of a rand(a) call lies within a partition, that partition is
  # said to be used
  # No rand(a) calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand(a) is called, all those
  # partitions will be reset to be unused to let that rand(a) call return a
  # Numeric lying within 1 of those partitions
  # If INT_NUM_PARTS is set as nonpositive, INT_NUM_PARTS will become a for a
  # rand(a) call
  INT_NUM_PARTS = 10

  # Writes your code here
 
  #

end # RNG_Controller

module Kernel

alias rand_rng_controller rand
def rand(max = 0, &argb)
# Writes your codes here
#
end # rand

end # Kernel

It's given that:


- NUM_PARTS is an Integer


Goal -


Alias rand to control the RNG using RNG_Controller::FLOAT_NUM_PARTS and RNG_Controller::INT_NUM_PARTS in the manner described in the comments showing what RNG_Controller::FLOAT_NUM_PARTS and RNG_Controller::INT_NUM_PARTS do respectively


The possible range of va;ues of rand should still be that of the aliased rand


The expected value of rand should be at least extremely close to that of the aliased rand


Example -


The below lists 20 consecutive extended rand call results with RNG_Controller::FLOAT_NUM_PARTS being 10:

Spoiler

0.5583369022811258 // 6 - [0.5, 0.6)
0.8856774551202906 // 9 - [0.8, 0.9)
0.7053351634934172 // 8 - [0.7, 0.8)
0.2910141721648054 // 3 - [0.2, 0.3)
0.46443921703774416 // 5 - [0.4, 0.5)
0.34247765359444715 // 4 - [0.3, 0.4)
0.9611230852360236 // 10 - [0.9, 1)
0.170055669517572 // 2 - [0.1, 0.2)
0.6280946076323228 // 7 - [0.6, 0.7)
0.09900382018076581 // 1 - [0, 0.1)
(all the 10 partitions are used after the 1st 10 consecutive Math.random() call and thus reset to become unused again)
0.49970969353564276 // 5 - [0.4, 0.5)
0.19670031315146652 // 2 - [0.1, 0.2)
0.6183234115814623 // 7 - [0.6, 0.7)
0.9592661473226407 // 10 - [0.9, 1)
0.837747307203645 // 9 - [0.8, 0.9)
0.06670947818157003 // 1 - [0, 0.1)
0.20614586616388186 // 3 - [0.2, 0.3)
0.38808043042462215 // 4 - [0.3, 0.4)
0.7973840400497697 // 8 - [0.7, 0.8)
0.5467456358572309 // 6 - [0.5, 0.6)

Condition - Your codes must always be 100% correct in this situation


Constraint - You can only add new code in RNG_Controller and the rand(although you can add anything you want)


My Hint -

Spoiler

module RNG_Controller

  # The number of equally-sized partitions of the range of return values of rand
  # The ith partition is [(i - 1) / FLOAT_NUM_PARTS, i / FLOAT_NUM_PARTS)
  # If the result of a rand call lies within a partition, that partition is said
  # to be used
  # No rand calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand is called, all those
  # partitions will be reset to be unused to let that rand call return a Numeric
  # lying within 1 of those partitions
  # If FLOAT_NUM_PARTS is set as nonpositive, FLOAT_NUM_PARTS will become 1 for
  # all rand calls
  FLOAT_NUM_PARTS = 10

  # The number of equally-sized partitions of the range of return values of
  # rand(a)
  # The ith partition is [a(i - 1) / INT_NUM_PARTS, ai / INT_NUM_PARTS)
  # If the result of a rand(a) call lies within a partition, that partition is
  # said to be used
  # No rand(a) calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand(a) is called, all those
  # partitions will be reset to be unused to let that rand(a) call return a
  # Numeric lying within 1 of those partitions
  # If INT_NUM_PARTS is set as nonpositive, INT_NUM_PARTS will become a for a
  # rand(a) call
  INT_NUM_PARTS = 10

  # The storage of all used partitions
  USED_PARTS = []
  #

end # RNG_Controller

My Solution -

Spoiler

module RNG_Controller

  # The number of equally-sized partitions of the range of return values of rand
  # The ith partition is [(i - 1) / FLOAT_NUM_PARTS, i / FLOAT_NUM_PARTS)
  # If the result of a rand call lies within a partition, that partition is said
  # to be used
  # No rand calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand is called, all those
  # partitions will be reset to be unused to let that rand call return a Numeric
  # lying within 1 of those partitions
  # If FLOAT_NUM_PARTS is set as nonpositive, FLOAT_NUM_PARTS will become 1 for
  # all rand calls
  FLOAT_NUM_PARTS = 10

  # The number of equally-sized partitions of the range of return values of
  # rand(a)
  # The ith partition is [a(i - 1) / INT_NUM_PARTS, ai / INT_NUM_PARTS)
  # If the result of a rand(a) call lies within a partition, that partition is
  # said to be used
  # No rand(a) calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand(a) is called, all those
  # partitions will be reset to be unused to let that rand(a) call return a
  # Numeric lying within 1 of those partitions
  # If INT_NUM_PARTS is set as nonpositive, INT_NUM_PARTS will become a for a
  # rand(a) call
  INT_NUM_PARTS = 10

  # The storage of all used partitions
  USED_PARTS = []
  #

end # RNG_Controller

module Kernel

  alias rand_rng_controller rand
  def rand(max = 0, &argb)
    # Rewritten to only return RNG within an unused partition
    if max.abs >= 1
      num_parts = RNG_Controller::INT_NUM_PARTS
      num_parts = max.to_i.abs if num_parts <= 0
    else
      num_parts = [RNG_Controller::FLOAT_NUM_PARTS, 1].max
    end
    used_parts = RNG_Controller::USED_PARTS
    used_parts.clear if used_parts.size >= num_parts
    begin
      part_index = rand_rng_controller(num_parts, &argb)
    end while used_parts.include?(part_index)
    used_parts.push(part_index)
    (rand_rng_controller(max, &argb) + part_index * [max, 1].max) / num_parts
    #
  end # rand

end # Kernel

It achieves the goal, meets the condition and conform to the constraint.


Proof:


Initially RNG_Controller::USED_PARTS is empty.


If RNG_Controller::USED_PARTS already has num_parts elements, it will be reset to have 0 elements.


When calling rand, part_index will always return a random Integer within [0, num_parts - 1] which is generated by the aliased rand(num_parts).


It also means the returned Numeric is always within [part_index * max / num_parts, (part_index * max + [max, 1].max) / num_parts), as the aliased rand(max) always returns a Numeric within [0, max).


So the ith partition of a rand call will be [(i - 1) / FLOAT_NUM_PARTS, i / FLOAT_NUM_PARTS), and that of a rand(a) call will be [a(i - 1) / INT_NUM_PARTS, ai / INT_NUM_PARTS).


Besides, if RNG_Controller::USED_PARTS already contains the current value of part_index, a new part index will be generated from multiplying the result of a new aliased rand call with num_parts.


As the do while loop can only be reached when RNG_Controller::USED_PARTS has less than num_parts elements, that loop will eventually generate a part_indexvalue that's not already included by RNG_Controller::USED_PARTS.


This will lead to that part_index value being stored as an element in RNG_Controller::USED_PARTS, preventing subsequent rand calls to accept that part_index value as the final part_index value.


After num_parts rand calls, RNG_Controller::USED_PARTS will have num_parts elements, leading to the reset of RNG_Controller::USED_PARTS.


Combining, the above codes are always 100% correct in the below situation:

Spoiler

  # The number of equally-sized partitions of the range of return values of rand
  # The ith partition is [(i - 1) / FLOAT_NUM_PARTS, i / FLOAT_NUM_PARTS)
  # If the result of a rand call lies within a partition, that partition is said
  # to be used
  # No rand calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand is called, all those
  # partitions will be reset to be unused to let that rand call return a Numeric
  # lying within 1 of those partitions
  # If FLOAT_NUM_PARTS is set as nonpositive, FLOAT_NUM_PARTS will become 1 for
  # all rand calls
  FLOAT_NUM_PARTS = 10

  # The number of equally-sized partitions of the range of return values of
  # rand(a)
  # The ith partition is [a(i - 1) / INT_NUM_PARTS, ai / INT_NUM_PARTS)
  # If the result of a rand(a) call lies within a partition, that partition is
  # said to be used
  # No rand(a) calls can return a Numeric within a used partition
  # If all FLOAT_NUM_PARTS partitions are used when rand(a) is called, all those
  # partitions will be reset to be unused to let that rand(a) call return a
  # Numeric lying within 1 of those partitions
  # If INT_NUM_PARTS is set as nonpositive, INT_NUM_PARTS will become a for a
  # rand(a) call
  INT_NUM_PARTS = 10

About the possible range of values returned by rand:

Spoiler

The value returned by rand is (rand_rng_controller(max, &argb) + part_index * [max, 1].max) / num_parts, where rand_rng_controller(max, &argb) is the value returned by the aliased rand.


As the possible range of values returned by the aliased rand is [0, max), and the possible range of values of part_index is [0, num_parts - 1], the possible range of values returned by rand =


([0, max) + [0, num_parts - 1] * [max, 1].max) / num_parts


= [0, max / num_parts) + [max / num_parts, max * 2 / num_parts) + [max * 2 / num_parts, max * 3 / num_parts) + ... + [max * (num_parts - 1) / num_parts, max * num_parts / num_parts)


= [0, max)


So the possible range of values returned by rand is that of the aliased rand.

About the expected value of rand:

Spoiler

Let -


- Max be the maximum value that can be returned by the aliased rand


- X be the random variable of the aliased rand


- Y be the random variable of rand


Then -


- E(X) = (Max - 0) / 2 = Max / 2


Also, for the ith rand call in each consecutive num_parts rand calls, let -


- P(i) be the final value of part_index


- X(i) be the random variable of a random number within [Max * P(i) / num_parts, Max * (P(i) + 1) / num_parts) generated by the aliased rand call


- Y(i) be the random variable of this rand call


Then -


- Y(i) = X(i)


- E(Y(i)) = E(X(i)) = (Max * P(i) / num_parts + Max * (P(i) + 1) / num_parts) / 2 = Max * (2P(i) + 1) / num_parts / 2


So over an extremely large number of consecutive num_parts rand calls -


- E(Y) = E(Y[1]) / num_parts + E(Y[2]) / num_parts + E(Y[3]) / num_parts + ... + E(Y[num_parts]) / num_parts


          = Max * [(2P[1] + 1) + (2P[2] + 1) + (2P[3] + 1) + ... + (2P[num_parts] + 1)] / num_parts / 2 / num_parts


          = Max * [2(num_parts - 1)(num_parts) / 2 + num_parts] / num_parts ^ 2 / 2


          = Max * num_parts ^ 2 / num_parts ^ 2 / 2


          = Max / 2


          = E(X)


Meaning that the expected value of rand is at least extremely close to that of the aliased rand.