http://code.activestate.com/recipes/tags/breadth_first_search/2013-10-02T12:52:23-07:00ActiveState Code Recipes2013-10-02T12:52:23-07:00Rutger Saalminkhttp://code.activestate.com/recipes/users/4187940/http://code.activestate.com/recipes/578678-shortest-common-supersequence-algorithms/

<p style="color: grey"> Python recipe 578678 by <a href="/recipes/users/4187940/">Rutger Saalmink</a> (<a href="/recipes/tags/approximation/">approximation</a>, <a href="/recipes/tags/bound/">bound</a>, <a href="/recipes/tags/breadth_first_search/">breadth_first_search</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/depth_first_search/">depth_first_search</a>, <a href="/recipes/tags/sequence/">sequence</a>, <a href="/recipes/tags/shortest/">shortest</a>, <a href="/recipes/tags/super/">super</a>). </p> <p>The Shortest Common Supersequence (SCS) problem is an NP-hard problem (<a href="https://en.wikipedia.org/wiki/Shortest_common_supersequence" rel="nofollow">https://en.wikipedia.org/wiki/Shortest_common_supersequence</a>), which occurs in problems originating from various domains, e.g. Bio Genetics. Given a set of strings, the common supersequence of minimal length is sought after. Below a set of algorithms is given, which I used in approximating and/or backtracking the optimal solution(s). </p>

2009-03-16T13:35:05-07:00Stephen Chappellhttp://code.activestate.com/recipes/users/2608421/http://code.activestate.com/recipes/576692-sliding-block-puzzle-solver/

<p style="color: grey"> Python recipe 576692 by <a href="/recipes/users/2608421/">Stephen Chappell</a> (<a href="/recipes/tags/breadth_first_search/">breadth_first_search</a>, <a href="/recipes/tags/puzzle_solver/">puzzle_solver</a>). </p> <p>Recently, I was playing a game called "An Untitled Story" and was frustrated at some of the puzzles it contained. One such puzzle type was a sliding block puzzle game that presented the player with walls, movable blocks, and targets that you had to place the blocks on. The blocks could be moved an infinite amount of times, but once put into motion, they would continue until they hit either a wall or another block. To help solve these puzzle, I wrote the following program to figure out the solutions for me. It can find valid answers far faster than the human mind. The program is somewhat messy but looks much better than its first version.</p>