Temukan jarum biner di tumpukan jerami desimal

41

Tantangan

Anda diberikan:

  • daftar h bilangan bulat positif tidak kosong yang tidak disortir (tumpukan jerami)
  • bilangan bulat positif n (jarum)

Tugas Anda adalah mengembalikan daftar semua gabungan desimal unik permutasi dari h yang representasi binernya berisi representasi biner dari n .

Contohnya

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

    contoh

    Hanya ada satu rangkaian yang cocok, jadi output yang diharapkan adalah [321].

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

    Kali ini, ada tiga rangkaian yang berisi pola biner 111 . Output yang diharapkan adalah [123, 231, 312].

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

    Hanya dua permutasi yang tersedia dan keduanya cocok. Output yang diharapkan adalah [123, 312].

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

    Satu-satunya gabungan yang cocok adalah 122 ( 1111010 dalam biner, yang berisi 1111 ), sehingga output yang diharapkan adalah [122]. Perhatikan bahwa dua permutasi sebenarnya mengarah ke 122 tetapi Anda tidak diizinkan untuk menghasilkan [122, 122].

Klarifikasi dan aturan

  • Anda dapat menggunakan jarum sebagai integer ( 65), string yang mewakili nilai desimal ( "65") atau string yang mewakili nilai biner ( "1000001").
  • Anda dapat mengambil tumpukan jerami sebagai array / objek / set integer asli ( [11,12,13]), array / objek / set string asli yang mewakili nilai desimal ( ["11","12","13"]), atau string nilai desimal ( "11 12 13"atau "11,12,13") yang dibatasi . Anda juga dapat memilih varian menggunakan array angka (seperti [[1,1],[1,2],[1,3]]).
  • Output harus mengikuti salah satu format yang dijelaskan di atas untuk tumpukan jerami, tetapi tidak harus yang sama.
  • Anda tidak seharusnya menangani tumpukan jerami yang gabungan angka desimalnya lebih tinggi daripada bilangan bulat unsigned representable tertinggi dalam bahasa Anda.
  • Selain itu, kode Anda secara teoritis harus mendukung input apa pun - dengan asumsi itu diberikan cukup waktu dan memori.
  • Ini SPARTA! , jadi jawaban tersingkat dalam byte menang!

Uji kasus

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 ]
Arnauld
sumber
1
Output dari solusi saya adalah seperti set([(1, 2, 2)]). Apakah ini valid atau haruskah saya singkirkan set?
Dead Possum
@DeadPossum Ya, ini valid.
Arnauld
Bisakah input tumpukan jerami menjadi string tunggal ("123")? Dalam beberapa bahasa string sama dengan array karakter, jadi saya pikir itu masuk akal
Luis Mendo
@LuisMendo Tidak bisa karena ["12","3"]dan ["1","23"]dua tumpukan jerami yang berbeda.
Arnauld
@Arnauld Ah, saya pikir itu angka. Terima kasih
Luis Mendo

Jawaban:

17

05AB1E , 10 8 byte

Mengambil jarum dalam biner untuk menghemat 1 byte.

-2 byte terima kasih kepada Emigna

œJÙʒbŒIå

Cobalah 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
kalsowerus
sumber
1
ÙʒJÙʒbŒIå juga harus bekerja.
Emigna
@Emigna Terima kasih, itu menghemat 2 byte :)
kalsowerus
11

Python 2, 90 byte

-3 byte terima kasih kepada @ Gábor Fekete

Cobalah online

Diambil sebagai array input string, mewakili int dari hay dan string, mewakili jarum dalam biner

from itertools import*
lambda H,N:{i for i in permutations(H)if N in bin(int(''.join(i)))}
Possum Mati
sumber
4
Menulis {...}alih-alih set(...)menghemat 3 byte.
Gábor Fekete
1
@ GáborFekete Saya selalu lupa, bahwa {} diset: D Terima kasih
Dead Possum
Saya percaya ini gagal H=['1'], N='0'.
user2357112 mendukung Monica
Oh, tunggu, input harus positif.
user2357112 mendukung Monica
10

Java 10, 320 312 305 297 292 byte

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

Input sebagai List & binary-String, output sebagai Strings pada baris baru.

Penjelasan:

Coba di sini.

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
Kevin Cruijssen
sumber
Secara pribadi saya akan mencari l->n->{...setelah void p(...lambda adalah jawaban untuk prompt dan fungsi diperlukan setup agar lambda berfungsi. Konsensus tentang "ekspresi fungsi" adalah sesuatu seperti "ekspresi 'terakhir dari kiriman Anda dapat menjadi' ekspresi fungsi 'jika ketika disimpan ke variabel, ia memenuhi persyaratan jawaban fungsi" IIRC. Tapi itu hanya masalah pemformatan, dan subyektif.
CAD97
@ CAD97 Saya tidak tahu urutan itu penting. Terakhir kali saya memposting jawaban Java 8 dengan dua metode yang saya gunakan voidkarena lebih pendek dari lambda kedua dan banyak .apply. Belum memeriksanya untuk jawaban ini (yaitu void p(List l,int k)& 2x p(l,0)versus (l,k)->& 2x p.apply(l,0)). Hmm .. yang kedua sepertinya 1 byte lebih pendek dalam hal ini. Tapi Anda mengatakan aturan menyatakan Anda hanya diperbolehkan memiliki satu metode lambda? Masih agak bingung mengapa itu harus menjadi yang terakhir. Secara pribadi saya selalu posting jawaban saya dalam urutan ini: imports; class-fields; main-method/lambda; other methods.
Kevin Cruijssen
lagi, sebagian besar pendapat, saya ingin seseorang yang lebih berpengalaman untuk berpadu sebelum benar-benar mengatakan satu atau lain cara. Namun, saya tahu ini benar: Jika Anda perlu memanggil metode (misalnya rekursif atau sebagai pembantu), itu perlu memiliki nama. Tetapi untuk pemesanan, itu tidak terlalu penting karena tidak mengubah jumlah byte. Tapi saya memesanimports;helper methods;lambda
CAD97
@ CAD97 Ah tentu saja, jadi itu akan menjadi void p(List l,int k)& 2x f(l,0);versus f=(l,p)->& 2x p.apply(l,0);(yang berarti versi saat ini lebih pendek 1 byte). Adapun pesanan, saya akan tetap dengan ini karena saya sudah melakukannya dengan semua jawaban saya, dan masuk akal bagi saya secara pribadi untuk memulai dengan metode utama dalam penjelasan, dan kemudian metode pembantu jika ada
Kevin Cruijssen
dan sayangnya Anda tidak bisa hanya melakukannya f=(lambda)di Jawa, itujava.util.function.BiConsumer<List,Integer>f=(l,p)->{...}
CAD97
9

Japt , 15 14 13 12 10 byte

Mengambil tumpukan jerami sebagai array bilangan bulat dan jarum sebagai string biner. Output array string integer.

á m¬f_°¤øV
  • Disimpan satu byte berkat produk ETH

Cobalah


Penjelasan

á 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
Shaggy
sumber
Sangat bagus, tentang apa yang akan saya lakukan. ®¬nÃmenyimpan satu byte pada pemetaan. (Saya juga akan pindah âke tengah-tengah program untuk menyingkirkan yang kedua Ã; tidak menyimpan byte, tetapi itu sedikit lebih efisien dan terlihat sedikit lebih baik)
ETHproductions
Aha, terima kasih, @ ETHproductions - Saya sangat fokus untuk melihat apakah saya bisa mencukur byte dengan mengeluarkan setiap angka sebagai array sehingga saya melewatkan perubahan sederhana pada pemetaan. Itu âadalah perbaikan cepat yang ditempelkan pada akhirnya ketika Arnauld menunjukkan bahwa saya lupa menghapus duplikat dari array terakhir tetapi, Anda benar, menghapus duplikat sebelum menjalankan filter akan lebih efisien.
Shaggy
4

Ruby , 61 59 byte

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

Cobalah online!

Fitur keren hari ini: Saya tidak tahu saya bisa menampilkan representasi biner dari string yang berisi angka.

Contoh:

puts "%b"%"123"

-> 1111011
GB
sumber
3

JavaScript (ES6), 140 byte

Mengambil jarum sebagai string biner.

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

Darrylyeo
sumber
3

Brachylog , 15 byte

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

Cobalah online!

Penjelasan

{            }ᵘ    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
Fatalisasi
sumber
2

Mathematica, 170 156 byte

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


memasukkan

[{12, 34, 56}, 21]

keluaran

{125634, 341256, 345612, 563412}

J42161217
sumber
Ada spasi putih di v[#2, 2].
Yytsi
1

CJam, 23 22 21 19 byte

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

Ini adalah blok yang mengambil input n hpada stack dan meninggalkan output sebagai array pada stack.

Penjelasan:

                   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]
Buah Esolanging
sumber
1

R, 114 byte

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

Menggunakan banyak paket. pryr::f()secara otomatis membuat fungsi, mengambil p, string dari pola biner untuk mencari, dan x, vektor dengan input lain sebagai input. combinat::permnmembuat semua permutasi dari x. R.utils::intToBinadalah versi yang bagus dan bertele-tele untuk mengonversi angka (atau representasi karakter dari angka) menjadi angka biner, yang sudah tersimpan sebagai karakter. Jadi menerapkan ini pada semua permutasi dan mengeluarkannya jika string biner pterkandung dalam versi biner dari rangkaian tersebut. Baris baru yang eksplisit dicetak, karena jika tidak, hasilnya akan seperti itu 12 56 3456 34 1234 56 1234 12 56.

plyr's l_plydigunakan untuk menekan keluaran daftar null, selain output biasa. Jika output seperti ini diizinkan:

3 2 1 
[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
NULL

[[5]]
NULL

[[6]]
NULL

Maka kita bisa menyimpan beberapa byte dengan menggunakan lapply:

108 byte:

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

Jika output seperti ini diizinkan:

[[1]]
NULL

[[2]]
NULL

[[3]]
NULL

[[4]]
[1] 3 2 1

[[5]]
NULL

[[6]]
NULL

Maka kita bisa melakukannya lebih pendek:

101 byte:

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

Tidak diizinkan

JAD
sumber
0

Perl 6 , 69 byte

{set @^a.permutations».join.grep(*.fmt('%b').contains($^b.base(2)))}
Sean
sumber