Let's share your Javascript/RMMV 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: Finding Array Elements

Spoiler

Intended difficulty level - 2(Little Javascript coding proficiency)

Situation - Consider the below piece of code:

/* Returns null if array's empty Returns the element in array with the smallest property num that's just larger than num if sign equals to 1 Returns the element in array with the largest property 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 property num if sign equals to 1 If there's no such elements, return the element in array with the largest property num if sign equals to -1 No argument will be mutated */function find_min_max_num_prop(array, num, sign) { // Writes your codes here only //}; // find_min_max_num_prop

It's given that:

- array is an Array

- num is a Number

- sign is always either 1 or -1

- Every element in array has a property num, which is a Number

Goal -

Returns null if array's empty

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

Returns the element in array with the largest property 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 property num if sign equals to 1.

If there's no such elements, return the element in array with the largest property 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_prop(although you can add anything you want).

My Hint -

Spoiler

Sort array first.

My Solution -

Spoiler

/* Returns null if array's empty Returns the element in array with the smallest property num that's just larger than num if sign equals to 1 Returns the element in array with the largest property 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 property num if sign equals to 1 If there's no such elements, return the element in array with the largest property num if sign equals to -1 No argument will be mutated */function find_min_max_num_prop(array, num, sign) { // Writes your codes here only if (array.length == 0) { return null; }; var temp_array = []; for (index = 0; index < array.length; index++) { temp_array.push(array[index]); } temp_array.sort(function(a, { return (a.num - b.num) * sign }); for (index = 0; index < array.length; index++) { if (temp_array[index].num * sign > num * sign) { return temp_array[index] } } return temp_array[0] //} // find_min_max_num_prop

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 null if array's empty.

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

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

So it's sure that that ith element'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 smallest/largest element for sign being 1/-1, will be returned.



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

Edit: My solution made some serious mistakes. Now they're all fixed lol

 

[AwesomeCool]

This is a great idea!

Those that want to learn Javascript (or programming in general) should try and do challenges like this.

 

[DoubleX]

This is a great idea!

Those that want to learn Javascript (or programming in general) should try and do challenges like this.

That's exactly what I'm thinking of.

As now I'm still just incredibly nub in Javascript, I can only post easy and simple challenges like this, but I'll try to post harder and more complicated challenges as I improve

 

[AwesomeCool]

@DoubleX - I suggest not giving the solution right away.  May tempt some people to look at the answer who would be interested in trying it.

 

[DoubleX]

Edit: My solution in Challenge 1 made some serious mistakes. Now they're all fixed lol

@DoubleX - I suggest not giving the solution right away.  May tempt some people to look at the answer who would be interested in trying it.

Maybe you're right. I thought a spoiler was enough

Challenge 2: Eliminating Repeated Executions

Spoiler

Intended difficulty level - 3(Some Javascript coding proficiency)

Situation - Consider the below piece of code:

CustomObjManager = { throw new Error("This is a static class");}//-------------------------------------------------------------------//// Eliminates repeated do_something execution for all custom objects ////-------------------------------------------------------------------//// obj: The current custom object executing do_something// objs: An array of all custom objects// active_objs: An array of all active custom objectsCustomObjManager.do_something_once = function(obj, objs, active_objs) { if this.do_something_cond() { // Write your codes here only // }} // CustomObjManager.do_something_once// objs: An array of all custom objects// active_objs: An array of all active custom objectsCustomObj.prototype.do_something = function(objs, active_objs) { this.do_something_part_1(); CustomObjManager.do_something_once(this, objs, active_objs) this.do_something_part_2();} // CustomObj.prototype.do_something

It's given that:

- All custom objects are prototypes of CustomObj.

- objs and active_objs are arrays of 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 true.

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 property called _custom_obj_lock with its elements always being custom objects.

This time I don't include my solution yet. Let's check if it'll be better

 

[DoubleX]

Challenge 3: Tracing Object Properties

Spoiler

Intended difficulty level - 4(Decent javascript coding proficiency)

Situation - Consider the plugin function, plugin call and configuration parts of DoubleX RMMV Object Properties:

// Traces all object properties meeting some conditions linked to the //// queried object //// Designed as a bug diagnosis tool used by Javascript coders with debug //// experience //

Spoiler

//============================================================================////    ** Plugin Call Info                                                     ////       A path in the object property trace will stop if it'd be cyclic      ////----------------------------------------------------------------------------////    * Object manipulations                                                  ////      1. trace_obj_prop(cond, label)                                        ////         - Traces all object properties satisfying function cond linked to  ////           this object                                                      ////         - Labels all traced object properties with function label          ////         - cond and label are functions written in                          ////           Object Property Tracing Condition Function and                   ////           Object Property Tracing Label Function respectively              ////      2. _obj_prop_log[cond]                                                ////         - Returns the log of all traced object properties satisfying       ////           function cond linked to this object                              ////============================================================================//

Spoiler

    //------------------------------------------------------------------------//    // Object Property Tracing Condition Function                             //    // - Setups cond used by trace_obj_prop(cond, label)                      //    //------------------------------------------------------------------------//    // cond must be a function taking the object property as the only argument    // The below examples are added to help you setup your own cond functions    // Checks if the currently traced object's indeed an object    cond_obj: function(obj) {        return typeof obj === "object";    }, // substitute cond with "cond_obj" to use this function    // Checks if the currently traced object's an array    cond_array: function(obj) {        return Array.isArray(obj);    }, // substitute cond with "cond_array" to use this function    // Add your own cond functions here        //------------------------------------------------------------------------//    // Object Property Tracing Label Function                                 //    // - Setups label used by trace_obj_prop(cond, label)                     //    //------------------------------------------------------------------------//    // label must be a function taking the object property as the only argument    // All label functions must return a string    // The below examples are added to help you setup your own label functions    // Always returns the entire object    label_obj: function(obj) {        return obj;    }, // substitute label with "label_obj" to use this function    // Always returns the type(including Array) of each traced object property    label_array: function(obj) {        if (Array.isArray(obj)) {            return "array";        }        return typeof obj;    }, // substitute label with "label_array" to use this function    // Add your own label functions here

The following parts are already implemented:

Spoiler

// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.trace_obj_prop = function(cond, label) { // New // Finish this function's contents //}; // Object.prototype.trace_obj_prop// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.log_obj_prop = function(cond, label) { // New // Finish this function's contents //}; // Object.prototype.log_obj_prop//----------------------------------------------------------------------------//// Label and use all nonempty subtrees to form the object property tree ////----------------------------------------------------------------------------//// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.traverse_obj_prop_tree = function(cond, label) { // New // Finish this function's contents //}; // Object.prototype.traverse_obj_prop_tree// prop: The current object property to be tracedObject.prototype.is_obj_prop = function(prop) { // New // Finish this function's contents //}; // Object.prototype.is_obj_prop

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

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

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

My Hint -

Spoiler

// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.trace_obj_prop = function(cond, label) { // New    if (this._obj_prop_trace === undefined) {        this._obj_prop_log = {};        this._obj_prop_trace = {};    }    // Adds new codes here    //    this._obj_prop_log[cond] = "";    this._obj_prop_trace[cond] = {};    this.log_obj_prop(cond, label);}; // Object.prototype.trace_obj_prop// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.log_obj_prop = function(cond, label) { // New    // Checks if the currently traced object property has object properties    var has_obj_prop = false;    for (prop in this) {        if (this.hasOwnProperty(prop) && this.is_obj_prop(prop)) {            has_obj_prop = true;            break;        }    }    //    if (has_obj_prop) {        this._obj_prop_log[cond] = "{";        this.traverse_obj_prop_tree(cond, label);        this._obj_prop_log[cond] += "}";    }}; // Object.prototype.log_obj_prop//----------------------------------------------------------------------------//// Label and use all nonempty subtrees to form the object property tree       ////----------------------------------------------------------------------------//// cond: The function checking whether an object property will be traced// label: The function returning the label of an traced object propertyObject.prototype.traverse_obj_prop_tree = function(cond, label) { // New    var ot = DoubleX_RMMV.Obj_Prop;    for (prop in this) {        if (this.hasOwnProperty(prop) && this.is_obj_prop(prop)) {            // Adds new codes here            //        }    }}; // Object.prototype.traverse_obj_prop_tree

 

[GaryCXJk]

I think you're thinking too specific here with the challenges. You're asking people to tackle actual problems one may or may not actually face.

You generally want people to tackle problems that are tangible, that people immediately understand. For example:

Prime factorization

Spoiler

Prime factorization is the process of finding the base primes from which an integer is built from. For example, the base primes for the number 18 is 2, 3 and 3, as 18 = 2 * 3 * 3. In number theory, all numbers can be created from a combination of prime numbers, and that combination is unique for each number.

Prime factors are mainly used in encryption algorithms, as you'll always end up with a unique number when you multiply two primes with each other.

Challenge

Write a function that takes one parameter, the number that needs to be factorized. This function must return that number's factor in an array.

You are allowed to make a prime table.

Make sure to test your results to see if they are correct.

Try to aim for a low execution time. You can poll the execution time like this:

var totalTime = 0;var iterations = 5;var executions = 1000;for(var idx = 0; idx < iterations; idx++) { var output = []; var start = new Date(); for var idx2 = 0; idx2 < executions; idx2++) { [...] } var duration = (new Date()) - start; totalTime+= duration; console.log('Time: ' + duration + ' ms');}console.log('Average time: ' + (totalTime / iterations) + ' ms');

This example is short and simple, and would only need minor alterations for it to be used for other purposes. It's an exercise that doesn't exactly have a certain goal other than to challenge somebody.

 

[DoubleX]

I think you're thinking too specific here with the challenges. You're asking people to tackle actual problems one may or may not actually face.

You generally want people to tackle problems that are tangible, that people immediately understand. For example:

Prime factorization

Spoiler

Prime factorization is the process of finding the base primes from which an integer is built from. For example, the base primes for the number 18 is 2, 3 and 3, as 18 = 2 * 3 * 3. In number theory, all numbers can be created from a combination of prime numbers, and that combination is unique for each number.

Prime factors are mainly used in encryption algorithms, as you'll always end up with a unique number when you multiply two primes with each other.

Challenge

Write a function that takes one parameter, the number that needs to be factorized. This function must return that number's factor in an array.

You are allowed to make a prime table.

Make sure to test your results to see if they are correct.

Try to aim for a low execution time. You can poll the execution time like this:

var totalTime = 0;var iterations = 5;var executions = 1000;for(var idx = 0; idx < iterations; idx++) { var output = []; var start = new Date(); for var idx2 = 0; idx2 < executions; idx2++) { [...] } var duration = (new Date()) - start; totalTime+= duration; console.log('Time: ' + duration + ' ms');}console.log('Average time: ' + (totalTime / iterations) + ' ms');

