Peer Review by @SamuelePino

[SamuelePino]

Peer Review

At First Sight: Presentation and Readability

The README file is well done and self-explanatory. It helps understand rapidly the idea behind the algorithm used, and even how the heuristic function works. You might also have explained why you choose that specific heuristic function.

The absence of comments and a slighty complex code syntax slow down a bit the comprehension of the code.

---

Algorithmic Approach and Code Analysis

The algorithm you used is a Greedy, and it uses a good heuristic function (considering the results). After the first lines of initialization, we found the while-loop. Here you take the best list (found using heursitic function h), which is the list with the lowest cost. Then you remove it from the main list of the problem.

You add this list to flat_sol throuhg .extend. The variable flat_sol seems to be a single list of integers, containing only the elements of the lists which compose the current solution sol; it is used to efficiently compute the number of integers w in the solution, after the while loop ended.

Then you update the flag covered by adding those new integers gained in the current cycle, through the |= between the sets

- Main Function: My_greedy

def my_greedy(N):
    goal = set(range(N))

    lists = sorted(problem(N, seed=42), key=lambda l: -len(l))

    starting_x = lists.pop(0)

    sol = list()
    sol.append(starting_x)

    flat_sol = list(starting_x)
    nodes = 1

    covered = set(starting_x)
    while goal != covered:
        most_promising_x = min(lists, key = lambda x: h(flat_sol, x))
        lists.remove(most_promising_x)

        flat_sol.extend(most_promising_x)
        sol.append(most_promising_x)
        nodes = nodes + 1

        covered |= set(most_promising_x)

    w = len(flat_sol)

    logging.info(
        f"Greedy solution for N={N}: w={w} (bloat={(w-N)/N*100:.0f}%) - visited {nodes} nodes"
    )
    logging.debug(f"{sol}")
    return sol

The algorithm is quite interesting, because it implements a good heuristic function, and it manages to find solutions also for N = 50 and higher; it also manages to keep a "quite low" bloat (how far the solution is from the optimal one) considering that is a greedy algorithm.

---

Personal Suggestion:

It would be interesting trying with some other heuristic function, to understand if there exsist better ones to use. Maybe you can implement a system to explore not only the next step, but maybe the next m steps, starting from a finite bunch of k best candidate (i.e at cycle i=6 you select the best k=3 lists using the function h, and then you try exploring m=4 steps further starting from each of these 3 best candidates. Then you can select the best between those 3 further explorations). You can do it randomly, at fixed n cycle or at each cycle. It would be interesting analyzing obtained results.