541
\$\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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
1

3649 Answers 3649

1
8 9
10
11 12
122
4
\$\begingroup\$

Challenge Statement

The goal of this challenge is to build the 5 state Infinite Time Turing machine that takes the longest to halt.

The rest of this challenge is some definitions and an example to help you.

Turing Machines

For clarity we will define the Turing machines as used for this problem. This is going to be rather formal. If you are familiar with Turing machines this is a single-tape, binary Turing machine, without an explicit halt state, and with the possibility of a no shift move. But for the sake of absolute clarity here is how we will define a classical Turing machine and its execution:

A Turing machine consists of a \$3\$-Tuple containing the following:

  • \$Q\$: A finite non-empty set of states.
  • \$q_s : Q\$: The initial state.
  • \$\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$: A partial transition function, which maps a state and a binary symbol, to a state, a binary symbol and a direction (left, right or no movement).

During execution of a specific Turing machine the machine has a condition which is a \$3\$-Tuple of the following:

  • \$\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$: The tape represented by a function from an integer to a binary symbol.
  • \$k_\alpha :\mathbb{Z}\$: The location of the read head.
  • \$q_\alpha : Q\$: The current state.

For a Turing machine the transition function takes the condition of a machine at step \$\alpha\$ and tells us the state of the machine at step \$\alpha + 1\$. This is done using the transition function \$\delta\$. We call the function \$\delta\$ with the current state and the symbol under the read head:

\$ \delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$

If this does not yield a result, then we consider the machine to have halted at step \$\alpha\$, and the condition remains the same. If it does yield a result \$\left(q_\delta, s_\delta, m_\delta\right)\$ then the new state at \$\alpha+1\$ is as follows:

  • \$\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\$ (That is the tape replaces the symbol at the read head with the symbol given by \$\delta\$)
  • \$k_{\alpha+1} = k_\alpha+m_\delta\$ (That is the read head moves left right or not at all)
  • \$q_{\alpha+1} = q_\delta\$ (That is the new state is the state given by \$\delta\$)

Additionally we define the condition of the machine at time \$0\$.

  • \$\xi_0(k)=0\$ (Tape is all zeros to start)
  • \$k_0=0\$ (Read head starts a zero)
  • \$q_0=q_s\$ (Start in the initial state)

And thus by induction the state of a Turing machine is defined for all steps corresponding to a natural number.

Infinite Ordinals

In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. If you would like to look up a more formal definition this explanation is based of of the Von Neumann definition of ordinals.

In most contexts when talking about the order of events we use natural numbers. We can assign numbers to events such that events with smaller numbers happen earlier. However in this challenge we will care about events that happen after an infinite number of prior events, and for this natural numbers fail. So we will introduce infinite ordinals.

To do this we will use a special function \$g\$. The \$g\$ function takes a set of numbers and gives us the smallest number greater than all the numbers in that set. For a finite set of natural numbers this is just the maximum plus 1. However this function is not defined on natural numbers alone. For example what is \$g(\mathbb{N})\$, or the smallest number greater than all naturals. To create our ordinals we say

  • \$0\$ exists and is an ordinal.
  • If \$X\$ is a set of ordinals then \$g(X)\$ exists and is an ordinal.

This gives us the natural numbers (e.g. \$1 = g(\{0\})\$, \$2 = g(\{1\})\$ etc.) but also gives us numbers beyond that. For example \$g(\mathbb{N})\$, this is the smallest infinite ordinal, and we will call it \$\omega\$ for short. And there are ordinals after it, for example \$g(\{\omega\})\$ which we will call \$\omega + 1\$.

We will in general use some math symbols \$+\$, \$\times\$ etc. in ways that are not defined explicitly. There are precise rules about these operators, but we will just use them as special notation without definition. Hopefully their use should be clear though. Here are a few specific ordinals to help you out:

\$ \begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\ \omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\ \omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z\in \mathbb{N}\})\\ \omega^\omega &=& & & g(\{\omega^x\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\})\\ \end{eqnarray} \$

If an ordinal is not the successor of another ordinal, meaning there is not a next smaller ordinal, we call that ordinal a limit ordinal. For example \$\omega\$, \$\omega\times3\$, and \$\omega^{\omega\times 2}+\omega^6\times 4\$ are all limit ordinals. \$3\$, \$\omega\times 5 + 12\$ and \$\omega^{\omega^\omega}+1\$ are not. Some authors will specify further that 0 is not a limit ordinal, we will be explicit about 0 when we talk about limit ordinals to avoid confusion.

Infinite Time Turing Machines

A classical Turing machine is equipped with a start status, and a way to get from one status to another. This allows you to determine the status of the machine at any finite step.

Infinite time Turing machines extend classical Turing machines to have a defined status non-zero limit ordinals as well. That is ordinals as defined above which are not the successor of any previous ordinal. This addition makes the condition of the machine defined at transfinite time as well.

Formal definition

For this we add an additional object to the machine's definition

  • \$q_l : Q\$: The limit state

And we define the condition of the machine at some limit ordinal \$\lambda\$ to be

  • \$\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$
  • \$k_n = 0\$
  • \$q_n = q_l\$

\$\$

Example

Here we have a diagram of the current 2-state champion:

2-State champion If we want to calculate how long this takes to halt we can't just throw it into a computer and run it, rather we have to determine it by hand.

To start we follow the machine through it's normal execution. It starts at \$q_1\$ and we can see that from there it always moves to \$q_2\$ flipping the cell under the read-write head. So here it turns the cell on. Then since the cell is on it will transition back to \$q_1\$, turning the cell off and moving to the right. This puts us in the exact same condition as the start, except the read-write head has advanced by 1. So it will continue in this loop of flipping on bit on and off and moving to the right endlessly.

ANIMATION 1 HERE

Now that we have determined the behavior of the machine for all finite steps we can figure out the state at step \$\omega\$. Each cell is on for at most 1 step, before being turned off, and then it is never on again. So the limit supremum of each cell is \$0\$, and at step \$\omega\$ the tape is entirely empty.

So this means that after \$\omega\$ the machine just repeats its exact behavior, the condition at step \$\omega+n\$ is the same as the condition at step \$n\$. And this persists even after we hit another limit ordinal, \$\omega+\omega\$, the tape remains blank and just repeats the same behavior over and over.

ANIMATION 2 HERE

So we now have an accurate description of the machine for states of the form \$\omega\times n + m\$, and it doesn't halt for any of those steps. It just repeats the same infinite pattern an infinite number of times. So now we can look at the step after all the steps we have described. We take the next limit ordinal:

\$ g(\{\omega\times n + m : n\in \mathbb{N}, m \in \mathbb{N}\}) = \omega\times\omega = \omega^2 \$

Your first instinct might be that the tape will be completely empty again, since it was empty at every step \$\omega\times n\$. However with infinities instincts can be misleading, so we should look at the definitions carefully instead.

In order for a cell to be zero it must converge to zero. Since the only possibilities are zero and one, this means that for each cell there must be some step \$x\$ after which that cell is always zero. Previously since each cell was only turned on once that step was just the step after it was turned off.

Now if such a step were to exist for a cell \$k\$ it would be of the form \$\omega\times n + m\$, however we know that the cell will be turned on again some time during the \$\omega\times(n+1)\$ iteration. In fact it will be turned on at exactly step \$\omega\times(n+1) + 2k + 1\$.

So no cell (with a non-negative index) will converge to a stable value. Meaning that by the limit supremum all non-negative cells will be on at time \$\omega^2\$.

ANIMATION 3 HERE

So here we finally get some new behavior. With cell 0 on, the machine transitions to \$q_2\$ turning the cell off, and since \$q_2\$ doesn't have a transition for off cells the machine halts.

This gives us a total of \$\omega^2+1\$ steps until halting.

\$\endgroup\$
3
  • \$\begingroup\$ It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. \$\endgroup\$
    – user41805
    May 7 '21 at 12:39
  • \$\begingroup\$ @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. \$\endgroup\$
    – Wheat Wizard Mod
    May 7 '21 at 12:42
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/36747/45613 and codegolf.stackexchange.com/questions/18028/… (This doesn't seem to be a duplicate) \$\endgroup\$
    – Beefster
    May 18 '21 at 16:25
4
\$\begingroup\$

Reveal by Halves (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

A valid answer:

  • Takes a number \$w\$ and (assumed non-negative) integer \$x\$.
  • Outputs an integer list with a length of \$2^w\$, initially filled with zeroes.
  • For each number \$n\$ from \$0\$ to \$w-1\$ (inclusive), divide the list into sub-lists of size \$2^n\$, then increment all of the values in the sub-list that contains the index \$x\$.

Examples

(with coordinates from left, 0 indexed, but your answer may have change these)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds

Meta questions

  • Are these tags fitting?
  • Would this be better in one dimension? (like \$3, 2\$ returns 11320000) Edit: I've changed it to one dimension but I can revert if it makes it less interesting.
  • Should \$w\$ or \$2^w\$ be the input?
  • Is this a duplicate?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ My opinions on some meta questions. 1) I think one dimension would be better, the core of the challenge remains the same but the challenge itself becomes more "pure" which, in my opinion, is a good thing. 2) I'm a fan of flexible I/O, so if it were up to me I'd let people choose if they want \$w\$, \$2^w\$ or both as input. If you don't like this, both options are honestly fine. \$\endgroup\$
    – Delfad0r
    May 10 '21 at 22:24
4
\$\begingroup\$

I'm Lazy*: Top-left align my text

posted

\$\endgroup\$
2
  • \$\begingroup\$ Definitely not too trivial for code golf \$\endgroup\$
    – qwr
    Jun 2 '21 at 14:20
  • \$\begingroup\$ I think squash up could be its own challenge which has room for simplification. My thoughts being using a transposed grid of strings, which I guess can work for this challenge too \$\endgroup\$
    – qwr
    Jun 2 '21 at 14:21
4
\$\begingroup\$

Demonstrate some advanced abstract algebra

\$\endgroup\$
10
  • \$\begingroup\$ I think we should be able to define the types and values of S, rather than necessarily using integers. In that case, - and + would not (necessarily) be actual arithmetic negation and addition, so maybe they would have to be renamed to use other symbols (or just use function syntax f(a,b)?) \$\endgroup\$
    – pxeger
    May 31 '21 at 8:50
  • \$\begingroup\$ And do all 9 functions have to operate on the same set S? I think it could be more interesting if they didn't have to, but it might result in cheating/loopholes. Also, what does "uniquely exhibits" mean exactly? Demonstrates exactly one of the 9 properties? \$\endgroup\$
    – pxeger
    May 31 '21 at 8:52
  • \$\begingroup\$ In fact, I think people will just submit "addition, addition, multiplication, subtraction" for the first 4 at least, and I suspect they will almost always be the shortest option in most languages so it might not be very interesting as it is \$\endgroup\$
    – pxeger
    May 31 '21 at 9:04
  • \$\begingroup\$ Writing one program is hard enough. Writing 9 seems like a lot to ask. I think you could make a stripped down challenge using just commutativity and associativity. I barely known any abstract algebra. I think these varieties are called magmas? \$\endgroup\$
    – qwr
    Jun 2 '21 at 14:54
  • \$\begingroup\$ Is this even possible with the surjectivity condition? You should provide an example of each program. \$\endgroup\$
    – qwr
    Jun 2 '21 at 14:57
  • \$\begingroup\$ @qwr I don't have examples for each program, and even if I did, I wouldn't include them as that would just lead to people porting them into their own languages. Yes, I believe magma is the correct term for \$*\$ here. I'm not sure if this is possible, but I'd be surprised if it isn't. I've allowed for an answer to be a proof of impossibility however, on that off-chance. \$\endgroup\$ Jun 2 '21 at 15:04
  • \$\begingroup\$ Well it's more than a magma since you added more two more operators right \$\endgroup\$
    – qwr
    Jun 2 '21 at 15:18
  • \$\begingroup\$ @qwr No, I believe a magma is just a pair, the binary operator and the set its closed on, no matter the additional operators defined on that set \$\endgroup\$ Jun 2 '21 at 15:31
  • \$\begingroup\$ This is a really cool problem. It is hard so I wouldn't be again having a separate "easy" version with just the main three: commutative/associative/distributive. Uniquely exhibiting those is already a nontrivial and neat challenge. I don't know if others would vote a dupe, but I'd def be in favor of having both. As is, I don't think the harder version will have a lot activity. But I do think an easier one would! \$\endgroup\$
    – AviFS
    Jun 13 '21 at 1:18
  • \$\begingroup\$ @AviFS I do actually have an easier version Sandboxed, where I think they're clearly separate enough to not be dupes. \$\endgroup\$ Jun 13 '21 at 1:42
4
\$\begingroup\$

Minimal distinct character quine

\$\endgroup\$
3
  • \$\begingroup\$ This seems well specificed \$\endgroup\$ Jun 16 '21 at 10:04
  • \$\begingroup\$ distinct means different? \$\endgroup\$
    – mathcat
    Jun 19 '21 at 10:01
  • \$\begingroup\$ @math Yes (filler) \$\endgroup\$
    – emanresu A
    Jun 19 '21 at 10:30
4
\$\begingroup\$

Full name quine

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice question but seems hard \$\endgroup\$
    – mathcat
    Jun 25 '21 at 18:11
  • 1
    \$\begingroup\$ i assume custom SBCS languages will have to output the full names of their characters when represented in unicode? Or should they output the name of the visual representation? \$\endgroup\$
    – Razetime
    Jun 28 '21 at 6:20
  • \$\begingroup\$ Full names represented in unicode. \$\endgroup\$
    – emanresu A
    Jun 28 '21 at 8:29
4
\$\begingroup\$

r my Vyxal

\$\endgroup\$
6
  • \$\begingroup\$ Needs more test-cases. Also, in the explanation you use spaces as though they're ignored, but that isn't mentioned in the description of the task itself. I'd suggest just saying that "all other characters" will be limited to ASCII letters only, for example?. \$\endgroup\$
    – pxeger
    Jul 4 '21 at 7:47
  • \$\begingroup\$ @pxeger In Vyxal, spaces are NOPs used to seperate stuff. In the subset I'm using, spaces are a function like everything else. I'll make that clearer, and add more testcases. \$\endgroup\$
    – emanresu A
    Jul 4 '21 at 8:15
  • \$\begingroup\$ But I'm suggesting limiting the definition of what are functions to ASCII letters only to provide more golfing opportunities without having to handle edge cases that might occur because of spaces \$\endgroup\$
    – pxeger
    Jul 4 '21 at 8:54
  • \$\begingroup\$ @pxeger Ok. (filler) \$\endgroup\$
    – emanresu A
    Jul 4 '21 at 8:55
  • \$\begingroup\$ It says that we can assume there will always be two values to pop, but one of the testcases is simply “1”. Is that something that we will have to account for? \$\endgroup\$ Jul 4 '21 at 15:09
  • \$\begingroup\$ @AaronMiller What I meant is, wherever there's a function, there will be two. I'll add that. \$\endgroup\$
    – emanresu A
    Jul 4 '21 at 19:58
4
\$\begingroup\$

Extremely small data compressor

In 2014 Jarek Duda at Purdue University wrote a paper containing several ideas for encoding computer data, entitled “Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding". The paper is available at Cornell University Library’s ArXiv project: https://arxiv.org/abs/1311.2540

One of the many fascinating things about this paper is that it begins by describing an extremely simple data compression algorithm, using the concept of the "Uniform asymmetric binary systems (uABS)". In fact, it is so simple, that you can implement it in only a few lines of code.

Basically it attempts to interpret a sequence of input symbols as a single Integer, and as each symbol comes in the Integer can be appended with new information. The trick is that the Integer is represented not using a place-value binary number system, but an alternative system. This representation is designed so that sequences of symbols which occur with higher probability will be represented by a smaller amount of space within the Integer's encoding.

Challenge

You will implement the simple uABS compression algorithm, so that given a sequence of 0s and 1s, your program will compress them into a (usually) smaller sequence of 0s and 1s.

Pseudocode

The algorithm in psuedocode is as follows:

  • Begin with an Integer X, and set it to 1. This will be the main Integer that we append during the algorithm.
  • The input data is a sequence of symbols, each 0 or 1, called Input
  • Find the probability P that any given symbol in Input is 1, (the number of 1s divided by the total number of symbols)
  • For each symbol S in Input, set X to the output of the function Encode(x,s,p)
  • After processing all the input symbols, output the final integer X. -- This encoded integer will hopefully have less bits than the input

The Encode function itself can be described as follows:

$$ Encode(x,s,p)= \left\{ \begin{array}{11} \mbox{if } s = 0 & \big\lceil\frac{x+1}{1-p}\big\rceil-1 \\ \mbox{if } s = 1 & \big\lfloor\frac{x}{p}\big\rfloor \end{array} \right. $$

Where

$$ \begin{array}{11} s \text{ is a symbol, either 0 or 1} \\ x \text{ is the Integer} \\ p \text{ is the probability that any symbol in the Input data is 1 } \\ \lceil \rceil \text{ is the mathematical ceiling function } \\ \lfloor \rfloor \text{ is the mathematical floor function } \end{array} $$

Notes

  • The input is a sequence of symbols, each symbol being 0 or 1, in any method that is available in your chosen language. Examples include a sequence of ascii characters '0' '1', an array of integers, etc.

  • The output will be a sequence of symbols in the same format as the input sequence. The output sequence represents the compressed version of the input data.

  • Empty input data has undefined behavior.

  • Input data containing only 0s has undefined behavior.

  • Sometimes the encoded Integer might have more bits than the input, not less. This typically happens when the number of 1s and 0s is relatively even. Data with an unbalanced number of 0s and 1s results in better compression.

  • You may assume that the size of Integer will be your language's largest integer type. The test cases outside this range can be ignored for your language.

  • Note that if you are trying to test this by 'decoding' or 'decompressing' the compressed data, and compare it to the original, one would have to store additional information, such as the length of input and probability P, but for simplicity this has been left out of the challenge.

Example Input and Output

Short examples:

Input             Output    
10                101
10010100000       1011101001
1111              1
11111111111       1
10000000          11011
10011111010101    10110000100101    

Longer examples:

Input  11111110110111110111111111011111
Output 11111000011110110

Input  000000000001000000010000000000001100000000001
Output 1110000101100111000011111

Input  000000000001000000010000000000001100000000001000000000000000000000000000000000000000000000000000000000000000001
Output 1010100110111110010111011110110101010

Scoring

  • The program with the fewest number of characters wins.
\$\endgroup\$
9
  • \$\begingroup\$ 1. IMO the pseudocode could be made clearer by firstly explaining what "machine integer" means (does it mean "unbounded integer" aka "big integer"?) and secondly golfing it a bit: using a "foreach" loop notation for S and eliminating the variable X'. 2. I think it would be helpful to be explicit about how p should be derived from the input. I presume that it means looping over the input twice, once to count and once to compress. 3. IMO restricting the input format to strings of ASCII 0 and 1 detracts from the core challenge. Why not allow arrays/lists of integers? \$\endgroup\$ Jul 7 '18 at 12:13
  • \$\begingroup\$ Thanks, i have revised. \$\endgroup\$
    – don bright
    Jul 7 '18 at 14:08
  • \$\begingroup\$ I really like this one. Something quasi-practical, and yet simple and small enough to be fun. Just to be clear, the output is the binary representation fo the integer X, without any leading zeros, correct? \$\endgroup\$ Jul 8 '18 at 19:02
  • \$\begingroup\$ Also, you mention "input size of at least 128 symbols", but it might be more important to specify output size limit, since many languages have hard bounds on maximum integer size. Since output size varies for the same input length, it might have to be something like "you may assume that the number of symbols in the output is less than or equal to the number of bits in your language's largest integer type". (The last test case would then be optional in languages that can handle only up to 32 bit integers). \$\endgroup\$ Jul 8 '18 at 19:12
  • \$\begingroup\$ yes the output is the binary representation of the final integer X, i believe the leading zeros is correct. do you think 32 bit is the good limit or 64, since modern machines tend to be 64 bit? thanks \$\endgroup\$
    – don bright
    Jul 8 '18 at 20:05
  • \$\begingroup\$ 32 is probably a reasonable limit, one that most languages can handle without need for external libraries. \$\endgroup\$ Jul 14 '18 at 14:22
  • \$\begingroup\$ @sunar thanks, i have updated. \$\endgroup\$
    – don bright
    Dec 29 '18 at 14:21
  • \$\begingroup\$ I assume the intent is for P to be calculated as # of '1' in the input / # of symbols in the input? That seems like it would match the definition given, but it would be helpful if it's described explicitly. \$\endgroup\$ Jan 3 '19 at 22:24
  • \$\begingroup\$ Done, thanks.... \$\endgroup\$
    – don bright
    Jan 3 '19 at 23:32
4
\$\begingroup\$

Alphabet Reconstruction

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Fairly similar \$\endgroup\$
    – Dingus
    Oct 17 '21 at 11:00
  • \$\begingroup\$ @Dingus but mine is better :P I'll give this some thought and if I can't think of a new spin to put on this ill just delete it cause its a dupe. Thank you! \$\endgroup\$ Oct 17 '21 at 16:06
  • \$\begingroup\$ @Dingus hope this changes it enough. Flipped it on its head :D \$\endgroup\$ Oct 18 '21 at 13:20
  • 1
    \$\begingroup\$ I certainly like the new story better! I found it a bit confusing that the first example has the unordered letters first in the output; the significance of 'any given wordlist may have more than one proper alphabet' hadn't sunk in. I'd suggest expanding on this point under one of the earlier subheadings. \$\endgroup\$
    – Dingus
    Oct 19 '21 at 0:55
  • 1
    \$\begingroup\$ For the printable characters, perhaps specify ASCII 33-126? But I'd actually suggest restricting it to only alphabetic (A-Za-z) characters instead. Handling ^ or $ (for instance) doesn't really add anything to the challenge but will complicate any regex-based solutions. \$\endgroup\$
    – Dingus
    Oct 19 '21 at 0:55
  • \$\begingroup\$ @Dingus noted! ill think abt how to word the "more than one proper alphabet" bit, and once i figure it out ill make both edits :) thank you for your help \$\endgroup\$ Oct 19 '21 at 2:02
  • \$\begingroup\$ @Dingus does this clarify the multiple valid options thing? also, do you think I should include every valid output for the Cod Com Dy example? \$\endgroup\$ Oct 19 '21 at 13:14
  • 1
    \$\begingroup\$ Nice, it's crystal clear now. The only other suggestion I'd make is to consider deferring to the default I/O formats instead of stipulating space/newline delimited strings. At the least, taking input as a list of strings seems fairly natural, as does outputting a list of characters. \$\endgroup\$
    – Dingus
    Oct 19 '21 at 23:11
  • \$\begingroup\$ @Dingus ah, it was some weird holdover. What exactly should I write, "May take input and output in any reasonable format"? \$\endgroup\$ Oct 20 '21 at 0:05
  • \$\begingroup\$ Yep sounds good. \$\endgroup\$
    – Dingus
    Oct 20 '21 at 1:06
  • 1
    \$\begingroup\$ @Dingus great :) im at +3 so ill ask chat for feedback and unless theres any objections, i think ill post it :] \$\endgroup\$ Oct 20 '21 at 2:15
4
\$\begingroup\$

Play RPS with 3 bits of memory

This is a rough draft for now, the specifics, presentation and title will probably be adjusted

In this game you will be building bots to play rock paper scissors against each other. Of course rock paper scissors is not a very interesting game, just pick one of the three randomly. Can't get better than that?

The first thing here is that, we will play a slight variation on the game which introduces a small amount of strategy.

But more importantly in this version we will be designing very simple bots. Your bot will not be able to pick things randomly, nor will it be able to simulate complex strategies, because your bots will have 3 bits of working memory.

The game

Before we get into exactly how the bots will be made and what exactly it means to have only 3 bits of memory lets cover the game.

For each pair of bots we will play 48 rounds of RPS. In each round both bots will select a choice of Rock, Paper or Scissors. Rock beats scissors, paper beats rock and Scissors beats paper, if the two chose the same move they tie.

When you win you will receive points based on your play. If you win with scissors you get 1 point, if you win with paper you get 3 points, and if you win with rock you get 6 points. If you tie or lose you get 0 points.

Each bot will play every other bot and the bots will be scored on the number of points gained in total.

The bots

Your bot will have 3 bits of working memory, that means at any given time it will have stored a number between 0 and 7. To decide what to play it will know two things

  1. What it has in memory
  2. The last move it's opponent made

Given those it should spit out

  1. What move it wants to make
  2. 3-bits to write into memory

This is so simple you don't actually need to write "code" to represent your bot. Your bot is really just a \$8\times 3\$ lookup table, plus a single move which it will make as it's first move. (We can assume that the starting memory is 0 without loss of generality)

And in fact you will submit your bots in this format as it makes it easy to verify your bot works and doesn't cheat.


Sandbox

I like this challenge because it is

  1. Completely deterministic who wins, to the point where you can, for small bot pool work out with pen and paper the scores.
  2. It is basically language agnostic. No need to bother with JS.
  3. There's basically no way to cheat. It's going to be really hard to exploit a vulnerability in the handler when you can't run arbitrary code.

I am a little concerned though that there might not be a whole lot to do? I'm not sure how much better one bot really can be than others. Obviously you can always take 1 bot and design a bot which plays perfectly against it. But I'm not totally sure how much a carefully arranged bot is going to do better than ones that are just a pile of random connections.

Turning the memory size up could improve this but the larger you make it the more complex each bot gets, and I think the fun is really in being able to hand tune your bot.

However I don't know what I can do to find out other than just post this.

\$\endgroup\$
6
  • \$\begingroup\$ Seems bruteforceable \$\endgroup\$
    – pxeger
    Oct 17 '21 at 18:40
  • 4
    \$\begingroup\$ This is a unique challenge, and I think you could post it. If it doesn't work out, then we'll all know not to do it again (or an improved version could be posted later). If it does work, CGCC'll have a new kind of challenge, which would be great. \$\endgroup\$
    – user
    Oct 17 '21 at 18:57
  • \$\begingroup\$ @pxeger There are 1333735776850284124449081472843776 machines possible. Brute forcing that would probably mean playing every machine against every other machine. It may be solvable, but I don't think it is feasible to brute force it. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 17 '21 at 21:15
  • 1
    \$\begingroup\$ I'd prefer to have rigid I/O (fixed I/O method and format) for KotH purposes. Or you could just say "write down the 8x3+1 possible outputs in a specific format". The barrier to post some bot looks pretty low, so I'd expect a large number of answers in the worst(?) case which would require some kind of automated controller. \$\endgroup\$
    – Bubbler
    Oct 18 '21 at 1:13
  • \$\begingroup\$ @WheatWitch ah, I misread the challenge \$\endgroup\$
    – pxeger
    Oct 18 '21 at 6:59
  • 1
    \$\begingroup\$ @bubbler oh I absolutely will write a controller once the rules are nailed down a bit. Just because you can score this by hand does not mean it would not be very tedious \$\endgroup\$
    – Wheat Wizard Mod
    Oct 18 '21 at 7:40
4
\$\begingroup\$

Remove submatrices

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

Solve the halting problem for ^/a*b*/b*a*/[ab]*$ in ///

///, a.k.a. Slashes is an esoteric programming language with simple two operations. One is to output its source to remove from it. The other is to substitute itself. The language is proven to be Turing-complete, so some programs such as /ab/bbaa/aab won't halt while some such as /ab/bbaa/ab will.

At first I questioned if halting problem for ^/[ab]*/[ab]*/[ab]*$ is solvable, but I learned unlikely.

So I am simplying to ^/a*b*/b*a*/[ab]*$.

Problem

Given a slashes program that matches ^/a*b*/b*a*/[ab]*$ in POSIX BRE (i.e. below), determine whether the program halts or not.

Format of program, if you are not familiar with POSIX BRE

program = "/" first "/" second "/" third
first = "" | first "a" | first first.b
first.b = "" | first.b "b"
second = "" | second "b" | second second.a
second.a = "" | second.a "a"
third = "" | third "a" | third "b"

Constrains

In this problem every program's length is up to 153.

Detailed rules

  • Can be either a full program or a function.
  • Standard i/o apply.
    • Examples of input format
      • a string of program
      • three strings p,q,r when the program is /p/q/r
      • integers p,q,r,s and a string t when the program is /a\{p\}b\{q\}/b\{r\}a\{s\}/t
      • entirely as an integer (think of it by yourself)
    • Examples of output format
  • Standard loopholes apply.
  • This is ; shortest code wins.

Examples

Testcase generator 1

My noncompetive solution

///: no
/a//: yes
/ab/bba/aab: yes
/ab/bba/aaab: yes
/ab/bba/aabb: no

Meta

  • Were similar things ever done before?
  • I am not even sure if this problem is solvable.
  • Just thought there are answers if I clarify maximum length of input.
  • Should I change the problem's genre to ? Would making a maximum length of the program be boring?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ /// is turing-complete, so this is not possible \$\endgroup\$
    – pxeger
    Apr 25 '21 at 12:33
  • \$\begingroup\$ Should we simplify it more? \$\endgroup\$
    – user100411
    Apr 25 '21 at 20:23
4
\$\begingroup\$

Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
    #This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character

Other notes

  • When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
  • The . command does not pop the item from the dump
  • When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
  • Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
  • Nested loops are supported
  • The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
  • BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
  • The maximum value of an item in the dump is 255

Examples/Testcases

brainf**k emulation

++++++(;++++++++;-);.

This should output 0

Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
    ;         #Move to another item in the dump
              #    Note the first time this loop runs,
              #    this will insert a new item
    ++++++++  #Increment the new item by 8
    ;         #Switch to another item in the dump
              #    Note there are only 2 items currently,
              #    So this will switch to the only other
              #    item, the one we initially incremented to 6
    -         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
              #    Note this switches the pointer back to
              #    The item we have been incrementing by
              #    8 each loop
.             #Output as ASCII character

This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

Random output

+:++:+++:++++:+++++:;.

This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
       #    Note this last item is added because ; will
       #    always switch to an item that is *not* the
       #    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character

To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
          ^

As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

cat

,(.,)

Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

When will it end?

++++(,:+++++;++(;++++++;--):++++;---)

This program doesn't output anything, but runs for a non-deterministic amount of time.

Explanation

++++             #Increment first item to 4
(                #Start loop
    ,            #Read char from STDIN to new item in dump
    :+++++       #Push 5 to dump
    ;++          #Switch to random item in dump and add 2
    (            #Start loop
        ;++++++  #Switch to random item in dump and add 6
        ;--      #Switch to random item in dump and subtract 2
    )            #End loop
    :++++        #Push 4 to dump
    ;---         #Switch to random item in dump and subtract 3
)

This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

\$\endgroup\$
1
  • \$\begingroup\$ I feel like a lot of time will come from the RNG, so better solutions might sacrifice some "randomness" for speed - You might want to standardise "randomness" \$\endgroup\$
    – emanresu A
    Dec 22 '21 at 3:42
4
\$\begingroup\$

Converge to a number

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

Rearrange a list so no element is in its original place

Rules: take a list of positive integers (allowing duplicates) and output those integers reordered such that no item of the output list is equal to the item in the same index of the input. Assume this is possible for any input you will get.

Examples:

 in: 1,2,3,4
out: 2,3,4,1

 in: 3,3,1,2
out: 2,1,3,3

 in: 1,1,2,2,3,3,3
out: 3,2,3,3,2,1,2

meta:

Is this a dupe of this? Duplicate items aren't allowed in that challenge, and you have to uniformly-random-ly output one of all valid derangements. Sort of a tossup on whether that's too similar in my own opinion, I have no idea.

\$\endgroup\$
3
  • \$\begingroup\$ what happens when the input is [1, 2, 2, 2, 2, 2]? \$\endgroup\$
    – badatgolf
    Dec 16 '21 at 13:31
  • \$\begingroup\$ @justANewbie "Assume this is possible for any input you will get" means that you wont get that input. Should I rewrite that clause to be clearer? \$\endgroup\$ Dec 16 '21 at 13:33
  • \$\begingroup\$ I see no reason to restrict it to single digit numbers, positive integers seems fine. \$\endgroup\$ Dec 17 '21 at 18:24
4
\$\begingroup\$

Schrödinger's cat program

\$\endgroup\$
1
  • \$\begingroup\$ This is probably good to post now, and it looks like a good challenge! \$\endgroup\$
    – emanresu A
    Dec 27 '21 at 5:59
4
\$\begingroup\$

Incrementally Increment Identical Integers

\$\endgroup\$
2
  • \$\begingroup\$ Total rewording suggestion for everything up until before "To demonstrate": Given a non-empty non-descending list of any integers, increment each number by how many identical elements occur to its left. \$\endgroup\$
    – Adám
    Jan 1 at 18:16
  • 2
    \$\begingroup\$ @Adám For what it's worth, I find that less understandable than the current description. It's probably a difference of APL mindset vs. Python mindset. \$\endgroup\$
    – DLosc
    Jan 1 at 18:18
4
\$\begingroup\$

Egyptian fraction representations of 1

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

Remove odd indices and double the even indices

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The test cases are now consistent with the example explanation, but not with the "remove odd, double even" description. You could fix this by either changing this to "remove even, double odd", or switching to 0-indexing \$\endgroup\$
    – pxeger
    Jan 17 at 12:40
4
\$\begingroup\$

Cops and Robbers - Find my other token

\$\endgroup\$
7
  • \$\begingroup\$ The robbers wins = many cracks (accept the most upvoted) \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:26
  • \$\begingroup\$ 3. No you can't \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:26
  • \$\begingroup\$ 2. No maybe secret is too hard. do you mean secret guessing game? \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:28
  • \$\begingroup\$ 1. Yeah this is ok \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:28
  • \$\begingroup\$ 4. If you want then No, else Yes \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:30
  • \$\begingroup\$ 2 votes is best, if you want then goto post \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 14:48
  • 1
    \$\begingroup\$ @Fmbalbuena The sandbox guideline says typically at least 3 votes. \$\endgroup\$
    – mathcat
    Jan 14 at 15:02
3
\$\begingroup\$

Given a text, determine the language it is written in. The possible languages are: English, Danish, Romanian and Hungarian. The shortest program wins.

Some examples of text in each language can be found at Project Gutenberg

You are required to include examples of runs on text files other than the ones provided here.

The input file name is given as a command line argument. Except the input text, you are not allowed read additional files (e.g. to train your program) so please encode any data in your program.

Your program must output on of the following words English, Danish, Romanian, Hungarian.

Examples

$ ./language pg2600.txt
English
$ ./langauge pg12167.txt
Danish
$ ./language 11756-0.txt
Romanian
$ ./language 30163-0.txt
Hungarian
\$\endgroup\$
6
  • \$\begingroup\$ Another source of plain text passages might be the Gutenburg project. They do have books in languages other than English. \$\endgroup\$ Jun 22 '11 at 14:53
  • \$\begingroup\$ Thanks. I updated the text problem to include some books from Gutenberg. \$\endgroup\$
    – Alexandru
    Jun 22 '11 at 15:04
  • \$\begingroup\$ Related \$\endgroup\$
    – Beta Decay
    Sep 7 '16 at 10:32
  • \$\begingroup\$ Looks pretty trivial to me. Any sufficiently long text will have ă if Romanian, ő if Hungarian, å if Danish, and neither if English. None of the special characters occur in any other of the four languages. \$\endgroup\$
    – Adám
    Jun 5 '17 at 10:45
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$
    – user58826
    Jun 9 '17 at 15:20
  • \$\begingroup\$ @programmer5000 The OP hasn't been seen since 2011, I think you're fine. \$\endgroup\$ Jul 21 '17 at 13:21
3
\$\begingroup\$

Count Syllables

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

Input

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

4
challenge
to
count
syllables

Output

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

2
1
1
3

Scoring

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

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

Rules

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

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

Suggestions

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

\$\endgroup\$
10
  • 12
    \$\begingroup\$ This has one major flaw: the output is subjective. How many syllables do these words have? Every; victory; hierarchy; desire; oil; hour; poem. The only real way I see to work around this is for you to produce a marked-up version of the word list. \$\endgroup\$ May 29 '12 at 20:40
  • \$\begingroup\$ I was really worried about that, and I don't see a way around it. \$\endgroup\$
    – PhiNotPi
    May 29 '12 at 20:42
  • 1
    \$\begingroup\$ I personally would love to see more language processing challenges. I agree with @PeterTaylor on the difficulty of some words. Perhaps taking a specific text(s) and identifying explicitly in the challenge which words will have how many syllables? \$\endgroup\$
    – Gaffi
    Jun 8 '12 at 3:34
  • 2
    \$\begingroup\$ @PeterTaylor ...Or maybe you could filter ambiguous words out of the reference list? \$\endgroup\$
    – user16991
    Feb 8 '15 at 1:19
  • 1
    \$\begingroup\$ What's the point of the first line of input? \$\endgroup\$
    – msh210
    Apr 27 '16 at 20:05
  • 3
    \$\begingroup\$ If you provide a reference list, A hyphenated reference list, and hide a secret list which may or may not include members of the reference list, this would be a reasonable challenge \$\endgroup\$ Sep 17 '16 at 0:05
  • \$\begingroup\$ Do you plan to post this? If not, I'd be happy to adopt it. (If you don't respond within two weeks, by community standards, I'm allowed to do so.) \$\endgroup\$
    – MD XF
    Aug 18 '17 at 3:20
  • \$\begingroup\$ The example of inaccurate program that would score 2 - did you mean to output 3 1 1 2 rather than 3 2 2 2? \$\endgroup\$
    – Heimdall
    Nov 9 '17 at 18:31
  • \$\begingroup\$ A reference list could be dynamic: potential contestants can ask for words of their choice to be added to the list. They won't know what's on the secret list but will try to make their programs as accurate as possible (according to your syllable count) so they should always be able to ask for specific words they are not sure about. Of course, you could make it in different language. In my language, Slovene, it's much clearer how many syllables words have. How about Solresol, haha! \$\endgroup\$
    – Heimdall
    Nov 9 '17 at 18:38
  • \$\begingroup\$ I am going to adopt this if you don''t respond \$\endgroup\$ Dec 20 '17 at 16:48
3
\$\begingroup\$

Chess move

The Challenge

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

Requirements

The chess move will have this format:

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

Examples:

d2d4
f8g7
a7a8R

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

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

rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

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

Scoring

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

Bonus multipliers:

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

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

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

Examples

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

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

e2e4 rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

Your corresponding output string would then be one of these:

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

rnbqkbnr pppppppp 00000000 00000000  0000P000  00000000 PPPP0PPP RNBQKBNR
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Before I get on to more specific criticisms: as presented, without the bonus this is too trivial to be interesting. I suggest removing some flexibility: require Fen notation for the board position and algebraic notation for the move, and making the current bonus options mandatory. On specifics: it's not clear why you talk about storage; and the board position notations you suggest don't include enough information to know whether en passant is possible. \$\endgroup\$ Dec 22 '13 at 23:56
  • \$\begingroup\$ @PeterTaylor I agree that compared to chess programs this may be trivial, but I would like to make it a golf challenge. Compared to the hot code golf questions this is quite elaborate already in its basic form. (For a good solution the board design may need to be changed drastically). It is true that there is no attention to the legality of moves (whether it is possible to capture en passent) but for a mere viewer this is not required so I am not too worried about this. So far the chess questions seem to get very few answers as they tend to be complex and I hope to offer relatively easy entry. \$\endgroup\$ Dec 30 '13 at 11:02
  • 2
    \$\begingroup\$ Your point about en passant is valid - you had said in the spec to not worry about legality. I'll try to convince you of my first point: without the bonus, this reduces to: a) parse first four characters into (col 1, row 1, col 2, row 2); b) take board as a 64-char string; c) board[8*row_2+col_2] := board[8*row_1+col_1]; board[8*row_1+col_1] := ' '; print board. This is trivial compared to any good golf question. (Note that the hot questions at the moment are neither golf questions nor good questions). \$\endgroup\$ Dec 30 '13 at 12:14
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$
    – user58826
    Jun 9 '17 at 15:40
3
\$\begingroup\$

Black Box

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

The game

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

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

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

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

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

Input and output

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

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

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

Your output has to be terminated by a newline character.

Examples

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

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

If the input were

cf
D-
Em
HH
Co

then the output should be

kb
kg
nd
pg

but if the input were only

Em
HH

then the output might be for example

K

Scoring

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

\$\endgroup\$
3
\$\begingroup\$

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

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

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

Character set definitions used:

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

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

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

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

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


Example answer (C)

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

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


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

\$\endgroup\$
3
\$\begingroup\$

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

Roman Calculator

Create a basic calculator for Roman numerals.

Requirements

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

For you to decide

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

Extra Credit

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

Sample input/output

XIX + LXXX                 (19+80)
XCIX

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

The shortest code wins.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ You might want to be explicit about which variants of Roman numerals need to be supported. For example, do I have to understand IV as 4, or can I require that it be written as IIII? And what about, say, writing 8 as IIX instead of VIII, 19 as IXX or XVIV instead of XIX, or 99 as IC instead of XCIX? (All these variants have, AFAIK, been used classically.) \$\endgroup\$ Feb 9 '14 at 22:36
  • \$\begingroup\$ @IlmariKaronen thanks. I modified the question to be slightly more specific about that. \$\endgroup\$
    – Danny
    Feb 10 '14 at 14:09
  • 1
    \$\begingroup\$ I think that using IV, IX, IC, XC, etc. should be alright, but only allow one prefix. Also, 19 should be written XIX, not IXX. One other thing, can we assume that the operators will be separated by a space, or no? \$\endgroup\$
    – user10766
    Feb 12 '14 at 0:32
  • 1
    \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$
    – user58826
    Jun 9 '17 at 16:06
  • \$\begingroup\$ 1. I don't need to handle I/III but need to handle I/III+II/III? 2. For the extra can I output maybe [V] for 5000? \$\endgroup\$
    – l4m2
    Apr 12 '18 at 15:05
  • \$\begingroup\$ @programmer5000 it was posted to main awhile ago. codegolf.stackexchange.com/questions/20670/… \$\endgroup\$
    – Danny
    Apr 26 '18 at 11:58
3
\$\begingroup\$

4 and 20 baked in a π

While some might describe π as a string of seemingly random numbers, one can also look at it in a way similar to a monkey with a typewriter. Eventually, it should calculate out to something more interesting. For example, the sequence 1337 shows up 4,814 places to the right of the decimal. At 700,731 places right of the decimal, you'll find the sequence 160151, which is "pi" represented as ASCII (although you'll find a 'pointer' to it much faster, as the sequence 700731 begins at 29,830 digits to the right).

So, your task is to make a program to find things in π. Your program will accept a positive integer and output the number of places right of the decimal point that number appears. To keep the run times down, input can be limited to numbers in the range of 0 to 1000 (without leading zeros).

Example: Using 415 as the input, the output should be 2:

3.14159
   ^

Rules:

  • You can not use any precalculated values of π, including language constants, built in functions that return π or digits of π, or any resource outside the code itself (such as files or websites).
  • You can not use any trig functions to calculate π.

Bonus points if you find the sequence 072 101 108 108 111 044 032 087 111 114 108 100 033.

This is code golf, so lowest score wins.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ It's not clear to me whether you require answers to support leading zeroes. Also: program, named function or snippet? And how indexed? (Giving 415 as a test case would be a good way to answer the last question) \$\endgroup\$ Mar 11 '14 at 6:58
  • 3
    \$\begingroup\$ Isn't this just Calculate 500 digits of pi with a search function tagged on at the end? By the way, your bonus points are quite safe — even if you searched a trillion trillion trillion digits of pi, your chance of finding an arbitrary 39-digit sequence would still be less than 0.1%. \$\endgroup\$
    – r3mainer
    Mar 11 '14 at 14:59
  • \$\begingroup\$ Edited to clarify leading zeros and indexing. @squeamishossifrage - Yes and no. The number of digits to find the answer depends on the input, which both limits the choice of algorithm to generate the search space and gives more ample room to golf the integration of the search function. The worst case is under 10000 digits for n between 0 and 1000. I suppose I could put in a time limit of a couple minutes and expand the range of n to 10000 (worst case is just under 390k), but that seems obnoxious. Thoughts? \$\endgroup\$
    – Comintern
    Mar 11 '14 at 17:20
  • 1
    \$\begingroup\$ @AlexA. - Not a drug reference. \$\endgroup\$
    – Comintern
    Apr 1 '15 at 22:34
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9 '17 at 16:15
3
\$\begingroup\$

Create a calendar

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

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

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

Rules:

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

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

\$\endgroup\$
9
  • 1
    \$\begingroup\$ "bandwidth is expensive" <sup>[citation needed]</sup> \$\endgroup\$ Mar 22 '14 at 5:27
  • 1
    \$\begingroup\$ Seems rather close to Output: Calendar Month \$\endgroup\$ Mar 22 '14 at 5:33
  • \$\begingroup\$ Who decides what counts as bootstrapping code? It seems odd to arbitrarily exclude code like that, and the examples you gave can be golfed a lot: they're more or less equivalent to main(){ and <? respectively. \$\endgroup\$ Mar 24 '14 at 20:49
  • \$\begingroup\$ @WanderNauta Bootstrapping code is the code that's essentiell to get a working noop program. \$\endgroup\$
    – TimWolla
    Mar 24 '14 at 21:00
  • \$\begingroup\$ @TimWolla That definition won't fly. A zero-byte file is a working noop PHP script, for example. \$\endgroup\$ Mar 24 '14 at 21:01
  • 1
    \$\begingroup\$ @WanderNauta A zero byte file is a working noop in every language. \$\endgroup\$
    – TimWolla
    Mar 24 '14 at 22:12
  • \$\begingroup\$ So what's bootstrapping code then? :) \$\endgroup\$ Mar 24 '14 at 22:53
  • 1
    \$\begingroup\$ for the limit I'd say code-shuffleboard or restricted-source \$\endgroup\$
    – Einacio
    Mar 26 '14 at 15:57
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$
    – user58826
    Jun 9 '17 at 16:28
3
\$\begingroup\$

ASCII ART edge detection

As the title says, I was thinking to contest in which one must detect edges of an ASCII art.

The code should accept a B/W ASCII art as input. A B/W ASCII art is defined as (by me) an ASCII art with only one kind of non-white-spaces character (in our case: an asteriks *). And as output produce a standard ASCII art (all ASCII characters are accepted) which should remember the contourn of the first.

The purpose of using more than one character in the output is to make some edges ssmoother. For instance, one could let this input

     *** 
   ****
 ******
******
****** 
 ******
   ****
     ***

could became:

      ___
    _/   ) 
  _/    /
 /      |
