THINK FIRST·CODE LATER

← All labs

Properties as oracles: check an AI's slot merger

Problem

An AI wrote mergeSlots, which merges a student's free-time slots on one day. You do not trust it, but you also do not want to compute every expected answer by hand. Instead, check properties that any correct output must have.

Times are minutes since midnight; a slot is start-end with start < end. Slots that overlap or touch (e.g., 600-660 and 660-720) must be merged.

Input: pairs of lines until the end of input: the input slots, then the claimed output of the AI, each as space-separated start-end items (a line may be - for an empty list).

For each pair (numbered from 1) check, in this order, and report all violated properties:

  1. NOT_SORTED — output starts are not strictly increasing;
  2. OVERLAP_OR_TOUCH — some output slot starts at or before the end of the previous one;
  3. COVERAGE — the set of minutes covered by the output differs from the set covered by the input (minute m is covered by slot s-e if s <= m < e).

Print Case k: OK or Case k: FAIL (P1, P2...). Finally print Passed: x/n.

Input:

600-660 630-700
600-700
600-660 660-720
600-660 660-720
540-600 480-500
480-500 540-610

Output:

Case 1: OK
Case 2: FAIL (OVERLAP_OR_TOUCH)
Case 3: FAIL (COVERAGE)
Passed: 1/3

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

s9-2-data-1.txt

600-660 630-700
600-700
600-660 660-720
600-660 660-720
540-600 480-500
480-500 540-610
What your program must print for s9-2-data-1.txt
Case 1: OK
Case 2: FAIL (OVERLAP_OR_TOUCH)
Case 3: FAIL (COVERAGE)
Passed: 1/3

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < s9-2-data-1.txt

Windows PowerShell does not understand <:

Get-Content s9-2-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.