DEV Community: PhilipSterling

Basic RegExp in JS

PhilipSterling — Mon, 19 Aug 2019 21:58:12 +0000

Regular Expressions or Regex are strings used for describing search patterns within text.

var pattern = new RegExp(pattern, attributes);
//or 
var pattern = /pattern/attributes;
//eg pattern = /\n/g or pattern = new RegExp(\n,g)
//for newline characters globally

It gets complicated

/[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,6}/i
//What is this?

The Pattern Example-

In order to better understand patterns in regex I will show some complicated examples and break them down into understandable components.

//Philip@example.com
/[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,6}/i
//this is the regex for identifying an email address string 
//regardless of address

//First component
//Philip
/[A-Z0-9._%+-]/
//This component looks for a string containing a through z
//represented by A-Z or 0-9 represented by 0-9 then the other
//allowed characters in the first part of an email which are
// . _ % + -

//Second component
//Philip@
/+@/
//This component makes the return whatever block came before the
//@ sign in the email address and checks for the @ sign

//Third component
//Philip@example
/[A-Z0-9.-]/
//This component makes the return a any character block that includes
// a through z 0 through 9 . and -

//Fourth component
//Philip@example.
/+\./
//This component makes the return add a . by use of \. which
//escapes the dot in

//Fifth component
//Philip@example.com
/[A-Z]{2,6}/
//This component adds the values of any string a through z that is
//between 2 and 6 characters long.
//For example .co would work but .o or .comcomo would not

The Attributes Example -

These are typically used for the characters 'g' 'i' and 'm' which allow you to search (g) globally through the whole string, (i) independent of case, and (m) in multiline matches

//In our example case we used the attribute /i so that it would accept
//independent of case for any character a through z

Basic Patterns to know -

//Special Characters
//Any special characters have to be escaped into the regex 
//through the use of the \ character, these include
\0 - null

\t - tab

\n - newline

\. - .

\[ - [

//and so on

//Quantifiers
//Quantifiers determine the amount of a certain character or pattern you are looking for

a* - 0 or more a's

a+ - 1 or more a's

a? - 0 to 1 a's

a$ - any string that ends in a

^a - any string that begins with a

a{2} - exactly 2 a's in sequence

a{2,} - 2 or more a's in sequence

a{2,4} - 2 to 4 a's in sequence

//Metacharacters
//Metacharacters are used to represent a variety of character with
//limited input

. - any single character

\s - whitespace

\S - not whitespace

\d - decimal digit

\D - not a decimal digit

\w - alphanumeric character

\W - not alphanumeric character

{ab|bc} - or operator

//Ranges
//Ranges of characters are done in regex through bracket notation

[A-Z] - all characters a through z

[.] - all dots

[^.] - all not dots

That is all the basic inputs for regex that allow you to better create patterns for string searching.

Sources

https://regexr.com/ - Useful tool for testing out your regexes to make sure they are working before implementing them.

Simple Radix Sort

PhilipSterling — Thu, 08 Aug 2019 20:02:25 +0000

Sorting data takes time.

In order to better understand radix sort I recommend you either read my previous post on counting sort or any documentation on how counting sort works because the LSD Radix sort is built off of counting sorts.

In most radix sorts you start by sorting the LSD (least significant digit) then moving through all the digits until you reach the (MSD) most significant digit.

The definition of Radix (or base) is the number of unique digits including 0 to represent numbers in a number system.

Binary has a radix of 2.
Hexadecimal has a radix of 16.
The Decimal system or Base-10 typical system you use daily has a radix of 10.

An LSD Radix sort can be run in JavaScript with two inputs. The first for the array to be sorted and the second for the largest number of digits in a single element of the array.

function LSDRadixSort(array, radix) {

  //sets the radix to base 10 by default unless otherwise specified.
  radix = radix || 10;

  // Determine minimum and maximum values in the array to be sorted.
  var minValue = array[0];
  var maxValue = array[0];
  for (var i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i];
    } else if (array[i] > maxValue) {
      maxValue = array[i];
    }
  }

  var exponent = 1;
  // This while loop runs a counting sort for each index in an array from
  //least significant to most significant
  while ((maxValue - minValue) / exponent >= 1) {

    array = countingSortByDigit(array, radix, exponent, minValue);

    exponent *= radix;
  }

  return array;
}

