text:
The Alphabet Chromosome
Introduction
Alphabet challenges are in our DNA, so let's show it.
Challenge
Print the following the text exactly:
AaBbCc        cCbBaA
BbCcDd        dDcCbB
EeFfGg        gGfFeE
HhIiJj        jJiIhH
KkLlMm        mMlLkK
NnOoPp        pPoOnN
QqRrSs        sSrRqQ
TtUuVv        vVuUtT
   WwXx      xXwW
       Yy  yY
         ZZ
         zz
         ZZ
       Yy  yY
   WwXx      xXwW
TtUuVv        vVuUtT
QqRrSs        sSrRqQ
NnOoPp        pPoOnN
KkLlMm        mMlLkK
HhIiJj        jJiIhH
EeFfGg        gGfFeE
BbCcDd        dDcCbB
AaBbCc        cCbBaA

Rules

You must match the case of each letter
Trailing and/or leading newlines and/or spaces are allowed

Winning
Shortest code in bytes wins.

It doesn't make much sense that the first two lines both contain B and C when all other lines (bar the mid section) have unique letters.

@Fatalize That's to make the challenge slightly more interesting

I would personally argue it does the opposite

I believe there's a mistake in the 9th line. Should be "WwXx      xXwW", not "WwXx      xXWw", shouldn't it?

You probably should've used the Sandbox to get feedback before posting.

@BetaDecay Fatalize is right, that makes the challenge more boring.

Are trailing spaces allowed per line or only at the text block's end?

