Sandbox for Proposed Challenges

Question

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Comments addressing specific points mentioned in the proposal
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Answer 1

Adding two numbers in Tally marks

Tally marks, also called hash marks, are a form of numeral used for counting. Increment is as simple as adding an extra stroke. Usually each five stroke is combined:

1 一    (1)
2 二    (2)
3 三    (3)
4 亖    (4)
5 圭    (5)
6 圭一  (51)
7 圭二  (52)
8 圭三  (53)
...

12345 would take the place of 一二三亖圭 in this question to simplify IO. Thus, a non-negative integer is represented in form /^5*[1234]?$/, whose value is the sum of digits.

Given two values, output their sum, both I/O in tally marks.

Test cases:

4 + 2 = 51
551 + 552 = 55553

Answer 2

English Golf

Your challenge is to golf some English text by replacing some words with their contractions. Here is a list of the contractions you need to support:

Words	Contraction
are not	aren't
can not	can't
could have	could've
could not	couldn't
dare not	daren't
did not	didn't
does not	doesn't
do not	don't
had not	hadn't
has not	hasn't
have not	haven't
he had	he'd
he is	he's
he will	he'll
I am	I'm
I had	I'd
I have	I've
I will	I'll
is not	isn't
it is	it's
it will	it'll
let us	let's
might have	might've
might not	mightn't
must have	must've
must not	mustn't
need not	needn't
shall not	shan't
she had	she'd
she is	she's
she will	she'll
should have	should've
should not	shouldn't
that is	that's
that will	that'll
there had	there'd
there is	there's
they are	they're
they had	they'd
they have	they've
they will	they'll
was not	wasn't
we are	we're
we had	we'd
we have	we've
we will	we'll
were not	weren't
will not	won't
would have	would've
would not	wouldn't
you are	you're
you had	you'd
you have	you've
you will	you'll

This is just a minimal list but you can support other common (please show your source) English contractions should you so wish. Most of them have one of am/are/is, had, have/has, not or will as the second word, except for "let us".

If there is a choice of contraction you can choose either or go for a double contraction e.g. "couldn't've".

The contraction should keep the case of the words, e.g. "Let us go!" becomes "Let's go!".

This is code-golf, so the shortest program or function that breaks no standard loopholes wins.

Answer 3

Classify a Coxeter group

In this challenge you will take as input a Coxeter matrix representing a Coxeter group. Your program will then classify it as one of the following:

• Spherical
• Euclidean
• Compact
• Paracompact
• Hypercompact

Your program should output one of 5 distinct values depending on which category the input falls into.

This is code-golf. The goal is to minimize the size of your source code as measured in bytes.

Sandbox

I had this idea, but haven't had enough time to write up a specification. I'll explain what each of these are, and give the enumerations of each class.

Answer 4

Count Syllables

The goal of this challenge is to write a program that can count the syllables in a word as accurately as possible.

Input

On STDIN, your program will receive a number X followed by X lines, each containing a single word. Simple enough. (Should there be a limit on the size of X?) The words will come from this list.

4
challenge
to
count
syllables

Output

Your output should be to STDOUT and have X lines. On each line should be the number of syllables counted in that word.

2
1
1
3

Scoring

To score you program, it will receive a long secret list of words to test. All programs will receive the same list of words. For each word, the number of syllables that your program got wrong will be added to the score of the program. If it output a 4 or a 2 when the word had 3 syllables, then one point will be added. If it said a 15 instead of a 3, then 12 points will be added to the score. The lower the score, the better.

For example, if for the above input your program output 3 2 2 2 (which would be produced by a program that counts strings of vowels), then the program would receive a score of 2.

Rules

Your program should not access any external files (such as the word list). Also, your program should be no more than 5,000 bytes long (is this a reasonable limit?).

The winner will be the person whose program has the lowest score, therefor the most accurate syllable counter. The deadline for submissions is [some time at least a month away].

Suggestions

I am open to all constructive criticism. Is 5,000 bytes a reasonable limit for the program size? How long should the official scoring test be? How long should the deadline be?

Answer 5

Play Simple 2-Dimensional Minecraft

Recently I found this video of "HansLemurson" showing a computer that was built in minecraft, which runs minecraft. He is playing minecraft on a computer that was built in minecraft that is running on his computer. To be specific, it is a two dimensional version with an 8x8 grid of cells. There is gravity, block placement, and even jumping. It is worth noting that the computer is single purpose. The same person has built programmable computers, but making them single purpose allows the computer to be much smaller.

Details

The minecraft world is an 8x8 grid (one horizontal and one vertical dimension). The grid is comprised of either Xs (representing blocks) or empty spaces. The player is an X that is blinking on and off about once every second.

There are two modes in the game, controlled by a toggle switch. The first mode is movement. This is controlled by a WASD-like button arrangement. If the player chooses to move left/right/down, the computer checks to see if the space immediately in that direction is empty. If so, then the player moves into that space.

If the player chooses to move up, then the computer checks that the block underneath the player is solid. If so, then the player moves upward two units. Notice that this can propel the player into a solid block. If this happens, the player is obscured by the solid block, but can still move to an empty block next to him. When the player is inside on a solid block, the game continues as if the block isn't there, although the block is still there once the player leaves it.

After each move, the player falls down one unit if there is empty space there. This simulates gravity. This is also why moving up moves up two units, so that the gravity makes a net movement of up one unit. Gravity does not cause the player to fall all of the way to the ground, just one unit.

The second mode is block placement. In this mode, the same exact WASD buttons are used. Instead of moving the player, they toggle the state of the block in that direction. If the player presses "left" and there is a block there, then the block is destroyed. If there is not a block there, then a block is placed. Again after this move, the player is again subject to gravity. The blocks are not subject to falling.

Toggling the toggle switch does not count as a move, and does not invoke gravity.

The game board is a torus, so all actions (movement, block creation) can wrap around the board. The board does not scroll with the player. The player moves, and the blocks stay in the same place.

The challenge

You challenge is to write the shortest program that simulates this game. Your program should display and update the map correctly (with Xs as blocks, and with the blinking player). It should accept input from a button that toggles the state and four buttons for movement and actions. This is code golf.

There are imaginary bonus points for adding more features (block types, game size, etc) to your game.

Suggestions?

Answer 6

Bad Voice Recognition Calculator

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

• Input/output will be using your preferred method (STDIN, ARGV, etc.).
• Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
• Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
  • When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
• Basic calculator functions required:
  • "Add"/"Plus"/"Sum"/"And" (+)
  • "Subtract"/"Minus"/"Remove" (-)
  • "Multiply"/"Times" (*)
  • "Divide"/"Divided"/"Divide by"/"Divided by" (/)
  • "Raise"/"Exponent"/"Power"/"To the power of" (^)
  • "<Base>Root"/"<Base>Radical" (√)
  • "Point"/"Decimal" (.)
  • "Pi" (π)
• All strings in the list above must be accounted for in your code, capitalization does not matter.
• Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
• Negative numbers may be assigned using "Minus" or "Negative".
  • The string "Minus" bust be accounted for as an operator and identifier. (see example)
• "And" is only acceptable as an operator, not as part of a named number.
  • "one hundred and one"
  • "one hundred one"
• "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
  • "a hundred" does not equate to "one hundred" and is not a valid input.
• No more than 2 terms will be used.
  • "one plus one minus one" will not be implemented.
• If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

• "one add one" --> "two"
• "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
  • Alternatively: "five zero three four subtract one zero six zero zero"
• "three root twenty seven" --> "three"
• "ten minus minus ten" --> "twenty"
  • Alternatively: "ten subtract negative ten"

