Brute-force the switchboard

Question

The other day, our team went to an escape room. One of the puzzles involved a board of six mechanical switches where you had to find the correct combination of on and off in order to unlock a box, somewhat like this:

-v-v-v-
-v-v-v-

Being developers, we decided it would be more efficient to try every single one of 2^6=64 combinations than actually solve the puzzle. So we assigned some poor guy to do some binary counting:

-v-v-v-
-v-v-v-

-v-v-v-
-v-v-^-

-v-v-v-
-v-^-v-

-v-v-v-
-v-^-^-

and so on.

The challenge
Write a program that, given the switches all in off position as a string formatted as above, generates all combinations of on and off in any order.

You can write either a full program or a function. Thus, your program can either take in input through stdin, a file, or as a single string argument, and either return or print the output. If returned, the output may be in a list/array/etc. rather than a single string. If the output is a single string, the boards should be separated by newlines (trailing newlines are allowed.)

The input strings will match the regex r'((-v)+-)(\n(-v)+-)*' and represent one board with all switches off. This means no zero case, and switches are left-aligned. Each row might not have the same number of switches.

Each output board should be of the exact same format as the input, except that the v's may be replaced by ^'s as required. The output boards can be separated by any number of newlines.

Since runtime is naturally O(2^n) in the number of switches, your code will not be tested on any more than 10 switches in any arrangement.

This is code-golf, so shortest code in number of bytes wins.

Sample inputs and outputs

Input:

-v-

Possible output:

-v-
-^-

Input:

-v-
-v-

Possible output:

-^-
-^-
-^-
-v-

-v-
-^-


-v-
-v-