Vim (no external tools), 106 bytes
Newlines for clarity:
:h<_↵↵↵YZZPllabc♥
:s/./\u&&/g↵
qa6li↵♥q7@a3i ♥fY
i↵    →→↵  →↵→ð♥
ʌHA ♥9l
qbmaʌ99jY$P`ah@bq@b
y11G:g//m0↵P

Here ↵ is Return, → is Right, ♥ is Escape, ʌ is CTRL-V, and ð is Delete.

PowerShell v2+, 175 169 163 154 bytes
($x=(-join(65..67+66..86|%{$_;32+$_}|%{[char]$_})-split'(.{6})'-ne'')+'   WwXx'+'       Yy'+(' '*9+'Z')|% *ht 10|%{$_+-join$_[9..0]})
' '*9+'zz'
$x[10..0]

Try it online!
Abuses the fact that default Write-Output at the end of execution inserts a newline between elements.
The first line constructs the branches. We loop over two ranges corresponding to the ASCII values for the capital letters, each iteration output a char array of that letter and that letter +32 (which is the lowercase ASCII point). That's -joined together into one long string, then -split on every six elements (encapsulated in parens so they're preserved), followed by a -ne'' to pull out the empty elements as a result of the split, thus forming an array of strings.
These strings in an array get array-concatenation to add on the WwXx, Yy, and Z elements, then a PadRight 10 to make them all the appropriate width. At this point we have an array of strings like the following (one element per line).
AaBbCc
BbCcDd
EeFfGg
HhIiJj
KkLlMm
NnOoPp
QqRrSs
TtUuVv
   WwXx
       Yy
         Z

That whole array is piped to another loop to construct the mirrored strings with -join and array-reversing [9..0].
AaBbCc        cCbBaA
BbCcDd        dDcCbB
EeFfGg        gGfFeE
HhIiJj        jJiIhH
KkLlMm        mMlLkK
NnOoPp        pPoOnN
QqRrSs        sSrRqQ
TtUuVv        vVuUtT
   WwXx      xXwW
       Yy  yY
         ZZ

We save the resulting strings into $x and enclose in parens to also place a copy on the pipeline.
The next line places the zz string on the pipeline, then the $x array in reverse order. All of those are left on the pipeline and output is implicit.
PS C:\Tools\Scripts\golfing> .\alphabet-chromosome.ps1
AaBbCc        cCbBaA
BbCcDd        dDcCbB
EeFfGg        gGfFeE
HhIiJj        jJiIhH
KkLlMm        mMlLkK
NnOoPp        pPoOnN
QqRrSs        sSrRqQ
TtUuVv        vVuUtT
   WwXx      xXwW
       Yy  yY
         ZZ
         zz
         ZZ
       Yy  yY
   WwXx      xXwW
TtUuVv        vVuUtT
QqRrSs        sSrRqQ
NnOoPp        pPoOnN
KkLlMm        mMlLkK
HhIiJj        jJiIhH
EeFfGg        gGfFeE
BbCcDd        dDcCbB
AaBbCc        cCbBaA

-9 bytes thanks to mazzy.

154 bytes - '(.{6})' instead (......) and RightPad instead tail spaces.

Python 2, 230 bytes
s='';m=['AaBbCc','BbCcDd','EeFfGg','HhIiJj','KkLlMm','NnOoPp','QqRrSs','TtUuVv','   WwXx',' '*7+'Yy',' '*9+'Z'];
p=lambda l:l.ljust(10)+l[::-1].rjust(10)+'\n';
for l in m:s+=p(l);
s+=' '*9+'zz\n';
for l in m[::-1]:s+=p(l)
print s

Remove semicolon from second, third and fourth lines 2) Remove the newline at the end of the first line 3) Enjoy your answer being shorter than daHugLenny's 4) Since nobody said it yet, welcome to PPCG!

Python 2, 156 bytes
r=('AaBbCc.BbCcDd.EeFfGg.HhIiJj.KkLlMm.NnOoPp.QqRrSs.TtUuVv.   WwXx.%8cy.%10c.%10c'%(89,90,'z')).split('.')
for k in r+r[-2::-1]:s='%-10s'%k;print s+s[::-1]

Try it online!
Maybe the formula 512/(i**4+47)-1 is of interest to future golfers: it maps the integers around 0 to $$\cdots,-1,-1,0,3,7,9,\fbox{9},9,7,3,0,-1,-1,\cdots$$
which encodes how many spaces to prepend to each line ((-1)*' ' being equal to 0*' ').

Python 2, 331 241 229 bytes
Will golf it more later.
l=("AaBbCc|BbCcDd|EeFfGg|HhIiJj|KkLlMm|NnOoPp|QqRrSs|TtUuVv|   WwXx|%sYy"%(" "*7)).split("|");n=0;v=1;p='for i in([8]*8+[6,2])[::v]:print l[n]+" "*i+l[n][::-1];n+=v';exec p;v=-1;n=9;print"{0}ZZ\n{0}zz\n{0}ZZ".format(" "*9);exec p

Lua, 212 Bytes
s=([[         Z
       Yy
   WwXx
TtUuVv_QqRrSs_NnOoPp_KkLlMm_HhIiJj_EeFfGg_BbCcDd_AaBbCc    ]]):gsub("_","    \n")S="         zz"for z in s:gmatch"[%w ]+"do k=z..z:reverse()S=k..'\n'..S..'\n'..k end print(S)

Simple enough, based off of TimmyD's answer, kind of.
Builds the top left arm using a really poorly compressed chunk,
then does both mirrors at once around a 'zz', and prints.
Try it on Repl.It

Stax, 42 41 38 35 bytes
înáöêòé{V║»╧å╓ä¥ì√‼╦▓°nlΓΣ▌ê9t☻*$╢√

Run and debug it
Update: There was a bug in the 41 byte solution. (yes, even though it has no input)  While fixing it, I found 3 more bytes to shave.
Update again: There's competition afoot, so I removed 3 more contingency bytes.
Explanation: (of a different, yet identically sized solution)
VA3(        "ABC"
VAD2T       "BCD...VWX"
+3/         concatenate and split into groups of 3
'Y]+        concatenate ["Y"]
{cv\$m      map each string using: copy, lowercase, zip, flatten
.ZzM+       concatenate ["Z", "z"]
|p          palindromize list of strings
m           map each string _ using the rest of the program and implicitly print output
  c%Nh6+H   (-len(_)/2 + 6) * 2
  )         left-pad (npm lol amirite) to length
  A(        right-pad to 10
  :m        mirror (a + a[::-1])

Run this one

05AB1E, 48 46 40 38 36 bytes
Ž3ô8.DƵJ6XD)bTj»0ð:1žRAu¦«Dl.ιS.;º.∊

-2 bytes (and the opportunity for 10 more with this alternative approach) thanks to @MagicOctopusUrn.
Try it online.
Explanation:
Ž3ô            # Push compressed integer 1008
   8.D         # Duplicate it 8 times
      ƵJ       # Push compressed integer 120
        6      # Push 6
         XD    # Push 1 twice
           )   # Wrap all into a list
b              # Convert each to binary
 Tj            # Add leading spaces to each binary-string to make them size 10
   »           # Then join all strings by newlines
0ð:            # Replace all 0s with spaces
 žR            # Push the string "ABC"
   Au¦«        # Merge the uppercased alphabet minus the first "A" with it
       Dl      # Create a lowercase copy
         .ι    # Intersect the uppercase and lowercase strings: "AaBbCcBb..."
           S   # Convert it to a list of characters
1           .; # Replace every 1 with each of these characters in the same order
º              # Then mirror everything vertically without overlap,
 .∊            # and horizontally with the last line overlapping
               # (and output the result implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž3ô is 1008 and ƵJ is 120.

-2 bytes using a mask approach: •3ô•8.D120 6 1D)bí.Bí»…abcA¦«Dus.ιv1y.;}0ð:º.∊

@MagicOctopusUrn Ah nice, and with some compression and the builtin "abc" it can be golfed by 6 more: •3ô• can be Ž3ô; 120 6 1D can be ƵJ6XD; …abcA¦«Dus.ι can be žRAu¦«Dl.ι. :)

Wow, nice improvements, I knew there had to be a better way to make that array.

@MagicOctopusUrn Oh, and 2 more by changing í.Bí to Tj (only works in the new version, but not sure if its a bug or intentional). So implicitly you enabled a 10-bytes save in total with your alternative approach. :D

You gotta find one more to win ;).

@MagicOctopusUrn Fine, 2 more removed. ;p And žRAu¦«Dl.ιS could alternatively be A¬žR:uSDl.ι, but unfortunately that won't save bytes. And 0м.B instead of 0ð: is a byte more instead of less.. Kinda hoped the mirrors might implicitly box by adding trailing spaces so the .B wouldn't be necessary, but maybe it's better they don't for other challenges I guess.

@KevinCruijssen: You'll need 2 more again. :)

@recursive Hehe. :) Not sure if I'm able to find something for -2. -1 might still be possible. Had already upvoted your Stax answer last month. Stax byte encryption has an edge here, since I doubt the unencrypted source code is shorter? ;) Btw, could you add an explanation to your answer. Curious to see your approach.

@KevinCruijssen: The unpacked stax source is now at 42 bytes.  The packing concept is kind of a double-edge sword, since it makes the primary symbol alphabet smaller at the same time as reducing their effective packed size.  One character instructions from printable ascii are roughly ~6.5 bits after packing, but non-ascii characters aren't usable.  I decided to do it that way to keep that langauge easily type-able.
I will add an explanation today.

@recursive If you remove 6 more bytes from the unpacked version, I'll try to remove 2 ;p And I indeed understand the value of the unpacked vs packed version. I now copy non-ASCII characters almost every time, whereas languages like Japt or unpacked Stax could just type them. :)

@KevinCruijssen: Hah.  I'll try!

@KevinCruijssen: Added an explanation, although I can't shake the feeling there is some additional bloat in there somewhere.

Matricks, 105 bytes (noncompeting)
Whoa, I found a lot of bugs. The only hard part of this challenge was the cross in the middle. That makes almost half the byte count.
Run with the -A 1 flag
m+/c2+66+*r3*32%c2 7 6v{k-{}1z-L1Q}u{q-Lc2k+{}2b0b0b0a[a0a0u[a89a121]a[u0u90]]}a{Y}u[mQc9a122a122]u{z1cX}

Explanation:

m+/c2+66+*r3*32%c2 7 6                       # Construct the "normal" block
v{k-{}1z-L1Q}                                # Add the "abnormal" part above
u{q-Lc2k+{}2b0b0b0a[a0a0u[a89a121]a[u0u90]]} # Make the 1/4 of the weird diagonal
a{Y}u[mQc9a122a122]u{z1cX}                   # Mirror the block just created, adding
                                             # lowercase zs in between halves

Another bug I haven't fixed yet is that the last part, u{z1cX} doesn't work when you put the cut after the X. Will investigate/fix.

///, 229 bytes
/*/\/\///^/        *0/AaBbCc^cCbBaA
*1/BbCcDd^dDcCbB
*2/EeFfGg^gGfFeE
*3/HhIiJj^jJiIhH
*4/KkLlMm^mMlLkK
*5/NnOoPp^pPoOnN
*6/QqRrSs^sSrRqQ
*7/TtUuVv^vVuUtT
*8/   WwXx      xXwW
*9/       Yy  yY
/0123456789^ ZZ
^ zz
^ ZZ
9876543210

Try it online!

PowerShell, 150 bytes
($x='AaBbCc
BbCcDd
EeFfGg
HhIiJj
KkLlMm
NnOoPp
QqRrSs
TtUuVv
   WwXx
       Yy
         Z'-split'
'|% *ht 10|%{$_+-join$_[9..0]})
' '*9+'zz'
$x[10..0]

Try it online!

Brainfuck, 456 bytes
+[>-[-<]>>]>[->++>++++++>++++>+<<<<]>>+>+>------<.<.>+.<+.>+.<+.<........>.>.<-.>-.<-.-->-.-->.>+++++++[-<<+++.<+++.>+.<+.>+.<+.<........>.>.<-.>-.<-.>-.>.>]<<<<...>>+++.<+++.>+.<+.<......>.>.<-.>-.>.<<<.......>>++.<++.<..>.>.>.<<<.........>>+..>.<<<.........>+..>>.<<<.........>>..>.<<<.......>>-.<-.<..>.>.>.<<<...>>--.<--.>+.<+.<......>.>.<-.>-.>.>+++++++[-<<---.<---.>+.<+.>+.<+.<........>.>.<-.>-.<-.>-.>.>]<<-.<-.>+.<+.>+.<+.<........>.>.<-.>-.<-.>-.

Try it online!

Python 3, 215 bytes (Non-Competing)
p=lambda l:l.ljust(10)+l[::-1].rjust(10)
a=("AaBbCc|BbCcDd|EeFfGg|HhIiJj|KkLlMm|NnOoPp|QqRrSs|TtUuVv|   WwXx|%sYy|%sZ"%(7*' ',9*' ')).split('|')
print('\n'.join([p(x)for x in a]+[' '*9+'zz']+[p(x)for x in a[::-1]]))

Try it online!
Takes some ideas from the two Python 2 solutions, but applies them to an approach using join() that seems to save quite a few bytes. It's possible that this can be golfed further; I might revisit this later.

Note that answers no longer have to be marked non-competing.

@JonathanFrech Python 3 was released long before this challenge. This must have the tag "non-competing" for some other reason.

@pppery One thing I did notice is that this post does not create spaces to fill the chromosome's left-concave region.

@squid May I ask why this answer has been marked non-competing?

Ruby, 177 ...  145 bytes
puts r=(("%s%s%s\n"*8+"%5s%s\n%9s\n%11s")%[*?a..?c,*?b..?z].map{|x|x.upcase+x}).lines.map{|l|l=l.chop.ljust 10;l+l.reverse},"%11s"%"zz",r.reverse

Try it online!

Bubblegum, 168 bytes
00000000: 6dd1 c712 8230 1006 e0fb 3e45 5e85 264d  m....0....>E^.&M
00000010: 7a51 b8a1 14e9 1d91 a757 4632 ce38 9bd3  zQ.......WF2.8..
00000020: e6cb a4ec 1f26 626f dc9d 1ce3 cedd d888  .....&bo........
00000030: 819d f898 62cc ef0c 4272 4ac5 8c62 26a6  ....b...BrJ..b&.
00000040: a744 00e9 21e7 4a41 b150 72f9 2181 5a9e  .D..!.JA.Pr.!.Z.
00000050: 2bad a658 6bd5 b954 416f 8cd6 ec28 7666  +..Xk..TAo...(vf
00000060: 6b34 3a58 bd3d 3823 c5d1 19ec de02 77f2  k4:X.=8#......w.
00000070: 667f a1b8 f8b3 37b9 f0a9 2ecf ebfa b5f5  f.....7.........
00000080: fabc c0b1 1ebc 0879 0574 4648 18fe ea6d  .......y.tFH...m
00000090: c3fc b7e3 ef44 f462 f489 6833 68db 6840  .....D.b..h3h.h@
000000a0: 6894 68e8 0cf2 3d6f                      h.h...=o

Try it online!
Since this is my first Bubblegum submission, it might not be the optimal solution. Please double-check.


text:
The Permutation Pigeon-hole Principle
In the game of sudoku, many players like to "pencil in" possible numbers that can go in each square:

The above row can be represented as an array:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [1,2,4], [8]]

Now, notice that there is only 1 place where a 4 can go.  This effectively lets us simplify the above list to:
[[1,2,9], [6], [5], [7], [1,2,9], [1,2,9], [3], [4], [8]]

The goal of this challenge is to take a list of possible numbers in a permutation, and deduce which possibilities can be eliminated.
As another example, lets say you have the following array of possibilities:
[[0,1,3], [0,2,3], [1,2], [1,2]]

The last two places must be filled with 1 and 2.  Therefore, we can remove those possibilities from the first two elements in the array:
[[0,3], [0,3], [1,2], [1,2]]

As another example:
[[0,1,2,3], [0,2], [0,2], [0,2]]

Its impossible to construct a permutation from the above possibilities, as there's only 1 location for both 1 and 3, and you would want to return an empty array.
You need to input a list of possibilities and output the remaining possibilities after the maximum number of possibilities have been eliminated.

If a particular array is impossible, you either need to return an empty array, or an array where one of the subarrays is empty.
You may assume that the array will be well-formed, and have at least 1 element.
Given an array of size N, you can assume the numbers in the subarray will always be in the range [0:N), and that N <= 10
You may not assume that every number from 0 to N-1 will be present
You may assume that numbers within a single subarray are unique.
If a subarray contains only a single possibility, you can either represent the possibility in an array or by itself.  [[1],[2],[0]], [1,2,0], [[1,2],0,[1,2]] are all valid.
You may accept the array either in a reasonable string format or in list/array format.
Subarrays can be in any order.
Instead of dealing with ragged arrays, you can pad empty places with -1.

Test cases
[[0]]                                         -> [[0]]
[[1],[0]]                                     -> [[1],[0]]
[[1],[1]]                                     -> []
[[1],[0,1]]                                   -> [[1],[0]]
[[0,1,2],[1,2],[1,2]]                         -> [[0],[1,2],[1,2]]
[[0,1],[1,2],[0,2]]                           -> [[0,1],[1,2],[0,2]]
[[2,1],[1,2],[1,2]]                           -> []
[[0,3],[2,1],[3,0],[3,2]]                     -> [[0,3],[1],[0,3],[2]]
[[0,1],[0,1],[2,3],[2,3,0]]                   -> [[0,1],[0,1],[2,3],[2,3]]
[[0,1],[0,3],[3,2],[0]]                       -> [[1],[3],[2],[0]]
[[3,5,2],[0,2,4],[4,0],[0,1,3,5],[2,1],[2,4]] -> [[3,5],[0,2,4],[4,0],[3,5],[1],[2,4]]
[[6,9,8,4],[4,5],[5,3,6],[3,8,6,1,4],[3,1,9,6],[3,7,0,2,4,5],[9,5,6,8],[6,5,8,1,3,7],[8],[8,0,6,2,5,6,3]] -> [[6,9,4],[4,5],[5,3,6],[3,6,1,4],[3,1,9,6],[0,2],[9,5,6],[7],[8],[0,2]]
[[3,5,0],[5,7],[5,1,2],[1,3,0],[5,3],[5,0],[5,3,7,8,0,6],[7,5,0,1,8],[1,0,8],[0,6]] -> []
[[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]] -> [[9,0,2,3,7],[0,7,6,5],[6,9,4,7],[9,1,2,3,0,5],[2,8,5,7,4,6],[6,5,7,1],[5,9,4],[5,9,3,8,1],[5,0,6,4],[0,7,2,1,3,4,8]]
[[2,6,0],[0,4,3],[0,6,2],[0,7],[0,9,2,3,6,1,4],[1,7,2],[2,7,8],[8,6,7],[6,5,2,8,0],[5,8,1,4]] -> [[2,6,0],[3],[0,6,2],[0,7],[9],[1],[2,7,8],[8,6,7],[5],[4]]
[[8],[8,0,6,5,7,2,4,1],[8,6,9,3,5,0,7],[3,9,1,0],[9],[9,2,6],[2,8,3],[3,1,6,8,2],[6],[6,4,5,3,0,7]] -> [[8],[5,7,4],[5,7],[0],[9],[2],[3],[1],[6],[4,5,7]]
[[8,1,0],[5,8,7,6,2,0],[6,8,2],[2,4,0,9],[4,1,7,3,6,8],[8,1],[8,0,3],[0,8,2],[0,8,3],[1,8,0]] -> []

This is a code-golf so make your answers as short as possible!

Any number greater than 9?

You don't need to support numbers greater than 9.

Can I return with duplicates in subarrays?

@LeakyNun no.  Subarrays can only contain unique elements.

I think you've got some mistakes in your fourth test case; one of the sublists is double-bracketed.

@TheBikingViking thanks for the catch!

@edc65 nice catch! Fixed

@edc65 actually, I think my old one was correct.  There are a total of 10 numbers, 0 through 9, but all numbers are less than 10

@edc65 you're right.  N can be 10.

Isn't this challenge just a form of compression? As in, would a simple compression challenge differ from this?

I guess.  It's really not too effective, as most randomly generated sets of possibilities can't be reduced.

I mean, your challenge is somewhat original. It's not just the usual compression challenge.
However, can it be reduced to one?

Yeah, in a broad sense, its a form a lossless compression.

Brachylog, 21 bytes
:1fz:da|,[]
:2a#d
:Am

Try it online!
Try it online!
Predicate 0 (main predicate)
:1fz:da|,[]
:1f            Find all solutions of Predicate 1 using Input as Input.
   z           Transpose
    :da        Deduplicate each.
       |,[]    If there is no solution, return [] instead.

Predicate 1 (auxiliary predicate 1)
:2a#d
:2a     Each element of Output satisfies Predicate 2 with each element of Input as Input
   #d   Each element is different

Predicate 2 (auxiliary predicate 2)
:Am     Output is member of Input

Jelly, 10 bytes
Œp⁼Q$ÐfZQ€

Try it online!
Œp⁼Q$ÐfZQ€   Main chain, argument: z

Œp           Cartesian product
  ⁼Q$Ðf      Filter for those that remain unchanged when uniquified
       Z     Transpose
        Q€   Uniquify each subarray

It seems a bit disingenuous to claim 10 bytes when Jelly uses characters outside of latin1. Represented as UTF-8 the above sequence requires 16 bytes.

@ChrisBecke Jelly has its own charset

And yet - if I try it online! - I need to send 16 bytes.

@ChrisBecke Yes but if you download Jelly you would only have to write a 10-byte program.

And save it in a text file I cannot edit with anything other than Jelly? By that argument if Jelly compressed its program we should only count the compressed bytes?

@ChrisBecke No, Jelly still uses 0x00-0xFF, just that the representation of those bytes are different and requires multiple UTF-8 bytes to represent. Are we required to use existing code pages like CP437?

Pyth, 11 bytes
{MC{I#.nM*F

Try it online!
{MC{I#.nM*F
         *F  reduce by Cartesian product
             produces nested arrays
      .nM    flatten each
   {I#       filter for invariant under deduplication
  C          transpose
{M           deduplicate each

Haskell, 100 bytes
import Data.List
p z=map nub$transpose$filter(and.(flip$zipWith elem)z)$permutations[0..length z-1]

Nice solution! and.flip(zipWith elem)z is shorter

Actually, 27 bytes
Rd╗R`╜∙"♂i"£M╗`MX╜`;╔=`░┬♂╔

Try it online!

Python 3, 101 99 bytes
Thanks to @TLW for -2 bytes
from itertools import*
lambda x:list(map(set,zip(*[i for i in product(*x)if len(i)==len(set(i))])))

An anonymous function that takes input via argument of a list of lists and returns a list of sets.
How it works
from itertools import*        Import Python's library for iterator generation
lambda x                      Anonymous function with input possibilities x as a
                              list of lists
...for i in product(*x)...    For i in the Cartesian product of x, ie all candidate
                              arrangements:
[...if len(i)==len(set(i))]    Filter into list by non-duplicity (set removes
                               duplicates, so there are no duplicates if the length
                               of i is the same as the length of the set of
                               the elements of i)
zip(*...)                     Unpack and take the transpose, leaving the modified
                              possibilities with duplicates
map(set,...)                  Remove duplicates
:list(...)                    Return the modified possibilities as a list of sets

Try it on Ideone

list(map(set, is shorter, I think

Mathematica, 46 bytes
Union/@Thread@Select[Tuples@#,DuplicateFreeQ]&

PHP, 245 231 bytes
131 117 for the cartesian product function, 114 for the other stuff
function c($a){if ($a){if($u=array_pop($a))foreach(c($a)as$p)foreach($u as$v)yield $p+[count($p)=>$v];}else yield[];}
function p($a){foreach(c($a)as$i)if(max(array_count_values($i))<2)foreach($i as$k=>$v)$r[$k][$v]=$v;return$r?:[];}

I ran into memory issues on some of the test cases, with a recursive function for the cartesian product. Worked better with this generator class and function c($a){$b=[];foreach($a as$i)$b[]=new \ArrayIterator($i);return new CartesianProductIterator($b);}.
But my generator is shorter and does the same job.
The larger examples, however, result in an Internal Server Error (both with the iterator and the generator) after a while on my machine. Currently no time to check the server logs, unfortunately.

source: Stack Exchange

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

sort: votes


text:
Find the minimum and maximum integers in an array, without using builtins

Challenge
Given an array of integers, received from stdin, function arguments, program arguments, or some other method:
Output only the minimum and maximum numbers in the array, through a return value, stdout, or other fitting methods.
Example session
> minmax( {0, 15, 2, 3, 7, 18, -2, 9, 6, -5, 3, 8, 9, -14} )
-14 18

Reference implementation
// C++14

void minmax(std::vector<int> v) {
    int min = v[0]; int max = v[0];
    for(auto it : v) {
        if (*it < min)
            min = *it;
        if (*it > max)
            max = *it;
    }
    std::cout << min << ' ' << max << std::endl;
}

Rules

You may not use a built-in function to calculate the values.
Standard loopholes disallowed.
Creative implementations encouraged.
This is code-golf, shortest answer wins but will not be selected.

Clarifications

If the array contains 1 element you need to output it twice.
If the minimum and maximum values are the same, you need to output them both.

Anti-Dupe Information: Built ins are explicitly disallowed, and there are no strings in the array

Is it allowed to output a single value if min and max are the same or do we have to output the same value twice?

@MartinEnder Same value twice.

This is a do X without Y challenge, which aren't particularly interesting.

@Mego Here the Y is just using built-in isn't it?

ugh, maybe I should have disallowed sorting

@DmitryKudriavtsev Try the sandbox next time.

@DmitryKudriavtsev Yet you used it yourself here.

@LeakyNun That's because it makes for the shortest solutions. I encouraged creative methods...

@Mego sure, i'll try

Can we assume that there will be at least 2 elements in the array?

@LeakyNun No, there can be 1

@DmitryKudriavtsev Will there be 0?

@LeakyNun no, 1 or more

Seriously, use the Sandbox. Your changes to the challenge have invalidated every single answer.

@Mego Not every answer. Only like 5 of them. These were clarifications that were answers to questions people asked in the comments.

"Only like five of them" enough said...

Is a function that picks the largest of exactly two elements (in contrast to the largest of a whole array) allowed or does it count as a forbidden built-in?

@nimi Allowed...

I encouraged creative methods No, you encouraged short solutions, by tagging it code golf

May I assume that a variable holds the length of the array (number of elements, regardless of size)? My language has 0-indexed arrays that contain an unlimited number of values, all of which are initialised to zero. If I request the value of a[7], but there were only five elements in the array, I'll get 0 and never know that something went wrong.

@Joe he uses a vector class/template instead of a true array. He makes use of the fact that he can safely iterate from start to end because the length is stored. It seems like you should be able to as well.

As said Luis Mendo Yes, everyone is just posting "i sort your array using a built-in and take first and last", in different languages, not really creative :x

Well, to be fair, I immediately qualified sort as forbidden (isn't it a builtin...) when reading the challenge. It's basically a superset of minmax.

What are builtin, is there a meta topic about that?

why they are all using sort

what's the number range that must do? must be signed?

Jelly, 3 bytes
Ṣ.ị

Try it online!
Sort the array, and then takes the 0.5-th element.
Jelly uses 1-indexing, and floating points indexing means take its floor and its ceil.
So the 0.5-th element would give you the 0th element and the 1st element.
The 0th element is the last element.

Pretty Clever I'm wait for it.... Jelly!

Oh, so that would make finding the median trivial.

In which encoding is that three bytes?

@KonradRudolph This.

Don't you want the first and last elements, rather than the first two elements?  Or have I misunderstood your explanation?

@TobySpeight In 1-based indexing the 0th element is the last element.

Thanks for the clarification.  I failed to read the last line in your answer.

Python, 61 49 37 36 34 31 bytes
lambda s:s.sort()or[s[0],s[-1]]

-12 bytes thanks to RootTwo
Another -12 bytes thanks to chepner
-2 bytes thanks to johnLate
-3 bytes thanks to johnLate

I changed the heading to Python because it works in Python 3 also.

You can golf off a dozen bytes: use [::(len(s)-1)or 1] for the first subscript.  And the second term can be shortened to s[:len(s)<2].

At the cost of sorting the list twice, you can shave off another 12 bytes: lambda s:sorted(s)[:1]+sorted(s)[-1:].

save 6 bytes by lambda s:sorted(s)[::len(s)-1]

The current version (lambda s:sorted(s)[::len(s)-1]) does not work for arrays with one element (ValueError: slice step cannot be zero). A possible fix would be lambda s:sorted(s*2)[::len(s*2)-1] (34 bytes).

31 bytes: lambda s:s.sort()or[s[0],s[-1]]

Brain-Flak 220 218 bytes
(({}))([]){({}[()]<(([])<{({}[()]<([([({}<(({})<>)<>>)<><({}<>)>]{}<(())>)](<>)){({}())<>}{}({}<><{}{}>){{}<>(<({}<({}<>)<>>)<>({}<>)>)}{}({}<>)<>>)}{}<>{}>[()]){({}[()]<({}<>)<>>)}{}<>>)}{}({}<((())){{}{}([][()])}{}>)

Try It Online!
Explanation
First it doubles the top value (in cast the list is only one long)
(({}))

Then it uses my bubble sort algorithm:
([]){({}[()]<(([])<{({}[()]<([([({}<(({})<>)<>>)<><({}<>)>]{}<(())>)](<>)){({}())<>}{}({}<><{}{}>){{}<>(<({}<({}<>)<>>)<>({}<>)>)}{}({}<>)<>>)}{}<>{}>[()]){({}[()]<({}<>)<>>)}{}<>>)}{}

Then it picks up the top value of the stack (i.e. the min)
({}<...>)

Then it pops until the height of the stack is one:
((())){{}{}([][()])}{}

JavaScript (ES6), 34 bytes
a=>[a.sort((x,y)=>x-y)[0],a.pop()]

sort sorts in-place, so I can just refer to the [0] index for the lowest value and pop the highest value from the array, however it does a string sort by default so I have to pass a comparator.

I don't think you need the (x,y)=>x-y part, unless using sort() with the default algorithm counts as a builtin.

@Scott But I don't want a lexical sort...

Right...  I didn't test it with numbers > 10 or < 0.  I didn't know sort() internally treats everything as strings - sorry!

Mathematica, 18 bytes
Sort[#][[{1,-1}]]&

Sorts the array and extracts the first and last values.

R, 31 bytes
l=sort(scan());l[c(1,sum(l|1))]

Not that original, but hey !

ARM Machine Code, 26 bytes
Hex dump (little endian):
6810 4601 f852 cb04 4560 bfc8 4660 4561 bfb8 4661 3b01 d8f5 4770

This is a function, with no system call or library dependence. The encoding is Thumb-2, a variable (2 or 4 byte) encoding for 32-bit ARM. As one might imagine, there's no easy way to just sort and pick the first and last elements here. Overall there's nothing really that fancy going on here, it's more or less the same as the reference implementation.
Ungolfed assembly (GNU syntax):
.syntax unified
.text
.global minmax
.thumb_func
minmax:
    @Input: @r0 and r1 are dummy parameters (they don't do anything)
    @r2 - Pointer to list of integers (int*)
    @r3 - Number of integers to sort (size_t)
    @Output:
    @Minimum of the list in r0 (int)
    @Maximum in r1 (int)
    ldr r0,[r2] @min=r2[0]
    mov r1,r0 @max=min
    loop:
        @ip is intra-procedure call register, a.k.a. r12
        ldr ip,[r2],#4 @ip=*r2++
        cmp r0,ip
        it gt @if (r0>ip)
        movgt r0,ip @r0=ip
        cmp r1,ip
        it lt @if (r1<ip)
        movlt r1,ip @r1=ip
        subs r3,r3,#1
        bhi loop @while (--r3>0)
    bx lr @Return

Tested on the Raspberry Pi 3; here's the testing script (C99, input through argv):
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
//First 2 arguments are dummies.
uint64_t minmax(int,int,int* array,size_t size);

int main(int argc,char** argv) {
    int i;
    int array[argc-1];
    for (i=1;i<argc;i++) {
        array[i-1]=atoi(argv[i]);
    }
    uint64_t result = minmax(0,0,array,argc-1);
    printf("Minimum is %d, maximum is %d.\n",(unsigned)result,(unsigned)(result>>32));
}

Haskell, 27 bytes
f x=(`foldl1`x)<$>[min,max]

In Haskell, min and max give minimum and maximum of two arguments, not of a list. I couldn't tell whether this is disallowed (it seems that instead only minimum and maximum would be disallowed) so please let me know if they are and I'll promptly delete this answer.

@nimi FGITW effect, sadly...

Octave, 20 bytes
@(n)sort(n)([1,end])

This sorts the input vector and outputs the first and last value.

Actually, 5 bytes
S;F@N

Try it online!
Explanation:
S;F@N
S      sort
 ;     dupe
  F    first element
   @N  and last element

05AB1E, 6 4 bytes
{Âø¬

Explanation
{     # sort list
 Â    # bifurcate
  ø   # zip
   ¬  # head

Try it online

MATL, 4 bytes
S5L)

Try it online!
Explanation
S    % Implicitly input the array. Sort
5L   % Push [1 0]. When used as a (modular, 1-based) index, this means "first and last"
)    % Apply as an indexing vector into the sorted array. Implicitly display

Python, 29 bytes
lambda s:s[s.sort():1]+s[-1:]

Test it on Ideone.

C, 83 81 79 bytes
m,M;f(a,s)int*a;{for(m=M=*a;s--;++a)*a<m?m=*a:*a>M?M=*a:0;printf("%i %i",m,M);}

the declaration can turn into ...f(a,s)int*a{... per this

You can combine the ternary expressions to get another 2 bytes off: m,M;f(a,s)int*a;{for(m=M=*a;s--;++a)*a<m?m=*a:*a>M?M=*a:0;printf("%i %i",m,M);}

In gcc you can replace *a>M?M=*a:0 with *a<M?:M=*a

POSIX Awk, 44 bytes
awk '{for(;NF-1;NF--)if($1>$NF)$1=$NF}1' RS=

Brachylog, 9 bytes
oOtT,Oh:T

Try it online!

Processing, 59 52 bytes
void m(int[]x){x=sort(x);print(x[0],x[x.length-1]);}

Processing doesn't actually let me read from stdin that I've been able to find, and I don't know if its internal Java compiler supports lambdas (and its been so long since I've had to write serious Java that I don't remember how).

You can save bytes by removing spaces after int[]

V, 12 bytes
:sor
ò2Gjkd

Try it online!
Credit to DJMcMayhem for this.

\o/ Yay, I'm no longer the only person to have ever used this language!

If the input is a single number, that number still has to be output twice

@LuisMendo hm, will work on that.

CJam, 10 9 bytes
q~$_(p;W>

Try it online.
I'm really not good at CJam.
q~          e# eval input
  $         e# sort
   _        e# duplicate
    (       e# pop first
     p      e# print
      ;     e# remove array
       W>   e# get last element

The usual way to get the first element of a list is 0= (but that unfortunately that doesn't save any bytes). Two other 9-byte solutions: 0W]q~$f=p or the unnamed block {$2*_,(%}.

8 bytes: q~$(p)p;. You can use ) to get the last element like you use ( to get the first.

@BusinessCat That's what I originally had, but it fails for single-element input.

@Pietu1998: Oh, you're right. I didn't notice that.

Perl 6 13 bytes
*.sort[0,*-1]

Test:
my &min-max = *.sort[0,*-1];

say min-max 1;
# (1 1)
say min-max (0, 15, 2, 3, 7, 18, -2, 9, 6, -5, 3, 8, 9, -14)
# (-14 18)

Darn, you beat me there!

Python 2, 34 bytes
x=sorted(input());print x[0],x[-1]

APL (Dyalog), 11 10 5 bytes
-5 thanks to Erik the Outgolfer.
According to the original poster, using a function that picks the largest of exactly two elements (in contrast to the largest of a whole array) [is] allowed. Therefore, the obvious solution is:
⌊/,⌈/

⌊/ minimum-reduction
, followed by
⌈/ maximum-reduction

More in the spirit of the challenge:
(⊃,⊢/)⍋⊃¨⊂

(
 ⊃ first
 , followed by
 ⊢/ the last (lit. right-reduction)
) of
⍋ the indices of the elements in ascending order
⊃¨ each picks from
⊂ the entire argument
TryAPL online!

Wonder why this got downvoted.

Looks like you can do it in 5 bytes...

PHP, 44 bytes
function a($a){sort($a);echo $a[0].end($a);}

C++ (g++), 148 133 131 122 119 bytes
#import<map>
#import<vector>
[](std::vector<int>v){int a=v[0],b=a;for(int i:v)i<a?a=i:i<b?:b=i;printf("%d %d\n",a,b);};

Try it online!

JavaScript (ES6), 46 bytes
I wanted to try an answer without sorting:
a=>a.map(i=>i<n?n=i:i>x?x=i:0,n=x=a[0])&&[n,x]

Bonus recursive version, 53 bytes:
f=([i,...a],n=i,x=i)=>i+.5?f(a,i<n?i:n,i>x?i:x):[n,x]

Thanks. Mine also doesn't use sort.

PHP, 66 65 bytes
Note: this doesn't use any sort builtin. Also, PHP 7 required for the null coalesce operator.
for(;n|$x=$argv[++$i];$x>$h&&$h=$x)$l=min($l??$x,$x);echo"$l,$h";

The max part is straightforward. The min part is a bit more elaborate. since in PHP null is less than 123, null needs to be handled. For this I'm using the null coalesce operator. If $l is null, use the current number ($x) instead, then take the smaller of the 2 numbers.
Run like this:
php -d error_reporting=30709 -r 'for(;n|$x=$argv[++$i];$x>$h&&$h=$x)$l=min($l??$x,$x);echo"$l,$h";' -- 0 15 2 3 7 18 -2 9 6 -5 3 8 9 -14;echo

37 bytes (with sort)
Being allowed to sort makes it trivial (windows-1252 encoding):
php -d error_reporting=30709 -r '$a=$argv;echo$a[sort($a)],~ß,end($a);' -- 0 15 2 3 7 18 -2 9 6 -5 3 8 9 -14;echo

Sort returns 1 when successful, and the list of arguments will start with - which will be sorted as the first item, so we need item 1 to yield min. Therefore we happen to be able to use the return value of sort as the index, saving 2 bytes.
Tweaks

Use n|"0" to make "0" truthy to continue the loop, instead of 0 ."0". Saved a byte

Java, 115 bytes
String f(int[]i){int t=i[0],a=t,b=t;for(int c=0;c<i.length;c++){a=i[c]<a?i[c]:a;b=i[c]>b?i[c]:b;}return""+a+" "+b;}

Ungolfed:
String f(int[] i) {
    int t=i[0], a=t, b=t; // assigns a and b to i[0]
    for (int c=0; c < i.length; c++) { // loop through the array
        a=(i[c]<a) ? i[c] : a;
        b=(i[c]>b) ? i[c] : b; // assignment with ternary operator
    }
    return ""+a+" "+b; // returns a string
}

My first ever code "golf" solution.

JavaScript (ES6), 68 58 bytes (without sorting)
Oh my first try in Golf: without explicit sort (and without min max).
Thanks to @ETHproductions for golfing tips!!
a=>(b=[],a.map(n=>b[n]=0),[b.indexOf(0),b.lastIndexOf(0)])

Does not work with negative integers.
Tried @Luis Mendo 's approach but got it 2 bytes longer... Cost for supporting negative numbers lol?
a=>[a.find(n=>a.every(e=>e>=n)),a.find(n=>a.every(e=>e<=n))]

Could get shorter if order of output is not important:
a=>a.filter(n=>a.every(e=>e>=n)||a.every(e=>e<=n))

Currying doesn't work in this case; the function is called internally as f(a,b), and curried functions need to be called as f(a)(b). (Try testing it out in a browser console.)

@ETHproductions You are correct. I should have provided an already sorted list as input when I was testing... Sorry for the misleading info. Other than a browser console, what ways are good ways to test ES6 code?

I sometimes use this page to test my JS code, although this only supports what your browser does in terms of ES6 features. There are online places where you can run ES6 in any browser, but all the ones I found are very strict with the code (not accepting undeclared variables and the like).

Some golfing tips: you can get rid of the let and return and wrap everything in parentheses, like so: a=>(b=[],a.map(n=>b[n]=0),[b.indexOf(0),b.lastIndexOf(0)])

@ETHproductions Thanks a lot! What does the , mean in the parentheses? (I don't know what is happening there)

In JS, when you have an expression like (a,b,c), it returns the last value, i.e. c. For example, ("abc",[],3)+1 returns 4 (3+1).

@ETHproductions Oh thanks.. What are usages of this feature in real life?

Here are a couple of answers I've written which use that trick.

Julia 0.6, 19 bytes
x->sort(x)[[1,end]]

Try it online!

Haskell, 36 bytes
(\l->(head l,last l)).Data.List.sort

Would love to use &&& here but imports are so costly...

You can't just use Data.List.sort from what I know, you'd need to import it. You could specify Haskell and put LambdaBot in brackets which imports Control.Arrow as well, this would make it valid and save you 20 bytes (no need for Data.List at all).

Ruby, 38 23 bytes
def m(v) puts v.sort![0];$><<v[-1];end
->v{[v.sort![0],v[-1]]}

Thanks @Jordan!

You don't need the space after def m(v). Regardless, you can save 15 bytes by using a lambda and just returning an array: ->v{[v.sort![0],v[-1]]}.

Retina, 17 bytes
O#`
$
¶$`
Ss`¶.+¶

