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

4643 Answers 4643

1
130 131
132
133 134
155
0
\$\begingroup\$

Draw me a circle

Given a radius \$r\in\mathbb{N}\$ and \$r\geq 3\$, draw an ASCII circle for me, using \$x\$'s. Your circle does not have to look perfect, it just has to be identifiable as one. To make the circle look good, you have to use a \$2:1\$ ratio for width and height of the circles. This is due to characters being taller than wide.

One thing that is required though is an appropriate angle increment. I reccomend \$r\times3\$.

You do not have to account for float rounding errors!

Given the radius \$5\$, your output should look similar to this:

     x x x x x x     
    x           x    
 xx               xx 
 x                 x 
x                   x
 x                 x 
 xx               xx 
    x           x    
     x x x x x x 

IO

Input and output can be in any reasonable form.

More test-cases

Note that these don't have to be an exact match!

3 ->   
        x x xx    
      xx       xx 
     x           x
      xx       xx 
         xx x x  

7 -> 
        xx x x x x xx        
      x               x      
    x                   x    
  xx                     xx  
 x                         x 
 x                         x 
x                           x
 x                         x 
 x                         x 
  xx                     xx  
    x                   x    
      x               x      
        xx x x x x xx  
\$\endgroup\$
2
  • \$\begingroup\$ what does "appropriate angle increment?" mean? does it rule out drawing a circle without using angles? \$\endgroup\$
    – don bright
    Sep 27, 2021 at 2:09
  • \$\begingroup\$ how many percent of it should match? i could fill the entire board and say it match. I recommand giving a fixed shape and enlarge it with size increase. \$\endgroup\$
    – okie
    Sep 28, 2021 at 1:02
0
\$\begingroup\$

Drop down the numbers

\$\endgroup\$
9
  • \$\begingroup\$ What happens when two non-zero entries ought to go to the same place? For example" What if a column is 2, 1, 0? What does that column become? \$\endgroup\$
    – Wheat Wizard Mod
    Sep 22, 2021 at 21:34
  • \$\begingroup\$ Also what if a number can't move down far enough? e.g. a 1 in the bottom row, or a 2 in the bottom two rows. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 22, 2021 at 21:35
  • \$\begingroup\$ @WheatWizard Edited to clarify. \$\endgroup\$ Sep 22, 2021 at 22:06
  • 1
    \$\begingroup\$ what do you mean by big number decide? Can you give out a simple example to explain it? thanks :D \$\endgroup\$
    – okie
    Sep 23, 2021 at 5:36
  • 1
    \$\begingroup\$ @okie Explained \$\endgroup\$ Sep 23, 2021 at 13:08
  • \$\begingroup\$ Thanks for the explanation, it's much clearer now, anyway, i think the second example's 4th row is wrong? \$\endgroup\$
    – okie
    Sep 24, 2021 at 0:09
  • \$\begingroup\$ @okie Fixed. Any other problems with the test cases? \$\endgroup\$ Sep 24, 2021 at 0:12
  • \$\begingroup\$ @AlanBagel I think it's good to go now! just remember to add rules and any extra stuff that you want to mention. For example: standard rules applys and such \$\endgroup\$
    – okie
    Sep 24, 2021 at 0:20
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Sep 26, 2021 at 14:03
0
\$\begingroup\$

Irreducibile Polynomials

in progress

todo, add several test cases. and figure out how to deal with verifying answers. figure out how references work, not just using plain hyperlinks.

As you may know, Polynomials are mathematical expressions of the sum of a variable raised to various powers and multiplied by various coefficients. For example consider the variable \$x\$

\begin{array}{11} 3x^2 & \mbox{ exponent is 2, leading coefficient is 3 } \\ 3x^2 + 16x & \mbox { add a term with exponent = 1, coefficient = 16 } \\ 3x^2 + 16x + 7 & \mbox { add another term, with exponent = 0, constant coefficient = 7 } \\ \end{array}

In general we can write a polynomial named \$P\$ as a function of \$x\$ as follows: $$ P(x) = a_mx^m + a_{m-1} x^{m-1} ... + a_1 x^1 + a_0 x ^ 0 $$

Polynomials are somewhat similar to integers in that they can be factored into smaller polynomials that when multiplied together give the original polynomial. This process can be repeated until the integer or polynomial cannot be factored anymore. For integers this smallest factor is called a Prime, but for Polynomials it is called Irreducible. For integer polynomials over the integers, which is what this challenge is limited to, we have the following examples:

$$ \begin{array}{11} \mbox{polynomial} & \mbox{irreducible factors} \\ x^2-1 & (x-1),(x+1) \\ x^5-x^4-2x^3-8x^2+6x-1 & (x^2 - 3x + 1),(x^3 + 2x^2 + 3x - 1) \\ 6x^2 + 243x - 378 & (x+42),3,(2x-3) \\ \end{array} $$

How do we know a polynomial is irreducible? We could do trial polynomial-division on all possible smaller polynomials, but it turns out that there are several algorithms that can quickly tell us if a polynomial is irreducible.

This challenge is to write a program that returns True if a given Polynomial meets any of the four irreducibility criteria given below.

This is Code Golf - fewest number of bytes wins!

Criteria 1: Gotthold Eisenstein

First your program should determine if the input polynomial meets the irreducibility criteria of Gotthold Eisenstein. This criteria looks for the existence of a special number \$q\$ such that the following are true:

  • \$q\$ is prime
  • \$q\$ is not a factor of the Leading Coefficient
  • \$q\$ is a factor of all the non-Leading Coefficients
  • \$q^2\$ is not a factor of the Constant Coefficient

For example:

$$P(x) = 3x^3 + 15x^2 - 25x + 10$$

has a \$q\$ of 5, where

  • 5 is prime
  • 5 is not a factor of the leading coefficient 3,
  • 5 is a factor of the non-leading coefficients 15, -25, and 10
  • 5 squared is not a factor of the constant coefficient 10

Therefore \$P\$ is irreducible, and your program should return True

Criteria 2: Oskar Perron

In 1907 Oskar Perron's paper describes a criteria that does not require factoring the coefficients. Recall that polynomial P can be written as

$$ P(x) = a_{m}x^m + a_{m-1} x^{m-1} ... + a_1 x^1 + a_0 x^0 $$

  • Assume \$P\$ is monic, which means the leading coefficient \$a_{m}\$ is \$1\$.
  • Assume \$a_0\$ is not \$0\$
  • If the absolute value of \$a_{m-1}\$ is greater than the sum of all the other coefficient's absolute value, then \$P\$ is irreducible
  • In more mathy language:

$$ |a_{m-1}| > \sum_{\substack{i=0\\i\neq{m-1}}}^{m} |a_i| \implies P \mbox{ is irreducible} $$

Example:

  • \$P(x)=x^{38797389} - 55x^2 + 2x - 9\$
  • \$a_m=1\$ and \$a_0 \ne 0\$
  • \$|a_{m-1}| = 55\$
  • Sum of other coefficients absolute value is \$1+2+9 = 12\$
  • \$55 > 12\$

Therefore \$P\$ is irreducible, and your program should return True

Criteria 3: Michael Filaseta 1988

Next we visit Michael Filaseta's 1988 paper in which he describes the following wonderful criteria: If \$P(x)\$ is an integer polynomial of degree \$<= 31\$ which has non-negative coefficients, and \$P(10)\$ is prime, then \$P\$ is irreducible.

For example:

  • \$ P(x) = x^8+2x^4+23 \$
  • \$P\$ is of degree 8, which is less than or equal to 31
  • \$ P(10) = 100020023 \$
  • \$100020023\$ is prime

Therefore \$P\$ is irreducible, and your program should return True

Criteria 4: Filaseta and Gross

In 2014 Filaseta and Samuel Gross published the following remarkable criteria, which doesn't depend on the degree of the polynomial:

  • Consider \$P(x)\$ an integer polynomial with coefficients between \$0\$ and \$49598666989151226098104244512918\$.
  • If \$P(10)\$ is prime then \$P\$ is irreducible

For example

  • \$ P(x) = 54x^{38} + 78783x^{33} + 035033459404x^{21} + 1190354877x^{11} + 56007093177 \$
  • all coefficients are between \$0\$ and \$49598666989151226098104244512918\$
  • \$ P(10)= 5478783035033459404119035487756007093177 \$
  • \$5478783035033459404119035487756007093177\$ is prime

Therefore \$P\$ is irreducible, and your program should return True

Input format

The input format can be whatever is easiest for your language, and if your language has built-in polynomials, that is allowed. The test-case polynomials can be converted to your chosen format before processing into your program. You can take input as an argument to a function, as standard input, or whatever is easiest for your language.

If your language has no built-in polynomial format, one suggestion is to look at the PolyNumber format - that is, an array listing the coefficients, and the position within the array indicating the exponent. Lowest powers come first. For example

$$x^2+1 \mbox { is } [1,1] $$ $$2x^3+5x^2+7x+4 \mbox { is } [4,7,5,2] $$ $$x^4 + 5 \mbox{ is } [ 5,0,0,0,4 ] $$

Extra notes

First, please note these criteria are sufficient but not necessary. This means that if a polynomial meets the criteria, then it is irreducible. However, just because it doesn't meet the criteria, that doesn't mean it's not irreducible. For the challenge, your program just needs to return True if an irreducibility criteria is satisfied. Returning a non-True value will simply indicate the criteria were not satisfied, it won't necessarily mean that the input polynomial is or isn't irreducible.

Second, a quick glossary of terminology, for polynomial \$P\$ we have the function

$$P(x) = a_mx^m + a_{m-1} x^{m-1} ... + a_1 x^1 + a_0 x ^ 0 $$

  • Leading Coefficient - the coefficient of the highest power term: \$a_m\$
  • Constant Coefficient - the coefficient of the 0th power term: \$a_0\$
  • Degree - The value of the highest exponent: \$m\$
  • Integer Polynomial - a polynomial where all coefficients are integers
  • Monic Polynomial - a polynomial with Leading Coefficient of 1

For example let us create an integer polynomial with degree 9, a leading coefficient of 42, and a constant coefficient of -7, as follows:

$$ 42x^9-7 $$

Refs

Filaseta, M. (1988). Irreducibility Criteria for Polynomials with non-negative Coefficients. Canadian Journal of Mathematics, 40(2), 339-351. doi:10.4153/CJM-1988-013-6

https://bigprimes.org/

https://www.sciencedirect.com/science/article/pii/S0022314X13002539

\$\endgroup\$
2
  • \$\begingroup\$ It's clear that a lot of work has gone into this, but I question whether asking for solutions to test against multiple rigid criteria (one of which includes a 32 byte constant) isn't pulling in the opposite direction to code golf. It's unclear to me how much scope there is for creativity here, since each criterion includes a prescribed set of conditions that are mostly independent of each other. Have you considered just asking whether a given polynomial is irreducible? \$\endgroup\$
    – Dingus
    Oct 12, 2021 at 5:43
  • \$\begingroup\$ well its a good point but... but i was hoping that these four techniques are not as independent as they appear to be at first glance. Also asking "is this irreducible" only has one answer, to fully factor the polynomial, which systems like Mathematica automatically will win. \$\endgroup\$
    – don bright
    Oct 14, 2021 at 8:10
0
\$\begingroup\$

Hearts KotH

Your challenge, should you choose to accept it, is to write a Java bot to play a simplified version of hearts.

Hearts is a four-player trick-based card game. To start a round of hearts, each player is dealt 13 cards. The player who has the two of clubs starts by playing the two of clubs. Going around the circle each player plays another card, in the same suit as as the first card if possible. Once every player has played one card, the trick is complete, and goes to the player who placed the highest valued card in the original suit (aces are high). The player who takes the trick is responsible for all of the points contained in the trick, as well as leading the next trick. This continues until all players are out of cards, at which point the hand is complete.

During a hand, each heart taken is worth 1 point and the queen of spades 13 points. If during the course of a hand one player receives all 26 points, they shoot the moon and receive zero while everyone else receives 26 points. The game ends once a player clears 100 points, at which point the player with the lowest score wins.

The Challenge ​

Write a Java 11 bot extending a (todo) abstract class. A new bot will be instantiated for each hand. Every combination of 4 bots will play one game with each other. After all of the games are complete, the bots will be scored on the total number of wins (higher is better), with the tiebreaker being the average score per game (lower is better).

Tampering with the controller, tampering or instantiating other bots, damaging my computer, taking an excessively long time to complete a turn, failing to compile, violating standard loopholes, or throwing a runtime Error is strictly prohibited and will result in disqualification. Throwing an exception will result in a 1 point penalty and the controller playing for you in an unspecified manner. Nondeterministic bots and storing data between both Hands and games are permitted.

Meta:

Is this clear enough?

I haven't written the controller yet, is there any data in particular that you would like to see the bots receive (among other things, a way to determine the legality of the move, as well as cards played are already passed in)?

\$\endgroup\$
4
  • \$\begingroup\$ How are the cards distributed? If it's random, I'm worried there won't be much strategy possible and it'll mostly just be a random outcome. \$\endgroup\$ Oct 5, 2021 at 17:22
  • \$\begingroup\$ @RedwolfPrograms the plan right now is random, but it doesn't have to be. My theory was that since there are typically 5-10 hands per game in real life, the law of large numbers would win out. In real life, while the game is slightly more complicated all strategies boil down to card counting and probability-based heuristics anyway, and you can get quite good at it. \$\endgroup\$
    – Aiden4
    Oct 5, 2021 at 17:33
  • \$\begingroup\$ It seems like card counting and probability based heuristics would both make for a pretty boring KotH, since while they'd be challenging to keep track of as a human, a bot could be optimized without too much work being necessary. \$\endgroup\$ Oct 5, 2021 at 19:04
  • \$\begingroup\$ @RedwolfPrograms the way things are set up currently, the relatively boring task of counting cards is mostly handled by the controller. Also, most KotH challenges have been probability based heuristics, like the various rock paper scissors challenges and the various prisoner's dilemma based challenges. Still, if the consensus seems to be that this won't do very well I will head back to the drawing board. \$\endgroup\$
    – Aiden4
    Oct 5, 2021 at 20:35
0
\$\begingroup\$

Optimize my Cruise Control

My cars cruise-control functionality has 4 different methods of adjustment, all using a single stalk. They are as follows:

  • Hard press up (press until you feel the click): +5 mph
  • Soft press up (press lightly, but not to the click): +1 mph
  • Soft press down (press lightly, but not to the click): -1 mph
  • Hard press down (press until you feel the click): -5 mph

If your current speed is not a multiple of 5, a hard press will take you up/down to the nearest 5 multiple.

The challenge is to write a function that takes your current speed and target speed as parameters, and outputs the shortest sequence of stalk inputs to get from current -> target speed.

Rules:

  • Take 2 integers as input
  • Return a list/iterable/whatever of the minimum actions needed to get to target speed

Examples: (U is hard up, u is soft up, d is soft down, D is hard down)