Since it's extremely tedious to check your answer for bigger numbers of switches, here's a Python script as a sanity check tool. (I've included a currently commented-out snippet to generate expected output from a given input file in case you want more test cases.) It's quite a bit less flexible in terms of input and output than the spec, unfortunately; put the input string in a file named 'input' and the newline-separated output (sorry, no list formatting) in a file named 'output' in the same directory and run python3 sanitycheck.py.

Answer 1

Haskell, 25 24 23 17 bytes

mapM$min"^v".pure

Try it online!

-1 byte thanks to @H.PWiz

-1 byte thanks to @nimi

Returns a list of strings. The TIO has 2 extra bytes for the function declaration - I've seen other people leave it off when they write the function pointfree so I'm doing the same unless told otherwise.

Previous Answer (25 bytes)

g 'v'="v^"
g x=[x]
mapM g

The explanations are all for the previous answer, which works pretty much the same way, except I inlined the definition of g. The way g works now is by using lexical comparison to substitute ^v for v and keep everything else the same.

Interestingly, this works for arbitrary switchboards:

>>> mapM g "-----^-----"
  ["-----v-----", "-----^-----"]

Explanation (Short)

g 'v'="v^" -- for 'v', choose between 'v' or '^'
g x=[x]    -- for any other character, choose just that character
mapM g     -- find all ways to choose characters using g on the given input

Explanation (Long)

mapM is a pretty scary function for those not familiar with Haskell. But it's not hard to understand in this context. By making it act on Strings (which in Haskell are lists of characters), I've specialized it to its definition for lists. So in this context, its type signature is

mapM :: (a -> [b]) -> [a] -> [[b]]
--      ^^^^^^^^^^                  arg 1: a function from any a to a list of b
--                    ^^^           arg 2: a list of a
--                           ^^^^^ return: a list of list of b

It is actually even more specialized in my usage of it - a and b are both Char - so we can see the type signature as

mapM :: (Char -> String) -> String -> [String]

Let's quickly look at what g does before explaining how mapM works.

g :: Char -> String
g 'v' = "v^"
g  x  = [x]

g uses pattern matching to convert the Char 'v' into the string "v^"; everything else gets converted to a singleton string (remember, strings are just lists of Chars, so we can put x in a singleton list). Testing on the REPL, we find this is the case

>>> g 'a'
  "a"
>>> g 'b'
  "b"
>>> g 'v'
  "v^"

Note that g has the right type to be an argument of mapM (unsurprisingly!).

We'll explore how mapM works by giving it g and the argument

"-v-\n-v-"

as input.

mapM first maps g over the String, and because g converts Chars to Strings, this gives us a list of Strings

["-", "v^", "-", "\n", "-", "v^", "-"]

While this is the correct output type, mapM does slightly more. You can think of it as forming all Strings that you could create from this list if you had to pick a single character from each String in it (in order).

So for the first element, you have no choice other than to pick the Char '-'. For the second element, you can choose between 'v' and '^', so on and so forth.

It's roughly equivalent to this python code:

result = []
for x1 in "-":
  for x2 in "v^":
    for x3 in "-":
      ...
        result.append(''.join([x1, x2, x3, x4, x5, x6, x7]))

Except that since Haskell separates between Chars and Strings, when it puts the Chars into a list, it doesn't need to join them.

So the final output is

["-v-\n-v-", "-v-\n-^", "-^-\n-v-", "-^-\n-^-"]

as desired.

Answer 2

Jelly, 7 bytes

«Ƭ€”^Œp

Try it online!

Output is a list of Jelly strings.

Explanation:

«Ƭ€”^Œp  Arguments: 1
«Ƭ€”^    Dyad-nilad pair
  €       Map over left argument
 Ƭ         Apply repeatedly until a result that has previously been seen is seen
           again, return original and intermediate results
«           Dyad: Minimum of arguments
   ”^     Nilad: Literal: '^'
         Note: 'v' is the only character that is greater than '^' and can
         appear in the input, so, while for every character c other than 'v'
         this operation returns [c], for 'v' it returns ['v', '^']. In this way,
         duplicates are never going to appear in the output.
     Œp  Monad: Cartesian product of elements

Answer 3

Perl 6, 32 bytes

{[X~] .comb».&{$_,('^'if /v/)}}

Try it online!

• .comb splits the string into characters.
• ».&{...} maps the characters according to the function between the braces.
• $_, ('^' if /v/) produces a list of alternates for each character. Only v has an alternate: ^.
• [X~] reduces that list with the string-concatenation cross-product operator X~.

Answer 4

Perl 5, 29 bytes

sub{glob"\Q@_"=~s/v/{v,^}/gr}

Try it online!

My first submission!

---

Normally, Perl 5 golfers submit programs instead of functions to save from having to include sub{} at a minimum. But they have to add say, say␠, say for or say for␠ in exchange.

By going the sub approach, I could shorten

say for glob"\Q$_"=~s/v/{v,^}/gr        # Perl 5, -0n, 32 bytes

to

sub{glob"\Q@_"=~s/v/{v,^}/gr}           # Perl 5, 29 bytes

---

The explanation is quite simple. Perl 5 has a builtin glob operator which accepts a shell-like glob pattern which can be used to generate lists of file names (e.g. foo*.txt) or list of strings (e.g. {a,b,c}). The catch is that the newline needs to be escaped, which I've done using quotemeta (as \Q).

Answer 5

K (ngn/k), 27 25 bytes

{?(,/,/:\:)/x,'"^"/"v"\x}

Try it online!

"^"/"v"\ replace "v" with "^"

x,' zip with the original chars

(,/,/:\:)/ cartesian product over

? uniq

Answer 6

APL (Dyalog Classic), 21 17 15 bytes

⊃⊢∘.,.∪'v'⎕r'^'

Try it online!

similar to my k solution

returns an n-dimensional array of strings (n = number of switches)

in easier to explain form: ⊃(∘.,⌿ ⊢ ∪¨ 'v'⎕r'^')

'v'⎕r'^' replace vs with ^s

⊢ ∪¨... unions with each of the original characters. it's a vector of strings of length 1 or 2

∘.,⌿ cartesian product reduction

⊃ disclose

to get to the fully golfed version we follow the pattern f⌿ A g¨ B -> A f.g B:

∘.,⌿ ⊢ ∪¨ 'v'⎕r'^' -> ⊢ ∘.,.∪ 'v'⎕r'^'

as a side effect the parentheses are no longer needed

Answer 7

Java, 202 197 189 191 bytes

Yes, it's a comparatively verbose language, but that's what I consider as classical golfing:

import java.util.function.Function;

public class SwitchBored
{
    public static void main(String[] args)
    {
        Function<String, String> f = s->{byte i,j,k,m=1,u='^',d='v',a[]=(s+"\n\n").getBytes();for(i=0,s="";i<m;i++,s+=new String(a))for(j=0,k=0;k<a.length;k++){if(a[k]==d||a[k]==u){a[k]=(i&1<<j++)!=0?u:d;m<<=i>0?0:1;}}return s;};

        //System.out.println(f.apply("-v-"));
        System.out.println(f.apply("-v-v-v-\n-v-v-v-"));
        //System.out.println(f.apply("-v-v-v-\n-v-v-"));
        //System.out.println(f.apply("-v-v-v-v-v-\n-v-"));
        //System.out.println(f.apply("-v-v-v-v-v-\n-v-v-v-v-v-"));
    }
}

I thought that a "simple" way of dealing with the line breaks that are necessary to achieve to proper layout was to actually re-use the original input character array, and only fill it with 'v's and '^'s at the appropriate positions.

Updates:

It turned out that not storing the positions allows ditching the int and array variable declarations (at the cost of checking each position of the array whether it contains an v or ^ on the fly), saving 5 bytes.

Another 8 bytes saved by computing the upper limit (1<<numberOfSwitches) more compactly.

According to the rule mentioned in the comment, function declaration should be counted, so now it's a lambda...

Answer 8

J, 42 bytes

]`('v'I.@e.~[)`[}"1'v^'{~2#:@i.@^1#.e.&'v'

Try it online!

explanation

]`('v' I.@e.~ [)`[}"1 ('v^' {~ 2 #:@i.@^ 1 #. e.&'v')

