459
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

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

2568 Answers 2568

0
\$\begingroup\$

Forecast Romantic Dates

Sort of inspired by this.

A Romantic date is a date that, when the year, month and day are converted to Roman Numerals the individual values contain no more than two symbols. For example, in YY-MM-DD format: the Romantic date 20-04-15 would become XX-IV-XV.

For the purpose of this challenge, years will only be tracked by the two least significant digits of the year, as otherwise the last Romantic date was in the 15th century. In addition, they wouldn't add much to the challenge as the omissions of the leap year every 400 years is irrelevant, as February the 29th is not a Romantic date.

Romantic dates

For your convenience, here is a list of all of the two digit numbers that can be represented with two or fewer symbols in Roman numerals:

[1, 2, 4, 5, 6, 9, 10, 11, 15, 20, 40, 50, 51, 55, 60]

These were determined using the "standard method" that negative groups would only be used with the symbols that are powers of ten and only on the values that are five or ten times that symbol's value. So I only combines with V and X for example.

Dates which include only numbers from this list are Romantic dates. For the purpose of this challenge, assume an ideal Western calendar: no dates are ever skipped or repeated, 12 months per year, and more than 20 days per month. Assume there is no year, month or day zero (i.e. year 99 loops to 1 not to 0).

Task

Given a date as input, output that date if it is Romantic, or output the next Romantic date.

Input and Output

You may accept input in any consistent ordering of year, month and day with any consistent separator. You may specify if the input should have the numbers padded to be two digits. If the numbers are padded, you may choose to have no separator. Your output must have the same form as your input.

Test Cases

The following test cases are all in the format YY MM DD, with no padding.

1 1 1 => 1 1 1
20 4 3 => 20 4 4
15 7 1 => 15 9 1
51 9 7 => 51 9 9
70 9 7 => 1 1 1
20 6 24 => 20 9 1
47 12 1 => 50 1 1
60 11 24 => 1 1 1

Here is the script that I used to generate these.

Sandbox

Did I miss any Romantic numbers? I just did that by hand.

Allow unary? I'm unsure about this because it sort of violates the reasoning behind Romantic dates for the values to have >2 symbols...

Should I explain more about parts of dates that are not useful? For example, the length of the months is entirely irrelevant as the later days are all skipped. My concern is that the current one feels clunky already

Should I allow both outputting the input if the date is already Romantic or the strictly next Romantic date (as long as it is consistent)? There doesn't seem to be much different, but I don't know if that'd be too broad? Personally leading towards allowing it.

I'm also somewhat tempted to make use of the silly title a bit more, but I'm not sure if that'd be going overboard.

Too boring / compression based? I've particularly been trying to think of a way for fewer results to wrap back around to 1.

\$\endgroup\$
  • \$\begingroup\$ That rule should be spelt out explicitly in the question, because although some people insist on it it's a modern innovation. There are actual Roman inscriptions which do use e.g. IC. \$\endgroup\$ – Peter Taylor Jun 24 '16 at 21:05
  • \$\begingroup\$ @PeterTaylor You're right, I originally left out the reasoning because I thought it might clutter up the spec, but I realise now I just left that comment undeleted to prevent people from asking the same question. I don't have time right now but I'll edit it in once I get a chance. Also, I figured it was better with this rule because I thought say VL was rather unintuitive, does that make sense or should I be more laissez-faire about it? \$\endgroup\$ – FryAmTheEggman Jun 24 '16 at 22:04
0
\$\begingroup\$

Stacks and Stacks and Stacks...

Write a program that, with the input as n, finds the first n-gonal and n-gonal pyramid number that is NOT 1.

n is guaranteed to be larger than or equal to 3.

Examples:

  • n = 3: 10
  • n = 4: 4900
  • n = 2: The output can be nothing, False, or anything that you want, just as long as it can be distinguished from an actual output.

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

Bonus:

  • If your code output both the name of the n-gon and the number: You get a big fat -50% off of your byte count (see below for examples).
    • n = 4: Square 4900
    • n = 3: Triangle 10
    • n = 5: Pentagon ??? (the ??? is a placeholder because I have no idea what the number is)

Meta:

  • Is the bonus a good idea?
\$\endgroup\$
  • \$\begingroup\$ I don't think the bonus is a good idea because 1) the name compression takes away from the original challenge and likely isn't worth it and 2) you haven't defined the naming scheme (e.g. 12-gon vs dodecagon) \$\endgroup\$ – Sp3000 Jun 26 '16 at 7:10
  • \$\begingroup\$ @Sp3000 Ah, OK. I really want to incorporate the use of strings in the challenge, but if the idea sucks, then I'll scrap it. Any further suggestions? \$\endgroup\$ – Qwerp-Derp Jun 26 '16 at 7:12
  • 2
    \$\begingroup\$ Adding strings just makes it feel like squeezing two challenges into one, unfortunately. I'd recommend posting the shape names as a separate challenge, but I see we have this challenge. As for suggestions, maybe 1) remove the part about n = 2, since you already say n is guaranteed to be at least 3 and 2) maybe make it explicit that the output should be both n-gonal and n-gonal pyramidal (and maybe explain, say, that 10 is the 4th triangular and 3rd triangular pyramid number) \$\endgroup\$ – Sp3000 Jun 26 '16 at 7:16
  • \$\begingroup\$ Hmm my other problem is - what happens if there's no solution for a given n? Note the only reason I'm asking is because the number of solutions for any n could be finite, e.g. A027568. (6 is 946, 8 is 1045, 10 is 175 and 11 is 23725 I believe) \$\endgroup\$ – Sp3000 Jun 26 '16 at 9:28
  • \$\begingroup\$ Yeah, that could be a problem... maybe a time limit? Or maybe check numbers up to a given range. \$\endgroup\$ – Qwerp-Derp Jun 28 '16 at 6:50
  • \$\begingroup\$ One alternative could be to allow solutions to potentially infinite loop/hit memory or recursion errors in the case of no solution/large solution. Numerical limit to check up to could work too, that'd probably be better than a time limit (since it reduces a dependency) \$\endgroup\$ – Sp3000 Jun 28 '16 at 9:02
  • \$\begingroup\$ @Sp3000 I would probably go with the numerical limit/memory limit thing, whichever comes first. But what about golfing/esoteric languages? There might not necessarily be a memory/numerical bound for those. \$\endgroup\$ – Qwerp-Derp Jun 29 '16 at 9:04
0
\$\begingroup\$

Pyth Meta-Golf Golf Battery

(now that's a name, isn't it?)

The Challenge

Write a program in a language of your choice that takes an input of code in the same language and outputs a code that does the same thing in Pyth (though not necessarily the shortest code).

Rules

Given the test battery set below, you should try to find the best way to minimize your score with the following rules:

  • You must minimize the source code of the submission.
    • You may not used compressed versions of the input source for each test; the Pyth code must be output procedurally.
    • The code must theoretically do the same conversion for any input code, not necessarily just these test cases.
  • You must minimize the input code of each test.
    • If an input is shown to be shortenable by without non-standard libraries of the submitted language, you must change it immediately to the shorter answer. If your answer does not support this change, then you must change your answer to accommodate.
  • You may not submit answers written in Pyth.

Scoring is done with the following equation:

(source code)*((Pyth src out, test 1)/(input src in, test 1)+(same for test 2)+...)

Objectives of each test

Test 1:

Output the string "Hello, world!".

Test 2:

Given an integer input, multiply that input by three and output it.

Test 3:

Quine. (must be a valid quine in the submitted language and in Pyth)

Test 4:

Produce infinite output.

Test 5:

Cat program.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not a Pyth expert, but I strongly suspect that what this asks is impossible in many languages. E.g. I understand that Python's multi-threading support is extremely limited. Even if true impossibility is not an option, answers in many languages won't fit inside the 30000-character limit. E.g. I don't think the grammar for Java fits inside the limit, let alone a lexer and parser. \$\endgroup\$ – Peter Taylor Jun 27 '16 at 9:56
  • 1
    \$\begingroup\$ I agree with Peter, that this seems like unless you use only trivial languages it probably won't be possible to answer. The scoring would also make this confusing: to make sure a solution is correct one would have to not only test 10 programs, you would also have to golf 5 programs. Further, there is a bit of a problem in Pyth's $ operator, which runs literal Python, which means you should probably ban Python as well. I'm not really sure of how to turn this into a good question, too heavily restricting the type of program seems to be the only way, but it also seems to defeat the purpose. \$\endgroup\$ – FryAmTheEggman Jun 27 '16 at 13:09
0
\$\begingroup\$

Don't even think about non-42-related numbers!


Introduction and Credit

We all love our Answer to the Ultimate Question of Life, the Universe, and Everything which, of course is 42. So let's take this unworthy Fibonacci-Sequence thingy and adapt it to be worthy of 42!

Specification

Input

The input will be a positive integer.

Output

The output will be either true or false.

What to do?

Your task is to implement the predicate that the number under consideration is an element of the generalized Fibonacci-Sequence given by:

a_1 = 14
a_2 = 42
a_n = 41 * a_{n-1} + 43 * a_{n-2}

Where 42 is the ultimate answer, 41 and 43 are the primes next to it and 14 is the preceding catalan number.

Potential corner cases

The number will always be greater than zero. Your program must pass all (32-bit) test vectors below.

Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

Test Vectors

14 -> true
42 -> true
2324 -> true
4080622 -> true
97090 -> true
171480372 -> true
7 -> false
1 -> false
41 -> false
43 -> false
\$\endgroup\$
  • \$\begingroup\$ a_3 is already outside the range of 8-bit unsigned integers, a_6 is outside the range of 32-bit signed integers, and a_11 is outside the range of 64-bit signed integers. It would be worth addressing this issue and at least ensuring that languages which are inherently 8-bit can't just special-case the two values which they can handle. \$\endgroup\$ – Peter Taylor Jun 25 '16 at 21:58
  • \$\begingroup\$ @PeterTaylor I'm unsure how to formulate this without disqualifying legitimate approaches. Would saying "your program must pass all test vectors" (with 32-bit test vectors) also be considered OK for most people? \$\endgroup\$ – SEJPM Jun 25 '16 at 22:16
  • \$\begingroup\$ I feel like this is too much two separate challenges: one to test for membership in the sequence, and the other to takeWhile on a condition. I also suspect the sequence has a direct arithmetic membership test like the one where n is a Fibonacci number exactly if either 5*n*n+4 or 5*n*n-4 is a square. \$\endgroup\$ – xnor Jun 25 '16 at 23:27
  • \$\begingroup\$ What is takewhile? \$\endgroup\$ – Qwerp-Derp Jun 26 '16 at 7:02
  • \$\begingroup\$ @xnor, I originally only wanted to do the takeWhile, but needed a (mediumly) complex, interesting predicate, so I came up with this one. Of course I'm open to suggestion for more suitable interesting predicates. \$\endgroup\$ – SEJPM Jun 26 '16 at 10:18
  • \$\begingroup\$ @DerpfacePython, the higher-order functionality described in the second paragraph of "what to do?" is also called takewhile, I've clarified this though. \$\endgroup\$ – SEJPM Jun 26 '16 at 10:21
  • \$\begingroup\$ @SEJPM I think the other way -- to do a challenge about takeWhile, make the predicate as simple possible. Beware chameleon challenges and needless fluff. One clean condition would be integers being positive. \$\endgroup\$ – xnor Jun 26 '16 at 10:56
0
\$\begingroup\$

Compute the mincut of a graph

Given a graph, compute a division of the graph such that the edges stranded between the cut.

hayo mouseover readers; leave a comment if you see this!

Red line: a cut

Green line: a mincut

Input

The first line will contain the number of nodes. The rest of the lines will contain pairs of positive integer IDs separated by spaces showing connectedness between the nodes with those IDs. Here's an example; for a graph where 1 is connected to 2 and 2 is connected to 3:

3
1 2
2 3
  • You may assume that the nodes are numbered consecutively from one to the number of nodes.
  • However, you may not assume that the list of pairs of nodes is in any specific order.

Output

Simply output a comma-separated list of the IDs of the nodes of one of subgraphs created by the cut.

Additional Rules!

  • You cannot implement brute-force search. Other than that, feel free to use Karger's Algorithm* or another algorithm. Remember that Karger's algorithm is likely the easiest to implement.
  • Notice: you must run Karger's algorithm at least this many times to ensure a low chance of failure and a low chance of failure

*Karger's algorithm

For your convenience, I've included a simple description of Karger's algorithm.

  1. find two adjacent nodes and merge them into one node (so that all nodes that where connected to the original two nodes are connected to the new node), concatenating the labels
  2. repeat step one until there are only two nodes
  3. the result is any label of one of the nodes
  4. repeat steps 1-3 at least this many times to ensure a low probability of failure, and choose the result that occurs the most often
\$\endgroup\$
  • 1
    \$\begingroup\$ 1. Wouldn't it be better to take the graph as an adjacency matrix or list? 2. Your description of the minimum cut is somewhat confusing. 3. Karger's algorithm is probabilistic, which isn't allowed by our defaults (I don't think). Allowing probabilistic algorithms opens up a whole can of worms (for instance I could write a program that just returns a random cut) -- you should probably make it so that the algorithm must return the minimum cut two-thirds of the time or something similar if you want to allow them. \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:07
  • \$\begingroup\$ @quartata 1. it's an adjacency list 2. yeah I need help with that 3. I made sure you had to repeat it insert some math equation here amount of times \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jul 5 '16 at 0:13
  • \$\begingroup\$ Sorry I misunderstood the input. \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:14
  • \$\begingroup\$ Generally adjacency lists are done like [node1, connected_node1, connected_node2, ...] and not in pairs like you have it; this is more flexible and you don't have to specify the number of nodes (it is just the length of the input list) \$\endgroup\$ – a spaghetto Jul 5 '16 at 0:35
  • 2
    \$\begingroup\$ "You cannot implement brute-force search" is too vague. What about a basically brute force search that shortcuts some obviously wrong possibilities? I think what you want is a running time bound. \$\endgroup\$ – xnor Jul 5 '16 at 1:55
  • 1
    \$\begingroup\$ 1. The I/O description seems to assume that all answers will be programs taking input on stdin and writing output to stdout, but our defaults are more flexible. In particular, by default we allow answers to be functions which take arrays and return arrays. Comma-separating is also IMO unnecessarily constrained, especially as the input isn't comma-separated. \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:51
  • 1
    \$\begingroup\$ 2. "Feel free to use Karger's algorithm or another algorithm". There's an implicit licence here to use another non-deterministic algorithm, but although you give an explicit iteration count for Karger's algorithm you don't for e.g. randomised Kruskal's algorithm, which it's based on. 3. Besides which, in general I don't think that questions should tell people which algorithm to use. Specify the task and constraints (e.g. "Randomised algorithms are allowed, but must find the correct answer with probability at least foo. All answers must be polynomial-time"). \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:54
  • \$\begingroup\$ 4. But if you're going to include an algorithm description, be careful to get it right. Karger's algorithm is randomised, but in the description given there's no mention of where the random selection occurs or of what uniformity constraints are required to get the desired behaviour. \$\endgroup\$ – Peter Taylor Jul 5 '16 at 7:55
  • 1
    \$\begingroup\$ Food for thought: outputting the value of the min cut instead might lend to more approaches. Also, any rules on min cut/max flow/possibly other optimisation builtins? \$\endgroup\$ – Sp3000 Jul 5 '16 at 10:34
  • \$\begingroup\$ I'm going to add a story to this soon. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jul 5 '16 at 13:55
