I’m writing an algorithm to solve skyscrapers puzzles: Skyscraper puzzles combine the row and column constraints of Sudoku with external clue values that re-imagine each row or column of numbers as a road full of skyscrapers of varying height. Higher numbers represent higher buildings. To solve a Skyscr…
Tag: algorithm
Mergesort with Python
I couldn’t find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds Answer You can initialise the whole result list in the top level call to mergesort: Then for the recursive calls you can use a helper …
Python Integer Partitioning with given k partitions
I’m trying to find or develop Integer Partitioning code for Python. FYI, Integer Partitioning is representing a given integer n as a sum of integers smaller than n. For example, an integer 5 can be expressed as 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1
Efficient calculation of Fibonacci series
I’m working on a Project Euler problem: the one about the sum of the even Fibonacci numbers. My code: The problem’s solution can be easily found by printing sum(list2). However, it is taking a lot of time to come up with the list2 I’m guessing. Is there any way to make this faster? Or is it …
Python string ‘in’ operator implementation algorithm and time complexity
I am thinking of how the in operator implement, for instance In CPython, which algorithm is used to implement the string match, and what is the time complexity? Is there any official document or wiki about this? Answer It’s a combination of Boyer-Moore and Horspool. You can view the C code here: Fast se…
Find the smallest number that is greater than a given number in a sorted list
Given a sorted list of numbers, I need to find the smallest number that is greater than a given number. Consider this list: Say the specified number is 320. Then, my method should return 353 as 353 is the smallest number greater than 320. I am trying to use a slightly modified form of binary search; however o…
How to trace the path in a Breadth-First Search?
How do you trace the path of a Breadth-First Search, such that in the following example: If searching for key 11, return the shortest list connecting 1 to 11. Answer You should have look at http://en.wikipedia.org/wiki/Breadth-first_search first. Below is a quick implementation, in which I used a list of list…
How does one find the largest consecutive set of numbers in a list that are not necessarily adjacent?
For instance, if I have a list This algorithm should return [1,2,3,4,5,6,7,8,9,10,11]. To clarify, the longest list should run forwards. I was wondering what is an algorithmically efficient way to do this (preferably not O(n^2))? Also, I’m open to a solution not in python since the algorithm is what mat…
Rolling or sliding window iterator?
I need a rolling window (aka sliding window) iterable over a sequence/iterator/generator. (Default Python iteration could be considered a special case, where the window length is 1.) I’m currently using the following code. How can I do it more elegantly and/or efficiently? For the specific case of windo…
Python file parsing: Build tree from text file
I have an indented text file that will be used to build a tree. Each line represents a node, and indents represent depth as well as node the current node is a child of. For example, a file might look like ROOT Node1 Node2 Node3 Node4 Node5 Node6 Which indicates that ROOT contains three children: 1, 5, and 6, …