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\$
2
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4703 Answers 4703

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

My math license got revoked

Your task is to replicate the method described in https://xkcd.com/410/.

Not going to develop the question more until I have enough time to get some test cases together and make sure that there are complex friendly numbers.

I'm sandboxing this for the future, but here's a (work-in-progress) python reference implementation:

def is_divisible(a, b):
return a // b == a / b

def sum_divisors(a):
    divisors = []

    for real_part in range(1, a.real):
        for complex_part in range(1, a.imag):

            number_to_test_if_divisor = complex(real_part, complex_part)
            if is_divisible(a, number_to_test_if_divisor):
                divisors.append(number_to_test_if_divisor)

    return sum(divisors)

def is_friendly(a, b):
    return sum_divisors(a) / a == sum_divisors(b) / b


a = complex(input("a: "))
b = complex(input("b: "))

print(is_friendly(a, b))
\$\endgroup\$
2
\$\begingroup\$

Solve quadratic equations when 1+1=0

This is the code-golf version of this challenge, I also created a fastest-code version that focuses on solving one (important) special case

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

Compute the logarithm of a matrix

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

Base-10 to bijective base-10

Convert base-10 positive integer (base-10 number using digits 0123456789) to bijective base-10 (base-10 number using digits 123456789A, where A means 10).

Shortest code wins.

You can also choose another symbol in place of the A.

\$\endgroup\$
1
  • \$\begingroup\$ It may be a duplicate of this challange \$\endgroup\$
    – bsoelch
    Commented Aug 1, 2023 at 11:21
2
\$\begingroup\$

Cutting a Circular Pizza Vertically

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

First odd then even indices

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

Walk by walls in a room

\$\endgroup\$
2
  • \$\begingroup\$ It is unclear where one test case ends and the next begins \$\endgroup\$
    – mousetail
    Commented Aug 15, 2023 at 13:54
  • \$\begingroup\$ @mousetail Just clarified it \$\endgroup\$
    – Joao-3
    Commented Aug 15, 2023 at 14:23
2
\$\begingroup\$

Zeckendorf to F(4k+2) representation

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

Normalize a Gaussian GCD

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

Minimal number of jumps to reach a square

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

Prefix code generator

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

Pseudo-Quantum Bogosort

Quantum Bogosort is as follows:

  1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.

  2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)

  3. All remaining universes contain lists which are sorted.

Source

Given that we cannot destroy the universe, the next best thing is to destroy a thread!

The challenge is as follows: Make a new thread for each possible permutation of a list and if the list is not sorted, destroy the thread.

Rules

Input is a list of length 4 or less

Output is a sorted list and I guess the number of the thread that is sorted? This part is iffy...

This is standard code-golf

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

Inverse trigonometric functions


Example equations using complex logarithm:

\$ \sin^{-1}(z)=-i \cdot \ln(\sqrt{1-z^2}+iz) \$

\$ \cos^{-1}(z)=-i \cdot \ln(\sqrt{z^2-1}+z) \$

\$ \tan^{-1}(z)=\frac{i}{2} \cdot \ln(\frac{1-iz}{1+iz}) \$

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

Volume of a squaricililinder

Inspired by an interestingly-shaped glass at a cafe.

WHAT THE HECK IS A SQUARICILILINDER!?!?!

A squaricililinder is a prism with a square at one end and a circle at the other. The circle is as small as possible while being able to fit the square at the other end inside.

The width of the glass increases at a constant rate as you go up it.

Now what's the challenge?

Given the height of a squaricililinder and the diameter of the circle on it, calculate the area of the squaricililinder.

How am I supposed to calculate it?

It's simple, all you need to do is plug in the height \$h\$ and the diameter \$d\$ to this simple formula: $$\small\underbrace{4\times\left( \int_0^h \int_0^{\frac d{\sqrt 2} }\frac yh\times\sqrt{ 1-\frac{x^2\times\left(6-4\sqrt2\right)}d } dx dy\right) + \left(\frac{d^2}2 \times h \right)}_\textrm{I hope I got the formula right...}$$ It was obtained by calculating the area of the cuboid inside and then doing some two-dimensional integrals on the circular parts.

Can you give me an example implementation?

Sure, here's an ungolfed and slow example in Python + sympy:

from sympy import *

x, y, d, h = symbols("x, y, d, h")

def calculate_area_of_shape(diameter: float, height: float) -> float:
    
    formula_in_integral = (y / h) * sqrt(1 - (((x ** 2) * (6 - 4 * sqrt(2))) / d))
    
    integral_part = integrate(integrate(formula_in_integral, (x, 0, d / sqrt(2))), (y, 0, h))
    
    actual_formula = 4 * integral_part + ((d ** 2) / 2) * h
    
    return actual_formula.subs(d, diameter).subs(h, height)

Anything else?

This is , so shortest code wins!

\$\endgroup\$
5
  • 3
    \$\begingroup\$ Can you be more specific how a squaricililinder is constructed? I assume it's made by connecting points on the circle to those on the square. But how do we match the points? By fraction of the perimeter? By angle of the center? \$\endgroup\$
    – xnor
    Commented Sep 4, 2023 at 0:03
  • \$\begingroup\$ You should add test-cases to make it easier to verify different approaches (your examples times out on ato) \$\endgroup\$
    – bsoelch
    Commented Sep 4, 2023 at 11:37
  • \$\begingroup\$ You should make it more clear if you are talking about the volume or the (surface) area \$\endgroup\$
    – bsoelch
    Commented Sep 4, 2023 at 11:41
  • \$\begingroup\$ For h=d=1 your equation gives a volume of 1.8727, which is more than the volume of a cylinder with height h and diameter d (pi*(d/2)²*h= 0.785). But the way I understood your description the shape should be contained in that cylinder \$\endgroup\$
    – bsoelch
    Commented Sep 4, 2023 at 12:00
  • \$\begingroup\$ I don't understand what the width of the glass is, which you say goes up at a constant rate. And I still have my question about how the squaricylinder is constructed. \$\endgroup\$
    – xnor
    Commented Sep 7, 2023 at 8:30
2
\$\begingroup\$

Median of Chi-Square

Output the IEEE-754 single-precision floating-point number represented by the following binary decomposition:

Sign, Exponent, Mantissa
0, 01111101, 11010001110110101101101

This is the most accurate approximation of the median of the chi-squared distribution \$\chi^2(1)\$, which is approximately \$0.454936423119572751942516646979649\$ in decimal. There is no known closed form of this value.

\$\endgroup\$
12
  • \$\begingroup\$ Worth noting this value is 1055452525 in decimal and 3EE8ED6D in Hex. \$\endgroup\$
    – ATaco
    Commented Sep 4, 2023 at 1:08
  • \$\begingroup\$ Does this approach fall under "Hard-coding the output"? \$\endgroup\$
    – bsoelch
    Commented Sep 4, 2023 at 9:19
  • \$\begingroup\$ @bsoelch No. That's clever, actually. \$\endgroup\$ Commented Sep 4, 2023 at 9:40
  • \$\begingroup\$ This is \$\frac{15265133}{2^{25}}\$, right? \$\endgroup\$ Commented Sep 10, 2023 at 5:33
  • \$\begingroup\$ @CommandMaster Yeah. \$\endgroup\$ Commented Sep 10, 2023 at 5:47
  • \$\begingroup\$ Do you have to output exactly this number? Or can you output anything which rounds off to this, when treated as a single floating-point number? The exact number in decimal is 0.4549364149570465087890625 \$\endgroup\$ Commented Sep 10, 2023 at 5:55
  • \$\begingroup\$ @CommandMaster The task is to output the floating-point number approximation, not the number itself. \$\endgroup\$ Commented Sep 10, 2023 at 5:57
  • \$\begingroup\$ @DannyuNDos The exact floating-point number in decimal is 0.4549364149570465087890625. \$\endgroup\$ Commented Sep 10, 2023 at 6:00
  • \$\begingroup\$ @CommandMaster Since the task is to output the floating-point number, that wouldn't make a difference. \$\endgroup\$ Commented Sep 10, 2023 at 6:02
  • \$\begingroup\$ I think I am confused. Is the following statement correct? "A solution is valid iff it takes no input, and outputs (according to the standard I/O rules) a number, that if rounded to a single-precision floating-point number will round to \$\frac{15265133}{2^25}\$". In particular, would a Mathematica answer which symbolically outputs the exact number be valid? \$\endgroup\$ Commented Sep 10, 2023 at 6:06
  • \$\begingroup\$ @CommandMaster Dunno whether Mathematica has floating-point numbers, so I cannot really answer that. \$\endgroup\$ Commented Sep 10, 2023 at 6:10
  • \$\begingroup\$ Is lambda:0.4549364149 a valid Python answer? It outputs a double-precision float which isn't equal to the approximation, but if rounded to single-precision it's equal \$\endgroup\$ Commented Sep 10, 2023 at 6:12
