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\$
0

4634 Answers 4634

1
47 48
49
50 51
155
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\$

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\$

Sum up snail number neighbours

\$\endgroup\$
1
\$\begingroup\$

I've Got The Key, I've Got The Secret

A cryptography challenge in 2 parts.

Part 1

Implement a pair of programs in any language (the two programs could be in different languages if you wanted) to encode and decode a string of plaintext.

Input and Output

The encoder must take the plaintext (and an optional key) and return an encoded string. The decoder must take the cyphertext (and an optional key) and return the plaintext exactly as it was given to the encoder.

Restrictions

  • The encoding and decoding code must be entirely implemented in the language - no libraries or cryptography functions may be used.
  • The code (encoder+decoder) cannot be longer than 1024 characters.

Part 2

Implement programs (multiple programs per answer, one answer per entrant) which crack your opponents encryption algorithms.

Input

The cyphertext.

Output

The plaintext that generated the ciphertext.

Scoring

I will upvote all answers to part 1 which have working encryption and have obviously made an attempt at golfing their answer.

In order to be eligible to win, an entrant will have to have taken part in both parts of the question. Overall score will be (length of shortest program that cracks your code-(length of encoder+length of decoder)). Highest score wins and winning entrant's entries will be accepted on both questions.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ The obvious place for this to fall flat on its face is if someone is able to implement AES or something similar within the 1024 character restriction. \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 13:06
  • 1
    \$\begingroup\$ Probably better if the methods of the part one programs are disclosed in non-obfuscated language, though with the short length restriction this may not be necessary. \$\endgroup\$ Jun 13, 2012 at 15:23
  • 3
    \$\begingroup\$ Forget AES: RSA is easily doable. That aside, you need to define "crack" in part 2. \$\endgroup\$ Jun 13, 2012 at 15:35
  • 1
    \$\begingroup\$ Also, it's not clear whether "optional key" means that it's optional to make the algorithm unkeyed (doesn't make much sense, I admit) or optional to supply it, in which case it uses a default key. \$\endgroup\$ Jun 13, 2012 at 15:42
  • 1
    \$\begingroup\$ @PeterTaylor I just put optional in to leave it up to the implementer whether or not they wanted to have the key input or hard-coded (or use no key). I'd have thought everyone would have the key input into their program, but I didn't want anyone to feel forced into it by the spec. Hmm, if RSA is doable within the character restriction I'll end up with a load of unbreakable codes which would make for a pretty crap part 2. By crack I meant cyphertext goes in, some time later plaintext comes out. Would restricting the character count further help, or is this question beyond help? \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 16:05
  • 3
    \$\begingroup\$ On that definition of crack, I can brute force for the length of the decoder plus a few bytes to iterate over all keys of the right length and some heuristics to check plausibility of the plaintext. The brute force cracker might even be shorter than the decoder if the decoder wasn't written in GolfScript... I think this question may be beyond help. \$\endgroup\$ Jun 13, 2012 at 16:28
  • 3
    \$\begingroup\$ @PeterTaylor Okay, thanks. I like the 'build your own - knock everyone else's down' aspect of this question though. I'll have to find another area where it could apply. \$\endgroup\$
    – Gareth
    Jun 13, 2012 at 16:34
  • 2
    \$\begingroup\$ @Gareth I too like the competitive nature of this idea. I'm looking forward to a question with this plan in mind! \$\endgroup\$
    – Gaffi
    Jun 13, 2012 at 19:31
  • 2
    \$\begingroup\$ I think it would be better to split this into a "cops" post and a "robbers" post. \$\endgroup\$
    – wizzwizz4
    Feb 16, 2017 at 9:46
  • 1
    \$\begingroup\$ @wizzwizz4 Wow, this is another blast from the past. I think this pre-dates the cops-and-robbers tag. I always seem to be ahead of my time. :-) \$\endgroup\$
    – Gareth
    Feb 16, 2017 at 9:49
1
\$\begingroup\$

Countability of Sets of Finite Sets

The aim of this challenge is to code-golf a program which returns an iterator that will iterate over all possible non-empty finite sets of positive integers.

So if running long enough, this iterator should eventually touch on {1}, {2, 5}, {3, 6, 112} (ie none of these should occur "at infinity")

You may choose the order in which you iterate over these sets, but the order must satisfy the following requirement:

Under a particular ordering, if S is the i'th set to be returned by the iterator, then we shall call i the index of set S.

Let a restriction (k,T) be an assertion about a set S that says S has size k and T is a subset of S.

For a given restriction (k,T) and iterator IT, let the restricted iterator be the iterator which takes sets returned by IT and filters out sets that don't satisfy the assertion, iterating only over the ones that do. In other words, if IT iterates over the sequence of all sets, the restricted iterator iterates over the subsequence satisfying (k,T). Now if S is the n'th set returned by the restricted iterator, then we'll call n the restricted index of S with respect to (k,T)

Your ordering must satisfy the property that for any restriction there exists a polynomial P(x) such that for any set satisfying the restriction (with index i and restricted index n), i < P(n)

Note that the following ordering is not acceptable:

{1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3} {4} {1, 4} {2, 4}...

This is the sequence that comes from counting 1, 2, 3, 4, 5, 6... and listing the set bits in the binary representation of each number.

This is because the restriction (1, {}) satisfies only the sets {1}, {2}, {3}, {4}... whose index i as a function of their restricted index is i=2^(n-1) which is not bounded by any polynomial


Sandbox Questions

The reason for the strange requirement at the end is to disqualify any variants on the most natural ordering which simply counts upwards from 1 and enumerates the set bits in each number. In this ordering, the n'th set of length-one occurs at index 2^n which is non-polynomial.

I posted this problem originally, but didn't think of the obvious solution and so I left out the final restriction. I'd like to re-post it with the extra restriction. But first I'd like to know what people think. Is there a better way I can word that restriction or a more natural restriction I could impose instead?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I don't understand the extra restriction, so I can't suggest a rewording, but I can say that it needs one. (In particular: what is k? And what function does T serve? Is it really a parameter of the property?) \$\endgroup\$ Jun 18, 2012 at 8:25
  • 1
    \$\begingroup\$ I don't understand it either. Maybe a sample of an ordering, satisfying the requirement, and another one, violating it, would help. \$\endgroup\$ Jun 18, 2012 at 15:31
  • 1
    \$\begingroup\$ I understand the restriction now, although I haven't worked through the full implications. Does allowing T to be non-empty make a significant difference at all? \$\endgroup\$ Jun 19, 2012 at 6:52
  • 1
    \$\begingroup\$ I don't know. It may not. I guess the size part is the important part. I was just thinking that the ordering should be such that you run into all kinds of sets frequently. \$\endgroup\$
    – dspyz
    Jun 20, 2012 at 7:17
1
\$\begingroup\$

The One with Two Parts

The aim of this challenge is to create a pair of functions which scramble and unscramble any given piece of text.

Part 1

In part one you post your scrambling function, along with the length in characters and language of your unscrambling function (but NOT its code). The length of the scrambler does not affect your score so you needn't golf it unless you want to. The two functions may be written in different languages if you wish.

Input/Output

The scrambling function should take one argument only - a string containing the input text - and return a string containing the scrambled text. The unscrambling function should also take only one argument - the scrambled text - and return the original text. The input text will be limited to characters in the ASCII set range from 0 to 127.

Part 2

In part two you try to beat your opponents' scores for their unscrambling functions. You MUST use the language they specify for their unscrambler in part one. Please give just one answer to this question containing all your unscrambling functions making it clear which question in part one each function unscrambles (maybe each answer in part one should give its scrambler a name for identification?).

Once the closing date (TBA) has passed all participants should post their unscrambling functions in their answer to part one to prove the length, language and functionality of their function.

Scoring The participants score will be calculated as follows: (unscrambler length from part one) - (shortest unscrambler length from part two). The participant with the lowest score wins and will have their answers accepted on both parts of the challenge. To be eligible to win a participant must have taken part in both parts of the question.

Example

In part 1:

  • Bob posts a Python answer and says his unscrambler is a 165 character Python function.
  • Fred posts a GolfScript answer and says his unscrambler is a 59 character GolfScript function.
  • Joe posts a JavaScript answer and says his unscrambler is a 180 character PHP function.
  • Jim posts a Ruby answer and says his unscrambler is 163 character Ruby function.

In part 2:

  • Bob posts an 82 character GolfScript function to unscramble Fred's scrambled text. He also posts a 175 character PHP function to unscramble Joe's scrambled text.
  • Fred posts a 181 character PHP function to unscramble Joe's scrambled text.
  • Joe posts a 150 character Python function to unscramble Bob's scrambled text.
  • Jim posts a 156 character Python function to unscramble Bob's scrambled text. He also posts a 91 character GolfScript function to unscramble Fred's scrambled text.

