Popular recipes tagged "algorithm" but not "algorithms"http://code.activestate.com/recipes/tags/algorithm-algorithms/2017-05-12T10:40:58-07:00ActiveState Code Recipesgroupby() For Unsorted Input (Python)
2017-05-12T10:40:58-07:00Alfehttp://code.activestate.com/recipes/users/4182236/http://code.activestate.com/recipes/580800-groupby-for-unsorted-input/
<p style="color: grey">
Python
recipe 580800
by <a href="/recipes/users/4182236/">Alfe</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/datastructures/">datastructures</a>, <a href="/recipes/tags/generators/">generators</a>, <a href="/recipes/tags/grouping/">grouping</a>, <a href="/recipes/tags/lazy/">lazy</a>).
</p>
<p>We all know the <code>groupby()</code> which is available in the <code>itertools</code> standard module. This one yields groups of consecutive elements in the input which are meant to be together in one group. For non-consecutive elements this will yield more than one group for the same key.</p>
<p>So effectively, <code>groupby()</code> only reformats a flat list into bunches of elements from that list without reordering anything. In practice this means that for input sorted by key this works perfect, but for unsorted input it might yield several groups for the same key (with groups for other keys in between). Typically needed, though, is a grouping with reordering if necessary.</p>
<p>I implemented a likewise lazy function (yielding generators) which also accepts ungrouped input.</p>
Extended Euclidean Algorithm (Python)
2016-03-03T07:12:28-08:00Samuel James Ericksonhttp://code.activestate.com/recipes/users/4187478/http://code.activestate.com/recipes/578631-extended-euclidean-algorithm/
<p style="color: grey">
Python
recipe 578631
by <a href="/recipes/users/4187478/">Samuel James Erickson</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/discrete/">discrete</a>, <a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/euclid/">euclid</a>, <a href="/recipes/tags/extended/">extended</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/logarithm/">logarithm</a>).
Revision 2.
</p>
<p>given input of integers a and b, this program returns GCD(a,b) along with integers x and y such that ax+by=GCD(a,b).</p>
Finding sets in the card game SET! (Python)
2013-04-05T12:49:36-07:00Sander Evershttp://code.activestate.com/recipes/users/4173111/http://code.activestate.com/recipes/578508-finding-sets-in-the-card-game-set/
<p style="color: grey">
Python
recipe 578508
by <a href="/recipes/users/4173111/">Sander Evers</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/optimization/">optimization</a>, <a href="/recipes/tags/search/">search</a>, <a href="/recipes/tags/setgame/">setgame</a>).
Revision 2.
</p>
<p>In the card game <a href="http://en.wikipedia.org/wiki/Set_%28game%29">SET!</a>, players are shown an array of 12 (or more) symbol cards and try to identify a so-called 3-card <strong>set</strong> among these cards as quickly as possible.</p>
<p>A card has four attributes (number, shape, color and shading), each of which can take 3 possible values. In a <strong>set</strong>, for each attribute, all three cards should have either the same value, or the three different values.</p>
<p>This recipe solves the problem of finding <em>all</em> sets within an array of an arbitrary number of cards, showing some clever optimizations and celebrating the clarity of Python in expressing the algorithms.</p>
Eight queen problem (Javascript) (JavaScript)
2013-03-20T19:03:44-07:00Thomas Lehmannhttp://code.activestate.com/recipes/users/4174477/http://code.activestate.com/recipes/578497-eight-queen-problem-javascript/
<p style="color: grey">
JavaScript
recipe 578497
by <a href="/recipes/users/4174477/">Thomas Lehmann</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/queen/">queen</a>, <a href="/recipes/tags/queens/">queens</a>).
</p>
<ul>
<li>Adding this for my old <a href="http://code.activestate.com/recipes/577438/">recipe 577438</a> (in Python).</li>
<li>Use node.js or HTML as execution (see comments in "log" function)</li>
</ul>
Topological Sort (Python)
2012-09-27T12:21:23-07:00Sam Dentonhttp://code.activestate.com/recipes/users/4172262/http://code.activestate.com/recipes/578272-topological-sort/
<p style="color: grey">
Python
recipe 578272
by <a href="/recipes/users/4172262/">Sam Denton</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/sort/">sort</a>, <a href="/recipes/tags/sorting/">sorting</a>, <a href="/recipes/tags/topological/">topological</a>, <a href="/recipes/tags/toposort/">toposort</a>).
</p>
<p>A topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).</p>
Generating Balanced Parenthesis (Python)
2013-02-14T22:00:22-08:00bartenderhttp://code.activestate.com/recipes/users/4185259/http://code.activestate.com/recipes/578458-generating-balanced-parenthesis/
<p style="color: grey">
Python
recipe 578458
by <a href="/recipes/users/4185259/">bartender</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>).
</p>
<p>The python code generates balanced parenthesis recursively.
Example for depth=3 i.e. 3 opening brackets and 3 closing brackets,the sample output should be:</p>
<p>((()))
(()())
(())()
()(())
()()()</p>
<p>The number of such output ( 5 in above case) is a Catalan Number.</p>
topological sorting again (Python)
2013-03-06T19:21:11-08:00yotahttp://code.activestate.com/recipes/users/4184815/http://code.activestate.com/recipes/578406-topological-sorting-again/
<p style="color: grey">
Python
recipe 578406
by <a href="/recipes/users/4184815/">yota</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/graph/">graph</a>, <a href="/recipes/tags/python3/">python3</a>, <a href="/recipes/tags/sort/">sort</a>, <a href="/recipes/tags/topological/">topological</a>).
Revision 9.
</p>
<p>Topological sorting is the answer to the following question : in a direct acyclic graph, how can I pick up nodes "in order", such as upstream nodes are always before downstream ones ? Many solutions may exists, many algorithms too.</p>
<p>Alas, it seems I'm too stupid to understand already proposed recipes on topological sorting. Hopefully I do grasp the "write once, read many" concept.</p>
<p>Here, you will find a plain algorithm, optimized only for code clarity, of a topological sorting for direct acyclic graphs, implemented in python from the pseudo code found on <a href="http://en.wikipedia.org/wiki/Topological_sorting">wikipedia</a>:</p>
<pre class="prettyprint"><code>L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
</code></pre>
<p>Only tested with python3.2, should work with other versions. Be careful, code indented with tabs, since space is evil è_é</p>
Super Simple Sudoku Solver in Python source code (Python)
2012-06-23T14:56:05-07:00David Adlerhttp://code.activestate.com/recipes/users/4182015/http://code.activestate.com/recipes/578140-super-simple-sudoku-solver-in-python-source-code/
<p style="color: grey">
Python
recipe 578140
by <a href="/recipes/users/4182015/">David Adler</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/recursive/">recursive</a>, <a href="/recipes/tags/recurssion/">recurssion</a>, <a href="/recipes/tags/sodoku/">sodoku</a>, <a href="/recipes/tags/sudoku/">sudoku</a>).
Revision 5.
</p>
<p>A simple algorithm which uses a recursive function to solve the puzzle.</p>
<hr />
<p>THE ALGORITHM</p>
<p>The credit for this algorithm must go to Richard Buckland:
<a href="http://www.youtube.com/watch?v=bjObm0hxIYY&feature=autoplay&list=PL6B940F08B9773B9F&playnext=1" rel="nofollow">http://www.youtube.com/watch?v=bjObm0hxIYY&feature=autoplay&list=PL6B940F08B9773B9F&playnext=1</a></p>
<p>Takes a partially filled in grid, inserts the min value in a cell (could be a random cell, in this case the first free cell). If the min value is not legal it will increment until the max value is reached (number 9), checking each time if the incremented value is legal in that cell (ie does not clash with any already entered cells in square, col or row). If it is legal, it will call itself (the hasSolution function) thus using this slightly more filled in grid to find a new cell and check which value is legal in this next cell. If no values are legal in the next cell, it will clear the previous grid entry and try incrementing the value.</p>
<p>isLegal = does not conflict with any other numbers in the same row, column or square</p>
Genetic Algorithm in Python source code - AI-Junkie tutorial (Python)
2012-06-19T12:59:13-07:00David Adlerhttp://code.activestate.com/recipes/users/4182015/http://code.activestate.com/recipes/578128-genetic-algorithm-in-python-source-code-ai-junkie-/
<p style="color: grey">
Python
recipe 578128
by <a href="/recipes/users/4182015/">David Adler</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/artificial/">artificial</a>, <a href="/recipes/tags/genetic/">genetic</a>, <a href="/recipes/tags/network/">network</a>, <a href="/recipes/tags/neural/">neural</a>, <a href="/recipes/tags/python/">python</a>).
Revision 5.
</p>
<p>A simple genetic algorithm program. I followed this tutorial to make the program <a href="http://www.ai-junkie.com/ga/intro/gat1.html." rel="nofollow">http://www.ai-junkie.com/ga/intro/gat1.html.</a></p>
<p>The objective of the code is to evolve a mathematical expression which calculates a user-defined target integer.</p>
<hr />
<p>KEY:</p>
<p>chromosome = binary list (this is translated/decoded into a protein in the format number --> operator --> number etc, any genes (chromosome is read in blocks of four) which do not conform to this are ignored.</p>
<p>protein = mathematical expression (this is evaluated from left to right in number + operator blocks of two)</p>
<p>output = output of protein (mathematical expression)</p>
<p>error = inverse of difference between output and target</p>
<p>fitness score = a fraction of sum of of total errors</p>
<hr />
<p>OTHER:</p>
<p>One-point crossover is used.</p>
<p>I have incorporated <strong>elitism</strong> in my code, which somewhat deviates from the tutorial but made my code more efficient (top ~7% of population are carried through to next generation)</p>
Evolutionary Algorithm (Generation of Prime Numbers) (Python)
2011-11-27T06:45:00-08:00Alexander James Wallarhttp://code.activestate.com/recipes/users/4179768/http://code.activestate.com/recipes/577964-evolutionary-algorithm-generation-of-prime-numbers/
<p style="color: grey">
Python
recipe 577964
by <a href="/recipes/users/4179768/">Alexander James Wallar</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/example/">example</a>, <a href="/recipes/tags/genetic/">genetic</a>, <a href="/recipes/tags/genetic_algorithm/">genetic_algorithm</a>, <a href="/recipes/tags/genetic_algorithms/">genetic_algorithms</a>, <a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/number/">number</a>, <a href="/recipes/tags/of/">of</a>, <a href="/recipes/tags/prime/">prime</a>, <a href="/recipes/tags/primelist/">primelist</a>, <a href="/recipes/tags/primes/">primes</a>, <a href="/recipes/tags/theory/">theory</a>).
</p>
<p>This is an evolutionary algorithm that returns a random list of prime numbers. This code is highly inefficient for a reason. This algorithm is more of a proof of concept that if a prime was a heritable trait, it would not be a desired one. </p>
<p>Parameters:</p>
<p>isPrime --> n: number to check if it is prime
allPrimes --> n: size of list of random primes, m: the primes in the list will be between 0 and m</p>
Rsync Algorithm (Python)
2011-01-09T16:32:22-08:00Eric Pruitthttp://code.activestate.com/recipes/users/4170757/http://code.activestate.com/recipes/577518-rsync-algorithm/
<p style="color: grey">
Python
recipe 577518
by <a href="/recipes/users/4170757/">Eric Pruitt</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/delta/">delta</a>, <a href="/recipes/tags/diff/">diff</a>, <a href="/recipes/tags/patch/">patch</a>, <a href="/recipes/tags/python3/">python3</a>, <a href="/recipes/tags/rsync/">rsync</a>).
Revision 4.
</p>
<p>This is a pure Python implementation of the <a href="http://samba.anu.edu.au/rsync/">rsync algorithm</a>. On my desktop (3.0GHz dual core, 7200RPM), best case throughput for target file hash generation and delta generation is around 2.9MB/s. Absolute worst case scenario (no blocks in common) throughput for delta generation is 200KB/s to 300KB/s on the same system.</p>
<p>Tested in Python 2.5, 2.6, and 3.1. In 2.7, io.BufferedReader should yield the best throughput. On all other versions use __builtin__.open.</p>
Chess Notation Player (Python)
2011-05-25T18:41:33-07:00Stijn de Graafhttp://code.activestate.com/recipes/users/4178055/http://code.activestate.com/recipes/577719-chess-notation-player/
<p style="color: grey">
Python
recipe 577719
by <a href="/recipes/users/4178055/">Stijn de Graaf</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/chess/">chess</a>, <a href="/recipes/tags/game/">game</a>, <a href="/recipes/tags/notation/">notation</a>, <a href="/recipes/tags/viewer/">viewer</a>).
</p>
<p>This allows you to input the algebraic chess notation of a game, move by move, and the position of the pieces will be shown on the screen. The upper case letters represent Black pieces and the lower case letters represent White pieces. Most notations are accepted, including Castling and Disambiguating. For details on Algebraic Chess notation see: <a href="http://en.wikipedia.org/wiki/Algebraic_chess_notation." rel="nofollow">http://en.wikipedia.org/wiki/Algebraic_chess_notation.</a></p>
Simple Sudoku (Python)
2011-06-02T14:15:02-07:00amir naghavihttp://code.activestate.com/recipes/users/4177294/http://code.activestate.com/recipes/577716-simple-sudoku/
<p style="color: grey">
Python
recipe 577716
by <a href="/recipes/users/4177294/">amir naghavi</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/game/">game</a>, <a href="/recipes/tags/oo/">oo</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/random/">random</a>, <a href="/recipes/tags/sudoku/">sudoku</a>).
Revision 10.
</p>
<p>This is a simple sudoku game.</p>
converting numbers to their alphabetical style (Python)
2011-03-17T06:57:06-07:00amir naghavihttp://code.activestate.com/recipes/users/4177294/http://code.activestate.com/recipes/577607-converting-numbers-to-their-alphabetical-style/
<p style="color: grey">
Python
recipe 577607
by <a href="/recipes/users/4177294/">amir naghavi</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/string/">string</a>).
Revision 4.
</p>
<p>converts numbers to alphabetical numbers </p>
interleave bits (aka morton-ize aka z-order curve) (Python)
2011-02-02T12:50:58-08:00Romain Dartigueshttp://code.activestate.com/recipes/users/4167472/http://code.activestate.com/recipes/577558-interleave-bits-aka-morton-ize-aka-z-order-curve/
<p style="color: grey">
Python
recipe 577558
by <a href="/recipes/users/4167472/">Romain Dartigues</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/bits/">bits</a>, <a href="/recipes/tags/manipulation/">manipulation</a>, <a href="/recipes/tags/mathematical/">mathematical</a>, <a href="/recipes/tags/mathematics/">mathematics</a>).
</p>
<p>This recipe let you encode in a single number two or three numbers.</p>
<p>Note: this is only an adaptation of the recipes from <strong>Sean Eron Anderson</strong> and <strong>Fabian “ryg” Giesen</strong>; all credits goes to the respective authors.</p>
<ul>
<li><a href="http://graphics.stanford.edu/%7Eseander/bithacks.html#InterleaveBMN" rel="nofollow">http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN</a></li>
<li><a href="http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/" rel="nofollow">http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/</a></li>
</ul>
SMS_Encryption (Python)
2011-03-14T08:26:29-07:00amir naghavihttp://code.activestate.com/recipes/users/4177294/http://code.activestate.com/recipes/577606-sms_encryption/
<p style="color: grey">
Python
recipe 577606
by <a href="/recipes/users/4177294/">amir naghavi</a>
(<a href="/recipes/tags/acm/">acm</a>, <a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/encryption/">encryption</a>).
</p>
<p>the answer of an acm problem to further explantion look at source code.</p>
Topological Sort (Python)
2010-09-28T19:22:27-07:00Paddy McCarthyhttp://code.activestate.com/recipes/users/398009/http://code.activestate.com/recipes/577413-topological-sort/
<p style="color: grey">
Python
recipe 577413
by <a href="/recipes/users/398009/">Paddy McCarthy</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/sorting/">sorting</a>, <a href="/recipes/tags/topological/">topological</a>).
</p>
<p>Given items that depend on other items, a topological sort arranges items in order that no one item precedes an item it depends on.
In this example items are strings and dependencies are expressed in a dictionary whose keys are items and whose values are a set of dependent items. Note that the dict may contain self-dependencies (which are ignored), and dependent items that are not also dict keys, such as the item 'ieee'.</p>
TRAC Interpreter -- Sixties programming language (Python)
2010-08-22T19:05:09-07:00Jack Trainorhttp://code.activestate.com/recipes/users/4076953/http://code.activestate.com/recipes/577366-trac-interpreter-sixties-programming-language/
<p style="color: grey">
Python
recipe 577366
by <a href="/recipes/users/4076953/">Jack Trainor</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/educational/">educational</a>, <a href="/recipes/tags/interpreter/">interpreter</a>, <a href="/recipes/tags/language/">language</a>, <a href="/recipes/tags/trac/">trac</a>).
</p>
<p>A Python implementation of an interpreter for the TRAC programming language developed by Calvin Mooers in the early 1960s. This implementation reconstructs Mooers' original algorithm in Python and supports only a limited number of TRAC primitives for demonstration purposes.</p>
TRAC Interpreter - Dragon style (Python)
2010-09-20T00:42:21-07:00Jack Trainorhttp://code.activestate.com/recipes/users/4076953/http://code.activestate.com/recipes/577396-trac-interpreter-dragon-style/
<p style="color: grey">
Python
recipe 577396
by <a href="/recipes/users/4076953/">Jack Trainor</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/educational/">educational</a>, <a href="/recipes/tags/interpreter/">interpreter</a>, <a href="/recipes/tags/language/">language</a>, <a href="/recipes/tags/lexical_analyzer/">lexical_analyzer</a>, <a href="/recipes/tags/trac/">trac</a>).
</p>
<p>I've rewritten the TRAC interpreter from <a href="http://code.activestate.com/recipes/577366/">Recipe 577366</a> using a modern recursive descent style based on the Dragon book's lexer/parser model at the end of "Compliers: Principles, Techniques and Tools," Chapter 2, by Aho, Sethi, Ullman (1986).</p>
TRAC Interpreter - Class and Stack version (Python)
2010-09-20T01:16:07-07:00Jack Trainorhttp://code.activestate.com/recipes/users/4076953/http://code.activestate.com/recipes/577397-trac-interpreter-class-and-stack-version/
<p style="color: grey">
Python
recipe 577397
by <a href="/recipes/users/4076953/">Jack Trainor</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/educational/">educational</a>, <a href="/recipes/tags/interpreter/">interpreter</a>, <a href="/recipes/tags/language/">language</a>, <a href="/recipes/tags/lexical_analyzer/">lexical_analyzer</a>, <a href="/recipes/tags/trac/">trac</a>).
</p>
<p>This is my third and final version of the Trac Interpreter from <a href="http://code.activestate.com/recipes/577366/">Recipe 577366</a>. It processes the character stream into appropriate class objects and stores these objects on a stack.</p>