---

Sandbox Questions:

1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
2. Does the title fit?
3. Are there any constraints that should be added/lifted?
4. Are any more examples needed for clarification?

Thanks for your input, guys!

Answer 7

Chess move

The Challenge

Write a program that gets a string containing a chessmove and a chessboard as input, and then outputs the chessboard.

Requirements

The chess move will have this format:

<from square><to square>[<promoted to>]

Examples:

d2d4
f8g7
a7a8R

The chessboard format is not fixed, but there must be a 1 to 1 relation between the board and the string to represent the board. Also the format of the input must bet the same as the format of the output. Two suggestions of what it could look like:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

It is not required to store anything except the location of the pieces, and validity of moves can be assumed.

Scoring

Base score is character count (assuming your program can move pieces for all moves)

Bonus multipliers:

• If the program updates the promoted piece, divide by 2
• If the program also moves the rook when castling, divide by 2
• If the program also removes the pawn when capturing en passent, divide by 2

The moves, and castling & en passent in particular are explaned on Wikipedia.

So basically writing a 100 character solution for the base problem gives the same score as an 800 character solution with all bonus multipliers.

Examples

If you would choose to use one of the board formats above, your input would look like one of these strings:

e2e4 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

e2e4 rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

Your corresponding output string would then be one of these:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  0000P000  00000000 PPPP0PPP RNBQKBNR

Answer 8

code-golf game board-game algorithm

Black Box

Your task is to analyze a given situation for the game Black Box. Given a sequence of guesses and answers, your program is to either print the solution or suggest the next move.

The game

The board consists of 8×8 cells, with edges labeled like this:

I'll probably create nice images here, particularly to make sure that the squares of the board are really square.

 abcdefgh
i        I
j        J
k        K
l        L
m        M
n        N
o        O
p        P
 ABCDEFGH

The player shoots rays into the interior of the box, where they might get deflected, reflected or absorbed. He is told the position where the ray leaves the black box again, and from that has to deduce the positions of 4 atoms inside the black box.

I'll have to include more of the game rules here, but for now see Wikipedia.

Input and output

Input is a sequence of line, each consisting of two characters. The first denotes the point where the ray of light enters the black box, the second the place where it comes out again. In the case of a reflection, both characters will be equal. In the case of a hit, the second character will be -.

If the input is enough to fully determine the locations of the atoms, then output should be four lines giving the coordinates of each atom. The lines should be two lower case characters each, the first giving the row and the second giving the column of the found solution. The atom positions must be printed in lexicographical order.

If the input is consistent with more than one set of atom positions, then the output should consist of a single line containing a single character, which is the location where the next ray should be shot. That location has to be chosen in such a way that it can help find the solution. This is the case unless all of the atom positions consistent with the input so far would produce the same output for this next ray as well.

Your output has to be terminated by a newline character.

Examples

Let's take the atom configuration the Wikipedia article uses as an example as well:

 abcdefgh
i        I
j        J
k O    O K
l        L
m        M
n   O    N
o        O
p      O P
 ABCDEFGH

If the input were

cf
D-
Em
HH
Co

then the output should be

kb
kg
nd
pg

but if the input were only

Em
HH

then the output might be for example

K

Scoring

This is code golf, so shortest answer wins. However, I'll only accept answers which are practical in so far as they compute their result in reasonable time. I'd say no more than five minutes on my system where I'll evaluate the answers, and I'll simply hope that correct solutions will be much faster and incorrect ones much slower, so that the speed of my system doesn't make a difference. A submission which gives a wrong answer for one of my test cases will be disqualified until it gets fixed. I will probably point out the problem in a comment to that post.

Answer 9

Create a program with "exact repetition" in its source code

The task is to create a program, with the following restrictions placed on the printable ASCII characters in the source code: choose some k > 0.

• Every non-alphabetic character has to appear exactly k times.
• Every alphabetic character has to appear at most k times.
  • This rule differs from the former in order to avoid boring dummy identifiers while still making it a challenge to choose good library functions to call.

Character set definitions used:

• Non-alphabetic characters are !"#$%&'()*+,-./0123456789:;<=>?@[\]^_{|}~ and '`' (backtick).
• Alphabetic characters are ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.

Note that no restriction is placed on characters outside of the range of printable ASCII characters (including control codes, tabs, newlines, higher unicode codepoints, etc).

What the program does is up to you; be creative. Some general guidelines:

• Programs that do something interesting might have better chances, although more impressive code structure (i.e. fewer comments) is also beneficial.
• Stuffing excess characters in comments is boring, and should be avoided/is discouraged.
• Dead/no-op code isn't terribly interesting either, but is probably unavoidable and at least has to conform to the language's grammar.

This is popularity-contest: whatever has the most upvotes at Feb 1, 2014 gets accepted as the winner.

---

Example answer (C)

#
#
/*$$@``*/_[]={9.};main() {printf("He%clo \
world!%c\
",2^7&!8.&~1|~-1?4|5?0x6C:48:6<3>2>=3<++_[0],'@'^79-5);}

Prints "Hello world!" (adapted from an answer to another question). Probably wouldn't score a lot (since what it does isn't terribly interesting). Each of the non-alphabetic characters appear exactly twice, and no alphabetic character appears more than twice.

---

For meta: I want to post this, but I'm worrying that "do something interesting" might give too little guidance and the question won't receive many answers.. thoughts? Is it good as-is, or should I come up with some task that one should be required to implement (and possibly change the ruling to code-challenge, with length + 2^(characters-in-comments) as the score)?

Answer 10

This is my first try at writing a challenge. Please let me know how I can improve it.

Roman Calculator

code-golf

Create a basic calculator for Roman numerals.

Requirements

• Supports +,-,*,/
• Input and output should expect only one prefix per symbol (i.e. 3 can't be IIV because there is two I's before V)
• Input and output should be left to right in order of value, starting with the largest (i.e. 19 = XIX not IXX, 10 is larger than 9)
• Left to right, no operator precedence, as if you were using a hand calculator.
• Supports whole positive numbers input/output between 1-4999 (no need for V̅)
• No libraries that do roman numeral conversion for you

For you to decide

• Case sensitivity
• Spaces or no spaces on input
• What happens if you get a decimal output. Truncate, no answer, error, etc..
• What to do for output that you can't handle. Negatives or numbers to large to be printed.

Extra Credit

• -20 - Handle up to 99999 or larger (numbers with a vinculum)

Sample input/output

XIX + LXXX                 (19+80)
XCIX

XCIX + I / L * D + IV      (99+1/50*500+7)
MIV

The shortest code wins.

Answer 11

Create a calendar

popularity-contest calendar

We all know HDD-space is precious and bandwidth is expensive, therefore it is best to reduce the size of your executables. Let's start with your calendar:

Your task is to build a calendar app in at most 512 bytes. The calendar must at least support the following features, but additional features may gain you additional upvotes:

• It must be able to show the current month with the current day highlighted
• The user must be able to find out the week day of each day

Rules:

• Maximum code length is 512 bytes (counted as UTF-8 without BOM)
• You may subtract the bootstrapping code (i.e. int main(int argc, char **argv) in C or <?php in PHP) and imports from the final size to allow for more verbose languages to be in
• You may use standard time / date functions of your programming language, as long as they don't allow you to output a ready to use calendar
• No network access (I said bandwidth is expensive!)
• Voters decide on the amount of features / look and feel / creativity

---

This needs a tag for the size restriction, any suggestions?

Answer 12

