title: Pascal's Fibonacci Triangle

text:
# Question
Title: Pascal's Fibonacci Triangle
What do you get when you cross Pascal's Triangle and the Fibonacci sequence? Well, that's what you have to find out!

# Task

Create a triangle that looks like this:

```
          1
        1   1
       2  2  2
    3   5  5   3
  5  10  14  10  5
8  20  32  32  20  8

```

Basically, instead of each cell being the sum of the cells above it on the left and right, you also need to add the cell on the left above the cell on the left and the cell on the right above the cell on the right.

This is A036355.

You may choose to do one of the following:

* Output the \\$n\\$th row (indexed as you wish)
* Output the first \\$n\\$ rows
* Output all rows infinitely

# Rules

* Each row may be represented as a string separated by some character that is not a digit or an ordered collection of numbers. You do not need to align the triangle like I did in the example.
* If you choose to output multiple rows, you need either an ordered list of rows, or a string that uses a different separator than the one you use within rows.
* Please specify which task you chose in your answer, along with the input (if applicable) and output format.
* You can receive input and output through any of the standard IO methods.
* This is , so shortest code in bytes wins!

## Bounty

As Scala is the language of the month, I will be giving a 50 rep bounty for any Scala answers to this question (not just if you're a first-time user). If multiple Scala answers are posted, I will be happy to put a bounty on a different Scala answer of yours instead.

# Answer
> 13 votes
# Python 2, ~~73~~ ~~72~~ 69 bytes

-1 byte thanks to dingledooper!
-3 bytes thanks to Sisyphus!

Prints the rows indefinitely.

```
c=a=[0]
b=[1]
while 1:print b;a,b=b,map(sum,zip(c*2+a,a+c*2,c+b,b+c))

```

Try it online!

# Answer
> 7 votes
# Haskell, <sup>~~82~~ \\$\cdots\\$</sup> 60 bytes

```
[]%[1]
u%v=v:v%foldl1(zipWith(+))[0:0:u,u++[0,0],0:v,v++[0]]

```

Try it online!

*-10 thanks to @user*

*-4 thanks to @ovs*

Fairly new to Haskell, and never golfed in it before. Happy to be beaten!

# Answer
> 6 votes
# , 30 bytes

Returns the n'th row.

```
0{((+|.)@(+/)@,.,:{~)&0&(1,:0)

```

Try it online!

### How it works

* `f&0&(1,:0)` `(1,:0) f 0` will be executed `n` times
* `(last two rows) g@,. (0)` append a 0 to each row and execute g, f.e. `g (2 2 2 0,: 1 1 0 0)`
* `(+|.)@(+/)` sum the two rows `3 3 2 0` and add it to its reverse: `3 5 5 3`
* `,:{~` append the previous row `3 5 5 3,:2 2 2 0`
* `0{` after `n` iteration get the last row `3 5 5 3`

# Answer
> 5 votes
# 05AB1E, ~~25~~ ~~24~~ ~~19~~ ~~18~~ ~~13~~ 12 bytes

-6 bytes thanks to @ovs

-4 bytes thanks to @Neil, which allowed for additional -1

-2 bytes thanks to @Kevin Cruijssen

```
1‚ηλ₂0š+0šÂ+

```

Try it online!

A port of the python answer, basically. Outputs the rows infinitly

Explaination:

```
1 push 1
‚ pair. Since there is no input, it pairs 1 with 1, to get [1, 1]
η prefixes, get [[1], [1, 1]]
λ recursive environment
₂ push a(n-2)
0š prepend 0 to a(n-2)
+ sum with implicit a(n-1)
0š prepend a zero
Â Bifurcate - push a and reversed(a)
+ sum

```

# Answer
> 5 votes
# Scala, ~~156..133~~ 120 bytes

*-23 bytes thanks to user!*
*-13 bytes thanks to Command Master!*

```
()=>{var(a,b)=Seq(1,1)->Seq(1)
while(1>0){println(b)
val t=a
a=Seq(0+:0+:b,b:+0:+0,a:+0,0+:a).transpose.map(_.sum)
b=t}}

```

Try it online!

Output is infinite.

Explanation:

```
object M extends App {
  var (a, b) = Seq(1, 1) -> Seq(1)                                          // init (a, b) := ([1, 1], [1]])
  while (1 > 0) {                                                           // while true
    println(b)                                                              // print b
    val t = a                                                               // cache a in a local variable t
    a = Seq(0 +: 0 +: b, b :+ 0 :+ 0, a :+ 0, 0 +: a).transpose.map(_.sum)  // calculate the new triangle row with
                                                                            // the help of the shifted lists a and b like in the example below
    b = t                                                                   // set b the cached previous value of a
  }
}

```

Example for n = 4:

```
   0  0  2  2  2
+  2  2  2  0  0
+  3  5  5  3  0
+  0  3  5  5  3
-----------------
=  5 10 14 10  5

```

# Answer
> 4 votes
# Haskell, 81 bytes

```
q=zipWith(+)
z=[0,0]
f=[]:[1]:[q(a++z)$q(z++a)$q(b++[0])$0:b|(a,b)<-zip f$tail f]

```

Try it online!

Returns an infinite list of all rows, 1-indexed (hence the `tail` in TIO to dispose of element `0`).

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

```
≔⟦¹⟧ηＦＮ«⊞υ⁰≔Ｅυ⁺κ§ηλι≔ηυ⊞ι⁰≔Ｅ⮌ι⁺κ§ιλη»Ｉη

```

Try it online! Link is to verbose version of code. Outputs the 0-indexed nᵗʰ row. Explanation: Relies on the symmetry of the triangle.

```
≔⟦¹⟧η

```

Start with the 0ᵗʰ row with just a `1` in it (using the predefined empty list for the "-1ᵗʰ" row).

```
ＦＮ«

```

Repeat `n` times.

```
⊞υ⁰

```

Append a `0` to the previous row.

```
≔Ｅυ⁺κ§ηλι

```

Sum the previous and current row to a temporary variable.

```
≔ηυ

```

Copy the current row to the previous row.

```
⊞ι⁰

```

Append a `0` to the new row.

```
≔Ｅ⮌ι⁺κ§ιλη

```

Add the new row to its reverse and save that as the current row.

```
»Ｉη

```

Print the final row.

Previous 54-byte version worked by creating the matrix formed by rotating the triangle anticlockwise by 45°:

```
Ｎθ⊞υＥθ⁼ι¹⊞υ⟦⁰⟧Ｆθ«≔⟦⁰⟧ηＦ⁻θι⊞ηΣ⁺…⮌η²Ｅ…⮌υ²§λ⊕κ⊞υη»Ｉ✂Ｅυ⊟ι²

```

Try it online! Link is to verbose version of code. Outputs the 1-indexed nᵗʰ row. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υＥθ⁼ι¹

```

Create a fictitious "-1ᵗʰ" row with a single `1` in the first column. This seeds the first row later.

```
⊞υ⟦⁰⟧

```

Create a "0ᵗʰ" row of zeros. (Because Charcoal uses cyclic indexing, I only need one zero.)

```
Ｆθ«

```

Loop over the desired output rows.

```
≔⟦⁰⟧η

```

Start with a "0ᵗʰ" column of just a zero.

```
Ｆ⁻θι

```

Loop over the additional numbers needed to complete this row of the rotated triangle.

```
⊞ηΣ⁺…⮌η²Ｅ…⮌υ²§λ⊕κ

```

Get the latest two numbers for this row plus the two numbers in the columns above and push the sum to the current row.

```
⊞υη

```

Push the completed row to the triangle.

```
»Ｉ✂Ｅυ⊟ι²

```

Print the last number in each row, excluding the two initial dummy rows.

# Answer
> 4 votes
# Perl 5, 86 bytes

```
$,=$";@b=@c,@c=@,while say@,=map$,[$_]+($_>0)*$,[$_-1]+($_>1)*$b[$_-2]+$b[$_]||1,0..@,

```

Try it online!

Output is infinite.

# Answer
> 3 votes
# AWK, ~~117~~ 111 bytes

Prints the first `n` rows of the triangle, unformatted.

Edit: Let `l` and `c` be two integers. `l c` concatenates their values as a string. For example: in the first element, `0 0` evaluates `"00"` (str). `00` would evaluate `0` (int).

```
{print a[0 0]=1;for(;++l<$1;)for(c=0;c<=l;c++)printf a[l c]=a[l-1 c-1]+a[l-1 c]+a[l-2 c-2]+a[l-2 c](c~l?RS:FS)}

```

Step by step:

```
{
print a[0 0]=1;                  # sets the top of the triangle
for(;++l<$1;)                    # looping for the lines
  for(c=0;c<=l;c++)              # looping for the columns
    printf a[l c]=               # prints the ["l c"]th element of the array,
           a[l-1 c-1]+a[l-1 c]+  # which is the sum of these elements of the l-1 line
           a[l-2 c-2]+a[l-2 c]   # and these elements of the l-2 line.
           (c~l?RS:FS)           # if it's the last column, adds a line feed,
                                 # otherwise, a space.
}

```

Try it online!

# Answer
> 3 votes
# Husk, ~~17~~ 15 bytes

```
:;1mSż+oΘ↔Ẋż+Θ₀

```

Try it online!

Answering Razetime's challenge from the Husk chat

### Explanation

```
:;1mSż+oΘ↔Ẋż+Θ₀
:;1                Begin with [1]
              ₀    Define the sequence recursively
          Ẋż+Θ     Pairwise sums of rows (e.g. [1,1]+[2,2,2]=[3,3,2])
   m               For each of these sums
    Sż+             Sum it to
       oΘ↔          itself reversed with an extra leading 0
                    (e.g. [3,3,2]+[0,2,3,3]=[3,5,5,3])

```

All the sums between lines are performed with `ż+`, which sums elements at the same indices and keeps elements from the longer line unchanged.

---

## Previous solution, 17 bytes

```
∂ƒ(:İftS‡+T0Ẋż+ΘΘ

```

Try it online!

Here's my previous solution using an original approach.

### Explanation

If we rotate the triangle 45° counterclockwise, we'll find out it is actually an infinite 2D matrix:

```
1  1  2  3  5 ...
1  2  5 10 20 ...
2  5 14 32 71 ...
3 10 32 84 ...
5 20 71 ...
...

```

This answer builds that matrix and then returns its antidiagonals, which will be the rows of the original triangle.

```
∂ƒ(:İftS‡+T0Ẋż+ΘΘ
∂                    Antidiagonals of
 ƒ(                  Fixpoint of the following function (defines the matrix recursively)
   :İft              Set the Fibonacci sequence as the first row
               ΘΘ    Add two empty rows before the matrix
            Ẋż+      and get the pairwise row sums
       S‡+T0         then sum this to itself transposed

```

The recursive definition computes the sums of each row with the previous one, and adds it to the sums of each column with the previous one; since the matrix is symmetric along the main diagonal, column sums are computed by transposing the row sums. Two empty rows need to be added to deal with the numbers near the sides of the triangle, where there are less than two rows/columns to sum.

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~60~~ 47 bytes

```
#3&@@@(#3&@@(1/(1-x(1+y+x+y^2x))+O@x^#)+O@y^#)&

```

Try it online!

1-indexed. Returns the first \\$n\\$ rows by truncating the generating function \\$\frac1{1-x(1+x+y+xy^2)}\\$.

---

older, **66 bytes**

```
Sum[Multinomial[#-n-2i,n-2j,i,j],{i,0,#-n},{j,0,n}]~Table~{n,0,#}&

```

Try it online!

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

```
f=(a=0,b=[1])=>print(b)+f(b,[...b,0].map((x,i)=>x+(a[i]|0)+(b[i-1]|0)+(a[i-2]|0)))

```

Try it online!

* Missing a JavaScript answer, hoping @Arnauld is fine

# Answer
> 2 votes
# Jelly, 14 13 12 bytes

```
1WɓŻ+Ż++µ³¡0

```

Try it online!

Returns the nth row, indexed from 0.

Makes use of the fact that Jelly's “repeat n times” quick `¡`, when given a dyad, behaves in a Fibonacci-ish way.

# Answer
> 2 votes
# Husk, ~~29~~ ~~28~~ ~~23~~ 19 bytes

* Saved 1 byte thanks to caird coinheringaahing
* Saved 5 bytes thanks to Razetime!
* Saved 4 bytes thanks to Leo!

```
¡öFz+S+m↔z+ḣ´e0↔;;1

```

Try it online!

Outputs an infinite list, explanation coming soon. This is *really* long, so it looks like I'm not going to get the bounty anyway.

```
¡öFz+S+m↔z+ḣ´e0↔;;1
¡                     Create infinite list by repeatedly applying function
                      that list of previous result to create new result
                ;;1   Initial list of results - [[1]]
  Fz+S+m↔z+ḣ`e0↔      Function to get next row from previous rows
               ↔      Reverse previous rows (so last 2 rows are at start)
            `e0       [0, 0]
           ḣ          Prefixes ([[0], [0,0]])
         z+           Zip by concatenating ([0, 1, 1], [0, 0, 1])
     S+               Then add those lists
       m↔             To their reverse ([1, 2, 1], [1, 0, 1])
  F                   Fold over that 2-element list of lists
   z+                 By adding them together to get the new row

```

# Answer
> 2 votes
# Haskell, 59 bytes

```
x!y=zipWith(+)x$y++[0,0]
x#y=x:(0:0:y)!y!(0:x)!x#x
t=[1]#[]

```

Try it online!

# Answer
> 1 votes
# PHP, ~~124~~ ~~115~~ 112 bytes

```
echo 1;for($q=[1];print"
";$p=$q,$q=$r)for($i=-1;++$i<=count($q);)echo$r[$i]=$q[$i-1]+$q[$i]+$p[$i-2]+$p[$i].~_;

```

Try it online!

Did the world want this answer? Probably not. Did it deserve it? Definetly.

straightforward PHP soup that outputs all rows forever (at least until scientific notation -quickly- makes things unreadable)

EDIT: saved 9 bytes by not initializing $p and $r. There wasn't enough warnings for my taste.

EDIT2: saved another 3 bytes with another strategy for the newline output, thanks to `print` returning a truthy value (note that I'm aware that a byte could be saved with a "assumed constant" line separator like `print A`, but I preferred a readable output)

# Answer
> 1 votes
# Julia 1.0, 53 bytes

```
f(i=1,j=[])=@show(i),f([i;0]+[0;i]+[j;0;0]+[0;0;j],i)

```

Try it online!

call `f()` for infinite output

Only correct up to 64-bit signed integer limit, replace `i=1` with `i=big(1)` to make it work for any number

# Answer
> 1 votes
# Pip `-s`, 22 bytes

```
Y^1LaS(l+:Py)+:RVlPE0y

```

Outputs the first `n` rows. Try it online!

### Explanation

Each row of the triangle, represented as a list, can be obtained by a two-step process: first add the two previous rows; then take that result, reverse it, prepend 0, and add it to itself.

```
 [2 2 2]
+[3 5 5 3]
----------
 [5 7 7 3]
+[0 3 7 7 5]
------------
 [5 10 14 10 5]

```

Let's start with a less-golfed version of the code:

```
Y[1]La{Pyl+:yl+:RVlPE0Sly}
                            a is command-line argument; l is empty list (implicit)
Y[1]                        Yank the first row into y
    La{                  }  Loop a times:
       Py                    Print y, the current row
         l+:y                Add the two rows together, saving the result in l
                RVl          Reverse that list,
                   PE0       prepend 0,
             l+:             and add it back to l (the new row)
                      Sly    Swap l and y; y is now the new row and l the row above it

```

To get to 22 bytes:

* Using this tip, `[1]``^1`.
* We can print `y` while adding it to `l`: `l+:Py`.
* An assignment expression evaluates to an lvalue, so we can use it in the swap command: `S(l+:RVlPE0)y` (parentheses not necessary, added for clarity).
* But then we can take the same idea one step further and replace the `l` in *that* assignment with the first `l` assignment. We'll need parentheses because assignment operators are right-associative; but since the body of the loop is now one statement, we can drop the curly braces for a net 1-byte savings: `S(l+:Py)+:RVlPE0y`.

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


title: sporeball numbers

text:
# Question
Title: sporeball numbers
## 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.

# Answer
# 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 .
> 10 votes

# Answer
# 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

```
> 8 votes

# Answer
# , 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.

# , 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.
> 5 votes

# Answer
# 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`.
> 4 votes

# Answer
# 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.
> 4 votes

# Answer
# Charcoal, 53 bytes

```
≔⍘Ｎ²θＦ⊕ＬθＦιＦ⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ι×²∕ι²

```

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:

```
≔⍘Ｎ²θ

```

Convert the input to base 2.

```
Ｆ⊕ＬθＦι

```

Loop over all nontrivial substrings of the input.

```
Ｆ⁼✂θκι¹⮌✂θκι

```

If this substring equals its reverse...

```
⊞υ⁺…θκ✂θι

```

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

```
¿⌊υ

```

If the original number was not palindromic, ...

```
⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ι×²∕ι²

```

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

# Answer
# 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

```
> 4 votes

# Answer
# 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

```
> 3 votes

# Answer
# 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.

```
> 3 votes

# Answer
# 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.
> 3 votes

# Answer
# 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`.
> 2 votes

# Answer
# 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.
> 2 votes

# Answer
# 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!
> 2 votes

# Answer
# 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`.
> 1 votes

---
Tags: code-golf, number, decision-problem, binary, palindrome
---


title: Are We Fast And Furious?

text:
# Question
Title: Are We Fast And Furious?
There are currently nine feature length films in the core *Fast & Furious/The Fast and the Furious* media franchise, a series of films about bald men scowling and driving cars very fast. The names of the films, as can be seen, follow a completely logical and sensible convention:

* *The Fast and the Furious*
* *2 Fast 2 Furious*
* *The Fast and the Furious: Tokyo Drift*
* *Fast & Furious*
* *Fast Five*
* *Fast & Furious 6*
* *Furious 7*
* *The Fate of the Furious*
* *F9*

I'm a Hollywood producer working on the new, tenth *Fast & Furious* film, and I'm struggling to find a title which hasn't yet been used. Please write me a piece of code - as short as possible - which takes in my input string, and returns a truthy value if **any** of the following are true:

1. the input string is already an existing *Fast & Furious* film title
2. the input string differs from an existing *Fast & Furious* film title *only* by replacing an existing number with `ten` or `10`
3. the input string differs from an existing *Fast & Furious* film title *only* by replacing `&` with `and` (or vice versa).

For instance, all of these strings would return a **truthy** value:

* *The Fast and the Furious* (matches check 1)
* *The Fast & the Furious* (matches check 3)
* *Fast and Furious 10* (matches checks 2 and 3)
* *10 Fast 2 Furious* (matches check 2)
* *Furious Ten* (matches check 2)
* *F10* and *FTEN* (match check 2)

And all of these strings would return a **falsy** value:

* *The Fast or The Furious*
* *Fast Times at Ridgemont High*
* *Fast/Furious 10*
* *Too Fast Too Furious*
* *Ten Furious*
* *Fast Ten Furious*
* *The Fast and the Furious: Kyoto Cruise*

*Fate of the Furious*, as a pun, is obviously a tricky case. Unless you're very driven, you don't need to support puns, just exact text matches. If you can create a new *Fast & Furious* film title which is a pun, please share.

**Clarifications**

* The matching is not case-sensitive, so the input string can be in lowercase. The film company design team will work out how to depict your title on the posters anyway, and the answer is 'in red, with speedy lines'.
* I've clarified that the numbering match should only be true if an existing number in the title has been replaced with the string `10` or `ten`.

# Answer
# Python 3, 190 bytes

```
lambda a:re.match("(the '!the %(: tokyo drift)?|(2# ' (2# %|'!%|' (five#|'!% (6#|% (7#|the fate of the %|f(9#)$".translate({33:" (and|&) ",35:"|10|ten)",39:"fast",37:"furious"}),a)
import re

```

Try it online!

A very naive attempt at this.
> 1 votes

---
Tags: code-golf, decision-problem, regular-expression, text-processing
---


title: Donation arms race

text:
# Question
Title: Donation arms race
The barfoos, a hypothetical alien species, go about charity in an interesting way.

Every morning, barfoo Specialists come up with an ordered list of causes to donate to, and for each cause they recommend what quantity of resources should be donated.

That wasn't the weird part. Here's the weird part:

A random civilian barfoo will donate the recommended quantity of resources to the first cause. Another one will likewise donate to the very next cause on the list, and keep going down the list until it has given at least as much as its compatriot, at which point it immediately stops.

This continues, each civilian giving at least as much as *the one directly before*, until the remaining elements of the Great List of Charitable Causes can no longer satisfy this donation arms race, at which point the Specialists themselves just chip in.

**How many civilian barfoos are involved?**

**Input:** a sequence of \\$1\leq n\leq100000\\$ integers each of value \\$1\leq i\leq1000\\$, representing the recommended donation sizes for the Great List of Charitable Causes in the order in which it's given to the barfoos.

**Output:** a single integer representing the number of civilian barfoos who donate something.

## Sample 1

Input: `5 2 3 1 3 4 2 5`

Output: `3`

This may be divided into the buckets `5`, `2 3` (sum 5), `1 3 4` (sum 8) and `2 5` (sum 7, cannot satisfy a fourth civilian barfoo).

## Sample 2

Input: `4 1 2 3 6 6`

Output: `4`

This may be divided into the buckets `4`, `1 2 3` (sum 6), `6` and `6`. (In this case, no Specialists need to involve themselves.)

---

* ; the shortest code in bytes wins.
* The linked rules apply.
* Please explain your code.
* Please link to Try It Online! or another online demo.

---

Credit: 'Nomnomnom' (AIO 2009, Senior)

# Answer
> 8 votes
# Python 2, 60 bytes

```
d=p=t=0
for x in input():
 d-=x
 if d<1:t+=1;p=d=p-d
print t

```

Try it online!

The code is easier to understand in the below version, which is fairly natural: `t` tracks the number of barfoos who donate, `p` tracks the previous donation, and `s` tracks the sum of the current barfoo's donation.

**61 bytes**

```
s=p=t=0
for x in input():
 s+=x
 if s>=p:t+=1;p=s;s=0
print t

```

Try it online!

The original replaces tracking `s` with tracking `d=p-s`, the amount the current barfoo needs to donate to catch up with the previous donation. This lets us replace `s>=p` with `d<1`, saving a byte. Note that `s/p` doesn't work because `p` starts at 0.

# Answer
> 6 votes
# Python 3.8 (pre-release), ~~59~~ ~~57~~ ~~59~~ 58 bytes

Don't mind me, just abusing the walrus

```
lambda y,p=0,d=0:len([p:=(d:=p-d)for x in y if(d:=d-x)<1])

```

Surculose Sputum shaved a byte using xnor's idea to keep track of the remaining amount of donation needed instead of the current donation.

Try it online!

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

```
f=([v,...a],p,s=0)=>v?(s+=v)<p?f(a,p,s):1+f(a,s):0

```

Try it online!

### Commented

```
f = (            // f is a recursive function taking:
  [ v,           //   v = next entry in the input array
    ...a ],      //   a[] = all remaining entries in the input array
  p,             //   p = previous donation, initially undefined
  s = 0          //   s = current donation
) =>             //
  v ?            // if v is defined:
    (s += v)     //   add v to s
    < p ?        //   if the result is less than the previous donation:
      f(a, p, s) //     do a recursive call with the updated s
    :            //   else:
      1 +        //     increment the final result
      f(a, s)    //     do a recursive call with p = s (and s = 0, implicitly)
  :              // else:
    0            //   stop recursion

```

# Answer
> 3 votes
# Jelly, 8 bytes

```
ŒṖ§ṢƑƇḢL

```

A monadic Link accepting a list of numbers which yields a non-negative integer.

**Try it online!** (not efficient)

### How?

```
ŒṖ§ṢƑƇḢL - Link: list
ŒṖ       - all partitions (order is such that those with shorter sublists at the left appear first)
  §      - sums (sum each part of each partition)
     Ƈ   - filter keep those for which:
    Ƒ    -   is invariant under:
   Ṣ     -     sort
      Ḣ  - head
       L - length

```

# Answer
> 3 votes
# Pyth, 8 bytes

```
lesDI#./

```

Try it online!

Form all ordered partitions `./`, then filter `#` for the partitions which are invariant `I` under sorting `D` by sum `s`. Take the last one the survived the filler `e`, which is also the longest due to the order that `./` outputs partitions, and return its length `l`.

This is one of the longest string of prefix modifiers (`DI#`) I've ever used, it's a challenge that fits Pyth quite well.

# Answer
> 2 votes
# Python 2, ~~64~~ 62 bytes

```
f=lambda l,p=1,c=0:c/p and-~f(l,c)or l>[]and f(l[1:],p,c+l[0])

```

Try it online!

A recursive function that takes in a list of integers and returns the number of barfoos.

**How**: `p` and `c` keeps track of the previous donation and the current donation. If the current donation is sufficient, moves to a new barfoo. Otherwise, adds another cause to the current donation.

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
.œ.ΔOD{Q}g

```

Try it online!

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

Port of xnor's Python answer.

```
n;m;s;f(int*l){for(n=m=s=0;*l;s=s<1?++n,m-=s:s)s-=*l++;s=n;}

```

Try it online!

Inputs a zero-terminated integer array.

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

Similar to my JS answer, but with \\$p\\$ and \\$s\\$ declared in the global scope. They are reset to \\$0\\$ on the last iteration to make sure that the function is reusable.

Takes a zero-terminated array of integers as input.

```
p,s;f(int*a){a=!*a?p=s=0:!((s+=*a++)>=p?s-=p=s:1)+f(a);}

```

Try it online!

# Answer
> 1 votes
# PHP, 62 bytes

```
for(;$a=$argv[++$i];)if(($s+=$a)>=$t){$r++;$t=$s;$s=0;}echo$r;

```

Try it online!

Pretty straightforward implementation, saying that "s" is for "sum", "t" for "total" and "r" for "result" should be enough ;)

# Answer
> 0 votes
# \[C#\], 108 bytes

```
f=(i,c,p,s,q)=>{y=c;if(i==L.Length)return;var t=L[i++];p=i==0?t:p;q=s+t>=p;f(i,q?++c:c,q?s+t:p,q?0:s+t,q);};

```

Try It online!

Very verbose recursion implementation, but I'm proud of this ugly baby. Call function with ever greater sum of donations until donation is equal to or greater then increment a counter, and set sum to 0. Increase index (to loop through donations). Return when index is equal to length of donations.

# Answer
> 0 votes
# Charcoal, 41 bytes

```
≔⁰ηＷΦＥθ…θ⊕λ¬‹Σκη«⊞υω≔Σ§ι⁰η≔✂θＬ§ι⁰Ｌθ¹θ»ＩＬυ

```

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

```
≔⁰η

```

Start off with no resources.

```
ＷΦＥθ…θ⊕λ¬‹Σκη«

```

Find out which prefixes of the remaining list contain as least as many resources as the last donation.

```
⊞υω

```

Keep track of how many times a donation was found.

```
≔Σ§ι⁰η

```

Calculate the minimum donation for next time.

```
≔✂θＬ§ι⁰Ｌθ¹θ

```

Remove the recommendations that were donated.

```
»ＩＬυ

```

Print the count of donations.

# Answer
> 0 votes
# Io, 72 bytes

Port of xnor's Python solution.

```
method(I,d :=p :=t :=0;I foreach(x,d=d-x;if(d<1,t=t+1;p=d=p-d))return t)

```

Try it online!

# Answer
> 0 votes
# Perl 5, 35 + 1 bytes

```
$d-=$_;if($d<1){$\++;$p=$d=$p-$d}}{

```

Try it online!

I counted one additional byte for replacing the standard command-line switch `-e` by `-pe`.

This program reads the list of causes from its standard input, one amount per line. When there is nothing left to read, it prints the number of civilian barfoos who donated something.

This is a port of xnor's Python2 solution with a few Perl golfing tricks thrown in. I use the following variables: `$\` tracks the number of barfoos who have successfully donated, `$p` tracks the previous donation, and `$d` tracks the amount that the current barfoo still needs to donate to catch up with the previous donation.

### Slightly more natural, 36 + 1 bytes

```
$s+=$_;if($s>=$p){$\++;$p=$s;$s=0}}{

```

Try it online!

In this version, `$s` counts the sum of what the current barfoo is trying to donate instead of tracking what is still missing (as done with `$d` above).

### Ungolfed and commented

The implementation is simple but it uses a few well-known Perl golfing tips:

* The `-p` switch wraps `while (<>) { ... ; print }` around the program but it does so literally, in a way that allows unmatched curly braces in the code to match those that are added by the wrapper. So `perl -p 'foo}{bar'` becomes `while (<>) { foo } { bar ; print }`. In this codegolf entry, I have an empty `bar` (which is kind of sad, but this is another topic).
* The special variable `$\` is the output record separator for the print operator. Using `print` without arguments would print `$_` followed by `$\`, but `$_` is undefined at the end of the `while` loop, so assigning a value to `$\` is a convenient way to print something at the end of the program.
* Incrementing an undefined variable sets its value to 1. `$\` is undefined by default.

To make the ungolfed code more readable and to make it easier to understand what is printed, here I use a variable `$t` for counting the number of successful donations instead of using the output record separator `$\`. The natural version of the code would look like this:

```
while (<>) {           # Read all input lines (one amount per line).
  $s += $_;            # Add the amount for the current cause to $s.
  if ($s >= $p) {      # If we can match or exceed the last donation,
    $t++;              # then count it and invite the next barfoo.
    $p = $s;
    $s = 0;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

```

...and the slightly optimized version would look like this:

```
while (<>) {           # Read all input lines (one amount per line).
  $d -= $_;            # Subtract the amount from what we need to catch up.
  if ($d < 1) {        # If the difference from the last donation is 0 or lower,
    $t++;              # then count it and invite the next barfoo.
    $d = $p - $d;
    $p = $d;
  }
}                      # When we reach the end of the input,
print $t;              # print the number of barfoos who donated.

```

# Answer
> 0 votes
# MMIX, 52 bytes (13 instrs)

Takes pointer to sequence of 16-bit integers as sole argument, sequence terminated by a 0.

(jelly xxd)

```
00000000: e301 0000 e302 0000 e303 0000 87ff 0000  ẉ¢¡¡ẉ£¡¡ẉ¤¡¡⁷”¡¡
00000010: 42ff 0008 e700 0002 2002 02ff 5102 fffc  B”¡®ḃ¡¡£ ££”Q£”‘
00000020: 2003 0302 3402 0003 e701 0001 f1ff fff8   ¤¤£4£¡¤ḃ¢¡¢ȯ””ẏ
00000030: f802 0000                                ẏ£¡¡

```

**Disassembly and explanation**

```
charity SETL $1,0       // ndonors = 0
        SETL $2,0       // amtleft = 0
        SETL $3,0       // prevdonor = 0
0H      LDWU $255,$0,0  // loop: amt = *causes (causes is const uint16_t *)
        BZ   $255,0F        // if(!amt) goto end
        INCL $0,2       // causes++
        ADD  $2,$2,$255 // amtleft += amt
        PBN  $2,0B      // iflikely(amtleft < 0) goto loop
        ADD  $3,$3,$2   // prevdonor += amtleft
        NEG  $2,0,$3    // amtleft = -prevdonor
        INCL $1,1       // ndonors++
        JMP  0B         // goto loop
0H      POP  2,0        // end: return ndonors

```

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