function countingSortByDigit(array, radix, exponent, minValue) {
  var i;
  var bucketIndex;
  var buckets = new Array(radix);
  var output = new Array(array.length);

  // Initialize the bucket array
  for (i = 0; i < radix; i++) {
    buckets[i] = 0;
  }

  // Count the frequencies
  for (i = 0; i < array.length; i++) {
    bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
    buckets[bucketIndex]++;
  }

  // Compute cumulative amounts
  for (i = 1; i < radix; i++) {
    buckets[i] += buckets[i - 1];
  }

  // Move items in the array to be sorted
  for (i = array.length - 1; i >= 0; i--) {
    bucketIndex = Math.floor(((array[i] - minValue) / exponent) % radix);
    output[--buckets[bucketIndex]] = array[i];
  }

  // set output to the original array
  for (i = 0; i < array.length; i++) {
    array[i] = output[i];
  }

  return array;
}

Now radix seems complicated but if we break it down to a simple example it becomes a lot easier to understand.
Lets say that there is an array of numbers in base 10 that we want to sort

[99, 88, 2 ,33 ,79, 44, 10]

when we are in the while loop of the radix sort we would first sort by the ones place

[9, 8, 2, 3, 7, 4, 0]
//=> 
[0, 2, 3, 4, 8, 9, 9]
//which makes the actual array
//=> 
[10, 2, 33, 44, 88, 99, 79]
//then we sort that array by the 10's place
//=> 
[0, 1, 3, 4, 7, 8, 9]
//which makes the actual array
//=> 
[02, 10, 33, 44, 79, 88, 99]

This works for however many digits there are in total in the longest number for any radix be it base 2, 10 or 16.

Simple Counting Sort

PhilipSterling — Thu, 25 Jul 2019 17:35:59 +0000

Sorting data takes time.

So, why does counting sort have a different time complexity than the merge, bubble, heap and other sorts, why is there a variable k in the time complexity?

countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {

   // 1.
   let i; 
   let indexOfReturn = 0;
   let count = [];

   // 2.
   for (i = 0; i <= 9; i++) {
      count[i] = 0;
   }

   // 3.
   for (i = 0; i < arrayToSort.length; i++) {
      count[arr[i]]++;
   }

   // 4.
   for (i = 0; i <= 9; i++) {
      while (count[i]-- > 0) {
         arrayToSort[indexOfReturn++] = i;
      }
   }
   return arrayToSort;
}


//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]

This is complicated so let's break it down into 4 components:

Variables needed

//We are using a base 10 counting sort so the minimum 
//digit is 0 and the maximum digit is 9

//declaring i for index as a let to use in our for loops
let i; 

//declaring the starting index of the returnArray,
//which will just be a modification of the ArrayToSort
let indexOfReturn = 0;

//count is an array which will be marked in the time complexity
//as k so when you see O(n+k) k is the length(and therefore operations) 
//of count and n is the length(and therefore operations) 
//of the array to be sorted
let count = [];

First counting length for() loop

for (i = 0; i <= 9; i++) {
   count[i] = 0;
}

//this for loop sets up the count array to be used to
//keep track of the count of all numbers in the array to be sorted
// => count = [0,0,0,0,0,0,0,0,0,0]
//when created the count array has indexes equal to the base of the
//numbers that you are sorting, and because we are sorting in base 10
//it has 10 indexes that all point to the value zero

First array length for() loop

for (i = 0; i < arrayToSort.length; i++) {
   count[arr[i]]++;
}

//this for loop goes for the length of the array that will be
//sorted and increases the value in the indexes of count that are 
//equal to the value in the array that needs to be sorted
// => count = [1,2,1,3,1,1,1,1,1,1]
//the indexes of count now reference the amount of each digit that
//are in the array

Second counting length for() loop