Spoiler

This example is short and simple, and would only need minor alterations for it to be used for other purposes. It's an exercise that doesn't exactly have a certain goal other than to challenge somebody.

My attempt:

Spoiler

// int: The integer to be factorized into base primesfunction prime_factorization(int) { var base_primes = []; // Stores all base primes in the ascending order for (index = 0; index < all_primes.length; index++) { // Stops if the current prime's too large to be a base prime if (int < all_primes[index] * all_primes[index]) { break; } // // Factorize int by the current base prime repeatedly while (int % all_primes[index] === 0) { base_primes.push(all_primes[index]); int /= all_primes[index]; } // } // Pushes the last base prime into the base prime list base_primes.push(int); //}; // prime_factorizationWhere all_primes is a built-in prime table containing all primes sorted in the ascending order.

Correctness:

1. A prime number's a base prime of int if and only if int is divisible by that prime number.

2. As all_primes is sorted in the ascending order, if int is smaller than the square of the currently checked prime number, it's sure that all the remaining prime numbers are either already pushed into base_primes or not base primes of int, as any prime number that's larger than the square root of int must multiply with one that's smaller than the square root of int in order to get int as the product.

3. As the function always check the currently smallest unchecked prime number before checking larger ones, it's impossible to miss the smaller base primes.