Let take

-v-
-v-

as our example input.

• ('v^' {~ 2 #:@i.@^ 1 #. e.&'v') creates all possible combos of just the switches, ignoring the input format. for our example it produces:

  vv
  v^
  ^v
  ^^
  

  • 1 #. e.&'v' counts the numbers of vs in the input.
  • 2 #:@i.@^ raises 2 to that power, produces the integers from 0 to that number i., and converts them to binary #:
  • 'v^' {~ changes to binary digits to v and ^
• ]`('v' I.@e.~ [)`[}"1 amends the original input, producing one copy of it for each row of the result described in the previous step (ie, all possible v/^ combos). In each copy the v of the original input are replaced with one possible sequence of v/^.

Answer 9

C (gcc), 75 74 70 bytes

-5 byte thanks to @ceilingcat

*b=0;f(char*s){b=b?b:s;*s?f(s+1),*s>46?*s=94,f(s+1),*s='v':0:puts(b);}

Try it online!

requires the memory s points to to be writable

Answer 10

J, 41 40 24 bytes

[:>@,@{<@(,'^'$~'v'=])"0

Try it online!

Answer 11

Python 2, 87 bytes

def f(s):i=s.find('v');return(i>=0and f(s[:i].replace('^','v')+'^'+s[i+1:])+'\n'or'')+s

Try it online!

A non-regex approach.

Answer 12

Python 3.8 (pre-release), 129 117 116 110 106 bytes

-10 bytes thanks to @Chas Brown

f=lambda s:{s.replace('v','{}').format(*['v^'[c<'1']for c in bin(x+i)[::-1]])for i in range(x:=1<<len(s))}

Try it online!

Answer 13

C (gcc), 102 bytes

i,j,l;f(char*s){for(l=j=0;l++<1<<j;puts(""))for(i=j=0;s[i];i++)putchar(s[i]>64?l&1<<j++?118:94:s[i]);}

Try it online!

Answer 14

K4, 44 bytes

Solution:

-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2};

Examples:

q)k)-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-";
-v-
-^-

q)k)-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-\n-v-";
-v-
-v-
-v-
-^-
-^-
-v-
-^-
-^-

