Fixed docstrings, added a couple of human_eval puzzles

akalai · akalai · commit f265d19ba84e · 2021-09-17T17:31:46.000-04:00
diff --git a/generators/chess.py b/generators/chess.py
@@ -180,10 +180,10 @@ def gen_random(self):
             self.add(dict(m=m, n=n, target=target))  # solved by someone
 
 
-class UNSOLVED_UncrossedKnightsPath(UncrossedKnightsPath):
+class UNSOLVED_UncrossedKnightsPath(PuzzleGenerator):
     """Uncrossed Knights Path (open problem, unsolved)
 
-    The goal of these problems is to *beat* the nxn_records from
+    Similar to above, but the goal of these problems is to *beat* the nxn_records from
     [http://ukt.alex-black.ru/](http://ukt.alex-black.ru/)
     (accessed 2020-11-29).
 
@@ -193,11 +193,37 @@ class UNSOLVED_UncrossedKnightsPath(UncrossedKnightsPath):
     unsolved_nxn_records = {10: 61, 11: 76, 12: 94, 13: 113, 14: 135, 15: 158,
                             16: 183, 17: 211, 18: 238, 19: 268, 20: 302, 21: 337, 22: 375, 23: 414}
 
+    @staticmethod
+    def sat(path: List[List[int]], m=10, n=10, target=62):
+        """Find a long (open) tour of knight moves on an m x n chess-board whose edges don't cross."""
+        def legal_move(m):
+            (a, b), (i, j) = m
+            return {abs(i - a), abs(j - b)} == {1, 2}
+
+        def legal_quad(m1, m2):  # non-overlapping test: parallel or bounding box has (width - 1) * (height - 1) >= 5
+            (i1, j1), (i2, j2) = m1
+            (a1, b1), (a2, b2) = m2
+            return (len({(i1, j1), (i2, j2), (a1, b1), (a2, b2)}) < 4  # adjacent edges in path, ignore
+                    or (i1 - i2) * (b1 - b2) == (j1 - j2) * (a1 - a2)  # parallel
+                    or (max(a1, a2, i1, i2) - min(a1, a2, i1, i2)) * (max(b1, b2, j1, j2) - min(b1, b2, j1, j2)) >= 5
+                    # far
+                    )
+
+        assert all(i in range(m) and j in range(n) for i, j in path), "move off board"
+        assert len({(i, j) for i, j in path}) == len(path), "visited same square twice"
+
+        moves = list(zip(path, path[1:]))
+        assert all(legal_move(m) for m in moves), "illegal move"
+        assert all(legal_quad(m1, m2) for m1 in moves for m2 in moves), "intersecting move pair"
+
+        return len(path) >= target
+
+
     def gen(self, target_num_instances):
-        for count, n in enumerate(self.nxn_records):
+        for n in self.unsolved_nxn_records:
             if len(self.instances) >= target_num_instances:
                 return
-            self.add(dict(m=n, n=n, target=self.nxn_records[n] + 1))  # Note the +1 means breaking the record!
+            self.add(dict(m=n, n=n, target=self.unsolved_nxn_records[n] + 1))  # Note the +1 means breaking the record!
 
 
 if __name__ == "__main__":
diff --git a/generators/codeforces.py b/generators/codeforces.py
@@ -1048,6 +1048,7 @@ class CombinationLockObfuscated(CombinationLock):
 
     @staticmethod
     def sat(states: List[str], start="012", combo="329", target_len=6):
+        """Figure out what this does only from the code"""
         return all(sum((int(a[i]) - int(b[i])) ** 2 % 10 for i in range(len(start))) == 1
                    for a, b in zip([start] + states, states[:target_len] + [combo]))
 
diff --git a/generators/human_eval.py b/generators/human_eval.py
@@ -2556,7 +2556,6 @@ def gen_random(self):
         self.add(dict(n=n))
 
 
-
 class HexPrimes(PuzzleGenerator):
     """Inspired by [HumanEval](https://github.com/openai/human-eval) \\#78"""
 
@@ -2587,7 +2586,7 @@ def sat(b: str, n=5324680297138495285):
         assert inside[0] == "1" or len(inside) == 1
         m = 0
         for c in inside:
-            m = 2*m + int(c)
+            m = 2 * m + int(c)
         return m == n
 
     @staticmethod
@@ -2601,6 +2600,93 @@ def gen_random(self):
         self.add(dict(n=n))
 
 