4. As base_primes always stores all the currently collected base primes of int in the ascending order, before the last base prime's pushed into base_primes, the product of all base primes currently stored in base_primes multiplying the current value of int always equals to the originally passed int.

5. If more than 1 base prime's the same prime number, they'll all be pushed into base_primes, as the current value of int is always repeated divided by the current prime number which is known to be a base prime of the current value of int, until that current number becomes not being a base prime number of the current value of int.

- Combining, if a prime number's a base prime of the current value of int, if must also be a base prime of the originally passed int, meaning that base primes always stores the correct base primes of int, including the last value of int itself, which is always the last base prime of the originally passed int.

Execution Time:

The loosest lower bound is O(logn)(base 2), where n is the value of the originally passed int, as 2 is the smallest prime number, meaning 2 ^ n being the passed int is the local best case for numbers around that value.

The loosest upper bound is O(n ^ 0.5), where n is the value of the originally passed int, as a prime number being the passed int is the local worst case for numbers around that value, meaning every prime number from 2 to the one just smaller than the square root of int will be checked before pushing the originally passed int as the sole base prime.

I hope this attempt at least makes a little sense XD

 

[Tsukihime]

I think you're thinking too specific here with the challenges. You're asking people to tackle actual problems one may or may not actually face.

Isn't that what makes them challenges? A lot of challenges are unrealistic. For example, school examinations.

 

