Sandbox for Proposed Challenges

Question

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Comments addressing specific points mentioned in the proposal
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Answer 1

Program an Uncircularness Score

derivative of this challenge

Meta:

This is just a rough idea for a slightly different challenge. I have no idea how successfull it would be in the current state, so feel free to share your opinions and suggestions.

code-challengemathgeometry

Your task is to program a mathematical function s, that takes a finite set A of points in the 2D plane, and outputs an uncircularity score s(A) that satisfies following properties:

1. positive definiteness: If there is a circle or a straight line that contains all points of A, then s(A) = 0. Otherwise s(A) > 0
2. It is surjective to the nonnegative real numbers, that means for every nonnegative real number r there is a finite subset A of the plane such that s(A) = r.

Scoring

You get one point for every of the following properties that your function (provably) has.

• Translation Invariance: s is translation invariant if s(A) = s(A + v) for every vector v and for all A.
• Scale Invariance: s is scale invariant, if s(A) = s(A * t) for every t≠0 and for all A.
• Monotony: s is monotonous if s(A) ≤ s(B) for all A,B where A ⊆ B.
• Circle Inversion Invariance: s is circle inversion invariant, if s(A) = s(f(A)) for all A with 0 ∉ A, where f(x,y) = (x/(x^2+y^2), y/(x^2+y^2)) is the circle inversion. (Here (x,y) represent the cartesian coordinates of a point in the plane.)
• Triangle inequality: s satisfies the "triangle inequality" if s(A ∩ B) ≤ s(A) + s(B) for all A,B. (This is implied by Monotony.)
• Reverse triangle inequality: s satisfies the "reverse triangle inequality" if s(A) + s(B) ≤ s(A ∪ B) for all A,B.
• Continuity. s is said to be continuous if the function f(p) := s(A ∪ {p}) (mapping the a point p to a real number) is continuous using the standard absolute value on the real numbers, and the standard euclidean norm on the points of the plane.
• More to come...

Answer 2

Squeeze Out a Square Quine

...the bigger the better.

Task

Write a full program that is a proper quine (a piece of code that outputs itself without reading its source code). To make things more difficult, your code (and obviously the output) has to be in a form of a square, meaning that your code must consist of n lines of length n (not counting the newline to the line length).

Scoring

Your answer's score will be n, the side length of the square. The largest square quine wins. To avoid answers being padded to create arbitrarily large squares, your code must fail to be a proper quine if any single non-newline character is replaced by some other character that appears in the code. There must be, at minimum, two different non-newline characters in the code.

---

For example, if your code was...

abc
def
ghi

...and would output itself, your answer would be valid and its score would be 3.

A single trailing newline in the output is allowed.

code-bowling code-challenge quine source-layout

Answer 3

Shortest Path Distance

Uh oh! You want to get to the point (10,10) from the origin, but there are a whole bunch of boxes in the way! What is the length of the shortest path which avoids all of them?

Input

Your program should take a set of rectangles, defined by the coordinates of two opposite corners, as input; the format is up to you.

For example, a possible input might look like

[[(1,3), (5,2)], [(5,4), (7,5)]]

But you could also take it as

[(1,3), (5,2)]
[(5,4), (7,5)]

Or anything else, as long as it allows for unambiguous input.

These inputs would define the rectangles shown below:

You can assume that all rectangles will have integer coordinates with x,y between 1 and 9 inclusive, which guarantees a possible path. You can also assume that no rectangles intersect in any way (that means no shared edges or vertexes).

Output

Your program/function must return the value of the shortest path from the origin to (10,10), have the absolute error at most 10^-2 and measured using the euclidean metric.

In the example given above, 14.564 and 14.56 would be accepted, while 14.55 and 14.57 would not.

Example I/O

[[(1,3), (5,2)], [(5,4), (7,5)]] -> 11.40
[] -> 14.14
[[(1,1), (2,9)], [(9,2), (3,1)]] -> 14.28
[[(2,2), (1,1)], [(9,3), (8,5)], [(1,9), (2,8)]] -> 14.28 (Note: rounded up)
[[(9,1), (1,9)]] -> 18.11

Other Rules

Shortest code wins, no exploiting loopholes, yadda yadda yadda, you get the idea, it's code golf.

Answer 4

Any comments for improvement would be appreciated.
Should I choose a harder function? (maybe "Is this binary number prime?")
Or maybe not harder, but some other decision problem suggestion?

Majority function, a non-uniform computing challenge

Non-uniform computing is a class of computing where a different procedure can be specified for each input size of a problem. This allows discussing complexity of languages that are only straight line computations (no looping constructs), yet which are powerful enough to compute any fixed input size function a Turing machine can compute. It also allows taking advantage of algorithms that may work well if only you could tweak a parameter for each size (even if the parameter is difficult to compute) or where there are only a small number of exceptions in each input size (so checking those exceptions then using the algorithm succeeds).

Goal:

Write a program or function which, given an input length, outputs an If-Then-Else sequence (defined below) which determines if greater than half the inputs are 1 (the majority function).

This is code-challenge. Your score will be:

G20 + 4*G5 + 10*G2 + L

Where L is the size of your submission in bytes, and G20 is the length of the generated If-Then-Else sequence for size=20 (length being defined as number of If-Then-Else statements). Similarly G5 and G2 are the lengths for the generated programs for size=5 and size=2 respectively. The lowest score wins.

This is in some sense an "inception" code golf. You will be judged on the length of your program as well as the length of the programs it generates.

To prevent submissions that just loop over all possible ITE sequences till it finds the smallest one that works, entries need to provide the G20, G5, G2 values along with the code submission for it to be a valid entry. As the number of possible sequences quickly becomes infeasible to search, this should eliminate raw brute forcing.

If-Then-Else "programs"

An If-Then-Else (ITE) statement is a logical statement of the form:

if A then B else C

The logical value of this statement is referred to as the "output", and the values A, B, and C are the "inputs" of the statement. To turn this into a formatted language, a file (or string) describing an ITE program will be a series of lines that contain:

<input_term> <space> <input_term> <space> <input_term>

Where an input_term is one of:

• '0'
• '1'
• 'I' <decimal_number>
• 'Q' <decimal_number>

The values 0 and 1 are Boolean false and true respectively. The value of I(number) is the value of the input at index 'number'; for example I3 = Input #3 (input numbering starts at zero). The value of Q(x) is the result of ITE statement number 'x' (again, numbering starts at zero).

The result of an ITE program is the output of its last statement.

Example ITE program

Here is a simple interpreter for ITE programs, written in python: ite.py

