text:
Digital Sum Fibonacci
We are all familiar with the Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

However, instead of, f(n) = f(n-1) + f(n-2) we'll be taking digital sum of the previous 2 entries.

The sequence should still start with 0, 1, after that the differences are rapidly apparent. This list is 0-indexed, you may use 1-indexed as well, state which you used.
f(0)  = 0
f(1)  = 1
f(2)  = 1   # 0 + 1
f(3)  = 2   # 1 + 1
f(4)  = 3   # 1 + 2
f(5)  = 5   # 2 + 3
f(6)  = 8   # 3 + 5
f(7)  = 13  # 8 + 5
f(8)  = 12  # 8 + 1 + 3
f(9)  = 7   # 1 + 3 + 1 + 2
f(10) = 10  # 1 + 2 + 7
f(11) = 8   # 7 + 1 + 0
f(12) = 9   # 1 + 0 + 8
f(13) = 17  # 8 + 9
f(14) = 17  # 9 + 1 + 7
f(15) = 16  # 1 + 7 + 1 + 7
f(16) = 15  # 1 + 7 + 1 + 6
f(17) = 13  # 1 + 6 + 1 + 5
f(18) = 10  # 1 + 5 + 1 + 3
f(19) = 5   # 1 + 3 + 1 + 0
f(20) = 6   # 1 + 0 + 5
f(21) = 11  # 5 + 6
f(22) = 8   # 6 + 1 + 1
f(23) = 10  # 1 + 1 + 8
f(24) = 9   # 8 + 1 + 0
f(25) = 10  # 1 + 0 + 9
f(26) = 10  # 9 + 1 + 0
f(27) = 2   # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)

Note: I didn't notice the repetition until I posted the challenge itself, and here I was thinking it'd be impossible to write another novel Fibonacci challenge.

Your task is, given a number n, output the nth digit of this sequence.
First 3 digits: [0,1,1],
24-digit repeated pattern: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]
Hint: You may be able to exploit this repetition to your advantage.

This is code-golf, lowest byte-count is the winner.

BONUS: If you use the repetition in your answer, I will award the lowest byte-count answer that takes advantage of the repetition in the sequence a bounty of 100 points. This should be submitted as part of your original answer, after your original answer. See this post as an example of what I am talking about: https://codegolf.stackexchange.com/a/108972/59376
To qualify for this bonus your code must run in constant time (O(1)) with an explanation.
Bonus Winner: Dennis https://codegolf.stackexchange.com/a/108967/59376 < Dennis won.
Most Unique Implementation: https://codegolf.stackexchange.com/a/108970/59376
(Also will receive 100 points, finalized after correct answer is chosen)

Can we use 1-based indexing or does it have to be 0-based?

@BusinessCat yeah, sure, screw it.

How do you define takes advantage of the repetition? Does it have to be hardcoded or I just add a %24 to a "normal" solution?

@Dennis I define taking advantage of the repetition to mean O(1). Your code should be running in constant time, if it is truly exploiting the repetition.

@Dennis technically %24 on the input would make it upper bounded at 27 iterations; while, not interesting, it definitely counts.

Could be a fun exploitation in Mathematica by using OEIS series A010077 and WolframAlpha[] function, though I'm sure that falls under standard loopholes

Mathematica, Part[WolframAlpha["A010077", {{"Continuation", 1}, "ComputableData"}],n]

Oasis, 5 bytes
Code:
ScS+T

Try it online!
Expanded version:
ScS+10

Explanation:
ScS+   = a(n)
     0 = a(0)
    1  = a(1)
S      # Sum of digits on a(n-1)
 c     # Compute a(n-2)
  S    # Sum of digits
   +   # Add together

Oh man... I'm going to start learning Oasis too.

JavaScript (ES6), 45 bytes

f=(n,x=0,y=1)=>n?f(n-1,y,(x%9||x)+(y%9||y)):x
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

x and y can't both be 9, since that would require the previous number to be 0, so their digital sum can't exceed 17. This means that the digital root for numbers greater than 9 is the same as the remainder modulo 9.

This, this also will get a bounty equivalent to the repetition leader... This is an awesome mathematical insight.

Python 2, 53 bytes
f=lambda n:n>1and sum(map(int,`f(n-1)`+`f(n-2)`))or n

Recursive function. The base cases of n=0 and n=1 yield n, larger numbers calculate the value by calling f(n-1) and f(n-2) converting each to a string, concatenating the two strings, converting each character to an integer using a map with the int function, and then sums the resulting list.

Using the modulo-24 information I can currently get a 56 byte non-recursive unnamed function:
lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)

Yes! So much +1! A repetition answer :). I've added a bonus section in your honor sir, you're now the leader in a 100 point bounty contest!

JavaScript (ES6), 34 bytes
f=n=>n<2?n:~-f(--n)%9+~-f(--n)%9+2

May freeze your browser for inputs above 27 or so, but it does work for all input values. This can be verified with a simple cache:

c=[];f=n=>n<2?n:c[n]=c[n]||~-f(--n)%9+~-f(--n)%9+2
<input type=number value=0 min=0 step=1 oninput="O.value=f(this.value)"> <input id=O value=0 disabled>

As pointed out in Neil's brilliant answer, the output can never exceed 17, so the digital sum of any output above 9 is equal to n%9. This also works with outputs below 9; we can make it work for 9 as well by subtracting 1 with ~- before the modulus, then adding back in 1 after.

The best I could do with hardcoding is 50 bytes:
n=>"0x"+"7880136ba5867ffedb834968"[n%24]-(n<3)*9+2

Jelly, 8 bytes
;DFS
ç¡1

Try it online!
How it works
ç¡1   Main link. No arguments. Implicit left argument: 0

  1   Set the right argument to 1.
ç¡    Repeatedly execute the helper link n times – where n is an integer read from
      STDIN – updating the left argument with the return value and the right
      argument with the previous value of the left argument. Yield the last result.

;DFS  Helper link. Arguments: a, b

;     Concatenate; yield [a, b].
 D    Decimal; convert both a and b to their base-10 digit arrays.
  F   Flatten the result.
   S  Compute the sum of the digits.

Alternate solution, 19 bytes, constant time
;DFS
9⁵ç23Ð¡⁸ịµṠ>?2

Try it online!
How it works
9⁵ç23Ð¡⁸ịµṠ>?2  Main link. Argument: n

9               Set the return value to 9
 ⁵              Yield 10.
  ç23Ð¡         Execute the helper link 23 times, with initial left argument 10
                and initial right argument 9, updating the arguments as before.
                Yield all intermediate results, returning
                [10,10,2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9].
   ⁸ị           Extract the element at index n. Indexing is 1-based and modular.
     µ          Combine all links to the left into a chain.
       >?2      If n > 2, execute the chain.
      Ṡ         Else, yield the sign if n.

+1 for the chuzpe of “let's just calculate the whole repeated section in constant time“ :D

JavaScript (ES6), 52 46 45 bytes
_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)

Usage
_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)
_(7)

Output
13

Explanation
This function checks if the input is smaller than 2, and if so, it returns the input. Otherwise, it creates an array of two values that are appended to each other as strings. Those two values are the result of calling the function with input - 1 and input - 2.
The ... operator splits this string into an array of characters, which then is converted to a string again, but now with +es between values. This string is then interpreted as code, so the sum is calculated, which is then returned.
This is a double-recursive algorithm, which makes it quite inefficient. It needs 2n-2 function calls for input n. As such, here's a longer but faster solution. Thanks to ETHproductions for coming up with it.
f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c

This doesn't work for big values like 27, it freezes the browser (at least it does for me)

It takes some time, but it will get there... eventually. I'll look into it, but performance isn't important for this challenge...

Well, jesus, it's not that computationally intense, your program should work for values beyond 27... But if it works for 1-28, that technically proves it works for higher.

@KritixiLithos It's the recursion that's the problem. Computing the nth number in the sequence requires roughly 2^(n-2) function calls, which builds up pretty rapidly.

You can save a byte with [..._(--$)+[_(--$)]] :-)

Thanks, now the single-recursion algorithm will need to be another byte shorter...

05AB1E, 8 bytes
XÎF‚¤sSO

Try it online!
Explanation
XÎ        # push 1,0,input
  F       # input_no times do:
   ‚      # pair the top 2 elements of the stack
    ¤     # push a copy of the 2nd element to the stack
     s    # swap the pair to the top of the stack
      S   # convert to list of digits
       O  # sum

Perl 6,  41  37 bytes
{(0,1,{[+] |$^a.comb,|$^b.comb}...*)[$_]}

Try it
{(0,1,*.comb.sum+*.comb.sum...*)[$_]}

Try it
{ # bare block lambda with implicit parameter ｢$_｣
  (

    0, 1,           # first two values

    # WhateverCode lambda with two parameters ( the two ｢*｣ )
    *.comb.sum      # digital sum of first parameter
    +
    *.comb.sum      # digital sum of second parameter

    ...            # keep using that code object to generate new values until:

    *              # never stop

  )[ $_ ]          # index into the sequence
}

You can write the inner lambda as *.comb.sum+*.comb.sum.

You can write (*~*).comb.sum instead of *.comb.sum+*.comb.sum.

