text:
Palindrome Compression
Challenge
Write a program that compresses and decompresses ASCII text losslessly. It should be specialized to work well with palindromes, including case-insensitive and punctuation-insensitive palindromes. The best compression with the smallest source wins.
Scoring
total_bytes_saved / sqrt(program_size) - Highest score wins
total_bytes_saved is how many bytes smaller the compressed strings are than the originals, total across the test cases below. program_size is the size in bytes of the source code of both the compression and decompression programs. Code shared between the two need only be counted once.
For instance, if there are 10 test cases and a 100 byte program saved 5 bytes on 7 test cases, 10 each on 2 of them, but the last test case was 2 bytes longer, the solution would score 5.3. ((7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3)
Test Cases

tacocat
toohottohoot
todderasesareddot
amanaplanacanalpanama
wasitacaroracatisaw?
Bob
IManAmRegalAGermanAmI
DogeeseseeGod
A Santa at NASA
Go hang a salami! I'm a lasagna hog.

Rules

Standard loopholes apply.
The compression must work on all printable ASCII (bytes 32-126, inclusive) text strings, not just palindromes. It doesn't actually have to save space for any inputs, however.
Output can be any sequence of bytes or characters, regardless of its implementation or internal representation (strings, lists, and arrays are all fair game, for instance). If encoding to UTF-8, count bytes, not characters. Wide strings (e.g. UTF-16 or UTF-32) are not allowed unless the only codepoints possibly used are between 0 and 255.
Compression/Decompression builtins are not allowed.

For the sake of our own enjoyment, post the compressed strings with your source code.
UPDATE 1: Scoring changed from total_bytes_saved / program_size to total_bytes_saved / sqrt(program_size) in order to give more weight to better compression and less weight to aggressive golfing. Adjust your scores accordingly.
UPDATE 2: fixed wasitacaroraratisaw? to be wasitacaroracatisaw?

If case, punctuation and spacing is removed from the the input, is it guaranteed that inputs will be strict palindromes? Edit: nevermind - I see the wasitacaroraratisaw? is a counterexample to that

Which range of ASCII characters are we supposed to support in the input? Is it [32-126]?

Yeah I don't think the 1000 * part is really needed, and no I don't think it will make the score feel more "satisfying" ;)

Can we use compression/decompression built-ins?

@Arnauld: I want to say 0-127, but just the printables sounds fine. Gives you an extra 32 values you can use for compression control codes. So yeah, [32-126]

@Lynn I'm going to say no on that.

@DLosc: I didn't realize I didn't have an even-length palindrome in there. Good catch. (if only someone had noticed in the sandbox)

With so few inputs, there is not much scope for doing anything clever. It would be nice to have at least a few times more.

Here are a few more test cases I think would be a good addition–two longer all-letter palindromes, a long mixed palindrome, a very long, very mixed palindrome, and a short non-palindrome (to ensure entries can work on non-palindromes).

I'm thinking I need to change the scoring to give more weight to the bytes saved. Maybe I should sqrt the program length...

I like this scoring system much better. (Also, I only noticed now that wasitacaroraratisaw? is not a palindrome... sneaky sneaky!)

@ETHproductions Oh. You're right. I actually missed that. It actually should be wasitacaroracatisaw? I remembered the palindrome wrong.

Incidentally, DigitalTrauma noticed that one and I didn't realize it wasn't actually a palindrome even after he pointed it out.

@Beefster Oh :P Compressed 6 more bytes for free, thanks!

A man, a plan, a God's 'nam. Tables, nitrate, tar, tinsel, Batman's dog: Anal Panama -- 1632

@Blacksilver my own solution saved 22 bytes on that one.

JavaScript (ES6), 3.143 (81 bytes saved, 664 byte program)
R='replace',S=String.fromCharCode,T=c=>c.charCodeAt(),U='toUpperCase',V='0000000',W=(a,b,c=2)=>a.toString(c).slice(b),X=x=>'0b'+x,Y=a=>[...a].reverse().join``,Z=/[^]/g
C=s=>S(...((Y(q=s[U]()[R](/[^A-Z]/g,m=''))==q?(q=q.slice(0,p=-~q.length/2),p%1&&10):11)+q[R](Z,x=>W(T(x),2))+111+s[R](Z,c=>/[a-z]/.test(c)?W("00",m,m=1):m+(/[A-Z]/.test(c,m='')?"01":W(c<'!'?2:T(c)+384)))+V).match(/(?!0+$).{8}/g).map(X))
D=s=>{s=s[R](Z,c=>W(256+T(c),1))+V;M=r=>(s=s[R](p=s.match(`^${r}|`)[0],''),p);for([,a]=M`1.|0`,t=u=i='';!M`111`;)t+=W(X(M`.{5}`)-~8,0,36);for(t+=W(Y(t),a?a/0:1);p;)u+=M`0(?=00)|00?1`?(c=t[i++])?+p[1]?c[U]():c:'':M`10`?' ':M`11`&&S(X(M`.{7}`));return u+W(t,i)}

Now that I'm fairly satisfied with this program (and the scoring system), I'll write a bit of an explanation.
The basic idea is to compress the input into a string of bits, then compress each set of 8 bits into a byte. For the purposes of explanation, I'll just manipulate the bit string.
The bit string can be separated into several sections:
input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

0      | 10100 00001 00011 01111 111 | 01 00001 10 01 0001 110101110
header | letter data                 | styling data

The header is a very simple mapping:
0  -> odd-length palindrome
10 -> even-length palindrome
11 -> non-palindrome

Letter data is also fairly simple. First, all non-letters are extracted from the string, and all letters are converted to uppercase. If the resulting string is a palindrome, the reversed half is stripped. Then this mapping is applied:
A -> 00001
B -> 00010
C -> 00011
D -> 00100
...
Z -> 11010

This section is terminated with 111. After that comes the styling data, which stores upper/lower-case data and non-letters. This works like so:
01 -> next letter as uppercase
0...01 (n 0s) -> next (n-1) letters as lowercase
10 -> space
11xxxxxxx -> character with code point 0bxxxxxxx

So going through the example shown above, we have
header: 0 -> palindrome
letter data: 10100 00001 00011 01111 111 -> taco
styling data:
  01        -> T
  00001     -> aco
  10        -> <space>
  01        -> C
  0001      -> at
  110101110 -> .

When the end of the bit string is reached, all remaining characters from the letter data are appended to the result. This saves us from having to do one last 000...001 and allows us to truncate these bits from the string.
Going through the test cases:
tacocat -> 3 bytes (-4)
    24 bits: 010100000010001101111111
toohottohoot -> 5 bytes (-7)
    35 bits: 10101000111101111010000111110100111
todderasesareddot -> 7 bytes (-10)
    49 bits: 0101000111100100001000010110010000011001100101111
amanaplanacanalpanama -> 8 bytes (-13)
    59 bits: 00000101101000010111000001100000110000001011100000100011111
wasitacaroracatisaw? -> 11 bytes (-9)
    84 bits: 010111000011001101001101000000100011000011001001111111000000000000000000001110111111
Bob -> 2 bytes (-1)
    16 bits: 0000100111111101
IManAmRegalAGermanAmI -> 13 bytes (-8)
    98 bits: 00100101101000010111000001011011001000101001110000101100111010100010100101000001010100000010100101
DogeeseseeGod -> 7 bytes (-6)
    54 bits: 000100011110011100101001011001100101111010000000000101
A Santa at NASA -> 8 bytes (-7)
    63 bits: 100000110011000010111010100000011110110010000011000011001010101
Go hang a salami! I'm a lasagna hog. -> 20 bytes (-16)
   154 bits: 1000111011110100000001011100011100001100110000101100000010110101001111010011000000110001100000000111010000110011101001110011000110000000001100000111010111

Wow. I'm really impressed by this approach. I would have never thought to make a bit-packed encoding like this. (I did think of the case of packing ASCII into 7 bits, but doesn't save much space for palindromes) I'm impressed that you managed to save space on Bob as well.

This is a great example of the fundamentals of engineering. Taking a problem description, thinking about different ways to solve it, and making tradeoffs between requirements (ie how many bits to dedicate to various styles), etc

@Beefster Thanks :-) Bob really just fell into place--1 bit for the header, 10+3 bits for the two letters, and 2 bits for the single uppercase letter. Couldn't get it any shorter if I tried my hardest...

I'm not entirely sure, but can't -~8 be golfed to +9? Or is ~ used differently here than ~x → -x-1? No idea if that single saved byte would even increase the score at all though, but still.. ;)

@KevinCruijssen the problem is that the thing being added to is a string, so it has to converted to a number first. This way is a byte shorter than -0+9

@ETHproductions Ah of course (didn't notice it was a string)! +9 would concat to the string, while -~8 would do +9 arithmetically (since - doesn't do anything for strings, so it interpret it as a number). In that case -~8 is pretty smart. :) Nice answer btw, +1 from me! Very smart storing all the information in bits like that, even saving a byte on Bob.

Python 2: 2.765 (70 bytes saved, 641 byte program)
I changed my approach a little. It now works well on imperfect palindromes. There are no compressed strings that will be longer than the input. Perfect even-length palindromes will always compress to 50% the original size.
A=lambda x:chr(x).isalpha()
def c(s):
 r=bytearray(s);q=len(r);L=0;R=q-1;v=lambda:R+1<q and r[R+1]<15
 while L<=R:
  while not A(r[L])and L<R:L+=1
  while not A(r[R])and R:
   if v()and r[R]==32:r[R]=16+r.pop(R+1)
   R-=1
  j=r[L];k=r[R]
  if A(j)*A(k):
   if L!=R and j&31==k&31:
    r[L]+=(j!=k)*64;r[R]=1
    if v():r[R]+=r.pop(R+1)
   else:r[L]|=128;r[R]|=128
  L+=1;R-=1
 while r[-1]<16:r.pop()
 return r
def d(s):
 r='';t=[]
 for o in s:
  if 15<o<32:r+=' ';o-=16
  while 0<o<16:r+=chr(t.pop());o-=1
  if o==0:continue
  if 127<o<192:o-=64;t+=[o^32]
  elif o>192:o-=128
  elif A(o):t+=[o]
  r+=chr(o)
 while t:r+=chr(t.pop())
 return r

Results
'tacocat' <==> 'tac\xef'
4/7 (3 bytes saved)
'toohottohoot' <==> 'toohot'
6/12 (6 bytes saved)
'todderasesareddot' <==> 'todderas\xe5'
9/17 (8 bytes saved)
'amanaplanacanalpanama' <==> 'amanaplana\xe3'
11/21 (10 bytes saved)
'wasitacaroracatisaw?' <==> 'wasita\xe3ar\xef\x09?'
12/20 (8 bytes saved)
'Bob' <==> '\x82\xef'
2/3 (1 bytes saved)
'IManAmRegalAGermanAmI' <==> 'I\x8d\xa1n\x81m\x92e\xa7\xa1\xec'
11/21 (10 bytes saved)
'Dogeeseseegod' <==> '\x84ogees\xe5'
7/13 (6 bytes saved)
'A Santa at NASA' <==> 'A S\xa1\xaeta\x12\x14'
9/15 (6 bytes saved)
"Go hang a salami! I'm a lasagna hog." <==> "\x87o hang a salam\xa9!\x11'\x01\x11\x17\x13."
24/36 (12 bytes saved)

And as a bonus, it saves 6 bytes on my incorrect palindrome I had before.
'wasita\xe3ar\xef\x02\xf2\x06?' <==> 'wasitacaroraratisaw?'
6 bytes saved

