Calculating total slots

Question

Given a list of jobs, which must be done in order, with each taking a slot to do, how long will it take to perform them all if after doing a job the same job cannot be done for the next two slots (cooling off slots)? However, a different job can be assigned in this cooling off slots.

For example,

[9,10,9,8] => output: 5

Because jobs will be allocated as [9 10 _ 9 8].
1. First, 9 needs two cooling off spots _ _. So we start with 9 _ _.
2. Next job 10 is different from the previous job 9, so we can allocate one of _ _. Then we will have 9 10 _.
3. Third, 9 cannot be allocated now, since first job 9 is the same job and it needs cooling off time. 9 10 _ 9.
4. Last, 8 is not same as any other previous two jobs, so it can be allocated right after 9 and since this is last job, it does not need cooling off time. Final list is 9 10 _ 9 8 and expected output is 5, which is the number of spots (or number of slots)

Test cases:

[1,2,3,4,5,6,7,8,9,10] => output : 10 ([1 2 3 4 5 6 7 8 9 10])
[1,1,1] => output: 7 ([1 _ _ 1 _ _ 1])
[3,4,4,3] => output: 6 ([3 4 _ _ 4 3])
[3,4,5,3] => output: 4 ([3 4 5 3])
[3,4,3,4] => output : 5 ([3 4 _ 3 4])
[3,3,4,4] => output : 8 ([3 _ _ 3 4 _ _ 4])
[3,3,4,3] => output : 7 ([3 _ _ 3 4 _ 3])
[3,2,1,3,-4] => output : 5 ([3 2 1 3 -4])
[] => output : 0 ([])
[-1,-1] => output : 4 ([-1 _ _ -1])

Input value can be any integer (negative, 0, positive). Length of job-list is 0 <= length <= 1,000,000.
Output will be an integer, the total number of slots, which is indicated in test case as output. The list inside the parenthesis is how the output would be generated.

Winning criterion
code-golf

Answer 1

05AB1E, 22 bytes

v¯R¬yQiõˆ}2£yåiˆ}yˆ}¯g

Try it online or verify all test cases.

Explanation:

v           # Loop over the integers `y` of the (implicit) input-list:
 ¯R         #  Push the global_array, and reverse it
   ¬        #  Get the first item (without popping the reversed global_array itself)
    yQi  }  #  If it's equal to the integer `y`:
       õˆ   #   Add an empty string to the global_array
   2£       #  Then only leave the first 2 items of the reversed global_array
     yåi }  #  If the integer `y` is in these first 2 items:
        ˆ   #   Add the (implicit) input-list to the global_array
 yˆ         #  And push the integer `y` itself to the global_array
}¯g         # After the loop: push the global array, and then pop and push its length
            # (which is output implicitly as result)

Answer 2

Brachylog, 10 bytes

It's always nice to see problem where Brachylog performs best

⊆Is₃ᶠ≠ᵐ∧Il

Explanation

⊆I           # Find the minimal ordered superset of the input (and store in I) where:
   s₃ᶠ       #     each substring of length 3
      ≠ᵐ     #     has only distinct numbers
        ∧Il  # and output the length of that superset

Try it online!

Answer 3

R, 74 68 bytes

length(Reduce(function(x,y)c(y,rep("",match(y,x[2:1],0)),x),scan()))

Try it online!

Constructs the work array (in reverse), then takes the length. Just a bit shorter longer than Kirill L.'s answer, so sometimes, the naive approach is pretty good. EDIT: shorter again! I also borrowed Kirill's test template.

-6 bytes replacing max(0,which(y==x[2:1])) with match(y,x,0).

Answer 4

Jelly, 14 bytes

ṫ-i⁹⁶ẋ⁸;;µƒ⁶L’

Try it online!

Answer 5

R, 123 bytes

`-`=nchar;x=scan(,'');while(x!=(y=gsub("([^,]+),(([^,]*,){0,1})\\1(,|$)","\\1,\\2,\\1\\4",x)))x=y;-gsub("[^,]","",y)+(-y>1)

Try it online - single program!

Try it online - multiple examples!

A full program that reads a comma-separated list of integers as the input, and outputs the slots needed. I’m sure this could be golfed some more, and implementing this regex-based solution in some other languages would be more efficient in bytes.

