539
\$\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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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!

\$\endgroup\$
0

3549 Answers 3549

1
60 61
62
63 64
119
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Related \$\endgroup\$
    – pxeger
    Aug 10 at 9:21
1
\$\begingroup\$

Determine the length of a Puyo Puyo chain

Puyo Puyo is a Japanese tile-matching puzzle game currently developed by Sega. The gameplay seems simple but it is actually quite complex.

You have a 12x6 board which you can fill with various colors (typically red, green, blue, yellow, and purple) of Puyo (round slime-like creatures with eyes). Each turn, you control a pair of Puyo that you can manipulate and place on the board not unlike Tetris.

When a pair is placed, gravity is applied to the board. If there is an empty gap underneath one or more Puyo in a column, they fall to fill the gap.

When two Puyo of the same color are adjacent to each other, they link together. When 4 or more Puyo are linked, they pop (disappear). After a group of Puyo pops, if gravity causes another group to pop, then you have created a chain. The goal of Puyo Puyo is to place Puyo so that you create as long of a chain as possible to overwhelm your opponent with nuisance Puyo.

Nuisance Puyo are a special case - they are colorless (usually gray or transparent), but more importantly they do not link together. Instead, they pop when an adjacent colored Puyo pops.

Challenge

Given a Puyo Puyo board in any reasonable format (12 lines of 6 character strings, a 12x6 matrix of characters/numbers, 12 6-character strings in an array, etc.) output the chain length as a number. Standard loopholes apply.

This is code-golf, so shortest source code wins.

Bonus: In Puyo Puyo Tsuu, a hidden 13th row was added above the playfield to allow for longer chains. You will get a -5% score bonus if your program can optionally accept a 13th row.

Test cases

Note: Intermediate board states are shown to demonstrate the game mechanics; you are not required to output them.

Key: Red, Green, Blue, Yellow, Purple, Nuisance, . empty

Output: 4

...... ...... ...... ...... ......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
......>......>......>......>......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
..GBR. ...BR. ....R. ...... ......
..RGBR ...GBR ....BR .....R ......
..RGBR ...GBR ....BR .....R ......
.RRGBR ..GGBR ...BBR ....RR ......

Output: 4

...... ...... ...... ...... ......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
...... ...... ...... ...... ......
......>......>......>......>......
.G.... ...... ...... ...... ......
YG.... ...... ...... ...... ......
NGY... ..Y... ..Y... ...... ......
NGR... Y.R... ..R... ..Y... ......
YBR... YBR... ..R... ..R... ......
YYBR.. YYBR.. .BBR.. ..RR.. ......
BBRR.. BBRR.. BBRR.. ..RR.. ..Y...

Output: 0

......
......
......
......
......
......
......
......
.B....
BR....
BR....
BR....

Output: 19 (requires bonus; sorry, no intermediate states)

..YRYY
GBBYRG
RBYRYY
GBYRYG
RYRGBG
YRGBYG
RYRGBY
RYRGBY
RGGBGB
GBYRBB
RGBYRG
RGBYRG
RGBYRG

The Puyo Nexus chain simulator might be useful while debugging.

\$\endgroup\$
1
\$\begingroup\$

Reverse cadaddadadaddddaddddddr

The Lisp language has a family of functions car, cdr, cadr, etc for accessing arrays. For each one, an a defines taking the first item of an array, and a d defines taking the rest.

For example, running cadr on [[1,3,4],5,7] will return [3,4] as the a gets the first item ([1,3,4]) and the d removes the first item.

We've already had a challenge regarding running a cadaddadadaddddaddddddr on a list, but what about the reverse?

Your challenge is to, given a string of the type above (starting with a c, ending with a r, with only ad in the middle), and a single value, create an array such that running the string as a cadaddadadaddddaddddddr on the array returns said value.

For example, given the input cadar, 1 a possible output could be [[0,[1]]] since running cadar on that gives 1.

Scoring

This is , shortest wins!

Testcases

These are possible outputs, all that matters is that your program returns an array which works for the condition.