[DoubleX]

My solution to Challenge 2: Eliminating Repeated Executions

Spoiler

//-------------------------------------------------------------------//// Eliminates repeated do_something execution for all custom objects ////-------------------------------------------------------------------//// obj: The current custom object executing do_something// objs: An array of all custom objects// active_objs: An array of all active custom objectsCustomObjManager.do_something_once = function(obj, objs, active_objs) { if this.do_something_cond() { // Write your codes here only this._custom_obj_lock = this._custom_obj_lock || []; var index = this._custom_obj_lock.indexOf(obj); if (index !== -1) { return this._custom_obj_lock.splice(index, 1); } this._custom_obj_lock = objs.filter(function(o) { return o !== obj; }); var inactive_objs = objs.filter(function(0) { return active_objs.indexOf(o) === -1; }); inactive_objs.forEach(function (element, index, array) { element.do_something(objs, active_objs); }); // }}; // CustomObjManager.do_something_once

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

Proof:

- 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.

So it's always 100% correct

 

[DoubleX]

Challenge 4: Ranking Player Scores

Spoiler

Intended difficulty level - 2(Little javascript coding proficiency)

Situation - Consider the below piece of code:

"use strict";// players: All players to have their ranks made based on their scoresfunction makePlayerRanks(players) { // Writes your codes here only //}; // makePlayerRanks

It's given that:

- players is an Array, where every element always has Number properties id, rank and score.

- 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 makePlayerRanks.

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 makePlayerRanks, only rank of each element in players can be different from what it's right before calling makePlayerRanks.

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

Constraint - You can only add new code in makePlayerRanks 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

"use strict";// players: All players to have their ranks made based on their scoresfunction makePlayerRanks(players) { if (players.length > 0) { var block = function(a, { return b.score - a.score }; players.sort(block); // Sets rank of all elements with the ith highest score as i var length = players.length; var min = 0; var max = 0; var rank = 1 var score = null; for (var index = 0; index < length; index++) { if (score) { if (score === players[index].score) { max = index; if (index === length - 1) { for (var i = min; i <= max; i++) { players.rank = rank; } break; } continue; } for (var i = min; i <= max; i++) { players.rank = rank; } min = index; max = index; rank += 1; score = player.score; if (index === size - 1) { players[index].rank = rank; } } else { score = players[index].score; } } // block = function(a, { return a.id - b.id }; players.sort(block); }}; // makePlayerRanks

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

Proof:

Right after calling makePlayerRanks, only rank of each element in players can be different from what it's right before calling makePlayerRanks, 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 makePlayerRanks.

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 makePlayerRanks.

 

[DoubleX]

Challenge 5: Implementing Linked Battlers

Spoiler

Intended difficulty level - 4(Decent javascript coding proficiency)

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

