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

Can the chefs go? (formerly "Decode Triple G Start")

Answer 2

I've Got The Key, I've Got The Secret

A cryptography challenge in 2 parts.

Part 1

Implement a pair of programs in any language (the two programs could be in different languages if you wanted) to encode and decode a string of plaintext.

Input and Output

The encoder must take the plaintext (and an optional key) and return an encoded string. The decoder must take the cyphertext (and an optional key) and return the plaintext exactly as it was given to the encoder.

Restrictions

• The encoding and decoding code must be entirely implemented in the language - no libraries or cryptography functions may be used.
• The code (encoder+decoder) cannot be longer than 1024 characters.

Part 2

Implement programs (multiple programs per answer, one answer per entrant) which crack your opponents encryption algorithms.

Input

The cyphertext.

Output

The plaintext that generated the ciphertext.

Scoring

I will upvote all answers to part 1 which have working encryption and have obviously made an attempt at golfing their answer.

In order to be eligible to win, an entrant will have to have taken part in both parts of the question. Overall score will be (length of shortest program that cracks your code-(length of encoder+length of decoder)). Highest score wins and winning entrant's entries will be accepted on both questions.

Answer 3

Countability of Sets of Finite Sets

The aim of this challenge is to code-golf a program which returns an iterator that will iterate over all possible non-empty finite sets of positive integers.

So if running long enough, this iterator should eventually touch on {1}, {2, 5}, {3, 6, 112} (ie none of these should occur "at infinity")

You may choose the order in which you iterate over these sets, but the order must satisfy the following requirement:

Under a particular ordering, if S is the i'th set to be returned by the iterator, then we shall call i the index of set S.

Let a restriction (k,T) be an assertion about a set S that says S has size k and T is a subset of S.

For a given restriction (k,T) and iterator IT, let the restricted iterator be the iterator which takes sets returned by IT and filters out sets that don't satisfy the assertion, iterating only over the ones that do. In other words, if IT iterates over the sequence of all sets, the restricted iterator iterates over the subsequence satisfying (k,T). Now if S is the n'th set returned by the restricted iterator, then we'll call n the restricted index of S with respect to (k,T)

Your ordering must satisfy the property that for any restriction there exists a polynomial P(x) such that for any set satisfying the restriction (with index i and restricted index n), i < P(n)

Note that the following ordering is not acceptable:

{1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4}...

This is the sequence that comes from counting 1, 2, 3, 4, 5, 6... and listing the set bits in the binary representation of each number.

This is because the restriction (1, {}) satisfies only the sets {1}, {2}, {3}, {4}... whose index i as a function of their restricted index is i=2^(n-1) which is not bounded by any polynomial

---

Sandbox Questions

The reason for the strange requirement at the end is to disqualify any variants on the most natural ordering which simply counts upwards from 1 and enumerates the set bits in each number. In this ordering, the n'th set of length-one occurs at index 2^n which is non-polynomial.

I posted this problem originally, but didn't think of the obvious solution and so I left out the final restriction. I'd like to re-post it with the extra restriction. But first I'd like to know what people think. Is there a better way I can word that restriction or a more natural restriction I could impose instead?

Answer 4

The One with Two Parts

The aim of this challenge is to create a pair of functions which scramble and unscramble any given piece of text.

Part 1

In part one you post your scrambling function, along with the length in characters and language of your unscrambling function (but NOT its code). The length of the scrambler does not affect your score so you needn't golf it unless you want to. The two functions may be written in different languages if you wish.

Input/Output

The scrambling function should take one argument only - a string containing the input text - and return a string containing the scrambled text. The unscrambling function should also take only one argument - the scrambled text - and return the original text. The input text will be limited to characters in the ASCII set range from 0 to 127.

Part 2

In part two you try to beat your opponents' scores for their unscrambling functions. You MUST use the language they specify for their unscrambler in part one. Please give just one answer to this question containing all your unscrambling functions making it clear which question in part one each function unscrambles (maybe each answer in part one should give its scrambler a name for identification?).

Once the closing date (TBA) has passed all participants should post their unscrambling functions in their answer to part one to prove the length, language and functionality of their function.

Scoring The participants score will be calculated as follows: (unscrambler length from part one) - (shortest unscrambler length from part two). The participant with the lowest score wins and will have their answers accepted on both parts of the challenge. To be eligible to win a participant must have taken part in both parts of the question.

Example

In part 1:

• Bob posts a Python answer and says his unscrambler is a 165 character Python function.
• Fred posts a GolfScript answer and says his unscrambler is a 59 character GolfScript function.
• Joe posts a JavaScript answer and says his unscrambler is a 180 character PHP function.
• Jim posts a Ruby answer and says his unscrambler is 163 character Ruby function.

In part 2:

• Bob posts an 82 character GolfScript function to unscramble Fred's scrambled text. He also posts a 175 character PHP function to unscramble Joe's scrambled text.
• Fred posts a 181 character PHP function to unscramble Joe's scrambled text.
• Joe posts a 150 character Python function to unscramble Bob's scrambled text.
• Jim posts a 156 character Python function to unscramble Bob's scrambled text. He also posts a 91 character GolfScript function to unscramble Fred's scrambled text.

The scores:

• Bob scores 165 - 150 = 15
• Fred scores 59 - 82 = -23
• Joe scores 180 - 175 = 5
• Jim scores 163 - 0 = 163

so Fred wins.

Miscellaneous

I suggest that the closing date be two weeks after the challenge begins, and that unscramblers be posted to part one within 48 hours of closing date in order to be eligible.

Answer 5

Compile BF to TM

Your task is to write a compiler accepting a Brainfuck program (previous challenge: Interpret Brainfuck, wikipedia: Brainfuck) as input and outputting a Turing Machine which produces identical output when supplied with the same (correct) input.

You may select the output format from among the various formats accepted by the answers to Turing Machine Simulator.

The following links may also be useful.
An introduction to programming in BF
BF is Turing-complete
Programming a Turing Machine
Programming Praxis: Turing Machine Simulator

Equivalently, you may write a Brainfuck interpreter in TM, or any partial compilation/interpretation which results in a TM program as described above.

If we consider squares of the TM tape to represent bits (blank=0, mark=1) of the BF memory, then eight squares represent a cell. Each BF instruction translates to a minimum of 8 states of the Turing Machine.

'>' "advance" (++ptr) could be implemented by eight states (sixteen transitions):

adv8 _ adv7 R _
adv8 1 adv7 R 1
adv7 _ adv6 R _
adv7 1 adv6 R 1
adv6 _ adv5 R _
adv6 1 adv5 R 1
adv5 _ adv4 R _
adv5 1 adv4 R 1
adv4 _ adv3 R _
adv4 1 adv3 R 1
adv3 _ adv2 R _
adv3 1 adv2 R 1
adv2 _ adv1 R _
adv2 1 adv1 R 1
adv1 _ link R _
adv1 1 link R 1

where 'link' represents the first state of the following instruction.

'<' "rewind" (--ptr) can be implemented similarly by making leftward movements and rewriting the same symbol just read.

'+' "increment" (++*ptr) can be implemented by a ripple-carry from the Least Significant Bit to the Most Significant Bit, borrowing "rewind" states to back-up to normal position. If the LSB is on the left, it would look something like this:

inc8 _ link N 1
inc8 1 inc7 R _
inc7 _ rew1 N 1
inc7 1 inc6 R _
inc6 _ rew2 N 1
inc6 1 inc5 R _
inc5 _ rew3 N 1
inc5 1 inc4 R _
inc4 _ rew4 N 1
inc4 1 inc3 R _
inc3 _ rew5 N 1
inc3 1 inc2 R _
inc2 _ rew6 N 1
inc2 1 inc1 R _
inc1 _ rew7 N 1
inc1 1 overflow N 1

where overflow is a HALT state.

For I/O, the simplest way I can think is to place all input on the tape after the memory area, and expand the alphabet to include a symbol indicating the dividing line between the memory portion and the input portion of the tape. In fact, by expanding the cell size to nine squares, this symbol can serve as an input pointer, advancing as the input is consumed. (So "advance" and "rewind" now need 9 states each.) And another new symbol is written in front of the current memory cell to serve as the memory pointer. Inputting a byte therefore consists of schleping each bit over the entire space between the two tape positions with something like this:

input _ set-memptr L _
input 1 set-memptr L 1
set-memptr _ find-inptr R *
find-inptr _ find-inptr R _
find-inptr 1 find-inptr R 1
find-inptr $ schlep-bit R $
schlep-bit _ schlep-blank L _
schlep-bit 1 schlep-one L 1
schlep-blank $ schlep-blank L $
schlep-blank _ schlep-blank L _
schlep-blank 1 schlep-blank L 1
schlep-blank * deposit-blank R *
schlep-one $ schlep-one L $
schlep-one _ schlep-one L _
schlep-one 1 schlep-one L 1
schlep-one * deposit-one R *
deposit-blank _ etc R _
deposit-blank 1 etc R _
deposit-one _ etc R 1
deposit-one 1 etc R 1

where "etc" represents going to get the next bit in similar fashion.

To perform a loop (all BF loops are "while" loops, so the exit control is at the beginning and the end has a simple goto back to the beginning), we need first to check is the current cell is zero,

zero8 _ zero7 R _
zero8 1 body R 1
zero7 _ zero6 R _
zero7 1 left1 L 1
zero6 _ zero5 R _
zero6 1 left2 L 1
zero5 _ zero4 R _
zero5 1 left3 L 1
zero4 _ zero3 R _
zero4 1 left4 L 1
zero3 _ zero2 R _
zero3 1 left5 L 1
zero2 _ zero1 R _
zero2 1 left6 L 1
zero1 _ exit-loop R _
zero1 1 left7 L 1
left7 _ left6 L _
left7 1 left6 L 1
left6 _ left5 L _
left6 1 left5 L 1
left5 _ left4 L _
left5 1 left4 L 1
left4 _ left3 L _
left4 1 left3 L 1
left4 _ left3 L _
left4 1 left3 L 1
left3 _ left2 L _
left3 1 left2 L 1
left2 _ left1 L _
left2 1 left1 L 1
left2 _ loop-body L _
left2 1 loop-body L 1
...
loop-body-final _ zero8 N _
loop-body-final 1 zero8 N 1

So assuming the machine starts at tape-location 0, and the input is on the tape starting at 0 and going to the right, the "startup code" for this arrangement would be

startup _ place$ L _
startup 1 place$ L 1
place$ _ left270000 L $
left270000 _ left269999 L _
...

Jeez! The output is going to be HUGE! It might be better to treat the BF memory as negative-indexed and reverse all the _L_s and _R_s in 'advance', 'rewind', 'increment', and 'decrement'.

---

Questions:

Bonuses for optimizations? If I can implement this myself and provide a complete example output, The bonus could be "subtract the difference between your program's output for the example input with the example output". So eliminating states would be far more valuable than shrinking the code. One could possibly achieve a negative score!

---

Edit: Actually I think this is unreasonable unless the Turing Machine is augmented with non-reading (movement-only or epsilon) transitions. Duplicating every letter of the alphabet just to move over one square is just ridiculously painful. That means this challenge won't link-up nicely with the other one. :(

What about, instead of implementing the compiler, just devise a translation scheme (as above) that leads to a smaller output for a trivial sample program (based on calculating, rather than coding)? "Back of the envelope" compiler.

Answer 6

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

• King Wen sequence -- Wikipedia

• some nice info and images

I suppose I need to implement this first to avoid copyright issues! :)

Answer 7

Self-Golfing Code?

I don't know if I just didn't search hard enough, but I couldn't find any challenge regarding self-golfing code, or rather, any code that can deterministically reduce another set of text code to a much smaller program, yet still compile/run.

For example, take this:

int main() {
std::cout<<"Hello world 1!"<<std::endl;
std::cout<<"Hello world 2!"<<std::endl;
std::cout<<"Hello world 3!"<<std::endl;
std::cout<<"Hello world 4!"<<std::endl;
std::cout<<"Hello world 5!"<<std::endl;
}

And output this (as one possible solution):

#define A std::cout<<"Hello world 
#define B !"<<std::endl;
#define C B A
int main() {
A 1 C 2 C 3 C 4 C 5 B
}

Alternative:

Sub MySub()
Dim aNumber As Integer
Dim someString As String
aNumber = 123
someString = "abc"
MsgBox aNumber
MsgBox someString
End Sub

into (again, as one possible solution)

Sub m()
Dim a As Integer
Dim s As String
a = 123
s = "abc"
MsgBox a
MsgBox s
End Sub

Do we have a challenge for this?

If not, here are some rules I envision:

• Golfing code need not be in the same language as code to be golfed.
• Since compilers/running of code varies, newly golfed code must still run under same environment.
• Possible challenge scoring (multiple options -- thinking code golf):
  • 1: Shortest golfing code wins (not my favorite, since you can minimally shorten the base code, yet still write the shortest program).
  • 2: Shortest output of a set of pre-defined code (potentially limiting if participants are unfamiliar with the options available)
  • 3: Combination of length of golfing code and the output result of the same as input. (Ratio, summation, etc.) -- This I think is my preferred option.
  • 4: Multi-player Ratio of golfed size of other participants' own code versus their original submission. (Similar limitations to that of point #2.)

Answer 8

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>

---

I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

Answer 9

Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

• interpreting the language is fine
• translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

• Lisp
• APL
• J
• Brainfuck (already posted)
• Whitespace
• Forth

Answer 10

Missile Command

I'm making this CW, because it needs lots of help. I've been toying with this idea for a while. Think "battleship" to get in the right mind-frame. But, instead of ships, what you lay down are tiles which represent a Befunge-style program. This program controls the behavior of guided missiles ejected from the spawn tile. The goal is to program a missile which will obliterate an opponent's program block, as well as guard its own control block.

Haven't nailed-down the board size. 20x20 seems a little cramped.

         1         2
12345678901234567890
____________________1  4x20 program block
____________________2
____________________3
_______@____________4
....................5  12x20 arena
....................6
....................7
....................8
....................9
....................01
....................1
....................2
....................3
....................4
....................5
....................6
___________@________7  4x20 program block
____________________8
____________________9
____________________02

Tiles

@ spawn

Program control.

I'm imagining these to change direction of the code for "boustrophedon" writing.

this,then\
 txen,siht

haven't thought it all though, yet.

/

\

Movement.

F forward move forward one square

B back move back one square

L left turn left 90°

R right turn right 90°

So the submissions would be 4x20 code blocks which compete in a king-of-the-hill style.

Answer 11

Find all of the Scrabble numbers:

A scrabble number is a number n whose scrabble representation can score n points. As an example consider 12: its English spelling twelve has value 12 when it is placed on a stretch of six blank tiles. Since the highest ever reported 1 word scrabble score barely exceeds 2000 points, that will be the upperbound for this challenge.

Score and quantities for English:

2 blanks |  x1  |  x2  |  x3  |  x4  |  x6  |  x8  |  x9  |  x12 |
    1    |      |      |      | LSU  | NRT  | O    | AI   | E    |
    2    |      |      | G    | D    |      |      |      |      |
    3    |      | BCMP |      |      |      |      |      |      |
    4    |      | FHVWY|      |      |      |      |      |      |
    5    | K    |      |      |      |      |      |      |      |
    8    | JX   |      |      |      |      |      |      |      |
   10    | QZ   |      |      |      |      |      |      |      |

Considerations for either bonus points to scoring or extra requirements:

• Respect the board, only using gaps between double/triple letter and double/triple word scores that occur on a standard scrabble board.
• Respect the tile count for each letter.
• There are non-English versions of scrabble, maybe it should be 'language-agnostic' (lol, but seriously is there a reason to accept only English submissions?).
• Should the 2 blanks be allowed?

Answer 12

Sort all lines according to their corresponding Levenshtein Distance to the first line.

Shamelessly borrowed from: http://golf.shinh.org/p.rb?Levenshtein+Distance+Sort+FIXED

For a definition of the Levenshtein Distance, look here: http://en.wikipedia.org/wiki/Levenshtein_algorithm

Rules:

Takes input from stdin. Must work for all possible input. Get points for:

Smallest character count. Using Languages that are difficult to golf in. I think character count / the average values from here (http://golf.shinh.org/lranking.rb) might suffice?

Answer 13

Quine with syntax highlighting

---

I don't really have much of an idea how to properly pose a quine challenge, or what the common syntax highlighting rules are (or aren't) for various languages. So, I figured I'd just toss this concept up here for consideration and let the community flesh it out if they think it's a good idea.

quinecode-golf

Answer 14

McDonald's Drive-Thru

Changes from original:

• Provided some clarification of requirements with regards to impossible ordering quantities.
• Added specification to include total cost of order.
• Added specification to prefer lowest cost in case of a tie for number of packages.

TODO:

• Verify package sizes and pricing to be used for this challenge.
• Add pricing to output samples.
• Edit or remove "not have any limitations" rule. As currently written, it may force otherwise unnecessary bloating of code in some languages. (e.g.: PowerShell can handle numbers as uint64 to work with extremely large quantities, but it defaults to int32.)

We want to write a program to help McDonald's Drive-Thru employees assist their customers in ordering Chicken McNuggets. Chicken McNuggets only come in packs of 4, 6, 9, or 20. However, customers may not always be considering this when they pull up to the speaker.

For example, a customer might want to order 50 McNuggets but they really don't care what sort of packaging they come in - they just want to make sure they get 50 McNuggets one way or another. We want to help the customers get the best value out of their order - that is, to compose an order large enough to accommodate their needs in as few packages as possible with little to no excess.

Users will provide a request for n Chicken McNuggets. Your program's task is to provide the user with the sizes and numbers of McNugget packages needed to fulfill the order exactly. If the exact order cannot be fulfilled, the system must output an order which would meet the customer's needs with as little excess as possible. The system must also provide the total cost of the order.

Rules

• For values of n which can be ordered exactly, output how many of each pack must be ordered to achieve the requested quantity.
• For impossible orders (1,2,3,5,7,11), print "[requested quantity] is impossible. Have [nearest valid quantity >n]:" followed by the normal output for the nearest possible quantity >n.
• Impossible orders cannot be hard-coded. The program must be able to determine whether fulfilling an order exactly is possible without being explicitly told that 1,2,3,5,7, and 11 are impossible.
• Output must exclude any package sizes which do not need to be ordered.
• Output must be in descending order of package size.
• Output must include the sum total cost of all the packages. (Tax not included.)
• Further layout and formatting of the output is up to you, so long as it is unambiguous.
• Program must not have any limitations beyond those inherent to the system or programming language.
• If there are multiple ways to assemble the order in the least number of packages, output the method which has the lowest total price.

Examples:

Input: 8
Output:

2x4

Input: 43
Output:

1x20 1x9 1x6 2x4

Input: 11
Output:

11 is impossible. Have 12: 2x6

Relevant Numberphile Link

math code-golf

---

My main concern is that this problem may be too similar to this thread:

Work out change

Otherwise, are there any changes that should be made to this?

Answer 15

.... . .-.. .-.. --- .-- --- .-. .-.. -..

Another Hello World challenge, this time with Morse code!

Taking no input, your program must output HELLO WORLD in audible Morse code, printing each letter as it is played. For the purpose of this challenge, the following Morse code guidelines will be followed:

Duration of sounds:

• Dits are one time-unit long.
• Dahs are three time-units long.
• The gap between elements within the same character is equal to one dit.
• The gap between characters within the same word is equal to one dah.
• The gap between words is seven time units long.
• The length of "one time unit" is up to the programmer, so long as it is consistent throughout the message.

Letters:

• H: ....
• E: .
• L: .-..
• O: ---
• W: .--
• R: .-.
• D: -..

code-golf

---

I'm a little iffy on that last bullet regarding duration. Should I set a hard standard, or a minimum? If so, what to?

Answer 16

Find Maximum number of 4+ letter words from Scabble Tiles

The challenge is to find the most words with 4 or more letters you can make with one set of scrabble tiles.

The tile distribution is as follows:

2 Blank Tiles
A 9  N 6    +====+===========+
B 2  O 8    | 01 | K J X Q Z |
C 2  P 2    | 02 | B C M P F |
D 4  Q 1    | 02 | H V W Y * |
E 12 R 6    | 03 | G         |
F 2  S 4    | 04 | L S U D   |
G 3  T 6    | 06 | N R T     |
H 2  U 4    | 08 | O         |
I 9  V 2    | 09 | A I       |
J 1  W 2    | 12 | E         |
K 1  X 1    +====+===========+
L 4  Y 2
M 2  Z 1

Valid words are any words that are 4+ that are available in this file, the official scrabble dictionary.

Tiles cannot be used twice. This means you can only have 1 word with a K, J, X, Q, and/or Z unless you use a blank tile to represent one of these letters.

I'm not sure how I'd do scoring on this. I want shorter code to score better, but I don't want a short piece of code that finds a lot less words to score better than a longer piece that finds many more words.

Answer 17

Code Golf: counting all colors in an image

The goal of this Code Golf is to create a program that counts all colors in an image.

The input

The input will be a path to the image file.

The output

The output should be a number that indicates how much different colors your program found in the image.

The scoring

It's also important that your program supports much image formats, so I'll calculate the score based on this formula:

(character_count * 3) / (number_of_supported_image_formats * 2)

Some other rules

• The lowest score wins
• You're not allowed to execute an external program
• No Internet access
• A color doesn't just count if it's present in the palette, there really should be pixels of that color in the image.
• You should also count pixels with 0% opacity.
• #FFFFFF with 100% opacity is not the same color as #FFFFFF with 50% (of course, this is the same for all other colors).
• In vector image formats, if there's a red square (for example) with 50% opacity that overlaps a blue square, then this should count as two colors: red and blue.
• In vector image formats, in case of a gradient, the number of colors depend on which colors are used in the gradient. For example, if there is a red/yellow gradient, then you should count this as two colors: red and yellow.
• A paletted image format is another image format than the non-paletted variant.
• SVG 1.0 is another image format than SVG 1.1 (also count for other image formats).

Answer 18

Since this question is closed, I figured I'd post it here so further issues can be hammered out in Meta instead of the main site.

Known Issues:

• Some rules seem a bit unclear to some users.
• Clarification may be needed on what is needed to qualify for the "win percentage" bonus.
• Win percentage bonus may not be enough to be a real incentive. (This may just depend on the language or implementation.)
• Perhaps the win percentage bonus should be eliminated entirely, or maybe it should just be made a mandatory part of the spec.
• It's been suggested to use a simple 1-9 numbering system for the board positions, instead of any sort of X,Y coordinates.
• May want to allow some flexibility on the input format. (i.e.: Input must still specify the sequence of moves thus far, using whatever addressing scheme is specified in the spec, but leave the delimiters - or lack thereof - up to the developer.)
• Exactly what is expected of the program, such as how it can figure out whose turn it is or what the output should be, seems to need some clarification.
• Some test cases should probably be added.
• Clarification may be needed on the matter of what parts of the game we can assume have followed the guide already.
• Some flaws exist in the chart. (Two already mentioned in comments on the original post.) These should be identified and addressed so that proper expectations for those conditions are clearly set.
• Original post said we would not have to account for null input (i.e.: X asking what their first move should be) but this might be a good enhancement to add.

I personally think this is a great challenge. So far, I've had a very hard time finding a lot of room for optimization and got up to probably 400 characters in PowerShell before I gave up (not even half-way through the chart yet) due to some of the above issues. I'd really like to see what some more serious golfers could do with this, once the spec is properly hammered out.

---

Overview

This is the XKCD tic-tac-toe cheetsheet:

It's rather big, I know. But it's also your most valuable resource in your challenge.

The challenge

Create a program (in your language of choice) that uses the Optimal Move Cheatsheet (henceforth OMC) to output the optimal move when given a sequence of moves.

The input

Your program will be fed a series of moves in the following fashion:

A3 A2 B2 C2 ...

Where the first combination is always X, the second O, and so on. The letter is the Y coordinate (A-C, A at the top) and the number is the X coordinate (1-3, 1 at the left).

You may assume that the given combination is following the OMC's suggestion for each move at least for the player asking for a recommendation. You can also assume that the input will never be null (at least one move has been made). You must:

1. Figure out whether the next move is for X or O (you don't need to output this)
2. Use the OMC to decide the next move
3. Print the next move in the standard format A3

Optional:

You may also include the player's chance of winning (as a percentage) for 50 character discount on your score.

Answer 19

Implement addition using only division (code golf)

Thought you could implement division using only addition? Well try it the other way around!

Your job is to make a function or equivalent program that accepts 2 numbers and adds them using only division.

Rules

• No importing libraries
• You can't use anything dealing with mathematics except / and /=, (and their equivalents)
• No bitwise operations
• No string operations except input, output, return, and string concatenation

Answer 20

Code-Golf: Write a number as an expression that's as short as possible

The goal of this code-golf is to create a program that takes a number as input (using STDIN, command line arguments, or prompting for input), and outputs that number, but written as an expression that's as short as possible. So, 10000 should become 10^4. If there is no way to write an expression that's shorter than the number, then output just the number.

Other rules

1. No network access.
2. You're not allowed to execute an external program.
3. Only use the operators +, -, *, / and ^ (that's raising power, not XOR).
4. Order of operations must be taken in account. Use parentheses if necessary.
5. This is a code golf, so the code with the smallest amount of characters wins.
6. The input will always be smaller than 2^32.

Test cases

500000000   -->    5*10^8     or    10^9/2
999999      -->    10^6-1
10          -->    10
4294967295  -->    2^32-1
16384       -->    2^14

Answer 21

code-golf

Recognize spoken numbers of .wav file

The goal of this code golf is to create a program or function that recognizes (and outputs) the spoken numbers of a Waveform Audio File (.wav).
The rules are:

1. No network access and you are not allowed to run external programs.
2. The input will be the file path to the WAV file, and the spoken text will only be one of these digits: one, two, three, four or five.
3. The output must be the recognized spoken number of the WAV file.
4. You are not allowed to use third-party libraries.
5. This is a code golf, so the code with the smallest character count wins.

Answer 22

code-golfstring

Print Lorem ipsum

The goal of this code golf is to write a program that prints EXACTLY this text:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

The rules:

1. No external resources
2. The shortest code in bytes wins.

Answer 23

Here's my first proposal. It just occurred to me that it might be a bit difficult testing submissions without a functioning server, but maybe we can manage without? What do you people think?

---

The web hosting company I use has a jobs page that looks a bit like this:

If you want to work for them, you have to calculate the correct answer and submit it through this form. But you only have a few seconds in which to do this, so you need a script to do it for you. If you submit the correct answer in time, you're then given a hash code and an email address, and are asked to email your source code to this address, using the hash code as the subject line:

Using any language you like, write a script to download and submit this application form with the correct answer and hidden id field, and then email your source code with the hash code provided as the subject line. You can assume that the HTML source of the two pages is as follows:

1. http://jobs.example.com/

<!DOCTYPE html>
<html>
<head>
<title>Job Application</title>
</head>
<body>
<p>Evaluate 943 + 376 - 394 * 573 * 983 , and submit the answer with the following form.</p>
<form method="POST" action="apply.pl">
<input type="text" name="answer" value="" />
<input type="hidden" name="id" value="5d41402abc4b2a76b9719d911017c592" />
<input type="submit" name="submit" value="submit" />
</form>
</body>
</html>

2. http://jobs.example.com/apply.pl

<!DOCTYPE html>
<html>
<head>
<title>Job Application</title>
</head>
<body>
<p>Well done, that was the correct answer. Now email your source
code to [email protected] with the following text in the Subject
header:</p>
<p><code>1a79a4d60de6718e8e5b326e338ae533</code></p>
<p>But hurry, you only have five seconds!</p>
</body>
</html>

The only variable parts of these pages are:

1. The sum (up to 6 numbers separated by any combination of +, - and * with spaces on both sides)
2. The hidden id field that must be submitted with the form.
3. The hash code on the second page

You may assume that the sum can be calculated without overflow using 32-bit integer arithmetic.

code-golf

Answer 24

The Poet's Quine:

Write a quine with 1 or more rhyme scheme from http://en.wikipedia.org/wiki/Rhyme_scheme when read. The non-alphanumeric symbols aren't used for rhyming in this scheme (apart from the basic arithmetic signs like plus, minus, times and divided by), neither are comments. Words may be pronounced in any dialect, but it needs to be consistent within the same stanza (no having the first word be pronounced in a Scottish way and the second in a Welsh way).

Contest type would be popularity contest.

Thoughts on this proposal?

Answer 25

The shortest C program which generates the most instructions

Write a very short C program (length being defined by character count) which generates the most instructions when compiled. Of course, indicate your compiler, the version, and your operating system, and say what your program does. Linked libraries do not count!

Score

• Base score: 1/(characters) * (instructions)
• Bonus: if it computes something "useful," +20%

---

I'm fascinated by C challenges and compiler oddities, but I'm not sure about this question because of the variance you'll get between different compiler versions. Would it be acceptable to ask users to use an online resource which will compile C to assembly? I found two after a cursory search:

• C/C++ to Assembly v2
• GCC Explorer

Answer 26

How many pizzas do I need

code-golf

Write a program that figures out the minimum number of pizzas I need to order and the amount of left overs I will have.

Requirements

• Each pizza is 8 slices
• Each person gets one choice of pizza topping, represented by a letter A-Z
• Input in the format PVBC 2. Where each letter represents the choice of 1 person (e.g. P=Plain, V=Vegie, etc...), and the number is the amount of slices each person is allowed to eat. Letters can be in any order and do not need to be grouped.
• If I don't need a full pizza I must be able to do half one topping and half another topping, the output for a half and half pizza will be denoted by X/Y where X and Y are different toppings
• If I need multiple of a certain type of pizza they must be shown on one line (e.g. 2 x V Pizza). If there are different combinations the both result in the same, least, amount of pizzas, either output works
• Output must match the format below of one type of pizza per line and a comma separated list of left overs. The output must show the minimum amount of pizzas and leftover possible.

Extra Credit

• -20 - Take a 3rd argument that allows you to input the number of slices in a pizza, assume it will be an even number such that you can split it in half

Sample Input/Output

PCPVCB 3              (6 slices P, 3 slices V,  6 slices C, 3 slices B)
1 x P Pizza
1 x V/B Pizza
1 x C Pizza
2 slices P, 2 slices C, 1 slice V, 1 slice B left over

VBBCBBB 2             (10 slices B, 2 slices C, 2 slices V)
1 x C/V Pizza
2 x B Pizza
6 slices B, 2 slices C, 2 slices V left over

The 2nd example has many other combinations that could result in only 3 pizzas, this is just an example of what an output might be.

The shortest code wins.

Answer 27

Resurrect Adobe SubScript.

In an obscure conference procedings volume of forgotton lore, there's a quaint little paper which describes an early effort to implement a published subset of Adobe Postscript. There a line in the bibliography! :) But it cannot be found Nobody's ever heard of it. :(

Adobe Systems, "SubScript Specification", 1984.

But there's obvious utility in such a thing. So this is a hypothetical Micro-Manual Postscript, and its name shall be ASS[*]. :)

ASS is a dynamically-typed stack-based programming language with powerful graphics primitives. It has support for floating-point arithmetic, arrays and dictionaries.

The scanner reads white-space delimited tokens and attempts to interpret the token as a decimal floating-point number with optional sign (+/-). The program may (but is not required to) support exponential notation. Failing to recognize a valid number, the token becomes a name object, an atomic symbol type which is identified by the name (an "interned" string).

Types

As suggested by the scanner behavior and the operator list , there are the following object types:

• floating-point numbers (coerced to integer where appropriate)
• names (usually an index into a string table, for easy comparisons)
• arrays (an indexable sequence of objects)
• dictionaries (a key-value map of objects)
• operators (a pointer to a built-in function)

Operators

Operators are the basic actions predefined in the dynamic name space.

Stack Manipulation

• any   pop   -
  pop an object from the operand stack

• any₁ any₂   exch   any₂ any₁
  exchange top two elements

• any_N any_N-1 ... any₀ N   index   any_N any_N-1 ... any₀ any_N
  retrieve object from stack by position

where N is treated as an integer.

Arrays.

• N   array   array
  create a new array of length N

• any₀ any₁ ... any_N-1 array   astore   array
  fill array with objects from stack

• array   aload   any₀ any₁ ... any_N-1 array
  spill contents of array onto stack

• [   any₀ any₁ ... any_N-1   ]   array
  construct an array

• array index any   put   -
  put a value into array

• array index   get   any
  retrieve value from array

where index is treated as an integer.

The typical way to implement the array syntax is using an auxiliary type, the marktype object, and an operator counttomark. This is an implementation detail and is not strictly required but may be found to be convenient.

• -   [   mark
  produce marktype object as a sentinel on the stack

• mark any_N any_N-1 ... any₁   counttomark   mark any_N any_N-1 ... any₁ N
  count objects up to mark

Then the ] operator may be implemented in terms of the other array operators.

• mark any_N any_N-1 ... any₁   ]   array
  { counttomark array astore exch pop }

Dictionaries.

• N   dict   dict
  create a new dictionary, an associative container with room for N name-value pairs

• dict   begin   -
  push dictionary on dictionary stack, making names part of the dynamic name space

• -   currentdict   dict
  push copy of topmost dictionary on dictionary stack to the operand stack

• -   end   -
  pop and discard the topmost dictionary on the dictionary stack

• name any   def   -
  associate name with any value in topmost dictionary

• name   load   any
  lookup name in each dictionary in the dictionary stack from the top-down, returning the first match, or error if not found

Matrices and transformations.

A matrix is a 6-number array [a b c d e f] which represent a left-multiplying affine transformation matrix with the constant right-most column omitted.

 a b 0
 c d 0  =>  [a b c d e f]
 e f 1

• -   matrix   matrix
  returns a new identity matrix [1 0 0 1 0 0]

• matrix   setmatrix   -
  make matrix the current transform in the graphics state

• -   currentmatrix   matrix
  return current transform from the graphics state

• x y   transform   x′ y′
  transform (x,y) pair by current transformation matrix

Transforming a point involves multiplying the homogeneous vector through the transformation matrix:

          [a b 0]
[x y 1] * [c d 0] => [x' y' 1]
          [e f 1]

or, equivalently

x' = a*x + c*y + e
y' = b*x + d*y + f

Path description.

• -   newpath   -
• x y   moveto   -
• x y   lineto   -
• -   closepath   -

Clipping.

• -   clip   -
• -   clippath   -

Painting.

• -   erasepage   -
• -   fill   -
• -   showpage   -

The fill operator is where the magic happens. This operator is responsible for performing all of the graphics algorithms in sequence:

• Shape Mapping
  Tranform the coordinates of the path from user space to device space using the current transformation matrix.

• Shape Clipping
  Clip the portions of the path that lie outside the clipping path.

• Filling
  *Perform a scan-line rasterization of the (may assumed closed-) polygon described by the path into the output frame buffer.

And showpage copies the contents of the framebuffer to the actual output mechanism (window or file as described above).

... need to fill this out a little more. Math, graphics state, errors. Describing stroked lines is too much, I think. I'm not sure if it needs the forall operators for iterating through arrays and dicts. I'd like to avoid any need for overloading different types under the same operator name, and calling back to user code from an operator.

Output may be to a window, or to a file in a simple format, like pgm or even a text-file of hashes and spaces for rough bitmaps. No half-toning. Only bi-level filling of convex polygons will be required. But a program may handle more colors if desired.

This is CW in case anybody wants to help me type-in the basic operators.

Questions

Does it need anything more? Should something be removed as unnecessary? Does anyone have the spec??

Perusing my ps implementations of the graphics portions linked in the comments, I've noticed the following needed operators:

length
sub
roll
add
eq
array copy
mul
div
ne

I think it needs loops, too. It's possible to do with just recursion, of course, but loops are nice. And length, I think, needs to be polymorphic, operating on array or dict to retrieve the size for making copies and calculating indices. Add sin and cos, too.

---

And this would be a code-challenge.

[*] The moniker "ASS" is not intended as a disparagement of Adobe Systems nor any of their stupendous intellectual property. Rather it is merely intended to express frustration at the encountered difficulty in locating this document.

Answer 28

Off-topic bullshit detector

You run a blog about astronomy and for each post there is an area for comments, where people post comments. So, when you post news about the discovery of a new exoplanet, quickly there are some people commenting about its habitability or about the methods using for their detection, and you do answer those comments, very nice.

You already have a very good spam detector that handles people who tries to post links to viagra-selling sites, so you do not worry with these.

But there is always people who you really hate and makes you very tired. People who insists to post comments that every astronomer is tired and angry to see:

• Comments about creationism.
• Comments about ancient astronauts theory.
• Comments about religion arguing that instead of looking to the sky, people should look for God.
• Comments claiming that this is all a big lie made up by governments around the world, and in fact the man never went to the Moon and the Earth is flat.
• Comments about planet Nibiru, planet Hercolobus, planet X, planet Nemesis and similars.
• Comments about Mayan, Sumerian, or Nostradamus profecies about the end of the world in any particular date.
• Comments about the CIA hiding ETs in Area 51 captured from Roswell and similar stuff.
• Comments about conspiracies by secret groups controlling or willing to control the world, like the Illuminati, the Masonry, the New World Order, and similars.
• Useless flamewar comments that happens when people from two different groups in the previous categories disagree one with the other, posting comments that makes you sometimes doubt that intelligent life exists on Earth.

Your task is: Create a complete program that receives as input a text comment limited to 300 characters and outputs Yes/No, 0/1, Approve/Reject or something similar, rejecting the bullshit comments and accepting the valid ones.

Further, we have a few restrictions:

• As a policy of your company, everyone may comment any post at will, without the need of prior registration, so you can't build some sort of reputation barrier system for this.
• You can't also make comments be approved by other frequent commenters based in some reputation system. This happens because your competitor did that and the result was that the people that you want to avoid managed to take over the site being the ones with the most reputation and thus completely ruining your competitor's site. So, your boss decided that you should not build a reputation system.
• No use of external resources in the internet.
• You are allowed to save files in the disk or to use a database (please do not abuse this rule).
• If you do need, you can add a training program to pre-populate the program data.
• Your algorithm must be deterministic and consistent. I.E, in a given state for a given input, it always produce the same output. So, do not make it randomized nor use as input something like the colors of the pixels in the screen, the system clock or similar sources of entropy.
• [Lacking a rule to avoid exploiting the score system by overfitting the test data].

---

Ok, people, what do you think about this question? Good? Bad? Leave a comment.

This is still lack a winning criteria. Don't know if should be popularity-contest, some sort of code-challenge or something else. code-golf is surely out-of-question for this. What do you think?

Further, to make it testable, this will need some sort of corpus which falls in those bullshit categories and some perfectly valid as well. If you do have some suggestion on this, please, drop a comment.

Answer 29

Repost from previous sandbox, I realize this is somewhat similar to the Limerick program abit higher, but this was made before that.

The Poet's Quine:

Write a quine with 1 or more rhyme scheme from http://en.wikipedia.org/wiki/Rhyme_scheme when read. The non-alphanumeric symbols aren't used for rhyming in this scheme (apart from the basic arithmetic signs like plus, minus, times and divided by), neither are comments. Words may be pronounced in any dialect, but it needs to be consistent within the same stanza (no having the first word be pronounced in a Scottish way and the second in a Welsh way).

Contest type would be popularity contest.

Thoughts on this proposal?

Answer 30

Weighted letters combination to get 2014.

If a=1, b=2, c=3, d=4,...z=26, which letter combinations (in particular order) when operated by any one or two or three or all four of +,-,X,/ (in any order) will give 2014 as the result?

For example, j*t*j+n=10*20*10+14=2014, t*j*j+n=20*10*10+14=2014 and n+j*t*n=14+10*20*10=2014

are three different combinations.

N.B. - max number of consecutive same letters should be 2, see link http://www.oxforddictionaries.com/words/are-there-any-english-words-containing-the-same-letter-three-times-in-a-row