571
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

\$\endgroup\$
1
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    May 15 at 14:05

4692 Answers 4692

1
47 48
49
50 51
157
2
\$\begingroup\$

Make Code Printing X Without X

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

How many twisted corners?

Posted here

\$\endgroup\$
6
  • \$\begingroup\$ suggested testcase: B U2 D2 F => 0, Also, is repeating a move legal? (like U U' or F2 F) \$\endgroup\$
    – Fmbalbuena
    Oct 31, 2023 at 16:55
  • \$\begingroup\$ Is this a parsing challenge or is the input format loose? (e.g. RRR instead of R', RR instead of R2) \$\endgroup\$
    – noodle man
    Oct 31, 2023 at 23:11
  • \$\begingroup\$ @noodleman good point, I'll redefine the input. \$\endgroup\$
    – math scat
    Nov 2, 2023 at 18:38
  • \$\begingroup\$ You might want to include a worked example with a GIF or something like that. \$\endgroup\$
    – noodle man
    Nov 2, 2023 at 21:17
  • \$\begingroup\$ @noodleman right, thanks! \$\endgroup\$
    – math scat
    Nov 2, 2023 at 21:19
  • \$\begingroup\$ Is the input guaranteed to have at least one move, or may it be empty? \$\endgroup\$
    – noodle man
    Nov 2, 2023 at 21:27
2
\$\begingroup\$

Sub-quadratic base conversion

Write a program that converts a positive integer given in base 10 to its base 2 representation.

Your algorithm must run in a complexity lower that \$O(n^2)\$

Rules

  • You can assume that each arithetic operation (sum/multiplication/division/remainder/exponentation) has the running time of the fastest known algorithm, independent of the implementation that is actually used (This includes methods that you wrote yourself).
    • Addition can be done in linear time
    • Multiplcation/division/remainder run in \$ O(n \cdot \log(n))\$ where \$n\$ is the sum of the numbers of bits of the inputs *.
    • Exponentiation \$N^X\$ runs in \$O((n \log x)(\log(n)+\log(\log x)))\$ where \$n\$ and \$x\$ are the numbers of bits in \$N\$ and \$X\$ respectively.
    • If you know faster algorithms please link them in your challenge
  • All built-in base-conversion/library methods for base-conversion are assumed to run in quadratic time in the input, even if the actual implementation is faster
  • (... more rules will follow)


* The \$O(n log (n)) \$ multiplication algorithm assumes that both arguments have the approximately same size, for simplicity you may assume that the same complexity can be archived for arbitrary argument sizes (this may not be true in practice).


Meta

  • Is this a duplicate?
  • Is there interest in a challenge of this form?
  • Is my explanation clear?
\$\endgroup\$
6
  • \$\begingroup\$ This seems like it would be extremely hard for languages with no built-in big integers, because they probably have to implement subquadratic multiplication \$\endgroup\$ Nov 16, 2023 at 0:37
  • \$\begingroup\$ @CommandMaster I clarified that the running time of the multiplication method does not matter \$\endgroup\$
    – bsoelch
    Nov 16, 2023 at 9:51
  • \$\begingroup\$ I see. Does it that apply to multiplying by 10 \$a\$ times, or do you have to calculate \$10^a\$ once and then multiply by it? \$\endgroup\$ Nov 16, 2023 at 10:49
  • \$\begingroup\$ @CommandMaster repeated multiplication by fixed number will be calculated as exponentiation, multiplication until a given condition is satisfied will be calculated as individual multiplications \$\endgroup\$
    – bsoelch
    Nov 17, 2023 at 8:08
  • \$\begingroup\$ Is x in exponent width or value? \$\endgroup\$
    – l4m2
    Nov 19, 2023 at 10:46
  • \$\begingroup\$ Need O(nm) multiplication when m>>n \$\endgroup\$
    – l4m2
    Nov 19, 2023 at 10:50
2
\$\begingroup\$

Compute the Kimberling Sequence

Introduction

The Kimberling Seqeunce is a sequence of sequences. Each sequence is defined in terms of the previous sequence and the previous stage number. At each stage, the numbers from the previous stage are rearranged as follows:

  • For k in [1,...,i], write term i+k and then term i-k.
  • Discard the ith term.
  • Write the remaining terms in order.

We start with all positive integers at stage 0, so the first few rows look like this.

1  2  3  4  5  6  7  8  9 10 11
2  3  4  5  6  7  8  9 10 11 12
4  2  5  6  7  8  9 10 11 12 13
6  2  7  4  8  9 10 11 12 13 14
8  7  9  2 10  6 11 12 13 14 15

At each stage, the number on the diagonal is expelled (it is an open question as to whether every number is eventually expelled).

Challenge

Your program must take a positive integer n as input and output the integer expelled in forming the nth stage of the Kimberling sequence.

Answer the following questions for your readers.

Standard loopholes are forbidden. As this is , shortest program wins.

Example Input and Output

1 -> 1
2 -> 3
3 -> 5
4 -> 4
5 -> 10
6 -> 7
7 -> 15
8 -> 8
9 -> 20
10 -> 9
11 -> 18
12 -> 24
25 -> 2
100 -> 229
1000 -> 394
1001 -> 1274

More test cases from OEIS.

Sandbox Questions

This is my first code golf question, so I'm not sure what to ask other than is there anything that I can improve/need to fix before asking the main site?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thanks for using the sandbox! I think your initial explanation is a bit imprecise/incorrect. I think you want to say something like: "at stage k write the value from stage k-1 at index k+1, then index k-1, then write the rest of the sequence from stage k-1 excluding the value at index k" or something (probably format it better, as you have already). As it is, you don't define i or k. Also, I think you should consider the default template for sequence in the tag info (click "more info" to see it). Good luck! \$\endgroup\$ Nov 23, 2023 at 6:14
  • \$\begingroup\$ Thanks, I mostly just copied the definition from the MathWorld link, but I'll make it more understandable. \$\endgroup\$
    – Tbw
    Nov 23, 2023 at 16:15
  • 1
    \$\begingroup\$ Darn. I almost finished submitting this question, and then I saw it was a duplicate of codegolf.stackexchange.com/questions/67542/… \$\endgroup\$
    – Tbw
    Nov 24, 2023 at 21:51
2
\$\begingroup\$

Implement the "Wolontis" Function

While looking at old ALGOL documentation with someone else on Discord, this "famous" function popped up:

An image claiming to show "the famous Wolontis Function"

Although it’s mentioned in other language manuals of the era, such as Runcible and FORTRAN, we haven't managed to find any references to this function online — so let's change that.

The expression in the image is \$\frac{\sin x}{\sqrt{1-e^{-x^3}}}\$. Your task is to implement this function for positive inputs, as its value is undefined at \$x=0\$ and imaginary for negative \$x\$. Floating-point inaccuracies are permitted.


Sandbox questions

  • How accurate/precise should answers be required to be?
  • What other tags should I add?
  • Any other information I should include? e.g. would a graph be helpful?
\$\endgroup\$
1
  • 2
    \$\begingroup\$ there's references to it here and here. I think 'famous' means famous to 1950s mathematicians ^^ \$\endgroup\$
    – guest4308
    Nov 22, 2023 at 9:58
2
\$\begingroup\$

Read a French number

We have Spell out numbers in French, Translate numbers to French and Telling time in French, but we were missing the reverse:

Challenge

Read a French expression, and output the corresponding integer.

Input

In true French, a French number expression is a list of French words separated by whitespace, and possibly by hyphens "-" and the word "et", such as "sept mille deux cent vingt-et-un".

For this challenge, you do not need to care about hyphens and the word "et": you are free to take input as a whitespace-separated string of words such as "sept mille deux cent vingt un", or as a list of single-word strings such as ["sept", "mille", "deux", "cent", "vingt", "un"].

All French words will be taken from the following list:

        'zero': 0, 'un': 1, 'deux': 2, 'trois': 3, 'quatre': 4,
        'cinq': 5, 'six': 6, 'sept': 7, 'huit': 8, 'neuf': 9,
        'dix': 10, 'onze': 11, 'douze': 12, 'treize': 13,
        'quatorze': 14, 'quinze': 15, 'seize': 16,
        'vingt': 20, 'trente': 30, 'quarante': 40, 'cinquante': 50,
        'soixante': 60,
        'cent': 100, 'mille': 1000, 'million': 1000000, 'milliard': 1000000000

Note that in correct French, "million" and "milliard" must take an -s in plural form, but for this challenge you do not need to care about that. "zéro" also must take an accent on the "e", but you do not need to care about that. "un" must be "une" in feminine form, but you do not need to care about that.

Also note that if we simply added "septante: 70, octante: 80, huitante: 80, nonante: 90" then we would be able to handle Belgian French and Swiss French, but for this challenge you do not need to care about that.

Output

Output one integer, corresponding to the French input number.

Conversion rule

Once the sequence of French words has been converted into a sequence of numbers, this sequence can be converted into one number by identifying the largest number in the sequence, then using one simple recurrence rule:

convert(left, largest, right) = convert(left) * largest + convert(right)

with of course the special cases that convert(empty left sequence) = 1 and convert(empty right sequence) = 0.

For instance:

"sept mille deux cent vingt un"
[7    1000  2    100  20    1]
[7] * 1000 + [2 100 20 1]
7000 + ([2] * 100 + [20 1])
7000 + (200 + ([] * 20 + [1]))
7221

Test cases

"sept mille deux cent vingt un"     ->  7221
"soixante douze cent vingt un"      ->  7221
"dix sept cent quatre vingt neuf"   ->  1789
"mille sept cent quatre vingt neuf" ->  1789
"trois mille neuf cent quatre vingt dix sept" -> 3997
"cent mille milliard cent trente sept million trois cent quatre vingt quinze mille huit cent cinq"
    ->  100_000_137_395_805
"zero"                 -> 0
"un milliard dix sept" -> 1_000_000_017
"mille"                -> 1000

Rules

  • This is code-golf, the shortest code in bytes wins!
\$\endgroup\$
2
\$\begingroup\$

Generate the snowflake pattern sequence

A snowflake figure looks like this:

1,2,4,8

A few rules govern how many points each ring can have.

  • The innermost ring must have between 1 and 8 inclusive points.
  • Every other ring must have between 2 and 8 inclusive points.
  • To ensure symmetry, every ring must have a integer multiple times as many points as the next smallest ring.

Valid snowflake sequences, from the smallest to the largest ring, include: 1,2,2,6, 2,4,8, 3,6, 8,8,8,8,8, etc.

Your task is, given a number, output the best configuration of rings.

If there are multiple solutions, find the most aesthetically pleasing one as follows:

  • The one with the most unique ring sizes
  • Unique ring sizes being equal, the one with the biggest smallest ring. Eg. 2,6 is better than 1,7.
  • If the unique ring sizes and smallest ring are both equal, output the one with the smallest total number of rings.

If there are still multiple options, you may choose one arbitrarily.

Test Cases

Number Pattern Image
1 1 1
2 2 2
3 1,2 1,2
4 1,3 1,3
5 1,4 1,4
6 2,4 2,4
7 1,2,4 1,2,4
8 2,6 2,6
9 1,2,6 1,2,6
10 1,3,6 1,3,6
11 1,2,8 1,2,8
12 4,8 4,8
13 1,4,8 1,4,8

1 2 1,2 1,3 1,4 2,4 1,2,4 2,6 1,2,6 1,3,6 1,2,8 4,8 1,4,8

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

Parse nested absolute values

Part1

Part2

\$\endgroup\$
1
  • 4
    \$\begingroup\$ Implicit products would definitely lead to some obvious ambiguous cases like |1|2|3|. I notice that you do account for ambiguity in the spec; are there any such cases without implicit products? One way or another, the solutions would be radically different, since you can’t just assign a parenthesis direction based on local context. \$\endgroup\$ Dec 1, 2023 at 17:53
2
\$\begingroup\$

Implement a simple stack language

\$\endgroup\$
10
  • 3
    \$\begingroup\$ Do you plan to prevent stack based languages just eval'ing it? Also, what's the Winning Criteria..? code-golf? \$\endgroup\$
    – ATaco
    Dec 1, 2023 at 1:48
  • \$\begingroup\$ @ATaco No, I think eval for stack languages would still be interesting. How am I supposed to mark the winning criteria? \$\endgroup\$
    – RubenVerg
    Dec 1, 2023 at 6:08
  • \$\begingroup\$ I suggest to represent the stack in a left=bottom/right=top manner, like it is typically done in every stack based language I know. \$\endgroup\$
    – Philippos
    Dec 1, 2023 at 6:20
  • \$\begingroup\$ »and push them in the opposite order (swap)« strictly thought, they are not pushed in the opposite order: A swap pushes the value first that was popped first. But I doubt this will be misunderstood by anyone. (-; \$\endgroup\$
    – Philippos
    Dec 1, 2023 at 13:51
  • \$\begingroup\$ @Philippos would "and push them so that they are in opposite order" be better? woudln't change it to "and push them in the same order" which would definitely make it more confusing \$\endgroup\$
    – RubenVerg
    Dec 1, 2023 at 13:53
  • \$\begingroup\$ Agreed! »opposite order« is the clearest. \$\endgroup\$
    – Philippos
    Dec 1, 2023 at 17:27
  • \$\begingroup\$ I am definitely trying this in Trilangle if/when it's posted. Maybe give me a couple weeks because it's exam week, but \$\endgroup\$
    – Bbrk24
    Dec 2, 2023 at 3:15
  • \$\begingroup\$ Would it be allowed to only support integers in some bounded interval (e.g. 32-bit integers), or do you require support for arbitrary size integers? Is the integer format required to be decimal or would unary integers be allowed? \$\endgroup\$
    – bsoelch
    Dec 2, 2023 at 15:20
  • \$\begingroup\$ Can the instructions be represented as a sequence of smaller instructions? Can I for example have an an instruction # that pops two numbers and pushes the sum and difference and then define addition as #drop and subtraction as # swap drop or do all operations have to be atomic \$\endgroup\$
    – bsoelch
    Dec 2, 2023 at 16:04
  • \$\begingroup\$ @bsoelch Bounded integers are fine (but maybe specify if it's a very low bound), and you can input them in whatever way you like. Instructions can be not atomic as long as they're deterministic. \$\endgroup\$
    – RubenVerg
    Dec 2, 2023 at 16:45
2
\$\begingroup\$

Simulate a Plant Cell

Now posted! (old drafts still in version history)

\$\endgroup\$
2
  • \$\begingroup\$ The challenge seems good, but the way it's explained/presented could use some improvement. The C6H12O6+6O2 part should be in any order. \$\endgroup\$
    – Jakav
    Dec 14, 2023 at 22:43
  • \$\begingroup\$ Done and posted \$\endgroup\$
    – W D
    Dec 14, 2023 at 22:54
2
\$\begingroup\$

Generate an efficient A* heuristic

A* is a pathfinding algorithm that can be much faster than Dijkstra's, but it requires a heuristic. The heuristic is a function that takes as input one point of the graph, and the destination, then gives a lower bound for the distance between the two points.

The closer the heuristic is to the true shortest distance, the faster the algorithm runs. But if the heuristic ever overestimates, the algorithm is no longer guaranteed to find the shortest path.

Your task is to generate a good heuristic for a given graph. You must submit 2 functions:

  • The first functions must run in at most O(n^3) time. Given a graph, output up to three 64-bit floating point numbers per point.
  • The second function must run in O(1). Given two points on the graph, output a lower bound for the distance between the two points.

Edges of the graph are guaranteed to have positive, non-zero, integer lengths.

Scoring

Your score is the sum of the differences of your heuristic and the true shortest distance on the (yet to be decided) large graph below. The smallest score wins.

\$\endgroup\$
6
  • \$\begingroup\$ I think you meant that if it overestimates the algorithm might not find the shortest path, not underestimate \$\endgroup\$ Dec 20, 2023 at 4:13
  • \$\begingroup\$ Do you want answers to optimize for the particular graph you give, or work well for some general class? \$\endgroup\$ Dec 20, 2023 at 4:19
  • \$\begingroup\$ @CommandMaster I'm looking for a general algorithm but the test case will be just one large graph, which will be the street grid for a real life city, distances scaled by the speed limit. Hard coding the results for that specific graph is a standard loophole but using patterns that may be present is encouraged \$\endgroup\$
    – mousetail
    Dec 20, 2023 at 6:17
  • \$\begingroup\$ Does the second function only get the numbers for the two points, or can it access the entire graph (and just has to use \$O(1)\$ time)? \$\endgroup\$ Dec 22, 2023 at 4:08
  • \$\begingroup\$ If you take a real life city, does it mean the graph is planer? \$\endgroup\$ Dec 22, 2023 at 4:13
  • \$\begingroup\$ I think it would be better to look at the ratio, not the difference, between the heuristic and the true distance. I also think allowing \$O(\log^k(n))\$ time might allow more interesting solutions \$\endgroup\$ Dec 22, 2023 at 4:16
2
\$\begingroup\$

ASCII flood fill

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

This question was marked as posted and is therefore not shown - you can see the revision history for details.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ Can I use random simulation? If so, how many trials are required? Can I output as a floating point number or a fraction? If you think that 0, 00 => 100% should be handled, you may want 00, 0 => 0% too. \$\endgroup\$
    – Bubbler
    Dec 26, 2023 at 6:26
  • \$\begingroup\$ @Bubbler No typical random. Output flexible. I don't place both X,Y and Y,X in the list \$\endgroup\$
    – l4m2
    Dec 26, 2023 at 6:32
  • 1
    \$\begingroup\$ Suggested test cases: 000, 101 => 41.7% (5/12), 000, 011 => 40% (2/5), 111, 1001 => 57.1% (4/7) \$\endgroup\$
    – Bubbler
    Dec 26, 2023 at 6:37
  • \$\begingroup\$ This was going to be Part 2 of my proposal. \$\endgroup\$
    – Neil
    Jan 5 at 1:22
  • 1
    \$\begingroup\$ An interesting test case is 111, 0011; 111 is expected to appear after 14 bits while 0011 is expected to appear after 16 bits... but before 111! \$\endgroup\$
    – Neil
    Jan 5 at 1:27
  • \$\begingroup\$ @Neil Is it 5/12? I currently don't have a solver \$\endgroup\$
    – l4m2
    Jan 5 at 3:33
  • \$\begingroup\$ My source gives 7/12 but I assume that's the probability for 0011. \$\endgroup\$
    – Neil
    Jan 5 at 8:01
  • 1
    \$\begingroup\$ 01, 1 is a valid test case. You have a 1/2 chance of the first bit being 1, in which case 1 will appear first, otherwise 01 will appear first. I think 0, 00 is also a valid test case; 0 always appears first of course. \$\endgroup\$
    – Neil
    Jan 5 at 8:29
2
\$\begingroup\$

How many people are awake?

The following data contains the population of each timezone in the world (source):

UTC;Population (in thousands)
-11;57
-10;1853
-9.5;8
-9;639
-8;66121
-7;41542
-6;272974
-5;332101
-4.5;31923
-4;77707
-3.5;499
-3;248013
-2;4855
-1;3285
0;285534
+1;857443
+2;609921
+3;496279
+3.5;81889
+4;129089
+4.5;31042
+5;305642
+5.5;1458945
+6;199668
+6.5;50112
+7;439650
+8;1679526
+9;220112
+9.5;1814
+10;29482
+11;5267
+11.5;2
+12;6112
+13;308
+14;11

(for the sake of simplicity, I'm removing +X.75 UTC times from the list)

Assuming that every person in the world wakes up at 8AM and goes to sleep at 12AM (in their local time), how many people are simultaneously awake in the world at a given UTC time?

For example, suppose the given time is 2PM UTC. These are the timezones where the local time at 2PM UTC is between 8AM inclusive and 12AM exclusive:

  -6 08:00 272974
  -5 09:00 332101
-4.5 09:30 31923
  -4 10:00 77707
-3.5 10:30 499
  -3 11:00 248013
  -2 12:00 4855
  -1 13:00 3285
  +0 14:00 285534
  +1 15:00 857443
  +2 16:00 609921
  +3 17:00 496279
+3.5 17:30 81889
  +4 18:00 129089
+4.5 18:30 31042
  +5 19:00 305642
+5.5 19:30 1458945
  +6 20:00 199668
+6.5 20:30 50112
  +7 21:00 439650
  +8 22:00 1679526
  +9 23:00 220112
+9.5 23:30 1814

Now, just add the population of these timezones and output 7818023 (corresponding to ~7.8 billion people).

Input

An UTC time. You may accept one of the following (or all of them):

  • two natural numbers h and m, where 0 ≤ h ≤ 23 and m ∈ {0, 30}
  • a real number r, where 0 ≤ r < 24 and its fractional part can be only 0 or 5 (so r = 23.5 corresponds to 23:30).

Standard I/O applies, so you can accept them as lists, strings, etc. You can even accept m as a boolean value, where 0 means HH:00 and 1 means HH:30.

There are two ways of solving this question: hardcoding the output (since there are only 48 possible inputs) or hardcoding the population data and solving by time arithmetic. However, to make this challenge more interesting, you are allowed to accept the population data as an additional input, so you don't need to hardcode it (thus saving you some bytes) and focusing only on the time arithmetic. So you can read it as additional lines from STDIN or an additional function argument.

Output

How many people are awake at the given time, in thousands.

Test cases

00:00 -> 1942634
00:30 -> 1942634
01:00 -> 2382284
01:30 -> 2432396
02:00 -> 2632064
02:30 -> 4091009
03:00 -> 4396651
03:30 -> 4427693
04:00 -> 4556782
04:30 -> 4638671
05:00 -> 5134950
05:30 -> 5134950
06:00 -> 5744871
06:30 -> 5744871
07:00 -> 6602314
07:30 -> 6602314
08:00 -> 6887848
08:30 -> 6887848
09:00 -> 6891133
09:30 -> 6891133
10:00 -> 6895977
10:30 -> 6895977
11:00 -> 7143682
11:30 -> 7144181
12:00 -> 7215776
12:30 -> 7247697
13:00 -> 7574531
13:30 -> 7574531
14:00 -> 7818023
14:30 -> 7816209
15:00 -> 7637639
15:30 -> 7637639
16:00 -> 6024234
16:30 -> 6024234
17:00 -> 5585223
17:30 -> 5535119
18:00 -> 5337304
18:30 -> 3878359
19:00 -> 3572774
19:30 -> 3541732
20:00 -> 3412643
20:30 -> 3330754
21:00 -> 2834475
21:30 -> 2834475
22:00 -> 2224554
22:30 -> 2224554
23:00 -> 1367111
23:30 -> 1367111

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

Accumulate spare change


In this challenge, given some cash, you'll pay for various items as simply as possible (e.g., one $20 bill for a $17 purchase), and get spare change in return. Your task is to figure out what bills and coins you have after all of the transactions.

Input

Your input will be an initial amount of cash, and a list of zero or more prices of items. You can take these either as dollars with decimal cents ($12.95 = 12.95) or as an integer number of cents ($12.95 = 1295). The prices of items will not exceed the initial amount of cash, and no inputs will contain fractional cents.

Task

First, you'll break down your inputted cash into bills and coins, such that the minimum number of bills/coins are required. The following bills and coins exist:

  • $100
  • $50
  • $20
  • $10
  • $5
  • $1
  • $0.25
  • $0.10
  • $0.05
  • $0.01

Then, for each item purchased, you'll pay using the fewest bills/coins possible, and you'll get change in return. If there are multiple possibilities (e.g., for $45, you could pay with a $50 or a $100), choose the closest one. The only exception is if it's possible to pay using 2-4 of the same bill/coin instead of one that's larger than doing it that way (e.g., $40 as 2 $20 bills, or $1 as 4 $0.25 coins if a $1 bill isn't available, but never 4 $5 bills instead of one $20 bill).

Output

Your output will be the number of each bill and coin remaining after the transactions are complete.

Example

Initial cash: $70

You now have $50 + $20.

Transactions:

  • $11: You pay with $20, and now have $50 + $5 + $1 × 4
  • $0.65: You pay with $1, and now have $50 + $5 + $1 × 3 + $0.25 + $0.10
  • $18.75: You pay with $50, and now have $20 + $10 + $5 + $1 × 2 + $0.25 × 2 + $0.10
  • $25: You pay with $20 + $5, and now have $10 + $1 × 2 + $0.25 × 2 + $0.10
  • $2: You pay with $1 × 2, and now have $10 + $0.25 × 2 + $0.10
  • $4.25: You pay with $10, and now have $5 + $0.25 × 5 + $0.10
  • $1: You pay with $0.25 × 4, and now have $5 + $0.25 + $0.10

Output: $5 + $0.10

\$\endgroup\$
7
  • \$\begingroup\$ I like it a lot because there are a real-world applications. At the final step in the example, you "now have $5 + $0.25 + $0.10". Shouldn't the output be that instead of "$5 + $0.10"? \$\endgroup\$ Jan 19 at 8:59
  • \$\begingroup\$ Possible clarification: "than doing it that way (e.g., $40 as 2 $20 bills, or $1 as 4 $0.25 coins if a $1 bill isn't available, …" → "then use the smaller denomination (e.g., $40 as 2 $20 bills instead of a $50 bill, or $1 as 4 $0.25 coins instead of a $5 bill when a $1 bill isn't available, …" \$\endgroup\$ Jan 19 at 9:02
  • 1
    \$\begingroup\$ Is there a "black box" issue? The output will in many cases be the same regardless of how you handle the transactions. An answer that disregards the rules may still show the expected result for many inputs — e.g., if you just subtract the total transactions from the initial cash and break down the result into allowed denominations, you probably get the right output much of the time. Proposal: make the test case enforce "the only exception" rule. Or ask that an answer should show the intermediate steps. The rules would be easier to refer to if they were in a numbered list. \$\endgroup\$ Jan 19 at 9:04
  • \$\begingroup\$ @doubleunary No, that won't give you the right answer. If I have two $100s and deduct $4.16 a few dozen times, I accumulate tons of pennies. Simply taking the remaining cash and making chasnge with it would give you a totally wrong result, and that's the main point of the challenge \$\endgroup\$ Jan 22 at 15:06
  • \$\begingroup\$ Thats understood, but the "output will in many cases be the same". The test case in the question would be vulnerable to this shortcut. I suggest you modify the test case or request intermediate steps be shown. It is also unclear whether "the only exception" rule would be observed when calculating the denominations you get as change. It would be good to specify explicitly how change is calculated. \$\endgroup\$ Jan 22 at 15:20
  • \$\begingroup\$ @doubleunary I'll have more test cases in the final challenge yeah \$\endgroup\$ Jan 22 at 23:36
  • \$\begingroup\$ Great. I left a couple other comments as well. Perhaps you could edit the sandbox question to its final form so that others could review those edits before you post the question on the main site. \$\endgroup\$ Jan 23 at 8:46
2
\$\begingroup\$

Complete a mystery sequence

Given a sequence of three integers, determine if the sequence is arithmetic (of the form [a, a+d, a+2*d]) or geometric (of the form [a, a*r, a*r^2]) by outputting a fourth term that completes it (a+3*d for arithmetic, a*r^3 for geometric).

Examples:

[1, 2, 3] -> 4 (This is an arithmetic sequence with a difference of 1)
[2, 4, 8] -> 16 (This is a geometric sequence with a ratio 2)
[20, 15, 10] -> 5 (arithmetic sequence, d=-5)
[6, 6, 6] -> 6 (arithmetic with d=0 OR geometric with r=1)
[3, -9, 27] -> -81 (geometric with r=-3)
  • Input is guaranteed to be a valid arithmetic and/or geometric sequence (so you won't have to handle something like [10, 0, 99])
  • For geometric sequences, the ratio between terms is guaranteed to be an integer (ie. [4, 6, 9] would be an invalid input, as the ratio would be 1.5)
  • If a sequence could be either arithmetic or geometric, you may output either term that completes it
  • This is code golf, so aim for the lowest byte count possible!

Notes:

  • I'm not sure if there is a sequence that could be completed two different ways. I'd assume there is, but I haven't found it (although I haven't been looking for very long)
  • Is this too much of an A/B challenge?
  • Title suggestions would be appreciated
\$\endgroup\$
9
  • \$\begingroup\$ I think it's fine. Maybe you can just call it a "mathematical progression" instead of "mystery sequence", to recall AP and GP, but it's just my opinion \$\endgroup\$
    – enzo
    Jan 15 at 17:39
  • \$\begingroup\$ Some minor things to be added: 1. you need to define a scoring method (it usually is [code-golf], fewer bytes better) and 2. maybe change the wording "determine if a sequence is ... and output a fourth term that completes it" to "determine if a sequence is ... by outputting a fourth term that completes it", because the former makes it look like there are two outputs instead of just one. Again, it's just an opinion of mine, it's fine either way \$\endgroup\$
    – enzo
    Jan 15 at 17:42
  • 1
    \$\begingroup\$ You should consider adding some info on how to handle invalid input (e.g. [10, 0, 99]): does the answerers need to validate the input first, outputting some value such as "not valid"? Or they can assume that only valid input will be passed (recommended)? \$\endgroup\$
    – enzo
    Jan 15 at 17:47
  • 1
    \$\begingroup\$ That all said, you made a very interesting question! Keep going. \$\endgroup\$
    – enzo
    Jan 15 at 17:51
  • \$\begingroup\$ @enzo thank you for the input! i'll try and make some of the points clearer \$\endgroup\$
    – nyxbird
    Jan 15 at 18:00
  • \$\begingroup\$ 'd like to see if solution use no branch \$\endgroup\$
    – l4m2
    Jan 15 at 20:05
  • \$\begingroup\$ @l4m2 I almost have one, but it fails on a constant sequence. It might be a bit of an annoying edge-case, seeing as no other sequence can be both geometric and arithmetic \$\endgroup\$ Jan 18 at 3:57
  • \$\begingroup\$ Is [1, 0, 0] (geometric with ratio 0) a possible sequence? \$\endgroup\$ Jan 18 at 4:11
  • \$\begingroup\$ @CommandMaster Saw similar question but three inputs are all positive so they did c%b?2*c-b:c*c/b \$\endgroup\$
    – l4m2
    Jan 18 at 5:03
2
\$\begingroup\$

Fastest bytewise comparisons in 64-bit unsigned integers

[tag:i-don't-know]

  • Create a function that accepts two 64-bit unsigned integers, a and b.

  • Compare each corresponding byte in a and b.

  • If the byte in a is greater than the byte in b in the same position, set the corresponding byte in the output to 255.

  • Otherwise, set the corresponding byte in the output to 0.

  • Return the resulting 64-bit unsigned integer.

Restrictions: the code runs in x86-64, no explict SSEx, AVXx (is ok if the compiler vectorices the result)

Example:

a =      202      141        1      123       61       53       40 251
b =      158       75      185      217        5       90      152 225
a = 11001010 10001101 00000001 01111011 00111101 00110101 00101000 11111011
b = 10011110 01001011 10111001 11011001 00000101 01011010 10011000 11100001
a>b=     255      255        0        0      255        0        0      255
a>b=11111111 11111111 00000000 00000000 11111111 00000000 00000000 11111111
\$\endgroup\$
3
  • \$\begingroup\$ GCC compiles it to a single instruction so it seems bad \$\endgroup\$
    – l4m2
    Jan 29 at 6:48
  • \$\begingroup\$ @l4m2 I see, is SSE. What about non using bytes, like using numbers with 4 bits, 5 bits, 9 bits \$\endgroup\$
    – vakvakvak
    Jan 29 at 18:11
  • \$\begingroup\$ @l4m2 The compiler using SSE means that 64 bit registers (non SIMD) remain unused, so there is an opportunity to extract more performance, although I don't know how to take advantage of it. By the way, without compiler optimizations, your code does unnecessary branches. If you store 0,1 in each byte, C[i] = A[i] > B[i], and at the end return the C*255, you avoid a lot of ?. \$\endgroup\$
    – vakvakvak
    Jan 30 at 8:50
2
\$\begingroup\$

How quickly can you type this string?

Given a string consisting of only printable ascii (letters, numbers, symbols, and spaces), how many keystrokes are required minimally to type out this string from scratch? The allowed keystrokes are:

  • one character from printable ascii for 1 keystroke
  • Ctrl-C (copy) any contiguous substring you have typed so far and replace whatever is currently copied (2 keystrokes) and Ctrl-V (paste) any string in your clipboard (1 keystroke)
  • Backspace the last typed character for 1 keystroke

For example, the string "cbaabcbabaacba" can be typed in 12 keystrokes, which is optimal.

Test Cases

cbaabcbabaacba => 12
ababcc => 6
aaaaaaaaaaaaa => 9

Scoring

This is , so the shortest code wins!

\$\endgroup\$
4
  • \$\begingroup\$ The common definition of key stroke in typing competitions is each key press. Thus you must count <kbd>⇧</kbd> (shift), too. From your description it is unclear what <kbd>Ctrl‑C</kbd> and <kbd>Ctrl‑V</kbd> mean. As a terminal user I’d say ETX and SYN respectively. \$\endgroup\$ Jan 27 at 17:40
  • \$\begingroup\$ Ctrl C and Ctrl V and copy and paste, respectively. \$\endgroup\$ Jan 27 at 17:48
  • \$\begingroup\$ Does Ctrl-C append to the clipboard, or reset it? \$\endgroup\$
    – noodle man
    Feb 4 at 17:04
  • \$\begingroup\$ It could be either, I'm not sure which would be best for the challenge. \$\endgroup\$ Feb 4 at 20:14
2
\$\begingroup\$

Divmod continuosly until the remainder is 1 or 0, then get the remainder

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Doesn't 88,7 continue 12,4 and 3,0, resulting in 0? \$\endgroup\$
    – Philippos
    Jan 9 at 6:27
  • \$\begingroup\$ @Philippos Thanks! Probably it's a typo. \$\endgroup\$
    – Fmbalbuena
    Jan 10 at 17:30
  • \$\begingroup\$ I liked this challenge! \$\endgroup\$
    – enzo
    Jan 10 at 22:17
  • \$\begingroup\$ @enzo Just a reminder for you: if you see a good post, then you can upvote it, not just commenting it. \$\endgroup\$
    – Fmbalbuena
    Jan 10 at 22:26
2
\$\begingroup\$

The primitive circle problem

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

Swap letter cases

\$\endgroup\$
1
  • \$\begingroup\$ Why isn't this a dupe yet lol \$\endgroup\$
    – noodle man
    Feb 20 at 20:25
2
\$\begingroup\$

Sum up snail number neighbours

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

Reconstruct a list from its prefixes

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

How quickly can you type this unary string?

\$\endgroup\$
6
  • \$\begingroup\$ Can there be multiple strings in the clipboard or only one at a time? \$\endgroup\$ Mar 8 at 9:06
  • \$\begingroup\$ @CommandMaster Only one. \$\endgroup\$
    – emanresu A
    Mar 9 at 0:49
  • \$\begingroup\$ Isn't ctrl-c technically two keystrokes? \$\endgroup\$
    – vengy
    Mar 10 at 1:32
  • \$\begingroup\$ You can't erase characters, right? \$\endgroup\$ Mar 10 at 4:33
  • \$\begingroup\$ @CommandMaster Yes. \$\endgroup\$
    – emanresu A
    Mar 10 at 6:25
  • \$\begingroup\$ @vengy For the sake of simplicity it's one in this challenge. \$\endgroup\$
    – emanresu A
    Mar 10 at 6:25
2
\$\begingroup\$

Implement a 2-player version of 1D Chess

\$\endgroup\$
9
  • \$\begingroup\$ Your question had 4 out of 5 reopen votes, but I thought of a bunch of other questions about game over. I've seen less well developed questions go live on the main site, but it's good to get things as clear as possible. Any reason why you've deleted the title? I would suggest maybe include in the title that you're looking for a 2 player game, as that seemed to be creating some confusion. For inspiration, see the regular 2 dimensional chess question: codegolf.stackexchange.com/q/45179/15599 \$\endgroup\$ Mar 24 at 14:18
  • \$\begingroup\$ @LevelRiverSt I've added the title, other than that, i''m not sure what else there is to improve \$\endgroup\$
    – Quadruplay
    Mar 24 at 14:29
  • \$\begingroup\$ Per my last comment on the original question consider the following. Incorrect moves: presumably the program must disallow ending your move in check? Also what game-over behaviour is required. You've noted that according to chess rules the game ends when there are only the kings left or a stalemate/checkmate is reached. Is the program required to exit when this condition is reached (in particular stalemate/checkmate requires checking if a player is able to move) or can it just hang? \$\endgroup\$ Mar 24 at 14:51
  • \$\begingroup\$ Feedback here in the sandbox can be useful, but it doesn't get the same traffic as on the main site, so some things can get missed even here. You were doing pretty well for a first question. \$\endgroup\$ Mar 24 at 14:53
  • \$\begingroup\$ Also, maybe limit input format to START CELL, END CELL. The PIECE, END CELL format actually raises several questions about whether a player should use uppercase, lowercase, or case according to their colour. Apologies for suggesting it in the first place. \$\endgroup\$ Mar 24 at 15:03
  • \$\begingroup\$ @LevelRiverSt i seem to have addressed everything you've talked about. no worries about suggesting the PIECE, END CELL format, it's more readable \$\endgroup\$
    – Quadruplay
    Mar 24 at 15:08
  • \$\begingroup\$ Program must also exit when there are only kings left? Also I suggest you delete the bit about 3-move-repitition rule being "welcome." I don't recommend requiring it (very tedious to implement) and nobody is going to do if if you don't require it. Other than that, now that you have deleted from the main site and posted to sandbox, I suggest you wait a few days and see if anyone thinks of anything else. \$\endgroup\$ Mar 24 at 15:19
  • 1
    \$\begingroup\$ Could you specify better the "Incorrect moves must be rejected" rule? Do you mean that the program should detect illegal moves and ask for input again, or could a program exit with an error when a player tries an illegal move? It could also be an idea to just let programs assume that all input will be legal and save people from having to validate input every time, but it is your choice what to require here. \$\endgroup\$
    – Leo
    Mar 25 at 1:15
  • 1
    \$\begingroup\$ @Leo i've hopefully clarified it \$\endgroup\$
    – Quadruplay
    Mar 25 at 1:20
2
\$\begingroup\$

Swifty Argument Labels

\$\endgroup\$
2
  • \$\begingroup\$ So empty input just behave as _ \$\endgroup\$
    – l4m2
    Mar 21 at 1:32
  • \$\begingroup\$ @l4m2 Yeah, pretty much. I should probably simplify that... gimme a sec to edit. \$\endgroup\$ Mar 21 at 11:14
2
\$\begingroup\$

Output a 1-2-3 sequence

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

Is it a cartesian product?

\$\endgroup\$
9
  • \$\begingroup\$ Without order maybe better called multiset \$\endgroup\$
    – l4m2
    Apr 6 at 8:45
  • \$\begingroup\$ Diff set and multiset, [1,1][1,1][1,2][2,1][2,2] \$\endgroup\$
    – l4m2
    Apr 6 at 8:45
  • \$\begingroup\$ Is this equivalent to the matrix counting appearances of pairs being of rank 1? \$\endgroup\$ Apr 7 at 6:16
  • \$\begingroup\$ Can the input list be empty? Can it be taken as a matrix, counting the number of appearances of each pair? \$\endgroup\$ Apr 7 at 6:16
  • \$\begingroup\$ @CommandMaster I specified "nonempty". Taking it as a matrix seems a bit too different from the input format I have here, so I'll say no on that one. I'm not sure whether it's equivalent to that problem. \$\endgroup\$
    – emanresu A
    Apr 7 at 6:24
  • \$\begingroup\$ @l4m2 I'm trying to keep things somewhat simple, so I'll stick with list. I'll add that testcase \$\endgroup\$
    – emanresu A
    Apr 7 at 6:25
  • \$\begingroup\$ If it's list then [[1,4],[1,6],[2,4],[7,4],[7,6],[2,6]] would be false, [1,2,7]x[4,6] should be [[1,4],[1,6],[2,4],[2,6],[7,4],[7,6]] \$\endgroup\$
    – l4m2
    Apr 7 at 6:31
  • \$\begingroup\$ @l4m2 I guess you're right that changing everything to multiset is the easiest way to show that order doesn't matter, I've also clarified that elements can be repeated. \$\endgroup\$
    – emanresu A
    Apr 7 at 6:35
  • \$\begingroup\$ typo? multiset list -> multiset \$\endgroup\$ Apr 23 at 23:58
2
\$\begingroup\$

Interpret PlusOrMinus

PlusOrMinus is an esoteric programming language invented by Esolang user PythonshellDebugwindow.

Language specification

There is a wrapping byte accumulator (incrementing 255 results in 0 and decrementing 0 results in 255) in the language.

There are two instructions in the language:

  • +, which increments the accumulator.
  • -, which prints the accumulator as ASCII (e.g.: A if accumulator is 65), then decrements the accumulator. Other characters are ignored.

Examples

Here are some examples to test your programs:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-++++++++++++++++++++++++++++++-++++++++-+-++++-++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-++++++++++++++++++++++++++++++++++++++++++++++++++++++++-+++++++++++++++++++++++++-++++-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

Prints Hello, World!.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-++++++++++++++++++++++++++++++++++-++-++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

Prints Nope..

Goal

This is , so you goal is to use the fewest bytes to interpret the language. The program to interpret can be from console input, file input or string.

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

Enumerate all matches of a regex

\$\endgroup\$
9
  • \$\begingroup\$ Seems brute-forcing all strings and test would be shorter in most languages \$\endgroup\$
    – l4m2
    Apr 22 at 1:14
  • 1
    \$\begingroup\$ Suggest a*a* multiple possible match way \$\endgroup\$
    – l4m2
    Apr 22 at 1:15
  • \$\begingroup\$ a** might also be tricky \$\endgroup\$
    – xnor
    Apr 22 at 2:36
  • \$\begingroup\$ is ab* valid? (according to your specification, (ab)* or a(b)* is valid, but ab* is not) \$\endgroup\$
    – tsh
    Apr 22 at 11:56
  • \$\begingroup\$ Suggest testcase: ((((a|a))*|a))* \$\endgroup\$
    – tsh
    Apr 22 at 11:57
  • \$\begingroup\$ (a|b)* output seems wrong, missing aa and ab (and similarly for longer strings) \$\endgroup\$
    – DLosc
    Apr 22 at 14:58
  • \$\begingroup\$ This behavior is a subset of Regenerate with the -a flag. \$\endgroup\$
    – DLosc
    Apr 22 at 15:07
  • \$\begingroup\$ @tsh That's just for consistency's sake, a(b)* means the same thing as ab* would in normal regex. And apparently I completely forgot about that while writing the testcases, fixed now \$\endgroup\$
    – emanresu A
    Apr 22 at 19:41
  • \$\begingroup\$ @DLosc Fixed, and yes regenerate somewhat inspired this challenge. \$\endgroup\$
    – emanresu A
    Apr 22 at 19:45
1
47 48
49
50 51
157

You must log in to answer this question.

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