571
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

If you think one of your posts 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".

\$\endgroup\$
1
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    May 15 at 14:05

4691 Answers 4691

1
138 139
140
141 142
157
0
\$\begingroup\$

Compressed UTF-8

\$\endgroup\$
0
\$\begingroup\$

Worst algorithm for anything

Now, any coder worth their salt will know how to sort an array in-place in nlogntime. Most can probably figure out a way to do it in n!n time and factorial memory usage. Let's see an algorithm that tops those numbers; can you come up with a way to sort an array in up-arrow time? Can you come up with an algorithm whose O-notation contains the Graham's number series?

Rules:

  • The algorithm must solve a problem that isn't just an obfuscation of 'do a ridiculous amount of NOPs".
  • Highest O-notation in either memory usage or time wins, tie broken by the other one and then by a golfed implementation.

Discussion

I'm not sure whether I should limit this to solving a specific problem. For that matter, I don't know if this would be an interesting challenge.

\$\endgroup\$
0
\$\begingroup\$

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

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\$

\$\endgroup\$
1
  • \$\begingroup\$ Probably worth showing at least one example of n(x) for clarity's sake \$\endgroup\$ Aug 21, 2023 at 19:26
0
\$\begingroup\$

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 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 ?

\$\endgroup\$
2
  • \$\begingroup\$ Isn't the complex logarithm not unique? Which value(s) should answers output? \$\endgroup\$
    – Bbrk24
    Aug 22, 2023 at 14:20
  • \$\begingroup\$ To bsoelch: I find this challenge boring (I’ll abstain from voting because it isn’t terrible either). @Bbrk24 The term is principal natural logarithm. Real part ≔ ln | x |; and imaginary part ≔ arg(x) ∩ (−π, +π] in radians. \$\endgroup\$ Aug 31, 2023 at 18:30
0
\$\begingroup\$

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


How clear is this?

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

Yes I'm going to add more test cases.

\$\endgroup\$
0
\$\begingroup\$

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:

enter image description here


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...

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

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"

\$\endgroup\$
2
  • \$\begingroup\$ Regarding whether "syntactically correct" is clear, I'm not sure. In standard languages it's fairly clear - its compilation doesn't terminate with a syntax error (although even that might be vague if the compilation can halt earlier due to another, valid, factor). But in a lot of esolangs every finite string of characters is a well formed program, so it might give them a very very significant advantage. You should also specify whether the language your code is in must be the same as the one it outputs. \$\endgroup\$ Sep 8, 2023 at 14:56
  • \$\begingroup\$ This seems like it would be incredibly difficult for any language with moderately complicated syntax (e.g. Python), so limiting it to a language like that wouldn't likely result in any valid answers IMO \$\endgroup\$ Sep 19, 2023 at 14:46
0
\$\begingroup\$

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 quantum1. This can be compared to having multiple ready queues and processors daisy-chained as so:

enter image description here

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\$.2 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 work3. 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 , 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.

1 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.

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

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

\$\endgroup\$
0
\$\begingroup\$

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?
\$\endgroup\$
0
\$\begingroup\$

Digits of Infinity (computing A206636)

In this PDF, https://www.vixra.org outlines a way to find the last \$ n \$1, 3 digits of infinity and a method to do so.

Let us define the infinity sequence2, taking the function \$ f(n) \$.

\$ f(1) = 2^2 = 4\$
\$ f(n) = 2^{f(n-1)}\$

Starting from \$ f(3) \$, the last \$ n - 2 \$ digits are the same for all \$ f(n) \$ numbers with \$ n \gt 2 \$ in this sequence.

Your task: given an integer \$ n \$ through standard I/O, return the last \$ n \$ digits of infinity.

Input

