text:
Checkmate (aka the urinal problem)
My Precalc teacher has one of his favorite problems that he made up (or more likely stole inspired by xkcd) that involves a row of n urinals. "Checkmate" is a situation in which every urinal is already occupied OR has an occupied urinal next to them. For instance, if a person is an X, then
X-X--X
is considered checkmate. Note that a person cannot occupy a urinal next to an already occupied urinal.
Task
Your program will take a number through stdin, command line args, or a function argument. Your program will then print out or return the number of ways that checkmate can occur in with the inputted number of urinals.
Examples
0 -> 1 (the null case counts as checkmate)
1 -> 1 (X)
2 -> 2 (X- or -X)
3 -> 2 (X-X or -X-)
4 -> 3 (X-X-, -X-X, or X--X)
5 -> 4 (X-X-X, X--X-, -X-X-, or -X--X)
6 -> 5 (X-X-X-, X--X-X, X-X--X, -X--X- or -X-X-X)
7 -> 7 (X-X-X-X, X--X-X-, -X-X--X, -X--X-X, X-X--X-, X--X--X or -X-X-X-)
8 -> 9 (-X--X--X, -X--X-X-, -X-X--X-, -X-X-X-X, X--X--X-, X--X-X-X, X-X--X-X, X-X-X--X, X-X-X-X-)
...
Scoring
The smallest program in bytes wins.

Related.

Related

The test cases keep getting updated. Can we have a program to verify them once and for all? And preferably get one higher, out of sequence?)

Alright, the test cases are correct according to my results. Also, there's no need for any more test cases.

The n=0 case should be 1. There is exactly one setup which is checkmate, and that's ''. This is the same as with factorial and permutations, 0! = 1, because there is exactly 1 way to arrange 0 items.

oeis.org/A228361

No toilet at all is indeed a checkmate situation. :D

The urinal problem has been around much longer than XKCD.  I first encountered it a decade before Randal's blog post; and have no reason to believe the flash game implementation that was shared around the dorm lan my freshman year was the origin of it.

Does the cubicle count in this problem?

Oasis, 5 bytes
Code
cd+2V

Extended version
cd+211

Explanation
1 = a(0)
1 = a(1)
2 = a(2)

a(n) = cd+
       c      # Calculate a(n - 2)
        d     # Calculate a(n - 3)
         +    # Add them up

Try it online!

This is a strange answer, the language was created about a month ago with no proper documentation in the repo....

@tuskiomi It do have a doc, in info.txt

@TùxCräftîñg that's just a reference sheet...

@tuskiomi It count as a doc

@TùxCräftîñg sure, if you want to be technical. I could draw a horse and call it documentation towards my programming project. that doesn't make it useful, or decisive.

@tuskiomi info.txt is useful, it contains a documentation for every Oasis commands

@tuskiomi That's the result of procrastination and lazyness. I'll try to add a concise documentation on how the actual language works today.

Java 7, 65 42 bytes
int g(int u){return u>1?g(u-2)+g(u-3):1;}

The sequence just adds previous elements to get new ones. Hat tip to orlp and Rod for this shorter method ;)
Old:
int f(int u){return u<6?new int[]{1,1,2,2,3,4}[u]:f(u-1)+f(u-5);}

After the fifth element, the gap in the sequence rises by the element five previous.

If u=3 then your function returns 1 but the examples show that it should be 2.

Oops! I was using my f function from the other snippet instead of recursing. Stupid me, fixing...

Can't that last part (u>0?u:1;) become 1;?

@ConorO'Brien That misses u=2

@Geobits ah, okay

Doesn't this return 1 for u=0 when it ought to return 0?

@Jordan If there are zero urinals, then "every urinal is already occupied" in the one configuration possible. I believe the test case shown in the question is wrong.

You can replace u>0?u:1;) by 1; if you change the first comparison to u>1, then on u=2 the output will be g(0)+g(-1), which will be 2

Oh, that's clever... I didn't think of going negative with it :)

Python 2, 42 40 39 35 bytes
f=lambda n:n>1and f(n-2)+f(n-3)or 1

Generating the actual sets:
lambda n:["{:0{}b}".format(i,n).replace("0","-").replace("1","X")for i in range(2**n)if"11"not in"{:0{}b}".format(i*2,2+n).replace("000","11")]

Ruby, 58 34 bytes
Heavily inspired by Geobits' original Java answer.
f=->n{n<3?n:n<6?n-1:f[n-1]+f[n-5]}

See it on repl.it: https://repl.it/Dedh/1
First attempt
->n{(1...2**n).count{|i|!("%0#{n}b"%i)[/11|^00|000|00$/]}}

See it on repl.it: https://repl.it/Dedh

Python, 33 bytes
f=lambda n:+(n<2)or f(n-2)+f(n-3)

Uses the shifted base cases f(-1) = f(0) = f(1) = 1. If True could be used for 1, we would not need 3 bytes for the +().

J, 31 27 23 bytes
Saved 4 bytes thanks to miles!
0{]_&(]}.,+/@}:)1 1 2"_

An explanation is to come soon.
Old solution
(>.1&^)`(-&3+&$:-&2)@.(2&<)

This is an agenda. The LHS is a gerund composed of two verbs: >.1&^ and -&3+&$:-&2. The first one is used if the condition (2&<) fails. That means the fork >.1&^ is activated over the argument. Observe:
   1 ^ 0 1 2
1 1 1
   (1&^) 0 1 2
1 1 1
   0 1 2 >. (1&^) 0 1 2
1 1 2
   (>.1&^) 0 1 2
1 1 2

Here, >. takes the max of two values. Thus, it yields 1, 1, and 2 as the initial terms.
The second verb in the gerund is a fork:
-&3 +&$: -&2

The left and right tines are applied to the verb, subtracting 3 and 2 respectively; then the middle verb is called with left and right arguments equal to those. $: calls the verb on each argument, and + adds those two. It's basically equivalent to ($: arg - 3) + ($: arg - 2)
Test cases
   f =: (>.1&^)`(-&3+&$:-&2)@.(2&<)
   f 0
1
   f 2
2
   f 4
3
   f 6
5
   f 8
9
   F =: f"0         NB. for tables
   F i.13
1 1 2 2 3 4 5 7 9 12 16 21 28
   i.13
0 1 2 3 4 5 6 7 8 9 10 11 12
   (,. F) i.13
 0  1
 1  1
 2  2
 3  2
 4  3
 5  4
 6  5
 7  7
 8  9
 9 12
10 16
11 21
12 28

PHP, 105 113 93 bytes
+3 for n=1; +9 for $argv, -1-3 golfed
-20: noticed that I don´t have to the combinations, but only their count
for($i=1<<$n=$argv[1];$i--;)$r+=!preg_match("#11|(0|^)0[0,]#",sprintf("%0{$n}b,",$i));echo$r;

run with -r
loop from 2**n-1 to 0:

check binary n-digit representation for 11, 000, 00 at the beginning or the end, or a single 0
if no match, increase result

print result
same size, slightly simpler regex
for($i=1<<$n=$argv[1];--$i;)$r+=!preg_match("#11|^00|00[,0]#",sprintf("%0{$n}b,",$i));echo$r;

loop from 2**n-1 to 1 (instead of 0)
check binary representation for 11, 00 at the beginning or the end, or 000
prints nothing for n=0

PHP, 82 bytes
Arnauld´s answer ported and golfed:
for($i=$k=1<<$n=$argv[1];--$i;)$r+=!($i&$x=$i/2|$i*2)&&(($i|$x)&~$k)==$k-1;echo$r;

prints nothing for n=0

add 3 bytes for the new n=0: insert ?:1 before the final ;

JavaScript (ES6) / Recursive, 30 27 bytes
Edit: saved 3 bytes thanks to Shaun H

let

f=n=>n<3?n||1:f(n-2)+f(n-3)

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

JavaScript (ES6) / Non-recursive 90 77 bytes
Edit: saved 13 bytes thanks to Conor O'Brien and Titus

let f =

n=>[...Array(k=1<<n)].map((_,i)=>r+=!(i&(x=i>>1|i+i))&&((i|x)&~k)==k-1,r=0)|r

for(var n = 1; n < 16; n++) {
  console.log(n, f(n));
}

I think ((i|r|l)&(k-1)) can become ((i|r|l)&k-1), or even ((i|r|l)&~-k)

one byte: i<<1 -> i*2 or i+i

