Post AYjJKmT5AHNxvSDTjk by sten@chaos.social
(DIR) More posts by sten@chaos.social
(DIR) Post #AYjFBWXAddRe5HSWh6 by sotolf@social.linux.pizza
2023-08-14T11:51:41Z
0 likes, 0 repeats
So, would this count as dynamic programming? I can't really grasp the meaning of it yet. I have a set of bags that contain other bags, some bags are empty, using a queue of all the bags I go through this algorithm:map of bag to intqueue of bagswhile queue not empty: bag = queue.popFirst if bags inside of bag all in map: map[bag] = count(bags in bag) + sum(map[bag] for bag in bags) else: queue.addLast bag return map[goal]#askfedi #programming
(DIR) Post #AYjFBXGBwFSQKuWTrs by sten@chaos.social
2023-08-14T11:59:38Z
0 likes, 0 repeats
@sotolf Looking *very* casually through your algorithm, I don't think it's an example of dynamic programming. In DP, a problem is solved by solving ALL smaller instances of it. For example, computing the Levenshtein distance between words A and B works by computing the Levenshtein distance between all prefixes of A and all prefixes of B. I don't see that in your algorithm, but as I said, I just had a very casual look.
(DIR) Post #AYjFBXy9IocSXF5aNs by Archivist@social.linux.pizza
2023-08-14T17:46:20Z
0 likes, 0 repeats
@sten Wait... That is a pretty bad way to see Levenstein distance.? I almost always use a (virtual) graph to implement that@sotolf
(DIR) Post #AYjGp6DlzK5e0uoxqC by sten@chaos.social
2023-08-14T18:04:34Z
0 likes, 0 repeats
@Archivist @sotolf And you can compute the minimal(!) edits that turn A into B without also computing the minimal edits between any prefix of A and any prefix of B?
(DIR) Post #AYjIjIHMRb85a6rIoa by Archivist@social.linux.pizza
2023-08-14T18:26:04Z
0 likes, 0 repeats
@sten Yes, I don't know if the complexity is optimal though. I generally write it the way I explain it, as a distance on a graph@sotolf
(DIR) Post #AYjJKmT5AHNxvSDTjk by sten@chaos.social
2023-08-14T18:32:43Z
0 likes, 0 repeats
@Archivist @sotolf That's very interesting. Can you outline your technique?
(DIR) Post #AYjJnREfBaiKTK8YTI by Archivist@social.linux.pizza
2023-08-14T18:38:02Z
0 likes, 0 repeats
@sten @sotolfOf course! Just give me some time to draw a diagram for it
(DIR) Post #AYjOvWp2nWgjt1pZdg by Archivist@social.linux.pizza
2023-08-14T19:35:29Z
0 likes, 0 repeats
@sten @sotolf After getting a better read at my current mental capacity, I think it is wiser for me to send you the diagram no sooner than wednesday, because it appears staying under the sun all day made my brain kinda unreliable, as I managed to read 5/3 = 2.67 several times before finding that mistake
(DIR) Post #AYjPGnm8xf5wXzcNk0 by sten@chaos.social
2023-08-14T19:39:20Z
0 likes, 0 repeats
@Archivist @sotolf No rush!