Znajdź igłę binarną w dziesiętnym stogu siana


41

Wyzwanie

Dostałeś:

  • niepusta, nieposortowana lista h dodatnich liczb całkowitych (stóg siana)
  • dodatnia liczba całkowita n (igła)

Twoim zadaniem jest zwrócenie listy wszystkich unikatowych konkatenacji dziesiętnych permutacji h, których reprezentacja binarna zawiera reprezentację binarną n .

Przykłady

  1. h = [1, 2, 3]
    n = 65

    przykład

    Jest tylko jedna pasująca konkatenacja, więc oczekiwany wynik to [321].

  2. h = [1, 2, 3]
    n = 7

    Tym razem istnieją trzy konkatenacje, które zawierają wzorzec binarny 111 . Oczekiwany wynik to [123, 231, 312].

  3. h = [12, 3]
    n = 7

    Dostępne są tylko dwie kombinacje i obie są zgodne. Oczekiwany wynik to [123, 312].

  4. h = [1, 2, 2]
    n = 15

    Jedyną zgodną konkatenacją jest 122 ( 1111010 w formacie binarnym, która zawiera 1111 ), więc oczekiwany wynik to [122]. Należy zauważyć, że dwie permutacje faktycznie prowadzić do 122 , ale są nie pozwolił na wyjście [122, 122].

Wyjaśnienia i zasady

  • Możesz wziąć igłę jako liczbę całkowitą ( 65), ciąg reprezentujący wartość dziesiętną ( "65") lub ciąg reprezentujący wartość binarną ( "1000001").
  • Możesz wziąć stóg siana jako natywną tablicę / obiekt / zestaw liczb całkowitych ( [11,12,13]), natywną tablicę / obiekt / zestaw ciągów reprezentujących wartości dziesiętne ( ["11","12","13"]) lub rozdzielany ciąg wartości dziesiętnych ( "11 12 13"lub "11,12,13"). Możesz również wybrać wariant, korzystając z tablic cyfr (np [[1,1],[1,2],[1,3]].).
  • Dane wyjściowe muszą być zgodne z jednym z formatów opisanych powyżej dla stogu siana, ale niekoniecznie tym samym.
  • Nie powinieneś obsługiwać stogów siana, których najwyższa konkatenacja dziesiętna jest większa niż najwyższa reprezentowana liczba całkowita bez znaku w twoim języku.
  • Poza tym twój kod powinien teoretycznie obsługiwać wszelkie dane wejściowe - zakładając, że ma wystarczająco dużo czasu i pamięci.
  • To jest SPARTA! , więc wygrywa najkrótsza odpowiedź w bajtach!

Przypadki testowe

Haystack             | Needle   | Output
---------------------+----------+-----------------------------------
[ 1, 2, 3 ]          | 65       | [ 321 ]
[ 1, 2, 3 ]          | 7        | [ 123, 231, 312 ]
[ 12, 3 ]            | 7        | [ 123, 312 ]
[ 1, 2, 2 ]          | 15       | [ 122 ]
[ 1, 2 ]             | 7        | []
[ 12, 34, 56 ]       | 21       | [ 125634, 341256, 345612, 563412 ]
[ 1, 2, 3, 4, 5 ]    | 511      | [ 53241 ]
[ 1, 3, 5, 7, 9 ]    | 593      | [ 37519, 51793, 75913, 75931 ]
[ 11, 12, 13, 14 ]   | 12141311 | [ 12141311 ]
[ 1, 2, 1, 2, 1, 2 ] | 1015     | [ 221112 ]

1
Wyniki mojego rozwiązania są podobne set([(1, 2, 2)]). Czy jest ważny, czy powinienem się go pozbyć set?
Dead Possum

@DeadPossum Tak, jest ważny.
Arnauld

Czy wejście stogu siana może być pojedynczym ciągiem („123”)? W niektórych językach ciąg znaków jest taki sam, jak tablica znaków, więc myślę, że miałoby to sens
Luis Mendo

Nie @LuisMendo Może dlatego, ["12","3"]i ["1","23"]są dwa różne stogi.
Arnauld

@Arnauld Ah, myślałem, że to cyfry. Dzięki
Luis Mendo

Odpowiedzi:


17

05AB1E , 10 8 bajtów

Bierze igłę w systemie binarnym, aby zaoszczędzić 1 bajt.

-2 bajty dzięki Emignie

œJÙʒbŒIå

Wypróbuj online!

œJÙʒbŒIå   Arguments: a, n
œJÙ        Get all unique permutations of a
   ʒ       Filter: Keep if following code returns true
    b      Convert to binary
     Π    Get all substrings
      Iå   Check if substrings contain n
           Implicit output of filtered list

1
- J'ʒbŒIå powinien również działać.
Emigna

@Emigna Dzięki, że oszczędza 2 bajty :)
kalsowerus

11

Python 2, 90 bajtów

-3 bajty dzięki @ Gábor Fekete

Wypróbuj online

Pobiera jako tablicę wejściową ciągów, reprezentujących ints z siana i łańcucha, reprezentujących igłę w systemie binarnym

from itertools import*
lambda H,N:{i for i in permutations(H)if N in bin(int(''.join(i)))}

4
Pisanie {...}zamiast set(...)oszczędza 3 bajty.
Gábor Fekete

1
@ GáborFekete Zawsze zapominam, że {} jest ustawiony: D Dzięki
Dead Possum

Wierzę, że to się nie udaje H=['1'], N='0'.
user2357112 obsługuje Monikę

Och, czekaj, dane wejściowe muszą być dodatnie.
user2357112 obsługuje Monikę

10

Java 10, 320 312 305 297 292 bajtów

import java.util.*;Set s=new HashSet();l->n->{Long q=0;p(l,0);for(var x:s)if(q.toString(q.decode(x+""),2).contains(n))System.out.println(x);}void p(List l,int k){int i=k,x=l.size();for(Collections C=null;i<x;p(l,k+1),C.swap(l,k,i++))C.swap(l,i,k);if(k>x-2)s.add((l+"").replaceAll("\\D",""));}

Dane wejściowe jako lista i ciąg binarny, dane wyjściowe jako ciągi w nowych wierszach.

Wyjaśnienie:

Wypróbuj tutaj.

import java.util.*;           // Required import for Set, HashSet, List, and Collections

Set s=new HashSet();          // Class-level Set

l->n->{                       // Method (1) with List and String parameters and no return-type
  Long q=0;                   //  Number-object is required for two static method-calls below
  p(l,0);                     //  Determine all permutations of given list and put it in the Set
  for(var x:s)                //  Loop over these permutations
    if(q.toString(q.decode(x+""),2)
                              //   If the binary String of the current permutation
        .contains(n))         //   contains the binary String of the input integer
      System.out.println(x);} //    Print this permutation

void p(List l,int k){         // Method (2) with List and integer parameters and no return-type
  int i=k,x=l.size();         //  Two temp integers
  for(Collections C;          //  Collections-object is required for two static method-calls below
      i<x                     //  Loop `i` in the range [`k`, list-size)
      ;                       //    After every iteration:
       p(l,k+1),              //     Do a recursive-call to this method with `k+1`
       Collections.swap(l,k,i++))
                              //     And swap the items at indices `k` and `i` back
    Collections.swap(l,i,k);  //   Swap the items at indices `i` and `k`
  if(k>x-2)                   //  If `k` is now equal to the size of the list - 1
    s.add((l+"").replaceAll("\\D",""));}
                              //   Add this permutation to the Set

Osobiście postawiłbym l->n->{...po, void p(...ponieważ lambda jest odpowiedzią na monit, a funkcja wymaga konfiguracji, aby lambda działała. Konsensus w sprawie „wyrażeń funkcyjnych” jest czymś w rodzaju „ostatniego” wyrażenia przesłanego przez użytkownika może być „wyrażeniem funkcyjnym”, jeśli po zapisaniu w zmiennej spełnia wymagania odpowiedzi funkcji „IIRC. Ale to tylko kwestia formatowania i subiektywna.
97 CAD

@ CAD97 Nie miałem pojęcia, że ​​zamówienie ma znaczenie. Ostatnim razem opublikowałem odpowiedź Java 8 z dwiema metodami, których użyłem, voidponieważ była krótsza niż druga lambda i wielokrotność .apply. Nie sprawdziłem tej odpowiedzi (tj. void p(List l,int k)& 2x p(l,0)versus (l,k)->& 2x p.apply(l,0)). Hmm .. drugi wydaje się w tym przypadku o 1 bajt krótszy. Ale mówisz, że zasady mówią, że możesz mieć tylko jedną metodę lambda? Wciąż trochę zdezorientowany, dlaczego to musi być ostatni. Osobiście zawsze zakładać moje odpowiedzi w następującej kolejności: imports; class-fields; main-method/lambda; other methods.
Kevin Cruijssen

znowu, to głównie opinia, chciałbym, żeby ktoś bardziej doświadczony włączył się, zanim naprawdę powie w ten czy inny sposób. Wiem jednak, że to prawda: jeśli musisz wywołać metodę (np. Rekurencyjną lub jako pomocnik), musi ona mieć nazwę. Ale w przypadku zamawiania nie ma to tak naprawdę znaczenia, ponieważ nie zmienia liczby bajtów. Ale imports;helper methods;lambda
zamawiam

@ CAD97 Ah oczywiście tak byłoby void p(List l,int k)i 2x f(l,0);porównaniu f=(l,p)->ze 2x p.apply(l,0);zamiast (co oznacza, że bieżąca wersja 1 bajt krótszy). Jeśli chodzi o kolejność, pozostanę przy tym, ponieważ zrobiłem to ze wszystkimi moimi odpowiedziami, a dla mnie osobiście sensowne jest rozpoczęcie od głównej metody w wyjaśnieniu, a następnie metody pomocniczej, jeśli są jakieś.
Kevin Cruijssen

i niestety nie można tego zrobić po prostu f=(lambda)w Javie, tojava.util.function.BiConsumer<List,Integer>f=(l,p)->{...}
97 CAD

9

Japt , 15 14 13 12 10 bajtów

Pobiera stóg siana jako tablicę liczb całkowitych, a igłę jako ciąg binarny. Zwraca tablicę ciągów liczb całkowitych.

á m¬f_°¤øV

Spróbuj


Wyjaśnienie

á m¬â f_°¤øV
              :Implicit input of array U=haystack and string V=needle
á             :Unique permutations of U
  m           :Map
   ¬          :  Join to a string
    f_        :Filter
      °       :  Postfix increment current element to cast it to an integer
       ¤      :  Convert to base-2 string
        øV    :  Does that contain V?
              :Implicit output of resulting array

Bardzo miło o tym, co bym zrobił. ®¬nÃzapisuje bajt na mapowaniu. (Chciałbym również przejść âdo środka programu, aby pozbyć się drugiego Ã; nie zapisuje żadnych bajtów, ale jest nieco bardziej wydajny i wygląda nieco lepiej)
ETHproductions

Aha, dzięki, @ETHproductions - Byłem tak skupiony na sprawdzeniu, czy mogę ogolić jakieś bajty, wypisując każdą liczbę jako tablicę, że przegapiłem tę prostą zmianę mapowania. âByło szybkie ustalenie dołączona na końcu, kiedy Arnauld wskazał, że zapomniałem usunąć duplikaty z ostatecznej tablicy, ale masz rację, usuwanie duplikatów przed uruchomieniem filtr będzie bardziej efektywny.
Kudłaty

4

Rubin , 61 59 bajtów

->a,n{a.permutation.select{|s|"%b"%s.join=~/#{"%b"%n}/}|[]}

Wypróbuj online!

Fajna funkcja dnia: nie wiedziałam, że mogę wyprowadzić binarną reprezentację ciągu zawierającego liczbę.

Przykład:

puts "%b"%"123"

-> 1111011

3

JavaScript (ES6), 140 bajtów

Bierze igłę jako ciąg binarny.

(h,n,S=new Set,p=(a,m='')=>a.length?a.map((_,i)=>p(A=[...a],m+A.splice(i,1))):S.add(+m),_=p(h))=>[...S].filter(d=>~d.toString(2).indexOf(n))


3

Brachylog , 15 bajtów

{hpc.ḃs~ḃ~t?∧}ᵘ

Wypróbuj online!

Wyjaśnienie

{            }ᵘ    Find all unique outputs, given [h, n], of:
 hpc.                The Output is the concatenation of a permutation of h
    .ḃs              Take a substring of the binary representation of the Output
       ~ḃ            Convert it back to a decimal number
         ~t?∧        This decimal number must me n

2

Mathematica, 170 156 bajtów

(t={};l=Length;v=IntegerDigits;j=v[#2, 2];s=FromDigits/@Flatten/@v@Permutations@#1;Table[If[l@SequenceCases[v[s[[i]],2],j]>0,t~AppendTo~s[[i]]],{i,l@s}];t)&


Wejście

[{12, 34, 56}, 21]

wydajność

{125634, 341256, 345612, 563412}


Jest spacja w v[#2, 2].
Yytsi

1

CJam, 23 22 21 19 bajtów

{e!{si2b1$2b#)},\;}

Jest to blok, który pobiera dane wejściowe n hze stosu i pozostawia dane wyjściowe jako tablicę na stosie.

Wyjaśnienie:

                   e# Stack:                      | 65 [1 2 3]
e!                 e# Unique Permutations:        | 65 [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
  {                e# Filter where block is true: | 65 [3 2 1]
   s               e#   Convert to string:        | 65 "321"
    i              e#   Convert to int:           | 65 321
     2b            e#   Convert to binary:        | 65 [1 0 1 0 0 0 0 0 1]
       1$          e#   Copy behind:              | 65 [1 0 1 0 0 0 0 0 1] 65
         2b        e#   Convert to binary:        | 65 [1 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 1]
           #       e#   Find array in another:    | 65 2
            )      e#   Increment:                | 65 3
             },    e# End filter                  | 65 [321]
               \;  e# Delete back:                | [321]

1

R, 114 bajtów

pryr::f(plyr::l_ply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste(y,collapse=""))))cat(y,"\n")))

Korzysta z wielu pakietów. pryr::f()automatycznie tworzy funkcję, pobierając pciąg wzorca binarnego do wyszukania oraz xwektor z innymi danymi wejściowymi jako danymi wejściowymi. combinat::permntworzy wszystkie permutacje x. R.utils::intToBinto przyjemna i niewygodna wersja do konwersji liczb (lub reprezentacji znakowej liczby) na liczbę binarną, już wygodnie przechowywaną jako znak. Więc zastosuj to do wszystkich permutacji i wyślij je, jeśli ciąg binarny pjest zawarty w binarnej wersji konkatenacji. Wypisywany jest wyraźny znak nowej linii, ponieważ w przeciwnym razie wynik byłby 12 56 3456 34 1234 56 1234 12 56.

plyr's l_plyjest używane do zignorowania wypisywania listy zerowej, oprócz zwykłego wyjścia. Jeśli takie wyjście jest dozwolone:

3 2 1 
[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
NULL

[[5]]
NULL

[[6]]
NULL

Następnie możemy zapisać kilka bajtów, używając lapplyzamiast tego:

108 bajtów:

pryr::f(lapply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste(y,collapse=""))))cat(y,"\n")))

Jeśli takie wyjście jest dozwolone:

[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
[1] 3 2 1

[[5]]
NULL

[[6]]
NULL

Następnie możemy to zrobić jeszcze krócej:

101 bajtów:

pryr::f(lapply(combinat::permn(x),function(y)if(grepl(p,R.utils::intToBin(paste0(y,collapse=""))))y))

Nie dozwolony.


0

Perl 6 , 69 bajtów

{set @^a.permutations».join.grep(*.fmt('%b').contains($^b.base(2)))}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.