The scores:

  • Bob scores 165 - 150 = 15
  • Fred scores 59 - 82 = -23
  • Joe scores 180 - 175 = 5
  • Jim scores 163 - 0 = 163

so Fred wins.

Miscellaneous

I suggest that the closing date be two weeks after the challenge begins, and that unscramblers be posted to part one within 48 hours of closing date in order to be eligible.

\$\endgroup\$
6
  • \$\begingroup\$ Are there any rules regarding scrambling? i.e. is "Stockholm"->"Stockhoml" a valid scramble? (it may not matter, but I'm curious. And to be clear, the scoring is the difference between your opponent's unscrambler length and your own for the same language? \$\endgroup\$
    – Gaffi
    Jul 16, 2012 at 16:39
  • \$\begingroup\$ @Gaffi No, you scramble however you want. If you want to just output the text as given that's ok, but you probably won't win with that strategy. The aim is to do it in a way that is easy for you to unscramble but difficult for all the others. That way your score will be smaller. Yes, the score is the difference between your score and the score of the best of your opponents' attempts. I'll add an example to make that bit clearer I think. \$\endgroup\$
    – Gareth
    Jul 16, 2012 at 21:27
  • \$\begingroup\$ I think this gives an advantage to people who use (relatively) obscure languages. If the scrambler is written in J and the descrambler in GolfScript then only people who know both can realistically attempt a descrambler. (NB the rules don't say how the score works if no-one attempts a particular unscrambler). \$\endgroup\$ Jul 17, 2012 at 6:59
  • \$\begingroup\$ I did consider saying that programs that had no attempts at beating them were not eligible to win, but then I thought that if they were scored as though the shortest attempt to beat them was 0 then they wouldn't have much of an advantage. I'll add that into the example scoring. What do you think? I want to encourage answers that are clever or well obfuscated rather than written in Malbolge or something like that. \$\endgroup\$
    – Gareth
    Jul 17, 2012 at 7:28
  • 1
    \$\begingroup\$ Does it mean that since no one attempts to solve Jim's Ruby challenge his chances are minimal that he'll win? That would discourage complicated scramblers or difficult languages. \$\endgroup\$
    – Howard
    Jul 17, 2012 at 17:12
  • \$\begingroup\$ @Howard As it stands, yes that's how it would work. The alternative, as Peter Taylor points out, is that people using obscure languages have an advantage. I'm not sure how else I might score unscramblers that no-one has attempted to beat. Maybe give them a score of 0? Please, if you or anyone else has any suggestions for making the challenge as inclusive as possible, let me know. \$\endgroup\$
    – Gareth
    Jul 17, 2012 at 17:51
1
\$\begingroup\$

Compile BF to TM

Your task is to write a compiler accepting a Brainfuck program (previous challenge: Interpret Brainfuck, wikipedia: Brainfuck) as input and outputting a Turing Machine which produces identical output when supplied with the same (correct) input.

You may select the output format from among the various formats accepted by the answers to Turing Machine Simulator.

The following links may also be useful.
An introduction to programming in BF
BF is Turing-complete
Programming a Turing Machine
Programming Praxis: Turing Machine Simulator

Equivalently, you may write a Brainfuck interpreter in TM, or any partial compilation/interpretation which results in a TM program as described above.

If we consider squares of the TM tape to represent bits (blank=0, mark=1) of the BF memory, then eight squares represent a cell. Each BF instruction translates to a minimum of 8 states of the Turing Machine.

'>' "advance" (++ptr) could be implemented by eight states (sixteen transitions):

adv8 _ adv7 R _
adv8 1 adv7 R 1
adv7 _ adv6 R _
adv7 1 adv6 R 1
adv6 _ adv5 R _
adv6 1 adv5 R 1
adv5 _ adv4 R _
adv5 1 adv4 R 1
adv4 _ adv3 R _
adv4 1 adv3 R 1
adv3 _ adv2 R _
adv3 1 adv2 R 1
adv2 _ adv1 R _
adv2 1 adv1 R 1
adv1 _ link R _
adv1 1 link R 1

where 'link' represents the first state of the following instruction.

'<' "rewind" (--ptr) can be implemented similarly by making leftward movements and rewriting the same symbol just read.

'+' "increment" (++*ptr) can be implemented by a ripple-carry from the Least Significant Bit to the Most Significant Bit, borrowing "rewind" states to back-up to normal position. If the LSB is on the left, it would look something like this:

inc8 _ link N 1
inc8 1 inc7 R _
inc7 _ rew1 N 1
inc7 1 inc6 R _
inc6 _ rew2 N 1
inc6 1 inc5 R _
inc5 _ rew3 N 1
inc5 1 inc4 R _
inc4 _ rew4 N 1
inc4 1 inc3 R _
inc3 _ rew5 N 1
inc3 1 inc2 R _
inc2 _ rew6 N 1
inc2 1 inc1 R _
inc1 _ rew7 N 1
inc1 1 overflow N 1

where overflow is a HALT state.

For I/O, the simplest way I can think is to place all input on the tape after the memory area, and expand the alphabet to include a symbol indicating the dividing line between the memory portion and the input portion of the tape. In fact, by expanding the cell size to nine squares, this symbol can serve as an input pointer, advancing as the input is consumed. (So "advance" and "rewind" now need 9 states each.) And another new symbol is written in front of the current memory cell to serve as the memory pointer. Inputting a byte therefore consists of schleping each bit over the entire space between the two tape positions with something like this:

input _ set-memptr L _
input 1 set-memptr L 1
set-memptr _ find-inptr R *
find-inptr _ find-inptr R _
find-inptr 1 find-inptr R 1
find-inptr $ schlep-bit R $
schlep-bit _ schlep-blank L _
schlep-bit 1 schlep-one L 1
schlep-blank $ schlep-blank L $
schlep-blank _ schlep-blank L _
schlep-blank 1 schlep-blank L 1
schlep-blank * deposit-blank R *
schlep-one $ schlep-one L $
schlep-one _ schlep-one L _
schlep-one 1 schlep-one L 1
schlep-one * deposit-one R *
deposit-blank _ etc R _
deposit-blank 1 etc R _
deposit-one _ etc R 1
deposit-one 1 etc R 1

where "etc" represents going to get the next bit in similar fashion.

To perform a loop (all BF loops are "while" loops, so the exit control is at the beginning and the end has a simple goto back to the beginning), we need first to check is the current cell is zero,

zero8 _ zero7 R _
zero8 1 body R 1
zero7 _ zero6 R _
zero7 1 left1 L 1
zero6 _ zero5 R _
zero6 1 left2 L 1
zero5 _ zero4 R _
zero5 1 left3 L 1
zero4 _ zero3 R _
zero4 1 left4 L 1
zero3 _ zero2 R _
zero3 1 left5 L 1
zero2 _ zero1 R _
zero2 1 left6 L 1
zero1 _ exit-loop R _
zero1 1 left7 L 1
left7 _ left6 L _
left7 1 left6 L 1
left6 _ left5 L _
left6 1 left5 L 1
left5 _ left4 L _
left5 1 left4 L 1
left4 _ left3 L _
left4 1 left3 L 1
left4 _ left3 L _
left4 1 left3 L 1
left3 _ left2 L _
left3 1 left2 L 1
left2 _ left1 L _
left2 1 left1 L 1
left2 _ loop-body L _
left2 1 loop-body L 1
...
loop-body-final _ zero8 N _
loop-body-final 1 zero8 N 1

So assuming the machine starts at tape-location 0, and the input is on the tape starting at 0 and going to the right, the "startup code" for this arrangement would be

startup _ place$ L _
startup 1 place$ L 1
place$ _ left270000 L $
left270000 _ left269999 L _
...

Jeez! The output is going to be HUGE! It might be better to treat the BF memory as negative-indexed and reverse all the _L_s and _R_s in 'advance', 'rewind', 'increment', and 'decrement'.


Questions:

Bonuses for optimizations? If I can implement this myself and provide a complete example output, The bonus could be "subtract the difference between your program's output for the example input with the example output". So eliminating states would be far more valuable than shrinking the code. One could possibly achieve a negative score!


Edit: Actually I think this is unreasonable unless the Turing Machine is augmented with non-reading (movement-only or epsilon) transitions. Duplicating every letter of the alphabet just to move over one square is just ridiculously painful. That means this challenge won't link-up nicely with the other one. :(

What about, instead of implementing the compiler, just devise a translation scheme (as above) that leads to a smaller output for a trivial sample program (based on calculating, rather than coding)? "Back of the envelope" compiler.

\$\endgroup\$
8
  • \$\begingroup\$ "How much detail on BF do I need to supply? Can I simply reference the BF question?" A link to almost any site that describes the language will do. \$\endgroup\$ Nov 5, 2012 at 16:52
  • \$\begingroup\$ Winning condition? \$\endgroup\$ Nov 6, 2012 at 13:43
  • \$\begingroup\$ "Longest prefix containing syntactically-correct Malbolge!" :) ... I'd say have none at all. Perhaps the questioner should be required to accept their own example answer? \$\endgroup\$ Nov 6, 2012 at 18:08
  • \$\begingroup\$ @PeterTaylor Apologies for my last comment. I thought we were on my other answer about the [fun] tag. . . . This one would be a golf: shortest code by character count. But I think a clever system of bonuses could make it interesting. \$\endgroup\$ Nov 7, 2012 at 10:06
  • \$\begingroup\$ The "Equivalently, you may write a Brainfuck interpreter in TM" option doesn't play very well with being a code golf - how are you going to count the length of the TM? \$\endgroup\$ Nov 7, 2012 at 11:15
  • \$\begingroup\$ @PeterTaylor Since the TM question specified 5-tuples, I think it's sufficient to count the tuples (== transitions). You can reduce states by increasing the alphabet (or vice versa), but the transitions would remain constant, I think. \$\endgroup\$ Nov 8, 2012 at 5:25
  • \$\begingroup\$ I'd like to adopt (work on and post) this challenge if you don't want to. Would I be able to? If you do not respond to this message within two weeks, by community guidelines, I am allowed to take it over. \$\endgroup\$
    – MD XF
    Aug 18, 2017 at 3:23
  • \$\begingroup\$ Yes, please. If you can do something with it, strike while the iron is hot. \$\endgroup\$ Aug 18, 2017 at 4:19
1
\$\begingroup\$

Graphical Output -- Esoteric Artifacts -- The Glass Bead Game

Draw the Cabalistic Tree of Life

Simply described, the Tree of Life is an undirected network of nodes representing the conduit between matter and higher forms of spiritual energy. It has an upper face arranged in a hexagon, and a lower fact built from equilateral triangles adjacent to the lower two edges of the upper face. Don't label the paths, paths may overlap however you wish, may be single (thick) lines, even. Code Golf. Bonus -100 for labels on the Sephiroth (nodes); Bonus -150 for Hebrew labels.

Tree of Life after Kirtcher

Draw a Mandala for each Natural Number

Draw a circle with interesting visual patterns using the input N [ 1 .. \inf ) to determine the number of points around the circle to anchor figures whose shape is also modified by the input N. Actually, 12 seems like a good max: they're pretty much a blur after that no matter what.

Eg. http://code.google.com/p/xpost/downloads/detail?name=ve6a.ps
//lotsoflines n = 1 ..12

Mandalas 1 - 12

(doesn't need to be this elaborate, This is >600 lines of showing-off.).

. . . need good images for these . . .

Draw the Ptolemeic System of the Universe

All the stuff I could find is animated already. Maybe this one's done-to-death. :(

Update: Found good stuff on Alchemy. The "Keplar Platonic" model could be fun (3D and all). This one looks good, too. And this.

Draw the Pythagorean Monochord

aka pre-classical nomogram. I misplaced my Pythagoras books, I know I've got a picture somewhere.

This is the one I was thinking of.

But I think this one's even cooler

Draw the I-Ching Hexagrams in King Wen Sequence.

I suppose I need to implement this first to avoid copyright issues! :)

\$\endgroup\$
3
  • \$\begingroup\$ The I-Ching one would have to be in standard order to be remotely interesting, and then becomes as much about kolmogorov-complexity as graphical-output \$\endgroup\$ Nov 22, 2012 at 21:24
  • \$\begingroup\$ For the others: images, please! \$\endgroup\$ Nov 22, 2012 at 21:25
  • \$\begingroup\$ I've emailed the owner of the Alchemy pages asking for permission to use his copyrighted images. Awaiting response. \$\endgroup\$ Jan 28, 2013 at 8:25
1
\$\begingroup\$

Self-Golfing Code?

I don't know if I just didn't search hard enough, but I couldn't find any challenge regarding self-golfing code, or rather, any code that can deterministically reduce another set of text code to a much smaller program, yet still compile/run.

For example, take this:

int main() {
std::cout<<"Hello world 1!"<<std::endl;
std::cout<<"Hello world 2!"<<std::endl;
std::cout<<"Hello world 3!"<<std::endl;
std::cout<<"Hello world 4!"<<std::endl;
std::cout<<"Hello world 5!"<<std::endl;
}

And output this (as one possible solution):

#define A std::cout<<"Hello world 
#define B !"<<std::endl;
#define C B A
int main() {
A 1 C 2 C 3 C 4 C 5 B
}

Alternative:

Sub MySub()
Dim aNumber As Integer
Dim someString As String
aNumber = 123
someString = "abc"
MsgBox aNumber
MsgBox someString
End Sub

into (again, as one possible solution)

Sub m()
Dim a As Integer
Dim s As String
a = 123
s = "abc"
MsgBox a
MsgBox s
End Sub

Do we have a challenge for this?

If not, here are some rules I envision:

  • Golfing code need not be in the same language as code to be golfed.
  • Since compilers/running of code varies, newly golfed code must still run under same environment.
  • Possible challenge scoring (multiple options -- thinking code golf):
    • 1: Shortest golfing code wins (not my favorite, since you can minimally shorten the base code, yet still write the shortest program).
    • 2: Shortest output of a set of pre-defined code (potentially limiting if participants are unfamiliar with the options available)
    • 3: Combination of length of golfing code and the output result of the same as input. (Ratio, summation, etc.) -- This I think is my preferred option.
    • 4: Multi-player Ratio of golfed size of other participants' own code versus their original submission. (Similar limitations to that of point #2.)
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Sounds more like an auto-golfer than obfuscation. Seems like it would be very hard to make it a fair contest unless you pick a language to golf, and even then it had better be a simple language (no platform dependency issues or compiler options). \$\endgroup\$ Feb 13, 2013 at 15:15
  • \$\begingroup\$ @PeterTaylor My examples are golfing, but either would work. Perhaps golfing would be simpler, then? I agree that the options for usable languages makes this a bit messy... Would one challenge per language be acceptable? (i.e. aligned with most challenges that are language-agnostic) \$\endgroup\$
    – Gaffi
    Feb 13, 2013 at 17:36
  • 2
    \$\begingroup\$ Language-agnostic to mean means that you can write a program to do it in any language. Since the language to be golfed can be different from the submitted program, I don't see any incompatibility between making the problem "Write a program to golf Piet" and being language-agnostic. \$\endgroup\$ Feb 15, 2013 at 0:18
  • \$\begingroup\$ @PeterTaylor So then you see no problem with one question per language on which to operate? Are there any proposed scoring algorithms you particularly like/dislike? \$\endgroup\$
    – Gaffi
    Feb 15, 2013 at 12:02
  • \$\begingroup\$ That depends on what you mean. If you're planning to post 10 questions at once, yes, that would be a problem. But I don't see a problem with posting a well-defined "Auto-golf Piet" and following it up two months later with "Auto-golf Perl 5". \$\endgroup\$ Feb 16, 2013 at 10:19
  • \$\begingroup\$ Scoring is an issue. The halting problem means that it's impossible to write an optimal solution, so the scoring must take into account how good the solution is. I think option 3 is the best, and you'll want a big test set (maybe a few kB taken from a real-world open source project) with coverage of the language features. \$\endgroup\$ Feb 16, 2013 at 10:22
  • \$\begingroup\$ Btw, your first example doesn't work. You can't have unmatched quotes in preprocessor directives. Don't know why. \$\endgroup\$
    – MD XF
    Jan 13, 2018 at 18:03
  • \$\begingroup\$ I honestly think this would be fine if you did something like solely maco-golfing, making it somewhat language agnostic because of gcc -E. \$\endgroup\$
    – Adalynn
    Nov 10, 2018 at 14:36
1
\$\begingroup\$

DeCSS

It is known that the DVD Content Scrambling System can be deciphered with a rather short program (434 bytes of C, 472 bytes of Perl). Can you do better?

<< Test cases go here >>


I don't plan to include a more detailed spec, because it will just wind up duplicating some of the code. The test cases would be in the form of (key, link to data file, md5sum of the deciphered stream).

\$\endgroup\$
4
  • 3
    \$\begingroup\$ And the winning criterion is who is the first to get post from the courts? \$\endgroup\$
    – celtschk
    Oct 3, 2015 at 20:18
  • 1
    \$\begingroup\$ @celtschk, I think that would be unfair. Winning criteria shouldn't really depend on where people live... \$\endgroup\$ Oct 10, 2015 at 20:56
  • 3
    \$\begingroup\$ I think you should at least explain the general concept of the spec. \$\endgroup\$ Aug 2, 2016 at 22:53
  • 1
    \$\begingroup\$ This actually sounds interesting. @PeterTaylor Perhaps you could use (and link to) Charles Hannum's explanation of the algorithm and post this. (It would be fun to have it as a popularity contest for a program that looks like it's nothing DeCSS related, or a program that furthers the gallery's point about the text vs source code arbitrary distinction - but I don't know if popularity contests are popular any more!) \$\endgroup\$
    – Sundar R
    Jun 25, 2018 at 8:25
