text:
11 = (1+2+3+4+5) - (1+2+3) + (6) - (4)
Given a positive integer N, your task is to return the number of steps required by the following algorithm to reach N:

Find the smallest triangular number Ti such that Ti ≥ N. Build the corresponding list L = [ 1, 2, ..., i ].
While the sum of the terms of L is greater than N, remove the first term from the list.
If the sum of the terms of L is now less than N, increment i and append it to the list. Go on with step #2.

We stop as soon as N is reached. Only the first step is systematically executed. Steps #2 and #3 may not be processed at all.
Examples
Below is an example for N = 11:

So the expected output for N = 11 is 4.
Other examples:

N = 5 - We start with T3 = 1 + 2 + 3 = 6, followed by 2 + 3 = 5. Expected output: 2.
N = 10 - Only the first step is required because 10 is a triangular number: T4 = 1 + 2 + 3 + 4 = 10. Expected output: 1.

First 100 values
Below are the results for 1 ≤ N ≤ 100:
  1,  2,  1,  4,  2,  1,  2, 10,  2,  1,  4,  2,  6,  2,  1, 22,  8,  2, 10,  2,
  1,  2, 12,  6,  2,  4,  2,  1, 16,  2, 18, 50,  2,  6,  2,  1, 22,  6,  2,  4,
 26,  2, 28,  2,  1,  8, 30, 16,  2,  6,  4,  2, 36,  2,  1,  2,  4, 12, 40,  2,
 42, 14,  2,108,  2,  1, 46,  2,  6,  4, 50,  2, 52, 18,  2,  4,  2,  1, 56, 12,
  2, 20, 60,  4,  2, 22, 10,  2, 66,  2,  1,  4, 10, 24,  2, 40, 72,  8,  2,  6

Rules

You may write either a full program or a function, that either prints or returns the result.
You're required to process any N ≤ 65536 in less than one minute on mid-range hardware.
Given enough time, your program/function should theoretically work for any value of N that is natively supported by your language. If it doesn't, please explain why in your answer.
This is code golf, so the shortest answer in bytes wins!

Related. (I suspect you already know about this one, but just posting it for posterity)

What is the maximum value of N we need to handle?

@Luke Please see the updated rules.

Do you accept unary output?

@Titus This is a bit disputed, but I'll stick to the current consensus on that one.

Jelly, 29 31 28 bytes
-3 thanks to caird coinheringaahing (save a $, use the newer Ä, and use the newer Ƒ)
ÆDµ’H+ṚḞƑƇṂ
>TḢ_@Ç}‘Ḥ
RÄðċȯç

