Bak-Sneppen

baksnep_start

Bak-Sneppen, A simplistic model of competitive evolution…

Definition of the Bak-Sneppen model

This problem was brought to my attention by another student working on developing it for a research problem. I thought I’d mock up a parallel version just to play around. Its not necessarily appropriate, but it was the flavor of the month for my hobbies.

The system works as follows:

  1. Create a random environment of unsigned 32-bit integers.
  2. For each element in the environment, give it an index of the element directly less than and greater than or equal to.
  3. Move this structures onto the GPU along with…
  4. A 3 * batchSize list random integers
  5. Now each thread checks if it has a valid less than index, if not, it and its neighbors pop integers off the random list, overwrite their values, record their indexes, and remove themselves from the structure.
  6. Each thread not removed checks if the removed elements are greater than or equal to them, and less than their greater value, if so they re-insert those elements above them.
  7. It does this batchSize times
  8. Then once a batch is done, the GPU starts over

Meanwhile

  • The CPU is updating an array with new random values, and swapping pointers to keep random values fresh.
  • The CPU is copying the recorded changed indices to keep a record of what elements “died”

All together it ends up being pretty darn fast.

baksnep_end

SDPS_Brute

seednum

This is a small console application built to solve the puzzles presented by a fellow student’s mobile math game. It gives you access to 7 basic arithmetic functions and a single digit. The goal is to reach a target value, using only those tools. The secondary goal is to complete the task with the fewest instances of the given digit.

I first solved a few puzzles by hand. With advice by the student (who had played the game more than any sane man should) I started to develop a basic strategy for how to quickly solve puzzles. The functions given are +, -, *, /, ^, square root, and factorial. Two of these take in a single value, square root and factorial. The other five take in two.

For n digits:

I decided to only allow for factorial and square root to be used on the given digit, and build up a set of constants from the 5 possible combinations of these two. Being x, sqrt(x), x!, sqrt(x!), and (sqrt(x))!. I throw out any of the ones resulting in non-integers. So we have a list of n choices from these constants.

Next is the function application and order of operations. I create a binary tree of n-1 digits, initialized so that it is only left descending. This tree represents the order of operations. It uses a solver function recursively downward that ends in the root reaching the statement value. I also create a list of n-1 s choices from the functions between any 2 digits.

We then iterate through every combination of functions and digits, stopping if we reach the target value. If not, we move the left-most leaf of the tree directly right of the leaf directly right of it, and reset the lists to iterate again.

This method is entirely unwieldy, and STILL does not cover the entire search space.

It has a worst case step count of… (25^n)/5 * (2(n-1) choose (n-1))

Dear god why did I do this. Source

Thoughts:

  • If a solving tree member returns a non-integer, quit the solution process and iterate.
  • Some function combinations are useless. Scan for these ( find …*(x/x) structures)
  • Perhaps use an exploratory method using factor similarity as a metric for shortest path.
  • Tree members ALSO need a state, as a factorial/ square root could also be applied to a statement fragment. This is a bit of a problem though as factorial could be applied recursively…
  • Half the order permutations are identical, so after the symmetric case I can stop