Explanation
Decompression uses a stack. Codepoints from 32-127 are treated literally. If a character is a letter, a value is pushed onto the stack as well. Values 128-192 are used for case flipped letters, so the caseflipped letter (o^32 because of how ASCII is laid out) gets pushed onto the stack and the normal letter gets added to the string. Values 192-255 are used to add letters without pushing to the stack, so this is used when letters do not match and for the middle letter in odd-length palindromes. Codepoints 1-15 indicate that the stack should be popped that number of times. Codepoints 17-31 are similar, but they print a space first before popping from the stack. There is also an implicit "pop until empty" instruction at the end of an input.
The compressor works from both ends and folds in matching letters as values 1-31. It skips over non-letters. When the letters match but the case does not, it adds 64 to the left letter and increments the right letter. This allows it to save space on IManAmRegalAGermanAmI. At the middle or when the letters do not match, it ors 128 to both sides. I can't add there because I need to avoid the special case where left == right. When folding neighboring pop markers on the right side, I have to check that the neighboring one won't overflow into codepoint 16 because I need that for spaces. (This is not actually an issue for any of the test case strings)
EDIT 1: No more ungolfed version.

Python3, 1.833 (25 bytes saved, 186 byte program)
Just simple 0-order equal-probability entropy coding. No palindrome-specific optimizations.
def C(s):
    u=0
    for c in s:u=u*96+ord(c)-31
    return u.to_bytes((u.bit_length()+7)//8,'big')
def D(a):
    u,s=int.from_bytes(a,'big'),''
    while u:s,u=s+chr((u%96)+31),u//96
    return s[::-1]

Java 8, score: 1.355 (20 bytes saved / 218 (107+111) bytes)
Compress function (contains three unprintable ASCII characters):
s->{int l=s.length();return s.contains(new StringBuffer(s).reverse())?s.substring(l/2)+(l%2<1?"":""):s;}

Decompress function (contains two unprintable ASCII characters):
s->{return s.contains("")?new StringBuffer((s=s.replaceAll("","")).substring(s.length()&1^1)).reverse()+s:s;}

Explanation:
Try it online.
Only compresses perfect palindromes.
s->{                      // Method with String as both parameter and return-type
  int l=s.length();       //  Get the length of the input
  return s.contains(new StringBuffer(s).reverse())?
                          //  If the input is a palindrome:
    s.substring(l/2)      //   Only return the second halve of the String
    +(l%2<1?"":"")        //   + either one (if even) or two (if odd) unprintables
   :                      //  Else:
    s;}                   //   Simply return the input again

s->{                      // Method with String as both parameter and return-type
  return s.contains("")?  //  If the input contains an unprintable:
    new StringBuffer((s=s.replaceAll("",""))
                          //   Remove the unprintables
                     .substring(s.length()&1^1))
                          //   And take either the full string (if even),
                          //   or minus the first character (if odd)
    .reverse()            //    And reverse that part
    +s                    //   And append the rest of the input (minus the unprintables)
   :                      //  Else:
    s;}                   //   Simply return the input again


text:
Bracket Expansion!
Your challenge is to expand some brackets in a program's input as shown:

Find a string s between two matching brackets [ and ], with a single digit n after the closing bracket.
Remove the brackets.
Replace s with itself repeated n times. (If n is 0, simply remove s.)
Go to step 1 until there are no more matching brackets in the input.

Additional rules and clarifications:

You will take input and give output via any allowed means.
A trailing newline in the output is allowed.
You only need to handle printable ASCII in the input.
You may assume that all brackets match, i.e. you will never receive the input []]]] or [[[[].
You may assume that each closing bracket ] has a digit after it.

Test cases:
Input                -> Output
[Foo[Bar]3]2         -> FooBarBarBarFooBarBarBar
[one]1[two]2[three]3 -> onetwotwothreethreethree
[three[two[one]1]2]3 -> threetwoonetwoonethreetwoonetwoonethreetwoonetwoone
[!@#[$%^[&*(]2]2]2   -> !@#$%^&*(&*($%^&*(&*(!@#$%^&*(&*($%^&*(&*(
[[foo bar baz]1]1    -> foo bar baz
[only once]12        -> only once2
[only twice]23456789 -> only twiceonly twice3456789
[remove me!]0        ->
before [in ]2after   -> before in in after

As this is code-golf, the shortest answer in each language wins. Good luck!

Sandboxed post.

You should post another challenge to compress a string back down to its shortest format

Is it worth stating explicitly that your string s should never contain other brackets? For example, attempting to solve [Foo[Bar]3]2 by expanding the string Foo[Bar 3 times would result in an invalid state Foo[BarFoo[BarFoo[Bar]2

@BradC that all depends on how you choose to implement the task.

Does that mean that there are two valid answers to [a[b]2c[d]2e]2? You get abbcddeabbcdde by expanding b and d first, but ababcdbcdedbabcdbcdede by expanding a[b and d]2e first.

@BradC Ah. Clarified that they should be matching brackets.

Simpler example: [[a]2[b]2]2 expands to either aabbaabb or aababbaababb depending on how exactly you pair up the brackets. This is an anomaly, though, for most other test cases, you end up with mismatched pairs. Not sure that "matching" entirely conveys the distinction here, but I get the point. Thanks.

Suggested test case: [']3 => '''

Gema, 17 characters
[#]?=@repeat{?;#}

Sample run:
bash-4.4$ gema '[#]?=@repeat{?;#}' <<< '[three[two[one]1]2]3'
threetwoonetwoonethreetwoonetwoonethreetwoonetwoone

Wow, talk about finding the right language for the job!

Or the right job for the language. Many challenges had to skip because the recursive argument was not flexible enough.

Accepting this for now cause I don't see any way it's getting beat, but it'll be unaccepted in the unlikely case that it does.

Retina, 24 23 22 bytes
+`\[([^][]*)](.)
$2*$1

Try it online! This is practically a builtin in Retina 1. Edit: Saved 1 byte thanks to @Kobi. 47 45 bytes in Retina 0.8.2:
].
]$&$*¶
{+`\[([^][]*)]¶
$1[$1]
\[([^][]*)]

Try it online!

Haskell, 101 96 bytes
fst.(""%)
infix 4%
s%']':d:r=(['1'..d]>>s,r)
s%'[':r|(t,q)<-""%r=s++t%q
s%x:r=s++[x]%r
s%e=(s,e)

Try it online! Instead of using regular expression like most of the other answers, this implements a recursive parser.
-5 bytes thanks to BMO!

A fixity declaration for (%) saves you 1 byte and ['1'..d] saves you another 4, see this.

@BMO Nice, I didn't expect a fixity declaration would ever be useful for code golfing. I think you should add that to the tips question.

Perl 5, 34 33 29 + 1 (-p) = 30 bytes
s/.([^[]*?)](.)/$1x$2/e&&redo

Try it online!
Cut it down with some help from @Shaggy and @TonHospel.

I don't know pearl but redo seems gorgeous!

I think you should be able to save a byte by not escaping the ].

I don't know Perl but this seems to work for 30+1 bytes.

These 29+1 also work: perl -pe 's/.([^[]*?)](.)/$1x$2/e&&redo' and perl -pe 's/.([^][]*)](.)/$1x$2/e&&redo'

Japt v2, 21 20 19 bytes
Saved 2 bytes thanks to @Shaggy
e/.([^[]*?)](./@YpZ

Test it online!
e is recursive replace, which makes one replacement at a time until there are no more matches. In this case, matches of the regex /\[([^[]*?)](\d)/g are replaced with with <inner text> repeated <digit> times until there are no more matches.
According to what I have planned (here), this regex should eventually be at least 3 2 bytes shorter:
‹[“⁽[»₋”]“.›

As we "may assume that each closing bracket ] has a digit after it" you should be able to replace (\d with (..

You can also replace \[ with .

@Shaggy Nice, thanks!

Scala, 173 bytes
l.foreach{x=>def r(c:String):String={val t="""\[([^\[\]]*)\](.)""".r.unanchored;c match{case t(g,h)=>r(c.replaceAllLiterally(s"[$g]$h",g*h.toInt));case _=>c}};println(r(x))}

Try it online!
Expanded:
l.foreach { x =>
  def remove(current: String): String = {
    val test ="""\[([^\[\]]*)\](.)""".r.unanchored
    current match {
      case test(g, h) => remove(current.replaceAllLiterally(s"[$g]$h", g * h.toInt))
      case _ => current
    }
  }

  println(remove(x))
}

Old solution
Scala, 219 215 213 212 199 bytes
l.foreach{x=>def r(c:String):String={"""\[([^\[\]]*)\](.)""".r.findFirstMatchIn(c).map{x=>val g=x.group(1);val h=x.group(2).toInt;r(c.replaceAllLiterally(s"[$g]$h",g*h))}.getOrElse(c)};println(r(x))}

Try it online!
Expanded:
l.foreach { x =>
  def remove(current: String): String = {
    """\[([^\[\]]*)\](.)""".r.findFirstMatchIn(current).map { x =>
      val g = x.group(1)
      val h = x.group(2).toInt
      remove(current.replaceAllLiterally(s"[$g]$h", g * h))
    }.getOrElse(current)
  }
  println(remove(x))
}

Where l is the list of strings that we will process.
Thanks  Kevin Cruijssen for -1 byte
Went from 212 to 199 by removing an unused parameter, didn't pay attention.

Welcome to PPCG! Try tio's scala interpreter at https://tio.run/#scala and see if you can submit a link for the answer, so that others can try it online. :)

Thank you! I edited the answer to include the link. Hopefully it is ok how the header, code and footer is declared in order to be a proper submission.

Hi, welcome to PPCG! Great first answer, +1 from me. I think you can save 1 byte by changing (\d) to (.), because we know a block-bracket ] is always followed by a digit.

JavaScript, 71 67 66 bytes
I had a 54 byte solution but it got screwed over by the second test case! :(
f=s=>s!=(x=s.replace(/.([^[]*?)](.)/,(_,y,z)=>y.repeat(z)))?f(x):x

Test Cases

f=s=>s!=(x=s.replace(/.([^[]*?)](.)/,(_,y,z)=>y.repeat(z)))?f(x):x
o.innerText=`[Foo[Bar]3]2
[one]1[two]2[three]3
[three[two[one]1]2]3
[!@#[$%^[&*(]2]2]2
[[foo bar baz]1]1
[only once]12
[only twice]23456789
[remove me!]0
before [in ]2after`.split`\n`.map(x=>x.padEnd(22)+`:  `+f(x)).join`\n`

Python 3, 110 93 92 bytes
import re
f=lambda s:f(re.sub(r'\[([^][]+)\](.)',lambda m:m[1]*int(m[2]),s))if'['in s else s

Try it online!
-17 bytes thanks to pizzapants184
-1 byte thanks to Kevin Cruijssen

-17 bytes in Python 3 with re.match indexing and substring check using in.

-1 byte by changing (\d) to (.), because we know a block-bracket ] is always followed by a digit.

Python 3, 155 148 101 97 bytes
def f(x):
 a=x.rfind('[')
 if~a:b=x.find(']',a);x=f(x[:a]+x[a+1:b]*int(x[b+1])+x[b+2:])
 return x

Try It Online
Thanks to HyperNeutrino and Mego for -47 bytes and user202729 for -4 bytes.

Make it a one-liner to save a couple bytes: def f(x):a=x.rfind('[');b=x.find(']',a);return f(x[:a]+x[a+1:b]*int(x[b+1])+x[b+2:])if~a else x

Stacked, 39 38 bytes
Saved 1 byte thanks to Shaggy, golfed the regex!
['\[([^[\]]+)](.)'{.y x:x#~y*}recrepl]

Try it online!
Simply recursively replaces a regex '\[([^[\]]+)](.)' with the repetition rule.

I think you can save a byte by not escaping the last ].

JavaScript - 77 75 72 bytes
f=a=>a.replace(/(.*)\[([^[]*?)](.)(.*)/,(a,b,c,d,e)=>f(b+c.repeat(d)+e))

Edit: updated regex with Shaggy's recommendation
Snippet:

const test = ["[Foo[Bar]3]2", "[one]1[two]2[three]3", "[three[two[one]1]2]3", "[!@#[$%^[&*(]2]2]2", "[[foo bar baz]1]1", "[only once]12", "[only twice]23456789", "[remove me!]0", "before [in ]2after"];

const f=a=>a.replace(/(.*)\[([^[]*?)](.)(.*)/,(a,b,c,d,e)=>f(b+c.repeat(d)+e))

d.innerHTML=test.map(f).join("
");

Welcome to PPCG! You can get this down to 70 bytes by tweaking your RegEx.

Yes, 72 bytes, obviously, sorry; I was forgetting to count the f=!

QuadR with the ≡ argument, 30 28 bytes
\[[^[]+?].
∊(⍎⊃⌽⍵M)⍴⊂1↓¯2↓⍵M

Try it online!
\[[^[]+?]. replace "[non-[ stuff]character" with
¯2↓⍵M drop the last two characters of the Match ("]digit")
1↓ drop the first character ("[")
⊂ enclose to be treated as a whole
(…)⍴ reshape to length:
 ⌽⍵M reverse the Match
 ⊃ pick the first (the digit)
 ⍎ evaluate
∊ ϵnlist (flatten)
≡ repeat until no more changes happen

The equivalent Dyalog APL function is 47 bytes:
'\[[^[]+?].'⎕R{∊(⍎⊃⌽⍵.Match)⍴⊂1↓¯2↓⍵.Match}⍣≡

Try it online!

C, 407 368 bytes
Thanks to Jonathan Frech for saving bytes.
golfed (file bracket.c):
i,j,k,l,n;char*f(a,m)char*a;{for(i=0;a[i];++i){a[i]==91&&(j=i+1);if(a[i]==93){k=a[i+1]-48;if(!k){for(l=i+2;l<m;)a[++l-i+j-4]=a[l];a=realloc(a,m-3);return f(a,m-3);}for(l=j;l<i;)a[~-l++]=a[l];for(l=i+2;l<m;)a[++l-4]=a[l];m-=3;n=m+~-k*(i---j--);a=realloc(a,n);for(l=i;l<m;)a[l+++~-k*(i-j)]=a[l];for(m=0;m<k;++m)for(l=j;l<i;)a[l+++m*(i-j)]=a[l];return f(a,n);}}return a;}

ungolfed with program:
#include <stdlib.h>
#include <stdio.h>

// '[' = 133
// ']' = 135
// '0' = 48

i, j, k, l, n;

char* f(a,m) char*a;
{
  for (i=0; a[i]; ++i) {
    a[i]==91&&(j=i+1);

    if (a[i]==93) {
      k=a[i+1]-48;

      if (!k) {
        for (l=i+2; l<m; )
          a[++l-i+j-4] = a[l];

        a = realloc(a,m-3);
        return f(a,m-3);
      }
      for (l=j;l<i;)
        a[~-l++] = a[l];
      for (l=i+2; l<m; )
        a[++l-4] = a[l];
      m -= 3;
      n = m+~-k*(i---j--);
      a = realloc(a,n);

      for (l=i; l<m; )
        a[l+++~-k*(i-j)] = a[l];
      for (m=0; m<k; ++m)
        for (l=j; l<i;)
          a[l+++m*(i-j)] = a[l];

      return f(a,n);
    }
  }
  return a;
}

int main()
{
  char c[]="[Foo[Bar]3]2";
  char *b;

  char cc[]="[remove me!]0";
  char *bb;

  char ccc[]="[only once]12";
  char *bbb;

  b=malloc(13);
  bb=malloc(14);
  bbb=malloc(14);

  for (i=0; i<13; ++i)
    b[i] = c[i];

  for (i=0; i<14; ++i)
    bb[i] = cc[i];

  for (i=0; i<14; ++i)
    bbb[i]=ccc[i];

  printf("%s\n", f(b, 13));
  printf("%s\n", f(bb, 14));
  printf("%s\n", f(bbb, 14));

  return 0;
}

Compiled with gcc 5.4.1, gcc bracket.c

368 bytes.

387 with the needed include (for realloc). I will do a clean update (with the ungolfed version) later.
Thanks

If you use GCC, I think the compiler will attempt to guess the definition of both malloc and realloc, including stdlib.h by its own.

I didn't know that. Nice feature for code golfing. Thanks.

Java 8, 250 249 241 239 bytes
s->{for(;s.contains("[");)for(int i=0,j,k;i<s.length();)if(s.charAt(i++)==93){String t="",r=t;for(j=k=s.charAt(i)-48;j-->0;)t+=s.replaceAll(r="(.*)\\[([^\\]]+)\\]"+k+"(.*)","$2");s=k<1?t:s.replaceFirst(r,"$1$3").replace("",t);}return s;}

-2 bytes thanks to @JonathanFrech (code contains two unprintable ASCII characters now, which can be seen in the TIO-link below).
Sigh... Java with regex is so damn limited.. I'll just quote myself from another answer here:

Replacing WWWW with 222W is easy in Java, but with 4W not.. If only Java had a way to use the regex capture-group for something.. Getting the length with "$1".length(), replacing the match itself with "$1".replace(...), converting the match to an integer with new Integer("$1"), or using something similar as Retina (i.e. s.replaceAll("(?=(.)\\1)(\\1)+","$#2$1")) or JavaScript (i.e. s.replaceAll("(.)\\1+",m->m.length()+m.charAt(0))) would be my number 1 thing I'd like to see in Java in the future to benefit codegolfing.. >.> I think this is the 10th+ time I hate Java can't do anything with the capture-group match..
Quote from here.

Explanation:
Try it online.
s->{                           // Method with String as both parameter and return-type
  for(;s.contains("[");)       //  Loop as long as the String contains a block-bracket
    for(int i=0,j,k;i<s.length();)
                               //   Inner loop over the characters of the String
      if(s.charAt(i++)==93){   //    If the current character is a closing block-bracket:
        String t="",r=t;       //     Create two temp-Strings, starting empty
        for(j=k=s.charAt(i)-48;//     Take the digit after the closing bracket
            j-->0;)            //     Loop that many times:
          t+=s.replaceAll(r="(.*)\\[([^\\]]+)\\]"+k+"(.*)","$2");
                               //      Append `t` with the word inside the block brackets
        s=k<1?                 //     If the digit was 0:
           t                   //      Replace the input with an empty String as well
          :                    //     Else:
           s.replaceFirst(r,"$1$3").replace("",t);}
                               //      Replace the word between brackets by `t`,
                               //      and remove the digit
  return s;}                   //  Return the modified input-String as result

I think you can use a truly ASCII though unprintable character to save two bytes. (Your solution really takes 241 bytes, 239 characters.)

@JonathanFrech Thanks! Was looking for a 1-byte character outside the printable ASCII range. Didn't thought about using an unprintable..

Red, 147 bytes
f: func[t][a: charset[not"[]"]while[parse t[any a some[remove["["copy h any a"]"copy d a](insert/dup v: copy""h to-integer d)insert v | skip]]][]t]

Ungolfed:
f: func [t][
    a: charset [not "[]"]                          ; all chars except [ and ]
    while [ parse t [                              ; repeat while parse is returning true
        any a                                      ; 0 or more chars other than [ and ]
        some [                                     ; one or more block:
            remove ["[" copy h any a "]" copy d a] ; remove the entire block, store the
                                                   ; substring between the [] in h,
                                                   ; the digit into d
            (insert/dup v: copy "" h to-integer d) ; makes d copies of h
            insert v                               ; and inserts them in place
            | skip ]                               ; skip if no match
        ]
    ][]                                            ; empty block for 'while'
    t                                              ; return the modified string
]

I started learning Red's Parse dialect only yesterday, so I'm sure my code can be improved further. Parse is incomparably more verbose than regex, but is very clear, flexible and readable and can be freely mixed with the rest of the Red language.
Try it online!

Wolfram Language (Mathematica), 86 bytes
#//.s_:>StringReplace[s,"["~~x:Except["["|"]"]...~~"]"~~d_:>""<>x~Table~FromDigits@d]&

Try it online!

C,381 bytes
Compact version:
while(1){int t=strlen(i);int a,c=-1;char*w;char*s;char*f;while(c++<t){if(i[c]==']'){int k=c-a;w=calloc((k--),1);memcpy(w,&i[a+1],k);s=calloc((t-c-1),1);memcpy(s,&i[c+2],t-c-2);i[a]=0;int r=i[c+1]-48;if(r==0){f=calloc(t,1);sprintf(f,"%s%s",i,s);}else{f=calloc((t+k),1);sprintf(f,"%s%s[%s]%d%s",i,w,w,r-1,s);}free(i);i=f;break;}else if(i[c]=='[')a=c;}free(w);free(s);if(c>=t)break;}

Full version:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void proceed(char* input)
{
  while(1)
  {
    int t=strlen(input);
    int start,cursor=-1;
    char* word;
    char* suffix;
    char* final;
    while(cursor++<t)
    {
      if(input[cursor]==']')
      {
        int wordlength = cursor-start;
        word=calloc((wordlength--),sizeof(char));
        memcpy(word, &input[start+1], wordlength );
        suffix=calloc((t-cursor-1),sizeof(char));
        memcpy( suffix, &input[cursor+2], t-cursor-2 );
        input[start]='\0';
        int rep=input[cursor+1]-'0';
        if(rep==0)
        {
          final=calloc(t,sizeof(char));
          sprintf(final,"%s%s",input,suffix);
        }
        else
        {
          final=calloc((t+wordlength+5),sizeof(char));
          sprintf(final,"%s%s[%s]%d%s",input,word,word,rep-1,suffix);
        }
        free(input);
        input=final;
        break;
      }
      else if(input[cursor]=='[')
        start=cursor;
    }
    free(word);
    free(suffix);

    if(cursor>=t)break;
  }
}

int main()
{
  char* input=calloc(256,sizeof(char));
  sprintf(input,"a[[toto]2b]2[ana]3");
  printf("in : %s\n",input);
  proceed(input);
  printf("out: %s\n",input);
  return 0;
}

Welcome to PPCG!

Welcome to the site! Note that C submissions need to be full programs or functions, not just snippets.

Jelly, 30 bytes
œṡ”]µḢUœṡ”[ẋ€1¦Ṫ©Ḣ$FṚ;®
Çċ”]$¡

Try it online!

Explanation.

œṡ”]µḢUœṡ”[ẋ€1¦Ṫ©Ḣ$FṚ;®    Helper link 1, expand once.
                           Assume input = "ab[cd]2ef".

œṡ      Split at first occurence of
  ”]      character "]".
    µ   Start new monadic chain. Value = "ab[cd","2ef".

Ḣ       Ḣead. "ab[cd"
 U      Upend. "dc[ba"
  œṡ”[  Split at first occurence of "[". | "dc","ba".

ẋ€        Repeat ...
  1¦        the element at index 1...
          by ...
    Ṫ Ḣ$    the Ḣead of the Ṫail of ...
          the input list ("ab[cd","2ef") (that is, 2)

          The command Ḣ also pop the head '2'. The remaining
            part of the tail is "ef".
     ©    Meanwhile, store the tail ("ef") to the register.

          Current value: "dcdc","ba"
FṚ        Flatten and Ṛeverse. | "abcdcd"
  ;®      Concatenate with the value of the register. "abcdcdef"

Çċ”]$¡    Main link.

 ċ”]$     Count number of "]" in the input.
     ¡    Repeatedly apply...
Ç           the last link...
            that many times.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Check if all non-zero elements in a matrix are connected
Input:
A matrix containing integers in the range [0 - 9].
Challenge:
Determine if all non-zero elements are connected to each other vertically and/or horizontally.
Output:
A truthy value if all are connected, and a falsy value if there are non-zero elements/groups that aren't connected to other elements/groups.
Test cases:
Test cases are separated by line. Test cases can be found in more convenient formats here (Kudos to Dada).
The following are all connected and should return a truthy value:
0
---
0 0
---
1 1 1
0 0 0
---
1 0 0
1 1 1
0 0 1
---
0 0 0 0 0 0
0 0 3 5 1 0
0 1 0 2 0 1
1 1 0 3 1 6
7 2 0 0 3 0
0 8 2 6 2 9
0 0 0 0 0 5

The following are all not-connected, and should return a falsy value:
0 1
1 0
---
1 1 1 0
0 0 0 2
0 0 0 5
---
0 0 5 2
1 2 0 0
5 3 2 1
5 7 3 2
---
1 2 3 0 0 5
1 5 3 0 1 1
9 0 0 4 2 1
9 9 9 0 1 4
0 1 0 1 0 0

This is code-golf, so the shortest submission in each language wins. Explanations are encouraged!

Inspired by this challenge.

Perhaps the input should contain only ones and zeros (or truthys and falsys), as this is essentially about connected components.

Can we take input as an 1d array and a number of columns?

@ovs sure. I can't see that it should give you any advantages over other people that have already answered.

Related: how many zeroes do you need to change to make all nonzero elements connected

Related: count the number of components (but with diagonal entries adjacent).

Related

MATL, 7 bytes
4&1ZI2<

This gives a matrix containing all ones as truthy output, or a matrix containing at least a zero as falsy. Try it online!
You can also verify truthiness/falsiness adding an if-else branch at the footer; try it too!
Or verify all test cases.
Explanation
4       % Push 4 (defines neighbourhood)
&       % Alternative input/output specification for next function
1ZI     % bwlabeln with 2 input arguments: first is a matrix (implicit input),
        % second is a number (4). Nonzeros in the matrix are interpreted as
        % "active" pixels. The function gives a matrix of the same size
        % containing positive integer labels for the connected components in
        % the input, considering 4-connectedness
2<      % Is each entry less than 2? (That would mean there is only one
        % connected component). Implicit display

OP's note: in case there's any doubt: the outputs are perfectly fine and adheres to the linked meta post.

It's blowing my mind that MATL/matlab considers an array of numbers to be truthy IFF it contains no zeros. http://www.mathworks.com/help/matlab/ref/if.html (earlier comment deleted)

@Sparr (Actually, it is iff it contains no zeros and is not empty.) I was also confused when I learned that any nonempty array is truthy in other languages

Retina 0.8.2, 80 77 74 bytes
T`d`@1
1`1
_
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)$))(?!\3)[1_]
$1_$4_
^\D+$

Try it online! Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation:
T`d`@1

Simplify to an array of @s and 1s.
1`1
_

Change one 1 to a _.
+m`^((.)*)(1|_)( |.*¶(?<-2>.)*(?(2)$))(?!\3)[1_]
$1_$4_

Flood fill from the _ to adjacent 1s.
^\D+$

Test whether there are any 1s left.

@FryAmTheEggman Thanks, and you gave me an idea as to how to save another two bytes too!

Wolfram Language (Mathematica), 54 bytes
Saved 2 bytes thanks to user202729.
Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&

Try it online!

JavaScript (ES6), 136 135 bytes
Returns a boolean.
m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

Test cases

let f =

m=>!/[1-9]/.test((g=(y,x=0)=>1/(n=(m[y]||0)[x])&&!z|n?(m[y++][x]=0,z=n)?g(y,x)&g(--y-1,x)&g(y,x+1)||g(y,x-1):g(m[y]?y:+!++x,x):m)(z=0))

console.log('[Truthy]')

console.log(f([
  [0]
]))
console.log(f([
  [0,0]
]))
console.log(f([
  [1,1,1],
  [0,0,0]
]))
console.log(f([
  [1,0,0],
  [1,1,1],
  [0,0,1]
]))
console.log(f([
  [0,0,0,0,0,0],
  [0,0,3,5,1,0],
  [0,1,0,2,0,1],
  [1,1,0,3,1,6],
  [7,2,0,0,3,0],
  [0,8,2,6,2,9],
  [0,0,0,0,0,5]
]))

console.log('[Falsy]')

console.log(f([
  [0,1],
  [1,0]
]))
console.log(f([
  [1,1,1,0],
  [0,0,0,2],
  [0,0,0,5]
]))
console.log(f([
  [0,0,5,2],
  [1,2,0,0],
  [5,3,2,1],
  [5,7,3,2]
]))
console.log(f([
  [1,2,3,0,0,5],
  [1,5,3,0,1,1],
  [9,0,0,4,2,1],
  [9,9,9,0,1,4],
  [0,1,0,1,0,0]
]))

Commented
The recursive function g() first looks for a non-zero cell (as long as the globally-defined flag z is set to 0) and then starts flood-filling from there (as soon as z != 0).
m =>                               // given the input matrix m
  !/[1-9]/.test((                  // test whether there's still a non-zero digit
    g = (y, x = 0) =>              //   after recursive calls to g(), starting at (x=0,y=0):
      1 / (n = (m[y] || 0)[x]) &&  //     n = current cell; if it is defined:
      !z | n ? (                   //       if z is zero or n is non-zero:
          m[y++][x] = 0,           //         we set the current cell to zero
          z = n                    //         we set z to the current cell
        ) ?                        //         if z is non-zero:
          g(y, x) &                //           flood-fill towards bottom
          g(--y - 1, x) &          //           flood-fill towards top
          g(y, x + 1) ||           //           flood-fill towards right
          g(y, x - 1)              //           flood-fill towards left
        :                          //         else:
          g(m[y] ? y : +!++x, x)   //           look for a non-zero cell to start from
      :                            //       else:
        m                          //         return the matrix
    )(z = 0)                       //   initial call to g() + initialization of z
  )                                // end of test()

APL (Dyalog Unicode), 36 22 bytesSBCS
~0∊∨.∧⍨⍣≡2>+/|↑∘.-⍨⍸×⎕

Try it online!
thanks @H.PWiz
⍸×⎕ coordinates of non-zero squares
2>+/|↑∘.-⍨ adjacency matrix of the neighbour graph
∨.∧⍨⍣≡ transitive closure
~0∊ is it all 1s?

C, 163 bytes
Thanks to @user202729 for saving two bytes!
*A,N,M;g(j){j>=0&j<N*M&&A[j]?A[j]=0,g(j+N),g(j%N?j-1:0),g(j-N),g(++j%N?j:0):0;}f(a,r,c)int*a;{A=a;N=c;M=r;for(c=r=a=0;c<N*M;A[c++]&&++r)A[c]&&!a++&&g(c);return!r;}

Loops through the matrix until it finds the first non-zero element. Then stops looping for a while and recursively sets every non-zero element connected to the found element to zero. Then loops through the rest of the matrix checking if every element is now zero.
Try it online!
Unrolled:
*A, N, M;

g(j)
{
    j>=0 & j<N*M && A[j] ? A[j]=0, g(j+N), g(j%N ? j-1 : 0), g(j-N), g(++j%N ? j : 0) : 0;
}

f(a, r, c) int*a;
{
    A = a;
    N = c;
    M = r;

    for (c=r=a=0; c<N*M; A[c++] && ++r)
        A[c] && !a++ && g(c);

    return !r;
}

Jelly, 23 bytes
FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3

Try it online!

Explanation.
The program labels each morphological components with a different numbers, then check if there are less than 3 numbers. (including 0).
Consider a row in the matrix.
«Ḋo   Given [1,2,3,0,3,2,1], return [1,2,3,0,2,1,1].
«     Minimize this list (element-wise) and...
 Ḋ      its dequeue. (remove the first element)
      So min([1,2,3,0,3,2,1],
             [2,3,0,3,2,1]    (deque)
      ) =    [1,2,0,0,2,1,1].
  o   Logical or - if the current value is 0, get the value in the input.
         [1,2,0,0,2,1,1] (value)
      or [1,2,3,0,3,2,1] (input)
      =  [1,2,3,0,2,1,1]

Repeatedly apply this function for all row and columns in the matrix, in all orders, eventually all morphological components will have the same label.
µ«Ḋoµ€ZUµ4¡ÐL  Given a matrix with all distinct elements (except 0),
               label two nonzero numbers the same if and only if they are in
               the same morphological component.
µ«Ḋoµ          Apply the function above...
     €           for €ach row in the matrix.

      Z        Zip, transpose the matrix.
       U       Upend, reverse all rows in the matrix.
               Together, ZU rotates the matrix 90° clockwise.
         4¡    Repeat 4 times. (after rotating 90° 4 times the matrix is in the
               original orientation)
           ÐL  Repeat until fixed.

And finally...
FJṁa@ ... FQL<3   Main link.
F                 Flatten.
 J                Indices. Get `[1,2,3,4,...]`
  ṁ               ṁold (reshape) the array of indices to have the same
                  shape as the input.
   a@             Logical AND, with the order swapped. The zeroes in the input
                  mask out the array of indices.
      ...         Do whatever I described above.
          F       Flatten again.
           Q      uniQue the list.
            L     the list of unique elements have Length...
             <3   less than 3.

Imaginary bounty if you can do it in linear time. I think it's not possible in Jelly, even ¦ takes O(n).

(without Python eval, of course)

Haskell, 132 bytes
 \m->null.snd.until(null.fst)(\(f,e)->partition(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f])e).splitAt 1.filter((/=0).(m!)).indices$m

extracted from Solve Hitori Puzzles
indices m lists the (line,cell) locations of the input grid.
filter((/=0).(m!)) filters out all locations with non-zero values.
splitAt 1 partitions off the first member into a singleton list next to a rest list.
any(==1)[(b-d)^2+(p-q)^2|(d,q)<-f] tells if (b,p) touches the frontier f.
\(f,e)->partition(\(b,p)->touches(b,p)f)e splits off touchers from  not[yet]touchers.
until(null.fst)advanceFrontier repeats this until the frontier can advance no further.
null.snd looks at the result whether all locations to be reached were indeed reached.
Try it online!

Perl, 80 79 78 73 70 bytes
Includes +2 for 0a
Give the input matrix without spaces on STDIN (or in fact as rows separated by any kind of whitespace)
perl -0aE 's%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/'
000000
003510
010201
110316
720030
082629
000005
^D

Easier to read if put in a file:
#!/usr/bin/perl -0a
use 5.10.0;
s%.%$".join"",map chop,@F%seg;s%\b}|/%z%;y%w-z,-9%v-~/%?redo:say!/}/

Java 8, 226 219 207 205 201 bytes
int[][]M;m->{int c=0,l=m[0].length,i=m.length*l;for(M=m;i-->0;)c+=m[i/l][i%l]>0?f(i/l,i%l):0;return c<2;}int f(int x,int y){try{M[x][y]*=M[x][y]>0?f(x+f(x,y+f(x-f(x,y-1),y)),y)-1:1;}finally{return 1;}}

-2 bytes thanks to @ceilingcat.
Try it online.
Explanation:
int[][]M;              // Integer-matrix on class-level, uninitialized
m->{                   // Method with integer-matrix parameter & boolean return
  int c=0,             //  Amount of non-zero islands, starting at 0
      l=m[0].length,   //  Amount of columns in the matrix
      i=m.length*l;    //  Index integer
  for(M=m;             //  Set the class-level matrix to the input
      i-->0;)          //  Loop over the cells
    c+=                //   Increase the count by:
       m[i/l][i%l]>0?  //    If the current cell is not 0:
        f(i/l,i%l)     //     Flood-fill the matrix with a separated method
                       //     And increase the count by 1
       :               //    Else:
        0;             //     Leave the count the same
  return c<2;}         //  Return whether 0 or 1 islands are found

// Separated recursive method with cell input & integer return
int f(int x,int y){
  try{m[x][y]*=M[x][y]>0?
                       //  If the current cell is not 0:
           f(m,x,y-1)  //   Recursive call west
          f(m,x-...,y) //   Recursive call north
         f(m,x,y+...)  //   Recursive call east
        f(m,x+...,y)   //   Recursive call south
        -1:1;}         //   Empty the current cell
  }finally{            //  Catch and swallow any ArrayIndexOutOfBoundsExceptions
                       //  (shorter than manual if-checks)
           return 1;}  //  Always result in 1, so we use it to our advantage
                       //  to save bytes here by nesting, instead of having four
                       //  loose calls to each direction)

Grime, 37 bytes
C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
e`C|:\0

Prints 1 for match and 0 for no match.
Try it online!
Explanation
The nonterminal C matches any nonzero character that is connected to the first nonzero character of the matrix in the English reading order.
C=[,0]&<e/\0{/e\0*0$e|CoF^0oX
C=                             A rectangle R matches C if
  [,0]                         it is a single character other than 0
      &                        and
       <                       it is contained in a rectangle S which matches this pattern:
        e/\0{/e\0*0$e           R is the first nonzero character in the matrix:
        e                        S has an edge of the matrix over its top row,
         /0{/                    below that a rectangle of 0s, below that
             e\0*0$e             a row containing an edge, then any number of 0s,
                                 then R (the unescaped 0), then anything, then an edge.
                    |CoF^0oX    or R is next to another match of C:
                     CoF         S is a match of C (with fixed orientation)
                        ^0       followed by R,
                          oX     possibly rotated by any multiple of 90 dergees.

Some explanation: e matches a rectangle of zero width or height that's part of the edge of the input matrix, and $ is a "wildcard" that matches anything.
The expression e/\0{/e\0*0$e can be visualized as follows:
+-e-e-e-e-e-e-e-+
|               |
|      \0{      |
|               |
+-----+-+-------+
e \0* |0|   $   e
+-----+-+-------+

The expression CoX^0oX is actually parsed as ((CoF)0)oX; the oF and oX are postfix operators and concatenation of tokens means horizontal concatenation.
The ^ gives juxtaposition a higher precedence then oX, so the rotation is applied to the entire sub-expression.
The oF corrects the orientation of C after it is rotated by oX; otherwise it could match the first nonzero coordinate in a rotated English reading order.
e`C|:\0
e`       Match entire input against pattern:
    :    a grid whose cells match
  C      C
   |     or
     \0  literal 0.

This means that all nonzero characters must be connected to the first one.
The grid specifier : is technically a postfix operator, but C|:\0 is syntactic sugar for (C|\0):.

Python 2, 211 163 150 bytes
m,w=input()
def f(i):a=m[i];m[i]=0;[f(x)for x in(i+1,i-1,i+w,i-w)if(x>=0==(i/w-x/w)*(i%w-x%w))*a*m[x:]]
f(m.index((filter(abs,m)or[0])[0]))<any(m)<1>q

Try it online!
Output is via exit code. Input is as an 1d list and the width of the matrix.

JavaScript (Node.js), 115 102 bytes
A=>w=>(A.find(F=(u,i)=>u&&[-w,-1,1,w].map(v=>v*v>1|i%w+v>=0&i%w+v<w&&F(A[v+=i],v),A[i]=0)),!+A.join``)

Try it online!
Receive input as (1d-array)(width). Rewrites all entries in one of the connected non-zero regions with 0 and checks whether the resultant array is a zero matrix. The matrix will become zero if there is zero or one connected non-zero region.
A=>                         // all rows are concatenated into an 1-d array
 w=>                        // width of the original matrix
  (
   A.find(                  // find the first non-zero entry
    F=(                     // helper function
     u,                     // value of the entry
     i                      // index of the entry
    )=>
     u                      // return 0 if value is 0 or out of range
     &&[-w,-1,1,w].map(     // return an array otherwise, and find the neighbors
      v=>                   // for each neighbor
       v*v>1                // if y-coord change: let go anyway
       |i%w+v>=0&i%w+v<w    // if x-coord change: let go only if on the same row
       &&F(A[v+=i],v),      // recurse on the neighbor
      A[i]=0                // before recursing change the current entry to 0
     )
   ),                       // if all entries were 0, no change is made
   !+A.join``               // return whether all entries are now 0
  )                         // if all entries are 0, then +A.join`` == 0

Tip: Use Array.prototype.find if you want to map through an array with a function that the return values can be ignored but to stop once the function is executed.
In this case, I want to map through the array to change only the first connected non-zero region found, but not the other regions (otherwise the array will become a zero matrix no matter what the original input is), so find is used here to save some bytes.

JavaScript (Node.js), 96 bytes
f=(A,P,Q)=>!A.map((B,i)=>B.map((C,j)=>(P-i)**2+(Q-j)**2-1|!C||f(A,i,j,A[i][j]=0,P=0+[P])))|P>'0'

Try it online!
P = 0 if 1 chunk, 00 if 2 chunk, to allow call inside

Uiua, 31 bytes
/×♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.

Try it online!
The same approach as ngn's APL answer.
∧↧1♭⍥'∺'/↥↧.⧻.⊠(≤1/+⌵-).▽♭∶/⊂⇡△.    input: a matrix(n,m)
▽♭∶/⊂⇡△.  collect coordinates of positive numbers:
       ⇡△     coordinates of each position in the matrix (n,m,2)
     /⊂       reduce by join; flatten the first two dimensions
  ♭∶      .    original matrix flattened
▽             keep: for each number n in the matrix, get n copies of its coords
⊠(≤1/+⌵-).  create adjacency matrix:
⊠(      ).    self cross product over the coordinates:
   ≤1/+⌵-      sum of absolute difference is 1 or less?
⍥'∺'/↥↧.⧻.  get transitive closure:
⍥       ⧻.    run <length of the array> times:
  '∺'/↥↧.      self matrix product, using min as product and max as sum
/×♭         test if it is all ones

05AB1E, 42 bytes
Ā©˜ƶ®gäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]˜0KÙg!

Input as a matrix of integers; output as a 05AB1E truthy/falsey value (only \$1\$ is truthy in 05AB1E, so if the result is \$\geq2\$ it's falsey).
Try it online or verify all test cases.
Explanation:
Uses the same flood-fill algorithm I've used in multiple other challenges.
Ā             # Convert each positive integer in the (implicit) input-list to 1s
 ©            # Store this matrix in variable `®` (without popping)
  ˜           # Flatten it to a single list
   ƶ          # Multiply each by its 1-based index to make all values unique
    ®gä       # Convert it back to a matrix with the dimensions of `®`
Δ             # Loop until it no longer changes to flood-fill:
 2Fø0δ.ø}     #  Add a border of 0s around the matrix:
 2F     }     #   Loop 2 times:
   ø          #    Zip/transpose; swapping rows/columns
     δ        #    Map over each row:
    0 .ø      #     Add a leading/trailing 0
 2Fø€ü3}      #  Convert it into overlapping 3x3 blocks:
 2F    }      #   Loop 2 times again:
   ø          #    Zip/transpose; swapping rows/columns
    €         #    Map over each inner list:
     ü3       #     Convert it to a list of overlapping triplets
 ®*           #  Multiply each 3x3 block by the value in matrix `®`
              #  (so the 0s remain 0s)
 εεÅsyøÅs«à   #  Get the largest value from the horizontal/vertical cross of each 3x3
              #   block:
 εε           #   Nested map over each 3x3 block:
   Ås         #     Pop and push its middle row
     y        #     Push the 3x3 block again
      ø       #     Zip/transpose; swapping rows/columns
       Ås     #     Pop and push its middle rows as well (the middle column)
         «    #     Merge the middle row and column together to a single list
          à   #     Pop and push its maximum
]             # Close the nested maps, flood-fill loop, and outer loop
 ˜            # Flatten the resulting flood-filled matrix
  0K          # Remove all 0s
    Ù         # Uniquify the values of each island
     g        # Pop and push its length (which is 1 if it was a single island)
      !       # Factorial to convert 0 to 1 (and 1 remains 1), since 0 is also truthy
              # (after which the result is output implicitly)

Vyxal 3, 8 bytes
Þoᵛᵛa?∧₌

Try it Online!
Þoᵛᵛa?∧₌
Þo        # grid neighbors
  ᵛᵛa     # any truthy?
     ?∧   # Logical and with input
       ₌  # equals input

Created with the help of Luminespire.

Perl 5, 131 129 + 2 (-ap) = 133 bytes
push@a,[@F,0]}{push@a,[(0)x@F];$\=1;map{//;for$j(0..$#F){$b+=$a[$'][$j+$_]+$a[$'+$_][$j]for-1,1;$\*=$b||!$a[$'][$j];$b=0}}0..@a-2

Try it online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Remove entries from array to sort it and maximize sum of elements
This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills.
Task
Write a program that removes entries from an array so that the remaining values are sorted in a strictly decreasing order and their sum is the maximized among all other possible decreasing sequences.
Input and Output
Input will be an array of integer values strictly greater than 0 and all different from each other.
You are free to choose whether to read input from file, command line or stdin.
Output will be a descending-sorted subarray of the input one, whose sum is greater than any other possible descending-sorted subarray.
Note: [5, 4, 3, 2] is a subarray of [5, 4, 1, 3, 2], even if 4 and 3 are not adjacent. Just because the 1 was popped.
Bruteforce solution
The simplest solution of course would be iterate among all possible combinations of the given array and search for a sorted one with the greatest sum, that would be, in Python:
import itertools

def best_sum_desc_subarray(ary):
    best_sum_so_far = 0
    best_subarray_so_far = []
    for k in range(1, len(ary)):
        for comb in itertools.combinations(ary, k):
            if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
                best_subarray_so_far = list(comb)
                best_sum_so_far = sum(comb)
    return best_subarray_so_far

Unfortunately, since checking if the array is sorted, and calculating the sum of it's elements is  and since this operation will be done  times for  from  to , the asymptotic time complexity will be

Challenge
Your goal is to achieve a better time complexity than the bruteforce above. The solution with the smallest asymptotic time complexity is the winner of the challenge. If two solutions have the same asymptotic time complexity, the winner will be the one with the smallest asymptotic spatial complexity.
Note: You can consider reading, writing and comparing atomic even on large numbers.
Note: If there are two or more solutions return either of them.
Test cases
Input:  [200, 100, 400]
Output: [400]

Input:  [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]

Input:  [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]

Input:  [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]

Input:  [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]

Input:  [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]

Input:  [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]

Related. (I can't check right now whether the two algorithms are in fact equivalent, but I think they might be.)

Comments are not for extended discussion; this conversation has been moved to chat.

@AndersKaseorg I completely overlooked it. Thanks for pointing it out.

Haskell, \$O(n \log n)\$ time, \$O(n)\$ space
{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -> F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.>< sNew F.<| right'
  where
    (left, right) = F.split (\s -> sArr s > [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -> sSum s > sSum sNew) right

bestSubarray :: [Int] -> [Int]
bestSubarray = sArr . F.measure . bestSubarrays

How it works
bestSubarrays xs is the sequence of subarrays of xs that are on the efficient frontier of {largest sum, smallest first element}, ordered from left to right by increasing sum and increasing first element.
To go from bestSubarrays xs to bestSubarrays (x:xs), we

split the sequence into a left side with first elements less than x, and a right side with first elements greater than x,
find a new subarray by prepending x to the rightmost subarray on the left side,
drop the prefix of subarrays from the right side with smaller sum than the new subarray,
concatenate the left side, the new subarray, and the remainder of the right side.

A finger tree supports all these operations in \$O(\log n)\$ time.

Perl
This should be O(n^2) in time and O(n) in space
Give numbers separated by space on one line to STDIN
#!/usr/bin/perl -a
use strict;
use warnings;

# use Data::Dumper;
use constant {
    INFINITY => 9**9**9,
    DEBUG    => 0,
};

# Recover sequence from the 'how' linked list
sub how {
    my @z;
    for (my $h = shift->{how}; $h; $h = $h->[1]) {
        push @z, $h->[0];
    }
    pop @z;
    return join " ", reverse @z;
}

use constant MINIMUM => {
    how  => [-INFINITY, [INFINITY]],
    sum  => -INFINITY,
    next => undef,
};

# Candidates is a linked list of subsequences under consideration
# A given final element will only appear once in the list of candidates
# in combination with the best sum that can be achieved with that final element
# The list of candidates is reverse sorted by final element
my $candidates = {
    # 'how' will represent the sequence that adds up to the given sum as a
    # reversed lisp style list.
    # so e.g. "1, 5, 8" will be represented as [8, [5, [1, INFINITY]]]
    # So the final element will be at the front of 'how'
    how  => [INFINITY],
    # The highest sum that can be reached with any subsequence with the same
    # final element
    sum  => 0,
    # 'next' points to the next candidate
    next => MINIMUM,   # Dummy terminator to simplify program logic
};

for my $num (@F) {
    # Among the candidates on which an extension with $num is valid
    # find the highest sum
    my $max_sum = MINIMUM;
    my $c = \$candidates;
    while ($num < $$c->{how}[0]) {
        if ($$c->{sum} > $max_sum->{sum}) {
            $max_sum = $$c;
            $c = \$$c->{next};
        } else {
            # Remove pointless candidate
            $$c = $$c->{next};
        }
    }

    my $new_sum = $max_sum->{sum} + $num;
    if ($$c->{how}[0] != $num) {
        # Insert a new candidate with a never before seen end element
        # Due to the unique element rule this branch will always be taken
        $$c = { next => $$c };
    } elsif ($new_sum <= $$c->{sum}) {
        # An already known end element but the sum is no improvement
        next;
    }
    $$c->{sum} = $new_sum;
    $$c->{how} = [$num, $max_sum->{how}];
    # print(Dumper($candidates));
    if (DEBUG) {
        print "Adding $num\n";
        for (my $c = $candidates; $c; $c = $c->{next}) {
            printf "sum(%s) = %s\n", how($c), $c->{sum};
        }
        print "------\n";
    }
}

# Find the sequence with the highest sum among the candidates
my $max_sum = MINIMUM;
for (my $c = $candidates; $c; $c = $c->{next}) {
    $max_sum = $c if $c->{sum} > $max_sum->{sum};
}

# And finally print the result
print how($max_sum), "\n";

This answer expands on Ton Hospel's one.
The problem can be solved with dynamic programming using the recurence
$$
T(i) = a_i + \max \left[ \{0\} \cup \{ T(j) | 0 \leq j < i \wedge a_i \leq a_j \} \right ]
$$
where \$(a_i)\$ is the input sequence and \$T(i)\$ the maximally achievable sum of any decreasing sub-sequence ending with index \$i\$.  The actual solution may then be retraced using \$T\$, as in the following rust code.
fn solve(arr: &[usize]) -> Vec<usize> {
    let mut tbl = Vec::new();
    // Compute table with maximum sums of any valid sequence ending
    // with a given index i.
    for i in 0..arr.len() {
        let max = (0..i)
            .filter(|&j| arr[j] >= arr[i])
            .map(|j| tbl[j])
            .max()
            .unwrap_or(0);
        tbl.push(max + arr[i]);
    }
    // Reconstruct an optimal sequence.
    let mut sum = tbl.iter().max().unwrap_or(&0).clone();
    let mut limit = 0;
    let mut result = Vec::new();

    for i in (0..arr.len()).rev() {
        if tbl[i] == sum && arr[i] >= limit {
            limit = arr[i];
            sum -= arr[i];
            result.push(arr[i]);
        }
    }
    assert_eq!(sum, 0);
    result.reverse();
    result
}

fn read_input() -> Vec<usize> {
    use std::io::{Read, stdin};
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    s.split(|c: char| !c.is_numeric())
        .filter(|&s| !s.is_empty())
        .map(|s| s.parse().unwrap())
        .collect()
}

fn main() {
    println!("{:?}", solve(&read_input()));
}

Try it online!


text:
Can square tree rings be generated from primes?
Apparently yes! In three easy steps.
Step 1
Let f(n) denote the prime-counting function (number of primes less than or equal to n).
Define the integer sequence s(n) as follows. For each positive integer n,

Initiallize t to n.
As long as t is neither prime nor 1, replace t by f(t) and iterate.
The number of iterations is s(n).

The iterative process is guaranteed to end because f(n) < n for all n.
Consider for example n=25. We initiallize t = 25. Since this is not a prime nor 1, we compute f(25), which is 9. This becomes the new value for t. This is not a prime nor 1, so we continue: f(9) is 4. We continue again: f(4) is 2. Since this is a prime we stop here. We have done 3 iterations (from 25 to 9, then to 4, then to 2). Thus s(25) is 3.
The first 40 terms of the sequence are as follows. The sequence is not in OEIS.
0 0 0 1 0 1 0 2 2 2 0 1 0 2 2 2 0 1 0 3 3 3 0 3 3 3 3 3 0 3 0 1 1 1 1 1 0 2 2 2

Step 2
Given an odd positive integer N, build an N×N array (matrix) by winding the finite sequence s(1), s(2), ..., s(N2) to form a square outward spiral. For example, given N = 5 the spiral is
s(21)   s(22)   s(23)   s(24)   s(25)
s(20)   s(7)    s(8)    s(9)    s(10)
s(19)   s(6)    s(1)    s(2)    s(11)
s(18)   s(5)    s(4)    s(3)    s(12)
s(17)   s(16)   s(15)   s(14)   s(13)

or, substituting the values,
 3       3       0       3       3
 3       0       2       2       2
 0       1       0       0       0
 1       0       1       0       1
 0       2       2       2       0

Step 3
Represent the N×N array as an image with a grey colour map, or with some other colour map of your taste. The map should be gradual, so that the order of numbers corresponds to some visually obvious order of the colours. The test cases below show some example colour maps.
The challenge
Given an odd positive integer N, produce the image described above.
Rules

The spiral must be outward, but can be clockwise or counter-clockwise, and can start moving right (as in the above example), left, down or up.

The scales of the horizontal and vertical axes need not be the same. Also axis labels, colorbar and similar elements are optional. As long as the spiral can be clearly seen, the image is valid.

Images can be output by any of the standard means. In particular, the image may be displayed on screen, or a graphics file may be produced, or an array of RGB values may be output. If outputting a file or an array, please post an example of what it looks like when displayed.

Input means and format are flexible as usual. A program or a function can be provided. Standard loopholes are forbidden.

Shortest code in bytes wins.

Test cases
The following images (click for full resolution) correspond to several values of N. A clock-wise, rightward-first spiral is used, as in the example above. The images also illustrate several valid colour maps.

N = 301:

N = 501:

N = 701:

If an array of values of s(n) can be fed into some plotting function/package without being modified (I think imshow in matplotlib could handle this for example) is this an acceptable output form?

@dylnan Sure, as long as it plots the image on screen or produces a file it's valid. In fact I generated the examples with something similar to what you mention. Just be careful with the scaling of values. For example it's not acceptable if all values above 1 are given the same color, as Matlab's (and possibly Matplotlib's) imshow does

good point. Not sure if imshow does that.

i am so confused. What is going on?

@Christopher Is there anything in the challenge I should clarify?

Related to spiral.

Related -- prime counting function

How did you come up with this challenge?

@kamoroso94 Please see here

@LuisMendo I just don't understand how step one works at all. I find the notation confusing,"iteratively replace t by f(t) until the result is either prime or 1." is the hardest part

@Christopher I have changed that phrase and explained the example step by step. Clearer now?

Yeah very clear

Dyalog APL, 94 bytes
'P2'
2⍴n←⎕
9
(⍪0){×≢⍵:(≢⍺)((⍉∘⌽⍺,↑)∇↓)⍵⋄⍺}2↓{⍵⌊1+⍵[+\p]}⍣≡9×~p←1=⊃+/(≠⍨,≠⍨,~⍴⍨(×⍨n)-2×≢)¨,\×⍳n

assumes ⎕IO=0
output for n=701 (converted from .pgm to .png):

MATLAB - 197 185 178 175 184 163 162 148 142 140 bytes
Shaved 12 bytes, thanks to Ander and Andras, and lots thanks to Luis for putting the two together. Shaved 16 thanks to Remco, 6 thanks to flawr
function F(n)
p=@primes
s=@isprime
for a=2:n^2
c=0
if~s(a)
b=nnz(p(a))
while~s(b)
b=nnz(p(b))
c=c+1
end
end
d(a)=c
end
imagesc(d(spiral(n)))

Result for N=301 (F(301)):

Explanation:
function F(n)
p=@primes % Handle
s=@isprime % Handle
for a=2:n^2 % Loop over all numbers
    c=0 % Set initial count
    if~s(a) % If not a prime
        b=nnz(p(a)) % Count primes
        while~s(b) % Stop if b is a prime. Since the code starts at 2, it never reaches 1 anyway
            b=nnz(p(b)) % count again
            c=c+1 % increase count
        end
    end
    d(a)=c % store count
end
imagesc(d(spiral(n))) % plot

Wolfram Language (Mathematica), 124 bytes
Thanks to Martin Ender for saving 12 bytes!
Image[#/Max@#]&[Array[(n=0;Max[4#2#2-Max[+##,3#2-#],4#
#-{+##,3#-#2}]+1//.x_?CompositeQ:>PrimePi[++n;x];n)&,{#,#},(1-#)/2]]&

Try it online!

The image generated is:

Closed form formula of the spiral value taken directly from this answer of mine.

#/2-.5 saves a byte.

Haha, are you suggesting that to yourself?

@user202729 Doesn't seem to work.

I didn't mean to interrupt your inner dialogue :-P

Defer the definition of p until you need it: ...,{y,p=(1-#)/2,-p},{x,p,-p}

Scratch that, using Array instead of Table saves a lot more: https://tio.run/##NcrNCoJAFEDhvU8hXpB@Zqoxt0ERLYIKi6DF5QZDjTrQpIwTGOKzmxHtDh/HSJcrI52@yS5ddFsjM4Uw3ct6CRTiylr5xrNFcT2oyl1y/VA7XTlMrDYq0awfMYYIIv6tMQCb9w3EYhgBb37AIWppLNi6MGVRaaeORFyErAEGLRsIDsNpRBR22mT@wk9RzAR5m7osrMOgx0n5zALm90Xe6fXEoK7v/t@p@wA

And another two by avoiding NestWhileList: https://tio.run/##NchNC4IwGADgu79CfEG0zc88JfZBdOgQWNfxEqPUdtgUW7AQf7sZ0e3hkVw/Ksm1uPGpLqaj5E3FIDpxswV02a7v@Zt5qojzuVgGKaTBVwSALmcD0gwWEAy/CCAdkSRRFJrrZt/Krn0KXZ1X67IXsioFI0TlBnPlu3QACiP1kgD8KEV0JyEbu7BrlsQJWgfTtb1mzpxhpxqH2rPQurwUc4y52//H6QM

MATLAB: 115 114  110 bytes
One liner (run in R2016b+ as function in script) 115 bytes
I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end;end

Putting the function in a separate file, as suggested by flawr, and using the 1 additional byte per additional file rule
In the file s.m, 64 + 1 bytes for code + file
function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end

Command window to define I, 45 bytes
I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)))

Total: 110 bytes

This uses recursion instead of while looping like the other MATLAB implementations do (gnovice, Adriaan). Run it as a script (in R2016b or newer), this defines the function I which can be run like I(n).
Structured version:
% Anonymous function for use, i.e. I(301)
% Uses arrayfun to avoid for loop, spiral to create spiral!
I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));

% Function for recursively calculating the s(n) value
function k=s(n,k)
    % Condition for re-iterating. Otherwise return k unchanged
    if n>1 && ~isprime(n)
        % Increment k and re-iterate
        k = s( nnz(primes(n)), k+1 );
    end
end

Example:
I(301)

Notes:

I tried to make the s function anonymous too, of course that would reduce the count significantly. However, there are 2 issues:

Infinite recursion is hard to avoid when using anonymous functions, as MATLAB doesn't have a ternary operator to offer a break condition. Bodging a ternary operator of sorts (see below) also costs bytes as we need the condition twice.
You have to pass an anonymous function to itself if it is recursive (see here) which adds bytes.

The closest I came to this used the following lines, perhaps it can be changed to work:

    % Condition, since we need to use it twice
    c=@(n)n>1&&~isprime(n);
    % This uses a bodged ternary operator, multiplying the two possible outputs by
    % c(n) and ~c(n) and adding to return effectively only one of them
    % An attempt was made to use &&'s short-circuiting to avoid infinite recursion
    % but this doesn't seem to work!
    S=@(S,n,k)~c(n)*k+c(n)&&S(S,nnz(primes(n)),k+1);

MATLAB - 126 121* bytes
I attempted a more vectorized approach than Adriaan and was able to shave more bytes off. Here's the single-line solution:
function t(n),M=1:n^2;c=0;i=1;s=@isprime;v=cumsum(s(M));while any(i),i=M>1&~s(M);c=c+i;M(i)=v(M(i));end;imagesc(c(spiral(n)))

And here's the nicely-formatted solution:
function t(n),
  M = 1:n^2;
  c = 0;
  i = 1;
  s = @isprime;
  v = cumsum(s(M));
  while any(i),         % *See below
    i = M > 1 & ~s(M);
    c = c+i;
    M(i) = v(M(i));
  end;
  imagesc(c(spiral(n)))

*Note: if you're willing to allow a metric crapton of unnecessary iterations, you can change the line while any(i), to for m=v, and save 5 bytes.

Nice! I like how you use cumsum to vectorize and avoid nnz(primes(...)

If I understand correctly, it doesn't hurt to iterate more times than necessary (at the cost of speed). So you can replace while any(i) by for m=M. Who cares if the code takes hours to run :-)

@LuisMendo: Sure, why not? It already iterates once more than needed, what's another n^2 or so iterations gonna hurt! ;)

That's the spirit! You can also keep the faster-running version, but the byte count is that of the shorter

Python 3, 299 265 bytes
Saved 5 bytes thanks to formatting suggestions from Jonathan Frech and NoOneIsHere.
Removed an additional 34 bytes by removing a function definition that was only called once.
This is a little longer than some others, due to python not having a command to determine primeness, or spiral an array.  It runs relatively quickly however, around a minute for n = 700.
from pylab import*
def S(n):
 q=arange(n*n+1);t=ones_like(q)
 for i in q[2:]:t[2*i::i]=0
 c=lambda i:0 if t[i]else 1+c(sum(t[2:i]));S=[c(x)for x in q]
 t=r_[[[S[1]]]]
 while any(array(t.shape)<n):m=t.shape;i=multiply(*m)+1;t=vstack([S[i:i+m[0]],rot90(t)])
 return t

Test it with
n = 7
x = S(n)
imshow(x, interpolation='none')
colorbar()
show(block=False)

Possible 294 bytes (untested).

One quick thing: you can remove the space between import and *.

J, 121 Bytes
load 'viewmat'
a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1'

Defines a function:
a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1' | Full fuction
                                                                     (,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1  | Creates the number spiral
              {:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0                                      | Applies S(n) to each element
       viewmat                                                                                | View the array as an image

R, 231 bytes
function(n){p=function(n)sum(!n%%2:n)<2;M=matrix(0,n,n);M[n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))]=sapply(1:(n^2),function(x){y=0;while(x>2&!p(x)){x=sum(sapply(2:x,p));y=y+1};y});image(M)}

Slightly less golfed:
function(n){
    p=function(n)sum(!n%%2:n)<2 #"is.prime" function
    M=matrix(0,n,n)             #empty matrix
    indices=n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))
    values=sapply(1:(n^2),function(x){
        y=0
        while(x>2&!p(x)){
            x=sum(sapply(2:x,p))
            y=y+1
            }
        y})
    M[indices]=values
    image(M) #Plotting
}

Anonymous function. Output in a graphic window. Scale is on the red-scale with darkest shade equals to 0 and clearer shades increasing values.
Result for n=101:

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Tell me how to flop
As computer scientists, you're probably all familiar with the basic list operations of pop and push. These are simple operations that modify a list of elements. However, have you ever heard of the operation flop? (as in flip-flop)? It's pretty simple. Given a number n, reverse the first n elements of the list. Here's an example:
>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

The cool thing about the flop operation, is that you can use it do some cool things to a list, such as sorting it. We're going to do something similar with flops:

Given a list of integers, "Neighbor it". In other words, sort it so that every duplicate element appears consecutively.

This can be done with flops! For example, take the following list:
>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

This leads us to the definition of today's challenge:

Given a list of integers, output any set of flops that will result in the list being neighbored.

Using the last list as an example, you should output:
4
3
6

because flopping the list by 4, then by 3, then by 6 will result in a neighbored list. Keep in mind that you do not need to print the shortest possible list of flops that neighbors a list. If you had printed:
4
4
4
3
1
1
6
2
2

instead, this would still be a valid output. However, you may not ever output a number larger than the length of the list. This is because for a list a = [1, 2, 3], calling a.flop(4) is nonsensical.
Here are some examples:
#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]

#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>

#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]

#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]

#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

Keep in mind that in each of these examples, the output given is just one potential valid output. As I said before, any set of flops that neighbors the given list is a valid output. You can use this python script to verify if a given list of flops correctly neighbors a list.
You may take input and output in any reasonable format. For example, function arguments/return value, STDIN/STDOUT, reading/writing a file etc. are all valid. As usual, this is code-golf, so make the shortest program you can, and have fun! :)

I heard it as fl(oating point) op(eration).

@WeijunZhou That's a measure of computational speed, for counting operations carried out py a piece of hardware. https://en.wikipedia.org/wiki/FLOPS

Related

Do submissions have to be deterministic or can I pseudo-randomly flop until the array is grouped?

@Dennis As long as small inputs finish reasonably fast and reliably, I guess that's fine.

Are zero flops allowed to appear in the output?

Related. NB any answer to that question would be an answer to this one, but since being sorted is a stronger condition than being "neighboured" it may be possible to out-golf them so this might not be a duplicate (although the fact that the only answer so far sorts is not encouraging).

Would it be OK to use a string of characters as input ? So e.g. ABA instead of 11 2 11

Haskell, 98 71 bytes
h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

Try it online!
Explanation
For a list of length  n this method produces 2*n flops. It works by looking at the last element of the list, looking for the same element in the list before and flipping it to the second to last position. Then the list with the last element removed is recursively "neighboured".
For the list [1,2,3,1,2] the algorithm works like this:
[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

All together this yields the flops [2,4,0,3,1,2,0,1,0,0] and the neighboured list [3,1,1,2,2].

Wolfram Language (Mathematica), 71 bytes
If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

Try it online!
How it works
Given an array of length n, outputs a sequence of 4n flops that sort the array in increasing order: in particular, putting duplicate elements next to each other.
The idea is that to sort an array, we move its largest element to the end, and then sort the first n-1 elements of the array. To avoid implementing the flop operation, we move the largest element to the end in a way which does not disturb the other elements:
{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

In general, if the largest element is in position i, the sequence of flops that moves it to the end is i, n, n-1, i-1.

You can move the largest element to the end with just i, n. Why then do n-1, i-1? There's no need for a stable sort.

@PeterTaylor I don't think the answer actually performs flops, rather, it removes the largest element each time, and outputs the equivalent of that operation in terms of flops.

Jelly, 19 17 bytes
ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Sorts the list.
Try it online!

I think ỤŒ¿’Æ!‘ṚĖµUż’ṚF reverse sorts since Œ¿ is modulo L!.

For whatever reason, that doesn't work for the last test case, which probably means that my code will fail for some obscure edge case as well...

And it does indeed fail for input [4, 3, 2, 1, 3]. Bummer.

Oh, boo; that's a shame.

Ụ>Ṫ$ƤSạỤĖµUż’ṚF saving 2 bytes by replacing the helper link.

Python 2, 69 bytes
l=input()
while l:k=l.index(max(l));print-~k,len(l),;l=l[:k:-1]+l[:k]

Try it online!

Clean, 88 bytes
I think there's a possibly shorter one with guards, but I haven't found it yet.
import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

Try it online!
As a function literal. Works the same way as Laikoni's Haskell answer, but golfed slightly differently, and of course also in a different language.

JavaScript, 150 bytes
(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

Try it online!
JavaScript, 151 bytes
a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

Try it online!

Both basically sort the array by flipping the max number to the beginning and then flipping it to the back, repeating this with the remaining array. The first one uses reduce, the second one uses a for loop.
Ungolfed:
array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)];
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;)
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}

C (gcc), 165 160 bytes

Thanks to ceilingcat for saving five bytes.

m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}

Try it online!
Verification

Perl 5.10 (or higher), 66 bytes
Includes +3 for -n
The use 5.10.0 to bring the language to level perl 5.10 is considered free
#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Run with the input as one line on STDIN:
flop.pl <<< "1 8 3 -5 6"

Sorts the list by repeatedly finding any inversion, flopping it to the front then flopping the inversion and flopping everything back to its old position.
It was surprisingly hard to get in the same ballpark as python on this one :-)


text:
Find The Local Maxima And Minima
Definition
The maxima and minima of a given function are the largest and smallest values of the function either within a given range or otherwise within the entire domain of the function.
Challenge
The challenge is to find the local maxima and minima of a given polynomial function using any method you may like. Don't worry, I will try my best to explain the challenge and keep it as simple as possible.
The input will contain all the coefficients of the single variable polynomial in either decreasing or increasing order of power (up to you). For example,

[3,-7,1] will represent \$3x^2 - 7x + 1\$
[4,0,0,-3] will represent \$4x^3 - 3\$

How To Solve Using Derivatives
Now, let's say our input is [1,-12,45,8], which is nothing but the function \$x^3 - 12x^2 + 45x + 8\$.

The first task is to find the derivative of that function. Since it is a polynomial function, so it is indeed a simple task to do.

The derivative of \$x^n\$ is \$n\times x^{n-1}\$. Any constant terms present with \$x^n\$ are simply multiplied. Also, if there are terms added/subtracted, then their derivatives are also added or subtracted respectively. Remember, the derivative of any constant numerical value is zero. Here are a few examples:

\$x^3 \to 3x^2\$
\$9x^4 \to 9\times4\times x^3 = 36x^3\$
\$-5x^2 \to -5\times2\times x = - 10x\$
\$2x^3 - 3x^2 + 7x \to 6x^2 - 6x + 7\$
\$4x^2 - 3 \to 8x - 0 = 8x\$

Now solve the equation by equating the new polynomial to zero and get only the integral values of \$x\$.

Put those values of \$x\$ in the original function and return the results. That should be the output.

Example
Let us take the example we mentioned earlier, i.e, [1,-12,45,8].

Input: [1,-12,45,8]
Function: \$x^3 - 12x^2 + 45x + 8\$
Derivative: \$3x^2 - 24x + 45 + 0 \to [3,-24,45]\$
Solving equation: \$3x^2 - 24x + 45 = 0\$, we get \$x = 3\$ and \$x = 5\$.
Now putting \$x = 3\$ and \$x = 5\$ in the function, we get the values \$(62,58)\$.
Output: [62,58]

Assumptions

Assume that all the input coefficients are integers. They can be in increasing or decreasing order of power.

Assume the input to be at least a 2-degree polynomial. If the polynomial has no integer solutions, you can return anything.

Assume that the final result will be integers only.

You can print the results in any order. The degree of the input polynomial would not be more than 5, so that your code can handle it.

The input will be valid so that the solutions of x are not saddle points.

Also, you are not forced to do it by the derivative method. You can use any method you feel like.
Sample Input And Output
[2,-8,0] -> (-8)
[2,3,-36,10] -> (91,-34)
[1,-8,22,-24,8] -> (-1,0,-1)
[1,0,0] -> (0)

Scoring
This is code-golf so the shortest code wins.

If I understand correctly: in the example the step "Solving equation" would be partially this previous challenge of you? Also, step "Now putting x=3 and x=5 in the function" means the original function at "Function" and not the function at "Derivative", right?

For sample I/O 3, I'm getting (-1, 0, 1), which I believe is the actual correct answer... not sure though. If you disagree with me ping me in chat.

Is it okay to take the actual polynomial as input, like 3x^2-7x+1?

@HyperNeutrino very sorry. That was a typo. Fixed now.

@JungHwan yes it's okay

@KevinCruijssen yes, absolutely.

The input will be valid so that the solutions of x are not saddle points, the case [1,0,0,3] seems to give a saddle point.

@JungHwanMin ah that example was added before the rule was made. Removed now.

Suggested test case: [1,0,0] -> (0) (credit to @betseg). My answer was correct for all your test cases, but failed for this one. And Arnauld's JavaScript answer also failed for this test cases. If multiple answers fail a certain test case, it's a good test case to add. :)

x^3 - 12x^2 + 45x + 8 = 0, although personally I prefer you write it as f(x)=x^3-12x^2+45x+8 without the =0 because =0 doesn't make sense since we are dealing with a function, not solving an equation.

Under “how to solve“ there is a sign error with +8 in the input list but -8 in the description.

@FelixDombek yeah right ty.

Jelly, 20 bytes
ASŒRḅ@Ðḟ
J’U×µṖÇḅ@€³

Try it online!
Explanation
ASŒRḅ@Ðḟ     Helper Function; find all integer solutions to a polynomial
             All integer roots are within the symmetric range of the sum of the absolute values of the coefficients
A            Absolute Value (Of Each)
 S           Sum
  ŒR         Symmetric Range; `n -> [-n, n]`
      Ðḟ     Filter; keep elements where the result is falsy for:
    ḅ@       Base conversion, which acts like the application of the polynomial
J’U×µṖÇḅ@€³  Main Link
J                             Range of length
 ’                    Lowered
  U          Reversed
   ×         Multiplied with the original list (last value is 0)
    µ        Begin new monadic chain
     Ṗ       Pop; all but the last element
      Ç      Apply last link (get all integer solutions of the derivative)
       ḅ@€³  Base conversion of the polynomial into each of the solutions; apply polynomial to each solution of the derivative.

The helper function in this program was taken from Mr. Xcoder's answer
here which was based off of Luis's answer here

@JungHwanMin I'll point that out to OP. That's a direct violation of the statement that there will be no saddle points because the derivative of the polynomial at 3 is 0. edit oh you already did nvm just upvoted the comment then

Outgolfed :P

JavaScript (ES7), 129 120 bytes
Takes the coefficients in increasing order of power.
a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

Test cases

let f =

a=>(g=x=>x+k?(A=g(x-1),h=e=>a.reduce((s,n,i)=>s+n*(e||i&&i--)*x**i,0))()?A:[h(1),...A]:[])(k=Math.max(...a.map(n=>n*n)))

console.log(JSON.stringify(f([0,-8,2])))        // (-8)
console.log(JSON.stringify(f([10,-36,3,2])))    // (91,-34)
console.log(JSON.stringify(f([8,-24,22,-8,1]))) // (-1,0,-1)

Commented
a => (                        // given the input array a[]
  g = x =>                    // g = recursive function checking whether x is a solution
    x + k ? (                 //   if x != -k:
      A = g(x - 1),           //     A[] = result of a recursive call with x - 1
      h = e =>                //     h = function evaluating the polynomial:
        a.reduce((s, n, i) => //       for each coefficient n at position i:
          s +                 //         add to s
          n                   //         the coefficient multiplied by
          * (e || i && i--)   //         either 1 (if e = 1) or i (if e is undefined)
          * x**i,             //         multiplied by x**i or x**(i-1)
          0                   //         initial value of s
        )                     //       end of reduce()
      )() ?                   //     if h() is non-zero:
        A                     //       just return A[]
      :                       //     else:
        [h(1), ...A]          //       prepend h(1) to A[]
    :                         //   else:
      []                      //     stop recursion
  )(k = Math.max(             // initial call to g() with x = k = maximum of
    ...a.map(n => n * n)      // the squared coefficients of the polynomial
  ))                          // (Math.abs would be more efficient, but longer)

fails for 0,0,1 (x^2=0)

@betseg Thanks for reporting this. Fixed.

Java 8, 364 239 227 226 218 bytes
a->{int l=a.length,A[]=a.clone(),s=0,i,r,f=l,p;for(;f>0;A[--f]*=f);for(int n:A)s+=n<0?-n:n;for(r=~s;r++<s;){for(p=0,i=f=1;i<l;f*=r)p+=A[i++]*f;if(p==0){for(f=i=0;i<l;f+=a[i++]*Math.pow(r,p++));System.out.println(f);}}}

Uses the same functionality from this answer of mine.
-8 bytes thanks to @OlivierGrégoire by taking the array in reversed order.
Explanation:
Try it online.
a->{                  // Method with integer-varargs parameter and integer return-type
  int l=a.length,     //  The length of the input-array
      A[]=a.clone(),  //  Copy of the input-array
      s=0,            //  Sum-integer, starting at 0
      i,              //  Index-integer
      r,              //  Range-integer
      f=l,            //  Factor-integer, starting at `l`
      p;              //  Polynomial-integer
  for(;f>0;           //  Loop over the copy-array
    A[--f]*=f);       //   And multiply each value with it's index
                      //   (i.e. [8,45,-12,1] becomes [0,45,-24,3])
  for(int n:A)        //  Loop over this copy-array:
    s+=n<0?-n:n;      //   And sum their absolute values
  for(r=~s;r++<s;){   //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
    for(p=0,          //   Reset `p` to 0
        i=f=1;        //   and `f` to 1
                      //   (`i` is 1 to skip the first item in the copy-array)
        i<l;          //   Inner loop over the input again, this time with index (`i`)
        f*=r)         //     After every iteration: multiply `f` with the current `r`
      p+=             //    Sum the Polynomial-integer `p` with:
         A[i++]       //     The value of the input at index `i`,
               *f;}   //     multiplied with the current factor `f`
    if(p==0){         //   If `p` is now 0:
      for(f=i=0;      //    Use `f` as sum, and reset it to 0
          i<l;        //    Loop over the input-array
        f+=a[i++]*Math.pow(r,p++));
                      //     Fill in `r` in the parts of the input-function
      System.out.println(f);}}}
                      //    And print the sum

fails for 1,0,0 (x^2=0)

@betseg Thanks! Fixed and golfed.

You should accept the input in reversed order (it is explicitly allowed) to reduce your count like this: int... ,i, ...; for(;f>0;)A[--f]*=f;. Unless I'm mistaken, this should save you at least 4 bytes. If you do this, make sure to invert all your accesses to the input.

@OlivierGrégoire Thanks, 8 bytes saved!

Julia 0.6 (with Polynomials package), 57 bytes
using Polynomials
x->map(Poly(x),roots(polyder(Poly(x))))

Try it online!
Takes coefficients in increasing order, i.e. the first input is the constant term.
Example run:
julia> using Polynomials

julia> g = x -> map(Poly(x), roots(polyder(Poly(x))))
(::#1) (generic function with 1 method)

julia> g([8,45,-12,1])
2-element Array{Float64,1}:
 58.0
 62.0

Wolfram Language (Mathematica), 30 bytes
a@x/.#&/@Solve[a=#;#'@x==0,x]&

Takes a pure-function polynomial (i.e. a polynomial with # as a variable and with a & at the end).
Try it online!

19 bytes

Haskell, 89 bytes
-3 bytes thanks to Laikoni.
r#l=foldr1((.(r*)).(+))l
r l|_:d<-zipWith(*)[0..]l,t<-sum$abs<$>d=[i#l|i<-[-t..t],i#d==0]

Try it online!
Takes coefficients reversed.

d<-tail$ can be shortened to _:d<-.

Jelly, 9 bytes
J’×UḊÆrḅ@

Try it online!
Takes input as a list of coefficients in decreasing order of powers
How it works
J’×UḊÆrḅ@ - Main link. Takes a list of coefficients C on the left
J         - Yield indices; [1, 2, ..., len(C)]
 ’        - Decrement; [0, 1, ..., len(C)-1]
   U      - Yield C reversed
  ×       - Multiply each element of C reversed by each element of [0, 1, ..., len(C) - 1]
    Ḋ     - Remove the leading 0
     Ær   - Solve the polynomial represented by the new list of coefficients
       ḅ@ - Evaluate the roots as inputs to C (base conversion)

Vyxal, 8 bytes
∆Ċ:∆Kv∆Q

Try it Online!
The power of actual symbolic algebra.
Explained
∆Ċ:∆Kv∆Q
∆Ċ        # Convert the list of coefficients into an expression that looks like a*x**n + b*x**(n-1) ... + z
  :       # Push a second copy of that
   ∆K     # Get the stationary points of that (returns x values)
     v∆Q  # and sub those x-values into the original equation

Python 3, 156 bytes
def f(p,E=enumerate):a=lambda p,v:sum(e*v**i for i,e in E(p));d=[e*i for i,e in E(p)][1:];r=sum(map(abs,d));return[a(p,x)for x in range(-r,r+1)if a(d,x)==0]

Try it online!
-2 bytes thanks to Mr. Xcoder
-22 bytes thanks to ovs

Python + numpy, 91

1 byte saved thanks to @KevinCruijssen

from numpy import*
p=poly1d(input())
print map(lambda x:int(polyval(p,x)),roots(p.deriv()))

Try it online.

Pari/GP, 28 bytes
p->[eval(p)|x<-polroots(p')]

Evaluate the polynomial at the roots of its derivative.
Try it online!