+class NearbyDuplicates(PuzzleGenerator):
+    """Inspired by [HumanEval](https://github.com/openai/human-eval) \\#80"""
+
+    @staticmethod
+    def sat(indices: List[int], s="I am an unhappy string!"):
+        """A string is happy if every three consecutive characters are distinct. Find two indices making s unhappy."""
+        i, j = indices
+        return s[i] == s[j] and 0 <= i < j < i + 3
+
+    @staticmethod
+    def sol(s):
+        for i in range(len(s) - 2):
+            if s[i] == s[i + 1]:
+                return [i, i + 1]
+            if s[i] == s[i + 2]:
+                return [i, i + 2]
+
+    def gen_random(self):
+        a = self.random.string(min_len=1)
+        s = a + self.random.choice(["", self.random.char()]) + a[-1] + self.random.string(min_len=1)
+        self.add(dict(s=s))
+
+
+class Grader(PuzzleGenerator):
+    """Inspired by [HumanEval](https://github.com/openai/human-eval) \\#81"""
+
+    @staticmethod
+    def sat(grades: List[str], gpas=[2.8, 3.1, 4.0, 2.2, 3.1, 2.5, 0.9]):
+        """
+        Convert GPAs to letter grades according to the following table:
+        4.0: A+
+        3.7: A
+        3.4: A-
+        3.0: B+
+        2.7: B
+        2.4: B-
+        2.0: C+
+        1.7: C
+        1.4: C-
+        below: F
+
+        Sample input: [4.0, 3.5, 3.8]
+        Sample output: ['A+', 'A-', 'A']
+        """
+        assert len(grades) == len(gpas)
+        letters = ['A+', 'A', 'A-', 'B+', 'B', 'B-', 'C+', 'C', 'C-', 'F']
+        scores = [4.0, 3.7, 3.4, 3.0, 2.7, 2.4, 2.0, 1.7, 1.4, 0.0]
+        for grade, gpa in zip(grades, gpas):
+            i = letters.index(grade)
+            assert gpa >= scores[i]
+            assert i == 0 or gpa <= scores[i - 1]
+        return True
+
+    @staticmethod
+    def sol(gpas):
+        letters = ['A+', 'A', 'A-', 'B+', 'B', 'B-', 'C+', 'C', 'C-', 'F']
+        scores = [4.0, 3.7, 3.4, 3.0, 2.7, 2.4, 2.0, 1.7, 1.4, 0.0]
+        ans = []
+        for gpa in gpas:
+            i = 0
+            while gpa < scores[i]:
+                i += 1
+            ans.append(letters[i])
+        return ans
+
+    def gen_random(self):
+        gpas = [self.random.random() * 4.0 for _ in range(self.random.randrange(10))]
+        self.add(dict(gpas=gpas))
+
+
+class FactorString(PuzzleGenerator):
+    """Inspired by [HumanEval](https://github.com/openai/human-eval) \\#82"""
+
+    @staticmethod
+    def sat(factor: str, s="catscatcatscatcatscat"):
+        """Find a string which when repeated more than once gives s"""
+        return len(factor) < len(s) and s == factor * (len(s) // len(factor))
+
+    @staticmethod
+    def sol(s):
+        n = len(s)
+        return next(s[:i] for i in range(1, len(s)) if s == s[:i] * (n // i))
+
+    def gen_random(self):
+        s = self.random.pseudo_word() * self.random.randrange(2, 10)
+        self.add(dict(s=s))
+
 
 if __name__ == "__main__":
     PuzzleGenerator.debug_problems()
diff --git a/generators/number_theory.py b/generators/number_theory.py
@@ -11,13 +11,13 @@
 class FermatsLastTheorem(PuzzleGenerator):
     """[Fermat's last theorem](https://en.wikipedia.org/w/index.php?title=Fermat%27s_Last_Theorem)
 
-    Find integers a,b,c > 0, n > 2, such such that `a ** n + b ** n == c ** n`
     Supposedly unsolvable, but how confident are really in the super-complicated proof?
 
     See [Wiles, Andrew. "Modular elliptic curves and Fermat's last theorem." Annals of mathematics 141.3 (1995): 443-551.](https://www.jstor.org/stable/2118559)"""
 
     @staticmethod
     def sat(nums: List[int]):
+        """Find integers a,b,c > 0, n > 2, such such that a^n + b^n == c^n"""
         a, b, c, n = nums
         return (a ** n + b ** n == c ** n) and min(a, b, c) > 0 and n > 2
 
@@ -28,12 +28,11 @@ class GCD(PuzzleGenerator):
     """[Greatest Common Divisor](https://en.wikipedia.org/w/index.php?title=Greatest_common_divisor&oldid=990943381)
     (GCD)
 
-    Find the greatest common divisor of two integers.
-
     See also the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)"""
 
     @staticmethod
     def sat(n: int, a=15482, b=23223, lower_bound=5):
+        """Find a large common divisor of two integers."""
         return a % n == 0 and b % n == 0 and n >= lower_bound
 
     @staticmethod
@@ -66,12 +65,11 @@ class GCD_multi(PuzzleGenerator):
     """[Greatest Common Divisor](https://en.wikipedia.org/w/index.php?title=Greatest_common_divisor&oldid=990943381)
     (GCD)
 
-    Find the greatest common divisor of a *list* of integers.
-
     See also the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)"""
 
     @staticmethod
     def sat(n: int, nums=[77410, 23223, 54187], lower_bound=2):
+        """Find a large common divisor of the list of integers."""
         return all(i % n == 0 for i in nums) and n >= lower_bound
 
     @staticmethod
@@ -96,12 +94,11 @@ class LCM(PuzzleGenerator):
     """[Least Common Multiple](https://en.wikipedia.org/wiki/Least_common_multiple)
     (LCM)
 
-    Find the least common multiple of two integers.
-
     See also the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)"""
 
     @staticmethod
     def sat(n: int, a=15, b=27, upper_bound=150):
+        """Find a small common multiple of two integers."""
         return n % a == 0 and n % b == 0 and 0 < n <= upper_bound
 
     @staticmethod
@@ -123,12 +120,11 @@ class LCM_multi(PuzzleGenerator):
     """[Least Common Multiple](https://en.wikipedia.org/wiki/Least_common_multiple)
     (LCM)
 
-    Find the least common multiple of a list of integers.
-
     See also the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)"""
 
     @staticmethod
     def sat(n: int, nums=[15, 27, 102], upper_bound=5000):
+        """Find a small common multiple of a list of integers."""
         return all(n % i == 0 for i in nums) and n <= upper_bound
 
     @staticmethod
@@ -152,15 +148,14 @@ def gen_random(self):
 class SmallExponentBigSolution(PuzzleGenerator):
     """Small exponent, big solution
 
-    Solve for n: b^n = target (mod n)
-
     Problems have small b and target but solution is typically a large n.
     Some of them are really hard, for example, for `b=2, target=3`, the smallest solution is `n=4700063497`
 
     See [Richard K. Guy "The strong law of small numbers", (problem 13)](https://doi.org/10.2307/2322249)"""
 
     @staticmethod
     def sat(n: int, b=2, target=5):
+        """Solve for n: b^n = target (mod n)"""
         return (b ** n) % n == target
 
     @staticmethod
@@ -205,6 +200,7 @@ class ThreeCubes(PuzzleGenerator):
 
     @staticmethod
     def sat(nums: List[int], target=10):
+        """Given n, find integers a, b, c such that a^3 + b^3 + c^3 = n."""
         assert target % 9 not in [4, 5], "Hint"
         return len(nums) == 3 and sum([i ** 3 for i in nums]) == target
 
diff --git a/generators/trivial_inverse.py b/generators/trivial_inverse.py
@@ -661,9 +661,9 @@ def gen_random(self):
 
 
 class IntNegSquareRoot(PuzzleGenerator):
-    """Find a negative integer that when squared equals perfect-square a."""
     @staticmethod
     def sat(n: int, a=10000200001):
+        """Find a negative integer that when squared equals perfect-square a."""
         return a == n * n and n < 0
 
     @staticmethod
diff --git a/make_dataset.py b/make_dataset.py
@@ -57,7 +57,6 @@ def save_readme(gen_modules, filename):
         n = len(puzzles)
         link = f"[{sec_name}](#{sec_name.lower().replace(' ', '-')})"
         n_instances = sum(p["n_instances"] for p in puzzles)
-        tot_instances += len(puzzles)
         tot_instances += n_instances
         table += f"- [{sec_name} ({len(puzzles):,} problems, {n_instances:,} instances)](#{sec_name.lower().replace(' ', '-')})\n"
         for i, puzzle in enumerate(puzzles):
@@ -138,10 +137,15 @@ def main(args):
             "examples": examples
         }
 
+    for p in puzzles:
+        if p["sat"] == utils.remove_docstring(p["sat"]):
+            print(p["sat"])
+            assert False, f"Puzzle {p['name']} in {p['module']} doesn't have a valid docstring"
+
     utils.save_json(puzzles, args.json, make_dirs_if_necessary=True, indent=2)
     save_readme(summaries, args.readme)
     utils.info(f"Elapsed time: {(time.perf_counter() - start_time) / 60:.2f} minutes")
-
+    utils.info(f"Saved {len(puzzles)} to {args.json} and {args.readme}")
 
 if __name__ == "__main__":
     args = parser.parse_args()
diff --git a/puzzle_generator.py b/puzzle_generator.py
@@ -362,8 +362,8 @@ def add_test(self, sol_src, run_test_type=False):
         """Assert that the solution satisfies the given instance and add the solution to the instance.
         Do a round-trip json encoding/decoding to mimic the actual test and deter strange attacks.
         Ideally this could be done by running a protected process (like in evaluating programming
-        contest submissions) but that is much slower so we will only add that later if the AI
-        starts misbehaving."""
+        contest submissions) but that is much slower. Since this is a test we authored presumably it has
+        no evil code."""
 
         if sol_src in self.sol_srcs:  # already added this solution
             return
diff --git a/puzzles/README.md b/puzzles/README.md
diff --git a/puzzles/puzzles.json b/puzzles/puzzles.json
diff --git a/utils.py b/utils.py