You can use one variable for l and r, saving 6 bytes: !(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1; and if you can insert ,k-- somewhere, you can replace k-1 with k to save parens.

&(k-1) needs no parens anyway; but you can use &~k instead.

i'm just gonna leave this here: f=n=>n<3?n||1:f(n-2)+f(n-3)

MATL, 25 23 bytes
W:qB7BZ+t!XAw3BZ+!3>a>s

Try it online! Or check all test cases.
Explanation
Two convolutions! Yay!
This builds an array, say A, where each possible configuration is a row. 1 in this array represents an occupied position. For example, for input 4 the array A is
0 0 0 0
0 0 0 1
0 0 1 0
···
1 1 1 0
1 1 1 1

The code then convolves array A with [1 1 1]. This gives an array B. Occupied positions and neighbours of occupied positions in A give a nonzero result in array B:
0 0 0 0
0 0 1 1
0 1 1 1
···
2 3 2 1
2 3 3 2

So the first condition for a configuration to be a checkmate is that B contains no zeros in that row. This means that in that row of A there no empty positions, or there were some but were neighbours of occupied positions.
We need a second condition. For example, the last row fulfills the above condition, but is not part of the solution because the configuration was not valid to begin with. A valid configurations cannot have two neighbouring occupied positions, i.e cannot have two contiguous 1's in A. Equivalently, it cannot have two contiguous values in B exceeding 1. So we can detect this by convolving B with [1 1] and checking that in the resulting array, C,
0 0 0 0
0 1 2 1
1 2 2 1
···
5 5 3 1
5 6 5 2

no value in that row exceeds 3. The final result is the number of configurations that fulfill the two conditions.
W:q    % Range [0 1 ... n-1], where n is implicit input
B      % Convert to binary. Each number produces a row. This is array A
7B     % Push array [1 1 1]
Z+     % 2D convolution, keeping size. Entries that are 1 or are horizontal
       % neighbours of 1 produce a positive value. This is array B
t!     % Duplicate and transpose (rows become columns)
XA     % True for columns that contain no zeros
w      % Swap. Brings array B to top
3B     % Push array [1 1]
Z+     % 2D convolution, keeping size. Two horizontally contiguous entries
       % that exceed 1 will give a result exeeding 3. This is array C
!      % Transpose
3>     % Detect entries that exceed 3
a      % True for columns that contain at least one value that exceeds 3
>      % Element-wise greater-than comparison (logical and of first
       % condition and negated second condition)
s      % Sum (number of true values)

Jelly, 11 bytes
,’fR_2ß€So1

Try it online! or verify all test cases.
How it works
,’fR_2ß€So1  Main link. Argument: n

 ’           Decrement; yield n - 1.
,            Pair; yield [n, n - 1].
   R         Range; yield [1, ..., n].
  f          Filter; keep the elements that are common to both lists.
             This yields [n, n - 1] if n > 1, [1] if n = 1, and [] if n < 1.
    _2       Subtract 2 from both elements, yielding [n - 2, n - 3], [-1], or [].
      ß€     Recursively call the main link for each integer in the list.
        S    Take the sum of the resulting return values.
         o1  Logical OR with 1; correct the result if n < 1.

How does this work? Does it use the recursive formula, or something else?

@ConorO'Brien Yes, it uses the recursive formula. I've added an explanation.

Mathematica, 35 bytes
a@0=a@1=1;a@2=2;a@b_:=a[b-2]+a[b-3]

Defines a function a. Takes an integer as input and returns an integer as output. Simple recursive solution.

AnyDice, 51 bytes
function:A{ifA<3{result:(A+2)/2}result:[A-2]+[A-3]}

There should be more AnyDice answers around here.
My solution defines a recursive function that calculates a(n)=a(n-2)+a(n-3). It returns a(0)=a(1)=1 and a(2)=2 using some integer division magic.
Try it online
Note: the output may look weird, and that's because it's usually used to output dice probabilities. Just look at the number to the left of the bar chart.

Perl, 35 34 bytes
Includes +1 for -p
Give input on STDIN
checkmate.pl <<< 8

checkmate.pl:
#!/usr/bin/perl -p
$\+=$b-=$.-=$\-$b*4for(++$\)x$_}{

A newly developed secret formula. Ripple update 3 state variables without the need for parallel assignments.
It is equally short (but a lot slower and taking a lot more memory) to just solve the original problem:
#!/usr/bin/perl -p
$_=grep!/XX|\B-\B/,glob"{X,-}"x$_

but that doesn't work for 0

Jelly, 19 bytes
The recursive solution is probably shorter...
Ḥ⁹_c@⁸
+3µ:2R0;ç€µS

See it at TryItOnline
Or see the series for n = [0, 99], also at TryItOnline
How?
Returns the n+3th Padovan's number by counting combinations
Ḥ⁹_c@⁸ - Link 1, binomial(k, n-2k): k, n
Ḥ      - double(2k)
 ⁹     - right argument (n)
  _    - subtract (n-2k)
     ⁸ - left argument (k)
   c@  - binomial with reversed operands (binomial(k, n-2k))

+3µ:2R0;ç€µS - Main link: n
  µ       µ  - monadic chain separation
+3           - add 3 (n+3)
   :2        - integer divide by 2 ((n+3)//2)
     R       - range ([1,2,...,(n+3)//2]
      0;     - 0 concatenated with ([0,1,2,...,(n+3)//2]) - our ks
        ç€   - call previous link as a dyad for each
           S - sum

JavaScript (ES6), 62 bytes
n=>[1,...Array(n)].reduce(($,_,i,a)=>a[i]=i<3?i:a[i-3]+a[i-2])

This is the first time that I've needed two dummy variable names. A recursive version would probably be shorter, but I really like reduce... Edit: Found a solution, also 62 bytes, which only has one dummy variable:
n=>[1,...Array(n)].reduce((p,_,i,a)=>a[i]=i<5?i+2>>1:a[i-5]+p)

CJam, 20 bytes
1_2_{2$2$+}ri*;;;o];

Try it online!
Explanation
This uses the recurrence relationship shown in the OEIS page.
1_2_                   e# Push 1, 1, 2, 2 as initial values of the sequence
           ri          e# Read input
    {     }  *         e# Repeat block that many times
     2$2$              e# Copy the second and third elements from the top
         +             e# Add them
              ;;;      e# Discard the last three elements
                 o     e# Output
                  ];   e# Discard the rest to avoid implicit display

FRACTRAN, 104 93 bytes
Input is 11**n*29 and output is 29**checkmate(n).
This is mostly for fun, especially since I'm currently being outgolfed by Python, JS, and Java. Same number of bytes as PHP though :D Golfing suggestions welcome.
403/85 5/31 3/5 9061/87 3/41 37/3 667/74 37/23 7/37 38/91 7/19 5/77 1/7 1/17 1/2 340/121 1/11

Ungolfing
               At the start we have 11**n * 29
1/11           If n < 2, we remove the 11s and print 29**1
340/121        If n >= 2, we subtract two 11s (n-2) and add one 17, two 2s and one 5.
                 We now have 17**1 * 29**1 * 2**2 * 5.
                 These are the register for a, b, c at registers 17, 29, and 2.
                 5 is an indicator to start the first loop.
                 This loop will move a to register 13.
403/85 5/31    Remove the 17s one at a time, adds them to the 13 register.
                 5 and 31 reset the loop.
3/5            Next loop: moves b to a and adds b to a in register 13.
9061/87 3/41   Remove the 29s one at a time, adds them to the 17 and 13 registers.
                 3 and 41 reset the loop.
37/3           Next loop: moves c to b in register 29.
667/74 37/23   Remove the 2s one at a time, adds them to the 29 register.
                 37 and 23 reset the loop.
7/37           Next loop: moves a+b to c in register 2.
38/91 7/19     Remove the 13s one at a time, adds them to the 2 register.
                 7 and 19 reset the loop.
5/77           Move to the first loop if and only if we have an 11 remaining.
1/7 1/17 1/2   Remove the 7 loop indicator, and all 17s and 2s.
               Return 29**checkmate(n).

><>, 25+2 = 27 bytes
211rv
v!?:<r@+@:$r-1
>rn;

Needs the input to be present on the stack at program start, so +2 bytes for the -v flag. Try it online!
The first line initialises the stack to 1 1 2 n, where n is the input number. The second line, running backwards, checks that n is greater than 1. If it is, n is decremented and the next element in the sequence is generated as follows:
r$:@+@r              a(n-3) a(n-2) a(n-1) n

r        Reverse   - n a(n-1) a(n-2) a(n-3)
 $       Swap      - n a(n-1) a(n-3) a(n-2)
  :      Duplicate - n a(n-1) a(n-3) a(n-2) a(n-2)
   @     Rotate 3  - n a(n-1) a(n-2) a(n-3) a(n-2)
    +    Add       - n a(n-1) a(n-2) a(n)
     @   Rotate 3  - n a(n) a(n-1) a(n-2)
      r  Reverse   - a(n-2) a(n-1) a(n) n

The final line outputs the number on the bottom of the stack, which is the required element in the sequence.

05AB1E, 12 bytes
XXXIGX@DŠ0@+

Explanation
XXX            # initialize stack as 1, 1, 1
   IG          # input-1 times do:
     X@        # get the item 2nd from bottom of the stack
       DŠ      # duplicate and push one copy down as 2nd item from bottom of the stack
         0@    # get the bottom item from the stack
           +   # add the top 2 items of the stack (previously bottom and 2nd from bottom)
               # implicitly print the top element of the stack after the loop

Try it online!

Actually, 25 bytes
This seems a little long for a simple f(n) = f(n-2) + f(n-3) recurrence relation. Golfing suggestions welcome. Try it online!
╗211╜¬`);(+)`nak╜2╜2<I@E

Ungolfing
         Implicit input n.
╗        Save n to register 0.
211      Stack: 1, 1, 2. Call them a, b, c.
╜¬       Push n-2.
`...`n   Run the following function n-2 times.
  );       Rotate b to TOS and duplicate.
  (+       Rotate a to TOS and add to b.
  )        Rotate a+b to BOS. Stack: b, c, a+b
         End function.
ak       Invert the resulting stack and wrap it in a list. Stack: [b, c, a+b]
╜        Push n.
2        Push 2.
╜2<      Push 2 < n.
I        If 2<n, then 2, else n.
@E       Grab the (2 or n)th index of the stack list.
         Implicit return.

Actually, 18 bytes
This is an Actually port of Dennis' longer Jelly answer. Golfing suggestions welcome. Try it online!
3+;╖½Lur⌠;τ╜-@█⌡MΣ

Ungolfing
         Implicit input n.
3+       Add 3. For readibility, m = n+3.
;╖       Duplicate and store one copy of m in register 0.
½Lu      floor(m/2) + 1.
r        Range from 0 to (floor(m/2)+1), inclusive.
⌠...⌡M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  τ╜-      Push m-2k. Stack: [m-2k, k]
  @█       Swap k and m-2k and take binomial (k, m-2k).
            If m-2k > k, █ returns 0, which does not affect the sum() that follows.
         End function.
Σ        Sum the list that results from the map.
         Implicit return.

Haskell, 27 bytes
r=1:1:2:zipWith(+)r(tail r)

Try it online!

Vyxal, 7 bytes
⁺»‡_+TḞ

Try it Online!
Uses the same recurrence relation a(n) = a(n-2) + a(n-3)
      Ḟ # Create an infinite list
⁺»      # Starting from digits of 112
  ‡     # Generate new terms by a function
     T  # Taking in the last three terms
   _    # Pop the first
    +   # Add the other two together

Stax, 7 bytes
ÉKΦΘÄO¢

Run and debug it
Uses the recurrence relation.  C(n) = C(n-2) + C(n-3)

C (gcc), 33 bytes
f(n){return n<2?1:f(n-2)+f(n-3);}

Try it online!

05AB1E, 8 bytes
ƵBSλè₂₃+

Try it online or verify the infinite list.
Explanation:
ƵB        # Push compressed integer 112
  S       # Convert it to a list of digits: [1,1,2]
   λ      # Start a recursive environment,
    è     # to output the 0-based (implicit) input'th value
          # (which will be output implicitly as result afterwards)
ƵBS       # Starting at a(0)=1, a(1)=1, a(2)=2
          # And where every following a(n) is calculated as:
     ₂₃+  #  a(n-2) + a(n-3)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why ƵB is 112.


text:
Alexa and the Tea Plantation
Hey guys, first time poster here. I went on Coderoulette recently and some guy posted this question. I looked around online but it doesn't seem to be anywhere. I figured I would post it here for anyone who is a fan of these types of problems. Enjoy!

Alexa is a druid who loves Mathematics! She lives in the land of Alfa, taking care of a tea plantation.
The plantation has N plants and the height of the ith plant is Hi.
Alexa has developed a recent interest in palindromes. She wants to crop the plants so the height of the plants forms a palindrome (without any reordering). She has 2 spells in her arsenal- the 'Growlith' spell will increase the height of a plant by 1 unit, the 'Shrinkooza' spell will decrease the height of a plant by 1 unit. The 'Growlith' and 'Shrinkooza' spells cost A and B units of magic respectively. Help Alexa find the minimum units of magic, that shall enable her to fulfill her objective.
Input Format
First line contains an integer T. T testcases follow.
First line of each test case consists of 3 space-separated integers N, A and B.
Next line consists of N space-separated integers, the initial height of the plants.
Output Format
Print the answer to each test case on a new line.
Constraints
1 <= T <= 10
1 <= N <= 105
0 <= A, B <= 108
1 <= Hi <= 103

Example
Input
1
5 2 2
1 6 2 3 4

Output
12

Explanation
She can use the 'Growlith' spell on the first plant 3 times and the 'Shrinkooza' spell on the second plant 3 times to form 4 3 2 3 4.
Challenge
Write code that will create a palindrome using the least units of magic possible for N plants.
Scoring
This is code golf. The shortest code in bytes wins.

What's the winning criterion?

Don't be discouraged just check out some other challenges based on their input format and winning criterion, the underlying problem is interesting.

Also, @AlexA. is male.

"Lowest complexity" for this is probably not ideal, since there's an easy O(n) solution that will probably be used by all answers.

I'm open to suggestions. I just think it's an interesting problem and wasn't sure where else to post it. If you have a better winning criterion please feel free to edit or let me know!

Code golf (e.g shortest answer wins) is usually the easiest one.

Please reconsider the input format. Usually we are not so restrictive. People want to use the native format of their favorite language. "Any reasonable format" is a good way to go.

I don't see the need for multiple testcases in a single run (that's more for automation on another sites). Welcome to PPCG.

The introduction makes me worry that this might be a copyright infringement. Was the original question posted under a licence compatible with CC-SA?

Maybe I am missing something or your provided output example and the challenge do not match exactly. do you want the minimal cost to create a palindrome or the palindrome itself? (or both?)

05AB1E, 20 bytes
WU|vy#Â‚ø€¥˜Ä2ä`OX*,

Explanation
WU                    # store minimum cost in X
  |v                  # for each testcase
    y#                # convert to list split on spaces
      Â‚ø             # zip with its own reverse
         €¥           # deltas of each pair
           ˜Ä         # deep flatten and take absolute value
             2ä       # split into 2 pieces
               `      # flatten (leaves the smaller piece on top of the stack)
                O     # sum
                 X*   # multiply with minimum cost
                   ,  # print

Try it online!

Julia, 88 Bytes
f(l,A,B)=reduce(+,map(abs,map(sum,[zip(-l,reverse(l))...][1:fld(end,2)])))*min([A,B]...)

Explained:
If I am not mistaken, all we have to do is either grow all necessary plants or shrink them (depending on which operations is less expensive)

zip input list with a reverse of itself (align corresponding heights)
only look at first half of the list (floor when length is odd)
sum the differences
multiply with minimum cost (A or B)

Example
f([1,6,2,3,4],1,2) -> 6   (grow plant 1 and 4, yields [4,6,2,6,4])
f([1,6,2,3,4],3,2) -> 12   (shrink plant 2 and 5, yields [1,3,2,3,1])

Note:
As there is still a discussion about the input format, I disregarded it for the moment.
Update:
Updated to output energy, as I think that outputing the actual palindrome is more challenging I attach my previous code here (76 Bytes):
f(l,A,B)=reduce(hcat,map(x->sort([x...]),[zip(l,reverse(l))...]))[A>B?1:2,:]

No, the challenge is to output the minimum amount of energy required to create a palindrome from the plant heights.

okay, updated my answer :)

JavaScript (ES6), 70 bytes
f=(a,g,s)=>a.reduce((t,h,i)=>t+Math.abs(a[a.length+~i]-h),0)*(g>s?s:g)/2

Double-counts the differences, but we only need to make half the changes, which is achieved by dividing by 2 at the end.

source: Stack Exchange

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

sort: votes


text:
Find the largest number n positions away from n
A sequel to this question.
Task
Given an array of positive integers, find the largest element k for which:

There exists some positive integer distance n, so that the element in the array located n places to the left or right from k equals n.

The array is guaranteed to contain at least one element satisfying this condition.
The shortest code (in bytes) wins. You may choose whichever I/O format you like.
Example
Given the input
[4, 6, 7, 9, 3, 6, 5, 7, 2]

The eligible values are:

The 4, as there is a 7 located 7 positions to its right
The first 6, as there is a 3 located 3 positions to its right
The 3, as there is a 4 located 4 positions to its left
The 5, as there is a 2 located 2 positions to its right
The second 7, as there is a 3 located 3 positions to its left.

Of these values, the largest is 7.
Test cases
[1, 13] → 13
[2, 9, 8, 3, 72, 2] → 8
[5, 28, 14, 5, 6, 3, 4, 7] → 14
[1, 3, 5, 15, 4, 1, 2, 6, 7, 7] → 7
[5, 1, 3, 5, 2, 5, 5, 8, 5, 1, 5, 1, 2, 3] → 5
[5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5] → 10

Two more (albeit slightly redundant) cases within the example: the first 6 (again) as there is a 5 five positions to it's right; or the second 7 (again) as there is a 6 six positions to it's left.

On my phone the title appears to be "Find the largest number positions away from an". 2. The condition stated is that there exists some k such that (a property that doesn't depend on k). It surely must be wrong.

@PeterTaylor "this" in "this element" refers to k.

@Taemyr, that doesn't make sense for two reasons: firstly, because k is not stated to be an element; and secondly because we're asked to "find the largest element satisfying" the condition, so "this element" has an antecedent outside the condition.

@PeterTaylor Someone had edit the post incorrectly. It was right the first time :(

Maybe you could avoid all confusion by saying "find the largest element k such that" and then use k instead of this element in the definition?

@MartinEnder I agree. That's much more understandable, and that's how I'd phrase it if I were writing it mathematically.

Jelly, 9 bytes
Jạþ`=ḅa¹Ṁ

Try it online! or verify all test cases.
How it works
Jạþ`=ḅa¹Ṁ  Main link. Argument: A (array)

J          Indices; yield [1, ..., len(A)].
   `       Use the previous return value as left and right argument:
 ạþ        Absolute difference table; take the absolute value of the difference
           of each pair of indices, yielding a 2D array.
    =      Compare each absolute difference with the corresponding item of A.
     ḅ     Base; convert each Boolean list from base i to integer, where i is the
           corresponding item of A. The value of i is not important; we only care
           if the list contains a 1, which will result in a non-zero integer.
       ¹   Identity; yield A.
      a    Logical AND; replace non-zero values with the corresponding items of A.
        Ṁ  Take the maximum.

Hmm, not sure what the policy about this is, but you now have two different approaches in separate answers, in the same program language by the same user. Wouldn't it be more advisable to put both 9- and 10-byte snippets in the same answer, since it's the same programming language and both by you? I can understand multiple answers in the same programming language by multiple users, but I personally think different approaches by the same user in the same programming language would be better suited as edits. Just my opinion.

That was my first meta question, and the consensus seemed to be that different approaches should be posted in different answers. In this case, my approaches don't have anything but the maximum at the end in common, so I went for a separate post.

05AB1E, 21 bytes
vyN+Ny-})¹gL<Ãv¹yè})Z

Explanation
v      }               # for each num in input
 yN+                   # push index + num
    Ny-                # push index - num
        )              # wrap stack in a list
         ¹gL<Ã         # remove indices outside the range of input
              v¹yè})   # get list of elements in input at the remaining indices
                    Z  # get max

Try it online!

You probably use it all the time, but I only just noticed "wrap stack in a list".   Neat.

@GreenAsJade: Yeah it's one of the commands I use the most :)

Haskell, 61 57 55 bytes
f x=maximum[a|(n,a)<-x,(i,b)<-x,b==abs(n-i)]
f.zip[0..]

Usage example: (f.zip[0..]) [5,28,14,5,6,3,4,7] -> 14.
(More or less) a direct implementation of the definition: for each index n of the input list x keep a := x!!n if there's an index i where b := x!!i equals abs(n-i). Find the maximum.
Edit: @xnor saved two bytes. Thanks!

Since you're not using x, it should be shorter to define a function in z and compose in zip[0..].

Jelly, 10 bytes
,N+JFfJị¹Ṁ

Try it online! or verify all test cases.
How it works
,N+JFfJị¹Ṁ  Main link. Argument: A (array)

,N          Pair A with -A (element-wise negative).
   J        Yield the indices of A [1, ..., len(A)].
  +         Add the elements of A (and their negatives) with the corr. indices.
    F       Flatten the resulting 2D array.
     fJ     Filter indices; remove invalid indices (not in [1, ..., len(A)]) from
            the generated array. The result is the list of all indices of eligible
            elements of A.
       ị¹   Retrieve the corresponding elements of A.
         Ṁ  Take the maximum.

