19
\$\begingroup\$

Background

We've studied at least five different types of numbers based on the IDs of different users on this site. Why not study another?

My user ID is \$91030_{10}\$. Its binary representation is \$10110001110010110_2\$, a representation which has an interesting property of its own:

  • One option for the longest palindromic run of binary digits is \$0011100\$.
  • If you remove this run of digits, the remaining list of digits (\$1011010110\$) can be split into two identical halves.

I define a sporeball number as any positive integer where at least one of the options for the longest palindromic run of digits in its binary representation can be removed such that the remaining list of digits can be split into two identical halves.

Task

Write a program or function which takes a positive integer as input and determines whether or not it is a sporeball number.

Some clarifications to keep in mind:

  • Leading zeroes should be ignored.
  • Exactly one palindromic run of digits should be removed before checking if the remaining digits can be split into identical halves.
    • If one of the options for the longest palindromic run occurs multiple times, remove only one occurrence, rather than all of them, before checking if the remaining digits can be split into identical halves.
  • Single digits are palindromic.
  • The empty string "" is not palindromic, and cannot be split into two identical halves.

Remember that there may be more than one longest palindromic run of digits:

  • The binary digits of \$12_{10}\$ (\$1100\$) contain two options for the longest palindromic run (\$11\$ and \$00\$). No matter which one is removed, the remaining digits will be able to be split into identical halves. Thus, \$12_{10}\$ is a sporeball number.
  • The binary digits of \$20_{10}\$ (\$10100\$) contain two options for the longest palindromic run (\$010\$ and \$101\$). Removing \$010\$ leaves the digits \$10\$, which cannot be split into identical halves; however, removing \$101\$ leaves the digits \$00\$, which can be. Thus, \$20_{10}\$ is a sporeball number.

There are 153 sporeball numbers under 1,000:

12 20 23 24 26 28 29 39 48 57 60 68 71 84 87 96 100 106 108 110 111 113 117 123 124 132
135 154 166 178 180 183 192 204 207 210 222 225 237 240 243 252 260 263 277 282 287 295
314 326 334 336 337 340 343 348 351 354 370 372 375 384 392 394 396 399 404 412 418 426
428 431 432 446 449 457 469 476 477 479 480 483 484 490 491 496 497 501 503 508 516 519
533 538 543 562 600 610 612 615 634 646 652 660 663 664 670 673 676 691 700 703 706 718
720 735 742 754 756 759 768 778 780 783 792 804 816 821 826 828 831 834 858 870 874 876
879 894 897 918 921 922 924 927 933 957 960 963 972 978 987 993 999

Rules

  • This is , so shortest answer in bytes wins.
  • Standard I/O rules apply.
\$\endgroup\$
12
  • 4
    \$\begingroup\$ Nice name. I’m afraid I’ll never have a set of numbers named after me \$\endgroup\$ – user Sep 19 '20 at 3:39
  • 1
    \$\begingroup\$ @JoKing The empty string is not palindromic because it contains no characters to read backwards or forwards. \$\endgroup\$ – sporeball Sep 19 '20 at 4:24
  • 2
    \$\begingroup\$ "You can use any two distinct values for true and false." - this is not the site default of truthy/falsey (which allows values which the language evaluates as true/false). I don't think there is a good reason to override this default here. \$\endgroup\$ – Jonathan Allan Sep 19 '20 at 15:17
  • 4
    \$\begingroup\$ FWIW the empty string is palindromic, by definition, since it's the same forwads as it is backwards. It will never be the longest present, however (since, as you point out, single digits are palindromic). \$\endgroup\$ – Jonathan Allan Sep 19 '20 at 15:26
  • 2
    \$\begingroup\$ Does "exactly one palindromic run of of digits" mean all instances of a single palindrome, or one instance of a palindrome? The least number where this makes a difference is 2405. \$\endgroup\$ – att Sep 21 '20 at 5:08

14 Answers 14

10
\$\begingroup\$

Brachylog, 26 bytes

{ḃ~c₃↺{↔?¬Ė}ʰ↻c}ᶠlᵒlᵍh∋~jz

Try it online!

