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