-5
\$\begingroup\$

Your task is to remove smallest amount elements from a list, so the most elements are on their corresponding place. The element is on it's corresponding place, when it's value is equal to it's position.

Let's look at this example list:

1 5 3 2 5

This list has three elements on their corresponding place (1 on position 1, 5 on position 5, 3 on position 3).

Input

The input is a sequence of decimals in any reasonable format. For example:

1 3 2 3 6

Output

The output is a sequence of decimals in any reasonable format which contains, as its first element, the amount of elements removed from the input then the corresponding, 1-based element positions removed.

For example, for input given above, the (correct) output:

1 2

instructs us to remove one element, the one at index two (the first 3), which will leave us with 1 2 3 6 which has three elements at their index positions.

This output would be incorrect:

2 2 5

Since although removing the two elements at indexes two and five would leave us with 1 2 3 which also has three elements at their index positions, we've removed more than the minimal necessary.

More complicated example

1 2 3 3 4 5 6

In this case you can remove either of 3's, but not both (so 1 3 and 1 4 are both acceptable outputs).

1 3 2 3 4 5 6 7 8

In this case, if you would remove 3 on position 2, it would pass more elements, than if you would remove 3 on position 4 (so 1 4 is incorrect while 1 2 is correct).

1 3 2 3 5 6 7 8 9

Here removing 3 on position 2 is a mistake, because this actually makes the situation worse in obvious way (there are now less correctly placed elements than before). (the correct output is 0 since removing no elements is the best thing to do)

1 7 2 8 1 3 9

In this case we want to remove the three elements at positions 2, 4, and 5 (leaving us 1 2 3 9 for three in the correct location) so the correct output would be 3 2 4 5)

Rules

  • This is code golf, so the shortest code wins!
  • Loopholes are forbidden.
  • Assume that input is valid, contains nothing more than digits and spaces, and the input numbers inside the string are decimals in range of 0 <= n <= 99.
  • Please include a link to an online interpreter for your code.
  • If anything is unclear, please let me down in the comments.
\$\endgroup\$
  • \$\begingroup\$ Can we use 0 based indices? \$\endgroup\$ – Embodiment of Ignorance Aug 15 at 18:09
  • \$\begingroup\$ @EmbodimentofIgnorance I want to make it uniform, so only 1 based indices are allowed. \$\endgroup\$ – Krzysztof Szewczyk Aug 15 at 18:10
1
\$\begingroup\$

Pyth, 20 bytes

lBhMh.Ms.eqktb.DQZyU

Try it online!

\$\endgroup\$
  • \$\begingroup\$ It was stated clearly that you have to. \$\endgroup\$ – Krzysztof Szewczyk Aug 15 at 18:57
  • \$\begingroup\$ Ok, edited the answer. I still don't understand why. \$\endgroup\$ – Mr. Xcoder Aug 15 at 18:58
  • \$\begingroup\$ Because there is such requirement in the answer. \$\endgroup\$ – Krzysztof Szewczyk Aug 15 at 18:59
1
\$\begingroup\$

Jelly, 18 bytes

JŒPṚœPF=J$SʋÞ⁸ṪL;$

Try it online!

How?

JŒPṚœPF=J$SʋÞ⁸ṪL;$ - Link: list of numbers, A
J                  - range of length (A) [1,2,3,...,len(A)]
 ŒP                - all partitions      [[1],[2],...,[1,2],[1,3],...,[2,3],...]
   Ṛ               - reversed (so longest to shortest)
            Þ      - sort (the p's in all partitions) by:
             ⁸     -   (using the chain's left argument, A, as the right argument)
           ʋ       -   last four links as a dyad, i.e. f(p, A):
    œP             -     partition A at the indices in p
      F            -     flatten (to give result of dropping the values at indices in p)
         $         -     last two links as a monad:
        J          -       range of length (of the flatten result)
       =           -       equals? (vectorises)
          S        -     sum
              Ṫ    - tail (i.e. the shortest p which yields the maximal sum)
                 $ - last two links as a monad:
               L   -   length (of that result)
                ;  -   concatenate

An alternative for =J$ is ĖE€

\$\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.