7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ How do you define a brute force search? \$\endgroup\$
    – xnor
    Mar 9, 2015 at 7:55

9 Answers 9

8
\$\begingroup\$

Haskell, 49 characters

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.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 34 26 characters

Saved 8 characters thanks to Zgarb.

r 2=[0,1]
r n=[n]
f=mapM r
\$\endgroup\$
1
  • 1
    \$\begingroup\$ sequence.map is equivalent to mapM, which is 8 characters shorter. \$\endgroup\$
    – Zgarb
    Mar 9, 2015 at 15:25
5
\$\begingroup\$

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] ;
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to the site! :) \$\endgroup\$
    – DJMcMayhem
    Oct 3, 2017 at 20:36
3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Since the OP isn't asking for a named function you can even drop the f=. \$\endgroup\$ Mar 9, 2015 at 12:06
1
\$\begingroup\$

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

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

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.";
\$\endgroup\$
0
\$\begingroup\$

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!

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

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: >@,.

\$\endgroup\$

Your Answer

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

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