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

4629 Answers 4629

1
40 41
42
43 44
155
2
\$\begingroup\$

Find the k-th order summary of a number

Posted

\$\endgroup\$
2
  • \$\begingroup\$ very similar: codegolf.stackexchange.com/questions/70837/say-what-you-see \$\endgroup\$
    – Razetime
    Nov 4, 2021 at 2:15
  • \$\begingroup\$ @Razetime, yes they are quite similar, but the look and say operation is a bit different from the summary operation; for example look_and_say(112211) = 21 22 21 whereas summary(112211) = 41 22 \$\endgroup\$ Nov 4, 2021 at 5:51
2
\$\begingroup\$

Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an integer to each one which is simply its rank in the list.

For example, take \$\ell=7, s=5, m=4\$, the list could look like:

(0, 0, 0, 0, 0, 1, 4)  rank 1
(0, 0, 0, 0, 0, 2, 3)  rank 2
(0, 0, 0, 0, 0, 3, 2)  rank 3
(0, 0, 0, 0, 0, 4, 1)  rank 4
(0, 0, 0, 0, 1, 0, 4)  rank 5
(0, 0, 0, 0, 1, 1, 3)  rank 6
(0, 0, 0, 0, 1, 2, 2)  rank 7
(0, 0, 0, 0, 1, 3, 1)  rank 8
(0, 0, 0, 0, 1, 4, 0)  rank 9
[...]
(3, 2, 0, 0, 0, 0, 0) rank 449
(4, 0, 0, 0, 0, 0, 1) rank 450
(4, 0, 0, 0, 0, 1, 0) rank 451
(4, 0, 0, 0, 1, 0, 0) rank 452
(4, 0, 0, 1, 0, 0, 0) rank 453
(4, 0, 1, 0, 0, 0, 0) rank 454
(4, 1, 0, 0, 0, 0, 0) rank 455

This challenge requires you to produce two pieces of code/functions.

  • Given a rank, compute the corresponding array directly. Call this function unrank()
  • Given an array, compute its rank. Call this function rank()

Your code should run in polynomial time. That is it shouldn't be brute force and more specifically it should take \$O(\ell^a s^b m^c)\$ time for fixed non-negative integers \$a, b, c\$. Any non-brute force method is likely to satisfy this requirement.

Examples

unrank((7, 5, 4), 9) = (0, 0, 0, 0, 1, 4, 0)
rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451
unrank((14,10, 8), 100000)  = (0, 0, 0, 1, 0, 0, 1, 3, 1, 2, 0, 0, 2, 0)
rank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000000

Your score will be the total size for your code

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

Convert codepoint to UTF-9

\$\endgroup\$
4
  • 5
    \$\begingroup\$ For clarity, I'd start octal constants with 0o. Also, an explanation of how UTF-9 works should probably be included here. \$\endgroup\$ Jun 19, 2021 at 1:39
  • 2
    \$\begingroup\$ Could you include the basic algorithm to encode UTF-9 in your post instead of require an external resource? So this question can be made self contained. \$\endgroup\$
    – tsh
    Oct 12, 2021 at 6:27
  • \$\begingroup\$ @tsh Should I do with actual program source or in pseudo code? \$\endgroup\$
    – user100411
    Oct 12, 2021 at 12:26
  • \$\begingroup\$ first challenge that made me LOL \$\endgroup\$
    – don bright
    Oct 18, 2021 at 3:12
2
\$\begingroup\$

Lexigolf: Is this number a prime?

Write a program that, given a strictly positive integer n as input, determines whether n is prime and prints a truthy or falsy value accordingly.

For the purpose of this challenge, an integer is prime if it has exactly two strictly positive divisors. Note that this excludes 1, who is its only strictly positive divisor.

Goal

Competing programs are compared lexicographically. The program that is lexicographically less than all other programs is the winner.

If a program begins with a prefix that may be removed without altering the program's behavior, it is disqualified. This is to discourage adding meaningless whitespace or comments to change the first character (consider int main(){} or /**/int main(){}).

For example,

abc < def
aa < ba
aaaaaaa < aba
aa < aaaa
Zzz < aaa
012 < AAA

Meta

This is essentially an earlier classic code-golf challenge, Is this number a prime?, except with a different goal, which I propose is called lexigolf.

I'm not sure whether lexicographic order should entirely be based on UTF-8 (for languages that can be expressed in bytes). It seems to massively favor weird esolangs that rely on characters with small ASCII codes. There is also a loophole in prefixing the program with noop characters, e.g. placing a arbitrary amount of whitespace before a C program: int main() {} > int main(int, char**) {} > int main(int argc, char **argv) {} (fixed? probably still a loophole somewhere)

