text:
Count the number of Hankelable matrices
Background
A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1s. E.g. a 5x5 binary Hankel matrix looks like
a b c d e
b c d e f
c d e f g
d e f g h
e f g h i

where a, b, c, d, e, f, g, h, i are either 0 or 1.
Let's define a matrix M as Hankelable if there is a permutation of the order of rows and columns of M so that M is a Hankel matrix. This means one can apply one permutation to the order of the rows and a possibly different one to the columns.
The Challenge
The challenge is to count how many Hankelable n by n matrices there are for all n up to as large a value as possible.
Output
For each integer n from 1 upwards, output the number of Hankelable n by n matrices with entries which are 0 or 1.
For n = 1,2,3,4,5 the answers should be 2,12,230,12076,1446672. (Thanks to orlp for the code to produce these.)
Time limit
I will run your code on my machine and stop it after 1 minute. The code that outputs the correct answers up to the largest value of n wins. The time limit is for everything from n = 1 to the biggest value of n for which you give an answer.
The winner will be the best answer by the end of Saturday 18 April.
Tie Breaker
In the case of a tie for some maximum n I will time how long it takes to give the outputs up to n+1 and the quickest one wins. In the case that they run in the same time to within a second up to n+1, the first submission wins.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.
My machine
The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor on an Asus M5A78L-M/USB3 Motherboard (Socket AM3+, 8GB DDR3). This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.
Notes
I recommend against iterating over all n by n matrices and trying to detect if each one has the property I describe. First, there are too many and second, there seems to be no quick way to do this detection.
Leading entries so far

n = 8 by Peter Taylor. Java
n = 5 by orlp. Python

I really enjoy the word "Hankelable."

For n=6 the total is 260357434. I think memory pressure is a bigger issue than CPU time.

This is an awesome question. I have been thoroughly nerd-sniped.

Java (n=8)
import java.util.*;
import java.util.concurrent.*;

public class HankelCombinatorics {
    public static final int NUM_THREADS = 8;

    private static final int[] FACT = new int[13];
    static {
        FACT[0] = 1;
        for (int i = 1; i < FACT.length; i++) FACT[i] = i * FACT[i-1];
    }

    public static void main(String[] args) {
        long prevElapsed = 0, start = System.nanoTime();
        for (int i = 1; i < 12; i++) {
            long count = count(i), elapsed = System.nanoTime() - start;
            System.out.format("%d in %dms, total elapsed %dms\n", count, (elapsed - prevElapsed) / 1000000, elapsed / 1000000);
            prevElapsed = elapsed;
        }
    }

    @SuppressWarnings("unchecked")
    private static long count(int n) {
        int[][] perms = new int[FACT[n]][];
        genPermsInner(0, 0, new int[n], perms, 0);

        // We partition by canonical representation of the row sum multiset, discarding any with a density > 50%.
        Map<CanonicalMatrix, Map<CanonicalMatrix, Integer>> part = new HashMap<CanonicalMatrix, Map<CanonicalMatrix, Integer>>();
        for (int m = 0; m < 1 << (2*n-1); m++) {
            int density = 0;
            int[] key = new int[n];
            for (int i = 0; i < n; i++) {
                key[i] = Integer.bitCount((m >> i) & ((1 << n) - 1));
                density += key[i];
            }
            if (2 * density <= n * n) {
                CanonicalMatrix _key = new CanonicalMatrix(key);
                Map<CanonicalMatrix, Integer> map = part.get(_key);
                if (map == null) part.put(_key, map = new HashMap<CanonicalMatrix, Integer>());
                map.put(new CanonicalMatrix(m, perms[0]), m);
            }
        }

        List<Job> jobs = new ArrayList<Job>();
        ExecutorService pool = Executors.newFixedThreadPool(NUM_THREADS);

        for (Map.Entry<CanonicalMatrix, Map<CanonicalMatrix, Integer>> e : part.entrySet()) {
            Job job = new Job(n, perms, e.getKey().sum() << 1 == n * n ? 0 : 1, e.getValue());
            jobs.add(job);
            pool.execute(job);
        }

        pool.shutdown();
        try {
            pool.awaitTermination(1, TimeUnit.DAYS); // i.e. until it's finished - inaccurate results are useless
        }
        catch (InterruptedException ie) {
            throw new IllegalStateException(ie);
        }

        long total = 0;
        for (Job job : jobs) total += job.subtotal;
        return total;
    }

    private static int genPermsInner(int idx, int usedMask, int[] a, int[][] perms, int off) {
        if (idx == a.length) perms[off++] = a.clone();
        else for (int i = 0; i < a.length; i++) {
            int m = 1 << (a[idx] = i);
            if ((usedMask & m) == 0) off = genPermsInner(idx+1, usedMask | m, a, perms, off);
        }
        return off;
    }

    static class Job implements Runnable {
        private volatile long subtotal = 0;
        private final int n;
        private final int[][] perms;
        private final int shift;
        private final Map<CanonicalMatrix, Integer> unseen;

        public Job(int n, int[][] perms, int shift, Map<CanonicalMatrix, Integer> unseen) {
            this.n = n;
            this.perms = perms;
            this.shift = shift;
            this.unseen = unseen;
        }

        public void run() {
            long result = 0;
            int[][] perms = this.perms;
            Map<CanonicalMatrix, Integer> unseen = this.unseen;
            while (!unseen.isEmpty()) {
                int m = unseen.values().iterator().next();
                Set<CanonicalMatrix> equiv = new HashSet<CanonicalMatrix>();
                for (int[] perm : perms) {
                    CanonicalMatrix canonical = new CanonicalMatrix(m, perm);
                    if (equiv.add(canonical)) {
                        result += canonical.weight() << shift;
                        unseen.remove(canonical);
                    }
                }
            }

            subtotal = result;
        }
    }

    static class CanonicalMatrix {
        private final int[] a;
        private final int hash;

        public CanonicalMatrix(int m, int[] r) {
            this(permuteRows(m, r));
        }

        public CanonicalMatrix(int[] a) {
            this.a = a;
            Arrays.sort(a);

            int h = 0;
            for (int i : a) h = h * 37 + i;
            hash = h;
        }

        private static int[] permuteRows(int m, int[] perm) {
            int[] cols = new int[perm.length];
            for (int i = 0; i < perm.length; i++) {
                for (int j = 0; j < cols.length; j++) cols[j] |= ((m >> (perm[i] + j)) & 1L) << i;
            }
            return cols;
        }

        public int sum() {
            int sum = 0;
            for (int i : a) sum += i;
            return sum;
        }

        public int weight() {
            int prev = -1, count = 0, weight = FACT[a.length];
            for (int col : a) {
                if (col == prev) weight /= ++count;
                else {
                    prev = col;
                    count = 1;
                }
            }
            return weight;
        }

        @Override public boolean equals(Object obj) {
            // Deliberately unsuitable for general-purpose use, but helps catch bugs faster.
            CanonicalMatrix that = (CanonicalMatrix)obj;
            for (int i = 0; i < a.length; i++) {
                if (a[i] != that.a[i]) return false;
            }
            return true;
        }

        @Override public int hashCode() {
            return hash;
        }
    }
}

Save as HankelCombinatorics.java, compile as javac HankelCombinatorics.java, run as java -Xmx2G HankelCombinatorics.
With NUM_THREADS = 4 on my quad-core machine it gets 20420819767436 for n=8 in 50 to 55 seconds elapsed, with a fair amount of variability between runs; I expect that it should easily manage the same on your octa-core machine but will take an hour or more to get n=9.
How it works
Given n, there are 2^(2n-1) binary nxn Hankel matrices. The rows can be permuted in n! ways, and the columns in n! ways. All we need to do is to avoid double-counting...
If you calculate the sum of each row, then neither permuting the rows nor permuting the columns changes the multiset of sums. E.g.
0 1 1 0 1
1 1 0 1 0
1 0 1 0 0
0 1 0 0 1
1 0 0 1 0

has row sum multiset {3, 3, 2, 2, 2}, and so do all Hankelable matrices derived from it. This means that we can group the Hankel matrices by these  row sum multisets and then handle each group independently, exploiting multiple processor cores.
There's also an exploitable symmetry: the matrices with more zeroes than ones are in bijection with the matrices with more ones than zeroes.
Double-counting occurs when Hankel matrix M_1 with row permutation r_1 and column permutation c_1 matches Hankel matrix M_2 with row permutation r_2 and column permutation c_2 (with up to two but not all three of M_1 = M_2, r_1 = r_2, c_1 = c_2). The row and column permutations are independent, so if we apply row permutation r_1 to M_1 and row permutation r_2 to M_2, the columns as multisets must be equal. So for each group, I calculate all of the column multisets obtained by applying a row permutation to a matrix in the group. The easy way to get a canonical representation of the multisets is to sort the columns, and that is also useful in the next step.
Having obtained the distinct column multisets, we need to find how many of the n! permutations of each are unique. At this point, double-counting can only occur if a given column multiset has duplicate columns: what we need to do is to count the number of occurrences of each distinct column in the multiset and then calculate the corresponding multinomial coefficient. Since the columns are sorted, it's easy to do the count.
Finally we add them all up.
The asymptotic complexity isn't trivial to calculate to full precision, because we need to make some assumptions about the sets. We evaluate on the order of 2^(2n-2) n! column multisets, taking n^2 ln n time for each (including the sorting); if grouping doesn't take more than a ln n factor, we have time complexity Theta(4^n n! n^2 ln n). But since the exponential factors completely dominate the polynomial ones, it's Theta(4^n n!) = Theta((4n/e)^n).

This is very impressive. Could you say something about the algorithm you have used?

Python2/3
Pretty naive approach, in a slow language:
import itertools

def permute_rows(m):
    for perm in itertools.permutations(m):
        yield perm

def permute_columns(m):
    T = zip(*m)
    for perm in itertools.permutations(T):
        yield zip(*perm)

N = 1
while True:
    base_template = ["abcdefghijklmnopqrstuvwxyz"[i:i+N] for i in range(N)]

    templates = set()
    for c in permute_rows(base_template):
        for m in permute_columns(c):
            templates.add("".join("".join(row) for row in m))

    def possibs(free, templates):
        if free == 2*N - 1:
            return set(int(t, 2) for t in templates)

        s = set()
        for b in "01":
            new_templates = set(t.replace("abcdefghijklmnopqrstuvwxyz"[free], b) for t in templates)
            s |= possibs(free + 1, new_templates)

        return s

    print(len(possibs(0, templates)))
    N += 1

Run by typing python script.py.

You have the language listed as Python 2/3, but for it to work in Python 2, don't you need from __future__ import print_function (or something like that)?

@AlexA. Normally, yes, but not in this case. Consider Python2's behaviour when you type return(1). Now replace return with print :)

Cool! I learn something new everyday. :)

Haskell
import Data.List
import Data.Hashable
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S

main = mapM putStrLn $ map (show.countHankellable) [1..]

a§b=[a!!i|i<-b]

hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
    where
      go _ []     = []
      go s (x:xs) = if x `S.member` s then go s xs
                                    else x : go (S.insert x s) xs

pmap = parMap rseq

makeMatrix :: Int->[Bool]->[[Bool]]
makeMatrix n vars = [vars§[i..i+n-1]|i<-[0..n-1]]

countHankellable :: Int -> Int
countHankellable n = let
    s = permutations [0..n-1]
    conjugates m = concat[permutations[r§q|r<-m]|q<-s]
    variableSets = sequence [[True,False]|x<-[0..2*(n-1)]]
 in
    length.hashNub.concat.pmap (conjugates.makeMatrix n ) $ variableSets

Nowhere near as fast as Peter's - that's a pretty impressive setup he's got there! Now with much more code copied from the internet. Usage:
$ ghc -threaded hankell.hs
$ ./hankell

A Haskell answer is always welcome. Thank you.

@Lembik - how's mine doing on your machine?


text:
Number of unique outputs by substituting variables
Given a set of formulas like this:
bacb
bcab
cbba
abbc

Give an algorithm that finds the number of unique results you can get when each variable is substituted for either "0" or "1" in every formula.
There are (k!)^2 formulas, each with 2k-1 variables and k^2 terms. Express your asymptotics in terms of k.
Fastest algorithm wins. In case of a tie the solution with lower asymptotic memory usage wins. If that's still a tie, first post wins.

For the example above the following results can be acquired by substituting the variables:
1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

So the correct answer is 12. Among others, 1010 can not be made using the above formulas.
I've made  three more tests cases, with respective solutions of 230, 12076 and 1446672.

Clarification: what is k in the question? Is it just some abstract constant?

@isaacg Yes. It's to prevent ties between solutions that are faster for less but larger formulas, for example.

So each letter a,b,... is a variable? And we have always only an uneven number of variables? Doesn't it matter how long the sequence of variables is, and on how many formulas you are given?

@flawr The exact relation between the number of variables, number of terms and number of formulas is given in the question.

Does 'can be' mean that you can get up to $(k!)^2$ formulas or are there exactly $(k!)^2$ formulas? Besides that, do you have any application for an algorithm with those specifications? I'm just asking because the specs seem to be pretty arbitrary.

@flawr The figures are exact, I just meant that it could be for any positive integer $k$. And this is a subproblem I encountered while making an answer to this challenge, that I thought was interesting on its own.

This is a cool challenge. It took me a while to understand that the formulæ represent numbers.

I'm confused. What are the formulas? What are variables and terms?

@xnor In the example above there are 4 formulas (bacb, bcab, cbba, abbc). The first formula (bacb) has 4 terms, in order: b, a, c, b. All formulas have 3 variables, a, b, and c.

@orlp I see now, thanks. I believe counting 3-colorings reduces to this. So it's #P-hard. There won't be a polynomial time solution, thought different exponential ones can still compete.

Mathematica, O(k^2(k!)^2) time
Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Hopefully I calculated the time complexity correctly. Input is a list of formulas such as {"bacb","bcab","cbba","abbc"}. Runs in less than 30 seconds for every test case on my machine, but who cares about absolute times?
Explanation:

First off, the & at the end makes it a pure function, with # referring to the first argument, #2 being the second argument, etc.
Length[*..*] takes the length of the list contained inside it.
Union@@(*..*) takes the contained list and supplies it as the arguments for Union, which returns a list of the unique elements in any of its arguments.
*..*&/@# takes a pure function and maps it over the list of formulas, so that {a,b,c} becomes {f[a],f[b],f[c]}. Note that in nested pure functions, #n refers to its innermost arguments.
Fold[*..*&,#,*..*] takes a accumulator function, starting value, and list, and returns f[f[...[f[starting value,l_1],l_2],...],l_n].
Union[Characters[#]] takes all the characters in the current formula and gets all the unique elements, giving us the variables.
Flatten[*..*] flattens its argument, so that {{{a},b},{{c,{d}}}} becomes {a,b,c,d}.
{*..*,*..*} is simply a way to combine the two results using the above Flatten.
StringReplace[#,#2->"0/1"] takes the previous result and returns it with the current variable replaced with either 0 or 1.

Why are you using k as the variable in your time? Still, factorial time! Phew!

The op said: "Express your asymptotics in terms of k." Also, I had to do a GeneralUtilities\Benchmark` for each method used.

Care to add a plain english description of your algorithm? I'm unfamiliar with Mathematica, so I can't verify your solution.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
King of the Hill: Robot Battle
Your task here is to write an AI for a simple robot battle. The class to be implemented is provided at the bottom of this post, and source of the controller can be found here.
Requirements

Write a class which implements the abstract Bot class, provided at the bottom of this post
You must provide a 0-argument constructor, this must change the value of the Name field, but may not change any other inherited fields
Outside of the constructor, you may not change any of the inherited fields in any way
Your action method should, when called (it will be called once per turn cycle, with a copy of the 64 by 64 map as its argument), return one of the Action enum fields:

UP  to move up (towards y=0)
DOWN to move down
LEFT to move left (towards x=0)
RIGHT to move right
MINE to plant a mine and then move a random direction
PASS to pass

Within the passed map, 0 represents an empty cell, -1 represents a mined cell, and anything else denotes a cell occupied by a bot (each bot will be represented by its unique bot_id, you can get your bot's id by calling this.id())
A bot is eliminated in any of the following situations:

It moves out of the map
It moves into a cell occupied by a mine
Another bot moves into the cell it currently occupies
Its action method takes more than 50ms to respond
Its action method throws any exception that is not caught within its own bounds

To win
Have your bot be the last bot standing!
Additional Rules
The round is not allowed to last more than 1,000 turn cycles. If, after the 1,000th turn cycle, more than one bot is still standing, all of the surviving bots are considered to have tied that round.
Each time a new bot is submitted, it will, as soon as possible, be pitted in two two-bot, three three-bot, and three-four bot rounds; each time against randomly selected opponents.
Scoring
total score=1000*(wins+(1/3) ties - (1/12) losses)/roundsPlayed
The exceptions to this are that any bot that has played at least one round that it didn't lose is guaranteed at least one point, and no bot may have a negative score.
The class to be implemented:

import java.util.*;

public abstract class Bot {
    public static enum Action{
        UP,DOWN,LEFT,RIGHT,MINE,PASS;
    }
    public static final class Position{
        public int x;
        public int y;
        public String toString(){
            return "("+x+","+y+")";
        }
        public double distance(Position p){
            int dx=p.x-this.x;
            int dy=p.y-this.y;
            return Math.sqrt(dx*dx+dy*dy);
        }
        public Position(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public String toString(){return name;}
    public Position p;
    public String name="";
    public abstract Action action(int[][] map);
    private int bot_id;
    public final int id(){return bot_id;}
    public final void register(List<Bot> a){
        a.add(this);
        bot_id=a.size();
    }
}

Leaderboard
The full match log may be read here

ProtectiveBot (6 wins, 6 ties, 1 loss)- 609 points
Albert (2 wins, 8 ties, 0 losses)- 467 points
Frozen (1 win, 8 ties, 0 losses)- 407 points
Cocoon (1 win, 3 ties, 3 losses)-250 points
Wanderlust (0 wins, 3 ties, 5 losses)- 73 points
MineThenBoom (0 wins, 2 ties, 11 losses)- 1 point
PatientBot (0 wins, 0 ties, 13 losses)- 0 points

Sample Bots
Simple Pathfinder: http://pastebin.com/raw.php?i=aNBf00VU
RandomBot: http://pastebin.com/raw.php?i=VD8iGaHC
Minelayer: http://pastebin.com/raw.php?i=sMN1zSa0

Maybe you could remove the Java restriction by changing the output to a letter (i.e, UDLRMP for up, down, left, right, mine, pass) and accepting that output as input to the controller. Only the first byte is read, and anything other than one of those six commands is counted as pass. (Just an idea, personally, I've never coded a KOTH controller.)

The return value WAS a string, before I changed it to an Enum at coredump's suggestion.  2.Also, that would mean a complete restructure of the controller, and would also be harder to set up

@SuperJedi224 OK, then. Where will the results of the matches be placed, or is the leaderboard all we will see?

Why does your position class use the euclidean metric? Because of the way movement works, it would make much more sense to have the distance method return the taxicab distance rather than the euclidean distance.

I want to let you know I've updated my bot (apparently it always laid down mines). Also, can the logs say whose mine blows up bot X?

No, not at present.

@ASCIIThenANSI a while back I coded a wrapper for a java-only contest, so other entrants could just output to stdout. It wasn't very popuar :(

I think you need to adjust the tournament to run a lot more rounds. This is a contest with a high standard deviation of results.
Also, every bot should be in the same number of rounds, and the same number of 3 and 4 bot rounds, to keep it fair.

Is that better?

How do I use the controller? I would like to test my bot before submitting it.

I just run it from Eclipse usually. The source code for the controller does indicate which part of it to edit.

You'll still need a lot more competitions. The start location is random, and 9 bots currently competing (3 samples, 6 answers), so for a given bot in a two-bot battle, there are (64 * 64) positions it could start, (64 * 64 -1) positions its opponent could start, and 8 possible opponents, meaning there are 134184960 possible battles. Bot score is based on only 2 of them.

How to split the bots up for matches is a complicated question, but however you do that, I think each bot should be playing in something like 100 matches, not 3-6.

Yes, but where do I put the bots, the class Bot, etc.? I tried stuffing it all into one file, and it didn't work. So how do I split it up?

Each class definition goes to a seperate .java file with the same name as the class

I think there is something wrong with how mines are represented. I used some code from the Minelayer, and checked to make sure it would never walk into a mine, and it did anyway. I am assuming mines are represented by -1.

@ASCIIThenANSI They are. Honestly, I'm not sure where the problem is, but I'll see if I can figure it out.

@SuperJedi224 Maybe it's storing mine coordinates wrong, for instance, the map that the bot has isn't the same controller has.

@SuperJedi224 I believe I've found the problem. Around line 54 of you're controller, you write Bot.Action s. I assume this sets the bot's action to s. But shouldn't that be s = Bot.Action(map), to set the bot's action (given the map as an argument) to s?

No, that line means that variable s has type Bot.Action. The line that gets its value is a few lines down.

Never mind looking for the bug, there was a typo in my bot.

ProtectiveBot
A bunch of ideas rolled together to form something. There are a number of states that it can enter. Firstly, if there is no-one around them, it will build itself a cocoon which is just about indestructible, and sit in it for a while, killing anyone it can.
If there is someone close during startup, there is less then 200 turns left, or there is only one enemy bot remaining, the bot will enter a aggressive mode, which is essentially an enhanced pathfinder, attempting to trick its opponents. This mode uses a flood style pathfinding system at close range, and the same technique in the provided pathfinding example at long range.
If there are multiple instances of this bot in game, the bots will refrain from killing each other until the end.
Its big as well, weighing in at 527 741 lines. Compiling against Java 8. Also, have a graphic renderer of the battle system: https://github.com/j-selby/RobotBattleController

I've reached the limit for how big these posts can be, see bot src at
  https://github.com/j-selby/RobotBattleController/blob/master/src/main/java/ProtectiveBot.java.
  Sorry...

Rev 3:

Threaded pathfinding. No more timeouts!
Detection of stalemates. TODO: Do something about them.
Full A* pathfinding. No more dumb stuff.
Checks OTHER bots positions for unfair play (trapping themselves in completely).

Rev 2:

Stopped bot being killed at corners
Smarter building logic
Will never do any move that could endanger us, excluding against other instances of ProtectiveBot.

Technically speaking, you should restructure it so the status handling in the name is done by overwriting the toString method, not by actually changing the name field.

Your bot is still doing REALLY well though. While it does seem to have a longer response time than the other bots, it has still been within the 50ms limit with room to spare so far.

@SuperJedi224 Yeah, overriding toString was something I should have done earlier. Its slower because my flood pathfinding is awful (I need to implement proper A* style stuff, and then we should be good to go), especially when there are other bots trapped. I just noticed that this bot is weak to approaching other robots diagonally, so thats another thing to change.

On the last round, it timed out on turn 788. Just thought you should know that.

Hummmm - yeah, I've been getting that in a few instances as well. Previously, it just froze the program though, so theres an improvement there.

@SuperJedi224 These battles now always seem to end in stalemates. Could I suggest a 2 turn move to disarm mines or something to break others fortresses?

@selby-That or something similar would probably be a good idea.

Frozen
After analyzing how the controller worked, I determined the only way to lose is to move. Therefore, this robot stays in place unless absolutely necessary.
public class Frozen extends Bot{
        public Frozen(){
            this.name="Frozen";
        }
        public Action action(int[][] map) {
            if (p.x > 0 && map[p.x-1][p.y] > 0) return Action.LEFT;
            if (p.x < map.length-1 && map[p.x+1][p.y] > 0) return Action.RIGHT;
            if (p.y > 0 && map[p.x][p.y-1] > 0) return Action.UP;
            if (p.y < map.length-1 && map[p.x][p.y+1] > 0) return Action.DOWN;
            return Action.PASS;
        }
}

I was going to argue with you that there are other ways to die, but considering your leaderboard position I'd say you have the right of it.

The other way to die is to have a bot move onto me, so Frozen moves onto them first. It's biggest flaw is that other bots have more wins when not pitted against Frozen, giving them a better score.

Wanderlust
I join the competetion with a bot called Wanderlust! Its algorithm is actually pretty straightforward. While it's trying to avoid mines and not running off the map, it's randomly spraying mines around. If an enemy bot would come closer, though, it scurries off in the opposite direction.
Wanderlust's a decent bot, but just doesn't cut it when there are A* algorithm bots on the field. You can see it running away while the enemy bot is figuring out how to get closer, but eventually it dies. (Unless those bots get trapped of course, which then simply results in a tie.)
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Wanderlust extends Bot {

private static final double NEAR_ENEMY_RUN_DISTANCE = 12;
private static final double NEAR_ENEMY_PASS_DISTANCE = 2.5;
private static final int SAFE_NUMBER_OF_MINES = 0;
private Random random;

public Wanderlust() {
    this.name = "Wanderlust";
    this.random = new Random(System.currentTimeMillis());
}

@Override
public Action action(int[][] map) {

    List<Action> actions = new ArrayList<Action>();
    List<Position> enemyPositions = mapEnemyPositions(map);
    Position nearestBotPosition = getNearestBotPosition(enemyPositions);
    Action action = Action.PASS;

    if (nearestBotPosition != null && nearestBotPosition.distance(this.p) < NEAR_ENEMY_RUN_DISTANCE) {
        // Run! Can't risk to drop a mine because of the random movement afterwards.
        // So check where the enemy is and run the opposite way!
        // This is all good unless the enemy is reaaaally close. In that case, we're just struck with fear and stand still.

        if (nearestBotPosition.distance(this.p) < NEAR_ENEMY_PASS_DISTANCE) {
            return Action.PASS;
        }

        int dx = this.p.x - nearestBotPosition.x;
        int dy = this.p.y - nearestBotPosition.y;

        Action horizontalAction = dx < 0 ? Action.LEFT : Action.RIGHT;
        Action verticalAction = dy < 0 ? Action.UP : Action.DOWN;

        // Is the enemy closer to me on the x-axis, or the y-axis?
        if (Math.abs(dx) < Math.abs(dy)) {
            // OK, which way do we run away from the enemy? Left or right?
            // And if we can't run left or right, we should think about a back-up plan: moving vertically.
            Action primaryAction = dx < 0 ? Action.LEFT : Action.RIGHT;
            actions.add(primaryAction);
            actions.add(verticalAction);
            action = getValidMove(actions, true, map);
        } else {
            // OK, which way do we run away from the enemy? Up or down?
            // And if we can't run up or down, we should think about a back-up plan: moving horizontally.
            Action primaryAction = dy < 0 ? Action.UP : Action.DOWN;
            actions.add(primaryAction);
            actions.add(horizontalAction);
            action = getValidMove(actions, true, map);
        }
    } else {
        // Just casual strolling. Hey, perhaps dropping a mine? #casualThings
        actions.add(Action.LEFT);
        actions.add(Action.RIGHT);
        actions.add(Action.UP);
        actions.add(Action.DOWN);
        actions.add(Action.MINE);

        if (this.p.x == 0 || this.p.x == 63 || this.p.y == 0 || this.p.y == 63 || getNumberOfMinesAroundPosition(this.p, map) > SAFE_NUMBER_OF_MINES) {
            actions.remove(Action.MINE);
        }

        action = getValidMove(actions, false, map);
    }

    return action;
}

private Action getValidMove(List<Action> actions, boolean preserveOrder, int[][] map) {

    List<Action> validMoves = new ArrayList<Action>();

    for (Action action : actions) {
        if (action == Action.LEFT && this.p.x > 0 && map[this.p.x-1][this.p.y] >= 0) {
            validMoves.add(Action.LEFT);
        }

        if (action == Action.RIGHT && this.p.x < 63 && map[this.p.x+1][this.p.y] >= 0) {
            validMoves.add(Action.RIGHT);
        }

        if (action == Action.UP && this.p.y > 0 && map[this.p.x][this.p.y-1] >= 0) {
            validMoves.add(Action.UP);
        }

        if (action == Action.DOWN && this.p.y < 63 && map[this.p.x][this.p.y+1] >= 0) {
            validMoves.add(Action.DOWN);
        }

        if (action == Action.MINE) {
            validMoves.add(Action.MINE);
        }
    }

    if (validMoves.isEmpty()) {
        return Action.PASS;
    }

    return preserveOrder ? validMoves.get(0) : validMoves.get(random.nextInt(validMoves.size()));
}

private int getNumberOfMinesAroundPosition(Position position, int[][] map) {
    int count = 0;

    if (position.x > 0 && map[position.x-1][position.y] == -1) {
        count++;
    }

    if (position.x < 63 && map[position.x+1][position.y] == -1) {
        count++;
    }

    if (position.y > 0 && map[position.x][position.y-1] == -1) {
        count++;
    }

    if (position.y < 63 && map[position.x][position.y+1] == -1) {
        count++;
    }

    return count;
}

private Position getNearestBotPosition(List<Position> enemyPositions) {
    Position botPosition = null;
    double distance = Double.MAX_VALUE;

    for (Position position : enemyPositions) {
        double botDistance = position.distance(this.p);
        if (botDistance <= distance) {
            distance = botDistance;
            botPosition = position;
        }
    }

    return botPosition;
}

private List<Position> mapEnemyPositions(int[][] map) {

    List<Position> enemyPositions = new ArrayList<Position>();

    for (int yy = 0; yy < 63; yy++) {
        for (int xx = 0; xx < 63; xx++) {
            if (map[xx][yy] > 0 && map[xx][yy] != id()) {
                enemyPositions.add(new Position(xx, yy));
            }
        }
    }

    return enemyPositions;
}
}

Also, there's a small bug present in the controller, I think.
s = (new Bot.Action[]{Bot.Action.DOWN, Bot.Action.LEFT, Bot.Action.RIGHT, Bot.Action.UP})[r.nextInt(2)];
Shouldn't that 2 be changed into a 4? Because right now, after placing a mine you either go down or left. Never right or up, which makes sense because of the output of r.nextInt(2).

There appears to be a problem - a curly brace is left at the bottom of the post.

@ASCIIThenANSI Indeed, fixed that! :)

PatientBot
Super simple bot that puts down a defensive wall and then just waits. (I will probably write a more serious solution later, but this will do for now.)
public class PatientBot extends Bot{
    public PatientBot(){
        name="PatientBot";
    }
    int turn = 0;
    public Action action(int[][] map){
        switch(turn++){
        case 0: return Action.UP;
        case 1: return Action.MINE;
        case 2: return Action.LEFT;
        case 3: return Action.DOWN;
        case 4: return Action.MINE;
        case 5: return Action.DOWN;
        case 6: return Action.RIGHT;
        case 7: return Action.MINE;
        case 8: return Action.RIGHT;
        case 9: return Action.UP;
        case 10: return Action.MINE;
        default: return Action.PASS;
        }
    }
}

Oh, whoops. I missed the part about MINE moving you in a random direction. I'll fix it later.

Well, here's another Simple Pathfinder variant I wrote, and I decided... why not enter it this time?
Albert

import java.util.*;

public class Albert extends Bot{
    private Random r=new Random();
    public Albert(){
        this.name="Albert";
    }
    private int countMines(int[][] map,Position p){
        int mines=0;
        if(p.y==63||map[p.x][p.y+1]==-1)mines++;
        if(p.y==0||map[p.x][p.y-1]==-1)mines++;
        if(p.x==0||map[p.x-1][p.y]==-1)mines++;
        if(p.x==63||map[p.x+1][p.y]==-1)mines++;
        return mines;
    }
    @Override
    public Action action(int[][] map) {
        List<Position> enemies=new ArrayList<Position>();
        for(int x=1;x<map.length;x++){
            for(int y=1;y<map[x].length;y++){
                if(map[x][y]!=0&↦[x][y]!=this.id()&↦[x][y]!=-1){
                    enemies.add(new Position(x,y));
                }
            }
        }
        double d=200;
        Position x=null;
        for(Position pos:enemies){
            if(p.distance(pos)<d){
                x=pos;
                d=p.distance(pos);
            }
        }
        if(countMines(map,p)==0&&r.nextDouble()<0.5&&d>2.01)return Action.MINE;
        if(d>1.03&&d<3)return Action.PASS;
        if(x==null)return Action.PASS;
        if(x.x<p.x&↦[p.x-1][p.y]!=-1&&countMines(map,new Position(p.x-1,p.y))<2&&r.nextDouble()<0.8)return Action.LEFT;
        if(x.x>p.x&↦[p.x+1][p.y]!=-1&&countMines(map,new Position(p.x+1,p.y))<2&&r.nextDouble()<0.8)return Action.RIGHT;
        if(x.y>p.y&↦[p.x][p.y+1]!=-1&&countMines(map,new Position(p.x,p.y+1))<2&&r.nextDouble()<0.8)return Action.DOWN;
        if(x.y<p.y&↦[p.x][p.y-1]!=-1&&countMines(map,new Position(p.x,p.y-1))<2&&r.nextDouble()<0.8)return Action.UP;
        List<Action> v=new ArrayList<Action>();
        if(p.y>0&↦[p.x][p.y-1]!=-1&&countMines(map,new Position(p.x,p.y-1))<3)v.add(Action.UP);
        if(p.y<63&↦[p.x][p.y+1]!=-1&&countMines(map,new Position(p.x,p.y+1))<3)v.add(Action.DOWN);
        if(p.x>0&↦[p.x-1][p.y]!=-1&&countMines(map,new Position(p.x-1,p.y))<3)v.add(Action.LEFT);
        if(p.x<63&↦[p.x+1][p.y]!=-1&&countMines(map,new Position(p.x+1,p.y))<3)v.add(Action.RIGHT);
        v.add(Action.PASS);
        return v.get((new Random()).nextInt(v.size()));
    }
}

Cocoon
I borrowed a bit of utility code from some other bots. The basic strategy here is to get into a safe spot. To accomplish that, I try to lay mines in spots likely to bump me into safe spots. Nearby goals are preferred over distant goals. Absolutely nothing is done about other bots. This bot can usually build a safe spot in a few dozen turns after laying down a checkerboard of failures, so it will at least tie with other bots that can't seek it out and kill it that fast. A bit of code to avoid or kill other bots would improve that scenario.
import java.awt.*;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class CocoonBot extends Bot{
    private static final int Y = 64, X = 64;
    public CocoonBot() {
        this.name="Cocoon";
    }

    private int neighborMines(int[][] map, Point p){
        int mines=0;
        if (p.y>=Y-1||map[p.x][p.y+1]==-1) mines++;
        if (p.y<=  0||map[p.x][p.y-1]==-1) mines++;
        if (p.x>=X-1||map[p.x+1][p.y]==-1) mines++;
        if (p.x<=  0||map[p.x-1][p.y]==-1) mines++;
        return mines;
    }

    @Override
    public Action action(int[][] map) {

        Point firstPoint = new Point(p.x, p.y);
        if ( neighborMines(map,firstPoint) == 4 ) {
            return Action.PASS; // we've built a cocoon and are safe
        }

        // calculate how many mines surround each point of the map, 0-4
        Map<Point, Integer> safety = new HashMap<>();
        for(int x=0; x<X; x++) {
            for(int y=0; y<Y; y++) {
                //TODO: teach the bot that it won't ever lay mines on the edge or adjacent to other mines
                //      so effective safety is 0 if getting to 3 requires one of those actions
                Point p = new Point(x,y);
                int s = neighborMines(map,p);
                safety.put(p,s);
            }
        }

        // flood fill the map to find travel paths and distances from the current square to each other non-mine square
        LinkedBlockingQueue<Point> frontier = new LinkedBlockingQueue<>();
        Map<Point, Point> came_from = new HashMap<>();
        Map<Point, Integer> distance = new HashMap<>();
        frontier.add(firstPoint);
        came_from.put(firstPoint, new Point(-1, -1));
        distance.put(firstPoint,0);
        Point current;
        while((current = frontier.poll()) != null) {
            // TODO: bail here for squares too far away to be worth considering
            for(int d=0; d<4; d++) {
                int dx = d<2?(d*2-1):0; //-1 +1  0  0
                int dy = d<2?0:(d*2-5); // 0  0 -1 +1
                if (current.y+dy<Y && current.y+dy>=0 && current.x+dx<X && current.x+dx>=0) {
                    if (map[current.x+dx][current.y+dy] != -1) {
                        Point next = new Point(current.x+dx, current.y+dy);
                        if(!distance.containsKey(next)) {
                            frontier.add(next);
                            came_from.put(next, current);
                            distance.put(next,distance.get(current)+1);
                        }
                    }
                }
            }
        }

        // calculate the safety of where we might end up after dropping a mine
        // weighted towards safer spaces, we really want to end up in space that's already safety=3
        Map<Point, Integer> safety2 = new HashMap<>();
        for(int x=0; x<X; x++) {
            for(int y=0; y<Y; y++) {
                int s = 0;
                for(int d=0; d<4; d++) {
                    int dx = d<2?(d*2-1):0; //-1 +1  0  0
                    int dy = d<2?0:(d*2-5); // 0  0 -1 +1
                    Point p = new Point(x+dx,y+dy);
                    if ( x+dx<0||x+dx>=X||y+dy<0||y+dy>=Y || map[x+dx][y+dy]==-1 ) {
                        // never risk moving into a mine or off the map!
                        s = -999;
                        break;
                    } else if ( safety.containsKey(p) ) {
                        // safety 3 is great
                        // safety 2 is ok
                        // safety 1 is better than nothing
                        s += safety.get(p)>2?12:safety.get(p)>1?3:safety.get(p); // magic numbers!
                    }
                }
                Point p = new Point(x,y);
                safety2.put(p,s);
            }
        }

        // find the safest/closest point
        Point bestpoint = firstPoint;
        double bestscore = safety2.get(firstPoint)+0.1;
        distance.remove(firstPoint);
        for (Map.Entry<Point,Integer> pd : distance.entrySet()) {
            Point p = pd.getKey();
            double score = safety2.get(p)/Math.pow(pd.getValue(),0.8); // magic number!
            if(score > bestscore) {
                bestscore = score;
                bestpoint = p;
            } else if (score == bestscore) {
                if ( (bestpoint.x-X/2)*(bestpoint.x-X/2)+(bestpoint.y-Y/2)*(bestpoint.y-Y/2) >
                     (p.x-X/2)*(p.x-X/2)+(p.y-Y/2)*(p.y-Y/2) ) {
                    // aim for the middle, less wasted time at edges
                    bestscore = score;
                    bestpoint = p;
                }
            }
        }

        // we're in the right spot, place a mine and hope for a good random bump
        if(bestpoint == firstPoint) {
            return Action.MINE;
        }

        // walk back up came_from to figure out which way to step to get to bestpoint
        while(came_from.get(bestpoint) != firstPoint) {
            bestpoint = came_from.get(bestpoint);
        }
        if ( bestpoint.x > firstPoint.x ) {
            return Action.RIGHT;
        }
        if ( bestpoint.x < firstPoint.x ) {
            return Action.LEFT;
        }
        if ( bestpoint.y > firstPoint.y ) {
            return Action.DOWN;
        }
        if ( bestpoint.y < firstPoint.y ) {
            return Action.UP;
        }

        // should never happen
        return Action.MINE;
    }

}

On the two four-bot rounds your bot was just in, it timed out on turn 1. That doesn't seem to happen when there are fewer bots though.

That's really weird, since it doesn't do anything with other bots at all.

MineThenBoom
A modified version of the pathfinder.His priorities are crush, mine, leave, sit. Yeah, the guy's a little crazy.
Updates to this bot may be given as I find new strategies. Please notify me if something goes wrong.
import java.util.*;

public class MineThenBoom extends Bot{
    public MineThenBoom() {
        this.name="MineThenBoom";
    }
    public Action action(int[][] map) {
        List<Position> enemies=new ArrayList<Position>();
        for(int x=1;x<map.length;x++){
            for(int y=1;y<map[x].length;y++){
                if(map[x][y]!=0&&map[x][y]!=this.id()&&map[x][y]!=-1){
                    enemies.add(new Position(x,y));
                }
            }
        }
        double d=200;
        Position x=null;
        for(Position pos:enemies){
            if(p.distance(pos)<d){
                x=pos;
                d=p.distance(pos);
            }
        }
    // initialize checking for walls
    boolean can_move_left = p.x != 0;
    boolean can_move_right = p.x != 63;
    boolean can_move_up = p.y != 0;
    boolean can_move_down = p.y != 63;
    // Check if there's anyone nearby to crush, if it won't put us in danger.
        if(x.x<p.x&&map[p.x-1][p.y]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
       if(no_one_around)return Action.LEFT;
    }
        if(x.x>p.x&&map[p.x+1][p.y]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.RIGHT;
    }
        if(x.y>p.y&&map[p.x][p.y+1]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.DOWN;
    }
        if(x.y<p.y&&map[p.x][p.y-1]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1;
       if(no_one_around)return Action.UP;
    }
    // If we've come this far, it means no one is crushable. Lay a mine, but only if we're ABSOLUTELY safe.
    boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
    boolean not_walking_into_mine = map[p.x+1][p.y] == 0 && map[p.x-1][p.y] == 0 && map[p.x][p.y-1] == 0 && map[p.x][p.y+1] == 0;
    boolean not_walking_near_danger = map[p.x+2][p.y] < 1 && map[p.x-2][p.y] < 1 && map[p.x][p.y+2] < 1 && map[p.x][p.y-2] < 1;
    if(no_one_around && not_walking_into_mine && not_walking_near_danger)return Action.MINE;
    // OK, let's take a little walk.
        if(x.x<p.x&&map[p.x-1][p.y]!=-1) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
       if(no_one_around)return Action.LEFT;
    }
        if(x.x>p.x&&map[p.x+1][p.y]!=-1) {
       boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.RIGHT;
    }
        if(x.y>p.y&&map[p.x][p.y+1]!=-1) {
       boolean no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.DOWN;
    }
        if(x.y<p.y&&map[p.x][p.y-1]!=-1) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1;
       if(no_one_around)return Action.UP;
    }
    // We clearly are pinned down by some number of players on one or more edges. Let's make our way out of here!
    no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1 && map[p.x-2][p.y] < 1 && map[p.x-1][p.y] == 0 && x.x<p.x;
    if(no_one_around)return Action.LEFT;
    no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x+2][p.y] < 1 && map[p.x+1][p.y] == 0 && x.x>p.x;
    if(no_one_around)return Action.RIGHT;
    no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1 && map[p.x][p.y-2] < 1 && map[p.x][p.y-1] == 0 && x.y<p.y;
    if(no_one_around)return Action.DOWN;
    no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x][p.y+2] < 1 && map[p.x][p.y+1] == 0 && x.y>p.y;
    if(no_one_around)return Action.UP;
    // Well then. We can't crush, lay a mine, or escape.
    // We are most likely near a player who, if they move, will either no longer be a threat or we can crush.
    // If we are somehow surrounded by mines, we're safe anyways.
    return Action.PASS;

    }
}

CHANGES

Fixed bot so it wouldn't always lay mines, and won't be crushed too easily.
Fixed severe logic flaws in bot, as well as minor tune-ups.
Once again, rewrote all the logic.
v1.0: Added code to try to move around a little, see if we can force other bots like us to move.

Thanks to SuperJedi224 for helping me with my code.

What you could do (if not already) is only have your bot place a mine if there are none it could randomly move onto after doing so.

There were some minor syntax errors (which I just fixed for you), also, when I tested the fixed version against the Minelayer, there was an IndexOutOfBounds exception on line 28 of your bot.

@SuperJedi224 OK, should be fixed. It clamps it to 0 and 63 as the edges. If there are different edge measures, or variables for these edges, please let me know.

@theonlygusti The code already accounts for mines, and tries to avoid them. It also places mines when people are nearby (to increase its chance of winning.)

min and max are static methods of the Math class, not globals. I'll fix that for you.

@SuperJedi224 Thanks for your help. I look forward to seeing some good entries in this competition!

Your missing a few semicolons. It won't let me fix it because it says it's too minor a change.

@SuperJedi224 Thanks for pointing that out. This new bot should work much better. You can also use code (one blank line and then 4 spaces indentation) for a leaderboard. I can suggest that in an edit, if you'd like.

You have some duplicate variable declarations. Here's your code again with that problem fixed: http://pastebin.com/raw.php?i=rRFZHxmP

I'm seeing a few logical errors with your bot. x==0 is a valid location, but you start enemy search with x==1. For the nearby-crush-tests, a copy-paste error causes the !=0 part to check the wrong place on the latter 3 tests. I suspect that will help your bot not suicide as much.

@Wasmoo OK, thanks for the help.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Generate net puzzles
An acyclical grid  is a mapping of an acyclical graph (that is, a tree) where each node has no more than four edges onto a toroidal rectangular grid such that each cell of the grid is occupied by a node. Here is an example of an acyclical grid:
┴─┐╵╵│└┘└╴╶┴┬
╴╷╵┌┐│╷┌┬┐╶┐├
╷│╷╵│├┘│╵└╴│╵
┘└┴┐│└┬┤┌─┬┴─
╷╶─┤│╷╵├┤╶┘╶┐
│╶┐└┤└┬┤╵╷╶─┤
┤╷└─┴┬┤└┐└┬┬┴
│├──┐│├╴├─┤├╴
┘└┐┌┴┤└┐├╴╵╵┌
┌┬┘╵┌┴┐╵└─┐╶┘
┤└─┐│╷│┌┬╴╵╷╶

Some browser fonts have trouble rendering this in a properly monospaced way. If the grid looks off, please copy-paste it into a text editor of your choice.
Notice that this grid is toroidal: the left and right, as well as the top and bottom are connected preserving the axis you are moving along. For example, if you move left in the third row you eventually end up on the right of the third row and vice versa.
This grid is composed of box-drawing characters which fall into four classes:

The characters ╵ , ╶, ╷, and ╴ denote leaves (nodes with one edge)
The characters │ and ─ denote nodes with two edges in a collinear arrangement
The characters ┴, ├, ┬, and ┤ denote nodes with three edges
The characters └, ┌, ┐, and ┘ denote nodes with two edges in a perpendicular arrangement

The characteristic matrix of an acyclical grid is a matrix comprising for each cell in the acyclical grid the class of the node positioned there. For instance, the characteristic matrix of the aforementioned grid is this:
3241124441133
1114424232123
1211234214121
4434243342332
1123211331414
2144343311123
3142333444333
2322423131331
4444334431114
4341434142414
3424212431111

A net puzzle is an n × m matrix of integers in the range from 1 to 4 such that it is the characteristic matrix of exactly one acyclical grid.
If you want to gain an intuitive understanding about net puzzles, you can play net from Simon Tatham's puzzle collection. Make sure that “wrapping” and “ensure unique solution” are both checked and that “barrier probability” is set to 0.
The challenge
Write a function or program that given two integers n and m in the range from 3 to 1023 generates a net puzzle of dimension n × m. You may optionally receive a third integer p in the range from 1 to 1023.
If you implement the variant with two arguments (the non-deterministic variant), then your submission shall with great probability return a different puzzle each time it is called. If you implement the variant with three arguments (the deterministic variant), then the set of puzzles generated for all p for a given pair (n, m) shall contain at least four different puzzles for each pair (n, m).
There are no further restrictions with respect to input and output.
Scoring
This challenge is code golf. The solution with the least number of octets wins.

Did you choose counting characters on purpose? We usually count bytes since some languages get an easy boost from UTF-16 encoding their source and just base converting (CJam, looking at you).

@Pietu1998 compressing source code is usually seen as a standard loophole / bad style. I count characters because it's a reasonable way to avoid the discussions about which encoding to use.

@Pietu1998 There is a meta post about character count. It is assumed that either bytes or UTF-8 should be used (for counting). So if your program is 10 chars in UTF-16, that counts as 20.

@mbomb007 It's my challenge and I want this to be counted in characters, mkay?

CJam will probably win then. And no, compressing source code isn't a standard loophole. It's part of the language.

@mbomb007 My intent is not to punish people for using a domain specific language. I don't care if CJam wins. If you have hate against CJam, please fight against CJam in your challenge but please leave mine alone.

@FUZxxl Counting characters usually leads to even more efficient compression of source code, because you can use the full Unicode codepoint range.

@orlp I count “compressing source code” as a standard loop hole, as said above.

That is at most a non-standard loophole. You need to specify that in the question if you want to disallow it. And I'm not sure if it is objective enough.

@mbomb007 Can you show me that meta post? All posts I found basically say “challenges are scored in bytes unless OP explicitly specifies that they are scored in characters” and the code-golf tag wiki agrees with that.

@FUZxxl reviving the dead here:  The problem here is not that you are scoring by characters but that you assume that "Compressing source code" is a standard loophole.  This is not true. So, after posting that potential loophole, do you still want to score this in characters?

@NathanMerrill In this case, we may score in octets.

K (ngn/k), 38 bytes
{((x,y)#&(0;y;y*x-2;y-2;2))z|:/x!z+!x}

Try it online!
I can't believe that it went unanswered for, like, six and a half years?
Implements the three-argument version. It is a function that takes n m p as three separate parameters and builds a valid net puzzle deterministically.
Basically what it does is to build one asymmetric and easily constructible net puzzle of size n m, and then permute its rows based on p.
What it builds & Why it is valid for this challenge
The result for f[5;6;0] is this:
1 1 1 1 1 1
2 2 2 2 2 2
2 2 2 2 2 2
2 2 2 2 2 2
3 3 3 3 4 4

In box drawing chars:
1 1 1 1 1 1 : ╷╷╷╷╷╷
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
2 2 2 2 2 2 : ││││││
3 3 3 3 4 4 : ┴┴┴┴┘└

And it has a unique solution, as well as its reflections and rotations (as in APL sense; cyclically moving rows and columns).
Why unique solution? First, the solution is an unrooted tree (in graph-theoretical sense); if a configuration has a cycle, then it is not a solution because it necessarily has two or more disjoint parts. Then, the 2's must be all aligned either horizontally or vertically, but if they're horizontal then they form one or more cycles of their own. So they must be vertical. Then the orientation of 1's are fixed (downwards), and then the 3's (disconnected to the lower side). Finally the orientations for 4's are fixed in order to connect everything.
The code is easy:
&(0;y;y*x-2;y-2;2)    Create an array of:
                      m copies of 1's, m*(n-2) copies of 2's,
                      (m-2) copies of 3's, and 2 copies of 4's
(x,y)#                Reshape into n-row, m-col matrix

For "at least four distinct puzzles" part, I had to use two different permuting methods because of the 3x3 grid (single reflection gives at most 2; stepwise rotation gives at most either n or m). I went for pure row permutation because applying two separate transforms was too long.
For code, !x creates the identity permutation vector 0 1 2 ... (n-1), x!z+ rotates it by p steps, and z|:/ reverses it p times. This creates lcm(2, n) unique grids, which is always at least 4.
I know, it's likely against the original intent of the challenge, but this is not the first time I exploited "generate at least x distinct grids" :P

Since the original grid is toroidal, can those rotated permutations really be described as different?

@Neil "Different integer matrix" is my interpretation of different. If OP intended otherwise, it should've been in the challenge text.

@Bubbler Yes, your interpretation is correct and was intended.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Wrap-Around Subsequences
Introduction
In this challenge, your task is to find generalized subsequences of strings.
The subsequences are not necessarily contiguous, and they can also "wrap around" the string, going past its end and starting again from the beginning.
You'll want to minimize the number of wraps, though.
More formally, let u and v be any two strings, and k ≥ 0 an integer.
We say that u is a k-wrapping subsequence of v, if there are distinct indices i1, i2, ..., ilen(u) such that u == v[i1] v[i2] ... v[ilen(u)], and at most k of the indices ij satisfy ij > ij+1.
This means that u can be found inside v by going from left to right, choosing some of its characters on the way, and wrapping around at most k times (equivalently, doing at most k+1 sweeps across v).
Note that no character can be chosen more than once, even after a wrap-around, and that 0-wrapping subsequences are exactly the ordinary subsequences that we are all familiar with.
The Task
Your inputs are two non-empty alphanumeric strings u and v, and your output is the smallest integer k such that u is a k-wrapping subsequence of v.
If no such k exists, the output shall be -1.
Example
Consider the inputs u := xyzyxzzxyx and v := yxzzazzyxxxyz.
If we start looking for the characters of u in v in a greedy fashion, we will wrap around 3 times:
 yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>

Thus the correct output is at most 3.
Note how the left-most character x is selected once, and then ignored on the second sweep, since it cannot be re-used.
However, there exists a shorter method with only 2 wrap-arounds:
 yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>

It turns out that one wrap-around (that is, two sweeps) is not enough, so the correct output is 2.
Rules and Bonuses
You can write either a function or a full program, and you can also change the order of the inputs if needed.
The lowest byte count wins, and standard loopholes are disallowed.
There is a bonus of -10% for computing all of the test cases in under 10 seconds total. I will test unclear cases on my machine; my reference implementation in Python takes about 0.6 seconds. I have a 7-year old laptop with 1.86 GHz dual core CPU, which you may want to take into account.
Test Cases
"me" "moe" -> 0
"meet" "metro" -> -1
"ababa" "abaab" -> 1
"abaab" "baabaa" -> 1
"1c1C1C2B" "1111CCCcB2" -> 3
"reverse" "reserved" -> 2
"abcdefg" "gfedcba" -> 6
"xyzyxzzxyx" "yxzzazzyxxxyz" -> 2
"aasdffdaasdf" "asdfddasdfsdaafsds" -> 2

Would this also be a valid solution for the example? It's a greedy approach.

@orlp It is not valid, because the first x is used in three distinct sweeps. It can only be used once.

Ahhh, I see now.

Pyth, 34 bytes
Mh+Smssm>.ukC,dtdfqGsm@HkT.PUHlG_1

This defines a function g, which takes two strings as parameter. Try it online: Pyth Compiler/Executor
This code is very inefficient. It has a time and memory complexity of len(v)!/(len(v)-len(u))!. It is not able to solve the longer test cases in under 10 seconds. (It also will crash very likely, since it will run out of memory.)
M                                    define g(G, H): return _
                          .PUHlG        all permutations of [0, 1, ..., len(H)-1] of length len(G)
                 fqGsm@HkT              filter the permutations which form the string G
    mssm>.ukC,dtd                       compute the number of wraps for each of the remaining permutations
  +S                            _1      sort the numbers and append -1
 h                                      return the first element

Haskell, 160 * 0.9 = 144 bytes
a#(-1)=a
a#b=min a b
f y=w(y++" ")0$length y
w _ n _[]=n
w(c:d)n o g@(a:b)|n>o=(-1)|a==c=z#w y n z g|c==' '=w y(n+1)o g|1<2=w y n o g where z=w d n o b;y=d++[c]

Timing for all test cases (note: arguments are flipped):
*Main> map (uncurry f) [
             ("moe", "me"),
             ("metro", "meet"),
             ("abaab", "ababa"),
             ("baabaa", "abaab"),
             ("1111CCCcB2", "1c1C1C2B"),
             ("reserved", "reverse"),
             ("gfedcba", "abcdefg"),
             ("yxzzazzyxxxyz", "xyzyxzzxyx"),
             ("asdfddasdfsdaafsds", "aasdffdaasdf")]
[0,-1,1,1,3,2,6,2,2]
(0.08 secs, 25794240 bytes)

How it works (short version): simple brute force that takes the minimum of using a matching character and skipping it. I stop the search when either finished (returning the number of cycles) or when cycled more than the minimum so far (returning -1).
Saved a lot of bytes compared to my first version, mainly because I switched from a full program to a function.
With some comments and proper spacing golfed Haskell is quite readable:
-- a minimum function that ignores a -1 in the right argument to prevent
-- "not solvable" cases in parts of the recursive search to dominate low numbers
-- of solvable parts. If the case isn't solvabale at all, both arguments are
-- -1 and are carried on.
a # (-1) = a
a # b    = min a b

-- the main function f calls the worker funktion w with arguments
-- * the string to search in (STSI), appended by a space to detect cycles
-- * the number of cycles so far
-- * the minimum of cycles needed so far, starting with the length of STSI
-- * the string to search for (STSF) (partial applied away and therefore invisible)
f y = w (y++" ") 0 (length y)

-- the worker function
w _ n _ [] = n          -- base case: if STSF is empty the work is done and the
                        -- number of cycles is returned

w (c:d) n o g@(a:b)     -- "c" is first char of STSI, "d" the rest
                        -- "n" number of cycles, "o" minimum of cycles so far
                        -- "g" is the whole STSF, "a" the 1st char, "b" the rest
  | n>o    = (-1)             -- if current cycle is more than a previous result,
                              -- indicate failure
  | a==c   = z # w y n z g    -- if there's a character match, take the min of
                              -- using it and skipping it
  | c==' ' = w y (n+1) o g    -- cycle detected, repeat and adjust n
  | 1<2    = w y n o g        -- otherwise try next char in STSI

  where                 -- just some golfing: short names for common subexpressions
  z = w d n o b;        -- number of cycles if a matching char is used
  y = d ++ [c]          -- rotated STSI

For reference: old version, full program, 187 bytes
main=interact$show.f.lines
a#(-1)=a
a#b=min a b
f[x,y]=w x(y++" ")0 0
w[]_ n _=n
w g@(a:b)(c:d)n m|a==c=w b d n 1#y|c==' '&&m==1=w g(d++" ")(n+1)0|c==' '=(-1)|1<2=y where y=w g(d++[c])n m

@Zgarb: reworked my solution. It's now faster and shorter.

Runs in 0.6s when interpreted, 0.01s when compiled.

JavaScript (ES6) 174 (193 - 10%)
Recursive search, like the @nimi's answer, keeping the min of wraps. The solutions space is big (above all for the last example) but cutting the search at the min currently found keeps the time low.
Edit 1 Add a missing test case, shortened a bit
Edit 2 No need to pass param w around, it's fixed
K=(w,s,x)=>
  ~-(R=(r,l,p=0,q=1,z=w[p],i=0)=>
  {
    if(z&&!(q>x)){
      if(~(r+l).indexOf(z))
        for(t=l?R(l+r,'',p,q+1):x;x<t?0:x=t,i=~r.indexOf(z,-i);)
          t=R(r.slice(-i),l+r.slice(0,~i),p+1,q);
      q=x
    }
    return q
  })(s,'')

Ungolfed
K=(word, astring)=>
{
  var minWraps // undefined at first. All numeric comparison with undefined give false
  var R=(right, left, pos, wraps)=>
  {
    var cur = word[pos]
    var i,t;
    if (! cur) // when all chars of word are managed
      return wraps;
    if (wraps > minWraps) // over the minimum wrap count already found, stop search
      return wraps;
    if ( (right+left).indexOf(cur) < 0 ) // if the current char is not found in the remaining part of the string
      return minWraps; // return the current min, could still be undefined (that means 'no way')
    if ( left ) // if there is a left part, try a wrapping search with the current char
    {
      t = R(left+right, '', pos, wraps+1)
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    // find all occurrences of current char in the remaining part
    // for each occurrence, start a recursive search for the next char
    for(i = 0; (i = right.indexOf(cur, i)) >= 0; i++)
    {
      var passed = right.slice(0,i) // the passed chars go in the left part
      var rest = right.slice(i+1)
      t = R(rest, left+passed, pos+1, wraps) // try next char in the remaining part, no wrap
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    return minWraps
  }
  var result = R(astring, '', 0, 1) // start with right=string and left empty
  return ~-result; // decrement. convert undefined to -1
}

Test In Firefox/FireBug console
time=~new Date;
[['me','moe']
,['meet','metro']
,['ababa','abaab']
,['abaab','baabaa']
,['1c1C1C2B','1111CCCcB2']
,['reverse','reserved']
,['abcdefg','gfedcba']
,['xyzyxzzxyx','yxzzazzyxxxyz']
,['aasdffdaasdf','asdfddasdfsdaafsds']]
.forEach(s=>console.log(s,r=K(...s)))
time-=~new Date

Output (last line is the execution time in ms)

["me", "moe"] 0
["meet", "metro"] -1
["ababa", "abaab"] 1
["abaab", "baabaa"] 1
["1c1C1C2B", "1111CCCcB2"] 3
["reverse", "reserved"] 2
["abcdefg", "gfedcba"] 6
["xyzyxzzxyx", "yxzzazzyxxxyz"] 2
["aasdffdaasdf", "asdfddasdfsdaafsds"] 2
116

Tested with Firebug, runs in 175ms on my machine.

@Zgarb then there is room for improvements: I'll try to make it slower and shorter


text:
Memory is Expensive
You are a robot. You are stranded in a small cage with weird humans wearing weird suits looking at you. Your solar panel is malfunctioning, and your energy is running out. On the wall there is a riddle, and if you answer correctly the humans will grant you access to an energy source (yay!). However your RAM unit is leaking power, and the more you use it, the more energy will be lost.

For each byte you access, you spend 1 energy unit (a bit costs 1/8 energy).
The program that uses the least energy wins.
Arrays cost the sum of all their variables.  Strings and other non-fixed-length variables/arrays are prohibited, as your bot will be unable to calculate how much energy it spent.  (Recursion is prohibited too!)

The riddle is weird, it changes after a while, so your bot must not hardcode the answer.
The riddle is a mathematical challenge:

We shall input you with 3 variables, and they are free, but you shall not change them.
For these 3 inputs, a, b and c, thou shalt calculate an integer p equivalent to floor(pi * 10^(c-1)), then you shall calculate x = a!/b!.  Then you shall add to x the integer p.  If and only if c is greater than x, you shall yell Pi!!!!
a, b and c are integers smaller than the number 13.

Example: for a = 5, b = 4, and c = 3, calculate 5!/4! + 314. as x = 5, and c = 3, don't yell Pi!!!!
Once finished calculating, your bot should output the answer. The input can be either in form of calling a function or the user typing a number when prompted.
If 2 bots have the same energy spending, the shortest code wins.
Also, the energy cost is for the worst case (that's why I said a, b and c are smaller than 13). (Extra clarification: the language overheads don't count, unless you abuse them to store data.)

Does the program count towards the RAM? If yes, how?

Is it "either yell Pi!!! or output the answer" or is it "potentially yell Pi!!! and always output the answer"?

What about languages where integers are of non-constant length?

I have trouble understanding what you have to do (partly because of the strange language), I especially do not really understand the second yellow box, can anyone transcribe that to 'modern' english? Are a,b,c integers? What does 'equivalent' exactly mean here?

@orlp Then do the minimum size needed to contain them. For example, even though numbers in Mathematica are (mostly) arbitrary, the minimum number is 16 bytes.

I think that what is and is not a RAM access probably needs some clarification. Does our code exist in RAM? Do some or all of local varaibles? Do global variables?

O.P., have merci of us and please explain what and how do me count towards the energy usage, please.

Is the division a floor division or floating-point division?  That is, what if a=1 and b=2, should x be equal to 0.5 or 0?   What is "the answer" that we should output?

@LegionMammal978 What about machine integers in a packed array?

@2012rcampion Exactly what do you mean by "packed"?

@LegionMammal978 See Developer`PackedArrayQ.  Packed arrays use machine integers, so they're only 64 bits/8 bytes.

@2012rcampion It only seems pack larger arrays (such as Range[40].)

@LegionMammal978 Range[1]//PackedArrayQ

@LegionMammal978 Or ConstantArray[_, 1] to turn any integer or machine-precision number into a packed array.  Although ByteCount shows that the array actually takes up 112 bytes, the question states that arrays are to be counted as the sum of their elements (8 in this case).

FUZxxl no, its only for tie braking.
Martin: possibly yell pi, and always output.
flawr, a b and c are integers.
Runner. global and local variables count, your program doesnt. (exept for tie braking)
2012Champion a is always bigger than b, and if it isnt, then answer whatever.

10^c means 10 XOR c or 10 * 10 * 10 ...?

@IsmaelMiguel That was my modification, it means exponentiation.  (The original spec said "an integer equivalent to pi to c places".)  Actually now that you point it out, it looks like I made an off-by-one error (should be 10^(c-1), since for c=3, it should be p=314, not 3141).

@2012rcampion It isn't well explicit. I'm doing by string accesses and cutting it. In math, 10^c is totally different from 10^c in programming.

AVR (274 bytes, 0 energy points)
With all those fancy high-level languages you're never really sure how much RAM you're accessing.  The only way to be sure is to nuke it from orbit go down to the bytes.  Fortunately I just happen to be teaching myself assembler at the moment.
This submission is a subroutine that uses the AVR-GCC calling convention.  Fortunately it so happens that both the return value and the arguments fit in registers.  The return value will be at most 12! + floor(pi * 10^11) = 0x49 41 e6 f2 4e (five bytes) and each of the arguments is at most 12 (one byte each).  Each size is rounded up to the nearest multiple of two, so we get a total size of 6 + 2 + 2 + 2 = 12 bytes.  Starting at R25, the return value fits in R20-R24, and the arguments live in R18, R16, and R14.
Note that as per the rules ("... but you shall not change [the inputs].") I don't write to R18, R16, or R14.  I also don't explicitly use the stack or access anything other than the registers, meaning only two bytes are ever read from RAM during the whole program: RET reads the return address from the stack.  However, the rules state "language overheads don't count," so the total score is zero.
The only other oddity is that I don't have a printf function, so in order to "yell" I bit-bang a generic parallel interface on port D.  (That's digital pins 0-6 if you run this on an Arduino UNO, with pin 7 being the clock.)
Here is the code itself.  All the jumps are relative, so you can plop this anywhere in your program and have it work.
4e e4 56 ef 69 e5 75 e2 89 e4 90 e0
22 24 23 94 33 24 44 24 55 24 77 24
60 2e 63 94 20 17 10 f4 22 24 12 c0
26 15 80 f0 56 9c 50 2c 46 9c 40 2c
51 0c 36 9c 30 2c 41 0c 57 1c 26 9c
20 2c 31 0c 47 1c 57 1c 63 94 ee cf
57 14 01 f5 47 14 f1 f4 37 14 e1 f4
2e 14 d0 f4 10 e5 1b b9 10 68 1b b9
19 e6 1b b9 10 68 1b b9 11 e2 1b b9
10 68 1b b9 1f 77 1b b9 10 68 1b b9
1f 77 1b b9 10 68 1b b9 1f 77 1b b9
10 68 1b b9 00 00 7b b8 1c e0 61 2e
6e 18 c9 f1 13 e3 81 9f 80 2d 91 2d
71 9f 70 2d 81 0d 97 1d 61 9f 60 2d
71 0d 87 1d 97 1d 51 9f 50 2d 61 0d
77 1d 87 1d 97 1d 41 9f 40 2d 51 0d
67 1d 77 1d 87 1d 97 1d 45 0f 56 1f
67 1f 78 1f 89 1f 97 1d 46 0f 57 1f
68 1f 79 1f 87 1d 97 1d 48 0f 59 1f
67 1d 77 1d 87 1d 97 1d 45 2f 56 2f
67 2f 78 2f 89 2f 99 27 86 95 77 95
67 95 57 95 47 95 6a 94 39 f6 42 0d
53 1d 64 1d 75 1d 87 1d 08 95

Here is the breakdown, including a short header to demonstrate calling the function.
0x0000  1fef      ldi  r17, 0xFF  ; write 1111 1111
0x0002  1ab9      out  0x0a, r17  ; to port D direction register
0x0004  10e0      ldi  r17, 0x00  ; write 0000 0000
0x0006  1bb9      out  0x0b, r17  ; to port D output register
0x0008  25e0      ldi  r18, 0x05  ; set a to 5
0x000a  04e0      ldi  r16, 0x04  ; set b to 4
0x000c  13e0      ldi  r17, 0x03  ;
0x000e  e12e      mov  r14, r17   ; set c to 3 (can't ldi, r14 < r16)
0x0010  0e940a00  call 0x14       ; call our subroutine @ 0x0014
0x0014  4ee4      ldi  r20, 0x4E  ; initialize output
0x0016  56ef      ldi  r21, 0xF6  ; with maximum 'pi integer'
0x0018  69e5      ldi  r22, 0x59  ; Floor[Pi*10^11]
0x001a  75e2      ldi  r23, 0x25  ;  = 314 159 265 358 (12 digits)
0x001c  89e4      ldi  r24, 0x49  ;  = 0x 49 25 59 f6 4e
0x001e  90e0      ldi  r25, 0x00
0x0020  2224      eor  r2, r2     ; initialize x
0x0022  2394      inc  r2         ; to 1
0x0024  3324      eor  r3, r3     ; (eor clears a byte)
0x0026  4424      eor  r4, r4
0x0028  5524      eor  r5, r5
0x002a  7724      eor  r7, r7     ; r7 stays zero (handy)
0x002c  602e      mov  r6, r16    ; count = b
0x002e  6394      inc  r6         ; count++
0x0030  2017      cp   r18, r16   ; if a >= b
0x0032  10f4      brcc .+4        ; go to loop @ 0x0038
0x0034  2224      eor  r2, r2     ; otherwise x is zero
0x0036  12c0      rjmp .+36       ; go to end of loop @ 0x005c
0x0038  2615      cp   r18, r6    ; if a < count
0x003a  80f0      brcs .+32       ; go to end of loop @ 0x005c
0x003c  569c      mul  r5, r6     ; otherwise multiply high byte by count
0x003e  502c      mov  r5, r0     ; copy low byte of result (high byte = 0)
0x0040  469c      mul  r4, r6     ; multiply second byte by count
0x0042  402c      mov  r4, r0
0x0044  510c      add  r5, r1     ; carry
0x0046  369c      mul  r3, r6     ; multiply third byte
0x0048  302c      mov  r3, r0
0x004a  410c      add  r4, r1
0x004c  571c      adc  r5, r7
0x004e  269c      mul  r2, r6     ; multiply low byte
0x0050  202c      mov  r2, r0
0x0052  310c      add  r3, r1
0x0054  471c      adc  r4, r7
0x0056  571c      adc  r5, r7
0x0058  6394      inc  r6         ; count++
0x005a  eecf      rjmp .-36       ; return to start of loop @ 0x0038
0x005c  5714      cp   r5, r7     ; if any of the high bytes of x
0x005e  01f5      brne .+64       ; are nonzero
0x0060  4714      cp   r4, r7     ; then jump past 'yelling'
0x0062  f1f4      brne .+60       ; @ 0x00a0
0x0064  3714      cp   r3, r7
0x0066  e1f4      brne .+56
0x0068  2e14      cp   r2, r14    ; only the low byte is a comparison
0x006a  d0f4      brcc .+52       ; since c is only one byte long
0x006c  10e5      ldi  r17, 0x50  ; write 'P' to buffer
0x006e  1bb9      out  0x0b, r17  ; write to PORTD
0x0070  1068      ori  r17, 0x80  ; set clock bit (buffer |= 1000 0000)
0x0072  1bb9      out  0x0b, r17  ; PORTD
0x0074  19e6      ldi  r17, 0x69  ; 'i'
0x0076  1bb9      out  0x0b, r17  ; PORTD
0x0078  1068      ori  r17, 0x80  ; 1000 0000
0x007a  1bb9      out  0x0b, r17  ; PORTD
0x007c  11e2      ldi  r17, 0x21  ; '!'
0x007e  1bb9      out  0x0b, r17  ; PORTD
0x0080  1068      ori  r17, 0x80  ; 1000 0000
0x0082  1bb9      out  0x0b, r17  ; PORTD
0x0084  1f77      andi r17, 0x7F  ; clear clock bit (buffer &= 0111 1111)
0x0086  1bb9      out  0x0b, r17  ; PORTD
0x0088  1068      ori  r17, 0x80  ; 1000 0000
0x008a  1bb9      out  0x0b, r17  ; PORTD
0x008c  1f77      andi r17, 0x7F  ; 0111 1111
0x008e  1bb9      out  0x0b, r17  ; PORTD
0x0090  1068      ori  r17, 0x80  ; 1000 0000
0x0092  1bb9      out  0x0b, r17  ; PORTD
0x0094  1f77      andi r17, 0x7F  ; 0111 1111
0x0096  1bb9      out  0x0b, r17  ; PORTD
0x0098  1068      ori  r17, 0x80  ; 1000 0000
0x009a  1bb9      out  0x0b, r17  ; PORTD
0x009c  0000      nop             ; baud rate is 1/4 processor speed
0x009e  7bb8      out  0x0b, r7   ; PORTD
0x00a0  1ce0      ldi  r17, 0x0C  ; buffer = 12
0x00a2  612e      mov  r6, r17    ; count = buffer (# of places in p)
0x00a4  6e18      sub  r6, r14    ; count -= c (# of /= 10 we need)
0x00a6  c9f1      breq .+114      ; if count == 0 skip loop @ 0x011a
0x00a8  13e3      ldi  r17, 0x33  ; buffer = 51
0x00aa  819f      mul  r24, r17   ; following the same procedure as before
0x00ac  802d      mov  r24, r0    ; we multiply p by 51
0x00ae  912d      mov  r25, r1
0x00b0  719f      mul  r23, r17   ; since we can't divide by 10
0x00b2  702d      mov  r23, r0    ; we divide by 5
0x00b4  810d      add  r24, r1    ; by multiplying by
0x00b6  971d      adc  r25, r7    ; 0b0.00110011001100110011
0x00b8  619f      mul  r22, r17   ; equivalent to multiplying by
0x00ba  602d      mov  r22, r0    ; 0b110011 = 51
0x00bc  710d      add  r23, r1    ; then repeatedly adding to itself
0x00be  871d      adc  r24, r7    ; shifted right by one byte
0x00c0  971d      adc  r25, r7
0x00c2  519f      mul  r21, r17
0x00c4  502d      mov  r21, r0
0x00c6  610d      add  r22, r1
0x00c8  771d      adc  r23, r7
0x00ca  871d      adc  r24, r7
0x00cc  971d      adc  r25, r7
0x00ce  419f      mul  r20, r17
0x00d0  402d      mov  r20, r0
0x00d2  510d      add  r21, r1
0x00d4  671d      adc  r22, r7
0x00d6  771d      adc  r23, r7
0x00d8  871d      adc  r24, r7
0x00da  971d      adc  r25, r7
0x00dc  450f      add  r20, r21   ; add p to itself, shifted one byte
0x00de  561f      adc  r21, r22
0x00e0  671f      adc  r22, r23
0x00e2  781f      adc  r23, r24
0x00e4  891f      adc  r24, r25
0x00e6  971d      adc  r25, r7
0x00e8  460f      add  r20, r22   ; shifted two bytes
0x00ea  571f      adc  r21, r23
0x00ec  681f      adc  r22, r24
0x00ee  791f      adc  r23, r25
0x00f0  871d      adc  r24, r7
0x00f2  971d      adc  r25, r7
0x00f4  480f      add  r20, r24   ; shifted four bytes
0x00f6  591f      adc  r21, r25
0x00f8  671d      adc  r22, r7
0x00fa  771d      adc  r23, r7
0x00fc  871d      adc  r24, r7
0x00fe  971d      adc  r25, r7
0x0100  452f      mov  r20, r21   ; shift right one byte
0x0102  562f      mov  r21, r22
0x0104  672f      mov  r22, r23
0x0106  782f      mov  r23, r24
0x0108  892f      mov  r24, r25
0x010a  9927      eor  r25, r25   ; clear top byte
0x010c  8695      lsr  r24        ; finally divide by two
0x010e  7795      ror  r23        ; by shifting right one bit
0x0110  6795      ror  r22
0x0112  5795      ror  r21
0x0114  4795      ror  r20
0x0116  6a94      dec  r6         ; count--
0x0118  39f6      brne .-114      ; if count != 0, repeat @ 0x00a8
0x011a  420d      add  r20, r2    ; add x to p
0x011c  531d      adc  r21, r3
0x011e  641d      adc  r22, r4
0x0120  751d      adc  r23, r5
0x0122  871d      adc  r24, r7
0x0124  0895      ret             ; return

Note that the since the subroutine directly follows the main routine, the subroutine is actually executed twice.  The second RET call then tries to read from an empty stack.  I left this behavior in the minimal example, since it's not a problem if you go step-by-step through the AVR simulator, and I wanted to keep the byte count low.
Mathematica (70 bytes, 6 energy points)
Function[{a,b,c},If[c>a!/b!,Print["Pi!!!!"]];a!/b!+Floor[Pi 10^(c-1)]]

a, b, and c are 'free', and don't count towards the number of accesses.
The string contains six characters, which count as six bytes.

I believe the string PI!!!! counts towards the number of accesses. I also thought arguments counted, too, since you're still referencing them, which ends up loading them (a memory access).

@kirbyfan64sos "We shall input you with 3 variables, and they are free" (emphasis mine).  You're right about the string, but since "Strings [...] are prohibited" it doesn't matter anyway.

@kirbyfan64sos Actually, does the string count?  Since it's an immediate value, it's never stored in a variable and thus never "accessed".  Also, since Mathematica is functional, my function never even sees the string.  (If the OP ever clarifies the counting method I'll update my count)

In the JavaScript answer, the OP said strings do.

@kirbyfan64sos OK, I see now.  I'll edit the question to include that.

@kirbyfan64sos Actually the OP says in that comment that you should only count bytes you "actually use," but also says that a 31 byte array costs 31 energy.  Does that mean per access or upon array construction?  Does each array access cost 0, 1, or 31?  Should my string cost 0 if I don't use it (c <= a!/b!)?

I don't quite know. Also, if your interpretation of the answer is the correct one, then both IsmailMiguel and I are wrong...ARGH!

@kirbyfan64sos Yeah, the scoring system could definitely be better specified.  Maybe we should just get OP to score them for us?

@2012rcampion Actually, I'm not even counting the array. I left it open. I left EVERYTHING open. Let the O.P. decide. That's what I did.

@matultimate Can you confirm the score for my new solution?

@2012rcampion, i dindt think of languages where you could just call a function to calculate pi, so i guess mathematica is 6 points, however thats on a technicality

@matultimate Two points, 1) I was asking about my score for the AVR answer, I already knew it's 6 for my MMA answer. 2) When you say "calculate" pi, but "cannot hardcode the answer," what do you mean?  Do we have to compute pi from first principles?  arccos(-1) or something?  All the answers (incl. mine) so far use a hardcoded constant.

Both of these are ports of @IsmaelMiguel's answer.
K, 59 bytes, # of accesses is proportional to input size
f:{:[z>(l[x]%(l:*/1+!:)y)+0$z#"3141592653589";"PI!!!!";""]}

The number of accesses would be something like (assuming a, b, and c are free):
a*4+b*4+19

C89, 172 bytes (DON'T LOOK! CAST AWAY!)
int l(int n){int r=1;while(n--)r*=r;return r;}char s[]="PI!!!!";char*f(int a,int b,int c) {char p[]="3141592653589";p[c-1]=0;if(l(a)/l(b)+strtol(p,0,0)>=c)s[0]=0;return s;}

Apparently we're not allowed to use recursion, so this increased by several characters. Darn it.
Again assuming a, b, and c are free, the # of accesses might be something like:
a*4*4+b*4*4+3*4+3*8+15 == a*16+b*16+51

Thanks to @mbomb007 for pointing out I accidentally forgot an exclamation mark in "PI!!!!".

You're supposed to yell "PI!!!!", (4 ! in a row)

@mbomb007 Fixed.

for a, b and c = 12 im guessing the num of accesses would be 435 in the C program? am i correct? can you also clarify the number of accesses for the worst case cenario for the K code please

@matultimate It's hard. In C, there are more logical memory accesses, but any interpreted language (such as K or JavaScript) has more many real memory accesses. Of course, maybe I'm overthinking the challenge...

@matultimate Also, different computers have different sizes. For instance, on 64-bit computers, a long is 8 bytes; on 32-bit, it's 4. To add to that, in every language, you've got invisible overhead. For instance, in K and JavaScript, would the garbage collector count?

@kirbyfan64sos, if the biggest num you use is 4 bits, than no matter what system you are in it costs 4 points. and no the language overhead does not count

Javascript (155 bytes, 14+ accesses)
Alright, this isn't the most golfed answer.
Quoting this: "Arrays cost the sum of all their variables"... I have no idea how to interpret this, since an array is simply a set of values all aligned in the memory.
Also, there's no information about how to access functions or anything else.
But here is the code:
function(a,b,c){var m=[1,1,2,6,24,120,720],f=function(n){return m[n]=m[n]?m[n]:n*f(n-1)};return ((f(a)/f(b))+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

For the score (using a=5, b=4, and c=3):

Creates an array with the factorial until 7 already there (? accesses)
Creates a variable f with a function to access the array (? accesses)
Calculates the factorial of a (2 accesses)
Calculates the factorial of b (2 accesses)
Divides them (2 accesses)
Calculates the sum of the number "equivalent to PI" (Math.PI*Math.pow(10,c)>>0) now it is only 3 accesses since it fetches c characters from the string and converts to integer:

Gets the value of PI (∞ accesses)
Calculates the power of 10 to multiply by Math.PI (∞ accesses + 1)
Sums it all together (2 accesses)
Rounds it (1 access)

Compares with c (2 accesses)
Either returns an empty string (0 accesses) or PI!!!! (6 accesses).

Result: To be improved! The battery would die in no time! DO NOT RUN THIS CODE ON YOUR ROBOT OR IT WILL EXPLODE

I assume that the access to the window object is ∞ (infinite) due to the fact that it contains everything, including itself.
Conclusion: I'm missing some crucial information and explanation to calculate the final number of accesses. But shouldn't be too bad, right?

Why am I using var? Simple: if it is declared without var, it is effectively accessing the window object which is a ∞ (infinite) number of accesses and the battery wouldn't even last 1 nanosecond. We would have a very fast drain, probably followed by an explosion.

Javascript (165 bytes, 31 bytes for the factorial array + 16 accesses):
This one should be easier to calculate
function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

It has a 31 bytes-long list with all the 13 factorial numbers required.
It was calculated with the following code:
var i=0,m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800],k;for(k in m)i+=Math.ceil(m[k].toString(2).length/8);

This makes it faster (if time is critical) and cleaner both for humans and machines. With a VERY good branch-prediction, the number of accesses could be reduced to 7 accesses.
It works as the code above, except that it doesn't have to calculate the factorial.

Javascript (3 bytes, self-destruction)
Yes, the smallest losing entry!
It drains your battery so fast it will explode!
It's simple, just run:
top

And you are set. top is a variable that will access to window.top, which is the same as window, which has recursion  EVERYWHERE

Javascript (31*2+6+6 bytes (592 bits), 187*2+42+38=494 bits ):
Same thing as before, but a lot easier to calculate the number of accesses:
function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(''.substr.call(3141592653589,0,c)))<c?'PI!!!':'';}

Empty strings and 0 aren't being calculated. Why? They are NOTHING in the memory. They only have a datatype.
The aray is being accessed twice, so, I'm counting that the entire array must be scattered.
If not, then the number of accesses drops to 22 bytes (146 bits)!!!
That is for the worst case!!!

For your array, since it is made up of 2-byte integers (apparently), your 7-element array would be 2 * 7 = 14 accesses.

@LegionMammal978 That makes VERY little sense... [1,1,2,6,24,120,720] would be 8 bytes long (only the last number is 2-bytes long), and you would use 1 extra byte to access 1 element. So, shouldn't it be 2-3 bytes per access?

I meant for creating it. If you are on a 64-bit system, it would be 8 bytes for the address + 1 byte for the offset + 8 bytes for the resulting address + 1 byte for the element = 18 bytes. For 32-bit systems, it would just be 4 + 1 + 4 + 1 = 10 bytes.

@LegionMammal978 That makes sense. But there is no cost in creating variables, I guess... At least it isn't specified. (But I'm being a little fair by counting the access to register a new number in the factorial array)

@LegionMammal978 In your opinion, how do you think that [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800] should be calculated? It is 31 bytes long. And contains every factorial required for this.

Well, it needs to load the array in RAM to store it.

@LegionMammal978 Honestly, I have no quacking idea how the quacking heck am I quascking suposed to quacking count this quacky crap! I'm gonna beg for the O.P.'s merci.

well you realy shouldnt have hardcoded the answer :P ("The riddle is weird, it changes after a while, so your bot must not hardcode the answer.").
anyways the number of accesses would be 1 per byte you actually use, ill ignore the overhead for making an array work. (thats why i said it is the sum of all vatiables :P ) so if the array is 31 byte long its 31 energy points, no need to worry about language overhead.

I was reading your second JS code, and hardcoded PI has to count for the energy cost

@matultimate how much doesn '3141592653589'.substr(0,c) cost? and ''.substr.call(3141592653589,0,c)? The first is an array of characters, accessed with base on the value of c. The 2nd, is a 0-byte string which calls a function which calls a function to set the this as the number 3141592653589 which ocupies 42 bits (almost 6 bytes). How about the 0?

'3141592653589' counts as a string ( 1 byte per character) while 3141592653589 and 0 cont as integers (0 costs 1 bit)

@matultimate But 0 is 0 bits... Same as '' or false.

Java (4 Energy points, maybe)
Here's my solution. I am not entirely sure how to score it as I might be invalid.
Calculating p wasn't part of the output so I skipped it (the people holding the bot wouldn't know if it was calculated or not). Also, I'm not sure if this is counts for hardcoding and I don't have enough rep to comment to ask.
public class Bot {
    public void foo(final int a, final int b, final int c) {
        if (b > a) {
            return;
        }
        int x = a - b;
        if (x > 4) {
            return;
        } else if (x == 3 && c < 7) {
            return;
        } else if (x == 2 && c < 3) {
            return;
        } else if (c < 2) {
            return;
        }
        System.out.println("Pi!!!!");
    }
}

you do have to output p

"thou shalt calculate an integer p" Doesn't say to output it anywhere though. Nevertheless I will work on it soon.

"Once finished calculating, [you] should output the answer."  This problem is full of loopholes and issues, but this is not one of them, sadly.  (This was actually my original solution too, but then I read more carefully.)

@2012rcampion I guess I thought "Pi!!!!" was the answer. (Isn't it always Pi, 0, or 1?)

The answer you output is a!/b! + floor(pi * 10^(c-1)) for a >= b, and whatever you want for a < b, as far as I understand.  Can @matultimate confirm this?

I didn't realize this in the edit window for my other comment, the italics was a joke because in math class it always seemed like the answer was something really simple in the end, not talking about the challenge itself.


text:
IMP: Implicit multiplication parser
Jack likes the C programming language, but hates writing expressions like V=a*b\*h; to multiply values.
He would like to just write V=abh; instead; why should the compiler moan about abh being undefined? Since int a, b, h; are defined, can't it just deduce multiplication?
Help him implement a parser that deciphers a single multiplication term,
provided the set of variables defined in current scope is known.
For simplicity, no numbers will be included (i.e. 2abh), only single-character variables.
The input is a multiplication term T, fulfilling regexp:
[a-zA-Z_][a-zA-Z_0-9]*

 and a variable set Z  .
A parsing P of the term T over variable set Z is a string fulfilling the following conditions:

P can be turned back into T by removing all * characters
The string either is a variable name from Z or consists of proper variable names from Z split up by single * characters.

The solution should print all possible ways to parse the input.
Examples:
Vars           a, c, ab, bc
Term           abc
Solution       ab*c, a*bc

Vars           ab, bc
Term           abc
Solution       -

Vars           -
Term           xyz
Solution       -

Vars           xyz
Term           xyz
Solution       xyz

Vars           width, height
Term           widthheight
Solution       width*height

Vars           width, height
Term           widthheightdepth
Solution       -

Vars           aaa, a
Term           aaaa
Solution       aaa*a, a*aaa, a*a*a*a

The input (the list of variables and the term) may be supplied in any way suitable for the language.
The output can be in any sensible form (one result per line or a comma-separated list etc.) - but it should be unambiguous and possible to read.
Empty output is acceptable if there is no possible parsing of a term (in the examples I used '-' for clarity).
This is code-golf, so the shortest code wins.

In your first example, I believe ab*c is an incorrect parse, since c is not an allowed variable.

With a recursive scan I find exactly your result in the sample. But it's questionable: why a*aaa aaa*a and not ab*c c*ab

Because of rule 1. of parsing. Yes, multiplication is usually commutative, but we don't go so far - we just want to "reconstruct" multiplication in the order it was done. Actually in Jack's language we could have a matrix type - the multiplication is not commutative then. And "aaaa" can be both juxtaposition of "aaa" and "a" or "a" and "aaa" - this not for commutativeness, rather for ambiguity we are taking both into account.

Exact duplicate of http://codegolf.stackexchange.com/questions/45496/insertspacesbetweenwords

Pyth, 18 chars
mj\*dfqzsTsm^Qkhlz

This solution is adapted from my Interpreting Fish
solution. The problems are actually very similar.
Expects input as such:
aaaa
"a", "aaa"

Gives output like this:
['a*aaa', 'aaa*a', 'a*a*a*a']

Try it here.

sm^Qkhlz: Generates all sequences of variables containing up to the length of the input string number of variables.
fqzsT: Filters out the variable sequences that match the input string
mj\*d: Inserts the * symbol and prints.

Python 2 - 147 94 bytes

R=lambda S,V,F=[]:S and[R(S[len(v):],V,F+[v])for v in V if v==S[:len(v)]]or print("*".join(F))

This defines a function R to be used like:
>>> R("abc", ["a", "bc", "ab", "c"])

Prints output like:
a*bc
ab*c

JavaScript (ES6) 111
Adapted from my "fish" answer, the main difference is finding all solutions, not just the first.
F=(v,t)=>(k=(s,r)=>s?v.map(v=>s.slice(0,l=v.length)==v&&k(s.slice(l),[...r,v])):console.log(r.join('*')))(t,[])

The output is printed to the console. The function result have no meaning and must be discarded.
Test In Firefox/FireBug console
F(['a','c','ab','bc'],'abc')
a*bc
ab*c

F(['ab','bc'],'abc')

F(['aaa','a'],'aaaa')
aaa*a
a*aaa
a*a*a*a

F(['xyz'],'xyz')
xyz