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

4635 Answers 4635

1
25 26
27
28 29
155
3
\$\begingroup\$

Count N-Rich Permutations of an Integer Sequence

Given a sequence of integers with length \$L\$ and an integer \$1 \le N \le L\$, an "\$N\$-rich" permutation is one whose the longest strictly increasing subsequence has length exactly \$N\$.

For example, let our sequence be [0, 1, 2, 3]. There is exactly one \$1\$-rich permutation, given by [3, 2, 1, 0]. By contrast, there are sixteen \$2\$-rich permutations:

[0, 2, 1, 3] [0, 3, 1, 2] [0, 3, 2, 1]
[1, 0, 3, 2] [1, 2, 0, 3] [1, 3, 0, 2] [1, 3, 2, 0]
[2, 0, 3, 1] [2, 1, 0, 3] [2, 1, 3, 0] [2, 3, 0, 1] [2, 3, 1, 0]
[3, 0, 2, 1] [3, 1, 0, 2] [3, 1, 2, 0] [3, 2, 0, 1]

Note that [0, 1, 3, 2] is \$3\$-rich and NOT \$2\$-rich, because even though it contains a strictly increasing subsequence of length 2, it also contains a longer strictly increasing subsequence.

The Challenge

Your challenge is to write a function which takes in an integer sequence S with some length \$L\$, and an integer \$1 \le N \le L\$, and returns the number of N-rich permutations of S.

This is code golf, so the shortest valid answer wins.

Test cases

Each row is a sequence along with the expected output for all possible values of L. For example, the first row says that if your function is called f, then f([1, 2, 3, 4, 5], 3) = 41

[1, 2, 3, 4, 5] => 1, 69, 41, 8, 1
[1, 2, 2, 3, 3, 4, 5] => 4, 2612, 2064, 336, 24, 0, 0
[1, 1, 1, 1, 1, 1, 1] => 5040, 0, 0, 0, 0, 0, 0
[1, 2, 3, 1, 2, 3, 4] => 8, 2976, 1864, 192, 0, 0, 0
\$\endgroup\$
3
\$\begingroup\$

Could it be a possible chess move?

Backstory

Professor Chesster has a library of chess puzzles with solutions, but a meteor has struck (not real, I promise) and now their hard drive may be corrupted! Luckily, Professor Chesster's puzzle FENs are stored securely, but the solutions to those puzzles have all been jumbled up and could be as ridiculous as gxm9=L or even axc3! Professer Chesster needs a quick and simple scan to check if the solutions to their puzzles are valid.

Luckily, most of the meteor is not radioactive (no ) but because Professor Chesster's hard drive is now a literal potato, they need the code to be as short as possible () or it might overheat!

Stop waffling pls and show me the challenge!!!

OK, fine. Here:

Check if a move inputted with algebraic notation could be valid. Return a truthy value if it is, and a falsy value otherwise.

List of all moves that are valid

