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 Skyscraper puzzle you must place 1 to 5, or 1 to whatever the
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 function to which you
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 okay even this way…
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 search/count implementation, based on a mix between
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 on execution the
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 to represent the queue of paths. This prints: [‘1’, ‘4’,
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 matters. Thank you. Answer Here is a simple one-pass O(n) solution:
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 window_size == 2 (i.e., iterating over adjacent, overlapping pairs in a sequence), see
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, Node1