Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

bug in min-cut caused by destructive mutation from sort #14

Open
bo-tato opened this issue Jan 19, 2024 · 0 comments · May be fixed by #15
Open

bug in min-cut caused by destructive mutation from sort #14

bo-tato opened this issue Jan 19, 2024 · 0 comments · May be fixed by #15

Comments

@bo-tato
Copy link

bo-tato commented Jan 19, 2024

I was doing advent of code, day 25: https://adventofcode.com/2023/day/25
the test data is:

(let ((g (make-instance 'graph)))
  (graph:populate
   g
   :nodes '(jqt rhn xhk nvd rsh frs pzl lsr hfx cmg qnr lhk bvb ntq rzs)
   :edges-w-values '(((jqt rhn) . 1)
                     ((jqt xhk) . 1)
                     ((jqt nvd) . 1)
                     ((rsh frs) . 1)
                     ((rsh pzl) . 1)
                     ((rsh lsr) . 1)
                     ((xhk hfx) . 1)
                     ((cmg qnr) . 1)
                     ((cmg nvd) . 1)
                     ((cmg lhk) . 1)
                     ((cmg bvb) . 1)
                     ((rhn xhk) . 1)
                     ((rhn bvb) . 1)
                     ((rhn hfx) . 1)
                     ((bvb xhk) . 1)
                     ((bvb hfx) . 1)
                     ((pzl lsr) . 1)
                     ((pzl hfx) . 1)
                     ((pzl nvd) . 1)
                     ((qnr nvd) . 1)
                     ((ntq jqt) . 1)
                     ((ntq hfx) . 1)
                     ((ntq bvb) . 1)
                     ((ntq xhk) . 1)
                     ((nvd lhk) . 1)
                     ((lsr lhk) . 1)
                     ((rzs qnr) . 1)
                     ((rzs cmg) . 1)
                     ((rzs lsr) . 1)
                     ((rzs rsh) . 1)
                     ((frs qnr) . 1)
                     ((frs lhk) . 1)
                     ((frs lsr) . 1)))
  (graph:min-cut g))

min-cut returns different results each time, only sometimes finding the correct result of 3.
This seems to be caused from the mutation side-effect of sort, in graph.lisp:

(loop :while rest :do
              ;; grow A by adding the node most tightly connected to A
              (let ((new (car (sort rest #'> :key {connection-weight a}))))
                (setf rest (remove new rest))
                (push new a)))

changing it to (sort (copy-tree rest) ... and it returns the correct result every time.

@bo-tato bo-tato linked a pull request Jan 19, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant