# Sandbox for Proposed Challenges

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

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

Get the Sandbox Viewer to view the sandbox more easily!

# Eric Angelini's "1995" puzzle

• your post looks good, tags can be code-golf and sequence. Aug 6, 2021 at 14:19

# Prove NL=coNL

## Description

One of the achievements of complexity theory is showing that NL, the set of problems with solutions that can be verified in logarithmic space, is the same as coNL, the set of problems which can be verified to have no solution in logarithmic space (i.e. the set of problems whose complement is in NL). Your task is to implement a logarithmic-space verifier for the complement of the NL-complete problem "graph connectivity." More precisely, you will be given a directed graph $$\ G \$$ in adjacency matrix format, as well as two vertices $$\ s \$$ and $$\t\$$. Then, you may read some input from STDIN, which you should interpret as a "proof" $$\P\$$ that $$\s\$$ and $$\t\$$ are not connected (i.e. there is no path from $$\s\$$ to $$\t\$$). Finally, you must output whether $$\P\$$ is a valid proof of the fact that $$\s\$$ and $$\t\$$ are disconnected in $$\G\$$. All of this must happen using $$\O(\log n)\$$ extra space, where $$\n\$$ is the size of the adjacency matrix of $$\G\$$.

## Rules

• You will write a function that takes $$\(G, s, t)\$$ as inputs. Here, $$\G\$$ is a 2d $$\\ell\times\ell\$$ array, and the vertices are integers less than $$\\ell\$$. If $$\i\$$ and $$\j\$$ are less than $$\\ell\$$, then G[i][j] is truthy (you can decide exactly which truthy value) if there is an edge from $$\i\$$ to $$\j\$$, and falsy otherwise.
• You may not write to the array $$\G\$$, but it does not count towards your memory usage limit of $$\O(\log n)\$$. Be careful about making copies of the array, e.g. G.map(x => ...) in javascript would not be allowed, because it makes a copy of G, which uses too much extra memory.
• You can decide the format of the input from STDIN; there are no restrictions, other than the fact that for every input $$\(G, s, t)\$$, if $$\s\$$ and $$\t\$$ really are disconnected, there must be some proof that works, and conversely, if $$\s\$$ and $$\t\$$ are connected, no proof should be accepted.
• To be clear, when $$\s\$$ and $$\t\$$ really are disconnected, you can think of the proof as "maximally helpful," as though the input wants to prove that $$\s\$$ and $$\t\$$ are disconnected. However, if they are connected, the proof is adversarial. It is trying to trick you into reporting that the vertices are disconnected when they really aren't.
• Pretend that the native integer type of your language is unbounded. On the other hand, for the purposes of counting memory, an integer requires $$\O(\log |i|)\$$ memory, where $$\i\$$ is the value of the integer, because it requires that many bits to store.
• Rather than reading input from STDIN, you may receive the proof $$\P\$$ from user input in another way (e.g. repeated prompt calls in javascript). If your language supports it, you may choose to receive the proof in the form of an "input stream" I, as long as the following restrictions are on the "input stream": you should not be able to have random access to the proof's contents (i.e. access the $$\n\$$th byte without first getting the first $$\n-1\$$ bytes), and once you read a byte or some bytes, they should be "forgotten" unless you explicitly save it (and if you save it, it counts towards your $$\O(\log n)\$$ limit). Thus, for example, an array would not be acceptable, since it has random access, but it would be acceptable to accept a function I which returns the next byte of the "simulated input" every time you call it.
• If your program throws an error, you may count that as equivalent to returning false (i.e. $$\P\$$ is not a valid proof).
• Your program may exceed the space constraints when $$\P\$$ is an invalid proof, since as Anders Kaseorg pointed out, such a program can easily be converted into one which meets the space requirements always.
• Fewest bytes wins!

## Algorithm

An algorithm is given in section 7 of here (or is easily found on Google), but I will briefly describe it here for convenience (you do not have to use this algorithm/format):

We will ask the proof to build a sequence $$\r_0, r_1, \dots r_\ell\$$, where $$\\ell\$$ is the number of vertices, such that $$\r_i\$$ gives the number of vertices reacheable from $$\s\$$ in at most $$\i\$$ steps. Initialize $$\r_0 = 1\$$. Then, given $$\r_i\$$, the proof gives a claim of what $$\r_{i+1}\$$ should be. It proves this claim by claiming for each vertex $$\v\$$ whether $$\v\$$ is reachable in $$\i+1\$$ steps from $$\s\$$. In either case, for each vertex, the proof lists all $$\r_i\$$ vertices along with the paths used to get there. We verify that $$\r_i\$$ distinct vertices have been listed, and that at least one of them (or none of them) is connected to $$\v\$$, depending on what was claimed. Then, when we are proving $$\r_\ell\$$, we check that $$\t\$$ is not one of the vertices that can be reached from $$\s\$$.

## Test cases

