# June 2016 Community Challenge

I don't see one of these yet, so here's the question for the proposals for the June 2016 Community Challenge! (I skipped May, as there wasn't enough time to get a good pool of suggestions.)

It's time to choose a for June 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 Tuesday, May 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 . The challenge runs throughout June (but nothing stops you from posting an entry later on).

When I was a child, the board-game "Chutes & Ladders" really grew my hatred for anything random.

The board is 10 x 10. The object of the game is to get your piece from the bottom left corner (1) to the top left corner (100). This means the numbers "snake" as they increase e.g.

square 10 steps "up" a row to square 11 and
square 11 steps "left" a column to square 12.


Basically the bottom two rows are:

20 19 18 17 16 15 14 13 12 11
1  2  3  4  5  6  7  8  9  10


Which the player would traverse in a counter-clockwise motion. My game used a spinner with 6 equal portions of a circle each representing a number 1 to 6. The same could be said for a die. A player gets to spin/roll once per turn and try to be the first player to reach 100.

Pretty simple idea, but there are pitfalls (chutes/snakes) and shortcuts (ladders) to, I don't know, make the game fun? My version had

• 9 chutes with a total change of -221
• 9 ladders with a total change of 171

Located at:

| If you land on | Go To | delta |
|----------------|-------|-------|
| 5              | 14    | 9     |
| 9              | 31    | 22    |
| 20             | 38    | 18    |
| 16             | 6     | -10   |
| 28             | 84    | 56    |
| 36             | 44    | 8     |
| 40             | 42    | 2     |
| 49             | 11    | -38   |
| 51             | 67    | 16    |
| 56             | 53    | -3    |
| 62             | 19    | -43   |
| 64             | 60    | -4    |
| 71             | 91    | 20    |
| 80             | 100   | 20    |
| 87             | 24    | -63   |
| 93             | 73    | -20   |
| 95             | 75    | -20   |
| 98             | 78    | -20   |


# The Challenge

Write a program that

1. Will generate a game-board with the same total change (Delta = -50)
2. Has an arbitrary (>1) number of chutes and ladders
3. Ensure NO square contains the beginning of both a chute and a ladder
4. Ensure NO square contains the end of a chute and the beginning of a ladder
5. Ensure NO square contains the end of a ladder and the beginning of a chute
6. No chute has a positive change and no ladder a negative change
7. No chute ends below 1 and no ladder ends above 100
8. No ladder begins on Square 1 and no chute begins on Square 100

If you want to string chutes together or string ladders together, go for it. Beware though, children will cry. If you want 1 ladder and 17 chutes, go for that as well.

Note: the intent being that what you write can create many different boards, not just one static board.

But, you can put any restrictions on the possible scenario game-boards as you’d like.

Bonus – allow n players to play the game on the board

I tried & did not succeed with this challenge in VBA. If you are curious what a dozen hours in VBA produces without result, proceed with caution

• I am so going to over-engineer and go an extra mile on this! – Simon Forsberg Apr 27 '16 at 18:50
• It seems like you don't need to, so I'll ask, do you need to display the board? (Yes I'm that sad to not display a board!) – Peilonrayz Apr 28 '16 at 15:56
• @JoeWallis Doesn't seem to be a requirement, but if you want to, you can. – Simon Forsberg Apr 30 '16 at 9:06
• @simon is correct - you don't have to display it as long as you know it's legal. But, I mean, it is a board game :) – Raystafarian May 2 '16 at 11:16
• I feel like I'd do this if I ever played the real thing even once... – Legato Jun 11 '16 at 19:43
• That project where you tried so hard, its epic. Code quality is guaranteed that way! – Randy Jun 14 '16 at 6:21

## Simplify a DFA

Understanding and simplifying a formal language can be difficult. Doing it for a visual representation of that language is a well-understood phenomenon for "regular languages" (RegEx anyone?).

Your task is: Given a Deterministic Finite State Automaton, find the simplest representation of that automaton.

An automaton is formally defined as a 5-Tuple $M = (S, \Sigma, \delta, s_0, F)$
$S$ contains a Set of all possible States the automaton has.
$\Sigma$ defines the alphabet that the Automaton works on. For all intents and purposes here this is the standard ASCII alphabet.
$\delta$ is the "transition function" more on that later.
$s_0$ is the starting state for the automaton.
$F$ is a subset of $S$ and describes all states that are valid terminations for the Automaton.

### How it works

$\delta$ defines the transitions between the states. Say our word begins with an a. The automaton inputs it's current state ($s_0$) and the read character (a) as arguments to $\delta$ and the result of this function "call" is the state that the automaton has next.
If there is no such state, the automaton terminates with the result that the input is not contained in the language.

Otherwise the automaton reads the next character in the input and checks again. If (and only if) the automaton reaches a "terminating state" when the last character from the input is read, the input is in the language described by the automaton.

It kinda looks like this in java-ish pseudocode:

currentState = start;
for each (character in input)
currentState = delta(currentState, character);
if currentState is empty: return false;
end for
return currentState is in terminatingStates;


## The goal

The goal of simplifying a DFA is to reduce the number of States it has to a minimum.

### How to minimize the number of states

The standard algorithm taught in CS-Theory classes works as follows:

1. Create a list of all pairs of states. The order of states in a pair does not matter. (Iow. $(s_0, s_1) = (s_1, s_0)$
2. Mark all pairs where at least one component is a terminating state.
3. While you mark new pairs do:

• Check all non-marked pairs for each symbol in your alphabet for the following condition:

if the pair delta(currentPair[0], symbol) and delta(currentPair[1], symbol) is marked:
mark currentPair
break for

4. After you stopped marking pairs, you can merge all non-marked pairs, where each pair of states gets a new state.

As you can see, this algorithm is basically $O(2^nm)$ where $n$ is the number of states and $m$ the number of different symbols in your alphabet.

• This brings back memories of CS Theory class... shudders – syb0rg Jun 2 '16 at 12:46
• – Dan Pantry Jun 6 '16 at 11:43
• ^.^ - the reason i hated studying computer science . They never stop with this Theories. – Siobhan Jun 28 '16 at 16:56

A Tennis match simulater.

Pretty much as it says on the tin- some code which gives a final match result for two virtual players. You can choose how complex you wish to make it: for example you could just take the stats of your virtual players, throw in a random modifier and then builds a final score, or choose to run the match point-by-point, making use of shifting tactics, mental strength, tiredness (how much the player's had to run around the court) into account. This would allow coders of all skill-levels to take part. Balancing the random factor would be an interesting part of the challange

• I feel that at the moment, this challenge is very broad. It could mean nothing and it could mean everything... – Simon Forsberg Apr 27 '16 at 18:36
• I agree, if it were made more specific this could be interesting, maybe make it specific to one sport. Tennis could be a good candidate, since the rules are not overly complicated unlike baseball or football etc. – Phrancis Apr 27 '16 at 20:41
• I take your points, and will edit as suggested. If anyone thinks further changes are needed, feel free to edit my, or post an alternative, version. – Orangesandlemons Apr 27 '16 at 20:57
• I like how this is completely in the spirit of Code Review's community-challenge, being completely language-agnostic and leaving implementation details up to the participant. But I agree, it could be a tiny little bit more specific - for example, put in what the scoring rules are for a Tennis game. – Mathieu Guindon Apr 27 '16 at 21:24
• I like it only because it's the only one I could feasibly do. – Insane Apr 28 '16 at 5:41
• isn't that Pong (Pong Game Website) – Malachi Jun 8 '16 at 14:02
• @Malachi you could do it as pong to generate the score, but you'd need to program the players, and make tennis-like scores – Orangesandlemons Jun 8 '16 at 14:12