title: Keep/Drop/Increase Sequence

text:
# Question
Title: Keep/Drop/Increase Sequence
Here is the sequence I'm talking about:

```
{1, 4, 5, 9, 10, 11, 16, 17, 18, 19, 25, 26, 27...}

```

Starting from 1, keep 1, drop the next 2, keep the next 2, drop 3, keep 3 and so on. Yes, it's on OEIS (A064801), too!

**The Challenge**

Given an integer `n>0`, find the nth term of the above sequence

**Test Cases**

```
Input -> Output
1->1
22->49
333->683
4444->8908
12345->24747

```

This is code golf so the shortest answer in bytes wins! Good luck!

# Answer
# Java (OpenJDK 8), ~~45~~ 44 bytes

```
n->{int i=0;for(;++i<n;n-=i);return~-n+i*i;}

```

Try it online!

*-1 byte thanks to @Nevay*

After staring at this for a while, I noticed a pattern. Every time we drop `n` numbers, the next number in the sequence is a perfect square. Seeing this, I mentally broke the sequence into convenient chunks: `[[1],[4,5],[9,10,11],...]` Basically, the `i`th chunk starts with `i*i`, and iterates upwards for `i` elements.

To find the `n`th number in this sequence, we want to find first which chunk the number is in, and then which position in the chunk it occupies. We subtract our increment number `i` from `n` until `n` is less than `i` (which gives us our chunk), and then simply add `n-1` to `i*i` to get the correct `position` in the chunk.

Example:

```
n = 8
n > 1? Yes, n = n - 1 = 7
n > 2? Yes, n = n - 2 = 5
n > 3? Yes, n = n - 3 = 2
n > 4? No, result is 4 * 4 + 2 - 1 = 17

```
> 12 votes

# Answer
# Python 3, ~~47~~ 46 bytes

1 byte thanks to Mr. Xcoder.

```
def f(n):a=round((2*n)**.5);return~-n+a*-~a//2

```

Try it online!

VERY fast for higher numbers
> 8 votes

# Answer
## Haskell, ~~48~~ ~~43~~ 41 bytes

```
n#l=[l..l+n]++(n+1)#(l+2*n+3)
((0:0#1)!!)

```

4 extra bytes for 1-based indexing instead of 0-based. An unnecessary restriction, IMHO.

Try it online!

```
n#l             -- n is one less than the number of element to keep/drop and
                -- l the next number where the keep starts
   [l..l+n]     -- keep (n+1) numbers starting at l
   ++           -- and append a recursive call
   (n+1)#       -- where n is incremented by 1 and
      (l+2*n+3) -- l skips the elements to keep & drop

0#1             -- start with n=1 and l=0 and
 0:             -- prepend a dummy value to shift from 0 to 1-based index
    !!          -- pick the i-th element from the list

```
> 7 votes

# Answer
# Haskell, 33 bytes

An anonymous function. Use as `((!!)$0:do n<-[1..];[n^2..n^2+n-1]) 1`

```
(!!)$0:do n<-[1..];[n^2..n^2+n-1]

```

Try it online!

* Constructs the sequence as an infinite list, then indexes into it with `!!`. The `0:` is a dummy element to adjust from 0- to 1-based indexing.
* The range `[n^2..n^2+n-1]` constructs a subsequence without gaps, starting with the square of `n` and containing `n` numbers.
* The `do` notation concatenates the constructed ranges for all `n>=1`.
> 4 votes

# Answer
# Jelly, 8 bytes

```
Ḷ+²µ€Ẏ⁸ị

```

Try it online!
> 3 votes

# Answer
# Python 3, 46 bytes

```
f=lambda x,y=0,z=0:y<x and f(x,y+z,z+1)or~-y+x

```

Try it online!
> 3 votes

# Answer
# TeX, 166 bytes

```
\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

```

## Usage

```
\documentclass[12pt,a4paper]{article}
\begin{document}
\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

\f{1}

\f{22}

\f{333}

\f{4444}

\f{12345}
\end{document}

```
> 3 votes

# Answer
# 05AB1E, 12 bytes

```
LεÝÁćn+}˜¹<è

```

Try it online!
> 2 votes

# Answer
# Perl 6, 43 bytes

```
{(1..*).rotor({++$=>++$+1}...*).flat[$_-1]}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  ( 1 .. * )                  # range starting from 1

  .rotor(                     # break it into chunks

    { ++$  =>  ++$ + 1} ... * # infinite Seq of increasing pairs
    #   1  =>    1 + 1    ==>   1 => 2 ( grab 1 skip 2 )
    #   2  =>    2 + 1    ==>   2 => 3
    #   3  =>    3 + 1    ==>   3 => 4
    # ...  =>  ... + 1

  ).flat\                     # reduce the sequence of lists to a flat sequence
  [ $_ - 1 ]                  # index into the sequence
                              # (adjusting to 0-based index)
}

```

`(1..*).rotor({++$=>++$+1}...*)` produces:

```
(
 (1,),
 (4, 5),
 (9, 10, 11),
 (16, 17, 18, 19),
 (25, 26, 27, 28, 29),
 ...
).Seq

```
> 2 votes

# Answer
## Mathematica, 37 bytes

```
Flatten[Range@#+#^2-1&~Array~#][[#]]&

```

## Explanation

```
Range@#+#^2-1&

```

`Function` which takes a positive integer `#` and returns the run of `#` consecutive numbers in the sequence.

```
...~Array~#

```

Produces the list of all such runs up to the input `#`

```
Flatten[...][[#]]

```

`Flattens` the resulting list and returns the `#`th element.
> 2 votes

# Answer
# Javascript, ~~43~~ 38 bytes

```
n=>eval("for(r=1;n>r;)n-=r++;r*r+n-1")

```

Try it online!

I use the fact, that for each triangular number plus one, the result is a square number.

As an example: triangular numbers are 0, 1, 3, 6, 10... so for 1, 2, 4, 7, 11... we observe 1, 4, 9, 16, 25... in our sequence.

If the index is somewhere between these known numbers, the elements of our sequence only advance by one. For instance, to calculate the result for 10, we take 7 (as a triangular number plus one), take the result (16) and add 10-7=3. Thus, 16+3=19.
> 2 votes

# Answer
# Vyxal, 8 bytes

```
v₍ʁ²ṠfJi

```

Try it Online!

Would beat Jelly if zero-indexing were allowed (remove `J`).

```
v₍ʁ²ṠfJi
v        # For each in a range [1, n]:
 ₍       #  Apply both of the next two elements and wrap in a list:
  ʁ      #   Range [0, n), and:
   ²     #   Square n
    Ṡ    # Sum each (vectorizing)
         # For an input of 4, this will give [[1], [4, 5], [9, 10, 11], [16, 17, 18, 19]]
         # Basically, for each x in [1, n], add x^2 to each in [0, x)
     f   # Flatten
      J  # Prepend the input to the beginning (doesn't matter what we prepend)
       i # Index the input into this

```
> 2 votes

# Answer
# cQuents, 27 bytes

```
#R(2B)^.5)|1:b~-B+A*-b~A//2

```

Try it online!

Currently a port of Leaky's Python answer, I think there's a better way though.
> 1 votes

# Answer
# Swift 3, 72 bytes

Port of my Python solution.

```
func f(_ x:Int,_ y:Int=0,_ z:Int=0)->Int{return y<x ?f(x,y+z,z+1):y+x-1}

```

**Test Suite.**
> 1 votes

# Answer
# C# (Mono), 164 bytes

```
using System.Linq;n=>{var a=new int[1]{1}.ToList();for(int i=1,m;a.Count<n;a.AddRange(new int[++i*2].Select((_,d)=>m+d+1).Skip(i).Take(i)))m=a.Max();return a[n-1];}

```

Try it online!
> 1 votes

# Answer
# Perl 5, 33 + 1 (-p) = 34 bytes

```
$\+=$.--?1:2+($.=++$s)while$_--}{

```

Try it online!
> 1 votes

# Answer
# MATL, 12 bytes

```
:"@U@:q+]vG)

```

Try it online!

### Explanation

```
:        % Push range [1 2 ... n], where n is implicit input
"        % For each k in that range
  @U     %   Push k^2
  @:     %   Push range [1 2 ... k]
  q      %   Subtract 1: gives [0 1 ... k-1]
  +      %   Add: gives [k^2 k^2+1 ... k^2+k-1]
]        % End
v        % Concatenate all numbers into a column vector
G)       % Get n-th entry. Implicitly display

```
> 1 votes

# Answer
# Tampio, ~~310~~ 308 bytes

```
n:n uni on n unena 1:lle
a unena k:lle on a vuona k:lla vähennettynä a:sta ja k
a vuona nollalla ja k on a
a vuona k:lla vähennettynä nollasta ja k on a
a vuona b:n seuraajalla ja k on yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla ja k:n vähennettynä a:sta arvolla unena k:n seuraajalle seuraaja

```

Usage: `4:n uni` evaluates to `9`.

Explanation:

```
n:n uni on n unena 1:lle
uni(n)  =  n `uni` 1

a unena k:lle on  a vuona  k:lla vähennettynä a:sta ja k
a `uni` k     =  (a `vuo` (k     `vähennetty` a)    )  k

 a vuona nollalla ja k on a
(a `vuo` 0        )  k =  a

 a vuona  k:lla vähennettynä nollasta ja k on a
(a `vuo` (k     `vähennetty` 0)       )  k =  a

 a vuona  b:n seuraajalla ja k on
(a `vuo` (b   + 1)        )  k =

 yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla
(yhteenlasku            (k   *          2     )

 ja k:n vähennettynä a:sta arvolla unena  k:n seuraajalle seuraaja
((  k   `vähennetty` a     )       `uni` (k   + 1)   )  ) + 1

```

From standard library:

```
a `vähennetty` b = b - a
yhteenlasku a b  = a + b

```
> 1 votes

# Answer
# JavaScript (ES6), 33 bytes

Recursive solution inspired by Xanderhall's observations.

```
f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)

```

---

## Try it

```
o.innerText=(
f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)
)(i.value=12345);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```
> 1 votes

# Answer
# Python 3, 50 bytes

```
def f(n):
 a=i=0
 while a<n:a+=i;i+=1
 return~-a+n

```

Try it online!
> 0 votes

# Answer
# Mathematica, 82 bytes

```
Complement[Range[3#],Array[#+⌊((r=Sqrt[1+8#])-1)/2⌋⌊(r+1)/2⌋/2&,3#]][[#]]&

```
> 0 votes

# Answer
# Python, 40 bytes

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

```

Try it online!

Optimizing Leaky Nun's expression.

---

# Python, 41 bytes

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

```

Try it online!

Recursive expression.
> 0 votes

# Answer
# Javascript (ES6) 100 98 Bytes

```
var k=n=>{var s=[],i=1,c=1,j;while(s.length<n){for(j=i;j<i+c;j++){s.push(j)}i+=c*2+1;c++}return s}

```

Kind of did this one fast, so I bet there is a lot of room for improvement, just basic loops and counters.
> 0 votes

# Answer
# Retina, 27 bytes

```
.+
$*
((^1|1\2)+)1
$1$2$&
1

```

Try it online! Port of @LeakyNun's Python answer. The first and last stages are just boring decimal ⇔ unary conversion. The second stage works like this: `((^1|1\2)+)` is a triangular number matcher; `$1` is the matched triangular number while `$2` is its index. The trailing `1` means it matches the largest triangular number strictly less than the input, thus resulting in exactly one fewer iteration than the Python loop, meaning that `$1` is equivalent to `a-i` and `$2` to `i-1` and their sum is `a-1` or `~-a` as required. (`$&` just prevents the match from being deleted from the result.) Note that for an input of `1` no matching happens and the output is simply the same as the input. If you were perverse you could use `^((^1|1\2)*)1` to match in that case too.
> 0 votes

