A
\r\n
), LF (\n
) or CR (\r
).\r\n
), LF (\n
) or CR (\r
) visually;#include <stdio.h>
#include <stdlib.h>
#include <X11/Xlib.h>
int main( void )
{
Display *display;
Window parent, window;
int screen;
Colormap cmap;
unsigned long plane_mask, pixels[2];
int border, background;
display = XOpenDisplay( "" );
if ( !display ) {
fprintf( stderr, "XOpenDisplay error\n" );
exit( 1 );
}
screen = DefaultScreen( display );
parent = RootWindow( display, screen );
cmap = DefaultColormap( display, screen );
if ( !XAllocColorCells( display, cmap, False,
&plane_mask, 0, pixels, 2 ) ) {
fprintf( stderr, "XAllocColorCells error\n" );
exit( 1 );
}
getchar();
}
timetable.xml
<?xml version="1.0" encoding="UTF-8"?>
<university>
<lectures>
<lecture>
<id>l-0</id>
<name>Calculus 101</name>
<roombookings>
<booking>
<room>Audimax</room>
<weekday>Mon</weekday>
<startTime>10:00:00</startTime>
<endTime>12:00:00</endTime>
</booking>
<booking>
<room>Audimax</room>
<weekday>Wed</weekday>
<startTime>10:00:00</startTime>
<endTime>14:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-1</id>
<name>Counting 101</name>
<roombookings>
<booking>
<room>Audimax</room>
<weekday>Mon</weekday>
<startTime>15:00:00</startTime>
<endTime>17:00:00</endTime>
</booking>
<booking>
<room>Audimax</room>
<weekday>Fri</weekday>
<startTime>10:00:00</startTime>
<endTime>12:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-2</id>
<name>Tricky Problems 101</name>
<roombookings>
<booking>
<room>Room A</room>
<weekday>Tue</weekday>
<startTime>09:00:00</startTime>
<endTime>11:00:00</endTime>
</booking>
<booking>
<room>Room B</room>
<weekday>Thur</weekday>
<startTime>10:00:00</startTime>
<endTime>12:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-3</id>
<name>Timetabling 101</name>
<roombookings>
<booking>
<room>Room B</room>
<weekday>Thur</weekday>
<startTime>14:00:00</startTime>
<endTime>17:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-4</id>
<name>Computer Stuff 101</name>
<roombookings>
<booking>
<room>Room A</room>
<weekday>Tue</weekday>
<startTime>12:00:00</startTime>
<endTime>14:00:00</endTime>
</booking>
<booking>
<room>Room B</room>
<weekday>Wed</weekday>
<startTime>16:00:00</startTime>
<endTime>19:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-5</id>
<name>Cool Numbers 101</name>
<roombookings>
<booking>
<room>Room A</room>
<weekday>Thur</weekday>
<startTime>08:00:00</startTime>
<endTime>12:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-6</id>
<name>Quantum Leaps 101</name>
<roombookings>
<booking>
<room>Room A</room>
<weekday>Mon</weekday>
<startTime>14:00:00</startTime>
<endTime>18:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-7</id>
<name>Tiny Stuff 101</name>
<roombookings>
<booking>
<room>Room A</room>
<weekday>Tue</weekday>
<startTime>10:00:00</startTime>
<endTime>13:00:00</endTime>
</booking>
<booking>
<room>Room B</room>
<weekday>Fri</weekday>
<startTime>11:00:00</startTime>
<endTime>13:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-8</id>
<name>Big Stuff 101</name>
<roombookings>
<booking>
<room>Room B</room>
<weekday>Tue</weekday>
<startTime>13:00:00</startTime>
<endTime>15:00:00</endTime>
</booking>
<booking>
<room>Room B</room>
<weekday>Wed</weekday>
<startTime>16:00:00</startTime>
<endTime>18:00:00</endTime>
</booking>
</roombookings>
</lecture>
<lecture>
<id>l-9</id>
<name>Stars and Stuff 101</name>
<roombookings>
<booking>
<room>Room B</room>
<weekday>Wed</weekday>
<startTime>15:00:00</startTime>
<endTime>17:00:00</endTime>
</booking>
</roombookings>
</lecture>
</lectures>
<curricula>
<curriculum>
<name>Maths</name>
<lecture>l-0</lecture>
<lecture>l-1</lecture>
<lecture>l-2</lecture>
<lecture>l-3</lecture>
<lecture>l-4</lecture>
<lecture>l-5</lecture>
</curriculum>
<curriculum>
<name>Physics</name>
<lecture>l-0</lecture>
<lecture>l-1</lecture>
<lecture>l-6</lecture>
<lecture>l-7</lecture>
<lecture>l-8</lecture>
<lecture>l-9</lecture>
</curriculum>
</curricula>
</university>
public class MathplanApplication {
private static String ROOMCONFLICT_MSG = """
Course with ID %s and course with ID %s have a room conflict for room %s %n""";
private static String SubjectCONFLICT_MSG = """
Course with ID %s and course with ID %s have a program conflict for program %s
""";
public static void main(String[] args) throws FileNotFoundException {
SpringApplication.run(MathplanApplication.class, args);
try {
List<ClassBooking> cbList =
UniversityFileParser.parseUniversityFile(
"./src/main/resources/timetable.xml");
ScheduleConflictDiscovery.findSchedulingConflicts(cbList);
resultPresentation();
} catch (Exception e) {
e.printStackTrace();
}
}
private static void resultPresentation() {
if(!ScheduleConflictDiscovery.getRoomConflicts().isEmpty()) {
System.out.printf("There were %d room conflicts discovered: %n",
ScheduleConflictDiscovery.getRoomConflicts().size());
}
ScheduleConflictDiscovery.getRoomConflicts().forEach(
st -> printRoomConflict(st));
if(!ScheduleConflictDiscovery.getRoomConflicts().isEmpty()) {
System.out.printf("%nThere were %d program conflicts discovered: %n",
ScheduleConflictDiscovery.getProgramConflicts().size());
}
ScheduleConflictDiscovery.getProgramConflicts().forEach(
st -> printProgramConflict(st));
}
private static void printRoomConflict(Set<ClassBooking> st) {
String[] ids = new String[2];
String room = null;
int counter = 0;
for(ClassBooking cb: st) {
ids[counter] = cb.getId();
room = cb.getRoom();
counter++;
}
System.out.printf(ROOMCONFLICT_MSG, ids[0], ids[1], room);
}
private static void printProgramConflict(Set<ClassBooking> st) {
ClassBooking[] cbs = new ClassBooking[2];
int counter = 0;
for(ClassBooking cb: st) {
cbs[counter] = cb;
counter++;
}
cbs[0].getInCurriculum().retainAll(cbs[1].getInCurriculum());
String degree = cbs[0].getInCurriculum().stream().findFirst().get();
System.out.printf(SubjectCONFLICT_MSG, cbs[0].getId(), cbs[1].getId(), degree);
}
}
private String id;
private String room;
private DayOfWeek weekday;
private LocalTime beginTime;
private LocalTime endTime;
private Set<String> inCurriculum;
public ClassBooking(String id, String room, DayOfWeek weekday,
LocalTime beginTime, LocalTime endTime, Set<String> inCurriculum) {
super();
this.id = id;
this.room = room;
this.weekday = weekday;
this.beginTime = beginTime;
this.endTime = endTime;
this.inCurriculum = inCurriculum;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getRoom() {
return room;
}
public void setRoom(String room) {
this.room = room;
}
public DayOfWeek getWeekday() {
return weekday;
}
public void setWeekday(DayOfWeek weekday) {
this.weekday = weekday;
}
public LocalTime getBeginTime() {
return beginTime;
}
public void setBeginTime(LocalTime beginTime) {
this.beginTime = beginTime;
}
public LocalTime getEndTime() {
return endTime;
}
public void setEndTime(LocalTime endTime) {
this.endTime = endTime;
}
public Set<String> getInCurriculum() {
return inCurriculum;
}
public void setInCurriculum(Set<String> inCurriculum) {
this.inCurriculum = inCurriculum;
}
@Override
public int hashCode() {
return Objects.hash(beginTime, endTime, id, inCurriculum, room, weekday);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
ClassBooking other = (ClassBooking) obj;
return Objects.equals(beginTime, other.beginTime) && Objects.equals(endTime, other.endTime)
&& Objects.equals(id, other.id) && Objects.equals(inCurriculum, other.inCurriculum)
&& Objects.equals(room, other.room) && weekday == other.weekday;
}
@Override
public String toString() {
return "ClassBooking [id=" + id + ", room=" + room + ", weekday=" + weekday + ", beginTime=" + beginTime
+ ", endTime=" + endTime + ", inCurriculum=" + inCurriculum + "]";
}
}
public class UniversityFileParser {
private static JAXBContext jaxbContext;
private static Map<String,List<String>> curriculumMap = new HashMap<>();
private UniversityFileParser() throws JAXBException {
jaxbContext = JAXBContext.newInstance(University.class);
}
public static List<ClassBooking> parseUniversityFile(String fileURL)
throws FileNotFoundException, JAXBException {
University university = (University) JAXBIntrospector.getValue(
jaxbContext.createUnmarshaller().unmarshal(new FileReader(fileURL)));
parseCurriculum(university);
return parseLectures(university);
}
private static List<ClassBooking> parseLectures(University university) {
List<List<ClassBooking>> fuck = university.getLectures().getLecture()
.stream().map(lecture -> parseBookings(lecture.getId(),
lecture.getRoombookings())).toList();
return fuck.stream().flatMap(Collection::stream).toList();
}
private static List<ClassBooking> parseBookings(String id,
Roombookings roomBookings) {
List<ClassBooking> classBookings = new ArrayList<>();
for(Booking b: roomBookings.getBooking()) {
ClassBooking cb = new ClassBooking(id,b.getRoom(),
getWeekday(b.getWeekday()),
LocalTime.of(b.getStartTime().getHour(), 0),
LocalTime.of(b.getEndTime().getHour(), 0),
addPrograms(id));
classBookings.add(cb);
}
return classBookings;
}
private static void parseCurriculum(University university) {
for(Curriculum curr: university.getCurricula().getCurriculum()){
List<Lecture> newCurriculum =
curr.getLecture().stream().map(entry -> (Lecture) entry.getValue())
.toList();
List<String> newCurriculumString = newCurriculum.stream().
map(Lecture::getId).toList();
System.out.println(newCurriculumString);
curriculumMap.put(curr.getName(), newCurriculumString);
}
}
private static Set<String> addPrograms(String courseID) {
Set<String> programSet = new HashSet<>();
for(String degree: curriculumMap.keySet()) {
if(curriculumMap.get(degree).contains(courseID)) {
programSet.add(degree);
}
}
return programSet;
}
//I can't change it because JAXB delivers them to me with three letters
private static DayOfWeek getWeekday(String weekday) {
switch(weekday) {
case("Mon"):
return DayOfWeek.MONDAY;
case("Tue"):
return DayOfWeek.TUESDAY;
case("Wed"):
return DayOfWeek.WEDNESDAY;
case("Thur"):
return DayOfWeek.THURSDAY;
case("Fri"):
return DayOfWeek.FRIDAY;
default:
return null;
}
}
}```
```public class ScheduleConflictDiscovery {
private static Set<Set<ClassBooking>> roomConflicts;
private static List<Set<ClassBooking>> programConflicts;
public static void findSchedulingConflicts(List<ClassBooking> cbList) {
roomConflicts = new HashSet<>();
programConflicts = new ArrayList<>();
for(int i = 0;i<cbList.size();i++) {
ClassBooking currCB = cbList.get(i);
List<ClassBooking> overlaps = IntStream.range(i+1, cbList.size()).filter(j -> hasOverLap(currCB, cbList.get(j))).mapToObj(k -> cbList.get(k)).toList();
findConflicts(currCB, overlaps);
}
roomConflicts.forEach(x -> System.out.println(x));
}
public static void findConflicts(ClassBooking currentCB, List<ClassBooking> overlaps) {
for(ClassBooking cb: overlaps) {
if(currentCB.getRoom().equals(cb.getRoom())) {
Set<ClassBooking> cbSet = Set.of(currentCB, cb);
roomConflicts.add(cbSet);
}
Set<String> copy = new HashSet<>(currentCB.getInCurriculum());
copy.retainAll(cb.getInCurriculum());
if(!copy.isEmpty()) {
Set<ClassBooking> cbSet = Set.of(currentCB, cb);
programConflicts.add(cbSet);
}
}
}
//Is just preliminary, I will make a single return statement out of it once I'm
//done testing
private static boolean hasOverLap(ClassBooking cb1, ClassBooking cb2) {
if(cb1.getWeekday() != cb2.getWeekday()) {
return false;
}
if((cb1.getBeginTime().isBefore(cb2.getBeginTime()) ||
cb1.getBeginTime().equals(cb2.getBeginTime())) &&
cb1.getEndTime().isAfter(cb2.getBeginTime())) {
return true;
}
if((cb1.getBeginTime().isAfter(cb2.getBeginTime()) ||
cb1.getBeginTime().equals(cb2.getBeginTime())) &&
cb1.getBeginTime().isBefore(cb2.getEndTime())) {
return true;
}
return false;
}
public static Set<Set<ClassBooking>> getRoomConflicts() {
return roomConflicts;
}
public static void setRoomConflicts(Set<Set<ClassBooking>> roomConflicts) {
ScheduleConflictDiscovery.roomConflicts = roomConflicts;
}
public static List<Set<ClassBooking>> getProgramConflicts() {
return programConflicts;
}
public static void setProgramConflicts(List<Set<ClassBooking>> programConflicts) {
ScheduleConflictDiscovery.programConflicts = programConflicts;
}
}
```
N = 3200
. In this case it takes a lot of time to end. I left it running during the night to get the answer.import numpy as np
def min_max(mat1, mat2, i, j):
''' this function takes 2 matrices and 2 indexes
and return the minimum of the element wise maximum
between row i of mat1 and col j of mat2 '''
return min(np.maximum(mat1[i,:], mat2[:,j]))
def max_prod(mat1,mat2):
''' this function takes 2 matrices and return a new matrix
where position (i,j) is min_max(mat1, mat2, i, j) '''
n = len(mat1)
my_prod = np.zeros((n,n), dtype=float)
for i in range(n):
for j in range(i,n):
my_prod[i,j] = min_max(mat1,mat2,i,j)
my_prod[j,i] = min_max(mat2,mat1,j,i)
return my_prod
N = 5
A = np.random.randint(1,20, size=(N,N))
print max_prod(A,A)