exercism / problem-specifications

Shared metadata for exercism exercises.
MIT License
327 stars 545 forks source link

Exercise ideas: Game trees, Comma-Separated Trees, Collatz Trees #1388

Open sshine opened 6 years ago

sshine commented 6 years ago

Game trees are trees that describe the possible choices in a turn-based game. The leaves are final states where either player has won, and each step up the tree describe the turn before where the other player (alternating at each level in the tree) has a number of choices corresponding to one sub-tree each.

An exercise would consist of describing a game between two persons (Alice and Bob?) in a story-like fashion, a (possibly illustrated?) description of game trees, and a task to 1) build the game tree between Alice and Bob for the given game, and 2) given a game tree, pick the best move.

The exercise can be unit-tested for small game trees and property-tested for larger game trees.

As for the specific game, popular choices are Nim and Tic-tac-toe. We might also pick something else.

Motivation: In my opinion, the Haskell track lacks tree-based exercises. (Ping @petertseng)

sshine commented 5 years ago

Another tree-based exercise that resembles the already existent "Tree Building" exercise is Comma-Separated Trees.

It has a blend of whitespace-sensitive parsing and constructing a tree from CSV-like values. It isn't too difficult to write a custom parser for it, and it poses some interesting, non-standard challenges for parser combinator libraries.

It could work as either a refactoring or a hard from-scratch exercise.

rpottsoh commented 5 years ago

Should this be closed because #1424?

sshine commented 5 years ago

@rpottsoh: Not at all. :-) I'm still collecting ideas. I'll submit a PR to one of them when I've completed the track implementation of one of them. (It's one of those things that are a little harder to timebox, I think.)

sshine commented 5 years ago

Inspired by XKCD 710, and to supplement the Collatz Conjecture exercise, here are Collatz Trees:

collatz_conjecture

The exercise's goal is to construct a tree like the one in the XKCD drawing. The tree is binary, since you can only ever arrive at a Collatz number from an odd or an even number. And the tree has a fixed structure, so the only variation is how much of the tree to generate. This makes it an excellent candidate for lazy data structures.

An animation of a Collatz Tree can be found here.

coriolinus commented 5 years ago

Oh, that sounds fun!

How's this for test cases: provide a derivation path, expect the item at that position in the tree.

Case: [] -> 1 Case: ["even"] -> 2 Case: ["odd"] -> nil Case: ["even", "even"] -> 4 Case: ["even", "even", "even"] -> 8 Case: ["even", "even", "even", "even"] -> 16 Case: ["even", "even", "even", "even", "odd"] -> 5

On Thu, Jan 17, 2019 at 11:14 AM Simon Shine notifications@github.com wrote:

Inspired by XKCD 710 https://xkcd.com/710/, and to supplement the Collatz Conjecture exercise, here are Collatz Trees:

[image: collatz_conjecture] https://user-images.githubusercontent.com/50879/51311112-79815f80-1a48-11e9-839b-01dfa0396bec.png

The exercise's goal is to construct a tree like the one in the XKCD drawing. The tree is binary, since you can only ever arrive at a Collatz number n from an odd or an even number. And the tree has a fixed structure, so the only variation is how much of the tree to generate. This makes it an excellent candidate for lazy data structures.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/exercism/problem-specifications/issues/1388#issuecomment-455117624, or mute the thread https://github.com/notifications/unsubscribe-auth/AHdeThYXWUET9FoFm8BaINPhIXuIMlJPks5vEE0egaJpZM4YWnF0 .

Smarticles101 commented 5 years ago

An animation of a Collatz Tree can be found here.

Oh my gosh it's beautiful lol.

sshine commented 5 years ago

I'm still hunting for a good first tree-based exercise for the Haskell track.

The following is a bit too mathy, but very simple:

Calkin-Wilf trees (2000) enumerate the positive rationals:

calkin-wilf

iHiD commented 5 years ago

For context, would you mind explaining what language techniques you imagine these sorts of exercises teaching? Maybe with examples from a couple of different types of languages? Thanks :)

sshine commented 5 years ago

TL;DR: I imagine that these exercises will mainly teach tree-based recursion and pattern matching.


In Haskell I'd like to cover the standard Data.Tree and potentially one of the Functor, Foldable or Traversable type classes (generalised recursion schemes), depending on the exercise. That is: You don't need to define your own multi-way tree type, and you don't need to define the recursive function yourself. In OCaml / SML I expect to cover only algebraic types and pattern matching, since their libraries don't have generic tree types or generic recursion schemes on them.

The purpose of this issue has so far been collecting tree-based exercise ideas until one strikes me as an ideal first exercise. So far the ones I've found are too mathy (MinMax trees, Collatz trees, Calkin-Wilf trees) and Comma-Separated trees involve parsing, so for Haskell that'd mean covering both trees and parser combinators in one go, which is not ideal at all.

Our existing tree-building exercise has two drawbacks: It's too difficult, and it's a refactoring exercise. And the existing binary-search-tree exercise has one drawback: It implements a common data structure available in the standard library.

sshine commented 5 years ago

Here's an idea for a good introductory multi-way tree exercise: Family trees. A simple but flexible model of a family tree has n children and 0, 1 or 2 parents (unspecified who's who), where a parent has three fields: name, birth year and death year, all optional.

Step 1: Model a family tree. If your language has a preferred way to express multi-way trees, use this. The exercise's module exports the abstract constructors necessary for the next step.

Step 2: Define certain operations on this family tree. This could be

find :: FamilyTree -> (Person -> Bool) -> [Person]

such that one could write find isAlive or find (diedBefore 1900).

Story: To be written, but there's a theme.


Thoughts prior to this formulation: