44
\$\begingroup\$

Introduction

Suppose you have a ruler with numbers from 0 to r-1. You place an ant between any two of the numbers, and it starts to crawl erratically on the ruler. The ruler is so narrow that the ant cannot walk from one position to another without walking on all the numbers in between. As the ant walks on a number for the first time, you record it, and this gives you a permutation of the r numbers. We say that a permutation is antsy if it can be generated by an ant in this way. Alternatively, a permutation p is antsy if every entry p[i] except the first is within distance 1 from some previous entry.

Examples

The length-6 permutation

4, 3, 5, 2, 1, 0

is antsy, because 3 is within distance 1 of 4, 5 is within distance 1 of 4, 2 is within distance 1 from 3, 1 is within distance 1 from 2, and 0 is within distance 1 from 1. The permutation

3, 2, 5, 4, 1, 0

is not antsy, because 5 is not within distance 1 of either 3 or 2; the ant would have to pass through 4 to get to 5.

The task

Given a permutation of the numbers from 0 to r-1 for some 1 ≤ r ≤ 100 in any reasonable format, output a truthy value if the permutation is antsy, and a falsy value if not.

Test cases

[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True

Fun fact: for r ≥ 1, there are exactly 2r-1 antsy permutations of length r.

\$\endgroup\$
4
  • 7
    \$\begingroup\$ This is a very interesting challenge with many different solutions: I count at least 7 unique strategies being used so far. \$\endgroup\$ Oct 24, 2016 at 16:05
  • 1
    \$\begingroup\$ The structured input form of permutations is contributing a lot to the variety of approaches. The condition for being antsy can be expressed in different ways that are inequivalent on general lists. \$\endgroup\$
    – xnor
    Oct 24, 2016 at 21:51
  • 2
    \$\begingroup\$ I'm disappointed there isn't an ANTSI C solution yet. \$\endgroup\$ Oct 26, 2016 at 6:15
  • \$\begingroup\$ @NoSeatbelts ANSI \$\endgroup\$
    – S.S. Anne
    Mar 11, 2020 at 16:19

28 Answers 28

19
\$\begingroup\$

Pyth, 7 bytes

/y+_QQS

Try it online. (Only small test cases are included due to exponential run-time.) Outputs 2 for Truthy, 0 for Falsey.

/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

In other words,

lambda l: subseq(sorted(l), concat(reverse(l), l))

where subseq outputs whether the elements of the first list appear in order in the second list, not necessarily adjacent. The subseq is done in Pyth by taking all subsets of the second list, which keep the order of the elements, and counting the number of occurrences of the first list. This takes exponential time.

Why does this work? For a permutation to be antsy, stepping from 0 to n-1 must consist of going only left, then going only right. This is because the elements greater than the first element must increase left to right, and those less than it must decrease left to right.

[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1      
 2  ^        
    3     ^
          4

If we mirror the list by putting a reversed copy to its left, this walk now only goes right.

[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |             
 0     ^      |             
       1      | ^           
              | 2  ^        
              |    3     ^  
              |          4                                  

Conversely, any rightward of this mirror list corresponds to a left-then-right walk of the original list. This rightward just is a sorted subsequence of 0 to n-1. In an antsy list, this sorted subsequence is unique, except for an arbitrary choice between the two adjacent copies of the original first element.

\$\endgroup\$
4
  • 7
    \$\begingroup\$ You can cut it down to 6 bytes by using... just kidding. \$\endgroup\$
    – jwg
    Oct 24, 2016 at 15:24
  • 3
    \$\begingroup\$ There's something hideous about using an exponential-time approach to a problem with an obvious linear-time solution even if it golfs down nicely. \$\endgroup\$ Oct 24, 2016 at 21:05
  • \$\begingroup\$ @jwg I'd believe it, actually. If the list count took arguments in the opposite order, you could get 6 bytes by taking two inputs implcitly. \$\endgroup\$
    – xnor
    Oct 24, 2016 at 21:29
  • \$\begingroup\$ ayyyyy, turning to the pyth side :D \$\endgroup\$
    – Maltysen
    Oct 25, 2016 at 0:42
12
\$\begingroup\$

Haskell, 46 bytes

(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Checks whether the vector difference of the running maxima and the running minima is [0,1,2,3...].

l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]  
difference =    [0, 1, 2, 3, 4]

Zgarb saved 2 bytes with (%)=scanl1.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ That's so clever! +1 \$\endgroup\$ Oct 24, 2016 at 15:47
  • 1
    \$\begingroup\$ Could you save some bytes by defining (#)=scanl1? \$\endgroup\$
    – Zgarb
    Oct 24, 2016 at 17:36
  • 1
    \$\begingroup\$ @Zgarb Thanks, I forgot you could do that. \$\endgroup\$
    – xnor
    Oct 24, 2016 at 21:27
9
\$\begingroup\$

JavaScript (ES6), 45

a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

I thought it's too simple to need as explanation, but there is a trick, and just in case, here is my first version, pre-golf

a => {
  k = []; // I'll put a 1 in this array at position of each value 
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Note: in the golfed code a is used instead of k, as I need no reference to the original array inside the every call. So I avoid to pollute the global namespace reusing the parameter

Test

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g), 
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

\$\endgroup\$
3
  • \$\begingroup\$ Real nice. I tried this approach with recursion, but I can't get it below 65: f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1) \$\endgroup\$ Oct 24, 2016 at 15:58
  • \$\begingroup\$ How does this work? Are you using some mutable list magic? \$\endgroup\$
    – Zgarb
    Oct 24, 2016 at 16:59
  • \$\begingroup\$ @Zgarb explanation added \$\endgroup\$
    – edc65
    Oct 24, 2016 at 17:47
6
\$\begingroup\$

Python 2, 49 bytes

f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

Checks whether each prefix of the list contains all numbers between its min and max inclusive. It does so by checking if the difference of the max and min is less than its length.


54 bytes:

f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

Checks if the last element is either one less than the min of the other elements, or one more than their max. Then, removes the last element and recurses. On a single-element list, outputs True.

This can also be checked via an amusing but longer list comprehension.

lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

I'd like to use the inequality min(l)-2<l.pop()<max(l)+2, but the pop needs to happen first. Using a program to output via error code would likely be shorter.

\$\endgroup\$
6
\$\begingroup\$

Mathematica, 42 bytes

!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Uses pattern matching to try and find a prefix a whose maximum difference from the next element b is greater than 1 (and negating the result of MatchQ).

\$\endgroup\$
0
6
\$\begingroup\$

Perl, 39 38 35 bytes

Includes +1 for -p

Give sequence on STDIN:

antsy.pl <<< "2 1 3 0"

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I'm having a hard time trying to understand this one... Care to explain a little? thanks :-) (just the main idea should be enough) \$\endgroup\$
    – Dada
    Oct 25, 2016 at 19:44
4
\$\begingroup\$

MATL, 11 bytes

&-|R1=a4L)A

Try it online! Or verify all test cases.

Explanation

This computes a matrix of all pairwise absolute differences and keeps the upper triangular part. The result is true iff there is at least a 1 value in all columns except the first.

&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results
\$\endgroup\$
4
\$\begingroup\$

R, 72 64 60 bytes

v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

A permutation is antsy if and only if all its left subpermutations are continuous (i.e. have difference one when sorted).

If input is guaranteed to have length more than one, then we can replace 1:sum(1|v) with seq(v), which saves four bytes.

The seq(v) in the if condition behaves differently when the input is of length one --- it generates the sequence 1:v instead of seq_along(v). However, fortunately, the output turns out to be TRUE in this case, which is the desired behaviour. The same also happens for zero-length input.

In R, T is a preset variable equal to TRUE (but R allows you to redefine it). TRUE is also deemed to be equal to 1.

Thanks to @Billywob for some helpful improvements to the original solution.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Reading input using scan would save you two bytes. In that case it's exactly the same number of bytes as the for loop approach: v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1) which would be 2 bytes shorter than your vectorized approach. \$\endgroup\$
    – Billywob
    Oct 24, 2016 at 11:08
  • \$\begingroup\$ Nice idea, and I can go one better I think by abusing T. Will edit. \$\endgroup\$
    – JDL
    Oct 24, 2016 at 11:50
3
\$\begingroup\$

05AB1E, 7 bytes

Âìæ¹{¢O

Try it online! or as a modified test suite.

Explanation

Uses the process described by xnor in his brilliant Pyth answer.
Returns 2 for truthy instances and 0 for falsy.

Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)
\$\endgroup\$
3
\$\begingroup\$

Perl, 63 bytes

Note that @Gabriel Banamy came up with a shorter (55 bytes) answer. But I think this solution is still interesting, so I'm posting it.

The bytes count includes 62 bytes of code and -n flag.

s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

To run it :

perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Short explanations : converts each number k to the unary representation of k+1 (that +1 is needed so the 0s don't get ignored). Then for each number k+1 (expressed in unary as 1(1*)), we look if either k ($1 holds k) or k+2 (which is then 11$1) are present in the preceding string (referenced by $-backtick). If no, then we set $. to zero. At then end we print $. which will be 1 if we never set it to zero, or zero otherwise.

\$\endgroup\$
3
\$\begingroup\$

Brain-Flak 302 264 256 Bytes

Thanks to Wheat Wizard for saving 46 bytes

([]){{}({}<>)<>([])}{}<>(({}))([]){{}({}<>)<>([])}{}<>(({}<>))<>(()){{}(({})<(({})<>[({})]<>(())){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>({}<<>(({})<>[({})<>(())]){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>>)<>>[({})](<()>)){{}{}(<(())>)}{}}([][()(())]){((<{}{}>))}{}

The top of the stack will be a 1 for truthy and a 0 for falsy.

Truthy: Try it Online!
Falsy: Try it Online!

The idea is to hold the minimum and maximum number that the ant has visited in the off stack. Then compare each number to both of those and update the appropriate one. If the next number is not 1 less than the min or 1 more than the max, break out of the loop and return false.


Brief Explanation:

([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack 
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily 
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack
\$\endgroup\$
4
  • \$\begingroup\$ I would check for push pop reductions I see some already a few places where you could use this strategy. \$\endgroup\$
    – Wheat Wizard
    Oct 24, 2016 at 15:41
  • \$\begingroup\$ @WheatWizard I'm sure there are a few, I just didn't have time to work them out yet. Thanks for the reminder. \$\endgroup\$
    – Riley
    Oct 24, 2016 at 15:44
  • \$\begingroup\$ I'm glad this at least makes sense to you O_O \$\endgroup\$ Oct 24, 2016 at 16:26
  • \$\begingroup\$ You can also replace instances of ([]){({}[()]<({}<>)<>>)}{} with ([]){{}({}<>)<>([])}{} to save a couple more bytes \$\endgroup\$
    – Wheat Wizard
    Oct 24, 2016 at 18:56
3
\$\begingroup\$

Jelly, 9 8 7 bytes

;@UŒPċṢ

Try It Online!

A Jelly translation of xnor's answer.

Old solutions:

;\Ṣ€IỊȦ
;\Ṣ€IE€P

Try it online!

Works very similarly to my Pyth answer below:

;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?
\$\endgroup\$
5
  • \$\begingroup\$ The conversion of xnor's other method to Jelly is also 7 bytes »\_«\⁼Ṣ but much more efficient \$\endgroup\$
    – miles
    Oct 24, 2016 at 11:59
  • \$\begingroup\$ ŒBŒPċṢ and ;\Ṣ€IỊȦ should save one byte in each approach. \$\endgroup\$
    – Dennis
    Oct 24, 2016 at 14:31
  • \$\begingroup\$ Unfortunately, the first doesn't work because I would need the reversed input to be bounced, like UŒBŒPċṢ which doesn't save any bytes. The is nice, though; I had misread that atom to output the logical NOT of what it actually did. \$\endgroup\$
    – Steven H.
    Oct 24, 2016 at 20:26
  • \$\begingroup\$ I'm not sure why you'd need the U (or the @ now that I think about it). If an array is antsy, so is the reversed array, no? \$\endgroup\$
    – Dennis
    Oct 25, 2016 at 0:58
  • 1
    \$\begingroup\$ Not necessarily: [2, 1, 3, 0] is antsy but [0, 3, 1, 2] is not. \$\endgroup\$
    – Steven H.
    Oct 25, 2016 at 1:14
3
\$\begingroup\$

CJam (21 20 bytes)

{:A,{_)A<$2*)@-#},!}

Online test suite

Dissection

This uses the observation by xnor in his Haskell answer that the difference between the maximum and minimum of the first n elements should be n-1.

{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Alternative approach (also 20 bytes)

{_{a+_)f-:z1&,*}*^!}

Online test suite

This checks directly that each element after the first is at distance 1 from a previous element. Since the input is a permutation and hence doesn't repeat values, this is a sufficient test. Thanks to Martin for a 1-byte saving.

Dissection

{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}
\$\endgroup\$
2
  • \$\begingroup\$ I think this saves one? {_{a+_)f-:z1&,*}*^!} \$\endgroup\$ Oct 24, 2016 at 19:15
  • \$\begingroup\$ @MartinEnder, very nice. Curiously you posted that just as I was posting a completely different approach with the same byte count. \$\endgroup\$ Oct 24, 2016 at 21:45
3
\$\begingroup\$

Java, 100 98 79 75 bytes

a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Formerly:

a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

Saved 3 bytes by replacing true and false with 1>0 and 0>1.

Saved 23 bytes thanks to excellent suggestions from Peter Taylor!

Ungolfed:

a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Keep track of the highest and lowest values seen so far as m and n; only accept a new value if it is m + 1 or n - 1 i.e. the next higher or lower value; initialize the high value, m, to one less than the first element so that it will "match" the first time around the loop. Note: this is a linear-time, online algorithm. It requires only three words of memory, for the current, highest-so-far, and lowest-so-far values, unlike a lot of the other solutions.

If the next value misses both the high and low ends of the range, the lowest-so-far value is set to -1 and then the low end can never proceed and reach zero. We then detect an antsy sequence by checking whether the low value, n, reached zero.

(Unfortunately this is less efficient because we always have to look at the entire sequence rather than bailing out after the first wrong number, but it's hard to argue with a 23-byte savings (!) when other solutions are using O(n^2) and exponential time approaches.)

Usage:

import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Note: this can also be written without taking advantage of Java 8 lambdas:

Java 7, 89 bytes

boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}
\$\endgroup\$
6
  • \$\begingroup\$ Good handling of the special case. int m,n;m=n=a[0];--m; could be int n=a[0],m=n-1;, and the expensive return and else could be reduced with i==m+1?m++:n=(i==n-1)?i:-1;return n==0; (or something similar - I haven't tested this). \$\endgroup\$ Oct 25, 2016 at 7:30
  • \$\begingroup\$ @PeterTaylor Fantastic! Unfortunately, Java won't allow any side effects such as m++ or m+=1 there, so I still need an if and an else, and it loses the aspect of short circuiting on the first bad value, but that is a big improvement. Thank you! \$\endgroup\$ Oct 25, 2016 at 8:06
  • \$\begingroup\$ It will allow side-effects in a complex expression. What it might not like is using a general expression as a statement. In the worst case you need to create a dummy variable j and assign the result to it, but suspect there would be a better way of doing it. \$\endgroup\$ Oct 25, 2016 at 8:16
  • \$\begingroup\$ @PeterTaylor Well, I tried a few variations on it, including assigning it to a dummy variable g, and I couldn't get it to work. (I'm using Java 9-ea+138, maybe it's a difference between Java 8 and Java 9?) I may try again tomorrow. \$\endgroup\$ Oct 25, 2016 at 8:19
  • \$\begingroup\$ Got it. n-=i==m+1?m-m++:i==n-1?1:n+1; \$\endgroup\$ Oct 25, 2016 at 8:26
3
\$\begingroup\$

Jelly, 5 bytes

Ụ<ƝṢƑ

Try it online!

In Is it a tower permutation?, xnor comments

This is closely related to Antsy Permutations -- a tower permutation is one whose inverse permutation, read backwards as a list, is antsy.

Combining pxeger's answer to that question with (Grade, which inverts permutations) yields a short Jelly answer to this question.

Instead of reversing the list before inverting the permutation, which would cost another byte, I just check for "anti-towers" by changing > to <.

\$\endgroup\$
2
\$\begingroup\$

Pyth (fork), 13 bytes

!sstMM.+MSM._

No Try It Online link for this fork of Pyth. The fork includes the deltas function .+, which is not part of the standard Pyth library.

Explanation:

           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Seeing this convinces me to merge this into Pyth. \$\endgroup\$
    – isaacg
    Oct 24, 2016 at 8:11
2
\$\begingroup\$

J, 14 bytes

/:~-:>./\-<./\

This is based on @xnor's method.

Explanation

/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted
\$\endgroup\$
2
\$\begingroup\$

Perl, 66 54 +1 = 55 bytes

+1 byte for -n.

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Explanation:

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Prints 0 if false, 1 if true.

-11 bytes thanks to @Dada

\$\endgroup\$
4
  • 1
    \$\begingroup\$ That one is really nice. You can golf it down to 55 bytes though : perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.' : -n instead of <>=~ which allows you to get rid of /r modifier. use \d+ and then $& instead of (\d+) and $1. !@a instead of 0>$#a. $.&= instead of $.&&=. push@a,$& instead of @a=(@a,$&) \$\endgroup\$
    – Dada
    Oct 24, 2016 at 17:21
  • \$\begingroup\$ For some reason, my system tells me the new file is 55 bytes long, which is obviously wrong because it's only 54 characters, so ??? \$\endgroup\$ Oct 24, 2016 at 17:55
  • \$\begingroup\$ Hmm that's strange. (and I have no idea where this comes from). But I'm pretty sure it's only 54 (the PPCG-Design script tells me 54, and my bytecount app tells me 54 aswell). \$\endgroup\$
    – Dada
    Oct 24, 2016 at 17:58
  • 2
    \$\begingroup\$ Is it possible the byte count was out due to the file having an unnecessary newline at the end? \$\endgroup\$ Oct 25, 2016 at 1:12
2
\$\begingroup\$

Brainfuck, 60 bytes

,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

The permutation is given as bytes with no separators and no terminating newline. Since \x00 occurs in the input, this is designed for implementations with EOF = -1. The output is \x00 for false and \x01 for true.

If a permutation of \x01 up to chr(r) is allowed, then we can replace all instances of ,+ with , for a score of 57 with an EOF = 0 implementation.

Try it online (57-byte version): Input can be given as a permutation of any contiguous range of bytes excluding \x00, and the output will be \x00 for false and the minimum of the range for true.

We keep track of the min and max seen so far, and for each character after the first, check whether it is min-1 or max+1 or neither. In the case of neither, move the pointer outside the normal working space so that the local cells become zero.

The memory layout of the normal working space at the beginning of the main loop is

c a b 0 0

where c is the current character, a is min, and b is max. (For the 60-byte version, everything is handled with an offset of 1 because of ,+.)

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 8 bytes

⇧2lvƒ<ÞṠ

Try it Online!

Like Lynn's Jelly answer, takes my Vyxal answer to Is it a tower permutation?, adds a grade up at the beginning, and changes > to <.

How?

⇧2lvƒ<ÞṠ
⇧        # Grade up (i.e. sort indices by corresponding values)
 2l      # Get overlapping pairs
   vƒ<   # For each pair, check if the first item is less than the second
      ÞṠ # Is it sorted in ascending order?
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 22 bytes

:@[fb:{oLtT,Lh:T:efL}a

Try it online!

Explanation

I haven't found a concise way of checking whether a list contains consecutive integers or not. The shortest I found is to generate a range between the first and last element of that list and check that that range is the original list.

:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L
\$\endgroup\$
2
  • \$\begingroup\$ Range from first to last is one approach which had occurred to me in CJam. The other was sort, pairwise differences, check they're all 1. I don't know how easy that is in Brachylog. \$\endgroup\$ Oct 24, 2016 at 8:04
  • \$\begingroup\$ @PeterTaylor There is no short way of generating consecutive pairs (or directly compute pairwise differences) unfortunately (for now). \$\endgroup\$
    – Fatalize
    Oct 24, 2016 at 8:09
1
\$\begingroup\$

Batch, 133 bytes

@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

Takes input as command-line arguments. Exits with error level 0 for success, 1 for failure.

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

Java, 170 bytes

boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Array x has values from 0 to maximum number in order (Python would be much better here...). The loop goes backwards trying to match the lowest (x[b]) or the highest (x[e]) number not yet encountered; if it does, that number could be reached in that step.

Test code here.

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

05AB1E, 7 bytes

ηε{¥P}P

Try it online!

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

R, 57 bytes

function(x,y=x[-1],`!`=cummin){y[]=y+1-!x&y-1+!-x;any(y)}

Try it online!

Completely different and somewhat shorter approach to JDL's previous R answer.

Returns FALSE for antsy sequences, TRUE for not-antsy sequences.
Add two bytes to reverse the output to truthy for antsy sequences: 59 bytes, but save 4 bytes by taking input using scan: 55 bytes

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 47 bytes

A little longer than Martin Ender's solution (surprise surprise!). But it's one of my more unreadable efforts, so that's good :D

#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Explanation:

#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list
\$\endgroup\$
0
\$\begingroup\$

Java 7, 170 169 bytes

import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Ungolfed & test code:

Try it here.

import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19 }));
    System.out.println(c(new int[]{ 34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19 }));
    System.out.println(c(new int[]{ 47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }));
  }
}

Output:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true
\$\endgroup\$
0
\$\begingroup\$

[JavaScript], 54 bytes

e=>e.every((f,m)=>!m||e.some((e,o)=>o<m&&(e-f)**2==1))

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! :) \$\endgroup\$
    – naffetS
    Apr 23, 2022 at 15:57
  • \$\begingroup\$ You can get down to 58 bytes if you remove the ,s=e-f and then instead of s*s, do (e-f)**2. \$\endgroup\$
    – naffetS
    Apr 23, 2022 at 16:00
  • \$\begingroup\$ also, you don't have to include the f= in the byte count, which means you can get down to 56 bytes. :) \$\endgroup\$
    – naffetS
    Apr 23, 2022 at 16:08
  • \$\begingroup\$ Oh wow, awesome! thanks for these suggestions! It was my first, but definitely not my last code golf :) \$\endgroup\$ Apr 23, 2022 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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