Python 3, 85 80 72 Bytes
lambda l,e=enumerate:max(i for p,i in e(l)for s,j in e(l)if j==abs(s-p))

Edit: -8 Bytes thanks to @Dennis

EXCEL: 32 30 bytes
=MAX(IF(A:A-ROW(A:A)<0,A:A,0))
I still cannot believe I got it to be this short...
How to use:
paste this into ANY cell EXCEPT the cells of column A. After pasting, while still editing, press control+shift+enter to correctly enter it.
put your values into column A, 1 value per cell (as per CSV entry).
If you want to find out how this works, I've posted an additional tip in my Tips for golfing in Excel question.

I'm loving these excel golfs - who'd'a thought!!

JavaScript (ES6), 61 bytes
a=>Math.max(...a.filter((_,i)=>a.some((e,j)=>e==i-j|e==j-i)))

Perl, 45 bytes
Includes +2 for -ap
Give numbers on a line on STDIN:
largest.pl <<< "5 12 2 5 4 7 3 3 6 2 10 5 5 5 4 1 8 5"

largest.pl:
#!/usr/bin/perl -ap
($_)=sort{$b-$a}map@F[$^P=$n-$_,$n+++$_],@F

One more byte can be gained by replacing ^P by the literal control character, but that leads to a warning on STDERR on recent perls.
Assumes largest number + array length < 2^32

Pyth, 19 17 bytes
Thanks to @Pietu1998 for -2 bytes
eS@LQ@UQs.e,-kb+b

A program that takes input of a list on STDIN and prints the result.
Try it online
How it works
eS@LQ@UQs.e,-kb+b  Program. Input: Q
         .e        Map over Q (implicit input fill) with elements as b and indices as k:
            -kb     k-b
               +b   k+b (Implicit fill with k)
           ,        2-element list of those (possible indices)
        s          Flatten that
      UQ           Yield [0, 1, 2, 3..., len(Q)-1]
     @             Filter the flattened list by presence in the above, removing invalid
                   indices
  @LQ              Index into Q at those indices
 S                 Sort that
e                  Yield the last element of that, giving the maximum
                   Implicitly print

}# is the same as @. Also, if you rearrange the last bit to ,-kb+bk you can remove the last k since Pyth auto-inserts it.

@Pietu1998 Thanks. I didn't know about the implicit fill for enumerate; does that work for any other map-type functions?

Works for any lambda, it autofills the rest of any lambda with the first lambda variable.

MATL, 13 Bytes
ttn:tYTq=a)X>

Input must be a column vector. I.e., input is semicolon-separated like [1;2;3], or comma separated with a transpose tick at the end like [1,2,3]'.
Try it online!
All test cases: (A), (B), (C), (D), (E), (F)
Thanks to Suever for suggestions in the MATL chatroom to save 2 characters.
Explanation:
The overall strategy is the same as my Octave/MATLAB answer, where the basic concept is explained:
https://codegolf.stackexchange.com/a/94161/42247
The specific code in this MATL answer is built up as follows:
The core of the method is the construction of the Toeplitz matrix whose ij'th entry is abs(i-j). We first construct the Toeplitz matrix with entries abs(i-1)+1 with MATL's toeplitz command YT as follows:
n:tYT % Equivalent to @(v)toeplitz(1:length(v))

To see how this works, let us call the input vector to this code snippet 'v'. The 'n' finds the length of v, then ':' constructs the vector 1:length(v). Next the 't' makes another copy of 1:length(v) on the stack; this extra copy is needed due to a well-known bug in the YT function in MATL (the MATL equivalent of toeplitz()), wherein it expects two copies of the input instead of 1. Then YT takes the two copies of this vector 1:length(v) off the stack, and makes the abs(i-j)+1 Toeplitz matrix from them.
Now we need to subtract 1 from this matrix to get the Toeplitz matrix with entries abs(i-j), and find the ij locations where this abs(i-j) Toeplitz matrix is equal to the matrix of all column vectors containing column-copies of the input vector v. This is done as follows:
t n:tYT q=
% t [code] q= is equivalent to @(v) [code](v)-1 == v

The first 't' makes an extra copy of the input and stores it on the stack. The 'n:tYT' makes the toeplitz matrix as described earlier and outputs it into the stack. Then 'q' subtracts 1 from the Toeplitz matrix, and '=' does the elementwise equality comparison between the abs(i-j) matrix and the vector whose columns are copies of the input. Note that by comparing a column vector to a matrix, we are implicitly taking advantage of MATLAB/MATL's operator broadcasting rules (the column vector in the comparison gets copied to make a matrix without issuing any commands).
Finally, we need to find the row indices i where there is a column j such that the ij'th entry in the matrix difference constructed above equals 1, then get the value of the input vector corresponding to these indices, then take the maximum. This in the following three steps:
1) Find the indices for any row that contains a nonzero:
tn:tYTq= a
% [code] a is equivalent to @(v) any([code](v))

2) Extract the elements of the input vector corresponding to those indices:
t tn:tYTq= a ) X>
% t [code] ) is equivalent to @(v) v([code](v)]