Hi, first time golf questioner, hopefully I'm doing it right!

Maths Trade Calculator

A maths trade (or "math" trade if you prefer) is a way of calculating complex trades of arbitrary items in a circle of participants where not all participants want all items.

X participants have an item they would like to trade. Each participant is assigned a unique number, and provides a list of (numbers identifying) the items they would willingly trade their item for. They may provide an empty list (i.e. they would rather not trade).

Input

X lines, one for each participant, comprising a unique number identifying them, followed by a colon, then a comma-separated-list of numbers identifying other items that they would trade for. e.g.:

1:2,3,4
2:
3:1,4
4:2

The numbers identifying the participants will not necessary be in order, nor will they necessarily be 1 to X. You may assume that they will be numeric.

This string can be in STDIN, or an argument to a function, or similar and can be followed by a new-line or not, whatever the coder prefers.

Output

One or more trade loops in which all participants are making trades they're happy with. Each loop should be on a new line and comprise a participant number, followed by "->", followed by the participant they should give their item to, then another "->", and another participant number etc, until the loop is closed and the last participant number matches the first one. Another line is added with the number of completed trades. e.g.:

1->3->1
2

Participants for which no valid trade is possible are omitted.

Output can be via STDOUT, or returned as a string, or something else, with an optional final new-line.

Trade rules

