41
\$\begingroup\$

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! , 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 ]
\$\endgroup\$
10
  • 1
    \$\begingroup\$ My solution's output is like set([(1, 2, 2)]). Is it valid or should I get rid of set? \$\endgroup\$ May 29, 2017 at 13:27
  • \$\begingroup\$ @DeadPossum Yes, it's valid. \$\endgroup\$
    – Arnauld
    May 29, 2017 at 13:31
  • \$\begingroup\$ 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 \$\endgroup\$
    – Luis Mendo
    May 29, 2017 at 13:36
  • \$\begingroup\$ @LuisMendo It can't because ["12","3"] and ["1","23"] are two distinct haystacks. \$\endgroup\$
    – Arnauld
    May 29, 2017 at 13:38
  • \$\begingroup\$ @Arnauld Ah, I thought they were digits. Thanks \$\endgroup\$
    – Luis Mendo
    May 29, 2017 at 13:39

11 Answers 11

17
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ œJÙʒbŒIå should work as well. \$\endgroup\$
    – Emigna
    May 29, 2017 at 13:34
  • \$\begingroup\$ @Emigna Thanks, that saves 2 bytes :) \$\endgroup\$
    – kalsowerus
    May 29, 2017 at 13:42
11
\$\begingroup\$

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)))}
\$\endgroup\$
4
  • 4
    \$\begingroup\$ Writing {...} instead of set(...) saves 3 bytes. \$\endgroup\$ May 29, 2017 at 13:37
  • 1
    \$\begingroup\$ @GáborFekete I always forget, that {} is set :D Thanks \$\endgroup\$ May 29, 2017 at 13:39
  • \$\begingroup\$ I believe this fails on H=['1'], N='0'. \$\endgroup\$ May 29, 2017 at 18:54
  • \$\begingroup\$ Oh, wait, the input is required to be positive. \$\endgroup\$ May 29, 2017 at 19:01
10
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – CAD97
    May 29, 2017 at 16:43
  • \$\begingroup\$ @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. \$\endgroup\$ May 29, 2017 at 17:06
  • \$\begingroup\$ 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 \$\endgroup\$
    – CAD97
    May 29, 2017 at 17:17
  • \$\begingroup\$ @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. \$\endgroup\$ May 30, 2017 at 6:46
  • \$\begingroup\$ and unfortunately you can't just do f=(lambda) in Java, it's java.util.function.BiConsumer<List,Integer>f=(l,p)->{...} \$\endgroup\$
    – CAD97
    May 30, 2017 at 7:16
9
\$\begingroup\$

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

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
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ May 29, 2017 at 16:14
  • \$\begingroup\$ 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. \$\endgroup\$
    – Shaggy
    May 29, 2017 at 16:19
4
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Brachylog, 15 bytes

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

Try it online!

Explanation

{            }ᵘ    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
\$\endgroup\$
2
\$\begingroup\$

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}

\$\endgroup\$
1
  • \$\begingroup\$ There's a whitespace at v[#2, 2]. \$\endgroup\$
    – Yytsi
    May 30, 2017 at 5:38
1
\$\begingroup\$

CJam, 23 22 21 19 bytes

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

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]
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 69 bytes

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.