for (i = 0; i <= 9; i++) {
   while (count[i]-- > 0) {
      arrayToSort[indexOfReturn++] = i;
   }
}
//this for loop goes for the length of the count and changes the indexes
//of the array to be sorted to be equal to the index of the count array
//while the count is still greater than 0
//You can see that the indexes are not compared against each other but 
//are instead just kept track of through count and returned in index 
//order from smallest to largest from 0 -> 9
// => arrayToSort = [0,1,1,2,3,3,3,4,5,6,7,8,9]

Pulling it all together again

countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {
   let i; 
   let indexOfReturn = 0;
   let count = [];
   for (i = 0; i <= 9; i++) {
      count[i] = 0;
   }
   for (i = 0; i < arrayToSort.length; i++) {
      count[arr[i]]++;
   }
   for (i = 0; i <= 9; i++) {
      while (count[i]-- > 0) {
         arrayToSort[indexOfReturn++] = i;
      }
   }
   return arrayToSort;
}

//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]


// after all the counting and indexing into count is done
//the return is the sorted array

Counting sort doesn't seem too useful but radix sort is built off of counting sorts and both Counting sort and Radix sort have time complexities based off of


// n => Length of the array
// k => Base of the number system you are sorting
// Leading to O ( n + k ) being the runtime

Counting sort has low time complexity because it has limited use, it can only be used on numbers of one character length. It is not a comparison sort so you don't need to know the values of the indexes next to what you are sorting.

References -

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html - Very useful animation about radix sort

https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-11.php - Information about how to format a counting sort in javascript

Understanding the basics of seeding Random using ruby

PhilipSterling — Tue, 02 Jul 2019 16:42:46 +0000

When you create a Random object in ruby without an argument the system-generated seed will be applied to that instance. If you pass in an argument of an integer, that integer will be used as the seed value for that Random instance

random_w_system_seed = Random.new
random_w_user_seed = Random.new(2330)

Seeding affects the order in which a random generator will put out pseudorandom numbers. If two Random instances have the same seed they will put out the same random numbers in the same order when called.

#Here, you can see that the first numbers generated by both 
#instances are the same because they share the same seed
random_same_seed_1 = Random.new(12345)
random_same_seed_2 = Random.new(12345)
random_same_seed_1.rand == random_same_seed_2.rand
# => true

#the same applies for comparing the objects, if they will both generate 
#the same number next, when compared it will evaluate to true
random_same_seed_1 == random_same_seed_2
# => true

#Lets call this first Random instance again so that
#it is one step ahead of the second Random instance
random_same_seed_1.rand
# => 0.3163755545817859

#Now the same seed is not returning the same value because
#the first instance is generating the third number in the
#sequence while the second instance is still generating the 
#second number in the sequence
random_same_seed_1.rand == random_same_seed_2.rand
# => false

Whenever a new Random instance is created without passing in a seed a seed will be passed to it by the system. You can check what this seed is with the #seed method. Additionally, you can set the system seed to a specific number so all Random instances generated without an argument share the same seed. You can do this by calling .srand to set the systems seed for random.

#Here, you can get return seeds from Random instances so you can 
#create Random instances with the same seed
random_instance_sys_seed = Random.new
random_instance_sys_seed.seed
# => 124999659906724141071882940163137705973

random_instance_user_seed = Random.new(12345)
random_instance_sys_seed.seed
# => 12345

#Here, you can see that using .srand to set the system seed for rand
#called without a user made instance and the user made Random instance
#have the same return value
random_instance_user_seed.rand
# => 0.9296160928171479

Random.srand(12345)
Random.rand
# => 0.9296160928171479

A class method for Random called .new_seed is what is used to make system seed values if there is no argument given when creating a new Random instance, it can also be called to return arbitrary seeds that are system created.

Random.new_seed
# => 32130858170704068723128768018578826042

So whats the point? If you want a random number why do you want to seed? The main reason is so even with pseudorandom returns you can have repeatable outcome from a program. This can be used for testing, debugging, teaching, sharing statistical analyses, or writing academic papers.