# 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 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!

# Implement a feature-rich calculator

We have a few many calculator challenges on this site, but none seem to require a complex one with many different features.

This challenge is about emulating my old Casio calculator, except with no digit limit. Features are:

• basic (start with a single operation, then input the next operation)
• all clear (AC) which starts a new "calculation". No need for C.
• errors for dividing by zero (otherwise there should be no error)
• memory: M to set the memory to current number, MC as an inline expression representing the memory, and M- to get rid of the memory.

This should operate either on STDIN (prompt for commands each time) or in a function (taking in either a list of commands or a newline-separated string with commands).

## Spec

Your solution should be able to handle floating-point numbers, hence float division should be used regardless of context.

When first run, the calculator will be "ON". It is guaranteed that input syntax is valid.

The chain of commands begins with a number operation number-like structure, where number can be replaced with MC to represent a reference to the memory. For instance 5 * 5 or 6/MC. Whitespace can be ignored or forbidden, that can be your call, but whatever it is you may assume syntax is valid.

Then, if your submission is a full program, it should output the result of that operation, or if a function, append that to the end of a list.

Subsequent operations can either be:

• M this sets the memory to current number. Memory can only ever hold a single number at a time.
• AC. Clears the current calculation and resets the number. Memory, however, will still be accessible.
• M-. (M minus) This clears the memory, and calls to MC will never be given when there is nothing in the memory.
• operation number where operation is + - * or /, and number is a number which can be replaced with MC.
• Off. The command Off stops the program, and it is reasonable to assume that no commands will be passed afterwards.
• - (minus sign) negates current number. Outputs the new number.

Division by zero should trigger an error and restart the calculation. AC, M, MC and M- should output nothing. Memory can be overwritten.

Note that operation number operation number will never be given, and that all operations will be performed on non-negative numbers. (we have the negate operator for negative numbers)

Also note that this challenge is less about parsing / processing a string input and more about responding to different kinds of input.

## Example

As a full program, but note that a function will have to take in an array of commands. There is a >  before each command, but in your version, it is not required.

> 5*5
25
> *4
100
> /200
0.5
> /0
ERROR (or some form of ERROR)
> 15*6
90
> M
> +MC
180
> AC
> 7-MC
-83
> -
83
> M-
> +5
88
> Off


Meta: is it a duplicate? any clarifications needed?

• Maybe use the [interactive] tag, and make it clearer that this is less parsing/processing a given string input and more responding to inputs as given Jun 18 '21 at 14:16
• The "error" should not terminate the program, right? Would it be OK to, on error, print anything that is distinguishable from numeric output (say "X", "Inf", or "NaN"), or print something different across errors (e.g. "Inf" for 1/0, "NaN" for 0/0)? Jun 25 '21 at 1:40
• @Bubbler Yes, that's fine. You can also output Inf for 1/0 and NaN for 0/0 like you mentioned.
– user100690
Jun 25 '21 at 5:10

# KotH - Floating Point Prisoners Dilemma

• Looks intriguing! How does each round work though? So one is coop, zero is defect, but what do the floats in between do? Look forward to hearing! Jun 11 '21 at 2:33
• It uses an equation from the wonderful fellows at math.stackexchange.com to determine what the in-between states should do. I'm bad at explaining, so the equations in my (probably horrible) code are in the play function of the controller class in controller.py Jun 11 '21 at 2:46
• @4D4850 Would you link to the question if you have it still? Jun 11 '21 at 17:46
• It was actually closed, but here it is: math.stackexchange.com/questions/4152360/… Jun 11 '21 at 18:27
• Understood it now, good challenge! Jun 12 '21 at 8:39
• Should I post the question? Jun 17 '21 at 19:08
• Posted on Main: codegolf.stackexchange.com/questions/229926/… Jun 17 '21 at 22:14
• I've edited this down to a stub now that it's been posted to save space Jun 18 '21 at 14:33

# Outputting Blum Integers

• I'd suggest using standard sequence rules (answers can choose $n$th, first $n$ or infinite output). I've also edited the challenge a bit, feel free to revert any changes you dislike Jun 18 '21 at 14:29
• @cairdcoinheringaahing thanks for the suggestion, i'll apply it
– user100752
Jun 19 '21 at 9:14

# What's missing

• This is probably too easy Mar 22 '21 at 12:14
• Some languages may have built-in Bag / MultiSet / Counter collection type. And a simple - operate or something similar may get correct result. Will you allow answers use such type of values as input / output?
– tsh
Mar 23 '21 at 1:41
• @tsh I guess? It doesn't really make a difference for the languages that have creative solutions. It's code-golf, which means answers generally don't get accepted. Mar 23 '21 at 8:22
• ruby does have array-array, but it wont work for arrays with similar items missing. I feel this is easy, but it can work as a codegolf challenge
– user100752
Jun 22 '21 at 9:24
• @EliteDaMyth Honestly, I'm really surprised this doesn't already exist. Jun 22 '21 at 9:33

## Do these points approximately make up a regular n-sided polygon?

The input is a set of integer coordinates. Take them in whatever form you want, e.g. a list of tuples or just a plain list. The question is: can you draw an n-sided regular polygon with vertices at the specified coordinates? n being the amount of coordinates provided. Answer truthy if yes, falsy if no.

The level of precision is in integers. That means you will have to round both the x and y values of the ideal polygons to the nearest whole values. Here's an example diagram:

The triangle has points at approximately (5,5), (4,9), (1,6). You can draw a regular triangle to fit these coordinates, even if the actual points of the triangle are not at quite the same coordinates.

The same goes for the pentagon. The coordinate set (3,1), (7,1), (8,5), (5,8), (2,5) makes up a regular pentagon-ish, accurate to whole values.

Any set of coordinates can make up an infinite amount of approximate n-gons. You answer truthy if there's at least one such n-gon. One way of thinking about it is to consider a unit square around each of the points, then determine if you can stretch a regular polygon such that every point falls within the squares.

Further ground rules:

• The coordinates will always be positive.
• They do not have to be in any particular order.
• Coordinate values will never exceed 1000.
• There will not be more than 10 coordinates.

### Examples:

(5,5), (4,9), (1,6) -> true
(3,1), (7,1), (8,5), (5,8), (2,5) -> true
(1,1), (1,1), (2,1) -> true
(1,1), (2,1), (130,1) -> false

(42,42) -> true


(according to Wikipedia, a monogon is still a polygon, meaning any input is valid.)

(0,1), (5,10) -> true


(any two points make up a regular bigon so this should work for any coordinates)

(1,3), (1,3), (1,3), (1,3) -> true


