تحدي كود البحث في المصفوفة

Question

إليكم تحدي (كود الجولف):خذ صفيفين من البايتات وحدد ما إذا كان الصفيف الثاني عبارة عن سلسلة فرعية من الأول.إذا كان الأمر كذلك، قم بإخراج الفهرس الذي تظهر فيه محتويات المصفوفة الثانية في الأولى.إذا لم تجد المصفوفة الثانية في المصفوفة الأولى، فقم بإخراج -1.

إدخال المثال:{ 63, 101, 245, 215, 0 } { 245, 215 }

الناتج المتوقع:2

مثال على الإدخال 2:{ 24, 55, 74, 3, 1 } { 24, 56, 74 }

الناتج المتوقع 2:-1

يحرر: أشار شخص ما إلى أن المنطقي زائد عن الحاجة، لذا كل ما يجب على وظيفتك فعله هو إرجاع int الذي يمثل فهرس القيمة أو -1 إذا لم يتم العثور عليه.

Answer 1

ج

37 حرفًا للحصول على وظائف أكثر مما هو مطلوب:تقوم بإرجاع قائمة الجميع مؤشرات المطابقة.

I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))

الاستخدام:

   NB. قم بتسمية هذه الوظيفة
   أنا =: I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))
   NB. اختبار رقم 1
   245 215 أنا 63 101 245 215 0
2
   NB. الاختبار رقم 2 - لا توجد نتائج
   24 56 74 أنا 24 55 74 3 1

   NB. الاختبار رقم 3:مباريات في مواقع متعددة
   1 1 أنا 1 1 1 2 1 1 3
0 1 4
   NB. الاختبار رقم 4:تطابقات السلسلة الفرعية الدقيقة فقط
   1 2 أنا 0 1 2 3 1 0 2 1 2 0
1 7

---

NB. list[0 to end], list[1 to end], list[2 to end], ...
<@}."0 _~i.@#

