14
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Not very clear: should [0,1,2,3,4,5,4,3,2,1] be considered true or false? \$\endgroup\$ – G B May 29 '17 at 12:10
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Nathan Merrill May 29 '17 at 12:19

11 Answers 11

6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 7 bytes, in fact \$\endgroup\$ – val May 29 '17 at 9:19
  • 2
    \$\begingroup\$ @val No, 05AB1E uses a custom encoding, 05AB1E. \$\endgroup\$ – Erik the Outgolfer May 29 '17 at 9:20
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Interesting, is ɓ a relatively new feature? \$\endgroup\$ – ETHproductions May 29 '17 at 4:19
  • \$\begingroup\$ Yes, it's from a pull request by Jonathan Allan. \$\endgroup\$ – Dennis May 29 '17 at 4:20
  • \$\begingroup\$ Aha, 13 days ago. Hadn't seen it used yet though (maybe you or Jonathan have and I just missed it). \$\endgroup\$ – ETHproductions May 29 '17 at 4:24
  • \$\begingroup\$ The real interesting part here is «\ in my opinion though. \$\endgroup\$ – Erik the Outgolfer May 29 '17 at 9:55
2
\$\begingroup\$

Ruby, 59 54 41 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Christoph May 29 '17 at 9:28
  • \$\begingroup\$ 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. \$\endgroup\$ – Christoph May 29 '17 at 9:29
  • 1
    \$\begingroup\$ 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 ! \$\endgroup\$ – Christoph May 29 '17 at 10:00
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Jörg Hülsermann May 29 '17 at 12:17
  • 1
    \$\begingroup\$ @Christoph Okay In this case we need a Version under 7.1 and we use ´a&` instead of ~ Try it online! \$\endgroup\$ – Jörg Hülsermann May 29 '17 at 13:46
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By porting Dennis' answer we could get down to 53 bytes. function(n)all(unique(cummin(rev(n)))==max(n):min(n)) \$\endgroup\$ – Giuseppe Sep 21 '17 at 17:13
1
\$\begingroup\$

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]))

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @MDXF Do you want to welcome him? \$\endgroup\$ – Stan Strum Sep 21 '17 at 16:55
  • \$\begingroup\$ @StanStrum did i misunderstand the rules? is my english too messy? i -am- posting for the first time... \$\endgroup\$ – Barodus Sep 21 '17 at 16:57
  • \$\begingroup\$ 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 \$\endgroup\$ – Stan Strum Sep 21 '17 at 16:58
  • \$\begingroup\$ Looks like the privilege is to the both of you. Thanks, people ^^ \$\endgroup\$ – Barodus Sep 21 '17 at 16:59
  • \$\begingroup\$ This is a great first answer, hope you have fun in your future of PPCG! \$\endgroup\$ – Stan Strum Sep 21 '17 at 17:00
0
\$\begingroup\$

JavaScript (ES6), 82 73 72 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]));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.