CJam, 22 20 bytes
Saved 2 bytes thanks to Martin Ender
ri2,{(_(jAb\jAb+:+}j

Straightforward recursive algorithm, nothing fancy. 0-indexed.
Try it online! or test for 0-50 (actually runs pretty fast).
Explanation
ri                    Read an integer from input
  2,                  Push the array [0 1]
    {             }j  Recursive block, let's call it j(n), using the input as n and [0 1] as base cases
     (                 Decrement (n-1)
      _(               Duplicate and decrement again (n-2)
        jAb            Get the list digits of j(n-2)
           \           Swap the top two elements
            jAb        Get the list of digits of j(n-1)
               +       Concatenate the lists of digits
                :+     Sum the digits

CJam, 42 bytes
Solution using the repetition. Similar algorithm to Jonathan Allan's solution.
ri_2,1+"[2358DC7A89HHGFDA56B8A9AA]"S*~@*+=

Try it online!

MATL, 15 bytes
lOi:"yyhFYAss]&

Try it online!
lO       % Push 1, then 0. So the next generated terms will be 1, 1, 2,...
i        % Input n
:"       % Repeat that many times
  yy     %   Duplicate top two elements in the stack
  h      %   Concatenate into length-2 horizontal vector
  FYA    %   Convert to decimal digits. Gives a 2-row matrix
  ss     %   Sum of all matrix entries
]        % End
&        % Specify that next function (display) will take only 1 input
         % Implicit display

Mathematica, 49 bytes
If[#<2,#,Tr[Join@@IntegerDigits[#0/@{#-1,#-2}]]]&

Straightforward recursive definition. Gets pretty slow after a while.
Mathematica, 79 71 bytes
If[#<3,Sign@#,(9@@LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ")[[#~Mod~24]]]&

Hardcoding the periodic pattern. Lightning fast and satisfyingly abusive to Mathematica  :) Thanks to JungHwan Min for saving 8 bytes!

For your second code LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ" is 8 bytes shorter than 43626804920391712116157158790~IntegerDigits~18.

you're right! One of these days I'm going to remember LetterNumber....

Python 2, 54 46 bytes
f=lambda n:n>2and~-f(n-1)%9+~-f(n-2)%9+2or n>0

Heavily inspired by @ETHproductions' ES6 answer.
Try it online!

C, 96 bytes
or 61 bytes counting escape codes as 1 byte each
0 indexed. Similar to some of the other answers I am indexing a lookup table of values but I have compressed it into 4 byte chunks. I didn’t bother investigating the mod 24 version because I didn’t think it was as interesting since the others have done so already but let’s face it, C isn’t going to win anyway.
#define a(n) n<3?!!n:2+(15&"\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"[(n-3)/2%12]>>n%2*4)

explanation:
#define a(n)                                                                                // using a preprocessor macro is shorter than defining a function
             n<3?!!n:                                                                            // when n is less than 3 !!n will give the series 0,1,1,1..., otherwise..
                                                                             (n-3)/2%12          // condition the input to correctly index the string...
                           "\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"                     // which has the repeating part of the series encoded into 4 bits each number
                                                                                // these are encoded 2 less than what we want as all numbers in the series after the third are 2 <= a(n>2) <= 17 which conforms to 0 <= a(n>2) - 2 <= 15
                                                                                >>n%2*4  // ensure the data is in the lower 4 bits by shifting it down, n%2 will give either 0 or 1, which is then multiplied by 4
                        15&                                                                      // mask those bits off
                     2+                                                                          // finally, add 2 to correct the numbers pulled from the string

Try it online!

I do count the escape codes as 1 byte each! Great job

Japt, 27 25 bytes
U<2?U:~-ß´U %9+~-ß´U %9+2

Try it online!
Saved 2 bytes thanks to ETHproductions.

Hey, thanks for using Japt :-) You can use ´ in place of -- to save two bytes.

Haskell, 54 bytes
a!b=sum$read.pure<$>([a,b]>>=show)
g=0:scanl(!)1g
(g!!)

Try it online! Usage: (g!!) 12

Python 2, 56 bytes
Simple iterative solution.
a,b=0,1
exec'a,b=b,(a%9or a)+(b%9or b);'*input()
print a

Try it online!
Using (a%9or a)+(b%9or b) actually turned out to be shorter than sum(map(int(`a`+`b`)))!

I think you meansum(map(int,a+b)) (can't figure out how to use ` in comments)

PowerShell, 79 bytes
$b,$c=0,1;for($a=$args[0];$a;$a--){$z=[char[]]"$b$c"-join'+'|iex;$b=$c;$c=$z}$b

Try it online!
Lengthy boring iterative solution that does direct digit-sum calculations each for loop. At the end of the loop, the number we want is in $b, so that's left on the pipeline and output is implicit. Note that if the input is 0, then the loop won't enter since the conditional is false, so $b remains 0.

Batch, 85 bytes
@set/ax=0,y=1
@for /l %%i in (1,1,%1)do @set/az=x-x/10*9+y-y/10*9,x=y,y=z
@echo %x%

I was wondering how I was going to port my JavaScript answer to batch but the clue was in @Dennis's Python solution.

Pyth, 20 bytes
J,01VQ=+JssjRT>2J)@J

A program that takes input of a zero-indexed integer and prints the result.
Test suite (First part for formatting)
How it works
[Explanation coming later]

Ruby, 58 bytes
->n{n<3?n<=>0:"9aa2358dc7a89hhgfda56b8a"[n%24].to_i(18)}

The simple hardcoded solution.

stacked, 40 bytes
{!2:>[:$digitsflatmap sum\last\,]n*last}

This lambda is equivalent to the following lambda:
{n : 2:>[:$digitsflatmap sum\last\,]n*last}

Try it online!

Octave, 148 bytes
function f = fib(n)
  if (n <= 1)
    f = n;
  else
    f = sum(int2str((fib(n - 1)))-48) + sum(int2str((fib(n - 2)))-48);
  endif
endfunction

Welcome to ppcg! Nice first post!

Haskell, 151 bytes
import Numeric
import Data.Char
s i=foldr(\c i->i+digitToInt c)0$showInt i""
d a b=a:d b(s a+s b)
f 0=0
f 1=1
f 2=1
f i=d 2 3!!fromIntegral(mod(i-3)24)

Invoke the function with f 123456789012345678901234567890123456789012345678, for example.
The code works also with very big indices. Because of the implemented modulo 24 functionality it is very fast.
The uncompressed code:
-- FibonacciDigital
-- Gerhard
-- 13 February 2017

module FibonacciDigital () where

import Numeric
import Data.Char

-- sum of digits
digitSum :: Int -> Int
digitSum i = foldr (\c i -> i + digitToInt c) 0 $ showInt i ""

-- fibonacci digital sequence function with arbitrary starting values
fibonacciDigitals :: Int -> Int -> [Int]
fibonacciDigitals a b = a : fibonacciDigitals b (digitSum a + digitSum b)

-- index -> fibonacci digital value
f :: Integer -> Int
f 0 = 0
f 1 = 1
f 2 = 1
f i = fibonacciDigitals 2 3 !! fromIntegral (mod (i-3) 24)

-- End

Vyxal 2, 7 bytes
≬"Ṡ∑k≈Ḟ

Try it Online!

J-uby, 24 bytes
(:digits|:sum)**:++[0,1]

Uses the ** operator which is absent in the latest version of J-uby; I've restored it in the header on ATO.
Attempt This Online!

Perl 5 -MList::Util=sum -p, 53 bytes
($\,$b)=($b|0,sum($b=~/./g,$\=~/./g)||1);$_--&&redo}{

Try it online!

Nice, I've had a little play, but I keep generating the wrong answer so I need to have a look at this later again! I think you can save the |0 using $- though!

Oh, noticed another few bytes too if you combine $\ and $b ($-) into a string and split them both into chars: Try it online!

2 more bytes if you require 1-indexing instead and use while$_--: Try it online!

R, 90 bytes
A horribly long solution, but it's better than the 108 I originally had.  I suspect that there is a lot better way to do this, but I can't see it at the moment.
function(n,x=0:1){repeat`if`(n,{x=c(x,sum(scan(t=gsub('',' ',x))))[-1];n=n-1},break);x[1]}

This is an unnamed function that uses gsub and scan(t= to split the numbers in the vector into digits.  The sum of these is added to the vector while the first item is dropped.  repeat is used to step through the sequence n times and the result is the first item of the vector.

PHP, 80 Bytes
for($r=[0,1];$i<$argn;)$r[]=array_sum(str_split($r[$i].$r[++$i]));echo$r[$argn];

Online Version

Mathematica, 67 bytes
r=IntegerDigits;f@0=0;f@1=1;f[x_]:=f@x=Tr@r@f[x-1]+Tr@r@f[x-2];f@#&

Fig, \$8\log_{256}(96)\approx\$ 6.585 bytes
Gr2'+SxS

Try it online!
Beats Jelly for once.
Gr2'+SxS
G        # Generate an infinite list using the initial terms...
 r2      # [0, 1]
   '     # And the generating function...
     Sx  # Digit sum of first number
       S # Digit sum of second number
    +    # Add the sums

Japt, 11 bytes
@Zo2 xì'x}g

Try it


text:
Copy a file - Windows style
This challenge is inspired by xkcd:

Challenge:
You'll simulate the copying a large file (1 Gigabyte). The transfer rate will vary between 10 kB/second to 100 MB/second.
Your task is to output the time remaining of the file transfer. The output should look like:
Time remaining: 03:12    (meaning it's 3 minutes and 12 seconds left)
Time remaining: 123:12   (meaning it's 2 hours, 3 minutes and 12 seconds left)
Time remaining: 02:03:12 (optional output, meaning the same as above)

Leading zeros need not be displayed for minutes and hours (optional), but must be shown for seconds. Showing the time remaining using only seconds is not OK.
The file transfer:

The transfer rate will start at 10 MB/second.
Every second, there will be a 30% chance that the transfer rate will change
The new transfer rate should be picked randomly (uniform distribution) in the range [10 kB/s, 100 MB/s], in steps of 10 kB/s.

Note: You don't need to actually copy a file.
You may choose to use: 1 GB = 1000 MB, 1 MB = 1000 kB, 1 kB = 1000 B, or 1 GB = 1024 MB, 1 MB = 1024 kB, 1 kB = 1024 B.
Output:

You start at 01:40, not 01:39.
You display the time after the transfer rate changes, but before anything is transferred at that rate
The seconds should be displayed as integers, not decimals. It's optional to round up/down/closest.
You should clear the screen every second, unless that's impossible in your language.
The output should be constant: Time remaining: 00:00 when the file transfer is over.

Example:
I have rounded up all decimal seconds.
Assume the lines below are shown with 1 second in between, and the screen is cleared between each one:
Time remaining: 01:40  (Transfer rate: 10 MB/s)
Time remaining: 01:39      1 GB - 10 MB
Time remaining: 01:38      1 GB - 2*10 MB
Time remaining: 01:37      1 GB - 3*10 MB
Time remaining: 01:28:54   1 GB - 4*10 MB  (TR: 180 kB/s)
Time remaining: 01:28:53   1 GB - 4*10 MB - 180 kB
Time remaining: 01:28:52   1 GB - 4*10 MB - 2*180 kB
Time remaining: 00:13      1 GB - 4*10 MB - 3*180 kB  (TR: 75 MB/s)
Time remaining: 00:12      1 GB - 4*10 MB - 3*180 kB - 75 MB
Time remaining: 00:11      1 GB - 4*10 MB - 3*180 kB - 2*75 MB
Time remaining: 00:10      1 GB - 4*10 MB - 3*180 kB - 3*75 MB
Time remaining: 00:09      1 GB - 4*10 MB - 3*180 kB - 4*75 MB
Time remaining: 00:08      1 GB - 4*10 MB - 3*180 kB - 5*75 MB
Time remaining: 14:09:06   1 GB - 4*10 MB - 3*180 kB - 6*75 MB  (TR: 10 kB/s)
Time remaining: 14:09:05   1 GB - 4*10 MB - 3*180 kB - 6*75 MB - 10 kB
Time remaining: 00:06      1 GB - 4*10 MB - 3*180 kB - 6*75 MB - 20 kB  (TR: 88.110 MB/s)
Time remaining: 00:05
Time remaining: 00:04
Time remaining: 00:03
Time remaining: 00:02
Time remaining: 00:01
Time remaining: 00:00     <- Transfer is finished. Display this.

You should put the XKCD tool-tip text below the image. Save people the time of having to look it up themselves.

@mbomb007, hover the image :)

Should that be, "you start at 1:40 (or 1:42) not 1:39 (or 1:41)"?

Also if we are using the 1024 version, what are the step sizes we should be using?

If hours remaining is zero, can we leave output as 00:00:10 for example?

@JonathanAllan, First comment: yes. Second comment, 10 kB (10240 bytes).

@AdmBorkBork, yes. 00:00:10 is OK.

How can I display "1:40" at the beginning if I do my displays after the rate change?

@Maltysen the rate changes from 0 to 10 Mb/s at t=0. The rate is 10 the first second.

Is erasing the line sufficient?

@JonasWielicki, I don't understand what you mean...? Is erasing a line different from clearing it?

@StewieGriffin You ask for clearing the screen, which is, in terminal emulators, different from erasing the line. The screen may have previous history and the previous prompt on it.

Then yes, erasing the line is ok :-)

"Leading zeros need not be displayed for minutes and hours (optional), but must be shown for seconds." So 2:3:12 is also acceptable? That looks weird.

@StewieGriffin is http://codegolf.stackexchange.com/a/109608/63187 ok?

@ChristopherPeart, I'm afraid not.

Pyth - 70 68 bytes
K^T5J^T3W>KZ%." r3úBTêî¢¤;¥
í".D/KJ60=J?<OT3O^T4J=-KJ.d1.

Try it online without sleeps.

@DigitalTrauma sorry, was using Luis' answer as a guide ._.

@DigitalTrauma fixed.

Lol. When porting from (golfing) language A to (golfing) language B is easier than reading the spec ;-)

@Maltysen Sorry about that! :-)

@DigitalTrauma forgot to take out the sleeps on the updated link. fixed now

Can you give an explanation of what the heck is going on here?

Code doesn't always display 0:00 at the end.

PowerShell, 190 215 187 bytes
($t="Time remaining: ")+"00:01:42";for($f,$r=1gb,10mb;$f-gt0;$f-=$r){if((Random 10)-lt3){$r=(Random -mi 1kb -ma (10mb+1))*10}$t+[Timespan]::FromSeconds([int]($f/$r));sleep 1}$t+"00:00:00"

Try it online! (TIO doesn't support clearing screen between lines)
Sets our initial $file size and our initial transfer $rate to 1gb and 10mb/s, respectively. Then, so long as we still have $file remaining, we loop.
Inside the loop, the if selects a number from 0 to 9 inclusive, and if it's 0, 1, or 2 (i.e., 30% of the time), we change the rate. This picks a random integer between 1kb and 10mb then that's multiplied by 10 to get our step count.
We then leverage the FromSeconds static method from the TimeSpan .NET library to construct the time remaining. The output format of that call exactly matches the challenge requirements, so no need for additional formatting.
(Saved a bunch thanks to @ConnorLSW)

@StewieGriffin TIO has output caching. Select "disable output cache" in the Settings drawer, and it gives different results.

Maybe I'm missing something but the -f operator doesn't appear to do anything. By taking that out and using for loop instead of while, and then changing both instances of get-date to date, I was able to shave off 22 bytes. Try it online!

@briantist TIO requires Get-Date because otherwise it uses the Linux date command, which is different. You can drop it on Windows because PowerShell wraps the Windows date command. But, thanks for the for loop construction!

@AdmBorkBork yeah I noticed that, but in a stock Windows environment it would work. I wonder if it's acceptable to just put nal date get-date in the header in TIO?

@AdmBorkBork and on windows it doesn't wrap the windows date command, it just ignores it because it's not an .exe on windows, so it falls back to the same behavior as random (try the command with get- prepended if all else fails).

@briantist Dennis has updated TIO to also have an alias for date to be Get-Date, so it will now work without the Get-. I'm going to leave this answer as-is so that it's still competing. Thanks!

@AdmBorkBork woah very nice! Thanks Dennis.

tried to cut down on parts of this, pretty sure i'm missing something in the rules though, can someone tell me why $s=1GB;$t=10kb;do{$t=($t,(random -mi 10kb -ma 100mb))[(random 10)-lt3];($a="Time Remaining ")+[Timespan]::FromSeconds(($s-=$t)/$t).ToString("hh\:mm\:ss");sleep 1;cls;}while($s-gt0);$a+"00:00:00" is invalid?

@AdmBorkBork Random 10 includes 0 but not 10, so i use -lt instead of -le should that not give the same effect? is there any issue with [Timespan]::FromSeconds(x).ToString("hh\:mm\:ss")?

@ConnorLSW Don't need the special formatting, as the default output matches the challenge specificiations. I took that and the Random (sorry for my fencepost error) and merged the changes in, saving almost 30 bytes. Thanks!

No worries, glad to get PowerShell higher on the list where possible :)

@AdmBorkBork I don't think the [int] cast is required anymore either.

@ConnorLSW Removing it results in milliseconds being tacked on as decimals.

MATL, 78 bytes
Thanks to @Maltysen and @DigitalTrauma for corrections.
1e5 1e3`XK10&XxyXIy/t0>*12L/'MM:SS'XO'Time remaining: 'whD-r.3<?1e4Yr}K]I0>]xx

Try it at MATL Online! (you may need to press "Run" several times if it doesn't initially work).
The online interpreter times out after 30 seconds. You may want to change 10 (pause time in tenths of second) to something smaller such as 3 in order to increase speed of display
Explanation
1e5                  % Push 1e5: file size in 10-kB units
1e3                  % Push 1e3: initial rate in 10-kB/s units
`                    % Do...while
  XK                 %   Copy current rate into clipboard K (doesn't consume it)
  10&Xx              %   Wait 1 second and clear screen
  y                  %   Duplicate current file size onto the top of the stack
  XI                 %   Copy it to clipboard I (doesn't consume it)
  y                  %   Duplicate current rate onto the top of the stack
  /                  %   Divide. This gives the estimated remaining time in seconds
                     %   It may be negative in the last iteration, because the
                     %   "remaining" file size may have become negative
  t0>*               %   If negative, convert to 0
  12L/               %   Push 86400 and divide, to convert from seconds to days
  'MM:SS'XO          %   Format as a MM:SS string, rounding down
  'Time remaining: ' %   Push this string
  wh                 %   Swap, concatenate
  D                  %   Display
  -                  %   Subtract. This gives the new remaining file size
  r                  %   Push random number uniformly distributed in (0,1)
  .3<                %   Is it less than 0.3?
  ?                  %   If so
    1e4Yr            %     Random integer between 1 and 1e4. This is the new rate
                     %     in 10-kB/s units
  }                  %   Else
    K                %     Push rate that was copied into clipboard K
  ]                  %   End
  I                  %   Push previous remaining file size from clipboard I
  0>                 %   Is it positive?
]                    % End. If top of the stack is true: next iteration
xx                   % Delete the two numbers that are on the stack

I don't understand MATL, but it looks to me as if you're always getting a new rate instead of only 30% of the time from your explanation.

@Maltysen Corrected now. Thanks for the heads-up!

Ruby, 116 110 bytes
Try it online, except repl.it reads \r as a newline and also can't use $><< so it's replaced with its 5-byte equivalent, print.
Shoutout to JonasWielicki for the initial idea of using \r to reset the line.
f=1e5;r=1e3;(k=f/r=rand<0.3?1+rand(1e4):r;$><<"\rTime remaining: %02d:%02d"%[k/60,k%60];f-=r;sleep 1)while f>0

This version is untested on Windows, but works on Unix.

Bash + common utils, 117
Straightforward implementation.  A few bytes saved by dividing out by 10000:
for((b=10**5,r=1000;b>0;r=RANDOM%10<3?RANDOM%10000+1:r,b-=r));{
clear
date -ud@$[b/r] "+Time remaining: %T"
sleep 1
}

Try it online. Using sleep 0 on the TIO so you don't have to wait.  clear doesn't work on TIO.

JavaScript (ES6), 162 bytes
Shows minutes as is with padded seconds (floored)
E.g., 123:45

t=1e5
s=1e3
setInterval(c=>c.log(`Time remaining: ${c.clear(d=t/s),d/60|0}:`+`0${t-=s>t?t:s,r=Math.random,s=r()<0.3?1+r()*1e4|0:s,d%60|0}`.slice(-2)),1e3,console)

I think you forgot to shorten console.clear to c.clear ;-) That's a great idea, BTW

