37
\$\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\$
  • 7
    \$\begingroup\$ This is a very interesting challenge with many different solutions: I count at least 7 unique strategies being used so far. \$\endgroup\$ – ETHproductions Oct 24 '16 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 '16 at 21:51
  • 1
    \$\begingroup\$ I'm disappointed there isn't an ANTSI C solution yet. \$\endgroup\$ – NoSeatbelts Oct 26 '16 at 6:15

23 Answers 23

18
\$\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\$
  • 7
    \$\begingroup\$ You can cut it down to 6 bytes by using... just kidding. \$\endgroup\$ – jwg Oct 24 '16 at 15:24
  • 2
    \$\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\$ – David Conrad Oct 24 '16 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 '16 at 21:29
  • \$\begingroup\$ ayyyyy, turning to the pyth side :D \$\endgroup\$ – Maltysen Oct 25 '16 at 0:42
11
\$\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\$
  • \$\begingroup\$ That's so clever! +1 \$\endgroup\$ – Gabriel Benamy Oct 24 '16 at 15:47
  • 1
    \$\begingroup\$ Could you save some bytes by defining (#)=scanl1? \$\endgroup\$ – Zgarb Oct 24 '16 at 17:36
  • 1
    \$\begingroup\$ @Zgarb Thanks, I forgot you could do that. \$\endgroup\$ – xnor Oct 24 '16 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\$
  • \$\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\$ – ETHproductions Oct 24 '16 at 15:58
  • \$\begingroup\$ How does this work? Are you using some mutable list magic? \$\endgroup\$ – Zgarb Oct 24 '16 at 16:59
  • \$\begingroup\$ @Zgarb explanation added \$\endgroup\$ – edc65 Oct 24 '16 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\$
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\$
  • 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 '16 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\$
  • 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 '16 at 11:08
  • \$\begingroup\$ Nice idea, and I can go one better I think by abusing T. Will edit. \$\endgroup\$ – JDL Oct 24 '16 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\$
  • \$\begingroup\$ I would check for push pop reductions I see some already a few places where you could use this strategy. \$\endgroup\$ – Sriotchilism O'Zaic Oct 24 '16 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 '16 at 15:44
  • \$\begingroup\$ I'm glad this at least makes sense to you O_O \$\endgroup\$ – Gabriel Benamy Oct 24 '16 at 16:26
  • \$\begingroup\$ You can also replace instances of ([]){({}[()]<({}<>)<>>)}{} with ([]){{}({}<>)<>([])}{} to save a couple more bytes \$\endgroup\$ – Sriotchilism O'Zaic Oct 24 '16 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\$
  • \$\begingroup\$ The conversion of xnor's other method to Jelly is also 7 bytes »\_«\⁼Ṣ but much more efficient \$\endgroup\$ – miles Oct 24 '16 at 11:59
  • \$\begingroup\$ ŒBŒPċṢ and ;\Ṣ€IỊȦ should save one byte in each approach. \$\endgroup\$ – Dennis Oct 24 '16 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 '16 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 '16 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 '16 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\$
  • \$\begingroup\$ I think this saves one? {_{a+_)f-:z1&,*}*^!} \$\endgroup\$ – Martin Ender Oct 24 '16 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\$ – Peter Taylor Oct 24 '16 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\$
  • \$\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\$ – Peter Taylor Oct 25 '16 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\$ – David Conrad Oct 25 '16 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\$ – Peter Taylor Oct 25 '16 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\$ – David Conrad Oct 25 '16 at 8:19
  • \$\begingroup\$ Got it. n-=i==m+1?m-m++:i==n-1?1:n+1; \$\endgroup\$ – Peter Taylor Oct 25 '16 at 8:26
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\$
  • 3
    \$\begingroup\$ Seeing this convinces me to merge this into Pyth. \$\endgroup\$ – isaacg Oct 24 '16 at 8:11
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\$
  • 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 '16 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\$ – Gabriel Benamy Oct 24 '16 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 '16 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\$ – trichoplax Oct 25 '16 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\$
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\$
  • \$\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\$ – Peter Taylor Oct 24 '16 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 '16 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\$

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\$
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\$
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\$

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.