text:
Find the largest contiguous prime in a string
In fairness, this is based on a StackExchange question - but its a good question.
The challenge is fairly simple:

Take a string of numerals
Find and print the largest contiguous prime number in the string

Scoring:

Lowest number of characters wins.
Victor will likely be a golfscript entry but we won't hold that against them, cause we all have fun and learn things, right.
Winner we be awarded when I notice that I haven't actually ticked the green button.

Assumptions:

The string is only numbers

If the string contains letters, you may have undefined behaviour

The string contains at least 1 prime

If the string does not contains 1 valid prime number, you may have undefined behaviour

Speed is not a constraint

Use a shorter prime algorithm over a faster one.
If your entry eventually finishes, thats ok, just make sure it will provable happen before the heat death of the universe.

The length of the string can be assumed less than 15 characters long

For example:
>> Input:  3571
<< Output: 3571

>> Input:  123
<< Output: 23

>> Input:  1236503
<< Output: 236503

>> Input:  46462
<< Output:  2

>> Input:  4684
<< Output: ValueError: max() arg is an empty sequence

>> Input:  460
<< Output: 0   # Note, zero is not a prime, but the above string has no valid prime

>> Input:  4601
<< Output: 601

>> Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
<< Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.

Possible implementations:

Find all substrings of the input, check if they are prime. - Legostormtroopr (original)
Find all integers less than input, check if they are in the input then check if it is prime - Ben Reich
Take a list of all primes less than the input, check if it is in the input - daniero

This seems basically like: find a way of iterating over each substring of the string, and check the primality of the substring. Sounds like a fun problem.

@Quincunx Correct. But I wanted to make it as unambiguous as possible. And also drop pop-culture references.

@Quincunx That's not the only possible algorithm, though!  Check out my answer, which can be described as: Iterate over all integers less than the input, and determine the largest one that is both a substring of the input and is prime.

@BenReich Or as I did, iterate over all primes less than or equal to the input in and see of they are in the string.

Regarding proof that a given program will finish before the heat death of the universe: For strings of what size? Currently, you've not defined an upper bound. For that matter, what's the largest prime we need to be able to identify?

@Iszi I've added a constraint for timing purposes, where we assume the string is less than 15 characters.

You might also want to add a constraint against referencing any list of primes (or state that such list must be included in the character count).

@Iszi Not sure why? The Prime module in Daniero's answer is part of the standard package.

@LegoStormtroopr To even the playing field a bit. For many (most?) languages, a list of primes is not quite so built-in. Or are you allowing us to include our own lists as a call to a web reference or local text file without including that in the source?

Why do I care about an even playing field? We know which scripts win, but winning isn't everything? Make the shortest, cleverest code possible you can in your favourite language.

@LegoStormtroopr Can you add a test case to the end which ensures entire numbers (like 3571) are also tested and not just substrings? I've sent an edit request and it's awaiting peer review.