3) Find and return the maximum element:
t tn:tYTq= a ) X>
% [code] X> is equivalent to @(v) max(v).

The behaviour of function YT has changed in release 20.2.2. Now it uses 1 input by default (which is more useful in general). While that would save you 1 byte here (remove t before YT), it can't be exploited because the change in the language postdates the challenge. But it has the effect that your answer is no longer valid in the new release, which is now live in TIO

You can either edit the linked code and leave a note, or use this link to the  to MATL Online interpreter, which supports older releases. Unfortunately you also need to update the other links. Sorry for the inconvenience

Irrespective of that, you can save 1 byte replacing n: by f

Ruby, 66 bytes
->a{i=-1;a.map{|e|i+=1;[a[j=i+e]||0,a[0>(k=i-e)?j:k]||0].max}.max}

Octave / MATLAB, 40 Bytes
@(v)max(v(any(toeplitz(1:nnz(v))-v==1)))

Input must be a column vector.
Thanks to Luis Mendo for suggestions saving 3 bytes (see comment)
Thanks to Suever for suggestions saving 4 more bytes (replacing ~~(sum()) with any())
Explanation:
Given an input vector v, this problem is equivalent to finding all solutions i,j of the following discrete equation,
abs(i-j) = v(i),   i,j both in 1..k,

where abs() is the absolute value function. Each v(i) for which this equation is solved is one of the candidate solutions which we can maximize over.
As a discrete function of i and j, all possibilities for the left hand side can be arranged in the toeplitz matrix that looks something like this:
[0, 1, 2, 3, 4]
[1, 0, 1, 2, 3]
[2, 1, 0, 1, 2]    <--- abs(i-j)
[3, 2, 1, 0, 1]
[4, 3, 2, 1, 0]

And since the right hand side doesn't depend on i, all possibilities for it can be arranged into a matrix where the columns are all copies of the input,
[v(1), v(1), v(1), v(1), v(1)]
[v(2), v(2), v(2), v(2), v(2)]
[v(3), v(3), v(3), v(3), v(3)]   <--- v(i)
[v(4), v(4), v(4), v(4), v(4)]
[v(5), v(5), v(5), v(5), v(5)]

To find all solutions to the equation, we subtract these two matrices and find the locations where there is a zero. The rows where there is a zero correspond to the desired indices i's where there is a j such that abs(i-j) = v(i).
Other tricks:

It takes less characters to construct the absolute value function plus one, abs(i-j)+1, then check for locations where the difference is 1, rather than construct the true (unshifted) absolute value function.
Uses automatic operator broadcasting to implicitly make column copies of v
Gets the length of the input via nnz() instead of length(), which works since the inputs are said to be positive in the problem statement.

Input format is flexible by default. You can take v as a column vector, just state that in the answer. Also, you replace find by ~~ to save two more bytes

@LuisMendo Thanks, I edited the post to incorporate your suggestions!

For different languages (or a significantly different approach in the same language) you should post another answer. There's a MATL chatroom should you have any questions regarding the language

BTW, due to a bug in MATL's toeplitz (YT), it uses two inputs (not one) by default

Ok cool. I translated it to MATL and posted another answer here: http://codegolf.stackexchange.com/a/94183/42247

Python, 58 bytes
Based on Tony S.'s Ruby answer. This answer works in Python 2 and 3. Golfing suggestions welcome.
lambda n:max([n[i+v]for i,v in enumerate(n)if i+v<len(n)])

Ungolfing
def f(array):
    result = []
    for index, value in enumerate(array):
        if index + value < len(array):
            result.append(array[index + value])
    return max(result)

56 bytes: lambda n:max(n[i+v]for i,v in enumerate(n)if i+v<len(n))

Mathematica, 69 bytes
Max@MapIndexed[{If[#2[[1]]>#,a[[#2-#]],{}],a[[#2+#]]~Check~{}}&,a=#]&

Anonymous function. Takes a list of integers as input and returns an integer as output. Ignore any messages generated.

Scala, 94 bytes
a=>a.zipWithIndex.filter(p=>a.zipWithIndex.exists(x=>x._1==Math.abs(p._2-x._2))).unzip._1.max

PHP, 128 Bytes
<?foreach(($i=$_GET[i])as$k=>$v){$k-$v<0?:!($i[$k-$v]>$m)?:$m=$i[$k-$v];if($k+$v<count($i))if($i[$k+$v]>$m)$m=$i[$k+$v];}echo$m;

Java 7, 125 123 bytes
int c(int[]a){int r=0,i=0,l=a.length,x;for(;i<l;r=l>(x=i+a[i])?a[x]>r?a[x]:r:r,r=(x=i-a[i++])>0?a[x]>r?a[x]:r:r);return r;}

2 bytes saved thanks to @mrco.
Ungolfed (sort of) & test code:
Try it here.
class M{
  static int c(int[] a){
    int r = 0,
        i = 0,
        l = a.length,
        x;
    for(; i < l; r = l > (x = i + a[i])
                      ? a[x] > r
                         ? a[x]
                         : r
                      : r,
                 r = (x = i - a[i++]) > 0
                      ? a[x] > r
                         ? a[x]
                         : r
                      : r);
    return r;
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 1, 13 }));
    System.out.println(c(new int[]{ 2, 9, 8, 3, 72, 2 }));
    System.out.println(c(new int[]{ 5, 28, 14, 5, 6, 3, 4, 7 }));
    System.out.println(c(new int[]{ 1, 3, 5, 15, 4, 1, 2, 6, 7, 7 }));
    System.out.println(c(new int[]{ 5, 1, 3, 5, 2, 5, 5, 8, 5, 1, 5, 1, 2, 3 }));
    System.out.println(c(new int[]{ 5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5 }));
  }
}

Output:
13
8
14
7
5
10

You don't need x & y. Just reuse one of them(-2).
Also i don't think you can set r in a huge ternary-if because you always have to test both cases, left and right.

@mrco Thanks, removed the ,y. And I indeed came to the same conclusion regarding the single ternary if. Of course it is possible, but you'll do the check twice making it a lot longer.

JavaScript (ES6),  56 54  53 bytes
l=>l.map((n,i)=>m=Math.min(m,~l[i+n],~l[i-n]),m=0)|~m

Try it online!

Java, 118 bytes
int f(int[]a){int t=0,i,j,z=0,l=a.length;while(t<l*l){i=t/l;j=t++%l;z=a[i]>z&&((i<j?j-i:i-j)==a[j])?a[i]:z;}return z;}

Welcome to PPCG! :)

Actually, 17 bytes
This answer is an Actually port of my Python answer. Golfing suggestions welcome. Try it online!
;╗ñ♂Σ⌠╜l>⌡░⌠╜E⌡MM

Ungolfing
         Implicit input L.
;╗       Duplicate L and save a copy of L to register 0.
ñ        enumerate() the other copy of L.
♂Σ       sum() all the pairs of [index, value of n]. Call this list Z.
⌠...⌡░   Push values of Z where the following function returns a truthy value. Variable v_i.
  ╜        Push L from register 0.
  l        Push len(L).
  >        Check if len(L) > v_i.
⌠...⌡M   Map the following function over Z_filtered. Variable i.
  ╜        Push L from register 0.
  E        Take the ith index of L.
M        max() the result of the map.
         Implicit return.

Ruby 56 bytes
My smallest ruby solution.
->n{x=[];i=0;n.map{|v|x<<n[v+i]&&v+i<n.size;i+=1};x.max}

Pretty easy to test in rails console
a = ->n{x=[];i=0;n.map{|v|x<<n[v+i]&&v+i<n.size;i+=1};x.max}
a[[1, 13]
=> 13
a[[2, 9, 8, 3, 72, 2]]
=> 8
a[[5, 12, 2, 5, 4, 7, 3, 3, 6, 2, 10, 5, 5, 5, 4, 1, 8, 5]]
=> 10

This started at 63 bytes, thanks for the suggestions to help trim it down!

you can use .map instead of .each

also (x) if (y) can be replaced with (y)&&(x)

You can use a<<b instead of a+=[b]

@Sherlock9 I forgot about << . Using a+=[b] didn't work with Cyoce's suggestion using &&. Now it does, thanks!

T-SQL(sqlserver 2016), 132 bytes
Golfed:
;WITH C as(SELECT value*1v,row_number()over(order by 1/0)n FROM STRING_SPLIT(@,','))SELECT max(c.v)FROM C,C D WHERE abs(D.n-C.n)=D.v

Ungolfed:
DECLARE @ varchar(max)='2, 9, 8, 3, 72, 2'

;WITH C as
(
  SELECT
    value*1v,
    row_number()over(order by 1/0)n
  FROM
    STRING_SPLIT(@,',')
)
SELECT
  max(c.v)
FROM
  C,C D
WHERE
  abs(D.n-C.n)=D.v

Fiddle

Clojure, 68 bytes
#(apply max(map(fn[i](get % i 0))(flatten(map-indexed(juxt - +)%))))

For example (map-indexed (juxt - +) [3 4 1 2]) is ([-3 3] [-3 5] [1 3] [1 5]) (index +/- its value), these are used to look-up values from the original vector (out-of-range defaulting to 0) and the max value is found. Still feels a bit verbose but at least I got to use juxt :)

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

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