|      /
|      \
 \      |
  `\     |
     \___)

The input \n separated string as input. Each line has a maximum of 80 characters. The number of rows is not specified.

I'd put it as a popularity-contest since, beside my simple code, I'd like to see more "round" edge detections which use more than one character in smooth edges.

Also, I don't want to tag it as code-golf since I'm quite sure one can do this job using aplay (with ASCII art renderer) and command line GIMP (to apply edge detection).

As a popularity contest, there are no strict rules on how the output should be..just use your fantasy!

This is my sample program:

import fileinput as f
import re as r
import copy as c
a,s,p='*',' ','+'
def read(n):
    s=[list(' '*n)]
    for l in f.input():
        if(len(l)>n):l=l[:n]
        k=list(r.sub('[^ ^\%c]'%a,'',' '+l+' '))
        s.append(k+[' ']*(n-len(k)))
    s.append([' ']*n)
    return s
def np(s):
    s=c.deepcopy(s)
    for l in s[1:-1]:
        for w in l[1:-1]: print(w,end='')
        print()
def grow(i):
    o=c.deepcopy(i)
    for x in range(1,len(o)-1):
        for y in range(1,len(o[x])-1):
            if(i[x][y]==a): o[x-1][y-1]=o[x-1][y+1]=o[x-1][y]=o[x+1][y]=o[x+1][y-1]=o[x+1][y+1]=o[x][y+1]=o[x][y-1]=a

    return o
def diff(i,o):
    c=[]
    for x in range(0,len(i)):
        l=[]
        for y in range(0,len(i[x])):
            if(i[x][y]==a and o[x][y]==s): l.append(p)
            else: l.append(s)
        c.append(l)
    return c
I=read(80)
np(diff(grow(I),I))

Here below I put both input of the programs. It is an 80x70 ASCII ART. It means it has 70 lines of 80 characters, each separated by \n.

                                              *************
                                          *****          *****                   
                                     ******                  ***                 
                                    ***                         ****             
                             *********                             **            
                          ***********                               **           
                     ******   *******                                **          
                 *****       *******      ***                         **         
              ****          ********     *****                          *        
             **            *********     *****                    *****  *       
           ***            *********     *******                  ******  **      
          **             **********     *******                  ******   **     
         **              **********    *******                  ********   *     
        *               ***********   ******                    ********   *     
       **              ************   *****                     ********    *    
       *               ************    ***                       ********   *    
      *               *************                               ******    *    
     *                *************                                 ***     *    
    **                *************                                         *    
    *                **************                                         *    
   **                *************                                         **    
   *                 *************                                         **    
  **                *************                                          ***   
 ***                *************                                          ****  
 **                 ************                                           ****  
 **                *************                                           ****  
 **                *************           *****                           ****  
 **                *************          **   **          **              ****  
 **                 ************          *     *         ** **            ****  
 *                  ************          **   **        **   **           ****  
 *                  *************        *******         **   ***          ****  
 *                  ************          *****           *******          ****  
 *                   ************         ***               *****          ****  
**     *             *************                          ****          *****  
**    ***            **************                                      *****   
*    *****            *************                                     ******   
** *******             **************                                  *******   
**********             ***************              *                *********   
**********              *****************          ***             ***********   
***********              *******************                    **************   
***********               **********************            ******************   
************              *****************     **     ***********************   
*************             ******************      ****     *******************   
**************            ******************              ********************   
****************           ******************              *******************   
***************           *******************              *******************   
****************           ******************              ******************    
******************         ******************             *******************    
*******************         *****************             *******************    
*********************      ******************           ********************     
*********************************************          *********************     
**********************************************       ***********************     
************************     *****************      ************************     
 **********************       ******************* **************************     
 *********************        *********************************************      
 *********************        ****************************  ***************      
 ********************         **************************    ***************      
 ********************         *********************         ***************      
 *******************          ********************         ****************      
 ******************           *****************            ****************      
 *****************             ****************            ***************       
 *****************             ****************            ***************       
 *****************             *****************           ***************       
  ****************             *****************           ***************       
   **************              ******************          ***************       
                                 ****************          ****************      
                                  **************            ***************      
                                                             **************      
                                                              ************       

A possible output could be:

                                         +++++             ++++
                                    ++++++     ++++++++++     +++
                                   ++      +++++        +++++   +++++
                            ++++++++   +++++                ++++    ++
                         ++++         ++                       ++++  ++
                    ++++++           ++                           ++  ++
                +++++      +++       +   +++++                     ++  ++
             ++++     +++++++       ++  ++   ++                     ++  ++
            ++    +++++   ++        +   +     +                  +++++++ ++
          +++  ++++      ++         +  ++     ++                ++     ++ ++
         ++   ++        ++         ++  +       +                +      ++  ++
        ++  +++         +          +  ++       +               ++      +++  +
       ++  ++          ++          + ++       ++               +        +++ +
      ++ +++          ++           + +      +++                +        + + ++
      +  +            +            + +     ++                  +        ++++ +
     ++ ++           ++            + ++   ++                   ++        + + +
    ++ ++            +             +  +++++                     ++      ++ + +
   ++ ++             +             +                             +++   ++  + +
   +  +             ++             +                               +++++   + +
  ++ ++             +              +                                      ++ +
  +  +              +             ++                                      +  +
 ++ ++             ++             +                                       +  ++
++  +              +             ++                                       +   ++
+   +              +             +                                        +    +
+  ++             ++            ++                                        +    +
+  +              +             +         +++++++                         +    +
+  +              +             +        ++     ++        ++++            +    +
+  +              +             +        +  +++  +       ++  +++          +    +
+  +              ++            +        + ++ ++ +      ++  +  ++         +    +
+ ++               +            ++      ++  +++  +      +  +++  ++        +    +
+ +                +             +      +       ++      +  +++   +        +    +
+ +                +            ++      ++     ++       ++       +        +    +
+ +   +++          ++            ++      +   +++         +++     +       ++    +
  +  ++ ++          +             ++     +++++             +    ++      ++     +
  + ++   ++         +              +                       ++++++      ++     ++
 ++++     +         ++             +++                                ++      +
  +       +          ++              ++            +++              +++       +
          +           +               ++++        ++ ++           +++         +
          ++          ++                 ++++     +   +        ++++           +
           +           ++                   +++++ +++++    +++++              +
           ++           ++                      +++   ++++++                  +
            ++           +                 +++++  +++++                       +
             ++          +                  +  +++    +++++                   +
              +++        +                  ++   ++++++  +                    +
                +        ++                  +           ++                   +
               ++        +                   +            +                   +
                +++      ++                  +           ++                  ++
                  ++      +                  +           +                   +
                   +++    ++                 +         +++                   +
                     ++++++                  +        ++                    ++
                                             ++     +++                     +
                                              +    ++                       +
                        +++++                 ++++++                        +
+                      ++   ++                   +                          +
+                     ++     +                                             ++
+                     +      +                            ++               +
+                    ++      +                          ++++               +
+                    +       +                     ++++++ ++               +
+                   ++       +                    ++      +                +
+                  ++        +                 ++++       +                +
+                 ++         ++                +          +               ++
+                 +           +                ++         +               +
+                 +           +                 +         +               +
++                +           +                 ++        +               +
 ++              ++           +                  +        +               ++
  ++++++++++++++++            +++                +        +                +
                                ++              ++        ++               +
                                 ++++++++++++++++          ++              +
                                                            ++            ++
                                                             ++++++++++++++

This is also the output produced by the script above. Of course it is not the best output and I'm sure one can easily produce a smoother one.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ It would be useful to be more precise about which characters should be non-blank in the output: characters which were non-blank in the input but adjacent to blanks, or characters which were blank in the input but adjacent to non-blanks? \$\endgroup\$ Apr 4 '14 at 9:50
  • \$\begingroup\$ Thanks for pointing. I re-written the phrase in the answer. You can use every ASCII character in the output (as usual ASCII art). E.g. I used only + symbol, but one could makes round edges using symbols like \ or / etc.. \$\endgroup\$ Apr 4 '14 at 9:55
  • \$\begingroup\$ edited again... \$\endgroup\$ Apr 4 '14 at 10:09
  • \$\begingroup\$ Can you define the input that will be used by all the participants? It's necessary to have only one input to compare the outputs of the different answers. The first example is too simple and the last one is too long. So I suggest to use something between these 2 examples. \$\endgroup\$
    – A.L
    Apr 4 '14 at 17:29
  • \$\begingroup\$ Thanks, I chosen a cute panda as input. \$\endgroup\$ Apr 6 '14 at 8:09
  • 1
    \$\begingroup\$ one could let this input (…) could became → try something like "this input (…) could become" outpuit → output \$\endgroup\$ Apr 7 '14 at 13:31
  • \$\begingroup\$ I edited it now, so do you people thinks it is a good question? \$\endgroup\$ Apr 9 '14 at 17:15
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9 '17 at 16:32
  • \$\begingroup\$ Hi @programmer5000 , I already asked such a question. Do you mean to re-use it again? See: codegolf.stackexchange.com/questions/26139/… \$\endgroup\$ Jun 12 '17 at 13:39
3
\$\begingroup\$

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

Maths Trade Calculator

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

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

Input

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

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

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

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

Output

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

1->3->1
2

Participants for which no valid trade is possible are omitted.

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

Trade rules

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

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

Some more example inputs and possible outputs

1

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

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

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

2

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

0

3

1:5,9
5:1
9:1

1->5->1
2

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

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

\$\endgroup\$
5
  • \$\begingroup\$ "can be followed by a new-line or not, whatever the coder prefers." How flexible is this? For instance, can I use trailing commas, like 1:2,4,7, if it makes my code shorter? \$\endgroup\$ May 2 '14 at 17:28
  • 2
    \$\begingroup\$ Will the participants always be numbered 1 to n and their input lines provided in order? If so, state it. If not, include a test case which fails if an implementation decides to ignore everything before the : in each input line. \$\endgroup\$ May 5 '14 at 10:02
  • \$\begingroup\$ @m.buettner I would say a trailing comma is not acceptable, on the end of any line, or the end of the input/output. \$\endgroup\$
    – Johno
    May 6 '14 at 8:55
  • \$\begingroup\$ @PeterTaylor Good tip. I'll correct the question to state that you can't assume that the numbers will be 1 to n, in order. \$\endgroup\$
    – Johno
    May 6 '14 at 8:57
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9 '17 at 16:39
1
8 9
10
11 12
122

You must log in to answer this question.

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