25
\$\begingroup\$

xkcd: Scheduling Conflict

(I meant to post this while 1542: Scheduling Conflict was still the current xkcd, but I had a scheduling conflict.)

Input

The input will be a list of 3n elements, which represent n events. The first element in each group of 3 will be the name of an event; the second and third, the start and end time respectively. For example:

foo 12 34 bar 56 78

represents an event foo that starts at "time 12" (times are represented simply by integers; you can think of them as minutes past midnight) and ends at 34, and a second event bar that starts at 56 and ends at 78.

The names of events will always consist of only alphanumeric characters, and the times will always be integers ≥ 0 and < 1440. The end time will always be at least 1 greater than the start time. They are not guaranteed to be sorted in any way.

If you would like, you may take this as a single space-separated string; otherwise it should be taken as an array, list, vector, or your language's equivalent.

Output

The output should be a space-separated list of event names. The rules for which event names to output are as follows:

  • None of the events that you output may conflict with each other. For example, with the input a 0 10 b 5 15, you may not output both a and b because the times conflict (that is, partially overlap). If an event ends exactly as another one starts, you may include both.

  • You may not output the event called NSCC ("National Scheduling Conflict Competition"), of which there will always be exactly one of in the input. You also must output at least one event that conflicts (partially overlaps) with NSCC (and there will always be at least one of those as well).

  • You must output as many events as possible while following the above two rules. (This is so that you look as busy as possible, so that missing the NSCC seems more credible.)

This may also be output as either a single space-separated string or an array, list, vector, etc.

There can be more than one possible output.

Test cases

Note that the outputs listed are only examples. Your code may output something different, as long as it still follows the three rules above (notably, this means there must be the same amount of events as the example).

In: UnderwaterBasketWeavingConvention 50 800 NSCC 500 550
Out: UnderwaterBasketWeavingConvention

In: SconeEating 0 50 RegexSubbing 45 110 CodeGolfing 95 105 NSCC 100 200
Out: SconeEating CodeGolfing

In: VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775
Out: NerdSniping DoorknobTurning

In: NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500
Out: C D E

In: A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060
Out: A D E F G

In: A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16
Out: E

Feel free to add more test cases in an edit if there are edge-cases that I missed.

Rules

  • Your code must complete within 30 seconds for all of the provided test cases (this is more of a sanity check, as it should probably complete much faster for all the test cases combined) on a reasonable personal machine.

  • This is , so the shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Is it acceptable to use camelCase for events in inputs ? for instance using underwaterBasketWeavingConvention 50 800 nscc 550 instead of your example? \$\endgroup\$ – Fatalize Jun 27 '15 at 8:32
  • 4
    \$\begingroup\$ @Fatalize Not sure what you mean; the input is given exactly as it is shown. You should be able to support any combination of alphanumberic characters. \$\endgroup\$ – Doorknob Jun 27 '15 at 8:34
  • 4
    \$\begingroup\$ I'll have to work on a solution to this later; I have a scheduling conflict right now. \$\endgroup\$ – Alex A. Jun 27 '15 at 18:33
  • \$\begingroup\$ In the second example there are two spaces between "CodeGolfing" and "95" -- is this a mistake, or do we need to account for arbitrary numbers of spaces in the input? For right now, I'm going to assume the former, since you seem a little bit lenient on the format of the input. \$\endgroup\$ – vijrox Jun 28 '15 at 4:45
  • \$\begingroup\$ @VijayRamamurthy Yes, it is. Fixed. \$\endgroup\$ – Doorknob Jun 28 '15 at 10:07
9
\$\begingroup\$

Pyth, 45 bytes

