Distributed Evolutionary Algorithms in Python
DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. It seeks to make algorithms explicit and data structures transparent. It works in perfect harmony with parallelization mechanism such as multiprocessing and SCOOP.
DEAP includes the following features:
- Genetic algorithm using any imaginable representation
- List, Array, Set, Dictionary, Tree, Numpy Array, etc.
- Genetic programing using prefix trees
- Loosely typed, Strongly typed
- Automatically defined functions
- Evolution strategies (including CMA-ES)
- Multi-objective optimisation (NSGA-II, SPEA2, MO-CMA-ES)
- Co-evolution (cooperative and competitive) of multiple populations
- Parallelization of the evaluations (and more)
- Hall of Fame of the best individuals that lived in the population
- Checkpoints that take snapshots of a system regularly
- Benchmarks module containing most common test functions
- Genealogy of an evolution (that is compatible with NetworkX)
- Examples of alternative algorithms : Particle Swarm Optimization, Differential Evolution, Estimation of Distribution Algorithm
See the DEAP User’s Guide for DEAP documentation.
Installation
We encourage you to use easy_install or pip to install DEAP on your system. Other installation procedure like apt-get, yum, etc. usually provide an outdated version.
pip install deap
The latest version can be installed with
pip install git+https://github.com/DEAP/deap@master
If you wish to build from sources, download or clone the repository and type
python setup.py install
#Tree #Traversals
Below is the Python code for traversing trees in various recursive modes like In order, Preorder, Post Order and their reverse orders…
The code is provided in python, but can be easily translated to Java/JS/PHP etc
#HackerRank: Computing the Correlation
Problem
You are given the scores of N students in three different subjects – Mathematics, Physics and Chemistry; all of which have been graded on a scale of 0 to 100. Your task is to compute the Pearson product-moment correlation coefficient between the scores of different pairs of subjects (Mathematics and Physics, Physics and Chemistry, Mathematics and Chemistry) based on this data. This data is based on the records of the CBSE K-12 Examination – a national school leaving examination in India, for the year 2013.
Pearson product-moment correlation coefficient
This is a measure of linear correlation described well on this Wikipedia page. The formula, in brief, is given by:
where x and y denote the two vectors between which the correlation is to be measured.
Input Format
The first row contains an integer N.
This is followed by N rows containing three tab-space (‘\t’) separated integers, M P C corresponding to a candidate’s scores in Mathematics, Physics and Chemistry respectively.
Each row corresponds to the scores attained by a unique candidate in these three subjects.
Input Constraints
1 <= N <= 5 x 105
0 <= M, P, C <= 100
Output Format
The output should contain three lines, with correlation coefficients computed
and rounded off correct to exactly 2 decimal places.
The first line should contain the correlation coefficient between Mathematics and Physics scores.
The second line should contain the correlation coefficient between Physics and Chemistry scores.
The third line should contain the correlation coefficient between Chemistry and Mathematics scores.
So, your output should look like this (these values are only for explanatory purposes):
0.12
0.13
0.95
Test Cases
There is one sample test case with scores obtained in Mathematics, Physics and Chemistry by 20 students. The hidden test case contains the scores obtained by all the candidates who appeared for the examination and took all three tests (Mathematics, Physics and Chemistry).
Think: How can you efficiently compute the correlation coefficients within the given time constraints, while handling the scores of nearly 400k students?
Sample Input
20
73 72 76
48 67 76
95 92 95
95 95 96
33 59 79
47 58 74
98 95 97
91 94 97
95 84 90
93 83 90
70 70 78
85 79 91
33 67 76
47 73 90
95 87 95
84 86 95
43 63 75
95 92 100
54 80 87
72 76 90
Sample Output
0.89
0.92
0.81
There is no special library support available for this challenge.
Solution(Source)
#HackerRank: Correlation and Regression Lines solutions
import numpy as np
import scipy as sp
from scipy.stats import norm
Correlation and Regression Lines – A Quick Recap #1
Here are the test scores of 10 students in physics and history:
Physics Scores 15 12 8 8 7 7 7 6 5 3
History Scores 10 25 17 11 13 17 20 13 9 15
Compute Karl Pearson’s coefficient of correlation between these scores. Compute the answer correct to three decimal places.
Output Format
In the text box, enter the floating point/decimal value required. Do not leave any leading or trailing spaces. Your answer may look like: 0.255
This is NOT the actual answer – just the format in which you should provide your answer.
physicsScores=[15, 12, 8, 8, 7, 7, 7, 6, 5, 3]
historyScores=[10, 25, 17, 11, 13, 17, 20, 13, 9, 15]
print(np.corrcoef(historyScores,physicsScores)[0][1])
0.144998154581
Correlation and Regression Lines – A Quick Recap #2
Here are the test scores of 10 students in physics and history:
Physics Scores 15 12 8 8 7 7 7 6 5 3
History Scores 10 25 17 11 13 17 20 13 9 15
Compute the slope of the line of regression obtained while treating Physics as the independent variable. Compute the answer correct to three decimal places.
Output Format
In the text box, enter the floating point/decimal value required. Do not leave any leading or trailing spaces. Your answer may look like: 0.255
This is NOT the actual answer – just the format in which you should provide your answer.
sp.stats.linregress(physicsScores,historyScores).slope
0.20833333333333331
Correlation and Regression Lines – A quick recap #3
Here are the test scores of 10 students in physics and history:
Physics Scores 15 12 8 8 7 7 7 6 5 3
History Scores 10 25 17 11 13 17 20 13 9 15
When a student scores 10 in Physics, what is his probable score in History? Compute the answer correct to one decimal place.
Output Format
In the text box, enter the floating point/decimal value required. Do not leave any leading or trailing spaces. Your answer may look like: 0.255
This is NOT the actual answer – just the format in which you should provide your answer.
def predict(pi,x,y):
slope, intercept, rvalue, pvalue, stderr=sp.stats.linregress(x,y);
return slope*pi+ intercept
predict(10,physicsScores,historyScores)
15.458333333333332
Correlation and Regression Lines – A Quick Recap #4
The two regression lines of a bivariate distribution are:
4x – 5y + 33 = 0
(line of y on x)
20x – 9y – 107 = 0
(line of x on y).
Estimate the value of x
when y = 7
. Compute the correct answer to one decimal place.
Output Format
In the text box, enter the floating point/decimal value required. Do not lead any leading or trailing spaces. Your answer may look like: 7.2
This is NOT the actual answer – just the format in which you should provide your answer.
x=[i for i in range(0,20)]
'''
4x - 5y + 33 = 0
x = ( 5y - 33 ) / 4
y = ( 4x + 33 ) / 5
20x - 9y - 107 = 0
x = (9y + 107)/20
y = (20x - 107)/9
'''
t=7
print( ( 9 * t + 107 ) / 20 )
8.5
Correlation and Regression Lines – A Quick Recap #5
The two regression lines of a bivariate distribution are:
4x – 5y + 33 = 0
(line of y on x)
20x – 9y – 107 = 0
(line of x on y).
find the variance of y when σx= 3.
Compute the correct answer to one decimal place.
Output Format
In the text box, enter the floating point/decimal value required. Do not lead any leading or trailing spaces. Your answer may look like: 7.2
This is NOT the actual answer – just the format in which you should provide your answer.
http://www.mpkeshari.com/2011/01/19/lines-of-regression/
Q.3. If the two regression lines of a bivariate distribution are 4x – 5y + 33 = 0 and 20x – 9y – 107 = 0,
- calculate the arithmetic means of x and y respectively.
- estimate the value of x when y = 7. – find the variance of y when σx = 3.
Solution : –
We have,
4x – 5y + 33 = 0 => y = 4x/5 + 33/5 ————— (i)
And
20x – 9y – 107 = 0 => x = 9y/20 + 107/20 ————- (ii)
(i) Solving (i) and (ii) we get, mean of x = 13 and mean of y = 17.[Ans.]
(ii) Second line is line of x on y
x = (9/20) × 7 + (107/20) = 170/20 = 8.5 [Ans.]
(iii) byx = r(σy/σx) => 4/5 = 0.6 × σy/3 [r = √(byx.bxy) = √{(4/5)(9/20)]= 0.6 => σy = (4/5)(3/0.6) = 4 [Ans.]
variance= σ**2=> 16
#HackerEarth: #BattleOfBots 9: Taunt
Taunt is a two player board game which is played on a 10X4 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Orange ( First Player ) or Green ( Second Player ) being conventional. Each player has nine piece in total. The players move their pieces towards to his / her opponent’s area by moving their pieces strategically. Each piece has a different moving feature and is one of the 3 types of pieces.
Piece 1: It can move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.
Piece 2: It can move to horizontally adjacent cell or can move two steps forward, if the cell doesn’t contain a piece of same color (except the piece itself).
This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.
Piece 3: It can move two step diagonally in the forward direction, if the cell doesn’t contain a piece of same color (except the piece itself).
This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.
Players take turns involving moves of pieces as mentioned above and can captures opponent’s piece by jumping on or over opponent’s pieces.
Note: Forward direction for first player is downward and for second player is upward.
If a piece (except piece 1) is moving downward and touches the last row, its direction will change i.e. now it will move upward. Similarly, once if a piece (except piece 1) is moving upward and touches the first row, its direction will change i.e. now it will move downward.
Rules:
- Player can only move according to the moves mentioned above.
- A player may not move an opponent’s piece.
- A player can captures opponent’s piece by jumping on or over opponent pieces.
The game will end after 100 moves ( 50 moves for each player ) or when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.
We will play it on an 10X4 grid. The top left of the grid is [0,0] and the bottom right is [9,3].
Input:
The input will be a 10X4 matrix consisting only of 0,1or2. Next line will contain an integer denoting the total number of moves till the current state of the board. Next line contains an integer – 1 or 2 which is your player id.
In the given matrix, top-left is [0,0] and bottom-right is [9,3]. The y-coordinate increases from left to right, and x-coordinate increases from top to bottom.
A cell is represented by 3 integers.
First integer denotes the player id (1 or 2).
Second integer denotes the type of piece (1, 2 or 3).
Third integer denotes the direction of the piece (0 (upward) or 1 (downward)). When the piece is of first type, direction doesn’t matter as the piece is free to move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.
Empty cell is represented by 000.
Output:
In the first line print the coordinates of the cell separated by space, the piece you want to move.
In second line print the coordinates of the cell in which the piece will jump.
You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if the piece is able to jump to [1,1], but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.
Starting state
The starting state of the game is the state of the board before the game starts.
131 131 131 121 121 121 111 111 111 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 210 210 210 220 220 220 230 230 230
First Input
This is the input give to the first player at the start of the game.
131 131 131 121 121 121 111 111 111 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 210 210 210 220 220 220 230 230 230 0 1
000 000 000 000 000 000 000 111 000 000 111 130 000 000 000 000 000 000 000 000 000 220 000 000 131 000 000 000 121 000 210 000 000 210 131 000 000 210 000 000 58 1
8 2 8 0
Explanation
This is player 1’s turn, and the player will move the piece at [8,2] and will take two steps diagonally in downward direction and will be at [8,0]
After his/her move the state of game becomes:
000 000 000 000 000 000 000 111 000 000 111 130 000 000 000 000 000 000 000 000 000 220 000 000 131 000 000 000 121 000 210 000 130 210 000 000 000 000 000 000 59 2
Note: Direction of the piece is also changed from 1 to 0 as the piece was moving downward and touches the last row. This state will be fed as input to program of player 2.
Here is the code of the default bot.
Java Code to Zip all folders in a particular folder.
A small utility code to create multiple zip files for all folders in the a particular folder.
for example
- c:/path/to/folder -> folder 1 -> folder 2 -> folder 3 -> folder 4
Output:
- c:/path/to/folder -> folder 1 -> folder 2 -> folder 3 -> folder 4 -> folder 1.zip -> folder 2.zip -> folder 3.zip -> folder 4.zip
original source: https://goo.gl/sp0bqr
LDAP Connector
Below is a sample code to perform LDAP Queries. Just modify the configuration information and then provide any valid query to get the search results.
You can also modify the code to get custom business logic as required.
Sort a list of tuples by Nth item in Python
Suppose you have a list of tuples that looks something like this:
[('abc', 121),('abc', 231),('abc', 148), ('abc',221)]
And you want to sort this list in ascending order by the integer value inside the tuples.
We can achieve this using the key
keyword with sorted()
.
sorted([('abc', 121),('abc', 231),('abc', 148), ('abc',221)], key=lambda x: x[1])
key
should be a function that identifies how to retrieve the comparable element from your data structure. For example, the second element of the tuple, so we access [1]
.
HackerRank: Repeated String
Problem
Lilah has a string, s
, of lowercase English letters that she repeated infinitely many times.
Given an integer, n
, find and print the number of letter a
‘s in the first letters of Lilah’s infinite string.
Input Format
The first line contains a single string, s
.
The second line contains an integer, n
.
Constraints
1<=|s|<=100
1<=|n|<=10^12
- For
25%
of the test cases,n <= 10^6
Output Format
Print a single integer denoting the number of letter a’s in the first letters of the infinite string created by repeating infinitely many times.
Sample Input 0
aba
10
Sample Output 0
7
Explanation 0
The first n = 10
letters of the infinite string are abaabaabaa
. Because there are 7 a
‘s, we print on a new line.
Sample Input 1
a
1000000000000
Sample Output 1
1000000000000
Explanation 1
Because all of the first n=1000000000000
letters of the infinite string are a, we print 1000000000000 on a new line.