1
\$\begingroup\$

Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

  • interpreting the language is fine
  • translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

  • Lisp
  • APL
  • J
  • Brainfuck (already posted)
  • Whitespace
  • Forth
\$\endgroup\$
6
  • 1
    \$\begingroup\$ This only works for languages which are small and well defined. BF fits those criteria. Whitespace does too. The others may not. Lisp and Forth have so many dialects that you would have to specify exactly which dialect to support; Lisp, Forth, APL and J might have too many built-ins to fit in an answer: there are character limits. \$\endgroup\$ May 12, 2013 at 15:16
  • \$\begingroup\$ You don't have to provide all the built-ins, but that is why it is here. \$\endgroup\$ May 12, 2013 at 15:38
  • \$\begingroup\$ What defines the "basic commands"? \$\endgroup\$ Aug 31, 2015 at 17:54
  • \$\begingroup\$ I don't know? Maybe that you can do the basic stuff with it like +,-,print,... \$\endgroup\$ Aug 31, 2015 at 18:22
  • 1
    \$\begingroup\$ I suggest a programmer can implement the tiniest subset of those languages in order to be Turing-complete, as these are non-trivial subsets that can theoretically simulate the rest of the language... \$\endgroup\$
    – user85052
    Jun 28, 2019 at 4:17
  • \$\begingroup\$ Which human is learning the programming language by looking at the code? \$\endgroup\$
    – MilkyWay90
    Aug 26, 2019 at 3:23
