This post described a python solution on coding challenge "the power sum" (med) and common points on BFS algorithm. The_Power_Sum asks how many solutions on equation \(n_1^x + n_2^x + .. n_i^x = n\) when \(n_1, n_2, n_i \in [1, n]\)
Problem Statement
Given positive numbers \(n,x\) and find how many solutions can satisfy \(n_1^x + n_2^x + .. n_i^x = n\) when \(n_1, n_2, n_i \in [1, n]\). Since every number is unique and only shows up once from \([1,n]\), with the symmetry of \(+\) operation, the answer is how many combinations from set \([1,n]\), not permutation. On a general perspective of view, the solution space is within \(\sum_{i=1}^n C(^n_k)\), which is \(2^n\).
For example, if n is 10 and x is 2 then there answer is 1 since there is only one solution of \(1^2 + 3^2 = 10\). But 100, 2 would get 3 as answer because \(100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2\).
Rephrase the Problem to Mathimatical Language
Terminology
BFS: Breadth First Search. Classic BFS defines problem as a search in space described by set V, E where each V as vertex has a set of E (\(V_i \to V_j\) where \(V_i, V_j \in V\)).
The worst performance is \(O(|V| + |E|)\) because it travels from all candidate vertexes and loops all possible \(E_i\). Therefore, to cache all the candidate partial results, the worst space complexity is \(O(|V|)\). Here \(E\) only describes the state transition and a \(O(|V|)\) structure queues the concerned information on paths.
The classic BFS procedure is straight, simple and useful. We can find the transformed BFS in DB join query, distributed query on indexes or caches, Fast Hashing, GeoApps as Navigator and Shopping Guide Apps. Keys within fundamental algorithms are how to apply the abstract model to real worlds \(\lambda \to \pi\). The most natrual principal of computer system design is to mimic a structure which represents the nouns of concepts from real world. Which requests a map from machine space to human view space.
Problem Space
To apply the thoughts of DFS and BFS algorithm we shall rephase the problem to a typical search in given logical sapce. Moreover, if we generally define a vector to present the tracks of current search, a set of vector could be regarded as the set of partial search results.
Intermediate Result Set
BFS, as how the term is coined, will cache the intermediate results and move forward on all of them during each step. So it is fair to all possible branches. That's why it can find the fastest path(s).
Here search sapce it numbers of [1, n]. Since each number can only show up once or not, we have n vertexes on a linear space. We can assign 0, 1 to the vertex to mark it picked up or not picked-up in current search branch. The string of '0' and '1' can represent a path of current search and the strings in list can play the data structure as the intermediate vectors of partial search results.
Algorithm Application Key Points:
My previous post is about a common recursive design of DFS. It emphasized two key steps to form a recursive solution.
- ✎ Termination condition: For DFS, it is the test whether to record the result as a success and whether to continue the search. Back to current problem, I stop the branch because it is not meaningful to add any positive number since the summary is already satisfied or even exceeded.
- Whether to record the success path when termination state found
- Whether to continue search: if there is a cycle of arcs from one termination state to another termination state and the path is meaningful, we shall continue but be reminded of cycles in search.
- ✎ How to reduce: "Reduce" is a term to apply the sub-problem (current scope of search) of DFS to join the other branch of search.
For a BFS algorithm, we evaluate all branches on the same depth level in search. Sometimes the depth is a term of cost. Here for current problem, we can assign the number of positive numbers visited as the depth of search.
On each step, BFS check the partial search result set and work on all partial paths. Usually we loop all of the candidates and move forward one step if the candidate can generate further paths to search.
Smart Search
A loop on all candidates is mentioned in above section. However, it could be generalized to a weight based candidate set. So a ranking based on partial results can be assessed. Based on what we know for each step, the weight will be adjusted. A smart search can work from high ranked candidate branch to the low ranked ones. Which is also the key to \(A^*\) algorithm although heuristic algorithms are not within the scope of this post.
In current solution to "The Sum of Power" coding challenge, we just force the exceeded partial search paths do not take any more number. It is to cut off not useful branches in the search space.
To shrink the search scope for this particular problem, uplimit is calculated because for \(n_i > \sqrt[X]N where i \in [1, n]\) the \(n_i\) is safe to bypass. Each element has two branches on search paths, '1': selected, '0': bypassed, so search space is within \(2^{lmt}\).
Solution and code
With above understanding, turning design into codes is a straight and clear action. The BFS codes have 11 lines in Python to search given space.
A dict is introduced to queue the intermediate results as {search path in 0|1 string : partial sum }.
def bfs(lmt, tgt, pwr): |
We could not alter an iterator within the iteration loop with Python (or other langauge like Java). So a tmp_rec is introduced to queue those partial paths which are meaningful to take further efforts to catch up and search deeper.
Following Up
This problem is a common BFS application occasion. As we have above implementation for BFS, a general way of coding can be applied to other BFS solution.
(TBC: Would get back and add other generalized BFS solving examples.)
References
The coding challenge link, https://www.hackerrank.com/challenges/the-power-sum
Previous Post, http://maxwu.me/2017/05/02/Recursive-Depth-First-Search-with-a-tracking-Set
Change Log
- May 18, 2017: Change to MathJax format to rewrite equations clearly.
- May 16, 2017: Finish the initial draft.