33
\$\begingroup\$

N children, with no two sharing their exact size, are lined up in some order. Each can only compare heights with their immediate neighbours. When the teacher shouts "raise hands if you are the tallest", they do so if they are taller than both their neighbours, and they do so simultaneously. If only one raises their hand, he wins. If more than one raise their hands, they are all eliminated from the row (preserving the order of the rest of the children) and they repeat the process.

Write a program, which takes an array of distinct integers (you can assume they are strictly positive) and outputs the winner of this game. This is code-golf, so the shortest code wins.

Examples (with intermediate stages shown):

5 3 9 8 7 → 3 8 7 → 8

1 2 9 4 → 9

9 3 8 7 4 12 5 → 3 7 4 5 → 3 4 → 4


Current leaders:

  1. Jelly: 17 bytes [by Dennis♦]
  2. MATL: 20 bytes [by Luis Mendo]
  3. APL: 28 bytes [voidhawk]
  4. k: 40 bytes [by Paul Kerrigan]

There's also a battle of Pythons going on. Still waiting for more golfing languages to show up.

I currently accepted Dennis♦'s answer - if there are new winners, I'll update the selection.

\$\endgroup\$
  • 2
    \$\begingroup\$ sounds more like "who might be the tallest, or might not?" - to actually find "who is the tallest" you'd have to eliminate the ones that keep their hands down \$\endgroup\$ – Alnitak Dec 1 '16 at 17:42
  • 4
    \$\begingroup\$ I drew similarity to kids' games, where one person shouts some signature phrase after which the game is named. Funnily enough, the tallest is least likely to win (by a huge margin). Asymptotically, out of N! permutations, only in 2^(N-1) cases he wins. \$\endgroup\$ – orion Dec 1 '16 at 21:03

16 Answers 16

4
\$\begingroup\$

Jelly, 17 bytes

j@N»3\=x@ḟ@ḢṖ?µ¬¿

Input is a comma-separated string of integers.

Try it online!

Credits go to @Xanderhall, @Sherlock, and @ErikGolfer for laying the groundwork.

How it works

j@N»3\=x@ḟ@ḢṖ?µ¬¿ Main link: Argument: A (integer or list of integers)

               ¬¿ While the logical NOT of A (0 for a positive integer, a non-empty
                  array for a non-empty array) is truthy:
              µ     Execute the chain of links to the left.
  N                   Negative; multiply all integers in A by -1.
j@                    Join -A, separating by A. This prepends and appends a
                      negative to A and appends more integers that will be ignored.
   »3\                Compute the maxima of all overlapping slices of length 3.
      =               Compare the maxima with the elements of A, yielding 1 or 0.
       x@             Repeat the elements of A, 1 or 0 times.
                      This ignores Booleans without a counterpart in A.
            Ṗ?        If the popped result is truthy, i.e., if it has at least two
                      elements:
         ḟ@             Filter/remove those elements from A.
                      Else:
           Ḣ            Head; extract the (only) element of the return value.
\$\endgroup\$
10
\$\begingroup\$

JavaScript (ES6), 78 76 72 bytes

Thanks to @edc65 for -4 bytes

f=a=>a.map((c,i)=>(p>c|c<a[i+1]?q:r).push(p=c),p=q=[],r=[])&&r[1]?f(q):r

Takes in an array of integers and outputs an array containing only the winner.

Test snippet

f=a=>a.map((c,i)=>(p>c|c<a[i+1]?q:r).push(p=c),p=q=[],r=[])&&r[1]?f(q):r

g=a=>a?console.log("Input:",`[${a}]`,"Output:",f(a.map(Number))+""):console.error("Invalid input")

g([5,3,9,8,7])
g([1,2,9,4])
g([9,3,8,7,4,12,5])
<input id=I value="9 1 8 2 7 3 6 4 5"><button onclick="g(I.value.match(/\d+/g))">Run</button>

Here are a few other attempts, using .filter and array comprhensions:

f=a=>(q=a.filter((c,i)=>p>(p=c)|c<a[i+1]||0*r.push(c),p=r=[]))&&r[1]?f(q):r
f=a=>(r=a.filter((c,i)=>p<(p=c)&c>~~a[i+1]||0*r.push(c),p=q=[]))[1]?f(q):r
f=a=>[for(c of(i=p=q=[],r=[],a))(p>c|c<a[++i]?q:r).push(p=c)]&&r[1]?f(q):r
f=a=>(q=[for(c of(i=p=r=[],a))if(p>(p=c)|c<a[++i]||0*r.push(c))c])&&r[1]?f(q):r