Na1, Na2, ..., Nh8
Ka1, ...
... [all other pieces]
Nxa1, Nxa2, ... [captures]
Nba1, ... [specify row]
N2a1, ... [specify col]
Nb3a1, ... [row & col]
Nbxa1, N2xa1, Nb3xa1, ...
(NOT Kab3 as there's only one king)
O-O (or 0-0??? META - WHAT DO I DO)
O-O-O (or 0-0-0??? META - THIS TOO)
axb2 to axb7
bxc2 to bxc7
...
gxh2 to gxh7
then bxa1 to bxa7 ... hxg7
Then promotions (a1=Q, a1=R, a1=B, a1=N)
b1=QRBN, c1=QRBN, ..., h1=QRBN
a8=QRBN, ...
axb1=QRBN,bxc1=QRBN, .......
[other moves I may have missed]

Scoring

Again, Professor Chesster's hard drive is such a potato that they require it to be golfed as much as possible. (this is )

META: Mandatory duplicate check

Not a duplicate of Is it a valid chess move? as that asks about a specific position.

Not a duplicate of Is it a plausible chess move? as that doesn't include piece information and a few other things that will be mentioned below

Sandbox/Meta stuff

  • Specifications
    • Do I include...
      • Check (move+)?
      • Double check (move++)?
      • Checkmate (move#)?
    • Did I miss any other chess moves?
  • Funny enough backstory?
\$\endgroup\$
9
  • \$\begingroup\$ Are we allowed to move our king into check? \$\endgroup\$ Aug 20, 2023 at 9:19
  • \$\begingroup\$ related challenges: next move in restricted set of moves, verify next move \$\endgroup\$
    – bsoelch
    Aug 20, 2023 at 13:08
  • \$\begingroup\$ @bsoelch If I'm reading it correctly it's about outputting all possible moves from any position. So something like axc6 would not be included in the output because no matter what the position is, a pawn can't take a piece two files away from it. I could be misinterpreting the question though, it certainly isn't too clear what is meant by "all valid chess moves." \$\endgroup\$
    – Aiden Chow
    Aug 20, 2023 at 18:50
  • \$\begingroup\$ It's all moves that could ever be valid in any position. Editing that in now \$\endgroup\$
    – W D
    Aug 21, 2023 at 9:21
  • \$\begingroup\$ Considering that the order of possible moves is not fixed I would not mark it as sequence \$\endgroup\$
    – bsoelch
    Aug 21, 2023 at 9:28
  • \$\begingroup\$ You should probably explain/link to the chess notation you are using \$\endgroup\$
    – bsoelch
    Aug 21, 2023 at 9:30
  • \$\begingroup\$ @TheEmptyStringPhotographer doesn't matter as it's over all possible boards || @bsoelch thanks for related challenges; not marked sequence anymore; linked to algebraic notation || @AidenChow yes - see the updated question \$\endgroup\$
    – W D
    Aug 21, 2023 at 9:35
  • \$\begingroup\$ IMO you would need to specify how to differentiate a a good move from a brilliant move from a normal move (Sotckfish uses an AI and an specific scoring system to determine the quality of a move) \$\endgroup\$ Aug 21, 2023 at 14:29
  • \$\begingroup\$ You don't need to differentiate them; this program has no input. It generates ALL possible moves from ALL possible boards \$\endgroup\$
    – W D
    Aug 22, 2023 at 8:02
3
\$\begingroup\$

Decode Chess Move

\$\endgroup\$
2
  • \$\begingroup\$ Apart from exluding moves like Nae5 (which I assume you did intentionally - "Knight (b) to a3" or "Knight(b) to a3" seem like good options if you were to include it) this looks good. May want to specify how to handle O-O-O (using the letter o and not the number 0) \$\endgroup\$
    – W D
    Aug 23, 2023 at 9:43
  • 1
    \$\begingroup\$ @WD for ambiguous moves (such as Nae5 even tho that is not a valid move) input will specify the starting square and the target square. For example, imagine there is a knight on d3 and another one on f3, input will specify the movement of the d3 knight as Nd3e5 \$\endgroup\$ Aug 23, 2023 at 13:32
3
\$\begingroup\$

Erasure Poetry

Given two strings of digits \$A\$ and \$B\$, count the minimum number of digits that need to be removed from \$A\$ to make it a substring of \$B\$. (META: i am still brainstorming what this actual challenge part should be, though i think this challenge might be good).

However, you will not be "writing" programs/functions to solve this challenge, so much as you will be finding them in the previous answer.

Challenge specification

(spec in progress)

Take two strings of digits \$A\$ and \$B\$. You can assume these strings will both be nonzero in length and contain any amount of the following characters in any order: 0123456789. Return the number of digits needed to be removed from \$A\$ in order to make it be a substring of \$B\$.

Worked out examples:

A: "3"
B: "123"
Output: 0
Explanation: "3" is already a substring of "123", so 0 characters need to be removed from it

A: "1322"
B: "12345"
Output: 2
Explanation: "12" is the biggest potential substring of B that could be made from A, and it requires removing the 3 and one of the 2s

A: "12345"
B: "123"
Output: 2
Explanation: "123" is the biggest potential substring of B that could be made from A, and it requires removing the 4 and 5

A: "12345"
B: "67890"
Output: 5
Explanation: None of A exists in B, so "" (the empty string) is the biggest potential substring of B that could be made from A, and it requires removing all 5 of the digits

Scoring specification

Contrary to what I said in the intro, you will technically be writing a program or function to solve this challenge. However, you will not be scored directly on your code length.

Included with your answer will be a list of characters you will remove from the previous answer's code such that it becomes your answer's code. If this is not possible with removals alone, you may also add characters to the previous answer, but this will come with a score penalty.

In particular: Your score is the number of characters you need to add to some substring of the previous answer's code in order to make it your answer's code. Lowest score wins.

The first answer to base your score off of will be provided at the bottom of this post.

Answer chaining rules

Importantly, you may not answer the challenge in a language that has already been used unless your answer has a lower score. Flags and version numbers do not differentiate languages in this challenge.

(more clarifications and guidelines)

Answer chaining example

6. MyOwnLanguage, +3 characters

previous answer with removed characters replaced with *:

do ****thing *o**

with my added characters becomes:

do thing now!

Try It Online

7. HQ9+2, +0 characters

previous answer with removed characters replaced with *:

do*thing****!

with my (0) added characters becomes:

dothing!

Try It Online

Starting answer

0. JavaScript (V8), +361 characters

f = (a, b) => {
  const isSubstring = (c, d) => {
    if(!c){
      return true
    }else{
      return RegExp(`${c}`).test(d)
    }
  }
  if(isSubstring(a, b)){
    return 0
  }else{
    a = [...Array(a.length).keys()]
        .map(w => a.slice(0, w)
                + a.slice(w + 1)
            )
    a = a.map(w => f(w,b))
    return 1 + Math.min(...a)
  }
}

Try it online!

meta

work in progresss, but feel free to suggest anything you think i might be missing, even if it seems obvious. Still working out the formatting for everything to look nice :-)

\$\endgroup\$
3
  • 2
    \$\begingroup\$ How does this work with SBCS? \$\endgroup\$ Sep 5, 2022 at 17:37
  • \$\begingroup\$ @CommandMaster not sure yet, im thinking about just making it based on the byte value itself. seems fair since most languages use just printable ascii, and from what ive seen, most SCBSes have their printable ascii on the same bytes as regular printable ascii. I might require / ask that languages with alternate encodings provide a hex dump. Does that sound reasonable? \$\endgroup\$ Sep 5, 2022 at 18:09
  • \$\begingroup\$ @CommandMaster actually I changed my mind, im making it char based so its just gonna be easier to work with in general :P I can't imagine there will be much cheesing in the way of "my language has one million different encodings for these commands so i can do every solution in 0", plus you can only use the language again if you can actually lower its score :P this should be ok :-) \$\endgroup\$ Oct 17, 2022 at 13:45
3
\$\begingroup\$

A robber flipped some bits. This is what happened to the cop's code.

Objective

Cops shall pose a code that outputs a truthy or falsy value deterministically, depending on the input. The output must be truthy on some inputs and falsy on some other inputs.

Flipping some bits in the code shall result in negating the output for every input. Robbers shall find such bits.

Winning criterion

For cops, the submission whose the cardinality of all valid inputs is the biggest shall win. The shortness of the code is a tiebreaker. In other words, this is primarily and secondarily . (Note that there may be infinitely many valid inputs, and its cardinality cannot exceed aleph-naught.)

For robbers, the submission whose percentage of the flipped bits is the closest to 50% shall win. The number of the flipped bits is a tiebreaker. So this is primarily and secondarily .

Rule

Cops must specify what the valid inputs are.

\$\endgroup\$
6
  • \$\begingroup\$ I think you should elaborate the 'cardinality of valid inputs' scoring criterion better. In Husk, a cop answer could be = increment. All integers are valid inputs (so they are infinite), and only -1 results in falsy output (zero). I don't think there's a single-byte Husk command that would make -1 truthy and everything else falsy, so it seems uncrackable. \$\endgroup\$ Sep 1, 2023 at 12:25
  • 1
    \$\begingroup\$ @DominicvanEssen they way I understood the second sentence of the objective, there has to be a way to crack the program for the submission to be valid \$\endgroup\$
    – bsoelch
    Sep 3, 2023 at 8:31
  • 1
    \$\begingroup\$ @bsoelch - ah, that makes sense… \$\endgroup\$ Sep 3, 2023 at 9:30
  • \$\begingroup\$ Why is higher cardinality better? I would think it would be the opposite. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 3, 2023 at 18:56
  • \$\begingroup\$ @WheatWizard If smaller cardinality were better, cop submissions might take no input, which gives cardinality 1. That's too trivial. \$\endgroup\$ Sep 4, 2023 at 1:17
  • \$\begingroup\$ Isn't trivial better? It makes it harder to disguise things. But if trivial is bad what's to prevent someone from "taking" the input and ignoring it. That makes no real difference to the cop but makes their score in that infinity. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 4, 2023 at 2:10
3
\$\begingroup\$

What's my score?

The question score on Stack Exchange is the total number of upvotes minus the total number of downvotes a question receives. However, the reputation gained/lost for every upvote/downvote is different (10/-2 on Code Golf).

Given the total reputation and the reputation gained/lost on votes, list out all possible scores the question could have.

Rules

  • The total reputation, the reputation gained by an upvote and reputation lost by a downvote must be integers
  • The upvote-reputation will be positive and the downvote-reputation will be negative
  • You can output the possible question scores as a (possibly infinite) list or print each one individually.
  • This is , so the shortest answer wins

Examples

[total reputation, upvote-reputation, downvote-reputation] -> [question scores]

[28, 10, -2]  -> [2, -2, -6, -10, ...]
[34, 10, -2]  -> [1, -3, -7, -11, ...]
[17, 10, -2]  -> []
[11, 7, -5]   -> [1, -1, -3, -5, ...]
[82, 31, -11] -> [2, -18, -38, -58, ...]
[15, 5, -10]  -> [3, 4, 5, 6, ...]
\$\endgroup\$
3
\$\begingroup\$

Sum of consecutive nth powers

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

How many ways to cut a number into an equation?

\$\endgroup\$
3
\$\begingroup\$

Play a game of memory

\$\endgroup\$
3
  • \$\begingroup\$ Suggest test case "cbxcxvbaav", 8 \$\endgroup\$
    – math scat
    Sep 12, 2023 at 12:37
  • \$\begingroup\$ @mathscat Added, thank you. \$\endgroup\$
    – Philippos
    Sep 12, 2023 at 12:58
  • 1
    \$\begingroup\$ @bsoelch In Memory you pick the cards in order, so you can adjust the second card based on the first, so if you see the first has a match you can choose that match as the second card \$\endgroup\$ Sep 12, 2023 at 19:32
3
\$\begingroup\$

Numbers with distinct decimal digits

\$\endgroup\$
3
\$\begingroup\$

Implement Subleq

\$\endgroup\$
2
  • \$\begingroup\$ @bsoelch Fixed. \$\endgroup\$ Sep 19, 2023 at 17:40
  • \$\begingroup\$ @bsoelch That was a mistake on my part as well, I'll replace the example. \$\endgroup\$ Sep 20, 2023 at 18:38
3
\$\begingroup\$

Do you win a Numeric Mahjong?

\$\endgroup\$
5
  • \$\begingroup\$ why do we need the first rule? That would be like restricting languages made after posting this question \$\endgroup\$ Sep 19, 2023 at 12:41
  • \$\begingroup\$ @UndoneStudios Now that I think of it, fractional byte encodings seem fine. Variable length encodings (like Vyncode) are a problem, because they don't really define a mapping from a char in source to an integer. \$\endgroup\$
    – Bubbler
    Sep 19, 2023 at 23:36
  • \$\begingroup\$ This should be a question to raise in meta \$\endgroup\$ Sep 20, 2023 at 3:55
  • \$\begingroup\$ @UndoneStudios The rule is needed to define how to convert a source code to a list of integers. It totally isn't like "restricting languages made after posting this question". All languages can participate as long as they have a textual or byte representation (which practically all languages used on the site do). Only some encodings of some languages are not allowed. \$\endgroup\$
    – Bubbler
    Sep 20, 2023 at 4:19
  • \$\begingroup\$ Well, technically, I was only against variable encodings; that is cheaty \$\endgroup\$ Sep 20, 2023 at 4:21
3
\$\begingroup\$

I (rev)?(pal)? the source code, you (rev)?(pal)? the input!

\$\endgroup\$
3
\$\begingroup\$

Complete an equivalence relation

In set theory, a relation from a set \$A\$ to a set \$B\$ is a set of pairs of elements from \$A\$ and \$B\$. For example, \$\{(1, 5), (1, 6), (2, 4), (3, 5)\}\$ is a relation from the set \$\{1, 2, 3\}\$ to the set \$\{4, 5, 6\}\$.

A relation \$R\$ from a set \$A\$ to itself is an equivalence relation iff:

  • It is reflexive: For all elements of \$A\$, \$(a, a)\$ is in \$R\$.
  • It is symmetric: If a pair \$(a, b)\$ is in \$R\$, then so is \$(b, a)\$.
  • It is transitive: If the pairs \$(a, b)\$ and \$(b, c)\$ are in \$R\$, then so is \$(a, c)\$.

For example, \$\{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)\}\$ is an equivalence relation on the set \$\{1, 2, 3\}\$.

