PolyU OS As

q2-de.py

#!/usr/bin/env pypy3
from constraint import *
from collections import Counter
from itertools import combinations
problem = Problem()

requests = [60, 77, 70, 33, 99, 83, 75, 21, 77, 28, 60, 48]
request_l = len(requests)
slots = {
    'A': 123,
    'B': 345,
    'C': 234
}

print(sum(requests), sum(slots.values()), '{:.2f}%'.format(
    (sum(requests) * 100) / sum(slots.values())))

for name, size in slots.items():
    combs = set()
    for i in range(1, len(requests) + 1):
        for comb in combinations(requests, i):
            if sum(comb) > size:
                continue
            if sum(comb) < size * 0.87:  # !?
                continue
            s_comb = tuple(sorted(comb))
            if s_comb in combs:
                continue
            combs |= {s_comb}
    print(name, len(combs))
    problem.addVariable(name, list(combs))


def ensure_subset(a, b, c):
    req_c = Counter(requests)
    req_c.subtract(Counter(a + b + c))
    return all(map(lambda i: i >= 0, req_c.values()))


problem.addConstraint(lambda a, b, c: len(
    a) + len(b) + len(c) >= request_l - 1)
problem.addConstraint(ensure_subset)

sols = problem.getSolutions()
sols.sort(key=lambda s: sum([i for t in s.values() for i in t]))
sols.reverse()
slots_total = sum(slots.values())

dup = set()
for s in sols[:25]:
    check = s['A'], s['B'], s['C']
    if check in dup:
        continue
    sum_v = sum([i for t in s.values() for i in t])
    left = 1000 - (slots['A'] - sum(s['A'])) - (slots['B'] - sum(s['B'])) - (slots['C'] - sum(s['C']))
    print('A: {} {}/{} ({:.2f}%) | B: {} {}/{} ({:.2f}%) | C: {} {}/{} ({:.2f}%) | Total: {}/{} ({:.2f}%) | Ans: {}/1000 ({:.2f}%)'.format(
          str(s['A']), sum(s['A']), slots['A'],  (sum(
              s['A']) * 100) / slots['A'],
          str(s['B']), sum(s['B']), slots['B'],  (sum(
              s['B']) * 100) / slots['B'],
          str(s['C']), sum(s['C']), slots['C'],  (sum(
              s['C']) * 100) / slots['C'],
          sum_v, slots_total, (sum_v * 100) / slots_total,
          left, (left * 100) / 1000
          ))
    dup |= {check}

q2-de.txt

