Popular recipes tagged "algorithm" but not "mathematics"

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.

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.

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

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 è_é

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

Rsync Algorithm (Python)

2011-01-09T16:32:22-08:00

Python recipe 577518 by Eric Pruitt (algorithm, delta, diff, patch, python3, rsync). Revision 4.

This is a pure Python implementation of the rsync algorithm. 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.

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.

Binary Search Tree (C++)

2011-08-08T00:13:44-07:00

C++ recipe 577828 by sivarama sarma (algorithm, algorithms, datastructures).

Binary Search Tree.

Chess Notation Player (Python)

2011-05-25T18:41:33-07:00

Python recipe 577719 by Stijn de Graaf (algorithm, chess, game, notation, viewer).

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: http://en.wikipedia.org/wiki/Algebraic_chess_notation.

Simple Sudoku (Python)

2011-06-02T14:15:02-07:00

Python recipe 577716 by amir naghavi (algorithm, game, oo, python, random, sudoku). Revision 10.

This is a simple sudoku game.