Input and output are linefeed-separated.
Try it online!
Explanation
O#`

Sort lines by numerical value.
$
¶$`

Duplicate the entire input to make sure that the first and last element are distinct.
Ss`¶.+¶

Remove all intermediate lines, leaving only the minimum and maximum.

BASH 38
grep -o '[^ ]*'|sort -g|sed -n '1p;$p'

Scala, 55 bytes
val s=args.map(_.toInt).sorted
print(s.head+" "+s.last)

To execute:
$ scala minmax.scala 1 2 3 4 5 6 7 8 9

dc, 110 bytes
?ddsMsmzdsAsa[z1-:az0<S]dsSx[>R]s?[la;asM]sR[lM]sQ[lQxla1-dsa;al?xla0<N]dsNxlAsa[<R]s?[la;asm]sR[lm]sQlNxlmlMf

Help me, dcers! You are my only hope!
Thanks to @seshoumara for finding that bug!
I'll add an explanation later. Here it is broken up a bit:
?dd sM sm
zd sA sa
[z 1- :a z0<S]dsSx
 [>R]s?
 [la;asM]sR
 [lM]sQ
[lQx la 1- dsa ;a l?x la0<N]dsNx
lA sa
 [<R]s?
 [la;a sm]sR
 [lm]sQ
lNx
lm lM f

