Problem 42708. Placing Beads Neatly in a Box

Created by Ned Gulley

Solve Later

You are given a string of n black and white beads. Your job is to pack them neatly into a square box. "Neatly" in this case means that all the black beads are at the bottom, and all the white beads are at the top.
Half the beads are black, and half are white. The number of beads n will always be an even number perfect square (4, 16, 36, ...). Black beads are 1, and white beads are 0, so a string might look like this.
 str = [0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1]
Return a square matrix bx that indexes into str such that
 str(bx) = [ 0 0 0 0
             0 0 0 0
             1 1 1 1
             1 1 1 1 ]
The matrix bx consists of the numbers 1 through n snaking through the box in a 4-connected sense (see Cody Problem 42705, Is It a Snake?).
Here's one solution for the string shown above.
 bx = [ 1  8  9 10 
        2  7 12 11
        3  6 13 14
        4  5 16 15 ]
In general the answers are not unique. I will be checking that bx contains the numbers 1 through n, that they form a snake, and that when used with the string of beads, they result in a tidy ones-on-the-bottom formation.
I am grateful to the solvers of problem 42705 for giving me nice short code to use in my test suite for this problem!

Solve

Solution Stats

43 Solutions
13 Solvers

Last Solution submitted on Dec 19, 2024

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Alfonso Nieto-Castanon on 23 Jan 2016

note: the "is it sneaky?" part of the testsuite is not really a complete test (e.g. the matrix [1 2 3; 4 5 6; 7 8 9] would pass that). Using "complex(I,J)" instead of "I+J" would fix this.

Ned Gulley on 25 Jan 2016

Thanks Alfonso! Advice taken.

Ned Gulley on 25 Jan 2016

You also gave me a new test for "Is it Snaky (42705)" that knocked out the current leader.

Carl Witthoft on 27 Jan 2016

Can you clarify: does the partial sequence 1-1-0-1 force a failure? Your diagram doesn't seem to allow diagonal paths, so it seems that a single 0 or 1 causes failure.

Ned Gulley on 28 Jan 2016

Hi Carl: All sequences are generated from successful packings. So you wouldn't get 1-1-0-1 because, as you note, it couldn't be packed successfully. In other words, this situation shouldn't come up.

Solution Comments

Show comments

Problem Recent Solvers13

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 42708. Placing Beads Neatly in a Box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 42708. Placing Beads Neatly in a Box

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers13

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players