n, an integer (or the closest to one in your language), \$ \ge 1 \$ (if 1-indexed; you can also take a zero-indexed input, but the number of digits outputted will then have to be n+1). Most programs will probably compute \$ f(n+2) \$ for the output, which is permissible (but not compulsory; I'd love to see any other creative way for large n, though no bonus points). Input will be less than or equal to the highest number n such that your program can compute in under 2 minutes.

Output

The last n (or n+1 if 0-indexed) digits of infinity (through accepted I/O).

Test Cases:

Input -> Output

1 -> 6
2 -> 36
3 -> 736
10 -> 3432948736
22 -> 8098615075353432948736

This is , so shortest answer wins!

Note: my bet is that most programs that are well-golfed will not be able to calculate these digits easily; \$ f(5) \$ has over 19000 digits! However, if your program, given infinite time, infinite memory, and unbounded integer types, can compute this, it's valid.

1. Apparently, the digits of infinity are infinite.
2. This is OEIS A206636.
3. I do not believe in this method, I just picked it out because I thought it would make for a good challenge.

\$\endgroup\$
14
  • 3
    \$\begingroup\$ Infinity is not a number. Therefore, it cannot have digits. The paper seems a bit sketchy to my knowledge of different infinities. \$\endgroup\$
    – Seggan
    Sep 14, 2023 at 15:32
  • 2
    \$\begingroup\$ What are the differences between viXra.org and arXiv.org? "Warranted or not, it has a reputation of being an alternative to arXiv for cranks and to host a lot of junk science, fake proofs or even outright nonsense" \$\endgroup\$ Sep 14, 2023 at 23:32
  • 5
    \$\begingroup\$ I would suggest it be named differently, like "A206636". This removes the dependency on viXtra. I also agree with the above, infinity is a concept, not a number, unless they are talking about p-adics, although that's unlikely. \$\endgroup\$ Sep 15, 2023 at 1:01
  • 2
    \$\begingroup\$ I'd upvote because this would be a challenge that really punishes naive approaches, due to the tetrative growth. Also, is there a limit on the inputs? Because -1 is also an integer, and so is 2^127-1 \$\endgroup\$ Sep 15, 2023 at 1:05
  • 2
    \$\begingroup\$ This paper shows such a violent misunderstanding of infinity it's comical. \$\endgroup\$
    – ATaco
    Sep 15, 2023 at 1:16
  • \$\begingroup\$ Alright, everyone; I don't actually believe that the digits of infinity can be calculated with such a simple sequence; I just chose this because I just thought the sequence was an interesting one. And yes, there is a limit; only from 1 may the inputs be passed. \$\endgroup\$ Sep 15, 2023 at 4:04
  • 1
    \$\begingroup\$ I my opinion allowing solutions that compute f(n+2) and then take the last n digits, makes the challenge less interesting. I would suggest some requirement for reasonable running time (e.g. "the program has to be able to compute the result for n=10 in less than a minute on a modern computer"). \$\endgroup\$
    – bsoelch
    Sep 15, 2023 at 11:23
  • \$\begingroup\$ Would it be allowed that the program only works up to n=18 (largest result that fits in a signed 64-bit integer), or do you require big-int support \$\endgroup\$
    – bsoelch
    Sep 15, 2023 at 17:14
  • \$\begingroup\$ @bsoelch about your earlier comment; it's a mistake with my framing: I meant that most trivial programs will do this, and it's not compulsory (that would be a non-observable requirement), and the second comment, I believe my last part makes the ruling on that clear (if your code *practically* can compute up till n=18, and theoretically can compute for any n, then it's valid) \$\endgroup\$ Sep 17, 2023 at 9:36
  • \$\begingroup\$ If infinity did indeed have digits, it would have to be an infinite stream of 0s, since it has to be a multiple of every power of 10. \$\endgroup\$ Sep 25, 2023 at 7:44
  • \$\begingroup\$ False; I could make a bigger infinity by adding 1. \$\endgroup\$ Sep 25, 2023 at 9:05
  • \$\begingroup\$ @UndoneStudios but that can’t be an infinity, because it is not divisible by 10. Infinity must be an “integer” multiple of every single number. \$\endgroup\$ Sep 25, 2023 at 10:21
  • \$\begingroup\$ You are assuming a value of infinity as a value; it is not; but the point is it cannot be an infinite stream, because that would make it indivisible by... it's a complicated topic, and that's the reason why we don't consider *infinity* to be a value, which I already explained in my earlier comment. Also, such a definition would be recursive and would include itself as well, causing issues in calculation. \$\endgroup\$ Sep 25, 2023 at 13:02
  • \$\begingroup\$ Your definition is one of multiple definitions, but it is absolutely not the definition I hold when thinking of infinity as having digits. \$\endgroup\$ Sep 25, 2023 at 13:03
0
\$\begingroup\$

really shitty sloppy wip but i just want to start this post so that i can be past the first hurdle next time i look at this. feel free to ask anything just know this is like step 0;

implement this weird algorithm which will be given a more descriptive name

here is the algorithm in js:

f = x => x.reduce((a, b) => [b, ...f(a)], [])

implement this program in your language of choice;

rules

it has to run in faster time complexity than this naive implementation, which is like, exponential i think.

shortest code wins

notes: i might make it so you only have to output the result of running this on range lists like [0 1 2 3 ... n], so only the permutation that the algorithm results in, rather than for arbitrary input, since generating the permutation is one thing and then applying it is another

\$\endgroup\$
0
\$\begingroup\$

Find an eigenvalue of a 3x3 Matrix

Write a program of function that given a 3x3 matrix as input outputs an Eigenvalue of that matrix

Examples/Test-cases:

[[1,0,0],[0,1,0],[0,0,1]]    -> 1.0
[[1,2,3],[4,5,6],[7,8,7]]    -> -0.22165260583979401
[[5,3,4],[2,6,7],[0,4,10]]   -> 1.887934888738847
[[-3,2,5],[0,6,7],[0,0,-10]] -> -3.0
[[0.2915131378594483, 0.41257765061649787, 0.9253019986284902], [0.21696836678486353, 0.5331738150906348, 0.3247753676328128], [0.20672257620794932, 0.3453811902047663, 0.4771215769253173]] -> -0.03135020654472091
[[0.2447175622890705, 0.38693057299215594, 0.8576673327257548], [0.47607062999761074, 0.1126298515845301, 0.9707452917395663], [0.7524371727807047, 0.502675518344781, 0.6725321940186385]] -> -0.2768104753672565

Rules

  • You can take the matrix in any convenient format
  • The input matrix will be 3x3, the entries will be in the interval [-10,10]
  • The error of your result should be at most 10^-5
  • Your program may fail for some inputs as long as the probability of failure for a Matrix with uniformly distributed entries is 0
  • You can choose any eigenvalue as output, and may return different values on different calls
  • You are not allowed to use built-in functions that directly compute a eigenvalue/eigenvector of a matrix
  • You are allowed to use other matrix functions but are encouraged to solve the problem without matrix built-ins

Example solution in Python (non-golfed)

Uses a derivative-free variation of Newtons algorithm on the determinant

def det(M):
  return (M[0][0]*M[1][1]*M[2][2]+M[0][1]*M[1][2]*M[2][0]+M[0][2]*M[1][0]*M[2][1]-
          M[2][0]*M[1][1]*M[0][2]-M[2][1]*M[1][2]*M[0][0]-M[2][2]*M[1][0]*M[0][1])

def copy(M):
  return [[a for a in R]for R in M]

def subtX(M,x):
  N=copy(M)
  for i in range(len(M)):
    N[i][i]-=x;
  return N

def eigenValue(M):
  x0=0;x1=1;y0=1
  while abs(y0)>1e-5:
    N0=subtX(M,x0)
    N1=subtX(M,x1)
    y0=det(N0);y1=det(N1)
    x0,x1=x0-y0*(x1-x0)/(y1-y0),x0
  return x0

Attempt This Online!


Meta

  • Is this duplicate/ and interesting question ?
  • Is my explanation clear ?
\$\endgroup\$
0
\$\begingroup\$

Interpret a Turing Complete (strict) Subset of your Language

  • Write a program which can interpret some programs exactly the same way as your language, where these can be used to model any computation.
  • Demonstrate how to do this.
  • Your Interpreter may have features your language doesn't have, but your demonstration may not use them.
  • You may not use a built-in which interprets the source language, like eval()

The feature set does not need to be made of characters or something, you just need to say what it is.

It's [code-golf] until i can think of something better. how do you do tags in markdown?

Example: a javascript interpreter which only allows String.replace, functions, and the ternary conditional thing ? : may be able to be used as a convoluted slashes emulator.

Discussion:

  • This challenge was originally intended to make all languages equally interesting, but I think it still favors turing tarpits and golfing languages.
  • As with many Challenges which already exist, this one also gives actually interpreted languages kind of a leg up.
  • Making it illegal for turing completeness to arise from interpreter quirks is propably not that important. (like, ACE in my brainfuck interpreter?)
  • Banning eval might introduce rules-lawyering on what eval actually is, like, are Regexes allowed? is a built-in which evaluates arithmetic allowed? I'd say yes. It might also further favor turing tarpits, though it would nerf golfing languages which propably have an eval construct. It might also make the program more laborious to write, obviously, but
  • Allowing eval might make writing the program boring as well, as that's an established technique.
  • Making this [code-golf] is boring, maybe i should make it about the conciseness of an example program? It wouldn't devolve into HQ9+, but its discriminatory, like how is slashes supposed to calculate a factorial?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to cgcc, and interesting idea. Can you define "useful" more (maybe even formally)? Also, don't forget to add a winning criterion (such as code-golf) \$\endgroup\$ Sep 26, 2023 at 21:11
0
\$\begingroup\$

This is my first time here, as this was originally a pure math question that I figured would be more likely to be answered on this site.

Chaitin's incompleteness theorem states that for any theory whose axioms can be computed by a computer program (e.g. Peano arithmetic, ZFC, etc.), there exists a explicit number such that the theory cannot prove that any specific sequence of bits has Kolmogorov complexity larger than that number if the theory is consistent. That is, if the theory is consistent, one cannot prove in this theory that any program which computes this explicit sequence of bits must be of length at larger than this number.

One doesn't really have to know too much about computation theory to do the golfing exercise - the proof of Chaitin's incompleteness comes from the computer program which computes the shortest proof that some explicit number has complexity larger than N. If N is larger then the length of this program, then one has a length at most N program which computes a number which provably cannot be computed by a program with length at most N.

The task I am proposing is to design a Turing tarpit (which doesn't explicitly refer to Peano arithmetic) such that Peano arithmetic cannot prove that any output takes more than a N bit program to compute, for the smallest N. I'm pretty sure N cannot be more than a couple thousand bits, and it's probably the case that it's on the order of a couple hundred bits.

(Note that Peano is implied by second order Peano, which can be formulated with a finite number of axioms, so you don't have to worry about making programs to generate all of the infinite axioms of Peano arithmetic)

\$\endgroup\$
7
  • \$\begingroup\$ Welcome to CGCC! While this is fine for the sandbox, before posting you should take a look at some challenges and make your formatting more alike to them. Regarding the challenge itself - I believe (although I don't know enough logic to prove) that there are programs which PA can't prove don't output any particular output. What prevents if code=="A": run such a program else: run code as python, which gives \$N=1\$? \$\endgroup\$ Oct 16, 2023 at 3:29
  • \$\begingroup\$ This doesn't quite work, as this doesn't give a witness to PA not proving that any program has Kolmogorov complexity larger than 1. After all, PA does prove that some machine has Kolmogorov complexity is larger than 1 since PA should decide what the first two programs in basically any language output. Sufficient conditions for such a witness is that the program, if it terminates, outputs a number, you can prove PA proves this number has complexity larger than N, the program must halt whenever there is such a proof for any number, and the program is of size at most N. \$\endgroup\$ Oct 16, 2023 at 3:57
  • \$\begingroup\$ But if there's a program which PA can't prove anything about its output (which is hardcoded as part of the language, so a single byte A runs it) than it couldn't prove any string has a larger complexity, because that implies A doesn't output it which PA can't prove \$\endgroup\$ Oct 16, 2023 at 4:15
  • \$\begingroup\$ Ah ok, yeah that's what I meant about the language not referring to PA or any other specific theory explicitly. \$\endgroup\$ Oct 16, 2023 at 4:43
  • \$\begingroup\$ This seems hard to define properly, because there are problems (like Goodstein's sequences) which don't refer to PA but PA still can't prove, and it seems likely there are problems like that of the format we want. \$\endgroup\$ Oct 16, 2023 at 4:49
  • \$\begingroup\$ I wanted to use PA for concreteness, but a version without a naturality requirement would be one where the program adjustable for any theory encoded by a first-order sentence. I think the alternative of requiring an actual witness program of the form of the second comment also allows dropping naturality since encoding the meaning of 'A' into arithmetic would be complicated enough to waste bits. \$\endgroup\$ Oct 16, 2023 at 5:00
  • \$\begingroup\$ In particular, since a programming language must be computable, the only way PA might not prove anything about the output of 'A' is if the program assigned to 'A' doesn't terminate. In this particular case, it must halt whenever PA is inconsistent, so it's some explicit function applied to the first proof of inconsistency. Thus, we have a explicit function of the first inconsistency of PA such that it's provable in the base theory (PA or Q) that if PA can prove that this function is not any explicit number, then PA is inconsistent. This might be impossible, and surely can't happen naturally. \$\endgroup\$ Oct 16, 2023 at 6:13
0
\$\begingroup\$

Seat people as far as possible

Imagine there are \$n\$ people \$\{a_1, a_2, \ldots, a_n\}\$ who enter a room in order and sit down in \$n\$ seats, arranged in a row. However, all of these people hate social contact, so they want to sit as far away from each other as possible; specifically, they sit in the set which maximizes the minimum distance from anyone who is already seated. They break ties by sitting in the seat furthest to the left. For example, suppose \$n=5\$. Then the people will sit down in the following order:

_ _ _ _ _ 
1 _ _ _ _ 
1 _ _ _ 2
1 _ 3 _ 2
1 4 3 _ 2
1 4 3 5 2

Your challenge is, given a positive integer \$n\$, output the final arrangement of \$n\$ people in \$n\$ seats as described above. You can start the numbering of the people from 0 or 1.

Test Cases

(In these examples, numbering starts at 1.)

0 []
1 [1]
2 [1, 2]
3 [1, 3, 2]
4 [1, 4, 3, 2]
5 [1, 4, 3, 5, 2]
6 [1, 4, 3, 5, 6, 2]

Standard loopholes are forbidden. As this is , shortest program wins.

Questions

Has this been done before? It feels like would have been (or it reduces to some problem which has been done before), but I don't know how to find out.

\$\endgroup\$
4
  • \$\begingroup\$ “Imagine there are n people {a1,a2,…,an} who enter a room in order and sit down in n seats, arranged in a row.” Wouldn’t that mean that they all have to sit next to each other, if there are exactly n seats in a row? Am I reading this wrong? \$\endgroup\$
    – noodle man
    Oct 31, 2023 at 17:11
  • \$\begingroup\$ @noodleman Eventually, all the seats will be filled, but the i-th person doesn't necessarily sit in the i-th seat -- they sit in whatever seat in the row maximizes the min distance. \$\endgroup\$ Oct 31, 2023 at 17:19
  • \$\begingroup\$ Oh, I see. So this is a slight variant of the “urinal problem”? There are a few challenges related to it, maybe there’s a dupe under a different title \$\endgroup\$
    – noodle man
    Oct 31, 2023 at 17:22
  • \$\begingroup\$ Very closely related: codegolf.stackexchange.com/q/47952/108687 This is like an easier version though so maybe it’s not a dupe \$\endgroup\$
    – noodle man
    Oct 31, 2023 at 17:26
0
\$\begingroup\$

Positions on the Pickleball Court

My doubles pickleball group often has five people. Four are playing and one is awaiting the next game. We can represent the state of the game with a string of five characters like abCde. This indicates that a and b are playing against c and d with c serving. We want to write a routine that gives the possible positions after the next rally is complete. The examples below will assume we start with this configuration.

There are four possible outcomes of a rally.

1)The serving side wins the rally but does not win the game. The players on the serving side change places and the same player serves, so we go to abdCe.

2)The serving side wins the rally and thereby wins the game. The players rotate one position right and the serve goes to the first position, so we go to Eabcd

3)The receiving side wins the rally, but the partner of the server has not served yet. The players stay in position and the serve goes to the partner, so we go to abcDe

4)The receiving side wins the rally and the partner of the server has served. The players stay in position and the serve goes to the first player of the other side, the one in first or third position. Here we go to Abcde

Your task is to write a routine that takes a configuration at the start of a rally and returns or prints the four possible configurations at the end of the rally in the order of the possibilities above. A configuration has the five characters in any order with the server any of the first four. This is code golf, so the shortest solution wins. You can use other characters and other ways of indicating the server if you wish, like digits and making the server negative or adding $5$ to the server or putting an asterisk after the server. There needs to be a clear break between the four possibilities, like a space, a newline, or separate elements of a list. You can take your input in any convenient way, as a string or array for example. The characters used should be the same on input and output.

Test cases-input first column, output the remaining four

Abcde bAcde Eabcd aBcde abCde

caBed caeBd Cabed cabEd Cabed

dBace Bdace Edbac Dbace dbAce

bcdAe bcAde Ebcda bcDae Bcdae

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice challenge. I’d suggest even more flexibility on input/output, e.g. allowing the output to be a list of lists of digits. Suggest also formatting the test cases as a code block so you have monospacing. \$\endgroup\$ Nov 1, 2023 at 23:35
0
\$\begingroup\$

UTF-8 sum of source code.

Output the sum of the UTF-8 characters codes of your source code.

Draft notes

  • Seems like there isn't that yet..

  • After some feedbacks I think this has nothing interesting or relevant. There may be a lot of answers consisting of 150 or answers in the form: print(sum).

  • Not going to post it, thanks for feedback.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ When posting this you should also make a CW of all languages 150 is an answer in. \$\endgroup\$ Nov 9, 2023 at 13:31
  • \$\begingroup\$ Do quine rules apply? \$\endgroup\$
    – Adám
    Nov 9, 2023 at 15:31
  • \$\begingroup\$ @CommandMaster thanks for the feedback, good catch, I'll do it, I'm also hope to see a language where 0 is an answer. \$\endgroup\$
    – AZTECCO
    Nov 9, 2023 at 19:39
  • \$\begingroup\$ @Adám yes thank you, I forgot to add a qune tag and rule. \$\endgroup\$
    – AZTECCO
    Nov 9, 2023 at 19:42
  • \$\begingroup\$ If quine rules apply, then a 0 score answer is impossible. Is that intended? \$\endgroup\$
    – lyxal
    Nov 9, 2023 at 22:37
  • \$\begingroup\$ @lyxal no it wasn't, I missed the 0 rule but honestly I would like to allow 0 bytes answers, is it a bad idea? Thanks \$\endgroup\$
    – AZTECCO
    Nov 10, 2023 at 7:38
  • \$\begingroup\$ Personally, I'd be all for 0 byte answers being allowed, because I already have one in mind :). \$\endgroup\$
    – lyxal
    Nov 10, 2023 at 9:31
  • 1
    \$\begingroup\$ Also, this challenge is very very similar except it's codepage values instead of utf8, and requires non empty programs: codegolf.stackexchange.com/questions/135571/… \$\endgroup\$
    – lyxal
    Nov 10, 2023 at 9:32
  • \$\begingroup\$ @lyxal yes I've seen it and honestly it's more interesting than mine. On second thought I think mine has nothing interesting.. we will have just answers of 150 as stated above and print sum or similar \$\endgroup\$
    – AZTECCO
    Nov 10, 2023 at 14:28
0
\$\begingroup\$

Literate Programming in Base 26

Sandbox questions

  • Is the source restriction interesting?
  • Is the title OK?
  • Should I use base 27 and require the words to be separated by a space?
\$\endgroup\$
0
\$\begingroup\$

Emulate a Turing Complete processor

(As opposed to a Turing-complete processor.)

In the puzzle game Turing Complete, at one stage you get to "build" a processor out of previous parts. This processor has six registers R0-R5, a program counter, an input and an output, all 8-bit. All registers default to zero. Unless changed by a condition instruction, the program counter will increment after each instruction.

There are four instructions:

  1. 0o0XY is the "Immediate" instruction. The instruction itself is copied into the R0 register.
  2. 0o1XY is the "Compute" instruction. The source registers are always R1 and R2 and the destination is always R3. Y can be 0-5 representing one of six computations, Or, Nor, Nand, And, Plus, Minus. X is ignored.
  3. 0o2XY is the "Copy" instruction. X and Y can be 0-5 representing a register or 6 representing the input or output respectively.
  4. 0o3XY is the "Condition" instruction. Y can be 0-7 representing one of eight conditions, False, Zero, Negative, Non-Positive, True, Non-Zero, Non-Negative, Positive. If the signed value in the R3 register satisfies the condition, the program counter becomes the value of the R0 register. X is ignored.

Your task is to accept a program, which is an array of up to 256 bytes (but your program can use any reasonable data type), an input stream of bytes, and the number of instructions to execute (since there's no Halt instruction and there's no guarantee that the computation will ever "finish"), and return the bytes that the program has written to its output.

You can assume that the bytes of the program will only be legal values, although you must ignore X for the Compute and Condition instructions. You can assume that the program counter will not index out of the array, although if the input array is 256 bytes then it is possible for the program counter to wrap around since it only has 8 bits.

This is , so the shortest program or function that breaks no standard loopholes wins!

\$\endgroup\$
0
\$\begingroup\$

Stairspin

Given a grid, of n x n size. The elements are indexed so:

00 10 20 ...
01 11 21 ...
02 12 22 ...
.. .. .. ...

and so on.

There is a very interesting transformation called the Stairspin: The 4x4 grid

00 10 20 30
01 11 21 31
02 12 22 32
03 13 23 33

becomes

01 00 10 20
02 12 11 30
03 22 21 31
13 23 33 32

after the transformation.

Your task is, given n and the index of an element, you must find where the element goes after the Stairspin.

Examples:

  • 4 00 -> 10
  • 5 12 -> 11
  • 3 11 -> 11

Fewest bytes win!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's generally discouraged to need to infer the spec from examples, and in this case it takes some hard staring to infer. Am I correct that the Stairspin is dividing the matrix into concentric rings, and rotating each ring clockwise? \$\endgroup\$ Nov 20, 2023 at 7:22
  • \$\begingroup\$ @UnrelatedString Yes! That's such a good description. Thank you! \$\endgroup\$ Nov 21, 2023 at 18:07
0
\$\begingroup\$

Produce a secure block cipher round function (1 bit round key; 7 bit message).

Tags: math,encryption,cryptography,linear algebra

Introduction

We are going to need new symmetric encryption functions. We are at the point where we cannot improve the performance of integrated circuits very much simply by shrinking transistors. Furthermore, we are approaching the limits of the energy efficiency of transistors using conventional irreversible computation. The only way to surpass these limits is to use reversible computation. But to get the most out of reversible computation, one needs to use algorithms that are designed for reversible computation. Since the AES encryption protocol was not designed for reversible computation, it is probably a good time for cryptographers to produce, evaluate, and standardize new symmetric encryption functions that are efficient on fully reversible hardware/software. And as a bonus, cryptographic functions are more resistant to side channel attacks when we run them on reversible hardware since irreversible computation not only leaks energy, but irreversible computation leaks some information that can be used to decipher what is being encrypted.

In addition to the need for new cryptographic functions, the rise of AI will bring rise to new cryptoanalytic techniques that can be used to better evaluate the security of block ciphers (this is my personal opinion based on my personal research). Cryptographers can also employ new techniques for evaluating block ciphers including the application of invariants that measure the level of cryptographic security of block ciphers and always give isomorphic block cipher round functions the same level of cryptographic security (this makes it impossible to artificially inflate the security value by relabeling all the possible messages and round keys). Spectral techniques are one way of assigning each block cipher or block cipher round function a specific number that measures its cryptographic security. In this challenge, we shall apply one of these spectral techniques to measure the cryptographic security of some very simple block cipher round functions.

The goal of this challenge is to produce a very simple block cipher round function that minimizes a measure of its cryptographic insecurity. Since this kind of block cipher round function has a microscopic 7 bit message size, it is subject to brute force attacks, and it will probably not have any practical use whatsoever, but we can still measure the level of its cryptographic security in various ways.

The participants in this challenge do not need to have prior experience with evaluating block ciphers and such prior experience probably will not help very much.

Spectral radius

If \$X\$ is a matrix, then the spectral radius is the value \$\rho(X)=\max\{|\lambda|:\lambda\,\text{is an eigenvalue of}\,X\}.\$ It is well known that \$\rho(X)=\lim_{n\rightarrow\infty}\|X^n\|^{1/n}\$ and this limit does not depend on the matrix norm chosen.

The spectral radius of a complex matrix \$X\$ can often be easily computed. If \$v_0\$ is an arbitrary vector and \$v_{n+1}=\frac{Xv_n}{\|Xv_n\|}\$ for all \$n\$, then \$\|Xv_n\|\$ will converge to the spectral radius \$\rho(X)\$ except in the case when \$X\$ has multiple eigenvalues with maximum absolute value.

Challenge

Produce a pair of permutations \$(P,Q)\$ of \$\{1,2,...,127,128\}\$ with the smallest associated spectral radius \$\rho((P_2+Q_2)/2)\$. The pair of permutations \$(P,Q)\$ should be thought of as the round function for a \$7\$ bit message. If the round key is \$0\$, we perform the transformation \$x\mapsto P(x)\$ to the message \$x\$, and if the round key is 1, then we perform the transformation \$x\mapsto Q(x)\$ to the message \$x\$. A lower spectral radius signifies a greater level of cryptographic security.

Let \$X=\{1,2,...,128\}\$. Let \$Y\$ be the collection of all unordered pairs of distinct elements in the set \$X\$. For example, \$Y\$ contains the pairs \$\{2,3\},\{56,57\},\{2,16\}\$ along with other pairs. The set \$Y\$ contains \$128\cdot 127/2=8128\$ elements.

If \$P\$ is a permutation of \$\{1,...,128\}\$, then the mapping \$P\$ induces a permutation \$P_0\$ of \$Y\$ defined by letting \$P_0(\{a,b\})=\{P(a),P(b)\}\$. Let \$U\$ be the real vector space generated by the basis \$Y\$. Let \$L\$ be the linear functional mapping \$U\$ to the field of real numbers defined by setting \$L(\{x,y\})=1\$ whenever \$x,y\$ are distinct. Let \$V=\ker(U)\$. Then \$V\$ is the subspace of \$U\$ generated by pairs \$\{u,v\}-\{x,y\}\$. We extend the mapping \$P_0\$ to a linear operator \$P_1:U\rightarrow U\$ by linearity. In other words, \$P_1(\alpha_1\{x_1,y_1\}+\dots+\alpha_n\{x_n,y_n\})= \alpha_1P_0(\{x_1,y_1\})+\dots+\alpha_nP_0(\{x_n,y_n\})\$ \$=\alpha_1\{P(x_1),P(y_1)\}+\dots+\alpha_n\{P(x_n),P(y_n)\}.\$ Let \$ P_2:V\rightarrow V\$ be the restriction of the operator \$P_1\$. The operator \$P_2\$ is the unique linear operator from \$V\$ to \$V\$ where \$ P_2(\{u,v\}-\{x,y\})=P_1(\{u,v\})-P_1(\{x,y\})\$ whenever \$\{u,v\},\{x,y\}\in Y\$ Our goal is to minimize the spectral radius \$\rho((P_2+Q_2)/2)\$ of the average \$(P_2+Q_2)/2\$.

Given a pair of permutations \$P,Q\$ of \$\{1,2,...,127,128\}\$, set we produce a Markov chain on the set \$\{\{x,y\}:x,y\in\{1,\dots,127,128\},x\neq y\}\$ where we transition from \$\{x,y\}\$ to \$\{P(x),P(y)\}\$ with probability \$1/2\$ and from \$\{x,y\}\$ to \$\{Q(x),Q(y)\}\$ with probability \$1/2\$. This Markov chain is associated with a double stochastic matrix \$A\$. The doubly stochastic matrix \$A\$ has spectral radius \$1\$, but the second largest absolute value of an eigenvalue of \$A\$ measures how quickly powers \$A^n\$ of \$A\$ converge to the matrix where each entry is equal to each other. In other words, the second largest absolute value of an eigenvalue of \$A\$ measures how quickly iterating steps in the Markov chain approaches the uniform Markov chain. The second largest absolute value of an eigenvalue of \$A\$ is just the spectral radius \$\rho((P_2+Q_2)/2)\$.

The averaging operator \$(P_2+Q_2)/2\$ satisfies the circular law, so the eigenvalues of \$(P_2+Q_2)/2\$ should be approximately uniformly distributed on the disk centered at zero with radius \$\sqrt(2)/2\$. Furthermore, if the permutations \$P,Q\$ are good enough, then the spectral radius of \$(P+Q)/2\$ should be approximately \$\sqrt(2)/2\$.

Computing the spectral radius

One can easily use power iteration to compute the spectral radius of a sparse matrix except for one tiny problem. The matrix \$(P_2+Q_2)/2\$ will be a real matrix, and the eigenvalues of real matrices will be symmetric around the real number line. This means that imaginary eigenvalues of real matrices must always come in pairs. Now, since the real number line has zero area and since the eigenvalues of \$(P_2+Q_2)/2\$ satisfy the a sort of circular law (but for \$(P_2+Q_2)/2\$ the eigenvalues somewhat cluster near the boundary of the disk due to the unitarity of \$P_2,Q_2\$), the matrix \$(P_2+Q_2)/2\$ is more likely to have a pair of conjugate dominant eigenvalues rather than a single real dominant eigenvalue. We can circumvent this issue by applying the power iteration technique to the complex matrix \$(P_2+(1+i\cdot \epsilon)\cdot Q_2)/2\$ and then slowly decreasing \$\epsilon\$ down to zero so that the power iteration obtains a single dominant eigenvalue/eigenvector pair for \$(P_2+Q_2)/2\$.

Format

In your answer, please specify the permutations P,Q that you use along with the spectral radius of \$(P_2+Q_2)/2\$ (which should be around \$\sqrt{2}/2\$) together with the code or algorithm that you have used to produce the permutations P,Q.

There are two ways that you can specify your permutations.

  1. You may write your permutations as tables. For example, [4,5,6,1,2,3,7,8] will denote the permutation of {1,...,7,8} where 1->4,2->5,3->6,4->1,5->2,6->3,7->7,8->8.

  2. You may also write your permutations as products of disjoint cycles. For example, (2,6)(3,7)(1,4,8,5) will denote the permutation of {1,...,7,8} where 2->6,6->2,3->7,7->3,1->4,4->8,8->5,5->1.

Sample answer (with reduced key size).

Here is a sample answer where (for simplicity) the permutation \$P\$ takes \$5\$ bits as input and out rather than \$7\$ bits (\$P\$ is a permutation of \$\{1,\dots,31,32\}\$).

P: (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26)(27,28,29)(30,31)

Q: (1,31,29,23,27,12,16,8,6,10,17,2,9,5,24,11,14,7,30,4,19,32,26,15,3,20)(13,18,21,22,28)

P: [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 1, 28, 29, 27, 31, 30,32]

Q: [ 31, 9, 20, 19, 24, 10, 30, 6, 5, 17, 14, 16, 18, 7, 3, 8, 2, 21, 32, 1, 22, 28, 27, 11, 25, 15, 12, 13, 23, 4, 29, 26 ]

Loss: 0.705873796001...

Observe that the loss is less than \$\sqrt{2}/2\$ but not by much.

We observe that the permutations \$P,Q\$ are uninterpretable, so for these permutations, no information about the algorithm used to produce \$P,Q\$ can be gained from the permutations \$P,Q\$ themselves. Here, the answerer is encouraged to post the code used for generating the permutations \$P,Q\$ or a description of the algorithm or technique used to produce \$P,Q\$.

Meta (for sandbox only)

I have already asked a couple of questions on this site, but this question is different in several regards, so I need to sandbox this question. While the spectral radius can be computed very quickly to a high degree of accuracy, it will take much computational power to produce \$P,Q\$ where \$\rho((P_2+Q_2)/2)\$ is sufficiently small. Users with greater computational power will have a slight advantage over those without such computational power. The pair \$(P,Q)\$ will also most likely contain no meaningful information about the algorithm used to obtain \$(P,Q)\$. The permutations \$P,Q\$ in proposed answers will probably look exactly like random permutations and they will probably be completely uninterpretable. Finally, the loss for a pair \$(P,Q)\$ shall be a real number rather than an integer.

If we tried to simplify the Markov chain to the Markov chain with transitions \$x\mapsto P(x)\$ with probability \$1/2\$, and \$x\mapsto Q(x)\$ with probability 1/2, then I already know how to make the the doubly stochastic matrix have characteristic polynomial \$(x-1)x^{127}\$ which means that all the eigenvalues except for one are zero, so we really do need to make the question as complicated as I have made it.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You should use MathJax, it's quite hard to read currently (note that in codegolf we use \$, not just $). You should also given a example for some \$P,Q\$ pair, perhaps smaller \$\endgroup\$ Nov 16, 2023 at 23:26
0
\$\begingroup\$

I am a big fan of the famous 10 PRINT CHR$(205.5+RND(1));: GOTO 10. This will produce a maze like pattern with random generated symbols of / and \ with a 50% chance to be printed, and indefinitely. Such like ///\/\\\//\/\/\\\\\/\///\ and so on. There already exist a book about this at https://10print.org/ which was published in 2011.

I am working at a second book, which among many other things, will show this code in as many diffrent languages as possible. The book will explain how all the codes are working. The idea to this book is to show other approaches and to bring new ideas of programming.

Therefore I call on you to realize the code in as many different programming languages as possible and please explain exactly how and why the code works. If possible, please the use "Try it online!" function. By publishing your codes here, you automatically declare that I may use the code in my book, for which I will of course cite you as the source.

The winners are those with the shortest code for each language. However, it is also a prerequisite that the code is explained at least briefly.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ I think it would make more sense for there to be one winner per language, with the winner being the submission with the shortest code (this is common for code-golf here). Also, please specify how random the decision should be. Does it have to be an exact 50% chance of / and 50% chance of \? Finally, please clarify that the program should generate characters like this forever, or until the program is terminated via user input like ctrl+C. May the submission instead be a function that returns some sort of infinite-list structure? (Many languages used on this site have similar structures.) \$\endgroup\$
    – noodle man
    Nov 19, 2023 at 15:25
  • 1
    \$\begingroup\$ Also, very very related--minus the licensing stipulation, I suppose. \$\endgroup\$ Nov 20, 2023 at 7:18
  • 1
    \$\begingroup\$ @UnrelatedString that's not the only question on this subject. There's also codegolf.stackexchange.com/q/25967/15599 where a large number of answers use this. A new question may be closed as a duplicate (and may not generate more answers than the 2 existing questions put together.) A bounty on an existing question might be a good approach, if OP had sufficient reputation to spare. See also codegolf.stackexchange.com/q/58653/15599 (given a maze of this type as input, rotate it 45 degrees.) \$\endgroup\$ Dec 16, 2023 at 3:10
0
\$\begingroup\$

Manipulate a set of pixel grids

@sandbox is this a dupe? I couldn't find one and was a bit surprised

Your code should take in one input representing a number of boolean grids and one set of manipulations for each grid, and output a new set of manipulated pixel grids.

The manipulations you must implement are:

  • a swap: two pixels which are orthogonally adjacent to each other swap places.
  • a toggle: one pixel is toggled.

The grids may be of any rectangular dimension and will have only 2 values. All grids in any one input will be of identical dimension.

Each input grid corresponds to one set of manipulations. There may be any number of manipulations for each grid, including none. A manipulation may undo what a previous manipulation did.

You may choose any format for how the input grids and manipulations must be represented.

Examples:

input: 'aa|aa|aa;a |a | a; a|  |a ;' 
2x3 grids, looks like this:
aa | a  |   a
aa | a  |    
aa |  a |  a 
manipulations: '3sa6t1t;4sb1t4t1t;;' (s[a(bove)|b(elow)|l(eft)|r(ight)]=swap at index, t=toggle at index)
output: ' a|aa|a ;a | a|aa; a|  |a ;'
gridified again:
 a | a  |   a
aa |  a |    
a  | aa |  a 

input: 
'|█ █| ██|██ |  █|
 | █ |█ █| ██|  █|
 |███| ██|███|█  |'
manipulations: 'svshttsvsv/5/8/1/7/5;tttttttttt/4/3/6/8/3/;;svshsv/5/5/5;' (s[v(ertically)|h(orizontally)]=swap; tt = toggle)
output:
'|  █| ██|██ |  █|
 |██ |   | ██|  █|
 | ██|  █|███|█  |'

, so shortest code in each language wins. valid code takes in any size grid and gives an output grid in the same format as the input with provided swaps and toggles preformed on the grid.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It’s hard to understand what you’re going for, could you please explain it more other than just by adding examples? \$\endgroup\$
    – noodle man
    Nov 22, 2023 at 18:04
  • 1
    \$\begingroup\$ @noodleman sorry, I meant to save it rather than post it so soon after the other one this morning. usually I let it sit in the editor for a couple days while I'm working on it. I'm going to sleep now but I'll look at it closer tomorrow. \$\endgroup\$
    – guest4308
    Nov 22, 2023 at 20:04
0
\$\begingroup\$

Bingo Cards

PDF version here. SVG version here.

Tags: code-golf card-games file-system

Also posted my own implementation as a benchmark and to encourage others to answer the question.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Looking at your sample solution you don't seem to be interested in the part of the code that converts the image to a PDF document, (all the work of converting the canvas to PDF is done by the library you included), so you should probably allow other image output formats (e.g. HTML, drawing to screen) to make it easier to solve the challenge in languages with less powerful / no PDF-libraries \$\endgroup\$
    – bsoelch
    Nov 20, 2023 at 11:07
  • \$\begingroup\$ @bsoelch Thanks a lot for the suggestion. I asked another question that accepts the output without requiring any file-write operations or to generate a PDF file. Also gave the link in the Sandbox post. \$\endgroup\$
    – paki eng
    Nov 26, 2023 at 1:20
0
\$\begingroup\$

Draw minimalistic southpark characters

Your task is to output or draw this image of our favorite characters. It is obviously inspired from the logo of Southpark Digital Studios, as shown here: https://southpark.cc.com/, but simplified.

original

The image has an aspect ratio of 40:12, and everything is aligned on this 40x12 grid. You must output a bitmap image of at least 40 by 12 pixels or a vector graphic.

I've enlarged this images and added thin gray lines for easy pixel counting. The background should be black, white or transparent.

enlarged version

You must use at least 12 bit color depth (4 bit per RGB channel) and these colors:

Stan:    #56a #fdb #a65
Kyle:    #f61 #fdb #3a3
Cartman: #4bc #fdb #d24
Kenny:   #f61 #743 #fdb (outer - middle - inner)

Open questions:

I want a transparent background, which is meaningless (or very difficult) if the image is show on screen.

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

Which skill to train?

\$\endgroup\$
0
\$\begingroup\$

One-dimensional map colouring

\$\endgroup\$
0
\$\begingroup\$

Night hike partitioning

\$\endgroup\$
0
\$\begingroup\$

The Challenge Challenge

Your goal is to create a challenge that has the longest possible best solution. Post it as an answer to this question, along with the shortest possible solution to that challenge you know of. The number of bytes in that solution is your score, with a higher score being better. To prevent challenges that are boring, bad, not in the spirit of the contest, made of many arbitrary steps, etc, the answer with the most votes will win.

Rules

  • You may not include special scoring in your challenge. All that matters is byte-count.
  • You may not intentionally limit the number of languages that can participate in your challenge; any language that can output and input text should be a language that your challenge could be completed in.
  • If someone finds a shorter solution to your challenge, you must update your answer with that solution once you see it.
  • Your challenge must not need links to be complete; you can't refer to a website for parts of your challenge other than to clarify. This is to prevent challenges that are too complex, with many arbitrary steps. Your solution to your challenge is not included in this rule.
  • You may not create a challenge where the goal is simply to output a piece of text ( challenges are not allowed). For example, the factorial/negation challenge is allowed, but outputting an ASCII keyboard is not.

Requirements for an answer

  • A challenge (within the answer)
  • The shortest possible solution to it (that you know of), or, if it is too long to fit, a sufficient explanation of what it that so that the program could be constructed without any difficulty.
  • The length of that solution

If someone finds an answer to your challenge with a byte count that is shorter than your answer to your challenge, that becomes your new byte count.

The challenge with the most votes wins.

Questions:

  • Looking at meta pop con questions, I think this satisfies what is needed for one of those. Are there changes I need to make here though?
  • Are there any ways I should change this in general?
  • Are there comments I haven't fully addressed?
\$\endgroup\$
9
  • \$\begingroup\$ Would a user post a new challenge as a question, then link to it in an answer to your challenge? \$\endgroup\$
    – Someone
    Dec 14, 2023 at 18:26
  • 1
    \$\begingroup\$ @Somebody I think the idea was that each answer to this challenge would contain both a spec and a solution. \$\endgroup\$
    – noodle man
    Dec 14, 2023 at 19:06
  • 4
    \$\begingroup\$ This is a cool idea, but I think it’s likely that submissions will devolve to “output the following text” with a solution that uses a built-in compression method. \$\endgroup\$
    – noodle man
    Dec 14, 2023 at 19:10
  • \$\begingroup\$ @noodleman You are right on both points. I was going to add a rule that stopped people from doing the “output the following text” thing, but forgot when I wrote it up, so I'll add that now. \$\endgroup\$
    – Jakav
    Dec 14, 2023 at 21:41
  • \$\begingroup\$ I've made changes to the question. Is this ready to post, or are additional changes needed? \$\endgroup\$
    – Jakav
    Dec 14, 2023 at 22:08
  • 1
    \$\begingroup\$ The exception you added doesn't make sense, because the linked Fizz Buzz challenge is a kolmogorov-complexity challenge. \$\endgroup\$
    – m90
    Dec 15, 2023 at 6:50
  • 2
    \$\begingroup\$ -1, I don't think there is a way to make this challenge interesting - there are too many possible challenges. For example, if someone just makes up a random composition of actions, it's quite likely there isn't a much shorter program for that. How do you even exclude something like \$f(n) = \text{some random number} \cdot n\$, and the myriad of other equivalents? \$\endgroup\$ Dec 15, 2023 at 10:11
  • \$\begingroup\$ @m90 Thanks, I'll change that. \$\endgroup\$
    – Jakav
    Dec 15, 2023 at 13:58
  • \$\begingroup\$ @CommandMaster The only way I see is to make it a popularity contest. If it isn't, I can't exclude those things. I'm not sure what changes would be needed to make it a popularity contest though, if it even is possible. \$\endgroup\$
    – Jakav
    Dec 16, 2023 at 14:24
1
138 139
140
141 142
157

You must log in to answer this question.

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