Note on the second TIO I’ve wrapped it in a function to permit multiple examples to be shown. This function also shows the final list, but this is not output my the main program if run in isolation.

Answer 6

TSQL query, 158 bytes

Input data as a table.

The query is recursive so

OPTION(MAXRECURSION 0)

is necessary, because the list of numbers can exceed 100 although it can only go handle 32,767 recursions - is the limitation really needed in this task ?

DECLARE @ table(a int, r int identity(1,1))
INSERT @ VALUES(3),(3),(4),(4);

WITH k as(SELECT null b,null c,1p
UNION ALL
SELECT iif(a in(b,c),null,a),b,p+iif(a in(b,c),0,1)FROM @,k
WHERE p=r)SELECT sum(1)-1FROM k
OPTION(MAXRECURSION 0) 

Try it online

Answer 7

Python 2, 67 bytes

r=[]
for x in input():
 while x in r[-2:]:r+=r,
 r+=x,
print len(r)

Try it online!

Implements the challenge pretty literally. Uses copies of the list itself as "blanks", since these can't equal any number.

Answer 8

Charcoal, 27 23 bytes

Ｆθ«Ｗ№✂υ±²¦¦¦ι⊞υω⊞υι»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:

Ｆθ«

Loop over the jobs.

Ｗ№✂υ±²¦¦¦ι⊞υω

Add cooling off spots while the job is one of the last two in the result.

⊞υι»

Add the current job to the result.

ＩＬυ

Print the number of spots.

Answer 9

Perl 6, 98 bytes

{($!=$,|$_ Z$_ Z .[1..*+1])>>.repeated.squish(:with({$+^=[*] $! ne$^a ne$^b,$b==($!=$a)})).sum+$_}

Try it online!

Blergh, there's got to be a better way of doing this. I'm not 100% sure this is fully correct, though it passes all the edge cases I could think of.

Basically, this starts by grouping all the triplets of the input list, with padding to either side. For example, [1,2,1,2] becomes (Any,1,2), (1,2,1), (2,1,2), (1,2,Nil). We get the repeated elements in each triplet, becoming (), (1), (2), ().