1
\$\begingroup\$

Missile Command

I'm making this CW, because it needs lots of help. I've been toying with this idea for a while. Think "battleship" to get in the right mind-frame. But, instead of ships, what you lay down are tiles which represent a Befunge-style program. This program controls the behavior of guided missiles ejected from the spawn tile. The goal is to program a missile which will obliterate an opponent's program block, as well as guard its own control block.

Haven't nailed-down the board size. 20x20 seems a little cramped.

         1         2
12345678901234567890
____________________1  4x20 program block
____________________2
____________________3
_______@____________4
....................5  12x20 arena
....................6
....................7
....................8
....................9
....................01
....................1
....................2
....................3
....................4
....................5
....................6
___________@________7  4x20 program block
____________________8
____________________9
____________________02

Tiles

@ spawn

Program control.

I'm imagining these to change direction of the code for "boustrophedon" writing.

this,then\
 txen,siht

haven't thought it all though, yet.

/

\

Movement.

F forward move forward one square

B back move back one square

L left turn left 90°

R right turn right 90°

So the submissions would be 4x20 code blocks which compete in a king-of-the-hill style.

\$\endgroup\$
2
  • \$\begingroup\$ If this is deterministic, won't it be "Last person to submit their program wins"? \$\endgroup\$ Jun 7, 2013 at 8:39
  • \$\begingroup\$ That is a danger, yes. I'm hoping ways around it can be found. There could be a random operator. And proximity detection, or something. \$\endgroup\$ Jun 7, 2013 at 8:46
