Vectors in C++

Vectors in C++ is an interesting data structure which is bit similar to arrays. Not having a fixed size is the main difference though. The vector class is in C++ std namespace.

Vectors are associated with some useful methods which are handy in controlling vectors. Refer to the guide for more info.

Method push_back( ) to be used to add elements to a vector. Accessing an element can be done through accessing the relevant index as in arrays. size( ) gives the number of elements in a vector.

Defining a Vector

Creating an instance of the vector class.


#include <iostream>
#include <vector>

using namespace std;

int main()
{
   vector<string> names;
   
   cout << "Size of the vector : " << names.size() << endl;
   return 0;
}

Assign Values to a Vector


#include <iostream>
#include <vector>

using namespace std;

int main()
{
   vector<string> names;
   names.push_back("Alex");
   names.push_back("Bob");
   
   cout << "Size of the vector :" << names.size() << endl;
   cout << "First Name :" << names[0] << endl;
   
   names[0] = "Alex the great";
   
   cout << "First Name :" << names[0] << endl;
   
   return 0;
}

Example

Here is an example on how vectors can be used to solve a problem.

Write a function that accepts an upper bound positive integer and then calculate all the prime numbers within the given integer (excluding). Prime number set should starts with 2 in the index = 0.


#include <iostream>
#include <vector>

using namespace std;

vector<int> get_primes(int num);
bool is_prime(int num);

int main()
{
   vector<int> output;
   output = get_primes(20);
   
   for(int j=0; j < output.size(); j++){
       cout << "Prime No at index - " << j << " = " << output[j] << endl;
   }
   
   return 0;
}

vector<int> get_primes(int limit){
    vector<int> primes;
    for(int i = 2; i < limit; i++){
        if(is_prime(i)){
            primes.push_back(i);
        }
    }
    return primes;
}

bool is_prime(int num){
    for(int i = 2; i<num; i++){
        int r = num % i;
        if(r ==0){
            return false;
        }
    }
    return true;
}

Output

Prime No at index - 0 = 2
Prime No at index - 1 = 3
Prime No at index - 2 = 5
Prime No at index - 3 = 7
Prime No at index - 4 = 11
Prime No at index - 5 = 13
Prime No at index - 6 = 17
Prime No at index - 7 = 19

The code is self-explanatory. Notice how vectors are used in methods. Assigning values and accessing the indexes.

Coding Challenge #1 – Sum of multiples

Here is a little coding challenge to try.

The objective is to find the sum of multiples within a given range.

For example assume that given multiples are 4, 5 and 7. The upper limit is 20 (excluding). Multiples of 4 within 20 are 4, 8, 12 and 16. Then multiples of 5 within 20 are 5, 10 and 15. The multiples of 7 within 20 are 7 and 14. The objective is to find the sum of all those numbers.

The upper limit and the number of multiples can be vary from problem to problem.

Solution in Cpp

#include <iostream>

using namespace std;

int isMult(int mult[], int n, int length);

int main () {
    int no_of_mult = 2;
    int multiSet[no_of_mult] = {3, 5};
    int upper_limit = 10;
    
    int sum = 0;
    for (int i=0; i &lt; upper_limit; i++){
        sum = sum + isMult(multiSet, i, no_of_mult);
    }
    cout &lt;&lt; "Sum = " &lt;&lt; sum;
}

int isMult(int mult[], int n, int length){
    for(int i =0; i &lt; length; i++){
        int r = n % mult[i];
        if(r == 0){
            return n;
        }
    }
    return 0;
}

Try it online http://tpcg.io/ujmQDD

Finding nth prime number – JavaScript

Recently one of my friends mentioned a coding problem where the 1001th prime needs to be found out. Out of many ways to achieve the answer, I used the elimination method which probably you would have used in the elementary school. Formally, this method is known as Sieve of Eratosthenes. When the position of the prime needs to be found out this approach is pretty simple and straightforward.

Following is how the problem is solved:

The 1001th prime is 7927
The source code can be used to find out any nth prime.

However the time efficiency of this algorithm is in order of n! which means for higher upper limit, this method is extremely slower.

Check the code which is self explanatory.


class prime{
	constructor(){
	}
	
	getPrimes(limit){
		let arr = this.createList(limit);
		let primes = this.savePrimes(arr);
		return primes;
	}
	
	createList(max){
		let numberList = [];
		for (let i=2; i<=max; i++) {
			numberList.push(i);
		}
		return numberList;
	}

	savePrimes(numArr){
		let i, j;
		for (i=0; i < numArr.length; i++){
			let x = numArr[i];
			for (j=i+1; j < numArr.length; j++ ){
				let y = numArr[j];
				let r = y%x;
				if(r==0){
					numArr[j] = null;
				}
			}
			numArr = this.removeZeros(numArr);
		}
		return numArr;
	}

	removeZeros(numArr){
		let newArr = [];
		for (let x in numArr){
			let e = numArr[x];
			if(e!=null){
				newArr.push(e);
			}
		}
		return newArr;
	}
}

let obj = new prime();
let primeNumbers = obj.getPrimes(10000);
console.log(primeNumbers[1000]);

New Approach to Solve Dynamic Job Shop Scheduling Problem Using Genetic Algorithm

This paper has been presented in 3rd International Conference on Information Technology Research held in Colombo on 2018 December 06th.

