June 2016 Community Challenge

Question

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 community-challenge 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 community-challenge. The challenge runs throughout June (but nothing stops you from posting an entry later on).

Answer 1

Chutes (snakes¹) & Ladders

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

• 18 Chutes & Ladders
• 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

¹https://en.wikipedia.org/wiki/Snakes_and_Ladders

---

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

Answer 2

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.

Answer 3

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