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

4629 Answers 4629

1
137 138
139
140 141
155
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\$

Factorial Numbers

Write a function or program to print "factorial numbers" as defined in this xkcd comic. Test cases are conveniently provided by the comic too.

You will take an integer number N as input.

You can either

  1. output the factorial number representation of N
  2. output the factorial number representation of all numbers up to and including N in order (note: must include N; this is different from default rules)

You can assume that the input is not "illegal", but your program must work for all legal inputs. Default loopholes and I/O rules apply. If this can be done in 1 built-in method, you may post it but it will not compete.

This is code-golf so shortest wins. The competition will be between each language, so non-golfing languages should compete.

\$\endgroup\$
4
  • \$\begingroup\$ Duplicate \$\endgroup\$
    – emanresu A
    Sep 29, 2023 at 23:59
  • \$\begingroup\$ @emanresuA ah wow. But the post is 10 years old and the newest answer is 5 years old. Perhaps there are innovations in golfing languages that make this interesting again. What can be done about this? The comic was posted yesterday too. Thanks. \$\endgroup\$ Sep 30, 2023 at 0:04
  • 1
    \$\begingroup\$ Unfortunately, the thing about good challenge ideas is that a lot of them have already been done. If you wanted to raise interest in that challenge you could post an answer to it. \$\endgroup\$
    – emanresu A
    Sep 30, 2023 at 0:09
  • \$\begingroup\$ Thanks. I might try that. \$\endgroup\$ Sep 30, 2023 at 0:12
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\$

I'm building a Code-Golf type game for an authorization language. The premise is to review a piece of an authorization policy and the permissions to identify the least number of rules you need to create in order to keep the permissions true.

Example of one policy and two permissions below. What are Alice and Anthony's roles?

  • Alice can read Organization metaworldpeace
  • Anthony can add_member Organization metaworldpeace

actor User { }

