text:
Generalized Gray codes
Input: An array I of k positive integers. The integers will be no larger than 100 and k ≤ 100.
Output: Your code must output all possible arrays O of non-negative integers  of length k with the restriction that 0 ≤ Oi ≤ Ii. To get from one array to the next you may  add or subtract 1 to one value in the array.  Your code must not output the same array twice.  If the number of different arrays to be output is very large, your code should just carry on outputting forever until it is killed.
Examples

If I is an array of k ones then this is exactly the problem of iterating over all Gray codes of bit width k, except that the first and the last element do not need to be reachable in one step.
If I = [2,1] then one possible ordering of the output arrays is (0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
If I = [2,1,3] then one possible ordering of the output arrays is (0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),....

This is a code-golf challenge, the submission with the source code with the shortest length wins. Don't let the short answers in golfing languages discourage you from posting an answer in other languages. Try to come up with the shortest answer in any language.
This is also a restricted-complexity challenge. Every new array should be output with O(k) time elapsing since the previous outputted array (or the start of the program for the first array outputted). This means that the running time per new output array (they are each of length k) should be no greater than O(k). That is it should take time proportion to k and not, for example k2 or 2k.  Note this is not the average time per output but the worst case time for each and every array outputted.
You can assume that all arithmetic on 64 bit integers can be performed in constant time as can reading and outputting them as well as assignment and looking up and changing values in arrays.
One consequence of the restricted-complexity is that solutions that only output at program exit are not acceptable.

(should "add or subtract 1" performed modulo I_i+1? Can you reach 0 from I_i?)

@user202720 No I didn't intend that.

How do the complexity work when n and k are limited? assuming they go to infinity with bit width how to go

@l4m2 For the purposes of the complexity analysis assume k goes to infinity.

@Anush so how do bit width go?

Python 3, 116 bytes
def f(a):
 l=len(a);t=[0]*l;d=[1]*l
 while 1:
  i=0;yield t
  while not-1<t[i]+d[i]<=a[i]:d[i]*=-1;i+=1
  t[i]+=d[i]

Try it online!
Thanks Mnemonic for -1 byte.
Generator function. (thanks Dennis for reminding me, I forgot the feature exists) If the output should be printed to stdout then use print(t,flush=1) for 9 additional bytes, or if Python is called with -u, print(t) suffices for +1 bytes.
Stops with an error (IndexError). If you want to call this function and then continue the program, you have to catch it.

How long does the inner while loop run for?

@Anush At most k steps, because at each step i increases by 1 and after k steps i==k and d[i] causes an error.

This is a very nice solution.

You can save a byte by replacing not 0<= with not-1<.

Could you use yield t instead of print(t,flush=1)?

You can save 3 bytes by switching to Python 2 and using tabs instead of 2 spaces.

@Mnemonic I don't like Python 2.

Stax, 22 bytes
▒)∙ñ╚▀NK♀F☺S(A#P`░]╪Db

Run and debug it
Here's a big one to show the asymptotic behavior  Press run.
Unpacked, ungolfed, and commented, it looks like this.
,           pop from input to main stack
W           run the rest of the program repeatedly until explicitly cancelled
  cJP       copy top of stack and print, delimited by spaces
            get the index to mutate
  i^            iteration index + 1
  x{^|%}I       repeatedly apply divmod using l[k]+1 from input
                get the index of the first value that returns modulus >0
  cU=C      if the result is -1 (no match), then terminate the program
            get the direction to mutate
  s             get the "div" part of the last div operation called "d"
  ^|1           -1 ^ (d+1)
  ~{+}&     increment element in array at the index by the calculated amount

Run this one

Measuring in bit complexity, iteration index is O(k) bits, so division k times may take O(k²) time...

Kotlin, 181 178 bytes
Thanks to:
Anush pointed out I misunderstood the challenge saving 2 bytes.
ovs pointed out a 1 byte savings.
val p={a:List<Int>->var l=a.size
val v=Array(l,{0})
val i=Array(l,{1})
l-=1
o@while(0<1){println(v)
var p=l
while(v[p]+i[p]!in 0..a[p]){i[p]*=-1
p-=1
if(p<0)break@o}
v[p]+=i[p]}}

Try it online!

For the example in the question with 2 1 3 your code needs 3 2 4 as input it seems.

while(true) can be while(1<2)

JavaScript (Node.js), 114 bytes
a=>{b=a.map(_=>0);c=a.map(_=>1);for(i=0;a[i];b[i]+=c[i]||-1){console.log(b);for(i=0;b[i]==a[i]*c[i];i++)c[i]^=1;}}

Try it online! Ungolfed:
function ggray(maxima) {
    var current = Array(maxima.length).fill(0);
    var flag = Array(maxima.length).fill(1);
    for (;;) {
        console.log(current);
        for (var i = 0; ; i++) {
            if (i == maxima.length) return;
            if (current[i] != maxima[i] * flag[i]) break;
            flag[i] = 1 - flag[i];
        }
        if (flag[i]) current[i]++;
        else current[i]--;
    }
}


text:
Golf a bit-reversal table
The Premise:
You are writing a C driver for a screen for use on an embedded system. The screen uses a tortured version of SPI that requires data to be sent LSb (least-significant-bit) first, but MSB (most-significant-byte) first.
A fast way to do this (if you have the memory) is to use the integer value of each byte to index an array that returns the bit-reversed counterpart, but writing that out by hand is a pain, so...
The Challenge:
Write the shortest program possible to output this array:
[
    0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
    0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
    0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
    0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
    0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
    0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
    0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
    0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
    0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
    0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
    0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
    0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
    0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
    0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
    0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
    0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
]

The output can be an actual array or a string that looks like an array. Pretty formatting is optional as long as you can copy and paste it into your driver and use it as-is.
The pretty array above was generated by this python 3 code (112 bytes):
print('['+', '.join([(''if i%16else'\n\t')+'%#04x'%int(bin(i)[:1:-1].ljust(8,'0'),2)for i in range(256)])+'\n]')

This is a specialisation of an earlier question which just fixes its input, and that qualifies as a trivial variant for the purposes of considering it a duplicate.

(unrelated to the challenge) There are other fast ways here too, not counting C macro hacks.

Also, we have a sandbox for proposed challenge, which can be used to remove challenge issues before posting, including duplicates.

And BTW: welcome to PPCG! This is a well written first challenge, but the (probably) optimal method was indeed already used in the other challenge.

source: Stack Exchange

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

sort: votes


text:
Golfing out the haters
The setup:
A social network reports the number of votes a post has in two ways: the number of net upvotes (total upvotes - total downvotes), and the % of votes that were upvotes, rounded to the nearest integer (.5 rounds up).  The number of net upvotes is an integer (not necessarily positive), and the second is guaranteed to be an integer between 0 and +100 inclusive.  The number of upvotes and the number of downvotes are both either zero or positive 32-bit integers (you can specify signed or unsigned).  Assume that if there are zero total votes, the percentage upvoted is reported as zero.
The challenge:
Given these two integers (net upvotes and % upvoted), what is the shortest program you can write which determines the lowest number of total upvotes the post received, with all the constraints above satisfied?
Input constraints are guaranteed. If the input does not satisfy the constraints above, the program behavior is up to you. Bonus kudos if it doesn't enter an infinite loop or otherwise crash. Consider returning a negative number if you want more guidance.
General rules:

This is code-golf, so the shortest valid solution (measured in bytes) wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.  Bonus kudos for a client-side Web language like Javascript.
If you have interesting solutions in multiple languages, post them separately.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, or full programs. Your call.
Default loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation of how the code works.
Keep in mind that if you are doing an integer division operation that truncates (e.g. 20/3=6) rather than rounds, that might not be fully correct.
Additional test cases that explore the edge cases in the above constraints are welcome.
While the expected return type is numeric, boolean "false" can be used in place of 0.

Example test cases:
The first column is just a reference number included to facilitate discussion.
ref net  %up    answer
1   0    0   => 0
2   -5   0   => 0
3   -4   17  => 1
4   -3   29  => 2
5   -2   38  => 3
6   -1   44  => 4
7   0    50  => 1
8   5    100 => 5
9   4    83  => 5
10  3    71  => 5
11  2    63  => 5
12  1    56  => 5
13  1234 100 => 1234
14  800  90  => 894  (tip: don't refer to this as the "last test case;" others may be added.)

That zero total vote special case is pretty finicky. If there's an equal number of upvotes and downvotes, the percentage upvotes is 50%, except it's 0% when there's no votes, breaking the upvote-downvote symmetry.

@xnor 0/0 is generally undefined, so an assumption must be made.  With this choice, you get an automatic "answer = second input" if the second input is 0, and an automatic "answer = first input" if the second input is 100.

Suggested test case borrowed from @nwellnhof: 1000, 100. Can you confirm that the expected answer is 1000?

Downvoted, because haters gotta hate :)

@Arnauld and nwellnhof: as noted in the comment just before yours, if the second input = 100, the answer = first input.  If the 100 was really a rounded slightly lower percent, more than the first input # of upvotes would be required to get net votes = first input, and this challenge seeks the lowest number of total upvotes.

JavaScript (ES6), 47 bytes
Takes input in currying syntax (n)(p), where n is the number of net upvotes and p is the percentage of upvotes. May return false for 0.
n=>p=>(g=u=>u/(u-n/2)*50+.5^p?g(u+1):u)(n>0&&n)

Try it online!
Commented
n => p => (          // given n and p
  g = u =>           // g = recursive function taking u = number of upvotes
    u / (u - n / 2)  //   compute u / (total_votes / 2)
    * 50 + .5        //   turn it into a percentage, add 1/2
    ^ p ?            //   XOR it with p, which gives 0 if the integer parts are matching
                     //   if the result is not equal to 0:
      g(u + 1)       //     try again with u + 1
    :                //   else:
      u              //     stop recursion and return u
)(n > 0 && n)        // initial call to g() with u = max(0, n)

Edge cases
Let Fn(u) = u / (u - n / 2) * 50 + 0.5

If u = 0 and n = 0, then Fn(u) = NaN and Fn(u) XOR p = p. So, we return u = 0 if n = p = 0 (first iteration of the first test case) or continue with the recursion if p != 0 (first iteration of the 7th test case).
If u > 0 and u = n / 2, then Fn(u) = +Infinity and -- again -- Fn(u) XOR p = p. Unless p = 0, we just go on with the next iteration. (This happens in the 9th and 11th test cases.)

Nice! You get bonus kudos for language choice, and for including an explanation + link to a live demo!

Stax, 17 bytes
ëI╩½• ╠☺Vì∞«S↑♠αS

Run and debug it
This is brute force.  It starts with 0 for candidate upvotes, and increments until it satisfies the formula.
Unpacked, ungolfed, and commented, it looks like this.
0       push zero
{       start filter block...
        candidate upvotes is on the stack
  cHx-  calculate candidate downvotes for denominator (upvotes * 2 - net)
  c1?   if denominator is zero, replace it with 1
  :_    floating point division
  AJ*   multiply by 100
  j     round to integer
  ;=    is equal to second input?
        increment until a match is found
}gs

Run this one

Clean, 114 107 104 bytes
import StdEnv
? =toReal o toInt
$a d#e= ?d
= ?a+until(\c#b= ~c*e/(e-100.0)
= ?(?100*b/(?b+c))==e)inc 0.0

Try it online!
Defines the function $ :: Int Int -> Real, where the arguments are signed integers and the return value is a double-precision float exactly representable by a 32-bit signed integer.
It checks every value of c in the equation b=-cd/(d+1) to find a b satisfying a+c=b and b/(b+c)=d, since the smallest c results in the smallest b, take the first element of the set of all solutions.

05AB1E, 13 bytes [mildly broken]
*²·т-/ò²т;Qi1

Try it online!
Explanation:
To solve this, I assumed inputs a, b and expected result x.
Given the info in the setup, that gave me the equation:
 2x         100x
———— - a = ——————
 a           b

Rearranging for x gives
        ab
x = ——————————
     2b - 100

The only test case this doesn't work for is 0, 50 - I simply hardcoded to check for this.
*²·т-/ò²т;Qi1     Implicit Inputs: a, b              STACK (bottom to top)
*                 Multiply the inputs together       [ab]
 ²·               Take the second input * 2          [ab, 2b]
   т-             Subtract 100                       [ab, 2b - 100]
     /ò           Divide and round                   [round(ab/(2b-100))]
       ²т;Qi1     If 2nd input = 50, push 1 to stack
                  { Implicitly output top item of stack [either 1, or round(...)] }

This doesn't work correctly for some inputs.  90% with 800 net votes can be done with 894 up votes.

@recursive I know what it is. It assumes 90% exactly, not 89.5%.

Well, closer to 90.5% in this case but yes.

Now I realise it's trickier than I thought. I'll think about it, but for now I'll mark it as broken.

@GenoRacklinAsher Now I realise it's trickier than I thought. I'll think about it... Those are the kinds of comments I like to read, seeing them as the hallmark of a good puzzle :-).

