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

n-gon in m-gon

code-golfgeometrymath

What is the greatest equilateral triangle you can fit into a regular pentagon? This is what this challenge is about, but with regular n-gons/m-gons.

Challenge

Given two integers m,n greater or equal to 3, find the maximal ratio of the areas of the two polygons such that the m-gon is completely contained in the n-gon.

Details

We are always talking about regular polygons, this means that all sides have the same length and all vertices are on a circle. The output can be a floating point-, fixed point- or rational number and must be correct to three decimal places.

Examples

 m  n  ratio (area m-gon / area n-gon)
 x  x  1 (for all x)
 3  4  1/4*sqrt(3) = 0.4330
 4  3  12/(7*sqrt(3)+12) = 0.4974
 3  6  1/2 = 0.5
 6  3  2/3 = 0.6667
 

Would be nice to have larger examples.

Answer 2

Got Your PIN!

code-golfcombinatorics math sequence

I bet I can write down your PIN! 0000 0001 0002 0003 ... 9999.

Task: Write a program that outputs a string containing all possible four digit PINs.

The string should not contain any whitespace (trailing newline is okay).

Score: Length of program (in bytes) + length of output.

Explanation

The output string only needs to contain each PIN somewhere in it; digits can be reused. For instance the string “123456789” contains the PINs 1234, 2345,3456,4567,5678,and 6789. By reusing digits, it's possible to save a significant amount of space from the naive implementation (0000000100020003...9999).

At best, this could be written as a 10,003 digit string. 4 digit for the first PIN, then one more digit for the other 9999 PINs.

Testing your code

I've written a basic Python script that can check your solution and indicate any PINs you are missing.

import sys
s = sys.stdin.readline()
passes = True
for ix in range(10000):
    pin = "%04d" % (ix)
    if s.find(pin) == -1:
        print("Missing PIN %s" % pin)
        passes = False

if passes:
    print('Result passes!')
print('String length is %d characters.' % len(s))

Answer 3

Roll identical boson dice code-golf random

When you roll two dice, the chance of a 5 and 6 in either order is a 2 in 36 (or 1/18), since it could happen as (5,6) or (6,5). But (6,6) can only happen one way and has a 1 in 36 chance.

Our dice will instead work as identical bosons: (5,6) and (6,5) are a single outcome {5,6} that is equally likely to {6,6}. So, each of these 21 unordered pairs is equally likely, with chance 1/21.

{1,1}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,2}, {2,3}, {2,4}, {2,5}, {2,6}, {3,3}, {3,4}, {3,5}, {3,6}, {4,4}, {4,5}, {4,6}, {5,5}, {5,6}, {6,6}

Similarly, for 3 dice, [5,5,6], [5,6,5], and [6,5,5] all count as a single outcome {5,5,6}, but [6,5,6] is different.

Task: Output a random roll of n boson dice, so that each possible result is equally likely as an unordered multiset, i.e. when sorted.

It's OK if your output is ordered as long as the overall probabilities are right. You may sometimes output [5,6] and sometimes [6,5] as long as their total chance is 1/21. They don't have to each be 1/42 chance. You could output [5,6] with 1/21 chance and never [6,5].

Input: A positive integer n

Output: A random list of n numbers from 1 to 6, so that each outcome is equally like when taken as an unordered multiset.

Time restriction: Your code has work up to n=50 within 1 minute.

Answer 4

Limited-Information Maze-Solving Bot

(Still in draft/beta format. Feedback welcome.)

code-challenge maze

Based on a challenge idea I posted in chat and the ensuing conversation. Thanks to NathanMerrill, zgarb, and Jonathan Frech for assistance in fleshing this out.

The challenge

You're writing two separate programs/functions/routines/etc. The first, which we'll call the helper program, takes the input maze and calls the second, which we'll call the solving bot. The solving bot must solve the maze based on its interaction with the helper program.

The maze is 51x51 characters in size. For clarity in this challenge description, it is composed of # walls and corridors, but you can use any two distinct, consistent ASCII characters of your choice. E.g., use ! for walls and x for corridors, use 1 for walls and 0 for corridors, etc. This maze is one of many that will be the input to your helper program/function.

The maze start is always guaranteed to be somewhere on the left-most column, and the exit is always guaranteed to be somewhere on the right-most column. The maze is guaranteed to have at least one path from the start to the exit. As a result of this construction, the very top row and very bottom row are all #, and the very left and right columns are all # except for the start and exit.

The solving bot that you're creating needs to find a solution to the maze (not necessarily the shortest), but is limited in that it can only "see" a new 5x5 section of the maze at a time. The bot is scored by how many times it needs to request a new 5x5 section from the helper program/function.

The upper bound is obviously to simply request every possible 5x5 section, for a score of around 100. The lower bound is where someone with perfect knowledge of the maze can request only those 5x5 sections containing the exact route of the shortest solution, possibly as low as 10. Your bot will be run through (1000?) different mazes, and the bot with the fewest total requests will be the winner.

The solving bot is placed on the left-hand side where the start is, and the first 5x5 section is provided for free. However, the bot doesn't know where, vertically, it is on the left-hand side of the maze. It could be in the top corner (as in the example below), in the bottom corner, or anywhere in between.

Input/Output

The code you're writing be required to take the maze as an input (STDIN, a file to read, etc.) and call a subroutine of some sort for the solution bot.

Input: (1000?) 51x51 mazes Output: How many total requests your solving bot took

Yes, this is a non-observable requirement to be on the honor system and ensure the two "halves" of your program (i.e., the I/O half and the solving half) talk to each other correctly and accurately. I trust the community enough to believe that this is OK.

Further rules

Your solving bot should be deterministic. That is, when presented with the same maze two or more times, it should request the same number of 5x5 sections.

Example Maze

