# Question
Title: Wherre are the adjacent characters in the title? [3, 4]!
Title misspelled on purpose. Read more to find out why.

Your task: given a delimited string or list including the characters `A,B,C,D`, output the indexes of all the adjacent equal characters. Output can be multiple strings/integers on multiple lines, a list/array, or a delimited string.

All output should be in a list or string, or multiple printed lines. Each printed line, if there are multiple, should only contain 1 string or number. Trailing whatevers are okay.

Standard methods of input/output. Standard loopholes apply.

For example, the input `'ABCDDCBA'` should output `3,4` or `4,5`, depending on whether it is 0- to 1- indexed, because those numbers are the indexes of `D` and the `D` next to it.

**Test cases:**

Test cases have input given as a single string, and output as a `,`-delimited string. Outputs are 0-indexed, add 1 to every outputted item to get it to be 1-indexed.

```
Input: 'ABCDCABCD'
Output: ''

Input: 'AABBCCDD'
Output: '0,1,2,3,4,5,6,7'

Input: 'ABCDDDCBA'
Output: '3,4,5'

Input: 'ABBCDD'
Output: '1,2,4,5'

```

This is , so shortest code wins!

# Answer
# MATL, ~~8~~ 7 bytes

```
d~ftQvu

```

Output is 1-based.

Try it online!

### Explanation with example

Consider input `'ABCDDDCBA'`.

```
d     % Implicitly input a string. Consecutive differences
      % STACK: [1  1  1  0  0 -1 -1 -1]
~     % Negate. Each character that equals the next gives true
      % STACK: [0 0 0 1 1 0 0 0]
f     % Find: (1-based) indices of true elements
      % STACK: [4 5]
tQ    % Duplicate, add 1 element-wise
      % STACK: [4 5], [5 6]
v     % Concatenate vertically
      % STACK: [4 5; 5 6]
u     % Unique (remove duplicates). This doesn't automatically sort, but the
      % output will be sorted because the input, read in column-major order, is
      % Implicitly display
      % STACK: [4; 5; 6]

```
> 7 votes

# Answer
# Retina, ~~33~~ ~~29~~ 23 bytes

*Saved 6 bytes thanks to Martin Ender*

```
T`L`:`(.)\1+
:
$.`¶
T`L

```

Outputs a linefeed-separated list of indices.

Try it online!

**Explanation**

```
T`L`:`(.)\1+

```

Transliterate runs of the same character into colons, to mark positions where there are duplicate characters.

```
:
$.`¶

```

Then replace each colon with the length of the text before it, followed by a linefeed.

```
T`L

```

Finally, delete any remaining letters.
> 10 votes

# Answer
# Jelly, 7 bytes

```
JṁŒgḊÐf

```

1-based; returns a list of lists of the runs of indexes as allowed by the OP.

**Try it online!**

### How?

```
JṁŒgḊÐf - Main link: char-list s       e.g. 'DCCABBBACCCD' (which is a python interpreted input of ['D','C','C','A','B','B','B','A','C','C','C','D'])
J       - range(length(s))                  [1,2,3,4,5,6,7,8,9,10,11,12]
  Œg    - group-runs(s)                     [['D'],['C','C'],['A'],['B','B','B'],['A'],['C','C','C'],['D']]
 ṁ      - mould left like right             [[1],[2,3],[4],[5,6,7],[8],[9,10,11],[12]]
     Ðf - filter keep items that would be truthy (empty is not truthy) after applying:
    Ḋ   -     dequeue (x[1:])               [    [2,3],    [5,6,7],    [9,10,11]     ]

```
> 9 votes

# Answer
# Brain-Flak, ~~57~~ 46 bytes

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

```

Includes +2 for `-ar`

Uses 0-based indexing.

Try it online!

```
# While true
{

  # Subtract the second value on the stack from the first
  ({}[({})]

  # Push the height of this stack (the main stack) on the other stack
  <(([]<>)

  # Push the height of the main stack - 1
  [()])>

  # Push the difference that we calculated a second ago
  )

  # If they weren't the same character
  {

    # Pop the difference and the two stack heights
    (<{}{}{}>)

  # End if
  }

  # Pop the difference (or the 0 to get out of the if)
  {}

# Switch back to the main stack and end while
<>}

# Switch to the stack with the indexes and implicitly print
<>

```
> 8 votes

# Answer
# Brachylog, 19 bytes

```
l⟦k:?z{sĊtᵐ=∧Ċ∋h}ᶠd

```

Try it online!

### Explanation

Brachylog is usually terrible with indexes, which again shows here.

If `false.` is an acceptable output in cases where there are no adjacent characters, then this would be 1 byte less by replacing `ᶠd` by .

```
l⟦k                      The list [0, …, length(Input) - 1]
   :?z                   Zip the Input with this list
      {         }ᶠd      Find with no duplicates:
            ∧Ċ∋h           The heads of each element of Ċ = [A, B] (i.e. the indexes)…
        Ċtᵐ=               …where the tails of both A and B are equal (i.e. the letters)…
       sĊ                  …and where Ċ = [A, B] is a substring of the Input

```
> 7 votes

# Answer
# Brain-Flak, ~~69, 59~~, 56 bytes

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

```

Try it online!

+2 bytes for the `-ar` flags which enables ASCII input and reverses the stack.

Uses 0-based indexing. Saved 10 bytes by reducing my push-pop redundancy. Saved another 4 bytes by switching from 1 to 0-based indexing.

This is pretty much the only string based challenge that brain-flak is good at. That's because brain-flak is great at comparing consecutive characters, even though it's horrendous at string processing in general. Here is readable version of the code with comments to explain how it works:

```
#While True
{

    #Determine if top two are equal
    ({}[({})]<(())>){((<{}{}>))}{}

    #If so
    {

        #Pop the one, and negate it's value (giving us -1)
        ([{}]

        #Push stack height over
        ([]<>)

        #Then push stack height plus the negated pop (-1)
        )

        #Push a zero back onto the main stack
        (<>)

    #Endwhile
    }

    #Pop the zero
    {}

#Endwhile
}

#Toggle back, implicitly display
<>

```
> 6 votes

# Answer
## Mathematica, 32 bytes

```
Union@@StringPosition[#,x_~~x_]&

```

Pure function which returns the 1-indexed positions of characters adjacent to an identical character.

## Explanation:

`StringPosition["string","sub"]` gives a list of the starting and ending character positions at which `"sub"` appears as a substring of `"string"`. `x_~~x_` is a `StringExpression` which matches two adjacent, identical characters. For example, `StringPosition["ABCDDDCBA",x_~~x_]` gives `{{4, 5}, {5, 6}}`. Applying `Union` joins the lists, sorts, and deletes duplicates.
> 6 votes

# Answer
# Cubix, ~~37 32 31 29~~ 28 bytes

*Thanks to ETHProductions for pointing me in the direction of a three-byte saving*

```
$uO@(;Usoi?-!w>;.....S_o\;#O

```

Try it here! Note that the output indices are 1-based and not in ascending order.

### Expanded:

```
      $ u O
      @ ) ;
      U s o
i ? - ! w > ; . . . . .
S _ o \ ; # O . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

```

# Explanation

This works by reading the input character by character. To compare two characters, we simply subtract the their character codes, and if the result is 0, we print the current length of the stack, a space, the current length of the stack - 1 and another space. Then we clean up the stack a bit, and we start with the read loop again. If the end of the input string is reached, the program stops.
> 6 votes

# Answer
# Octave, 35 bytes

```
@(s)unique([x=find(~diff(+s)),x+1])

```

Try it online!

Similar to my MATL answer. Here `unique` automatically sorts . The input to `diff` must be converted to `double`, which is done by the unary `+`.
> 5 votes

# Answer
## C#, 115 bytes

---

**Golfed**

```
i=>{var o="";for(int x=1,l=i.Length;x<=l;x++)o+=(x<l&&i[x]==i[x-1])||(x>1&&i[x-1]==i[x-2])?(x-1)+" ":"";return o;};

```

---

**Ungolfed**

```
i => {
   var o = "";

   for( int x = 1, l = i.Length; x <= l; x++ )
      o += ( x < l && i[ x ] == i[ x - 1 ] ) || ( x > 1 && i[ x - 1 ] == i[ x - 2 ] )
         ? ( x - 1 ) + " "
         : "";

   return o;
};

```

---

**Ungolfed readable**

```
i => {
   // List of positions
   var o = "";

   // Cycle through the string
   for( int x = 1, l = i.Length; x <= l; x++ )
      // Check if 'x' is below the string length
      //    and if the current and previous char are the same...
      //    ... or if 'x' is beyong the string length
      //    and the 2 previous chars are the same.
      o += ( x < l && i[ x ] == i[ x - 1 ] ) || ( x > 1 && i[ x - 1 ] == i[ x - 2 ] )

         // If true, add the index to the list of positions...
         ? ( x - 1 ) + " "

         // ...otherwise add nothing
         : "";

   // Return the list of positions.
   return o;
};

```

---

**Full code**

```
using System;
using System.Collections.Generic;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
         Func<String, String> f = i => {
            // List of positions
            var o = "";

            // Cycle through the string
            for( int x = 1, l = i.Length; x <= l; x++ )
               // Check if 'x' is below the string length
               //    and if the current and previous char are the same...
               //    ... or if 'x' is beyong the string length
               //    and the 2 previous chars are the same.
               o += ( x < l && i[ x ] == i[ x - 1 ] ) || ( x > 1 && i[ x - 1 ] == i[ x - 2 ] )

                  // If true, add the index to the list of positions...
                  ? ( x - 1 ) + " "

                  // ...otherwise add nothing
                  : "";

            // Return the list of positions.
            return o;
         };

         List<String>
            testCases = new List<String>() {
               "ABCDCABCD",
               "AABBCCDD",
               "ABCDDDCBA",
               "",
               "A",
               "AA",
               "AAA",
         };

         foreach( String testCase in testCases ) {
            Console.WriteLine( $"{testCase}\n{f( testCase )}\n" );
         }

         Console.ReadLine();
      }
   }
}

```

---

**Releases**

* **v1.0** \- `115 bytes` \- Initial solution.

---

**Notes**

Nothing to add
> 5 votes

# Answer
# C, 75 bytes

```
i;f(char*s){for(i=0;*s;++s,++i)if(s[1]==*s|(i&&s[-1]==*s))printf("%d ",i);}

```

