Skip to content

Instantly share code, notes, and snippets.

View rajatdiptabiswas's full-sized avatar
:octocat:
Octocat says Git Gud

rajat rajatdiptabiswas

:octocat:
Octocat says Git Gud
View GitHub Profile
#!/usr/bin/env python3
class Node(object):
"""Class for tree nodes"""
def __init__(self, key):
super(Node, self).__init__()
self.key = key
self.left = None
@rajatdiptabiswas
rajatdiptabiswas / Backtracking : Sudoku Solver.py
Created April 8, 2018 20:26
Given a partially filled 9×9 2D array, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9 (https://www.geeksforgeeks.org/backtracking-set-7-suduku/)
#!/usr/bin/env python3
"""
Sudoku Solver
guesses:
1-9
grid:
@rajatdiptabiswas
rajatdiptabiswas / Backtracking : Rat in a Maze.py
Created April 8, 2018 20:23
Problem where a rat starts from source and has to reach the destination (https://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/)
#!/usr/bin/env python3
def is_safe(x, y, n, maze):
if 0 <= x <= n-1 and 0 <= y <= n - 1 and maze[y][x] == 1:
return True
else:
return False
@rajatdiptabiswas
rajatdiptabiswas / Backtracking : N Queens.py
Last active April 8, 2018 20:21
Problem of placing N chess queens on an N×N chessboard so that no two queens attack each other (https://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/)
#!/usr/bin/env python3
def is_safe(row, col, size, board):
# check vertical
for y in range(row):
if board[y][col]:
return False
# check left diagonal
@rajatdiptabiswas
rajatdiptabiswas / Memoization.py
Last active March 24, 2018 10:53
The memoization decorator in Python to solve Dynamic Programming problems
#!/usr/bin/env python3
def memoization(function):
memo = {}
def helper(x):
if x not in memo:
memo[x] = function(x)
return memo[x]
@rajatdiptabiswas
rajatdiptabiswas / Binary Indexed Tree.py
Last active June 22, 2023 05:20
Implementation of Binary Indexed Tree/Fenwick Tree in Python
#!/usr/bin/env python3
"""
Binary Indexed Tree / Fenwick Tree
https://www.hackerearth.com/practice/notes/binary-indexed-tree-made-easy-2/
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
https://www.youtube.com/watch?v=v_wj_mOAlig
https://www.youtube.com/watch?v=kPaJfAUwViY
"""
@rajatdiptabiswas
rajatdiptabiswas / 2D Point Class.py
Created March 1, 2018 12:39
A point class with x and y coordinates for 2D planes
import math
class Point(object):
'''Creates a point on a coordinate plane with values x and y'''
def __init__(self, x, y):
'''Defines the x and y coordinates in the variables'''
self.X = x
self.Y = y
@rajatdiptabiswas
rajatdiptabiswas / Tower of Hanoi.py
Last active February 14, 2018 08:59
Python program to solve the Tower of Hanoi problem recursively
#!/usr/bin/env python3
def tower_of_hanoi(number, beginning, auxiliary, ending):
if number == 1:
print("{} -> {}".format(beginning, ending))
return
else:
tower_of_hanoi(number-1, beginning, ending, auxiliary)
@rajatdiptabiswas
rajatdiptabiswas / Palindromic Permutations.py
Created February 5, 2018 17:23
Lists all the palindromes that can be formed from a given string
#!/usr/bin/env python3
from itertools import permutations
def main():
t = int(input())
for cases in range(t):
string = str(input())
@rajatdiptabiswas
rajatdiptabiswas / Snake Game.py
Last active February 2, 2023 19:15
A simple snake game written in Python using the PyGame library (https://github.com/rajatdiptabiswas/snake-pygame)
"""
Snake Eater
Made with PyGame
"""
import pygame, sys, time, random
# Difficulty settings
# Easy -> 10