(generated from http://www.delorie.com/game-room/mazes/genmaze.cgi )

###################################################
            #     # #   # #   #   #         #   # #
# ######### ##### # # # # # # # # # ####### ### # #
#   #       #   #   # # #   # # #         #   # # #
### # ####### # # ### # ### # # ############# # # #
#   #   #   # # #   # #     # #   #   #   # #   # #
# ####### # ### ### ####### # ### # # # # # # ### #
#     #   #       #       # # #   # # # # # # #   #
##### # ################# # # # ### ### # # # # ###
#   #       #     #         # #         # # # #   #
### ####### ##### # ######### ##### ##### # ##### #
#   #           #   #       #     # #   # #   #   #
# ##### ### ### # ### ########### # # # # # # ### #
#       # # #   # # #   #         # # # #   # #   #
######### # ### # # ### # ######### # ##### # # ###
#       # #   #   # # #   #       # # #     # # # #
# ##### # ### ##### # ##### ##### # # # ##### # # #
#     #   #       # # #   #     # #   # #     # # #
### # ####### # ### # # # ##### # ### # ####### # #
#   #     #   #   # #   #   #   #   # # #         #
# ####### # ##### # ####### # ### # ### # ### # ###
# #     # #     # #       # # #   #   #   #   #   #
# # ### # ##### # # ####### # # ##### ####### ### #
#   #   #       # #     #   # #     #   #   # # # #
##### ########### ##### # ########### # # # # # # #
# #   #       #   #   # #       #   # # # # #   # #
# # ### # ##### ### # # ### ### # # # ### # ##### #
#   # # #       #   #     # # #   # #   # #   #   #
##### # # ##### # ##### # # # ##### ### # ### # ###
#   # # #     # #   #   # #   #         #   # #   #
# # # # ##### # ### # ### ##### ### ##### # # ### #
# # #   #     #     # # #         #       # # #   #
# ####### ########### # ############### ##### # ###
#     #   #   #       #             # #   #   # # #
##### # ### # # ####### ######### # # ### # ### # #
#   #     # # # #       #       # #   #   # #   # #
# ##### # ### # # ######### ### ##### # ### # ### #
# #     #   #   #     #   # #   #     # #   #     #
# # ####### ######### # # # ##### ### # # ##### ###
# # # #     #     #   # # #     # # #   #     #   #
# # # # ######### # ##### ##### # # ##### ### # # #
#   #   # #     # # #     #   #     #   # #   # # #
### ##### # ### # # # ### # # ####### ### ### # # #
# #     # # #   # # # #   # #       #       #   # #
# ##### # # # ### # # ##### ####### ####### ##### #
#       #   # #   # #       # #   # #       #   # #
### ######### # # # ######### # # # # ####### # # #
#   #   #   # # # #   #         #   #     #   #   #
# ### # # # # # ##### # ####### ########### ##### #
#     #   #   #       #       #             #      
###################################################

Example starting block:

#####

# ###
#   #
### #

Answer 5

Type the alphabet as fast as you can

Your task is to make a program that measures how fast you can type the letters of the English alphabet.

• The program shall only accept lowercase letters a to z in alphabetical order.
• Each letter is echoed as typed on the same line (without new line or any other separators between letters).
• If you type an invalid character the program shall output Fail and exit.
• If you type all 26 letters the program shall output the time in milliseconds it took from the first to the last letter and exit.
• The timer starts when you type the first letter, a.

Example outputs:

b
Fail

abcdefgg
Fail

abcdefghijklmnopqrstuvwxyz
6440

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

Answer 6

Stable modular exponents

coge-golf math number-theory

It is well-known that the final three digits of Graham's number are 387. This is because Graham's number is a ridiculously tall exponent tower of threes: 3^(3^(3^...))), and it can be shown that any such tower of height at least 5 has 387 as its final three digits.

This generalises: given any base n and any starting number a, the exponent tower a^(a^(a^...))) will eventually stabilize modulo n. After that point, whatever you put in the topmost exponent, be it just a last a, or a continuation of the exponent tower (i.e. more than one a), or any other number, its congruency class modulo n will not change. That is the challenge that I set before you here today.

Problem statement

Write a program or a function that takes two numbers a and n (within your language's standard signed or unsigned integer range) as input, and outputs the limit l of the sequence a%n, (a^a)%n, (a^(a^a))%n,..., which can be mathematically proven to be eventually constant (and therefore have a well-defined limit).

Your program should be able to handle a > n (note that a and a+n doesn't necessarily give the same result), and we require that 0 <= l < n.

Warning: Reducing the exponents mudulo n, i.e. calculating this sequence recursively using b[0] = a%n, b[i] = (a^b[i-1])%n will yield the wrong result, and might not stabilize.

Test cases

If we call the function f(a, n), it should give the following:

> f(3, 1000)
387
> f(6, 10)
6
> f(5, 9)
2
> f(14, 9)
4
> f(3, 81)
0

Scoring criteria

Standard code golf rules, use as few bytes as possible.

Answer 7

Voronoi Iteration

code-golfmathgeometry

Given a finite set of points in the plane, output the set vertices of the corresponding Voronoi diagram.

Details

A vertex of the voronoi diagram is a point of the plane that has the same distance to the three or more closest input points. As usual, you don't have to worry about the rounding issues of limited precision floating point numbers.

Examples

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

Inspired by this question on MO.

Answer 8

Invisible target - probability KotH

king-of-the-hill game grid probability-theory ?

---

In short

Walls are gradually added and the player nearest to the stationary invisible target at the end of the game wins.

---

Detail

Players are all present on a 32 by 32 grid of square cells, which wraps toroidally. One randomly chosen cell is the target, which is not indicated to any of the players (regardless of whether they are on that cell or not). The target does not move.

Players all take their turn simultaneously. After each turn there is a small chance of a wall being added.

Wall rules

• The wall will never be placed on a player.
• The wall will never be placed in a cell that does not have a route to the target.
• Of the possible positions for the wall to be placed, one will be chosen uniformly pseudorandomly.
• The probability of a wall being placed each turn is 1/7.
• The wall will be placed such that every player still has a route to the target (this includes never placing a wall on the target).

Note that a player having a route to the target means that there exists a path that does not include a wall. If another player blocks the path it still counts as a path.

Movement rules

• A player can move to any of the 4 orthogonally adjacent cells (or stay still).
• A player cannot share a cell with another player.
• A player cannot move onto a wall.
• A player can move onto the target, but will have no way of knowing that this has happened.

Starting position

At the start of the game the arena will have no walls and the players will be randomly positioned with the guarantee that there are no other players within each player's 5 by 5 neighbourhood.

Winning

Play will continue until no wall can be placed for 10 consecutive attempts (note that attempts only occur with probability 1/7 each turn so this will take more than 10 turns). When play stops the player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many, and in most cases there will be a player on the target cell, meaning only a single winner.

Each of the (one or several) joint winners scores one point. Games will be played until one player is the clear winner, or until it is clear there should be joint winners overall.

---

Input and output

Input

During an N player game the input will be a space separated string of N+1 integers received on STDIN:

• The player's position (an integer).
• The position of any wall added since the player's last turn (an integer).
• The position of every enemy player (N-1 integers).

Positions will be single integers from 0 to 1023, representing the distance in English reading order from the top left cell.

For a 4 by 4 arena this would give the following numbering:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

If no wall was added the wall location will be 1024.

During a particular game the order of enemy players will be consistent - the nth location will always refer to the same enemy player.

Output

The player must send an integer from 0 to 4 to STDOUT representing a move in English reading order:

  0
1 2 3
  4

(2 being no move).

A move to an unoccupied cell will not necessarily succeed - it will fail if another player is also trying to move to the same cell.

A move to an occupied cell will not necessarily fail - it will succeed if that player is also moving away from that cell (provided that player succeeds in moving away from that cell, and no other player is also trying to move to that cell).

This means two players can swap cells if they both decide to on the same turn.

A player taking longer than 50 milliseconds to respond will not move.

---

Sandbox questions

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

• Alternative adversarial 2 player version: One player is the target, and the other player is seeking the target. Each player can move one square orthogonally or stay still. Walls are added as in the multiplayer game, and the game ends when the seeker moves onto the target's cell. The score of each player is the number of moves the game lasted. Lower score is better for the seeker player, higher score is better for the target player. The target can always see the location of the seeker. The seeker can never see the location of the target. Might also be interesting to allow both players to choose where to place a wall on their turn (in addition to moving). This might open up the possibility of double bluff. Walls would still be prevented from being placed on a cell that doesn't leave a path from seeker to target. Would this be more/less interesting than the multiplayer version? Are they sufficiently distinct to post as separate challenges, or should one be chosen as the one to be posted? Would this adversarial version work best as two KotHs that use each other's answers to judge their own answers (like a cops and robbers challenge) or should all the seeker answers and target answers be posted to one challenge? Alternatively each answer could be required to deal with being either a seeker or a target, but I like the idea of people being able to specialise and build just one or other, without being obliged to write both.

Answer 9

Number rewinder

Inspired by this SO question and little bit expanded.

Your task is to rotate left a given integer by one digit in a given base and return integer (move the MSD to the LSD position).

Input: Two integers Number > Base > 1
Output: Result

Test cases:

Number Base  Result  String representations
61453   10    14536  61453 -> 14536
61453   16      223  F00D -> DF (00DF)
61453    8   229481  170015 -> 700151
60429   16    49374  EC0D -> C0DE
62977   16    24607  F601 -> 601F

This is Code-golf, standard loopholes are forbidden and shortest answer wins.

Answer 10

The Programming Language Quiz, Mark II - Cops

Answer 11

How acceptable is it to base challenges off of pre-existing challenges? I saw the challenge for Your Own Pet Ascii Snake and had a thought about making the output look more 'snakelike' by printing the characters |,\,/,(,),_ instead of always using the + character.

Here's how it would work. You would get some positive, negative, and 0 numbers as input, and based on those numbers, the snake moves one row down and that many characters in that direction. So, for a snake like the ones in the previous problem, your array would be restricted to the numbers 0, 1, and -1.

Here are the rules to draw the snake, the characters you print are dependent on the spacing of the lines before and after it.

So, say your snake is at position n (in the previous problem, n=30 to start, in this one you need to figure out a number for n that will keep your entire snake on the screen),

if the input is 0 you print n-1 spaces and a |
if the input is +1 you print n spaces and a \
if the input is +2 you print n spaces and \_, +10 would be \_________ (9 _ and a backslash)
if the input is -1 you print n-2 spaces and /
if the input is -2 you print n-3 spaces and _/, -10 would be _________/

Here's an example snake based on this array [+4, -3, +1, -4, +2, -3, +2, +5, -4, -1, -2, 0, +4, -4]

                        |
                         \___
                          __/
                          \
                       ___/
                       \_
                      __/
                      \_
                        \____
                        ____/
                       /
                     _/
                    |
                     \___
                     ___/

I could also add optional 'curvy' rules that would include the '(' and ')' characters on direction changes to produce a snake like this, based on the same array above:

                         |
                         \___
                          ___)
                         (_
                       ____)
                      (__
                      ___)
                     (__
                        \____
                        _____)
                       /
                     _/
                    (
                     \___
                     ____)

note that for the curvy snake, 0s are handled differently depending on if there is a direction change in the rows above and below them, here there is a negative, 0, positive pattern, so we use a '(', if there were no direction change we'd use a |, and in the opposite pattern, a ')'

