Python Forum
How to simplify square finding program?
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
How to simplify square finding program?
#1
I found this problem in a programming forum Ohjelmointiputka:

https://www.ohjelmointiputka.net/postit/...nus=ahdruu and
https://www.ohjelmointiputka.net/postit/...us=ahdruu2

Somebody said that there is a solution found by a computer, but I was unable to find a proof.

Find the smallest rectangle digits such that one can read the squares of the numbers 1, 2, ..., 100.

Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.

But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.

What kind of algorithm will find the matrix?

I saw from https://stackoverflow.com/questions/3382...ng-problem that the following program solves the problem in the case 11x11:

#
# An attempt to solve a nice problem from SO using a random search approach
#
# The problem is to place the squares of all numbers from 1 to 100 in
# a 11x11 grid writing them either horizontally, vertically or in diagonal.
# 11*11 is only 121 and this means that the required packing is very tight
# (the total number of digits is 358, giving that on average each grid
# cell needs to be used for 2.95 different square numbers).
#
# Do whatever you want with this code, just don't blame me if it doesn't
# do what you think or if it even doesn't do what I say it does.
#
# Andrea "6502" Griffini
#

import random, time, sys

N = 11
K = 100

# These are the numbers we would like to pack
numbers = [str(i*i) for i in xrange(1, K+1)]

# Build the global list of digits (used for weighted random guess)
digits = "".join(numbers)

def random_digit(n=len(digits)-1):
    return digits[random.randint(0, n)]

# By how many lines each of the numbers is currently covered
count = dict((x, 0) for x in numbers)

# Number of actually covered numbers
covered = 0

# All lines in current position (row, cols, diags, counter-diags)
lines = (["*"*N for x in xrange(N)] +
         ["*"*N for x in xrange(N)] +
         ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)] +
         ["*"*x for x in xrange(1, N)] + ["*"*x for x in xrange(N, 0, -1)])

# lines_of[x, y] -> list of line/char indexes
lines_of = {}
def add_line_of(x, y, L):
    try:
        lines_of[x, y].append(L)
    except KeyError:
        lines_of[x, y] = [L]
for y in xrange(N):
    for x in xrange(N):
        add_line_of(x, y, (y, x))
        add_line_of(x, y, (N + x, y))
        add_line_of(x, y, (2*N + (x + y), x - max(0, x + y - N + 1)))
        add_line_of(x, y, (2*N + 2*N-1 + (x + N-1 - y), x - max(0, x + (N-1 - y) - N + 1)))

# Numbers covered by each line
covered_numbers = [set() for x in xrange(len(lines))]

# Which numbers the string x covers
def cover(x):
    c = x + "/" + x[::-1]
    return [y for y in numbers if y in c]

# Set a matrix element
def setValue(x, y, d):
    global covered
    for i, j in lines_of[x, y]:
        L = lines[i]
        C = covered_numbers[i]
        newL = L[:j] + d + L[j+1:]
        newC = set(cover(newL))
        for lost in C - newC:
            count[lost] -= 1
            if count[lost] == 0:
                covered -= 1
        for gained in newC - C:
            count[gained] += 1
            if count[gained] == 1:
                covered += 1
        covered_numbers[i] = newC
        lines[i] = newL

def do_search(k, r):
    start = time.time()

    for i in xrange(r):
        x = random.randint(0, N-1)
        y = random.randint(0, N-1)
        setValue(x, y, random_digit())

    best = None
    attempts = k
    while attempts > 0:
        attempts -= 1
        x = random.randint(0, N-1)
        y = random.randint(0, N-1)
        old = lines[y][x]
        setValue(x, y, random_digit())
        if best is None or covered > best[0]:
            now = time.time()
            sys.stdout.write(str(covered) + chr(13))
            sys.stdout.flush()
            attempts = k
        if best is None or covered >= best[0]:
            best = [covered, lines[:N][:]]
        else:
            setValue(x, y, old)
    print
    sys.stdout.flush()
    return best

for y in xrange(N):
    for x in xrange(N):
        setValue(x, y, random_digit())

best = None
while True:
    if best is not None:
        for y in xrange(N):
            for x in xrange(N):
                setValue(x, y, best[1][y][x])
    x = do_search(100000, N)
    if best is None or x[0] > best[0]:
        print x[0]
        print "\n".join(" ".join(y) for y in x[1])
    if best is None or x[0] >= best[0]:
        best = x[:]
But how this can be generalized to solve the problem in non-square cases? I heard that the squares if integers 1–100 can be put to the grid of 117 elements (https://www.ohjelmointiputka.net/postit/...us=ahdruu2) . And how this code can be simplified?
Reply
#2
This is a interesting problem. Would be good if I could read the actual problem from the links provided and if they were in english. I mean i could spend next 30mins or more to understand the logic behind the code. But I dont have that time :/
Reply
#3
Oh. Sorry. The problem is like this:

Find a grid of size 9x13 with following properties:

1. Every cell contains a digit in base 10.

2. One can read the numbers from the grid by selecting a starting square, go to one of its 8 nearest grid, maintain that direction and concatenate numbers. By reading the grid one can find the squares of 1 to 100. For every number, you can choose where to start finding the number and which direction you go (8 possibilities).

For example, if we have the following grid:

340934433
324324893
455423343

Then one can select the leftmost upper number 3 and select direction to the right and down to read numbers 3, 32 and 325. Similarly from the second row and first column one can read numbers like 33, 34, 32, 324, 3243, ...

Now, one can find that the minimal grid that contains the squares of 1 to 10, is

00182
36495

The problem has two versions. First asks to find a minimal grid that contains squares of 1 to 20 and second asks to find squares of 1 to 100.

The code I posted solves the second version in the case 11x11 grid. But one can write the code in a cleaner way. And I think it tries to solve the problem for only square cases. It would be nice to learn what kind on algorithm would put the squares of 1 to 100 to a grid of size 117 elements? Like does a "semirandom" search like the code above works, what is exactly a "semirandom search algorithm" or can this be solved by, say, simulated annealing, genetic algorithm, or bin packing algorithm?
Reply
#4
The code can be found on https://github.com/minkkilaukku/square-p...qPackMB.py . Just modify the lines M=13 N=9.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Im at square one even with trying to install python origen 1 322 Jan-12-2024, 05:39 AM
Last Post: ndc85430
  I want to simplify this python code into fewer lines, it's about string mandaxyz 5 2,047 Jan-15-2022, 01:28 PM
Last Post: mandaxyz
Thumbs Up [SOLVED] Simplify condition test in if block? Winfried 2 1,675 Aug-25-2021, 09:42 PM
Last Post: Winfried
  square root of 5 input numbers mrityunjoy 1 1,995 Jun-10-2020, 11:08 AM
Last Post: perfringo
  square root of 6 input numbers mrityunjoy 3 2,557 Jun-07-2020, 06:35 AM
Last Post: ndc85430
  How can i simplify this code Jezani_VIII 4 2,716 Aug-25-2019, 02:23 PM
Last Post: perfringo
  Is it OK to use a context manager to simplify attribute access? nholtz 0 2,022 Jun-11-2019, 01:19 AM
Last Post: nholtz
  Dijkstra code - trying to simplify it grandpapa10 1 2,135 Jan-23-2019, 12:43 PM
Last Post: Larz60+
  cropping a picture (always square) Leon 1 2,104 Aug-13-2018, 10:04 AM
Last Post: Leon
  Error when trying to square a number pistacheoowalnuttanker 5 3,767 Jul-20-2018, 02:23 AM
Last Post: pistacheoowalnuttanker

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020