1. A participant may not be involved in more than one trade
2. A participant may not receive an item that they didn't want
3. All loops must be closed
4. Maximum number of possible trades should be completed (i.e. no submitting a zero-trade output and claiming it's valid). If there are multiple permutations, pick whichever you prefer.

This is a code golf challenge, so shortest working code wins.

Some more example inputs and possible outputs

1

1:2,3,4,5
2:3,5,7,9
3:1,2,5,6,10
4:
5:1,2,3,4,10
6:5,7,9
7:3,6,9,10
8:1,2,4,10
9:1
10:9

1->9->10->3->1
7->2->5->6->7
8

For instance, in this trade: 9 stated that he would accept 1's item in a trade, 10 stated that he would accept 9's item, 3 would accept 10's and 1 would accept 3's. In the second loop, 2 receives 7's item, 5 receives 2's, 6 receives 5 and 7 receives 6's. (Other outputs are possible from this input.)

2

1:2
4:
2:3
5:1
3:4

0

3

1:5,9
5:1
9:1

1->5->1
2

1->9->1 is also valid in this case, but both cannot be completed. Either is acceptable.

Thanks for reading guys! Let me know if there are any improvements I can make.

Answer 13

Design and Solve a Maze

(this question on hold while the details are ironed out)

---

Your task is to play the roles of both characters in this scene from Inception. In it, Cobb gives Ariadne a challenge:

You have two minutes to design a maze that takes one minute to solve.

Some liberties will be taken on that description. Most importantly, this challenge is not time-based, rather scores are based on the effectiveness of your mazes and maze-solvers.

I apologize for the many edits to this challenge as we iterate towards an easy and fair format..

Part I: Maze format

All mazes are square. A cell in the maze is represented as a zero-indexed tuple row column.

Walls are represented by two binary strings: one for horizontal walls (which block movement between rows) and vertical walls (vice versa). On an NxN maze, there are Nx(N-1) possible walls of each type. Let's take a 3x3 example where the cells are labelled:

A   B | C
   ---
D | E   F
   ---
G   H | I

all possible vertical walls are: AB BC DE EF GH HI. Translated into a string, the walls shown are 011001 for vertical walls and 010010 for horizontal walls. Also, by "binary string" I mean "the characters '0' and '1'".

The full maze format is a string which contains, in this order:

• width
• start cell tuple
• end cell tuple
• horizontal walls
• vertical walls

For example, this maze:

   0 1 2 3 4
   _________
0 | |  E|  _|
1 |  _|_|_  |
2 |_ _ _  | |
3 |  _ _  | |
4 |____S|___|
start:(4,2)
end:(0,2)

is formatted to this:

5
4 2
0 2
00001011101110001100
10100110000100010010

Part II: The Architect

The Architect program creates the maze. It must play by the rules and provide a valid maze (one where a solution exists, and the end is not on top of the start).

input via stdin: Two positive integers:

size [random seed]

Where size will be in [15, 50]. You are encouraged to make use of the random seed so that matches can be replayed, although it is not required.

output to stdout: A valid size x size (square) maze using the format described in Part I. "valid" means that a solution exists, and the start cell is not equal to the end cell.

The score of an Architect on a given maze is

   # steps taken to solve
------------------------------
max(dist(start,end),(# walls))

So architects are rewarded for complex mazes, but penalized for each wall built (this is a substitute for Ariadne's time restriction). The dist() function ensures that a maze with no walls does not get an infinite score. The outside borders of the maze do not contribute to the wall count.

Part III: The Solver

The Solver attempts to solve mazes generated by others' architects. There is a sort of fog-of-war: only walls adjacent to visited cells are included (all others are replaced with '?')

input via stdin: the same maze format, but with '?' where walls are unknown, an extra line for the current location, and a comma-separated list of valid choices from this location. (This is a big edit that is meant to make it simpler to write a maze-parsing function)

example (same as the above 5x5 maze after taking one step left)

5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2

Which corresponds something like this, where ? is fog:

   0 1 2 3 4
   _________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|

output to stdout: One of the tuples from the list of valid choices

Each Solver's score is the inverse of the Architect's score.

Part IV: King of the Hill

Architects and Solvers are given separate scores, so there could potentially be two winners.

Each pair of architects and solvers will have many chances to outwit each other. Scores will be averaged over all tests and opponents. Contrary to code golf conventions, highest average score wins!

I intend for this to be ongoing, but I can't guarantee continued testing forever! Let's say for now that a winner will be declared in one week.

Part V: Testing

I have written a Python testing kit which includes a Maze class for parsing and writing in the proper formats, as well as an example architect/solver pair: Daedalus and the Minotaur

Available on both Dropbox and GitHub

Part VI: Submitting

• I maintain veto power over all submissions - cleverness is encouraged, but not if it breaks the competition or my computer! (If I can't tell what your code does, I will probably veto it)
• Come up with a name for your Architect/Solver pair. Post your code along with instructions on how to run it.

Answer 14

Author note: I was thinking about new genres today, and I had an idea. What if there could be a challenge that encourages people to write good code, instead of the code-golf gibberish we all know? Here's a challenge that attempts to do that. (This could even possibly be a new-genre, which would be great because it would bring in a greater high quality question volume to the site, but I'm terrible at coming up with names. Feel free to suggest something in the comments.)

---

Build your own image editor

code-challenge application-building (?)

For this challenge, you will create the best GUI image editor that can perform the most tasks that you possibly can... from scratch.

Tasks and scoring

Here are the features / tasks used to score your program. Each task is worth a certain amount of points, which is specified in brackets before the task description. For convenience, each task will also be prefixed by an ID string so that you can refer to them when describing your program.

• [1 A] Brush tool: Simple, click and drag the mouse to draw freestyle doodles. Must draw a contiguous path.
  • [1 A1] Ability to change the brush size.
• {TODO: etc., add more}

Requirements

Your editor must conform to the following requirements:

• Must accept input via the mouse. Tools (brush, flood fill, etc.) can be switched and configured with keyboard shortcuts, by clicking icons with the mouse, through a menu, or however you would like.
• You may not use a single built-in function to accomplish one or more of the tasks. For example, if your language has a built-in image flood fill function, you may not use it and must build your flood fill from scratch.

Final score and voting

This is the syntax you should use to describe your score in your answer:

# {language}, {your score} score
<sup>(features implemented: {A, A1, ...})</sup>

    {your code here}

{description, comments, other notes, etc. here}

The amount of votes your post has (upvotes minus downvotes) will be multiplied by {TODO: figure out a good number} and added to your score. (Do not add this to the score in your post, since votes change constantly; I will add them manually.) Voters, please vote according to the following criteria:

• elegance and readability of the source code
• ease of use of the image editor and how powerful it is
• remember to sort by "active" so that you're voting for new answers too, and not just the top voted ones!

Answer 15

Help Joe Bloggs with his password hash

Joe was confidently using "password1" as his main password to all his accounts until one day he received an e-mail from fBay. His account has been compromised and he must change his password immediately. Yet worse, the attacker had access to all Joe's accounts. Being an engineer, Joe thought: What if I could hash somehow my password using a keyword? I wouldn't need to remember any passwords and I would have a different one for each account.

Joe then creates an algorithm - he takes the domain name as a key and creates the password for each of his account consisting of:

1. (<consonants><vowels>)(alternating case: lower, capital, lower...)
2. <number of consonants><number of vowels>
3. <sum of consonants and vowels numbers converted to a character on US Qwerty Keyboard>

Joe then opens an account on SO to create a new code golf challenge. He uses stackoverflow as a key to generate password:

1. sTcKvRfLwAoEo - consonants and vowels in alternating case
2. 94 - 9 consonants, 4 vowels
3. 9+4=13, 1+3=4, Shift+4=$

Therefore, Joe's password for stackoverflow is: sTcKvRfLwAoEo94$

Challenge

Create a shortest function to generate a password given the rules above. The code should accept a string type parameter d and return/display the generated password.

Rules

1. Only Latin letters from the input should be used. Any other characters should be ignored.
2. Minimum input length is 1 letter. (guys at q.com need passwords as well!)
3. Assume Y is a vowel
4. If vowels or consonants are missing, use 0 accordingly. E.g. input a would result in a01!
5. Shortest code wins

List of vowels and consonants

US qwerty keyboard

Answer 16

Diplomacy

king-of-the-hill

Note for Sandbox: I have not finished (or really started) the control program for this game, because I wanted to see if there was interest in it before I dedicated too much time to the project. that means that the rule are still up to be tweaked, so please leave a comment if you have a suggestion, and comment or vote if you are interested in seeing this happen.

Diplomacy is a complex strategy game, with a very entertaining combat system. This challenge will be to write a bot to compete in a simplified version of diplomacy combat.

Rules

Rounds

Countries (bots) will begin the game with 10 health, representing their remaining will to fight. The goal is to eliminate all other Nations by attacking them until they have 0 health.

The game will consist of several rounds. On the first round, all bots will receive 2 numbers as command line arguments: The first will be the total number of countries fighting, and the second will be their number in the list. Each following round, bots will receive a command line arguments containing the actions taken by each player last round and a list of all bots and their remaining health separated by commas, like so

 1:A2,2:S3,3:A4,4:A3 1:10,2:7,3:7,4:1

Each bot must then output a desired action, which is one two commands

1. Attack a player. This is done by printing the letter A followed by the number of the player you with to attack. For instance, A3
2. Support a player. This will give the player you support a boosted attack.

Resolving combat

After player have sent in their moves, attack scores will be calculated thus:

1. All players start with a strength of 1, and one point is added for every player supporting them. For instance, if the moves are 1:A3,2:S1,3:A2,4:S2 then bot 1 has strength 2, bot 2 has strength 2, bot three has strength 1, and bot 4 has strength 1.
2. After strength has been calculated, bots will deal damage based on their strength. The formula for damage is (Attacker's strength + 1) - (Defender's Strength) In the above situation, player 3 would take 2 damage and player 2 would take 0 damage. Note that, unlike regular diplomacy, attacking a supporter does not cut support.
3. All attack take place simultaneously and independently. This means that if player 1 and 2 both attack player 4, then they each deal 1 damage. If player 3 were to support player 4, then player 4 would take no damage.

Round Ends

After combat has been resolved, countries that have 0 health will no longer be able to attack or support. However, they still will be listed in the input with an health of 0. When a bot is eliminated, all remaining bots will receive a single point.

Ending the game

The game ends when either 100 turns have elapsed or only 2 or less players remain. At this point, the player with the highest remaining health is the winner and receives 1 point. In case of ties, all tied bots will revive 1 point. If all bots die on the same turn, this is not a tied victory, but mutually assured destruction, and all bots will receive 0 points.

Scoring

The control program will run 100 rounds of the game. The winner will be the country with the most points at the end of 100 rounds.

Code

You may write in any language I can reasonably compile. I will make an effort to compile odd languages, but make no promises as to my ability to do so. Please provide your source code, an explanation, and a command line command to run your program.

Notes

• You are allowed to write to a file. In fact, you are encouraged to do so.

• Because this is a game where cooperation is paramount, you are allowed to write bots that work together, with the following restriction:

  • Only two bots can be written by a single player to work together at a time.

• Standard Loopholes apply. You are not allowed to change the way the control program runs. If you provide invalid input to the control program, the program will just skip your turn. However, you are allowed to spy on other countries files, and all bot programs will be in the same folder at runtime. This is war, after all!

• I reserve the right to disqualify any country that takes more than about a second to run, or that tries a loophole not mention within. That being said, if it is sufficiently clever I will probably let it go.

I will have source code up soon for a sample country that will be competing, and will post the control program when I finish it.

Answer 17

Check GenericScript source code for compiler errors

Given the source code for a GenericScript program as input, parse the source code to check that it conforms to the syntax rules for the language. The syntax definition for GenericScript is below. If a part of the source code is found to be invalid, the program should output "Invalid syntax", otherwise it should output "Valid syntax".

Win Criteria

This is code golf. Shortest code wins.

Syntax

Source code will be considered to be valid if it matches the rule for "Program" below.

Program             = Sequence
Sequence            = Statement [Sequence]
Statement           = SequenceBlock | Assignment | If | While | Output
SequenceBlock       = "{" Sequence "}"
Assignment          = Identifier "=" (String | Bool); 
If                  = "if(" Bool ")" Statement ["else" Statement]
While               = "while(" Bool ")" Statement
Output              = "print(" String ");"
Identifier          = {Any sequence of alphanumeric characters prefixed with "var" }
Bool                = StringEquals | Identifier
StringEquals        = String "==" String
String              = StringConstant | OperatorConcat | Input | Identifier
StringConstant      = "'"StringContent"'"
StringContent       = Character [StringContent]
Character           = {Any character except for "'"}
OperatorConcat      = String "&" String
Input               = "read()"

Whitespace is defined as any sequence of the ascii characters 9, 10, 13 and 32. Whitespace characters are allowed between tokens but are not required.

Rules

1. The answer should be a complete program
2. Standard input/output allowed
3. Standard loopholes apply
4. Universally testable answers only

Test Input

Valid syntax:

print('What is your name?');
varInput = read();
print('Hello ' & varInput);

Invalid syntax:

if(read() == 'DoTask1')
  print('Executing you'r command');

Answer 18

Text Adventure Game

Objective

Your goal is to develop a complete text-based adventure game with the shortest code possible. The player navigates in a dungeon composed of rooms. The game objectives are to find the treasure, slain the dragon and rescue the princess.

Rules

A room description is as follows:

You are in <description>.
You can go <exits>
You see <object>      (optional)

• exits can be "north", "east", "west", "south".
• description can be "a adjective cavern", "a adjective room", "a adjective corridor", "a adjective hall", "a cell", "the dragon's lair".
• adjective can be "dark", "murky", "small", "large", "narrow", "gloomy", "huge", "strange", "tiny", "broad", "old".
• object can be "the princess", "the dragon", "a troll", "a goblin", "a sword", "gold", "a key", "a trunk".

Exit list must be comma-separated and end with "and". If there is no object in the room, the last line is omitted.

Example of valid description:

You are in a murky room.
You can go north, east and south.
You see a goblin.

The game accepts the following commands (case is ignored) :

• GO direction : direction can be NORTH, EAST, WEST, SOUTH
• TAKE item : item can be SWORD, GOLD, KEY
• KILL monster : monster can be DRAGON, TROLL, GOBLIN. The DRAGON and the TROLL can be killed only if the user has the SWORD. If he hasn't, he loses the game. The weak GOBLIN can be killed with bare hands. When a monster dies, he disappears from the room. When the GOBLIN dies, he drops a SWORD. When the TROLL dies, he drops a KEY.
• KISS person : person can be PRINCESS, DRAGON, TROLL, GOBLIN. Kissing the princess validates one of the objective of the game, and the princess disappears from the room. Kissing a monster results in player death.
• OPEN object : object can be TRUNK. If the player has the KEY, the TRUNK object disappears and is replaced with GOLD.

OBJECTS
The player can perform an action on an object only if the object is in current room. A room can contain only one object ; a given object can be found in only one room. At the beginning of the game, only the following objects are placed in the map : PRINCESS, DRAGON, TROLL, GOBLIN, TRUNK. Other objects are not yet created.

ACTIONS

• If an action cannot be performed (e.g. GO NORTH where there is no exit to the north, or TAKE DRAGON, or DANCE GANGNAM STYLE), the message "Sorry, I can't do that" must be displayed.
• If an action can be performed, the message "OK" and the current room description should be displayed.
• You can read game commands from console or as a program parameter, as you wish.

MAP
The dungeon should have at least 30 rooms. The dungeon should not contains a series of more than 5 exits in the same direction. The exits between rooms must be consistent, e.g. if you go north from room #1 to room #2, there must a south exit in room #2 leading back to room #1. Every room name should be unique. There must be at least one room of each kind (hall, cavern, corridor...)

• A hall has at least 3 exits.
• A corridor can have only 2 exits.
• The cell has only one exit.
• There is only one dragon's lair and only one cell, containing respectively the dragon and the princess.

GAME END
The game ends when the player has been killed, or when he has taken the gold, slain the dragon and kissed the princess.

• If the player dies, the message "You have been killed by X !" is displayed, with X being the name of the monster.
• If the player wins, the message "Well done adventurer ! you've conquered the dungeon." is displayed.

Player should not be able to win the game in less than 40 turns.

Example

You are in a murky room.
You can go north, east and south.
You see a goblin.
> KILL GOBLIN
Ok.
You are in a murky room.
You can go north, east and south.
You see a sword.
> TAKE SWORD
Ok.
You are in a murky room.
You can go north, east and south.
> GO NORTH
Ok.
You are in a narrow corridor.
You can go south and east.  

Scoring

The shortest code wins.

Answer 19

Simulate a Quantum Circuit

Work-in-progress until I can make sure I know what I am doing and can finish the spec. code-golf or maybe advanced-code-golf

---

Quantum computers are the way of the future! Why wait, when you can simulate one now?

Your mission is to determine the output of a quantum circuit given its input and a diagram of logic gates.

Details

You will simulate a single quantum register and apply a series of quantum logic gates to it. A quantum register is a group of qubits. The state of a register is described by a vector of 2^N complex numbers, where N is the number of qubits in the register.

a|000>
b|001>
c|010>
d|011>
e|100>
f|101>
g|110>
h|111>

Above is a representation of a 3-qubit register. Each letter (a b c etc.) represents a complex number. There is an addition restriction that:

|a|^2 + |b|^2 + |c|^2 + |d|^2 + |e|^2 + |f|^2 + |g|^2 + |h|^2 = 1

Quantum gates

Gates are represented by a 2^N x 2^N square unitary matrix, where N is the number of input qubits. All quantum gates have the same number of outputs and inputs, since they neither create nor destroy qubits, they modify them.

A common quantum gate is called the Hadamard gate and acts on a single qubit. The matrix [H] looks like this:

1/Sqrt(2)  1/Sqrt(2)
1/Sqrt(2)  -1/Sqrt(2)

If we let [R] represent the following 1-qubit register:

0.6|0>
O.8|1>

Then the application of the gate is represented by [H][R] and gives the following result:

7*Sqrt(2)/10|0>
 -Sqrt(2)/10|1>

It is still true that the sum of the squares of the absolute values is equal to 1.

(TODO: explain how to apply gates to larger registers)

Measurement

Measurement collapses the state of the quantum register.

(Todo: Explain how measurement works)

Input

Output

Answer 20

BS

king-of-the-hill

The goal of this challenge is to implement an AI for the game of BS, also known as Bull Shit, Cheat, Bluff, and numerous other names.

The game is outlined in this wikipedia article.

The Rules of the Game

For the purposes of this challenge, the game will work like this:

1. A standard 52-card deck is dealt out to the players
2. The current rank is set to Ace
3. The play order is randomized
4. The player holding the Ace of Hearts goes first
5. On each player's turn:
   1. The current player plays some number of cards
   2. The current player states how many of what rank they played
   3. Other players may declare 'BS'.
   4. If any player declares 'BS':
      1. All players are notified of which players declared 'BS'.
      2. The played cards are revealed to all players.
      3. If the played cards are inconsistent with the current player's statement:
         • The current player adds the played cards and all cards in the pile to their hand
      4. If the played cards are consistant with the current player's statement:
         • The last player to declare 'BS' that round adds the played cards and pile to their hand.
   5. If no player declares 'BS':
      1. The played cards are added to the pile, without revealing them.
      2. If the played cards were inconsistant with the current player's statement, the current player may declare 'Peanut Butter'.
   6. If the current player has no cards in their hand, the current player wins.
   7. The current rank is incremented. (If the current rank is King, it becomes Ace.)

The Messaging Protocol

Play will be conducted via messages passed to the standard input and received from the standard output of each program. Each message will be terminated with a single newline character.

Cards

Card ranks are represented as one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, or K. Card suits will be represented as one of S, C, H, or D. Cards are represented as the rank, followed immediately by a suit. For instance, the Ten of Clubs would be represented by TC, and the Three of Hearts would be represented by 3H.

A hand of cards will be represented as a space-delimited sequence of cards. For instance, a hand containing the Queen of Spades and the Six of Diamonds could be represented as QS 6D or 6D QS.

Player Identification

A player will be represented by their nickname, followed by a number from 0 to 32768, in parenthesis, formatted as an integer. This number is guaranteed to be unique within a particular game. A player's nickname must have at least one character, can have up to 32 characters, and may only include letters, numbers, and underscores. For instance, a player with nickname ExampleAI and ID number 16480 would be identified in the game as ExampleAI(16480).

When the game begins, each program will recieve a message containing their unique ID:

Unique ID: uniqueID

Each player will reply with their desired nickname:

Nickname: name

Names may contain only alphanumeric characters and underscores.

After all players have responded with their nickname, the standard play sequence begins.

Standard Play Sequence

When a player's turn begins, each player will receive a be given a list of the players and their card counts, in order of play:

Players: player[count], player[count], ... player[count]

Each player will be informed of the contents of their hands:

Hand: initial_hand

The current the player will then receive this message:

Your turn: current_rank 

The current player will reply with a space-separated list of of cards:

Play: list_of_cards

Once they have submitted their play, all players will receive the number of cards, formatted as an integer, along with the current rank:

Player player plays: nunber_of_cards x current_rank

Each other player may then declare BS on that play by sending any message up to 32 characters, containing the capital letters B and S, and otherwise only contains lowercase letters and spaces. So any of Bull Shit, Bananna Split or Bacon Sandwich would be acceptable.

During this period, the current player may declare Peanut Butter by sending any message up to 32 characters, as long as it contains the capital letters P and B, and otherwise only contains lowercase letters and spaces. So any of Peanut Butter, Pancake Batter or Polish Bacon would be acceptable.

In order to allow the game to move faster, if a player does not wish to declare either of these things, they must instead send:

Pass

After all players have responded, all players will receive a list of players who called BS, in the order they called it:

Called BS: player, player ... player

If no player called BS, this message will still be sent --- it just won't have any players listed. If any player did call BS, then all players will recieve:

Player player had played: list_of_cards

If they were bluffing, all players recieve:

Player player was bluffing.

And the current player receives:

Your bluff was called: list_of_cards_recieved

If they were not bluffing, all players recieve:

Player player was not bluffing.

Player last_player receives the pile.

The last player who called BS recieves this message:

You misjudged: list_of_cards_received

The list of cards received will contain, in reverse chronological order, the contents of each play since the last call. (Separate plays will not be delimited in the list.)

If no player declared BS, and the current player was bluffing and declared Peanut Butter, then all players recieve the message:

Player player was bluffing.

If the current player has no cards left in their hand, all players receive this message, and the game terminates:

Player player won!

Otherwise, the next player's turn begins.

---

Example Game

The following might be considered a typical (abbreviated) message transcript:

Unique ID: 16481
> Nickname: Alice
Players: Alice(16481)[18], Bob(16479)[17], Charlie(16480)[17]
Hand: 2D 7S AS TC 5S JS JC 3C 8H 9D 5D AH 7C 6C 4D KC KH KS
Your turn: A
> Play: AS 2D AH
Player Alice(16481) plays: 3 x A
> PB
Called BS:
Player Alice(16481) was bluffing.
Players: Bob(16479)[17], Charlie(16480)[17], Alice(16481)[15]
Hand: 7S TC 5S JS JC 3C 8H 9D 5D 7C 6C 4D KC KH KS
Player Bob(16479) plays: 2 x 2
> BS
Called BS: Alice(16481)
Player Bob(16479) had played: 2H 2C
Player Bob(16479) was not bluffing.
Player Alice(16481) takes the pile.
You misjudged: 2H 2C AS 2D AH
Players: Charlie(16480)[17], Alice(16481)[20], Bob(16479)[15]
Hand: 7S TC 5S JS JC 3C 8H 9D 5D 7C 6C 4D KC KH KS 2H 2C AS 2D AH
 .
 .
 .
Players: Alice(16481)[3], Bob(16479)[41], Charlie(16480)[8]
Hand: KC KH KS
Your turn: K
> Play: KC KH KS
Called BS: Charlie(16480), Bob(16479)
Player Alice(16481) was not bluffing.
Player Bob(16479) receives the pile.
Player Alice(16481) won!

Your implementation may be written in any language, provided that you, upon request, provide a link to a suitable free-as-in-freedom compiler or interpreter that I can download and run at no cost. You also need to provide a UNIX command that can start your program.

Sandbox Questions

I want to gauge the community's interest in my problem before finalizing the spec and writing the control program.

I also need to get some idea of what sort of time-limiting scheme would be reasonable. In order to be able to to a lot of runs, I will need to be able to ensure that each AI doesn't take too much time to make its decisions, or prevent a stuck AI from holding up a game. I also need to be able to ensure that there is no motivation to deliberately stall a game. For example, if an AI determines that it is very unlikely to win, it might stall in order to prevent the game from finishing.

I would also like feedback on the messaging protocol:

• Are there any additional messages that you think should be passed?
• Would it be more convenient/clear if one or more of them were formatted differently?
  • Would it be better to use a different format for the plays message?
  • Would it be better to use different words to help distinguish the plays and played messages?

Answer 21

Turn my keyboard into a piano code-golf music

I'm sure we've all thought "man, wouldn't it be cool if my keyboard played musical notes as I program?". Of course, the answer to that question is a resounding no.

Regardless, it's what you're going to make.

Input

Input will be given, in real-time, on the keyboard.

The keyboard mapping that you will use is given in the diagram below. This kind of layout is used by several music programs already.

You can see that the bottom row (Z, X, C, V, B... ., /) represents all of the white keys, and the black keys are added on the row above (S, D, G, H, J... L, ;). This is then repeated on the two rows above, except the notes are an octave higher.

The notes C5 to E5 are repeated both on the lower rows and the upper rows.

So, if the user were to input Q (or ,) on the keyboard, middle-C (C5) should play. Similarly, if they input B, G4 should play.

^{The diagram above is an edited form of an image found here.}

Output

The only output will be sound. The actual sound used is up to you (it could be a piano sample or the internal beeper), but it should output sound at the correct pitch.

The program should not terminate by itself - the user should be able to keep inputting notes until they get bored.

References

• A diagram of the US keyboard layout (for comparison with the image above) can be found here.
• A table of the frequencies of notes can be found here. The range of notes that you will be using are from C4 to E6, inclusive.

Rules and Disambiguation

• This is code-golf, so the shortest correct implementation wins.
• Input should be given in real-time (i.e. no pressing Enter between each inputted note).
  • There should be no greater than a 0.25 second delay between pressing a key and hearing the note.
• Only programs that have the notes correctly mapped to the QWERTY keyboard will be accepted.
• The only output should be sound. There should be nothing displayed (except for a mandatory console window or similar).
• Polyphony (multiple notes playing at once) is not part of the specification.
• The program should not terminate by itself - a user should be able to keep pressing keys and hearing notes until they decide to close it.
• The waveform outputted is not important (it can be a beep or a piano sound or whatever you like); the pitch, however, should be accurate.
  • The file size of any sound files used will not be counted in the bytecount.
  • Please link any sound files you use with your answer.

Meta

• There are probably some obvious things that I've forgot to explain - please point these out!
• Also let me know if any of the wording is confusing.
• I've assumed that the readers will at least know very basic music theory (e.g. that there are 12 semitones in an octave). Is this okay?
• "Polyphony is not part of the specification" - polyphony is not the focus of the program, and therefore shouldn't be a consideration when submitting answers (i.e. if the shortest implementation means that one note will stop when a new note is played, then that's fine). Is this acceptable?
• Should I exclude the use of any external libraries that are designed to play sound or designed to repeat a function at regular intervals? Should I count sound file size in the score? I'm worried that having either of these would limit the possible entries to those that can use the internal beep (so, C/C++, C#, Python, Java?...).
• Another problem may be portability, or the lack thereof (e.g. C/C++ using the Windows API to access the Beep() function).

_{Really meta: answers/edits by me won't be done until the morning (approximately 9 hours from now).}

Answer 22

Let's talk about this...

I am planning on hosting a King of the Hill challenge in which bots will have to coordinate each other in order to be successful. The idea is to play a Diplomacy-like game between bots. The engine (still in development) will start the bots and communicate with them via stdin/stdout. There will be three phases:

0. Initialization

Well, this is not a recurring phase, it is just the engine telling each bot his id, the total number of bots participating and a seed, which can be used for generation of pseudo-random numbers (bots need to be deterministic).

1. Talking Phase (10s)

In the Talking phase, bots can send messages to each other (via engine) in order to coordinate their actions. To this end, a common language is necessary. This language should be able to express any ideas, plans and opinions a bot could have. However, not every bot is forced to be able to understand everything. Simpler bots might just ignore messages they do not understand.

Since I would like each player to be able to submit more than one bot, it is forbidden to implement a "secret handshake" by which bots recognize each other and from then on work together unconditionally.

2. Planning Phase (2s)

In this phase, bots submit what they want to do this turn. Each bot has a certain amount of supply (initially five), and can command one action per supply point. There are three possible actions:

1. Attack another bot
2. Support another bot's attack against a third bot
3. Defend another bot

There are some restrictions:

• Per opponent, you can either attack or defend them, and only once
• You cannot support an attack against a bot you also defend
• You cannot attack, defend, support yourself or a dead bot, and neither can you support attacks against yourself

3. Resolution Phase (as short as possible)

After all orders have been submitted, the engine will resolve them simultaneously in the following way:

The defending strength of each bot is the number of bots defending that bot. The attacking strength of each attack is the number of support orders for that attack. Each attack with an attacking strength greater than the defending strength of the attacked bot results in the supply counter of the attacked bot being reduced by one, and the supply counter of the attacker being increased by one.

Support orders which support a non-existent attack do nothing.

Then, all bots with supply of zero or less will be shut down by the engine: they died.

Afterwards, all remaining bots are informed about the decisions of other bots, and a new turn begins with its Talking Phase.

Further Rules

A game will consist of ten plus random number turns, so that "last turn betrayals" are not possible. The supply count of each bot will count towards their total score. I plan an ensemble of about 100 games. The bot with the highest total score wins. Tie-breaker will be the popularity (number of votes).

I am interested in your opinion: do you think that this challenge is too complex? I imagine that the code of a decent bot would be too long to fit in a post. So people would have to use github or pastebin or similar to submit their entries. The main problem imo is the interpretation of the (yet to be determined) common language.

Answer 23

Happy Holidays!

Introduction

With the holidays upon us, I decided to make an appropriately themed challenge. You are provided with a list of holidays and their respective date ranges, and given a date, you have to output a holiday greeting or the time remaining until the next holiday as appropriate.

Challenge

The list of holidays is below. You have to include it in your program (so no using a library or other external resource for this). Feel free to use any convenient format.

Start  | End    | Name
------ | ------ | -------------------
Dec 6  | Dec 7  | Saint Nicholas' Day
Dec 13 | Dec 14 | Saint Lucy's Day
Dec 24 | Dec 27 | Christmas
Jan 1  | Jan 2  | New Year
Jan 6  | Jan 7  | Epiphany
Feb 14 | Feb 15 | Valentine's Day

You are given a date as input (STDIN, function argument, or anything convenient) in YYYY-mm-dd HH:MM:SS format (e.g.: 2014-12-30 11:15:00).

You may assume that the time zone is either UTC or the system's time zone. The holiday lasts from 00:00:00 on the start date (inclusive) to 00:00:00 on the end date (exclusive).

If the date falls within the range of the holiday, you must output Happy <holiday>!, except if it's Christmas, in which case you must output Merry Christmas!.

If it doesn't, but another holiday is coming at most a week in the future, you must output:

<time> left until <holiday>.

where <time> is in the following format:

<days>d <hours>h <minutes>m <seconds>s

You can't use a library for converting the time to that format.

If there are no whole days, hours, minutes or seconds remaining, omit the number entirely. For example, 1d 0h 3m 4s should be printed as 1d 3m 4s.

If there are no upcoming holidays, you must output (no pun intended):

There are no upcoming holidays.

A trailing newline is optional, but be consistent in your program—don't add a trailing newline in one case and omit it in another.

Standard loopholes are obviously forbidden.

Test cases

Date                | Output
------------------- | ----------------------------------
2014-12-05 23:59:59 | 1s left until Saint Nicholas' Day.
2014-12-06 00:00:00 | Happy Saint Nicholas' Day!
2014-12-06 12:00:00 | Happy Saint Nicholas' Day!
2014-12-06 23:59:59 | Happy Saint Nicholas' Day!
2014-12-07 00:00:00 | 6d left until Saint Lucy's Day.
2014-12-14 00:00:00 | There are no upcoming holidays.
2014-12-24 00:00:00 | Merry Christmas!

Note that your program must work for any year, not just 2014.

Winner

This is code golf, so the submission with the fewest number of bytes wins. An answer will be accepted after a week, but I'll be happy to change the accepted answer if a new valid submission beats the previous high score.

---

code-golf date

Answer 24

Find the Minimum Width of a Set of Points

code-golfgeometrytime-complexity

Given a set of points in 2D space, you're to find the direction along which those points occupy the shortest width.

More formally, consider a set of n points P = {p₁, ..., p_n}, where p_i = (x_i,y_i), and a unit vector d = (x_d, y_d). Now K is the set of lengths obtained from orthogonal projection of P onto d. In particular, k_i = x_ix_d + y_iy_d. The width L of P along d is defined as max k_i - min k_i. Your task is to find the d along which L is minimal.

To keep things interesting, your algorithm's time complexity must not exceed O(n log n).

You may write a program or function, taking input via STDIN, command-line argument or function argument. The result may be printed to STDOUT or returned.

You can expect the input P to be in any convenient list or string format, but the input must not be pre-processed (e.g. sorted by coordinates). You may assume that the input contains at least 2 points and that no two points coincide.

The output must be correct to 10 significant (decimal) digits. Of course, d is only unique up to the relative sign of the coordinates, so there are two correct answers for each input. You may return either of those.

You must not use built-in functions related to this problem, like finding the minimum width of a polygon, or computing the convex hull of a set of points. You may use built-in vector/matrix types and operations.

Sandbox Notes

• I'll write my own solution at some point next week, and use it to provide a number of test cases.
• I'm also planning to add a handful of diagrams to clarify the definitions.
• The challenge was inspired by this proposal from Calvin's Hobbies, I think they are sufficiently different, as this problem here is only one approach to tackling his challenge (and even then it's only a subproblem). But if people think, they are too similar, and posting this one would make his a duplicate in the future, I'll retract this challenge (as I'd really like to see his posted some time).

Answer 25

The Genetic Game of Life

In this game, you play as cells (as in cellular automata). Your goal is to reproduce and kill off other cells on the board.

At the beginning of the game, two distinct configurations will be randomly chosen, one for reproduction, one for killing. The configurations will consist of 3 squares in a 5 by 5 area, not including the center square. For example,

OOXOX
OOOOO
OO OO
OOOXO
OOOOO

is an example configuration, where X represents a cell, and O can either be empty or filled. The configurations do not work if rotated.

The cells will be placed randomly, but equidistant from each other in a toroidal board. Cells will be placed in a random turn order.

Each turn, each cell will move a square one at a time. If a cell's movement creates the reproduction configuration with cells of the same type, and the center square is empty, then a new cell will spawn. If a cell's movement creates the killing configuration with cells of any type, and the center square is filled, then the cell in the center square will die.

When a new cell spawns, its DNA will be conglomeration of the DNA of the bots in the configuration. It will take its first turn after all other cells have taken 1 turn.

A cell that has not been part of a killing configuration after 200 turns will die.

The cell type with the most cells after 100K turns wins.

IO

Each turn, you will be passed a string of 1s and 0s representing your DNA, and a list of 49 integers representing a 7x7 grid of the vision around the cell. Specimens of the same type will have the same integer, and 0 will represent an empty square.

You must return a single character (N, E, S, W or X) representing the direction that the cell will travel. Attempting to move into another cell will result in your cell not moving.

Answer 26

Convert a Finite State Machine to a Regular Expression

Anyone can make a finite state machine for matching a regular expression. But what about a regular expression that emulates a finite state machine? This inverse operation is much more confusing.

Input

• A positive integer N, denoting the number of states in the machine. They are labeled 0 to N - 1.
• A list of accepting states of the machine. A string is considered to be accepted by the machine if it ends in one of these when there are no characters left.
• A list of triples (integer a, character b, integer c) representing the transition rules: when the machine is at state a and the current character in the string is b, then it may advance one character and move to state c.

You may specify the ordering and formatting of input.

Output

A regular expression that matches a string iff it is accepted by the finite state machine.

Additional Rules

• An input for the state machine may contain only printable ASCII characters which are not in the set ^$()[]|+?*\..

• The machine begins in state 0.

• You should not use any regex features other than |, (), ?, *, +

• You may not use libraries designed for this task (which apparently exist).

• The regex should match full strings (assume it is surrounded by ^ and $).

• An answer is either a program which prints the regex to stdout, or a function which returns the regex.

This is code golf: write your code in as few bytes as possible.

Sandbox Question

Should the FSM be deterministic or non?

Answer 27

ASCII Robot Wars

This idea is based off of the game "Besiege" (which I've never played) and a previous sandboxed idea of mine called "Epic Customizable Tank Battle."

The main idea is that your program is the AI that controls a robot equipped with various weapons. In this challenge, however, you will also have the opportunity to design your robot

List of Parts

(completely arbitrary and subject to total replacement)

• Wooden planks + and armored metal plates # make up the body of the robot.
• Wheels @ allow your robot to move. TODO - turning
• Most weapons are formed with two parts, a body and a pointer v^<> to denote the direction of aim.
• Cannons have a body of %, ballistas have a body of (something), spikes and battering rams are (something).
• Maybe helicopter blades can be X.
• Banners, which serve no purpose but decoration, could be $.

Example 5x5 robot

This robot has four wheels, three cannons facing forward, armored sides, and a flag in the middle.

@^^^@
#%%%#
#+$+#
#+++#
@###@

Controlling the Bot

I think this would make a really cool Stack-Snippet KOTH, since it is "visually interesting" to watch robots blow each other into pieces. Writing the controller will be hard because this is a major deviation from previous pixel-based KOTHs.

Answer 28

Sorting Source Code code-golfquine

Your task in this challenge is to write a program that takes no input and outputs This program consists of followed by your program's source code characters, but in alphabetical order.

Details

• You may only use printable ASCII characters and line breaks in your program.
• When outputting all source code characters, ignore line breaks and sort all characters by their ASCII number from lowest to highest.
• Reading your program's source code is not allowed.
• This is code-golf, so the shortest valid submission (in bytes) wins.

Here is a correctly ordered list of all printable ASCII characters (mind the space at the very beginning):

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Example

If the source code for your program is

print 'This program consists of ';
print this.sort();

then output must be

This program consists of       ''().;;Tacfghhiiiiimnnnooooppprrrrrssssssttttt

Answer 29

Strange question about transit schematics (title tbd)

graphical-output popularity-contest

In this challenge, your goal is to produce a schematic diagram of a transit network, given a list of lines and a list of stations as input. This is a popularity-contest -- the program's goal is to maximize the readability of the diagram by carefully choosing where to draw the stations and lines.

Each line in the transit network is formatted as a list of strings. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"

The first string on the list is the name of the line. The remaining strings are the stations that that particular line stops at. In this example the Peel Line stops at Douglas, Port Erin, Braddan Halt, Union Mill, and terminates at Crosby. The lines are bidirectional so the Peel Line would also go back the other way.

Of course, most transit networks will have more than one line. Each line of the transit network will have its own line in the input. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"
"Foxdale Line", "Ramsey", "St. John's", "Union Mill", "Bishop", "Foxdale"

Notice how both lines stop at Union Mill. This means that Union Mill is an interchange station for those two lines. A station is an interchange station if more than one line stops at it. Here is an attempt at what the network might look like:

This map does some things well but fails at other things. The lines are coloured different colours which helps differentiate the lines. In addition, the interchange station is emphasised with the white dot to show it is an interchange station. However, it fails at other things, the most prominent being that the text "Union Mill" is overlapping the line, and there is a lack of a key showing which line is which. When we fix these elements the map looks like this:

Much better! (Another way I could have resolved the Union Mill overlapping issue was to change the paths of the lines.) In addition, we can also have lines being a loop. This is indicated by the first and last train stations being the same. For instance:

"Island Line", "Port Erin", "Kitterland", "Kalfr", "Ardglass", "Kearney", "Port Erin"

The Island Line in this case is a loop that goes from Port Erin to Kitterland to Kalfr, then to Ardglass and Kearney, before finally returning to Port Erin, completing the loop.

With more complicated train networks, it becomes more difficult to arrange the stations and lines in a readable manner. Here are some inputs of varying complexity and density to try your program on. Some of them are based of actual networks, while others are made up for this challenge.

Challenge Input 1: Oslo, Norway:

"1", "Frognerseteren", "Voksenkollen", "Lillevann", "Skogen", "Voksenlia", "Holmenkollen", "Besserud", "Midtstuen", "Skådalen", "Vettakollen", "Gulleråsen", "Gråkammen", "Slemdal", "Ris", "Gaustad", "Vinderen", "Steinerud", "Frøen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"2", "Østerås", "Lijordet", "Eiksmarka", "Ekravein", "Røa", "Hovseter", "Holmen", "Makrellbekken", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"3", "Mortensrud", "Skullerud", "Bogerud", "Bøler", "Ulsrud", "Oppsal", "Skøyenåsen", "Godlia", "Hellerud", "Brynseng", "Helsfyr", "Ensjø", "Tøyen", "Grønland", "Jernbanetorget (Oslo S)", "Stortinget", "Nationaltheatret", "Majorstuen", "Blindern", "Forskningsparken", "Ullevål stadion", "Berg", "Tåsen", "Østhorn", "Holstein", "Kringsjå", "Sognsvann"
"4", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Høyenhall", "Manglerud", "Ryen", "Brattlikollen", "Karlsrud", "Lambertseter", "Munkelia", "Bergkrystallen"
"5", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Hasle", "Økern", "Risløkka", "Vollebekk", "Linderud", "Veitvet", "Rødtvet", "Kalbakken", "Ammerud", "Grorud", "Romsås", "Rommen", "Stovner", "Vestli"
"6", "Bekkestua", "Ringstabekk", "Jar", "Bjørnsletta", "Åsjordet", "Ullernåsen", "Montebello", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Sinsen", "Storo"

Here's what the official map looks like for some inspiration (click to enlarge):

TODO: more challenge inputs coming!

Sandbox Notes

• I've had this one sitting around for a while. I've wanted to try and make a popularity-contest graphical-output that wasn't just about making the prettiest image. So instead it's about making the most functional image, which I'm not sure is any better than the art challenges...
• Another thing I've been considering is changing it to a code-golf. I'd have minimum requirements for the final output (a key, coloured lines, distinguished interchange stations, etc.) and the shortest code that implemented all the requirements would win. I'd like your thoughts on whether this challenge would work better as code golf or popularity contest.

Answer 30

Permutations of the Fifteen Puzzle

POSTED