Find a binary needle in a decimal haystack

Question

The challenge

You're given:

• a non-empty, unsorted list h of positive integers (the haystack)
• a positive integer n (the needle)

Your task is to return the list of all unique decimal concatenations of permutations of h whose binary representation contains the binary representation of n.

Examples

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

   example

   There's only one matching concatenation, so the expected output is [321].

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

   This time, there are three concatenations which contain the binary pattern 111. The expected output is [123, 231, 312].

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

   Only two permutations are available and both are matching. The expected output is [123, 312].

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

   The only matching concatenation is 122 (1111010 in binary, which contains 1111), so the expected output is [122]. Note that two permutations actually lead to 122 but you are not allowed to output [122, 122].

Clarifications and rules

• You may take the needle as an integer (65), a string representing a decimal value ("65") or a string representing a binary value ("1000001").
• You may take the haystack as a native array/object/set of integers ([11,12,13]), a native array/object/set of strings representing decimal values (["11","12","13"]), or a delimited string of decimal values ("11 12 13" or "11,12,13"). You may also opt for a variant using arrays of digits (like [[1,1],[1,2],[1,3]]).
• The output must follow one of the formats described above for the haystack, but not necessarily the same one.
• You're not supposed to handle haystacks whose highest decimal concatenation is greater than the highest representable unsigned integer in your language.
• Apart from that, your code should theoretically support any input -- assuming it's given enough time and memory.
• This is (削除) SPARTA! (削除ここまで) code-golf, so the shortest answer in bytes win!

Test cases

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 ]

• Dead Possum: My solution's output is like set([(1, 2, 2)]). Is it valid or should I get rid of set?
• Arnauld: @DeadPossum Yes, it's valid.
• Luis Mendo: Can the haystack input be a single string ("123")? In some languages a string is the same as an array of chars, so I think it would makes sense
• Arnauld: @LuisMendo It can't because ["12","3"] and ["1","23"] are two distinct haystacks.
• Luis Mendo: @Arnauld Ah, I thought they were digits. Thanks

Answer 1

05AB1E, (削除) 10 (削除ここまで) 8 bytes

Takes the needle in binary to save 1 byte.

-2 bytes thanks to Emigna

œJÙʒbŒIå

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

• Emigna: œJÙʒbŒIå should work as well.
• kalsowerus: @Emigna Thanks, that saves 2 bytes :)

Answer 2

Python 2, 90 bytes

-3 bytes thanks to @Gábor Fekete

Try it online

Takes as input array of strings, representing ints from hay and string, representing needle in binary

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

• Gábor Fekete: Writing {...} instead of set(...) saves 3 bytes.
• Dead Possum: @GáborFekete I always forget, that {} is set :D Thanks
• user2357112: I believe this fails on H=['1'], N='0'.
• user2357112: Oh, wait, the input is required to be positive.

Answer 3

Java 10, (削除) 320 (削除ここまで) (削除) 312 (削除ここまで) (削除) 305 (削除ここまで) (削除) 297 (削除ここまで) 292 bytes

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 as List & binary-String, output as Strings on new-lines.

Explanation:

Try it here.

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

• CAD97: Personally I'd put l->n->{... after void p(... as the lambda is the answer to the prompt and the function is required setup for the lambda to work. Consensus on "function expressions" is something like "the last 'expression' of your submission can be a 'function expression' if when stored to a variable it meets the requirements of a function answer" IIRC. But that's just a formatting issue, and a subjective one at that.
• Kevin Cruijssen: @CAD97 I had no idea the order mattered. Last time I posted a Java 8 answer with two methods I used void because it was shorter than a second lambda and the multiple .apply. Haven't checked it for this answer (i.e. void p(List l,int k) & 2x p(l,0) versus (l,k)-> & 2x p.apply(l,0)). Hmm.. second one seems to be 1 byte shorter in this case. But you say rules state you are only allowed to have one lambda method? Still a bit confused why it has to be the last one. Personally I always post my answers in this order: imports; class-fields; main-method/lambda; other methods.
• CAD97: again, it's mostly opinion, I'd want someone more experienced to chime in before really saying one way or the other. However, I know this to be true: If you need to call a method (e.g. recursive or as a helper), it needs to have a name. But as for ordering, it doesn't really matter as it doesn't change the byte count. But I order as imports;helper methods;lambda
• Kevin Cruijssen: @CAD97 Ah of course, so it would be void p(List l,int k) & 2x f(l,0); versus f=(l,p)-> & 2x p.apply(l,0); instead (which means the current version is 1 byte shorter). As for the order, I'll just stick with this since I've done so with all my answers, and it also makes sense to me personally to start with the main method in the explanation, and then the helper method(s) if there are any.
• CAD97: and unfortunately you can't just do f=(lambda) in Java, it's java.util.function.BiConsumer<List,Integer>f=(l,p)->{...}