GolfScript 40 37
.{`\`?)}+\~),\,{.,(;\{\%!}+,,1=},)\;

This looks at all numbers less than or equal to the the input, filters down to the ones that are substrings of the input, and then filters further down to the primes.  Then, it takes the largest such element (which is obviously guaranteed to have the most digits).
Let's break it down into two main sections:
.{`\`?)}+\~,\,

This part of the code filters down to all integers string contained in the input.  It uses grave accent to turn numbers into strings, and then ? to determine the index of the substring.  Since ? returns -1 in the case of no containment, increment using ) so that the output is 0 for non-substrings, which will behave nicely with the , filtering.
{.,(;\{\%!}+,,1=},

This part of the code filters down to the primes by counting the number of factors less than the given number (an integer is a factor only if number factor %! is 1.  A prime number will have exactly 1 factor strictly less than itself, so do 1=.
Since the numbers are in order, take the last one and clear the stack using )\;
This obviously isn't as efficient as possible (since it somewhat unnecessarily iterates over all integers less than the input), but it still terminates with big input like 1236503 relatively quickly on my computer (1 minute).

Thanks to you I shaved almost as many answer as you used :P

If the input is a prime then this won't find it, because the first filter is applied to numbers up to but not including it. The fix costs one character, but there are two characters to be saved by storing the input in a variable rather than concatenating with the block (because that way you eliminate some flips).

Python 2.7 - 84
Here is a reference implementation to beat, I used it for the example output in the question, so its gauranteed to work * Not an actual guarantee
Shameless improvement based on Ben Reich's much better solution than my original one. With major assistance from Volatility
N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

Prior incantations of the second line include:
print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

The original version - 143
N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))

Get rid of p and replace not p(x) with sum(x%i for i in range(2,x))<1 - it should work and gets you down to 86 chars.

@Volatility Not quite, sum(x%i for i in range(2,x)) will be quite high for most numbers. But the generator is a great idea and I got it to 91.

Actually, you know what, I think you can use all(x%i for i in range(2,x)) instead.

Switching to all and bracketing the (\x`in`N`)` Saves a few more too!

Vyxal G, 4 bytes
ǎ⌊~æ

Try it Online!
Link includes test cases.
Input as a string. Add the Ṡ flag if you want input as a number.
Explanation
ǎ⌊~æ  # Implicit input
ǎ     # Substrings
 ⌊    # Cast to integer
  ~   # Filtered by
   æ  # Is prime
      # G flag gets maximum
      # Implicit output

Haskell, 94
main=getLine>>=print.maximum.filter(\x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]

Care to explain the process behind this for those who don't do Haskell?

@LegoStormtroopr Sure, i try it. main = getLine >>= print . maximum . filter isPrime . map read . allNums is the original form. it gets a line and gives it (>>=) to the big combined function - combined with the . infix operator, who simply puts the result of the right function to the left function. things like (\x -> ...) are lambda expressions. function parameters are applied without parenthesis and functions can be partially applied ((0/=) for example is a function, that checks if a number is not 0).

allNums = init . scanr (:) []. scanr scans and init removes the last value of the result of scanr, which is an empty string, that cant be read to a Integer.
map read reads a list of strings to its destinated values. in this case Integer or something else from the Integral typeclass, because isPrime need a Integral.
filter isPrime does exactly, what it says. isPrime x = and $ map ((0/=). mod x) [2..(x-1)] means, given a list from 2 to (x-1), make the division check and then apply and to the Bool list.

there are some more clear and powerful functions in other standard modules, but i tried to work with the Prelude module only. ;)

Scala (83 chars)
I wasn't sure how to provide inputs to the program so I considered n is the input. Here's the actual solution (based on which the solution length is evaluated). Below that is an executable form of the solution (which isn't golfed yet) for execution along with the output (for the samples give OP has).
Solution:
n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

Executable solution:
object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

Sample output:
3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

Explanation:
Steps are pretty straight forward.
input -> Find all substrings -> filter non primes -> find longest value

main(Array[String]): Method provides sample input and executes method q(String) for each input
q(String): Wraps actual program logic from p(String) so any exceptions are appropriately reported. Helps in formatting the output better because invalid inputs are going to get NumberFormatExceptions where as the lack of a prime will throw an UnsupportedOperationException
p(String): Actual logic of the program. Let's split the explanation for this into parts

n.inits: Creates an Iterator to iterate over the String input (n)
flatMap(f): Applies an operation on the Iterator and pushes the result into a List

_.tails.toList.init.map(BigInt(_)): Splits the String and removes empty Strings from the resultant List. Finally converts the String to a BigInt which is an equivalent of java.math.BigInteger. For golfing reasons, BigInt is selected (shorter name).

filter(f): if f returns false, the value is removed from the resultant List

_ isProbablePrime 1: This line could have been written as _.isProbablePrime(1) but the representation used saves 1 byte. This line actually checks if the value is a prime (probabilistically; since certainty is set to 1, execution time goes up but the system makes certain (more or less) that the number is a prime.

max: Finds the maximum value (not String based length. Actual max value)

J (24 22)
Reading from the keyboard is actually shorter than defining a function.
>./(*1&p:);".\.\1!:1[1

Test:
   >./(*1&p:);".\.\1!:1[1
3571
3571
   >./(*1&p:);".\.\1!:1[1
46462
2
   >./(*1&p:);".\.\1!:1[1
1236503
236503
   >./(*1&p:);".\.\1!:1[1
4684
0
   >./(*1&p:);".\.\1!:1[1
4680
0
   >./(*1&p:);".\.\1!:1[1
twelve monkeys is a pretty good movie
__

Explanation:

1!:1[1: read a line of text from the keyboard
".\.\: the evaluation (".) of each suffix (\.) of each prefix (\) of the string.
;: flatten the matrix
*1&p:: multiply each value by whether it is a prime or not (so all nonprimes will be zero)
>./: get the largest value in the list

Ruby 61
Take all primes up to N and see if they are in the string
require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

I think this only works on Ruby 1.9 and newer, but I'm not sure.

What does your program return for the last test example? The prime, 2, is in it, but should not be recognized (if I understand the requirements correctly).

@DavidCarraher: Assumptions:
The string is only numbers; If the string contains letters, you may have undefined behaviour I think that "undefined behaviour" means that it could spit out 2 or it could spit out mush

Kyle, Very good observation!

Perl 6 (40 characters, 41 bytes)
$_=get;say max grep &is-prime,+«m:ex/.+/

First get input into $_, this makes the regex match call shorter. :ex gives exhaustive matching for regex, it will give all possibilities. The hyper op +« (or +<< works too) will make numbers out of the Match objects, those are passed to grep with &is-prime sub as selector. Finally take the maximum of the remaining list and output it.

Jelly, 6 bytes
DẆḌẒƇṀ

Try it online!
Takes input as an integer. If input must be a string, then 7 bytes. Returns 0 for numbers with no primes in them.
How it works
DẆḌẒƇṀ - Main link. Takes n on the left
    Ƈ  - Find...
     Ṁ - ...the largest...
 Ẇ     - ...contiguous...
  ḌẒ   - ...prime...
D      - ...in a string

or, alternatively,
DẆḌẒƇṀ - Main link. Takes n on the left
D      - Convert n to digits
 Ẇ     - Get all contiguous sublists
  Ḍ    - Convert each back from digits
    Ƈ  - Filter keep:
   Ẓ   -   Primes
     Ṁ - Yield the maximum

PowerShell, 170 bytes
I'm sure there is a better way of doing this...
$v.count..1|%{
	$d=$_
	0..(-$d+$v.count)|%{
		$n=$v[$_..($_+$d-1)]-join""
		$a=@()
		1..[math]::sqrt($n)|%{$a+=$_,($n/$_)*!($n%$_)}
		if($a.count-eq2){$b+=$n}
	}
}

$b[0]

Try it online!

05AB1E, 5 bytes
Œʒp}Z

Try it online!
Explanation
Œʒp}Z  # Implicit input
Œ      # Substrings
 ʒ }   # Filtered by
  p    # Is prime
    Z  # Maximum
       # Implicit output

Perl 6 (50 characters, 51 bytes)
say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

+« maps strings to numbers, max gets the biggest number, get receives a line. /(.+)<?{(+$0).is-prime}>/ is a regular expression that gets all primes <?{}> is a code assertion. is-prime is Int class method which checks if number is a prime. I need to cast value to number by using +, because it's Str by default. :ex means that it tries to find ALL matches (including those where overlap others). Because of Rakudo Perl bug, it's currently impossible to use m// here.
This works for any number, and if you remove max (or replace it with sort) you will get list of all primes in the number, for extra bonus (not that this gives points, or anything). For example (with sort in this case):
1234567890
2 3 5 7 23 67 89 4567 23456789

Mathematica 67 47
StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

Explanation
The code is a pure function. It has no name.
In it, # represents the full input string.
StringCases takes the input, #, and checks for substrings, a, of one character or more (that's why __ was used instead of _) that are primes; PrimeQ must return True for the substring.
All the favorable cases, i.e. the substrings that are primes, are by default returned in a list.  〚1〛, or [[1]] takes the first part, that is, the first element of that list of primes. element[[1]] is shorthand for Part[element, 1].  If there is more than one prime, the first one will be the longest prime (StringCases checks the longest substrings first).
Examples
StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

"236503"

StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@
{"1236503", "123", "46462", "4684", "460", "4601",
"12 monkeys is a pretty good movie, but not as good as se7en"}

{"236503", "23", "2", {}[[1]], {}[[1]], "601", "2"}

Care to explain the process behind this for those who don't do Mathematica?

I must say that usage of 〚1〛 characters was sadistic on us, non-mathematica, programmers. (cue me frantically worried that I'm going blind, then looking at other brackets with confusion that they look sharp, while this one isn't!)

〚1〛has double brackets and is equivalent to [[1]].  I used them because a double bracket counts as a single character.

@David Carraher Yeah, but I think you have to count it as two bytes so it doesn't really save you anything.

But I'm counting characters, not bytes.  Please explain.

Japt -h, 6 bytes
ã f_°j

Try it

Husk, 6 bytes
→fṗmrQ

Try it online!

Arturo, 50 bytes
$[s][last select..1do s'x->∧prime? x in?~"|x|"s]

Try it

PARI/GP, 212 bytes
Try it online!
ss(s,n,m)=concat(Vec(s)[n..n+m-1])
ivn(s)={my(v=Vecsmall(s));for(i=1,#s,if(v[i]<48||v[i]>57,return(0)));1}
ips(s)={my(l=#s);for(i=1,l,for(j=1,i,my(st=ss(s,j,l+1-i));if(ivn(st)&&isprime(eval(st)),return(st))));""}

Ungolfed version
substring(s,n,m)=concat(Vec(s)[n..n+m-1])
is_valid_number(s) = {
  my(vec_s = Vecsmall(s));
  for (i = 1, #s, if (vec_s[i] < 48 || vec_s[i] > 57, return(0)));
  return(1);
}
is_prime_string(s) = {
  my(len = #s);
  for (i = 1, len,
    for (j = 1, i,
      my(substr = substring(s, j, len+1-i));
      if (is_valid_number(substr) && isprime(eval(substr)), return(substr));
    )
  );
  return("");
}
strings = ["1236503", "123", "46462", "4684", "460", "4601","12 monkeys is a pretty good movie, but not as good as se7en"];
ans = vector(#strings, i, is_prime_string(strings[i]))
print(ans)

source: Stack Exchange

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

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

sort: votes


text:
One Line Aquarium
My parents-in-law have a fishpond in their yard, filled with koi. It didn't really cross my mind until I noticed the following extract from my code.
',') & '_'
... I had fish-faces looking back at me from my screen...
Which has given me a great idea...
My quest for you, my dear golfers is to create a one-line ASCII aquarium, with the following rules:

The size of the aquarium from side of the tank to the other side of the tank should be no smaller than 60 characters and no bigger than 80 characters. Sides of the tank need to be indicated using the pipe/bar (|) character.
Fish must be able to "swim" left to right between the sides of the tank. As they will be turning, a front view is required for the transition from one direction to the other.
The fish must look like the following:

}}< }} ',') Fish swimming right
(',' {{ >{{ Fish swimming left
}}('_'){{ Fish facing the front

When a fish turns to change direction (30% chance), it must start from one direction, face the front, then face the other direction... Make sure there is ample room for the fish to turn, i.e. requires six spaces before the edge of the tank minimum...
Unless a fish is blowing a bubble or changing direction, it will continue in the direction it is facing, if it gets within six spaces of the side of the tank, it will change direction.
The fish (facing left or right) can on occasion (10% chance) stop to blow bubbles in succession (.oO*), so the fish is required to have a space available next to them in order for the bubble to exist, so a fish can only swim as close to the sides, save one space. The bubble must disappear before the fish can move on...

A series of example lines of the fish's behavior, with - characters indicating the spaces, as the code display feature on here is a little strict... I will expect these dashes to be replaced with spaces when you code this...
Each line here could be considered a frame in time-lapse.
|-}}< }} ',')----------|
|--}}< }} ',')---------|
|---}}< }} ',')--------|
|----}}< }} ',')-------|
|-----}}< }} ',')------|
|-----}}< }} ',').-----|
|-----}}< }} ',')o-----|
|-----}}< }} ',')O-----|
|-----}}< }} ',')*-----|
|---------}}('_'){{----|
|-----------(',' {{ >{{|
|----------(',' {{ >{{-|
|---------(',' {{ >{{--|
|--------.(',' {{ >{{--|
|--------o(',' {{ >{{--|
|--------O(',' {{ >{{--|
|--------*(',' {{ >{{--|
|--------(',' {{ >{{---|
|-------(',' {{ >{{----|
|------(',' {{ >{{-----|

etc. The above example is, as I said, small, but you get the general idea...
Shortest code wins...
I am expecting the output on the same line (if possible), if not, displaying frame after frame in succession is fine... Whether you go one line or multiple lines is up to you. If you are doing multiple lines, they must be separated by a newline.
Also a timer is imposed between frames, 2000ms . This is mandatory.
Let's see what you've got!

If the fish gets too close to the edge of the aquarium, is it required to turn, or it may phase out of the screen? Must it be possible that the fish blows bubbles in this situation? Also, must it be possible (or is it forbidden, or is allowed but not required) for the fish to blow bubbles twice in succession?

Are we allowed to leave old frames on the screen? If not, then the set of languages able to compete is rather limited.

@JanDvorak Just quoting the bullet point I made: "Unless a fish is blowing a bubble or changing direction, it will continue in the direction it is facing, if it gets within six spaces of the side of the tank, it will change direction."
So if it gets within six spaces of the side of the tank it is required to change direction. It is also possible that a fish may blow bubbles twice...

OK, thanks. Golfscript is out due to the timing requirements, so, which language should I choose? :-)

@JanDvorak Old frames can be left on the screen, I have updated my OP accordingly... I would suggest anything with a timing capability ;) JavaScript, PHP, PERL, C, etc.

Javascript was my first idea, but the timing makes a bit of overhead...

Okay, I may have to alter this considerably...

@JanDvorak Okay, I have changed this to 100 frames of the aquarium's output...
You reckon GolfScript can still be used?

Wait, no, don't do changes like this! I've already started coding! Would you mind rolling back?

Please use the sandbox the next time.

Really? I wanted this to be simpler for everyone... You were right, setting a timer is too much overhead...
I can't leave GolfScript in the corner...

@JanDvorak I'll remember the sandbox for next time, promise.

Uh, no, most languages can just do sleep(2) or a similar (and this would be the first time I use a function while golfing, and i like it). And Golfscript deserves to be left out.

Dammit... Okay, I'll roll it back... About time we had a real code golf challenge...

Thanks :-) (be sure to include the information that old frames can be left on the screen but they must be separated by a newline)

Done! You're right, I should have sandboxed this first! LOL

It's not explicitly stated, but I guess there must be exactly one fish in the aquarium?

How is the size of the aquarium counted? The count of the hyphens + fish-chars in the middle? Wall-to-wall distance? 60..80 characters including the walls?

@JanDvorak I assume including the walls.

@JanDvorak One fish only; it's easier ;)
Also one side of the tank counts as character 1, and the other side of the tank is x where x is a number between 60 and 80 (inclusive)

Amazing, so my aquarium is within tolerance :-) Now to get the fish moving :-)

So yes, including walls! ;)

Is it required that the fish may bubble twice in succession, or are we allowed to let it happen? It makes a three-character difference for me.

Hmmm, it's okay if it bubbles twice, but like I said, but if it bubbles once, then moves and bubbles again, that's okay too. Just go with your gut @JanDvorak

"the bubble must disappear before the fish can move on" but in your example there's no frame where the bubble is gone and the fish hasn't moved. Which one is true, or are we allowed to do either?

@Eliseod'Annunzio Would you consider having either the timer or n frames of output? I'm working on a SQL version.

@JanDvorak I'd say the bubble must have completed before the fish can move.

Python 3 (278)
Previously: 334, 332, 325, 302, 300, 299, 291, 286, 284, 281
import random,time
r=random.random
F="}}('_'){{%s","}}< }} ',')%s","%s(',' {{ >{{"
p,d=9,1
c=b=0
while 1:
 if c:p-=c+c*3*(2*d+c==1);d=c-c*d*d;c-=d
 elif b%5:b+=1
 elif.3>r()or{p*d}<{-5,53}:c=-d
 elif.1>r():b=1
 else:p+=d
 print('|%-70s|'%(' '*p+F[d])%' .oO*'[b%5]);time.sleep(2)

Golfing in Python is always difficult due to the indentation requirements of statements, but despite that, this went incredibly well!
Big thanks to Volatility and DSM for helping me golf this so much further.
Clean version
from random import random as r
from time import sleep as s
F = { 1: "}}< }} ',')%s", 0: "}}('_'){{%s", -1: "%s(',' {{ >{{" }

# p: position (from left)
# d: direction (-1: left, +1: right)
# c: changing direction (0: not changing, +1: to right, -1: to left)
# b: bubble (0)
p, d, c, b = 9, 1, 0, 0

while 1:
    if c:
        p -= c*[1,4][2*d+c==1]
        if d:
            d = 0
        else:
            d, c = c, 0
    elif b % 5:
        b += 1
    else:
        # change direction
        if r() < .3 or p * d in (-5,53):
            c = -d
        # start bubbling
        elif r() < .1:
            b = 1
        # move forward
        else:
            p += d

    # print fish and sleep
    print('|{:<70}|'.format(' '*p+(F[d]%' .oO*'[b%5])))
    s(2)

Ruby, 291 289
l="(',' {{ >{{";m="    }}('_'){{    ";r="}}< }} ',')";w=?\s;s=w*6;q="|#{r+s*9}|"
f=->*s{(puts q;sleep 2)if q.sub! *s}
loop{rand>0.1||(f[") ",")."]||f[" (",".("];f[?.,?o];f[?o,?O];f[?O,?*];f[?*,w])
q[7]==?(||q[-8]==?)||rand<0.3?f[s+l,m]&&f[m,r+s]||f[r+s,m]&&f[m,s+l]:f[w+l,l+w]||f[r+w,w+r]}

The fish is eleven characters long, making the aquarium 6*9+11+2 = 67 characters wide, which fits neatly in the required tolerance.
The f lambda function does all the heavy lifting: it accepts a substitution as a pair of arguments, then attempts to apply the substitution on the aquarium. If it succeeds, it paints one frame of the animation. It then reports the success value as 2 (the delay taken) or nil (delay not executed).
Fish will not blow bubbles twice in succession. (Fix: ...while rand>0.1 - 4 characers)
Fish may blow bubbles even before a forced turn. (Fix: rearrange the branching structure)
There is a frame where the bubble is completely gone (including the *) but the fish has not moved into the resulting void. This follows the letter, but not the example. (Fix: replace f[?*,w] with q[?*]=w - free)
Does not clear the console. Fix: add `clear` (Unix) or system 'cls' (Windows console) before puts q to fix (Ref.) or use print instead of puts and prepend \r to the aquarium (suggested by @manatwork).
Readable version:
# l - left fish; m - middle fish + space; r - right fish
# w - single space character; s - six spaces; q - the aquarium
l="(',' {{ >{{"; m="    }}('_'){{    "; r="}}< }} ',')";
w=" "; s=w*6; q="|#{r+s*9}|"
f = ->k,v do
  if q.sub! k,v
    puts q
    sleep 2
    return 2
  else
    return nil
  end
end

loop do
  if rand < 0.1
    f[") ",")."] || f[" (",".("]
    f[?.,?o]; f[?o,?O]; f[?O,?*]; f[?*,' ']
  end
  if q[7] == "(" || q[-8] == ")" || rand < 0.3
    (f[s+l,m] && f[m,r+s]) || (f[r+s,m] && f[m,s+l])
  else
    f[w+l,l+w] || f[r+w,w+r]
  end
end

I would add \r to the beginning of q: q="\r|#{r+s*9}|". Then use $><<q instead of puts q. Is 1 character longer, but looks better without using external commands.

\r clears the screen? It doesn't in my case. Or, why don't you like puts?

No, \r is carriage return. By using $><<q for output the cursor will stay in the same line (puts forces a \n after the output) so starting the next output with \r will jump back to the beginning of the current line and start to output from there. Thus overwrites the aquarium line's previous “image”.

@manatwork unfortunately, this completely messes up the jRuby interactive window, which ignores the \r.

Oh. Sorry to hear that. And thank you for the information. Sadly this is the first fact I learn about jRuby. :(

Perl, 281
@f=("s O(',' {{ >{{","s}}('_'){{s","}}< }} ',')O s");$d=1;@o=split//," *Oo. ";{$_="|".$"x$x.$f[$d+1].$"x(44-$x).'|
';s/O/$o[$b]/;s/s/    /g;print;if($b||$t){$b--if$b;if($t){$d+=$t;$t=0if$d}}else{$x+=$d;$t=($x<1)-($x>43);if(!$t){$b=5if.9<rand;if(.7<rand){$t=-$d;$b=0}}}sleep 2;redo}

or more clearly
@f = ( "s O(',' {{ >{{", "s}}('_'){{s", "}}< }} ',')O s" );
$d = 1;
@o = split //, " *Oo. ";
{
    $_ = "|" . $" x $x . $f[ $d + 1 ] . $" x ( 44 - $x ) . '|
';
    s/O/$o[$b]/;
    s/s/    /g;
    print;
    if ( $b || $t ) {
        $b-- if $b;
        if ($t) { $d += $t; $t = 0 if $d }
    }
    else {
        $x += $d;
        $t = ( $x < 1 ) - ( $x > 43 );
        if ( !$t ) {
            $b = 5 if .9 < rand;
            if ( .7 < rand ) { $t = -$d; $b = 0 }
        }
    }
    sleep 2;
    redo
}

Fish turning correctly. Bubbles blowing.
285 - if you like the real aquarium feel and not the scrolling version:
$|=@f=("s O(',' {{ >{{","s}}('_'){{s","}}< }} ',')O s");$d=1;@o=split//," *Oo. ";{$_="\r|".$"x$x.$f[$d+1].$"x(44-$x).'|';s/O/$o[$b]/;s/s/    /g;print;if($b||$t){$b--if$b;if($t){$d+=$t;$t=0if$d}}else{$x+=$d;$t=($x<1)-($x>43);if(!$t){$b=5if.9<rand;if(.7<rand){$t=-$d;$b=0}}}sleep 2;redo}

Where do you do turning? I can't see you setting $d=0 in the "required turning" case.

sleep2 (without space) is not working for me; also when you are turning, you don’t keep the fish face aligned. And the bubbles seem to never appear.

"Also a timer is imposed between frames, 2000ms . This is mandatory." - this doesn't happen at all for me. Also, bubbles don't appear, the fish just sits in place. Also, the head should stay in place while the fish is turning, not the body center (at least that's what the example shows)

Drat! Golfed too Hard. Need an extra space with sleep! Fish was bubbling nicely too! hang on...

Oops - forgot the head in the middle when turning at the edges - need some rework...

OK. Think I have it this time. Thanks for pointing out the horrendous errors. Going to bed!

The head is still not aligned correctly when turning; and I believe you should pause once before starting the bubble.

$b=5 sorts out the bubbles. Not too sure how to turn the fish to align the tail properly. Do all the other entries do this?

Ruby, Python and C do this, yes, as does the fish in OP’s example.

Hmmmm probably need to go back to the drawing board on this one!

@KevinColyer my entry doesn't do that either: the pivot when turning is the mid-lenth of the fish so that it occupy the same space before and after the turn. Didn't thought it was a specification.

@plannapus - works now though!

R, 451 characters
A first attempt:
f=function(j,p){cat("\r|",rep("-",j),p,rep("-",50-j),"|",sep="");Sys.sleep(2)};d=F;j=5;P=c("--}}(\'_\'){{--","-}}< }} \',\')-","-(\',\' {{ >{{-");B=c("-",".","o","O","*","-");g=Vectorize(gsub,v="replacement");b=list(g("-$",B,P[2]),g("^-",B,P[3]));repeat{if(j<5 & d){d=!d;j=j+1;f(j,P[1])};if(j>44 & !d){d=!d;f(j,P[1]);j=j-1};if(runif(1)<.1){for(i in b[[d+1]])f(j,i)}else{f(j,P[d+2])};if(runif(1)<.3){d=!d;f(j,P[1]);f(j,P[d+2])};if(d){j=j-1}else{j=j+1}}

Indented:
f=function(j,p){ #Printing function (depends of buffer and kind of fish)
    cat("\r|",rep("-",j),p,rep("-",50-j),"|",sep="")
    Sys.sleep(2)
}
d=F   #Direction: if FALSE left to right, if TRUE right to left.
j=5   #Buffer from left side of tank
P=c("--}}(\'_\'){{--","-}}< }} \',\')-","-(\',\' {{ >{{-") #The fish
B=c("-",".","o","O","*","-") #The bubble sequence
g=Vectorize(gsub,v="replacement")
b=list(g("-$",B,P[2]),g("^-",B,P[3])) #Fish+bubble
repeat{
    if(j<5 & d){ #What happens if too close from left side
        d=!d
        j=j+1
        f(j,P[1])
        }
    if(j>44 & !d){ #What happens if too close from right side
        d=!d
        f(j,P[1])
        j=j-1}
    if(runif(1)<.1){ #If bubble sequence initiated
        for(i in b[[d+1]])f(j,i)
        }else{f(j,P[d+2])} #Otherwise
    if(runif(1)<.3){ #If fish decide to turn
        d=!d
        f(j,P[1])
        f(j,P[d+2])
    }
    if(d){j=j-1}else{j=j+1} #Increment or decrement j depending on direction
}

It prints the aquarium as stdout on a single line (then 2s break and carriage return before the aquarium at t+1 is printed).

C, 400 394 373 characters
#define p printf
#define a(x) l[5]=r[11]=x;d();
char *l="      (',' {{ >{{",*f="    }}('_'){{    ",*r="}}< }} ',')      ",*c,s=7,i,*T;d(){p("|");for(i=0;i<s;i++)p(" ");p(c);for(i=0;i<70-s;i++)p(" ");puts("|");sleep(2);}b(){a(46)a(111)a(79)a(42)a(32)}t(){T=c;c=f;d();c=T==r?l:r;d();}m(){c==l?s--:s++;d();s>69||s<1?t():0;}main(){c=r;for(d();;)i=rand()%10,i?i>6?t():m():b();}

With whitespace:
#define p printf
#define a(x) l[5]=r[11]=x;d();
char *l="      (',' {{ >{{",
     *f="    }}('_'){{    ",
     *r="}}< }} ',')      ",
     *c,
     s=7,
     i,
    *T;
d(){
  p("|");
  for(i=0;i<s;i++)
    p(" ");
  p(c);
  for(i=0;i<70-s;i++)
    p(" ");
  puts("|");
  sleep(2);
}
b(){
  a(46)
  a(111)
  a(79)
  a(42)
  a(32)
}
t(){
  T=c;
  c=f;
  d();
  c=T==r?l:r;
  d();
}
m(){
  c==l?s--:s++;
  d();
  s>69||s<1?t():0;
}
main(){
  c=r;
  for(d();;)
    i=rand()%10,
    i?i>6?t():m():b();
}

Can i==l?(c=r):(c=l) be shortened to c=i==l?r:l?

You can save a few characters by #define p printf(

@Ace gcc doesn't like it when I do that.

it works for me. http://oi41.tinypic.com/15fqbvb.jpg

Looks like it will stop after 8 lines, generating a "Bus error: 10" on my iMac (using gcc -o to compile).

It looks like I'm going to have to change the char* to char[] to increase cross-system compatibility.  I was hoping to golf this down to 349 characters, but we will see if that materializes.

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


text:
Create Balanced BST from Sorted List of Integers
Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion.
For example:
func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]

Before we start, a hint: we can simplify this problem a ton so that we don't actually have to think about the input integers (or any comparable object for that matter!).
If we know the input list is sorted already, it's contents are irrelevant. We can simply think about it in terms of indices into the original array.
An internal representation of the input array then becomes:
func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]

This means rather than writing something that has to deal with comparable objects, we really only need to write a function which maps from the range [0,n) to the resulting array. Once we have the new order, we can simply apply the mapping back to the values in the input to create the return array.
Valid solutions must:

Accept a zero-element array and return an empty array.
Accept an integer array of length n and return an integer array

Of length between n and the next highest power of 2 minus 1. (e.g., for input size 13 return anywhere between 13 and 15).
Array which represents a BST where the root node is at position 0 and the height is equal to log(n) where 0 represents a missing node (or a null-like value if your language allows). Empty nodes, if present, must only exist at the end of the tree (e.g., [2,1,0])

The input integer array has the following guarantees:

Values are 32-bit signed integers greater than zero.
Values are unique.
Values are in ascending order from position zero.
Values may be sparse (i.e., not adjacent to each other).

The most terse code by ascii character count wins, but I'm also interested in seeing elegant solutions for any particular language.
Test cases
The outputs for simple arrays containing 1 to n for various n. As described above, the trailing 0s are optional.
[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]

All questions on this site, whether a programming puzzle or a code golf, should have an objective primary winning criterion, so that it is possible to indisputably decide which entry should win.

@Howard Thanks. Updated with definitive criteria for winner.

It would be very useful to have some test cases which cover the difficult cases, rather than (as at present) just the easiest one.

Is there some reason for ruling out recursion? Not that I'm looking at a recursive solution, but that seems both artificial and unnecessary.

@dmckee I had hoped it would steer people towards figuring out a function which maps indices from the input array to the output array directly. Maybe I should post my solution...

Funny. I've actually been seriously researching this problem to improve cache behavior of binary searches in a very large amount of data (how to map the index of an array so that a binary search "middle" ends up in the first element, then second or third, etc.). The idea was that since the first few compares would end up in the beginning of the arrays it would avoid at least a few cache misses (and TLB misses later). Reversing the order of the bits in the index actually kind of worked, but I dropped it after figuring out regularity of the data and implementing interpolation search instead.

Can someone explain how the list represents a BST?

Ruby, 143
s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)>(3<<k)?b+(2<<k)-1:e-(1<<k);r<<ARGV[m];q<<[b,m]<<[m+1,e]};p r

It is a (loosely) compressed version of the following code which basically does a BFS on the tree.
def l(n)
    k = Math::log2(n).to_i-1
    if n+2 > (3<<k) then
        (2<<k)-1
    else
        n-(1<<k)
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result << tab[m]
    queue << [b,m] if b < m
    queue << [m+1,e] if m+1 < e
  end
  result
end

p bfs(ARGV)

Besides, because it's BFS, not DFS, a requirement of non-recursive solution is not significant, and it puts some languages at a disadvantage.
Edit: Fixed solution, thanks to @PeterTaylor for his comment!

@PeterTaylor The intention was to put 3 on the left of 4, but there are no blanks, so it is wrong. Thanks for pointing that out!

@PeterTaylor Fixed over the lunch, it should work now.

Java, 252
Ok, here is my attempt. I've been playing around with bit operations and I came up with this direct way of calculating the index of an element in the BST from the index in the original array.
Compressed version
public int[]b(int[]a){int i,n=1,t;long x,I,s=a.length,p=s;int[]r=new int[(int)s];while((p>>=1)>0)n++;p=2*s-(1l<<n)+1;for(i=0;i<s;i++){x=(i<p)?(i+1):(p+2*(i-p)+1);t=1;while((x&1<<(t-1))==0)t++;I=(1<<(n-t));I|=((I-1)<<t&x)>>t;r[(int)I-1]=a[i];}return r;}

The long version follows below.
public static int[] makeBst(int[] array) {
  long size = array.length;
  int[] bst = new int[array.length];

  int nbits = 0;
  for (int i=0; i<32; i++)
    if ((size & 1<<i)!=0) nbits=i+1;

  long padding = 2*size - (1l<<nbits) + 1;

  for (int i=0; i<size; i++) {
    long index2n = (i<padding)?(i+1):(padding + 2*(i-padding) + 1);

    int tail=1;
    while ((index2n & 1<<(tail-1))==0) tail++;
    long bstIndex = (1<<(nbits-tail));
    bstIndex = bstIndex | ((bstIndex-1)<<tail & index2n)>>tail;

    bst[(int)(bstIndex-1)] = array[i];
  }
 return bst;
}

You need a character count, and this is not currently golfed.

@dmckee I've edited the post to include a compressed version and a character count

Good show. I'll bet that some of those spaces are unnecessary. In c, int[] b(int[] a) is just as well expressed as int[]b(int[]a).

You have a.length in the array allocation. Change it to s. Get rid of space between for ( multiple times. Each for loop creates a int i=0 and also int t=0. Create with n (int n=0,i,t;) and then just i=0 in the loops and t=1 inside. Declare the inner long x and long I with s and just initialize in the loop (long s=a.length,I,x; and x=../I=..). You shouldn't need spaces around the binary AND &.

Also, I=I|.. can be written I|=..

I've shortened my code a bit further, thanks to all the suggestions. Using s in the array allocation needs a cast to int, so it doesn't save that much. But the rest of the optimizations were worth about 15 characters.
I also found a neat optimization for the log2 calculation here

I only looked at your answer after I posted mine. It seems we took more or less the same approach.

def fn(input):
    import math
    n = len(input)
    if n == 0:
        return []
    h = int(math.floor(math.log(n, 2)))
    out = []
    last = (2**h) - 2**(h+1) + n

    def num_children(level, sibling, lr):
        if level == 0:
            return 0
        half = 2**(level-1)
        ll_base = sibling * 2**level + lr * (half)
        ll_children = max(0, min(last, ll_base + half - 1) - ll_base + 1)
        return 2**(level-1) - 1 + ll_children

    for level in range(h, -1, -1):
        for sibling in range(0, 2**(h-level)):
            if level == 0 and sibling > last:
                break
            if sibling == 0:
                last_sibling_val = num_children(level, sibling, 0)
            else:
                last_sibling_val += 2 + num_children(level, sibling - 1, 1) \
                    + num_children(level, sibling, 0)
            out.append(input[last_sibling_val])
    return out

Golfscript (99 89)
~]:b[]:^;{b}{{:|.,.2base,(2\?:&[-)&2/]{}$0=&(2/+:o[=]^\+:^;|o<.!{;}*|o)>.!{;}*}%:b}while^p

Basically a straight port of my Python solution, works in pretty much the same way.
Can probably be improved quite a bit with more "golfisms", already improved by 10 characters with @petertaylor's input :)

I think it should be possible in no more than 70, although I still haven't quite finished my GolfScript answer. There are some easy improvements to yours, though. !{;}{}if can just be !{;}* because ! guarantees to return 0 or 1. You can use non-alphabetic tokens for variables, so if you use ^ instead of r, | instead of x, & instead of y you can eliminate all that whitespace.

@PeterTaylor Thanks, didn't know about non alphanumeric variables, still very new to golfscript :)

Not quite sure if this fits exactly your requirement of empty nodes being at the end of the tree and it certainly won't win any prizes for brevity, but I think it's correct and it has test cases :)
public class BstArray {
    public static final int[] EMPTY = new int[] { };
    public static final int[] L1 = new int[] { 1 };
    public static final int[] L2 = new int[] { 1, 2 };
    public static final int[] L3 = new int[] { 1, 2, 3 };
    public static final int[] L4 = new int[] { 1, 2, 3, 5 };
    public static final int[] L5 = new int[] { 1, 2, 3, 5, 8 };
    public static final int[] L6 = new int[] { 1, 2, 3, 5, 8, 13 };
    public static final int[] L7 = new int[] { 1, 2, 3, 5, 8, 13, 21 };
    public static final int[] L8 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35 };
    public static final int[] L9 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56 };
    public static final int[] L10 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56, 91 };

    public static void main(String[] args) {
        for (int[] list : Arrays.asList(EMPTY, L1, L2, L3, L4, L5, L6, L7, L8, L9, L10)) {
            System.out.println(Arrays.toString(list) + " => " + Arrays.toString(bstListFromList(list)));
        }
    }

    private static int[] bstListFromList(int[] orig) {
        int[] bst = new int[nextHighestPowerOfTwo(orig.length + 1) - 1];

        if (orig.length == 0) {
            return bst;
        }

        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.push(orig);

        int counter = 0;
        while (!queue.isEmpty()) {
            int[] list = queue.pop();
            int len = list.length;

            if (len == 1) {
                bst[counter] = list[0];
            } else if (len == 2) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(new int[] { 0 });
            } else if (len == 3) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(getSubArray(list, 2, 1));
            } else {
                int divide = len / 2;
                bst[counter] = list[divide];
                queue.add(getSubArray(list, 0, divide));
                queue.add(getSubArray(list, divide + 1, len - (divide + 1)));
            }
            counter++;
        }

        return bst;
    }

    private static int nextHighestPowerOfTwo(int n) {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

    private static int[] getSubArray(int[] orig, int origStart, int length) {
        int[] list = new int[length];
        System.arraycopy(orig, origStart, list, 0, length);
        return list;
    }
}

Java 192
Maps index in input to index in output
int[]b(int[]o){int s=o.length,p=0,u=s,i=0,y,r[]=new int[s],c[]=new int[s];while((u>>=1)>0)p++;for(int x:o){y=p;u=i;while(u%2>0){y--;u/=2;}r[(1<<y)-1+c[y]++]=x;i+=i>2*s-(1<<p+1)?2:1;}return r;}

Long version:
static int[] bfs(int[] o) {
  int rowCount = 32 - Integer.numberOfLeadingZeros(o.length); // log2
  int slotCount = (1<<rowCount) - 1; // pow(2,rowCount) - 1

  // number of empty slots at the end
  int emptySlots = slotCount - o.length;
  // where we start to be affected by these empty slots
  int startSkippingAbove = slotCount - 2 * emptySlots; // = 2 * o.length - slotCount

  int[] result = new int[o.length];
  int[] rowCounters = new int[rowCount]; // for each row, how many slots in that row are taken
  int i = 0; // index of where we would be if this was a complete tree (no trailing empty slots)
  for (int x : o) {
    // the row (depth) a slot is in is determined by the number of trailing 1s
    int rowIndex = rowCount - Integer.numberOfTrailingZeros(~i) - 1;
    int colIndex = rowCounters[rowIndex]++; // count where we are
    int rowStartIndex = (1 << rowIndex) - 1; // where this row starts in the result array

    result[rowStartIndex + colIndex] = x;

    i++;
    // next one has to jump into a slot that came available by not having slotCount values
    if (i > startSkippingAbove) i++;
  }

  return result;
}

Wolfram Mathematica 11, 175 Bytes
g[l_]:=(x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2);Join@@Table[Cases[l//.{{}->{},b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])},_Integer,{m}],{m,x[l]}])

The function g[l] takes as an input a List (e.g l={1,2,3,4,...}) and returns a List of the desired form. It works as follows:

x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) takes a list and finds the root of the associated BST.

i=Length[a]+1 shortcut for the length of the list
2^Ceiling@Log2[i]/2 upper bound on the value of the root
Min[i-#/2,#]&@(...) Minimum of the two argument where # stands for what is inside the (...)

l//.{...} Apply repeatedly the replacement rules that follow to l
{}->{} Nothing to do (this is the edge case to avoid an infinite loop)
b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b]) Split a List into {{lesser}, root, {greater}}
Cases[...,_Integer,{m}] Take all integers at level (depth) m
Table[...,{m,1,x[l]}] For all m up to x[l] (which is more than necessary actually).

It can be tested by running
Table[g[Range[a]], {a, 0, 15}]//MatrixForm

This implementation does not include trailing zeroes.

Java
This is a direct calculation solution.  I think it works, but it has one pragmatically innocuous side effect.  The array it produces may be corrupt but not in any way that would affect searches.  Instead of producing 0 (null) nodes, it will produce unreachable nodes, that is the nodes will already have been found earlier in the tree during the search.  It works by mapping the indices array of a regular power of 2 size binary search tree array onto an irregularly sized binary search tree array.  At least, I think it works.
import java.util.Arrays;

public class SortedArrayToBalanceBinarySearchTreeArray
{
    public static void main(String... args)
    {
        System.out.println(Arrays.toString(binarySearchTree(19)));
    }

    public static int[] binarySearchTree(int m)
    {
        int n = powerOf2Ceiling(m + 1);
        int[] array = new int[n - 1];

        for (int k = 1, index = 1; k < n; k *= 2)
        {
            for (int i = 0; i < k; ++i)
            {
                array[index - 1] = (int) (.5 + ((float) (m)) / (n - 1)
                        * (n / (2 * k) * (1 + 2 * index) - n));
                ++index;
            }
        }

        return array;
    }

    public static int powerOf2Ceiling(int n)
    {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

}

Here's a more condensed version (just the function and names paired down).  It's still got the white space, but I'm not worried about winning.  Also this version actually takes an array. The other one just took an int for highest index in the array.
public static int[] b(int m[])
{
    int n = m.length;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    int[] a = new int[n - 1];

    for (int k = 1, j = 1, i; k < n; k *= 2)
    {
        for (i = 0; i < k; ++i)
        {
            a[j - 1] = m[(int) (.5 + ((float) m.length) / (n - 1)
                    * (n / (2 * k) * (1 + 2 * j) - n)) - 1];
            ++j;
        }
    }

    return a;
}

Since this is [tag:code-golf], shorten your methods/names/etc to as short as possible; remove all whitespace (and unnecessary methods / material), and insert the character count. Otherwise, your doing great.

@Jake Wharton.  I'd really like to see your direct mapping solution.  I'm not a 100% sure mine works for very large arrays because it relies on a continuous mathematical mapping whose values get rounded.  It certainly seems to work, but I'm not sure how to prove it.

GolfScript (79 77 70 chars)
Since the example in the question uses a function, I've made this a function. Removing the {}:f; to leave an expression which takes input on the stack and leaves the BST on the stack would save 5 chars.
{[.;][{{.!!{[.,.)[1]*{(\(@++}@(*1=/()\@~]}*}%.{0=}%\{1>~}%.}do][]*}:f;

Online demo (note: the app might take a bit of warming up: it timed out twice for me before running in 3 secs).
With whitespace to show the structure:
{
    # Input is an array: wrap it in an array for the working set
    [.;]
    [{
        # Stack: emitted-values working-set
        # where the working-set is essentially an array of subtrees
        # For each subtree in working-set...
        {
            # ...if it's not the empty array...
            .!!{
                # ...gather into an array...
                [
                    # Get the size of the subtree
                    .,
                    # OEIS A006165, offset by 1
                    .)[1]*{(\(@++}@(*1=
                    # Split into [left-subtree-plus-root right-subtree]
                    /
                    # Rearrange to root left-subtree right-subtree
                    # where left-subtree might be [] and right-subtree might not exist at all
                    ()\@~
                ]
            }*
        }%
        # Extract the leading element of each processed subtree: these will join the emitted-values
        .{0=}%
        # Create a new working-set of the 1, or 2 subtrees of each processed subtree
        \{1>~}%
        # Loop while the working-set is non-empty
        .
    }do]
    # Stack: [[emitted values at level 0][emitted values at level 1]...]
    # Flatten by joining with the empty array
    []*
}:f;

Python (175 171)
Fairly condensed, still fairly readable;
def f(a):
 b=[a]
 while b:
  c,t=((s,2**(len(bin(len(s)))-3))for s in b if s),[]
  for x,y in c:
   o=min(len(x)-y+1,y/2)+(y-1)/2
   yield x[o]
   t+=[x[:o],x[o+1:]]
  b=t

It yields the result back, so you can either loop over it or (for display purposes) print it as a list;
>>> for i in range(1,17): print i-1,list(f(range(1,i)))
 0 []
 1 [1]
 2 [2, 1]
 3 [2, 1, 3]
 4 [3, 2, 4, 1]
 5 [4, 2, 5, 1, 3]
 6 [4, 2, 6, 1, 3, 5]
 7 [4, 2, 6, 1, 3, 5, 7]
 8 [5, 3, 7, 2, 4, 6, 8, 1]
 9 [6, 4, 8, 2, 5, 7, 9, 1, 3]
10 [7, 4, 9, 2, 6, 8, 10, 1, 3, 5]
11 [8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7]
12 [8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9]
13 [8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11]
14 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13]
15 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]

@dtldarek His comment seems to be removed, but this seems to pass the test cases now.

I deleted my comment lest people refrain from upvoting @dtldarek's answer because of a comment saying it was buggy.

@PeterTaylor Well, thank you for your consideration ;-)

J, 52 bytes
t=:/:(#/:@{.(+:,>:@+:@i.@>:@#)^:(<.@(2&^.)@>:@#`1:))

