40
\$\begingroup\$

Given a rectangular haystack of size at least 2x2 composed of all the same printable ASCII characters, output the location (counting from the top-left) of the needle which is a different character.

For example, if the following haystack is input:

#####
###N#
#####
#####

The output should be 3,1 when zero-indexed (what I'll be using in this challenge) or 4,2 when one-indexed.

The haystack can be composed of any printable ASCII character:

^^^
^^^
^N^
^^^
^^^
^^^

output: 1,2

and the needle will be any other printable ASCII character:

jjjjjj
j@jjjj
jjjjjj

output 1,1

It's also possible to have a needle in the corner:

Z8
88

output 0,0

88
8Z

output 1,1

or to have the needle at the edge:

>>>>>>>>>>
>>>>>>>>>:
>>>>>>>>>>

output 9,1

Rules and Clarifications

  • Input and output can be given by any convenient method. This means you can take input as a list of list of characters, as a single string, etc.
  • You can print the result to STDOUT or return it as a function result. Please state in your submission what order the output is in (i.e., horizontal then vertical, as used in the challenge, or vice versa).
  • Either a full program or a function are acceptable.
  • You do not get to pick which characters to use. That's the challenge.
  • The haystack is guaranteed to be at least 2x2 in size, so it's unambiguous which is the needle and which is the hay.
  • There is only ever one needle in the input, and it's only ever one character in size.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
16
  • \$\begingroup\$ Suggested test case: 88\n8Z (with any two characters of course). \$\endgroup\$ Feb 1 '19 at 14:24
  • \$\begingroup\$ Can we take input as a multi-dimensional array? i.e. [ ['#','#','#','#','#'], ['#','#','#','N','#'], ['#','#','#','#','#'], ['#','#','#','#','#'] ]; \$\endgroup\$
    – 640KB
    Feb 1 '19 at 14:39
  • 2
    \$\begingroup\$ @gwaugh Like a list of list of characters? Yes, that's fine (and explicitly called out as OK). \$\endgroup\$ Feb 1 '19 at 14:40
  • 3
    \$\begingroup\$ Can we take input as a pair of a string without newlines and the width (or height) of the haystack? i.e. ("########N###########", 5) \$\endgroup\$ Feb 1 '19 at 15:17
  • 3
    \$\begingroup\$ @someone Yes, though it doesn't have a real quorum, I feel that should be allowed. \$\endgroup\$ Feb 1 '19 at 15:32

43 Answers 43

1
2
0
\$\begingroup\$

Röda, 81 bytes

f a{i=indexOf;l=i("
",a)+1;chars a|sort|count|[[_2,_1]]|min|i _[1],a|[_%l,_1//l]}

Try it online!

Takes input as a string containing newline-terminated lines. Returns a stream containing 0-indexed horizontal and vertical indexes.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -n0, 77 bytes

$t=(@b=sort/./g)[0]eq$b[1]?pop@b:$b[0];++$y&/\Q$t/g&&say"$y,",pos for /.+$/mg

Try it online!

Output is row,column starting from the top left, 1-indexed

\$\endgroup\$
0
\$\begingroup\$

Haskell, 64 bytes

f s=[(r,c)|c<-[0..],r<-[0..length s-1],any(notElem$s!!r!!c)s]!!0

Try it online! f takes a list of lines and returns zero-indexed (row,column).

Works by iterating through the columns and rows and looking for a character which does not appear on all rows.

\$\endgroup\$
0
\$\begingroup\$

C# .NET, 133 112 111 bytes

m=>{var c=m[0][0];c=m[1][0]!=c?m[1][1]:c;for(int i=0,j;;i++)for(j=m[i].Count;j-->0;)if(m[i][j]!=c)return(i,j);}

-1 byte thanks to @EmbodimentOfIgnorance.

Port of my Java answer, but with a List<List<char>> input and int-tuple output, instead of char[][] input and string output.

Try it online.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can't you save two bytes by turning you char[][] into a List<List<char>>? Since List<T>.Count is shorter than Array.Length \$\endgroup\$
    – Gymhgy
    Feb 2 '19 at 18:47
  • \$\begingroup\$ @EmbodimentofIgnorance Thanks! :) \$\endgroup\$ Feb 2 '19 at 20:42
0
\$\begingroup\$

APL+WIN, 39 bytes

Index origin =1. Prompts for character matrix as a string input followed by row width. Outputs row by column index position.

(,(⍳i÷n)∘.,⍳n←⎕)[((1=+/m∘.≡m)/⍳i←⍴m←⎕)]

Try it online! Courtesy of Dyalog Classic

Explanation:

⍳i←⍴m←⎕ Prompt for string and create a vector of indices from 1 to length string.

(1=+/m∘.≡m) Boolean vector identifying position of unique character in string.

(...)/⍳i Use Boolean to select index position of unique character.

,⍳n←⎕ Prompt for row width of character matrix and create a vector of indices.

,(⍳i÷n)∘., Create a nested vector of row by column indices of character matrix.

(...)[...] Select row by column index position of unique character.
\$\endgroup\$
0
\$\begingroup\$

Kotlin, 142 bytes

The result is zero based [vertical,horizontal].

{d:List<String>->val h=if(d[0][0]!=d[0][1])d[1][0]
else d[0][0]
var a=""
for(r in d.indices)for(c in d[r].indices)if(h!=d[r][c])a="[$r,$c]"
a}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python3

Well I've never tried to do code golf before and I really can't compete with some of these really good solutions, so I've prepared a long-form answer just to demonstrate how I would solve this problem. This function takes a 2-D list of characters of any size as its input.

(edited to shorten the function up as much as I could)

def f(i):
    a = None
    b = 0
    c = None
    d = 0
    h = len(i)
    for y in range(h):
        for x in range(len(i[y])):
            if a == None:
                a = i[y][x]
            elif a != None:
                if i[y][x] != a:
                    c = i[y][x]
            if i[y][x] == a:
                b += 1
            elif i[y][x] == c:
                d += 1
    if b == 1:
        n = a
    elif d == 1:
        n = c
    for y in range(h):
        for x in range(len(i[y])):
            if i[y][x] == n:
                return (x, y)

Here is a longer version that demonstrates the example input. If you run this script it will show you the 2-D array and the needle (randomly generated every time) as well as solve it with the find_needle() function.

# Code golf! Needle in a haystack challenge
# sgibber2018 (my email handle)
"""
Notes: I can't really compete with what's already been done but I'm doing
       it just to do it. 
"""

import random

input_height = 10
input_width = 10
example_input = [["#" for x in range(input_width)] \
    for y in range(input_height)]
needle_spot_y = random.randrange(input_height)
needle_spot_x = random.randrange(input_width)
example_input[needle_spot_y][needle_spot_x] = "!"

for y in range(input_height):
    print(example_input[y])

# and now for the algorithm itself:
def find_needle(example_input):
    # declare two variables to count different char types
    c1 = None
    c1_count = 0
    c2 = None
    c2_count = 0
    # iterate through the whole list
    height = len(example_input)
    for y in range(height):
        for x in range(len(example_input[y])):
            # assign c1 or c2 accordingly
            if c1 == None:
                c1 = example_input[y][x]
            elif c1 != None:
                if example_input[y][x] != c1:
                    c2 = example_input[y][x]
            # count the symbols based on whether or not they match
            if example_input[y][x] == c1:
                c1_count += 1
            elif example_input[y][x] == c2:
                c2_count += 1
    # Find the value with just one increment
    if c1_count == 1:
        needle = c1
    elif c2_count == 1:
        needle = c2
    # go back through the list and find the needle and get it's pos
    for y in range(height):
        for x in range(len(example_input[y])):
            if example_input[y][x] == needle:
                return (x, y)

print(find_needle(example_input))

The function find_needle() takes a 2-D list and returns the coordinates of the character that only has one count. I could probably shorten this up a little but I don't think I can compete with the existing Python3 answer which is mighty impressive. How do you calculate the size of your answers?

\$\endgroup\$
7
  • \$\begingroup\$ Done! I'm wary of violating Python's whitespace rules too much but I shortened all the variables. Thanks for the heads up. How do I calculate the bytes? \$\endgroup\$ Feb 4 '19 at 2:31
  • 2
    \$\begingroup\$ You can use a number of tools. Here is an environment you can use that counts bytes, if you hit the link button at the top it will even generate an form filled answer for you. Also some tips: most operators =, == etc. don't require space on each side of them, so you can remove that easily, If you want to reply to a user in comments you can use @ <user-name> other wise they are unlikely to see it. Anyway, hope you have fun here! \$\endgroup\$
    – Grain Ghost
    Feb 4 '19 at 2:41
  • 2
    \$\begingroup\$ I'd also suggest looking at the Tips for golfing in Python page for some general shortcuts you can take \$\endgroup\$
    – Jo King
    Feb 4 '19 at 2:47
  • \$\begingroup\$ Welcome to PPCG! I recommend going through the tips as per Jo King's suggestion. RE: "I'm wary of violating Python's whitespace rules" - for code-golf you need to violate whatever saves bytes and still works; however for this challenge we can make do with no newlines at all - the only white-space abuse of the port of my Python 2 answer to Python 3 (at 62 bytes) is to miss the space between ) and for [twice] and between in and ( - and, in fact, no "Python rules" are broken only "style guidelines" (although I don't actually see this one in PEP-8). \$\endgroup\$ Feb 4 '19 at 18:16
  • \$\begingroup\$ The current code (using tabs or single spaces in place of four spaces) is 387 bytes. Removing trivial white-space is 347 bytes. \$\endgroup\$ Feb 4 '19 at 19:04
0
\$\begingroup\$

C (gcc), 81 bytes

Takes input as three pointers: one to the array, and two to the dimensions. Returns by modifying the dimensions to be the coordinates of the needle.

i;f(char*a,int*w,int*h){for(i=0;*a==a[i];i++);i=i-1?i:*a==a[2];*h=i/ *w,*w=i%*w;}

Try it online!

Degolf

i;f(char*a,int*w,int*h)
{
  for(i=0;*a==a[i];i++); // Count the number of elements equal to
                         // the one at (0,0)
  i=i-1?i:*a==a[2];  // Special case i==1, because it is 
          // ambiguous whether the needle is at 0 or 1 there.
  *h=i/ *w,*w=i%*w; // Modify pointers to indicate coordinates.
  // the space between i/ and *w is required, as /* starts a comment
}
\$\endgroup\$
1
  • \$\begingroup\$ Suggest i=*a;i=strspn(a,&i) instead of for(i=0;*a==a[i];i++) \$\endgroup\$
    – ceilingcat
    Feb 24 '19 at 3:05
0
\$\begingroup\$

Python 2, 63 bytes

lambda s,w:divmod(s.find({s.count(c):c for c in s}[1]),w)[::-1]

Try it online!

Expects a string with no newlines and the width of the haystack as arguments.

Explanation:

                         # get a dictionary of (number of occurrences : character)
                         {s.count(c):c for c in s}
                         # only one character will have one occurrence, so get that character
                         .........................[1]
                  # get the 0-indexed index of the needle character
                  s.find(............................)
           # flat_index / width will give us how many rows "down" the needle is (the y-value)
           # the remainder will give us how many columns "over" the needle is (the x-value)
           # so take the divmod and reverse the returned values to get (x,y)
           divmod(....................................,w)[::-1]
# anonymous function, takes haystack string with no newlines and haystack width
lambda s,w:
\$\endgroup\$
0
\$\begingroup\$

C# (.NET Core), 135 111 bytes

S=>{for(int x=0,y;;x++)try{for(y=0;;y++)if(S[x][y]!=(S[0][0]==S[0][1]?S[0][0]:S[1][0]))return y+","+x;}catch{}}

Try it online! (111 bytes)
Try it online! (135 bytes)

New one:

for (int x = 0, y; ; x++)
    try
    {
        for (y = 0; ; y++)
            if (S[x][y] != (S[0][0] == S[0][1] ? S[0][0] : S[1][0]))
                return y + "," + x;
    }
    catch { }

Previous one:

int i = 0, y;
var r = "";
for (; i < S.Length; i++)
    for (y = 0; y < S[i].Length; y++)
        r = S[i][y] != (S[0][0] == S[0][1] ? S[0][0] : S[1][0]) ? i + "," + y : r;
return r;
\$\endgroup\$
0
\$\begingroup\$

C (VC++) Visual Studio 2017, 538bytes

well there can be a couple of Bytes be stripped of if the haystack and needle string is Input via command line Parameters but i can not get it to work proberly then so the haystack and needle string is hard coded in the source (ugly….. 😢) takes 50bytes

Maybe anyone wants to improve on that

anyway the Code i came up with is

#include"stdafx.h"
#define r v[1][i]
#define i(x,y) if(x==y)
void main(){const char*v[]={"haystack.exe","#####\n##+##\0" };int i=0,z=0,s=0,c=r,f=c,a=-1,h=0;do{c=r;i(c,f)a++;i(a,1)h=c;if(h&&c!=h&&c!=10)break;i(c,10){z++;s=0;}}while(s++,i++,c);printf("%d,%d",s-1,z);}

the ungolfed variant is

#include "stdafx.h"

int main(/*int argc, const char * argv[]*/)
{
    const char * argv[] = {"haystack.exe","#####\n##+##\0" };
    int i = 0,row = 0, col = 0;
    char character = argv[1][i];
    char firstChar = character;
    int howMany = -1;
    char hay = '\0';
    do
    {
        char character = argv[1][i];
        if (character == firstChar)
        {
            howMany++;
        }
        if (howMany ==1)
        {
            hay = character;
        }
        if ((hay != '\0') && (character != hay)&&(character!='\n'))
        {
            break;
        }
        if (character == '\n')
        {
            row++;
            col = 0;
        }
        col++;
        i++;
    } while (character != '\0');
    printf("%d,%d", col-1, row);
    while (1);
    return 0;
}

i dont expect this to be explained

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG! I'm not familiar enough with C++ to assist, but I know there's a tips page you can check out. \$\endgroup\$ Feb 19 '19 at 13:33
0
\$\begingroup\$

Befunge-98 (PyFunge), 62 bytes

~:04p~-k#v>~:a-!2j6$_04g-!..@
-#v_$$1+0>  >~:a
.;>04g-#;_1+^@.

Try it online!

Output is: column row

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 9 bytesSBCS

Anonymous tacit prefix function. In a sense, this is actually a kind of poly-glot, as it takes as argument either a character matrix or a list of strings, with the code meaning something else in each case. Always returns [row,column] in which ever index origin is currently active. (APL lets you choose.)

⍸↑=∊~∘∊∩/

Try it online!

If the argument is a matrix, the function works like this:

∩/ intersection reduction of each row. Since there will be at least one all-hay row, this gives us at least one hay character. And since every row has at least one hay character, the intersection will always empty out the row that has the needle character.

ϵnlist (flatten) this, giving us one or more hay characters

 then…

~ remove all such characters from…

 the ϵnlisted (flattened) argument, leaving just the needle

↑= Boolean matrix indicating where the matrix equals the needle

the indices where true

If the argument is a list of strings, the function works like this:

∩/ intersection reduction of the strings. Since only one string will have a needle, and all strings have hay, this will give us one or more hay characters without the needle character.

ϵnlist (flatten) this, giving us the one or more hay characters

 then…

~ remove all such characters from…

 the ϵnlisted (flattened) argument, leaving just the needle

↑= Boolean matrix indicating where the matrix constructed by merging the strings equals the needle

the indices where true

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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