2D binary list python

Question

I'm having trouble making a function that places a number inside a binary grid. For instance, if i'm given 4 3 2 1, and I have a grid that is 5x5, it would look like the following...

My current code reads a text file and creates a list that is arranged in descending order. For instance if the text file contained 1 2 3, it would create a list of integers 3 2 1. Also my code prompts for a bin # which creates a binxbin square. I don't know how to actually place in a number 4 for the bin. This is the function that should place in the values which i'm stuck with.

def isSpaceFree(bin, row, column, block):
    if row + block > len(bin):
        return False
    if column + block > len(bin):
        return False
    if bin[row][column] == 0 :
        return True
    else:
        return False
    for r in range(row, row+block):
        if bin[row][column] != 0:

In what sense is this a binary list? I'm confused - what do you want to put in your square? The number 4? — Brionius
– Brionius, Commented Oct 22, 2013 at 15:10
So if the number 4 is the first number in the list, it will create a 4x4 block. The original list just contains 0s in the 5x5 bin. The 4 will replace the 0's. And it will start again from the top to check the 3 and 2 and 1. — steve
– steve, Commented Oct 22, 2013 at 15:12
I'm very confused. In what sense does the sequence 4 3 2 1, 1 2 3 or 3 2 1 have anything to do with how you fill the 5x5 grid? Is it always a 5x5 grid? — Justin Jasmann
– Justin Jasmann, Commented Oct 22, 2013 at 15:13
The 5x5 grid is created with a bin value. I didn't include it but the main function prompts for a bin value and uses list comprehension to create a 5x5 grid if I put in 5 for the bin. The 4 3 2 1 is used in the example. But What I meant by the 123 and 321 is that my main function also opens a word file and sorts the list in descending order so that the biggest number comes first and then it moves down the list. — steve
– steve, Commented Oct 22, 2013 at 15:15
I'm guessing you're trying to do bin packing? As in, user input "4 3 2 1" means, "try to fit this 4x4 block in the bin given, followed by a 3x3 block, then a 2x2 block, then a 1x1 block". Is that right? And in your example, you can only fit a 4x4 and 1x1 block in the bin, so the other two are left out? — Kevin
– Kevin, Commented Oct 22, 2013 at 15:17

Kevin · Accepted Answer · 2013-10-22 15:34:38Z

1

It sounds like isSpaceFree should return True if you can create a square with origin origin (row, column) and size block, without going out of bounds or overlapping any non-zero elements. In which case, you're 75% of the way there. You have the bounds checking ready, and half of the overlap check loop.

def isSpaceFree(bin, row, column, block):
    #return False if the block would go out of bounds
    if row + block > len(bin):
        return False
    if column + block > len(bin):
        return False

    #possible todo:
    #return False if row or column is negative

    #return False if the square would overlap an existing element
    for r in range(row, row+block):
        for c in range(column, column+block):
            if bin[r][c] != 0: #oops, overlap will occur
                return False

    #square is in bounds, and doesn't overlap anything. Good to go!
    return True

Then, actually placing the block is the same double-nested loop, but instead performing an assignment.

def place(bin, row, column, block):
    if isSpaceFree(bin, row, column, block):
        for r in range(row, row+block):
            for c in range(column, column+block):
                bin[r][c] = block

x = [
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
]

place(x, 0, 0, 4)

print "\n".join(str(row) for row in x)

Result:

[4, 4, 4, 4, 0]
[4, 4, 4, 4, 0]
[4, 4, 4, 4, 0]
[4, 4, 4, 4, 0]
[0, 0, 0, 0, 0]

edited Oct 22, 2013 at 15:34

answered Oct 22, 2013 at 15:29

Kevin

76.5k13 gold badges141 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

steve Over a year ago

Hey @kevin, thanks for the help. I'm having trouble with 2 things. The first is that I have a list block[] which contains 4 3 2 1 and I want it to automatically do 4 first and see if it fits, if it does then move onto 3 and stop when it can't fit anymore blocks. The second is how would I define column and rows in my main function?

Kevin Over a year ago

Sorry, I only know enough about the bin packing problem to provide the functions I've given. Actually solving the problem is somewhat beyond my expertise :-)

Collectives™ on Stack Overflow

2D binary list python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related