Bottom Page

• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 How to simplify square finding program? meknowsnothing Programmer named Tim Posts: 10 Threads: 3 Joined: Feb 2019 Reputation: -1 Likes received: 0 #1 Mar-12-2019, 06:20 PM 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? hshivaraj Wafer-Thin Wafer Posts: 92 Threads: 10 Joined: Nov 2017 Reputation: 4 Likes received: 9 #2 Mar-12-2019, 10:56 PM 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 :/ meknowsnothing Programmer named Tim Posts: 10 Threads: 3 Joined: Feb 2019 Reputation: -1 Likes received: 0 #3 Mar-13-2019, 05:37 AM 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? meknowsnothing Programmer named Tim Posts: 10 Threads: 3 Joined: Feb 2019 Reputation: -1 Likes received: 0 #4 Jun-11-2019, 08:20 PM The code can be found on https://github.com/minkkilaukku/square-p...qPackMB.py . Just modify the lines M=13 N=9. « Next Oldest | Next Newest »

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)