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

Guessing on straws

Dedicated to Martin Gardner, taken from his book

Background

In the old days, the Slavs had such divination. One girl was clutching six straws in her fist, and her friend was pairing first the top and then the bottom ends. If all straws were ring-tagged, the girl would be married.

Goal of challenge

Having the number of straws and the binding schemes, determine whether the single hole cycle will result.

Input

• Number of straws N, even integer >= 2
• Two nested lists as top and bottom links, for instance [[1, 4], [2, 5], [6, 3]]

Schemes may be valid or invalid! On one hand, it is guaranteed that are used only positive integers not more N; no self-links ([1, 1]), no tautologies ([[1, 2], [2, 1], …]), no broken lists ([[1], [ ], …]) etc.

Please note, that pairs are unordered, so eg [[1, 4], [2, 5], [6, 3]] and [[4, 1], [2, 5], [3, 6]] both valid (and equivalent) schemes.

But due to the girl’s inattention, followed cases can take place:

• Missing pair (one or more): [[1, 4], [6, 3]], [[1, 10], [4, 5], [3, 7]] etc.
• More than two binding straws: [[1, 4], [1, 5], [2, 6]] (and as result, free straws)

All of these inputs are invalid, your program must detect them and stop with appropriate message (see below).

Output

Any three distinct symbols for "Invalid input", "No loop", "Has loop" cases. Suitable for golfing on your language:

• -1 for invalid input, 0 for "No loop", 1 for "Loop"
• None, False and True respectively
  etc.

Test cases

N: 2, TopLinks: [[1, 2]], BottomLinks: [[2, 1]]  → True

N: 4, TopLinks: [[1, 2], [3, 4]], BottomLinks: [[2, 1], [3, 4] ]  → False

N: 4, TopLinks: [[1, 2], [2, 4]], BottomLinks: [[2, 1], [3, 4], [3, 2] ]  → Invalid

N: 8, TopLinks: [[1, 2], [3, 4], [6, 5], [7, 8]], 
BottomLinks: [[8, 1], [3, 2], [4, 5], [7, 6] ]  → True

Answer 2

Shortest Code to Implement a Simple Encryption Algorithm

Write a program or function that implements a simple encryption algorithm. The algorithm takes in a string of ASCII characters and a key, and outputs an encrypted string.

Encryption Algorithm

1. Convert each character in the input string to its ASCII value
2. XOR each ASCII value with the corresponding byte in the key (cycling through the key if necessary)
3. Convert the resulting XOR values back to ASCII characters
4. Concatenate the ASCII characters into a single string and output the result

Your program or function should take in two inputs:

A string of ASCII characters (up to 1024 characters in length) A key string (up to 1024 characters in length) Your program or function should output a single string representing the encrypted message.

Test Cases

Input:
message: "Hello World"
key: "secret"
Output:
"UW]cU\xf3M]Z]^Y"

Input:
message: "12345"
key: "password"
Output:
"^%-'$#"

Input:
message: "This is a test message"
key: "key"
Output:
"\x03\x1a\x1c\x17\x02\x0eP\bI\x11\x07\x14N\x1d\x10M\r\b\x1f"

This is a codegolf challenge, so the goal is to write the shortest possible implementation of the encryption algorithm. The winner will be determined based on the length of their code, with ties broken by earlier submission time.

Answer 3

Mapping Passing Through Point

Answer 4

Optimize Distance Travelled By Thrown Object (With Air Resistance)

code-golf

Suppose you're on a flat surface, then throw an object with some velocity \$v_0\$ at an angle \$\theta\$ above the ground. Assuming the only forces on the object are (constant) gravity and air resistance, we can model the horizontal and vertical components of the acceleration (the instantaneous change in velocity in the x and y direction) as follows:

$$a_x = v_x^2 * \delta$$ $$a_y = v_y^2 * \delta + g$$

Where \$v_x\$ and \$v_y\$ are the horizontal and vertical components of velocity, \$g\$ is acceleration due to gravity, and \$\delta\$ is the coefficient of acceleration due to drag (which is a single number which depends on the drag coefficient, cross-sectional area, and the density of the fluid, and the mass).

The initial x and y components of velocity are $$v_x = v_0 \cos \theta, v_y = v_0 \sin \theta$$

The object stops moving when it hits the ground again (when its \$y\$ position becomes 0 again). We want to find the angle \$\theta\$ which maximizes the horizontal distance \$x\$ that the object travels.

