Problem 42708. Placing Beads Neatly in a Box

• Created by Ned Gulley
• Appears in Computational Geometry IV

×

Like (7)

Difficulty:

(54)

Rate

• Solve Later   
• Add To GroupÂ

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

65.12% Correct | 34.88% Incorrect

• 43 Solutions
• 13 Solvers

Last Solution submitted on Dec 19, 2024

Last 200 Solutions

Solution Comments

ANNOUNCEMENT ×

Registration Now Open for MathWorks AUTOMOTIVE CONFERENCE 2025

Hello Community, We're excited to announce that registration is now open for the...

Problem Recent Solvers13

Suggested Problems

• Select every other element of a vector

  34027 Solvers

• Removing rows from a matrix is easy - but what about inserting rows?

  231 Solvers

• Check if number exists in vector

  12360 Solvers

• Create a Multiplication table matrix...

  581 Solvers

• Square Digits Number Chain Terminal Value (Inspired by Project Euler Problem 92)

  232 Solvers

More from this Author50

• When Was That Goal Scored?

  109 Solvers

• Encoding Google Maps Polylines

  13 Solvers

• Beads on a Necklace (Convex Hulls)

  53 Solvers

• Give a matrix that matches itself when rotated

  13 Solvers

• Frobenius McNugget Factorization

  38 Solvers