Enigmatic Code

Programming Enigma Puzzles

Enigma 1018: Half-time

From New Scientist #2174, 20th February 1999 [link]

Professor Dolittle shades in those squares corresponding to one of his lectures. He has at least one lecture a day (and on some days he actually has more than one) and no two consecutive days have exactly the same lecture times. On just one day he has no afternoon lectures. Dolittle only seems to work half the week: it is possible to cut the timetable into two pieces of equal area, with one straight cut, so that one half is completely free of shading.

Someone was needed to give an extra lecture at one of two times next week: the one later in the week was also at a later time of day. I asked the professor if he was lecturing at those times. I knew that his answer together with all the above information, would enable me to work out his complete timetable.

In fact, he was free for just the first of those two times and he agreed to take an extra lecture at that time. If I told you the day of that extra lecture you would be able to work out his complete timetable.

Please send in a copy of the professor’s timetable (without the extra lecture added).

In the magazine this puzzle seems to have been labelled: “Enigma 1081“.

[enigma1018]

One response to “Enigma 1018: Half-time

  1. Jim Randell 22 March 2019 at 7:18 am

    I found this to be quite convoluted to solve (and also that it was quite easy to go wrong).

    The first problem I had was finding the ways that the timetable could be bisected. Using just the white area, I reasoned that the cut must be a single straight line, at some angle that passes directly through the centre of the Wed, 11am slot. As we change the angle of the cut, the whole squares which are separated by the cut only change when the line passes an intersection on the grid. So I was able to solve this problem geometrically and find 12 different ways of bisecting the timetable.

    We then consider each possible split, and consider subsets of the complete squares on either side of the cut, to find sets that satisfy the conditions. I took the phrase “on some days” to mean “on at least 2 days” (although it also seems to work if we take it to mean “on at least 1 day”).

    The program finds 4 different timetables that satisfy the conditions.

    We then consider the two possible slots for the extra lecture, and find those that give a unique timetable according to the answer from the professor, and those where the professor is free for the first slot, but not the second, are recorded.

    This finds three potential scenarios. Two of the scenarios have the same slot for first potential extra lecture, but correspond to different timetables for the professor. The third scenario provides the answer.

    This Python program uses quite a lot of useful routines from the enigma.py library. It runs in 132ms.

    Run: [ @repl.it ]

    from itertools import combinations, product
    from enigma import subsets, tuples, irange, icount_at_least, filter_unique, unpack, fraction, compare, first, uniq, printf
    
    # label the possible lecture slots as follows:
    #
    #       9am 10am 11am  2pm  3pm
    #  Mon:   0    1    2    3    4
    #  Tue:   5    6    7    8    9
    #  Wed:  10   11   12   13   14
    #  Thu:  15   16   17   18   19
    #  Fri:  20   21   22   23   24
    
    # possible lecture slots
    slots = irange(0, 24)
    
    # extract day (0 - 4) and time (0 - 4)
    day = lambda x: x // 5
    time = lambda x: x % 5
    
    # put the slots into days
    days = list(set() for _ in irange(0, 4))
    for x in slots: days[day(x)].add(x)
    
    # make a canonical form of a split
    def canonical(s):
      m = first(x for x in s if x != 0)[0]
      return tuple(s if m == 1 else (-x for x in s))
    
    # determine possible bisections of the timetable by a straight cut
    # consider lines passing through centre and an intersection
    splits = dict()
    for (x, y) in product(irange(1, 5, step=2), irange(-5, 5, step=2)):
      if x == y == 0: continue
      m = (a, b) = fraction(y, x)
      if m in splits: continue
      # for each square determine on which side of the line the 4 corners fall
      split = [0] * 25
      for (x0, y0) in product(irange(-4, 4, step=2), repeat=2):
        vs = set(compare(a * (x0 + dx), b * (y0 + dy)) for (dx, dy) in product((-1, +1), repeat=2))
        i = (5 * (x0 + 4) // 2 + (y0 + 4) // 2)
        if -1 not in vs: split[i] = +1
        if +1 not in vs: split[i] = -1
      splits[m] = canonical(split)
    
    # consider possible splits, and collect possible timetables
    rs = list()
    for split in uniq(splits.values()):
      for k in set(split):
        if k == 0: continue
        # possible slots
        slots = list(i for (i, x) in enumerate(split) if x == k)
        # choose possible filled slots
        for lectures in subsets(slots, min_size=7):
    
          # count the number of lectures on each day
          ns = list(len(d.intersection(lectures)) for d in days)
    
          # "he has at least one lecture a day"
          if 0 in ns: continue
    
          # "on some days he has more than one"
          f = lambda n: n > 1
          if not icount_at_least(ns, f, 2): continue
    
          # "no two consecutive days have exactly the same lecture times"
          times = list(set(time(x) for x in d if x in lectures) for d in days)
          if any(x == y for (x, y) in tuples(times, 2)): continue
    
          # "on just one day he had no afternoon lectures" (time = 3, 4)
          if sum(not(t.intersection((3, 4))) for t in times) != 1: continue
    
          rs.append(lectures)
    
    # now consider possible additional lecture slots (A, B)
    # and collect potential (timetable, A, B) solutions
    ss = list()
    for (A, B) in combinations(irange(0, 24), 2):
    
      # B is later in the week and later in the day than A
      if not(day(A) < day(B) and time(A) < time(B)): continue
    
      # do these slots give a unique answer from the professor?
      f = lambda lectures: (A in lectures, B in lectures)
      (rs1, _) = filter_unique(rs, f)
    
      for s in rs1:
        # the professor is free for A but not B
        if A not in s and B in s:
          printf("[A = {A}, B = {B} -> lectures = {s}]")
          ss.append((s, A, B))
    
    # now if we knew knew the day of a we could find the solution
    f = unpack(lambda s, A, B: day(A))
    (ss, _) = filter_unique(ss, f)
    
    # output solutions
    for (s, A, B) in ss:
      printf("lectures = {s}; A = {A}, B = {B}")
    

    Solution: The timetable looks like this:

    The extra lecture that the professor agrees to is on Wednesday at 2pm.

    The other slot, when the professor was already lecturing, is Friday at 3pm.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: