# Find The Sum of the First n Bouncy Numbers

Terminology

An increasing number is one where each digit is greater than or equal to all the digits to the left of it (ex. 12239)

A decreasing number is one where each digit is less than or equal to all the digits to the left of it (ex. 95531)

A bouncy number is any number that is not increasing or decreasing. Since this requires at least 3 digits, the first bouncy number is 101

Given an integer n greater than or equal to 1, find the sum of the first n bouncy numbers

Rules

• This is code golf, so the answer with the shortest amount of bytes wins
• If your language has limits on integer size (ex. 2^32-1) n will be small enough that the sum will fit in the integer
• Input can be any reasonable form (stdin, file, command line parameter, integer, string, etc)
• Output can be any reasonable form (stdout, file, graphical user element that displays the number, etc)

Test cases

1 > 101
10 > 1065
44701 > 1096472981

• I'm not sure I understand your Restrictions. Can I sort the numbers and check if they're the same as the original number? That's using a built-in (sort), but it's not strictly a built-in to check if it's increasing. Check out Non-observable program requirements and Do X without Y on our "Things to avoid" Meta post. Jul 6 '18 at 19:54
• Hi, Welcome to PPCG! While this is a nice first post (+1), I have some small suggestions: No builtins that check if a number is increasing may be used, No builtins that check if a string is lexicographically increasing may be used (disallowing built-ins) is a thing to avoid when writing challenges; we have a Sandbox for Proposed challenges, where you can share your post idea before submission in order to receive feedback and guidance :) Jul 6 '18 at 19:54
• I updated the restrictions to better match the "Exceptions" category of the link you posted Jul 6 '18 at 20:03
• I still do not see the point of having such a restriction in the first place. Of course, it is up to you whether to keep it or not, but forbidding built-ins is typically bad practice. If you feel like the challenge is trivialised by built-ins, you should note that simply restricting them doesn't make solving the task more interesting, but rather adds boilerplate. Could you consider removing that restriction? (by the way, this still falls under Do X without Y) Otherwise, I like the idea quite a lot, and I wouldn't want a slightly subjective restriction to detract from the actual task. Jul 6 '18 at 20:06
• I have however removed the restriction, as it is clear that it is more enjoyable for the community that way, and will trust the guidelines and best practices here that ensure challenges are of the best quality Jul 6 '18 at 20:23

# Jelly, 10 8 bytes

ṢeṚƬ¬µ#S


Try it online!

### How it works

ṢeṚƬ¬µ#S  Main link. No arguments.

#   Read an integer n from STDIN and call the chain to the left with argument
k = 0, 1, 2, ... until n of them return a truthy result.
Yield the array of successful values of k.
µ    Monadic chain. Argument: k (integer)
Ṣ           Sort, after promoting k to its digit array.
ṚƬ        Reverse 'til the results are no longer unique and yield unique results.
Calling Ṛ on k promotes it to its digit array. If k = 14235, the
result is [14235, [5,3,2,4,1], [1,4,2,3,5]].
e          Check if the result to the left appears in the result to the right.
¬       Negate the resulting Boolean.
S  Take the sum.

• +1 ṚƬ is extremely neat... Jul 6 '18 at 20:26

# Pyth, 10 bytes

s.f!SI#_B


Try it here!

### How it works?

s.f!SI#_B – Full program. Takes an integer Q from STDIN and outputs to STDOUT.
.f        – Find the first Q positive integers that satisfy a certain condition.
!SI#_B  – The condition. Returns true for bouncy numbers only.
_B – Cast the number to a string and bifurcate (pair) it with its reverse.
#    – Filter-keep those...
I     – That are invariant under...
S      – Sorting.
– To clarify, I (invariant) is a Pyth operator that takes two inputs, a
function and a value and checks whether function(value) == value, so
this is technically not a built-in.
!       – Logical not. The empty list gets mapped to true, other values to false.
s          – Sum.