NB. Does the LHS completely match the RHS (truncated to match LHS)?
[-:#@[{.>@]

NB. boolean list of match/no match
([-:#@[{.>@])"_ 0(<@}."0 _~i.@#)

NB. indices of *true* elements
I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))

Answer 2

اللثغة الشائعة:

(defun golf-code (master-seq sub-seq)
  (search sub-seq master-seq))

Answer 3

بوستسكريبت, 149 146 170 166 167 159 حرفا (في الجزء "القيام بالعمل"):

% define data
/A [63 101 245 215 0] def
/S [245 215] def

% do the work
/d{def}def/i{ifelse}d/l S length 1 sub d/p l d[/C{dup[eq{pop -1}{dup S p
get eq{pop p 0 eq{]length}{/p p 1 sub d C}i}{p l eq{pop}if/p l d C}i}i}d
A aload pop C

% The stack now contains -1 or the position

لاحظ أن هذا العثور على آخر حدوث المصفوفة الفرعية إذا تم احتواؤها أكثر من مرة.

مراجعة التاريخ:

• يستبدل false بواسطة [[ne و true بواسطة [[eq لحفظ ثلاثة أحرف
• تمت إزالة الخلل الذي قد يسبب نتيجة سلبية خاطئة إذا كان العنصر الأخير من S يظهر مرتين في A.لسوء الحظ، يحتوي هذا الخطأ على 24 حرفًا.
• جعل إصلاح الخلل أرخص قليلاً، مما أدى إلى توفير أربعة أحرف
• اضطررت إلى إدراج مسافة مرة أخرى لأن الشرطة هي حرف قانوني في الاسم.لم يتم اكتشاف هذا الخطأ في بناء الجملة لأن حالة الاختبار لم تصل إلى هذه النقطة.
• توقفت عن إعادة العناصر المنطقية لأن OP لم يعد يتطلبها.يحفظ 8 أحرف.

النسخة الموضحة:

لسوء الحظ، أداة تمييز بناء جملة SO لا تعرف PostScript، لذا فإن إمكانية القراءة لا تزال محدودة.

/A [63 101 245 215 0] def
/S [245 215 ] def

/Slast S length 1 sub def % save the index of the last element of S,
                          % i.e. length-1
/Spos Slast def % our current position in S; this will vary
[ % put a mark on the bottom of the stack, we need this later.

/check % This function recursively removes values from the stack
       % and compares them to the values in S
{
  dup [ 
  eq
  { % we found the mark on the bottom, i.e. we have no match
    pop -1 % remove the mark and push the results
  }
  { % we're not at the mark yet
    dup % save the top value (part of the bugfix)
    S Spos get
    eq 
    {  % the top element of the stack is equal to S[Spos]
       pop % remove the saved value, we don't need it
       Spos 0
       eq 
       { % we are at the beginning of S, so the whole thing matched.
         ] length % Construct an array from the remaining values
                  % on the stack. This is the part of A before the match,
                  % so its length is equal to the position of the match.
                  % Hence we push the result and we're done.
       }
       { % we're not at the beginning of S yet, so we have to keep comparing
         /Spos Spos 1 sub def % decrease Spos
         check % recurse
       }
       ifelse
    }
    { % the top element of the stack is different from S[Spos]
      Spos Slast eq {pop} if % leave the saved top value on the stack
                             % unless we're at the end of S, because in
                             % this case, we have to compare it to the
                             % last element of S (rest of the bugfix)
      /Spos Slast def % go back to the end of S
      check % recurse
    }
    ifelse
 }
 ifelse
}
def % end of the definition of check

A aload % put the contents of A onto the stack; this will also push A again,
        % so we have to ...
pop % ...remove it again
check % And here we go!

Answer 4

C99

#include <string.h>

void find_stuff(void const * const array1, const size_t array1length, /* Length in bytes, not elements */
                void const * const array2, const size_t array2length, /* Length in bytes, not elements */
                char * bReturnBool,
                int * bReturnIndex)
{
    void * found = memmem(array1, array1length, array2, array2length);
    *bReturnBool = found != NULL;
    *bReturnIndex = *bReturnBool ? found - array1 : -1;
}

باختصار، و بعض الشيء الكثير من الفوضى:

#include <string.h>
#define f(a,b,c,d,e,f) { void * g = memmem(a, b, c, d); f = (e = !!g) ? g - a : -1; }

Answer 5

بايثون 2 و 3، 73 68 58 حرفا

مرتكز على نيخيل تشيليا'س إجابة kaiser.se'س إجابة:

>>> t=lambda l,s:''.join(map(chr,l)).find(''.join(map(chr,s)))
>>> t([63, 101, 245, 215, 0], [245, 215])
2
>>> t([24, 55, 74, 3, 1], [24, 56, 74])
-1

بايثون 3, 41 36 حرفا

شكرا جزئيا ل القاضم:

>>> t=lambda l,s:bytes(l).find(bytes(s))
>>> t([63, 101, 245, 215, 0], [245, 215])
2
>>> t([24, 55, 74, 3, 1], [24, 56, 74])
-1

هاسكل, 68 64 حرفا

ترتيب الوسيطة كما هو محدد في OP:

import List;t l s=maybe(-1)id$findIndex id$map(isPrefixOf s)$tails l

مثل زائل كما يشير، يمكننا تبديل الوسائط وتقليل الكود بمقدار أربعة أحرف:

import List;t s=maybe(-1)id.findIndex id.map(isPrefixOf s).tails

Answer 6

في بايثون:

def test(large, small):
    for i in range(len(large)):
        if large[i:i+len(small)] == small:
            return i
    return -1

ولكن بما أن الناس يريدون مقتضبًا وليس أنيقًا:

def f(l,s):
 for i in range(len(l)):
  if l[i:i+len(s)]==s:return i
 return -1

وهو 75 حرفًا، مع احتساب المسافة البيضاء.

Answer 7

روبي، باستخدام Array#pack (نص مكون من 41 حرفًا):

def bytearray_search(a,b)
  (i=b.pack('C*').index(b.pack('C*')))?i:-1
end

لغة Perl (نص مكون من 36 حرفًا، باستثناء معالجة المعلمات):

sub bytearray_search {
  ($a,$b) = @_;
  index(pack('C*',@$a),pack('C*',@$b))
}

Answer 8

أشعر أنني أغش، ولكن استخدام Perl سيفعل ما يريده OP:

sub byte_substr {
    use bytes;
    index shift,shift
}

عادة index() تعمل لغة Perl على سلاسل ذات دلالات أحرف، لكن براغما "استخدام البايتات" تجعلها تستخدم علم مقاطع البايت بدلاً من ذلك.من الصفحة الرئيسية:

عندما يكون "استخدام بايت" ساري المفعول ، يتم تجاهل الترميز مؤقتًا ، ويتم التعامل مع كل سلسلة كسلسلة من البايتات.

Answer 9

واحد آخر في بايثون:

def subarray(large, small):
    strsmall = ' '.join([str(c).zfill(3) for c in small])
    strlarge = ' '.join([str(c).zfill(3) for c in large])
    pos = strlarge.find(strsmall)
    return  ((pos>=0), pos//4)

Answer 10

روبي 1.9 (44ب)

_=->a,b{[*a.each_cons(b.size)].index(b)||-1}

p _[[63, 101, 245, 215, 0], [245, 215]]
p _[[24, 55, 74, 3, 1], [24, 56, 74]]

جوروبي (29 ب)

_=->a,b{a.e_(b.sz).dx(b)||-1}

Answer 11

بايثون:84 حرفا

def f(a,b):
 l=[a[i:i+len(b)]for i in range(len(a))]
 return b in l and l.index(b)or-1

مقدمة:84 حرفًا (يقول "لا" بدلاً من إرجاع -1):

s(X,[]).
s([H|T],[H|U]):-s(T,U).
f(X,Y,0):-s(X,Y).
f([_|T],Y,N):-f(T,Y,M),N is M+1.

Answer 12

تعريف وظيفة Python oneliner في 64 حرفًا

def f(l,s): return ''.join(map(chr,l)).find(''.join(map(chr,s)))

منذ أن تم تمريرنا صراحة مجموعة من البايتات يمكننا تحويل ذلك إلى مصفوفة البايت الأصلية في بايثون str والاستخدام str.find

Answer 13

بايثون 3 36 بايت

على أساس ستيفان 202

>>> t=lambda l,s:bytes(l).find(bytes(s))
... 
>>> t([63, 101, 245, 215, 0], [245, 215])
2
>>> t([24, 55, 74, 3, 1], [24, 56, 74])
-1

Answer 14

في بايثون:

def SearchArray(input, search):
found = -1
for i in range(0, len(input) - len(search)):
    for j in range(0, len(search)):
        if input[i+j] == search[j]:
            found = i
        else:
            found = -1
            break
if  found >= 0:
    return True, found
else:
    return False, -1

لاختبار

print SearchArray([ 63, 101, 245, 215, 0 ], [ 245, 215 ])
print SearchArray([ 24, 55, 74, 3, 1 ], [ 24, 56, 74 ])

الذي يطبع:

(True, 2)
(False, -1)

لاحظ أن هناك حلًا أقصر، ولكنه يستخدم ميزات لغة بايثون غير المحمولة حقًا.

Answer 15

شركة#:

private object[] test(byte[] a1, byte[] a2)
{
    string s1 = System.Text.Encoding.ASCII.GetString(a1);
    string s2 = System.Text.Encoding.ASCII.GetString(a2);
    int pos = s1.IndexOf(s2, StringComparison.Ordinal);
    return new object[] { (pos >= 0), pos };
}

مثال الاستخدام:

byte[] a1 = new byte[] { 24, 55, 74, 3, 1 };
byte[] a2 = new byte[] { 24, 56, 74 };
object[] result = test(a1, a2);
Console.WriteLine("{0}, {1}", result[0], result[1]); // prints "False, -1"

Answer 16

public class SubArrayMatch
{
    private bool _IsMatch;
    private int _ReturnIndex = -1;
    private List<byte> _Input;
    private List<byte> _SubArray;
    private bool _Terminate = false;
#region "Public Properties"
    public List<byte> Input {
        set { _Input = value; }
    }

    public List<byte> SubArray {
        set { _SubArray = value; }
    }

    public bool IsMatch {
        get { return _IsMatch; }
    }

    public int ReturnIndex {
        get { return _ReturnIndex; }
    }
#endregion
#region "Constructor"
    public SubArrayMatch(List<byte> parmInput, List<byte> parmSubArray)
    {
        this.Input = parmInput;
        this.SubArray = parmSubArray;
    }
#endregion
#region "Main Method"
    public void MatchSubArry()
    {
        int _MaxIndex;
        int _Index = -1;
        _MaxIndex = _Input.Count - 1;

        _IsMatch = false;

        foreach (byte itm in _Input) {
            _Index += 1;

            if (_Terminate == false) {
                if (SubMatch(_Index, _MaxIndex) == true) {
                    _ReturnIndex = _Index;
                    _IsMatch = true;
                    return;
                }
            }
            else {
                return;
            }
        }
    }

    private bool SubMatch(int BaseIndex, int MaxIndex)
    {
        int _MaxSubIndex;
        byte _cmpByte;
        int _itr = -1;

        _MaxSubIndex = _SubArray.Count - 1;
        _MaxSubIndex += 1;

        if (_MaxSubIndex > MaxIndex) {
            _Terminate = true;
            return false;
        }

        foreach (byte itm in _SubArray) {
            _itr += 1;

            _cmpByte = _Input(BaseIndex + _itr);

            if (!itm == _cmpByte) {
                return false;
            }
        }

        return true;
    }
#endregion

}

بقلم أنهار حسين ميا الذي حرره:أنهار مياه@:07/03/2009

Answer 17

بي أتش بي

في 105...

function a_m($h,$n){$m=strstr(join(",",$h),join(",",$n));return$m?(count($h)-substr_count($m,",")-1):-1;}        

أو بشكل أكثر صراحة

function array_match($haystack,$needle){
  $match = strstr (join(",",$haystack), join(",",$needle));
  return $match?(count($haystack)-substr_count($match,",")-1):-1;
}

Answer 18

جنو ج:

int memfind(const char * haystack, size_t haystack_size, const char * needle,
    size_t needle_size)
{
    const char * match = memmem(haystack, hasystack_size, needle, needle_size);
    return match ? match - haystack : -1;
}

ANSI C، بدون مكتبة:

int memfind(const char * haystack, size_t haystack_size, const char * needle,
    size_t needle_size)
{
    size_t pos = 0;
    for(; pos < haystack_size; ++pos)
    {
        size_t i = 0;
        while(pos + i < haystack_size && i < needle_size &&
            haystack[pos + i] == needle[i]) ++i;

        if(i == needle_size) return pos;
    }

    return -1;
}

Answer 19

روبي.ليس بالضبط الأقصر في العالم، ولكنه رائع لأنه امتداد لـ Array.

class Array
  def contains other=[]
    index = 0
    begin
      matched = 0
      ndx = index
      while other[matched] == self[ndx]
        return index if (matched+1) == other.length
        matched += 1
        ndx += 1
      end
    end until (index+=1) == length
    -1
  end
end

puts [ 63, 101, 245, 215, 0 ].contains [245, 215]
# 2
puts [ 24, 55, 74, 3, 1 ].contains [24, 56, 74 ]
# -1

Answer 20

C#، قوائم تسمى "a" و"b":

Enumerable.Range(-1, a.Count).Where(n => n == -1 
    || a.Skip(n).Take(b.Count).SequenceEqual(b)).Take(2).Last();

إذا كنت لا تهتم بإرجاع المثيل الأول، فيمكنك فقط القيام بما يلي:

Enumerable.Range(-1, a.Count).Last(n => n == -1 
    || a.Skip(n).Take(b.Count).SequenceEqual(b));

Answer 21

int m(byte[]a,int i,int y,byte[]b,int j,int z){return i<y?j<z?a[i]==b[j++]?m(a,++i,y,b,j,z):m(a,0,y,b,j,z):-1:j-y;}

جافا، 116 حرفًا.لديه القليل من الوظائف الإضافية التي تم طرحها.حسنًا، من الحماقة دفع شرط البداية وأطوال المصفوفة إلى المتصل.نسميها مثل:

m(byte[] substring, int substart, int sublength, byte[] bigstring, int bigstart, int biglength)

Answer 22

مثل فريدريك قام بالفعل بنشر الشفرة باستخدام طريقة التحويل STRING.إليك طريقة أخرى يمكن القيام بها باستخدام C#.

com.jwoolard ضربني لذلك، راجع للشغل.أنا أيضًا استخدمت نفس الخوارزمية التي استخدمها.كانت هذه إحدى المشكلات التي كان علينا حلها باستخدام لغة C++ في الكلية.

public static bool Contains(byte[] parent, byte[] child, out int index)
{
    index = -1;

    for (int i = 0; i < parent.Length - child.Length; i++)
    {
        for (int j = 0; j < child.Length; j++)
        {
            if (parent[i + j] == child[j])
                index = i;
            else
            {
                index = -1;
                break;
            }
        }
    }

    return (index >= 0);
}

Answer 23

اللثغة v1

(defun byte-array-subseqp (subarr arr)
  (let ((found (loop 
                  for start from 0 to (- (length arr) (length subarr))
                  when (loop 
                          for item across subarr
                          for index from start below (length arr)
                          for same = (= item (aref arr index))
                          while same
                          finally (return same))
                  do (return start))))
    (values (when found t) ; "real" boolean
            (or found -1))))

Lisp v2 (ملاحظة، subseq ينشئ نسخة

(defun byte-array-subseqp (subarr arr)
  (let* ((alength (length arr))
         (slength (length subarr))
         (found (loop 
                   for start from 0 to (- alength slength)
                   when (equalp subarr (subseq arr start (+ start slength)))
                   do (return start))))
    (values (when found t)
            (or found -1))))

Answer 24

ج#:

public static object[] isSubArray(byte[] arr1, byte[] arr2) {
  int o = arr1.TakeWhile((x, i) => !arr1.Skip(i).Take(arr2.Length).SequenceEqual(arr2)).Count();
  return new object[] { o < arr1.Length, (o < arr1.Length) ? o : -1 };
}

Answer 25

في روبي:

def subset_match(array_one, array_two)
  answer = [false, -1]
  0.upto(array_one.length - 1) do |line|
    right_hand = []
    line.upto(line + array_two.length - 1) do |inner|
      right_hand << array_one[inner]
    end
    if right_hand == array_two then answer = [true, line] end
  end
  return answer
end

مثال:IRB (MAIN): 151: 0> subet_match ([24 ، 55 ، 74 ، 3 ، 1] ، [24 ، 56 ، 74]) => [false ، -1

IRB (MAIN): 152: 0> Subet_Match ([63 ، 101 ، 245 ، 215 ، 0] ، [245 ، 215]) => [True ، 2

Answer 26

يعمل C# مع أي نوع يحتوي على عامل المساواة:

first
  .Select((index, item) => 
    first
     .Skip(index)
     .Take(second.Count())
     .SequenceEqual(second) 
    ? index : -1)
  .FirstOrDefault(i => i >= 0)
  .Select(i => i => 0 ? 
     new { Found = true, Index = i } 
    : 
     new { Found = false, Index - 1 });

Answer 27

(defun golf-code (master-seq sub-seq)
  (let ((x (search sub-seq master-seq)))
    (values (not (null x)) (or x -1))))

Answer 28

هاسكل (114 حرفًا):

import Data.List
import Data.Maybe
g a b | elem b $ subsequences a = fromJust $ elemIndex (head b) a | otherwise = -1

Answer 29

روبي، أشعر بالخجل بعد رؤية رمز لار

def contains(a1, a2)
  0.upto(a1.length-a2.length) { |i| return i if a1[i, a2.length] == a2 }
  -1
end

Answer 30

إليك إصدار C# باستخدام مقارنة السلسلة.إنه يعمل بشكل صحيح ولكنه يبدو مخترقًا بعض الشيء بالنسبة لي.

int FindSubArray(byte[] super, byte[] sub)
{
    int i = BitConverter.ToString(super).IndexOf(BitConverter.ToString(sub));
    return i < 0 ? i : i / 3;
}

// 106 characters
int F(byte[]x,byte[]y){int i=BitConverter.ToString(x)
.IndexOf(BitConverter.ToString(y));return i<0?i:i/3;}

إليك إصدارًا أطول قليلًا يُجري مقارنة حقيقية لكل عنصر من عناصر المصفوفة على حدة.

int FindSubArray(byte[] super, byte[] sub)
{
    int i, j;
    for (i = super.Length - sub.Length; i >= 0; i--)
    {
        for (j = 0; j < sub.Length && super[i + j] == sub[j]; j++);
        if (j >= sub.Length) break;
    }
    return i;
}

// 135 characters
int F(byte[]x,byte[]y){int i,j;for(i=x.Length-y.Length;i>=0;i--){for
(j=0;j<y.Length&&x[i+j]==y[j];j++);if(j>=y.Length)break;}return i;}