0
\$\begingroup\$

Generate a random Vietnamese syllable

tags:


The Vietnamese syllable space is interesting, because it is huge.

TODO: Describe the space and why it is interesting.

Here's how such syllables are made:

The onset matches the regex ^([bcdđghklmnprstvx]|qu|[cgkpt]h|ng|tr)$

The vowel is one of the following massive list:

a à a' ã á a.
â â` â' â~ â´ â.
a. ă` ă' ă~ ă´ ă.
e è e' e~ é e.
ê ê` ê' ê~ ê´ ê.
i ì i' ĩ í i. ia iê
o ò o' õ ó o. oa oă oe
ô ô` ô' ô~ ô´ ô.
o' ò' o" õ' ó' o'.
u ù u' ũ ú u. ua uâ uê ui uô uo' uy
u' ù' u" ũ' ú' u'. u'a u'o'
y y` y' y~ ý y. ya yê

The coda matches the regex ^([iouycptmn]|ch|ng|nh)$

(thanks Peter Taylor!)

The onset, vowel and coda are concatenated to make the result syllable.

Objective

The objective is to generate random Vietnamese syllables. Your program has to take no input and as output include only the syllable, with an optional trailing new line.

Clarifications

  • Each syllable must be generated with a non zero probability.

I think it's unclear. Contributions are so much welcome.

\$\endgroup\$
  • \$\begingroup\$ 1. I'm not sure what you mean by can be with. 2. You don't mention randomness anywhere excwpt the clarification. 3. Object should probably be Objective. \$\endgroup\$ – Dennis Jul 3 '16 at 18:44
  • \$\begingroup\$ 1. c can also be with h means that h can follow c as the 2nd stage letter in the syllable. 2. Where should I also mention it? 3. Ah k :) \$\endgroup\$ – user48538 Jul 3 '16 at 18:46
  • \$\begingroup\$ If I'm reading this correcting then it can be vastly simplified by saying that the onset matches the regex ^([bcdđghklmnprstvx]|qu|[cgkpt]h|ng|tr)$, the vowel is one of a massive set of options (I don't see any benefit to splitting that into "stage 2" and "stage 3"), and the coda matches the regex ^([iouycptmn]|ch|ng|nh)$ \$\endgroup\$ – Peter Taylor Jul 4 '16 at 16:36
0
\$\begingroup\$

Let's play some Briscola

Briscola is an Italian game, played with a deck of 40 cards, divided in 4 suits - coins (denari - D), swords (spade - S), cups (coppe - C) and clubs (bastoni - B).

The values on the cards range numerically from one through seven, plus 3 special cards - knave (11), knight (12) and king (13).

Gameplay:

After the deck is shuffled, each player is dealt three cards. The next card is placed face up on the playing surface, and the remaining deck is placed face down. This card is the Briscola, and represents the trump suit for the game.

First player starts by playing one card face up on the playing surface. Each player subsequently plays a card in turn, until all players have played one card.

The winner of that hand is determined as follows: If any briscola (trump) has been played, the player who played the highest valued trump wins, else the player who played the highest card of the lead suit (suit of the first card played) wins.

Ranking

Briscola has a special type of ranking:

1   ace
3   three
13  king
12  knight
11  knave
7
6
5
4
2

Rules:

Standard loopholes apply.

Input:

As an input, you must accept 5 values (cards), in a reasonable format, for example:

briscola (trump card), 1. card, 2. card, 3. card, 4.card

Output:

You must output the winning card

Example input and output:

4S 7D 12B 13B 2S -> 2S
5D 1D 5D 12S 3C -> 1D
3B 2C 4S 5S 7D -> 2C
12D 3S 11B 1B 7S -> 3S
\$\endgroup\$
  • \$\begingroup\$ As mentioned in chat, I think this is probably a duplicate of this challenge. Just adding so other people don't have to go looking. \$\endgroup\$ – FryAmTheEggman Jul 6 '16 at 21:15
0
\$\begingroup\$

nth number that multiplies k equals its reverse

Tags: ,


It's quite simple, given n and k, output the nth number such that, if the number is multiplied by k and its digits reversed, it equals the original number. Both input and output are positive numbers.


The challenge originally is from Mego, posted on my broken challenge. Firstly, I used 4 instead of k, but based on my tests, only 1 and 4 values gives output, so I decided to put 4 instead of k, finally I put k back. But the challenge would be ruin with that putting "9"*(n-1) between 2178, so no loopholes will be permitted.

I just posted here for further discussions, suggestions and improvements.

\$\endgroup\$
  • \$\begingroup\$ Those numbers are positive right? \$\endgroup\$ – Fatalize Jul 6 '16 at 7:52
  • \$\begingroup\$ Please add some examples of expected outputs. \$\endgroup\$ – Fatalize Jul 6 '16 at 7:53
  • \$\begingroup\$ Also you might want to prevent people from hardcoding 2178 in any fashion in their code so that they have to compute the numbers, because it seems they all are of the form 21X...X78 where X...X is a series of nines (except for the first one, which is 0). \$\endgroup\$ – Fatalize Jul 6 '16 at 7:56
  • \$\begingroup\$ According to the community advises, I'm not allowed to prevent people use methods those work perfectly. \$\endgroup\$ – Ehsaan Jul 6 '16 at 8:23
  • \$\begingroup\$ Let's wait to see what others think. I personally don't think it's very interesting if people are allowed to hardcode the "format" of those numbers. \$\endgroup\$ – Fatalize Jul 6 '16 at 8:26
  • \$\begingroup\$ Me neither, I think the challenge isn't interesting at all. \$\endgroup\$ – Ehsaan Jul 6 '16 at 8:43
  • 1
    \$\begingroup\$ I think there's no good way to prevent hardcoding. Maybe making "4" were an input parameter as well would make solutions actually search for an answer? \$\endgroup\$ – xnor Jul 6 '16 at 9:01
  • \$\begingroup\$ @xnor You mean make 4 as k input? \$\endgroup\$ – Ehsaan Jul 6 '16 at 9:33
  • \$\begingroup\$ @Ehsaan Yes, exactly. \$\endgroup\$ – xnor Jul 7 '16 at 9:09
  • \$\begingroup\$ 9 works too: 1089 * 9 = 9801. \$\endgroup\$ – Neil Jul 10 '16 at 17:36
0
\$\begingroup\$

Write a program that can determine the median value of a read-only (static, const, immutable) sequence of unsorted numbers (array, list, stream) but minimises storage, without completely sacrificing speed.

The basic bracket is that if we copied all the values into a sorted list and then picked the middle one (or average of the middle pair), it would require storage of the whole sequence, so the storage would be 'n', and the performance would be O(n log n).

The score is the total cost of finding the median of 1 bn values, divided by 1 bn, at a cost of 8 per value stored, 1 per comparison or numerical operation and 1 per read, for the worst case. Thus if our insertion sort costs exactly n*log2(n), the for 1 bn values the total score is 1 for the read, 29.8 for the sort + 8 for the storage, for a total of 37.8.

If instead we skimmed the whole range to get the average (costing 1 for the read and 1 for the summation), we could then only store some portion of the range to sort; but then we would need a second pass to be sure that there were an equal number of values above and below this median (at the cost of another 2).

Lowest score wins, low-level languages (C/C++/D) only so that we can count the actual operations.

\$\endgroup\$
  • 3
    \$\begingroup\$ 1. It's not clear to me what counts as a "value stored" or a "read", and I think there are probably gray areas with "comparison or numerical operation" too. (E.g. in C is if (foo) a comparison?) 2. "The score is the total cost ... for the worst case." For any non-trivial algorithm, the full calculation of this score risks being longer than the code. There's a reason that complexity theorists deal with Landau notation rather than exact operation counts. \$\endgroup\$ – Peter Taylor Jul 7 '16 at 13:39
0
\$\begingroup\$

Reinventing the Modularization Wheel

In a language of your choice, implement a function or language construct that imports another file of the same language and executes it, making exported values from that file available to the calling file. If one already exists, you may not use it in your implementation.

For example, in Node, you would have to implement require() without using require(), even indirectly. In C, you would implement a function or construct equivalent to #include without using #include in the implementation. In Python, you would implement import. In client-side JavaScript, I suppose the closest equivalent would be <script src="..."></script>. So JavaScript implementations would be restricted to AJAX calls only, since <script> tags would not be allowed in the implementation.

This is not to say that you aren't allowed to use the built-in import at all, but only use them in the implementation. The intention here is to reinvent the wheel.

Requirements

  • Do not include the built-in modularization in any way in your import implementation.
  • Standard libraries only.
  • Byte-count includes the implementation itself, and any special changes that need to exist on the file being imported, if any.
  • The function or construct accepts a relative file path. As long as this is satisfied, you may extend the functionality of your modularization to have global imports, or even remote imports (like using a URL as input).
  • The imported file must have a construct for denoting values that must be exported. Only these values should be directly accessible from the calling file.
  • Using the built-in export function or construct of your language is acceptable, and if it is a built-in, it does not need to be included in your byte-count.
  • If your language does not have modularization, then implementing a mechanic for exporting should be included in your byte-count.
  • Document the usage of your function or construct.

This is and the shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Perhaps just restrict this to languages which support modularization to avoid loopholes \$\endgroup\$ – Downgoat Jul 7 '16 at 18:45
  • \$\begingroup\$ @Downgoat if people wanted to use a built-in for reading a plaintext file, and then use an eval()-like built-in to execute it in a way that exposes only denoted values (however you define that), I think it would be acceptable. What sort of loopholes do you foresee? \$\endgroup\$ – Patrick Roberts Jul 7 '16 at 18:49
0
\$\begingroup\$

Print a Pilcrow Scarecrow

Print the following ascii scarecrow using the pilcrow character

    ¶¶¶
   ¶¶¶¶¶
    ¶¶¶
    ¶¶¶  ¶
 ¶¶¶¶¶¶¶¶¶¶
    ¶¶¶
    ¶¶¶
   ¶ ¶ ¶
  ¶¶ ¶ ¶¶
     ¶
     ¶
¶¶¶¶¶¶¶¶¶¶¶
  • Padding must be with (space) and built with
  • Trailing padding is okay
  • Print to stdout
  • This is

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

It's time to unify!


Introduction

Wouldn't it be awesome if they whole world would be united and there would be no conflicts and disputes? Now while you can't unify nations, you certainly can unify expressions to resolve their unknown relation and conflicts.
Your mission is simple: Unify the world (of expressions)!
And of course, because you're lazy you want to do this with the least effort (read: code-length) possible.

Specification

Input

Your input will be a unification problem. You can format it however you want and need, as long as you don't encode additional information to what is given in the standard / example format. Encoding the number of arguments per function into the input is allowed but not mandatory, you can also just derive this from the input.

Example format:
Your first input will be list of function symbols, which is represented as a list of pairs of strings and non-negative integers.
Your second input will be a list of equalities (you may represent each as a string), which represent the unification problem. They will be represented as a list of strings as well. Anything which is not a parenthesis or an equality sign can be considered a variable. If the number of arguments is 0, parenthesis are omitted.

Example input: [("f",1),("g",2),("h",3),("a",0)], [x=f((g(a,y)),y=h(g(f(a),z),f(z),a)]

Output

The output is either some falsy value or something representing a list of equalities. It is allowed to use the empty list to indicate a falsy value.

What to do?

You need to unify the inputs you got. In the end there must only be variables on the left side of the equality-signs if the you didn't encounter an error. If you did you need to report it (-> false or empty list).

To do the unification, you can - but don't have to - use Martelli and Montanari's algorithm, which goes as follows:

E is always the (complete) set of equalities except the current one
x,y,z are variables, f,g,h are functions, t1,t2, ...,tn,s1,...,sn are arbitrary terms (compositions of functions and variables)
{x=x} E => E, e.g. if you encounter two equivalent variables, discard
{f(t1,...,tn)=f(s1,...,sn)} E => {t1=s1,t2=s2,...,tn=sn} E, e.g. if you encounter the same function on both sides, unify the arguments along with your rest
{f(t1,...,tn}=g(s1,...,sn)} E => Error, if the symbols are different, you can't succeed
{x=f(t1,...,tn)} E => {x=f(t1,...,tn)} E[x -> f(t1,...,tn)], e.g. if you see a variable equals a term, replace the variable with this term in all other expressions
{x=f(t1,...,tn)} E => Error, e.g. if any of the t1,..,tn contain x at some point
{f(t1,...,tn)=x} E => {x=f(t1,...,tn)} E, e.g. if you see a variable "naked" on the right side, swap the sides

Two step-by-step examples are provided below additionally to the test cases.

Corner Cases

You can get an empty list of function symbols, this means you have exclusively variables in the second input.
The input list of equalities will never be empty, your code does not need to handle this case.

Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

Test-cases

All these test cases use the functions [("a",0),("b",0),("f",1),("g",1),("h",2)]

[x=b] -> [x=b]
[a=x] -> [x=a]
[a=b] -> []
[y=f(x)] -> [y=f(x)] 
[x=f(x)] -> []
[f(x)=f(y)] -> [x=y] 
[f(x)=g(y)] -> []
[h(x,y)=h(a,b)] -> [x=a,y=b] 
[x=f(z),y=f(a),x=y] -> [x=f(a),y=f(a),z=a]
[h(x,f(y))=z,z=h(f(y),v)] -> [x=f(y),v=f(y),z=h(f(y),f(y))]

Step-By-Step Example

Example 1: Test Case 9
[x=f(z),y=f(a),x=y] => (replace x in third equation with first x)
[x=f(z),y=f(a),f(z)=y] => (replace y in third equation)
[x=f(z),y=f(a),f(z)=f(a)] => (remove f's in third equation)
[x=f(z),y=f(a),z=a] => (replace the z in the first expression)
[x=f(a),y=f(a),z=a]

Example 2:
Let [("f",2),("g",2),("a",0),("b",0)] be your functions
[f(g(a,x),g(y,b)=f(x,g(v,w)),f(x,g(v,w))=f(g(x,a),g(v,b))] => (remove f in second equation)
[f(g(a,x),g(y,b)=f(x,g(v,w)),x=g(x,a),g(v,w)=g(v,b))] => (function symbol missmatch in equation 2)
[]
\$\endgroup\$
0
\$\begingroup\$

create a golfed down regexp that matches all substrings

inspired by Determine the "Luck" of a string where I found a way to golf almost 30 bytes at once
(with a falling trick for that challenge, but I still like the idea).

The word "lucky" contains 15 different substrings:

  • lucky
  • luck, ucky
  • luc, uck, cky
  • lu, uc, ck, ky
  • l, u, c, k, y

Challenge
Create a program or function that, for a given string s, creates the shortest possible regexp using basic PCRE syntax that matches and returns all substrings of s and nothing else.

  • code needs not to be case sensible
  • basic syntax means: alternatives, quantifiers, grouping and custom character classes (e.g. [abc])
  • other features (assertions, backreferences, recursion etc.) may be used, but are not required to qualify
  • the result may include delimiters and modifiers

The result for lucky would be l?ucky?|l?uc?|c?ky?|l|c|y.


  • is the description sufficient?
  • the challenge not too easy, not too hard?
  • any other hints you might have?
  • I will add test cases that expose possible bugs (like silly and digdug)
  • not sure yet if I will go for shortest code yet
\$\endgroup\$
0
\$\begingroup\$

Write a Gopher Interpreter

This code golf challenge will task you with writing an interpreter for an esolang I created a while back called Gopher, Details on the language can be found Here

Pass Conditions

This challenge requires you to create an Interpreter (Or you could go a step ahead and create a Compile/Transpiler) however for the code to pass as correct it must meet the following criteria

  • Take in a single input being the Gopher Code
  • Output the result of the Interpreted code

  • Invalid code does not need to be handled, however you may do so if you wish

  • As this is code-golf the smallest byte size wins

Example Input and Output

Input:

&++<'×<&÷+<^-<<×-<#!+<$@-<&@<×-<@++<@<.!<=

Output:

Hello World
\$\endgroup\$
  • \$\begingroup\$ Thanks for using the Sandbox! Anyway, you should add the relevant information on Gopher to the body of this post, as if your github account/repo dies or is changed people still need to be able to answer this question. \$\endgroup\$ – FryAmTheEggman Jul 11 '16 at 17:15
0
\$\begingroup\$

Having had a look, it seems there isn't a challenge for "Given any date, output the day of the week". Is that a challenge worth having?

Something like

"Given an input date, in the form dd/mm/yyyy, output the day of the week"

Shortest code wins

What do we think? perhaps this already exists and I didn't find it.

\$\endgroup\$
  • 3
    \$\begingroup\$ Duplicate \$\endgroup\$ – AdmBorkBork Jul 11 '16 at 14:04
  • 2
    \$\begingroup\$ Glad I checked! \$\endgroup\$ – Matt Jul 11 '16 at 14:05
0
\$\begingroup\$

Golf your way from (inc|dec)rements to the basic math operations

Write five different functions or programs that do addition, subtraction, multiplication, division and modulo with integers by only using increments, decrements, loops/recursion and comparisons.

  • Assume division & modulo will never receive 0 or negative integers as the divisor/modulus.
  • Modulo's result has the sign of its dividend.
  • Division truncates its quotient, e.g divide(11, 4) returns 2 and divide(-5, 3) returns -1.
  • Programs must print the result to STDOUT. Functions must return the result.
  • Your five functions/programs may invoke each other.
  • All functions/programs must support 32-bit signed integers, i.e everything between -231 and 231-1 (inclusive). Overflow is allowed, i.e it's OK if add(2147483647, 1) returns -2147483648.
  • Explicitly adding/subtracting 1 to/from numbers is allowed, in case you use a programming language that doesn't have built-ins for incrementing and decrementing.
  • Shortest program wins as long as it doesn't exploit standard loopholes!


I seriously have no idea how to make test cases for this.

\$\endgroup\$
  • 1
    \$\begingroup\$ Why not one function that returns all of those? You should also specify what you mean by divisions and modulo as they differ slightly from language to language. (E.g. what is -2 mod 5? and what is -1/2?) And only doing increments/decrements, loops/recursion and compraisions is also quite vague. \$\endgroup\$ – flawr Jul 10 '16 at 16:37
  • 1
    \$\begingroup\$ I don't think test cases would really be necessary since it's just basic arithmetic. You can easily tell if your output is correct or not. Also, I'm assuming that division will truncate the quotient since there isn't really any way to do decimals in this fashion, but that should probably be specified. \$\endgroup\$ – Business Cat Jul 11 '16 at 14:18
  • 1
    \$\begingroup\$ I already did this because I was bored... \$\endgroup\$ – Mega Man Nov 19 '16 at 12:52
0
\$\begingroup\$

ASCII to Unicode equation beautifier

You may well be used to typing equations in ASCII, but with the advent of Unicode we can spruce them up a bit. We can fix

  • Powers (numeric superscripts only)
  • Numeric subscripts
  • Mathematical signs (-, *, / ^ → -, ×, ÷, ↑)

Examples:

x^3 - 1 = (x - 1)(x^2 + x + 1)  →  x³ − 1 = (x − 1)(x² + x + 1)
g_0 = 3^^3^^3 -= 3^(3^3)        →  g₀ = 3↑↑3↑↑3 = 3↑(3³)
800*600                         →  800×600
1/x                             →  1÷x

You may assume that all digits directly after a ^ or _ are meant to be super/subscripts (and the ^ or _ to be removed) and that all the mathematical signs are to be replaced wherever they appear.

This is , so the shortest solution wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ This seems to be two questions crammed into one. The first one is the superscript and subscript transformation, which is mildly interesting; and the second one is the straight substitution of various characters for others, which is completely boring apart from the ambiguity it introduces in the interpretation of ^. I suggest ditching the substitution of minus, times, and divide symbols and giving explicit lists (with copyable characters and Unicode code points in decimal and hex) of the superscript, subscript, and up-arrow characters. \$\endgroup\$ – Peter Taylor Jul 14 '16 at 6:39
0
\$\begingroup\$

Autotune a chord

Auto-Tune is a pitch correction program which alters the pitch without changing the length. It can be used to fix off-pitch chords in music, which is good because I have an out of tune piano. The goal of this challenge is given some input waveform which contains a single chord played on my piano, tune each note to the nearest equally tempered note found on a standard piano (see Input for more details).

Input

The input is something which looks like a time-domain audio sample input containing a single chord being played. All data is sampled at 192kHz, with 16-bit PCM (little endian integer), mono channel. The input may come from any source desired (file io, stdio, function parameter, etc.).

Output

The output of your code should be something which looks like a time-domain audio sample containing the tuned chord. It does not need to have the same sample rate or datapoint format as the input, but must be the same length in real time as the original sample (or as close as possible). The output may be to any source desired (file io, stdio, function parameter, etc.).

Examples

See this github repo for various inputs and outputs. The provided examples have inputs/outputs in an uncompressed wav file. Feel free to re-encode/gut the data for your inputs.

Scoring

This is code golf; shortest code wins. Standard loopholes apply. You may use any libraries/builtins so long as they were not designed specifically for performing pitch correction.

Main concern: This challenge seems potentially too difficult, so one alternative I've been considering is changing the piano samples into sine waves at the fundamental frequencies (avoids issues with amplitude decay/harmonics). An even simpler challenge might be to give inputs in the frequency domain (list of fundamental frequencies), though I'm not sure that would make for an interesting challenge as it seems almost too easy at that point.

\$\endgroup\$
  • 1
    \$\begingroup\$ It seems very difficult to determine what outputs are considered correct. \$\endgroup\$ – feersum Jul 14 '16 at 7:44
  • \$\begingroup\$ yeah, that thought had crossed my mind as well. I've considered measures based on the delta of the FFT of user output/expected output, but I'm not sure this is necessarily a good measure of "in tune". \$\endgroup\$ – helloworld922 Jul 14 '16 at 7:47
  • \$\begingroup\$ I suspect that the biggest technical challenge would be phase. The harmonics of each string in isolation should be in phase, because they all derive from a single hammer strike, but the keys of the chord are probably not all struck at exactly the same time, and there will be resonant driving interactions between them which will complicate the signal. I suggest that you explicitly state that people can ignore this issue. \$\endgroup\$ – Peter Taylor Jul 14 '16 at 13:39
0
\$\begingroup\$

This will be a challenge. Additional tags are , and .

How fast is your Stack Exchange community?


tl;dr

Your task is to find how fast a Stack Exchange community reacts. "How fast" is here the average of the time elapsed until the first answer or the closing of the question.

Input

  • the Stack Exchange site's name, e.g. stackoverflow, codegolf, codereview etc.
  • optionally the Stack Exchange API URL: https://api.stackexchange.com/2.2/

Requirements

  • Calculate the average time it takes until the first answer or closing of the question.
  • Take the 1000 latest questions into account, e.q. ten API requests with 100 items each.

Output

  • Output the average time in minutes and seconds, like 01:23 or 1:23.
  • Run your program at least against stackoverflow, codegolf and code review and show the results.
  • Feel free to add results for your other favorite communities as well.

Boilerplate

  • You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
  • This is so shortest answer in bytes wins.
  • Standard loopholes are disallowed.
  • Leading/trailing whitespaces/newlines are fine.
\$\endgroup\$
  • 2
    \$\begingroup\$ How do you count unanswered and unclosed questions? Also, I don't know about the API, but there might be problems with deleted answers. I think you should probably write a reference implementation before posting this. \$\endgroup\$ – FryAmTheEggman Jul 14 '16 at 13:10
  • \$\begingroup\$ @FryAmTheEggman Thanks a lot – all good points. Didn't think that there might be questions that are unclosed and unanswered. Will check the API whether deleted even will be send. Good point with the reference implementation – maybe in JavaScript that it can be run as a stack snippet. What do you think in general about the challenge idea? Boring? Interesting? Too complicated? \$\endgroup\$ – insertusernamehere Jul 14 '16 at 13:15
  • 1
    \$\begingroup\$ It's about doing basically one task, so I don't think it is complicated. I think the results are probably more interesting than the challenge (there are only so many ways to average something and to parse html), but it makes sense and isn't trivial, so I wouldn't say it's boring. Seems fine overall. Also note internet, date and, I suppose, math. \$\endgroup\$ – FryAmTheEggman Jul 14 '16 at 13:24
  • \$\begingroup\$ @FryAmTheEggman Thanks again for your feedback and the tag suggestions. I also think that the results are the interesting part. I wanted to try a popularity contest in the first place because of that. But I couldn't come up with the necessary criteria. :) \$\endgroup\$ – insertusernamehere Jul 14 '16 at 13:30
0
\$\begingroup\$

Convert a BMP image to grayscale

The images manipulation is a great way to exercise and increase your skills. In my opinion it's also very interesting.

What you must do?

The objective of exercise is much easy: convert an image bmp colorful in an image grey.
You can use every language, the question most appreciated will be that don't use library.
Image stock: http://www.mediafire.com/convkey/c491/p7aya9cxafvfc91zg.jpg Image converted: http://www.mediafire.com/convkey/3903/rcigd79pkwd12qczg.jpg?size_id=3

\$\endgroup\$
  • 1
    \$\begingroup\$ What is the winning criterion? It is code-golf, popularity-contest, other criterion? \$\endgroup\$ – TuxCrafting Jul 15 '16 at 10:30
  • 1
    \$\begingroup\$ Also, the You can use any language is unnecessary, it's implied here. And you can use ![](<image url>) to show the images. \$\endgroup\$ – TuxCrafting Jul 15 '16 at 10:33
  • 4
    \$\begingroup\$ This is very underspecified at present. 1. What weights should be used in the conversion from RGB to greyscale? 2. What bit depths should be supported? 3. Is it required to support all of BMP's features (e.g. ICC colour profiles, CMYK, JPEG, PNG)? If not, what is the minimum feature set which must be supported? \$\endgroup\$ – Peter Taylor Jul 15 '16 at 10:53
  • \$\begingroup\$ @Blind To mention someone, you can use @<username>, and please add the tags to your post ([tag:<tag name>]) \$\endgroup\$ – TuxCrafting Jul 15 '16 at 12:43
  • \$\begingroup\$ @TùxCräftîñg , It's a code-golf. @ Peter Taylor , It's equal, you can use that weight you want. 2.see 1st. 3.just support BMP. \$\endgroup\$ – Blind Jul 15 '16 at 16:27
  • 1
    \$\begingroup\$ That doesn't actually answer questions 2 or 3. \$\endgroup\$ – Peter Taylor Jul 15 '16 at 19:32
  • \$\begingroup\$ Just to let you know, you can only @mention one person per comment, and it won't work with a space between the @ and the name. \$\endgroup\$ – trichoplax Jul 20 '16 at 16:20
0
\$\begingroup\$

Do I have an emoji?

Given an input string in your language, return truthy/falsey if the input contains an valid Unicode emoji character.

What is an Emoji?

The word emoji comes from the Japanese:

絵 (e ≅ picture) 文 (mo ≅ writing) 字 (ji ≅ character).

Emojis are pictorial symbols used to represent feelings, actions, or objects.

For this challenge, use the Full Emoji Data list provided by Unicode as a reference to determine which characters are valid Emojis.

Sample test cases:

"" -> 0

"💩" -> 1

"hello💩" -> 1

"hello" -> 0

"!±≡𩸽" -> 0


Discussion:

This seems trivial, but I noticed we didn't have an emoji detection challenge. There might be a concern about the encoding of the input string, but reading the linked meta posts about Strings I feel that this challenge can use whatever String format the language used in the answer supports.

The acceptable output for booleans is also up for discussion. Do we have a meta post on what output formats are acceptable for booleans?

\$\endgroup\$
  • 5
    \$\begingroup\$ One question: What exactly is an emoji? I think it should be specified in the challenge. \$\endgroup\$ – user48538 Jul 18 '16 at 16:38
  • 1
    \$\begingroup\$ See meta.ppcg.lol/q/2190, just say truthy/falsey. \$\endgroup\$ – LegionMammal978 Jul 18 '16 at 16:39
  • \$\begingroup\$ @zyabin101 can I use Unicode's emoji list as a list of valid emoji characters for this challenge? \$\endgroup\$ – JAL Jul 18 '16 at 16:44
  • \$\begingroup\$ Up to you. [filler text] \$\endgroup\$ – user48538 Jul 18 '16 at 16:51
  • \$\begingroup\$ I've attempted to clarify what an emoji is, at least for this challenge. Hopefully this will make this question more clear and a better fit for the site. \$\endgroup\$ – JAL Jul 19 '16 at 2:39
  • \$\begingroup\$ A source which gives actual ranges would be more convenient for people writing answers, although unicode.org/Public/emoji/3.0//emoji-data.txt isn't entirely consistent with the other lists. \$\endgroup\$ – Peter Taylor Jul 19 '16 at 9:52
0
\$\begingroup\$

Trim trailing spaces in less than O(n²) time

Since s/\s+$// runs in O(n²) time, Stack Overflow needs to replace it with something faster. Please write a code snippet for them. Your score will be the number of bytes in your submission, multiplied by the time taken to process a string of 1000 non-spaces with 1,000,000 leading and trailing spaces, divided by 1000 times the time taken to process a string of 1-non space with 1,000 leading and trailing spaces. (In other words, if your code runs in O(n) time then this should cancel out.)

\$\endgroup\$
  • \$\begingroup\$ The fancy scoring seems like it might be confusing/hard to implement. Why not just restrict the complexity to be less than O(n²) like you suggest in the title? \$\endgroup\$ – FryAmTheEggman Jul 21 '16 at 13:18
  • \$\begingroup\$ @FryAmTheEggman That's fairly easily fixed with (?<!\s)\s+$ or using RTL matching in .NET/Retina. (In fact, the latter would probably be a good candidate for winning the challenge even if actual runtime is taken into account.) \$\endgroup\$ – Martin Ender Jul 21 '16 at 15:29
  • \$\begingroup\$ @MartinEnder That is what I had in mind ;) Is there a reason that would be bad? I think that is likely around the best performance you can get, being linear w.r.t. the number of spaces at the end of the string? \$\endgroup\$ – FryAmTheEggman Jul 21 '16 at 15:33
  • \$\begingroup\$ @FryAmTheEggman well it just means there's likely a very simple solution that might win the challenge. \$\endgroup\$ – Martin Ender Jul 21 '16 at 15:35
  • \$\begingroup\$ The scoring mechanism is not going to work well because the times will be so small that there will be more noise in the measurement than signal. Especially for the smaller test case, where the string will fit in L1 cache. \$\endgroup\$ – Peter Taylor Jul 21 '16 at 16:15
  • 1
    \$\begingroup\$ The scoring can be exploited by intentionally doing badly on smaller cases. \$\endgroup\$ – xnor Jul 22 '16 at 2:46
0
\$\begingroup\$

Reverse stdin to stdout, Unicode aware and by grapheme clusters

It's 2016. High time that we were Unicode-aware, don't you think?

Given a UTF-8 string on stdin, reverse it by extended grapheme clusters (as defined by the Unicode consortium; this can be found here, for instance) and place it on stdout. This is seemingly a trivial challenge, but surprisingly difficult in many languages.

You may not use an explicit end-of-file character - if supported, use EOF. If not supported, use an explicit length at the start of the string, and document the format.

Note that the string may be of any length (barring RAM limitations).

You must handle direction override characters "properly", in the sense that the directionality of every character must remain the same after reversing the string.

\$\endgroup\$
  • \$\begingroup\$ I need examples for this. \$\endgroup\$ – TLW Jul 21 '16 at 23:05
  • \$\begingroup\$ Can you give a link to the Unicode definition of grapheme clusters? \$\endgroup\$ – Steven H. Jul 21 '16 at 23:59
  • \$\begingroup\$ Sure: unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries \$\endgroup\$ – TLW Jul 22 '16 at 1:18
  • 1
    \$\begingroup\$ I don't understand what you mean about the direction override characters. Could you give some test cases (preferably with hexdumps of input and output)? What other corner cases are there? On a first read-through I can tell that understanding the definition of extended grapheme cluster will take some time, but I'm not clear on whether it covers e.g. emoji type modifiers, emoji families, etc. The definition also makes reference to degenerate cases, and they should be covered by test cases too. \$\endgroup\$ – Peter Taylor Jul 27 '16 at 12:05
0
\$\begingroup\$

Given an ordinal A and a nonnegative integer B, compute f_A(B)

A will be expressed in Cantor Normal Form. A number is in Cantor Normal Form if it is 1, or if it is either of the form a+b or w^a, where a and b are in Cantor Normal Form, and w is the ordinal omega.

f_A(B) is the fast-growing hierarchy, specifically, the Wainer Hierarchy. f_0(n)=n+1. f_(a+1)(n)= n iterations of f_a to n. f_a(n)=f_an if a is a limit ordinal. a[n] is the nth member of the fundamental sequence for a.

\$\endgroup\$
  • \$\begingroup\$ You'll definitely need to add the definitions of these, as most people won't have any idea how to answer. You can use one of various online TeX -> image services and add those to your post. Sadly we don't have MathJax activated because it borked a bunch of other features. I'd also heavily recommend adding some test cases. \$\endgroup\$ – FryAmTheEggman Jul 21 '16 at 14:38
  • \$\begingroup\$ Test cases are impossible to add. But thanks for formatting advice! \$\endgroup\$ – Oliver Daugherty-Long Jul 21 '16 at 15:14
0
\$\begingroup\$

Difficulty Naming


Introduction

In the game osu!, players can make their own beatmaps (levels). The harder the beatmap is, the bigger the star rating will be.

Beatmaps have star icons with different colors and letters according to their star rating.

osu! has also four game modes. The shape of the icon will change depending on the game mode.

The Challenge

Given a star rating and a gamemode, output the (generally used) difficulty name.

The Input

  • A positive floating-point number (star rating)
    • You can assume the number will never have more than two decimal places.
  • A positive integer (game mode)
    • 1 is Standard, 2 is Taiko, 3 is Catch the Beat and 4 is Mania (you can use other numbers for the game modes, these are the default.)

The Output

  • A string (difficulty name)

Use this table to determine the output:

diff table http://image.prntscr.com/image/174e34e56dbb40ad81b209fac3fdc5bc.png

(if the star rating is exactly 5.25, it counts as Above 5.25)

Rules

  • This is , so the shortest solution wins.
  • Standard loopholes are disallowed.
  • You can take the input either as an array/list, a string separated by commas or spaces, or each number individually.
  • Again, you can use other numbers for the game modes.

Test Cases

2.24, 2 ---> Futsuu
1.1, 4 ---> Basic
3.14, 1 ---> Hard
7.0, 3 ---> Overdose
5.0, 4 ---> Exhaust
31415.0, 2 ---> Ura Oni
0.01, 1 ---> Easy
5.25, 1 ---> Expert

Sandbox

If you see any grammar errors or anything like that, please tell me, I'm not a native speaker.

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

Could it all add up to nothing?

Given an input number, return a truthy value if it is possible to arrange permutations of + and - signs to make the sum of the range up to that value 0.

Note that you don't have to output which set of combinations is truthy.

Test cases:

1 (1) --> Falsy
2 (1,2) --> Falsy
3 (1,2,3) --> 1+2-3, Truthy
4 (1,2,3,4) --> -1+2+3-4, Truthy
5 (1,...,5) --> Falsy
6 (1,...,6) --> Falsy
7 (1,...,7) --> 1+2-3-4+5+6-7, Truthy
8 (1,...,8) --> 1+2-3-4-5-6+7+8, Truthy

Just one thing - no using eval or similar commands.

This is so the shortest answer in bytes wins!

Sandbox notes

Require a range or a list as input?

\$\endgroup\$
  • \$\begingroup\$ For general lists, I think it would be basically the same as this question. For ranges, I suspect there's a direct criterion. \$\endgroup\$ – xnor Jul 25 '16 at 21:50
  • \$\begingroup\$ @xnor so do I which is why I think it could be more interesting if the pattern could be found. It gets exponentially longer as the lists get longer so is harder to check - better as a fastest algorithm/fastest code? \$\endgroup\$ – Blue Jul 25 '16 at 21:52
  • \$\begingroup\$ I can show that it's exactly the numbers of form 4*n or 4*n-1. \$\endgroup\$ – xnor Jul 25 '16 at 21:59
  • \$\begingroup\$ (Ninja'd by xnor) There is probably quite an easy pattern, e.g. if the upper limit is divisible by four, you can always find a zero sum with a "little gauss" argument. \$\endgroup\$ – flawr Jul 25 '16 at 22:01
  • \$\begingroup\$ @xnor I'd love to see a proof=) \$\endgroup\$ – flawr Jul 25 '16 at 22:01
  • 4
    \$\begingroup\$ The key is that the pattern +--+ on four consecutive numbers adds to 0. With 4*n, just repeat +--+. With 4*n-1, do +1+2-3, then repeat +--+. With the rest, the sum is odd so it's impossible. \$\endgroup\$ – xnor Jul 25 '16 at 22:04
  • \$\begingroup\$ So saveable? Sounds trivial now. \$\endgroup\$ – Blue Jul 25 '16 at 22:31
  • \$\begingroup\$ Well, I'm guessing xnor's solution would be pretty short. \$\endgroup\$ – mbomb007 Jul 29 '16 at 14:35
0
\$\begingroup\$

Grow and Visualize Decision Tree

META: work in progress...

  • Would providing the points as an image instead of a list of coordinates simplify the challenge?

Given two sets of points in the plane with coordinates x,y, both in [0,1), grow a (binary) decision tree as specified below and output a square pixel image of a given size, that visualizes the corresponding tree.

How to grow the tree

The we call the two sets here classes and follow the following recursive approach:

  1. If at least one of the classes is empty, label the current node as a leaf of the nonempty class and stop. Otherwise:

  2. First find the mean of each of the x (or y)-coordinates of each of the two classes, and find the mean/center c of those two means. Then we partition both classes as follows: All points with an x (or y)-coordinate strictly smaller than c belong to one half, all the other ones to the other half. The we set the current node to the decision is the x-cooridinate (or y-coordinate) less than c?

  3. For each of the halves, go back to step 1 and 2, and set the resulting nodes as the child nodes from the current node. If you previously considered the x-coordinates, then consider y-coordinates and vice versa.

enter image description here

How to visualize the tree

We partition the the unit interval [0,1) into N equidistant sub intervals [0,1/N), [1/N,2/N), [2/N,3/N)... and correspondingly the unit square [0,1)x[0,1) into squares

[i/N,(i+1)/N)x[j/N,(j+1)/N) for i,j=0,1,2,...,N-1

which later will be represented by a pixel. For each square [i/N,(i+1)/N)x[j/N,(j+1)/N) we classify the point i/N,j/N with the tree we just grew and colour the corresponding pixel with the corresponding colour.

For the example above the output would look like so:

enter image description here

Details

  • Input: An integerN>5 and two sets of points in any convenient format (e.g. as two separate list of points, or as a single list with a label for each point etc.) You can assume that in total there is at least one point.
  • Output: A pixel image (vector images composed of squares are ok too) of the visualization.
    • You have to choose any two distinct colours, I recommend blue and red.
    • The x-axis should point to the right, the y-axis can point in any direction.
    • The submission should display the image on the screen or save it to a file (like jpg/png/tiff or similar formats)
\$\endgroup\$
  • \$\begingroup\$ 1. The example has the y-axis running upwards, but the text doesn't specify whether that's required. 2. What exactly counts as a "pixel image"? In particular, I assume that a 2-dimensional array doesn't, but if you don't rule that out explicitly then someone will probably try it. \$\endgroup\$ – Peter Taylor Jul 25 '16 at 20:33
  • \$\begingroup\$ @PeterTaylor Thank you for the feedback, I added these points. I just had the idea to provide the input points as image, instead of a list of coordinates as a simplificatio. \$\endgroup\$ – flawr Jul 25 '16 at 21:51
0
\$\begingroup\$

Make a sequence from a sequence!

(Title is bad and I should feel bad)

Given a sequence of positive Integers, take each consecutive pair of two (without taking an element two times) (x,y) and print y x times.

For example for 3,1,4,2

  1. Pairs are (3,1) and (4,2)
  2. (3,1): Print 1 three times: 1 1 1
  3. (4,2): Print 2 four times: 2 2 2 2
  4. Resulting sequence/output is 1, 1, 1, 2, 2, 2, 2

Input

A sequence of positive integers divisible by two. This can be done by parameters, a flat array, an integer stream etc. AS LONG AS there's no nesting or pre-matching of pairs involved.

Output

The resulting sequence as showcased above. Same rules for datatypes as declared in input, keep everything flat.

Test cases

      3, 1, 4, 2 => 1, 1, 1, 2, 2, 2, 2
            6, 5 => 5, 5, 5, 5, 5, 5
1, 1, 1, 1, 1, 1 => 1, 1, 1

Reference Implementation (Ruby, 55 bytes)

f=->a{a.each_slice(2).collect{|x|Array.new *x}.flatten}

Ungolfed:

def g *a
  a.each_slice(2).collect do |x|
    Array.new(x[0], x[1]) 
  end.flatten
end

The first golfer to find a shorter solution in this language gets a -1 bonus.

Scoring

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ 1. You explicitly mention printing. Could a function submission also return the array? 2. I recommend dropping the bonus. 3. Can the input be empty or will there be at least one pair? \$\endgroup\$ – Dennis Jul 27 '16 at 21:16
  • \$\begingroup\$ This is close enough to this question that I would cast my supervote to close as duplicate. \$\endgroup\$ – Peter Taylor Jul 28 '16 at 8:08
  • \$\begingroup\$ @PeterTaylor indeed. Will drop this challenge then. \$\endgroup\$ – Seims Jul 28 '16 at 10:02
0
\$\begingroup\$

CAPTCHAs (Cops and Robbers Style)

Cops will write a program that generates a CAPTCHA (either through stdin/stdout or on whatever UI is available to your language using only built-ins).

Robbers will attempt to bypass the generated CAPTCHA programmatically, given access to the Cops' programs' stdin/stdout or UI process/thread (for example, in JavaScript, running on the same document and window).

I need help fleshing this idea out a little more... any suggestions will help.

\$\endgroup\$
  • 1
    \$\begingroup\$ How are you going to ensure that captchas are actually captchas, and not an encrypted string turned into an image? The only way I can think to ensure that we're actually dealing with Captchas is to have humans solve them, which would add another layer of complexity to this challenge. \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 16:03
  • \$\begingroup\$ @NathanMerrill Well, part of the requirement of a CAPTCHA is that humans should be able to pass the test without just guessing, but I don't know how to make that a more concrete requirement. Perhaps "The required input from an end-user should be visible and somewhat readable in the presented image / ascii-art"? \$\endgroup\$ – Patrick Roberts Jul 29 '16 at 16:08
  • \$\begingroup\$ Right, that's super broad. Unless you have some sort of test where users actually fill out the captcha, I think its going to remain broad. (Unless you can think of another way to test) \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 16:12
  • \$\begingroup\$ @NathanMerrill I could volunteer to test by running and filling out a CAPTCHA, and give objective feedback whenever an answer is posted, saying whether the CAPTCHA cop submission is acceptable or not. Would that be a sufficient test? \$\endgroup\$ – Patrick Roberts Jul 29 '16 at 16:14
  • \$\begingroup\$ Unfortunately not. It'd be like challenges that say "Write the cleanest code, judged by me". \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 16:15
  • \$\begingroup\$ @NathanMerrill here's an idea. I can add the popularity-contest tag by allowing voting of a cop submission to be based on the human usability. Then I don't have to define exactly what criteria makes a CAPTCHA acceptable. \$\endgroup\$ – Patrick Roberts Jul 29 '16 at 16:25
  • \$\begingroup\$ That would theoretically work. Historically, though, popularity contests that have worked work because people would vote up based on the "wow factor". Aka, generate an image with limitation X, and people upvote and say "Wow, that's a impressive rendering". You'd really have a hard time getting to people vote based on "this is readable", but that's a personal opinion. I don't think it would be off-topic though. \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 16:28
0
\$\begingroup\$

Create me a Brainf*** assembler

Write a way to convert "human readable" assembly (of any kind) to Brainf***. I.E specify a language "X" (which may already exist or may be your own invention), and create a way to map each valid program to a valid Brainf*** program. This is a so the most convenient assembler as evidenced by upvotes wins!

\$\endgroup\$
  • \$\begingroup\$ Convenient is a very broad criterion for judgement. I'd recommend specifying a particular variety of assembly, then make it a code golf challenge. \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 22:46
  • \$\begingroup\$ @NathanMerill can I specify a specific language I have in mind? \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:06
  • \$\begingroup\$ @NathanMerrill and then make it code golf \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:06
  • \$\begingroup\$ Yes, that would be on topic, but not necessarily interesting, depending on the target language \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 23:15
  • \$\begingroup\$ github.com/rjhunjhunwala/S.I.L.O.S that is the target language, and since both BF and S.I.L.O.S are turing complete it seems possible, but challenge \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:16
  • \$\begingroup\$ You would need to include a complete specification of the language on your post, but I have no idea if that would be interesting \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 23:19
  • \$\begingroup\$ @Nathan Merrill all in all I think it seems to be a ridiculous challenge. Any non tricial in brainf*** is a challenge, now making code to generate non trivial brainf*** is impossible \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:20
  • \$\begingroup\$ @NathanMerrill I will delete this challenge as it seems to be uninteresting? \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:21
  • \$\begingroup\$ It's much easier to generate BF than to handwrite it. I don't know if it would be interesting, that's up to the community \$\endgroup\$ – Nathan Merrill Jul 29 '16 at 23:23
  • \$\begingroup\$ It seems that it is challenging to write any reasonalbly readable environment for assembling to brainf*** \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 23:27
  • \$\begingroup\$ what if I choose X to be Brainfuck or Brainfuck+one extra command. \$\endgroup\$ – KarlKastor Jul 30 '16 at 19:49
  • \$\begingroup\$ Than you would likely lose. @KarlKastor. It is not code-golf but rather popularity-contest \$\endgroup\$ – Rohan Jhunjhunwala Jul 30 '16 at 19:50

You must log in to answer this question.

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