Show HN: Slices – puzzle game

Post by eutectic » Thu, Dec 10, 2020, 12:57 AM UTC

klmadfejno wrote: post #58

siraben wrote: post #50

What would be an efficient solver for this problem, and what would the running time be? Seems like a naive solver would be too slow for this, could it be restated into finding the minimal number of cuts needed to fully disconnect a planar graph?

My gut intuition says you don't need to check the entire space of possible lines, just the lines between any two dots (rotated by an trivially small degree to separate the two), because a "correct" cut should always be defined by the bounds between which some dot on the border is included or excluded in a given cut. You also don't need to check each sequence of legal cuts. Most positions can be deduced to be unwinnab…

Post by klmadfejno » Thu, Dec 10, 2020, 3:15 AM UTC

eutectic wrote: post #71

klmadfejno wrote: post #58

Earlier quoted context omitted.

My gut intuition says you don't need to check the entire space of possible lines, just the lines between any two dots (rotated by an trivially small degree to separate the two), because a "correct" cut should always be defined by the bounds between which some dot on the border is included or excluded in a given cut. You also don't need to check each sequence of legal cuts. Most positions can be deduced to be unwinnab…

I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry. E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.

Post by jpcooper » Thu, Dec 10, 2020, 5:33 AM UTC

eutectic wrote: post #68

I was inspired to write a solver for this kind of puzzle (it's not pretty but it seems to work well): import numpy as np import z3 import matplotlib.pyplot as plt from sklearn.svm import LinearSVC from sklearn.cluster import KMeans def normalize(v): return v / np.sqrt(np.dot(v, v)) def line_normal(v): return np.array([v[1], -v[0]]) def line_segment_intersection_test(e0, e1): a, c, b, d = e0[0], e1[0], e0[1] - e0[0],…

Post by jpcooper » Thu, Dec 10, 2020, 6:15 AM UTC

eutectic wrote: post #76

jpcooper wrote: post #75

Earlier quoted context omitted.

Are you sure you can’t do this with a linear programme? Surely there is a way to encode the line choices, the partitions they create and the number of dots within those partitions as a linear programme. Might be fun to try. Edit: Outsourced to codegolf. Had to move the question to the sandbox, as I was unsure on grading. Will update when accepted.

Well,it is a set cover problem so you can use ILP and mip is actually much faster than z3. I'm sure it's possible (though maybe not easy) to use more geometry. I don't see how to make a simple linear program though.

Post by eutectic » Fri, Dec 11, 2020, 3:14 AM UTC

klmadfejno wrote: post #73

eutectic wrote: post #71

Earlier quoted context omitted.

I came up with basically this same idea independently when writing my solver (pasted in my top-level comment). It mostly works well, but it isn't obvious how to extend it to capture non-convex geometry. E.g. cutting off 2 ears to create 3 regions vs cutting off whole head to create 2 regions.

That's an impressive quick effort. My second initial gut reaction says you could add a point to the graph at the local minima of a non-convex curve and use it as a way to generate additional candidate, but not require the solver to eliminate it? Could probably smoosh an extra rule inn there somehow to eliminate pieces on that particular piece, but it wouldn't generalize to all non convex curves.