@ETHproductions Ooooops! Thanks :)

You could get this down to 154 bytes by adding HTML - <input id=o> - and making a couple of other adjustments: t=1e5;i=s=1e3;setInterval(_=>o.value=\Time remaining: ${(d=t/s)/60|0}:`+`0${t-=s>t?t:s,r=Math.random(),s=r<.3?1+r*1e4|0:s,d%60|0}`.slice(-2),i)`

Python 3.6 (212 203 bytes)
from random import*
import time,datetime
r=1e7
d=1e9
while 1:
 print(f"\x1b[KTime remaining: {datetime.timedelta(seconds=d//r)}",end="\r");d=max(0,d-r);time.sleep(1)
 if random()>.7:r=randint(1,1e4)*1e4

Pretty straightforward, I think. Erases the line using ANSI escape sequence and K command.

Saved 9 bytes thanks to @ValueInk

Skip a space in your first line with from random import*. d//r is shorter than int(d/r). Also, might as well go with r=1e7;d=1e9 from the start.

@ValueInk Right, didn’t think of 1eX for r and d because I wanted them to be integers; when I shortened the randint line, I forgot about that ... :)

C 184 171 155 bytes
f(){i,j=0,r=1e7;for(i=1e9;i>0;i-=r){j=i/r;printf("Time remaining: %02d:%02d:%02d\r",j/3600,(j/60)%60,j%60);sleep(1);if(rand()%10<3)r=(rand()%10000)*1e4;}}

I hope this qualifies.
Ungolfed version:
void f()
{
    int j=0;
    float rate=1e7;
    for(int size=1e9;i>0; size-=rate)
    {
       j=size/rate;
       printf("Time remaining: %02d:%02d:%02d\r",j/3600,(j/60)%60,j%60);
       sleep(1);

       if(rand()%10<3)
          rate=(rand()%10000)*1e4;

   }

}

Explanation: In the golfed version i corresponds to size in ungolfed version and r is rate in ungolfed version. j stores the time remaining in seconds.

I have 10^9 bytes to copy. I start copying at the rate of 10 Megabytes/second,
If the probablity is less than 30% , change the rate (from 10 kilobytes to 100 Megabytes per second)

@ValueInk Thanks for saving 13 bytes.
@nmjcman101 Thanks for saving 16 bytes.

This doesn't look like it actually does what the challenge says. Can you explain how it works?

It just simulates time output, i have not figured out how to do the data transfer part. Guess I'm gonna put this on hold until then.

You don't change the rate after 3 iterations. It has a 30% chance of changing. So you probably want to do something similar to the following: if(rand()%10<3)r=(rand()%10000+1)*1e4; (Especially since the minimum rate is 10 kB/s, not 1MB/s like your solution is saying, and the rate chance should be a somewhat uniform distribution.)

@ValueInk Thanks so much. :) Updated. Gets the work done! I did not know how exactly to simulate the 30% probability part. So much clearer now.

you can golf j/3600,(j/60)%60,j%60 (21)  with s=60; and  j/s/s,j/s%s,j%s (20)

Additionally, you can get rid of system("clear"); by putting a \r at the end of your printf and removing the \n at the beginning.
You can also put the i-=r inside of the for loop, after the second ;

@nmjcman101 I have done carriage return in one or some of my other solutions as well, but this time somehow on my terminal, putting \r did not work, I could not see anything.

Batch, 193 bytes
@set/ap=10000,s=p*10,r=p/10
:l
@set/at=s/r,m=t/60,n=t%%60+100,s-=r
@cls
@echo Time remaining: %m%:%n:~1%
@timeout/t>nul 1
@if %random:~-1% lss 3 set/ar=%random%%%p+1
@if %t% gtr 0 goto l

Note: Slight bias towards rates of 27.68 MB/s or less.

source: Stack Exchange

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

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

sort: votes


text:
Big code... for you!
At the opening scene of the Dark Knight rises, there is a rather awkward dialogue between a CIA agent and the villain Bane.

CIA agent: “If I pull that [mask] off, will you die?”
Bane: “It would be extremely painful…”
CIA agent: “You’re a big guy.”
Bane: “…for you.”

It’s unsure if Bane intends to say “painful for you” or “big guy for you”. Let’s settle this problem once for all through code golfing!
Challenge
Your task is write a program that reorders the above dialogue depending on an integer given as input.
CIA agent dialogue words are:
If I pull that off will you die? You're a big guy.
Bane’s dialogue words are:
It would be extremely painful... for you!
Please note that die?, You’re, painful... and you! are considered as single words.

