458
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2561 Answers 2561

0
\$\begingroup\$

Pareto optimality challenge

Write a class that maintains a pareto optimal set. This class must have these three methods:

k(int n): Constructs the class. N is the array size that all of the other methods must use.

boolean k.p(int[] n): Adds n if there exists no entry m in k such that each single term of m is greater than each corresponding term in n. The method must also return true if n has been entered into k, or false otherwise. n can be assumed to be of the length specified by the constructor.

boolean k.s(int[] n): Returns true if n was previously entered by the above method and there exists no other term m in k such that each term of m is greater than each corresponding entry in n. Returns false otherwise.

This is code golf, so shortest entry wins. Yes, programming languages without classes may be used, but all the usual properties of classes must be satisfied by the three methods above.

\$\endgroup\$
0
\$\begingroup\$

ASCII Snake

NOTES

It was pointed out to me that we already have had at least 2 snake challenges before. However, seeing as they are from a couple years ago, I think another snake challenge would be nice. Below (from the description section to the end) I describe a "classic" snake challenge.

However, I want to differentiate this from the classic challenge. I am more than open to suggestions in the comments below. My idea is the following:

Make an "infinite" snake game. That is, every 10 points, the level changes and the snake is reset according to the following pattern:

--The nth level contains n obstacles in the form of the '#' character. These work the same as walls. They are randomly placed around the map, the difficulty is that they cannot create a situation where an ungettable 'x' exists. for example:

------------------------------
| #                          |  11
|                            |
|              oooooo        |
|              o    o        |
|              o    v        |
|              o             |
|                            |
|                            |
|    x                       |
|                            |
------------------------------

would be unacceptable because if an "x" were to spawn in the corner, it would be an automatic game over. Also, the barriers may not form a wall which closes off areas of the arena.

I can flesh out this idea more if you think it is any good.

Please Give Me Feedback On This Question

When I have a working question, I will begin work on a basic solution in C++.

Description

The goal of this challenge is to create a real time (non-buffered input) ASCII version of the popular game Snake .

The board is 10 newlines by 32 spaces. The boundary consists of the " | " and " - " characters.

The snake body is made of the "o" character.

The snake head is v,<,>,^ depending on direction of travel (intuitively)

The snake eats " x ".

For example a game board might look like:

------------------------------
|                            |  11
|                            |
|              oooooo        |
|              o    o        |
|              o    v        |
|              o             |
|                            |
|                            |
|    x                       |
|                            |
------------------------------

In the new game, the snake has three body segments and a head. It gains one body segment every time it eats an "x".

The score (the number of segments+head) should be displayed somewhere on the screen.

The starting position of the snake and the starting position of the "x" is left to the writer.

After an "x" is eaten, the snake gains a segment, and a new "x" must spawn. "x"s may not spawn in a set of predetermined coordinates. They must spawn "pseudo-randomly" in the loosest sense of the phrase. This means that they can spawn using a random number generator or their position may be simply a function of the snake's position or some such simple rule.

The snake moves according to nonbuffered user input according to one or both of the following layouts:

"W" - change direction up.

"A" - change direction left.

"D" - change direction right.

"S" - change direction down.

AND/OR

"UP" - change direction up.

"DOWN" - change direction left.

"LEFT" - change direction right.

"RIGHT" - change direction down.

Note that, as per the rules of snake, at a given instance of the game, only three options are available to the player:

-- Do nothing (and continue moving straight)

-- Turn 90 degrees

-- Turn -90 degrees

Therefore, at a given instance, two of the movement buttons should be unresponsive. E.g. in the above case, only right and left are responsive.

Snake movement follows the normal pattern. For those of you not familiar with it: Let segment zero, $$s_0$$ be the head and segment $$s_n$$ be the very end of the snake. In a given frame, the snake has 3 choices, go straight, go left, or go right (from the snake's reference frame). $$s_0$$ moves into one of these spaces based on user input. Then $$s_i$$ moves into the space taken by $$s_{i-1}$$ on the previous frame.

If an "x" is eaten, then on the next frame the new segment $$s_{n+1}$$ is placed where $$s_n$$ was on the previous frame.

The game ends when the snake head collides with the snake body or a with a wall.

Rules

1) Only languages which are available for free may be used. Libraries may be used (for i/o, etc), however the actual snake program must be written by you. (if library overuse is an issue, it will be determined by up/down votes)

2) The game must be playable (i.e. the framerate must be acceptable on most machines, as determined by readers)

3) The winner is the program using the smallest number of bytes that fits the above description.

4) If an online compiler is available, it is recommended that you link it with your code so that others may play your game.

\$\endgroup\$
  • \$\begingroup\$ FYI, we've had a couple snake-based challenges already (1 2). \$\endgroup\$ – Geobits Oct 5 '15 at 16:07
  • \$\begingroup\$ Thank you. I'll either delete this post or come up with a way to make it fundamentally different. Since those were three years ago hopefully I can come up with a refreshing twist \$\endgroup\$ – Liam Oct 5 '15 at 19:06
0
\$\begingroup\$

Machine Learning

If you give a downvote please say why! (otherwise how will I learn, thanks)

The task is to create a simple program that "learns"

-->The challenge is to create a program which:

(1) outputs 50 integers (1 at a time) and waits for input after each.

The input given will be 1 or 0 depending on whether the number is "good" or "bad" based on a predetermined pattern (see the pattern section for more information)

(2) The program will then output something to the effect of

<< Learning done. Ready for testing.

At which point it will wait for integer input.

(3) My script will then input 50 integers (1 at a time) and the program will read the integers and output 1 or 0 depending on whether it thinks the integer fits the pattern.

-->Types of Patterns

Patterns will be of the following types, in an unknown order

- is divisible by x (x no larger than 20)

- is greater/less than x (x no larger than 100)

- is a perfect square

- has exactly x prime divisors (x no larger than 3)

- is coprime to x (shares no common divisors with x except 1) (x no larger than 100 and not prime)

numbers above subject to change if a case is made in the comments

-->Scoring

Bots will be scored on correct answers to my script input. The score is equal to the total number of correct answers across all 5 tests. There is a max score of 250.

Since I do anticipate perfect scores, ties will be broken by golf score of the source.

Further ties will be broken by submission time.

-->Example of A Test

note: "in" is for my input. "out" is for machine output.

The rule is "even-good, odd-bad"

out<<  10
in>>   1
out<<  1901
in>>   0

... more lines like this ....

out<<  Learning Complete. Ready for Input.

in>>   12
out<<  1
in>>   87
out<<  0

... more lines like this ...

Say the machine got 47/50 correct on this test, then it currently has a score of 47. I would then proceed to test it with 4 different patterns. And sum its score on each test for its final score.

-->Rules

(1) you may not use external tables, i.e. have a library that contains table for all possible tests. However, your code may generate such tables.

(2) the bot may not exceed an average time of 2 seconds per output. This goes for both the learning and testing sections. I really don't want to have to spend over 15 minutes per test. The average is so that it can spend a bit of start-up time to generate tables if it needs to.

(3) Use of external libraries is permitted, although it should be clear that the bulk of the work is yours. (this will be determined by downvotes)

(4) Languages must have a free interpreter available. If they don't I won't be able to test them. This rules out MatLab, Mathematica, etc.

(5) other rules may be added as necessary.

\$\endgroup\$
  • \$\begingroup\$ As interesting as this challenge sounds, I think you'd need a lot more than 5 test cases and 20 inputs to be able to see any sort of meaningful result. \$\endgroup\$ – Sp3000 Oct 6 '15 at 4:44
  • \$\begingroup\$ Really? Why do you say that? Regardless, that shouldn't be a problem, I could write a script to test the bots. \$\endgroup\$ – Liam Oct 6 '15 at 4:45
  • \$\begingroup\$ Given only 5 * 20 = 100 inputs, I'd expect there to be only a difference of a few incorrect responses between the top answers, which is small enough to be caused by chance. Also, is there any limit on the size of the programs? \$\endgroup\$ – Sp3000 Oct 6 '15 at 4:50
  • \$\begingroup\$ Okay, I'll bump it up to 50 questions per test. I'll edit the scenario shortly. No, no size limit (should there be), although I think that I'll put in something to the effect of "bot must make decisions within 1 min at all steps" \$\endgroup\$ – Liam Oct 6 '15 at 4:52
  • \$\begingroup\$ Mathematica is free. \$\endgroup\$ – LegionMammal978 Oct 24 '15 at 23:47
0
\$\begingroup\$

Mutating variable

Output
n number of lines (where n is from 10 to 30, each run is random) where each line is either (all of the lines have to be possible)

  1. Array of n random chars (or String with n random characters) made out of letters only
  2. random int divisible by n (by int I mean a whole number of any kind)
  3. random double whose first two decimal digits is n (by double I mean an number that has decimal digits) therefore for n=12 it will have format ###.12####
  4. random boolean true or false (by that I mean 1 or 0)

No two consequent lines may be same type

Another requirement is that in your code may call print (or System.out.println or whatever you use to print to screen) only once.

This is code-golf, so shortest code wins.

By random I mean use your language's built-in random number generator,

\$\endgroup\$
  • \$\begingroup\$ Why the strange "may only print once" requirement? Also, for random, it might be better to use a somewhat standard definition instead of "anything you like". That's just begging for the ubiquitous xkcd/Dilbert joke of constantly using the same output. \$\endgroup\$ – Geobits Oct 7 '15 at 17:11
  • \$\begingroup\$ @Geobits I edited the question to accommodate for the random suggestion you proposed. And for only one line to print. I just thought it would make task a bit harder is all, and I tried it on a few languages I know, and it did make things just a tad bit more tricky. \$\endgroup\$ – Quillion Oct 7 '15 at 18:38
  • \$\begingroup\$ Just a few more comments/questions: 1) You seem to have removed the part about all lines having to be possible 2) Is there a minimum number of choices for the random string/int/double? Otherwise I could just random between n and 2n, say. \$\endgroup\$ – Sp3000 Oct 7 '15 at 22:35
  • \$\begingroup\$ @Sp3000 I added requirement where all the lines have to be possible. Also what do you mean by minimum number of choices? I didn't quiteget the question you asked. \$\endgroup\$ – Quillion Oct 8 '15 at 13:08
  • \$\begingroup\$ You don't specify a range for the randomness, so the easiest thing to do is probably random between two possible options for everything, e.g. between n/2n for the int, or 0.n/1.n for the double, and "aaaaaaaaa"/"bbbbbbbbb" for the string \$\endgroup\$ – Sp3000 Oct 8 '15 at 13:14
  • \$\begingroup\$ @Sp3000 I thought that wherever I use word random I amply that they must use their language's random method. So if I say n random chars, I mean that every char has to be generated using the random method. How would I clarify that? \$\endgroup\$ – Quillion Oct 8 '15 at 14:55
  • \$\begingroup\$ Well the problem is that this has nothing to do with a language's random method. I could use random.choice("ab") or random.choice("abcdefg") - both use the language's random, but there's more outcomes in one than the other \$\endgroup\$ – Sp3000 Oct 8 '15 at 15:17
  • \$\begingroup\$ @Sp3000 so let the person use any random they like I guess. See no problem with aaaaa then bbbb and etc. As long as other requirements are met. The fun I wanted to see is printing all of those values and see the smallest amount of code. \$\endgroup\$ – Quillion Oct 8 '15 at 15:36
  • \$\begingroup\$ If you're fine with that then that's okay then I guess. Was just checking \$\endgroup\$ – Sp3000 Oct 8 '15 at 15:42
  • \$\begingroup\$ @Sp3000 so the question is ripe enough to post on the main site? \$\endgroup\$ – Quillion Oct 8 '15 at 16:23
  • \$\begingroup\$ I think if you add the explanation for "consequent lines" back in it'd be fine. The writing could be a bit better, but at least it's not as ambiguous now. Also, if by 10-30 you mean that 10 and 30 are both possible, then it might be good to write that as "10 to 30 inclusive". \$\endgroup\$ – Sp3000 Oct 9 '15 at 10:29
  • \$\begingroup\$ @Sp3000 Thanks for all your advice. I highly appreciate it! But I am leaving code golf for a while. As of late I noticed that it has become too toxic for my liking. Thanks for your help however :) \$\endgroup\$ – Quillion Oct 9 '15 at 12:57
0
\$\begingroup\$

Ceylon golfer (whitespace + comment removal)

As some people might have noted, I'm answering here often using Ceylon. This is usually done first writing a "normal" program, then slimming it down using whichever tricks I find, and at the last step remove all superfluous white space (and possibly also comments)

I want to automatize the last step.

Ceylon is syntax-wise a C-like language, so this golfer might be useful also for other languages. The details might differ, though.

This is similar to Remove Whitespace from a Java Program, but not the same, as Ceylon strings are a bit more complicated.

Details

A Ceylon program is a Unicode character stream, which can be lexically analized into a series of tokens, possibly separated by whitespace. (Only ASCII white space is allowed: space, tab, form feed (FF), line feed (LF), carriage return (CR).)

That whitespace is sometimes necessary – when otherwise the two tokens would stick together and form one token, or when a comment would become longer than before (but comments are to removed, too). Other whitespace can be removed.

Lines are terminated by LF, CR or a sequence of CR LF.

We have two kinds of comments:

  • Multiline comments start with /* and end with */.
  • end-of-line comments start with // or #! and end with the line (i.e. at the next line terminator).

Everything which is not whitespace or a comment is part of a token.

