23
\$\begingroup\$

Background

When searches return many pages of results, GitHub avoids cluttering their UI by eliding page links. Instead, their UI let's you select:

  1. Pages at the beginning of the results.
  2. Pages near the current page.
  3. Pages at the end of the results.

In this way, no more than 11 page links are ever displayed at one time. Before describing the precise logic underlying the pager, a few screenshots will help demonstrate it:

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

The logic

Assuming a total of n results, and a current page of p, the pager will always show:

  1. The current page.
  2. The 4 pages closest in absolute distance to the current page.
    • That is, it will show a "window" of length 5, centered on the current page, but shifting as needed if the current page is too close to one of the boundaries (the first or last page).
  3. The first 2 pages.
  4. The last 2 pages.
  5. All other contiguous pages besides these will be elided with a single ..., with one exception:
    • If only 1 page would be elided, simply show that page rather than the ..., because it's going to take up the same amount of space anyway.

As an aside unrelated to the challenge, it's interesting that Stack Overflow does not follow the exception to rule 5.

Task

Input: A total number of pages n and a current page p.

Output: A list containing all the pages, in order, to be shown by the GitHub pager, with logic as described above. You may use any value that is not a possible page value to represent the ellipses. For example, -1, infinity or 0 (but 0 is only valid if you are using 1-based indexing).

  • You can use 0-based or 1-based indexing.
  • You can take input and output in any reasonable format (eg, output can be an array, 1 number per line, etc).

This is code golf with standard site rules.

Test Cases

Format will be [n, p] => <output list>, using -1 to represent ellipsis. Test cases use 1-based indexing.

[1, 1] => [1]
[2, 1] => [1, 2]
[2, 2] => [1, 2]
[5, 1] => [1, 2, 3, 4, 5]
[5, 5] => [1, 2, 3, 4, 5]
[11, 6] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[11, 5] => [1, 2, 3, 4, 5, 6, 7, -1, 10, 11]
[12, 6] => [1, 2, 3, 4, 5, 6, 7, 8, -1, 11, 12]
[12, 7] => [1, 2, -1, 5, 6, 7, 8, 9, 10, 11, 12]
[13, 7] => [1, 2, -1, 5, 6, 7, 8, 9, -1, 12, 13]
[100, 1] => [1, 2, 3, 4, 5, -1, 99, 100]
[100, 100] => [1, 2, -1, 96, 97, 98, 99, 100]
[100, 99] => [1, 2, -1, 96, 97, 98, 99, 100]
[100, 98] => [1, 2, -1, 96, 97, 98, 99, 100]
[100, 95] => [1, 2, -1, 93, 94, 95, 96, 97, 98, 99, 100]
[100, 94] => [1, 2, -1, 92, 93, 94, 95, 96, -1, 99, 100]
\$\endgroup\$
5
  • 2
    \$\begingroup\$ I think this is a dupe of something... \$\endgroup\$
    – Seggan
    Jul 5 at 1:24
  • \$\begingroup\$ Before posting I searched “pager” and a couple other terms but didn’t find anything. If you find one we can close it. \$\endgroup\$
    – Jonah
    Jul 5 at 1:29
  • 1
    \$\begingroup\$ Goto the Nth Page is very similar. \$\endgroup\$
    – Dingus
    Jul 5 at 1:34
  • 1
    \$\begingroup\$ Yeah pretty close though it lacks the “GitHub” exception and adds the prev/next logic. Feel free to vote to close, I won’t be offended. \$\endgroup\$
    – Jonah
    Jul 5 at 1:46
  • 1
    \$\begingroup\$ Another related one: Page Selector. \$\endgroup\$
    – pajonk
    Jul 5 at 5:48

9 Answers 9

5
\$\begingroup\$

Python 3.8, 103 bytes

lambda n,m:[S&{i+1}and i for i in range(n)if{i}&(S:={0,1,2,*range(min(n-5,m-2),max(6,m+4)),n-2,n-1,n})]