# K (ngn/k), 37 bytes

{+/x{{(a~&\a)|a~|\a:10\x}(1+)/x+1}\0}


Try it online!

{ } is a function with argument x

x{ }\0 applies the {} on 0 x times, preserving the intermediate results

(1+) is the successor function

{ }(1+)/x+1 applies the successor function starting from x+1 until the {} returns true

10\x are the decimal digits of x

a: assign to a

|\ is the max-scan (partial maxima) of a

&\ analogously, is the min-scan

a~|\a does a match its max-scan?

| or

a~&\a its min-scan?

+/ sum

# JavaScript (ES6), 77 bytes

f=(i,n=0,k,p)=>i&&([...n+''].map(x=>k|=x<p|2*(p<(p=x)))|k>2&&i--&&n)+f(i,n+1)


Try it online!

### Commented

f = (                     // f = recursive function taking:
i,                      //   i = number of bouncy numbers to find
n = 0,                  //   n = current value
k,                      //   k = bitmask to flag increasing/decreasing sequences
p                       //   p = previous value while iterating over the digits
) =>                      //
i && (                  // if there's still at least one number to find:
[...n + '']           //   turn n into a string and split it
.map(x =>             //   for each digit x in n:
k |=                //     update k:
x < p |           //       set bit #0 if x is less than the previous digit
2 * (p < (p = x)) //       set bit #1 if x is greater than the previous digit
//       and update p
)                     //   end of map()
| k > 2               //   if both bits are set (n is bouncy):
&& i--                //     decrement i
&& n                  //     and add n to the total
) + f(i, n + 1)         //   add the result of a recursive call with n + 1


# Python 2, 11092 89 bytes

n=input()
x=s=0
while n:b={-1,1}<=set(map(cmp,x[:-1],x[1:]));s+=x*b;n-=b;x+=1
print s


Try it online

This function determines if a number is bouncy:

lambda x:{-1,1}<=set(map(cmp,x[:-1],x[1:]))

• You can compare characters directly. In fact, your set comprehension can become set(map(cmp,x[:-1],x[1:])). Jul 6 '18 at 21:17
• @Jakob Thanks. I always forget you can use map that way. Jul 6 '18 at 21:20
• x=s=0\nwhile n:b={-1,1}<=set(map(cmp,x[:-1],x[1:]));s+=x*b;n-=b;x+=1 saves 3 bytes Jul 6 '18 at 21:25

# Python 2, 84 bytes

i=s=0
n=input()
while n:b=i>sorted(i)[2::5]<i[::-1];n-=b;s+=b*i;i+=1
print s


Try it online! Or see a test-suite.

# Retina, 93 bytes