I didn't record how to invoke this, and now I can't remember. Whatever I'm doing now, I'm doing it wrong, because this is always returning 0 as the smallest element.

Pfew! It took some starring at it, but found the bug in your code. It's the first character (0) which you duplicate and initialize registers M and m. But if in the input list no number is smaller than m=0, or no number is greater than M=0, then you get an incorrect result, because you artificially added 0 to the sample numbers. The solution is to replace that first 0 with ?d, which reads the numbers and initializes M and m with the last number, thus making it a part of the sample. Then run the code like this: echo "8 _2 5"|dc -e "?ddsMsm....".

Wow, thanks, @seshoumara! I never would have noticed that! (I'd forgotten all about this question, too :P)

Factor, 38 bytes
[ natural-sort [ first ] [ last ] bi ]

Sort the sequence and get its first and last elements.

Python, 35 34 bytes
lambda s:sorted(s+s[:1])[::len(s)]

Alternative version:
lambda s:sorted(s+s)[::len(s)*2-1]

Old version, 35 bytes.
lambda s:sorted(s+[s[0]])[::len(s)]

Fairly simple: take the input list, append the first element, sort it, then take the first and (length)th element of the resulting list. As the length of the input after appending an element is length + 1, this ends up taking the first and last element of said list, which are the minimum and maximum elements.

Though not the shortest answer in Python, this is very creative! +1

The 34-byte one doesn't work in Python 3; this works in both 2 and 3. Also, it was posted after this one.

@mbomb007 - fine, golfed. This is now tied for the shortest Python implementation, and as a bonus it works in both 2 and 3.

Pyke, 5 4 bytes
S'he

Try it here!
S    - sorted(input)
 'he - ^[0], ^[-1]

dc, 45 bytes
[dsa]dsAx[dsz]dsZx[dla>Adlz<Zs.z0<f]dsfxlzlaf

This is a fairly straightforward equivalent of the C++ reference code:
#Test data
0 15 2 3 7 18 _2 9 6 _5 3 8 9 _14

# Uses two variables: a for min, and z for max

# Functions A and Z simply store a copy to a and z respectively.  Call
# them both, to initialize the variables.
[dsa]dsAx
[dsz]dsZx

# Function f is the main work - define and call it
[
    dla>A                       # copy into a if lower
    dlz<Z                       # copy into z if higher
    s.                          # discard value
    z0<f                        # recurse until end of input
]dsfx

# print the result
lzlaf

C#, 60 bytes
n=>{System.Array.Sort(n);return new[]{n[0],n[n.Length-1]};};

A naïve method at 93 bytes:
n=>{var r=new[]{n[0],n[0]};foreach(int i in n){if(i<r[0])r[0]=i;if(i>r[1])r[1]=i;}return r;};

Octave, 35 bytes
@(x)[x(all(t=x<=x')) x(sum(t)==1)]

This is an anoynymous function. Try it at ideone.
The code avoids using sorting. Namely, it does all pairwise "less than or equal" comparisons between elements of the input. The minimum is the element for which all comparisons are true. The maximum is that for which only one comparison is true.

zsh, 22 bytes
(){echo $1 $_} ${(n)@}

defines a lambda function that prints its first arg ($1) and the last argument to the previous command ($_), and passes it $@ after sorting it so the previous command becomes the invocation of that lambda

zsh, 21 bytes
this only works fine if there's more than 1 argument :(
<<<"${${(n)@}/ * / }"

sorts $@, makes it a string and replaces everything from the first space to the last one with a single space, then passes it as input to cat with <<<

usage:
$ ./minmax 23 342 21 10
10 342

Bash + coreutils, 30 bytes
tr \  \\n|sort -n|sed '$p;1!d'

The sed script prints, after the input is sorted, the first and last integers.

C++14, 66 bytes
As unnamed lambda returning via reference parameters. Accepts any random access container of integers.
[](int&a,int&b,auto&C){a=b=C[0];for(auto x:C)a=x<a?x:a,b=x>b?x:b;}

Ungolfed and usage:
#include<vector>
#include<iostream>

auto f=
[](int&a,int&b,auto&C){
  a=b=C[0];
  for(auto x:C)
    a=x<a?x:a,
    b=x>b?x:b;
}
;

int main(){
  std::vector<int> v{1,2,3,4,5,6,7,8,9,0,10,121,-12,100,100,100};
  int a;
  int b;
  f(a,b,v);
  std::cout << a << ", " << b << std::endl;
}

Tcl, 62 bytes
puts [lindex [set L [lsort -r [join $argv]]] 0]\ [lindex $L e]

Try it online!

Clojure, 28 bytes
#((juxt first last)(sort %))

At least juxt is mildly interesting.

Python, 110 Bytes
Long, but it doesn't use sort.
def m(a):
 d=a[0]
 if len(a)==1:return d,d
 b,c=m(a[1:])
 if b>=d>=c:return b,c
 if d>b:return d,c
 return b,d

Output is a tuple of the form (max, min). Probably the least computationally efficient way to get the max/min of an array (other than bongo sorting it  :P)

Python, 97 bytes
def k(s):
 d=s[0]
 if s[1:]:
  a,b=k(s[1:])
  return(a+d+abs(a-d))/2,(b+d-abs(b-d))/2
 return d,d

Only clever part is that in python [] is falsy.
Only builtin used is abs.
It uses more builtins than the 110 byte python solution, and more bytes than the 26 byte solution using sort.

x86 opcode, 19 bytes
00: mov ebx, [esi]
02: mov edx, ebx
04: lodsd
05: cmp eax, ebx
07: cmovg ebx, eax
0A: cmp eax, edx
0C: cmovl edx, eax
0F: loop lp1
11: xchg eax, ebx
12: ret

Input: ECX(length), ESI(array)
Output: EAX(max), EDX(min)
Removing xchg eax, ebx makes 18B but output is not usual reg

SNOBOL4 (CSNOBOL4), 87 bytes
	M =INPUT
	N =M
R	I =INPUT	:F(O)
	N =LT(I,N) I
	M =GT(I,M) I	:(R)
O	OUTPUT =N ' ' M
END

Try it online!

Thunno 2 h, 3 bytes
ṠḲZ

Try it online!
Thunno 2, 4 bytes
Ṡçht

Try it online!
Explanation
ṠḲZ   # Implicit input
Ṡ     # Sort the list in ascending order
 Ḳ    # Bifurcate: duplicate and reverse
  Z   # Zip the two lists together
      # Implicit output of first item

Ṡçht  # Implicit input
Ṡ     # Sort the list
 ç    # Parallelly apply:
  h   #  First item
   t  #  Last item
      # Implicit output

Swift, 77 bytes
let f={(($0+[]).reduce(Int.max){$1>$0 ?$0:$1},$0.reduce(.min){$1<$0 ?$0:$1})}

The relatively obvious approach. I believe this is how the max() and min() methods are actually implemented for Sequence in the standard library.

Vyxal 3, 3 bytes
SÞh

Try it Online!
sort, take the ends

J-uby, 20 bytes
:sort|-[:first,:pop]

Attempt This Online!

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

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


text:
Create an unlimited counterstring
A counterstring is some sort of self-describing test data that is used in software testing. Not sure it was actually invented by James Bach, but I know it from there.
The idea is as follows: the test data contains many asterisk (*). The number in front of the asterisk tells you how long the test data is at that point. If you need to know a position in the test data that is not an asterisk, find the last asterisk, look at the number before and add the number of digits that follow.
The sequence starts like this:
2*4*6*8*11*14*17*20*23*
             ^

As you can see, the marked asterisk is at position 14.
If a file happens to be truncated as follows
[...]2045*20

then you can derive that there is a limit of 2047 characters somewhere (2045 where the asterisk is plus 2 for 2 and 0).
It's your task to create the shortest (this is code-golf) program that outputs (std::out or file or whatever) an arbitrary long test string of that format. The length in characters is given as argument. The program shall support up to 2 GB test data (input value 2147483647 characters).
"Dangerous" positions in the 2 GB file:
8*11*
98*102*
998*1003*
9998*10004*
99998*100005*
999995*1000003*
9999995*10000004*
99999995*100000005*
999999995*1000000006*

This should answer @Leaky Nun's question if there is a decision to make between 995*999* and 995*1000* or similar: no.
The end of the 2 GB file with input value 2147483647 is:
2147483640*2147483

If it does not halt then how do you test it?

You can interrupt at any time I'd say. Plus you could stop at 2 GB if you like. Just thought the code is shorter if the while loop does not need a condition

Is that length in characters?

Can you prove that we would never have to choose between 995*999* and 995*1000* or anything like that?

Are both of those acceptable then?

If you're only creating the 2GB version for yourself, why don't you remove that line and only tell us to create the string up to a length as input?

@DJMcMayhem It is an input parameter tacked at the end of the challenge.

Is an unlimited answer still viable?

In the future, please use the Sandbox to iron out kinks in your challenges before posting them.

@Mego: agreed, especially because I'm not always active on PCG.

@LeakyNun: no, there's no decision to be made like 995999 and 9951000. I have added the dangerous positions into the question

Is it possible for the input length to cut-off partway through a number? Suppose the input was 1000, would 998*1003* be acceptable output, or must it only be 998*10?

@TimmyD: IMHO it's ok to create a longer output, since it doesn't matter for the designed real-world use (testing).

@ThomasWeller If we can create a longer output, can we take no input and just produce the 2GB string?

Pyth, 25 17 15 14 bytes
<uu++GlN\*k)Qk

Try it online.
Length is taken via STDIN.

Haskell, 60 58 bytes
As a function we get:
f=length.show
iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show

Full program, 72 70 bytes
This outputs an infinite counterstring to STDOUT:
f=length.show
main=putStr$iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show

Inputting the length requires 20 additional bytes:
main=interact(\j->take(read j)$iterate(\n->1+n+(f$n+1+f n))2>>=(++"*").show)

This works up to your approximately your RAM size, since Haskell defaults numeric integral types to Integer.

Python 3, 126 114 99 bytes
def f(x,s=''):
 i=t=2
 while len(s)<x:i+=len(str(t+i))-len(str(t));s+=str(t)+'*';t+=i
 print(s[:x])

A function that takes input via argument of the character count at which to truncate the string, and prints to STDOUT.
How it works
The difference between the numbers in the string is initially 2. Every time an order of magnitude is passed, this difference is increased by 1; this can be achieved by taking the difference between the number of digits of the current number and the number of digits of the current number added to the difference, which is 1 only when required. The function simply loops while the length of the string is less than the input, appends to the string and updates the difference and number as required, and then truncates before printing.
Try it on Ideone
Infinite output version, 69 bytes
s=i=2
while 1:i+=len(str(s+i))-len(str(s));print(end=str(s)+'*');s+=i

Python 2, 74 72 66 64 61 Bytes
f=lambda n,i=2:"%d*"%i+f(n,len(`i+2`)-~i)[:n-2]if i<n*2else""

Takes an integer n and outputs a counterstring of length n.
program version, 69 Bytes:
s,n,i="",input(),2
while i<2*n:s+="%d*"%i;i+=len(`i+2`)+1
print s[:n]

Takes an integer n from stdin and prints a counterstring of length n.
Shorter, but only almost working, alternative version:
n,i=input(),2
while i<2*n:print("%d*"%i)[:n-i],;i+=len(str(i+2))+1

R, 92 bytes
    N=nchar;f=function(n){z=0;y="";while(z<n){z=z+N(z+N(z)+1)+1;y=paste0(y,z,"*")};strtrim(y,n)}

Example output:

f(103)
  [1] "2*4*6*8*11*14*17*20*23*26*29*32*35*38*41*44*47*50*53*56*59*62*65*68*71*74*77*80*83*86*89*92*95*98*102*1"

PowerShell v5, 97 bytes
param($n)$l=1;for($i=0;$i-lt$n){$i+="$i*".length;if("$i".Length-gt$l){$i++;$l++};ac .\o "$i*" -n}

Takes input as a command-line argument $n, sets helper $l which we use to keep track of our integer length. Then, we loop from 0 up to $n. Each iteration, we increment $i by the .length of the string formed from $i and an asterisk. Then, if the .length of $i changed (e.g., we moved from 2 digits to 3 digits), we increment both the helper $length variable and $i (to account for the additional digit). We then use the add-content command to append "$i*" to file .\o in the current directory, with -noNewLine.
NB

Requires v5, since the -noNewLine parameter was finally added in that version.
PowerShell will automatically up-convert from [int] to [double] (no, I don't know why it doesn't go to [long]), so this will properly handle input up to and greater than 2147483648, without problem. Theoretically, it will handle input somewhere up to around 1.79769313486232E+308 (max value of [double]) before complaining, but I expect the disk to fill up before that happens. ;-)
Due to the loop conditional checking, this will output to the file a minimum of the input length. For example, for input 10 this will output 2*4*6*8*11*, since 11 is the first $i value greater than the input.

PowerShell v2+, also 97 bytes (non-competing)
param($n)$l=1;-join(&{for($i=0;$i-lt$n){$i+="$i*".length;if("$i".Length-gt$l){$i++;$l++};"$i*"}})

Instead of sending to a file, this encapsulates the loop iterations and then -joins them together into a string. This allows it to work for versions earlier than v5. However, since .NET defines a [string] with a constructor like String(char c,Int32 length), this version does not satisfy the max input requirement, since the output string will overflow and barf.
Also, you may not want to have a ~2GB string floating around in your pipeline. Just sayin'.

1.79769313486232E+308 will certainly not work, because adding small numbers to a float won't change the value any more. See http://stackoverflow.com/questions/12596695/why-does-a-float-variable-stop-incrementing-at-16777216-in-c So my guess it that it stops working once it was "upgraded" to double

@ThomasWeller PowerShell [double]s are 64-bit. For example, run for($i=2147483645;$i-lt2147483655;$i++){"$i - " + $i.GetType()} will show a steady progression of $i but the Type changes at 2147483648 to double. I'm sure at some point it'll stop working, likely around ~15 digits of precision or when the .ToString starts using e. The [double]::MaxValue was more of a throwaway joke than a serious upper bound.

Jelly, 22 19 18 bytes
2µṾL+®‘¹©=¡=µ³#j”*

Try it online!
Find the first n numbers in the string then join the list with an asterisk. This will always be longer than n which was allowed by OP in the comments.
The program selectively updates the register with the current number in the sequence in the # loop with ¹©=¡. I was hoping this could be shorter, by putting © after the second µ for example, but unfortunately that doesn't work and I couldn't figure out any thing shorter.


text:
Pokemon GO Evolution Cost Calculator
Tired of always wondering how many more Pokémon you need to catch to get those high-tier evolutions? Wonder no more! Now you will write a complete program or function to calculate it for you!
The Challenge:
As input, your program will receive a list of the costs in candy to evolve a Pokémon to the next tier. (This list may be separated by any delimiter of your choosing, or as function arguments). Your program will then return or print the number of Pokémon that must be caught, including the one that will be evolved, to evolve through all the tiers given.
How do you calculate this? Like so:
1. Add up all the candy costs: 12 + 50 = 62
2. Subtract 3 candies from the total, this being from the one Pokémon you keep for evolving: 62 - 3 = 59
3. Divide this number by 4 (3 for catching, 1 for giving it to the Professor), always taking the ceil() of the result: ceil(59/4) = 15
4. Finally, add 1 to this total to get the total number of Pokémon you must catch, 16!
Example Input -> Output:
[4] -> 2
[50] -> 13
[12, 50] -> 16
[25, 100] -> 32
[19, 35, 5, 200] -> 65

Winning:
The app has already taken up most of the space on your phone, so your program needs to be as short as possible. The complete program or function with the smallest byte count will be accepted in two weeks! (with any ties being settled by the earliest submitted entry!)

How is the output calculated?

Whoops, knew I must have forgotten something...

In the future, please use the Sandbox to work out kinks in your challenges and to get feedback on them before posting.

If you want a slightly less nonsensical rationale for short code length, you could go with "because the app has almost killed your battery, you want your code to be as short as possible, so you can type it in before your battery dies."

Yes, next time I will definitely use the Sandbox first.

Can we assume it costs at least one to evolve?

Shouldn't the formula be floor(Sum(L)/4)+1? The current formula doesn't work for sums divisible by 4. For example [400] would return 100, when in reality it needs to be 101 for the extra one to evolve.

@EamonOlive I think thats fair.

And @Emigna I will rollback to my previous algorithm, which did handle that case correctly.

I hope someone posts an answer in Go

Shouldn't the function also take hatching eggs into account?

This should never be posted to GO.  This has almost nothing to do with how Pokemon are evolved.  As I understand the question, you are evolving different Pokemon for each item in the list.  If this is the case, for the test case of [12,50], you need to catch 4 to evolve the type that needs 12 while you need 13 to evolve the one that needs 50.  That would total 17.  If instead you are trying to say you need two different candy costs to evolve a Pokemon, this is not the way the game works. You only need one candy type to evolve one Pokemon.

Is my SILOS answer considered valid. Can I assume that no Pokemon has more than 8 evolution stages?

@Keeta: each item in the list is a cost to evolve a pokemon to the tier. A real life example would be Gastly -> Gengar = [25,100] => 32i.e. 32 Gastly caught are needed to evolve first to a Haunter then to a Gengar.

This doesn't take into account that you get a single candy back when you evolve. As in, if you have 12 candies and evolve a Pidgey (cost 12), you end up with one candy after evolution. For a test case with several evolutions like [12,12,12,12], this means you only need to catch 12 instead of the 13 yours would give as an answer. Not that any evolution chain in the actual game has that many stages... but your test cases do.

@Enigma If this were the original posters intent, there would be no requirement for more than 2 levels for the test cases.  There are no Pokemon GO characters that evolve more than twice.  With another discrepancy pointed out by Geobits, I stand by my statement that this should not be posted to GO.

@Keeta Emigna is correct about the way this challenge is supposed to work. However, I wish I had remembered the fact Geobits had pointed out, as that would make this challenge much more interesting.

@FryAmTheEggman Unless there is still a typo that I'm not seeing, the correct result for [3] is 1.

You're missing the subtract 3 part, 3-3 = 0 -> ceil(0/4) = 0 + 1 = 1, that should clear it up :)

Jelly, 5 4 bytes
S:4‘

Try it online!
Sum, integer divide : by 4 and increment ‘.

;-; I'm 4 seconds late

It doesn't work when the sum is divisible by 4.

Gives wrong answer for [4].

Fixes. Apparently the spec changed when I was sleeping.

05AB1E, 4 bytes
O4÷>

Explanation
O    # sum
 4÷  # integer division by 4
   > # increment

Try it online

÷ is 2 bytes   ...

@user23127: 05AB1E uses the CP-1252 encoding.

C# REPL, 15 bytes
n=>n.Sum()/4+1;

Casts to Func<IEnumerable<int>, int>.

Actually, 4 bytes
Σ¼≈u

Try it online!
Explanation:
Σ¼≈u
Σ     sum
 ¼    divide by 4
  ≈   floor
   u  add 1

Aren't these unicode characters 2 bytes each?

@user23127 If this were encoded in UTF-8, yes. Actually (and its predecessor Seriously) use CP437.

Brachylog, 5 bytes
+:4/+

Try it online!
Explanation
A very original answer…
+        Sum
 :4/     Integer division by 4
    +    Increment

BASH (sed + bc) 19
sed 's~)~+4)/4~'|bc

Input is a + separate list on stdin
E.g.:
echo '(19+35+5+200)'|  sed 's~)~+4)/4~'|bc

S.I.L.O.S 100 99 103 characters + 22 for sample input
Code with testing harness.
set 512 52
set 513 10
GOSUB e
GOTO f
funce
a = 0
i = 511
lblE
i + 1
b = get i
a + b
if b E
a / 4
a + 1
return
lblf
printInt a

input as a series of set commands to modify the spots of the heap starting at spot 512.
Try it Online!

Just because Pokemon Go doesn't have more than 8 tiers of evolution (it actually maxes out at 3), doesn't mean you aren't required to handle larget test cases.

@Mego the spec clearly references pokemon go, and thus we can assume that all input will be valid input. I would have posted a much better version that does indeed handle newline separaated input terminated with a zero sentinel, but the TIO is currently borked

@Mego let me clarify with the OP. If this is invalid I can modify it to work for even larger test casees

This is actually a standard loophole - you're assuming rules not present in the challenge.

@Mego modified for a cost of three bytes, it now should work up to 1000's of evolutions.

Retina, 18 17 bytes
Byte count assumes ISO 8859-1 encoding.
$
¶4
.+|¶
$*
1111

Input is linefeed-separated.
Try it online!

@orlp yay for rule changes. fixed.

Haskell, 17 bytes
(+1).(`div`4).sum

Pyke, 4 bytes
seeh

Try it here!
((sum(input)/2)/2)+1

Pyth, 5 bytes
h/sQ4

Try it here!
Sum input with sQ, divide by 4 with /4 and finally increment h.

CJam, 7 bytes
{:+4/)}

Try it here!
Defines an unnamed block that expects the input on the stack and leaves the result there.
:+ sums the list, 4/ divides the result by 4 and ) increments that.

R, 22 bytes
floor(sum(scan())/4+1)

JavaScript, 29 Bytes
x=>x.reduce((a,b)=>a+b)/4+1|0


text:
How can I get a repdigit?
In honor of how much rep I had several hours ago, when I first thought of this challenge:

Numbers like this that are made up of a single digit repeating are called repdigits. Repdigits are fun! Every body would be more happy if the amount of rep they had was a repdigit¹, but I am impatient, so you need to help me find out the fastest way to get to a repdigit.
Here is your challenge:
Given a positive integers representing reputation, output the minimum amount of rep they need to gain to get to a repdigit. For example, at the time of writing this challenge, user Martin Ender had 102,856 rep. The nearest rep-digit is 111,111, so he would need to gain: 8255 rep to be at a repdigit.
Since people dislike losing rep, we will only consider non-negative changes. This means that, for example, if someone is at 12 rep, rather than losing 1 rep, the solution is to gain 10 rep. This allows '0' to be a valid output, since anyone who has 111 rep is already at a repdigit.
Input and output can be in any reasonable format, and since it is impossible to have less than 1 rep on any Stack Exchange site, you can assume no inputs will be less than 1.
One cornercase to note:
If a user has less than 10 rep, they are already at a repdigit, and so they also need '0'.
Test IO:
#Input      #Ouput
8           0
100         11
113         109
87654321    1234567
42          2
20000       2222
11132       11090

