101
\$\begingroup\$

This challenge was inspired by this Wendy's commercial from 1984.

Where's the beef?

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 ]
Improve this question
\$\endgroup\$
15
  • \$\begingroup\$ Is using 1-based indices allowed (where the top left is (1,1))? \$\endgroup\$
    – Doorknob
    Oct 23, 2016 at 16:07
  • \$\begingroup\$ @Doorknob Yes, if it's the same format for both X and Y (question updated accordingly). \$\endgroup\$
    – Arnauld
    Oct 23, 2016 at 16:12
  • 37
    \$\begingroup\$ Bonus points if we also output wether the 0xBEEF is 0xDEAD? :P \$\endgroup\$
    – TuxCrafting
    Oct 23, 2016 at 16:21
  • 12
    \$\begingroup\$ This challenge is really random and kinda silly. But it's actually a pretty great challenge still. +1 \$\endgroup\$
    – DJMcMayhem
    Oct 23, 2016 at 16:38
  • 1
    \$\begingroup\$ Can I output y, x (i.e. reverse order)? \$\endgroup\$
    – Luis Mendo
    Oct 23, 2016 at 22:31

23 Answers 23

Reset to default
42
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
9
  • 1
    \$\begingroup\$ 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) \$\endgroup\$
    – DJMcMayhem
    Oct 23, 2016 at 17:02
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Doorknob
    Oct 23, 2016 at 17:21
  • \$\begingroup\$ Oh interesting. How convenient! \$\endgroup\$
    – DJMcMayhem
    Oct 23, 2016 at 17:39
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Oct 23, 2016 at 17:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Christian Rondeau
    Oct 25, 2016 at 13:01
30
\$\begingroup\$

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].
Improve this answer
\$\endgroup\$
8
  • 15
    \$\begingroup\$ I don't get it... how can you code something that is not human readable?? \$\endgroup\$
    – David Gomes
    Oct 23, 2016 at 17:46
  • 15
    \$\begingroup\$ Jelly is by far easier to write than to read. :P \$\endgroup\$
    – Dennis
    Oct 23, 2016 at 18:54
  • 52
    \$\begingroup\$ @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 ;-) \$\endgroup\$
    – Francesco
    Oct 23, 2016 at 19:36
  • 1
    \$\begingroup\$ You could output (x,y) with ṡ4Z€Ḅw€“Ье‘ĖUṀ \$\endgroup\$
    – Jonathan Allan
    Oct 24, 2016 at 2:04
  • 2
    \$\begingroup\$ @JonathanAllan Nice. There's also ṡ€4ḄZjw“¿ÇÇБ’d24 with 0-based indexing, but it is, unfortunately, one byte longer. \$\endgroup\$
    – Dennis
    Oct 24, 2016 at 2:10
22
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ Could you possibly use s.search(r) instead of r.exec(s).index? \$\endgroup\$
    – ETHproductions
    Oct 24, 2016 at 2:39
  • 1
    \$\begingroup\$ @ETHproductions Of course I could. I must have been half asleep yesterday... \$\endgroup\$
    – Neil
    Oct 24, 2016 at 7:32
  • \$\begingroup\$ For me, using nodejs to execute, it is not working unless i change s=>[ to (s,i)=>[, because you need to define i somewhere :/ \$\endgroup\$
    – Mijago
    Oct 25, 2016 at 19:37
  • \$\begingroup\$ @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! \$\endgroup\$
    – Neil
    Oct 25, 2016 at 20:38
  • \$\begingroup\$ I think this fails for 000010110010110011100011100011100011100011110011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 \$\endgroup\$
    – Taemyr
    Oct 26, 2016 at 8:41
14
\$\begingroup\$

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);
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Lince Assassino
    Nov 1, 2016 at 13:27
  • \$\begingroup\$ 163 bytes \$\endgroup\$
    – MD XF
    Jan 19, 2018 at 4:02
10
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
8
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ No worries about x and y being switched. \$\endgroup\$
    – Arnauld
    Oct 23, 2016 at 22:33
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice :) Weirdly, for block patterns sometimes it's golfier to just walk around in a spiral: 1011>001>1(11>){3}1>1 \$\endgroup\$
    – Sp3000
    Oct 24, 2016 at 23:00
  • \$\begingroup\$ @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}. \$\endgroup\$
    – DLosc
    Oct 25, 2016 at 19:48
7
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Use , instead of . in the echo and you can remove the parentheses. (-4) \$\endgroup\$
    – Titus
    Oct 30, 2016 at 20:13
  • \$\begingroup\$ In the comments, Arnauld allows output without a delimiter. (-4) \$\endgroup\$
    – Titus
    Oct 30, 2016 at 20:20
  • \$\begingroup\$ 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) \$\endgroup\$
    – Titus
    Oct 30, 2016 at 20:44
  • \$\begingroup\$ @Titus nice and done \$\endgroup\$
    – Jörg Hülsermann
    Oct 30, 2016 at 20:58
6
\$\begingroup\$

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;
    }

}
Improve this answer
\$\endgroup\$
4
  • 2
    \$\begingroup\$ What are those four spaces there between a[y++]>>=1) and if((a[y]&15)==. Btw, I count 182 bytes instead of 183? :S \$\endgroup\$
    – Kevin Cruijssen
    Oct 24, 2016 at 7:23
  • \$\begingroup\$ @KevinCruijssen fixed . \$\endgroup\$
    – Numberknot
    Oct 24, 2016 at 7:29
  • 1
    \$\begingroup\$ Everything alright ;-) \$\endgroup\$
    – Karl Napf
    Oct 24, 2016 at 15:34
  • 1
    \$\begingroup\$ You can still remove the space between ...a[y++]/=2) and if((a[y]&15)==.... \$\endgroup\$
    – Kevin Cruijssen
    Jun 29, 2017 at 11:47
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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]
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 24: $#:(4 4$#:48879)I.@,@E.] Try it online! \$\endgroup\$
    – Jonah
    Apr 17, 2021 at 0:44
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Might this mistakenly find a "beef" across the boundary where two lines are concatenated? \$\endgroup\$
    – xnor
    Oct 24, 2016 at 23:59
  • \$\begingroup\$ Yeah, I think so. I'll roll the edit back until I can test it properly. \$\endgroup\$
    – Dennis
    Oct 25, 2016 at 0:01
  • 2
    \$\begingroup\$ That's what happens when you use a toroidal bun. \$\endgroup\$
    – mbomb007
    Oct 27, 2016 at 13:46
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Fails for '000010110010110011100011100011100011100011110011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000' Your (.)* needs to be (.){0,8} \$\endgroup\$
    – Taemyr
    Oct 26, 2016 at 8:41
  • \$\begingroup\$ 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})*?(.)*?. \$\endgroup\$
    – Dom Hastings
    Oct 26, 2016 at 9:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Taemyr
    Oct 26, 2016 at 10:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – Taemyr
    Oct 26, 2016 at 10:46
  • \$\begingroup\$ @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! \$\endgroup\$
    – Dom Hastings
    Oct 26, 2016 at 11:31
5
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
7
  • 1
    \$\begingroup\$ You can save 3 characters by combining the regex for the binary EE: (.{8}1110){2} instead of .{8}1110.{8}1110 \$\endgroup\$
    – wullxz
    Oct 24, 2016 at 13:01
  • 1
    \$\begingroup\$ You can also save another 3 bytes by changing length$` into $-[0] \$\endgroup\$
    – Gabriel Benamy
    Oct 24, 2016 at 17:49
  • \$\begingroup\$ @wullxz Of course! I tried \1 but had no luck, didn't think to try {2}! Thanks! \$\endgroup\$
    – Dom Hastings
    Oct 25, 2016 at 7:01
  • \$\begingroup\$ @GabrielBenamy Amazing, thank you very much! Updated! \$\endgroup\$
    – Dom Hastings
    Oct 25, 2016 at 7:01
  • 2
    \$\begingroup\$ @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: perldoc.perl.org/perlvar.html (look for @-) \$\endgroup\$
    – Dom Hastings
    Oct 25, 2016 at 8:16
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ If you sue single spaces instead of 4 and check it on Linux it's 137 \$\endgroup\$
    – ElPedro
    Oct 24, 2016 at 18:42
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – ElPedro
    Oct 24, 2016 at 18:59
  • \$\begingroup\$ @elpedro I'm using Python 3, and it's fine with the import being on the same line. \$\endgroup\$
    – penalosa
    Oct 24, 2016 at 19:02
  • \$\begingroup\$ Fully understood :) \$\endgroup\$
    – ElPedro
    Oct 24, 2016 at 19:03
  • \$\begingroup\$ Jeez, just reread my comments and I'm making so many typos tonight. Good thing I'm not trying to write any code... \$\endgroup\$
    – ElPedro
    Oct 24, 2016 at 19:09
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
12
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Adám
    Oct 26, 2016 at 13:23
  • \$\begingroup\$ Yeah, Dyalog has characters that differ from GNU. Or is it something else? \$\endgroup\$
    – Adalynn
    Oct 26, 2016 at 21:56
  • \$\begingroup\$ Well, ⍸ is being added from v16, I've been unable to find a list of GNUAPL primitives. \$\endgroup\$
    – Adám
    Oct 26, 2016 at 22:59
  • \$\begingroup\$ I've got GNU APL running, it's mostly just codepoint differences. \$\endgroup\$
    – Adalynn
    Oct 26, 2016 at 23:08
  • \$\begingroup\$ From what I've noticed. \$\endgroup\$
    – Adalynn
    Oct 26, 2016 at 23:13
1
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.