There are spaces to the left of my example snake because I didn't want to count out how many spaces I should leave exactly, I don't know whether it should be mandatory to cut out extra whitespace to the left, or whether to let people have as much or as little whitespace as they want, provided that their snake doesn't 'go off screen'

Answer 12

The TI series of calculators. I've put a lot of hours in writing TI-BASIC programs. The single most tedious part was either scrolling through the program, or switching between alpha and numeric input.

For those unfamiliar, the entire Latin alphabet is overlaid on the existing keys alphabetically, and to type any of them (For variable names or assembly programming), you had to first press the ALPHA key, then your desired letter. Alternatively, you could press 2ND, A-LOCK and type in any number of letters, before pressing ALPHA again for numeric input.

Why am I saying all this? I want to write a code golf like challenge where scoring is done with this tediousness in mind, like switching between numbers/punctuation and letters carrying an extra penalty.

My original idea is that the source code of the submission would be converted to hexadecimal, and the number of transitions between alphas and numerics would be the "score," with a lower score being better.

How can/should I better refine this scoring system, and what sort of challenge should accompany it?

The Challenge

Implement a program or function, in the language of your choice, that takes a string of characters as input and outputs that string's "tediousness score."

How tediousness is scored:

1. The string is converted into its hexadecimal representation. This is Unicode for languages that don't specify, but for a language like, say, Jelly, the Jelly codepage is used.
   "The quick brown fox jumps, over the lazy dog's back." in Unicode == 0x54686520717569636b2062726f776e20666f78206a756d70732c206f76657220746865206c617a7920646f672773206261636b2e
2. Each switch between numbers and letters in the hexadecimal representation is counted.
   0x54686520717569636b2062726f776e20666f78206a...
..0 12 34 56 78 9...
3. This is your tediousness score. For this example, it is 25.

Standard loopholes apply.

Should I change the tediousness score? How might I implement golf? I thought about adding/multiplying the two together, but it still seemed to be in favor of just plain golfing. I wanted to make golfing languages be a bit harder for a golfing challenge, since they really pack their character sets and there would be a high "tediousness score".

Is the challenge, as written, clear enough? Should I restrict or relax the I/O requirements?

Answer 13

Signed exponentiation

code-golf math

---

Let us define signed exponentiation of a base x to a power n as this procedure:

1. Take the absolute value of x.
2. Raise to the power of n.
3. Re-apply the original sign of x.

Or, for a more mathematical (albeit slightly flawed) definition:

For this challenge, we will denote the signed exponentiation of x to a as x ' a. Some notes:

• Unlike f(x) = x^a, f(x) = x ' a is defined for negative x no matter the value of a.
• The negative portion of the graph of x ' n is the positive portion rotated halfway about the origin; hence, f(x) = x ' a is an odd function for all values of a.
• If a is odd, x ' a = x^a for all values of x.
• x ' 1 = x, while x ' -1 = 1 / x. x ' 0 is a sign function (+1 for positive x, -1 for negative x).

Challenge

Given a base x and a power n, compute x ' n.

Rules

• You may assume that -9 ≤ x, n ≤ +9.
• You may assume that x ≠ 0, for the sake of avoiding 0 ' 0, 0 ' -1, etc.
• You may assume that 1e-4 ≤ |x ' n| ≤ 1e9.
• The output must be precise to at least 3 significant digits for the given test cases.
• Input/output may be taken/given in any standard format.

Test cases

x, n -> output
1, 0 -> 1
3.14159, 0 -> 1
-9, 0 -> -1
7, 1 -> 7
-1.23456, 1 -> -1.23456
5, 2 -> 25
-4, 3 -> -64
0.1, 4 -> 0.0001
-9, 9 -> -387420489
1, -1 -> 1
-3, -1 -> -0.33333
5, -2 -> 0.04
2.71828, -9 -> 0.0001234
4, 0.5 -> 2
-2, 0.5 -> -1.41421
2, -0.5 -> 0.7071
3.8236, -1.6702 -> 0.10645
0.1, -9 -> 1000000000

Scoring

This is code-golf, so the shortest code in bytes in each langauge wins.

---

Sandbox questions

• Could the definition be improved?
• Too many test cases? Are there any important ones missing?
• Any issues with the rules?

Answer 14

Inversion languages

cops-and-robbers language-design

Cops

For this challenge you will design two languages, A and B. Both A and B should be Turing equivalent¹. When run in your two languages a program has four options:

1. It halts in both A and B.

2. It halts in A but not B.