Try it online!

0-indexed. Use set() for ellipsis. And it can be 97 bytes if we can output each page numbers as a set.

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

Jelly, 22 bytes

_2«Ɠ»3,‘ŻạⱮ«4§<11×RŒg§

Try it online!

Takes page count as a command-line argument and page number from standard input. 1-based, using 0 for elided pages.

Algorithm

In order to handle the special case of showing five pages at one end if the active page happens to be there, the page number \$p\$ is clamped into the range \$[3, n-2]\$ (this is impossible if there are 4 or fewer pages, but in that case, the algorithm gives the correct result regardless of the page number because the first two and last two pages cover the whole range). The idea is that instead of having a special case, we can just use the "natural" behaviour of showing pages within two spaces of the current page in order to show the five pages at an end.

For each page, its page number is then compared to \$0\$, the clamped value of \$p\$, and \$n+1\$, looking for the absolute distance. If the page is within two pages of any of these anchors, then we want to display its page number. We also want to display a page if it's within three pages of two of the anchors (if the anchors are on the same side of the page, it'll necessarily be within two pages of one of them because no two anchors can be in the same place; if the anchors are on opposite sides, then they're forming a one-page gap which needs to be displayed rather than elided). To accomplish this check, any absolute distance that's 4 or greater is clamped to 4, and then the three absolute distances are added together. If we're within two pages of any anchor, the sum will be at most \$4+4+2=10\$ (but could be lower). If we're within three pages of two anchors, the sum will be at most \$4+3+3=10\$ (again, it could be lower). If neither of these conditions hold, the sum will be at least \$4+4+3=11\$. So we can check whether a page should be displayed by seeing whether the sum is in the range \$[0,10]\$ or not.

Once the list of pages to include has been determined, they're converted into a list of page numbers of the appropriate format (by pointwise-multiplying the "should be included" boolean by the page number, and then collapsing runs of consecutive zeroes). The runs of consecutive zeroes can be detected by looking for runs of consecutive equal elements, because all the included page numbers will be different from each other.

Explanation

_2«Ɠ»3,‘ŻạⱮ«4§<11×RŒg§
   Ɠ                     Read and parse standard input
  «                      Clamp to at most
_2                         {the argument} minus 2
    »3                   Clamp to at least 3
      ,                  Form a 2-element list with
       ‘                   {the argument} plus 1
        Ż                Prepend 0
          Ɱ              For each number from 1 to {the argument}
         ạ                 take its absolute difference with {each list element}
           «4            Clamp to at most 4
             §           For each {page}, sum the three clamped differences
              <11        1 for sums below 11, 0 for sums at least 11
                 ×       Multiply
                  R        {pointwise} by a list from 1 to {the argument}
                   Œg    Group consecutive equal elements
                     §   Replace each {group} with its sum
\$\endgroup\$
4
\$\begingroup\$

Python, 98 bytes (@xnor)