\$\endgroup\$
7
  • 1
    \$\begingroup\$ For the scoring favoring weird esolangs that rely on certain characters, the scoring here is typically a per-language comptition, so Java and GolfScript wouldn't be competing. The null byte prefixing is a bit of an issue, so you might want to require that you can't take any number of characters off the left side of the program without making it stop working (so prefixing a null byte wouldn't be allowed unless it actually affected how the program ran). Also, primality testing might not be the best challenge for this idea, since many golfing languages have it as one or two byte built-ins. \$\endgroup\$ Nov 16, 2021 at 17:42
  • \$\begingroup\$ @Fmbalbuena The < are to indicate which is lexicographically smaller, not which is winning \$\endgroup\$ Nov 16, 2021 at 17:43
  • 2
    \$\begingroup\$ You might want to allow language with SBCSs (custom code pages, instead of UTF-8 or ASCII) like Jelly to use those for the lexicographic order instead, since that would make it more interesting to try to find the lexicographically smallest program in those languages. \$\endgroup\$ Nov 16, 2021 at 17:46
  • \$\begingroup\$ @RedwolfPrograms, I've updated the post \$\endgroup\$
    – OLEGSHA
    Nov 16, 2021 at 17:51
  • 1
    \$\begingroup\$ In some languages (for example, Befunge) you could probably detect whether the leading spaces were removed... \$\endgroup\$
    – Maya
    Nov 16, 2021 at 22:19
  • 3
    \$\begingroup\$ Removing only prefixes isn't enough: I could add a test at the end to check whether that prefix is present. Maybe you should require the code to be irreducible instead? \$\endgroup\$
    – Dingus
    Nov 16, 2021 at 22:55
  • 4
    \$\begingroup\$ It seems like this challenge is entirely about finding the lexicographically smallest prefix that can be extended arbitrarily far in a way that removing a prefix of it will be invalid syntax or fail. The prime-finding task doesn't really matter -- any code is equivalent if put after arbitrarily much prefix padding. \$\endgroup\$
    – xnor
    Nov 17, 2021 at 2:12
2
\$\begingroup\$

Will one-cell brainfuck halt?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Do you really want use - for increment while + for decrement? Or maybe a typo? \$\endgroup\$
    – tsh
    Nov 10, 2021 at 10:17
  • \$\begingroup\$ @tsh Oops. Fixed. \$\endgroup\$
    – emanresu A
    Nov 14, 2021 at 1:01
2
\$\begingroup\$

Construct a Heptagon avoiding compass use

A while back I asked you to construct a pentagon avoiding compass use. Now flawr suggested:

Next time you should ask people to draw a heptagon, which would be slightly more challenging:)

This is of course a joke, because if you didn't already know it is not possible to construct a Heptagon using a ruler and compass ...

... in finite steps.

In this challenge answers will construct equilateral polygon of 7 sides, using a ruler and a compass.

We will begin with some standard ruler and compass operations:

  • Draw a line that passes through two non-identical points. (Ruler)

  • Draw a circle centered at one point such that another point lies on the circle. (Compass)

  • Place a point at an intersection of two non-identical objects (a circle and a line, a line and a line or a circle and a circle)

Normally a construction must be finished after some finite number of operations. However we will allow you to take any ordinal number of steps. Meaning you can perform an infinite number of steps and then perform more.

To go with this you are given one more operation:

  • Choose converging sequence of already drawn points and place a point at their limit. (limiting)

This operation is only meaningfully useful if you have already performed an infinite number of steps, but is crucial to constructing a heptagon.

Summary

In this challenge you will start with two arbitrarily placed (but non-equal) points on an infinite plane. You must then describe some sequence of steps to arrive at a regular Heptagon. Here a regular heptagon simply being 7 points which form the vertices of a heptagon, they do not need to be in any particular position relative to the starting points.

Your score will be the number of compass operations used in the entire proof with lower being better. Since many answers may end up using an infinite number of compass steps we will break ties by the strict supremum of ordinals representing steps you have used a compass.