(any set identical coordinates will always match an n-gon that's tiny enough to have all of its coordinates rounded to the same integer).

• I just found this question. It seems to be the same question but it is closed with no answers, and I think my requirements are clearer. Jun 16 '21 at 12:12
• I don't think the current explanation addresses the question "How are we supposed to tell if the polygon is regular without knowing its exact coordinates?" I feel like there's some way to gradually constrain polylines, but not quite sure. Also, I think "One way of thinking about it is to consider a circle of half a unit around one of the points" should be "... consider a unit square around one of the points" instead. What is the expected output of (0, 0), (0, 2), (1, 1), (2, 0) (which is borderline square with (-0.5, -0.5), (-0.5, 1.5), (1.5, 1.5), (1.5, -0.5))? Jun 23 '21 at 0:15
• @Bubbler Thanks for the comment. You are correct about the circle being a square! My mistake. And yes, that would be truthy. Jun 23 '21 at 8:59
• @Bubbler regarding "how are we supposed to tell if polygon is regular" that's asking for an example answer strategy, not part of the question, is it? The question is whether there is any regular polygon where each point falls in those unit squares. That's almost an optimisation problem. It's not impossible, all the required information is there. But I could try to come up with one approach - but answers should not feel obligated to copy that approach because for this problem there would be many solution strategies. Jun 23 '21 at 9:03

Alteration of a challenge that was considered too close to an older quasi-duplicate.

# ISO Computus

from a signed integer year number provided as sole input
the integer number of the calendar week of Easter Sunday as sole output
with as few variables and as few arithmetic operations as possible.

Easter Sunday is determined according to the Gregorian Computus (as used in the all Western Christian churches, including the Catholic Church, and some others), for which there are several equivalent algorithms available, see Computus, Gent, Stockton and ESTRALGS.TXT. There are 35 possible month-day dates, from 22 March to 25 April.

The week of the year is specified by international standard ISO 8601-1: All weeks start on Monday; there are no partial weeks; the first week of the year has 4 January (or the first Thursday) in it. For more information see the Mathematics of the ISO 8601 Calendar. There are just six possible results, weeks 12 through 17. W17 will hardly ever occur – it has never occurred since 1583 at least.

## Restrictions

• You may use all basic arithmetic operators, including addition, substraction, multiplication, division, integer division, modulo, rounding (with integer flooring and ceiling), exponentiation, logarithms.
• You may not use library functions that implement an algorithm for the Computus, like PHP's easter_date(), EasterSunday[year] from the Mathematica Calendar package or Easter from the R package timeDate.
• You may not use other predefined date functions, e.g. to find the day of the week or the week of the year.

## Ranking score

Your solution must be an algorithm implemented as an executable script in a programming language of your choice.

• Each numeric variable and constant, whether used by name or literal value, counts as 1 point.
• Each basic operation, as defined above, counts as 1 point.
• Each definition of a custom function or method counts as 5 points.
• Each call of a custom function or method counts as 1 point.
• Imports and similar initializations required by the programming language are ignored.
• Neither reading the input value and returning or printing the output value nor eventual variables for storing their value are counted.
• The answer with the fewest points wins.
• TBD…

Example:

function CFAQEaster(year) { // Calendar FAQ
// 5 points for Div() function
var G, C, H, I, J, L // 6 points for variables
G = year % 19        // 2: 1 point for modulo, 1 point for 19
C = Div(year,100)    // 2: 1 point for function call, 1 point for 100
H = (C - Div(C,4) - Div(8*C+13,25) + 19*G + 15) % 30
// 16: 8 points for operations, 2 points for function calls, 6 points for additional numeric values
I = H - Div(H,28)*(1 - Div(29,H+1)*Div(21-G,11))
// 13: 5 points for operations, 3 points for function calls, 5 points for additional numeric values
J = (year + Div(year,4) + I + 2 - C + Div(C,4)) % 7
// 6 points for operations, 2 points for function calls, 2 points for additional numeric values
L = I - J            // 1 point for substraction
EasterMonth = 3 + Div(L+40,44)
// 6: 2 points for addition, 1 point for function call, 3 points for additional numeric values
EasterDay = L + 28 - 31*Div(EasterMonth,4)
// 6: 3 points for operations, 1 point for function call, 2 points for additional numeric values
return {Y:year, M:EasterMonth, D:EasterDay}
// 63 points in total
}


## Contemporary example input: output

• 2001: 15
• 2002: 13
• 2003: 16
• 2004: 15
• 2005: 12
• 2006: 15
• 2007: 14
• 2008: 12
• 2009: 15
• 2010: 13
• 2011: 16
• 2012: 14
• 2013: 13
• 2014: 16
• 2015: 14
• 2016: 12
• 2017: 15
• 2018: 13
• 2019: 16
• 2020: 15
• 2021: 13

The return value must be correct for a complete cycle of input years, i.e. from 1 through 5700000, even though the original event that is celebrated did not occur before 30 (if ever at all) and the Gregorian Calendar was not used before late 1582, i.e. the proleptic Gregorian Calendar applies.

## Resources

• I believe this challenge is better done as alorithm-golfing rather than counting characters or bytes. However, I'm not sure at all how to award a score. The rules above are very much up to bikeshedding. Jul 1 '21 at 10:46
• The main problem with any kind of scoring like this is that many programming languages have very different set of built-in operations and features. How many points for using a mapping or reduction on an array? How many points for swapping two numbers on the stack? How many points for using the 1 command in Hexagony, which computes x>=0?x*10+1:x*10-1? A better way would be to fix the language and a very strict set of features available, like "use Python 3, only +-*/ operators on numbers are allowed". Jul 14 '21 at 7:28
• A few suggestions: perhaps add the date tag, and say something like Output "WEEKDAY" if there are 5 dates, all from Monday-Friday, "WEEKEND" if there are two dates: Saturday and Sunday, and "ALLDAYS" if the input contains seven days all from Monday-Sunday.
– user100690
Jun 28 '21 at 12:46

# Generate the shortest regex to match these but not those

• A possible short program just enumerates all the regexes. This might not be feasible, and you may not be able to score submissions at all... Jun 28 '21 at 17:34
• @Trebor I don't quite understand what you mean by this. Jun 28 '21 at 18:13
• If you just write a program and tests, one by one, all the regexes, and outputs the first one that works, this would be a valid program. But to give it a score, you would probably need days, if not years. Jun 29 '21 at 8:06

# Solve Fermat's Last Theorem with matrices

Fermat's Last Theorem states that there is no such triple of positive integers $$\(x, y, z)\$$ such that

$$x^n + y^n = z^n$$

for all integers $$\n > 2\$$. However, this conjecture does not hold for integer matrices:

\begin{align} & \left( \begin{matrix} 1 & 3 \\ 0 & 1 \end{matrix} \right)^3 + \left( \begin{matrix} -1 & 0 \\ 1 & -1 \end{matrix} \right)^3 \\ = & \left( \begin{matrix} 1 & 9 \\ 0 & 1 \end{matrix} \right) + \left( \begin{matrix} -1 & 0 \\ 3 & -1 \end{matrix} \right) \\ = & \left( \begin{matrix} 0 & 9 \\ 3 & 0 \end{matrix} \right) \\ = & \left( \begin{matrix} 0 & 3 \\ 1 & 0 \end{matrix} \right)^3 \\ \end{align}

You are to take two $$\k \times k\$$ integer matrices $$\A\$$ and $$\B\$$, and a positive integer $$\n \ge 2\$$, and output a $$\k \times k\$$ integer matrix $$\C\$$ such that

$$A^n + B^n = C^n$$

You may output any such $$\C\$$. You may also take $$\k\$$ as an input, and you may assume that $$\k \ge 2\$$

This is , so the shortest code in bytes wins

• Is it guaranteed that A, B, n are given so that such a C exists? Why not just make a challenge about taking the nth root of a given matrix (which is arguably the hardest part of the task)? Jul 14 '21 at 6:54

# I'm a lizard, cut here!

• I think you mean n≥2
– xnor
Jul 21 '21 at 5:05
• @xnor sure thanks Jul 21 '21 at 5:11

# How effective is compression?

Vyxal has a very simple format for compressed integers: a base-255-encoded string of characters wrapped in «.

With base 255, the number to be compressed needs to be 10000 or greater for the compression to have an advantage against ordinary numbers, as with 1 character, you can represent at most 3-digit numbers (up to 254), which ties with 1 + 2 (for the «) = 3 bytes; with 2 you can represent up to 65024 in 4 bytes, beating 5 for n ≥ 10000.

But what if it was another base?

If it were base 99, it would take 3 bytes, since you can only express up to 9800 with 2, which isn't any better than expressing the number. But with 3, you can reach 970299, which has 6 digits

Your challenge is to take a positive integer $$\b\$$ 11 or greater, and find the smallest number $$\n\$$ such that $$\log_b(10^n) + 2 < n\$$. You may output $$\10^n\$$ instead.

This is , shortest wins!

Testcases coming soon.

• Be sure to include the testcases for n=100 and n=1000. The correct answer is floor(1+2/(1-1/log10(n))), but the wrong answer ceil(2/(1-1/log10(n))) gives identical results for all other n. (The correct answer can be also wrong due to floating-point imprecision. Is this allowed?) Jul 29 '21 at 7:45
• @Bubbler Ok, will do. Shouldn't be wrong as it's taking a single logarithm. Jul 29 '21 at 7:56
• Straightforward Python fails because of 1/3, not single logarithm btw Jul 29 '21 at 8:13

# KOTH: Prisoners Dilemma Single Elimination king-of-the-hillpython

I was playing around with this and found some interesting strategies. This is sufficiently different from this post because you are playing different bots each game, instead of repeatedly playing the same ones.

## How the game works

The basic game is the prisoners dilemma. A bot and it's opponent may choose to defect (1) or cooperate (0). Defecting gives you 1 point, and if your opponent cooperates you gain 2 points. If you defect and your opponent cooperates this adds up to a total of 3 points.

In every round, you play against every opponent (including yourself) in random order. The bot does not know who it is playing against. This process repeats 100 times to form a single round, after each round the player with the lowest score is eliminated, and the scores of the rest of the players is divided are 2. Round continue until either every remaining player always defects, or always cooperates, at which point the best player is decided by their score. (After this points scores converge quite fast, so to avoid noise deciding the winner I measure at the point with the most pronounced differences)

## Input

Your bot does not know who it is playing against, not even if it is playing against itself. However, the bot does know what its opponent decided on its last 3 games, and for each of those 3 games what the opponent's opponent decided. Basically, the input will look like this:

[
[0, # Three games ago, your opponent decided not to defect
[1, # Your opponent's opponent from three games ago defected three games before that
0,
0],
[1,  # Your opponent defected in their second to last game
[1, # Your opponent's opponent from two games ago defected the 3 games before that
1,
1]
[0, [0, 0, 0]
]


(With 1 and 0 replaced with True and False)

Any of these players might be the same. Your opponent's opponent could actually be your current opponent if they played against themselves last, or it could be yourself if you played against eachother twice in a row. (Unlikely, but possible at the end of a round)

Your bot does not receive what it's own last decisions are but is free to keep that info in it's own state.

# Output

You can output any value, if bool(output) == True your bot defects, otherwise your bot cooperates.

## Example Bots

Nice bot never defects:

class NiceBot:
def get_choice(self, last_3_games):
return 0 # Any False-y value will work, for example False or an empty string


Mean bot always defects:

class MeanBot:
def get_choice(self, last_3_games):
return 1


Majority bot chooses whatever it's opponent chose the most often:

class MajorityBot:
def get_choice(self, last_3_games):
choices = [i[0] for i in last_3_games]
return max(set(choices), key=choices.count)


Bandwagon bot will avoid decisions by chosing what the bots opponents chose the most.

class BandwagonBot:
def get_choice(self, last_3_games):
total_true = sum(
i[1].count(True)
for i in last_3_games
)



Bandwagon bot will only play if the number of bots is even.

## Other specifics

A bot may implement a reset() method that will be called every time an opponent is eliminated. For bots that keep state this might be a good time to clear it.

Other rules:

• You are not allowed to use any form of randomness.
• You are not allowed to use IO
• Standard loopholes apply, in particular no exploiting the controller
• Standard library imports are allowed for simple functionality that you could implement yourself without breaking any of the other rules eg itertools, functools but not for example sys, time or asyncio. Ask if you are not sure. Definitely no attempts to import parts of the controller or other bots.

# Controller

I have a controller written but I would need to simplify it a little to remove some parts that have become redundant. Don't want to put too much effort into making it presentable if it is not a suitable challenge.

# Train A Single Perceptron

You must write a program that will train a perceptron to simulate the things described in the test cases section of this question.

## What is a perceptron and how to train it

A perceptron takes inputs and returns 1 if the dot product of the inputs and its list of weights is greater than or equal to 0 and it returns 0 otherwise. To take the dot product, multiply the elements of the list and take the sum. In other words, your program must find the line (w⋅x=1) that linearly separates the two possible classes of outputs. Example: dot product of [0,2] and [8,3] is 0+6, which equals 6. Your job is to return the list of weights that will make the perceptron return the correct outputs for a list of inputs 100% of the time.

https://desmos.com/calculator/d2nryjmw2t

https://towardsdatascience.com/perceptron-learning-algorithm-d5db0deab975

## Inputs

The program should take as input training inputs and training labels. Each list of inputs corresponds to exactly one output. This data must be used to train the perceptron.

## Outputs

The program should output the final list of weights as integers. The dot product of these weights and any valid input to the perceptron should be the correct output of the perceptron 100% of the time.

## Training

How you train the perceptron is up to you. To train a perceptron to simulate an AND gate, your program should take training inputs and the correct output for each list of inputs. In the case of the AND gate, your program would take [[0,0],[0,1],[1,0],[1,1]] as the list of training inputs and [0,0,0,1] as the list of what the neuron should output given each input. The program should then output a list of weights, which will output the correct output when used in a perceptron.

## Test Cases

1. AND gate:
• Input List: [[0,0],[0,1],[1,0],[1,1]]
• Correct Outputs: [0,0,0,1]
• Your program should output a list of two weights that will solve the problem of behaving like an AND gate when used in a perceptron.
2. Only outputs 1 if the third input is 1:
• Input List: [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
• Correct Outputs: [0,1,0,1,0,1,0,1]
3. OR gate:
• Input List: [[0,0],[0,1],[1,0],[1,1]]
• Correct Inputs: [0,1,1,1]
4. Make up your own test case, and try to make it interesting!

## Scoring

This is code golf, so the shortest program in bytes wins.

• Could you maybe add a note that this task is to find a line ($w \cdot x=1$) that linearly separates the two classes? That might make the challenge more accessible to people unfamiliar with perceptrons. As a side note, the decision are of linear perceptrons can be visualized quite nicely: desmos.com/calculator/d2nryjmw2t
– ovs
Aug 1 '21 at 10:51
• I guess you changed the threshold to $1$ to avoid the bias? I'm not quite sure this works because now the origin $(0,0)$ is always classified as $w\cdot 0=0$. I think just going with the usual definition should be fine.
– ovs
Aug 1 '21 at 10:55
• Ok, I updated it. Aug 4 '21 at 2:11

# Eric Angelini's "1995" puzzle

• your post looks good, tags can be code-golf and sequence. Aug 6 '21 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 '21 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 '21 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 '21 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 '21 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 '21 at 5:40
• @Razetime About half the commands are different, and this is much simpler. Aug 27 '21 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 '21 at 18:23
• Is the input guaranteed to be valid? And what's up with the colons in the example? Sep 8 '21 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 '21 at 0:22
• the acceptance criteria for the numbers needs to be a lot more specific. Aug 19 '21 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 '21 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 '21 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 '21 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 '21 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 '21 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 '21 at 6:25
• @user The footnote at the end is easy to overlook, I'll change it. Aug 20 '21 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 '21 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 '21 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 '21 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 '21 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 '21 at 7:12
• No, the Jimmies are on the backs of more Jimmies, and it's Jimmies all the way dow. Sep 10 '21 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 '21 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 '21 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 '21 at 19:08
• Why not allow giving the first n numbers in the sequence?