title: BalancE the UppercasE

text:
# Question
Title: BalancE the UppercasE
Oh, No!
the sentences are out of balance.
Quick! balance them.

---

A word is defined as follows:

> A sequence of letters \[A-Za-z\] separated by **any** non-letter character (\[0-9\] ~+- etc.)

A word is BaLanCeD if its capitalization is the same forwards as it is backwards.

Given a sentence with words, balance each word by capitalizing a letter on the right-hand side for each uppercase letter on the left-hand side, and the other way around. Do not make uppercase letters lowercase.

## Rules

* For each letter `n` chars from the beginning of a word, it and the letter `n` chars from the end of the word should both be made uppercase if either of them is upper case.
* All input will be printable ASCII (codepoints 32  to 126 `~`).

**No need to balance if:**

* The capital is in the middle of a term (word) (equal amount of letters on each side)
* No capitals are present in the term

**Example:**

```
eeeeE → EeeeE
eEeee → eEeEe
eeEee → eeEee
Eeee. → EeeE.
{EEee}1EEeEEEeeeeee → {EEEE}1EEeEEEEEEeEE

```

**TesT CaSeS:**

```
It was the first new century. →
IT was the first new century.

IiIIiiIIiiiI Ii iI iiiI iiii iIi. →
IiIIIIIIIIiI II II IiiI iiii iIi.

I sueD the airport for misplacing my Luggage. – I lost my Case. →
I SueD the airport for misplacing my LuggagE. – I lost my CasE.

The Policemen  CraCked THE CaSE of the lost cocaIne. →
ThE PolicemeN  CraCkeD THE CASE of the lost coCaIne.

JUST IN CASE. →
JUST IN CASE.

If(!1){ /\hElloBinOLIngo}elsE{ print( 'bOn aPPetit')} →
IF(!1){ /\hElLOBinOLInGo}ElsE{ print( 'bOn aPPeTIt')}

xK/TH"E7k['VyO%t>2`&{B9X.8^$GWc=!+@ 3Us}]JFM)jbuI,-:alPw*Qvpq5zi\Z(_n1dC~?<;fDAm0SR|eYg6#rN4Lho →
XK/TH"E7k['VyO%t>2`&{B9X.8^$GWC=!+@ 3US}]JFM)JbuI,-:aLPw*QvpQ5zi\Z(_n1DC~?<;fDAm0SR|eYg6#RN4LhO

Foo_bar →
FoO_bar

```

(the " →" will not be included in the input)

This is codegolf, so attempt to achieve least amount of bytes

# Answer
> 8 votes
# JavaScript (Node.js),  ~~76~~  72 bytes

*Saved 2 bytes thanks to @tsh*

```
s=>s.replace(/[a-z]+/gi,w=>Buffer(w).map((c,i,a)=>c&=a[w.length+~i]|95))

```

Try it online!

### Commented

```
s =>                     // s = input string
s.replace(               // replace in s:
  /[a-z]+/gi,            //   match all words in a case-insensitive way
  w =>                   //   for each word w:
    Buffer(w)            //     turn it into a Buffer
    .map((c, i, a) =>    //     for each character c at position i in this array a[]:
      c &=               //       bitwise AND of c with:
        a[w.length + ~i] //         the counterpart character taken from the end of
                         //         the word
        | 95             //         OR 0b1011111
                         ///        (all letter bits except the lowercase bit)
    )                    //     end of map()
                         //     implicit coercion of the Buffer to a string
)                        // end of replace()

```

# Answer
> 5 votes
# Jelly, 18 bytes

```
=ŒsŒgṁ@µŒu=ŒuṚTƲ¦)

```

A full program that takes a string argument and prints the result.

**Try it online!**

### How?

```
=ŒsŒgṁ@µŒu=ŒuṚTƲ¦) - Main Link: list of characters (S)
 Œs                - swap-case (only affects alphabetic characters)
=                  - (S) equals (that); vectorises
   Œg              - group runs of equal elements
     ṁ@            - (S) mould-like (that) -> list of "words"
                       (any single non-alphabetic character is now a word)
       µ         ) - for each (word in that):
                ¦  -   sparse application...
               Ʋ   -   ...to indices: last four links as a monad:
           Œu      -       upper-case (word)
          =        -       (word) equals (that); vectorises
             Ṛ     -       reverse
              T    -       truthy indices
        Œu         -   ...action: upper-case (the character at the index)
                   - implicit, smashing print (just prints the characters in the list of lists)

```

Seems a bit long to me:

* The partitioning atoms (`œṖ`, `œṗ`, `œP`, and `œp`) don't seem to help much here even though it seems like they should.
* Perhaps there is a way to shorten code by zipping (`"`) a dyadic function with the reverse of each (`U`)?

# Answer
> 5 votes
# C (gcc), ~~132~~ \\$\cdots\\$ ~~115~~ 114 bytes

Saved ~~3~~ 11 bytes thanks to AZTECCO!!!

```
f(s,e)char*s,*e;{for(;!isalpha(*s);++s);for(e=s;isalpha(*++e););for(*e&&f(e);s<e;++s)*--e&*s&32||(*s&=95,*e&=95);}

```

Try it online!

Modifies the input string to have in-word balanced capitalisation.

### Explanation

```
f(s,e)char*s,*e;                           // function taking a string
{                                          // parameter s and also declares
                                           // e as a string pointer
  for(;!isalpha(*s);++s);                  // loop until s pointes to the
                                           // beginning of the next word
  for(e=s;isalpha(*++e););                 // loop until e pointes to one
                                           // past the end of that word
  for(                                     // loop over this word
      *e&&f(e);                            // while e points to one past
                                           // the current word
                                           // recursively handle the next
                                           // word if we're not at the end
               s<e;                        // loop while s is before e
                   ++s)*--e                // bump s and e towards the middle
                   ++s)                    // bump s forwards at the end of
                                           // each loop
                       *--e                // bump e backwards at the
                                           // beginning of each loop
                       *--e&*s&32||        // if both characters aren't
                                   (       // both lower case then
                                    *s&=95 // make the first character upper
                                   ,       // case regardless of its case
                                    *e&=95 // and also make the second
                                           // character upper case
                                   );      // regardless of its case
}                                          //

```

# Answer
> 5 votes
# Perl 5 `-p`, 60 bytes

```
s|\pL+|$i=0;join'',map$F[--$i]=~/[A-Z]/?uc:$_,@F=$&=~/./g|ge

```

Try it online!

# Answer
> 4 votes
# Husk, ~~16~~ 13 bytes

```
ṁṠzo?aID↔ġo¬√

```

Try it online!

```
            ġo¬√    # first ġroup the input into sublists (words) according to whether the elements are/aren't letters
ṁ                   # now map across this list of words and concatenate the results into a string, with the function
 Sz        ↔        # zip together each word and its reverse using
   μ      )         # 2-argument lambda function:
    ?  D⁰           # if arg 1 is uppercase
     a   ²          # return uppercase of arg 2
      I             # otherwise return arg 2 unchanged

```

# Answer
> 3 votes
# Stax, ~~19~~ 16 bytes

```
Å;√∩b₧Aµ╗∞q«J,╕*

```

Run and debug it

Replaces each match of `[A-Za-z]+` using the ruleset.

-3, borrowing the untruth idea from Jonathan Allan's answer.

## Explanation

```
V^{c{96<mr:1{]^}&}R implicit input of string
V^                  regex: "[A-Za-z]+"
  {c{96<mr:1{]^}&}R replace each occurrence with the following regex:
   c                copy the match
    {96<m           boolean array for uppercase letters
         r:1        reverse and take truthy indices
            {]^}&   uppercase the match at those indices

```

# Answer
> 3 votes
# Ruby, ~~73~~ 72 bytes

```
->s{s.gsub(/[A-Z]+/i){|a|r=0;w='';a.bytes{|b|w<<(a[r-=1]>?Z?b:b&95)};w}}

```

Try it online!

# Answer
> 3 votes
# Retina 0.8.2, 62 bytes

```
T`l`L`.(?=([A-Za-z])*)(?<=(?=(?>(?<-1>.)*)[A-Z])(?>[A-Za-z]+))

```

Try it online! Explanation:

```
.(?=([A-Za-z])*)

```

Count the number of letters following the match.

```
(?<=(?=)(?>[A-Za-z]+))

```

Skip back to the beginning of the word, and then...

```
(?>(?<-1>.)*)

```

... match the same number of characters, ...

```
[A-Z]

```

... followed by an uppercase letter.

```
T`l`L`

```

Uppercase matching letters.

# Answer
> 3 votes
# Red, ~~155~~ 152 bytes

```
func[s][a: charset[#"A"-#"Z"#"a"-#"z"]parse s[any[change copy w some a(repeat
i d: length? w[if w/:i < #"["[n: d - i + 1 w/:n: w/:n and 95]]w)| skip]]s]

```

Try it online!

# Answer
> 3 votes
# Python 3, ~~236~~ ~~230~~ 217 bytes

My first answer in Code Golf!

Edit: *-6 bytes thanks to @movatica*

*-6 bytes thanks to @Danis*

*-7 bytes thanks to @Alex bries*

```
s=input()+'_'
o=''
i=0
for j in range(len(s)):
 p=s[j]
 if p<'A'or'a'<p<'Z'or p>'z':u=[c<'a'for c in s[i:j]];b=[x|y for(x,y)in zip(u,u[::-1])];o+=''.join([c,c.upper()][x]for(c,x)in zip(s[i:j],b))+p;i=j+1
print(o[:-1])

```

Try it online!

Commented code (*original*):

```
import re

```

...import the regex module to find non letter characters

```
s=input()+'_'

```

...take the imput from the console, and append a non letter character to complete the last iteration in the loop

```
o=''

```

...initialize the output string

```
i=0

```

...initialize the index to find the start of each new identified word

```
for j in range(len(s)):

```

...loop on the characters of the input

```
 if re.match('[^A-Za-z]',s[j]):

```

...identify a non letter character that separates words

```
u=[ord(c)<97for c in s[i:j]];

```

...list of boolean values corresponding to the letters in the word: True if uppercase

```
b=[x|y for(x,y)in zip(u,u[::-1])];

```

...reverse the list of boolean values, and apply `or` elementwise to obtain the symmetric list of uppercase characters

```
o+=''.join([[c,c.upper()][x]for(c,x)in zip(s[i:j],b)])+s[j];

```

...builds the output string: convert to uppercase according to the symmetric list built before; add the non letter character

```
i=j+1

```

...update the starting index of the next word.

```
print(o[:-1])

```

...prints the output balanced string (discarding the added last character)!

# Answer
> 3 votes
# Perl 5 (-p), 32 bytes

```
s/\pL+/$&&~reverse~$&&$"x"@+"/ge

```

The trick, to uppercase, is to AND characters with the negation of space.

How it works

For each sequence of letters

bitwise NOT

bitwise AND with space character repeated (at least the size of the match, here majorant is the position after match @+)

Reverse

bitwise negate

bitwise AND with matched.

Try it online!

# Answer
> 2 votes
# 05AB1E,  ~~15~~  13 bytes

-1 thanks to Makonede! (Duplicate-TOS and then reverse-TOS has a one-byte built-in, `Â`.)
-1 thanks to Kevin Cruijssen! (Take a list of characters.)

```
.γa}εÂ.uÅÏu]˜

```

**Try it online!**

### How?

```
.γa}εÂ.uÅÏu]˜ - (accepts a list of characters)
.γ }          - group by:
  a           -   is alphabetic?
    ε         - for each:
     Â        -   push a copy and then push a reversed copy
      .u      -   is upper-case? (vectorises)
        ÅÏ    -   apply at truthy indices (of that, to the forward copy):
          u   -     upper-case
           ]  - } } (close all loops)
            ~ - flatten

```

# Answer
> 2 votes
# Julia, 76 bytes

```
n->replace(n,r"[a-zA-Z]+"=>x->(L=length(x)+1;map(c->c-32(x[L-=1]<'['<c),x)))

```

Try it online!

# Answer
> 2 votes
# Charcoal, 29 bytes

```
Ｆ⁺Ｓψ¿№α↥ι⊞υι«⭆⮌⮌υ⎇№α⊟υ↥κκ¿℅ιι

```

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

```
Ｆ⁺Ｓψ

```

Loop over the input with a null terminator.

```
¿№α↥ι

```

If the current character is a letter, ...

```
⊞υι«

```

... push it to the predefined empty list, otherwise:

```
⭆⮌⮌υ⎇№α⊟υ↥κκ

```

Loop over a copy of the saved letters, retrieving them in reverse order each time, and uppercasing the copy if the reverse order letter is uppercase.

```
¿℅ιι

```

Print the non-letter unless it's the null terminator.

# Answer
> 2 votes
# Java, 320 Bytes

```
s->java.util.regex.Pattern.compile("[a-zA-Z]+").matcher(s).replaceAll(m->java.util.stream.IntStream.range(0,m.group().length()).mapToObj(i->(Character.isUpperCase(m.group().charAt(m.group().length()-1-i))?Character.toUpperCase(m.group().charAt(i)):m.group().charAt(i))+"").collect(java.util.stream.Collectors.joining()))

```

Try it online!

## Explanation

