13
\$\begingroup\$

At the end-of-day on Sunday, May 31st, the most-voted post will become the next .

It is June 1, and the top-voted answer is: Decrypt a monoalphabetic substitution cipher

April's Calculator submissions submissions are still rolling in, and May Battleship submissions are starting to arrive, but I felt it'd be prudent that we get a month's challenge decided early so that a challenge can be agreed upon before the month begins (just before).

What should we do this time? Feel free to resubmit non-winning ideas from previous rounds, although new ideas are usually more successful.

  • Post an answer to this question with your challenge
  • Vote for those answers which interest you
  • At the end-of-day on Sunday, May 31st, the most-voted post will become the next .

Once the challenge topic is decided, you can post questions on the main-site related to the challenge. The idea is to run the challenge all the way through June... although nothing stops you from posting an "entry" later than that :)

Disclaimer: Most of this text is borrowed from Mat's Mug.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for posting. I was just about to do this today when I spotted this. \$\endgroup\$
    – RubberDuck
    May 13, 2015 at 11:44
  • \$\begingroup\$ May 31st? Surely it should be June? \$\endgroup\$
    – ArtOfCode
    Jun 16, 2015 at 13:09

6 Answers 6

8
\$\begingroup\$

Decrypt a monoalphabetic substitution cipher

A monoalphabetic substitution cipher applies a substitution table to the letters in the plaintext (often omitting all non-letters to disguise the word boundaries). For example, if the table is:

plaintext   ABCDEFGHIJKLMNOPQRSTUVWXYZ
ciphertext  RDYBXZWFCTIELAMJPGQVNSOHUK

Then the plaintext HELLO WORLD would be encrypted as FXEEMOMGEB.

Your program should take as input a ciphertext, for example:

UXLIRNXSOPQAKJBJTXSVTJKRHXKKJKLIQQOEBLXRSNJKWQKQKYSAQKLRVQNLJKQD 
QRPLJRSEWIRSWQWJHQKTRKKQRWIXSODXNXJSNJTLIQBRNLLIXNXNUIRLXYSAQKLR
VQLJAJTJKEJYKQRAQK

(together with advice from the cryptanalyst, if you wish) and output the plaintext.

Some more examples to test your code on (each is encrypted with a different cipher):

EVSXTTIWGVRMWIXWDXEMHWXDVCWGVSIKXWIRIQIVQFIVUUFIKGXEMLFVVMRVCFMW
XTGIWFBZITGIWITGXEBEXEDVTGIWYVCETWDLIBTIZIWKVLIXCTBUCFTGIWIBKEVQ
FXYIFBOIGVSI

UZIRUKEJJXVMDKADJZXRYHSNOZENDNDKZXJDUIDJHJUAOAYIDUZIEUZNUKKXVOUA
OXZKUSSTSDUKYJUGSDUZIHDZOUSEUIDMOKCUVDAMDXGBDVAOGDKASOLDIAXKDD

EPOMQDHHXOHXKMOPKTQPNXTPEUCHKSDTUXDQDMDSDHNDQDOKMDQDMKXKQEADWYPK
TPGNKAPRQXNXOTLWKQOCPEDKOTGXVVXTHPOHSPWHXXTLWXGPOHSXNXKQQXWAGXHN
DOGXHEDHHKRQXH

CYNCWRBNQNGNYPQANYPJQRCRBNCRBNSFYLQCCWRBNQNIBPXBPQRBNYFRJSFKGFYF
YLIBPXBRBNQHPSPRIBCLNXPHBNSQRBNG

Challenge entries

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Originally proposed here. \$\endgroup\$ May 11, 2015 at 11:29
  • 17
    \$\begingroup\$ Encrypted? Those are just village names in Wales :) \$\endgroup\$
    – Flambino
    May 20, 2015 at 20:15
8
\$\begingroup\$

Resubmit May's runner-up

StackSTV

Stack Exchange uses an STV-based system for holding elections. They use the software OpenSTV to host it.

That software is no longer being maintained, and the system is being rebranded as OpaVote, and will no longer be free.

This month's challenge:

Build an implementation of the same STV algorithm used for Stack Exchange moderator elections, that consumes data in the same format that Stack Exchange provides, and produces the same results.

Algorithm

The actual algorithm use is linked in this Meta.StackExchange question/answer: How are moderator election votes counted, in plain English?

Specifically, using the "Meek STV" algirithm here - in Wikipedia.

Inputs

For examples of input data, see: Stack Overflow Elections

Typical data looks something like:

10 3
1 1 2 3 0
1 4 5 6 0
1 6 7 2 0
1 3 6 1 0
1 6 8 4 0
1 6 3 2 0
1 4 1 9 0
1 8 9 3 0
1 8 7 3 0
....
1 8 2 1 0
1 9 4 6 0
1 4 8 3 0
1 3 4 8 0
1 4 5 10 0
0
"meagar"
"Raghav Sood"
"Bohemian"
"0x7fffffff"
"Undo"
"bluefeet"
"Matt"
"Jon Clements"
"Siddharth Rout"
"Doorknob"