Your challenge is to, given a relation from a set to itself, add as few pairs of elements as possible to transform it into an equivalence relation.

Worked example

If we start with the relation \$\{(1, 2), (3, 2), (4, 4)\}\$, then:

Firstly, the relation must be reflexive, so all pairs of elements \$(a, a)\$ must be added, resulting in \$\{(1, 2), (3, 2), (4, 4), (1, 1), (2, 2), (3, 3)\}\$.

Next, the relation must be symmetric, so we need to add the inverses of \$(1, 2)\$ and \$(3, 2)\$, resulting in \$\{(1, 2), (3, 2), (4, 4), (1, 1), (2, 2), (3, 3), (2, 1), (2, 3)\}\$.

Finally, the relation must be transitive. Since \$(1, 2)\$ and \$(2, 3)\$ are in the relation, so must be \$(1, 3)\$, and likewise \$(3, 1)\$ must also be in the relation. Adding these results in \$\{(1, 2), (3, 2), (4, 4), (1, 1), (2, 2), (3, 3), (2, 1), (2, 3), (1, 3), (3, 1)\}\$, and this is an equivalence relation.

Input/output is can be lists of pairs of positive integers, or an adjacency matrix. You can optionally take the domain of the relation (i.e. all unique values in it). The order in which you output the pairs does not matter, and you can assume the input will be nonempty.