Go 1.10, 154 bytes
func h(n,u float64)float64{if u==50{return 1};r:=Round(n*u/(2*u-100));s:=Round(n*(u+.5)/(2*u-99));v:=s/(2*s-n);if v>1||Round(v*100)!=u{return r};return s}

Try it on Go Playground! (TIO runs Go 1.9, which doesn't have math.Round)
Ungolfed version
func haters(n, u float64) float64 {
    if u == 50 {
        return 1
    }
    r := Round(n * u / (2*u - 100))
    //Test the case where we were given a percentage that was rounded down (e.g. 90.4% given as 90%)
    //We test this by adding 0.5% to u. The denominator is just a simplified form of 2*(u+0.5) - 100
    s := Round(n * (u + .5) / (2*u - 99))
    //Check if s is a valid result
    v := s / (2*s - n)
    if v > 1 || Round(v*100) != u {
        return r
    }
    //s is strictly less than r, so we don't need to check the minimum.
    return s
}

In the interests of adding an explanation, the above formula for r can be derived by simultaneously solving n=v-d and u = 100 * v/(v + d) for v, where v and d are the number of upvotes and downvotes respectively. The derived formula is undefined for v = 50, so we have to handle that case (which we do with the first if statement).

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


text:
split and capitalize
Challenge :
Given a string split at specific positions and capitalize the first character of the given word. Capitalize the first word's first char if and only if it was already capitalized
Input :
A string s and a character c.
Ouput :
The string with each occurrence of c replaced with the first char capitalized
Examples :
STRING(s)             CHARACTER(c)  RESULT
Hello_world           _             HelloWorld
me,no,like            ,             meNoLike
you-got-it            -             youGotIt
Am^I^clear            ^             AmIClear
go!full!caps          !             goFullCaps
weird&but&tRue        &             weirdButTRue
ProbleM1fixed1no      1             ProbleMFixedNo
!prob!!lem!s!Olved!!  !             ProbLemSOlved

Note :

Given input will always be valid. i.e : The first will always be a string with at least one instance of the character to replace at. The second will always will be a single character.
The length of the input string will be greater 4.
There will be at least one occurrence of the character to split at.
The input is guaranteed to contain only letters and the separator (Thanks @Arnauld)
Separator is anything that is not an alphabet (a-z / A-Z) (suggested by @Dennis)

Winning criteria :
This is code-golf so shortest code in bytes for each language wins.

Thanks to @JonathanAllan for pointing out two mistakes.

Tips when creating test cases: Make each one cover at least one corner case. All your test cases are basically identical (maybe except the one with 1). Try to think about how solutions might fail, and make a test case for such situations. Some examples: Letters as separators, the separator being the last character, consecutive separators and so on. There's no need to have many test cases that doesn't test different things.

You're missing a delimiter in the last test case - there should be a ! there. I would edit it myself, but there's not enough characters for me to do it.

Can it be 123 | 2 => 13?

@l4m2 : If it helps you Yes otherwise general rule so far is that the test case will have at least one alphabet

I've downvoted this due to the multiple changes to the spec. On a sidenote, you need to make mention a lot sooner than the last test case that the string may contain 2 or more consecutive "separators" and that we are not guaranteed that a letter will always follow a "separator".

@Shaggy : I can't stop you from down-voting so :( . Also The test case was suggested by Dennis and frankly I don't see a problem with where it is. You are supposed to read the test case. Tell me if there is a problem and then it can be changed.

Not that it matters, but I didn't suggest any test cases.

@Dennis : I'm pretty sure it was you , if not then StewieGriffin ? I don't know, you removed all comments

I looked it up: Stewie didn't suggest any test cases, but he asked whether the first or last character could be a separator and whether there could be consecutive separators. In the future, please consider using the sandbox to get all these details sorted out before going live. It's frustrating to get your answer invalidated because of changes in the specification. The most surprising of all is the restriction to take the character as input, even if the program doesn't need it. That makes no sense at all.

@Dennis : I didn't add that and didn't intend to. See the Scala answer for clarification on that. (If you think it is not required I could removed it) but i'm guessing that's gonna get me more down-votes

Yes, I've seen the Scala answer. If an answer surprises you by not requiring one of the inputs, just let it be, don't add extra rules to the challenge to invalidate the answer. (That's my opinion, not a rule.) Improving your challenge by removing a superfluous restriction shouldn't earn you any downvotes. I'm sure the affected answerers would be happy to save a few bytes.

@Dennis : So I should change this ?

I think so, yes.

@Dennis : Okat done.

@Dennis : I updated the description just for you :)

Can we have a test-case with separator ., I can imagine some string splitting functions struggling with that one.

Python 3, 63 bytes
lambda s,c:''.join(map(min,s,s[0]+s.title()[1:])).replace(c,'')

Try it online!

JavaScript (ES6), 58 56 bytes
Saved 2 bytes thanks to @l4m2 / @Downgoat
Takes input in currying syntax (s)(c).
s=>c=>s.replace(u=/./g,x=>u=x==c?'':u?x:x.toUpperCase())

Try it online!
Commented
s => c =>                  // given s and c
  s.replace(u = /./g, x => // initialize u to a RegExp; replace each character x in s with,
    u =                    // and update u to:
      x == c ?             //   if x is the separator:
        ''                 //     an empty string
      :                    //   else:
        u ?                //     if u is not an empty string:
          x                //       x unchanged
        :                  //     else:
          x.toUpperCase()  //       x capitalized
  )                        // end of replace()

consolation 56 bytes for s=>c=>s.replace(RegExp(c+".","g"),m=>m[1].toUpperCase()), since it doesn't work for special regex characters

50 bytes. Or 47 if you don't bother taking the second input, which is irrelevant.

@Shaggy Thanks! I've added it as a separate version, since the new rules are quite different from the original ones.

fail !prob!!lem!s!Olved!!

@l4m2, that's a new test case which changes the spec yet again. A + before the . in the RegEx will get around it.

@Shaggy By adding a +, we're not going to capitalize the right character anymore. (This works but is only 1 byte shorter than the original version.)

well i saw it's added after the comment

s=>c=>s.replace(u=/./g,x=>u=x==c?'':u?x:x.toUpperCase())?

Your explanation says u < 1?a:b checks for empty string so why not just do u?b:a

@Downgoat D'oh. This may have been derived from an earlier version where it really was needed. Or (more probably), I'm just stupid. :) Thanks!

@l4m2 Indeed. (Sorry, I missed your comment.)

C (gcc), 61 53 55 bytes
-8 bytes thanks to Dennis!
f(s,c)char*s;{for(;*s;putchar(*s++))if(*s==c)*++s&=95;}

Try it online!

Suggest *s==c?*++s&=95:0; instead of if(*s==c)*++s&=95;

sed 4.2.2 (-r), 21
s/[^a-z]+(.)?/\u\1/gi

I tried \W instead of [^a-z], but unfortunately that doesn't match _.
Try it online!

By our new standards, each invocation of a flags is considered a different language, and thus your answer can be changed to sed 4.2.2 (-r), 21 bytes.

@Mr.Xcoder Sounds good - thanks!

APL (Dyalog Classic), 22 bytes
{⍵~⍨1(819⌶@(⍵=¯1⌽⊢))⍺}

Try it online!

Why Dyalog Classic for this answer?

at the time, unicode dyalog answers were required to link to a single-byte encoding (or else scoring would default to utf8), so it was easier to post in classic dyalog

Perl 6 -p, 19 bytes
s:g[<:!L>(.)]=$0.uc

Try it online!

Jelly, 8 bytes
Œt⁸1¦«⁸ḟ

Try it online!
How it works
Œt⁸1¦«⁸ḟ  Main link. Left argument: s (string). Right argument: c (character).

Œt        Title case; capitalize the first character of each word.
  ⁸1¦     Replace the first character of the result with the first character of s.
     «⁸   Take the character-wise minimum of the result and s.
          Note that uppercase letters have lower code points than lowercase ones.
       ḟ  Filterfalse; remove all occurrences of c.

Octave, 83, 66, 64 bytes
Saved 2 bytes thanks to Luis Mendo. upper instead of toupper.
@(s,c,k=upper(s(i=find(s==c)+1)))[strsplit({s(i)=k,s}{2},c){:}];

