April 2015

[science_man_88]

26 immediate neighbors puzzles me a bit because that could differ from the 2-d faces of the cube or the cube structure. one forces two to be in a 3 by three by 3 cube the other a 5 by 5 plane.

[LaurV]

Actually, on a plane there are only 24 neighbors in a 5x5 box.
They are talking about 9 directions if on a side, 6 directions if close to an edge, down to 4, 3, 2, and 1 direction if on the corner.
It doesn't matter for the problem. You just have a cube made of 7x7x7=343 smaller cubes. From the smaller cubes, at least 161 are transparent (peters) and at most 182 are opaque (wendies). You have to arrange all together in the 7x7x7 transparent box, in such a way that doesn't matter how you look through it**, you should see no light.

All "planar" solutions with 15 wendies are mirrors, flips, and rotations of the 4 images below, and there are no other solutions. Totally 112, because 4 of them are fixed to rotation, so there are 3*4*8+1*4*4=112. The blue/green is the 15-th wendy, the green representing the symmetrical position.



Now the trick is that you need to pick 5 of the 112 solutions, stack them in a 7x7x5, and repeat 3 times on each axis of the cube. This way you are "guarded" against any orthogonal lose of the light, and ortho-diagonal lose of light (i.e. diagonal in each orthogonal plan) and you still don't use all the wendies, because they overlap a lot. The remaining wendies you can use to guard against the leaks of light that goes from one plan to the other (pure diagonal).

Disclaimer: I don't consider that I give an important hint, therefore I post it here. One still has to do a hell of a work to solve the problem. And yes, the black spoilers annoy me as much as they annoy axn, and more (I already said that repeatedly). If the opinion in different, some mod can hide this post, no harm will be done.

----------
** Of course, assuming you only look orthogonal, and at 45 deg angles, you are not allowed to look at strange angles like 17.5 (when you will always see some light close to a corner... hehe).

Edit: now putting them together I realize that there are not 112 solutions, few of them overlap, and few of them have more axes of symmetry. For example, the first diagram on the upper left generates only 4 positions with the wendy on green, and another 8 with the wendy on blue-not-on-a-side. Total 12. The other are symmetrical. The lower-left diagram generates only 4 (green) plus 2*8=16 on blue-not-side, because blue-side is already covered by the upper-left diagram. So, left side is only 32 positions, totally. Same reasoning for the right side if you rotate it once. So the complexity of the problem is lower, only 64^5+change, instead of 112^5+change. Also, heuristically, the diagrams with 15th wendy on the side should be picked more than the others, because they will overlap more when dispatches on the three axes of the cube (as the most of the wendies are on the outside layer). But this may be false, or tricky.

[Ken_g6]

Like the problem says, there are 26 projections of the cube you have to look at. Even if you use those 2D solutions in 7 layers, OR-ing them on 3 axes, that's only 8+6+4=18 projections. You still have to consider the 8 other axes that are diagonal to all the planes.

(Actually, half the projections are looking through the cube opposite to the other half, so 13 projections.)

Come to think of it, all corners and all edges must be wendies. They can all be exposed in one projection or another as a single layer. So that's a minimum of (7*2+5*2)*2+(5*4) = 68 wendies just there.

[Ken_g6]

Edit: I guess two points on a diagonal don't block the other diagonal. Never mind.

[LaurV]

That is what I said in my posts too.

[LaurV]

I have a solution where I place more peters in the cube than required (i.e. less wendies). I am going to send it tonight.

Two interesting observations: one is that the problem has two interpretations (I read it well when I reached the stage of submitting a solution, to avoid confusion) and my solution can still be improved (i.e. some wendies still can be removed) depending on the interpretation, but the solution I have uses the minimum number of wendies that covers both interpretations.

The second interesting observation is that the solution is completely done by hand, using AutoCAD. I placed wendies (small cubes 1x1x1) in a bigger cube (21x21x21, you need to have spaces too, otherwise the small cubes are obstructing the holes) based on the planar solutions above, and then I turned it all around to see where the holes are. If I could push my finger through the monitor, I placed a new wendy on that line. That's it. It took me few hours during the weekend. I don't think that many people here play with acad, but I can print a 3D-pdf so anybody can play with it later, of course, that will be after the submission period.

So, remark that the 161 peters required is not maximal. You can place more. But I don't think they offer any bonus for it

[LaurV]

