First part
This puzzle is a serious jump in difficulty. It is a spin on the famous River Crossing Puzzle, and I haven't done anything of this sort in quite a while. The Wikipedia page says there are at least three possible approaches to solving the problem: graph theorems, dynamic programming and integer programming; I have never heard of the latter.
I'm not sure when I'll start the problem.
It has been on my mind for a while. It is a different problem from the habitual: not only the solving techniques are more sophisticated, the representation of the problem is also more convoluted. But it must start somewhere.
Parsing
I thought about skipping the parsing and directly coding the input data; but it doesn't make much sense – parsing is an important skill, anyway. I must keep in mind, however, that the data representation might change at some point. This is a computationally intensive problem, and that choice might have a direct impact on the program's runtime and efficiency.
The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip.
The second floor contains a hydrogen generator.
The third floor contains a lithium generator.
The fourth floor contains nothing relevant.This is the input form, and the following is a diagram representing the data:
F4 . . . . .
F3 . . . LG .
F2 . HG . . .
F1 E . HM . LM A regex parser on the input seems reasonable. For every line, It should catch every expression of the form ELEMENT-compatible microchip and ELEMENT generator; and, for simplicity, I'll just keep the first letter of the ELEMENT. For now, each item will be represented by a string, akin to what is represented in the diagram. Every floor then be represented by a list, in which each element is a string.
This took me a while (of course, I haven't been programming non-stop; yesterday was a somewhat hectic day).
GENERATOR_REGEX = r'\b(\w)(?:\w+\sgenerator)'
MICROCHIP_REGEX = r'\b(\w)(?:\w+-compatible microchip)'
with open('input') as file_input:
def extract_items(
regex: str,
lines: list[tuple]
) -> list[tuple]:
return reduce(lambda x, y: x + y,
list(map(
lambda line_index: [(''.join(filter(None, result)),
line_index[0])
for result in re.findall(regex,
line_index[1])],
lines)),
[])
lines_with_index = list(enumerate(file_input.readlines(),
start=0))
generators = extract_items(GENERATOR_REGEX, lines_with_index)
microchips = extract_items(MICROCHIP_REGEX, lines_with_index)This produces two lists.
[('s', 0), ('p', 0), ('t', 1), ('r', 1), ('c', 1)]
[('s', 0), ('p', 0), ('r', 1), ('c', 1), ('t', 2)]Puzzle rules
Having parsed the input, the next step is to bring us closer to the problem solving logic. I'm thinking of building some functions that abstract the underlying data representation – the floors are represented by lists of strings, which themselves stand for microchips and generators – translating it to actions in the context of our problem.
def get_piece_element(piece: tuple) -> str:
return piece[0]
def get_piece_floor(piece: tuple) -> int:
return piece[1]
def generator_and_chip_on_same_floor(
chip: tuple,
generators: list[tuple]
) -> bool:
chip_element, chip_floor = get_piece_element(chip), get_piece_floor(chip)
same_generator = list(filter(lambda gen: get_piece_element(gen) == chip_element,
generators))
return get_piece_floor(same_generator) == chip_floor
def chip_has_another_generator_on_same_floor(
chip: tuple,
generators: list
) -> bool:
chip_element, chip_floor = get_piece_element(chip), get_piece_floor(chip)
other_generators = list(filter(lambda gen: get_piece_element(gen) != chip_element,
generators))
return any(map(lambda gen: get_piece_floor(gen) == chip_floor,
other_generators))
# a given state is legal if
# - all microchips have the corresponding generator in the same floor
# - if a given microchip does not meet the above requirement,
# then there are no other generators in the same floor.
def is_legal_state(
microchips: list[tuple],
generators: list[tuple]
):
return all(map(
lambda chip: (
generator_and_chip_on_same_floor(chip, generators) and
not chip_has_another_generator_on_same_floor(chip, generators)
),
microchips))Although this is already getting quite long, I feel the code is readable and the last function, is_legal_state, benefits a lot from the other functions. It seems very concise. Of course, I should also produce some tests to assess the validity of my functions.
import unittest
class TestingLegalStates(unittest.TestCase):
def test_valid_state(self):
microchips = [('s', 0), ('p', 0), ('t', 2), ('r', 1), ('c', 1)]
generators = [('s', 0), ('p', 0), ('t', 1), ('r', 1), ('c', 1)]
self.assertTrue(is_legal_state(microchips, generators))
def test_invalid_state_because_t_has_no_generator(self):
microchips = [('s', 0), ('p', 0), ('t', 0), ('r', 1), ('c', 1)]
generators = [('s', 0), ('p', 0), ('t', 1), ('r', 1), ('c', 1)]
self.assertFalse(is_legal_state(microchips, generators))
def test_invalid_state_because_t_is_with_wrong_generator(self):
microchips = [('s', 0), ('p', 0), ('t', 2), ('r', 1)]
generators = [('s', 0), ('p', 0), ('t', 1), ('r', 1), ('c', 2)]
self.assertFalse(is_legal_state(microchips, generators))Of course, there were some minor mistakes: the following condition should have been an or, thus making use of boolean lazy evaluation – it is a sufficient condition that a chip has its own generator in the same floor; if not, then it is necessary that there are no other generators on its floor:
generator_and_chip_on_same_floor(chip, generators) or
not chip_has_another_generator_on_same_floor(chip, generators)and, also
same_generator = next(filter(lambda gen: get_piece_element(gen) == chip_element,
generators))the next instead of list guarantees getting an element instead of a list containing an element, which was creating some unnecessary troubles.
Now we're closer to working on the real problem. We need:
- a function to validate whether the problem is solved – that all microchips and generators are on the fourth floor – and that should be very easy (a three-liner, I think, at most);
def is_puzzle_solved(
microchips: list[tuple],
generators: list[tuple]
) -> bool:
return all(get_piece_floor(piece) == 3 for piece in
microchips + generators)- to code the notion of the elevator; a move can only be done within the reach of the elevator, and it should start at the bottom floor (0).
- movement rules, and the new status that arises from each movement.
From that moment onwards, I think we can start brute-forcing and optimising the solution. There will be two big problems ahead: to cache the already visited states (so as not to waste computation and memory space), and also, which I think will be slightly more complicated, to understand whether two states are actually the same (ie: the following states are fundamentally representing an equal situation).
[('s', 0), ('p', 0)]
[('s', 1), ('p', 0)]
[('s', 0), ('p', 0)]
[('s', 0), ('p', 1)]Oof. It has been a while. I think about this puzzle every day; not necessarily in the sense that I'm actively conjuring up solutions, but more so that I long for a couple of hours to immerse in it again. I have a couple of hours ahead, indeed, after dinner – it's raining heavily outside... – so let's tackle it.
The is_puzzle_solved function is tested. The concept of having an elevator will be included in the state of each iteration, which is defined by the position of every generator, microchip, the number of turns elapsed and the elevator floor. As for movement rules, I coded a function that takes all possible combinations up to two items (it can be none, where the elevator would move alone).
# NOTE how to account for a move where
# the elevator moves alone?
def get_all_possible_move_combinations(
microchips: list[tuple],
generators: list[tuple],
) -> list[list]:
return (combinations(microchips + generators, 1) +
combinations(microchips + generators, 2))I still don't know exactly how this fits into the bigger picture, but I'll take it from here. Just for the sake of ensuring this function behaves as expected, I'll produce some simple tests.
Err...in the meantime, I realised that by making combinations(microchips + generators, _ ) I lose information about which is which – because the tuple doesn't actually retain any information about each piece's type. This can easily be circumvented by just adding an identifier to each tuple (something like 'g' for generator, and 'm' for microchip).
I suppose this is the result of a bad design decision, which comes to haunt me later on. There are other ways to solve this, but ideally I'll mature enough as a programmer that I won't need to track back and solve these minor issues as I'm tackling bigger problems. Anyway, this was easily fixed in the parsing. But since I did this, then I do not need to separate generators and microchips anymore...so I refactored everything. There's now
def get_piece_type(piece: tuple) -> str:
return piece[2]which led to further refactors:
def generator_and_chip_on_same_floor(
chip: tuple,
pieces: list[tuple]
) -> bool:
chip_element, chip_floor = get_piece_element(chip), get_piece_floor(chip)
return any(map(lambda piece: (get_piece_type(piece) == 'g' and
get_piece_element(piece) == chip_element and
get_piece_floor(piece) == chip_floor),
pieces))
def chip_has_another_generator_on_same_floor(
chip: tuple,
pieces: list
) -> bool:
chip_element, chip_floor = get_piece_element(chip), get_piece_floor(chip)
return any(map(lambda piece: (get_piece_type(piece) == 'g' and
get_piece_element(piece) != chip_element and
get_piece_floor(piece) == chip_floor),
pieces))I suppose the code could be better, but I'm just trying to get steps further for now.
I also just realised that there is another constraint on get_all_possible_move_combinations: the pieces must be all on the same floor. Thus, I'll only apply combinations to a particular floor, which is where the elevator is at. What a big detail to oversee! 🥵
def get_all_possible_move_combinations(
pieces: list[tuple],
floor: int
) -> list[list]:
return (list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 1)) +
list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 2)) +
[])So, after this long refactor, I'm sort of back at where I started – but at least the code is better, and possibly more robust.
I suppose the next step is to generate the new states given the combinations from the function above. The elevator can either be going up or down (ideally, never below 0 nor above 3...), thus any combination generates at most two new possible states.
I woke up in the middle of the night, mildly restless.
def generate_moved_pieces(
pieces_to_move: list[tuple],
state: tuple[list[tuple], int],
move: int,
) -> tuple[list[tuple], int]:
pieces, floor = state
if (floor == 0 and move == -1 or
floor == 3 and move == 1):
return tuple()
return ([piece for piece in pieces
if piece not in pieces_to_move] +
[create_piece_on_different_floor(piece, move)
for piece in pieces_to_move]
)
This already accounts for the case where the elevator goes below 0 or above 3. The function is already tested as well.
At this point, it feels like the problem logic has all the building blocks in place to start getting some solutions (albeit yet to be optimised, for example by with caching already seen states – a visited set – and also by ).
As today I slept well, for a very welcome change, I came to the sports center in the morning to do some yoga and hopefully spend a few minutes with this problem.
I couldn't do any further progress yesterday, other than realising – although it was not documented here – that there were still problems with the code (of course). My main function is the following
def get_minimum_number_of_steps(
# queue is a list of states
queue: list,
nbr_of_turns: int,
visited: set[list],
) -> int:
# CHECK ALL OF THE QUEUE AT ONCE
states, floor = queue
if states and is_puzzle_solved(states):
return nbr_of_turns
return get_minimum_number_of_steps(
NEW_QUEUE,
nbr_of_turns + 1,
visited.union(list(map(lambda state: state[0],
queue))))I believe this is a breadth-first search approach; I check all states in my queue, and then produce all the following states at once, where NEW_QUEUE is. To do that, however, I need the generate_moved_pieces function, which is now refactored and further worked in as generate_new_states_for_queue.
def generate_new_states_for_queue(
pieces_to_move: list[tuple],
state: tuple[list[tuple], int],
) -> tuple[list[tuple], int]:
def generate_new_states(new_floor: int):
return ([[piece for piece in pieces
if piece not in pieces_to_move] +
[create_piece_on_different_floor(piece, new_floor)
for piece in pieces_to_move],
new_floor]
)
pieces, floor = state
return reduce(lambda x, y: x + y,
map(lambda new_floor: generate_new_states(new_floor),
[x for x in list(range(floor - 1, floor + 2, 2))
if 0 <= x <= 4]),
[])Now, the NEW_QUEUE variable can be substituted by a very complicated call.
def get_minimum_number_of_steps(
# queue is a list of states
queue: list,
nbr_of_turns: int,
visited: set[list],
) -> int:
# CHECK ALL OF THE QUEUE AT ONCE
states, floor = queue
if states and is_puzzle_solved(states):
return nbr_of_turns
return get_minimum_number_of_steps(
reduce(lambda x, y: x + y,
list(map(lambda state:
generate_new_states_for_queue(
state,
get_all_possible_move_combinations(state)),
states)),
[]),
nbr_of_turns + 1,
visited.union(list(map(lambda state: state[0],
queue))))
This is not readable at all. In fact, I feel there's some major refactor coming in. The crux of the problem seems to be that
- for every state, all move combinations must be calculated;
- for every move combination, new states arise.
Each of these for loops are represented in the reduce calls. At this moment, generate_new_states_for_queue is generating the upper and lower floor movements of the elevator for every move combination on a given state.
Ideally, this would work for the very small example, but there's still some work to be done on the visited parameter.
I've looked closer into the code throughout the day, and it is passing the first iteration; but generate_new_queue is not properly accumulating all possible states, so that's where I am stuck right now.
I got to this problem on the 25th...I know it is one of the most difficult on the 2016 edition, and I can only wonder how long it would take if I were focusing on this as a full-time thing. It's ok – I'm satisfied with the progress, and the code is looking decent. I did, however, take a long while to debug the myriad of small problems that arose, and, again, it is something I'd like to work on in the future.
def get_minimum_number_of_steps(
# queue is a list of states
queue: list,
nbr_of_turns: int,
visited: set[list],
) -> int:
if any(map(lambda state: is_puzzle_solved(state),
queue)):
return nbr_of_turns
return get_minimum_number_of_steps(
generate_new_queue(queue),
nbr_of_turns + 1,
visited.union({tuple(state) for state in list(map(lambda x: x[0],
queue))}))It's raining outside, so this is the first thing I'll tackle in the morning. It feels close!
There were issues with generate_new_queue yesterday, which was then refactored into its own function; not only is the code cleaner, it now allows for testing.
I noticed some issues with the consistency of get_all_possible_move_combinations, which are now more clear:
class TestingCombinationOfPieces(TestingParsing):
def test_getting_combinations_for_single_piece_in_floor(self):
res = get_all_possible_move_combinations(
[[('a', 0, 'g')], 0])
self.assertTrue(len(res) == 1)
self.assertTrue(type(res) == list)
self.assertTrue(type(res[0]) == tuple)
self.assertTrue(type(res[0][0]) == tuple)
self.assertTrue(type(res[0][0][0]) == str)
self.assertTrue(type(res[0][0][1]) == int)
self.assertTrue(type(res[0][0][2]) == str)
def test_getting_combinations_for_three_pieces_in_floor(self):
res = get_all_possible_move_combinations(
[[
('a', 0, 'g'),
('b', 0, 'g'),
('c', 0, 'g'),
], 0
]
)
self.assertTrue(type(res) == list)
self.assertTrue(type(res[0]) == tuple)
self.assertTrue(type(res[0][0]) == tuple)
self.assertTrue(type(res[0][0][0]) == str)
self.assertTrue(type(res[0][0][1]) == int)
self.assertTrue(type(res[0][0][2]) == str)
self.assertTrue(len(res) == 6)I had to be more rigorous with this, as there were issues when producing tests.
I also noticed some problems with the function nomenclature, which was not so clear. Also, having functions inside of functions makes it harder to test, so I set to fix all of this.
def get_all_possible_move_combinations(
state: tuple[list[tuple], int]
) -> list[tuple[tuple]]:
"""return all possible combinations of pieces that can be moved.
The result comes in the form of a list of tuples, in which each tuple
has the tuples representing pieces to be moved"""
pieces, floor = state
return (list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 1)) +
list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 2)))
def generate_state_with_moved_pieces(
pieces: list[tuple],
pieces_to_move: list[tuple],
new_floor: int,
) -> list[list[tuple], int]:
old_pieces = [piece for piece in pieces
if piece not in pieces_to_move]
new_pieces = [create_piece_on_different_floor(piece, new_floor)
for piece in pieces_to_move]
return [old_pieces + new_pieces, new_floor]
def accumulate_new_states_for_queue(
pieces_to_move: list[tuple],
state: tuple[list[tuple], int],
) -> list[[list[tuple], int]]:
"""returns between one or two new states for a given
list of pieces to move, according to the floors the elevator
goes to"""
pieces, floor = state
# get the possible floors to visit
# ie. if elevator is at 0, only returns the state for 1,
# if elevator is at 1, returns the state for 0 and 2."""
floor_filter = [x for x in list(range(floor - 1, floor + 2, 2))
if 0 <= x <= 4]
return reduce(lambda x, y: x + y,
map(lambda new_floor: generate_state_with_moved_pieces(
pieces,
pieces_to_move,
new_floor),
floor_filter))
def generate_new_queue(old_queue: list):
return reduce(lambda x, y: x + y,
list(map(lambda state:
accumulate_new_states_for_queue(
get_all_possible_move_combinations(state),
state),
old_queue)),
[])The tests are now passing, but I know of at least two problems:
- nowhere am I accounting for the case in which the elevator moves without selecting any piece;
- I am still not properly accounting for all combinations, which I suppose is the issue I was set out to fix from yesterday.
This refactor & testing makes it easier to progress further. generate_new_queue seems concise, and I wouldn't touch it further; accumulate_new_states_for_queue, however, will need some work. It is the first function to receive the move combinations, and it must map state generation to each combination.
Another day, another go, and I'm picking up where I left off yesterday.
accumulate_new_states_for_queue has a misleading name. At this point, it gets all possible combinations – even if the following function is not handling that correctly – and produces a state (from the following function) for the available floors.
There are still not tests for it (I'm being sloppy, and not doing test-driven development properly); so I'm thinking of duplicating this function, to retain and isolate its floor-mapping behaviour, and then test it with simple combinations against generate_state_with_moved_pieces (which is tested, granular, and working well).
(a hopefully more clear mapping of what must be done)
The first issue I'm coming across with is at the new function accumulate_possible_floors.
def accumulate_possible_floors(
state: tuple[list[tuple], int],
pieces_to_move: list[tuple],
) -> list[[list[tuple], int]]:
"""returns between one or two new states for a given
list of pieces to move, according to the floors the elevator
goes to"""
pieces, floor = state
# get the possible floors to visit
# ie. if elevator is at 0, only returns the state for 1,
# if elevator is at 1, returns the state for 0 and 2."""
floor_filter = [x for x in list(range(floor - 1, floor + 2, 2))
if 0 <= x <= 4]
return reduce(lambda x, y: [x] + [y],
map(lambda new_floor: generate_state_with_moved_pieces(
pieces,
pieces_to_move,
new_floor),
floor_filter),
)It's mostly the same as it was before (with some changes in the reduce return call). It should return a list of states, but in the case of returning just one state (eg. [[('s', 0, 'm'), ('s', 1, 'g')], 1]) the result will be the state itself, and not a list with just one element (the sole state).
Phind promptly suggests changing the reduce call to a list comprehension, and it works like a charm.
While testing the same function, but with a different combination of floors, the tests failed; I traced it back to generate_state_with_moved_pieces, which seems to not be able to put pieces on a lower floor. There was a slight issue on create_piece_on_different_floor; it took 10 seconds to solve.
Further tests went smoothly. I'm ready to create accumulate_possible_combinations.
In the meantime, I realised there was still a problem which I had yet to tackle, and thus I created a test: test_generating_one_floor_with_no_moved_pieces. This accounts for the case in which the elevator moves without taking any pieces. accumulate_possible_floors handles it well, but it is necessary that the function providing the combinations provides this empty case. I know it is not, at this point, but at least it became much more clear where this problem would arise.
This is solved:
def get_all_possible_move_combinations(
state: tuple[list[tuple], int]
) -> list[tuple[tuple]]:
"""return all possible combinations of pieces that can be moved.
The result comes in the form of a list of tuples, in which each tuple
has the tuples representing pieces to be moved"""
pieces, floor = state
return (list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 1)) +
list(combinations([piece for piece in pieces
if get_piece_floor(piece) == floor], 2)) +
[((),)])I'm already testing the accumulate_possible_combinations. It is breaking somewhere, and through a couple of print statements, I found the culprit:
(('s', 0, 'g'),)
(('s', 0, 'm'),)
(('s', 0, 'g'), ('s', 0, 'm'))
((),)File "/home/apinto/prog/roc/ex11/ex11_1.py", line 147, in <listcomp>
return [state for state in floors]
^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/apinto/prog/roc/ex11/ex11_1.py", line 142, in <lambda>
floors = map(lambda new_floor: generate_state_with_moved_pieces(
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/apinto/prog/roc/ex11/ex11_1.py", line 123, in generate_state_with_moved_pieces
new_pieces = [create_piece_on_different_floor(piece, new_floor)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/apinto/prog/roc/ex11/ex11_1.py", line 123, in <listcomp>
new_pieces = [create_piece_on_different_floor(piece, new_floor)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/apinto/prog/roc/ex11/ex11_1.py", line 51, in create_piece_on_different_floor
return tuple([get_piece_element(piece),
^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/apinto/prog/roc/ex11/ex11_1.py", line 36, in get_piece_element
return piece[0]It breaks when handling the empty movements. I quickly solved it by adding a not-so-elegant if clause to generate_state_with_moved_pieces.
if pieces_to_move == ((),):
return [pieces, new_floor](a sidenote:)
Everything seems to be running now. Did some basic tests for generate_new_queue, which means that the whole stack of calls should be tested and supposedly working.
Running on the example,
def get_minimum_number_of_steps(
# queue is a list of states
queue: list,
nbr_of_turns: int,
visited: set[list],
) -> int:
# CHECK ALL OF THE QUEUE AT ONCE
print(nbr_of_turns)
if any(map(lambda state: is_puzzle_solved(state),
queue)):
return nbr_of_turns
return get_minimum_number_of_steps(
generate_new_queue(queue),
nbr_of_turns + 1,
visited.union({tuple(state) for state in list(map(lambda x: x[0],
queue))}))There's a severe hang at around the 5th turn. At the 6th, it seems to have stopped, and since this is highly exponential, there is no point in trying to wait further. There are two things to note:
- the
visitedparameter is never used, and I never tested it. So that's, I suppose the next step: basic caching. - afterwards, if it is still quite slow, there should be a way to test for equivalency of states, and abstract that;
- if it is still prohibitively slow after (properly) implementing the
visitedparameter, further techniques must come into play – like implementing a sorting mechanism for the queue, to first reach out for the states closest to being the solution. This, I think, would turn my BFS approach into the A*.
Thinking where I'd implement the visited parameter, it feels natural to make it part of the queue variable. It would come into play at every accumulate_possible_combinations call: if a particular state has already been visited, the function returns an empty list. But before tackling that, I'll take a well-deserved break.
I'm just trying to make some later-in-the-day progress in the puzzle. There were some issues with hashing mutable elements (lists) into the visited set, so I went ahead and refactored every state to be using a tuple.
Then another issue arose:
# NOTE there seems to be a problem here.
# Do I really need an edge case?
# could the default behaviour not handle this already?
def generate_state_with_moved_pieces(
pieces: list[tuple],
pieces_to_move: list[tuple],
new_floor: int,
) -> list[list[tuple], int]:
if pieces_to_move == ((),):
return tuple(pieces) + tuple(new_floor,)
else:
old_pieces = [piece for piece in pieces
if piece not in pieces_to_move]
new_pieces = [create_piece_on_different_floor(piece, new_floor)
for piece in pieces_to_move]
return tuple([old_pieces + new_pieces, new_floor])It has been a while since I tackled the puzzle. During my last try, I managed to get the code running and sort-of-working: but the result when running the example was 7 steps instead of 11 to get the shortest solution. I resorted to Phind for some quick tips, and it noticed I was never using my is_legal_state function, which is, of course, a massive oversee. I then got to 9 steps. And then I had a little of a breakdown about whether I should really be doing these sorts of puzzles during my volunteering stay in Slovenia, because maybe this is just covering up some underlying issues about how I spend my free time, and it's high time I call my therapist, anyway – but I digress.
So there are many things to improve in the code. Of course, I only now realise that having changed everything to tuples as a big mistake, as tuples are ordered – thus, it would be very rare for any two states to actually be the same due to the way I'm building them, which could be solved by centralising the creation of states and ensuring some sort of order to them. And then, state creation is not properly abstracted in my code, which is a big pain to handle if there comes another need for a refactor. I'm keeping these two issues in mind, but I suppose I can first achieve the goal of matching the example and then iterate further improvements from there.
During the small crisis that happened, I came to the conclusion that I have really no way to reason whether my code is properly finding the right states – at this point, it would be comfortable to see it work against the example. Thus, I suppose my priority is to ensure I am getting to all the necessary states in the example. In my is_puzzle_solved function, in which I check all the states in the queue for possible final states, I added a couple of lines for debug purposes:
def states_are_equal(state1, state2):
pieces1, floor1 = state1
pieces2, floor2 = state2
if floor1 != floor2:
return False
for piece in pieces1:
if piece not in pieces2:
return False
return True
def is_puzzle_solved(
state: tuple[tuple[tuple], int],
nbr_of_turns: int
) -> bool:
pieces, _ = state
if any(map(lambda example: states_are_equal(state, example),
example_states)):
print(f"found example state for turn {nbr_of_turns}!")
print(state)
if all(map(lambda piece: get_piece_floor(piece) == 3,
pieces)):
print(state)
return True
return False
(not my best piece of code, but desperate times call for desperate measures).
There's a sort of free morning ahead, so I decided to tackle this.
I started the day by properly testing the states_are_equal function, and also another function to handle the visited set variable. This was needed because the visited.union() was not enough, as tuples are unordered, and thus the union would really have to check for a different kind of equality. The code is not following the functional paradigm, at least for now, and I won't refactor it so soon.
def add_states_to_visited(
visited: set,
queue: list
) -> list:
states_to_add = []
for new_state in queue:
found = 0
for state in visited:
if states_are_equal(state, new_state):
found = 1
break
if found == 1:
continue
else:
states_to_add.append(new_state)
return visited.union(set(states_to_add))This is also tested.
Just to recap: what I am currently trying to do is go through all the steps (each recursive call for a new queue) and check whether the states in the example are properly represented in my solution. This will immensely help my further debugging (I am getting 9 steps instead of 11).
Recalling that I have the following lines being matched against every state in my queue:
if any(map(lambda example: states_are_equal(state, example),
example_states)):
print(f"found example state for turn {nbr_of_turns}!")
print(state)and that this is happening in my terminal:
found example state for turn 1!
((('h', 1, 'g'), ('l', 2, 'g'), ('l', 0, 'm'), ('h', 1, 'm')), 1)
found example state for turn 2!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 2, 'g'), ('h', 2, 'm')), 2)
found example state for turn 3!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 1, 'm'), ('h', 1, 'g')), 1)
found example state for turn 3!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 1, 'g'), ('h', 1, 'm')), 1)Notice how the first and the third and fourth states in the output, counting from top, are the same: there are still problems in the code (repeated states, or states that are equal albeit represented in different order among the tuple, must be excluded from further iterations in the queue).
This seems provisionally solved with the following lines:
def state_is_visited(
state: tuple[list[tuple], int],
visited: set
) -> bool:
for visited_state in visited:
if states_are_equal(state, visited_state):
return True
return False
def accumulate_possible_combinations(
state: tuple[list[tuple], int],
all_combinations: list[tuple],
visited: set
) -> tuple[tuple[tuple], int]:
"""accumulates at most two new states for each given combination of
pieces to move, according to the floors the elevator
goes to"""
states = tuple(new_state for combination in all_combinations
for new_state in accumulate_possible_floors(state,
combination)
if not state_is_visited(new_state, visited))
return statesIf the above correction (tested!), the output now looks like...
found example state for turn 1!
((('h', 1, 'g'), ('l', 2, 'g'), ('l', 0, 'm'), ('h', 1, 'm')), 1)
found example state for turn 2!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 2, 'g'), ('h', 2, 'm')), 2)
found example state for turn 3!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 1, 'm'), ('h', 2, 'g')), 1)
found example state for turn 3!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 2, 'g'), ('h', 1, 'm')), 1)
found example state for turn 4!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 2, 'g'), ('h', 0, 'm')), 0)
found example state for turn 4!
((('l', 2, 'g'), ('l', 0, 'm'), ('h', 2, 'g'), ('h', 0, 'm')), 0)
found example state for turn 4!
((('l', 2, 'g'), ('h', 0, 'm'), ('l', 0, 'm'), ('h', 2, 'g')), 0)
found example state for turn 5!
((('l', 2, 'g'), ('h', 2, 'g'), ('l', 1, 'm'), ('h', 1, 'm')), 1)
found example state for turn 5!
((('l', 2, 'g'), ('h', 1, 'm'), ('h', 2, 'g'), ('l', 1, 'm')), 1)
found example state for turn 5!
((('l', 2, 'g'), ('h', 2, 'g'), ('l', 1, 'm'), ('h', 1, 'm')), 1)
found example state for turn 5!
((('l', 2, 'g'), ('h', 2, 'g'), ('h', 1, 'm'), ('l', 1, 'm')), 1)
[. . .]
found example state for turn 9!
((('l', 3, 'g'), ('h', 3, 'g'), ('h', 2, 'm'), ('l', 3, 'm')), 3)...which brings both good news and bad news. Starting with the good: there is some progress, and I am not as hopelessly blocked as I felt during the past week. This is good.
As for the bad news, all of the example states up until and including step 9 are passed through (although there are clearly repeated states being tested for, which I should solve too at a later stage), but my solver is concluding the problem on step 9; that is wrong, because the elevator must go down another floor (step 10) and then bring the h microchip up (step 11). It's good to finally understand the nature of the issue.
If the program stops after turn 9, it means that the queue for turn 9 already includes the final solution. In fact it does, as I checked for this by hardcoding a state check for turn 9; and if turn 9 already has the solution, it would, in ideal conditions, be generated on turn 8. But after checking which states are generated on turn 8 (given the state it should achieve as per the example), the final state is not generated either, which means the final state is coming from another different state which I cannot really track down. This is a bummer, but there's another solution: hardcode a check to print the state that originates the final state.
Doing this, I unearth the state ((('h', 3, 'g'), ('h', 3, 'm'), ('l', 2, 'g'), ('l', 2, 'm')), 2). In fact, if it were possible to arrive at this state legally, the solution is just one move away: the elevator could move to the 4th floor with both l chip and generator, and it would be done. It is however very likely that it doesn't arrive here legally. I see two possible options: keep tracking back to past states (shouldn't take too long, and eventually I'll find a subtle, illegal state that I am not properly accounting for), or just try to produce more and more tests until I arrive to an illegal state that is uncovered. Both approaches are quite similar, in the sense that I am expecting an error in the checking for legal states, but this is not guaranteed. At the moment, I'm backtracking for illegal states in the accumulate_possible_combinations function.