New Approach to Solve Dynamic Job Shop Scheduling Problem Using Genetic Algorithm

Authors : Chandradeepa Kurera, Palitha Dasanayake

Session Chair : Prof. Chan-Yun Yang

Abstract— Job Shop Scheduling Problem (JSSP) is one of the most common problems in manufacturing due to its widespread application and the usability across the manufacturing industry. Due to the vast solution space the JSSP problem deals with, it is impossible to apply brute force search techniques to obtain an optimal solution. In this research, Genetic Algorithm (GA) approach, which is another widely used nonlinear optimization technique, has been used to propose a solution using a novel chromosome representation which makes seeking solutions for the Dynamic JSSP more efficient. Due to operation order criteria of the jobs and the machine allocation requirement on machines, generating solutions for JSSP needs an extra effort to eliminate infeasible solutions. Due to level of the complexity with added constraints, there is a high tendency to get more infeasible solutions than feasible solutions. This results in consuming a lot of computing resources to correct such a conventional order-based chromosome representation. Due to this, a new representation is proposed in this paper. It is found that the proposed new chromosome representation approach makes it possible to model such dynamic behaviours of schedules without compromising the performances of GA.

Keywords— Genetic Algorithm, Job Shop Scheduling Problem, Dynamic Job Shop Scheduling Problem

Corresponding Author – bckurera AT gmail DOT com

Conference Web Site – http://www.icitr.mrt.ac.lk/

Working with Dictionaries – JSON in Python

In Python, Dictionary is a data structure in which data is indexed by the key value. Therefore in order to access it’s data members the key value is required. When converting data to JSON it is ideal to use dictionary as JSON format support the key-index and value pairing format. In this post, it is mentioned how to achieve dictionary to JSON and JSON to dictionary conversion.

Dictionary

A structure of a simple dictionary is as follow:


sample_dictionary = {'key-1' : 'value-1', 'key-2' : 'value-2' }

There is a function named dict( ) which can be used to create a dictionary.

JSON library

In Python, JSON library is readily available. Main two methods we are using are dumps and loads.

.dumps()

Converts a data structure in this case a dictionary to a JSON string.

.loads()

This method can be used to convert a JSON string to a dictionary data structure so that it can be accessed within the code using key-values of the indexes.

Study the following example, a dictionary is defined with few levels, termed as nested dictionary. Data of a Tennis match is arranged.

import json

match = {
	'match-name' : 'USA F35 Futures',
	'match-general-info' : 
		{'match-date' : '2018.12.04', 'match-time' : '22:30', 'match-place' : 'Tallahassee'},
	'player-A' : 
		{'name' : 'Random Name A', 'age' : 20, 
			'rankings' : {'local' : 4, 'ITF' : 17, 'results' : 
				{'winner': 35, 'runner-up': 20, 'break-down' :
					{'semi' : 10, 'quarter' : 4, 'R16' : 1}
				}
			}		 
		}
}


json_string = json.dumps(match,0)

print ('Data Set in JSON format \n' + json_string)

match_dict = json.loads(json_string)

no_of_semis = match_dict['player-A']['rankings']['results']['break-down']['semi']

print ('Number of semi-final matches the player played : ' + str(no_of_semis) + ' matches')

Note that how the values of the data structure are accessed using nested indexes. This method can be used to manage multi-level data hierarchy but it might be bit difficult to manage as the size of the data structure increases. Another disadvantage is to access the values, it is required to supply the key of the index.

Download files from a URL – Python script

Downloading files from a web server over the internet is a trivial task which is performed in our everyday life. Isnt it?

For example when accessing a web site, your browser downloads some files to your computer. Commonly, it could obviously be .html files and then it might include .css .js files as well. You dont notice it as it is handled and managed by the browser itself. However there can be instances that you need to access a specific URL and download some files. No doubt it can be done manually. What if there are hundreds of files to be downloaded. In this article it is discussed how to get it done with minimal effort using a Python script.

Disclaimer – Employing a script to access/ download content from a web server can cause a higher traffic towards the web server. Therefore do not use this knowledge to access any resource in a web server without getting prior permissions. Use this script at your own risk. The author bears no responsibility.

For the purpose we are going to use the library urllib which is an inbuilt library in Python. .urlopen and .read methods can be used to access the content of the resource and then .write method can be used to save the content to the local machine. Check how the code is organized.

Python Version 2.7.15

import urllib
url = 'http://url-for-resources'

webf = urllib.urlopen(url)
txt = webf.read()
f = open('local-machine-folder-path', 'w+')
f.write(txt)
f.close()

It is pretty straight forward. Then the next objective is to automate the process. Using a loop is the easiest. One issue to overcome though. How to get the file names. If the file names follow a regular sequence for example data_01.json, data_02.json, data_03.json etc, it is possible to generate the sequence. Otherwise file names should be inserted to the code. A solution could be to extract the file names to a file and then read the file and get filenames. 

Here is the Python script for the above approach.


import urllib

f = open("local-file-with-file-names", "r")
file_list = f.readlines()


for x in file_list:

	filename = x.strip()
	url = 'http://url-for-resources/'+ filename

	webf = urllib.urlopen(url)
	txt = webf.read()
	f = open('local-file-path-to-save/'+filename, 'w+')
	f.write(txt)
	f.close()
	
	print('Saving file ' + filename)

One line contains one file name in the file which is used to include files to be downloaded.