Given an integer n as input, convert it to binary
Reading the binary digits from left to right, output the next word from CIA agent dialogue if the digit is 1, and the next word from Bane dialogue if the digit is 0. The words should be separated by a space.
When the speaker changes, add a line feed. Also, prefix each dialogue line with the speaker name (BANE:  or CIA: ).

You can assume that the input always starts with a 1 in binary form, and has 12 ones and 7 zeroes.
Example
522300

Converted to binary: 1111111100000111100

The number starts with 8 ones, so we output the 8 first words from CIA’s agent dialogue, and prefix them with CIA:
CIA: If I pull that off will you die?

Then we got 5 zeroes, so we get the 5 first words from Bane’s dialogue:
BANE: It would be extremely painful...

Then there are 4 ones, so we output the 4 next CIA words:
CIA: You’re a big guy.

Then 2 zeroes:
BANE: for you!

Final result:
CIA: If I pull that off will you die?
BANE: It would be extremely painful...
CIA: You’re a big guy.
BANE: for you!

More test cases:
494542
CIA: If I pull that
BANE: It would be
CIA: off
BANE: extremely
CIA: will you die? You're
BANE: painful... for
CIA: a big guy.
BANE: you!

326711
CIA: If
BANE: It would
CIA: I pull that off will you
BANE: be extremely painful... for
CIA: die? You're
BANE: you!
CIA: a big guy.

Can each line end in a space?

@xnor Yes, that's ok.

"that" and "it" as first word of Bane's speech don't line up in test cases/quote

@Mistah fixed to "it", thanks!

Is a leading newline allowed?

@user63956 no, it should start with the CIA agent sentence. newline or no newline is allowed at the end.

Is it just me or someone read the dialogue in bane's voice.

"It’s unsure if Bane intends to say “painful for you” or “big guy for you”"
Actually... https://i.imgur.com/ZRA76Af.jpg

@SomeGuy Maybe you're unsure, but it's pretty clear that "painful for you" is most likely the intended meaning. "Big guy for you" hardly makes sense grammatically.

When I  watched the film, I didn't put ellipses after Bane's "it would be extremely painful." Neither does the script. So I wonder, why did you?

@theonlygusti I took the dialogue from knowyourmeme.com - there is a whole article on this important topic :-)

Pyth - 138 bytes
I should look into compressing the movie script.
K_cc"guy big a You're die? you will off that pull I If you! for painful... extremely be would That"d12jmj;++@c"BANECIA"4ed\:m.)@Kedhdr8jQ2

Test Suite.

JavaScript (ES6), 203 201 bytes
Edit: saved 2 bytes by shamelessly borrowing the trim() idea from ETHproductions answer
n=>"If I pull that off will you die? You're a big guy. It would be extremely painful... for you!".split` `.map((_,i,a)=>[`
BANE: `,`
CIA: `,' '][j^(j=n>>18-i&1)?j:2]+a[k[j]++],k=[j=12,0]).join``.trim()

Test cases

let f =

n=>"If I pull that off will you die? You're a big guy. It would be extremely painful... for you!".split` `.map((_,i,a)=>[`
BANE: `,`
CIA: `,' '][j^(j=n>>18-i&1)?j:2]+a[k[j]++],k=[j=12,0]).join``.trim()

console.log(f(522300))
console.log(f(494542))
console.log(f(326711))

JavaScript (ES6), 209 202 201 bytes
(n,a="It would be extremely painful... for you! If I pull that off will you die? You're a big guy.".split` `,b=[6,18])=>(F=(s,p=n%2)=>n?F((p^(n>>=1)%2?p?`
CIA: `:`
BANE: `:` `)+a[b[p]--]+s):s.trim())``

Old approach:
(n,a="If I pull that off will you die? You're a big guy. It would be extremely painful... for you!".split` `,b=[12,0])=>(F=p=>p^n%2?F(n%2)+(p?`
CIA:`:`
BANE:`):n?F(p,n>>=1)+" "+a[b[p]++]:``)(n%2).trim()

Test snippet

f=(n,a="It would be extremely painful... for you! If I pull that off will you die? You're a big guy.".split` `,b=[6,18])=>(F=(s,p=n%2)=>n?F((p^(n>>=1)%2?p?`
CIA: `:`
BANE: `:` `)+a[b[p]--]+s):s.trim())``

console.log(f(522300))
console.log(f(494542))
console.log(f(326711))

I'm shamelessly borrowing your trim() idea. I was sure there was something better than slice(1) but couldn't figure it out.

@Arnauld Fine with me, now we're all tied up. I bet there's a way to do it in under 200 :-)

C++11 (GCC), 298 293 bytes
#include<sstream>
[](int i){std::stringstream b("It would be extremely painful... for you!"),c("If I pull that off will you die? You're a big guy.");std::string s,w;int n=0,t=i,p;while(t/=2)n++;for(;n>=0;p=t)((t=i>>n&1)?c:b)>>w,s+=p^t?t?"CIA: ":"BANE: ":" ",s+=t^(i>>--n)&1?w+"\n":w;return s;}

A lambda function that takes an integer and returns the dialogue as a std::string. You can see it in action here.
Ungolfed version (with some explanation):
#include<sstream>

[](int i) {
    std::stringstream bane("It would be extremely painful... for you!"),
                      cia("If I pull that off will you die? You're a big guy.");
    std::string s, w;
    int n = 0, t = i, p;
    // Find the position of the most significant bit (n)
    while (t/=2) n++;

    for (; n>=0; p=t) {
        t = i>>n&1; // Current bit
        // Append the speaker name if the previous bit was different
        if (t != p) s += (t ? "CIA: " : "BANE: ");
        else s += " ";

        // Read the next word from one of the streams
        if (t) cia >> w;
        else bane >> w;

        s += w;

        if (t != ((i>>--n)&1)) // Append a newline if the next bit is different
            s += "\n";
    }

    return s;
}

JavaScript (ES6), 252 227 226 bytes
n=>[...n.toString(2,b="If I pull that off will you die? You're a big guy.".split` `,c="It would be extremely painful... for you!".split` `)].map((a,i,j)=>(a!=j[i-1]?+a?i?`
CIA: `:`CIA: `:`
BANE: `:``)+(+a?b:c).shift()).join` `

Usage
f=n=>[...n.toString(2,b="If I pull that off will you die? You're a big guy.".split` `,c="It would be extremely painful... for you!".split` `)].map((a,i,j)=>(a!=j[i-1]?+a?i?`
CIA: `:`CIA: `:`
BANE: `:``)+(+a?b:c).shift()).join` `
f(522300)

Notes
This is golfing-in-progress, I think I can still shave off some bytes, but feel free to leave suggestions in the comments.

Python 3.6, 232 bytes
from itertools import*
c="you! for painful... extremely be would It".split(),"guy. big a You're die? you will off that pull I If".split()
for n,r in groupby(f'{int(input()):b}',int):
 print("BCAINAE::"[n::2],*[c[n].pop()for _ in r])

Edit, equivalently:
from itertools import*
c="It would be extremely painful... for you!".split(),"_ If I pull that off will you die? You're a big guy.".split()
for n,r in groupby(map(int,f'{int(input()):b}')):
 print("BCAINAE::"[n::2],*map(c[n].pop,r))