resource Organization { 
    roles = ["admin", "member"];
    permissions = ["read", "add_member"];
# role hierarchy:
# admins inherit all member permissions
"member" if "admin";

# org-level permissions
"read" if "member";
"add_member" if "admin";

   

\$\endgroup\$
3
  • \$\begingroup\$ ??? i cant see what this has to do with code golf \$\endgroup\$
    – Seggan
    Nov 10, 2023 at 18:32
  • 1
    \$\begingroup\$ @Seggan It's underspecified, but does seem like an atomic-code-golf. \$\endgroup\$ Nov 10, 2023 at 18:34
  • \$\begingroup\$ Or perhaps a metagolf...? \$\endgroup\$ Nov 10, 2023 at 18:46
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\$

Pi to n digits

Calculate \$π\$ to n digits - no overshooting. The input will be a positive integer or 0. Your program should output \$π\$ displayed with exactly n digits (not counting '3.'). You cannot use any function that uses or returns pi under the hood. Standard loopholes are not allowed.

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

\$\endgroup\$
3
  • \$\begingroup\$ Does this have to work with arbitrarily large values of n if supported by the language? e.g. does a Python answer have to work for n=99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999989999999999? \$\endgroup\$
    – Someone
    Dec 7, 2023 at 2:33
  • 2
    \$\begingroup\$ This seems like a dupe of Calculate 500 digits of pi, requiring the number of digits to be variable wouldn't affect answers interestingly in my opinion. \$\endgroup\$ Dec 7, 2023 at 6:54
  • 1
    \$\begingroup\$ @Somebody It only has to work up to the largest number type supported by the language. \$\endgroup\$
    – Flummox
    Dec 7, 2023 at 14:23
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
0
\$\begingroup\$

Translate Japanese hiragana into the flick input method

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

Output [Some-Text]. You're given its translate in [Some-Language].

Sandbox Notes:

  • This seems area where machine learning would work
  • Stealing question Allowed
\$\endgroup\$
0
\$\begingroup\$

golf a range with modulus and subtraction

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

Output a 1-digit integer log table

Log tables were originally used for multiplication, since \$ x \times y = \exp(\log x + \log y) \$, superseding the use of trigonometric functions for this purpose. A log table I used in school back in the day had 900 main entries and then some interpolation entries you could use to give yourself almost an extra digit of accuracy.

However, if you were building a mechanical computer, you wouldn't need to have thousands of entries, as you could just program it to do long multiplication; the stumbling block is actually multiplying two digits together in the first place.

One approach to this is to use something called an Irish logarithm table. This is basically a pair of integer mappings \$ f \$ and \$ g \$ such that \$ g(f(x) + f(y)) = x \times y \$ for all \$ x, y \in \{ 0..9 \} \$.

For this challenge I would like you to output any two integer mappings with that property, in any reasonable format. In particular, since the length of the f mapping is always ten, there is no need to separate the f and g mappings in your output.

Note that while the f mapping maps from 0 to 9, the g mapping will have gaps because some of its indices won't correspond to the sum of two values of f. You can handle this either by outputting the mapping as a dictionary or by padding the output array with a suitable filler value.

Excluding the filler value, the g mapping only needs to output the values 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81.

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

\$\endgroup\$
9
  • \$\begingroup\$ Any potentially shorter way than log(x)*999? \$\endgroup\$
    – l4m2
    Dec 31, 2023 at 0:41
  • \$\begingroup\$ @l4m2 What integer are you using for an input of 0? \$\endgroup\$
    – Neil
    Dec 31, 2023 at 0:59
  • \$\begingroup\$ Also, I can see I should have specified non-negative integers. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 1:03
  • \$\begingroup\$ And I might need to include the highest index of g in the scoring somehow. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 1:04
  • \$\begingroup\$ Is there a reason for outputting mappings and not just implementing the functions? \$\endgroup\$ Dec 31, 2023 at 4:30
  • \$\begingroup\$ @CommandMaster It's to help you construct a mechanical calculator which can do lookup tables but not function calls. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 8:18
  • \$\begingroup\$ I just don't think that requiring answers to do return [f(i) for i in range(10)] is interesting - do you have solutions constructing these mappings in a different way? \$\endgroup\$ Dec 31, 2023 at 9:12
  • \$\begingroup\$ @CommandMaster I wasn't expecting there to be a closed form for f and g; if you have one then this question becomes irrelevant. \$\endgroup\$
    – Neil
    Dec 31, 2023 at 9:41
  • \$\begingroup\$ There is discrete log mod 83, although that isn't really a closed form and you need to do something for 0 \$\endgroup\$ Dec 31, 2023 at 10:11
0
\$\begingroup\$

Golf golfing a range with modulus and subtraction

In this other question I asked you to golf code which finds an equation transforming a list of unique numbers down to a minimal list. For this question, I'm asking you to write code which golfs that equation. In the other question we found that ((l-5)%99-94)%98 is a valid equation that turns l=[2,1,5,3,99,7,6] into [2,1,4,3,0,6,5], but if we do some more thinking, we can see that there are shorter ways to do this: (l%91-5)%8 gives the list [5,4,0,6,3,2,1] and l%95-1 gives the list [1,0,4,2,3,6,5]. Rather than golfing the code used to generate the equation, in this question you are looking for an algorithm that produces the shortest final equation.

To be a valid answer, your code must give an equation that transforms a provided list of unique, non-negative integers into a list of unique, non-negative integers in the range 0 to len(list)-1. You are scored for the length of the equation that you output rather than the length of your code. Each operation is one point, so an output of ((l-5)%99-94)%98 would score 4, (l%91-5)%8 would score 3, and l%95-1 would score 2. In a tie, the score is the character length of the complete equation including parenthesis, so ((l-5)%99-94)%98 would score 16, (l%91-5)%8 would score 10, and l%95-1 would score 6. Lowest score wins, as with normal code golf.

Different lists may give better scores using some algorithms over others, so we need to test your code to be sure that it is the best for many different lists. The score you list on your answer is the average score your code gets on all lists of 1-15 digits with values in the range 0-63 (say the average primary and secondary score in your answer). As this question is about the algorithm rather than the code length, you should explain your method as well. If you can prove that your method will always give the best possible score, I will mark your answer as accepted and (if it's simple enough) use your method as the example explanation in the other question. If this happens, I will also edit this question to include an explanation of your algorithm and this question will become a normal code-golf question where everyone implements that algorithm or an equivalent in as few bytes as possible in each language.

As the lists your code is tested against are finite in length and have a maximum value, you could theoretically brute-force the shortest solution by trying every possible modulus and subtraction value and returning the shortest. To prevent this, your code should run in less than O(r^l) time, where r is the range and l is the length.

@sandbox, What do you think is a good range? Should it be 1-7 digits, 1-31 digits? Values from 0-31, values from 0-127? Or should it be decimal ranges, 1-9 digits ranging from 0-99?

Also, what other tags?

\$\endgroup\$
6
  • \$\begingroup\$ Is there anything preventing solutions from doing a boring, trivially optimal, bruteforce solution? \$\endgroup\$ Dec 23, 2023 at 2:48
  • \$\begingroup\$ @CommandMaster do you think that looks good for preventing bruteforce solutions? \$\endgroup\$
    – guest4308
    Dec 24, 2023 at 4:33
  • 1
    \$\begingroup\$ Requiring to build the equation one operand at a time seems overly restrictive, and it's also not very clearly defined. What kind of calculations can you do on the array, before you actually "build" the solution? \$\endgroup\$ Dec 24, 2023 at 4:56
  • \$\begingroup\$ @CommandMaster yeah, I think that worked better in my head than it would in practice. I can't think of any other way to restrict bruteforce solutions without also restricting algorithmic solutions, do you have any ideas? or if not; is it fine to just have 'the brute force solution does not count' in the question? \$\endgroup\$
    – guest4308
    Dec 24, 2023 at 5:03
  • \$\begingroup\$ I think the best way to prevent brute force would just be to restrict the runtime, and have larger inputs \$\endgroup\$ Dec 24, 2023 at 5:04
  • \$\begingroup\$ @CommandMaster do you think that works to prevent bruteforce? and also for larger inputs what were you thinking would be a good amount? I think rn it's checking around 2e14 lists \$\endgroup\$
    – guest4308
    Dec 26, 2023 at 14:59
0
\$\begingroup\$

Unnecessary fluff

Sandbox note

There is a fairly efficient way to calculate this \$h\$, which might be interesting. Do you think I should require polynomial time, or being able to calculate all the testcases in a minute?

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

Shortest path to open a letter lock

\$\endgroup\$
4
  • \$\begingroup\$ I think this is easier than you intend it to be, but fair enough. Can the input be taken as a list of indices of the alphabet rather than a string / list of codepoints? \$\endgroup\$
    – noodle man
    Jan 6 at 22:45
  • \$\begingroup\$ @noodleman i think that would ruin the theme here, i wasnt even sure if i should include the list of letters instead of the full string \$\endgroup\$
    – pacman256
    Jan 7 at 0:06
  • 1
    \$\begingroup\$ Well, taking a string as a list of characters is an I/O default on this site. I would personally recommend letting letters of the alphabet be taken as indices, as that's just an extra step that most solutions will have to use and could be very long in some languages. Alternatively, a slightly more interesting variant of this challenge would be to take an arrangement of the alphabet as input (like abc...z or azbycx... or ajoifqw...) rather than always using the same alphabet. \$\endgroup\$
    – noodle man
    Jan 7 at 1:34
  • \$\begingroup\$ @noodleman From what I have seen, allowing letters to be replaced with indices is generally not an option for input in challenges like this, especially when the whole point is to have two "words" to switch between \$\endgroup\$
    – pacman256
    Jan 7 at 4:55
1
137 138
139
140 141
155

You must log in to answer this question.

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