1
\$\begingroup\$

Find all of the Scrabble numbers:

A scrabble number is a number n whose scrabble representation can score n points. As an example consider 12: its English spelling twelve has value 12 when it is placed on a stretch of six blank tiles. Since the highest ever reported 1 word scrabble score barely exceeds 2000 points, that will be the upperbound for this challenge.

Score and quantities for English:

2 blanks |  x1  |  x2  |  x3  |  x4  |  x6  |  x8  |  x9  |  x12 |
    1    |      |      |      | LSU  | NRT  | O    | AI   | E    |
    2    |      |      | G    | D    |      |      |      |      |
    3    |      | BCMP |      |      |      |      |      |      |
    4    |      | FHVWY|      |      |      |      |      |      |
    5    | K    |      |      |      |      |      |      |      |
    8    | JX   |      |      |      |      |      |      |      |
   10    | QZ   |      |      |      |      |      |      |      |

Considerations for either bonus points to scoring or extra requirements:

  • Respect the board, only using gaps between double/triple letter and double/triple word scores that occur on a standard scrabble board.
  • Respect the tile count for each letter.
  • There are non-English versions of scrabble, maybe it should be 'language-agnostic' (lol, but seriously is there a reason to accept only English submissions?).
  • Should the 2 blanks be allowed?
