text:
Where's the 0xBEEF?
This challenge was inspired by this Wendy's commercial from 1984.

Illustration by T S Rogers
Your task is to find a hexadecimal 0xBEEF on a binary bun.
The 'beef' consists of the following pattern:
1 0 1 1  (0xB)
1 1 1 0  (0xE)
1 1 1 0  (0xE)
1 1 1 1  (0xF)

And the 'bun' consists of a 12x12 binary matrix, such as:
1 1 1 0 0 1 1 1 1 1 1 0
1 1 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1
1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1

Input
Your program or function will take the binary matrix as input. The matrix format is very flexible, but it must be clearly described in your answer.
For instance:

a single binary string, with or without separators between the rows:
"111001111110 110100100000..."
or:
"111001111110110100100000..."
an array of binary strings:
["111001111110", "110100100000", ...]
an array of numbers (each number describing a row once converted back to binary and left-padded with zeros):
[3710, 3360, ...]

Output
The coordinates (X, Y) of the 'beef', (0, 0) being the top left corner of the bun.
Alternatively, you may use 1-based coordinates (but not a mix of both formats, like 0-based for X and 1-based for Y).
For the above example, the expected answer is (3, 4) (0-based) or (4, 5) (1-based):
   00 01 02 03 04 05 06 07 08 09 10 11
00  1  1  1  0  0  1  1  1  1  1  1  0
01  1  1  0  1  0  0  1  0  0  0  0  0
02  0  1  0  0  0  1  1  1  1  1  0  1
03  1  0  0  1  0  0  1  0  0  1  0  0
04  1  0  0 [1  0  1  1] 0  0  1  1  1
05  1  1  1 [1  1  1  0] 0  0  0  1  0
06  1  1  0 [1  1  1  0] 0  0  0  0  1
07  1  0  0 [1  1  1  1] 0  0  0  0  1
08  1  0  0  1  1  1  0  1  1  1  1  1
09  1  1  1  1  1  0  0  1  1  1  1  1
10  1  0  0  0  0  1  0  1  0  1  1  1
11  1  1  0  0  1  1  0  0  0  0  1  1

Again, any reasonable format would work as long as it is specified in your answer. Please also mention if you're using 0-based or 1-based coordinates.
Rules

You can safely assume that there is always exactly one 'beef' on the bun. Your code is not required to support cases with more than one beef or no beef at all.
The beef pattern will always appear as described. It will never be rotated or mirrored in any way.
This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.

Test cases
In the following test cases, each row of the matrix is expressed as its decimal representation.
Input : [ 3710, 3360, 1149, 2340, 2407, 4034, 3521, 2529, 2527, 3999, 2135, 3267 ]
Output: [ 3, 4 ]

Input : [ 1222, 3107, 1508, 3997, 1906, 379, 2874, 2926, 1480, 1487, 3565, 633 ]
Output: [ 3, 7 ]

Input : [ 2796, 206, 148, 763, 429, 1274, 2170, 2495, 42, 1646, 363, 1145 ]
Output: [ 6, 4 ]

Input : [ 3486, 3502, 1882, 1886, 2003, 1442, 2383, 2808, 1416, 1923, 2613, 519 ]
Output: [ 1, 1 ]

Input : [ 3661, 2382, 2208, 1583, 1865, 3969, 2864, 3074, 475, 2382, 1838, 127 ]
Output: [ 8, 8 ]

Input : [ 361, 1275, 3304, 2878, 3733, 3833, 3971, 3405, 2886, 448, 3101, 22 ]
Output: [ 0, 3 ]

Input : [ 3674, 2852, 1571, 3582, 1402, 3331, 1741, 2678, 2076, 2685, 734, 261 ]
Output: [ 7, 7 ]

Is using 1-based indices allowed (where the top left is (1,1))?

@Doorknob Yes, if it's the same format for both X and Y (question updated accordingly).

Bonus points if we also output wether the 0xBEEF is 0xDEAD? :P

This challenge is really random and kinda silly. But it's actually a pretty great challenge still. +1

Can I output y, x (i.e. reverse order)?

@LuisMendo Yes, that's OK.

Can input be a "binary" matrix containing 1, -1 instead of 1, 0?

@LuisMendo No, I expect either numbers or some "standard binary" representation made of zeros and ones.

Can I return the output as a string, e.g., '34'?

@Dennis - Yes. (Provided that it means (3, 4) and not the 34th position.)

Yes, that's what I had in mind. Thanks for clarifying.

Is the "bun" always exactly 12x12?

@JDL Yes it is.

@DJMcMayhem: it is not really random : http://www.catb.org/jargon/html/D/DEADBEEF.html . see also : https://en.wikipedia.org/wiki/Magic_number_%28programming%29#Magic_debug_values

Mmm I want someone to 0xFEED me some 0xDEAD 0xBEEF

Jelly, 20 17 16 bytes
ṡ€4ḄZw€“¿ÇÇÐ‘ĖUṀ

Input is in form of a Boolean matrix, output is the 1-based index pair (Y, X).
Try it online! or verify all test cases.
How it works
ṡ€4ḄZw€“¿ÇÇÐ‘ĖUṀ  Main link. Argument: M (2D array of Booleans)

ṡ€4               Split each row into 9 chunks of length 4.
   Ḅ              Convert these chunks from base 2 to integer.
    Z             Zip/transpose. This places the columns of generated integers
                  into the rows of the matrix to comb through them.
       “¿ÇÇÐ‘     Push the array of code points (in Jelly's code page) of these
                  characters, i.e., 0xB, 0xE, 0xE, and 0xF.
     w€           Window-index each; in each row, find the index of the contiguous
                  subarray [0xB, 0xE, 0xE, 0xF] (0 if not found).
                  Since the matrix contains on one BEEF, this will yield an array
                  of zeroes, with a single non-zero Y at index X.
             Ė    Enumerate; prefix each integer with its index.
              U   Upend; reverse the pairs to brings the zeroes to the beginning.
               Ṁ  Take the maximum. This yields the only element with positive
                  first coordinate, i.e., the pair [Y, X].

I don't get it... how can you code something that is not human readable??

Jelly is by far easier to write than to read. :P

@l3n you seem to imply that Dennis is a human. While it is a possibility, given the kind of tricks that routinely pulls out, I wouldn't discount other ... let's say, more cyberpunk alternatives ;-)

You could output (x,y) with ṡ4Z€Ḅw€“Ð¬Ðµ‘ĖUṀ

@JonathanAllan Nice. There's also ṡ€4ḄZjw“¿ÇÇÐ‘’d24 with 0-based indexing, but it is, unfortunately, one byte longer.

This is 16 characters, but 35 bytes (in UTF-8).

@Useless The bytes link in the header points to Jelly's code page, which encodes each of the 256 characters it understands as a single byte.

Very ingenious!