2
\$\begingroup\$

Sums of sum of divisors in sublinear time

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

Unique String Deletions

You are given a string s, where s.length <= 42, and an integer k, where k <= s.length. All regular test cases have totals < 2147483648, but bonuses exceed this value. If limited by int32, return modulo of value.

Return the count of all unique strings obtained by deleting k characters. Fastest algorithm wins. In case of a tie by algorithmic complexity, whoever has the most bonus cases wins.

Test cases: These are the sums of all f(s, k) from k=0 to k=s.length

"" = 1
"a" = 2
"aaaaa" = 6
"meow" = 16
"acacc" = 17
"cbcab" = 26
"abcacc" = 37
"cbabca" = 50
"alifra" = 63
"caadbac" = 87
"abbbacbb" = 78
"abbbbbabab" = 97
"doggaggy" = 112
"abbabacca" = 162
"abbbacbbaa" = 218
"isosceles" = 384
"armageddon" = 720
"123456789abcdef" = 32768
"supercalifragilistic" = 812760

Bonus cases: (Used as tiebreaker)

"arithmosesquippedaliophobia" = 80375252
"antidisestablishmentarianism" = 174600720
"pseudopseudohypoparathyroidism" = 644909314
"supercalifragilisticexpialidocious" = 11073277084
"hippopotomonstrosesquippedaliophobia" = 14891636776
\$\endgroup\$
7
  • \$\begingroup\$ There's a similar question for binary strings with restricted-time. Do you think there's room for improving the algorithmic complexity from what the answers there do? \$\endgroup\$
    – xnor
    Commented Sep 12, 2023 at 2:11
  • \$\begingroup\$ Shouldn't the empty string output 1? \$\endgroup\$
    – xnor
    Commented Sep 12, 2023 at 2:12
  • \$\begingroup\$ I've characterized my solution, and it runs in 3.55e-8*n^(2.19) \$\endgroup\$ Commented Sep 12, 2023 at 2:36
  • \$\begingroup\$ Using the same approach as the answers in the question @xnor linked you can create a linear-time algorithm \$\endgroup\$ Commented Sep 12, 2023 at 2:43
  • \$\begingroup\$ I'd expect someone will find a linear time solution, and then a lot of answers will copy it, and you will just get a bunch of ties. Perhaps you can have the number of allowed deletions be different than s.length? \$\endgroup\$ Commented Sep 12, 2023 at 2:47
  • \$\begingroup\$ From what i found on SO: [It's a classic DP] stackoverflow.com/questions/5151483/… \$\endgroup\$ Commented Sep 12, 2023 at 2:52
  • \$\begingroup\$ @CommandMaster changed the question to use number of deletions as a parameter. \$\endgroup\$ Commented Sep 12, 2023 at 3:15
2
\$\begingroup\$

Draw numbers as dice patterns

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

How sorted is this array

Given an array output the minimum number of swaps needed to sort that array

Examples

[1, 2, 3, 4, 5]   ->  0
[1, 3, 2, 4, 5]   ->  1
[5, 4, 3, 2, 1]   ->  2
[1, 3, 4, 5, 2]   ->  3
[2, 3, 4, 5, 1]   ->  4

[3, 5, 1, 11, 7, 3] -> 3

Rules

  • You can assume that the elements of the array are positive integers
  • There might be duplicate elements
  • This is , the shortest code wins

Optional additional requirement

Solve the problem in \$O(n²)\$


Meta

  • Would you consider this challange to be a duplicate? My solution only asks for the number of swaps, which seems to be a much easier task than finding the actual pairs of indices
    These twp challenges I found are very similar but not exactly the same: sorting networks, swaps in bubble sort
\$\endgroup\$
1
  • \$\begingroup\$ Is the input a permutation? If it is the answer is the length of the input minus the number of cycles in the permutation, which seems like it would be a simple modification to an existing question \$\endgroup\$ Commented Sep 11, 2023 at 12:50
2
\$\begingroup\$

Add two rational numbers... esoterically

Objective

Build a binary operator \$\star : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\$ such that, there exists a bijection \$i : \mathbb{Z} \to \mathbb{Q}\$ such that, for every integer \$M\$ and \$N\$, \$M \star N = i^{-1}(i(M) + i(N))\$ holds.

Or in mathematical terms, build a binary operator \$\star\$ that admits a group isomorphism from \$(\mathbb{Z}, \star)\$ to \$(\mathbb{Q}, +)\$.

I/O Format

Flexible. Standard loopholes apply.

Scoring

This is a challenge. The submission whose the asymptotic worst-case time complexity of \$\star\$ is the fastest wins.

The parameter \$n\$ for the time complexity is \$s(M) + s(N)\$, where \$s\$ is defined as follows:

  • \$s(0) = s(-1) = 0\$.
  • For every integer \$D > 0\$, \$s(D) = \lfloor \log_2 D \rfloor + 1\$.
  • For every integer \$D < -1\$, \$s(D) = \lfloor \log_2 (-D-1) \rfloor + 1\$.

The shortness of your code is a tiebreaker. That is, this challenge is secondarily .

Notes and Rules

Note that each bijection \$i\$ induces \$\star\$ uniquely. As such, your submission must specify your choice of \$i\$.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ How would you score built-ins (e.g. for arithmetic operations on integers, int to string, ...)? O(1), the complexity of the languages implementation or the complexity of the best known algorithm? \$\endgroup\$
    – bsoelch
    Commented Sep 20, 2023 at 9:56
  • 1
    \$\begingroup\$ Additionally, I'd suggest having something else other than code-length as the tie breaker, according to Using shortest code as a tie-breaking winning criterion in code-challenge questions \$\endgroup\$ Commented Sep 21, 2023 at 10:52
  • \$\begingroup\$ I thought of an interesting solution, so I removed my comments regarding interesting solutions \$\endgroup\$ Commented Sep 22, 2023 at 11:54
  • \$\begingroup\$ Is O(1) possible on word-RAM model? \$\endgroup\$
    – l4m2
    Commented Oct 8, 2023 at 9:08
  • \$\begingroup\$ @l4m2 it depends on what operators you allow, but O(n) is definitely possible \$\endgroup\$ Commented Oct 8, 2023 at 10:37
2
\$\begingroup\$

Build the smallest self driving Car

Your goal is building the smallest self driving car to get from A to B.

The car is a point mass of 1kg and has a steering wheel to turn left and right, as well as an accelerator pedal to accelerate and brake. Furthermore it is equipped with LIDAR: If 0° is the forward direction, it has a laser every 10° from -90° to +90°. Each of these lasers measures the distance to the next wall. The point A is where the car starts witz zero velocity, pointing north. The destination B is an area where the car has to stop to finish the trip (it can be facing any direction).

Your job is to write a function that is called every second, to steer your car to the B area, without crashing into the wall.

def car(lidar, speed):
    # lidar is an array of 19 floating point numbers
    # speed is an integer
    steering = ... # can be any integer from -3 to 3 and refers to a multiple of 10° (eg -2 means -20°) the car is turned in this step.
    acceleration = ... # can be any of [-1, 0, 1] and refers to the acceleration in `m/s` for the next step
    # first the car is turned by the indicated amount, then the acceleration is added to the current velocity, and then we take a velocity-sized step in the current direction

    return steering, acceleration

The function must be deterministic and a black box function, that is, it can only communicate to the outside world via the inputs arguments and the returned values. The function must be as small as possible (measured in bytes).

If the car crashes into a wall, it will be disqualified.

the car with lidar

Map

the map will need to be determined it will be a closed non-self intersecting polygon. Here is an example but it will be a longer and maybe a little bit more complicated:

enter image description here


Discussion

  • EDIT: I just remembered there was Lab Rat Race: an exercise in genetic algorithms where we did something similar. So maybe it would make sense to take the challenge in a slightly different direction.

  • EDIT2: There is an almost identical challenge in http://janismac.github.io/ControlChallenges/ (go to the menu with the little squares and choose "Vehicle Steering" or "Vehicle Racing"). After playing around with this I think a combination of golfing code and time would be nice.


I'd obviously have to write a controller and come up with a good map that is doable with the velocity/direction constraints. Ideally with some graphical output for the participants to debug their car.

  1. Shall there be multiple maps?
  2. Are the discrete actions a good idea? (And are the ranges any good?) I think for the velocity it is nice so the car can come to a full stop in the target area.
  3. Should the steering be limited when the velocity is higher?
  4. Currently it feels like this will end up as just as a compression challenge i.e. who can hardcode a good sequence of steering inputs. I'm not sure this is all that fun. Are there other challenge modes or variations for this setting that would be more interesting? (The other thing I had in mind was giving the players a fixed code-budget and measuring how far they can get in the map.)
  5. Should the cars be allowed to have some memory between each step? (e.g. limited to a certain number of bits) - after the update from above I think it would make sense to allow some (or maybe even an unlimited) amount of memory between each step. But still it would be nice to have some sort of restriction.
\$\endgroup\$
2
  • \$\begingroup\$ I agree with point 4, I think this is already hard enough and golfing wouldn't make it more interesting. Perhaps a test-battery code-challenge, with the score based on how far the car gets on average? Maybe with hidden tests to prevent overfitting \$\endgroup\$ Commented Sep 13, 2023 at 4:18
  • 1
    \$\begingroup\$ Thanks for the input, yes that would definitely fit. I think I'd like people to overfit in the sense that they do a fixed route. But if we'd make a score based on distance we'd have to impose some other limit or challenge, I think? \$\endgroup\$
    – flawr
    Commented Sep 13, 2023 at 18:44
2
\$\begingroup\$

Transpose a multidimensional array

\$\endgroup\$
2
  • \$\begingroup\$ These kinds of operations are common in libraries/languages for scientific computing, like MATLAB/Octave or in python numpy/pytorch. In these languages you usually find a function like pytorch.org/docs/stable/generated/torch.permute.html or numpy.org/doc/stable/reference/generated/numpy.einsum.html that make it easier to comprehend what dimensions are moved to which other dimensions. Could you maybe phrase your challenge also in terms of these functions? I think it is easier to understand if you explain how the dimensions need to be moved (instead of showing this example). \$\endgroup\$
    – flawr
    Commented Oct 2, 2023 at 9:42
  • \$\begingroup\$ This is also a builtin in BQN. \$\endgroup\$
    – DLosc
    Commented Oct 2, 2023 at 15:42
2
\$\begingroup\$

Golf a LaTeΧ math expression

\$\endgroup\$
3
  • \$\begingroup\$ So, just, remove whitespace before non-alphanumeric? am I missing something here? \$\endgroup\$ Commented Oct 5, 2023 at 10:58
  • \$\begingroup\$ @noodleman It's more complicated, sometimes you can remove {}, and sometimes you can remove a space before an alphanumeric (in a b you can, but not in \a b) \$\endgroup\$ Commented Oct 5, 2023 at 11:19
  • \$\begingroup\$ Definitely add test cases reflecting those behaviours \$\endgroup\$ Commented Oct 5, 2023 at 11:21
2
\$\begingroup\$

Visualise the Euclidean GCD

\$\endgroup\$
1
  • \$\begingroup\$ Again, going to assume code-golf? \$\endgroup\$ Commented Oct 3, 2023 at 10:57
2
\$\begingroup\$

Is this your answer?

NOTE: The scoring criterion for this is currently broken. I'll fix it at some point ™


In this challenge, you must write an answer that distinguishes itself from all previous answers. No matter what input is passed in, it must output one of two consistent values. Your answer must output one value, marked as "truthy", when your answer's code is input, and the other value, marked as "falsy", when the code of at least one previous answer is input. Whichever value it outputs when anything else is input does not matter as long as it outputs one of the two values.

However, you are not only trying to distinguish your answer from others, but also to trick previous answers into thinking your source code is their own and outputting their truthy value.

Your answer's score is \$\frac{\text{byte count} + 2}{\text{tricked answers } \cdot \text{ answers that don't trick you}}\$, where "tricked answers" is the number of previous answers that output their truthy value when given your code, and "answers that don't trick you" is the number of previous answers for which your answer correctly returns the falsy value. Your answer must trick at least one previous answer and not be tricked by at least one previous answer.