Dreadfully slow for large falsy testcases, but verifies truthy ones surprisingly quickly. My original solution ran into the same false negatives as xash's deleted answer, but fortunately the process of fixing that helped me shave off 2 bytes.

{              }ᶠ             Find every possible result from:
 ḃ                             take the binary digits of the input,
  ~c₃                          split them into three (possibly empty) partitions,
     ↺{    }ʰ↻                 for the middle partition:
       ↔                        reversed it is
        ?                       itself
         ¬Ė                     which is not the empty list;
          Ė                     replace it with the empty list.
              c                and re-concatenate the partitions.
                 lᵒ           Sort the results by length,
                   lᵍ         group them by length,
                     h        and take the first group (that with minimal length).
                      ∋       Some element of that group
                       ~j     is something concatenated with itself
                         z    which is not the empty list.

Rather than maximize the length of the palindromic substring, it just minimizes the length of everything left, which is an approach I really only came up with because of my initial approach of relying on .

\$\endgroup\$
8
\$\begingroup\$

05AB1E, 47 45 43 42 40 41 40 31 bytes

b©ŒʒÂQ}é.γg}θε®sõ.;D2ä1ìËsgĀ*}à

Try it online!

-2 thanks to @ovs!
-1 thanks to @ovs!
-1 (lol) thanks to a bug fix
-1 thanks to @ovs (again!)
+1 due to challenge clarification :-(
but -1 thanks to @Kevin!
and another whopping -9 thanks to @Kevin!

Don't mind me... just posting another overly long answer in 05AB1E that will probably be was golfed by anyone experienced with 05AB1E.

The ÂQ trick to see if a string is a palindrome was taken from this 05AB1E tip answer by Kevin.

Explained (old)

bDV.œ˜ʒÂQ} ЀgàUʒgXQ}εYsõ:Ðg;ôËsgD0ÊsÈ**}à
bDV                                             # Get the binary representation of the input, and assign variable Y to that value while still keeping a copy on the stack
   .œ                                           # Push all partitions of that binary representation
     ˜                                          # Flatten said list and
      ʒ                                         #  Select items where:
       ÂQ}                                      #      They are a palindrome

            Ð                                   # and push three copies of it to the stack.
             €g                                 # For one of those copies, push the length of each item
               àU                               # Find the maximum length and assign it to variable Y
                 ʒgXQ}                          # From the list of palindromic partitions, select the ones which are of the maximum length
                      ε                         # And from that list:
                       Ysõ:                     #   Replace the occurrence of that number in variable Y with nothing THEN
                           Ð                    #   Triplicate it THEN
                            g;ô                 #   Split it in half THEN
                               Ë                #   See if all elements are equal AND
                                sgD0ÊsÈ**       #   Ensure the length of Y with the item removed isn't 0 and isn't odd
                                         }à     # Close the map, and take the maximum of the list and implicitly print the result
\$\endgroup\$
9
  • 1
    \$\begingroup\$ time to do this in Keg \$\endgroup\$ – Razetime Sep 19 '20 at 5:34
  • 1
    \$\begingroup\$ I think you can replace O>≠ with à (maximum), because the list only contains 1s and 0s at the end. And if you flatten the partitions before checking for palindromes, the map isn't necessary. \$\endgroup\$ – ovs Sep 19 '20 at 7:12
  • 1
    \$\begingroup\$ @sporeball fixed \$\endgroup\$ – lyxal Sep 19 '20 at 20:50
  • 1
    \$\begingroup\$ Since : performs infinite replacement, this also fails on an input of 2405. \$\endgroup\$ – sporeball Sep 21 '20 at 6:31
  • 1
    \$\begingroup\$ 31 bytes: DV...Y to ©...®; .œ˜ to Œ; ЀgàUʒgXQ} to é.γg}θ; ËsgƵ2SQË* to 1ìËsgĀ*. \$\endgroup\$ – Kevin Cruijssen Sep 21 '20 at 7:44
5
\$\begingroup\$

J, 80 78 75 66 61 57 bytes

1 e.#\,@((#<.[-:[:,~,~inv)\.*[:(*i.@#=+./"{i:1:)(-:|.)\)]

Try it online!

-3 bytes thanks to Marshall

-9 bytes thanks to xash

Tougher than I thought it would be.

Finally a respectable size, though still high for J.

