Bottom Page

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?
Quote
#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 :/
Quote
#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?
Quote
#4
The code can be found on https://github.com/minkkilaukku/square-p...qPackMB.py . Just modify the lines M=13 N=9.
Quote

Top Page

Possibly Related Threads...
Thread Author Replies Views Last Post
  Finding nearest point of a Multidigraph in Python 3.7 stixmagiggins 3 125 Aug-16-2019, 01:32 PM
Last Post: ThomasL
  Is it OK to use a context manager to simplify attribute access? nholtz 0 151 Jun-11-2019, 01:19 AM
Last Post: nholtz
  Help with finding correct topic in Python learning yahya01 1 284 Jun-06-2019, 05:01 PM
Last Post: buran
  Finding perfect numbers BillMcEnaney 6 450 Apr-04-2019, 04:46 AM
Last Post: BillMcEnaney
  Finding exact phrase in list graham23s 2 224 Mar-13-2019, 06:47 PM
Last Post: graham23s
  finding yesterday and tomorrrow without using date.time module apexman 10 549 Feb-25-2019, 05:33 AM
Last Post: samsonite
  Dijkstra code - trying to simplify it grandpapa10 1 262 Jan-23-2019, 12:43 PM
Last Post: Larz60+
  Finding phrases of one semantic meaning VladislavMz 2 283 Dec-20-2018, 03:29 AM
Last Post: VladislavMz
  finding problems connecting python to sqlite Dennis 1 295 Dec-10-2018, 02:58 PM
Last Post: Larz60+
  Finding files knollfinder 2 326 Dec-09-2018, 08:03 AM
Last Post: Gribouillis

Forum Jump:


Users browsing this thread: 1 Guest(s)