K:
"$+"{/(?=.*;(_*);\1_)(?=.*_(_*);\2;)/^{:(#*).* :$1#;$.($1#
)\d
*_;
):(#+).*
$1:$1
\G#


Try it online! Explanation:

K:


Initialise s=i=0. (s is the number of #s before the :, i the number of #s after.)

"$+"{ ... )  Repeat n times. /(?=.*;(_*);\1_)(?=.*_(_*);\2;)/^{ ... )  Repeat while i is not bouncy. :(#*).* :$1#;$.($1#


Increment i and make a copy in decimal.

\d
*_;


Convert the digits of the copy to unary. The bounciness test uses the unary copy, so it only works once i has been incremented at least once.

:(#+).*
$1:$1


Add i to s and delete the copy of the unary digits, so that for the next pass of the inner loop the bounciness test fails and i gets incremented at least once.

\G#


Convert s to decimal.

121 byte version calculates in decimal, so might work for larger values of n:

K0:0
"$+"{/(?=.*;(_*);\1_)(?=.*_(_*);\2;)/^{:(\d+).* :$.($1*__);$.($1*__) )+;\d ;$&*_;
)\d+:(\d+).*
$.(*_$1*):$1 :.*  Try it online! Explanation: K0:0  Initialise s=i=0. "$+"{
...
)


Repeat n times.

/(?=.*;(_*);\1_)(?=.*_(_*);\2;)/^{
...
)


Repeat while i is not bouncy.

:(\d+).*
:$.($1*__);$.($1*__)


Increment i and make a copy.

+;\d
;$&*_;  Convert the digits of the copy to unary. The bounciness test uses the unary copy, so it only works once i has been incremented at least once. \d+:(\d+).*$.(*_$1*):$1


Add i to s and delete the copy of the unary digits, so that for the next pass of the inner loop the bounciness test fails and i gets incremented at least once.

:.*


Delete i.

# 05AB1E, 12 bytes

µN{Â‚Nå_iNO¼


Try it online!

Explanation

µ              # loop over increasing N until counter equals input
Nå_i      # if N is not in
N{Â‚          # the pair of N sorted and N sorted and reversed
NO    # sum N with the rest of the stack
¼   # and increment the counter


# Java 8, 114 112 bytes

n->{int i=0,s=0;for(;n>0;++i)s+=(""+i).matches("0*1*2*3*4*5*6*7*8*9*|9*8*7*6*5*4*3*2*1*0*")?0:--n*0+i;return s;}


Uses a regular expression to check if the number is increasing or decreasing. Try it online here.

Ungolfed:

n -> { // lambda
int i = 0, // the next number to check for bounciness
s = 0; // the sum of all bouncy numbers so far
for(; n > 0; ++i) // iterate until we have summed n bouncy numbers, check a new number each iteration
s += ("" + i) // convert to a String
.matches("0*1*2*3*4*5*6*7*8*9*" // if it's not an increasing  number ...
+ "|9*8*7*6*5*4*3*2*1*0*") ? 0 // ... and it's not a decreasing number ...
: --n*0 // ... we have found another bouncy number ...
+ i; // ... add it to the total.
return s; // return the sum
}


# Python 2, 250 bytes

n=input()
a=0
b=0
s=0
while a<n:
v=str(b)
h=len(v)
g=[int(v[f])-int(v[0]) for f in range(1,h) if v[f]>=v[f-1]]
d=[int(v[f])-int(v[0]) for f in range(1,h) if v[f]<=v[f-1]]
if len(g)!=h-1 and len(d)!=h-1:
a+=1
s+=b
b+=1
print s

• Welcome! You may wish to view this page for Tips for Golfing in Python Jul 6 '18 at 21:04
• I suggest using ; to put as many statements on a single line as possible, removing whitespace, and defining a function for the 2 long lines that are very similar, so you can reuse some of the code. Also, you can do a=b=s=0 and len(g)!=h-1!=len(d). Jul 6 '18 at 21:11
• Thanks for the tips. I've got to go now. but I'll work on it later. Jul 6 '18 at 21:37

# Stax, 14 bytes

Ö²àDæ▲☼Ty≡°lû↕


Run and debug it

## Ruby (123 106 bytes)

o=0
x=[?0]
(z=(x=(x.join.to_i+1).to_s.chars).sort)!=x&&z!=x.reverse ? (n-=1;o+=x.join.to_i):1while n>0
p o


Looks pretty ugly to me. Bounciness is defined in this block x.sort!=x&&x.sort!=x.reverse

# Red, 108 bytes

func[n][i: s: 0 until[t: form i
if(t > u: sort copy t)and(t < reverse u)[s: s + i n: n - 1]i: i + 1
0 = n]s]


Try it online!

f: func [ n ] [
i: s: 0
until [
t: form i
if ( t > u: sort copy t ) and ( t < reverse u ) [
s: s + i
n: n - 1
]
i: i + 1
0 = n
]
s
]


A good opportunity to use form - form i is 5 bytes shorter than to-string i

# MATL, 31 30 bytes

l9tVdZS&*0<a?wQtG>?.]y]QT]xvs


Try it online!

l       % Initialize counter to 1
9       % First value to check for being bouncy
       % Start do-while loop
tV    % duplicate the current number and convert to string
% (let's use the iteration where the number is 1411)
% stack: [1, 1411, '1411']
d     % compute differences between the characters
%  For non-bouncy numbers, this would be either all
%  positive values and 0, or all negative values and 0
% stack: [1, 1411, [3 -3 0]]
ZS    % keep only the signs of those differences
% stack: [1, 1411, [1 -1 0]]
&*    % multiply that array by its own transpose, so that
%  each value is multiplied by every other value
%  since it would have had only all -1s or all 1 (other than 0s)
% stack: [1, 1411, [1 -1  0
-1  1 0
0  0  0]]
0<a?  % if any value in the matrix is less than 0
wQ    % switch the counter to top, increment it
% stack: [1411, 2]
tG>?  % duplicate it, check if it's gotten greater than the input limit
.]    % if so, break out of loop
y]    % else, duplicate bouncy number from inside stack,
%  keeping a copy to be used for summing later
% stack: [1411, 2, 1411]
QT    % increment number, push True to continue loop
]     % loop end marker
x     % if we've broken out of loop, remove counter from stack
v     % concatenate the bouncy numbers we've collected in stack and
s     % sum them


# R, 96 bytes

function(n){while(n){y=diff(T%/%10^(0:log10(T))%%10);g=any(y<0)&any(y>0);F=F+T*g;n=n-g;T=T+1};F}


Try it online!

Explanation :

while(n){                         # while n > 0

T%/%10^(0:log10(T))%%10   # split T into digits(T==TRUE==1 at the 1st loop)
y=diff(                         ) # compute the diff of digits i.e. digits[i] - digits[i+1]

g=any(y<0)&any(y>0)               # if at least one of the diff is < 0 and
# at least one is > 0 then T is "bouncy"

F=F+T*g                           # if bouncy increment F (F==FALSE==0 at the 1st loop)

n=n-g                             # decrement n by 1 if bouncy

T=T+1}                            # increment T by 1 and loop

F}                                # return F


# Ruby, 76 bytes

->n,s=i=0{[d=(i+=1).digits,d.reverse].index(d.sort)||(s+=i;n-=1);n<1?s:redo}


Try it online!

# C (gcc), 104 bytes

f(b,o,u,n,c,y){for(o=u=0;b;u+=y?0:o+0*--b,++o)for(n=o,y=3;n/10;)c=n%10,n/=10,y&=(c-=n%10)<0?:c?2:y;b=u;}


Try it online here.

Ungolfed:

f(n, // function: return type and type of arguments defaults to int;
// abusing extra arguments to declare variables
i,   // number currently being checked for bounciness
s,   // sum of the bouncy numbers
j,   // copy of i to be used for checking bounciness in a loop
p,   // used for investigating the last digit of j
b) { // whether i is not bouncy; uses the two least significant bits to indicate increasing/decreasing
for(i = s = 0; // check numbers from zero up; initial sum is zero
n; // continue until we have n bouncy numbers
s += b ? 0 // not bouncy, no change to the sum
: i + 0* --n, // bouncy, add it to the sum and one less bouncy number to go
++i) // either way, move to the next number
for(j = i, b = 3; j/10; ) // make a copy of the current number, and truncate it from the right until there is just one digit left
// bounciness starts as 0b11, meaning both increasing and decreasing; a value of 0 means bouncy
p = j % 10, // get the last digit
j /= 10, // truncate one digit from the right

• Suggest u+=!y?--b,o:0,++o instead of u+=y?0:o+0*--b,++o, ;y&=(c-=n%10)<0?:c?2:y)c=n%10,n/=10; instead of ;)c=n%10,n/=10,y&=(c-=n%10)<0?:c?2:y;` Oct 26 '18 at 1:30