siiky
2024/08/15
2024/08/15
en
Continuing the recent trend: on the previous log I wrote about a possible way out of a bad place.
It's been hard for me concentrate on anything lately, both at and out of work. Yesterday I went back to pnee to try and implement the pnee:over_all() strategy. It seemed like an insurmountable obstacle, a lot more complicated than anticipated, because of the used data structures, because consumed tokens must be removed from their places, because non-consumed tokens must be kept in their original order, but especiall because I couldn't concentrate on it and Just Get That Shit Done. I took a break for dinner and afterwards, with a lighter head, I came up with a plan. It's still a bit complicated, the implementation will be even more so, but I think it'll work!
Today I woke up at 7h in the morning, went to a quiet place, and wrote everything down in paper. This is what I got:
The plan is to create a new pnee_place function, that'll be mutually recursive with the "top" over_all() function. The "inner" function will take the place itself, the number of tokens to consume, and a "callback" that'll recursively call the "top" function to tentatively consume from the remaining places. Once they've gone to the full depth, i.e., once there's a combination of tokens to test, the predicate provided by the programmer is used to verify (or not) that the combination is acceptable.
If it is, this combination (InputTokens), along with the new marking, are returned, and the call tree is slowly undone (can be optimized with a throw/catch, but I'll leave that for later). Otherwise, error is returned, signalling a new combination must be got and tested. And here there are two possibilities in the "inner" function. The first is that the combination was accepted, and should be passed along up the call stack. The second is that the combination wasn't accepted, in which case it must try the next option, if there is any, or return error, signaling, as before, that no accepted combination was found.
After writing the roughest of sketches yesterday, and describing it in words today, I'm convinced it works. It's just a dumb backtracking algorithm after all. The complication stems from the data structures (which are generic, not lists), and the requirements.