For example, if the first answer was the Python program print(1), then a valid second answer would be the JavaScript function x=>x.includes('x'), which checks if the input string contains a x, returning true for itself, false for the singlee previous answer, and either true or false for any input string. As the previous answer prints a 1 when given this code, this would score \$\frac{18+2}{1 \cdot 1} = 20\$.


First answer (will be posted along with the question):

1: Python 3, 8 bytes

print(1)

Try it online!

Outputs 1 for truthy and 0 for falsy.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ So I insta-win by having a 0 byte answer that tricks at least 1 program? \$\endgroup\$
    – lyxal
    Commented Oct 3, 2023 at 23:36
  • \$\begingroup\$ @lyxal Yes, but it'd need to be a zero-byte answer that outputs one of two consistent values no matter what input is provided, so no Vyxal zero-byte cat for you. I don't think a zero-byte answer is possible, and tricking at least one program (the first) is guaranteed. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 23:38
  • \$\begingroup\$ Try it Online! \$\endgroup\$
    – lyxal
    Commented Oct 3, 2023 at 23:39
  • \$\begingroup\$ @lyxal Yes, but it also needs to output a different, truthy value when your program is input. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 23:40
  • \$\begingroup\$ Try it Online! \$\endgroup\$
    – lyxal
    Commented Oct 3, 2023 at 23:41
  • \$\begingroup\$ @lyxal It needs to output a falsy value when print(1) is input, a truthy value when your source code is input, and one of those two values for any other possible input. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 23:42
  • \$\begingroup\$ The first answer doesn't comply with that rule, so it should be considered invalid. \$\endgroup\$
    – lyxal
    Commented Oct 3, 2023 at 23:43
  • \$\begingroup\$ @lyxal The first answer doesn't have to output a falsy value because there are no answers before it which would require outputting said falsy value. \$\endgroup\$
    – emanresu A
    Commented Oct 3, 2023 at 23:44
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – lyxal
    Commented Oct 3, 2023 at 23:44
  • \$\begingroup\$ Are duplicate answers (identical source-code as previous answer) allowed? \$\endgroup\$
    – bsoelch
    Commented Oct 4, 2023 at 7:23
  • \$\begingroup\$ @bsoelch ... yes, and that results in one more tricked answer for a slightly lower score... this scoring criterion is annoying. \$\endgroup\$
    – emanresu A
    Commented Oct 4, 2023 at 9:41
  • \$\begingroup\$ Just chipping in to say that i dont think identical answers should be allowed, and that if someone really wants to they should be allowed to tank their score in bytes by just trying really hard not to get tricked :-) it just seems right to me in my opinion so thats all i have to say \$\endgroup\$ Commented Oct 4, 2023 at 16:05
  • \$\begingroup\$ The problem is, people could add an answer that is extremely similar to the previous answer, say with a comment added or two, and under the current scoring system do better \$\endgroup\$
    – emanresu A
    Commented Oct 4, 2023 at 19:00
  • 1
    \$\begingroup\$ A late true detector has ->0 score \$\endgroup\$
    – l4m2
    Commented Oct 8, 2023 at 3:36