Standard loopholes apply, and the shortest solution in bytes wins!

Can I return the answer as a singleton array? It wouldn't actually save bytes, but I could make my answer a lot faster.

@Dennis I don't see why not.

Can we take input as a string?

@Dennis Why would I say no? I always try to avoid restrictive IO in my challenges, and a lot of languages (like my own) don't distinguish between string and integer input, so I don't see any reason I would restrict it.

Related: http://codegolf.stackexchange.com/q/73916/17602

@DJMcMayhem Mind adding what a repdigit is in case the link is dead at some point?

@ColdGolf I highly doubt Wikipedia will die any time soon, but I added some more info.

The smallest possible rep gain is 2 rep from editing, right? Since the question says only positive changes are valid, wouldn't this affect the minimum actually possible increase to a repdigit in some cases, like 10 requiring +12 to get to 22, because there is no +1? The tests don't seem to consider this.

@Anko you can gain 2 by edit and lose 1 through negative vote, so it is possible to have one more rep than what you currently have, and while there is a loss involved, the absolute is still positive.

@BrianH. I guess the specificity of "we will only consider non-negative changes" is up to interpretation… I took it as "imagine nobody ever loses rep for anything".

@Anko, if it were impossible to lose rep, that would mean the lowest rep gain that turns odds to evens and viceversa would be 15 though, so the 100 would give 122 as result instead of 11

@brianh No, the smallest rep gain that turns odds to evens is 5 (question upvote). However, for the sake of this challenge, we're ignoring the fact that there are only certain amounts to gain rep. So 110 should give 1, even though there isn't a way to gain one rep.

Jelly, 6 bytes
DE$1#_

Output is a singleton array.
Try it online! or verify most test cases. Test case 87654321 is too slow for TIO.
How it works
DE$1#_  Main link. Argument: n

   1#   Call the link to the left with argument k = n, n + 1, n + 2, etc. until one
        match is found, then return the matching k.
  $       Combine the two links to the left into a monadic chain.
D           Convert k to base 10.
 E          Test if all decimal digits are equal.
     _  Subtract n from the result.

Wow... all ASCII. This is a first. Are there any other Jelly solutions which are all ASCII? Just curious.

This one and that one were easy to find. There may be others.

Haskell, 39 bytes
until(((==).head>>=all).show)(+1)>>=(-)

Try it online

Brachylog, 9 bytes
:.#++#==,

Try it online!
This is pretty efficent as it makes use of constraints arithmetic.
Explanation
:.            The list [Input, Output].
  #+          Both elements must be positive or zero.
    +         The sum of those two elements…
     #=       …must result in an integer where all digits are the same.
       =,     Assign a value that matches those constraints.

I love how Brachylog reads like the answer. Like, you just define: This is the answer you're looking for. Figure it out for me :)

@DJMcMayhem That's the cool factor of declarative languages! (though it's not always that magical :p)

Awesome solution! I think that Brachylog could always perform an implicit labeling of remaining CLP(FD) variables at the end of a program. To get this, wrap the whole execution in call_reside_vars/2, fetch the CLP(FD) variables, and label them. For example: call_residue_vars(Program, Vs0), include(fd_var, Vs0, Vs), label(Vs). What do you think?

@mat Thanks! I'll add implicit labeling at the end of programs to the list of enhancements to make, since I can't think of any situation where one would want to output a variable at the end of execution.

Hey...

Python 2, 41 40 bytes
def f(n):r=10**len(`n`)/9;print-n/r*-r-n

Not the shortest approach, but very efficient. Test it on Ideone.
How it works
For input 10**len(`n`) rounds n up to the nearest power of 10. Afterwards, we divide the result by 9. This returns the repdigit 1…1 that has as many digits as n. We save the result in r. For example, if n = 87654321, then r = 11111111.
The desired repdigit will be a multiple or r. To decide which, we perform ceiling division of n by r. Since Python 2's division operator / floors, this can be achieved with -n/r, which will yield the correct absolute value, with negative sign. For example, if n = 87654321, this will return -8.
Finally, we multiply the computed quotient by -r to repeat the quotient once for each digit in n. For example, if n = 87654321, this returns 88888888, which is the desired repdigit.
Finally, to calculate the required increment, we subtract n from the previous result. For our example n = 87654321, this returns 1234567, as desired.

Another 41 is lambda n:10**len(`n`)/9*-~int(`n*9`[0])-n. It almost works to do lambda n:int(`n*9`[0]*len(`n`))-n, but the digit is one too small and I don't see a good way to fix it.

Would you mind explaining the logic behind this formula? Baffles me how it's O(1).

@shooqie I've edited my answer.

@Dave: Huh, it's interesting actually. I always assumed that closed-form formula == O(1), but I guess it makes sense.

Amazing approach. It may be slightly longer in terms of bytes for Python 2, but it saves a whopping 40 bytes in Java 7, so thanks. :) (Also thanks a lot for the "How it works" part.)

Python 2, 37 bytes
f=lambda n:1-len(set(`n`))and-~f(n+1)

Test it on Ideone. Note that this approach is too inefficient for test case 87654321.
How it works
If n is already a repdigit, 1-len(set(`n`)) will return 0 since the length of the set of n's digits in base 10 will be 1. In this case, f returns 0.
If n is not a repdigit, f(n+1) recursively calls f with the next possible value of n. -~ increments the return value of f (0 when a repdigit is found) by 1 each time f is called recursively, so the final return value equals the number of times f has been called, i.e., the number of times n had to be incremented to get a repdigit.

I'm never clear for these things whether the L on longs needs to be handled.

What the, how does-- it... You can't... what? For a moment there I was proud of my 52 byte answer...

@xnor: Solutions in C aren't required to work for long integers by default, so I always assumed the same way true for Python.

@DJMcMayhem looks to me like it recursively counts up until it finds a repdigit via checking the size of a set built from the string representation of the number. The -~ allows the function to count the number of calls it made.

Perl 6, 23 bytes
{($_...{[==] .comb})-1}

A lambda that takes the input number as argument, and returns the result.
Explanation:

Uses the ... sequence operator to increment the input number until it reaches a repdigit (tested by splitting its string representation into characters and seeing if they're all equal).
Subtracts one from the length of the sequence.

The test can be replaced /(.)$0*/

Java 7, 116 76 bytes
int c(int i){int r=(int)Math.pow(10,(i+"").length())/9;return(-i/r-1)*-r-i;}

Used @Dennis' amazing approach to lower the byte-count by a whopping 40 bytes.
Ungolfed & test cases:
Try it here.
class Main{
  static int c(int i){
    int r = (int)Math.pow(10, (i+"").length()) / 9;
    return (-i / r - 1) * -r - i;
  }

  public static void main(String[] a){
    System.out.println(c(8));
    System.out.println(c(100));
    System.out.println(c(113));
    System.out.println(c(87654321));
    System.out.println(c(42));
    System.out.println(c(20000));
    System.out.println(c(11132));
  }
}

Output:
0
11
109
1234567
2
2222
11090

Actually, your "try it" gives prints out 1 if you feed it 8 instead of printing 0 as it should.

@SQB Ah you're right. Hmm, that pretty weird, since the output in my post I've copy-pasted from my IDE console..

Shouldn't the second to last output be 2222 and the fourth output be 12345678?

@DanTheMan Ah, the second to last should indeed be 2222 instead of 222. I fixed a mistake in the code, but had by accident still used the old output here. It's fixed now. As for the fourth, no, it should be 123467 (as you can also see at OP's question).

Pyth, 9 8 7 bytes
1 byte thanks to @FryAmTheEggman.
-f@F`TQ

Try it online.
Very inefficient, loops through all numbers from the input to the next repdigit.

Brain-Flak 690 358 bytes
Here's my go at it
(({})[()])(()){{}(({}())){(({}))(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}>)<>(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)}{}<>{(([])<{{}({}[()]<>)<>([])}{}><>){({}[()]<({}<>)<>>)}{}<>}([]){{}{(<({}<>)<>>)}{}([])}{}<>(([][()()])<{{}{}([][()()])}{}>)}{}({}[{}])

Try It Online
Explanation
Start by making a second copy of the input that is one less than the original.  We will use the copy to search for the next repdigit.  We subtract one in case the number itself was a repdigit
(({})[()])

Push one to satisfy the coming loop. (doesn't have to be one just not zero)
(())

This loop will run until there is a repdigit on top of the stack
{

Pop the crap.  Their is a "boolean" on top that drives the loop, since it is no longer needed we pop it.
{}

Add one and duplicate the top.  The copy will be decomposed into its digits.
(({}()))

While the copy is not zero...
{

Copy again
(({}))

Mod 10 and move to the other stack
(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}>)<>

Divide by 10 (Integer division)
(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)

}

Pop the zero that was our copy
{}

We have now decomposed the number into its base 10 digits, So we swap over to the stack with all the digits.
<>

While the leading digit is not zero
{

We pick up a copy of the stack height (i.e. the number of digits)...
(([])<

Silently subtract one from every number on the stack
{
{}
({}[()]<>)<>
([])
}
{}

Put the stack height we picked up down. (and swap to the other stack)
><>)

We use the stack height to pull all the digits we placed on the other stack back onto the proper stack.
{
({}[()]<({}<>)<>>)
}

Pop the zero that was our stack height
{}

Swap back onto the stack with the digits (or what were the digits)
<>

End loop
}

Now we have subtracted the top digit from all the other digits.  If all the digits are zero the orginal number (not the input but the number we are checking) was a repdigit.[citation needed].  So we need to check for non-zeroes.
While the stack height is not zero
([])
{
{}

If the digit is not zero move it to the other stack and replace it with a zero.
{
(<({}<>)<>>)
}

Pop it (now it is a zero)
{}

End loop
([])
}
{}

Swap over onto the other stack (duh..)
<>

Grab our selves a copy of the stack height minus two
(([][()()])<

While the stack height is not two (the original and the accumulator)
{
{}

Pop the top
{}

End the while
([][()()])
}
{}

Put down our copy of the stack height minus two.  This ends up being the number of digits that are not the same as the first digit.  In other words if it is zero it is a repdigit.
>)

If this loop ends we have found a repdigit
}

Pop the "boolean"
{}

Subtract the original from the repdigit
({}[{}])

Seriously, how do you do this? I was thinking "oh, I'd like to do it in brain flak, but I can't figure out how to determine if it's a repdigit or not". This is crazy! Do you use a script to generate most of these answers?

@DJMcMayhem Nope just practice.  A explanation will follow.

@DJMcMayhem I'm sorry perhaps I don't understand. 112+110 = 222?

I'm sorry, you're totally right, I don't know what I'm saying. Please ignore that last comment.

Python 2, 52 bytes
a=b=input()
while len(set(str(a)))!=1:a+=1
print a-b

Python 2 has several tricks that make this shorter. For example, input is numeric, so we don't need to cast to int. (-5 bytes) We also don't need to put parenthesis around the a-b (-1 byte)
Use this script to verify all test cases:
def f(i):
    a=b=i
    while len(set(str(a)))!=1:a+=1
    return a-b

inputs = [8, 100, 113, 87654321, 42, 20000, 11132]
outputs = [0, 11, 109, 1234567, 2, 2222, 11090]

for i in range(len(inputs)):
    print(f(inputs[i]) == outputs[i])

You may also try it online!

Excel, 85 79 bytes
Put the following formula in any cell except cell N since it's a name for reference cell of input:
=IF(1*(REPT(LEFT(N),LEN(N)))<N,REPT(LEFT(N)+1,LEN(N))-N,REPT(LEFT(N),LEN(N))-N)

Explanation:

N is the input and also name of reference cell.
LEFT(N) take the first digit of input value.
LEN(N) return the length of input value.
REPT(LEFT(N),LEN(N)) repeat the first digit of input value LEN(N) times and multiply it by 1 to convert text format to number format so we can use it for number comparison.
The syntax for the IF function in Microsoft Excel is: IF( condition, [value_if_true], [value_if_false]), hence makes the whole formula is self-explanatory.

You can omit Num_chars in LEFT and save 4 bytes:
LEFT(N)

Make that 6 bytes

@Wernisch Thanks. Edited.

You can save 25 bytes by coercing the IF condition into a 1 or 0 using -- thus you do not need to repeat yourself just to +1: =REPT(LEFT(N)+(--1*(REPT(LEFT(N),LEN(N)))<N),LEN(N))-N

Actually, in this instance, you don't need to coerce it explicitly, you can instead just use: =REPT(LEFT(N)+(1*(REPT(LEFT(N),LEN(N)))<N),LEN(N))-N, saving 27 bytes to give a total of 52.

GNU sed, 223 + 1(r flag) = 224 bytes
s/$/:0%/
:;y/:%/%:/
/^(.)\1*%/{s/.*%(.*):/\1/;q}
:f;s/9(@*:)/@\1/;tf
s/8(@*:)/9\1/;s/7(@*:)/8\1/
s/6(@*:)/7\1/;s/5(@*:)/6\1/
s/4(@*:)/5\1/;s/3(@*:)/4\1/
s/2(@*:)/3\1/;s/1(@*:)/2\1/
s/0(@*:)/1\1/;s/(^|%)(@*:)/\11\2/
y/@/0/;t

Run:
sed -rf repdigit.sed <<< "112"

Output:
110

This is a pure sed solution, the arithmetic is simulated using regular expressions only. The algorithm works as follows:

the pattern space format is set to ^current_reputation:needed_reputation%$
in each iteration of the main loop the separators are switched:
a) %: applies the increment to needed_reputation
b) :% applies the increment to current_reputation
if the current_reputation is a "repdigit", the needed_reputation is printed and the program ends

05AB1E, 10 6 bytes
∞.Δ+Ë

Try it online!
Explanation
∞<      # from the infinite list of non-negative integers
  .Δ    # find the first number where
     Ë  # all digits are equal
    +   # after adding the input

-2 bytes that no doubt weren't possible yet at time of posting: remove § and change ¹- to α. And here a rather similar 8-byte alternative: ∞+.ΔÙg}α

R, 102 98 91 bytes
a=scan(,'');i=0;while(length(unique(strsplit(a,"")[[1]]))!=1){a=paste(strtoi(a)+1);i=i+1};i

Ungolfed :
a=scan(,'') #Asks for input
i=0         #Initialize i to 0, surprisingly

while(length(unique(strsplit(a,"")[[1]]))!=1)
    #Splits the input into its digits,
    #compute the length of the vector created by the function `unique`, which gives all the digits once.
    #as long as the this length is different from one :
{
a=paste(strtoi(a)+1) #Increases by one the value of the input (while messing around with its format)
i=i+1                           #Increases by one the value of the counter
}

i #Outputs the counter

Messing around with the format (as.numeric and as.character) adds some bytes, but R is not really flexible !

PowerShell v2+, 66 bytes
param($n)for($x=+"$($n[0])";($y="$x"*$n.length)-lt$n;$x++){}+$y-$n

The usually-good-for-golf very loose casting of PowerShell is a major downfall here.
Takes input $n as a string, and enters a for loop. For the setup step, we extract out the first character $n[0], but have to convert it back to a string "$(...)" before casting as an int + and saving into $x. Otherwise, the later arithmetic will be using the ASCII value of the char-code.
The conditional checks whether a string constructed from $n.length "$x"s, temporarily stored in $y, is less-than $n. So long as it's not, we increment $x++, setting up the conditional for the next loop.
For example, for input 123, the value of $y when the conditional is first checked will be 111, which is less-than $n, so the loop continues. There's nothing in the loop body, so the step increment happens $x++, then the conditional is checked again. This time $y equals 222, which is greater than $n, so the loop terminates. If the input is already a repdigit, the conditional is not satisfied, because at that point $y is equal to $n.
Once out of the loop, we cast $y to an integer +, then subtract $n. That result is left on the pipeline and output is implicit.

Perl, 40 + 1 (-n) = 41 bytes
/^(.)\1*$/&&say($v|0) or$_++&&++$v&&redo

If printing nothing instead of 0 when the number is already a repdigit is acceptable, then 37 bytes are enough :
/^(.)\1*$/&&say$v or$_++&&++$v&&redo

Run with -n (1 byte) and -E or -M5.010 (free) :
perl -nE '/^(.)\1*$/&&say($v|0) or$_++&&++$v&&redo'

Explanations : there are two major parts in the code : /^(.)\1*$/&&say$v and $_++&&++$v&&redo. The first one test if $_ is a repdigit; if yes it prints the number we added to the original number to make it a repdigit ($v), and if no, we had 1 to both $_ and $v, and start over.

41 bytes of perl, duplicates 1st digit (or 1st digit+1 if any digit is larger than 1st) by length of string, then subtracts input: perl -pe '@x=sort/./g;//;$_=(($x[-1]>$&)+$&)x+@x-$_'

Java, 74 72 bytes
int c(int i){int n=0;while(!(i+++"").matches("^(.)\\1*$"))n++;return n;}

(If the other Java entry is 76 bytes, this one is 74 72, since it's two four bytes shorter).
Anyway, just increment the input until it's a repdigit while incrementing a counter. Return the counter.
Yes, those are three pluses in a row, two to increment the input, one to concatenate an empty string to make it a string.
No, I didn't think it would be legal without a space in between either, but there you go. That's what a typo will do for you: one byte shorter.
Using a for-loop instead of a while takes exactly as many bytes:
int c(int i){int n=0;for(;!(i+++"").matches("^(.)\\1*$");n++);return n;}

Edit:
An earlier version had matches("^(\\d)\\1*$") to check for a repdigit, but since we've just converted an int to a string, using a . to match is enough.

Ungolfed & test cases:
Try it here.
class Main{
  static int c(int i){
    int n=0;
    while(!(i++ + "").matches("^(.)\\1*$")) {
      n++;
    }
    return n;
  }

  public static void main(String[] a){
    System.out.println(c(8));
    System.out.println(c(100));
    System.out.println(c(113));
    System.out.println(c(87654321));
    System.out.println(c(42));
    System.out.println(c(20000));
    System.out.println(c(11132));
  }

}
Output:
0
11
109
1234567
2
2222
11090

We normally recommend always using for loops as occasionally you can spot a way to save a byte in a way that you couldn't using a while loop.

@Neil Well, I'll be bleeped if I know how here.

I wasn't suggesting you could save a byte, I was just trying to point out that it was unremarkable that the for loop was the same length as you wouldn't expect it to be longer.

@Neill ah, okay.

Vyxal, 6 bytes
λ?+≈;ṅ

Try it Online!

5 with a smaller lambda

Pyke, 13 11 bytes
o+`}ltIr)ot