AGH.gqhk"NSCC"m,hdrFtdcQ3hMef&.{KseMT@KehHtyG

This one was quite tough to golf. Found quite a few 45 byte solutions, this one is probably the most exotic one, since it uses A (pair-assign) and .g (group-by).

Try it online: Demonstration or Test harness

Explanation

                            implicit: Q = input list
                      cQ3   split Q into triples
              m             map each triple d to:
               ,              the pair containing
                hd              - d[0] (name)
                  rFtd          - range from start-time to end-time
   .g                       group these tuples k by:
     qhk"NSCC"                k[0] == "NSCC"
AGH                         pair assign to G,H. This assigns all
                            tuples != NSCC to G, and the NSCC one to H

                  yG        generate all subsets of G
                 t          remove the first one (the empty subset)
   f                        filter for subsets T, which satisfy:
         eMT                  get the last item (the range) for all tuples in T
        s                     and combine them (sum)
       K                      assign to K
     .{                       check for uniqueness of K (no overlapping times)
    &                         and
            @KehH             check the intersection of K and H[0][1]
  e                         take the last element (most events)
hM                          get the first item (name) for each event
                            and implicitly print this list
\$\endgroup\$
13
\$\begingroup\$

SWI-Prolog, 537 524 516 502 447 436 bytes

z(A:B:C,[D:E:F|G]):-(A=D;B>=F;E>=C),(G=[];z(A:B:C,G)).
u([A|B],C):-z(A,C),(B=[];u(B,C)).
y([A,B,C|D])-->[A:B:C],(y(D);{_=_}).
d-->[A:_],{write(A),tab(1)},d;{_=_}.
l([H|T],R):-T=[],R=H;length(H,N),l(T,X),length(X,M),(N>M,R=H;R=X).
v([],_,R,R).
v([A|T],Z,B,R):-u(A,A),\+z(Z,A),v(T,Z,[A|B],R);v(T,Z,B,R).
s([E|T],[F|N]):-E=F,(N=[];s(T,N));s(T,[F|N]).
x(A):-y(A,D,[]),K="NSCC":_,select(K,D,E),setof(L,s(E,L),B),v(B,K,[],R),l(R,S),d(S,[]),!.

Brief explanation of what each predicate does:

  • z(A,B) checks that an event A doesn't conflict with any event of a list of events B
  • u(A,B) checks that every event of a list A does not conflict with any event of a list B (used to check that there are no conflicts in list A by calling u(A,A))
  • y(A,B,C) splits a List into a list of triplets (to transform inputs into a list of events)
  • d(A) prints the names of events in a list A
  • l(A,R) evaluates the longest list of events R contained in the list of lists A
  • v(A,NSCC,C,R) returns a list R containing every list of events in A that have no internal conflict and that conflict with the event NSCC
  • s(A,B) true if B is a subset of A
  • x(A) main predicate, A is the input.

Test cases: execute test. in the interpreter after loading the code above with the following added after it:

test:-
    x(["UnderwaterBasketWeavingConvention",50,800,"NSCC",500,550]),
    nl,
    x(["SconeEating",0,50,"RegexSubbing",45,110,"CodeGolfing",95,105,"NSCC",100,200]),
    nl,
    x(["VelociraptorHunting",0,300,"NerdSniping",200,500,"SEChatting",400,700,"DoorknobTurning",650,750,"NSCC",725,775]),
    nl,
    x(["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]),
    nl,
    x(["A",800,900,"NSCC",700,1000,"B",650,750,"C",950,1050,"D",655,660,"E",660,665,"F",1030,1040,"G",1040,1060]),
    nl,
    x(["A",10,11,"B",11,12,"C",12,13,"D",13,14,"NSCC",15,1090,"E",10,16]).

This took me way more time than I thought it would. This can probably be golfed significantly more. Also you could probably use the various constraint programming libraries that exist to get shorter solutions.

Edit: Thanks to @Oliphaunt for the idea of using A:B:C instead of [A,B,C] for triplets. Saves 14 bytes.

Edit2: Thanks again to @Oliphaunt for pointing out that the predicate ``t/3`was useless. Saves 55 bytes

Edit3: Gained 11 bytes using definitive clause grammar on predicates y and d.

\$\endgroup\$
  • \$\begingroup\$ Love answers in Prolog! Nice one. \$\endgroup\$ – plocks Jun 27 '15 at 18:47
  • \$\begingroup\$ I'm a Prolog lover too. Suggestions: 1. I think you can use e.g. A/B/C instead of [A,B,C] for the triplets, saving 10 bytes; 2. Can you use \+ instead of not? 3. Could you explain why you need the final cut in x(A)? \$\endgroup\$ – Oliphaunt - reinstate Monica Jun 27 '15 at 21:22
  • \$\begingroup\$ I'll come back to you tomorrow, from my laptop. Right now in bed with the tablet which makes for clumsy typing and I should probably sleep anyway. :-) \$\endgroup\$ – Oliphaunt - reinstate Monica Jun 27 '15 at 21:37
  • 1
    \$\begingroup\$ Here is a version that saves 14 bytes. I used : instead of / to benefit from the former's right-associativity, i.e. so I could write A:_ as shorthand for A:_:_ (but A+B/C works just as well: you can then use A+_). By the way, also in your original you could've used [A|_] instead of [A,_,_]. Note finally that my version of SWI-Prolog didn't have nth0/4, so I used select/3 instead. \$\endgroup\$ – Oliphaunt - reinstate Monica Jun 28 '15 at 9:37
  • 1
    \$\begingroup\$ I wondered before about the need for t(S,T) but then forgot. Now tested: you can save 55 more bytes by dropping it entirely and directly calling s(E,L) from setof/3. \$\endgroup\$ – Oliphaunt - reinstate Monica Jun 28 '15 at 12:59
6
\$\begingroup\$

JavaScript (ES6), 228

Second try, I hope this one works.

My target is the longest sequence of events that has a timing conflict, but no timing conflict when the event NSCC is removed. This modified sequence with NSCC removed is the output requested.

I use a Breadth First Search examining a queue of candidate solutions, starting with longest (the first is the initial list). From a candidate solution of n events I build and enqueue n more candidate solutions, removing one of the events and keeping the others.

A candidate solution is valid if there is a timing conflict 'as is', but when the NSCC event is filtered out there is no conflict. I use a subfunction K to check for conflicts.

Probably could be golfed a little more...

Test running the snippet below (being EcmaScript 6, FireFox only)

F=l=>(K=>{
  l.map(v=>l.push(l.splice(0,3)));// I'm particularly proud of this trick for grouping in triplets (in pith it's "cQ3")
  for(S=[l.sort((a,b)=>a[1]-b[1])];!K(l=S.shift())|K(m=l.filter(x=>x[0]!='NSCC'));)
    l.map((v,i)=>(S.push(n=[...l]),n.splice(i,1)));
})(l=>l.some(x=>[p>+x[1],p=+x[2]][0],p=0))||m.map(x=>x[0])

// Less golfed and ES5

function Find(l) {
  var n,m;
  var Check = function(l) {
    // check timing conflict comparing start time and end time of previous event (events must be sorted)
    var p = 0 // previous event end time, init to 0
    return l.some( function(x) {
      var err = p > +x[1]; // unary plus convert string to number
      p = +x[2]; // update end time
      return err;
    });  
  };  
  // group initial array in triplets
  // forEach repeats for the initial number of elements in l, even if l becomes shorter
  // so it loops more times than necesary, but it works anymay
  l.forEach(function() { 
    l.push(l.splice(0,3)); // remove first 3 elements and add to back as a triple
  }) 
  l.sort(function(a,b) { return a[1]-b[1]} ); // sort by start time
  var S=[l]; // S is the main queue, start with complete list 
  
  while (l = S.shift(), // current list
         m = l.filter( function(x) { return x[0]!='NSCC'} ), // current list with NSCC removed
         !Check(l)|Check(m)) // loop while list ha no errors or filtered list do have errors
  {
    // build new candidate to check
    l.forEach ( function(v,i) {
      n = l.slice(); // make a copy of l
      n.splice(i,1); // remove ith element
      S.push(n); // put in S
    });  
  }
  // when exiting while, m has the list with NSCC removed
  return m.map( function(x) { return x[0]; }); // keep the event name only
}

// Test

out=(...x)=>O.innerHTML += x + '\n';

test=[
  ['UnderwaterBasketWeavingConvention 50 800 NSCC 500 550','UnderwaterBasketWeavingConvention']
, ['SconeEating 0 50 RegexSubbing 45 110 CodeGolfing  95 105 NSCC 100 200','SconeEating CodeGolfing']
, ['VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775'
  ,'NerdSniping DoorknobTurning']
, ['NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500','C D E']
, ['A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060','A D E F G']
, ['A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16','E']
]


test.forEach(x=>{
  var l=x[0].split(/\s+/), r=F(l).sort().join(' '), e=x[1].split(/\s+/).sort().join(' ');
  out('Test ' + (r==e ? 'OK':'FAIL')+'\nInput:    '+x[0]+'\nResult:   '+r+'\nExpected: '+e)
} )
<pre id=O></pre>

\$\endgroup\$
  • 3
    \$\begingroup\$ May I ask the point of a Stack Snippet if the program doesn't do anything if you don't call the function? \$\endgroup\$ – Beta Decay Jun 27 '15 at 22:36
  • 1
    \$\begingroup\$ @BetaDecay: edc65 usually adds test cases that run in the snippet. Sounds like he'll be returning to this answer soon, at which time I assume he'll add the runnable stuff. :) \$\endgroup\$ – Alex A. Jun 27 '15 at 22:58
  • 1
    \$\begingroup\$ @BetaDecay Was in a hurry. And (worse yet) it fails one of the test. \$\endgroup\$ – edc65 Jun 27 '15 at 23:55
1
\$\begingroup\$

Java, 828 bytes

There's probably a more concise Java implementation out there, but here's my stab:

String s(String e){String[] a=e.split(" ");String m="";String[] c=g(a.length/3);int l=0;for(int i=0;i<a.length;i+=3)if(a[i].equals("NSCC"))l=i/3;for(String p:c)if(p.indexOf(l+"")==-1&&!h(p,a)&&h(p+l,a)&&p.length()>m.length())m=p;String r="";for(int i=0;i<m.length();i++)r+=a[3*(m.charAt(i)-48)]+((i==m.length()-1)?"":" ");return r;}boolean h(String c, String[] e){for(int i=0;i<c.length()-1;i++){int p=c.charAt(i)-48;for(int j=i+1;j<c.length();j++){int q=c.charAt(j)-48;if((Integer.parseInt(e[3*p+1])-Integer.parseInt(e[3*q+2]))*((Integer.parseInt(e[3*p+2])-Integer.parseInt(e[3*q+1])))<0)return true;}}return false;}String[] g(int n){if(n>1){String[] result=new String[(int)Math.pow(2,n)];String[] l=g(n-1);for(int i=0;i<l.length;i++){result[2*i]=l[i];result[2*i+1]=l[i]+(n-1);}return result;}else return new String[]{"","0"};}
\$\endgroup\$
  • \$\begingroup\$ Declaring all variables in one place will save bytes. \$\endgroup\$ – Spikatrix Jun 28 '15 at 6:05
  • \$\begingroup\$ You don't need to else return. \$\endgroup\$ – lirtosiast Jul 1 '15 at 1:39
0
\$\begingroup\$

Python, 373 characters

import itertools as j
a=zip(*[iter(input())]*3)
f,g,r=[],0,"NSCC"
p=f
for q in a:
 p=(p,q)[q[0]==r]
for h in range(1,len(a)+1):
 for i in j.combinations(a,h):
  s,i,l,m=0,sorted(i,key=lambda k:int(k[1])),-1,len(i)
  for n in i:
   s=(s,1)[p[1]<n[2]or p[2]<n[1]]
   if r==n[0]or n[1]<l:
    m=-1
    break
   else:
    l=n[2]
  if s*m>g:
   g,f=m,i
for o in f:
 print o[0]

Creates all possible combinations and checks each one.

Test

Input: ["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]

Output:

D
C
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.