配列検索コードチャレンジ

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

質問

これが私の（コードゴルフの）課題です。2 つのバイト配列を取得し、2 番目の配列が最初の配列の部分文字列であるかどうかを判断します。存在する場合、2 番目の配列の内容が最初の配列に現れるインデックスを出力します。最初の配列で 2 番目の配列が見つからない場合は、-1 を出力します。

入力例:{ 63, 101, 245, 215, 0 } { 245, 215 }

期待される出力:2

入力例 2:{ 24、55、74、3、1 } { 24、56、74 }

期待される出力 2:-1

編集： bool は冗長であると誰かが指摘しました。そのため、関数が行う必要があるのは、値のインデックスを表す int を返すか、見つからない場合は -1 を返すことだけです。

役に立ちましたか？

解決

J の

要求されたよりもさらに多くの機能のための

37の文字：。それはのすべてのの一致指数

のリストを返します。 
I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))

使用方法：

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

他のヒント

のCommon Lispます：

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

追記、 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 3文字を保存するには
  • の最後の要素が存在しない場合に偽陰性を引き起こす可能性があるバグを削除しました。 S に二度登場する A. 。残念ながら、このバグ修正には 24 文字が含まれています。
  • バグ修正を少し安くし、4 文字を節約しました
  • ダッシュは名前に使用できる文字であるため、スペースを再度挿入する必要がありました。テスト ケースがこの時点に達していないため、この構文エラーは検出されませんでした。
  • 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!

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

速記で、及び<ストライキ>ビット LOTのメシエ

#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 58文字

<ストライキ> 68

<ストライキ> ニキルChelliahするの<のhref = "https://stackoverflow.comに基づいて、 /質問/ 1078770 /配列探索・コード・チャレンジ/ 1078794＃1078794" >答えの カイザー.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

のPython 3、36文字

<ストライキ> 41

のおかげ一部に 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

ハスケル、64文字

<ストライキ> 68

OPで指定された引数の順序ます：

import List;t l s=maybe(-1)id$findIndex id$map(isPrefixOf s)$tails l
ephemientするが指摘するように、

、我々は4つの文字で引数を切り替えて、コードを減らすことができます：

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

Pythonでます：

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文字ですどちらます。

ルビー、使用アレイ＃パック（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))
}

私は浮気が、OPが何を望んだろうPerlの本を使用していていることを感じます：

sub byte_substr {
    use bytes;
    index shift,shift
}

Perlで通常のindex()はキャラクタ・セマンティクスを持つ文字列で動作しますが、プラグマが、それは代わりに、バイトsegmanticsを使用します「の使用は、バイト」。 manページから：

  

「使用バイト」である場合には          効果は、符号化が一時的に無視され、各文字列が処理され          一連のバイトとしてます。

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)

ルビー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}

パイソン: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.

64文字で関数定義oneliner Pythonの

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

私たちは、明示的にのバイトの配列の我々は、Pythonのネイティブバイト配列strにそれを変換することができますし、

str.findを使用渡されますので、

ののpython3 36バイトの

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

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

をテストするには、

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

どのプリントます：

(True, 2)
(False, -1)

注短く解決策がありますが、それは本当に移植性がありませんPython言語の機能を使用します。

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

使用例：

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

}

AnharフセインMiahことで 「編著：Anhar.Miah @：2009年3月7日

PHP

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

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ライブラリなします：

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

ルビー. 。厳密には世界最短ではありませんが、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＃の、 "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));
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の文字。それは、発信者に開始条件と配列の長さをプッシュするその場しのぎですので、余分な機能の少しはOK。でスローしました。好きなことを呼び出します：

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

フレドリックのようにはすでに文字列変換方法を使用してコードを掲載しています。ここでは、C＃を使用して行うことができる別の方法です。

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

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はコピーを作成します。

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

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

例： IRB（メイン）：151：0> subset_match（[24、55、74、3、1]、[24、56、74]） => [FALSE、-1]

IRB（メイン）：152：0> subset_match（[63、101、245、215、0]、[245、215]） => trueを、2

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

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

のHaskell（114文字）

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

Rubyは、私はラールのコードを見て恥ずかしい

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

ここで文字列比較を使用して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;}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top