A monadic link that returns the result (N=65536 takes less than two seconds).
Try it online!
How?
For a thorough explanation of the algorithm see the fantastic post by Martin Ender.
ÆDµ’H+ṚḞƑƇṂ - Link 1, smallest natural number, M, that satisfies the below*, N
            - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD          - divisors of N
  µ         - monadic chain separation, call that d
   ’        - increment d (vectorises)
    H       - halve (vectorises
      Ṛ     - reverse d
     +      - add (vectorises)
         Ƈ  - filter keep if:
        Ƒ   -   is invariant under:
       Ḟ    -     floor (i.e. those which are the result of even divisors)
          Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double

RÄðċȯç - Main link: N
R      - range -> [1,2,...,N]
 Ä     - reduce with addition -> [1,3,6,10,...T(N)]
  ð    - dyadic chain separation, call that t
   ċ   - count occurrences of N in t (1 if N is triangular else 0)
     ç - call last link (2) as a dyad(t, N)
    ȯ  - or

The 29 byte full-program implementation I created of the algorithm described takes 4 min 30 for N=65536 on my laptop, so I suppose it does not count.
Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’

29 bytes

Nice save of $, thanks!

28 bytes

@cairdcoinheringaahing Thanks.

Mathematica, 79 bytes
Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

Explanation
I couldn't be bothered to implement the algorithm in the challenge, so I wanted to look for a shortcut to the solution. While I found one, unfortunately it doesn't beat the Mathematica answer that does implement the algorithm. That said, I'm sure this isn't optimally golfed yet, and there might be other languages who can benefit from this approach or some of the insights gained in the process.
So I claim that the sequence we're supposed to compute is:
f(n) = 2*(A212652(n) - A002024(n)) + 1 + A023532(n-1)
Alternatively, it's f(n) = 1 if n is a triangular number and f(n) = 2*(A212652(n) - A002024(n) + 1) otherwise.
In the first expression, A023532 simply encodes these two different cases. The other two sequences (plus 1) are the difference between the the largest integer k in the longest decomposition of n into consecutive integers (k-i+1) + (k-i+2) + ... + k = n and the largest integer j so that 1 + 2 + ... + j < n.
In somewhat simpler words, here is how we find the answer for non-triangular numbers: first, find the largest triangular number Tj which is less than n. Then j is the penultimate integer that gets added during step 1 (because after adding j+1 we will have exceeded n). Then decompose n into as many (or as small) consecutive integers as possible and call the maximum among these numbers k. The result is simply 2*(k-j). The intuitive reason for this is that the maximum in the decomposition grows by 1 every other step and we stop when we reach k.
We need to show four things to prove that this works:

f(n) = 1 for triangular numbers. This is trivially the case, because the first step simply iterates through all triangular numbers. If we hit n exactly during this process we're done and there was only one step to compute.
For all other numbers, we always end after a deletion step, never after an insertion step. That means all other f(n) are even.
In each insertion step after the first, we only add a single number. This guarantees that we'll reach a decomposition including k after k-j pairs of steps.
The final decomposition of n that we obtain is always the longest possible decomposition of n into consecutive integers, or in other words, it's always the decomposition of n with the lowest maximum among the summed numbers. In other words, the last number we add to the sum is always A212652(n).

We've already shown why (1) is true. Next, we prove that we can't end on an insertion step except the initial one (which doesn't happen for non-triangular numbers).
Suppose we ended on an insertion step, reaching n after adding a value p to the sum. That means that before this insertion step, the value was n-p (or less if we added multiple values at once). But this insertion step was preceded by a deletion step (since we couldn't have hit n during step 1). The last value q we removed during this deletion step was necessarily less than p due to the way the algorithm works. But that means before we removed q we had n-p+q (or less) which is less than n. But that's a contradiction, because we would have had to stop removing integers when we hit n-p+q instead of removing another q. This proves point (2) above. So now we know that we always end on a deletion step and that therefore all non-triangular numbers have even outputs.
Next we prove (3), that each insertion step can only insert one value. This is essentially a corollary of (2). We have shown that after adding one value we cannot hit n exactly and since the prove was using an inequality, we also cannot end up below n (since then n-p+q would still be less than n and we shouldn't have removed that many values in the first place). So whenever we add a single value, we're guaranteed to exceed n because we went below n by removing a smaller value. Hence, we know that the upper end of the sum grows by 1 every other step. We know the initial value of this upper end (it's the smallest m such that Tm > n). Now we just need to figure out this upper end once we've reached the final sum. Then the number of steps is simply twice the difference (plus 1).
To do this, we prove (4), that the final sum is always the decomposition of n into as many integers as possible, or the decomposition where the maximum in that decomposition is minimal (i.e. it's the earliest possible decomposition). We'll again do this by contradiction (the wording in this part could be a bit more rigorous, but I've already spent way too much time on this...).
Say the earliest/longest possible decomposition of n is some a + (a+1) + ... (b-1) + b, a ≤ b, and say the algorithm skips it. That means at the time that b gets added, a must no longer be part of the sum. If a was part of the sum s, then we'd have n ≤ s at that moment. So either the sum only contains the values from a to b, which equals n and we stop (hence we didn't skip this decomposition), or there is at least one value less than a in the sum, win which case n < s and that value would get removed until we hit the exact sum (again, the decomposition wasn't skipped). So we'd have to get rid of a before adding b. But that means we'd have to reach a situation in which a is the smallest component of the sum, and the largest isn't b yet. However, at that point we can't remove a, because the sum is clearly less than n (since b is missing), so we're required to add values first until we add b and hit n exactly. This proves (4).
So taking these things together: we know that the first pair of steps gives us a maximum value of A002024(n). We know that the maximum value of the final decomposition is A212652(n). And we know that this maximum is incremented once in every pair of steps. Hence, the final expression is 2*(A212652(n) - A002024(n) + 1). This formula almost works for triangular numbers, except that for those we only need 1 step instead of 2, which is why we correct the result with the indicator function of the triangular numbers (or its inverse, whichever is more convenient).
Finally, as for the implementation. For the former sequence, I'm using the formula MIN(odd d|n; n/d + (d-1)/2) from OEIS. It turns out to save a few bytes if we take the factor of 2 into this expression to get MIN(odd d|n; 2n/d + d-1), because that -1 then cancels with the +1 in my first version of f(n) which directly encodes the two cases for triangular and non-triangular numbers. In the code, this is:
Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

For the latter sequence (1, 2, 2, 3, 3, 3, ...), we can use a simple closed form:
⌊(2#)^.5+.5⌋

And finally, the inverse indicator function of the triangular numbers is 0 whenever 8n+1 is a perfect square. This can be expressed in Mathematica as
⌈Sqrt[8#+1]~Mod~1⌉

There are a lot of ways to express these last two sequences and to shift some constant offset between them, so I'm sure this is not an optimal implementation yet, but I hope this might give others a starting point to look into new approaches in their own languages.
Since I went to all this trouble, here is a plot of the sequence up to n = 1000 (I could also compute 100k in a couple of seconds, but it doesn't really show any additional insights):

It might be interesting to look into the variations about those very straight lines, but I'll leave that to someone else...

I finally took the time to read your answer thoroughly. This is brilliant. Note that (3) was already assumed in the algorithm (step #3 is a if, not a while), but the proof is -- of course -- much welcomed.

@Arnauld Thank you. :) I must have overlooked/misunderstood the if/while part. Good thing it doesn't make a difference then.

Mathematica, 72 bytes
(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Pure function taking an integer argument.
How it works
For[ ... ]

A For loop.
l=u=c=k=0

Initialization; set l (lower), u (upper), c (counter), and k (sum) to 0.
k!=#

Condition; repeat while k is not equal to the input.
c++

Increment; increment the counter c.
If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

Body
If[#>k, ... ]

If the input is greater than k:
While[#>k,k+=++u]

While the input is greater than k, increment u and increment k by u.
If the input is not greater than k:
While[#<k,k-=l++]

While the input is less than k, decrement k by l and increment l.
( ... ;c)

Return c after the loop.

For[,...] beats While[...].

PHP>=7.0, 74 Bytes
while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;

use the spaceship operator
Try it online!
Expanded
while($i=$r<=>$argn) # if input is not equal sum of array
  for($s++;  # raise count steps
  ($r<=>$argn)==$i;)
  # so long as value compare to input has not change to lower/higher to higher/lower or equal
    $r+=$i+1
      ?-++$y # if $i was higher remove the first integer
      :++$x;} # if $i was lower add the next highest integer
echo$s; # Output steps

What's $argn?

@chx A variable which is available when you you PHP from the command line with the -R Option http://php.net/manual/en/features.commandline.options.php

Wow. I never heard of -R much less argv or argi. I knew of argc and argv of course. Very interesting, thanks.

took the liberty of golfing that down a bit; see my post.

Haskell, 70 63 68 64 bytes
EDIT:

-7 bytes: Got rid of a space, two signs, and some parentheses by negating the sense of a. Fixed off-by-one errors in the explanation.
+5 bytes: Argh, completely missed that 65536 requirement, and it turns out (1) powers of 2 are particularly expensive, because they only get hit when you get to the number itself (2) so is summing long ranges (that wrap around zero) all the time. Replaced the sum with a mathematical formula.
-4 bytes: Adjusted a and b linearly to get terms in the summation formula to cancel.

1#1 is an anonymous function taking and returning an integer.
Use as (1#1) 100.
1#1
(a#b)n|s<-a*a-b*b=sum$[a#(b+2)$n|s>8*n]++[(b#a)(-n)+1|s<8*n]

Try it online!
How it works

(a#b)n represents the current step of calculation. a, b are numbers in 1, 3, 5, .., while n can be either positive or negative depending on the step.

When in step 1 or 3, it represents the list [(a+1)/2,(a+3)/2..(b-1)/2] and goal number -n.
When in step 2, it represents the list [(b+1)/2,(b+3)/2..(a-1)/2] and goal number n.

The strange correspondence between a, b and the lists is in order to be able to do summation with the short expression s=a*a-b*b.

In step 1 and 3, this is the same as s= -8*sum[(a+1)/2..(b-1)/2].
In step 2, this is the same as s=8*sum[(b+1)/2..(a-1)/2].

Branching is done by having list comprehensions that produce elements in only one case each, and summing the results.

If s>8*n, then b is incremented by 2 before recursing.

In step 1 and 3, this grows the list, while in step 2, this shrinks it.

If s<8*n, then recursion changes the step by swapping a and b, and negating n, and 1 is added to the result.
If s==8*n, then neither of the two list comprehensions gives any elements, so the sum is 0.

(1#1) n represents a dummy "stage 2" before starting, that immediately gets changed to step 1, building the list from [1..0]=[].

Python 2, 104 bytes
N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s

Try it online!
Alternates between adding terms to the end of the list, and removing terms from the beginning.

C, 94 91 bytes
Try Online
c;s;m;M;f(n){while(s-n){while(s<n)s+=++M;c++;if(s==n)break;while(s>n)s-=++m;c++;}return c;}

Extensive use on uninitialized variables oO

@YSC in C, uninitialized globally-declared integers are set to zero at compile time. read more

Forgot about this. Thank you for this reminder.

FYI, I posted another C answer. At least one of the tricks I used won't work with other compilers (the missing return), but for the ones that do, feel free to incorporate them into your answer.

Python 3, 150 138 bytes
n=int(input())
S=sum
l=[1]
i=s=1
while S(l)<n:i+=1;l+=[i]
while S(l)!=n:
 while S(l)>n:l.pop(0)
 s+=1
 if S(l)<n:i+=1;l+=[i];s+=1
print(s)

Changelog:

Changed append to +=, removed else (thanks musicman523, Loovjo; -12 bytes)

Step #2 can remove one or several terms at once from the list (like 1, 2 and 3 in the example for N = 11) but is counted as one step either way.

@Arnauld overlooked that; fixed.

Can you explain why the else is necessary? I believe the else runs every time, because the loop always terminates normally (without break), and it seems to work fine without it.

You could skip the A=l.append part and use l+=[x] instead.

dc, 61 bytes
dsN[ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx]dsFxz2-

Try it online!
Explanation
Main recursive macro:
ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx
   9k4*d2*1+dv-0k2/-                              # Compute triangular root
                    d1+*2/                        # Compute triangular number
  d                       -d[q]s.0=.              # Check if sum is exact
 d                                  -lN-          # Compute S-N or S+N
                                        0lN-sN    # Update N := -N
d                                             lFx # Leave the trail and recurse

This macro:

Finds minimum triangular number that exceeds the current number on the stack (using the modified triangular root formula).
Checks if triangular sum S represents the current number exactly. Exits if it does.
Proceeds to step 1 with either S+N (over-approximation) or S-N (under-approximation), the choice alternates between iterations.

When it does exit, the trail left on the stack tells the main program how many iterations it took.

Python 2, 86 81 bytes
n=input()
l=u=i=s=0
while n:k=n>0;i+=k^s;s=k;l+=k;n-=l*k;u+=k^1;n+=u*-~-k
print i

Try it online!
Computes the 65536 test case in 0.183s on TIO.

This recursive version at 84 bytes is not able to compute all values up to 65536:

def f(n,l=[0],m=1):k=n>sum(l);return n==sum(l)or f(n,[l[1:],l+[l[-1]+1]][k],k)+(m^k)

Try it online!

Batch, 126 bytes
@echo off
set/an=s=l=u=0
:l
if %s% lss %1 set/as+=u+=1,n+=!!l&goto l
if %s% gtr %1 set/as-=l+=1&goto l
cmd/cset/an+n+2-!l

Explanation: l is zero if step 2 has never executed. This allows n to track number of iterations of step 3. Since the algorithm never stops at step 3, it must therefore have run step 1 once and step 2 n+1 times for a total of n+n+2 steps. However if the parameter is a triangular number then step 2 never executes so we need to subtract one step.

C (tcc), 71 bytes (61+10)
Command-line arguments (including a space):
-Dw=while

Source:
c,m,M,s;f(n){w(++c,s-n){w(c&s<n)s+=++M;w(~c&s>n)s-=m++;}--c;}

How it works:
c counts the number of steps. m and M store the minimum and maximum of the range, s the sum. Initially, they're all zero.
Continuously, c is increased, and s is compared to n. As long as they're unequal:

If c is odd, then as long as s<n, add an integer to the end of the range: increase M by one, and s by M.
If c is even, then as long as s>n, remove an integer from the start of the range: decrease s by m, and increase m by one.

When the loop exits, c has been increased one too many times. Decrementing it produces the correct result, and it happens to be calculated in the correct register to act as the return value.
Amusingly happens to use the exact same variable names as Khaled.K's C answer. They aren't copied.

Mathematica, 92 bytes
(For[q=a=b=0;t={},t~AppendTo~q;q!=#,If[q<#,q+=++b,q-=++a]];Length@Split@Sign@Differences@t)&

Pure function taking an integer argument and returning an integer.
The variables a and b stand for the (constantly changing) beginning and end numbers in the sum under consideration, while q stands for the running total (of the numbers from a+1 to b); t keeps track of all the values of q encountered so far. After initializing these variables, the For loop keeps executing If[q<#,q+=++b,q-=++a], which either adds a new number on to the end or subtracts the number at the front as dictated by the spec, until q equals the input.
Now we just have to extract the number of steps from t, the list of q values encountered along the way. For example, when the input is 11, the For loop exits with t equaling {0,1,3,6,10,15,14,12,9,15,11}. The best way I found to calculate the number of steps from this is to count how many times the differences switch from going up to going down; that's what the verbose command Length@Split@Sign@Differences@t does, but I suspect that can be improved.

05AB1E, 28 27 bytes
ÅTθÊiÑÂ<;+ʒ.ï}ßI·t2z+ï->·ë1

Port of @JonathanAllan's Jelly answer, which is using @MartinEnder's Mathematica formula, so make sure to upvote both of them!
Try it online or verify the first 100 test cases. (NOTE: The .ï has been replaced with DïQ in the TIOs, because this .ï bug on floating values, which was fixed on October 23rd, hasn't been pushed to TIO yet.)
Explanation:
ÅT             # Push a list of triangular numbers smaller than or equal to the
               # (implicit) input-integer
  θ            # Pop and only leave the last value in this list
   Êi          # If it's NOT equal to the (implicit) input, so the input isn't a
               # triangular number:
     Ñ         #  Get all divisors of the (implicit) input
      Â        #  Bifurcate this list (short for Duplicate & Reverse copy)
       <       #  Decrease each by 1 in the reversed list
        ;      #  Then halve each
         +     #  And add the values at the same positions in the lists together
          ʒ    #  Filter it by:
           .ï  #   Where the decimal value is an integer
          }ß   #  After the filter: pop and leave the minimum
     I·        #  Push the input again and double it
       t       #  Take the square-root of this
        2z+    #  Add 1/2 to it
           ï   #  Floor it to an integer
     -         #  Subtract it from the earlier minimum
      >        #  Increase it by 1
       ·       #  Double it
    ë          # Else (the input is a triangular number):
     1         #  Simply push a 1
               # (after which the top of the stack is output implicitly as result)

PHP 7, 59 Bytes
(7.0.1 or later)
for(;$d=$argn<=>$s;$x+=$d!=($argn<=>$s))$s+=$$d+=$d;echo$x;

Run as pipe with -nR or try it online.
breakdown:
for(;$d=$argn<=>$s;     # $s<N: $d=+1, $s>N: $d=-1, $s==N: 0 -> falsy -> break
    $x+=$d!=($argn<=>$s))   # 3. if sign of difference changed, increment counter
    $s+=                    # 2. add to sum
        $$d+=$d;            # 1. increment ${1} or decrement ${-1}
echo$x;                 # print step counter

uses the spaceship operator <=> (introduced in PHP 7.0) and variable variables (introduced in PHP/FI).
Thanks @Jörg for reminding me of the spaceship.
Without the parentheses around the spaceship in the post condition, PHP wouldn not know what comparison to evaluate first (and throw a syntax error).
PHP 7 (unary output), 53 bytes
for(;$d=$argn<=>$s;print$d!=($argn<=>$s))$s+=$$d+=$d;

Perl 6, 114 bytes
{((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}

(inspired by an earlier Haskell implementation)
Try it
It runs with an input of 65536 in under 45 seconds on my computer, but I have been unable to get it to run in under 60 seconds with TIO.run.
I have Rakudo v2017.04+ , where it has v2017.01.
Rakudo/NQP/MoarVM gets optimizations almost daily, so there could be any number of them from the interim that are needed to get it in under time.

Expanded
{
  (

    # generate a sequence

    (0,0,1),           # initial value

    -> (\a,\b,\c) {
      b,               # swap the first two values

      (a..*)
      .first(          # find the first number that brings us to or past the input

        -> \d {
          (d,b).minmax # get a Range object regardless of which is larger
          .sum * c     # sum it, and negate it every other time

          >=           # is it equal to or greater than

          $_ * c       # negate the original input every other time
        }

      ),

      -c               # invert for next round
    }

    ...                # keep doing that until

    -> (\a,\b,\c) {
     (a,b).minmax.sum == $_ # it finally reaches the input
    }

  ) - 1 # count the number of elements in the sequence
        # and subtract one for the initializer
}

Note that Rakudo has an optimization for Range.sum so that it doesn't have to iterate through all of the values.

Husk, 32 bytes
→L↑o≠⁰Σ¡?oḟo≤⁰ΣṫS:o→→o>⁰Σḟo>⁰ΣḣN

Try it online!
Not that this will not run in 1 minute for n-65536, hence it cannot compete.
However, it can theoretically calculate for any given n.

Jelly, 26 bytes
S>³
RÄ<i0RḊÇ¿Ṃ;‘ƊÇ?S⁻³ƊÐ¿L

Try it online!
Full program only, because ¿ handles dyads in an... interesting way.
Directly implements the given algorithm.
S>³                       Monadic helper link:
S                         the sum of the argument,
 >                        is it greater than
  ³                       the input (to the entire program)?

RÄ<i0RḊÇ¿Ṃ;‘ƊÇ?S⁻³ƊÐ¿L    Main link:
 Ä                        cumulative sums of
R                         [1 .. input],
   i0                     first index of 0 in
  <                       whether or not each sum is less than the input,
     R                    starting with [1 .. that index]:
                    ¿     while
               S⁻³Ɗ       the sum is not equal to the input,
              ?           if
             Ç            (helper link) the sum is greater than the input,
      Ḋ                   then remove the first element
       Ç¿                 while the sum is greater than the input,
          ;   ?           else concatenate
         Ṃ                the smallest element to
           ‘Ɗ             the list incremented.
                   Ð¿L    Output the number of iterations this took.

I haven't finished verifying execution times, but specifically for N = 65536 TIO takes 9 seconds while my computer takes 15.
EDIT: My machine seems to have taken more than a minute for N = 32924, 32933, and 32941. TIO computes each result in less than 5 seconds, however, so I suspect this may be because the lid of my laptop was closed for eight hours.
N = 45596 also just now took a minute and 9 seconds, but this also coincided with my laptop going to sleep, and TIO takes less than 2 seconds for it.

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:
Gilbreath's Conjecture
Suppose we start with the infinite list of prime numbers:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, ...

Then, we take the absolute differences between each pair of numbers, repeatedly:
[1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, ...
[1, 0, 2, 2, 2, 2, 2, 2, 4, 4, 2, 2, 2, 2, 0, 4, 4, 2, ...
[1, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 4, 0, 2, ...
[1, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2, 4, 2, ...

Notice that the leading number is 1 every time. Gilbreath's Conjecture is the prediction that this continues to be the case forever.
The only way the leading number would stop being a 1 is if the next number after it was neither a 0 nor a 2. The only way the second number wouldn't be a 0 or a 2 is if the number after that was neither a 0 nor a 2. And so on.
The index of the earliest number, other than the leading 1, which is neither a 0 nor a 2, can never go down by more than 1 between a consecutive pair of sequences. This fact has been used to put a very strong lower bound on when, if ever, a sequence might not have a 1 as the first element.
In this challenge, you will be given the index of a sequence, and you must output the index of the first number in that sequence which is not the leading 1, and is not a 0 or a 2.
For instance, in the 4th absolute difference sequence above:
[1, 2, 0, 0, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2, 4, 2, ...

The first entry that's neither a zero or a two, other than the first entry, is the 15th position, 14 zero indexed. So if the input was 4, you would output 14.
For inputs from 1 to 30, the outputs should be:
[3, 8, 14, 14, 25, 24, 23, 22, 25, 59, 98, 97, 98, 97, 174, 176, 176, 176, 176, 291, 290, 289, 740, 874, 873, 872, 873, 872, 871, 870]
This is OEIS A000232.
This is assuming you have 1 indexed inputs and 0 indexed outputs. You may index your inputs and outputs starting at any constant integers, as long as you can accept the range of inputs corresponding to all sequences.
Requirements: Your solution must run in at most 1 minute on a input of up to 30. If it's close enough that it depends on the computer specs, it's allowed.
Shortest code wins.

Can I 2-index my input?

@LeakyNun Sure.

Can output use input-based indexing?

@LuisMendo Correct, fixed. No, the indexing must be a constant.

Jelly, 17 bytes
ÆNạ2\Ḋ¿Ḣ’Ị
R‘ÇÐ¿L

Try it online!
Input is 2-indexing. Output is 1-indexing.
On TIO all testcases in total take 22.309 s.

Mathematica, 66 bytes
(For[z=1,Last@Nest[Abs@*Differences,Array[Prime,z+#],#]<3,z++];z)&

Pure function taking a positive integer as argument and returning a 1-indexed integer. Nest[Abs@*Differences,Array[Prime,z+#],#] computes the #th iterated absolute difference list of the list of the first z+# primes. For[z=1,Last@...<3,z++] loops this computation until the last element of the resulting list is at least 3, and then z is output. (Note that the correctness of the algorithm assumes Gilbreath's conjecture!)

Pyth, 32 bytes
-l.W>3h.WtHaVZtZ>QH+ZfP_TheZ.fP_

Try it online!
Uses 2-indexing.

MATL, 18 bytes
`@:YqG:"d|]3<A}@G-

Input and output are 1-based. It takes less than 40 seconds in TIO for each of the test cases.
Try it online!
Explanation
This keeps trying longer initial sequences of primes until the iterated absolute consecutive differences give at least one value exceeding 2.
`        % Do... while loop
  @:Yq   %   Array of first k primes, where k is iteration index
  G:"    %   Do this as many times as the input
    d|   %     Absolute value of consecutive differences
  ]      %   End
  3<A    %   Are they all less than 3? This is the loop condition
}        % Finally (execute before exiting loop)
  @G-    %   Push last iteration index minus input. This is the output
         % End (implicit). Continue with next iteration if top of stack is true
         % Display (implicit)

Perl 6, 136 120 bytes
{->\i,\n{i??&?BLOCK(i-1,lazy
n.rotor(2=>-1).map: {abs .[1]-.[0]})!!1+n.skip.first:
:k,none 0,2}($_,grep &is-prime,2..*)}

Ungolfed:
{   # Anonymous function with argument in $_
    sub f(\i, \n) {  # Recursive helper function
        if i != 0 {  # If we're not done,
            # Recurse on the absolute differences between adjacent entries:
            f(i - 1, lazy n.rotor(2 => -1).map: { abs .[1] - .[0] });
        } else {
            # Otherwise, return the first index after 0
            # where the value is neither 0 nor 2.
            1 + n.skip.first: :k, none 0, 2;
        }
    }
    # Call the helper function with the argument passed to the top-level
    # anonymous function (the recursion depth), and with the prime numbers
    # as the initial (infinite, lazy) list:
    f($_, grep &is-prime, 2 .. *);
}

With an input of 30, the function runs in about four seconds on my modest laptop.
...which becomes 1.4 seconds after upgrading my seven-month-old Perl 6 installation (which also gives me the skip method that lets me shave off several bytes from my first solution).  All test cases from 1 to 30 take about ten seconds.

Haskell, 94 bytes
f(a:b:r)=abs(a-b):f(b:r)
length.fst.span(<3).(iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!)

Try it online! The last line is an anonymous function. Bind to e.g. g and call like g 4. All test cases combined take less than 2 seconds on TIO.
How it works
[n|n<-[2..],all((>0).mod n)[2..n-1]] generates an infinite list of primes.
f(a:b:r)=abs(a-b):f(b:r) is a function yielding the absolute differences of the elements of an infinite list.
Given a number n, (iterate f[n|n<-[2..],all((>0).mod n)[2..n-1]]!!) applies f n times to the list of primes. length.fst.span(<3) computes the length of the prefix of the resulting list where the elements are smaller 3.

Axiom, 289 bytes
g(n:PI):PI==(k:=n*10;c:List NNI:=[i for i in 1..(k quo 2)|prime?(i)];repeat(a:=concat(c,[i for i in (k quo 2+1)..k|prime?(i)]);j:=0;c:=a;repeat(j=n=>break;j:=j+1;b:=a;a:=[abs(b.(i+1)-b.i)for i in 1..(#b-1)]);j:=2;repeat(j>#a=>break;a.j~=2 and a.j~=1 and a.j~=0=>return j-1;j:=j+1);k:=k*2))

ungolf it and test
f(n:PI):PI==
  k:=n*10
  c:List NNI:=[i for i in 1..(k quo 2)|prime?(i)]
  repeat
    a:=concat(c,[i for i in (k quo 2+1)..k|prime?(i)])
    j:=0;c:=a
    repeat
       j=n=>break
       j:=j+1
       b:=a
       a:=[abs(b.(i+1)-b.i)  for i in 1..(#b-1)]
    j:=2
    repeat
       j>#a=>break
       a.j~=2 and a.j~=1 and a.j~=0 => return j-1
       j:=j+1
    k:=k*2

(4) -> [g(i)  for i in 1..30]
   (4)
   [3, 8, 14, 14, 25, 24, 23, 22, 25, 59, 98, 97, 98, 97, 174, 176, 176, 176,
    176, 291, 290, 289, 740, 874, 873, 872, 873, 872, 871, 870]

it if not find the solution expand the prime list of 2*x in a loop and recompute all the remain lists. 3 seconds for find g(30)

source: Stack Exchange

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

sort: votes


text:
Name the Hadrons
Challenge
Given a quark composition of a particle as input, output the corresponding hadron's name.
Quarks will be represented by a capital letter and antiquarks by a lowercase letter.
The quarks may be in any order, not necessarily the order given below.
Built-in functions the access data about particles and/or quarks are disallowed.
The only quarks you will be given are U (up), u (antiup), D (down), d (antidown), S (strange), s (antistrange), C (charm), c (anticharm), B (bottom or beauty), b(antibottom or antibeauty).
List of Hadrons and their quark compositions
Note that although there are various other hadrons such as pentaquarks and glueballs etc., you only need to support the hadrons given in the following lists
Baryons (QQQ) and Antibaryons (qqq)
The names in brackets are alternative names for the particles. You may output either name.
Input - Output

UUU - delta++
uuu - antidelta++
UUD - delta+ (proton)
uud - antidelta+ (antiproton)
UDD - delta0 (neutron)
udd - antidelta0 (antineutron)
DDD - delta-
ddd - antidelta-
UUS - sigma+
uus - antisigma+
UDS - sigma0
uds - antisigma0
DDS - sigma-
dds - antisigma-
USS - xi0
uss - antixi0
DSS - xi-
dss - antixi-
SSS - omega-
sss - antiomega-

UUC - charmed sigma++
uuc - charmed antisigma++
UDC - charmed sigma+
udc - charmed antisigma+
DDC - charmed sigma0
ddc - charmed antisigma0
UUB - bottom sigma+
uub - bottom antisigma+
UDB - bottom sigma0
udb - bottom antisigma0
DDB - bottom sigma-
ddb - bottom antisigma-
USC - charmed xi+
usc - charmed antixi+
DSC - charmed xi0
dsc - charmed antixi0
UCC - double charmed xi++
ucc - double charmed antixi++
DCC - double charmed xi+
dcc - double charmed antixi+
USB - bottom xi0
usb - bottom antixi0
DSB - bottom xi-
dsb - bottom antixi-
UBB - double bottom xi0
ubb - double bottom antixi0
DBB - double bottom xi-
dbb - double bottom antixi-
UCB - charmed bottom xi+
ucb - charmed bottom antixi+
DCB - charmed bottom xi0
dcb - charmed bottom antixi0
SSC - charmed omega0
ssc - charmed antiomega0
SSB - bottom omega-
ssb - bottom antiomega-
SCC - double charmed omega+
scc - double charmed antiomega+
SCB - charmed bottom omega0
scb - charmed bottom antiomega0
SBB - double bottom omega-
sbb - double bottom antiomega-
CCB - double charmed bottom omega+
ccb - double charmed bottom antiomega+
CBB - charmed double bottom omega0
cbb - charmed double bottom antiomega0
CCC - triple charmed omega++
ccc - triple charmed antiomega++
BBB - triple bottom omega-
bbb - triple bottom antiomega-

Mesons (Qq)
Input - Output

Ud - pion+
Uu - pion0
Dd - pion0
Du - pion-
Us - kaon+
Ds - kaon0
Sd - antikaon0
Su - kaon-
Ss - phion0
Cd - D meson+
Dc - D meson-
Cu - D meson0
Uc - antiD meson0
Cs - strange D meson+
Sc - strange D meson-
Cc - psion0
Bu - B meson-
Ub - B meson+
Db - B meson0
Bd - antiB meson0
Sb - strange B meson0
Bs - strange antiB meson0
Bb - upsilon0

Winning
Shortest code in bytes wins.

Built-in functions the access data about particles and/or quarks are disallowed. I'm looking at you, Mathematica.

So, this challenge is essentially to compress aa look up table?

@RohanJhunjhunwala there is actually quite a lot of logic behind the values albeit it takes time to find.

Mathematica does have a ParticleData function with a QuarkContent option.

@dzaima what I meant was, there is a look up table which can be generated through a logical means, but the goal is to generate it with the shortest code.

Doesn't look hard. I mean, each quark has its own electric charge, you only have to handle the name, not the charge.

It seems the baryons can be any combination of 3 quarks of the same case. Mesons are combinations of 2 quarks of opposite case,  but for mesons Cb and Bc are missing. Is this intentional? 2. Ordering the letters differently would mean the same thing -  must our program be able to handle different orders of letters, or will they always be ordered as shown? (i.e. will it always be UDS for example or could it be SUD or DSU for example?) Similarly for mesons could we have uD?

@LevelRiverSt Cb and Bc being missing are most likely an oversight. Since there's no ordering to the quarks in QCD, I'd expect that the quarks could be named in any order. However, clarification is needed from the author.

@Level, "the quarks may be in any order, not necessarily the order given below."

There is no Top quark in your challenge, but it's too late to change. (Also its just bottom, not beauty or something. There is no such quark as a 'beauty quark'.)

@SIGSEGV 1. A top quark decays too quickly for it to interact via the strong force and form into hadrons. 2. The bottom quark at one point was called a beauty quark, as per Murray Gell-Mann's poetic naming of charm and beauty, but bottom was favoured by boring physicists

@LevelRiverSt I couldn't find any mention of a Cb or a Bc meson anywhere, so I couldn't find a name for it

Read name the hard-ons... I'll go back to elementary school now ._..

SOGL 0.11, 341 339 333 310 305 305 300 bytes
‘θw±
on”≥
0c{≤
”=?"▒
on0”←"█
c SW?"▲
?ļ0←j ►
?"anti”o}▼
SD”;W¡+}□
=?ļ-←ļ+←■
‘B≤a=+}:?"⁽¬Τk⅜K±l?@+}ob@+o}▓
UCl2-? CA"K¼⁶▓ BA"δ╬▓cd≠▼≤: U=; D=++}"8}↕x╔:⁵F┘¹±o≤"B□"κ§)Ƨ7%s±p←"Ss▒phi█Cc▒psi█Bb▒upsil█SdUcBd”2n{=▼}≤"U□1>?▲ka≥pc DW►S■"pi≥Pcρ►D■▲)»β⁴‘o}ƧBs=▼ Dc BW?X B}" mes≥+p"D═S┐╔¬ν↑FνF⌠V3╗βstA\≈²‘:cW2+Wp

JavaScript (ES6), 456 448 431 420 bytes
This code is using only two small lookup tables:

one to identify the quarks: 'CUBDScubds'
another one to detect the 'anti' prefix of Mesons: 'SdUcBdBs'

Everything else is deduced from the quarks.
(s,[a,b]=[...s].map(c=>(i='CUBDScubds'.search(c)%5,m|=1<<i,j+=i<2,k+=i&1,p+=i?i-2?'':'bottom ':'charmed ',i),m=j=k=0,p=''))=>s[2]?p.replace(/(\w+) \1( \1)?/,(_,a,b)=>b?'triple'+b:'double '+a)+(s>'Z'?'anti':'')+['omega','xi','sigma','delta'][k]+('-0+'[j]||'++'):(m&16&&m&5?'strange ':'')+(~'SdUcBdBs'.search(s)?'anti':'')+(m&1?m^1?'D mes':'psi':m&4?m^4?'B mes':'upsil':m&16?m^16?'ka':'phi':'pi')+'on'+'-0+'[(a<2)-(b<2)+1]

let f =

(s,[a,b]=[...s].map(c=>(i='CUBDScubds'.search(c)%5,m|=1<<i,j+=i<2,k+=i&1,p+=i?i-2?'':'bottom ':'charmed ',i),m=j=k=0,p=''))=>s[2]?p.replace(/(\w+) \1( \1)?/,(_,a,b)=>b?'triple'+b:'double '+a)+(s>'Z'?'anti':'')+['omega','xi','sigma','delta'][k]+('-0+'[j]||'++'):(m&16&&m&5?'strange ':'')+(~'SdUcBdBs'.search(s)?'anti':'')+(m&1?m^1?'D mes':'psi':m&4?m^4?'B mes':'upsil':m&16?m^16?'ka':'phi':'pi')+'on'+'-0+'[(a<2)-(b<2)+1]

res = [
  "UUU", "uuu", "UUD", "uud", "UDD", "udd", "DDD", "ddd", "UUS", "uus", "UDS", "uds", "DDS", "dds", "USS", "uss",
  "DSS", "dss", "SSS", "sss", "UUC", "uuc", "UDC", "udc", "DDC", "ddc", "UUB", "uub", "UDB", "udb", "DDB", "ddb",
  "USC", "usc", "DSC", "dsc", "UCC", "ucc", "DCC", "dcc", "USB", "usb", "DSB", "dsb", "UBB", "ubb", "DBB", "dbb",
  "UCB", "ucb", "DCB", "dcb", "SSC", "ssc", "SSB", "ssb", "SCC", "scc", "SCB", "scb", "SBB", "sbb", "CCB", "ccb",
  "CBB", "cbb", "CCC", "ccc", "BBB", "bbb", "Ud",  "Uu",  "Dd",  "Du",  "Us",  "Ds",  "Sd",  "Su",  "Ss",  "Cd",
  "Dc",  "Cu",  "Uc",  "Cs",  "Sc",  "Cc",  "Bu",  "Ub",  "Db",  "Bd",  "Sb",  "Bs",  "Bb"
]
.map(s => s + ' - ' + f(s)).join("\n");

console.log(res);

Perl 5, 318 bytes
$_=<>;$h=qw/- ++ + 0/[y/uc//*2*($i=3-map{${lc;}++}/./g)-$u-$c-$i];$a=($i?!$h&&/[dUB]/:/[a-z]/)&&anti;map{/(.)/;$q.=("","$_ ","double $_ ","triple $_ ")[$$1]}charmed,bottom;print(($i?($u+$d>1?pi:$s>1?phi:$c>1?psi:$b>1?upsil:$c+$b?($s?"strange $a":$a).($b?B:D).' mes':$a.ka).on:$q.$a.qw/omega xi sigma delta/[$u+$d]).$h)

Newlines added for readability (slightly):
$_=<>
$h=qw/- ++ + 0/[y/uc//*2*($i=3-map{${lc;}++}/./g)-$u-$c-$i]
$a=($i?!$h&&/[dUB]/:/[a-z]/)&&anti
map{/(.)/;$q.=("","$_ ","double $_ ","triple $_ ")[$$1]}charmed,bottom;
print(($i?($u+$d>1?pi:$s>1?phi:$c>1?psi:$b>1?upsil:$c+$b?($s?"strange $a":$a).($b?B:D).' mes':$a.ka).on:$q.$a.qw/omega xi sigma delta/[$u+$d]).$h)


text:
Rotate the Roots
Given a nonzero polynomial with integer coefficients and roots that are on the imaginary and on the real line such that if a is a root then so is -a, return another polynomial with the roots rotated by 90 degrees.
Details
The polynomial can be given in any reasonable format, e.g. as a list of coefficients. The symmetry condition that a is a root if and only if -a is a root too enforces the rotated polynomial to have real integer coefficients as well.
Examples
In the following the polynomials are given as a list of coefficient of the monomials in descending degree. (i.e. the constant comes last)
The polynomial x^2-1 has roots {1,-1}. Rotating them by 90° means multiplying by i (the imaginary unit), so the output polynomial should have the roots {i,-i}, which is x^2 + 1.
Input / Output
[1 0 10 0 -127 0 -460 0 576]  [1 0 -10 0 -127 0 460 0 576]
[1 0 -4 0] [1 0 4 0]
[1] [1]

May I take in the degree of the polynomial as well as the polynomial

Yes I think that is acceptable.

All your examples use monic polynomials. Can we assume the input polynomial will be monic? Does the output polynomial have to be monic?

No it can also have other leading coefficients than 1, and the output is also just defined up to a integral multiple.

It seems the format doesn't have to be a list of coefficients. How far do the reasonable formats go? Can my format be a string expression in the indeterminate x, so that my submission can string-replace x with (i*x)? Can my format a function that evaluates the polynomial, so that my submission is to compose it with the function x -> i*x?

In the coefficient list form, can our output polynomial have leading zeroes?   Can the coefficient be floats like 4.0? Complex numbers like 4.0+0j?

Yes, any of them are acceptable.

@xnor String representations are valid too as long as they produce integer (i.e. real) coefficients.

Mathematica, 10 Bytes
Pure function which takes a function of x and substitutes in ix.
#/.x->I*x&

Alternative with only 7 bytes but not quite sure if it counts. Pure function which takes in a pure function and returns a function of x.
#[I*x]&

And you didn't even need any builtins!

I'm pretty sure a pure function polynomial is a "reasonable format" (like it was here) It uses # as the variable and has a & at the end.

I would upvote this twice if I could

My only concern about the second answer was the mismatch between input (a pure function) and output (a function of x).

Jelly, 5 bytes
Jı*Ċ×

Try it online!
How it works
Multiplies the first element by 1, the third element by -1, etc.
Jı*Ċ×  argument: z
J      [1,2,...,len(z)]
 ı     i (the imaginary unit)
  *    to the power of (each element)
   Ċ   imaginary part
    ×  multiply by input (vectorize)

Proof of algorithm
Let the polynomial be f(x).
Since we are guaranteed that if x is a root then so is -x, so f must be even, meaning that its coefficient for the odd powers must be 0.
Now, rotating the roots by 90° is essentially f(ix).
Expanding then comparing coefficients proves the algorithm.

So, we need not touch the 2,4th,6th, 8th etc?

Those are zero anyway.

Your trick with ı*Ċ is very nice, you should explain it :)

@Leo It's essentially a straightforward implementation though...

The logic here is not quite right, because you can instead have all coefficients for even powers be 0.

@ØrjanJohansen Are you saying that the coefficients for odd powers can be non-zero?

@ØrjanJohansen Could you give me an example?

x^5 - x^3 + x.

@ØrjanJohansen You're right. You should talk to flawr about that.

I already did, we cleared it up in the comments and then deleted them again. Note that the test cases are in descending order.

JavaScript (ES6), 25 bytes
a=>a.map((e,i)=>i%4?-e:e)

The original polynomial has solutions of the form x = ±a where a lies on the real or imaginary line. Except when a = 0 (in which case x is a factor of the polynomial), this means that x² - a² is a factor of the polynomial (which means alternate terms are always zero). Now when we rotate the roots, the factor changes to x² + a². Since all the factors change at the same time, the third term of the polynomial, which is the sum of all the -a² terms, changes sign, the fifth term, which is the sum of products of pairs of -a² terms, keeps the same sign, etc. alternating every other term.

Octave, 27 bytes
@(x)round(poly(roots(x)*j))

Try it online!
This directly applies the definition: compute roots, multiply by j, convert back from roots to polynomial. A final rounding is necessary because of floating-point numerical errors.

Python 3, 42 bytes
f=lambda x,s=1:x and[0,x[0]*s]+f(x[2:],-s)

Try it online!

S.I.L.O.S, 71 66 bytes
readIO
b=i
lbla
readIO
d=c
d&2
i=i*(1-d)
printInt i
b-1
c+1
if b a

Try it online!
I have no clue what wizardry @Leaky Nun did here to save 5 bytes.
Took me a second to figure out, but The second bit of C will alternate like we want. Therefore @Leaky Nun exploited this to save the bits we need.

66 bytes

Casio-Basic, 8 bytes
n|x=x

Unnamed function, using Ian Miller's Mathematica approach. The imaginary  from the Math2 keyboard needs to be used (counts as 2 bytes, char code 769), and the polynomial should be entered as an equation of x.
7 bytes for the code, 1 byte to specify n as a parameter.
Explanation: Takes the equation n, then simply replaces all instances of x with x.

Pari/GP, 16 bytes
p->x=I*x;eval(p)

Try it online!

TI-Basic, 20 bytes
seq(real(i^X/i)Ans(X),X,1,dim(Ans

If stored in prgmA, run with:
{1, 0, 3, 0, 1}:prgmA

seq( just had to be the one* command that doesn't support complex numbers. :)
*: Exaggeration

Stax, 5 bytes
Æ[]▐↨

Run and debug online!
Port of the Jelly answer.
Uses ASCII representation to explain:
mih|1*
m         Map each element with rest of program, print mapped results on individual lines
 i        Current 0-based loop index
  h       Floor(i/2)
   |1     (-1)^(i/2)
     *    Multiply with current element

If there can be leading zeros, they need to be trimmed first and it can be done at the cost of another byte.


text:
Is it a Cactus?
In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.
Here is a Cactus with 3 simple cycles outlined with dashed lines.

The following graph is similar to the one pictured above but is not a Cactus because the two vertices labeled in red are shared by two simple cycles.

Things can get a little bit trickier, for example the following graph:

Might look like a Cactus but it is not.  This can be shown by highlighting the following cycle:

This cycle shares more than one point with a lot of the more obvious cycles in the graph.
Definitions

A connected graph is a graph such that there exists at least one path between any two vertices.
A simple cycle is a path on a graph that starts and ends at the same vertex and visits no vertex more than once.
A simple graph is an undirected, unweighted graph such that no vertices are connected two each other by more than one edge and no vertex is connected to itself.  A simple graph is the most basic type of graph and is what most people mean when they say graph.

Task
Take a simple graph as input and decide whether it is a Cactus graph.  You should output two distinct values one for True and one for False.  You may take input in any format you see fit.
This is code-golf so you should aim to minimize the byte count of your answers.
Test Cases
Test Cases as Adjacency Matrices

What complexity class does this problem belong to?

Mathematica, 62 bytes
Sort@#==#⋃#&[Join@@FindCycle[#,∞,All]]&&ConnectedGraphQ@#&

Checks: (find all cycles, there are no duplicate edges) and (The graph is a connected graph)

g should be #, right?

So you're telling me there's no isCactus builtin? I'm disappointed.

Someone should write one.

You should put Mathematica Simplified as a separate answer.

@Aaron It would be CactusQ if it existed, I believe.

Python 2, 299 289 bytes
j=input()
n=len(j)
Q=range(n*n)
L=N=[[{1<<i%n|1<<i/n}]*j[i/n][i%n]for i in Q]
for _ in Q:N=[[a|b for A,B in zip(N[i/n::n],N[i%n::n])for a in A for b in B if{1}>a&b]for i in Q];L=[L[i]+N[i]for i in Q]
1/all(L[i]*all(A&B|B&C|C&A for A in L[i]for B in L[i]for C in L[i])for i in Q if i%n<i/n)

Try it online! (simulates STDIN to run all test cases at once)
-10 bytes thanks to @ovs
Takes input as an adjacency matrix from STDIN.
Outputs by the presence of an error in accordance with a default output method. An IndexError represents non-cactus, and no error represents cactus.
Theory
A simple cycle can be thought of as two disjoint simple paths between a pair of vertices. Similarly, our conjoined cycles correspond to three distinct simple paths being present between a pair of vertices (better explanation near the bottom of the ungolfed code).
To detect these conjoined cycles, we:

find all paths between all pairs of vertices, keeping track of the edges using Python sets.
for each pair of vertices, if three paths are pairwise disjoint, then a conjoined cycle is present.

The first bullet has the side-benefit of making the connectedness easy to test: if a path exists between every pair of distinct vertices, then the graph is connected.
Potential improvements
If input could be taken via STDIN as n followed by n*n rows of boolean values, 13 bytes could be saved, but it doesn't feel right.
A lot of generator for-loop code is repeated, so surely there's a better way. I tried itertools.product, but that ended up with a net cost of +9 bytes. I might have to go with exec/string-replacement abuse like in Baba, which could especially help with for i in Q being used four times.
Ungolfed Code
Python 2 has two main benefits over Python 3 here:

input() automatically parses the input
Division is floor division by default.

j = input()
n = len(j)
Q = range(n * n)
# Replace each 0 in the adjacency matrix with []
#   and each edge with a label such that the element of N representing the edge m→n has the
#   same label as the element of N representing the edge n→m
L = N = [
    # Each edge label is a 2-hot integer (easiest way to ensure ensure equality in both directions since the graph is undirected)
    # Each path's edge sequence is stored as a set of edge labels
    # N[i] is a list of paths from vertex i % n to vertex i / n
    # N[i] starts out as all possible paths of length 1, i.e. edges
    # L[i] starts as the same
    [{1 << i%n | 1 << i/n}]
    * j[i / n][i % n]
    for i in Q
]

# Repeat this n**2 times:
# (In reality, only about log_2(n) times is needed, but there isn't a big performance loss)
for _ in Q:
    # Update N from the list of all possible paths of length k to the list of all possible paths of length k+1
    N = [
        [
            # The union of two paths is possible
            a | b
            # ... for every paths list in N
            for A, B in zip(N[i / n :: n], N[i % n :: n])
            # ... and for every pair of paths in each of these paths lists
            for a in A
            for b in B
            # Limit the search to be through disjoint paths only
            # equivalent to `{1}>a&b == not a&b` because a,b contain only tuples, not integers
            if {1} > a & b
        ]
        for i in Q
    ]
    # Update L from being list of all possible paths of length at most k to the list of all possible paths of length at most k+1
    # (It really seems like these two generator for-loops can be merged into one for loop, but I couldn't get it to work
    #  I might be able to store L and N in the same list, but that's super slow performance; hard to test)
    L = [L[i] + N[i] for i in Q]
# Raises a ZeroDivisionError iff the result of the `all` call is False
1/all(
    # L[i] is falsey ←→ L[i] is an empty list ←→
    # no path exists between vertices i%n and i/n ←→ graph is not connected ←→ not cactus
    L[i]
    * all(
        # `A & B | B & C | C & A` is falsey
        # → A,B,C are three disjoint simple paths between vertices i%n and i/n
        # → AB' and CB' are two cycles that share an edge
        # → The graph is non-cactus
        A & B | B & C | C & A
        # using itertools.product is net +9 bytes last I checked
        for A in L[i]
        for B in L[i]
        for C in L[i]
    )
    for i in Q
    # L is symmetric, and we don't want to check the main diagonal
    if i % n < i / n
)

Super-ungolfed code
def dot(r1, r2):
    return [
        path1 | path2
        for paths1, paths2 in zip(r1, r2)
        for path1 in paths1
        for path2 in paths2
        # simple paths, so exclude those that share edges
        if len(path1 & path2) == 0
    ]

def mul(paths1, paths2):
    return [[dot(row, col) for row in zip(*paths2)] for col in paths1]

def f(adj):
    n = len(adj)
    paths_length_1 = [
        [
            [{(min(x, y), max(x, y))}] if entry == 1 else []
            for x, entry in enumerate(row)
        ]
        for y, row in enumerate(adj)
    ]
    all_paths = paths_length_1
    paths_length_n = paths_length_1
    for _ in range(n):
        paths_length_n = mul(paths_length_1, paths_length_n)
        for y in range(n):
            for x in range(n):
                all_paths[y][x].extend(paths_length_n[y][x])
    for x, row in enumerate(all_paths):
        for y, paths in enumerate(row):
            # The graph is non-cactus if it is not conneted
            if x != y and len(paths) == 0:
                return False
            # The graph is non-cactus if there exist three piecewise disjoint simple paths A,B,C
            # between two nodes because A+B' forms one cycle and C+B' forms the other cycle
            for A, B, C in itertools.combinations(paths, 3):
                if len(A & B) == 0 and len(B & C) == 0 and len(A & C) == 0:
                    return False
    return True

I think frozenset([i%n,i/n]) can be replaced by 1<<i%n|1<<i/n, and if you flip error/non-error 1/... is a bit shorter than [0][...]

@ovs Added. And I must say, great idea with the two-hot integer

I just recently used this on my Erdős–Woods answer, but to save memory and time instead of bytes. Otherwise I wouldn't have seen it, it's definitely a bit unusual

JavaScript (Node.js), 130 bytes
f=(x,y,h)=>x.every(h=(c,i,g)=>!g||h([c[1],c[0]],i)?eval(y)-c[0]||f(x.filter(_=>i--),y+[,c]):0)>/(,\d+,).*(,\d+),.*\1.*\2$/.test(y)

Try it online!
Finds a path through a,b,a,b
y has form undefined,1,2 therefore eval(y) gets the last value in y

Didn't notice requirement of connection

Mathematica, with IGraph/M, 9 bytes
IGCactusQ

IGraph/M provides a Mathematica interface to the popular igraph network analysis package. You can use IGCactusQ function in  IGraphM`  package.
Needs["IGraphM`"];
IGCactusQ[g]

Ungolfed version of @JungHwan Min's Mathematica answer.
Clear["Global`*"];
g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3,
   3 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 4,
   3 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6,
   6 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8,
   8 \[UndirectedEdge] 5, 7 \[UndirectedEdge] 9,
   9 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 11,
   11 \[UndirectedEdge] 7, 8 \[UndirectedEdge] 12,
   8 \[UndirectedEdge] 13}, VertexLabels -> "Name",
  GraphLayout -> "SpringElectricalEmbedding"]

myCactusGraphQ[graph_] :=
 Module[{cycles, noDuplicateEdges },
  cycles = FindCycle[graph, \[Infinity], All]; (*Find all cycles in the graph, with no limit on their length *)
  noDuplicateEdges = DuplicateFreeQ[Join@@cycles];
  noDuplicateEdges && ConnectedGraphQ[graph] (*Finally, check that the graph is connected AND the noDuplicateEdges condition is met*)
]

Print["myCactusGraphQ[g]=", myCactusGraphQ[g]]


text:
Calculate the binary split sum of a word
Take a string, s containing printable ASCII-characters as input, and output its "binary split sum". Need an explanation?
How do you get the binary split sum?
We'll use the string A4 as an example in the following explanation.

Convert the characters to binary, treating each letters as a 7-bit ASCII character
A -> ASCII 65 -> 1000001
4 -> ASCII 52 -> 0110100

Concatenate the binary numbers into a new binary number
A4 -> 1000001 & 0110100 -> 10000010110100

Split the new binary number into chunks, where no 1 can have a 0 to its left. You should not split consecutive 1s.
10000010110100 -> 100000, 10, 110, 100

Convert these binary numbers to decimal
100000, 10, 110, 100 -> 32, 2, 6, 4

Take the sum of these numbers:
32 + 2 + 6 + 4 = 44

So, the output for the string A4 should be 44.

Test cases:
a
49

A4
44

codegolf
570

Hello, World!
795

I think this would have been a nicer challenge without the ASCII conversion step, just taking the (decimal) number after step 2 as input.

Well, 8372 actually.

@xnor, you might be right, and it would be cleaner. I had fun solving this in Octave though, and I hope others will enjoy solving it too :)

Python 2, 86 81 76 bytes
-5 bytes thanks Adnan
-5 bytes thanks xnor

s=0
for c in input():s=s*128+ord(c)
print eval(bin(s).replace('01','0+0b1'))

Try it online!
for c in input():s=s*128+ord(c) to do the ASCII conversion numerically, where *128 is used to left shift s 7 times (steps 1 and 2)
eval(('0'+new_bin).replace('01','0+0b1')) to split and sum (steps 3, 4 and 5)

Nice trick with the eval!  Doing the ASCII conversion numerically saves some bytes.

Jelly, 13 bytes
Oḅ128BŒg;2/ḄS

Try it online!
How it works
Oḅ128BŒg;2/ḄS  Main link. Argument: s (string)

O              Ordinal; map characters to their code points.
 ḅ128          Unbase 128; convert the resulting list from base 128 to integer.
     B         Binary; Convert the resulting integer to base 2.
      Œg       Group consecutive, equal bits.
        ;2/    Concatenate all non-overlapping pairs.
           Ḅ   Unbinary; convert from base 2 to integer.
            S  Take the sum.

I've missed that trick of base conversion before.

Ah, nice trick indeed!

MATL, 14 bytes
YB!'1+0*'XXZBs

Try it online!
Explanation
Consider input 'A4' as an example.
YB        % Implicit input. Convert to binary using characters '0' and '1'.
          % Gives a char matrix, where each row corresponds to a number
          % STACK: ['1000001'; '0110100']
!         % Transpose. This is necessary because MATL uses column-major
          % order when linearizing a matrix into a vector
          % STACK: ['10'; '01'; '01'; '00'; '01'; '00'; '10']
'1+0*'    % Push this string: regexp pattern
          % STACK: ['10'; '01'; '01'; '00'; '01'; '00'; '10'], '1+0*'
XX        % Regexp. Linearizes the first input into a row (in column-major
          % order), and pushes a cell array of substrings that match the
          % pattern given by the second input
          % STACK: {'100000'; '10'; 110'; '100'}
ZB        % Convert each string into a decimal number. Gives numeric vector
          % STACK: [32; 2; 6; 4]
s         % Sum. Implicitly display
          % STACK: 44

05AB1E, 14 bytes
Çžy+b€¦Jγ2ôJCO

A port of my Jelly answer, using the 128 offset from Adnan's 05ab1e answer (rather than the 256 in the Jelly answer I wrote).
Try it online!
How?
Çžy+b€¦Jγ2ôJCO
Ç              - to ordinals
   +           - add
 žy            - literal 128
    b          - to binary
     €         - for each
      ¦        -   dequeue
       J       - join
        γ      - group into chunks of equal elements
          ô    - split into chunks of
         2     - literal 2
           J   - join
            C  - from binary
             O - sum

05AB1E, 18 bytes
Code:
Çžy+b€¦JTR021:2¡CO

Explanation:
Ç                   # Take the ASCII value of each character
 žy+                # Add 128 to each value (to pad each with enough zeros)
    b               # Convert to binary
     €¦             # Remove the first character
       J            # Join the array
        TR021:      # Replace 01 by 021
              2¡    # Split on the number 2
                C   # Convert from binary to decimal
                 O  # Sum them all up

Uses the 05AB1E encoding. Try it online!

JavaScript (ES6), 97 92 bytes
s=>eval(s.replace(/./g,c=>(128+c.charCodeAt()).toString(2).slice(1)).replace(/1+/g,'+0b$&'))

Edit: Saved 5 bytes with some help from @ConorO'Brien.

My own solution was 97 bytes, too: s=>eval([...s].map(e=>(e.charCodeAt()+128).toString(2).slice(1)).join``.replace(/1+0*/g,'+0b$&')) You can use my replace method to save a byte, I think

@ConorO'Brien More than a byte, I think!

Oo, nice :D

Japt, 18 12 bytes
c_¤ùT7Ãò< xÍ
c_           // Firstly, take the input and map over it as charcodes.
  ¤          // Take the binary representation of each item
   ùT7       // and left-pad it with zeroes to standardize the items.
      Ã      // After all of the above,
       ò<    // partition the result where ever a 0 precedes a 1.
          xÍ // Then sum the numbers from base 2.

Takes input as a single string.
I also tried out the 128 or 256 addition used by other answers, but 0-padding was shorter to use.
Shaved off a whole whopping 6 bytes thanks to ETHproductions and Oliver.
Try it out here.

You can use more auto-functions here: òÈ<YÃ can be ò< (with trailing space), and Ën2Ãx can be xn2. You can also use T in place of 0 to save on the comma. (Also, feel free to join us in the Japt chatroom if you ever have questions or would like help with golfing :-) )

@ETHproductions Thanks again, especially for the T trick, didn't know you could (ab)use variables for that, that's very handy. The auto-function xn2 looks a bit weird when compiled, x("n", 2), so I think it will still take a bit before I fully understand the logic behind them. With your help, the Japt solution is now tied for the first place with the Jelly answer.

ETHproductions recently made a shortcut for n2 : Í. It hasn't hit TIO yet, but you can use it here: https://ethproductions.github.io/japt/?v=1.4.5&code=Y1+k+VQ3w/I8IHjN&input=IkE0Ig==

@Oliver Wow, that's very bleeding edge, that isn't even covered in the interpreter shortcuts reference yet. Thanks a lot!

Jelly, 16 15 bytes
-1 byte thanks to Dennis (no need to flatten by 1 when a full flatten is fine - replace ;/ with F)
O+⁹Bṫ€3FŒg;2/ḄS

Try it online!
How?
O+⁹Bṫ€3FŒg;2/ḄS - Main link: list of characters, s    e.g. "A4"
O               - cast to ordinal (vectorises)        [65,52]
  ⁹             - literal 256
 +              - add (vectorises)                    [321, 308]
   B            - convert to binary (vectorises)      [[1,0,1,0,0,0,0,0,1],[1,0,0,1,1,0,1,0,0]]
    ṫ€3         - tail €ach from index 3              [[1,0,0,0,0,0,1],[0,1,1,0,1,0,0]]
       F        - reduce with concatenation           [1,0,0,0,0,0,1,0,1,1,0,1,0,0]
        Œg      - group runs of equal elements        [[1],[0,0,0,0,0],[1],[0],[1,1],[0],[1],[0,0]]
          ;2/   - pairwise reduce with concatenation  [[1,0,0,0,0,0],[1,0],[1,1,0],[1,0,0]]
             Ḅ  - convert from binary (vectorises)    [32,2,6,4]
              S - sum                                 44

;/ can be replaced with F.

PHP, 116 Bytes
for(;$c=ord($argn[$i++]);)$r.=sprintf("%07b",$c);$t=mb_split("(?<=0)(?=1)",$r);echo array_sum(array_map(bindec,$t));

Online Version
PHP, 117 Bytes
for(;$c=ord($argn[$i++]);)$r.=sprintf("%07b",$c);$t=preg_split("#0\K(?=1)#",$r);echo array_sum(array_map(bindec,$t));

Try it online!
PHP, 120 Bytes
for(;$c=ord($argn[$i++]);)$r.=sprintf("%07b",$c);preg_match_all("#1+0+#",$r,$t);foreach($t[0]as$b)$s+=bindec($b);echo$s;

Try it online!
or
for(;$c=ord($argn[$i++]);)$r.=sprintf("%07b",$c);preg_match_all("#1+0+#",$r,$t);echo array_sum(array_map(bindec,$t[0]));

Pyth, 21 bytes
It's too long...
siR2:.BiCMQ128"1+0+"1

Test suite.

[F#], 249 245 bytes
open System
let rec c a=function|[]->[a]|'0'::'1'::y->(a+"0")::(c""('1'::y))|x::y->c(a+string x)y
let x i=c""(String.Join("",(Seq.map(fun c->Convert.ToString(int c,2).PadLeft(7,'0'))i))|>Seq.toList)|>Seq.map(fun c->Convert.ToInt32(c,2))|>Seq.sum

Try it online!
Note: the version on tio.run has "open System" in the header, I've added its count to the code above.
I'm not sure what the rules are on imports.
Ungolfed
let rec convert acc = function
    | [] -> [acc]
    | '0'::'1'::xs -> (acc + "0") :: (convert "" ('1'::xs))
    | x::xs -> convert (acc + string x) xs

let calculateSum input =
    let binary = Seq.map (fun x -> Convert.ToString(int x, 2).PadLeft(7, '0')) input

    String.Join("", binary)
    |> Seq.toList
    |> convert ""
    |>Seq.map (fun x -> Convert.ToInt32(x, 2))
    |>Seq.sum

if open System is the same as C#s using System; then yes you need to include it in the count. If you can do it in F# you could fully qualify whatever the System is for . For example, in C# System.Console... instead of using System;Console...

@TheLethalCoder It is the same, yes. Also, thanks for clarifying this :) I opted for the "open.." version because it's not only String, but also Convert that live in that namespace.

Ruby, 60 bytes
->s{s.bytes.map{"%07b"%_1}.join.scan(/1+0*/).sum{_1.to_i 2}}

Attempt This Online!

Perl 6, 62 bytes
{sum map {:2(~$_)},.comb».ord».fmt('%07b').join~~m:g/11*0*/}

use .ords instead of .comb».ord. prefix [~] can often be used instead of .join. comb exists which does the m:g/… thing. /11*0*/ can be shortened to /1+0*/. I came up with {sum map {:2($_)},comb /1+0*/,[~] .ords».fmt('%07b')}

mathematica 193 bytes
f=FromDigits;l=Flatten;(S=Split@l@Table[PadLeft[IntegerDigits[ToCharacterCode@#,2][[k]],7],{k,StringLength@#}];Plus@@Table[f[RealDigits@f@Join[S[[i]],S[[i+1]]],2],{i,1,Length@S-1,2}]+Last@l@S)&

You can save 7 bytes by doing f=FromDigits;l=Flatten; at the start, and then replacing all instances of those two functions with f and l.

J, 34 bytes
[:+/@(,#.;.1~1,1=2#.\,)(7#2)#:3&u:

Try it online!
Explanation
[:+/@(,#.;.1~1,1=2#.\,)(7#2)#:3&u:  Input: array of characters S
                              3&u:  Get ASCII values of each character
                       (7#2)        Array with 7 copies of the value 2
                            #:      Convert each value to a base 2 array with length 7
[:  (                 )             Operate on those binary values
                     ,                Flatten it
                 2  \                 For each infix of size 2
                  #.                    Convert it to decimal from binary
               1=                     Test each value for equality to 1
             1,                       Prepend a 1
      ,                               The flattened binary values
         ;.1~                         Chop that at each occurrence of a 1
       #.                               Convert each chop from binary to decimal
 +/@                                Reduce by addition

J, 40 bytes
+/>#.&.>(1,}.|.1 0 E.|.b)<;.1 b=.,#:a.i.

usage:
+/>#.&.>(1,}.|.1 0 E.|.b)<;.1 b=.,#:a.i.'A4'

returns 44

Clojure, 150 bytes
#(loop[[c & C](for[i % j[64 32 16 8 4 2 1]](mod(quot(int i)j)2))p 0 r 0 R 0](if c(if(=(dec c)p 0)(recur C c 1(+ R r))(recur C c(+(* 2 r)c)R))(+ R r)))

Well I was hoping the conversion from ASCII to bytes was shorter than this. The actual loop body is quite short, using r to accumulate the current result and R to accumulate the total result. If the previous bit p is 0 and the current bit c is 1 then we split a new chunk and accumulate to R, otherwise we update the r and keep R as it was.

Python 123 bytes
lambda w:sum(map(lambda x:int(x,2),"".join(map(lambda x:bin(ord(x))[2:].zfill(7),list(w))).replace("01","0:1").split(":")))

Updated, thanks to Martin Ender.

Welcome to PPCG! All answers need to be either full programs or callable functions (as opposed to snippets where the input is stored in a hardcoded variable). The function can be unnamed, though, so including a lambda w: would be enough to make your answer valid.

Sorry, I probably didn't phrase that well. Your edit is still invalid because a) the input is hardcoded, b) If this is a full program, it doesn't actually print the result. For a full program you'd have to read the input from standard input or a command-line argument, and print the result to standard output. That's why I said it's probably easiest if you submit it as a function by adding lambda w:.

Ohhh, Ok, i get it, it would be enough like this: f=lambda w:sum(map(lambda x:int(x,2),"".join(map(lambda x:bin(ord(x))[2:].zfill(7),list(w))).replace("01","0:1").split(":")))

yep, that's valid. You don't even need the f=, because we allow unnamed functions (unless you reference the function name for recursive calls).

K (oK), 31 bytes
Solution:
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$

Try it online!
Examples:
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$,"a"
49
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$"A4"
44
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$"codegolf"
570
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$"Hello, World!"
795

Explanation:
Convert to ASCII values, convert to 7-bit binary, flatten, find where differs, and against original list to find where 1s differ. Cut at these indices, convert back to decimal and sum up:
+/2/'_[;x]&x&~~':x:,/(7#2)\'`i$ / the solution
                            `i$ / convert to integer
                     (7#2)      / draw from 2, 7 times => 2 2 2 2 2 2 2
                          \'    / decode each (convert to binary)
                   ,/           / flatten
                 x:             / save as x
             ~~':               / not-not-each previous (differ)
            &                   / and with
           x                    / x
          &                     / indices where true
     _[;x]                      / projection, cut x at ...
  2/'                           / encode each (convert from binary)
+/                              / sum up

Bonus
Managed a 31 byte version in K4 too, but as there's no TIO for it I'm posting my oK solution.
+/2/:'_[;x]@&x&~~':x:,/1_'0b\:'

APL (Dyalog), 30 bytes
{+/2⊥¨(1∘+⊆⊢)∊¯7↑¨2⊥⍣¯1¨⎕UCS⍵}

Try it online!
How?
⎕UCS⍵ - Unicodify
2⊥⍣¯1¨ - encode each in binary
¯7↑¨ - and pad to the left with zeros to 7 places
∊ - flatten
1∘+⊆⊢ - partition by self increased by one
2⊥¨ - decode each from binary
+/ - sum

Factor + math.unicode, 73 bytes
[ [ "%07b"sprintf ] map-concat R/ (?<=0)(?=1)/ re-split [ bin> ] map Σ ]

Try it online!

[ "%07b"sprintf ] map-concat Convert each code point in the input string to a 7-bit binary number string and join them all together.
R/ (?<=0)(?=1)/ re-split Split into a sequence of strings down the middle of every 01.
[ bin> ] map Σ Convert each from binary string to decimal integer and sum.


text:
String subtraction
Objective
Create a function to reverse string concatenation
Input
Two strings (alphanumeric + spaces), where one should be subtracted for the other.

You can assume that the string to be subtracted will never be larger than the other one.

Output
The result from the subtraction
Subtraction
You should remove one string from the start or the end of another string.
If the string is present in the start and in the end, you can only remove one, which one will be removed is up to you.
If the string isn't in the start or in the end, or isn't an exact match, it is an invalid subtraction and you should output the original string.
Test Cases
Valid Subtraction
'abcde','ab' -> 'cde'
'abcde','cde' -> 'ab'
'abab','ab' -> 'ab'
'abcab','ab' -> 'abc' or 'cab'
'ababcde','ab' -> 'abcde'
'acdbcd','cd' -> 'acdb'
'abcde','abcde' -> ''
'abcde','' -> 'abcde'
'','' -> ''

Invalid Subtraction (returns original string)
'abcde','ae' -> 'abcde'
'abcde','aa' -> 'abcde'
'abcde','bcd' -> 'abcde'
'abcde','xab' -> 'abcde'
'abcde','yde' -> 'abcde'

Invalid Input (don't need to be handled)
'','a' -> ''

This is code-golf, so the shortest code in bytes wins!

Why is the result of the first case not cde? What do you mean by valid? Do we need to judge the validity of the input, or do you mean that we will not receive invalid inputs?

@LeakyNun was a typing error, fixed

I think the empty string edge-case should probably be in the invalid section - mind you I suppose it doesn't make any difference to the result :)

I think you should drop the terms "valid" and "invalid", as they have a common meaning on PPCG which you are clearly not intending.

Damn you, 'abcde','bcd' -> 'abcde', for breaking my solution

Can we assume the strings will be regex-safe (alphanumeric + spaces)?

I'd suggest 'ababcde',  'ab' → 'abcde' as a test case. Some naive algorithms fail on that one.

@ais523 good point

Wait, why 'abcde','bcd' -> 'abcde'? abcde contains bcd, and should therefore return ae.

@MDXF the objective here is "reverse a concatenation", not just to remove a substring c:

@Rod Yeah, just noticed that. Whoops.

@Rod You might consider retitling the challenge "Reverse string concatenation"?

Suggested Testcase AbcdEbcd, bcd => AbcdE and not AEbcd

@Wernisch I guess this is covered by 'acdbcd','cd' -> 'acdb', right?

@Rob, You are right, apologies.  Had incorrectly copied that test case.

Java 8, 46 45 44 40 bytes
-1 byte thanks to TheLethalCoder
-1 byte because I'm dumb (thanks Rod!)
-4 bytes thanks to Kevin Cruijssen
a->b->a.replaceFirst("^"+b+"|"+b+"$","")

Try it online! (includes all test cases)
A Java answer actually beats a few other practical languages. Smiles. (and now it beats JS!)

Use currying to save a byte a->b->

@TheLethalCoder Thanks.

Why did you leave in the unused hashmap in your online example?

You can change the First to All for -2 bytes. Because of the ^ and $ it's always either at the end or start of the String, so even with replaceAll it only replaces it once. Try it here. PS: I added the previous byte-counts striked-through to your answer, which is what usually is done after code-golf edits here on PPCG.

@KevinCruijssen I knew about the strike-throughs, guess I just forgot this time. However, if i use All instead of First, this becomes true: "abab" + "ab" -> ""

@Okx Ah, good call, missed that part of the abcab + ab test case. In that case you'll indeed need First. Oh, but you can still golf it by 4 bytes by changing "(^"+b+")|("+b+"$)" to "^"+b+"|"+b+"$" if I'm not mistaken.

Brachylog (Try It Online!), 12 bytes
~cpĊh.∧Ċtw|w

Try it online!
Takes the string to subtract from from standard input, and the string to subtract as a command line argument.
Explanation
~cpĊh.∧Ċtw|w
~c            Split {the input} into pieces
  p           and (possibly) rearrange those pieces
   Ċ          such that there are two pieces
    h         and the first
     .        matches the command line argument
      ∧       then
         w    print
        t     the last
       Ċ      piece.
          |   If all else fails,
           w  print {the input}.

JavaScript (ES6), 41 bytes
s=>t=>s.replace(eval(`/^${t}|${t}$/`),'')

Takes input via currying syntax, i.e. f("abab")("ab").

Now, why have I never thought to use eval() for constructing RegExes before?!

Retina, 21 bytes
1 byte thanks to Martin Ender.
(.*);(\1|(.*)\1$|)
$3

Try it online!

JavaScript (ES6), 76 70 45 41 bytes
s=>t=>s.replace(RegExp(`^${t}|${t}$`),"")

Try It

f=
s=>t=>s.replace(RegExp(`^${t}|${t}$`),"")
o.innerText=f(i.value="abcde")(j.value="ab")
i.oninput=j.oninput=_=>o.innerText=f(i.value)(j.value)
<input id=i><input id=j><pre id=o>

You don't need new .

@programmer500, I kinda gave up working on this when I saw ETH's version! :D Updated now. Thanks.

Japt, 11 9 bytes
k"^|$"¬qV

Try it online!

Perl 6, 21 bytes
->$_,$b {S/^$b|$b$//}

Try it
Expanded:
-> $_, $b {   # pointy block lambda

  S/          # Str replace and return (implicitly against ｢$_｣)

  |   ^ $b    # starting with the second argument
  |     $b $  # or ending with the second argument

  //          # replace with nothing.

}

TI-Basic (TI-84 Plus CE), 63 bytes
Prompt Str0,Str2
inString(Str0,Str2
If Ans
sub(Str0,1,Ans-1)+sub(Str0,Ans+length(Str2),length(Str0)-Ans+1-length(Str2→Str0
Str0

I have a question, why didn't you use Str1 as a variable?

@Zacharý I think I had something stored in it at the time. I don't really remember.

What does Ans even refer to on the fourth line?

@Zacharý Ans refers to the last evaluated value, so in this case it refers to the value returned by inString(, which is the index of the substring Str2 in the string Str0 or 0 if the substring does not appear. An if statement does not modify the value of Ans, so on the fourth line the index is still in Ans.

Oh, I forgot how inString worked. Nice golf!

APL (Dyalog), 31 30 bytes
-1 thanks to  Zacharý.
This actually uses reverse (i.e. the inverse of) concatenation! Takes original string as left argument, and what to subtract as right argument.
{0::⍺{0::⍺⋄,∘⍵⍣¯1⊢⍺}⍵⋄⍵,⍣¯1⊢⍺}

Try it online!
Ungolfed:
{
    0::⍺{         ⍝ if an error happens, apply the following function on the arguments
        0::⍺          ⍝ if an error happens, return the left argument unmodified
        ,∘⍵⍣¯1⊢⍺      ⍝ inverse-append right argument on left argument
        }⍵
    ⍵,⍣¯1⊢⍺      ⍝ inverse-prepend the right argument on the left argument
}

Legend:
{…} anonymous function
⍺ left argument of the current function
⍵ right argument of the current function
0::… if any error happens, execute this, else…
⍣¯1⊢ inverse
,∘⍵ concatenate ⍵ on the right
⍵, concatenate ⍵ on the left

I think you can save a byte with {0::⍺{0::⍺⋄,∘⍵⍣¯1⊢⍺}⍵⋄⍵,⍣¯1⊢⍺}.

@Zacharý Yes, thanks.

Bash, 66 61 49 bytes
case $1 in *$2)echo ${1%$2};;*)echo ${1#$2};;esac

Try it online!
less golfed:
a=$1;
case $1 in
    *$2)  c=${a%$2};;
    $2*)  c=${a#$2};;
      *)  c=$1;;
esac;
echo $c

Uses case to test begining or end, and array prefix/suffix (% / #) substraction

Nice use of case, but longer than necessary. The 2nd and 3rd pattern could be merged into a single one: *)c=${1#$2};;. Then with only 2 branches would be shorter to echo each directly instead of using variable $c: case $1 in *$2)echo ${1%$2};;*)echo ${1#$2};;esac. Or you could keep using it, but without case: c=${1%$2};[[ $c = $1 ]]&&c=${1#$2};echo $c.

Python, 69 68 64 57 51 45 bytes
This ended up being a completely different solution with Regex.
Thanks to Value Ink for -2 bytes!
and Felipe Nardi Batista for the massive -6 bytes!
import re
lambda s,c:re.sub(c+'$|^'+c,'',s,1)

Try it online!

For -2 bytes: re.sub(c.join("^|$"),'',s,1)

For -6 bytes:c+'$|^'+c

Mathematica, 162 bytes
(c=Characters;a=c@#;b=c@#2;l=Length;t={};If[l@Intersection[a,b]==l@b,If[MemberQ[Partition[a,l@b,1],b],t=a;Table[t=DeleteCases[t,b[[i]],1,1],{i,l@b}]],t=a];""<>t)&

test input style ["abcde","ab"]

Nice solution! You can save a byte by using # instead of #1 — they mean exactly the same. Also, instead of using StringJoin@t, you can cheat by joining an empty string to it with ""<>t, which automatically joins everything in t together too. Have you seen the Mathematica golfing tips page?

There are a few more things you can do to save bytes (I don't think you don't need to define t={}; at the start, for instance), but it might be easier to use a different approach entirely — have you tried using the StringReplace function?

You are allowed to take a String array as input, so you don't really need c=Characters;a=c@#;b=c@#2;

Also, l@Intersection[a,b] is l[a∩b].

PHP, 54 Bytes
[,$x,$y]=$argv;echo preg_replace("#^$y|$y$#","",$x,1);

Testcases

Python 2, 72 65 bytes
a,b=input()
l=len(b)
print[[a,a[:-l]][b==a[-l:]],a[l:]][b==a[:l]]

Try it online!
-7 bytes thanks to @FelipeNardiBatista

golfed

@FelipeNardiBatista thanks a lot!

Python 2, 68 bytes
def f(s,c):v=len(c);print[s[v:],s[:-v],s][[s[:v],s[-v:],c].index(c)]

Try it online!

Haskell, 49 bytes
f s a b|s==b=a|a/=b,h:t<-a=f(s++[h])t b|1<3=s
f""

Try it online! Usage: f"" "abcdef" "ab". Alternatively, define (-)=f""and use like  "abcdef" - "ab".
This regex-free solution works by recursively splitting the string in all its pre- and postfixes and checking whether the string to be substracted matches one of them.

C#, 88 bytes
s=>r=>s.StartsWith(r)?s.Substring(r.Length):s.EndsWith(r)?s.Substring(0,s.IndexOf(r)):s;

Compiles to a Func<string, Func<string, string>>.

R, 20 42 41 bytes
pryr::f(sub(sprintf('^%s|%s$',b,b),'',a))

-1 byte thanks to MickyT!
Returns an anonymous function (which has arguments in the order b,a). Computes the string difference a-b. sub is a simple substitution that swaps the first occurrence of the pattern with, in this case, the empty string ''. Constructs the regex with sprintf to match only at the beginning and end of string. Requires the pryr package to be installed.
On the TIO link, uses the more verbose function(a,b) definition for the function for four more bytes.
Try it online!

What about the 'abcde','bcd' -> 'abcde' case?

"sub is a simple substitution that simply swaps the first occurrence of b in a": Will this swap if the second string is in the middle of the first string?

I misread the question! Oops. Thanks for catching that!

you can get 1 byte back with sprintf('^%s|%s$',b,b)

@MickyT, thanks! fixed.

Ruby (lambda expression), 29 bytes
->a,b{a.sub /^#{b}|#{b}$/,""}

Yay for regex interpolation! Requires regex-safe subtrahends, but that's okay as per the challenge.

Tcl, 37 bytes
proc s {a b} {regsub "^$b|$b$" $a {}}

Try it online! (now running all tests)
Tcl is straightforward. proc s {a b} defines a function named s which takes parameters a and b. regsub substitutes {}, which is an empty string, for the value of b when it's at the start or end of a. The return is implicit.

AWK, 21 32 bytes
{sub("^"$2"|"$2"$",z,$1);$0=$1}1

Try it online!
Original submission naively replaced text within first string, not just at beginning or end.
{sub($2,z,$1);$0=$1}1

Try it online !
Originally tried without the braces, but it required tricks to print out empty lines and or no-matches which ended up adding more bytes than this version.

C, 96 bytes
It's common knowledge that string manipulation in C is cumbersome, as an extension golfing would be borderline masochistic. Sounds alright to me.
f(a,b,t,l)char**a,*b,*t;{t=*a;l=strlen(b);bcmp(t,b,l)?bcmp(t+=strlen(t)-l,b,l)||(*t=0):(*a+=l);}

One of the less readable programs I've written. Takes two inputs (despite how the function looks), a char** pointing to the string to deconcatenate and a char* which is the string to remove. The input pointer is edited in place and becomes the output (who cases about memory leaks anyway).
Example usage:
char *a = malloc(6);
strcpy(a, "abcde");
char *b = malloc(4);
strcpy(b, "abc");
f(&a,b);
printf("%s\n", a); // "de"

Common Lisp, 121 bytes
(lambda(x y)(cond((equal(#1=subseq x 0 #3=(length y))y)(#1#x #3#))((equal(#1#x #2=(-(length x)#3#))y)(#1#x 0 #2#))(t x)))

Try it online!
The usual wordy Common Lisp!
Ungolfed version:
(defun f(x y)
  (cond ((equal (subseq x 0 (length y)) y)               ; if x starts with y
         (subseq x (length y)))                          ; return rest of x
        ((equal (subseq x (- (length x) (length y))) y)  ; if x ends with x
         (subseq x 0 (- (length x) (length y))))         ; return first part of x
        (t x)))                                          ; else return x

Kotlin, 91 bytes
{a,b->val v=b.length
if(a.startsWith(b))a.drop(v)else if(a.endsWith(b))a.dropLast(v)else a}

Try it online!

? {a,b->var c=a.removePrefix(b);if(a==c){c=a.removeSuffix(b)};c}

@mazzy feel free to submit that as your own answer.

Powershell, 34 40 bytes
+6 bytes when Invalid Subtraction test cases added
param($s,$t)$s-replace"^$t(?!.*$t$)|$t$"

Comment:
The regexp expression ^$t|$t$ does not work as expected: it replaces both matches instead one (flag g always on). So, we are forced to use the negative lookahead group.
Test script:
$f = {
    param($s,$t)$s-replace"^$t(?!.*$t$)|$t$"
}

@(
    ,('abcde','ab', 'cde')
    ,('abcde','cde', 'ab')
    ,('abab','ab', 'ab')
    ,('abcab','ab', 'abc', 'cab')
    ,('ababcde','ab', 'abcde')
    ,('acdbcd','cd', 'acdb')
    ,('abcde','abcde', '')
    ,('abcde','', 'abcde')
    ,('','', '')

    ,('abcde','ae', 'abcde')
    ,('abcde','aa', 'abcde')
    ,('abcde','bcd', 'abcde')
    ,('abcde','xab', 'abcde')
    ,('abcde','yde', 'abcde')

    ,('','a', '')
) | % {
    $s,$t,$e = $_
    $r = &$f $s $t
    "$($r-in$e): $r"
}

Output:
True: cde
True: ab
True: ab
True: abc
True: abcde
True: acdb
True:
True: abcde
True:

QBIC, 57 bytes
Whegh, this is a mess in QBIC/QBasic...
B=@ `+B┘x=instr(;,;)~x|?_t_sB,x-1|+_sB,x+_lC|,_lB|||\?B

B=@ `+B          Prepend a string to B$. Thisis a hack to avoid errors with
                 removing substrings stating at index 1
┘                Line-break in QBasic output
       (;,;)     Read the string (B$) and the to-be-removed substring (C$)
x=instr          And make x to be the starting index of the first C$ in B$
~x|              IF X <> 0 (ie C$ is present in B$)
?                PRINT
 _t                trimmed version (drops the prepended space)
  _sB,x-1|+        of a substring from 1 to x (the start of C$) -1
  _sB,x+_lC|,_lB   and the rest of the string, starting after C$
                     _l takes the length of a string
  |||              End TRIM, end Substring, end Length
\?B              When missing C$, just print B$

I initially misread the instructions.  Thanks, Ørjan Johansen for pointing out my mistake!
PowerShell, 46 51 bytes
Function F($o,$a){([regex]"^$a").replace($o,'',1);}

Try it online!

This fails on the 'abcde' 'bcd' case.

I'm seeing expected results from that test case -- TIO here

It's a listed test case of the OP and the result should be abcde - bcd does not occur at either end of the string.

You are correct.  I misread the instructions.  Thanks for pointing it out!

Lua, 71 65 bytes
Accepting suggestions
a,b=...p='(.*)'print(a:match('^'..b..p)or a:match(p..b..'$')or a)

Try it online!

Excel, 129 bytes
=IFERROR(IF(FIND(B1,A1)=1,SUBSTITUTE(A1,B1,"",1),IF(FIND(B1,A1,LEN(A1)-LEN(B1))>LEN(A1)-LEN(B1),LEFT(A1,LEN(A1)-LEN(B1)),A1)),A1)

sed, 56 53 bytes
s/^(.*),(.*)\1$/\2/
s/^(.*),\1(.*)$/\2/
s/.*,(.*)/\1/

Try it online!

Pip, 19 bytes
Y'^.X:baRyNa?yb.'$x

Try it online!
Kinda sad this isn't shorter. The main problem is that Pip's R operator replaces all matches, not just the first one; otherwise, aR"^|$"J Xbx would work for 12 bytes.
                     a, b are command-line args; x is empty string (implicit)
    X:b              Convert b to a regex in-place
 '^.                 Prepend ^
Y                    and yank that regex into the y variable
       aR         x  In a, replace the following expression with the empty string:
         yNa?         Is there a match of y in a? I.e., does b match at the beginning of a?
             y        If so, replace y (b at the beginning of a)
              b.'$    If not, replace b with $ appended (b at the end of a)

Kotlin, 62 42 56 bytes
+12 bytes I think that type definitions are mandatory in the Kotlin lambda with 2 arguments
{a:String,b:String->Regex("^$b|$b$").replaceFirst(a,"")}

Test script:
var f = {a:String,b:String->Regex("^$b|$b$").replaceFirst(a,"")}

fun main(args: Array<String>) {
    println(f("abcde","ab"))
    println(f("abcab","ab"))
    println(f("abcde","bcd"))
}

Output:
cde
cab
abcde

Kotlin (without Regex), 62 76 bytes
{a:String,b:String->var c=a.removePrefix(b)
if(a==c){c=a.removeSuffix(b)}
c}