# Brute-force the switchboard

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.

• nice first challenge! Jul 19 '19 at 17:51
• Hopefully, the "poor guy" knew about Gray code in order to only flip one bit between each combination. Jul 20 '19 at 12:00
• Time is our most precious asset, don't waste it in vain. Jul 20 '19 at 12:54
• Given the theme, I'm disappointed you didn't require an order that requires the least amount of toggles (e.g. 00->01->11->10 has 3 toggles while 00->01->10->11 has 4) -- Fellow brute force escaper Jul 20 '19 at 18:43
• @EricDuminil: if the mechanical switches were not buttons (and maybe even if), then most likely, the difference the time needed between switching one, two and three consecutive switches (which you could probably do almost simultaneously) wouldn't be large enough to offset the extra mental work to follow the Gray code. Jul 21 '19 at 15:26

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. • Ooh, I've been waiting for a purely functional answer, this really blew me away at how concise it was. Jul 20 '19 at 20:07 • @Rin'sFouriertransform I was pleased with how nicely mapM worked for this challenge, at first I had it formulated as sequence . map g but that can be expressed compactly as mapM id . map g and then I saw I could just mapM g – cole Jul 20 '19 at 20:27 • I think you can swap =='v' for >'-' Jul 20 '19 at 20:29 # 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~. # 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  • I've actually been scrambling through the Jelly code pages to try to figure out how the first answer has continually outgolfed every single other answer, almost always by a pretty good margin...would you care to explain how this works? Jul 20 '19 at 20:03 • @Rin'sFouriertransform I've added an explanation. Jul 20 '19 at 21:51 # 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).

# 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

• Anything with an outer-product inner product deserves +1.
Jul 21 '19 at 0:34

# K (ngn/k), 27 25 bytes

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


Try it online!

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

x,' zip with the original chars

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

• .. and here's me thinking I did alright in 44 bytes!
– mkst
Jul 20 '19 at 9:46

# 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/^.

# Java, 202197189 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.

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

• I'm pretty sure you have to include the function definition (String generate(String s) {...}) in your byte count. Here's a fixed/lambda version for 191 bytes. I did some minor golfing to shave off 3 bytes Jul 20 '19 at 2:44
• @BenjaminUrquhart OK, these are details of the "rules" that I'm not familiar with (I'm not golfing here sooo regularly). I thought that the actual { function body } should be relevant, because it does not matter whether you put it into a function that is static or not, and of course, if the declaration counts towards the score, one can convert it into a lambda expression. But that's what is done now, thanks for pointing this out. Jul 20 '19 at 12:31
• A few suggestions: 1. use ascii-codes, not chars (d=94). 2. Initialise i when you declare it. 3. Use i++<m instead of separate increment (need to modify the contents of the loop in one place, but this adds no cost). 4. Can you get away with (i&1<<j++)>0? 5. I don't think you need the {} for the inner for loop. 6. You can replace a[k]==d||a[k]==u with a[k]>45, I think. 7. Go with j=k=0. All that should remove 19bytes. Jul 20 '19 at 22:27
• @VisualMelon Some of these are the "classical golfing" approaches, and I already applied some of them. Whether or not they are applicable depends - I think that some {} are necessary, but I can have another look. The a[k]>45 may be a neat trick, however. Admittedly, I only wrote this to waste some time waiting for a meeting to start (hence the class name - this was intentional ;-)) but maybe I'll have another look - thanks in any case! Jul 20 '19 at 22:31
• @Marco13 indeed, they are classic tricks, but all applicable here specifically. I won't spoil the fun by giving you my 172 byte solution based on them (BTW, it think yours is 192, not 191, but I don't know how the lambda counting works: I'm opposed to it in any case). Jul 20 '19 at 22:33

# J, 41 40 24 bytes

[:>@,@{<@(,'^'$~'v'=])"0  Try it online! • very impressive. love the use of {. although i think [:>@,@{<@(,'^'$~'v'=])"0 would be slightly more fair since "Each output board should be of the exact same format as the input" and the input isn't boxed. Jul 20 '19 at 22:48
• @Jonah thanks. corrected.
– ngn
Jul 20 '19 at 23:02

# 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.

• A way more concise approach than mine, nice work! Jul 22 '19 at 20:49

# 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

# 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!

• Welcome to PPCG! 123 bytes using a similar idea. Jul 24 '19 at 0:19
• 119 bytes (previously wrong link in this comment). Jul 24 '19 at 1:01

# 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!

# 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


# 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

• ah, I was so focused on taking input in a much harder way that I neglected the ease of this one. Nice use of "[<-"! Jul 22 '19 at 17:27
• @Giuseppe: I'm not very satisfied by this solution... but I tried to generate the combinations in other ways (e.g. using binary conversion) but this ended up being the shortest. Jul 23 '19 at 11:57

# JavaScript, 88 bytes

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


Try it online!

• n>>=1 -> n/=2
– ngn
Jul 20 '19 at 10:51

# 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.

# Perl 5-0, 51 bytes

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


Try it online!

• Jul 20 '19 at 18:56
• Jul 20 '19 at 19:07
• Oh, basic tip: Using -n would have avoided the need for $_=<>; Jul 21 '19 at 11:27 # 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! # 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! # 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! # 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  # 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.