```
s->java.util.regex.Pattern.compile("[a-zA-Z]+").matcher(s)//match words
  .replaceAll(m->//replace each word, m is MatchResult, m.group() is current word
     java.util.stream.IntStream.range(0,m.group().length())//iterate over indexes of word
       .mapToObj(i->(Character.isUpperCase(m.group().charAt(m.group().length()-1-i))
       //check if character at reflected index is uppercase
    ?
  Character.toUpperCase(m.group().charAt(i))//make uppercase
  :m.group().charAt(i)) //do not modify
   + "" //concatenate with empty string to force result to be a String
  ).collect(java.util.stream.Collectors.joining()))//collect as single String

```

# Answer
> 2 votes
# , 60 bytes

```
[:;]<@((+.&(91>3&u:)|.)`(,:toupper)});.1~1,2|@-/\e.&Alpha_j_

```

Try it online!

Well this is shockingly verbose for J. Surely I am missing some better alternatives, but this is what I have for now...

# Answer
> 2 votes
# Python 3, ~~153~~, ~~149~~, ~~148~~, 110 bytes

*Using `re.sub` is even more elegant than re.finditer...*

```
lambda s:re.sub('[a-zA-Z]+',lambda w:''.join([c,c.upper()][d<'a']for c,d in zip(w[0],w[0][::-1])),s)
import re

```

Try it online!

# Answer
> 2 votes
# AWK, 113 bytes 141 bytes

```
{for(b=1+split($0,l,"[ ]");--b;$b=e){a=split(toupper(m=l[b]),c,d=e=x);for(split(m,f,d);a;a--){if(f[++d]==c[d])f[a]=c[a];}for(;d;)e=f[d--]e}}1

```

Try it online!

*The code got longer to address a bug related to whitespace parsing as noted by Dominic van Essen.*

This isn't all that short, but AWK isn't well suited to this challenge (as far as I can tell) so I think it's worth posted anyway.

Here's how it works...

The first `for` loop processes each commandline argument in reverse order. First it has to break the arguments into words explicitly, since TIO doesn't provide a way to set `RS` and `ORS` variables easily.

```
b=1+split($0,l,"[ ]")

```

which sets variable `b` to the number of space delimited words found, and stores the array of words (some of which might be empty strings) in variable `l`. The `1+` is necessary to keep the code from skipping the last word.

then at the top of each loop,

```
--b

```

the code decrements `b`. The words in the array are processed in reverse order to avoid having to use another variable.

The body of the loop consists of three statements, the first one is:

```
a=split(toupper(m=l[b]),c,d=e=x)

```

which does a couple of things.

* converts the current argument `l[b]` to upper case
* splits that word into a character array, assigns that to variable `c`
* sets variables `d` and `e` to an empty string
* set variable `a` to the number of characters in the argument
* stores the untranslated value of the current argument in variable `m`

The second statement is another loop, checking character by character and translating to uppercase as needed. It does that by initializing the loop with:

```
split(m,f,d)

```

which converts the current commandline argument to a character array, stored in variable `f`. At this point `f` has the original characters, and `c` has the same characters translated to uppercase.

The loop condition and "end of loop" action cause the code to iterate `a` times, which is the number of characters in the current argument.

The body of this second loop is single statement:

```
if(f[++d]==c[d])f[a]=c[a]

```

which translates the paired character to uppercase if the character we're checking is already uppercase. The loop decrements `a` and increments `d` each iterations, which keeps the pairing in sync.

The third statement in the body of the outer loop, is essentially a "join" operation concatenating the characters in the translated character array.

```
for(;d;)e=f[d--]e

```

The only trick here is using the `d` variable as the iteration control, since it was incremented up to the length of the commandline argument in the previous loop. Also working backwards means we can use `f[d--]e` without having to use a space between them since the closing bracket separates the variables.

Then the "end of loop" action on the outer loop assigns the re-assembled string to the current commandline argument.

```
$b=e

```

And all that's left to do is add a "truthy" test without any action to print everything.

```
1

```

# Answer
> 1 votes
# Java (JDK), 130 bytes

```
a->{for(int i=0,l=a.length,c,s,e;i<l;i++){for(s=i;i<l&&(c=a[i]&95)>64&c<91;i++);for(e=i;s<e;a[e]&=c)a[s]&=c=a[s++]^a[--e]^32|95;}}

```

Try it online!

## Credits

# Answer
> 1 votes
# Japt, 30 bytes

```
òÈ+Y è"%L"
®íZmr"%a" ÔÏ?Xu:XÃc

```

Try it online!

I'm not happy with this, but I haven't actually been able to find something better. Inputs and outputs as an array of characters.

Explanation:

```
òÈ+Y è"%L"
ò                      # Partition the input between pairs of characters where truthy:
 È+Y                   #  Join the two characters into a string
     è"%L"             #  Count how many are not in [A-Za-Z]
                       # Implicitly store as U

®íZmr"%a" ÔÏ?Xu:XÃc    #
®                      # For each word:
  Zmr"%a"              #  Replace lowercase letters with ""
          Ô            #  Reverse it
 í         Ï     Ã     #  Pair each with the original letter at that index
            ?          #  If the modified array has anything other than "":
             Xu        #   Replace the original letter with upper-case
               :X      #  Otherwise leave it unchanged
                  c    # Flatten all the words back into a single array of chars

```

# Answer
> 1 votes
# PowerShell, ~~91~~ 82 bytes

```
$args-replace'[a-z]+',{-join(&{($w="$_")|% t*y|%{[char]($w[--$i]-bor95-band$_)}})}