[5, 6] -> [u]
[20, 37] -> [U,U,U,u,u]
[42, 45] -> [U]
[16,23] -> [U,u,u,u] or [U,U,d,d]

currently known issues

  • needs more examples
  • similar to the Optimal Change problem.

Other possible improvements

  • Maybe make it a more generalized function that takes 4 inputs [v_current, v_target, delta_small, delta_large]. This would have the effect of complicating the logic and making the problem a bit less trivial.
\$\endgroup\$
0
\$\begingroup\$

Write an interpreter for "MathScript"

I had an idea for a new language, it's called MathScript! I got the idea from Mathematica.

Basically, this is how it works:

  • Functions are called by using the following syntax: FunctionName{some, arguments, separated, by, commas}
  • The builtin functions are Display, Add, Sub, Mul, IntDiv, FloorDiv, Pow, Factorial, FibN, and OddEvenQ

The first few function names are pretty descriptive. IntDiv and FloorDiv calculate the integer division and floor division, respectively. FibN calculates the N'th Fibonacci number, and OddEvenQ returns 1 if a number is even and 0 if it is odd.

  • Variables are created as so: <Name> :: <Value>
  • The syntax for changing variables is the same as the syntax to change variables.
  • The syntax for for loops are as following: LoopN{<n>} :: [some, statements, separated, by, commas]

Test Cases

---
Display{Factorial{Add{2, 3}}} => 120
---

---
a :: 1
LoopN{3} :: [a :: Add{a, 1}, Display{a}] => 2 <newline> 3 <newline> 4 <newline>
---

---
num :: Add{Sub{1, 2}, Mul{Pow{2, 3}, Add{1, 2}}}
odd_or_even0 :: OddEvenQ{num}
num :: Factorial{num}
odd_or_even1 :: OddEvenQ{num}
Display{odd_or_even0} => 0
Display{odd_or_even1} => 1
---

Scoring

This is , so the fastest answer wins. The testing will be on an i7 processer Windows 10 machine. The test case will be LoopN{10} :: [LoopN{10} :: [Display{Add(2, Pow{3, 4})}]].

Some clarification

Whitespace is ignored. Trailing commas in function arguments is allowed. You can assume that the input will always be correct. Display outputs something to stdout. Case is significant. (e. g Loopn != LoopN) If there are multiple statements, they can be separated by newlines or nothing at all. Blank lines can be anywhere.

Language types

The types are the string (specified between double quotes or single quotes), the integer, and the float. Integers can be specified using normal numbers like 5 and 7383. The integer limit is [-232, 232] (32-bit). Floats can be specified using normal math notation, so these are all valid floats:

2.0
3.4
3.141592653
.8
2.

The LoopN function's first argument can be a integer literal, or a predefined variable.

One Final Note

Compilers are allowed.

Meta

  • Any suggestions?
  • Anything to clarify?
\$\endgroup\$
13
  • \$\begingroup\$ Is whitespace significant, or only used to separate tokens? Are trailing commas allowed? Will the input ever have a syntax error? What does display do? I assume it prints out something, but how does it print it out? Is case significant? If so, shouldn't your second test case should read LoopN? In your first test case you use Print, did you mean Display? The second test case seems to have multiple statements; how are statements separated? Are they always separated by newlines, or can it be any token separator? If they're always separated by newlines, can newlines appear anywhere else? \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:28
  • \$\begingroup\$ Every challenge has to have an objective scoring criterion; what is it for this challenge? Consider code-golf or fastest-code. \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:29
  • \$\begingroup\$ I see that you've tagged this fastest-code; this scoring criterion often involves a bit more work for the author, as all answers have to be scored on the same machine for fairness. If you use this scoring criterion, you should specify what machine you'll be running submissions on, as well as what test cases the input will be run on. \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:33
  • \$\begingroup\$ Some feedback re the language itself: there's no obvious conditional construct, though one can use LoopN{<cond>} :: [ <body> ] if cond is known to be either 0 or 1, and Pow{0, Pow{0, Pow{<cond>, 2}}} to convert <cond> to 1 if non-zero, or 0 if 0. Additionally, there's no obvious way to check for equality, other than using something like Pow{0, Pow{Sub{A, B}, 2}}, and no obvious way to check for greater than or less than. \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:42
  • \$\begingroup\$ More questions re the challenge: What are numbers? Are they all ints? All floats? What's the difference between IntDiv and FloorDiv? What are all of the valid ways to specify a number? What precision should be supported for numbers? Possible options include arbitrary precision (this would be helpful towards making the language turing-complete), implementation-defined (e.g. whatever your language supports), or something specific like IEEE-754 double precision floats. \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:46
  • \$\begingroup\$ How does LoopN work? Can you pass it a computed value, or does it have to be a number literal? If it's a computed value, is it recomputed every time, or stored after the first time? If it's recomputed, you could create while loops, which would be helpful for turing-completeness. \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:48
  • \$\begingroup\$ How many arguments do each of the functions take? What happens if a function is called with an incorrect number of arguments? Can that be assumed not to happen, or should some kind of error be outputted? \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:50
  • \$\begingroup\$ Does FibN support a non-positive index? If not, can it be assumed to not be called with that, or should an error be outputted? What happens if you divide by zero? \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:52
  • \$\begingroup\$ What happens if you call Factorial with a negative number? Does Factorial support an input of 0? (it probably should) \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:53
  • \$\begingroup\$ If floats exist in the language, what does OddEvenQ do if you pass it a non-integer? \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 21:54
  • \$\begingroup\$ Are compilers allowed? \$\endgroup\$
    – tjjfvi
    Sep 26, 2021 at 22:07
  • \$\begingroup\$ The second test case are looking weird, isn't the output should be 2 \n 3 \n 4 \n? \$\endgroup\$
    – okie
    Oct 4, 2021 at 4:59
  • \$\begingroup\$ I feel like you should add more MathScript programs to test with. An answer could optimize solely for the single test case you've given. \$\endgroup\$
    – user
    Oct 6, 2021 at 1:01
0
\$\begingroup\$
\$\endgroup\$
0
\$\begingroup\$

Balanced Bracket Sequence

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

Pattern in Prime

Given a positive integer less than 100 with no preceding zeros we have to find all 12 digit primes that contains the maximum number of time the given pattern.

Note: Pattern's occurance can overlap. For example 11 occur 6 times in 1111111

Example:

pattern = 1 , count = 13 the maximum occurance is in 111111110111, eleven, and those 12 digit primes are {101111111111,111011111111,111111011111,111111110111,111111111101,111111111511,111111111611,111111211111,111113111111,111211111111,111511111111,116111111111,311111111111}

pattern = 22 , count = 1 {522222222229}

pattern = 69, count = 162

pattern = 37, count = 151

Output format: first line should be count of such primes, and then print the primes in sorted order

If possible while answering please write a short explanation of what you did. This is , so the shortest answer in bytes per language wins.

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

Best Rotation

If we rotate a raster image by some angle that is not a multiple of \$90°\$, we will have to use some kind of interpolation. Depending on what kind of interpolation method we use, we get a better or a worse quality. This is especially apparent if we repeat the rotation multiple times. In the following image we se the original on the top left, and then the result of different interpolation methods when used to rotate the original \$360\$ times by \$1°\$.

salvator mundi \$\renewcommand\phi\varphi\$

Challenge

Given some angle \$\phi\$ Your task is to find a method to find a (deterministic) function \$f_\phi\$ that takes some image \$I\$ and rotates it by \$\phi\$.

Scoring (not solved yet)

