555
\$\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".

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3937 Answers 3937

1
16 17
18
19 20
132
3
\$\begingroup\$

Posted.

\$\endgroup\$
2
  • \$\begingroup\$ For the sake of completion: can I give my output as a list of strings? \$\endgroup\$
    – lyxal
    Apr 29, 2020 at 23:02
  • \$\begingroup\$ @Lyxal Seeing as that's a generally accepted I/O method, yes. \$\endgroup\$
    – sporeball
    Apr 30, 2020 at 0:09
3
\$\begingroup\$

Complete a sequence using its distances

Given \$A = (a_1,\dots,a_k)\ k\ge2 \$ a nonrepetitive sequence of positive integers.
Starting from \$i=2\$, while \$a_i\in A:\$

  • If \$d=|a_i-a_{i-1}|\$ is not already in \$A\$, append \$d\$ to \$A\$
  • Increase \$i\$

Output the completed sequence.

Example

In:  16 20 13 3

     16 20 13 3 4
      --^
     16 20 13 3 4 7
         --^
     16 20 13 3 4 7 10
            --^
     16 20 13 3 4 7 10 1
              --^
     16 20 13 3 4 7 10 1
                --^
     16 20 13 3 4 7 10 1
                  --^
     16 20 13 3 4 7 10 1 9
                     --^
     16 20 13 3 4 7 10 1 9 8
                         --^
Out: 16 20 13 3 4 7 10 1 9 8

This is

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You could define the self-distances completion for a sequence of positive integers instead of a k-permutation. I believe it would be clearer that way. Also, is the input guaranteed to be duplicate-free? \$\endgroup\$
    – Zgarb
    Jun 1, 2020 at 20:15
  • \$\begingroup\$ @Zgarb Yes, you're right, for the purpose of this challenge refer to a sequence would be totally ok, I've copied this def from the linked challenge where since it's fundamental to consider the max in the input sequence, this number in the context of k-permutation of n - containing n - will naturally be n... But that's not a problem, a k permutation is also a sequence of positive integer. And yes, I forgot to require the input to be duplicate-free \$\endgroup\$
    – Domenico
    Jun 1, 2020 at 20:44
  • \$\begingroup\$ @Zgarb what do you think about the name? Does it make sense? It's a bit too bulky? \$\endgroup\$
    – Domenico
    Jun 1, 2020 at 20:53
  • 1
    \$\begingroup\$ "append d to (the end of) A" could be clearer to programmers than "prolong A with d". Using "the end of" is optional. \$\endgroup\$
    – Hiatsu
    Jun 2, 2020 at 3:05
  • 1
    \$\begingroup\$ The name could be "Complete a sequence using its distances" if you want to go for maximum clarity. \$\endgroup\$
    – Zgarb
    Jun 2, 2020 at 8:08
3
\$\begingroup\$

_

\$\endgroup\$
7
  • \$\begingroup\$ @mathjunkie then the codepoints given are incorrect. \$\endgroup\$
    – lyxal
    May 24, 2020 at 22:43
  • \$\begingroup\$ @Lyxal Why are they incorrect? I wrote a program to generate the codepoints. \$\endgroup\$
    – user92069
    May 25, 2020 at 8:15
  • \$\begingroup\$ Oh wait. I thought they were in binary. \$\endgroup\$
    – lyxal
    May 25, 2020 at 8:18
  • \$\begingroup\$ As in, you were using the binary representation of each ordinal value. \$\endgroup\$
    – lyxal
    May 25, 2020 at 8:19
  • \$\begingroup\$ @Lyxal No. I was using the decimal expansion of the ord codes. I am going to clarify that. \$\endgroup\$
    – user92069
    May 25, 2020 at 8:19
  • \$\begingroup\$ I cam see that now. I just assumed those numbers were base 2,rather than base 10 \$\endgroup\$
    – lyxal
    May 25, 2020 at 8:20
  • \$\begingroup\$ Seems pretty clear, but would benefit from test cases with odd-length strings. For example, 'rim' (false) and 'rum' (true) illustrate the 'first half longer' splitting rule. (Truthiness for these two words would be swapped if the rule were second half longer.) \$\endgroup\$
    – Dingus
    May 29, 2020 at 7:24
3
\$\begingroup\$

Bot Duels KOTH

Obligatory blurb adding story fluff. Or, maybe a self-referential paragraph about meta-self-referential blurbs? Or: <announcer voice> Will your bot survive... The Arena? </announcer voice>. Yes, I think a good non-self-referential (such as this) short paragraph full of short sentences without run-ons or many, many, many, many commas will suffice.

Overview

This is a King-of-the-Hill challenge. Bot with the most wins wins. You may submit multiple bots as long as they differ in strategy. Bots will play against every other bot. The bot who is currently playing against every other bot goes first, and goes second when their opponent is playing against every other bot. Bots will face off in an arena with x boundaries of 10 and -10 and y boundaries of 10 and -10. Bots will either start at (-5, 0) or (5, 0). Your goal is to defeat the other bot by reducing it's HP to 0 or less. Bots start with 20+armor modifier HP and do not regenerate health. Your bot defeats the other bots using weapons, which have damage, range, and cooldown. Armor has speed.

Submissions

Submissions should be a JS function that takes the following parameters:

  • curr_x - the current x coordinate of your bot
  • curr_y - the current y coordinate of your bot
  • enemy_x - the current x coordinate of your opponent's bot
  • enemy_y - the current y coordinate of your opponent's bot
  • enemy_armor - the armor that your enemy is wearing
  • storage - a storage object you can use to store data between function calls

The function should return an array with 3 items (in the following order):

  • desired x - the x coordinate you want to move to
  • desired y - the y coord you want to move to
  • use weapon? - if true, and desired x and desired y are Infinity, then you use your weapon

Submissions should be structured as

Weapon: your weapon here
Armor: your armor here

function definition
block

Explanation underneath, if any.

Armor

(currently designing new weapons and armor) The types of armor available are:

  • Light - increases HP by 3, has a speed of 3
  • Medium - increases HP by 5, has a speed of 2
  • Heavy - increases HP by 7, has a speed of 1

Weapons

The types of weapons are:

  • Laser - High-range, high-damage, low ROF. 5 points of damage, 5 rounds to cool down, and a range of 6 units
  • Rifle - General-purpose weapon. 5 damage, range of 4, 3 rounds to cool down.
  • Sword - High-ROF, high-damage spiky thing. 5 points of damage, really low range of 1, and a rather quick 2 rounds to cool down.

Turns

On your turn, you can either move or use weapon (or do nothing, if that's what you really want to do).

  • If you move, you can move a distance (computed using the Euclidean Distance formula) less-than or equal-to (<=) your armor's speed.
  • If you choose to use weapon, and if the enemy is in range of your weapon, then you deal damage equal to your weapon's damage and the weapon goes into cooldown. A weapon in cooldown can't be used. Weapons can be used after a number of turns equal to their cooldown property has passed after being used.
  • To do nothing, simply return your current x and y coordinates, like so: return [curr_x, curr_y, false].

Rules

  • If you try to use a weapon during cooldown, nothing happens and your turn ends
  • If you try to use a weapon and your opponent is out of range, nothing happens and your turn ends.
  • If you try to move more than your armor's speed, nothing happens and your turn ends
  • If you try to move out-of-bounds, same thing
  • If you move into another bot's space, then the bot with the lowest HP loses and the bot with the highest HP wins, making this a viable strategy.
  • All standard loopholes (accessing controller, duplicate bots, suicide bots, etc.) are, of course, disallowed.

Examples

TowerDefense Weapon: Laser
Armor: Heavy

function(curr_x, curr_y, enemy_x, enemy_y, enemy_armor, storage) {
    let actions = [Infinity, Infinity, true];
    return actions;
}

Just sits and shoots, lol. A perfectly viable strategy (and a rather strong one, too, while weapons are still being reworked). Takes the highest-hp armor available because it doesn't need to move at all.


DumbBot

Weapon: Rifle
Armor: Medium

function(curr_x, curr_y, enemy_x, enemy_y, enemy_armor, storage) {
      let actions = [curr_x, curr_y, false];
      // if storage is empty
      if (!storage.data) {
        // then write our starting loc
        storage.data = curr_x.toString() + " " + curr_y.toString();
      }

      // if we're starting at x = -5
      if (storage.data.includes("-5")) {
        if (curr_x < 3) {
          // move right
          actions[0] += 2;
          actions[1] = curr_y;
        }
        // otherwise we must be close enough
        else {storage.data = "shoot";}
      }

Assumes enemy doesn't move (such as TowerDefense). Moves to the enemy's starting location, then shoots. As such, takes the Medium armor and the Rifle. Kind of a generic all-purpose bot, like the weapons and armor it uses.

Controller

The controller can be found here. Run all current submissions here.

Best of luck, and, may the odds be ever in your favor (even though this is a 1v1 and not a FFA)

Sandbox

  • Are the rules explained thoroughly? Is anything unclear?
  • Is the game (armor, weapons, punishment for breaking rules, etc.) balanced well? Are there any strategies that dominate?
  • Would this KOTH be fun?
  • Would you participate in the competition?
  • Any obvious bugs in the (horribly messy) controller code?
  • Create a simple submission similar to something that you would actually submit and test it against the example bots. Is the code still working?
\$\endgroup\$
8
  • \$\begingroup\$ An arena that contains the points (-5, 0) and (5, 0) would be larger than 10x10. Isn't the heavy armor creating more health that can be removed in a turn? \$\endgroup\$ Jun 15, 2020 at 17:07
  • \$\begingroup\$ Armor adds health at beginning of game. It’s a one-time buff. And yes, I messed up the field size. It’s 20x20 \$\endgroup\$
    – nope
    Jun 15, 2020 at 21:32
  • \$\begingroup\$ If armor is one-time, then the Light armor is strictly better than Medium because both last only for one shot, leading to various weirdness. \$\endgroup\$ Jun 16, 2020 at 1:41
  • \$\begingroup\$ a) How much health does each bot start with? b) Are you sure the arena is supposed to be 20x20? Not 21x21 or 19x19? As it is one of the bots will have to start closer to the edge (and which one it is isn't specified as far as I can tell). c) Is there a reason why some disallowed actions cause an immediate forfeit while others only make the offending bot skip a turn? d) The "Stuff Not Allowed" and "Other viable strategies" are confusing. Namely, under the first one you list a viable strategy, and under the second - something that's disallowed. \$\endgroup\$
    – Alion
    Jun 16, 2020 at 12:02
  • \$\begingroup\$ b.2) On further inspection, is this game grid-based or played on a continuous arena? As in, can you move in fractions? In the second case, (b) becomes irrelevant. \$\endgroup\$
    – Alion
    Jun 16, 2020 at 12:40
  • \$\begingroup\$ e) What's the mysterious "Distance formula"? Plain old euclidean distance? Taxicab? Chebyshev? f.1) How do you "include [what weapon and armor your bot is using] in your submission"? f.2) More generally, is there a specific submission format? Or will anything human-readable do? g) Are bots allowed to act randomly with the help of Math.random, for example? h) Is it really necessary to override this loophole? \$\endgroup\$
    – Alion
    Jun 16, 2020 at 13:06
  • \$\begingroup\$ i) Have you considered adding more weapon types or modifying the current set? Currently the choice is pretty one-dimensional, since you avoid varying the damage property. \$\endgroup\$
    – Alion
    Jun 16, 2020 at 13:07
  • \$\begingroup\$ As for whether this KotH is fun or not - it seems okay, but I think it lacks variety. Addressing (i) would probably help with that. I would definitely give this challenge a try regardless if it hit main (perhaps as a result of me being a JS KotH junkie). \$\endgroup\$
    – Alion
    Jun 16, 2020 at 13:18