Try it online!
Wow, that's probably the messiest piece of Octave-code I've ever written! This uses two of the tricks posted in this tips question, namely Argument list, and cell arrays.
Explanation:
Argument list input:
@(s,c,k        % An anonymous function that may take three input variables, s, c, k
               % where the third argument has the default value:
 k=upper(s(i=find(s==c)+1))

k is here the first character in s after each separator c, converted to upper case. The index of each capitalized character is stored in i.
Cell array body:
We create a cell array with two elements, one were we say that all i'th characters should be substituted by its counterpart in k, and the other one with s, that is now already updated. We index this using {2} so that we only get the whole, modified string back. This is fed to strsplit, which splits it into cells at the separator character. We convert it to a comma-separated list using {:}, and concatenates it back to a string using square brackets [].
Apologies if that didn't make any sense to you... It barely makes sense to me :P

Retina 0.8.2, 20 bytes
T`lLp`LL_`[\W\d_]+.?

Try it online! Takes the string only, separator optional. All non-alphabetic characters are deleted but any following alphabetic character is uppercased. Previous 34-byte version accepted arbitrary input:
T`l`L`(?=.*(.)$)\1+.
(?=.*(.)$)\1

Try it online! Link includes test suite. Assumes the input consists of the string and character concatenated together. Explanation: The first stage transliterates all characters immediately following occurrences of the end character from lower to upper case and the second stage then deletes all occurrences of the end character.
For both solutions, using a right-to-left match instead of a + also works.

Since the input is guaranteed to only contain alphabetic characters and the separator, you can use [^a-z] instead of the lookaheads Try it online!

Scala, 83 bytes
def f(s:String)={val w=s.split("[^a-zA-Z]");w(0)+w.tail.map(_.capitalize).mkString}

Try it online!
Explanation:
def f(s: String) = {                        // takes a String "s" as input
  val w = s.split("[^a-zA-Z]");             // split on non-alpha chars
  w(0) + w.tail.map(_.capitalize).mkString  // upper case first letter of all words except first one and join array into a String
}                                           //

V, 6 7 bytes
1 byte saved by not using argument
ÓÁˆ/õ±

Try it online!
The program takes in the text as input and the char as an argument.
Hexdump:
00000000: d3c1 882f f5b1                           .../..

This is a simple substitution. Uncompressed, it looks like the following
:s/\A(.)/\u\1/g

Perform a global substitution in which \A, a non-alphabetic character, followed by a character (.) is replaced with uppercased \u first capture group \1

Doesn't work for input where c is a special regex character

@ConorO'Brien Fixed, and thanks to this I found a shorter solution :D

Röda, 57 54 bytes
-3 bytes thanks to Cows quack
{(_/`\Q$_`)|{pull;[upperCase(_[:1]),_1[1:]]if[#_1>0]}}

Try it online!
Explanation:
{
  (_/`\Q$_`)| /* Pull two strings and split the first with the second */
  {
    pull;                /* Pull one string and print it */
                         /* For each string _1 in the stream: */
                         /*   If _1 is not empty: */
    [                    /*     Print: */
      upperCase(_[:1]),  /*       The first character capitalized */
      _1[1:]             /*       The rest of characters */
    ]if[#_1>0]           /*   End if */
  }
}

You can leave out the \E from the regex, and _[0:1] → _[:1]

Red, 87 bytes
func[s c][b: split s c prin b/1 foreach w next b[if w <>""[w/1: uppercase w/1 prin w]]]

Try it online!

05AB1E, 9 bytes
¡ćsvyćusJ

Try it online!
Explanation
¡           # split the string on the char
 ć          # extract the head of the resulting list
  s         # swap the head to the bottom of the stack
   vy       # for each string y in the rest of the list
     ću     # extract the head and capitalize it
       s    # swap it below the rest of the string
        J   # join everything to one string

PHP, 91 83 bytes
$a=explode($argv[2],$argv[1]);echo array_shift($a);foreach($a as$i)echo ucfirst($i);

Run with -r. Was 2 bytes shorter using split instead of explode, but ^ test fails due to regex.
-8 thanks to Med

You can remove {and } from the for loop, it will only treat the next statement as body of the condition.

You can even do the echo inside the loop:
$a=explode($argv[2],$argv[1]);echo array_shift($a);foreach($a as$i)echo ucfirst($i);

R, 64 bytes
Pure regular expression solution using https://www.regular-expressions.info/replacecase.html. Unfortunately separators can be underscores so I couldn't use \w to capture letters. Improved version taking advantage of gsub's ignore.case parameter to save on [a-zA-Z]. Correction thanks to https://codegolf.stackexchange.com/users/95126/dominic-van-essen, who has a 25% shorter solution in the comments.
function(s,c)gsub('[^a-z]([a-z]?)([a-z]*)','\\U\\1\\E\\2',s,T,T)

Try it online!
https://codegolf.stackexchange.com/users/95126/dominic-van-essen 's solution, with an extra character removed (by using ? for optional):
R, 47 bytes
function(s,c)gsub("[^a-z]+(.)?","\\U\\1",s,T,T)

Try it online!

Your TIO link shows that this doesn't work for the last test case...

...but you can fix it for 48 bytes...

...or (actually using the argument c) for 57 bytes...

Would you like to add your (growing number of) R golfs to the Language of the month page (edit the first 'answer' there...).  It's nice for other R-golfers (and would-be-R-golfers) to be able to easily find examples to learn from...

Thanks for the correction @DominicvanEssen, much better than mine! I'm amused that not using the argument is still better!

Me too, and based on the 'Scala' answer that the OP mentions, it seems that you don't even need to accept c as a function argument...

Well done on shaving another byte off my attempt!  By the way, if you're embedding links, you can make your text more readable by using a link-label in square-brackets [ ] immediately followed by the link itself in parentheses ( ).

LaTeX, 97 bytes
The function
\def~#1#2{{\seq_set_split:Nnn~{#2}{#1}\seq_map_function:NN~"}}\def"{\let"\text_titlecase_first:n}

Complete document with test cases
\documentclass[preview,border=3.14]{standalone}

\ExplSyntaxOn
\catcode`\~13
\catcode`\"13

\def~#1#2{{\seq_set_split:Nnn~{#2}{#1}\seq_map_function:NN~"}}\def"{\let"\text_titlecase_first:n}

\ExplSyntaxOff

\begin{document}
~{Hello_world}_

~{me,no,like},

~{you-got-it}-

~{Am^I^clear}^

~{go!full!caps}!

~{weird&but&tRue}&

~{ProbleM1fixed1no}1

~{!prob!!lem!s!Olved!!}!
\end{document}

Results (in PDF)

Pinecone, 314 bytes
s:String.input;p:String.input;k:IntArray:s.len;k.set:0,-1;o:"";n:1;i:0|i<s.len|i:i+1@((s.sub:i,i+1)=p?(k.set:n,i;n:n+1))k.set:n,s.len;i:1|i<n+1|i:i+1@(x:k.get:i-1;y:k.get:i;x:x+1;j:s.sub:x,y;e:1|e<256|e:e+1@((j.sub:0,1)=e.ascii?(e<96?(o:o+(e.ascii)+(j.sub:1,(j.len)))|(o:o+(e-32).ascii+(j.sub:1,(j.len))))))print:o

This was extremely fun....

Vyxal, 5 bytes
/ḣǐJṅ

Try it Online!

Use the s flag for 4 bytes

R, 87 bytes
g<-function(s,x,z=strsplit(s,x,T)[[1]])cat(z[1],capwords(z[-1]),sep="")
example(chartr)

Try it online!
Uses this trick can can not be properly executed in TIO so I simulated it.
We need the T otherwise one of the test cases fails.

Groovy, 43 bytes, 45 bytes
s.replaceAll(/\$c(.)/){it[1].toUpperCase()}

Try it online. Test suite included excluding the last item as it lacks the separator char c.

Go, 138 92 87 bytes
Dropped 46 bytes thanks to @Dennis' title case idea.
func f(s,d string){p:=Split(s,d);Print(p[0]+Replace(Title(Join(p[1:]," "))," ","",-1))}

Try it online!

Husk, 10 bytes
ΣΓ·:mΓo:ax

Try it online!
Explanation
ΣΓ·:mΓ(:a)x  -- example inputs: 'x' "abxbcxcdxdex"
          x  -- split on character: ["ab","bc","cd","de"]
 Γ           -- pattern match (x = head) (xs = tail) and do..
  ·:         -- | construct list (x:xs) but with the second argument do..
    m        -- | | map (eg. "bc")
     Γ(  )   -- | | | pattern match on first character
      ( a)   -- | | | | upper-case it
      (: )   -- | | | | and join again
             -- | | | : "Bc"
             -- | | : ["Bc","Cd","De"]
             -- : ["ab","Bc","Cd","De"]
Σ            -- concatenate: "abBcCdDe"

F# (Mono), 122 bytes
let f(s:string)c=s|>Seq.mapi(fun i x->if i>0&&s.[i-1]=c then Char.ToUpper(x)else x)|>Seq.where((<>)c)|>Seq.toArray|>String

Try it online!

Java 10, 141 bytes
s->c->{var r=s.split("\\"+c);var r=a[0],t;for(int i=0;++i<a.length;r+=t.isEmpty()?"":(char)(t.charAt(0)&~32)+t.substring(1))t=a[i];return r;}

Try it online.
Explanation:
s->c->{                    // Method with String and character parameters and String return-type
  var r=s.split("\\"+c);   //  Split String by character (with potential regex char)
  var r=a[0],              //  Result-String, starting at the first item
      t;                   //  Temp-String to reduce bytes
  for(int i=0;++i<a.length;//  Loop in the range [1, length_of_array)
      r+=                  //    After every iteration: append the result-String with:
         t.isEmpty()?      //     If the current item empty:
          ""               //      Append nothing
         :                 //     Else:
          (char)(t.charAt(0)&~32)
                           //      Capitalize the first character
          +t.substring(1)) //     And append the other characters as is
    t=a[i];                //   Set `t` to the current String-item of the array
  return r;}               //  Return the result-String

Stax, 11 bytes
óKo{cplòüö\

Run and debug it
Explanation
/BsF1:/s^s|dl                 # Full Program, unpacked, Implicit Input
/                             # Split on substrings (Split input with symbol to split on)
 B                            # Remove first element from array. Push the tail of the array, then the removed element.
  s                           # Swap first two elements of stack
   F                          # Start for loop
    1:/                       # Split array at index; push both parts.
       s^s                    # Swap first two elements of stack, capitalize character, swap first two elements
         |dl                  # Get length of stack, listify that amount (entire stack), implicit output of array

There's a few parts I would really like to fix somehow. I can get it down to about 8 bytes, but it fails on the last test case >.<

Ruby -pl, 36 bytes
$_.gsub!(/[^a-z]+(.|$)/i){$1.upcase}

Try it online!
Takes only the string without second argument. Uses the block version of gsub! method because with common gsub! x,y syntax $1 is not readily filled with match data. |$ in regex is necessary for the test case with separator in the end.

Python 3, 77 bytes
o=[]
for x in s.split(c): o.append(chr(ord(x[0])-32)+x[1:])
print(''.join(o))

Try it online!
This assumes that the string is ASCII encoded and assumes that s and c are preloaded variables containing the input.
for x in s.split(x)       #loop through items in the string s split by x
    o.append(             #add the following to c
        chr(              #turn the following number into a character
            ord(          #turn the following character into a number
                x[0]      #the first character in string x
            )-32          #subtract 32 from this number
        +x[1:]            #add everything past and including the second character in string x

This solution works on the fact that in ASCII encoding, lowercase letters are positioned 32 entries after capitalised letters
Edit: i just realised that this also capitalises the first character in the string, which it shouldn't. but i'm quite proud of my nonsense, so i'll leave this up if that's allowed

What is s supposed to be ?

@MuhammadSalman A string s and a character c.

Lovely, make it work, Go here and see if it works or not : TIO. When it does tell me ?

oops! i just realised i made a mistake when changing the variable names, c=[] is supposed to be any other variable

@MuhammadSalman here

Edited to add the specification, and a TIO link

Pip, 23 bytes
Ya^by@0AL(UC@_.@>_M@>y)

might be shorter with regex substitution.
Try it online!

Rust, 130 125 bytes
|s,c|(|mut u|s.chars().flat_map(|x|if x==c{u=1;vec![]}else if u>0{u=0;x.to_uppercase().collect()}else{vec![x]}).collect())(0)

Try it online!
-5 bytes thanks to Aiden4
So Rust has no built-in support for regular expressions or title case, and the uppercase function can return multiple characters... On the plus side, this works for non-ASCII encodings :)

You can shave off 5 bytes if you use flat_map() instead of map().flatten()

Wolfram Language (Mathematica), 45 bytes
""<>MapAt[Capitalize,##~StringSplit~All,2;;]&

Try it online!


text:
prOGraMMIng PuZZleS & cOde ____
Input
A non-empty encoded string consisting of printable ASCII characters (in the range 32-126), where some missing letters have been replaced with _.
Output
A decoded string of the same length with all letters in lowercase, including the missing ones.
How?
Edit: As mentioned by @Deusovi in the comments, this is a variant of Bacon's cipher.

Gather all letters in the original string and group them by 5. Additional letters that do not fit in a full group of 5 are ignored.
Convert each group into binary: lowercase = 0, uppercase = 1. This leads to a list of integers.
Use each value N in this list to replace each _ in the original string with the N-th letter of the alphabet (0-indexed), in order of appearance.

Example: prOGraMMIng PuZZleS & cOde ____
prOGr --> 00110 -->  6 -->  7th letter = 'g'
aMMIn --> 01110 --> 14 --> 15th letter = 'o'
gPuZZ --> 01011 --> 11 --> 12th letter = 'l'
leScO --> 00101 -->  5 -->  6th letter = 'f'

By replacing the missing letters and converting everything back to lowercase, the original string is unveiled:
programming puzzles & code golf

This is the expected output.
Clarifications and rules

The missing letters are guaranteed to appear at the end of the string. More formally: there will never be any letter after the first _ in the input string. However, there may be other printable ASCII characters such as spaces and punctuation marks.
The input is guaranteed not to contain any useless capital letter: all capital letters are bits set to 1 which are required to decode the missing letters. Everything else is in lowercase.
The input string is guaranteed to be valid. Especially:

It will always contain enough full groups of 5 letters to decode the underscores.
The binary-encoded integers are guaranteed to be in the range [0-25].

There may be no _ at all in the input string, in which case you just have to return the input.
This is code-golf, so the shortest answer in bytes wins!

Test cases
Input : hello!
Output: hello!

Input : helLO, worl_!
Output: hello, world!

Input : i aM yoUr faTh__.
Output: i am your father.

Input : prOGraMMIng PuZZleS & cOde ____
Output: programming puzzles & code golf

Input : Can YOu gUesS tHE ENd oF This ____?
Output: can you guess the end of this text?

Input : THe qUICk brown FOx JUMps oVEr the la__ ___.
Output: the quick brown fox jumps over the lazy dog.

Input : RoadS? wHERe we're goinG WE doN't need _____.
Output: roads? where we're going we don't need roads.

Input : thE greatESt Trick thE DeVIl EVer PUllEd wAs CONvInciNg tHe WorLD h_ ____'_ _____.
Output: the greatest trick the devil ever pulled was convincing the world he didn't exist.

Some extra test-cases:
Input : BInar_
Output: binary

Input : 12 MonKey_
Output: 12 monkeys

Input : hyPerbolIZ__
Output: hyperbolized

Input : {[One Last Test ca__]}
Output: {[one last test case]}

Should we only consider as many groups of 5 as there are underscores in the input?

In that case, the rule when there's no _ in the input string is a bit of a special case.

Sorry, misunderstood your comment (and I think you misunderstood mine). My question is whether we should ignore extra groups of five if there are too few underscores, which seems apparent from the test cases.

Ooh, Bacon cipher!

@Deusovi Ah, I was pretty sure such a scheme would exist. Thanks for mentioning the right name. Related.

"There may be no _ at all in the input string, in which case you just have to return the input." - but do we have to lowercase it or not in this case?

@SztupY As The input is guaranteed not to contain any useless capital letter, in case there is no underscore there also won't be a capital letter.

missed that, thanks

Can input contain [] brackets (or some other char with ASCII code between Z and a) in the middle of the string? If so, probably worthy of another test case, as I just tried using [A-z] regex and only later realized it would fail on such scenario.

@KirillL. Yes, anything in [32-126]. I've added another test case.

AHK answer is needed

05AB1E, 18 bytes
Code:
áS.u5ôJC>.bv'_y.;l

Uses the 05AB1E encoding. Try it online!
Explanation:
á                       # Remove non-letters from the input string.
 S                      # Split the result into individual characters.
  .u                    # Check if is uppercase for each character.
    5ôJ                 # Split into binary numbers of length 5.
       C                # Convert from binary to decimal.
        >               # Add one.
         .b             # Map 1 → A, 2 → B, 3 → C, ..., 25 → Y, 26 → Z.
           v            # For each letter:
            '_y.;       #   Replace the first occurrence of '_' with the current letter.
                 l      #   Convert the string to lowercase.

Perl 5 -pF -MList::Util=sum, 75 bytes
@a=grep!/\W|\d/,@F;s!_!(a..z)[sum map{a gt shift@a&&16/2**$_}0..4]!eg;$_=lc

Try it online!
Explanation:

-pF reads a line of input into the variable $_ and, split into characters, into the array @F.
@a=grep!/\W|\d/,@F sets the array @a equal to those members of @F that don't satisfy the regex \W|\d. \W is anything but letters, numbers, and _; \d is numbers. So \W|\d is anything but letters and _, and @a has all the letters and _ characters. We will wind up never examining the _ characters in @a. (Note that this only works because the input is guaranteed ASCII.)
map{a gt shift@a&&16/2**$_}0..4 does the following for 0 through 4: It shifts the next element off of @a, shortening it, and evaluates whether a is asciibetically greater than that element (i.e. whether that element is uppercase). If so, && isn't short-circuited, so we get 16 divided by 2 to rhe power of the input value (0 through 4). Otherwise && is short-circuited and we get 0. map returns the list of five numbers to sum, which adds them.
That's the element we want from the list a..z, and that's what we get from (a..z)[…].
s!_!…!eg converts each _ in $_, in turn, to the appropriate letter.
$_=lc converts $_ to the lowercase version of itself, and -p prints it.

Python 2, 113 bytes
s=input()
i=k=0
for c in s:
 if c.isalpha():k+=k+(c<'a');i+=1;s=s.replace('_',chr(k%32+97),i%5<1)
print s.lower()

Try it online!

J, 62 61 bytes
tolower u:@]`(I.@t=.'_'=[)`[}+/@t$97+_5#.\3|0 2 4-.~'@Z`z'&I.

Try it online!

Nice answer.  3|0 2 4-.~'@Z`z'&I. is especially nice.

Retina, 91 90 bytes
T`l`a
T`L`A
[^Aa]

L`.{5}
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
^
$+¶
+`_(.*)¶a+(.)
$2$1
0G`
T`L`l

Try it online! Explanation:
T`l`a
T`L`A
[^Aa]

Translate lowercase letters to a and uppercase letters to A, deleting everything else.
L`.{5}

Split the Aas into groups of 5.
A
aA
+`Aa
aAA

Convert from binary into unary, treating A as 1 and a as 0. Since there were 5 Aas originally, there are 5 as left, plus a number of As depending on the desired position in the alphabet.
+T`_lA`l_`[^A]A

Increment the last a according to the number of following As.
^
$+¶

Prepend the original input.
+`_(.*)¶a+(.)
$2$1

Replace any _s with the next decoded letter.
0G`

Remove any spare decoded letters.
T`L`l

Lowercase everything.
Retina 0.8.2, 117 bytes
.+
$&¶$&
T`L`l`^.*
T`l`a`.*$
T`L`A
T`aAp`aA_`.*$
(.*¶)?.{5}
$&;
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
+`_(.*¶)a+(.);
$2$1
1G`

Try it online! Explanation:
.+
$&¶$&

Duplicate the input.
T`L`l`^.*

Lowercase the first copy.
T`l`a`.*$

Translate lowercase letters to a in the second copy.
T`L`A

Translate uppercase letters to A. These must be in the second copy because the first copy was already lowercased.
T`aAp`aA_`.*$

Delete everything else in the second copy.
(.*¶)?.{5}
$&;

Split the second copy (now just Aas) into groups of 5.
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
+`_(.*¶)a+(.);
$2$1
1G`

Decode the letters and insert them as before.

Scala, 189 bytes
def f(s:Array[Char])={var j=0;s.zipWithIndex.collect{case(95,i)=>s(i)=(Integer.parseInt(s.filter(_.isLetter)slice(j,j+5)map(k=>if(k<91)1 else 0)mkString,2)+97)toChar;j+=5};s.map(_.toLower)}

Try it online!
Explanation:
def f(s: Array[Char]) = {                // takes a String in input
  var j = 0                              // j stores at which block of 5 letters we're currently at
  s.zipWithIndex.collect {               // Array('h', 'e', ...) => Array(('h', 0) ('e', 1), ...) and we apply a collect transformation (filter/map)
    case (95, i) =>                      // we only handle cases where the char is '_' (95)
      s(i) = (                           // we modify the char at index i with the following
        Integer.parseInt(                // Integer.parseInt("00110", 2) = 6
          s                              //
            .filter(_.isLetter)          // filter out non letter chars (spaces, punct, figures, ...) from the input string (thanks @Arnauld for the fix)A
            .slice(j, j+5)               // "substring" the array to the block of 5 letters in question
            .map(                        // map on the current block of 5 letters
              k =>                       // the index of the next char in the block f 5 (e.g. 13)
                if (k < 91) 1 else 0     // if the current char is upper case (<91) then we replace it by a bit true, otherwise by a bit false
            )mkString,                   // Array(0, 1, 1, ...) => "011..."
          2                              // cast string to binary
        )                                //
        + 97                             // +97 to create a lower case char
      )toChar                            // cast from int to char
      j += 5                             // update the starting index of the next block of 5 letters
    }                                    //
  s.map(_.toLower)                       // return the updated seq of chars all in lower case
}                                        //

Jelly,  28 27  26 bytes
-1 thanks to Erik the Outgolfer & dylnan
Not a very Jelly-friendly challenge!
ḟŒs$Ƈ<”[s5Ḅ+97Ọż@ṣ”_$FṁLŒl

A monadic link accepting and returning lists of characters.
Try it online!
How?
ḟŒs$Ƈ<”[s5Ḅ+97Ọż@ṣ”_$FṁLŒl - Link: list of characters    e.g. "MfUNE_?"  (shorthand for ['M','f','U','N','E','_','?'])
    Ƈ                      - filter keep each if:
   $                       -   last two links as a monad:
 Œs                        -     swap-case
ḟ                          -     filter discard
                           - ...i.e. keep A-Z,a-z since they change when the case is swapped
                           -                                  "MfUNE"
      ”[                   - literal character                '['
     <                     - less than? (i.e. is upper-case?) [1,0,1,1,1]
        s5                 - split into fives                 [[1,0,1,1,1]]
          Ḅ                - from base two (vectorises)       [[23]]
           +97             - add (vectorises) ninety-seven    [[120]]
              Ọ            - from ordinals (vectorises)       [['x']]
                    $      - last two links as a monad:
                  ”_       -   literal character              '_'
                 ṣ         -   split at                       [['M','f','U','N','E'],['?']]
               ż@          - swapped @rgument zip             [[['M','f','U','N','E'],'x'],['?']]
                     F     - flatten                          "MfUNEx?"
                       L   - length (of input)                7
                      ṁ    - mould like                       "MfUNEx?"
                           - ...removes any excess characters
                        Œl - lower-case                       "mfunex?"

JavaScript (Node.js), 94 bytes
x=>x.toLowerCase(w=/[a-z]/gi).replace(/_/g,g=Z=>Z>62?(Z-52).toString(36):g(w.exec(x)<g|2*-~Z))

Try it online!
JavaScript (Node.js), 125 124 bytes
x=>x.replace(s=/./g,c=>parseInt(c,36)>9?c.toLowerCase(s+=+(c<{})):c=='_'?('0b'+s.slice(4,9)-~9).toString(36,s=s.slice(5)):c)

Try it online!

APL (Dyalog Unicode), 46 bytesSBCS
Anonymous lambda, Assumes ⎕IO (Index Origin) to be 0.
{_←'_'=⊢⋄819⌶A[2⊥⍉(+/_⍵)5⍴A∊⍨⍵∩A,819⌶A←⎕A]@_⍵}

Try it online!
{…⋄…} two-statement function; ⍵ is the argument, ⋄ separates statements
 ⊢ argument (no-op function)
 '_'= where equal to an underscore (i.e. a Boolean mapping function)
 _← assign that function to _
 A[…]@_⍵ put the following characters of A at positions of underscores in the argument
  ⎕A the uppercase Alphabet
  A← assign that to A
  819⌶ lowercase it (819 ≈ BIg, with no left argument means not big, i.e. lowercase)
  A, prepend the uppercase alphabet; this gives us all letters
  ⍵∩ intersection of the argument and that; just the letters of the argument
  A∊⍨ which of those are members of the uppercase alphabet; uppercase bits
  (…)5⍴ reshape that to the following number of rows, and five columns:
   _⍵ the mask of underscores in the argument
   +/ sum that; number of underscores
  ⍉ transpose (to treat each row as a number rather than as a bit position)
  2⊥ evaluate as base-2
 819⌶ lowercase everything

Jelly, 26 bytes
xn¥Œs<”[s5Ḅ‘ịØaṛi”_ḟ0Ɗ¦ƒŒl

Try it online!
Different approach from Jonathan Allan's. EDIT: So, I, uh, apparently thought of the same byte reduction as Jonathan Allan, so it doesn't hurt to mention his name again.

CJam, 43 bytes
q'_/_0={el_eu=!},_eu.=5/2fb65f+:c1$,(<.+:el

Try it online!

Clean, 180 ... 150 bytes
import StdEnv
?s=['a'+sum[i\\i<-:""&c<-s|c<'a']: ?(drop 5s)]
@['_':b][x:y]=[x: @b y]
@[a:b]z=[toLower a: @b z]
@e _=e
$s= @s(?(filter isAlpha s))

Try it online!
Defines the function $ :: [Char] -> [Char] with @ :: [Char] [Char] -> [Char] as a helper to replace underscores, and ? :: [Char] -> [Char] as a helper to generate the replacement characters.

How does the i<-:"" part work? Are chars implicitly converted to numbers when summing or adding them?

@Laikoni no, there's no implicit conversion. You can add and subtract Chars though.

C (gcc), 111 109 101 100 bytes
Edit: Added lowercasing per @FrownyFrog's comment; thanks to Lynn, Christoph and user5329483 for their suggestions!
f(s,t,i)char*s,*t;{for(t=s;t=strchr(t,95);*t=i+1)for(i=3;i<64;s++)isalpha(*s)?i=2*i|*s<97,*s|=32:0;}

Try it online!

You can save 2 bytes with i+=i+(*s<97).

You could abolish j by introducing a marker bit in i and rewriting the second for as for(i=1;i<32;s++). And compensate the extra 32 in the outer for. As a newbee here I count a seven byte spare.

Found another byte: for(i=3;i<96;s++) brings the 65 down to a single-digit number, aka 1.

Stax, 22 bytes
â╟▓ïMeee¶▐f◄┴≈┘n╛äyΩ○N

Run and debug it
The general approach is a regular expression replacement of "_" using a callback function that slices letters of the inputs to compute each replacement character.
v       convert to lower case
'_      "_" string literal
{       begin block for regex replacement
  yVl|& all the letters only from the original input
  5/    split into chunks of 5
  i@    keep the ith one, where i is the 0-based number of times this block has run
  {97<m map 5-letter chunk to bits to indicate which are lowercase
  :b    decode as 5-bit integer
  97+]  add 97 and wrap in array to convert to lower case character
}       end block for regex replacement
R       do regex replacement

Run this one

JavaScript (Node.js), 100 bytes
s=>s.toLowerCase(c=/[a-z]/gi).replace(/_/g,_=>(g=n=>n?(c.exec(s)<{})*n+g(n>>1):10)(16).toString(36))

Try it online!
Thanks to @Arnauld, saves 2 bytes.

@Arnauld you are right. edited to /[a-z]/gi now.

R, 153 135 113 bytes
function(s,S=utf8ToInt(s)){S[S==95]=2^(4:0)%*%matrix(S[S%in%c(65:90,97:122)]<95,5)+97
cat(tolower(intToUtf8(S)))}

Try it online!
Issues some warnings with the use of matrix but that shouldn't affect the result. Also issues warnings as [<- assignment will remove extraneous assigned objects by default.
40(!) bytes down thanks to JayCe's improvements

I don't think you need ,length(L)%/%5

Also no need to define L?

@JayCe okay well today I learned that [<- will throw out elements past the length of the indexes...

Me too actually!

Translated your approach to intToUtf8

113 chars :)

@JayCe very nice! I made an R chatroom a month or two ago, but it died because there weren't many active R golfers; it seems like we're starting to get a couple (you, ngm, Kirill L occasionally, I've seen pajonk get active suddenly) who are more active so it might be time to create a new one!

sounds like a great idea!

Haskell, 139 bytes
([]%)
a%(x:y)|x=='_'=['a'..]!!foldl1((+).(2*))(take 5a):drop 5a%y|x>'@',x<'['=[x..]!!32:(a++[1])%y|x>'`',x<'{'=x:(a++[0])%y|1<2=x:a%y
a%e=e

Try it online!

TypeScript's Type System, 637 526 515 505 496 490 489 bytes
//@ts-ignore
type a<S="abcdefghijklmnopqrstuvwxyz",A=[]>=S extends`${infer F}${infer R}`?a<R,[...A,F]>:A;type u<S,D>=D extends`${infer A}${infer R}`?`${u<S,R>}${u<S,R>}${S[A]extends a[any]?"":1}`:D;type c<S,T=[]>=S extends[{},{},{},{},{},...infer R]?c<R,[...T,a[a<u<S,"43210">>["length"]]]>:T;type p<S,O=[]>=S extends[infer A,...infer R]?p<R,F<A,0>extends a[any]?[...O,A]:O>:O;type F<S,V=c<p<a<S>>>>=[S,V]extends[`${infer A}_${infer B}`,[{},...infer R]]?F<`${A}${V[0]}${B}`,R>:Lowercase<S>

Try it at the TS Playground!
I managed to golf off a load of bytes:

I started by using @emanresu A's much shorter binary-to-unary type, but noticed that in this case it would be shorter if it operated on a tuple rather than string of bits, so I modified it accordingly.
I then thought to have the binary-to-unary type operate not on 1s and 0s, but on the characters themselves, and check if it's uppercase or lowercase within that same type, saving a lot of bytes.
I no longer needed the Split type for anything other than the alphabet, so I inlined the alphabet into it's definition.
I realized that F could be inlined into the FillBlanks type, by Lowercaseing the final result and giving the fill string a default. I also utilized this tip of mine to reduce two extends clauses into one, saving around 10 bytes.
I changed the Chunk type to operate on a list of characters, so the pattern match could be reduced to just "5 items and the rest", with the 5 items selected individually, and did the splitting in F.
I did a bit more rearranging to reduce the Chunk type a lot more.
I golfed away 2 infer clauses and removed a pair of unneeded parentheses.
I changed u back to using a string and then splitting it to get its length in c.

I’d say at this point this is one of my most well-golfed TS submissions.

This was a fun one!
The following explanation more closely resembles my old 637 bytes version, but the general structure is still roughly the same.
// Split<Str> converts string Str to a tuple of characters.
type Split<
  Str extends string,
  Arr extends string[] = []
> = Str extends `${infer A}${infer R}` ? Split<R, [...Arr, A]> : Arr;

// Lowercase alphabet tuple.
type Alphabet = Split<"abcdefghijklmnopqrstuvwxyz">;

// To get the case of a letter:
// if it is in the lowercase alphabet, return 0, else 1.
type Case<C extends string> = C extends Alphabet[number] ? 0 : 1;

// Replace all occurrences of Find with Rep in string Str.
type Replace<
  Str extends string,
  Find extends string,
  Rep extends string
> = Str extends `${infer Start}${Find}${infer Rest}`
  // Recursively substitute until no more occurrences are found.
  ? Replace<`${Start}${Rep}${Rest}`, Find, Rep>
  : Str;

// See https://esolangs.org/wiki/Binary_to_unary_conversion
type BinToUn1<In extends string> = Replace<In, "1", "0*">
type BinToUn2<In extends string> = Replace<In, "*0", "0**">
type BinToUn3<In extends string> = Replace<In, "0", "">
type BinaryToUnary<Binary extends string> = BinToUn3<
  BinToUn2<BinToUn1<Binary>>
>;

// This type does the bulk of the work.
type Chunk<
  S extends string,
  T extends string = ""
  // Map each chunk of five letters to:
> = S extends `${infer A}${infer B}${infer C}${infer D}${infer E}${infer R}`
  ? Chunk<
      R,
      // The character of the alphabet at index
      `${T}${Alphabet[
        // convert from binary
        Split<BinaryToUnary<
          // the case of each character in the chunk.
          `${Case<A>}${Case<B>}${Case<C>}${Case<D>}${Case<E>}`>
        >["length"]]}`
    >
  : T;

// Filter out non-alphabetic characters.
type Alphabetics<
  S extends string,
  O extends string = ""
> = S extends `${infer A}${infer R}`
  ? Alphabetics<R, Lowercase<A> extends Alphabet[number] ? `${O}${A}` : O>
  : O;

// Fill each underscore with the corresponding character
// of the fill string.
type FillBlanks<
  Str extends string,
  Fill extends string
> = Str extends `${infer Start}_${infer Rest}`
  ? Fill extends `${infer X}${infer R}`
    ? FillBlanks<`${Start}${X}${Rest}`, R>
    : Str
  : Str;

// Final type that composes all of the above to a single type:
type F<S extends string> = Lowercase<FillBlanks<S, Chunk<Alphabetics<S>>>>;

Try it at the TS Playground!
All of the recursive types used here are tail-recursive, increasing the recursion limit from 50 to 999. The only exception to this is the binary-to-unary type, but it won't get near the recursion depth for any 5-bit number.

Why is Split necessary? string already implements ArrayLike<string>.

@Bbrk24 Because you can't index into or get the length of a string type.

You can save 2 bytes by using 2 instead of * (you don't need to quote 20)

@Bbrk24 Thought of that but forgot to add it, thanks!

You can save ~30 bytes by using the binary-to-unary algorithm from my answer here (note: While it's not tail-recursive the recursive calls only go log(n) levels deep)

@emanresuA i never got around to implementing your suggestion until now but thanks! i managed to save another 100 bytes while implementing that lol

Go, 219 217 192 210 209 156 bytes
Saved 25 bytes thanks to @Lynn!
Saved 53 bytes thanks to @ovs!
Had to lose 18 bytes because of a bug with strings with no underscores :(
func p(s string){b:=0;n:=0;for _,c:=range s{if IsLetter(c){b+=b;if IsUpper(c){b+=1};n++;s=g.Replace(s,"_",string('a'+b%32),(5-n%5)/5)}};Print(g.ToLower(s))}

Try it online!

Red, 247 bytes
func[s][a: charset[#"a"-#"z"#"A"-#"Z"]v: copy""parse s[any[copy c a(append v to-string c)|
skip]]k: 0 t: copy""repeat n(length? v)/ 5[c: 0 p: 16
loop 5[if v/(k: k + 1) <#"a"[c: c + p]p: p / 2]append t#"a"+ c]foreach c
t[replace s"_"c]lowercase s]

Try it online!
More readable:
f: func[s][
    a: charset[#"a"-#"z"#"A"-#"Z"]
    v: copy ""
    parse s[any[copy c a(append v to-string c)| skip]]
    k: 0
    t: copy ""
    repeat n (length? v) / 5[
        c: 0
        p: 16
        loop 5[
            if v/(k: k + 1) < #"a" [c: c + p]
            p: p / 2
        ]
        append t #"a" + c
    ]
    foreach c t[replace s "_" c]
    lowercase s
]

Haskell, 165 bytes
g""
import Data.Char
f t(x:s)('_':r)=x:f t s r
f[0,a]s r=g(s++[chr a])r
f[n,a]s(c:r)=toLower c:f[div n$1+sum[1|isAlpha c],a+sum[n|isUpper c]]s r
f _ s e=e
g=f[16,97]

Try it online! Example usage: g"" "BInar_" yields "binary".

PowerShell, 121 bytes
switch -r($args|% t*y){_{$_=$a[$n++]+97}[a-z]{$x+=$x+($_-le96);if(!(++$i%5)){$a+=,$x;$x=0};$_=$_-bor32}.{$r+=[char]$_}}$r

Try it online!
Less golfed:
switch -Regex ($args|% toCharArray){
    _ {                     # is underscore
        $_=$a[$n++]+97      # get a char from the array of letter
    }

    [a-z] {                 # is letter
        $x+=$x+($_-le96)    # $x=2*$x+($_-le96)
        if(!(++$i%5)){      # if(++$i%5 -eq 0)
            $a+=,$x         # add an element to the array of letters
            $x=0            # init
        }
        $_=$_-bor32         # to lower
    }

    . {                     # is any char ('_' and letters included)
        $r+=[char]$_        # add the char to result
    }
}
$r

Ruby, 107 106 103 bytes
->s{s.chars.map{|c|c !~/\W|\d/?c<?a?1:0:p}.join.scan(/.{5}/){|b|s[?_]&&=(b.to_i(2)+97).chr};s.downcase}

Try it online!

Java 10, 186 184 162 bytes
s->{var b="";for(Byte c:s.getBytes())s=(b+=c>64&c<91?1:c>96&c<123?0:"").length()>4?s.replaceFirst("_",(char)(97+c.valueOf(b,2))+(b="")):s;return s.toLowerCase();}

-2 bytes thanks to @ceilingcat.
Try it online.
Explanation:
s->{                        // Method with String as both parameter and return-type
  var b="";                 //  Binary-String, starting empty
  for(Byte c:s.getBytes())  //  Loop over the characters of the input-String:
    s=(b+=c>64&c<91?        //   If the current character is a lowercase letter:
           1                //    Append "1" to the binary-String
          :c>96&c<123?      //   Else-if it's an uppercase letter:
           0                //    Append "0" to the binary-String
          :                 //   Else (it's not a letter):
           ""               //    Append nothing to the binary-String
      ).length()>4?         //   And if the length of the new binary-String is now 5:
       s.replaceFirst("_",  //    Replace the first "_" in the input-String with
          (char)(97+c.valueOf(b,2))
                            //    the binary-String as character
         +(b="")):s;        //    And reset the binary-String
  return s.toLowerCase();}  //  Return the modified lowercased input-String

@ceilingcat Thanks, but I've been able to save 22 more bytes by changing the for-loop to a for-each loop instead.

Japt, 25 bytes
r'_@r\L mè\A sTT±5 ÍdIÄÃv

Try it

Explanation
r'_                           :Replace underscores
   @                          :Pass each match through a function
    r                         :  From original input remove
     \L                       :    /[^a-zA-Z]/g
        m                     :  Map
         è                    :    Count
          \A                  :      /[A-Z]/g
             s                :  Slice
              T               :    From index T (initially 0)
               T±5            :    To index T+=5
                   Í          :  Convert from base-2 string to base-10 integer
                     IÄ       :  Add 64+1
                    d         :  Get character at that codepoint
                       Ã      :End function
                        v     :Lowercase

Perl 5 -p, 78 bytes
for$h(s/\W|\d//gr=~y/a-z/0/r=~y/A-Z/1/r=~/.{5}/g){s%_%chr 65+oct"0b$h"%e}$_=lc

Try it online!

I fixed it with 3 more bytes, which makes your answer a bit better under the current rules.

Not better but different. Each language + options is considered separately, not competing with the same language + other options, as I understand it.

Pyth, 36 bytes
Km@Gim!}kGd2c@+r1GGQ5VQp?qN\_.(KZr0N

Try it here
Explanation
Km@Gim!}kGd2c@+r1GGQ5VQp?qN\_.(KZr0N
             @+r1GGQ                   Get the letters from the input...
            c       5                  ... in chunks of 5.
 m        d                            For each chunk...
     m!}kG                             ... check if each letter is uppercase...
    i      2                           ... converted to binary...
  @G                                   ... and get the corresponding letter.
                     VQp               For each character in the input...
K                       ?qN\_.(KZ      ... if the character is '_', replace it...
                                 r0N   ... otherwise, lowercase it.

Python 3.5, 296 bytes
u=input();f=u.find('_');m=''.join([c for c in u if c.isalpha()]);z=[chr(int(''.join(['0'if o.islower() else'1' for o in l]),2)+65)for l in[m[h:h+5]for h in range(0,len(m),5)]if len(l)==5];[z.insert(v,d)for v,d in enumerate(u[f:])if d!="_"];u=list(u);u[f:]=z[:len(u[f:])];print(''.join(u).lower())

Try it online
First code golf :)
(I know its not small in bytes, I was just having fun making a 1 line code)
Here is the explanation:

User input

u=input()

Finds the index of the first _ in the string and stores it

f=u.find('_')

strips string of all non-alpha characters

m=''.join([c for c in u if c.isalpha()])

Splits the alpha string into an array with each element consisting of 5 characters
Ex. ['THeqU', 'ICkbr', 'ownFO', 'xJUMp', 'soVEr', 'thela']
Then converts lowercase characters to 0 and uppercase characters to 1
Ex. ['11001', '11000', '00011', '01110', '00110', '00000']
and converts the binary string to an integer, adds 65 and converts that to a character
Ex. ['z', 'y', 'd', 'o', 'g', 'a']

z=[chr(int(''.join(['0' if o.islower() else '1' for o in l]),2)+65) for l in [m[h:h+5] for h in range(0,len(m),5)] if len(l)==5]

finds all characteres after the first _ and pushes them into the array z at their respective locations (defined above)
Ex. ['z', 'y', ' ', 'd', 'o', 'g', '.', 'a']

[z.insert(v,d) for v,d in enumerate(u[f:]) if d!="_"]

split our string into a list of characters

u=list(u)

slice our string from the first _ to the end of the list and replace it with the array z.  I also had to slice the array z to the length of the split string from the first _ to the end because I got an extra character in the lazy dog example (the "a" at the end of the examples above)

u[f:]=z[:len(list(u[f:]))]

*print out the answer *

print(''.join(u).lower())

There's more to golfing than just getting everything on one line. 165 bytes

You can remove the space between o.islower() and else, and I think '1' and for. Also, you can change if d!="_" to if"_"!=d, but the above comment already does that.

jq, 165 159 bytes
Unnecessary space before as, and found a place where(a|[thing])[] could be replaced with (a|thing)
reduce(split("[^a-z]";"i")|add|explode|while(length>4;.[5:])[:5]|map(try(.>91//1)+0//0)|reduce .[]as $x(3;2*.+$x)+1)as $r(ascii_downcase;sub("_";[$r]|implode))

Try it online!

Try it online!
Phew, this was a fun one! reduce is the real star of the show here.
reduce (
    # filter to alphanumeric characters and explode string into codepoints
    split("[^a-z]";"i") | add | explode |
    # chunk letters from string into full groups of 5
    while(length>4; .[5:])[:5] |
    # for each chunk emit 1 if uppercase, 0 if lowercase
    map(try(.>91//1)+0//0) |
    # reduce each chunk to a codepoint
    # start with 3, double and add the next element in the array.
    # [0,0,1,1,0] -> 6 [0,1,1,0] -> ... 102, we need to add one to map correctly
    reduce .[] as $x(3;2*.+$x)+1
# for each code point $r:
) as $r (
    # initialize with lowercased input
    ascii_downcase;
    # substitute "_" with the current letter ([codepoint]|implode)
    sub("_";[$r]|implode)
)

Vyxal, 135 bitsv2, 16.875 bytes
\_ÞIλ?Ǎ5ẇƛaB›øA}¢ɽ

Try it Online!
The s flag is for user convenience. Outputs as a list of characters otherwise.
Explained
\_ÞIλ?Ǎ5ẇƛaB›øA}¢ɽ
\_ÞIλ          }¢   # Replace the indices that correspond to "_"s by each letter in:
     ?Ǎ5ẇ           #   Push the input with non-letters removed, wrapped in chunks of length 5
         ƛ     }    #   To each chunk:
          aB›       #     int(is_upper(chunk), 2) + 1
             øA     #     Nth letter
                 ɽ  # Convert that to lowercase

Created with the help of Luminespire.

GolfScript, 94 84 82 72 bytes
.{.[65-\97-]{26,?)}/+},5/{{91<}%2base}%:s;0:l;{32|.127={l):l(s=97+}@if}%

Try it online!
This is probably not optimal but I can't find anything shorter.
Explanation:

{.[65-\97-]{26,?)}/+},
Filter by:

For each of [inp - 65, inp - 97]:

Index of this in [0, 1, ..., 25] (-1 if not found)
Add one to get 0 for not found, nonzero otherwise

Take the sum of the result, giving 0 iff if both results were 0.

5/ Divide into chunks of length 5.

{{91<}%2base}%:s;
Map each chunk of 5 to:

Map each of the 5 to:

Is it less than 91? (is it uppercase?)

Convert this result from binary to decimal.
Assign this to the variable s.

0:l; Assign the variable l to 0.

{ ... }% Map each character of the input to:

32| Convert to lowercase by bitwise or-ing with 32. This will give 127 for an underscore.

.127={ ... }@if Return that unless it is 127 (for us, underscore), in which case...

l):l Increment l

(s= Index into s

97+ Add 97 to make it a lowercase letter.


text:
Find the longest uninterrupted arc
The challenge here is to find the longest uninterruped arc around a unit circle with a random amount of points distributed in random positions around it.
Here is a diagram to assist my explanation:

The red line indicates the largest arc between any two points that is not interrupted by any other points. The challenge is to find the two points on either end of the red line. The green line is simply the straight line distance.
A clarification about what interrupted means: When drawing an arc around the edge of the circle (the red line), this arc should not be intersected by any other point.
Here is a template for the function in C#:
int[] FindPair(double[][] points)
{
     return new[]{ 0, 1}; //Find the indices of the two points
}

The function should return two integers, the indices of the two points on either end of the green line.
Assumptions:

The Length of the points array is arbitrary but more than two. In the example we have: points[40][]
Each element of the points array contains the x, y position of the point, for example:  points[i] = {x, y}
You can assume that the distance of any given point to the origin at the centre of the circle is always 1.

Notes:

The answer with the smallest Big O algorithm complexity wins. In case of a tie, shorter code wins.
Bonus points for the solution to have the ability to work in more dimensions than two.
I do have a solution, but it is very computationally expensive and only produces the correct answer around 99% of the time.
I am not sure if the problem has a name in mathematics, or a generally accepted solution. If anyone knows of a better name for this problem so that I can have a better title, that would be helpful.

Test case 1:

Points: {
  { -0.71997 , -0.69400 },
  { 0.88564 , 0.46437 },
  { 0.78145 , -0.62397 },
  { 0.98409 , -0.17765 },
  { 0.88220 , 0.47087 },
  { 0.69938 , 0.71475 },
  { -0.89036 , -0.45526 },
  { -0.70588 , -0.70833 },
  { 0.70507 , 0.70914 },
  { -0.34971 , 0.93686 }
}

Solution:
{6, 9}

Test case 2:

Points: {
  { -0.71038 , 0.70382 },
  { 0.04882 , 0.99881 },
  { -0.53250 , -0.84643 },
  { -0.86814 , -0.49632 },
  { 0.97588 , -0.21829 },
  { 0.73581 , -0.67719 },
  { 0.88413 , -0.46724 },
  { -0.28739 , -0.95781 },
  { -0.68325 , 0.73019 },
  { 0.91879 , 0.39475 },
  { 0.65335 , 0.75706 },
  { -0.21009 , -0.97768 },
  { -0.94542 , -0.32585 },
  { 0.83207 , -0.55467 },
  { 0.99482 , 0.10170 },
  { 0.86228 , 0.50643 },
  { 0.98017 , 0.19817 },
  { 0.67520 , 0.73763 },
  { -0.03982 , -0.99921 },
  { -0.57624 , -0.81728 }
}

Solution: {0, 12}

Invalid example:

This is invalid, because when drawing an arc around the edge of the circle (the red line) between the two points connected by the green line, this arc is intersected by another point.

Welcome to PPCG! This question might get closed because this community is quite strict about the standards for winning conditions. But I hope you stick around and set more challenges! You are strongly encouraged to try them out in the sandbox, to get feedback before posting them on the main site.

@Nathaniel: I completely understand, please let me know if there is anything I can do to improve the winning conditions.

@Karl The only case that the arc is "interrupted" is the arc is larger than 180°, in that case just discard the arc. (<-- initially I overlooked that part because none of the test cases have such an "arc", but that can be checked in linear time)

@Karl I believe that a good number of coders on the site would come up with an optimal solution almost instantly for this specific problem, making it largely a race to post first.

I have added code-golf to the precedence. If I am proven wrong, and an optimal solution is easy to find then we can golf the optimal solution. But I still think the computational complexity is a challenge in itself.

Complexity is O(n) if you read similar problem, so it's mainly a code-golf; but is it [tag:fastest-code] or [tag:restricted-complexity]?

@l4m2: What is the similar problem? If you can give an answer in O(n) I would be very impressed. It would not be fastest-code but rather fastest-algorithm and then code-golf.

@user202729: Yes that would be valid. You can assume the input will always have 2 or more points.

JavaScript (Node.js), O(n), 234 229 228 211 bytes
a=>(b=a.map(s=>Math.atan2(...s)/Math.PI+2),k=[],b.map(t=>d=![k[u=t*a.length|1]=t<k[u]?k[u]:t,k[--u]=t>k[u]?k[u]:t]),k.filter(t=>t).map((v,i,s)=>d=d<(t=s[i+1]||s[0]+2)-v?(T=t)-(V=v):d),[T,V].map(x=>b.indexOf(x)))

Try it online!
Assuming:

atan2 is O(1)
x.map, x.filter are O(n) function calls
x.indexOf is O(n)

a=>(
  n=a.length,
  b=a.map(([t,u])=>Math.atan2(t,u)/Math.PI+2),    // [1, 3)
  k=[...Array(n*4)],
  b.map(t=>d=![k[u=t*n|1]=t<k[u]?k[u]:t,k[--u]=t>k[u]?k[u]:t]),
  // interval = 2/n, just enough
  k.filter(t=>t).map(
    (v,i,s)=>d=d<(t=s[i+1]||s[0]+2)-v?(T=t)-(V=v):d
  ),  // furthest
  [b.indexOf(T),b.indexOf(V)]
)

How stupid I was

but in this case is array manuing still O(1)?

I still don't understand how this works, but I am willing to accept this as the answer once I have the chance to run extensive test cases. Even though it is longer than the other answer, it has a lower time complexity.

Unless the points are always given in order around the circle, an O(n) time solution is not possible.

@Anush I degolfed it and, after probably hours of investigation, have concluded that it's legit. It seems to work as follows. It splits the circle into n equal segments, where n is the number of points. In each segment, it records the min and max angle. The longest arc is then found by comparing the max angle of one segment to the min angle of the next nonempty segment. This utilizes the fact that the longest arc will always span multiple segments since it must always be at least 2pi/n radians in length. Very very clever solution! I hope OP doesn't mind me revealing their secrets ;P

Here is my degolf + 3:30AM writeup of this answer, if anyone else is interested in how it works.

Python 3, O(n*log(n)), 167 bytes
import math
def f(p):p=[math.atan2(*x)for x in p];q=sorted(p);d=[b-a for a,b in zip(q,q[1:])]+[math.pi*2-q[-1]+q[0]];i=d.index(max(d));return map(p.index,(q*2)[i:i+2])

Try it online!
The sorting step takes O(n*log(n)) time, all other steps take linear time.

Ungolfed
import math
def f(p):
  p=[math.atan2(x, y)for x, y in p]   # convert coords to angle (radians)
  q=sorted(p)                         # sort by angle
  d=[b-a for a,b in zip(q,q[1:])]     # calculate the difference between two adjacent points
  d+=[math.pi*2-q[-1]+q[0]]           # difference between first and last point
  i=d.index(max(d))                   # where is the maximum delta?
  return map(p.index,(q*2)[i:i+2])    # where were these two points in the original list?

An interesting answer. I see now it is easy to solve in two dimensions. Would this approach be able to work in more than two dimensions with some modifications? Or would that be best suited as another question?

@Karl Another question. Although in more than 2D it's very unlikely that a point lies right on a line segment, and it's hard to determine due to numerical inaccuracy.

You're right, the only approach I've found in more than 2D involves taking many samples across the arc and checking for intersections.

@user202729 If you could post that math in an (incomplete?) answer, that would be appreciated.

APL (Dyalog Unicode), O(n), 92 bytes
L←12○⎕
x←(n←⍴L)⍴⊂⍬
L{x[⌊n×.5+⍺÷○2],←⊂⊂⍺⍵}¨⍳n
1∘⊃¨{2↑⍵⌽⍨⊃⍸(⌊/=⊢)2-/{⍵,⍵+○2}⊃¨⍵}⊃,/{⍵[⍋⊃¨⍵]}¨x

Try it online!
Takes input as a vector of complex numbers and outputs a single array of the two indices. This uses bucket sort to achieve linear complexity.
Requires ⎕IO←0
Details
L←12○⎕   ⍝ Take input to L and convert all points to their phases  -- O(n)
n←⍴L     ⍝ Set n to be the length of L
x←n⍴⊂⍬   ⍝ Create an array consisting of `n` empty buckets         -- O(n)
L{...}¨⍳n  ⍝ For each ⍺=element of of L, ⍵=corresponding index:    -- ×n:
  ⍺⍵         ⍝ Create an entry consisting of the two-element array ⍺ ⍵    -- O(1)
  x[...],←⊂⊂ ⍝ Append it to the correct bucket in x                       -- O(1)
  ⌊n×.5+⍺÷○2 ⍝ Map phases in [-pi, pi) to bucket indices in 0..n-1        -- O(1)
x          ⍝ Now, x is a vector of buckets,
           ⍝ each of which contains a vector of entries (phase, index)
{⍵[⍋⊃¨⍵]}¨ ⍝ Sort each bucket by phase (buckets contain 1 element on average, so this is O(1) average case per bucket)
⊃,/        ⍝ Join so we have a single sorted vector of all entries (phase, index)
{...}      ⍝ Computationally less-worrisome part now that we have the phases sorted
           ⍝ Most following lines are O(n), rest are O(1)
  ⊃¨         ⍝ Extract the phase of of each entry
  {⍵,⍵+○2}   ⍝ Add 2pi to each phase, and append (deals with wrapping around)
  2-/        ⍝ Compute the difference of each consecutive pair of phases
               ⍝ (always negative since the phases are increasing)
  ⊃⍸(⌊/=⊢)   ⍝ Find the index i of the minimum difference (most negative --- furthest)
  ⍵⌽⍨        ⍝ Rotate the original vector of (phase, index) by i
  2↑         ⍝ Take the first 2 entries
  1∘⊃¨       ⍝ Get the indices of these two entries

89

JavaScript (Node.js), O(n log n)?, 130 129 125 bytes
a=>a.map((r,i)=>[Math.atan2(...r)+6,i]).sort().map(([r,s],i,a,[p,q]=a[++i]||a[a=0])=>[p-r+!a*2*Math.PI-8,[s,q]]).sort()[0][1]

Try it online!
If the sorting is treated as O(n log n), then the whole algorithm is O(n log n); however it sorts by ASCII, so I'm not quite sure if the complexity remain

How can it give the right answer if it sorts doubles as strings?

@PeterTaylor Align them

Is there any reason you perform a sort (n log n) rather than just a linear search for the maximum value (O(n))? Or am I interpreting the answer wrong?

@Karl Another sort is there, so if using sort is shorter I just use it

Wolfram Language (Mathematica), 92 bytes
s~Position~#-1&/@Last@(S=SortBy)[Partition[S[s=#,ArcTan@@#&],2,1,-1],EuclideanDistance@@#&]&

Try it online!


text:
Give a permutation with no two consecutive integers next to each other
Challenge
Given an integer n ≥ 4, output a permutation of the integers [0, n-1] with the property that no two consecutive integers (integers with absolute difference 1) are next to each other.
Examples

4 → [1, 3, 0, 2]
5 → [0, 2, 4, 1, 3]
6 → [0, 2, 4, 1, 3, 5]
7 → [0, 2, 4, 1, 5, 3, 6]

You may use 1-indexing instead (using integers [1, n] instead of [0, n-1]).
Your code must run in polynomial time in n, so you can't try all permutations and test each one.

When you say "output a permutation", do you mean as a list? Or can we  produce a function that implements the permutation mapping
itself?

@xnor It should be outputted in some human readable form. I don't care exactly how.

Would [[1,3],[0,2]] be an acceptable output format?

@Shaggy It's not great. Does it mean 1,3,0,2?

Related

The related question demands no output if not possible.  This one avoids that by eliminating the only inputs where it isn’t possible (I<4).

Jelly, 3 2 bytes
ḂÞ

Sorts the integers in [1, ..., n] by their LSB.
Try it online!

Wow! That is amazing.

is LSB the least significant bit? I've never seen that acronym before

@Budd Yes, LSB is least significant bit.

“Sort by LSB” means that every other one moves to the beginning, but does the definition of Jelly require that the numbers in each half remain in their original order?  If not, 100 (4) could be next to 101 (5) and still be “sorted by LSB”. Not faulting your code, but perhaps the describing comment isn’t complete?

@WGroleau Yes, Þ stable sort, because it's implemented using Python sorted function, which is guaranteed to be stable.

The algorithm is more impressive to me than the small size, in its cleverness.  You could also, I suppose, reverse the bit order, sort, and reverse it back.

There can only be 65536 different two byte Jelly programs. It is amazing so many of those turn out to be answers to ppcg challenges.

@WGroleau Sure, but "reversing bit order" is a builtin almost never

Python 2, 32 bytes
lambda n:(range(n|1)*2)[1:n*2:2]

Try it online!

Python 3, 40, 38 bytes
lambda n:[*range(1,n,2),*range(0,n,2)]

Try it online!
This runs in O(n) time.
Thanks to Dennis for saving 2 bytes!

Winner of the fastest prize! :)

Fastest running, or first posted?

@WGroleau First posted.

Python 2, 34 bytes
lambda n:range(1,n,2)+range(0,n,2)

Try it online!
Python 2, 40 bytes
lambda n:[(k-~k)%(n|1)for k in range(n)]

Try it online!

Octave, 17 bytes
@(x)[2:2:x,1:2:x]

Try it online!
This uses the same approach as many others. Concatenate two vectors, one with all the even number in the inclusive range 2 ... x, and all the odd numbers in the inclusive range 1 ... x. The syntax should be fairly obvious, so I won't explain that.

Aren't 3 and 2 next to each other in f(4)?

Oops... fixed. Same byte count. :-)

Haskell, 22 bytes
f is a function of n that returns an appropriately ordered list. I am using the 1-indexing option.
f n=[2,4..n]++[1,3..n]

Gaia, 2 bytes
r∫

Try it online!
This simply (stable) ∫orts the integers in the range [1, input] by their parity.

Same comment as on Jelly:  does the algorithm or the definition of the language guarantee that the two halves each remain in their original order?

@WGroleau Yes, in Gaia, the sort meta-operator is stable.

R, 39 36 35 bytes
function(x)c(seq(2,x,2),seq(1,x,2))

Try it online!

There is a trailing NA for odd numbers.

https://tio.run/#%23K/qfZvs/rTQvuSQzP0@jQjNZo8pGtzi1UMNQp0LHSFOnKrrKpiJW21Dzf5qGpSZXmoaF5n8A

Wife's fault. We had to go on our bike ride before I could fix that. But you shaved some bytes off too.

Yeah I felt bad asking you to add bytes so I had to find a way to remove some... it worked out well.

Aren't 3 and 2 next to each other for f(4)?

@pajonk that won't work either, as f(9) doesn't include 8 but does include 0

inspired by the octave answer

@Giuseppe f(4) still not working

@pajonk ah duh, then just reverse them. My bad.

@pajonk one byte added in the process

@Giuseppe oh but yours is shorter just realized that.

05AB1E, 3 bytes
Port of DJMcMayhem's Python answer and Dennis's Jelly answer
ÝΣÉ

Try it online!
How?
ÝΣÉ - implicitly take input onto stack  e.g. 7
Ý   - pop a and push range(a)               [0,1,2,3,4,5,6]
 Σ  - sort by (stable):
  É -   is even? (x%2==0 ?)                 [1,3,5,0,2,4,6]
    - implicit print of top of stack

JavaScript (ES6), 40 bytes

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))
<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Edit: Saved 1 byte thanks to @Arnauld.

Japt, 4 bytes
You could also replace u with v to get a different order.
õ ñu

Try it
Or, if we can ouput an array of 2 arrays:
õ ó

Try it

Technically the second one outputs a list of numbers separated by commas ;-) Both fail on 4, unfortunately; you can fix the first one by changing u to v or o to õ.

Mathematica, 50 -> 47 -> 42 bytes
p = Join[Range[2, #, 2], Range[1, #, 2]] &

Try it online!
Thanks to user202729 for pointing out the twofold optimization potential Join[] insteaed of Flatten[] and using pure functions.
I'd like to add two remarks.
1) It is fairly straightforward to construct a specific permutation with no falling or rising succession for n>=4 as requested n the OP.
It consists of two consecutive list.
For even n these are:
list1 = (2,4,...,n/2)
list2 = (1,3,...,n/2-1)
For odd n we have:
list1 = (2,4,...,Floor[n/2])
list2 = (1,3,...,Floor[n/2])
For this "algorithm" just one decision must be made (n even or odd), the rest is just writing down n numbers.
A possible Mathematica solution is provided at the top.
2) A related question is how many such permuations exist as a function of n.
Mathematica, 124 Bytes
a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Try it online!
Example:
a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034}

To count the number of such permutations is a standard problem.
For n = 4 there are 2:
{{2,4,1,3},{3,1,4,2}}
For n = 5 there are 14:  {{1,3,5,2,4},{1,4,2,5,3},{2,4,1,3,5},{2,4,1,5,3},{2,5,3,1,4},{3,1,4,2,5},{3,1,5,2,4},{3,5,1,4,2},{3,5,2,4,1},{4,1,3,5,2},{4,2,5,1,3},{4,2,5,3,1},{5,2,4,1,3},{5,3,1,4,2}}
The number a(n) of these permutations rises quickly: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...
For large n the ratio a(n)/n! seems to approach the limit 1/e^2 = 0.135335...
I have no strict proof but it is just a conjecture from numerical evidence. You can test this by trying to run the program online.
The program above (based on the reference given below) calculates these numbers.
You can find more information in the relevant sequence on OEIS: A002464. Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.

@ Stewie Griffin As I am new here, please explain in more detail what you mean. In my first remark I have provided an algorithm and a code which solves the problem in polynomial time. Hence it should be considered a solution to the challenge. The second part extends the interesting problem. Hence it should be regarded as a comment.

I took the liberty of slightly modifying your submission so your Mathematica code is at the top. With code-golf challenges it's mandatory to provide actual code (shortest possible). The way I formatted it it becomes a Mathematica answer as you probably intended it to be, and still has your original explanation below it. If you feel something is missing or I incorrectly edited your initial answer, feel free to edit it yourself again. Welcome to PPCG! :)

@ Kevin Cruijssen Thank you very much for th warm welcome and the editing of my naive submission. I have now added a Mathematica program for the second remark. Which is most probably not lege artis. Most of all I don't know how to create the nice "try it online" link.

Any link can be created using [some text](the_link). As for the "Try it online" link in particular, the website https://tio.run/ that's being hosted by our very own @Dennis contains links to all kind of programming languages. Wolfram Language (Mathematica) is one of them. At the top you can then click the play button to run the code, or the hyperlink button to copy "Try it online." (markup-)links. And you can split your code into actual "Code" (your submission), with an optional header/footer for (pretty-)printing one or multiple testcases.

Apologies for my somewhat blunt comment, and lack of reply thereafter! The answer appeared in the review queue, and I didn't notice the code because of the formatting. It's not uncommon that new users posts "interesting observations" to challenges, without providing an actual answer to it. While it's done in good faith, it's not what the site is about. I thought this was such an answer. I should have responded to your comment, but I was in a hurry and couldn't write a new comment, so instead I just removed the old one. Apologies! And welcome to the  site! I hope you'll stick around! :)

@ Kevin Cruijssen Than you for the hints. I tried my very best but 1) the program wouldn't run in tio, and 2) the link looks terrible in the text. I'm afraid I still need some help.

@ Stewie Griffin Apology accepted, of course. Don't worry, it's ok. I hope to adapt quickly to the customes in this interesting forum.

You can use lambda function to shorten the program. p=Flatten[{Range[2,#,2],Range[1,#,2]}]&. Also, we allow anonymous function (an expression that evaluates to a function) by default, so Flatten[{Range[2,#,2],Range[1,#,2]}]& suffices. Using Join and infix notation would be shorter: Range[2,#,2]~Join~Range[1,#,2]&.

(and all answers on a [tag:code-golf] challenge must attempt to be as short as possible, i.e., must be a serious contender submission)

Ruby, 27 bytes
->n{[*2.step(n,2)]|[*1..n]}

Try it online!
Using 1-indexing

Whitespace, 161 bytes
Here is the official, uncommented submission:
Try it online!
push_0
read_n
		push_0
retreive_n			push_1
subtract	   dup_and_out[

 	]label_s'

'push_2
subtract	   dup[
 ]jump_next_if_neg:

:dup_and_out[

 	]else_jump_back:

:label_ss'

'push_0
retreive_n			push_2
subtract	   dup_and_out[

 	]dup[
 ]jump_next:

:label_ssss'

'push_2
subtract	   dup[
 ]jump_end_if_neg:

:dup_and_out[

 	]else_jump_back:

:label_sss'

'end

Try it online!
I sacrificed a few bytes so that the program would execute without any errors, I believe that I could lose around 7-8 bytes, and it would still output correctly, but it would also output error messages, and nobody wants that.
Full Byte Explanation:
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate

Some things to golf: push_0, read_STDIN_as_int, push_0, retrieve can be push_0, duplicate_0, read_STDIN_as_int, retrieve to save a byte. And the first label can be an empty one with NSSN instead of NSSSN (and then the second label can be NSSSN; third NSSTN; and fourth NSSSSN). This should save 8 bytes as well. Also, you can remove the first Jump_to_third_label because you have the Set_third_label right below it already. In total: 140 bytes; (or with comments: Try it online.) -3 bytes if you remove NNN exit.

JavaScript (Node.js), 42 bytes
n=>(f=i=>i<n?[i,...f(i+2)]:i&1?[]:f(1))(0)

Try it online!
JavaScript (Node.js), 47 bytes
n=>(f=i=>i--?[n--*2%(N|1)+N%2,...f(i)]:[])(N=n)

Try it online!

F# (Mono), 27 bytes
let f n=[2..2..n]@[1..2..n]

Try it online!

Gol><>, 14 bytes
FL:2%Z}:3=?$|B

Try it online!
Example full program & How it works
1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return

J, 10 bytes
i./:2|1+i.

Try it online!
Explanation:
  /:          sort
i.            the numbers in the range 0..n-1
    2|        according the remainder mod 2 of
      1+i.    the numbers in the range 1..n

Java 8, 56 bytes
n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Port of @Neil's JavaScript (ES6) answer.
Try it online.

Old 66 bytes answer:
n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Try it online.
Explanation:
n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other

Ruby, 27 bytes
->n{(1..n).sort_by{|i|i&1}}

As in this answer, n first integers are sorted by their least significant bit.
Try it online!