Or a double for-loop, horribly long:

a=>eval("for(r=[,1];r[1]&&(p=i=q=[],r=[]);a=q)for(c of a)(p>c|c<a[++i]?q:r).push(p=c));r")

Explanation

The way this works is pretty simple: it builds an array of those who are relatively taller (r) and an array of those that aren't (q), then returns r if it only has one item; if not, it runs itself on q and returns the result of that.

\$\endgroup\$
  • \$\begingroup\$ Where's the snack snippet? \$\endgroup\$ – Cows quack Nov 30 '16 at 20:06
  • \$\begingroup\$ @KritixiLithos Added :-) \$\endgroup\$ – ETHproductions Nov 30 '16 at 20:12
  • \$\begingroup\$ "[1,2,5,8,9,12,3,4,10] Output: 5" I think this should output 8, not 5. First, 12 and 10 are eliminated, then 9 and 4, then 8 wins. \$\endgroup\$ – orion Nov 30 '16 at 20:15
  • 1
    \$\begingroup\$ @orion My bad, the snippet wasn't converting its arguments to numbers before sending them into the function. This has been fixed. \$\endgroup\$ – ETHproductions Nov 30 '16 at 20:20
  • \$\begingroup\$ You can save 4 bytes on your filter example by switching q and r. You avoid the &&r and the filter expression turns out to be a byte shorter too. \$\endgroup\$ – Neil Nov 30 '16 at 21:25
8
\$\begingroup\$

MATL, 20 bytes

`tTYadZSd0<~&)nq}x2M

Input is a column vector, using ; as separator.

Try it online! Or verify all test cases.

Explanation

This is a direct implementation of the procedure described in the challenge. A do...while loop keeps removing elements until only one has been removed; and that one is the output.

The elements to be removed are detected by taking differences, signum, then differences again. Those that give a negative value are the ones to be removed.

`        % Do...while
  t      %   Duplicate. Takes input (implicit) the first time
  TYa    %   Append and prepend a zero
  d      %   Consecutive differences
  ZS     %   Signum
  d      %   Consecutive differences
  0<~    %   Logical mask of non-negative values: these should be kept
  &)     %   Split array into two: those that should kept, then those removed
  nq     %   Size minus 1. This is used as loop condition. The loop will exit
         %   if this is 0, that is, if only one element was removed
}        % Finally (i.e. execute at the end of the loop)
  x      %   Delete array of remaining elements
  2M     %   Push last element that was removed
         % End (implicit)
         % Display (implicit)
\$\endgroup\$
4
\$\begingroup\$

Python3, 265 260 248 243 203 121 117 112 111 bytes

def T(I):
 b=[0];q=[];J=b+I+b
 for i,x in enumerate(I):[q,b][J[i]<x>J[i+2]]+=x,
 return len(b)<3and b[1]or T(q)

Thank you @ZacharyT, @orion, and @mathmandan for saving 5 45 a lot of bytes!

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

Haskell, 85 bytes

