5
\$\begingroup\$

Related: What's my telephone number? which asks to calculate the terms of A000085, the number of possible ordinal transforms of length n.

Background

Ordinal transform is a transformation on an integer sequence. For a sequence \$a=(a_0, a_1, a_2, \cdots)\$, the \$n\$-th term of the ordinal transform \$ord(a)_n\$ is defined as the occurrence count of \$a_n\$ in \$a_0, a_1, \cdots, a_n\$. Informally, \$ord(a)\$ can be described as "the value \$a_n\$ appears the \$ord(a)_n\$-th time in the sequence \$a\$".

For example, the sequence [1, 2, 1, 1, 3, 2, 2, 3, 1] transforms into [1, 1, 2, 3, 1, 2, 3, 2, 4].

1, 2, 1, 1, 3, 2, 2, 3, 1
1, 1, 2, 3, 1, 2, 3, 2, 4
^     ^  ^              ^
|     |  |              4th occurrence of 1
|     |  3rd occurrence of 1
|     2nd occurrence of 1
1st occurrence of 1

The number of possible ordinal transforms is A000085. A hint to tackle this problem can be found on the page (search for "ballot sequences").

Challenge

Given a non-empty finite integer sequence, test if it can be the result of ordinal transform of some integer sequence.

You can assume the input entirely consists of positive integers.

For output, you can choose to

  1. output truthy/falsy using your language's convention (swapping is allowed), or
  2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy

[1]
[1, 1]
[1, 2, 3, 1]
[1, 1, 2, 2]
[1, 2, 1, 2, 1, 2, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 1, 2, 3, 1, 2, 3, 2, 4]
[1, 1, 2, 3, 4, 2, 1, 3, 2, 1]

Falsy

[2]
[6]
[1, 3]
[2, 1, 1]
[1, 2, 2, 1]
[1, 2, 3, 2]
[1, 2, 3, 4, 4]
[1, 2, 3, 2, 1]
\$\endgroup\$
3
  • \$\begingroup\$ Does this work out to the same as stackable sequences with 1-indexing? \$\endgroup\$ – xnor Jul 15 at 1:54
  • \$\begingroup\$ @xnor Turns out to be yes. Another difference is that the sequence contents are not upper-bounded, though I guess it's minor... \$\endgroup\$ – Bubbler Jul 15 at 2:01
  • 1
    \$\begingroup\$ I've closed this as a duplicate of the challenge linked by @xnor - I believe that the differences between the two are minor, as shown by my answers to both \$\endgroup\$ – caird coinheringaahing Jul 15 at 3:02
4
\$\begingroup\$

Jelly, 8 7 bytes

Ṭ€+\I’Ȧ

Try it online!

-1 byte thanks to Jonathan Allan

Outputs an empty array (falsey) if it can be the result, and a non-empty array (truthy) if not.

How it works

Ṭ€+\I’Ȧ - Main link. Takes a list L on the left
 €      - For each integer I in L:
Ṭ       -   Untruth; Generate a list of zeroes of length I, replace the last with 1
   \    - Scan by:
  +     -   Addition
    I   - Get the forward differences of each
     ’  - Decrement
      Ȧ - This array does not contain any 0s

For exactly what this does, let's look at this step by step:

Command Truthy example Falsey example
Start [1, 2, 3, 1] [1, 2, 3, 2]
Ṭ€ [[1], [0, 1], [0, 0, 1], [1]] [[1], [0, 1], [0, 0, 1], [0, 1]]
+\ [[1], [1]+[0,1], [1]+[0,1]+[0,0,1], [1]+[0,1]+[0,0,1]+[1]]

[[1], [1,1], [1,1,1], [2,1,1]]

[[1], [1]+[0,1], [1]+[0,1]+[0,0,1], [1]+[0,1]+[0,0,1]+[0,1]]

[[1], [1,1], [1,1,1], [1,2,1]]

At this point, we have running counts of each element. The ith element of Ṭ€+\ is a list [a,b,c,...,z] where a is the number of counts of 1 in the first i elements of the input, b the counts of 2 and so on. The input is only truthy if each list is ordered descendingly.

In order to do this, we get the forward differences of each. This will be a list of lists of -1, 1 and 0. If any of the differences have 1, then it's ascending. We then decrement, mapping 1 to 0 and everything else to a non-zero element. Finally, we check with Ȧ that there are no zeroes in the list at any level.

\$\endgroup\$
5
  • \$\begingroup\$ I've definitely been thinking of something involving Ṣ€Ƒ myself, if that gets you marginally more confident \$\endgroup\$ – Unrelated String Jul 15 at 0:36
  • 1
    \$\begingroup\$ Looks correct to me. Interesting that Jelly doesn't have non-vectorizing cumulative sum built-in :P \$\endgroup\$ – Bubbler Jul 15 at 0:39
  • 1
    \$\begingroup\$ 7 bytes using the truthy/falsey in your language option, I to take forward-differences and R to force 0 and -n to empty lists and +n to [1..n]. \$\endgroup\$ – Jonathan Allan Jul 15 at 1:35
  • \$\begingroup\$ @JonathanAllan That's brilliant, thanks! \$\endgroup\$ – caird coinheringaahing Jul 15 at 1:37
  • 2
    \$\begingroup\$ I really like this table method of explanation. I'll probably be stealing that at some point. \$\endgroup\$ – Jonah Jul 15 at 3:22
3
\$\begingroup\$

JavaScript (ES6), 40 bytes

a=>a.every(n=>a[a[~n]=-~a[~n],-n]--|n<2)

Try it online!

Ungolfed:

arr => {
  const count = [Infinity]
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    count[num] = (count[num] || 0) + 1;
    count[num - 1] = (count[num - 1] || 0) - 1;
    if (count[num - 1] < 0) {
      return false;
    }
  }
  return true;
}
\$\endgroup\$
2
\$\begingroup\$

Japt, 16 15 bytes

Quite exhausted so I'm sure I'll improve upon it in the morn'. Less sure that it's actually correct so, mods, please delete if it's not. Shockingly, it was correct! Haven't been able to improve much on my score, though.

e1g2Æ=¡YôgU è¶X

Try it or run all test cases

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.