Heuristic Fuzzy Alchemy

Andy Novocin

Daily Challenge

Multisets are allowed to have repeated elements. A multiset of \(n\) items may thus have fewer than \(n!\) distinct permutations. For example, \(\{1,1,2,2\}\) has only six permutations: \((1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2,1,2,1), (2,2,1,1)\) Design and implement an efficient algorithm for constructing all permutations of a multiset.

Math Problem of day

Is the number 341 550 071 728 321 prime?

Interview Question

Telephone keypads have letters on each numerical key. Write a program that generates all possible words resulting from a given digit sequence (e.g. 145238) into letters.

Final HW is released

Introducing Set Cover:

Given \(S = \{S_1, \dots, S_n\}\) a set of subsets of \(U\) (the universe).

Find the smallest subset \(T \subset S\) such that union of \(T == U\).

Brute Force Tweaking

Pruning your search:

If your answer_so_far isn't valid then backtrack immediately.

Tweaking 2

If you can look ahead and see that no valid future paths are possible then backtrack immediately.


Skiena gives a nice treatment of pruning techniques in his Sudoku solver.

When I started coding Sudoku solving was the first C program I wrote.

A friend gave me advice that I'll never forget:

Good advice

When building a program, exploit what computers are best at (many stupid tasks per second), not what humans are best at (pattern finding, fuzzy thinking).

Artificial Neural Networks

Not as hard as you think.

The goal is to take in a 0-1 array of size \(i\) and spit out a 0-1 array of size \(o\).

Real Neural Nets

Artifical Neural Nets


A neuron will either fire a signal (ON/Yes/True) or it won't (OFF/No/False).

The synapses adjust the chemicals in the area of the neuron and either encourage firing or discourage firing.

If enough encouragement is there the neuron fires.

Artifical Neural Nets

Input, Output

So the input neurons are sensory inputs and they are either on, 1, or off, 0.

The connections will each get a floating point value (typically in \([-1, 1]\)) which we can store in some matrices.

The on neurons add the values to the hidden neurons, if more positive than negative they fire.

Likewise they contribute to the output neurons which decide yes or no each.

Nice resource for learning ANN


Useful for Automatons

Programming Task 4

Genomic Dungeon Rats!

The final version isn't ready just yet (I had to sleep sometime) but you can begin thinking about it.

How it works

Your goal is to give me a genome (280 ascii characters (between 42-122)) which encodes the personality of a champion dungeon rat.

I provide a black-box simulator which takes in a genome and tells you how long that rat survived.

I want to be able to animate the rat's run, so I might stick with Javascript

Genome Encoded Rats

You don't need to know much about the rats but I'm excited

They have 24 input sensors: is there food, obstacle, or a pit in 8 square sets around me.

They make 4 output choices (increase/decrease speed in x/y direction).

The genome encodes all of the weights in the rat's brain (10 hidden neurons).

Dungeon Rat progress so far


Your task

Optimize the rat's genome for longevity using a blackbox evaluator.

You can use Simulated Annealing, Genetic Algorithms, Monte Carlo testing, whatever

Show me how you came up with your genome.

Samples of Genomic Learning

Learning to Walk

GA Walkers

NES learning

NES had very little RAM

When pruning isn't enough

We turn to methods for hunting down a close enough answer.


If I give up on finding the best answer then I need a concept of fitness

Some way to distinguish the quality of wrong answers.


Just guess an answer!

(Not a very good technique)

ICUP Thought challenge

How many possible genome sequences do our rats have?

(280 characters in the genome between value 42 and 122)

Gradient Descent

Hill climbing / Valley Diving

Wherever my guess is, head down or up.

What will go wrong?

Simulated Annealing

SA idea

Try many random values and accept any that improve your solution

"Temperature" will start high and cool over time

While temp is high there is a good chance of jumping to a random spot that does NOT improve your solution

After a while lower the temperature a bit.

If you complete a cycle and stay at the same peak then call it an answer.

Simulated Annealing

More examples

Genetic Algorithms

View each answer as part of a population

Each generation, let the most fit answers "reproduce" mixing the parent characteristics

Have a small probabilty of mutation where parts of the answer are altered

Cull the population pool of the weakest and repeat

Pros and Cons

The fitness function goes a long way in determining the outcome.

Works best when there is a natural dimensionality to the answers.

Not always the right answer (TSP is a notable failure for GA)

Ball Carrying


If the domain allows better inroads then you can make problem specific progress.

SA and GA and even Swarm Optimization are techniques that can apply to many areas

Hence the name Meta-Heuristic

Primality Testing

How long does it take to test whether a number is a prime?

If time

Introduce Knapsack, Bandwidth Reduction, *-Discrepancy