All Questions
Tagged with python-2.x algorithm
162 questions
5
votes
4
answers
937
views
Decrease Computation Time for Python Tic-Tac-Toe Minimax Algorithm
Background
I am currently participating in a tic-tac-toe coding challenge. During their move, each participant is given the board state and their team, X or O. The blank board is:
...
- 153
2
votes
1
answer
179
views
LeetCode 839: Similar String Groups III
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you!
Problem
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that ...
- 3,542
2
votes
2
answers
168
views
Python - Hexadecimal to Decimal conversions
I have written a python 2 program for a school project to convert from hexadecimal to decimal without using built-in functions and vice versa in python. I would like to know how I can make my code ...
- 564
1
vote
3
answers
52
views
`set_includes` (string subsequence-containment) in Python 2
I've implemented C++'s std::includes algorithm in Python, so that I can use it to efficiently implement a Scrabble "can I make this word" function:
...
- 19.4k
2
votes
2
answers
2k
views
Heap Sort Implementation in Python
Objective: Create a heap sort that returns a unsorted list to sorted from greatest to least.
Does this implementation look correct? Do you have any tips for optimizing this?
...
- 131
7
votes
3
answers
179
views
Python methods to reduce running times KTNS algorithm
I have been trying to develop an algorithm called keep the tool needed soonest (for more information about the KTNS explanation (page 3)) but during the simulations, I have realized that it takes too ...
- 185
4
votes
1
answer
179
views
2D discrete motion planner
I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
- 43
4
votes
2
answers
1k
views
Finding palindromic strings of even length
Given a string of digits. Find the length of longest substring of even length i.e. 0,2,... which is a palindrome or which can be rearranged to form a palindrome (see example below).
Here is my code: ...
- 605
1
vote
2
answers
5k
views
7
votes
4
answers
1k
views
Solving jumbled letters using a given dictionary
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters.
Example:
...
- 605
1
vote
1
answer
995
views
The Substring Game! challenge
This is the Substring Game! challenge from HackerEarth:
Watson gives Sherlock a string (let's denote it by S). Watson calculates all the substrings of S in his favourite order.
According to ...
- 605
1
vote
1
answer
1k
views
Project RoboNest - Nestable/Breakable For Loops + Basic While Loops for Robot Framework
I'm implementing things in Robot Framework that it does not support by default, including nestable For Loops and, now, While Loops. I'm looking for readability, algorithm, methodology, and/or ...
- 258
1
vote
1
answer
294
views
Greedy Algorithm - Tuple Comparator
I've completed the problem set 9 of the OCW 6.00sc course which requires the implementation of a greedy algorithm - see prompt.
When completing problem 2, it is asked to implement comparator ...
- 131
5
votes
2
answers
1k
views
Prime Number Generator (6n + 1 or 6n - 1)
This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares ...
- 845
3
votes
2
answers
23k
views
Using BFS to solve 8-puzzle game using Python 2
I'm trying to solve the 8-puzzle game using BFS, DFS and A* algorithms implemented using Python 2.7. For now, I have managed to solve a couple of test cases using BFS and I want to know how I can ...
- 113
2
votes
0
answers
46
views
Algorithm for point distribution of traversal between 2 points on a line in time
Not sure if this is best SO forum to post at, please suggest/move to more appropriate place otherwise. A synopsis of the problem 1st:
Given a scenario where we have messages with data that define a ...
- 133
14
votes
4
answers
2k
views
Codechef: Prime Number Generator
Peter wants to generate some prime numbers for his cryptosystem. Help
him! Your task is to generate all prime numbers between two given
numbers!
Input
The input begins with the number t of test cases ...
- 241
3
votes
1
answer
1k
views
Bank account balance data structure design and code
I'm working on designing a bank account data structure and related operations (1. debit, 2. credit and 3. get balance difference).
Debit means withdraw some money from an account, at a certain ...
- 3,453
0
votes
1
answer
454
views
Dijkstra's shortest path with max intermediate nodes limitation
Suppose want to calculate the shortest path from one node to all other nodes, with the restriction of intermediate nodes cannot be more than a given number.
My major idea is, following how Dijkstra's ...
- 3,453
1
vote
1
answer
3k
views
Find index where left sum equals to right sum
Given an array, find if there is an index where left sum equals to right sum.
My idea is calculate sum, and scan again to see if there is an index for which ...
- 3,453
4
votes
4
answers
21k
views
Use Python to determine the repeating pattern in a string
I am writing an algorithm to count the number of times a substring repeats itself. The string is between 1-200 characters ranging from letters a-z. There should be no left overs at the end of the ...
- 145
2
votes
0
answers
147
views
Parse path string
Suppose path string are encoded in this way:
2T3T5: means move 2 steps, turn right, move 3 steps, turn right, and move 5 steps
32T: which better read as 3(2T), and it means do the following operation ...
- 3,453
3
votes
3
answers
6k
views
Finding the longest palindromic substring
I have the following code that works correctly. I am wondering if there is a simpler way to go about implementing my solution and/or if there is anything that looks non-standard in my code. If anyone ...
- 349
4
votes
2
answers
721
views
Checking whether any anagram of a string appears within another string
I have the following code that takes a string t and checks to see if any anagram of t is a substring of ...
- 349
3
votes
1
answer
88
views
Group duplicate files (part 3)
This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a ...
- 3,453
3
votes
1
answer
1k
views
Find the minimum path sum in a binary tree
I am working on the problem of finding the minimum path sum in a binary tree, and printing the path. The path can be from the root node to any leaf node.
Here is my code in Python 2.7. I am looking ...
- 3,453
1
vote
1
answer
118
views
Group duplicate files (part 2)
This is a continued discussion (from here => Group duplicate files) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a new post.
...
- 3,453
4
votes
1
answer
155
views
Group duplicate files
Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice ...
- 3,453
3
votes
0
answers
117
views
Quick select - shuffle to make sorting faster
I'm trying to use shuffle to improve worse case scenario of quick select (e.g. every time, selected pivot value is the largest, so each iteration, only one elements could be removed from judgement).
...
- 3,453
2
votes
3
answers
5k
views
Two ways to randomly shuffle cards
Here are two implementations I wrote to randomly shuffle cards.
The first method (shuffle) selects a random card, then swaps it to the front.
The second method (<...
- 3,453
8
votes
1
answer
1k
views
Find the nearest point of a given set of points (part 2)
This is a continued discussion from here, and I use new a approach (bounding box/or envelop algorithm) to improve the algorithm efficiency. Any code bugs, algorithm time complexity improvement or ...
- 3,453
8
votes
2
answers
3k
views
Sudoku solver recursive solution
Here is my code in Python 2.7 for a Sudoku resolver. Any advice on performance improvement, code bugs or general code style advice is appreciated.
My major idea is:
Using method generate some random ...
- 3,453
5
votes
1
answer
839
views
Counting the number of elements in a sorted array
Suppose I have a sorted array, and each element may appear multiple times.
To make it simple, here is an example:
...
- 3,453
9
votes
1
answer
9k
views
Find the nearest point of a given set of points
Suppose there are a set of given points (represented by x and y two dimensional coordinates), and for any given point A, I want ...
- 3,453
13
votes
1
answer
2k
views
Extended stable marriage challenge
I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
- 251
6
votes
2
answers
7k
views
Prefix search by trie tree
I'm working on the prefix search problem:
Given a set of words, for example words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats'], for any given prefix, find ...
- 3,453
3
votes
1
answer
248
views
Dynamic programming solution for cross river algorithm (part 2)
I'm working on the cross river problem (previous post here). Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style advice is appreciated.
More ...
- 3,453
5
votes
1
answer
1k
views
Dynamic programming solution for cross river algorithm
Working on below cross river problem, and post my code in Python 2.7 using dynamic programming. Any advice on performance improvement in terms of algorithm time complexity, code bugs or code style ...
- 3,453
2
votes
1
answer
1k
views
Minimize max distance of Gas Station
I'm working on this problem, and any advice on performance improvement, bugs or code style issues are appreciated.
Problem
Description
There are N gas stations on a straight, M kilo-meters ...
- 3,453
5
votes
1
answer
223
views
Using range minimal query for lowest common ancestor (LCA) -- part 2
Here is my code to use range minimal query to resolve the LCA problem. I applied comments from here.
Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style ...
- 3,453
3
votes
2
answers
613
views
Balanced smileys check algorithm (part 4)
This is a follow-up for here, for bug fixes and applied advice.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to ...
- 3,453
5
votes
1
answer
756
views
Balanced smileys check algorithm (part 3)
This is a follow-up for here, for bug fixes and applied advice.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to ...
- 3,453
2
votes
2
answers
645
views
Balanced smileys check algorithm (part 2)
This is a follow-up for here.
Problem
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to express himself
through ...
- 3,453
4
votes
1
answer
1k
views
Guess number with lower or higher hints
Problem statement
Two players - Alice and Bob. Alice needs to guess a number \$n\$, from
range \$[1, N]\$, \$N \le 200\$
In \$i\$th turn, Alice guesses a number \$i\$
Bob chooses to ...
- 3,453
9
votes
1
answer
846
views
Check “five in a row” for a 15x15 chess board (part 2)
This is a follow-up from here. I have a further optimization for space complexity by store only direction status data for one row for each directions (refer to variable ...
- 3,453
2
votes
1
answer
261
views
Circle check algorithm optimization for directed graph
Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly ...
- 3,453
5
votes
1
answer
1k
views
Quick select the kth smallest value
Here is my code for quick select in Python 2.7. I am trying to optimize code for fewer comparisons. And my specific question is marked in code, 3 lines marked with ...
- 3,453
4
votes
1
answer
513
views
Using range minimal query for lowest common ancestor (LCA)
Here is my code to use range minimal query to resolve the LCA problem. Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated.
More ...
- 3,453
3
votes
1
answer
1k
views
Rabin Karp algorithm improvement for string contains A to Z only
I have made some improvement to Rabin Karp algorithm when the source and pattern only contain the characters from A to Z. The improvement is, I use base 26 for hashing (as there are total 26 ...
- 3,453
2
votes
1
answer
320
views
Multiword Expression Tagging in Python
I am trying to write a small python code,where
I am reading a text file-which contains both Multiwords (MWEs)
and singular words (NMWEs).
I am trying to tag each one, as follows.
I have a ...
- 131