25
\$\begingroup\$

Problem 4 in the 2019 BMO, Round 1 describes the following setup:

There are \$2019\$ penguins waddling towards their favourite restaurant. As the penguins arrive, they are handed tickets numbered in ascending order from \$1\$ to \$2019\$, and told to join the queue. The first penguin starts the queue. For each \$n > 1\$ the penguin holding ticket number \$n\$ finds the greatest \$m < n\$ which divides \$n\$ and enters the queue directly behind the penguin holding ticket number \$m\$. This continues until all \$2019\$ penguins are in the queue.

The second part of the question asked candidates to determine the penguins standing directly in front of, and directly behind, penguin \$33\$. This could be done by examining the patterns in the queue, considering prime factors: see the online video solutions for more information.


The Challenge

Your task is to design a program or function which, given a positive integer \$k\$ representing the penguin with ticket number \$k\$, outputs the ticket numbers of the penguins directly before and after this penguin.

For example, penguin \$33\$, stands directly behind \$1760\$ and directly in front of \$99\$, so the program should output, in some reasonable format, \$[1760, 99]\$.


Rules

  • The input will be an integer in the range \$1 < k \le 2019\$.
  • Your program should output two integers, in any reasonable format, representing the ticket numbers of the penguins before and after.
  • These can be output in any order, (front first or behind first) but this order must be consistent.
  • The penguin will not be at the front or back of the queue: so you don't have to handle the edge cases of \$k = 1\$ or \$k = 1024\$.
  • As penguins find it difficult to read human glyphs, your program should be as short as possible. This is a - so the shortest program (in bytes) wins!

Test Cases

These outputs are given in the format [front, behind].

33   -> [1760, 99]
512  -> [256, 1024]
7    -> [1408, 49]
56   -> [28, 112]
1387 -> [1679, 1241]
2019 -> [673, 1346]
2017 -> [1, 2011]
2    -> [1536, 4]
\$\endgroup\$
  • 2
    \$\begingroup\$ @game0ver It doesn't, it joined the queue behind n = 11, but then subsequent penguins whose numbers are multiples of 11 but not 33 pushed in front of it. \$\endgroup\$ – Neil Dec 8 '19 at 22:17
  • \$\begingroup\$ Ah, thanks, my mistake, I though that \$m\$ was supposed to be 1760. \$\endgroup\$ – game0ver Dec 8 '19 at 22:19

13 Answers 13

6
\$\begingroup\$

Perl 6, 79 76 71 bytes

{($!=sort {[R,] -$_,{first $_%%*,$_^..1}...1},^2020)[+(@$!...$_)X-2,0]}

Try it online!

Sorts numbers 1 to 2019 lexicographically by the reversed, negated sequence of largest divisors, then finds the neighbors. Example mappings:

1760 => (-1 -11 -55 -110 -220 -440 -880 -1760)
  33 => (-1 -11 -33)
  99 => (-1 -11 -33 -99)

In other words, the negated cumulative product of prime factors in descending order.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 15 bytes

⁽¥ØÆfṚNƊÞṣị"@Ø.

A monadic Link accepting an integer between 1 and 2019 * which yields a list of two integers, [in-front, behind].

* If 1 or 1024 is input the missing ticket number will be shown as 0.

Try it online!

How?

⁽¥ØÆfṚNƊÞṣị"@Ø. - Link: n
⁽¥Ø             - literal 2019
        Þ       - sort (range [1..2019]) by: 
       Ɗ        -   last three links as a monad:
   Æf           -     prime factorisation (e.g. 1100 -> [2,2,5,5,11])
     Ṛ          -     reversed
      N         -     negated
         ṣ      - split at (n)
             Ø. - literal [0,1]
            @   - with swapped arguments:
           "    -   zip with:
          ị     -     index into (1-based & modular)
                      - i.e. [last of left list, first of right list]
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 16 15 bytes

Ž7ëLΣÒR(}ûI¡€θ¨

Port of @JonathanAllan's Jelly answer, so make sure to upvote him!
-1 byte thanks to @Grimmy.

Outputs in the order [front, behind].

Try it online or verify all test cases.

Explanation:

Ž7ë              # Push compressed integer 2019
   L             # Pop and push a list in the range [1,2019]
    Σ            # Sort this list by:
     Ò           #  Get the prime factors (with duplicates)
      R          #  Reverse it
       (         #  Negate each inner value
        }û       # After the sort: palindromize this list ([a,b,c] → [a,b,c,b,a])
          I¡     # Split this pallindromized list by the input-integer
            €θ   # For each inner list: only leave the last value
              ¨  # And remove the last value, so the pair remains
                 # (after which this pair is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž7ë is 2019.

\$\endgroup\$
  • 1
    \$\begingroup\$ -1 using ûI¡€θ¨ (ûDIQÀÏ also works, for the same byte-count). \$\endgroup\$ – Grimmy Dec 9 '19 at 17:38
  • 1
    \$\begingroup\$ There's also ûʒQYsV, for a slightly weirder 15. \$\endgroup\$ – Grimmy Dec 9 '19 at 17:48
  • \$\begingroup\$ @Grimmy Thanks! Nice use of the palindromize builtin! And that third one is indeed weird. Took me a few looks to understand what was going on. But again pretty smart. :) \$\endgroup\$ – Kevin Cruijssen Dec 9 '19 at 18:11
3
\$\begingroup\$

Python 2, 137 133 121 bytes

q=[1]
for n in range(2,2020):j=q.index(max(m for m in q if n%m<1))+1;q=q[:j]+[n]+q[j:]
print q[q.index(input())-1::2][:2]

Try it online!

4 bytes thx to Arnauld; 11 bytes thx to FlipTack.

Another naive implementation.

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

JavaScript (ES6),  105 ... 101  100 bytes

A straightforward implementation that builds the full queue and looks for the penguin with the input ticket within it.

Returns [front, behind].

k=>[eval("for(n=q=[];m=++n%2020;q.splice(q.indexOf(m),0,n))while(n%--m)q")[i=q.indexOf(k)+1],q[i-2]]

Try it online!

Commented

The code in eval() builds and returns the queue in reverse order:

for(                      // outer loop:
  n = q = [];             //   q[] = queue, n = counter (initially zero'ish)
  m = ++n % 2020;         //   increment n; set m to n mod 2020, so that we
                          //   stop when n = 2020
  q.splice(               //   after each iteration:
    q.indexOf(m), 0, n    //     insert n before m in q[] (should be *after* m to build
  )                       //     the queue from first to last, but it's shorter this way)
) while(n % --m)          //   inner loop: decrement m until it divides n
    q                     //     dummy loop statement so that q[] is returned by eval()

which gives \$q[\:]=[1024,512,...,2017,1]\$.

Wrapper code:

k => [                    // k = input
  eval("...")             // build q[]
  [i = q.indexOf(k) + 1], // return the element after k ('in front of')
  q[i - 2]                // and the element before k ('behind')
]                         //
\$\endgroup\$
  • 3
    \$\begingroup\$ "straighforward" - Arnauld, 2019 :D I find this evil ^^ \$\endgroup\$ – Kaddath Dec 9 '19 at 10:26
  • \$\begingroup\$ @Kaddath Did you mean I find this eval? :p \$\endgroup\$ – Arnauld Dec 11 '19 at 11:06
  • \$\begingroup\$ Yeah but not only, the way loops are used to build and return q are really clever! \$\endgroup\$ – Kaddath Dec 11 '19 at 12:00
2
\$\begingroup\$

C++ (clang), 288 ... 211 210 bytes

#import<queue>
#import<regex>
#define l find(begin(q),end(q)
using v=std::vector<int>;v f(int p){v q{1};for(int n=1,d,i;d=i=++n<2020;q.insert(l,d),n))for(;++i<n&d<2;)d=n%i?d:n/i;auto t=l,p);return{*++t,t[-2]};}

Try it online!

Saved 22 bytes thanks to @ceilingcat!!!!
Saved 1 byte thanks to @AZTECCO!!!!

Ungolfed:

#include <vector>
#include <algorithm>

auto f(int p)
{
    std::vector<int> q{1};
    for (int n = 2; n <= 2019; ++n)
    {
        int d = 1;
        for (int i = 2; i < n; ++i)
        {
            if (n % i == 0)
            {
                d = n / i;
                break;
            }
        }
        auto it = find(begin(q), end(q), d);
        q.insert(it, n);
    }
    auto it = find(begin(q), end(q), p);
    std::vector<int> r = {*(it + 1), *(it - 1)};
    return r;
}
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thanks!! Well spotted comma for space save!! :-) \$\endgroup\$ – Noodle9 Dec 16 '19 at 21:01
1
\$\begingroup\$