* # State Notetags: * 1. <linked battlers: LBCX, LBSX, LBWX> * - Sets all 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 of the * original stat change due to hitting the min/max stat value, thost * not being taken by that battler will be shared by the rest of the * linked battlers also * - The battler originally having a stat to be changed is the last * linked battler taking the change not shared by any other ones * - LBCX can be set in Linked Battler Condition Functions * - LBSX can be set in Linked Battler Stat Functions * - LBWX can be set in Linked Battler Weight Functions

Spoiler

    /*------------------------------------------------------------------------     *    Linked Battler Condition Functions                                       *    - Setups LBCX used by <linked battlers: LBCX, LBSX, LBWX>                *------------------------------------------------------------------------*/    /* LBCX are used in functions included in LINKED_STATS     * LBCX are functions that will be bound to battler calling them upon use     * LBCX names can only use alphanumeric characters     * Each linked battler besides the caller can be referenced by battler     * The caller will always pass LBCX even when it's supposed to fail     * 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: function(battler) { return true; },    /* Sets the linked battler condition to include all and no linked battlers     * if switch with id x is on and off respectively     */    LBC2: function(battler) { return $gameSwitches.value(x); },    // Adds new LBCX here        /*------------------------------------------------------------------------     *    Linked Battler Stat Functions                                            *    - Setups LBSX used by <linked battlers: LBCX, LBSX, LBWX>                *------------------------------------------------------------------------*/    /* LBSX are used in functions included in LINKED_STATS     * LBSX are functions that will be bound to battlers upon use     * LBSX names can only use alphanumeric characters     * It must return an Array, which should include all strings of getter     * functions 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: function() { return ["hp", "mp", "tp"]; },    // Sets the linked battler stat to include nothing    LBS2: function() { return []; },    // Adds new LBSX here        /*------------------------------------------------------------------------     *    Linked Battler Weight Functions                                          *    - Setups LBWX used by <linked battlers: LBCX, LBSX, LBWX>                *------------------------------------------------------------------------*/    /* LBWX are used in functions included in LINKED_STATS     * LBWX are functions that will be bound to battlers upon use     * LBWX names can only use alphanumeric characters     * It must return a Number     * No stat change will take place for any linked battler if the sum of all     * weights of all linked battlers is 0     * Each linked battler besides the caller 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: function(battler) { return 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:  function(battler) { return battler === this ? x : 1; },    // Adds new LBWX here        /* Sets the battler functions to be used by linked battlers     * Its property names must be the battler stat getter function names     * Its values must be Arrays, each containing the battler stat setter     * function name, the index of the argument as the original new stat value     * in the stat setter function argument list, and each linked battler's     * min/max stat value     * All battler functions as min/max stat value must be referenced by this     * All the included battler stat getter functions will be extended     */    LINKED_STATS: {      /* General form:       * FunctionClass: {       *     getter: ["setter", statArgIndex, "statMin", "statMax"]       * }       */      Game_BattlerBase: {        /* General form:          * getter: ["setter", statArgIndex, "statMin", "statMax"]         */        hp: ["setHp", 0, "0", "this.mhp"],        mp: ["setMp", 0, "0", "this.mmp"],        tp: ["setTp", 0, "0", "this.maxTp()"]        // Adds new functions here              }      // Adds new classes here          }

The notetag reading and helper parts are already implemented:

Spoiler

