September 2016 Community Challenge

Question

We've just gotten the August 2016 Community Challenge going, so it's time to pick one for September.

---

It's time to choose a community-challenge for September 2016.

• Post your challenge as an answer to this question. Feel free to resubmit non-winning ideas from previous months.
• Vote for those answers which interest you.
• At the end-of-day on Wednesday, August 31st, the top-voted post will become the next challenge.

Once the challenge topic is decided, post your solution as a question on the main site and tag it with community-challenge. The challenge runs throughout September (but nothing stops you from posting an entry later on).

Answer 1

I resubmit Legato's submission for August 2016:

CRitter Collaboration

Choose a previous community challenge and work with someone(s) to complete it.

Though interest in challenges may be high time can be scarce so this is a way to get more participation! It doesn't even have to be a community challenge as long is it's something you and others agree to work towards for the challenge period.

Definite Benefits:

1. Exercise in effective communication.
2. Getting to know fellow CRitters!
3. Experience in organization / group tasks.
4. Less time-consuming.

Possible Benefits:

1. Practice in another language.
2. Exercise in language agnostic design.
3. Using a VCS such as Git.

Room to find people to work with / discuss implementation, and plan.

Answer 2

Chain (or belt) drive system

I propose a variation on this challenge by Ell over on PCG - minus the golfing requirement, of course. (Disclosure: I've already done this challenge in JavaScript)

To quote the original:

Your program will be given a list of sprockets, specified as (x, y, radius) triplets. The resulting chain drive system is comprised of these sprockets, connected together by a closed taut chain passing over each of them, in order. [...]

For example, given the input

(0, 0, 16),  (100, 0, 16),  (100, 100, 12),  (50, 50, 24),  (0, 100, 12)

the output should look something like

The original challenge is to generate a fully animated chain drive system, but that's quite a mouthful, so I propose that it can be solved to different degrees:

• Analysis without visual output (e.g. calculating the total chain length, whether the chain crosses itself, the rotational offset from one sprocket to the next that's necessary for the chain to mesh, time taken for a link in the chain to make one full circuit, etc.)

• Simplified, static visualization showing the spatial layout and chain path

• Full-on animation, as per the original challenge

• Interactive visualization (animated or not), e.g. with customizable settings or even click and drag sprockets

And the chain doesn't need to be a chain nor do the sprockets need to be sprockets; it could just be a belt drive system, i.e. plain circles and lines. This would add a lot of flexibility as things won't need to mesh (and radii and placements won't be constrained), but you'd still be calculating tangent points etc.. Animation wouldn't be as fun, but one could add indicators to the wheels and belt to show the movement.

Or one could go the other way, and have the chain be properly segmented into links like a bike chain, instead of drawing a smooth arc around the sprockets.

I admit that the challenge appears a little daunting, but it's actually not that bad. If the goal is simply to do that analysis part (i.e. no animation or graphical output), it can be done in pretty much any language. All that's needed is a bit of vector math (to work out tangent points), and basic geometry (to work out arc lengths).

Still, the task does look daunting, which presents a bit of a barrier to entry so I don't know if it's the best fit for a community challenge. But personally I found it to be an interesting (and fun!) task, with plenty of "meat" on its bones.

Answer 3

I re-submit Heslacher's proposal from August 2015:

---

In image processing, a contour is a closed curve forming the boundary of a region of the image (or a union of closed curves, if the region has holes). For example, given this image:

The contour of the black region is the pair of orange curves shown here:

Implement an algorithm that finds the contour of a region in an image.

You may assume, if you wish, that the image is represented as a two-dimensional array of Booleans (indexed by \$x\$ and \$y\$, say), with array entries containing true for the region of interest.

Possible choices of algorithm include:

• Theo Pavlidis
• Moore-Neighbor
• Marching squares

Answer 4

Combinations Calculator

What is a combination?

A combination is a selection of all or part of a set of objects, without regard to the order in which objects are selected.

For example, suppose we have a set of three letters: A, B, and C. We might ask how many ways we can select 2 letters from that set. Each possible selection would be an example of a combination. The complete list of possible selections would be: AB, AC, and BC.

source

The challenge

You are to take input of

• n non-numeric elements in whatever format you'd like
• r size of combination groups

And output how many distinct combinations of r elements are possible from the total n population, without regard for the order of the elements. So as to say that both AB and BA cannot both be counted because they are the same combination with different permutations.

Sample data points

As an example of input to output, you can use these data points

(n,r) = c

7   1    7 
7   2    21 
7   3    35 
7   4    35 
7   5    21 
7   6    7 
7   7    1 
15  1    15 
15  2    105 
15  3    455 
15  4    1,365 
15  5    3,003 
15  6    5,005 
15  7    6,435 
15  8    6,435 
15  9    5,005 
15  10   3,003 
15  11   1,365 
15  12   455 
15  13   105 
15  14   15 
15  15   1 

Bonus round

If you feel like it, instead of output of the number of combinations, output the actual combinations in a legible form e.g.

Note: (n=34, r=17) > 2³¹

Answer 5

This question is about entering in the colors of a Rubik's cube with four squares (2x2) per side. It uses a text interface.

I was thinking that we could have a challenge to create a graphical interface for a 3x3 Rubik's cube.

There are six sides, each with a 3x3 grid. Parts of the cube can be rotated, mixing up the colors. The center of each grid always stays the same color. The corners are shared between three sides. For example, one corner is red, white, and blue. Some pairings for colors are impossible because the colors are on opposite sides.

Opposite color pairs when solved: green/blue; red/orange; yellow/white.

As I said, the base problem could be a graphical interface to choose the colors for each square. A simple interface might just show each of the six sides. A more advanced program could show them as a cube and allow the user to rotate the cube to choose the colors on a different side. Bonus points if the program could check that the chosen colors are actually possible in a solvable cube. A really advanced program could solve the cube.

Advantages of this challenge:

• Choice of language is open.
• It has a variety of levels. Someone could implement a simple color chooser or a more complex one. With or without solver.
• Users often prefer graphical interfaces and this is a chance for those of us who are more comfortable with code or text interfaces to work with a basic one. And think about how to make it more advanced.
• The highest level problem is complex enough to be interesting.
• If someone solves every suggestion here -- do the 4x4 cube (or more). Or one of the alternative shapes.