Sandbox for Proposed Challenges

Question

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".

Answer 1

Implement a tag system simulator

Answer 2

Convert chessboards to algebraic notation

code-golfchess

---

Note: this is "simple" algebraic notation. It is only based off of my very limited knowledge. En passant, draw offers, disambiguation etc are not included and no bonuses will be given for handling those cases.

Algebraic notation is a compact, universal chess notation which provides an easy method of communication between two chess players. There are many apps that can convert a game of chess into algebraic notation given a list of boards; in this challenge you will write one as well.

Before I go over the challenge details, here's a quick crash course of algebraic notation.

Castling: there are two types of castling: kingside castling, the "short" way, and queenside castling, the "long" way. The short way is denoted as O-O (or 0-0) and the long way is O-O-O (or 0-0-0). When castling is performed, the king and rook both move at the same time, making castling the only occasion when two pieces can move at the same time.

K..R -> .RK. (kingside)
R...K -> ..KR. (queenside)

Other moves: the rest of the time, only a single piece moves. The move's anatomy in algebraic notation looks like this:

• the first character is the piece type, except when a pawn is moving. In the case of the pawn the piece type is not included. Otherwise, a knight is N, king is K, rook is R, queen is Q and bishop is B.
• next, we add x if the move is a capture. If not add nothing.
• Then, as a chessboard "coordinate", the position that piece is moving to. For example a4, b5 etc:

a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1

So a pawn moving to e4 would be e4, a bishop moving to h5 capturing a piece there would be Bxh5, a rook moving to g6 would be Rg6, etc. Note that pawn capturing at e4 would be xe4.

An additional character is placed at the end in certain circumstances: if the move makes the moving side "check" the opposing side then a + is added. For checkmates we add # instead. Note that this applies to castling as well (O-O+).

I will ignore en passant for this challenge.

Now, for the challenge itself...

You will take in a sequence of boards representing an entire game, and output its corresponding algebraic notation.

I don't really care how you take the boards. You could take in a FEN string:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

or a 8-line, 8-column board:

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

or a list of pieces:

['W', 'R', 'a8'], ...

or whatever else is reasonable. I will not accept taking in algebraic notation-like strings like Ra8 Kb7, for instance. You can take in a list of boards, double-newline separated, etc.

For each board you must output the algebraic notation of the move from the previous board to the current board by inferring the move from the difference between the boards, along with any necessary pluses and hashes in case the move is a check or checkmate. You must output the correct algebraic notation, but the end "list" can be of any format: a list, space-separated, newline-separated, etc. I don't really care as long as it is reasonable.

Example

Two boards have been given.

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

rnbqkbnr
pppppppp
........
........
........
.......N
PPPPPPPP
RNBQKB.R

Output:

Nh3

Another example:

....k...
........
........
K.......
....b...
....R...
........
.q......

....k...
........
........
K.......
....R...
........
........
.q......

Output:

Rxe4+

And finally, the Fool's mate with black castling once:

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

rnbqkbnr
pppppppp
........
........
........
.....P..
PPPPP.PP
RNBQKBNR

rnbqkbnr
pppp.ppp
....p...
........
........
.....P..
PPPPP.PP
RNBQKBNR

rnbqkbnr
pppp.ppp
....p...
........
......P.
.....P..
PPPPP..P
RNBQKBNR

rnbqkb.r
pppp.ppp
....p..n
........
......P.
.....P..
PPPPP..P
RNBQKBNR

rnbqkb.r
pppp.ppp
....p..n
........
......P.
P....P..
.PPPP..P
RNBQKBNR

rnbqk..r
pppp.ppp
...bp..n
........
......P.
P....P..
.PPPP..P
RNBQKBNR

rnbqk..r
pppp.ppp
...bp..n
........
......P.
PP...P..
..PPP..P
RNBQKBNR

rnbq.rk.
pppp.ppp
...bp..n
........
......P.
PP...P..
..PPP..P
RNBQKBNR

rnbq.rk.
pppp.ppp
...bp..n
........
......P.
PP...P..
R.PPP..P
.NBQKBNR

rnb..rk.
pppp.ppp
...bp..n
........
......Pq
PP...P..
R.PPP..P
.NBQKBNR

Output:

f3 e6 g4 Nh6 a3 Bd6 b3 O-O Ra2 Qh4#

This is code-golf, so the winner is the answer with the least bytes.

---

Meta: is this a duplicate? How could I improve the challenge further?

Answer 3

Make a number serious

I'm a big fan of silly challenges, but I'm afraid we're going to have to get serious. It's time to get rid of the lols.

Or rather, the 101s, which look quite a bit like lols.

Task:

Take an integer as input. You'll make this number serious by removing the 101s from the number's binary representation. Now, particularly good jokes sometimes elicit lolols or even l(ol)+s from numbers, so we must get rid of these too.

Answer 4

C character constants.

I'm not sure if we had something like this before.

Given a value n between 1 and output the shortest possible c type character constant.

Examples:
1 -> '\1'
7 -> '\7'
8 -> '\b'
9 -> '\t'
65 -> 'A'

The character constants can only contain ASCII characters from 32 - 127.

Answer 5

Fast Inverse Square Root //evil floating point bit level hacking

Introduction

The fast inverse square root algorithm is a function developed in C for Quake III. It was at the time the fastest way to compute the inverse square root of a function, which is needed for most vector operations.

The code as written in 1999, from the quake 3 source, is as follows:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Challenge

Given a floating-point number in any form you wish, calculate its inverse square root and return it as a float to at least 4 decimal places.

Example

Input:

3

Output:

0.5773502691

Judging

This is a challenge for creativity as well as code size.

For example, I would rate a 1:1 copy in c# about a 3/5, but a brainfuck copy 5/5 for the challenge and creativity.

Answer 6

Apply gravity to this matrix

Answer 7

A *character*-less quine

Similar to “What did we forget?”

---

Output

Your program must be a quine - that is, print its own source code with no input or unused input.

Although this is quine, you are allowed to read your own source code. Assume the file is named “q” and that no extension is needed. There is no bonus for not reading the source code.

If you remove all occurrences of a character that is in your program, it should print the character removed. It is allowed to then raise an error; however, there is no bonus for this either.

To the sandbox: do I need this? => Your program must have at least 3 different characters.

Lowest number of bytes wins (this is code-golf, after all)

Sanbdox things

• Anything I should change?
• This used to be “Numberless” (see edit history) - should I change it back?

code-golf source-layout radiation-hardening quine

Answer 8

Your Challenge

Find out if a function always returns its input.

Input/Output Information

Input is a math expression as a string with operators + - ( ) /.
The multiplication symbol is *, or x if you specify.

The input will always will only contain whitespace spaces, decimal points, numbers (0123456789), math symbols (+ - ( ) / and one of the following: * or x) and one lowercase letter that is the variable.

Whitespace in the input must be ignored.

Output is whether the function will always return its input.

The expression will never have a division by a polynomial with its degree >1.
Example: x*x*x/x*x <= this will never be input.

Example Input/Output

Input: n /3 + 2*n/3 + 175 - 175*(n+ 1-n)
Output: truthy
Explain: Simplifies to "n"

Input: f
Output: truthy
Explain: Any variable is allowed

Input: j*(j-3.1)/(j-   3.1)
Output: falsey
Explain: In normal math, this evaluates to j
However, when j is 3.1, it is undefined
Therefore, it doesn’t ALWAYS return its input
This is because when j is 3.1, the output is not 3.1

Input: 1j
Output: truthy
Explain: 1j = j which is the input

Input: n/2 + n/2
Output: truthy
Explain: Simplifies to 2n/2 = n which is the input

Scoring

This is code-golf, so lowest amount of bytes wins!

Sandbox Questions

I brought this back from a long time ago.

Any unaddressed problems?

code-golf math

Answer 9

Alternating Digit Divisibility

TODO: Could use a better title..

code-golfnumberarithmeticinteger

Challenge:

Given a list of at least two positive integers, output a pair of lists of digits. Both inner lists in the output are the digits which evenly divide each number in the alternating converted lists. The first converted list will be [sum(digits(n)), n, sum(digits(n)), ...], and the second will be [n, sum(digits(n)), n, ...].

Step-by-step example:

Input: [611,44,381]

Step 1: Convert it to the two alternating lists:

[[sum([6,1,1]),44,sum([3,8,1])],    →    [[8,44,12],
 [611,sum([4,4]),381]]                    [611,8,381]]

Step 2: Check for each number which digits evenly divides it:

[[[1,2,4,8],[1,2,4],[1,2,3,4,6]],
 [[1],[1,2,4],[1,3]]]

Step 3: Leave the digits present in each of the inner lists of lists, which is our output:

[[1,2,4],
 [1]]

Output: [[1,2,4],[1]]

Challenge rules:

• I/O is flexible. Input can be a list of strings, integers, 2D list of digits, etc. Output can be a list of lists of digits, a single flattened list of digits (i.e. [1,2,4,1] in the example above), two lists printed on separated lines, each digit printed separated, a string or single (big) integer (i.e. 1241), etc. etc.
• You're allowed to swap the order of the alternation if it's convenient in your language of choice (i.e. the example above would output [[1],[1,2,4]]/[1,1,2,4]/1124/etc. instead).
• 0 will never be in the output.

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Input:                      Output:

[611,044,381]               [[1,2,4]], [1]]
[200,32000,4000]            [[1,2], [1,5]]

TODO: More to come, including some larger ones

Answer 10

Encrypt this Message

Answer 11

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  

Answer 12

Drop down the numbers

Answer 13

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

Answer 14

Hearts KotH

king-of-the-hill

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)?

Answer 15

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.

Answer 16

fastest-code

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 fastest-code, 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?

Answer 17

Answer 18

Balanced Bracket Sequence

Answer 19

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 code-golf, so the shortest answer in bytes per language wins.

code-golf number prime pattern-matching

Answer 20

Best Rotation

code-challenge 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°\$.

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

Answer 21

code-golf

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 code-golf, 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?

Answer 22

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

Answer 23

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.

Answer 24

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 code-golf 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.}

Answer 25

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) .

Answer 26

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.

Answer 27

Posted here

Answer 28

posted here

Answer 29

Implement every dirname (1p)

code-golf string

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

• it contains portable filename character set only, and
• its length is up to 256 bytes, including trailing a NULL character (as in _POSIX_PATH_MAX from limits.h).

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

• ?

Answer 30

Write a Stack Exchange compliant brainfuck explainer