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.

dfs and bfs graph traversal (Python)

2013-06-28T09:59:38-07:00

Python recipe 576723 by bruce wernick (algorithm, graph).

Very simple depth first search and breath first graph traversal. This is based on the find_path written by Guido van Rossum.

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)

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.

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 (Python)

2010-12-26T08:31:16-08:00

Python recipe 577519 by FB36 (algorithm, algorithms, graph, routes). Revision 3.

A-star (A*) Shortest Path Algorithm

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-01-26T22:48:06-08:00

C++ recipe 577552 by FB36 (algorithm, algorithms, datastructures).

Binary Search Tree.

Huffman coding, Encoder/Deconder (Python)

2009-01-04T04:11:37-08:00

Python recipe 576603 by Shao-chuan Wang (algorithm, compression, decompression, huffman_code). Revision 2.

Please refer to wikipedia: http://en.wikipedia.org/wiki/Huffman_coding

Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

Huffman Data Compression (C++)

2010-12-01T02:47:09-08:00

C++ recipe 577480 by FB36 (algorithm, algorithms, datastructures, data_compression). Revision 2.

Huffman encoding (data compression). Usage: huffman -i [input file name] -o [output file name] [-e|d]

RC4, ARC4, ARCFOUR algorithm (Python)

2009-05-03T09:45:59-07:00

Python recipe 576736 by Thimo Kraemer (algorithm, encryption, text). Revision 5.

RC4 generates a pseudorandom stream of bits (a keystream) which, for encryption, is combined with the plaintext using bit-wise exclusive-or; decryption is performed the same way (since exclusive-or is a symmetric operation).

(see http://en.wikipedia.org/wiki/RC4)

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

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.

Floyd-Steinberg dithering algorithm (Python)

2009-06-02T01:28:46-07:00

Python recipe 576788 by Alan Holt (algorithm, dithering, floyd_steinberg, image, manipulation).

Floyd-Steinberg dithering is an image dithering algorithm (see http://en.wikipedia.org/wiki/Floyd-Steinberg for more details). While the algorithm is mainly for image manipulation, I use it to create random locations for sensor networt devices.

Dijkstra Shortest Path Algorithm (Python)

2011-10-29T18:46:53-07:00

Python recipe 577506 by FB36 (algorithm, algorithms, graph, routes). Revision 5.

Dijkstra shortest path algorithm.

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

2010-11-14T06:32:53-08:00

C++ recipe 577461 by FB36 (ai, algorithm, algorithms, artificial_intelligence, neural_network). Revision 2.

(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

Find Prime Numbers in python (Python)

2010-06-12T08:22:40-07:00

Python recipe 577259 by Giannis Fysakis (algorithm, algorithms, primality_testing, prime, primes, prime_generator, prime_number). Revision 2.

The algorithm is based on the idea
that the next larger prime after one prime is the sum of the two smaller previous minus three prime numbers back. For the first five prime numbers 2,3,5,7,11 this pattern is not true also it is not true if the number is a composite number (including of course if the number's square root is integer).

Example trying to find the tenth prime

so lets play with numbers 17(minus 3 from Next,position 7), 19(minus 2 from Next,position 8), 23(minus 1 from Next,position 9) and number Next at position 10 :

hmmm ... if we add 19 and 23 we get 42, but 42 minus 17 equals 25 which isn't a prime :(

In order to correct this we assume that 25 is the next prime number ( temporary holding the tenth position) finally to get the real Next prime number we take 23 + 25 = 48 , we subtract 19 and we get 29 which finally it takes the tenth position ( because it deserves it :P)

Longest common subsequence problem solver (Python)

2009-08-06T06:36:56-07:00

Python recipe 576869 by Shao-chuan Wang (algorithm, decorator, lcs, longest_common_subsequence). Revision 2.

Longest common subsequence problem is a good example of dynamic programming, and also has its significance in biological applications.

For more information about LCS, please see: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Also, here, I use a 'cached' decorator to keep core algorithm neat. You can see how great the decorator could be. :)

Also note that, this recipe is just a demonstration of LCS and the usage of a python decorator. However, the memory is not used very efficiently. If the problem is very large-scaled, it may lead to stack overflow or memory error.

So, do not use this recipe to deal with large-scaled problems. ;)

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

Most viewed recipes tagged "algorithm"