Popular recipes tagged "algorithm" but not "algorithms"

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.

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

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

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.

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

interleave bits (aka morton-ize aka z-order curve) (Python)

2011-02-02T12:50:58-08:00

Python recipe 577558 by Romain Dartigues (algorithm, bits, manipulation, mathematical, mathematics).

This recipe let you encode in a single number two or three numbers.

Note: this is only an adaptation of the recipes from Sean Eron Anderson and Fabian “ryg” Giesen; all credits goes to the respective authors.

SMS_Encryption (Python)

2011-03-14T08:26:29-07:00

Python recipe 577606 by amir naghavi (acm, algorithm, encryption).

the answer of an acm problem to further explantion look at source code.

Topological Sort (Python)

2010-09-28T19:22:27-07:00

Python recipe 577413 by Paddy McCarthy (algorithm, sorting, topological).

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

TRAC Interpreter -- Sixties programming language (Python)

2010-08-22T19:05:09-07:00

Python recipe 577366 by Jack Trainor (algorithm, educational, interpreter, language, trac).

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.

TRAC Interpreter - Dragon style (Python)

2010-09-20T00:42:21-07:00

Python recipe 577396 by Jack Trainor (algorithm, educational, interpreter, language, lexical_analyzer, trac).

I've rewritten the TRAC interpreter from Recipe 577366 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).

TRAC Interpreter - Class and Stack version (Python)

2010-09-20T01:16:07-07:00

Python recipe 577397 by Jack Trainor (algorithm, educational, interpreter, language, lexical_analyzer, trac).

This is my third and final version of the Trac Interpreter from Recipe 577366. It processes the character stream into appropriate class objects and stores these objects on a stack.