0
\$\begingroup\$

Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few substrings as possible, such that each substring is a permutation of a consecutive integer range. More formally, if the input array is A, then the output is minimum number of partition of A into B(s):

  • Each arrays B form a partition of A into substrings. Inductively, this means that either B is the singleton array containing 1 element from A, or the elements of B is a subsequence of A, which when sorted are contiguous like x,x+1,x+2,...
  • The number of arrays B is minimal.

Example

Consider the input array A = [1,2,3,4,3,5].
Output is 2
One possible minimal partitions are B = [1,2,3],[4,3,5]. That's the only partition to 2 substrings.

{4,3,5} in sorted order is {3,4,5} which is contiguous.

Input

An array of integers A.

Output

A number, indicate the smallest number of parts A can be splitted to.

Winning criteria

Your submissions will be scored in bytes, with less bytes being better.

\$\endgroup\$
23
  • 1
    \$\begingroup\$ This site is for programming contests (i.e., you post programming challenges in questions), general programming questions are off-topic here. \$\endgroup\$
    – DELETE_ME
    Jan 27 '18 at 7:52
  • 3
    \$\begingroup\$ (in other words, because the question is a question, it's off-topic. Counter-intuitive) \$\endgroup\$
    – DELETE_ME
    Jan 27 '18 at 7:52
  • \$\begingroup\$ Is this a code-golf? Maybe you should clarify and add a code-golf tag. \$\endgroup\$
    – alephalpha
    Jan 27 '18 at 8:04
  • 2
    \$\begingroup\$ Is the example answer 2 because the minimal length of any possible B is 2 or because there are 2 such minima? Seems to be some conflict between "your task is to partition it into as few contiguous increasing subsequences as possible" vs "we have Q queries updating single value on A asking minimum number of type B(s) possible" \$\endgroup\$ Jan 27 '18 at 9:38
  • 1
    \$\begingroup\$ This challenge needs more test cases. I'd suggest [], [3], [1,2], [2,5], [2,6,3], [1,2,11,12,3,4,9,20,22,10,5,6,14,13]. \$\endgroup\$
    – Zgarb
    Jan 27 '18 at 13:42
1
\$\begingroup\$

Kotlin, 91 bytes

fold(mutableListOf<Int>()){r,i->r.indexOfFirst{it<i}.let{if(it<0)r+=i else r[it]=i
r}}.size

Beautified

fold(mutableListOf<Int>()) {r,i->
    r.indexOfFirst { it<i }.let {
        if (it<0) r+=i else r[it]=i
        r
    }
}.size

Test

fun MutableList<Int>.f() =
fold(mutableListOf<Int>()){r,i->r.indexOfFirst{it<i}.let{if(it<0)r+=i else r[it]=i
r}}.size

fun main(args: Array<String>) {
    val i = mutableListOf(1,2,3,4,3,5)
    println(i.f())
}

TIO

TryItOnline

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

JavaScript (ES6), 82 bytes

f=(a,n=Math.min(...a),i=a.indexOf(n))=>1/a[0]?i<0?1+f(a):f(a,a.splice(i,1)[0]+1):1
\$\endgroup\$
0
0
\$\begingroup\$

Haskell, 139 bytes

import Data.List
l=length
q(x:r)=map([x]:)(q r)++[(x:y):v|(y:v)<-q r]
q[]=[[]]
s(x:y)=x+l y==last(x:y)
f x=minimum[l y|y<-q x,all(s.sort)y]
\$\endgroup\$
0
\$\begingroup\$

Jelly, 9 bytes

Œ!Iċ€1ṀạL

Try it online!

How it works

Œ!Iċ€1ṀạL  Main link. Argument: A (array)

Œ!         Take all permutations of A.
  I        Increments; compute the forward differences of each permutation.
   ċ€1     Count the number of 1's i each array of deltas.
      Ṁ    Take the maximum.
        L  Compute the length of A.
       ạ   Take the absolute value of the difference of the maximum and the length.
\$\endgroup\$
6
  • \$\begingroup\$ I believe [1,2,8,3,4,3,5,7] should actually not return either 3 or 2 but 1 since there is only a single minimal length partition, [[1,2],[8],[3],[4,3,5],[7]], satisfying the criteria. (Either that or 5 since that's the minimal length) \$\endgroup\$ Jan 27 '18 at 14:08
  • \$\begingroup\$ That may have been what the OP was going for, but the latest revision clearly asks to indicate the smallest number of parts A can be splitted to. \$\endgroup\$
    – Dennis
    Jan 27 '18 at 14:11
  • \$\begingroup\$ Also, since [1,2,3,4,5],[3] appear as part of the worked example, reordering is clearly allowed. \$\endgroup\$
    – Dennis
    Jan 27 '18 at 14:12
  • \$\begingroup\$ Ah, hadn't updated since going out.... \$\endgroup\$ Jan 27 '18 at 14:13
  • \$\begingroup\$ It is not; it has been there since revision 1. By contiguous, the OP appears to mean that the partitions consist of consecutive integers, \$\endgroup\$
    – Dennis
    Jan 27 '18 at 14:17

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