560
\$\begingroup\$

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".

\$\endgroup\$
0

4331 Answers 4331

1
24 25
26
27 28
145
2
\$\begingroup\$

Coprime Factorization of the Least Common Multiple

Given any (ordered) pair of integers (a, b), it's possible to write their least common multiple1 as a product c · d of two coprime divisors of a and b, respectively. For example, consider the pair (12, 18); the least common multiple of 12 and 18 is 36; 36 can be written as the product 4 · 9; 4 and 9 are coprime; 4 divides 12 and 9 divides 18.

For the purpose of this challenge, we'll call the pair (c, d) a coprime factorization of lcm(a, b), or simply a coprime factorization of (a, b). Note that a pair of integers may have more than one coprime factorization.

Challenge

Write a program or a function that takes a pair of integers and produces a coprime factorization of it.

Input and Output

You may read the input through STDIN, the command line, as function arguments or an equivalent method. You may assume that the input values are representable using your environment's default integer type, however you may not generally assume that their least common multiple is representable using the same type (unless your environment guarantees that.)

You may write the output to STDOUT, return it as the function's result or use an equivalent method. Note that the order of the output matters: the first output value should divide the first input value and the second output value should divide the second input value.

Scoring

This is code-golf. The shortest code, in bytes, wins.

Examples

Below is a list of input pairs and possible corresponding output pairs:

12, 18            4, 9
18, 12            9, 4
7, 13             7, 13
7, 13             -7, -13   (but not -7, 13)
1, 1              1, 1
-1, 1             1, 1
-1, -1            1, 1
30, 105           2, 105
30, 105           6, 35
30, 105           30, 7
10, 10            1, 10
10, 10            -10, -1
2, 6              2, 3
2, -6             1, 6
5, 25             1, 25
0, 8              0, 1
0, 0              0, 1   (but not 0, 0)
4, 1073741825     4, 1073741825   (but not 4, 1 if your LCM overflows to 4)

-1009612890, 633162618     138645, 70351402
140710086, -875522142      15634454, 120231
970683318, 823353894       133299, 91483766
660164274, -511130862      60014934, 85789
1048411386, 10420542       116490154, 1431
982611234, 1017084222      109179026, 139671
725309046, 922185198       99603, 102465022
65472462, -784948626       8991, 87216514
447559002, -857040426      49728778, 117693
-726750882, 708662394      66068262, 118943
133894134, -685199790      18387, 25377770
1563277915, 522665550      312655583, 18022950
873424926, 54855306        97047214, 7533
-1053523350, 347810166     117058150, 47763
855729666, 361179918       95081074, 4509
946303182, 135991350       129951, 15110150
-595150578, 475084962      81729, 52787218
886532526, 145690974       121743, 1798654
511393014, 541933722       70227, 60214858
755325450, 750082410       83925050, 20601

1 For the purpose of this challenge, lcm(n, 0) = lcm(0, n) = 0 for all n, where lcm is the least common multiple.

\$\endgroup\$
2
  • \$\begingroup\$ What's the point of the negative numbers? \$\endgroup\$
    – feersum
    Oct 26, 2014 at 22:59
  • \$\begingroup\$ @feersum Generality, mostly. \$\endgroup\$
    – Ell
    Oct 26, 2014 at 23:17
2
\$\begingroup\$

md5sum Creator

This is my first code golf challenge; critiquing welcome.

Your task is to create a new md5sum function. You need to output to STDOUT the input, a space or a tab character, the md5sum, then a new line. The spec for an md5sum can be found here, thanks to the IETF. For example:

1 c4ca4238a0b923820dcc509a6f75849b
2 c81e728d9d4c2f636f067f89cc14862c
... 
//hashes generated on http://www.md5.cz/
  • You may use existing libraries so long as you are not directly calling an md5sum function from within that library.
  • Output is not case sensitive (A is the same as a when it comes to an md5sum).
  • Your program/function will take in a string, and output the md5sum as a string
  • No downloading data from the Internet.
  • Code Golf, so the shortest answer wins!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ what should the output file be called? isn't it easier to use STDOUT? and should the character separating the number and its md5 be a tab or a space or the correct number of spaces? \$\endgroup\$
    – user16402
    May 30, 2014 at 6:40
  • \$\begingroup\$ Is the output case-sensitive? \$\endgroup\$ May 30, 2014 at 12:49
  • \$\begingroup\$ @professorfish Edited. Thanks for the input. \$\endgroup\$ May 30, 2014 at 16:12
  • \$\begingroup\$ MD5 takes a sequence of octets, so how should I pack my integers? Should I pack 4 bytes in network byte order? Or little-endian? Or format each integer in ASCII? Or UTF-16? \$\endgroup\$
    – kernigh
    Jun 19, 2014 at 20:53
  • \$\begingroup\$ In that case, do you need to update your sample output? All online md5 generators I've used treat input as ASCII. \$\endgroup\$ Jun 19, 2014 at 22:07
  • \$\begingroup\$ Done @PeterTaylor. Thanks \$\endgroup\$ Jun 19, 2014 at 22:41
  • \$\begingroup\$ I don't see any problems with this now. \$\endgroup\$
    – user10766
    Nov 3, 2014 at 21:46
  • 1
    \$\begingroup\$ I'd prefer if you included the relevant parts of the MD5 spec in the answer. I don't feel like reading an entire RFC to compete in the challenge, and challenges should generally be self-contained anyway. \$\endgroup\$ Nov 3, 2014 at 22:57
2
\$\begingroup\$

Convert Images to NetPBM format

NetPBM format is perhaps the most important image format in the history of computer graphics. Critics have called it "the format of our time." What is so revolutionary about NetPBM, you may ask? It has the unparalleled ability to store images as text files!

You have been tasked with converting images from their ancient, "lossy" format to the lossless full-color NetPBM PPM (P3) format.

The Specifics

You have a few choices as to which file format you wish to process into a PPM file.

  • JPEG
  • GIF
  • TIFF
  • PNG

Choose wisely.

The file created by your program should adhere to the P3 specifications. Here are the parts of a P3 file listed out:

  1. The characters "P3" followed by whitespace.
  2. An ASCII decimal number (like "4") which represents the image width in pixels, followed by whitespace.
  3. An ASCII decimal number (like "3") which represents the image height in pixels, followed by whitespace.
  4. An ASCII decimal number (like "255") which is to represent maximum pixel intensity. It can be an integer from 1 to 65535, inclusive. It is followed by whitespace.
  5. After this there is one line per row of pixels:
    1. Each row is separated by whitespace
    2. Each row contains one triplet for each pixel in that row, with the pixels separated by whitespace
    3. Each pixel consists of three ASCII decimal numbers separated by whitespace. These numbers represent the RGB values of that pixel, in that order. Each number must be an integer from 0-MAX, inclusive, where MAX is the number listed earlier.

Here is an example of PPM format ripped from Wikipedia:

P3
3 2
255
255   0   0     0 255   0     0   0 255
255 255   0   255 255 255     0   0   0

This is code golf: the shortest submission wins. Standard code golf rules apply.

\$\endgroup\$
2
  • \$\begingroup\$ I believe the actual spec limits line lengths to something like 76 characters, although certainly the GIMP will load NetPBM files which don't respect that. You might want to add a note about how much of the chosen input spec people must implement: I think that all four of those have some options which might not be widely used. \$\endgroup\$ Nov 8, 2014 at 20:33
  • \$\begingroup\$ Image compression challenge: render in 0x0 1-bit greyscale! \$\endgroup\$
    – feersum
    Nov 8, 2014 at 21:21
2
\$\begingroup\$

Simple Square Packing

This is meant to be a straightforward golfing puzzle. Hopefully this hasn't been done before.

Your challenge is to figure out how large of a square is needed to fit some other squares inside of it. You input will be a list of the sizes of other squares, and the output will be the size of the needed square.

To make this problem easier (solvable) the squares will not rotate and will have integer sizes.

Example

Let's say that you have squares of sizes 2,3,3,3,4,5. This is how they can pack optimally:

555554444
555554444
555554444
555554444
55555.333
333333333
333333333
33333322.
......22.

In this case, they all fit in a size 9 square, so your program should output a 9.

Test Cases

To be added.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ This in an NP-complete problem, so solutions will be exponential time in general. You should decide what degree of brute-forcing in solutions you're OK with. \$\endgroup\$
    – xnor
    Nov 14, 2014 at 10:09
2
\$\begingroup\$

Code Yourself a DFA

or

In this challenge, your task is to implement a deterministic finite automaton (DFA for short) that recognizes the following regular language L. The alphabet of L is x,1,2,3, and it is the set difference of (1x*|2(xx)*|3(xxx)*)* and (x|1|2|3)*1x*1x*1(x|1|2|3)*. Intuitively, the strings in the language L consist of zero or more "blocks" of the form 1xx...x, 2(xx)(xx)...(xx) or 3(xxx)(xxx)...(xxx), and three blocks of the first kind cannot occur consecutively.

The API

Your program will take two arguments from STDIN, separated by a space: a letter from the alphabet x,1,2,3, and a string that represents the current state of the DFA. The program should then write to STDOUT either A or R, a space, and a string that represents the new state of the DFA. The first letter indicates whether the new state is accepting (A) or rejecting (R). After that, the program should quit.

For example, suppose that we are checking the input string 2xx, and that the start state of my DFA is start. Then, my program is given the input 2 start, and it answers with A 2block and quits, so the next state is 2block, which is accepting. Next, the program is given x 2block, and it answers with R 2block', which is rejecting. Finally, the program is given x 2block', and it answers with A 2block. Since this state is accepting, the input is accepted (as it should be, since it is an element of L).

Rules and Scoring

Your answer should include a program and the name of its start state (which should be accepting in this case, since the empty string is in L). The score of your answer is the byte count of your program, plus three times the number of states in the DFA; the lowest score wins. A control program (written in Python 3) that checks the validity of your submission and its state count can be found here (TODO). See the README file for instructions. Finally, some additional rules:

  • Your program should be completely deterministic, and cannot read any input from any external source, other than the STDIN arguments listed above.
  • A state of the DFA is either accepting or rejecting. If your program claims that some state is accepting, and later that it's rejecting, the control program will disqualify it.
  • The states of your DFA must be strings of printable non-whitespace ASCII characters, and all such strings are valid potential states. The actual state set of your DFA is the set of states reachable from the given start state.
  • Every state of your DFA must support a transition by every letter in the input alphabet.

Sandbox questions

I'd like some comments on the scoring of this challenge, and the language L. I have tried to choose them so that there could be meaningful trade-offs between state count and byte count. Specifically, if L is too simple or the penalty on program length is too low, the best tactic is to just compress the minimal DFA. Conversely, if L is too complicated, I fear that no-one will have the energy to write a DFA for it by hand.

\$\endgroup\$
2
  • \$\begingroup\$ It's not clear to me why you talk about states being final or not final. The standard terminology, which is the one used by the background material you link to, is accepting vs non-accepting. I also find the description of the desired FSM hard to read: code markup (obtained with backticks) would be clearer than italics, and I'd find regex's | notation clearer than + for alternation. \$\endgroup\$ Nov 27, 2014 at 18:08
  • \$\begingroup\$ @PeterTaylor: Good comments, I edited them in. \$\endgroup\$
    – Zgarb
    Nov 27, 2014 at 19:19
