April 2017 Community Challenge

Question

It's that time of year again! I want to get a head-start on the 2017 community challenge, we have a lot of new faces over the winter and it would be great to get everyone participating again!

For those who don't know community challenges are a way for the entire community to band together and come up with a challenge for us all to try to implement. You can pick a challenge that has been previously suggested and unselected, or you can pick a brand new challenge!

For any new users, do note that these are not like the Programming Puzzles and Code Golf challenges: no one wins and no one loses, it's an opportunity for everyone to train themselves further and see how the community interacts with different ideas. All questions must continue to be on-topic for the site.

To help start things off, here are all the community challenges from last year:

• September 2016: CRitter Collaboration
• August 2016: Rainfall Challenge
• July 2016: Monopoly
• June 2016: Chutes/Snakes and Ladders

And 2015:

• October 2015: Mandelbrot Set Fractals
• September 2015: Elevator Management
• August 2015: Racetrack
• July 2015: StackSTV
• June 2015: Monoalphabetic Substitution Decryption
• May 2015: BattleShip!
• April 2015: Simple Calculator

Lastly, all the pre-community-challenge challenges:

• Winterbash 2014: Simon Says
• April 2014: 2-player Cardfighting
• January 2014: Ultimate Tic-Tac-Toe
• December 2013: Create a Scheduler
• December 2013: Simple Text Adventure
• December 2013: Read the Pokédex!
• December 2013: Sudoku Solver
• December 2013: Evaluate a poker hand
• November 2013: Rock Paper Scissors Lizard Spock

Feel free to select any ideas that are not listed directly above, you can view those questions and select other ideas in them, just not the ones that won.

Usually I post these on the first day of the month before, but I want to give enough time for everyone to have an opportunity to get involved, the early parts of the year can be busy for a lot of us, so I want us all to have plenty of time!

---

It's time to choose a community-challenge for April 2017.

• 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 Friday, March 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 April (but nothing stops you from posting an entry later on).

Answer 1

Simulate a Multi-Way Intersection

This was actually a project I had to do in college with PLC's. The idea is to simulate a four-way (or other intersection) stop-light, each light should be green for a duration, then yellow for a duration, then red for a duration.

You may implement this with whichever country's traffic light system / regulations you prefer, or make your own up! You may also choose any intersection: three, four, five, etc. I'm going to demonstrate the example with the United States general simple traffic light timing structure and a four-way intersection.

United States Four-Way Example

The total duration of the red signal should be no less than green + yellow. Each direction of traffic should never be green or yellow at the same time. If we define a basic timing of 4s green, 1s yellow then given a EastWest light and a NorthSouth light the states should be:

Time | EastWest | NorthSouth
-----+----------+-------------
0s   | Red      | Green
1s   | Red      | Green
2s   | Red      | Green
3s   | Red      | Green
4s   | Red      | Yellow
5s   | Green    | Red
6s   | Green    | Red
7s   | Green    | Red
8s   | Green    | Red
9s   | Yellow   | Red

You may optionally support overlap of the red signal, since not all vehicles will stop for yellow. Thus a timing of green 4s and yellow 1s would have red 6s or so.

Input

There's no specified input, but you may accept input of the signal timings to meet that requirement. You may also use artificial 'sensors' and 'buttons' as input to your algorithm.

Output

I leave the method of output to you, but at a minimum it should support a 1s tick and output each light's state at that point. (The table above would be a great format.)

You should also indicate the basic rules of the lights you've selected, if you don't use this basic version.

You may optionally support a graphical simulation of the intersection and draw vehicles on screen that follow the rules of your lights. (In this example: stop at yellow if possible, stop at red always, stop at green never.)

Bonus Points

• Demonstrate vehicle collisions at improper timings;
• Allow alteration of timings and speeds of vehicles;
• Turn-lanes (left and right) and timing;
• Sidewalk/pedestrian/biking lanes and timing;
• Demonstrate vehicle acceleration/deceleration;

