title: Two Parallel Linked Chains

text:
# Question
Title: Two Parallel Linked Chains
## Background

We define the two types of chain to be a string that contains only dashes, "-", or only underscores, "\_". We link two chains using one equals sign, "=".

Criteria:

1. The type of chain must change following an equals sign.
2. You must link the chains, you can do so multiple times, and it does not matter what length the chains are so long as they are equal to or above one.
3. The chain must not start or end with an equals sign.
4. No two equals signs may be adjacent.
5. There must be at least three characters, and both types of chain must show up.
6. The chain must only contain underscores, dashes, and equals signs.

## Your Task

Given a string, return True if it is a valid two-parallel-linked-chains (tplc) and return False otherwise.

* Input: The string will be maximum 256 characters long. It may contain characters which are not underscores, dashes, or equals signs.
* Output: Return either True or False, depending of if it is valid tplc or not.

**Explained Examples**

```
Input => Output
______=-------=___=-----=_=- => True

```

The string is a valid tplc because it follows all criteria.

```
Input => Output
 => False

```

Empty string does not satisfy criteria 5.

```
Input => Output
=_=- => False

```

The string starts with an equals sign, and does not satisfy criteria 3.

```
Input => Output
___ => False

```

There is only one type of chain, so the string does not satisfy criteria 5.

```
Input => Output
__==--- => False

```

There are two consecutive adjacent equals signs, so the string does not satisfy criteria 4.

```
Input => Output
_=- => True

```

The string satisfies all criteria.

```
Input => Output
_=----=___=--@- => False

```

The string contains a forbidden character, @, so the string does not satisfy criteria 6.

```
Input => Output
__=__ => False

```

The type of chain does not change after an equals sign, so does not satisfy criteria 1.

```
Input => Output
___--- => False

```

The chains are not linked (no equals sign), and does not satisfy criteria 2.

**Test Cases**

```
Input ~> Output

 ~> False
_ ~> False
_- ~> False
== ~> False
==_ ~> False
-_- ~> False
_== ~> False
=_=- ~> False
____ ~> False
-=__£ ~> False
*=___ ~> False
->-=_ ~> False
__=]- ~> False
0x=+y ~> False
--X__ ~> False
_==-- ~> False
-=_=_ ~> False
_-==_- ~> False
_-_-_= ~> False
_==__= ~> False
_=--__ ~> False
___=__ ~> False
--=__ _ ~> False
__=___=___ ~> False
______=----&---- ~> False
___=---------=________-_____ ~> False
--------=_________=-=_=-=_=----=__==----- ~> False

-=_ ~> True
_=- ~> True
-=__=--- ~> True
_=--=___ ~> True
_=-=_=-=_ ~> True
__=------ ~> True
__=------------=____________=--------------=_____________=-------- ~> True
---------=____________=----------=_=-=_=---------------=_______________________ ~> True

```

This is , so shortest answer wins.

# Answer
> 11 votes
# Regex, ~~36~~ ~~32~~ ~~30~~ 29 bytes

```
^(?=.*=)(_|(^|\b=)-+(=_|$))*$

```

Try it online!

-1 thanks to @InSync which allowed for another -1

This is my first regex answer, so it's quite possible I missed some optimizations.

## Explanation

We start with a `(?=.*=)` to make sure the string contains a `=`.

Once we know it does, we can use the following DFA. Let's convert it to a regular expression.

We'll start by removing the bottom two states, and making sure there's only a single accepting state:

Now we remove the left state.

We can remove the `-+` since it's inconsistent with there being a `=` in the string, so we get:

which is equivalent to `(-+=)?_(_|=-+=_)*(=-+)?`.

Then, we can notice the duplication of `=-+`, and since we end with `$` regardless we can optimize it to `(-+=)?_(_|=-+(=_|$))*`. Now, we can do the same for `-+=`, and optimize it to `(_|(^|=)-+(=_|$))*`. However, this introduces the problem that a match can start with `=`. To fix this, we can notice that `_` is a word character, while `-` and `=` aren't. This means that `\b=` matches iff the previous character was `_`, which works in our scenario.

# Answer
> 10 votes
# Jelly, 12 bytes

```
f⁾-_Œgj”=⁼>E

```

Try it online!

```
f⁾-_            Filter out all characters but -_.
    Œg          Group runs of consecutive equal elements.
      j”=       Join on =.
         ⁼      Does this result equal the input?
          >E    And, are the elements of the input not all equal?

```

# Answer
> 10 votes
# JavaScript (ES6), 70 bytes

This code is using an explicit finite-state machine rather than regular expression functions.

Expects a list of characters and returns **0** or **1**.

```
a=>a.map(c=>a|=(s=+"0X00XX11X143"[s+5*"-_=".indexOf(c)])>2,s=2)&&a&s<2

```

Try it online!

This could be **56 bytes** if the input was guaranteed to contain only underscores, dashes and equal signs. (This version expects a list of ASCII codes.)

## States

* State **0**: We are within a `"-"` chain and expect either another `"-"` or a `"="`.
* State **1**: We are within a `"_"` chain and expect either another `"_"` or a `"="`.
* State **2**: This is the initial state where we expect either `"-"` or `"_"`.
* State **3**: We are just after a `"="` preceded by a `"_"` chain. We now expect a `"-"`.
* State **4**: We are just after a `"="` preceded by a `"-"` chain. We now expect a `"_"`.
* State **X**: An error has occurred.

## State-transition table

This table gives the new state based on the current state and the next character.

```
    | 0 1 2 3 4 X
----+------------
"-" | 0 X 0 0 X X
"_" | X 1 1 X 1 X
"=" | 4 3 X X X X

```

The rightmost column is not stored in the lookup string because the **X** state is actually encoded as *NaN*, which forces any further lookup index to be evaluated to *NaN* as well and leaves the state unchanged till the end.

We don't have to store the trailing **X**'s either.

Hence the final lookup string: `"0X00X" + "X11X1" + "43"`.

## Output

The input is correct if and only if:

* We end up in state **0** or **1**.
* We've reached state **3** or **4** at least once.

# Answer
> 6 votes
# Python, 74 bytes

```
lambda s:0<2*(c:=(s+s[::-1]).count)("_=-")==2*len(s)-c("_")-c("-")+c("_-")

```

Attempt This Online!

## How?

Looking at the counts of certain substrings we can enforce Rules 1,3,4 by requiring that #"-=\_" + #"\_=-" = #"=" and rule 5 by requiring this number be positive.

Rule 2 by requiring neither "-\_" nor "\_-" occurring, i.e. their counts being zero.

Rule 6 by requiring #"=" + #"-" + #"\_" = |s| (the length of the input).

# Answer
> 5 votes
# 05AB1E, ~~25~~ ~~20~~ ~~15~~ ~~13~~ 12 bytes

```
„-_Ãγ'=ýQIË›

```

-2 bytes porting *@UnrelatedString*'s Jelly answer, so make sure to upvote that answer as well!
-1 byte thanks to *@CommandMaster*

Outputs `1` for truthy and `0` for falsey.

Try it online or verify all test cases.

**Previous 15 bytes approach:**

```
'=¡€Ôι€Ù˜{„-_SQ

```

Outputs `1` for truthy and `0` for falsey.

Try it online or verify all test cases.
Or verify all test cases with add debug-lines, to better understand what's going on.

**Original ~~25~~ 20 bytes approach:**

```
ê…-=_ÊI„-_Â‚åI'=¡õåM

```

Outputs a reversed boolean (`0` for truthy; `1` for falsey). If this is not allowed, a single trailing byte can be added to reverse it.

Try it online or verify all test cases.

**Explanation:**

```
„-_Ã      # Only keep the "-_" characters of the (implicit) input-string,
          # removing any other characters
    γ     # Split this string into equal adjacent groups
     '=ý '# Join it with "="-delimiter
        Q # Check if this string is equal to the (implicit) input,
          # resulting in 1 or 0 for truthy/falsey respectively
I         # Push the input-string again
 Ë        # Check if all of its characters are the same (or it's an empty string)
›         # Check that the first check is larger than the second
          # (aka, verify whether the first is truthy and second is falsey)
          # (after which the result is output implicitly)

```

```
'=¡      '# Split the (implicit) input-string by "="
   €      # Map over each substrings:
    Ô     #  Connected uniquify the characters in the substring
     ι    # Uninterleave it into two parts
      €   # Map over both inner lists:
       Ù  #  Uniquify the list of substrings
˜         # Flatten the pair of lists of strings
 {        # Sort it
  „-_SQ   # Check if what remains is equal to pair ["-","_"]
          # (after which the result is output implicitly)

```

```
ê…-=_Ê    # Rules 5 and 6:
ê         #  Sorted-uniquify the characters in the (implicit) input-string
 …-=_     #  Push string "-=_"
     Ê    #  Pop both, and check whether they're NOT equal
I„-_Â‚å   # Rule 1:
I         #  Push the input-string again
 „-_      #  Push string "-_"
    Â     #  Bifurcate it; short for Duplicate & Reverse copy
     ‚    #  Pair the two together: ["-_","_-"]
I     å   #  Check for both whether they occur in the input-string
I'=¡õ    '# Rules 3 and 4:
I         #  Push the input-string yet again
 '=¡     '#  Split it on "="
    õå    #  Check if this list of parts contains an empty string ""
M         # Push the largest integer on the stack (also looks within lists)
          # (after which it is output implicitly as result)

```

# Answer
> 4 votes
# Regex with conditionals, 29 bytes

```
^((?(2)=(?!\2))(-|_)\2*){2,}$

```

Try it online! Link includes test cases. Explanation:

```
^(...){2,}$

```

Match at least two chains.

```
(?(2)=(?!\2))

```

If there is a previous chain, then it must be a different chain separated by `=`.

```
(-|_)\2*

```

Match a chain, but capturing only its first character.

# Regex with lookbehind, ~~31~~ 30 bytes

```
^(-+|_+)(=(-|_)(?<!\3=.)\3*)+$

```

Try it online! Link includes test cases. Explanation:

```
^(-+|_+)

```

Match a leading chain.

```
(...)+$

```

Match at least one more chain.

```
=(-|_)(?<!\3=.)

```