Ideally, you would write a separate program that takes an input $$\(G, s, t)\$$ and outputs a possible proof $$\P\$$ if $$\s\$$ and $$\t\$$ are disconnected; this just makes testing easier, and it does not count towards your total bytes.

G s t --> are_disconnected
[[0,0,0,0],[1,0,1,0],[0,1,0,1],[0,1,1,0]] 0 3 --> true
[[0,1,1],[0,0,1],[1,1,0]] 1 0 --> false
[[0,0],[0,0]] 1 1 --> false
[[0,0,1,1],[0,0,1,0],[0,1,0,1],[0,0,1,0]] 1 0 --> true


Here, true should be interpreted as there is a valid proof that s and t are disconnected, whereas false is interpreted as there is no valid proof.

# Which in and out shuffles do I need?

If you watch Matt Parker's latest video as of time of writing, you'll know that for any given start and end position, there is a sequence of six in and out shuffles that will move the card at the start position $$\ p \$$ to the end position $$\ q \$$. One method is to use the 0-indexed formula from the video: Express $$\ 64p-q \$$ in the form $$\ 52t-s \$$ for the smallest positive integers $$\ t \$$ and $$\ s \$$, and then take the bitwise XOR of $$\ s \$$ and $$\ t \$$ as a 6-bit binary integer. For instance, to move the card from position $$\ 16 \$$ to position $$\ 22 \$$, we have $$\ 16 \times 64 - 22 = 1002 = 20 \times 52 - 38 \$$, so the result is the bitwise XOR of $$\ 20 \$$ and $$\ 38 \$$, which is $$\ 50_{10} \$$ or $$\ 110010_2 \$$, so you need two in-shuffles, two out-shuffles, an in-shuffle and an out-shuffle.

Given the start and end position, which you can take as 0- or 1-indexed as you prefer, output the list of shuffles required. You don't have to output a list of six shuffles, but you cannot use more than six shuffles, and if your output is variable length you need to indicate the length in some way. You can use any two distinct symbols to indicate the two types of shuffles, except you can't use 1 or I for out-shuffles or 0 or O for in-shuffles, as that would be too confusing.

This is , so the shortest program that breaks no standard loopholes wins!

• Related Aug 10, 2021 at 9:21
• I can think of a couple of languages with automatic wins (Lost, Cascade). it's probably impossible in a standard language, and merely very hard in most 2D langs
– Jo King Mod
Aug 25, 2021 at 10:07

# Fletcher's 16 bit checksum code-golf

## Intro