3
\$\begingroup\$

Posted.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Just an observation: the table is almost antisymmetric reading top-down vs bottom-up. That is, if you split the table in half based on the value of A, then the X value in any row in the top half of the table is mostly the opposite of the X value in the same row (reading upwards from the bottom) in the bottom half. Whether that simplifies the problem at all, I'm not sure. \$\endgroup\$
    – Dingus
    Jun 15, 2020 at 0:23
  • \$\begingroup\$ I think the [kolmogorov-complexity] tag should apply here, and the [number] tag doesn't seem very helpful. \$\endgroup\$ Jun 16, 2020 at 5:58
3
\$\begingroup\$

Polyglot: Convert Case


Your task is to write a program that performs case conversion from plain text, and other case formats, into one of the specified formats below. Inputs will be either plain lowercase text, or one of the detailed cases below. You must remove non-alphabetic characters, except (space), _ and -, split on these, or differences in case (e.g. bA), and either join on the desired chars or join on the empty string and capitalise the first char of each word (or not the first of doing camel case). Your program must be a polyglot in at least two different languages. For example, running your code in Python 2 transforms input to snake_case, running it in JavaScript transforms to kebab-case, Ruby transforms to PascalCase and 05AB1E transforms to camelCase.

Tasks

The following case conversions must be completed:

camelCase

this is a test         thisIsATest
camelCaseTest          camelCaseTest
PascalCaseTest         pascalCaseTest
snake_case_test        snakeCaseTest
kebab-case-test        kebabCaseTest
Testing!!one!!!1!!!    testingOne1
aBCDef                 aBCDef
ABCDef                 aBCDef
a_b_c_def              aBCDef
a-b-c-def              aBCDef

Try it online!

PascalCase

this is a test         ThisIsATest
camelCaseTest          CamelCaseTest
PascalCaseTest         PascalCaseTest
snake_case_test        SnakeCaseTest
kebab-case-test        KebabCaseTest
Testing!!one!!!1!!!    TestingOne1
aBCDef                 ABCDef
ABCDef                 ABCDef
a_b_c_def              ABCDef
a-b-c-def              ABCDef

Try it online!

snake_case

this is a test         this_is_a_test
camelCaseTest          camel_case_test
PascalCaseTest         pascal_case_test
snake_case_test        snake_case_test
kebab-case-test        kebab_case_test
Testing!!one!!!1!!!    testing_one_1
aBCDef                 a_b_c_def
ABCDef                 a_b_c_def
a_b_c_def              a_b_c_def
a-b-c-def              a_b_c_def

Try it online!

UPPER_SNAKE_CASE

this is a test        THIS_IS_A_TEST
camelCaseTest         CAMEL_CASE_TEST
PascalCaseTest        PASCAL_CASE_TEST
snake_case_test       SNAKE_CASE_TEST
kebab-case-test       KEBAB_CASE_TEST
Testing!!one!!!1!!!   TESTING_ONE_1
aBCDef                A_B_C_DEF
ABCDef                A_B_C_DEF
a_b_c_def             A_B_C_DEF
a-b-c-def             A_B_C_DEF

Try it online!

kebab-case

this is a test         this-is-a-test
camelCaseTest          camel-case-test
PascalCaseTest         pascal-case-test
snake_case_test        snake-case-test
kebab-case-test        kebab-case-test
Testing!!one!!!1!!!    testing-one-1
aBCDef                 a-b-c-def
ABCDef                 a-b-c-def
a_b_c_def              a-b-c-def
a-b-c-def              a-b-c-def

Try it online!

Rules

  • Your code should produce the same output as the linked examples.
  • Entries with the most conversions win, with code length being a tie-breaker.

Questions for sandbox

  • Have I missed any other major naming schemes?
\$\endgroup\$
16
  • \$\begingroup\$ in the example, at the start, you said python 2 and javascript, while below there are 4 conversions. Must you do all of them in a different language each? Also, do language versions (python 2 / python 3) count as different languages? \$\endgroup\$ Jul 3, 2020 at 3:27
  • \$\begingroup\$ @CommandMaster It was just a cut down example to explain the concept of a polyglot. I'm still unsure whether it makes sense to allow two or more languages or require all four. I feel like allowing two or more would enable more elegant solutions as snake Vs kebab is the same bar the delimiter and Pascal Vs camel is the same bar leading capitalisation. What're your thoughts? \$\endgroup\$ Jul 3, 2020 at 6:28
  • \$\begingroup\$ Different language versions count as different languages (not sure of there's a relevant meta post. I'll try and look for it when I'm not on mobile.) \$\endgroup\$ Jul 3, 2020 at 6:29
  • \$\begingroup\$ If the usual 'different command-line flags count as different languages' rule applies, then is there a risk that the snake vs kebab cases could be trivially solved using the command-line flag to specify the delimiter...? \$\endgroup\$ Jul 6, 2020 at 11:23
  • \$\begingroup\$ Yeah, I guess so. Something like Perl's -i flag could enable using $^I to be either - or _. Although then doing the same would probably be tricky and potentially still at least a little ingenious. \$\endgroup\$ Jul 6, 2020 at 12:46
  • \$\begingroup\$ "Have I missed any other major naming schemes?" Yes: Ada_Ninety_Five_Case, Title Case, and (jokingly) StRaNgEcAsE. What's wrong with UPPER_SNAKE_CASE? \$\endgroup\$ Jul 9, 2020 at 5:55
  • \$\begingroup\$ @fireflame241 I think that converting back from upper snake case might be slightly more tricky than just snake case, as checking for an underscore might not be enough to see if there's more transformation necessary, if for example there was already an underscore in normal text... I could state that isn't a problem though I guess? Adding more cases might make me lean towards mandating only a minimum of two transformations required as well and changing the scoring to number of transformations with code length as a tie-breaker... Thanks again, will think on this a bit. \$\endgroup\$ Jul 9, 2020 at 6:16
  • \$\begingroup\$ If you restrict words to be composed only of letters, then you could avoid that issue, and a few others. For example, how would aB_Cd be handled? It could be snake case, where the _ separates the words, or camel case, where the _ is the start of the second word. I think right now there's too many test cases, too little explanation. \$\endgroup\$ Jul 9, 2020 at 6:32
  • \$\begingroup\$ @fireflame241 Yeah, I think you're right. Ok. I'll work on this. Thanks! \$\endgroup\$ Jul 9, 2020 at 6:45
  • \$\begingroup\$ Re: flags as languages again. I was more thinking of a program 'checking' to see what flags had been used (even if they have no direct effect), and modifying its behaviour accordingly. For instance, perl -m foo + then checking whether foo is loaded. This would also be similar to language+library = different language. Worst cheat of all would be awk -v mode=1... \$\endgroup\$ Jul 9, 2020 at 16:03
  • \$\begingroup\$ Along the same lines, it would be important to specify that it isn't Ok to just run different versions of a language (which currently 'count' as different languages), and for the program to determine the version & modify its behaviour. \$\endgroup\$ Jul 9, 2020 at 16:10
  • \$\begingroup\$ I don't think it's possible to rule out different language versions for polyglot challenges, and using flags to classify as different languages might be questionable too. I guess if the answers aren't in the spirit of the task or are a little boring they'll be voted on accordingly. I'm open to more input on this though! Thank you for the feedback! \$\endgroup\$ Jul 9, 2020 at 21:13
  • \$\begingroup\$ "polygot in at least two different languages" so we must write 4 programs, how can there be fewer than 4 languages? \$\endgroup\$
    – qwr
    Jul 9, 2020 at 22:46
  • \$\begingroup\$ @qwr I just amended the rules to allow 2 or more languages, you don't have to have all 5. I'm hoping this will allow some creative solutions. If I missed a reference to that I'm struggling to see it, but morning eyes... \$\endgroup\$ Jul 10, 2020 at 6:07
  • \$\begingroup\$ For some reason I thought there were 4 programs. So to clarify, the minimum is two languages / two conversions? \$\endgroup\$
    – qwr
    Jul 10, 2020 at 6:11
3
\$\begingroup\$
\$\endgroup\$
8
  • \$\begingroup\$ What's the upper limit of the output string Y? \$\endgroup\$
    – user92069
    Jul 25, 2020 at 5:24
  • \$\begingroup\$ @Third-party'Chef' Y is a programming language not a string. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 25, 2020 at 12:31
  • \$\begingroup\$ Sorry, I meant X. \$\endgroup\$
    – user92069
    Jul 25, 2020 at 12:32
  • \$\begingroup\$ @Third-party'Chef' I didn't put an upper limit, but its length is your score so longer means worse score. Is there some issue I am not seeing that means an upper limit is needed. \$\endgroup\$
    – Wheat Wizard Mod
    Jul 25, 2020 at 12:36
  • \$\begingroup\$ Now that this has been posted to main, could you delete this proposal to create more space for new answers? \$\endgroup\$ Sep 25, 2020 at 0:51
  • \$\begingroup\$ @cairdcoinheringaahing you know that that takes up more space right? \$\endgroup\$
    – Wheat Wizard Mod
    Sep 25, 2020 at 4:04
  • \$\begingroup\$ Deleting the post? How does it take up more space? It's no change from 10k+ users and it removes an answer for <10k users \$\endgroup\$ Sep 25, 2020 at 12:28
  • \$\begingroup\$ @cairdcoinheringaahing It does increase the size for users above 10k. You can test it for yourself if you want. Further comments also increase the size. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 25, 2020 at 18:53
3
\$\begingroup\$

Is this Chessboard Reachable?

The goal of this challenge is to determine, given the state of a chessboard, whether or not that chessboard can actually be reached in the course of standard play. Of course, doing this in general is a rather hard problem, so we'll be simplifying the problem to a set of a few rules which should approximate the "reachability" constraint.

Your input will be a chessboard, specifying what pieces are at what positions on the 8x8 board. At each position, there can be either nothing or a piece. If there is a piece, it is either a pawn, bishop, knight, rook, queen, or king, and it is either white or black. Input can be taken in any reasonable form. Your output should be truthy or falsy, indicating whether all of the below rules are satisfied.

For the below rules, I'll be using standard chess notation to refer to the squares on the board. That is, I'll be referring to squares on the board by their rank (1-8) and their file (a-h), as such

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

where the white player starts on ranks 1-2 and the black player starts on ranks 7-8. Obviously, you don't have to use the same notation, and if it's easier for you to take the board input flipped or rotated, that's fine too as long as you specify it in your answer.

For one of the rules, you have to distinguish between white and black squares on the board. The board is layered with a checkerboard pattern, so white squares are always immediately surrounded by black on all four sides, and vice versa. In typical chess, the a1 square is black, but that doesn't really matter for the below criteria.

The Rules

In order for a board to be considered reachable, it must satisfy all of the following rules. This is , so you don't have to tell me which rule an unreachable board violated; all I expect of your output is a "yes" or a "no".

  1. White and black each have exactly one king on the board: no more, no less.

  2. Pawns cannot appear on rank 1 or rank 8.

  3. Each player has a maximum of 16 pieces on the board total. These pieces must be a subset of the following: 2 bishops, 2 rooks, 2 knights, 1 queen, 1 king, and 8 wildcards. The "wildcard" pieces can be any piece they please (since we assume pawns could have been promoted).

  4. For either player, if that player has at least two bishops, and those two bishops cannot have been promoted from pawns (i.e. they must be the "bishops" in rule 3, not the "wildcards"), then that player must have at least one bishop on a white square and at least one bishop on a black square.

  5. All of a player's pawns must be able to reach the square they're occupying. More formally, for each player, there must be an assignment (an injective function) from the set of that player's surviving pawns to the files (a-h) they started on, such that each pawn can reach its current position from its starting position with only forward and forward-diagonal movements.

Pawn Movements

Rule 5 may require some elaboration. Suppose a white pawn is on d5. Then it could have come from the following places (indicated by X)

 8........
 7........
 6........
 5...♙....
 4..XXX...
 3.XXXXX..
 2XXXXXXX.
 1........
  abcdefgh

So it could have started on a2, b2, c2, d2, e2, f2, or g2, but not h2. There must be an assignment of pawns to starting positions such that no two pawns started at the same position and every pawn can reach its current position from where it began. A black pawn follows the same rules but started on rank 7 and moves down rather than up. So a black pawn at the same position could have come from b7, c7, d7, e7, or f7, as follows.

 8........
 7.XXXXX..
 6..XXX...
 5...♟....
 4........
 3........
 2........
 1........
  abcdefgh

Notes

  • Only the rules above apply. Other complexities of a standard game of chess (in particular, castling or en passant) are not part of this problem and should not be considered.
  • This is , so the shortest solution wins.
  • Input can be taken in whatever form is most convenient. Output follows the usual rules, so any two distinct outputs for truthy/falsy are acceptable.
  • This is an oversimplification of the reachability problem in chess. As such, an answer which provably enumerates every chessboard and tests for membership is not correct.

Examples

Reachable chessboards (true):

 8♜♞♝♛♚♝♞♜
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1♖♘♗♕♔♗♘♖
  abcdefgh

 8........
 7........
 6........
 5........
 4........
 3........
 2..♚.....
 1.....♔..
  abcdefgh

 8........
 7.....♚..
 6.♛......
 5...♟....
 4........
 3.....♕..
 2........
 1...♔....
  abcdefgh

 8.....♚..
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1....♔...
  abcdefgh

 8.....♚...
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1....♔...
  abcdefgh

 8........
 7.♚......
 6...♕♕♕♕.
 5..♕....♕
 4..♕..♔.♕
 3.......♕
 2........
 1........
  abcdefgh

 8........
 7...♚.♟.♙
 6.♙.♙..♙.
 5.....♘..
 4.♕..♕♘♗♖
 3.....♘♗♖
 2..♕....♖
 1......♔.
  abcdefgh

 8♜..♛♚♜♜♜
 7♟♟♟♟♟♟..
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1♖♘♗♕♔♗♘♖
  abcdefgh

 8♜♞♝♛♚♝♞♜
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙.
 1♖♗♘♕♔♗♘♖
  abcdefgh

 8♛♛♛♛♛♛.♛
 7........
 6......♚.
 5.♝.♝....
 4.....♟..
 3........
 2..♖♖♖.♔.
 1........
  abcdefgh

 8.....♚..
 7........
 6........
 5........
 4........
 3.♙♙.....
 2..♙♙♙♙♙♙
 1.....♔..
  abcdefgh

 8.....♚..
 7........
 6........
 5........
 4........
 3.....♙..
 2...♙♙♙.♙
 1.....♔..
  abcdefgh

 8.....♚..
 7........
 6.♟♟♟♟...
 5.♟♟.....
 4........
 3........
 2........
 1.....♔..
  abcdefgh

Unreachable chessboards (false):

(Rule 1: Not enough kings)

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

(Rule 1: Too many kings)

 8♚♚♚♚♚♚♚♚
 7♚♚♚♚♚♚♚♚
 6♚♚♚♚♚♚♚♚
 5♚♚♚♚♚♚♚♚
 4♚♚♚♚♚♚♚♚
 3........
 2........
 1...♔....
  abcdefgh

(Rule 2: Bad white pawn placement)

 8.....♚..
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2.♙♙♙♙♙♙♙
 1♙...♔...
  abcdefgh

(Rule 2: Bad black pawn placement)

 8.♟...♚..
 7♟.♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1....♔...
  abcdefgh

(Rule 3: Too many white queens)

 8........
 7.♚......
 6...♕♕♕♕.
 5..♕....♕
 4..♕..♔.♕
 3..♕....♕
 2........
 1........
  abcdefgh

(Rule 3: Too many black pieces)

 8♜♞♝♛♚♝♞♜
 7♟♟♟♟♟♟♟♟
 6......♟.
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1♖♘♗♕♔♗♘♖
  abcdefgh

(Rule 3: Too many white pieces)

 8........
 7...♚.♙.♙
 6.♙.♙..♙.
 5.....♘..
 4.♕..♕♘♗♖
 3.....♘♗♖
 2..♕....♖
 1......♔.
  abcdefgh

(Rule 3: Too many black rooks)

 8♜..♛♚♜♜♜
 7♟♟♟♟♟♟♟.
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1♖♘♗♕♔♗♘♖
  abcdefgh

(Rule 4: White bishops are the same color)

 8♜♞♝♛♚♝♞♜
 7♟♟♟♟♟♟♟♟
 6........
 5........
 4........
 3........
 2♙♙♙♙♙♙♙♙
 1♖♗♘♕♔♗♘♖
  abcdefgh

(Rule 4: Black bishops are the same color)

 8♛♛♛♛♛♛♛♛
 7........
 6......♚.
 5.♝.♝....
 4.....♟..
 3........
 2..♖♖♖.♔.
 1........
  abcdefgh

(Rule 5: White pawn placement is impossible)

 8.....♚..
 7........
 6........
 5........
 4........
 3..♙.....
 2.♙♙♙♙♙♙♙
 1.....♔..
  abcdefgh

(Rule 5: White pawn placement is impossible)

 8.....♚..
 7........
 6........
 5........
 4........
 3.....♙.♙
 2...♙♙♙.♙
 1.....♔..
  abcdefgh

(Rule 5: Black pawn placement is impossible)

 8.....♚..
 7.♟♟♟♟...
 6........
 5.♟♟.....
 4.♟♟.....
 3........
 2........
 1.....♔..
  abcdefgh

Example Implementation (Python 3)

# Takes input from stdin in the form shown above (a grid of Unicode
# chess characters and dots). Prints True if reachable. Prints False
# and the first rule number which is violated if unreachable.

import sys
from collections import defaultdict, namedtuple

Piece = namedtuple('Piece', ['color', 'type'])

# Read in the data from stdin.
data = []
for line in sys.stdin:
    chars = list(filter(lambda x: x in ".♟♙♝♗♞♘♜♖♛♕♚♔", line))
    if chars:
        data.append(chars)
    if len(data) == 8:
        break
assert len(data) == 8
for line in data:
    assert len(line) == 8

# Parse it into a more convenient format.
translation = {
    ".": None,
    "♟": Piece('black', 'pawn'),
    "♙": Piece('white', 'pawn'),
    "♝": Piece('black', 'bishop'),
    "♗": Piece('white', 'bishop'),
    "♞": Piece('black', 'knight'),
    "♘": Piece('white', 'knight'),
    "♜": Piece('black', 'rook'),
    "♖": Piece('white', 'rook'),
    "♛": Piece('black', 'queen'),
    "♕": Piece('white', 'queen'),
    "♚": Piece('black', 'king'),
    "♔": Piece('white', 'king'),
}
for rank in data:
    for i in range(8):
        rank[i] = translation[rank[i]]

# Count the number of each piece that each player has, slotting
# necessary pawn promotions into their own category.
allowed = { 'bishop': 2, 'rook': 2, 'knight': 2, 'king': 999, 'queen': 1, 'pawn': 0 }
pieces = defaultdict(lambda: 0)
for rank in data:
    for piece in rank:
        if piece is None:
            continue
        if pieces[piece] >= allowed[piece.type]:
            # Already have too many; it's a promoted pawn
            pieces[Piece(piece.color, 'pawn')] += 1
        else:
            # Count it normally
            pieces[piece] += 1

# Rule 1: Each color should have exactly one king.
if pieces[Piece('white', 'king')] != 1 or pieces[Piece('black', 'king')] != 1:
    print(False, 1)
    exit(0)

# Rule 2: Pawns cannot appear on rank 1 or rank 8.
for piece in data[0] + data[7]:
    if piece is not None and piece.type == 'pawn':
        print(False, 2)
        exit(0)

# Rule 3: Since we already put any "overflow" pieces at the pawn key,
# we just need to make sure we have at most eight pawns.
for color in ['white', 'black']:
    if pieces[Piece(color, 'pawn')] > 8:
        print(False, 3)
        exit(0)

# Rule 4: If we have both bishops and our pawns are all accounted for,
# then we have to have a bishop in each color.
for color in ['white', 'black']:
    if pieces[Piece(color, 'bishop')] >= 2 and pieces[Piece(color, 'pawn')] >= 8:
        squares = { 'white': False, 'black': False }
        for y, rank in enumerate(data):
            for x, piece in enumerate(rank):
                square_color = 'white' if (x + y) % 2 == 0 else 'black'
                if piece == Piece(color, 'bishop'):
                    squares[square_color] = True
        if not (squares['white'] and squares['black']):
            print(False, 4)
            exit(0)

# Rule 5: All pawns must be able to get to where they are. I solve
# this here by brute force (simply trying every possible permutation),
# which is exponentially inefficient, but it'll do for this example.
def recursive_assign(taken, choices, i):
    if i >= len(choices):
        return True
    current = choices[i]
    for x in current:
        if x not in taken:
            if recursive_assign(taken + [x], choices, i + 1):
                return True
    return False

for color in ['white', 'black']:
    starting_file = 6 if color == 'white' else 1
    choices = []
    for y, rank in enumerate(data):
        for x, piece in enumerate(rank):
            if piece == Piece(color, 'pawn'):
                possibilities = range(8)
                possibilities = filter(lambda i: abs(i - x) <= abs(y - starting_file), possibilities)
                choices.append(list(possibilities))
    if not recursive_assign([], choices, 0):
        print(False, 5)
        exit(0)

print(True)

Proposed Tags

Sandbox Concerns

  • I worry Rules 4 and 5 are still not clear enough. I tried to write them in a way that was as clear as possible while still being mathematically unambiguous.
\$\endgroup\$
4
  • \$\begingroup\$ too long. try to combine rules or at least don't draw so many of them in a column \$\endgroup\$ Aug 4, 2020 at 9:06
  • 2
    \$\begingroup\$ If you're going to use unicode chess symbols, use a double-wide filler character instead of .. The alignment in your examples is off, making it very distracting. I'd recommend switching them to ASCII letters using the typical KQRBNP convention. \$\endgroup\$
    – Beefster
    Aug 4, 2020 at 16:40
  • 2
    \$\begingroup\$ To add to Beefster's comment, in some fonts the chess symbols are not even double wide, they're somewhere in between. So double-wide fillers won't work either. +1 for ASCII notation. \$\endgroup\$
    – Bubbler
    Aug 4, 2020 at 23:43
  • \$\begingroup\$ if I recall correctly, you can have two bishops of the same color. Up to nine. By promoting pawns to bishops. Very rare indeed, but legal. I want this to main page, though. \$\endgroup\$ Aug 14, 2020 at 15:19
3
\$\begingroup\$

Road Sort Order

In Britain, road identifiers use a scheme of a letter, followed by a 1-4 digit number.

From Most-Important to Least-Important, the letters are:

M
A
B
C
D
U

The numbers also represent further assumptions around the importance of the road, such that a 1-digit number is more important than a 4-digit number.

Thus, the M898 is less important than the M8, but more important than the A8.

interesting but not relevant for the challenge - Roads are also sorted into nine Zones, of equal importance. The first number in each road identifier gives the Zone that the road starts in (e.g. A8 starts in Zone 8 - although there are exceptions where one Motorway spurs off of another, e.g. M48 is so named because it is a spur of the M4 even though it is officially in Zone 5).

The challenge

Given a pair of road identifiers, identify and output which is the most important road. Where there is no difference in importance by the above rules (e.g "B4063" and "B1234") then either output is acceptable.

Usual I/O rules apply, this is so lowest bytes wins. There will be two inputs, and no invalid inputs (i.e. they will follow the rules, although they may not be actual real-life roads).

If you say so in your answer, you may instead output the least significant road (i.e. as long as I know which it is, you can do either).

You may take the input as a string, array of strings, or array of strings and integers as follows:

"M123M223"
["M123","M223"]
["M",123,"M",223]

#SANDBOX# If there are input formats that you think should/n't be allowed, let me know.

Examples

  • A11,M2 -> M2(Motorways come before A roads)
  • M823,M89 -> M89 (two-digit roads are more important than 3-digit roads, even though 89 alphabetically comes after 823)
  • A1262,A150 -> A150
  • U6340,D6340 -> D6340
  • M1,M2 -> Either
  • B100,C99 -> B100
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'd suggest simplifying sorting to just comparing two distinct values. Or even, mapping a value to a number so that the comparisons are right. \$\endgroup\$
    – xnor
    Aug 4, 2020 at 19:56
  • \$\begingroup\$ @xnor sorry I'm not sure what you mean. Do you mean only ever have two inputs? \$\endgroup\$ Aug 5, 2020 at 7:25
  • \$\begingroup\$ Yes, like have a possible input be like f("A11","M2") with it being a decision problem to tell if the first or second one is more important. Or, just have us write a function g producing a number so that, say, g("A11")>g("M2"). \$\endgroup\$
    – xnor
    Aug 5, 2020 at 21:11
  • \$\begingroup\$ @xnor how's that? I've made it return the most (or least) significant road of a pair \$\endgroup\$ Aug 6, 2020 at 7:34
  • \$\begingroup\$ Looks good! I'm a bit worried about the "any sensible format" since counting digits is important. Like, would a length-four array padded with nulls for missing digits count as acceptable? I think this would be you compare the number parts as a direct list comparison in some languages. \$\endgroup\$
    – xnor
    Aug 7, 2020 at 3:15
3
\$\begingroup\$

Posted

Shift Tac Toe

Shift Tac Toe is a game that combines Tic Tac Toe and Connect 4 together. In this game, you start with a 3 by 3 board, and each row is connected to a slider that you can move left and right. At the start, the sliders all start to the very right(this means that you can't move the slider to the right on the first turn). Each slider can hold a total of 5 pieces. Each turn, the player can drop an O or a X in one of the 3 columns of the Tic Tac Toe grid depending on which turn it is, or the player can move one of the sliders one spot to the left or to the right. All pieces fall to the bottom most space that is unoccupied. The pieces can also fall from one slider to another outside the 3 by 3 grid. If a piece is outside the 3 by 3 grid and doesn't fall into the bottom slider, then the piece is taken out. If it does reach the bottom slider, it will stay in play. A notable example of this is shown in the following grid:

     --- --- --- --- ---
    |   |   |   |   - O -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    |   |   |   |   -   -
     --- --- --- --- ---
In the grid above, the dashes(-) indicate the part of the sliders that are outside of the 3 by 3 grid and the vertical bars(|) indicate the 3 by 3 grid.
As you can see, this is the starting board except that the middle slider is one spot over to the left, and that there is an O at the very top right. 
What happens in this scenario? There is nothing immediately underneath it, so does it go out of play? 
No. This is because it still falls into the bottom slider, which means that it is still in play.

The final grid is this:
     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    |   |   |   |   - O -
     --- --- --- --- --- 

Pieces can also stack outside of the 3 by 3 grid. Players will alternate between O and X, with the O player going first.

Example game:

Start with 3 by 3 grid with sliders all the way to the right:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- --- 
|   |   |   |   -   -
 --- --- --- --- ---

The O player places an O in the middle column of the 3 by 3 grid and it falls to the bottom:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- --- 
|   | O |   |   -   -
 --- --- --- --- ---

The X player then places an X in the middle column:

 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   | X |   |   -   -
 --- --- --- --- --- 
|   | O |   |   -   -
 --- --- --- --- ---

The O player then pushes the middle row slider one space to the left. 
Notice that after the slider moves, there is nothing under the X anymore, so it falls down. 
Also note that the slider has moved one space to the right as indicated below:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | X | O |   |   -   -
     --- --- --- --- ---

The X player places a X in the rightmost column:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | X | O | X |   -   -
     --- --- --- --- --- 

The O player then moves the bottom slider one spot to the left.
Notice that all the pieces shift one place to the left, and the leftmost X is now out of the playing field:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- 
- X | O | X |   |   -
 --- --- --- --- --- 

The X player places a X in the leftmost column:

     --- --- --- --- ---
    |   |   |   |   -   -
 --- --- --- --- --- ---
-   | X |   |   |   -
 --- --- --- --- --- 
- X | O | X |   |   -
 --- --- --- --- --- 

The O player places an O in the leftmost column:

     --- --- --- --- ---
    | O |   |   |   -   -
 --- --- --- --- --- ---
-   | X |   |   |   -
 --- --- --- --- --- 
- X | O | X |   |   -
 --- --- --- --- --- 

The X player shifts the top slider one place to the left. Notice that the O falls one place down because there is nothing beneath it:

 --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- ---
- O | X |   |   |   -
 --- --- --- --- --- 
- X | O | X |   |   -
 --- --- --- --- --- 

The O player is not very good at this game, so he shifts the middle slider one place to the right. 
This shifts all the pieces in the middle row one place to the right:

 --- --- --- --- ---
-   |   |   |   |   -
 --- --- --- --- --- ---
    | O | X |   |   -   -
 --- --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- --- 

The X player wins the game by placing a X in the middle column:

 --- --- --- --- ---
-   |   | X |   |   -
 --- --- --- --- --- ---
    | O | X |   |   -   -
 --- --- --- --- --- ---
- X | O | X |   |   -
 --- --- --- --- --- 

Your job is to take in a string or array of any length that only consists of 9 unique characters(you choose the characters). Three of the characters will choose which column you place the X or O(depending on whose turn it is), three of them will choose which slider to move right, and the last three will choose which slider to move left. You can assume that the input only has these 9 characters. The output should be a 3 by 3 matrix or some kind of list/string that clearly shows the final position of the grid upon following the instructions of the input. You can assume that all inputs are valid. Each character takes up a turn. Also, if any move results in a winning move(forms 3 in a row in the 3 by 3 grid like regular Tic-Tac-Toe), then ignore the rest of the input. Note that the pieces that form the winning 3 in a row all have to be in the 3 by 3 grid. The two example grids below are NOT winning positions:

Grid #1:
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- ---
|   |   |   |   -   -
 --- --- --- --- --- 
|   |   | O | O - O -
 --- --- --- --- ---
This is not a winning move because two of the O's are outside the playing field, despite the fact that it forms a 3 in a row.
Using the character assignment stated below, this grid pattern can be achieved with 99372467643.

Grid #2:
 --- --- --- --- ---
|   |   |   |   - O -
 --- --- --- --- ---
|   |   |   | O - X -
 --- --- --- --- --- 
|   |   | O | X - X -
 --- --- --- --- ---
This is not a winning position because two of the O's are outside the playing field.
Using the character assignment below, this grid pattern can be achieved with 939318836537734654

In the examples below, 1, 2, and 3 mean drop in the leftmost, middle, and rightmost column respectively. 4, 5, and 6 mean to move the top, middle, and bottom slider to the right respectively, and 7, 8, and 9 mean to move the top, middle, and bottom slider to the left respectively.

Examples

Input will be in the form of a string
Output will be a list of lists, with each sub-list representing a row(I'm Python programmer so this list format might not be compatible with all languages). 
The first, second, and third sub-list correspond to the top, middle, and bottom row of the 3 by 3 grid respectively. 
The output will have 'O' for the O pieces, 'X' for the X pieces, and an empty string for empty spaces.

Input: 123332
Output:
[['','','O'],
 ['','X','X'],
 ['O','X','O']] 

Input: 33387741347
Output:
[['','',''],
 ['','','O'],
 ['X','O','X']]

Input: 2283911752
Output:
[['','X',''],
 ['O','X',''],
 ['O','X','']]

Input: 228374739
Output:
[['','',''],
 ['','',''],
 ['X','X','X']]

Input: 8873334917349
Output:
[['','',''],
 ['','','O'],
 ['X','X','O']]

Input: 799333466
Output:
[['','',''],
 ['','',''],
 ['','','']]

Input: 99372467643
Output:
[['','',''],
 ['','',''],
 ['','','O']]

Input: 939318836537734654
Output:
[['','',''],
 ['','',''],
 ['','','O']]

This is , so shortest code wins!

My concerns about this challenge:

Are the rules of this game explained enough? Do you understand this game?

Is this a good challenge overall?

Are the examples correct(if you understand the rules)?

Should I put more examples(or if you understand the rules, could you supply me with some)?

What other tags can this challenge fit into?

\$\endgroup\$
7
  • \$\begingroup\$ Welcome to the site! Generally it's a good idea to leave challenges in the Sandbox for at least a few days to give people time to review. Even more so if you have questions/concerns about your challenge. \$\endgroup\$
    – Dingus
    Aug 2, 2020 at 4:51
  • \$\begingroup\$ @Dingus The problem is I already posted it so what do I do now? \$\endgroup\$
    – Aiden Chow
    Aug 2, 2020 at 7:01
  • \$\begingroup\$ Actually I was referring to future challenges. For this one, there are probably two options: 1. Leave it on main, responding to feedback in the comments. 2. Delete the main post, wait a while (maybe a week) for more feedback here, then repost/undelete on main. The choice really depends on how much needs to be done to iron out the kinks. \$\endgroup\$
    – Dingus
    Aug 3, 2020 at 0:11
  • 1
    \$\begingroup\$ If the moves result in any unpermitted moves, then output any falsey value challenges usually assume only valid input unless the challenge itself is to determine only if the input is valid or not. \$\endgroup\$
    – Noodle9
    Aug 4, 2020 at 19:30
  • \$\begingroup\$ @Noodle9 Ok so should I take that out? \$\endgroup\$
    – Aiden Chow
    Aug 5, 2020 at 2:04
  • \$\begingroup\$ Make it one or the other, either assume valid input and output grid. Or determine whether or not input is valid as the challenge. \$\endgroup\$
    – Noodle9
    Aug 5, 2020 at 9:30
  • \$\begingroup\$ @Noodle9 Ok edited. \$\endgroup\$
    – Aiden Chow
    Aug 5, 2020 at 18:02
3
\$\begingroup\$

Generalized Game Theory KOTH

Game Theory is a field of mathematics that is concerned with strategic interactions among 'rational decision-makers'. The main focus of game theory is the payoff-matrix.

A payoff matrix represents an interaction between two parties, and shows how many points a party can get if they choose different strategies. Here is an example of a payoff matrix:

             Player 1
             A  |   B
Player 2 +------+-------
       A | 3, 3 | 5, 1
         +------+-------
       B | 1, 5 | 2, 2

In this example, if player 1 chooses A and player 2 also chooses A, they would both get 3 points. If player 1 chooses B but player 2 chooses A, player would get 5 points but player 2 would only get 1.

The above payoff matrix is an example of the prisoners dilemma

The challenge

Programs will face off in a round-robin tournament. Each round will consist of a randomly generated payoff matrix, with both programs choosing either strategy A or strategy B. Programs will earn points accordingly. The winner will be the program with the most points, with ties broken by source code length.

Questions for meta:

  • best practices for creating KOTH challenges?
    • language considerations? I'm most comfortable with javascript but am also capable of writing in python
    • is it better to limit a KOTH to one language? it's easier to manage but limits who can submit
    • or allow multiple languages? It allows more people to compete but is more difficult to judge
  • Any comments about the overall problem?
    • Has this been done before?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 1-1) Either JS or Python should be fine. Both are popular here and you can share the controller's code on TIO so that others can easily run it. Some other KOTH writers tend to provide a visual interface, but it's completely optional. 1-2) KOTH is usually limited to one language since they have to compete through the controller. 2) I don't think it's done before. But tie-breaking by code golf is not a good idea (in fact, tie breaking is not necessary at all). \$\endgroup\$
    – Bubbler
    Aug 19, 2020 at 0:29
  • \$\begingroup\$ Also, if you're planning to run through hundreds of payoff matrices, it will be more interesting to allow the programs to remember previous matches, so the whole competition looks like a generalized repeated game. \$\endgroup\$
    – Bubbler
    Aug 19, 2020 at 0:32
  • \$\begingroup\$ @Bubbler In that case I will probably make the controller in javascript. And yes, the game will definitely be repeated and programs will be able to access the past history. thank you for your feedback :) \$\endgroup\$
    – thesilican
    Aug 19, 2020 at 0:40
3
\$\begingroup\$

Implement the Polygamma function

\$\endgroup\$
4
  • \$\begingroup\$ Mathematica: PolyGamma. \$\endgroup\$ Jul 27, 2020 at 3:37
  • 1
    \$\begingroup\$ Looks good, except that I have no idea where to start. \$\endgroup\$
    – Bubbler
    Jul 31, 2020 at 1:00
  • \$\begingroup\$ You say, "Results may differ due to floating point inaccuracies," but how accurate do results have to be? I'd guess, from "the output should show at least 5 decimal places," that you'd like the results to be accurate to at least 5 decimal places? (But I'm not sure that makes sense for large values like m=46, z=5, since floating point values have significant digits, not significant decimal places.) \$\endgroup\$
    – DLosc
    Aug 30, 2020 at 21:33
  • \$\begingroup\$ @DLosc I'm not the best when it comes to floating point issues, but I don't see any major issues with requiring the first 5 decimal places to be correct \$\endgroup\$ Aug 30, 2020 at 21:38
3
\$\begingroup\$

The Turing Text Tape

Posted here: TTT: Turing Text Tape

\$\endgroup\$
2
  • \$\begingroup\$ If you have a reference implementation, please do add it in. \$\endgroup\$
    – Razetime
    Sep 23, 2020 at 4:43
  • \$\begingroup\$ I already did, there's a link to a python 3 implementation... \$\endgroup\$ Sep 23, 2020 at 20:45
3
\$\begingroup\$

Peel away the layers - Cops

Peel away the layers - Robbers

\$\endgroup\$
13
  • 3
    \$\begingroup\$ I feel like you could remove a lot of the complexity of the challenge description by just requiring robbers to crack the whole submission at once, and so you don't need to specify MD5 hashes or anything like that and you don't need to worry about rep/CW/answer chaining. This might also allow for creativity by creating 'misleading' chains of polyglots (you decode with lang A in a chain, you get Greetings?, but in lang B you get Greetings!). You should also specify whether multiple of the same language in a chain is allowed. \$\endgroup\$
    – Sisyphus
    Sep 26, 2020 at 11:42
  • \$\begingroup\$ Also consider that answers of the form echo "....." would be valid, and reduce to The Programming Language Quiz. You might be able to ward off just replicating the original challenge by having a very strict set of allowed languages (eg. must be on TIO), which would force using the polyglot system effectively. \$\endgroup\$
    – Sisyphus
    Sep 26, 2020 at 11:42
  • \$\begingroup\$ @Sisyphus I've sat on it for a few days, and I think that's probably the best way forwards, even if it does make the Robbers' jobs harder. "You may repeat languages" is already in the spec (now bolded). I don't want to have to limit the available languages/interpreters any more than I have to, as some of the best answers to the last challenge like this (TPLQ) relied on the more obscure interpreters, and limiting languages could ruin that. Given that this requires 2 languages minimum, and that echo "..." style answers probably won't be competitive, I think this should be different enough \$\endgroup\$ Sep 30, 2020 at 22:25
  • \$\begingroup\$ Looks a lot better. You have my upvote. \$\endgroup\$
    – Sisyphus
    Sep 30, 2020 at 22:52
  • \$\begingroup\$ You should limit the program size to fitting literally inside the answer, otherwise you might get unary shenanigans that make cracking literally impossible \$\endgroup\$
    – pxeger
    Oct 1, 2020 at 16:06
  • 1
    \$\begingroup\$ @pxeger On second thoughts, I've decided to limit each program to 65535 bytes, just to keep it sensible \$\endgroup\$ Oct 1, 2020 at 16:33
  • \$\begingroup\$ Does an inner layer have to output a full program, or can it print a function? \$\endgroup\$
    – pxeger
    Oct 1, 2020 at 18:50
  • 1
    \$\begingroup\$ @pxeger Either is fine, I'll edit that in \$\endgroup\$ Oct 1, 2020 at 18:55
  • 1
    \$\begingroup\$ So just to clarify, we don't need to reveal the number of layers, just the number of distinct languages? \$\endgroup\$
    – Sisyphus
    Oct 4, 2020 at 7:43
  • \$\begingroup\$ "Free here means that anyone can use the program without having to pay to do so" - is it still free if they must pay with their time and sanity? \$\endgroup\$
    – pxeger
    Oct 4, 2020 at 8:42
  • \$\begingroup\$ Did you mean Robbers' not Robber's chatroom - it's not entirely clear \$\endgroup\$
    – pxeger
    Oct 4, 2020 at 11:52
  • 2
    \$\begingroup\$ @Sisyphus the robbers' task is hard enough as is, let alone having to deal with cops that may use 2 languages but have 15 or so layers, so I've edited it to consistently say that you have to reveal the number of layers, \$\endgroup\$ Oct 4, 2020 at 19:35
  • \$\begingroup\$ @pxeger "Free" means per site standards, and yes, I've corrected that typo \$\endgroup\$ Oct 4, 2020 at 19:35
3
\$\begingroup\$

We're all unique in our own way

\$\endgroup\$
9
  • \$\begingroup\$ I like the idea, but I feel like there should be some incentive to make the byte requirement small, large, contain common bytes, contain uncommon bytes, etc. Is there any reason to pick anything other than randomly? \$\endgroup\$ Oct 4, 2020 at 0:05
  • 1
    \$\begingroup\$ @RedwolfPrograms I've decided to make the number of bytes allowed has to be unique for each answer (i.e. only one answer may allow 120 bytes etc.), which means that people will have to be more selective with how many bytes are allowed when posting new answers, as well as which of those bytes are allowed \$\endgroup\$ Oct 4, 2020 at 0:44
  • \$\begingroup\$ Suggested edit: "The chain ends when 14 days pass with no new answers being posted or when all unique number of bytes have been used" \$\endgroup\$
    – lyxal
    Oct 4, 2020 at 6:13
  • \$\begingroup\$ Also, there's no incentive to answer high no.bytes, as no one wants to have a high amount tacked onto their score. \$\endgroup\$
    – lyxal
    Oct 4, 2020 at 6:14
  • \$\begingroup\$ Further, I suggest you add a "languages cannot be newer than 4/10/2020" to avoid sandbox sniping \$\endgroup\$
    – lyxal
    Oct 4, 2020 at 6:16
  • \$\begingroup\$ Proposed scoring system: each answer is worth 257 - n points (n = number of allowed bytes), highest score wins. \$\endgroup\$
    – lyxal
    Oct 4, 2020 at 6:18
  • \$\begingroup\$ Does “each byte must be used a minimum of one times” mean you have to use every byte in the list? If so, I think framing this as a list of bytes you “can use” is misleading. Also, if you have to use 100 bytes, but your answer only needs 20, does anything stop you from just stuffing those remaining 80 bytes in a comment or an unused string variable? It might be more interesting if you force those bytes to have some function in the program, or get rid of this requirement and let people use a subset of the allowed bytes. \$\endgroup\$ Oct 4, 2020 at 16:14
  • \$\begingroup\$ @Lyxal I've added in that ending condition. I don't think any scoring system that involves the number of bytes available will provide an incentive to answer with both high and low bytes, so I've changed the score to be the number of answers posted. I dislike banning languages in general, so I've only banned languages specifically designed to answer this challenge \$\endgroup\$ Oct 4, 2020 at 20:37
  • \$\begingroup\$ @water_ghosts Yes, it does mean that, I've edited to reflect that. Nothing's stopping you from having portions of the code completely unexecuted, and requiring all code to be run is an unobservable requirement. Given how broad new answers can be in terms of language and output, I think it shouldn't be an issue with requiring all the bytes be present \$\endgroup\$ Oct 4, 2020 at 20:50
3
\$\begingroup\$

The Great Code Golf Heist

Alternatively, the most literal cops'n'robbers you'll ever see

Backstory

Sandbox Note: This part will be specific to each thread, so I've provided each version

Robbers

For the last few years, you and your team of robbers have been planning to rob the International Code Golf Museum (ICGM) of some of it's most prized possessions (rumour has it, they have a rare transcript of Dennis being outgolfed!). Tonight is the night that your plans will be put into action... tonight you will walk away with glorious riches and legendary artifiacts of code golf history.

That is, if you can actually manage to get in, loot the rooms and get back out without getting caught.

Cops

Tonight has been a quiet night at the Internation Code Golf Museum (ICGM)...too quiet for one's liking.

Of course, that's probably due to the fact that a bunch of robbers are rumoured to strike tonight and steal the most priceless artifacts from the ICGM's collections (we can't have them finding out the fact that Arnauld is a machine learning algorithm designed to answer challenges with Javascript, can we. [that's a joke we love you Arnauld!])