vim, 126 80 77 76
/\v1011\_.{9}(1110\_.{9}){2}1111<cr>:exe'norm Go'.join(getpos('.'))<cr>xxdawhPXXd{

Expects input in the form
111001111110
110100100000
010001111101
100100100100
100101100111
111111000010
110111000001
100111100001
100111011111
111110011111
100001010111
110011000011

And outputs (with 1-based indices) as
4 5

/                      regex search for...
\v                     enable "very magic" mode (less escaping)
1011\_.{9}             find the first line ("B"), followed by 8 chars + 1 \n
(1110\_.{9}){2}        find the second and third lines ("EE")
1111<cr>               find the fourth line ("F")
:exe'norm Go'.         insert at the beginning of the file...
join(getpos('.'))<cr>  the current position of the cursor
xxdawhPXX              do some finagling to put the numbers in the right order
d{                     delete the input

Thanks to Jörg Hülsermann for indirectly saving 46 bytes by making me realize my regex was super dumb, and to DJMcMayhem for 3 more bytes.

A couple tips: 1) Yp is better than yyp (even though I know you object to Y :P) 2) the whitespace in exec 'norm Go' is unnecessary. And 3) kd{ is shorter than kdgg. (Haven't tested that though)

@DJMcMayhem Oh, I always forget about Y because I have it rebound in my vimrc. :P In fact, the kdgg was equivalent to just d{, which, surprisingly, does not delete the current line.

Oh interesting. How convenient!

I'm always confused when things such as { turn out to be a character movement; so I have do something like {d'' instead to delete whole lines.

@Neil You could do dV{ instead

@DJMcMayhem I learned vi in the old days, so I'm not used to all these new options such as visual mode!

While you actually encoded B your comment says D.

@LorenPechtel Whoops, thanks for pointing that out.

You could use echo instead of printing into the buffer, I don't think there's anything preventing this in the challenge. That would shave off around 10 bytes.

JavaScript (ES6), 63 60 56 bytes
s=>[(i=s.search(/1011.{9}(1110.{9}){2}1111/))%13,i/13|0]

Takes input as a 155-character space-delimited string of 12 12-digit binary strings, returns zero-indexed values. Edit: Saved 3 bytes thanks to @JörgHülsermann. Saved 4 bytes thanks to @ETHproductions.

Could you possibly use s.search(r) instead of r.exec(s).index?

@ETHproductions Of course I could. I must have been half asleep yesterday...

For me, using nodejs to execute, it is not working unless i change s=>[ to  (s,i)=>[, because you need to define i somewhere :/

@Mijago Odd, it worked in Node 4 when I tried it (I normally use the Spidermonkey JS shell). Mind you a typo had crept into the code so some good came out of it!

I think this fails for 000010110010110011100011100011100011100011110011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

@Taemyr Actually it works for your case but if fails if I change the first 1 to a 0, so I fixed my code (fortunately that didn't cost me any bytes).

@Neil I am happy my last comment on the Retina solution got in before your fix.

@Neil It was my "use static"; i use everywhere which forces me to define every variable. Mystery solved!

C, 146 177 173 163 bytes
Thanks to Numberknot for fixing the code (shifting the lower three rows).
Saving 4 bytes by replacing >>=1 with /=2 in 4 places.
Saving 10 more bytes by letting x and y be global and default int thanks to MD XF
#define T(i,n)(A[y+i]&15)==n
x,y;b(int A[12]){for(x=9;x--;){for(y=0;++y<9;A[y]/=2)if(T(0,11)&&T(1,14)&&T(2,14)&&T(3,15))return(x<<4)+y;A[9]/=2;A[10]/=2;A[11]/=2;}}

Ungolfed:
int b(int A[12]) {
 for (int x=8; x>=0; --x) {
  for (int y=0; y<9; ++y) {
   if ((A[y]&15)==11 && (A[y+1]&15)==14 && (A[y+2]&15)==14 && (A[y+3]&15)==15) {
    return (x<<4) + y;
   }
   A[y]/=2;
  }
  A[9]/=2; A[10]/=2; A[11]/=2;
 }
}

Returns x,y (0-based) in the high and low nibble of a byte.
Usage:
int temp=b(array_to_solve);
int x=temp>>4;
int y=temp&15;
printf("%d %d\n",x,y);

you can change your define to #define T(i,n)if((A[y+i]&15)==n) and the if section to T(0,11)T(1,14)T(2,14)T(3,15)return to save 6 bytes. Also change the function signature to int b(int*A) to 4 more bytes saved.

163 bytes

MATL, 22 21 bytes
Eq[ODDH]B~EqZ+16=&fhq

Input is a binary matrix, with ; as row separator. Output is 1-based in reverse order: Y X.
Try it online! Or verify all test cases with decimal input format.
Explanation
The pattern is detected using 2D convolution. For this,

The matrix and the pattern need to be in bipolar form, that is, 1, -1 instead of 1, 0. Since the pattern has size 4×4, its occurrence is detected by an entry equal to 16 in the convolution output.
The convolution kernel needs to be defined as the sought pattern reversed in both dimensions.

Also, since the convolution introduces an offset in the detected indices, this needs to be corrected for in the output.
Eq      % Implicitly input binary matrix. Convert to bipolar form (0 becomes -1)
[ODDH]  % Push array [0 8 8 2]
B       % Convert to binary. Each number gives a row
~Eq     % Negate and convert to bipolar. Gives [1 1 1 1; 0 1 1 1; 0 1 1 1; 1 1 0 1]
        % This is the "BEEF" pattern reversed in the two dimensions. Reversal is
        % needed because a convolution will be used to detect that patter
Z+      % 2D convolution, keeping original size
16=&f   % Find row and column indices of 16 in the above matrix
h       % Concatenate horizontally
q       % Subtract 1. Implicitly display

Mathematica, 62 bytes
BlockMap[Fold[#+##&,Join@@#]==48879&,#,{4,4},1]~Position~True&

Returns all positions of the BEEF matrix, 1-indexed. The input must be a matrix of binary digits. The x and y in the output are switched, though.

No worries about x and y being switched.

PHP, 87 Bytes
binary string as input without separators, returns zero-indexed values.
preg_match("#1011(.{8}1110){2}.{8}1111#",$argv[1],$c,256);echo($s=$c[0][1])%12,$s/12^0;

array of numbers as input 128 Bytes
<?foreach($_GET[a]as$a)$b.=sprintf("%012b",$a);preg_match("#1011(.{8}1110){2}.{8}1111#",$b,$c,256);echo($s=$c[0][1])%12,$s/12^0;

14 Bytes saved by @Titus Thank You

Use , instead of . in the echo and you can remove the parentheses. (-4)

In the comments, Arnauld allows output without a delimiter. (-4)

Use flag PREG_OFFSET_CAPTURE: append ,256 to the preg_match parameters, remove ^(.*) from the regex, $c[0][1] instead of strlen($c[1]) (-6)

@Titus nice and done

Slip, 28 bytes
27 bytes of code, +1 for p option.
(?|1011)(\(?|1110)){2}\1111

Requires input as a multiline rectangle of 1's and 0's without spaces. Try it here (with third testcase as input).
Explanation
Slip is a language from the 2-D Pattern Matching challenge. Sp3000 could say a lot more about it than I can, but basically it's an extended form of regex with some directional commands that let you match in two dimensions. The above code uses the eponymous "slip" command \, which doesn't change the match pointer's direction but moves it sideways by one character. It also uses "stationary group" (?|...), which matches something and then resets the pointer to its previous location.
The code breaks down as follows:
(?|1011)                     Match 1011; reset pointer to beginning of match
        (         ){2}       Do the following twice:
         \                     Slip (moves pointer down one row)
          (?|1110)             Match 1110; reset pointer to beginning of match
                      \1111  Slip and match 1111

This matches the 0xBEEF square. The p option outputs the coordinates of the match, 0-indexed.

Nice :) Weirdly, for block patterns sometimes it's golfier to just walk around in a spiral: 1011>001>1(11>){3}1>1

@Sp3000 Ha! Spiral was the shortest method in SnakeEx, but I didn't think of trying it in Slip. Really nice trick with the 1(11>){3}.

Java 7,182 177 bytes
I ported Karl Napf C answer to JAVA And Thanks to Karl Napf for saving 5 bytes by reminding me Bit magic.(Btw i came up with this idea too but @KarlNapf return part idea was yours not mine).Sorry if i displeased you.
(0-based)

int f(int[]a){int x=9,y,z=0;for(;x-->0;){for(y=0;y<9;a[y++]/=2) if((a[y]&15)==11&(a[y+1]&15)==14&(a[y+2]&15)==14&(a[y+3]&15)==15)z=(x<<4)+y;a[y]/=2;a[10]/=2;a[11]/=2;}return z;}

Ungolfed
class Beef {

    public static void main(String[] args) {
        int x = f(new int[] { 1222, 3107, 1508, 3997, 1906, 379, 2874, 2926, 1480, 1487, 3565, 633 });
        System.out.println(x >> 4);
        System.out.println(x & 15);
    }

    static int f(int[] a) {
        int x = 9,
            y,
            z = 0;

        for (; x-- > 0; ) {
            for (y = 0; y < 9; a[y++] /= 2)
                if ((a[y] & 15) == 11
                  & (a[y + 1] & 15) == 14
                  & (a[y + 2] & 15) == 14
                  & (a[y + 3] & 15) == 15)
                    z = (x << 4) + y;

            a[y] /= 2;
            a[10] /= 2;
            a[11] /= 2;
        }
        return z;
    }

}

What are those four spaces there between a[y++]>>=1) and if((a[y]&15)==. Btw, I count 182 bytes instead of 183? :S

@KevinCruijssen fixed .

Everything alright ;-)

You can still remove the space between ...a[y++]/=2) and if((a[y]&15)==....

Scala, 90 bytes
("1011.{8}(1110.{8}){2}1111".r.findAllMatchIn(_:String).next.start)andThen(i=>(i/12,i%12))

Explanation:
(
  "1011.{8}(1110.{8}){2}1111" //The regex we're using to find the beef
  .r                          //as a regex object
  .findAllMatchIn(_:String)   //find all the matches in the argument thats going to be passed here
  .next                       //get the first one
  .start                      //get its start index
)                             //this is a (String -> Int) function
andThen                       //
(i=>                          //with the found index
  (i/12,i%12)                 //convert it to 2d values
)

(a -> b) andThen (b -> c) results in a (a -> c) function, it's like the reverse of compose, but requires fewer type annotations in scala. In this case, it takes a string of the binary digits as input and returns a tuple of zero-based indices.

Python 2, 98 95 92 bytes
lambda x:'%x'%(`[''.join('%x'%int(s[i:i+4],2)for s in x)for i in range(9)]`.find('beef')+15)

Input is a list of strings, output is the string XY (1-based indices).
Test it on Ideone.

Might this mistakenly find a "beef" across the boundary where two lines are concatenated?

Yeah, I think so. I'll roll the edit back until I can test it properly.

That's what happens when you use a toroidal bun.

Perl 5 + -n -M5.10.0, 51 bytes
Uses 0-based indices. Expects input as a string of 1s and 0s and outputs space separated co-ordinates.
Thanks to @wullxz and @GabrielBenamy for helping me save 9 bytes, and to @Taemyr's comment on my Retina answer for pointing out an issue!
/1011.{9}(1110.{9}){2}1111/;say"@-"%13,$","@-"/13|0

Try it online!

You can save 3 characters by combining the regex for the binary EE: (.{8}1110){2} instead of .{8}1110.{8}1110

You can also save another 3 bytes by changing length$\`` into $-[0]`

@wullxz Of course! I tried \1 but had no luck, didn't think to try {2}! Thanks!

@GabrielBenamy Amazing, thank you very much! Updated!

@GabrielBenamy What does $-[0] do?

@User112638726 "$-[0] is the offset of the start of the last successful match. $-[n] is the offset of the start of the substring matched by n-th subpattern, or undef if the subpattern did not match." from: http://perldoc.perl.org/perlvar.html (look for @-)

@DomHastings Thanks! I'll have a look

Retina, 47 bytes
I'd like to preface this with an apology. I think this is probably terrible and a bad example of how to use the language, but since I used a Regex for my Perl answer, I thought I'd try Retina. I'm not very good. :( The snippets on github helped me greatly though!
Thanks to @wullzx for his comment on my Perl answer for -3 bytes and to @Taemyr for pointing out an issue with my method!
Expects input as a space-separated binary string and outputs co-ordinates space separated.
(.{13})*(.)*1011(.{9}1110){2}.{9}1111.*
$#2 $#1

Try it online!
Verify all tests at once.

Fails for '000010110010110011100011100011100011100011110011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'  Your (.)* needs to be (.){0,8}

Is this countered by You can safely assume that there is always exactly one 'beef' on the bun. Your code is not required to support cases with more than one beef or no beef at all.? It can be resolved with ungreedy modifiers if necessary though (.{12})*?(.)*?.

Look again, there is only one beef in that input - and it's not at the point where your program indicates.  The problem would not be resolved by using eager modifers, since I can switch the fake beef with the real beef.  the problem is that your regex matches a "beef" that starts less than 4 bits from the end of a matrix row.

You could also resolve this by changing the {8}'s to {9} and asking for the lines in the input to be space seperated, for a zero byte cost fix.

@Taemyr Ahhh! I see! I misunderstood your point... You are indeed correct. My Perl solution potentially falls foul of this as well. Will get that changed ASAP. Thank you for your comments and suggestion!

J, 31 29 bytes
[:($#:I.@,)48879=4 4#.@,;._3]

The input is formatted as a 2d array of binary values, and the output is the zero-based coordinates as an array [y, x].
The flattening and base conversion to find the index is something I learned from this comment by Dennis.
Usage
   f =: [:($#:I.@,)48879=4 4#.@,;._3]
   ] m =: _12 ]\ 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1
1 1 1 0 0 1 1 1 1 1 1 0
1 1 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1
1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1
   f m
4 3
   f (#:~2#~#) 3710 3360 1149 2340 2407 4034 3521 2529 2527 3999 2135 3267
4 3
   f (#:~2#~#) 1222 3107 1508 3997 1906 379 2874 2926 1480 1487 3565 633
7 3
   f (#:~2#~#) 2796 206 148 763 429 1274 2170 2495 42 1646 363 1145
4 6
   f (#:~2#~#) 3486 3502 1882 1886 2003 1442 2383 2808 1416 1923 2613 519
1 1
   f (#:~2#~#) 3661 2382 2208 1583 1865 3969 2864 3074 475 2382 1838 127
8 8
   f (#:~2#~#) 361 1275 3304 2878 3733 3833 3971 3405 2886 448 3101 22
3 0
   f (#:~2#~#) 3674 2852 1571 3582 1402 3331 1741 2678 2076 2685 734 261
7 7

Explanation
[:($#:I.@,)48879=4 4#.@,;._3]  Input: 2d array M
                            ]  Identity. Get M
                 4 4    ;._3   For each 4x4 subarray of M
                       ,         Flatten it
                    #.@          Convert it to decimal from binary
           48879=              Test if equal to 48879 (decimal value of beef)
[:(       )                    Operate on the resulting array
         ,                       Flatten it
      I.@                        Find the indices where true
    #:                           Convert from decimal to radix based on
   $                               The shape of that array
                               Returns the result as coordinates [y, x]

24: $#:(4 4$#:48879)I.@,@E.] Try it online!

APL (Dyalog Extended), 13 bytes
⍸⎕⍷⍨~⊤0 8 0 6

Try it online!
We already have Zacharý's APL answer, but APL has improved a lot over the recent years, just enough to beat Jelly!
A full program that takes the binary matrix from stdin and prints the (y,x) to stdout.
How it works
⍸⎕⍷⍨~⊤0 8 0 6
     ⊤0 8 0 6  ⍝ Binary representation (a number → column)
               ⍝ 0 1 0 0
               ⍝ 0 0 0 1
               ⍝ 0 0 0 1
               ⍝ 0 0 0 0
    ~  ⍝ Boolean negation
 ⎕⍷⍨   ⍝ Take input and mark 1 where the 2D pattern appears
⍸      ⍝ Extract the coordinates of all ones

Ruby, 62 bytes
def f(a);a=~/1011(.{8}1110){2}.{8}1111/;$`.size.divmod(12);end

It expects a string of 0 and 1 and returns an array of Y and X, zero-based.
Try at ideone.

Scala, 318 Bytes
This solution could be further improved... but I kept it readable and allowed for the input to be the multi-line spaced matrix.
Actual Solution if Array of binary String
def has(s: String, t: String): Int = s.indexOf(t)
val beef = List("1011", "1110", "1110", "1111")
l.zipWithIndex.map{case(e,i)=>l.drop(i).take(4)}.map{_.zip(beef)}.map{_.collect{case e=>has(e._1,e._2)}}.zipWithIndex.filterNot{e => e._1.contains(-1) ||  e._1.distinct.length > 1}.map{e=>s"(${e._1.head},${e._2})"}.head

Sample Working
val bun =
"""1 1 1 0 0 1 1 1 1 1 1 0
1 1 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1
1 0 0 1 0 0 1 0 0 1 0 0
1 0 0 1 0 1 1 0 0 1 1 1
1 1 1 1 1 1 0 0 0 0 1 0
1 1 0 1 1 1 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1
""".replaceAll(" ","")
def has(s: String, t: String): Int = s.indexOf(t)
val beef = List("1011", "1110", "1110", "1111")
val l = bun.split("\n").toList
l.zipWithIndex.map{case(e,i)=>l.drop(i).take(4)}
.map{_.zip(beef)}
.map{_.collect{case e=>has(e._1,e._2)}}.zipWithIndex
.filterNot{e => e._1.contains(-1) ||  e._1.distinct.length > 1}
.map{e=>s"(${e._1.head},${e._2})"}.head

F# - 260 bytes
Full program, including the required EntryPoint designator (so count fewer if you wish I suppose).
Input: each row as separate string:
"111001111110" "110100100000" "010001111101" "100100100100" "100101100111" "111111000010" "110111000001" "100111100001" "100111011111" "111110011111" "100001010111" "110011000011"
Code:
[<EntryPoint>]
let main a=
 let rec f r:int=
  let b=a.[r].IndexOf"1011"
  if(b>0)then if(a.[r+1].[b..b+3].Equals"1110"&&a.[r+2].[b..b+3].Equals"1110"&&a.[r+3].[b..b+3].Equals"1111")then r else f(r+1)
  else f(r+1)
 printfn"%d%d"(a.[f 0].IndexOf"1011")(f 0);0

Not the most elegant solution most likely, but i wanted to keep with strings, so this is how i did it. I almost got it to be a single line and smaller using pipes, but there is something with the double if block that was getting me that i couldn't resolve. So oh well!
I thought too about porting Karl's answer into F# as it's a good one, and may still do that for fun as another approach, but wanted to stick with this one to be different.

Element, 130 bytes
_144'{)"1-+2:';}144'["1-+19:~?1+~?!2+~?3+~?12+~?13+~?14+~?15+~?!24+~?25+~?26+~?27+~?!36+~?37+~?38+~?39+~?16'[&][12%2:`\ `-+12/`]']

Try it online!
Takes input as one long string of 1s and 0s without any delimiters.  Outputs like 3 4 (0-based indexing).
This works by placing the input data into an "array" (basically a dictionary with integer keys) and then, for each possible starting value, tests the bits at particular offsets (all 16 of them in a very laborious process).

Python, 137 bytes (according to Linux (thanks ElPedro))
def f(s,q=0):import re
 i=s.index(re.findall('1011.{8}1110.{8}1110.{8}1111',s)[q])+1
 x=i%12
 y=(i-x)/12
 if x>8:x,y=f(s,q+1)
 return x,y

Not exactly a competitive bytecount, but the algorithm is a bit interesting. Takes input as a string of binary values.

If you sue single spaces instead of 4 and check it on Linux it's 137

I think you need a newline and space before the import (I get an IndentError in Python 2 without it) which costs 2 bytes but you can then put i=..., x=... and y=... on the same line as  and separate with ; to lose 1 byte for 136

@elpedro I'm using Python 3, and it's fine with the import being on the same line.

Fully understood :)

Jeez, just reread my comments and I'm making so many typos tonight. Good thing I'm not trying to write any code...

Dyalog APL, 29 27 bytes
Takes a 12x12 binary array as user input and returns the coordinates in reverse order, the indexes start at 1.
Thanks to @Adám for saving many bytes.
-2 Bytes because I'm dumb and left everything in a function for no reason.
0~⍨∊{⍵×⍳⍴⍵}⎕⍷⍨~0 8 0 6⊤⍨4/2

Save 2 by replacing ~2 8 12∊⍨4 4⍴⍳16 with 15 7 15 9⊤⍨4/2. Note that 0~⍨∊{⍵×⍳⍴⍵} can be replaced with ⍸ from version 16.0 (your code only works in Dyalog APL).

Yeah, Dyalog has characters that differ from GNU. Or is it something else?

Well, ⍸ is being added from v16, I've been unable to find a list of GNUAPL primitives.

I've got GNU APL running, it's mostly just codepoint differences.

From what I've noticed.

⍸⎕⍷⍨15 7 15 9⊤⍨4/2

Does ⍸ work in GNU APL?

No, and what does that index char do?

ISn't that evaluated input?

From Dyalog APL version 16, ⍸ is {⍵/⍳⍴⍵}, i.e. the indices of the ones in a Boolean vector.

⎕ is indeed evaluated input. This allows the user to directly enter a matrix 12 12⍴... or enter the name of a predefined variable containing the data. The entire line is the body of a tradfn.

This whole sequence of exchanges somehow led me to believe v16 was released. Wow, I was just dumb.

R, 111 bytes
function(a,b=63357%/%2^(0:15)%%2)
which(sapply(1:9,function(i)sapply(1:9,function(j)all(a[i+0:3,j+0:3]==b))),T)

Try it online!
Searches for identities of 4x4 matrix starting at all indices of 9x9 matrix (to avoid edge overlaps).

05AB1E, 17 bytes
2Fø€ü4}JJ˜Žùòbk9‰

Input as a matrix of bits. Output is 0-based, in the order \$Y,X\$.
Try it online or verify all test cases.
Explanation:
2Fø€ü4}     # Create transposed overlapping 4x4 blocks of the (implicit) input-matrix:
2F          #  Loop 2 times:
  ø         #   Zip/transpose; swapping rows/columns
   €        #   Map over each row:
    ü4      #    Create all overlapping quartets
 }          #  Close the loop
J           # Join each row of each matrix together
 J          # Join the rows of each matrix together
  ˜         # Flatten the list of strings
   Žùò      # Push compressed integer 63481
      b     # Convert it to binary: 1111011111111001
       k    # Get the index of this binary-string in the list
        9‰  # Divmod it by 9
            # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Žùò is 63481.

Uiua, 12 bytes
⊚⌕⋯13_7_7_15

Self explanatory. Converts the number array to bits, finds where it is. The input is a 12x12 bit matrix, the output is a 1x2 matrix where the X coordinate is the second element.
Test pad

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


text:
Antsy permutations
Introduction
Suppose you have a ruler with numbers from 0 to r-1.
You place an ant between any two of the numbers, and it starts to crawl erratically on the ruler.
The ruler is so narrow that the ant cannot walk from one position to another without walking on all the numbers in between.
As the ant walks on a number for the first time, you record it, and this gives you a permutation of the r numbers.
We say that a permutation is antsy if it can be generated by an ant in this way.
Alternatively, a permutation p is antsy if every entry p[i] except the first is within distance 1 from some previous entry.
Examples
The length-6 permutation
4, 3, 5, 2, 1, 0

is antsy, because 3 is within distance 1 of 4, 5 is within distance 1 of 4, 2 is within distance 1 from 3, 1 is within distance 1 from 2, and 0 is within distance 1 from 1.
The permutation
3, 2, 5, 4, 1, 0

is not antsy, because 5 is not within distance 1 of either 3 or 2; the ant would have to pass through 4 to get to 5.
The task
Given a permutation of the numbers from 0 to r-1 for some 1 ≤ r ≤ 100 in any reasonable format, output a truthy value if the permutation is antsy, and a falsy value if not.
Test cases
[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True

Fun fact: for r ≥ 1, there are exactly 2r-1 antsy permutations of length r.

This is a very interesting challenge with many different solutions: I count at least 7 unique strategies being used so far.

The structured input form of permutations is contributing a lot to the variety of approaches. The condition for being antsy can be expressed in different ways that are inequivalent on general lists.

I'm disappointed there isn't an ANTSI C solution yet.

@NoSeatbelts ANSI

Pyth, 7 bytes
/y+_QQS

Try it online. (Only small test cases are included due to exponential run-time.) Outputs 2 for Truthy, 0 for Falsey.
/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

In other words,
lambda l: subseq(sorted(l), concat(reverse(l), l))

where subseq outputs whether the elements of the first list appear in order in the second list, not necessarily adjacent. The subseq is done in Pyth by taking all subsets of the second list, which keep the order of the elements, and counting the number of occurrences of the first list. This takes exponential time.
Why does this work? For a permutation to be antsy, stepping from 0 to n-1 must consist of going only left, then going only right. This is because the elements greater than the first element must increase left to right, and those less than it must decrease left to right.
[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1
 2  ^
    3     ^
          4

If we mirror the list by putting a reversed copy to its left, this walk now only goes right.
[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |
 0     ^      |
       1      | ^
              | 2  ^
              |    3     ^
              |          4

Conversely, any rightward of this mirror list corresponds to a left-then-right walk of the original list. This rightward just is a sorted subsequence of 0 to n-1. In an antsy list, this sorted subsequence is unique, except for an arbitrary choice between the two adjacent copies of the original first element.

You can cut it down to 6 bytes by using... just kidding.

There's something hideous about using an exponential-time approach to a problem with an obvious linear-time solution even if it golfs down nicely.

@jwg I'd believe it, actually. If the list count took arguments in the opposite order, you could get 6 bytes by taking two inputs implcitly.

ayyyyy, turning to the pyth side :D

Haskell, 46 bytes
(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Checks whether the vector difference of the running maxima and the running minima is [0,1,2,3...].
l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]
difference =    [0, 1, 2, 3, 4]

Zgarb saved 2 bytes with (%)=scanl1.

That's so clever! +1

Could you save some bytes by defining (#)=scanl1?

@Zgarb Thanks, I forgot you could do that.

JavaScript (ES6), 45
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

I thought it's too simple to need as explanation, but there is a trick, and just in case, here is my first version, pre-golf
a => {
  k = []; // I'll put a 1 in this array at position of each value
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Note: in the golfed code a is used instead of k, as I need no reference to the original array inside the every call. So I avoid to pollute the global namespace reusing the parameter
Test

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g),
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

Real nice. I tried this approach with recursion, but I can't get it below 65: f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)

How does this work? Are you using some mutable list magic?

@Zgarb explanation added

Python 2, 49 bytes
f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

Checks whether each prefix of the list contains all numbers between its min and max inclusive. It does so by checking if the difference of the max and min is less than its length.

54 bytes:
f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

Checks if the last element is either one less than the min of the other elements, or one more than their max. Then, removes the last element and recurses. On a single-element list, outputs True.
This can also be checked via an amusing but longer list comprehension.
lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

I'd like to use the inequality min(l)-2<l.pop()<max(l)+2, but the pop needs to happen first. Using a program to output via error code would likely be shorter.

Mathematica, 42 bytes
!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Uses pattern matching to try and find a prefix a whose maximum difference from the next element b is greater than 1 (and negating the result of MatchQ).

Perl, 39 38 35 bytes
Includes +1 for -p
Give sequence on STDIN:
antsy.pl <<< "2 1 3 0"

antsy.pl:
#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++

I'm having a hard time trying to understand this one... Care to explain a little? thanks :-) (just the main idea should be enough)

MATL, 11 bytes
&-|R1=a4L)A

Try it online! Or verify all test cases.
Explanation
This computes a matrix of all pairwise absolute differences and keeps the upper triangular part. The result is true iff there is at least a 1 value in all columns except the first.
&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results

R, 72 64 60 bytes
v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

A permutation is antsy if and only if all its left subpermutations are continuous (i.e. have difference one when sorted).
If input is guaranteed to have length more than one, then we can replace 1:sum(1|v) with seq(v), which saves four bytes.
The seq(v) in the if condition behaves differently when the input is of length one --- it generates the sequence 1:v instead of seq_along(v). However, fortunately, the output turns out to be TRUE in this case, which is the desired behaviour. The same also happens for zero-length input.
In R, T is a preset variable equal to TRUE (but R allows you to redefine it). TRUE is also deemed to be equal to 1.
Thanks to @Billywob for some helpful improvements to the original solution.

Reading input using scan would save you two bytes. In that case it's exactly the same number of bytes as the for loop approach: v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1) which would be 2 bytes shorter than your vectorized approach.

Nice idea, and I can go one better I think by abusing T. Will edit.

Jelly, 9 8 7 bytes
;@UŒPċṢ

Try It Online!
A Jelly translation of xnor's answer.
Old solutions:
;\Ṣ€IỊȦ
;\Ṣ€IE€P

Try it online!
Works very similarly to my Pyth answer below:
;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?

The conversion of xnor's other method to Jelly is also 7 bytes »\_«\⁼Ṣ but much more efficient

ŒBŒPċṢ and ;\Ṣ€IỊȦ should save one byte in each approach.

Unfortunately, the first doesn't work because I would need the reversed input to be bounced, like UŒBŒPċṢ which doesn't save any bytes.  The Ị is nice, though; I had misread that atom to output the logical NOT of what it actually did.

I'm not sure why you'd need the U (or the @ now that I think about it). If an array is antsy, so is the reversed array, no?

Not necessarily: [2, 1, 3, 0] is antsy but [0, 3, 1, 2] is not.

05AB1E, 7 bytes
Âìæ¹{¢O

Try it online!
or as a modified test suite.
Explanation
Uses the process described by xnor in his brilliant Pyth answer.
Returns 2 for truthy instances and 0 for falsy.
Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)

Brain-Flak 302 264 256 Bytes
Thanks to  Wheat Wizard for saving 46 bytes
([]){{}({}<>)<>([])}{}<>(({}))([]){{}({}<>)<>([])}{}<>(({}<>))<>(()){{}(({})<(({})<>[({})]<>(())){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>({}<<>(({})<>[({})<>(())]){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>>)<>>[({})](<()>)){{}{}(<(())>)}{}}([][()(())]){((<{}{}>))}{}

The top of the stack will be a 1 for truthy and a 0 for falsy.
Truthy: Try it Online!
Falsy:  Try it Online!
The idea is to hold the minimum and maximum number that the ant has visited in the off stack. Then compare each number to both of those and update the appropriate one. If the next number is not 1 less than the min or 1 more than the max, break out of the loop and return false.

Brief Explanation:
([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack

I would check for push pop reductions  I see some already a few places where you could use this strategy.

@WheatWizard I'm sure there are a few, I just didn't have time to work them out yet. Thanks for the reminder.

I'm glad this at least makes sense to you O_O

You can also replace instances of ([]){({}[()]<({}<>)<>>)}{} with ([]){{}({}<>)<>([])}{} to save a couple more bytes

CJam (21 20 bytes)
{:A,{_)A<$2*)@-#},!}

Online test suite
Dissection
This uses the observation by xnor in his Haskell answer that the difference between the maximum and minimum of the first n elements should be n-1.
{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Alternative approach (also 20 bytes)
{_{a+_)f-:z1&,*}*^!}

Online test suite
This checks directly that each element after the first is at distance 1 from a previous element. Since the input is a permutation and hence doesn't repeat values, this is a sufficient test. Thanks to Martin for a 1-byte saving.
Dissection
{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}

I think this saves one? {_{a+_)f-:z1&,*}*^!}

@MartinEnder, very nice. Curiously you posted that just as I was posting a completely different approach with the same byte count.

Perl, 63 bytes
Note that @Gabriel Banamy came up with a shorter (55 bytes) answer. But I think this solution is still interesting, so I'm posting it.
The bytes count includes 62 bytes of code and -n flag.
s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

To run it :
perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Short explanations : converts each number k to the unary representation of k+1 (that +1 is needed so the 0s don't get ignored). Then for each number k+1 (expressed in unary as 1(1*)), we look if either k ($1 holds k) or k+2 (which is then 11$1) are present in the preceding string (referenced by $-backtick). If no, then we set $. to zero. At then end we print $. which will be 1 if we never set it to zero, or zero otherwise.

Java, 100 98 79 75 bytes
a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Formerly:
a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

Saved 3 bytes by replacing true and false with 1>0 and 0>1.
Saved 23 bytes thanks to excellent suggestions from Peter Taylor!
Ungolfed:
a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Keep track of the highest and lowest values seen so far as m and n; only accept a new value if it is m + 1 or n - 1 i.e. the next higher or lower value; initialize the high value, m, to one less than the first element so that it will "match" the first time around the loop. Note: this is a linear-time, online algorithm. It requires only three words of memory, for the current, highest-so-far, and lowest-so-far values, unlike a lot of the other solutions.
If the next value misses both the high and low ends of the range, the lowest-so-far value is set to -1 and then the low end can never proceed and reach zero. We then detect an antsy sequence by checking whether the low value, n, reached zero.
(Unfortunately this is less efficient because we always have to look at the entire sequence rather than bailing out after the first wrong number, but it's hard to argue with a 23-byte savings (!) when other solutions are using O(n^2) and exponential time approaches.)
Usage:
import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Note: this can also be written without taking advantage of Java 8 lambdas:
Java 7, 89 bytes
boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Good handling of the special case. int m,n;m=n=a[0];--m; could be int n=a[0],m=n-1;, and the expensive return and else could be reduced with i==m+1?m++:n=(i==n-1)?i:-1;return n==0; (or something similar - I haven't tested this).

@PeterTaylor Fantastic! Unfortunately, Java won't allow any side effects such as m++ or m+=1 there, so I still need an if and an else, and it loses the aspect of short circuiting on the first bad value, but that is a big improvement. Thank you!

It will allow side-effects in a complex expression. What it might not like is using a general expression as a statement. In the worst case you need to create a dummy variable j and assign the result to it, but suspect there would be a better way of doing it.

@PeterTaylor Well, I tried a few variations on it, including assigning it to a dummy variable g, and I couldn't get it to work. (I'm using Java 9-ea+138, maybe it's a difference between Java 8 and Java 9?) I may try again tomorrow.

Got it. n-=i==m+1?m-m++:i==n-1?1:n+1;

@PeterTaylor You're a genius. Thanks a million!

Jelly, 5 bytes
Ụ<ƝṢƑ

Try it online!
In Is it a tower permutation?, xnor comments

This is closely related to Antsy Permutations -- a tower permutation is one whose inverse permutation, read backwards as a list, is antsy.

Combining pxeger's answer to that question with Ụ (Grade, which inverts permutations) yields a short Jelly answer to this question.
Instead of reversing the list before inverting the permutation, which would cost another byte, I just check for "anti-towers" by changing > to <.

Pyth (fork), 13 bytes
!sstMM.+MSM._

No Try It Online link for this fork of Pyth.  The fork includes the deltas function .+, which is not part of the standard Pyth library.
Explanation:
           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.

Seeing this convinces me to merge this into Pyth.

J, 14 bytes
/:~-:>./\-<./\

This is based on @xnor's method.
Explanation
/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted

Perl, 66 54 +1 = 55 bytes
+1 byte for -n.
s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Explanation:
s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Prints 0 if false, 1 if true.
-11 bytes thanks to @Dada

That one is really nice. You can golf it down to 55 bytes though : perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.' : -n instead of <>=~ which allows you to get rid of  /r modifier. use \d+ and then $& instead of (\d+) and $1. !@a instead of 0>$#a. $.&= instead of $.&&=. push@a,$& instead of @a=(@a,$&)

For some reason, my system tells me the new file is 55 bytes long, which is obviously wrong because it's only 54 characters, so ???

Hmm that's strange. (and I have no idea where this comes from). But I'm pretty sure it's only 54 (the PPCG-Design script tells me 54, and my bytecount app tells me 54 aswell).

Is it possible the byte count was out due to the file having an unnecessary newline at the end?

Brainfuck, 60 bytes
,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

The permutation is given as bytes with no separators and no terminating newline. Since \x00 occurs in the input, this is designed for implementations with EOF = -1. The output is \x00 for false and \x01 for true.
If a permutation of \x01 up to chr(r) is allowed, then we can replace all instances of ,+ with , for a score of 57 with an EOF = 0 implementation.
Try it online (57-byte version): Input can be given as a permutation of any contiguous range of bytes excluding \x00, and the output will be \x00 for false and the minimum of the range for true.
We keep track of the min and max seen so far, and for each character after the first, check whether it is min-1 or max+1 or neither. In the case of neither, move the pointer outside the normal working space so that the local cells become zero.
The memory layout of the normal working space at the beginning of the main loop is
c a b 0 0
where c is the current character, a is min, and b is max. (For the 60-byte version, everything is handled with an offset of 1 because of ,+.)

Vyxal, 8 bytes
⇧2lvƒ<ÞṠ

Try it Online!
Like Lynn's Jelly answer, takes my Vyxal answer to Is it a tower permutation?, adds a grade up at the beginning, and changes > to <.
How?
⇧2lvƒ<ÞṠ
⇧        # Grade up (i.e. sort indices by corresponding values)
 2l      # Get overlapping pairs
   vƒ<   # For each pair, check if the first item is less than the second
      ÞṠ # Is it sorted in ascending order?

Brachylog, 22 bytes
:@[fb:{oLtT,Lh:T:efL}a

Try it online!
Explanation
I haven't found a concise way of checking whether a list contains consecutive integers or not. The shortest I found is to generate a range between the first and last element of that list and check that that range is the original list.
:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L

Range from first to last is one approach which had occurred to me in CJam. The other was sort, pairwise differences, check they're all 1. I don't know how easy that is in Brachylog.

@PeterTaylor There is no short way of generating consecutive pairs (or directly compute pairwise differences) unfortunately (for now).

Batch, 133 bytes
@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

Takes input as command-line arguments. Exits with error level 0 for success, 1 for failure.

Java, 170 bytes
boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Array x has values from 0 to maximum number in order (Python would be much better here...). The loop goes backwards trying to match the lowest (x[b]) or the highest (x[e]) number not yet encountered; if it does, that number could be reached in that step.
Test code here.

05AB1E, 7 bytes
ηε{¥P}P

Try it online!

R, 57 bytes
function(x,y=x[-1],`!`=cummin){y[]=y+1-!x&y-1+!-x;any(y)}

Try it online!
Completely different and somewhat shorter approach to JDL's previous R answer.
Returns FALSE for antsy sequences, TRUE for not-antsy sequences.
Add two bytes to reverse the output to truthy for antsy sequences: 59 bytes, but save 4 bytes by taking input using scan: 55 bytes

Java 7, 170 169 bytes
import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Ungolfed & test code:
Try it here.
import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19 }));
    System.out.println(c(new int[]{ 34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19 }));
    System.out.println(c(new int[]{ 47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }));
  }
}

Output:
true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true

Mathematica, 47 bytes
A little longer than Martin Ender's solution (surprise surprise!). But it's one of my more unreadable efforts, so that's good :D
#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Explanation:
#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list

[JavaScript], 54 bytes
e=>e.every((f,m)=>!m||e.some((e,o)=>o<m&&(e-f)**2==1))

Try it online!

Welcome to Code Golf, and nice first answer! :)

You can get down to 58 bytes if you remove the ,s=e-f and then instead of s*s, do (e-f)**2.

also, you don't have to include the f= in the byte count, which means you can get down to 56 bytes. :)

Oh wow, awesome! thanks for these suggestions! It was my first, but definitely not my last code golf :)

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:
100 Prisoners and a light bulb
100 Prisoners and a light bulb
You may have seen this puzzle over on the puzzles exchange or perhaps heard it somewhere else. If you are unfamiliar with this puzzle check out:  100 Prisoners and a Light bulb
The gist of this puzzle is that there are 100 prisoners, each one is separated from one another and must go into a room one at a time. The prisoner selected to go into the room is selected uniformly at random each time. In this room there is a light bulb and a switch, the prisoner must either turn the light on, turn the light off, or do nothing. At any given time one of the prisoners may say that all 100 prisoners have been in the room at least once. If he is correct they are all freed, if they are incorrect they are all killed. Prior to being separated the group of prisoners may discuss a strategy and they may never communicate again.
One working strategy:

The prisoners select one prisoner as the leader. When anyone else enters the room they do nothing unless it's the first time they enter the room and the light is off; in that case, they turn the light on. When the leader enters the room and the light is on then he turns the light off and maintains a counter, adding one to it. Once he counts 99 (the light has been turned on once for every other prisoner) he knows that all 100 (including himself) have been in the room, and he claims their freedom.

The code challenge:
Take no input into your program.
Simulate the strategy and output the number of times a prisoner entered the room before the leader claimed their freedom.
n represents the number of times a prisoner enters the room for the first time.
k represents the leader of the prisoners.
d represents a data structure holding boolean values for each prisoner.
l represents a boolean value to hold the state of the light bulb.
i represents the number of iterations of the puzzle before it ends.
Examples:
Randomly pick an element from d. if l is false and k[rand] is false then l is now true and d[rand] is true. i = i + 1
Randomly pick an element from d. if l is true and d[rand] is false then do nothing. i = i + 1
Randomly pick an element from d. if l is false and d[rand] is true then do nothing. i = i + 1
Randomly pick an element from d. if d[rand] = k and if l is false then do nothing. i = i + 1
Randomly pick an element from d. if d[rand] = k and if l is true, set l to false, add 1 to n. i = i + 1
Randomly pick an element from d. if d[rand] = k and if l is true and n = 99 then end puzzle.  i = i + 1 and output i.
this is code-golf so the shortest code wins. Have Fun!

Shouldn't the close vote people add some useful comment?

@Lembik I would hope so, I am watching the close votes pile up and as I read my question over and over I am struggling to find a reason.

It's probably not clear what is asked. I'll try to add an answer, but I'm not too sure too

Better a close vote with no explanation than nothing at all. If it results in the question being put on hold then a reason will be displayed, and others can comment with suggestions for improvement. The idea of putting on hold is to prevent answers coming in until the challenge is ready, so answers aren't invalidated by any changes that need to be made to the wording. It's a positive thing.

@trichoplax point taken, however a close vote and a comment is much more helpful to the OP to make corrects faster and easier.

What needs to be quick is putting on hold. That prevents any answers so then improvements can be made slowly until it's ready. I've just read through and decided it isn't yet clear to me, so I've voted to put on hold as unclear. That was the urgent bit. Now I can take the time to try and explain what I found unclear so the challenge can be edited and then reopened.

Randomly select one element from an array of 100 where one is the leader For this I wasn't sure if "one is the leader" meant that one should also be randomly selected, or whether the leader is always at index 1.

For future challenges, I recommend leaving them in the sandbox for a few days to gather feedback before posting here on main. I've done this for all of my challenges except one, and that one didn't go well... I find the sandbox works well for fine tuning and potentially making changes that are harder to make after posting.

I have some problems reading the challenge (and the edit). Probably due to difficulties with the english language. But overall the challenge seems clear. @trichoplax do you really not understand Randomly select one element from an array of 100 where one is the leader as Randomly select one element from an array of 100 so that this one is the leader?

In fact, after the edit it's so less clear. The first few paragraph of the added section are a total mess. From the initial text, is seems that the leader is chosen at random from the 100 prisoners, but now ... I cannot tell

@edc65 The sentence didn't make immediately clear to me what the meaning was, so I'd like to see it replaced with an unambiguous one. Removing such ambiguities will make the challenge read more smoothly, which will increase the number of people who answer, which is better for everyone.

I don't mind how long it takes to get it clear, or how many edits. There's no rush.

The hidden quoted block seems to be essential rather than optional. I think it should be a non-hidden quoted block. Also, in this challenge I find it hard to decide when an answer is correct

It's worth considering this meta post on non observable requirements. Is it a requirement that code follows the steps described and uses the same method? Or is any code that gives output with the equivalent probability distribution valid?

@trichoplax Good point. I was about to point out the same, but the linked post explains it much better

Hopefully the new edit makes things a little more clear.

If the edit is to correct a previous unclear wording, then it would be better to remove the previous wording and just settle on one new wording that is unambiguous. The old versions are all stored in the edit history, so it isn't necessary to have "Edit" as a heading - you can simply rewrite and delete anything no longer required.

"Output the number of times a prisoner enters the room after it is guaranteed they have all been in the room at least once." Huh? Guaranteed by what process? Don't they claim their freedom once it's guaranteed that they've all been in the room at least once, so that the output would be 0 unconditionally?

@PeterTaylor Output the number of times a prisoner enters the room after the prisoners have gained their freedom. n iterations.

Do they not stop entering the room when they're free?

They do not keep entering no.. while(not free){iterate, n++} return n;

I believe "the number of times a prisoner enters the room after the prisoners have gained their freedom" is intended to mean "the total number of times a prisoner has entered the room when the prisoners gain their freedom". The current phrasing gives a meaning that is almost opposite, so I feel this challenge would benefit from being on hold longer while this is discussed.

@Emigna no it isn't as the leader will be the last random chosen index.

@jacksonecac That's not true. The light will be turned on by the 99th prisoner, and the leader has already entered the room, but needs to enter again after the light was turned on the 99th time in order to count the last prisoner, even though they've all been in the room. Also, it's probably helpful to note in the question that if you're doing it right, you should be getting a number ~10000. The algorithm is probably O(n^2)

@mbomb007 so the i.e. is correct the definition isn't.

@jacksonecac So it's not while (not free) {...}, it's really while (count < 99) {...}, and you have to increment that count whenever the leader turns off the light.

@mbomb007 not free and count < 99 are synonymous. You can't be free if count < 99 and you can't be in prison if count > 98

@jacksonecac The leader doesn't know "magically" when the 99th prisoner has turned on the light. The leader is chosen randomly, so you have to wait for the leader to be chosen and see that the light is on for the 99th time. We're just trying to be clear for users who might try to implement the algorithm wrong. The prisoners are not freed until the leader has entered the room and counted 99, which is different than checking whether every prisoner has been in the room and flipped the light with your code.

@mbomb007 that depends entirely on when you increment n. Which should only be when the leader is in the room. n is set to 99 when the leader has entered the room for the last time and when he counts to 99. Once he counts to 99, the program should exit and return the number iterations, n.

Correct. But it wasn't clear from your description of the challenge. "Repeat this process until all elements are true and output how many iterations there were." - this description is wrong

It seems that we now know what the requirement is, but the challenge wording doesn't make that clear for new people arriving, so it needs to be edited to be short, clear and unambiguous.

The comment "n is set to 99 when the leader has entered the room for the last time ... the program should exit and return the number of iterations, n." means "always output 99", which isn't what is intended. This is just a typo, but it's these little things that need to be tidied up to avoid confusing people. We're getting there but this isn't ready yet.

This needs re-opened or deleted. I cannot do either.

Python 2, 133 bytes
I used binary operations to keep track. I had if(i<1)*b:... but I think that's an off-by-one error. Not sure.
from random import*
L=2**99-1
b=l=c=0
while l<99:
    i=randint(0,99)
    if(i>98)*b:b=0;l+=1
    elif(L&1<<i)*(b<1):b=1;L|=1<<i
    c+=1
print c

Try it online
Less golfed:
from random import*
L=[1for _ in range(100)]
b=l=c=0
while l<99:                         # check leader's count of prisoners
    i=randint(0,99)
    if b and i==99:b=0;l+=1         # if light on and leader, turn off and count
    elif L[i] and b<1:b=1;L[i]=0    # else if new prisoner and light off, turn on
    c+=1                            # iterations
print c

CJam (26 bytes)
100,1a*0-{{__100mr>!}g;}%,

Dissection
100,1a*0-  e# Generate a list [1 1 1 2 1 3 1 ... 98 1 99] representing (in reverse order)
           e# the number of prisoners at each step who can advance to the next step
{          e# For each element in the list...
  {        e#   While we fail to select a suitable prisoner...
    __     e#     dup twice: once to leave on stack as a counter, and once for comparison
    100mr  e#     Select a random prisoner
    >!     e#     Test whether that prisoner is suitable
  }g
  ;        e#  Pop to avoid overcounting by one
}%
,          e# Count up the values we left on the stack

Perl 5, 77 bytes
++$i,($s=0|rand 100)?!$a[$s]&&!$l++&&$a[$s]++:$l&&++$n&($l=0)while$n<99;say$i

Try it online!

Python 3, 164 bytes, aka garbage :)
from random import*
d={}
a=l=n=p=0
for i in range(100):
 d[i]=0
while n<100:
 a+=1
 p=randint(0,99)
 if p==50:
  l=0
 else:
  l=1
 if d[p]==0:
  d[p]=1
  n+=1
print(a)

I think you've misunderstood the problem. This always prints 100, while the number of times the prisoners have entered the room is variable.

it only prints at the end like @mbomb's answer

As it should. But your answer counts the number of different prisoners that have entered the room, so the result is always 100.

Oh You want the iterations, I see.

That's better, but the output is still incorrect. Compare your answer with mbomb's.

You're ignoring a large part of the problem and only check if all 100 have already entered the room. The problem is a bit more complex than that.

I think i get it now will edit later

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


text:
Traveling Pumpkin Problem
Background:
Jack is a pumpkin that enjoys spooking the citizens of the villages near his pumpkin patch every Halloween.  However, every year after someone lights the candle inside of him, he has a limited amount of time to spook everyone before the candle burns out, thus being unable to spook any more villagers because nobody can see him.  In past years, he has only been able to spook a small amount of villages due to his poor decision making, but now that he has you to help him, he will be able to spook as many villages as possible!
Task:
Given a list of village locations and a candle lifespan, output the maximum number of villages Jack can visit.  You do not have to print the path itself.
Input:
The lifespan of the candle and a list of village locations in a Cartesian coordinate system.  The pumpkin patch Jack originates from will always be at 0,0.  You may format the input in anyway you wish.  To simplify Jack's movements, he can only move horizontally, vertically, or diagonally, meaning his candle will either lose 1 or 1.5 (he takes a bit longer diagonally) units of life every move.  The candle burns out when the lifespan is less than or equal to 0.
Output:
An integer equal to the maximum number of villages Jack can visit before the candle burns out.
Rules:
This is code-golf, so shortest code in bytes wins.  Standard loopholes are not allowed.
Test cases:
// Format [lifespan] [list of village coordinates] -> [maximum visit-able villages]

4 -1,0 1,0 2,0 3,0 4,0 5,0 -> 3
4 1,1 2,2 3,3 -> 2
5 1,1 2,1 3,1 4,1 5,0 5,1 -> 4

Giggling at the title

Can the input coordinates be a complex number for each village?

@LuisMendo I wasn't planning on having them unaligned with the grid.

I mean 4-j instead of 4 -1, etc

"To simplify Jack's movements" is kinda ironic, this is a lot more difficult now :D

@LuisMendo Ah, then yes you can take in the numbers in any format you wish.

@Pietu1998 Jack is a simple pumpkin, he only knows how to move in cardinal and ordinal directions :P

I think your first case output should be 3 if i am not wrong

@Numberknot Ah you're right, both the first and second test cases should be one lower.  I'll modify them as I was trying to test for specific things and forgot that I specified that a lifespan value of 0 meant no light.

Is he visit again at the same village too?

@Numberknot No, once a village has been scared they will not fall for the same trick, he can only scare each village one time.

@Yodle Except for next year, of course.

"To simplify Jack's movements..." wouldn't it be simpler if it was sqrt(2) instead of 1.5...? Because, you know... squares?

Can villages be on top of each other (i.e. at the same coordinates)?

@mbomb007 I had it like that, but I figured dealing with halves would make it easier to work with.  Maybe not though!

@ETHproductions No, only one village can occupy a given x,y pair.

This is a N-Pumpkin Hard problem, so in general the max number of villages could be difficult to find. There is a max number of villages?

Actually, what is 1.5 here, in real life is √2. But, let's simplify things.

@edc65 Let's say no more than 1000, but I don't have any large test cases currently.

@EriktheGolfer It sounded easier to me, at least in my head, to have a rational number, but I guess if enough people think sqrt(2) is better, I could change it (I originally had it like that on the sandbox, but changed it for here).  Most of the answers already have 1.5 though.

@Yodle Wait; isn't it just me? I did not make a suggestion to replace it with sqrt(2), I just stated a real-life vs. PPCG fact here. In fact, I opposed to it ("But let's simplify things.")

@EriktheGolfer Ah okay sorry, just wanted to make sure I wasn't making it more difficult :P

For test case "5 1,1 2,1 3,1 4,1 5,0 5,1", it seems that the answer be 3 rather than 4.

@mso I'm pretty sure it's 4.  You go diagonally to 1,1, with 3.5 lifespan left.  Then you go right until you reach 0.5 which is 3 moves, all of which have villages.

Jelly, 30 29 27 25 bytes
_AṢæ..
0,0ṭṚç2\+\<S
Œ!ç€Ṁ

Try it online!
Apparently Jelly's dot product just ignores a list size mismatch and doesn't multiply the extra elements of the other array, just adds them. Shaves off 2 bytes.
Explanation
_AṢæ..              Helper link to calculate distance. Arguments: a, b
_                     subtract the vertices from each other
 A                    take absolute values of axes
  Ṣ                   sort the axes
   æ..                dot product with [0.5]

0,0ṭṚç2\+\<S        Helper link to calculate max cities. Arguments: perm, max
0,0                   create pair [0,0]
   ṭ                  append that to the permutation
    Ṛ                 reverse the permutation (gets the [0,0] to the beginning)
     ç2\              find distances of each pair using the previous link
        +\            find all partial sums
          <           see if each sum was less than the max
           S          sum to count cases where it was

Œ!ç€Ṁ               Main link. Arguments: cities, max
Œ!                    get permutations of cities
  ç€                  find max cities for each permutation using the previous link
    Ṁ                 take the maximum

In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations)

@edc65 Nowhere does it say that cases that big need to be testable, as long as the algorithm theoretically works given enough time and memory. (Programs that can actually solve TSP for n ≈ 1000 are so complex they wouldn't be fun to golf anymore.)

Ok not 1000, but not even 15?

@edc65 I can't find an algorithm that would be fast and look easily implementable in Jelly. I might look into making a more efficient solution (e.g. Held-Karp) in another language. BTW, none of the answers use actually fast algorithms; the JS one is better, but slow if there are many cities in range.

Java 7, 206 201 bytes
Thanks to @KevinCruijssen for saving 5 bytes

int f(float e,int[]a,int[]b){int x=0,y=0,c=0,d=0,t;float s;for(int i:a){s=(i!=x&b[c]==y)|(i==x&b[c]!=y)?Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1:Math.abs(i-x)*1.5;d+=e-s>=0?1:0;e-=s;x=i;y=b[c++];}return d;}

Ungolfed
class Travellingpumpkin {

public static void main(String[] args) {

    System.out.println(f( 5 ,new int[] { 1,2,3,4,5,5 } , new int[] { 1,1,1,1,0,1 } ));

}
static int f( double e , int[]a , int[]b ) {
    int x = 0 , y = 0 , c = 0 , d = 0 , t;
    double s ;

    for ( int i : a ) {
    s = ( i != x & b[c] == y )|( i == x & b[c] != y )
         ? Math.sqrt( ( t = i - x ) * t + ( t = b[c] - y ) * t ) * 1
         : Math.abs( i - x ) * 1.5 ;

        d += e-s >= 0 ? 1 : 0 ;
        e -= s ;
        x = i ; y = b [ c++ ] ;
    }
    return d ;

}

   }

Nice, good on including the "ungolfed" form.  Although if you turned that in I think the code reviewer would not call it ungolfed.  ;)

+1. One thing to golf: You use i-x twice and b[c]-y twice, so you can add ,t to the ints, and then use this: Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1 instead of Math.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1.

How could this possibly work in the general case?

JavaScript (ES6), 145
Anonymous recursive function, parameter s is the candle lifespan, parameter l is the village coordinate list.
A Depth First Search, stopping when the distance reachs the candle lifespan
f=(s,l,x=0,y=0,v=0,A=Math.abs,X=Math.max)=>X(v,...l.map(([t,u],i,[h,...l],q=A(t-x),p=A(u-y),d=(l[i-1]=h,p+q+X(p,q))/2)=>s<=d?v:f(s-d,l,t,u,1+v)))

Less golfed see the snippet below
Test

f=(s,l,x=0,y=0,v=0,A=Math.abs,X=Math.max)=>
  X(v,...l.map(
      ([t,u],i,[h,...l],q=A(t-x),p=A(u-y),d=(l[i-1]=h,p+q+X(p,q))/2)=>
      s<=d?v:f(s-d,l,t,u,1+v)
  ))

// ungolfed version

F=(s, l,
   x=0, y=0, // current position
   v=0 // current number of visited sites
  ) =>
   Math.max(v, ...l.map(
     (
       [t,u], i, [h,...l], // lambda arguments
       q = Math.abs(t-x), p = Math.abs(u-y), // locals
       d = (p+q+Math.max(p,q))/2
     ) => (
       l[i-1] = h,
       s <= d
         ? v
         : F(s-d, l, t, u, v+1)
     )
  ))

;[[4,[[-1,0],[1,0],[2,0],[3,0],[4,0],[5,0]], 3]
,[4, [[1,1],[2,2],[3,3]], 2]
,[5, [[1,1],[2,1],[3,1],[4,1],[5,0],[5,1]], 4]
].forEach(test=>{
  var span=test[0],list=test[1],check=test[2],
      result = f(span, list)
  console.log(result==check?'OK':'KO',span, list+'', result)
})

Scala, 196 bytes
def f(l:Int,c:(Int,Int)*)=c.permutations.map(x=>((0,0)+:x sliding 2 map{p=>val Seq(c,d)=Seq((p(0)._1-p(1)._1)abs,(p(0)._2-p(1)._2)abs).sorted
c*1.5+(d-c)}scanLeft 0d)(_+_)takeWhile(_<l)size).max-1

Ungolfed:
def g (l: Int, c: (Int, Int)*) = {
    c.permutations
    .map { x =>
        ((0, 0) +: x).sliding(2).map({ p =>
            val Seq(c, d) = Seq((p(0)._1 - p(1)._1) abs, (p(0)._2 - p(1)._2) abs).sorted
            c * 1.5 + (d - c)
        }).scanLeft(0d)(_ + _).takeWhile(_ < l).size
    }.max - 1
}

Explanantion:
def f(l:Int,c:(Int,Int)*)= //defien a function with an int and a vararg-int-pait parameter
  c.permutations           //get the permutations of c, that is all possible routes
  .map(x=>                 //map each of them to...
    ((0,0)+:x                //prepend (0,0)
    sliding 2                //convert to a sequence of consecutive elemtens
    map{p=>                  //and map each of them to their distance:
      val Seq(c,d)=Seq(        //create a sequence of
        (p(0)._1-p(1)._1)abs,  //of the absolute distance between the x points
        (p(0)._2-p(1)._2)abs   //and he absolute distance between the y coordinates
      ).sorted                 //sort them and assign the smaller one to c and the larger one to d
      c*1.5+(d-c)              //we do the minimum difference diagonally
    }                        //we now have a sequence of sequence of the distances for each route
    scanLeft 0d)(_+_)       //calculate the cumulative sum
    takeWhile(_<l)          //and drop all elements that are larger than the candle lifespan
    size                    //take the size
  ).max-1                   //take the maximum, taht is the size of the largest route and subtract 1 because we added (0,0) at the beginning

MATL, 27 bytes
EH:"iY@OwYc!d|]yyXl++Ys>sX>

EDIT (26 nov 2016): Due to changes in the Xl function, it has to be replaced in the above code by 2$X>. The links below incorporate that modification.
Try it online! Or verify all test cases.
Explanation
The pumpkin distance between two cities separated Δx and Δy in each coordinate can be obtained as ( |Δx| + |Δy| + max(|Δx|, |Δy|) ) / 2.
The code follows these steps:

Generate all permutations of x coordinates and of y coordinates, and prepend a to each 0. Each permutation represents a possible path.
Compute absolute consecutive differences for each path (these are |Δx| and |Δy| above).
Obtain the pumpkin distance for each step of each path.
Compute the cumulative sum of distances for each path.
Find, for each path, the number of steps before the accumulated distance reaches the chandle lifespan.
Take the maximum of the above.

Commented code:
E        % Input candle lifespan implicitly. Multiply by 2
H:"      % Do thie twice
  i      %   Input array of x or y coordinates
  Y@     %   All permutations. Gives a matrix, with each permutation in a row
  OwYc   %   Prepend a 0 to each row
  !      %   Transpose
  d|     %   Consecutive differences along each column. Absolute value
]        % End
yy       % Duplicate the two matrices (x and y coordinates of all paths)
Xl       % Take maximum between the two, element-wise
++       % Add twice. This gives twice the pumpkin distance
Ys       % Cumulative sum along each column
>        % True for cumulative sums that exceed twice the candle lifespan
s        % Sum of true values for each column
X>       % Maximum of the resulting row array. Inmplicitly display

can MATL really generate all permutation of 1000 (x,y) pairs?

@edc65 No, that's too much (there are over 10^2500 permutations of 1000 elements). I don't think any language can

In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations)

@edc65 Ah, I see. 1000 villages seems unrealistic if the problem is NP-hard, as it appears to be

Python 2.7, 422 bytes
thanks to NoOneIsHere for pointing out additional improvements!
thanks to edc65 for noting not to save the list but use iterators instead!
Try it online!
from itertools import permutations
def d(s,e):
    d=0
    while s!=e:
        x=1 if s[0]<e[0] else -1 if s[0]>e[0] else 0
        y=1 if s[1]<e[1] else -1 if s[1]>e[1] else 0
        s=(s[0]+x,s[1]+y)
        d+=(1,1.5)[x and y]
return d
l,m=4,0
for o in permutations([(1,1),(2,2),(3,3)]):
    a,c=l-d((0,0),o[0]),1
    for j in range(len(o)-1):
        a-=d(o[j],o[j+1])
        c+=(0,1)[a>0]
    m=max(c,m)
print m

Explanation:
The function calculates the distance between two points according to the given rules, the loop iterates through all permutations generated by the generator of the input and calculates the distance, if the distance is lesser than the candle lifespan it subtracts it and adds the place to the counter, if that counter is greater than the current max it substitutes it.
ungolfed:
from itertools import permutations

def distance(start_pos, end_pos):
    distance = 0
    while start_pos != end_pos:
        mod_x = 1 if start_pos[0] < end_pos[0] else -1 if start_pos[0] > end_pos[0] else 0
        mod_y = 1 if start_pos[1] < end_pos[1] else -1 if start_pos[1] > end_pos[1] else 0
        start_pos = (start_pos[0] + mod_x, start_pos[1] + mod_y)
        distance += (1, 1.5)[mod_x and mod_y]
    return distance

lifespan, max_amount = 4, 0
for item in permutations([(1,1), (2,2), (3,3)]):
    lifespan_local, current = lifespan - distance((0,0), item[0]), 1
    for j in range(len(item) - 1):
        lifespan_local -= distance(item[j], item[j + 1])
        current += (0, 1)[lifespan_local > 0]
    max_amount = max(current, max_amount)
print max_amount

Hello, and welcome to PPCG! You can make current c, and ll m.

wow, thanks! missed that one

In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations)

will look into that at some point, thanks for the heads up. I didn't really read the comments because there are many of them.

done, using generator now, instead of storing all of the permutations it generates them on the go, should use about O(n) for the permutation.

Racket
(define (dist x1 y1 x2 y2)     ; fn to find distance between 2 pts
  (sqrt(+ (expt(- x2 x1)2)
          (expt(- y2 y1)2))))

(define (fu x1 y1 x2 y2)       ; find fuel used to move from x1 y1 to x2 y2;
  (let loop ((x1 x1)
             (y1 y1)
             (fuelUsed 0))
    (let* ((d1 (dist (add1 x1) y1 x2 y2))        ; horizontal movement
           (d2 (dist x1 (add1 y1) x2 y2))        ; vertical movement
           (d3 (dist (add1 x1) (add1 y1) x2 y2)) ; diagonal movement
           (m (min d1 d2 d3))) ; find which of above leads to min remaining distance;
      (cond
        [(or (= d2 0)(= d1 0)) (add1 fuelUsed)]
        [(= d3 0) (+ 1.5 fuelUsed)]
        [(= m d1) (loop (add1 x1) y1 (add1 fuelUsed))]
        [(= m d2) (loop x1 (add1 y1) (add1 fuelUsed))]
        [(= m d3) (loop (add1 x1) (add1 y1) (+ 1.5 fuelUsed))]))))

(define (f a l)
  (define u (for/list ((i l))
    (fu 0 0 (list-ref i 0) (list-ref i 1))))  ; find fuel used for each point;
  (for/last ((i u)(n (in-naturals)) #:final (>= i a))
    n))

Testing:
(f 4 '((1 1) (2 2) (3 3))) ;-> 2
(f 5 '((1 1) (2 1) (3 1) (4 1) (5 0) (5 1))) ;-> 4

Output:
2
4

However, above code does not work for negative values of x and y.

Python, 175 bytes
def f(c,l):
 def r(t):p=abs(t[0]-x);q=abs(t[1]-y);return p+q-.5*min(p,q)
 v=0;x,y=0,0
 while c>0 and len(l)>0:
  l.sort(key=r);c-=r(l[0]);x,y=l.pop(0)
  if c>=0:v+=1
 return v

c is the lifespan of the candle, l is a list of tuples - village coordinates, v is the number of visited villages, (x,y) is pair of coordinates of the village Jack is currently in.
r(t) is a function which calculates the distance to the current position and is used to sort the list so that the closest becomes l[0]. The formula used is |Δx| + |Δy| - min(|Δx|, |Δy|) / 2.
Try it here!

PHP, 309 bytes
function j($x,$y,$c,$v){if($s=array_search([$x,$y],$v))unset($v[$s]);for($c--,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v))>$m?$n:$m;for($c-=.5,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v))>$m?$n:$m;return$s?++$m:$m;}echo j(0,0,$argv[1],array_chunk($argv,2));

Absolutely brute force and not even very short. Use like:
php -r "function j($x,$y,$c,$v){if($s=array_search([$x,$y],$v))unset($v[$s]);for($c--,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v))>$m?$n:$m;for($c-=.5,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v))>$m?$n:$m;return$s?++$m:$m;}echo j(0,0,$argv[1],array_chunk($argv,2));" 5 1 1 2 1 3 1 4 1 5 0 5 1

With more whitespace and saved in a file:
<?php
function j( $x, $y, $c, $v)
{
    if( $s = array_search( [$x,$y], $v ) )
        unset( $v[$s] );

    for( $c--, $i=4; $c>0 && $i--;)
        $m = ( $n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v) )>$m ? $n : $m;

    for( $c-=.5, $i=4; $c>0 && $i--;)
        $m = ( $n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v) )>$m ? $n : $m;

    return $s ? ++$m : $m;
}
echo j( 0, 0, $argv[1], array_chunk($argv,2) );


text:
Totally Invertible Submatrices
(inspired by this question over on Math)
The Definitions
Given an n x n square matrix A, we can call it invertible if there exists some n x n square matrix B such that AB = BA = In, with In being the identity matrix of size n x n (the matrix with the main diagonal 1s and anything else 0), and AB and BA representing usual matrix multiplication (I won't go into that here - go take a linear algebra class).
From that, we can call an m x n matrix C totally invertible if every k x k submatrix (defined below) of C is invertible for all k > 1, k <= (smaller of m,n).
A submatrix is defined as the resulting matrix after deletion of any number of rows and/or columns from the original matrix. For example, the below 3x3 matrix C can be transformed into a 2x2 submatrix C' by removing the first row 1 2 3 and the middle column 2 5 8 as follows:
C = [[1 2 3]
     [4 5 6]    -->  C' = [[4 6]
     [7 8 9]]              [7 9]]

Note that there are many different submatrix possibilities, the above is just an example. This challenge is only concerned with those where the resulting submatrix is a k x k square matrix.
The Challenge
Given an input matrix, determine if it is totally invertible or not.
The Input

A single matrix of size m x n, in any suitable format.
Without loss of generality, you can assume m <= n or m >= n, whichever is golfier for your code, and take the input that way (i.e., you get a transpose operation for free if you want it).
The input matrix size will be no smaller than 3 x 3, and no larger than your language can handle.
The input matrix will consist of only numeric values from Z+ (the positive integers).

The Output

A truthy/falsey value for whether the input matrix is totally invertible.

The Rules

Either a full program or a function are acceptable.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

The Examples
Truthy

[[1 2 3]
 [2 3 1]
 [3 1 2]]

[[2 6 3]
 [1 12 2]
 [5 3 1]]

[[1 2 3 4]
 [2 3 4 1]
 [3 4 1 2]]

[[2  3  5  7  11]
 [13 17 19 23 29]
 [31 37 41 43 47]]

Falsey

[[1 2 3]
 [4 5 6]
 [7 8 9]]

[[1 6 2 55 3]
 [4 5 5 5  6]
 [9 3 7 10 4]
 [7 1 8 23 9]]

[[2 3 6]
 [1 2 12]
 [1 1 6]]

[[8 2 12 13 2]
 [12 7 13 12 13]
 [8 1 12 13 5]]

Where is the singular submatrix in 2 6 3; 1 12 2; 5 3 1?

@feersum Whoops - thanks for the catch. That was supposed to have gone under Truthy and the one below it was supposed to be a 6 in the corner, not a 7. Clumsy typos.

At first, I thought the title said "totally invertible submarines".

Jelly, 26 24 23 20 19 17 16 bytes
-1 byte thanks to @miles (unnecessary for each, €, when taking determinants)
-2 bytes, @miles again! (unnecessary chain separation, and use of Ð€ quick)
ZœcLÆḊ
œcÐ€JÇ€€Ȧ

TryItOnline! or all 8 tests
How?
œcÐ€JÇ€€Ȧ  - Main link: matrix as an array, M
    J      - range of length -> [1,2,...,len(a)] (n)
  Ð€       - for each of right argument
œc         -     combinations of M numbering n
     Ç€€   - call the last link (1) as a monad for €ach for €ach
        Ȧ  - all truthy (any determinant of zero results in 0, otherwise 1)
                 (this includes an implicit flattening of the list)

ZœcLÆḊ - Link 1, determinants of sub-matrices: row selection, s
Z      - transpose s
   L   - length of s
 œc    - combinations of transposed s numbering length of s
    ÆḊ - determinant

I was thinking I needed it because I have a bunch of combinations, but no I do not need to instruct to explicitly. Thanks!

I learned about it from that last challenge using determinants, and verified that it indeed does have ldepth = 2 in the source

Also I think you can save a byte in link 2 using ZœcLÆḊ and another byte in the main link by çÐ€JȦ

Good stuff @miles thanks again! I thought that the first of those two did not work when I tried it, but it must have been when I was using the € you golfed off. Totally forgot about Ð€.

@miles ...and that gets another byte off by allowing me to combine main and the link before it.

Nice combining, I think you can make it a one liner if you want with œcÐ€JµZœcLÆḊµ€€Ȧ which is also 16 bytes

Mathematica 10.0, 34 bytes
#~Minors~n~Table~{n,Tr@#}~FreeQ~0&

A 6-tilde chain... new personal record!

MATL, 57 bytes
tZyt:Y@!"@w2)t:Y@!"@w:"3$t@:)w@:)w3$)0&|H*XHx]J)]xxtZy]H&

Of course, you can Try it online!
Input should be in 'portrait' orientation (nRows>=nColumns). I feel that this may not be the most efficient solution... But at least I'm leaving some room for others to outgolf me. I would love to hear specific hints that could have made this particular approach shorter, but I think this massive bytecount should inspire others to make a MATL entry with a completely different approach. Displays 0 if falsy, or a massive value if truthy (will quickly become Inf if matrix too large; for 1 extra byte, one could replace H* with H&Y (logical and)). Saved a few bytes thanks to @LuisMendo.
tZy  % Duplicate, get size. Note that n=<m.
%   STACK:  [m n], [C]
t: % Range 1:m
%   STACK:  [1...m], [m n], [C]
Y@   % Get all permutations of that range.
%   STACK:  [K],[m n],[C] with K all perms in m direction.
!"   % Do a for loop over each permutation.
%   STACK:  [m n],[C], current permutation in @.
@b   % Push current permutation. Bubble size to top.
%   STACK:  [m n],[pM],[C] with p current permutation in m direction.
2)t:Y@!" % Loop over all permutations again, now in n direction
%   STACK: [n],[pM],[C] with current permutation in @.
@w:" % Push current permutation. Loop over 1:n (to get size @ x @ matrices)
%   STACK: [pN],[pM],[C] with loop index in @.
3$t  % Duplicate the entire stack.
%   STACK: [pN],[pM],[C],[pN],[pM],[C]
@:)  % Get first @ items from pN
%   STACK: [pNsub],[pM],[C],[pN],[pM],[C]
w@:) % Get first @ items from pM
%   STACK: [pMsub],[pNsub],[C],[pN],[pM],[C]
w3$)  % Get submatrix. Needs a `w` to ensure correct order.
%   STACK: [Csub],[pN],[pM],[C]
0&|  % Determinant.
%   STACK: [det],[pN],[pM],[C]
H*XHx% Multiply with clipboard H.
%   STACK: [pN],[pM],[C]
]    % Quit size loop
%   STACK: [pN],[pM],[C]. Expected: [n],[pM],[C]
J)   % Get last element from pN, which is n.
%   STACK: [n],[pM],[C]
]    % Quit first loop
xxtZy% Reset stack to
%   STACK: [m n],[C]
]    % Quit final loop.
H& % Output H only.