Popular recipes tagged "algorithm"

groupby() For Unsorted Input (Python)

2017-05-12T10:40:58-07:00

Python recipe 580800 by Alfe (algorithm, datastructures, generators, grouping, lazy).

We all know the groupby() which is available in the itertools 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.

So effectively, groupby() 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.

I implemented a likewise lazy function (yielding generators) which also accepts ungrouped input.

Reversi Othello (Python)

2016-09-19T18:03:09-07:00

Python recipe 580698 by FB36 (ai, algorithm, algorithms, game, games).

Reversi/Othello Board Game using Minimax, Alpha-Beta Pruning, Negamax, Negascout algorithms.

Simple Infix Expression Evaluation (Python)

2015-11-07T18:44:05-08:00

Python recipe 579122 by FB36 (algorithm, algorithms, math, mathematics, stack).

Simple infix expression evaluation using a stack.

Hopfield Artificial Neural Network (C++)

2016-07-03T21:58:49-07:00

C++ recipe 580688 by Jay baller (ai, algorithm, algorithms, artificial_intelligence, neural_network).

(Discrete (Binary)) Hopfield Artificial Neural Network (ANN).

For more info see:

http://en.wikipedia.org/wiki/Hopfield_net

http://www.scholarpedia.org/article/Hopfield_network

Computing simple list functions recursively (Python)

2016-03-01T20:41:13-08:00

Python recipe 580617 by Vasudev Ram (algorithm, algorithms, lists, python, python2, recursion, recursive).

This recipe shows how to compute some simple list functions (functions that operate on lists) using simple recursive algorithms. Simple non-recursive algorithms exist for these tasks; this recipe is just for illustrative purposes. However, the principles described can be used for more complex recursive algorithms, for which non-recursive algorithms might be more complex than the recursive ones.

Infix Expression Evaluation (Python)

2015-11-08T05:08:26-08:00

Python recipe 579123 by FB36 (algorithm, algorithms, math, mathematics, stack).

Infix expression evaluation using two stacks.

Flattening an arbitrarily nested list in Python (Python)

2014-10-05T21:44:45-07:00

Python recipe 578948 by Vasudev Ram (algorithm, algorithms, flatten, list, lists, python).

This is a recipe to flatten a Python list which may have nested lists as items within it. It works for lists that have a maximum depth of nesting roughly equal to the recursion depth limit of Python, which is set to 1000 by default, though it can be increased with sys.setrecursionlimit().

Extended Euclidean Algorithm (Python)

2016-03-03T07:12:28-08:00

Python recipe 578631 by Samuel James Erickson (algorithm, common, discrete, divisor, euclid, extended, gcd, greatest, logarithm). Revision 2.

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).

Finding sets in the card game SET! (Python)

2013-04-05T12:49:36-07:00

Python recipe 578508 by Sander Evers (algorithm, optimization, search, setgame). Revision 2.

In the card game SET!, players are shown an array of 12 (or more) symbol cards and try to identify a so-called 3-card set among these cards as quickly as possible.

A card has four attributes (number, shape, color and shading), each of which can take 3 possible values. In a set, for each attribute, all three cards should have either the same value, or the three different values.

This recipe solves the problem of finding all sets within an array of an arbitrary number of cards, showing some clever optimizations and celebrating the clarity of Python in expressing the algorithms.

Eight queen problem (Javascript) (JavaScript)

2013-03-20T19:03:44-07:00

JavaScript recipe 578497 by Thomas Lehmann (algorithm, queen, queens).

Adding this for my old recipe 577438 (in Python).
Use node.js or HTML as execution (see comments in "log" function)

Topological Sort (Python)

2012-09-27T12:21:23-07:00

Python recipe 578272 by Sam Denton (algorithm, sort, sorting, topological, toposort).

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).

Knight's Tour using Warnsdorff Algorithm (Python)

2012-12-17T06:04:19-08:00

Python recipe 578382 by FB36 (algorithm, algorithms, math, mathematics).

Knight's Tour using Warnsdorff Algorithm.

Generating Balanced Parenthesis (Python)

2013-02-14T22:00:22-08:00

Python recipe 578458 by bartender (algorithm).

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:

((())) (()()) (())() ()(()) ()()()

The number of such output ( 5 in above case) is a Catalan Number.

topological sorting again (Python)

2013-03-06T19:21:11-08:00

Python recipe 578406 by yota (algorithm, graph, python3, sort, topological). Revision 9.

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.

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.

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 wikipedia:

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)

Only tested with python3.2, should work with other versions. Be careful, code indented with tabs, since space is evil è_é

Knight's Tour Map using Warnsdorff's Algorithm (Python)

2012-12-18T01:05:51-08:00

Python recipe 578386 by FB36 (algorithm, algorithms, graphics, math, mathematics, pil).

Solves Knight's Tour Problem using Warnsdorff's Algorithm for every square on the chessboard of arbitrary size.

It colors each initial square with a color that depends on the final square coordinates. (This is a method used to create fractals.) Many different formulas maybe used for coloring (based on abs/rel x/y/dist/ang).

Calculating each tour in full creates a highly chaotic image (and takes hours). So I added maxItPercent to cut-off tours earlier. (Using %10 creates an image that has both ordered and chaotic regions.)

Super Simple Sudoku Solver in Python source code (Python)

2012-06-23T14:56:05-07:00

Python recipe 578140 by David Adler (algorithm, python, recursive, recurssion, sodoku, sudoku). Revision 5.

A simple algorithm which uses a recursive function to solve the puzzle.

THE ALGORITHM

The credit for this algorithm must go to Richard Buckland: http://www.youtube.com/watch?v=bjObm0hxIYY&feature=autoplay&list=PL6B940F08B9773B9F&playnext=1

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.

isLegal = does not conflict with any other numbers in the same row, column or square

A-star Shortest Path Algorithm (C++)

2010-12-25T23:36:35-08:00

C++ recipe 577457 by FB36 (algorithm, algorithms, game, graph, graphs, routes). Revision 4.

A-star (A*) is a shortest path algorithm widely used for RTS games, GPS navigation etc.

Genetic Algorithm in Python source code - AI-Junkie tutorial (Python)

2012-06-19T12:59:13-07:00

Python recipe 578128 by David Adler (algorithm, artificial, genetic, network, neural, python). Revision 5.

A simple genetic algorithm program. I followed this tutorial to make the program http://www.ai-junkie.com/ga/intro/gat1.html.

The objective of the code is to evolve a mathematical expression which calculates a user-defined target integer.

KEY:

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.

protein = mathematical expression (this is evaluated from left to right in number + operator blocks of two)

output = output of protein (mathematical expression)

error = inverse of difference between output and target

fitness score = a fraction of sum of of total errors

OTHER:

One-point crossover is used.

I have incorporated elitism 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)

Evolutionary Algorithm (Generation of Prime Numbers) (Python)

2011-11-27T06:45:00-08:00

Python recipe 577964 by Alexander James Wallar (algorithm, example, genetic, genetic_algorithm, genetic_algorithms, list, number, of, prime, primelist, primes, theory).

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.

Parameters:

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

Shannon-Fano Data Compression (Python)

2010-12-18T22:09:40-08:00

Python recipe 577502 by FB36 (algorithm, algorithms, data_compression). Revision 3.

Shannon-Fano Data Compression. It can compress any kind of file up to 4 GB.

(But trying to compress an already compressed file like zip, jpg etc. can produce a (slightly) larger file though. Shannon-Fano is not the best data compression algorithm anyway.)