lambda n,k:[1,2,3*(k<7),*range(max(6,min(k,m:=n-2))-2,min(max(6,m),k+3+2//k)),m*(k+6>n),n-1,n][:n]

Attempt This Online!

Old Python, 101 bytes

lambda n,k:[1,2,3*(k<7),*range(max(4,min(k-2,n-4)),min(max(6,n-2),k+3+2//k)),(n-2)*(k+6>n),n-1,n][:n]

Attempt This Online!

Old Python, 110 bytes (@tsh)

lambda n,k:range(1,-~n*(n<9))or[1,2,3*(k<7),*range(max(4,min(k-2,n-4)),min(n-2,k+3+2//k)),(n-2)*(k+6>n),n-1,n]

Attempt This Online!

Old Python, 112 bytes

lambda n,k:range(1,-~n*(n<9))or[1,2,3*(k<7),*range(max(4,k-2--2//(k+~n)),min(n-2,k+3+2//k)),(n-2)*(k+6>n),n-1,n]

Attempt This Online!

Thanks to @tsh for spotting typo.

1-based, 0 for ellipsis. Outputs a range object instead of a list if n<9. If that is not acceptable we can add 3 bytes or switch to python 2.

\$\endgroup\$
2
  • \$\begingroup\$ Will lambda n,k:range(1,-~n*(n<9))or[1,2,3*(k<7),*range(max(4,min(n-4,k-2)),min(n-2,k+3+2//k)),(n-2)*(k+6>n),n-1,n] works? I really didn't understand what is going on here. \$\endgroup\$
    – tsh
    Jul 6 at 9:22
  • \$\begingroup\$ Saving a few bytes from your 101 with walrus: lambda n,k:[1,2,3*(k<7),*range(max(6,min(k,m:=n-2))-2,min(max(6,m),k+3+2//k)),m*(k+6>n),n-1,n][:n] \$\endgroup\$
    – xnor
    Jul 7 at 11:04
2
\$\begingroup\$

Python3, 194 bytes:

lambda n,p:F([[-1,i][i<3 or p+4-2*(p-2>0)>=i>=p-2-2*(n-p<2)+(n-p==1)or i>n-2]for i in range(1,n+1)])
F=lambda j,l=0:j if[]==j else[[[-1,l+1][l+2 in j],j[0]][j[0]!=-1]]*(j[0]+l!=-2)+F(j[1:],j[0])

Try it online!

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

Python, 151 bytes

lambda l,k:re.sub('  +',' . ',' '.join(str(i)if(i<2 or i>l-3or k-3<i<k+3or(i<5and k<6)or(i>l-6and k>l-7))else''for i in range(l))).split(' ')
import re

Attempt This Online!

Returns a list of strings. Abuses regex to remove duplicate spaces. Elipsed pages are replaced with a .

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

05AB1E, 45  44  38 bytes

Crossed out &nbsp;44&nbsp; is no longer 44 :)

4ÝÍ+¤I-F<}¬(ƒ>}3LìI2Ý-«ILÃïêD¥Θ2ä1.ý˜*

Inputs in the order \$p,n\$. Outputs with 0 for the ellipsis.

Try it online or verify all test cases.

Explanation:

Step 1: Create list [1,2,3,p-2,p-1,p,p+1,p+2,n-2,n-1,n], while keeping \$p-2\$ and \$p+2\$ in bounds, and remove any overlapping duplicated values:

4Ý          # Push list [0,1,2,3,4]
  Í         # Decrease each by 2 to [-2,-1,0,1,2]
   +        # Add each to the first (implicit) input p: [p-2,p-1,p,p+1,p+2]
    ¤       # Push the last value / maximum (without popping the list): p+2
     I-     # Decrease it by the second input n
       F }  # (If it's positive) loop that many times:
        <   #  Decrease the values in the list by 1 each iteration
    ¬       # Push the first value / minimum (without popping the list): p-2
     (      # Negate it
      ƒ }   # (If it's now non-negative) loop that + 1 amount of times:
       >    #  Increase the values in the list by 1 each iteration
3Lì         # Prepend-merge list [1,2,3]
 2Ý         # Push list [0,1,2]
I  -        # Subtract each from the second input n: [n,n-1,n-2]
    «       # Merge that list
IL          # Push a list in the range [1,n]
  Ã         # Only keep those values from the list, removing out of bounds values
   ï        # `Ã` converts the values to strings, so convert them back to integers
ê           # Sorted-uniquify the list

Step 2: Insert the 0s where necessary, and output the result:

D           # Duplicate this list
 ¥          # Pop the copy, and push its forward differences
  Θ         # Check for each whether it's equal to 1 (1 if 1; 0 otherwise)
   2ä1.ý˜   # Insert a 1 in the middle of the list:
   2ä       #  Split it into two equal-sized parts
     1.ý    #  Intersperse with 1
        ˜   #  Flatten it back to a single list
         *  # Multiply the values at the same positions
            # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 34 32 30 29 28 bytes

R©ạÞḣ5;⁸’¤;2ḣ⁸Ṭµ+3\ỊŻ¬o×®Œg§

Try it online!

Thanks to Unrelated String for -2 byte.

Explanation (outdated)

R©                       Range and copy to register.
   Þ                     Sort by...
  ạ                        Absolute difference with p.
    ḣ5                   First 5 elements.
      ;⁸’¤;2             Append n-1 and 2.
            ®œ&          Intersection with register, for the special case that n=1.
               Ṭ         Untruth (boolean array from truthy indices).
µ                        Chain separator.
ṡ3                       All slices with length 3.
  §                      Sum each slice.
   2=                    True if equals to 2.
     1;                  Prepend 1.
       |                 Vectorized OR with the result of the previous chain.
        ×®               Vectorized multiplication by the register.
          Œg             Group nearby equal elements. Only possible for the zeros.
            §            Sum each group.
\$\endgroup\$
3
  • \$\begingroup\$ Feels like there should be more to golf, but -2 with S€ -> §. \$\endgroup\$ Jul 7 at 14:05
  • 1
    \$\begingroup\$ @UnrelatedString Thanks. But one of the § breaks the case where n=1 for some reasons. \$\endgroup\$
    – jimmy23013
    Jul 7 at 17:22
  • 1
    \$\begingroup\$ In that case, it seems ṡ3S€ -> `+3\` still works. \$\endgroup\$ Jul 7 at 17:28
1
\$\begingroup\$

Retina 0.8.2, 158 bytes

.+
$*
\G1
$`1 
¶

O`1+
\b(1+) \1\b
<$1>
(?=(1+ ){0,2}<)((1+ |<1+> ){5}).+ 1+( 1+ 1+)
$2...$4
(1+ 1+ )1+ .+(( 1+| <1+>){5})(?<=>( 1+){0,2})
$1...$2
<|>

1+
$.&

Try it online! Takes newline-separated values but link is to test suite that splits on spaces for convenience. Explanation:

.+
$*

Convert to unary.

\G1
$`1 

Generate all of the page numbers.

Concatenate the current page.

O`1+

Sort it into position, so it's now a duplicate.

\b(1+) \1\b
<$1>

Change the duplicate into a marking.

(?=(1+ ){0,2}<)((1+ |<1+> ){5}).+ 1+( 1+ 1+)
$2...$4

Elide at least two page links starting from three pages after the current page to two pages before the last page, but also not starting before page 6.

(1+ 1+ )1+ .+(( 1+| <1+>){5})(?<=>( 1+){0,2})
$1...$2

Elide page links before the current page, using the same rules but mirrored.

<|>

Remove the marking for the current page.

1+
$.&

Convert to decimal.

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

JavaScript (ES6), 106 bytes

Expects (n)(p). The output is 1-indexed, with 0 for ellipsis.

n=>g=(p,b=k=i=[])=>++k>n?b:g(p,k<(p<3?6:3)|k>n-(p+3>n?5:2)|(p-=k)*p<9?[...b,...k>++i?[k+~i?0:i]:[],i=k]:b)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ It's always surprised me that JS engines won't accept a Unicode ellipsis () as the spread operator, instead of .... Could save you four bytes! 😉 (Note: While true, this (facetiously-made) justification would be a terrible reason to make a language operator. Nevertheless, I am genuinely a bit surprised it hasn't been done.) \$\endgroup\$
    – FeRD
    Jul 7 at 13:59
  • 1
    \$\begingroup\$ @FeRD However, we score in bytes and is 3 bytes once encoded in UTF-8 (0xE2, 0x80, 0xA6), leading to the exact same score. (As opposed to a language like Jelly that uses a custom code page, which means that each symbol is exactly one byte.) \$\endgroup\$
    – Arnauld
    Jul 7 at 14:13

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.