Testcases

{(1, 1)} -> {(1, 1)}
{(1, 2)} -> {(1, 2), (1, 1), (2, 2), (2, 1)}
{(1, 2), (3, 4)} -> {(1, 2), (1, 1), (2, 2), (2, 1), (3, 4), (3, 3), (4, 4), (4, 3)}
{(1, 2), (1, 3)} -> {(1, 2), (1, 3), (1, 1), (2, 2), (3, 3), (2, 1), (3, 1), (2, 3), (3, 2)}
{(1, 1), (2, 2), (3, 3)} -> {(1, 1), (2, 2), (3, 3)}
{(1, 1), (2, 2), (3, 4)} -> {(1, 1), (2, 2), (3, 3), (3, 4), (4, 3)}
{(1, 2), (3, 2), (4, 1)} -> {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)}
{(8, 19), (4, 12), (9, 31), (4, 18)} -> {(8, 8), (8, 19), (19, 8), (19, 19), (4, 4), (4, 12), (4, 18), (12, 4), (12, 12), (12, 18), (18, 4), (18, 12), (18, 18), (9, 9), (9, 31), (31, 9), (31, 31)}
{(8, 7), (2, 7), (14, 3), (3, 16)} -> {(2, 2), (2, 7), (2, 8), (7, 2), (7, 7), (7, 8), (8, 2), (8, 7), (8, 8), (3, 3), (3, 14), (3, 16), (14, 3), (14, 14), (14, 16), (16, 3), (16, 14), (16, 16)}
{(1, 1), (1, 2)} -> {(1, 1), (1, 2), (2, 1), (2, 2)}
\$\endgroup\$
8
  • \$\begingroup\$ Could output be loosened to not require outputting pairs already in the input? Although for some reason I feel iffy about going in between, i.e. allowing the output to contain some input pairs without requiring it to contain all of them... \$\endgroup\$ Sep 27, 2023 at 8:47
  • 1
    \$\begingroup\$ @UnrelatedString What exactly are you thinking of when you say that? I can't think of any reasonable approach which would necessitate that. Besides, the point of the challenge is to create the minimal superset that's an equivalence relation. \$\endgroup\$
    – emanresu A
    Sep 27, 2023 at 20:17
  • \$\begingroup\$ I was mostly inspired by the phrase "add as few pairs of elements as possible"--thinking about the interplay between symmetry and transitivity, it seems unlikely any solution would actually benefit from only outputting the added pairs, which makes me kinda curious about leaving the option open. \$\endgroup\$ Sep 28, 2023 at 3:24
  • \$\begingroup\$ Do you have to deduce the set or can you take it as input? Can you use adjacency matrices? Can you output the equivalence classes? \$\endgroup\$ Sep 28, 2023 at 9:13
  • \$\begingroup\$ Possible dupe \$\endgroup\$ Sep 28, 2023 at 9:18
  • \$\begingroup\$ @CommandMaster I'll allow taking the domain as input, and I/O as adjacency matrices. I'm not going to allow outputting the equivalence classes because I can think of several approaches that wouldn't even compute them and I want things to stay semiconsistent. I don't think this is a dupe for two reasons: one, that challenge requires outputting the number of sets to add which a lot of answers take advantage of; two, while transitivity is the hard part of this challenge, incorporating reflexivity and symmetry into an answer from there is still nontrivial. \$\endgroup\$
    – emanresu A
    Sep 29, 2023 at 1:27
  • \$\begingroup\$ are delimiters required? or can i take {(1, 2), (3, 4)} as 1 2 3 4 and output 1 2 1 1 2 2 2 1 3 4 3 3 4 4 4 3? \$\endgroup\$ Sep 29, 2023 at 2:25
  • 1
    \$\begingroup\$ @thejonymyster Since it's a list of pairs, sure, that's fine. I believe taking a flattened list is in the I/O defaults anyway \$\endgroup\$
    – emanresu A
    Sep 29, 2023 at 2:26