It's your job to stop the robbers and make sure that not a single thing leaves the museum.

The Museum

Sandbox Note: This part is common to both cops and robbers

Here is a map of the museum:

Museum Map

You may be wondering "hang on, what are the dimensions of that map?". Well the answer is simple: you don't need to know.

Movement around the ICGM is analogous to a Henry Stickmin game: in each room, you can either move to an adjacent room, or perform an action in that room.

Robbers start at the Getaway Car and can enter through either Hallway A or Hallway B. They then move through Hallway A.A then Hallway A.B or move through Hallway B.A and then Hallway B.B. Either way, they end up at the exhibition room. From the exhibition room, robbers can move to any of the treasure rooms which is where all the valuables are stored. After that, they make their way back to the getaway car to, well, escape and get away.

Cops are randomly allocated a position at the start of the heist, and can move wherever they need to.

Sandbox Note: There's going to be a system where each room takes a certain number of "strides" to get from one end to another. This way, robbers with stolen items are "slowed down" a little and the cops have a bit of a chance to catch up

Stealing Treasures

Sandbox Note: Robber specific

Once you reach a treasure room, you have the oppourtunity to get your hands on some of the finest works the ICGM has to offer. There will be a selection of items to choose from, each with different values. Sandbox Note: I might add a part where there is a limit on how much robbers can carry

