17
\$\begingroup\$

inspired by Longest Increasing Substring

Task

Given a list of non-negative integers, output the length of its longest alternating subsequence.

An alternating sequence is a sequence of numbers which alternates between strictly increasing and strictly decreasing. [], [999], [9, 1], and [0, 5, 0, 3, 2, 4] are examples of an alternating sequence, while [0, 0] and [1, 3, 5] are not.

A mathematical definition: A sequence \$A = a_1, a_2, \cdots, a_n\$ is alternating if

  • \$a_k \ne a_{k+1}\$ for \$k = 1, 2, \cdots, n-1\$, and
  • \$a_k < a_{k+1} \Rightarrow a_{k+1} > a_{k+2} \$ and \$a_k > a_{k+1} \Rightarrow a_{k+1} < a_{k+2}\$ for \$k = 1, 2, \cdots, n-2\$.

If the input is [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], the longest alternating subsequence is [3, 1, 4, 1, 9, 2, 6, 3, 5] and its length is 9. Note that the subsequence does not need to be contiguous.

Scoring

The score of your answer is calculated as follows:

  • Treat your source code as a list of bytes (or, if your language uses a non-256-char custom character set, the list of character codes within the character set).
    • If your language supports multiple encodings, you may use the one that gives the best score. However, the score and the code size must be calculated using the same encoding.
  • Give it as input to your own program, and the output is your score.

The lowest score wins. Tiebreaker is shorter code in bytes.

Test cases

[] => 0
[1] => 1
[1, 1] => 1
[9, 9, 9, 9, 9, 9, 9] => 1
[5, 10] => 2
[0, 1, 2] => 2
[5, 10, 10, 5] => 3
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] => 9
[1, 2, 2, 2, 3, 3, 4, 4, 5, 6] => 2
[2, 2, 1, 2, 5, 6, 6, 5] => 4
\$\endgroup\$
11
  • 2
    \$\begingroup\$ I feel like this will mostly be a competition to stuff arbitrary code execution into a format with few alternations, like a character repeated many times or an increasing sequence. \$\endgroup\$
    – xnor
    Oct 6, 2022 at 0:09
  • \$\begingroup\$ Anyone who writes a Unary solution gets a score of 0 automatically, so it's just a question of who can score 0 in a different language and win the tiebreaker. \$\endgroup\$
    – DLosc
    Oct 6, 2022 at 1:50
  • \$\begingroup\$ @DLosc Unary would score 1 (not 0), but you're right that it'd be next to impossible to beat or even tie with a different language. \$\endgroup\$
    – Bubbler
    Oct 6, 2022 at 1:56
  • \$\begingroup\$ If a program only supports input lengths as long as the source code, is that allowed? \$\endgroup\$ Oct 6, 2022 at 10:41
  • 1
    \$\begingroup\$ @12431234123412341234123 No, any answer must (at least theoretically) support inputs of arbitrary length. Otherwise Jelly L would work for example. \$\endgroup\$
    – Bubbler
    Oct 6, 2022 at 12:13

9 Answers 9

7
\$\begingroup\$

Python 3, score 16, \$6.6 \times 10^{2073} \$ bytes

exec(b"".fromhex(str(len(" "))))

Try it online!

The string " " above should actually be the number of spaces below, about \$6.6 \times 10^{2073} \$, but somehow Stack Exchange won't let me post the whole string and TIO won't run it.