3. It halts in B but not A.

4. It doesn't halt in either A or B.

Your goal is to try to design A and B such that as many programs as possible halt in exactly one language (options 2 and 3). Doing such for all programs is impossible², thus there will always be programs that meet either criterion 1 or criterion 4. The robbers will attempt to find these programs.

Further rules on languages

Since we are only considering whether programs halt or not we don't care about I/O. Because of this programs should not take any input. You may produce output but really doesn't matter because it can neither hurt nor help you.

All programs should be deterministic in both languages, this means that any program that can halt must always halt and any program that can run indefinitely must do so.

Answering

Your answer should contain the following information.

1. A concrete description of both languages

2. Proofs that each language as described is Turing complete.

Your definitions should be rigorous and unambiguous. Meaning that a reasonable person should (given enough time) be able to workout the result of any computation. This means all edge cases should be covered and there should be no undefined behavior.

Scoring

Your score will be the time between your post and the first crack with a higher score being better.

Robbers

Robbers will score 1 point for every answer that they crack, with a higher score being better.

Your answers should include the program which cracks the cop's answer and a proof that it does.

Sandbox

This is kind of just an idea right now. I have to iron out a lot of details and I will. I'll flesh it out later I just want to get it down so I don't forget it. Right now the most useful feedback would be in broad strokes. Don't worry about details, that's my job.

---

^{1: Turing equivalent is very similar to Turing completeness, but also stipulates that the language can be simulated by a Turing machine. Turing complete languages are not Turing equivalent if they are incomputable.}

^{2: Suppose that we did have two Turing complete languages A and B such that every program halted in exactly one of the languages. We could solve the halting problem in language A by running a program in both A and B on separate threads until one of them halted, then outputting whether it was A or not.}

Answer 15

Really skirting bit of sandboxing here (I haven't taken the time to develop the question):

I'd like to do a 2-d variant of this one.

Two lasers between two mirrors

The input would be an ascii maze, with a marker for the laser starting point, e.g.:

+---+------+
|*  |      |
|   |      |
|   |  ----+
|   |      |
|   |      |
|   |      |
|   +---   |
|          |
|          |
|          |
+----------+

• Astrisk(*): laser starting point.
• Whitespace: passable.
• Any other character is a reflective obstacle.

Result:

+---+------+
|\  |   /\ |
| \ |  /  \|
|  \| /----+
|  /|/   /\|
| / |\  / /|
|/  | \/ / |
|\  +---/  |
| \    /   |
|  \  /    |
|   \/     |
+----------+

Rules:

• When you can't move horizontally, reverse horizontal direction.
• When you can't move vertically, reverse vertical direction.
• Stop going when you meet the same laser coming the other way (e.g. when you hit a corner or reach your starting position again).I'm thinking of a golfing challenge.
• If the laser revisits a space in the other direction, draw an upper case X.

Simplifying factors:

• Let's just say the laser always goes the same way.
• The map is always a rectangle.
• Just the one laser.

It'll probably just be a golfing challenge.

Answer 16

X1M4L got in before me and posted the very similar challenge Print the previous answer!, which I don't mind at all. However, that one seems to have turned out quite a lot more open-ended than this version would be, with answers tending to score in the tens of thousands. So after a sufficiently long delay this will probably not be considered a duplicate - I intend to leave it in the sandbox for at least a few months before posting.

Compress the previous answer

This is an answer-chaining challenge. The first answer must output the empty string. The second answer must output the source code of the first answer, and so on, with each answer outputting the code of the previous one.

To make this challenging, no answer may be longer than 100 bytes in length. Once the answers start getting close to this limit, it will become necessary to compress the text of the previous answers, which itself will become harder over time.

Each answer should output the exact string of bytes that forms the previous program. Because of this, if your program is in any format other than plain ASCII, you should post a hexdump as well as the source, so that the next person knows exactly what to output.

An answer's score is its position in the chain, i.e. the Nth answer scores N points. Your score is the score of your highest-scoring answer. You are encouraged to treat this challenge cooperatively, keeping the chain going as long as possible by not adding extra unnecessary entropy to your code.

The code of your answer cannot be identical to the code of any previous answer. The first answer must be at least one byte in length.

You may not post two consecutive answers. There are no restrictions on language.

tags: code-challenge answer-chaining compression

Answer 17

Rebuild My Scrabble Board

code-golf game board-game string

My daughter and I have an ongoing Scrabble tournament. We enjoy admiring the board at the end of a game. But recently we knocked over the board and didn't get a chance to get a good look or take a picture. Fortunately, we kept track of all our moves. Your challenge is to take the list of moves and use it to rebuild the Scrabble board.

Input

Each move includes 4 pieces of information

1. Column - A - O, like the column label of a typical spreadsheet. Upper or lower case is OK, but you only need to support one or the other.
2. Row - 1 - 15, like the row label of a typical spreadsheet. 0-indexed 0 - 14 is acceptable.
3. Orientation - H=Horizontal, V=Vertical - Upper or lower case is OK, or you may choose any other 2 printable ASCII characters.
4. Tiles - A - Z plus @ for blank. Upper or lower case is OK, but you only need to support one or the other. You can use a different printable ASCII character for blank if you prefer, but not the space character or a period. The tiles for a move may be a string or a list of characters - e.g., CAT or (C,A,T).

Input format may be a tuple, list, separate lines (4 per move) or any other reasonable format. Column + Row may be combined, spreadsheet-style (e.g., A1, O15), but the orientation and tiles must be separate fields. Column can't be numeric - that is easy for the computer but in the middle of a game we have enough to keep track of, so remembering which # is Row and which # is Column would be too confusing - spreadsheet notation is easy to remember.

Output

The completed Scrabble board is to be printed in a format similar to Draw an Empty Scrabble Board. However, the double/triple squares are not printed and the moves are, obviously, included. Specifically:

• 15x15 matrix
• Unused spaces display as a period .
• No leading spaces allowed.
• Trailing spaces allowed.
• One line feed at the end of each row.
• Up to one leading and one trailing line feed permitted.
• Blank tiles are to be output using the same character as input (default @).

Rules

Each move is placed starting with the first tile in the specified location. Each additional tile is to be placed in the next available location. In other words, your program must keep track of filled locations and skip them, just like a player placing tiles on the board.

What you don't need to worry about:

1. Invalid words - if my daughter and I decided it was OK, you don't have to check it.
2. Invalid locations - these are real moves, so there will of course be enough space to place all the tiles, and you don't have to double-check that a move starts on an empty space (but you can do that if it makes your algorithm shorter since you do have to check for all the other tiles in each move).
3. Proper use of the standard Scrabble set of tiles - e.g., you don't have to check that there are only 2 blanks, 1 Z, etc.

Examples

[Sandbox note: Plan to include a couple of complete games plus a few shorter examples to highlight particular issues]

Input:

(G,8,H,CAT)
(G,9,V,OMPUTE)
(F,9,H,RB)
(H,7,H,TIME)
(I,6,V,BE)

Output:

...............
...............
...............
...............
...............
........B......
.......TIME....
......CAT......
.....ROBE......
......M........
......P........
......U........
......T........
......E........
...............

Scoring

• The input and output can be given by any convenient method.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• Standard loopholes are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 18

Find the minimum set of letters to buy

Imagine that you own a board like this:

which lets you write any message that you want, given that you have the letters for the message. Given that you have a list of messages that you want to switch between, find the minimum number of each letter that you have to order with your board.

As an example, if your messages are Hello world and Hello aliens, you would need the letters Helloworldaiens, as both messages share the Hello part and the letter l in the second word.

For this challenge, input messages will only consist of letters a-zA-Z and space, however note that spaces are not included in the output as you don't need to buy them.

Input

Input consists of a list of strings, which all match [a-zA-Z ]+. There is no limit on the amount of messages that can be provided, or their length.

Output

Output consists of a string of a list of characters, where the letters in the output can be rearranged to create all the input messages, and is of minimal length. The output does not need to be sorted.

Examples

['Hello world', 'Hello aliens'] => Hadeeilllnoorsw
['foo', 'bar', 'baz'] => abfoorz
['Eat more tacos', 'Drink more tequila'] => DEaaceeiiklmnooqrrsttu
['Golfing is a fun activity', 'Code should be readable'] => CGaabbcdddeeeeffghiiiillnnoorsttuvy
['a', 'b', 'c', 'd', 'e', 'f', 'g'] => abcdefg

This would of course be a code-golf challenge

Answer 19

Note: I'm putting this challenge on the back burner for a indefinite time in favor of the Hierarchies challenge. Go check that or the Formic Forest out if you're interested in a Formic sequel.

---

Formic Functions 3: Memory

This is a preliminary write-up of a new challenge heavily inspired by Formic Functions. The spec is based on the original challenge's spec - credits for most of what you'll read here to trichoplax.

Each player starts with one ant - a queen, who collects food. Each piece of food can be held or used to produce a worker. Workers also collect food to be brought back to the queen.

All players compete in one arena. The winner is the queen holding the most food after she has taken 8,000 10,000 [Thanks @Draco18s] turns. Ants can communicate by changing the colors of the arena squares (which can also be modified by rivals), as well as by storing messages for their peers.

The arena

The arena is a toroidal (edge wrapping) grid of hexagonal cells arranged in a rhombus of side length 1000. All cells start as color 1.

Initially exactly 1% 0.5% of cells will contain food. The 5000 pieces of food will be scattered uniformly randomly. No new food will be introduced during the game.

The queens will be placed randomly on empty cells, with no guarantee that they will not be adjacent to each other (although this is very unlikely).

Ant abilities

• Sight: Each ant sees the 7 cells in its neighborhood. It has no knowledge of any other ants outside this neighborhood. It sees the contents of each of the 7 cells (other ants and food), and also each cell's color.
• Memory: Each ant has access to a string as its memory. It is initially empty for the queen, and must be initialized by the queen when spawning a worker. For ways to change the memory after initialization, see Output below.
• No orientation: An ant does not know where it is or which way it faces - it has no concept of North. The neighborhood will be presented to it at a randomly rotated orientation that changes each turn so it cannot even walk in a straight line unless it has colors to guide it. (Making the same move every turn will result in a random walk rather than a straight line.)
• Moving, color marking, producing workers and transferring food: See Output below.
• Immortality: These are highland ants that cannot die. You can confuse rival ants by changing the colors around them, or constrain them from moving by surrounding them with 6 ants of your own, but they cannot be harmed apart from this. [Should ants be able to die? If so, how?]
• Carrying food: A worker can carry up to 1 piece of food. A queen can carry an arbitrary amount of food.

Coding

Provide a function body

Each ant is controlled by an ant function. Each turn the player's ant function is called separately for each ant (not just once per player, but once for the queen and once for each worker that player controls). Each turn, the ant function will receive its input and return a move for that particular ant.

Post an answer containing a code block showing the body of a JavaScript function, and it will be automatically included in the controller. The name of the player forms the title of the answer, in the form # PlayerName.

No access to outside data

Functions must be fully deterministic. When called with a given input, they must return the same output every time. A function must not access global variables and must not store state between turns in other ways than through the provided memory string. It may use built in functions that do not involve storing state or accessing data from the outside. For example, the use of Math.abs() is fine, but Date.getTime(), Math.random() must not be used.

An ant function may only use a pseudo random number generator that it supplies itself, that utilizes data provided through input. For example, it may implement its own pseudo RNG via its memory string, seeded by the environment (or statically).

A simple random strategy is still possible due to the random orientation of the input - an ant that always chooses the same direction will perform a random walk rather than a straight line path.

An ant function is permitted to contain further functions within its body.

Input and output

Input

The orientation of the input will be chosen at random for each ant and for each turn. The input will be rotated by 0, 60, 120, 180, 240 or 300 degrees, but will never be reflected.

Cells are numbered in this order:

 0 1
5 6 2
 4 3

The ant function will receive an array called view, containing an object for each of the 7 visible cells. Each object will have the following:

color: a number from 1 to 8
food: 0 or 1
ant: null if there is no ant on that cell, or otherwise an ant object

[Is 8 colors perhaps too many?]

If a cell contains an ant, the ant object will have the following:

food: 0 or more (maximum 1 for a worker)
queen: true or false
friend: true or false
memory: memory string when friendly, otherwise undefined

[Should ants be able to read rivals' memories? This would cause rampant edit wars. Rejected.]

The ant can determine its own details by looking at the ant in the central cell, view[6].ant. For example, view[6].ant.memory contains the memory of the executing ant.

Output

Output is returned as an object representing the action to take. This can have any of the following:

cell: a number from 0 to 6 (mandatory)
color: a number from 1 to 8 (optional)
spawn: a string (optional)
memory: a string (optional)

If color and spawn are omitted or non-truthy, then cell indicates the cell to move to.

If color is a number, the indicated cell is set to that number.

If spawn is a string, a worker ant is created on the indicated cell. The new worker will have its memory initialized to that string. The string cannot be longer than 256 characters. Only a queen can create a new worker, and only if she has food, as this costs one piece of food per worker.

If memory is a string, the executing ant will have its memory immediately changed to that string. The string cannot be longer than 65,536 characters for the queen, and 256 characters for workers. An ant may change its memory while also performing a different action - changing memory does not take a turn.

[Should changing own memory take a turn?]

[Should ants be able to send a message directly to another ant's inbox? For example, a message could look like this: {title:"help", content:view_array_of_sender}. An ant should also be able to perform an action while sending a message, otherwise the described behavior could be emulated.]

[Should ants be able to see the age of an ant? This behavior will often be emulated with memory. Is there a reason not to do that?]

[Is 65,536 characters a good number to pick for the max length of memory? Thanks to @Draco18s's and @dzaima's advice, workers now have significantly less memory than a queen.]

Example outputs:

{cell:0}: move to cell 0
{cell:5, memory:"abc"}: move to cell 5 and set own memory to "abc"
{cell:6}: move to cell 6 (that is, do nothing, as 6 is the central cell)
{cell:6, color:8}: set own cell to color 8
{cell:2, color:1, memory:"hey"}: set cell 2 to color 1 and set own memory to "hey"
{cell:1, spawn:"def", memory:"5252"}: create a worker with its memory initialized to "def" on cell 1 and set own memory to "5252"
{cell:3, color:0}: equivalent to just `{cell:3}` - move rather than set color
{cell:1, spawn:0}: equivalent to just `{cell:1}` - move rather than create worker
{cell:4, color:0, spawn:0}: move to cell 4 - color 0 and type 0 are ignored

Invalid outputs:

{cell:7}: cell must be from 0 to 6
{cell:0, color:9}: color must be from 1 to 8
{cell:0, spawn:true}: spawn must be a string
{cell:6, spawn:"254"}: cannot create a worker on a non-empty cell
{cell:0, color:1, spawn:"77"}: cannot set color and create worker in the same turn
{cell:3, memory:true}: cannot set memory to non-string
{cell:2, spawn:true}: cannot create a worker with a non-string memory
{cell:0, memory:long_string}: (if long_string is a string of length > 65536) cannot set memory to a string of length greater than 65536

[Missed any?]

An ant moving onto a cell containing food will automatically pick up the piece of food. If that ant is a laden worker, it will move onto the cell without picking up the piece of food.

An unladen worker trying to move onto an enemy queen with food will steal one piece of food from her instead. A laden worker trying to move onto an unladen friendly worker or a friendly queen will give its food to their target instead.

Turn order

Ants take turns in a set order. At the start of a game the queens are assigned a random order which does not change for the rest of the game. When a queen creates a worker, that worker is inserted into the turn order at the position before its queen. This means that all other ants belonging to all players will move exactly once before the new worker takes its first turn.

Limit on number of players

Obviously an unlimited number of players cannot fit into the arena. If there are more than 8 answers, only 8 of them will play in any one game.

[Good max number of players?]

Time limit per turn

Each time the ant function is called, it should return within 20 milliseconds. Since the time limit may be exceeded due to fluctuations outside the ant function's control, an average will be calculated. If at any point the average is above 20 milliseconds and the total time taken by that particular ant function across all calls so far is more than 10 seconds, the relevant player will be disqualified.

[Enough time?]

Disqualification

This means the player will not be eligible to win and their ant function will not be called again during that game. They will also not be included in any further games. If a player is disqualified on the tournament machine during a leaderboard game then it will be excluded from all future leaderboard games until edited.

A player will be disqualified for any of the following for any of its ants (queen or worker):

• Exceeding the time limit as described.
• Returning an invalid move as described under Output.
• The cell to move to contains an ant and the case isn't defined under Output.
• The cell to produce a worker on contains an ant.
• A worker is trying to produce a worker.

[Did I miss any?]

It may seem harsh to disqualify for invalid moves, rather than simply interpreting this as no move. However, I believe that enforcing correct implementations will lead to more interesting strategies over time. This is not intended to be an additional challenge, so a clear reason will be displayed when a player is disqualified, with the specific input and output alongside to aid in fixing the code.

Multiple answers and editing

You may provide multiple answers, provided that they do not team up against the others. Provided each answer is working solely towards its own victory, you are permitted to tailor your strategy to take advantage of weaknesses in specific other strategies, including changing the color of the cells to confuse or manipulate them. Bear in mind that as more answers come in, the likelihood of meeting any particular player in a given game will diminish.

You may also edit your answers whenever you choose. It is up to you whether you post a new answer or edit an existing one. Provided the game is not flooded with many near-identical variations, there should be no problem.

If you make a variation of another person's answer, please remember to give them credit by linking to their answer from yours.

Scoring

At the end of each game, a player's score is the number of other players who have less food carried by their queen. Food carried by workers is not counted. This score is added to the leaderboard, which is displayed in order of average score per game.

Joint places indicate that the order of players is not yet consistent between 6 subsets of the games played so far. The list of games is split into 6 subsets because this is the minimum number that will give a probability of less than 5% that a given pair of players will be assigned distinct places in the wrong order.

[Scoring mechanism subject to change.]

[New feature/modification recommendations are very welcome! I want this challenge to be as different from the original Formic as possible, while keeping its spirit.]

hexagonal-grid game king-of-the-hill javascript

Answer 20

How many times was the function called?

Inspired by this question.

Using your language of choice, write a function that takes no argument and returns the number of times it was called.

Specifics:

Your language needs to support something callable (multiple times) that takes no argument (or an empty unused argument) and returns a number or a string representing the number of times it was called, for example 1, 1.0 or "1". Standard I/O applies.

Samples:

f() returns 1
f();f() returns 1 2
f();f();f();f() returns 1 2 3 4

Note that f(f(f(f()))) (function composition with itself) is not in the scope of this challenge.

As this is code-golf, the winning solution in any language is the one that uses the fewest number of bytes in this language.

code-golf function

Answer 21

Mixed alphanumeric sort

code-golf sorting array-manipulation

Can't decide if you want to sort by letter or by number? Just do both!

Create a program that, given a series of strings composed of the characters _, 0-9, and a-z, sorts them and returns them in order.

---

Sorting is done according to the following algorithm:

• A token is any character among _a-z or a contiguous series of numerals
• The empty string is sorted first
• Single token strings are sorted as follows:
  • _ is sorted before numbers, and numbers are sorted before letters
  • Numbers are sorted in numeric order, and letters are sorted from A to Z
  • If two numbers have the same value, the shorter one is sorted first
• Multi token strings are sorted according to the first token. If the first token is the same, then use the second, then third, etc.

---

Here is an example of a sorted list. You can use newlines, commas, or whatever else to separate the items, or you can just use a standard array type.

_first
5
5x
5y
123
0123
124
ab_
ab5
ab10
abc
abc
abc00b
abc000a

---

Rules

• Input list can contain empty strings, but is always at least 1 element long
• Input and output may be a list, or a string with separator characters of choice
• Output can also be in-place (modifying the input list), as long as the changes are readable from outside the program
• You can choose to process uppercase characters instead of lowercase ones
• Standard loopholes apply
• Lowest byte count wins

---

Sandbox questions

• Is the description clear enough, or could anything be added to it?
• It turns out this is a near duplicate of this one, but with the addition of a character that must be sorted before numbers, which changes the strategy. Is this different enough to be its own question?

Answer 22

Diagonalize a Blackbox code-golf math matrix function

todo: test cases

more math explaination?

better challenge definition?

The function \$f(x_1,x_2,x_3)=(3x_1,x_1+2x_2,x_1+x_2+x_3)\$ is a linear transformation on \$\mathbb{R}^3\to\mathbb{R}^3\$. We can prove this, because like all linear transformations, it satisfies:

• \$f(x_1+y_1,x_2+y_2,x_3+y_3)=f(x_1,x_2,x_3)+f(y_1,y_2,y_3)\$
• \$f(\alpha x_1,\alpha x_2,\alpha x_3)=\alpha f(x_1,x_2,x_3)\$

Or, more compactly:

• \$f(\alpha x+\beta y) = \alpha f(x)+\beta f(y)\$

All linear transformations like this can be represented by a matrix multiplication, such as:

$$ M = [f(x)] = \begin{bmatrix} 3 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = (x_1,x_1+x_2,x_1+x_2+x_3) $$ One way to find this matrix is by feeding each of the members of the standard basis for \$\mathbb{R}^3\$, which is \$B = \{(1,0,0),(0,1,0),(0,0,1)\}\$, into \$f(x)\$ to get the columns. This can be for any linear transformation and any basis to get a matrix which represents the transformation in that basis.

For some linear transformations, there is a basis \$B'\$ in which \$M'\$ is diagonal - this requires that \$M\$ in \$B\$ be diagonalizable which requires it have unique eigenvalues. However, in this challenge all transformations you have to deal with will fulfill these requirements.

Continuing with the same example, we can determine the eigenvalues of \$M\$ by finding solutions to \$|M-\lambda I_3|=0\$, and the eigenvectors by solving \$Mv=\lambda v\$ for each \$\lambda\$:

$$ |M-\lambda I_3| = (3-\lambda) \begin{vmatrix} 2 - \lambda & 0 \\ 1 & 1 - \lambda \end{vmatrix} = (3-\lambda)(-(2-\lambda)(1-\lambda))\\ (\lambda-3)(-(2-\lambda)(1-\lambda)) = 0 \implies \lambda_1,\lambda_2,\lambda_3 = 3,2,1$$ This gives us a diagonal matrix \$M' = \begin{bmatrix}3&0&0\\0&2&0\\0&0&1\end{bmatrix}\$ $$ \begin{bmatrix} 3 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 1 \end{bmatrix}\begin{pmatrix} a\\b\\c \end{pmatrix} = \begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\\ \lambda_1\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}3a\\3b\\3c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_1=(1,1,1)\\ \lambda_2\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}2a\\2b\\2c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_2=(0,1,1)\\ \lambda_3\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}3a\\a+2b\\a+b+c\end{pmatrix}\implies v_3=(0,0,1) $$ This gives us a basis \$B'=\{(1,1,1),(0,1,1),(0,0,1)\}\$ where the matrix \$M'\$ represents \$f(x)\$.

In this basis, a vector that would be \$(5,6,7)\$ in \$B\$ is instead \$(5,1,1)\$, as shown here: $$(5,1,1)_{B'} = 5(1,1,1)+1(0,1,1)+1(0,0,1) = (5,6,7)_B$$

This affects the transformation as well:

$$ \begin{bmatrix} 3&0&0\\ 1&2&0\\ 1&1&1 \end{bmatrix} \begin{pmatrix} 5\\6\\7 \end{pmatrix} =\begin{pmatrix} 15+0+0\\ 5+12+0\\ 5+6+7 \end{pmatrix} =(15,17,18)_B\\ \begin{bmatrix} 3&0&0\\ 0&2&0\\ 0&0&1 \end{bmatrix} \begin{pmatrix} 5\\1\\1 \end{pmatrix} =\begin{pmatrix} 15+0+0\\ 0+2+0\\ 0+0+1 \end{pmatrix} =(15,2,1)_{B'}\\ (15,2,1)_{B'}=15(1,1,1)+2(0,1,1)+1(0,0,1)=(15,17,18)_B $$

Caveats

Notice how when we were finding \$v_1\$ above we picked \$(1,1,1)\$ to simplify. Unfortunately \$v_1=(7,7,7)\$, \$v_2=(0,-3,-3)\$ (and infinitely many more) are also valid in this context.
To make every solution uniform, we normalize each of the vectors:

$$ v_1=\frac{(1,1,1)}{\sqrt{1^2+1^2+1^2}}=(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})\\ v_2=\frac{(0,1,1)}{\sqrt{1^2+1^2}}=(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})\\ v_3=\frac{(0,0,1)}{\sqrt{1^2}}=(0,0,1) $$

So we get a basis \$B'=\{(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}),(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}),(0,0,1)\}\$, which corresponds to:

$$(5,1,1)_{B'} = 5(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})+1(0,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})+1(0,0,1)\\ = (\frac{5}{\sqrt{3}},\frac{1}{\sqrt{2}}+\frac{5}{\sqrt{3}},1+\frac{1}{\sqrt{2}}+\frac{5}{\sqrt{3}})_B$$

Additionally, we also add a restriction so that the first non-zero element of each eigenvector must be positive, flipping the signs of the rest of the vector if it was initially negative.

The Challenge

Your task is to write a function or program which takes a black-box function or program and either:

1. outputs a function or program which accepts arguments in a special basis \$B'\$ as described above, performs the transformation on them, and returns the result in the standard basis \$B\$

2. outputs the result in \$B\$ directly and takes the secondary arguments in \$B'\$ itself

Input

You are given a function (via one of the standard IO methods applicable) taking a vector as input and returning another vector in the same form, as the same data type.

Alternatively, you can take a program (via the name of an executable in the current working directory, or a process ID) which takes a vector as input through one of the standard input methods for programs, and outputs a vector in a whitespace-separated string.
(The executable can be in a different language, so don't try to read it.)

The input and output vectors for this function or program are in \$\mathbb{R}^n\$ with basis \$B\$.
You are also given a number specifying the size of the lists to be used (\$n\$ in \$\mathbb{R}^n\$).

If you follow the second option you will additionally receive a vector in basis \$B'\$.

Output

Otherwise, output a function taking a vector as input and returning another vector, where the function you output uses the standard IO methods for your language. Your submission may output this function as a literal function, function pointer, or as source code for such a function in your language. Instead of a function, you may output a whole program as source code or compiled binary, which takes a vector as input and returns another vector via the standard IO methods for your language.

The input and output vectors for this function or program are in \$\mathbb{R}^n\$.
The input vectors have basis \$B'\$, and the output vectors have basis \$B\$.

If you follow the second option then the above statement applies to your submission instead of the output, and you do not need to output a function nor a program but instead the specified vector.

Criteria

As this is code-golf, the shortest code in bytes for each language, further subdivided by combination of function / program as input / submission / output, wins!

Test Cases

todo

Notes

While it's a bit math-y, there are multiple interesting routes to go for a solution to this:

• Transform \$B'\to B\$ and pass to the input function or program
• Follow the question closely and apply the transformation via \$M'\$
• More I won't disclose
• Probably more I haven't thought of

Answer 23

Making a Mountain out of a Molehill

Answer 24

Recognize the hardest context-free language

code-golf decision-problem string grammars

---

A context-free language is a class of strings that can be recognized by a pushdown automaton, or equivalently produced by a BNF grammar. In her 1973 paper, Sheila Greibach showed that there exists in some sense a "maximally complex" context-free language. In this challenge, your task is to recognize this language.

The language

The words of the language \$L\$ use the seven characters \$\mathtt{()[]ABC}\$. You may use any seven printable ASCII characters in their place, but we use these in the explanation and test cases. A string \$s\$ is in the language if:

1. It can be broken into \$n\$ pieces: \$s = w_1 \mathtt{C} w_2 \mathtt{C} \cdots w_n \mathtt{C}\$ where the \$w_i\$ do not contain \$\mathtt{C}\$s.
2. Each \$w_i\$ has a substring of the form \$\mathtt{B} x_i \mathtt{B}\$ where \$x_i\$ does not contain \$\mathtt{B}\$s.
3. The concatenation \$x_1 x_2 \cdots x_n\$ has the form \$\mathtt{A} b\$, where \$b\$ is a balanced string over \$\mathtt{()[]}\$.

Note that each \$w_i\$ may have several substrings that begin and end with \$\mathtt{B}\$, but we require that the third condition holds for at least one choice of the \$x_i\$. Also, some of the \$x_i\$ may be empty.

Here is an example of a string in \$L\$ and an explantion for it:

]BA[]BA[](BCB[]BA]B()(BC]B][BB]BCB)BAAB))C
           C           C        C        C    Split by C
     BA[](B B[]B            BB   B)B          Find substring surrounded by B in each part
      A[](   []                   )           Their interiors give A + balanced string

