Skip to content

Instantly share code, notes, and snippets.

View MrNocTV's full-sized avatar

loctv MrNocTV

View GitHub Profile
@MrNocTV
MrNocTV / tree.py
Last active June 29, 2017 14:15
Python General Tree and Binary Tree implementation
from LinkedQueue import LinkedQueue
class Tree:
class Position:
def element(self):
raise NotImplementedError('must be implemented by subclas')
def __eq__(self, other):
raise NotImplementedError('must be implemented by subclas')
from sys import stdin, stdout
T = int(stdin.readline())
for _ in range(T):
B, W = [int(x) for x in stdin.readline().split()]
X, Y, Z = [int(x) for x in stdin.readline().split()]
if X == Y == Z:
print(B*X + W*Y)
else:
if X > Y and Z+Y < X:
'''
First you find 8 end points of 8 directions (if they exist)
Then go through k obstacle points, update if they are smaller than the end point
Smaller means near the queen position
Then if they are mark as updated means they are obstacles and
should be - 1 in the total squares
'''
from sys import stdin, stdout
@MrNocTV
MrNocTV / PriorityQueue.py
Last active July 3, 2017 09:25
Priority Queue implemented by : Unsorted List, Sorted List (both using PositionalList), and Binary Tree (implemented using array)
'''
Priority Queue:
- Unsorted Double Linked List implementation
- Sorted Double Linked List implemenration
- Array-based Binary Tree implementation
- Positional List is a doubly linked list:
head <=> node1 <=> node2 <=> ... <=> noden <=> tail
'''
from DoublyLinkedList import PositionalList
@MrNocTV
MrNocTV / DoublyLinkedList.py
Created July 1, 2017 10:02
Double Linked List Python Implementation with Position technique
class Empty(Exception):
pass
class _DoublyLinkedBase:
'''
Abstract base class for double linked list
'''
class _Node:
__slots__ = '_element', '_next', '_prev'
@MrNocTV
MrNocTV / MinAbsDiffInArray.py
Created July 1, 2017 11:59
Minimum Absolute Difference in an Array
'''
1. sort
2. set min as first pair
3. compair consecutive pair with min
'''
from sys import stdin, stdout
n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
a.sort()
@MrNocTV
MrNocTV / SumVSXOR.py
Created July 1, 2017 16:44
Sum VS XOR
'''
given n, find the number of x, such that
0 <= x <= n
n + x = n xor x
1. We can iterate from 0 to n: O(n)
2. Analyze:
n + i = n^i + n&i
since n + i = n^i => n&i == 0
we count unset bit in n and calculatew 2 to the power of that value
@MrNocTV
MrNocTV / LinkedHeapPriorityQueue.py
Last active July 3, 2017 09:22
Priority Queue Heap implemented with Binary Tree
'''
Use positional list to maintain O(1) on 'add' operation
Use one more attribute _prev in _Node to get the next last element
But first we have to maintain the last element by _last_node
As we removing, _last_node is assigned to _prev of it
PositionalList is a doubly linked list with structure:
head <=> node1 <=> node2 <=> ... <=> noden <=> tail
'''
@MrNocTV
MrNocTV / TheGreateXOR.py
Created July 3, 2017 16:24
The Great XOR
'''
Given x, count how many a (0 < a < x) such that:
a xor x > x
- a < x means the first set bit (bit 1) in 'x' is '0' in a
example:
x = 110101
=> a = 0xxxxx
with each bit in a, if it is 0, then if we turn it to 1, there will be 2 to ther power of (number of bits that are left).
@MrNocTV
MrNocTV / BreadthFirstSearch.py
Created July 6, 2017 14:26
Breadth First Search and Shortest Part from one node to the others
def breadth_first_search(start, n, graph, DISTANCE=6):
from collections import deque
parent_table = dict()
distance= dict() # store distance from start to other nodes
visited = set()
waiting_list = deque() # support remove front O(1)
# set up distance
for v in range(1, n+1):
distance[v] = 0
waiting_list.append(start)