Yarrr!
(however, a new bonus is offered for "more peters than wendies", but I have no time to "rethink", tomorrow early morning we start to put as much as distance as possible between us and the city, during Songkran craziness, we won't be back too soon).

[Batalov]

You can update your solution. They accept this.

[Xyzzy]

http://domino.research.ibm.com/Comm/...April2015.html

The April Ponder This solution will be posted on May 4th.

[R. Gerbicz]

Deleted. I will post my solution after May 4th.

[R. Gerbicz]

I was a little confused what was the deadline of the problem after they delayed to post the solution, note that for example for the October 2014 challenge there are some solutions submitted in November.
(probably the best to post solution after they publish)

My submitted solutions (you can easily check that these are good strings (inserted some line breaks):

For the easier part:
One solution:
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWPPPPPWWPPPPPPPPPPPPWPWPPPPPWPPPPPWWPWPWPWWWWWWWWWPPPPPWWPPPPPW
WPPPPPPPPPPPPWWWPPPPWWPPWPPWWWWWWWWWPPPPPPWPPPPPWWPPPPPWWPPPPPPWPWP
PPWWPPPWPWWWWWWWWWPPPPPWWPPPPPWWPPPPPWWPPPPPWWPPPPPWWPWPWPWWWWWW
WWWPPPPPPWPPPPPPPPPPWPPWPPWPPPWPPPPPWWWWWWWWWWWWWWWWPPWPWWWWPPPW
WWWWPPWWWWPWPWWWPPPPWWWWWWWWW

I've written an integer program for the problem and solved it in roughly 15 seconds with the free Glpk program. See the attachments for the code (and comments) and the screen output.

For the star:
To get a star, a solution for more Peter Pans than Wendies (172 Peters, 171 Wendies):
WWWWWWWWPPPWWWWPWPWWWWPPPWWWWPWPWWWWPPPWWWWWWWWWWWWWWWWWW
PPPPPPWPPWPPPWPPPPPPWPPWPPPWPPPPPPWWWWWWWWWPWWWWWPPPPPPWPPPPPPWPPPP
PPPPPPPPWWPPPPPPWWWWPWWWWWPWWWWPPWPPWWPPPPPWWPPPPPWWPPPPPWWPPPPPW
WWWPWWWWWPWWWWPPPPPPWWPPPPPPPPPPPPWPPPPPPWPPPPPPWWWWWPWWWWWWWWW
PPPPPPWPPPPPPWPPPPPPWPPPPPPWPPPPPPWWWWWWWWWWWWWWWWWWPPPWWWWPWPWW
WWWPPWWWWPWPWWWWWPPWWWWWWWW

This is a vertex cover problem in a hypergraph. To see this: the vertices of the graph are the center's of the cells, on one hyperdge there are centers that are on a line. If there is at least one Wendy on each line that crosses the 7x7x7 cube, then the Wendies form a so called hitting set, so on each hyperedge there is at least one point (Wendies) from the set. To find a minimum hitting set is a NP hard problem.

The first idea was to use only the cells in the hitting set that are in the (big) cube's face cells (there are 343-125=218 such cells), since in this case each line crosses the big cube's face cell centers on at most two different places, and in this case our hypergraph will be only a graph, the covering problem is easier (still NP complete). Obviously in all minimal hitting set we should use all cell centers that are in the big cube's edge cells (because there is a line that crosses only these cell centers), there are 68 such cells, so the graph has 218-68=150 points.

Unfortunately the best covering uses 173 Wendies (170 Peters), so suboptimal. We have to use some inner cell centers in the hitting set, if we fix some inner centers then we can consider only such lines that are avoiding these centers and in this case our hypergraph will be again only a graph. It turned out that there are 3 different centers (and their symmetric ones) that improve our solution to 171 Peters, if we use exactly one cell center from: (1,2,3), (1,3,3) or (2,3,3) (if the cell centers are from [0,6]X[0,6]X[0,6]).

Using two inner cell centers is still few (giving only 171 Peters), but with three inner cell centers we can reach 172 Peters (and 171 Wendies), these 3 centers are: (1,2,3),(1,4,3),(3,1,3). (To reach this tried some other triplets.)

If we fix these 3 inner cell centers, then my solution gives the Wendies rather quickly, using a tree search algorithm. Searching for maximum independent set, as the complement of this is a minimum vertex cover. Let alpha(G) be the size of max. inependent set in G, then it is known that alpha(G)=max{alpha(G-v),1+alpha(G-v-N(v))} if v is a vertex of G and N(v) are the neighbors of v. We choose v that has the maximum degree in G, and in each step to get an upper bound for alpha() we search for paths and cycles in the graph. Obviously if the maximal degree is 2 then we can get alpha() in polynomial time (as in the graph there are only paths/cycles and isolated points).
This is implemented in alpha.c code, and finds a solution (with 172 Peters) in 18 seconds. (the solution will appear under the line of alpha(G)>=50, the search will continue a little more, and proves that in fact alpha(G)=50).

ps. Here I won't post alpha.c code. With easy modification of ibm.txt you can find a solution for the hard part, but that could take very long time.

ps2. Tried the free igraph program to get alpha of a graph, it was pretty slow, so not used.