NNlk05's Big-Bag-'o'-Scripts™

[NNlk05]

NNlk05's Big-Bag-'o'-Scripts™
This thread is for all of my scripts, its modifications thereof, my ideas about scripts, and any discussion about any above.
Instead of creating tons of threads regarding all of my scripts, I decided to create one Big-Bag-'o'-Scripts™ to keep the Forums tidy.
Links to scripts

• OR-Tools still life searcher

[NNlk05]

OR-Tools still lifes searcher
This was intended to to find max-density still lifes and later modded to find still lifes with a certain population.
Setup
Try these in order:

Code: Select all

python3 -m pip install ortools
python -m pip install ortools
pip3 install ortools
pip install ortools

Code

Code: Select all

"""
OR-Tools still life searcher
By: NNlk05

Find still lifes in Conway's Game of Life

Versions:
1.0.0 (2026-7-17): Release

OR-Tools still life searcher - Find still lifes in Conway's Game of Life
Copyright (C) 2026 NNlk05

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""

import argparse
from ortools.sat.python import cp_model
from sys import exit, stderr
from platform import system

def get_python_exe() -> str:
    current_system = system()
    if current_system == "Linux":
        return "python"
    if current_system == 'Windows':
        return 'py'
    if current_system == 'Darwin':
        return "python3"
    return "python"

def print_error(message: str) -> None:
    print(f"{message} Exiting.", file=stderr)
    exit(1)

def parse_args() -> tuple[int, int, int | None, bool, bool]:
    parser = argparse.ArgumentParser(
        prog=get_python_exe() + " " + __file__,
        description="""
        OR-Tools still life searcher
        By: NNlk05
        Find still lifes in Conway's Game of Life
        """
    )
    parser.add_argument("x", type=int, help="Grid width")
    parser.add_argument("y", type=int, help="Grid height")
    parser.add_argument(
        "cells",
        nargs="?",
        type=int,
        default=None,
        help="Optional: Target number of live cells (if not specified, maximizes population)"
    )
    parser.add_argument(
        "-a", "--all",
        action="store_true",
        help="Print all solutions without prompting"
    )
    parser.add_argument(
        "-y", "--yes",
        action="store_true",
        help="Print all solutions without prompting (alias for --all)"
    )
    parser.add_argument(
        "-q", "--quiet",
        action="store_true",
        help="Skip the 'Population: x' message"
    )
    
    try:
        args = parser.parse_args()
    except SystemExit:
        raise
    
    if args.x <= 0 or args.y <= 0:
        print_error("Grid dimensions must be positive integers!")
    
    if args.cells is not None and args.cells <= 0:
        print_error("Cell count must be a positive integer!")
    
    all_solutions = args.all or args.yes
    
    return args.x, args.y, args.cells, all_solutions, args.quiet


class Grid:
    def __init__(self, x: int, y: int):
        self.x: int = x
        self.y: int = y

        self.grid: list[list[int]] = [
            [0 for _ in range(x)] for _ in range(y)
        ]

    def __str__(self) -> str:
        output: str = ""
        for row in self.grid:
            for cell in row:
                if cell == 1:
                    output += "O"
                elif cell == 0:
                    output += "."
                else:
                    print_error("Invalid value in Grid!")
            output += "\n"
        return output
    
    def pop(self) -> int:
        pop: int = 0
        for row in self.grid:
            for cell in row:
                if cell == 1:
                    pop += 1
                elif cell == 0:
                    pass
                else:
                    print_error("Invalid value in Grid!")
        return pop
    
    def is_still(self, x: int, y: int) -> bool:
        if not (0 <= x < self.x and 0 <= y < self.y):
            print_error(f"Coordinates ({x}, {y}) out of grid bounds!")

        count: int = 0
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                if dx == 0 and dy == 0:
                    continue 
                
                nx: int = x + dx
                ny: int = y + dy
                if 0 <= nx < self.x and 0 <= ny < self.y:
                    if self.grid[ny][nx] == 1:
                        count += 1

        current_state: int = self.grid[y][x]
        if current_state == 1:
            return count in (2, 3)
        elif current_state == 0:
            return count == 3
        else:
            print_error("Invalid value in Grid!")
            return False


def main() -> None:
    x, y, target_cells, all_solutions, quiet = parse_args()
    
    padded_x: int = x + 2
    padded_y: int = y + 2
    
    model: cp_model.CpModel = cp_model.CpModel()
    
    grid: Grid = Grid(x, y)
    grid_vars: list[list[cp_model.IntVar]] = [
        [model.NewIntVar(0, 1, f"cell_{i}_{j}") for j in range(padded_x)]
        for i in range(padded_y)
    ]
    
    for i in range(padded_y):
        for j in range(padded_x):
            if i == 0 or i == padded_y - 1 or j == 0 or j == padded_x - 1:
                model.Add(grid_vars[i][j] == 0)
    
    for i in range(padded_y):
        for j in range(padded_x):
            neighbors: list[cp_model.IntVar] = []
            for di in (-1, 0, 1):
                for dj in (-1, 0, 1):
                    if di == 0 and dj == 0:
                        continue
                    ni: int = i + di
                    nj: int = j + dj
                    if 0 <= ni < padded_y and 0 <= nj < padded_x:
                        neighbors.append(grid_vars[ni][nj])
            
            neighbor_sum: cp_model.IntVar = model.NewIntVar(0, 8, f"neighbors_{i}_{j}")
            model.Add(neighbor_sum == sum(neighbors))
            
            cell: cp_model.IntVar = grid_vars[i][j]
            
            model.Add(neighbor_sum >= 2).OnlyEnforceIf(cell)
            model.Add(neighbor_sum <= 3).OnlyEnforceIf(cell)
            
            model.Add(neighbor_sum != 3).OnlyEnforceIf(cell.Not())
    
    interior_sum = sum(
        grid_vars[i][j]
        for i in range(1, padded_y - 1)
        for j in range(1, padded_x - 1)
    )
    
    if target_cells is not None:
        model.Add(interior_sum == target_cells)
    else:
        model.Maximize(interior_sum)
    
    solver: cp_model.CpSolver = cp_model.CpSolver()
    status: cp_model.CpSolverStatus = solver.Solve(model)
    
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        if target_cells is None:
            optimal_pop = int(solver.ObjectiveValue())
            model.Add(interior_sum == optimal_pop)
        
        while True:
            for i in range(y):
                for j in range(x):
                    grid.grid[i][j] = int(solver.Value(grid_vars[i + 1][j + 1]))
            print(grid)
            if not quiet:
                print(f"Population: {grid.pop()}")
            
            if all_solutions:
                forbid_clause = []
                for i in range(1, padded_y - 1):
                    for j in range(1, padded_x - 1):
                        if solver.Value(grid_vars[i][j]) == 1:
                            forbid_clause.append(grid_vars[i][j].Not())
                        else:
                            forbid_clause.append(grid_vars[i][j])
                model.AddBoolOr(forbid_clause)
                
                status = solver.Solve(model)
                if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
                    print("\nNo more unique solutions found.")
                    break
            else:
                ans = input("Another solution (Y/n)? ").strip().lower()
                if ans != 'n':
                    break
                
                forbid_clause = []
                for i in range(1, padded_y - 1):
                    for j in range(1, padded_x - 1):
                        if solver.Value(grid_vars[i][j]) == 1:
                            forbid_clause.append(grid_vars[i][j].Not())
                        else:
                            forbid_clause.append(grid_vars[i][j])
                model.AddBoolOr(forbid_clause)
                
                status = solver.Solve(model)
                if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
                    print("\nNo more unique solutions with the same population found.")
                    break
    else:
        print_error("No solution found!")


if __name__ == "__main__":
    main()

Usage:

Code: Select all

positional arguments:
  x            Grid width
  y            Grid height
  cells        Optional: Target number of live cells (if not specified, maximizes population)

options:
  -h, --help   show this help message and exit
  -a, --all    Print all solutions without prompting
  -y, --yes    Print all solutions without prompting (alias for --all)
  -q, --quiet  Skip the 'Population: x' message

[NNlk05]

OR-Tools still lifes searcher

Here's 5 (out of many) 10x10 cases as a benchmark found by my program first with LifeWiki's version:

Code: Select all

x = 29, y = 58, rule = B3/S23
ob2ob2ob2o9bob2ob2ob2o$2ob2obob2o9b2ob2obob2o$6bo18bo$4ob2ob2o9b2ob3o
b3o$o2bobo2b2o10bobo2bo2bo$bobo2bo12bo2bo2bobo$2ob3ob3o9b3ob3ob2o$6bo
2bo12bo$2ob2obobo10b2obob2ob2o$2obob2ob2o9b2ob2ob2obo3$ob2ob2ob2o$2ob
2obob2o$6bo$4ob2ob2o$o2bobo2b2o$bobo2bo$2ob3ob3o$o5bo2bo$bob2obobo$2o
bob2ob2o3$o2bob2ob2o$5obobo$6bo2bo$4obob3o$o2bob2o$bobo4b2o$2ob4ob2o$
6bo$2ob2obob2o$2ob2ob2obo3$o2bob2ob2o$5obob2o$6bo$4ob2ob2o$o2bobo2b2o
$bobo2bo$2ob3ob3o$o5bo2bo$bob2obobo$2obob2ob2o3$ob2ob2ob2o$2ob2obob2o
$6bo$5obob2o$o3bobob2o$bobo2bo$2ob3ob3o$o5bo2bo$bob2obobo$2obob2ob2o!

I wonder if any is synthable.

[NNlk05]

I realized there's a big space-time tradeoff in spaceship searching. One way to deal with that is using the Meet-in-the-Middle attack, in my other field of expertise, I've seen that MitM allows a 2^64 brute force that will normally take years to take less then a minute in WASM.
(Note: I'm not meaning this as a modification to the xfind family of programs. They already use way too much memory.)
Is there a way to apply MitM to spaceship searching?

I just realized ikpx2 already uses MitM... just not the way I exepected it to.