However, items with more value impact how fast you can move through. Sandbox Note: Something relating to the stride system here.

But being the sneaky robbers you are, you have a few tricks up your sleeve(s). When moving through the ICGM, you can:

  • Activate a trap that will slow down the cops (avaliable only once Sandbox Note: Subject to change)
  • [Other things coming soon]

Once you get back to the getaway van, everything you have stolen is considered "safe" and counts towards your team's score. But once you're in the van, that's it... you can't go back for more.

Your team wins if you manage to steal items with a combined worth of insert value here

Protecting the ICGM

Sandbox Note: Cop specific

In order to protect the artifacts of the ICGM from being stolen, you have a few abilities you can use against the robbers. You can:

  • Apprehend a robber if they are in your proximity
  • [Other things coming soon]

For your team to win, the total value of items stolen must not exceed insert value here

The Catch

Sandbox Note: Common to both threads

The heist program will only be simulated once. That means that if your submission errors, you're out of the game for good. I mean, you don't see criminals replace the things they stole just to rerun the heist over and over to see how good they are ;P.

The heist will occur on insert date here. You can edit your submissions all you like until the time of running.

The Controller

Coming soon.

Feedback

  • Seeing as how this is a first draft, there are bound to be flaws with things like the movement mechanics and cop/robber interactions. I'm more looking for first impressions and overall flaws in the challenge.
\$\endgroup\$
1
  • \$\begingroup\$ I can't wait to see the valuables you place in the treasure room. \$\endgroup\$
    – RGS
    Oct 13, 2020 at 17:13
3
\$\begingroup\$

Secret ">" Stacking Challenge: cheating

Sequel to Secret ">" Stacking Challenge: grading. You can skip the whole Background section if you already read the first one.

Background

Tetris Grand Master 3 has a hidden grading system based on the shape of the stack at the end of the game, which is called Secret ">" Stacking Challenge. It consists of entirely filling the lowest rows except for the zigzag pattern which starts at the left bottom cell and spans the entire width:

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

The board is graded by how many lines follow this exact pattern from the bottom line. Note that the topmost hole in the pattern must be blocked by an extra piece of block. If you consider the #s and .s as the mandatory pattern (blanks can be anything), you can get the score of 19 only if the exact pattern above is matched from the bottom line. Analogously, if the board matches this pattern

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

but not

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

then the score is 4.

For this challenge, consider a board of arbitrary size (other than 20 cells high and 10 cells wide). We can grade the board for the same pattern: for example, if the board has width 4, this is the pattern for score 3:

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

and this is the pattern for score 10:

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

Challenge

Given the board width and the desired score for Secret ">" Stacking Challenge, pick a sequence of tetrominoes and generate the sequence of moves that will achieve the score. The Tetris moves can be represented in any ways that clearly specify where each tetromino is placed in which orientation, optionally along with the board state after each placement.

For the Tetris movement rules, we use simple permissive rule as in this challenge: you can place a tetromino anywhere (even in closed rooms), as long as it doesn't float in the air or overlap with existing pieces. Therefore, if you plan to use coordinates, you need to specify both x and y coordinates (the y coordinate should be counted from the bottom, as the board can grow upwards without bound -- or count from the top by also outputting the field height).

You can assume the width is at least 5 and the score is nonzero. You should theoretically support arbitrarily high score. The generated sequence doesn't need to be minimal.

Standard rules apply. The shortest code in bytes wins.

Output example

For board with 6 and score 2, one possible way is as follows: (As are the tetromino placed at each turn, # are existing pieces on the board, and . are empty cells)

......  ......  ......  ......  ......
A.....  #.....  #.....  .AA...  .##AA.
AA....  ##AA..  ####AA  #.AA..  #.##AA
.A....  .#AA..  .###AA  .#####  .#####

The above is a valid output format (you can choose any distinct chars/values in place of .A#). The following is also valid (although it is less obvious, it is indeed an unambiguous description of tetromino placements):

......  ......  ......  ......  ......
A.....  ......  ......  .AA...  ...AA.
AA....  ..AA..  ....AA  ..AA..  ....AA
.A....  ..AA..  ....AA  ......  ......

And this: (tetromino code, rotation, x and y coordinates from bottom left, 0 indexed)

S 1 0 0
O 0 2 0
O 0 4 0
Z 0 1 1
Z 0 3 1

And anything in between (e.g. showing tetrominos as a canonicalized matrix instead of a code). If in doubt, ask in comments.

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

Calculate the inverse of a matrix

\$\endgroup\$
3
  • \$\begingroup\$ n , nor n2, will never exceed the maximum value... and The elements of M−1 will never exceed... Even under those assumptions, intermediate computations can exceed the maximum. So maybe it's better to say something more general, maybe along the lines of this \$\endgroup\$
    – Luis Mendo
    Oct 2, 2020 at 23:18
  • \$\begingroup\$ Also, matrix inversion notoriously causes floating-point error build-up when naïve algorithms (i.e. algorithms not specifically designed to avoid error accumulation) are used. This results in relatively large errors in the output. And those algorithms are likely to be the ones used in a golfing challenge (if the language doesn't have a builtin). So maybe you should add a note saying that it is sufficient if the algorithm works when arbitrary precision is assumed \$\endgroup\$
    – Luis Mendo
    Oct 2, 2020 at 23:18
  • 2
    \$\begingroup\$ @LuisMendo I've edited in "It is acceptable if your program fails for some inputs due to floating point issues, so long as the underlying algorithm or method works for arbitrary matrices." which I think should cover both of those points \$\endgroup\$ Oct 4, 2020 at 20:58
3
\$\begingroup\$

Can I print my picture on {A,B,C}{0-10} paper?

The task is to find the smallest paper size on which it is possible to print a picture of the dimensions given in milimetres. The image will be printed without margins.

Input:

Two numbers (bigger than zero) and a letter a, b, or c, for example:

290
200
A

Output:

Paper size, for example:

A4

Another examples:

218,297,a      A3
1,1,c          C10
9999,9999,c    ??? (error)
74,52,A        A8
31,44,B        B10
26,1100,A       A0

  • Upper- and lowercase variants of letters "A", "B" and "C" are allowed on input and on output.
  • The image can be printed vertically or horizontally.
  • The values can be passed as a parameter or entered by the user.
  • Width and height of picture will be always > 0, and letters will be always 'a', 'b', or 'c'. You don't need to validate them.
  • You need to handle paper sizes A0 - A10, B0 - B10 and C0 - C10. If the image is too large, you can throw an exception, print an error or whatever you want, as long as it is clearly different from valid result and the application will not hung up.

Paper sizes, please ignore inch values (source: Wikipedia) : Paper sizes


This is - fewest bytes wins.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Perhaps you should inline what sizes the An, Bn and Cn papers are. Also, some more test cases (~5-10) would be nice for the final version. \$\endgroup\$
    – Sisyphus
    Oct 22, 2020 at 0:03
3
\$\begingroup\$

Brainfuck arbitrary precision multiplication

Goal

The goal is to multiply two numbers in the shortest amount of cycle.

The Input

The input is two numbers written decimally separated by a space. The number is NOT restricted by the size of the integer inside of the cells. The program must accept arbitrary sized integer

The Output

The output is a single integer written decimally.

Brainfuck variants used

Since the flavors of the Brainfuck is important in this challenge, you are required to use this flavor

Memory

The memory is an array of cells, unbounded to the left and the right, with 8-bit integer as the contents.

Input/Output

The input and the output uses ASCII symbol mapping. EOF is interpreted as \0 char.

Looping

The [ means that "check the current cell. If it's zero, jump to the instruction after the matching ]" The ] means that "jump to the matching [." no cycle is taken in this instruction.

Cycle

Every instruction takes a single cycle every time it's executed except for ]. ] is a free instruction.

Reference implementation

For the reference implementation, use copy.sh with this option:

  1. Cell size (Bits): 8
  2. Dynamic (infinite) Memory: yes
  3. End of input: char: \0
  4. Count instructions

Scoring

The winner is the program that is: (later number is for tiebreaker)

  1. The program with lowest computational complexity (counted by using cycle metric as explained above, and in x where x is the length of the largest input in base 10) is the winner.
  2. The program with lowest space complexity (counted by finding the rightmost cell reached by program)
  3. The program that takes the least cycle to execute 1234567890*987654321
  4. The program that takes the least memory to execute 1234567890*987654321
  5. The shortest code

Computational complexity is determined in terms of the number of digits each arguments have.

\$\endgroup\$
8
  • \$\begingroup\$ fastest-code is the winning criterion tag, so you don't need code-challenge. To lower the obstacle before starting to work on the challenge, I suggest to use the copy.sh online interpreter as the standard. (I think it satisfies the cycle count rule?) \$\endgroup\$
    – Bubbler
    Sep 3, 2020 at 7:02
  • \$\begingroup\$ @Bubbler Actually, I designed my challenge with copy.sh as the reference. The only difference is that the memory tape is not unbounded to the left. \$\endgroup\$
    – Xwtek
    Sep 3, 2020 at 7:25
  • \$\begingroup\$ You can set "memory overflow behavior" to "abort" for that. \$\endgroup\$
    – Bubbler
    Sep 3, 2020 at 7:39
  • \$\begingroup\$ @Bubbler It's not possible to have both infinite memory and abort as memory overflow behavior. I changed the challenge so that the memory is also unbounded to the left. \$\endgroup\$
    – Xwtek
    Sep 3, 2020 at 7:42
  • \$\begingroup\$ Can we make assumptions such as 'the number of digits in the numbers is less than X' or 'the number of digits in the number of digits in the numbers is less than X'? \$\endgroup\$ Sep 5, 2020 at 14:32
  • \$\begingroup\$ @thedefault. No. The program must handle arbitrary sized number. \$\endgroup\$
    – Xwtek
    Sep 5, 2020 at 15:57
  • \$\begingroup\$ @Xwtek So it would be impossible to answer it in a flavor with 30000 cells of one byte each? I think the limit on the size of each number should be half of the number of cells (and thus infinite for flavors with infinite cells) \$\endgroup\$ Sep 9, 2020 at 23:30
  • \$\begingroup\$ @RedwolfPrograms Yes, it's impossible. Maybe I'll make a challenge to minimize memory use, but for now, you have to use infinite flavors. "I think the limit on the size of each number should be half of the number of cells" Not necessarily, I bet you need much more memory than that. \$\endgroup\$
    – Xwtek
    Sep 11, 2020 at 2:20
3
\$\begingroup\$

Posted.

\$\endgroup\$
22
  • \$\begingroup\$ "Given a list of strings of two-letter abbreviations (see below) for US states, determine whether they are connected." So can we expect a python list? Or should we expect a comma separated list? I think you should clarify the input. Giving the input as a python list gives python (and any other languages that have the same syntax) an advantage over, for example bash. \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 14:27
  • \$\begingroup\$ What should the output be? Is it <input> is not connected. or <input> is connected.? Or can it just be true/false? \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 14:48
  • \$\begingroup\$ @nthnchu I think they mean a list of strings, whatever that is in your language. I agree with using truthy/falsy for connected/not connected. \$\endgroup\$
    – Razetime
    Nov 8, 2020 at 15:13
  • 2
    \$\begingroup\$ @Keba Are we required to compress the list, or take it as an input? If we need to compress it, add kolmogorov-complexity. \$\endgroup\$
    – Razetime
    Nov 8, 2020 at 15:14
  • \$\begingroup\$ Thanks for your replies. My idea was that the exact input/output format should not matter to much. Accepting a list of strings is fine but I guess just a long string such as "AK WA OR" or even "AKWAOR" is also fine – whatever works well in your language. And output should be truthy/falsy, yes. Thought that was covered by standard I/O rules but tried to clarify it. \$\endgroup\$
    – Keba
    Nov 8, 2020 at 17:20
  • 1
    \$\begingroup\$ @Razetime: Sorry, I am not sure whether I can follow. The code should output a truthy/falsey value for a given list of strings. \$\endgroup\$
    – Keba
    Nov 8, 2020 at 17:22
  • 1
    \$\begingroup\$ @Keba They are asking whether the list of states is provided as input or if we must keep it in our code. If we should keep it in the code, you should add the kolmogorov-complexity tag. \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 22:20
  • \$\begingroup\$ @nthnchu The input should consist of a list of strings such as ["AK", "WA"] (or something equivalent) and nothing more. The list of neighboring states, however, is not included in the input. Still, the output is not constant and hence that tag does not apply? \$\endgroup\$
    – Keba
    Nov 8, 2020 at 22:49
  • 1
    \$\begingroup\$ @Keba It still has the large constant string of the neighboring states. Look at wikipedia and kolmogorov-complexity's info page for more info. \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 22:57
  • 1
    \$\begingroup\$ Even though the output isn't constant is still relates to it. \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 23:04
  • 1
    \$\begingroup\$ From that page: ”a post should be tagged kolmogorov-complexity iff the bulk of the challenge is to produce a string or a subset of a dataset which is given in the question.“ I do not thing that the bulk of the challenge is to produce that string. First, that string does not need to appear anywhere and second, the main problem should be to decide whether the corresponding graph is connected or not. \$\endgroup\$
    – Keba
    Nov 8, 2020 at 23:17
  • \$\begingroup\$ And this question looks very different from the ones posted with that tag. \$\endgroup\$
    – Keba
    Nov 8, 2020 at 23:18
  • \$\begingroup\$ Yeah you're kind of right. Just wondering, is ["AK"] considered connected? \$\endgroup\$
    – nthnchu
    Nov 8, 2020 at 23:41
  • \$\begingroup\$ It is, I add it to the list of test cases. \$\endgroup\$
    – Keba
    Nov 8, 2020 at 23:50
  • 1
    \$\begingroup\$ My case for the tag is that compressing the string is one of the only ways to win; I just completed the challenge in less bytes than the string in python because I compressed it. \$\endgroup\$
    – nthnchu
    Nov 9, 2020 at 0:01
3
\$\begingroup\$

Jelly's Untruth

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

Generalised Taxicab Numbers

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

posted

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

Is my triangle on the lattice?

Posted on the main site.

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

Is it a Lobster Number?

Posted

\$\endgroup\$
6
  • \$\begingroup\$ I like the idea, but the fact that prime numbers don’t count seems a bit arbitrary. \$\endgroup\$
    – user
    Jan 23, 2021 at 21:11
  • 2
    \$\begingroup\$ It definitely is a bit arbitrary, but I felt that it made sense as an edge case, since while it is a prime factor, it is already the number itself, and there are no other factors. The related (but not identical) OEIS sequence also seems to have made this distinction, so it seemed reasonable. It also has the simple explanation that lobsters are not needed to get the result for the prime numbers, and shouldn't be overly difficult to work around in golfing, as all you need is a single comparison (is there only one factor, or is the first factor equal to the number). \$\endgroup\$
    – IronEagle
    Jan 23, 2021 at 21:35
  • \$\begingroup\$ Yeah, that makes sense, and it's not a deal-breaker for me, it would just make writing an answer slightly more annoying :) \$\endgroup\$
    – user
    Jan 23, 2021 at 21:36
  • \$\begingroup\$ @user - Posted since there seems to be no general problems with the question. \$\endgroup\$
    – IronEagle
    Jan 24, 2021 at 15:04
  • \$\begingroup\$ Well, I don't see any problems with it myself, but it would have been good to let it sit a few more days to get more feedback \$\endgroup\$
    – user
    Jan 24, 2021 at 15:07
  • 1
    \$\begingroup\$ @user - I'll keep that in mind, this is my first question here, this site is quite a bit different from the other StackExchange sites. \$\endgroup\$
    – IronEagle
    Jan 24, 2021 at 15:13
3
\$\begingroup\$

BF memory layout optimizer (posted).

See the notes in the revision history.

[please review other sandbox posts]

\$\endgroup\$
3
  • 1
    \$\begingroup\$ (upvote this comment if you want a variant with [fastest-code] instead.) \$\endgroup\$
    – DELETE_ME
    Jan 31, 2021 at 2:11
  • 2
    \$\begingroup\$ (upvote this comment if you want both a [code-golf] version and a [fastest-code] version.) \$\endgroup\$
    – DELETE_ME
    Jan 31, 2021 at 2:11
  • 1
    \$\begingroup\$ (upvote this comment if you want only a [code-golf] version.) \$\endgroup\$
    – DELETE_ME
    Jan 31, 2021 at 2:11
3
\$\begingroup\$

Note:

  • as you can probably tell, this is a simpler variation; however the poster of the other sandbox post has not been visiting the site for a while.
  • because of the current situation, I recently (after the 2 upvotes is made) changed the winning criteria. Is there any problem with the description?
  • What info should be included in the header?...

Efficient table-lookup computation

Posted: Efficient table-lookup computation

\$\endgroup\$
20
  • \$\begingroup\$ (ah, right. The sandbox is still as inactive as usual.) \$\endgroup\$
    – DELETE_ME
    Jan 30, 2021 at 17:16
  • \$\begingroup\$ Or it could be that the challenge is simply a little hard to read.) \$\endgroup\$
    – DELETE_ME
    Jan 31, 2021 at 14:45
  • \$\begingroup\$ If two answers have the same A+B, is the one with lower A or lower B considered better, or is there no tie-breaker? \$\endgroup\$
    – Dingus
    Feb 2, 2021 at 8:43
  • \$\begingroup\$ @Dingus No, see the meta post about challenge having multiple winning conditions. codegolf.meta.stackexchange.com/questions/19041/… \$\endgroup\$
    – DELETE_ME
    Feb 2, 2021 at 10:19
  • \$\begingroup\$ There's no consensus on that meta question. I think you should state that if two answers have the same A+B then they score the same. \$\endgroup\$
    – Dingus
    Feb 2, 2021 at 10:37
  • \$\begingroup\$ @Dingus +1 is not a consensus? \$\endgroup\$
    – DELETE_ME
    Feb 2, 2021 at 10:42
  • 1
    \$\begingroup\$ A post is considered as a consensus only if it's at >= +10 and upvotes >= 2*downvotes. So +5/-4 (at the time of writing) is closer to a controversy than a consensus. I guess many people have just feelings without enough justification about whether it's fine or not. I personally view it as a good challenge, so I upvoted it. \$\endgroup\$
    – Bubbler
    Feb 8, 2021 at 23:20
  • \$\begingroup\$ A minor nitpick: In your Python code, adding string to a number is invalid. I guess you meant to take the inputs as strings, e.g. m1 = "0" etc. \$\endgroup\$
    – Bubbler
    Feb 8, 2021 at 23:21
  • \$\begingroup\$ For the lack of sandbox feedback, I usually leave my challenges for at least a week, regularly asking for feedback in the chat (at least 2 or 3 times before moving to main). \$\endgroup\$
    – Bubbler
    Feb 8, 2021 at 23:24
  • \$\begingroup\$ @Bubbler Fixed. \$\endgroup\$
    – DELETE_ME
    Feb 9, 2021 at 1:41
  • \$\begingroup\$ to me it looks like the given method to generate a single score from A and B only adds confusion, especially the "combined score" part... what's the advantage compared to a simpler formula like A^2+B^2? (I would be in favour of just using A and B and letting all pareto-optimal solutions win, but I understand that at the moment there's not enough consensus for this) \$\endgroup\$
    – Leo
    Feb 12, 2021 at 8:57
  • \$\begingroup\$ @Leo Because it doesn't encourage these solutions, obviously? -- (I think that the solution with minimum A is pretty interesting, but I'd like to see a solution that generates reasonably-good parametrized solutions too.) \$\endgroup\$
    – DELETE_ME
    Feb 12, 2021 at 9:53
  • \$\begingroup\$ @Leo as explained in the linked meta post -- (did I explain it clearly enough?) that method would allow essentially the same "every solutions win" situation by letting every such "winning" solution improves the "combined" score. (and is the only one that I can come up with with that condition) \$\endgroup\$
    – DELETE_ME
    Feb 12, 2021 at 9:54
  • \$\begingroup\$ The problem with the combined score is that you have two scores again, the "normal" one and the "combined" one... Does only one or the other count for "victory"? \$\endgroup\$
    – Leo
    Feb 12, 2021 at 10:29
  • \$\begingroup\$ @Leo Obviously the combined one. Note that the criteria is chosen so that the combined score is always better than or equal to the normal score, and the combined score is always better than the previous combined score. \$\endgroup\$
    – DELETE_ME
    Feb 12, 2021 at 10:32
