3
\$\begingroup\$

Given a sequence \$S\$ with length \$n\$ of exactly one each of whole numbers from \$1\$ to \$n\$, your task is to return a number \$\sigma\$ indicating how shuffled it is.

Definition of shuffledness

Humans perceive shuffling randomness locally [Citation Needed], so the shuffledness of a sequence is based on the ability to find various patterns within each sliding window \$W\$ of 5 consecutive elements of the sequence (\$W = \{S_x, S_{x+1}, S_{x+2}, S_{x+3}, S_{x+4}\}\$ for some \$x\$- these will overlap, as each \$x\$ that is at least \$4\$ less than \$n\$ is considered). For each window of 5 elements, add a point for each test of the following that fails: (Note the 1-indexing due to the use of mathematical notation)

  • Apply the following tests to the whole window:
    1. \$W\$ is monotonic
    2. \$W\$ is in ascending order
    3. Some permutation of \$W\$ is a run of sequential integers (e.g. 1, 2, 3, 4, 5)
    4. For all \$W_i\$ where \$i>1\$, \$W_i = W_{i-1}+k\$ for some integer \$k\$.
      • This corresponds to regular linear intervals
    5. For all \$W_i\$ where \$i>1\$, \$W_i = W_{i-1}+ax+k\$ for some integers \$k, a\$, where \$x=i\$.
      • This corresponds to regular quadratic intervals (which could also be linear)
  • Apply the same tests for subwindows where 1 or 2 elements have been removed (if any one of those reduced windows passes a particular test, this step passes. Only count one failure when a test fails for all reduced windows.
  • Apply the same tests for windows with some pair of adjacent elements optionally swapped (this step will pass if all tests passed for the whole unmodified window) Replace test 3 with the following:
    • \$W\$ is an ascending or descending sequence of sequential integers (e.g. 5, 4, 3, 2, 1)

Notes

  • Ascending sequential sequences will pass every test for all windows and therefore be scored as \$0\$
  • Descending sequential sequences will pass all tests except the "ascending" one for all windows and will therefore be scored as \$3(n-4)\$
  • The naive maximum shuffledness is \$15(n-4)\$

Examples

  • [1, 5, 3, 2, 4]
    • All elements:
      • Passes test 3
      • Fails all other tests (+4)
    • Elements removed:
      • Passes tests 1, 2, 5 with [1, 2, 4] (remove 5 and 3)
      • Passes test 3 with [5, 3, 2, 4] (remove 1)
      • Fails test 4 (+1)
    • Elements swapped:
      • Fails all tests (+5)
        • Test 3 fails because it requires the elements to be in order for this case only
    • \$\therefore \sigma = 10\$
  • [1, 2, 4, 3, 5]
    • All elements:
      • Passes test 3
      • Fails all other tests (+4)
    • Elements removed:
      • All tests pass with [1, 2, 3] (remove 4, 5)
    • Elements swapped:
      • Passes all tests (swap 4, 3)
    • \$\therefore \sigma = 4\$
  • [3, 6, 9, 12, 15] (a sliding window)
    • All elements:
      • Passes tests 1, 2, 4, 5
      • Fails test 3 (+1)
    • Elements removed: same (+1)
    • Elements swapped: same (+1) (no swap)
    • \$\therefore \sigma = 3\$
  • [8, 12, 13, 11, 6] (a sliding window)
    • All elements:
      • Passes test 5 (\$a=-3, k=4\$)
      • Fails all other tests (+4)
    • Elements removed:
      • Passes tests 1, 2, 5 with [8, 12, 13] (remove 11, 6)
      • Passes test 3 with [12, 13, 11] (remove 8, 6)
      • Fails test 4 (+1)
    • Elements swapped: same as all elements (+4) (no swap)
    • \$\therefore \sigma = 9\$
  • [2, 4, 6, 1, 3, 5] (whole sequence)
    • First window: ([2, 4, 6, 1, 3])
      • All elements: Fails all tests (+5)
      • Elements removed:
        • Passes tests 1, 2, 4, 5 with [2, 4, 6]
        • Passes test 3 with [2, 1, 3]
      • Elements swapped: Fails all tests (+5)
    • Second window: ([4, 6, 1, 3, 5])
      • All elements: Fails all tests (+5)
      • Elements removed:
        • Passes tests 1, 2, 4, 5 with [1, 3, 5]
        • Passes test 3 with [4, 6, 5]
      • Elements swapped: Fails all tests (+5)
    • \$\therefore \sigma = 20\$

Rules and such

  • Standard IO rules, loopholes, etc
  • You must handle sequences of up to 1000 elements long
  • You may assume \$S\$ is at least 5 elements long
  • No validation necessary. You may assume that all inputs contain exactly one each of every whole number from \$1\$ to \$n\$
  • Shortest code wins!
\$\endgroup\$
  • \$\begingroup\$ In the first example, how can it fail all tests for the elements swapped bit? \$\endgroup\$ – Nick Kennedy Dec 28 '19 at 0:22
  • \$\begingroup\$ How is \$W_x\$ defined? \$\endgroup\$ – flawr Dec 28 '19 at 11:17
  • \$\begingroup\$ @NickKennedy The swapped elements test requires the run to actually be in order \$\endgroup\$ – Beefster Dec 30 '19 at 4:10
  • \$\begingroup\$ @flawr \$W_x\$ is the \$x\$th element of \$W\$ \$\endgroup\$ – Beefster Dec 30 '19 at 4:11
  • \$\begingroup\$ @Beefster I'd suggest adding that in a small comment, or writing something like \$W = (W_1,W_2,\ldots)\$. (It was confusing for me as \$x\$ is an unusual variable to use for indexing.) \$\endgroup\$ – flawr Dec 30 '19 at 14:44
2
\$\begingroup\$

Jelly, 71 65 bytes

J4Ṭ;-+ʋ€ịṭ@Wẋ¥€3ṭœcJ;2/Ṣṭ,`Ɗ€€ƲḊ,UṢƑ€o\ƲI,I$E€ƊIỊẠƊ3ƭ€€€»/€¬µ5ƤFS

Try it online!

A monadic link taking a list if integers and returning an integer. I’m sure this can be shortened further.

Explanation

...µ5Ƥ   | Run the main chain (below) for each 5-integer-long infix of the list
      F  | Flatten list
       S | Sum

Main chain

This generates the lists for the each set of tests. To deal with the variation in test 3, there are 3 copies made of each innermost list. For the first and second sets of tests, the last copy of each innermost list is sorted, while for the third set of tests it is not.

Main chain part 1 (generates swapped lists for third set of tests)

J                | Sequence along list [1,2,3,4,5]
 4    ʋ€         | Do the following as a dyad for each of 1,2,3,4 with 1,2,3,4,5 as the right argument:
  Ṭ              | - Convert to logical list with 1 at the relevant index [[1],[0,1],[0,0,1],[0,0,0,1]]
   ;-            | - Concatenate -1 to this
     +           | - Add (to [1,2,3,4,5])
        ị        | Index into original list
         ṭ@      | Tack onto end the original list
           Wẋ¥€3 | Repeat each inner list 3 times

Main chain part 2 (generates lists for first and second sets of tests)

ṭ             Ʋ  | Tack output of part 1 onto the following:
 œcJ             | - Combinations of lengths 1,2,3,4,5
    ;2/          | - Pairwise reduce using concatenation
           Ɗ€€   | - Following as a monad for each innermost list:
       Ṣ         |   - Sort
        ṭ,`      |   - Tacked onto the list paired with itself
               Ḋ | - Remove first (i.e. the combinations of lengths 1 and 2)

Main chain part 3 (runs the tests)

                   3ƭ€€€     | For each innermost list, do one of the following three in turn:
       Ʋ                     | - Tests 1 and 2
,U                           |   - Pair with reversed list
  ṢƑ€                        |   - Check whether each invariant if sorted
     o\                      |   - Cumulative or
              Ɗ              | - Tests 4 and 5
        I                    |   - Increments (test 4)
         ,I$                 |   - Paired with increments of increments (test 5)
            E€               |   - Check if all equal for each of these
                  Ɗ          | - Test 3
               I             |   - Increments
                Ị            |   - Absolute value <= 1
                 Ạ           |   - All
                        »/€  | Reduce each using max - picks the best results for each test for each set of tests
                           ¬ | Not (vectorises)
\$\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.