Tokens are of these forms:

  • Identifiers or keywords start with a (uppercase or lowercase) letter and then can contain letters, _ and digits. They can also start with \I or \i instead. (Examples are true, Integer, a, helloWorld, example1234, \Iexample1234.)
  • Literals:

    • numeric literals (decimal integer, hex integer, binary integer, formal floating point, shortcut floating point) have the form [0-9_]+[kMGTPmunpf]?|\$[01_]+|\#[0-9a-fA-F_]+|[0-9_]+\.[0-9_]+(e[+-]?[0-9]+|[kMGTPmunpf])? (where the _ is only allowed at certain places).

      (Maybe that can be simplified to [#$0-9][0-9a-fA-FkMGFPmunpf._]*, with the dot not being the last character. Not all such strings are valid numeric literals, but I guess you don't have to figure them all out. The details are in the specification linked above.)

    • Character literals have the form ' + single character (except " or \) or escape sequence + ', where an escape sequence is either a \{ + a name or code of a character + }, or a \ followed by a single (non-{) character.

      Examples: ' ', '←', 'a', '\'', '`', '\{#0020}', '\{#212B}', '\n', '\{ALCHEMICAL SYMBOL FOR GOLD}', '"', '\"', '\\', '/'.

    • String literals:

      • A simple string literal is " + a sequence of single characters (except ", \ and ` ) and escape sequences (see above) + "
      • An interpolated string literal (or string template) looks like a simple string literal, but can also contain `` + some non-string-code + `` inside the string. (In this non-string-code the whitespace and comment removal can be applied.)
      • A verbatim string literal is """ + a sequence of any characters, except """, + """. (There is no escape sequences or interpolation here.)

      There is further complication with multi-line string literals, but I guess for this challenge we can assume that there are no multi-line string literals.

      Examples for String literals: "", """""" (both the empty string), "Hello World!", "Escapes: \{#212B}, \{ALCHEMICAL SYMBOL FOR GOLD}", """non-interpreted Escapes: \{#212B}, \{ALCHEMICAL SYMBOL FOR GOLD}""", "some more escapes: \n, \r, \f, \t, \b, \\, \`, \', \"", "punctuation: ' ` \" and more text", """punctuation: ' ` " and even single \.""",

  • A lot of symbols are punctuation and operators:

     , ; ... { } ( ) [ ] ` ? . ?. *. = => + - * / % ^ ** ++ -- .. : -> !
     && || ~ & | === == != < > <= >= <=> += -= /= *= %= |= &= ~= ||= &&=
    

    The grammar is such that whitespace adjacent to one of those punctuation tokens is never relevant, so it can be removed.

Challenge

Write a program which receives as input a valid Ceylon program, and outputs the same program, with all comments and non-essential white space removed.

Whitespace is essential when without it two tokens would be one token – this applies specifically to keywords/identifiers and numeric literals. In those cases replace any string of whitespace with a single space.

(I guess there are some cases like 10else where an integer literal can be joined with a keyword, but for safety it is better to always have a space in there.)

Of course, whitespace inside a string is highly relevant, so it should not be touched.

If a removed comment was the only thing between two keywords/identifiers, make sure to put a space in there.


Open questions

  • I guess I should add some example inputs and expected outputs.
  • How to score this? Simply as Codegolf, assuming there will be correct answers? Or give some example programs and see which entry succeeds to make them smallest?
  • I guess most Ceylon programs to be golfed will actually be ASCII only – do we allow ASCII-only solutions, while giving a bonus for proper Unicode handling (in comments, strings, identifiers)?
  • Do we require full programs, or allow also functions which take+return strings (or character streams)?
  • Did I simplify the grammar not enough, or too much?
  • I can imagine some bonuses for finding the shortest representation of an integer of float literal .. not sure if that is worth the complication.
  • Another possible bonus would be to find the shortest way of representing a string literal (replacing some Unicode escapes by the actual characters, choosing between " and """, etc.).
  • Do we want to handle multiline strings correctly? Maybe as a bonus?
  • Another possible bonus would be to remove strings literals which are not passed or assigned to anything (these are often used for documentation comments) – but I'm not sure how to define that without specifying the whole grammar.

    (Those have leadings space in the following lines, up to the column where the literal started, which needs to be removed when lexing. If we change the alignment of the string literal, we need to adjust those spaces too. Here it can sometimes be useful actually not include a new-line before the string to minimize that indentation.)

\$\endgroup\$
0
\$\begingroup\$

Steganographic Image Encoding

Write two programs, an encoder and decoder. Score is the sum of the source in bytes.

Encoder Specs

Input:

  • a lossless 24-bit color image file
    • could be anything from BMP to PNG to PPM
  • an arbitrary data file
    • undefined behavior if one attempts to encode a too-large file in a too-small image.
  • an integer value, n, from 1 to 8, indicating the number of bits to use per subpixel.

Output:

An encoded image with the arbitrary data stored in the n least significant bits of the pixel data. The data must be stored in the pixels, i.e. not in some hidden metadata. How the data is serialized into the 3-D image space (height, width, color channel) is undefined.

Decoder Specs

Input:

  • an image produced by the encoder
  • the arbitrary file's length in bytes
  • the same integer value the decoder took indicating the number of bits per subpixel.

Output:

  • the identical arbitrary data file as was provided to the encoder

Requests for Comment:

  • Fix n to 1?
  • Encode the length/LSB's used in the image so you don't need to specify them again. (e.g. fixed format for a couple pixels to define it?) Requirement/Bonus?
  • Maybe have the arbitrary data file be another image of the same dimensions, a la the Wikipedia example (cat in a tree)? That could be kinda boring though; some very simple array operations could do it all. Or that could be clever. In that case, there's necessarily data loss of the hidden image.
  • If n was one and this only required an encoder, it would be the same as this, but this requires a matching decoder. One way encoding challenges I find dull.
  • I'd be fine with using image libraries to load/save the image
\$\endgroup\$
0
\$\begingroup\$

Objective

Given a string in Markdown, determine how much of the string is in bold and italic.

Test Cases

**Bold** --> 0
*Italic* --> 0
**_BI_** --> 2
__*abcde*__ --> 5
This is in **bold and _this_ is in italic** --> 4
\**_BI_** --> 0
\\**_BI_** --> 2
This is not in ___ bold-italic ___ --> 0
\$\endgroup\$
0
\$\begingroup\$

Implementations of linked lists

Given the source code of a function or method to delete the first node having value x if existed, from a non-cyclic singly linked list, in a specific programming language. Write a program or function (not necessarily in the same language) to decide what kind of implementation it is.

You don't have to check for all the cases. But the more intelligent your code is, the better.

The possible implementations need to be checked are:

Pointer of pointers

(Spec and examples to be added.)

Head node

(Spec and examples to be added.)

Moving the data

(Spec and examples to be added.)

(And maybe some others.)


Possible winning criteria:

  • Just .
  • Something like where a submission is valid if no shorter programs can do all the things documented in the answer.
\$\endgroup\$
0
\$\begingroup\$

Would someone like to write a crontab puzzle?

I have just asked for a software that displays all times at which a cronjob runs. As I think more about it, this might be a nice golfing question.

Unfortunately I'm not too familiar with the crontab specification, especially when it comes to combining operators such as

*/15,34,49-52 * * * * /path/to/command

Is that suitable for code-golf at all? If someone or a group of people would define it as a puzzle, I'd be glad to see it.

Starting point:

The program

  • takes a crontab line as input
  • checks if it is valid or not
  • if valid, from now on lists the next execution times
  • limited to a user definable amount

E.g.

program -n 10 30 17 * * *

produces 10 lines of output (assuming today is 2015-10-22 18:00)

2015-10-23 17:30
2015-10-24 17:30
2015-10-25 17:30
2015-10-26 17:30
2015-10-27 17:30
2015-10-28 17:30
2015-10-29 17:30
2015-10-30 17:30
2015-10-31 17:30
2015-11-01 17:30
\$\endgroup\$
0
\$\begingroup\$

Word Game KotH

First of all, I don't know what this game is called (or if it even has a name), but it's a modification of a game I've played a few times on road trips, especially with my family. I'll be thinking of a better name.

Any suggestions at all are very welcome.

How It's Played

There are 51 bots playing per game. At the beginning of the game, they are given a collection of letters (which is not necessarily a word), for example "a" or "jet." The bots take turns in a predetermined order. When it is a bot's turn it is passed the current word(s) and has four2 options:

  1. It can change a single letter to any other letter.
  2. It can add a single letter to any position in the word.
  3. It can swap any two letters in the word.
  4. It can split the word at any point.

If you didn't infer already, these actions are allowed with the caveat that their result is a valid word or two valid words, if the bot chooses to split. The game ends when the combined lengths of all the words in play are 3 times the length of the longest word in the dictionary used (e.g. if "onomatopoeia" is the longest word, the max length would be 36 letters since it has 12) or when only one bot remains. The bots are scored on how many turns they last*, and the winner of the game is granted a bonus3.

*The turn they lose on is not counted, so if the bot were to lose on its first turn it would have lasted 0 turns.

A word is valid if it is both in the dictionary and hasn't been played before.

Bots should take a reasonable amount of time in making their plays (no more than a few seconds).

Available Methods

isValid(word) returns a Boolean value (whether the word is valid or not).

getDictionary() returns the entire dictionary as a single string.

getPreviousPlays() returns the words previously played as an array (one word per element).

Once any of the following methods are called, the bot's turn is over:

change(index,letter) changes the letter at that index to the letter provided. This method cannot change a space to a letter (to prevent stalling).

insert(index,letter) inserts the provided letter at the provided index.

swap(index1,index2) swaps the letters at index1 and index2.

split(index) splits the word into two by inserting a space at the specified index. Both of these words have to be valid4

If any of the calls to these methods are invalid, the bot is disqualified for that game (treated as a loss).

Author's notes

  1. Basically a random number I determined; I don't know if it's too big or small.
  2. Is four too few to make this challenge interesting?
  3. This bonus is undetermined as of now, but I'd say 2 points tentatively. I'm also a bit unsure as to whether that is a good scoring method. Should it just be on victories or position in victory (i.e. first, second, third, etc. place)? I'm also worried that this might encourage users to submit bots that collaborate to last as many rounds as possible.
  4. Would it be more interesting if this ignored validity? e.g. if you have candies dog as the two words, splitting candies into can and dies would be valid even if either of those words had been played before.

I haven't done a KotH submission before, so I'd love feedback as to how to improve this.

Unimplemented Portions

Controller

This is the big unimplemented portion: I want to get feedback on the idea as a whole before diving into programming out a controller.

Scoring

I'm still unsure as to how the games should be scored.

\$\endgroup\$
  • \$\begingroup\$ I don't understand how the game starts. If I'm passed a bunch of random letters, surely the majority of the time I can't make a word and I lose immediately? \$\endgroup\$ – Peter Taylor Oct 24 '15 at 8:58
0
\$\begingroup\$

Create CHIQRSX9+ Analogue Program.

Your task is to create a program in same language, that when given a CHIQRSX9+ will print a that analogue. That analogue program will do similiar thing that CHIQRSX9+ program do. There's exception though. There's may be more than 1 instruction. Then it's meant to be executed

  1. C => Read until empty line and print all entered lines, including empty line.
  2. H => Print "Hello, world!"
  3. I => Read input until a newline then return that analogue
  4. Q => Print the analogue program source code. (Not the entered one)
  5. R => Read input until a newline then print that string after doing ROT-13
  6. S => Read comma separated number until newline and sort that.
  7. X => For this, X have undefined behavior.
  8. 9 => Print 99 Bottles of beer with correct pluralization.
  9. + => Increment Accumulator.

Printing instruction(C, H, I, Q, R, S, and 9) begin in a new line. After everything is printed, accumulator count is written at new line. Final newline is optional.

Example

If there's program X written in Haskell, then

X
CH
>main=interact$(++"\nHello, world!\n0").unlines.takeWhile(/="").lines

Which when compiled (Example as W) will do that

W
This is a line
This is another line

>This is a line
>This is another line
>
>Hello, world!
>0

Another example for Q

X
Q
>main=putStr(s++[';','s','=']++show s);s="main=putStr(s++[';','s','=']++show s)"

Yet another example

X
H+
>main=printStr"Hello, world!\n1"

Here is for indication of output. DO NOT print it.

Sandboxing Question

How about scoring. I want to reward short produced program. However, shorness of producing program is also counted. I guess just 10A+5B+C. Where A is length of original source code, B is length of "QQQQ" analogue program. C is length of "CHIQRS9+".

\$\endgroup\$
  • \$\begingroup\$ Well, please tell me what's wrong in my question? \$\endgroup\$ – Akangka Oct 24 '15 at 15:51
  • \$\begingroup\$ 1. I think this is a source-source compiler, which might be a more recognisable title than "create analogue program". 2. The HQ9+ family has a very mixed reception here, so you should probably expect some downvotes. 3. Why does the scoring system include a weight for votes? \$\endgroup\$ – Peter Taylor Oct 25 '15 at 7:43
  • \$\begingroup\$ 1. If it source-source compiler, Q will compiled to main=putstr"Q\n0" instead. \$\endgroup\$ – Akangka Oct 25 '15 at 13:10
  • \$\begingroup\$ 2. What's wrong about HQ9+ except that it can be used to cheat at golfing. \$\endgroup\$ – Akangka Oct 25 '15 at 13:11
  • \$\begingroup\$ 3. Just a tiny boost since "QQQQ" "CHIQRS9+" and original source code is already very big. Wait I'm writing it wrong. It must be subtraction. Else it will be penalty \$\endgroup\$ – Akangka Oct 25 '15 at 13:12
  • \$\begingroup\$ Is that vote annoying? \$\endgroup\$ – Akangka Oct 26 '15 at 8:05
  • \$\begingroup\$ Congrats on posting the 1600th answer in the Sandbox! \$\endgroup\$ – mbomb007 Oct 27 '15 at 15:57
0
\$\begingroup\$

Goal

The goal is to stitch several ordered lists of numbers into a single list that contains each of those lists as a contiguous sublist, with the numbers in the same order without gaps. The resulting list should be as short as possible.

Input

n ordered lists of numbers between -2^63 and 2^63-1

Ouput

A minimum-length list so that each input list appears within that list with its elements in the same order without gaps

Example

Input:

[1, 2, 3] [3, -38, 23424, 292] [0, 1, 2] [-38]

Output:

[0, 1, 2, 3, -38, 23424, 292]

The output contains each of the input lists:

[0, 1, 2, 3, -38, 23424, 292]
   [1, 2, 3]
         [3, -38, 23424, 292]
[0, 1, 2]
            [-38]
\$\endgroup\$
  • \$\begingroup\$ Many languages have built-ins both for flattening a list of lists and for removing duplicates, giving them a straightforward solution. I think that makes this too easy overall. The removing duplicates part is like this challenge, though it uses characters and requires preserving order. \$\endgroup\$ – xnor Oct 30 '15 at 21:26
  • \$\begingroup\$ But it is not only about removing duplicates, but also about finding the perfect combination of lists, so you have to figure out in which order you want to put the input lists together. Also it might be necessary to have duplicates in the output to be able to have all input lists in there. \$\endgroup\$ – Nitek Oct 31 '15 at 7:13
  • 2
    \$\begingroup\$ Oh, my mistake, I didn't realize the lists had to appear as contiguous subsequences. Let me edit that to try to make it clearer. \$\endgroup\$ – xnor Oct 31 '15 at 7:18
  • 1
    \$\begingroup\$ Out of curiosity, I found notes about this as an algorithmic problem, and it's NP-hard, so solutions are going to be exponential time. It would do good to include some test cases that a greedy algorithm would get wrong. \$\endgroup\$ – xnor Oct 31 '15 at 7:29
  • 2
    \$\begingroup\$ Looks like we already have this challenge. \$\endgroup\$ – xnor Oct 31 '15 at 8:53
  • \$\begingroup\$ Good catch. It's indeed the same problem. Thanks for pointing that out! \$\endgroup\$ – Nitek Oct 31 '15 at 9:03
0
\$\begingroup\$

Hello, World! Fitted in cases.

Your task is to take a line of input and print Hello,world! multiple times fitted to length of input. The cases of that character is fitted to input in same position(except shifted from deletion). If the corresponding character is non-alphabeth, you must use default case(lowercase except for "h" that is uppercase). And for punctuations, if the corresponding character is not punctuation, it will deleted. And if the corresponding character is space, the the ouput is space but it doesn't skip the "Hello,world" writing.

Example

Hello, world!
Hello, world!

About punctuation deletion and space insertion

I have a dog. I name it Underdog.
H ello w orld H ello wo Rldhellow

Explanation

Ihaveadog.InameitUnderdog.
Hello,worlD!hello,world!hellow
Helloworld!hello,World!hellow
HelloworldHello,wOrld!hellow
HelloworldHellowoRld!hellow
HelloworldHellowoRldhellow

Other examples

.....&^&%&*%&(&)^$#()&#()&@#)*%)#1-
Hello,world!Hello,world!Hello,world

UPPERCASES
HELLOWORLD

lowercases
helloworld

Abdeg,fGhiJ.
Hello,wOrlD!

Example Program

Here is ungolfed version of example program in Python. If there is error, correct me.

p=readline()
h="Hello, world"
i=0
k=""
for a in xrange(len(p)):
    if p[a]==" ":
        k=k+" "
        continue
    if isUpper(p[a]):
        if isAlpha(h[i]):
            k=k+upper(h[i])
        i=i+1
        continue
    if isLower(p[a]):
        if isAlpha(h[i]):
            k=k+lower(h[i])
        i=i+1
        continue
    k=k+h[i]
    i=i+1

Sandbox Question

This language is surely need to be fixed.

\$\endgroup\$
0
\$\begingroup\$

How am I doing?

My boss is a flashy sort of fellow. He likes all things animated.

He's asked me to write a progress bar to show the completeness of our super-secret project.

Now with me being me, I'm getting you to write this for me and showing the best one to my boss.

Task

  • Output a progress bar to stdout.
  • Whenever a newline is sent to stdin, increase the percentage on the percentage bar by 1%
  • If not already enabled and if possible in your language, set the terminal mode to non-echoing (stdin doesn't automatically get shown, think like when your typing in your password for sudo)
  • You may not assume the cursor is in a certain position, it must produce a progress bar relative to where you started the program (no absolute jumps)

To help you, you may use ANSI escape codes, ANSI colour codes and any UTF-32 unicode points.

The winner is the entry with the most upvotes.

Sandbox Notes:

  • Is this too broad? - I'm sticking to ANSI only but I'm not saying anything else about what it looks like.
\$\endgroup\$
  • \$\begingroup\$ Anyone care to say why this is worth a downvote? \$\endgroup\$ – Blue Nov 2 '15 at 17:12
  • \$\begingroup\$ Popularity contests tend to attract them (even the good ones). \$\endgroup\$ – trichoplax Nov 3 '15 at 19:47
  • \$\begingroup\$ This doesn't seem very tightly defined. Generally, the broader a popularity contest is, the more I expect it to gather downvotes. \$\endgroup\$ – trichoplax Nov 3 '15 at 19:48
  • \$\begingroup\$ Also, a simple requirement means most of the popularity of an answer will come from optional extras rather than meeting the spec. See the line between art and programming for other's thoughts on this. \$\endgroup\$ – trichoplax Nov 3 '15 at 19:50
  • \$\begingroup\$ Thanks for the link, I think I'll just let this question die here (I'm not sure if I should delete it or not, I'm going with not deleting it unless someone else says otherwise) \$\endgroup\$ – Blue Nov 3 '15 at 19:57
  • \$\begingroup\$ I usually delete my challenges once I know for certain I will not post them, but for ones I (or someone else) might be able to salvage in future I leave them around. \$\endgroup\$ – trichoplax Nov 3 '15 at 19:59
  • \$\begingroup\$ I don't think this one is ready for main, but remember that here (as on main) a lone downvote doesn't really mean anything. It could be anyone for any reason - rational or otherwise. \$\endgroup\$ – trichoplax Nov 3 '15 at 20:00
0
\$\begingroup\$

Kaprekar Transformation

Kaprekar Transformation is an transformation a number by following that instruction:

  1. Take n-digit integer.
  2. Sort it anscending and descending.
  3. Subtract the largest number and smallest number.

Your program have to do this:

  1. Take 1 number, x.
  2. Output all possible cycle and fixnums for doing repeated x-digit Kaprekar Transformation on all possible input. Rotation is considered same. So it is invalid to print:

    [00],[09,81,63,27,45],[81,63,27,45,09]

The output is a list consisting of list representing the cycle. You may using any style of list and even intermix it with restriction that it should not be ambigous. For example, comma separated item with item using comma separated item with enclosing bracket is OK, but not comma separated item with item using comma separated item without enclosing bracket.

Example:

8
>[00000000],[43208766,85317642,75308643,84308652,86308632,86326632,64326654],[63317664],[64308654,83208762,86526432],[97508421]

Or

>[00000000],[[43208766,85317642,75308643,84308652,86308632,86326632,64326654],[63317664],[64308654,83208762,86526432],[97508421]]
\$\endgroup\$
  • \$\begingroup\$ I'm afraid this is a duplicate: codegolf.stackexchange.com/q/2762/8478 ... also, for future reference, requiring one specific list format is bound to put an arbitrary set of languages at a massive advantage (those which can just use their native string format), while all others may have to do some non-trivial string processing which distracts from the (interesting) core of the challenge. \$\endgroup\$ – Martin Ender Nov 2 '15 at 12:56
  • \$\begingroup\$ @MartinBüttner No, it is the generalization. You have to handle arbitrary digit this time. And you have to detect cycle and find all cycle given a digit. Btw, there is typo. 2 39 is different example. \$\endgroup\$ – Akangka Nov 2 '15 at 13:04
  • \$\begingroup\$ Task one seems to be identical. The fact that the other challenge only has to work with 4-digit numbers doesn't seem substantial. I'm pretty sure almost any answer there can be adapted to a variable number of digits in a couple of bytes. As for Task 2, I did overlook that. You could simply reduce the challenge to just task 2 (I'm not even sure why you'd combine two independent tasks into a single challenge?). Even task 2 can be solved by simply looping the solution to task 1 over all possible X-digit numbers, but there might be other ways to golf this one. \$\endgroup\$ – Martin Ender Nov 2 '15 at 13:07
  • \$\begingroup\$ @MartinBüttner Then, why it isn't duplicate of codegolf.stackexchange.com/questions/1255/hitting-495-kaprekar ? \$\endgroup\$ – Akangka Nov 2 '15 at 13:14
  • \$\begingroup\$ Because it has been overlooked, I suppose. Fixed. \$\endgroup\$ – Martin Ender Nov 2 '15 at 13:15
  • \$\begingroup\$ @MartinBüttner Maybe add time limit make this different enough. \$\endgroup\$ – Akangka Nov 2 '15 at 13:15
  • \$\begingroup\$ I don't know. Since you have to output the entire list anyway, there is not much you can optimise beyond actually applying the transform until you hit a cycle. If you limited the challenge to the second task, a time limit might make more sense, but then again the second task might be different enough not to be a duplicate in the first place. \$\endgroup\$ – Martin Ender Nov 2 '15 at 13:17
  • \$\begingroup\$ @MartinBüttner Then remove task 1 and it won't be duplicate? And add speed limit. \$\endgroup\$ – Akangka Nov 2 '15 at 13:29
  • \$\begingroup\$ I don't even think a time limit is necessary for part 2. \$\endgroup\$ – Martin Ender Nov 2 '15 at 13:30
  • \$\begingroup\$ @MartinBüttner Is Task 1 still have to deleted. And please, don't discuss in the Chat, because I can't access that. Better use my email: christianirwanhw@gmail.com \$\endgroup\$ – Akangka Nov 2 '15 at 13:57
  • \$\begingroup\$ As I said above, I don't see why you would want to squeeze both tasks into a single challenge in the first place. (How would you score answers? Sum of the two solutions?) And if you split them up, then the first answer is certainly a duplicate, but the second is fine (and if you didn't split them up, I don't see why you'd redo the same challenge as part of another challenge either). \$\endgroup\$ – Martin Ender Nov 2 '15 at 13:59
  • 1
    \$\begingroup\$ The cycle identification is borderline duplicate of codegolf.stackexchange.com/q/26578/194 \$\endgroup\$ – Peter Taylor Nov 2 '15 at 14:32
0
\$\begingroup\$

Show How a Regex Is Matched

What your program or function should do:

  1. Accept input of two strings; let's call them r and s.
  2. Determine whether r is a valid regular expression (you can use any common definition of regex for this purpose, or any common definition of regexes but with lookahead and lookbehind removed; indicate which you're using). Otherwise, don't output.
  3. If so, determine whether s matches r as a regex. Otherwise, don't output.
  4. If so, output/print, in order, the part of r matched by each character of s, and also the part of s that matches it.

Note: You may use your language's regex-matching library for this.

Example:

Using PCRE; my inputs and outputs are r first and then s.

^.el*(o.*)*d\b and Hello, world!
^.ello......d\b and Hello, world

.\1\W and 800-555-1212
..\W and 00-

\b and a
\b and empty string

\d and a
no output (it doesn't match)


First floated in chat.
Not a dupe of Compile Regexes (which asks you to match regexes whereas this allows you to use the resources of your language to do so).

\$\endgroup\$
  • \$\begingroup\$ 1. It sure looks like a dupe to me: what's your argument for it not being a trivial transformation of the previous question? 2. In your examples, you seem to try to draw a distinction between outputting the empty string and not outputting anything. How does that work? 3. What exactly is the output format? E.g. the first example and the second example don't seem to be consistent in their treatment of metacharacters. \$\endgroup\$ – Peter Taylor Nov 5 '15 at 22:49
  • \$\begingroup\$ @PeterTaylor 1. It's not a dupe at all: the older question asks you to match regexes whereas this allows you to use the resources of your language to do so; also, the older question outputs a means of determining matching, without regard to how it's matched, whereas this requires an output of the latter. 2. This question is OBE because of the edit I'm doing to fix #3. 3. Yeah, I messed up an example: I'll fix that immediately. \$\endgroup\$ – msh210 Nov 5 '15 at 23:05
  • \$\begingroup\$ 1. With respect to the second half, see "simple transformation". But the first half is relevant, and worth editing in to the "Not a dupe" sentence. 3. I still can't figure out the output format from the examples. Obviously you want to ensure that it's not as trivial as asking the regex engine for group 0, but I think you need to first write a clear spec for the output and then write the examples (or, better, write a reference implementation to generate the examples). \$\endgroup\$ – Peter Taylor Nov 6 '15 at 7:27
  • \$\begingroup\$ @PeterTaylor, yeah, I'll have to work on it some more. If anyone else has ideas, please chime in! \$\endgroup\$ – msh210 Nov 6 '15 at 9:24
0
\$\begingroup\$

Python assembler

Python is a hybrid interpreted language. It first gets compiled into byte-code and then gets interpreted.

What does this byte-code look like you may ask? The dis module disassembles python code. Source code for dis module here

print "Hello, World!"

Gets disassembled into the following assembly.

  1           0 LOAD_CONST               0 ('Hello, World!')
              3 PRINT_ITEM
              4 PRINT_NEWLINE
              5 LOAD_CONST               1 (None)
              8 RETURN_VALUE

The output is divided in the following columns:

  1. the line number, for the first instruction of each line

  2. a labelled instruction, indicated with >>,

  3. the address of the instruction,

  4. the operation code name,

  5. operation parameters, and

  6. interpretation of the parameters in parentheses.

The disassembly of a basic for loop

for i in range(10):
    print i

gives

  1           0 SETUP_LOOP              25 (to 28)
              3 LOAD_NAME                0 (range)
              6 LOAD_CONST               0 (10)
              9 CALL_FUNCTION            1
             12 GET_ITER
        >>   13 FOR_ITER                11 (to 27)
             16 STORE_NAME               1 (i)

  2          19 LOAD_NAME                1 (i)
             22 PRINT_ITEM
             23 PRINT_NEWLINE
             24 JUMP_ABSOLUTE           13
        >>   27 POP_BLOCK
        >>   28 LOAD_CONST               1 (None)
             31 RETURN_VALUE

Your task:

Given some python code that has been disassembled, recreate the original code object as close as you can. You can take the disassembled code through any method you chose.

Your program will output all the arguments to recreate a python code object

That is to say your program will output the following

0,             
0,      
nlocals,              
stacksize,            
0,                
codestring,           
consts,               
names,                
varnames,             
"a string here",            
"another string here",
0,        
lnotab,               
(),             
()

You can work out the variables listed above but you have to output it all, even the constants.

  • nlocals - The number of local variables
  • stacksize - The maximum number of values held on the stack at once
  • codestring - A binary containing all the opcodes and their arguments
  • consts - A tuple of constants
  • names - A tuple of global variables
  • varnames - A tuple of local names (length of nlocals)
  • lnotab - A tuple containing a map of bytecode positions to line numbers

You may use the following code to disassemble a .pyc file:

import sys, dis, marshal

with open(sys.argv[1], "rb") as code_f:
    code_f.read(8) # Magic number and modification time
    code = marshal.load(code_f)
    dis.dis(code)

This is code-golf, the shortest code in bytes wins

Sandbox notes

Wow that was a long one. Perhaps too long?

Is the spec completely tight?

Should I explain anything further?

Am I making it too hard for non-python entries to take part?

Should I only make it a requirement to reassemble code without any functions/classes? I'm pretty sure dis doesn't show all that.

\$\endgroup\$
  • 1
    \$\begingroup\$ For one thing, yes this looks very hard for non-Python entries to me. For another, I think there's too much going on at once (there's a lot to output), and you don't explain much about how to output each specific component (ideally the post should be self-contained enough to work out what to do without knowing too much about Python/dis) \$\endgroup\$ – Sp3000 Nov 9 '15 at 15:41
0
\$\begingroup\$

Vigenère Cipher

Write a program that is capable of breaking a text encyripted using Vigenère cipher encyription.

Goals:

  • Take encripted text from STDIN and write plaintext to STDOUT.

Limits

  • Keyword will always be 3 letters in length.
  • Plaintext will always be in between 5-10 letters in length (inclusive).
  • All Plaintexts, Keywords and Encyripted Texts will be in English.

Scoring:

This is a . Shortest code in bytes wins.


I'm not sure if this is a valid and solvable question, so any suggestions are welcomed.

\$\endgroup\$
  • \$\begingroup\$ Dupe \$\endgroup\$ – Mego Nov 10 '15 at 18:19
  • \$\begingroup\$ I'm not sure this can actually be done without having a big dictionary for such a short piece of text. (Also, what does "encrypted texts will be English" mean?) \$\endgroup\$ – Paŭlo Ebermann Nov 15 '15 at 15:01
  • \$\begingroup\$ @PaŭloEbermann It means they will only contain english characters, no special letters from other languages. \$\endgroup\$ – goodguy Nov 15 '15 at 15:12
  • \$\begingroup\$ Then write "consist of the letters A-Z" instead (or similar if you allow spaces and punctuation – though that needs more specification). \$\endgroup\$ – Paŭlo Ebermann Nov 15 '15 at 15:14
  • \$\begingroup\$ For Vigenere, in general you can either try a "plaintext dictionary attack" (which means you'll have a list of valid plaintext words, like in the question linked by Mego – that would be a plain duplicate), or you try analysis of character frequencies or repetitions, which need a lot longer ciphertext in order to analyze anything useful. (Or you just output all possible plaintexts, and let the task of recognizing the correct one to some human.) \$\endgroup\$ – Paŭlo Ebermann Nov 15 '15 at 15:19
0
\$\begingroup\$

List Style Converter

[code:golf]

Task

Given a list, format it into list of the choice of the input. The list will be list of item defined below, but it can be multidimensional.

List Styles

There is 2 list separators:

  1. Space
  2. Comma

    For one dimensional list, only one separator is accepted. Space and only space between item is considered as separator. It is impossible to have more than 2 dimension without enclosing list of second dimension or third dimension. when parsing list, comma takes lower precedence and it is parsed with least dimension as possible. Space is optional between ] with [; } with {; and ) with (

    There is 3 list enclosure:

  3. [...]

  4. (...)
  5. {...}

    Closing bracket must be present.

Item

There is 2 types of item, another list or those following regex [0-9a-zA-Z]* or everything enclosed with single quote or double quote. If enclosed with single quote, it can contains double quote and vice versa. There is no zero-length item

Here is valid non-list item

98Az
Helloworld
"Hello, world!"
"It's house."

Here is the list

Hello, World!
Space then it is list
()

Here is invalid item.

!$%#%^$*%%^&%^&$%#:;,./<>?
Helloworld!

Input

The input consist of string of number then space then list as defined above. The number indicates the output format.

There are n digit of number where n is dimension of the input array. each number correspond with this one. (Table formatting needed). The dimension is counted from outer into inner. You may assume that there is no two 0 or 1 without being separated by 2 - 7.

  1. 0 = unenclosed comma list
  2. 1 = unenclosed space list
  3. 2 = parantheses enclosed comma list
  4. 3 = parantheses enclosed space list
  5. 4 = square bracket enclosed comma list
  6. 5 = square bracket enclosed space list
  7. 6 = curly bracket enclosed space list
  8. 7 = curly bracket enclosed space list

Output

A identical list but with formatting changed according to input (i.e. each item it list is identical). Space not between list is allowed

Test cases

> denotes output # denotes comment

6 Hello, world
> {Hello world}
5 (1, 1, 2, 3, 5, 8, 13, 21)
> [1, 1, 2, 3, 5, 8, 13, 21]
#Alternatively
> [1,1,2,3,5,8,13,21]
#Or
> [ 1,1, 2,3, 5,8, 13,21 ]
#But it is invalid
> [1,1, 2,3, 5,8, 1 3,2 1]
#Also
> [1,1,2,3,5,8,13,21,]
10 Hello, I am doctor
#Parsing rules that space separator bound tighter
> Hello I,am,doctor
01 Hello, I am doctor
> Hello, I am doctor
0 "Not to be confused be space or comma in a quoted item"
> "Not to be confused be space or comma in a quoted item"
51 [1,2] [3,4]
> [1 2,3 4]
51 [1,2][3,4]
> [1 2,3 4]

Sandbox Question.

The format needs helps. Needs pointing when there is ambiguity.

\$\endgroup\$
  • \$\begingroup\$ I'm not sure that I fully understand this. To take a couple of your examples, Hello, World! appears to have two separators (a comma and a space): is it a one-dimensional three-element list, or a two-dimensional list? Is () a one-dimensional list or a two-dimensional list? And in the input, which order are the dimensions listed in, and what constraints are there on which formats can be used at which levels? (E.g. 00 is clearly not going to work, but I'm not sure whether 010 is permitted). \$\endgroup\$ – Peter Taylor Nov 16 '15 at 23:20
  • \$\begingroup\$ @PeterTaylor That's why I post the challenge here, because this challenge is nontrivial to writing. It is one dimensional comma separated list. Only space between item is list separator. Comma (except inside quote) isn't valid part of item. The input order is from outer into inner. You can assume that 00 and 010 isn't never entered. \$\endgroup\$ – Akangka Nov 17 '15 at 8:35
  • \$\begingroup\$ () is one-dimensional list since you have to it is parsed with least dimension as possible \$\endgroup\$ – Akangka Nov 17 '15 at 8:43
  • 1
    \$\begingroup\$ I'm afraid that I'm even more confused than before about spaces and commas. You seem to be saying that in the example 6 Hello, world a (comma plus space) makes a single separator in a one-dimensional list, whereas in 10 Hello, I am doctor a (comma plus space) is two distinct separators in a two-dimensional list. Do you have a reference implementation which we might be able to use to reverse-engineer the spec while the question is still in the sandbox? \$\endgroup\$ – Peter Taylor Nov 17 '15 at 16:55
  • \$\begingroup\$ In "Hello, world", "Hello" and "World" can be 1-item space separated list, however, lowest dimension takes precedence. In "Hello, I am a doctor" It is list containing 2 item. One is 1-item list, other is 4-item list. \$\endgroup\$ – Akangka Nov 18 '15 at 9:56
0
\$\begingroup\$

Triangularity

The diagram of the triangle the program needs to solve.

This is a challenge where you have to work out the length of a given w and h.

To qualify as a correct solution:

  1. The program uses STDIN to get the values of w and h.
  2. The program uses STDOUT to output the value of a in the above diagram.

The shortest code in bytes wins.

Tags: code-golf, maths

\$\endgroup\$
  • \$\begingroup\$ What's the formula? Unless it's very complicated, I expect it will be totally straightforward to golf. \$\endgroup\$ – xnor Nov 18 '15 at 11:45
  • 1
    \$\begingroup\$ @xnor, a = w/2 * sin(atan(h/w)). The diagram throws in some irrelevancies and omits a relevant line, but it's not an interesting problem. \$\endgroup\$ – Peter Taylor Nov 18 '15 at 13:02
  • \$\begingroup\$ @Peter Should I post this or do you think it's too easy? \$\endgroup\$ – Tobsta Nov 18 '15 at 21:31
  • 1
    \$\begingroup\$ @Tobsta I think it's too straightforward. Languages with trig will use the formula Peter gave, and the rest will do something like h*w/sqrt(h*h+w*w)/2. \$\endgroup\$ – xnor Nov 18 '15 at 21:58
  • \$\begingroup\$ @xnor Ok, got it \$\endgroup\$ – Tobsta Nov 18 '15 at 22:54
0
\$\begingroup\$

Wildcard Golf

Introduction

I've read this problem long time ago somewhere but I still don't know what's the best solution, so I'm posting it here. I don't remember the original author or wording so here is all in my own words.

This is different from regex golf because only two wildcards, * (equivalent to the regex .*) and ? (equivalent to the regex .), are allowed.

Challenge

You are given two lists of strings. You need to generate the shortest wildcard that matches all strings in the first list (the wanted-list) and none in the second list (the unwanted-list). In the wildcard, you can use * to match 0 or more chars and use ? to match any one char.

For simplicity we can assume that inputs only have lowercase English characters and each string won't be longer than 100 characters. But the list can be very long (like several thousand), so speed of your program is important.

The correct answer that has the lowest average-case theoretic time complexity wins. In a tie, an easier-to-read answer wins.

Example Input and Output

Input:

  • Wanted list: abacum, academ, alarm, adam
  • Unwanted list: alien, african, atom

One possible output: a?a*

I'd also like to hear about how to approach this problem, and how to prove the theoretic lower bound of time/space complexity.


I'm new to this so comments are welcome. I'm not sure if my winning criteria is clear and practical. Also I don't know what tags I should put there. This is not a code-golf question.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's already been done \$\endgroup\$ – Peter Taylor Nov 17 '15 at 21:46
  • \$\begingroup\$ Thanks for pointing it out @peter-taylor. This challenge is different in terms of using wildcards, not regex. So you think it is not worthy to post? \$\endgroup\$ – Yan Li Nov 17 '15 at 22:06
  • \$\begingroup\$ Ah, I thought you were using wildcard as a synonym of regex. I take the point that removing alternation does make quite a different problem. Although it has the downside that there are insoluble cases (e.g. I don't think your wildcards can separate a wanted list of a and abba from an unwanted list of aba), so you'd need to specify how those cases should be handled. \$\endgroup\$ – Peter Taylor Nov 17 '15 at 22:16
  • \$\begingroup\$ Thanks! I'll edit and clarify these concerns. \$\endgroup\$ – Yan Li Nov 17 '15 at 22:18
0
\$\begingroup\$

C++ Expression Matching

So, I like C++. And I like regex matching puzzles (heck, "regex golf" is what first got me lurking on this site). Might as well try to sort of combine the two!

Rules

Write a full program that takes as input two lists of zero to five integers in the range [1, 127], and outputs a string representation of a C expression that evaluates to nonzero / true for all integers in the first list, and zero / false for all integers in the second list. Input can be taken in any convenient form.

As a special case, if the second list is empty, then the expression returned must evaluate to true for only the integers in the first list, and false for all other integers in the range [1, 127]. Likewise, if the first list is empty, it should evaluate to false for the integers in the second list, and true for all others in that range.

The program will not receive two empty lists as input. If both lists are non-empty, there are no requirements on the result of the output when evaluated with an integer not in the input. (any return value is fine, as is undefined behavior, division by 0, etc).

The following tokens may be used in the expression:

  • Integer literals in decimal, hex, or octal, with optional U and/or LL suffix to denote unsigned / long long ints.
  • A single int variable, which will contain each of the integers from the input in turn. The variable can have any legal variable name.
  • Any of the unary operators + - ! ~
  • Any of the binary operators + - * / % << >> < > <= >= == != & | ^ && || ,
  • The ternary operator ?:
  • Parentheses.
  • Operators that mutate their arguments (++ --, = += -= etc.) are not allowed.
  • Character literals ('a', '_', '\0', etc.) are not allowed.

Some examples of possible outputs:

true            false           sample expression
[1, 3, 5, 7],   [2, 4, 6, 8]    c%2
[5, 6, 10],     [2, 8, 16]      t&~-t
[7, 14, 21],    []              22>x&!(x%7)

(TODO: Specify undefined / implementation-defined behavior details? My test program assumes 32-bit ints / longs, 64-bit long longs, and "nice" two's-complement signed overflow / conversion.)

This challenge is ; your score is determined by the total number of characters in the outputs for these ten randomly-generated inputs: (TODO).

Bonus: Subtract 15 from your score if the output expression evaluates to 1, not just nonzero, for all 'true' inputs.

Sandbox Questions

Welp, turns out my "Round Fractions" question from earlier is pretty much a subset of "Closest fraction". So here's another idea I've been tossing around since the one challenge I answered in C a while back (Area of an ASCII Polygon).

This is still very much a work-in-progress spec, though; some questions I have:

  • I believe this could be tagged as C rather than C++; the only difference I'm aware of is the ternary conditional's precedence, and given that no assignment operators are allowed, it might not make a difference.
  • I'm not sure what tags would go best on this (is it if the output isn't fixed?)
  • I imagine there should probably be some additional constraint to prevent theoretically optimal but impossibly slow brute-force searches.
  • The range [1, 127] is kind of arbitrary; my thought is that it should be able to handle anything in ASCII range + whitespace characters, but not much more than that, so as to make the special cases less restrictive.
  • Would there be a way to spin this off as , if establishing run-time conditions is too arbitrary?

I'm mostly done writing a program to test the output expressions; just need to do a bit more testing.

That's pretty much it; hopefully this is enough to work with for feedback. Thoughts / comments?

\$\endgroup\$
  • \$\begingroup\$ Interesting challenge. I think a time-limited code-challenge is a better fit than code-golf, because there's a lot of complexity with that many operators and golfed code would be hideous. I think the random test cases should be supplemented with some which are designed to favour different operators, so that deciding to leave some out for speed becomes a real trade-off. There's only one integer literal which anyone would want to use in octal, so you could make a special case for 0. If you're going to allow LL in tokens then you really should be explicit about type widths. \$\endgroup\$ – Peter Taylor Nov 26 '15 at 21:01
0
\$\begingroup\$

Typographic Chemistry

Inspired by this: https://xkcd.com/1442/

Task

You must make a program or function that take input a string from STDIN and output the possible allowed reactions (1 point per unique reaction, see also "Score" below)

Rules

A chemical reaction is allowed if all the "legs" of the elements are used, i.e., there are no unpaired "legs". A "leg" is just the end of a curve in the typographic print of the chemical symbol (see the comic and it should be clear). So for example:

Carbon - C - 2 legs

Oxygen - O - 0 legs

Hydrogen - H - 4 legs

Nitrogen - N - 2 legs

Potassium - K - 4 legs

Phosphorus _ P 1 leg

An element can be rotated, reflected but not stretched in any way, so that the only possible bonds are (here I don't know how to rotate the chars, if somebody can help it would be welcome):

$$CH \;\mathrm{(with\;the\;C\;on\;top\;or\;bottom\;rotated\;by\;90\;degrees)}\\CK \;\mathrm{(with\;the\;C\;on\;top\;or\;bottom\;rotated\;by\;90\;degrees\;or\;to\;the\;right\;rotated\;by\;180)}\\ HK\;\mathrm{(on\;top\;of\;each\;other\;or\;on\;the\;side\;rotating\;one\;by\;180)}\\ NN\;\mathrm{(with\;one\;reflected\;has\;two\;legs\;on\;top\;and\;two\;diconnected\;legs\;on\;bottom)}\\ P\;\mathrm{(with\;anything)}\\ O\;\mathrm{doesn't\;bond}$$

These are the only possible elements passed from STDIN. Notice that the difference between H and K is that K can bond also laterally with a C.

Extra Rule

If no reaction is possible, the output should be equal to the input

Score

1 point per reaction. Bonus: X3 the score if you can print the reaction diagramatically, i.e. print the shape of the molecule (like in the comic)

Example

$$Input \rightarrow Output\\ C\,C \rightarrow (C_2)\\ N \, N \rightarrow N \, N\\ C\,N \, N\,P\,P \rightarrow (C N_2 P_2)\\ C\,C\,K \, H\,H\rightarrow (KC_2H_2)\\ C\,H\,O\rightarrow C\,H\,O $$

\$\endgroup\$
  • \$\begingroup\$ Your rules seem to be imposing extra grid-alignment constraints on the letters (e.g. you don't seem to permit the hydrogen crystal from the xkcd). Does that mean that although P can bond with anything except O, the positions in which it can do so are restricted? \$\endgroup\$ – Peter Taylor Nov 24 '15 at 19:05
  • \$\begingroup\$ Hi, I don't want to impose necessarily the extra grid alignment, thanks for noticing it. Yes, P can bond with anything, I added it so that it is easier to have "allowed" reactions. \$\endgroup\$ – Costantino Nov 25 '15 at 15:01
  • \$\begingroup\$ So does that mean e.g. that CP_2 is possible? \$\endgroup\$ – Peter Taylor Nov 25 '15 at 15:12
  • \$\begingroup\$ yes it is, although I have no idea how you could print it. Do you have any good way to state the rules simply and effectively? \$\endgroup\$ – Costantino Nov 25 '15 at 15:39
  • \$\begingroup\$ This is so far from the truth of chemistry that you really need some decent drawings to show what's acceptable. The number of bonds an atom can make is in reality determined by its column in the periodic table: K=1 (except the bond is usually ionic not covalent), H=1, C=4, N=3, P=3 (sometimes 5), O=2. \$\endgroup\$ – Level River St Nov 25 '15 at 23:25
  • \$\begingroup\$ Hi, I have prepared an image, but I can't upload it because I don't have enough reputation. Can you help me? \$\endgroup\$ – Costantino Nov 26 '15 at 16:06
  • \$\begingroup\$ The easiest solution I can see is to remove entirely the list of possible bonds and the bonus and to effectively convert it into a question of whether there exists a graph with the desired degree sequence. IMO that's still an interesting question, and one which hasn't been asked here before. \$\endgroup\$ – Peter Taylor Nov 26 '15 at 21:08
0
\$\begingroup\$

Note: I think the question is fine. I just need some more testcases for it.



You are given the priority order of alleles for a particular trait. For example,

A B
O

means that A and B are equally dominant and O is recessive to both of them. An organism has exactly two alleles, but only the dominant trait(s) is/are expressed. So an organism with gene AO will express only A but an organism with gene AB will express both A and B. An organism with two same alleles will express that allele only.

Each offspring will receive two alleles - one from the mother and the other from the father. So if the initial parents are AB and AO, the offspring formed will be:

AA - 25%
AO - 25%
AB - 25%
BO - 25%

Expressed traits will be

A - 50%
AB - 25%
B - 25%

Offspring of one generation may breed only with a single member of the opposite sex in the same generation during its lifetime. Assume for the sake of this challenge that every male finds a random female in the same generation and has exactly two children - one male and one female. Siblings may interbreed. Note that, except for the first generation, we can ignore the sex of the individuals as their sex chromosomes assort independently of their other characteristics.

Input

  • Priority order of all alleles (may include unnecesary alleles)
  • Genotype of every organism in initial generation
  • Number of generations created
  • Any one allele
  • (Optional) Number of lines of input for priority order (for languages like C++)

Output

  • Probability of the specified allele existing in a randomly selected individual in the specified generation (accurate to three decimal places)

Challenge

  • Once two/three answers are posted, I'll use the same testcases in all of them to see which of them are faulty.
  • After a week (or I could prolong the deadline) I will upload a lengthy test case in a few days. The code that solves it in the fastest time wins.

Sample data (Some simple testcases)

#1

A
B
C
Male(s) - AA
Female(s) - AB
5
C

Output 0

#2

A
B
C
Male(s) - AA
Female(s) - AB
2
A

Output 0.75

#3

A B
C D
Male(s) - AC,BD
Female(s) - AC,BC
1
C

Output 0.125

\$\endgroup\$
  • 1
    \$\begingroup\$ "Once two/three answers are posted, I'll use the same testcases in all of them to see which of them are faulty" You should have a way to verify answers without using other answers. \$\endgroup\$ – FryAmTheEggman Dec 1 '15 at 17:35
  • \$\begingroup\$ @FryAmTheEggman I am abandoning this Q, anyone else is free to post it themselves. \$\endgroup\$ – ghosts_in_the_code Dec 2 '15 at 9:47
0
\$\begingroup\$

Cops and Robbers - Find the Formula

Cops will write a function that takes numerical inputs and produces numerical outputs (note - outputs can be any base and may contain letters). They will post the language, the number of bytes it takes to write the code (up to 128), rounded up to the nearest power of 2, as well as a minimum of 2 test cases. The robbers will try to write a program that takes the same numerical inputs as the test cases and produces identical outputs.

Note - PRNG's, hashing, and other forms of encryption are not allowed.

Scoring

Cops (if safe)

The floor of the product of:

  • 128 divided by the power of two rounded up for the bytes
  • The natural logarithm of the number of test cases

If cracked, -10 points.

Robbers

The floor of the quotient of

  • Half the number rounded up to by the cops
  • The natural logarithm of the number of test cases
\$\endgroup\$
  • \$\begingroup\$ Say I have a function f(x) that returns x when x<2 and 3*x ᴏtherwise. Would the robber's function only have to match the given test cases, or have to match all test cases? \$\endgroup\$ – Conor O'Brien Nov 27 '15 at 3:06
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ The given test cases only. \$\endgroup\$ – Arcturus Nov 27 '15 at 3:16
  • \$\begingroup\$ Is there a maximum of test cases? \$\endgroup\$ – Conor O'Brien Nov 27 '15 at 3:24
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ I'm not sure if there should be. If there were, I'd say maybe 10 or 12. \$\endgroup\$ – Arcturus Nov 27 '15 at 3:25
  • \$\begingroup\$ I think the scoring algorithm might be a bit complex. \$\endgroup\$ – Conor O'Brien Nov 27 '15 at 3:41
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ I want to do something that awards points depending on the number of test cases because that makes it more likely that the robber found the intended solution and is "more" right. \$\endgroup\$ – Arcturus Nov 27 '15 at 5:03
  • 2
    \$\begingroup\$ The cops-and-robbers lesson which everyone should have learnt by now is that built-in crypto functions should be banned because otherwise the cops have an easy time. \$\endgroup\$ – Peter Taylor Nov 27 '15 at 13:49
  • 1
    \$\begingroup\$ ^ That should include hashing and PRNGs. Although it's really hard to rule them out conclusively. My personal goal is still to come up with more CnRs that aren't susceptible to stuff like that in the first place (like my Programming Language Quiz). \$\endgroup\$ – Martin Ender Nov 27 '15 at 14:00
  • \$\begingroup\$ @MartinBüttner Given that I've explicitly disallowed hashing, PRNGs, and encryption, what do you think of this challenge? \$\endgroup\$ – Arcturus Nov 27 '15 at 22:15
  • \$\begingroup\$ @Eridan It's still susceptible to arbitrary base conversions or expmod (just check out any CnR-submission by Dennis to see some examples). People can just throw together a quasi-random program in a golfing-language without having to understand it and just run some numbers through it to generate test cases. \$\endgroup\$ – Martin Ender Nov 27 '15 at 22:36
  • \$\begingroup\$ @MartinBüttner I didn't realize those were bad for CnR challenges (I even mentioned base conversion above). Is there a specific way I could describe methods like those to disallow them? \$\endgroup\$ – Arcturus Nov 27 '15 at 22:50
  • \$\begingroup\$ @Eridan none I can think of. That's why I meant that this is an inherent problem of any CnR that lets participant choose what their program does. In CnRs where the programs need to solve a specific task, this is not such a big issue, because the cops actually need to find a convoluted but working implementation themselves. \$\endgroup\$ – Martin Ender Nov 27 '15 at 23:07
  • \$\begingroup\$ Even with crypto banned, numerical functions make for boring CnR challenges since it's much more likely to be about finding parameters rather than guessing the structure of the code. \$\endgroup\$ – xnor Nov 28 '15 at 9:57
  • 1
    \$\begingroup\$ A problem: Anyone can just write an interpolating polynomial. \$\endgroup\$ – LegionMammal978 Nov 28 '15 at 13:49
0
\$\begingroup\$

Quiddler

Quiddler is a card game where you try to create words from letter cards drawn from a deck. A word is defined as being more than 2 cards in length. Sometimes letters are combined on cards in this game, however that will not be the case in this challenge.

Your mission is to write a program which creates words from the letters read in on standard input. Your dictionary of words is the words file on any standard unix system. You may assume that all strings this file is all lowercase.

Input

The string of letters you can use to create words is read in on standard input. This string will be all lowercase, and will not have any spaces in it.

Valid examples are:

actlj
jactl
ljdkj
jjabc

Invalid are:

jklKLJKKJLKUIU
klj kljklj djkas;

Output

The list of all possible results from said string each string. Remember you can produce multiple words in the same answer.

Examples of valid output include. Please remember that I came up with these off the top of my head, and may not be complete. Input is left aligned and the output is presented as the indented lines. The -> is for your benefit.

tacb  -> 
         cat
         act
         bat
         tab

fivquedrr ->
         five qud
         quid five
         river
         quiver

The order of the solutions output does not need to be in any specific order.

The environment

This program must run in a standard UNIX-like environment. This means that you may use any standard shell (bash, ksh, csh, zsh, fish), and you have access to all the standard tools. This challenge is restricted to the shell scripting languages.

The path to the dictionary file in the environment variable, DICT, the path to the file should not be in any valid solution. Use $DICT as the path to the dictionary. This is included so that you can provide testing instructions for your program.

Winner

The winner is the one with the fewest bytes of code that produces the correct output.

\$\endgroup\$
  • \$\begingroup\$ In the example output, I'm not sure why for the first input the output is newline-separated, but for the second it's space-separated. I also don't understand the second paragraph in the section "The environment". \$\endgroup\$ – Peter Taylor Nov 27 '15 at 21:30
  • \$\begingroup\$ @PeterTaylor In quiddler you can have multiple words per possible solution. I'll add a second example to demo. \$\endgroup\$ – HSchmale Nov 27 '15 at 21:53
  • \$\begingroup\$ So is this basically a variant on Countdown where the dictionary is amplified by including its Cartesian power? \$\endgroup\$ – Peter Taylor Nov 28 '15 at 8:08
  • \$\begingroup\$ @PeterTaylor: Pretty much, except I did not know that existed. Also, for each answer you can only use each answer once. \$\endgroup\$ – HSchmale Nov 28 '15 at 16:43
0
\$\begingroup\$

Ancient Language Translator

<insert a silly story here>

Task:

Write a program that takes an English sentence and translates it into the Ancient Language. You have to implement at least 42 words. For the purpose of this challenge, you do not have to care about special rules such as "(may be shortened to al when used as a prefix, as in albitr)".

Input:

An English sentence.

Output:

A translated version of the input, simply replace the English words with the Ancient ones.

Examples:

To be added.

Scoring:

Suggestions?

\$\endgroup\$
  • 2
    \$\begingroup\$ This might be considered as too broad as there is no specific words to implement. For scoring a code-challenge might work with the score being something like the sum of the length of all words implemented. code-golf might also work. Kind of related challenge. The title is also possibly misleading, so I'd suggest putting "Ancient Language" in quotes \$\endgroup\$ – Downgoat Nov 29 '15 at 16:55
  • \$\begingroup\$ I think this would be uninteresting just because it's just replacement, not actual translation. \$\endgroup\$ – cat Nov 30 '15 at 3:07
  • \$\begingroup\$ @sysreq Translating English into the "Ancient Language" is just replacement as far as I know... \$\endgroup\$ – Stefnotch Nov 30 '15 at 17:24
  • \$\begingroup\$ @Downgoat Oh, ok! So, what words should have to be included? A selection of) the most common words: en.wikipedia.org/wiki/Most_common_words_in_English \$\endgroup\$ – Stefnotch Nov 30 '15 at 17:26
0
\$\begingroup\$

Nested Header List

The goal of this challenge is to complete a list of consecutive nested header numbers when given a start and an end. When given 1.1.1 and 1.1.5 you should generate 1.1.1, 1.1.2, 1.1.3, 1.1.4, 1.1.5

Specific Rules

  1. Your entry must take in a start, end, and multiple optional range parameters. Parameters can be taken form STDIN (or nearest equivalent) or a file.
  2. Your entry may assume valid input
  3. Input will be of the following format:
    1. start and end will be strings of . delimited integers of the same length
    2. start and end will have three segments; (1) set values, (2) iterator, (3) trailing values.
      • The iterator is the first value which differs between start and end.
      • The set values are the values before the iterator. These values never change
      • The trailing values are the values after the iterator. These values iterate up as determined by the range parameter(s). All trailing values will be 1.
    3. range will be a list of integers with a length corresponding to the number of trailing values. When there are no trailing values, range is not specified. The value of range corresponding to each trailing value determines the inclusive upper bound which that entry iterates to.
  4. Output will be to STDOUT (or closest alternative) and will show each value separated by at least one delimiter. Delimiter can by any character or string of characters, but it must be consistent. Output must be sorted correctly

Examples

start = '1.1.5.1', end = '1.1.6.1', range = [5]
Output: 1.1.5.1, 1.1.5.2, 1.1.5.3, 1.1.5.4, 1.1.5.5, 1.1.6.1
                                                  ^
                                                  previous value is iterated
                                                  only when iterating value
                                                  limit set by range


start = '1.1.5.1', end = '1.1.7.1', range = [5]
Output: 1.1.5.1, 1.1.5.2, 1.1.5.3, 1.1.5.4, 1.1.5.5, 1.1.6.1,
        1.1.6.1, 1.1.6.2, 1.1.6.3, 1.1.6.4, 1.1.6.5, 1.1.7.1

start = '1.5.1.1', end = '1.6.1.1', range = [5,2]
Output: 1.5.1.1, 1.5.1.2, 1.5.2.1, 1.5.2.2, 1.5.3.1, 1.5.3.2, 
        1.5.4.1, 1.5.4.2, 1.5.5.1, 1.5.5.2, 1.6.1.1

This is code golf so shortest code by bytes wins.

Bonuses

  1. Allow trailing values to be values other than 1 in end parameter - 12.5% off
  2. Handle incorrect number of values in range parameter - 12.5% off
  3. Handle end less than start by producing list in reverse - 50% off
\$\endgroup\$
0
\$\begingroup\$

Count the Connect Four Positions

Connect Four is a two-player game on a rectangular board. The board is m spaces wide and n spaces tall, and players alternate placing pieces in columns. A placed piece always fills the lowest empty space in a column, and a player may not move in a full column. In the standard game, m=7 and n=6.

The game ends when one player completes a row of four pieces vertically, horizontally, or diagonally, or all m columns are full. The edges of the board do not wrap.

Challenge

Write a program or function to determine the number of distinct, legal m by n Connect Four boards after p plies. (A ply is one move by one player.) A legal position is one reachable from the empty board through a sequence of moves in which no player had already won. (A position in which one player has just won is legal.)

Rules

You may assume that 0<=p<=m*n, m<=8 and n<=8.

As usual, hardcoding is not allowed.

Your code should be at most 1024 bytes in length, and use at most 16 GB of memory.

Related: Determine winner of Connect 4

Test cases

[need to add; include OEIS]

Relevant links:

\$\endgroup\$
0
\$\begingroup\$

Compile from Brainfuck

The professors at Brainfuck University realized their jobs are horrible, because all they do is discuss quantum mechanics using Brainfuck, so they decided to take their programs and compile them to a better language. Because of the randomness of quantum particles, their program needs to be small so it has a smaller chance of being disrupted in the Higgs Field.

Your task is to get a Brainfuck program from any input and output that program transcompiled into another language. Here is an example:

++-->><<

Compiles to the C program:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    unsigned char *cell = calloc(30000, 1);
    unsigned char *cells = cell;
    if (!cell) {
        fprintf(stderr, "Error allocating memory.\n");
        return 1;
    }
        //actual program
        ++*cell;
        ++*cell;
        --*cell;
        --*cell;
        --cell;
        --cell;
        ++cell;
        ++cell;

        free(cells);
        return 0;
}

Score

Your score is the size of your program added to the size of the output.

Bonuses

\$\endgroup\$
  • 3
    \$\begingroup\$ Dupe \$\endgroup\$ – Mego Dec 5 '15 at 9:55

You must log in to answer this question.

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