META this is the issue. Ideally we'd like to have some objective criterion. But so far I have not managed to find one that cannot be gamed:

  1. If we just let the participants rotate an image by some angle \$\phi\$ how can we then compare it to the "exact" solution? Maybe their method is better than the best standard method, even if they have to apply it repeatedly. So it seems we can only truly check against a total rotation that is a multiple of \$90°\$.

  2. Let's say we say we use an angle of \$\phi = 2\pi/n\$ and let them apply their "rotation" \$n\$ times to measure e.g. the \$l^2\$-error \$E = \Vert I - f_\phi(\ldots f_\phi(I)\ldots)\Vert_2\$ . This means they could just use \$f_\phi = id\$.

  3. If we instead use a total rotation of e.g. \$\pi/2\$ (that is \$\phi = \frac{\pi}{2n}\$, with \$n\$ rotations). Then the participants could just use some permutation of pixels that just happens to rotate the image after \$n\$ rotations exactly (or maybe exactly except for some pixels).

So does anyone have another suggestion of how to objectively measure it without introducing any hand-wavey rules?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ My gut feeling is that if this problem were phrasable in an objective manner it would basically already be solved. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 14, 2021 at 21:50
  • \$\begingroup\$ @WheatWitch Maybe it is solved but I don't think the objective "rules" matter - I'm just trying to make rules that don't have loopholes. For instance for the approach of measuring the error of repeted rotations totalling 90° I'd like that the intermediate images also look very much like the original. Any "sane" algo would obey that, but I just struggle to find a way to enforce this without any hand-waveyness. \$\endgroup\$
    – flawr
    Oct 15, 2021 at 11:48
  • \$\begingroup\$ As an alternative I'm considering actually dropping the idea of seeking "sane" algorithms and encouraging pathologic algorithms that manage to do great 90° rotations while having visually nonsense intermediate images. But I think that this is trivial, as I outlined in (3.). \$\endgroup\$
    – flawr
    Oct 15, 2021 at 11:50
  • \$\begingroup\$ A third idea would be some kind of king-of-the-hill where each submission will be paired with every other submission to rotate the image a total of 90° and then find some kind of average score. \$\endgroup\$
    – flawr
    Oct 15, 2021 at 11:51
0
\$\begingroup\$

Halve Code Regen

TODO: This is a horrible title.

Your challenge is to write a program, and when I half the program, the output must stay the same. Then, I will halve it and add the last two characters, and the output should be the same with the program's last two characters at the end.

Sometimes the code can't be halved evenly, and when that happens, I will do something similar to floor division:

blahy => bl
horse => ho
meddle => med (regular halving)
oof => o

Example for "the output should be the same with the program's last two characters at the end"

Let's say we have this code:

q|w_a2e(o+2ei2ere

and the output is

q|w_a2e(o+2ei2ere

when I change it to

q|w_a2e(o+2ei2erere

by adding the last two characters (re), the output should look like

q|w_a2e(o+2ei2erere

(Note the extra re at the)

Rules

  • No padding with comments
  • The program must have at least 2 characters.
  • Standard loopholes apply
  • The output cannot be empty.

Scoring

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

How I came up with the random code in the example two sections ago

q means quine. | is a separator. w_a2e means when the last two characters are added to the end. (o+2e means add the last two characters to the end. i2ere means ignore a repeated 2e at the end.

Meta

  • Is this even possible?
  • If so, any other suggestions?
\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think this would be more interesting if multiple halves of the program had to work. Otherwise it's just output something (or nothing since it doesn't look like you've ruled that out.) and then pad the program out with comments. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 27, 2021 at 13:30
  • \$\begingroup\$ @WheatWizard Fixed. Any idea for a better title? \$\endgroup\$ Sep 27, 2021 at 13:34
  • 1
    \$\begingroup\$ That's not quite what I meant. I mean that splitting the same program in half multiple ways ought to preserve the output. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 27, 2021 at 13:39
  • \$\begingroup\$ Also you should definitely restrict the output further. At the very least it should have to be non-empty. You should also require the programs to be at least 1 or 2 bytes long. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 27, 2021 at 13:39
  • \$\begingroup\$ @WheatWizard Fixed. \$\endgroup\$ Sep 27, 2021 at 13:43
  • \$\begingroup\$ I still can't decide on a better title, though. \$\endgroup\$ Sep 27, 2021 at 14:17
  • \$\begingroup\$ I don't understand what the "the output should be the same with the program's last two characters at the end" part means. Can you show a full example of what you do to the program? \$\endgroup\$ Oct 16, 2021 at 19:05
0
\$\begingroup\$

Integer points on Hyperspheres

Given two non-negative integers \$r\$ and \$d\$, write a program that will output the number of integer points that lie on all hyperspheres of dimension \$d\$ or lower with radius \$r\$ or lower.

For example, given \$r = 5, d = 2\$, the program would do something like this:

The hypersphere of dimension 2 is a circle. The radius is 5. There are 12 integer points on this circle, as follows: $$(5,0),(4,3),(3,4),(0,5),(-3,4),(-4,3),(-5,0),(-4,-3),(-3,-4),(0,-5),(3,-4),(4,-3)$$

If the radius is 4, there are 4 integer points: $$(4,0),(0,4),(-4,0),(0,-4)$$

If the radius is 3, again it's 4 integer points. If the radius is 2, again 4. Radius 1 - again, 4. Radius 0 has only 1 integer point. If we add all these up it's 12 + 4 + 4 + 4 + 4 + 1 , or 29 points total for the 2 dimensional hyperspheres with radius \$<=5\$.

Now if we take the dimension 1 hypersphere, it is interpreted as 2 points in a one dimensional space, distance r from the origin. For example the 1 dimensional hypersphere with radius 5 has only two points, $$(5),(-5)$$ and their coordinates are only single dimensional. So, the dimension 1 hypersphere with radius 5 has two integer points. The dimension 1 hypersphere with radius 4 also has 2 integer points, and so on. The total integer points on all 1 dimensional hypspheres with radius 0 to 5 is 2 + 2 + 2 + 2 + 2 + 1, or 11.

The dimension 0 hypersphere is defined for this challenge to have 0 points.

So the final output of a program with input \$r = 5, d = 2\$ will be 29 + 11 + 0, or 40.

  • You may assume that r and d will be low enough so that the integer type of your language will be large enough so that it can represent the answer. In other words if your language has only 16 bit integers, then you can write a program that assumes r and d will be low enough so that the final answer is between 0 and 65535.

  • This is Code Golf, lowest # of bytes wins

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is essentially Pythagorean triples but generalised to d-tuples, right? (and allowing 0) \$\endgroup\$
    – pxeger
    Oct 18, 2021 at 10:42
  • \$\begingroup\$ i think so, yes, that sounds correct... \$\endgroup\$
    – don bright
    Oct 19, 2021 at 2:11
0
\$\begingroup\$

Same String Regardless of Repetition

Challenge

Write a full program that prints a string that has a length of at least 1. When the source code is repeated any amount of times, that string should still be outputted. For example, if my source code is ABC and it prints Hello, World!, then ABCABC will still print Hello, World! and ABCABCABC will also print Hello, World! and etc.

Rules

  • It has to be a full program that takes no input (or have an unused input if this is impossible) and prints the string to STDOUT.
  • The program and the string have to be at least 1 byte long.
  • The strings that are outputted with each repetition have to be exactly the same. Trailing or leading spaces make the strings different.
  • There must be only one output.
  • There is no code between repetitions.
  • Comments in your code are not allowed.
  • This is code-golf, so programs are scored in bytes, with less bytes being better.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I’m not too sure if “comments are not allowed” is an easy rule to enforce… everything else seems fine, +1 from me \$\endgroup\$
    – W D
    Oct 22, 2021 at 2:47
  • 1
    \$\begingroup\$ Maybe require the program to print a number alongside the Hello, World! to enforce that the code has to account for the repetitions? so ABC => 1. Hello, World!, ABCABC => 2. Hello, World! etc., and just make sure to specify that code can't read itself? This way, if you just comment out the rest of the code, it will fail. \$\endgroup\$ Oct 22, 2021 at 12:47
  • 1
    \$\begingroup\$ To avoid comment abuse and answers along the lines of print('Hello, World!');exit; you could require the program to be irreducible. However I suspect this challenge will still be really easy in most golfing languages. Here is an example (2 byte program repeated 3 times), and I don't even know Japt. \$\endgroup\$
    – Dingus
    Oct 24, 2021 at 3:26
0
\$\begingroup\$

In 1960 Andrey Kolmogorov conjectured that any algorithm to multiply two integers would require \$\Omega(n^2)\$* steps.

Within a week of presenting this conjecture it was proven false by graduate student Anatoly Karatsuba. Karatsuba's algorithm is an algorithm to multiply two numbers which takes in the worst case \$O(n^{\log_2 3})\$ time.

Your task will be to implement this algorithm. You will receive as input two binary strings. These can be lists of ints, arrays of bools etc.

You should then output the binary representation of their product in the same format.

It's hard to say in precise terms what it means to implement a particular algorithm. So here we will require only that your algorithm have asymptotic time complexity of \$O(n^{\log_2 3})\$ and \$\Omega(n^{\log_2 3})\$ where \$n\$ is the total number of bits in the input. Which is to say that it is neither better nor worse than Karatsuba's algorithm up to a constant factor.

This is so answers will be scored in bytes with lower bytes being the goal.


* In this challenge we will use \$f\in \Omega(g)\$ to mean that \$\displaystyle\limsup_{x\to \infty}\dfrac{f(x)}{g(x)}\$ does not converge to \$0\$. Also stated as \$f \in \Omega(g) \iff \exists k.\forall x.\exists x'.f(x')\geq k\cdot g(x')\$. This is the Hardy-Littlewood definition.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Python is known to use the exact algorithm under the hood, and it may be true for some other langs as well. Is it OK to use such built-in? Also, is it OK to use even faster multiplication and just slow it down with dummy recursion? \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 5:24
  • \$\begingroup\$ As bubbler mentioned, I would suggest remove the lower bound from the question, as the answer may implement a better algorithm (I don't know if it exist or not) and then slow it down by appending some dummy operations. \$\endgroup\$
    – tsh
    Oct 26, 2021 at 6:28
  • \$\begingroup\$ Also, you should explain what does \$n\$ means in the formula (length of input). As it is not very clear to readers. \$\endgroup\$
    – tsh
    Oct 26, 2021 at 6:29
  • \$\begingroup\$ @tsh is "where n is the total number of bits in the input." unclear? I'm not sure how I can explain it more directly than that. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 26, 2021 at 7:50
  • \$\begingroup\$ @Bubbler RE builtins: I don't ban builtins, I don't think it makes challenges better and only leads to confusion. It's up to the user whether they want to have fun. RE faster algos: The point of this challenge to implement this algorithm, not faster ones. The lower bound is there to encourage the algo. If you use a faster algorithm you are going to have to pay the cost to pad it out to the correct run time. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 26, 2021 at 8:33
  • 2
    \$\begingroup\$ I guess it could be better to further specify "the total number of bits of the two input numbers". Also probably move it closer to the first use of n. \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 8:52
  • \$\begingroup\$ @Bubbler Technically the \$n\$ in the initial statement is a little more complex. It's just a explainer so I don't think it's worth getting into all the details when in basically works like the default meaning of \$n\$. \$\endgroup\$
    – Wheat Wizard Mod
    Oct 26, 2021 at 9:07
0
\$\begingroup\$

Solve linear equations over the integers

All variables in this question are integer valued.

Input

4 integers w, x, y, z. They can be positive or negative and will be less than 1048576 in absolute value.

Output

The general solution to the equation.

\$ aw+bx+cy+dz = 0 \$.

The variables \$a, b, c, d\$ must all be integer values.

Output format

Your output should consist of three tuples each with four parts, one for each of the values a, b, c, d. Let me explain by example:

Input: -118, 989, 918, -512

Answer: b = 2 n_0 
        c = 9 n_0 + 256 n_1 + 81 a
        d = 20 n_0 + 459 n_1 + 145 a

Explanation: n_0 and n_1 are integers that you can set to anything you like. The solution says: a can also be set to any integer value, b must be twice whatever you set n_0 to. This means that a can be set to any integer, c can now be calculated in terms of three variables we have already set and so can d.

The format of your output should be 3 tuples (#,#,#,#), (#,#,#,#), (#,#,#,#). We can assume three free integer variables n0, n1 and n2 and so (a,b,c,d) = (#,#,#,#)n0 + (#,#,#,#)n1 + (#,#,#,#)n2. In the example above the output would therefore be:

Output: (0, 2, 9, 20), (0, 0, 256, 459), (1, 0, 81, 145)

Examples

Example one:

 Input: -6, 3, 7, 8

 Answer:  c = 2a + 3b + 8n
          d = -a - 3b - 7n 
          n is any integer

Output: (1, 0, 2, -1), (0, 1, 3, -3), (0, 0, 8, -7)

Example two:

Input: -116, 60, 897, 578

Answer: c = 578 n + 158 a + 576 b
        d = -897 n - 245 a - 894 b 
        n is any integer

Output: (1, 0, 158, -245), (0, 1, 576, -894), (0, 0, 578, -897)

Example three:

Input: 159, -736, -845, -96

Output: (1, 0, 27, -236), (0, 1, 64, -571), (0, 0, 96, -845)

Discussion

To understand this challenge further it is worth looking at this possible general solution which does not work [(z, 0, 0, -w), (0, z, 0, -x), (0, 0, z, -y)]. The problem with this is that there are solutions to the problem instances above which are not the sum of any integer multiples of those tuples. For example: take input -6, 3, 7, 8 from Example 1. The proposed solution would give the tuples:

(8, 0, 0, 6), (0, 8, 0, -3), (0, 0, 8, -7)

Why doesn't this work?

There is a solution for this instance with a = 1, b = 1, c = 13, d = -11 because -6+3+7*13-11*8 = 0. However there are no integers n_0, n_1, n_2 to make n_0 * (8, 0, 0, 6) + n_1 * (0, 8, 0, -3) + n_2 * (0, 0, 8, -7) = (1, 1, 13, -11) .

\$\endgroup\$
17
  • \$\begingroup\$ I expect the most common form of outputs would be (a,b,c,d) = (#,#,#,#)x + (#,#,#,#)y + (#,#,#,#)z, where #s are some integer constants and x,y,z are free variables. In this case, may I simply output the three vectors of length 4? \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 2:35
  • \$\begingroup\$ @Bubbler. The inputs are labelled w,x,y,z. I assume your x,y,z are not those? \$\endgroup\$
    – user7467
    Oct 26, 2021 at 3:32
  • \$\begingroup\$ I mean, (a,b,c,d) = (#,#,#,#)n0 + (#,#,#,#)n1 + (#,#,#,#)n2 if it reads better. Or in four separate equations: a = #n0 + #n1 + #n2; b = #n0 + #n1 + #n2; .... \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 3:34
  • \$\begingroup\$ @Bubbler what worries me slightly about that formulation is that it might force the coefficients to be really large. You seem to get much smaller coefficients if you express the variables in terms of previous ones and some free variables. \$\endgroup\$
    – user7467
    Oct 26, 2021 at 3:37
  • \$\begingroup\$ No, the coefficient size is irrelevant. Your example output in my format is a = 0*n_0 + 0*n_1 + 1*n_2; b = 2*n_0 + 0*n_1 + 0*n_2; c = 9*n_0 + 256*n_1 + 81*n_2; d = 20*n_0 + 459*n_1 + 145*n_2, or (a,b,c,d) = (0,2,9,20)n_0 + (0,0,256,459)n_1 + (1,0,81,145)n_2 in short. I'm only asking about the output format here. Is outputting [[0,2,9,20], [0,0,256,459], [1,0,81,145]] OK? \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 3:39
  • \$\begingroup\$ Let me think if you would ever have to express d in terms of c which in turn is expressed in terms of b. \$\endgroup\$
    – user7467
    Oct 26, 2021 at 3:44
  • \$\begingroup\$ Such situation can always be simplified to my form using substitution followed by expansion. \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 3:47
  • \$\begingroup\$ Yes. That’s where my concern about coefficient size comes in I believe. \$\endgroup\$
    – user7467
    Oct 26, 2021 at 3:49
  • \$\begingroup\$ Why are you concerning about the coefficient size in the first place? Isn't it plain code golf and we're allowed to output any solution that solves the problem I assume? \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 3:52
  • \$\begingroup\$ Maybe I shouldn’t worry about it. You can solve the problem so that you get ugly answers with huge coefficients (which is what sympy does). I thought it would be good to avoid that. \$\endgroup\$
    – user7467
    Oct 26, 2021 at 4:11
  • \$\begingroup\$ Thanks for your understanding. But still you didn't answer my original question about the output format. \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 4:15
  • \$\begingroup\$ If you have to scale your byte count by a factor which is how much larger (in absolute value) your largest coefficient is than the examples is that then code-challenge? \$\endgroup\$
    – user7467
    Oct 26, 2021 at 4:16
  • \$\begingroup\$ I really like your output format. I am just trying to work if it causes problems which I want to avoid. An alternative is to have 3 coefficients for a, 4 for b, 5 for c and 6 for d. That would enable you to express each one in terms of both the free variables and the other variables. \$\endgroup\$
    – user7467
    Oct 26, 2021 at 4:17
  • \$\begingroup\$ No, mixing code length with some other metric doesn't work (believe me, I tried it once and failed). Just go pure code-challenge (must run in reasonable amount of time, smallest coefficient wins) or pure code-golf (no time limit, output anything valid). For the former, you also need to prepare a good amount of hidden test cases (test-battery), otherwise you can't avoid hardcoded solutions. \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 4:23
  • \$\begingroup\$ The point is that "fully general format" as in your examples is way too tedious to actually output in non-Mathematica languages, so I'm suggesting a structured output which tries to simplify that. And all possible outputs can be expressed in the format I'm suggesting. If you decided for code-golf, you should absolutely stop worrying about the coefficient size. Please. \$\endgroup\$
    – Bubbler
    Oct 26, 2021 at 4:41
0
\$\begingroup\$

Is someone eavesdropping? (WIP)

Alice and Bob, who are quantum physicists, are being watched by Eve, a quantum FBI agent. Eve has quantum tunneled underneath Bob's house and is tapping all his quantum channels. Luckily, Alice and Bob are using the BB84 protocol to exchange quantum keys to encode their quantum messages. Your job is to write a program/function to help Alice and Bob determine if Eve is evesdropping.

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

Posted here

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

posted here

\$\endgroup\$
2
  • \$\begingroup\$ Will input word contains duplicate characters? What is expected output for top, [to, two, too], equipment, [queue, queen, quine]? \$\endgroup\$
    – tsh
    Oct 26, 2021 at 6:24
  • \$\begingroup\$ Updated examples. \$\endgroup\$
    – Seggan
    Oct 26, 2021 at 15:01
0
\$\begingroup\$

Implement every dirname (1p)

Implement the dirname utility from scratch. It can be either a program or a fucntion. Assume input string satisfies these constraints:

The dirname utility, however, has two kinds of implementations. This is because some POSIX systems treat //foo/bar differently from /foo/bar. So in this challenge, you must output every possible outputs, in any order. They can be duplicated.

Here is the algorithm to implement the utility, provided string to be input:

  1. If string is //, skip steps 2 to 5.
  2. If string consists entirely of <slash> characters, string shall be set to a single <slash> character. In this case, skip steps 3 to 8.
  3. If there are any trailing <slash> characters in string, they shall be removed.
  4. If there are no <slash> characters remaining in string, string shall be set to a single <period> character. In this case, skip steps 5 to 8.
  5. If there are any trailing non- <slash> characters in string, they shall be removed.
  6. If the remaining string is //, it is implementation-defined whether steps 7 and 8 are skipped or processed.
  7. If there are any trailing <slash> characters in string, they shall be removed.
  8. If the remaining string is empty, string shall be set to a single <slash> character.

The final string is the output.

Standard I/O rules apply. Standard Loopholes apply. No builtins or libraries that does exactly same functionality. Shortest code wins.

Examples

Some examples are taken from POSIX explaination of basename().

* means an empty string. 1st column is input and 2nd and 3rd are possible outputs.

usr               .
usr/              .
*                 .
..                .
../               .
/                 /
//                /          //
///               /
/usr/             /
//usr/            /          //
///usr/           /
/usr/lib          /usr
//usr//lib//      //usr
/home//dwc//test  /home//dwc

Meta

  • ?
\$\endgroup\$
0
\$\begingroup\$

Write a Stack Exchange compliant brainfuck explainer

\$\endgroup\$
6
  • \$\begingroup\$ @Adám But i prefer using 4 spaces \$\endgroup\$
    – Fmbalbuena
    Nov 14, 2021 at 22:40
  • \$\begingroup\$ I'm not sure what you mean by stating your preferences. Either it is allowed, or not. \$\endgroup\$
    – Adám
    Nov 14, 2021 at 22:41
  • 1
    \$\begingroup\$ ~ is ascii 126 \$\endgroup\$
    – tsh
    Nov 15, 2021 at 5:10
  • \$\begingroup\$ I would suggest avoid characters [] in description so they are ensured to be comment. \$\endgroup\$
    – tsh
    Nov 15, 2021 at 5:12
  • \$\begingroup\$ @tsh Oh, that's interesting, then the code remains runnable, even when fully explained. \$\endgroup\$
    – Adám
    Nov 15, 2021 at 7:32
  • 2
    \$\begingroup\$ I still strongly recommend giving the explanation strings as an argument, or even giving both explanation strings and symbols as arguments; that'd make the solution into a general code explainer. \$\endgroup\$
    – Adám
    Nov 15, 2021 at 8:10
0
\$\begingroup\$

Escape the maze

Introduction

Here is a random maze:

#####
#M.#E
#.##.
#.##.
#....
#####

Here M is the starting point and E is the endpoint. # is a maze wall and . is a path.

Now we can get out of this maze by following the sequence sssdddwww. (s is dow, d is right, w is up, a is left.)

Your challenge

Given a maze, output the shortest possible route to the endpoint. (E) You may assume the maze is solvable.

Test cases

#####
#M.#E
#.##.
#.##.
#....
#####

outputs

#####
#..#E
#M##.
#.##.
#....
#####

#####
#..#E
#.##.
#M##.
#....
#####

#####
#..#E
#.##.
#.##.
#M...
#####

#####
#..#E
#.##.
#.##.
#.M..
#####

#####
#..#E
#.##.
#.##.
#..M.
#####

#####
#..#E
#.##.
#.##.
#...M
#####

#####
#..#E
#.##.
#.##M
#....
#####

#####
#..#E
#.##M
#.##.
#....
#####

#####
#..#M
#.##.
#.##.
#....
#####

(Notice the newlines between the steps.)

Scoring

This is , so shortest code wins.


Todo

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Meta code golf. add tag maze :p \$\endgroup\$
    – Fmbalbuena
    Nov 18, 2021 at 20:21
  • \$\begingroup\$ @Fmbalbuena Done. \$\endgroup\$ Nov 18, 2021 at 20:22
  • \$\begingroup\$ Dupe of Find the shortest path from point A to point B. That challenge has itself been closed as a dupe of Textual maze solver, a decision I don't necessarily agree with, but better to reopen the existing challenge than create a new one. \$\endgroup\$
    – Dingus
    Nov 18, 2021 at 22:31
0
\$\begingroup\$

Solve the halting problem for Minyrinth

Introduction

Minyrinth is the stripped-down version of Labyrinth. It has the same routing semantics as Labyrinth but only four non-wall commands, and only one register (that can hold unbounded signed integers) instead of two stacks. The register is initialized to zero.

Commands

  • " is a no-op path.
  • @ halts the program.
  • ) increments the register.
  • ( decrements the register.

You may assume that the input only contains the four command characters plus spaces (non-path) and newlines (used for 2D layout).

Execution semantics

Copied directly from the README, with some parts edited for Minyrinth:

The source code consists of single-character instructions and is interpreted as a 2D grid. The instruction pointer starts at the first non-whitespace character in the file (in reading order) going right.

Labyrinth is interpreted in a simple loop. At each step, the command under the instruction pointer is executed, then the new movement direction is determined, and then the instruction pointer moves one cell in that direction. The edges of the grid are not connected.

The instruction pointer will generally follow "corridors" of instructions. Junctions can be used for non-trivial control flow. How the new movement direction is determined depends on the number of available steps (i.e. number of direct neighbours with known commands):

  • 4 neighbours: The top of the main stack is examined. If it's 0, keep moving straight ahead. If it's negative, turn left. If it's positive, turn right.

  • 3 neighbours: Do the same as for four neighbours, but if you hit the wall, reverse the direction. Hence, a T-junction hit from the side differentiates between 0 and non-zero. A T-junction hit from the bottom on the other hand sends negative/positive to the left/right whereas a 0 value reverses the direction.

  • 2 neighbours: The first rule here is, don't turn around. So if you came from one of the two directions, continue in the other direction. If this is not the case, but one of the two directions is straight ahead, follow that one (this can happen, for instance, at the start of the program in a corner).

  • 1 neighbour: Go towards the only available direction. Usually, this means you have hit a dead end and turn around on the spot (executing the command you turn around on only once).

  • 0 neighbours: Remain where you are without changing your direction. This can occur at the very start of the program.

Challenge

Solve the halting problem for Minyrinth. Unlike Labyrinth which is Turing-complete, Minyrinth simulates a specific case of a pushdown automaton whose halting problem is decidable.

For output, you can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Some hints can be found in CS Stack Exchange: Decidability of halting problem for DPDAs with \$\epsilon\$-transitions?, Counter Machine (Halting Problem)

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

Plan my factory

"Factory games", such as Factorio, Mindustry, and Satisfactory are my favourite genre of video games, and the way I play them involve a lot of ratio calculations to make sure the factory is running as efficiently as possible.

Given a list of recipe specifications, and a desired production rate of an end product, output the necessary input rates of raw materials, where "raw material" is any ingredient that does not have a provided recipe.

For example:

Recipes:

[
    {
        name: "Iron Plate",
        time: 3.2,
        quantity: 1,
        input: [{
            name: "Iron Ore",
            quantity: 1
        }]
    },
    {
        name: "Copper Plate",
        time: 3.2,
        quantity: 1,
        input: [{
            name: "Copper Ore",
            quantity: 1
        }]
    },
    {
        name: "Iron Gear",
        time: 0.5,
        quantity: 1,
        input: [{
            name: "Iron Plate",
            quantity: 2
        }]
    },
    {
        name: "Automation Science Pack",
        time: 5,
        quantity: 1,
        input: [
            {
                name: "Iron Gear",
                quantity: 1
            },
            {
                name: "Copper Plate",
                quantity: 1
            }
        ]
    },
]

Desired production rate:

{
    name: "Automation Science Pack",
    rate: 60
}

Expected output:

[
    {
        name: "Iron Ore",
        rate: 120
    },
    {
        name: "Copper Ore",
        rate: 60
    }
]

Both input and output may be any standard IO format that represents item names as strings and quantities/rates as integers.

Testcases

TBA

Sandbox

Is this a chameleon challenge?

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

Golf a Friedman's tree sequence for 3 colors

Friedman proved that given a sequence of 3-labelled rooted trees with following conditions, TREE sequence, must be finite and defined maximum length of such sequence as TREE(3).

  • \$i\$th tree, \$T_i\$, should have no more than \$i\$ vertices. (index is 1-based)
  • No tree \$T_i\$ can be homeomorphically embeddable into any of the following tree \$T_j\$ if \$i < j\$.
    • A tree \$A\$ is said to be homeomorphically embeddable to tree \$B\$ if and only if there exists a function \$f\$ from vertices of \$A\$ to vertices of \$B\$ which satisfies following conditions:
      1. \$f\$ preserves label. That is, \$v\$ and \$f(v)\$ has same label.
      2. If \$u\$ is ancestor of \$v\$, then \$f(u)\$ is ancestor of \$f(v)\$.
      3. If \$u_1\$ and \$u_2\$ are children of \$v\$, then the path from \$f(u_1)\$ to \$f(u_2)\$ contains \$f(v)\$.
    • There is a guide with examples in this youtube video.

It is well known that TREE(3) is far larger than \$2^{64}\$.

Challenge

Find a TREE sequence with length of \$2^{64}\$ or longer. Your task is to implement a program or a function or a subroutine that takes one 64-bit integer \$i\$ and outputs a tree \$T_i\$ of your TREE sequence.

Rules

  • Standard loopholes apply.
  • Standard I/O rules apply.
  • Shortest code wins.
  • Output can be any format as long as it describes a 3-labelled tree.
  • Describe how your outputs form valid TREE sequence.

Example of valid sequence, length 16

1 - {}              # 1 vertex tree with label {}. Note that any tree after this cannot contain node with label {}.
2 - [[]]            # 2 vertex tree with label both []. Any tree after this cannot contain two ancestor-child node with both label [].
3 - [(())]
4 - ([][])          # Root with label (), 2 children with label [].
5 - ([]((())))
6 - ([](()))
7 - [()]
8 - []
9 - ((((((((()))))))))
10 - (((((((())))))))
11 - ((((((()))))))
12 - (((((())))))
13 - ((((()))))
14 - (((())))
15 - ((()))
16 - (())

Meta

This is my first challenge. Suggestions?

I'm sure that normal computers will have serious difficulty to execute code for this problem, but also I don't want answers to just brute force TREE sequence and print ith term. How can I balance the question?

\$\endgroup\$
1
  • \$\begingroup\$ You definitely need some examples of the rules. Also, "homeomorphically embeddable" is not a term the average codegolfer is familiar with. \$\endgroup\$
    – Maya
    Nov 16, 2021 at 22:21
0
\$\begingroup\$

OEIS A049190

your task is to print all numbers of this sequence.

is separated by newline, is separated by space or separated by comma.

the first few numbers are:

1, 3, 5, 59, 245, 2491, 235253, 127756731, 330567489269, 258479716298484155, 36823182192123209878050549, 25576412117054296344209353299113896379, 10994511204169842163496446583221775727830456269734123253

How to get numbers of this sequence:

this is look and say but in binary and convert to decimal

Meta

  • How to clarify this?
\$\endgroup\$
0
\$\begingroup\$

Convert codepoint to UTF-1

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

Infinite ordinals from a well-ordering

\$\endgroup\$
3
  • \$\begingroup\$ Are the score categories essentially arbitrary? If so, it's not clear to me whether this is a good idea: it seems like these constraints provide the only motivation for choosing a well-ordering different from the 'default' (1, 2, 3, ...). Poor constraint choices could derail the challenge (i.e. make it too trivial or too hard). On the subject of scoring, looking at the bytes category for example, do you mean that if the default ordering is chosen, the code must be exactly 1 byte? \$\endgroup\$
    – Dingus
    Nov 12, 2021 at 0:48
  • \$\begingroup\$ Also, there's a typo under the second example: 2 < 101 is true. \$\endgroup\$
    – Dingus
    Nov 12, 2021 at 0:48
  • \$\begingroup\$ @Dingus I tried to clarify the scoring part. So if you choose \$\omega\cdot 2\$ you just try to golf an implementation of it. In this case someone has (hypothetically) managed to do it in one byte. As for the difficulty of the ordinals, the first two are one-liners in most languages, \$\omega^\omega\$ can be implemented with a while loop and \$\epsilon_0\$ with a tree. The score categories are not totally arbitrary. \$epsilon_0\$ is an important ordinal, and the smaller ones follow a natural pattern. Another option is to have just one ordinal, making this a normal golf and not a challenge. \$\endgroup\$
    – AnttiP
    Nov 12, 2021 at 7:41
0
\$\begingroup\$

Baloney Sandwich KOTH

Tags: [king-of-the-hill], [python]

Introduction

In this King Of The Hill Challenge, your bots will be playing Baloney Sandwich.

How Baloney Sandwich is played

  1. First, the entire deck is dealt equally to all players (EVERY BOT PLAYS; if there is more than 26 bots, it will be 2 decks mixed together).
  2. Then, the player with the ace of spades goes first.
  3. They play all of their aces
    • However! They could opt to "cheat" and instead play cards that are not aces, or mix and match aces with other cards.
  4. Every other player has their call_bs (bs = Baloney Sandwich) method called after this play, in turn until a player returns True; if a player returns True then the cards played are "revealed".
    • Every player has their bs_call_outcome method to "reveal" the cards
    • If no player returns True but the player was lying, the pb method is called (pb = Peanut Butter)
  5. Play continues with twos, threes, etc.; after kings, start over at aces

Creating A Player

Your player should be in this format:

class ExamplePlayer(AbstractBSPlayer):
    def __init__(self, hand: list[int]):
        super().__init__(hand)
        # Any necessary initialization goes here

    def call_bs(self, player_name: str, card_rank: int, number_of_cards: int) -> bool:
        """
        player_name is the name of the bot who just played
        The number of cards they played is number_of_cards
        The claimed rank is card_rank (1 is Ace; 11-13 are face cards)
        """
        # Magic decision maker
        return False # never calls "Baloney Sandwich"
        # return True would always call "Baloney Sandwich"
    
    def bs_call_outcome(self, player_name: str, caller_name: str, card_rank: int, cards: list[int], cheated: bool):
        """
        player_name is the name of the bot who just played
        caller_name is the name of the bot who called "Baloney Sandwich"
        The claimed rank is card_rank
        The cards they played is cards
        cheated is True if the player cheated
        """
        pass  # Couldn't care less
    
    def pb(self, player_name: str, card_rank: int, number_of_cards: int):
        """
        player_name is the name of the bot who just played
        The number of cards they played is number_of_cards
        The claimed rank is card_rank (1 is Ace; 11-13 are face cards)
        """
        pass # Couldn't care less

    def play_cards(self, card_rank: int) -> list[int]:
        """
        The rank you will claim to play is card_rank
        """
        # Magic decision maker
        return self.hand[0] # Always plays the first thing in hand

A player has access to the following instance variables:

  • self.store: A dictionary that is empty by default. The only instance variable allowed to be written to.
  • self.hand: A list of ints, each representing a card (1 is Ace, 11-13 are face cards)

Testing Your Player

The controller can be found at https://github.com/sethpeace/bs-koth. I apologize in advance that it is janky beyond comprehension.

Rules

Runtime Disqualifications

  • You must play at least one card every turn
  • You can't play cards you dont have in your hand
  • You can't take longer than one second to return from a function

Pre-runtime Disqualifications

  • No reading or writing to controller, runtime, or other submissions (bots can't read them; you can if you feel like it)
  • Only write to self.store instance variable
    • Other variables inside function scope are of course OK
  • Don't design a bot to defend or support specific bots
  • Bots can't use the same strategy as another bot
  • Standard loopholes apply
\$\endgroup\$
4
  • \$\begingroup\$ This seems too similar to codegolf.stackexchange.com/questions/48473/thats-bs-card-game \$\endgroup\$ Nov 27, 2021 at 16:45
  • \$\begingroup\$ @RedwolfPrograms you are correct; thank you \$\endgroup\$
    – Seth
    Nov 27, 2021 at 16:46
  • \$\begingroup\$ It's cool to see some more KotHs being written though! If you have any ideas for ones that you're not sure are dupes, feel free to bring them up in chat to save the effort of having to write out a whole spec first. \$\endgroup\$ Nov 27, 2021 at 16:48
  • \$\begingroup\$ @RedwolfPrograms alright thanks again :) \$\endgroup\$
    – Seth
    Nov 27, 2021 at 16:49
0
\$\begingroup\$

Implement xorshift128+

I don't have time to finish writing this draft at the moment.

Might also consider something like xoroshiro if it's more interesting to implement, but since xorshift128+ is so common it seems like a clearer choice.

(Possible idea: Given initial seed, determine number of iterations it'll take to get a certain random number with xorshift128+. It's not a CSPRNG, so there might be something more interesting than brute force.)

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

Radiate a prime checker into a sum program

Write a program or function that takes a number n and returns/print truthy if it is prime, and falsy otherwise. Additionally, if you remove 1 character of the source code, the program must now take a list of one or more numbers and return/print the sum. This must work for at least one character, and your score is however many characters that this does /not/ work for. Lowest score wins.

meta:

let me know if i need to clarify anything etc also: would it make sense to allow the programs to be the other way around (i.e. a sum checker where removing 1 character makes it a prime checker instead)? Just in case it could lead to a more interesting golf

\$\endgroup\$
2
  • \$\begingroup\$ It says "remove or change 1 character". By change, do you mean simply changing an arbitrary character to another arbitrary character, e.g. abc -> axc? If so, a lot of golfing languages will likely be able to make a trivial 0-score program where they simply change a 1-byte prime checker to a 1-byte sum command. That might not be a bad thing, per se, but it's something to keep in mind. \$\endgroup\$ Dec 8, 2021 at 21:16
  • \$\begingroup\$ @AaroneousMiller True, ill stick to just "remove". Wasn't sure of potential ramifications, thanks \$\endgroup\$ Dec 8, 2021 at 21:18
1
130 131
132
133 134
155

You must log in to answer this question.

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