3
\$\begingroup\$

Generalise perfect numbers

\$\endgroup\$
3
  • \$\begingroup\$ Better having a statement "in this challenge \$\sigma^n(k) \$ denotes...". It can be interpreted as \$(\sigma(k))^n \$ too. \$\endgroup\$
    – DELETE_ME
    Feb 24, 2021 at 4:15
  • \$\begingroup\$ Can answers assume that "the sequence is infinite"? \$\endgroup\$
    – DELETE_ME
    Feb 24, 2021 at 4:16
  • \$\begingroup\$ @user202729 Addressed both questions \$\endgroup\$ Feb 28, 2021 at 1:18
3
\$\begingroup\$

Byte-sized Huffman Coding (WIP)

Huffman codings are a method to compress data with certain frequency properties, usually text. Normally, these operate on bits rather than bytes, but this challenge will instead operate on whole bytes instead. Since you wouldn't get any benefit otherwise, you can represent multiple consecutive characters with a sequence of one or more bytes, for instance '. ' (a period followed by a space) could be represented by byte 1, 'The' could be represented with byte 2, and 'Ishmael' could be represented by a 255 then a 7 (among many other sequence codings).

Challenge

Create a program that compresses a plain-text version of a work of literature by returning a byte-wise Huffman coding table and a sequence of bytes that represents the text with that table.

Rules and Assumptions

  • You may assume that the text is written in English and uses only printable ASCII characters plus space, newline, and tab.
  • It must be a proper Huffman coding; no mapping may be the prefix of another.
  • Not all Huffman sequences need to be mapped to a particular character sequence; you could, for instance, not have 7 mapped to anything or not have 255, 39 mapped to something, but have every other 1 and 2 byte sequence mapped to something.
  • The returned coding table must be able to encode every possible sequence of valid characters (as per the first assumption above). The simplest way to do this is to make sure that every individual character is mapped to a Huffman byte sequence.
  • It can be possible to encode a body of text multiple ways using the returned encoding table. If both ca and at are mapped to byte sequences, cat could be encoded two ways. This is totally fine.
  • Case must be preserved.
  • Runs do not need to be deterministic, i.e. two runs of the same program with the same input could produce different Huffman tables and compressed output.
  • Your program must return a result within a reasonable amount of time to be considered a valid solution. (If you want a hard limit, I'll say 5 minutes on a 2GHz Intel dual-core i5 with 16 GB RAM running Windows 10)

Scoring

Your results will be run against a corpus of (TBD) 12 publicly available literary (and non-fiction) works. For each work of literature, your score will be the size, in bytes, of the compressed text, plus the total length of all text strings mapped to a byte sequence in the Huffman-coding table. Your overall score is the total score across all 12 works.

Lowest score wins.

Literature list

  • The King James Bible
  • Hamlet by William Shakespeare
  • Dracula by Bram Stoker
  • Frankenstein by Mary Shelley
  • On the Origin of Species by Charles Darwin
  • Moby-Dick by Herman Melville
  • Little Women by Louisa May Alcott
  • Tom Sawyer by Mark Twain
  • Pride and Prejudice by Jane Austen
  • The Hound of the Baskervilles by Arthur Conan Doyle
  • < Something that entered the public domain in 2019 because it was published in 1923 >
  • < Something written in the last 20 years willingly released into the public domain or with a Creative Commons license that allows derivative works >

Sandbox

At least one of the last two literary works should preferably be written by a female and/or non-white author to hopefully make writing styles diverse enough to make hard-coded Huffman tables ineffective. Each work should be comparable in length to the other works.

Links to these books (in plain text) would be appreciated. Substitution suggestions are welcome.

\$\endgroup\$
8
  • \$\begingroup\$ If you want to vary writing styles, is there a non-fiction work that only contains the allowed characters? \$\endgroup\$
    – trichoplax
    Sep 24, 2019 at 23:21
  • \$\begingroup\$ @trichoplax The most notable non-fiction book I can think of for that would be "On the Origin of Species" by Charles Darwin. I've also thought about throwing in the King James bible. Maybe I could bump up the total to 12 works. I also probably will drop War and Peace because the plain text version I found was machine converted and has issues. \$\endgroup\$
    – Beefster
    Sep 25, 2019 at 15:21
  • \$\begingroup\$ Regarding plain text books, have you checked Project Gutenberg? They have plaintext versions of many of their books. \$\endgroup\$ Sep 25, 2019 at 18:35
  • \$\begingroup\$ I have no idea how much sample text is a good amount for this challenge (number of books, length of books) but it's probably worth doing some kind of rough check that there is enough text to give variation between answers (no optimal solution) while still being little enough text that running in a reasonable time is realistic (doesn't require weeks of work before an answer is efficient enough to meet the time restriction). Maybe others can suggest good ways of approximating this? \$\endgroup\$
    – trichoplax
    Sep 25, 2019 at 20:16
  • \$\begingroup\$ @trichoplax so basically you suggest sampling out, say, a few chapters instead of the whole book and then reducing the required runtime? I'm open to that, especially since the word count difference between Hamlet and the Bible is so big. The interesting thing about the Bible is that it has a ton of different authors, so it would almost be better to have the first chapter of each book instead of inserting, say, the entirety of Genesis. \$\endgroup\$
    – Beefster
    Sep 26, 2019 at 4:41
  • \$\begingroup\$ I couldn't guess at this point whether more text or less text would be better, and I don't have a way of estimating, just wondering if anyone else does. \$\endgroup\$
    – trichoplax
    Sep 26, 2019 at 7:32
  • \$\begingroup\$ I see no problem with 5 minutes as a rough time limit. I'd lean towards a time limit that allows someone to write a quick answer and then improve on it gradually, to encourage more participants. How long that needs to be for the text you settle on I don't know. As long as you're confident an optimal solution can't be found, you could just time a naive approach and then choose a time that doesn't exclude that. Then you can get lots of early answers to get the competition going, but still have open ended improvement over the long term \$\endgroup\$
    – trichoplax
    Sep 26, 2019 at 7:38
  • \$\begingroup\$ Not to say that this isn't an interesting challenge as it is but I do wonder if it wouldn't be more interesting without requiring that we use Huffman Encoding? \$\endgroup\$
    – Shaggy
    Sep 27, 2019 at 22:21
1
16 17
18
19 20
132

You must log in to answer this question.

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