function takes a sorted list and returns in binary tree order
notice that trees have identical shape but bottom level is shortened

`1: start with 1
<.@(2&^.)@>:@# iterate by floor of log2 ( length + 1 )
+: , >:@+:@i.@>:@# loop : appends double of last vector with odd numbers 1,3 .. 2*length+1
# /:@{. take only the required number of items and get their sort indices
/: apply those sort indices to the given input

TIO

Python 2, 107 bytes
Golf of Joachim Isaksson's answer, Input is a singleton containing the list.
def f(a):
 for x in a:
	if x:w=len(x);y=1<<len(bin(w))-3;o=min(w-y+1,y/2)+~-y/2;yield x[o];a+=x[:o],x[o+1:]

Try it online!


text:
Find number of rectangles in a 2D byte array
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000111111000000000000000000011111111111111100000000000000000
0000000000000100001000000111111000000011111111111111100000000010000000
0000000000000100001000000111111000000000000000000000011000000000000000
0000000000000111111000000111111000000000000000000000011000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

Your are given a 2 dimensional array of bytes of size m x n.  It is guaranteed that all the bytes are 1's or 0's.
Find the number of rectangles represented by 1's when viewed in 2d, as shown above.
Only fully filled rectangles are considered for counting.
Rectangles must be surrounded by 0's unless they are on edge(1's diagonally touching rectangles are Okay though (see example.)).
For example, in above array there are 5 valid rectangles.
You can use any language.

I think a better way to word it is to say that: rectangles must be surrounded by 0's, or an edge

Done. Thanks for wording it in a better English.

What about 1100\n1100\n0011\n0011 ?

I think that's why I wrote 'adjacent / overlapping'.  These are 2 valid rectangles from my initial intention.  But the 'surrounding' condition is restricting them now. Do you have a better way to explain it

Even at adjacent it's ambiguous whether or not diagonal means adjacent or not. The same ambiguity whether or not surrounded means, surrounded at the corners, or just sides

I'm not sure there is a more succinct way to word it. Probably keep it as is and explicitly state that the corners can be 1's. Or including that case in your example helps as well.

I put my ideas in an edit suggestion

Just for clarification, degenerate rectangles shouldn't be counted, correct? For example, are a single 1 or a single subrow/subcolumn of adjacent 1's invalid?

Yes, they are invalid, and should not be counted.

So far this question has got only 1 answer.  The solution from Howard is pretty slick.  It seems that it was on the harder side.

GolfScript, 107 characters
.n?):L;'1'/{,}%{1$+)}*;][]\{:A{{+}+[1L.~)-1]%&}+1$\,.@^\[[[A]]+{|}*]+}/{.{L%}{%$..&1$,1$,/*$=}:C~\{L/}C&},,

The input must be given on STDIN.
Examples:
11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5

See comments above - it seems that "valid" rectangles need to have width/height both > 1.

@PaulR That rule is not written in the question, by all reasonable definitions those are perfectly fine rectangles - maybe I'll add that later.

I agree with your definition - I was just noting the discrepancy in the comments - it looks like OP needs to update the question to make it more definitive.

I clarified that rectangle of size 1 is valid.

But you also said in the comments, in response to: "Just for clarification, degenerate rectangles shouldn't be counted, correct? For example, are a single 1 or a single subrow/subcolumn of adjacent 1's invalid?" by saying:
"Yes, they are invalid, and should not be counted."

I think when I said "rectangle of size 1 is valid", it added an ambiguity that it might always be valid regardless of other rules.   So it is true that rectangle of size 1 is a valid rectangle but it should also conform to all the other rules of the problem.  To get away from the ambiguity I removed the line 'rectangles of size 1 are valid', however, I kept the size 1 rectangle showing that it is valid because it fulfills all the rules, not because it is of size 1.  Let me know if it is still confusing, but you get the idea i guess.