# Answer
# C (gcc), 38 bytes

Using @Xanderhall's algorithm here

```
i;f(n){for(i=0;++i<n;n-=i);n=n-1+i*i;}

```

Try it online!
> 0 votes

# Answer
# PHP, ~~48 42~~ 37+1 bytes

ported from Leaky Nun´s answer

```
while($argn>$a+=$i++);echo$a+~-$argn;

```

Run as pipe with `-F` or try it online.

**direct approach, 42+1 bytes** (ported from Leaky Nun´s other answer)

```
<?=($a=(2*$argn)**.5+.5|0)*-~$a/2+~-$argn;

```

Run as pipe with `-nR` or uncomment in above TiO.

**older iterative solution, 48+1 bytes**

```
for(;$argn--;$n++)$c++>$z&&$n+=++$z+$c=1;echo$n;

```
> 0 votes

# Answer
# Ruby, ~~37~~ 36 bytes

-1 byte thanks to Steffan

Port of Leaky Nun's Python 3 answer.

```
->n{~-n-(a=((2*n)**0.5).round)*~a/2}

```

Attempt This Online!
> 0 votes

# Answer
# TI-Basic, <sup>~~41~~</sup> 22 bytes

```
Input N
int(.5+√(2N
N-1+.5Ans(Ans+1

```

Port of Leaky Nun's Python 3 answer.

**I was quite happy with my previous 41-byte solution so here it is:**

```
Input N
For I,1,N
For J,1,I(N>0
DS<(N,0
Ans+1
Ans+1
End
End
Ans-1

```

Needs a fresh calculator, or at least `Ans` initialized to `0`
> 0 votes

# Answer
# Japt, 9 bytes

0-indexed

```
g°Uô²cÈóY

```

Try it

```
g°Uô²cÈóY     :Implicit input of integer U
g             :Index into
 °U           :  Prefix increment U
   ô          :  Range [0,U]
    ²         :  Square each
     cÈ       :  Flat map each X at 0-based index Y
       óY     :    Range [X,X+Y)

```
> 0 votes

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


# Question
Title: Lengthy numbers type A : remove all occurrences of length
Given a non negative integer number tell if it can be erased by repeatedly removing **all** occurrences of the length of that number from it **including overlapping matches**.

* Erasing means cancel all its digits. For example the number *4440* is not lengthy because after removing all 4's you obtain *0* which cannot be erased.
Neither the number *50022* or *50044* is lengthy A because you first remove 5 obtaining *0022* or *0044* and there's no way to cancel leading 0's.

**Examples**

```
3610106336 has 10 digits: remove 10's
36xxXX6336 -> 366336

366336 has 6 digits: remove 6's
3xx33x -> 333

333 remove 3's -> erased

```

Here an example with **overlapping matches**.

```
11111666661 has 11 digits

xxXX1666661  \ overlapping 11's
1XXxx666661  /
We have 5 '1' for a total of 4 '11' matched, remove all

666661  -> remove 6's
1 -> and finally 1

```

# Test cases

Truthy

```
1, 12, 21, 22, 123, 321, 322, 331, 333, 4441, 4444, 12345, 987654321, 3610106226, 1010101010, 11111111111, 10812816208148888188, 82428208832101683082414123828341883888,3919555395539111955255533922519455392511539551925395511, 1515515551555515555515555551555555155555155551555155151, 999199999915999991599999999915999915999999919399999999991915999999999999999999999915999999929999999, 10121111011011011011011011011011011012110110110121101110110121111011123101101101101121011011110110111, 15101251011012229752519101110101010101010111111101101101101101111011011011011110111101101101101101915, 2020220202202022020220202232020220202202022020223220232020222220220222202202202202202202202202202202202220223202202202202202202202202222022022022022022022222202202202202202222022022022022022023876543213

```

Falsy

```
0, 2, 9, 10, 11, 23, 233, 4440, 50022, 50044, 1101010101, 11131111311, 121666626162, 181811818128181818, 127271272722672224724122727122712242722472727272722472727272247272127272, 1001023010023100160010010010010061110250100123001001001230061001010100102370100610016001001001110230, 1241242212412241241241241241241241241241241241141624124114241241241242612412412416241222412411424221241244124142412412144124, 108484298442981044294284942984429844294291042942942942849429429484284948429484842942942984104842984429429844298448429429429429429429429428494294294842942942948429428484942942942942984429429844284948429428494842849484284942942942942942984484294294284942942942942942942942942942910429429484294294

```

This is , standard rules apply.

* Input can be given in any convenient method.
* Output any two different values telling if the number is lengthy or not lengthy.

# Answer
# Retina, 16 bytes

```
+~`^.*
v`$.&¶
^$

```

Try it online! Link includes test cases. Explanation:

```
^.*
v`$.&¶

```

Replace the input with a Retina program that erases all overlapping occurrences of its length from it. (Replacing overlapping matches can do weird things in Retina but fortunately only if the matches are variable length.)

```
~`

```

Execute that program on the input.

```
+`

```

Repeat the above until no more erasures can be made.

```
^$

```

Test whether the input was completely erased.
> 7 votes

# Answer
# , 42 bytes

```
''-:(#~1-]+./@(-@i.@#@]|.!.0"{E.~)":@#)^:_

```

Try it online!

Handling overlaps made this awkward, and this was the shortest approach I could find.

Consider string input `'82428208832101683082414123828341883888'`.

The approach is to do the following until a fixed point:

* Find all matches `E.` of the length within the input. This returns a boolean vector where the ones indicate the *start* of each match.

```
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 1 0 0 0 0 0 0 0 0 1 0 0 0

```

But we need to mark every position of each match....
* `-@i.@#@]` So we generate the numbers `0 1 ... <length of length>` (in this case just `0 1`) and then rotate our boolean vector right by each, creating copies of it:

```
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 1 0 0 0 0 0 0 0 0 1 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 1 0 0 0 0 0 0 0 0 1 0 0

```
* `+./` And sum the rows:

```
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 1 1 0 0 0 0 0 0 0 1 1 0 0

```
* Finally we invert the mask and use that to filter the input:

```
8242820883210168308241412283418888

```
* `''-:` Once the fixed point is reach, we just check if the final result is empty.
> 5 votes

# Answer
# Ruby, ~~90 ...~~ 65 bytes

```
->n{n.gsub!(/#{n.size.to_s[/(.*)(.*\1)\2*/]}(#$2)*/){}?redo:n<?0}

```

Try it online!

### How?

To replace overlapping occurrences use the following regex to split:

```
/(.*)(.*\1)\2*/

```

This will always match the whole number that we are searching, but if some parts are repeated in an `ABABABABA` pattern, then the regex groups will capture A and BA. B will be empty if only A is repeated, and A will be empty if the pattern is not repeating.

So, now that we have captured `A` plus any number of occurrences of `BA`, we can use a new regex to find overlapping matches, we need to add `(BA)*` at the end:

```
/#{n.size.to_s[/(.*)(.*\1)\2*/]}(#$2)*/

```

Repeat until there is nothing left to substitute, then check if the string is empty.

Thanks AZTECCO and Dingus each for -1 byte ideas which put together brought the byte count down by 3.
> 5 votes

# Answer
# K (ngn/k), ~~36~~ 33 bytes

-2 bytes from @Traws' improvement, -1 more from tweaking more

```
~#{x@i^/(#n:$#x)#[n~x@;]':i:!#x}/

```

Try it online!

Takes input as a string. If it is okay to return empty lists for "Truthy" inputs, and non-empty lists for "Falsy" inputs, 2 bytes can be trimmed (the leading `~#`).

* `{...}/` set up a converge-reduce, running the code in `{...}` until two successive iterations return the same value or the original input
    + `(#n)#[...;]':i` set up a stencil-apply, with a `(#n)` window size, applying `#[...;]` to each slice of `i`
        - `i:!#x` generate a list of indices of the input, storing in `i`
        - `(#n:$#x)` determine the string to remove, storing in `n`; calculate its length, and use that as the window size
        - `#[n~x@;]` filter each slice down to those that match the string to remove (`n`) (slices that do not match the string to remove become empty lists)
    + `i^/` remove those indices
    + `x@` index into the input, and (implicitly) return
* `~#` convert empty lists to `1`, and non-empty lists to `0`
> 3 votes

# Answer
# JavaScript (ES6), 101 bytes

Returns a Boolean value.

```
f=s=>s==(s=s.replace(/./g,(c,i)=>[...q=s.length+''].some(_=>s.slice(i--).match('^'+q))?'':c))?!s:f(s)

```

Try it online!

Or **92 bytes** by throwing an error if the input cannot be fully erased:

```
f=s=>s&&f(s.replace(/./g,(c,i)=>[...q=s.length+''].some(_=>s.slice(i--).match('^'+q))?'':c))

```

Try it online!
> 2 votes

# Answer
# PowerShell Core, 144 bytes

```
param($a)for(;($i=$a|% Le*)*($l-$i)){$a=-join$a[(($k=0..($l=$a|% Le*))|?{$_-notin($k|?{$a|% su* $_|% s*h "$l"}|%{$_..($_+"$l".Length-1)})})]}!$a

```

Try it online!

Takes the number as a `string`, returns `$true` or `$false`.
The timeout is caused by the "overlapping remove" that generates lots of strings in memory

So here is a version that does not timeout, calculating the array of characters to remove only once: Try it online!
> 2 votes

# Answer
# Mathematica, 114 bytes

```
StringReplacePart[#,"",List@@Interval@@StringPosition[#,ToString@StringLength@#,Overlaps->All]]&~FixedPoint~#==""&

```

View it on Wolfram Cloud!
> 2 votes

# Answer
# 05AB1E, 22 bytes

```
ΔÐgU.sRXδÅ?XgGDÁ~}_Ï}d

```

Port of *@Jonah*'s J answer.

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

Try it online or verify all test cases.

**Explanation:**

```
Δ         # Loop until the result no longer changes:
          # (using the implicit input-integer in the first iteration)
 Ð        #  Triplicate the current integer
  g       #  Pop one, and get its length
   U      #  Pop and store this length in variable `X`
  .s      #  Pop another one, and get a list of its suffices
    R     #  Reverse this list of suffices
      δ   #  Map over the list of suffices:
     X Å? #   Check which suffix starts with the length we stored in variable `X`
  X       #  Push the length from variable `X` again
   g      #  Get the length of that length
    G     #  Loop that length-2 amount of times:
     D    #   Duplicate the current list of 0s/1s
      Á   #   Rotate it once towards the right
       ~  #   Bitwise-OR the values at the same positions together
    }_    #  After the inner loop: invert all 1s/0s
      Ï   #  Only keep the digits in the integer at the truthy indices
}d        # After the changes-loop: check if what remains is a non-negative number
          # (resulting in 0 for the empty strings; 1 if any digits still remain)
          # (which is output implicitly as result)

```

Unfortunately 05AB1E lacks a builtin to get all indices of a match (it only has a builtin `k` for the first index of a match). Otherwise the `.sRXδÅ?` could probably have been a bit shorter.

PS: Without having to deal with overlapping matches, this could be 6 bytes instead: `ΔDgK}d`.
> 2 votes

# Answer
# Charcoal, 23 bytes

```
Ｗ⌕ＡθＩＬθ≔Φθ¬⊙ＩＬθ№ι⁻λνθ¬θ

```

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

```
Ｗ⌕ＡθＩＬθ

```

While there are overlapping matches of the inputs length in the input...

```
≔Φθ¬⊙ＩＬθ№ι⁻λνθ

```

... filter out each character that matched at least one of the digits in the length.

```
¬θ

```

Output whether the input was lengthy.
> 2 votes

# Answer
# C (gcc), ~~153~~ ~~142~~ 137 bytes

-4 bytes thanks to AZTECCO

```
char*o,*a,b[999];k;z;d;f(i,n){a=i;o=b;for(z=k=0;*a;a++)atoi(strndup(a,d=log10(n)+1))^n?k<1?*o++=*a:k--:(z=1,k=d-1);*o=0;z=z?f(b,o-b):!n;}

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~117~~ 109 bytes

-8 bytes thanks to AZTECCO

```
f=->s{a=*0...x=s.size
s.scan(/(?=#{x})/){a-=[*(y=$`.size)...y+x.to_s.size]}
s!=(x=a.map{s[_1]}*"")?f[x]:s>""}

```

Attempt This Online!
> 1 votes

# Answer
# Pyth, 32 bytes

```
W&znz=sm*@zd.Amx>z-dklzl`lzlz;!z

```

Try it online!
> 1 votes

# Answer
# Japt, 26 bytes

```
_ðZl)rÈhXÊs îS Y}Z kS}gUÊN

```

Try it

Input is a string, output is an empty string for "truthy" or a non-empty string for "falsy". A version which specifically outputs "true" or "false" requires just an added flag. All test cases can be run here.

Explanation:

```
_ðZl)rÈhXÊs îS Y}Z kS}gUÊN
                         N # Starting with the input string as Z
_                    }gUÊ  # Repeat this process a number of times equal to its length:
 ð  )                      #  Find indices of this string:
  Zl                       #   The current length of Z
     rÈ         }Z         #  For each index Y apply this function to Z consecutively:
        XÊ                 #   Get the length of Z
          s                #   Turn it into a string
            îS             #   Replace each character with a space
       h       Y           #   Overwrite Z with that string starting at index Y
                   kS      #  Remove all spaces

```

This recursive alternative is a little longer, but I figured I would include it in case it has more room to golf.
> 1 votes

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


title: Union of Intervals

text:
# Question
Title: Union of Intervals
Given a list of intervals, perform the union of them, and reduce overlaps. That means, overlapping parts are reduced. (`[a, b] U [c, d] = [a, d]` if `b > c`) Assuming all a \< b in all intervals `[a, b]`. Implement as a function of a list of input intervals -\> list of output intervals. Shortest code wins. You cannot use any existing libraries.

Clarifications:

* Open and closed intervals are not distinguished.
* Intervals for real numbers, not integers. (`[2, 3], [4, 5] -> [2, 3], [4, 5]`)
* No need to sort output intervals
* The order if inputs do not matter
* Illegal inputs are only `[a, b]` where `b >= a`, it has nothing to do with the order of input intervals and the number of input intervals.
* You do not need to show an error message on undefined behaviors

Examples (with number lines)

```
 [2, 4], [7, 9] --> [2, 4], [7, 9]
   234
        789
-> 234  789

 [1, 5], [2, 10] --> [1, 10] (overlapping [2, 5] reduced)

   12345
    234567890
-> 1234567890
 [2, 4], [3, 6], [8, 9] -> [2, 6], [8, 9]
   234
    3456
         89
-> 23456 89

 [4, 2], [2, 2] -> (undefined behavior: against the assumption)

```

# Answer
> 2 votes
# GolfScript, 32

```
[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]

```
* Add 2 characters if you prefer a block, 4 if you prefer a named block.
* Input and output are array of pairs, e.g. `[[2 4] [3 5]]`
* Assumes that input is ordered by the first element.
* Compacts "adjacent" ranges (\[2 4\]\[5 6\] -\> \[2 6\])
* First GolfScript effort. Advice & rotten fruit appreciated.

Full test program:

```
[~](;2/[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]`

```

Example invocation:

```
ruby golfscript.rb intervals.gs <<EOF
3
2 4
3 6
8 9
EOF
# Expected output: [[2 6] [8 9]]

```

# Answer
> 4 votes
## Haskell (103)

I think, it is way too verbose for Haskell. Thanks to Hoa Long Tam for his sorting function.

```
m%(x:y)|x>m=m:x:y|2>1=x:m%y;m%_=[m]
(x:y)?l|x`elem`l=y?l|0<1=x:y?(x:l);a?_=a
a∪b=foldr(%)[](a++b)?[]

```

In Haskell, an intervall from `a` to `b` is denoted by `[a..b]`. My notation is very similar to the mathematical notation. Use it like this:

```
[a..b] ∪ [c..d] ∪ ... ∪ [y..z]

```

# Answer
> 3 votes
Ok, here's my 250 character crack at it.

```
void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}

```

The function takes an int array, and operates on it in-situ. The array is terminated by a 0, and the intervals may be given in any order.

Sample output:

```
input list: (7,9) (5,6) (1,4) (15,18) (13,16) (2,3) (8,11)
output list: (1,4) (5,6) (7,11) (13,18)

```

Sample program:

```
#include <stdio.h>

void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}

/*
void n(int a[])
{
    if(!a[2])return;
    if(a[2]<=a[1]) {
        if(a[1]<a[3])
            a[1]=a[3];
        int *b=a+2;
        while(*b=*(b+2))++b;
        n(a);
    }
    n(a+2);
}

void m(int a[])
{
    if(!a[2])return;
    if(a[0]>a[2]) {
        int s=a[0],t=a[1];
        a[0]=a[2];a[2]=s;
        a[1]=a[3];a[3]=t;
        m(a+2);m(a);n(a);
    }
    m(a+2);n(a+2);
}
*/

void p(int a[])
{
    if(!*a) {
        printf("\n");
        return;
    }
    printf("(%d,%d) ",a[0],a[1]);
    p(a+2);
}

int main (int argc, const char * argv[])
{
    // Code golf entry
    // Interval Merging

    int a[] = {7,9,5,6,1,4,15,18,13,16,2,3,8,11,0};
    printf( "input list: " ); p(a);
    m(a);
    printf( "output list: " ); p(a);

    return 0;
}

```

# Answer
> 2 votes
## Python, 100 chars

```
def f(L):R=sorted(set(p for p in sum(L,[])if 1-any(x<p<y for x,y in L)));return zip(R[::2],R[1::2])
print f([[2, 4], [7, 9]])
print f([[1, 5], [2, 10]])
print f([[3, 6], [2, 4], [8, 9]])
print f([[1, 5], [3, 5], [4, 5]])

```

generates

```
[(2, 4), (7, 9)]
[(1, 10)]
[(2, 6), (8, 9)]
[(1, 5)]

```

Takes all the endpoints of the intervals, removes any that are strictly inside another interval, uniquifies & sorts them, and pairs them up.

# Answer
> 2 votes
## Haskell, 55 characters

```
v(q@(a,b):p@(c,d):r)|c>b=q:v(p:r)|1<3=v((a,d):r);v x=x

```

If the input is unsorted, then 88 characters:

```
p@(a,b)§(q@(c,d):r)|b<c=p:q§r|a>d=q:p§r|1<3=(min a c,max b d)§r;p§_=[p]
u i=foldr(§)[]i

```

Test runs:

```
ghci> testAll v
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]
ghci> testAll u
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]

```

I'm assuming that "can't use any existing libraries" precludes importing `List` and calling `sort`. If that were legal, than the unsorted version would be only 71 characters.

# Answer
> 2 votes
## Scala, 272 characters

```
type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}

```

Usage:

```
object Intervals2 extends Application
{
    type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}

    print(f(List((1,2),(3,7),(4,10))))
}

```

Creates an array and inserts a 1 for every interval start and a -1 for every interval end. Then steps through the array adding the values to a counter outputting a start every time the counter steps from 0 to 1 and an end when it steps from 1 to 0. Probably unnecessarily complicated.

Output:

```
List((1,2), (3,10))

```

# Answer
> 1 votes
## Perl (146) (92) (90)

golfed down to 90 chars, creatively using the regex engine

```
sub u{map$h[$_]=1,@$_[0]..@$_[1]for@_;$w.=$_+0for@h;push@r,$-[0],$+[0]-1while$w=~/1+/g;@r}

```

usage example:

```
my @out1 = u([1, 5], [2, 10]); # (1,10)
my @out2 = u([2, 4], [3, 6], [8, 9]); # (2, 6, 8, 9)

```

let's explain this code a bit.

this subroutine receives an array of arrayrefs, each aref pointing to an array containing two elements, start and end of the interval: `([2, 4], [3, 6], [8, 9])`

for every aref, we generate an array of elements from first to last `($_->[0] .. $_->[1])`. then we use map to set elements of such indexes in @h to 1.

```
for (@_) {
    map {$h[$_] = 1} ($_->[0] .. $_->[1]);
}

```

after this, `@h` will contain either ones (for intervals) or undefs, depicted below as hyphens for clarity.

```
index: 0 1 2 3 4 5 6 7 8 9
@h:    - - 1 1 1 1 1 - 1 1

```

next we build a string from @h, adding 0 to replace undefs with something more useful (undef + 0 = 0).

`$w .= $_+0 for @h;`

$w contains `011111011` now.

it's time to abuse the regex engine a bit.

`push @r, ($-[0], $+[0]-1) while $w=~/1+/g;`

after successful matches, @- and @+ arrays contain respectively position of start and end of each match; 0th element is used for the entire match, first for $1, second for $2 and so on.

`$+[0]` actually contains the position of first non-matching char, so we have to substract one.

`@r` contains `(2, 6, 8, 9)` now.

`@r`

to make the sub return `@r`.

# Answer
> 1 votes
### Scala  305  279 chars without invocation:

```
type I=(Int,Int)
def l(p:I,q:I)=if(p._1<q._1)true else if(p._1>q._1)false else p._2<q._2
def r(l:List[I]):List[I]=l match{case x::y::z=>{if(y._1<=x._2&&y._2>x._2)(x._1,y._2)::r(z)else
if(y._1<=x._2&&y._2<=x._2)x::r(z)else
x::r(y::z)}case _=>l}
def c(v:List[I])=r(v.sortWith(l))

```

invocation:

```
val i=List((7,9),(5,6),(1,4),(15,18),(13,16),(2,3),(8,11))
c(i)
res0: List[(Int, Int)] = List((1,4), (5,6), (7,11), (13,18))

```

# Answer
> 1 votes
# Brachylog, 12 bytes

```
⟦₂ᵐcod~c~⟦₂ᵐ

```

Try it online!

A delightfully declarative solution, taking input as a list of lists through the input variable and outputting a list of lists through the output variable.

```
        ~⟦₂ᵐ    The output is a list of intervals, where each interval is a range in
      ~c        the smallest partition of
  ᵐ             each element of the input
⟦₂              converted to an inclusive range,
   c            concatenated,
    o           sorted,
     d          and deduplicated
        ~⟦₂ᵐ    for which each element of the partition is a range.

```

# Answer
> 1 votes
## Clojure, 138 bytes

```
#(let[S(set(apply mapcat range(apply map list %)))Q(sort S)](map list(for[s Q :when(not(S(dec s)))]s)(for[s(map inc Q):when(not(S s))]s)))

```

This shortens to **119 bytes** if the input is more flexible, namely a list of intervals' starting points AND a list of intervals' ending points:

```
#(let[S(set(mapcat range % %2))Q(sort S)](map list(for[s Q :when(not(S(dec s)))]s)(for[s(map inc Q):when(not(S s))]s)))

