I will be reviewing your final version of lab1.
I would like to start saying that the comments, the README and the code in general is very readable and simple (in a positive sense) so good job!
Issues
As you probably already know, your selected heuristic function h() for A* is sub-optimal since it doesn't consider the repetitions of numbers (weight to minimize) in the current state nor the incoming list. Thus, the solution found is good but it analyzes too many "bloated" nodes before moving on with the actually optimal nodes.
Comments
Sorting the list of lists (implemented with frozenset and HashableArray objects) when storing them in ALL_STATES variable is a very significant optimization for avoiding the same list of lists in a different order.
The HashableArray class is a good idea to solve the un-hashability problem. A simpler way of doing it would be to cast every list and list of lists to tuple objects at the beginning (sorted as well, as you did). In this way every instance is hashable and immutable.
As you wrote on your README, the function bytes() gives an error for N > 200 because it cannot take iterables that contain numbers that are > 256. A quick fix for that would be removing this function completely (the function hash(self._data) should be enough if you work with tuples as mentioned above).
goal_test() builds the set covered by the given state inside its scope each time it is called. The way I did it was to compute and save the covered set inside the State object when created so that the goal_test() function just checks if it is equal to the already known solution. Your approach seems more efficient since it will only construct the covered set when analyzing (and testing) a node. Good job once again.
Minor issues
The name ALL_STATES is not accurate, since the lists alone do not compose a state, but just potential elements of the states.
The first import should be from lab1_afterdeadline import * and not from lab1 import *.
Lab 1 review by Omar Ormachea
I will be reviewing your final version of lab1. I would like to start saying that the comments, the README and the code in general is very readable and simple (in a positive sense) so good job!
Issues
h()
for A* is sub-optimal since it doesn't consider the repetitions of numbers (weight to minimize) in the current state nor the incoming list. Thus, the solution found is good but it analyzes too many "bloated" nodes before moving on with the actually optimal nodes.Comments
frozenset
andHashableArray
objects) when storing them inALL_STATES
variable is a very significant optimization for avoiding the same list of lists in a different order.HashableArray
class is a good idea to solve the un-hashability problem. A simpler way of doing it would be to cast every list and list of lists to tuple objects at the beginning (sorted as well, as you did). In this way every instance is hashable and immutable.bytes()
gives an error for N > 200 because it cannot take iterables that contain numbers that are > 256. A quick fix for that would be removing this function completely (the functionhash(self._data)
should be enough if you work with tuples as mentioned above).goal_test()
builds the set covered by the given state inside its scope each time it is called. The way I did it was to compute and save the covered set inside theState
object when created so that thegoal_test()
function just checks if it is equal to the already known solution. Your approach seems more efficient since it will only construct the covered set when analyzing (and testing) a node. Good job once again.Minor issues
ALL_STATES
is not accurate, since the lists alone do not compose a state, but just potential elements of the states.from lab1_afterdeadline import *
and notfrom lab1 import *
.