Answer 2

(re-submit of an idea from the last round)

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

(Please do check out the original challenge in its entirety, as it includes plentiful examples of input and output, and goes into a lot more detail, all of which Ell explains better than I can hope to do here.)

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 (for example some or all of: 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 rigid 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 math; trigonometry and basic geometry (to work out tangent points and 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

Virtual machine

The task here is to create a simulated computer of some kind.

The virtual machine should have a CPU, an instruction set and anything else needed (e.g. simulated ROM, RAM, registers, ALU, I/O) to execute the instructions on the virtual machine. The machine could be an actual processor such as the 6502 or a well-known specification for a virtual processor for teaching or a completely new processor.

It could even be for one of the esoteric languages, but personally, I think we have enough of those already.

The virtual machine would be able to run a binary program and display the contents of either memory or registers.

Additional possibilities include novel architecture (e.g. one with no registers or one that implements trinary) cycle-counting, pretty display, simple assembler for the machine, or even some higher level language. Simulated DSPs would be welcome, too.

The language of the implementation could, of course, be anything.

Answer 4

Chess!

Last year ended with a board-game spree. Let's continue this year with one.

I think you all know the game of Chess, which is exactly why I just linked to the wikipedia page. Even though everyone knows it, you might not know all the details about it.

What I like about a Chess challenge is that it can be both a small and a large challenge, depending on what you want to do with it. Let's take a look at some possible challenges for Chess: (feel free to pick the ones you want)

• Implement logic to determine where/how pieces can move/attack
• Determine which squares are threatened by what pieces
• Implement support for some Chess notation (there are a bunch to choose from)
• Given a history of chess moves, check if all moves are valid and figure out how the board looks like now.
• Interact with the Lichess API for example use this data and implement the above
• Make a GUI
• Make a Chess computer opponent
• Make a Chess computer opponent that beats Stockfish level 8 (good luck with that)
• Implement some Chess variant such as Atomic Chess
• Probably a bunch of other stuff

Answer 5

PIZZA time !

This challenge is a practice problem for Google Hash Code 2017.

Introduction

Did you know that at any given time, someone is cutting pizza somewhere around the world? The decision about how to cut the pizza sometimes is easy, but sometimes it’s really hard: you want just the right amount of tomatoes and mushrooms on each slice. If only there was a way to solve this problem using technology…

Problem description

Pizza

The pizza is represented as a rectangular, 2-dimensional grid of R rows and C columns. The cells within the grid are referenced using a pair of 0-based coordinates [r, c], denoting respectively the row and the column of the cell.

Each cell of the pizza contains either:

• mushroom, represented in the input file as M; or
• tomato, represented in the input file as T

Slice

A slice of pizza is a rectangular section of the pizza delimited by two rows and two columns, without holes. The slices we want to cut out must contain at least L cells of each ingredient (that is, at least L cells of mushroom and at least L cells of tomato) and at most H cells of any kind in total – surprising as it is, there is such a thing as too much pizza in one slice.

The slices being cut out cannot overlap. The slices being cut do not need to cover the entire pizza.

Goal

The goal is to cut correct slices out of the pizza maximizing the total number of cells in all slices.

Input data set

The input data is provided as a data set file – a plain text file containing exclusively ASCII characters with lines terminated with a single \n character at the end of each line (UNIX- style line endings).

File format

The file consists of:

• one line containing the following natural numbers separated by single spaces:

  • R (1 ≤ R ≤ 1000) is the number of rows,
  • C (1 ≤ C ≤ 1000) is the number of columns,
  • L (1 ≤ L ≤ 1000) is the minimum number of each ingredient cells in a slice,
  • H (1 ≤ H ≤ 1000) is the maximum total number of cells of a slice
  • R lines describing the rows of the pizza (one after another). Each of these lines contains C characters describing the ingredients in the cells of the row (one cell after another). Each character is either M (for mushroom) or T (for tomato).

Example Input File

3 5 1 6
TTTTT
TMMMT
TTTTT

3 rows, 5 columns, min 1 ingredient per slice, max 6 cells per slice

File format

The file must consist of:

• one line containing a single natural number S (0 ≤ S ≤ R × C) , representing the total number of slices to be cut,
• U lines describing the slices. Each of these lines must contain the following natural numbers separated by single spaces:
  • r1, c1, r2, c2 (0 ≤ r1, r2 < R, 0 ≤ c1, c2 < C) describe a slice of pizza delimited by the rows r1 and r2 and the columns c1 and c2 , including the cells of the delimiting rows and columns. The rows ( r1 and r2 ) can be given in any order. The columns ( c1 and c2 ) can be given in any order too.

Example

3
0 0 2 1
0 2 2 2
0 3 2 4

Example description

3 slices.
First slice between rows (0,2) and columns (0,1).
Second slice between rows (0,2) and columns (2,2).
Third slice between rows (0,2) and columns (3,4).

Validation

For the solution to be accepted:

• the format of the file must match the description above,
• each cell of the pizza must be included in at most one slice,
• each slice must contain at least L cells of mushroom,
• each slice must contain at least L cells of tomato,
• total area of each slice must be at most H

Scoring

The submission gets a score equal to the total number of cells in all slices.

Note that there are multiple data sets representing separate instances of the problem. The final score is the sum of your best scores on the individual data sets.

Scoring example

The example submission file given above cuts the slices of 6, 3 and 6 cells, earning 6 + 3 + 6 = 15 points.

Answer 6

Copied over (and lightly adapted from) this question:

The latest hit on TV is a jumping game played on a giant rectangular chessboard. Each participant dresses up in a green frog suit and starts at the top left corner of the board. On every square there is a spring-loaded launcher that can propel the person either to the right or down.

Each launcher has two quantities R and D associated with it. The launcher can propel the person upto R squares to the right and upto D squares down. The participant can set the direction of the launcher to Right or Down and set the number of squares to jump to any number between 1 and R squares when jumping right, or between 1 and D squares when jumping down. The winner is the one who can reach bottom right corner of the chessboard in the smallest number of jumps.

For instance, suppose you have 3 × 4 chessboard as follows. In each square, the pair of numbers indicates the quantities (R,D) for the launcher on that square.

(1,2)   (1,2)   (1,2)   (2,1)
(3,1)   (1,1)   (1,2)   (1,2)
(1,1)   (1,1)   (1,2)   (2,2)

Here, one way to reach the bottom right corner is to first jump 1 square right, then jump 2 squares down to the bottom row, then jump right two times, one square a time, for a total of 4 jumps. Another way is to first jump 1 square down, then jump 3 squares right to the last column and finally jump one square down to the bottom right corner, for a total of 3 jumps. On this board, it is not possible to reach the bottom right corner in fewer than 3 jumps.

Your task is to write a program to calculate the smallest number of jumps needed to go from the top left corner to the bottom right corner, given the layout of the launchers on the board.

Solution hint

Set up a graph in which the (i,j) positions are vertices and use breadth first search.

Input format

The first line of the input contains two positive integers M and N, giving the dimensions of the chessboard. M is the number of rows of the board and N is the number of columns. This is followed by 2M lines of input: M lines describing the R values of the launchers followed by M lines describing the D values of the launchers. Line 1+i, 1 ≤ i ≤ M, has N integers, describing the R values for row i. Line M+1+i, 1 ≤ i ≤ M, has N integers, describing the D values for row i.

Output format

The output should be a single integer, the minimum number of jumps required to reach the bottom right square from the top left square on the given chessboard.

Test data

You may assume that 1 ≤ M ≤ 250 and 1 ≤ N ≤ 250.

Sample input

3 4 
1 1 1 2
3 1 1 1
1 1 1 2
2 2 2 1
1 1 2 2
1 1 2 2

Sample output

3