import Data.List
f x=(#)=<<(x\\)$[b|a:b:c:_<-tails$0:x++[0],b<a||b<c]
[s]#_=s
_#i=f i

Usage example: f [9,3,8,7,4,12,5] -> 4.

How it works:

f x =                            -- main function with parameter x
         [b|                  ]  -- make a list of all b
            a:b:c:_              -- where b is the second element of all lists with
                                 -- at least 3 elements
             <- tails $ 0:x++[0] -- drawn from the tails of x with a 0 pre- and
                                 -- appended (tails [1,2,3] -> [1,2,3],[2,3],[3],[])
               ,b<a||b<c         -- and b is not greater than its neighbors
   (#)=<<(x\\)                   -- feed the list difference of x and that list
                                 -- and the list itself to the function #

[s]#_s                           -- if the list difference is a singleton list,
                                 -- return the element
_#i=f i                          -- else start over with the list of b's

A variant, also 85 bytes:

import Data.List
f x|n<-[b|a:b:c:_<-tails$0:x++[0],b<a||b<c]=last$f n:[s|[s]<-[x\\n]]

Bind the list of b (see above) to n and return the element s if x\\n is a singleton list and f n otherwise.

\$\endgroup\$
  • \$\begingroup\$ You can get rid of the import and save 3 bytes with f x|y@(_:z)<-x++[0]=(#)=<<(x\\)$[b|(a,b,c)<-zip3(0:y)y z,b<a||b<c]. \$\endgroup\$ – Zgarb Dec 1 '16 at 14:03
  • \$\begingroup\$ @Zgarb: \\ still needs the import. Btw, tails can also be replaced by ...|a:b:c:_<-scanr(:)[]$0:x++[0],.... \$\endgroup\$ – nimi Dec 1 '16 at 16:52
  • \$\begingroup\$ Ohh right, I didn't realize that. \$\endgroup\$ – Zgarb Dec 1 '16 at 17:00
2
\$\begingroup\$

Mathematica, 107 108 bytes

(For[x=y=#,Length@y>1,x=DeleteCases[x,#|##&@@y],y=Intersection[Max@@@x~Split~Less,#&@@@Split[x,#>#2&]]];y)&

Explanation

First, set x and y equal to the input List. The loop continues until Length@y==1. x~Split~Less is the list of lists of consecutive, increasing elements, Split[x,#>#2&] is the list of lists of consecutive, decreasing elements. Taking the Max of all of the lists in the former gives the list of children taller than the child to their right (along with the right-most child). Taking the first argument (#&) of all of the lists in the latter gives the list of children taller than the child to their left (along with the left-most child). The intersection of these two will be the list of children who raised their hand. Set this equal to y. x=DeleteCases[x,#|##&@@y] removes from x any elements matching an element of y (#|##& is equivalent to Alternatives). Once the loop terminates, return y. If the output must be an integer (rather than a list containing a single integer), return #&@@y (+4 bytes).

Thanks to Martin Ender for saving 2 bytes and making me comply with the rules. Open to suggestions.

\$\endgroup\$
  • \$\begingroup\$ I don't think !Less works as you expect, since this doesn't actually evaluate to a function. You'll probably need to use Greater (or #>#2&) there. You can use x~Split~Less for the first Split though and > for the Length condition. \$\endgroup\$ – Martin Ender Dec 1 '16 at 14:58
  • 1
    \$\begingroup\$ As for having to evaluate Clear@y between function calls, I'm afraid that's not valid. You'll either have to reset it yourself, scope it better, or turn this into a full program with Input and Print. \$\endgroup\$ – Martin Ender Dec 1 '16 at 14:59
1
\$\begingroup\$

Perl 6, 111 bytes

{(@_,{(($/=(0,|@$_,0).rotor(3=>-2).classify({+so .[1]>.[0,2].all})){1}>1??$/{0}!!$/{1})».[1]}...*==1)[*-1][0]}

Expanded:

{  # bare block lambda with implicit parameter list 「@_」

  (                                    # generate a sequence
    @_,                                # starting with the input

    {   # code block used to get the next value in the sequence
        # which has implicit parameter 「$_」

        (
          (


            $/ =   # store in 「$/」 for later use

            ( 0, |@$_, 0 )             # the input with 0s before and after
            .rotor( 3 => -2 )          # take 3 at a time, back up 2, repeat
            .classify({
              +                        # Numify the following:
              so                       # simplify the following Junction
              .[1] > .[ 0, 2 ].all     # is the middle larger than its neighbors
            })



          ){1}                         # look at the values where it is true
          > 1                          # is there more than 1?

        ??                             # if so
          $/{ 0 }                      # look at the false ones instead

        !!                             # otherwise
          $/{ 1 }                      # look at the true ones

      )».[1]                           # undo the transformation from 「.rotor」
    }

    ...                                # keep doing that until

    * == 1                             # there is only one value
  )\
  [ * - 1 ]                            # the last value of the sequence
  [ 0 ]                                # make it a singular value ( not a list )

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

Python 2, 100 98 bytes

def f(A):
 t=[0];l=[];a=b=0
 for c in A+[0]:[l,t][a<b>c]+=[b];a,b=b,c
 return t[-2]and f(l)or t[1]

Uses the short-circuiting return as in Yodle's answer (by Zachary T)

\$\endgroup\$
  • \$\begingroup\$ You can take 3 more bytes off by: using +=b, instead of +=[b] (credit to mathmandan), using t=[0] to use t to add to A, and then, since we now start with 0 in t, checking t[-2]<1 is shorter than len(t)<2, and use t[1] as the result in that case. \$\endgroup\$ – orion Dec 1 '16 at 18:06
  • \$\begingroup\$ The last line becoming return t[-2]and f(l)or t[1]. \$\endgroup\$ – orion Dec 1 '16 at 23:22
0
\$\begingroup\$

Mathematica, 101 bytes

If[Equal@@(a=Position[Max/@Partition[#,3,1,{2,2},0]-#,0]),#[[Last@a]],#0@Fold[Drop@##&,#,Reverse@a]]&

Unnamed recursive function taking a list of numbers as input, and returning a list with a single number (the winner) as output.

The core of the algorithm is Max/@Partition[#,3,1,{2,2},0], which computes the array of (the-max-of-me-and-my-neighbors)s from the input list. a=Position[...-#,0] then subtracts the original list and returns where the 0s are; these are the hand-raising children.

If[Equal@@a, #[[Last@a]], #0@Fold[Drop@##&,#,Reverse@a]]& branches depending on whether all the elements of a are equal or not (in this case, they will be only if a is a singleton); if so, then this child is the winner and we output her number; if not, then we recursively call this function on the list with all elements at positions in a removed.

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

Python 2, 99 Bytes

def f(l):k=[x[0]for x in zip(l,[0]+l,l[1:]+[0])if(max(x),)>x];return(len(k)+2>len(l))*max(l)or f(k)
\$\endgroup\$
0
\$\begingroup\$

PHP, 131 bytes

$r=$a=$argv;for(;$r[1];$a=array_values(array_diff($a,$r))){$r=[];foreach($a as$i=>$x)if($x>$a[$i-1]&$x>$a[$i+1])$r[]=$x;}echo$r[0];

Takes numbers from command line arguments. Fails if filename starts with a positive number.

breakdown

// import (and init $r[1])
$r=$a=$argv;
// while more than 1 raised hand, remove them from data
for(;$r[1];$a=array_values(array_diff($a,$r)))
{
    // reset hands
    $r=[];
    // raise hands
    foreach($a as$i=>$x)
        if($x>$a[$i-1]&$x>$a[$i+1])$r[]=$x;
}
// output
echo$r[0];
\$\endgroup\$
0
\$\begingroup\$

k, 40 bytes

{$[1=+/B:(|>':|x)&>':x;x@&B;.z.s x@&~B]}

Explanation:
$ is an if-else.

The condition is whether 1 is the sum of B, which is defined as the minimum of two lists generated by checking if x is greater than the prior and post-positions (Pipe is reverse).

If this is true we return x where B is true.
Otherwise we recurse without the true positions.

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

Scala 129 bytes

Golfed

def x(a:List[Int]):Int={val (y,n)=(0+:a:+0).sliding(3).toList.partition(l=>l.max==l(1));if(y.length>1)x(n.map(_(1)))else y(0)(1)}

Ungolfed

def whoIsTallest(a: List[Int]): Int = {
  val (handUp, handDown) = (0 +: a :+ 0).sliding(3).toList.partition {
    case x :: y :: z :: Nil => y > x && y > z
  }
  if (handUp.length > 1)
    whoIsTallest(handDown.map(_(1)))
  else
    handUp.head(1)
}

By padding the list left and right with 0's, can then group in sets of 3 and partition the list for those where the hand is up, the left and right most elements compare to 0 on the outside so get the correct number (assuming nobodys height is negative!)

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

C++14, 182 bytes

#define P .push_back(c[i]);
int f(auto c){decltype(c)t,s;int i=0;(c[0]>c[1]?t:s)P for(;++i<c.size()-1;)(c[i-1]<c[i]&&c[i]>c[i+1]?t:s)P(c[i-1]<c[i]?t:s)P return t.size()<2?t[0]:f(s);}

Learned that the ternary operator can be used with C++ objects. Requires the input to be a random access container with push_back, like vector, deque and list.

Creates two containers t and s of the same type and appends the local tallest to t and the rest to s. If there is only 1 element in t return that one, otherwise recursive call itself with s.

Ungolfed:

int f(auto c){
  decltype(c)t,s;
  int i=0;
  (c[0]>c[1] ? t : s).push_back(c[i]);
  for(;++i<c.size()-1;)
    (c[i-1]<c[i]&&c[i]>c[i+1] ? t : s).push_back(c[i]);
  (c[i-1]<c[i] ? t : s).push_back(c[i]);
  return t.size()<2 ? t[0] : f(s);
}
\$\endgroup\$
0
\$\begingroup\$

R, 83 bytes

Two different versions:

This one takes a vector N:

while(T){Z=diff(sign(diff(c(0,N,0))))<0;if(sum(Z)>1)N=N[!Z]else{print(N[Z]);break}}

This one creates a function F defined recursively:

F=function(N){Z=diff(sign(diff(c(0,N,0))))<0;if(sum(Z)>1)F(N[!Z])else return(N[Z])}
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 28 bytesSBCS

{1=≢⍸s←⍵=3⌈/∊0⍵0:s/⍵⋄∇⍵/⍨~s}

Try it online!

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