For example if two answers both use an infinite number of compass operations, their primary score is \$\infty\$. If one of them uses all of their compasses at finite numbered their secondary score is \$\omega\$, which would beat the other answer if it uses the compass at any time \$\omega\$ and after.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The theoretical optimal score is likely 2. It is known that a circle and its center (with a couple other known points, because we can't create arbitrary point) plus straightedge operations equals general compass + straightedge in terms of constructibility. It must be possible to construct a sequence of constructible points that converges to a heptagon-related point. The actual challenge is coming up with a constructive solution. \$\endgroup\$
    – Bubbler
    Dec 6, 2021 at 2:01
2
\$\begingroup\$

How long will my microwave run for?

\$\endgroup\$
4
  • \$\begingroup\$ I'd recommend getting rid of the bonuses, they're pretty strongly discouraged \$\endgroup\$ Dec 3, 2021 at 17:32
  • \$\begingroup\$ @RedwolfPrograms I do like the bonus challenge, however I'm not sure what to do with it. \$\endgroup\$
    – Ginger
    Dec 3, 2021 at 17:33
  • 1
    \$\begingroup\$ You could just turn the bonus challenge into a separate question \$\endgroup\$
    – pxeger
    Dec 3, 2021 at 17:41
  • \$\begingroup\$ @pxeger I'll make it a seperate question and post it later. \$\endgroup\$
    – Ginger
    Dec 3, 2021 at 17:49
2
\$\begingroup\$

Operator precedence is dead

Calculate the result of some math expressions using the following constraints:

  • Numbers will be between 0 and 9
  • Operators are + - / *
  • Expressions will always have the format Number operator number operator number...
  • Parenthesis have the highest precedence
  • The order of reading goes Left Left Right Right Left Left Right Right etc.
  • Division by 0 never happen

For example:

1+3-4*9
1       = 1   ; Start calculating using the left most number
 +    9 = 10  ; Add 9
  3  *  = 30  ; Multiply by 3
   -4   = 26  ; subtract 4

Using this method 1+3-4*9 = 26

Input / Output

Input:

  • string OR list of characters OR list of numbers and characters
  • Can be reversed if specified in the answer

Output: a number

Precision

Floating point errors are OK.

More examples and test cases:

2*9 = 18
1+3-4*9
1       = 1
 +    9 = 10
  3  *  = 30
   -4   = 26
8-5*0/9+8/2+3*4
8               = 8
 -            4 = 4
  5          *  = 20
   *        3   = 60
    0      +    = 60
     /    2     = 30
      9  /      = 3.33333...
       +8       = 11.33333...
Knowing that 1+3-4*9 is 26

8-5*0/9+8/2+(1+3-4*9)*4
8                       = 8
 -                    4 = 4
  5                  *  = 20
   *        (1+3-4*9)   = 520
    0      +            = 520
     /    2             = 260
      9  /              = 28.8888...
       +8               = 36.8888...
8-2+4*6/2
8         = 8
 -      2 = 6
  2    /  = 3
   +  6   = 9
    4*    = 36
(1+2*7)*6+3+(2*2+3)

First group:
1+2*7
1
 +  7 = 8
  2*  = 16

Second group:
2*2+3
2
 *  3 = 6
  2+  = 8

(1+2*7)*6+3+(2*2+3)
(1+2*7)             = 16
       *    (2*2+3) = 128
        6  +        = 134
         +3         = 137
1+(6+(6+1*2)/2)/4
Nested group:
6+1*2
6     = 6
 +  2 = 8
  1*  = 8

Group:
6+(6+1*2)/2
6           = 6
 +        2 = 8
  (6+1*2)/  = 1

Full expression:
1+(6+(6+1*2)/2)/4
1                 = 1
 +              4 = 5
  (6+(6+1*2)/2)/  = 5

Scoring

This is , so the answer with the least amount of bytes wins.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ "Division by 0 should not return a valid number." What do you mean by "a valid number"? I'd suggest just saying answers can assume division by zero will never occur \$\endgroup\$
    – pxeger
    Dec 17, 2021 at 3:05
  • 1
    \$\begingroup\$ Thanks for your feedback @pxeger ! I'm removing errors handling \$\endgroup\$
    – Julian
    Dec 17, 2021 at 3:20
2
\$\begingroup\$

Subdivide the Bezier Curve

Background

A Bezier curve is a type of curve that has a lot of applications in all sorts of places, but most commonly, in computer graphics. It has a very simple algorithm and yet can represent a wide variety of shapes with just one common formula. If you've ever used pen tools in drawing software, you're probably already familiar with the general idea behind Bezier curves.

Given an ordered list of control points, we set some parameter \$t\$ in the range \$[0, 1]\$. Then, for each \$t\$, we draw a line between each consecutive pair of control points and select a point that is \$t\$ from the starting point. For example, if we have three control points and \$t\$ is \$\frac13\$:

enter image description here

The purple point is \$\frac13\$ of the way from the red point to the blue point, and the black point is \$\frac13\$ of the way from the blue point to the green point. You can change the ratio and move the points around here to try it out.

Now, we have one fewer point than we initially had control points. Let these be the new control points, and do this again with the same \$t\$:

enter image description here

(Desmos link). Now, we finally have a single point, so that is the point we obtain for this value of our parameter \$t\$. The Bezier curve is obtained from all final points for each \$0\leq t\leq 1\$. For more points, we just repeat this for more steps. Here's what a Bezier curve with four control points looks like:

enter image description here

(Desmos link)

Challenge

Given a list of control points for a Bezier curve and a positive integer \$n\$, subdivide the Bezier curve into \$n\$ segments and return the points. More precisely, return the output points for \$t=0,\frac1n,\frac2n,\cdots,\frac{n-1}n,1\$.

You may do I/O in any reasonable format; for example, a list of pairs or a pair of x and y coordinates for input, and a pair of numbers for output. Floating point errors are acceptable but your outputs should have an accuracy of at least \$10^{-3}\$ relative or absolute, whichever is larger.

There will be at least one point and \$n\$ will be a positive integer.

Example

Given input \$\{(0,0),(1,3),(4,2),(5,1)\}\$ and \$3\$ subdivisions:

For \$t=0\$, we just have \$(0,0)\$, and for \$t=1\$ we just have \$(5,1)\$.

For \$t=\frac13\$, we first go \$\frac13\$ of the way from each control point to the next to get \$\{(\frac13,1),(2,\frac83),(\frac{13}3,\frac53)\}\$. Repeating that once more gives us \$\{(\frac89,\frac{14}9),(\frac{25}9,\frac73)\}\$. Finally, if we do it once more, we get the single point \$(\frac{41}{27},\frac{49}{27})\$.

For \$t=\frac23\$, we first get \$\{(\frac23,2),(3,\frac73),(\frac{14}3,\frac43)\}\$, then \$\{(\frac{20}9,\frac{20}9),(\frac{37}9,\frac53)\}\$, and finally, \$(\frac{94}{27},\frac{50}{27})\$. And just for a sanity check, the points are indeed on the curve:

enter image description here

Note that these points do not evenly subdivide the Bezier curve by arclength. The arclength of a Bezier curve actually cannot be calculated exactly and subdividing like that would have to be done via approximations.

Test case generator

Credit to Wezl for the original idea.

\$\endgroup\$
2
  • \$\begingroup\$ love the interactive parts \$\endgroup\$
    – Wezl
    Dec 18, 2021 at 17:28
  • \$\begingroup\$ When reading this I didn't expect it to be you having posted it lol \$\endgroup\$
    – emanresu A
    Dec 23, 2021 at 7:55
2
\$\begingroup\$

Demonstrate some easier abstract algebra

From my related challenge, Demonstrate some advanced abstract algebra

Consider a binary operator \$*\$ that operates on a set \$S\$. For simplicity's sake, we'll assume that \$*\$ is closed, meaning that its inputs and outputs are always members of \$S\$.

Let's define some basic terms describing the properties of \$*\$. We can say that \$*\$ can have any of these properties, if they hold for all \$a,b,c \in S\$:

  • Commutative: \$a*b = b*a\$
  • Associative: \$(a*b)*c = a*(b*c)\$
  • Distributive: \$a*(b+c) = (a*b)+(a*c)\$, for some binary operator \$+\$ on \$S\$

We can also define 3 related properties, for a unary operation \$-\$ on \$S\$:

  • Anti-commutative: \$a*b = -(b*a)\$
  • Anti-associative: \$(a*b)*c = -(a*(b*c))\$
  • Anti-distributive: \$a*(b+c) = -((a*b)+(a*c))\$

Finally, we define 3 more, that only describe \$*\$ if the complete statement is true for \$a,b,c \in S\$:

  • Non-commutative: There exists \$a, b\$ such that \$a*b \ne b*a\$ and \$a*b \ne -(b*a)\$
  • Non-associative: There exists \$a, b, c\$ such that \$(a*b)*c \ne a*(b*c)\$ and \$(a*b)*c \neq -(a*(b*c))\$
  • Non-distributive: These exists \$a,b,c\$ such that \$a*(b+c) \ne (a*b)+(a*c)\$ and \$a*(b+c) \ne -((a*b)+(a*c))\$

We now have 9 distinct properties a binary operator can have: commutativity, non-commutativity, anti-commutativity, associativity, non-associativity, anti-associativity, distributivity, non-distributivity and anti-distributivity.

This does require two operators (\$-\$ and \$+\$) to be defined on \$S\$ as well. For this challenge we'll use standard integer negation and addition for these two, and will be using \$S = \mathbb Z\$.

Obviously, any given binary operator can only meet a maximum of 3 of these 9 properties, as it cannot be e.g. both non-associative and anti-associative.


Let's create a "table" of these properties:

Commutative Associative Distributive
Regular Commutative Associative Distributive
Anti Anti-commutative Anti-associative Anti-distributive
Non Non-Commutative Non-associative Non-distributive

Your task is to write 3 programs (either full programs or functions. You may "mix and match" if you wish).

Each of these 3 programs will:

  • take two integers, in any reasonable format and method

  • output one integer, in the same format as the input and in any reasonable method

  • be non-constant. That is, there exists at least two distinct inputs that have distinct outputs.

  • have exactly 3 of the 9 above properties. However, those three properties muse be in different rows and columns in the above table from each other. This means that it can be (for example) commutative, non-associative, anti-distributive; non-commutative, anti-associative, distributive; or anti-commutative, associative, non-distributive. But, it cannot be (for example) commutative, associative, distributive; non-commutative, non-associative, non-distributive; or non-commutative, anti-distributive, anti-associative.

This is ; the combined lengths of all 3 of your programs is your score, and you should aim to minimise this.

Additionally, you should include some form of proof that your programs do indeed have the required properties and do not satisfy the other properties. Answers without these are not considered valid.

Alternatively, a proof of impossibility is a valid answer. If you can demonstrate that there are no such programs that satisfy the criteria listed above, then this proof constitutes a valid answer as well.


Meta

\$\endgroup\$
5
  • \$\begingroup\$ There exists no anti-distributive surjection when \$S=\mathbb Z\$. Maybe there exists one when \$S=(\mathbb Z/2\mathbb Z)^k\$, but I haven't found one yet. \$\endgroup\$ Jun 16, 2021 at 9:12
  • \$\begingroup\$ I would remove the constraint that the operator be a surjection, and just impose that it be non-constant. If you convince yourself that such an anti-distributive operator exists, you could post the challenge, but I would change it to "write 3-9 programs, such that each property is verified by (at least) one program". That would be an incentive to have programs which verify several properties at once, but make it more manageable. \$\endgroup\$ Jun 16, 2021 at 9:18
  • \$\begingroup\$ Also, there are problems with your "anti-associativity": if b = 1, then (a*b)*c = a*(b*c). \$\endgroup\$
    – anatolyg
    Jun 16, 2021 at 10:43
  • \$\begingroup\$ @RobinRyder If \$ S=(\mathbb Z / 2\mathbb Z)^k\$, aren't anti-distributive operators the same as distributive operators? \$\endgroup\$
    – Nitrodon
    Jun 16, 2021 at 14:21
  • \$\begingroup\$ @Nitrodon Yes, of course you are right. \$\endgroup\$ Jun 16, 2021 at 15:03
2
\$\begingroup\$

Twins' complements

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

Code Golf Birthday Cake

Your task is to print this exact text:

     0 2 4 6 8 10
     | | | | | |
    &***********&
    | Code Golf |
   | e---------f |
  | d___________l |
 | o-------------o |
| C_______________G |
 ###Dennis$Dennis###
#####################

Rules

  • Trailing or leading newline is allowed
  • , so shortest code wins!

Meta

  • Any feedback?
\$\endgroup\$
9
  • \$\begingroup\$ why is it lopsided \$\endgroup\$ Dec 21, 2021 at 15:56
  • \$\begingroup\$ @thejonymyster fixed? \$\endgroup\$ Dec 21, 2021 at 15:57
  • \$\begingroup\$ No, that's more lopsided. You only need one $ between the Dennises, if that helps. \$\endgroup\$ Dec 21, 2021 at 16:00
  • \$\begingroup\$ @thejonymyster fixed? \$\endgroup\$ Dec 21, 2021 at 16:18
  • \$\begingroup\$ Well now the bottom is asymmetric, but also what do the numbers mean? \$\endgroup\$ Dec 21, 2021 at 17:16
  • \$\begingroup\$ @thejonymyster the site is about 9 years old \$\endgroup\$ Dec 21, 2021 at 18:27
  • 1
    \$\begingroup\$ Are you sure you want the bottom line have an extra # on left side but no such # on right side? \$\endgroup\$
    – tsh
    Dec 24, 2021 at 5:30
  • \$\begingroup\$ @tsh fixed now? \$\endgroup\$ Dec 24, 2021 at 11:53
  • \$\begingroup\$ can you add more candles? \$\endgroup\$
    – Fmbalbuena
    Dec 27, 2021 at 16:06
2
\$\begingroup\$

Domino tilings in an N-dimensional cube

Challenge

Imagine an N-dimensional cube which has dimensions 2×2×...×2. Given the value of N (a positive integer), calculate the number of ways it can be divided into 2×1×1×...×1 "hyper-domino" pieces (two unit N-dimensional hypercubes glued together).

Standard rules apply. The shortest code in bytes wins.

Examples and test cases

For N = 1, the "cube" is a single domino. A single domino can be divided into a single domino in exactly one way, so the answer is 1.

For N = 2, the "cube" is a 2×2 square. It can be divided, or tiled, in two ways:

--  ||
--  ||

For N = 3, the cube is a 2×2×2 cube. It can be divided into four domino-cubes in nine different ways. One way to count it is to see that, if you pick a unit cube, it can be used by three different domino-cubes (one in each direction), and in all cases the rest forms a small staircase-like shape

L1  L2
#   #
##  ##

which can be divided into three pieces in three ways (# denotes a piece in Z-direction)

#   #
--  --

#   #
##  ##

|   |
|#  |#

which gives 3×3 = 9.

The corresponding sequence is A005271.

N    Answer
-----------
1    1
2    2
3    9
4    272
5    589185
6    16332454526976
7    391689748492473664721077609089
\$\endgroup\$
2
\$\begingroup\$

Number of complete rhyme schemes

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

Is it a perfect word?

\$\endgroup\$
1
  • \$\begingroup\$ @mathcat "The word may always be assumed to be lowercase." \$\endgroup\$
    – Ginger
    Jan 14, 2022 at 19:31
2
\$\begingroup\$

Number of arrangements of half a Rubik's cube

From a corner-on view of a Rubik's cube calculate the number of arrangements of stickers that are out of view.

Your input will provide the state of a Rubik's cube when viewed like the below image:

enter image description here

This input will be an array, in any defined order†, grouping†, and nesting† that you choose, containing the colours‡ of the \$27\$stickers (A.K.A. facelets or tiles) on three sides of a 3x3 Rubik's cube that join at one corner, like you can see above.

The input may be assumed to be that of a solvable state where only face turns can return the cube to having six sides with a single colour on each (if it isn't then your code may do anything, short of summoning Cthulhu).

† The input may be a flat list of colour-labels or you may specify that these labels will already be grouped in any way you wish (it may be a ragged, nested list for example), but the content thereof should only consist of the sticker colour-labels.

‡ Since the centres of the cube are actually fixed relative to each other, and hence the hidden centres' colours are known, you may choose to leave any or all of the central stickers out of the expected input (it could be as short as \$24\$ sticker colour-labels) while using a labeling that identifes the colours as the top-centre, left-centre, right-centre, and their three opposite colours. For the record, the standard colour theme, as in the image above, has orange opposite red, white opposite yellow, and green opposite blue (hence orange is the hidden centre sticker on the bottom etc.).

You should output the number of possible arrangements of sticker colours of the \$27\$ stickers which are not in the input (i.e. those stickers which are out of view). Note that swapping two of those stickers of the same colour is considered to be the same arrangement.


Sandbox questions

  1. Does this need test cases? (I'm not even 100% sure what the output should be if the input looked like a solved cube from that perspective although I may be able to work it out without writing a program it's certainly more than one - e.g. U' L R2 D' M D2 M' D' L' R2 U or R2 U R2 F2 R2 U2 F2 R2 F2 U R2)

  2. Is the spec clear?

\$\endgroup\$
1
  • \$\begingroup\$ You should probably make it more explicit that the center colors of the opposite faces are known. (Also, I'm fairly sure that a "solved cube" input would have an output of 192, but that's just me doing quick math in my head, so I could be wrong.) \$\endgroup\$
    – Nitrodon
    Jan 14, 2022 at 15:18
2
\$\begingroup\$

Solve nonimplication-SAT

\$\endgroup\$
1
  • \$\begingroup\$ I don't think there is really one set of "standard decision-problem rules" (as there are for sequence); you could just say something like "output using any two distinct values representing true and false" \$\endgroup\$
    – pxeger
    Dec 31, 2021 at 23:26
2
\$\begingroup\$

Is this continuous terrain?

\$\endgroup\$
5
  • \$\begingroup\$ [Suggested Testcase](Try it online!) \$\endgroup\$
    – Fmbalbuena
    Jan 10, 2022 at 0:23
  • \$\begingroup\$ I am unsure if you should allow both ~ and -. Can one even freely mix them? \$\endgroup\$ Jan 10, 2022 at 12:33
  • \$\begingroup\$ @JonathanFrech as in you can choose to take input with overlines replaced with one of them \$\endgroup\$
    – emanresu A
    Jan 11, 2022 at 8:39
  • \$\begingroup\$ question name idea: "is this continuous terrain?" I have a feeling there is a dupe of this. \$\endgroup\$
    – Razetime
    Jan 14, 2022 at 4:05
  • \$\begingroup\$ @Razetime Good idea! \$\endgroup\$
    – emanresu A
    Jan 14, 2022 at 8:25
2
\$\begingroup\$

Sides of a polygon

\$\endgroup\$
5
  • \$\begingroup\$ Will the shape touch itself? Say, like this or this ? \$\endgroup\$
    – tsh
    Dec 27, 2021 at 5:40
  • \$\begingroup\$ @tsh No,it won't. \$\endgroup\$
    – emanresu A
    Dec 27, 2021 at 5:56
  • \$\begingroup\$ By your current examples, this is a valid shape although it looks very strange. \$\endgroup\$
    – tsh
    Dec 29, 2021 at 7:15
  • \$\begingroup\$ @tsh Yeah, I’ll just leave that since allowing those shapes doesn’t car assist any problems or ambiguousities. \$\endgroup\$
    – emanresu A
    Dec 29, 2021 at 8:18
  • \$\begingroup\$ I would like for the valid inputs to be more clearly defined. How many sides does @ths's "very strange" looking shape have? \$\endgroup\$ Jan 10, 2022 at 12:52
2
\$\begingroup\$

BCD to binary, with bitwise


In this challenge, you'll convert an 8-digit BCD (Binary Coded Decimal) number to a 32 bit (unsigned) integer in the fewest instructions possible, with only bitwise instructions available.

Task:

You'll be given a single positive integer as input, from 00000000 to 999999999. It will be represented using BCD, as a 4-byte unsigned integer, with each nibble being a decimal digit from 0000 (0) to 1010 (10). More significant nibbles will correspond to more significant digits of the decimal number.

Your output should be that same number, as an ordinary 32-bit integer.

Instructions:

This is atomic code golf, so you can only use the following instructions, the number of which is used for scoring:

and [r], [r|I]      Bitwise AND
or  [r], [r|I]      Bitwise OR
xor [r], [r|I]      Bitwise XOR

not [r]             Bitwise NOT

shr [r], [r|I]      Shift right (zero fill)
shl [r], [r|I]      Shift left

mov [r], [r|I]      Copy

All instructions will write their output to the first register listed, and for the second argument [r|I] indicates either a register or an immediate (any 32-bit constant) can be provided.

You have four registers to work with, all of which hold a single 4 byte unsigned integer: ra, rb, rc, and rd. Any instruction using only registers costs 1 byte, and any with an immediate cost a total of 4 (this isn't technically possible, since the immediates are 4 bytes on their own, but I don't want to make them too costly).

Input will be provided in ra, and the contents of ra when your program is finished will be used as output. All other registers will be initialized to 0.

Instructions Mk. 2:

This is atomic code golf, so you can only use the following instructions, the number of which is used for scoring:

and [r], [r|I]      Bitwise AND
or  [r], [r|I]      Bitwise OR
xor [r], [r|I]      Bitwise XOR

not [r]             Bitwise NOT

shr [r], [r|I]      Shift right (zero fill)
shl [r], [r|I]      Shift left

mov [r], [r|I]      Copy

goto [r|I]          Go to an instruction (`0` is the start of the program)
goif [r] [r|I]      Go to an instruction, if `r` is not all `0`s

All instructions (aside from goto and goif) will write their output to the first register listed, and for the second argument [r|I] indicates either a register or an immediate (any 32-bit constant) can be provided.

You have 8 registers to work with, all of which hold a single 4 byte unsigned integer: ra, rb, rc, rd, rk, rn, rp, and rs. Any instruction using only registers costs 1 score, and any with an immediate cost a total of 2.

Input will be provided in ra, and the contents of ra when your program is finished will be used as output. All other registers will be initialized to 0.

Other:

I don't actually know if this is an interesting challenge, or if more registers will be needed, or if there's already a well known solution. I'd try it myself but it's kinda late here so I'm too tired to, and if I don't post this now I'll forget about it lol

\$\endgroup\$
1
  • \$\begingroup\$ Maybe just give infinite amount of registers and don't call them "byte" but "score"? \$\endgroup\$
    – l4m2
    Jan 18, 2022 at 12:29
2
\$\begingroup\$

Compress and decompress

\$\endgroup\$
4
  • \$\begingroup\$ self-referential might be better than quine. But are you assuming normal quine rules? Are programs allowed to introspect their own source code? \$\endgroup\$
    – pxeger
    Jan 17, 2022 at 10:15
  • \$\begingroup\$ This challenge is fairly similar to Encode a Lenguage, but I think it's sufficiently open-ended that it's different in an interesting way. \$\endgroup\$
    – pxeger
    Jan 17, 2022 at 10:18
  • \$\begingroup\$ Personally I think this would be more interesting if you were allowed to read your source code, because otherwise it becomes too much of a quine variant where most of the code is taken up by encoding the program's source code, and not the interesting task (which is the compression). (Sorry, I probably should have given you this opinion before I asked you to decide whether quine rules applied) \$\endgroup\$
    – pxeger
    Jan 17, 2022 at 10:26
  • 1
    \$\begingroup\$ @pxeger I added the quine rules specifically to discourage solutions where you just swap your programs source code and a single input. The other (more interesting imo.) approach is to actually do compression and then make your source code compressible. \$\endgroup\$
    – AnttiP
    Jan 17, 2022 at 10:32
2
\$\begingroup\$

Prime Number Fibonacci

In this challenge, you will make a program that calculates the Fibonacci sequence with a twist. Instead of it starting with 0 and 1, it starts with the nth prime number determined by input by the user. The second number is the nth+1 prime number. The sequence should also stop after nth number iterations.

Walkthrough:

  1. Get a number from the input. We will call it n
  2. Calculate the n prime number and n+1 prime number
  3. Make a function that adds these numbers and calls itself with the result.
  4. Make the function stop once prime number with index n numbers are output

Examples:

input:2
output:
8
13
21
34
55

input:10
output:
60
91
151
242
393
635
1028
1663
2691
4354
7045
11399
18444
29843
48287
78130
126417
204547
330964
535511
866475
1401986
2268461
3670447
5938908
9609355
15548263
25157618
40705881
65863499
106569380

input:5
output:
24
37
61
98
159
257
416
673
1089
1762
2851
4613
7464

By the way, here is the JavaScript code I used for this example:

var primeNumber1 = prime(num);
var primeNumber2 = prime(num+1);
fib(primeNumber1,primeNumber2,0,primeNumber1);
}
function fib(num1,num2,iterations,max){
console.log(num1+num2);
if(iterations == max+1){
return;
}
fib(num2,num1+num2,iterations+1,max);
}
function prime(number){
var numPrime = 0;
for(var i = 0; i > -1; i++){
if(isPrime(i)){
numPrime++;
if(numPrime == number){
return i;
}
}
}
}
function isPrime(num) {
  for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}
\$\endgroup\$
4
  • \$\begingroup\$ I would define the task more clearly. Something along the lines of (if I understood correctly) "Let \$(p_k)_{k\geq 1}\$ denote the ordered sequence of all prime numbers. Given a natural number \$n\geq 1\$, output \$(a_1,\dots,a_{p_n+p_{n+1}})\$ where \$a_{-1}:=p_n\$, \$a_0:=p_{n+1}\$ and \$a_k:=a_{k-2}+a_{k-1}\$ for \$k\geq 1\$." \$\endgroup\$ Jan 19, 2022 at 9:28
  • \$\begingroup\$ @JonathanFrech I have no idea what those symbols mean except for greater than and I know := is used in statically typed programming language to infer the type of a variable. Could you explain what the math string means and how it would clarify my question? \$\endgroup\$ Jan 19, 2022 at 14:12
  • \$\begingroup\$ When you say "the nth prime number", is for you 2 the prime number with index \$0\$ or \$1\$? I guess the latter, so \$p_1=2\$. Then I understand your task to be printing \$p_n\$ integers which are defined as follows: the first number to be printed is \$a_1=p_n+p_{n+1}\$, the second is \$a_2=p_{n+1}+a_1\$, the third \$a_3=a_1+a_2\$ and so on up to \$a_{p_n+p_{n+1}}\$. I found it hard to read into your explanation and would like a more clear definition of the task -- be it with formulae or word descriptions. \$\endgroup\$ Jan 20, 2022 at 19:21
  • \$\begingroup\$ I guess my problem is that I have to infer from your example that the 2nd prime number is 3 and "Make a function that adds these numbers and calls itself with the result." requires thinking of Fibonacci to properly interpret. \$\endgroup\$ Jan 20, 2022 at 19:23
2
\$\begingroup\$

Mat Printing Matrix

\$\endgroup\$
5
  • \$\begingroup\$ er wats default I/O @adam \$\endgroup\$
    – DialFrost
    Jan 17, 2022 at 11:56
  • \$\begingroup\$ im sorry i dont understand @adam could u explain the defualt IO (i alr read the link doesnt rly help) or edit my post thx \$\endgroup\$
    – DialFrost
    Jan 17, 2022 at 12:02
  • \$\begingroup\$ like this? i changed it \$\endgroup\$
    – DialFrost
    Jan 17, 2022 at 12:08
  • \$\begingroup\$ Yeah, this looks great. Maybe put in the tags you plan on using. \$\endgroup\$
    – Adám
    Jan 17, 2022 at 12:55
  • \$\begingroup\$ @adam pls edit the tags if its wrong thx \$\endgroup\$
    – DialFrost
    Jan 17, 2022 at 13:24
2
\$\begingroup\$

Implement an argwhere function

Posted

\$\endgroup\$
2
  • \$\begingroup\$ Interesting. I'm guessing "no", but are langs without function definition allowed to participate? \$\endgroup\$ Jan 14, 2022 at 19:53
  • \$\begingroup\$ @thejonymyster I'm not too interested in making restrictions. If your language can accept code as input and run it to make decisions, I'd say that's good enough. But as with all functional-programming questions, some languages will inevitably be excluded. \$\endgroup\$
    – chunes
    Jan 15, 2022 at 5:47
2
\$\begingroup\$

Is this word in standard order?

\$\endgroup\$
6
  • \$\begingroup\$ IMO this would be better as an array challenge with arrays of [1,2,3] etc. \$\endgroup\$
    – emanresu A
    Dec 31, 2021 at 22:07
  • \$\begingroup\$ @emanresuA I considered that, but I thought using letters might create some interesting solutions using regular expressions and what-not. Do you think I should allow working over any set (e.g. the natural numbers), not just the alphabet? Or would that be too complex? \$\endgroup\$
    – pxeger
    Dec 31, 2021 at 22:14
  • \$\begingroup\$ And "some \$x\$"? \$\endgroup\$ Jan 10, 2022 at 12:35
  • \$\begingroup\$ @JonathanFrech What do you mean? \$\endgroup\$
    – pxeger
    Jan 18, 2022 at 8:28
  • \$\begingroup\$ @pxeger I edited in what I meant; feel free to revert. \$\endgroup\$ Jan 19, 2022 at 9:16
  • 1
    \$\begingroup\$ I thought on first looks that this is the same as Stackable sequences, but this allows things like aabcc, which I think would be a good test case. Perhaps another useful characterization is that if we take the first appearance of each letter, the resulting sequence counts up from a without gaps. \$\endgroup\$
    – xnor
    Jan 19, 2022 at 11:57
2
\$\begingroup\$

Move to Right and left

\$\endgroup\$
2
  • \$\begingroup\$ why are there X crossings? wouldn't they just combine right there? \$\endgroup\$ Jan 20, 2022 at 15:42
  • \$\begingroup\$ @thejonymyster this is cross. \$\endgroup\$
    – Fmbalbuena
    Jan 20, 2022 at 17:35
2
\$\begingroup\$

Crack the Caesar cipher

\$\endgroup\$
2
  • \$\begingroup\$ Can we not have to deal with capitalisation? \$\endgroup\$
    – emanresu A
    Jan 18, 2022 at 21:08
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Jan 21, 2022 at 21:59
2
\$\begingroup\$

Regex ordinals

Inspired by this xkcd comic, your job is to write an extremely meta regex.

Specifically, the depth of a regex is an ordinal defined as follows:

  1. regex golf has depth 0.
  2. meta-x has depth 1 greater than the depth of x.
  3. The depth of <regex> is the supremum of the depths of everything <regex> matches.

Of course, it's possible for a string not to have a depth. For example, /.*/ matches itself, so its depth would have to be greater than its depth, which is impossible.

Your challenge is to write a regex with depth \$\omega^2\$.

And this is code golf, so the shortest regex wins.

Examples of regex ordinals

  • meta-regex golf is depth 1.
  • meta-meta-regex golf is depth 2.
  • /(meta-)*regex golf/ is depth \$\omega\$.
  • /(meta-)*\/(meta-)\*regex golf\// is depth \$\omega 2\$.
\$\endgroup\$
1
2
\$\begingroup\$

Von Neumann Probe Battle ()


This is just an idea for now, placing it here as a draft and to collect feedback.

Basically, your goal would be to design a set of machines, including factories and spacecraft, which start on earth and spread outward into the universe. You'd be able to design these machines. Not just their code, but the parts that make them up.

For example, you could start on earth with a single factory, which would make a swarm of mining bots. These would bring ore to the surface, and the factory would switch to making spacecraft. Once the spacecraft are built, the factory could assemble all of the parts needed to make an identical factory, load them onto the spacecraft, and send them to the moon. Then, both factories would start the process over.

The ultimate goal would be to build "stamps", which cost a small amount of iron, and then vanish from existence. These are used for scoring.

This challenge might not be very practical, due to the issues involved in simulating a detailed and exponentially increasing swarm of robots in a vast universe.

\$\endgroup\$
2
  • \$\begingroup\$ stamps? you mean paperclips \$\endgroup\$
    – Ginger
    Jan 22, 2022 at 22:05
  • \$\begingroup\$ @GingerIndustries Maybe :p \$\endgroup\$ Jan 22, 2022 at 22:06
2
\$\begingroup\$

Pretty print my arrays

I like to pretty print multidimensional arrays, like this:

[ [ [1, 2, 3],
    [4, 5, 6] ],
  [ [7, 8, 9],
    [6, 4, 2] ] ]

But it's a pain to do by hand and it'd be nice to have a program that does this for me. Your challenge is to create a program that does this for me, taking a multidimensional array containing only numbers and prettyprinting it.

Specifically, an array of depth 1 is printed joined by , with [ prepended and ] appended:

[1, 2, 3]

An array of depth \$n+1\$, which contains at least one array of depth \$n\$, has its subarrays prettyprinted, joined by newlines and indented by two spaces. All but the last subarray have a comma appended, the last has ] appended, and the first has its first line indented with [ instead of two spaces:

enter image description here

Here's a reference implementation:

function recursivePrettyPrint(array){
  if(array.every(x => typeof x == "number")){
    return `[${array.join(', ')}]`;
  } else {
    return array.map((item, index) => {
      let result = recursivePrettyPrint(item) + ',';
      result = result.split`\n`;
      if(index == 0){
        result[0] = '[ ' + result[0];
      } else {
        result[0] = '  ' + result[0];
      }
      for(let i = 1; i < result.length; i++){
        result[i] = '  ' + result[i]
      }
      return result.join('\n');
    }).join('\n').slice(0,-1) + ' ]';
  }
}

function change(){
  let array = JSON.parse(document.getElementById('input').value);
  let output = document.getElementById('output');
  output.innerText = recursivePrettyPrint(array);
}
<textarea id=input></textarea>

<button id=run onclick=change()>Pretty Print</button>

<pre id=output></pre>

Numbers may be multiple digits. The input will always be orthogonal/rectangular, and you may take its dimensions as well.

Testcases

[[892, 759], [962, 251]] ->
[ [892, 759],
  [962, 251] ]

[118, 922, 619] ->
[118, 922, 619]

[[966, 639, 616, 255], [622, 483, 87, 241], [453, 870, 728, 725], [163, 936, 48, 967], [261, 833, 87, 200]] -> 
[ [966, 639, 616, 255],
  [622, 483, 87, 241],
  [453, 870, 728, 725],
  [163, 936, 48, 967],
  [261, 833, 87, 200] ]

[[[[[912, 547], [366, 754]], [[723, 536], [779, 238]]], [[[559, 392], [602, 709]], [[692, 915], [412, 302]]]], [[[[3, 504], [936, 83]], [[352, 442], [425, 375]]], [[[380, 440], [793, 762]], [[850, 321], [780, 457]]]]] ->
[ [ [ [ [912, 547],
        [366, 754] ],
      [ [723, 536],
        [779, 238] ] ],
    [ [ [559, 392],
        [602, 709] ],
      [ [692, 915],
        [412, 302] ] ] ],
  [ [ [ [3, 504],
        [936, 83] ],
      [ [352, 442],
        [425, 375] ] ],
    [ [ [380, 440],
        [793, 762] ],
      [ [850, 321],
        [780, 457] ] ] ] ]

[[[128, 910, 664, 658], [172, 238, 564, 492], [325, 384, 566, 90]], [[876, 819, 764, 105], [583, 528, 731, 839], [480, 126, 692, 875]], [[215, 84, 268, 504], [400, 674, 997, 526], [799, 692, 193, 296]], [[943, 185, 567, 188], [118, 200, 879, 409], [116, 493, 62, 343]]] -> 
[ [ [128, 910, 664, 658],
    [172, 238, 564, 492],
    [325, 384, 566, 90] ],
  [ [876, 819, 764, 105],
    [583, 528, 731, 839],
    [480, 126, 692, 875] ],
  [ [215, 84, 268, 504],
    [400, 674, 997, 526],
    [799, 692, 193, 296] ],
  [ [943, 185, 567, 188],
    [118, 200, 879, 409],
    [116, 493, 62, 343] ] ]
```
\$\endgroup\$
3
  • \$\begingroup\$ "Numbers may be multiple digits" but you should state that numbers will be the only atomic data to occur. \$\endgroup\$
    – Adám
    Jan 24, 2022 at 23:40
  • 2
    \$\begingroup\$ Fine challenge, but I hate this way of printing arrays :P \$\endgroup\$
    – Wheat Wizard Mod
    Jan 24, 2022 at 23:46
  • \$\begingroup\$ May I input the array as a string? If so, what formatting may I assume for the input array? For example, will there always be a space after each comma? \$\endgroup\$
    – tsh
    Jan 27, 2022 at 8:16
1
40 41
42
43 44
155

You must log in to answer this question.

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