q)k)-1{@[x;&w;:;]@/:"v^"@a\:'!*/a:(+/w:"v"=x)#2}"-v-v-\n-v-v-v-\n-v-";
-v-v-
-v-v-v-
-v-
-v-v-
-v-v-v-
-^-
-v-v-
-v-v-^-
-v-
-v-v-
-v-v-^-
-^-
-v-v-
-v-^-v-
-v-
-v-v-
-v-^-v-
-^-
-v-v-
-v-^-^-
-v-
-v-v-
-v-^-^-
-^-
-v-v-
-^-v-v-
-v-
-v-v-
-^-v-v-
-^-
-v-v-
-^-v-^-
-v-
-v-v-
-^-v-^-
-^-
-v-v-
-^-^-v-
-v-
-v-v-
-^-^-v-
-^-
-v-v-
-^-^-^-
-v-
-v-v-
-^-^-^-
-^-
-v-^-
-v-v-v-
-v-
-v-^-
-v-v-v-
-^-
-v-^-
-v-v-^-
-v-
-v-^-
-v-v-^-
-^-
-v-^-
-v-^-v-
-v-
-v-^-
-v-^-v-
-^-
-v-^-
-v-^-^-
-v-
-v-^-
-v-^-^-
-^-
-v-^-
-^-v-v-
-v-
-v-^-
-^-v-v-
-^-
-v-^-
-^-v-^-
-v-
-v-^-
-^-v-^-
-^-
-v-^-
-^-^-v-
-v-
-v-^-
-^-^-v-
-^-
-v-^-
-^-^-^-
-v-
-v-^-
-^-^-^-
-^-
-^-v-
-v-v-v-
-v-
-^-v-
-v-v-v-
-^-
-^-v-
-v-v-^-
-v-
-^-v-
-v-v-^-
-^-
-^-v-
-v-^-v-
-v-
-^-v-
-v-^-v-
-^-
-^-v-
-v-^-^-
-v-
-^-v-
-v-^-^-
-^-
-^-v-
-^-v-v-
-v-
-^-v-
-^-v-v-
-^-
-^-v-
-^-v-^-
-v-
-^-v-
-^-v-^-
-^-
-^-v-
-^-^-v-
-v-
-^-v-
-^-^-v-
-^-
-^-v-
-^-^-^-
-v-
-^-v-
-^-^-^-
-^-
-^-^-
-v-v-v-
-v-
-^-^-
-v-v-v-
-^-
-^-^-
-v-v-^-
-v-
-^-^-
-v-v-^-
-^-
-^-^-
-v-^-v-
-v-
-^-^-
-v-^-v-
-^-
-^-^-
-v-^-^-
-v-
-^-^-
-v-^-^-
-^-
-^-^-
-^-v-v-
-v-
-^-^-
-^-v-v-
-^-
-^-^-
-^-v-^-
-v-
-^-^-
-^-v-^-
-^-
-^-^-
-^-^-v-
-v-
-^-^-
-^-^-v-
-^-
-^-^-
-^-^-^-
-v-
-^-^-
-^-^-^-
-^-

Explanation:

In-place replacement of "^". Determine number of combinations of switches (e.g. 2^n), count up in binary, replace switches...

-1{@[x;&w;:;]@'"v^"@a\:'!*/a:(+/w:"v"=x)#2}; / the solution
-1                                         ; / print to STDOUT, swallow -1
  {                                       }  / lambda taking implicit x
                                        #2   / take 2
                             (         )     / do this together
                                  "v"=x      / does input = "v" ?
                                w:           / save as w
                              +/             / sum up
                           a:                / save as a
                         */                  / product
                        !                    / range 0..n
                    a\:'                     / convert each to base-2
               "v^"@                         / index into "v^"
             @'                              / apply each
   @[x;&w;:;]                                / apply assignment to x at indexes where w is true

Answer 15

R, 116 bytes

function(x,u=utf8ToInt(x))apply(expand.grid(rep(list(c(118,94)),sum(u>45))),1,function(i)intToUtf8(`[<-`(u,u>45,i)))

Try it online!

Function returning a vector of newline separated boards

Answer 16

JavaScript, 88 bytes

s=>(g=n=>n--?g(n)+`
`+s.replace(/v/g,_=>'v^'[i=n&1,n>>=1,i]):'')(2**~-s.split`v`.length)

Try it online!

Answer 17

Retina 0.8.2, 29 bytes

T`¶v`;#
+%1`#
v$'¶$`^
%`;|$
¶

Try it online! Explanation:

T`¶v`;#

Change the newlines into ;s and the vs into # markers.

+%1`#

Replace the #s one at a time from left to right.

v$'¶$`^

Change each line into two lines, one with the # replaced with a v, one with it replaced with a ^.

%`;|$
¶

Change the ;s back into newlines and space the results apart.

Answer 18

Perl 5 -0, 51 bytes

$_=<>;s/\s/P/g;s/v/{v,^}/g;say s/P|$/\n/gr for glob

Try it online!

Answer 19

JavaScript (Node.js), 80 73 68 bytes

f=([x,...y],g=c=>f(y).map(z=>c+z))=>x?g(x).concat(x>'a'?g`^`:[]):[y]

Try it online!

Answer 20

Python 3 - construct, 203 bytes

def f(a):
 b=[0]
 for l in a.split():b+=[b[-1]+l.count('v')]
 return'\n'.join(''.join(f"{k:b}".zfill(b[-1])[x:y]+'-\n'for x,y in zip(b,b[1:]))for k in range(2**b[-1])).replace('0','-v').replace('1','-^')

Try it online!

First try, not very small but works. There is no elegant string replacement in Python...

The First loop builts a mapping of lines to bit indices, i.e. for each line, the index of the first bit in a bit counter is stored. This is used for indexing the bit counter in the next loop.

The Second loop runs a binary counter, extracts the bits for each line and iteration and joins them. After joining everything together, it is translated back to the switch map format, using string replacement.

I guess, there is a more elegant way by reusing the input string instead of rebuilding it over and over again.

Edit: inspired by the Python 3.8 answer, here is a much shorter replacing version

Python 3 - replace, 123 bytes

def f(a):r=range;n=a.count('v');return'\n'.join(a.replace('v','{}').format(*('v^'[k&2**i>0]for i in r(n)))for k in r(2**n))

Try it online!

Answer 21

Ruby, 64 bytes

Returns an array. Gets numbers from \$1\$ to \$2^v\$ (where \$v\$ is the number of "v" in the input) and flips switches based on the \$v\$ least significant bits. This allows us to save a byte over iterating from \$0\$ to \$2^v-1\$, because the \$v\$ least significant bits in \$2^v\$ are all zero.

In Ruby, i[j] returns the jth bit of i starting from the least significant bit, aka it is equivalent to (i>>j)&1.

->s{(1..2**s.count(?v)).map{|i|j=-1;s.gsub(/v/){'v^'[i[j+=1]]}}}

Try it online!

Answer 22

Charcoal, 28 bytes

⪫ＥＸ²№θv⭆θ⎇⁼λv§v^÷ιＸ²№…θμv붶

Try it online! Link is to verbose version of code. Explanation:

   ²                            Literal 2
  Ｘ                             Raised to power
    №                           Count of
      v                         Literal `v`
     θ                          In input string
 Ｅ                              Map over implicit range
        θ                       Input string
       ⭆                        Map over characters and join
           λ                    Current character
          ⁼                     Equal to
            v                   Literal `v`
         ⎇                      Then
              v^                Literal `v^`
             §                  Circularly indexed by
                 ι              Outer index
                ÷               Integer divided by
                   ²            Literal 2
                  Ｘ             Raised to power
                    №           Count of
                        v       Literal `v`
                      θ         In input string
                     …          Truncated to length
                       μ        Inner index
                         λ      Else current character
⪫                         ¶¶    Join with newlines
                                Implicitly print

Answer 23

PHP, 93 bytes

for(;$j<1<<$x;$j+=print$s)for($x=0,$s=$argv[1];$i=strpos($s,v,$i+1);$s[$i]=$j&1<<$x++?'^':v);

Try it online!

Standalone program, input via command line.

Loop the number of possible permutations of the input string based on the number of v's. While counting up in binary, replace each binary 1 with a ^ and each binary 0 with a v in the input string.