```

There has to be a better way.

# Answer
> 1 votes
# Japt, 18 bytes

This feels far too long. I/O as sorted, 2D array of intervals.

```
c_ròÃòÈaY ÉÃ®g[TJ]

```

Try it

# Answer
> 1 votes
# Jelly (fork), 11 bytes

```
r/€FṢQŒġ.ịⱮ

```

Try it online! or rather, don't

Outputs the ranges as `[b, a]` where \\$b \> a\\$ (so the example `[2, 4], [3, 6], [8, 9]` is output as `[6, 2], [9, 8]`)

## How it works

```
r/€FṢQŒġ.ịⱮ - Main link. Takes a list of pairs on the left
  €         - Over each pair:
r/          -   Reduce into a range
   FṢQ      - Flatten, sort and deduplicate
      Œġ    - Group adjacent consecutive elements
        .ịⱮ - Select the first and last from each group

```

# Answer
> 0 votes
# Perl 5 `-MList::Util=max -n`, 89 bytes

```
@r=/\S+/g;map{/ /;$`<=$r[1]?$r[1]=max@r,$'*1:(say"@r")|(@r=($`,$'))}sort{$a-$b}<>;say"@r"

```

Try it online!

# Answer
> 0 votes
# Ruby, 75 bytes

```
->a{a.map{[*_1.._2]}.reduce(:|).sort.slice_when{_2-_1>1}.map{|a,*,b|[a,b]}}

```

Attempt This Online!

# Answer
> 0 votes
# Mathematica, 18 bytes

```
List@@Interval@@#&

```

View it on Wolfram Cloud!

---
Tags: code-golf
---


title: Get the day of the year of a given date

text:
# Question
Title: Get the day of the year of a given date
**Challenge**

Given two positive integers \\$1 \le m \le 12\\$ and \\$1\le d \le 31\\$, representing a month and days into the month, output the amount of days that have passed since January 1st, on a non-leap year. You can assume that the number of days passed will always be constrained by the number of days in the month (so \\$m = 2, d = 31\\$ will never be an input)

This is so the shortest code in bytes wins.

**Examples**

For example, \\$m = 2, d = 11\\$ represents February 11th. This is the 42nd day of the year (31 days in January + 11 days), so the output is 42.

# Answer
> 16 votes
# Haskell, 27 bytes

```
m%d=div(275*m)9-30+d-mod 2m

```

Try it online!

This is a “closed-form” answer (in a C-like language it would be `275*m/9-30+d-2%m`).

# Answer
> 9 votes
# JavaScript (ES6),  ~~40 37~~  36 bytes

Expects `(day)(month)`.

```
d=>g=m=>--m?31-(4/m&2)+~m%9%2+g(m):d

```

Try it online!

### How?

This is a recursive function that computes the number of days in each full month (i.e. lower than \\$m\\$), sums them all together and finally adds \\$d\\$ on the last iteration.

We use `4 / m & 2` to distinguish between February and all other months:

* For January, `4 / 1 & 2` is `4 & 2`, which is \\$0\\$
* For February, `4 / 2 & 2` is `2 & 2`, which is \\$2\\$
* For \\$m\>2\\$, `4 / m & 2` is \\$0\\$ because \\$0\<4/m\<2\\$

We use `~m % 9 % 2` to subtract \\$1\\$ for months that do not have \\$31\\$ days:

```
    m |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |  10 |  11
   ~m |  -2 |  -3 |  -4 |  -5 |  -6 |  -7 |  -8 |  -9 | -10 | -11 | -12
mod 9 |  -2 |  -3 |  -4 |  -5 |  -6 |  -7 |  -8 |   0 |  -1 |  -2 |  -3
mod 2 |   0 |  -1 |   0 |  -1 |   0 |  -1 |   0 |   0 |  -1 |   0 |  -1

```

(This also works for December, but we never have to compute the total number of days in this month.)

# Answer
> 8 votes
# Gaia, 6 bytes

A dyadic function taking the month above the day. Gaia has a nice collection of date/time builtins.

```
(∂k<Σ+

```

Try it online!

```
(       # decrement the month
 ∂k     # push list [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] (builtin)
   <    # take the first month-1 elements from this list
    Σ   # sum them
     +  # add the day

```

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

```
m=>d=>--m*31+d-'003344555667'[m]

```

Try it online!

Thanks to A username for pro golf tips!

# Answer
> 7 votes
# JavaScript, 33 bytes

```
m=>d=>((m+9)%12*51+99)*.6%365+d|0

```

Try it online!

# Answer
> 6 votes
# C (gcc), <sup>~~47~~</sup> 27 bytes

```
f(d,m){m=275*m/9-30+d-2%m;}

```

Try it online!

Uses formula from Lynn's Haskell answer.

# Answer
> 5 votes
# Bash, 16

```
date -d$1/1 +%-j

```

Input is given on the command-line as slash-separated integers, with month first.

Try it online!

# Answer
> 5 votes
# Python 3, ~~60~~ ~~55~~ 51 bytes, 1-based month

`lambda` function that accepts the month (1-based) and the day.

*-5 bytes*: used a "31-days" default month, and the list s accounts for the cumulate (absolute) difference between the actual days of months and 31
*-4 bytes*: the list is removed from the function parameters, thanks to *@Hunaphu* and *@mic\_e*

```
lambda m,d,a=[3,0,3,2,3,2,3,3,2,3,2]:28*(m-1)+sum(a[:m-1])+d  # original version

lambda m,d,s=[0,0,3,3,4,4,5,5,5,6,6,7]:31*m-31-s[m-1]+d

lambda m,d:31*m-31-[0,0,3,3,4,4,5,5,5,6,6,7][m-1]+d

```

Try it online!

Explanation *(original version)*:

* `m,d`: input month and day
* `a[...]`: list of days to add to the "base" 28-day month, from january to novemeber, passed as optional argument
* `28*(m-1)`: the total number of days in the previous "28-days" months
* `+sum(a[:m-1])`: add the remaining days of the previous months (as difference actual days - 28)
* `+d`: add the days of the selected month

---

# Python 3, ~~56~~ ~~50~~ 46 bytes, 0-based month

*-4 bytes (compared to 1-based month number)*: if 0-based month number is allowed as input
*-6 bytes*: used the "31-days" approach
*-4 bytes*: the list is removed from the function parameters, thanks to *@Hunaphu* and *@mic\_e*

```
lambda m,d,a=[3,0,3,2,3,2,3,3,2,3,2]:28*(m)+sum(a[:m])+d  # original version

lambda m,d,s=[0,0,3,3,4,4,5,5,5,6,6,7]:31*m-s[m]+d

lambda m,d:31*m-[0,0,3,3,4,4,5,5,5,6,6,7][m]+d

```

# Answer
> 5 votes
## Excel formula, 18 Bytes

```
=DATE(1,A1,B1)-366

```
* Cell `A1` contains the input month.
* Cell `B1` contains the input day.

Saved 8 bytes from answer by Crissov by evaluating the offset as 366, then added 2 bytes by converting named ranges `m` and `d` into cell references.

If leap years were allowed, then it could be shortened to a single function `=DATE(0,A1,B1)`

# Answer
> 4 votes
# Japt, 16 bytes

Well, this ain't right :\ Normally Japt would be ruling the roost in a date based challenge but not this time, despite all the tricks I can muster. Which makes me seriously worried that, after 16 long months, I've lost my edge when it comes to golfing on me phone over a few pints down the boozer!

```
ÒÐBì)nÐUi¹z864e5

```

Try it

# Answer
> 4 votes
# Factor, 29 bytes

```
[ 1 -rot <date> day-of-year ]

```

Try it online!

* `1 -rot <date>` Create a timestamp from the year 1 and the two inputs. (1 is not a leap year according to Factor's calendar vocabulary.) This is the shortest way I know of to create a timestamp object from a month and day.
* `day-of-year` Factor has a builtin for this once you have a timestamp.

# Answer
> 2 votes
# Jelly, ~~16~~ 15 bytes

```
“LɓịNH’D+28⁸;ḣS

```

Try it online!

Takes \\$d\\$ then \\$m\\$ on the command line

```
“LɓịNH’D+28⁸;ḣS - Main link. Takes d on the left and m on the right
“LɓịNH’         - Compressed integer; 303232332323
       D        - Convert to digits; [3, 0, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3]
        +28     - Plus 28 to each; [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
           ⁸;   - Prepend d; [d, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
             ḣ  - Take the first m
              S - Sum

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 11 bytes

Full program. Prompts for `[month,day]`

```
1⎕DT⊂1900,⎕

```

Try it on TryAPL! ( is stdin, but is emulated with the variable  since TryAPL doesn't allow stdin)

prompt for `[month,day]`; `[2,11]`

`1900,` prepend `1900`; `[1900,2,11]`

enclose to represent as scalar time stamp; `[[1900,2,11]]`

`1⎕DT` convert DateTime to days since 1899-12-31; `42`

# Answer
> 2 votes
This works on my PowerShell 5 on my computer; I can't get it working on TIO:

## PowerShell 5, 97 bytes

```
function s($m,$d){1+(New-Timespan -st (Get-Date -day 1 -mo 1) -e (Get-Date -day $d -mo $m)).Days}

```

Call as `s 2 11` for the example date (month before day-of-month).

### *Golfed by @mazzy, 82 bytes*

# PowerShell, 82 bytes

```
param($m,$d)1+(New-Timespan -st (Date -day 1 -mo 1) -e (Date -day $d -mo $m)).Days

```

Try it online!

*The golfing relies on an alias or implementation of command (`Date`) that does not exist in a default Windows 10 installation of PowerShell 5. The TIO PowerShell is PowerShell 6 on Linux.*

# Answer
> 2 votes
# Red, 36 bytes

```
func[m d][pick to now reduce[d m]11]

```

Try it online!

# Answer
> 2 votes
# Vyxal `s`, 14 bytes

```
‹»HȦð9E»fẎ28+p

```

Try it Online! Port of @caird's Jelly solution

```
‹»HȦð9E»fẎ28+p
 »HȦð9E»          Push compressed integer 303232332323
        f         Convert to digits
‹        Ẏ        Slice [0:m-1]
          28+     Add 28 to each list element
             p    Prepend to the day of the month

```

`s` flag: Sums the top of the stack and outputs the sum.

# Answer
> 2 votes
# Vyxal, 17 bytes

```
»∇ė{»4τ28+¦0p?‹i+

```

Try it Online! Works now, and -2.

# Answer
> 2 votes
# Desmos, ~~90~~ ~~82~~ 59 bytes

```
f(m,d)=total([0,31,28,31,30,31,30,31,31,30,31,30][1...m])+d

```

*Saved 23 bytes 'cause I was so dumb... I've been trying to do some clever list manipulation to save bytes, but it never came to my mind to just put the list itself.*

### Very Brief Explanation:

`[0,31,28,31,30,31,30,31,31,30,31,30]`: The number of days in each month(excluding December), with an extra `0` element at the beginning.

`total( ... [1...m])+d`: Sum of the first `m` elements of the list explained above, then add `d`.

Try It On Desmos!

Try It On Desmos! - Prettified

## Solution using Lynn's "closed form" formula, 34 bytes

```
f(m,d)=floor(275m/9)-30+d-mod(2,m)

```

# Answer
> 2 votes
# Pip, 24 bytes

```
b+$+A*""@<Da

```

The code contains unprintable characters. Here's a hexdump:

```
00000000: 622b 242b 412a 221f 1c1f 1e1f 1e1f 1f1e  b+$+A*".........
00000010: 1f1e 1f22 403c 4461                      ..."@<Da

```

If you put that into `xxd -r`, save the results in a file, and then run the file as Pip code with the two inputs as command-line arguments, you can try it here! Or, here's a 25-byte version in Pip Classic: Try it online!

### Explanation

```
                          a (month) and b (day) are command-line arguments
      ""      String containing characters with codes 31, 28, 31, 30, etc.
    A*                    Get the ASCII code of each character
                      Da  Decrement a
                    @<    The first (^ that many) items of the list of charcodes
  $+                      Sum
b+                        Add b

```

# Answer
> 2 votes
# , 57 bytes

**(my own attempt)**

```
function(m,d){F[c(8:14,2:8)]=30:31;F[3]=28;sum(F[1:m],d)}

```

Try it online!

An alternative  solution to pajonk's answer, without using any date built-ins.

---

# , 34 bytes

**(port of Lynn's answer)**

```
function(m,d)(275*m)%/%9-30+d-2%%m

```

Try it online!

# Answer
> 2 votes
# K (ngn/k), ~~25~~ 20 bytes

**Solution:**

```
{+/y,x#28+4\3390446}

```

Try it online!

**Explanation:**

*Assumes months are 0-indexed!*

Naive approach, there are likely better ones out there.

```
{+/y,x#28+4\3390446} / the solution
{                  } / lambda taking implicit x, y args
          4\3390446  / creates 3 0 3 2 3 2 3 3 2 3 2 from base-4
       28+           / add 28 to each item (vectorised)
     x#              / take 'month' items from this list (January = 0)
   y,                / prepend 'days'
 +/                  / sum up

```

**Edits:**

* **-5 bytes**; using deltas against 28 instead of days-per-month

**Extra:**

* **+2 bytes** for 1-indexed month `{+/y,x#0,28+4\3390446}`

# Answer
> 1 votes
# MATL, 9 bytes

```
14Liq:)hs

```

**Try it online!**

### Explanation

```
14L % Push [31 28 31 30 31 30 31 31 30 31 30 31]: month lengths (predefined literal)
i   % Input: month, m
q   % Subtract 1
:   % Inclusive range from 1 to that
)   % Index into the array of month lengths: gives its first m-1 terms
h   % Implicit input: day, d. Concatenate with previous array
s   % Sum of array. Implicit display

```

# Answer
> 1 votes
# Charcoal, 20 bytes

```
Ｉ⁺↨Ｅ…”)“M⟧₂”⊖Ｎ⁻³¹ι¹Ｎ

```

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

```
     ”)“M⟧₂”            Compressed string `03010100101`
    …                    Truncated to length
             Ｎ          Month as an integer
            ⊖           Decremented
   Ｅ                     Map over characters
                ³¹       Literal integer `31`
               ⁻         Subtract
                  ι      Current value
  ↨                ¹     Take the sum
 ⁺                       Plus
                    Ｎ    Day as an integer
Ｉ                        Cast to string
                         Implicitly print

```

Base 1 conversion is used in case the list is empty (i.e. January).

# Answer
> 1 votes
# Perl 5 (`-p`), 36 bytes

```
/ /;$_=strftime"%-j",(0)x3,$',$`-1,0

```

Try it online!

# Answer
> 1 votes
# , 40 bytes

```
function(m,d)format(ISOdate(1,m,d),"%j")

```

Try it online!

Using buildins, returning as string.

---

Returning as a number (also using buildins):

### , 44 bytes

```
function(m,d)as.POSIXlt(ISOdate(1,m,d))$yd+1

```

Try it online!

# Answer
> 1 votes
# PHP, 42 bytes

```
fn($m,$d)=>date(z,mktime(0,0,0,$m,$d,1))+1

```

Try it online!

Pretty much builtin. The year parameter could be omitted, but the current year would then be used. To avoid a leap year `1` was used (it actually corresponds to 2001 according to the doc). `1` is added because the result is zero indexed.

This is satisfying, the byte count is The Answer, which is also the answer to the test case!

1 byte shorter but less satisfying:

# PHP, 41 bytes

```
fn($m,$d)=>date(z,strtotime("1-$m-$d"))+1

```

Try it online!

# Answer
> 1 votes
## Excel, ~~30~~ 24 bytes

* `=DATE(1,m,d)-DATE(1,1,0)` \[24\]
* `=DAYS(DATE(1,m,d),DATE(1,1,0))` \[30\]

Edit: I used the year 2001 before, because I do not trust Excel with dates before 1905.

# Answer
> 1 votes
# Python 3, 41 bytes

```
lambda m,d:31*~-m-(539785049600>>3*m&7)+d

```

Try it online!

# Python 3, 41 chars, 50 bytes

```
lambda m,d:d+ord('0\x00>v´ðĮŪƨǦȢɠʜ'[m])/2

```

Try it online!

# Answer
> 1 votes
# Mathematica, 30 bytes

```
{1}~DateDifference~{1,#,#2+1}&

```

Try it here!

Returns as a quantity object:

Using the `DateDifference` builtin and the fact that `{y}` is treated as January 1st on year `y`. I thought of `{1}~DateDifference~{##}&` at first, but sadly `DateDifference` starts from 0 days instead of 1.

# Answer
> 0 votes
# Java, 141 bytes

```
int d(int d,int m){for(int i=1;i<m;i++){switch(i){case(2):d+=28;break;case(4):case(6):case(9):case(11):d+=30;break;default:d+=31;}}return d;}

```

# Answer
> 0 votes
# Perl 5, 35 bytes

Just a translation of the Haskell answer from @Lynn

```
$_=int 275*$F[0]/9-30+$F[1]-2%$F[0]

```

Try it online!

# Answer
> 0 votes
# TI-Basic, 12 bytes

```
dbd(101.1,Ans+.1

```

Takes input in `Ans` as an integer in the format DDMM (for example, November 23 is 2311).

---
Tags: code-golf, date
---


title: Implement Perceptron

text:
# Question
Title: Implement Perceptron
*There was a previous perceptron question but it was closed. Also it required a lot of extra stuff that's not normally part of the perception algorithm like I know it. This question will be much simpler*

The Perceptron is a extremely basic classification algorithm. While it still has some limited use it's been mostly overtaken by gradient descent based algorithms that can match much more complex functions. Still its fun and easy to implement, and is the foundation for many more complex algorithms.

The dot product is defined as follows:

$$(A\_0, A\_1, \dots, A\_n) \cdot (B\_0, B\_1, \ldots, B\_n) = A\_0 B\_0 + A\_1 B\_1 + \ldots + A\_n B\_n$$

## Algorithm Description

Percepron can classify vectors into 2 categories, simply by taking the dot product with some vector. If this is positive, you are in category A, if negative, then not.

The algorithm to compute this vector works as follow:

```
set the initial vector to <0, 0, ..., 0>

while not every data point is classified correctly:
    let p be the first incorrectly classified point
    if the dot product is positive or zero but it should be negative:
        add p to the vector
    if the dot product is negative or zero but it should be positive:
        subtract p from the vector

```

Sample Implementation

Among the many weaknesses of this algorithm is that it runs forever if no solution exists, that it can only classify categories separated by a straight plane, and that that plane must pass through the origin.

You *do not* need to follow this exact algorithm as long as you can guarantee a correct vector in all the cases this algorithm would.

## The task

Take as input a list of positive tuples and a list of negative tuples. All tuples will all be the same length, and can contain any real number representable by a 32 bit float. Then output a vector that perfectly classifies them.

This is . Shortest answer in each language wins.

You may also take input as a single list of `((x0, ..., xn), category)` tuples. You may take the length of the tuples as a extra input if desired.

You may assume a solution exists for the input given.

The tuples in the input will *always* have 1 as their last value, representing bias.

## Test Cases

Note: There are many vectors that can classify the data, any of them would be a valid result. Your code may still be correct if it produces very different values from this.

```
[
    {
        "positive": [[1,0, 1]],
        "negative": [[0,1,1]],
        "result": [1,-1,0]
    },
    {
        "positive": [[12.12958530911699, 71.71547437602891, 17.615042787292396, 1.0], [22.894324259518754, 7.747740085241489, -16.379692578583914, 1.0], [-77.19508767650036, 26.391457800328325, -34.128081828012256, 1.0], [96.46713849700853, 8.223882871718914, 95.59810235088628, 1.0], [95.47166665625838, 36.07081574287895, 20.660512993212635, 1.0]],
        "negative": [[-41.92974660410673, -42.941790456679854, 21.407959882725905, 1.0], [-99.40397441836177, 26.174868779681844, 56.51788064358769, 1.0], [34.482060088467364, -96.36102804944655, 1.5810491199434153, 1.0], [-43.06995918058733, -65.8456447109237, -99.04122951157478, 1.0], [7.7462310407688335, -10.894130800401939, 77.86204331190197, 1.0], [44.47180923569721, -93.53543659179937, 6.715910740415197, 1.0], [71.16273132699712, -80.16856861976358, 48.05726245445331, 1.0]],
        "result": [78.64936114023355, 237.2180619264857, -42.5708443640236, 10.0]
    },
    {
        "positive": [[19.891204296811196, 10.95935510782877, 25.985095341720097, -39.87626202198886, 13.054847014298801, -0.8134570474536389, -54.24129976411458, 1], [-16.576268085926657, 4.5002152868197385, 6.698984554370156, -49.780067496976976, 3.9392362908185703, -11.457246915347255, -3.84485029930714, 1], [-6.424223219895211, -67.86203596702003, 0.6670934629448197, -67.56926034741468, -34.71326779844648, -19.40781793399796, -38.93217338522913, 1], [-55.06122442753092, -46.49216596542017, -28.522294222446035, -30.89448675440849, 25.85546157303159, -28.753484757197114, -67.37074950075419, 1], [12.753734640663126, -42.688681313433065, -37.073894323478854, -22.678023584770216, -12.23724620287598, 4.467063264393019, -28.749388172615724, 1], [-25.894264060028036, -4.384289071814308, 25.545930397049247, -53.005653882689884, -17.7501576060518, -19.66585588898353, -33.29502103119091, 1], [-32.104636572417846, -61.44888846917201, -41.89407929533455, 20.32097494020971, 8.703788581939762, 12.493571659393822, -35.255247777162495, 1], [24.15536843650885, -25.610207061176325, 16.08185788882571, -34.478497500787185, -18.915615320612233, 24.782283056323323, -24.770226555932894, 1], [6.765979248514711, -1.6248990886835486, 19.091220818794667, 14.715692506417057, 7.953257187955259, 12.722665623234263, 14.914783085366352, 1]],
        "negative": [[-2.7270414497182855, 8.676310678740919, -72.98709301742022, -7.70910010724549, 10.477333664984855, -17.506198964389014, 18.233248667960424, 1], [-43.3010158973477, -20.807005424922295, -77.5083019019948, 16.126838313178908, -40.490353240152864, -11.81562605632648, -8.902497984641357, 1], [-31.71159835398403, -14.73301578999785, 13.902967116929815, -21.834371921202447, -40.86878402777407, 6.742152812766307, -16.213431636063206, 1], [-66.57071699396832, -2.6930106603672783, 24.856421108284607, 26.02555433076685, -45.195502153813656, -60.583102046347044, 18.622821621702442, 1], [-47.07567023723187, 8.668277396085415, -55.64099369519978, -24.3651014072761, -77.50500543887348, -29.67008512028478, -27.6004244984169, 1], [16.02465948636585, -64.28947887797132, -18.663992818184852, 11.001922130635734, -65.96111461946506, -70.07973218635979, -41.525576739268594, 1], [-33.6451045267202, -8.496296235717935, -20.129571219612984, 9.152732883489037, 10.242775447179753, -61.865587395289765, -32.78507965995476, 1], [-59.32306321222039, 12.522731642519034, 22.026994802405454, -18.062615366497297, -8.713470639955815, -44.04186584475624, 27.84951438666559, 1], [15.30669132488326, 4.865567302204951, -2.782248675090557, 24.252984759612147, -31.883249650258065, 0.5697927616565579, 22.431436239098076, 1], [1.0357436812954433, -32.44164907799862, 13.942522314820707, 16.30751529733827, -12.905194523861582, -22.446463524560656, 12.651474924205772, 1], [-56.03563699153419, 12.024854226295957, -39.90028407341309, 26.9268535257967, 23.808505964904285, 0.34968582027003947, -29.362006601750707, 1], [-85.14402438073334, -15.501824729148709, -63.38128746811267, -42.15734961052637, -4.1615796887736565, -7.25189532732314, -27.223088213381402, 1], [2.7529807581849184, -23.668062096200217, -9.028343561579462, 2.5495275958544283, 15.88901518194605, -59.28742737700396, 25.402434735936126, 1], [-49.514159298902705, -24.01610873489301, 19.949647054069544, -41.1158129509881, -53.808681913915706, -11.175092994514387, 16.753648710377945, 1], [13.052884356788013, -29.298799492103925, -11.675938518634197, -11.229831992030299, -82.661335125941, 0.4488670991709114, 15.5168860373427, 1], [-10.923814330565236, -44.964063927868544, -38.9909686186201, 15.763631832856007, -44.00734436715622, -54.69686019599016, -52.81999206838163, 1], [-43.815947420234714, 19.90446963235277, 4.773988726751696, -47.12560089860667, 13.028054180292472, -39.81105100874389, 16.639915018971934, 1], [-60.88215048423795, 18.63815015768826, 27.157195120177462, -31.93335885907136, -6.562377024790365, 20.3179674395969, 9.210423673803817, 1], [-20.199358866077134, -50.594347683405196, -65.49273675929138, 19.37323156150201, -13.877303200574588, 19.536120330891066, -17.908737459942998, 1], [-11.03148069515855, 18.400073052625856, -65.34212863735566, -5.32988003172234, 0.7010084382675785, 26.36787095325562, 22.718825279142763, 1], [-30.028696420764177, -20.038640467728513, -47.66006964061526, 1.669739637216125, 3.3366149257696947, -20.495524621115493, 11.79886970131642, 1]],
        "result": [53.402165827630355, -96.34048665666451, 46.75018310196545, -58.648563298215464, 167.65173848467344, 54.84963473487821, -66.47771531555354, 6.0]
    }
]

```

# Answer
> 6 votes
# JavaScript (ES6), 102 bytes

*-1 by @l4m2*

Expects `[ positive, negative ]`.

```
A=>(g=V=>A.some((a,j)=>a.some(v=>!(q=v.map((c,i)=>(x=V[c*=1-2*j,i]||0,t+=c*x,c+x),t=0))>=t))?g(q):V)``

```

Try it online!

### Commented

```
A => (                      // A = [ positive, negative ]
  g = V =>                  // g is a recursive function taking the vector V
  A.some((a, j) =>          // for each array a[] at position j in A[]:
    a.some(v => !(          //   for each vector v[] in a[]:
      q = v.map((c, i) =>   //     for each value c at position i in v[]:
        (                   //
          x = V[            //       set x to V[i], or 0 by default
            c *= 1 - 2 * j, //       multiply c by the expected sign
            i               //       (+1 if j = 0, -1 if j = 1)
          ] || 0,           //
          t += c * x,       //       add c * x to t
          c + x             //       set q[i] = c + x
        ),                  //
        t = 0               //       start with t = 0
      )) >= t               //     end of map(); trigger both some() if t <= 0
    )                       //   end of inner some()
  )                         // end of outer some()
  ?                         // if truthy:
    g(q)                    //   recursive call with V = q
  :                         // else:
    V                       //   stop the recursion and return V
)``                         // initial call to g with a dummy vector

```

# Answer
> 5 votes
# 05AB1E, ~~38~~ ~~35~~ 34 bytes

```
¬[©¹.Δ®*O(d}DÄi².Δ®*Od}DÄi®qës\-ë+

```

Naive port of the example implementation. Takes two separated lists of lists as inputs, the first being the `positive` list and the second the `negative`.

Try it online or verify all test cases.

**Explanation:**

```
н                # Get the first tuple of the first (implicit) positive input-list
[                # Start an infinite loop:
 ©               #  Store the current vector-list in variable `®` (without popping)
  ¹              #  Push the first positive input-list
   .Δ            #  Pop and find the first inner list which is truthy for:
                 #  (or -1 if none are truthy)
     ®           #   Push the vector-list
      *          #   Multiply the values in the two lists at the same positions
       O         #   Sum this list together
        (        #   Negate this sum
         d       #   And check if this -sum is non-negative (>=0)
                 #   (the `(d` is basically a sum<=0 check)
    }D           #  Duplicate the result of the find-first
      Äi         #  If it's -1 (thus none were found):
        ².Δ®*Od} #   Do another find-first on the second negative input-list,
                 #   but this time with sum>=0 check instead of sum<=0
     DÄi         #   Again similar; if it's -1 (thus none were found):
        ®        #    Push the vector-list
         q       #    And stop the program
                 #    (after which this vector-list is output implicitly as result)
       ë         #   Else (a result is found for the negative list):
        s\       #    Discard the positive result from the stack
          -      #    And subtract the values of the negative result from the vector-
                 #    list at the same positions
       ë         #  Else (a result is found for the positive list):
        +        #   Add the values of the positive result and the vector-list together
                 #   at the same positions

```

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

```
0~LinearOptimization~{a=#~Join~-#2,-1^Tr/@a}&

```

Try it online!

# Answer
> 4 votes
# Charcoal, ~~41~~ 39 bytes

```
≔⁺ＡＥＡ±ιθ≔§θ⁰ηＷΦθ¬›ΣＥκ×μ§ην⁰ＵＭη⁺κ§§ι⁰λＩη

```

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

```
≔⁺ＡＥＡ±ιθ

```

Concatenate the two lists of input vectors but negate the second one.

```
≔§θ⁰η

```

Edit: Saved 2 bytes by stealing @KevinCruijssen's trick of using the first input vector as the initial output vector. (This works because a vector of all zeros incorrectly classifies all of the input vectors so the first step is to add the first input vector to the vector of all zeros.)

```
ＷΦθ¬›ΣＥκ×μ§ην⁰

```

While the list of input vectors that do not have positive dot products with the output vector is not empty...

```
ＵＭη⁺κ§§ι⁰λ

```

... add the first such vector to the output vector.

```
Ｉη

```

Output the final vector.

~~34~~ 33 bytes using the newer version of Charcoal on ATO:

```
≔⁺Ａ±Ａθ≔§θ⁰ηＷΦθ¬›Σ×κη⁰ＵＭη⁺κ§§ι⁰λＩη

```

Attempt This Online! Link is to verbose version of code. Explanation: Saved 2 bytes because Negate fully vectorises. ~~Saved 1 byte because Times fully vectorises.~~ Saved 4 bytes because Times can pairwise multiply vectors.

---
Tags: code-golf, statistics, floating-point
---


title: Farigiraf my Girafarig

text:
# Question
Title: Farigiraf my Girafarig
A palindrome is a word that is its own reverse. I will define the left palindromic root of a word as the shortest prefix of the word for which the shortest possible palindrome that begins with that prefix is the original word. So the left palindromic root of `racecar` is `race` and the left palindromic root of `ABBA` is `ABB`.

The second case may not seem obvious at first, so consider this table:

```
Prefix | Shortest palindrome with same prefix
       |
""     | ""
"A"    | "A"
"AB"   | "ABA"
"ABB"  | "ABBA"
"ABBA" | "ABBA"

```

Since the shortest prefix which maps to `ABBA` is `ABB`, it is the left palindromic root of `ABBA`.

The process of converting from a prefix to the minimum palindrome is also called the left palindromic closure, as can be found in this related challenge.

Write the shortest code that, given a palindrome as input, returns the shortest palindrome that begins with the reverse of the left palindromic root of the input. Equivalently, find the left palindromic closure of the reverse of the left palindromic root of the input.

You may assume the input is part of some arbitrary alphabet, such as lower-case ASCII or positive integers, as long as it does not trivialise the challenge.

## Test cases

```
girafarig -> farigiraf
farigiraf -> girafarig
racecar -> ecarace
ABBA -> BBABB
 ->
a -> a
aa ->  aa
aba -> bab
aaa -> aaa
1233321 -> 333212333
11211 -> 2112
ABABA -> BABAB
CBABCCBABC -> CCBABCC

```

You can make additional cases using this program.

# Answer
# Vyxal, ~~12~~ ~~10~~ 9 bytes

*-1 byte thanks to Jonathan Allan!*

```
¦:R⋎ḟꜝȯḂ⋎

```

Test suite

## Explanation

```
¦         # prefixes of input
 :        # duplicate
  R       # reverse of each element
   ⋎      # merge join (vectorises)
          # - combines the strings on their longest common
          #   suffix and prefix respectively
    ḟ     # find the first index of the original input
     ꜝ    # bitwise not
      ȯ   # get this last number of characters in the input
       Ḃ  # push the reverse
        ⋎ # merge join

```
> 11 votes

# Answer
# Jelly, 23 bytes

No built-in palindromising :(

```
;ⱮṚḊ$ƤŒḂƇḢȯ
ŻḊƤÇ⁼¥Ƈ⁸ḢṚÇ

```

A monadic Link that accepts a list of characters and yields a list of characters.

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

### How?

```
;ⱮṚḊ$ƤŒḂƇḢȯ - Helper Link: get shortest palindrome: left palindromic prefix, S
     Ƥ      - for prefixes (of S):
    $       -   last two links as a monad:
  Ṛ         -     reverse
   Ḋ        -     dequeue
 Ɱ          - (S) map (that) with:
;           -   concatenate
        Ƈ   - keep those for which:
      ŒḂ    -   is palindrome?
         Ḣ  - head (Note: when S='' we head [] and get zero)
          ȯ - (that) logical OR (S) (deal with that zero)

ŻḊƤÇ⁼¥Ƈ⁸ḢṚÇ - Main Link: palindrome, P
Ż           - prepend a zero
  Ƥ         - for prefixes (of that):
 Ḋ          -   dequeue
      Ƈ     - keep those for which:
     ¥ ⁸    -   last two links as a monad - f(X=that, P):
   Ç        -     call Helper (X)
    ⁼       -     equals (P)?
        Ḣ   - head
         Ṛ  - reverse
          Ç - call Helper

```
> 7 votes

# Answer
# JavaScript (ES6), 113 bytes

Essentially a port of the Python program provided by the OP. Although I did find shorter methods, I've yet to find a *working* shorter method.

```
s=>[...s].some(c=>(F=S=>[...S].some(c=>[p+R==(Q=S+q)][q=c+q,p+=c,0],p=q='')&&Q)(S+=c,R=c+R)==s,R=S='')?F(R,R=S):s

```

Try it online!
> 6 votes

# Answer
# Japt, 33 bytes

```

U{ÊÆê jUÊXÃfêS Ì
©å+ æ_gV ¥UÃÔgV

```

Try it

Try all test cases

Explanation:

```
/n               # Store input as U

U{ÊÆê jUÊXÃfêS Ì # Define a function V which calculates left palindromic closure

U{               # Start defining a function with one input named U
  Ê              # Get the length of U
   Æ      Ã      # For each number X in the range [0...length):
    ê            #  U palindromized
      j  X       #  Remove X characters
       UÊ        #  Starting at index "length of U"
           fêS   # Keep the ones which are palindromes
               Ì # Return the last (shortest) one

©å+ æ_gV ¥UÃÔgV  # Main program

©                # Return U if it is an empty string
 å+              # Otherwise get the prefixes of U
    æ_     Ã     # Find the first (shortest) one where:
      gV         #  The left palindromic closure
         ¥U      #  Is U
            Ô    # Reverse it
             gV  # Return its left palindromic closure

```
> 5 votes

# Answer
# Retina, ~~102~~ 90 bytes

```
L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$&$' $' $^$`
0G`( .*)\1
r`((?(2)$)(?<-2>\2)*.?(.)*) .*
$1$^$`

```

Try it online! Link includes test cases. Input cannot contain spaces. Explanation:

```
L$vr`(?(1)$)(?<-1>\1)*.?(.)*

```

Find the longest palindromic suffix of each prefix of the input.

```
$&$' $' $^$`

```

For each match, make a list of the match and its suffix, another copy of the suffix and the reversed prefix. We'll check that the latter two are the same below, after which we know that the match and its suffix is the same as the reverse of the match with its prefix.

```
0G`( .*)\1

```

Keep only the result of the match with the shortest prefix that equals its suffix. This means that the left palindromic closure of the match with its prefix is the original input, but also it means that the match and its suffix is the reverse of the match with its prefix, thus avoiding manually reversing it.

```
r`((?(2)$)(?<-2>\2)*.?(.)*) .*

```

Find the longest palindromic suffix of the reversed prefix.

```
$1$^$`

```

Outputs its palindromic closure and delete the suffix and reversed prefix of the match.

Instead of taking the left palindromic closure of the reverse of the left palindromic root, it's also possible to take the right palindromic closure of the left palindromic root for the same byte count:

```
L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$`$& $' $^$`
0L$`(.*)( .*)\2
$1
^(.)*.?(?<-1>\1)*(?(1)^)
$^$=

```

Try it online! Link includes test cases. Input cannot contain spaces. Explanation:

```
L$vr`(?(1)$)(?<-1>\1)*.?(.)*
$`$& $' $^$`

```

As above, but directly taking the match with its prefix instead of the match and its suffix.

```
0L$`(.*)( .*)\2
$1

```

As above, but removing the suffix and reversed prefix.

```
^(.)*.?(?<-1>\1)*(?(1)^)
$^$=

```

Output the right palindromic closure by replacing the longest palindromic prefix with the reverse of the whole value.
> 4 votes

# Answer
# 05AB1E, ~~30~~ ~~23~~ 22 bytes

```
ηεÂ‚εη€¨íyì.ΔÂQ]ʒнQ}нθ

```

Iterative port of the example implementation.

Try it online or verify all test cases.

**Explanation:**

```
η            # Get the prefixes of the (implicit) input-string
 ε           # Map over each prefix:
  Â          #  Bifurcate it; short for Duplicate & Reverse copy
   ‚         #  Pair the two together
    ε        #  Map over this pair:
     η       #   Get the prefixes of the current string
      €¨     #   Remove the last character from each prefix
        í    #   Reverse each
         yì  #   Prepend the current string to each
     .Δ      #   Find the first that's truthy for:
       ÂQ    #    Check if it's a palindrome:
       Â     #     Bifurcate; short for Duplicate & Reverse copy
        Q    #     Check if the two strings are the same, thus a palindrome
 ]           # Close the find_first and nested maps
  ʒ  }н      # Find the first pair that's truthy for†:
   н         #  Where the first palindrome in the pair
    Q        #  Equals the (implicit) input-string
       θ     # Only leave the last/second palindrome of the found result-pair
             # (which is output implicitly as result)

```

NOTE: The empty input `""` perhaps requires an additional explanation for the execution path it follows:

1. `η` on an empty string becomes `[]`, so it won't execute the nested maps `εÂ‚εη€¨íyì.ΔÂQ]` and remains `[]` after it.
2. It also won't enter the filter `ʒнQ}`, so again remains `[]`.
3. `н` on an empty list will result in an empty string.
4. `θ` on an empty string is basically a no-op.

† If I'd used `.ΔнQ}` ('find first' builtin) instead of `ʒнQ}н` (filter + 'keep first' builtins), which I initially had when I was working on golfing my program, it would have resulted in `-1` for the empty list `[]`, incorrectly giving an output of `1` after the 'keep last' builtin `θ`.
> 4 votes

# Answer
# Charcoal, 48 bytes

```
∨⌊ΦＥθ…θ⊕κ⁼⊗⊕κＬ⁺θ⊟ΦＥι…⮌ι⊕μ⁼λ⮌λω‖ＯＯ←Ｌ⊟ΦＥ⊕ⅈ…ＫＡκ⁼ι⮌ι

```

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

```
∨⌊ΦＥθ…θ⊕κ⁼⊗⊕κＬ⁺θ⊟ΦＥι…⮌ι⊕μ⁼λ⮌λω

```

Output the shortest prefix whose palindromic closure equals the input to the canvas. This is calculated as the length of longest palindromic suffix of the prefix plus the length of the input equals twice the length of the prefix.

```
‖ＯＯ←Ｌ⊟ΦＥ⊕ⅈ…ＫＡκ⁼ι⮌ι

```

Calculate the length of the longest palindromic prefix of the prefix and reflect the canvas to the left with that amount of overlap, thus generating its right palindromic closure.
> 2 votes

---
Tags: code-golf, palindrome
---


title: Palindromic Powers

text:
# Question
Title: Palindromic Powers
## Powers

We define an `important power` as a number that can be represented as \\$ x^y \\$ where \\$ x ≥ 2 \\$ and \\$ y ≥ 2 \\$.

## Palindrome

We define an `important palindrome` as a number that is the same written forwards and backward, and is greater than `10`. Thus, the last digit must not be `0`.

## Palindromic Power

We define a `Palindromic Power` as a number that is both an `important palindrome` and `important power`.

## Example

My reputation when I first drafted this question was `343`, which was an `important power` as \\$ 343 = 7^3 \\$. It is also an `important palindrome`. Thus it is a `palindromic power`. (Interestingly, the number of badges I have when I first drafted this question was `7`).

## Your Challenge

Given an integer \\$ n \\$, print all `palindromic powers` that are less than (and not equal to) \\$ n \\$.

## Example Program

Your program should produce the same output as this program. The exact order of your answer does not matter

```
from math import log

def is_power(n, base):
    return not n%base and is_power(int(n//base), base)

def is_important_power(n):
    for base in range(2, int(n**0.5) + 1):
        if is_power(n, base):
            return True
    return False

def is_important_palindrome(n):
    s = str(n)
    return s == s[::-1] and n>10

def is_palindromic_power(n):
    return is_important_power(n) and is_important_palindrome(n)

def main(number):
    final = []
    for i in range(1, number):
        if is_palindromic_power(i):
            final.append(i)
    return final

```

These are the palindromic powers under `1000000`:

```
121
343
484
676
1331
10201
12321
14641
40804
44944
69696
94249
698896

```

## Input

You may assume the input is under `100000000`.

## Scoring

This is .

# Answer
> 11 votes
# Desmos, ~~177~~ 175 bytes

```
T->min(T+1,n),o->L[L>9]
n=\ans_0
T=0
k=10^{[floor(log(T+0^T))...0]}
L=join(o,[T][[0^{n-T}+∏_{A=2}^{T-1}sign(mod(log_AT,1))]=-sign(total(k[1]/kmod(floor(T/k),10))-T)^2])
o=[]

```

This was really fun to puzzle out and solve in Desmos! Surprisingly, the part to check for an important palindrome is longer than the part to check for an important power.

Might be prone to floating point errors because of the usage of `log`, but any attempt to fix this will most likely cost more bytes, so I will just leave it like this for now.

Output is shown in the `o` variable. More info on I/O in the graph links below.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 8 votes
# 05AB1E, 11 bytes

```
<TŸʒÓ¿≠yÂQ&

```

Try it online!

Before Kevin wakes up and outgolfs me. Port of Jelly.

## How?

```
<TŸʒÓ¿≠yÂQ&
<            # Decrement (implicit) input
 T           # Push 10
  Ÿ          # Pop top two values of the stack and push inclusive range
   ʒ         # Filter keep for n:
    Ó        # Get the exponents of the prime factorization of n
     ¿≠      # Is the GCD of the exponents not one?...
          &  # ...and...
       yÂQ   # Is y a palindrome?

```

# Answer
> 6 votes
# Jelly, 13 bytes

```
’⁵rŒḂƇÆEg/’ƊƇ

```

Try it online!

-1 byte thanks to Jonathan Allan!

In order for some \\$k = p\_1^{e\_1}p\_2^{e\_2}\cdots p\_i^{e\_i}\\$ to be a perfect power (for primes \\$p\_1, p\_2, \dots\\$), we must have that \\$\gcd(e\_1, e\_2, \dots, e\_i) \> 1\\$.

## How it works

```
’⁵rŒḂƇÆEg/’ƊƇ - Main link. Takes n on the left
’             - Decrement
 ⁵r           - Range from 10 to n-1
     Ƈ        - Keep those that are:
   ŒḂ         -   Palindromic
           ƊƇ - Keep those that are non-zero after:
      ÆE      -   Prime exponents
        g/    -   Reduce by GCD
          ’   -   Decremented

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), 60 bytes

```
Select[h=Range[#-1],(h[[a#]]=a=h[[#]])<#>9&&PalindromeQ@#&]&

```

Try it online!

```
Select[  Range[#-1],                                      ] pick numbers in the range where:
       h=           (h[[a#]]=a=h[[#]])                        (if x=a^b, h[[x]]=a)
                                      <#                      an important power
                                       #>9&&PalindromeQ@#     and an important palindrome

```

# Answer
> 4 votes
# Factor \+ `math.primes.factors project-euler.common`, ~~101~~ 102 bytes

```
[ iota 10 short tail [ palindrome? ] filter [ group-factors values 0 [ gcd nip ] reduce 1 > ] filter ]

```

Try it online!

This is a port of caird's Jelly answer. I toyed with some brute force solutions but they came out a little longer.

* `iota 10 short tail` Shortest way (I think) to create an exclusive range from 10 to the input that is empty if the input is less than 11.
* `[ palindrome? ] filter` Get the palindromes within the range.
* `[ ... ] filter` Get the perfect powers within the palindromes.
* `group-factors values` Get the exponents of the prime factorization.
* `0 [ gcd nip ] reduce` Take the GCD of a sequence.
* `1 >` Is it greater than 1?

Note that `[ ... ] filter [ ... ] filter` is shorter than any kind of boolean and logic that's possible in Factor, as far as I know. Compare these simple examples:

* `[ odd? ] filter [ 10 > ] filter`
* `[ dup odd? swap 10 > and ] filter`
* `[| n | n odd? n 10 > and ] filter`
* `[ { [ odd? ] [ 10 > ] } && ] filter` (short-circuiting \[starts to win out at 3-4 conditions\])

# Answer
> 3 votes
# Vyxal, 14 bytes

```
‹₀ṡ'ǐĠvLġċnḂ=∧

```

Try it Online!

Port of Jelly answer.

## How?

```
‹₀ṡ'ǐĠvLġċnḂ=∧
‹₀ṡ             # Descending range [input - 1, 10]
   '            # Filter for n:
    ǐ           # Get the prime factorization of n
     Ġ          # Group consecutive identical items
      vL        # Get the length of each
        ġċ      # Is the GCD of this array not one?...
             ∧  # ...and...
          nḂ=   # Is n palindromic?

```

# Answer
> 3 votes
# C (gcc), 117 bytes

Brute force at its finest. It might be improvable by merging the two `for` loops into one, but I currently have no idea how to go about that.

```
x,p,i,s,t;f(n){for(x=p=i=10;t=i%n;p=p<i?p*x:x/i||i==s&i/p&&printf("%d\n",i)?++i,x=2:++x)for(s=0;t;t/=10)s=s*10+t%10;}

```

Try it online!

### Ungolfed

```
x, p, i, s, t;
f(n) {
  for ( x = p = i = 10; i < n; ) {
    // This loop calculates and sets `s` to the reverse of `i`
    for (s = 0, t = i; t; t /= 10)
      s = s * 10 + t % 10;
    // `p` is a running variable that holds the current
    // power depending on the base, `x`.
    if (p < i) {
      // While `p` is less than `i`, multiply it by `x`
      // (in other words, increment its exponent)
      p *= x;
    } else {
      if (x >= i) {
        // If no solution is found,
        // reset everything and increment `i`
        p = x = 2, ++i;
      } else if (i == s && i == p) {
        // If a solution is found,
        // print `i`, then reset everything and increment `i`
        printf("%d\n", i);
        p = x = 2, ++i;
      } else {
        // Otherwise, increment `x` to check for a solution
        // with the next base
        p = ++x;
      }
    }
  }
}

```

# Answer
> 3 votes
# Haskell, ~~76~~ ~~72~~ 64 bytes

```
f n=[z|x<-[2..n],z<-map(x^)[2..n],z<n,(==)=<<reverse$show z,z>9]
```

Attempt This Online! Given the ranges `[2..n]` are used, this aproach is *rather* inefficient. The ATO Link works for `n=1000`, but times out for `n=10000`.

##### Explanation:

```
f n =                        -- function f takes input n
  [z|                        -- returns list of all z where ...
     x<-[2..n],              --   ... z = x^y for x in [2..n]
     z<-map(x^)[2..n],       --               and y in [2..n]
     z<n,                    --   ... z is smaller than n
     (==)=<<reverse$show z,  --   ... z is an palindrome
     z>9]                    --   ... and z is larger than 9

```

# Answer
> 3 votes
# C (gcc), 111 bytes

```
i,t,r;g(n){r=9/--n||g(n);for(t=n;t;t/=10)r=r*10+t%10;for(t=i=2;r==n&i<n;)t=t/n?t-n?++i:printf("%d\n",i=n):t*i;}

```

Try it online!

# Answer
> 2 votes
# Retina 0.8.2, 100 bytes

```
.+
$*¶

$.`
10A`
G`^(?=(.)+)(?<-1>\1)+$
.+
$*
Gr`(?=((?=((1*)(?=\5\3+$)1)(\2*$))\4){2,}1$)^(..+)
%`1

```

Try it online! Link uses `n=500` as otherwise it would be too slow. Explanation: Based on my answer to Perfect radicals.

```
.+
$*¶

$.`

```

List all the integers up to `n`.

```
10A`

```

Delete the first `10` (i.e. `0`..`9`).

```
G`^(?=(.)+)(?<-1>\1)+$

```

Keep only palindromes.

```
.+
$*

```

Convert to unary.

```
Gr`(?=((?=((1*)(?=\5\3+$)1)(\2*$))\4){2,}1$)^(..+)

```

Keep only powers whose degree is at least `2`. Note that the `r` flag reverses the direction of processing, as if the entire regex was in a lookbehind.

```
%`1

```

Convert to decimal.

# Answer
> 2 votes
# JavaScript (V8), 81 bytes

```
n=>(g=x=>(x*=p)<n?[...x+''].reverse(g(x)).join``==x&&print(x):++p*p<n&&g(p))(p=7)

```

Try it online!

### Note

For \\$n\<7\\$, there is no \\$k\\$ such that \\$n^k\\$ is a palindromic power less than \\$100000000\\$ with at least 2 decimal digits. Therefore, we can safely start the search with \\$n=7\\$ and get rid of the few single-digit palindromic powers (\\$2^2\\$, \\$2^3\\$, \\$3^2\\$).

### Commented

```
n => (              // n = upper bound
  g =               // g is a recursive function taking
  x =>              // the current result x
  (x *= p) < n ?    // multiply x by p; if it's less than n:
    [...x + '']     //   turn x into an array of digits
    .reverse(       //   reverse this array
      g(x)          //   do a recursive call with x unchanged
    )               //   (reverse() ignores this argument)
    .join`` == x && //   if x is palindromic:
      print(x)      //     print it
:                   // else:
  ++p * p < n &&    //   increment p; if p² is less than n:
    g(p)            //     do a recursive call with x = p
                    //   (otherwise, stop the recursion)
)(p = 7)            // initial call to g with x = p = 7

```

# Answer
> 2 votes
# Python, ~~87~~ 82 bytes

```
lambda n:[m for k in range(4,n*n)if 9<int(str(m:=(k//n)**(k%n))[::-1])==m<n>k%n>1]
```

Attempt This Online!

Brute-force. Extremely slow. \\$O\Big(n^2\Big)\\$.

*-5 bytes thanks to jezza\_99*

### Here's a much, much, much faster one:

# Python, 128 bytes

```
import sympy.ntheory as s,math
lambda x:[x for x in range(10,x)if math.gcd(*s.factorint(x).values())!=1and str(x)==str(x)[::-1]]
```

Attempt This Online!

\\$O\Big(n\Big)\\$.

# Answer
> 2 votes
# Julia 1.0, 55 bytes

```
!n=filter(i->"$i"==reverse("$i")&&i∈(r=2:i)'.^r,10:n)

```

Try it online!

with a beautiful \\$O(n^3)\\$ complexity and \\$O(n^2)\\$ memory usage

# Answer
> 1 votes
# Vyxal, 16 bytes

```
ɽ₀ȯ'ɽ›Ėe:⌊=anḂ=∧

```

Try it Online!

Who needs smart prime factorisation when you can just brute force it?

## Explained

```
ɽ₀ȯ'ɽ›Ėe:⌊=anḂ=∧
ɽ₀ȯ'             # From the range [11, n) (empty if n < 10) keep only items (x) where:
   ɽ›Ėe:⌊=a      # there exists a number in the range [2, x) where that number to an integer power equals  x
          nḂ=∧  # and x is a palindrome

```

The part which checks for important power better explained:

```
ɽ›Ėe:⌊=
ɽ›       # the range [2, x)
  Ė      # the reciprocal of each number in that range - no need to worry about floating point accuracy errors because everything is stored as fractions internally
   e     # x to the power of each of those reciprocals - this is taking every nth root of x which is less than x
    :⌊=  # determine whether each item is a whole integer.

```

# Answer
> 1 votes
# Ruby `-rprime`, 88 bytes

```
->x{(10..x).select{|y|y.prime_division.map(&:last).inject(:gcd)>1&&y.digits*''==y.to_s}}
```

Attempt This Online!

# Answer
> 1 votes
# Charcoal, 19 bytes

```
ＩΦ…χＮ›⁼ι⮌ι⬤…²ι⊖Σ↨ιλ

```

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

```
  …                 Range from
   χ                Predefined variable `10` to
    Ｎ               Input as a number
 Φ                  Filtered where
       ι            Current value
      ⁼             Equals
         ι          Current value
        ⮌           Reversed
     ›              And not
           …        Range from
            ²       Literal integer `2` to
             ι      Current value
          ⬤         All value satisfy
                 ι  Outer value
                ↨   Converted to base
                  λ Inner value
               Σ    Take the sum
              ⊖     Is not equal to `1`
Ｉ                   Cast to string
                    Implicitly print each match on its own line

```

A more efficient version for 28 bytes:

```
ＩΦ…χＮ∧⁼ι⮌ι⊙↨ι²⁼¹Σ↨ι⌈Ｘ⊖ι∕¹⁺²μ

```

Try it online! Link is to verbose version of code. Explanation: Works by only testing `20` (for `n=1000000`) approximate roots for each palindrome instead of all `n`.

# Answer
> 1 votes
# Java 8, 133 bytes

```
n->{for(;--n>9;)for(int t=2,i=2;(n+"").contains(new StringBuffer(n+"").reverse())&i<n;t=t>n?++i:t*i)if(t==n)System.out.println(i=n);}

```

Outputs in reversed order. Very slow for larger test cases.

Inspired by *@att*'s C answer.

Try it online.

**Explanation:**

```
n->{                // Method with integer parameter and no return-type
  for(;--n>9;)      //  Loop `n` downward in the range (n,9):
    for(int t=2,i=2;//   Create two temp integers, starting at 2
        (n+"").contains(new StringBuffer(n+"").reverse())&
                    //   If the current `n` is a palindrome:
        i<n         //   Inner loop as long as `i` is still smaller than `n`:
        ;           //     After every iteration:
         t=         //      Replace `t` with:
           t>n?     //       If `t` is larger than `n`:
            ++i     //        Increase `i` by 1 first, and set `t` to this new `i`
           :        //       Else:
            t*i)    //        Multiply `t` by `i`
      if(t==n)      //    If `t` is equal to the current `n`:
        System.out.println(
          i=n       //     Set `i` to the current `n`
        );}         //     And print it with trailing newline

```

# Answer
> 1 votes
# Burlesque, 48 bytes

```
-.{J<-==}FO9.-f{Jbcjfc:-.jqLGZ]{J@1.>jXXsm&&}ay}

```

Try it online!

```
-.         # Decrement
{J<-==}FO  # Filter palindromes
9.-        # Drop single digits
f{         # Filter
 J         # Duplicate
 bc        # Repeat infinitely
 jfc       # Factors
 :-.       # Greater than 1
 jqLGZ]    # Log of number against factor
 {
  J@1.>    # Greater than 1
  jXXsm    # Is whole number
  &&}      # And
  ay       # Any
 }

```

# Answer
> 0 votes
# J-uby `-rprime`, 85 bytes

Port of Steffan’s Ruby answer.

```
:!~&10|:select+(-[:prime_division|:*&:last|:/&:gcd|:<&1,:==%[:digits|:join,S]]|:all?)

```

Attempt This Online!

---
Tags: code-golf, number, sequence, arithmetic, palindrome
---


title: Tips for golfing in J-uby

text:
# Question
Title: Tips for golfing in J-uby
J-uby is the Language of the Month for June 2022, so I'm looking for tips for golfing in it. As usual, please post one tip per answer, and avoid general tips such as "remove whitespace" or "avoid comments".

# Answer
> 2 votes
# `join` to `*`

Say we have an array:

```
a=[1,2]

```

To join it with commas:

```
a.join','

```

However this seems too long, let's replace it with `*`:

```
a*','

```

Or even better:

```
a*?,

```

# Answer
> 2 votes
# `reduce` to `/`

Let's say we have an array of:

```
a=[1,2]

```

If we want to find the sum:

```
a.reduce:+

```

Golfed:

```
:+/a

```

Just swap the `a` and `:+` before placing a `/` smack in the middle!

# Answer
> 2 votes
# Conversions

```
number.abs    #To abs value
number.|

Object.to_i    #To integer
Z[Object]

Object.to_f    #To float
Q[Object]

Object.to_s    #To string
S[Object]

Object.to_a    #To array
A[Object]

Hash[Object]    #To hash
H[Object]

```

All these make sure of single letters for conversions.

# Answer
> 0 votes
# Flip your comparisons

`x < 1` in tacit J-uby is `~:<&1` but the equivalent `1 > x` is a byte shorter: `:>&1`.

---
Tags: code-golf, tips
---