Perl 5, 88 bytes

sub f{$_=1;for$n(2..2019){map{$n%$_ or$m=$_}1..$n/2;s/\b$m\b/$&,$n/}/(\d+),$_[0],(\d+)/}

Try it online!

Same ungolfed:

sub f {
  $_=1;                             # $_ is the comma separated queue "array string"
                                    # ...with 1 as the first penguin
  for $n (2..2019){                 # process the rest of the penguins 2-2019
    map { $n%$_ or $m=$_ } 1..$n/2; # find max $m divisible by current $n
    s/\b$m\b/$&,$n/                 # search-replace to place current $n behind $m
  }
  /(\d+),$_[0],(\d+)/               # find and return the two numbers:
                                    # the one before and the one after the input
                                    # parameter $_[0] in the $_ array string
}
\$\endgroup\$
1
\$\begingroup\$

R, 90 89 bytes

for(i in 2:2019)T=append(T,i,match(max(which(!i%%1:(i-1))),T));T[match(scan(),T)+c(-1,1)]

Try it online!

Builds up the list into T and extracts the relevant values.

As a bonus, it works for 1 and almost works for 1024, as R's 1-based indexing returns nothing for index 0 and NA for index 2020.

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

Jelly, 23 21 bytes

ḍƇṀ=⁸k⁸j
⁽¥ØRç/ṣ⁸ṪḢƭ€

Try it online!

Naïve answer that simply generates the list of penguins and finds the relevant place. A pair of links which, when called as a monad, takes an integer as its argument and returns a pair of integers indicating the penguins before and after in the list of penguins.

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

Ruby, 104 101 95 bytes

->n{*w=1;(2..2019).map{|z|w.insert(1+w.index(w.select{|x|z%x<1}.max),z)};w[w.index(n)-1,3]-[n]}

Try it online!

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

Japt, 36 bytes

1k
#É9ò2@iUaXâ n- gJÑ)ÄX
g[J1]c+UaNg

Try it

1k               assign [1] to U

#É9ò2            pass range 2...2019 to function:
     @i ...  X   insert each value in U at index:
 Ua               find max divisor of X in U:
   Xâ              divisors
      n-           sorted
         gJÑ)Ä     2nd to last

g                get elements at
 [J1]             [-1,1]
     c+UaNg       add index of 1st input in U
\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 109 bytes

^
2019$*_
_
$`_¶
(_+)\1+¶
$1 $&
+m`^(_+)¶((_+¶)*)\1 (_+¶)
$1¶$4$2
_+
$.&
^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Try it online! Note: Link only goes to 201 as 2019 is too slow for TIO. Explanation:

^
2019$*_

Prepend 2019 in unary.

_
$`_¶

Count from 1 to 2019.

(_+)\1+¶
$1 $&

Precede each number with its highest proper factor (except 1, which remains unchanged).

+m`^(_+)¶((_+¶)*)\1 (_+¶)
$1¶$4$2

Insert in turn each number after its highest proper factor.

_+
$.&

Convert to decimal.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Extract the predecessor and successor of the original input.

118 byte version that's fast enough to handle 2019 on TIO:

^
2019$*_
_
$`_¶
(_+)\1+\b
$.1;$.&
_
1
m{`^(\d+)¶\1;
$1¶
}`^(\d+¶)(\d+;\d+¶)
$2$1
^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Try it online! Explanation:

^
2019$*_
_
$`_¶

Prepend all of the unary numbers from 1 to 2019.

(_+)\1+\b
$.1;$.&

Convert to decimal and prepend the largest factor.

_
1

Except 1, which just becomes the first entry in the list.

m{`^(\d+)¶\1;
$1¶
}`^(\d+¶)(\d+;\d+¶)
$2$1

Bubble up each line until it finds its insertion point.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Extract the predecessor and successor of the original input.

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

Scala, 163 bytes

n=>{val a=(2 to 2019).map(x=>(x,((1 to x/2).filter(x%_==0)).max)).foldLeft(Seq(1))((l,e)=>l.patch(l.indexOf(e._2)+1,Seq(e._1),0));val i=a indexOf n;(a(i-1),a(i+1))

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.