6578656328272563252573272531303225272563252573272536312527256325257327253130382527256325257327253937252725632525732725313039252725632525732725393825272563252573272531303025272563252573272539372527256325257327253332252725632525732725313038252725632525732725343425272563252573272531313225272563252573272536312527256325257327253438252725632525732725343425272563252573272531313325272563252573272536312527256325257327253435252725632525732725343925272563252573272535382527256325257327253130382527256325257327253632252725632525732725393125272563252573272539332527256325257327253937252725632525732725313130252725632525732725313030252725632525732725333225272563252573272531303925272563252573272539372527256325257327253132302527256325257327253430252725632525732725313032252725632525732725343025272563252573272531303825272563252573272539312527256325257327253439252725632525732725353825272563252573272539332527256325257327253434252725632525732725313132252725632525732725343425272563252573272531313325272563252573272534312527256325257327253434252725632525732725343525272563252573272531323625272563252573272531303225272563252573272534302527256325257327253130382527256325257327253931252725632525732725343925272563252573272535382527256325257327253933252725632525732725343425272563252573272531313325272563252573272534342527256325257327253131342527256325257327253538252725632525732725363125272563252573272531303825272563252573272539312527256325257327253438252725632525732725393325272563252573272534312527256325257327253432252725632525732725343025272563252573272534302527256325257327253931252725632525732725313132252725632525732725343425272563252573272531313425272563252573272539332527256325257327253931252725632525732725313132252725632525732725363025272563252573272534382527256325257327253933252725632525732725343525272563252573272531313325272563252573272534312527256325257327253432252725632525732725343025272563252573272531313325272563252573272534352527256325257327253131342527256325257327253431252725632525732725363025272563252573272534382527256325257327253431252725632525732725343125272729

Repeating a character many times in a row doesn't affect the score because an alternating subsequence can't contain two consecutive equal values. So, the game becomes to write a low-scoring wrapper that decodes a huge string of spaces (or any character) into arbitrary code and executes it.

The ginormous number above corresponds to the following moderately-golfed code for the length of the longest alternating subsequence. Being an exponential-time algorithm, it's too slow to actually compute the result for the code itself with spaces de-duplicated.

91 bytes

f=lambda l,p=0,q=-1:l>[]and max(f(l[1:],p,q),-~f(l[1:],q,r:=l[0])*(([p,r][p<0]-q)*(q-r)<0))

Try it online!

The wrapper

exec(b"".fromhex(str(len(" "))))

takes the length of a string of spaces, converts it to a hexadecimal string, interprets pairs of hex values as base 256 ASCII to convert it to a bytestring, and executes the result. Its longest alternating subsequence has length 16, as can be checked by an efficient implementation like the last one here, compared to 66 for the direct 91-byte code. The filler character can be replaced with any low-ASCII character without affecting the score, and single versus double quotes has no effect.

Actually, you might notice that the length is converted to a base-10 string with str(), not hexadecimal. This byte-save makes the wrapper have fewer alternations, at the cost of only being able to generate code of ASCII values whose hex representation have no letters a-f.