```

Try it online!

where:

* `&{` creates a new context each contains `$i=0`
* `-bor` is bitwise `or`, `-band` is bitwise `and` have inspired by the Arnauld's answer

# Answer
> 0 votes
# Uiua SBCS, 19 bytes

```
⍜⊜□⍚(⍜▽⌵↥⇌.=1±.)⌵±.

```

Try it!

```
⍜⊜□⍚(⍜▽⌵↥⇌.=1±.)⌵±.
                  .  # duplicate input
                ⌵±   # letter mask
⍜⊜□⍚(          )     # under partition (map over words, leave rest intact)
              .      # duplicate word
           =1±       # uppercase mask
        ↥⇌.          # mirror it
     ⍜▽⌵             # capitalize letters given by mask

```

---
Tags: code-golf, string
---


title: Output two numbers (Robbers' thread)

text:
# Question
Title: Output two numbers (Robbers' thread)
> This is the robbers' thread to a challenge. Click the link to find the cops' thread.

In the cops' thread of this challenge, answerers will be writing programs which output two numbers, \\$x\\$ and \\$y\\$. As robbers, your goal will be to crack their submissions. To do this, you find a program in the same language as a cop's program which outputs a number in between \\$x\\$ and \\$y\\$, and is the same length as or shorter than the cop's program. Your program must use the same output method as the cop's submission.

You submit that program here and notify the cop in a comment on their answer.

For every answer you crack here you get 5 points. As an extra incentive you will gain an additional point for every byte shorter your program is than the cop's. If your program is the same length, that is fine; you still get 5 points.

The winner is the person with the highest total score across all answers.

# Answer
> 15 votes
# Malbolge, 6 bytes, cracks Kamila Szewczyk's answer

```
(&<`q#

```

Try it online! (or try it here to avoid timing-out)

Outputs 2.

**Explanation**.
The goal is to output the ASCII character "`2`" in a 7-byte or less program.

Malbolge code & data occupies the same memory space. When a Malbolge program is loaded, the last two single-byte instructions act as 'seeds' that determine how the remaining memory is initialized (in a deterministic but rather uncontrollable fashion). So if we try to construct 5 command/byte programs that use the contents of the memory to generate the ASCII encoding for "`2`", we can try different combinations of the remaining 2 commands/bytes to try to find one that gives the correctly-initialized memory to achieve this. There are 8 valid Malbolge commands (and any other byte in the program will generate an error upon loading), so this gives us 8x8 combinations to try per 5 byte program. This is obviously less than the 1/256 chance of 'hitting' the ASCII character "`2`" in any particular byte, so we'll probably have to try more than one program.

Each Malbolge command self-modifies immediately after execution, making re-use rather difficult. So here we try only single-pass programs, without any attempt to loop. We will need to use the commands `j` (set the data pointer), `<` (write an ASCII value to the output), and (probably) `v` (end the program). This gives us room for 2 more data-altering commands in within the 5-byte limit, so we can try combinations of `*` (rotate) and `p` (tritwise OP operation), as well `o` (no operation; but in Malbolge this changes the data pointer as a side effect so it can also affect the output).

Unfortunately, after trying all 64 combinations of the final two bytes across the Malbolge programs `jpo<v..`, `jop<v..`, `ojp<v..`, `jpp<v..`, `jppp<v.`, `jpppp<v`, `j*o<v..`, `j*p<v..`, `j*pp<v.` and `j*ppp<v` (where `.` represents any of the 8 Malbolge commands), we can only generate the output numbers 0, 1, 3, 5, 6, 7, 8, 9. At this point it seems likely that Kamila Szewczyk may have used a similar approach, and therefore hoped that generating the character "`2`" in 7 bytes or less is impossible...

But: what about shorter programs that omit the `v` (end the program) command? These allow the memory to be initialized differently, and so we can maybe find a combination that enables output of "`2`"... but the Malbolge interpreter will now continue reading bytes from the rest of the initialized memory and executing them as commands, with rather uncontrollable consequences! Still, if it hits a `v` (end of program) before it hits a `<` (write output), that could be Ok: so let's try it!

After some searching, we find that `j*p<..` is indeed able to initialize the memory to output "`2`", using two different suffix combinations: when test-run, `<j` unfortunately keeps running and outputs an additional "`2L`" before stopping, but `/j` stops after the "`2`". It's a crack!

To load into Malbolge, the final program - `j*p</j` \- must finally be encoded using a series of operations (see the spec) to yield the final loadable code of `(&<`q#`.

# Answer
> 9 votes
# , 4 bytes

```
2e98

```

Try it online!

Not much fun but the range makes it cracked

# Answer
> 9 votes
# Vyxal, ~~26 18~~ 14 bytes (88 bytes saved)

Crack of @lyxal's vyxal cop program

```
k×:\(+33*\↵+Ė›

```

Try it Online!

output lowest bound +1

(first time doing vyxal, tell me if I did something incorrectly)

## Explanation

```
k×         Push 2147483648 onto the stack
           => [2147483648]
:          Duplicate the stack
             => [2147483648, 2147483648]
\(+        Concatenate the last element of the stack with `(`
             => [2147483648, '2147483648(']
33*        Multiply by 33 the string on top of the stack
             => [2147483648, '2147483648(21 ... 8(2147483648(']
\↵+        Add `↵` to the string on top of the stack
             => [2147483648, '2147483648(21 ... 8(2147483648(↵']
Ė          Evaluate as vyxal code the last element of the stack (see the cop thread)
             => [ <lowest bound> ]
›          Add 1 to the result
             => [ <lowest bound +1> ]
           implicit output

```

# Answer
> 8 votes
# Brachylog, 5 bytes (0 bytes saved), 20922789888

```
16ḟ↔↔

```

Outputs \\$20\text{,}922\text{,}789\text{,}888\\$.

Cracks @Fatalize's Brachylog Cop answer, which is also 5 bytes and the range \\$14\text{,}159\text{,}265\text{,}359\\$ to \\$61\text{,}803\text{,}398\text{,}875\\$.

Try it online.

**Explanation:**

```
16ḟ    # Push the factorial of 16: 20922789888000
   ↔   # Reverse (but remain an integer): 88898722902
    ↔  # Reverse back: 20922789888

```

# Answer
> 6 votes
# Excel, 6 bytes, cracks Luke Dunn's answer

```
=1E250

```

Try it online!

# Answer
> 4 votes
# JavaScript (Node.js), 22 bytes

```
x=>'9'.repeat(1e7-1)-1

```

Try it online!

This cracks l4m2's cop.

Works only in theory. The string in the answer, with `9999999` golfed to `1e7-1`, minus 1, which coerces it to a number.

---

# JavaScript (Node.js), 22 bytes

```
x=>'909'.repeat(1e7/3)

```

Try it online!

Works in reality.

This one exploits the fact that the repetition count is rounded down.

# Answer
> 3 votes
# brainfuck, 15 bytes (10 bytes saved), cracks mathcat's answer

```
-[>+<-----]>++.

```

Try it online!

# Answer
> 3 votes
# pxeger's zsh, 13 bytes

```
tr<=z3 -c 0 1

```

Try it online!

Cracks https://codegolf.stackexchange.com/a/242150/3852

# Answer
> 2 votes
# Octave, 6 bytes, cracks robbie crockett's first answer

```
28^213

```

Try it online!

Found by a brute force search of `n` where `log(1.7e308,n)` is very close but less than an integer so that `n^ceiling(log(1.7e308,n))` is not too large.

# Answer
> 1 votes
# Seed, 4695 bytes (96 byte save), \\$9^{999999999999999}\\$

```
48 [encoded data, 4692 characters]

```

Nothing clever on my part I stole this from the answer's edit history.

# Answer
> 1 votes
# Python 3, 19 16 bytes (saves 22 25 bytes)

```
print(3*10**456570)

```

Cracks DialFrost's cop answer... I just did a bunch of trial and error to get this lol.

Try it online. Verify it's between the two numbers

# Answer
> 1 votes
# !@#$%^&\*()\_+, 6 bytes, cracks Fmbalbuena's answer

```
~(#)

```

Try it online!

---
Tags: number, cops-and-robbers, busy-beaver
---


title: 3D Hide & Seek Word Puzzle

text:
# Question
Title: 3D Hide & Seek Word Puzzle
# Challenge

Create a 3D word puzzle where the cube's dimensions match the length of the input word. The uppercase word (A-Z) must be validly placed within the cube in one of the fixed orientations: horizontally, vertically, or diagonally. The program should randomly place the hidden word and fill the rest of the cube with random letters.

**Input**

```
WORD

```

**Output**

```
Display the cube (n x n x n) layer by layer, where n is the WORD's length.

```

# Examples

**UP**

**AND**

**DOWN**

**APPLE**

**ORANGE**

**CODEGOLF** (Can you find it?)

```
N Y R Z O F K G   Y G B V E T P M   O J F K Y O O K   O Z N Q F A R P   M X E T N O I Y   F H C U O F Z A   G V A V O O F B   B V K U O V L F
W Y L W U H H K   Z M Z X D R K Q   G D D A B I D F   P Y G U I D L I   J Y D O M D Q W   F H B Q Q N B B   T A C F J Q L K   H R Y R Y B Z Q
L F C D Z B Z W   L E A J O F F J   Z O X Q G A R C   W N N W Y Z S U   S G E V T A C F   K F E O R O N V   K D G Z N W O P   L I W W J L C U
K L Z Q M A G C   M R Q E F M O I   O K T K T U A U   S E X A Y K C D   N J D V G E S G   X O F P T S F I   H Z B X E X U T   X R Q G V P Q O
B H F C J P Y A   P I Z G R X N A   A W Z H A Z H V   Q X T E T B Z A   Q A V I Z H G D   E H N J L G G W   V K A O Q U S G   N K M M X R G Z
B Q K R Y O R I   O J C Q K C P F   F U D R M U J G   E K B F A A C I   K G P O B M N E   M P M B K X X T   V B V N Z O R P   K N Q N J B M D
M L R C O U C F   A O H U H R E P   M L E T B F R Y   W J S U C Y A N   M X S W E C C X   C U F U V Q U H   J C Z W Y E J S   Z D C U I R F Z
C H D I M M C W   F W G N I I Z U   C X W Q M C O N   Y O W K X E Z J   U G Y U W Q V V   C N B T A T E Z   W C X Z E O W Z   N S C J P V X X

```

# Answer
# Python 3, ~~226~~ ~~213~~ ~~227~~ ~~222~~ 219 bytes

```
from random import*
def f(w):
 W=len(w);G=eval('[[[chr(randint(65,90))'+f"for _ in' '*{W}]"*3);l,a,b=map(randrange,(W,W,15))
 for n in range(W):G[[n,l][b&2>0]][[a,n][b!=4]][[a,n,n,W-n-1][b//4]]=w[::b%2or-1][n]
 return G

```

Try it online!

* *-13 bytes* by replacing `randint` with `randrange`
* *+14 bytes* by implementing the reverse of a word
* *-5 bytes* by creating a `b` variable to store `d`, `o` and `i`, and by using `eval`
* *-3 bytes* by removing the `randrange` alias, and inlining the `r` variable

A function that receives a word \\$w\\$ and returns a 3x3x3 matrix composed of lists.

To see where the word is, change `chr(65+g(26))` to `chr(97+g(26))`.

---

**How does it work?**

The `g`enerator stores an instance of the `random.randrange` function.

The `r`ange stores the numbers from 0 to until the length of the `w`ord, exclusive.

We initialize the `G`rid to random uppercase letters (`chr(65+g(26))`).

We initialize three variables with random values:

* `l`ayer: define the index of the layer the word will be written (UP: layer 1, APPLE: layer 2); this variable is ignored if the word is spread across layers
* `a`xis: define the index of the axis the word will be written (AND: axis 1, DOWN: axis 0, APPLE: axis 0); this variable is ignored if the word is set diagonally
* `b` a 4-bits integer, where
    + if the first bit is 0, the word will be put right-to-left (in reverse); otherwise, left-to-right
    + if the second bit is 0, the word will spread across layers (see AND, DOWN and ORANGE test cases); otherwise, it will be contained in a single layer (see UP and APPLE test cases)
    + if the third and fourth bits are `00`, the word will be set horizontally (AND and DOWN test cases); if `01`, the word will be set vertically (APPLE test case); if `10`, the word will be set diagonally-forward (UP and ORANGE test cases); if `11`, the word will be set diagonally-backward (see CODEGOLF test case).

Then, for each character of the `w`ord, we update the `G`rid doing some arithmetic based on `l`, `a` and `b`.
> 3 votes

# Answer
# Charcoal, 56 bytes

```
Ｗ⁼⌊υ⌈υ«≔⁻Ｅ³‽⁺²Ｌθ²υ≔ＥθＥυ⎇‹μ⁰⎇⊕μ⁻⊖Ｌθλλμυ»ＥθＥθ⭆θ§⁺θ‽α⌕υ⟦κμξ

```

Try it online! Link is to verbose version of code. Enter the word in lower case if you want to make it obvious where it ended up. Explanation:

```
Ｗ⁼⌊υ⌈υ«

```

Repeat until a suitable word placement is found.

```
≔⁻Ｅ³‽⁺²Ｌθ²υ

```

For each axis, either select a fixed index from `0` to the length of the word, or `-1` to spread the word in the forward direction along that axis, or `-2` to spread it in the reverse direction (so for example `-2, -2, -2` would result in the word written in reverse along the main diagonal).

```
≔ＥθＥυ⎇‹μ⁰⎇⊕μ⁻⊖Ｌθλλμυ

```

Use the randomly selected indices to generate a list of coordinates of each letter of the word.

```
»ＥθＥθ⭆θ§⁺θ‽α⌕υ⟦κμξ

```

Output the cube, but selecting the letter from the word instead of a random letter if the current coordinates are from the selected list.
> 2 votes

# Answer
# JavaScript, 239 bytes

```
f=(w,W=[...w],r=n=>n*Math.random()|0,d=[0,1,2].map(_=>r(3)-1),o=d.map(x=>[r(L=w.length),L-1][-x]|0),p=[],g=n=>n--?W.map((_,i)=>g(n,p[n]=i)):W.find((_,j)=>!o.some((x,k)=>x+j*d[k]-p[k]))||String.fromCharCode(65+r(26)))=>/1/.test(d)?g(3):f(w)

```

Try it online!

Creates a 3D array.

It works by choosing a random 3D direction vector \\$d\\$, where each axis is -1, 0, or 1. (If it gets all 0s try again.) Based on the direction, it chooses a random origin point \\$o\\$, for each axis \\$n\\$:

$$ o\_n = \begin{cases} L-1 &\text{if }d\_n = -1\\ R(0,L) &\text{if }d\_n = 0\\ 0 &\text{if }d\_n = 1\\ \end{cases} $$

Where \\$L\\$ is the length of the input word, and \\$R(a,b)\\$ is a random integer in \\$\[a, b)\\$.

It doesn't guarantee that the word appears only once.

### Ungolfed:

```
f = (w, // the input word
     W = [...w], // split word into array - this'll be handy later
     r = n => n * Math.random() | 0, // a handy random function
     d = [0,1,2].map(_ => r(3) - 1), // pick a random direction
     o = d.map(x => [r(L=w.length), L-1][-x]|0), // pick a random valid starting point
     p = [], // place to store current point
     g = n => // a recursive function to create the grid - taking n = dimension
       n-- // reduce the dimension and check if zero
         ? W.map((_, i) => g(n, p[n] = i)) // if >0 go deeper, recording in p
         : W.find((_, j)=> !o.some((x, k) => x + j*d[k] - p[k])) // if in word, use its letter
               || String.fromCharCode(65 + r(26)) // else a random letter
) => d.some(x => x) // check if direction is valid (not [0,0,0])
  ? g(2) // valid - create the grid
  : f(w) // invalid - try again :(

```
> 1 votes

# Answer
# C (gcc), ~~655~~ ~~542~~ ~~446~~ 437 bytes

*-105 bytes, thanks to @ceilingcat*

To disable the word hint, change `w[i]|32` to `w[i]|0`.

```
#define r rand()
f(w,s)char*w;{char*u=calloc(s*s,s);int x,y,z,a,b,c,p,i=s/2,l,m,n;if(r%2)for(;i--;)w[i]^=w[s+~i]^=w[i]^=w[s+~i];do for(x=r%s,y=r%s,z=r%s,a=r%3-1,b=r%3-1,c=r%3-1,p=a|b|c,i=0;i<s&&p;p*=l>=0&m>=0&n>=0&l<s&m<s&n<s)l=x+i*a,m=y+i*b,n=z+i++*c;while(!p);for(i=s;i--;)u[((x+i*a)*s+y+i*b)*s+z+i*c]=w[i]|32;for(;y=++i<s*s*s;)u[i]=u[i]?:65+r%26;for(;y<s;y+=puts(""))for(z=0;z<s;z+=printf(" "))for(x=0;x<s;)putchar(u[x++*s*s+y*s+z]);}

```

Try it online!
> 0 votes

---
Tags: code-golf, random, 3d, word-search
---


title: Program ordinals and omega squared

text:
# Question
Title: Program ordinals and omega squared
A program ordinal is a (possibly transfinite) ordinal which can be assigned to programs in some language depending on their output.

To be more specific:

* Strings that give no output have ordinal 0
* Programs that output a program of ordinal n have ordinal n+1
* Programs P0 outputting multiple programs P1, P2... Pn have ordinal S, where S is the supremum of the set of program ordinals corresponding to the programs P1, P2... Pn

Your goal is to create the shortest possible program with program ordinal ω\*ω, also writable as ω2 or omega squared.

Output is required for a program. As well as this, the output must go through STDOUT or closest equivalent.

All programs printed by your program must be delimited by any string, so long as the delimiter is always the same. (`acbcd` and `accbccd` are allowed, but not `acbed`) These delimiters must be the only output other than the programs themselves, unless your language must output trailing characters.

Here is a program-ordinal ω program created in pseudocode, which generates programs of the form "exit, print(exit), print("print(exit)")...:

```
x=exit
loop{
print(x)
x='print(#x)'
}

```

Within each iteration of the loop, x is printed and then wrapped in print() (exit becomes print(exit)). # is put before x in pseudocode to indicate that it is the variable x and not the actual alphabetical character x.

The shortest program (measured in bytes) which has program ordinal ω2 wins. Have fun.

# Answer
> 1 votes
# Mathematica, 38 bytes

```
Nest[Nest[HoldForm@*Print,#,∞]&,,2]

```

Thinking process:

```
y=w="x=0;Do[Print[x=\"Print[\"<>ToString[x,InputForm]<>\"]\"],∞]";Do[Print[y=StringReplace[w,"0"->ToString[y,InputForm]]],∞]

```

This first solution is the same as the other solutions, it is a port of Surculose Sputum's answer, so I *think* it is correct. ToString\[x,InputForm\] sanitizes a string to be fed into it's own print statement. w stores the program that outputs the 0,1,2,3,... or the first ω, and y stores the program fed into itself n times that outputs ω+1,ω+2,ω+3..., when looped gives ω\*ω.

But that got me thinking, all that nested loop does, is, well, Nest. Which is a function in Mathematica, and Mathematica also can output "held" code, meaning no handling strings. Which means I could change w to

```
w="Nest[HoldForm@*Print,0,∞]"

```

Which makes w hold a program that doesn't have a loop for n=0,1,2,3... , but has ω more directly inside it by just holding prints. Alternatively NestList would return the same n as the original program, but why waste time with printing 1, and then 2, and then 3, when we can just print a program ω.

But if I do that for the first part, what's stopping me from doing that to the last part?

```
Nest[HoldForm@*Print, Nest[HoldForm@*Print, 0, ∞], ∞]

```

Well, now we have that ω2 program we wanted, but it looks a bit... referential? Like it's code is nesting itself. Nesting nests time!

```
Nest[Nest[HoldForm@*Print,#,∞]&,0,2]

```

That looks very nice. And since the program of just the keyword "Null" (not to be mistaken for the null program) is a valid program, we can golf out that 0.

And it could even be changed for arbitrary ωn's, or even ωω for just two bytes more. If anyone wanted to run this themselves, I would change out the ∞ for a 3.

Side note: if you really wanted to keep using strings instead of holdform:

```
Nest[Nest["Print["<>ToString[#,InputForm]<>"]"&,#,∞]&,,2]

```

is 57 bytes, and good for learning.

# Answer
> 5 votes
# Python 2, ~~67 63~~ 65 bytes

```
x=""
while 1:x="x=%r\nwhile 1:x='print%%r;'%%x;exec x;"%x;print x

```

Try it online!

Use the same strategy as @UnrelatedString's answer, be sure to check out and upvote his answer! Repeatedly print out programs with ordinal \\$0, \omega, \omega2, \omega3,\ldots \\$. The programs are separated by the string `";\n"` (a semi-colon and a new line).

**68 bytes to separate programs by a blank line.**

### Explanation

A program with ordinal \\$n+1\\$ is created by adding a print statement around an \\$n\\$-ordinal program:

```
print <escaped string of ordinal-n program>

```

A program with ordinal \\$\omega(n+1)\\$ is created by repeatedly printing out programs with ordinal \\$\omega n, \omega n+1,\omega n+2,\ldots\\$

```
x = <string of omega*n program>
while 1:
  x = 'print %r' % x
  exec x

```

Note the use of `%r`, which escapes the given string `x`. This way, we don't have to worry about quote and new line characters.

Finally, a program with ordinal \\$\omega^2\\$ is created by repeatedly printing out programs with ordinal \\$0, \omega, \omega 2,\omega 3,\ldots\\$:

```
# string of program to go from omega*n to omega*(n+1)
s = "x=%r\nwhile 1:x='print%%r'%%x;exec x"
# current omega*n program, start with n=0
x = ""
while 1:
  # create the omega*(n+1) program from omega*n
  x = s % x
  # print it out
  print x

```

# Answer
> 2 votes
# Python 3, 85 bytes

```
s='def l(f,x):\n print(x+"\\n")\n l(f,"%s%r)"%(f,x))'
exec(s)
l(s+"\nl('print(',",'')

```

Try it online!

I... *think* this might be valid? This should print a sequence of programs, separated by blank lines, with ordinals ω, ω·2, ω·3, ω·4, ..., but the reasoning by which I arrived at those ordinals was pretty shaky and I've already forgotten what it even was, so I'd appreciate being shown that I'm completely wrong. The general idea of it is that one program with ordinal ω+ω = ω2 is one which prints a program with ordinal ω, then prints a program that prints that program (so that it has ordinal ω + 1), then prints a program that prints that, and so on... and the part I don't feel too solid about is doing that with the program with ordinal ω·2 to get to ω·3, and iterating to get ω2.

# Answer
> 0 votes
# Self-modifying Brainfuck, 47 bytes

```
-[[<]>[>.]+0]<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]

```

The `0` represents a null byte `\x00` and will be used as the delimiter between programs. I will also use `1` and `ÿ` to represent the bytes `\x01` and `\xff` respectively.

The idea here is to use the program `<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ` with some leading and trailing `1`s to represent ordinals between 0 and \\$\omega^2\\$. The number of trailing `1`s represent how many multiples of \\$\omega\\$ there are, and the number of leading `1`s is how much is added to it. The program `11111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111`, for example, represents \\$\omega3+5\\$ and prints the \\$\omega3+4\\$ program `1111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111`.

```
11111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111     // w3+5
11111                                           // Do nothing
     <[<]>-                                     // Decrement the first character of the code (a '1')
           [?????????????????????]              // If it's not zero do this (not in this case)
                                  >[.>]         // Print the remaining code
                                       ÿ111     // Do nothing

```

The leading `1`s will continue to be deleted until the \\$\omega3\\$ program is reached.

```
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111  // w3
<[<]>-                                  // Decrement the first character (the '<')
      [                     ]           // If it's not zero
       +                                // Increment it back to '<'
        [>]<-                           // Decrement the last character of the code (a '1')
             [?]                        // If it's not zero do this (not in this case)
                <[         ]            // Loop
                  [<]+                  // Add a '1' to the start of the program
                      [>.]<             // Print the code with a trailing '0'

```

This will print the following programs (delimited by `0`s):

```
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11       // w2
1<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11      // w2+1
11<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11     // w2+2
111<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11    // w2+3
...

```

These programs will keep deleting the leading `1`s until the program starts with `<`, then they delete a trailing `1` and print programs with an increasing number of leading `1`s. This continues until the 0 program is reached.

```
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ     // 0
<[<]>-                                  // Decrement the first character (the '<')
      [                     ]           // If it's not zero
       +                                // Increment it back to '<'
        [>]<-                           // Decrement the last character (the 'ÿ')
             [<]                        // Go to the start of the code
                <[?????????] >[??]ÿ     // Halt without printing anything

```

The \\$\omega^2\\$ program simply prints the \\$0, \omega, \omega2, \omega3, ...\\$ programs.

```
-[[<]>[>.]+0]<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]     // w^2
-                                                   // Append a 'ÿ' to the end of the code
 [          ]                                       // Loop
  [<]                                               // Find the '0'
     >[>.]                                          // Print the program with a trailing '0'
          +                                         // Add a '1' to the end

```

This prints:

```
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ     // 0
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ1    // w
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ11   // w2
<[<]>-[+[>]<-[<]<[[<]+[>.]<]]>[.>]ÿ111  // w3
...

```

---
Tags: code-golf, metagolf
---


title: Trim elements from the ends of a list

text:
# Question
Title: Trim elements from the ends of a list
The aim is to trim elements in from the ends of a list, depending on if they are in a second list of "falsey" results.

For example, if the first list is `[-1, 1, 2, 0, -1, 3, -1, 4, -1, -1]` and the second is `[-1]`, then we would remove all leading and trailing `-1`s from the first input, but not any `-1`s in the middle: `[1, 2, 0, -1, 3, -1, 4]`

You may take input in any allowed method and this is so the shortest code in bytes wins.

# Answer
# Haskell, ~~37~~ 36 bytes

```
f v|g<-reverse.snd.span(`elem`v)=g.g

```

Try it online!

* -1 byte thanks to xnor.

## How?

```
f v                     -- define a function f that takes as input a list v of falsey values
  |g<-                  --   inside the definition, define a new function g that...
    reverse             --     reverses...
    .snd                --     the second element of...
    .span               --     a tuple (say (x,y)) where x is the longest prefix of elements that...
      (`elem`v)         --       belong to v...
                        --     and y is the rest of the list
  =g.g                  --   f is defined as the composition g.g (basically apply g twice)

```
> 7 votes

# Answer
# Pyth, 3 bytes

```
.sF

```

Try it here!
> 6 votes

# Answer
# Java, 89 bytes

```
a->b->a.dropWhile(b::contains).sorted((c,d)->-1).dropWhile(b::contains).sorted((c,d)->-1)

```

Try it online!

# Java, 125 bytes

```
a->b->{int i=-1,j=a.length;for(;b.contains(a[++i]););for(;b.contains(a[--j]););return java.util.Arrays.copyOfRange(a,i,j+1);}

```

Try it online!
> 4 votes

# Answer
# Factor \+ `math.unicode`, 19 bytes

```
[ '[ _ ∈ ] trim ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes two sequences as input and returns one sequence as output.

* `'[ _ ∈ ]` Push a fried quotation to the data stack to be used later by `trim`. Whatever is on top of the data stack gets slotted into the quotation at the `_`. This will be the list of elements to trim.
* `trim` Take a sequence and a quotation and apply the quotation to elements on both ends of the sequence, removing elements for which the quotation returns `t`. Stop when `f` is encountered.
* Take an object and a sequence and return `t` if the object is in the sequence. Shorthand for `member?`.
> 4 votes

# Answer
# APL (Dyalog Extended), 4 bytes (SBCS)

Anonymous infix function.

```
⌂deb

```

Try it online!

A library function: delete ending blanks using the left argument as a list of what is considered "blanks".

Notes, comments, and APL implementation.
> 4 votes

# Answer
# 05AB1E, 1 byte

```
Ú

```

Try it online!

A builtin which trims.
> 3 votes

# Answer
# Scala, 46 bytes

```
s=>1.to(2)./:(_)((a,_)=>a.reverse dropWhile s)

```

Try it in Scastie!

```
s =>                            //The Set of falsy items
  1.to(2)                       //Make a range [1, 2] to trim twice
    ./:                         //Fold over it,
    (_)                         //starting with the list to trim
    ((a, _) =>                  //The list a and the number, which is ignored
     a.reverse                  //Reverse the list
      dropWhile                 //And drop while
      s)                        //Each item is present in s

```

## Same length, but more boring

```
s=>_.dropWhile(s).reverse.dropWhile(s).reverse

```

Try it in Scastie!

Boring.
> 3 votes

# Answer
# JavaScript (V8), ~~78~~ 62 bytes

*-16 bytes thanks to @Original Original Original VI*

```
(a,s,g=x=>s.includes(x[0])?g(x.slice(1)):x.reverse())=>g(g(a))

```

**Old:**

```
a=>n=>(t=z=>z.findIndex(d=>!n.includes(d)),a.slice(t(a),-t([...a].reverse())))

```

Can probably be shortened by a ton
> 3 votes

# Answer
# , ~~21~~ 19 bytes

```
[#~1-(*/\.>.*/\)@e.

```

Try it online!
> 3 votes

# Answer
# Python 3, 68 bytes

```
f=lambda a,b:a[-1]in b and f(a[:-1],b)or a[0]in b and f(a[1:],b)or a

```

Try it online!
> 3 votes

# Answer
# , ~~57~~ 55 bytes

```
function(x,y,`+`=cumprod)x[!+x%in%y&!rev(+rev(x)%in%y)]

```

Try it online!

Finds matching elements (`x %in% y`) as vector of `TRUE/FALSE` values, and calculates the cumulative product (`cumprod`, re-assigned to `+` here to save bytes) to convert everything after the first `FALSE` to zero. Then does the same from the other end (by `rev`ersing `x` and the `cumprod`). Finally, negates (`!`) to select only the non-terminal-matching elements of `x`.
> 3 votes

# Answer
# Husk, ~~7~~ 5 bytes

*Edit: -2 bytes thanks to Leo*

```
‼(↔↓€

```

Try it online!

**How?**

`↔↓€` removes the falsy elements from one end of the list, and then flips it:

```
 ↓    # drop the longest prefix of arg2 with elements that satisfy:
  €   # are present in arg1
↔     # then reverse the result

```

So we just need to do this twice (to remove from both ends of the list, and to restore the list to its original orientation):
`(` groups `↔↓€` together (the parentheses are automatically closed at the end of the program), and the higher-order function  runs a function provided as an argument twice.
> 3 votes

# Answer
# Python 2, 64 bytes

```
a,f=input()
for i in-1,0:
 while a and a[i]in f:a.pop(i)
print a

```

The `a and` is necessary if the falsey list, `f`, contains all the elements of `a` and the completely stripped list will be empty. Without it, the program errors with `IndexError: list index out of range`.

Try it online!
> 3 votes

# Answer
# Jelly, 1 byte

```
t

```

Try it online!

A builtin that does exactly this. Works with multiple "falsey" values as well: Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 56 bytes

Expects `(a)(b)`, where **a** is the array to trim, using the values in the set **b**.

```
a=>b=>(g=a=>a.reverse().filter(i=c=>i|=!b.has(c)))(g(a))

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
#//.{e=#|##&@@#2,a___,e...}:>{a}&

```

Try it online!

-6 bytes and correction from @att
> 1 votes

# Answer
# Red, 70 bytes

```
func[b t][while[find t b/1][take b]while[find t last b][take/last b]b]

```

Try it online!

# Using `parse`, 123 bytes

```
func[b t][r: copy[]foreach n t[append r reduce['quote n '|]]take/last r
parse b[remove some r to[any r end]remove some r]b]

```

Try it online!
> 1 votes

# Answer
# Retina 0.8.2, 52 bytes

```
m`^|$
,
(^)?,(([^,]+,)(?=.*¶.*,\3))*(¶.*)?(?(1)|$)

```

Try it online! Explanation:

```
m`^|$
,

```

Wrap both lists in additional commas.

```
(^)?,

```

Record whether this match is at the very start, but at the very least start at a comma.

```
(([^,]+,)(?=.*¶.*,\3))*

```

Match any number of terms which exist in the second array.

```
(¶.*)?

```

Optionally match the second array.

```
(?(1)|$)

```

If the match did not begin at the start, then it must end at the end.

```

```

Delete the matching values.
> 1 votes

# Answer
# Java (JDK), 86 bytes

```
l->b->{while(b.contains(l.peek()))l.pop();while(b.contains(l.getLast()))l.pollLast();}

```

Try it online!

Uses a `LinkedList` as input/output.
> 1 votes

# Answer
# Excel, 70 bytes

```
=LET(x,A1#,r,ROW(x),y,IF(x>-1,r,""),FILTER(x,(r>=MIN(y))*(r<=MAX(y))))

```
> 1 votes

# Answer
# Desmos, ~~227~~ 215 bytes

```
z(A)=length(A)
h(l,a,k)=\left\{l[a]=k:0,1\right\}
f(a,b)=\sum_{n=1}^{z(b)}(1-h(b,n,a))
s=f(A,B)
j(A,B)=A[\sum_{N=1}^{z(s)}N(1-h(s,N,0))\prod_{a=1}^{N-1}h(s,a,0)...z(A)]
p=j(A,B)
q=j(p[z(p)...1],B)
m(A,B)=q[z(q)...1]

```

Try It On Desmos!

Try It On Desmos!(Prettified Version)

Final function is \\$m(a,b)\\$, where \\$a\\$ is the list that is being trimmed, and \\$b\\$ is the list of "falsey" values that are trimmed from \\$a\\$.

Much harder than I initially anticipated because Desmos has limited list functionality. Hopefully it's fine if I output an one-element list with the one element being `undefined`(`[undefined]`) when the output is supposed to be an empty list(`[]`). If it isn't fine then tell me and I can fix(but it would cost more bytes ☹)

Note: Not too sure why, but you can't directly paste the code into Desmos for some reason. You have to paste each expression one at a time in order for it to work.
> 1 votes

# Answer
# Haskell + hgl, 14 bytes

```
jn m<rv.^dW<fe

```

Try it online!

(`.^` has been renamed to `<<` since this was posted)

# Explanation

To start we want to do the much simpler:

```
f x y=rv$dW(fe x)$rv$dw(fe x)y

```

This drops all things in `x` off the front, reverses it, then drops all things in `x` off the new front and reverses it back.

From here we can start by removing the `y`.

```
f x=rv<dW(fe x)<rv<dw(fe x)

```

Now we have the expression `rv<dW(fe x)` twice so let's fix that. `jn` will take a function on two arguments and pass the same value as both of its arguments.

```
f x=(rv<dW(fe x))<(rv<dW(fe x))
f x=jn m(rv<dW(fe x))

```

Now `x` is at the end so we can eta-reduce it away as well:

```
f x=jn m<rv.^dW<fe

```

## Reflection

Usually I would use `Rv` to reverse a list however `.^` next to `Rv` breaks the Haskell parser, so I had to use `rv` instead. I've been aware of this danger for a while now and this was a pretty close call. I will probably rename `.^` to `<<`.

"Compose a function with itself" achieved here with `jn m` is something that should probably have it's own name. It would have saved a byte here at least.
> 1 votes

# Answer
# Uiua SBCS, 11 bytes

```
▽¬↥⇌∩\×⇌.∊,

```

Try it!
> 0 votes

# Answer
# BQN, 16 bytes

```
(⌽(∨`·∧˝≠⌜)/⊢)⍟2

```

Takes the list as its right argument and the elements to trim as its left argument. Try it at BQN online!

### Explanation

```
(⌽(∨`·∧˝≠⌜)/⊢)⍟2
         ≠⌜         Make an inequality table of the two lists: 0 when elements are
                    equal, 1 when they aren't
       ∧˝           Fold each column on logical AND: 1 for elements in the list
                    that aren't one of the elements to trim, 0 for those that are
    ∨`·             Scan with logical OR: keep leading run of 0s but turn everything
                    after the first 1 into 1s
   (       )/⊢      Remove elements of the original list that correspond to 0s in
                    that list; keep elements that correspond to 1s
 ⌽                  Reverse
(              )⍟2  Do that twice

```
> 0 votes

# Answer
# Perl 5 `-a`, 59 bytes

```
$_=<>;for$i(0,-1){splice@F,$i,1while/(^| )$F[$i]\b/}say"@F"

```

Try it online!
> 0 votes

---
Tags: code-golf, array
---


# Question
Title: Enumerate the Phat-fingered-lights-out numbers
Even though the concept of *phat-fingered-lights-out number* should be pretty self-explanatory here is a definition:

Given a nonnegative integer in binary representation a *phat-fingered double-bit-flip* or phatflip for short replaces a pair of **adjacent**, **equal** bits with their complement.

For example given the number 0b111010010000101

0b1**11**010010000101 -\> 0b1**00**010010000101

0b11101**00**10000101 -\> 0b11101**11**10000101

0b**11**1010010000101 -\> 0b1010010000101

are phatflips whereas

0b1110**1**00**1**0000101 -\> 0b1110**0**00**0**0000101 (not adjacent)

0b1110100**10**000101 -\> 0b1110100**01**000101 (not equal)

0b111010010**000**101 -\> 0b111010010**111**101 (not a pair)

are not.

A *phat-fingered-lights-out number (or "pflon")* is a nonnegative integer that can be completely erased by a finite sequence of phatflips.

The first 1000 pflons are:

```
0, 3, 6, 9, 12, 15, 18, 24, 27, 30, 33, 36, 39, 45, 48, 51, 54, 57, 60, 63, 66, 72, 75, 78, 90, 96, 99, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 141, 144, 147, 150, 153, 156, 159, 165, 177, 180, 183, 189, 192, 195, 198, 201, 204, 207, 210, 216, 219, 222, 225, 228, 231, 237, 240, 243, 246, 249, 252, 255, 258, 264, 267, 270, 282, 288, 291, 294, 297, 300, 303, 306, 312, 315, 318, 330, 354, 360, 363, 366, 378, 384, 387, 390, 393, 396, 399, 402, 408, 411, 414, 417, 420, 423, 429, 432, 435, 438, 441, 444, 447, 450, 456, 459, 462, 474, 480, 483, 486, 489, 492, 495, 498, 504, 507, 510, 513, 516, 519, 525, 528, 531, 534, 537, 540, 543, 549, 561, 564, 567, 573, 576, 579, 582, 585, 588, 591, 594, 600, 603, 606, 609, 612, 615, 621, 624, 627, 630, 633, 636, 639, 645, 657, 660, 663, 669, 693, 705, 708, 711, 717, 720, 723, 726, 729, 732, 735, 741, 753, 756, 759, 765, 768, 771, 774, 777, 780, 783, 786, 792, 795, 798, 801, 804, 807, 813, 816, 819, 822, 825, 828, 831, 834, 840, 843, 846, 858, 864, 867, 870, 873, 876, 879, 882, 888, 891, 894, 897, 900, 903, 909, 912, 915, 918, 921, 924, 927, 933, 945, 948, 951, 957, 960, 963, 966, 969, 972, 975, 978, 984, 987, 990, 993, 996, 999, 1005, 1008, 1011, 1014, 1017, 1020, 1023, 1026, 1032, 1035, 1038, 1050, 1056, 1059, 1062, 1065, 1068, 1071, 1074, 1080, 1083, 1086, 1098, 1122, 1128, 1131, 1134, 1146, 1152, 1155, 1158, 1161, 1164, 1167, 1170, 1176, 1179, 1182, 1185, 1188, 1191, 1197, 1200, 1203, 1206, 1209, 1212, 1215, 1218, 1224, 1227, 1230, 1242, 1248, 1251, 1254, 1257, 1260, 1263, 1266, 1272, 1275, 1278, 1290, 1314, 1320, 1323, 1326, 1338, 1386, 1410, 1416, 1419, 1422, 1434, 1440, 1443, 1446, 1449, 1452, 1455, 1458, 1464, 1467, 1470, 1482, 1506, 1512, 1515, 1518, 1530, 1536, 1539, 1542, 1545, 1548, 1551, 1554, 1560, 1563, 1566, 1569, 1572, 1575, 1581, 1584, 1587, 1590, 1593, 1596, 1599, 1602, 1608, 1611, 1614, 1626, 1632, 1635, 1638, 1641, 1644, 1647, 1650, 1656, 1659, 1662, 1665, 1668, 1671, 1677, 1680, 1683, 1686, 1689, 1692, 1695, 1701, 1713, 1716, 1719, 1725, 1728, 1731, 1734, 1737, 1740, 1743, 1746, 1752, 1755, 1758, 1761, 1764, 1767, 1773, 1776, 1779, 1782, 1785, 1788, 1791, 1794, 1800, 1803, 1806, 1818, 1824, 1827, 1830, 1833, 1836, 1839, 1842, 1848, 1851, 1854, 1866, 1890, 1896, 1899, 1902, 1914, 1920, 1923, 1926, 1929, 1932, 1935, 1938, 1944, 1947, 1950, 1953, 1956, 1959, 1965, 1968, 1971, 1974, 1977, 1980, 1983, 1986, 1992, 1995, 1998, 2010, 2016, 2019, 2022, 2025, 2028, 2031, 2034, 2040, 2043, 2046, 2049, 2052, 2055, 2061, 2064, 2067, 2070, 2073, 2076, 2079, 2085, 2097, 2100, 2103, 2109, 2112, 2115, 2118, 2121, 2124, 2127, 2130, 2136, 2139, 2142, 2145, 2148, 2151, 2157, 2160, 2163, 2166, 2169, 2172, 2175, 2181, 2193, 2196, 2199, 2205, 2229, 2241, 2244, 2247, 2253, 2256, 2259, 2262, 2265, 2268, 2271, 2277, 2289, 2292, 2295, 2301, 2304, 2307, 2310, 2313, 2316, 2319, 2322, 2328, 2331, 2334, 2337, 2340, 2343, 2349, 2352, 2355, 2358, 2361, 2364, 2367, 2370, 2376, 2379, 2382, 2394, 2400, 2403, 2406, 2409, 2412, 2415, 2418, 2424, 2427, 2430, 2433, 2436, 2439, 2445, 2448, 2451, 2454, 2457, 2460, 2463, 2469, 2481, 2484, 2487, 2493, 2496, 2499, 2502, 2505, 2508, 2511, 2514, 2520, 2523, 2526, 2529, 2532, 2535, 2541, 2544, 2547, 2550, 2553, 2556, 2559, 2565, 2577, 2580, 2583, 2589, 2613, 2625, 2628, 2631, 2637, 2640, 2643, 2646, 2649, 2652, 2655, 2661, 2673, 2676, 2679, 2685, 2709, 2757, 2769, 2772, 2775, 2781, 2805, 2817, 2820, 2823, 2829, 2832, 2835, 2838, 2841, 2844, 2847, 2853, 2865, 2868, 2871, 2877, 2880, 2883, 2886, 2889, 2892, 2895, 2898, 2904, 2907, 2910, 2913, 2916, 2919, 2925, 2928, 2931, 2934, 2937, 2940, 2943, 2949, 2961, 2964, 2967, 2973, 2997, 3009, 3012, 3015, 3021, 3024, 3027, 3030, 3033, 3036, 3039, 3045, 3057, 3060, 3063, 3069, 3072, 3075, 3078, 3081, 3084, 3087, 3090, 3096, 3099, 3102, 3105, 3108, 3111, 3117, 3120, 3123, 3126, 3129, 3132, 3135, 3138, 3144, 3147, 3150, 3162, 3168, 3171, 3174, 3177, 3180, 3183, 3186, 3192, 3195, 3198, 3201, 3204, 3207, 3213, 3216, 3219, 3222, 3225, 3228, 3231, 3237, 3249, 3252, 3255, 3261, 3264, 3267, 3270, 3273, 3276, 3279, 3282, 3288, 3291, 3294, 3297, 3300, 3303, 3309, 3312, 3315, 3318, 3321, 3324, 3327, 3330, 3336, 3339, 3342, 3354, 3360, 3363, 3366, 3369, 3372, 3375, 3378, 3384, 3387, 3390, 3402, 3426, 3432, 3435, 3438, 3450, 3456, 3459, 3462, 3465, 3468, 3471, 3474, 3480, 3483, 3486, 3489, 3492, 3495, 3501, 3504, 3507, 3510, 3513, 3516, 3519, 3522, 3528, 3531, 3534, 3546, 3552, 3555, 3558, 3561, 3564, 3567, 3570, 3576, 3579, 3582, 3585, 3588, 3591, 3597, 3600, 3603, 3606, 3609, 3612, 3615, 3621, 3633, 3636, 3639, 3645, 3648, 3651, 3654, 3657, 3660, 3663, 3666, 3672, 3675, 3678, 3681, 3684, 3687, 3693, 3696, 3699, 3702, 3705, 3708, 3711, 3717, 3729, 3732, 3735, 3741, 3765, 3777, 3780, 3783, 3789, 3792, 3795, 3798, 3801, 3804, 3807, 3813, 3825, 3828, 3831, 3837, 3840, 3843, 3846, 3849, 3852, 3855, 3858, 3864, 3867, 3870, 3873, 3876, 3879, 3885, 3888, 3891, 3894, 3897, 3900, 3903, 3906, 3912, 3915, 3918, 3930, 3936, 3939, 3942, 3945, 3948, 3951, 3954, 3960, 3963, 3966, 3969, 3972, 3975, 3981, 3984, 3987, 3990, 3993, 3996, 3999, 4005, 4017, 4020, 4023, 4029, 4032, 4035, 4038, 4041, 4044, 4047, 4050, 4056, 4059, 4062, 4065, 4068, 4071, 4077, 4080, 4083, 4086, 4089, 4092, 4095, 4098, 4104, 4107, 4110, 4122, 4128, 4131, 4134, 4137, 4140, 4143, 4146, 4152, 4155, 4158, 4170, 4194, 4200, 4203, 4206, 4218, 4224, 4227, 4230, 4233, 4236, 4239, 4242, 4248, 4251, 4254, 4257, 4260, 4263, 4269, 4272, 4275, 4278, 4281, 4284, 4287, 4290, 4296, 4299, 4302, 4314, 4320, 4323, 4326, 4329, 4332, 4335, 4338, 4344, 4347, 4350, 4362, 4386, 4392, 4395, 4398, 4410, 4458, 4482, 4488, 4491, 4494, 4506, 4512, 4515, 4518, 4521, 4524, 4527, 4530, 4536

```

This is `code-golf` and a`sequence` challenge; standard rules apply:

* shortest code in bytes (full program or function) wins; each language or major language version is their own competition
* you can either take a number *n* and return the *n*-th pflon or the first *n* pflons; counting can be 0- or 1-based
* or you can take no input and output the sequence til kingdom come

*Source*: This is mostly a rip-off of this post over at puzzling SO.

# Answer
# Uiua 0.9.0, 14 bytes SBCS (updated!)

```
↙:▽=0/-⍉⋯.⇡×..

```

Try on Uiua Pad! Takes \\$n\\$ as input and outputs the first \\$n\\$ terms. Does essentially the same thing as my answer below and *@Mukundan314*'s APL answer.

## 19 bytes SBCS

```
⍥(+1(&p.|)≠0/-⋯.)∞0

```

Try it! Takes no input and outputs the sequence (change the  to some small number like `10`  if you want to see the beginning)

## Old Explanation

```
0 # push 0 to stack
⍥(       # repeat
  ⋯.     # to binary
  /-     # alternating difference
  ≠0     # not zero?
  (&p.|) # else print number
  +1     # add 1
)∞       # infinitely many times

```

## Theorem

\\$n\\$ is a pflon if and only if in the binary representation of \\$n\\$, the number of 1s in even positions of is equal to the number of 1s in odd positions.

### Proof

(\\$\implies\\$) Every phatflip clearly maintains whether the odd-even condition holds, as it either adds a 1 to both counts or removes a 1 from both counts. The condition holds for 0. Since any pflon can be obtained from phatflips starting at 0 (just reversing the sequence to get lights out), the condition holds for every pflon.

(\\$\impliedby\\$) We prove by strong induction on \\$n\\$. The base case 0 is trivial.

Let \\$n\>0\\$. Suppose all integers \\$k\\$ with \\$0 \leq k \< n\\$ for which the binary condition holds are pflons. Then suppose the binary condition holds for \\$n\\$.

\\$n\\$ must have at least a 1 in both even and odd position, so it must have a 1 in even position and a 1 in odd position separated by zero or more 0s. Since their positions have opposite parity, there must be an even number of 0s between them. So, we can flip all those 0s into 1s, then flip all those and the two 1s back into zeros. All these flips maintain the binary condition, as shown above, and the result \\$k\\$ is less than \\$n\\$ as we just switched two 1s to 0s. Therefore, \\$k\\$ is a pflon, and is accessible from \\$n\\$ by phatflips, so \\$n\\$ is a pflon.
> 10 votes

# Answer
# Jelly, 6 bytes

```
Bḅ-¬µ#

```

A full program that accepts a positive integer, `n`, on stdin and prints the first `n` phat-fingered-lights-out numbers.

**Try it online!**

### How?

Every phat-flip applies to an adjacent pair of bits, so if the number of odd-positioned ons is equal to the number of even-position ons then after flipping as many on-pairs as possible we can bring any remaining separated ons together by flipping pairs of offs and then flip remaining pairs of ons out of existence. A binary number with this property, is zero when converted from base \\$-1\\$ since, counting from the least significant bit as position \\$1\\$, odd-position ons contribute \\$1\\$ while even-position ons contribute \\$-1\\$ (and all offs contribute \\$0\\$).

```
Bḅ-¬µ# - Main Link: no arguments
    µ# - count up from k=0, and yield the first {stdin} integers for which:
B      -   convert to binary
 ḅ-    -   convert from base -1
   ¬   -   logical NOT
       - implicit print

```
> 6 votes

# Answer
# JavaScript (V8), 45 bytes

A full program that prints the sequence indefinitely.

This relies on arithmetic underflow to stop the recursion, making it slower than it should (+1 byte for a faster version).

```
for(n=-1;f=n=>n&&n%2-f(n/2);)f(++n)||print(n)

```

Try it online!
> 5 votes

# Answer
# Charcoal, ~~23~~ ~~19~~ 16 bytes

```
ＮθＩ…Φ×θθ¬↨↨ι²±¹θ

```

Try it online! Link is to verbose version of code. Outputs the first `n` terms. Explanation: Even more wildly overestimates an upper bound for `A039004(n)`, then uses @Tbw's theorem to find `n` terms.

```
Ｎθ                  Input `n` as an integer
      θ             Input `n`
     ×              Multiplied by
       θ            Input `n`
    Φ               Filter over implicit range where
           ι        Current value
          ↨         Converted to base
            ²       Literal integer `2`
         ↨          Interpreted as base
              ¹     Literal integer `1`
             ±      Negated
        ¬           Is zero
   …                Truncated to length
               θ    Input `n`
  Ｉ                 Cast to string
                    Implicitly print

```

Edit: Removed `⁺³Ｌ` saving 3 bytes to even more wildly overestimate `A039004(n)` thanks to @Tbw.

Outputting all of the pflons less than `n` would of course be shorter:

```
ＩΦＮ¬↨↨ι²±¹

```

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

```
  Ｎ         Input `n` as a number
 Φ          Filter over implicit range where
      ι     Current value
     ↨      Converted to base
       ²    Literal integer `2`
    ↨       Interpreted as base
         ¹  Literal integer `1`
        ±   Negated
   ¬        Is zero
Ｉ           Cast to string
            Implicitly print

```
> 5 votes

# Answer
# APL(Dyalog Unicode), 18 bytes SBCS

Requires Index Origin 0 (`⎕IO←0`)

```
A↑⍸0=-⌿2⊥⍣¯1⍳×⍨A←⎕

```

Try it on APLgolf!

A full program which outputs the first `n` phat-fingered-lights-out numbers.

```
A↑⍸0=-⌿2⊥⍣¯1⍳×⍨A←⎕
               A←⎕  # A = input
             ×⍨     # square
            ⍳       # range [0, 1, ..., arg - 1]
       2⊥⍣¯1        # to base 2
     -⌿             # alternating difference
   0=               # equals zero
  ⍸                 # indices of true
A↑                  # take first A elements

```
> 4 votes

# Answer
# x86 32-bit machine code, 23 bytes

```
83 C8 FF 40 BA AA AA AA AA 31 C2 F3 0F B8 D2 83 FA 10 75 EF E2 ED C3

```

Try it online!

Following the `fastcall` calling convention, this takes a number *n* in ECX and returns the 1-indexed *n*th pflon in EAX.

In assembly:

```
f:  or eax, -1      # Set EAX to -1 (all 1 bits).
r:  inc eax         # Add 1 to EAX. EAX will be the number being tested.
    mov edx, 0xAAAAAAAA # Set EDX to this value, with 1 bits in odd positions.
    xor edx, eax    # Exclusive-OR that value with EAX (inverts odd positions).
    popcnt edx, edx # Count the number of 1 bits in that value.
    cmp edx, 16     # Check whether it's 16.
    jne r           # If not, jump back (to test the next number).
    loop r          # Decrease ECX by 1 and jump back if it's nonzero.
    ret             # Return. (EAX is the return value.)

```
> 3 votes

# Answer
# APL+WIN, ~~29~~ 37 bytes

+8 bytes as it appears my original answer of outputting the series up to a given value was outside the rules. Prompts for number of values to output. Index origin = 0

```
n↑(0=-⌿((⌈2⍟1⌈n*2)⍴2)⊤m)/m←⍳1+(n←⎕)*2

```

Try it online! Thanks to Dyalog Classic

Original answer.

Prompts for an integer and outputs the sequence up to that value. Index origin = 0

```
(0=-⌿((⌈2⍟1⌈n)⍴2)⊤m)/m←⍳1+n←⎕

```
> 2 votes

# Answer
# , ~~23~~ 21 bytes

```
{.(#~0=-/"1@#:)@i.@*:

```

Try it online!

*Uses Tbw's observation and is basically a port of Mukundan314's APL answer*
> 2 votes

# Answer
# Haskell \+ hgl, 20 bytes

```
fl(qb sm<%uak<bs2)nn

```

Attempt This Online!

## Explanation

We convert the list to base 2, split it into digits in an even position and digits in an odd position, then check that these two lists have the same sum.

Since `0` and `3` in base 4 are `00` and `11` in base 2, each of these contributes the same amount to both lists and have no effect on the outcome. `1` and `2` in base 4 are `01` and `10` in base 2, so each contributes 1 to one of sums of the two halves. Thus checking if the sums are the same as checking if there are the same number of 1s as 2s in the base 4 representation.

# Haskell, 20 bytes

```
fl(eq0<rF(-)0<bs2)nn

```

Attempt This Online!

## Explanation

This uses the more complicated alternate sum approach found in this answer for the same byte count.

# Haskell, 21 bytes

```
fl((ce1*=*ce2)<bs4)nn

```

Attempt This Online!

## Explanation

This uses the naive approach, converting to base 4 and counting the number of 1 and 2 digits.

## Reflection

The thing to note is that hgl isn't really well suited for arithmetic heavy challenges (yet).

* There should be a function that combines `fl` and `nn` to get natural numbers satisfying a property.
* ~~I keep making variants of `l2`, but I feel like `l2 eq` would be a good shortcut to have.~~ The precedence on `(*=*)` is incompatible with `(<)`. I should change it to be anything else.
* `bs` should be made to handle negative bases as well. I do believe there is a way to do this question in terms of negative bases, although I haven't really investigated since I can't do negative bases in hgl.
* `rF(-)0`, or "alternating sum", could probably be added.
> 2 votes

# Answer
# Python 3, 107 bytes

```
f=lambda n,i=0,l=[]:i-1if n==sum(l)else f(n,i+1,l+[a(i,2)==a(i,3)])
a=lambda n,s:sum(map(int,bin(n)[s::2]))

```

Try it online!

Uses the same logic as other solutions to sum odd and even bits. Generates a list of T/F values corresponding to the index value's phat-ness, and returns the index found when the sum of the T/F list is equal to `n`.
> 2 votes

# Answer
# 05AB1E, 7 bytes

```
∞<ʒb®ö_

```

Outputs a lazy infinite list.

Try it online.

Or:

```
[Nb®ö_–

```

Infinitely outputs all results on a separated newline to STDOUT.

Try it online.

Both are a port of *@JonathanAllan*'s Jelly answer.

**Explanation:**

```
∞        # Push an infinite positive list: [1,2,3,...]
 <       # Make it non-negative by decreasing each by 1: [0,1,2,...]
  ʒ      # Filter this list by:
   b     #  Convert from a base-10 integer to a binary string
    ®ö   #  Convert from a base-(-1) integer to a base-10 integer
      _  #  Check that this is equal to 0
         # (after which the lazy finite list is output implicitly as result)

[        # Start an infinite loop:
 N       #  Push the current 0-based loop index
  b®ö_   #  Same as above
      –  #  If this is truthy: output the 0-based loop index with trailing newline

```
> 1 votes

# Answer
# C (gcc), ~~107~~ 92 bytes

*-15 thanks to @ceilingcat for much smarter for loop utilization*

```
b[2],i,c,k;f(n){for(k=c=0;k^n;k+=*b==b[1],c++)for(*b=b[1]=i=0;i<32;)b[i%2]+=c>>i++&1;n=c-1;}

```

Try it online!

Uses a 2 element array to count odd and even bits, incrementing a count if equal, and returns the last value checked when the count was incremented.
> 1 votes

# Answer
# Scala 3, 212 bytes

A port of @Arnold Palmer's Python answer in Scala.

---

Golfed version. Attempt This Online!

```
def f(n:Int,i:Int=0,l:Seq[Boolean]=Seq()):Int={if(n==l.count(identity))i-1 else f(n,i+1,l:+(a(i,2)==a(i,3)))}
def a(n:Int,s:Int)=n.toBinaryString.zipWithIndex.collect{case(c,i) if(i+s)%2==0=>c.toString.toInt}.sum

```

Ungolfed version. Attempt This Online!

```
object Main {
  def main(args: Array[String]): Unit = {
    for (i <- 1 to 16) {
      println(s"$i: ${f(i)}")
    }
  }

  def f(n: Int, i: Int = 0, l: List[Boolean] = List()): Int = {
    if (n == l.count(identity)) i - 1
    else f(n, i + 1, l :+ (a(i, 2) == a(i, 3)))
  }

  def a(n: Int, s: Int): Int = {
    val binaryString = n.toBinaryString
    // Create a sequence from the binary string starting at index `s` and taking every second character, then map to Int and sum
    binaryString.zipWithIndex.collect {
      case (char, index) if (index + s) % 2 == 0 => char.toString.toInt
    }.sum
  }
}

```
> 1 votes

---
Tags: code-golf, sequence
---


# Question
Title: Compute the phat-fingered double-bit-flip distance
Recall from this challenge that a *phat-fingered double-bit flip* or *phatflip* is defined as follows:

> Given a nonnegative integer in binary representation a *phat-fingered double-bit-flip* or phatflip for short replaces a pair of **adjacent**, **equal** bits with their complement.
>
> For example given the number 0b111010010000101
>
> 0b1**11**010010000101 -\> 0b1**00**010010000101
>
> 0b11101**00**10000101 -\> 0b11101**11**10000101
>
> 0b**11**1010010000101 -\> 0b1010010000101
>
> are phatflips whereas
>
> 0b1110**1**00**1**0000101 -\> 0b1110**0**00**0**0000101 (not adjacent)
>
> 0b1110100**10**000101 -\> 0b1110100**01**000101 (not equal)
>
> 0b111010010**000**101 -\> 0b111010010**111**101 (not a pair)
>
> are not.

Also recall that

> A *phat-fingered-lights-out number (or "pflon")* is a nonnegative integer that can be completely erased by a finite sequence of phatflips.

We now introduce the *phat-fingered double-bit flip distance* or *PhD*:

Given two pflons *a* and *b*, *PhD*(*a*,*b*) is the minimum number of phatflips required to change *a* into *b*.

Your task: Using as few bytes as possible implement the function *PhD*

Examples:

```
a,b -> PhD(a,b)
possible sequence
of phatflips (you
needn't implement
this)

15 27 -> 2
01111
00011
11011

33 36 -> 2
100001
100111
100100

39 54 -> 4
100111
100100
111100
110000
110110

57 66 -> 9
0111001
0111111
0111100
0110000
0110110
0000110
0011110
0010010
1110010
1000010

417 831 -> 4
0110100001
0110100111
0110111111
0000111111
1100111111

9504 14454 -> 10
10010100100000
10010100100110
10010111100110
10010110000110
10010110110110
10010000110110
10010011110110
10011111110110
10011001110110
10000001110110
11100001110110

```

# Answer
> 5 votes
# Charcoal, 51 bytes

```
ＮθＮηＷ⁻θη¿﹪ι²«≔³ζＷ∧＆θζ＆～θζ≦⊗ζ≔⁻｜θζ＆θζθ→»«≧÷²θ≧÷²η»Ｉⅈ

```

Try it online! Link is to verbose version of code. Explanation: Greedy algorithm which works for the test cases at least.

```
ＮθＮη

```

Input `a` and `b`.

```
Ｗ⁻θη

```

Repeat until `a` equals `b`.

```
¿﹪ι²«

```

If exactly one of `a` and `b` is odd, then:

```
≔³ζＷ∧＆θζ＆～θζ≦⊗ζ

```

Find the rightmost possible phatflip for `a`.

```
≔⁻｜θζ＆θζθ

```

Apply that phatflip to `a`.

Keep count of the number of phatflips.

```
»«≧÷²θ≧÷²η

```

Otherwise, divide both `a` and `b` by `2`.

```
»Ｉⅈ

```

Output the number of phatflips.

A port of @loopywalt's golf to @Vincent's solution is only 34 bytes:

```
≔Ｅ²ＮθＷ↨θ±¹«⊞υ↔ⅈＭ↨﹪θ²±¹→≔÷⮌θ²θ»Ｉ↨υ¹

```

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

```
≔Ｅ²Ｎθ

```

Input `a` and `b`.

```
Ｗ↨θ±¹«

```

Repeat until `a==b`.

```
⊞υ↔ⅈ

```

Save the absolute current offset.

```
Ｍ↨﹪θ²±¹→

```

Adjust the offset according to the difference between the bottom bits of `a` and `b`.

```
≔÷⮌θ²θ

```

Swap and halve `a` and `b`.

```
»Ｉ↨υ¹

```

Output the total number of phatflips.

# Answer
> 5 votes
# Python3, 56 bytes

```
p=lambda a,b,c=0:abs(c)+(a^b and p(b//2,a//2,c+a%2-b%2))

```

Thanks to @loopy walt for an elegant way to remove the mask completely by alternating the arguments (-50) and for golfing the result further (-19)

Now the solution is also quite fast!

# Python3, 125 bytes

```
def p(a,b):
 m=4**(a+b)//3
 def d(a,b,c=0):
  if a==0:return 0
  c+=a%2-b%2
  return abs(c)+d(a//2,b//2,c)
 return d(a^m,b^m)

```

New here, I feel like this is a fun/weird solution, I'll try to explain. When using phatflips (as I do everyday) I feel more like I am moving some bits than flipping some bits (do you get what I mean ?).

With that in mind, let's define the generalized phatflip: it is the operation of flipping *and* swapping 2 adjacent digits. Note that if the bits are the same, it is a normal phatflip, and if the bits are different, it doesn't do anything. Trying to minimize the number of generalized phatflip is the same thing as trying to minimize the number of phatflip.

The swapping looks cooler than the flipping to me, so to get rid of the flipping part, let's use an alternate binary representation for numbers: if \\$x\_ny\_n...x\_0y\_0\\$ is a normal binary representation of n, the alternate representation is obtained by flipping all the \\$y\_i\\$ , the even placed bits (e.g. 27 is normally 11011 but would be 01110 and 15 would not be 01111 but 11010). When adding leading digits with this alternate representation, make sure to alternate 0s and 1s.

With this alternate view, a phatflip just swaps adjacent bits! Now calculating the distance for swapping adjacent bits looks much easier! The distance between 27: 01110 and 15: 11010 is 2, and it is easy to know where the phatflips should be!

About the code, the variable m provides a xor-mask (1010...101) for the alternate view, and the function d calculates the distance for swapping adjacent bits. For a faster version, replace m=4\**len(bin(a+b))//3 (the mask doesn't need to be that long). It can certainly be golfed further, I don't know that much about code golfing --'

# Answer
> 3 votes
# JavaScript (ES6), 63 bytes

A port of Neil's greedy algorithm.

Expects `(a)(b)`.

```
a=>g=b=>a+b&1?(h=k=>(b&k)%3?h(k*2):1+g(b^k))(3):b&&g(b>>1,a/=2)

```

Try it online!

### Commented

```
a =>              // outer function taking a
g = b =>          // inner recursive function taking b
a + b & 1 ?       // if exactly one of a and b is odd:
  ( h = k =>      //   h is a recursive function taking a pattern k
    (b & k) % 3 ? //   if b AND k is neither 0b00(…) nor 0b11(…):
      h(k * 2)    //     try again with k * 2
    :             //   else:
      1 +         //     increment the final result
      g(b ^ k)    //     and do a recursive call with b XOR k
  )(3)            //   initial call to g with k = 0b11
:                 // else:
  b &&            //   stop if b = 0
    g(            //   otherwise do a recursive call with:
      b >> 1,     //     floor(b / 2)
      a /= 2      //     and a / 2
    )             //   end of recursive call

```

# Answer
> 1 votes
# Python3, 256 bytes

Can certainly be golfed further.

```
Y=lambda x:[*map(int,bin(x)[:1]+bin(x)[2:])]
def f(a,b):
 A,B=Y(a),Y(b)
 q,s=[(A,0)],[A]
 for i,c in q:
  if i[i[0]==0:]==B[B[0]==0:]:return c
  for j in range(len(i)-1):
   if i[j]==i[j+1]and(K:=i[:j]+[int(not i[j])]*2+i[j+2:])not in s:q+=[(K,c+1)];s+=[K]

```

Try it online!

# Answer
> 1 votes
# Scala 3, 137 bytes

A port of @Vincent's Python answer in Scala.

---

Golfed version. Attempt This Online!

```
(a,b)=>{val m=Math.pow(4,a+b).toInt/3;def d(a:Int,b:Int,c:Int=0):Int=if(a==0)0 else{val n=c+a%2-b%2;math.abs(n)+d(a/2,b/2,n)};d(a^m,b^m)}

```

Ungolfed version. Attempt This Online!

```
object Main {
  def f(a: Int, b: Int): Int = {
    val m = Math.pow(4, a + b).toInt / 3
    def d(a: Int, b: Int, c: Int = 0): Int = {
      if (a == 0) return 0
      val newC = c + a % 2 - b % 2
      math.abs(newC) + d(a / 2, b / 2, newC)
    }
    d(a ^ m, b ^ m)
  }

  def main(args: Array[String]): Unit = {
    println(f(15, 27) == 2)
    println(f(33, 36) == 2)
    println(f(39, 54) == 4)
    println(f(57, 66) == 9)
    println(f(417, 831) == 4)
    println(f(9504, 14454) == 10)
  }
}

```

---
Tags: code-golf
---


# Question
Title: Check if all non-zero elements in a matrix are connected
### Input:

A matrix containing integers in the range **\[0 - 9\]**.

### Challenge:

Determine if all non-zero elements are connected to each other vertically and/or horizontally.

### Output:

A truthy value if all are connected, and a falsy value if there are non-zero elements/groups that aren't connected to other elements/groups.

### Test cases:

Test cases are separated by line. Test cases can be found in more convenient formats here (Kudos to Dada).

The following are all connected and should return a truthy value:

```
0
---
0 0
---
1 1 1
0 0 0
---
1 0 0
1 1 1
0 0 1
---
0 0 0 0 0 0
0 0 3 5 1 0
0 1 0 2 0 1
1 1 0 3 1 6
7 2 0 0 3 0
0 8 2 6 2 9
0 0 0 0 0 5

```

The following are all not-connected, and should return a falsy value:

```
0 1
1 0
---
1 1 1 0
0 0 0 2
0 0 0 5
---
0 0 5 2
1 2 0 0
5 3 2 1
5 7 3 2
---
1 2 3 0 0 5
1 5 3 0 1 1
9 0 0 4 2 1
9 9 9 0 1 4
0 1 0 1 0 0

```

This is , so the shortest submission in each language wins. **Explanations are encouraged!**

---

Inspired by this challenge.

# Answer
# MATL, 7 bytes

```
4&1ZI2<

```

This gives a matrix containing all ones as truthy output, or a matrix containing at least a zero as falsy. Try it online!

You can also verify truthiness/falsiness adding an `if`-`else` branch at the footer; try it too!

Or verify all test cases.

### Explanation

```
4       % Push 4 (defines neighbourhood)
&       % Alternative input/output specification for next function
1ZI     % bwlabeln with 2 input arguments: first is a matrix (implicit input),
        % second is a number (4). Nonzeros in the matrix are interpreted as
        % "active" pixels. The function gives a matrix of the same size
        % containing positive integer labels for the connected components in
        % the input, considering 4-connectedness
2<      % Is each entry less than 2? (That would mean there is only one
        % connected component). Implicit display

```
> 10 votes

# Answer
# Retina 0.8.2, ~~80~~ ~~77~~ 74 bytes

```
T`d`@1
1`1
_
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)$))(?!\3)[1_]
$1_$4_
^\D+$

```

Try it online! Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation:

```
T`d`@1

```

Simplify to an array of `@`s and `1`s.

```
1`1
_

```

Change one `1` to a `_`.

```
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)$))(?!\3)[1_]
$1_$4_

```

Flood fill from the `_` to adjacent `1`s.

```
^\D+$

```

Test whether there are any `1`s left.
> 9 votes

# Answer
# Wolfram Language (Mathematica), 54 bytes

Saved 2 bytes thanks to user202729.

```
Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&

```

Try it online!
> 8 votes

# Answer
# JavaScript (ES6), ~~136~~ 135 bytes

Returns a boolean.

```
m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

```

### Test cases

```
let f =

m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

console.log('[Truthy]')

console.log(f([
  [0]
]))
console.log(f([
  [0,0]
]))
console.log(f([
  [1,1,1],
  [0,0,0]
]))
console.log(f([
  [1,0,0],
  [1,1,1],
  [0,0,1]
]))
console.log(f([
  [0,0,0,0,0,0],
  [0,0,3,5,1,0],
  [0,1,0,2,0,1],
  [1,1,0,3,1,6],
  [7,2,0,0,3,0],
  [0,8,2,6,2,9],
  [0,0,0,0,0,5]
]))

console.log('[Falsy]')

console.log(f([
  [0,1],
  [1,0]
]))
console.log(f([
  [1,1,1,0],
  [0,0,0,2],
  [0,0,0,5]
]))
console.log(f([
  [0,0,5,2],
  [1,2,0,0],
  [5,3,2,1],
  [5,7,3,2]
]))
console.log(f([
  [1,2,3,0,0,5],
  [1,5,3,0,1,1],
  [9,0,0,4,2,1],
  [9,9,9,0,1,4],
  [0,1,0,1,0,0]
]))
```

### Commented

The recursive function **g()** first looks for a non-zero cell (as long as the globally-defined flag **z** is set to **0**) and then starts flood-filling from there (as soon as **z != 0**).

```
m =>                               // given the input matrix m
  !/[1-9]/.test((                  // test whether there's still a non-zero digit
    g = (y, x = 0) =>              //   after recursive calls to g(), starting at (x=0,y=0):
      1 / (n = (m[y] || 0)[x]) &&  //     n = current cell; if it is defined:
      !z | n ? (                   //       if z is zero or n is non-zero:
          m[y++][x] = 0,           //         we set the current cell to zero
          z = n                    //         we set z to the current cell
        ) ?                        //         if z is non-zero:
          g(y, x) &                //           flood-fill towards bottom
          g(--y - 1, x) &          //           flood-fill towards top
          g(y, x + 1) ||           //           flood-fill towards right
          g(y, x - 1)              //           flood-fill towards left
        :                          //         else:
          g(m[y] ? y : +!++x, x)   //           look for a non-zero cell to start from
      :                            //       else:
        m                          //         return the matrix
    )(z = 0)                       //   initial call to g() + initialization of z
  )                                // end of test()

```
> 7 votes

# Answer
# C, 163 bytes

*Thanks to @user202729 for saving two bytes!*

```
*A,N,M;g(j){j>=0&j<N*M&&A[j]?A[j]=0,g(j+N),g(j%N?j-1:0),g(j-N),g(++j%N?j:0):0;}f(a,r,c)int*a;{A=a;N=c;M=r;for(c=r=a=0;c<N*M;A[c++]&&++r)A[c]&&!a++&&g(c);return!r;}

```

Loops through the matrix until it finds the first non-zero element. Then stops looping for a while and recursively sets every non-zero element connected to the found element to zero. Then loops through the rest of the matrix checking if every element is now zero.

Try it online!

**Unrolled:**

```
*A, N, M;

g(j)
{
    j>=0 & j<N*M && A[j] ? A[j]=0, g(j+N), g(j%N ? j-1 : 0), g(j-N), g(++j%N ? j : 0) : 0;
}

f(a, r, c) int*a;
{
    A = a;
    N = c;
    M = r;

    for (c=r=a=0; c<N*M; A[c++] && ++r)
        A[c] && !a++ && g(c);

    return !r;
}

```
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~36~~ 22 bytesSBCS

```
~0∊∨.∧⍨⍣≡2>+/|↑∘.-⍨⍸×⎕

```

Try it online!

thanks @H.PWiz

`⍸×⎕` coordinates of non-zero squares

`2>+/|↑∘.-⍨` adjacency matrix of the neighbour graph

`∨.∧⍨⍣≡` transitive closure

`~0∊` is it all 1s?
> 5 votes

# Answer
# Jelly, 23 bytes

```
FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3

```

Try it online!

---

## Explanation.

The program labels each morphological components with a different numbers, then check if there are less than 3 numbers. (including `0`).

Consider a row in the matrix.

```
«Ḋo   Given [1,2,3,0,3,2,1], return [1,2,3,0,2,1,1].
«     Minimize this list (element-wise) and...
 Ḋ      its dequeue. (remove the first element)
      So min([**1**,**2**,3,**0**,3,2,**1**],
             [2,3,**0**,3,**2**,**1**]    (deque)
      ) =    [1,2,0,0,2,1,1].
  o   Logical or - if the current value is 0, get the value in the input.
         [**1**,**2**,0,0,**2**,**1**,**1**] (value)
      or [1,2,**3**,**0**,3,2,1] (input)
      =  [1,2,3,0,2,1,1]

```

Repeatedly apply this function for all row and columns in the matrix, in all orders, eventually all morphological components will have the same label.

```
µ«Ḋoµ€ZUµ4¡ÐL  Given a matrix with all distinct elements (except 0),
               label two nonzero numbers the same if and only if they are in
               the same morphological component.
µ«Ḋoµ          Apply the function above...
     €           for ach row in the matrix.

      Z        **Z**ip, transpose the matrix.
       U       **U**pend, reverse all rows in the matrix.
               Together, **ZU** rotates the matrix 90° clockwise.
         4¡    Repeat 4 times. (after rotating 90° 4 times the matrix is in the
               original orientation)
           ÐL  Repeat until fixed.

```

And finally...

```
FJṁa@ ... FQL<3   Main link.
F                 **F**latten.
 J                Indices. Get `[1,2,3,4,...]`
  ṁ               old (reshape) the array of indices to have the same
                  shape as the input.
   a@             Logical AND, with the order swapped. The zeroes in the input
                  mask out the array of indices.
      ...         Do whatever I described above.
          F       **F**latten again.
           Q      uni**Q**ue the list.
            L     the list of unique elements have **L**ength...
             <3   less than 3.

```
> 3 votes

# Answer
# Haskell, 132 bytes

```
 \m->null.snd.until(null.fst)(\(f,e)->partition(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f])e).splitAt 1.filter((/=0).(m!)).indices$m

```

extracted from Solve Hitori Puzzles

`indices m` lists the `(line,cell)` locations of the input grid.

`filter((/=0).(m!))` filters out all locations with non-zero values.

`splitAt 1` partitions off the first member into a singleton list next to a rest list.

`any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f]` tells if `(b,p)` touches the frontier `f`.

`\(f,e)->partition(\(b,p)->touches(b,p)f)e` splits off touchers from not\[yet\]touchers.

`until(null.fst)advanceFrontier` repeats this until the frontier can advance no further.

`null.snd` looks at the result whether all locations to be reached were indeed reached.

Try it online!
> 3 votes

# Answer
# Java 8, ~~226~~ ~~219~~ ~~207~~ ~~205~~ 201 bytes

```
int[][]M;m->{int c=0,l=m[0].length,i=m.length*l;for(M=m;i-->0;)c+=m[i/l][i%l]>0?f(i/l,i%l):0;return c<2;}int f(int x,int y){try{M[x][y]*=M[x][y]>0?f(x+f(x,y+f(x-f(x,y-1),y)),y)-1:1;}finally{return 1;}}

```

-2 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
int[][]M;              // Integer-matrix on class-level, uninitialized
m->{                   // Method with integer-matrix parameter & boolean return
  int c=0,             //  Amount of non-zero islands, starting at 0
      l=m[0].length,   //  Amount of columns in the matrix
      i=m.length*l;    //  Index integer
  for(M=m;             //  Set the class-level matrix to the input
      i-->0;)          //  Loop over the cells
    c+=                //   Increase the count by:
       m[i/l][i%l]>0?  //    If the current cell is not 0:
        f(i/l,i%l)     //     Flood-fill the matrix with a separated method
                       //     And increase the count by 1
       :               //    Else:
        0;             //     Leave the count the same
  return c<2;}         //  Return whether 0 or 1 islands are found

// Separated recursive method with cell input & integer return
int f(int x,int y){
  try{m[x][y]*=M[x][y]>0?
                       //  If the current cell is not 0:
           f(m,x,y-1)  //   Recursive call west
          f(m,x-...,y) //   Recursive call north
         f(m,x,y+...)  //   Recursive call east
        f(m,x+...,y)   //   Recursive call south
        -1:1;}         //   Empty the current cell
  }finally{            //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                       //  (shorter than manual if-checks)
           return 1;}  //  Always result in 1, so we use it to our advantage
                       //  to save bytes here by nesting, instead of having four
                       //  loose calls to each direction)

```
> 2 votes

# Answer
# Perl, ~~80~~ ~~79~~ ~~78~~ ~~73~~ 70 bytes

Includes `+2` for `0a`

Give the input matrix without spaces on STDIN (or in fact as rows separated by any kind of whitespace)

```
perl -0aE 's%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/'
000000
003510
010201
110316
720030
082629
000005
^D

```

Easier to read if put in a file:

```
#!/usr/bin/perl -0a
use 5.10.0;
s%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/

```
> 2 votes

# Answer
# Grime, 37 bytes

```
C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
e`C|:\0

```

Prints `1` for match and `0` for no match. Try it online!

## Explanation

The nonterminal `C` matches any nonzero character that is connected to the first nonzero character of the matrix in the English reading order.

```
C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
C=                             A rectangle R matches C if
  [,0]                         it is a single character other than 0
      &                        and
       <                       it is contained in a rectangle S which matches this pattern:
        e/\0{/e\0*0$e           R is the first nonzero character in the matrix:
        e                        S has an edge of the matrix over its top row,
         /0{/                    below that a rectangle of 0s, below that
             e\0*0$e             a row containing an edge, then any number of 0s,
                                 then R (the unescaped 0), then anything, then an edge.
                    |CoF^0oX    or R is next to another match of C:
                     CoF         S is a match of C (with fixed orientation)
                        ^0       followed by R,
                          oX     possibly rotated by any multiple of 90 dergees.

```

Some explanation: `e` matches a rectangle of zero width or height that's part of the edge of the input matrix, and `$` is a "wildcard" that matches anything. The expression `e/\0{/e\0*0$e` can be visualized as follows:

```
+-e-e-e-e-e-e-e-+
|               |
|      \0{      |
|               |
+-----+-+-------+
e \0* |0|   $   e
+-----+-+-------+

```

The expression `CoX^0oX` is actually parsed as `((CoF)0)oX`; the `oF` and `oX` are postfix operators and concatenation of tokens means horizontal concatenation. The `^` gives juxtaposition a higher precedence then `oX`, so the rotation is applied to the entire sub-expression. The `oF` corrects the orientation of `C` after it is rotated by `oX`; otherwise it could match the first nonzero coordinate in a rotated English reading order.

```
e`C|:\0
e`       Match entire input against pattern:
    :    a grid whose cells match
  C      C
   |     or
     \0  literal 0.

```

This means that all nonzero characters must be connected to the first one. The grid specifier `:` is technically a postfix operator, but `C|:\0` is syntactic sugar for `(C|\0):`.
> 2 votes

# Answer
# Python 2, ~~211~~ ~~163~~ 150 bytes

```
m,w=input()
def f(i):a=m[i];m[i]=0;[f(x)for x in(i+1,i-1,i+w,i-w)if(x>=0==(i/w-x/w)*(i%w-x%w))*a*m[x:]]
f(m.index((filter(abs,m)or[0])[0]))<any(m)<1>q

```

Try it online!

Output is via exit code. Input is as an 1d list and the width of the matrix.
> 1 votes

# Answer
# JavaScript (Node.js), ~~115~~ 102 bytes

```
A=>w=>(A.find(F=(u,i)=>u&&[-w,-1,1,w].map(v=>v*v>1|i%w+v>=0&i%w+v<w&&F(A[v+=i],v),A[i]=0)),!+A.join``)

```

Try it online!

Receive input as `(1d-array)(width)`. Rewrites all entries in one of the connected non-zero regions with 0 and checks whether the resultant array is a zero matrix. The matrix will become zero if there is zero or one connected non-zero region.

```
A=>                         // all rows are concatenated into an 1-d array
 w=>                        // width of the original matrix
  (
   A.find(                  // find the first non-zero entry
    F=(                     // helper function
     u,                     // value of the entry
     i                      // index of the entry
    )=>
     u                      // return 0 if value is 0 or out of range
     &&[-w,-1,1,w].map(     // return an array otherwise, and find the neighbors
      v=>                   // for each neighbor
       v*v>1                // if y-coord change: let go anyway
       |i%w+v>=0&i%w+v<w    // if x-coord change: let go only if on the same row
       &&F(A[v+=i],v),      // recurse on the neighbor
      A[i]=0                // before recursing change the current entry to 0
     )
   ),                       // if all entries were 0, no change is made
   !+A.join``               // return whether all entries are now 0
  )                         // if all entries are 0, then +A.join`` == 0

```

> **Tip:** Use `Array.prototype.find` if you want to map through an array with a function that the return values can be ignored but to stop once the function is executed.
>
> In this case, I want to map through the array to change only the first connected non-zero region found, but not the other regions (otherwise the array will become a zero matrix no matter what the original input is), so `find` is used here to save some bytes.
> 1 votes

# Answer
# JavaScript (Node.js), 96 bytes

```
f=(A,P,Q)=>!A.map((B,i)=>B.map((C,j)=>(P-i)**2+(Q-j)**2-1|!C||f(A,i,j,A[i][j]=0,P=0+[P])))|P>'0'

```

Try it online!

`P` = `0` if 1 chunk, `00` if 2 chunk, to allow call inside
> 1 votes

# Answer
# Uiua, 31 bytes

```
/×♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.

```

Try it online!

The same approach as ngn's APL answer.

```
∧↧1♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.    input: a matrix(n,m)
▽♭∶/⊂⇡△.  collect coordinates of positive numbers:
       ⇡△     coordinates of each position in the matrix (n,m,2)
     /⊂       reduce by join; flatten the first two dimensions
  ♭∶      .    original matrix flattened
▽             keep: for each number n in the matrix, get n copies of its coords
⊠(≤1/+⌵-).  create adjacency matrix:
⊠(      ).    self cross product over the coordinates:
   ≤1/+⌵-      sum of absolute difference is 1 or less?
⍥'∺'/↥↧.⧻.  get transitive closure:
⍥       ⧻.    run <length of the array> times:
  '∺'/↥↧.      self matrix product, using min as product and max as sum
/×♭         test if it is all ones

```
> 1 votes

# Answer
# 05AB1E, 42 bytes

```
Ā©˜ƶ®gäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]˜0KÙg!

```

Input as a matrix of integers; output as a 05AB1E truthy/falsey value (only \\$1\\$ is truthy in 05AB1E, so if the result is \\$\geq2\\$ it's falsey).

Try it online or verify all test cases.

**Explanation:**

Uses the same flood-fill algorithm I've used in multiple other challenges.

```
Ā             # Convert each positive integer in the (implicit) input-list to 1s
 ©            # Store this matrix in variable `®` (without popping)
  ˜           # Flatten it to a single list
   ƶ          # Multiply each by its 1-based index to make all values unique
    ®gä       # Convert it back to a matrix with the dimensions of `®`
Δ             # Loop until it no longer changes to flood-fill:
 2Fø0δ.ø}     #  Add a border of 0s around the matrix:
 2F     }     #   Loop 2 times:
   ø          #    Zip/transpose; swapping rows/columns
     δ        #    Map over each row:
    0 .ø      #     Add a leading/trailing 0
 2Fø€ü3}      #  Convert it into overlapping 3x3 blocks:
 2F    }      #   Loop 2 times again:
   ø          #    Zip/transpose; swapping rows/columns
    €         #    Map over each inner list:
     ü3       #     Convert it to a list of overlapping triplets
 ®*           #  Multiply each 3x3 block by the value in matrix `®`
              #  (so the 0s remain 0s)
 εεÅsyøÅs«à   #  Get the largest value from the horizontal/vertical cross of each 3x3
              #   block:
 εε           #   Nested map over each 3x3 block:
   Ås         #     Pop and push its middle row
     y        #     Push the 3x3 block again
      ø       #     Zip/transpose; swapping rows/columns
       Ås     #     Pop and push its middle rows as well (the middle column)
         «    #     Merge the middle row and column together to a single list
          à   #     Pop and push its maximum
]             # Close the nested maps, flood-fill loop, and outer loop
 ˜            # Flatten the resulting flood-filled matrix
  0K          # Remove all 0s
    Ù         # Uniquify the values of each island
     g        # Pop and push its length (which is 1 if it was a single island)
      !       # Factorial to convert 0 to 1 (and 1 remains 1), since 0 is also truthy
              # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Vyxal 3, 8 bytes

```
Þoᵛᵛa?∧₌

```

Try it Online!

```
Þoᵛᵛa?∧₌
Þo        # grid neighbors
  ᵛᵛa     # any truthy?
     ?∧   # Logical and with input
       ₌  # equals input

```

Created with the help of Luminespire.
> 1 votes

# Answer
# Perl 5, ~~131~~ 129 + 2 (`-ap`) = 133 bytes

```
push@a,[@F,0]}{push@a,[(0)x@F];$\=1;map{//;for$j(0..$#F){$b+=$a[$'][$j+$_]+$a[$'+$_][$j]for-1,1;$\*=$b||!$a[$'][$j];$b=0}}0..@a-2

```

Try it online!
> 0 votes

---
Tags: code-golf, decision-problem, graph-theory, matrix
---