Your challenge is, given the initial velocity \$v_0\$, acceleration due to gravity \$g\$, and coefficient of acceleration due to drag \$\delta\$, output the angle \$\theta\$ (in either degrees or radians) which maximizes the horizontal distance travelled, within one percent of the true maximum.

Standard loopholes are forbidden. Since this is code-golf, the shortest program wins.

TODO: Test cases

Answer 5

Soundproof Cell

code-golf kolmogorov-complexity

Here's a message from the organizers:

Hello! We hope this message finds you well.

Unfortunately, your performance in the past games has been sub par. Your team is unimaginative and lacks creativity. Instead of inventing novel techniques to win our games, you keep sticking to the techniques you know. This is not the spirit we would like to encourage in our games.

Tomorrow's game will be very different from what you're used to. To give you some time to prepare, we are telling you the rules in advance.

There are 1000000 balloons whose values you can download here. These balloons lie on a straight line. Your job is to pop these balloons in an order to get the most "brownie points".

A balloon may have zero, one or two adjacent balloons. For example, a balloon at the middle of the line has two adjacent balloons. A balloon at the beginning of the line has one adjacent balloon. And if you pop the second balloon, which is the balloon to the right of the first balloon, the balloon at the beginning of the line will have zero adjacent balloons.

When you pop a balloon, the "brownie points" you will get will be equal to the average value of all balloons adjacent to the balloon you pop. If the balloon you pop has no adjacent balloons, you get no points. Remember that when a balloon is popped, it is totally destroyed and you can't pop it again. And no worries, you don't have to pop all the balloons.

We have a pretty intelligent robot here. It is currently partying inside a soundproof cell. Tomorrow it will pop the balloons on your behalf.

The robot, albeit intelligent, has no knowledge of the values of the balloons. It has knowledge of all programming languages in existence. Before the robot pops the balloons, you have to give it some code that when executed, outputs a sequence of balloon indices. You are allowed to use either 0-based or 1-based indices. If after finishing the instructions the robot doesn't get the most "brownie points" possible on your behalf, you are disqualified. But if the robot successfully gets the most "brownie points", your score will be the length of the code you give the robot. The shorter, the better! This is code-golf!

Summary

• The array of balloon values is fixed in advance.
• You write a program that outputs the optimal sequence of balloons to pop.
• Shortest code wins.

Tips

• The array of values is randomly generated with a CSPRNG and there is no meaningful way to compress it. However, the sequence of balloons has several important patterns that you can exploit.
• There are many optimal sequences, choose the sequence that is the easiest to compress.
• Remember you don't have to pop all the balloons.
• Your code may be too large to fit in an answer. You can host your code elsewhere, and your answer can contain an explanation of how you come up with the code.

Answer 6

Is it a plausible chess move

Answer 7

I'm Lost!

code-golf radiation-hardening

---

Lost is a 2d esolang where the instruction pointer starts at a random location. In this challenge, we'll replicate that for every language.

Your task is to write a program, which can be shifted any number of characters (these will be moved from the start to the end), and will still work. The program should print the string Which way is , followed any consistent string of your choice which is at least four characters, and a question mark.

Example:

Say my program is:

import print

print("Which way is Boston?")

What actually gets run might be:

port print

print("Which way is Boston?")im