3
\$\begingroup\$

The multiples are missing

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

? ? ?

Golfy Fairy Chess Notation + Validation

Step 1:

Design an encoding for fairy chess piece movement which encodes all of the following information:

  • Where a piece can move (INCLUDING arbitrary length movement)*
  • Whether those movements are "jumping" or not
  • Whether those movements are "capturing" or not**

You don't need to handle non-moving, royalty, special case movement (such as first move double-movement), or any other special stuff like that.

Step 2:

Write a program which, when given (A):

  • a chess position***
  • a starting square
  • an ending square

all in any reasonable format of your choice, as well as (B):

  • a description of a fairy chess piece's movement capabilities in the notation you designed in step 1

will output whether the movement on the board (A) is valid for that fairy chess piece (B)

Additional spec clarification

You may assume

  • All pieces other than the piece being moved are pawns
  • The fairy chess piece is the piece that will be moved
  • The fairy chess piece movement will be defined such that it could theoretically make a move, given the right board arrangement (i.e. no 'non-movers')
  • Movement will be entirely within the board
  • Board will be square and at least 2x2 in size
  • Piece will not attempt to capture its own teammates
  • Piece will not attempt to move to its own square, and you don't need to worry about whether the notation implies it should/shouldn't be able to.

You may not assume an 8x8 board.

Scoring:****

\$(\text{bytes in program})\times(\text{average bytes to represent each piece in (list of fairy chess pieces which will be provided)})\$

Lowest score wins

Optional challenge: try and make the format human legible! :-)

META:

*I will be sure to clarify in the question body how exactly this works; but basically i want to be able to include things like rook/bishop/queen/knightrider without having to assume a maximum movement distance

**I'll also be clear that pieces can only capture at the end of their move, so no multicapture or capture and then move / en passant nonsense :P

***I don't know how to explain, but this doesnt have to include which pieces are what. just where the pieces are and whether each piece is on your team or not, or something similarly simple

****Ideally, score would be based on both short notation as well as a short decoding program, but I'm not sure the exact balance yet. feel free to tell me this is a bad idea / throw your algo of choice at me, but i'll be studying other compression challenges as well

\$\endgroup\$
2
  • \$\begingroup\$ Heads up: It looks like the bullet-point formatting in the first list under step 2 is wrong (missing newlines?). \$\endgroup\$ Oct 6, 2023 at 14:53
  • \$\begingroup\$ @SuperStormer great catch, that wouldve taken forever for me to notice lol thank you \$\endgroup\$ Oct 6, 2023 at 15:32
3
\$\begingroup\$

Find the k-th largest number

Given the string representation of three sorted lists, get the k-th largest number.

The string representation has such form:

1 3 5 7 11 120 9988
23 68 99 111
107 131 888

aka. lists are separated by newline \n and numbers in one list are separated by space.

Length of each list, length of the string and k are directly given, but access to the string costs. You can fetch from a given position. Least fetches wins.

Your solution should handle all possible inputs well, but only optimize score for average cases.

This is an example solution. It solves the problem with an awful score, but you can also use lib here. Write the lib if it's absent in your language.


Sorted lists in test cases will be generated in this way:

  • Generate 1 million (1'000'000) integers uniformly in \$\left[0, 2^{31}-1\right]\$. Duplicates will likely appear.
  • Sort them.

[Not decided yet] It's fine if your code is only optimized for three 1M length arrays and fallback to worst solution for other input.

\$\endgroup\$
2
  • \$\begingroup\$ You should clarify what "average case" means. From what distribution are the inputs taken? Additionally, can there be duplicates in the lists? \$\endgroup\$ Oct 11, 2023 at 3:35
  • \$\begingroup\$ @CommandMaster Added \$\endgroup\$
    – l4m2
    Oct 11, 2023 at 8:35
3
\$\begingroup\$

Make Code Printing X without X