Uses spaces as delimiters. (A trailing comma doesn't look too good.)

Try it online!
> 4 votes

# Answer
# JavaScript, 52 bytes

Thanks @Neil for golfing off 1 byte

```
x=>x.map((a,i)=>a==x[++i-2]|a==x[i]&&i).filter(a=>a)

```

Receives input as a 0-indexed array of characters
Returns output as a 1-indexed array

## Explanation

```
x.map()

```

For each character in the string

```
(a,i)=>(a==x[++i-2]|a==x[i])*i

```

If it is equal to the previous character or the next character, return the index+1 otherwise do not return (leaves undefined in the array)

```
.filter(a=>a)

```

Remove all undefined elements from the resulting array

Try it online!
> 4 votes

# Answer
# Jelly, 8 bytes

```
=2\T’œ|$

```

Try it online!
> 3 votes

# Answer
# k, 18 bytes

```
{?,/-1 0+/:&:=':x}

```

Examples:

```
k){?,/-1 0+/:&:=':x}"AABCDDDCBAA"
0 1 4 5 6 9 10
k){?,/-1 0+/:&:=':x}"ABCDCBA"
()

```

Translation to `q` is easier to understand:

```
{distinct raze -1 0+/:where not differ x}

```
> 3 votes

# Answer
## QBIC, 42 bytes

```
;[2,_lA||~mid$(A,a-1,1)=mid$(A,a,1)|?a-1,a

```

Sample output:

```
Command line: AADCDBBD
 1             2
 6             7

```

Explanation:

```
;               Get A$ from the cmd line
[2,    |        FOR a% = 2 TO
   _lA|              the length of A$
~mid$(A,a-1,1)  IF the character at index a%
=mid$(A,a,1)    equals the char at index a%-1
|               THEN
?a-1,a          PRINT both indexes, tab-separated
                Any further doubles are printed on a separate line
                The IF and FOR are closed implicitly

```

---

EDIT: QBIC now has Substring! This challenge can now be solved in 32 bytes:

```
;[2,_lA||~_sA,a-1|=_sA,a||?a-1,a

```

Where:

```
_s      This is the substring function; it takes 1, 2 or 3 arguments.
        Arguments are comma-seperated, the list is delimited with |
        In this answer we see Substring take 2 arguments:
  A,    The string to take from
    a|  Starting position (note:uppercase represents strings, lowercase is for nums)
        Any omitted argument (in this case 'length to take') is set to 1.

```
> 3 votes

# Answer
# Python 2, ~~55~~ 54 bytes

```
m=j=0
for i in input():
 if m==i:print~-j,j,
 j+=1;m=i

```

Try it Online!

Outputs indices separated by spaces (note that this displays some indices twice as allowed by OP)
> 3 votes

# Answer
# C#, 89 Bytes

```
using System.Linq;s=>string.Join("",s.Skip(1).Select((a,i)=>a==s[i]?i+" "+(i+1)+" ":""));

```

If there are three or more characters in a row the indexes are repeated. Which @Comrade SparklePony allowed in the comments.

### Ungolfed full program:

```
using System;
using System.Collections.Generic;
using System.Linq;

namespace Namespace
{
    class Class1
    {
        static void Main(string[] args)
        {
            Func<string, string> f2 =
                s => string.Join("" ,         //Combine the results into one string
                s.Skip(1)                     //Start with the second element
                .Select(
                    (a, i) =>                 // 'a' is the current element, 'i' is the index of the element in the result of 'Skip'
                    a == s[i] ?               // therefore 's[i]' is the previous element; compare it with the current one
                    i + " " + (i + 1) + " " : //If true, return the indexes
                    ""                        //Otherwise an empty string
                ));

            var tests = new string [] {
               "ABCDCABCD",
               "AABBCCDD",
               "ABCDDDCBA",
               "ABBCDD"
            };

            foreach (var test in tests)
            {
                Console.WriteLine(test);
                Console.WriteLine(string.Join("", f2(test)));
                Console.WriteLine();
            }

            Console.ReadLine();
        }
    }
}

```
> 3 votes

# Answer
# Go, 116 bytes

```
func f(s string)map[int]int{L,l:=make(map[int]int),'0'
for i,r:=range s{if r==l{L[i-1]=i;L[i]=i}else{l=r}}
return L}

```

Attempt This Online!

Returns a map where the keys are the 0-based indexes of adjacent characters.

### Go, 141 bytes

```
func f(s string)(O[]int){L,l:=make(map[int]int),'0'
for i,r:=range s{if r==l{L[i-1]=i;L[i]=i}else{l=r}}
for k:=range L{O=append(O,k)}
return}

```

Attempt This Online!

Returns a slice that is the 0-based indexes of the adjacent characters.
> 3 votes

# Answer
# Perl 5, 37 bytes

35 bytes of code + `pl` flags.

```
s/(?<=(.))\1|(.)(?=\2)/print pos/ge

```

Try it online!

`(?<=(.))\1|(.)(?=\2)` will match either between two repeted characters (`(?<=(.))\1`), or before a character that is repeated (`(.)(?=\2)`).
Then, `print pos` prints the position of the match. (`pos` contains the index of the current match when used in a regex with `/g` modifier).
> 2 votes

# Answer
# PHP, 100 Bytes

```
for(;$i<strlen($s=$argn);$i++)$s[$i]==$s[$i+1]||$s[$i]==$s[$i-1]&&$i?$r[$i]=+$i:0;echo join(",",$r);

```
> 2 votes

# Answer
# Perl 6,  ~~66~~  57 bytes

```
*.comb.rotor(2=>-1).kv.flatmap({($^a,$a+1)xx[eq] $^b[0,1]}).squish

```

Try it

```
{m:ex/[(.)<($0|(.))>$0]{make $/.from}/».ast.sort.squish}

```

Try it
> 2 votes

# Answer
# Ruby, 51+1 = 52 bytes

Uses the `-n` flag.

```
i=0;d=[];gsub(/./){$&==$_[i+=1]?d+=[i-1,i]:0};p d&d

```

Try it online!
> 2 votes

# Answer
## Batch, 139 bytes

```
@set/ps=
@set/ai=c=0
:l
@if %s:~,1%==%s:~1,1% set c=2
@if %c% gtr 0 echo %i%
@set/ai+=1,c-=1
@if not "%s:~1%"=="" set s=%s:~1%&goto l

```

Takes input on STDIN. Works by keeping track of how many numbers to print in the `c` variable, which is reset to 2 when a pair is detected. Note: At a cost of 6 bytes, could be hardened to work with most ASCII characters and not just `ABCD`.
> 2 votes

# Answer
# k, 14 bytes

This is a function, it takes in a string, and returns a list of indices.

```
&{x|1_x,0}@=':

```

Explanation:

```
           =': /compare each letter to the previous, return binary list
 {       }@
    1_x,0      /shift left
  x|           /combine shifted and unshifted with binary or
&              /get indices of 1s

```

Try it online!

How to use:

```
&{x|1_x,0}@=':"STRINGGOESHERE"

```
> 2 votes

# Answer
# Julia 1.3, 23 bytes

```
!x=findall(r"(.)\1+",x)

```

Attempt This Online!

in Julia 1.3+, there is a function that does the job for me. The output is a list of ranges, which are equivalent to lists (`4:6 == [4,5,6]`)

+6 bytes if this format is not accepted
> 2 votes

# Answer
# Japt, 10 bytes

Input as a character array, output as a 2D array.

```
ò¦ m£T°ÃlÉ

```

Try it

```
ò¦ m£T°ÃlÉ     :Implicit input of array U
ò              :Partition on
 ¦             :  Inequality
   m           :Map
    £          :  Map
     T°        :    Postfix increment T, initially 0
       Ã       :End map
        l      :Filter by length
         É     :  Minus 1 (0 is falsey)

```
> 2 votes

# Answer
# PHP, 70 bytes

```
for(;a&$c=$argn[$i];)$i++&&$argn[$i-2]==$c||$argn[$i]==$c?print$i._:0;

```

takes input from STDIN; run with `-R`.
> 1 votes

# Answer
# JavaScript (V8), 64 bytes

```
x=>x.replace(/(.)\1+/g,f=(s,i,p)=>print(p)+s[i=-~i]&&f(s,i,1+p))

```

Try it online!

Not that short but fun

# JavaScript (Node.js), 45 bytes "by" fəˈnɛtɪk

```
x=>x.flatMap((a,i)=>a==x[++i-2]|a==x[i]?i:[])

```

Try it online!
> 1 votes

# Answer
# \>\<\>, ~~48~~ 47 bytes

```
0ril3(?;3[$::}@=r$:@e1.
=r{+]?\{1+}20.
}oan:{/1

```

Try it online!
> 1 votes

# Answer
# Vyxal, 6 bytes

```
₌ẏĠ•~Ḣ

```

Try it Online!

Similar stuff to the other answers but independently derived.

## Explained

```
₌ẏĠ•~Ḣ
₌ẏĠ    # range(0, len(input)) and group_consecutive(input)
   •   # mold the length range to the shape of the consecutive groups
    ~Ḣ # keep only lists where there's more than one item

```
> 0 votes

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


title: Toggle some bits and get a square

text:
# Question
Title: Toggle some bits and get a square
Given an integer \\$N\>3\\$, you have to find the minimum number of bits that need to be inverted in \\$N\\$ to turn it into a square number. You are only allowed to invert bits **below the most significant one**.

## Examples

* \\$N=4\\$ already is a square number (\\$2^2\\$), so the expected output is \\$0\\$.
* \\$N=24\\$ can be turned into a square number by inverting 1 bit: \\$11000 \rightarrow 1100\color{red}1\\$ (\\$25=5^2\\$), so the expected output is \\$1\\$.
* \\$N=22\\$ cannot be turned into a square number by inverting a single bit (the possible results being \\$23\\$, \\$20\\$, \\$18\\$ and \\$30\\$) but it can be done by inverting 2 bits: \\$10110 \rightarrow 10\color{red}0\color{red}00\\$ (\\$16=4^2\\$), so the expected output is \\$2\\$.

## Rules

* It is fine if your code is too slow or throws an error for the bigger test-cases, but it should at least support \\$3 \< N \< 10000\\$ in less than 1 minute.
* This is !

## Test cases

```
    Input | Output
----------+--------
        4 | 0
       22 | 2
       24 | 1
       30 | 3
       94 | 4
      831 | 5
      832 | 1
     1055 | 4
     6495 | 6
     9999 | 4
    40063 | 6
   247614 | 7        (smallest N for which the answer is 7)
  1049310 | 7        (clear them all!)
  7361278 | 8        (smallest N for which the answer is 8)
100048606 | 8        (a bigger "8")

```

Or in copy/paste friendly format:

```
[4,22,24,30,94,831,832,1055,6495,9999,40063,247614,1049310,7361278,100048606]

```

# Answer
## Ruby, 74 bytes

```
->n{(1..n).map{|x|a=(n^x*x).to_s 2;a.size>Math.log2(n)?n:a.count(?1)}.min}

```

Try it online!

This simply generates the sequence \\$\left\[1^2, 2^2, \ldots, n^2\right\]\\$ (which is far more than enough), XORs it with \\$n\\$, and then takes either the number of 1s in its binary representation if the number of bits is less than or equal to \\$\log\_2n\\$, or \\$n\\$ otherwise. It then takes the minimum number of bits flipped. Returning \\$n\\$ instead of the number of bits flipped when the highest bit flipped is greater than \\$\log\_2n\\$ prevents these cases from being chosen as the minimum, as \\$n\\$ will always be greater than the number of bits it has.

Thanks to Piccolo for saving a byte.
> 14 votes

# Answer
# Jelly, 12 bytes

```
²,BẈEðƇ²^B§Ṃ

```

Try it online!

Check out a test suite!

Monadic link. Should be golfable. ~~But I am too dumb to think of a way to get rid of the `³`s.~~ It's my first answer in which I successfully use filtering / mapping / looping in general along with a dyadic chain \o/

### Explanation

```
²,BẈEðƇ²^B§Ṃ – Full program / Monadic link. Call the argument N.
     ðƇ      – Filter-keep [1 ... N] with the following dyadic chain:
²,BẈE        – The square of the current item has the same bit length as N.
²            – Square.
 ,           – Pair with N.
  B          – Convert both to binary.
   Ẉ         – Retrieve their lengths.
    E        – And check whether they equate.
       ²^    – After filtering, square the results and XOR them with N.
         B   – Binary representation of each.
          §  – Sum of each. Counts the number of 1s in binary.
           Ṃ – Minimum.

```
> 6 votes

# Answer
# Husk, 20 bytes

```
▼mΣfo¬→S↑(Mo¤ż≠↔ḋİ□ḋ

```

Try it online!

## Explanation

```
▼mΣf(¬→)S↑(M(¤ż≠↔ḋ)İ□ḋ) -- example input n=4
        S↑(           ) -- take n from n applied to (..)
                     ḋ  -- | convert to binary: [1,0,0]
                   İ□   -- | squares: [1,4,9,16,...]
           M(     )     -- | map with argument ([1,0,0]; example with 1)
                 ḋ      -- | | convert to binary: [1]
             ¤  ↔       -- | | reverse both arguments of: [1] [0,0,1]
              ż≠        -- | | | zip with inequality (absolute difference) keeping longer elements: [1,0,1]
                        -- | : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1],[1,0,1,1,1],....
                        -- : [[1,0,1],[0,0,0],[1,0,1,1],[0,0,1,0,1]]
    f(  )               -- filter elements where
       →                -- | last element
      ¬                 -- | is zero
                        -- : [[0,0,0]]
 mΣ                     -- sum each: [0]
▼                       -- minimum: 0

```
> 5 votes

# Answer
# Perl 6, 65 bytes

```
{min map {+$^a.base(2).comb(~1) if sqrt($a+^$_)!~~/\./},^2**.msb}

```

Try it online!

I feel a little dirty for testing for a perfect square by looking for a period in the string representation of the number's square root, but...anything to shave off bytes.
> 5 votes

# Answer
# 05AB1E, ~~20~~ ~~15~~ 14 bytes

```
Lnʒ‚b€gË}^b1öß

```

-5 bytes thanks to *@Mr.Xcoder* using a port of his Jelly answer.

Try it online or verify all test cases (the biggest four test cases are removed, because they'll timeout after 60 sec).

**Explanation:**

```
L          # Create a list in the range [1, (implicit) input-integer]
           #  i.e. input=22 → [0,1,2,...,20,21,22]
 n         # Take the square of each
           #  i.e. [0,1,2,...,20,21,22] → [0,1,4,...,400,441,484]
  ʒ     }  # Filter this list by:
   ,       #  Pair the current value with the (implicit) input-integer
           #   i.e. 0 and 22 → [0,22]
           #   i.e. 25 and 22 → [25,22]
    b      #  Convert both to binary strings
           #   i.e. [0,22] → ['0','10110']
           #   i.e. [25,22] →  ['10000','11001']
     €g    #  Take the length of both
           #   i.e. ['0','10110'] → [1,5]
           #   ['10000','11001'] → [5,5]
       Ë   #  Check if both are equal
           #   i.e. [1,5] → 0 (falsey)
           #   i.e. [5,5] → 1 (truthy)
^          # After we've filtered, Bitwise-XOR each with the (implicit) input-integer
           #  i.e. [16,25] and 22 → [6,15]
 b         # Convert each to a binary string again
           #  i.e. [6,15] → ['110','1111']
  1ö       # Convert each to base-1, which effectively is a vectorized sum of their
           # digits, to get the amount of 1-bits in each binary string
           #  i.e. ['110','1111'] → [2,4]
ß          # Pop and leave the minimum of this list
           #  i.e. [2,4] → 2
           # (which is output implicitly as result)

```
> 4 votes

# Answer
# Java (JDK 10), 110 bytes

```
n->{int i=1,s=1,b,m=99,h=n.highestOneBit(n);for(;s<h*2;s=++i*i)m=(s^n)<h&&(b=n.bitCount(s^n))<m?b:m;return m;}

```

Try it online!
> 3 votes

# Answer
# Gaia, 18 bytes

Near-port of my Jelly answer.

```
s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋

```

Try it online!

### Breakdown

```
s¦⟪,b¦l¦y⟫⁇⟪^bΣ⟫¦⌋ – Full program. Let's call the input N.
s¦                 – Square each integer in the range [1 ... N].
  ⟪      ⟫⁇        – Select those that fulfil a certain condition, when ran through
                     a dyadic block. Using a dyadic block saves one byte because the
                     input, N, is implicitly used as another argument.
   ,               – Pair the current element and N in a list.
    b¦             – Convert them to binary.
      l¦           – Get their lengths.
        y          – Then check whether they are equal.
           ⟪   ⟫¦  – Run all the valid integers through a dyadic block.
            ^      – XOR each with N.
             bΣ    – Convert to binary and sum (count the 1s in binary)
                 ⌋ – Minimum.

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 67 bytes

```
Min@DigitCount[l=BitLength;#~BitXor~Pick[s=Range@#^2,l@s,l@#],2,1]&

```

Try it online!

Takes \\$\\{1, 2, \ldots, n\\}\\$ and squares them. Then, the numbers with same `BitLength` as the input are `Pick`ed, and `BitXor`ed with the input. Next, the `Min`imum `DigitCount` of `1`s in binary is returned.
> 2 votes

# Answer
# Brachylog, 56 41 bytes

It's not gonna break any length records but thought i'd post it anyway

```
⟨⟨{⟦^₂ᵐḃᵐ}{h∋Q.l~t?∧}ᶠ{ḃl}⟩zḃᶠ⟩{z{∋≠}ᶜ}ᵐ⌋

```

Try it online!
> 2 votes

# Answer
# x86-64 assembly, 37 bytes

Bytecode:

```
53 89 fb 89 f9 0f bd f7 89 c8 f7 e0 70 12 0f bd
d0 39 f2 75 0b 31 f8 f3 0f b8 c0 39 d8 0f 42 d8
e2 e6 93 5b c3

```

Nicely, this computes even the highest example in less than a second.

Heart of the algorithm is xor/popcount as usual.

```
    push %rbx
    /* we use ebx as our global accumulator, to see what the lowest bit
     * difference is */
    /* it needs to be initialized to something big enough, fortunately the
     * answer will always be less than the initial argument */
    mov %edi,%ebx
    mov %edi,%ecx
    bsr %edi,%esi
.L1:
    mov %ecx,%eax
    mul %eax
    jo cont     /* this square doesn't even fit into eax */
    bsr %eax,%edx
    cmp %esi,%edx
    jnz cont    /* can't invert bits higher than esi */
    xor %edi,%eax
    popcnt %eax,%eax
    cmp %ebx,%eax   /* if eax < ebx */
    cmovb %eax,%ebx
cont:
    loop .L1
    xchg %ebx,%eax
    pop %rbx
    retq

```
> 2 votes

# Answer
# PARI/GP 136 bytes

```
t(n)=b=#digits(n\2,2);for(j=0,b,v=concat(vector(b-j),vector(j,i,1));forperm(v,p,if(issquare(bitxor(n,fromdigits(Vec(p),2))),return(j))))

```

## Test

```
T=[4, 22, 24, 30, 94, 831, 832, 1055, 6495, 9999, 40063, 247614, 1049310, 7361278, 100048606];
for (i=1, #T, print(T[i]," | "t(T[i])))
4 | 0
22 | 2
24 | 1
30 | 3
94 | 4
831 | 5
832 | 1
1055 | 4
6495 | 6
9999 | 4
40063 | 6
247614 | 7
1049310 | 7
7361278 | 8
100048606 | 8
> ##
***   last result computed in 736 ms.

Test with OEIS A358701(9):
t(743300286)
9
##
last result computed in 3,813 ms.

```
> 2 votes

# Answer
# Charcoal, 31 bytes

```
ＮθＩ⌊ＥΦＥθ↨×ιι²⁼ＬιＬ↨θ²ΣＥ↨θ²¬⁼λ§ιμ

```

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

```
Ｎθ                              Input N
       θ                        N
      Ｅ                         Map over implicit range
          ιι                    Current value (twice)
         ×                      Multiply
        ↨   ²                   Convert to base 2
     Φ                          Filter over result
               ι                Current value
                  θ             N
                 ↨ ²            Convert to base 2
              Ｌ Ｌ               Length
             ⁼                  Equals
    Ｅ                           Map over result
                       θ        N
                      ↨ ²       Convert to base 2
                     Ｅ          Map over digits
                           λ    Current base 2 digit of N
                             ι  Current base 2 value
                              μ Inner index
                            §   Get digit of value
                          ⁼     Equals
                         ¬      Not (i.e. XOR)
                    Σ           Take the sum
   ⌊                            Take the minimum
  Ｉ                             Cast to string
                                Implicitly print

```
> 1 votes

# Answer
# Jelly, 20 bytes

```
BL’Ø.ṗŻ€©Ḅ^⁸Æ²a§ɼ¹ƇṂ

```

Try it online!
> 1 votes

# Answer
# Python 2, 82 bytes

```
lambda n:min(bin(i*i^n).count('1')for i in range(n)if len(bin(i*i^n))<len(bin(n)))

```

Try it online!
> 1 votes

# Answer
# Japt `-g`, 20 bytes

*This can be golfed down.*

```
op f_¤Ê¥¢lÃ®^U ¤¬xÃn

```

Try it online!
> 1 votes

# Answer
# C (gcc),  ~~93~~  91 bytes

```
g(n){n=n?n%2+g(n/2):0;}m;i;d;f(n){m=99;for(i=0;++i*i<2*n;m=g(d=i*i^n)<m&d<n/2?g(d):m);n=m;}

```

Try it online!

---

Edit: I think my original solution (Try it online!) is not valid, because one of the variables, `m`, global to save a few bytes by not specifying type, was initialized outside of `f(n)` and therefore had to be reinitialized between calls

---

# Ungolfed and commented code :

```
g(n){n=n?n%2+g(n/2):0;} // returns the number of bits equal to 1 in n
m; //miminum hamming distance between n and a square
i; //counter to browse squares
d; //bitwise difference between n and a square
f(n){m=99; //initialize m to 99 > size of int (in bits)
    for(
        i=0;
        ++i*i<2*n; //get the next square number, stop if it's greater than 2*n
        g(d=i*i^n)<m&&d<n/2&&(m=g(d)) //calculate d and hamming distance
//      ^~~~~~~~~~~^ if the hamming distance is less than the minimum
//                    ^~~~^ and the most significant bit of n did not change (the most significant bit contains at least half the value)
//                           ^~~~~~~^ then update m
       );
    n=m;} // output m

```

---

# Edits:

* Saved 2 bytes thanks to ceilingcat
> 1 votes

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

```
x=>g=(i=z=x)=>i?g(i-1,t=i*i^x,u=(N=i=>i&&i%2+N(i>>1))(t),z=z<u|t>x&i*i>x?z:u):z

```

Try it online!

If `t` and `t^x` are both larger than `x` then `t` is longer than `x`
> 1 votes

---
Tags: code-golf, integer, bitwise
---


title: Is it a valid slash draw?

text:
# Question
Title: Is it a valid slash draw?
Given a rectangle input with only `\`, `/` and space, decide if it's a valid output of Drawing in Slashes

Empty lines and columns at edge get cleaned up, so the 3rd true case is true.

True cases:

```
 /\/\
/ /\ \
\/ /  \
/\/ /\ \
\  /  \/
 \ \
  \ \
   \/

   /\/\
  / /\ \
 /  \ \/
/ /\ \/\
\/  \  /
    / /
   / /
   \/

/\
\/
      /\
      \/

```

False cases:

```
 /\
/  \
\ \/
 \/

 /\
/  \
\  \
 \/

/\
\/
     /\
     \/

```

Shortest code in each language wins.

# Answer
> 0 votes
# Charcoal, 62 bytes

```
ＷＳ⊞υι≔Ｅ/\ΣＥυ⁺μ⌕Ａλιθ∧∧⬤υ¬﹪⁺№ι/№ι\²⬤Ｅ⌊υＥυ§λκ¬﹪⁺№ι/№ι\²⬤⊟θ⌊﹪⁺ι⌊θ²

```

Attempt This Online! Link is to verbose version of code. Takes input as a rectangular list of newline-terminated strings. Not actually sure this works in general, but posting anyway just in case.

---
Tags: code-golf, ascii-art
---


title: CGAC2022 Day 7: Fen The Wicked

text:
# Question
Title: CGAC2022 Day 7: Fen The Wicked
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Fen is a magician Elf. He can cast spells on an array of numbers to produce another number or array of numbers.

One of his inventions is the Wick spell. He loves to use this spell because "once this spell is applied, a combination of `prefix sum` spells and `change number` spells becomes magically cheaper".

## Task

Implement Fen's Wick spell.

* Given an array of positive integers `A` of length `n`,
* Replace each item at 1-based index `i` with the sum of last `j` elements, where `j == 2 ** (trailing zeros of i in binary)`.

For example, if the given array is `A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1]`,

```
Wick(A) = [
    1,      # 1
    3,      # 1+2
    3,      #     3
    10,     # 1+2+3+4
    5,      #         5
    11,     #         5+6
    7,      #             7
    36,     # 1+2+3+4+5+6+7+8
    9,      #                 9
    10,     #                 9+1
]

```

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
[] -> []
[999] -> [999]
[3,1,4] -> [3,4,4]
[3,1,4,1,5,9,2,6] -> [3,4,4,9,5,14,2,31]

```

# Answer
# Python 3.8, 45 bytes

```
lambda l,i=0:[sum(l[i&(i:=i+1):i])for _ in l]

```

Try it online!

The start index for the sum at one-indexed position `i` is `i&i-1`, which is obtained from the binary representation of `i` by setting the rightmost 1 bit to 0.
> 11 votes

# Answer
# Python NumPy, 42 bytes

```
def f(a):b=a[1::2];b+=a[:-1:2];b@b>0!=f(b)

```

Attempt This Online!

### Python NumPy, 44 bytes

```
def f(a):a[1::2]+=a[:-1:2];a@a>0!=f(a[1::2])

```

Attempt This Online!

Takes a NumPy array and modifies it in-place.

### How?

Simple recursion best explained by example:

```
a1
   a2
      a3
         a4
            a5
               a6
                  a7
                     a8
                        a9

    ==>

a1
a1+a2
      a3
      a3+a4
            a5
            a5+a6
                  a7
                  a7+a8
                        a9

   ==>

a1
a1+a2
      a3
a1+a2+a3+a4
            a5
            a5+a6
                  a7
            a5+a6+a7+a8
                        a9

   ==>

a1
a1+a2
      a3
a1+a2+a3+a4
            a5
            a5+a6
                  a7
a1+a2+a3+a4+a5+a6+a7+a8
                        a9

```
> 6 votes

# Answer
# Rust, 64 bytes

```
|x:&[_]|(0..x.len()).map(|i|x[i&i+1..=i].iter().sum()).collect()

```

Attempt This Online!

Uses XNOR's trick. Also uses blatant abuse of type annotations outside the code.
> 5 votes

# Answer
# Charcoal, 12 bytes

```
ＩＥθΣ✂θ＆κ⊕κ⊕κ

```

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

```
  θ             Input array
 Ｅ              Map over elements
     θ          Input array
    ✂           Sliced from
       κ        Current index
      ＆         Bitwise And
         κ      Current index
        ⊕       Incremented
           κ    To current index
          ⊕     Incremented
   Σ            Take the sum
Ｉ               Cast to string
                Implicitly print

```

Due to Charcoal being 0-indexed, the length of the slice is `(k+1&-(k+1))` and the start position is therefore `k+1-(k+1&-(k+1))`. However `-(k+1)` is the same as `~k` so that simplifies to `k+1-(k+1&~k)`. Writing `k+1` as `(k+1&k)|(k+1&~k)` (which have no bits in common) we see that the `k+1&~k`s cancel, leaving `k+1&k`, at which point this degenerates into a port of @xnor's Python answer.
> 4 votes

# Answer
# Pip `-p`, ~~34~~ ~~27~~ ~~22~~ 18 bytes

```
$+g@(_BA_+1\,_)MEg

```

Try It Online!

Port of @xnor's answer. Started with a port of my own python answer, but @xnor's was much shorter

~~-7~~ -12 bytes thanks to @AidenChow and @DLosc
-4 bytes thanks to @DLosc
> 4 votes

# Answer
# Vyxal, ~~13~~ 7 bytes

```
ẏD›⋏ṡİṠ

```

Try it Online!

Half porting python. TIL  vectorises zip-wise between two lists.

## Explained

```
ẏD›⋏ṡİṠ
ẏ       # The range [0, len(input))
 D      # pushed three times to the stack
  ›     # increment the top copy
   ⋏    # and get the bitwise-and of each pair of n and n-1 in each list
# At this point the stack is: [[0, 1, 2, ..., len(input) - 1], [1 bitand 0, 2 bitand 3, 3 bitand 4, ..., len(input) bitand len(input - 1)]
    ṡ   # create the range [x, y] for each x and y pair in the top two stack items: [[0], [1, 0], [2], [3, 2, 1, 0], ...]
     İ  # get the nth item in the input at each atomic index in the above list: [[input[0]], [input[1], input[0]], ...]
      Ṡ # sum each sublist and implicitly print

```
> 4 votes

# Answer
# Python, 82 bytes

```
lambda A:[sum(A[i-2**len(bin(i)[2:].split("1")[-1]):i])for i in range(1,len(A)+1)]

```

Attempt This Online!
> 3 votes

# Answer
# JavaScript (ES6), 48 bytes

Isolates the least significant non-zero bit of the 1-based index and uses it as a counter to recursively add previous values to the current one.

```
a=>a.map((_,i)=>(g=j=>j&&a[--i]+g(j-1))(++i&-i))

```

Try it online!

---

# JavaScript (ES6), 47 bytes

Porting xnor's approach is 1 byte shorter.

```
a=>a.map((_,i)=>eval(a.slice(i&++i,i).join`+`))

```

Try it online!
> 3 votes

# Answer
# PARI/GP, 41 bytes

```
a->a*matrix(#a,,j,i,i-j<gcd(i,2^i)&&j<=i)

```

Attempt This Online!

---

# PARI/GP, 42 bytes

```
a->a*matrix(#a,,j,i,j>bitand(i,i-1)&&j<=i)

```

Attempt This Online!

A port of @xnor's Python answer.
> 3 votes

# Answer
# Excel (ms365), 119 bytes

Formula in `B1`:

```
=IFERROR(MAP(SEQUENCE(COUNT(A:A)),LAMBDA(z,SUM(OFFSET(A1,z-1,,-BIN2DEC(TEXTAFTER(0&BASE(z,2),1,-2,,,BASE(z,2))))))),"")

```

I've no doubt this can be further shortened.
> 3 votes

# Answer
# Desmos, 95 bytes

```
f(l)=[l[i-2^{[0...i][mod(floor(i/2^{[0...i]}),2)=1].min}+1...i].totalfori=[0...l.length][2...]]

```

Try It On Desmos!

Try It On Desmos! - Prettified

Desmos doesn't have any binary functionalities like converting to binary or bitwise anding, so basically around half the code is dedicated to converting to binary and finding the number of trailing zeroes.

Also, in case you were wondering, I can't simply do `[1...l.length]` instead of `[0...l.length][2...]` because `f([])` (empty list input) gives an error for `[1...l.length]`: "Ranges must be arithmetic sequences."
> 2 votes

# Answer
# 05AB1E, ~~9~~ 8 bytes

```
āεN&NŸèO

```

Try it online or verify all test cases.

**Explanation:**

```
ā         # Push a list in the range [1, (implicit) input-length]
 ε        # Map over each of these 1-based indices `y`:
  N       #  Push the 0-based map index `N`
   &      #  Bitwise-AND the 1-based index `y` and 0-based index `N` together
    NŸ    #  Pop and push a list in the range [y&N,N]
      è   #  Index each into the (implicit) input-list
       O  #  Sum this list together
          # (after which the list is output implicitly as result)

```
> 2 votes

# Answer
# Nibbles, 7.5 bytes (15 nibbles)

```
.,,$+>`&-$~$<$@

```

```
.,,$+>`&-$~$<$@
.                   # map over each i in
 ,                  # range from 1..
  ,                 # length of
   $                # input,
    +               #   get the sum of:
     >              #     drop the first j elements, where j is
      `&            #       bitwise AND of
        -$~         #         i-1 and
           $        #         i,
            <$      #     from the first i elements of
              @     #     input

```
> 2 votes

# Answer
# C (clang), 49 bytes

```
i;f(*a,n){for(;n;)for(i=n&--n;i<n;)a[n]+=a[i++];}

```

Try it online!

*Uses xnor's idea from his Python answer*

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Returns the Fen Wicked array through the input pointer.
> 2 votes

# Answer
# Python, ~~84~~ ~~83~~ 77 bytes

There's probably room for improvement here. Takes both the array and the length of the array, and returns a map.

```
lambda a,n:[sum(a[u-2**len(bin(u+1).split("1")[-1])+1:u+1])for u in range(n)]

```

Attempt This Online!
> 2 votes

# Answer
# Java 8, 89 bytes

```
a->{int l=a.length,r[]=new int[l],i;for(;l-->0;)for(i=l&l+1;i<=l;)r[l]+=a[i++];return r;}

```

Try it online.

**Explanation:**

```
a->{                  // Method with integer-array as both parameter and return-type
  int l=a.length,     //  Length of the input-array
      r[]=new int[l], //  Result-array, starting with this length amount of 0s
      i;              //  Index-integer, uninitialized
  for(;l-->0;)        //  Loop `l` in the range (length,0]:
    for(i=l&l+1;      //   Set `i` to `l` bitwise-AND-ed by `l+1`
        i<=l;)        //   Inner loop `i` in the range [i&i+1,l]:
      r[l]+=          //    Add to the `l`'th value of the result-array:
        a[i++];       //     The `i`'th value of the input-array
  return r;}          //  After the nested loop, return the resulting array

```
> 1 votes

# Answer
# Factor, 90 bytes

```
[ dup length [0,b) [ dup dup 1 + bitand swap 1 + rot [ <slice> ] keep swap sum ] map nip ]

```

Attempt This Online!
> 1 votes

# Answer
# Japt, 9 bytes

```
£sY°&YY x

```

Try it
> 1 votes

# Answer
# Ruby, 35 bytes

Port of xnor's approach via Arnauld's.

```
->a{i=0
a.map{eval a[i&i+=1,i]*?+}}

```

Attempt This Online!
> 1 votes

# Answer
# x86-64 machine code, 23 bytes

```
31 C9 8B 04 8F 89 CA FF C1 09 CA 39 F2 73 03 01 04 97 39 F1 72 EC C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and its length in ESI, and modifies the array in place.

---

Go through each position in ascending order, and add its value to the value at the position that should immediately contain it, if that position exists within the array's bounds.

```
―――――――7
   ↑ ↑↑
―――3 ||
 ↑↑  ||
―1| ―5| ―9
↑ | ↑ | ↑
0 2 4 6 8

```

With 0-indexing, if the current position is `n`, the containing position is `n OR n+1`.

---

Assembly:

```
f:  xor ecx, ecx            # Set ECX to 0.
r:  mov eax, [rdi + 4*rcx]  # Load the value at index ECX into EAX.
    mov edx, ecx            # Set EDX to the value of ECX.
    inc ecx                 # Increase the value of ECX by 1.
    or edx, ecx             # Set EDX to its bitwise OR with ECX.
    cmp edx, esi            # Compare that value to the the length.
    jae s                   # Jump if it's greater than or equal to the length.
    add [rdi + 4*rdx], eax  # (If it's less) Add EAX to the value at index EDX.
s:  cmp ecx, esi            # Compare ECX to the length.
    jb r                    # Jump back, to repeat, if it's lesser.
    ret                     # Return.

```
> 1 votes

# Answer
# Halfwit, 38 bytes

```
>[<?(>M<+;M>M<N+JM>{<b(n};W;R*;(n};W>{<b:Nn+(:n+?i$;_WR+

```

Try It Online!

Why did I create this language again? Doesn't help that several builtins that would've been useful for this are buggy or just unimplemented.

Uses xnor's trick.

```
== range generation ==
>[<?(>M<+; # Get the length of the input (oof)
>[<        # Push 0
   ?(    ; # Over every item of the input...
     >M<+  # Increment

== The binary bit ==
M>M<N+JM>{<b(n};W;R*;(n};W>{<b # For each index, calculate i & i-1
M                              # Over each integer from the previous...
 >M<N+                         # Decrement
      J                        # Pair with the decremented version
       M         ;             # Over each...
           b                   # Convert to base...
        >{<                    # 2
            (  ;               # Over each binary digit
             n}                # Push it to the bottom of the stack
                W              # Get all elements of the stack i.e. the reversed binary representation
                  R*;          # Reduce by multiplication i.e. & for single bits
                     (n};W     # Reverse again (see above)
                          >{<b # Convert back from binary

== Index into input and sum ==
:Nn+(:n+?i$;_WR+ # For each number from i&i-1 to i, get that index in the input, and sum
:Nn              # Make the stack [i&i-1,i&i-1,-(i&i-1), i]
   +             # i - (i&i-1)
    (      ;     # That many times...
     :           # Duplicate the i&i-1 kept on top of the stack.
      n+         # Add that to the current index
        ?i       # Index into the input
          $      # Push under the i&i-1
            _W   # Pop the i&i-1 and wrap the stack
              R+ # Sum

```
> 1 votes

# Answer
# Ohm v2, 13 bytes

```
l@€^à^G€³s®;Σ

```

Try it online!

Simple port of 05AB1E for the hats :p

## Explained

```
l@€^à^G€³s®;Σ
l@             # the range [1, len(input)]
  €----------  # to each number:
   ^à          #   bit-and with number - 1
     ^G        #   the range [number, ^]
       €---;   #   to each:
        ³s®    #     input[^]
            Σ  #   sum

```
> 1 votes

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

```
a=>a.map((_,i)=>(g=j=>j&~i?0:a[j]+g(j-1))(i))

```

Try it online!
> 1 votes

# Answer
# Jelly, 9 bytes

```
J&’‘rƲị⁸§

```

A monadic Link that accepts a list of positive integers and yields another.

**Try it online!**

### How?

Much like many others, uses the same bitwise trick that xnor used.

```
J&’‘rƲị⁸§ - Link: list of positive integers, A
J         - range of length (A) -> [1..length(A)]
     Ʋ    - last four links as a monad - f(X=that):
  ’       -   decrement (X)
 &        -   (X) bitwise AND (that)
   ‘      -   increment (that)
    r     -   inclusive range -> [[startIndexForSum, endIndexForSum] for each element]
       ⁸  - chain's left argument -> A
      ị   - (ranges) index into (A)
        § - sums

```
> 0 votes

# Answer
# Pyth, 11 bytes

```
.es:Q.&hkkh

```

Try it online!

Uses xnor's trick.

### Explanation

```
.es:Q.&hkkhkQ    # implicit k and Q added
                 # Q = eval(input()) implicitly
.e          Q    # enumerate k over the indices of Q
  s              # sum of
   :Q            # index Q from
     .&hkk       # k & (k+1)
          hk     # to k+1

```
> 0 votes

---
Tags: code-golf, array, data-structures
---


title: Triangular polkadot numbers

text:
# Question
Title: Triangular polkadot numbers
From the infinite triangular array of positive integers, suppose we select every 2nd numbers on every 2nd row as shown below:

$$ \underline{1} \\ \\;2\\; \quad \\;3\\; \\ \\;\underline{4}\\; \quad \\;5\\; \quad \\;\underline{6}\\; \\ \\;7\\; \quad \\;8\\; \quad \\;9\\; \quad 10 \\ \underline{11} \quad 12 \quad \underline{13} \quad 14 \quad \underline{15} \\ 16 \quad 17 \quad 18 \quad 19 \quad 20 \quad 21 \\ \underline{22} \quad 23 \quad \underline{24} \quad 25 \quad \underline{26} \quad 27 \quad \underline{28} \\ \cdots $$

The resulting sequence (A185868) is as follows:

```
1, 4, 6, 11, 13, 15, 22, 24, 26, 28, 37, 39, 41, 43, 45, 56, 58, 60, 62, 64, 66,
79, 81, 83, 85, 87, 89, 91, 106, 108, 110, 112, 114, 116, 118, 120, 137, ...

```

The task is to output this sequence.

I/O rules apply. You can choose to implement one of the following:

* Given the index \\$n\\$ (0- or 1-based), output the \\$n\\$th term of the sequence.
* Given a positive integer \\$n\\$, output the first \\$n\\$ terms of the sequence.
* Take no input and output the entire sequence by
    + printing infinitely or
    + returning a lazy list or a generator.

Standard rules apply. The shortest code in bytes wins.

# Answer
# Python, 35 bytes (@att)

```
lambda n:int((2*n)**.5-.5)**2+2*n-1

```

Attempt This Online!

### Python, 39 bytes

```
lambda n:(int((8*n)**.5-1)//2)**2+2*n-1

```

Attempt This Online!

Given the 1-based index computes a single value.
> 13 votes

# Answer
# Python 2, 47 bytes

Outputs the sequence indefinitely.

```
n=x=1
while 1:exec'2;print x;x+='*n+'n-~n';n+=1

```

Try it online!
> 10 votes

# Answer
# Haskell, 34 bytes

```
[2*n^2-3*n+2*k|n<-[1..],k<-[1..n]]

```

Attempt This Online!
> 6 votes

# Answer
# Jelly,  ~~9~~  8 bytes

```
Ḷ²’xRĖḄḣ

```

A monadic Link that accepts a positive integer, \\$n\\$, and yields a list of the first \\$n\\$ odd-odd triangular polka dot numbers.

**Try it online!**

### How?

Calculates the first \\$T(n)=\frac{n(n+1)}{2}\\$ terms, and outputs the first \\$n\\$.

```
Ḷ²’xRĖḄḣ - Link: integer, n     e.g. 5
Ḷ        - lowered range (n)         [    0,    1,    2,    3,    4]
 ²       - square (vectorises)       [    0,    1,    4,    9,   16]
  ’      - decrement                 [   -1,    0,    3,    8,   15]
    R    - range (n)                 [    1,    2,    3,    4,    5]
   x     - repeat elements           [   -1,    0,    0,    3,    3,    3,    8,    8,    8,     8,     15,     15,     15,     15,     15]
    Ė    - enumerate                 [[1,-1],[2,0],[3,0],[4,3],[5,3],[6,3],[7,8],[8,8],[9,8],[10,8],[11,15],[12,15],[13,15],[14,15],[15,15]]
     Ḅ   - convert from base 2 (vectorises)
           ...i.e. [a,b] -> 2a+b     [    1,    4,    6,   11,   13,   15,   22,   24,   26,    28,     37,     39,     41,     43,     45]
       ḣ - head (to index n)         [    1,    4,    6,   11,   13]

```
> 5 votes

# Answer
# Vyxal, 10 bytes

```
Þ∞:ẇ2Ḟ2vḞf

```

Try it Online! Outputs (theoretically) infinitely but crashes due to hitting the recursion limit caused by a bug.

```
Þ∞         # All positive integers
   ẇ       # Cut into slices of lengths...
Þ∞:        # Positive integers
    2Ḟ     # Get every second item
      2vḞ  # Get every second item of each
         f # Flatten the final array

```
> 4 votes

# Answer
# Rust, 43 bytes

```
|n|((n+n).sqrt().round()-1.).powi(2)+n+n-1.

```

Try it online!

A slightly modified version of loopy walt's answer.
> 4 votes

# Answer
# JavaScript (V8), 40 bytes

Prints the sequence forever.

```
for(n=i=q=1;;n+=--i?2:q+(i=++q))print(n)

```

Try it online!
> 3 votes

# Answer
# sclin, 32 bytes

```
; ; tk2* ;2^2* ;3* - + flat
$W1+

```

Try it here! Returns an infinite list. This code is so weird...

For testing purposes (use `-i` flag when running locally):

```
; 50tk >A
; ; tk2* ;2^2* ;3* - + flat
$W1+

```

## Explanation

Prettified code:

```
; ; tk 2* ; 2^ 2* ; 3* - + flat
$W 1+

```

`;` means "evaluate the next line as a function."

* `$W 1+` \[1, ∞) as *n*
* `; ; tk 2*` `[[2][2 4][2 4 6][2 4 6 8]...]` as *k*\*2
    + this works because `tk` ("take") vectorizes the second argument
* `; 2^ 2* ; 3* - +` *n*^2\*2 - *n*\*3 + *k*\*2
    + this whole segment is vectorized
* `flat` flatten

It's vectorizations all the way down!

---

# sclin, 19 bytes

```
2*""Q.5^.5- I2^ +1-

```

Try it here! Port of @loopywalt/@att's answer. Takes a 1-based index, but the whole function vectorizes quite neatly too.

For testing purposes (use `-i` flag when running locally):

```
$W1+ ; 50tk >A
2*""Q.5^.5- I2^ +1-

```
> 3 votes

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

```
[ 2 * dup √ .5 - 1 /i sq + 1 - ]

```

Try it online!

Outputs the 1-indexed nth term of the sequence. Port of loopy walt's and att's Python answer.

```
word  | data stack              | comment
------+-------------------------+-----------------
      | 5                       | example input
2     | 5 2                     |
*     | 10                      |
dup   | 10 10                   |
√     | 10 3.16227766016838     | square root
.5    | 10 3.16227766016838 0.5 |
-     | 10 2.66227766016838     |
1     | 10 2.66227766016838 1   |
/i    | 10 2                    | integer divide
sq    | 10 4                    | square
+     | 14                      |
1     | 14 1                    |
-     | 13                      | output

```
> 3 votes

# Answer
# , 55 bytes

```
function(n,`?`=rbind)diffinv(rep(1:n*2+1?2,1?1:n))[n]+1

```

Try it online!

Returns the 1-based nth term.
> 2 votes

# Answer
# Raku, 31 bytes

```
[\+] flat (1,3...*)Z(2 Xxx^∞)

```

Try it online!

This is an expression for the lazy infinite sequence of numbers.

* `(1, 3 ... *)` is the infinite sequence of odd numbers.
* `xx` is the replication operator, which replicates its left-hand side a number of times given by its right-hand side.
* `X` is the cross-product metaoperator. Applied to the replication operator `xx`, it makes a new operator that replicates as a cross product.
* `^∞` is the unbounded range of increasing integers starting at zero.
* `2 Xxx ^∞` produces a list of 2 replicated each number of times from zero to infinity: `(), (2,), (2, 2), (2, 2, 2), ...`.
* `Z` zips the odd numbers with the list of increasing numbers of twos: `(1, ()), (3, (2,)), (5, (2, 2)), (7, (2, 2, 2)), ...`.
* `flat` flattens that list: `1, 3, 2, 5, 2, 2, 7, 2, 2, 2, ...`. That gives the list of differences between adjacent terms of the sequence.
* `[\+]` gives the list of partial sums of the previous sequence, which is the desired polka-dot sequence.
> 2 votes

# Answer
# , 37 bytes

```
function(x)(((8*x)^.5-1)%/%2)^2+2*x-1

```

Try it online!

An alternative to Giuseppe's R answer, here using a variant of loopy walt's approach.
> 2 votes

# Answer
# Excel, 27 bytes

```
=INT((2*A1)^.5-.5)^2+2*A1-1

```

Direct implementation of loopy walt's answer in Python except it's shorter in Excel. Given the 1-based index computes a single value. Input is in `A1`. When copying the above into Excel, it will automatically add leading zeroes to change `.5` to `0.5`.

---

This **41 byte** solution prints the first 1,048,576 terms (or however many rows you have in your version of Excel):

```
=LET(r,ROW(A:A),INT((2*r)^.5-.5)^2+2*r-1)

```
> 2 votes

# Answer
# Vyxal, 12 bytes

```
Þ∞:ɾ•y_ƛy$;f

```

Try it Online!

Outputs the sequence forever.

## Explained

```
Þ∞:ɾ•y_ƛy$;f
Þ∞:          # Push two copies of an infinite list of positive integers
   ɾ         # In the second copy of the infinite list, push range [1, n] for each item
    •        # And mold the first copy of the infinite list to the shape of the second
     y_      # uninterleave the infinite list, giving two lists: the list of every second row starting at row 0, and the list of every second row starting at row 1. Discard the list starting at row 1.
       ƛy$;f # To each row in the remaining list, uninterleave the row, and return the list of every second item starting at index 0. Then flatten the result.

```
> 1 votes

# Answer
# Charcoal, 22 bytes

```
ＮθＦθＦ⊕ι⊞υ×ιιＩＥ…υθ⊕⁺ι⊗κ

```

Try it online! Link is to verbose version of code. Outputs the first `n` terms of the sequence. Explanation: Port of @JonathanAllan's Jelly answer.

```
Ｎθ

```

Input `n`.

```
ＦθＦ⊕ι⊞υ×ιι

```

Create an array containing each of the squares `0`, `1`, `4`, `9`, ... , ... each repeated `i+1` times.

```
ＩＥ…υθ⊕⁺ι⊗κ

```

Take the first `n` elements of the array, and add to each the incremented doubled index (0-indexed).

20 bytes using the newer version of Charcoal on ATO:

```
ＮθＩＥ…ΣＥθＥ⊕ι×ιιθ⊕⁺ι⊗κ

```

Attempt This Online! Link is to verbose version of code. Outputs the first `n` terms of the sequence. Explanation:

```
Ｎθ                      Input `n` as a number
       θ                Input `n`
      Ｅ                 Map over implicit range
          ι             Current value
         ⊕              Incremented
        Ｅ               Map over implicit range
            ι           Outer value
           ×            Multiplied by
             ι          Outer value
     Σ                  Concatenated
    …                   Truncated to length
              θ         Input `n`
   Ｅ                    Map over squares
                 ι      Current square
                ⁺       Plus
                   κ    Current index
                  ⊗     Doubled
               ⊕        Incremented
  Ｉ                     Cast to string
                        Implicitly print

```
> 1 votes

# Answer
# Desmos, 31 bytes

```
f(n)=floor(\sqrt{2n}-.5)^2+2n-1

```

Literally just a port of loopy walt's python answer, go upvote that answer too!

Try It On Desmos!

Try It On Desmos! - Prettified
> 1 votes

# Answer
# 05AB1E, ~~9~~ 8 bytes

-1 byte by porting @corvus\_192's Rust answer, which is a slightly modified version of @loopyWalt's Python answer, so make sure to upvote them as well!

Given \\$n\\$, it'll output the 1-based \\$n^{th}\\$ term (**8 bytes**):

```
·Dtò<n+<

```

Try it online or verify the first 25 items.

Given no input, it'll output the infinite sequence list (**9 bytes**):

```
∞£ιнειн}˜

```

Try it online.

**Explanation:**

```
·         # Double the (implicit) input-integer
 D        # Duplicate it
  t       # Take the square-root of the copy
   ò      # Round it to the nearest integer
    <     # Decrease it by 1
     n    # Square it
      +   # Add it to the doubled input that's still on the stack
       <  # Decrease it by 1
          # (after which it is output implicitly as result)

```

```
∞         # Push a positive infinite list: [1,2,3,4,5,...]
 £        # Split it into parts of itself (since there is no input):
          #  [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15],...]
  ι       # Uninterleave it into two parts
   н      # Pop and only keep the first
    ε  }  # Map over each remaining inner list:
     ιн   #  Do the same for those
        ˜ # Flatten the list of lists
          # (after which the infinite list is output implicitly as result)

```
> 1 votes

# Answer
# C (GCC), ~~68~~ 65 bytes

*-2 bytes thanks to @Sʨɠɠan*

```
i;r;main(s){for(;i<=r||(i=0,s+=++r+ ++r);i+=2)printf("%d ",s+i);}

```

Attempt This Online!
> 1 votes

# Answer
# Vyxal, 8 bytes

```
d:√ṙ‹²+‹

```

Try it Online!

Port of 05AB1E, which is a port of Rust, so make sure to upvote those answers!
> 1 votes

# Answer
# Pip, 24 bytes

```
((RTDBa-0.5)//1)E2+DBa-1

```

Try It Online!

Port of loopy walt's Python answer, so go upvote his answer too!
> 1 votes

# Answer
# \>\<\>, 39 bytes

Prints the infinite sequence.

```
130>$:2+@$:1+@v
2$-1v!?:$oan:{<}+
~+}v>

```

Try it online!

# \>\<\>, 38 bytes

Prints the nth term 1-indexed.

```
:8*$2*1v
}(?!v1+>::*{:
+1-n>2-2,:1%-:*

```

Try it online!
> 0 votes

# Answer
# Pyt, 10 bytes

```
2*Đ√½-Ɩ²+⁻

```

Try it online!

```
              implicit input
2*            double
  Đ           duplicate on the stack
   √          take the square root of top
    ½-        subtract 1/2
      Ɩ²      cast to an integer and square
        +     add the stack
         ⁻    decrement
              implicit output

```

Port of loopy walt's Python answer

If floating-point returns are allowed, then 9 bytes is possible:

```
2*Đ√⎶⁻²+⁻

```

Try it online!

Port of corvus\_192's Rust answer
> 0 votes

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


title: Is this series of quotes valid Python?

text:
# Question
Title: Is this series of quotes valid Python?
Python string parsing has quite a few edge cases. This is a string:

```
"a"

```

Putting 2 strings immediately after each other implicitly concatenates them, so this is also a string:

```
"a""a"

```

However, if you put 3 quotes in a row, it will create a "triple quoted string" which can only be ended by another 3 quotes in a row. A triple quoted string can contain other quotes. These quotes will not end the string unless there are 3 of them. Thus this is valid:

```
"""a"a"""

```

Of course, you can combine these together, so this is a valid string:

```
"""a""""a"

```

And this:

```
"""""aaa"""""""""

```

3 quotes in a row outside a string always starts a triple quoted string, even if such a string would be invalid. There is no backtracking.

A string is *not* valid if:

1. Any `a` appears outside of a string literal (would get `SyntaxError: invalid syntax` in python) OR
2. The end of the sequence is inside a string literal (would get `SyntaxError: unterminated string literal (detected at line 1)` in python)

## Your task

Given a string containing 2 distinct characters, one representing a double quote and another representing the letter "a" <sup>(most letters except b, u, r, and f would work exactly the same, you don't need to concern yourself with that detail)</sup>, determine if it would be a valid python string, or invalid syntax.

You do not need to consider single quotes or how double and single quotes normally interact.

An array of booleans or an array of bytes would also be a valid input method. Thus some valid representations for `"a"` include `$2$`, `[0,1,0]`, or `[False, True, False]`.

This is , shortest answer wins.

## Test Cases

| Truthy | Falsy |
| --- | --- |
| `"a"` (1-1) | `"a` (1) |
| `"a""a"` (1-2-1) | `"a"a"` (1-1-1) |
| `"""a"a"""` (3-1-3) | `""a"a"""` (2-1-3) |
| `"""a""""a"` (3-4-1) | `"""a"""a"` (3-3-1) |
| `"""""aaa"""""""""` (5-9) | `"""""aaa""""""""` (5-8) |
| `""""""""""""` (12) | `""""""aaa"""""""""` (6-8) |
| `"a""a""a""a"` (1-2-2-2-1) | `""""` (4) |
| `"a"""` (1-3) | `a` |
| `""` (2) | `"""a"` (3-1) |
| `""""""` (6) | `"""""""` (7) |
| `""""""""` (8) | `a""""""` (6) |

`eval` or `exec` or `ast.literal_eval` would be valid answers, though I hope to see more creative python answers as well.

# Answer
> 11 votes
# Python, 57 bytes

```
lambda s:not re.sub(r'("""|"(?!"")).*?\1','',s)
import re

```

Attempt This Online!

# Python 3.11, 53 bytes

```
lambda s:not re.sub(r'("("")?+).*?\1','',s)
import re

```

This requires Python 3.11 which that scandalously outdated ato does not support ;-P

# Answer
> 7 votes
# Retina 0.8.2, ~~23~~ 22 bytes

```
^(?>("(?>""|)).*?\1)+$

```

Try it online! Link includes test cases. Explanation:

```
^

```

Match must start at the beginning of the string.

```
(?>...)+$

```

After each quoted segment is matched, it cannot be backtracked and reevaluated. Instead, further quoted segments must be matched until the end of the string is reached.

```
("(?>""|))

```

Three quotes must be matched if possible, otherwise one. This decision cannot be changed later.

```
.*?\1

```

Match the closing quote(s) as early as possible.

Edit: Saved 1 byte thanks to @Mukundan314.

# Answer
> 6 votes
# C (GCC), ~~132~~ ~~130~~ ~~109~~ 108 bytes

*-12 bytes thanks to @ceilingcat*

*-9 bytes thanks to @jdt*

*-1 bytes thanks to @c--*

```
#define T bcmp(s,"\"\"\"",n)
n;g(char*s){for(n=3;~n;n-=2)if(!T){for(s+=n;T**s;s++);return*s&&g(s+n);}n=!*s;}

```

Try it online!

Note: 3 bytes can be shaved by changing the quote char.

# Answer
> 5 votes
# Jelly, 25 bytes (no built-in); 2 bytes (built-in)

### Built-in

The two-byte built-in `ŒV` (evaluate Python code) works as a full program when given the raw input enclosed in `'''` \- the exit code identifies the result: \\$0\\$ if valid, \\$1\\$ if not.

Aside: The zero-byte program, when given the raw input, will actually give the evaluated string if valid, or the input if not. However, this does not conform with defaults.

### Non built-in

```
Ạ3ƤḢḤ‘ɓẠ⁹ƤḢ×TƊḟḶ}+Ḣ
ḊÇ¡ÐL

```

A monadic Link that accepts a list of \\$1\\$s (`"`s) and \\$0\\$s (`a`s) and yields an empty list (falsey) if valid or a non-empty list (truthy) if not.

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

### How?

```
Ạ3ƤḢḤ‘ɓẠ⁹ƤḢ×TƊḟḶ}+Ḣ - Helper Link, prefix length that may be removed: list of 1s and 0s, L
 3Ƥ                 - for overlapping infixes of length 3:
Ạ                   -   all?
   Ḣ                - head -> 1 if L starts with three 1s, 0 otherwise
    Ḥ               - double
     ‘              - increment -> 3 if L starts with three 1s, 1 otherwise
      ɓ             - new dyadic Link - f(L, Y=that)
        ⁹Ƥ          - for overlapping infixes of length Y:
       Ạ            -   all?
             Ɗ      - last three links as a monad - f(Z=that):
          Ḣ         -   head (alters Z) and yield
            T       -   truthy indices (of the altered Z)
           ×        -   multiply (vectorises)
               Ḷ}   - lowered range (Y) -> [0] or [0,1,2])
              ḟ     - filter discard (these invalid locations)
                 +  - add Y (vectorises)
                  Ḣ - head (the empty list yields 0)

ḊÇ¡ÐL - Main Link: list of 1s and 0s, L
   ÐL - repeat while results are distinct applying:
  ¡   -   repeat...
 Ç    -   ...number of times: call the helper Link - f(current L)
Ḋ     -   ...action: dequeue

```

# Answer
> 4 votes
# Charcoal, 59 bytes

```
Ｗθ≔⎇⌕θ"""∧∧¬⌕θ"⊖№θ"✂θ⊕§⌕Ａθ"¹Ｌθ¹∧⊖№θ"""✂θ⁺⁶⌕✂θ³Ｌθ¹"""Ｌθ¹θ⁼θω

```

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

```
Ｗθ

```

Repeat until the input becomes the empty string (because all quoted substrings were successfully parsed) or zero (because an error occurred).

```
≔⎇⌕θ"""

```

If the input does not begin with `"""`, then...

```
∧∧¬⌕θ"⊖№θ"✂θ⊕§⌕Ａθ"¹Ｌθ¹

```

... it must begin with `"` and contain at least two `"`, in which case slice it after the second `"`, otherwise...

```
∧⊖№θ"""✂θ⁺⁶⌕✂θ³Ｌθ¹"""Ｌθ¹θ

```

... it must begin contain at leat two `"""`, in which case slice it after the second `"""`.

```
⁼θω

```

Output whether the input was valid.

# Answer
> 4 votes
# Regex (Javascript/PCRE), ~~31~~ 28 bytes

* -3 bytes thanks to Neil and Mukundan314

```
^(""$|"a+"|"""("?"?a)*""")+$

```

Try it on regexr

Basically:

* Empty single-quoted string may appear only at the end
* A single-quoted string outside the end must contain at least one element, this makes it unambiguous with a triple quoted string. Since "stock" regex has no way to prevent backtracking there must be no ambiguity.
* A triple quoted string may contain up to 2 quotes in a row. These quotes may not be at the end. If they where at the end they would end the string early. Unlike single quoted strings tripple quoted ones may be empty without introducing ambiguity.

# Answer
> 4 votes
# x86-64 machine code, 24 bytes

```
E2 03 6A 06 59 B0 14 AE 7B F6 18 D2 D2 C0 24 01 83 C9 03 00 D0 78 EE C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of a null-terminated byte string consisting of `"` and `x` in RDI, and returns 0 or 1 in AL. The starting point is after the first 2 bytes.

---

This uses a single-pass algorithm: it processes each character of the string in order. The validity condition can be checked by a DFA like this:

(Technically, to satisfy the most common definition of a DFA, we would need to fill in the missing transitions, pointing them to a sink state. But the program can easily return before the end of the string, so this is not a problem.)

We number the states 7, 6, 5, 4, 3, 2, 1 in the order shown, so that implementing the `"` transition is easy: subtract 1, and if the result is 0, change it to 6. The current state number is held in RCX.

The `x` character and the null terminator can be handled together, as follows:

|  | N0/N2 | Other |
| --- | --- | --- |
| NUL | Success | Failure |
| `x` | Failure | S/T |

The "S/T" case is implemented by bitwise-ORing the state number with 3, which changes it to 3 or 7 as appropriate.

In assembly:

```
q:  loop n          # (For ") Decrease RCX by 1, and jump if the result is not 0.
f:  push 6; pop rcx # (When it hits 0, or at the start) Set RCX to 6.
n:  mov al, 0x14    # Set AL to 0x14.
    scasb           # Read a byte from the string, advancing the pointer,
                    #  and set flags based on AL minus that byte.
    jpo q           # Jump if the sum of the bits is odd (true only for ").
    sbb dl, dl  # Subtract DL+CF from DL, making it 0 for NUL or -1 for x.
    rol al, cl  # Rotate AL left by the low byte of RCX, the state number...
    and al, 1   # ...and keep only the low bit, which is 1 only for state 4 or 6.
    or ecx, 3   # Bitwise-OR ECX with 3, changing 1–3 to 3 and 4–7 to 7.
    add al, dl  # Add DL to AL, making 1 for success, 0 for failure, -1 for S/T.
    js n        # Jump (to continue processing the string) if it's negative.
    ret         # Return.

```

# Answer
> 3 votes
# 05AB1E (legacy), ~~2~~ ~~1~~ 2 bytes

```
§g

```

-1 byte by changing an explicit evaluate as Python (`.E`) to an implicit one (`§`)
+1 byte because apparently the default is truthy/falsey when it's unspecified. I was under the impression two distinguished values were the default, unless truthy/falsey was mentioned specifically.

Input wrapped in a list (as-is, since 05AB1E uses `"`/`"""` for string-quotes as well).
Outputs `1` for truthy or nothing for falsey.

Try it online or verify all test cases

**Explanation:**

```
§   # Cast the (implicit) input to a string, which is implicitly evaluated as Python†
    # (if it was invalid Python, it will stop the program and output nothing)
 g  # Pop and push the length, to make the truthy cases explicit 1
    # (after which the truthy case is output implicitly with trailing newline)

```

† This only applies to the legacy version of 05AB1E, which is build in Python. In the new version of 05AB1E (build in Elixir), this wouldn't work.

---

# 05AB1E, 34 bytes

```
ΔU17SbεXr¡D¬õQ©sg3@*i¦¦yýëX}}®è}õQ

```

Less boring approach without Python eval. Uses `1` instead of `"` in the inputs.
Not the shortest approach, but at least it works.

Try it online or verify all test cases.

**Explanation:**

```
Δ                   # Continue until the result no longer changes
                    # (using the implicit input-string in the first iteration):
 U                  #  Pop the current string, and store it in variable `X`
 17S                #  Push pair [1,7]
    b               #  Convert each to binary: [1,111] (these are the quotes to check)
     ε              #  Map over them:
      X             #   Push string `X`
       s            #   Swap so the current (binary) quote is at the top
        ¡           #   Split string `X` on this single/triple (binary) quote
         D          #   Duplicate the split list
          ¬         #   Push its first item (without popping)
           õQ       #   Check that the first item is an empty string
                    #   (which means string `X` starts with the current (binary) quote)
             ©      #   Store this 0 or 1 in variable `®` (without popping)
         s          #   Swap so the split list is at the top again
          g         #   Pop and push its length
           3@       #   Check that this length is >=3
                    #   (which means there is a matching closing quote)
              *i    #   If both checks are truthy:
                ¦   #    Remove the empty first string
                 ¦  #    As well as the second string
                yý  #    Then join it with the (binary) quote again
               ë    #   Else:
                X   #    Simply keep `X` as is
               }    #   Close the if-else statement
     }              #  Close the map
      ®             #  Push the last `®` result for the triple-quote
       è            #  0-based index this check into the pair
}                   # After the loop:
 õQ                 # Check if what remains is an empty string
                    # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Whython, 20 bytes

```
lambda s:eval(s)+s?0

```

Just getting the obvious out of the way.

Attempt This Online!

### Explanation

Whython is mostly Python 3, but with a couple added features. Here, we use the rescue operator `?`, which returns its left operand unless it raises an exception, in which case it returns its right operand instead. So if the argument `s` represents a valid string, `eval(s)` returns that string. Since the string can be empty, we concatenate `s` to it to make sure the result is nonempty and therefore truthy. If `s` is not a valid string, `eval(s)` errors, so we return `0` (falsey) instead.

# Answer
> 2 votes
# GolfScript, 18 bytes

```
'"""'/['"']+2%{~}%

```

Try it online!

Split on ````` and eval each. Why 18 bytes though? :(

# Answer
> 2 votes
# Regex (Perl or PCRE), 21 bytes

```
^(?>("("")?+).*?\1)+$

```

Test online on Regex101

The idea to use a backreference was inspired by @Neil's answer. I wrote the rest myself, but most of it ended up the same (probably because there's only one shortest way to express the algorithm, so two golfers will come to the same conclusions).

The Regex101 link uses the `/gm` flags in order to test multiple inputs at once – the problem as stated takes only a single input, so those flags aren't required and aren't part of the submission. (The existence of Regex101 establishes "regex" as a valid programming language by itself for the purposes of this site, as Regex101 acts as an interpreter for the language.)

## Explanation

```
^(?>("("")?+).*?\1)+$
^                   $    Only the input as a whole matches
 (                )+     The input must consist of one or more of:
    (       )              a group named \1, which consists of
     "                     one double quote,
      ("")                 followed by two more double quotes
          ?+                 if they are present at that point in the input,
             .*            followed by any number of any characters,
               ?             the shortest number which leads to a match,
                \1         followed by another copy of \1,
  ?>                     but try only the first possibility for each block

```

Here, each block has its own `\1`, i.e. the delimiter is allowed to be different for each block.

Normally, regexes can backtrack if one potential parse doesn't work, to try a different potential parse. This solution therefore has to contain a couple of backtracking-blockers in order to ensure that if Python would reject a parse, we also reject the input rather than backtracking:

* The `+` on `"("")?+` means that if three double-quotes are present in a row at that point of the input, all three double-quotes must be included in `\1`, the variable that holds the delimeter; the regex engine isn't allowed to go back and try with just one. This ensures that `"""a"` is correctly rejected, by preventing it being parsed as `""``"a"`.
* The `?>` means that once the first possibility for a string in the input has been discovered, that must be used as a section when matching for the string as a whole; the regex engine isn't allowed to go back and try a different section. Because of the `?` on `.*?`, sections are tested shortest to longest, so in this situation, the restriction imposed by `?>` can equivalently be stated as "if any prefix of the input is a valid string, that prefix must be interpreted as the string, don't look for any longer prefixes that might also be valid". This ensures that `"""a""""` is correctly rejected, by preventing it being viewed as `a"` within triple quotes (because `"""a"""` is a valid string that will be tested first).

# Regex (Perl or PCRE, no backreferences), 25 bytes

```
^(?>""".*?"""|"a+"|""$)+$

```

Test online on Regex101

The thing that first inspired me to try answering this question with regex is that the set of allowed answers is a regular expression in the mathematical sense – you can solve it purely with a finite state automaton. Here's an answer that demonstrates that.

It's pretty similar to the previous solution, except that there are separate cases for the `"` and `"""` delimiters. When using `"""`, the string can be empty; as in the previous answer, there's a backtracking-blocker (here `?>`) present to ensure that only the first `"""` is matched. When using `"`, then the regex needs to disallow possibilities that would start with `"""`. The only such possibility is an empty string followed by another string, so we ensure that either the string is nonempty (i.e. it contains `a+`, i.e. one or more `a`), or else that we have an empty string at the end of input (written in regex syntax as `""$`).

As a side note, the fact that the set of answers is a regular expression in the mathematical sense implies that problem can also be solved without backtracking-blockers at all (meaning that no evaluation order hints are required either). However, the solution would likely be somewhat longer; the best I've found is `^("""("{0,2}a)*"""|"a+"|""$)+$` at 30 bytes.

# Answer
> 1 votes
# Turing Machine Code, 147 bytes

```
0 " _ r 1
0 _ _ * haltA
1 " _ r 2
1 a _ r S
2 " _ r T
2 _ _ * haltA
S a _ r S
S " _ r 0
T a _ r T
T " _ r 3
3 " _ r 4
3 a _ r T
4 " _ r 0
4 a _ r T

```

Try it online!

The input string is valid iff the machine halts on state `haltA`. Note that the machine is basically a DFA.

# Answer
> 1 votes
# C (gcc), 84 bytes

```
n;S;g(char*s){n=bcmp(s,S="\"\"\"",3)?1:3;S=strstr(s+n,S+3-n);n=*s-34?!*s:S&&g(S+n);}

```

Try it online!

Require 32-bit or +5 byte `long`

# Answer
> 0 votes
# Vyxal, 1 byte

Try it Online!

Python `eval` and inputs as a list. Returns a a list `[0]` if true and an empty list `[]` if false.

# Answer
> 0 votes
# Python (built-in), 4 bytes (built-in), JS (TODO)

Because I'm evil and mousetail allowed me to.

```
exec

```

~~I'll add a C answer later.~~ A C answer has already been added, so I'll add a JS answer by 19 November 2022.

Note: there are other answers that deserve your upvote, rather than this one.

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


# Question
Title: Calculate \$ \lfloor n \log_2(n) \rfloor \$, exactly
Given an integer \\$ n \ge 2 \\$, you need to calculate \\$ \lfloor n \log\_2(n) \rfloor \\$, assuming all integers in your language are unbounded.

However, you may **not** ignore floating-point errors - for example, in python `lambda n:int(n*math.log2(n))` is an invalid solution, because for example for `n=10**15`, `int(n*math.log2(n))` is 49828921423310432, while the actual answer is 49828921423310435.

## Rules

## Test cases

```
2 -> 2
3 -> 4
4 -> 8
5 -> 11
6 -> 15
7 -> 19
8 -> 24
9 -> 28
10 -> 33
100 -> 664
1000 -> 9965
10000 -> 132877

```

10 brownie points for beating my 4 byte 05AB1E answer.

This is code golf, so the shortest answer wins. Good luck!

# Answer
> 24 votes
# Python 3, 25 bytes

```
lambda n:len(bin(n**n))-3

```

Try it online!

If the answer is \\$x\\$, then \\$x+1 \> n\log{n} \ge x\\$ holds true, which means \\$2^{x+1} \> n^n \ge 2^x\\$. So we can simply count the number of bits in the binary representation of \\$n^n\\$.

# Answer
> 5 votes
# Vyxal, 4 bytes

```
ebL‹

```

Try it Online!

Translation of @ManishKundu's Python answer.

# Jelly, 5 bytes

```
*`BL’

```

Try it online!

Ditto.

# Answer
> 3 votes
# Jelly, 4 bytes

```
*ḃ2L

```

A monadic Link accepting an integer, \\$n\>1\\$, that yields \\$ \lfloor n \log\_2(n) \rfloor \\$.

**Try it online!**

### How?

As noted by Manish Kundu the answer is one less than the number of binary digits of \\$n^n\\$.

This can be achieved in Jelly in five bytes in a few ways one of which is: `*b2L’`.

Note, however, that \\$n^n=2^x-1\\$ has no integer solutions except \\$n=x=1\\$ (see Wolfram Alpha\*) and that the bijective base two representation of a number always has one less digit than the standard base two representation except when the number is of the form \\$2^k-1\\$ (when both representations are identical, a string of \\$k\\$ ones).

Since \\$n=1\\$ is invalid input we can, therefore, count the number of digits in the bijective base two representation of \\$n^n\\$.

```
*ḃ2L - Link: integer, n
*    - (n) exponentiate (n) -> n^n
  2  - two
 ḃ   - (n^n) in bijective base (2)
   L - length

```

* if someone has a proof, I'll happily put it here!

# Answer
> 3 votes
# MATL, 7 bytes

```
X$tZl*k

```

Try it online!

```
X$tZl*k
X$       - sym, implicit input
  t      - duplicate top of stack and push it
   Zl    - log2
     *   - multiply
      k  - floor

```

This is just what elementiro did except in golfed MATLAB, and since this is my first time posting, I am not sure if this is considered a duplicate.

# Answer
> 2 votes
# Ruby, 20 bytes

```
->n{/.$/=~"%b"%n**n}

```

Try it online!

Get the length of the binary string representation of n^n. Basically uses the same formula as Manish Kundu and everybody else after him.

Using `bit_width` or `digits(2).size` would make it longer.

# Answer
> 1 votes
# Julia, ~~18~~ 24 bytes

```
n->ndigits(n^n,base=2)-1

```

Try it online!

port of Manish Kundu's answer

### previous answer:

```
n->floor(log2(n)n)

```

Try it online!

input needs to be a `BigInt` to avoid floating point errors.

Technically invalid because you need to augment the precision for very big numbers (with `setprecision(2048)` for example for `10^100`)

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~17~~ 15 bytes (11 characters)

```
⌊#*Log2@#⌋&

```

-2 thanks to ZaMoC!

Try it online!

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

Same approach as Manish Kundu.

Expects a BigInt.

```
n=>(g=n=>n?g(n/2n)+1:-1)(n**n)

```

Try it online!

# Answer
> 1 votes
# Perl 5 `-Mbignum -p`, 24 bytes

```
$_=int$_*(1*$_)->blog(2)

```

Try it online!

# Answer
> 1 votes
# Charcoal, ~~10~~ 8 bytes

```
Ｉ⊖Ｌ↨Ｘθθ²

```

Try it online! Link is to verbose version of code. Explanation: Uses the same identity \\$ \lfloor n \log\_2 n \rfloor = \lfloor \log\_2 n^n \rfloor \\$ as everyone else. (Exponentially slow for large `n` of course, so stick to 4 digit inputs for testing on TIO.) Edit: Saved 2 bytes thanks to @CommandMaster.

# Answer
> 0 votes
# 05AB1E (legacy), 4 bytes

```
mbg<

```

Try it online!

# Answer
> 0 votes
# Pyth, 5 bytes

```
tl.B^

```

Test suite

A near literal translation of Manish Kundu's Python 3 answer.

# Answer
> 0 votes
# C (gcc), ~~52~~ \\$\cdots\\$~~35~~ 23 bytes

Saved 8 bytes thanks to tsh!!!

```
f(n){n=logb(pow(n,n));}

```

Try it online!

Uses the formula from Manish Kundu's Python answer.

# Answer
> 0 votes
# Java, 36 bytes

```
n->n.pow(n.intValue()).bitLength()-1

```

Accepts a `BigInteger` as input.

Try it online!

# Answer
> 0 votes
# MATLAB/Octave, 30 bytes

```
@(x)floor(sym(x)*log2(sym(x)))

```

Try it online! Anonymous function. The result is symbolic number but can be easily cast to any other type. This solution works as long as the upper bound of `int64` allows it.

---

Technically, much better solution is `@(x)floor(x*log2((x)))` (which is **20 bytes** btw) with symbolic input. Since the question says input is integer I couldn't use it though. Because our input is unbounded it works for much much bigger numbers (I managed to calculate 101 000 000 but the calculations took a while and the output in console was truncated, for too big numbers throws an error though). I encourage anyone to check the result for 10300 if their method is capable of working for such big inputs:

```
f(sym(10^300)) =

996578428466208704361095828846817052759449417907374183616426918744780432982587564755041923007811046529897211513075075548047229095279058066482590831899596618155585405797251670592905282757007467500082430012203570937256212532914759940262053756896742020749233906529817764982497756734670715067992925218241378

```

*...did I mention unlike some of the other answers this takes only ~0.05s for MATLAB to calculate even for that big inputs?*

# Answer
> 0 votes
# Pyt, 5 bytes

```
ṖɓąŁ⁻

```

Try it online!

```
ṖɓąŁ⁻
Ṗ        implicit input (n); raise n to the nth power
 ɓ       convert to binary string
  ąŁ     convert string to array of characters and get length
    ⁻    subtract one; implicit print

```

Port of Manish Kundu's Python answer

---
Tags: code-golf, math, number, integer
---


title: We're much closer than you think

text:
# Question
Title: We're much closer than you think
Martin Ender's 2D programming language Alice has two different modes depending on what orientation the IP has: orthogonal (Cardinal mode) or diagonal (Ordinal mode). Commands in Alice change their meaning depending on which mode the program is in when they're executed. One especially interesting implementation of this is Alice's `Z`, or "pack", command. For strings in Ordinal mode, this simply takes two strings **a** and **b** and interleaves (also known as "zip") them. For example:

```
a = "Hello"
b = "World"
Z -> "HWeolrllod"

```

However, while in Cardinal mode, `Z` pops two integers \\$n\\$ and \\$m\\$ and returns \\$\pi(n,m)\\$*, the Cantor pairing function. For example, for \\$n = 2, m = 3\\$, `Z` returns \\$\pi(2, 3) = 18\\$. The reasoning behind this is explained in this answer.

For clarity, the Cantor pairing function uses the following formula:

$$\pi(n,m) = \frac12(n+m)(n+m+1)+m$$

---

You are to write two **non-identical** programs that implement the two modes of `Z`. More specifically:

* The first should take two non-empty strings containing only printable ASCII (`0x20` to `0x7e`) of the same length* and output these strings zipped/interleaved together
* The second should take two non-negative integers \\$x\\$ and \\$y\\$ and should output \\$\pi(x, y)\\$ as specified above.

*: This isn't *technically* how the `Z` command works, read the Alice docs for more

You may input and output in any accepted method, and you may assume all inputs are reasonable for your language.

Your score is the Levenshtein distance between your two programs multiplied by the sum of the program lengths, aiming for a lower score. You can use this website to calculate Levenshtein distance.

## Test Cases

For the first program:

```
a, b -> Z
"a", "b" -> "ab"
"Hello,", "World!" -> "HWeolrllod,!"
"World!", "Hello," -> "WHoerllldo!,"
"Alice", "     " -> "A l i c e "

```

The second program:

```
n, m -> π(n, m)
2, 3 -> 18
5, 5 -> 60
0, 1 -> 2
1, 0 -> 1
100, 75 -> 15475

```

# Answer
> 11 votes
# Jelly, Score 1 * 8 bytes = 8

String zip:

```
+Ẇɼ+

```

Try it online!

Cantor pairing function:

```
+ẆL+

```

Try it online!

We use the fact that the Cantor pairing is equal to

$$ {n + m + 1 \choose 2} + m $$

Where the left term just happens to be the number of nonempty contiguous slices of \\$m+n\\$. This saves two bytes per program over the naive `+‘×+H+`, and one byte over the (less naive) `+‘c2+`.

Conveniently, in Jelly `+` zips strings (I had no idea!).

Explanations:

```
          Implicit input: strings s1, s2
+         Zip s1, s2.
 Ẇ        All nonempty slices.
  ɼ       Save the result to register (ignore previous 2).
   +      Zip s1, s2.

```

```
          Implicit input: numbers n, m
+         Compute m+n.
 Ẇ        All nonempty slices of implicit range m+n.
  L       Length.
   +      Add m.

```

---

Note that there are many ways to get 4 for the pairing function (`+R;S`, `+R+ƒ`, etc)

# Answer
> 5 votes
# Husk, score 1 × 12 bytes = 12

First program:

```
₅
+¹Σ+

```

Try it online! It takes \\$n\\$ and \\$m\\$ as two separate arguments.

Second program:

```
Ξ
+¹Σ+

```

Try it online! It takes the two strings in a list.

In the first program, the main function just calls the auxiliary function with its arguments flipped, and in the second program, the auxiliary function is ignored altogether.

# Answer
> 5 votes
# Python 3, 1 * (50 + 50) = 100

-2 bytes thanks to Neil!

**First function**:

Output is a tuple of characters.

```
lambda a,b:1and sum(zip(a,b),())or(a+b)*(a-~b)/2+b

```

Try it online!

**Second function**:

```
lambda a,b:0and sum(zip(a,b),())or(a+b)*(a-~b)/2+b

```

Try it online!

# Answer
> 5 votes
# Haskell, score 1×(43+43)=86

One program is:

```
a!b=sum[1..a+b]+b
(a:b)%(c:d)=a:c:b%d;a%b=b

```

It defines `a!b` = π(a, b), and an unused “helper function” `(%)`.

The other program is the same, but with a semicolon instead of a newline.

It defines `x%y` = Z(x, y), and an unused “helper function” `(!)`.

# Answer
> 4 votes
# Charcoal, score ~~200~~ ~~44~~ 1 * 42 bytes = 42

crossed out 44 is still regular 44

First program:

```
¿¹⭆§θ⁰⭆θ§λκＩ⁺Σ…·⁰Σθ⊟θ

```

Second program:

```
¿⁰⭆§θ⁰⭆θ§λκＩ⁺Σ…·⁰Σθ⊟θ

```

Explanation: Port of @ovs's approach. An `if` statement at the start is used to select the desired code, thus the distance between the two programs is one byte. Since one program has string output and the other has numeric output it's not possible to share code between the two. See the original answer that scored 10 * ~~20~~ 19 bytes = ~~200~~ 190 below for how each branch of the `if` works:

First program:

```
⭆§θ⁰⭆θ§λκ

```

Try it online! Link is to verbose version of code. Takes input as an array of two strings. Explanation:

```
  θ         Input array
 § ⁰        First element
⭆           Map over characters and join
     θ      Input array
    ⭆       Map over strings and join
       λ    Current string
      §     Indexed by
        κ   Outer index
            Implicitly print

```

Second program:

```
Ｉ⁺Σ…·⁰Σθ⊟θ

```

Try it online! Link is to verbose version of code. Takes input as an array of two integers. Explanation:

```
     ⁰      Literal `0`
       θ    Input array
      Σ     Sum
   …·       Inclusive range
  Σ         Sum
 ⁺          Plus
        ⊟   Last element of
         θ  Input array
Ｉ           Cast to string
            Implicitly print

```

# Answer
> 4 votes
# JavaScript (ES6), 1 * 102 bytes = 102

Doing it the @ovs way.

### Ordinal mode, 51 bytes

```
a=>b=>1?b.replace(/./g,(c,i)=>a[i]+c):b-(a+=b)*~a/2

```

Try it online!

### Cardinal mode, 51 bytes

```
a=>b=>0?b.replace(/./g,(c,i)=>a[i]+c):b-(a+=b)*~a/2

```

Try it online!

---

# JavaScript (ES6), 13 * 70 bytes = 910

### Ordinal mode, 35 bytes

```
e=>l=>l.replace(/./g,(l,i)=>e[i]+l)

```

Try it online!

### Cardinal mode, 35 bytes

```
e=>l=>l+(e,l-~e)/2*(((l,i)=>e,e)+l)

```

Try it online!

```
e=>l=>l.replace(/./g,(l,i)=>e[i]+l)
       ## # ## # ####        ###    // 13 differences
e=>l=>l+(e,l-~e)/2*(((l,i)=>e,e)+l)

e=>l=>                              // given e and l,
      l+(                           // compute l +
         e,                         // (meaningless filler)
           l-~e)/2*((               // (l + e + 1) / 2 *
                     (l,i)=>e,      // (meaningless filler)
                              e)+l) // (e + l)

```

# Answer
> 3 votes
# 05AB1E, 6 4dist(2 + 6 4) = 48 24 scored

*-24 points thanks to @ovs!*

I am sure that the programs can be heavily improved.

**Ordinal mode:**

Outputs the zipped string as a list of characters.

Also takes in input swapped, so `"Hello,", "World!" -> "WHoerllldo!,"` and `"World!", "Hello," -> "HWeolrllod,!".`

## How?

```
.ι          # Interleave the two inputs, then output implicitly

```

Try it online!

**Cardinal mode:**

```
+LO+

```

Takes in input in the right order this time!

## How?

```
+         # Add m and n
 LO       # Summation of all numbers in range [1...m+n]
   +      # Add m (which is still surviving in the stack) to the result and output implicitly

```

Try it online again!

# Answer
> 2 votes
# , 1×(76+76) = 152

Ordinal mode:

```
function(a,`^`=Reduce,p=paste0)`if`(F,sum(1:sum(a),a[2]),p^p^strsplit(a,""))

```

Try it online!

Cardinal mode:

```
function(a,`^`=Reduce,p=paste0)`if`(T,sum(1:sum(a),a[2]),p^p^strsplit(a,""))

```

Try it online!

Input is as a length-2 vector.

The only difference between the two functions is the 37th character, which flips between `F` and `T`. Either the second or the third argument of `if` is therefore executed. For the ordinal mode (interleaving), I relied on this tip by J.Doe.

# Answer
> 1 votes
# Pyt, 2x(6+6)=24

Ordinal mode:

```
Đ←+⇹ŕǰ

```

Requires strings to be passed in as arrays of characters

Try it online!

```
Đ         implicit input; duplicate string
 ←        get second input
  +       element-wise string addition
   ⇹ŕ     flip the stack and remove the top
     ǰ    join the list of strings into one string; implicit print

```

Cardinal mode:

```
Đ←+△+ǰ

```

Try it online!

```
Đ           implicit input (m); duplicate top of stack
 ←          get input (n)
  +         add the top two items on the stack (yielding n+m)
   △        get the (n+m)th triangle number
    +       add the top two items on the stack (yielding 1/2*(n+m)*(n+m+1)+m)
     ǰ      join the stack as strings (essentially a no-op here)

```

---
Tags: string, number, code-challenge, arithmetic
---