2
\$\begingroup\$

Is it a Valid Crossword Grid?

\$\endgroup\$
4
  • \$\begingroup\$ Suggested tags: crossword, grid \$\endgroup\$
    – pajonk
    Commented Jul 27, 2022 at 5:45
  • 3
    \$\begingroup\$ I don't see any clever algorithm for grid generation (that doesn't mean that there isn't one), so the answers are most likely use the brute-force method of generating all grids and checking their crosswordness - why not make it decision-problem then? \$\endgroup\$
    – pajonk
    Commented Jul 27, 2022 at 5:51
  • \$\begingroup\$ @pajonk I've modified the question as per your suggestion, but that makes it very similar to a previously posed question, so I'm unsure about this. I think there are some meaningful shortcuts to make the generation easier. \$\endgroup\$ Commented Jul 27, 2022 at 18:56
  • \$\begingroup\$ if you see shortcuts that make generation easier than brute-force, then ignore my previous comment. \$\endgroup\$
    – pajonk
    Commented Jul 28, 2022 at 9:36
2
\$\begingroup\$

Expected number of rounds for this labeling scheme

\$\endgroup\$
7
  • \$\begingroup\$ If one simulates ALL runs long enough (say up to length \$10^n\$) then it's deterministic and provably returns the correct answer with enough accuracy. Is that something you want? \$\endgroup\$ Commented Oct 19, 2023 at 2:28
  • \$\begingroup\$ @CommandMaster This is something that I would like to prevent if possible, but I am not sure how to go about doing this. The thing is that all these values are exact rational numbers, meaning that if I wanted to, I could require the answer to be (numerator, denominator) pairs and this would prevent simulation answers. But this would be inconvenient for everyone as most languages don't have a built-in fraction type and would have to do extra work to keep track of the numerator and the denominator in the code. \$\endgroup\$
    – Aiden Chow
    Commented Oct 19, 2023 at 3:29
  • \$\begingroup\$ But then by allowing floating point output, I'm allowing for answers like the one you mentioned by just simulating all possibilities up to a certain point, and that isn't what I want. \$\endgroup\$
    – Aiden Chow
    Commented Oct 19, 2023 at 3:29
  • \$\begingroup\$ Perhaps you can require that the algorithm is correct theoretically - if floating-point numbers had infinite accuracy. \$\endgroup\$ Commented Oct 19, 2023 at 3:31
  • \$\begingroup\$ @CommandMaster Is that something that is "observable"? I'm worried about setting any unobservable requirements. \$\endgroup\$
    – Aiden Chow
    Commented Oct 19, 2023 at 3:53
  • \$\begingroup\$ While unobservable requirements are generally discouraged, theoretical correctness is usually an exception. See this meta post, for example \$\endgroup\$ Commented Oct 19, 2023 at 5:02
  • \$\begingroup\$ @CommandMaster I made an edit with what you suggested. Can you check if the wording is correct, or anything wrong with how I said it? \$\endgroup\$
    – Aiden Chow
    Commented Oct 19, 2023 at 5:42
2
\$\begingroup\$

Smallest infinite irreducible program


A typical constraint for challenges, where the goal is to make your code as long as possible, is that your program must be "irreducible". I.e., no subset of characters can be removed from your program with it still being valid. If your code was xyz, none of x, y, z, xy, yz, or xz could do the same task as xyz. This makes it impossible to use comments, string literals, long variable names, or whitespace to pad out your code length, but through some trickery it's possible to design a program which can be made arbitrarily large while still being irreducible.

In this challenge, you'll try to golf the setup for this. Your submission will be a finitely sized "base" program, which is irreducible, and which can be increased to an arbitrarily high size through the addition of substrings at a chosen point (or set of points) in the program.

For example, a base program might look like wx()yz, and continue to function and be irreducible with the insertion of arbitrarily many abs in between the ()s (such as wx(ababab)yz). You can also require substrings to be inserted in multiple places at once (e.g., you might need a 1 to be appended to the program for each ab, so the previous example would look like wx(ababab)yz111).

Scoring:

Your score is the size in bytes of your base program. Your base program must be irreducible on its own; if the insertion of some minimum number of your chosen substring(s) is necessary for this, those must be included in the score.

Task:

Your irreducible program must do any one of the following tasks, of your choice:

  • Truth machine: Take an input. If the input is 0, print 0 and stop. If the input is 1, print 1 indefinitely
  • Arithmetic: Take two inputs, x and y. Print x + y².
  • Constant output: Print the string Good morning!