\$\endgroup\$
3
  • \$\begingroup\$ What about tiles which were already on the board and so wouldn't score anything? As for language: one approach would be to make it take the names of the tiles (and perhaps the values and counts of the letters) as input; this would also prevent the problem from being effectively one of Kolmogorov complexity. \$\endgroup\$ Jun 19, 2013 at 22:50
  • \$\begingroup\$ I don't believe that tiles on the board already would pose an issue. If you assume that the board may be prepared with any subset of the tiles beforehand (some may be impossible, but checking that is out of scope) all that is relevant to the problem is which are placed to complete the word. All the tiles points are counted, even the earlier placed, but only the new 7 (or less) tiles may qualify for triple/double-word/letter scores. w.r.t. kolmogorov, If I wanted to make it programming challenge instead of codegolf (so that isn't an issue) then there needs to be a scoring system right? \$\endgroup\$
    – Kaya
    Jun 19, 2013 at 23:33
  • \$\begingroup\$ Yes, if it isn't codegolf then it needs a scoring system. I'm not sure what you could use as an alternative scoring criterion, though: it's simple enough logic that pretty much any implementation would be IO-bound, so speed doesn't work; and big-O based tends to be less straightforward than you might think. \$\endgroup\$ Jun 21, 2013 at 11:05
1
\$\begingroup\$