731 702 104.13%
A 14
B 316
C 117
A: (60, 60) 120/123 (97.56%) | B: (21, 70, 77, 77, 99) 344/345 (99.71%) | C: (28, 48, 75, 83) 234/234 (100.00%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (21, 99) 120/123 (97.56%) | B: (48, 60, 77, 77, 83) 345/345 (100.00%) | C: (28, 60, 70, 75) 233/234 (99.57%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (21, 99) 120/123 (97.56%) | B: (60, 60, 70, 77, 77) 344/345 (99.71%) | C: (28, 48, 75, 83) 234/234 (100.00%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (48, 75) 123/123 (100.00%) | B: (21, 28, 60, 60, 77, 99) 345/345 (100.00%) | C: (70, 77, 83) 230/234 (98.29%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (48, 75) 123/123 (100.00%) | B: (28, 60, 77, 77, 99) 341/345 (98.84%) | C: (21, 60, 70, 83) 234/234 (100.00%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (48, 75) 123/123 (100.00%) | B: (21, 70, 77, 77, 99) 344/345 (99.71%) | C: (28, 60, 60, 83) 231/234 (98.72%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (48, 75) 123/123 (100.00%) | B: (60, 60, 70, 77, 77) 344/345 (99.71%) | C: (21, 28, 83, 99) 231/234 (98.72%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (21, 28, 70) 119/123 (96.75%) | B: (48, 60, 77, 77, 83) 345/345 (100.00%) | C: (60, 75, 99) 234/234 (100.00%) | Total: 698/702 (99.43%) | Ans: 996/1000 (99.60%)
A: (60, 60) 120/123 (97.56%) | B: (21, 28, 33, 75, 77, 99) 333/345 (96.52%) | C: (70, 77, 83) 230/234 (98.29%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 28, 33, 77, 83, 99) 341/345 (98.84%) | C: (70, 75, 77) 222/234 (94.87%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 28, 33, 75, 83, 99) 339/345 (98.26%) | C: (70, 77, 77) 224/234 (95.73%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 28, 33, 70, 83, 99) 334/345 (96.81%) | C: (75, 77, 77) 229/234 (97.86%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 28, 33, 77, 77, 99) 335/345 (97.10%) | C: (70, 75, 83) 228/234 (97.44%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (28, 70, 75, 77, 83) 333/345 (96.52%) | C: (21, 33, 77, 99) 230/234 (98.29%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 70, 75, 77, 99) 342/345 (99.13%) | C: (28, 33, 77, 83) 221/234 (94.44%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (33, 70, 75, 77, 83) 338/345 (97.97%) | C: (21, 28, 77, 99) 225/234 (96.15%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (28, 75, 77, 77, 83) 340/345 (98.55%) | C: (21, 33, 70, 99) 223/234 (95.30%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 75, 77, 77, 83) 333/345 (96.52%) | C: (28, 33, 70, 99) 230/234 (98.29%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (33, 75, 77, 77, 83) 345/345 (100.00%) | C: (21, 28, 70, 99) 218/234 (93.16%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (28, 70, 77, 77, 83) 335/345 (97.10%) | C: (21, 33, 75, 99) 228/234 (97.44%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (21, 70, 77, 77, 99) 344/345 (99.71%) | C: (28, 33, 75, 83) 219/234 (93.59%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (33, 70, 75, 77, 77) 332/345 (96.23%) | C: (21, 28, 83, 99) 231/234 (98.72%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (33, 70, 77, 77, 83) 340/345 (98.55%) | C: (21, 28, 75, 99) 223/234 (95.30%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (75, 77, 83, 99) 334/345 (96.81%) | C: (21, 28, 33, 70, 77) 229/234 (97.86%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)
A: (60, 60) 120/123 (97.56%) | B: (70, 77, 83, 99) 329/345 (95.36%) | C: (21, 28, 33, 75, 77) 234/234 (100.00%) | Total: 683/702 (97.29%) | Ans: 981/1000 (98.10%)

q2-fgh.py

#!/usr/bin/env pypy3
from constraint import *
from collections import Counter
from itertools import combinations

xyzs_list = [
    [17, 27, 37, 279],
    [23, 37, 55, 472],
    [37, 42, 63, 614],
]


def answers(q):
    print('Question', q)
    for xyzs in xyzs_list:
        x, y, z, s = xyzs
        problem = Problem()
        if q == 'f':
            problem.addVariable('X', range(10))
            problem.addVariable('Y', range(10))
            problem.addVariable('Z', range(10))
        elif q == 'g':
            problem.addVariable('X', range((s // x) + 1))
            problem.addVariable('Y', range((s // y) + 1))
            problem.addVariable('Z', range((s // z) + 1))
        elif q == 'h':
            problem.addVariable('X', range(1, 10))
            problem.addVariable('Y', range(1, 10))
            problem.addVariable('Z', range(1, 10))
        problem.addConstraint(lambda a, b, c: (a * x) + (b * y) + (c * z) <= s)
        sols = problem.getSolutions()
        minimal_unused_space = (
            lambda e: s - e['X'] * x - e['Y'] * y - e['Z'] * z)
        sols.sort(key=minimal_unused_space)
        print(x, y, z, s)
        for sol in sols[:10]:
            print(sol, minimal_unused_space(sol))


if __name__ == '__main__':
    for q in 'fgh':
        answers(q)

q2-fgh.txt

Question f
17 27 37 279
{'X': 6, 'Y': 1, 'Z': 4} 2
{'X': 5, 'Y': 3, 'Z': 3} 2
{'X': 4, 'Y': 5, 'Z': 2} 2
{'X': 3, 'Y': 7, 'Z': 1} 2
{'X': 2, 'Y': 9, 'Z': 0} 2
{'X': 1, 'Y': 0, 'Z': 7} 3
{'X': 0, 'Y': 2, 'Z': 6} 3
{'X': 8, 'Y': 1, 'Z': 3} 5
{'X': 7, 'Y': 3, 'Z': 2} 5
{'X': 6, 'Y': 5, 'Z': 1} 5
23 37 55 472
{'X': 6, 'Y': 9, 'Z': 0} 1
{'X': 6, 'Y': 6, 'Z': 2} 2
{'X': 2, 'Y': 7, 'Z': 3} 2
{'X': 6, 'Y': 3, 'Z': 4} 3
{'X': 2, 'Y': 4, 'Z': 5} 3
{'X': 6, 'Y': 0, 'Z': 6} 4
{'X': 2, 'Y': 1, 'Z': 7} 4
{'X': 9, 'Y': 7, 'Z': 0} 6
{'X': 5, 'Y': 8, 'Z': 1} 6
{'X': 1, 'Y': 9, 'Z': 2} 6
37 42 63 614
{'X': 8, 'Y': 6, 'Z': 1} 3
{'X': 8, 'Y': 3, 'Z': 3} 3
{'X': 8, 'Y': 0, 'Z': 5} 3
{'X': 4, 'Y': 8, 'Z': 2} 4
{'X': 4, 'Y': 5, 'Z': 4} 4
{'X': 4, 'Y': 2, 'Z': 6} 4
{'X': 0, 'Y': 7, 'Z': 5} 5
{'X': 0, 'Y': 4, 'Z': 7} 5
{'X': 0, 'Y': 1, 'Z': 9} 5
{'X': 9, 'Y': 5, 'Z': 1} 8
Question g
17 27 37 279
{'Z': 2, 'Y': 0, 'X': 12} 1
{'Z': 1, 'Y': 2, 'X': 11} 1
{'Z': 0, 'Y': 4, 'X': 10} 1
{'Z': 4, 'Y': 1, 'X': 6} 2
{'Z': 3, 'Y': 3, 'X': 5} 2
{'Z': 2, 'Y': 5, 'X': 4} 2
{'Z': 1, 'Y': 7, 'X': 3} 2
{'Z': 0, 'Y': 9, 'X': 2} 2
{'Z': 7, 'Y': 0, 'X': 1} 3
{'Z': 6, 'Y': 2, 'X': 0} 3
23 37 55 472
{'Z': 1, 'Y': 10, 'X': 2} 1
{'Z': 0, 'Y': 9, 'X': 6} 1
{'Z': 3, 'Y': 7, 'X': 2} 2
{'Z': 2, 'Y': 6, 'X': 6} 2
{'Z': 1, 'Y': 5, 'X': 10} 2
{'Z': 0, 'Y': 4, 'X': 14} 2
{'Z': 5, 'Y': 4, 'X': 2} 3
{'Z': 4, 'Y': 3, 'X': 6} 3
{'Z': 3, 'Y': 2, 'X': 10} 3
{'Z': 2, 'Y': 1, 'X': 14} 3
37 42 63 614
{'Z': 2, 'Y': 1, 'X': 12} 2
{'Z': 0, 'Y': 4, 'X': 12} 2
{'Z': 5, 'Y': 0, 'X': 8} 3
{'Z': 3, 'Y': 3, 'X': 8} 3
{'Z': 1, 'Y': 6, 'X': 8} 3
{'Z': 6, 'Y': 2, 'X': 4} 4
{'Z': 4, 'Y': 5, 'X': 4} 4
{'Z': 2, 'Y': 8, 'X': 4} 4
{'Z': 0, 'Y': 11, 'X': 4} 4
{'Z': 9, 'Y': 1, 'X': 0} 5
Question h
17 27 37 279
{'X': 6, 'Y': 1, 'Z': 4} 2
{'X': 5, 'Y': 3, 'Z': 3} 2
{'X': 4, 'Y': 5, 'Z': 2} 2
{'X': 3, 'Y': 7, 'Z': 1} 2
{'X': 8, 'Y': 1, 'Z': 3} 5
{'X': 7, 'Y': 3, 'Z': 2} 5
{'X': 6, 'Y': 5, 'Z': 1} 5
{'X': 2, 'Y': 2, 'Z': 5} 6
{'X': 1, 'Y': 4, 'Z': 4} 6
{'X': 9, 'Y': 3, 'Z': 1} 8
23 37 55 472
{'X': 6, 'Y': 6, 'Z': 2} 2
{'X': 2, 'Y': 7, 'Z': 3} 2
{'X': 6, 'Y': 3, 'Z': 4} 3
{'X': 2, 'Y': 4, 'Z': 5} 3
{'X': 2, 'Y': 1, 'Z': 7} 4
{'X': 5, 'Y': 8, 'Z': 1} 6
{'X': 1, 'Y': 9, 'Z': 2} 6
{'X': 9, 'Y': 4, 'Z': 2} 7
{'X': 5, 'Y': 5, 'Z': 3} 7
{'X': 1, 'Y': 6, 'Z': 4} 7
37 42 63 614
{'X': 8, 'Y': 6, 'Z': 1} 3
{'X': 8, 'Y': 3, 'Z': 3} 3
{'X': 4, 'Y': 8, 'Z': 2} 4
{'X': 4, 'Y': 5, 'Z': 4} 4
{'X': 4, 'Y': 2, 'Z': 6} 4
{'X': 9, 'Y': 5, 'Z': 1} 8
{'X': 9, 'Y': 2, 'Z': 3} 8
{'X': 5, 'Y': 7, 'Z': 2} 9
{'X': 5, 'Y': 4, 'Z': 4} 9
{'X': 5, 'Y': 1, 'Z': 6} 9

q3.py

#!/usr/bin/python3
segments = [
    (0, 1234),
    (2432, 304),
    (5678, 321),
    (3011, 234),
    (4004, 1357),
    (1234, 456),
    (3404, 345),
    (6666, 1525)
]

requests = 543, 211, 388, 201, 258, 99

if __name__ == '__main__':
    ranges_tmp = []
    for s in segments:
        ranges_tmp.append((s[0], s[0] + s[1]))
    ranges_tmp.sort(key=lambda r: r[0])
    ranges = ranges_tmp.copy()
    print('============================= first-fit')
    for req in requests:
        inserted = False
        for i, entry in enumerate(ranges[:-1]):
            space = ranges[i + 1][0] - entry[1]
            if req <= space:
                obj = entry[1], entry[1] + req
                ranges.insert(i + 1, obj)
                print('Inserted req {}, obj {}'.format(req, obj))
                inserted = True
                break
        if not inserted:
            print('No space to insert {}'.format(req))
        print(ranges)

    ranges = ranges_tmp.copy()
    print('============================= best-fit')
    for req in requests:
        inserted = False
        spaces = []
        for i, entry in enumerate(ranges[:-1]):
            space = ranges[i + 1][0] - entry[1]
            spaces.append((i + 1, space))
        spaces.sort(key=lambda s: s[1])
        for s in spaces:
            if req <= s[1]:
                base = ranges[s[0] - 1][1]
                obj = (base, base + req)
                ranges.insert(s[0], obj)
                print('Inserted req {}, obj {}'.format(req, obj))
                inserted = True
                break
        if not inserted:
            print('No space to insert {}'.format(req))
        print(ranges)

    ranges = ranges_tmp.copy()
    print('============================= worst-fit')
    for req in requests:
        inserted = False
        spaces = []
        for i, entry in enumerate(ranges[:-1]):
            space = ranges[i + 1][0] - entry[1]
            spaces.append((i + 1, space))
        spaces.sort(key=lambda s: s[1])
        spaces.reverse()
        print(spaces)
        for s in spaces:
            if req <= s[1]:
                base = ranges[s[0] - 1][1]
                obj = (base, base + req)
                ranges.insert(s[0], obj)
                print('Inserted req {}, obj {}'.format(req, obj))
                inserted = True
                break
        if not inserted:
            print('No space to insert {}'.format(req))
        print(ranges)

q3.txt

============================= first-fit
Inserted req 543, obj (1690, 2233)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (6666, 8191)]
Inserted req 211, obj (2736, 2947)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2947), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (6666, 8191)]
Inserted req 388, obj (5999, 6387)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2947), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (5999, 6387), (6666, 8191)]
Inserted req 201, obj (3749, 3950)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2947), (3011, 3245), (3404, 3749), (3749, 3950), (4004, 5361), (5678, 5999), (5999, 6387), (6666, 8191)]
Inserted req 258, obj (5361, 5619)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2947), (3011, 3245), (3404, 3749), (3749, 3950), (4004, 5361), (5361, 5619), (5678, 5999), (5999, 6387), (6666, 8191)]
Inserted req 99, obj (2233, 2332)
[(0, 1234), (1234, 1690), (1690, 2233), (2233, 2332), (2432, 2736), (2736, 2947), (3011, 3245), (3404, 3749), (3749, 3950), (4004, 5361), (5361, 5619), (5678, 5999), (5999, 6387), (6666, 8191)]
============================= best-fit
Inserted req 543, obj (5999, 6542)
[(0, 1234), (1234, 1690), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (5999, 6542), (6666, 8191)]
Inserted req 211, obj (3749, 3960)
[(0, 1234), (1234, 1690), (2432, 2736), (3011, 3245), (3404, 3749), (3749, 3960), (4004, 5361), (5678, 5999), (5999, 6542), (6666, 8191)]
Inserted req 388, obj (1690, 2078)
[(0, 1234), (1234, 1690), (1690, 2078), (2432, 2736), (3011, 3245), (3404, 3749), (3749, 3960), (4004, 5361), (5678, 5999), (5999, 6542), (6666, 8191)]
Inserted req 201, obj (2736, 2937)
[(0, 1234), (1234, 1690), (1690, 2078), (2432, 2736), (2736, 2937), (3011, 3245), (3404, 3749), (3749, 3960), (4004, 5361), (5678, 5999), (5999, 6542), (6666, 8191)]
Inserted req 258, obj (5361, 5619)
[(0, 1234), (1234, 1690), (1690, 2078), (2432, 2736), (2736, 2937), (3011, 3245), (3404, 3749), (3749, 3960), (4004, 5361), (5361, 5619), (5678, 5999), (5999, 6542), (6666, 8191)]
Inserted req 99, obj (6542, 6641)
[(0, 1234), (1234, 1690), (1690, 2078), (2432, 2736), (2736, 2937), (3011, 3245), (3404, 3749), (3749, 3960), (4004, 5361), (5361, 5619), (5678, 5999), (5999, 6542), (6542, 6641), (6666, 8191)]
============================= worst-fit
[(2, 742), (7, 667), (6, 317), (3, 275), (5, 255), (4, 159), (1, 0)]
Inserted req 543, obj (1690, 2233)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (6666, 8191)]
[(8, 667), (7, 317), (4, 275), (6, 255), (3, 199), (5, 159), (2, 0), (1, 0)]
Inserted req 211, obj (5999, 6210)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (5999, 6210), (6666, 8191)]
[(9, 456), (7, 317), (4, 275), (6, 255), (3, 199), (5, 159), (8, 0), (2, 0), (1, 0)]
Inserted req 388, obj (6210, 6598)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5678, 5999), (5999, 6210), (6210, 6598), (6666, 8191)]
[(7, 317), (4, 275), (6, 255), (3, 199), (5, 159), (10, 68), (9, 0), (8, 0), (2, 0), (1, 0)]
Inserted req 201, obj (5361, 5562)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (3011, 3245), (3404, 3749), (4004, 5361), (5361, 5562), (5678, 5999), (5999, 6210), (6210, 6598), (6666, 8191)]
[(4, 275), (6, 255), (3, 199), (5, 159), (8, 116), (11, 68), (10, 0), (9, 0), (7, 0), (2, 0), (1, 0)]
Inserted req 258, obj (2736, 2994)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2994), (3011, 3245), (3404, 3749), (4004, 5361), (5361, 5562), (5678, 5999), (5999, 6210), (6210, 6598), (6666, 8191)]
[(7, 255), (3, 199), (6, 159), (9, 116), (12, 68), (5, 17), (11, 0), (10, 0), (8, 0), (4, 0), (2, 0), (1, 0)]
Inserted req 99, obj (3749, 3848)
[(0, 1234), (1234, 1690), (1690, 2233), (2432, 2736), (2736, 2994), (3011, 3245), (3404, 3749), (3749, 3848), (4004, 5361), (5361, 5562), (5678, 5999), (5999, 6210), (6210, 6598), (6666, 8191)]

q4.py

#!/usr/bin/pypy3
REF_STRING = [0, 2, 3, 4, 1, 4, 5, 0, 1, 2,
              3, 1, 3, 2, 3, 4, 5, 0, 1, 3, 1, 0, 1, 2]
# REF_STRING = [0, 1, 3, 1, 4, 2, 1, 0, 1, 3, 1, 3, 1, 2, 5, 1, 2, 3, 4, 5, 1, 0, 5, 0] # Last year


def fifo(frame_count=3, ref=REF_STRING):
    cursor = 0
    frames = [-1] * frame_count
    records = []
    for c in ref:
        if c in frames:
            records.append((c, frames.copy(), -1))
        else:
            frames[cursor] = c
            records.append((c, frames.copy(), cursor))
            cursor += 1
            if cursor == frame_count:
                cursor = 0
    return records


def optimal(frame_count=3):
    frames = [-1] * frame_count
    records = []
    for i, c in enumerate(REF_STRING):
        if c in frames:
            records.append((c, frames.copy(), -1))
        else:
            distances = [9999] * frame_count
            for j, frame in enumerate(frames):
                try:
                    distances[j] = REF_STRING[i + 1:].index(frame)
                except ValueError:
                    pass
            cursor = distances.index(max(distances))
            frames[cursor] = c
            records.append((c, frames.copy(), cursor))
    return records


def lru_counter(frame_count=3, ref=REF_STRING):
    frames = [-1] * frame_count
    records = []
    counter = [-1] * frame_count
    records_counter = []
    for i, c in enumerate(ref):
        if c in frames:
            counter[frames.index(c)] = i + 1
            records.append((c, frames.copy(), -1))
            records_counter.append(counter.copy())
        else:
            cursor = counter.index(min(counter))
            frames[cursor] = c
            counter[cursor] = i + 1
            records.append((c, frames.copy(), cursor))
            records_counter.append(counter.copy())
    return records, records_counter


def kbs(frame_count=3, p=4):
    predictions = [[]]
    futures = []
    frames = [-1] * frame_count
    records = []
    for i, c in enumerate(REF_STRING):
        cycled_futures = futures.copy()
        cycles = i // p
        for j in range(cycles):
            idx = i - ((j + 1) * p)
            cycled_futures += predictions[idx]
        distances = [9999] * frame_count
        for j, frame in enumerate(frames):
            try:
                distances[j] = cycled_futures.index(frame)
            except ValueError:
                pass
        if c in frames:
            records.append((c, frames.copy(), -1))
        else:
            cursor = distances.index(max(distances))
            frames[cursor] = c
            records.append((c, frames.copy(), cursor))
        futures.append(c)
        if len(futures) > p:
            futures = futures[1:i+p]
        predictions.append(futures.copy())
        # print(futures)
    return records


def lru_stack(frame_count=3):
    stack = [-1] * frame_count
    records_stack = []
    for c in REF_STRING:
        if c in stack:
            stack.remove(c)
            stack.insert(0, c)
            records_stack.append(stack.copy())
        else:
            stack.pop()
            stack.insert(0, c)
            display = stack.copy()
            try:
                idx = display.index(-1)
                display = display[idx:] + display[: idx]
            except:
                pass
            records_stack.append(display)
    return records_stack


def render_digit(d, star):
    if d == -1:
        return '- '
    if star:
        return str(d) + '*'
    if d < 10:
        return str(d) + ' '
    return str(d)


def render_results(results):
    print('  '.join(map(lambda r: str(r[0]), results)))
    for i in range(len(results[0][1])):
        print(
            ' '.join(map(lambda r: render_digit(r[1][i], i == r[2]), results)))
    return results


def render_results_counter(results_counter):
    for i in range(len(results_counter[0])):
        print(
            ' '.join(map(lambda r: render_digit(r[i], False), results_counter)))
    return results_counter


def page_faults_count(results):
    page_faults = len(list(
        filter(lambda i: i >= 0, map(lambda r: r[2], results))))
    return page_faults


if __name__ == '__main__':
    for f in [3, 4]:
        print('FIFO ({} frames)'.format(f))
        r = render_results(fifo(f))
        print('{} page faults'.format(page_faults_count(r)))
        print()
        print('Optimal ({} frames)'.format(f))
        r = render_results(optimal(f))
        print('{} page faults'.format(page_faults_count(r)))
        results, results_counter = lru_counter(f)
        print()
        print('LRU ({} frames)'.format(f))
        render_results(results)
        print('Stack content')
        render_results_counter(lru_stack(f))
        print('{} page faults'.format(page_faults_count(results)))
        print()

    i = 0
    while True:
        s = REF_STRING.copy()
        pos = i // 6
        if pos > len(REF_STRING):
            break
        c = i % 6
        s.insert(pos, c)
        i += 1
        fifo_pf = page_faults_count(fifo(3, s))
        lru_pf = page_faults_count(lru_counter(3, s)[0])
        if lru_pf - fifo_pf >= 3:
            print('FIFO page faults: {}'.format(fifo_pf))
            print('LRU page faults: {}'.format(lru_pf))
            print('Revised reference string (char {} inserted to pos {}): {}'.format(
                c, pos, ' '.join(map(str, s))))
    print()
    for args in (3, 5), (3, 9), (4, 5), (4, 9):
        print('KBS ({} frames) (P={})'.format(*args))
        r = render_results(kbs(*args))
        print('{} page faults'.format(page_faults_count(r)))
        print()

q4.txt

FIFO (3 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  4* 4  4  4  0* 0  0  0  1* 1  1  1  1  1  0* 0  0  0  0  0  2*
-  2* 2  2  1* 1  1  1  1  2* 2  2  2  2  2  4* 4  4  1* 1  1  1  1  1 
-  -  3* 3  3  3  5* 5  5  5  3* 3  3  3  3  3  5* 5  5  3* 3  3  3  3 
16 page faults

Optimal (3 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  0  0  0  2* 2  2  2  2  2  4* 5* 0* 0  0  0  0  0  2*
-  2* 2  2  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
-  -  3* 4* 4  4  5* 5  5  5  3* 3  3  3  3  3  3  3  3  3  3  3  3  3 
12 page faults

LRU (3 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  4* 4  4  4  4  1* 1  1  1  1  1  1  4* 4  4  1* 1  1  1  1  1 
-  2* 2  2  1* 1  1  0* 0  0  3* 3  3  3  3  3  3  0* 0  0  0  0  0  0 
-  -  3* 3  3  3  5* 5  5  2* 2  2  2  2  2  2  5* 5  5  3* 3  3  3  2*
Stack content
-  -  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2 
-  2  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1 
0  0  0  2  3  3  1  4  5  0  1  2  2  1  1  2  3  4  5  0  0  3  3  0 
16 page faults

FIFO (4 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  1* 1  1  1  1  1  3* 3  3  3  3  3  3  0* 0  0  0  0  0  0 
-  2* 2  2  2  2  5* 5  5  5  5  1* 1  1  1  1  1  1  1  3* 3  3  3  3 
-  -  3* 3  3  3  3  0* 0  0  0  0  0  0  0  4* 4  4  4  4  1* 1  1  1 
-  -  -  4* 4  4  4  4  4  2* 2  2  2  2  2  2  5* 5  5  5  5  5  5  2*
16 page faults

Optimal (4 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  0  0  0  0  3* 3  3  3  3  3  3  3  3  3  3  3  3  2*
-  2* 2  2  2  2  2  2  2  2  2  2  2  2  2  4* 4  0* 0  0  0  0  0  0 
-  -  3* 3  1* 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
-  -  -  4* 4  4  5* 5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5 
10 page faults

LRU (4 frames)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  1* 1  1  1  1  1  1  1  1  1  1  1  5* 5  5  5  5  5  5  2*
-  2* 2  2  2  2  5* 5  5  5  3* 3  3  3  3  3  3  3  1* 1  1  1  1  1 
-  -  3* 3  3  3  3  0* 0  0  0  0  0  0  0  4* 4  4  4  3* 3  3  3  3 
-  -  -  4* 4  4  4  4  4  2* 2  2  2  2  2  2  2  0* 0  0  0  0  0  0 
Stack content
-  -  -  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2 
-  -  3  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1 
-  2  2  2  3  3  1  4  5  0  1  2  2  1  1  2  3  4  5  0  0  3  3  0 
0  0  0  0  2  2  3  1  4  5  0  0  0  0  0  1  2  3  4  5  5  5  5  3 
15 page faults

FIFO page faults: 16
LRU page faults: 19
Revised reference string (char 5 inserted to pos 10): 0 2 3 4 1 4 5 0 1 2 5 3 1 3 2 3 4 5 0 1 3 1 0 1 2
FIFO page faults: 16
LRU page faults: 19
Revised reference string (char 0 inserted to pos 11): 0 2 3 4 1 4 5 0 1 2 3 0 1 3 2 3 4 5 0 1 3 1 0 1 2

KBS (3 frames) (P=5)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  5* 5  5  2* 3* 3  3  3  3  3  3  3  3  3  3  0* 0  0 
-  2* 2  2  2  2  2  0* 1* 1  1  1  1  1  1  1  1  0* 1* 1  1  1  1  1 
-  -  3* 4* 1* 4* 4  4  4  4  4  4  4  2* 2  4* 5* 5  5  5  5  5  5  2*
18 page faults

KBS (3 frames) (P=9)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  0  0  0  0  3* 3  3  3  3  4* 5* 0* 0  3* 3  3  3  3 
-  2* 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 
-  -  3* 4* 1* 4* 5* 5  1* 1  1  1  1  1  1  1  1  1  1  1  1  0* 1* 1 
15 page faults

KBS (4 frames) (P=5)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  5* 5  5  5  5  5  5  2* 2  2  2  2  2  2  2  0* 0  0 
-  2* 2  2  2  2  2  0* 0  2* 3* 3  3  3  3  3  3  3  3  3  3  3  3  3 
-  -  3* 3  3  3  3  3  1* 1  1  1  1  1  1  1  1  0* 1* 1  1  1  1  1 
-  -  -  4* 1* 4* 4  4  4  4  4  4  4  4  4  4  5* 5  5  5  5  5  5  2*
17 page faults

KBS (4 frames) (P=9)
0  2  3  4  1  4  5  0  1  2  3  1  3  2  3  4  5  0  1  3  1  0  1  2
0* 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  3* 3  3  3  3 
-  2* 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 
-  -  3* 3  3  3  3  3  3  3  3  3  3  3  3  4* 5* 5  5  5  5  5  5  5 
-  -  -  4* 1* 4* 5* 5  1* 1  1  1  1  1  1  1  1  1  1  1  1  0* 1* 1 
13 page faults

q5-a.txt

Safe sequence: (4, 2, 3, 0, 1, 5)
Start avail: [0, 1, 1, 1]
P4 finished, avail: [2, 1, 1, 2]
P2 finished, avail: [3, 1, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P0 finished, avail: [6, 3, 5, 5]
P1 finished, avail: [6, 4, 5, 6]
P5 finished, avail: [6, 4, 6, 8]

Safe sequence: (4, 2, 3, 0, 5, 1)
Start avail: [0, 1, 1, 1]
P4 finished, avail: [2, 1, 1, 2]
P2 finished, avail: [3, 1, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P0 finished, avail: [6, 3, 5, 5]
P5 finished, avail: [6, 3, 6, 7]
P1 finished, avail: [6, 4, 6, 8]

Safe sequence: (4, 2, 3, 5, 0, 1)
Start avail: [0, 1, 1, 1]
P4 finished, avail: [2, 1, 1, 2]
P2 finished, avail: [3, 1, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P5 finished, avail: [5, 2, 4, 6]
P0 finished, avail: [6, 3, 6, 7]
P1 finished, avail: [6, 4, 6, 8]

Total number of safe sequences: 3
if X = B
Safe sequence: (4, 2, 3, 0, 1, 5)
Start avail: [0, 0, 1, 1]
P4 finished, avail: [2, 0, 1, 2]
P2 finished, avail: [3, 0, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P0 finished, avail: [6, 3, 5, 5]
P1 finished, avail: [6, 4, 5, 6]
P5 finished, avail: [6, 4, 6, 8]

Safe sequence: (4, 2, 3, 0, 5, 1)
Start avail: [0, 0, 1, 1]
P4 finished, avail: [2, 0, 1, 2]
P2 finished, avail: [3, 0, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P0 finished, avail: [6, 3, 5, 5]
P5 finished, avail: [6, 3, 6, 7]
P1 finished, avail: [6, 4, 6, 8]

Safe sequence: (4, 2, 3, 5, 0, 1)
Start avail: [0, 0, 1, 1]
P4 finished, avail: [2, 0, 1, 2]
P2 finished, avail: [3, 0, 2, 3]
P3 finished, avail: [5, 2, 3, 4]
P5 finished, avail: [5, 2, 4, 6]
P0 finished, avail: [6, 3, 6, 7]
P1 finished, avail: [6, 4, 6, 8]

Total number of safe sequences: 3
if X = C
Total number of safe sequences: 0
if X = D
Total number of safe sequences: 0

q5-b.txt

Safe sequence: (2, 4, 3, 5, 1, 0)
Start avail: [0, 0, 0, 1]
P2 finished, avail: [1, 0, 1, 2]
P4 finished, avail: [1, 2, 3, 2]
P3 finished, avail: [2, 2, 3, 2]
P5 finished, avail: [3, 4, 3, 2]
P1 finished, avail: [4, 4, 3, 4]
P0 finished, avail: [4, 5, 3, 5]

Total number of safe sequences: 1
If Y = B
Safe sequence: (2, 3, 4, 5, 1, 0)
Start avail: [0, 1, 0, 1]
P2 finished, avail: [1, 1, 1, 2]
P3 finished, avail: [2, 1, 1, 2]
P4 finished, avail: [2, 3, 3, 2]
P5 finished, avail: [3, 5, 3, 2]
P1 finished, avail: [4, 5, 3, 4]
P0 finished, avail: [4, 6, 3, 5]

Safe sequence: (2, 3, 5, 4, 1, 0)
Start avail: [0, 1, 0, 1]
P2 finished, avail: [1, 1, 1, 2]
P3 finished, avail: [2, 1, 1, 2]
P5 finished, avail: [3, 3, 1, 2]
P4 finished, avail: [3, 5, 3, 2]
P1 finished, avail: [4, 5, 3, 4]
P0 finished, avail: [4, 6, 3, 5]

Safe sequence: (2, 4, 3, 5, 1, 0)
Start avail: [0, 1, 0, 1]
P2 finished, avail: [1, 1, 1, 2]
P4 finished, avail: [1, 3, 3, 2]
P3 finished, avail: [2, 3, 3, 2]
P5 finished, avail: [3, 5, 3, 2]
P1 finished, avail: [4, 5, 3, 4]
P0 finished, avail: [4, 6, 3, 5]

Safe sequence: (3, 2, 4, 5, 1, 0)
Start avail: [0, 1, 0, 1]
P3 finished, avail: [1, 1, 0, 1]
P2 finished, avail: [2, 1, 1, 2]
P4 finished, avail: [2, 3, 3, 2]
P5 finished, avail: [3, 5, 3, 2]
P1 finished, avail: [4, 5, 3, 4]
P0 finished, avail: [4, 6, 3, 5]

Safe sequence: (3, 2, 5, 4, 1, 0)
Start avail: [0, 1, 0, 1]
P3 finished, avail: [1, 1, 0, 1]
P2 finished, avail: [2, 1, 1, 2]
P5 finished, avail: [3, 3, 1, 2]
P4 finished, avail: [3, 5, 3, 2]
P1 finished, avail: [4, 5, 3, 4]
P0 finished, avail: [4, 6, 3, 5]

Total number of safe sequences: 5

q5.py

#!/usr/bin/pypy3
from itertools import permutations

avail = [0, 1, 1, 1]

allocations = [
    [1, 1, 2, 1],
    [0, 1, 0, 1],
    [1, 0, 1, 1],
    [2, 1, 1, 1],
    [2, 0, 0, 1],
    [0, 0, 1, 2],
]

maxs = [
    [4, 3, 2, 1],
    [2, 4, 3, 2],
    [2, 0, 1, 1],
    [3, 2, 3, 4],
    [2, 0, 1, 2],
    [1, 2, 3, 4],
]

"""
avail = [0, 0, 0, 1]

allocations = [
    [0, 1, 0, 1],
    [1, 0, 0, 2],
    [1, 0, 1, 1],
    [1, 0, 0, 0],
    [0, 2, 2, 0],
    [1, 2, 0, 0],
]

maxs = [
    [0, 4, 0, 5],
    [3, 4, 3, 4],
    [1, 0, 1, 2],
    [1, 1, 0, 0],
    [1, 2, 3, 2],
    [3, 2, 1, 1],
]
"""


def find_perms():
    cnt = 0
    for perm in permutations([0, 1, 2, 3, 4, 5]):
        skip = False
        cur_avail = avail.copy()
        progress = [cur_avail.copy()]
        for p in perm:
            all_res = list(map(sum, zip(cur_avail, allocations[p])))
            deadlock = False
            for i, r in enumerate(all_res):
                if r < maxs[p][i]:
                    deadlock = True
                    break
            if deadlock:
                skip = True
                break
            cur_avail = all_res
            progress.append((p, cur_avail.copy()))
        if skip:
            continue
        print('Safe sequence: {}'.format(perm))
        print('Start avail: {}'.format(progress[0]))
        for p in progress[1:]:
            print('P{} finished, avail: {}'.format(p[0], p[1]))
        print()
        cnt += 1
    print('Total number of safe sequences: {}'.format(cnt))


def main():
    global allocations, avail
    find_perms()
    print('if X = B')
    allocations[3] = [2, 2, 1, 1]
    avail = [0, 0, 1, 1]
    find_perms()
    print('if X = C')
    allocations[3] = [2, 1, 2, 1]
    avail = [0, 1, 0, 1]
    find_perms()
    print('if X = D')
    allocations[3] = [2, 1, 1, 2]
    avail = [0, 1, 1, 0]
    find_perms()
    """
    print('If Y = B')
    avail = [0, 1, 0, 1]
    find_perms()
    """


if __name__ == '__main__':
    main()