Here is a BNF grammar for \$L\$: [TODO: verify that this is correct]

<L>        ::= <trash> "BB" <trash> "C" <L>
             | <trash> "BA" <balanced> "B" <trash> "C"
<balanced> ::= <skip-c> <balanced>
             | "(" <balanced> ")"
             | "[" <balanced> ")"
             | <balanced> <skip-cs> <balanced> <skip-cs>
<skip-cs>  ::= <skip-c> <skip-cs> | ""
<skip-c>   ::= "B" <trash> "C" <trash> "B"
<trash>    ::= <not-c> <trash> | ""
<not-c>    ::= "A" | "B" | "(" | ")" | "[" | "]"

The task

Your input is a non-empty string over the alphabet of \$L\$. As stated above, you may use any 7 printable ASCII characters. Your program/function shall do one of the following:

• Output a truthy value if the input is in \$L\$, and a falsy value if not.
• Output a consistent value if the input is in \$L\$, and a different consistent value if not.

The lowest byte count wins, and other standard code-golf rules apply.

Test cases

TODO

Answer 25

Number of Unit Squares Intersecting a Circle

code-golf geometry oeis

(Credit to user202729 for the illustration)

OEIS sequence A234300 is defined thusly:

• A radius range is either a single real number at which the circle centered at \$(0,0)\$ passes through some lattice point, or an interval between two such consecutive numbers.
• The first radius range is the number \$0\$.
• The \$n\$th term of the sequence is the number of unit squares on the upper right quadrant of the Cartesian grid whose interior contains some segment of the circle of radius \$r\$, where \$r\$ is in the \$n\$th radius range.

This table shows the radius range and corresponding sequence terms for the first 11 terms of the sequence.

Range       Term
0           0
(0,1)       1
1           1
(1,√2)      3
√2          2
(√2,2)      3
2           3
(2,√5)      5
√5          3
(√5,√8)     5
√8          4

Input

A positive integer n (or nonnegative for zero-indexed).

Output

Either the \$n\$th term of the sequence, or a list of the first \$n\$ terms. You may index from \$n=0\$ or \$n=1\$.

Answer 26

Non-overlapping Matrix Sum

Given k arrays of length n, output the maximum sum possible using one element from each matrix such that no two elements are from the same position. It is guaranteed that k<=n.

Input

A nonempty list of nonempty arrays of integers.

Output

An integer that represents the maximum sum.

Examples

Input -> Output
[[1]] -> 1
[[1, 3], [1, 3]] -> 4
[[1, 4, 2], [5, 6, 1]] -> 9
[[-2, -21],[18, 2]] -> 0
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 15
[[1, 2, 3, 4], [5, 4, 3, 2], [6, 2, 7, 1]] -> 16

Answer 27

Output Hello, World! ... sometimes

code-golf

On PPCG, we typically do not allow programs to work only part of the time. That is, all programs must work with 100% probability unless otherwise stated.

This challenge is going to state otherwise. Your program must, with nonzero probability, output this exact string to STDOUT:

Hello, World!

However, a simple Hello, World! program will not do. Your program must also have nonzero probability to behave in any other way than outputting the above string. This could be printing another string, printing Hello, World! surrounded by junk text, outputting Hello, World! to STDERR instead of STDOUT, outputting nothing, crashing, etc. Your program may have many different behaviors than printing the desired string.

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

Example program

The following program in JavaScript is a valid submission. It will output Hello, World! half the time, and the other half of the time output a float >= 0.5.

const THRESHOLD = 0.5;
let randomFloat = Math.random();

let output;

if(randomFloat < THRESHOLD) {
    output = "Hello, World!";
}
else {
    output = randomFloat.toString();
}

console.log(output);

Try it online!

Answer 28

Speeding up powers of 2

code-golf

Create a function or program that indefinitely prints outs successive powers of 2 separated by newlines. However, the nth term of the sequence (2^n) must have a delay of 1/n seconds either before or after it is printed, but please specify this in your answer. If you choose to add the delay before the number is printed, the first number may optionally have a delay before it is printed.

Your program may begin with 1 or 2 as the first printed number, but if you include 1, it is considered the 0th term, and your delays must be before each print and skip any initial delay (1/0 as a delay would not work, hence this rule).

Your program should run properly until it either reaches the integer limit of your language, or until n = 1000 (a 1 ms delay)

Expected output if 1 is included:

1 # after, wait 1/1 seconds
2 # after, wait 1/2 seconds
4 # after, wait 1/3 seconds
8 # after, wait 1/4 seconds
16 # after, wait 1/5 seconds
# etc...

Expected output if 1 is not included:

2 # before/after, wait 1/1 seconds
4 # before/aftert, wait 1/2 seconds
8 # before/after, wait 1/3 seconds
16 # before/after, wait 1/4 seconds
# etc...

---

Sandbox

• How should I improve the wording?
• What potential ambiguities or language limits are there?
• Is this too similar to a preexisting challenge?

EDITS: Clarified that n refers to the term number, not the power of 2

Answer 29

Static Code Analysis Battle!

Your programs will play a friendly game of rock, paper, scissors. There's a catch though; you can not use randomness and the combatants can see each other's source code.

That is, you will write a python program that, when imported, provides a function named rps. Given two combatants, say player1.py and player2.py, the controller will import them, and execute player1.rps(player2sourceCode) and player2.rps(player1sourceCode). These should output R, P, or S. The winner is then whoever would win in rock paper scissors with those moves. If one player makes a valid move, and the other does not, that player wins. If both players make an invalid move, it is considered tie. Additionally, taking more than 1 second to move is considered an invalid move.

Here are the rules:

1. Both the action of importing your module and your rps function should be pure functions. This means for example that you can not do the following:
   1. Use randomness or other non-deterministic code.
   2. Interfere with or receive information from the file system, I/O, peripherals, etc...
   3. Use time.sleep.
   4. Alter or access the state of the controller.
   5. Use other functions to do impure actions. For example, you can not call eval on the source code of an impure function call. An exception to this is if the only impure thing it does is interact with your program's state (i.e. it is permitted to change variables in your program's namespace). You can, however, call it on pure function call source code.
   6. Anything else that a pure function could not do.
2. Other functions in your source code, however, may be impure.
3. You may assume that the source code passed as an argument to rps obeys rule 1. You may not, however, assume that the rps in the passed source code is a pure function when you pass it source code that does not obey rule 1. Additionally, other functions in the module may be impure.
4. Additionally, going into an infinite loop is perfectly fine, although if it happens when the caller calls your program, your move will be considered invalid. If the opponent calls your program and it causes them to go into an infinite loop, however, their move will be considered invalid, and vice versa.

This is koth, so the program that defeats the other programs wins! In particular, I will run a match between each program and each other program. The winner will be the condorcet winner if one exists. Otherwise, the result will be a tie between the Schwartz set members.

Answer 30

Classic VCS ASCII Adventure

Moved to main. Thanks everyone for your input. Happy golfing!