J, alternate approach, 73 bytes

1 e.1}.((((<:@[,(-:|.)\#(#<.]-:[:,~,~inv)\.)~{.))^:(0<{.@]*1=#@])^:_#)@#:

Try it online!

This one uses do..while ^:(while)^:_, starting by searching the longest possible length palindrome, and stopping as soon as it finds any for a certain length, returning the boolean telling you if the complement for that palindrome is a doubled string.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ … and [:(*i.@#=1 i:~+./"1) still feels too long. But \ and \. are a nice fit for this challenge! \$\endgroup\$ – xash Sep 20 '20 at 3:01
  • 1
    \$\begingroup\$ 66 bytes \$\endgroup\$ – xash Sep 20 '20 at 3:35
  • \$\begingroup\$ @xash, thanks! now 61: tio.run/… \$\endgroup\$ – Jonah Sep 20 '20 at 3:39
  • \$\begingroup\$ @xash fwiw I spent some time trying to improve *i.@#=+./"{i:1: but wasn't able to. \$\endgroup\$ – Jonah Sep 20 '20 at 6:18
4
\$\begingroup\$

Retina, 126 bytes

.+
*
+`^(_*)\1(_?)(?!^|_)
$1$.2
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|.
$`$'
N$`
$.&
+m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1
0m`^(.+)\1$

Try it online! Explanation:

.+
*

Convert the input to unary.

+`^(_*)\1(_?)(?!^|_)
$1$.2

Convert it to binary.

Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|.
$`$'

Find and remove palindromes.

N$`
$.&

Sort the results by length, so that the first result corresponds to the longest palindrome.

+m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1

Remove all results of longer length.

0m`^(.+)\1$

Check whether any of them can be split.

\$\endgroup\$
1
  • \$\begingroup\$ I've since noticed that taking input directly as a binary string is allowed; this would naturally cut the byte count by 32 if applied here (simply delete the first four lines). \$\endgroup\$ – Neil Sep 20 '20 at 17:39
4
\$\begingroup\$

Charcoal, 53 bytes

≔⍘N²θF⊕LθFιF⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Lι⌊EυLλ⁼ιײ∕ι²

Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. - for a sporeball number, empty if not. Explanation:

≔⍘N²θ

Convert the input to base 2.

F⊕LθFι

Loop over all nontrivial substrings of the input.

F⁼✂θκι¹⮌✂θκι

If this substring equals its reverse...

⊞υ⁺…θκ✂θι

... then push the remaining digits to the predefined empty list.

¿⌊υ

If the original number was not palindromic, ...

⊙υ∧⁼Lι⌊EυLλ⁼ιײ∕ι²

... then output whether any of the results are of minimal length and equal themselves halved in length and doubled again.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Taking the input directly as a binary string would naturally save 5 bytes. \$\endgroup\$ – Neil Sep 20 '20 at 17:39
4
\$\begingroup\$

Jelly, 31 bytes

ḊḢŒḂḤœP⁸F
BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ

Try it online! Or see those up to 600 (up to 1000 is too slow).

How?

BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ - Main Link: n
B                     - convert (n) to a binary list
 Ø2                   - [2,2]
   j                  - join ([2,2]) with (B(n))
    ŒṖ                - partitions (none with empty parts, hence the Ø2j and ḟ€€2)
      ḟ€€2            - remove any 2s from each part of each
          ǀ          - call Link 1 for each
                        (removes second part if it's palindromic & flattens)
            LÐṂ       - keep only those with minimal length
                   Ƈ  - filter keep those for which:
                  $   -   last two links as a monad:
               ŒH     -     split into two
                 E    -     all equal?
                    Ẹ - any truthy?

ḊḢŒḂḤœP⁸F - Link 1: list of parts
Ḋ         - deueue
 Ḣ        - head -> second part
  ŒḂ      - is palindromic? (1 if so, else 0)
    Ḥ     - double
       ⁸  - the list of parts
     œP   - partition at index
            (0œP[4,5,6,7] -> [[4,5,6,7]] while 2œP[4,5,6,7] -> [[4],[6,7]])
        F - flatten
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 128...103 101 bytes

FreeQ[MinimalBy[$@@d~Drop~#&/@SequencePosition[d=#~IntegerDigits~2,_?PalindromeQ],Length],a__~$~a__]&

Try it online!

Returns False if the number is not a sporeball number, and True otherwise.

d=#~IntegerDigits~2                     (* get digits of input, base 2. *)
SequencePosition[ % ,_?PalindromeQ]     (* get positions of palindromic runs *)
d~Drop~#/@ %                            (* and remove them, *)
$@@ %                                   (* placing the remaining digits in $ *)
MinimalBy[ % ,Length]                   (* keep the shortest remaining digit lists *)
FreeQ[ % ,a__~$~a__]                    (* and check if they have identical halves. *)

$@@ is needed to handle cases like \$38=100110_2\$, where removing either of the two longest-palindromes 1001, 0110 has the same result 10.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 175 bytes

n=>(m=g=(s,p='',q=p)=>s?g(s.slice(1),p+s[0],q,s==[...s].reverse(L=s.length).join``?o=(L<=m?o:!(m=L))|L==m&/^(.+)\1$/.test(p+q):0,g(s.slice(0,-1),p,s[L-1]+q)):o)(n.toString(2))

Try it online!

Commented

n => (                    // n = input
  m =                     // initialize m to a non-numeric value
  g = (                   // g is a recursive function taking:
    s,                    //   s = middle part of the string (the palindromic one)
    p = '', q = p         //   p = left part, q = right part
  ) =>                    //
    s ?                   // if s is not empty:
      g(                  //   outer recursive call:
        s.slice(1),       //     with the first character of s removed ...
        p + s[0],         //     ... and appended to p
        q,                //     with q unchanged
        s == [...s]       //     split s
        .reverse(         //     reverse it
          L = s.length    //     set L = length of s (argument ignored by reverse)
        ).join`` ?        //     join again; if s is a palindrome:
          o =             //       update o:
            ( L <= m ?    //         if L is not higher than m:
                o         //           yield o
              :           //         else:
                !(m = L)  //           update m to L and yield 0
            ) | L == m &  //         bitwise OR with 1 if L = m (current max.)
            /^(.+)\1$/    //         and the concatenation of p and q can be
            .test(p + q)  //         split into 2 identical halves
        :                 //     else:
          0,              //       abort
        g(                //     inner recursive call:
          s.slice(0, -1), //       with the last character of s removed
          p,              //       with p unchanged
          s[L - 1] + q    //       with the last character of s prepended to q
        )                 //     end of inner recursive call
      )                   //   end of outer recursive call
    :                     // else:
      o                   //   return o
)(n.toString(2))          // initial call to g with s = binary string for n
\$\endgroup\$
3
\$\begingroup\$

Husk, 28 bytes

▲foE½†!ḋ¹ṠM-ö→kLfoS=↔m!ḋ¹Qŀḋ

Try it online! Returns an empty list (which is falsy in Husk) or a nonempty list (which is truthy).

Explanation

The repeated feels wasteful but I'm not sure how to get rid of it.

Input is a number, say n=357
▲f(E½)†!ḋ¹ṠM-(→kLf(S=↔m!ḋ¹)Q)ŀḋ   Parentheses added for clarity.
                              ḋ   Binary digits: D=[1,0,1,1,0,0,1,0,1]
                             ŀ    Indices: I=[1,2,3,4,5,6,7,8,9]
             (→kLf(S=↔m!ḋ¹)Q)     Get indices of longest palindromic runs.
                           Q      Slices: [[1],[2],[1,2],..,[1,2,..,9]]
                 f                Filter by condition:
                  (S=↔m!ḋ¹)       Is a palindrome in D.
                      m           Map
                       !          indexing into
                        ḋ¹        D (recomputed).
                   S=             That equals
                     ↔            its reverse.
               kL                 Classify (into separate lists) by length.
              →                   Get the last one: [[2,3,4,5],[4,5,6,7]]
          ṠM-                     Remove each from I: [[1,6,7,8,9],[1,2,3,8,9]]
      †                           Deep map
       !ḋ¹                        indexing into D (recomputed again): [[1,0,1,0,1],[1,0,1,0,1]]
 f                                Filter by condition:
  (E½)                            Splits into identical halves.
    ½                             Split into halves (if length is odd, first part is longer): [[1,0,1],[0,1]]
   E                              All elements are equal: 0
                                  Result is []
▲                                 Maximum, or [] if the argument is empty: []
                                  The final result is nonempty iff the last filter keeps a nonempty list.
\$\endgroup\$
3
\$\begingroup\$

Pip -p, 62 bytes

$Q_^@#_/2FIMN(_FI#*Y{c:y@$,:acQRVc?yRAaxx}M$ALCG1+#YTBa)=#_FIy

Outputs an empty list for falsey, non-empty for truthy. Try it online!

Oy vey. I'm not going to write up a detailed explanation for that monstrosity. Suffice it to say that half the bytecount (roughly the Y{c:y@$,:acQRVc?yRAaxx}M$ALCG1+# section) is required to find all palindromic substrings and remove them.

\$\endgroup\$
2
  • \$\begingroup\$ I want to try writing an explanation for this. \$\endgroup\$ – Razetime May 1 at 8:16
  • \$\begingroup\$ @Razetime Hey, go for it! \$\endgroup\$ – DLosc May 1 at 16:17
2
\$\begingroup\$

Python 3.8 (pre-release), 154 152 bytes

def f(n):s=f'{n:b}';k=len(s);return max((b-a,(r:=s[:a]+s[b:])[:(h:=k-b+a>>1)]==r[h:]>'')for a in range(k)for b in range(a,k+1)if(p:=s[a:b])==p[::-1])[1]

Try it online!

Commented:

s=f'{n:b}'                    # convert n to a binary string
k=len(s)                      # and take the length
return max( ... )[1]          # the second element from the maximum of 
  (b-a,                       #   tuples of palindrome length b-a ...
             [:(h:=k-b+a>>1)] #   ... and is the first half
  (r:=s[:a]+s[b:])            #       of the binary string without the palindrome
    ==r[h:]                   #       equal to the second half
    >'')                      #       and not equal to the empty string
  for a in range(k)           #   for palindrome starting positions a in [0, 1, ..., k-1]
  for b in range(a,k+1)       #   for palindrome end indices b in [1, 2, ..., k-a]
  if(p:=s[a:b])==p[::-1])     #   if this is an actual palindrome

If there multiple palindromes of same maximum length, max selects the tuple with the highest second value, where True>False.

\$\endgroup\$
2
\$\begingroup\$

Factor, 209 197 bytes

: s ( n -- ? ) >bin dup all-subseqs [ dup reverse = ] filter
dup [ last length ] dip [ length over = ] filter nip
[ split1 append [ ""= not ] keep dup length 2/ cut = and ]
with [ or ] map-reduce ;

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 33 42 bytes

s2
ã fêS üÊo
Vc@ðXãjXVÎlîòZÊ/2Ãd_Ê©ZÎ¥Zo

Try it

s2          - convert input to binary string

ã           - substrings
  fêS       - filter palindrome
      üÊo   - take last group by length

Vc@ðXÃ      - find indexes of each palindrome in input
£jXVÎlà     - map those indexes by removing n(=palindr.length) characters from input at index
®òZÊ/2Ã     - split all results
d_          - return true if any : 
  Ê©          - exists and..
    ZÎ¥Zo     - are ==
  • Fixed : now works for numbers with more identical longest palindromic runs like 2405 => 100101100101

  • Test : computes first 1000 terms and check if the result is the same as test cases.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ fails on 2405 \$\endgroup\$ – att Sep 21 '20 at 2:54
  • \$\begingroup\$ On second thought, the spec is a little vague about that. I'll ask. \$\endgroup\$ – att Sep 21 '20 at 5:07
  • \$\begingroup\$ @att I think you are right , that's why r replaces every occurrences of X, hence 100101100101 becomes 0101 which gives true, I think OP clearly stated that exactly one run have to be discarded. Thanks for spotting that out. \$\endgroup\$ – AZTECCO Sep 21 '20 at 5:45
1
\$\begingroup\$

Dotty, 201 bytes

s=>((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}

Try it online (in Scastie)

Input must already be a binary string.

Dotty, 226 bytes

x=>{val s=x.toBinaryString
((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}}

Try it online (in Scastie)

Input is an Int.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.