Top-rated recipes tagged "algorithm"

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.

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.

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.

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

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

SPOJ backup script (Python)

2010-02-09T08:50:44-08:00

Python recipe 577036 by Shashwat Anand (algorithm, algorithms, spoj, tools). Revision 3.

Introduction

At Sphere Online Judge (http://www.spoj.pl) you are given the capability of trying out the challenging problems given. It also gives you the capability of viewing and downloading your own solution.

The tool spojbackup tends to automatically backup all your Accepted submissions and save them on the desired location of your computer. The basic idea is to automate the process which can be used as a backup and an offline reference tool of your own codes.

Features

Resume downloads. spojbackup currently supports resuming of the solutions if internet connection is disrupted
Incremental backup facility it'll not download the code already present on your machine. Only newer code added in your signedlist will be downloaded
User-defined destination all codes are saved at user-defined destination if no option is given by user it saves in the folder from where command is run
Proxy support Proxy support is provided as SPOJ users are generally university students and they are generally behind a proxy and university firewall.

Bugs

In case of finding a bug please drop a mail to the authors. We will try to sort out the problems.

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

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.

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.

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)

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.

converting numbers to their alphabetical style (Python)

2011-03-17T06:57:06-07:00

Python recipe 577607 by amir naghavi (algorithm, recursion, string). Revision 4.

converts numbers to alphabetical numbers

Fibonacci Data Compression (Python)

2011-01-28T04:18:30-08:00

Python recipe 577554 by FB36 (algorithm, algorithms, data_compression).

Data compression via Fibonacci encoding.

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

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]

Fast Running Median using an Indexable Skiplist (Fast version) (Python)

2010-03-03T11:06:29-08:00

Python recipe 577073 by Raymond Hettinger (algorithm, indexable, median, running, skiplist, statistics). Revision 5.

Fast version of r576930 reimplemented using a list of lists instead of a node class.

Simple Permutations (Python)

2010-02-07T06:47:14-08:00

Python recipe 577031 by manchesterboy (algorithm, combinations, permutations). Revision 2.

Given a string of chars and a length, returns permutations of the specified length using the char string given in order. For example, given a string of "01" and a length of 3 returns 000, 001, 010, 011 ... 111

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.

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.