text:
Make An ASCII Poker Chip Stack Arrangement
Poker has etiquette in how you arrange your chips, often enforced in tournaments - your chips may not be "hidden" from your opponents by being behind others, mostly to not hide some large denomination chip(s).

The Challenge
We are going to be playing poker in ASCII, so we need to write a function or program that will draw our ASCII chip stack arrangement given its total value, n.
Input
- A positive integer, n (up to 2**32-1 should be handled)
Output
- An ASCII representation of the stack arrangement as defined below.
This may contain white-space to the right of each line such that no line is longer than one more character than the length used by printable characters in the longest (bottom) line;
This may contain a single trailing new line; and
The characters representing chips may be in lowercase if you prefer.
The stack arrangement will:

Contain the fewest chips possible, given the denominations (see below);
Will have equal valued chips in "stacks" (columns);
Be ordered such that the shorter stacks are to the right of taller stacks; and
Be ordered such that stacks with greater denomination chips will be to the right of equal sized stacks of lower denominations (representing that they are visible to our opponent(s) on the right)

The chips themselves are to be represented as individual characters identifying their colour:
    White : 1    = W
      Red : 5    = R
    Green : 25   = G
    Black : 100  = B
   Yellow : 500  = Y
     Pink : 1K   = P
   Orange : 5K   = O
     Cyan : 25K  = C
  Magenta : 100K = M
Aqua-blue : 500K = A
 Lavender : 1M   = L
   Indigo : 5M   = I
Turquoise : 25M  = T
   Violet : 100M = V
   Silver : 500M = S

Example
For n = 276,352 the smallest number of chips would be:
2 * 100K + 3 * 25K + 1 * 1K + 3 * 100 + 2 * 25 + 2 * 1
    MM         CCC       P        BBB       GG       WW

The single P must go on the far right,
then the three stacks of size 2 must go next,
- but the MM must go furthest to the right followed by the GG and then the WW since 100K > 25 > 1
then the two stacks of size 3 go on the left,
- but the CCC must go to the right of the BBB since 25K > 100
Now we must place these chips into actual stacks, to make our output:
BC
BCWGM
BCWGMP

Test Cases
Input:
1

Output:
W

Input:
9378278

Output:
L
LWGPCM
LWGPCMB
LWGPCMBI

Input:
22222222

Output:
ROI
ROI
ROIWBPML
ROIWBPML

Input:
1342185143

Output:
WRCIV
WRCIVOLS
WRCIVOLSGBMT

Input:
2147483647

Output:
RMIS
RMISPC
RMISPCWL
RMISPCWLGBYOTV

Input:
4294967295

Output:
S
S
S
S
SRML
SRMLGOIT
SRMLGOITBPCV
SRMLGOITBPCVA

This is code-golf, so shortest code in bytes wins. No loopholes, yada yada, you know the drill.

Wow, this looks fun, I may try a Julia answer when i get home.

Did you mean 2**31-1, or is your intent to be larger than most signed int types?

@Linus hmm, I made it unsigned; I did actually specifically ask if the input range was OK in the sandbox and no one responded. As you can see 2**32-1 is a test case, but I'm willing to lower it. (Interesting fact: PokerStars has a 25B chip in their image folder.)

Pyth, 56 55 52 bytes
The code contains some unprintables, so here's a reversible xxd hexdump.
00000000: 3d48 516a 5f2e 745f 2023 6c44 2a56 2e22  =HQj_.t_ #lD*V."
00000010: 4159 261c 0c24 2087 0c86 1e22 6d68 412e  AY&..$ ...."mhA.
00000020: 4448 645f 2e75 2a4e 5950 2a33 6a37 3733  DHd_.u*NYP*3j773
00000030: 3620 362f                                6 6/

Try it online. Test suite.
Pro tip: to golf  1 in the end of a program accepting a nonzero number in Q, just add /. /QQ, which in Python would be Q // Q, is 1 for nonzero Q.
Without compression and unprintables (55 bytes):
=HQj_.t_ #lD*V"SVTILAMCOPYBGRW"mhA.DHd_.u*NYP*3j7736 6/

JavaScript (ES6), 185 177 ... 171 bytes
f=(a,s='')=>(a=(a[0]?a:[...(m='25455')+m+m].map((m,i)=>(a-=(k=a/(v/=m)|0)*v,k*16+i),v=1E9).sort((a,b)=>b-a)).map(n=>n>15&&(s+='SVTILAMCOPYBGRW'[n&15],n-16)),s&&f(a)+`
`+s)

Formatted and commented
(a, s = '') => (                           // a = bankroll OR array of chip stacks
  a = (                                    // s = string of chip initials for this iteration
    a[0] ?                                 // if 'a' already is an array:
      a                                    // use it as-is
    :                                      // else, 'a' is the bankroll:
      [...(m = '25455') + m + m]           // for each 'm' in [ 2, 5, 4, 5, 5, ... ] (x3)
      .map((m, i) =>                       // v = current chip value = previous value / m
        (                                  // k = floor(a / v) = number of these chips
          a -= (k = a / (v /= m) | 0) * v, // update remaining bankroll: a = a - k * v
          k * 16 + i                       // saved in array: chip index in bits 0-3
        ),                                 // and number of chips in bits 4+
        v = 1E9                            // initial chip value = 1 billion
      )                                    // (1B / 2 -> 500M, 500M / 5 -> 100M, etc.)
      .sort((a, b) => b - a)               // sort the chip stacks
  )                                        //
  .map(n =>                                // for each chip stack:
    n > 15 &&                              // if there's at least one remaining chip of
    (                                      // this kind:
      s += 'SVTILAMCOPYBGRW'[n & 15],      // append its initial to the string
      n - 16                               // decrement the number of chips in this stack
    )                                      //
  ),                                       // process recursive call if there was at least
  s && f(a) + '\n' + s                     // one non-empty chip stack (the next lines are
)                                          // appended at the beginning of the final string)

Demo

let f=(a,s='')=>(a=(a[0]?a:[...(m='25455')+m+m].map((m,i)=>(a-=(k=a/(v/=m)|0)*v,k*16+i),v=1E9).sort((a,b)=>b-a)).map(n=>n>15&&(s+='SVTILAMCOPYBGRW'[n&15],n-16)),s&&f(a)+`
`+s)

function update() {
  document.getElementById('o').innerHTML = f(+document.getElementById('i').value);
}
update();
<input id="i" value="1342185143" oninput="update()">

Ruby, 181 177 bytes
->n{*a=5*10**8
14.times{|i|a<<a[-1]/[5,4,5,5,2][i%5]}
a=a.zip("SVTILAMCOPYBGRW".chars).map{|v,c|[-(n/v),v,c,n%=v]}.sort
l=-a[0][0]
(1..l).map{|i|a.map{|d|l-i<-d[0]?d[2]:""}*""}}

Tests on Ideone.

Python 2.7, 282 248 238 bytes
c=input();L=[]
for i in range(15):m=[5,1,25,5,1][i%5]*10**int("886665533322000"[i]);L+=[[c/m,i,"SVTILAMCOPYBGRW"[i]]];c%=m
L.sort();S=[]
while L[~1][0]:
 s=""
 for X in L[::-1]:
  if X[0]>0:X[0]-=1;s+=X[2]
 S+=[s]
for s in S[::-1]:print s

Explanation:
Fill list L with elements [quanity, chip_order, chip_character] indicating the quantity of each type of chip , where chip_order ensures chips of equal quantity get sorted in reverse order (higher value chips first). Take chips from L in reverse to build strings for each line. Print lines in reverse to get smallest lines on top.
Thanks to Blue for some of the improvements.

Great answer! However, there are a couple things you can do to golf it more. First, you can put multiple statements on one line by separating them by semicolons (but not statements that require indents after). Second, if you only use a variable once (like X, Y and S in the first for loop), you can just substitute the raw value to save some bytes. For more tips, check out http://codegolf.stackexchange.com/questions/54/tips-for-golfing-in-python

Also, regular input will get you the integer w/o having to convert, and X[0]>0 can be shortened to X[0]

@Blue, thanks I hate python's input. I'll check the tips and see if I can come up with anything else.