Luckily, this still allows all of exc('%0), which already suffice to run arbitrary Python 3 code, as shown by kzh. We could start by converting our payload code to this restricted format, but the result is very long -- it won't fit in my computer's memory. So, we "golf" this by taking advantage of also having access to all digits 0-9 and the letter s. A string, for example ABC with ASCII values [65,66,67], is converted to:

exec('%c%%s'%65%'%c%%s'%66%'%c%%s'%67%'')

which uses string formatting with %s to perform concatenation in place of the banned +. This format only gives a linear blow-up with 91 bytes becoming 1037, though this could surely be improved.

Amusingly, I thought that the Sep 2022 breaking change to Python string-converting large numbers would make this overall submission invalid in up-to-date versions of Python without using a command-line flag -- that is, if we're pretending that code of length \$6.6 \times 10^{2073} \$ can run at all. But, the 2074 digits of the number of spaces falls under the cutoff of 4300 past which str now errors out.

\$\endgroup\$
1
  • \$\begingroup\$ Holy, what is this??? :P \$\endgroup\$
    – DialFrost
    Oct 8, 2022 at 4:37
4
\$\begingroup\$

Husk, 11 13 14 bytes, score 9 6

Edit: +2 bytes to fix bug that counted repeated identical elements (thanks to Bubbler for spotting)
Edit2: changed approach for +1 byte but reducing score by 3

→OmöËεgfIẊo±-Ṗ

Try it online!

The codepoints of the program from the Husk code page are: [8,80,110,248,239,157,104,103,74,212,112,22,46,207], giving a longest alternating subsequence of length 6 (try it).
The codepoints were calculated using this program.

  mö            # map over
             Ṗ  # all subsequences of input
    ËεgfIẊo±-   # calculating length if it's an alternating seqeunce,
                # or returning zero otherwise (see below),
 O              # sort the results,
→               # and return the last (largest) element.   

         Ẋo     # map over all pairs of values
           ±-   # getting the sign of the difference,
       fI       # remove zeros,
      g         # and group adjacent equal values;
   Ë            # now, if all the groups 
    ε           # have a length of at most 1
                # return the length +1
                # (this is the length of the alternating subsequence)
                # otherwise return zero                        
\$\endgroup\$
4
\$\begingroup\$

Pyth, score: 7, (15 bytes)

+!!Qlr8-._M.+QZ

Try it online!

And as an added bonus it runs in O(n) time.

explanation

           .+Q     difference between each pair of elements in the input
        ._M        map list to the sign of the elements
       -      Z    remove all zeros
    lr8            number of sequences of repeated elements
+!!Q               add 1 if input is non-empty
\$\endgroup\$
4
\$\begingroup\$

05AB1E, score: 13 12 7 (23 21 10 bytes)

¥.±Igª¾Kγg

-1 score (and -2 bytes) taking inspiration from @DominicVanEssen's Husk answer.
-5 score (and -11 bytes) by porting @CursorCoercer's Pyth answer, so make sure to upvote him/her as well!

Try it online or verify all test cases.

The program has the following bytes, and using this as input in my own program results in 7 as its score.

Explanation:

¾ is used instead of 0 and γ is used instead of Ô to improve the score. ¥ could alternatively be ü-; I could be ¹ or s; ª could be š; and could be 0.S, but with any of those changes the score will remain the same, and combinations of some of these changes will also retain the same score, or even increase it.

¥           # Get the deltas/forward-difference of the (implicit) input-list
 .±         # Get the signum of each (0 if 0; -1 if <0; 1 if >0)
   Ig       # Push the input-length
     ª      # Append it to the list
      ¾K    # Remove all 0s from the list
        γ   # Split the list into groups of equal adjacent items
         g  # Get the length to get the amount of groups
            # (which is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Jelly, (12 bytes), score 4

I¹ƇṠŻạƝTL+JṂ

A monadic Link that accepts a list of non-negative integers and yields the length of the longest alternating subsequence.

Try it online! Or see the test-suite.

The bytes are: 74 130 145 206 211 212 151 85 77 44 75 180
See it score itself

How?

An alternating subsequence of maximal length can always be formed by taking the first element (if one exists) and appending the peaks and troughs, so the code calculates the length of that subsequence.

I¹ƇṠŻạƝTL+JṂ - Link: list of integers, A  e.g. [2,2,1,2,5,6,6,5]  OR  [4]  OR  []
I            - incremental differences (of A)  [0,-1,1,3,1,0,-1]      []       []
  Ƈ          - keep those for which:
 ¹           -   no-op                         [-1,1,3,1,-1]          []       []
   Ṡ         - sign                            [-1,1,1,1,-1]          []       []
    Ż        - prepend a zero                  [0,-1,1,1,1,-1]        [0]      [0]
      Ɲ      - for neighbours:
     ạ       -   absolute difference           [1,2,0,0,2]            []       []
       T     - truthy indices                  [1,2,5]                []       []
        L    - length                          3                      0        0
          J  - range of length (of A)          [1,2,3,4,5,6,7,8]      [1]      []
         +   - add (vectorises)                [4,5,6,7,8,9,10,11]    [1]      []
           Ṃ - minimum (empty list yields 0)   4                      1        0
\$\endgroup\$
3
\$\begingroup\$

Vyxal, score 4, 8 bytes

¯±ꜝĠL$ß›

Try it Online!

Port of CursorCoercer's Pyth answer, so upvote that!

The bytes are [212, 213, 222, 189, 76, 36, 14, 131].

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

Brachylog, score: 12 (18 bytes)

⊇L{s₂ᶠ≠ᵐ}-ᵐṡᵐ↰₁∧Ll

Try it online!

This scores 12 according to @Arnauld’s deleted JS answer, it times out on my own code.

This code, according to Brachylog’s code page, is the following string of char codes / integers:

[08, 4C, 7B, 73, 81, 98, 1B, 9F, 7D, 2D, 9F, D0, 9F, 0F, 80, 01, 4C, 6C]
[8, 76, 123, 115, 129, 152, 27, 159, 125, 45, 159, 208, 159, 15, 128, 1, 76, 108]

Explanation

⊇L                    L is a subset of the input
  L{s₂ᶠ≠ᵐ}            Get all contiguous sublists of 2 elements, which must be different
          -ᵐṡᵐ        Compute the signs of the subtraction of these sublists
              ↰₁      Get all contiguous sublists of 2 elements, which must be different
                ∧Ll   Output the length of L
\$\endgroup\$
4
  • \$\begingroup\$ The list of codepoints that you give seems to contain the alternating subsequence [76,123,115,152,27,125,45,159,159,15,128,76,108], which has a length of 13. \$\endgroup\$ Oct 6, 2022 at 9:18
  • 3
    \$\begingroup\$ @DominicvanEssen The alternating subsequence cannot contain [159,159] by the definition given. \$\endgroup\$
    – Bubbler
    Oct 6, 2022 at 9:20
  • 1
    \$\begingroup\$ @Bubbler - Ah, yes, you're right, so I need to re-check my code! Thanks! \$\endgroup\$ Oct 6, 2022 at 9:21
  • 1
    \$\begingroup\$ @DominicvanEssen I knew I could trust Arnauld’s code :p \$\endgroup\$
    – Fatalize
    Oct 6, 2022 at 9:22
2
\$\begingroup\$

Nibbles, 9 10.5 bytes (21 nibbles), score 7 6

Edit: +1.5 bytes but -1 score from fixing potential bug with empty input array, spotted by CursorCoercer

+`$,$,`=|!$>>@~`$-@$*

The 10 bytes + 1 half-byte of the Nibbles program are 8d 7d 3d b9 99 3c 04 0d 79 43 a (in decimal 141 125 61 185 153 60 4 13 121 67 10), giving a longest alternating subsequence of length 6.
Note that Nibbles pads the saved program with a filler 6 nibble at the end for odd numbers of nibbles: this is not counted in the bytes of the program.

+`$,$,`=|!$>>@~`$-@$*
         !              # zip together
          $             # the input
           >>@          # and the input without its first element
              ~         # using the combined function
                 -$@    # subtract arg2 from arg1
               `$       # and get the sign
        |           *   # filter to keep only nonzero elements
      `=                # and combine adjacent equal elements
     ,                  # now get the length of this
+                       # and add
 `$                     # 1 if non-zero
   ,$                   # the length of the input

enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ I have no way to test this, but going by your explanation I'd think this would fail on the case [] => 0 \$\endgroup\$ Oct 6, 2022 at 20:00
  • \$\begingroup\$ @CursorCoercer - I understand what you mean. I've tested with all the other test-cases, but Nibbles doesn't seem to have a way to input an empty list [] (this just gives an error). I should try to find a way to test this programmatically... \$\endgroup\$ Oct 6, 2022 at 20:58
  • \$\begingroup\$ @CursorCoercer - fixed now, amazingly improving the score thanks to all the nibbles shifting position within each byte. \$\endgroup\$ Oct 7, 2022 at 10:20
1
\$\begingroup\$

Charcoal, 49 bytes, score 28 24

≔¬¬θεFε«≔⁰ζ≔§θζηFθ«≔⁻›ηκ›κηδ≔κη¿∧⁻ζδδ«≔δζ≦⊕ε»»»Iε

Try it online! Link is to verbose version of code and includes the program's byte sequences using Charcoal's code page as sample input. Explanation:

≔¬¬θε

Start with a sequence of length 1 unless the input is empty.

Fε«

Don't try to measure the length of the sequence if the input is empty.

≔⁰ζ

Start with there not being a direction yet.

≔§θζη

Start with a copy of the first element of the sequence. (This uses the variable I just set to 0 because this avoids a double alternation.)

Fθ«

Loop over the elements of the sequence.

≔⁻›ηκ›κηδ

Calculate the direction between the previous and current element.

≔κη

Save the current element as the previous element.

¿∧⁻ζδδ«

If the direction is nonzero and has changed from the previous direction (tested in reverse order to avoid a double alternation), then...

≔δζ

... saved the new direction, and...

≦⊕ε

... increment the sequence length.

»»»Iε

Output the final sequence length.

The program will also work on string input (using the Unicode code points of the characters); the rearrangement of the condition actually avoided four alternations so its score is now 32 28 when measured this way.

I looked into the possibility of renaming the variables but as far as I can tell my naming scheme was already optimal.

\$\endgroup\$

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.