title: Tips for storage in a golfing language

text:
# Question
Title: Tips for storage in a golfing language
I am writing a golfing language.

Do you suggest variables, stack(s), tapes, registers, etc for storage in a code-golf language? What about implicit input?

Rough definitions:

* A **variable** is simply a name (usually one character long in golfing languages) that a value can be assigned to, and later retrieved by that name.
* A **register** is like a variable, but it has its own (usually single-byte) commands for setting/getting the value.
* A **stack** is a variable-length array/list of values, where the most recently added values (the values "on top") are the ones that are being modified.
* A **queue** is like a stack, except the values "on the *bottom*" are the ones that are being modified.
* A **tape** is a static array/list of values where each value has an index. The main difference between a stack and a tape is that values on a tape are modified in-place.

I would appreciate to know the advantages and disadvantages of each option for different scenarios, and overall. Please avoid opinions, and backup statements with reasoning.

# Answer
> 4 votes
All of the storage types involve storing something at one point and retrieving it later. To do this in only one operation, you should do either storing or retrieving automatically, and specify the position of the stored value in the other operation.

That is, for explicit storage, you could create an operator to retrieve the nth calculated value before this operation, or put back the current value after n operations. Alternatively, you could use the absolute position from the start of the program, or do more things such as removing some elements automatically after some operations (like in a stack). You could also make multiple operators, retrieving from different copies of the storage with or without these automatic operations. And you should try to make the maximum number needed to specify in the operations reasonably small, so you could assign one operator for each number.

But in most cases, you don't even need an operator and the language will do this implicitly. That is when you need to consider a more standardized model such as stacks or queues. The most successful for now seemed to be tacit programming, which doesn't even mention storage directly.

If you want to design a new such model, you could try expanding the evaluations as a dag, and try to think of a default dag if nothing else is specified. Most likely, the default is just a tree, except for that multiple leaves may be linked to the same input. You could for example use a queue for a balanced tree, or a stack for a deep tree where leaves are mostly constant, or something like Jelly for a deep tree where leaves are mostly copies of the input.

But note that, you could encode the shape of a binary tree in only 2 bits per operator. So, if your language has less than 64 operators, you may actually ignore the traditional models and just encode the complete tree in the spare bits (call them combine\_parent and below\_leaf flags). Even if there are more operators, you could make a fairly good default (such as the model of Jelly) and 3 modifiers to change it.

You could use the same model for implicit and explicit storage for convenience, but you don't have to. For example, you could use a stack for implicit storage, but don't pop elements in the explicit storage (or in another explicit storage in addition to the implicit one). It's likely it won't be called a stack in the final documentation, but you get the idea.

For reference, the size of the perfect encoding of a binary tree is the logarithm of the Catalan numbers. And the size of the perfect encoding of a "binary" dag is the logarithm of A082161, but obviously impractical. This assumes an operator with different argument order two different operators, adding another bit when it is not.

Sometimes you may still want variables for the loops. It might be possible to rewrite the loops in other ways. But if you really need it, don't use a 1-byte construct in addition to a name to define the variable. unless you are only using the preinitialized values, it's usually more efficient to use a 1-bit flag to specify whether you are reading or writing this variable.

# Answer
> 6 votes
### I suggest all of them!

More seriously, they all come in handy some of the time, and the more the better! Implicit input is never *bad*, just have a flag to turn it off. Variables are helpful so they don't need to be found on a stack or tape; same with registers. Stacks are helpful to store data, and so are tapes. I recommend trying to implement multiple, say a stack *and* registers, or a stack and variables, like GolfScript. If you can make each function one byte, then your language will probably be effective at golfing, as you can use the advantages of each.

An example:

* Say I want to take two numbers as inputs, and add their string lengths
* Variables might be better for this (a stack might not)
* Example code in GolfScript (with implicit input):

```
~,\,+
~ # Eval input (e.g. "1 2" > 1, 2)
, # Take Length
\ # Reverse items on the stack
, # Take Length
+ # Add
  # Implicit output

```

However, with variables (I know it's longer, it just doesn't have to swap places on the stack):

```
~,:a;,:b;ab+
~ # Eval input
, # Get length
:a# Store in "a"
; # Discard value left on stack
, # Length
:b# Store in "b"
; # Discard
a # Recall a
b # Recall b
+ # Add
  # Implicit output

```

### Overloads

