# The Take-back counting algorithm

Kids who are learning how to count often know runs of numbers, but can't seem to put those runs together properly.

For example, they might say:

1,2,3,4,7,8,9,10


Sometimes kids will realize that they skipped some numbers, and go back:

1,2,3,4,7,8,5,6,7,8,9,10


This is clearly the superior pattern. We need to identify them.

To identify these lists:

1. We identify the minimum M and the maximum N of the list

2. We step through the list. If the current number is greater than or equal to any member of the list to its right, then we remove the current number.

3. Iff the remaining list contains all numbers from M to N, then we return a truthy value.

You can assume your input list will contain at least 1 element. You can assume that all integers will be non-negative.

## Test cases:

Truthy:

0
10
0 0 0
1 0 1
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 0 1 2 3
0 1 2 3 4 5 5
0 1 1 2 2 3
0 3 6 1 4 7 2 5 8 3 4 5 6 7 8
1 3 5 7 2 3 4 5 6 7
5 6 0 1 2 3 6 7 4 5 6 7
5 6 7 8
5 5 6 7 8
4 6 7 8 3 4 5 6 7 8


Falsy:

1 0
4 3 2 1
1 2 3 7 8 9
0 1 2 3 1 3
0 1 2 3 1 3 4
0 1 2 3 1 3 2 4
0 1 2 3 1 3 2 4 3
1 3 5 7 2 4 6 8
0 1 2 1 3 4 5 6
4 5 6 3 4 5


This is , so make your answers as short as possible!