2
\$\begingroup\$

Balda AI in under 8192 bytes

Balda is a Russian word game which bears some similarities to Scrabble. Your task is to write an AI for an English version of it. However, because you can place any letters, the game would be easy if you knew all the words in the English language - hence, your entire program, including any word list, must be 8192 bytes or less.

The Game

The game consists of a square of 5x5 cells; each cell can be empty or hold one letter. At the start, a randomly selected 5-letter word is placed into the middle row. Example (please excuse my terrible ASCII art skills):

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
| P | L | A | N | E |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

There are two players. Each turn, a player must place one letter into an empty cell - any letter may be used. They must then compose a word which contains this letter. Words consist of horizontally and vertically adjacent letters; they can be backwards, upside-down, in a circle or any other shape. The player then receives one point per letter in this word. Words must be singular common nouns and at least 3 letters long. No word may be used twice in one game.

The game ends when there are no empty cells left, and the player with the most points wins.

Part of an example game:

+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   | T | N |   |   | < TURN 1: Player 1 writes PLAN; Player 2 writes PLANT. Score 4:5
+---+---+---+---+---+
| P | L | A | N | E |
+---+---+---+---+---+
|   |   |   | T | T | < TURN 2: Player 1 writes PLANET; Player 2 writes TENT. 10:9
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Control, Input, Output

Your program will be invoked once per turn and at the end of the game, with the following arguments, where game_status is 0 if the game is still in progress, 1 if it ended because no spaces are left, 2 if it ended because player 1 failed to provide a word, 3 for player 2, 4 if player 1 gave an invalid word and 5 for player 2:

your_player_number player1_score player2_score game_status

The previously used words and the game board (separated by a line with a *) will be provided on standard input, in the following format (blank cells are underscores):

PLANE
PLAN
PLANT
PLANET
TENT
*
_____
_TN__
PLANE
___TT
_____

It has 30 seconds to output a move in the following format. In the example, the N of PLANT is in row 2 and column 3:

ROW_NUMBER COLUMN_NUMBER LETTER_PLACED WORD_LETTER1_ROW WORD_LETTER1_COLUMN WORD_LETTER2_ROW WORD_LETTER2_COLUMN ..........

Player 2's second move in the example would be written as follows. 4 5 3 5 3 4 4 4 are the co-ordinates of each of the word's letters, in order.

4 4 T 4 5 3 5 3 4 4 4

Rules

  • Your program must be 8192 bytes or shorter at the start of the tournament. However, it may create any files and keep them between tournament games - hence, it can learn from its opponents.
  • Your program must have a name and version numbering.
  • Please provide instructions on how to run your program on Windows 8.1.
  • Libraries which provide word lists or are designed for word puzzles are not allowed.
  • Libraries created after this challenge was posted are not allowed.
  • Standard loopholes are forbidden. No web access.
  • Existing compression algorithms such as gzip are allowed, and you may use libraries to decompress them, but the decompression must be done in your program.
  • You must write a complete program, not a function.
  • If the control program detects that no words can be written, the game ends and the player with the most points wins.
  • If words can be written, but a player cannot submit a valid word in 30 seconds, they lose regardless of their score.
  • This is the official word list.
  • This is the same list, but only with five-letter words (i.e. those that can be the starting word)
\$\endgroup\$
9
  • \$\begingroup\$ 2k is nowhere near enough for the word list. I was very proud when I managed to write a word game for the Java4k game competition. I did it with a game design which meant that I only needed to include 4-letter words, and even so I had to chop some words to fit the word list and a bit of game logic in to 4kB (heavily compressed - uncompressed it was more like 10kB). \$\endgroup\$ Sep 4, 2014 at 22:07
  • \$\begingroup\$ @PeterTaylor Let's make it 8k then? \$\endgroup\$
    – user16402
    Sep 5, 2014 at 7:29
  • \$\begingroup\$ Maybe you should provide the word list in your computer (in txt) ? So my program just access it. Well, I have 30 seconds, sounds enough to buffer and read it. (cititation needed) \$\endgroup\$
    – Realdeo
    Sep 5, 2014 at 13:34
  • \$\begingroup\$ @Realdeo What do you mean? Your word list has to be part of your program. \$\endgroup\$
    – user16402
    Sep 5, 2014 at 17:54
  • \$\begingroup\$ What i"m trying to say that instead of having the word list in the program, and make the program huge, just have the wordList.txt avaliable for the program to access. \$\endgroup\$
    – Realdeo
    Sep 6, 2014 at 3:13
  • \$\begingroup\$ @Realdeo No, the wordList.txt may not be available for the program to access, it must be in your program. That's part of the challenge. \$\endgroup\$
    – user16402
    Sep 6, 2014 at 7:28
  • \$\begingroup\$ Can the input also list the words that have been used so far? In most boards, there will be words present that haven't been "used" (tenant or net in your example). \$\endgroup\$
    – Geobits
    Oct 6, 2014 at 19:08
  • \$\begingroup\$ "...or if a player cannot submit a valid word ..." Does this mean that if I'm in the lead at any point, I can just not submit a word? The game will end and I'll have more points. \$\endgroup\$
    – Geobits
    Oct 6, 2014 at 19:23
  • 1
    \$\begingroup\$ @Geobits 1. I forgot that. I'll add that in. 2. That's a big loophole. I'll change it to "if you can't submit a valid word, but there is one possible, you lose" and "if no words are possible, the game ends normally" \$\endgroup\$
    – user16402
    Oct 6, 2014 at 20:47
2
\$\begingroup\$

Rise and Shine - Posted

\$\endgroup\$
18
  • \$\begingroup\$ @trichoplax I forgot to add that part to the question. Fixed. \$\endgroup\$
    – globby
    Jan 21, 2015 at 2:03
  • \$\begingroup\$ If you want results to be valid over a range of 10,000 years, what influences do you want to be taken into account? Tectonic movements? Changes in the length of the day and year? Axial precession? \$\endgroup\$ Jan 21, 2015 at 2:08
  • \$\begingroup\$ @trichoplax Changed the date range. You may assume for the sake of the challenge that all of those are present day conditions. \$\endgroup\$
    – globby
    Jan 21, 2015 at 2:11
  • \$\begingroup\$ @trichoplax down to the second. \$\endgroup\$
    – globby
    Jan 21, 2015 at 2:18
  • \$\begingroup\$ I'd recommend being explicit in the question about what effects are not to be taken into account, to make sure there is an objective winner. Your shorter date range means other factors make less of a difference, but if measuring to the second some of them may still affect the correct answer. \$\endgroup\$ Jan 21, 2015 at 3:27
  • \$\begingroup\$ It might even be easiest to implement a non-golfed example solution so there is a well defined answer for every input - any disputes can simply be compared to the reference implementation. \$\endgroup\$ Jan 21, 2015 at 3:28
  • \$\begingroup\$ @trichoplax Added a resource that sums it up, would that suffice? \$\endgroup\$
    – globby
    Jan 21, 2015 at 4:40
  • \$\begingroup\$ If you state that the result given by the linked algorithm is the required result for this challenge then that would be unambiguous. Looking good. \$\endgroup\$ Jan 21, 2015 at 5:18
  • \$\begingroup\$ @trichoplax Alrighty. \$\endgroup\$
    – globby
    Jan 21, 2015 at 5:22
  • \$\begingroup\$ @MartinBüttner they are already excluded :) \$\endgroup\$
    – globby
    Jan 21, 2015 at 19:08
  • \$\begingroup\$ The time zone bonus should be closer to 0.085. Have you seen a time zone map lately? Plus, taking DST into account? I've been thinking about making that a challenge for a while, but I think even for a dedicated challenge, this is too much to be fun to golf. \$\endgroup\$ Jan 22, 2015 at 20:40
  • \$\begingroup\$ @MartinBüttner good point. Removing the bonus entirely, better for a separate challenge, which I will leave up to you. \$\endgroup\$
    – globby
    Jan 23, 2015 at 5:18
  • \$\begingroup\$ Did you intend to remove the resource? Ephimerides are a seriously hard problem, so this question shouldn't be posted without some kind of exhaustive reference for validation (and ideally a good suite of test cases). \$\endgroup\$ Jan 25, 2015 at 23:16
  • \$\begingroup\$ @PeterTaylor Added some test cases, does that suffice? \$\endgroup\$
    – globby
    Jan 26, 2015 at 6:02
  • \$\begingroup\$ The test cases were to supplement the reference implementation / formula, not to replace it. And are you sure about your test cases? I find it extremely odd that all of them have timezone offsets of hh:60. \$\endgroup\$ Jan 26, 2015 at 9:58
2
\$\begingroup\$

Count inversions

Given a list/array/vector of 0's and 1's, count the number of inversions, which are instances of a 0 coming later than a 1. In other words, an inversion is a pair of indices (i,j) with i<j that correspond to list elements L[i]==0 and L[j]==1.

This equals the minimum number of times on needs to swap adjacent elements to sort the list.

Test cases: TODO


Questions for Sandbox: Has this really not been asked before? I searched and didn't find it. Also, is this challenge too easy? It could be made a bit harder by having list elements be general integers, or requiring generating lists with a given inversion count instead.

\$\endgroup\$
1
  • \$\begingroup\$ I've got a 25-char GS answer for the "general integers" case without really trying. I'll leave it to you to judge whether that's too easy. Generating lists of a given length with a given inversion count is a more interesting problem to analyse, although I suspect that the analysis turns up a relatively simple solution which everyone can copy/port. \$\endgroup\$ Jan 29, 2015 at 11:38
2
\$\begingroup\$

Find the direction of the Bicycle (code challenge)

There is a trace of a bicycle in the snow, but you can only see the two lines of the two wheels. Your goal is to find out which direction the bycicle did go. Inspiration from George Hart

Task

Write a program that takes a pixel image as input and calculates which direction the bicycle was riding. The output consist of the direction (left or right) as well as and a percentage (0-100) of how sure you are.

You can assume that the front wheel and the backwheel have a distance of 100px and that the frontwheel has a path that is piecewise differentiable. (That means that the path of the frontwheel is smooth, and does only make a finite amount of sudden turns.) The path of the front wheel is marked black, while the one of the back wheel is marked red. You can expect all inputs to be non ambiguous. Both paths end in the right and left sides of the images.

Hint

The curve of the backwheel is called tractrix (but often we refer to one special curve as tractrix).

Score

Your score is the sum of the precentages of the paths you got right minus the sum of the percentages of those which you got wrong.

Examples inputs (more needed for an actual challenge)

Of course the challenge images will be without plotting grid.

EDIT: new two coloured images enter image description here enter image description here

--META:

Please comment on what is unclear / should be added or changed, and vote for the ideas how to make the challenge easier:

  1. Do not make it easier, both lines black
  2. Make it easier by making front wheel and back wheel different colours (unknown which one is which)
  3. Make it even easier by e.g. marking the back wheel path always red and the front wheel path always black