Answer 4

Japt, (削除) 15 (削除ここまで) (削除) 14 (削除ここまで) (削除) 13 (削除ここまで) (削除) 12 (削除ここまで) 10 bytes

Takes the haystack as an array of integers and the needle as a binary string. Outputs an array of integer strings.

á m¬f_°¤øV

• Saved a byte thanks to ETHproductions

Try it

---

Explanation

á 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

• ETHproductions: Very nice, about what I would have done. ®¬nÃ saves a byte on the mapping. (I'd also move â to the middle of the program to get rid of the second Ã; doesn't save any bytes, but it's a little more efficient and looks slightly better)
• Shaggy: Aha, thanks, @ETHproductions - I was so focused on seeing if I could shave any bytes off by outputting each number as an array I missed that simple change to the mapping. The â was a quick fix tacked on the end when Arnauld pointed that I'd forgotten to remove the duplicates from the final array but, you're right, removing the duplicates before running the filter would be more efficient.

Answer 5

Ruby, (削除) 61 (削除ここまで) 59 bytes

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

Try it online!

Cool feature of the day: I didn't know I could output the binary representation of a string containing a number.

Example:

puts "%b"%"123"
-> 1111011

Answer 6

Brachylog, 15 bytes

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

Try it online!

Explanation

{ }u 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

Answer 7

Mathematica, (削除) 170 (削除ここまで) 156 bytes

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

input

[{12, 34, 56}, 21]

output

{125634, 341256, 345612, 563412}

• Yytsi: There's a whitespace at v[#2, 2].

Answer 8

JavaScript (ES6), 140 bytes

Takes needle as a binary string.

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

f=
(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))
console.log( f([1, 2, 3], (65).toString(2)) )
console.log( f([12, 34, 56], (21).toString(2)) )

Answer 9

CJam, (削除) 23 (削除ここまで) (削除) 22 (削除ここまで) (削除) 21 (削除ここまで) 19 bytes

{e!{si2b12ドルb#)},\;}

This is a block that takes inputs n h on the stack and leaves the output as an array on the stack.

Explanation:

 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]

Answer 10

R, 114 bytes

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

Uses a bunch of packages. pryr::f() automatically creates a function, taking p, a string of the binary pattern to look for, and x, a vector with the other input as input. combinat::permn creates all permutations of x. R.utils::intToBin is a nice and wordy version to convert a numeric (or character representation of a numeric) to a binary number, already conveniently stored as a character. So applying this over all the permutations and outputting them if the binary string p is contained in the binary version of the concatenation. An explicit newline is printed, because otherwise the output would be 12 56 3456 34 1234 56 1234 12 56.

plyr's l_ply is used to surpress outputting a null list, besides the regular output. If output like this is allowed:

3 2 1 
[[1]]
NULL
[[2]]
NULL
[[3]]
NULL
[[4]]
NULL
[[5]]
NULL
[[6]]
NULL

Then we can save few bytes by using lapply instead:

108 bytes:

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

(削除) If output like this is allowed:

[[1]]
NULL
[[2]]
NULL
[[3]]
NULL
[[4]]
[1] 3 2 1
[[5]]
NULL
[[6]]
NULL

Then we can do it even shorter:

101 bytes:

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

(削除ここまで) Not allowed.

Answer 11

Perl 6, 69 bytes

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