It then squishes consecutive elements that are not the same list, but are the same size (to not squish something like [1,1,1]), and the first element is not equal to the element before it (because we can't merge the hours in [1,1,2,2]), and finally the element before hasn't also been squished ([1,2,1,2,1,2]). So (1), (2) in the above example above would be squished together.

Finally, we get the sum of all lengths of this list, which represent our inserted hours, and add the length of the original list.

For example:

(1,1,1) => (Any,1,1),(1,1,1),(1,1,Nil) => (1),(1,1),(1) => (no squishes) => 4+3 = 7
(1,2,1,2,1,2) => (Any,1,2), (1,2,1), (2,1,2), (1,2,1), (2,1,2), (1,2,Nil) => (),(1),(2),(1),(2),() => squish (1),(2) and (1),(2) => 2+6 = 8

Answer 10

JavaScript (ES6), 57 bytes

f=([x,...a],p,q)=>1/x?1+f(x!=p&x!=q?a:[x,...a,x=f],x,p):0

Try it online!

Commented

f = (             // f is a recursive function taking:
  [x,             //   x   = next job
      ...a],      //   a[] = array of remaining jobs
  p,              //   p   = previous job, initially undefined
  q               //   q   = penultimate job, initially undefined
) =>              //
  1 / x ?         // if x is defined and numeric:
    1 +           //   add 1 to the grand total
    f(            //   and do a recursive call to f:
      x != p &    //     if x is different from the previous job
      x != q ?    //     and different from the penultimate job:
        a         //       just pass the remaining jobs
      :           //     else:
        [ x,      //       pass x, which can't be assigned yet
          ...a,   //       pass the remaining jobs
          x = f   //       set x to a non-numeric value
        ],        //
      x,          //     previous job = x
      p           //     penultimate job = previous job
    )             //   end of recursive call
  :               // else:
    0             //   stop recursion

Answer 11

R, 81 70 bytes

sum(l<-rle(s<-scan())$l*3-3,1-l%/%6,((r=rle(diff(s,2)))$l+1)%/%2*!r$v)

Try it online!

After several unsuccessful attempts, the code turned rather ugly and not so short, but at least it works now...

First, we evaluate the lengths of consecutive runs of the same job. E.g. for 3, 3, 4, 3 this gives:

Run Length Encoding
  lengths: int [1:3] 2 1 1
  values : num [1:3] 3 4 3

Each of these runs produces (len - 1) * 3 + 1 steps (+ 1 is handled separately).

Next, we process occurrences of the same job 2 places apart, like: x, y, x, by using diff(s, lag=2). The resulting vector is also chunked into consecutive runs (r) by rle function. Now, because of various interleaved alternations we need to add ceiling(r$len/2) steps for all runs of zeroes. E.g.:

x y x (length 1) and x y x y (length 2) both need 1 extra step: x y _ x (y)

x y x y x (length 3) and x y x y x y (length 4) both need 2 extra steps: x y _ x y _ x (y)

Finally, we need to compensate for occurrences of these alternations in the middle of a long run of the same job: x, x, x, x..., hence 1-l%/%6 instead of simply 1.

Answer 12

C (gcc), 69 bytes

f(j,l)int*j;{j=l>1?(*j-*++j?j[-1]==j[l>2]?j++,l--,3:1:3)+f(j,l-1):l;}

Try it online!

Straightforward recursion.

f(j,l)int*j;{               //Jobs, (array) Length
    j=l>1                   //if l > 1, do a recursion:
        ? (*j-*++j          // check if first and second elements are equal (j++)
            ? j[-1]==       //  1st!=2nd; check if first and third are equal
                j[l>2]      //  (first and second if l==2, but we already know 1st!=2nd)
                ? j++,l--,3 //   1st==3rd (j++,l--) return 3+f(j+2,l-2)
                : 1         //   1st!=3rd (or l==2) return 1+f(j+1,l-1)
            : 3             //  1st==2nd            return 3+f(j+1,l-1)
          )+f(j,l-1)        // j and l were modified as needed
        : l;                // nothing more needed  return l
}

Answer 13

Perl 6, 48 bytes

{$!=0;.map:{{$_=($!=$!+1 max$_)+3}((%){$_})};$!}

Try it online!

45 bytes if the list has at least two elements:

+*.reduce:{$^b,|(*xx 3-(|$^a,*,$b...$b)),|$a}

Try it online!

Answer 14

Smalltalk, 125 bytes

c:=0.n:=q size.1to:n-2do:[:i|(j:=q at:i)=(k:=q at:i+1)ifTrue:[c:=c+2].j=(m:=q at:i+2)ifTrue:[c:=c+1]].k=m ifTrue:[c:=c+1].c+n

Explanation

c : accumulator of proximity penalty
q : input array.
n := q length
i : iteration index from 1 to: n-2 (arrays are 1-based in Smalltalk).
j := memory for element i, saves some few bytes when reused
k := similar to j but for i+1.
m := similar to k but for i+2.

Answer 15

Perl 5 -pl, 42 40 bytes

$a{$_}=~s/.*/$\=$&if++$\<$&;$\+3/e}{$_=0

Try it online!

Answer 16

Batch, 184 bytes

@echo off
@set l=-
@set p=-
@set n=0
@for %%j in (%*)do @call:c %%j
@exit/b%n%
:c
@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1
@set p=%l%&set l=%1&set/an+=1

Input is via command-line arguments and output is via exit code. Explanation:

@set l=-
@set p=-

Track the last two jobs.

@set n=0

Initialise the count.

@for %%j in (%*)do @call:c %%j

Process each job.

@exit/b%n%

Output the final count.

:c

For each job:

@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1

If we processed the job recently, add in an appropriate number of cooling off spots. Additionally, clear the last job so that the next job only triggers cooling off if it's the same as this job.

@set p=%l%&set l=%1&set/an+=1

Update the last two jobs and allocate a spot to this job.

Answer 17

Swift, 114 bytes

func t(a:[Int]){
var s=1
for i in 1...a.count-1{s = a[i-1]==a[i] ? s+3:i>1&&a[i-2]==a[i] ? s+2:s+1}
print("\(s)")}

Try it online!

Answer 18

Python 3, 79 75 bytes

-3 bytes thanks to mypetlion
-1 byte thanks to Sara J

f=lambda a,b=[]:a and f(*[a[1:],a,a[:1]+b,[b]+b][a[0]in b[:2]::2])or len(b)

Try it online!

Answer 19

Java (JDK), 110 bytes

j->{int p,q;for(p=q=j.length;p-->1;q+=j[p]==j[p-1]?2:(p>1&&j[p]==j[p-2]&(p<3||j[p-1]!=j[p-3]))?1:0);return q;}

Try it online!

Ungolfed commented code:

j -> {
    int p, q = j.length; // Run all jobs
    for (p = q; p-- > 1;) { // reverse iterate
        q += j[p] == j[p - 1] ? 2 : // add 2 if prev same
        (p > 1 && j[p] == j[p - 2] & // 1 if 2prev same
        (p < 3 || j[p - 1] != j[p - 3]) // except already done
        ) ? 1 : 0; // otherwise 0
    }
    return q;
}

Answer 20

Jelly, 20 bytes

ṫ-i⁹⁶x;
⁶;ç³Ṫ¤¥¥³¿L’

Try it online!

Although this is rather similar to @EriktheOutgolfer’s shorter answer, I wrote it without seeing his. In any case his is better!

Explanation

Helper dyadic link, takes current list as left item and next item as right

ṫ-            | take the last two items in the list
  i⁹          | find the index of the new item
    ⁶x        | that many space characters
      ;       | prepend to new item

Main monadic link, takes list of integers as input

⁶             | start with a single space
 ;            | append...
  ç³Ṫ¤¥       | the helper link called with the current list
              | as left item and the next input item as right
       ¥³¿    | loop the last two as a dyad until the input is empty
          L   | take the length
           ’  | subtract one for the original space

Answer 21

Python 2, 75 bytes

lambda a:len(reduce(lambda b,c:b+[c]*-~((c in b[-2:])+(c in b[-1:])),a,[]))

Try it online!

Answer 22

JavaScript (Node.js), 52 bytes

(a,i=0,h={})=>a.map(n=>h[n]=3+(i=h[n]>++i?h[n]:i))|i

Try it online!

Answer 23

APL (Dyalog Classic), 22 bytes

≢∊(⊢,⍨⊣,# #↓⍨⍳⍨)/⍵,⊂⍬⍬

Try it online!

Answer 24

JavaScript (V8), 101 bytes

f=a=>for(var c=0,i=0;i<a.length;i++,c++)a[i-1]==a[i]?c+=2:a[i-2]==a[i]&&(c++,a[i-1]=void 0)
return c}

Try it online!

Unpacked code looks as follows:

function f(a)
{
    var c = 0;
    for (var i = 0; i < a.length; i++, c++)
    {
        if (a[i - 1] == a[i])
            c+=2;
        else if (a[i - 2] == a[i])
            c++,a[i-1]=undefined;
    }

    return c;
}

My first ever code-golf attempt, can probably be optimized a lot by shrinking the array and passing it recursively.

Answer 25

Zsh, 66 60 bytes

-6 bytes from implicit "$@"

for j
{((i=$a[(I)$j]))&&a=
a=("$a[-1]" $j)
((x+=i+1))}
<<<$x

Try it online! I highly recommend adding set -x to the start so you can follow along.

for j                   # Implicit "$@"
{                       # Use '{' '}' instead of 'do' 'done'
    (( i=$a[(I)$j] )) \ # (see below)
        && a=           # if the previous returned true, empty a
    a=( "$a[-1]" $j )   # set the array to its last element and the new job
    (( x += i + 1 ))    # add number of slots we advanced
}
<<<$x                   # echo back our total

((i=$a[(I)$j]))
    $a[     ]           # Array lookup
       (I)$j            # Get highest index matched by $j, or 0 if not found
  i=                    # Set to i
((           ))         # If i was set nonzero, return true

a always contains the last two jobs, so if the lookup finds a matching job in a[2], we increment by three (since the job slots will be [... 3 _ _ 3 ...]).

If a is unset, the lookup will fail and the arithmetic expansion will return an error, but that only happens on the first job and isn't fatal.

We can save one more byte if we use $[x+=i+1] instead, and there are no commands on the users system comprised entirely of digits.

Answer 26

K (ngn/k), 27 bytes

{#2_``{y,#[0|2-x?y;`],x}/x}

Try it online!