Skip to content

Commit 63032b8

Browse files
thuva4thuva4
authored
Merge branch 'master' into master
2 parents bd8b4b5 + 3a24057 commit 63032b8

49 files changed

Lines changed: 2561 additions & 158 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

A*Search/c++/a.out renamed to AStarSearch/c++/a.out

File renamed without changes.

A*Search/c++/a_star.cpp renamed to AStarSearch/c++/a_star.cpp

File renamed without changes.

A*Search/python/astar.py renamed to AStarSearch/python/astar.py

File renamed without changes.

A*Search/python/astar.pyc renamed to AStarSearch/python/astar.pyc

File renamed without changes.

A*Search/python/astar_demo.py renamed to AStarSearch/python/astar_demo.py

File renamed without changes.

‎BellmanFord/Python/BellmanFord.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
#!/usr/bin/env python3

Bitap Algorithm/Bitap.cpp renamed to Bitap Algorithm/C++/Bitap.cpp

File renamed without changes.

‎Bitap Algorithm/Python/BiTap.py‎

Lines changed: 153 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,153 @@
1+
# -*- coding: utf-8 -*-
2+
import sys
3+
4+
"""Auxiliary procedure for printing each item of row in columns in binary form
5+
"""
6+
def _printTable(t, size):
7+
out = ""
8+
for i in range(len(t)):
9+
binaryForm = bin(t[i])
10+
binaryForm = binaryForm[2 : ]
11+
binaryForm = binaryForm.zfill(size)
12+
out += binaryForm + ", "
13+
out = out[ : -2]
14+
print out
15+
16+
"""Bitap (Shift-Or) fuzzy searching algorithm with Wu-Manber modifications.
17+
http://habrahabr.ru/post/114997/
18+
http://habrahabr.ru/post/132128/
19+
http://ru.wikipedia.org/wiki/Двоичный_алгоритм_поиска_подстроки
20+
Search needle(pattern) in haystack(real word from text) with maximum alterations = maxErrors.
21+
If maxErrors equal 0 - execute precise searching only.
22+
Return approximately place of needle in haystack and number of alterations.
23+
If needle can't find with maxErrors alterations, return tuple of empty string and -1.
24+
"""
25+
def bitapSearch(haystack, needle, maxErrors):
26+
haystackLen = len(haystack)
27+
needleLen = len(needle)
28+
29+
"""Genarating mask for each letter in haystack.
30+
This mask shows presence letter in needle.
31+
"""
32+
def _generateAlphabet(needle, haystack):
33+
alphabet = {}
34+
for letter in haystack:
35+
if letter not in alphabet:
36+
letterPositionInNeedle = 0
37+
for symbol in needle:
38+
letterPositionInNeedle = letterPositionInNeedle << 1
39+
letterPositionInNeedle |= int(letter != symbol)
40+
alphabet[letter] = letterPositionInNeedle
41+
return alphabet
42+
43+
alphabet = _generateAlphabet(needle, haystack)
44+
45+
table = [] # first index - over k (errors count, numeration starts from 1), second - over columns (letters of haystack)
46+
emptyColumn = (2 << (needleLen - 1)) - 1
47+
48+
# Generate underground level of table
49+
underground = []
50+
[underground.append(emptyColumn) for i in range(haystackLen + 1)]
51+
table.append(underground)
52+
_printTable(table[0], needleLen)
53+
54+
# Execute precise matching
55+
k = 1
56+
table.append([emptyColumn])
57+
for columnNum in range(1, haystackLen + 1):
58+
prevColumn = (table[k][columnNum - 1]) >> 1
59+
letterPattern = alphabet[haystack[columnNum - 1]]
60+
curColumn = prevColumn | letterPattern
61+
table[k].append(curColumn)
62+
if (curColumn & 0x1) == 0:
63+
place = haystack[columnNum - needleLen : columnNum]
64+
return (place, k - 1)
65+
_printTable(table[k], needleLen)
66+
67+
# Execute fuzzy searching with calculation Levenshtein distance
68+
for k in range(2, maxErrors + 2):
69+
print "Errors =", k - 1
70+
table.append([emptyColumn])
71+
72+
for columnNum in range(1, haystackLen + 1):
73+
prevColumn = (table[k][columnNum - 1]) >> 1
74+
letterPattern = alphabet[haystack[columnNum - 1]]
75+
curColumn = prevColumn | letterPattern
76+
77+
insertColumn = curColumn & (table[k - 1][columnNum - 1])
78+
deleteColumn = curColumn & (table[k - 1][columnNum] >> 1)
79+
replaceColumn = curColumn & (table[k - 1][columnNum - 1] >> 1)
80+
resColumn = insertColumn & deleteColumn & replaceColumn
81+
82+
table[k].append(resColumn)
83+
if (resColumn & 0x1) == 0:
84+
startPos = max(0, columnNum - needleLen - 1) # taking in account Replace operation
85+
endPos = min(columnNum + 1, haystackLen) # taking in account Replace operation
86+
place = haystack[startPos : endPos]
87+
return (place, k - 1)
88+
89+
_printTable(table[k], needleLen)
90+
return ("", -1)
91+
92+
"""Highlight letters in fullWord, which concur with letters in pattern with same order.
93+
wordPart - it's a part of fullWord, where matching with pattern letters will execute.
94+
"""
95+
class bitapHighlighter():
96+
def __init__(self, fullWord, wordPart, pattern):
97+
self._fullWord = fullWord
98+
self._wordPart = wordPart
99+
self._pattern = pattern
100+
self._largestSequence = ""
101+
102+
"""Finding longest sequence of letters in word. Letters must have same order, as in pattern
103+
"""
104+
def _nextSequence(self, fromPatternPos, fromWordPos, prevSequence):
105+
for patternPos in range(fromPatternPos, len(self._pattern)):
106+
char = self._pattern[patternPos]
107+
for wordPos in range(fromWordPos, len(self._wordPart)):
108+
if char == self._wordPart[wordPos]:
109+
sequence = prevSequence + char
110+
self._nextSequence(patternPos + 1, wordPos + 1, sequence)
111+
if len(self._largestSequence) < len(prevSequence):
112+
self._largestSequence = prevSequence
113+
114+
"""Divide fullWord on parts: head, place(wordPart) and tail.
115+
Select each letter of wordPart, which present in _largestSequence with <b></b> tags
116+
Return gathered parts in one highlighted full word
117+
"""
118+
def _gatherFullWord(self):
119+
placePos = self._fullWord.find(self._wordPart)
120+
head = self._fullWord[0 : placePos]
121+
tail = self._fullWord[placePos + len(self._wordPart) : ]
122+
highlightedPlace = ""
123+
for symbol in self._wordPart:
124+
if symbol == self._largestSequence[0 : 1]:
125+
highlightedPlace += "<b>" + symbol + "</b>"
126+
self._largestSequence = self._largestSequence[1 : ]
127+
else:
128+
highlightedPlace += symbol
129+
return head + highlightedPlace + tail
130+
131+
"""Run highlighting and return highlited word.
132+
"""
133+
def getHighlightedWord(self):
134+
self._nextSequence(0, 0, "")
135+
return self._gatherFullWord()
136+
137+
haystack = sys.argv[1]
138+
needle = sys.argv[2]
139+
errorsCount = sys.argv[3]
140+
print "haystack = " + haystack + ". needle = " + needle + ". errorsCount = " + errorsCount
141+
142+
# Display letters of haystack in columns
143+
out = ""
144+
out = out.ljust(len(needle) + 2)
145+
for i in range(len(haystack)):
146+
out += haystack[i].ljust(len(needle)) + " "
147+
out = out[ : -2]
148+
print out
149+
150+
# Start bitap searching
151+
(needlePlace, errors) = bitapSearch(haystack, needle, int(errorsCount))
152+
print "Result of Bitap searching:", needlePlace, errors
153+
print bitapHighlighter(haystack, needlePlace, needle).getHighlightedWord()