LB.DataManager = {}; var DM = LB.DataManager; DM.isDatabaseLoaded = DataManager.isDatabaseLoaded; DataManager.isDatabaseLoaded = function() { // Rewritten return DM.isDatabaseLoaded.apply(this, arguments) && DM.loadAllNotes(); // }; // DataManager.isDatabaseLoaded DM.loadAllNotes = function() { $dataStates.forEach(function(data) { if (data) { DM.loadStateNotes(data); } }); return true; }; // DM.loadAllNotes // data: The data to have its notetags read DM.loadStateNotes = function(data) { var regExp = /< *linked +battlers *: *(\w+) *, *(\w+) *, *(\w+) *>/i; data.meta.linkedBattlers = []; var linkedBattlers = data.meta.linkedBattlers; // Stores all LBCX-LBSX-LBWX triples in 1 single Array sequentially data.note.split(/[\r\n]+/).forEach(function(line) { if (!line.match(regExp)) { return; } linkedBattlers.push([RegExp.$1, RegExp.$2, RegExp.$3]); }); // }; // DM.loadStateNotes

Spoiler

    LB.Game_BattlerBase = {};    var GBB = LB.Game_BattlerBase, gf = "getLinkedBattlers";    GBB[gf] = function(stateId, cond) {        var aliveMems = $gameParty.aliveMembers() + $gameTroop.aliveMembers();        return aliveMems.filter(function(mem) {            return mem.isStateAdded(stateId) && LB[cond].call(this, mem);        }, this);    }; // GBB[gf]    GBB.linkedBattlersStateId = function(stat) {        if (!this._states) { return null; }        var linkedBattlers, states = this.states();        // Returns the (1st applicable LBCX-LBSX-LBWX triple and state id) pair        for (var index = 0, length = states.length; index < length; index++) {            linkedBattlers = states[index].linkedBattlers;            for (var i = 0, l = linkedBattlers.length; i < l; i++) {            	if (LB[linkedBattlers[i][1]].call(this).indexOf(stat) >= 0) {            	    return [linkedBattlers[i], states[index].id];            	}            }        }        //        return null;    }; // GBB.linkedBattlersStateId

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

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

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

My Hint -

Spoiler

    var Proto, Klass, func;    for (var k in LB.LINKED_STATS) {        if (!LB.LINKED_STATS.hasOwnProperty(k)) { continue; }        LB[k] = LB[k] || {}; // Ensures container GBB won't be rewritten        Proto = eval(k + ".prototype"); // Actual class prototype        Klass = LB.LINKED_STATS[k]; // Class name as string        for (var g in Klass) {            if (!Klass.hasOwnProperty(g)) { continue; }            func = Klass[g]; // ["setter", statArgIndex, "statMin", "statMax"] // Finishes the rest of the plugin implementations here //        }    }

My Solution -

Spoiler

    var Proto, Klass, func;    for (var k in LB.LINKED_STATS) {        if (!LB.LINKED_STATS.hasOwnProperty(k)) { continue; }        LB[k] = LB[k] || {}; // Ensures container GBB won't be rewritten        Proto = eval(k + ".prototype"); // Actual class prototype        Klass = LB.LINKED_STATS[k]; // Class name as string        for (var g in Klass) {            if (!Klass.hasOwnProperty(g)) { continue; }            func = Klass[g]; // ["setter", statArgIndex, "statMin", "statMax"]            /*----------------------------------------------------------------             *    Extends all stat setter functions to have shared stat change             *----------------------------------------------------------------*/            LB[k][func[0]] = Proto[func[0]];            Proto[func[0]] = new Function ([                "this._linkedBattler = GBB.linkedBattlersStateId.call(this, g);",                "if (this._linkedBattler) {",                "    return LB." + k + "." + gf + g + ".apply(this, arguments);",                "}",                "LB." + k + "." + func[0] + ".apply(this, arguments);",            ].join("\n")); // Proto[func[0]]            /*----------------------------------------------------------------             *    Redistributes the stat change to all found linked battlers               *----------------------------------------------------------------*/            LB[k][gf + g] = new Function ([                "var lB = this._linkedBattler[0];",                "var stateId = this._linkedBattler[1];",                "var mems = GBB." + gf + ".call(this, stateId, lB[0]);",                "var index = mems.indexOf(this);",                "if (index >= 0) { mems.splice(index, 1); }",                "mems.push(this);",                "var weights = mems.map(function(mem) {",                "    return LB[lB[2]].call(this, mem);",                "}, this);",                "var weightSum = weights.reduce(function(a, {",                "    return a + b;",                "}, 0);",                "if (weightSum === 0) { return; }",                "var statDiff = arguments[" + func[1] + "] - this[g];",                "var statChange, newStat, minStat, maxStat;",                "for (var i = 0, l = mems.length; i < l; i++) {",                "    statChange = statDiff * weights / weightSum;",                "    newStat = mems." + g + " + statChange;",                "    minStat = LB[k].min" + g + ".call(mems);",                "    maxStat = LB[k].max" + g + ".call(mems);",                "    if (newStat < minStat) {",                "        statChange = mems." + g + " - minStat;",                "        arguments[" + func[1] + "] = minStat;",                "    } else if (newStat > maxStat) {",                "        statChange = maxStat - mems." + g + ";",                "        arguments[" + func[1] + "] = maxStat;",                "    } else {",                "        arguments[" + func[1] + "] = newStat;",                "    }",                "    LB[k]." + func[0] + ".apply(mems, arguments);",                "    statDiff -= statChange;",                "    weightSum -= weights;",                "}",            ].join("\n")); // LB[k][gf + g]            // Returns the minimum stat value            LB[k]["min" + g] = new Function("return " + func[2] + ";");            // Returns the maximum stat value            LB[k]["max" + g] = new Function("return " + func[3] + ";");        }    }

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

Proof:

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

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

The new setter functions first check if the battler's linked with any other battler via any linking states, and calls the original setter functions if there's none.

If that's not the case, then the new LB[klass][gf + get] function 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 all 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 of the *           original stat change due to hitting the min/max stat value, thost *           not being taken by that battler will be shared by the rest of the *           linked battlers also                                              *         - The battler originally having a stat to be changed is the last    *           linked battler taking the change not shared by any other ones     *         - LBCX can be set in Linked Battler Condition Functions             *         - LBSX can be set in Linked Battler Stat Functions                  *         - LBWX can be set in Linked Battler Weight Functions

 

[DoubleX]

Challenge 3: Controlling RNG Randomness

Spoiler

Intended difficulty level - 2(Little Javascript coding proficiency)


Situation - Consider the below piece of code:








var RNGController = {

    /* The number of equally-sized partitions of the range of return values of
     * Math.random()
     * The ith partition is [(i - 1) / numParts, i / numParts)
     * If the result of a Math.random() call lies within a partition, that
     * partition is said to be used
     * No Math.random() calls can return a Number within a used partition
     * If all numParts partitions are used when Math.random() is called, all
     * those partitions will be reset to be unused to let that
     * Math.random() call return a Number lying within 1 of those partitions
     */
    numParts: x,

// Writes your codes here

//

}; // RNGController

(function(RNGC) {

'use strict';

RNGC.Math = {};
var M = RNGC.Math;

M.random = Math.random;
Math.random = function() {
// Writes your codes here

//
}; // Math.random

})(RNGController);

It's given that:


- numParts is a Number


Goal -


Extends Math.random() to control the RNG using RNGController.numParts in the manner described in the comments showing what RNGController.numParts does


The possible range of values returned by the extended Math.random() should be the same as that of the original Math.random()


The expected value of the extended Math.random() should be at least extremely close to that of the original Math.random()


Example -


The below lists 20 consecutive extended Math.random() call results with RNGController.numParts 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 RNGController and the extended Math.random()(although you can add anything you want)


My Hint -

Spoiler

var RNGController = {

    /* The number of equally-sized partitions of the range of return values of
     * Math.random()
     * The ith partition is [(i - 1) / numParts, i / numParts)
     * If the result of a Math.random() call lies within a partition, that
     * partition is said to be used
     * No Math.random() calls can return a Number within a used partition
     * If all numParts partitions are used when Math.random() is called, all
     * those partitions will be reset to be unused to let that
     * Math.random() call return a Number lying within 1 of those partitions
     */
    numParts: x,

// Write your codes here
usedParts: []
//

}; // RNGController

My Solution -

Spoiler

var RNGController = {

    /* The number of equally-sized partitions of the range of return values of
     * Math.random()
     * The ith partition is [(i - 1) / numParts, i / numParts)
     * If the result of a Math.random() call lies within a partition, that
     * partition is said to be used
     * No Math.random() calls can return a Number within a used partition
     * If all numParts partitions are used when Math.random() is called, all
     * those partitions will be reset to be unused to let that
     * Math.random() call return a Number lying within 1 of those partitions
     */
    numParts: x,

// The storage of all used partitions
usedParts: []
//

}; // RNGController

(function(RNGC) {

'use strict';

    RNGC.Math = {};
    var M = RNGC.Math;

    M.random = Math.random;
    Math.random = function() {
        // Rewritten to only return RNG within an unused partition
        if (RNGC.usedParts >= RNGC.numParts) { RNGC.usedParts.length = 0; }
        var partIndex, rng;
        do {
            rng = M.random.apply(this, arguments);
            partIndex = Math.floor(rng * RNGC.numParts);
        } while (RNGC.usedParts.indexOf(partIndex) >= 0);
        RNGC.usedParts.push(partIndex);
        return rng;
        //
    }; // Math.random

})(RNGController);

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


Proof:


Initially RNGController.usedParts is empty.


If RNGController.usedParts already has RNGController.numParts elements, it will be reset to have 0 elements.


When calling the extended Math.random(), partIndex will always return a random Integer within [0, RNGController.numParts - 1], as the original Math.random() always return a Number within [0, 1).


It also means rng is always equal to [partIndex / RNGController.numParts, (partIndex + 1) / RNGController.numParts).


Besides, if RNGController.usedParts already contains the current value of partIndex, a new part index will be generated from multiplying the result of a new original Math.random() call with RNGController.numParts.


As the do while loop can only be reached when RNGController.usedParts has less than RNGController.numParts elements, that loop will eventually generate a partIndex value that's not already included by RNGController.usedParts.


This will lead to that partIndex value being stored as an element in RNGController.usedParts, preventing subsequent extended Math.random() calls to accept that partIndex value as the final partIndex value.


After RNGController.numParts extended Math.random() calls, RNGController.usedParts will have RNGController.numParts elements, leading to the reset of RNGController.usedParts.


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
* Math.random()
* The ith partition is [(i - 1) / numParts, i / numParts)
* If the result of a Math.random() call lies within a partition, that
* partition is said to be used
* No Math.random() calls can return a Number within a used partition
* If all numParts partitions are used when Math.random() is called, all
* those partitions will be reset to be unused to let that
* Math.random() call return a Number lying within 1 of those partitions
*/

About the possible range of values returned by the extended Math.random():

Spoiler

When the value returned by the extended Math.random() lies within the ith partition, the possible range of values of that extended Math.random() call is [(i - 1) / numParts, i / numParts).


As all the numParts partitions will be used after numParts extended Math.random() call, the possible range of values returned by the extended Math.random() =


[0, 1 / numParts) + [1 / numParts, 2 / numParts) + [2 / numParts, 3 / numParts) + ... + [(numParts - 1) / numParts, 1)


= [0, 1)


Which is the possible range of values returned by the original Math.random().

About the expected value of the extended Math.random():

Spoiler

Let -


- X be the random variable of the original Math.random()


- Y be the random variable of the extended Math.random()


Then -


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


Also, for the ith extended Math.random() call in each consecutive RNGController.numParts extended Math.random() calls, let -


- P(i) be the final value of partIndex


- X(i) be the random variable of a random number within [P(i) / RNGController.numParts, (P(i) + 1) / RNGController.numParts) generated by the original Math.random() call


- Y(i) be the random variable of this extended Math.random() call


Then -


- Y(i) = X(i)


- E(Y(i) ) = E(X(i) ) = (P(i) / RNGController.numParts + (P(i) + 1) / RNGController.numParts) / 2 = (2P(i) + 1) / RNGController.numParts / 2


So over an extremely large number of consecutive RNGController.numParts extended Math.random() calls -


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


          = [(2P[1] + 1) + (2P[2] + 1) + (2P[3] + 1) + ... + (2P[RNGController.numParts] + 1)] / RNGController.numParts / 2 / RNGController.numParts


          = [2(RNGController.numParts - 1)(RNGController.numParts) / 2 + RNGController.numParts] / RNGController.numParts ^ 2 / 2


          = RNGController.numParts ^ 2 / RNGController.numParts ^ 2 / 2


          = 1 / 2


          = E(X)


Meaning that the expected value of the extended Math.random() is at least extremely close to that of the original Math.random().