No story this time :( This is something that I needed for a program and I thought that it would make for a fun little challenge. I'd love to see some unusual languages here!

## Challenge

Implement Fletcher16. The algorithm is very straight forward, as seen here in pseudocode:

    int sum1, sum2, check1, check2;
char[] message;

sum1 = 0;
sum2 = 0;
for i from 1 to message_length do
sum1 = ( sum1 + message[i] ) modulo 255;
sum2 = ( sum2 + sum1       ) modulo 255;
end for


There are two accumulators sum1 and sum2. We iterate over the message and for every byte inside of it we add the byte to the first sum and then modulo the value by 255. We then add the value of the first accumulator to the second one and modulo that by 255 as well. This is Fletcher's algorithm.

    check1 = 255 - (( sum1 + sum2) modulo 255);
check2 = 255 - (( sum1 + check1 ) modulo 255);


We then calculate the checksum by "simulating" the algorithm for the two resulting values. After subtracting the numbers from 255, we get two values check1 and check2. They are then appended to the input in that order.

#### To recap:

• Run the first part to get a "raw" checksum
• Run the second part on that raw checksum to get the Fletcher16 checksum.
• Append the Fletch16 checksum to the input.

Evaluating the checksum

• Run the first part on the string with the appended Fletcher16 checksum
• If 0: String is valid, else String isn't valid.
• Note: If we run the second part as well, the result will be 0xFFFF

## Input

• Binary data in any format, length is at least 1.
• If needed, the length of the data.

## Output

• The Fletcher16 checksum check2 << 8 | check1, since this is what gives the algorithm its name.

## Rules

• This is , shortest answer wins
• No standard loopholes
• No builtins. I doubt that there's a language that has one for this, but if so that that's no fun.
• A submissiom may be a program/function/link/lambda/chain/etc.

## Test cases

abcde -> 0xC846
abcdef -> 0x2088
abcdefgh -> 0x06D2

abcde\x46\xC8 -> 0xFFFF
abcdef\x88\x20 -> 0xFFFF
abcdefgh\xD2\x06 -> 0xFFFF


You can find a reference implementation in C here

## Sandbox

• Are there any mistakes?
• Is something unclear? I'm really not sure about the wording of the input.
• Is the output restriction reasonable?
• The pseudocode is nice but I don't think it is an adequate substitution for an actual explanation of the algorithm.
– Wheat Wizard Mod
Aug 25, 2021 at 9:20
• Ok, I'll see what I can do. I'll also add a C reference implementation as soon as I get one working. Aug 25, 2021 at 9:24

# A phonetic letter

input
a letter of the alphabet, A-Z (upper or lower or a mix, I don't mind)

output
the phonetic (i.e spelled name of the )letter of the one passed in, along with the appropriate indefinite article a or an (again, in any case), and any amount of leading/trailing whitespace you like (i.e. it's fairly flexible)

full set of test cases (lowercase) - see This english.se Answer

input output
a an a
b a bee
c a cee
d a dee
e an e
f an eff (or "an ef")
g a gee
h an aitch
i an i (or "an eye")
j a jay
k a kay
l an el (or "an ell")
m an em
n an en
o an o (or "an oh")
p a pee
q a cue (or "a queue")
r an ar (or "an arrrrr") with an arbitrary number of rs
s an ess (or "an es")
t a tee
u a u (or "a you")
v a vee
w a double-u (or "a double-you", matching u above)
x an ex
y a wy (or "a wye")
z a zed (or "a zee", if you must)

, usual rules and exceptions, shortest bytes wins.

# Interpret Tarfish

Tarfish is a more tarpit-style version of ><> that I recently created.

It is two-dimensional, and has a stack (array of numbers that can be popped and pushed) and an instruction pointer, which has x and y coordinates and a direction. The instruction pointer starts at 0,0 (top left corner of program), moving right.

It has the following commands (some are not included because they would overcomplicate this challenge):

Command action
> Set the IP's direction to right
v Set the IP's direction to down
< Set the IP's direction to left
^ Set the IP's direction to up
. Pop stack and output as character
, Pop stack and output as number
x Push x position of the IP to stack
y Push y position of the IP to stack
+ Increment the top item of the stack
- Decrement the top item of the stack
= Pop the top two items from the stack, if they're equal, skip the next instruction.
{ Shift the stack right - put the ToS on the bottom of the stack
} Shift the stack left - put the bottom item on top of the stack
_ Pop the stack

Every tick, the command pointed to by the IP is executed (Unless it was skipped), and the instruction pointer moves one place in its direction.

Despite having so few commands, Tarfish is in theory Turing-Complete.

Your challenge is to interpret this language.

You do not have to implement wrapping - If the instruction poiinter leaves the grid, that is undefined behaviour. If the program tries to pop from an empty stack, that is undefined behaviour.

# Scoring

This is , shortest wins!

# Testcases

x++++++++++++++++++++++++++++++++:+:+++++++++++:++++++++++++++++++++++++++++:.+++++++++++++++:++++++++++++++:.+++++++:::..+++:.{{{.{.{{.}}.:++++++.:.--------..; => Hello, World!

x+, => 1

v > v > x,
> ^ > ^
=> 8

x:++++++++++v
>+}     :y-=v{,;
^+++++++++{-<
=> 100

• this may be closed as a subset of the existing ><> challenge. Aug 27, 2021 at 5:40
• @Razetime About half the commands are different, and this is much simpler. Aug 27, 2021 at 8:16
• What's the stack item's range? And what should happen if output as a character is chosen when the top of the stack isn't valid ascii (like x-.)? Sep 8, 2021 at 18:23
• Is the input guaranteed to be valid? And what's up with the colons in the example? Sep 8, 2021 at 18:26

# Counting and so on

• Re: scoring. What if somebody achieves infinity? I suppose it would become impossible if you required different languages for each step. But either require or don't allow at all — merely allowing different languages would create two different challenges in one post. Prescribing a specific shape for each digit would make things less subjective, but then it'll be hard to find something that works both for Jelly and Java :P "And also individual winners for each program too" I suppose you meant language, but anyway, that's not a distinction we usually mention. Aug 18, 2021 at 0:22
• the acceptance criteria for the numbers needs to be a lot more specific. Aug 19, 2021 at 3:59
• @Razetime What about being able to stretch bits of the number in any orthogonal direction? Or just that it has to be the same shape, but at different scales? Aug 20, 2021 at 23:50
• I'd define "X resembles Y" as "Y can be obtained from X by repeatedly removing one out of two consecutive identical rows or columns". Aug 25, 2021 at 0:58

# Implement the binary operators*

*of INTERCAL

## Intro

As we all know, there are 5 different binary operations. Two combine two values, the rest modifies the value given.

## Challenge

Your task will be to implement some if not all of the operators. They are defined as followed

• $ (mingle) Given two values, returns a value that consists of the bits of both values alternating. Right argument has the first bit. • ~ (select) Given two values, discard all bits of the right value that aren't 1 in the same place in the second value. Then, pack them to the right. If this explanation is too confusing, refer to this diagram. • &, V and ? (AND, OR and XOR) Given a value, AND/OR/XOR neighbouring the bits. ## Rules • I/O in any format that isn't a binary representation of the number(s). • Each answer can contain up to five submissions, each handling a different operator. You don't need to use one language for all programs. • A valid submission can be a program/function/link/lambda/chain/etc. • This is . Shortest answer for each operator wins. ## Test cases  44$     4 = 2224
2 \$     9 =   73

255 ~   341 =   15
4214 ~ 47818 =   96

&  1999 =  967
&    71 =    3

V     4 =    6
V   100 =  118

?    42 =   63
?   428 =  387


## Sandbox things

• I'm unsure about what to submit. Is this "up-to-five-programs-one-per-op" fine or should it be changed?
• Anything else unclear?
• Is this question different enough from Implement INTERCAL's Binary Operators ?
• "If this explanation is too confusing, refer to this diagram" I have no idea what's going on in this diagram Aug 19, 2021 at 19:05
• "As we all know, there are 5 different binary operations." It'd be good to specify that these are the operations of INTERCAL.
– user
Aug 19, 2021 at 19:06
• What does the "(lists of)" provision mean--in what case is a list received as input, and what do you do with it? I'd also note that restricting input formats is generally frowned upon here, but if you're doing it just to block INTERCAL programs from using their native numeric I/O do note that the input is already base 10 ;) Aug 19, 2021 at 21:49
• @Dudecoinheringaahing me neither but that's what the manpage shows :) I think that the procedere should be clear if you look at the first test case. Aug 20, 2021 at 6:25
• @user The footnote at the end is easy to overlook, I'll change it. Aug 20, 2021 at 6:26
• @UnrelatedString I agree, "(lists of)" should be removed to avoid confusion. Bad wording on my part. The intent of the second part was to block I/O from being binary strings. I shoud have worded it like that or drop that entirely Aug 20, 2021 at 6:28
• Impractical if your time zone offset from Greenwich is not a whole number multiple of an hour (see e.g. wolframalpha.com/input/?i=Australia+time+zones). Sep 5, 2021 at 22:20
• @JonathanFrech Not really. I frequently do LPs with people in Iran which is one of these places. If you live there you know it. But this is a simple code golf challenge and I don't think it serves it to complicate this with that sort of stuff.
– Wheat Wizard Mod
Sep 6, 2021 at 8:15
• Yes, I meant your proposed scheme would be impractical if one were to live there; just as a comment. As a string-manipulating golfing challenge I think it has some merit. Sep 7, 2021 at 1:24
• @jonathanFrech And I'm saying that while the scheme works best for integer offsets, from actual experience it is perfectly practical for people living in Iran which is UTC+3.5 or UTC+4.5 because if you live there you are aware of the offset and you can easily account for it.
– Wheat Wizard Mod
Sep 7, 2021 at 7:12
• No, the Jimmies are on the backs of more Jimmies, and it's Jimmies all the way dow. Sep 10, 2021 at 10:19
• What's the center of mass of -- or ----, and does it suffice to have a Jimmy's arm on one side of the central two? Sep 10, 2021 at 21:15
• @emanresuA In the first it is at 1 and in the second it's at 2. (relative to the start of the platform) In either case the arm cannot be a place a Jimmy is directly touching so it must be in between two.
– Wheat Wizard Mod
Sep 10, 2021 at 21:37

This question has been posted on the main site

• You might want to link to the question from here next time, although it doesn't really matter much.
– user
Sep 26, 2021 at 19:08
• Why not allow giving the first n numbers in the sequence?
Sep 19, 2021 at 13:29
• @Adám I don't really see any reason why one would want to do that.
– Wheat Wizard Mod
Sep 19, 2021 at 13:44

## Pythagoras' Golfing Grid

• Does it matter which solution is output? At the very least e and h can be any pair of factors for $f - T$, and you could swap dg with jk, etc. You say "integer" but your example only uses positive integers. Do you mean positive integers? If you do, there might be some T which do not have a solution. Sep 17, 2021 at 16:06

# Let's go for a rollercodester ride

• also considering using absolute change for scoring instead of curvature Sep 10, 2021 at 20:53
• Seems interesting, but I think a program that just switches between something like unary and denser languages like Jelly would be optimal and probably not too difficult. (Although it does seem like it could be a good challenge, making something like that is probably non trivial) Sep 10, 2021 at 20:53
• Would it be improved by only allowing each language once? I was also thinking a zip bomb type answer could dominate, but maybe that's not a bad thing. I could divide the score of each step by the sum of the code lengths that went into it, so it would be normalized and always less than 2 (theoretically 0,100,0 becomes +100,-100 becomes -200, from code lengths 0+100+0, leaving 200/100=2. That's the best I can think of). I like that because longer sequences would be the only way to reach higher score values. I guess the minimum sequence would need 3 languages to be scorable. Sep 11, 2021 at 2:09
• I'd assumed that each language was only allowed once anyway, so that's probably the best thing to do. A zip bomb type answer probably wouldn't win, because you need more than just a massive increase in size, you need to be able to control what the output is so you can make it do something useful. I think the number of languages should definitely be factored into the score though, since a single massive increase or decrease in size could be the easiest way to win at the moment. Sep 11, 2021 at 15:23

# Count occurences in Pascal's Triangle

• The challenge itself looks good to post. That said, I don't think there are any interesting strategies beyond generating up to the nth row (starting from the zeroth), flattening and counting Sep 18, 2021 at 3:03
• Also, it appears this sequence isn't on OEIS, and that the closest sequence is A006987 Sep 18, 2021 at 3:07
• @cairdcoinheringaahing oeis.org/A003016
– tsh
Sep 18, 2021 at 8:26

# Minimizing flights of stairs climbed

• I think the bonus is the most interesting part and should be the main challenge. For now it's just a simple formula. Also, why the room numbers, not just floor numbers (which are room//100)? Sep 23, 2021 at 12:03
• @pajonk I'll make the bonus be the main challenge then. They are room numbers to add a bit of extra challenge for converting into the floor number. Sep 23, 2021 at 16:05

# Multiplication for geometric algebra

• If you're looking for feedback here in the sandbox, I think it would be nice to remove the challenge from main site for now. Sep 23, 2021 at 11:56
• very interesting challenge. Sep 27, 2021 at 2:15
• I've edited this down to a stub now that it's been posted to save space Sep 30, 2021 at 1:02

# Newton Polynomial

A newton polynomial is a interpolation polynomial where the coefficients are found using the Newton's divided differences method. The relevant Wiki is here.

1. Given a set of inputs and outputs to find and display the polynomial that describes the series. The input can be as two lists or a dictionary like structure. e.g. $$[x_1:y_2,\;x_2:y_2,\;...\;, x_{n-1}:y_{n-1},\; x_n:y_n]$$
2. Given any real number, return the interpolated value.

## Examples

Presentation of the polynomial must be in a format that is recognisable.

As ever this is code golf: so shortest answer wins.

• A summary of the method would be welcome (in addition to the Wikipedia link). From a super quick skim I think there might be errors in the final example output: shouldn't $(n-1)(n-2)$ be $(n-1)(n-3)$, and similarly $(n-1)(n-2)(n-3)$ be $(n-1)(n-3)(n-7)$? Oct 12, 2021 at 4:49
• computers don't use real numbers. but still an interesting challenge. do you care what format the output polynomial is in? Oct 18, 2021 at 3:14
• @Dingus thanks, yes working on a summary of the method, wanting to keep it consice though. no every term is included so '(n-1)(n-2)(n-3) etc. Oct 18, 2021 at 20:44
• @donbright true, but I haven't had time to look into using complex numbers. I'm currently not interested in using them for this. Id want the polynomial to be readable, what did you have in mind? Oct 18, 2021 at 20:47
• no i mean, "given any real number" should be something like "given a 32 bit floating point number in your languages format". as far as the polynomial format i was wondering if you would accept it all expanded out to $a_nx^n + a_{n-1}x^{n-1}...a_0$ form, to the point where it can be represented as an array of numbers, the numbers in the array are coefficients and the position in the array is the exponent. thanks. Oct 19, 2021 at 2:09
• @donbright ah I see what you're saying, yes I will amend that then. I'm not sure I quite understand how you want to layout it out. Maybe expecting a particular format is too hard and I should just ask for an array of coefficient, were you thinking of expanding (n-1)(n-2)(n-3)... for example? Oct 19, 2021 at 23:06
• yes the final result should be a polynomial, would it be ok to return a string saying 23.4n^4 + 3920n^3 ... Oct 20, 2021 at 2:32

# Wave square

Given an integer $$\n\$$ with the constraints $$\0 < n \leq 9\$$, output the corresponding square, that for each row shifts the sequence from $$\1\to n\$$ by one, overflowing when needed.

## I/O

Input is an integer $$\n\$$, $$\ 0 < n \leq 9\$$. Output can be as a returned String, matrix, array or to STDOUT. You can write a full program or a function.

## Examples

5:

12345
23451
34512
45123
51234


2:

12
21


1:

1


9:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678


## meta

Thoughts on extending the challenge to allow for inputs bigger than 9, which would then just be taken mod 10?

• One idea - using letters for numbers greater than 9 (i.e a for 10, b for 11, etc.) would allow for inputs of up to 35 without disrupting the format. Oct 18, 2021 at 2:33
• Thanks! I don't know if that'd be enough to make it distinct from another challenge though (someone posted it was a dupe in the nineteenth byte)
– 0xff
Oct 18, 2021 at 8:22

Input two positive integers m, n; Output a grid looks like below:

┌──────────────┐
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
└──────────────┘


Here is an example for 5×4 grid.

Characters used in the grid is shown as this table:

Char Code Point
Space U+0020
─ U+2500
│ U+2502
┌ U+250C
┐ U+2510
└ U+2514
┘ U+2518
├ U+251C
┤ U+2524
┬ U+252C
┴ U+2534

You may alternative use a CJK space 　 (U+3000) instead of two ASCII spaces   (U+0020 U+0020). If you chose this option, you should use a single horizontal grid line ─ (U+2500) instead of two. You may verify this behavior in the code snippet at bottom.

You may output:

• a single string
• an array of characters, an array of integers (whose value is the code point of each character);
• an array of strings, as the single string split by new lines;
• or an array of array of characters, an array of array of integers;

Use ASCII Space:

<pre lang="en">┌──────────────┐
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
└──────────────┘</pre>

Use CJK Space:

<pre lang="zh">┌─────────┐
├─┬─┬─┬─┬─┤
│　│　│　│　│　│
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│　│　│　│　│　│
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│　│　│　│　│　│
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│　│　│　│　│　│
├─┴─┴─┴─┴─┤
└─────────┘</pre>

• Nov 4, 2021 at 2:13

# Calculate Smith normal form of an integer matrix

Given an $$\m \times n\$$ matrix of integers A, there exist a $$\m \times m\$$ matrix P, an $$\m \times n\$$ matrix D, and an $$\n \times n\$$ matrix Q such that:

• P and Q are unimodular matrices (i.e. matrices which are invertible and whose inverses are also integer matrices);
• D is diagonal;
• each diagonal entry $$\d_{ii}\$$ of D is nonnegative; and
• $$\d_{11} \mid d_{22} \mid \cdots \mid d_{nn} \$$.

Furthermore, the matrix D is unique in this representation.

One common way to calculate D is via an algorithm that looks like a combination of the Euclidean algorithm for calculating gcd and Gaussian elimination -- applying elementary row and column operations until the matrix is in the desired format for D. Another way to calculate D is to use the fact that for each i, $$\d_{11} d_{22} \cdots d_{ii}\$$ is equal to the gcd of all determinants of $$\i\times i\$$ submatrices (including non-contiguous submatrices) of A.

## The challenge

You are to write a function or program that calculates the Smith normal form of an input matrix. The output may either be in the form of the full matrix D, or in the form of a list of the diagonal entries of D. In an imperative programming language, it is also acceptable to write a function that takes a matrix by reference and mutates the matrix into its Smith normal form.

## Rules

• This is code-golf: shortest code wins.
• Standard loophole prohibitions apply.
• You do not need to worry about integer overflow, if that applies in your language.

## Examples

1 2 3       1 0 0
4 5 6  ->   0 3 0
7 8 9       0 0 0

6  10       1 0
10 15  ->   0 10

6 0  0        1 0  0
0 10 0   ->   0 30 0
0 0  15       0 0  30

2 2       2 0
2 -2  ->  0 4

2 2  4 6       2 0 0 0
2 -2 0 -2  ->  0 4 0 0


Note: Mathematica already has a built-in to calculate Smith normal form. As such, you can use this to play around with test cases: Try it online!

• Three new matrices are introduced at the top of the post and it isn't immediately obvious which one is the Smith normal form. Suggest stating that it's D after the first set of bullet points. Nov 9, 2021 at 23:34

# Climbing up slippery stairs code-golfmathcombinatorics

## Challenge

You're standing in front of a stairway with $$\n\$$ stairs in total. (If you label each staircase $$\1,\cdots,n\$$, the starting point counts as the 0th staircase.) You can climb up $$\1,2,\cdots,k\$$ stairs at a time. But some stairs are slippery; if you step on it, it will cause you to slip backwards until you stand on a non-slippery one (or the starting point). In how many ways can you get to the $$\n\$$th staircase with exactly $$\s\$$ steps?

Task: Given the list of staircases of length $$\n\$$ marked with either "slippery" or "non-slippery" (you can choose any two consistent values) and the values of $$\k\$$ and $$\s\$$, answer the above question.

The $$\n\$$th staircase is guaranteed to be non-slippery, and you cannot move further than the $$\n\$$th. This implies that reaching the destination before you spend $$\s\$$ steps doesn't count.

For example, if the stairway is [non-slippery, slippery, non-slippery] and $$\k=2\$$, two possible first steps (climbing one or two stairs) will result in the same position (the first staircase), but count as two distinct possible moves. And if you try to climb one stair as the second step, you will end up not moving at all, but it still counts as a step.

You may assume $$\1 \le k \le n\$$ and $$\s \ge 1\$$. Some inputs may have no way to reach the destination at all; in that case, your code should output the value of zero for any value of $$\s\$$.

## Example and test cases

N means non-slippery, and S means slippery. 1-1-3 notation means that you can reach the top in three steps, trying to advance 1, 1, and 3 stairs at once.

N = [N, S, N, N]
k = 3
s = 1: answer = 0 (no way to climb 4 stairs at once)
s = 2: answer = 3 (1-3, 2-3, 3-1)
s = 3: answer = 4 (1-1-3, 1-2-1, 2-1-3, 2-2-1)

N = [S, S, N, S, S, N]
k = 4
s = 1: answer = 0
s = 2: answer = 2 (3-3, 4-3)
s = 3: answer = 8 (1-3-3, 1-4-3, 2-3-3, 2-4-3, 3-1-3, 3-2-3, 4-1-3, 4-2-3)


More test cases coming soon.

# ⧵begin{alignat} ... ⧵end{alignat} code-golfstring

Note: The title intentionally uses &#10741; (reverse solidus operator) instead of plain backslash, because otherwise MathJax would happily translate the entire title to... uh... a MathJax error box.

## Background

\begin{alignat}{n} ... \end{alignat} is a lesser known LaTeX/MathJax block that allows aligning multiple parts of multi-line equations.

\begin{alignat}{5}
A&=&B&\\
& &B&=&C&\\
& & & &C&=&D&\\
& & & & & &D&=&E
\end{alignat}


\begin{alignat}{5} A&=&B\\ & &B&=&C&\\ & & & &C&=&D&\\ & & & & & &D&=&E \end{alignat}

\begin{alignat}{5}
x&=&-3&a&-&2&b\\
y&=& 2&a&+& &b
\end{alignat}


\begin{alignat}{5} x&=& 3&a&-&2&b\\ y&=&-2&a&+& &b \end{alignat}

## Challenge

Implement "Poor Man's ASCII-Only Alignat", which tries to replicate the behavior of MathJax but in plain text. The spec of PMAOA is as follows:

• Let's define a "word" to be each part of a line delimited by the & character. A word can be empty, and the parts before the first & and after the last & also count as words.
• Given a multi-line string input, identify the 1st, 2nd, 3rd, ... word of each line.
• Right-align the 1st words of all lines, right-align the 2nd words of all lines, ..., and concatenate the aligned blocks horizontally. Padding is done with minimal amount of space characters. Trailing whitespace at the end of each line is optional.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Coming soon.

• By saying align, is extra spaces allowed? For example, "a&b\ncd&e" -> "..a..b\n.cd..e"
– tsh
Nov 9, 2021 at 10:02
• @tsh No, the padding should be minimal. Nov 9, 2021 at 10:14

# What is the maximum value generated by interleaving?

INTERCAL has an interleave operator which does the following operation. Let left operand be asdf and right one qwer in binary, respectively. The operation produces a binary value aqswdefr.

INTERCAL internally treats data as unsigned integers, so the value of the eight-bit value represents 0 to 255 in decimal, inclusively.

If one operand has fewer bits than the other, the fewer one gets padded with zero before operation. So, asd interleaving with qwer is equal to 0asd interleaving with qwer, which is 0qawsedr: it represents 0 to 127 in decimal.

Also, INTERCAL has an extension that handles any bases. Let's assume if 3-base numbers are handled. If each operand has 1 and 3 digits respectively, the maximum value for each operand is represented as 2 and 222 in 3-base number, respectively. Interleaving them results in 020222, which is 188 in decimal.

Given an input of three unsigned integers, output the largest possible value generated by interleaving. The three integers are: number of digits for left operand, number of digits for right operand, and in what base those operands are described with.

## Restrictions

• Base shall be 2 or greater.
• Each operand has at least 1 digit.

## Rules

• In either function or a program.
• Standard I/O rules apply, as long as every input and output value is represented as same base or same representation.
• So varying output base is not allowed.
• If input is represented as a list-like format, any orders of arguments or input values are fine.
• No standard loopholes.
• Shortest code wins

TODO.

# meta

• Am I missing any appropriate tags yet?
• The I/O rules seem fine. I'd suggest changing the title to something like 'What is the maximum value generated by interleaving?' Also, 'output what the possibly largest value interleaving generates' -> 'output the largest possible value generated by interleaving'. Nov 12, 2021 at 4:14

# Constructing Solar Panels from Squares part 2 code-golfnumberoptimization

Thanks to all your generous contributions of code, my horde of minions can now precisely calculate how to construct solar panels of any size, but there's a problem.

The logistics department used these results to calculate how many square panels they would need for every size up to 1,000,000, which is way too many panels. As it turns out, larger panels are more expensive than cheaper ones, so I've decided we need to try to use the largest square panels we can wherever possible.

To make matters worse, my team of scientists tell me that we should avoid using multiple panels of the same size in our configuration, except for our tiny 1x1 panels, to make sure the panels don't fall apart.

## The Challenge

Given a positive integer n, output a list of square numbers that sums to n containing the largest squares possible such that no square number other than 1 appears multiple times.

A square number is any integer that is the result of multiplying an integer by itself. For example 16 is a square number because 4 x 4 = 16 This is A000290

For example: For n = 12, you could achieve the desired size with 4 panels of sizes [9, 1, 1, 1]. As 9 is the largest square possible in this configuration, this is the best answer. For n = 13, you can achieve the desired size with only 2 panels: [9, 4]

If n is a square number, the output should be [n].

## Input

A positive integer n representing the total desired surface area of the solar panels. Note that 0 is not positive.

## Output

A list of square numbers that sums to n containing the largest squares possible.

### Testcases

1 -> [1]
2 -> [1,1]
3 -> [1,1,1]
4 -> [4]
7 -> [4,1,1,1]
8 -> [4,4]
9 -> [9]
12 -> [9,1,1,1]
13 -> [9,4]
18 -> [16,1,1]
30 -> [25,4,1]
50 -> [49,1]
60 -> [49,9,1,1]
70 -> [64,4,1,1]
95 -> [81,9,4,1]
300 -> [289,9,1,1]
1246 -> [1225,16,4,1]
12460 -> [12321,121,16,1,1]
172593 -> [172225,361,4,1,1,1]


# Sandbox

I don't think this challenge is similar enough to part 1 to be considered a dupe, as while some answers from part 1 could be trivially modified to work for part 2, they would likely be out-golfed by better approaches.

That said I'm not sure how well-worded the output requirement is. a list of square numbers that sums to n containing the largest squares possible such that no square number other than 1 appears multiple times. feels poorly worded, but I'm not sure how I could word it better.

• The challenge is unclear. I think you copied part 1 but forgot to edit testcase and example of challenge
– okie
Nov 17, 2021 at 1:04
• such that no square number other than 1 appears multiple times - test cases don't agree. Nov 17, 2021 at 5:24
• I did generate new testcases when I wrote this, but I guess I messed up when putting them in. I'll re-run and update the testcases now Nov 17, 2021 at 22:15
• 8->4,4 having 2 4
– okie
Nov 18, 2021 at 0:43
• Am not sure if this question may be solved by modify the previous one trivially. But there would be many answer be very similar though. I'm not sure if it would be a duplicate to that one in such case.
– tsh
Nov 18, 2021 at 3:59
• @okie yeah, the problem is with the wording of the challenge, not the testcases. Not sure how best to word it... Nov 18, 2021 at 14:07
• So only the largest and 1 can appear multiple time?
– okie
Nov 18, 2021 at 23:27

# Implement Unix Timestamp to Daytime

Given an unsigned integer that represents a timestamp since 1970/01/01 00:00:00 (which is Unix epoch time), output one of these to represent the daytime in GMT timezone:

• An array that stores year, month, date, hour, minute, second.
• A string in format YYYYMMDDHHmmss.
• Or whatever similar, as long as it complies with standard i/o rules.

# Rules

• Implement the function or the full program from vanilla.
• So no built-ins nor libraries that has the fuctionality (see next section).
• Implement leap year, too; but don't leap second (although leap second is not supported).
• You just need to support up to 2038/01/19 (so input range shall be 0 to 2147483647 (inclusive)).
• Standard loopholes apply.
• Standard I/O rules apply.
• Input and output format should be consistent and not ambiguous.
• So, for example, if output is a string like 1970121000, it's unqualified, as it can be recognized as 1970/01/21 00:00:00, 1970/12/01 00:00:00, or 1970/01/02 10:00:00.
• Shortest code wins.

# Test cases

0
-> 1970/01/01 00:00:00
999999999
-> 2001/09/09 01:46:39
1145141919
-> 2006/04/15 22:58:39
1330500000
-> 2012/02/29 07:20:00
1633773293
-> 2021/10/09 09:54:53
2147483647
-> 2038/01/19 03:14:07


# Hint

Here are implementations:

# Meta

• I once posted here but it's closed.
• TODO. define what builtins are.
• The most problem is that that KSH answer has a function that directly converts to the objective string; should I prohibit it?
• Maybe I wanted to say no date objects allowed.
• Is what is so-called date object ambiguos?
• Unix Timestamp does not support leap seconds. So there is nothing to do to require someone implement leap second support for an Unix Timestamp.
– tsh
Oct 12, 2021 at 6:28
• Am I required to support year above 2038? As, you know, support only 1970~2038 would avoid some leap year issues for 2100 or 2200.
– tsh
Oct 12, 2021 at 6:31
• @tsh 1. Thank you for pointing out leap seconds. 2. I clarified to support until 2038.
– user100411
Oct 12, 2021 at 12:27

## Permutation of all the number which separated by ':' and ','

• Welcome to Code Golf and thanks for using the Sandbox! This is a great challenge, but as it stands it's a little unclear from the instructions what's being asked. For example it's clear from the example that 1-2,11,44:110-113` means output every permutation of 1,2,11,44 on the left column and 110,111,112,113 on the right column, but that's not explained in the instructions. Nov 12, 2021 at 20:52
• @Mayube Thanks for your comment, I've updated the instructions. Nov 12, 2021 at 22:02