You may write a program or a function. If you choose to write a function, instead of printing you may return the output. For the truth machine task, you must use an infinite list/iterator if you return a value; you must have some way of getting an arbitrary number of 1s out of the return value in finite time (so you can't just append 1s to a list infinitely, and return the list once the infinite loop would stop).

\$\endgroup\$
5
  • \$\begingroup\$ If your code is xyzw and xz does the job it isn't irreducible, right? \$\endgroup\$ Commented Nov 5, 2023 at 7:37
  • 1
    \$\begingroup\$ I'm fairly sure there isn't an infinite set of strings such that none of them are a subsequence of one another, and this challenge is impossible \$\endgroup\$ Commented Nov 5, 2023 at 7:37
  • 1
    \$\begingroup\$ How can the program continue to be irreducible after inserting characters? The base program can be obtained by removing a subset of characters from the extended program and is also a valid program. \$\endgroup\$
    – bsoelch
    Commented Nov 5, 2023 at 8:49
  • \$\begingroup\$ See Higman's lemma, which says there isn't such an infinite set \$\endgroup\$ Commented Nov 5, 2023 at 19:07
  • \$\begingroup\$ Oh true, I guess I need to change how the insertion works \$\endgroup\$ Commented Nov 6, 2023 at 14:26
2
\$\begingroup\$

Find the fairest partition of a list

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should clarify that parts don't have to be continuous, currently it has to be deduced from the examples \$\endgroup\$ Commented Oct 30, 2023 at 7:30
  • \$\begingroup\$ Nice challenge. Shouldn’t the result for the fourth one be zero? \$\endgroup\$ Commented Nov 1, 2023 at 23:27
  • \$\begingroup\$ I’d probably also say absolute difference to be clear. \$\endgroup\$ Commented Nov 1, 2023 at 23:30
  • \$\begingroup\$ Are the lists guaranteed to be sorted? If so, may a submission take input sorted in descending order rather than ascending? \$\endgroup\$ Commented Nov 2, 2023 at 22:22
2
\$\begingroup\$

Make Code Printing X Without X

\$\endgroup\$
3
1
46 47
48
49 50
157

You must log in to answer this question.

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