The challenge is simple: write a program which takes in some string \$n\$ consisting of only uppercase and lowercase letters, and outputs the code for a program (in the same language) which takes in no input and outputs \$n\$. However, the code your program generates must not have any of the characters of \$n\$. For example, if your program was in Python, if the input was "Lit", your output could not be print("Lit"), because that contains L, i, and t. One valid output would be, for example, x=lambda:'\114\151\164'.

Some notes:

  • Uppercase and lowercase characters are treated as distinct -- e.g. if the input string contains A, your generated code can still contain the character a.
  • Your generated code follows the same restrictions as a standard code golf answer -- e.g. it can be code which defines an anonymous function returning the string, but it cannot work by saving the string into a variable.
  • Your submission is scored by the length of the generating code, not the generated code. In addition, there are no restrictions on the source of the generating program, only the generated.

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

Questions

I don't know what to call this challenge.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ code-generation \$\endgroup\$
    – noodle man
    Oct 15, 2023 at 3:37
  • 1
    \$\begingroup\$ Because of the possibility that input contains all letters, all answers would likely never output letters \$\endgroup\$
    – l4m2
    Oct 16, 2023 at 0:32
  • \$\begingroup\$ @l4m2 Hm.... I somehow didn't think of that; that means this challenge isn't possible in many languages. I could add a limit on the number of distinct characters which can occur in the input, but that feels inelegant. Other thoughts? \$\endgroup\$ Oct 16, 2023 at 21:59
3
\$\begingroup\$

Is it a valid crossword grid?

In crossword terminology, the grid is the region into which the crossword answers are inserted, consisting of white and black squares. The crossword answers, called entries, are inserted into contiguous sequences of white squares in a row or column, separated by black squares.

For British (and Commonwealth) crosswords, the grids usually follow a specific set of rules:

  • They should have 180 degree rotational symmetry (if there is a black square in the xth row and yth column, there should be a black square in the xth-to-last row and y th-to-last column).
  • No entries may be exactly two squares long.
  • All white squares must be joined in a single region.
  • No row/column can be completely filled with black squares.
  • Each two-by-two square must contain at least one white square.
  • Each two-by-three rectangle must contain at least one black square.

For n=3 there is only one valid grid (I'm using . for white squares and # for black squares):

...
.#.
...

For n=4 there are no valid grids, although British crosswords usually use odd n anyway.

Here are some examples of valid grids for n=5:

.....  .....  #.#.#  ###.#
.#.#.  .###.  .....  #....
.....  .....  #.#.#  #.#.#
.#.#.  .###.  .....  ....#
.....  .....  #.#.#  #.###

Here are two examples of valid grids for n=6:

......  ......
.##.#.  .##.#.
.#....  ....#.
....#.  .#....
.#.##.  .#.##.
......  ......

Input may be in the form of an array of any two byte-sized values and output can be any two distinct values of your choice or any of your language's truthy or falsy values respectively.

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

\$\endgroup\$
1
  • \$\begingroup\$ .................... :) \$\endgroup\$ Oct 16, 2023 at 21:57
3
\$\begingroup\$

Befunge Comment Outline Creator

\$\endgroup\$
6
  • \$\begingroup\$ Is it equivalent to a 0-1 matrix with an even sum in each row/column? Additionally, I'm assuming an all-space answer is invalid, but I don't see any rule disallowing it. Could you add one? \$\endgroup\$ Oct 20, 2023 at 6:26
  • \$\begingroup\$ @CommandMaster Almost, however having no semicolons at all would result in the IP reading in the comment as code. I could probably clarify that. \$\endgroup\$ Oct 20, 2023 at 6:36
  • \$\begingroup\$ Can I take as input w+2, h+2 instead of w, h? \$\endgroup\$ Oct 21, 2023 at 6:35
  • \$\begingroup\$ @CommandMaster Is it too expensive to add 2 to the inputs? \$\endgroup\$ Oct 21, 2023 at 7:04
  • \$\begingroup\$ I haven't tried, and w, h might be shorter, but it might be easier to use the size of the output instead of the size of the comment itself \$\endgroup\$ Oct 21, 2023 at 7:06
  • \$\begingroup\$ @CommandMaster Hm, I may consider it, it doesn't seem like it would be unfair \$\endgroup\$ Oct 21, 2023 at 7:10
3
\$\begingroup\$

Minecraft XP Orb Amounts

\$\endgroup\$
3
\$\begingroup\$

Intersections in a Circular Scrambled Word

Given a word W and a scrambled version of it S as input, you are required to return the number of intersections S will have when organized in a circular arrangement.

Example

Let W be VICTORY and S be VICYTRO. After transforming the scrambled word in its circular form and forming the original word by adding segments between the characters, we have the following diagram:

enter image description here

As we can see, for this particular example, the expected output is 2 interceptions.

Specs

  • Input will consist only of [A-Z] characters.
  • It is irrelevant how you set up the circular word (clockwise, counterclockwise, if the characters are evenly spaced from one another or not), just be consistent.
  • Input is flexible, read it however you see fit for you.
  • Standard loopholes are not allowed.

Test Cases

Format: 
W , S  --> output

VICTORY, VICYTRO --> 2
# To be added more 

This is , so shortest answers in bytes wins!

Meta

Is the challenge interesting? Is there anything unclear? I am not a native English speaker, so I welcome any corrections on the wording of the challenge.