Mathematica, 440 bytes
n=Input[]
c=Characters["SVTILAMCOPYBGRW"]
l=Reap[Do[n=n-#[[-i]]*Sow[Floor[n/#[[-i]]]]&@FoldList[Times,1,{5,5,4,5,2,5,5,4,5,2,5,5,4,5}],{i,1,15}]][[2,1]]
StringJoin@@((StringJoin[#,"\n"])&/@StringJoin/@Reverse/@((PadRight[#,Max[l],""]&/@Sort[Table[If[l[[n]]>0,Table[c[[n]],l[[n]]],Nothing],{n,1,15}],If[Length[#1]==Length[#2],Position[c,#1[[1]]][[1,1]]<Position[c,#2[[1]]][[1,1]],Length[#1]<Length[#2]]&])[[All,#]]&/@Range[Max[l]])//Reverse)

The ASCI-representation and right order swallows most of the code.
*Only works with Version11 and higher (use of Nothing)*

Is there really no free Mathematica?!

You can currently use it online at: https://develop.open.wolframcloud.com/app/

PHP, 274 Bytes
$t=$argv[1];$n=[500,100,25,5,1];$c=YBGRWAMCOPSVTIL;foreach($n as$k=>$v)for($i=0;$i<3;)$r[$v*10**($i*3)]=$c[$k+$i++*5];krsort($r);foreach($r as$v=>$k)$t-=($x[$v]=floor($t/$v))*$v;ksort($x);arsort($x);for($y=max($x);$y;$y--){foreach($x as$k=>$v)if($v>=$y)echo$r[$k];echo"\n";}


text:
The Base in the mix
Input:
A list/array of integers for which each item is in the range of 2-36.
Output:
The sum of the integers (as base 10), where each next integer is in the base of the previous value (starting with a regular base 10).
Example:
Let's say we have an input like this: [4, 12, 34, 20, 14, 6, 25, 13, 33]
Then we have a sum like this:
4    (4  in base-10) +
6    (12 in base-4 ) +
40   (34 in base-12) +
68   (20 in base-34) +
24   (14 in base-20) +
6    (6  in base-14) +
17   (25 in base-6 ) +
28   (13 in base-26) +
42   (33 in base-13)
= 235

Mathematical base explained:
I considered assuming everyone knows how base works, but I'll give a brief example of how it works anyway, just in case. Let's take the 34 in base-12 for example, how did we get 40?
1-34 in regular base-10:
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34
 So, from 1 to 34 is 34 steps in base-10

1-34 in base-12:
 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1A, 1B, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 2A, 2B, 30, 31, 32, 33, 34
 So, from 1 to 34 is 40 steps in base-12

Here is perhaps a useful calculator.
Challenge rules:

Array size will be in reasonable range (like 1-100 / see test cases).
The test cases will never contain integers of which the current value is invalid for it's previous base (i.e. You will never have something like 19 in base-6 or 6 in base-6, because base-6 only contains the digits 0-5).
You can take the input any way you'd like. Can be as an int-array, as a comma/space-separated string, etc. Your call. (You are also allowed to take the int-array reversed, which could be useful for stack-based programming languages.)

General Rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-golfing languages. Try to come up with as short an answer as possible for any programming language.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, please add an explanation if necessary.

Test cases:
[4, 12, 34, 20, 14, 6, 25, 13, 33]                            ->   235
 4+ 6+  40+ 68+ 24+ 6+ 17+ 28+ 42

[5, 14, 2, 11, 30, 18]                                        ->   90
 5+ 9+  2+ 3+  33+ 38

[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10]    ->   98
 12+ 13+ 11+ 9+ 8+ 7+ 6+ 5+ 4+ 3+ 5+  2+ 3+  3+ 3+  2+ 2

[36, 36]                                                      ->   150
 36+ 114

For stack based languages which have a LIFO container, can the input be given in reversed order? In dc I would require ~30 bytes just to flip the stack to have the first number in the input be the first one to be processed, which non-stack based languages have by default.

@seshoumara Why not. I'll clarify this in the challenge. It's mainly about the challenge and output, and not really about the input-format.

05AB1E, 7 6 5 bytes
Uses the 05AB1E encoding.
Saved 1 byte using the new built-in š as suggested by Kevin Cruijssen
TšüöO

Explanation
Input list is taken reversed, as allowed by challenge specification.
Tš     # prepend a 10 to the list
  üö   # reduce by conversion to base-10
    O  # sum

Try it online!
Modified testsuite

Can be 5 bytes now with the builtin š instead of ¸ì. Also, your explanation states "append" instead of "prepend". :)

@KevinCruijssen: Thank you :)

Python 3, 40 bytes
lambda a:sum(map(int,map(str,a),[10]+a))

Tests are at ideone
map(str, a) creates a generator, G, that calls str on each value in a, converting to strings
map(int, G, [10]+a) creates a generator that calls int(g, v) for pairs across G and [10]+a
int(g, v) converts the string g from the integer base v (if v is in [2,36] and g is valid)
sum does what it says on the tin

Python 2, 48 bytes
lambda a:sum(int(`x`,y)for x,y in zip(a,[10]+a))

Tests are at ideone
zip(a,[10]+a) traverses pairs of the values in a, and the previous value or 10 for the first
the backticks in the int call convert x to a string, s
int(s, y) converts the string s from the integer base y (if y is in [2,36] and s is valid)
sum does what it says on the tin

Perl, 35 34 33 bytes
Includes +2 for -ap
Run with the list of numbers on STDIN:
basemix.pl <<< "4 12 34 20 14 6 25 13 33";echo

basemix.pl:
#!/usr/bin/perl -ap
$\+=$&+"$`$& 10"*/.$/*$`for@F}{

I've been waiting for ages for a chance to use this abuse...
Explanation
The input numbers can have at most 2 digits. A number xy in base b is simply b*x+y. I'm going to use the regex /.$/ so the first digit ends up in $` and the last digit in $&, so the contribution to the sum is $&+$b*$`.
I abuse the fact that for does not properly localize the regex variables (like for example map and while do) so the results of a match in the previous loop is still available in the current loop. So if I'm careful about the order in which I do the operations the base is available as "$`$&", except for the very first loop where I need the base to be 10. So I use "$`$& 10" instead
The way the first $& works is an abuse too since it is actually changed by the /.$/ while it is already on the stack waiting to be added.
The final abuse is the }{ at the end which changes the loop implied by -p from
LINE: while (defined($_ = <ARGV>)) {
    ...code..
}
continue {
    die "-p destination: $!\n" unless print $_;
}

to
LINE: while (defined($_ = <ARGV>)) {
    ...code..
}
{
}
continue {
    die "-p destination: $!\n" unless print $_;
}

Which means $_ will be undefined in the print, but it still adds $\ in which I accumulated the sum. It is also a standard golf trick to get post-loop processing

I'd be really interested in an explanation for those of us with weaker perl-fu!

@m-chrzan Solution fixed and explanation added

PHP, 53 51 bytes
for(;$x=$argv[++$i];$b=$x)$s+=intval($x,$b);echo$s;

Iterates over the input, converting each input to string variant. Then takes the integer value using the previous number as base. For the first number, the base will not be set, PHP will then start off with 10 (inferred from the number format).
Run like this (-d added for aesthetics only):
php -d error_reporting=30709 -r 'for(;$x=$argv[++$i];$b=$x)$s+=intval($x,$b);echo$s;' -- 12 11 10 9 8 7 6 5 4 3 12 2 11 3 10 2 10;echo

Tweaks

Actually, no need to convert to string, as CLI arguments are already string. Saved 2 bytes.

Java 7, 109 89 86 bytes
int c(int[]a){for(Byte i=1;i<a.length;a[0]+=i.valueOf(a[i]+"",a[++i-2]));return a[0];}

Golfed 20 bytes thanks to @cliffroot (of which 12 because of a stupid mistake I made myself).
Ungolfed & test code:
Try it here.
class M{
  static int c(int[] a){
     for(Byte i = 1; i < a.length; a[0] += i.valueOf(a[i]+"", a[++i-2]));
     return a[0];
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 4, 12, 34, 20, 14, 6, 25, 13, 33 }));
    System.out.println(c(new int[]{ 5, 14, 2, 11, 30, 18 }));
    System.out.println(c(new int[]{ 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10 }));
    System.out.println(c(new int[]{ 36, 36 }));
  }
}

Output:
235
90
98
150

Do you really need p? The sum can be computed like this, can't it: r+=r.valueOf(""+a[i],a[i-1])?

used conversion +"" instead of valueOf and removed unnecessary variables – int c(int[]a){for(Integer i=1;i<a.length;a[0]+=i.valueOf(a[i]+"",a[++i-2]));return a[0];}

@cliffroot Ah, I'm an idiot.. When I was testing I made a mistake and had the 10 and p reversed. I realized the mistake and fixed it, but since the String part is now regular base-10 I can indeed remove the toString and just use +"".. Thanks, and also thanks for golfing the other things, -20 bytes. I really gotta make an answer you can't golf more (not that I don't appreciate it! the shorter the better of course - in code-golfing that is ;P)

Just to compare with my answer, yours in current Java's syntax is 79 bytes long (mine is presently 86 bytes long). But that's not fun taking others' code ;)

@OlivierGrégoire Feel free to post it as a separate answer. 86 bytes is still shorter than my previous 109 (-12 because of an obvious mistake, so 97) answer.

@cliffroot Btw, don't you mind that I edit your answer every time? If you post it as a separate answer you definitely get my (and other) upvotes for more rep. It's unfortunate comment upvotes aren't worth any rep..

@KevinCruijssen , I'm more than fine with it :) I just feel that realistically Java does not compete with all that 5-6 bytes solution, so I don't add my own answers often, but I still find it fun to golf down others' solution.

Jelly, 7 bytes
ṙ1DḅṖḌS

Try it online!

You could replace ṖḌ with F

Unfortunately, that won't work in the first number has two digits.

JavaScript ES6, 45 42 41 Bytes

const g =
     a=>a.map(v=>s+=parseInt(v,p,p=v),s=p=0)|s
;

console.log(g.toString().length);                                            // 42
console.log(g([4, 12, 34, 20, 14, 6, 25, 13, 33]));                          // 235
console.log(g([5, 14, 2, 11, 30, 18]  ));                                    // 90
console.log(g([12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10] )); // 98

Conventiently parseInt(x,0) === parseInt(x,10).
edit: Saved 1 byte thanks to @ETHproductions

Nice! I think you can save a byte by replacing &&s with |s.

You can also replace const g with just g

Java, 86 bytes
s->{int[]b={10};return s.reduce(0,(r,n)->{r+=n.valueOf(""+n,b[0]);b[0]=n;return r;});}

Testing and ungolfed
import java.util.function.ToIntFunction;
import java.util.stream.Stream;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<Stream<Integer>> f = s -> {
      int[] b = {10};                 // Base, initialized with 10
      return s.reduce(0, (r, n) -> {  // Typical use of reduction, sum starts with 0.
        r += n.valueOf("" + n, b[0]); // Add the value in the previous base.
        b[0] = n;                     // Assign the new base;
        return r;
      });
    };

    System.out.println(f.applyAsInt(Stream.of(new Integer[]{4, 12, 34, 20, 14, 6, 25, 13, 33})));
  }
}

Pure bash, 38
b=10
for i;{((t+=$b#$i,b=i));}
echo $t

The input list is given at the command-line.  for i; automatically iterates over the input parameters (equivalent to for i in $@;).
Ideone.

Actually, 12 bytes
;p(dX(♂$♀¿Σ+

Try it online!
Explanation:
;p(dX(♂$♀¿Σ+
;             dupe input
 p            pop first element from list
  (dX         pop and discard last element from other copy
     (♂$      stringify all elements in first copy
        ♀¿    for each pair of elements in the two lists, interpret the first element as a base-(second element) integer
          Σ   sum
           +  add first element of original list

CJam, 15 bytes
l~{A\:A10bb}%:+

Try it online!
Explanation
l~     e# Read and evaluate input.
{      e# Map this block over the input...
  A    e#   Push A. Initially this is 10, afterwards it will be the value of the
       e#   last iteration.
  \:A  e#   Swap with current value and store that in A for the next iteration.
  10b  e#   Convert to base 10 to get its decimal digits.
  b    e#   Interpret those in the base of the previous A.
}%
:+     e# Sum all of those values.

JavaScript (ES6), 54 48 40 bytes
I used a recursive approach.
f=([b,...a],c)=>b?parseInt(b,c)+f(a,b):0

Saved 6 bytes, thanks to Lmis!
Saved 8 more bytes, thanks to Neil!

I think you can save 3 bytes by using parseInt(a,b) instead of parseInt(a[0],b) since parseInt converts the first argument to string and ignores everything starting at the first invalid character (i.e. ',').

I also think you can save some bytes by using a[0]?stuff():0 instead of a.length&&stuff()

@Lmis Thanks, I've updated it :)

I think you can shorten this to 40 bytes: f=([b,...a],c)=>b?parseInt(b,c)+f(a,b):0

@Neil nice way of not using the slice function

Haskell, 65 59 bytes
b%x|x<1=x|y<-div x 10=b*b%y+x-10*y
sum.((10:)>>=zipWith(%))

Test it on Ideone.

Matlab, 68 bytes
Not a very creative solution, but here it is:
function[s]=r(x);j=10;s=0;for(i=x)s=s+base2dec(num2str(i),j);j=i;end

Tests:
>> r([4,12,34,20,14,6,25,13,33])
ans =
   235
>> r([12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10])
ans =
   98
>> r([5, 14, 2, 11, 30, 18])
ans =
   90
>> r([36,36])
ans =
   150

You can save one byte with function s=r(x);...

Perl 6,  52  50 bytes
{sum (10,|@_).rotor(2=>-1).map:{+":{.[0]}<{.[1]}>"}}
{sum (10,|@_).rotor(2=>-1).map:{":{.[0]}<$_[1]>"}}

Explanation:
# bare block lambda with implicit parameter ｢@_｣
{
  sum

    ( 10, |@_ )        # the input with a preceding 10
    .rotor( 2 => -1 )  # grab 2 values, back up one, repeat
    .map:
    {
      # create a string of the form ":10<4>"
      ":{
        .[0]            # first element from $_
      }<{
        .[1]            # second element from $_
      }>"
    }
}

Common Lisp, 83
(lambda(s)(loop for b ="10"then x for x in s sum(#1=parse-integer x :radix(#1#b))))

Details
(defun base-mix (list)
  (loop
     for base = "10" then string
     for string in list
     sum (parse-integer string :radix (parse-integer base))))

The loop construct accepts "v then w" iteration constructs, where v is an expression to be evaluated the first time the iteration variable is computed, and w is the expression to be evaluated for the successive iterations. Declarations are evaluated one after the other, so base is first "10", then the previous element stringof the list list being iterated. The sum keyword computes a sum: the integer read from string with base b, where b is the integer parsed from the base string, in base 10. #1= and #1# are notations to define and use reader variables: the first affects an s-expression to a variable, the other one replaces the reference by the same object. This saves some characters for long names.
Example
(base-mix '("4" "12" "34" "20" "14" "6" "25" "13" "33"))
=> 235

Python 2, 52 bytes
f=lambda x:x[1:]and int(`x.pop()`,x[-1])+f(x)or x[0]

Test it on Ideone.

Julia, 63 Bytes
f(l)=sum([parse(Int,string(l[i]),l[i-1])for i=2:length(l)])+l[]

Parses each number (except the first) taking the previous element as base and sums. Adds the first element at the end

Ruby, 52 bytes
->a{eval a.zip([10]+a).map{|e|'"%s".to_i(%s)'%e}*?+}

ungolfed
->a{
  eval(
    a.zip([10]+a).map { |e|
      '"%s".to_i(%s)' % e
    }.join("+")
  )
}

usage
f=->a{eval a.zip([10]+a).map{|e|'"%s".to_i(%s)'%e}*?+}
p f[[4, 12, 34, 20, 14, 6, 25, 13, 33]] # => 235

Scala, 67 bytes
def f(a:Int*)=a zip(10+:a)map{t=>Integer.parseInt(""+t._1,t._2)}sum

Explanation:
def f(a: Int*) =     //declare a method f with varargs of type Int as parameter
a zip (10 +: a)      //zip a with 10 prepended to a, resulting in...
                     //...Array((4,10), (12,4), (34,12), (20,34), (14,20), (6,14), (25,6), (13,25), (33,13))
map { t =>           //map each tuple t to...
  Integer.parseInt(  //...an integer by parsing...
    ""+t._1, t._2    //...a string of the first item in base-second-item.
  )
}
sum                  //and sum

Mathematica, 59 bytes
I wish Mathematica's function names were shorter. But otherwise I'm happy.
Tr[FromDigits@@@Transpose@{IntegerDigits/@{##,0},{10,##}}]&

For example,
Tr[FromDigits@@@Transpose@{IntegerDigits/@{##,0},{10,##}}]&[4,12,34,20,14,6,25,13,33]

yields 235.
{##,0} is a list of the input arguments with 0 appended (representing the numerals); {10,##} is a list of the input arguments with 10 prepended (representing the bases). That pair of lists is Transposed to associate each with numeral with its base, and FromDigits (yay!) converts each numeral-base pair to a base-10 integer, the results of which are summed by Tr.

Japt -x, 7 bytes
äÏsnX}A

Try it
äÏsnX}A     :Implicit input of array
ä           :Take each consecutive pair of elements
 Ï          :Pass them through the following function as X & Y
  s         :  Convert Y to a base-10 string
   nX       :  Convert to an integer from base-X
     }      :End function
      A     :Before doing any of that, though, prepend 10 to the array
            :Implicit output of the sum of the resulting array