All Possible Matching Lists

Implement a function that takes a list that consists of 0, 1 or 2, the list is called "pattern". Your job is to return all possible lists that match the pattern.

• 0 matches 0
• 1 matches 1
• 2 matches 0 and 1

Examples:

f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 1, 0, 0], [0, 1, 0, 1], [0, 0, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]


Order does not matter, you can use a {set} data structure instead.

You cannot use regular expressions or other string pattern matching mechanisms. You cannot use a brute-force search.

Shortest solution wins.

• How do you define a brute force search? – xnor Mar 9 '15 at 7:55

f[]=[[]]
f(2:r)=f(0:r)++f(1:r)
f(x:r)=map(x:)\$f r


Interestingly this is exactly what I'd write even if this wasn't golf - except for removing spaces and calling the list's tail r rather than xs.

Saved 8 characters thanks to Zgarb.

r 2=[0,1]
r n=[n]
f=mapM r

• sequence.map is equivalent to mapM, which is 8 characters shorter. – Zgarb Mar 9 '15 at 15:25

Prolog, 62 characters

f([],[]). f([H|T],[A|B]):-((H=2,(A=0;A=1));(H<2,A=H)),f(T,B).


Example:

?- f([0,2,0,2],X).
X = [0, 0, 0, 0] ;
X = [0, 0, 0, 1] ;
X = [0, 1, 0, 0] ;
X = [0, 1, 0, 1] ;

• Welcome to the site! :) – DJMcMayhem Oct 3 '17 at 20:36

Mathematica, 30 chars

f=Tuples[{#}&/@#/.{2}->{0,1}]&


Examples:

f[{0, 1, 1}]


{{0, 1, 1}}

f[{0, 2, 0, 2}]


{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}}

f[{2, 1, 0}]


{{0, 1, 0}, {1, 1, 0}}

• Since the OP isn't asking for a named function you can even drop the f=. – Martin Ender Mar 9 '15 at 12:06

Ruby - 76 characters

def f l;l==l-[2]?[l]:((j=l.dup)[k=l.index(2)]=0;(i=l.dup)[k]=1;f(j)+f(i))end


Testing script:

require_relative 'golf-lists'

[
[0, 1, 1],
[0, 2, 0, 2],
[2, 1, 0]
].each do |list|
puts "f([#{list.join(', ')}]) == #{f(list)}"
end


Result:

f([0, 1, 1]) == [[0, 1, 1]]
f([0, 2, 0, 2]) == [[0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]]
f([2, 1, 0]) == [[0, 1, 0], [1, 1, 0]]


Scheme (149) (148)

(define(f l)(if(null? l)'(())(let((t(f(cdr l)))(n(car l)))(if(< n 2)(map(lambda(m)(,n,@m))t)(,@(map(lambda(m)(0,@m))t),@(map(lambda(m)(1,@m))t]


With whitespace (the closing square brace closes all open parentheses on certain Scheme implementations; 154 chars without it):

(define (f l)
(if (null? l)
'(())
(let ((t (f (cdr l)))(n(car l)))
(if (< n 2)
(map (lambda (m) (,n ,@m)) t)
(,@(map (lambda (m) (0 ,@m)) t)
,@(map (lambda (m) (1 ,@m)) t]


CJam, 18 bytes

CJam is much younger than this challenge, so this is answer is not eligible for being accepted.

]]l~{2b\f{\f+~}}/p


Reads input from STDIN as a CJam style array.

Test it here.

Explanation

]]l~{2b\f{\f+~}}/p
]]                 "Push a nested empty array [[]] onto the stack. This is the base case.";
l~               "Read and eval the input.";
{          }/  "For each integer in the input.";
2b            "Convert to base 2. This turns 0 into [0], 1 into [1] and 2 into [1 0].";
\f{    }    "Swap with the current result and map this block onto the base-2 representation
copying in the current list of lists on each iteration.";
\f+      "Swap the list of lists with the 0 or 1 and add the number to each list.";
~     "Unwrap the list of lists. They'll be regrouped by the surrounding f{...}.";
p "Pretty-print the result.";


Python 2, 156 bytes

def f(l):R,L=range(len(l)),[];exec"\n".join(" "*j+"for v%d in[[l[%d]],[0,1]][l[%d]>1]:"%(j,j,j)for j in R)+"L+=["+"".join("v%d,"%j for j in R)+"],";return L


Try it online!

J, 19 bytes

[:>@,[:{{&(0;1;0 1)


Try it online!

I had originally created a much longer version using amend and binary numbers, but user b_jonas suggested the above approach in IRC to me.

It essentially converts 0 and 1 to themselves, and 2 to the list 0 1, and the just cross products everything using catalog {. Since catalog requires boxed data, and returns structured data, everything is (un)raveled and unboxed at the end: >@,.