car, 3 => [3]
cdddar, 5 => [0,0,0,5]
cadadadadar, 4 => [[0,[0,[0,[0,[4]]]]]]
caaaaaaaaar, 2 => [[[[[[[[[[2]]]]]]]]]]

Let me know if any of these are wrong.

\$\endgroup\$
7
  • \$\begingroup\$ one "]" is missing at the end in the 3rd and 4th test, if i'm not mistaken \$\endgroup\$
    – Basto
    Aug 13 at 12:37
  • \$\begingroup\$ @Basto Ok, thanks! \$\endgroup\$
    – emanresu A
    Aug 13 at 22:05
  • \$\begingroup\$ "only ad in the middle" ~> "only a, d in the middle"? Else I would read it as matching /c(ad)*r/. \$\endgroup\$ Sep 5 at 22:35
  • \$\begingroup\$ @JonathanFrech This is abandoned, feel free to take it up if you want. \$\endgroup\$
    – emanresu A
    Sep 5 at 22:43
  • \$\begingroup\$ Ok. I would have liked to solve it. Thanks for the offer to take it up but I respectfully decline. \$\endgroup\$ Sep 5 at 22:44
  • \$\begingroup\$ @JonathanFrech I posted it, but I made several mistakes that no one realised until it was too late. \$\endgroup\$
    – emanresu A
    Sep 5 at 22:46
  • \$\begingroup\$ But with some polish it would be a good question, I think. \$\endgroup\$ Sep 5 at 22:47
1
\$\begingroup\$
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Jo King Mod
    Aug 25 at 10:07
1
\$\begingroup\$

Fletcher's 16 bit checksum

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:

Adding the checksum

  • 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?
\$\endgroup\$
2
  • \$\begingroup\$ The pseudocode is nice but I don't think it is an adequate substitution for an actual explanation of the algorithm. \$\endgroup\$
    – Grain Ghost Mod
    Aug 25 at 9:20
  • \$\begingroup\$ Ok, I'll see what I can do. I'll also add a C reference implementation as soon as I get one working. \$\endgroup\$ Aug 25 at 9:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ this may be closed as a subset of the existing ><> challenge. \$\endgroup\$
    – Razetime
    Aug 27 at 5:40
  • \$\begingroup\$ @Razetime About half the commands are different, and this is much simpler. \$\endgroup\$
    – emanresu A
    Aug 27 at 8:16
  • \$\begingroup\$ 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-.)? \$\endgroup\$
    – Aiden4
    Sep 8 at 18:23
  • \$\begingroup\$ Is the input guaranteed to be valid? And what's up with the colons in the example? \$\endgroup\$
    – Aiden4
    Sep 8 at 18:26
1
\$\begingroup\$

Counting and so on

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – NieDzejkob
    Aug 18 at 0:22
  • 3
    \$\begingroup\$ the acceptance criteria for the numbers needs to be a lot more specific. \$\endgroup\$
    – Razetime
    Aug 19 at 3:59
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – emanresu A
    Aug 20 at 23:50
  • 1
    \$\begingroup\$ 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". \$\endgroup\$
    – Bubbler
    Aug 25 at 0:58
1
\$\begingroup\$

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 ?
\$\endgroup\$
6
  • 2
    \$\begingroup\$ "If this explanation is too confusing, refer to this diagram" I have no idea what's going on in this diagram \$\endgroup\$ Aug 19 at 19:05
  • 1
    \$\begingroup\$ "As we all know, there are 5 different binary operations." It'd be good to specify that these are the operations of INTERCAL. \$\endgroup\$
    – rues
    Aug 19 at 19:06
  • \$\begingroup\$ 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 ;) \$\endgroup\$ Aug 19 at 21:49
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 20 at 6:25
  • \$\begingroup\$ @user The footnote at the end is easy to overlook, I'll change it. \$\endgroup\$ Aug 20 at 6:26
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ Aug 20 at 6:28
1
\$\begingroup\$
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Sep 5 at 22:20
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Grain Ghost Mod
    Sep 6 at 8:15
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 7 at 1:24
  • \$\begingroup\$ @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. \$\endgroup\$
    – Grain Ghost Mod
    Sep 7 at 7:12