Sort all lines according to their corresponding Levenshtein Distance to the first line.

Shamelessly borrowed from: http://golf.shinh.org/p.rb?Levenshtein+Distance+Sort+FIXED

For a definition of the Levenshtein Distance, look here: http://en.wikipedia.org/wiki/Levenshtein_algorithm

Rules:

Takes input from stdin. Must work for all possible input. Get points for:

Smallest character count. Using Languages that are difficult to golf in. I think character count / the average values from here (http://golf.shinh.org/lranking.rb) might suffice?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ There are a number of ambiguities in the problem description. What is the correct behaviour if the input is empty? In the general case, should the first line be included in the lines which are sorted and output? Should the sort be by ascending or descending edit distance? How should ties be broken? \$\endgroup\$ Jun 25, 2013 at 20:23
  • \$\begingroup\$ As for handicapping: are you going to prohibit built-in or library-provided edit distance functions? If not then the averages you link are not especially relevant: PHP handily wins the existing edit distance question by virtue of its built-in function. \$\endgroup\$ Jun 25, 2013 at 20:27
  • \$\begingroup\$ (That existing question does also raise the possibility of yours being closed for not being sufficiently different). \$\endgroup\$ Jun 25, 2013 at 20:28
1
\$\begingroup\$

Quine with syntax highlighting


I don't really have much of an idea how to properly pose a quine challenge, or what the common syntax highlighting rules are (or aren't) for various languages. So, I figured I'd just toss this concept up here for consideration and let the community flesh it out if they think it's a good idea.

\$\endgroup\$
6
  • \$\begingroup\$ I'm pretty sure some languages don't even have syntax to highlight \$\endgroup\$ Dec 13, 2013 at 20:12
  • \$\begingroup\$ @JanDvorak Perhaps this would not quite be an "all languages" challenge, then - only languages which naturally lend themselves to syntax highlighting would be eligible. \$\endgroup\$
    – Iszi
    Dec 13, 2013 at 20:19
  • \$\begingroup\$ You also can't use a language that cannot render any decent GUI. Also, specifying the amount of syntax highlighting the program needs to generate will be hell. \$\endgroup\$ Dec 13, 2013 at 20:36
  • \$\begingroup\$ I don't think this question is feasible, due to the output restrictions and due to the difficulty in defining the minimum required syntax highlighting. \$\endgroup\$ Dec 13, 2013 at 21:09
  • \$\begingroup\$ I like this idea. I think you could specify an adequate level of highlighting with just keywords, strings or characters and numeric literals each having their own color. \$\endgroup\$
    – Οurous
    Feb 28, 2018 at 21:13
  • \$\begingroup\$ How would the syntax highlighting apply to the output? \$\endgroup\$ Oct 26, 2021 at 18:39
1
47 48
49
50 51
155

You must log in to answer this question.

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