• Not very clear: should [0,1,2,3,4,5,4,3,2,1] be considered true or false?
– G B
Commented May 29, 2017 at 12:10
• @GB False. When you are on the second element, you would remove it on step 2 (because there's another 1 later down the line). You'd also remove every other element (except for the last 1), so you'd end up with 0 1, which is not 0 1 2 3 4 5 Commented May 29, 2017 at 12:19

# 05AB1E, 5 bytes

I am not 100% certain this works, but it passes all test cases and I couldn't find any situation where it fails.

Ú¥1QP


Try it online!

Ú¥1QP   Main link. Argument a
Ú       Reverse uniquify a, keeps only last occurence of each element
¥      Get all deltas - all 1 if ascending list
1Q    Compare all deltas to 1
P   Product of all results

• 7 bytes, in fact Commented May 29, 2017 at 9:19
• @val No, 05AB1E uses a custom encoding, 05AB1E. Commented May 29, 2017 at 9:20

# Jelly, 10 9 bytes

ṀrṂɓṚ«\Q⁼


Try it online!

### How it works

ṀrṂɓṚ«\Q⁼  Main link. Argument: A (array)

Ṁ          Yield the maximum of A.
Ṃ        Yield the minimum of A.
r         Yield R := [max(A), ... min(A).
ɓ       Begin a new chain. Left argument: A. Right argument: R
Ṛ      Reverse A.
«\    Take the cumulative minimum.
Q   Unique; deduplicate the results.
⁼  Compare the result with R.

• Interesting, is ɓ a relatively new feature? Commented May 29, 2017 at 4:19
• Yes, it's from a pull request by Jonathan Allan. Commented May 29, 2017 at 4:20
• Aha, 13 days ago. Hadn't seen it used yet though (maybe you or Jonathan have and I just missed it). Commented May 29, 2017 at 4:24
• The real interesting part here is «\ in my opinion though. Commented May 29, 2017 at 9:55

# Ruby, 59 54 41 bytes

->a{a.reverse|[]==[*a.max.downto(a.min)]}


Try it online!

# Python 2, 81 bytes

x=input();r=m=[]
for n in x[::-1]:r=[n][:n<m]+r;m=r[0]
print r==range(m,max(x)+1)


Try it online!

# PHP, 148 130 bytes

-18 bytes, thanks @Christoph

$a=explode(' ',$argn);$b=range(min($a),max($a));foreach($a as$i=>&$k)for(;++$i<count($a);)$k<$a[$i]?:$k=-1;echo!array_diff($b,$a);


Try it online!

• Ok a lot to comment here: $argn is always a string foreach doesn't work on it. You could use $argv to get an array as input but beware that it always contains the filename as first element. You use $m and $n only once so you can save a lot of bytes creating $b earlier: $b=range(min($a),max($a));. The cast (bool) is completly unnecessary. if($k>=$a[$s])$a[$i]=null; to $k<$a[$s]?:$a[$i]=-1;. Using reference we can do this: foreach($a as$i=>&$k) (+1 byte) and $a[$i] to $k(-4 byte). Moreover that lets us drop $s=$i because we can iterate over $idirectly now. Commented May 29, 2017 at 9:28 • The result looks like this $a=$argn;$b=range(min($a),max($a));foreach($a as$i=>&$k)for(;++$i<count($a);)$k<$a[$i]?:$k=-1;echo!array_diff($b,$a); (117 bytes). But it still uses $argn in the wrong way. $a=explode(' ',$argn); would fix this for 13 additional bytes. Commented May 29, 2017 at 9:29
• No problem ! Always nice to find a new PHP golfer I hope to see more of you :) either Titus, Jörg or me are always there to help ! Commented May 29, 2017 at 10:00
• @Christoph Why not using $_GET as Input array? In this case there is no need to use explode additonal -6 Bytes for using not the $b variable Commented May 29, 2017 at 12:17
• @Christoph Okay In this case we need a Version under 7.1 and we use ´a& instead of ~ Try it online! Commented May 29, 2017 at 13:46

# Java 8, 264 262 bytes

import java.util.*;l->{int m=Collections.max(l),n=Collections.min(l),i=0,q;for(;i<(q=l.size());i++)if(l.subList(i+1,q).size()>0&&l.get(i)>=Collections.min(l.subList(i+1,q)))l.remove(i--);for(i=0;n<=m;)if(i<l.size()&&l.get(i++)==n)n++;else return 0>1;return 1>0;}


Explanation:

Try it here.

import java.util.*;                 // Import for Collections

l->{                                // Method with integer-ArrayList parameter and boolean return-type
int m=Collections.max(l),         //  Max of the list
n=Collections.min(l),         //  Min of the list
i=0,q;                        //  Two temp integers
for(;i<(q=l.size());i++)          //  Loop (1) over the list
if(l.subList(i+1,q).size()>0    //   If the sublist right of the current item is not empty
&&l.get(i)>=Collections.min(l.subList(i+1,q)))
//   and if the current item is larger or equal to the lowest value of this sublist
l.remove(i--);                //    Remove the current item from the main list
//  End of loop (1) (implicit / single-line body)
for(i=0;n<=m;)                    //  Loop (2) from min to max
if(i<l.size()                   //   If the current item doesn't exceed the list's size
&&l.get(i++)==n)                //   and the items are in order so far
n++;                          //    Go to the next item
else                            //   Else:
return 0>1;//false            //    Return false
//  End of loop (2) (implicit / single-line body)
return 1>0;//true                 //  Return true
}                                   // End of method


# R, 88 85 bytes

y=NULL;for(i in x<-scan())if(all(i<x[-(1:(F<-F+1))]))y=c(y,i);all(min(x):max(x)%in%y)


This can probably be golfed down further. Loops over the elements of x, checks if all upcoming values are bigger, and only then keeps that element. After the loop it creates a sequence from min(x) to max(x), and checks with %in% if all values are included in the pruned version of x.

• By porting Dennis' answer we could get down to 53 bytes. function(n)all(unique(cummin(rev(n)))==max(n):min(n)) Commented Sep 21, 2017 at 17:13

## JavaScript (ES6), 60 bytes

s=>(o={},s.reverse().every((n,i)=>!i|o[n+1]|o[n]&&(o[n]=1)))


Ungolfed:

s=>(
o={},
s.reverse().every((n,i)=>
!i|o[n+1]|o[n]&&(o[n]=1)
)
)


This is a simpler algorithm:

Iterate the array in reverse, and make sure each number (except the first) is one less than or equal to a number already seen.

Snippet:

f=

s=>(o={},s.reverse().every((n,i)=>!i|o[n+1]|o[n]&&(o[n]=1)))

console.log('Truthy');
console.log(f([0]))
console.log(f([10]))
console.log(f([0,0,0]))
console.log(f([1,0,1]))
console.log(f([0,1,2,3,4,5,6,7,8,9,10]))
console.log(f([0,1,2,3,0,1,2,3]))
console.log(f([0,1,2,3,4,5,5]))
console.log(f([0,1,1,2,2,3]))
console.log(f([0,3,6,1,4,7,2,5,8,3,4,5,6,7,8]))
console.log(f([1,3,5,7,2,3,4,5,6,7]))
console.log(f([5,6,0,1,2,3,6,7,4,5,6,7]))
console.log(f([5,6,7,8]))
console.log(f([5,5,6,7,8]))
console.log(f([4,6,7,8,3,4,5,6,7,8]))

console.log('Falsy');
console.log(f([1,0]))
console.log(f([4,3,2,1]))
console.log(f([1,2,3,7,8,9]))
console.log(f([0,1,2,3,1,3]))
console.log(f([0,1,2,3,1,3,4]))
console.log(f([0,1,2,3,1,3,2,4]))
console.log(f([0,1,2,3,1,3,2,4,3]))
console.log(f([1,3,5,7,2,4,6,8]))
console.log(f([0,1,2,1,3,4,5,6]))
console.log(f([4,5,6,3,4,5]))

## Haskell, 62 bytes

g(a:b)=[a|all(a<)b]++g b
g a=a
f x=g x==[minimum x..maximum x]


Try it online!

A direct implementation of the definition where g removes the elements if they are >= than the the elements to its right.

# C#, 69 bytes

s=>s.Where((e,i)=>s.Skip(i+1).All(r=>e<r)).Count()==s.Max()-s.Min()+1


In short:
s = input (s)equence
take from s element where all items after this one (skip (I)ndex + 1 items), current value is higher
count these, and see if the amount left is equal to the amount expected ((max)imum value minus (min)imum) amount of numbers

Try it online!

• @MDXF Do you want to welcome him? Commented Sep 21, 2017 at 16:55
• @StanStrum did i misunderstand the rules? is my english too messy? i -am- posting for the first time... Commented Sep 21, 2017 at 16:57
• No, no! It's a privilege to welcome a newcomer to PPCG, and I was asking him if he'd wanted to say hi to you Commented Sep 21, 2017 at 16:58
• Looks like the privilege is to the both of you. Thanks, people ^^ Commented Sep 21, 2017 at 16:59
• This is a great first answer, hope you have fun in your future of PPCG! Commented Sep 21, 2017 at 17:00

## JavaScript (ES6), 827372 70 bytes

Returns a boolean.

a=>a.filter((x,i)=>k-=a.every(y=>~i--<0|y>x,m=x>m?x:m),m=k=0)[0]+~m==k


### How?

We iterate on each element x of the input array a, keeping track of the maximum encountered value m and the number -k of values that are not greater than or equal to any member to their right. By definition, valid values appear in strictly ascending order.

We use filter() rather than map(), so that all elements get filtered out until k turns negative. This allows us to isolate the first valid element, which is also guaranteed to be the minimum value of the array.

Finally, we test whether minimum - (maximum + 1) == -number_of_valid_elements:

a.filter(...)[0] + ~m == k


### Test cases

let f =

a=>a.filter((x,i)=>k-=a.every(y=>~i--<0|y>x,m=x>m?x:m),m=k=0)[0]+~m==k

console.log('[Truthy]');
console.log(f([0]));
console.log(f([10]));
console.log(f([0,0,0,]));
console.log(f([1,0,1]));
console.log(f([0,1,2,3,4,5,6,7,8,9,10]));
console.log(f([0,1,2,3,0,1,2,3]));
console.log(f([0,1,2,3,4,5,5]));
console.log(f([0,1,1,2,2,3]));
console.log(f([0,3,6,1,4,7,2,5,8,3,4,5,6,7,8]));
console.log(f([1,3,5,7,2,3,4,5,6,7]));
console.log(f([5,6,0,1,2,3,6,7,4,5,6,7]));
console.log(f([5,6,7,8]));
console.log(f([5,5,6,7,8]));
console.log(f([4,6,7,8,3,4,5,6,7,8]));

console.log('[Falsy]');
console.log(f([1,0]));
console.log(f([4,3,2,1]));
console.log(f([1,2,3,7,8,9]));
console.log(f([0,1,2,3,1,3]));
console.log(f([0,1,2,3,1,3,4]));
console.log(f([0,1,2,3,1,3,2,4]));
console.log(f([0,1,2,3,1,3,2,4,3]));
console.log(f([1,3,5,7,2,4,6,8]));
console.log(f([0,1,2,1,3,4,5,6]));
console.log(f([4,5,6,3,4,5]));`