I will later add more test cases. Also, what is the general consensus here where there are multiple correct answers? Because when I add words with repeated letters, depending on the "path" you choose when forming the circular word, it will affect the number of intersections. (I'll update the specs section as well when I introduce these special cases).

Lastly, I didn't give much thought on my second point in the specs section, maybe it's wrong... I'll observe more cases later.

Pretty much any feedback is appreciated!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Could take input as a permutation of 1..n, to get rid of worrying about repeated letter ambiguity as well as some potential for a "chameleon challenge" (i.e. determining the permutation between the two words could be highly nontrivial in some languages and overshadow the actual "core" of intersections between circle chords). If you do want solutions to have to handle repeats, then I'd recommend just allowing them to give any of the possible outputs. \$\endgroup\$ Oct 29, 2023 at 19:52
  • 1
    \$\begingroup\$ re. multiple possible outputs: challenges often specify that submissions may choose to either output all possible outputs or just one of them. \$\endgroup\$
    – noodle man
    Oct 29, 2023 at 20:10
  • \$\begingroup\$ I suggest to write W and S instead of W and S to avoid confusion, because those are just names, no data. \$\endgroup\$
    – Philippos
    Oct 31, 2023 at 12:44
3
\$\begingroup\$

Seat gangs as far as possible

\$\endgroup\$
2
  • \$\begingroup\$ @noodleman No, the gangs can be any (non-zero) size -- \$k\$ is the number of gangs. \$\endgroup\$ Oct 31, 2023 at 17:45
  • 1
    \$\begingroup\$ Suggest test case 1,2,1,2,1 -> 1,1,1,2,2 \$\endgroup\$
    – noodle man
    Oct 31, 2023 at 17:46
3
\$\begingroup\$

Calculate a struct size

In C and C++, the size of a structure depends not only on the sizes of its members but also their alignment requirements.

This problem will assume a simple case in which each structure is made up of primitive types that have a size that is a power of two and an alignment that equals their size.

Given a list of the types in a structure, please output the resulting size of the structure.

Here is an example structure:

struct {
  char c[5];
  int i, j;
  short s[3];
}

Input in any of the following formats is acceptable:

  • A list of the sizes of the individual types that make up the structure; for the above that would be [1, 1, 1, 1, 1, 4, 4, 2, 2]
  • A list giving the lengths of each array and the sizes of its elements, which for the above would be [[5, 1], [1, 4], [1, 4], [3, 2]]
  • A list giving the size and alignment of each variable, which for the above would be [[5, 1], [4, 4], [4, 4], [6, 2]]

(The third format indirectly supports nested structures but this can be emulated for the other formats by replacing them with an array of the same size and alignment.)

The size of the above structure is 24. Here is how it is calculated:

  1. Each of the 5 chars consumes 1 byte each, making 5.
  2. Each int requires an alignment of 4, so there are three bytes of padding before the first of them. The total size is now 16.
  3. Each of the 3 shorts consume 2 bytes each. The total size is now 22.
  4. The entire structure has an alignment of the largest alignment of any member, which in this case is 4, so the size must be rounded up to the next multiple of 4, which is 24.

Visually:

c[0] c[1] c[2] c[3]
c[4] ..............
i__________________
j__________________
s[0]_____ s[1]_____
s[2]_____ .........

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

\$\endgroup\$
3
\$\begingroup\$

Just another traffic jam!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you specify the zip-lock system? \$\endgroup\$
    – Seggan
    Nov 27, 2023 at 19:53
  • \$\begingroup\$ @Seggan I added that, thank you. I somehow thought this would be internationally known. \$\endgroup\$
    – Philippos
    Nov 28, 2023 at 6:49
3
\$\begingroup\$

Output 5-line calendar

Given year, month and optionally weekday of 1st, output the calendar of the month.

For empty cell, fill it with the date where it's supposed to be, in last or next month, and add # to indicate gray. If last few days can't fit in 5 lines, then they share last line with 5th week, use / to separate two days.

Sample Input: Nov 2023

Sample Output:

 #28   #29   #30     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    #1    #2

Sample Input: Dec 2023

Sample Output:

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

Outputting a 2D array of string is fine

\$\endgroup\$
3
\$\begingroup\$

Longest irreducible quine

Posted here

\$\endgroup\$
15
  • \$\begingroup\$ Would a submission be valid if it can be reduced to an improper quine, but not to a proper one? \$\endgroup\$
    – noodle man
    Dec 4, 2023 at 17:17
  • \$\begingroup\$ @noodleman ty, clarified \$\endgroup\$
    – math scat
    Dec 4, 2023 at 20:33
  • \$\begingroup\$ In most languages it will be possible to make it longer by somehow splitting it, but you can't reduce it by only removing characters, but you also need to change some. I never saw a good »longest« challenge, and I doubt this will be the first. \$\endgroup\$
    – Philippos
    Dec 5, 2023 at 6:40
  • \$\begingroup\$ @Philippos not quite sure how this would work, care to give an example? \$\endgroup\$
    – math scat
    Dec 5, 2023 at 12:33
  • 2
    \$\begingroup\$ @Philippos This is wrong - it easily follows from Higman's lemma that in all languages (they don't even have to be computable!) there is only a finite number of irreducible programs which perform a given task, so in particular the length must be bounded. \$\endgroup\$ Dec 5, 2023 at 16:28
  • \$\begingroup\$ @CommandMaster thanks for clarifying! \$\endgroup\$
    – math scat
    Dec 5, 2023 at 16:32
  • \$\begingroup\$ An example: You can split your example like v='%r;print("v="+v%%v)';print("v="+v%v) Easy to reduce, but not only by only removing bytes. \$\endgroup\$
    – Philippos
    Dec 6, 2023 at 8:08
  • \$\begingroup\$ @Philippos Sure, but I don't see how this can be extended further indefinitely. (Granted, I'm not very experienced with quines/irreducible code) \$\endgroup\$
    – math scat
    Dec 6, 2023 at 15:19
  • \$\begingroup\$ You could continue like v='%r;pront("v="+v.replace(chr(111),"i")%%v)';print("v="+v.replace(chr(111),"i")%v), which of course could be repeated similarly many times without possible reduction. \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 7:22
  • \$\begingroup\$ @CommandMaster I don't know whether Higman's lemma can be appllied here. Even if it can, the length border could be somewhere in the thousands, millions, billions ... \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 7:25
  • \$\begingroup\$ @Philippos I know it can be large, but that's the point of the challenge. Why couldn't it be applied? If you look at the set of all irreducible programs performing a particular task, no element of that set is a subsequence of another element, so it must be finite. \$\endgroup\$ Dec 7, 2023 at 8:42
  • \$\begingroup\$ @CommandMaster Well, math scat may give it a try, but still I believe it won't be fun, because the people will lose interest before reaching any border. Or I'm wrong (rumours claim this did already happen before ;-) \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 8:48
  • \$\begingroup\$ @Philippos This irreducible code bowling challenge was very well received, I don't see why this will be worse \$\endgroup\$ Dec 7, 2023 at 9:37
  • \$\begingroup\$ @CommandMaster One look at the exponents is enough for me to walk away. \$\endgroup\$
    – Philippos
    Dec 7, 2023 at 10:20
  • \$\begingroup\$ (at Phillipos and CommandMaster) thanks for your feedback, I do think I'll give this challenge a try though. \$\endgroup\$
    – math scat
    Dec 12, 2023 at 12:06
