Tableau Recherche défi de code

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

Question

Voici mon (golf code) défi: Prenez deux tableaux d'octets et déterminer si le second tableau est une sous-chaîne de la première. Si elle est sortie l'indice auquel apparaît le contenu du second tableau dans la première. Si vous ne trouvez pas le deuxième tableau dans la première, puis la sortie -1.

Exemple de saisie {63, 101, 245, 215, 0} {245, 215}

Sortie prévue: 2

Exemple de saisie 2: {24, 55, 74, 3, 1} {24, 56, 74}

Sortie 2 attendu: -1

Modifier Quelqu'un a fait remarquer que le bool est redondant, donc toute votre fonction doit faire est de retourner un int représentant l'indice de la valeur ou -1 si elle est introuvable

.
Était-ce utile?

La solution

J

37 caractères pour encore plus de fonctionnalités que demandé:. Elle retourne une liste de tous indices correspondant 

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

Utilisation: 

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

Autres conseils

Common Lisp: 

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

PostScript, 149 146 170 166 167 159 caractères (dans la partie "faire le travail"): 

% 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

Notez que ce trouve le dernier occurance du sous-tableau si elle est contenue plus d'une fois.

Historique des versions:

  • Remplacer par false et [[ne par true pour sauver trois [[eq caractères
  • Suppression d'un bug qui pouvait provoquer un faux négatif si le dernier élément de apparaît deux fois dans S A. Malheureusement, cette bugfix a 24 caractères.
  • a fait le bugfix un peu moins cher, quatre caractères sauver
  • Nous avons dû insérer à nouveau un espace parce qu'un tableau de bord est un caractère juridique dans un nom. Cette erreur de syntaxe n'a pas été pris parce que le cas de test n'a pas atteint ce point.
  • Stopped retour les bools que l'OP ne les oblige pas plus. Enregistre 8 caractères.

Expliqué Version:

Malheureusement, la syntaxe surligneur SO ne sait pas si la lisibilité PostScript est encore limitée. 

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

En raccourci, et un peu un 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 caractères

D'après de Nikhil Chelliah réponse kaiser .se est répondre : 

>>> 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 caractères

Merci en partie à 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 caractères

Afin d'argument comme spécifié par l'OP: 

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

Comme le souligne ephemient sur, nous pouvons changer les arguments et réduire le code de quatre caractères: 

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

En Python: 

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

Mais puisque les gens veulent laconiques, pas élégant: 

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

Ce qui est de 75 caractères, en comptant les espaces.

Ruby, en utilisant tableau pack # (41 caractères corps): 

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

(corps 36 caractères, ce qui exclut la gestion des paramètres) Perl: 

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

Je sens que je triche, mais en utilisant Perl cela faire ce que l'OP veut: 

sub byte_substr {
    use bytes;
    index shift,shift
}

Normalement, dans les travaux Perl index() sur les chaînes de caractères avec la sémantique, mais le « use bytes » pragma fait utiliser segmantics octet à la place. De la page de manuel:

  

« octets d'utilisation » est en          effet, l'encodage est ignoré temporairement, et chaque chaîne est traitée          comme une série d'octets.

Un autre en 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 caractères 

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 caractères (dit "non" au lieu de retourner -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 définition de fonction en 64 caractères 

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

Puisque nous sommes explicitement passés un tableau d'octets nous pouvons transformer ce à tableau d'octets natif Python et utiliser str str.find

python3 36 octets

basé sur 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

En 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

Pour tester 

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

Ce qui imprime: 

(True, 2)
(False, -1)

Remarque il y a une solution plus courte, mais il utilise des fonctionnalités de langage python qui ne sont pas vraiment portable.

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

Exemple d'utilisation: 

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

}

Par Anhar Hussain Miah « Sous la direction de: 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;}

ou plus explicitement, 

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, sans bibliothèque: 

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

Ruby . Pas exactement le plus court dans le monde, mais cool car il est une extension 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 #, listes dites "a" et "b": 

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

Si vous ne vous pouvez simplement ne se soucient pas de retourner la première instance,: 

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 caractères. A un peu de fonctionnalités supplémentaires jeté. OK, il est donc une bidouille pour pousser condition de démarrage et le réseau des longueurs dans l'appelant. Appelez cela comme: 

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

Comme on l'a déjà affiché le code Fredrik en utilisant la voie de conversion STRING. Voici une autre façon, il pourrait être fait en utilisant C #.

jwoolard me devança, btw. Moi aussi, je l'ai utilisé le même algorithme que lui. Ce fut l'un des problèmes que nous avons dû résoudre en C ++, au collège. 

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 crée une copie 

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

Dans 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

Exemple: irb (main): 151: 0> subset_match ([24, 55, 74, 3, 1], [24, 56, 74]) => [Faux, -1]

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

C #, fonctionne avec tout type qui a opérateur d'égalité: 

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 caractères): 

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

Ruby, je me sens honte après avoir vu le code de Lar 

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

Voici une version C # en utilisant la comparaison de chaînes. Il fonctionne correctement, mais se sent un peu hacky pour moi. 

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

Voici une version légèrement plus longue qui effectue une véritable comparaison de chaque élément de tableau individuel. 

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;}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top