‎Borwein's Algorithm/Java/borwein_algorithm.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
/**
2+
3+
** Java Program to Implement Borwein Algorithm
4+
5+
**/
6+
7+
import java.util.Scanner;
8+
9+
10+
11+
/** Class Borwein **/
12+
13+
public class Borwein
14+
15+
{
16+
17+
/** compute 1/pi **/
18+
19+
public double getOneByPi(int k)
20+
21+
{
22+
23+
double ak = 6.0 - 4 * Math.sqrt(2);
24+
25+
double yk = Math.sqrt(2) - 1.0;
26+
27+
28+
29+
double ak1 ;
30+
31+
double yk1 ;
32+
33+
for (int i = 0; i < k; i++)
34+
35+
{
36+
37+
yk1 = (1 - Math.pow((1 - yk * yk * yk * yk),(0.25)))/(1 + Math.pow((1 - yk * yk * yk * yk),(0.25)));
38+
39+
ak1 = ak * Math.pow((1 + yk1), 4) - Math.pow(2, 2 * i + 3) * yk1 * (1 + yk1 + yk1 * yk1);
40+
41+
yk = yk1;
42+
43+
ak = ak1;
44+
45+
}
46+
47+
return ak;
48+
49+
}
50+
51+
/** Main function **/
52+
53+
public static void main (String[] args)
54+
55+
{
56+
57+
Scanner scan = new Scanner(System.in);
58+
59+
System.out.println("Borwein 1/Pi Algorithm Test\n");
60+
61+
/** Make an object of Borwein class **/
62+
63+
Borwein b = new Borwein();
64+
65+
66+
67+
System.out.println("Enter number of iterations ");
68+
69+
int k = scan.nextInt();
70+
71+
72+
73+
System.out.println("\nValue of 1/pi : "+ b.getOneByPi(k));
74+
75+
}
76+
77+
}