Ensure that each chain differs from the previous chain. (We don't have to match `\3` twice because the `.` much match the `\3` we just captured.)

```
\3*

```

Match the rest of this chain.

# Regex with capture groups, 32 bytes:

```
^(-|_)\1*(=(?!\1)(?<1>-|_)\1*)+$

```

Try it online! Link includes test cases. Explanation:

```
^(-|_)\1*

```

Match an initial chain, but capturing only its first character.

```
(...)+$

```

Match at least one more chain.

```
=(?!\1)

```

Ensure that each chain differs from the previous chain.

```
(?<1>-|_)\1*

```

Match the next chain, but capturing only its first character, pushing it to the original group.

# Answer
> 4 votes
# Charcoal, 28 bytes

```
∧№θ=∧⌊⪪θ=⬤θ№”{“→↘λΠz*”✂θκ⁺³κ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a tplc, nothing if not. Explanation:

```
∧№θ=

```

The input must contain at least one `=`, and...

```
∧⌊⪪θ=

```

... it must not contain leading, consecutive or trailing `=`s, and...

```
⬤θ№”{“→↘λΠz*”✂θκ⁺³κ

```

each sliding window of length 3 must be contained within the compressed string `---=_=-=___=--`.

# Answer
> 4 votes
# Brainfuck, 379 bytes (wrap + soft non-wrap)

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

```

Try it online! Outputs `-` for False and `<` for True. With EOF = 0.

It's been a while since I did anything in brainfuck. I'm sure I missed something that can obviously be golfed further.

This program works for the usual implementation that wraps cells at 255, but also for programs without wrap (soft non-wrap: they accept negative numbers). Accepting negative numbers bloats the size quite a lot, because you always need to go back to a point where you're certain the number isn't negative for `[-]` to terminate. I might come back to simplify the wrapping version, there's at least 65 free bytes to save and maybe more.

It's nice how the ASCII value for `_` (95) is almost double `-` (45) and that `-` and `=` (61) almost have a common divisor of 15. Creating the constants is either unnecessary or can be easily combined.

I did not yet try using a state-machine that sets up the `-` and `_` values and compares each chain to the appropriate one, but I think that could actually make the opposite + valid check simpler.

## Summary of steps

```
LINES 4 TO 6: setup
LINES 8 TO 17: check if valid first character
LINES 19 TO 55: core: consume alleged chain and mark if invalid
  LINES 23 TO 52: not identical: is the next value an equals sign and the value after that the opposite chain
    LINES 26 TO 31: Check if interruption an equals sign
    LINES 33 TO 39: Check if next chain not identical to current
    LINES 42 TO 52: Check if new chain is valid
LINES 57 TO 63: Output

```

## Summary of cells

| When | 0 | 1 | 5 | 6 |
| --- | --- | --- | --- | --- |
| Always (except when being used) | Is there at least one `=` in the chain | Is there NOT \[an invalid transition or an invalid character (including EOF after `=`)\] | 45: `-` | 60: `<`, `=` \- 1 |

| When | 2 | 3 | 4 |
| --- | --- | --- | --- |
| Interrupted by `=`? | Previous chain value | Interrupt - 61 | 60, then next chain |
| Identical chain | 0 | Previous chain value, then 0 | 0 |
| Not identical chain | 0 | 0 | Next chain value |
| Non-destructively `-` or `_`? | 0 or 50 | 45 | 0 or (50, then 0) or (other, then 0) |

## Full code with comments

```
OUTPUTS MINUS FOR FALSE AND LESS THAN FOR TRUE        works both with wrap and without wrap (soft)

LINES 4 TO 6: setup
  >+>>+++[>+++++<-]>              # Create marker for invalid and value 15
  [>+++>++++<<-]                  # Create 45 and 60
  <,[>+<<+>-]>                    # Store first input twice to validate as hyphen or underscore and compare to next values
LINES 8 TO 17: check if valid first character
  >[<-<+>>-]                      # Compare to hyphen
  <[ not a hyphen
    <[>->+<<-]>-----              # Test against 95 underscore and resets 45
    [ not an underscore
      <<<->>>>                    # Mark as invalid
      [<+<+>>-]<<[>+>+<<-]        # Add 90 again
      >+++++[-]                   # Add 5 and reset
    ]
  ]
  <[>>+<<-]                       # Reset 45 if started with hyphen
LINES 19 TO 55: core: consume alleged chain and mark if invalid
  Left (third) cell contains the previous value
  ,[ while there is a new value
    <[>>+<-<-]                    # Compare to previous
    LINES 23 TO 52: not identical: is the next value an equals sign and the value after that the opposite chain
    >[ not same chain check if equals sign
      >[<+<+>>-]                  # Reset value and store for later
      LINES 26 TO 31: Check if interruption an equals sign
        >>[<<<->+>>-]             # Compare to equals sign
        <<<-[ chain interrupt not an equals sign
          <<[-]>>                 # Mark as invalid
          +>[<+>>>+<<-]<[-]       # Reset value and 60 then remove value
        ]
        >[>>+<<-],                # Move 60 back if not already and store next chain value
      LINES 33 TO 39: Check if next chain not identical to current
        <<[>+>-<<-]               # Compare to previous chain value
        >>[ not equal to previous chain
          <[>+<-]                 # Reset new chain value pointer now moves one left
        ]
        <[ non empty only if pointer didn't move left and values were equal
          <<[-]>>[-]<             # Mark as invalid and remove stored value of previous chain
        ]
      <<[-]+>>                    # Mark as having an equals sign in the string
      LINES 42 TO 52: Check if new chain is valid
        >>>[<-<+>>-]              # Compare to hyphen
        <[ not a hyphen
          <[>->+<<-]>-----        # Test against 95 underscore and resets 45
          [ not an underscore
            <<<[-]>>>>            # Mark as invalid
            [<+<+>>-]<<[>+>+<<-]  # Add 90 again
            >++++[-]              # Add 5 and reset; we can add 4 because null would have been filtered already
          ]
          >[<<+<+>>>-]<<<+++++>>  # Add 50 to spot of next chain value
        ]
        <[>+>+<<-]                # Re add 45 if started with hyphen and copy back for comparison to next value
    ]
    >[<<+>>-]<,                   # Set next value and move to start previous
  ]
LINES 57 TO 63: Output
  string ended pointer at 3
  <<<[->+<]>--[<]                 # Move one to the right if valid string
                                    Three options:
                                    * either no equals sign so never go right
                                    * equals sign but also invalid go right then back to left
                                    * equals sign and valid go right then back to left
  >>>>>.                          # Output minus/less than sign

```

# Answer
> 3 votes
# JavaScript (Node.js), 66 bytes

```
a=>!!a.map(c=>a|=s=+"XX22200XX03X1"[s+5*"-_=".indexOf(c)],s=4)&a+s

```

Try it online!

Modified from Arnauld's

`!!a.map(...)` is `true` or `1` when used in bitwise operation.

`a` is the bitor of all historical value of `s`, so if `a` and `s` have different lowest bit then `a` has `1` and `s` has `0`

# Answer
> 3 votes
# Nibbles, 11.5 bytes (23 nibbles)

```
^==*"=";`=|$?"_-"$$_<<

```

Inspired by Unrelated String's Jelly answer.

Outputs a non-empty list (truthy) if the input is a valid, an empty list (falsy) if the input is not valid.

```
^==*"=";`=|$?"_-"$$_<<  # full program
^==*"=";`=|$?"_-"$$_<<$ # with implicit arg added;
          |             # filter
           $            # the input
            ?    $      # for letters that occur in
             "_-"       # "_-"
        `=              # and split into chunks
                  $     # of identical items
       ;                # (save this for later);
   *                    # now join these chunks
    "="                 # using "=" between them
 ==                     # and check if this is equal to
                   _    # the input (1 if it is, 0 otherwise);
^                       # finally, use this value to replicate
                      $ # the saved chunks from earlier
                    <<  # but without the last one

```

# Answer
> 2 votes
# Vyxal `G`, ~~90~~ ~~86~~ 79 bitsv2, ~~11.25~~ ~~10.75~~ 9.875 bytes

```
\_‹↔Ġ\=j₍≈≠

```

Try it Online!

Ports jelly but uses inverted booleans. Truly goofy hours here.

## Explained

```
\_‹↔Ġṅ\=j₍≈≠
   ↔          # The input filtered to only keep characters from
\_‹           # the string "_-"
    Ġṅ        # Grouped on consecutive characters
      \=j     # Joined on "="s
         ₍≈   # Check whether every item is the same (inverted boolean here makes it so that 0 means there's more than one pipe type)
         ₍ ≠  # Check that the string does not equal the input (inverted boolean here means 0 means its the same)

 Created with the help of Luminespire at https://vyxal.github.io/Luminespire

```

# Answer
> 1 votes
# Pyth, 19 bytes

```
q{SM.:{McQ\=2,M]"-_

```

Try it online!

Feels like there's one or two more bytes to be shaved here, but I couldn't get them for now.

### Explanation

```
                       # implicitly assign Q = eval(input())
        cQ\=           # split q on "="
      {M               # deduplicate each element, turning runs into single chars
    .:      2          # get all sublists of length 2
  SM                   # sort each sublist
 {                     # deduplicate the whole list
q            ,M]"-_    # compare to [["-", "_"]]

```

# Answer
> 1 votes
# Python 3, 60 97 bytes

* Edit: missed some of the rules, will revisit!

fun challenge!

```
lambda s:{str({*q})for q in s.split('=')}=={"{'-'}","{'_'}"}and(s.count("-=-")+s.count("_=_")==0)

```

Try it online!

# Python 3.9, 53 bytes

3.9 allows str unpacking/decoding which doesnt work in 3.8 (at least not on TIO). The dreaded "works on my computer" lol.

```
lambda s:{str(*{*q})for q in s.split('=')}=={'-','_'}

```

As always any help is appreciated!

# Answer
> 1 votes
# , 44 bytes

```
1-:&~.2+/\'_-=';@(2<@(,3#~1~:#)@~.;._1@,i.)]

```

Try it online!

Surprisingly difficult problem to golf well in J. I tried a few approaches.

Here we:

* Convert `_-=` to `0 1 2`
* Split on 2, and to each split group...
* Take the unique and...
* Append nothing to it if it has length 1, otherwise append a 3
* The result at this point will have the alternating form `0 1 0 1...` or `1 0 1 0...` iff it is a valid chain
* To check this, we take all sums of consecutive elements, take the unique of the result, and check if it is 1

# Answer
> 1 votes
# JavaScript (Node.js), 84 bytes

Interesting challenge!
This is a more classic JS solution, quite longer than the two "finite-state machine" answers.

```
p=>!p.split`=`.some(a=(s,i)=>(s<1|[...s].some(c=>c!="_-"[((p[0]!='_')+(a=i))%2])))&a>0

```

Try it online!

---

* The two `some` are basically two `every` negated, with their inner condition also negated
* The first `some` parses each string between and around the `=`, and the second `some` parses each character inside each string and controls that they all have the correct value (using the index of the string inside the splitted array, and the starting character of the whole input)
* The `a>0` controls that the input contains at least one `=`
* The `s<1` controls that no string are empty between and around the `=`

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


title: Alternating factorial

text:
# Question
Title: Alternating factorial
The alternating factorial is an alternating sum of decreasing factorials. For example, we could calculate the alternating factorial of 4 as follows:

* First, calculate the factorials from 4 down to 1:

$$ 4!\quad3!\quad2!\quad1!\quad = \\ 4\cdot3\cdot2\cdot1\qquad3\cdot2\cdot1\qquad2\cdot1\qquad1\quad= \\ 24\quad6\quad2\quad1 $$

* Next, insert alternating signs between the products, always starting with \\$\\;-\\$.

$$ 24-6+2-1 = \\ 19 $$

So 19 is the alternating factorial of 4. Mathematically, the alternating factorial is defined as $$ \large\operatorname{af}(n) = \sum\_{i=1}^n(-1)^{n-i}i! $$

For example, $$ \operatorname{af}(4)=(-1)^3\times1!+(-1)^2\times2!+(-1)^1\times3!+(-1)^0\times4!=19 $$ The alternating factorial can also be calculated by the recurrence relation $$ \operatorname{af}(n) = \begin{cases} 0, & \text{if $\\;n=0$} \\ n!-\operatorname{af}(n-1), & \text{if $\\;n\>0$} \end{cases} $$ The sequence of alternating factorials is OEIS A005165.

## Task

Given a non-negative integer as input, output its alternating factorial. You don't need to worry about values exceeding your language's integer limit. This is , so the code with the fewest bytes (in each language) wins.

## Test cases

```
n   af(n)
0   0
1   1
2   1
3   5
4   19
5   101
6   619
7   4421
8   35899
9   326981

```

# Answer
> 10 votes
# Jelly, 4 bytes

```
R!ḅ-

```

A monadic Link that accepts a non-negative integer, \\$n\\$, and yields its alternating factorial.

**Try it online!**

### How?

```
R!ḅ- - Link: n
R    - range (n) -> [1, ..., n-1, n]
 !   - factorial -> [1!, ..., (n-1)!, n!]
   - - -1
  ḅ  - convert from base -1 -> n! - (n-1)! + ... [+/-] 1!

```

# Answer
> 8 votes
# Wolfram Language (Mathematica), 20 bytes

```
AlternatingFactorial

```

Try it online!

# Answer
> 7 votes
# APL(Dyalog Unicode), 6 bytes SBCS

```
¯1⊥∘!⍳

```

Try it on APLgolf!

# Answer
> 6 votes
# Desmos, 28 bytes

```
f(k)=∑_{n=1}^k(-1)^{k-n}n!

```

Try It On Desmos!

Yea, I really could not think of any golfier way than to just copy the formula provided in the question. Not the most creative answer out there but at least it's the golfiest in Desmos (at least it better be....).

# Answer
> 6 votes
# \>\<\> (Fish), ~~53~~ 42 bytes

```
i:?vl1=?n-30.
:?v\:1$:@*$1-
1.\6
00.\~~$1-

```

Try it

The bottom 3 lines calculate the factorial of a number and push it to the stack, the top line just subtracts the top 2 elements from the stack, and prints the top of the stack if there is just one.

After a number is printed, the `-` crashes and the program exits.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 20 bytes

```
Nest[++i!-#&,i=0,#]&

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES6), 28 bytes

```
f=n=>n<2?n:n*f(n-2)+--n*f(n)

```

Try it online!

This is based on the recurrence formula given on OEIS for \\$n \> 1\\$:

$$a(n) = n\times a(n-2) + (n-1)\times a(n-1)$$

This alternate form accepts either Numbers or Bigints as input:

```
f=n=>n<2?n:n--*f(~-n)+n*f(n)

```

Try it online!

# Answer
> 4 votes
# Python, 40 bytes

```
f=lambda n:n>1and~-n*f(n-1)+n*f(n-2)or n

```

Attempt This Online!

Port of @Arnauld's JS answer.

# Answer
> 4 votes
# , ~~29~~ 31 bytes

*Edit: +2 bytes and complete change of approach to fix bug spotted by pajonk*

```
\(x)Reduce(`-`,gamma(x:1+1),,T)

```

Attempt This Online!

# Answer
> 4 votes
# Curry (PAKCS), 48 bytes

```
f 0=1
f x|x>0=x*f(x-1)
g 0=0
g x|x>0=f(x)-g(x-1)

```

Try it online!

My first answer in Curry. I had to determine the factorial because I couldn’t find it in the standard library

# Answer
> 4 votes
# Thunno 2, 6 bytes

```
RR€puḋ

```

(Thunno 2 isn't on ATO yet)

It seems that I forgot to add a "factorial" built-in to Thunno 2...

Port of Jonathan Allan's Jelly answer.

#### Explanation

```
RR€puḋ  # Implicit input                              5
R       # Push the range [1..input]                   [1, 2, 3, 4, 5]
 R      # For each number in this, push its range     [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]]
  €p    # Product of each inner list                  [1, 2, 6, 24, 120]
    uḋ  # Convert from base -1                        101
        # Implicit output

```

# Answer
> 4 votes
# Nibbles, ~~5.5~~ 5 bytes (10 nibbles)

*Edit: -0.5 bytes (1 nibble) thanks to xigoi*

```
/.\,$`*,$-

```

Attempt This Online!

Port of my R answer.

```
/.\,$`/,$*-
 .          # map over
  \         # reverse of
   ,$       # 1..input:
     `*     #   product of
       ,$   #   1..each element
            # (at this point we have list of
            # factorials in reverse order);
/           # now, fold over this from right to left
         -  # by subtraction

```

# Answer
> 4 votes
# MATL, 7 bytes

```
:Yp-1ZQ

```

Try it online!

# Answer
> 4 votes
# Oasis, 4 bytes

```
n!-0

```

Try it online.

**Explanation:**

```
   0 # Start with a(0)=0 (Oasis programs implicitly start with a(0)=1 unfortunately)
     # And calculate every following a(n) by:
  -  #  Subtracting
     #  the implicit previous term a(n-1)
n!   #  from n!
     # (and output the a(implicit input-argument)'th term implicitly as result)

```

# Answer
> 4 votes
# Brain-Flak, 64 bytes

```
{(({})[()]<({([{}]()({}))([{}]({}))}{}{}([{}])((){}))>)}{}({}<>)

```

Try it online!

This does not compute any factorials as intermediate results. Instead, it multiplies by successively smaller numbers and either adds or subtracts one. Sample calculation for the alternating factorial of 5:

```
0  *6 +1 = 1
1  *5 -1 = 4
4  *4 +1 = 17
17 *3 -1 = 50
50 *2 +1 = 101

```

# Answer
> 3 votes
# Jelly, 6 bytes

```
R!_@ƒ0

```

Try it online!

## How it works

```
R!_@ƒ0 - Main link. Takes n on the left
R      - Range; [1, 2, ..., n]
 !     - Factorial; [1, 2, 6, ..., n!]
    ƒ0 - Reduce by the following, beginning with 0:
  _@   -   y - x

```

For a list `[a, b, c, d, e]`, `_@ƒ0` calculates

```
((((0 _@ a) _@ b) _@ c) _@ d) _@ e
= e _ (d _ (c _ (b _ (a _ 0))))
= e - d + c - b + a - 0

```

# Answer
> 3 votes
# Vyxal, 4 bytes

```
ɾ¡uβ

```

Try it Online!

Port of the 4 byte jelly answer

## Explained

```
ɾ¡uβ
ɾ    # range [1, n]
 ¡   # factorial of each
  uβ # converted from base -1

```

# Answer
> 3 votes
# Pyt, 10 bytes

```
řĐ1~⇹^⇹!·Å

```

Try it online!

```
ř                 implicit input (n); řangify [1,2,...,n]
 Đ                Đuplicate
  1~              -1
    ⇹             swap top two elements
     ^            -1^[1,2,3,...,n]
      ⇹           swap top two elements
       !          factorial [1!,2!,3!,...,n!]
        ·         dot product
         Å        Åbsolute value; implicit print

```

Uses that fact that \\$\text{af}(n)=\left|\sum\_{i=1}^n(-1)^i i!\right|\\$

# Answer
> 3 votes
# Retina, 54 bytes

```
~(`.+
.+¶$$.($$'$&*
+`_(_(_+))
$$($.&$*$2$.1$*$1)
__
_

```

Try it online! Link includes test cases. Explanation: Port of @Arnauld's JavaScript answer.

```
~(`

```

Run the output of the rest of the program on the original input.

```
.+
.+¶$$.($$'$&*

```

Convert the input to unary and replace it with a command that replaces the input with an expression that converts the literal unary string back to decimal. The unary string represents `f(n)` at this point.

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

```

For `n>2`, repeatedly apply the recurrence relation `f(n)=n*f(n-2)+(n-1)*f(n-1)` to the unary string. `n` and `(n-1)` are represented in decimal while `f(n-2)` and `f(n-1)` remain represented in unary for the next pass.

```
__
_

```

`f(2)=1` while `f(n)=n` for `n<2` which is already correct.

Example: if `n=7`, then the rest of the program produces the following output:

```
.+
$.($'$(7*$(5*$(3*_2*_)4*$(4*_3*$(3*_2*_)))6*$(6*$(4*_3*$(3*_2*_))5*$(5*$(3*_2*_)4*$(4*_3*$(3*_2*_)))))

```

Retina will evaluate the expression using big integers so the limit is the length of the generated expression which has to fit in memory.

Note that there's an extra `$'` in the final expression in case it is empty to work around a Retina bug whereby `$.()` crashes Retina when it has no elements, but it's fine if it has a non-zero number of empty elements.

The recurrence relation is not used for `f(2)` because that would invoke `f(0)` whose representation would be empty, but `*` defaults to a RHS of `_` i.e. `1`. It could be done by representing `f(n)` with `$(n)` except that this triggers the empty length bug, so it needs another 3 bytes for a second copy of the workaround, making it overall a byte longer:

```
.+
.+¶$$.($$'$&*
~)+`_(_(_*))
$.&$*$$($$'$2)$.1$*$$($1)

```

# Answer
> 3 votes
# Excel, 38 bytes

Defined Name `a`:

```
=LAMBDA(n,IF(n,FACT(n)-a(n-1),))

```

After which, within the worksheet:

```
=a(A1)

```

for an input in cell `A1`.

# Answer
> 3 votes
# Pip, ~~17 16~~ 12 bytes

```
$* *\,\,aFDv

```

Attempt This Online!

Port of Jonathan Allan's Jelly answer.

*-4 thanks to @DLosc*

#### Explanation

```
$* *\,\,aFDv   ; Input on command line
      \,a      ; Range from 1 to input
    \,         ; Range from 1 to each
$* *           ; Product of each inner list
         FDv   ; From a list of digits in base -1
               ; Implicit output

```

Old:

```
({$*\,a}M\,a)FDv   ; Input on command line
         \,a       ; Range from 1 to input
 {     }M          ; Map over this list:
  $*               ;   Product of...
    \,a            ;   ...range from 1 to the number
(           )FD    ; Convert from a list of digits...
               v   ; ...in base -1
                   ; Implicit output

```

# Answer
> 3 votes
# Japt, 4 bytes

```
õÊìJ

```

Try it

```
õÊìJ     :Implicit input of integer U
õ        :Range [1,U]
 Ê       :Factorials
  ì      :Convert from base
   J     :-1

```

# Answer
> 3 votes
# Brachylog, 11 bytes

```
0|-₁↰I&ḟ;I-

```

Try it online!

### Explanation

Uses the recurrence relation.

```
0             af(0) = 0
 |            Or
  -₁↰I        I = af(Input - 1)
      &ḟ;I-   Output = Input! - I

```

# Answer
> 3 votes
# Julia 0.7, 23 bytes

```
!n=n>0?prod(1:n)-!~-n:0

```

Try it online!

Uses the recursive formula.

# Answer
> 2 votes
# Charcoal, 12 bytes

```
Ｉ↨ＥＮΠ…¹⁺²ι±¹

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
   Ｎ            First input as a number
  Ｅ             Map over implicit range
     …          Range from
      ¹         Literal integer `1` to
         ι      Current value
       ⁺        Plus
        ²       Literal integer `2`
    Π           Take the product
 ↨        ±¹    Interpret as base `-1`
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 2 votes
# minigolf, ~~23~~ 22 bytes

```
Ti,n;o,T*:1n,n*_*;+s,_

```

Attempt This Online!

## Explanation

```
T            Push -1 (b)
i,n;         [1..n] range of input
o            Reverse it
,            Map in [n..1]:
  T*:          Multiply (b) by -1 (since -1^0 = 1
  1            Push 1
  n            Push curr. item
  ,n*_         Reduce 1..n by product
  *            mul. w/ b
;            End map
+            sum (works for 0 case since sum of [] is 0)
s,_          drop b

implicit output

```

# Answer
> 2 votes
# PARI/GP, ~~40~~ 35 bytes

saved 5 bytes thanks to the comment.

Try it online!

```
f(n)=abs(sum(m=1,n,prod(k=1,m,-k)))

```

# Answer
> 2 votes
# , 10 bytes

```
_1#.1!@+i.

```

Port of Jonathan Allan's smart Jelly answer.

Attempt This Online!

```
_1#.1!@+i.
        i.  NB. range [0,n)
    1  +    NB. vectorized increment
     !@     NB. factorial of each
_1#.        NB. convert from base -1

```

# Answer
> 2 votes
# C (gcc), 32 bytes

```
f(n){n=n<2?n:n*f(n-2)+f(--n)*n;}

```

Try it online!

*Port of Arnauld's JavaScript answer*

# Answer
> 2 votes
# FunStack alpha, 39 bytes

```
Minus foldl 0 Product map IFrom1 IFrom1

```

Try it at Replit!

### Worked example

```
                4
IFrom1          [1,2,3,4]
IFrom1          [[1],[1,2],[1,2,3],[1,2,3,4]]
Product map     [1,2,6,24]
Minus foldl 0   19

```

where the last bit is

```
Minus          Subtract first argument from second
      foldl    Left-fold on that function
            0  starting with an accumulator value of 0

```

and so our result is -(-(-(-0+1)+2)+6)+24 = 19.

# Answer
> 2 votes
# Raku, 25 bytes

```
{[[&(&[R-])]] [\*] 1..$_}

```

Try it online!

There has got to be a better way of doing that second reduce. For reference, the `[op]` means reduce, the `\` means keep the intermediate values, and the `R` metaoperator reverses the order of the subtraction. So `[\*]` the range 1 to input will return a list of factorials from 1 to input. From this we want to fold right over the list with reversed subtraction, which would be `[R-]` right? However `R-` also has reversed precedence, so `a R- b R- c` is equivalent to `c - b - a` rather than `c - (b - a)`. So we have to make it a function rather than an operator with `&[R-]`, but inserting it into the reduction operator requires an extra pair of `[]`s as well as an `&()` for some reason (but `*R-*` also doesn't work for reasons). This bloats it up to the point where `reduce &[R-]` is now the same length, blergh.

Alternatively, we can construct a sequence and index into it:

# Raku, 30 bytes

*-1 byte thanks to Steffan*

```
{(0,{abs $_-=$*=++$}...*)[$_]}

```

Try it online!

If this IO method ends up allowed as default, then this can be shortened to 23 bytes.

# Answer
> 2 votes
# Haskell, 31 bytes

```
x!1=abs x
x!y=(1-x*y)!(y-1)

```

```
(0!)

```

Attempt This Online!

# Answer
> 1 votes
# 05AB1E, 4 bytes

```
L!®β

```

Port of *@JonathanAllan*'s Jelly answer.

Try it online or verify all test cases.

**Outputting the infinite sequence would be 5 bytes:**

```
0λN!α

```

Try it online.

**Explanation:**

```
L     # Push a list in the range [1, (implicit) input-integer]
 !    # Get the factorial of each
  ®β  # Convert it from a base-(-1) list to a base-10 integer
      # (which is output implicitly as result)

 λ    # Start a recursive environment,
      # to output the infinite sequence
      # (which is output implicitly at the end)
0     # Start with a(0)=0
      # Where every other a(n) is calculated by:
      #  (implicitly push the previous term a(n-1)
    α #  Get the absolute difference between it
  N!  #  and n!

```

# Answer
> 1 votes
# Ohm v2, 15 bytes

```
?@(!1→ρΓ³#R(ⁿ*Σ

```

Try it online!

Ohm is very weird. It thinks that the factorial of `1` is `nil`, doesn't do base conversion from -1 like other answers and doesn't like formatting numbers correctly sometimes.

## Explained

```
?@(!1→ρΓ³#R(ⁿ*Σ
?     # only execute this program if the input is not 0
@(    # the range 2..input
!     # factorial of each
1→ρ  # append 1 to that and rotate right. This is because `1!` gives nil
Γ     # Push -1
³#R(  # range(0, n - 1)[::-1]
ⁿ     # -1 to the power of each of those numbers
Σ     # summed.

```

# Answer
> 1 votes
# Rust, 54 bytes

```
fn a(n:i64)->i64{if n<2{n}else{n*a(n-2)+(n-1)*a(n-1)}}

```

All my attempts at golfing this straightforward recursive solution just made the code longer, so I welcome any help!

Attempt This Online!

# Answer
> 1 votes
# Pyth, 5 bytes

```
aF.!S

```

Try it online!

### Explanation

```
aF.!SQ    # implicitly add Q
          # implicitly assign Q = eval(input())
    SQ    # inclusive range from 1 to Q
  .!      # map to factorial
aF        # fold over the absolute difference

```

# Answer
> 1 votes
# Zsh, 49 bytes

```
r=i=$[$1>0]
for n ({$1..2})((r=r*n+(i=-i)))
<<<$r

```

Try it online!

This turned into a super interesting problem, because managing the right base cases for a recursive solution takes too many bytes. Instead, I came up with an equivalent form:

$$ \mbox{af}(n)=\mbox{af}'(1,-1,n)=\begin{cases} r,i,0 :& 0 \\ r,i,1 :& r \\ r,i,n :& \mbox{af}'(r\cdot n+i,-i,n-1) \end{cases} $$

There's probably a way to make both this form and the program shorter. I had to use `r=i=$[$1>0]` instead of `r=i=1` to get the \\$ n=0 \\$ case, otherwise this program will output `-1`. Also, you may notice that since my program uses a range between `$1` and `2`, that it doesn't follow the recursion above for \\$n = 1\\$. It turns out, looping upwards to 2 results in \\$(1\cdot 1 -1)\cdot 2 + 1 = 1\\$, so it all works out okay.

# Answer
> 1 votes
# x86-64 machine code, 29 bytes

Uses standard System V ABI with signature `long afact(int n)`. The input `n` is taken in `rdi`, and the output is given in `rax`.

```
31 c0 85 ff 74 16 ff c0 57 59 48 f7 e1 e2 fb 50 ff cf e8 e9 ff ff ff 48 29 04 24 58 c3

```

Try it online!

## Explanation

The function implements the recurrence relation \\$\operatorname{af}(n)\\$ as given in the question.

```
afact:
    ; clear rax
    xor eax, eax

    ; return if n=0
    test edi, edi
    jz __afact_retn

    ; factorial first
    ; set eax to 1
    inc eax

    ; n into rcx
    push rdi
    pop rcx

    ; n times:
__afact_flp:
    ; rax *= n(--)
    mul rcx
    loop __afact_flp

    ; n! is in rax
    ; save it
    push rax

    ; get afact(n-1) in rax
    dec edi
    call afact

    ; subtract rax from qword [rsp] (n!)
    sub qword [rsp], rax

    ; pop and return
    pop rax

__afact_retn:
    ret

```

---
Tags: code-golf, math
---


title: The Dating Game / Secretary Problem

text:
# Question
Title: The Dating Game / Secretary Problem
The bots are looking for love. Can you help them?

## The rules

The goal of this game is find the bot you have the highest compatibility with. However, robots, who are inexperienced at dating are unable to tell how well a date went.

In the game, bots take turns "speed dating" some other bot. After each date, each bot chooses whether to get married or to continue dating. If both bots agree to get married both are removed from the dating pool and their compatibility rank (100% is if you found the best one, 0% for the worst one) is their final score.

Bots won't be able to tell what the compatibility is, but they can compare dates. For example if bot A went on a date with bot B and C, they'll be able to tell if B or C was more compatible but not by how much.

Bot A's compatibility with B does not equal B's compatibility with A, but they are correlated.

If every bot has dated every other bot, the ordering is shuffled and any remaining bots can try again. However, everyone's final score is reduced by 25% (exponential) for every round they stay single. If a entire round ends without any new marriages the game ends and all remaining bots get a score of 0.

## Example bot

```
class BetterThanFirst:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """

    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.first_date = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        pass # called if a full round finished, optional

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.first_date is None:
            self.first_date = other
        else:
            return other > self.first_date

```

## Other rules

* No IO
* No RNG except via the provided PRNG
* No inspecting other bots. You are only allowed to use the `>`, `<`, `<=`, `>=`, `==` operators on other bots.
* No exploiting the controller.

## Controller

The controller repo is here: https://codeberg.org/Mousetail/KOTH-dating-game

Results, and the active game (if any) can be viewed here: https://koth.mousetail.nl/

# Answer
# Optimal Average

```
class OptimalAverage:
    def __init__(self, nrof_bots, rng):
        self.test_num = round((nrof_bots - 1)**0.5)
        self.tests = []

    def round_finished(self, nrof_remaining_bots):
        self.test_num = round((nrof_remaining_bots - 1)**0.5)
        self.tests = []

    def date(self, other) -> bool:
        if len(self.tests) < self.test_num:
            self.tests.append(other)
            return False
        else:
            return all(f <= other for f in self.tests)

```

Similar to @Spitemaster's answer but we skip the first \\$\sqrt{n}\\$ bots instead. While their strategy has been proven optimal for maximizing one's chance at getting the best candidate, this strategy is optimal for obtaining the best average score assuming that there is value in candidates that are not the best, which is the case here. Of course this still misses the same important notes; that the opposing bot won't always agree, and that bots will be dropping out as it goes along.
> 7 votes

# Answer
# Optimal Stopping Time

```
class OptimalStoppingTime:
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots - 1)/ 2.718)
        self.dates = []

    def round_finished(self, nrof_remaining_bots):
        pass

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.dates_left > 0:
            self.dates_left -= 1
            self.dates += [other]
        else:
            return all(other >= x for x in self.dates)

```

The optimal stopping time for the secretary problem is to skip the first n/e and then accept any better than the best seen so far. There may be a better strategy because it's not symmetric and other bots may not agree - and it doesn't account for bots dropping out.
> 6 votes

# Answer
# Naive Elitist

```
class NaiveElitist:
    def __init__(self, nrof_bots, rng):
        self.best = None

    def round_finished(self, nrof_remaining_bots):
        pass

    def date(self, other) -> bool:
        if self.best is None or other >= self.best:
            self.best = other
        return other >= self.best

```

This bot will settle for nothing less than the best!

...But it can't imagine that anything better than what it's already found could be possible, even if it's only experienced a single date.
> 4 votes

# Answer
# Crossing out options

```
class crossing_out_options:
    """accepts any bot at least as good as the best remaining bot which it hasn't accepted yet"""
    def __init__(self, nrof_bots, rng):
        self.candidates = []
        self.rejected_me = []
        self.pool = []
        self.first_date = True
    def round_finished(self, nrof_remaining_bots):
        self.candidates = [x for x in self.candidates if x in self.pool]
        self.pool = []
    def date(self, other) -> bool:
        self.pool += [other]
        if self.first_date:
            self.candidates = [other]
            self.first_date = False
            return False
        if other in self.rejected_me:
            return True  # no shame
        if all(other >= x for x in self.candidates):
            self.candidates = [x for x in self.candidates if x != other]
            self.rejected_me += [other]
            return True
        if not other in self.candidates:
            self.candidates += [other]
        return False

```

This bot keeps a list of all the "candidate" bots it has dated but not accepted, and which ones it tried to accept. It accepts the best bot from the candidate list. (Or any better bot, even if they rejected it before! No grudges!). At the end of the round it removes bots from the candidate list if it didn't encounter them this round.

The result is that it accepts any bot that "better than first" would accept, but learns and moves on if its best matches are already taken or don't love it back.
> 4 votes

# Answer
# Always Accepts

```
class EveryoneIsFine:
    """This bot just accepts everyone"""
    def __init__(self, nrof_bots, rng):
        self.botmotto="Accept everyone."
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        return True

```

This bot just doesn't care who they're married to.
> 3 votes

# Answer
# Logger

```
class Logger:
 """Logs how everyone was on the first round (rejecting all) and uses that to determine the best bot."""
 def __init__(self, nrof_bots, rng):
  self.botlist=[]
  self.counter=0
  self.bots=nrof_bots
 def round_finished(self, nrof_remaining_bots):
  self.counter=self.counter+1
  if nrof_remaining_bots!=self.bots:
   self.counter=0
   self.bots=nrof_remaining_bots
 def date(self, other):
  if self.counter==0:
   self.botlist.append(other)
   return False
  else:
   return other==max(self.botlist)

```

This bot gets the best bot by logging each bot and picking the one with the best compatibility. If the bot with the best compatibility marries a bot other than the Logger, ~~the Logger is screwed~~ the logger only notices at the end of the round and re-evaluates each bot.
> 3 votes

# Answer
# C+ dater

```
class c_plus_dater:
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.round = 0
        self.betterbots = 0
        self.bestbot = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.round += 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        marry = False
        if self.bestbot is None:
            self.bestbot = other
        else:
            if other > self.bestbot:
                self.betterbots += 1
                self.bestbot = other
                if self.betterbots >= 3:
                     marry = True
        return marry

```

Edited to avoid comparing a bot to a constant, instead only to each other. This bot takes any bot that is better than at least 3 other bots. But it probably gets buggy in the second round.

Old version: Bot takes anything above 70% in the first round, and lowers its standard each round after that.

\[I'm counting on compatibility being between 0 and 1\]
> 3 votes

# Answer
**The Hopeless Romantic**

This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of times. Which, it turns out, is quite long for robots.

```
class HopeLessRomantic:
    """
    This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of warranty. Which is long for robots.
    """

    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.firstlove= None

    def round_finished(self, nrof_remaining_bots):
        #alas! the light of my live has rejected me. *sad robot noise*
        pass

    def date(self, other) -> bool:
        if self.firstlove is None:
            self.firstlove= other              # madly fall in robolove
            return True
        elif self.firstlove==other:
            return True
        else:
            return False

```
> 3 votes

# Answer
# Optimal Cutoffs

```
import math

def value(n, k, j):
    return sum(i*math.comb(i,j)*math.comb(n-i-1,k-j-1) for i in range(j,n-k+j+1)) / math.comb(n,k)

def get_cutoff(n, k0):
    cutoff = {}
    for k in range(n,0,-1):
        if k >= k0: bst = 0
        z=0
        cutoff[k] = k
        for j in range(k-1,-1,-1):
            v = value(n,k,j)
            if v > bst:
                z += v
            else:
                cutoff[k] = j+(v<bst)
                z += (j+1)*bst
                break
        bst=z/k
    return cutoff

class OptimalCutoffs:
    def __init__(self, nrof_bots, rng):
        self.first_round = True
        n = nrof_bots - 1
        self.cutoff = get_cutoff(n, int(n * 3/4))
        self.met = []
    def round_finished(self, nrof_remaining_bots):
        self.first_round = False
    def date(self, other):
        if not self.first_round: return True
        self.met.append(other)
        self.met.sort()
        if self.met.index(other) >= self.cutoff[len(self.met)]:
            self.met.remove(other)
            return True
        else:
            return False

```

Uses dynamic programming to calculate the optimal cutoffs assuming the bot will meet 3/4 of the other bots, the other bot will always accept, and there is no payoff after the first round. Always accepts in rounds after the first.
> 3 votes

# Answer
# Third Time Lucky

```
class ThirdTimeLucky:
    """Picks the bot from the third date"""
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.number = 1

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.number = 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.number >= 3:
            self.number = 1
            return True
        else:
            self.number += 1
            return False

```

This bot believes that three dates is the correct number to go on and will be happy to marry the third bot. If the other bot refuses, then they go on another three dates, accepting only the third.
> 2 votes

# Answer
# Lower standards

```
class lower_standards:
    def __init__(self, nrof_bots, rng):
        self.sample_size = round((nrof_bots-1)**0.5)
        self.sample = [] # sample of dates (from the first round)
        self.curr = [] # all dates from the current round
        self.prev = [] # all dates from the previous round
        self.pool = nrof_bots - 1 # size of the dating pool
        self.round = 0 # round number
    def round_finished(self, nrof_remaining_bots):
        self.pool = nrof_remaining_bots - 1
        self.prev = self.curr
        self.curr = []
        self.round += 1
    def date(self, other) -> bool:
        self.curr += [other]
        if self.round == 0 :
            if len(self.sample) < self.sample_size :
                self.sample += [other]
                return False
            if all(other >= x for x in self.sample) :
                return True
        else :
            if sum(x > other for x in self.prev) <= len(self.prev) - self.pool + self.round - 1:
                return True
        return False

```

In the first round, this bot behaves like OptimalAverage.

On the second round, it behaves like a much more pessimistic version of Logger. Rather than assuming the current dating pool is the same as in the previous round, it takes into account that some bots have left. When the round ends, it looks at the number of bots still in the dating pool, and assumes that the remaining options are the worst possible subset of the previous round. It then accepts any bot which would be best in this reduced pool.

On the third and subsequent rounds, it becomes even less picky, accepting second best in the pessimistically reduced pool, then 3rd best, etc.
> 2 votes

# Answer
# Wait for it...

```
class wait_for_it:
    """always rejects in the first round,
     then only accepts the top 2 it saw in the previous round,
     until it sees that the game is about to end,
     at which point it panics and accepts anyone."""
    def __init__(self, nrof_bots, rng):
        self.pool_size = nrof_bots
        self.curr = []  # all dates from the current round
        self.prev = []  # all dates from the previous round
        self.end_count = 0  # number of rounds with no matches made
    def round_finished(self, nrof_remaining_bots):
        if nrof_remaining_bots == self.pool_size:
            self.end_count += 1
        else:
            self.end_count = 0
        self.pool_size = nrof_remaining_bots
        self.prev = self.curr
        self.curr = []
    def date(self, other) -> bool:
        self.curr += [other]
        if not self.prev:
            return False
        if self.end_count == 2:
            return True
        if sum(x > other for x in self.prev) <= 1:
            return True
        return False

```

This bot is always a step behind. In each round, it will accept either of the top 2 matches it saw in the previous round. However, it also keeps tabs on the end condition, and if two rounds have gone without a match being made, it will accept anyone to avoid ending up alone.
> 2 votes

# Answer
# Optimal Desperation

```
class optimal_desperation:
    """
    starts out believing in a beautiful theorem it heard about,
    but if that doesn't work out, it takes what it can get
    """
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots-1)/2.718)
        self.best = None
        self.desperate = False
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        if self.desperate:
            return True
        if self.best is None:
            self.best = other
            self.dates_left -= 1
            return False
        if self.dates_left > 0:
            self.dates_left -= 1
            self.best = max(other, self.best)
            return False
        if other >= self.best:
            self.desperate = True
            return True
        return False

```

Inspired by Spitemaster's Optimal Stopping Time, but when its optimally true love rejects it, it gets desperate and says "yes" to anyone and everyone.
> 2 votes

# Answer
# Partygoer

While sober, the partygoer doesn't care for dating. However, it likes meeting new people, so, just for the sake of it, the partygoer decided to join the - hey, look! Beer!

```
class Partygoer:
    """
    Decides when to marry depending on how sober it is. Then, it drinks.
    """

    def __init__(self, nrof_bots, rng):
        self.sobriety = 1.0
        self.rng = rng

    def round_finished(self, nrof_remaining_bots):
        self.sobriety -= .05

    def date(self, other) -> bool:
        limit = self.rng.random()
        flag = False
        if limit > self.sobriety:
            flag = True
        self.sobriety -= 0.01
        return flag

```

Uses the PRNG to decide a limit. Every time it goes on a date, it checks its sobriety. If it's greater than the limit, it decides to marry. Regardless, though, it takes a drink, decreasing its sobriety a little. If an entire round goes past without getting married, it decreases sobriety by a larger margin.
> 2 votes

# Answer
# Anything but the worst

```
class AnythingButTheWorst:
    """
    Will accept anyone as long as there is someone worse
    """

    # rng is a seeded PRNG you can use, no other forms of randomness allowed
    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.worst = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        pass  # called if a full round finished, optional

    def date(self, other) -> bool:  # Return True if you want to marry this bot, False otherwise
        if self.worst is None:
            self.worst = other
        else:
            self.worst = min(self.worst, other)

        return other > self.worst

```

Will settle for any bot except the worst one.
> 1 votes

# Answer
# Adaptive Better-than-median

```
class adaptive_better_than_median:
    """
    accepts bots better than the median,
    while updating the median as the game evolves
    """
    def __init__(self, nrof_bots, rng):
        self.curr = []
        self.prev = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        self.prev = self.curr
        self.curr = []

    def date(self, other) -> bool:
        self.curr += [other]
        if self.prev is None:
            return sum(other > x for x in self.curr) >= len(self.curr)//2
        return sum(other > x for x in self.prev) >= len(self.curr)//2

```

Just what the name says; behaves in the first and second rounds like "Better than Median", but then adjusts the median based on who dropped out in previous rounds.
> 1 votes

# Answer
# Top Three Previous

```
class TopThreePrevious:
    """
    Will marry any of the top three it has seen from the previous round.
    If it's the first round, it flips a coin instead.
    """

    def __init__(self, nrof_bots, rng):
        self.rng = rng
        self.best = []
        self.previousBest = []
        self.bots = []

    def round_finished(self, nrof_remaining_bots):
        self.best = []
        self.bots.sort(reverse = True)
        for i in range(3):
            self.best.append(self.bots[i])
        self.bots = []

    def date(self, other) -> bool:
        self.bots += [other]
        if len(self.best) == 0:
            return self.rng.random()>0.5
        return other in self.best

```

This bot simply checks if the bot it's currently dating was one of the top three it has seen in the previous round, or flips a coin if it's the first round (it uses the length of `self.best` to determine this).
> 1 votes

# Answer
# T

#### \*** not working \***

```
class T:
    def __init__(self, nrof_bots, rng):
        self.NR    =  nrof_bots
        self.d     =  {}
        self.mc    =  0
        self.r     = 1
        self.rc    = 1
        self.xrs   = []               # unseen in current round
        self.x     = set()            # seen in previous round
        self.xn    = []               # seen in this round
        self.c     =  0              # for debugging
    def update(self, other):
        self.c += 1
        self.rc += 1
        if other not in self.d: self.d[other] = 0 # Set if new
        self.d[other] += 1
        self.mc = max(self.mc, self.d[other])     # Highest number seen
        if self.mc > self.r: # update round
            missing_in_round = set(self.x).difference(set(self.xn))
            NR_ = self.NR - len(missing_in_round)
            self.NR = NR_
            self.r = self.mc                         # set round
            self.x = set(self.xn)                        # seen in prev round
            self.xrs = self.xn                           # All are unseen
            self.xn = []                                 # reset round
            self.rc = 1
        self.xn.append(other)
        xrs_ = set(self.xrs).difference({other})      # update unseen
        self.xrs  = list(xrs_)
        self.xrs.sort()                               # sort unseen

    def get1(rc, NR, xrs, xn):
         average_acceptance = 0.3
         N_ = NR - rc * 0.3
         dec = 0.7 * N_ / (N_+ 1)
         return dec

    def getd(rc, NR, xrs, xn):
        if len(xrs) == 0: # end of round
            xn_ = xn.copy()
            xn_.sort()
            dec = xn_[round(len(xn_) * 0.7)]
        else:
            dec = xrs[min(round(NR*0.7 - rc*0.14), len(xrs) - 1)]
        return dec

    def round_finished(self, nrof_remaining_bots):
        return None

    def date(self, other): # Return True if you want to marry this bot, False otherwise
        self.update(other)
        espouse = other >= (T.getd,T.get1)[self.r==1](self.rc, self.NR, self.xrs, self.xn)
        print(f'{self.c}:{other:3.2f} :::{espouse}')
        return espouse

```
> 1 votes

# Answer
```
class IDK_bot:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        import math
        self.rng=rng
        self.numbots=nrof_bots
        self.dates=[]
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.num=0
        self.rounds=0

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        import math
        self.numbots=nrof_remaining_bots
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.rounds+=1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        self.dates.append(other)
        self.dates.sort()
        self.num+=1
        if self.num<self.cutoff:
            return False
        score=self.dates.index(other)/self.num
        if score<0.5:
            return False
        return self.rng.random()<=score*(self.num/self.bots*1.2)**(1/3)*(1+self.rounds/5)

```

The bot defines a "cutoff" based on the `n/e` rule which has been proven to be approximately optimal for the secretary problem. However, since you aren't guaranteed to see every possible date, that limit is raised to the 4/5th power (an arbitrary number I selected) to give more potential candidates to select.

The actual selection is based on RNG. The bot first calculates the date's score, which is the relative ranking of the date in relation to the other dates it has seen, represented as a number from 0 to 1. The bot rejects any candidate with a score less than 0.5. The bot multiplies the score by a bunch of math, effectively taking into account the fraction of dates seen so far and how many rounds it has been in.

This lets the "score" be the largest part in deciding whether or not to accept a candidate, but also makes it so that the probability of acceptance increases as more bots are seen and as more rounds pass.

I haven't been able to test this, so please let me know if there are any bugs I need to fix.
> 1 votes

---
Tags: king-of-the-hill, python, optimization
---


title: Compute the maximal Ducci period

text:
# Question
Title: Compute the maximal Ducci period
Given an initial \\$n\\$-tuple \\$t\_0=(t\_{0,1},...,t\_{0,n})\\$, we can obtain its corresponding Ducci sequence \\$\\{t\_0, t\_1, ...\\}\\$ by the recurrence \\$\displaystyle t\_{i+1}=\left(\left|t\_{i,1}-t\_{i,2}\right|,\left|t\_{i,2}-t\_{i,3}\right|,...\left|t\_{i,n}-t\_{i,1}\right|\right)\\$.

That is, to obtain the next term of the sequence, we take the absolute differences of successive terms of \\$t\_i\\$, treating it as cyclic; by convention, the first element corresponds to the difference of the first two elements of \\$t\_i\\$.

When the initial tuple \\$t\_0\\$ consists of integers, such sequences are always eventually periodic. For example,
\\$(3,1,4)\to(2,3,1)\to(1,2,1)\to\underline{(1,1,0)}\to(0,1,1)\to(1,0,1)\to\underline{(1,1,0)}\\$
has a cycle of length 3.

## Task

Given a length \\$n\\$, compute the maximum cycle length among all Ducci sequences on tuples of \\$n\\$ integers.

This is A038553 on OEIS.

### Test cases

```
1       1
2       1
3       3
4       1
5       15
6       6
7       7
8       1
9       63
10      30
11      341
12      12
13      819
14      14
15      15
16      1
17      255
18      126
19      9709
20      60
21      63
22      682
23      2047
24      24
25      25575
37      3233097
51      255

```

# Answer
> 8 votes
# JavaScript (ES6), 62 bytes

```
n=>eval(`for(m=1,o=j=[];!o[m^=m/2^m%2<<n-1];o[m]=j++);j-o[m]`)

```

Try it online!

---

## 54 bytes

A recursive version, failing earlier.

```
f=(n,m=1,j=o=[])=>++j-o[m]||f(n,m^m/2^m%2<<n-1,o[m]=j)

```

Try it online!

---

## 65 bytes (ES11)

A BigInt version. This one can process all test cases on TIO.

```
n=>eval(`for(m=1n,o=j=[];!o[m^=m/2n^m%2n<<~-n];o[m]=j++);j-o[m]`)

```

Try it online!

---

## How?

The main observation here is that a necessary condition for a cycle to appear is that the only remaining elements in the tuple are \\$0\\$ and some \\$v\>0\\$. And because we're only interested in the maximum cycle length, it doesn't matter what happens before we reach this state.

When all elements in the tuple are in \\$\\{0,v\\}\\$, we have:

$$\left|t\_{i,j}-t\_{i,j+1}\right| = t\_{i,j} \operatorname{XOR} t\_{i,j+1}$$

We can arbitrarily choose \\$v=1\\$ and turn the \\$n\\$-tuple representation into a bit mask \\$m\\$. This allows us to apply all updates at once by doing the following 'XOR rotation':

```
m ^= m / 2 ^ m % 2 << n - 1

```

# Answer
> 3 votes
# Jelly, ~~11~~ ~~10~~ 8 bytes

```
Ṭṙ1ạƊÐḶL

```

Try it online!

*-2 thanks to Bubbler*

Just another port of Arnauld's approach. Now very straightforward, but check the edit history for a good laugh.

```
Ṭ           Create a list with a 1 at index n and 0s elsewhere.
    ƊÐḶ     Repeat while unique, collecting only the cycle:
 ṙ1         rotate once
   ạ        and take element-wise absolute differences with unrotated elements.
       L    How long is the cycle?

```

# Jelly, 11 bytes

```
&NṬnṬṙ1nƊƬL

```

Try it online!

It's longer, but worth showing off how to apparently guarantee starting within a cycle. Namely, when starting with the single-1 tuple as in the approach above, the state that begins the cycle appears to always be the XOR of two single-1 states, rotated relative to each other by the largest power of 2 that divides the length.

```
&N             Bitwise AND n with its two's complement.
&N             This gives the largest power of 2 which divides it.
  Ṭ            Create a list with a 1 at that index and 0s elsewhere.
    Ṭ          Create a list with a 1 at index n and 0s elsewhere.
   n           For each element, are they not equal?
        ƊƬ     Repeat while unique:
       n       elementwise inequality with
     ṙ1        the current tuple rotated once.
          L    How many distinct tuples did this produce?

```

# Answer
> 2 votes
# Python3, 145 bytes:

```
def f(n):
 m=[];v=[I==0for I in range(n)]
 while v not in m:m+=[v];v=[abs(v[I]-v[I+1if I+1<n else 0])for I in range(n)]
 return len(m)-m.index(v)

```

Times out on \\$n = 37\\$.

Try it online!

# Answer
> 2 votes
# Pyth, 17 bytes

```
LaVb.<b1l.uyNuyGU

```

Try it online!

Relies on the same as yet unproven assumption that @Arnauld makes, being that the maximum cycle can always be found by starting with `[1, 0, 0, 0, ...]`.

### Explanation

```
LaVb.<b1l.uyNuyGUQ    # implicitly add Q
                      # implicitly assign Q = eval(input())
L                     # define y(b)
 aV                   #   absolute difference, vectorized of
   b.<b1              #   b and b shifted one left (cyclically)
                UQ    # list(range(Q))
             uyG      # repeatedly apply y until a result that has been seen occurs
         .uyN         # repeatedly apply y until a result that has been seen occurs and accumulate all intermediate results
        l             # take the length of this list

```

# Answer
> 1 votes
# Python 2, 58 bytes

```
f=lambda n,k=1:~-2**2**n*k%~-2**n<1or-~f(n,k^1^k*2%~-2**n)

```

Try it online!

A recursive function, outputting True for 1. This will fail on large outputs due to exceeding the maximum recursion depth, which is around 1000 by default. Here's a longer iterative version, though it times out for larger inputs thanks to its double-decker power \\$2^{2^n}\\$.

**62 bytes**

```
N=2**input()
k=i=1
while~-2**N*k%~-N:k^=1^k*2%~-N;i+=1
print i

```

Try it online!

Here's the above but more optimized for speed.

**70 bytes**

```
n=input()
N=2**n
k=i=1
while~-2**(N%n)*k%~-N:k^=1^k*2%~-N;i+=1
print i

```

Try it online!

# Answer
> 1 votes
# Charcoal, 33 bytes

```
≔ＥＮ∧ι¹θＷ¬№υθ«⊞υθ≔Ｅθ⁼κ§θ⊕λθ»Ｉ⊕⌕⮌υθ

```

Try it online! Link is to verbose version of code. Explanation: Port of @Ajax1234's Python answer, but with inverted logic.

```
≔ＥＮ∧ι¹θ

```

Start with an array of length `n` whose first entry is `0` and remaining entries are `1`.

```
Ｗ¬№υθ«

```

Repeat until a cycle is detected.

```
⊞υθ

```

Save the current state.

```
≔Ｅθ⁼κ§θ⊕λθ

```

Update the state by comparing each value to the next.

```
»Ｉ⊕⌕⮌υθ

```

Output the length of the cycle.

A more efficient version using a dictionary and bit twiddling weighs in at 48 bytes, but can handle `n=29` on ATO:

```
≔⊖Ｘ²Ｎθ≔¹η≔⦃⦄ζＷ¬§ζη«§≔ζηＬζ≔﹪⊗ηθε≔⁻｜ηε＆ηεη»Ｉ⁻Ｌζ§ζη

```

Attempt This Online! Link is to verbose version of code.

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


title: Magic popcount numbers

text:
# Question
Title: Magic popcount numbers
There’s a famous tricky algorithm for counting the number of set bits in a 32-bit unsigned integer:

```
int popcount(unsigned x) {
   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
   return x;
}

```

I won’t explain it here. But imagine similar code for 512-bit integers! The hexadecimal constants would be huge, and form a pretty pattern. Your task is simply to **print this exact output**:

```
0x55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555
0x33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff
0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff
0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff
0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff
0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000000000000000000000000ffffffffffffffffffffffffffffffff
0x0000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

```

No trailing spaces, please — though a single trailing newline is optional.

This is , so the shortest answer (in bytes) wins.

# Answer
> 3 votes
# 05AB1E, ~~26~~ ~~22~~ 21 bytes

05AB1E uses the CP-1252 encoding.

```
9F„0x0NÍo×9ooNoo>÷hJ,

```

Try it online!

**Explanation**

```
9F                      # for N in [0 ... 8]
  „0x                   # push the string "0x"
     0NÍo×              # push 2**(N-2) zeroes
          9oo           # 2**2**9
                 ÷      # //
             Noo>       # (2**2**N+1)
                  h     # converted to base-16
                   J    # join everything to string
                    ,   # print with a newline

```

**Other versions that might be improved**

```
9F9ooNoo>÷h¾6o×J7o£R…0xÿ,
9F9ooNoo>÷h0žy×ìR7o£R…0xÿ,
9FX0No×1No×JCh7o×1K7o£…0xÿ,
8ÝovX0y×1y×JCh7o×1K7o£…0xÿ,
9F1NoÅ0D>)˜JCh1K7o×7o£…0xÿ,

```

# Answer
> 20 votes
# Python 2, 52 49 46 bytes

The kth number is given by `2**512/(2**2**k + 1)`. This is for a 512 bit number, so it's trivial to extend the pattern to different widths.

```
l=2;exec"print'0x%0128x'%(2**512/-~l);l*=l;"*9

```

3 bytes saved thanks to Dennis.
3 bytes saved thanks to xnor.

# Answer
> 7 votes
# PHP, ~~111~~ ~~110~~ 108 bytes

One byte saved thanks to @user59178.

```
<?=($p=str_pad)("0x",130,5).$p($s="\n0x",131,3);for($x=1;$x<65;$x*=2)echo($p($s,131,$p(0,$x,0).$p(f,$x,f)));

```

What´s the pattern for 1024 bits? :D

# Answer
> 7 votes
# Vim, 32 bytes

`i5<CR>3<Esc>qqYpVrf$<C-V>{yPG1vr0q6@q<C-V>{I0x<Esc>`

I only need to manually write the first `5` and `3`, and the macro takes care of the rest, "doubling the bit count" each time it runs. The order of the steps in the macro is a bit weird (make a new `f` line, block-wise copy, reuse the visual block size to put `0`s in the `f` line), but it's the fastest variant I've found.

# Answer
> 6 votes
# J, ~~46~~ 34 bytes

~~I'm working on golfing this, but this baby likes to stay at 46 bytes...~~ Not anymore! -12 bytes thanks to miles!

```
'0x',"1'5','3','0f'(128$#)"{~2^i.7

```

Try it online! :D

## Result

```
   '0x',"1'5','3','0f'(128$#)"{~2^i.7
0x55555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555
0x33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff
0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff
0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff
0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff
0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000000000000000000000000ffffffffffffffffffffffffffffffff
0x0000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

```

---

For this answer, I needed (ideally) a verb with rank `0 1` so as to use it in the `u"v` definition of rank; however, miles observed that `0 _` was sufficient for the task at hand.

```
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│= │< │<.│<:│> │>.│>:│+ │+.│+:│* │*.│*:│_ 0 0│_ 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│- │-.│-:│% │%.│%:│^ │^.│$ │$.│$:│~.│~:│0 0 0│0 _ _│0 _ _│0 0 0│2 _ 2│0 0 0│0 0 0│0 0 0│_ 1 _│_ _ _│_ _ _│_ 0 0│_ 0 0│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│| │|.│, │,.│,:│; │;:│# │#.│#:│! │/:│\:│0 0 0│_ 1 _│_ _ _│_ _ _│_ _ _│_ _ _│1 _ _│_ 1 _│1 1 1│_ 1 0│0 0 0│_ _ _│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│[ │[:│] │{ │{.│{:│}.│}:│".│":│? │?.│a │_ _ _│_ _ _│_ _ _│1 0 _│_ 1 _│_ 0 0│_ 1 _│_ 0 0│1 _ _│_ 1 _│0 0 0│_ 0 0│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│A │A.│b │C │C.│d │D │e │e.│E │E.│f │H │_ _ _│1 0 _│_ _ _│_ _ _│1 1 _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│0 _ _│_ _ _│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│i │i.│i:│I │I.│j │j.│L │L.│M │o │o.│p │_ _ _│1 _ _│0 _ _│_ _ _│1 _ _│_ _ _│0 0 0│_ _ _│_ 0 0│_ _ _│_ _ _│0 0 0│_ _ _│
├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│p.│p:│q │q:│r │r.│s │s:│S │t │T │u:│x:│1 1 0│0 _ _│_ _ _│0 0 0│_ _ _│0 0 0│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│_ _ _│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

```

Here you see a bunch of verbs' string representations with their respective ranks. This is the script I used to generate it.

# Answer
> 6 votes
## Retina, 43 bytes

```
:`
0x128$*5
:`5
3
;{:`33
0f
0(f+)(0+)
0$2$1

```

Try it online!

### Explanation

This makes a lot of use of the generally underused `:` option which lets you print intermediate results, because it's a lot shorter to modify a single line than to build up the whole output.

```
:`
0x128$*5

```

This replaces the empty input with `0x` followed by 128 `5`s and prints it to generate the first line.

```
:`5
3

```

This one replaces the `5`s with `3`s to generate the second line and prints it as well.

```
;{:`33
0f

```

This is the last special-cased line and it turns every two `3`s into `0f` to generate the third line. This also starts a loop through the last two stages (`{`). However, this stage won't do anything after the first iteration except print the current state. The `;` suppresses the output at the very end of the program to avoid duplicating the last line.

```
0(f+)(0+)
0$2$1

```

This substitution now transforms each line into the next, by swapping every other pair of `f`s and `0`s. The "every other pair" condition is enforced by matching a zero in front of the `f`, which makes it impossible to match consecutive pairs since matches cannot overlap.

# Answer
> 5 votes
# Pyth, 26 bytes

```
V9%"0x%0128x"/^2 512h^2^2N

```

Port of my Python answer.

# Answer
> 4 votes
# JavaScript (Firefox 30+), ~~139~~ ~~113~~ ~~112~~ ~~92~~ ~~83~~ 80 bytes

```
_=>[for(x of"970123456")(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)].join`
`

```

Finally hit the recursive sweet spot :-) Uses a handy-dandy string comprehension to save 3 bytes over `.map`:

```
_=>[..."970123456"].map(x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)).join`
`

```

`.replace` is also 83 bytes:

```
_=>"970123456".replace(/./g,x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):'0x')(128)+`
`)

```

If a leading newline were allowed, this would also be 80 bytes:

```
_=>"970123456".replace(/./g,x=>(f=y=>y--?f(y)+(x>6?x-4:y>>x&1&&'f'):`
0x`)(128))

```

# Answer
> 4 votes
# Actually, 25 bytes

```
9r`╙╙u9╙╙\#"0x%0128x"%`Mi

```

Try it online!

This solution uses the fact that `f(n) = 2**512//(2**2**n + 1)` (where `//` is floored division) to compure the values.

Explanation:

```
9r`╙╙u9╙╙\#"0x%0128x"%`Mi
9r`╙╙u9╙╙\#"0x%0128x"%`M   for n in range(1, 10):
      9╙╙\                   2**2**9//
   ╙╙u                                (2**2**n + 1)
          #"0x%0128x"%       pad with zeroes to 128 digits, prefix with "0x"
                        i  flatten and implicitly print

```

# Answer
> 3 votes
# Python 2, 60 bytes

```
k=1
exec"print'0x%0128x'%int(256/k*('0'*k+'1'*k),2);k*=2;"*9

```

Try it online!

# Answer
> 3 votes
# Bubblegum, 65 bytes

```
00000000: c5cb 4501 0441 1043 d17b d4fc 254b d110  ..E..A.C.{..%K..
00000010: f7cb 9761 9e7a 8d45 e451 4ce4 564c 04d7  ...a.z.E.QL.VL..
00000020: 2e11 b02b 8f08 80df aa5e 11fe fc77 762c  ...+.....^...wv,
00000030: 428b 5b8e ae8b 30c1 13b6 ce8b b091 377a  B.[...0.......7z
00000040: 01                                       .

```

Obligatory Bubblegum answer.

# Answer
> 3 votes
# Haskell, ~~84~~ 72 bytes

Porting @orlp's answer:

```
import Text.Printf
mapM(\n->printf"0x%0128x\n"$div(2^2^9)$2^2^n+1)[0..8]

```

94 byte alternatives without the power of `Text.Printf`:

```
import Data.List
mapM(putStrLn.("0x"++))$transpose$("53"++).reverse<$>sequence(["0f"]<*[1..7])

r=[0..127]
mapM(putStrLn.("0x"++))$('5'<$r):('3'<$r):[["0f"!!mod(div x(2^y))2|x<-r]|y<-[0..6]]

```

# Answer
> 3 votes
## Batch, 216 bytes

```
@echo off
set s=5
call:c
set s=3
call:c
set a=0
set b=f
for /l %%i in (1,1,7)do call:l %%i
exit/b
:l
set s=%a%%b%
:c
for /l %%j in (0%1,1,6)do call set s=%%s%%%%s%%
echo 0x%s%
set a=%a%%a%
set b=%b%%b%

```

# Answer
> 3 votes
## JavaScript (ES6), ~~74~~ ~~72~~ 70 bytes

Includes the optional trailing newline.

```
f=(i=1152)=>i--?f(i)+(i&127?'':`
0x`)+('53'[y=i>>7]||i&1<<y-2&&'f'):''

```

```
f=(i=1152)=>i--?f(i)+(i&127?'':`
0x`)+('53'[y=i>>7]||i&1<<y-2&&'f'):''

console.log(f())
```

# Answer
> 3 votes
# Ruby, ~~66 60~~ 45 bytes

```
x=2;9.times{puts"0x%0128x"%(2**512/-~x);x*=x}

```

Try it online!

Idea stolen from orlp

# Answer
> 3 votes
## PowerShell v2+, 68 bytes

```
5,3|%{"0x"+"$_"*128}
($a=1)..7|%{"0x"+('0'*$a+'f'*$a)*(128/($a*=2))}

```

PowerShell doesn't have arbitrary precision integers without using `[bigint]` calls, and those can't be easily converted to hexadecimal, so we're instead treating this as a string-based challenge.

The first line handles the repeating `5` and `3` by just doing a string multiplication out to `128` characters and tacking a `0x` on the front.

The next line loops from `$a=1` to `7`, each iteration outputting another string. Again we have the `0x` tacked onto the front, and we're doing string multiplication in the middle to construct the appropriate number of `0` and `f` concatenated together, and then doing string multiplication of *that* out to the appropriate number of characters. Note we're using variable `$a` here, and not the loop counter `$_`, so we can properly scale (otherwise we'd need to loop like `1,2,4,8,16,32,64|%{...}`, which is longer).

The resulting strings are left on the pipeline, and output via implicit `Write-Output` happens at program completion, with a newline between elements.

# Answer
> 3 votes
# , 43 bytes

```
64i0fòYpÓ¨¨0«©¨f«©©û2}/²²³³òdd{3ÄÒ5jÒ3Îi0x

```

Try it online!

This uses one of the longest compressed regexes I've ever needed in a V answer. Here is the more readable version, where I added a byte for readable regexes, and changed the unprintable escape character to `<esc>`

```
64i0f<esc>òYpÓö((0+)(f+)){2}/²²³³òdd{3ÄÒ5jÒ3Îi0x

```

Explanation (using the readable version):

```
64i0f<esc>                                          " Insert 64 "0f"s and escape to normal mode
          ò                      ò                  " Recursively:
           Yp                                       "   Duplicate this line
             Ó                                      "   Substitute:
              ö                                     "     (Optionally Turn the readable version on)
               ((0+)(f+))                           "     One or more '0's followed by one or more 'f's
                         {2}                        "     Repeated twice
                            /                       "   With:
                             ²²                     "     The second capture group twice (the '0's)
                               ³³                   "     Followed by the third capture group twice (the 'f's)
                                                    "   Once the search is not found, the loop will break
                                  dd                " Delete a line (because we have one too many)
                                    {               " Move to the first line
                                     3Ä             " Make three copies of this line
                                       Ò5           " Replace the first one with '5's
                                         jÒ3        " Move down a line and replace the second with '3's
                                            Î       " On every line:
                                             i0x    "   Insert a '0x'

```

# Answer
> 2 votes
# Pyth - ~~31~~ 30 bytes

To get pattern except for the `3`'s and `5`'s it cumulative reduces, each time doubling the chunks.

```
jm+"0x".[dd128+`3+`5.u.iNN6"0f

```

Try it online here.

# Answer
> 2 votes
# Vim 72 bytes

```
i0x128a5Ypll128r3o0x64a0fa0Ypqqffdt0fft0p@qq@qqwYp@qq@w@w@w@w:%s/0$

```

TryItOnline!

Unprintables:

```
i0x^[128a5^[Ypll128r3o0x^[64a0f^[a0^[Ypqqffdt0fft0p@qq@qqwYp@qq@w@w@w@w:%s/0$

```

The 4 `@w`s at the end are bugging me, but because I was relying on the `@q` to fail out at the end of a line, it fails out the @w as well. I might try just running q 32 times and seeing if it messes up the later lines.

# Answer
> 2 votes
# GNU sed 4.2.2, 77

```
s/^/0x5/
:
s/x5{,127}$/&5/
t
p
y/5/3/
p
s/33/0f/gp
:a
s/(f+)(0+f+)/\2\1/gp
ta

```

Try it online.

# Answer
> 2 votes
# C, 146 bytes

```
#define F for(i=0;++i<129;)s[i+1]=
#define P ;puts(s);
i,j;f(){char s[131]={'0','x'};F'5'P F'3'P for(j=1;(j*=2)<129;){F(i-1)%j<j/2?'0':'f'P}}

```

Ungolfed:

```
#define F for(i=0;++i<129;)s[i+1]=
#define P ;puts(s);
i,j;f(){
  char s[131]={'0','x'};
  F'5'P
  F'3'P
  for(j=1;(j*=2)<129;){
    F(i-1)%j<j/2?'0':'f'P
  }
}

```

# Answer
> 2 votes
# brainfuck, 211 bytes

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

```

Try it online!

# Answer
> 1 votes
# C#, 168 bytes

```
()={string R="",o="0",f="f";for(int i=0,j;i<9;i++){R+="0x";if(i>2){o+=o;f+=f;}for(j=0;j<128;){R+=i<1?"5":i<2?"3":o+f;j+=i>1?(int)Math.Pow(2,i-1):1;}R+="\n";}return R;};

```

# Answer
> 1 votes
# Stax, 19 bytes

```
⌡hÅék╝94"ºé♪╛#V┐5í╒

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
512r        [0..511]
{:Brm       convert each to bits and reverse each
M           transpose matrix, filling missing elements in rectangle with zero
m           map over each element of array, using the rest of the program.  outputs implicitly.
  4/        split bits into groups of 4
  {:b|Hm    convert each 4-bit binary number to single digit hex string
  .0xp      print "0x" without newline

```

Run this one

# Answer
> 1 votes
# ///, 193 bytes

```
/*/\/\///X/
0x*F/5555*G/FFFF*T/3333*U/TTTT*o/0f0f*1/oooo*t/00ff*2/tttt*g/0000*h/ffff*4/ghgh*6/gghh*7/gggg*8/hhhh*9/7788/0xGGGGGGGGXUUUUUUUUX11111111X22222222X44444444X66666666X78787878X99X77988

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 72 bytes

```
n=1n<<512n;f=(i=2n)=>i-n?`
0x`+(n/-~i+n).toString(16).slice(1)+f(i*i):''

```

Try it online!

# JavaScript (Node.js), 69 bytes from Arnauld's

```
f=(i=4608)=>i?f(i-=4)+(i&508?'':`
0x`)+('53'[y=i>>9]||i&1<<y&&'f'):''

```

Try it online!

# Answer
> 1 votes
# Vyxal `j`, 136 bitsv1, 17 bytes

```
‛0x53f‛0f6ʀE•J₇vẎ+

```

Try it Online!

Math? No we don't do that here. We do string manipulation instead.

## Explained

```
‛0x53f‛0f6ʀE•J₇vẎ+
      ‛0f           # The string "0f"...
            •       # with each character repeated n times...
         6ʀE        # for each n in [2**x for x in range(0, 7)].
             J      # Appended to...
   53f              # the list [5, 3].
# The top of the stack is [5, 3, "0f", "00ff", "0000ffff", ...]
              ₇vẎ   # Take the first 128 items of each item.
                    # This reuses previous digit/chars if the item isn't long enough
‛0x              +  # Add the string "0x" to each item
# The j flag joins on newlines before printing

 Created with the help of Luminespire at https://vyxal.github.io/Luminespire

```

---
Tags: code-golf, string, kolmogorov-complexity, hexadecimal
---


title: Measure the Diamond Road

text:
# Question
Title: Measure the Diamond Road
## Background

You are planning your trip away from the Diamond City, and must travel through Diamond Road. However, Diamond Road branches away from Diamond City to different locations.

Out of curiosity, you'd like to measure the total distance of unique roads used for all paths.

We define a path as a string that only contains `/` or `\`, which represent roads. You will be given a list of paths that can be traversed.

Starting from a central left most point, a path can be plotted on a map such that every `/` denotes a path upwards and every `\` denotes a path downwards. On every path, each road must strictly go from left to right.

Subsequent roads must be joined at the same level as the previous road if they are different types. If they are the same type, the level will change.

For example:

Given `//\\/\\\`

The map generated would be:

```
              /\
Start here _ /  \/\
                   \
                    \

```

Since you can have multiple paths, these paths may cross and share the same road.

For example:

Given `/\ /\/`

The map generated would be:

```
Start here _ /\/

```

Here, the first two roads in both paths are shared, but the total length of roads used would be 3, as shown on the map.

You must calculate the amount of unique roads used in all paths.

## Your Task

* Sample Input: A list of paths used, or a string of paths separated by spaces.
* Output: Return the total length of roads used.

**Explained Examples**

```
Input => Output

/ \ / \ => 2

Map:

Start here _ /
             \

Of the roads used, the total distance is 2.

```

```
Input => Output

/\/ \/\ /// => 8

Map:
               /
              /
Start here _ /\/
             \/\

Of the roads used, the total distance is 8.

```

```
Input => Output

//// \/\/ /\/\ //\\ => 12

Map:
                /
               /
              /\
Start here _ /\/\
             \/\/

Of the roads used, the total distance is 12.

```

```
Input => Output

/\//\//\/ \/\/\\//\ \//\/\/\/ \//\//\// /\/\/\/ \/ \\\ \//\/ \ => 28

Map:

                   /\/
                /\/\/
Start here _ /\/\/\/\/
             \/\/\  /\
              \   \/
               \

Of the roads used, the total distance is 28.

```

**Test Cases**

```
Input => Output
/ \ / \ => 2
/\/ \/\ /// => 8
//// \/\/ /\/\ //\\ => 12
/\//\//\/ \/\/\\//\ \//\/\/\/ \//\//\// /\/\/\/ \/ \\\ \//\/ \ => 28

\ => 1
/ => 1
\ \/\ => 3
/\ \/\/\/ => 8
/\ / \/\ \ => 5
//////////////////// => 20
////////// ////////// => 10
////////// \\\\\\\\\\ => 20
\ /\ \/ /\ \\\\\\\\\\ => 13
\/\ /\/ //\ \\/ \/ /\ / \ => 10
/\ /\/ /\/\ /\/\/ /\/\/\ /\/\/\/\ => 8
/\ \/ /\ /\ \/ /\ /\ \/ \/ \/ /\ /\ => 4
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ / => 2

```

This is , so shortest answer wins.

ps. I need help with tagging this question

# Answer
> 11 votes
# Python, 59 bytes

```
lambda L,*i:len({i:=(*sorted(i),d)*(d>" ")for d in L}-{()})

```

Attempt This Online!

Takes inputs as in the test cases, i.e. a single space separated string.

## How?

Encodes unique path elements by their left end and their direction.

# Answer
> 8 votes
# Nekomata \+ `-n`, 7 bytes

```
~pᵉloÐũ

```

Attempt This Online!

A port of @Albert.Lang's Python answer.

```
~pᵉloÐũ
~           Choose any item from the input
 p          Choose a prefix
  ᵉ  Ð      A pair of
   l            Last item of the prefix and
    o           The prefix sorted
      ũ     Remove duplicate results

```

---

# Nekomata \+ `-n`, 11 bytes

```
~e:∫xᵈÐcŤ~ũ

```

Attempt This Online!

-2 bytes thanks to @Kevin Cruijssen.

```
~e:∫xᵈÐcŤ~ũ
~               Choose any item from the input
                    Each item represents a path
 e              Character code
                    So / and \ are represented by two different numbers
  :             Duplicate
                    The first copy represents the directions of the roads
   ∫            Cumsum
                    These are the y coordinates of the end points
    x           Range from 0 to length - 1 (without popping)
                    These are the x coordinates of the end points
     ᵈÐc        Group the above three results into a list
        Ť       Transpose
         ~      Choose any of the (x, y, direction) triples
          ũ     Remove duplicate results

```

`-n` counts the number of results.

# Answer
> 7 votes
# JavaScript (Node.js), 61 bytes

```
s=>s.map(c=>x/=1/c?x:c<{_:s[x+c]=s[x+c]||++n}?2:5,x=1,n=0)&&n

```

Try it online!

-2B from Arnauld

# JavaScript (ES12), 55 bytes

```
s=>s.map(c=>x/=1/c?x:c<{_:s[x+c]||=++n}?2:5,x=1,n=0)&&n

```

Attempt This Online!

# Answer
> 6 votes
# Excel (ms365), 251 bytes

Not short perse, but I tried to make it so that one could freely add more values to column A:

Formula in `B1`:

```
=LET(x,TOCOL(A:A,1),s,SEQUENCE(MAX(LEN(x))),r,REDUCE(EXPAND(0,ROWS(x),,0),s,LAMBDA(y,z,HSTACK(y,TAKE(y,,-1)+SWITCH(MID(x,z,1),"/",1,"\",-1,"")))),REDUCE(0,s,LAMBDA(y,z,LET(c,CHOOSECOLS(r,z+{0,1}),y+ROWS(UNIQUE(FILTER(c,MMULT(--ISERR(c),{1;1})=0)))))))

```

There is probably still a considerable amount of bytes to be saved.

My idea was:

* Start with an array of zero's based on the amount of rows in input;
* Iterate as much as the longest input;
* During step 2 we add 1 if character equals '/', -1 if character is '/' or we add an empty string (results in error);
* If this 2d-array is completed we can iterate each pair of columns (thus: 1 & 2, 2 & 3 etc.) to count the unique rows if no error exists;
* Do this for all pairs and we get the total amount of distance travelled.

# Answer
> 5 votes
# 05AB1E, ~~16~~ ~~14~~ 13 bytes

```
εÇDηOā)ø}€`Ùg

```

Input as a list of strings.

Port of *@alephalpha*'s Nekomata's answer, so make sure to that answer as well!
-2 bytes thanks to *@alephalpha*

Try it online or verify all test cases.

**Explanation:**

```
ε        # Map over each string of the (implicit) input-list:
 Ç       #  Convert the string to a list of codepoint integers (47 if /; 92 if \)
  D      #  Duplicate this list of 1s and -1s
   η     #  Get the prefixes of the copy
    O    #  Sum each prefix together
     ā   #  Push a list in the range [1,length] (without popping the list)
      )  #  Wrap all three lists on the stack into a list
       ø #  Zip/transpose; swapping rows/columns, to create a list of triplets
}€`      # After the map: flatten the list of lists of triplets one level down
   Ù     # Uniquify this list of triplets
    g    # Pop and push its length
         # (which is output implicitly as result)

```

# Answer
> 4 votes
# Pyth, 11 bytes

```
l{sm.e,bS<d

```

Try it online!

Uses the idea that each unique road can be identified by its angle and starting position. Given any prefix of any input element this corresponds to looking at the last character and a "path key" which is the path up to that character sorted.

### Explanation

```
l{sm.e,bS<dkdQ    # implicitly add kdQ
                  # implicitly assign Q = eval(input())
   m         Q    # map Q over lambda d
    .e      d     #   enumerated map d over lambda b, k
      ,           #     2 element list:
       b          #     value  (last char)
        S<dk      #     sorted(d[:k])  (path key)
  s               # flatten nested list
 {                # deduplicate
l                 # get the length

```

# Answer
> 3 votes
# , 20 bytes

```
[:#@~.@;(/:~,{:)\&.>

```

Try it online!

This is mostly a port of Albert Lang's excellent approach, with one twist:

* Instead of sorting the prefix and appending the last element, we can sort *everything* (including the last elm) and append the last element.
* This allows for the golfier `(/:~,{:)` to replace `(/:~@}:,{:)`.

# Answer
> 2 votes
# Retina 0.8.2, 24 bytes

```
.
$%`$&¶
%O`.(?=.)
D`
.+

```

Try it online! Takes input on separate lines but link is to test suite which accepts a list of space-separated examples for convenience. Explanation:

```
.
$%`$&¶

```

Get all of the prefixes of all of the roads.

```
%O`.(?=.)
D`

```

Remove prefixes that have the same number of each type of road, excluding the last road.

```
.+

```

Count the total unique distance.

# Answer
> 1 votes
# JavaScript (ES12), 52 bytes

*My initial answer was buggy. This fixed version takes inspiration from @l4m2 and @Albert.Lang (although the relationship with the latter one is not obvious anymore).*

Expects a list of characters.

```
a=>a.map(c=>1/c?s=1:a[c+=s*=2^c>{}]||=++n,s=1,n=0)|n

```

Attempt This Online!

### Commented

```
a =>             // a[] = input array
a.map(c =>       // for each character c in a[]:
  1 / c ?        //   if c is a space:
    s = 1        //     reset s to 1
  :              //   else:
    a[           //
      c +=       //     build a lookup key by appending to c:
        s *=     //       the updated 'signature' s of the path:
          2 ^    //         obtained by multiplying by 2 if c = '/'
          c > {} //         or by 3 if c = '\'
    ] ||= ++n,   //     increment n if this key was not yet encountered
  s = 1,         //   start with s = 1
  n = 0          //   start with n = 0
) | n            // end of map(); return n

```

# Answer
> 1 votes
# Charcoal, 25 bytes

```
ＷＳ«Ｊ⁰¦⁰Ｆι≡κ/↗¹¶\»≔ＬＫＡθ⎚Ｉθ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

```
ＷＳ«

```

Loop over the roads.

```
Ｊ⁰¦⁰

```

Start each road at Diamond City.

```
Ｆι

```

Loop over each road segment.

```
≡κ/

```

If it's a `/`, then...

```
↗¹

```

... draw a `/` and move up left, otherwise...

```
¶\

```

... move down and draw a `\`.

```
»≔ＬＫＡθ

```

Get the count of cells covered.

```
⎚Ｉθ

```

Clear the canvas and output the count.

The first 16 bytes suffice to output the map itself:

```
ＷＳ«Ｊ⁰¦⁰Ｆι≡κ/↗¹¶\

```

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

# Answer
> 0 votes
# C (gcc), 99 bytes

```
f(char*p){int a[4096]={},n=0,s=0,c;while(c=*p++)~c&4?s=0:a[s+=1<<(c&=1)*6]&++c||(a[s]|=c,n++);p=n;}

```

Try it online!

it will collide when the strings have \>= (2^6 = 64) of either direction. increase the 6 (+1) and 4096 (\*4) to make it even better, to a theoretical maximum of 16 and 4294967296 (16 GiB of RAM, max 65535 of either direction). on TIO it only works up to 10 and 1048576 (4 MiB of RAM, max 1023).

---
Tags: code-golf
---