1
\$\begingroup\$
\$\endgroup\$
1
\$\begingroup\$
\$\endgroup\$
3
  • \$\begingroup\$ No, the Jimmies are on the backs of more Jimmies, and it's Jimmies all the way dow. \$\endgroup\$
    – emanresu A
    Sep 10 at 10:19
  • \$\begingroup\$ 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? \$\endgroup\$
    – emanresu A
    Sep 10 at 21:15
  • \$\begingroup\$ @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. \$\endgroup\$
    – Grain Ghost Mod
    Sep 10 at 21:37
1
\$\begingroup\$

This question has been posted on the main site

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

Pythagoras' Golfing Grid

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 17 at 16:06
1
\$\begingroup\$

Let's go for a rollercodester ride

\$\endgroup\$
4
  • \$\begingroup\$ also considering using absolute change for scoring instead of curvature \$\endgroup\$
    – M Virts
    Sep 10 at 20:53
  • \$\begingroup\$ 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) \$\endgroup\$ Sep 10 at 20:53
  • \$\begingroup\$ 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. \$\endgroup\$
    – M Virts
    Sep 11 at 2:09
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 11 at 15:23
1
\$\begingroup\$

Count occurences in Pascal's Triangle

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$ Sep 18 at 3:03
  • \$\begingroup\$ Also, it appears this sequence isn't on OEIS, and that the closest sequence is A006987 \$\endgroup\$ Sep 18 at 3:07
  • \$\begingroup\$ @cairdcoinheringaahing oeis.org/A003016 \$\endgroup\$
    – tsh
    Sep 18 at 8:26
1
\$\begingroup\$

Minimizing flights of stairs climbed

\$\endgroup\$
2
  • \$\begingroup\$ 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)? \$\endgroup\$
    – pajonk
    Sep 23 at 12:03
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Yousername
    Sep 23 at 16:05
1
\$\begingroup\$

Multiplication for geometric algebra

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – pajonk
    Sep 23 at 11:56
  • \$\begingroup\$ very interesting challenge. \$\endgroup\$
    – don bright
    Sep 27 at 2:15
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ Sep 30 at 1:02
1
\$\begingroup\$

Recursive Stalin Sort


Main Post

\$\endgroup\$
1
\$\begingroup\$

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.

Your task has two parts:

  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

enter image description here

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

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

\$\endgroup\$
7
  • \$\begingroup\$ 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)\$? \$\endgroup\$
    – Dingus
    Oct 12 at 4:49
  • \$\begingroup\$ computers don't use real numbers. but still an interesting challenge. do you care what format the output polynomial is in? \$\endgroup\$
    – don bright
    Oct 18 at 3:14
  • \$\begingroup\$ @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. \$\endgroup\$
    – george
    Oct 18 at 20:44
  • \$\begingroup\$ @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? \$\endgroup\$
    – george
    Oct 18 at 20:47
  • \$\begingroup\$ 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. \$\endgroup\$
    – don bright
    Oct 19 at 2:09
  • \$\begingroup\$ @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? \$\endgroup\$
    – george
    Oct 19 at 23:06
  • \$\begingroup\$ yes the final result should be a polynomial, would it be ok to return a string saying 23.4n^4 + 3920n^3 ... \$\endgroup\$
    – don bright
    Oct 20 at 2:32
1
\$\begingroup\$

Follow the border

\$\endgroup\$
1
\$\begingroup\$

Wave square

Task

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?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Dingus
    Oct 18 at 2:33
  • \$\begingroup\$ 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) \$\endgroup\$
    – Jadefalke
    Oct 18 at 8:22
1
\$\begingroup\$

Largest turing incomplete subset of ASCII

We have challenges about trying to find a short, turing complete number of characters in a language. In this challenge, you'll do the opposite, trying to find the largest subset of characters which is not turing complete.

Rules:

  • Like , competition is purely within a language, not between different ones
  • Languages with SBCSs or other custom code pages may use those instead of ASCII
    • SBCS submissions will not compete against ASCII submissions in the same language
  • In this challenge, "ASCII" is not short for "printable ASCII". All of 0x00 to 0x7f is allowed
    • So, the highest score possible would be 127 (for non-SBCS submissions), if there was a single character which is always needed for a TC program
  • The language you use must be turing complete (and must be TC with full ASCII or its SBCS, whichever you choose)

Possible rule:

You must be able to write a valid program using only (and all of) the chosen subset of ASCII/the SBCS. It doesn't need to do anything useful, it just can't error.

This prevents padding the subset with characters that would never be allowed in a valid program in your language, or not including just one critical character needed in every program. However, strings and comments could be a problem.

\$\endgroup\$
7
  • \$\begingroup\$ If a language is using SBCS, that would allow for a score higher than 94, wouldn't it? \$\endgroup\$ Oct 20 at 15:03
  • \$\begingroup\$ @AaroneousMiller It would, yes (this is fine since it's a competition within the language) \$\endgroup\$ Oct 20 at 15:10
  • \$\begingroup\$ An empty program is valid in some languages. \$\endgroup\$
    – xnor
    Oct 20 at 18:09
  • \$\begingroup\$ @xnor Ah, I meant using all of the characters in the chosen subset. Will fix. \$\endgroup\$ Oct 20 at 18:18
  • 2
    \$\begingroup\$ Maybe just allow all 256 bytes 0x00 to 0xff so it's a fair playing field? \$\endgroup\$
    – emanresu A
    Oct 20 at 19:00
  • \$\begingroup\$ I don't think the "possible rule" is needed. The equivalent challenge is to find a small set of chars/bytes such that some of them are absolutely needed for the lang to be TC, and take the set complement. IMO the first part is totally fair across languages (assuming full byte range), and the second part only depends on how you define the full set. So for maximum fairness I'd suggest "every char/byte is on the table, even the ones that cannot appear in any valid program". \$\endgroup\$
    – Bubbler
    Oct 20 at 23:30
  • 1
    \$\begingroup\$ @Bubbler To be fair, it's not meant to be fair to all languages. It'll be like code golf where scoring is per language. But I guess I agree the possible rule probably isn't needed. \$\endgroup\$ Oct 20 at 23:45
1
\$\begingroup\$

Find all paths

\$\endgroup\$
6
  • \$\begingroup\$ More test cases would be needed. Is this oeis.org/A121788? \$\endgroup\$
    – Luis Mendo
    Jun 27 at 15:24
  • \$\begingroup\$ I dont think this is that problem in the link \$\endgroup\$
    – PyGamer0
    Jun 27 at 15:34
  • \$\begingroup\$ Anyway, please include more test cases \$\endgroup\$
    – Luis Mendo
    Jun 27 at 16:24
  • \$\begingroup\$ Is this oeis.org/A001184? \$\endgroup\$
    – tsh
    Jun 28 at 8:22
  • \$\begingroup\$ yes it is @tsh updated! \$\endgroup\$
    – PyGamer0
    Jun 28 at 8:37
  • \$\begingroup\$ === Looks good! === \$\endgroup\$
    – emanresu A
    Jun 28 at 8:43
1
\$\begingroup\$

What's the valency?

The challenge.

Given an element, for simplicity lets assume the element is entered as a string of the symbol of the element (any consistent casing of your choice) and the only elements are the first 20 elements of the periodic table.

You have to output the valency of the element. The valency of the element has to be with the sign and as per the below cases.

All cases

h  ->  1
he ->  0
li ->  1
be ->  2
b  ->  3
c  ->  4
n  -> -3
o  -> -2
f  -> -1
ne ->  0
na ->  1
mg ->  2
al ->  3
si ->  4
p  -> -3
s  -> -2
cl -> -1
ar ->  0
k  ->  1
ca ->  2

This is code-golf so the shortest answer in bytes wins.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Since we require that challenges be self contained, you would need to provide the valency for each of the elements that you want to include. \$\endgroup\$ Sep 20 at 18:25
  • \$\begingroup\$ Adding to FryAmTheEggman's comment, several elements have more than one valency. For each element you need either to specify which valency/valencies to output or allow answers to choose. \$\endgroup\$
    – Dingus
    Oct 19 at 4:49
  • \$\begingroup\$ @FryAmTheEggman edited the question. It now includes all 20 cases. \$\endgroup\$
    – PyGamer0
    Oct 19 at 6:11
  • \$\begingroup\$ This looks much better! Now I would recommend allowing the inputs to be in whatever consistent casing (upper, lower, title) the answerer prefers. Otherwise, I think it is good to go. \$\endgroup\$ Oct 19 at 14:08
  • \$\begingroup\$ @FryAmTheEggman edited. \$\endgroup\$
    – PyGamer0
    Oct 19 at 15:18
  • \$\begingroup\$ @PyGamer0 The wording "(any case)" isn't clear enough – it could also mean that the program has to be able to handle any case. \$\endgroup\$
    – m90
    Oct 19 at 15:21
  • 1
    \$\begingroup\$ Perhaps "any consistent casing of your choice"? \$\endgroup\$ Oct 19 at 15:38
  • 6
    \$\begingroup\$ How many more "build an optimal lookup table" questions do we need? \$\endgroup\$
    – pxeger
    Oct 19 at 16:18
1
\$\begingroup\$

Loading Circle Animation

Challenge

Write a full program that takes no input (or has an unused input) that displays exactly the following ASCII animation infinitely (or for as long as possible) in STDOUT.

Frame 1:

 #
#
#  #
 ##

Frame 2:

 ##
#
#
 ##

Frame 3:

 ##
#  #
#
 #

Frame 4:

 ##
#  #
#  #

(Note that the line at the end is empty.)

Frame 5:

 ##
#  #
   #
  #

Frame 6:

 ##
   #
   #
 ##

Frame 7:

  #
   #
#  #
 ##

Frame 8:


#  #
#  #
 ##

(Note that the line at the start is empty.)

Rules

  • The program takes no input (or has an unused input).
  • The animation can start at any frame, but must animate in sequential order.
  • The animation can be in reverse order.
  • The program has to run infinitely (or for as long as possible).
  • The animation has to be displayed at the same position on screen for every frame.
  • Trailing/leading whitespace is okay, as long as the animation looks right.
  • # can be replaced with a different character that is 1 byte.
  • This is code-golf, so the shortest answer in bytes wins.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think it would be simpler if a program was just required to output eight frames, then stop. The infinite looping is unnecessary. (I think it's fine how it is) \$\endgroup\$ Oct 28 at 1:45
  • \$\begingroup\$ For example, someone submit a progrom like this: while True: print(".#\n#\n#..#\n.##);clearScreen();print(.##\n#\n#\n.##);clearScreen()... The program try to print a frame, and then clear the screen immediately. It in theory output each frame one by one. But user would be hard to distinguish each frames. Also, if you try to take a screenshot, most time you will got an empty screen (suppose clearScreen would be much slower than print). Is this still a valid answer? \$\endgroup\$
    – tsh
    Nov 4 at 8:03
  • \$\begingroup\$ @tsh Yes, as long as the user can tell what the animation is. \$\endgroup\$
    – Yousername
    Nov 12 at 22:59
1
\$\begingroup\$

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>

\$\endgroup\$
1
1
\$\begingroup\$

⧵begin{alignat} ... ⧵end{alignat}

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.

\$\endgroup\$
2
  • \$\begingroup\$ By saying align, is extra spaces allowed? For example, `"a&b\ncd&e" -> "..a..b\n.cd..e" \$\endgroup\$
    – tsh
    Nov 9 at 10:02
  • \$\begingroup\$ @tsh No, the padding should be minimal. \$\endgroup\$
    – Bubbler
    Nov 9 at 10:14
1
60 61
62
63 64
119

You must log in to answer this question.

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