Japt, 121 bytes
A=[`It Ùd ¼ extÚ+ pafª... f y!`¸`If I pªl È     f Øi y ¹e? Y' a big guy.`¸]¢®^T?["
BANE:""
CIA:"]gT=Z :P +S+AgZ vÃx

Contains many unprintables, so you'd just be better off testing it online.

Perl 6, 211 bytes
{.put for map |*,zip map {.[0]X .[1].rotor: .[2..*]},zip <CIA: BANE:>,(<If I pull that off will you die? You're a big guy.>,<It would be extremely painful... for you!>),|(.base(2)~~m:g/(.)$0*/)».chars.rotor(2)}

C#, 398 390 385 396 389 bytes
class P{static void Main(string[] a){string s="2"+System.Convert.ToString(int.Parse(a[0]),2),e="CIA: ",r="BANE: ",o="";int k=0,l=0,i=1;string[] c="If I pull that off will you die? You're a big guy.".Split(' '),b="It would be extremely painful... for you!".Split(' ');for(;i<s.Length;i++)o+=(s[i-1]==s[i]?" ":(i<2?"":"\n")+(s[i]>'0'?e:r))+(s[i]>'0'?c[k++]:b[l++]);System.Console.Write(o);}}

Launch with input number as parameter.
Ungolfed:
class P
{
    static void Main(string[] a)
    {
        string s = "2" + System.Convert.ToString(int.Parse(a[0]), 2), e = "CIA: ", r = "BANE: ", o = "";
        int k = 0, l = 0, i = 1;

        string[] c = "If I pull that off will you die? You're a big guy.".Split(' '), b = "It would be extremely painful... for you!".Split(' ');
        for (; i < s.Length; i++)
            o += (s[i - 1] == s[i] ? " " : (i<2?"":"\n") + (s[i] > '0' ? e : r))
                + (s[i] > '0' ? c[k++] : b[l++]);
        System.Console.Write(o);
    }
}

Back to 396 bytes because I didn't notice "no newline at the begining" rule.

Sadly, s.Replace("1",c[k++]).Replace("0",b[l++]) doesn't replace with corresponding words. It seems, C# gets replacing string once and slaps it in places.

Ruby, 204+1 = 205 bytes
Requires the -n flag.
d=[%w"It would be extremely painful... for you!",%w"If I pull that off will you die? You're a big guy."]
n=%w"BANE CIA"
("%b"%$_).scan(/((.)\2*)/).map{|i,b|puts n[k=b.to_i]+': '+d[k].slice!(0,i.size)*' '}

PHP, 198 bytes
while($i++<19)echo($t-$s=1&$argv[1]>>19-$i)?"
"[$i<2].($s?CIA:BANE).": ":" ",explode(0,"It0would0be0extremely0painful...0for0you!0If0I0pull0that0off0will0you0die?0You're0a0big0guy.")[$$s+++7*$t=$s];

Clojure, 401 bytes
(require '[clojure.string :as s])(defn f[n](let[c(map #(-(int %) 48)(Integer/toString n 2))p[(s/split"It would be extremely painful... for you!"#" ")(s/split"If I pull that off will you die? You're a big guy."#" ")]a["BANE" "CIA"]](loop[i[0 0] g"" d c q 2](if(<(count d)1)g(let[b(first d)j(i b)](recur(assoc i b (inc j))(str g(if(= b q)" "(str(when(not= 2 q)"\n")(a b)": "))((p b) j))(rest d) b))))))

Invocation:
(f 522300)

Ungolfed
(require '[clojure.string :as s])
(defn dialogue[num]
    (let [dacode (map #(- (int %) 48) (Integer/toString num 2))
          phrases [(s/split"It would be extremely painful... for you!"#" ")(s/split"If I pull that off will you die? You're a big guy."#" ")]
      actors ["BANE" "CIA"]]
      (loop [idxs [0 0] finaldial "" code dacode prevbit 2]
        (if (< (count code) 1) finaldial
            (let [bit (first code) idx (idxs bit)]
              (recur (assoc idxs bit (inc idx)) (str finaldial (if (= bit prevbit) " " (str (when (not= 2 prevbit) "\n") (actors bit) ": ")) ((phrases bit) idx)) (rest code) bit))))))

Perl, 205 bytes
@t=([qw/It would be extremely painful... for you!/],[qw/If I pull that off will you die? You're a big guy./]);$_=sprintf'%b',$0;print$n?'BANE':'CIA',": @{[splice$t[$n=1-$n],0,length$&]}"while s/(.)\1*//;

Put that into a file named 494542 and run like this:
perl -lX 494542

Tested on perl v5.22

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


text:
Golomb's wobbly sequence
OEIS has a variation (A111439) on Golomb's sequence. As in Golomb's sequence, A(n) describes how often n appears in the sequence. But in addition, no two consecutive numbers may be identical. While building up the sequence, A(n) is always chosen as the smallest positive integer that doesn't violate these two properties. Due to disallowed consecutive identical numbers, the series wobbles slightly up and down as it grows. Here are the first 100 terms:
1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9,
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12,
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15,
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18,
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

The full list of the first 10,000 numbers can be found on OEIS.
The challenge is to write a program or function which computes A(n), given n. n is 1-based to ensure that the self-describing property works.
Rules
You may write a program or a function and use any of the our standard methods of receiving input and providing output.
You may use any programming language, but note that these loopholes are forbidden by default.
This is code-golf, so the shortest valid answer – measured in bytes – wins.
Test Cases
n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Related.

I was curious so I graphed it. Neato.

@EngineerToast The graph is also on OEIS. I was looking into how long the "runs" are you see in your graph and that gets really weird. (This graph shows how often N appears after the last occurrence of N-1 which measures the number of wobbles down to N.)

Mathematica, 69 68 bytes
Thanks to Martin Ender for finding an extra –1 byte for me!
Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Unnamed function taking a positive integer n as input and returning a positive integer. We construct the entire list of the first n elements of this sequence, then take the Last element. The list is constructed by starting with the empty list {} and operating on it with a function n times in a row (via Nest).
The function in question is {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, which takes a partial list of sequence values (essentially ##&@@#) and appends the next value to it. The next value is computed by starting with x=1, then repeatedly replacing x by x+1 as long as the condition x==Last@#||#~Count~x==#[[x]] is met—in other words, if either x is the previous element, or else x is already in the list the correct number of times. This function spits some errors, since (for example) we shouldn't be calling the xth element of the initial list {}; however, the values are all correct.

Haskell, 67 bytes
f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Defines a function f. Try it online! It's very slow, computing f 15 times out on TIO.
Explanation
Just going with the definition: at every stage, choose the minimal positive number n that satisfies the constraints (not equal to previous entry, and has not occurred f n times yet).
f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Python 2, 99 86 bytes
Thanks to @Dennis for several improvements totaling 13 bytes!
s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

The program proceeds pretty naively: It keeps track of the list of values it's determined so far, and looks to append the next value.  It tries to append a 1 to the end of the list if it can; if not, then it tries a 2 and so on until something is allowed.
Now, we start by seeding the results for 1,2,3 to be 1,2,3.  This is done to avoid any problems with the list of already-computed values being too short: I conjecture that if n is at least 4 then a(n) is strictly less than n.  (In this program, s[n] is equal to a(n).  Our list actually is initialized to be [0,1,2,3] because lists are 0-indexed in Python.  So for instance a(1)=s[1]=1, and a(2)=s[2]=2.)
So, let's say we're trying to determine s[m], meaning that our list already includes s[0], s[1], ..., s[m-1].  We'll start at t=1 and try to set s[m]=1.  When that doesn't work, we go to t=2 and try to set s[m]=2.  Each time we increment t, we check whether s.count(t)==s[t]...but the right-hand side won't produce an error so long as we never have to go as high as t=m.  The conjecture says that we never have to, since the first value we compute is actually s[4].
This implementation computes 3 more values of the sequence than it needs to.  For example if n is 8, it'll compute up through s[11] before it returns the value of s[8].
I'd be happy to see a proof of the conjecture.  I believe it can be proven by (strong?) induction.
Edit: Here is a proof of the conjecture.  We actually prove a slightly stronger form of the statement, since it involves no extra work.
Theorem: For all n greater than or equal to 4, the term a(n) is less than or equal to (n-2).
Proof (by Strong Induction): (Base n=4): The statement is true for n=4, since a(4) = 2 = 4-2.
Now assume a(k) is less than or equal to k-2 for all k from 4 through n, inclusive (and assume n is at least 4).  In particular, this means that all previous terms of the sequence were at most (n-2).  We need to show that a(n+1) will be at most (n-1).  Now, by definition, a(n) is the smallest positive integer that doesn't violate any of the conditions, so we just need to show that the value (n-1) will not violate any of the conditions.
The value (n-1) will not violate the "no consecutive repeats" condition, because by the induction hypothesis the previous entry was at most (n-2).  And it won't violate the "a(m) is the number of times m appears" condition, unless (n-1) had already been reached a(n-1) times.  But by the strong induction assumption, (n-1) had previously been reached 0 times, and a(n-1) is not equal to 0 since a(m) is positive for all m.
Therefore a(n+1) is less than or equal to n-1 = (n+1)-2, as desired. QED.

Jelly, 17 bytes
Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

The last three test cases are too much for TIO. I've verified 1000 and 1257 locally.
Try it online! or verify the first 100 terms.
How it works
⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.

Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Python 2, 77 74 bytes
f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

This is a recursive implementation of @mathmandan's algorithm.
The implementation is O(insane): input 9 takes 2 seconds locally, input 10 52 seconds, and input 11 17 minutes and 28 seconds. However, if declared as a regular function rather than a lambda, memoization can be used to verify the test cases.
Try it online!
Note that even with memoization, TIO cannot compute f(1257) or f(10000) (both verified locally).

05AB1E, 32 31 bytes
XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Try it online!
Explanation
XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list
                                   and output last value in list and end of program

We are technically in loop G when we add N to global list, but all loops in 05AB1E use the same variable N as index, so the inner loop [...] has overwritten the N of G meaning we can add it outside the loop.
Issues with nested loops and conditionals prevents us from doing this inside the loop.

Befunge, 141 136 bytes
<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Try it online!
Because of Befunge's memory limitations, it's not really practical to keep track of all previous entries entries in the sequence, so this solution uses an algorithm with a lower memory footprint which calculates the values more directly.
That said, we're still limited by the cell size, which in the Befunge-93 reference interpreter is a signed 8-bit value, so the highest supported even number in the sequence is A(1876) = 126, and the highest supported odd number is A(1915) = 127.
If you want to test larger values, you'll need to use an interpreter with a larger cell size. That should include most Befunge-98 implementations (Try it online!).

Husk, 18 bytes
!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3

Try it online!
I decided to spare my soul and do it without combinators, and it's still the same size with them. Fun sequence.
just need to save a single byte...
Explanation
!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3
                ḣ3 start with [1,2,3]
 ¡λ            )   apply the following repeatedly:
             ŀΘ    prepend zero, get range [1..length+1]
                   → [1,2,3,4]
       f§          filter out values where:
           #¹      frequency in sequence
         <         is not less than
          ! ¹      projected frequency in sequence
                   → [2,3]
   ḟ               find the first element
    ≠→¹            which isnt equal to the most recent element
                   → 2
!                  take the nth element of this infinite list

Python 2, 117 bytes
Meh. Not that short. The simple iterative solution.
L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Try it online
Here's a really bad attempt at a recursive solution (129 bytes):
def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)

Fixed. I thought I could use -1 instead of n-1 to save a byte, I guess not.


text:
Detect Failing Castles
One of the interesting aspects of gravity is that, as far as I'm aware, you can't just have stuff floating in midair.
However, it seems not everyone at the Association of Random Castle Builders is aware of this fact, leading to castles such as this one:
                      #
                      #
    #  #      #  #   ###
    ####      ####   # #
    #### #  # ####   ###
    ##############   ###
    ######  ######   ###
    #####    #####   ###
                     ###
``````````````````````````````

and this one:
                                       # # #    # # #
                                       ##############
                                       ###  ####  ###
    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #
    ####      ####      ####      #### ############## ####      ####      ####      ####
    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####
    ####################################################################################
    ######  ########  ########  ########  ########  ########  ########  ########  ######
    ###################################    ######    ###################################
    ###################################    ######    ###################################
                                       ##
                                         ##
                                           ##
                                             ##
                                               ##
````````````````````````````````````````````````````````````````````````````````````````````

and even this one:
       ##########
   ####   #      ###
#######################
            #
              #
                #
                  #
                    #  # # #
                  #   #  ###
                   #   # ###
                # # #  #  ##
                # # ##   ###
                 #  #  #####
                   #   #####
                  # #  #####
                       #####
                       ## ##
                       #####
                       #####
                       ## ##
                       ## ##
````````````````````````````````````````````

Challenge
For a valid castle, all blocks will be connected to the ground either directly or indirectly. Your program or function will be given a castle such as the ones above as input, and your program must return a truthy or falsy value reflecting whether the castle is valid or not.
Rules

Input is given as a string.
All valid castles rest on a surface, ````````. (If the input string does not contain a surface, the castle is invalid.)
You can assume all input will satisfy these criteria:

The surface will always be flat.
The surface will always be at least as wide as the castle, so there will be no blocks to the left or right of the ground.
The input will never have # below the surface.
Input will only contain characters given in this challenge. (#, `, space or newline.)
You may assume the input will always contain at least one character.

Blocks are connected if they are either horizontally or vertically adjacent. Diagonal does not count!

Connected: #	or	###
Not connected: #      or	# #	or	 #                  		##

Castles must exist to be valid. (In other words, inputs without any # must give a falsy value.)
Input will only contain characters given in this challenge. (#, `, space or newline.)
You may assume the input will always contain at least one character.
Standard I/O and loophole rules apply.

Test cases
Falsy
All the examples given above.
#  #      #  #####      ######## #  # ########################  ###########    ##### (No ground.)
# ###      ######## #  # ########################  ###########    #####`````````````` (Topmost block is not connected either horizontally or vertically.)
   ``` (No castle.)                                     # # #    # # #                                        ##############                                     ##### ## #####  #  #      #  #      #  #      #  # #### #  # #### #  #      #  #      #  #      #  #  ####      ####      ####      ####  ##  ####  ##  ####      ####      ####      ####  #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # #### #  # ####  ####################################################################################  ######  ########  ########  ########  ########  ########  ########  ########  ######  ###################################    ######    ###################################  ###################################    ######    ###################################````````````````````````````````````````````````````````````````````````````````````````(Central tower isn't connected to the rest of the castle because there are no horizontally or vertically adjacent blocks connecting it.)    (No castle.) (No castle, just a single newline character.)
# ##``````` (Rightmost block is not connected either horizontally or vertically.)
   ``` (No castle.)
Truthy
#`#  #      #  #####      ######## #  # ########################  ###########    #####``````````````                      #                      #    #  #      #  #   ###    ####      ####   # #    #### #  # ####   ###    ##############   ###    ######  ######   ###    #####    #####   ###    #####    #####   ###``````````````````````````````                                       # # #    # # #                                          ##############                                       ###  ####  ###    #  #      #  #      #  #      #  # ###  ####  ### #  #      #  #      #  #      #  #    ####      ####      ####      #### ############## ####      ####      ####      ####    #### #  # #### #  # #### #  # #### ## ######## ## #### #  # #### #  # #### #  # ####    ####################################################################################    ######  ########  ########  ########  ########  ########  ########  ########  ######    ###################################    ######    ###################################    ###################################    ######    ###################################````````````````````````````````````````````````````````````````````````````````````````````                      ####  ###                      #  #### ###                      #         ###                      #           ##                      #                     ###                    #####                   #######                  #########                 ##### #####                #####   #####               ######   ######              #################              # ############# #                #############                #############                #############                ###### ######                ###### ######                #############                #############                #############                #############                ###### ######                ###### ######                #############                #############                #############                #############                ###### ######                ###### ######                #############                #############                #############                #############                #############                #####   #####                #####   #####                 #####   #####            `````````````````````                                                                                ####                                           #####                                          ######                                           ####                                            ####                                           #####                                          ########                                       ##########                                      ##########                                     ###########                                    ############                                  ##############   #####                       ################   ###########                #################    ###########################################      ########################################         #####################################            ##################################                 ############################                        ###################                 ``````````````````````````````````````````````````
Good luck!

Can we assume all lines of the input will be the same length (i.e. filled up with spaces)?

@smls No, you cannot assume input will be padded.

Some more test-cases that might be good to add: 1) Non-flat surface. 2) Too short surface. 3) Castle not connected to the surface. 4) Block connected to nothing but a surface.

@smls Re #1 and #2: I actually meant to specify that submissions don't have to handle that, but I now see that's not how I wrote it down. Since there are no solutions posted yet that handle these things, I'll update the question so that it's clear you don't have to handle these. Re #3: I can't really think of a situation where code would correctly handle Falsy test case 2, 4 and 6 and yet fail to detect a situation where there are no blocks at all connected to the ground. Re #4: I'm not sure what you mean by that. Isn't that already handled by Truthy test case number 1?

Related.

@user2428118: You're right, they're already implicitly handled.

How about an input where the castle is connected to the ground from the bottom (falsy I assume).

@feersum I hadn't thought of that yet... I don't want to render the existing answers invalid, so I'll specify that case doesn't have to be handled.

@user2428118 When you say input cannot be padded, do you mean right-padded, or on both sides? It seems like the string would have to be left-padd to align properly, but maybe I don't understand the input format.

@Brian You've misread my comment. I said "you cannot assume input will be padded", in other words: input may or may not have padding and your code should work regardless of whether the input is padded or not.

@user2428118 So in the banana example, what would the input string look like? How do we know that the stem is on the right side of the banana?

@BrianJ The original comment by smls asked if submissions can assume that all lines are of equal length, so by adding extra spaces to the right to make sure no line is shorter or longer than the others. Which I choose not to allow. Anyway, here is the banana with newlines replaced by \n. I hope it's clear now?

@user2428118 That pastebin makes it very clear to me. I was trying to ask if it would look like that when I said left-padding. Sorry for choosing confusing terminology.

A banana castle? BEST CASTLE EVER

Now I need to write an AHK script that opens MSPaint and uses the Paintcan tool.

As usual, left-pad causes trouble.

Snails, 21 18 bytes
-3 bytes due to additional input constraints edited into challenge.
!{t=\#!(\#o`+\`}\#

Unfortunately the time complexity is factorial, so most of the inputs aren't runnable.
Outputs 0 for falsy cases, and the number of # for truthy cases.
                 ,,
!{ t             ,, Assert that nowhere in the grid,
    =\#          ,, there is a '#'
    !(           ,, such that there does not exist
        (\# o)+  ,, an orthogonally connected path of '#'
        \`       ,, ending at a '`'
    )            ,,
}                ,,
\#               ,, Match '#' at starting position

This doesn't recognise the example you posted on Zgarb's answer as a castle. I don't see anything in the rules that says these shouldn't be detected as castles? The rules only say that it's a castle if each # is connected to the ground.

@Zgarb No, there's a bug in the explanation -- + is actually 1 or more times, not 0. it's going to look different anyway after allowing disconnected castles.

Octave,  53 51 bytes
@(s)([~,n]=bwlabel(s>32,4))|n==1&&nnz(diff(+s)==61)

Try It Online!
*Since op dropped requirement to check for empty input answer reverted to my first edit.
Explanation:
nnz(s)                       check for empty input
([~,n]=bwlabel(s~=' ',4))    label nonempty regions and count number of labels

n==1                         check if number of labels is 1.

nnz(diff(+s)==61)            check if blocks connected to the surface

Grime, 29 bytes
C=\`|\#&<0C>oX
e`\#&C!v#!&\##

Try it online!
Most test cases time out on TIO.
Replace the <0C> with <0CoF> to make it a little faster.
Explanation
I'm checking that from every # there exists a path to a `, and that there exists at least one #.
I recently added rotation commands to Grime, which make this challenge much easier.
C=\`|\#&<0C>oX  First line:
C=               Define nonterminal C as
  \`             the literal `
    |            or
     \#          the literal #
       &<  >     which is contained in a larger rectangle
         0C      containing said literal adjacent to a match of C
            oX   rotated by any multiple of 90 degrees.
e`\#&C!v#!&\##  Second line:
e`               Match entire input against this pattern:
         !       does not
       v#        contain
  \#             the literal #
    &C!          which is not a match of C,
          &      and
             #   contains
           \#    the literal #.

JavaScript (ES6), 197 196 bytes
f=(s,l=Math.max(...s.split`\n`.map(t=>t.length)),t=s.replace(/^.*/g,t=>t+' '.repeat(l-t.length)),u=t.replace(eval('/(#|`)([^]{'+l+'})?(?!\\1)[#`]/g'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,l,u)

Where \n represents the literal newline character. Tries to remove all #s one at a time by finding one adjacent to a ` and changing it to a `. Returns true if there was at least one # originally but there were all removed. Version that requires padded input for 118 117 bytes:
f=(s,t=s,u=t.replace(eval('/(#|`)([^]{'+s.search`\n`+'})?(?!\\1)[#`]/'),'`$2`'))=>t==u?/#/.test(s)>/#/.test(t):f(s,u)

Perl 6, 180 bytes
{?/\#/&&?all map ->\c{my \b=[map {[$^a.comb]},.lines];sub f(\y,\x){with b[y;x] ->$_ {b[y;x]=0;/\#/??f(y+(1|-1),x)|f(y,x+(1|-1))!!/\`/??1!!|()}}(|c)},map {|($++X ^$^a.comb)},.lines}

Checks if the input contains at least one #, and if every # can find a path to a `.
Rather inefficient, because the pathfinding is brute-forced using a recursive function that always visits all other # of the same connected region (i.e. doesn't short-circuit).
Uses some unholy interaction between Junction operators and slipping, to ensure that the path test is skipped for space characters without requiring a separate check for that outside of the pathfinding function.

Python 3, 214 206 bytes
def f(s):
 C=s.split('\n');n=max(map(len,C));o=[''];C=[*''.join(t.ljust(n)for t in C+o)]
 while C>o:o=C;C=['`'if z>' 'and'`'in{C[i+y]for y in(1,-1,n,-n)}else z for i,z in enumerate(C)]
 return'#'in{*s}-{*C}

Try it online!
The first line here is devoted to padding all the lines to the same length: we split the string (s.split('\n') is one char shorter than s.splitlines()), find the maximum length of a line, and assign to C a flattened list of all the characters after padding each line. (The newlines are gone.)
Then we make a list where each non-space character adjacent to at least one backtick is replaced by a backtick, and continue until no change happened (when the old list o is equal to C. We can compare with C>o instead of C!=o because replacing # (ASCII 35) with ` (ASCII 96) can only increase the list's lexicographical ordering.)
If no # remains, and at least one was present initially, the castle is valid.

Saved eight bytes checking for # in the set difference, rather than '#'in s and'#'not in C


text:
String truncation/summarization
Not entirely sure if this one or a similar challenge has already been posted, but here it goes anyway.
Write a program that takes a string as input and writes its trucated/summarized output form such that a specific sep (separator) is placed in the middle, removing the necessary characters of the original string so that the length of output equals a given width.
Rules

Input is a string, a width and a sep (separator);
if len(string) <= width: output = string, meaning that the output is the string itself unchanged;
if width <= len(sep): output = sep, meaning that the output is the separator only;
len(output) must be equal to width, with the exception of the previous case;
The excess character in case of uneven number of remaining characters for each half of the string can be placed on the left or right halve;
Standard code-golf challenge with the smallest program to win.

Examples
Format: "string" [length(string)] --> "output" [length(ouput) / width] with sep equal to _(...)_ (_ are whitespaces).
"xtlgxbdwytxcjacu" [16] --> "x (...) " [8 / 8]
"upjptz" [6] --> " (...) " [7 / 3]
"h" [1] --> "h" [1 / 1]
"qsshkvmawcmf" [12] --> " (...) " [7 / 7]
"tvdknroxszhufgck" [16] --> "tv (...) k" [10 / 10]
"ag" [2] --> "ag" [2 / 5]
"vbgdegtgshnzjrudca" [18] --> "vbgd (...) udca" [15 / 15]
"bscwimjjhmgvcwp" [15] --> "bscwimjjhmgvcwp" [15 / 18]
"xwhgbaenornbzwirlp" [18] --> "xwhgbaenornbzwirlp" [18 / 18]
"tbqyrekkzyizc" [13] --> "t (...) " [8 / 8]
"oowdwbeezeh" [11] --> "o (...) h" [9 / 9]
"avlzfzpjazhjc" [13] --> "avlzfzpjazhjc" [13 / 15]
"dngxmebwenfrbidonses" [20] --> "dngxme (...) donses" [19 / 19]
"bqfxyffdemjghipk" [16] --> "bqfxyffdemjghipk" [16 / 16]
"sfwnlkreghzff" [13] --> " (...) " [7 / 5]
"dznlsyaojtferxh" [15] --> "dznlsyaojtferxh" [15 / 17]
"zwkhjdafkzjdgc" [14] --> "zwk (...) dgc" [13 / 13]
"kpzochngmwoulne" [15] --> "kpz (...) lne" [13 / 13]
"vluqvhpcxg" [10] --> "vluqvhpcxg" [10 / 10]
"wuc" [3] --> "wuc" [3 / 8]

@JonathanAllan The latter is correct. The program should accept a string, the desired width and separator.

The two inequality driven rules have a conflict when len(string) = len(sep) = width, for example, what should the output be for string ab, separator 12, width 2. Are we free to output either the string or the separator in such cases?

The input/output need to be strings ? Or they can be list of characters?

@JonathanAllan The rules are in order. It is preferred to output the string itself if there is room for it. So, in your case, the output should be ab.

@Rod The challenge talks about strings as a sequence of characters, but I guess that lists are good too as it should not affect how the program is designed.

Related

The [tag:kolmogorov-complexity] tag is to be used for constant output. I have replaced it with the [tag:string] tag, you can revert if you disagree.

@EriktheOutgolfer No worries. Appreciate it!

Python 2, 93 76 72 bytes
s,w,p=input()
l=len(s)
if w<l:w=max(w-len(p),0);s[-~w/2:l-w/2]=p
print s

Try it online!
Input and output are a list of characters

Your code outputs the wrong value for the "upjptz" example.

@TomDevs fixed it

JavaScript (ES6), 78 bytes
(w,s,e,l=s.length,m=e.length)=>l>w?m<w?s.slice(0,w-m>>1)+e+s.slice(m-w>>1):e:s

I was pleasantly surprised to discover that w-m>>w and m-w>>1 give the desired result.

Python 2, 76 bytes
def f(s,p,w):t=len(s);q=len(p)-w;print[s,[p,s[:~q/2]+p+s[t+q/2:]][q<0]][t>w]

Tests are at TryItOnline!
Note: Places the extra character for odd splits on the right hand side
(question states that either is fine, although the examples show left only).

JavaScript ES6, 103 99 bytes
(a,b,c,d=a.length,e=c.length,f=(b>e?b:e)-e,g=a.split(""),h=g.splice(-~f/2,d-f,c))=>b<d?g.join(""):a

f=(a,b,c,d=a.length,e=c.length,f=(b>e?b:e)-e,g=a.split(""),h=g.splice(-~f/2,d-f,c))=>b<d?g.join(""):a;

console.log(f("dngxmebwenfrbidonses", 19, " (...) "));

You can save some bytes by changing ("") into \`. You can also shorten f: f=b>e?b-e:0`.

Mathematica, 90 bytes
If[(l=Length)[i=#2]<=#,#2,If[#<=(s=l@#3),#3,Join[(t=i~Take~Floor[#/2]&)[#-s],#3,t[s-#]]]]&

Unnamed function taking an integer (the width) as its first argument and two lists of characters (the string and the separator) as its second/third arguments, and returning a list of characters.


text:
Tool-Assisted Code Golf
TAS Golf

In the style of a tool-assisted speedrun with a code-golf twist, the goal of this challenge is to complete World 1-1 of the original Super Mario Bros game for the NES in your chosen programming language in as few bytes as possible, using only the in-game controller inputs in the format I'll describe below. Your program must output to stdout a list of lines in this format, created specifically for this challenge:
up down left right start select A B

Starting with the first frame, each newline represents the inputs for Controller 1 for a particular frame. The order of buttons per frame does not matter, and they can be separated by any amount of non-newline whitespace. All or none or some of the button names can be included per line. For example, a simple Python program that presses the D-pad right for 3 frames and then presses A might look like this:
for _ in range(3): print('right')
print('A')

And its output (which I would feed into my emulator to verify) would be:
right
right
right
A

Here, we define 'success' as reaching the flag at the end of World 1-1 pictured above. The score for this example Python submission, if it succeeded (which it doesn't), would be 44 bytes, or the original length of the Python program.
For an example working input file I created based on the current fastest TAS, see this Github Gist: https://gist.github.com/anonymous/6f1a73cbff3cd46c9e1cf8d5c2ff58e1 Note that this file completes the entire game.
There is no way to enter subframe inputs. There is also no way to enter inputs in Player 2's controller, but that also shouldn't be necessary (or useful) for completing the level or game.
The version of SMB used will be the original USA / Japan iNES ROM (md5sum 811b027eaf99c2def7b933c5208636de -- the USA version is the exact same as the Japanese version so either will work, the ROM is commonly labeled Super Mario Bros (JU) (PRG 0) or similar).
To test the submissions, I will run the programs, pipe their stdout into an input.txt file, and load them into FCEUX using this Lua script mario.lua I wrote for this challenge:
for line in io.lines('input.txt') do
   local t = {}
   for w in line:gmatch("%S+") do
      t[w] = true;
   end;
   joypad.set(1, t);
   emu.frameadvance();
end;
while (true) do
   emu.frameadvance();
end;

The specific command I'll be using is fceux mario.nes --loadlua mario.lua. There is no time limit to the programs, though they must eventually terminate.
This is a little Bash one-liner I made to convert a FCEUX movie (.fm2) file to an input.txt for my script, if it helps:
cat movie.fm2 | cut -d'|' -f 3 | sed 's/\.//g' | sed 's/R/right /g' | sed 's/L/left /g' | sed 's/D/down /g' | sed 's/U/up /g' | sed 's/T/start /g' | sed 's/S/select /g' | sed 's/B/B /g' | sed 's/A/A /g' | tail -n +13 > input.txt

For reference, here is a full-resolution map of World 1-1 (open the image in a new tab for full resolution):
(source: mariouniverse.com)
Note: At first glance, this may seem like a Kolmogorov complexity challenge on my given input.txt file. However, in reality the challenge is more complex than that because (a) the input.txt I provided is definitely not the shortest possible and (b) there has never been an attempt to create the shortest possible set of keypresses for SMB in this format. The 'fewest buttons possible' known TAS is different because it allows for holding of buttons for a long time, which would add length to the desired output in this challenge.

While you have provided a video of the level, I can't count how many rights are in the video. Could you tell us the moves needed?

@JackBates You can see a map of the level here: http://www.mariouniverse.com/images/maps/nes/smb/1-1.png I'll update the post to include that map.

Did you post this in the Sandbox? I don't remember it.

@JackBates I did: http://meta.codegolf.stackexchange.com/a/11421/48718

I think it's quite funny you have 16 upvotes and no answers :)

@JackBates that's the sign of a good, challengjng, non-trivial question

404 on that full resolution map image I think

@Liam I think the site is under maintenance, or one of their servers behind the load-balancer is down or something. Keep refreshing the page and you'll get it.

Python 2, 69 48 46 44 bytes
print"start\n\n"*19+(27*"A right\n"+"\n")*99

See it in action on youtube!
Automatically found with (a modified version of) this hacky script:
start = 18
oncycle = 21
offcycle = 4

while true do
    emu.poweron()
    -- emu.speedmode("maximum")

    starting = 0
    i = 0
    frames = 0
    last_mario_x = -1

    emu.message(start .. " " .. oncycle .. " ".. offcycle)

    state = 0
    while state ~= 6 and state ~= 11 and frames < 4000 do
        if frames > 500 and frames % 100 == 0 then
            mario_x = memory.readbyte(0x6D) * 0x100 + memory.readbyte(0x86)
            if mario_x == last_mario_x then emu.message("stuck " .. mario_x .. " " .. last_mario_x); break end
            last_mario_x = mario_x
        end

        if starting < start then
            joypad.set(1, {start=1})
            emu.frameadvance(); frames = frames + 1;
            joypad.set(1, {})
            emu.frameadvance(); frames = frames + 1;
            starting = starting + 1
        else
            if i < oncycle then
                joypad.set(1, {A=1, B=1, right=1})
                i = i + 1
            else
                joypad.set(1, {})
                i = i +  1
                if i == oncycle + offcycle then
                    i = 0
                end
            end

            emu.frameadvance()
            frames = frames + 1
        end

        state = memory.readbyte(0x000E)
        if state == 4 then
            emu.message("success!")
            os.exit()
            break
        end

    end

    if start < 30 then
        start = start + 1
    elseif offcycle < 10 then
        start = 18
        offcycle = offcycle + 1
    else
        offcycle = 1
        oncycle = oncycle + 1
    end
end

Tested and working! Bonus points for hitting the mushroom block! Thanks!

@Harry Please verify new version.

Confirmed, that's pretty incredible! Having some technical difficulties with recording but if someone else wants to do so with these submissions that would be greatly appreciated!

@Harry I just added another new version that saves 2 more bytes by... not using the B button! It barely fits in the 99 repeats, almost had to waste a byte on doing 100+ repeats.

Confirmed again, I really like your Lua script for this!

44-byte version also confirmed, fun to watch!

Ahh, this is the kind of answer I was going for, but I couldn’t find the right numbers!! Very nicely done.

@Harry This is a recording of mine: https://www.youtube.com/watch?v=2-I1EEOlQYA

Python 2, 107 bytes
i=0
print'\n'*33+'start'
for c in'~~22 +  2 2? @  F        . \r0'+'@'*10:print'A B right\n'[i:]*ord(c);i^=2

Very impressive and already much shorter than I thought! Maybe I should have stuck with the full game after all, haha. Also I tested this and can confirm it completes the level, if I can get it to record maybe I'll upload them all as YouTube videos!

JavaScript (ES6), 59 characters
_=>`start

`[a="repeat"](19)+(`A right
`[a](27)+`
`)[a](99)

This outputs the same text as orlp's answer. I tried coming up with a better method myself, but the movies I converted to an input.txt file did not always play properly. Whenever I tried running the emulator from cmd, I got an error stating "an unknown error occurred".

Can't run it right now on my end, but if it outputs the same input.txt as orlp's answer then we'll call it verified!

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


text:
Count My Change
Your task is to sort an array containing the strings "quarter", "dime", "nickel", and "penny" any number of times in no specific order and sort them so that they are in this order: quarter dime nickel penny (in other words, greatest to least monetary value).

Rules

Your program must take an array as input containing the names of U.S coins and sort them from greatest to least by monetary value.

For those who are not from the U.S or don't use change, the values of U.S coins, from greatest to least, are:

Quarter: 25 cents
Dime: 10 cents
Nickel: 5 cents
Penny: 1 cent

You may sort this array in any way you wish, as long as the output is ordered by the monetary values shown above.
Input can be taken in any way, be it command-line arguments or STDIN.
An input array would be all lowercase strings, something like this:

quarter dime nickel nickel quarter dime penny penny

The actual format of input and output is up to you.

Test Cases
"penny nickel dime quarter"
-> "quarter dime nickel penny"

"nickel penny penny quarter quarter quarter dime dime dime dime"
-> "quarter quarter quarter dime dime dime dime nickel penny penny"

"quarter dime nickel nickel quarter dime penny penny"
-> "quarter quarter dime dime nickel nickel penny penny"

This is code-golf, so standard rules & loopholes apply.

Let us continue this discussion in chat.

All test cases should include output. In the mobile the second and third cases are shown in two lines, so it looks as if the second line is the output

i'm canadian, can i assume the input has no pennies? ;)

@undergroundmonorail Sadly, no.

What happened to loonies and half-dollars?

@Adám This is not Canadian currency.

@ckjbgames I assumed that much. US coins come in 50¢, and $1, while Canada issues $2 instead of 1¢ and 50¢.

@Adám This is just coins that you would normally have on you as change.

Japt, 5 3 bytes
ñg9

Test it online!
Explanation
I, too, have added a sorting function to my language in the last few weeks :-) ñ takes in an array and a function and sorts the array as if each item had been mapped through that function.
The g function on a string takes in a number n and returns the nth char in the string, wrapping if n is negative or past the end of the string. The strings can thus be aligned as follows:
quarterquarter...
dimedimedimedi...
nickelnickelni...
pennypennypenn...

The 9th char (0-indexed) of each string has been highlighted in bold. These are in the correct order, so all we have to do is ñg9. (Though now that I look back on it, ñg5 would work as well...)

It should also work with 5, i think.

@FlipTack Yeah, I just noticed that myself. Not that it makes a difference ;-)

This. Cannot. Be. Defeated.

You outgolfed Dennis! Congrats!

@ckjbgames Dennis didn't post any answers ;-)

@ETHproductions He probably will. Just show him this question.

V, 7 bytes
ú/¨qu©¿

Try it online!
This uses the spiffy new sort command I added to V around a week ago (ú). Sweet timing!
The way this works is by sorting every line by default sorting (ASCII values) but ignoring the first match of a certain regex. In this case, the regex is (qu)?, although it has some gross non-ASCII stuff to avoid using backslashes. If you ignore the first two letters of "quarter", it starts with 'a', and then all of the coins are already in alphabetical order.
Non-competing version, 4 bytes
ú!/.

This feature was already implemented, but I hadn't tested it extensively yet so it had a bug that I only realized because of this challenge. There is no TIO link because TIO is slightly behind.
This works by reverse sorting every line but ignoring the first character on each line.

Python, 36 bytes
lambda a:a.sort(key=lambda x:x[-5:])

Unnamed function that sorts the list in-place by the key function given.
The slices of each coin name are then, arter, dime, ickel, and penny - which are in alphabetical (or more importantly, ordinal) order.

Oh oops - if I don't get the el the wrong way around I miss the c :p

Bash + coreutils, 18
tr q b|sort|tr b q

Transliterate q to b
Sort
Transliterate b back to q

Try it online.

Python 3, 42 41 38 bytes
An unnamed lambda function which takes input as a list of strings, sorts in place.
(Outgolfed by Jonathan Allan)
lambda x:x.sort(key=lambda s:(s*2)[5])

Try it online!
Other solutions I messed around with:
lambda x:x.sort(key=lambda s:s*(s<'q'))
lambda x:x.sort(key=lambda s:(s+'pi')[5])
lambda x:x.sort(key=lambda s:ord(s[3])%16)

Jelly, 4 bytes
6ịµÞ

Try it online! (the footer, ÇY, joins the resulting list with line feeds for a prettier print out.)
How?
6ịµÞ - Main link: list of strings
  µ  - monadic chain separation
   Þ - sort the list of strings by the monadic function:
6ị   - the sixth index - Jelly indexing is modular and 1-based

The Nth index of a list in Jelly is the Nth item starting at the left, counting from 1, and looping back to the start when need be. (The 0th is at the right, the -1th one left of that and so on too).
So the sixth character of ['d','i','m','e'] is 'i' since six is congruent to two modulo four.
The sixth character of the four coins in order are quarter, dime, nickel, penny
. These are in alphabetical (or more importantly, ordinal) order.

Another way to achieve the same thing would be to sort by the rotated strings with ṙ5µÞ, where ṙ rotates to the right, making the strings erquart, imed, lnicke, and penny.

PowerShell, 21 bytes
$args|sort{($_*3)[9]}

Try it online!
Explanation
Shamelessly stole the algorithm in ETHproductions's answer (basically). I multiply each string by 3, then sort based on the 9th character of the resulting string.

What is $_ in PowerShell?

@ckjbgames In a pipeline, within a scriptblock, it refers to the current item. So something like 1,2,3,4 | ForEach-Object { $_*2 } will output each number times 2; the script block is run once per input item.

That makes sense.

Bash (+coreutils) 11 bytes
Golfed
sort -rk1.2

How It Works
Reverse sort, with the "sort key" from the second character of the first field (word) till the end of line, i.e.:
uarter
ime
ickel
enny

Test
>echo penny nickel dime quarter|tr ' ' '\n'|sort -rk1.2

quarter
dime
nickel
penny

Try It Online !

Python, 32 bytes
lambda s:s.sort(key="npr".strip)

Try it online! Sorts the list in place.
The idea is to use a sorting key function without a lambda. A good candidate was x.strip, which takes the string x and removes its the left and right edges all characters in the input. For example, "abcdef".strip("faces") == "bcd".
The method "npr".strip takes:
quarter ->  np
dime    ->  npr
nickel  ->  pr
penny   ->  r

which are lexicographically sorted. I found the string npr by brute force. npu and npt also work, and there are none shorter.

CJam, 8 bytes
q~{5=}$p

Try it online!
Explanation
q~        Get and eval all input (array of coin names)
  {5=}$   Sort the array by the 5th index of each element (array indices loop in CJam)
       p  Print the result

Pyke, 9 7 5 bytes
.#5R@

Try it here!
.#5R@ - sort_by:
  5R@ -  i[5]

Retina, 10

6 10 bytes saved thanks to @ETHproductions

q
b
O`
b
q

Substitute q to b
Sort
Substitute b back to q

Try it online.

V, 8 7 bytes
1 byte saved thanks to @DJMcMayhem
Úçq/:m0

[Try it online!]
See @DJMcMayhem's answer in V (1 0 bytes shorter than mine)
Try it online!
Ú                    " sort all lines "
 ç                   " globally "
  q/                 "  where there a q is matched, "
    :m0              "  move it to the top of the buffer "

Here is an older solution at 1 byte larger, but I really like it.
V, 8 bytes
Ú/q
dGHP

[Try it online!]
Try it online!
Explanation
Ú        " sorts the lines

Now the buffer will be in this format:
dimes
nickels
pennies
quarters

The only thing left to do now is to move the quarters to the top.
/q      " search for a q "
dG      " delete everything from the first quarter to the end of buffer "
HP      " and paste it at the top of the buffer

You can do :m0 on your alternate solution to save a byte (and tie me) Úçq/:m0

@DJMcMayhem Thanks, TIL about :move

Japt, 3 bytes
ñé5

Try it online!

A couple other 3-byte solutions:
üÅw

Try it online!

ü é

Try it onlin!

T-SQL, 41 36 34 bytes
select*from @ order by right(a,5)

Explanation
Assume the input is pre-loaded in a table variable named @, with a single column named a, where each value is one coin to be sorted.
The select * from @ part is boiler-plate 'get all values to return'. The real magic happens in the order by clause.
Using the same strategy as Johnathan Allan, I sort by the last five characters (SQL will return the entire string if it's too short): arter, dime, ickel, penny.

q is the next letter after p, so for a simple mod to result in q less than p the value needs to be a factor of q, which is prime. You could subtract 1 first and then a modulus of 7 would work, but that would presumably take at least as many bytes as 113.

@Neil Yeah, I realized 113 being prime was wrecking my attempts to reduce the count. Doing -1 and then mod 7 is more bytes (including required parentheses.

APL (Dyalog APL), 11 bytes
Takes and returns list of strings.
{⍵[⍋↑5⌽¨⍵]}

Try it online!
{ anonymous function:
 ⍵[…] the argument indexed by
 ⍋ the ascending-making indices of
 ↑ the matrix whose rows are the padded
 5⌽ five-steps-rotated
 ¨⍵ items of the argument
}

JavaScript (ES6), 35 33 bytes
a=>a.sort(([,...a],[,...b])=>b>a)

Test cases

let f =

a=>a.sort(([,...a],[,...b])=>b>a)

console.log(f(['penny','nickel','dime','quarter']).join` `);
console.log(f(['nickel','penny','penny','quarter','quarter','quarter','dime','dime','dime','dime']).join` `);
console.log(f(['quarter','dime','nickel','nickel','quarter','dime','penny','penny']).join` `);

Befunge, 158 bytes
~:0`v0v4<~_
9:%8_^>8*`^1p9\+1g
$:!#@_1-0" ynnep">:#,_>
1-0" lekcin">:#,_>$:!#^_
" emid">:#,_>$:!#^_1-0
>:#,_$1>-:!#^_0" retrauq"
*84g9< ^*84g91-*84g94-*84g96-

Try it online!
String processing and sorting are not the sorts of things you'd typically want to attempt in Befunge, but this solution is taking advantage of John Kasunich's observation that we don't actually need to sort anything. We just count the number of occurrences of each coin (which can easily be determined from the first character), and then output that many of each coin name in the appropriate order.
It's still not at all competitive with other languages in terms of size, but this approach is at least better than it would have been if we'd tried to handle the challenge as a string sorting exercise.

Pyth, 3 bytes
@D5

Demonstration
Based on ETHproductions's answer in Japt.
Explanation:
@D5
@D5Q    Variable introduction
 D Q    Sort the input by
@ 5     Its fifth character

Brachylog, 3 bytes
↺₉ᵒ

Try it online!
Approach stolen from ETHproductions' Japt answer.
       The input
  ᵒ    sorted by
↺      its elements rotated left
 ₉     by 9
       is the output.

Husk, 3 bytes
Öṙ9

Try it online!
Ported from my Brachylog answer, which rips off ETHproductions' Japt answer but isn't an exact translation since it uses rotation instead of simple accessing-the-nth-element. There, I did it because ∋ doesn't let you index past the end of the input (which is probably quite helpful in many circumstances due to the declarative nature of the language). In Husk, ! does let you index past the end of the input, with the same modular wrapping around that Japt ñg9 uses, but it's from 1 so this program in particular would end up being one byte longer: Ö!10.
Ö      Sort by
 ṙ     rotation by
  9    9.

Vyxal, 3 bytes
µ5i

Try it Online! or Run all the test cases
How?
µ5i
µ   # Sort by:
 5i #  Index 5 into the list (zero-indexed, modular)

Port of Jelly.

Perl 6,  40 36  34 bytes
*.sort: {(<q d n p>Zxx 1..*).Bag{~m/./}}

Try it
*.sort: {%(<q d n p>Z=>1..*){~m/./}}

Try it
*.sort: {%(<q d n p>Z=>^4){~m/./}}

Try it
Expanded:
*\            # WhateverCode lambda ( this is the parameter )

.sort:        # sort using the following code block

{             # bare block lambda with implicit parameter ｢$_｣

  %(          # treat this list as a hash

    <q d n p> # list of first characters
    Z[=>]     # zipped using pair constructor
    ^4        # Range from 0 up-to 4 ( excludes 4 )

  ){          # get the value associated with this key

    ~m/./     # regex which gets the first character ( implicitly from ｢$_｣ )

  }

}

java 8, 128 112 bytes
This is a lambda expression for a java.util.function.Function<String[],String[]>
s->{String r="";for(String k:"q d c p".split(" "))for(String t:s)if(t.contains(k))r+=" "+t;return r.split(" ");}

Explantion:
For each of the 4 coins in order, go through the input and append the coin's name to the result every time there is a match for that coin's unique character. Split the result into an array and return it.

Mathematica, 50 bytes
Flatten@{Last@#,Most@#}&@Split@Sort@StringSplit@#&

RProgN, 18 bytes
~{3mtt¢\3mtt¢>}$

Explained
~               # Zero Space Segment
 {            } # Anonymous Function
  3m            # Repeat the inputted string 3 times
    tt¢         # And take the tenth character of that
       \3mtt¢   # Do the same for the entry underneith
             >  # Compare the ascii value of the two
               $# Sort the input by the anonymous function.

Try it online!

Ruby, 27 bytes
->s{s.sort_by{|x|(x*2)[5]}}

Batch, 82 bytes
@for %%c in (quarter dime nickel penny)do @for %%a in (%*)do @if %%a==%%c echo %%c

Takes input as command-line arguments and outputs to STDOUT. Works by concatenating the lists resulting from filtering the original list on each coin.

Ruby, 34 bytes
->m{m.sort_by{|c|c[1..2]}.reverse}

input and output as an array of strings

Ruby, 31 bytes
->s{s.sort_by{|i|i[1]}.reverse}

This will not always sort "nickel" and "dime" correctly.

Ruby, 30 bytes
->m{m.sort_by{|s|s[3].ord^16}}

Magical numbers found by trial and error. A bit clumsy, but shorter than using .reverse.

Smalltalk, 42 bytes
a sort:[:s :t|s allButFirst>t allButFirst]

Explanation
a              input array
sort:          sort message, criterion in the block
[:s :t |       block arguments, represent entries of the input array
allButFirst    copy the receiving string without its first character
>              alphabetic comparison

Perl 6 (19 bytes)
Takes a list of strings.
*.sort(*.comb[5%*])

In action:
my &f = *.sort(*.comb[5%*]);
say f(<quarter dime nickel nickel quarter dime penny penny>);

Thunno 2, 3 bytes
Þ9i

Try it online!
Port of ETHProductions's Japt answer - sort by 9th character.