Another thing that can be helpful is overloads. For example, if you have a variable storing function, maybe it could be used as a monad (one-input function; I'm not sure of the term out side of J/K/APL) to add to the stack or tape.

Example:

```
c12 # Stores "1" into register 2
c1] # Pushes "1" onto the stack ("]" is used to denote the end of the monad)

```

# Answer
> 4 votes
I'd suggest having some quickly usable storage (from the given - tape, queue, stack) and some permanent storage (variables, registers) for things to not get in the way while the program is doing something unrelated. I'd say that much more would rarely give anything and leave more characters free for more 1-byte instructions.

From the definitions given, the ones I think would work the best would be a stack and registers.
A stack, because a tape has to use functions just to store a new thing in it, while a stack should have simple push and pop functions (usually built in the commands). Registers, because they take less bytes usually compared to variables and if you need to store more than 2-4 different things for something, you're doing something wrong.

Don't limit the functions of them only to what their names or definitions suggest trough - some functions like `put the 1st thing of the stack on top of the stack` can definitely help.

# Answer
> 4 votes
There are basically two sorts of storage that need to be handled differently; access to recently generated values and/or the inputs; and long-term storage.

For long-term storage, variables seem to work best; anything with a limited number of options doesn't scale (although languages with this property, like Jelly, nonetheless can do fairly well even on medium-sized tasks). However, there's no need to provide variable *names* when storing the variable, most of the time; just have a command to store a value in the variable, and autogenerate the names according to a predictable pattern so that storing and retrieving the value can be one command each in simple cases. (For example, you could have commands to restore the most recently assigned variable, the second most recently, the third most recently, and so on, up to a small fixed number, plus a general command that took an argument.)

For short term storage, you want as much to be implicit as possible. Almost all golfing languages I've seen connect the output of one command to an input of the next, by default; the exact way in which this is done differs from language to language but normally comes to the same thing. However, the second input for a 2-input command is more interesting. Taking it from a stack works well in cases where values are only used once, but doesn't scale well when reusing values. (Try to avoid stack manipulation primitives; if you have to resort to using them, you're wasting a lot of bytes.) Alternatively, using user input or a recently assigned variable as the implicit second argument tends to give a few byte savings on simple programs, although you'll then need a parenthesis equivalent to make it possible to place nontrivial expressions on both sides of a binary operator.

In a golfing language I'm working on at the moment, I use a combination of a very cheap mechanism (a single *bit*) to specify the shape of the parse tree, automatically filling in missing arguments from user inputs by default, and a checkpointing approach that makes it possible to set the default for missing arguments to something else (plus plenty of special cases). At some point I'm likely going to add variables to communicate information greater distances along the program.

# Answer
> 2 votes
## A stack is sufficient for a terse golfing language.

First of all, implicit input is always nice, it's indisputable (it saves a lot from your source code, see this 05AB1E tip.)

I created  as a language which only allows manipulations upon the stack. If you read W's instruction reference, you will realize that W has absolutely no support for queues or tapes. Also, it doesn't even have assignable variables and accumulators! However, it still manages to be competitive, as well as having a similar bytecount as other stack-based golfing languages.

In my opinion, if you ever need an accumulator/variable, there's always a shorter way to re-write your program that purely uses stack manipulation.

# Answer
> -1 votes
I suggest a tape and a register.

I prefer tapes over stacks because tapes tend to have fewer elements, making manipulation of them easy. Also, being able to place elements in the tape in the register and vice versa makes for easy, short code.

---
Tags: code-golf, tips, language-design, golfing-language
---


# Question
Title: Is this a legal date? - April Fools' edition
# Task

A date can be compactly represented in a 6-character string in the format `ddmmyy` where the first two characters (`dd`) represent a day, the 3rd and 4th characters (`mm`) represent a month and the last two characters (`yy`) represent a `20XX` year. Given a string with 6 characters in `[0-9]` determine if it represents a valid date. But because today (the day this was posted) is April Fools' day, we will have a twist in the way dates work:

## April Fools' dates

We will pretend every 30-day month has 31 days and every 31-day month has 30 days. Furthermore, in years when February is supposed to have 29 days we will pretend February only has 28 days and in all the other years we will pretend February has 29 days; i.e.:

* months `01`, `03`, `05`, `07`, `08`, `10` and `12` have `30` days;
* months `04`, `06`, `09` and `11` have `31` days;
* February has `28` days if the year `yy` is a multiple of `4`, otherwise February has `29` days (let us assume we are in the year `20yy`);

# Input

An integer in `[0 - 311299]` or a 0-padded string representation of such an integer.

# Output

A Truthy value if the input corresponds to a date as per the April Fools' dates, Falsy otherwise.

# Test cases

Python naïve implementation for your convenience.

```
"000511" -> False
"000611" -> False
"290200" -> False
"290204" -> False
"290208" -> False
"310004" -> False
"310005" -> False
"310104" -> False
"310105" -> False
"310204" -> False
"310205" -> False
"310304" -> False
"310305" -> False
"310504" -> False
"310505" -> False
"310704" -> False
"310705" -> False
"310804" -> False
"310805" -> False
"311004" -> False
"311005" -> False
"311204" -> False
"311205" -> False
"311304" -> False
"311305" -> False
"311404" -> False
"311405" -> False
"010694" -> True
"031288" -> True
"050199" -> True
"050298" -> True
"050397" -> True
"060496" -> True
"070595" -> True
"100793" -> True
"150892" -> True
"181189" -> True
"200991" -> True
"251090" -> True
"280200" -> True
"280201" -> True
"280202" -> True
"280203" -> True
"280204" -> True
"280205" -> True
"280206" -> True
"280207" -> True
"280208" -> True
"290201" -> True
"290202" -> True
"290203" -> True
"290205" -> True
"290206" -> True
"290207" -> True
"310404" -> True
"310405" -> True
"310604" -> True
"310605" -> True
"310904" -> True
"310905" -> True
"311104" -> True
"311105" -> True

```

This challenge was inspired by this one.

---

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!

# Answer
> 15 votes
# JavaScript (ES6),  ~~62 60~~  59 bytes

Takes input as a 0-padded string. Returns \\$0\\$ for *false* or a positive integer for *true*.

```
s=>(m=s[2]+s[3])<13&31-(m^2?~m%9%2:s%4?1:2)>(s/=1e4)&&~~s*m

```

Try it online!

or Check all possible outputs against an ungolfed implementation

### Commented

```
s =>                // s = input string
  (m = s[2] + s[3]) // m = month, as a string
  < 13 &            // make sure that m is less than 13
  31 - (            // compute the upper bound for this month:
    m ^ 2 ?         //   if the month is not February:
      ~m % 9 % 2    //     use either 31 or 32
    :               //   else:
      s % 4 ?       //     if this is not a leap year:
        1           //       use 30
      :             //     else:
        2           //       use 29
  )                 // end of upper bound computation
  > (s /= 1e4)      // make sure that it's greater than the day
  && ~~s * m        // and finally make sure that day * month is not zero

```

# Answer
> 7 votes
# Python 3.8, ~~77~~ ~~67~~ ~~65~~ ~~62~~ 61 bytes

*-2 bytes thanks to @Bubbler*
*-3 bytes thanks to @xnor*
*-1 byte thanks to @PoonLevi's mod by float trick*

```
lambda s:13>(m:=s//100%100)>0<s//1e4<30-[s%4<1,m%-1.76][m!=2]

```

Try it online!

**Input**: Date as an integer.
**Output**: `True` or `False` if the date is valid or invalid respectively.

**How**:

Overall approach: return `13 > m > 0 < d < max_date_of_month` where `d, m` are date and month respectively.
The max date of month `m` is calculated as:

* If `m==2`: `30-(s%4<1)` evaluates to `29` if the year is divisible by 4, and `30` otherwise. Since the year is the last 2 digits of the input, input mod 4 is the same as the year mod 4.
* If `m!=2`: `30-m%-1.76` evaluates to `31.xxx` or `30.xxx`

---

### Old solution

### Python 3.8, ~~86~~ ~~83~~ 71 bytes

```
lambda s:13>(m:=s//100%100)>0<s//1e4<29+[s%4>0,([3,2]*7)[m+m//8]][m!=2]

```

Try it online!

**Input**: Date as an integer.
**Output**: `True` or `False` if the date is valid or invalid respectively.

**How**: `([3,2]*7)[m+m//8]` first creates a list storing the `max_date + 1` for each month (except February) by repeating `[3, 2]` a few times. If the month is August or after, the pattern switches, so we add 1 to the index.

# Answer
> 5 votes
# Retina 0.8.2, ~~96~~ ~~93~~ ~~91~~ 81 bytes

```
^(?!(..)?00|..[2-9]|..1[3-9]|31(?!0[469]|11)|3002|2902([02468][048]|[13579][26]))

```

Try it online! Link includes test cases. Edit: Saved 3 bytes thanks to @mathjunkie. Saved 2 bytes thanks to @ThomasAyoub. Saved a further 10 bytes thanks to @ThomasAyoub for noting that the day cannot be greater than 31. Explanation:

```
^

```

Match only at the beginning of the string.

```
(?!...)

```

Invert the condition so we're now looking for invalid dates. The invalidity conditions (separated by `|` in the original code) are as follows:

```
(..)?00

```

Either the day or month are zero.

```
..[2-9]

```

The month is 20 or higher.

```
..1[3-9]

```

The month is between 13 and 19.

```
31(?!0[469]|11)

```

The day is 31 and the month is not 4, 6, 9 or 11.

```
3002

```

February 30th.

```
2902([02468][048]|[13579][26])

```

February 29th on a leap year.

# Answer
> 4 votes
# Jelly, 28 bytes

```
Ɠ⁽¿ÇB31_+2¦4ḍ~ƊR;€"J$ḅ³Fċ:³$

```

A full program accepting a single integer from STDIN which prints a `1` or `0` to STDOUT.

**Try it online!** Or see the test-suite.

### How?

```
Ɠ⁽¿ÇB31_+2¦4ḍ~ƊR;€"J$ḅ³Fċ:³$ - Main Link
Ɠ                            - set the chain's left argument, N, to evaluated STDIN
 ⁽¿Ç                         - base 250 integer = 3765
    B                        - to binary     = [1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1]
     31_                     - 31 minus      = [30,30,30,31,30,31,30,30,31,30,31,30]
              Ɗ              - last three links as a monad - f(N):
           4ḍ                -   four divides (N)?
             ~               -   bitwise NOT (0 becomes -1 and 1 becomes -2)
          ¦                  - sparse application...
         2                   - ...to indices: [2]
        +                    - ...action: add
                               i.e. x=9 or 8: [30,2x,30,31,30,31,30,30,31,30,31,30]
               R             - range (vectorises) = [[1,2,...30],...]
                    $        - last two links as a monad - f(that):
                   J         -   range of length = [1,2,...,12]
                  "          -   zip with:
                ;€           -     concatenate each -> [[[1,1],[2,1],...,[30,1]],...]
                     ḅ       - convert from base (vectroises):
                      ³      -   100               -> [[101,201,...,3001],...]
                       F     - flatten
                        ċ    - count occurrences of:
                           $ -   last two links as a monad - f(N):
                         :   -     (N) integer divide:
                          ³  -       100

```

# Answer
> 3 votes
# 05AB1E, 34 bytes

```
2ô¨Ðθ©13‹sĀPr`2QiI4Ö≠ë®7(%ÉÌ}29+‹P

```

Just an initial answer. Can definitely be golfed by a few bytes.
Inspired by both *@Arnauld*'s JavaScript answer and *@SurculoseSputum*'s Python answer, so make sure to upvote them!!

Try it online or verify all test cases.

**Explanation:**

```
2ô             # Split the (implicit) input in parts of size 2: ddmmyy → [dd,mm,yy]
  ¨            # Remove the last item (the year): [dd,mm]
   Ð           # Triplicate this
               #  STACK: [[dd,mm],[dd,mm],[dd,mm]]
    θ          # Pop and push the last item
               #  STACK: [[dd,mm],[dd,mm],mm]
     ©         # Store the month in variable `®` (without popping)
      13‹      # Check that it's smaller than 13
               #  STACK: [[dd,mm],[dd,mm],mm<13]
   s           # Swap to get the triplicate value again
               #  STACK: [[dd,mm],mm<13,[dd,mm]]
    ĀP         # Check for both that they're not 0
               #  STACK: [[dd,mm],mm<13,(dd!=0)*(mm!=0)]
   r           # Reverse the stack
               #  STACK: [(dd>0)*(mm>0),mm<13,[dd,mm]]
    `          # Push both values separately to the stack
               #  STACK: [(dd>0)*(mm>0),mm<13,dd,mm]
     2Qi       # If the month is 2:
        I4Ö≠   #  Check that the input is NOT divisible by 4
               #   STACK: [(dd>0)*(mm>0),mm<13,dd,input%4>0]
       ë       # Else:
        ®7(%É  #  Check that the month (from variable `®`) modulo -7 is odd
               #   STACK: [(dd>0)*(mm>0),mm<13,dd,mm%-7%2>0]
             Ì #  And increase this by 2
               #   STACK: [(dd>0)*(mm>0),mm<13,dd,(mm%-7%2>0)+2]
       }29+    # After the if-else: add 29 to this value
               #  STACK: [(dd>0)*(mm>0),mm<13,dd,(input%4>0)+29] if mm == 2
               #  STACK: [(dd>0)*(mm>0),mm<13,dd,(mm%-7%2>0)+31] if mm != 2
           ‹   # Check that the dd is smaller than this value
               #  STACK: [(dd>0)*(mm>0),mm<13,dd<(input%4>0)+29] if mm == 2
               #  STACK: [(dd>0)*(mm>0),mm<13,dd<(mm%-7%2>0)+31] if mm != 2
            P  # And take the product of the stack to check if all are truthy
               #  STACK: [(dd>0)*(mm>0)*(mm<13)*(dd<(input%4>0)+29)] if mm == 2
               #  STACK: [(dd>0)*(mm>0)*(mm<13)*(dd<(mm%-7%2>0)+31)] if mm != 2
               # (after which this is output implicitly as result)

```

# Answer
> 2 votes
# Python 3.8, ~~136~~ \\$\cdots\\$~~93~~ 78 bytes

Takes the date as an integer and returns Truthy or Falsy.

```
lambda s,h=100:13>(m:=s//h%h)>0<s//h//h<(30-(s%4<1),31+(m in(4,6,9,11)))[m!=2]

```

Try it online!

# Answer
> 2 votes
# Perl 5 `Mbigint -p`, ~~76~~ 75 bytes

```
/(..)(..)/;$_=$1>0&&$1<substr 113130-($_%4?0:1).31323132313132313231,2*$2,2

```

Try it online!

# Answer
> 2 votes
# C (gcc), ~~95~~ \\$\cdots\\$ ~~71~~ 65 bytes

Saved ~~3~~ 4 bytes thanks to ceilingcat!!!
Saved a whopping 15 bytes thanks to Olivier Grégoire!!!
Saved 6 bytes thanks to Arnauld!!!

Takes the date as an integer and returns \\$0\\$ or \\$1\\$.

```
m;f(s){m=s/100%100;s=m<13&(m-2?~m%9%2-1:s%4<1)+(s/=1e4)<30&&s*m;}

```

Try it online!

# Answer
> 2 votes
# Java (JDK), 74 bytes

```
n->{int m=n/100%100;return(m==2?n%4<1?2:1:~m%9%2)<31-(n/=1e4)&13>m&n*m>0;}

```

Try it online!

## Credits

# Answer
> 2 votes
# Bash \+ GNU utilities, ~~86~~ ~~85~~ ~~83~~ 82 bytes

```
a=0424343443434;fold -2|xargs|(read d m y;date -d${a:${m#0}:1}/$d/0$[!(${y#0}%4)])

```

Try it online!

Input is on stdin.

Output is the exit code: `0` for truthy, `1` for falsey.

---

I thought I'd do a solution based on a date built-in, since I don't think anyone else has done that yet.

This program takes the input string \\$x\\$ and computes another string \\$y\\$ with the property that \\$x\\$ is a valid "April Fools date" iff \\$y\\$ is a valid normal date. So GNU date applied to \\$y\\$ will give the desired answer.

# Answer
> 2 votes
# Swift ~~279~~ ~~277~~ ~~272~~ ~~264~~ ~~262~~ ~~257~~ ~~256~~ ~~254~~ 252 bytes

```
func v(s:String)->Int{let m=Int(s.suffix(4).prefix(2))!;switch m{case 0,13...:return 0;case _:switch Int(s.prefix(2))!{case 1...28:return 1;case 29,30:return Int(s.suffix(4))!%4==0&&m==2 ?0:1;case 31:return[4,6,9,11].contains(m) ?1:0;case _:return 0}}}

```

My first and most probably failed attempt at code golf. Please be nice!

Here is a more readable version:

```
func validDate(s :String) -> Int {
    let mm = Int(s.suffix(4).prefix(2))!
    switch mm {
    case 0,13...:
        return 0
    case _:
    switch Int(s.prefix(2))! {
    case 1...28:
        return 1
    case 29, 30:
        return Int(s.suffix(4))! % 4 == 0 && mm == 2 ? 0: 1
    case 31:
        return[4,6,9,11].contains(mm) ? 1:0
    case _:
        return 0
    }
  }
}

```

Any constructive feedback is welcome, negative feedback not so welcome.

Link to project with swift tests on Github

**Updated solution** to make it work for console input

# ~~288~~ ~~251~~ 249 bytes

```
let s=readLine()!;let m=Int(s.suffix(4).prefix(2))!;let d=Int(s.prefix(2))!;if m<0||m>13{print(0)};if(1...28).contains(d){print(1)}else if d==29||d==30{print(!(Int(s.suffix(4))!%4==0&&m==2))}else if d==31{print([4,6,9,11].contains(m))}else{print(0)}

```

Try it online

# Answer
> 2 votes
# JavaScript (Node.js), 53 bytes

```
s=>`2${s&3&&1}2323223232`[s[2]+s[3]-1]>s/1e4-29&s>1e4

```

Try it online!

# Answer
> 1 votes
# Raku (raku -n file-with-one-line) 118 Bytes

```
/(..)(.)(.)(..)/;$!=10*$1+$2;die if 12 <$!||1>$!;$!=7.5-abs(7.5-$!);$!=($!+|4)+^1 if $!!= 2;Date.new($3%4??0!!1,$!,$0)

```

Result as exit code (0: ok, 1: error)

---
Tags: code-golf, decision-problem, date
---


title: Parse a Baseball Pitch String

text:
# Question
Title: Parse a Baseball Pitch String
Take an arbitrarily sized string as input. This string represents a baseball plate appearance, in which each character represents a pitch as follows:

* Strike: `S`
* Ball: `B`
* Foul ball: `F`
* Hit by pitch: `H`
* Ball in play: `X`

(For those wondering, this is a very *very* simplified version of Retrosheet's notation)

---

Your program must output 1 of 3 possible outputs to signify 1 of the mutually exclusive outcomes:

* Strikeout
* Walk
* Ball in play

It doesn't matter what the outputs are exactly, as long as they are *guaranteed* to be distinct.

---

For those unfamiliar with the rules of baseball:

* 3 strikes results in a strikeout
* 4 balls results in a walk
* A foul ball is a strike UNLESS the batter already has 2 strikes, in that case nothing happens
* Hit by pitch immediately results in a walk
* "Ball in play" immediately results in the "Ball in play" outcome

---

You may assume that:

* the input string is encoded as ASCII
* the input string represents an *entire* plate appearance (in other words it *will* end in one of the 3 outcomes above)
* there are no other characters other than the ones above

You may **not** assume that:

* there are no extra pitches/characters after the plate appearance is supposed to legally end
* your program must return on the last pitch/character

---

Examples:

"Strikeout"fy:

```
SSS
SBSBS
BBBSSS
BSBSBS
BSFFBFS
BBSSFFFFFFFFS
SSSBBBB
FSS

```

"Walk"y:

```
BBBFB
BBBB
BBBSB
SSBBBB
SSH
SBSFFBFFFFBFFFFFFFFB
BBBBSSS
HSSS
SBBBBSS

```

"Ball in play"ly:

```
X
SSX
BBBX
SBSX
FFFFFFFFFFFFFFX
XBSBSBSB

```

---

This is , so fewest bytes wins.

(This challenge was inspired by this YouTube video)

# Answer
> 10 votes
# Retina 0.8.2, 22 bytes

```
4=`B
H
2`F|S

1!`[XHS]

```

Try it online! Link includes test cases. Outputs `X` for ball in play, `H` for walk, and `S` for strikeout. Explanation:

```
4=`B
H

```

The fourth ball results in a walk, same as hit by pitch.

```
2`F|S

```

The first two foul balls/strikes are ignored.

```
1!`[XHS]

```

Take the first available result.

# Answer
> 7 votes
# JavaScript (ES9),  ~~68 66~~  55 bytes

*Saved 11 bytes thanks to @Neil!*

Returns \\$S\\$ for *Strikeout*, \\$X\\$ for *Ball in play* or an empty string for *Walk*.

```
s=>/(?<=(B.*){4})|(?=H)|X|(?<=([SF].*){2})S/.exec(s)[0]

```

Try it online!

### How?

We match either:

* `(?<=(B.*){4})` : an empty string preceded by 4 `B`'s
* `(?=H)` : an empty string followed by an `H`
* `X` : the character `X`
* `(?<=([SF].*){2})S` : an `S` preceded by 2 other strike characters (`S` or `F`)

As a result, we get an `S` for a *Strikeout*, an `X` for a *Ball in play*, or an empty string for a *Walk*.

# Answer
> 5 votes
# Python 3, ~~90~~ ~~88~~ ~~86~~ 85 bytes

*-2 bytes thanks to @ovs*

```
s=b=0
for i in map(ord,input()):s+=~i%2*~s*i%71<3;b+=i<67;b//4+s//3==i%4//2>exit(i%6)

```

Try it online!

Returns via exit code: `0` for a walk, `4` for ball-in-play, and `5` for a strikeout.

# Answer
> 4 votes
# SNOBOL4 (CSNOBOL4), 172 bytes

```
	I =INPUT
N	I LEN(1) . P REM . I	:($P)
S	S =LT(S,2) S + 1	:F(K)S(N)
B	B =LT(B,3) B + 1	:F(H)S(N)
F	S =LT(S,2) S + 1	:(N)
X	OUTPUT =0	:(E)
K	OUTPUT =1	:(E)
H	OUTPUT =2
E
END

```

Try it online!

`0` for a ball in play, `1` for a strikeout, and `2` for a walk.

gosh, I miss baseball :-(

*Thanks to Mitchell Spector for pointing out several bugs!*

# Answer
> 4 votes
# 05AB1E, ~~28~~ ~~26~~ ~~24~~ ~~22~~ 20 bytes

```
Ç.Δ6Ö½$¾4@N¾Ì@)yè}6%

```

Try it online!

Outputs 5 for strike out, 0 for walk, or 4 for ball in play.

```
Ç                   # convert the input to a list of ASCII codepoints
 .Δ              }  # find the first codepoint y such that:
   6Ö               #  is y divisible by 6? (true for B and H only)
     ½              #  if yes, increment the counter variable c
      $             #  push 1 and input
       ¾4@          #  is c >= 4?
          N¾Ì@      #  is the iteration count N >= c + 2?
              )     #  wrap the stack in a list: [1, input, c >= 4, N >= v + 2]
               yè   #  get the y-th element of that list (wraps around)

# * H and X are mapped to 1, so those characters always result in a match
# * nothing is mapped to `input`, it's just there to pad the list
# * B and F are mapped to `c >= 4`, so the 4th B results in a match (this would also
#   match HBBB or BBBBF, but we stop after the first match, so that's irrelevant)
# * S is mapped to `N >= c + 2`, so an S matches if it's preceded by at least 2 characters not in (B, H)

6%                  # after the loop: modulo 6 (B => 0, H => 0, S => 5, X => 4)

```

# Answer
> 3 votes
# C (gcc), ~~124~~ \\$\cdots\\$ ~~87~~ 86 bytes

Saved ~~12~~ 13 bytes thanks to ceilingcat!!!
Saved 6 bytes thanks to dingledooper!!!

```
c;b;s;f(char*p){for(b=s=0;c=*p++-66,s+=c==4&s<2|c==17,b+=!c,c!=6&b<4&s<3&c<22;);c%=3;}

```

Try it online!

Returns \\$0\\$ for a walk, \\$1\\$ for a ball in play, and \\$2\\$ for a strikeout.

# Answer
> 2 votes
# Retina 0.8.2, ~~42~~ 41 bytes

*Thanks to @Neil for saving a byte!*

```
(?<=(B.*){3})B
H
1!`X|H|(?<=([SF].*){2})S

```

Try it online!

Based on @Arnauld's JavaScript answer.

Returns `X` for ball-in-play, `H` for a walk, and `S` for a strikeout.

# Answer
> 2 votes
# Io, 142 bytes

Returns `0` for a strikeout, `5` for a walk, `4` for a ball-in-play.

```
method(I, s :=b :=0
I foreach(i,s=s+i%2+if((s-1)*i%69<3,1,0);b=b+if(i<67,1,0);if(((b/4)floor!=0)or(i%8<1)or((s/3)floor!=0),System exit(i%6))))

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 32 bytes

```
ηε.•Çšy•uS¢`+3@y'SÅ¿*·s4@r;M}0Kн

```

Outputs `2` for Strikeout; `1` for Walk; and `0.5` for Ball in play.

Try it online or verify all test cases.

Could be **31 bytes** by removing the `u` if we can take the input as lowercase.

**Explanation:**

```
η              # Get all prefixed of the (implicit) input-string
 ε             # Map each prefix to:
  .•Çšy•       #  Push compressed string "xhbsf"
        u      #  Convert it to uppercase: "XHBSF"
         S     #  Convert it to a list of characters: ["X","H","B","S","F"]
          ¢    #  Count each character in the current prefix-string
  `            #  Push the counts separated to the stack
   +           #  Add the counts of "S" and "F" together
    3@         #  Check that it's >= 3
           *   #  And:
      y'SÅ¿   '#  Check whether the current prefix ends with an "S"
            ·  #  And double this combined check (so 2 if truthy; 0 if falsey)
   s           #  Swap so the count of 'B' is at the top of the stack
    4@         #  Check that it's >= 4 (1 if truthy; 0 if falsey)
   r           #  Reverse the stack, so the count of 'X' is at the top of the stack
    ;          #  Halve it (0.5 if truthy; 0.0 if falsey)
  M            #  Push the largest value of the stack
 }0K           # After the map: remove all 0s
    н          # And pop and push the first value of the list
               # (after which it is output implicitly as result)

```

Note that this assumes the count of `"H"` and `"X"` can never be larger than 1, which we can due to the assumptions mentioned in the challenge description.

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•Çšy•` is `"xhbsf"`.

# Answer
> 1 votes
# sed -E, ~~69~~ ~~60~~ 59 bytes

```
s/([FS][^FS]*){2}S/&K/;s/([^B]*B){4}/&H/;s/[^KHX]*(.).*/\1/

```

Try it online!

*9 bytes off, thanks to math junkie.*

Input on stdin.

Output on stdout: H for walk, K for strikeout, X for in play.

# Answer
> 1 votes
# \[C#\], 147 bytes

```
d=(p,s,b,i)=>{var P=p[i];int t=0;if(P=='B')b++;if(P=='S'||(P=='F'&&s<2))s++;if(P=='H'||b>3)t=2;if(P=='X')t=3;if(s>2)t=1;return t!=0?t:d(p,s,b,++i);};

```

Try It online!

Return values: 1 = Strikeout, 2 = Walk, 3 = Ball in play.

(I wanted to use recursion for this answer, for learning)

# Answer
> 1 votes
# Z80Golf, 49 bytes

```
00000000: 0603 0e04 cd03 80fe 5320 0105 fe42 2001  ........S ...B .
00000010: 0dfe 4620 0310 0104 fe48 2001 4afe 5828  ..F .....H .J.X(
00000020: 0caf b93e 5728 06af b820 d93e 53cd 0080  ...>W(... .>S...
00000030: 76                                       v

```

Try it online!

Prints W for walk, S for strikeout, and X for ball in play.

## Ungolfed

```
        ld b,3  ; number of strikes until strikeout
        ld c,4  ; number of balls until walk
input:
        call $8003      ; A = next character from stdin
strike:
        ; if A == 'S', record a strike
        cp 'S'
        jr nz,ball
        dec b
ball:
        ; if A == 'B', record a ball
        cp 'B'
        jr nz, foul
        dec c
foul:
        ; if A == 'F',
        cp 'F'
        jr nz, hit_by_pitch
        ; record a strike
        ; jump to the next section if batter hasn't struck out
        djnz hit_by_pitch
        ; if batter has struck out, give them another chance
        ; foul balls can't strike out a batter
        inc b
hit_by_pitch:
        cp 'H'
        jr nz, ball_in_play
        ld c, d ; d is initialized to 0 by default
ball_in_play:
        cp 'X'
        jr z, exit
walk:
        xor a   ; 1 byte shorter than ld a, 0
        cp c
        ld a, 'W'
        jr z, exit
strikeout:
        xor a
        cp b
        jr nz, input
        ld a, 'S'
exit:
        call $8000
        halt

```

# Answer
> 0 votes
# Charcoal, 52 bytes

```
≔⪪Ｓ¹θＦ⪪B34HF02SS02F⁴Ｆ✂⌕Ａθ§ι⁰Ｉ§ι¹Ｉ§ι²§≔θκ§ι³§Φθ№XHSι⁰

```

Try it online! Link is to verbose version of code. Outputs `X`, `H` or `S` as appropriate. Explanation:

```
≔⪪Ｓ¹θ

```

Split the input string into an array of characters. (If that is a legal input format, then these 5 bytes could be removed, but it would be really hard to enter in any of the examples.)

```
Ｆ⪪B34HF02SS02F⁴

```

Iterate over a string literal which encodes the following rules: The fourth Ball counts as a Hit by pitch. The first two Fouls might count as Strikes. The first two Fouls or Strikes don't strike the batsman out so turn them back into Fouls.

```
Ｆ✂⌕Ａθ§ι⁰Ｉ§ι¹Ｉ§ι²

```

Find the range of matches of the source character that we're interested in.

```
§≔θκ

```

Update those matches with the destination character.

```
§ι³§Φθ№XHSι⁰

```

Filter out all characters except `X`, `H` and `S` and output the first remaining character.

# Answer
> 0 votes
## Javascript, 84 characters

```
z=>{y={B:-1,S:i=0,F:0};while(c=z[i++],d={H:'B',F:'S'}[c]||c,y[d]++,y[c]<3);return d}

```

Returns S, X or B for a strike-out, on-base or walk.

Auto-formatted version:

```
f = (z) => {
    y = { B: -1, S: (i = 0), F: 0 };
    while (((c = z[i++]), (d = { H: 'B', F: 'S' }[c] || c), y[d]++, y[c] < 3));
    return d;
};

```

# Answer
> 0 votes
# Foxrabbit's Finite-State Binary (FSB), 57 bytes

The 57 bytes in hexadecimal are:

```
01
04 43 04 01
06 47 08 02
06 49 0c 03
06 54 09 0c
00 00 05 05
02 04 06 07
01 00 00 00
02 48 07 0c
01 02 0a 0b
01 00 0a 0a
02 03 0b 0c
00 00 00 00
05 00 0d 0d
07 00 0d 0d

```

Assumes an ASCII-superset environment. Outputs a single byte with value 3 for strike-out, value 72 (ASCII 'H') for walk, or value 88 (ASCII 'X') for ball in play.

As an FFM program:

```
Get;inp;67;Ball:NotB
NotB;nop;71;Foul:NotBF
NotBF;nop;73;Print:NotBFH
NotBFH:nop;84;Strike:Print
Ball;lft;0;CountBall:CountBall
CountBall;inc;4;BallRet:SetH
BallRet;rgt;0;Get:Get
SetH;inc;72;SetH:Print
Foul;rgt;2;CountStrike:StrikeRet
Strike;rgt;0;CountStrike:CountStrike
CountStrike;inc;3;StrikeRet:Print
StrikeRet;lft;0;Get:Get
Print;out;0;End:End
End;hlt;0;End:End

```

The VM for both languages is a finite-state machine with access to an infinite tape of byte values. I used the initial tape cell for the most recent input character, the cell to the right for the number of strikes, and the cell to the left for the number of balls.

Try it online! In that link, the header and footer are the FFB interpreter written in Python and linked from the esolangs page, but modified a little to take an `io.BytesIO` instead of opening a binary file, and to skip the `chr` on an output instruction (since a printed byte 3 is annoying to verify). So the output there will be the decimal string "3", "72", or "88".

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


title: Are you ready to meet the Elite-Four?

text:
# Question
Title: Are you ready to meet the Elite-Four?
To be able to challenge the Elite-4 of top programmers, you need to show your badges first, that qualify you as a potential programmer-master. However, there's a twist. Once you show a badge, it is collected, which means you can't re-show it. So better come prepared! There are `n` badge collectors, each has a known list of `accepted_badges`. Given a list of your `badges`, your task is to find out, if you can access elite-four or if you require more badges. You can indicate this by printing a truthy-value for the first case or a falsey-value in the second case.

**Example**

```
accepted_badges: [ [a, b, c], [a, b, d], [d, e, f]]

```

If you have the badges `[a, b, d]` you can pass. Simply give your `a` badge to the first collector (`accepted_badges[0]`), your `b` badge to the second and your d badge to the last collector. So this is a truthy case.

If you have the badges `[a, b, c]` you are in bad luck. The last collector doesn't accept any of it.

If you have the badges `[b, c, d]` you can also pass. Here you will need to give your `c` badge to the first collector, the `b` badge to the second and the final collector will get the `d` badge.

If you have the badges `[a, e, f]` you will not be admitted, because you would have to use your a badge twice (since the first collector takes it away from you), which is not possible.

**Input:**

> A list\* of your badges
> A 2Dlist\* of badge collectors and their accepted badges

\*list can be the following:

```
1. a list, i.e. [a, b, c, ...] or [[a,b,c],[c,d,e]]
2. a list with first element = number of elements i.e. [3, a, b, c] or [ [2], [3, a, b, c], [1, a]]
2. a string     "abcd..."
3. a string with leading number of elements i.e. "3abc"
4. a seperated string i.e. "abc,def,ghi"
5. a separated string with leading numbers of elements i.e. "3abc,2ab,5abcdef"
6. or any other convenient input format you can think of

```

**Assumptions:**

You may assume:

* any list to never be empty
* input letters to always match `[a-z]`
* your number of badges matches the number of badge collectors

You may not assume:

* that any list is sorted

**Test cases (list format):**

```
['a','b','c','d']
[['a','b','c'],['d','e','f'],['b','c','d'], ['c', 'g']]
Truthy

['a', 'a', 'a']
[['a', 'b', 'c'], ['a', 'd', 'e'], ['a', 'b', 'e', 'f']]
Truthy

['a', 'a', 'f']
[['a', 'c', 'f'], ['a', 'd'], ['b', 'c']]
Falsey

['x', 'y', 'z', 'w']
[['x', 'y'], ['x', 'y'], ['z', 'w'], ['x', 'y']]
Falsey

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r'], ['r', 'q', 'p'], ['r'], ['s', 't'], ['p', 'q', 'r', 's', 't']]
Truthy

['p', 'q', 'r', 's', 't']
[['p', 'q', 'r', 's', 't'], ['p', 'q', 'r', 's'], ['p', 'q', 'r'], ['p', 'q'], ['p']]
Truthy

```

**Test cases (String format):**

```
"abcd"
"abc def bcd cg"
Truthy

"aaa"
"abc ade abef"
Truthy

"aaf"
"acf ad bc"
Falsey

"xyzw"
"xy xy zw xy"
Falsey

"pqrst"
"pqr rqp r st pqrst"
Truthy

"pqrst"
"pqrst pqrs pqr pq p"
Truthy

```

Lastly, this is so the answer with the least number of bytes wins. Please refrain from using any standard-loopholes.

# Answer
# 05AB1E, 8 bytes

```
.»â€˜JIå

```

Try it online!
> 1 votes

# Answer
# Python 2, 68 bytes

One of the few cases where itertools is useful.

```
lambda b,a:s(b)in map(s,product(*a))
s=sorted
from itertools import*

```

Try it online!
> 9 votes

# Answer
# Python 2, 70 bytes

```
f=lambda s,l:l and any(f(s.replace(x,'',1),l[1:])for x in l[0])or''==s

```

Try it online!

Tries every possible character from each list entry in turn, removing it from the target string `s` if present, and checking if we end up with the empty string. The `s.replace(x,'',1)` removes at most one copy of `x` in the string `s`.

An annoying issue is that in the base case where `l==[]`, we get an error when we try to read `l[0]` even if the result doesn't matter, making it hard to cut the `l and`. It "almost" works to save a byte as below, but we get an error when `l` becomes empty because the `l[0]` is evaluated before the `if l` is tested and fails.

```
f=lambda s,l:s==''or any(f(s.replace(x,'',1),l[1:])for x in l[0]if l)

```

Try it online!

**69 bytes**

```
f=lambda s,l:any(f(s.replace(x,'',1),l[1:]+[[]])for x in l[0])or''==s

```

Try it online!

Pad `l` to the right with empty lists.

**69 bytes**

```
f=lambda s,h,*t:t and any(f(s.replace(x,'',1),*t)for x in h)or s in h

```

Try it online!

Takes input as the target string, followed by a splatted list of lists.

---

## 69 bytes

```
f=lambda s,l:any(f(s.replace(x,'',1),l[x in l[0]:])for x in s)or[]==l

```

Try it online!

A "dual" method based on ovs' solution, iterating over characters in the target string and removing from the list.
> 6 votes

# Answer
# Haskell, 54 bytes

```
import Data.List
(.permutations).any.flip elem.mapM id

```

Try it online!

# Without imports, 85 bytes

```
x#[]=[[x]]
x#(a:b)=(x:a:b):map(a:)(x#b)
(.foldr((=<<).(#))[[]]).any.flip elem.mapM id

```

Try it online!
> 5 votes

# Answer
# Python 2, 79 bytes

```
f=lambda a,b:a==[]or any(f(a[x in a[0]:],b[:i]+b[i+1:])for i,x in enumerate(b))

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 9 bytes

*-1 byte thanks to @KevinCruijssen*

```
œεøε`¢]PZ

```

Try it online!
> 3 votes

# Answer
# Haskell, ~~66~~ 65 bytes

Port of my Python answer.

-1 byte thanks to @AdHocGarfHunter.

```
b#(a:s)=or[x!b#s|x<-a,elem x b]
b#x=1>0
x!(a:b)|a==x=b|w<-x!b=a:w

```

Try it online!
> 3 votes

# Answer
# Erlang (escript), 138 bytes

Aaargh! Erlang's cartesian product is eeeeevil! (It saved 20 bytes anyway.)

```
f(A,B)->lists:member(lists:sort(A),[lists:sort(tuple_to_list(C))||C<-sofs:to_external(sofs:product(list_to_tuple([sofs:set(I)||I<-B])))]).

```

Try it online!

# Explanation

Here `...` stands for nest the previous line inside this position.

f(A,B)-> % Take 2 items.
[sofs:set(I)||I<-B] % Convert every item of B into a sofs set

list_to_tuple(...) % Convert the input list into a tuple

sofs:product(...)  % Cartesian product of this set tuple

sofs:to_external(...) % Pick the value of the cartesian product

C<-...            % Assign it to the variable C

[lists:sort(tuple_to_list(C))||...] % For every item, convert the tuple to a list
                                    % And then sort that list

lists:member(lists:sort(A),...).    % Is argument 1 a member of the processed list?
```
</code></pre>
> 3 votes

# Answer
# C (gcc), 170 168 bytes

*Edited: Switched to returning 1 from inner `main` calls to save a byte not needing to negate the return value when assigning into `u`. Also another byte saved thanks to @ceilingcat for reminding me about `index` instead of `strchr`.*

```
f;char*l,*u;main(n,x)char**x;{if(f++){if(n){for(int i=0;l[i];i++)if(u[i]&&index(*x,l[i])){u[i]=0;u[i]=main(n-1,x+1);}return 1;}exit(1);}u=strdup(l=x[1]);main(n-2,x+2);}

```

Try it online!

A relatively straightforward recursive backtracking search. Takes input as command-line arguments, the first being the list of badges you have in a single character string (e.g. `abcd`) and each other argument being the list of badges accepted by each station in similar format. Contrary to traditional exit code logic the program's exit code is 0 when you cannot pass and 1 when you can pass, mainly because the return value of `main` is used in the program and it works out better that way. There is no output on stdout.

Originally I'd written a subroutine for the search part after initializing some state in `main` but when I abstracted the globals and saw the function signature was `int (int, char**)` I couldn't resist pulling it all back in and recursing on `main`.

Degolfed somewhat for viewing pleasure:

```
f;char*l,*u;                                                // Declare some storage. f is a counter used to only run the setup code on the original call to main. l gets assigned to be a pointer to the list of badges held. u is used as a buffer to track which badges are currently still available to be used.
main(n,x)char**x;{                                          // Typical golfed main declaration.
       if(f++){                                             // Only run the code in the if statement on subsequent calls to main (as a global f defaults to being initialized to 0).
               if(n){                                       // Catch the recursion base case (if n == 0 there are no stations left to pass).
                       for(int i=0;l[i];i++){               // Iterate over the badges we have available. i needs to be declared here since each recursive call needs to iterate over badges separately.
                               if(u[i]&&index(*x,l[i])){   // If the badge is available to be used (the entry in u for the badge is nonzero), and the badge is accepted by the next station...
                                       u[i]=0;              // Mark the badge as unavailable for the recursive call
                                       u[i]=main(n-1,x+1); // Recursively call main with the current station removed. If a sequence passing all stations is found the program exits immediately, so if main returns on an inner call it will always return 1; by assigning this into u we mark the badge as available again afterwards if we backtrack out of this call to continue searching.
                               }
                       }
                       return 1;                            // If we went over all our badges and couldn't get through this station, we need to backtrack the search so return 0 and continue.
               }
               exit(1);                                     // If there are no stations left we passed through all of them so immediately exit with code 1.
       }
       u=strdup(l=x[1]);                                    // Initialize storage for u. Initially I used calloc here, but since the needed length of u is the length of the list of badges held, strdup gets the job done while saving on bytecount (Just with the parity of the usage checks inverted since strdup means all the entries we care about are initialized to nonzero values).
       main(n-2,x+2);                                       // Make the first recursive call, with our new args starting at the first station's accepted badge list.
}                                                           // If we made it to the end without exiting the program, main will default to returning 0 since no return call was specified.

```
> 3 votes

# Answer
# Python 3, ~~85~~ 84 bytes

```
f=lambda b,r:b==""or any(B in r[0]and f(b[:i]+b[i+1:],r[1:])for i,B in enumerate(b))

```

Try it online! Golfed 1 byte by switching to an explicit enumeration.
> 2 votes

# Answer
# JavaScript (ES6),  ~~69~~  68 bytes

Takes input as `(b)(a)`, where \\$b\[\\:\]\\$ are the collector badges as a list of sets and \\$a\[\\:\]\\$ is our list of badges.

```
b=>g=a=>1/a||a.some((v,i)=>b[a.length-1].has(v)*g(a.filter(_=>i--)))

```

Try it online!

### Commented

```
b =>                       // b[] = collector badges as a list of sets
  g = a =>                 // g is a recursive function taking our list of badges
    1 / a ||               // yield +Infinity if a[] is empty
    a.some((v, i) =>       // otherwise, for each badge v at position i in a[]:
      b[a.length - 1]      //   test whether the collector at index a.length - 1
      .has(v) *            //   accepts the badge v
      g(                   //   multiply by the result of a recursive call where:
        a.filter(_ => i--) //     the i-th badge is removed from a[]
      )                    //   end of recursive call
    )                      // end of some()

```
> 2 votes

# Answer
# Charcoal, 37 bytes

```
Ｓθ⊞υθＦθ«Ｓι≔υη≔⟦⟧υＦηＦΦκ№ιλ⊞υΦκ¬⁼λμ»¿υ¹

```

Try it online! Link is to verbose version of code. Outputs `-` if you can challenge the Elite Four. Explanation:

```
Ｓθ

```

Read the badges.

```
⊞υθ

```

Start with a single entry with all badges remaining.

```
Ｆθ«

```

Loop over each guard.

```
Ｓι

```

Input the badges he accepts.

```
≔υη≔⟦⟧υＦη

```

Save the list of badges remaining so that we can clear it and still loop over the list.

```
ＦΦκ№ιλ

```

See whether this guard will accept any of these badges.

```
⊞υΦκ¬⁼λμ

```

If so then push the possible sets of remaining badges to the list. (If e.g. two guards both accept the same two badges then this could create duplicates depending on which badge you give to which guard but this does not affect the final result.)

```
»¿υ¹

```

If it was possible to give all the guards a badge then print a `-`.
> 2 votes

# Answer
# Perl 5 `-lpa`, ~~86~~ 79 bytes

```
$"="}{";@a=<>;chomp@a;map{$b=$F[0];$\|=!grep!$_,map$b=~s/$_//,/./g}glob"{@a}"}{

```

Try it online!

First line of input is the badges you hold. Subsequent lines are the ones needed. On each line, badges are comma separated.
> 2 votes

# Answer
# Perl 6, 40 bytes

```
{@^a.permutations.map(*Z∈@^b).max.min}

```

Try it online!

## Explanation

Basic approach is to work out every possible combination of our collectors badges against the other collectors badges and see if any combination is possible.

`@^a.permutations` computes all permutations of the list of your badges `[abcd] -> [[abcd],[abdc]...]`

`.map(*Z∈@^b)` For each of these permutations, zip each element of the resulting list (`*Z`) with whether each item is present in the corresponding other badge collector's badges (`@^b`). `[abcd],[[abc][def][bcd][cg]] -> ((True False True False) (True False True True) ...)`

`.max` Return the highest element in the list, i.e. the one with the most Trues.

`.min` Return the lowest element in this list, i.e. true if all the elements are true, else false.
> 2 votes

# Answer
# Python 3, 86 bytes

```
lambda a,b:any(all(map(str.count,b,c))for c in permutations(a))
from itertools import*

```

Try it online!

*-7 bytes thanks to xnor*
> 1 votes

---
Tags: code-golf
---


# Question
Title: Where to point a low-orbit ion cannon (asking for a friend)
# Challenge

## Premise

Bob lost1 Alice's precious grand piano. Big mistake. Alice has now stolen Bob's low-orbit ion cannon.

Alice refuses to just make up with Bob, so let's help her give him a *light tap* on the roof. Suppose that from the top Bob's house looks like a lattice polygon, where all points have integer coordinates...

1. So he says.

## Task

**Input:** an \\$n\times2\\$ matrix of integers (where \\$3\leq n\leq16\\$) representing the coordinates of the points of an \\$n\\$-gon, given in the order in which you would join them up. To be absolutely clear, the first and second values in each of the \\$n\\$ rows are respectively an \\$x\\$\- and a \\$y\\$-coordinate.

* If it would be far more natural to take something other than a 2D matrix in your language or it's impossible to take one, you can use something else. Should this happen, please clearly state what you're doing.
* \\$x\\$-coordinates or \\$y\\$-coordinates may be negative, zero or positive.
* The polygon formed by joining up the points in the given order may be convex or concave.
* There's no need to consider degenerate polygons.
* No input polygon will be self-intersecting, thank goodness.

**Output:** two numbers of any numeric type, respectively representing the \\$x\\$-coordinate and \\$y\\$-coordinate of a point within the polygon.

* No, your numbers needn't be integers.
* Your output needn't be consistent for any single input. You're allowed to generate an output in any valid way that shortens your code.
* Corners and edge points are forbidden. Sorry.

### Example 1

Input:

```
0 0
3 0
3 4

```

Possible output: `1 1`

### Example 2

Input:

```
-3 -1
0 1
-1 -1
-1 0

```

Possible output: `-0.31416 0.42`

# Remarks

* This is , so fewest bytes wins.
* The tag is here only to be on the safe side. I expect that not every answer will use randomness.
* Standard rules, I/O rules and loophole rules apply.
* If possible, link an online demo of your code.
* Please explain your code.

# Answer
# Python 3.8, ~~116~~ 110 bytes

```
lambda p:[x:=min(p)[0]+.1,sum(sorted(b+(d-b)*(x-a)/(c-a)for(a,b),(c,d)in zip(p,p[-1:]+p)if(a<x)^(c<x))[:2])/2]

```

Try it online!

**Input**: A list of points, each is a tuple of 2 integers.
**Output**: A point as a list of 2 numbers.

### Approach

Draw a vertical line through the polygon. Select the first 2 points where the line intersects with the polygon edges. Any point between those 2 points must be inside the polygon.

Note that the line should be chosen such that it doesn't intersect any polygon vertex.

### Code explanation

The x-coordinate of the line is selected as the minimum `x` of all vertices, plus a small amount (`0.1` is used in this case):

```
x:=min(p)[0]+.1

```

This ensures that the line intersects the polygon, and that it doesn't pass through any vertex (since vertices all have integer coordinates).

For each edge through vertices \\$(a,b)\\$ and \\$(c,d)\\$, the line intersects the edge if \\$a\<x\<c\\$ or \\$a\>x\>c\\$. Golfed using xor trick:

```
if (a<x)^(b<x)

```

The y-coordinate of each intersection is calculated using the following formula: $$\frac{y-b}{x-a}=\frac{d-b}{c-a}$$ or `b+(d-b)*(x-a)/(c-a)`

The y-coordinate of the final point is calculated as the average of the smallest 2 y-coordinates.
> 15 votes

# Answer
# Wolfram Language (Mathematica), 11 bytes

Mathematica has a built-in for pointing ion cannons. In fact, as far as I know, it should support self-intersecting roofs. Takes input as a polygon.

```
RandomPoint

```

Try it online!

By the way, `RandomPoint@Polygon@#&` is 5 bytes of Sledgehammer: `⡘⠼⡃⡖⣳`.
> 11 votes

# Answer
# Perl 5, 191 bytes

```
sub{sub c{($_[0]+$_[1])/2}map{$x{$_->[0]}=0}@_;$x=c sort
keys%x;for(0..$#_){($t,$y)=@{$_[$_]};($d=$_[$_-1][0]-$t)&&($t=($x-$t)/$d,$t*(1-$t)>0&&push@y,$y+$t*($_[$_-1][1]-$y))}@{[$x,c
sort@y]}}

```

It's deterministic and O(n).

Choose an \\$x\\$-coordinate \\$P\_x\\$ (`$x`) halfway between the smallest two unique input \\$x\\$ coordinates. Test each polygon side to see if that line segment intersects the \\$x=P\_x\\$ vertical line. If it does, add the \\$y\\$-coordinate of that intersection point to `@y`. Finally, let \\$P\_y\\$ be halfway between the two smallest values in `@y`, and the output is \\$(P\_x,P\_y)\\$: since you cross exactly one edge to get here from the \\$y=-\infty\\$ end of the \\$x=P\_x\\$ line, the point must be inside the polygon.

Try it online!
> 7 votes

# Answer
# MATL, 19 bytes

```
`xx,Xr]yy&G4$TF#ZQ~

```

The input is a vector with *x* coordinates, then a vector with *y* coordinates. The ouput is *x*, then *y*. Running time is random, but finite with probability 1.

Try it online!

### How it works

The program randomly generates points with a bidimensional Gaussian distribution until one of them happens to be inside the polygon. This distribution spans the full plane, so the code eventually finds a solution.

```
`       % Do...while
  xx    %   Delete twice. In the first iterarion this takes the two inputs
        %   (implicitly) and deletes them. In subsequent iterations this
        %   deletes the previous x, y candidate coordinates, which turned out
        %   not to be a solution
  ,     %   Do twice
    Xr  %     Generate a random number with a standard Gaussian distribution.
        %     Note that his covers the whole plane, although points close to
        %     the origin have greater a probability density
  ]     %   End. The stack contains two numbers representing x, y coordinates
        %   of a potential solution
  yy    %   Duplicate top two elements in the stack
  &G    %   Push the two inputs
  4$    %   Specify four inputs for the next function
  TF#   %   Specify the first of two possible outputs for the next function
  ZQ    %   Inpolygon function: takes four inputs, where the first and second
        %   define x, y coordinates of a point, and the third and fourth define
        %   the x, y coordinates of the polygon vertices. The (first) output is
        %   true if the point is strictly in the polygon, and false if not
  ~     %   Negate
        % End (implicit). A new iteration starts if the top of the stack is
        % true, meaning that the tested x, y values were not a solution
        % Display (implicit)

```
> 3 votes

# Answer
# Java 10, 378 bytes

```
import java.awt.geom.*;X->Y->{var p=new Path2D.Double();p.moveTo(X[0],Y[0]);int l=X.length,f=1,i=1;for(;i<l;)p.lineTo(X[i],Y[i++]);p.closePath();var r=p.getBounds();double x=0,y=0;for(;f>0;)for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),i=f=0;i<l-1;)f=!p.contains(x,y)|new Line2D.Double(X[i],Y[i++],X[i],Y[i]).contains(x,y)?1:f;return x+","+y;}

```

Having builtins is usually an advantage, right?.. :/ I'll see if a manual approach is shorter later on.

Input-coordinates as two loose arrays for `x` and `y` respectively, output as a comma-delimited String of the random `x,y`-coordinate.

Try it online.

**Explanation:**

```
import java.awt.geom.*;      // Required import for Path2D and Line2D
X->Y->{                      // Method with two int-arrays as parameters and String return-type
  var p=new Path2D.Double(); //  Create a Path2D
  p.moveTo(X[0],Y[0]);       //  Start at the first input-coordinate
  int l=X.length,            //  Store the amount of points in `l`
      f=1,                   //  Flag integer, starting at 1
  i=1;for(;i<l;)             //  Loop `i` in the range [1, l):
    p.lineTo(X[i],Y[i++]);   //   And draw a line to the `i`'th x,y-coordinate of the input
  p.closePath();             //  Close the path, so we now have our polygon
  var r=s.getBounds();       //  Create a Rectangle that encapsulates this polygon
  double x=0,y=0;            //  Create the random x,y-coordinate
  for(;f>0;)                 //  Loop as long as the flag is still 1:
    for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),
                             //   Get a random x,y-coordinate within the Rectangle
        i=f=0;               //   (Re)set both the flag and `i` to 0
        i<l-1;)              //   Inner loop `i` in the range [0, l-1):
      f=!p.contains(x,y)     //    If the Path2D-polygon does NOT contain this random x,y-coordinate
        |                    //    Or:
         new Line2D.Double(  //    Create a Line2D
          X[i],Y[i++],       //    from the `i`'th x,y-coordinate of the input
          X[i],Y[i])         //    to the `i+1`'th x,y-coordinate of the input
         .contains(x,y)?     //    And if this line does contain the random x,y-coordinate:
          1                  //     Change the flag to 1
        :                    //    Else:
          f;                 //     Keep the flag the same
  return x+","+y;}           //  And finally return our random x,y-coordinate as String

```
> 3 votes

# Answer
# Python 2, 89 bytes

```
l=input()
(B,b),(A,a),(C,c)=min(zip(l[1:]+l,l,l[2:]+l))
print.2+B,b+(a+c-b*2)/(A+C-B*2)/5

```

Try it online!

Here's the strategy for picking the point:

* Take the vertex \\$p\\$ with the smallest \\$x\\$-coordinate. If there's a tie, any is fine.
* Consider the two edges leading from \\$p\\$. To obtain a direction that's in between them, add them as vectors.
* Travel from \\$p\\$ in this direction far enough to go +0.2 units in the \\$x\\$ direction, and pick the point you arrive at.

Because \\$p\\$ is among the leftmost points of the polygon, any direction that's in between the two edges leading from it points inside the polygon. Because we only travel 0.2 units in the \\$x\\$ direction and all vertices lie on integer points, we can't have exited the polygon after going less than 0.5.
> 1 votes

# Answer
# Erlang (escript), 174 bytes

```
f(P)->X=hd(lists:min(P))+0.1,[X,lists:sum(lists:sublist(lists:sort([B+(D-B)*(X-A)/(C-A)||{[A,B],[C,D]}<-lists:zip(P,[lists:last(P)|lists:droplast(P)]),(A<X)xor(C<X)]),2))/2].

```

Try it online!
> 1 votes

---
Tags: code-golf, math, geometry, random
---


# Question
Title: Code golfing my guess the number game with feedback in NS-HUBASIC - Can it be code golfed any further?
The player has to keep guessing a number from 1 to 10 until they guess the correct number to win the game. If they make an incorrect guess, they're told if their guess was too low or too high.

Each line has to render below the previous line for me to accept the solution as the new code for the game (However, you can still share any solutions that break that rule.). For example, no lines can be rendered over other lines, such as "CORRECT." over "TOO LOW." or "TOO HIGH.".

Here's the code:

```
0N=RND(10)+1:DIMT$(2):T$(0)="CORRECT.":T$(1)="TOO LOW.":T$(2)="TOO HIGH.":F.T=0TO0:I."WHAT'S MY NUMBER? (1-10) ",G:T=G<>N:?T$(-(G>N)-T):N.

```

As for how I'm running NS-HUBASIC code, I'm doing it in Family BASIC V3.0, which I'm running under Nestopia v1.40.

If you need any documentation, you can find it here: https://gamefaqs.gamespot.com/nes/938747-family-basic-v3/faqs/59317

# Answer
> 2 votes
# ~~134~~  133 characters

Note: I don't know for sure whether a line-break counts as 1 character.

```
0N=RND(10)+1:DIMT$(2):T$(0)="TOO LOW.":T$(1)="CORRECT.":T$(2)="TOO HIGH."
1I."WHAT'S MY NUMBER? (1-10) ",G:?T$(SGN(G-N)+1):IF G-N T.1

```

### Example output

---
Tags: code-golf, random, tips, game, basic
---


# Question
Title: Mask values in a .env file for a screencast
Let's say I have a `.env` file with the following contents:

```
CF_WORKERS_ACCOUNT_ID=abcdef34632114
CF_WORKERS_API_TOKEN=abcdef34632114def3463def3463
FAB_DEV_ZONE_ID=434932843272439874329

```

I'm doing a screencast, and I want to quickly `cat .env` to show what's in the file, without broadcasting the exact values, since they're secret.

What I want is a one-line unix command (I'm on OSX personally) that gives me:

```
> cat .env | some_command
CF_WORKERS_ACCOUNT_ID=••••••••••••••
CF_WORKERS_API_TOKEN=••••••••••••••••••••••••••••
FAB_DEV_ZONE_ID=•••••••••••••••••••••

```

A little thing, but would be neat!

My best attempt is `cat .env | ruby -pe 'k,v=$_.split("=");$_="#{k}=#{v.gsub(/./,"•")}"'` but I'm sure it can be shorter...

# Answer
> 0 votes
# 05AB1E, 12 bytes

Uhh, I'd just solve it anyway...

```
'=¡`g'•иJ'=ý

```

Try it online!

## Explanation

```
'=¡          Split by equal signs
   `         Put both parts onto the stack
    g        Find the length of the second item
     '•иJ    Repeat that many •'s
         '=ý Join by the equal sign

```

# Answer
> 0 votes
# vim, ~~14~~ ~~13~~ 12 keystrokes, assuming you can somehow type •

Somehow matches 05AB1E.

```
:%norm$vT=r•

```

Assumes there is only one `=` character in a line.

Overly generic explanation:

```
:%norm        on every line do these normal mode commands
      $       go to the end of string
       vT=    select until but not including the previous =
          r•  replace with a nice unicode dot

```

just type these commands and don't forget not to save
Try it online! (with V)

# Answer
> 0 votes
# Perl 5, 23 chars

```
1while s/(=.*)[^•]/$1•/

```

as in

```
cat .env | perl -ple'1while s/(=.*)[^•]/$1•/'

```

Try it online!

# Answer
> 0 votes
# sed -E, 22 chars (26 bytes)

```
:a;s/(=.*)[^•]/\1•/;ta

```

Try it online!

This replaces every character after the first `=` with a .

Your use case would be:

`cat .env|sed -E ':a;s/(=.*)[^•]/\1•/;ta'`

or

`cat .env|sed ':a;s/\(=.*\)[^•]/\1•/;ta'`

(which is one byte shorter as a shell command).

By the way, you can shorten this again if you change your command structure slightly:

`sed ':a;s/\(=.*\)[^•]/\1•/;ta'<.env`

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


# Question
Title: Squeezy sequence, sideways sedimentation
# Challenge

## Premise

I've got multiple pretty numbers all in a row. Each is a decimal digit.

0s are weakly attracted to 0s, 1s are attracted to 1s a little more strongly and so on until 9. I don't know *why* — it must be something I ate. As a result, a sort of two-way sideways sedimentation occurs until the higher values are closer to the middle and the lower values closer to the sides.

Specifically, this happens:

1) Find all instances of digits having the highest value. If there's an even number \\$2p\\$ of them, go to step 2a. If there's an odd number \\$2q+1\\$ of them, go to step 2b.

2a) Consider the \\$p\\$ instances on the left and the \\$p\\$ instances on the right. Continue to step 3.

2b) Consider the \\$q\\$ instances on the left of the middle instance, and the \\$q\\$ instances on its right. Continue to step 3.

3) Each member of the former subset will move right by swapping places with the digit directly on its right *as long as this other digit is smaller*, and members of the latter subset will move left in a similar fashion. All such swaps happen simultaneously. If exactly one lower-value digit is enclosed by two high-value digits (one on each side), always move this lower-value digit to the right instead.

4) Repeat step 3 until all digits of this value are directly side-by-side.

5) Repeat steps 1 to 4 for smaller and smaller values until the values are exhausted.

Here's a detailed example.

```
2101210121012 | begin
1201120211021 | four 2s; the two on the left move right, the two on the right move left
1021122011201 | conflict, resulting in change from 202 to 220 (see step 3); meanwhile,
                 the two other 2s move inwards
1012122012101 | no remarks
1011222021101 | no remarks
1011222201101 | 2s are done
0111222210110 | six 1s, but exactly one on the left of the chain of 2s moves right, and
                 exactly two on the right move left. observe 1s can never pass through 2s
                 because 2 is not smaller than 1 (see step 3)
0111222211010 | no remarks
0111222211100 | end; 1s and 0s are done at the same time

```

Let's find the end state with the power of automation!

## Task

Input: an integer sequence where each element is between 0 and 9 inclusive. The sequence is of length \\$3\leq n\leq10000\\$.

Output: in any format, the end state that would be reached by following the instructions in the section 'Premise'. Shortcut algorithms that give you the correct answer are allowed.

### Examples

```
Input -> output
0 -> 0
40304 -> 04430
3141592654 -> 1134596542
2101210121012 -> 0111222211100
23811463271786968331343738852531058695870911824015 -> 01111122233333333445556666777888888999887554211100

```

# Remarks

# Answer
> 1 votes
# JavaScript (ES8), 186 bytes

A direct transformation of the input.

```
s=>(g=s=>s.join``)([...b=g((a=s.split(n=Math.max(...s)))[S='slice'](0,(k=a[L='length'])/2))+(m=a[k>>1])[S](0,k&1&&m[L]/2)].sort())+''.padEnd(k-1,n)+g([...g(a)[S](b[L])].sort((a,b)=>b-a))

```

Try it online!

# Answer
> 1 votes
# , 44 42 bytes

```
(/:~@{.,\:~@}.)~[:(#{2#]<.@-:@+|.)@I.>./=]

```

Try it online!

The meat of the problem is finding the right point to split the input.

After that, you just sort the left side up and the right side down, and cat them together (`/:~@{.,\:~@}.`).

We'd like to avoid treating "odd number of max elements" and "even number of max elements" as two special cases.

To do this, notice that given the indices of the max elements (`I.>./=]`), you can add that list elementwise with its reverse and average each element (`]<.@-:@+|.`).

Next, duplicate each element of *that* list in place (`2#`), and pull from the result the element at index "length of original list" (`#{`).

All together, this gives us the "midpoint" of the original list, where "midpoint" is defined as "the actual midpoint" in the odd case, and "the average of the two middle-ish" elements in the even case.

This is exactly where the algorithm tells us to split the input.

# Answer
> 1 votes
# Jelly, 15 bytes

```
MÆṁ$ĊœṖ⁸Ṣ€U2¦;/

```

A monadic link accepting a list (of any orderable items) which yields a list.

**Try it online!**

# Answer
> 0 votes
# Retina 0.8.2, 135 bytes

```
$
¶¶$`¶
O`\G.
+`((.)¶.*)¶(.*?\2)(.*)(\2.*)¶
$1$3¶$4¶$5
((.)¶.*)¶(.*)\2(.*)¶
$1$3¶$2¶$4
1A`
+`¶(.)(.*)(.)¶
$1¶$2¶$3
2=`¶

%O^`.
O`\G.
¶

```

Try it online! Link includes test cases. Explanation:

```
$
¶¶$`¶

```

Make a working area with a copy of the input surrounded by blank lines.

```
O`\G.

```

Sort the digits of the original input.

```
+`((.)¶.*)¶(.*?\2)(.*)(\2.*)¶
$1$3¶$4¶$5

```

Move minimal suffixes and prefixes of the copy of the input to the blank lines. Each moved minimal suffix must end with the largest digit and each moved minimal prefix must start with the largest digit.

```
((.)¶.*)¶(.*)\2(.*)¶
$1$3¶$2¶$4

```

If there is an odd number of the largest digit, move its exclusive prefix and suffix too.

```
1A`

```

Delete the sorted copy of the digits.

```
+`¶(.)(.*)(.)¶
$1¶$2¶$3

```

If there was an even number of the largest digit, move individual digits from the remainder of the copy of the input to the prefix and suffix areas.

```
2=`¶

```

Move the last digit (if any) or the odd largest digit to the suffix.

```
%O^`.

```

Sort both the prefix and the suffix descending.

```
O`\G.

```

Reverse the prefix.

Join the prefix and suffix together.

# Answer
> 0 votes
# Charcoal, 49 bytes

```
≔⌕Ａθ⌈θη≔…θ÷ΣＥ²§η÷⁻Ｌηι²¦²η⭆χ×Ｉι№ηＩι⮌⭆χ×Ｉι⁻№θＩι№ηＩι

```

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

```
≔⌕Ａθ⌈θη

```

Find all the positions of the maximum digit.

```
≔…θ÷ΣＥ²§η÷⁻Ｌηι²¦²η

```

Take the average of the middle two (or the middle position duplicated if there are an odd number of positions) and chop the input to this length.

```
⭆χ×Ｉι№ηＩι

```

Sort the chopped input. (Because we know the range of characters, we just repeat each character by the number of times it appears in the desired string.)

```
⮌⭆χ×Ｉι⁻№θＩι№ηＩι

```

Calculate the number of each digit remaining to give the sorted remainder, and then print that reversed so that the sort is descending.

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


title: Exactly N in a line

text:
# Question
Title: Exactly N in a line
Given a number N from 2 to 8, place any nonzero number of queens on a grid of any size so that every queen has exactly N queens (counting itself) in each of its row, column, and each diagonal.

**This challenge has a significant runtime limit.** Your code must finish all N from 2 to 8 (combined) within the 60-second timeout on TIO. This makes brute force unlikely to work.

Some example outputs are below. You can use this verification script to confirm your outputs.

*N=2*

```
.OO.
O..O
O..O
.OO.

```

*N=3* (by Christian Sievers)

```
..OOO......
.O.O...O...
OO...O.....
O...O....O.
O......O..O
..O...O..O.
..O..O....O
.O...O..O..
.......OO.O
...O..O..O.
....O.O.O..

```

*N=4* (by Christian Sievers)

```
...OO..OO...
..OO....OO..
.O...OO...O.
OO........OO
O....OO....O
..O.O..O.O..
..O.O..O.O..
O....OO....O
OO........OO
.O...OO...O.
..OO....OO..
...OO..OO...

```

Your output grid can be square or rectangular. It may have empty rows and/or columns, even ones on the outside as a "margin" that makes the array bigger than necessary.

You can output as a 2D array of two distinct values of your choice, or as a string that displays as such.

For the 60-second time limit, running verification code doesn't have to happen within this time. If your language is not on TIO, you test it on any reasonable machine. On the off chance that your grids might be so big that TIO can't print them, it's allowed to run the test with storing all 7 grids instead of printing them, such as to a size-7 list where that any of them may be retrieved.

# Answer
> 11 votes
# Python 2, 141 138 bytes

Try it online!

```
n=input()
P=[280]
for t in[1j,9,40j-40,64j+64]:P={p+i*t for i in range(n)for p in P}
r=range(792)
print[[x+y*1jin P for x in r]for y in r]

```

Takes `n` as input and prints a list of lists of booleans.

While the grids are generated within the 60 second time limit, they are larger than TIO's 128KiB limit, so they were simplified to be printable via TIO thanks to math junkie.

I added in the verification script to the TIO link so it can also be verified within TIO.

Here's my attempt at drawing my original solution for n=3. Hopefully this helps visualize it. Replace 57 with 40 and 408 with 64 for the current solution.

# Answer
> 9 votes
# Ruby, ~~85~~ 77 bytes

```
->n{j=n**3+n
((0...n*n).map{|i|((?.*n*n+?O)*9)[~i%n+i/n*n,j]}+[?.*j]*j)*n*$/}

```

Try it online!

Similar to and inspired by cardboard\_box's answer, but rotated by 45 degrees.

Below are the first 16 lines of the output for `n=4`. It should be apparent that that within each 16x16 box, the queens form diagonal lines of 4. In between the boxes there is a single blank column. If this was not there, the diagonal lines of each `n**2` x `n**2` box would line up exactly with its neighbour when `n` is even.

There are clearly 4 queens on each horizontal row and 1 queen in each vertical column (except the blank ones.) The rest of the pattern is a repeat of the below, interspersed with `n**3+n` rows of blanks to ensure the diagonals do not clash (I could get away with just a few rows less, but the code is shorter this way.)

The output is truncated by TIO so it's only possible to get full output up to 5, but it's apparent from the way the pattern is constructed that it meets the rules. Output has been verified up to 5.

```
.............O................O................O................O...
..............O................O................O................O..
...............O................O................O................O.
................O................O................O................O
.........O................O................O................O.......
..........O................O................O................O......
...........O................O................O................O.....
............O................O................O................O....
.....O................O................O................O...........
......O................O................O................O..........
.......O................O................O................O.........
........O................O................O................O........
.O................O................O................O...............
..O................O................O................O..............
...O................O................O................O.............
....O................O................O................O............

...many blank rows, then repeat the above a total of 4 times...

```

---
Tags: code-golf, combinatorics, grid, restricted-time
---


# Question
Title: Shortest self-avoiding path given a sequence of turns
Write a program or function which, given a *non-empty* sequence of right or left turns, outputs the length of the shortest self-avoiding path on a 2D lattice with those turns.

The input should be taken as a string, with each character being `R` or `L` for a right or left turn respectively.

The output should be an integer, the length of the shortest path with the given turns.

This is a gode golf - shortest code wins.

# Example

Given the input

```
LLLLLLLLLLRRL

```

The shortest path is the following (starting at `#`):

```
+-+-+-+-+-+-+
|           |
+ . + +-+-+ +
|   | |   | |
+ +-+ + #-+ +
| |   |     |
+ +-+ +-+-+-+
|   |
+-+-+ . . . .

```

And the total length of this path is `29` (counting the `-`s and `|`s, not the `+`s).

# Test Cases

```
L 2
RRRRRRRRRR 23
LRRLRLRRRRL 15
LLRRLRRRRLLL 17
LLRRRRRRLLLL 21
LLLLRLLRRLLRL 16
LRLRLRLLRLRRL 14
RLLRRRRLLRRLRL 17
RRRRLLRLLLRLRL 20
LLLLRRLRLRRRLRL 19
RRRLRRRLRRLRLRL 20

```

# Answer
> 8 votes
# Prolog, 284 bytes

```
e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

```

This is a pretty straightforward statement of the algorithm, and fairly inefficient (not all the test cases ran in reasonable time, although most did). It works via generating all possible lengths for the output from 1 upwards (`n`); generating all possible sequences of left/forward/right of that length which are consistent with the input (implemented in `e`; the new path is called `X`); then checking for the first such path that's valid (`c`, which calls into `v` to handle the effects of left and right turns on the x and y deltas). The return length is the first output seen in `L`. (+2 penalty if you want to prevent the function returning other possible outputs for the length if you backtrack into it; it's never quite clear how Prolog's idiosyncratic function returns should be counted.)

There isn't much in the way of golfing tricks here, but there is some. `n` was implemented with a constraint solver because it allows more whitespace to be removed without confusing the parser; this might require GNU Prolog to be used, not sure on that. (I couldn't do the same in `c` as it needs to handle negative numbers.) The implementation of `e` is considerably less efficient than it needs to be, via matching a list in multiple ways; the more efficient `e([],[]).` would be six bytes longer (it'd allow the `S=X;` on line 2 to be removed, but that's only a gain of four compared to a loss of ten). To allow me to match coordinates and directions as a whole, or just part, I represent them as `X/Y` (i.e. an unevaluated AST, which can be matched on), allowing me to use infix notation.

# Prolog, 256 bytes, too inefficient to easily test

Of course, because this is Prolog, many of the functions are reversible, e.g. `c` can be used to generate all paths from the origin to a particular coordinate pair. Additionally, `c` naturally generates from shortest to longest. This means that instead of asking for a minimum length explicitly, we can just get `c` to generate *all paths that go anywhere*, then look for the first one that's consistent with the input:

```
e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

```

This has exponential performance (O(3<sup>*n*</sup>), where *n* is the output). However, I did manage to verify it on some of the smaller tests (it takes around 7 seconds to output 14, and around 20 to output 15, on my computer).

# Answer
> 4 votes
# Pyth, 36 bytes

```
ff{I.u+NYY0f>r8YlQ.C+1*M._m^.j)hCdQT

```

Try it online!

This is pretty slow, but it works, and it's fast enough for short inputs.

The program works by representing directions as complex units (1,-1,i,-i), and points as complex numbers. First I convert the list of turns into a list of directions, then generate all list of n steps, filter for those with at least one step between each turn, and convert the directions into a list of points visited, and check if that list is unique. I increment n in a loop until I succeed.

Map to complex numbers:

```
m^.j)hCdQ
m       Q    Map over the input
      Cd     Convert to ASCII codepoint
     h       Increment
 ^.j)        Raise i to that power.

```

Since `L` has ASCII codepoint 76 and `R` has ASCII codepoint 82, this maps `L` to `i` and `R` to `-i`.

Map to absolute directions:

```
+1*M._ ...
    ._      Form all prefixes
  *M        Map each to its product
+1          Add the first direction, before any turns

```

Form lists of n steps with at least 1 step between each turn

```
f>r8YlQ.C ... T
       .C     T    Form all list of T steps
f                  Filter for lists where
  r8Y              Run length encoding of list
 >   lQ            With the first len(input) removed
                   is nonempty

```

There should be one more movement than there are turns in the input. Each movement is in a different direction, so the run length encoding should be longer than the input.

Map to points visited:

```
.u+NYY0  ...
.u   Y0   Reduce the following function over
          the list of steps, starting at 0.
          Return all intermediates.
  +NY     Add the new step to the current position.

```

Filter on non-self-intersecting:

```
f{I ...
f     Filter on
  I   Invariant under
 {    Deduplication

```

Find the first `T` where this succeeds: `f`.

---
Tags: code-golf, path-finding
---


title: Infinite Snake game

text:
# Question
Title: Infinite Snake game
*Infinite Snake* is just like the video game Snake, except for that the snake is infinitely long, there are no items to eat, and the Snake needs to move in a repeating `n`-step move pattern (e.g. right, up, right, up, right, down). The only constraint is that you can't crash back into yourself.

## Challenge

Your goal is to write code that counts the number of valid move patterns of length `n`, where two patterns are considered the same if you can get from one to the other through a series of rotations, reflections, and reversals.

This is a challenge, so the shortest code in bytes wins.

---

## Origin

This sequence is based on the On-Line Encyclopedia of Integer Sequence's lastest "nice" sequence, A334322.

> Number of endless self-avoiding walks of length n for the square lattice.

An "endless self-avoiding walk" (i.e., *valid move pattern*) is defined in the paper Endless self-avoiding walks by Nathan Clisby on the arXiv. Roughly speaking, an \\$n\\$-step self-avoiding walk (in the usual sense) is called *endless* if you can concatenate it with itself head-to-tail an infinite number of times and remain self-avoiding.

## Example

For example, Figure 2.1 in the paper gives an example of an endless self-avoiding walk (of length six) on the left and a non-example on the right.

---

# Small test cases

```
f(1) = 1:
---->

f(2) = 2:
---->----> and ---->
                   |
                   v

f(3) = 3:
---->---->---->, ---->---->, and ---->
                          |          |
                          v          v---->

f(4) = 7:
---->---->---->---->, ---->---->---->, ---->---->     ,
                                    |           |
                                    v           v---->

---->---->, ---->    ^, ---->     , and ---->     .
         |      |    |      |               |
         v      v---->      v---->          v
         |                       |          |
         v                       v          v---->

```

More small values:

```
 f(5) =   16
 f(6) =   39
 f(7) =   96
 f(8) =  245
 f(9) =  631
f(10) = 1642

```

# Answer
# JavaScript (ES6), 240 bytes

Returns the \\$n\\$-th term of the sequence.

```
f=(n,p=[],s=[])=>n?[-1,0,1,2].map(d=>f(n-1,[...p,[d%2,~-d%2]],s))|N:N=[...p,...p].every(o=([h,v])=>o[[n+=h,y+=v]]^=1,y=0)&&s.every(P=>(g=j=>!j||P.reverse().some(([h,v],i)=>(j&4?h:-h)-p[i][j&1]|(j&2?v:-v)-p[i][~j&1])&g(j-.5))(8))?s.push(p):N

```

Try it online!

## A334322 (133 bytes)

This is a version where the tests on symmetries of the square and reversals of the path have been removed. So, it generates A334322 instead.

This is just meant as a verification of the main algorithm.

```
f=(n,p=[],s=[])=>n?[-1,0,1,2].map(d=>f(n-1,[...p,[d%2,~-d%2]],s))|N:N=[...p,...p].every(o=([h,v])=>o[[n+=h,y+=v]]^=1,y=0)?s.push(p):N

```

Try it online!

## Commented

### Main algorithm

This is the main algorithm, which generates A334322.

```
f = (               // f is a recursive function taking:
  n,                //   n = input
  p = [],           //   p[] = current path as a list of (dx, dy)
  s = []            //   s[] = array of solutions
) =>                //
  n ?               // if n is not equal to 0:
    [-1, 0, 1, 2]   //   list of directions
    .map(d =>       //   for each direction d:
      f(            //     do a recursive call:
        n - 1,      //       decrement n
        [           //       new path:
          ...p,     //         copy all previous entries
          [         //         add a new pair (dx, dy):
            d % 2,  //           with dx = d mod 2
            ~-d % 2 //           and dy = (d - 1) mod 2
          ]         //           (NB: sign of mod = sign of dividend)
        ],          //       end of new path
        s           //       pass s[] unchanged
      )             //     end of recursive call
    ) | N           //   end of map(); yield N
  :                 // else:
    N =             //   update N:
      [...p, ...p]  //     append the path to itself
      .every(o =    //     o is an object used to store the positions
        ([h, v]) => //     for each (h, v) = (dx, dy):
        o[[         //       update o for the new position:
          n += h,   //         add dx to n
          y += v    //         add dy to y
        ]] ^= 1,    //       if a position was already visited, this XOR gives 0
        y = 0       //       start with y = 0 (we already have n = 0)
      ) ?           //     end of every(); if the path is self-avoiding:
        s.push(p)   //       push it into s[]
      :             //     else:
        N           //       leave N unchanged (see the note below)

```

**Note:** The first iteration always leads to a valid straight path. Because of that, \\$N\\$ is guaranteed to be defined when we encounter an invalid path for the first time. (Otherwise, this `N = N` could be a problem, as \\$N\\$ is not explicitly defined anywhere else.)

### Additional tests

Below are the additional tests that are performed to detect symmetries of the square and reversals of the path.

There are \\$16\\$ different tests whose parameters depend on the bits of a counter \\$j\\$ going from \\$8\\$ to \\$0\\$. We subtract \\$1/2\\$ from \\$j\\$ between each iteration so that each set of parameters is tested twice: once with the path \\$P\[\\:\]\\$ reversed and once with \\$P\[\\:\]\\$ put back in the original order.

```
s.every(P =>             // for each previous path P[] in s[]:
  ( g = j =>             //   g is a recursive function taking a counter j:
    !j ||                //     success if j = 0
    P.reverse()          //     otherwise, reverse P[]
    .some(([h, v], i) => //     for each (h, v) at position i in P[]:
      (j & 4 ? h : -h)   //       compare either h or -h with
      - p[i][j & 1] |    //       either p[i][0] or p[i][1]
      (j & 2 ? v : -v)   //       compare either v or -v with
      - p[i][~j & 1]     //       the other component of p[i]
    ) &                  //     end of some()
    g(j - .5)            //     do a recursive call with j - 1/2
  )(8)                   //   initial call to g with j = 8
)                        // end of every()

```
> 8 votes

---
Tags: code-golf, sequence, geometry, combinatorics, grid
---


title: The Koszul Sign Rule

text:
# Question
Title: The Koszul Sign Rule
## A Bit of Background

The exterior algebra is a central object in topology and physics (for the physics concept cf. fermion). The basic rule dictating the behavior of the exterior algebra is that \\$yx = -xy\\$ (and consequently \\$x^2 = -x^2 = 0\\$). Applying this rule twice we see that \\$yzx = -yxz = xyz\\$.

The product of two monomials is 0 if any repeated variable occurs, e.g. \\$vxyz * stuv = 0\\$ because \\$v\\$ is repeated. Otherwise, we want to put the variables into some standard order, say alphabetical order, and there is a sign introduced that counts how many variables we passed by each other, so for example \\$tvy * suxz = +stuvxyz\\$ because it takes a total of six crossings to put \\$tvysuxz\\$ into alphabetical order (on each line I have highlighted the most recently swapped pair): $$tvy * suxz = +\\, tvy\\;suxz\\ \phantom{tvy * suxz } {}= -tv\mathbf{\large sy}uxz\\ \phantom{tvy * suxz } {}= +t\mathbf{\large sv}yuxz\\ \phantom{tvy * suxz } {}= -\mathbf{\large st}vyuxz\\ \phantom{tvy * suxz } {}= +stv\mathbf{\large uy}xz\\ \phantom{tvy * suxz } {}= -st\mathbf{\large uv}yxz\\ \phantom{tvy * suxz } {}= +stuv\mathbf{\large xy}z\\ $$ Your task will be to compute this sign.

This is a special case of the Koszul Sign Rule which determines the sign of the terms in many sums in math. If you are familiar with determinants, the sign in the determinant formula is an example.

## Task

You will take as input two 32 bit integers \\$a\\$ and \\$b\\$, which we will interpret as bitflags. You may assume that \\$a\\$ and \\$b\\$ have no common bits set, in other words that \\$a\mathrel{\\&}b = 0\\$. Say a pair of integers \\$(i, j)\\$ where \\$0\leq i,j \< 32\\$ is an "out of order pair in \\$(a,b)\\$" when:

1. \\$i \< j\\$,
2. bit \\$i\\$ is set in \\$b\\$, and
3. bit \\$j\\$ is set in \\$a\\$.

Your goal is to determine whether the number of out of order pairs in \\$(a,b)\\$ is even or odd. You should output `true` if the number of out of order pairs is odd, `false` if it is even.

**Input**

A pair of 32 bit integers. If you would like your input instead to be a list of 0's and 1's or the list of bits set in each integer, that's fine.

**Output**

`true` or any truthy value if the number of out of order pairs is odd, `false` or any falsey value if it is even. Alternatively, it is fine to output any pair of distinct values for the two cases. It is also fine to output any falsey value when the number of out of order pairs is odd and any truthy value when the number of out of order pairs is even.

## Metric

This is code golf so shortest code in bytes wins.

## Test cases

```
    a = 0b000000
    b = 0b101101
    output = false // If one number is 0, the output is always false.

    a = 0b11
    b = 0b10
    output = UNDEFINED // a & b != 0 so the behavior is unspecified.

    a = 0b01
    b = 0b10
    output = true // 1 out of order pair (1,2). 1 is odd.

    a = 0b011
    b = 0b100
    output = false // 2 out of order pairs (1,2) and (1,3). 2 is even.

    a = 0b0101
    b = 0b1010
    output = true // 3 out of order pairs (1,2), (1,4), (3,4). 3 is odd.

    a = 0b0101010 // The example from the introduction
    b = 0b1010101
    output = false // 6 out of order pairs (1,2), (1,4), (1,6), (3,4), (3,6), (5,6).

    a = 33957418
    b = 135299136
    output = false

    a = 2149811776
    b = 1293180930
    output = false

    a = 101843025
    b = 2147562240
    output = false

    a = 1174713364
    b = 2154431232
    output = true

    a = 2289372170
    b = 637559376
    output = false

    a = 2927666276
    b = 17825795
    output = true

    a = 1962983666
    b = 2147814409
    output = true

// Some asymmetric cases:
    a = 2214669314
    b = 1804730945
    output = true

    a = 1804730945
    b = 2214669314
    output = false

    a = 285343744
    b = 68786674
    output = false

    a = 68786674
    b = 285343744
    output = true

    a = 847773792
    b = 139415
    output = false

```

# Answer
> 7 votes
# COW, ~~363~~ 285 bytes

```
moOoommoOmoOmoOoomMOOmoOmOoMOOMOomOoMoOmoOMMMMOOMMMMOomOoMOomoOmoOMoOmOoMMMOOOmooMMMmoomoOMMMOOOmOoMMMmOoMOOmOoMMMmoOmoOmoOMMMMOOMOomoOMMMMOOMMMMOoMOoMMMOOOmooMMMMoOmOomoomOomOoOOOmoomOomOoMOOMOomoOMoOmOoMMMMOOMMMMOomoOMOomOomOoMoOmoOMMMOOOmooMMMmoomOoMMMOOOmoOMMMmoOmoOmoOmoomoOmoOOOM

```

Try it online!

A major change! (It's faster but still test cases exceed the 60 seconds timeout on TIO)
Now I like it better, it's cleaner, symmetric and I've brute forced the memory cells disposition for least number of movements.

The idea is to directly operate in terms of parity. Information in both LSB will be used in each iteration and then `a` and `b` will be halved, until `b=0`.

* Every `a%2` is calculated (during *repeated subtraction*) alternating `+1` and `-1` in one memory cell, so that their partial sum `p` is available.
* When a '1' is found in `b`, the parity (the answer) is toggled `p` many times.

## Detailed Explanation:

```
moo ]    mOo <    MOo -    OOO *    OOM i
MOO [    moO >    MoO +    MMM =    oom o

[0]: a/2     [1]: a     [2]: Sum(a%2)     [3]: b%2     [4]: b     [5]: b/2     [6]: parity

>i>>>i                        ;  Read a in [1] and b in [5]
[                             ;  Loop while [5] is non-zero
    ><                        ;     Just 2 instructions for free cause COW doesn't handle consecutive parethesis :D
    [                         ;     Loop while [5] is non-zero
        -<+>=[=-<->>+<=*]=    ;         SECTION B
    ]                         ;     [5] is 0, [3] is b%2, [5] is b/2
    >=*<=                     ;     Copy [5] in [4], delete [5]
    <                         ;     Point to [3]
    [                         ;     Loop if [3] is non-zero. '1' it's been found in b, parity gets updated
        <=>>>=                ;         Copy [2] in [5]
        [                     ;         Loop while [5] is non zero
            -                 ;             Decrement [5]
            >=[=--=*]=+<      ;             TOGGLE [6]
        ]                     ;
        <<*                   ;         Delete [3] (to exit the loop)
    ]                         ;
    <<                        ;     Point to [1]
    [                         ;     Loop while [1] is non-zero
        ->+<=[=->-<<+>=*]=    ;         SECTION A
    ]                         ;     [1] is 0, a%2 is added in [2], [0] is a/2
    <=*>=                     ;     Copy [0] in [1], delete [0]
    >>>                       ;     Point to [5]
]                             ;     a's and b's LSB have been treated. Now a=a/2 and b=b/2
>>o                           ;  Print [6]

```

`SECTION A``SECTION B` is *repeated subtraction* that divide \\$n\\$ (`a` or `b`, resp.) by \\$2\\$.
This can't be done in one single step (i.e. `--`), because \\$0\\$ can't be surpassed in order to stop (so it'd be `-[- =*]=`). These sections contextually produce \\$n\bmod 2\\$ (LSB).

`TOGGLE` is a toggling method:
When target is **0** it fails the condition and simply `+1` is done.
When target is **1** it passes the condition and it's set to **-1** so that `+1` on exit makes it **0**.

*Copy*, *delete*, and *paste* in the same memory cell is a tecnique to treat a *while loop* like an *if loop*, also the seemgly useless *copy-paste* at the beginning of these (`=[=`) serves to balance the ending one (`=*]=`) in case *if condition* fails.

# Answer
> 6 votes
# 05AB1E, ~~11~~ 9 bytes

Port of my Python answer. Takes `a` and `b` in reverse order, output is 1 for a odd number of out-of-order pairs, 0 for an even number.

-2 bytes thanks to *@CommandMaster* !

```
тÝo÷&bSOÉ

```

Try it online!

### Explanation

```
Code        Comment                       (Example) Stack

            # implicit input              a, b
т           # push 100                    a, b, 100
 Ý          # inclusive range             a, b, [0,1,...,100]
  o         # 2**x                        a, b, [1,2,...,2**100]
   ÷        # integer divide              a, [b//1,b//2,...,b//2**100]
    &       # bitwise and                 [a&b//1, a&b//2, ..., a&b//2**100]
     b      # convert to binary           [000100, ... , 00101001001, ..., 0]
      S     # convert to a list of chars  ["0", "0", "0", "1", ..., "0"]
       O    # sum (as integers)           4 (number of "out of order pairs")
        É   # is this odd?                0
            # implicit output

```

# Answer
> 5 votes
# , 13 bytes

```
2|[:+/@,>/&I.

```

Try it online!

Take our input as lists of ones and zeros.

* `&I.` Convert both `a` and `b` to a lists of the indexes of the ones.
* `>/` Create a function table of all pairs of those indexes, where a cell will be `1` when the `a` index is greater than the `b` index.
* `[:+/@,` Flatten the table and sum all the ones.
* `2|` Remainder when you divide 2 into that sum. Will be 1 (true) exactly when the sum is odd.

# Answer
> 4 votes
# Python 2, ~~49~~ 46 bytes

-3 bytes thanks to Arnauld (and Noodle9)!

```
f=lambda a,b:b and~int(bin(a&b),13)&1^f(a,b/2)

```

Try it online!

# Answer
> 4 votes
# Jelly, 8 bytes

```
:Ƭ2&BSSḂ

```

A dyadic Link accepting an integer, \\$b\\$, on the left and an integer, \\$a\\$, on the right which yields `0` (even) or `1` (odd).

**Try it online!** Or see the test-suite.

### How?

```
:Ƭ2&BSSḂ - Link: integer b, integer a
  2      - literal two
 Ƭ       - starting with b, collect up while results are distinct, applying:
:        -   integer division
   &     - bitwise AND (vectorises) with a
    B    - convert to binary (vectorises)
     S   - sum
      S  - sum
       Ḃ - least significant bit (i.e. mod 2)

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~42~~  39 bytes

Takes input as `(a)(b)`.

Almost identical to ovs' answer.

```
a=>g=(b,n=a&b)=>n?!g(b,n&n-1):b&&g(b/2)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 19 bytes

```
ＮθＮη﹪Σ⭆φ⍘＆×θＸ²ιη²¦²

```

Try it online! Link is to verbose version of code. Outputs `-` for true, nothing for false. Port of @ovs's Python answer. Works for somewhat more than 32 bits. Explanation:

```
Ｎθ                  Input `a` as a number
  Ｎη                Input `b` as a number
      ⭆φ            Loop from 0 to 999 and join
          ×θＸ²ι     Left shift `a` that many times
         ＆     η    Bitwise And with `b`
        ⍘       ²   Convert to base 2 as a string
     Σ              Count total number of bits
    ﹪             ² Reduce modulo 2
                    Implicitly print

```

# Answer
> 1 votes
# Retina 0.8.2, 52 bytes

```
+`.(.*)¶.(.*)$
$&¶¶$1¶$2
(.+¶0|¶1).*¶¶

M`1
[13579]$

```

Try it online! Takes input in padded binary. Explanation:

```
+`.(.*)¶.(.*)$
$&¶¶$1¶$2

```

Generate all of the pairs of suffixes of the inputs.

```
(.+¶0|¶1).*¶¶

```

Delete the pairs of suffixes if the suffix of `b` starts with `0`, otherwise just delete the suffixes of `b`.

```
M`1

```

Count the total number of bits of suffixes of `a` remaining.

```
[13579]$

```

Check whether the total is odd.

# Answer
> 1 votes
# Io, 88 bytes

Port of the 05AB1E answer.

```
method(a,b,Range 0 to(100)map(x,((a/2**x)floor&b)asBinary)join removeSeq("0")size isOdd)

```

Try it online!

---
Tags: code-golf, math, bitwise, physics, topology
---