Try it here!
            - o = 0
o+          -     o++ + input
  `         -    str(^)
   }        -   deduplicate(^)
    lt      -  len(^)-1
      I )   - if ^:
       r    -  goto_start()
         ot - o++ -1

Actually, 15 bytes
;D;WXu;$╔l1<WX-

Try it online!
Explanation:
;D;WXu;$╔l1<WX-
;                dupe
 D;              decrement, dupe
   WXu;$╔l1<W    while top of stack is truthy:
    X              discard
     u             increment
      ;            dupe
       $╔l1<       1 if len(str(TOS)) > 1 else 0 (check if the string representation of the TOS contains only one unique digit)
                 after the loop, the stack will be [1 repdigit input]
             X   discard
              -  subtract input from repdigit

JavaScript (ES6), 42 bytes
f=(n,p=1)=>n<p?-~(n*9/p)*~-p/9-n:f(n,p*10)

Explanation: Recursively computes p as the next power of 10 after n. The digit to be repeated is then computed as 1+floor(9n/p), and the repunit is simply (p-1)/9, from which the result follows.

Jellyfish, 20 bytes
p
<
)\&&&~j<i
->N>u0

Try it online!
TIO can't handle the longer test cases, but given enough time and memory, they should work too.
Explanation

i is input, and < decrements it. This value is fed to the function on the left.
\> increments the value (at least once) until the function to the right gives a truthy value.
The test function is a composition (by &s) of four functions.
0~j converts to string.
u removes duplicate digits.
> removes the head of the resulting string.
N is logical negation: it gives 1 for an empty string, and 0 for non-empty. Thus the function tests for a rep-digit, and the result of \ is the next rep-digit counting from <i.
)- subtracts the result from the function input, that is, <i.
This difference is off by one, so < decrements it. Finally, p prints the result.

MATL, 10 bytes
q`QtVda}G-

Try it online!
This keeps incrementing the input until all digits are equal, so it's slow. The test case for input 87654321 times out in the online compiler.
q      % Take input implicitly. Subtract 1
`      % Do...while loop
  Q    %   Increment top of the stack
  tV   %   Duplicate and convert to string (i.e. digits of the number)
  d    %   Difference between consecutive digits
  a    %   True if any such difference is nonzero. This is the loop condition
}      % Finally (execute on loop exit)
  G-   %   Subtract input. This is the final result, to be (implicitly) displayed
       % End loop implicitly. If loop condition (top of the stack) is truthy: proceeds
       % with next iteration. Else: executes the "finally" block and exits loop
       % Display implicitly

PHP 5.6, 59 53 51 50 bytes
Saved 6 8 bytes thanks to @manatwork.
while(count_chars($argv[1]+$b,3)[1])$b++;echo$b?:0

Test with:
php test.php 11132

The count_chars() function with 3 as the second parameter returns a string with the distinct characters in a string. When this string is 1 character long ([1] will return false when it's length 1) then echo $b, otherwise increment $b and loop again.

Cool use of count_chars(). What about 3 as $mode parameter? So this would be the while condition: count_chars($argv[1]+$b,3)[1].

That's really clever, thanks for the idea. I did try using 3 for the mode originally but couldn't think of a way to use it without count or strlen so it turned out to be the same length.

Oh, and without initializing $b: echo$b?:0;

Ooo I forgot about the empty ternary. Good call!

Matlab, 65 64 bytes
t=input('');i=0;while nnz(diff(+num2str(t+i)))
i=i+1;end
disp(i)

Because of the while loop it's rather slow...
Explanation
t=input('')  -- takes input
i=0          -- set counter to 0
while
          num2str(t+i)   -- convert number to string
         +               -- and then to array of corresponding ASCII codes
    diff(             )  -- produce vector of differences (all zeros for 'repdigit')
nnz(                   ) -- and count non-zero entries
i=i+1                    -- while not all digits are the same increase the counter
end          -- end while loop
disp(i)      -- print the counter

Saving one byte thanks to @Luis Mendo.

Do you really need that +0? diff automatically casts chars to numbers

In my version if I dont't add it, diff treats the string as sym and tries to differentiate.

Then maybe move the plus to the front (as a unary operator) and remove the zero

Java, 59 bytes
int c(int i){return(i+"").matches("^(.)\\1*$")?0:c(i+1)+1;}

(I'm still not sure how to count Java entries, but according to the standard set by the first Java entry, this entry is 59 bytes, since it's 17 bytes shorter).
Anyway, if we have a repdigit, return 0, else add 1 to the input, call itself and add 1 to the result.

Ungolfed & test cases:
Try it here.
class Main{
  static int c(int i) {
    return
      (i+"").matches("^(.)\\1*$")
      ? 0
      : c(i+1) + 1;
  }

  public static void main(String[] a){
    System.out.println(c(8));
    System.out.println(c(100));
    System.out.println(c(113));
    System.out.println(c(42));
    System.out.println(c(20000));
    System.out.println(c(19122));
    // Entry below will run out of memory
    System.out.println(c(19121));
  }
}

Output:
Runtime error   time: 0.09 memory: 321152 signal:-1
0
11
109
2
2222
3100

As you can see, the last entry runs out of memory before it can finish. The (very appropriate) StackOverflowError is thrown from java.util.regex.Pattern.sequence(Pattern.java:2134), but I'm pretty confident there's nothing wrong with the regex itself, since it's the same one I used in my previous entry.

Ruby, 42 characters
->n{i=0;n.next!&&i+=1while n.squeeze[1];i}

Expects string input.
Sample run:
irb(main):019:0> ->n{i=0;n.next!&&i+=1while n.squeeze[1];i}['87654321']
=> 1234567

Ruby, 39 characters
Recursive call, runs into “SystemStackError: stack level too deep” on bigger results.
r=->n,i=0{n.squeeze[1]?r[n.next,i+1]:i}

Sample run:
irb(main):001:0> r=->n,i=0{n.squeeze[1]?r[n.next,i+1]:i}
=> #<Proc:0x00000002367ca0@(irb):10 (lambda)>

irb(main):002:0> r['20000']
=> 2222

Prolog, 120 bytes
r([H|T]):-r(H,[H|T]).
r(H,[H|T]):-r(H,T).
r(_,[]).
g(N,0):-number_chars(N,L),r(L).
g(N,X):-N1 is N+1,g(N1,X1),X is X1+1.

Try it online!

Forth (gforth), 54 bytes
: f 0 over s>f flog f>s 1+ 0 do 10 * 1- loop mod abs ;

Try it online!
Explanation

Gets the smallest repdigit of the same length as the input.
Negates the result and gets the remainder of dividing the input by that number.
Returns the absolute value of the result (since positive modulo negative is negative)

Code Explanation
: f                \ start a new word definition
  0 over           \ place 0 on stack and copy input back to top
  s>f flog f>s     \ move number to floating point stack, get log10, move back to stack (truncate)
  1+               \ add 1 to get number of digits
  0 do             \ start a loop from 0 to number of digits - 1
    10 * 1-        \ repeatedly multiply by 10 and subtract 1 to get smallest repdigit of that size
  loop             \ end loop
  mod abs          \ get that absolute value of input modulo result
;                  \ end the word definition

Brachylog v2, 6 bytes
;.+=∧ℕ

Try it online!
  +       The sum of
          the input
;         and
 .        the output
   =      is a repdigit,
    ∧     and
          the output
     ℕ    is a whole number.

The 5-byte +↙.=∧ gets away with omitting ℕ because it doesn't try non-positive outputs at all, but it also fails when given a number which is already a repdigit because it doesn't try non-positive outputs at all.

Rockstar, 122 bytes
listen to N
let M be N-1
O's 0
until O
let M be+1
cut M in S
roll S in D
O's 1
while S and O
let O be D's roll S

say M-N

Try it (Code will need to be pasted in)

C#, 82 bytes
using System.Linq;n=>{int i=n;while((i+"").Distinct().Count()!=1)++i;return i-n;};

C, 84 bytes
d,n,l,f;F(i){for(n=0;1;){l=i+n++;d=l%10;f=0;while(l/=10)f|=l%10-d;if(!f)return--n;}}

Test main:
int main() {
  printf("%d\n", F(8));
  printf("%d\n", F(100));
  printf("%d\n", F(113));
  printf("%d\n", F(87654321));
  printf("%d\n", F(47));
  printf("%d\n", F(20000));
  printf("%d\n", F(11132));
}

J, 39 bytes
f=.$:&>:`[@.(1=#@~.@(10&#.inv)@])
g=.0&f

Take the digits (10&#.inv)@], remove dups ~., check if the length is 1 (same basic idea as Dennis's solution).  Recurse with incremented left and right args if it's not.
Note because $: recurses on the entire verb, we need to define a second verb to give the left arg an initial value of 0.  I'd be curious to know how to avoid that, if possible.
Also, I'd be curious to know if there is a way to do this with ^: (do... while version).
Try it online!

TI-BASIC, 51 bytes
Ans→A:Ans→B:Repeat dim(Ans)=sum(Ans(1)=Ans:B+1→B:int(10fPart(B₁₀^(seq(⁻X-1,X,0,log(B:End:B-A

Slowly iterates through all integers greater than the input until the next repdigit has been reached.
Checks \$\approx20\$ numbers per second.
Input is the current reputation in Ans.
Output is the amount of rep required to reach the next repdigit.
Examples:
100
             100
prgmCDGF1D
              11
11132
           11132
prgmCDGF1D
           11090

Test case 11132 took \$\approx9.5\$ minutes to run.
Explanation:
Ans→A                                ;store the input into A and B
Ans→B
Repeat dim(Ans)=sum(Ans(1)=Ans       ;"do-while" the digits of B are not equal
B+1→B                                ;increment B
int(10fPart(B₁₀^(seq(⁻X-1,X,0,log(B  ;generate a list of B's digits reversed.  leave it in Ans
End
B-A                                  ;calculate the rep needed.  leave the result in Ans
                                     ;implicit print of Ans

Note:  TI-BASIC is a tokenized language.  Character count does not equal byte count.

Thunno 2, 5 bytes
µƘạ;_

Try it online!
Explanation
µƘạ;_  # Implicit input
µƘ ;   # Starting from the input, find the first integer where:
  ạ    #  Its digits are all equal (i.e. it's a repdigit)
    _  # Subtract the input from this number
       # Implicit output

Desmos, 70 bytes
Ported from @Anastasiya-Romanova 秀's Excel solution.
d=floor(logn)
a=floor(n/10^d)
r=∑_{i=0}^d10^i
f(n)=(a+\{ar<n,0\})r-n

Try it on Desmos!

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