This interpreter has some additional features like comments (start a line with #) and custom output names (start line with <name>: ) which are useful when playing with some ideas by hand. If you choose to utilize those features in your generated ITE programs, that's fine, although I'm not sure how that would help. This will be considered the defacto standard for the ITE language for this competition.

Here is an example program: parity4.ite

I0 0 1
I1 Q0 I0
Q1 0 1
I2 Q2 Q1
Q3 0 1
I3 Q4 Q3

As its name suggests, this is the parity function for input size 4. It returns 1 if the 4 inputs bits have an odd number of 1s, otherwise it returns 0. Here is an example of testing it on some values.

$ python ite.py parity4.ite 0110
0
$ python ite.py parity4.ite 0111
1

Answer 5

Solve the Square-Sum problem

Based on these (very good) Numberphile videos:

The Square-Sum problem and its extra footage.

The Problem:

Given a list of integer numbers [1,n] where n≥15; n≠18, 19, 20, 21, 22, 24, your task is to arrange those numbers in a way such that the sum of two consecutive numbers is a square number.

Example for n=15:

Original sequence: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Square-sum of it: 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
                   | |  |  | | |  |  | | |  |  | | |
                  3² 4² 5² 4²3²4² 5² 4²3²4² 5² 4²3²4²

This problem can be solved by creating a graph of every sum of two numbers in the sequence that result in a square number:

From that graph, it's possible to find its Hamiltonian Path:

This path, if existing, is the solution to the square-sum problem.

Rules:

---Under Construction---

Sandbox:

• Suggestions?
• Dupe?
• Test cases are under construction

Answer 6

Word ladder

A word ladder is a puzzle where the aim is to create the smallest sequence of steps between two fixed words (a starting word and a target word), where each step changes one letter to produce a new word. All the intermediate words must be recognised in a dictionary (which will be supplied).

If the target word is longer than the starting word, a step may add a letter at any position instead of changing one; if it's shorter than the starting word, a step may remove a letter instead of changing one.

Examples:

HAND
BAND
BOND
FOND
FOOD
FOOT

FINGER
FINER
FINE
TINE
TONE
TOE

EYES
EYED
DYED
DEED
TEED
TEND
TENT
TENTH
TEETH

The challenge

Write a program or function which accepts a dictionary of words and the two fixed words (i.e. a starting word and a target word), and produces an ordered list of intermediate words following the rules above. You may choose to output the starting word, the target word, both, or neither.

You may use any of the standard methods of input and output, and must not bypass the rules with any of the standard loopholes.

Scoring

(I need some help with this part).

The score is the number of dictionary lookups your program makes during a test run (or average of several test runs, if it's not deterministic) on a set of inputs with a simple English dictionary. Q: does this test set need to be prepared and included in the question?

---

Sandbox questions

I don't really want to make this a code-golf, as we'll just end up with simple brute-force algorithms; I really want to see creative use of the dictionary, either by pre-processing or perhaps by ordering candidate words.

Is there a way we can define a "dictionary lookup" and somehow separate the word generation/validation from knowledge of the fixed words, without making assumptions that the language has functions or other methods of isolating code?

Can we require the dictionary to be a separate process, and provide a reference implementation? I don't think we can, without excluding languages without reasonable inter-process communication (I'm thinking of PostScript, possibly JavaScript, and microcomputer BASIC).

Answer 7

Objective

Given a 2D array (of x by x size), write a program or function to alternatively shift elements of the array along the anti-diagonals. (anti-diagonals are right to left, top to bottom). (first anti-diagonal moves down second anti-diagonal moves up with elements wrapping when they reach the end of the anti-diagonal)

Example

a b c d
e f g h
i j k l
m n o p

Will become:

a e i g
b c j n
f m h o
d k l p

I will follow the tradition of selecting the shortest working code as the best answer

**edited for user202729 suggestion

Answer 8

Shape sequence sums

0. DEFINITIONS

For the purposes of this challenge, a sequence refers to a list of numbers whose absolute values increment in steps of 1. A sequence begins with a value of 1, 0, or -1.
A positive sequence refers to the natural numbers: 1, 2, 3, 4, and so on.
A negative sequence refers to the additive inverses of the natural numbers: -1, -2, -3, -4, and so on.

1. CHALLENGE

Given an integer n, return a list of sequences such that the sum of all the numbers in the list is equal to n. Sequences must alternate in sign (see test cases). Solutions must produce the list with the fewest sequences; that is, the sign should change a minimal number of times. (Read: Don't do 1, 2, -1 over and over again.) The resulting list must be flat, not nested. The shortest working solution wins.

2. TEST CASES

 17: 1, 2, 3, 4, 5, 6, -1, -2, -3, 1, 2, -1
 18: 1, 2, 3, 4, 5, 6, -1, -2
 19: 1, 2, 3, 4, 5, 6, -1, -2, 1
 21: 1, 2, 3, 4, 5, 6
-21: -1, -2, -3, -4, -5, -6
 -5: -1, -2, -3, 1
  0: 0 or [] (null set)

You may choose to begin each sequence with 0 instead of 1 or -1. However, if you do this, every sequence must begin with a zero, not just the positives, the negatives, the first sequence, or any other strict subset. This also means that input 0 requires a list containing a single 0.

 17: 0, 1, 2, 3, 4, 5, 6, 0, -1, -2, -3, 0, 1, 2, 0, -1
  0: 0

integer number code-golf

Answer 9

Different tasks, same characters, level 2

In this challenge, you need to solve 3 different tasks using the same set of characters. You can rearrange the characters, but you can't add or remove characters.

The winner will be the submission that solves all tasks using the smallest number of characters. All tasks must be solved in the same language.

Note that it's the smallest number of characters, not the smallest number of unique characters.

Twist: If one or more characters can be removed from a script without breaking it, then your submission is disqualified. This means that comments are out of the picture, as well as long variable names to get the character counts to match up.

You do not have to prove that it's impossible to remove characters and still have a functioning script, but you should try to make it impossible. If nobody bothers to look at it, then your submission is valid. If nobody sees a way to remove one or more characters, then your submission is valid. If however, someone looks at your post and sees something that can be removed without breaking it, then your submission is invalid.

---

Tasks:

I'll create 3 tasks that are fairly simple typical code-golf tasks.

---

So, what do you think about the idea?

Answer 10

What's in an ISBN?

code-golf

Given an ISBN-10 code starting with 0 or 1, extract the registration group, registrant, publication, and checksum numbers.

Background

We've talked about International Standard Book Numbers before, including converting them and calculating their checksums. Now let's talk about parsing their data.

An ISBN-10 code has four parts; in order from left to right: registration group, registrant, publication, and checksum. We're only going to consider registration group numbers 0 and 1, which represent English-speaking areas. Take a look at these two ISBN-10 codes, shown with their parts separated:

• 0-307-45547-5 – This book, from registration group 0, is printed by publishing giant Penguin Random House. Penguin prints thousands of books, so it's assigned ISBN blocks with few digits for registrar (307 here), leaving many digits for publication (45547). The checksum is 5.

• 1-940696-27-5 – This book, from registration group 1, is printed by indie poetry press Wave Books, which prints just a few books each year, so its ISBN blocks have many digits for registrant (940696 here) and just a few for publication number (27). The checksum is also 5.

Specification

Write a program or function that takes a non-separated ISBN-10 code and return its four parts as distinct values.

ISBN-10 codes in registration groups 0 and 1 are separated according to the following scheme, where xx… is registrant number and y is checksum.

From            to                 From            to
-------------   -------------      -------------   -------------
0-00-xxxxxx-y … 0-19-xxxxxx-y      1-00-xxxxxx-y … 1-09-xxxxxx-y
0-200-xxxxx-y … 0-699-xxxxx-y      1-100-xxxxx-y … 1-399-xxxxx-y
0-7000-xxxx-y … 0-8499-xxxx-y      1-4000-xxxx-y … 1-5499-xxxx-y
0-85000-xxx-y … 0-89999-xxx-y      1-55000-xxx-y … 1-86979-xxx-y
0-900000-xx-y … 0-949999-xx-y      1-869800-xx-y … 1-998999-xx-y
0-9500000-x-y … 0-9999999-x-y      1-9990000-x-y … 1-9999999-x-y

For example, 0307455475 lies in the range 0-200-xxxxx-y … 0-699-xxxxx-y, so we know it has three digits for registrant and five for publication and the program, given this input, should return 0, 307, 45547, and 5.

Likewise, 1940696275 is in the range 1-869800-xx-y … 1-998999-xx-y, so the program should return 1, 940696, 27, and 5.

Input

• Input may be in any convenient format, e.g. a string, list of characters, or list of numbers.
• The input must be 10 or fewer characters or numbers, plus an optional trailing newline. Leading zeroes are optional.
• In ISBN-10 codes the checksum 10 is represented with an X. If your program takes input as a list of numbers, the number 10 may be used. If it takes input as a string or list of characters, a single non-digit character of your choosing (e.g. X or x) must be used.
• Otherwise, standard input rules apply.

Output

• Output may be in any convenient format, as long as each part is easily distinguishable from the next, e.g. a delimited string, a list of four numbers, or a list of four lists of numbers.
• Leading zeroes are optional.
• If the checksum is 10, it may be 10 (as a number or string) or a single non-digit character of your choosing. For example, both 0 8044 2957 X and 0 8044 2957 10 are valid.
• Otherwise, standard output rules apply.

Winning

This is code-golf; the solution with the fewest bytes wins.

Standard loopholes are forbidden.

Test cases

Input       Output
0000000000  0-00-000000-0
0144751605  0-14-475160-5
0393765621  0-393-76562-1
0763320041  0-7633-2004-1
0859056018  0-85905-601-8
0906789222  0-906789-22-2
0958171947  0-9581719-4-7
0999999999  0-9999999-9-9
099999999X  0-9999999-9-X
1000000000  1-00-000000-0
1080925818  1-08-092581-8
1149092167  1-149-09216-7
1457721261  1-4577-2126-1
1578424693  1-57842-469-3
1973088617  1-973088-61-7
1999973361  1-9999733-6-1
1999999999  1-9999999-9-9
199999999X  1-9999999-9-X

Sandbox questions

1. What are good tags for this?

2. Is the description of the separation scheme clear?

3. Any test cases missing (or wrong)?

Answer 11

Code Basketball

king-of-the-hill

Programs are competing in a game of "basketball". They are given a 5x6 (Minus the top center character) grid on which to put either /, \, or ^. The programs can place two symbols every tick on the grid. If the programs try and place a symbol at the same place at the same time, neither symbol is placed.

On the first tick, a 'ball', o, is spawned at (3,6) on the grid. The ball falls by one character every tick. If the ball encounters a \ while falling, it moves to the right. If it encounters a /, it moves to the left. If the ball hits a ^, it moves back to the top of the grid at that x position. The ball only moves once every tick, and does not effect the map on it's own.

When the ball is on the bottom row, if it's on the left, it gives a point to the first program and respawns, if it's on the right, it gives a point to the second program and respawns. If it's in the center, it simply respawns without giving points to anyone.

If the ball tries to move off the map, it simply stays in place.

The grid is rotated when transfered to the contending programs so that it always appears that the left is that program's goal.

Program I/O

Programs use Standard Input and Standard Output to communicate to the contest framework. The program is sent a 30 byte buffer containing a map and a 2 byte buffer containing the position of the ball.

The program must send two 3 byte buffers in response with the character to put on the map, it's x position, and it's y position.

The framework gives each program 5 seconds to perform there action. If they fail to be within this 5 second window three times, they automatically lose to prevent the round from going on too long.

Competition

Programs will compete in pairs of two. The winner of each pair will move on to the next round, and be paired up with another winner.

Sandbox questions

1. How can this be improved?

2. What actions should I take to make sure rounds are fair?

3. How should invalid data be handled when sent to the framework?

Answer 12

Basketball Recruitment king-of-the-hill

You're recruiting your local neighborhood for your Jr Basketball team. However, the opposing team also is recruiting!

• You both stand at the end of the street of 100 houses. Each house has a kid with a unique, random height from 1 to 100. Taller is better.

• Actions take different amounts of time. Your opponent may have a different turn order, or may even have more/less turns than you.

• If you have spent less than or equal time than your opponent, then your turn is next (turns can be simultaneous)

On your turn you perform one of the following actions:

• Recruit the kid at the Nth house. This takes N Time.
  • If you both recruit the same kid, you get into argument, and he decides not to play basketball this year. (Nobody gets him)
  • Once recruited, a kid won't switch sides.
• Disqualify the kid at the Nth house. There are myriads of rules to Jr Basketball, and you know just which rules he's breaking. This takes 10 time.
  • You cannot disqualify a kid that has been recruited or is in the process of recruitment.
  • If you try to disqualify a kid on the same turn your opponent tries to recruit him, the disqualification fails.

After all of the boys have been recruited, been disqualified, or lost interest, we play the big game:

1. We place the teams into two lines from shortest to tallest.
2. Each pair of boys play each other.
3. The taller one wins, and gives his team 1 point.
4. If a team has more boys than the other, they get 1 point for each extra boy.
5. The team with the most points wins.

Now, your goal is to become the top recruiter. This means you need to win as many games as possible. You will face many other recruiters at random until a clear victor is decided.

Answer 13

Fortnightly Challenge #8: A new kind of "asynchronous" KOTH

This is a placeholder for the challenge spec. You can discuss this challenge in a special chat room.

---

Ordinary KOTHs require that a single user take up the job of hosting the competition: running the whole competition at once by themselves. Everything is dependent on them, and they can only run so many competitions or update ever so frequently. I think this can be improved... somehow.

Here are some ideas, many of which would require an encryption scheme or something to ensure correctness.

• Anybody can run the tournament and add their results to the current leaderboard somehow. This could be accomplished by some sort of cryptographic scheme to verify the results. Ideally the controller will be implemented via stack snippet to allow ordinary people to run it without downloading a controller.

• When a bot is added/updated, only the new pairs of contestants should be tried, and nearly anyone can update the leaderboard by themselves. (Assuming a deterministic KOTH, which it will probably need to be in order to prevent people from simply uploading the results that occurred in their favor.)

Answer 14

Generate a maximal binary Gray code

Given an input integer n, find an n-bit gray code where the sum of the absolute difference between each adjacent pair of bits converted to decimal is maximized.

For example, if n = 3, there are 96 possible gray codes, and the maximal sum of deltas in decimal of those is 21. Out of the 96 total, only 8 have maximal deltas.

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 0│0 0 1│0 1 0│0 1 1│1 0 0│1 0 1│1 1 0│1 1 1│
│1 0 0│1 0 1│1 1 0│1 1 1│0 0 0│0 0 1│0 1 0│0 1 1│
│1 1 0│1 1 1│1 0 0│1 0 1│0 1 0│0 1 1│0 0 0│0 0 1│
│0 1 0│0 1 1│0 0 0│0 0 1│1 1 0│1 1 1│1 0 0│1 0 1│
│0 1 1│0 1 0│0 0 1│0 0 0│1 1 1│1 1 0│1 0 1│1 0 0│
│1 1 1│1 1 0│1 0 1│1 0 0│0 1 1│0 1 0│0 0 1│0 0 0│
│1 0 1│1 0 0│1 1 1│1 1 0│0 0 1│0 0 0│0 1 1│0 1 0│
│0 0 1│0 0 0│0 1 1│0 1 0│1 0 1│1 0 0│1 1 1│1 1 0│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Checking the first result, the decimal values are

0 4 6 2 3 7 5 1

and the deltas of each adjacent pair are

4 2 4 1 4 2 4

and the sum of that is 21.

Rules

• The input will be an integer n > 0.
• You may output either one or all possible gray codes that satisfy the condition.
• code-golf

Answer 15

The Euler Masheroni Constant

The Euler Masheroni constant is a very interesting number. It is defined to be and appears seemingly everywhere in number theory. Famously, it is unknown whether it is rational, irrational, or transcendental.

The Challenge:

Pretty simple one here: Given N, your program should calculate the Euler Macaroni constant to at least N decimal places of prescision. Your score will be the maximum value of N for which the program is accurate, and ties will be won by the shortest code.

For refrence, the Euler Macaroni constant to 50 places is

0.57721566490153286060651209008240243104215933593992

Be sure to check out the wikipedia page for more formulas for the Oily Macaroni constant!

https://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant

Answer 16

Design a language and golf its interpreter

Your task is to design a language and write an interpreter for it. Your language must have the following properties:

• Its source code will consist of strings of two characters. I will write them as ( and ) and refer to them as parentheses, but you can choose whichever two distinct characters you like. You can choose whether to ignore other characters.

• Valid programs will consist of any string in which the parentheses are balanced, such as ()() or (()(()())). The empty string is a valid program. You may assume the input will be a valid program.

• Programs will take an input and return an output. Valid inputs and outputs are of the same form as source code: they must be balanced strings of parentheses. This input and output may be accomplished by any method you like, e.g. command-line arguments or STDIN/STDOUT. You may assume your program's input will always be valid.

• Your program must be Turing complete. That means that for every computable function from balanced strings to balanced strings, there must be a program in your language that computes it. Your answer must include a proof of Turing completeness, otherwise it is not a valid answer.

This is code-golf. Your score will be the size of your interpreter's implementation, measured in bytes. The lowest score wins.

Here are some additional rules and clarifications:

• Your interpreter must be a complete program

• You must include a description of your language's semantics. This is needed in order to prove that it's Turing complete.

• Your interpreter must correctly implement these semantics. (Or at least, it must be able to in principle, given infinite machine resources.) If someone finds a bug in your interpreter, your answer becomes invalid until it's fixed.

• You may not assume numerical types are of unlimited precision unless they actually are - be careful of integer overflow!

Here is the precise grammar for programs as well as input and output strings:

<expr> ::= "(" <expr_list> ")"
<expr_list> ::= "" | <expr_list> <expr>.
<program> ::= <expr_list>

You can optionally replace the last line with

<program> ::= <expr>

which means there must always be an enclosing pair of parentheses. (So ()() and the empty string would not be valid programs, for example.) If you do this, you must do it for input and output strings, as well as programs.

As mentioned above, ( and ) may be replaced with any two distinct characters.

Sandbox notes

I've been obsessed with designing a simple and elegant language with these properties for some time, but I've never come up with one that really satisfied me. It occurred to me that "source code size of the interpreter" might work as a proxy for simplicity and elegance, so I thought I'd give this a try. Suggestions for a better winning criterion (making it a code-challenge) would be welcome.

I'd also welcome suggestions for a snappier title.

Answer 17

Find Graph Isomorphism

Meta:

I don't know whether there are any known algorithms for solving this problem, that also means I'm not sure whether this is an interesting challenge. EDIT: Ok it is probably equally hard as the graph isomorphism problem.

Inspired by this puzzle graph-theoryfastest-algorithm

Given two isomorphic directed (unweighted) graphs with labelled nodes, find an isomorphism between the two graphs.

Details

• You have to provide a working implementation of your algorithm.
• You have to provide the complexity expressed in the number of nodes, edges (or possibly other numbers?)
• The graphs can be represented as an adjecency matrix, as set of pairs that represent edges, as an adjecency list or as a native graph type etc.
• The output can be a function that maps the labels of one graph to the labels of the other, as a list as a graph etc.
• If necessary, you can assume that there are no edges with the same start as end node.

Examples

to be added...

Answer 18

Assemble an XOISC program

Tags: code-golf, parentheses, parsing

---

Recently I solved this challenge, for which I created XOISC - a very low-level functional language. To compile a program (written in the absurdly high-level lambda calculus programming language) it must first be translated into an expression consisting only of X combinators and from there it can be translated to the "machine language".

There's an initially empty stack and the program only consists of a stream of integers. For each integer the following happens:

Pop N elements f₁,...,f_N and push X (f₁ (..(f_N-1 f_N)..)) - ie. it right-folds function application and applies this to another X.

Eventually we'll end up with a stack of functions which gets left-folded with function application. That's it.

How does it work?

When parsing such an expression, one thing to keep in mind is that function application is left-associative - meaning that X (X X) X is read as (X (X X)) X rather than X ((X X) X).

If we have an expression f g with sub-expressions f and g (in the code below App f g - eg. X (X X) X would be f = X (X X) and g = X), there's a simple recursive algorithm to assemble it:

-- Base case: We simply need to pop the accumulated functions 
asm' n X         = [n]
-- Recurse: First build the left function, then the right one. 
--          Incrementing n ensures that we leave (f g) on stack
asm' n (App f g) = asm' 0 f ++ asm' (n+1) g

-- Now we start with 0 functions on the stack:
asm expr = asm' 0 expr

For those unfamiliar with Haskell:

• this algorithm assumes an already parsed expression in the form of of a binary tree (the definition of the data structure would be data Exp = X | App Exp Exp where X would be a leaf and App f g would be a node with children f and g that are Exps as well)^*
• asm' n exp does a case distinction by matching a pattern on exp:
  • if the expression is X (ie. exp = X) it's the base case and just returns a singleton list containing n (an integer)
  • else it's of the form f g (with f,g some sub-expressions) which is expressed as App f g, so it will recursively build the list for f and append the list of g
• to assemble an expression exp we begin initialize the recursive algorithm with n = 0 (asm' 0 exp)

Note: Since a lot of people here know Python, you can find a horrible but very well documented Python reference implementation here which does the parsing as well as the assembling!

---

^* The | means that an Exp type can be constructed of either the left constructor (X) or of the right one (App Exp Exp where the two Exp are Exp two sub-expressions).

For example the expression X (X X) X would be expressed as App (App X (App X X)) X.

Example

Having an expression X (X X) X, it helps to think of the implicit parentheses: (X (X X)) X

Translating this with the above algorithm:

• Assemble (X (X X)):
  • Assemble X:
    • Base case => 0
  • Now Assemble X X, making sure it gets applied to the previous one (+1)
    • The first X gives us a 0
    • The second one gives us 0 + 1 + 1 = 2 (apply to X and previous one)
• So the left (X (X X)) gave us [0,0,2], assembling the right X:
  • This gives us 0 + 1 (apply to the previous one)

And we end up with the program [0,0,2,1].

Note: While this algorithm ensures that there's a program for every expression, there can be other solutions too. For example [0,0,1,0] would be a valid one for X (X X) X as well.

Challenge

Given an expression consisting of X combinators, translate it to the XOISC machine language:

• Input will be a string encoding such an expression
  • The input will be a valid expression and non-empty
  • You may choose to require an input string that contains no spaces
  • You may choose the characters encoding parentheses and the combinator itself (as long as it's consistent, eg. using [,],x instead of (,),X)
  • You're guaranteed that there are no unnecessary parentheses (eg. (X X) X would result in undefined behaviour)
• Output can be a list of integers, a string separated by new-lines or whitespaces

Testcases

These testcases assume that the input contains whitespaces and choose X to encode the combinator.

Note that there may be multiple valid outputs, you're free to choose one^* - I'll only show the solution resulting from the above algorithm:

X -> [0]
X X X -> [0,1,1]
X (X X) -> [0,0,2]
X (X X) X -> [0,0,2,1]
X (X (X (X X X))) -> [0,0,0,0,1,4]
X (X X) (X X) (X X) -> [0,0,2,0,2,0,2]
X (X X X (X X)) -> [0,0,1,1,0,3]
X (X (X X) (X X)) -> [0,0,0,2,0,3]
X X (X X (X (X (X (X (X X X)))) X) X) -> [0,1,0,1,0,0,0,0,0,1,5,2,2]
X (X (X X) X (X X X)) X (X (X (X X) X)) -> [0,0,0,2,1,0,1,3,1,0,0,0,2,3]
X (X (X (X (X X) X X) X X X) X X X X) X X X X X -> [0,0,0,0,0,2,1,2,1,1,2,1,1,1,2,1,1,1,1,1]
X (X (X X (X X) (X X) (X X) X) X (X X) X) X (X X X) X -> [0,0,0,1,0,2,0,2,0,2,2,1,0,2,2,1,0,1,2,1]

---

^{* Here's a program to validate alternative solutions}

Sandbox

• I already posted this to main, but apparently I did a bad job of explaining it.. It's hard to tell what's missing, I'd be happy for feedback (feel free to edit this)!

Answer 19

Convert Arabic Numbers to Chinese Numbers code-golf

There EXISTS a similar question, "Convert Chinese numbers", but the question itself differs from that question by:

1. That question asks for a shortest code converting Chinese numbers to Arabic numbers, but this asks for a shortest code converting in the opposite direction.
2. That question limits the range of 1 <= N < 10^3, but this has the range far larger than that -- 1 <= N < 10^8192.
3. Due to the range of that question, that question only considers one type of representation on Chinese numbers, but this considers four -- the commonly used Wan Jin (萬進) and other ancient systems. These terms will be explained in the introduction part.

There EXISTS another similar question "Convert a number to Korean", but there is essential difference because Korean number only uses Wan Jin, always omits "一(일)"s before "十(십)"s, "百(백)"s and "千(천)"s and all "零"s between digits, and so does Japanese.

Sandbox

• I have edited the challenge description so that the rules are now outlining the process of conversion. Although this will be clearer in illustrating the rules, will this be restricting the choice of algorithms?

Introduction

Chinese numbers, literally, is the number still in use in societies which uses Chinese characters. Although Arabic numbers are also in use nowadays, Chinese numbers still have an important role.

The system Chinese people in Taiwan are using is called Wan Jin (萬進), which names 1,000,000,000,000 (1 trillion) as Yi Zhao (一兆). However, according to Wu Jing Suan Shu (五經算術) ,in the history there existed 3 different kinds of such large-number representations. The reference says:

按黃帝為法，數有十等。及其用也，乃有三焉。十等者，謂「億、兆、京、垓、秭、壤、溝、澗、正、載」也。三等者，謂「上、中、下」也。其下數者，十十變之。若言十萬曰億，十億曰兆，十兆曰京也。中數者，萬萬變之。若言萬萬曰億，萬萬億曰兆，萬萬兆曰京也。上數者，數窮則變。若言萬萬曰億，億億曰兆、兆兆曰京也。

(Translation) According to Huang Di, there are 10 "ranks" of numbers. Regarding the usages, there are three. The 10 ranks are called Yì (億), Zhào (兆), Jīng (京), Gāi (垓), Zǐ (秭), Ráng (穰), Gōu (溝), Jiàn (澗), Zhèng (正), Zài (載). The three usages are called "Upper", "Middle" and "Lower". For the "Lower", the rank changes if multiplied by 10. We call 10 Wàn as Yì, 10 Yì as Zhào, and 10 Zhào as Jīng. For the "Middle", the rank changes if multiplied by 100,000,000. We call 100,000,000 Wàn as Yì, 100,000,000 Yì as Zhào, and 100,000,000 Zhào as Jīng. And for the "Upper", the rank changes if the rank exhausts its numbers. We call 1 Wàn Wàn as Yì, 1 Yì Yì as Zhào, and 1 Zhào Zhào as Jīng.

To sum up, we have 4 systems which is, or was in use in Chinese history:

• Xia Shu (下數): Starting from wan (萬, 10,000), the rank changes by multipling by 10. 10 wan is called yi (億, 100,000), 10 yi is called zhao (兆, 1,000,000), 10 zhao is called jing (京, 10,000,000), etc.
• Zhong Shu (中數): Starting from wan (萬, 10,000), the rank changes by multipling by 10⁸, with the exception of yi, which represents 10^8. 10,000 wan is called yi (億, 10^8), 10⁸ yi is called zhao (兆, 10^16), 10⁸ zhao is called jing (京, 10^24), etc.
• Shang Shu (上數): Starting from wan (萬, 10,000), the rank changes by squaring. 10,000 wan is called yi (億, 10^8), 10⁸ yi is called zhao (兆, 10^16), 10¹⁶ zhao is called jing (京, 10^32), etc.
• Wan Jin (萬進): Starting from wan (萬, 10,000), the rank changes by multipling by 10,000. 10,000 wan is called yi (億, 10^8), 10,000 yi is called zhao (兆, 10^12), 10,000 zhao is called jing (京, 10^16), etc.

Table 1: Rank markers in Chinese numbers

 Name    Wan Jin      Xia Shu      Zhong Shu   Shang Shu
(十               commonly representing 10^1            )
(百               commonly representing 10^2            )
(千               commonly representing 10^3            )
(萬               commonly representing 10^4            )
 億      10^8         10^5         10^8        10^8
 兆      10^12        10^6         10^16       10^16
 京      10^16        10^7         10^24       10^32
 垓      10^20        10^8         10^32       10^64
 秭      10^24        10^9         10^40       10^128
 穰      10^28        10^10        10^48       10^256
 溝      10^32        10^11        10^56       10^512
 澗      10^36        10^12        10^64       10^1024
 正      10^40        10^13        10^72       10^2048
 載      10^44        10^14        10^80       10^4096

For numbers smaller than 10, this works as

零:0 一:1 二:2 三:3 四:4 五:5 六:6 七:7 八:8 九:9

Challenge

In this challenge, you are required to write the shortest code, accepting two inputs: the number N, and a number S indicating the system used, converts N into the corresponding Chinese representation according to the given system, and output the representation. Here are some basic rules about converting Chinese numbers:

For numbers less than 10,000 and Xia Shu numbers:

1. Append position markers digit by digit first.
   • 1234 => 一千二百三十四
   • 1234567 => 一兆二億三萬四千五百六十七
2. Strip away all position markers prepended by "零", coalesce all consecutive "零"s into a single "零", and remove the leading/trailing "零"s.
   • 5 => 五, 25 => 二十五, 125 => 一百二十五
   • 20 => 二十, 100 => 一百, 5000 => 五千.
   • 1001 => 一千零一

For Wan Jin numbers:

1. Divide the digits into subgroups of at most 4 digits each from the right.
   • 12345678900004321 => 1'2345'6789'0000'4321
2. Apply to each subgroup the conversion for numbers less than 10,000 (as above), and append each subgroup with the corresponding rank markers. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
   • 1'2345'6789'0000'4321 => (一)京(二千三百四十五)兆(六千七百八十九)億零(零)萬零(四千三百二十一)
3. Discard the subgroups with "零", together with their rank markers, and remove redundant "零"s.
   • (一)京(二千三百四十五)兆(六千七百八十九)億零(零)萬零(四千三百二十一) => 一京二千三百四十五兆六千七百八十九億零四千三百二十一

For Zhong Shu numbers:

1. Divide the digits into subgroups of at most 8 digits each from the right.
   • 12345678900004321 => 1"23456789"00004321
2. Apply to each subgroup the conversion for Wan Jin numbers (as above), and append each subgroup with the corresponding rank markers. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
   • 1"23456789"00004321 => (一)兆(二千三百四十五萬六千七百八十九)億零(四千三百二十一)
3. Discard the subgroups with "零", together with their rank markers, and remove redundant "零"s.
   • (一)兆(二千三百四十五萬六千七百八十九)億零(四千三百二十一) => 一兆二千三百四十五萬六千七百八十九億零四千三百二十一

For Shang Shu numbers:

1. Divide the digits into 2 subgroups: the least significant one with number of digits equals to the least power of 2 not less than half of the original length, and the most significant one with the remaining digits.
   • 123456789012345678901234567890 => (12345678901234)(5678901234567890)
2. Append the most significant subgroup with the corresponding rank marker. If there is any "0" at the subgroup boundary, append "零" after the rank marker.
   • (12345678901234)(5678901234567890) => 12345678901234兆5678901234567890
3. Discard the subgroups with "零", together with their rank markers
4. Recursively apply all steps to each subgroup with a lower rank marker, until the number of digits in a subgroup is less than 4, which then apply the conversion for numbers less than 10,000 (as above).
   • 12345678901234兆5678901234567890 => 123456億78901234兆56789012億34567890 => 12萬3456億7890萬零1234兆5678萬9012億3456萬7890 => 十二萬三千四百五十六億七千八百九十萬零一千二百三十四兆五千六百七十八萬九千零一十二億三千四百五十六萬七千八百九十

And at last...

1. If "一十" is at the beginning, remove the "一".
   • 15 => 十五
   • 114514 => 十一萬四千五百一十四, 10011 => 一萬零一十一.
2. Remove redundant "零"s, and if an empty string occurs, return with "零".

For more details, the reference implementation in JSFiddle gives the reference code.

Requirements

• Your code must be a full program or a function. Defining helper functions are allowed. Snippets are not allowed.
• Standard loopholes are not allowed by default.
• You can use any methods of I/O that are considered "standard" by PPCG community.
• You must receive 2 inputs, one number N, and one number S. You can pass the inputs as strings or as integers. Please indicate your choice.
• You may assume the input is always valid, i.e. S in [0, 1, 2, 3] and N is within the corresponding range:

Table 2: Number systems and their representable number range

S (System)       N (Number Range)
0 (Wan Jin)      1 <= N < 1E+48
1 (Xia Shu)      1 <= N < 1E+15
2 (Zhong Shu)    1 <= N < 1E+88
3 (Shang Shu)    1 <= N < 1E+8192

• In case Unicode is not supported by the interpreter and/or the language, or for any reasons, you may use one of the two Chinese Pinyins in place of the corresponding Chinese characters as output as follows. Your choice must be consistent over all outputs. One space must be added between the pinyins of 2 characters. You must indicate if you choose to do so.

Table 3: The Chinese characters and their pinyin representations

Character  Pinyin              Character  Pinyin
一         yī or yi1           二         èr or er4
三         sān or san3         四         sì or si4
五         wǔ or wu3           六         liù or liu4
七         qī or qi1           八         bā or ba1
九         jiǔ or jiu3         十         shí or shi2
百         bǎi or bai3         千         qiān or qian1
萬         wàn or wan4         億         yì or yi4
兆         zhào or zhao4       京         jīng or jing1
垓         gāi or gai1         秭         zǐ or zi3
穰         ráng or rang2       溝         gōu or gou1
澗         jiàn or jian4       正         zhèng or zheng4
載         zài or zai4         零         líng or ling2

Example I/O (Only the first Pinyin format is displayed)

In these examples, I use ' => 萬, " => 億, (...) => 兆, [...] => 京, {...} => 垓, <...> => 秭 in the grouping for clarity. The grouping is only for illustration, and you do not need to print the groupings.

Input:    18446744073709551616 0
Grouping: [1844](6744)0737"0955'1616
Output:   一千八百四十四京六千七百四十四兆零七百三十七億零九百五十五萬一千六百一十六
    or    yī qiān bā bǎi sì shí sì jīng liù qiān qī bǎi sì shí sì zhào líng qī bǎi sān shí qī yì líng jiǔ bǎi wǔ shí wǔ wàn yī qiān liù bǎi yī shí liù

Input:    1234567890 1
Grouping: <1>{2}[3](4)5"6'7890
Output:   一秭二垓三京四兆五億六萬七千八百九十
    or    yī zǐ èr gāi sān jīng sì zhào wǔ yì liù wàn qī qiān bā bǎi jiǔ shí

Input:    1267650600228229401496703205376 2
Grouping: [126'7650](6002'2822)9401'4967"0320'5376
Output:   一百二十六萬七千六百五十京零六千零二萬二千八百二十二兆九千四百零一萬四千九百六十七億零三百二十萬零五千三百七十六
    or    yī bǎi èr shí liù wàn qī qiān liù bǎi wǔ shí jīng líng liù qiān líng èr  wàn èr qiān bā bǎi èr shí èr zhào jiǔ qiān sì bǎi líng yī wàn sì qiān jiǔ bǎi liù shí qī yì líng sān bǎi èr shí wàn líng wǔ qiān sān bǎi qī shí liù

Input:    8749002899132047697490008908470485461412677723572849745703082425639811996797503692894052708092215296 3
Grouping: {[8749](0028'9913"2047'6974)9000'8908"4704'8546}[(1412'6777"2357'2849)7457'0308"2425'6398](1199'6797"5036'9289)4052'7080"9221'5296
Output  : 八千七百四十九京零二十八萬九千九百一十三億二千零四十七萬六千九百七十四兆九千萬零八千九百零八億四千七百零四萬八千五百四十六垓一千四百一十二萬六千七百七十七億二千三百五十七萬二千八百四十九兆七千四百五十七萬零三百零八億二千四百二十五萬六千三百九十八京一千一百九十九萬六千七百九十七億五千零三十六萬九千二百八十九兆四千零五十二萬七千零八十億零九千二百二十一萬五千二百九十六
    or    bā qiān qī bǎi sì shí jiǔ jīng líng èr shí bā wàn jiǔ qiān jiǔ bǎi yī shí sān yì èr qiān líng sì shí qī wàn liù qiān jiǔ bǎi qī shí sì zhào jiǔ qiān wàn líng bā qiān jiǔ bǎi líng bā yì sì qiān qī bǎi líng sì wàn bā qiān wǔ bǎi sì shí liù gāi yī qiān sì bǎi yī shí èr wàn liù qiān qī bǎi qī shí qī yì èr qiān sān bǎi wǔ shí qī wàn èr qiān bā bǎi sì shí jiǔ zhào qī qiān sì bǎi wǔ shí qī wàn líng sān bǎi líng bā yì èr qiān sì bǎi èr shí wǔ wàn liù qiān sān bǎi jiǔ shí bā jīng yī qiān yī bǎi jiǔ shí jiǔ wàn liù qiān qī bǎi jiǔ shí qī yì wǔ qiān líng sān shí liù wàn jiǔ qiān èr bǎi bā shí jiǔ zhào sì qiān líng wǔ shí èr wàn qī qiān líng bā shí yì líng jiǔ qiān èr bǎi èr shí yī wàn wǔ qiān èr bǎi jiǔ shí liù

Here is a reference implementation in JS, not golfed at all

Winning Criteria

As this is a code-golf, so shortest code measuring in bytes wins. Accented Latin alphabets and Chinese characters must be measured in UTF-8 unless they are included in the SBCS of the language and can be used in the string literals.

Reference

Wikipedia - 中文數字

Answer 20

Build a cardinal cyclic quine

A cardinal cyclic quine is a cyclic quine with four states, one for each orientation of the cardinal directions.

See also Build a half cardinal cyclic quine and Take a stand against long quine lines.

Rules

You can decide which rotation you want to implement, clockwise or counter-clockwise.

Once rotated, any gaps in your code should be replaced with spaces to preserve the positioning.

Each program must be unique, you cannot use a quine that has the same layout regardless of orientation.

Your program must satisfy the community definition of a quine.

This is code-golf so the shortest program in each language wins. Your first program is used for your byte count.

Standard loopholes are forbidden.

Examples

If your program is:

$_=q{print};eval

Then the next iterations must be either:

$
_
=
'
p
r
i
n
t
'
;
e
v
a
l

lave;}tnirp{q=_$

l
a
v
e
;
'
t
n
i
r
p
'
=
_
$

or

l
a
v
e
;
'
t
n
i
r
p
'
=
_
$

lave;}tnirp{q=_$

$
_
=
'
p
r
i
n
t
'
;
e
v
a
l

Or if your program is:

;$_=';
;$_=';
print

Then the next iterations must be either:

;;
''t
==n
__i
$$r
;;p

;'=_$;
;'=_$;
 tnirp

p;;
r$$
i__
n==
t''
 ;;

or:

p;;
r$$
i__
n==
t''
 ;;

;'=_$;
;'=_$;
 tnirp

;;
''t
==n
__i
$$r
;;p

---

quine source-layout code-golf

Answer 21

Safely check a password against HIBP v2 range API

code-golf

Per https://www.troyhunt.com/ive-just-launched-pwned-passwords-version-2/, what would be the shortest code to safely check a password against the Have I Been Pwned? k-anonymity (range) API, as mentioned in the article?

API overview

Specifically, the API is at:

https://api.pwnedpasswords.com/range/$FIRST_5_CHARS_OF_SHA1

and returns a list of SHA1 hashes beginning with the specified 5 chars (more precisely: it returns only the substrings of hashes after $FIRST_5_CHARS_OF_SHA1).

For example, given a password P@ssw0rd, its SHA1 hash is:

21BD12DC183F740EE76F27B78EB39C8AD972A757
\---/\---------------------------------/
  |                     |
  `-- first 5 chars     `-- rest of chars

and thus for a request like one of below:

https://api.pwnedpasswords.com/range/21BD1
https://api.pwnedpasswords.com/range/21bd1

the API gives a response like below (... represents more lines):

...
29B59205F57C2608CAE47E8157621FF7645:1
2B766777053A89201D8257221BBC161E279:2
2D10A6654B6D75908AE572559542245CBFA:2
2D6980B9098804E7A83DC5831BFBAF3927F:1
2D8D1B3FAACCA6A3C6A91617B2FA32E2F57:1
2DC183F740EE76F27B78EB39C8AD972A757:47205
2DE4C0087846D223DBBCCF071614590F300:2
2DEA2B1D02714099E4B7A874B4364D518F6:1
2E90B7B3C5C1181D16C48E273D9AC7F3C16:1
2EAE5EA981BFAF29A8869A40BDDADF3879B:1
2F1AC09E3846595E436BBDDDD2189358AF9:1
...

Existence of 2DC183F740EE76F27B78EB39C8AD972A757 in the response means that P@ssw0rd was found in some breach and should be considered unsafe. Number 47205 signifies how many times such a password occurs in all the contributing breaches.

Rules details

• The password must be read from user's keyboard. Per the next rule, it should not be displayed on screen, thus if read from standard input, usually the "character echo" would need to be disabled (e.g. read -s in bash). If implemented as a GUI app, e.g. a standard "password input" widget may be used, which would replace typed characters with asterisks or black dots.
• "Safely" means that the solution should not leak raw password to other users of a machine (e.g. the raw password should never appear as part of command line of any subcommand, and should never appear on screen) or outside the machine (websites, etc.). The full hash should not be shared outside the machine either.
  • Specifically, it must be clear (for an experienced user of the language) from the code comprising the solution that the raw password (and the SHA) do not leak (as mentioned above). So, for example, the solution's code cannot be downloaded from a remote repository (not sure if it's already included in default forbidden loopholes list).
• The SHA sum of the checked password should be printed on screen, to make it possible to verify correctness of the solution, e.g. by checking SHA sum for P@ssw0rd. Other hashes can be printed too or not, but the one matching the checked password must be easy to see (i.e. always first/last/highlighted/...)
• The solution should also display the number of occurrences of the password "in the wild" as returned by the API (i.e. 47205 for P@ssw0rd).
• The solution should print at least a 1 character of prompt before reading the answer, so that user knows console is safely in "no echo" mode.

Extra tag

To keep with the site's sport spirit, I'm putting no formal restrictions on language. However, personally I'm particularly interested in and curious about "real-world usable" answers. As such, if your answer has the following "extra" attributes:

• can be typed in bash as a one-liner (with appropriate preamble like perl -ne if needed)
• is composed only of printable ASCII characters (no Unicode)

please append an extra marker/tag like below in the "title" line of your answer:

[bash oneliner: 30 +7]

where 30 is the length of the actual code in your preferred language, and +7 is the length of the required preamble/postamble. For pure bash answers, this can be +0. Please then also include the actual oneliner, together with the preamble/postamble.

As an explanation, the benefits of a one-liner I'm interested in for "real world users", are such that a one-liner is easy to re-type and execute in console for paranoid users, who would prefer to do it instead of Ctrl-C & Ctrl-V.

---

Sample naive answer in bash

Split to multiline with \s purely for readability:

$ (sha=$(IFS= read -s -p "pwned? " pw; tr -d '\n' <<<$pw | shasum ); \
  curl -s https://api.pwnedpasswords.com/range/${sha:0:5} | \
  (grep -i ${sha:5} || echo "${sha:5}:0") | \
  sed "s/^/${sha:0:5}/")
pwned? 21bd12DC183F740EE76F27B78EB39C8AD972A757:47205

One-liner:

$ (sha=$(IFS= read -s -p "pwned? " pw; tr -d '\n' <<<$pw | shasum ); curl -s https://api.pwnedpasswords.com/range/${sha:0:5} | (grep -i ${sha:5} || echo "${sha:5}:0") | sed "s/^/${sha:0:5}/")
pwned? 21bd12DC183F740EE76F27B78EB39C8AD972A757:47205

Answer 22

Image to HTML ASCII-Art

---

Given an input image n, output each pixel as a 0 using HTML for coloring and <br/> as a delimiter for the rows.

---

Example:

Input Image:

Example HTML Output: https://pastebin.com/jDHZwb4P

Rendered Output:

---

Rules:

• You may color the 0's using any HTML trick you know of (CSS Style, JavaScript, etc)...
• You may use any character other than 0 that shows visible color if you so wish.
• Colors must be exact down to the RGB of the pixel, alpha can be assumed non-existent.
• If you get a malformed image, or an image with transparency, you may error.
• This is code-golf, lowest byte-count wins.

Answer 23

Find most isolated point

code-golfmathgeometrygraph

Given a finite set S of points in d dimensions, find the most isolated points, that is the point with the greatest distance to its closest neighbours.

Or more mathematically, the point p ∈ S that maximizes min {d(p,q) | q ∈ S, q ≠ p}.

Details

• You can return the coordinates of the actual point, or you can alternatively return the index of the point in the input list.
• The most isolated point as defined above is not necessarily unique. But you can assume that the given input results in an unique such point.

Examples

1D:

• [0,1] (invalid, no unique result)
• [0,1,3] -> 3,

2D:

• [(0,0),(0,1),(1,2)] -> [(1,2)]

more to be added...

This challenge was inspired by this question. If you find a particularly time-efficient solution please post it there!

Answer 24

Implement RaGOL code-golf cellular-automata grid random

RaGOL (Random Game of Life) is a randomized cellular automaton based on GOL (Game of Life). For reference, here are the rules of GOL (B3/S23):

• Moore neighborhoods are used, that is, a cell # looks at its neighbors * as in here:

  .......
  .......
  ..***..
  ..*#*..
  ..***..
  .......
  .......

• A cell can have 2 states: dead or alive

• If a dead cell has 3 alive neighbors, it becomes alive.
• If an alive cell does not have exactly 2 or 3 alive neighbors, it becomes dead.

In this challenge, we will assume the board is unbounded, and the default state of a cell is dead.

However, since we have already implemented GOL, it's time to change the rules a bit. Here are the differences between GOL and RaGOL:

• If a dead cell has 3 alive neighbors, there is 1/3 of a chance it becomes alive.
• If an alive cell has 2 alive neighbors, there is 1/5 of a chance it becomes dead.
• If an alive cell has 3 alive neighbors, there are 2/5 of a chance it becomes dead.

Note that if an alive cell doesn't have exactly 2 or 3 alive neighbors, it still becomes dead just like in GOL.

Challenge

Your challenge is to get an x×y RaGOL board B where x > 0 and y > 0 and a number N > 0 and return the board after N generations starting from B.

Please note that the result isn't deterministic.

You will also need to expand the board to simulate an unbounded-board automaton in some cases.

Rules

• You can get B and N in any reasonable way.
• Errors due to floating-point imprecision do not matter, be it a slight difference due to how floats work or a precision limit of the float datatype you use. Otherwise, you must adhere to the aforementioned probabilities.
• You may expand the board as much as you like, as long as 1) the result will be theoretically returned at some point in time and 2) the whole expected result is shown.
  • Note: If your language has a board datatype which natively supports unbounded boards, you can use that instead of manually expanding the resulting board, as long as the correct result is returned sometime. You may also use third-party modules which provide such a datatype, or even implement your own, just as long as there is an implementation available online!

Answer 25

Square Number Chains

Background

Given a positive integer n >= 25, it is conjectured that there exists a permutation of the positive integers which are less than or equal to n in which every adjacent pair of numbers adds up to a square number. There are also several numbers less than 25 that this is also true for - 15, 16, 17, and 23.

The Challenge

Write a program or function which accepts a positive integer, n, and returns all positive integers less than or equal to n, ordered such that each adjacent pair adds up to a square number. If there are multiple valid orderings, only one needs to be returned, but your program must be deterministic - that is, for a particular input, your answer should return the same output every time.

You can assume that the input will always have at least one solution, so you don't have to deal with inputs 1-14, 18-22, or 24. If you prefer, you can require that input to your submission will always be greater than 24 - if so, please specify in your submission.

Output may be in the form of a list, or written to STDOUT, so long as there is a consistent and identifiable seperator between them - for example, a space, newline, comma, tab, etc are all fine.

You can validate your program's output by using this TIO link. It supports input as a string with any consistent separator, and will tell you what criteria (if any) your list is failing on.

Inspiration

The Square-Sum Problem - Numberphile

Test cases

Input    Example output
15       9,7,2,14,11,5,4,12,13,3,6,10,15,1,8
23       18,7,9,16,20,5,11,14,2,23,13,12,4,21,15,10,6,19,17,8,1,3,22

Winning Criteria

This is code-golf, so the shortest answer in bytes will be the winner! Good luck and happy golfing!

---

TODO

-More test cases

Feedback requested:

The Python program I've thrown together to provide solution verification is probably a bit shonky, I'm not that strong a Python programmer. If anyone has any comment/criticisms feel free to let me know, or improve it yourself!

As has been pointed out that this challenge is similar to a few others which ask for a Hamiltonian cycle. In my opinion this is suitably different, as this is looking for a Hamiltonian path, and the input is far simpler than the other challenges. What do people think?

Answer 26

The Challenge

The goal is to write a complete program that prints out every possible tetris block made up of #.

The blocks must have an equal chance of printing in any order and must appear exactly once each. The blocks may have any rotation, rotation may be consistent between executions. No two blocks can be touching. All blocks must have settled on the "floor".

ValidExample.exe
                    #   #
## ###      ##   ## #   #
##  #  ####  ## ##  ## ##

TouchingExample.exe
      #
      #  # ##
## ####  #  # ##   ## 
##  # # ##  #  ## ##   

FloatingExample.exe
       #   #             
## ### ## ## #     # ####
##  #   # #  ### ###     

Use the language of your choice, lowest number of bytes wins

Questions

• Is the wording clear enough?
• Does the challenge meet the expectations for a challenge here?
• What can I do to remove any ambiguity if there is any?
• Is the formatting for the question / examples ok?
• Would the challenge be "better" if the blocks had to be made up of their corresponding letter (IOJLZST)

Answer 27

Hyperprogramming: X×Y, X^Y, X^^Y all in two

code-golf math number arithmetic source-layout, just like the original.

Heavily inspired by Hyperprogramming: N+N, N×N, N^N all in one.

Your task is to write two programs so that they compute different hyperoperations when they are placed in relation to each other in the form of the mathematical notation for that hyperoperation.

Full rules:

Write two rectangular programs of the same size — call them "program A" and "program B" — that each take a single positive integer as input and output that integer. In this case, "rectangular" means that every line is the same length, and that there is no trailing newline. Thus, your two programs will each be composed of M lines of N bytes each.

The catch is that when the two programs are placed next to each other in various positions, they will act as a single program that takes two positive integers, X and Y, as input and outputs either X×Y, X^Y, or X^^Y (tetration), depending on the position. Moreover, when the locations of the two programs are reversed, the resulting program will print Y×X, Y^X, or Y^^X — e.g., with X and Y reversed.

The precise location of the two programs with respect to each other is determined by the notation for that particular operation. For instance, if your program A reads

*this* is
program A

and your program B reads

*this* is
program B

your program to output X×Y must contain both program's source codes placed horizontally adjacent without any filler inserted, like so:

*this* is*this* is
program Aprogram B

Because multiplication is commutative, both [AB] and [BA] must function identically.

Your programs to output X^Y and Y^X must contain the code of programs A and B in the locations [ᴀᴮ] and [ʙᴬ], with spaces padding the "exponent" program to the correct horizontal position and optional trailing spaces after each line of the "base" program to pad the layout into a rectangle — no partial padding allowed, it's all or nothing. Padding must be consistent for both X^Y and Y^X (as well as X^^Y and Y^^X later). Illustrated without trailing spaces:

         *this* is
         program B
*this* is
program A

and

         *this* is
         program A
*this* is
program B

Finally, your programs to output X^^Y and Y^^X must contain the code of programs A and B in the locations [ᴮᴀ] and [ᴬʙ], with spaces padding the "base" program, and trailing spaces after each line of the "superexponent" program to pad the layout into a rectangle if and only if your X^Y and Y^X programs included trailing spaces as padding. Illustrated without trailing spaces:

*this* is
program B
         *this* is
         program A

and

*this* is
program A
         *this* is
         program B

You do not have to support arbitrarily large integers, but your answer should work for a reasonable range of X and Y — that is, it should probably at the very least support all combinations of X and Y up to 3 except maybe 3^^3 = 7625597484987.

Source code reading is allowed, as it would be very difficult to otherwise distinguish X^Y and X^^Y in many languages.

As this is code-golf, fewest bytes wins.

Note: your score is the total byte count of a single one of your original two programs, not any of the hyperoperation-computing ones — for example, if your programs A and B are each 5×5, your score will be 5×5 + 4 newlines = 29. Since both programs A and B will have identical byte counts, it doesn't matter which one you pick.

Is there anything unclear about this? If so, how could I fix it?

Answer 28

Sandbox Notes

• Which tags should go?
• Is this uncomputable?
• Should I add more test cases?

Solve logical statements about arithmetic

math logic number number-theory arithmetic integer decision-problem code-golf

^{Ok, some of these need to go.}

Your task is to determine the truth or falsehood of boolean statements about integer expressions.

Integer Expressions:

• 1 is an integer expression.
• If a is an integer expression, then (-a) is an integer expression representing its negative.
• If a and b are integer expressions, then (a+b) and (a*b) are integer expressions representing their sum and product, respectively.
• A string of lowercase Latin letters is an integer expression if it is in scope. A value in scope in an integer or boolean expression is always in scope in all of its subexpressions.

Boolean Expressions:

• If a and b are integer expressions, then (a>b) is a boolean expression representing whether a is greater than b.
• If a and b are boolean expressions, then (a&b) is a boolean expression representing whether they are both true.
• If a is a boolean expression, then (!a) is a boolean expression testing whether a is false.
• If v is some string of lowercase letters, and e would be a boolean expression if v was in scope, then (v^e) is a boolean expression that represents whether e is true for any integer value of v.

Task

You will be given a boolean expression in any reasonable format (such as a string or a parse tree). You should output one of two distinct outputs depending on whether this boolean expression can be shown to be true or false.

Test Cases

(x^(!(y^(x>y)))) => True

Read: for all x, it is not the case that any y is less than x.
In other words, there is no number greater than all other numbers.

(!(x^(!(y^((y*y)>x))))) => True

Read: there is a number x which is less than the square of any y.
In other words: there is a number smaller than all squares (any negative number).

(x^(x>5)) => False

Read: all numbers are greater than 5.

(!(x^(!(x>x)))) => False

Read: it is not the case that all numbers are not greater than themselves.
In other words: there is a number greater than itself.

(y^(x^(!((!(y>(2*x)))&(!((2*x)>y)))))) => False

Read: for every two integers x and y, y is neither greater than nor less than 2x.
In other words: there is no number divisible by 2.

(x^((x*x)>x)) => False

Read: all numbers are less than their squares.

(x^(!(x>(x*x)))) => True

Read: there is no integer greater than its square.

Answer 29

Antigerrymandering

code-golf map set-partitions

From this question:

The United States has a unique love of gerrymandering––the deliberate manipulation of an electoral district to predict certain voting results. Just recently there was a gerrymandering case brought before the Supreme Court. Gerrymandering, especially when related to race, is ruled illegal and results in the requirement to redraw the district lines.

Gerrymandering has recently been getting even more attention in the news due to this year's congressional elections. Wouldn't it be nice if we could all decide on a simple, nonpartisan way to determine congressional districts?

Your task is to fix settle this discussion once and for all with a determinate program to partition a map into districts.

What you gotta do

Write a program or function that takes a positive integer n and a map (described below) and partitions the map into n contiguous districts of equal population (as nearly as possible) while minimizing the total length of the districts' borders.

The map

The map is a two-dimensional, rectangular matrix of one or more integers, each integer representing the population of its cell. This can be in any convenient format—an array of arrays, a stream of numbers, or even a JPEG, if desired! You are allowed to take the dimensions of the map as additional inputs.

The borders

Each cell in the map is to be treated as a square of side length 1. Total border length is the sum of the lengths of all edges of cells that are also the edge of a district. Note that this will necessarily include the entire perimeter of the map.

The partition

The n districts must have the lowest possible maximum difference in population from total population / n. In the case of a tie, they must have the lowest possible total border length, ensuring compact districts.

Take the following map:

1 5 7 8
7 4 2 5
8 5 3 5

It has total population 60. To divide it into two districts, each must have population 30. Additionally, each district must be orthogonally contiguous. Both of the following accomplish just that:

1│5 7 8
 └───┐
7 4 2|5
     │
8 5 3│5


1 5│7 8
   │
7 4│2 5
   │
8 5│3 5

Of these two partitions, the upper has total border length 14 (perimeter) + 5 (border) = 19, while the lower has length 17. Of these two options (and the other one I can see at the moment, the vertical line down the middle is to be chosen, since its border length is the lowest.

Now consider:

2 1 2

This again has two possible partitions into two districts, but these are tied in border length. Your program or function can return either partition, but it must return the same one each time.

Output

Lots of options. A string using one non-numeric character for border and another for no border. An array of numbers, with a surjection to the sixteen possible states of a cell's edges. A JPEG, with borders shaded. A pirate's map: "3 steps south. 2 steps east..." Really, anything that can be mapped to a partition. The output format must be consistent.

This is code-golf, so the shortest solution (in bytes) in each language wins!

---

Sandboxy stuff

Any clarification needed?

I'm making some test cases (based on real states' population distributions!); these'll be added soon.

Anything else worth mentioning?

Thanks!

Answer 30

Find the Intersection code-golf geometry

Challenge

Given some planes in an n-dimensional space, return the intersection of these planes with the highest degree, if it exists.

Details

You will be given two integers, n and k, such that 0 < k ≤ n and 1 < n. You will also be given (n-k) hyperplanes within the space Rⁿ. (A hyperplane in the space Rⁿ has (n-1) dimensions.) Your task is to find the intersection between them that has the highest number of dimensions, if it exists. This intersection will have at least k dimensions; it may have more than k dimensions if the inputs are not independent.

For example, if we are working in the 3-dimensional space (R³), you would be given planes with 2 dimensions. If you are given 3 distinct planes, you would at best be able to find a single point where they all intersect (0 dimensions). If you are given 2 distinct planes, you could find a line where they intersect (1 dimension). Et cetera.

Input format

You may choose any standard format to represent hyperplanes in Rⁿ. Here are two formats that I suggest:

1. v_n = c₁v₁ + c₂v₂ + ... + c_n-1v_n-1 + c_n, where v represents a variable and c represents a scalar constant.

2. c₁v₁ + c₂v₂ + ... + c_nv_n + c_n+1=0.

For example, consider the plane z=2x-3y in R³. In format 1, I would write this as v₃=2v₁-3v₂+0, so my program would take in the tuple of scalar constants (2, -3, 0). In format 2, I would rewrite this as 2x-3y-z+0=0, and similarly take the tuple (2, -3, -1, 0). You can choose one of these two formats or another standard format, so long as you provide details in your answer.

You may take in n and k explicitly if you wish, though you should be able to determine both from the list of planes (k is the number of planes, n is one more than the number of dimensions in a plane).

Output format

You should output a single plane in the same format as your input. If no intersecting plane exists, you should return something recognizably distinct from other valid outputs of your program (such as an empty tuple, false, a thrown exception, etc.).

Test Cases

These use suggested input format 1, with n and k provided implicitly.

[(c₁, c₂, ..., c_n), (...), ...] => (c₁, c₂, ...)

In R³, the intersection of z=-3x-2y, z=5+2x+3y, and z=-x-y-1 is the point (2, -3, 0)

[(2, 3, 5), (-3, -2, 0), (-1, -1, -1)] => (2, -3, 0) // This doesn't work

In R³, the intersection of z=4x+y and z=x+2y+1 is the line y=3x-1

[(4, 1, 0), (1, 2, 1)] => (3, -1)

Scoring criteria

This is code-golf, so the shortest answer in each language wins.

---

Meta

Can you follow the goal of the challenge and the details I've provided? I've tried to be as clear as possible, but I think I may have been too verbose.

I think my output format needs to change - there's no way to represent a point in Rⁿ the way I've phrased it...any suggestions?

More test cases coming soon.