(assuming there's no trailing newline)

Or:

print("Which way is Boston?")import print

Or:

ay is Boston?")import print

print("Which w

All of these must print the same, correct string.

Sandbox: I'm considering making the challenge to print how many characters your program was shifted by, but I'm worried that'd be impossible

Answer 8

Compute Pi using pure arithmetic fastest-coderestricted-sourcepythonpi

This is a sequel to the challenge Primality testing formula.

Given a positive integer \$ n \$ as input, write a Python 3 function or program that outputs the first \$ n \$ digits of Pi as an \$ n \$-digit decimal integer using pure arithmetic. This means that your source code can only contain:

• operators =, +, -, *, **, //, %, <<, >>, &, |, ^, ~, <, >, <=, >=, ==, !=
• variables
• integer constants
• parentheses ()
• semi-colons/newlines (to separate statements)

Unlike with the other challenge, you may use = if it helps speed up or simplify your code. However you may not use loops, built-ins, or anything else that's not stated above. Yes, it's possible.

Scoring

The winning criterion for this challenge is fastest-code. You will be scored on the highest \$ n = 10^b \$ your code can compute in one minute. The time taken for that run will be used to break ties.

Hardcoding to prioritize certain test cases is not allowed, and the code must work in theory for all positive values of \$ n \$.

Test Cases

  n | output
----+--------
  1 | 3
 10 | 3141592653
100 | 3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067

Answer 9

Let's start with a fairly innocuous definition of a polygon:

A polygon is a set of points \$P\$ in Euclidean space and set of edges each having two distinct endpoints in \$P\$, such that the edges form a single cycle.

We will define a regular polygon then as:

Take each edge of the polygon and divide it into two halves of equal length. The polygon is regular if for any pair of half edges, \$A\$ and \$B\$, there is an isometry of ambient space that maps every half edge to another and maps \$A\$ to \$B\$.

This can informally be phrased as "no two edges or faces are distinguishable by anything other than absolute position". You may also hear the common phrasing "all edges are the same length and all angles are equal".

Now the astute among you will be quick to point out that while this allows for what we normally consider polygons it also includes so called "star-polygons" such as the pentagram:

These edges intersect each other, but we didn't forbid this. So by the definition this is a valid 5-sided polygon.

These sort of edge cases are sort of common knowledge. However the even more astute among you may have noticed a much stranger loophole. I said "Euclidean space", not "2-dimensional Euclidean space".

Skew polygons

So can we make new polygons in higher dimensional spaces? Yes, for example here's a regular 6-sided polygon in 3D space:

Image curteousy of Polytope wiki user Sycamore916, CC-BY-SA-4.0

It turns out for example we can take any even sided polygon and raise half of its vertices up out of the plane to get a "skew" version of it that is 3D. And in 4D we can do even stranger things.

Challenge statement

The challenge is going to be to count these skew polygons. You are going to take an integer > 2 and output a list \$a\$ where \$a_d\$ represents the number of distinct regular polygons in \$d\$ dimensions.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Definitions

In order for this to work we must add 2 more definitions, the first is what makes two polygons distinct and the second is the dimension of a polygon.

A polygon in \$d\$ dimensions is a polygon such that the affine span of its vertices is a \$d\$-dimensional subspace.

For example the following vertices form a triangle:

$$ (1,0,0)\\ (0,1,0)\\ (0,0,1) $$

Each coordinate is given in 3D, however the polygon itself is 2D since all of its vertices lie on the same plane.

Two polygons \$A\$ and \$B\$ are the same if there is an invertible linear transform taking \$A\$ to \$B\$. Two polygons are distinct if they are not the same.

For example the skew hexagon discussed earlier can be stretched vertically by any positive factor. These do not count as distinct polygons since stretching is an invertible linear transform. However the skew hexagon is distinct from the normal planar hexagon since the stretch factor would be 0, and that linear transformation is not invertable (you cannot divide by 0).

Very nicely these two definitions coincide so that if two polygons have different dimensions they are automatically distinct, so there is no ambiguity as to how to count them.

Test cases

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

Spoilers

Here's the part where I would explain where the magic numbers come from.

Answer 10

Monopoly, But its in Creative Mode (sort of) koth

Disjointed Monopoly (?)

Starting Grid: 8x8 grid:

+--+--+--+--+--+--+--+--+
|XX|  |  |  |  |  |  |XX|
+--+--+--+--+--+--+--+--+
|  |+1|  |  |  |  |+1|  |
+--+--+--+--+--+--+--+--+
|  |  |+2|+1|+1|+2|  |  |
+--+--+--+--+--+--+--+--+
|  |  |+1|x2|x2|+1|  |  |
+--+--+--+--+--+--+--+--+
|  |  |+1|x2|x2|+1|  |  |
+--+--+--+--+--+--+--+--+
|  |  |+2|+1|+1|+2|  |  |
+--+--+--+--+--+--+--+--+
|  |+1|  |  |  |  |+1|  |
+--+--+--+--+--+--+--+--+
|XX|  |  |  |  |  |  |XX|
+--+--+--+--+--+--+--+--+

For each group of four players (grouped randomly), we run the game above with the four players starting at the +1 squares near the corner with 20 dollars each.

To ensure that no player is left over, each entry will be run four times. It is possible that two or more will compete against each other, but the grouping is random. (The order is also random.)

Objective: Eliminate all other players.

All players that has to pay more money than they can are eliminated.

(For all random numbers / choices, assume equal probability.)

We choose a random position and a random number of steps 1 ~ 4, and the bot moves in that directions. The map wraps around. Then, if the bot steps on...

• a Player: That player is eliminated instantly, and you do not execute the current square action.
• someone else's Property: Pay that someone the ammount equal to 2^rank dollars. rank is the rank of the property.
• your own Property: Choose whether to upgrade the property rank by 1 costing you 2*2^rank dollars. rank is the current rank of the property.
• any Utility station: get 2*rank dollars, and the utility station automatically upgrades its rank by 1.
• corner of Board (XX): Lose 20% of your money, rounded down.
• otherwise: Do an Action.

When you step on an empty cell (a cell not qualifying any of the above), you can do an Action. You can either:

• Build your own Property: Use 10 dollars to build a Property right here with a random integer rank between 1 and 4.
• Build your own Utility: Use 2 dollars to build a Utility station right here with a random integer rank between 1 and 4.
• Demolish a Square's structure. This will not demolish the bonus on the structure (for instance *2 and +1) and can apply to XX squares. This action has 25% probability of successing.

Demolish cost (paid even if failed):

• Property: 2*rank dollars. (Even if it is yours.)
• Utility: rank dollars.
• Other (including XX): no cost.

Bonus

Squares marked with +1, +2, and *2 have added bonus. The operations are applied to the rank when a structure is built on the square the bonus occupies. For instance, if a ranked 3 Utility is built on a *2 square, it will start at rank 6 instead. Everything else proceeds normally.

Meta: Gimme a better name for the challenge

Answer 11

Trippples

Introduction

Tripples (BGG) is a board game from the 1970s.

It is played on an 8x8 grid, and each tile on that grid (except the corner starting tiles, and four blank tiles) contain three arrows. The three arrows each point in one of eight directions (up, down, left, right; and diagonally between those). There are therefore 56 tiles, and 56 unique combinations of arrows - so each tile is unique when placed in the correct orientation.

Tiles are placed on the board, and depending on the variant of the rules being played this can either happen before the game starts (face up, either randomly or players take turns to draw and place tiles as they choose), before the game starts (face down, randomly), or over the course of the game as an alternative player action, instead of moving their playing piece.

Players start in adjacent corners and attempt to cross the board to the diagonally-opposite corner before their opponents can do so.

Players take turns, and may move their playing piece one square per turn. The interesting thing about this game is that the direction they can move is limited to the directions indicated by the arrows underneath their opponent's playing piece.

The rules are ambivalent regarding how the blank pieces are treated - either you can't go there at all, you get a second move if you can go there, or (house rule) your opponent can choose to move in any direction if you land there.

The challenge

(sandbox note: I discovered this game recently and thought it could be the basis for an interesting challenge - what the challenge is, though, I'm flexible on; so I'm happy to take suggestions. What is below is just one idea)

king-of-the-hill

Competitors write bots to play against another bot, in a Trippples competition.

*(sandbox query: which variant of the game rules is most interesting?)

A server program will provide the board state, and the competitor bot's function should return its next move.

Answer 12

Longest Tiles Combo

The New York Times has a puzzle game called Tiles on their website. This game consists of a grid of tiles, each made of multiple visual elements which are shared between tiles. The player first selects two tiles which share any visual element, removing those tiles from play. If the player then selects a third tile which matches some visual element with the second, their combo increases; they can repeat this process multiple times to increase their combo.

For example, take the following row:

The player could begin by selecting the middle and left tiles, which share the black middle square; they then could select the right tile, because the left and right tile share a purple square and a light blue background.

---

In this challenge, the grid of tiles will be represented by a list of tuples, where each tuple contains the same number of symbols; each symbol represents a visual element on the tile. For example, the above could be encoded as

[("light blue BG", "purple square", "small black square"), 
 ("orange BG", "purple circle", "small black square"),
 ("light blue BG", "purple square", "small black diamond")]

Note that for all of the tuples, the elements will be described in the same order -- e.g. the background will always be the first item in the tuple.

You can decide the set of symbols which are used; in the examples below, I'll use integers instead of strings, e.g.

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

The input format is flexible; for example, since order doesn't matter, you could use a set instead of a list, and instead of tuples you could use lists, strings, or sets.

Given the input as above, your goal is to output an integer indicating the largest possible combo length possible. You can assume there will be at least one matching pair of tiles -- i.e. the max combo will be at least one.

Test cases

Input	Output
[(0), (0)]	1
[(0), (0), (1)]	1
[(2, 4), (2, 3), (2, 5)]	2
[(1, 2, 3), (4, 5, 3), (1, 2, 6)]	2
[(9, 1, 14), (9, 17, 5), (3, 10, 14), (0, 13, 11), (16, 13, 6)]	2
[(4, 3, 1), (8, 0, 2), (7, 6, 2), (8, 6, 5), (4, 6, 2)]	4
[(16, 8), (12, 8), (15, 17), (18, 5), (12, 6), (0, 5)]	2
[(5, 1), (2, 9), (3, 15), (11, 0), (5, 9), (2, 14)]	3

Here's some very inefficient code to generate your own test cases.

Standard loopholes are forbidden. Since this is code-golf, the shortest program wins.

Answer 13

What is possible with all these blocks?

In this challenge, you will write code (in any way) that outputs the number of permutations of all sub-tuples of a tuple of length \$n\$ (also A000522(n) ). Here’s an example:

You have three blocks. You can start by counting how many arrangements of three blocks are possible (6). Then, work out how many ways there are to arrange two blocks (2) and multiply that by the number of unique pairs of blocks you can pick from the three blocks (3) to get the sub-answer (6). Then, work out how many ways you can arrange 1 object (1) and multiply that by the number of unique blocks you can pick from the three blocks (3) to get the sub-answer (3). Then, remember the number of empty combinations (1). Add those together to get the answer (16).

This is code golf, so shortest answer wins!

Answer 14

https://chat.stackexchange.com/transcript/message/63012181#63012181

Make a 0-byte metagolfscript solution that outputs its name.

Shortest name wins.

Answer 15

Landmine Number V

Answer 16

Compute 0.1+0.2+0.3+...+0.8+0.9+0.10+0.11+0.12+...+0.[n]

Test cases

10  -> 4.6
25  -> 7.3
64  -> 24.85
256 -> 81.496

Sandbox Note

Dupscanner

Answer 17

Challenge

Create a program that, when entered two numbers A as a numerator and B as a denominator, generates a list of equivalent fractions based off the fraction A/B.

Definition

Equivalent fractions are any set of fractions that equal the same when converted to a decimal number. Example: 3/6 (three sixths), 2/4 (two fourths) and 1/2 (one half) are equivalent fractions, since each fraction equals 0.5 when converted to a decimal number.

Rules

• Generate only the equivalent fractions with denominators smaller than B. Do not generate equivalent fractions with decimal points or negative numbers.
• Your output must look like this: (This example is for entering 10 as A and 20 as B)

1/2 2/4 3/6 4/8 5/10 6/12 7/14 8/16 9/18 10/20

• If you cannot generate equivalent fractions with denominators smaller than B, output A/B itself: (This example is for entering 1 as A and 2 as B)

1/2

• The answer with the lowest amount of bytes wins.
• You may use any programming language of your choice.

Answer 18

Is it a valid Go type?

code-golfsyntaxparsingdecision-problem

Answer 19

Separate two points in a topological space

Answer 20

2D Percolation Model

Per Wolfram MathWorld: "Percolation theory deals with fluid flow (or any other similar process) in random media."

The model is a 2 dimensional lattice whose edges are either "open" or "closed" with probability p in [0,1]. At a percolation probability P, each edge will be evaluated to be open or closed based on if P>p. Connected vertices compose a "cluster". For display purposes, clusters are often colored or otherwise uniquely denoted. An example of a percolation model is shown below:

3x3 Lattice

       Lattice                 Lattice with random 
                                edge values shown

 o ------ o ------ o           o -0.12- o -0.99- o
 |        |        |           |        |        |
 |        |        |          0.75     0.09     0.52
 |        |        |           |        |        |
 o ------ o ------ o           o -0.46- o -0.23- o
 |        |        |           |        |        |
 |        |        |          0.39     0.12     0.85
 |        |        |           |        |        |
 o ------ o ------ o           o -0.97- o -0.23- o

Percolation at P = 0.1, 0.5, and 0.9 yields 4 clusters

       P = 0.1                    P = 0.5                   P = 0.9

 o ------ o ------ o        o        o ------ o        o        o ------ o
 |                 |        |                 |                           
 |                 |        |                 |                             
 |                 |        |                 |                           
 o ------ o ------ o        o        o        o        o        o        o
 |        |        |                          |                        
 |        |        |                          |                        
 |        |        |                          |                        
 o ------ o ------ o        o ------ o        o        o ------ o        o

Vertices named according to cluster

P = 0.1                      P = 0.5                    P = 0.9

A A A                        A B B                      A B B
A A A                        A C B                      C D E
A A A                        D D B                      F F G

Challenge

Given a side length n and percolation probability P, create a percolation model of lattice size n x n with vertices displayed according to the cluster they belong to. The shortest code wins!

Inputs

The model shall take two inputs: n, P

1. n is the side length of the lattice
2. P is the percolation probability

Output

The model shall return an n x n display of vertices. Its a model so readability is important! List of lists, arrays, or pretty printing is allowed so long as there are n rows and n columns. Vertices shall have alphanumeric names of the same length to ensure readability. Edges need not be shown.

Rules

1. Cluster names shall be unique
2. The model shall be able to compute any percolation phase state from P = 0 to P = 1

Answer 21

Compressed UTF-8

Answer 22

Periodicity of the family of sequences s(n) such that n(x) is the first number co-prime with the previous n elements code-golf

The sequence of all numbers coprime to the previous is all natural numbers. This is OEIS 000027:

1, 2, 3, 4, 5, 6, 7, 8...

The sequence starting with 1, 2, and where the n-th term is the first number coprime to the previous 2 in the sequence, is periodic with period 6 (2x3). This is OEIS 047255

1, 2, 3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23

If you take the first number coprime with the previous 3 terms, you get a sequence periodic with a period of 210 (235*7). This is OEIS 062062

1, 2, 3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 22, 23, 25, 27, 28, 29, 31, 33, 34, 35, 37, 39, 41, 43

Your task is, given a number N output the periodicity of the co-prime sequence taking the last N terms.

As stated, the first elements of this sequence are:

1, 6, 210

The fourth is unknown, yet your program, given enough time, should in theory calculate it. It is known to be at least 245,589. It should not be extremely hard to calculate, just nobody has tried yet.

MathJax test, please ignore: \$abc\$

Answer 23

Complex logarithm

We have challenges for the regular real logarithm and the matrix logarithm, but we do not yet have a challenge for computing the logarithm of a complex number.

...

I will add a challenge body if there is interest

...

Rules

• You may chose which logarithm of the import you return as long as the imaginary parts for any two returned values differ by at most \$2\pi\$
• Please add built-in solutions to the community-Wiki post
• ... More rules will follow
• This is code-golf the shortest solution in bytes wins

Meta

• Is this different enough from the other two challenges ?

  As far as I can tell most (no built-in) algorithms used in these challenges break when applied to complex inputs

• Would there be interest in solving this challenge ?

Answer 24

When is My Holiday?

Background

I recently learned of a holiday, that occurred on August 20, 2023 and August 12, 2022. This got me wondering how on earth they were determining which day this holiday falls on.

The Challenge

In this challenge you will be given two dates which are from the same month but different years as input. You must construct the simplest possible description which applies to both dates.

Descriptions must be structured in a particular way. First, there are types of days

type	cost
day	1
Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday	1
weekday, weekend day	1
day which is a multiple of \$N\$	\$N\$

For the following we'll let \$D\$ be some type of day. We then have modifiers and constants.

modifier	constant
the nth \$D\$ after	the nth \$D\$
the nth \$D\$ before	the nth to last \$D\$
the nearest \$D\$ to

A valid description consists of 0 or more modifiers followed by a single constant. The simplest description is the one with the lowest cost, which is the sum of the cost of each \$D\$ which appears in the description.

For the purposes of this challenge we define "nearest" to mean "nearer than all others" so if there is a tie, then neither day is nearest and the description is not valid. "Nearest" may include the day itself. "Before" and "after" do not include the day itself.

I/O

Standard I/O rules apply, the dates may be taken in any reasonable format. And since the challenge is not about supposed to be about date calculation you may choose to take in data about the month surrounding each day. Some examples of valid input formatting are as follows. A program would take two such inputs.

2023-08-22

8/22/23

22.8.23

[[xx, xx, 01, 02, 03, 04, 05]
 [06, 07, 08, 09, 10, 11, 12]
 [13, 14, 15, 16, 17, 18, 19]
 [20, 21, 22, 23, 24, 25, 26]
 [27, 28, 29, 30, 31, xx, xx]], 
[3, 2]

You may assume any input given will have a solution. Your description need not apply to all years, just the ones in the input (eg. August 2023 has no 5th monday, but "the 5th monday" is still correct for 2021-08-30, 2022-08-29). If two or more descriptions tie you may output any or all.

Output the elements as seen in the tables above separated by spaces.

Test Cases

These test cases follow the YYYY-MM-DD input format

2022-07-04, 2023-07-04 -> the 4th day
2021-08-30, 2022-08-29 -> the 5th monday
2022-08-12, 2023-08-20 -> the 1st day which is a multiple of 4 before the 3rd Monday

code-golf calendar

---

How clear is this?

Should I be more lenient on output? (allow encoding schemes)

Yes I'm going to add more test cases.

Answer 25

Calculate equal, winning or losing trades in chess

For this challenge, assume you are playing white

---

Given two arrays containing all white and black chess piece positions on a chessboard, output if a given square is a equal, losing or winning trade. If there is no trade for a giving square, output something else.

• An equal trade happens when both black and white can lose the same amount of material in a given square

• A winning trade happens when white loses less material than black in a given square.

• A losing trade happens when white loses more material than black in a given square.

---

Example

Input: 
Black -> ["Ra8", "Bc8", "Qd8", "Rf8", "Kg8", "Nd7", "Ne7", "Bg7", "a6", "b5", ...
White -> ["Rd1", "Rf1", ...
Target -> "d5"

Output: Equal Trade

Visually would be:

---

Meta

• Would this be interesting?
• I'm not sure If I should allowed dynamic calculations or no. For example in the previous image, for square f5, there would be an equal trade since pawn attacks f5 square and if it takes, bishop will now be able to attack f5 square

---

I will add more examples later...

Answer 26

BB⁻¹(TREE(3))

Construct a Turing machine with tape alphabet {0, 1} that, starting on a tape filled with 0, it halts with at least TREE(3) 1's. Least states wins.

Notes

As math scat mentioned, this is asked in math stackexchange, but such a question may fit better here LOL

Answer 27

Return every possible program with positive probability

Write a program or function a (subset of a) Program language of your choice that returns every possible Program in the same Language with a positive probability

Rules

• You are allowed to take a stream of random bits as input
• Each program in your language has to have a positive probability to appear
• All returned programs have to be syntactically correct (META: might need further clarification)
• If in your language every string satisfies the above condition, consider using a different language

code-golf random

Meta

• Would this be an interesting challenge/ is this a duplicate?

• Should I add minimum language requirements (Turing completeness...)?

• Is "syntactically correct" clear

• Possible variant with more clear definition:
  "Generate every python program"

Answer 28

Simulate Feedback Scheduling on a Uniprocessor

Alternatively, exploiting university course content for code golf reputation

Like round robin scheduling, Feedback Scheduling is a way to schedule ready processes in an operating system. And like round robin scheduling, it runs processes for a certain amount of time (quantum), interrupted after that time (if not yet finished), and then added back to a ready queue for another round.

However, the key difference is that as a process repeatedly goes through the ready queue, it gets a longer quantum¹. This can be compared to having multiple ready queues and processors daisy-chained as so:

In the diagram, the first ready queue sends its processes to the first process to run for some time \$k\$. If the process finishes in this time, it is released. Otherwise, it is sent to the second ready queue, which has a quantum of \$2k\$.² The second ready queue sends its processes to the second processor to run for some time \$2k\$. Once again, if the process finishes in this time, the process is released. Otherwise, it is sent to the third ready queue. This generalises all the way down to the nth ready queue, which has interrupted processes sent back to itself. That is, it gets readded to the nth ready queue in a loop.

As this is a uniprocessor simulation, there's only one processor, so the concept of daisy-chaining multiple processors doesn't really work³. However, this can be simulated by using process priorities. Indeed, a higher priority process would be in one of the higher ready queues (closer to the first ready queue). A lower priority process would be in one of the lower ready queues (closer to the nth ready queue). A process with priority \$n\$ will be executed for \$n k\$, where \$k\$ is the quantum.

The priority only changes how long a process is executed. It does not change the selection order of the ready queue - that's still a first-come first-serve selection method. Processes arrive with a priority of 1, so as to not have any processes running for 0 time units.

The Challenge

Given a list of [int, int] (both > 0), as well as a base quantum, and a maximum priority, return a list of int representing the order that processes were executed. Assume that all the processes arrive at the same time.

The list of [int, int] represents a (simplified) list of processes. The two ints are the process id and service time (the time the process needs to fully run). (The priority is to be handled by the program, as all processes start with priority 1).

For example:

[[1, 5], [2, 10], [3, 3], [4, 12]]

Represents the following processes

Process ID	Service Time
1	5
2	10
3	3
4	12

The base quantum is how long each priority runs, before priority multiplication. The maximum priority represents the priority at which processes loop back into the same quantum.

Worked Example

Using the above process list ([[1, 5], [2, 10], [3, 3], [4, 12]]), a quantum of 4, and a maximum priority of 4, the process execution order will be:

TODO: Worked example at a time that isn't 11:39pm

Rules

• Input can be taken as list[list[int, int]], int, int, list[int], list[int], int, int, or some other reasonable input method.
• The processes, quantum and maximum priority can be taken in any order.
• For example:

list[int: processIds]
list[int: serviceTimes]
int: quantum
int: maximumPriority

or

int: maximumPriority
list[int: serviceTimes]
int: quantum
list[int: processIds]

or any other combination.

• Output can be list[int], str (joined on newlines, or spaces, or any constant delimiter) or some other reasonable output method.
• There will always be at least one process.
• The process ids list will always be a permutation of the range [1, number of processes].
• The process ids can be 0-indexed if you want it to be for some reason. Using 0-indexing, the ids list will always be a permutation of the range [0, number of processes].
• The order of the process ids list is important - processes are executed in the order they arrive (in a first come first serve manner). That is how the ready queue in an actual FB simulation works after all (FCFS selection strategy, with pre-emption on time quantums).

Test Cases

TODO: Write

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

Sandbox Meta

• Does the description I've provided make sense? It's not verbatim how FB scheduling works, but it's a simplification to make code golfing it not as tedious as it could be.
• Because I don't have a worked example/test cases yet, some parts might not make sense.

---

¹ Some variants of Feedback Scheduling use constant time slices for all quantums. However, this challenge will assume a variable time quantum, so as to provide fairness to longer processes.

² The factor of 2 is arbitrary. It could be any integer > 1.

³ At least, not with the simplification provided for this challenge. In practice, it might still work.

Answer 29

Sokobunny I

Answer 30

Roll a ball down an array

You are in a frictionless environment in a vacuum. Obligatory XKCD

You are given a inertialess, sizeless point mass which you have to roll down a slope. The ball starts with 0 speed.

If a ball has 0 speed and is touching the ground, it gains 1 speed in the direction of the lowest adjacent point. If both adjacent heights are the same, add 1 speed in the direction last traveled. When a ball changes direction, subtract 1 speed after the change. (This ensures that no loops occur)

The ball gains or loses speed based on the difference between the ball's current height, and the end height. A ball moves to the lowest possible square where the speed obeys the formula. $$(speed+1)^2 < (h-newh)^2 + (idx-newidx)^2$$

Given an array of integer heights, return the steps for the ball to settle/escape.

Ball Speed-move diagram

     . 4 4 4 .
   4 4 3 3 3 4 4
 . 4 3 2 2 2 3 4 . 
 4 3 2 1 1 1 2 3 4
 4 3 2 1 O 1 2 3 4
 4 3 2 1 1 1 2 3 4
 . 4 3 2 2 2 3 4 .
   4 4 3 3 3 4 4
     . 4 4 4 .

Examples:

[5,3,2,1,2,4] -> 5


Diagram:     Ball SPD = 1 Ball SPD = 2 Ball SPD = 3 BALL SPD = 1 Ball ESCAPED!
0            1            2            3            4            5
()           x\
55           55()         55 x         55           55        () 55         x
55        44 55        44 55()      44 55 x`\,   44 55        44 55        44
5533      44 5533      44 5533      44 5533  ()  44 5533   x  44 5533      44
553322  2244 553322  2244 553322  2244 553322  2244 553322  2244 553322  2244
553322112244 553322112244 553322112244 553322112244 553322112244 553322112244

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

          SPEED 1   SPEED 2   SPEED 4   SPEED 7   BALL ESCAPED
0         1         2         3         4         5
@         x
9         9@        9x        9         9         9         
98        98        98 @      98 x      98        98        
987       987       987       987       987       987       
9876      9876      9876      9876 @    9876 x    9876      
98765     98765     98765     98765     98765     98765     
987654    987654    987654    987654    987654    987654    
9876543   9876543   9876543   9876543   9876543 @ 9876543 x 
98765432  98765432  98765432  98765432  98765432  98765432  
977654321 977654321 977654321 977654321 977654321 977654321

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

 0 1 2
[2,1,2] -> 3

 0 1
   2
   0 (Loses 1 speed due to the direction change)

[2,1,3] -> 4

Questions for sandbox:

• How many more test cases should I add?
• Are there any inconsistencies or rules that need clarification?