3
\$\begingroup\$

How long is this string, really?

\$\endgroup\$
3
\$\begingroup\$

In this challenge answers will provide three elements:

  • A programming language: \$L\$
  • An output string: \$S\$
  • And a non-empty string: \$B_n\$

You will also write, but not reveal, a program in \$L\$ which outputs \$S\$, built by concatenating copies of the \$B_n\$ strings from your answer and previous answers in any order.

For example here are two answers given in pseudocode:

Answer 1

\$S\$ = H
\$B_0\$ = print "H"

The program is print "H"

Answer 2

\$S\$ = Hiiii
\$B_1\$ = ++"i"

The program is print "H"++"i"++"i"++"i"++"i"

Robbers will try to discover a valid solution, that is a program made from the \$B_n\$ strings in your answer and previous answers which outputs your \$S\$. Your goal will be to make this as hard as possible.

States

As with any challenge, cops' posts here can have 4 different states:

  • Vulnerable
  • Cracked
  • Safe
  • Revealed

All cops' posts start as vulnerable. If a robber finds and posts a solution to a vulnerable post they will receive 1 point and the post will become cracked. If a post lasts 10 days in vulnerable without being solved it automatically becomes safe. A cop with a safe post may choose to reveal their program and their safe post will become revealed. A robber can still solve a safe post, if they do they receive a point and the post becomes revealed.

Only revealed posts are eligible for scoring. Robbers are only permitted to solve vulnerable and safe posts.

Scoring

For cops' an answer's score is the number of cops' posts before it if it is revealed and 0 if it is any other state. The goal is to get as high a score as possible.

Languages

In the interest of fairness, we are going to require that languages are free and reasonably cross platform. Both languages you choose must be freely available on Linux and FreeBSD (the two largest foss operating systems). This includes languages which are free and open source.

Your selected languages must predate this challenge.

Programs here should be complete programs not functions, expressions or snippets.

\$\endgroup\$
4
  • \$\begingroup\$ I wonder, would cops want to make writing challenges for future cops easier or harder? Also, your example challenges don't state the language, although the text above them says the cop ought to state it. \$\endgroup\$ Feb 17 at 5:27
  • \$\begingroup\$ @CommandMaster I state both are in pseudocode. \$\endgroup\$
    – Wheat Wizard Mod
    Feb 17 at 7:00
  • \$\begingroup\$ Oh, I see. It's outside the answer quote, so this might be a bit confusing \$\endgroup\$ Feb 17 at 10:17
  • \$\begingroup\$ Does the cop/robber need to use all of previous \$B_n\$? I suggest stating either way explicitly. \$\endgroup\$
    – pajonk
    Feb 18 at 10:01
2
\$\begingroup\$

Huffman Decoding

Write a programm which takes two strings as input and prints a text.


The first argument is a Huffman Tree, serialized in the following format:

  • every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
  • <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
      d e

where a would have the key 00, b 01, c 10, d 110 and e the key 111.


The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

  • the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
  • the bitstring is broken up into 6-bit chunks and mapped to this characters
  • if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
  • - : the last chunk was five bits long
  • = : the last chunk was four bits long
  • =- : the last chunk was three bits long
  • == : the last chunk was two bits long
  • ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-

Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

\$\endgroup\$
2
  • \$\begingroup\$ It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. \$\endgroup\$ Oct 8, 2012 at 16:23
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$
    – user58826
    Jun 9, 2017 at 15:30
1
25 26
27
28 29
155

You must log in to answer this question.

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