16
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Is it ok if we output nothing instead of 0 for []? \$\endgroup\$ – wastl Mar 22 at 18:50
  • 8
    \$\begingroup\$ Isn’t it a bit early to accept an answer? \$\endgroup\$ – Nick Kennedy Mar 22 at 21:10
  • 7
    \$\begingroup\$ As @NickKennedy said, that's far, far too soon to be accepting a solution. Some even recommend never accepting a solution. \$\endgroup\$ – Shaggy Mar 22 at 23:41

26 Answers 26

2
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ What is the global areay? Is it empty on start of the program? \$\endgroup\$ – Embodiment of Ignorance Mar 22 at 23:09
  • \$\begingroup\$ @EmbodimentofIgnorance Yes, it's a single array to which I can add something, which I can push, and which I can clear. And it indeed starts empty initially. \$\endgroup\$ – Kevin Cruijssen Mar 23 at 8:59
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I was in the middle of commenting about using diff(s,lag=2) to detect proximity! Now you're a byte shorter than my solution... \$\endgroup\$ – Giuseppe Mar 22 at 19:51
  • \$\begingroup\$ Yeah, not giving up yet :) Now trying to get rid of some parentheses... \$\endgroup\$ – Kirill L. Mar 22 at 19:52
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 27 23 bytes

Fθ«W№✂υ±²¦¦¦ι⊞υω⊞υι»ILυ

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

Fθ«

Loop over the jobs.

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

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

⊞υι»

Add the current job to the result.

ILυ

Print the number of spots.

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ @Giuspeppe what does the c function do? \$\endgroup\$ – Embodiment of Ignorance Mar 22 at 22:50
  • \$\begingroup\$ @EmbodimentofIgnorance -- c stands for combine, although concatenate might be better; it combines its arguments into a single list. \$\endgroup\$ – Giuseppe Mar 22 at 23:01
  • \$\begingroup\$ Thanks, I thought it was weird that a language not designed for golfing would have one letter functions \$\endgroup\$ – Embodiment of Ignorance Mar 22 at 23:04
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Isn't this a snippet? \$\endgroup\$ – attinat Mar 28 at 22:43
1
\$\begingroup\$

Perl 5 -pl, 42 40 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Cut it down to 35 using -p and reworking the substitution: Try it online! \$\endgroup\$ – Xcali Mar 22 at 21:09
  • \$\begingroup\$ @Xcali That gives nothing for empty input, but I got to 39 \$\endgroup\$ – wastl Mar 22 at 21:31
  • 1
    \$\begingroup\$ Doesn't seem to work for 1,1,1. \$\endgroup\$ – nwellnhof Mar 23 at 15:01
  • \$\begingroup\$ @nwellnhof Fixed \$\endgroup\$ – wastl Mar 24 at 22:23
0
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ Fails for 3,4,3,4, should bet 5, not 6. \$\endgroup\$ – Kirill L. Mar 22 at 18:43
  • \$\begingroup\$ In addition to the xyxy fix @KirillL. noted, s = a can be s=a, and you can do s+= rather than multiple s=s+... and remove spaces after the ?: for i in 1...a.count-1{s+=a[i-1]==a[i] ?3:i>1&&a[i-2]==a[i] ?2:1} to save 9 bytes. \$\endgroup\$ – Daniel Widdis Mar 22 at 21:34
0
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ a[0]in b[:2]and f(a,['']+b)or f(a[1:],[a[0]]+b) can become f(*[a[1:],a,[a[0]]+b,['']+b][a[0]in b[:2]::2]) to save 2 bytes. \$\endgroup\$ – mypetlion Mar 22 at 17:59
  • 1
    \$\begingroup\$ [a[0]]+b can become a[:1]+b to save 1 byte. \$\endgroup\$ – mypetlion Mar 22 at 18:01
  • 1
    \$\begingroup\$ Replacing ['']+b with [b]+b saves a byte - b is a list, so it'll never be equal to any of the values in a \$\endgroup\$ – Sara J Mar 22 at 19:53
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Doesn't work for 3,4,3,4,3,4, returns 7 instead of 8 \$\endgroup\$ – Embodiment of Ignorance Mar 23 at 16:30
  • \$\begingroup\$ This is a wicked little problem. \$\endgroup\$ – Daniel Widdis Mar 23 at 17:03
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

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

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!

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

APL (Dyalog Classic), 22 bytes

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

Try it online!

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

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! This is a pretty great first post! \$\endgroup\$ – Rɪᴋᴇʀ Mar 25 at 23:45
0
\$\begingroup\$

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.

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

K (ngn/k), 27 bytes

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

Try it online!

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