The format is essentially:

  • The number of candidates, and seats on the first line - 10, and 3 represent there are 10 candidates, and 3 positions.
  • a list of any candidates that have withdrawn preceded with a negative number - one per line (Stack Exchange won't have these, likely).
  • a count of people with a specific combination of votes For example, in the first line: 1 1 2 3 0 that means that one person voted with the combination first-choice candidate 1, second choice candidate 2, third choice candidate 3. The 0 represents the end of that line. Note that combinations can be duplicated, potentially.
  • a zero on a line by itself represents the end of the vote section.
  • following that, is the names of the candidates, in the order of the choices.

Feel free to implement it in the language of your choice, and to embellish it with GUI, graphs, charts, etc.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Two months runner-up... how about making this a community project instead? \$\endgroup\$ Jun 2, 2015 at 1:23
8
\$\begingroup\$

Chat extension

The goal here is to write a program that Oneboxes GitHub links and allows markdown formatting on multi-line comments.

Markdown code:

*Text* and _Text_ = Italic
**Text** and __Text__ = Bold
***Text*** ___Text___ = Bold & Italic
[Text](http://something.com) = Linked "Text"

Examples:

Italic text and Italic text
Bold text and Bold text
Bold italic text and Bold italic text
Link to CR

Onebox example:

Onebox

\$\endgroup\$
3
  • 1
    \$\begingroup\$ If this challenge ever airs, please link it here! It will greatly help future users. \$\endgroup\$
    – Unihedron
    May 25, 2015 at 15:54
  • \$\begingroup\$ @Unihedron Sure, just help spread the word! \$\endgroup\$
    – user34073
    May 25, 2015 at 16:01
  • 1
    \$\begingroup\$ An interesting addition would be to be able to do [badge:badge-name], like how we can do [tag:tag-name]. \$\endgroup\$
    – user34073
    May 25, 2015 at 18:56
7
\$\begingroup\$

How about retro-programming (or vintage-programming)?

The idea is to create a simple piece of software for an ancient system, like a DOS program or a tiny NES game. Choose your favorite nostalgic platform and code something for it. If you lack the hardware, use an emulator or virtual-machine to test your program.

\$\endgroup\$
4
\$\begingroup\$

(Note: Resubmit)

Blackjack

Yes, the card game. No, hear me out!

As with many classic programming challenges, there's a deck of cards (usually several!) and shuffling and perhaps sorting involved. That's always fun. And there's all the cardshark jargon :)

At its most basic, there's the trickery of an Ace being worth either 1 or 11, so you sometimes need to track two possible scores for a hand.

Then there's the asymmetry in that there are two "players", but one is the dealer who must draw cards until a score of 17 or higher is reached. Perfectly simple rules for a computer to follow.

Now, while Blackjack is basically about getting closest to 21 without going over, there are many other rules that can be respected or ignored as one sees fit (the title above links to Wikipedia's article on Blackjack, where you'll find lots of stuff).

For the more adventurous there's "splitting": A hand of two cards of equal value may be split into two separate hands. And, depending on the hands and the rules you use, you might then split those two hands again. And while face cards are all worth 10, some rulesets do treat them differently when splitting.

Also, the original "blackjack" meant specifically Ace of Spades + a Jack, but nowadays it usually just means Ace + 10. And by the way, a blackjack is worth 21, but still beats non-blackjack hands worth 21, so straight-up numerical comparison isn't quite enough.

And then there's doubling down: Doubling your bet and receiving exactly 1 more card, but no more.

There's also "insurance" which is a side-bet on the dealer having a blackjack. This makes more sense in a real-life game where the dealer draws a hole card, and the player can attempt to "read" the dealer like in poker. Here, the dealer will probably be your inscrutable computer (since it's no fun to play as the dealer), so insurance probably isn't that interesting. Unless your program is counting cards, perhaps?

In terms of overall scope, there are many options:

  • A full game with a dealer and 1 or more positions for the player to play and configurable rules.

  • A game that plays itself, learning the best actions to take for a given hand over time, maybe? Tables for the best strategies for given hands already exist, so you can check your results.

  • A card counting program that plays the game like Rain Man. It can just track the most likely card to come up next, or think several moves ahead, including splits and doubling down, or tricking the dealer into busting. Just don't bring it near a casino if you value your health.

  • A simple game of blackjack against the computer (just hit/stand; no splitting/doubling down etc.).

  • A simple scoring function for two or more cards.

And anything in between.

In all, there's should be meat here for any skill level. The house wins.

\$\endgroup\$
1
1
\$\begingroup\$

This month's challenge was for creating "Battleship" implementations. Why don't we roll an extension of this into next month. Let's write Battleship AI and let's improve May's Battleship implementations to take AI plugins.

\$\endgroup\$
1
  • 6
    \$\begingroup\$ I'm not sure why you are assuming that there won't already be AI's in this month's challenge? \$\endgroup\$
    – rolfl
    May 11, 2015 at 0:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .