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

## Sudoku

### 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

## Basics

### 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

## Learning

## 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

### JsFiddle

## 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