All Questions
226
questions
28
votes
4answers
14k views
Repeatedly multiplying digits until a single digit is obtained
I've written code that solves a problem from codewars.com. My code passes all the tests on the codewars site. It's a simple enough problem to solve naïvely, but I would love to improve the structure.
...
27
votes
2answers
3k views
Sudoku using 'exact cover' solver
1. Introduction
This is a solution to Weekend Challenge #3: a Sudoku solver in Python. It works by translating a Sudoku puzzle into an exact cover problem, and then solving the exact cover problem ...
17
votes
3answers
4k views
Knapsack branch and bound: forward filter
I've coded branch and bound to solve the knapsack problem, and use a greedy linear relaxation to find an upper bound on a node I'm currently exploring. What I mean by this is that I first sort the ...
17
votes
2answers
2k views
A KenKen puzzle/solver in Python
I've written a simple KenKen puzzle/solver in Python. I'd love some feedback on the design of the puzzle, as well as the architecture for the solver.
To model the puzzle, I have the following classes:...
16
votes
4answers
53k views
Get value from dictionary given a list of nested keys
I would like to get a deeply-nested value, for example {"a":{"b":{"c":"myValue"}} by providing the keys to traverse. I tried chaining together .get() but that didn'...
13
votes
3answers
37k views
GCD using Euclid algorithm
Below is the problem taken from here.
Question 10: GCD*
The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder)...
13
votes
2answers
781 views
N-Queens, bitwise approach
I've recently solved the famous N-Queens problem:
Can you place \$N\$ chess queens on a \$N × N\$ board in such a way that no one
attacks another queen?
The idea here is based on the ideas from ...
12
votes
6answers
4k views
Python 3 - Fibonacci Implementation
I wrote a function returning the n-th Fibonacci number in Python 3:
...
12
votes
2answers
2k views
Tower of Hanoi Recursive Implementation using Python with OOP
I have just finished a small program for Tower of Hanoi using recursion. I did it to practice OOP which I recently learnt. It took me about 2 hours to research about the recursive algorithm and write ...
12
votes
2answers
3k views
Sudoku solver using simple deductions and brute-force guessing
Here's my attempt at Weekend Challenge #3.
Key characteristics of this Python entry are:
The strategy is to alternate between "auto-complete" (making simple deductions such as naked singles and ...
12
votes
1answer
2k views
Flatten an array of integers in Python
The goal is to flatten an array of nested arrays of integers.
For example [1, [2], [3, [4]]] should return [1, 2, 3, 4]
I'm ...
11
votes
5answers
3k views
Python: pass “mutable integer” in recursion
I'm working on some code to find the max depth/height in a tree. I came up with a recursive solution, and I find myself needing to pass an integer "by reference". Currently, I'm using a mutable ...
11
votes
2answers
5k views
Lovely Lucky LAMBs
I am trying to solve this question from google's foobar. However, my code exceeds the time limit, even though when I tested it I got correct answers. How can I make my code more efficient?
Lovely ...
11
votes
2answers
411 views
Finding acronyms with >=1 letters at the start of each consecutive word
Problem
I'm seeking a clean and efficient way to determine whether one string is an initialism/acronym of another.
Example: IBM => International Business Machines
However, a key condition for my ...
9
votes
6answers
7k views
Base 26 (letters) and Base 10 using recursion
I was messing around with base conversion between decimal and Base26 (alphabet) with no 0th case because I needed it for the Google Sheets API in order to find specific cell values from a 3 ...
9
votes
2answers
4k views
Generate all valid combinations of n pair of parentheses
Implement an algorithm to print all valid (e.g. properly opened and
closed) combinations of n pair of parentheses.
Following is my implementation and I think it works. Is the algorithm efficient? ...
9
votes
1answer
9k views
Path finding algorithm using recursion in Python
Here is a code I developed some time ago. I wonder if there is anything I can do to improve it. It works for non-loopy mazes which was already my goal.
In the maze defined, ...
9
votes
1answer
619 views
Number in words: recursive function
I would appreciate some feedback on the below code I wrote for a Project Euler problem. The answer comes out correct but I'd like feedback on the design of the function and implementation of ...
9
votes
1answer
136 views
Tower of Hanoi with helper function
Here is my solution to the Tower of Hanoi problem using Python
...
8
votes
2answers
2k views
Python traverse a directory recursively and print contact numbers
I am writing a python code to recursively traverse a directory containing only text files and then print the 10 digit Indian phone number and all its variants. I am very new to python and I have ...
8
votes
3answers
15k views
Recursive binary search in Python
I have implemented a recursive binary search in Python and tried to implement some verification to my code. Other than that, is there any optimization I am missing?
...
8
votes
2answers
1k views
Tic-Tac-Toe Recursive Solver
I am attempting to create a Tic-Tac-Toe game that uses a recursively checks every possible game board, and finds which boards result in a victory for X. (I ultimately plan to turn this into an AI ...
8
votes
4answers
141 views
Lazy generator of strings in lexicographical order
I needed to write a Python generator that lazily generates, in lexicographical order, strings composed of a certain alphabet (e.g. lowercase English letters).
My first thought was to make an infinite ...
8
votes
1answer
168 views
Find all paths in a graph
My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved?
Can some form of memoization be used here? There are cases ...
8
votes
1answer
862 views
Recursive search for combinations of words that have a specified MD5 hash
This code solves a challenge problem that a local company is hosting to attract/screen applicants. The link to the challenge is here.
In brief, we are given a wordlist containing approximately 100,...
8
votes
2answers
3k views
Permutations with replacement in Python
Many a times, I've had the need to use a permutations with replacement function.
So, I've written a function to do just that:
...
8
votes
1answer
616 views
Convert Iterable tree to string
I code this function to convert list of dict to a specific string to export last in a row table string field.
...
7
votes
4answers
21k views
Fibonacci sum with memoization
Problem:
Using the recursion approach, find a Fibonacci sum without repetition of computation.
...
7
votes
3answers
3k views
Simplifying this factorial function
def factorial(t,n):
if n == 1 : return t
else: x = (t * (n-1))
n = n-1
return factorial(x,n)
print factorial(6,6)
I can't seem to figure out a ...
7
votes
3answers
560 views
Sierpinski turtle triangle
I am working through Programming Fundamentals with Python on Udacity. The assignment was to create a recursive triangle. I am happy with the output, but I am hoping for feedback on the actual ...
7
votes
2answers
600 views
Recursive function and memorization to find minimum operations to transform n to 1
I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution.
...
7
votes
2answers
729 views
Recursive higher-order function
I have implemented a through function for myself in a project.
Since I am still quite new in python and want to learn it correctly, I would be happy about any ...
7
votes
1answer
676 views
Printing the number of ways a message can be decoded
My below solution to the following problem is exceeding the maximum recursion depth. I am looking for any improvements which i can make.
Problem
Alice and Bob need to send secret messages to each ...
7
votes
2answers
932 views
Web Scraper in Python
So, this is my first web scraper (or part of it at least) and looking for things that I may have done wrong, or things that could be improved so I can learn from my mistakes.
I made a few short ...
7
votes
1answer
177 views
Calculate highscores based on sales data
The background is my question is SO How to create a list of totals for durations?
where I found a recursive solution that I want to review. I could not test it for higher levels than 1 but to the best ...
6
votes
3answers
32k views
Get subsets of a set given as a list
This code is meant to create a list of subsets of a given set which is represented as a list.
I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures ...
6
votes
3answers
7k views
Tree structure with support for inorder and preorder traversal
I am learning Tree Data Structures and came up with this code for implementing basic Tree Node using class and performing various Tree based operations like Traversals and others. The code works ...
6
votes
3answers
1k views
Deep/recursive join, all, any, sum, len
I keep forgetting that the standard join() can only take a single iterable, so I made a few functions that act recursively on any passed arguments. Somewhat ...
6
votes
1answer
4k views
“Deep length” of a list
A list that contains one or more lists as elements is called a deep
list. For example, [1, [2, 3], 4] is a deep list.
Write a function ...
6
votes
2answers
868 views
Find the second largest number in an array with at most n + log2 n - 2 comparisons
This exercise is from Roughgarden's (excellent) course on algorithms on Coursera:
You are given as input an unsorted array of n distinct numbers, where
n is a power of 2. Give an algorithm that ...
6
votes
2answers
594 views
ASCII Paint Bucket
In MS Paint, if we choose paint bucket and fill click on a certain spot, it gets filled with a new chosen color along with its neighboring pixels that are the same color until it reaches certain ...
6
votes
3answers
11k views
Using pycparser to parse C header files
I have a small program which makes uses of pycparser to parse C header files. The code, unfortunately, kinda sprawls out everywhere to handle the different cases (example below).
What's the best way ...
6
votes
1answer
2k views
Longest common subsequence length and backtracking the string
Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...
6
votes
1answer
438 views
Ackermann function in Python 2.7
I'm relatively new to Python. I just want some constructive feedback on how to improve my code efficiency, style, error handling, etc.
In this case, I've programmed the Ackermann function, but it won'...
6
votes
2answers
6k views
Making the same amount from different combinations of coins (top-down approach)
I was reading a typical interview question found here. Given an amount and a list of denominations, count the number of possible ...
6
votes
2answers
94 views
Python backtracking algorithm to solve sudoku
I have recently gotten back into writing python and i decided to take up a project of writing a backtracking algorithm in python to solve Sudoku puzzles
How it Works
A matrix is declared to represent ...
6
votes
1answer
958 views
Functional, but not recursive, tree traversal
To learn tree traversal i implemented os.walk, tail-recursive and stack-based. Unfortunately Python doesn't support tail call optimization. How do i rewrite my ...
6
votes
0answers
995 views
Codewars: N-dimensional Von Neumann Neighborhood in a matrix
Task:
For creating this challenge on Codewars I need a very performant
function that calculates Von Neumann Neighborhood in a N-dimensional
array. This function will be called about 2000 times
The ...
5
votes
3answers
2k views
Insertion sort via recursion
I'm learning about algorithms and have been recently experimenting with insertion sort via recursion in Python.
My code works fine, but I was wondering if there are any possible improvements that ...
5
votes
2answers
129 views
Traveling salesman to find beer types from breweries
I am writing a modified travelling salesman problem recursively in Python 3.7. It has to find the best path around breweries to find the most beer types and not to exceed the ...
