Array Suche Code Herausforderung

StackOverflow https://stackoverflow.com/questions/1078770

Frage

Hier ist meine (Code Golf) Herausforderung: Nehmen zwei Arrays von Bytes, und bestimmen, ob das zweiten Array ein Teil der ersten ist. Wenn es ist, Ausgang, an dem der Index der Inhalt des zweiten Feldes in dem ersten erscheinen. Wenn Sie nicht über die zweite Anordnung in der ersten, dann Ausgang -1 finden.

Beispiel Eingabe: {63, 101, 245, 215, 0} {245, 215}

Erwartete Ausgabe: 2

Beispiel Eingang 2: {24, 55, 74, 3, 1} {24, 56, 74}

Erwarteter Ausgang 2: -1

Edit: Jemand hat darauf hingewiesen, dass der Boolesche redundant ist, so dass alle Ihre Funktion zu tun hat, ist ein int zurückgeben den Index des Wertes darstellt, oder -1, wenn nicht gefunden

.
War es hilfreich?

Lösung

J

37 Zeichen für noch mehr Funktionalität als angefordert. Es gibt eine Liste von alle passende Indizes 

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

Verbrauch: 

   NB. Give this function a name
   i =: I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))
   NB. Test #1
   245 215 i 63 101 245 215 0
2
   NB. Test #2 - no results
   24 56 74 i 24 55 74 3 1

   NB. Test #3: matches in multiple locations
   1 1 i 1 1 1 2 1 1 3
0 1 4
   NB. Test #4: only exact substring matches
   1 2 i 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.@#))

Andere Tipps

Common Lisp: 

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

Postscript, 149 146 170 166 167 159 Zeichen (in dem "die Arbeit" Teil): 

% 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
Hinweis

, dass dies findet die letzte Vorkommen des Sub-Array, wenn es enthalten ist mehr als einmal.

Versionsgeschichte:

  • Ersetzen false durch [[ne und true von [[eq drei Zeichen speichern
  • einen Fehler entfernt, die ein falsch negativ, wenn das letzte Element von S erscheint zweimal in A verursachen könnten. Leider ist diese Bugfix hat 24 Zeichen.
  • Aus der Bugfix ein wenig billiger und spart vier Zeichen
  • Sie hat einen Raum wieder einzuführen, da ein Strich ein Rechtscharakter in einem Namen ist. Diese Syntaxfehler wurden nicht gefangen, weil der Testfall hat diesen Punkt nicht erreichen.
  • Gestoppt die bools Rückkehr als das OP sie nicht mehr benötigen. Speichert 8 Zeichen.

Erklärung der Version:

Leider ist der SO Syntax-Highlighter nicht Postscript kennt so die Lesbarkeit noch begrenzt ist. 

/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!

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

In Kurzschrift und etwas a LOT messier: 

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

Python 2 & 3, 73 68 58 Zeichen

Basierend auf Nikhil Chelliah 's Antwort kaiser .se 's beantworten : 

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

Python 3, 41 36 Zeichen

Vielen Dank im Rahmen gnibbler : 

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

Haskell, 68 64 Zeichen

Das Argument, um so durch die OP angegeben: 

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

Wie ephemient weist darauf hin, können wir die Argumente wechseln und den Code von vier Zeichen reduzieren: 

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

In Python: 

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

Da aber die Leute wollen kurz und bündig, nicht elegant: 

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

Welche ist 75 Zeichen, Leerzeichen zu zählen.

Ruby mit Array # Packung (41 Zeichen Körper): 

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

Perl (36 Zeichen Körper, ohne Parameter handling): 

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

Ich fühle, dass ich zu betrügen, aber mit Perl dies tun würde, was der OP will: 

sub byte_substr {
    use bytes;
    index shift,shift
}

Normalerweise index() in Perl arbeitet auf Strings mit Charakter Semantik, aber die „Verwendung Bytes“ Pragma es Byte segmantics verwenden stattdessen macht. Aus der Manpage:

  

Wenn "Verwendung Bytes" ist in          Tatsächlich wird die Codierung vorübergehend ignoriert wird, und jede Zeichenfolge behandelt wird          als eine Reihe von Bytes.

Ein weiterer in Python: 

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)

Ruby 1.9 (44B) 

_=->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]]

goruby (29B) 

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

Python : 84 Zeichen 

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

Prolog : 84 Zeichen ( "nein" sagt statt Rückkehr -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.

Python oneliner Funktionsdefinition in 64 Zeichen 

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

Da wir explizit übergeben werden ein Array von Bytes wir das Python native Byte-Array str verwandeln kann und verwenden str.find

Python3 36 Bytes

basierend auf Stephan202 

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

In Python: 

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

Um zu testen 

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

Welche druckt: 

(True, 2)
(False, -1)

Hinweis gibt es eine kürzere Lösung, aber es nutzt Funktionen Python-Sprache, die nicht wirklich tragbar ist.

In C #: 

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

Anwendungsbeispiel: 

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"

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

}

Mit dem Anhar Hussain Miah ‚Herausgegeben von: Anhar.Miah @: 03.07.2009

PHP

105 ... 

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

oder mehr explizit, 

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

GNU C: 

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, ohne Bibliothek: 

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

Rubin . Nicht gerade die kürzesten in der Welt, aber kühl, da es um eine Erweiterung 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

C #, Listen namens "a" und "b": 

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

Wenn Sie nicht über die Rückkehr der ersten Instanz ist es egal, Sie können einfach tun: 

Enumerable.Range(-1, a.Count).Last(n => n == -1 
    || a.Skip(n).Take(b.Count).SequenceEqual(b));
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;}

Java, 116 Zeichen. Hat ein wenig zusätzliche Funktionalität in geworfen. OK, so ist es eine Flickschusterei Startbedingung zu schieben und Array Längen in den Anrufer. Nennen Sie es mögen: 

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

Wie Fredrik hat geschrieben bereits den Code der STRING Umwandlung Art und Weise verwendet wird. Hier ist ein weiterer Weg, um es mit C # getan werden könnte.

jwoolard schlägt mich zu ihm, btw. Ich habe zu dem gleichen Algorithmus wie er verwendet. Dies war eines der Probleme, die wir hatten mit C ++, in der Schule zu lösen. 

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

Lisp 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 (NB, SUBSEQ erstellt eine Kopie 

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

C #: 

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

In Ruby: 

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

Beispiel: IRB (Haupt): 151: 0> subset_match ([24, 55, 74, 3, 1], [24, 56, 74]) => [Falsch, -1]

IRB (Haupt): 152: 0> subset_match ([63, 101, 245, 215, 0], [245, 215]) => [True, 2]

C #, arbeitet mit jeder Art, die Gleichheits-Operator hat: 

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

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

Haskell (114 Zeichen): 

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

Rubin, ich fühle mich beschämt nach Lar Code zu sehen 

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

Hier ist eine C # Version mit String-Vergleich. Es funktioniert richtig, aber fühlt sich ein bisschen hacky zu mir. 

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

Hier ist eine etwas längere Version, die einen echten Vergleich jeden einzelnen Array-Elements führt. 

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;}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top