‎BreadthFirstSearch/JavaScript/BFS.js‎

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
// Fully runnable code, along with test cases at https://codepen.io/sniper6/pen/KXrJqG/
2+
3+
const BFS = (graph, source, target = -1) => {
4+
// Some error handling
5+
if (typeof graph.getNeighbors !== "function") {
6+
throw "Graph should implement a getNeighbors function";
7+
}
8+
if (typeof source !== "number") {
9+
throw "source should be a number";
10+
}
11+
12+
const Q = [], // The queue that will be used
13+
order = [], // Array to hold the order of visit. Mainly for unit testing
14+
visited = {}; // Keep track of visited vertices
15+
16+
let found = false;
17+
Q.push(source);
18+
visited[source] = true;
19+
while (Q.length !== 0) {
20+
const currentVertex = Q.shift();
21+
order.push(currentVertex);
22+
const neighbors = graph.getNeighbors(currentVertex);
23+
for (const neighbor of neighbors) {
24+
if (!visited[neighbor]) {
25+
Q.push(neighbor);
26+
visited[neighbor] = true;
27+
if (neighbor === target) {
28+
found = true;
29+
}
30+
}
31+
}
32+
}
33+
return { order, found };
34+
};
35+
36+
const GraphFactory = (() => {
37+
const GraphTemplate = {
38+
init() {
39+
this._graph = [];
40+
},
41+
getNeighbors(vertex) {
42+
return this._graph[vertex] || [];
43+
},
44+
addEdge(source, target, biDirectional = true) {
45+
this._addEdge(source, target);
46+
if (biDirectional) {
47+
this._addEdge(target, source);
48+
}
49+
},
50+
_addEdge(source, target) {
51+
this._graph[source] = this._graph[source] || [];
52+
this._graph[source].push(target);
53+
},
54+
printGraph() {
55+
console.log(JSON.stringify(this._graph, null, 2));
56+
}
57+
};
58+
59+
return {
60+
getGraph() {
61+
const Graph = Object.assign({}, GraphTemplate);
62+
Graph.init();
63+
return Graph;
64+
}
65+
};
66+
})();
67+
68+
describe("BFS", () => {
69+
let graph = null;
70+
71+
beforeEach(() => {
72+
graph = GraphFactory.getGraph();
73+
});
74+
75+
it("should throw error on bad graph", () => {
76+
expect(() => {
77+
BFS({});
78+
}).toThrow("Graph should implement a getNeighbors function");
79+
});
80+
81+
it("should throw error on no source vertex", () => {
82+
expect(() => {
83+
BFS(graph);
84+
}).toThrow("source should be a number");
85+
});
86+
87+
it("simple bi-directional graph where target is reachable", () => {
88+
graph.addEdge(0, 1);
89+
graph.addEdge(0, 3);
90+
graph.addEdge(1, 2);
91+
expect(BFS(graph, 0, 3)).toEqual({
92+
order: [0, 1, 3, 2],
93+
found: true
94+
});
95+
});
96+
97+
it("complex bi-directional graph where target is reachable", () => {
98+
graph.addEdge(0, 1);
99+
graph.addEdge(0, 2);
100+
graph.addEdge(1, 3);
101+
graph.addEdge(3, 4);
102+
graph.addEdge(4, 2);
103+
expect(BFS(graph, 0, 3)).toEqual({
104+
order: [0, 1, 2, 3, 4],
105+
found: true
106+
});
107+
});
108+
109+
it("complex uni-directional graph where target is reachable", () => {
110+
graph.addEdge(0, 1, false);
111+
graph.addEdge(0, 2, false);
112+
graph.addEdge(1, 3, false);
113+
graph.addEdge(3, 4, false);
114+
graph.addEdge(3, 5, false);
115+
graph.addEdge(4, 2, false);
116+
expect(BFS(graph, 0, 3)).toEqual({
117+
order: [0, 1, 2, 3, 4, 5],
118+
found: true
119+
});
120+
});
121+
122+
it("simple bi-directional graph where target is not present", () => {
123+
graph.addEdge(0, 1);
124+
graph.addEdge(0, 3);
125+
graph.addEdge(1, 2);
126+
expect(BFS(graph, 0, 5)).toEqual({
127+
order: [0, 1, 3, 2],
128+
found: false
129+
});
130+
});
131+
});

0 commit comments

Comments
 (0)