\$\endgroup\$
11
  • \$\begingroup\$ 1. Both paths black \$\endgroup\$
    – flawr
    Feb 2, 2015 at 21:41
  • \$\begingroup\$ 2. Both paths different colours, colours arbitrary each time \$\endgroup\$
    – flawr
    Feb 2, 2015 at 21:41
  • 6
    \$\begingroup\$ 3. Both paths different colours, same (known) colours each time \$\endgroup\$
    – flawr
    Feb 2, 2015 at 21:41
  • \$\begingroup\$ The basic task is unclear. I think that the two lines are meant to be the loci of two points which are separated by a constant amount (i.e. it's a "spherical cow in a vacuum" type of simulation), but surely that and the rather loose continuity constraint on one of them don't suffice to fully determine the evolution of the loci? An input could have both paths discontinuous and satisfy the stated constraints. I would like to see an explicit physical model or system of differential equations. \$\endgroup\$ Feb 3, 2015 at 14:11
  • \$\begingroup\$ Then it's also unclear what the output format is. What should the arrow look like? How is the confidence interval communicated to your test framework? What counts as "getting it right" vs "getting it wrong"? And finally, I think that you should either replace "there might be ambiguous inputs" with a guarantee not to include any or say that in the case of ambiguous inputs any answer is wrong. Otherwise it's a guessing game, not a fair challenge. \$\endgroup\$ Feb 3, 2015 at 14:18
  • \$\begingroup\$ Ok I will change that and do not allow ambiguous examples. I wanted the output to consist of the image input again that was altered: The program should draw an arrow on one of the lines (on an arbitrary place along the line) that represents the direction of the wheel of that path in which the wheel was going. As far as differential equations goes: I have no experience in that field. For simulation the bicycle I did following: f(t) is the position of the frontwheel at time t, similarly r(t) for the backwheel. I defined f as a function/spline and then calculated r. \$\endgroup\$
    – flawr
    Feb 4, 2015 at 9:47
  • \$\begingroup\$ Let h be the time step size. Then I calculated the distance vector of the two wheels: d(t+h):= f(t+h)-r(t) and then calculated the new position of the rear wheel: r(t+h) = f(t+h) - L/|d(t+h)| * d(t+h), where L is the distance between back and front wheel. For small enough h I thought this simulation was accurate enough. With given starting points and give f I thin r is uniquely determined. If you know how to write this as a differential equation I'd be happy to include it, but I am not sure how many of the people here can actually use them. \$\endgroup\$
    – flawr
    Feb 4, 2015 at 9:55
  • \$\begingroup\$ Doesn't sound much like a bicycle, but then the kind of curves you show would be impossible with a real bicycle in the snow. It would be good to edit the question with the description of your track generation model. And I don't think you've answered any of the three questions in my second comment. \$\endgroup\$ Feb 4, 2015 at 12:14
  • \$\begingroup\$ I am sorry, I forgot to answer those. What makes you think they are impossible? As long as you manage to keep balance those tracks seem perfectly possible to me. The arrow does not need a special shape, it just must be clear for the viewer. As an arrow can only point in two different directions parallel to a line it should be obvious from the output wheter it is the right or wrong direction. The output of the confidence is also up to the participant, I thought they could directly write it to the image so we only have one output item that can easily be displayed. \$\endgroup\$
    – flawr
    Feb 4, 2015 at 12:23
  • \$\begingroup\$ Have you ever ridden a bicycle in snow? You have to turn very carefully. As to the arrow, I can think of several nasty corner cases. The point at which I'm most confident could be where the path leaves the image, in which case only one pixel of the arrow would be inside the image bounds. The arrow could start at a point where the derivative is discontinuous, or where the path crosses back over itself, in which case there would be more than one correct answer. Given that the arrow is the same colour as one of the tracks, it could be unclear where it starts. \$\endgroup\$ Feb 4, 2015 at 12:37
  • \$\begingroup\$ Obviously we are talking about an idealized bicycle (since most bicycles also cannot drive backwards and the touching points of front and back wheel are not constant)... I will now alter the challenge so that both tracks end on the right and left side of the visible frame. This way the possible answers are right or left as a direction of travel. \$\endgroup\$
    – flawr
    Feb 4, 2015 at 13:04
2
\$\begingroup\$

Implement the Maximize Affirmed Majorities voting system

There are many different voting systems in existence. Different voting systems have different mathematical properties, which serve to describe the "positive features" of that system. Here is an informative list of these properties and a table of compliance.

In this challenge, you will implement a voting procedure called "Maximized Affirmed Majorities", a method created with the sole purpose of meeting as many mathematical requirements as possible. You will write the shortest (in bytes) program (or named function) possible to determine the winner of an election using this method.

The Procedure

Each vote is a self-consistent ordering of the candidates. It is possible for a vote to include ties between multiple candidates, like A>B=C>D=E=F. An example of a vote which violates these rules is `A>B>A.

Step 1: Create a tiebreaker

I know it's a little odd that creating a tiebreaker is the first step, but hopefully you never have to use a random tiebreaker for a full-scale election. A tiebreaker is a strict ordering of candidates. Let T(X,Y) be the tiebreak function, return true iff the tiebreaker ranks X above Y.

  1. Choose a uniformly random ballot, and adopt the preferences of that ballot.
  2. If the ordering is incomplete (like A>B=C>D=E=F), then choose a second uniformly random ballot (without replacement) and use that ballot to tie-break any unresolved orderings.
  3. Repeat step 2 until the tiebreaker is complete. If you run out of ballots to create a tiebreaker with, randomly resolve the remainder of the list.

Step 2: Create a list of majorities

This list takes the form of ordered pairs of candidates.

  1. For each pair of candidates (X,Y), let V(X,Y) be the number of voters who ranked X strictly over Y.
    1. If V(X,Y) > V(Y,X), then add (X,Y) to the list.
    2. If V(X,Y) < V(Y,X), then add (Y,X) to the list.

Step 3: Sort of the list in order of descending importance

A majority (X,Y) is ranked above (Z,W) if any of the following hold:

  • V(X,Y) > V(Z,W); more support of X>Y
  • V(X,Y) == V(Z,W) and V(W,Z) > V(Y,X); same support, but less opposition
  • V(X,Y) == V(Z,W) and V(W,Z) == V(Y,X) and T(W,Y) == True
  • V(X,Y) == V(Z,W) and V(W,Z) == V(Y,X) and Y == W and T(X,Z) == True

Step 4: Affirm majorities in order of preference

Let F(X,Y) be a function that returns whether or not X finished over Y in the final list. It is initialized to False for every pair of candidates.

  1. Iterate through the list of majorities, in order.
    1. If F(X,Y) == False and F(Y,X) == False, then Affirm(X,Y).

The function Affirm(X,Y) is defined as follows:

  1. Set F(X,Y) to true
  2. For each candidate A where X != A != Y
    1. If F(A,X) == True and F(A,Y) == False, then Affirm(A,Y)
    2. if F(Y,A) == True and F(X,A) == False, then Affirm(X,A)

Step 5: Determine the top candidate(s)

A candidate X is considered a top candidate if there exists no candidate Y such that F(Y,X) == True. That is, candidate X doesn't explicitly lose to anybody.

Step 6: Tiebreak to determine the winner

Out of the list of top candidates, the winner is the candidate who appears highest on the tiebreaker list.

Input

Input will be handled similarly to this online implementation I found, which also provides the complete ordering of candidates instead of just the winner.

Each line of input will contain a ballot, which is a list of space-separated candidates in descending order of preference. Optionally, two candidates separated by an = sign are considered equal in preference. A number followed by a colon at the start of a line denotes a multiple number of ballots.

[line] = ([number]: )?[candidate]( (= )?[candidate])*
[candidate] = alphanumeric string, not starting with a digit
[number] = a positive integer of course

Any candidates no ranked on a ballot are appended to the end and set equal to each other. You may optionally assume 1 or 2 newlines at the end of input.

Example input:

Bob Sally Test4
Bob Sally Test4
1: Bob = Sally Test4 = Sam
4: Test4 Bob

is the exact same as

Bob Sally Test4 Sam
Bob Sally Test4 Sam
Bob = Sally Test4 = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam
Test4 Bob Sally = Sam

Expected Output

Test4

Sandbox Notes

Any comments?

\$\endgroup\$
1
  • \$\begingroup\$ Interesting. Maybe some more testcases? \$\endgroup\$
    – Ypnypn
    Feb 10, 2015 at 21:16
2
\$\begingroup\$

Conway's Golf of Life- Brains vs Brawn Edition

2 programs play a competitive version of the game of life, where each program can set as many cells in the initial condidtions as there are characters in the other's source code.

The 2-player game of life is played on an infinite grid of cells. Each cell holds a value a, b, or 0. On each turn, the following rules are applied simultaneously to each cell:

  • A non-zero cell with 2 or three non-zero neighbours keeps its value
  • A non-zero cell with less than 2 or more than 3 non-zero neighbours is set to 0
  • A zero cell with 3 non-zero neighbours is set to the value of the majority of its non-zero neighbours
  • A zero cell with more or less than three non-zero neighbours keeps its value

The two player programs A and B have nA and nB characters respectively, and nA <= nB.

The grid is initialized to 0 everywhere

First, program A is called with the command line argument nB. It must output 2 * nB integers to stdout, which will be interpreted as a list L of nB ordered pairs. For each ordered pair in L, the cell at the coordinates in that pair will be set to 'a'

Second, program B is called with the command line argument nA followed by the 2*nB integers output by program B. It must output 2*nA integers to stdout, which will be interpreted as a list L of nA ordered pairs. For each ordered pair in L, the cell at the coordinates in that pair will be set to 'b'

Note: The coordinates output by programs must fit within 16 bit signed integers. However, calculation of steps will take place on an effectively infinite grid.

Once both programs have run, the grid is run through 10,000 turns. After this, if more cells are set to a, program A wins. Otherwise, program B wins.

The challenge is to create a program that has the best win/loss ratio against all other submissions.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Might be worth requiring the output of the program to be distinct cells as a precaution against a highly golfed program which manages to output something with only 2 chars in an attempt to win by default. \$\endgroup\$ Feb 9, 2015 at 17:44
  • \$\begingroup\$ Also, I think you should probably run two games for each pair of bots, because if one bot is allowed to place all its cell first, I'm sure that will give a bias in some direction. Also, is the grid infinite? \$\endgroup\$ Feb 9, 2015 at 17:50
  • \$\begingroup\$ Also related but potentially abandoned proposal. \$\endgroup\$ Feb 9, 2015 at 17:52
  • \$\begingroup\$ By infinite you mean the programs could choose silly coordinates like (1.000.000, 100.000.000)? \$\endgroup\$
    – user16991
    Feb 9, 2015 at 17:56
  • \$\begingroup\$ @kuroineko Yes. And that the patterns can move 10,000 cells in any direction without hitting a wall or wrapping around to the other side of a finite domain. \$\endgroup\$ Feb 9, 2015 at 17:58
  • 1
    \$\begingroup\$ well in that case I would try to spawn walker launchers all over the place, with a huge random starting position. \$\endgroup\$
    – user16991
    Feb 9, 2015 at 18:01
  • \$\begingroup\$ The computation you will need to do is O(step_number^3) so 10000 steps means around Const*10^12 calculation which is undoable. I would advise 100 steps. The two player's cells probably wouldn't interact anyway if they don't do it in 100 steps. One other thing: I would still add a coordinate-limit like -2^30<x,y<2^30 as you probably don't want to do arithmetic with arbitrarily big integers. You should set the output requirement clear as the golfed codes' outputs might include extra spaces, linebreaks etc. if not stated otherwise. Otherwise I think it's a great challenge. \$\endgroup\$
    – randomra
    Feb 14, 2015 at 18:10
  • \$\begingroup\$ Randomra: look up the algorithm "HashLife" which I would use to implement the control program. Calculating game of life steps can almost always be reduced to O(log(n)) - a pretty stunning result! I like the idea of limiting coordinates- I think I'll limit them to signed 32 bit integers, so contestants don't have to worry about handling inputs that break their language \$\endgroup\$ Feb 15, 2015 at 17:14
  • \$\begingroup\$ @QuadmasterXLII HashLife dissolves my concern. If you use the @[name] syntax at the start of your comment the person will be notified of your response and will notice it unlike I did. :) \$\endgroup\$
    – randomra
    Feb 22, 2015 at 18:50
2
\$\begingroup\$

Print All Provable Statements

This might be a stretch to make into a challenge, but I think it can be done. The challenge will most likely be code-golf. I'm thinking about using 2D geometry as the basis. I will have to create a notation system for geometrical and logical statements that is golf-friendly.

The general idea is that you start off with a list of known facts. Then, the program uses the laws of logical deduction to work through every possible deduction that can be made, and then add these new facts back into the pool of knowledge. Given enough time, every possible provable statement will show up in your list. Of course, you will run out of memory first, and that's okay.


Probably the best axioms to use are Tarski's Axioms. From the wiki article:

Tarski's system has the unusual property that all sentences can be written in universal-existential form, a special case of the prenex normal form. This form has all universal quantifiers preceding any existential quantifiers, so that all sentences can be recast in the form

∀u∀v...∃a∃b...

This fact allowed Tarski to prove that Euclidean geometry is decidable: there exists an algorithm which can determine the truth or falsity of any sentence. Tarski's axiomatization is also complete. This does not contradict Gödel's first incompleteness theorem, because Tarski's theory lacks the expressive power needed to interpret Robinson arithmetic (Franzén 2005, pp. 25–26).

There are three (?) fundamental relations:

  • x=y Equality - x and y refer to the same objects
  • Bxyz Betweenness - The point z is between x and z, lying on line segment xz. It is possible for x=y or y=z.
  • wx~yz Congruence - The length of line segment wx is equal to the length of line segment yz.

There are three congruence axioms:

  • xy~yx Reflexivity of Congruence
  • xy~zz → x=y Identity of Congruence
  • xy~zu & xy~vw → zu~wz Transitivity of Congruence

There are also betweenness axioms:

  • Bxyx → x=y Identity of betweenness
  • Bxuz & Byvz → ∃a(Buay & Bvax) Axiom of Pasch
  • Axiom Schema of Continuity: I'll need some help translating this.
  • ∃a∃b∃c(!Babc & !Bbca & !Bcab) Lower Dimension

And some more:

  • (xu~xv & yu~yv & zu~zv & u!=v) → (Bxyz | Byzx | Bzxy) Upper Dimension
  • (Bxuv & Byux & x!=u) → ∃a∃b(Bxya & Bxzb & Bavb) Equivalent to Euclid's Axiom
  • (x!=y & Bxyz & Bfgh & xy~fg & yz~gh & xu~fi & yu~gi) → zu~hi Five Point
  • ∃z(Bxyz & yz~ab) Segment Construction

Some notes on mathematical notation.

I think it would be a good idea to convert all math notation to ASCII. I've done with with congruence already, but I need replacements for → ∃ ∀. I might replace a!=b with !a=b for consistency, or I could go all-out and put everything in Polish notation.


If I wanted fancier axioms

Here is an alternative set of axioms, which are based on Hilbert's geometry axioms but excluding the ones that talk about planes. Some of them are copied verbatim from that website and may be unnecessarily fluffy. I would have to re-write all of them to be in formal notation.

  1. Given two distinct points A and B, then there exists exactly one line a that contains both points.
  2. Given a line a, there exist at least two distinct points A,B which lie on the line and three distinct points X,Y,Z which are not on the line.
  3. If a point B lies between points A and C, then points A,B,C are three distinct points on a line, and B also lies between C and C.
  4. For two distinct points A and C, there exists at least one distinct point B such that C lies between A and B.
  5. Of any three points on a line, there exists no more than one that lies between the other two.
  6. Let A, B, C be three points that do not lie on a line and let a be a line which does not meet any of the points A, B, C. If the line a passes through a point of the segment AB, it also passes through a point of the segment AC, or through a point of the segment BC.
  7. If A, B are two points on a line a, and A' is a point on the same or on another line a' then it is always possible to find a point B' on a given side of the line a' through A' such that the segment AB is congruent or equal to the segment A'B'. In symbols AB = A'B'.
  8. If a segment A'B' and a segment A"B", are congruent to the same segment AB, then the segment A'B' is also congruent to the segment A"B", or briefly, if two segments are congruent to a third one they are congruent to each other.
  9. On the line a let AB and BC be two segments which except for B have no point in common. Furthermore, on the same or on another line a' let A'B' and B'C' be two segments which except for B' also have no point in common. In the case, if AB = A'B' and BC = B'C' then AC = A'C'.
  10. Let angle(h,k) be an angle and a' a line and let a definite side of a' be given. Let h' be a ray on the line a' that emanates from the point O'. Then there exists one and only one ray k' such that the angle(h,k) is congruent or equal to the angle(h',k') and at the same time all interior point of the angle(h',k') lie on the given side of a'. Symbolically angle(h,k) = angle(h',k'). Every angle is congruent to itself, i.e., angle(h,k) = angle(h,k) is always true.
  11. If for two triangles ABC and A'B'C' the congruences AB = A'B', AC = A'C', angleBAC = angleB'A'C' hold, then the congruence angleABC = angleA'B'C' is also satisfied.
  12. Let a be any line and A a point not on it. Then there is at most one line in the plane, determined by a and A, that passes through A and does not intersect a.
  13. If AB and CD are any segments, then there exists a number n such that n segments CD constructed contiguously from A, along the ray from A through B, will pass beyond the point B.
  14. An extension of a set of points on a line with its order and congruence relations that would preserve the relations existing among the original elements as well as the fundamental properties of line order and congruence that follow from Axioms I-III, and from V,1 is impossible.
\$\endgroup\$
2
\$\begingroup\$

Rendezvous palace

Introduction

This comes from a well-liked question on the Math SE by RobAu and a more specific follow-up to that by Danikov.

There is a palace which is a grid of n × n rooms, which we will index using two coordinates 0 ≤ x,y < n. The rooms are organized in a torus topology, i.e. with wrap-around at the edges. So the room to the right of (n-1,3) is (0,3) again, and likewise for the y direction.

Two robots are placed into this grid, and their objective is to rendezvous. But the problem is that these only can can keep track of relative changes in position and orientation. So each robot has its own local coordinate system, where its initial position is called (0,0), but these two coordinate systems relate to one another in any of 4n2 possible ways, accounting for 4 possible relative rotations and n × n relative shifts. Each of these relations has equal probability.

The palace has no doors. The robots can move around the palace by teleportation. They move in a synchronized way, teleporting at exactly the same instant. To meet they either have to be in the same room at the same time, or to swap places during teleportation.

Challenge

Your task is to write a program for these robots, trying to minimize the expected time till rendezvous. The same program will be executed for both robots, and the robots have no way to distinguish which one is which. So we'll be executing two copies of your code in parallel.

Input

The only input is n, the size of the palace. In addition to that, the code has access to a random number generator, and the random numbers from one instance are assumed to be independent from those in the other instance. No other input or communication between the instances is allowed.

Output

The output of your code should be an infinite sequence of coordinate pairs, (x,y), indicating the target room for the next teleportation. The coordinates are relative to where the robot started, not relative to where he currently is located. Giving the same output repeatedly means you are staying put in a given room.

Framework

You are asked to evaluate your code yourself. Write or copy a framework which will randomly choose relative starting positions, execute two instances of your code in parallel, detect a successful rendezvous and report the time to rendezvous. Run that code a number of times, and compute the average and standard deviation of the time to rendezvous. See the section below for ready-to-copy code.

Submission

Your answer must include the code which constitutes the program for one robot. It must also include the average time to rendezvous and its standard deviation for the following setups:

  1. at least 1,000,000 runs for n = 2
  2. at least 100,000 runs for n = 64
  3. at least 10,000 runs for n = 256

You don't have to paste your framework by default, but be willing to provide it upon request. An explanation of what your code is doing and why you wrote it that way might bring upvotes.

Scoring

The title of best answer will go to the code with the minimal expected time to rendezvous for n = 64. I'll re-evaluate the top contenders myself, to make sure you included genuine results. The closer two competitors are, the more often I'll run their code to establish a reliable expected value from the average. This is an open-ended contest, so the title may be re-awarded when a better answer comes along.

Example frameworks

C++

You can use the following fixture if you like.

#include <random>
#include <iostream>
#include <iomanip>
#include <cmath>

constexpr int n = 64;
const int orientations[4][4] = {
  {1, 0, 0, 1},
  {0, 1, n - 1, 0},
  {n - 1, 0, 0, n - 1},
  {0, n - 1, 1, 0}
};

std::default_random_engine randEngine((std::random_device())());
std::uniform_int_distribution<int> randDist{0, n - 1};
std::uniform_int_distribution<int> randDist4{0, 3};
int rand() { return randDist(randEngine); }

typedef std::pair<int, int> pos_t;

class Robot {
public:
  pos_t next() { return {rand(), rand()}; }
};

class Transform {
  int dx, dy, ori;
public:
  Transform() : dx{rand()}, dy{rand()}, ori{randDist4(randEngine)} { }
  pos_t operator()(const pos_t& in) const {
    int x = in.first, y = in.second;
    const int *o = orientations[ori];
    return { (o[0] * x + o[1] * y + dx) % n, (o[2] * x + o[3] * y + dy) % n };
  }
};

unsigned long run() {
  Transform tr;
  pos_t p1{0, 0}, p2{0, 0};
  p2 = tr(p2);
  Robot r1, r2;
  unsigned long t = 0;
  while (p1 != p2) {
    ++t;
    pos_t q1 = r1.next();
    pos_t q2 = tr(r2.next());
    if (p1 == q2 && p2 == q1) break;
    p1 = q1;
    p2 = q2;
  }
  // std::cout << std::setw(8) << t << "\n";
  return t;
}

int main(int argc, char** argv) {
  double sum = 0, sumSq = 0;
  int report = 10;
  for (int i = 1; ; ++i) {
    double r = run();
    sum += r;
    sumSq += r*r;
    if (i == report) {
      double avg = sum / i;
      double var = (sumSq - sum*avg) / (i - 1);
      double sd = std::sqrt(var);
      std::cout << std::setw(8) << i << " runs: Expected: "
                << std::fixed << std::setprecision(2) << avg
                << ", SD: "
                << std::fixed << std::setprecision(2) << sd
                << std::endl;
      report *= 10;
    }
  }
}

In a submission you'd just paste the next function. A possible statistical report for the above could read:

n = 2: Expected 2.40, SD 2.68 in 10,000,000 runs
n = 64: Expected 4105.08, SD 4104.22 in 10,000,000 runs
n = 256: Expected 64911.36, SD: 65204.72 in 10,000 runs

Python, …

To be extended for other languages. Feel free to donate your own framework if you feel like it.

\$\endgroup\$
2
\$\begingroup\$

A Continuously Running KOTH, or "An MMO with all AIs"

This was an idea discussed in chat, I'm throwing a sandbox post together because I thought it would be really fun to do.

The main idea is that the KOTH is hosted an an external website, where the competitions is continuously running. When a person submits an answer, that player's pixels (or whatever they're called) will be spawned in the game world. Over time, build a larger army of themselves.

Basically, it's an MMO with all AIs.

As of right now, I don't have the capability to host a website for this. I think someone (Optimizer?) said that they had a website. Regardless, we probably don't have to worry about that until we figure out what the rules are going to be.

Some ideas

  • The world is a large array of randomly generated pixels. Every submission has a unique color. As pixels travel around, they can encounter other pixels of the same color, which then activate and join them.
  • A more Minecraft-y options involve more detailed resource gathering / crafting. Con: the complexity can get pretty hard for contestants.
  • A space theme can involve a randomly generated galaxy, which players can travel across. They can then colonize planets and build an empire. (Maybe resembling EVE Online?)
  • Some recommendations for ideas are Clash of Clans and Globulation 2, although I've never played either.
  • Maybe each player controls an adventure in a super-simplified Dwarf Fortress-style world.

You are free to edit this post to add ideas.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Sounds really interesting! But I think the backend of this can get really complicated... \$\endgroup\$
    – rorlork
    Apr 6, 2015 at 22:16
  • \$\begingroup\$ Would it be possible for a player to die out completely, so that the answer is permanently out of the competition? Is there some way that this could be prevented so every answer is represented, even if only by a very small number of pixels/creatures/... \$\endgroup\$ Apr 7, 2015 at 21:33
  • \$\begingroup\$ Respawning with a single individual would be one way. \$\endgroup\$ Apr 7, 2015 at 21:35
  • \$\begingroup\$ Alternatively each individual could have resilience inversely proportional to the number of individuals the player currently controls. So as the individuals reduce in number they get stronger, preventing the final individual from ever being killed. \$\endgroup\$ Apr 7, 2015 at 21:36
  • \$\begingroup\$ @trichoplax None of the specifics have really been thought through yet, but I think it would make sense to say that, upon death, players lose resources, but can't go below what they started the game with. \$\endgroup\$
    – PhiNotPi
    Apr 7, 2015 at 21:37
  • \$\begingroup\$ How about a text-based map, similar to the ones used in Roguelikes? Players build walls with their player color (| and =), with doors (+), tripwires (>-----<), mines (*), and guards (&). Weapons and armor ([ and ]) modify stats, like +2 to attack, potions (!) give buffs/debuffs, and various miscellaneous items (") are found randomly. Maybe a shop, where you use collected gold ($)? \$\endgroup\$ Apr 8, 2015 at 1:30
  • \$\begingroup\$ How would this be able to have a winning condition? \$\endgroup\$ Apr 14, 2015 at 9:50
  • \$\begingroup\$ Bump. Now that there's a KOTH server, you may wish to visit this idea with more attention. \$\endgroup\$
    – mbomb007
    Nov 3, 2015 at 15:43
2
\$\begingroup\$

Roguelike to Text Adventure Converter

Note: this challenge is a popularity contest for autogenerated interactive fiction. As such, the best way of judging answers is by playing them! It would threrefore be best for solutions to provide a link to a playable version online. Failing that a 'walkthrough'-style excerpt is fine, but not as fun.

Meta-comment: As you can see, I've changed this from a code golf challenge to a more creative popularity contest. Comments welcome!

Background

Roguelikes are a type of RPG characterized by by procedural level generation, turn-based gameplay, tile-based graphics and permadeath. Levels typically consisted of rooms connected by corridors. Early roguelikes, including Rogue itself, would use ASCII characters to represent the top-down view of each level.

Text adventures are a type of adventure game where the interface is text-only: the player uses text input to control the game and the game state is relayed back via text output. Like roguelikes, layouts typically consisted of interconnected rooms, with movement controlled either by specifying the room name or by giving a compass direction.

This challenge involves writing a program to automatically convert an ASCII representation of a roguelike level into a playable text adventure. The format of supported input levels is given below, as are some minimum features that must be supported by the output game. Beyond that, there is scope for as much or as little creativity you desire!

Input maps

The input of the program is an ASCII representation of a roguelike level, passed in via STDIN, command-line argument, function argument or in a file. Here is a small example:

        --------                
        |..=...+#######                                                                          
        |......|      #                                                                          
        --+-----    --+-------                                                                   
         ##         |...//...|                                                                   
       ###  ########+........|                                                                   
 ------+----+-      -----+----                                                                   
 |..%........|           #                                                                       
 |......!....|   ---     #                                                                       
 |..@........+###+.+######                                                                       
 |...........|   ---                                                                            
 -------------                                                                                   

A level consists of the following elements:

  • Rooms: these are size 1x1 or greater rectangular enclosures surrounded by walls and doors. The north and south walls are represented by -, as are the corners. The west and east walls are represented by |. Doors, which can appear instead of a wall (but not in a corner) are represented by +. The map above has four rooms.

  • Corridors: these are connected (and potentially winding) paths of #s leading from a door in one room to a door in another. The 'direction' of a corridor is defined by which walls it connects to. A corridor that links the north wall of one room to the south wall of another is going N-S, while one that links a north wall to a east wall is going NW-SE. Each room has at least one corridor leading out of it and at most one corridor per compass direction. Corridors that don't correspond to a valid direction (e.g. linking a north wall to a north wall) aren't permitted. Note that the relative layout of the rooms is irrelevant, only which walls the corridors connect to. The bottom-left room in the map above has three corridors: one going N-S, one NE-SW and one E-W.

  • Room content: empty spaces inside rooms are represented by ., while initial room objects are represented by !, %, / and =. These traditionallty correspond to potions, food, wands and rings, but may be called anything you want in your version. There may be multiple objects starting in one room, including of the same type. In the map above, the bottom-left room contains one potion and one food, while the top-right room contains two wands. Note that your program may implement other types of object beyond the ones that appear in the starting map (for example, the contents of a chest).

  • Starting position: one of the spaces in one of the rooms, represented by @, is the starting position of the playing character. In the map above, this is in the bottom-left room.

  • Void: the space between rooms, represented by spaces, is not part of the playing area.

Output games

The output of the program is an interactive game, taking input from STDIN and printing output on STDOUT, that is based on the input map. At the very least, the game should support the following commands:

  • LOOK (also executed whenever a player enters a room and at the start of the game). At the very least this should describe the directions of the doors and the content of the room, though it can do more. For example: "You are in a small room. You can go N, NW or W. The room contains 2 potions and no tea."
  • N/NW/W/SW/S/SE/E/NE. Moves to the appropriate room if possible (and outputs its description as above). Should indicate an error if there is no path in that direction.
  • INV. At the very least this should describe which objects the player is carrying. The player may optionally start with objects. For example: "You are carrying a ring, a potion and a used handkerchief."
  • GET [object]. Picks up one instance of the object from the room outputs some confirmation. Indicates an error if there isn't such an object in the room (or there is some sensible reason why the player can't pick the object up).
  • DROP [object]. Drops one instance of the object into the room and outputs some confirmation. Indicates an error if the player doesn't have the object (or there is some sensible reason why they can't drop it). There is no requirement to have a limit on the number of objects in a room (as there would be in the roguelike original).
  • USE [object]. Uses one instance of the object, possibly consuming it. The effect of using objects is entirely up to the solver!

Case-sensitivity is up to the solver, as is the grammatical correctness of the output. You may include aliases for the above commands if you wish.

Note that the game is allowed (and encouraged!) to support other commands, as well as other types of game elements (for example, creatures that move from room to room). The game need not have a well-defined ending, though it is welcome to. The setting need not be typical for a roguelike, either: a library, spaceship or ant colony are just as valid settings as a dungeon. Be creative!

Example

Here is a sample output from a hypothetical game based on the small map above (actual programs should use the larger map provided below). As mentioned above, it would be best if you could supply an interactive link so users can actually try out the game for real!

You are in a large, white room. You can go N, NE or E. The room contains a potion and a snack.
> INV
You are carrying nothing.
> GET potion
OK.
> INV
You are carrying a potion.
> N
You are in a medium-sized, green room. You can go SE or S. The room contains a ring.
> DROP potion
OK.
> LOOK
You are in a medium-sized, green room. You can go SE or S. The room contains a ring and a potion.
> DROP potion
You don't have a potion!
> GET potion
OK.
> USE potion
Zap! Your surroundings become a blur...
You are in a large, white room. You can go N, NE or E. The room contains a snack.

Scoring

This is a popularity contest, so highest vote tally wins.

Large map

Here is a larger map for use as the default for your online script (or for any walkthrough).

TODO: add larger map.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Congratulations on posting the 1000th answer to the sandbox! :) \$\endgroup\$ Apr 18, 2015 at 17:45
  • \$\begingroup\$ (Including deleted ones, of course.) \$\endgroup\$ Apr 18, 2015 at 17:45
  • 1
    \$\begingroup\$ This may indeed be a bit too much to be an enjoyable golf, but I'm not sure what you could really do about it. It's still a nice task. One thing you might want to make explicit somewhere is how the enumerations in LOOK and INV should be formatted ("a" for 1, numbers for >1, correct plurals, and multiple types separated by commas, except for and "and" before the last one, and no Oxford comma). \$\endgroup\$ Apr 19, 2015 at 2:03
  • \$\begingroup\$ I may park this here for a bit, while I think of ways either to simplify it enough to make it enjoyably golfable or change the purpose of the challenge to something else. \$\endgroup\$
    – Uri Granta
    Apr 19, 2015 at 6:10
  • \$\begingroup\$ Also, I'll add more test maps before I post this. \$\endgroup\$
    – Uri Granta
    Apr 19, 2015 at 6:11
  • \$\begingroup\$ I'd probably have great fun doing this one, but I probably wouldn't golf it too seriously unless unless a similar language (I use C#, so Java/C#/Maybe C++/Some VB or other) was posted by another user for me to compete directly with \$\endgroup\$ Apr 19, 2015 at 12:40
  • \$\begingroup\$ One possibility is allow leeway for creativity (e.g. customized item descriptions and behaviors, different room descriptions) and then turn this into a popularity contest based on the quality of the interactive fiction. \$\endgroup\$
    – Uri Granta
    Apr 19, 2015 at 15:02
  • \$\begingroup\$ Any comments on the new approach? \$\endgroup\$
    – Uri Granta
    May 1, 2015 at 10:51
2
\$\begingroup\$

Draw a trie diagram

Tries (pronounced "trees") are a type of data structure also known as a prefix tree. The prefix tree stores a list of strings by taking advantage of prefixes that are shared between multiple strings.

(Too lazy to type a better description now)

In this challenge, you will create a very simple diagram of a trie.

Input:

baby,bad,bank,box,dad,dance

Output:

b   d
a  oa
bdnxdn
y k  c
     e
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Should we be able to reconstruct the list based solely on the diagram? For example, does the diagram change if one of the words is a prefix (such as ban or bo)? \$\endgroup\$
    – Geobits
    Apr 29, 2015 at 17:40
  • \$\begingroup\$ @Geobits Don't worry, I was already thinking of that possibility. I don't know the answer yet. \$\endgroup\$
    – PhiNotPi
    Apr 29, 2015 at 18:35
2
\$\begingroup\$

Matchstick Equations

Your task in this challenge is to analyize a given "Matchstick Equation" like this one...

enter image description here

... and to find out whether it can be turned into a valid equation by rearranging the matches. If so, you are to output the least number of moves to do so and the resulting equation.

Input

The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. It is an equation that represents a matchstick arrangement and can be described using the following EBNF:

input = term, "=", term ;
term = number | (term, ("+" | "-"), term) ;
number = "0" | (numeralExceptZero , {numeral}) ;
numeralExceptZero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
numeral = "0" | numeralExceptZero ;

An example for a valid input would be 3+6-201=0+0+8.

Task

Consider the following illustration where each matchstick has a number assigned:

matchstick positions

We now map each input symbol to the corresponding matchstick positions as follows:

1 ↦ 4,5
2 ↦ 2,3,5,6,8
3 ↦ 3,4,5,6,8
4 ↦ 1,4,5,8
5 ↦ 1,3,4,6,8
6 ↦ 1,2,3,4,6,8
7 ↦ 4,5,6
8 ↦ 1,2,3,4,5,6,8
9 ↦ 1,3,4,5,6,8
- ↦ 8
+ ↦ 8,10
= ↦ 7,9

Each input formula can be turned into a matchstick arrangement. For example, the equation "45+6=92" becomes

enter image description here

where unused matchsticks are greyed out. Your task is to find out the least number of matchsticks that have to be rearranged in order to make the equation valid.

Output

We distinguish between three possible cases:

  • If the input is not valid (i.e. it doesn't satisfy the above EBNF), output whatever you want.
  • Otherwise, if there are ways to turn the equation into a valid one by rearranging the matchsticks, you have to output both the minimum number of rearrangements and the corresponding equation. Just as the input, the outputted equation must also satisfy the given EBNF. In the above example, the correct output would be 1 and 46+6=52. If there are multiple possibilities for the resulting equation, output any of them.
  • Otherwise (so if the input is valid but there is no way to make the equation true), you have to output -1.

Details

  • You are not allowed to remove or to add matches. That means, if the input is built of n matchsticks, the output must also consist of exactly n matchsticks.
  • "Empty" matchstick-blocks are only allowed at the end and the beginning of an equation, not in the middle. So, for example, turning 7-1=6 into 7 =6-1 by simply removing -1 from the left side and adding it on the right side with just 3 matchstick rearrangements is not allowed.

Examples

Input: 1+1=3Output: 1 and 1+1=2

Input: 15+6=21Output: 0 and 15+6=21

Input: 1=7Output: -1

Input: 950-250=750Output: 2 and 990-240=750

Input: 1-2=9Output: 1 and 1+2=3

Input: 20 + 3=04Output: anything

Winner

This is , so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

\$\endgroup\$
1
  • \$\begingroup\$ Can I adopt this abandoned proposal? \$\endgroup\$
    – user58826
    Jun 9, 2017 at 12:31
2
\$\begingroup\$

Formatting a Lisp-like Syntax

POSTED

\$\endgroup\$
2
\$\begingroup\$

From A to Zilch

Zilch, Farkle, Greed, Dice 10000: The game goes by many names, and many rules. Your goal is to make a program that can play them all optimally. The base rules goes as follows:

  1. At the beginning of your turn, you have 6 available dice
  2. At the beginning of each roll, you either choose to bank or continue.
  3. If you choose to bank, then you receive the total number of points you have accumulated and your turn is over.
  4. Roll all available dice
  5. If you didn't roll any combinations, you get 0 points for your entire turn, and your turn is over
  6. You must take one or more distinct combinations from your available dice and score them.
  7. If you have no available dice left over, you are able to use all 6 dice again.
  8. Go back to step #2

Your goal is to write a function or program that accepts 3 parameters:

  1. The number of points you currently have
  2. The number of dice you have left
  3. A list of (Combination, Point) pairs that define what combinations give points

and then returns a Truthy value if you should continue, otherwise a Falsy value.

Combinations are passed as a list of integers that represent the required digits for that combination.

For example, if I named my function foo, then a call to my function might look like:

foo(100, 5, [([1],100), ([5],50), ([1,1,2],1000)])

This would mean that I have 100 points so far, 5 dice left, and there are 3 possible combinations:

  1. Rolling a 1 would give me 100 points
  2. Rolling a 5 would give me 50 points
  3. Rolling 2 1s and a 2 would give me 1000 points.

Considering I have 5 dice, and it is quite likely for me to roll a 1 or a 5, I should definitely return a Truthy value. Also, note that in the above example, rolling 11235 would give me a maximum of '112'=>1000 + '5'=>50 = 1050 points. Each die can only be included in one combination.

\$\endgroup\$
2
  • \$\begingroup\$ Why wouldn't 11255 give 50 more points than 11235? \$\endgroup\$
    – feersum
    Jun 1, 2015 at 4:28
  • \$\begingroup\$ By maximum I meant that of all of the different combinations to be made with 11235, the ones I gave give the biggest score. I could instead score 2 1s and 1 5 if I wanted. \$\endgroup\$ Jun 1, 2015 at 4:36
2
\$\begingroup\$

Pirates!

Introduction

Arrr mateys!

All hands on deck! Tharr be a ship o' other pirates comin' starboard up t' us on t' starboard! Man t' six pounders! We'll show these guys what we're made of!

...

What? They have t' exact same ship, and t' exact same six pounders as us? That don't matter, we've got better cannon strategy! As long as we reinforce points o' our ship that they fire upon, and fire upon unreinforced parts o' their ship, we're aye t' win! Now, where's that techno thingamabob that said what t' do...?"

Game Description

In this King of the Hill challenge, you write a program to command a pirate crew in a naval war. The other pirate crews are controlled by other players' programs. By carefully choosing where and when to fire, you can defeat the other pirate crews and claim the golden treasure -- the green checkmark of legend.

A battle occurs between two ships. Each ship is mounted with 7 cannons in a row, labelled 1 to 7. Each cannon is directly opposite to the cannon on the other side. Ships all start with 0 damage. If a ship reaches 10 damage, it sinks, and the crew of the other ship win the battle. If both ships sink at the same time, the battle is a draw.

Each battle consists of several turns. On each turn your crew can do any of the following actions:

L:n

Load a cannonball into cannon n. All the cannons start with cannonballs in them, and naturally firing a cannon without a cannonball doesn't do anything.

You can only load one cannonball into a cannon at a time.

R:n

Reinforce a cannon n. Reinforcements will nullify a single attack on that cannon. However, reinforcements are but a transient defence -- they will wear off two turns after they have been applied.

[Todo: Clarification on "two turns"]

F:n

Fire a cannon n, which will hit cannon n on the opposing side. If the cannon is not reinforced, the opposing ship's damage will increase by 1. If the cannon is reinforced, the ship will not take damage, but the reinforcement will be destroyed.

Input Description

The controller will call your program from the command line like this:

<command> <history> <enemy_history> <damage> <your_damage>

where:

  • command is the command needed to run your program. For instance, if your program's source code was in the file arrr.rb, the command is ruby arrr.rb.
  • history is a comma separated list of moves that you have made. For instance, L:1,F:1,L:2,F:2 would mean that you loaded and fired cannon 1, and loaded and fired cannon 2.
  • enemy_history is a comma separated list of moves the enemy has made.
  • damage is your ship's damage (from 0 to 9, since 10 means you've sunk)
  • enemy_damage is the enemy ship's damage

Output Description

Output to STDOUT in the form:

A:N

where A is either L, R, or F, and N is an integer from 1 to 7. This indicates the move that you want the pirates to do.

[Todo: The rest of the spec. I'm tired and I'm posting it here to save it. Will come back some time to finish it. Maybe. Honestly I'm not too fond of the idea but it might have some potential.]

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Your specification was very well written until the Game Description; please consider rewriting the whole thing in Pirate. \$\endgroup\$ Jun 2, 2015 at 21:45
  • 2
    \$\begingroup\$ @FarazMasroor I'll consider it. I want to be careful that I don't go overboard on the pirate speech though since I don't want to make the spec difficult to read. \$\endgroup\$
    – absinthe
    Jun 2, 2015 at 22:05
  • \$\begingroup\$ Haha how about adding a translation at the bottom. \$\endgroup\$ Jun 2, 2015 at 22:08
  • \$\begingroup\$ >Implying Pirate is hard to read but English isn't \$\endgroup\$ Jun 2, 2015 at 22:14
2
\$\begingroup\$

Chinese Checkers

I'm considering writing a challenge that will have people write Chinese Checkers players.

Image courtesy of Wikipedia

Image courtesy of Wikipedia

The game is quite simple: In clockwise turns, players try to move their 'pegs' across the board. They may only move one peg each turn. Valid moves are either moving to an adjacent empty space, or hopping over any number of pegs (friend or foe). These moves cannot be combined. The game is won when somebody has all their pegs in the triangle opposite of where they started.

I will write a controller, that will match up all players against each other in a sufficiently large number of matches. Each match, there will be points for the first, second and third place. Winner is the one with the most points.

Players must have a time limit on each move. This limit will be checked by the controller, and penalties will be applied accordingly. There will also be a limit on total number of moves, to prevent my poor laptop from calculating Chinese Checkers until the heat death of the universe because some idiot decided that random walks would be the way to go.

Since I've never written a controller before, I'd first like to see whether you guys are interested at all in this challenge. Furthermore, which language is generally preferred for these kind of challenges: Java or C++?

\$\endgroup\$
6
  • \$\begingroup\$ Sounds like it could be good. You'll certainly get more participation if the controller is in Java. Ideally you'd also provide a wrapper that allows communication via STDIN/STDOUT, such that any language can participate. \$\endgroup\$ Jun 8, 2015 at 10:32
  • \$\begingroup\$ @MartinBüttner Thanks for the feedback! How should I do that? Ask people to upload their binaries? Or compile everything on my laptop, and limit the languages to compilers I can easily obtain with apt-get? \$\endgroup\$
    – Sanchises
    Jun 8, 2015 at 10:55
  • \$\begingroup\$ The latter. You'll usually want to compile things yourself. \$\endgroup\$ Jun 8, 2015 at 10:55
  • 1
    \$\begingroup\$ You should keep in mind that Chinese Checkers AI programs already exist, and much of the challenge may be adapting them to fit the time constraints, special rules, etc. \$\endgroup\$
    – lirtosiast
    Jun 8, 2015 at 20:50
  • \$\begingroup\$ @ThomasKwa I think (hope?) that for these kind of games, there is no 'best' AI (yet), so it all depends on what heuristics you choose to implement with what parameters. What do you think? \$\endgroup\$
    – Sanchises
    Jun 10, 2015 at 13:04
  • \$\begingroup\$ Although our members do impressive things, I'm not sure that there will be multiple people skilled enough to write their own state-of-the-art Chinese Checkers AI. One thing you may be able to do is have an extremely tight time constraint for each move (in the single-digit ms), because that may be a niche that mainstream AIs haven't filled yet. Don't trust me though, because I know nothing about board game AIs. \$\endgroup\$
    – lirtosiast
    Jun 10, 2015 at 15:17
2
\$\begingroup\$

Captcha cops-and-robbers

Cops develop a captcha algorithm in minimum bytes. Robbers tries to implement a recognizer that recognizes 90 of 100 generated captchas.

\$\endgroup\$
8
  • \$\begingroup\$ I'm sure there will need to be more details, but that seems to summarise what would be needed already so +1 \$\endgroup\$ Jun 9, 2015 at 18:15
  • \$\begingroup\$ @trichoplax, I'll edit into a fully fledged question if the idea gains some support. The main problem that the captcha needs to be solvable by humans, which is a bit subjective. \$\endgroup\$
    – Vi.
    Jun 9, 2015 at 19:12
  • \$\begingroup\$ Yes, I guess you'd need a population of unwitting humans for testing \$\endgroup\$ Jun 9, 2015 at 19:38
  • \$\begingroup\$ @trichoplax, I and other users can test and vouch for validity of posts. \$\endgroup\$
    – Vi.
    Jun 9, 2015 at 21:15
  • 1
    \$\begingroup\$ I guess it's the borderline cases that would be harder to judge. If 95% of humans agree on the solution it's OK. If only 50% of humans agree on any one solution then it's probably not OK. But what if 75% of us agree on a given solution? Does it count as a valid cop? \$\endgroup\$ Jun 9, 2015 at 21:47
  • 1
    \$\begingroup\$ @trichoplax, Maybe it needs some online service that that users can test in more or less controlled way? \$\endgroup\$
    – Vi.
    Jun 10, 2015 at 0:35
  • \$\begingroup\$ I think some companies use humans completing captchas as a way of determining what the "correct" human answers should be. We don't have a large pool of humans we can force to complete captchas though. \$\endgroup\$ Jun 10, 2015 at 0:48
  • \$\begingroup\$ I'd like to see this work if there's another way of verifying what is readable to a human. If nothing better comes up you can simply say that you as the question poster will be the designated subjective human. So the challenge should go ahead one way or another. \$\endgroup\$ Jun 10, 2015 at 0:49
2
\$\begingroup\$

Merging Words

Input

Two strings, and two numbers: "hlwl", "elo_ord!", 1 2

These may be function parameters, STDIN or language equivalents.

Output

The second string merged into the first string. The numbers specify how many characters to add when merging.

This is what happens:

h  l  w  l        //notice there is only 1 char per group (first number)
 el o_ or d!      //2 chars per group here (second number)
-------------
hello_world!

More formal-ish procedure:

  • start with the first string
  • Remove the first n chars from the first string and append it to r, where n is the first numerical input and r is the output string
  • Remove the first k chars from the second string and append it to r, where k is the second numerical input
  • Repeat the last 2 steps until both the first and the second string are empty. You may assume that first_string.length / second_string.length == n / k

Test Cases

input: aaaa bbbb 1 1
output: abababab

input: abcd iiiiiiii 1 2
output: aiibiiciidii

input: chmeeo aln 2 1
output: chameleon

input: emblem ezzent 3 3
output: embezzlement

This is code-golf, so shortest code wins!

\$\endgroup\$
4
  • \$\begingroup\$ Does the order of the input parameters matter? Can be input be formatted as something parsable (e.g., "aaaa" "bbbb" 1 1)? \$\endgroup\$
    – Dennis
    Jun 23, 2015 at 4:47
  • \$\begingroup\$ @Dennis The order does matter - start with the first string, and the input can be pretty much anything - I'll clarify that. \$\endgroup\$ Jun 23, 2015 at 11:20
  • 3
    \$\begingroup\$ FWIW this is 4 characters plus a couple for stack manipulation in certain golfing languages. \$\endgroup\$ Jun 23, 2015 at 13:29
  • 1
    \$\begingroup\$ What I meant was if the input could be read as "hlwl" 1 "elo_ord!" 2 or 1 "hlwl" 2 "elo_ord!" or even 1 "hlwl" "elo_ord!" 2, for example. \$\endgroup\$
    – Dennis
    Jun 23, 2015 at 14:28
2
\$\begingroup\$

Can you lose from this chess position?

Introduction

You are an arbiter who supervises a very large number of chess tournaments. Thus, you frequently rule on whether a player who runs out of time may claim a draw based on Article 6.9 of the FIDE Laws of Chess:

[...] If a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves.

In order to be able to perform your job more efficiently, you decide to create a computer program that determines whether it is possible for a player to be checkmated from a given position.

Regulations

The input will be a position with White to move, with at least one legal move available. You may assume that in the initial position, neither player will retain castling rights and no en passant capture will be available. Additionally, you may assume that the existence of en passant is irrelevant to the correct output. Your program must determine whether, starting from the input position, there exists any sequence of legal moves that ends in Black checkmating White's king.

Either a program utilizing standard input and output, or a function accepting a string and returning a number is acceptable.

Input will be given in FEN notation, but excluding the last 4 tokens – only the locations of the pieces on the board are described.

The program shall output 1 if it is possible for white to be checkmated, or 0 if it is not.

Restrictions

  • Your source code must fit inside a post on this site.
  • If the program exceeds 1 minute of thinking about a position, it is equivalent to an incorrect output.

The winner is the first competitor to submit a correct program. A program shall be considered correct if no one provides an input that causes the program to fail to produce correct output in time for three days after the program is posted.

Examples

Input

kb6/8/8/8/8/8/8/KB6

Output

1

Input

1kb5/8/8/8/8/8/8/KB6

Output

0

Input

3k4/8/1p1p1p1p/pPpPpPpP/P1P1P1P1/8/8/3K4

Output

0

---------------------------

Feedback

Suggestions for improvement are welcome. I would most like to have some input on the victory condition. Is it too difficult to achieve? Should I score it on a fixed set of positions instead?

\$\endgroup\$
3
  • 4
    \$\begingroup\$ The three day rule is a bad one. If an answer is incorrect, it's incorrect, and the possibility that no-one paid it much attention in the first 72 hours after posting shouldn't change that. \$\endgroup\$ Sep 19, 2014 at 19:45
  • \$\begingroup\$ This is interesting. Here's two slightly tricky test cases: 8/8/p1p1p1pk/P1P1P1q1/5P1K/6B1/8/5b2 and 7k/2PPRPRP/p3P1PP/8/8/8/P7/K7. \$\endgroup\$
    – Lopsy
    Sep 20, 2014 at 15:58
  • \$\begingroup\$ Hmm so maybe there should be a new rule that you are losing again, if someone provides a counterexample to your program at any date? @Lopsy nice example requiring a bishop promotion :) \$\endgroup\$
    – feersum
    Sep 20, 2014 at 16:18
2
\$\begingroup\$

Am I offering a bite that's more than people are willing to chew?


Truth Table Solver

Goal

This code golf challenge is to display a rule that is valid for a given truth table.

Input

The input into the program is a boolean array, though you may choose how this is formatted (array, string, etc.) Each value in the array is true or false (or 1 or 0 or any other boolean pair). The index of the value represents the truth table inputs and the value itself is the result of applying the unknown rule to these inputs.

For the truth table inputs, A is the least significant bit of the index. B is the second-least significant bit, and so on. The number of indices in the table determines the number of inputs: log2(n).

For example:

index c b a value
  0   0 0 0   0
  1   0 0 1   0
  2   0 1 0   0
  3   0 1 1   1
  4   1 0 0   1
  5   1 0 1   1
  6   1 1 0   1
  7   1 1 1   1

Output

Given this truth table, your program must determine the rule is, in this case, (a&b)|c and output it. The variables may be in any order and printing redundant brackets is fine.

Requirements

Rules may include any of the following operations NOT (~), AND (&), OR (|), XOR (^) and identify priority with brackets.

Test Cases

Here are some test cases, expressed as a string of boolean results:

0100              (~a)&b
00011111          (a&b)|c
01101000          a^b^c
0000011101110111  (a|b)&(c|d)
0100010100010000  a&(((~b)|c)^d)

Scoring

The shortest code after two weeks wins the contest.

\$\endgroup\$
5
  • \$\begingroup\$ The requirement to "support the operation... XOR" doesn't make sense to me. The obvious way to get the shortest program is to output in DNF, and XOR is unnecessary for that. The requirement to "identify priority with brackets" seems to contradict the example output ~a&b. \$\endgroup\$ Jul 3, 2015 at 6:24
  • \$\begingroup\$ What happens if a boolean array can be expressed in multiple ways? Do we output all possible options or just one? \$\endgroup\$
    – Beta Decay
    Jul 3, 2015 at 10:06
  • \$\begingroup\$ If you want to include a specific range of operators without having answers never use some of them (due to DNF as mentioned by Peter Taylor), you could require the shortest rule, instead of just any rule that works. \$\endgroup\$ Jul 3, 2015 at 16:01
  • 1
    \$\begingroup\$ Thanks for the feedback! After reading about DNF, I see now the easiest solution is to simply output every "true" row of the truth table which makes this purely an exercise in data transforming, not problem solving, eg. (a&b&~c)|(~a&~b&c)|(a&~b&c)|(~a&b&c)|(a&b&c) \$\endgroup\$ Jul 5, 2015 at 23:32
  • \$\begingroup\$ I want to take this one. \$\endgroup\$
    – Xwtek
    Jan 1, 2016 at 0:01
2
\$\begingroup\$

Translate Treehugger to BrainF**k

(?)

Overview

This problem deals with two esoteric programming languages that I will briefly describe for completeness.

Brainfuck is a language that has only 8 commands. Imagine a tape of values (generally 0-255) stretching infinitely to the right, initialized to zero, and an instruction pointer P pointing to the first element:

|-----|-----|-----|-----|-----...
|  0  |  0  |  0  |  0  |  ...
|-----|-----|-----|-----|-----...
   ^
   P

The eight commands effect the pointer and tape in the following way:

+ ===== increment the value that `P` currently points to
- ===== decrement the value that `P` currently points to
, ===== read a byte from stdin into the location that `P` points to
. ===== output the value that `P` points to as an ASCII character
> ===== move `P` one cell to the right
< ===== move `P` one cell to the left
[ ===== if the value pointed to by `P` is zero, jump past the matching ] ( while(*P){ )
] ===== if the value pointed to by `P` is non-zero, jump to the preceding [ ( } )

Some finer points, for the purposes of this question:

  • Adding one to 255 yields 0, and decrementing 0 yields 255.
  • Moving left off of the tape causes the program to abruptly halt.
  • All [ must be matched with a single ]. They may be nested.

Treehugger is a language derived from Brainfuck, but differs greatly in how memory is stored. Instead of viewing memory as a tape, view memory as a binary tree that expands infinitely downward:

       P
       v
       0
  0---/ \---0
 / \       / \
0   0     0   0
.   .     .   .
.   .     .   .
.   .     .   .

P begins at the top of the tree, and again all values are initialized as 0. Most of the commands are exactly the same as corresponding Brainfuck commands, but there are two differences:

< ===== move P down the left branch of the tree once
> ===== move P down the right branch of the tree once

There is also one new command:

^ ===== move P one node up the tree

It is simple to translate Brainfuck to Treehugger by replacing every < with a ^. Translating Treehugger to Brainfuck, however, is far more difficult.

Input

Your program or function will take in a list of characters from +-<>^,.[], representing a complete Treehugger program.

  • You may assume that the input ends in some terminating character, like a newline or EOF.
  • You may assume that, other than the optional terminating character, every character is one of the 9 commands.
  • The Treehugger program will have balanced [ and ].
  • The Treehugger program will not attempt to move up one node from the top of the tree at any point.
  • The Treehugger program will never contain a , character inside of a [] loop. The program will always take a finite, known number of input bytes.
  • The Treehugger program will terminate for all inputs.

Input must be taken as a string of characters through stdin or a function argument.

Output

Your output should be a functioning Brainfuck program that takes the same number of inputs and provides the same output as the corresponding Treehugger program. Brackets must be balanced, and the code must never move left off of the tape. Your Brainfuck program must terminate.

Rules and Scoring

Your score for this challenge is:

Length of your code + 0.1 * the length of each test case's output

Lowest score wins!

Standard Loopholes are disallowed.

Test cases

Coming soon to a challenge near you...


Is this interesting?

Too easy/hard?

Is the scoring system appropriate?

\$\endgroup\$
1
  • \$\begingroup\$ I do not think this is possibly. And lol "Soon" \$\endgroup\$ Aug 9, 2016 at 1:01
2
\$\begingroup\$

Proposed King-of-the-Hill: Synchronous Bughouse Chess960

I have an idea for what I think could be a fun and somewhat different KOTH contest. However, before I put in the work writing explicitly detailed instructions and writing/deploying a test server, I want to make sure that (a) there will be sufficient interest to go through this effort and (b) the best way to design the contest and restrictions if people would like to play.

Chess960 is a chess variant in which the starting positions of the back-rank pieces are randomized with constraints such that there are 960 possible starting positions. Bughouse chess is a team-based chess variant played asynchronously on two boards in which teammates hand the pieces they capture to their teammates to potentially drop on the board.

Synchronous Bughouse Chess960 (SBC960) is a chess variant I developed to combine these two variants and to impose some synchronization rules to make it suitable for a tournament. Each of the two boards is set up independently using the rules of chess960 of the other (thus making for 921,600 overall starting positions). Game play is organized into orderly rounds during which each player takes his turn in the following order: team 1 white, team 2 white, team 1 black, team 2 black. On a player's turn, he may move a piece according to chess960's rules, drop a captured piece according to bughouse chess's rules, or delay.

Each player starts the game with five delays. When a player uses a delay, his opponent's next turn is skipped (at no cost to the opponent other than perhaps momentum). Delays are legal moves. Play continues until a player has no legal actions when his turn in the round comes up (no legal moves, no legal drops, and no remaining delays). When that condition comes, the outcome of the game is determined by whether that player is in check. If so, the team who has checked the player wins. If not, the game ends in a draw. For convenience, a position is only considered "checkmate" if a player is in check and has no legal moves left.

My KOTH tournament idea is to have players design AIs to play SBC960. I think this game has some interesting possibilities because of the team-based play. For example, rushing for the win on one's board might be a losing strategy for a player if the other team can checkmate his teammate faster. It might also be viable for a player to allow himself to be checked toward checkmate if one's teammate can achieve checkmate before that player runs out of delays. Also, the many starting positions makes it impractical for anyone to write an entry that uses opening libraries.

So, the first question is:

1) Would anyone be interested in participating in an SBC960 tournament? If at least four people would compete, I am willing to put in the work to get this together

If people are willing to play, then I need to know the best way to structure the rules for the entries. This entails the server-client interface (STDIN/STDOUT? sockets with TCP/IP?), whether to permit people from designing AIs that think when it is not their turn, and whether I should have an official "pre-play" round so that AIs can learn how the other entries play. I see the opportunity to make a KOTH that is different than most of the KOTHs on the site, but I want to know:

2) What are people's recommendations for the best way to design the entry rules?

I would appreciate any feedback.

\$\endgroup\$
2
  • \$\begingroup\$ Team KotH is tricky. The only way that I think you really get to assess each answer's strength is to play with homogeneous teams: i.e. two of Alice's bot (one white, one black) vs two of Bob's bot (one white, one black). \$\endgroup\$ Jul 21, 2015 at 17:32
  • \$\begingroup\$ @PeterTaylor I had intended to use homogenous teams for at least some of the games to act at least as a tie-breaker. I think it might be possible to use ANOVA to determine how much an AI's results correlate to its abilities. Of course, I'd have to relearn ANOVA to determine whether this thought is correct. \$\endgroup\$
    – sadakatsu
    Jul 21, 2015 at 18:45
2
\$\begingroup\$

Vowel-Consonant Imbalance

Sandbox question: Is it too easy/too close to an existing question? Related ones I found: Find words containing every vowel and Finding the most 'unique' word

You should write a program or function which receives a list of space-separated words as input and outputs or returns one of the words with the greatest difference between its vowel and consonant counts.

E.g.

"cars" has 1 vowel and 3 consonant so the difference is 2
"queue" has 4 vowels and 1 consonant so the difference is 3

If multiple words have the same maximal difference, exactly one (any of them) should be returned.

Input

todo

Output

todo

Examples

todo

This is code golf so the shortest entry wins.

\$\endgroup\$
2
  • \$\begingroup\$ IMO this is too easy, but if you decide to post it then it needs an unambiguous working definition of "vowel". I assume that input can be mixed case, but e.g. is y a vowel or a consonant? (If you want to be realistic then the answer is "It depends", but I'm not sure I could write a clear and accurate spec for when it's a vowel). What about accented letters? \$\endgroup\$ Jul 22, 2015 at 6:01
  • \$\begingroup\$ @PeterTaylor Thanks, if I post it, I will clarify these. Input will be only lowercase letters and spaces. Vowels will be aeiouy. But it is really easy. Maybe I'll post it on a very slow day once... \$\endgroup\$
    – randomra
    Jul 22, 2015 at 10:48
2
\$\begingroup\$

CJam Expander

Input: a program written in CJam. You can accept input however you'd like.

Output: the same program ready to be put into a PPCG answer. You must:

  • Not change the horizontal position of any token in the program.
  • Put each token one line below the previous one except } which must appear on the same line as the corresponding {. The token immediately following a } will be one line below the }.
    • For this challenge, every letter is considered a token except literal strings and numbers which count as one token regardless of character length.
  • Add e# to the end of every line. The e#s must line up vertically two spaces to the right of the last character in the program.
  • Either prefix each line with four spaces or surround your output with <pre> and </pre>.

Example:

Adapted from Martin Büttner♦'s answer.

Input: 4,{"Happy Birthday "\2="Dear CJam""to You"?N}%

Output:

    4                                               e#
     ,                                              e#
      {                                         }   e#
       "Happy Birthday "                         %  e#
                        \                           e#
                         2                          e#
                          =                         e#
                           "Dear CJam"              e#
                                      "to You"      e#
                                              ?     e#
                                               N    e#

Bonus:

If you output a header and footer like the one below, multiply your score by 0.8. Using the same input, here is an output that qualifies for the bonus:

#CJam, 46 bytes


    4,{"Happy Birthday "\2="Dear CJam""to You"?N}%

Explanation:

    4                                               e#
     ,                                              e#
      {                                         }   e#
       "Happy Birthday "                         %  e#
                        \                           e#
                         2                          e#
                          =                         e#
                           "Dear CJam"              e#
                                      "to You"      e#
                                              ?     e#
                                               N    e#

[Try it online.][1]

[1]: link

Of course, you have to adjust the byte count to match the input. You are not required to make a working link for the online demo (although that would be cool).

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Similar, but with different I/O format and language specificity. \$\endgroup\$
    – Geobits
    Jul 21, 2015 at 17:19
2
\$\begingroup\$

Sort a CSV list by key...imperfectly.

Tags:

Anything I missed and/or overlooked here? I'm pretty sure I closed up most of the holes here. Also, what is there that could use some improvement?

Another question: would this be better tagged as ?


Introduction

You are working for some company you can't stand, two-week notice already turned in, and you've just been tasked with sorting all the CSVs the company has gathered over the years. This doesn't sound like much, except your boss, whom you also don't like, has demanded you implement your own sort. He doesn't care about Big-O whatever (he has never even heard of the term), but he just wants it done. You want to get back at him for making you do this, so you want to make that sort imperfect. At least you know he won't have time to check it until you're gone.

Objective

Your task is to write a program that sorts a CSV table (incorrectly), by key.

A correct program for purposes of this challenge:

  • doesn't use one of the tried-and-false, unfunny techniques.
  • takes two arguments (in order): the key to sort by, and optionally a separator, defaulting to a comma (,).
  • takes the CSV via standard input, in the following format:
    • Each row is separated by a Unix-style line feed.
    • Each entry within each row is delimited by the separator.
    • Each entry is unquoted/etc. It is solely delimited by the separator.
    • Each entry may be assumed to not contain an instance of the separator or a newline.
    • The first row indicates the key names. The successive rows are the data that needs sorted, by key
  • emits the sorted CSV via standard output.
    • The emitted data must also adhere to the above format, including the separator. It must be syntactically correct.
  • looks completely innocent, despite being completely and totally wrong. That's the underhanded spirit.
    • Please don't use Unicode lookalikes. It's not funny nor original, especially after seeing it multiple times on a single question.

In this case, the values for the key key are 1, 2, and 3.

foo,key,value
spammer,1,32nefr2u34
ball,2,304u23rne2
blarger,3,32o4u3jnk4

Invariants

  • The input CSV is assumed to be correct, including each row having the same number of entries. At least they weren't made by such air-headed people.
  • The entries may have varying lengths.
  • The associated values for the key is assumed to be a float (decimal not required) in textual form, base 10.
  • The list may vary in length.

Requirements

  • At least 1% of the list must vary from the "correct" output every single time. This may mean entries that are out of order, lost, or corrupted. This may also include entire columns going missing (in which 100% is "incorrect").
    • This is only required when there are at least 4 entries in the input.
    • The keys themselves are not counted as part of the list, but they don't necessarily have to remain intact.
  • It must print at least 50% of the data it took in, but more than 100% of the original is permitted.
    • As a special case, empty stdin allows empty stdout, and input just consisting of the headers may simply print just headers coming out.
  • The program must have no other external side effects other than what is required to do the above.

Other information

  • The sorting algorithm is up to the implementation. It doesn't matter, as long as it sorts, the sort is stable, and the algorithm's complexity is bounded (i.e. no Bogosort, infinite loops, etc.).
  • No other features may be added, including a help message.

Example

Input:

foo,key,value
ball,5.2,304u23rne2
spammer,1,32nefr2u34
blarger,3.1,32o4u3jnk4

Output (correct):

foo,key,value
spammer,1,32nefr2u34
blarger,3.1,32o4u3jnk4
ball,5.2,304u23rne2

Output (passes this challenge):

foo,key,value
spammer,1,32nefr2u34
ball,5.2,304u23rne2
blarger,3.1,32o4u3jnk4

The person with the highest number of votes wins!

\$\endgroup\$
4
  • \$\begingroup\$ The spec as written seems to allow emitting the empty string as the only output. \$\endgroup\$ Jul 20, 2015 at 13:21
  • \$\begingroup\$ @PeterTaylor Good catch... \$\endgroup\$
    – Claudia
    Jul 20, 2015 at 13:24
  • \$\begingroup\$ Most underhanded questions are tagged as both underhanded and popularity-contest. Since the winner is determined by the number of votes, I'd use both tags, and drop code-challenge. \$\endgroup\$
    – es1024
    Jul 21, 2015 at 6:46
  • \$\begingroup\$ @es1024 Done. <filler text> \$\endgroup\$
    – Claudia
    Jul 22, 2015 at 4:10
1
24 25
26
27 28
145

You must log in to answer this question.

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