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

4648 Answers 4648

1
18 19
20
21 22
155
3
\$\begingroup\$

Battleship KotH

This is a pretty rough idea to start but I figured I would drop it in the sandbox so that people can start to think about it and I will remember to do it.

The idea here is a that combines the game, battleship with .

The rough idea is that two enemies would face off, each turn irradiating a location in their opponents source code. Then the opponents source code would be recompiled and then try and attack back.

Some additional thoughts I've had:

  • We will likely want to limit the size of the board to a specific rectangular size

  • I would like there to be a feedback from shooting your opponent (in the game battleship this is hit/miss) so that you are doing more than just firing randomly. Perhaps programs might irradiate a single bit (flipping its value) and get back its value before it was irradiated.

Language choice is a bit tough since I would like something multipurpose and flexible but I don't want to have to deal with the security issues that are involved in compiling and running a fully featured programming language.

\$\endgroup\$
2
  • \$\begingroup\$ radiation-hardening tends to work best with deletion. This is going to need a maximum byte count to be fair, otherwise the best strategy is excessive amounts of whitespace and comments. Love the idea though. \$\endgroup\$
    – Beefster
    Sep 17, 2019 at 14:22
  • \$\begingroup\$ You don't actually have to limit yourself to a specific language on this one. It wouldn't be that hard to use a shell script to run whatever languages are available. One question though: is each program able to read the source code of the other or is each attack supposed to be blind? If you're worried about security, you could run the controller in a docker container or VM. \$\endgroup\$
    – Beefster
    Sep 17, 2019 at 14:26
3
\$\begingroup\$

Injection from two strings to one string

\$\endgroup\$
5
  • \$\begingroup\$ Do you think that a reasonably number of languages won't implement the following: convert the strings into numbers (e.g. treat each character as a base 128 digit) then give a resulting string of those two numbers joined by some other character? I haven't spent too long thinking about it but that seems very short in most languages. I suppose there are other variants though where you map characters to some subset and then join them. \$\endgroup\$ Sep 24, 2019 at 20:42
  • 2
    \$\begingroup\$ @FryAmTheEggman I imagine the solution used is going to depend on the language: what builtins it has, if it's more high-level or low-level, etc. But there may well end up being a prevalent algorithm. \$\endgroup\$ Sep 24, 2019 at 20:57
  • \$\begingroup\$ Why strings? Lists of integers, (even restricted to a range) work as well but don't have the complexities that strings do when it comes to printables etc. I feel like the simpler challenge is going to be the better one. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 26, 2019 at 3:30
  • 1
    \$\begingroup\$ @FryAmTheEggman Don't worry, I've thought of a totally different approach that I think would be shorter for many languages. \$\endgroup\$
    – xnor
    Sep 26, 2019 at 4:46
  • 2
    \$\begingroup\$ @SriotchilismO'Zaic Restricting the character set seems to me like a reasonably simple detail, while making it about strings encourages creativity with string operations, converting to string representations, etc. Also, I personally think string input/output is much more appealing to look at and easier to consume than a list of numbers. \$\endgroup\$ Sep 26, 2019 at 14:38
3
\$\begingroup\$

Code Golf Measurer © 2019

Hexdumps used with xxd look something like this:

00000000: 666f 6f20 6261 7220 7370 616d 2065 6767  foo bar spam egg
00000010: 730a                                     s.

Your task is to convert a hexdump in this form in to the number of bytes used.

Rules:

  • Usual loopholes forbidden.
  • This is , so shortest valid answer in bytes wins.
  • You may or may not include the newline at the end of text (0a). This means that if the hexdump ends in a newline (0a), that input may have it's output reduced by one.
  • An empty input must output 0.

Test cases:

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 2120 4865  Hello, world! He
00000010: 6c6c 6f2c 2077 6f72 6c64 210a            llo, world!.

returns 27 or 26

00000000: 0a                                       .

returns 1 or 0

00000000: 6368 616c 6c65 6e67 650a                 challenge.

returns 10 or 9

00000000: 4865 6c6c 6f2c 2077 6f72 6c64 21         Hello, world!

returns 13


returns 0

Sandbox:

  • Is this clear?
  • Is this a duplicate?
  • Other tags?
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Does the extra rule mean that the input can have an optional trailing newline, or that the results in all of your test cases could be reduced by 1? If you mean the former I recommend adding a test case that doesn't end with a newline. If you mean the latter then I recommend explicitly saying the file will end with a newline character. Also I suppose this is a string challenge. Thanks again for using the sandbox :) \$\endgroup\$ Oct 3, 2019 at 20:55
  • \$\begingroup\$ @FryAmTheEggman It means that all test cases could be reduced by one. This was intended as a code golf byte counter, and the newline most certainly isn't usually included. I'll clarify this and add another test case to highlight it. \$\endgroup\$
    – gadzooks02
    Oct 4, 2019 at 15:17
  • \$\begingroup\$ So: discard all the input except the last line, and parse hex? Or just output the last line and claim that your output is in hex? IMO it would be a more interesting problem with xxd input, where the last line is not present. \$\endgroup\$ Oct 5, 2019 at 9:00
  • \$\begingroup\$ @PeterTaylor If I were to switch to xxd, would that be a valid edit, or would that be too big a change such that I would have to post another challenge? \$\endgroup\$
    – gadzooks02
    Oct 5, 2019 at 9:45
  • \$\begingroup\$ I'm sure far more significant edits have been made to sandboxed challenges in the past. \$\endgroup\$ Oct 5, 2019 at 13:10
  • \$\begingroup\$ @PeterTaylor In that case, edited. \$\endgroup\$
    – gadzooks02
    Oct 5, 2019 at 14:52
3
\$\begingroup\$

Java vs C++

Now posted at Time to settle this: Java vs C++

\$\endgroup\$
9
  • \$\begingroup\$ How vital is the validation to the challenge? \$\endgroup\$ Aug 27, 2019 at 21:01
  • \$\begingroup\$ @UnrelatedString I think it's fairly integral if the story is considered. Gotta inform the user that they're feeding you crap. Also it should add an extra element of challenge. \$\endgroup\$ Aug 27, 2019 at 21:07
  • 3
    \$\begingroup\$ @MrRedstoner Validation is generally considered tedious by the users of this site, rather than challenging. I'd recommend reconsidering - clearly the validation code could make use of the submissions as a subroutine. There are also a couple near dupes 1 2 but I haven't found a precise dupe. That said, thanks for using the sandbox! \$\endgroup\$ Aug 28, 2019 at 0:36
  • 1
    \$\begingroup\$ getHTTP would result in... get_h_t_t_p? get_http? Error? Some other thing? \$\endgroup\$
    – Chas Brown
    Aug 28, 2019 at 1:42
  • \$\begingroup\$ @ChasBrown should be get_h_t_t_p, I shall add that. @FryAmTheEggman While I considered it part of the story, if those are the standards I figure I'll remove it and say the validation was done by a previous part of code. \$\endgroup\$ Aug 28, 2019 at 5:24
  • \$\begingroup\$ "If it is neither, output/return a falsey value." I would change this to something like "If it is neither, any unspecified behavior is fine (return a falsey value; give an error; try to convert it somehow anyway; etc.)." As mentioned by @FryAmTheEggman, validation is usually considered a distraction of the actual challenge (and can sometimes even double the code of the program/function for those answering), so most challenges assume the given input will always be valid. Apart from that the entire challenge looks fine, so +1 from me. Thanks for using the Sandbox! :) \$\endgroup\$ Aug 28, 2019 at 9:32
  • \$\begingroup\$ @KevinCruijssen Dang it missed that during the edit. Thanks for telling me! \$\endgroup\$ Aug 28, 2019 at 10:42
  • \$\begingroup\$ What should be returned from an input of a__b (two underscores)? \$\endgroup\$
    – Value Ink
    Aug 29, 2019 at 1:03
  • 1
    \$\begingroup\$ @ValueInk That would be invalid input. 'You may assume all input to be valid'. Therefore I refer you to the ANSI C standard for undefined behaviour. \$\endgroup\$ Aug 29, 2019 at 6:00
3
\$\begingroup\$

Can Jimmy escape the ghosts?

Posted: Can Jimmy escape the ghosts?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ S'all good, no problem \$\endgroup\$
    – Veskah
    Oct 17, 2019 at 14:05
3
\$\begingroup\$

Universal Self-correcting Program

The idea here is to make a program that can tolerate errors in its own code, while still functioning correctly.

Since "error" is too broad, we will define it by a single bit flip. Of course, more tolerant versions, that could accept swapping any character with any other character would still be valid.

This program is universal in the sense that you can write any other self-correcting program (with the same tolerance) -- more on that later.

Importantly:

1) This program takes as input a triple-redundancy string of characters, and outputs a corrected string.

2) This program executes correctly with any bit flip in its own code.

(1) Triple redundancy codes

A triple redundancy code consists of simply repeating each bit, character or byte 3 times. In this case we use characters.

Correction is done by taking the majority of the characters, so (A,A,B) is corrected to A, (A,B,B) is corrected to B and so on.

AAA => A
AAB => A
HHHEEELLXLLLXOO => HELLO

This is a very crude an inefficient code for correcting single bit errors, but it is the least complex, which is why I think may be the best choice here. Hamming codes are better but a little more complex.

(2) Error tolerance

Our program will be defined as error tolerant if it performs the desired decoding function for any single bit flip in its own code. It may take longer for some inputs or when some flips occur, but it should always terminate.

Putting it together

The error-tolerant program can receive as input a (possibly faulty) program, and outputs a error-free program. Therefore, if a single-bit error occurs anywhere in the system comprised of (decoder,input program), a corrected program will still be output.

Observation

I don't actually know if this is possible, quite possibly it won't be achievable in every language. If it is too hard, we may relax the tolerable errors.

Scoring

The score will reflect the reliability of your program to errors. Tolerance is simply the number of bit flips you code accepts anywhere. It must be at least 1 (accept 1 bit flip anywhere). Size is the length of your program in bytes.

The score is Score = Size / 2^Tolerance

Lowest score wins.

Note: Several other challenges are possibly solved by solving this one (which would make sense given its universality!) by hardcoding the input.

Detect if your program has been mutated

Write a program that always outputs “2012” - even if it's modified!

This solves the "Who Watches the Watchmen?" problem involved in error correcting programs, like in this challenge:

Meta radiation hardener

since the decoding program itself tolerates errors (what good would be an error correcting program that is itself in error? :p).

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Check the radiation-hardening tag for duplicates and rules clarifications, too. \$\endgroup\$ Mar 7, 2018 at 19:17
  • \$\begingroup\$ @AdmBorkBork Thanks, I wasn't aware of that. It appears no one has proposed a Universal radiation hardener yet (this is universal only in the sense of bit flip errors; those are actually a good model for radiation though!). \$\endgroup\$
    – Real
    Mar 7, 2018 at 19:30
  • 1
    \$\begingroup\$ Again Lenguage win lol \$\endgroup\$
    – l4m2
    Jan 8, 2019 at 14:53
  • \$\begingroup\$ Even though your scoring involves code length you should use code-challenge instead of code-golf for challenges that are not solely scored by code length. \$\endgroup\$
    – Laikoni
    Jan 10, 2019 at 20:14
3
\$\begingroup\$

Golfing with 2s

It is well-known that all positive integers can be represented via a sum of powers of 2. For example, 13=2^3+2^2+2^0. We can rewrite the 3 and 0, to get 13=2^(2+2/2)+2^2+2^(2-2). A shorter representation might be 13=2^2^2-2-2/2, or a more repetitive one 13=2+2+2+2+2+2+2/2

Challenge

Your task is, given a nonnegative integer as input, output/return a string containing only 2s and elementary operations, which when evaluated will yield that integer. These operations are +, -, *, /, ^, and appropriate parentheses. Use of multiple consecutive 2s (22, 222, etc) is not allowed.

However, the string should tend to be one of the shorter representations of the integer in question. So for the above example with 13, 2^2^2-2-2/2 and 2^2^2-2/2-2 are the shortest representations.

The input can be in any convenient format, but the output must be in the above format, either to a file or STDIO.

Scoring

Short code and efficient representation are both prioritized, so the score is the length in bytes plus the average length of the returned string for 9, 57, 554, 1894, 25993, 113193, 2998225, and 52748566.

Rules

Standard loopholes not allowed

Standard input/output forms apply

Some degree of brute forcing is allowed, but the program must be able to handle each of the test cases in under a minute each.

Example outputs

0            2-2
1            2/2
2            2
3            2+2/2
4            2^2
5            2^2+2/2
6            2^2+2
7            2^2+2+2/2
8            2*2*2
9            2*2*2+2/2
10           2*2*2+2
57           2^(2^2+2)-2^2-2-2/2
554          2*2^(2*2*2)+2*2^2^2+2*2*2+2
1894         2*2^(2*2*2+2)-(2^2^2-2)*(2*2*2+2+2/2)
25993        (2*2^(2*2*2+2)-2*2^(2*2*2)-2^2-2-2/2)*(2^2^2+2/2)
113193       2*2^2^2^2-(2^(2*2*2+2)-2^(2^2+2)-2^2^2-2-2/2)*(2^2^2+2+2/2)
2998225      (2*2^2^2^2-(2^(2*2*2+2)-2*2*2-2-2/2)*(2*2*2+2+2/2))*(2^2^2+2*2*2+2/2)
52748566     (2*2^(2^2^2+2^2)-2^2^2^2-2*2^(2*2*2+2)-2*2^(2*2*2)-2^(2*2*2)-2*2*2-2/2)*(2^2^2-2-2/2)*2
\$\endgroup\$
10
  • \$\begingroup\$ It doesn't have to be optimal. It should tend to be optimal but you can trade it out for a much shorter program if it helps. \$\endgroup\$ Dec 8, 2019 at 8:10
  • \$\begingroup\$ It might be a good idea to clarify length - do you mean the actual string length or the number of operations and 2s used? \$\endgroup\$ Dec 8, 2019 at 20:19
  • \$\begingroup\$ Added clarification for both. To Fry, I mean the string length, but I'm not entirely sure what the difference is. \$\endgroup\$ Dec 9, 2019 at 0:39
  • \$\begingroup\$ Can we use the numbers 22, 222, etc. in the output? \$\endgroup\$
    – 79037662
    Dec 10, 2019 at 16:33
  • \$\begingroup\$ No. Will add clarification for that as well. \$\endgroup\$ Dec 12, 2019 at 0:33
  • 1
    \$\begingroup\$ Can we submit a function that takes a value and returns a string? Typically you should try and avoid restricting input and output, and just rely on the community standards \$\endgroup\$
    – Jo King Mod
    Dec 13, 2019 at 3:26
  • 1
    \$\begingroup\$ in reasonable time I know this is hard to specify, but as it stands it is too broad: what is meant by "reasonable time"? Some previous challenges say things like "it should run within a minute on a modern computer for inputs less than..." \$\endgroup\$
    – Luis Mendo
    Dec 16, 2019 at 9:47
  • \$\begingroup\$ Yeah, I'm not really sure how to specify it further. I only really added it because when I showed this challenge to my friend, they wrote a brute-force that goes through every string with those 8 characters and finds the shortest one, and it would take a few minutes for inputs > 30. Does being able to run each of the test cases in under a minute sound good? \$\endgroup\$ Dec 16, 2019 at 19:15
  • \$\begingroup\$ That's the usual tactic, though you should probably specify what computer it is run on, since some will be faster than others. A possible idea could be the answerer has to run the biggest test case to completion, which should eliminate the worst of the brute force scripts \$\endgroup\$
    – Jo King Mod
    Dec 18, 2019 at 7:33
  • \$\begingroup\$ Giving the integers you'll be testing with might allow people to optimise those specific inputs sneakily - maybe ask for a TryItOnline link and then give every answer a score yourself? Just a suggestion. \$\endgroup\$
    – FlipTack
    Dec 27, 2019 at 19:10
3
\$\begingroup\$

Eats, shoots and leaves

As you know, a panda eats shoots and leaves. Your task today is to write a panda in as few bytes as possible.

       1
      / \
     7   5
    / \   \
   2   6   9
      / \   \
     3   8   4

Here this tree has two branches, 1-7-6 and 1-5-9. The branch 1-7-6 has a shoot 2 and leaves 3 and 8, while the branch 1-5-9 has a leaf 4. After eating the shoots and leaves, your panda should output the following tree:

       1
      / \
     7   5
      \   \
       6   9

If your panda is a program or function, it must output the tree in the same format that you input it. Alternatively it can be a subroutine that modifies the tree in-place.

If it helps, you can assume that the tree has at least two nodes, and/or that each node has at most two child nodes.

No standard loopholes.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What is a shoot, and what is a leaf? Is this question asked to remove all leaf nodes (nodes without children) in a tree? \$\endgroup\$
    – tsh
    Jan 13, 2020 at 1:30
  • \$\begingroup\$ @tsh For the purposes of the story, a shoot is a node which has no child nodes but whose parent has at least one grandchild node. Otherwise as you notice it has no effect on the outcome. \$\endgroup\$
    – Neil
    Jan 13, 2020 at 10:58
3
\$\begingroup\$

Bucket and Minimize

Post here

\$\endgroup\$
6
  • \$\begingroup\$ @FryAmTheEggman thanks for the info. updated \$\endgroup\$
    – scrawl
    Jan 21, 2020 at 9:40
  • \$\begingroup\$ "floor(12%5)+1 into 12 mod 5 buckets, and floor(12%5) in the rest". Shouldn't those floor(12%5) be floor(12/5) based on your \$\left\lfloor\frac{|L|}{N}\right\rfloor+1\$ formula? \$\endgroup\$ Jan 22, 2020 at 10:40
  • \$\begingroup\$ @KevinCruijssen er, yes. keeping things conventional. in my preferred language (k4) % is float division. i'll update it to avoid confusion. thanks! \$\endgroup\$
    – scrawl
    Jan 22, 2020 at 12:27
  • \$\begingroup\$ Ah ok. In most languages I know % is modulo and / is division. :) I thought maybe % was integer-division in your language of choice, making the floor obsolete. But your edit is indeed clearer. \$\endgroup\$ Jan 22, 2020 at 12:47
  • \$\begingroup\$ I would recommend cleaning the body of this answer and linking to the actual challenge: codegolf.stackexchange.com/q/198406/75323 \$\endgroup\$
    – RGS
    Feb 2, 2020 at 21:07
  • \$\begingroup\$ @RGS cleaned up \$\endgroup\$
    – scrawl
    Feb 2, 2020 at 23:55
3
\$\begingroup\$

Buildings made from cubes

Posted to main; thanks for input provided!

\$\endgroup\$
5
  • \$\begingroup\$ this looks perfect for fastest-code. with fastest-algorithm it's difficult to do complexity analysis on the solutions. \$\endgroup\$
    – ngn
    Jan 4, 2020 at 23:53
  • \$\begingroup\$ @ngn thanks, I’ve amended the alternative suggestion \$\endgroup\$ Jan 5, 2020 at 0:23
  • 3
    \$\begingroup\$ it may be good to mention explicitly that all blocks must form a single connected component, otherwise 2 separate 1x1x2 pieces would technically satisfy rules 1-4 \$\endgroup\$
    – ngn
    Jan 5, 2020 at 1:47
  • \$\begingroup\$ Is this basically \$a_n = \sum_{i=1}^n polyminoNumber(i)\cdot i^{n-i}\$? \$\endgroup\$ Feb 3, 2020 at 14:56
  • \$\begingroup\$ @mypronounismonicareinstate no it's not, though it is related to the polyomino numbers. I've posted to main (sorry for not updating Sandbox post), so please see there for two implementations of code. \$\endgroup\$ Feb 3, 2020 at 17:35
3
\$\begingroup\$

Parse Iota

Iota is a simple programming language, considered the "sister" of the language Jot. More info can be found here Every Iota program consists of either an i, or a * followed by two Iota programs. In BNF, this is:

iota ::= i | *<iota><iota>

Challenge

Your task is to, given any input, output a truthy or falsy value based on whether or not it is a valid Iota program.

  • Your program may take input in any form agreed upon by the community here. It just has to be able to take input from the user in some form.
  • The same rule goes for output. See the post above for valid output methods. Output may be any truthy or falsy value in your language, including integers, strings, arrays, or objects. If it can be converted to a Boolean, it is OK.

Example I/O

Input: i
Output: 1
Input: hello
Output: 0
Input: *i*i*ii
Output: 1
Input: i*i
Output: 0
Input: ***
Output: 0
Input: *
Output: 0
Input: iiiiiiiii
Output: 0;
Input: i
Output: 1
Input: *ii
Output: 1
\$\endgroup\$
5
  • \$\begingroup\$ Suggested test cases: *, ***, iiiiiiiiiii \$\endgroup\$
    – 79037662
    Feb 12, 2020 at 23:27
  • \$\begingroup\$ Ok, I added those @79037662 \$\endgroup\$
    – sugarfi
    Feb 13, 2020 at 0:37
  • \$\begingroup\$ I don't get how i*i*i*ii is produced. If I understand the grammar right, this is equivalent to checking if parens are matched after removing the final i that must come at the end, using *i as (). \$\endgroup\$
    – xnor
    Feb 13, 2020 at 7:12
  • \$\begingroup\$ @xnor - sorry, my bad. i fixed that. \$\endgroup\$
    – sugarfi
    Feb 13, 2020 at 12:02
  • 1
    \$\begingroup\$ I think that despite the different presentation, this would be similar enough to checking paren matching to be a duplicate. \$\endgroup\$
    – xnor
    Feb 14, 2020 at 11:22
3
\$\begingroup\$

The uniquely solvable sudoku

The task

Given a standard 9x9 sudoku board, output a Truthy value if that sudoku admits one and only one solution. Output a Falsy value if the sudoku has a number of solutions other than one. This means 0 solutions and two or more solutions.

The input

The board can be given in any sensible format. Some come to mind, and I'll exemplify for a 4x4 sudoku.

  • a 2D array with the state of the board, with any placeholder value for non-filled cells (including the digit 0, or no value at all if your language supports it): [[1,2,#,4],[#,4,1,2],[2,1,4,#],[4,#,2,1]]
  • a string of the digits row by row or column by column, so "12#4#412214#4#21" or "1#24241##14242#1"

The output

A Truthy value if the sudoku puzzle has a unique solution, Falsy otherwise.

Test cases

(To add)

Truthy

Falsy

\$\endgroup\$
2
  • \$\begingroup\$ Hmm, I'm surprised this isn't a duplicate with the amount of Sudoku-related challenges we have. Closest related challenge I could find is perhaps this one. \$\endgroup\$ Feb 18, 2020 at 16:21
  • \$\begingroup\$ @KevinCruijssen Thanks for your search! I can link this one, but this is still a new challenge, right? :) \$\endgroup\$
    – RGS
    Feb 18, 2020 at 17:44
3
\$\begingroup\$

Square Deltas

Given an strictly positive integer n, output all numbers in the sequence up to the index n. For the current test cases of the current challenge numbers are one-indexed. However, other formats are allowed as default.

Base sequence

We start from this sequence:

1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, ...

The sequence is described as follows: 1, 2 (xN), 1 repeated arbitary times. There are 2 more 2's than the previous 2-set, and the 2-sequence starts at 1. i.e.:

1,       2,       1,
1,    2, 2, 2,    1,
1, 2, 2, 2, 2, 2, 1,
and so on ...

However, our point is not to output this sequence. For every item in this sequence, add the item by that item of that sequence.

Adding the sequence

Here's an example of adding the sequence. Here, our sequence starts with 0:

  The sequence
    |
    v
0 + 1 = 1
1 + 2 = 3
3 + 1 = 4
4 + 1 = 5
...

Our generated sequence is therefore

0, 1, 3, 4, ...

Example test cases

Here is a sample program outputting the sequence up to the input.

3 -> [0, 1, 3]
10 -> [0, 1, 3, 4, 5, 7, 9, 11, 12, 13]

Sandbox

  • Can the challenge be clarified?
\$\endgroup\$
3
  • 5
    \$\begingroup\$ Why is the task asking for infinite output after index n, rather than a standard sequence challenge? A "standard sequence challenge" usually allows several I/O formats in a single challenge, including "input n -> the number at index n", "input n -> first n numbers", "no input -> infinite output of the sequence". \$\endgroup\$
    – Bubbler
    Mar 6, 2020 at 4:49
  • 2
    \$\begingroup\$ No, you don't need to make it harder. And even if it is too easy, please don't try to fake up the difficulty by enforcing unnatural I/O requirements. \$\endgroup\$
    – Bubbler
    Mar 6, 2020 at 4:56
  • 3
    \$\begingroup\$ Are you sure that you want to override the default sequence IO? Do you actually have a good reason for doing so? \$\endgroup\$
    – Jo King Mod
    Mar 12, 2020 at 4:36
3
\$\begingroup\$

Pendulum Encoding

Given an array as an input (which can be any acceptable/convenient format in your language), implement pendulum encoding.

How do I do that?

The current iteration index starts at 0.

  • If the iteration index is even, append the current item onto the output list.
  • If the iteration index is odd, prepend the current item onto the output list.

An example

The input is [a b c d e f g].
Note that the letters a-g are atoms, to prevent confusion from the iteration index.
N: the iteration index

N:0 Out:      [a]
N:1 Out:    [b a]
N:2 Out:    [b a c]
N:3 Out:  [d b a c]
N:4 Out:  [d b a c e]
N:5 Out:[f d b a c e]
N:6 Out:[f d b a c e g]

The output should be [f d b a c e g].

Another example

The input is [u d l n u e m p].

N:0 Out:        [u]
N:1 Out:      [d u]
N:2 Out:      [d u l]
N:3 Out:    [n d u l]
N:4 Out:    [n d u l u]
N:5 Out:  [e n d u l u]
N:6 Out:  [e n d u l u m]
N:7 Out:[p e n d u l u m]

Test cases

Here's a sample program doing this encoding.

Take note that the atoms in the list aren't always unique.

[a,b,c,d,e,f,g]   -> [f,d,b,a,c,e,g]
[]                -> []
[a]               -> [a]
[a,b,c,d]         -> [d,b,a,c]
[a,b]             -> [b,a]
[a,b,d]           -> [b,a,d]
[a,b,a,c,b,c]     -> [c,c,b,a,a,b]
[a,a,b,b,c,c]     -> [c,b,a,a,b,c]
[u,d,l,n,u,e,m,p] -> [p,e,n,d,u,l,u,m]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I can't see any issues with this challenge apart from the usual "make sure that you specify that output and input can be taken in any reasonable and convenient format". \$\endgroup\$
    – lyxal
    Mar 18, 2020 at 0:00
  • \$\begingroup\$ The "example" in the first paragraph is confusing. It seems to be example input, but it deson't have clear context. If feels very out of place. \$\endgroup\$
    – Wheat Wizard Mod
    Mar 20, 2020 at 15:16
  • \$\begingroup\$ Are the "atoms" unique? If not, you should at least include a test case where they aren't. \$\endgroup\$ Mar 20, 2020 at 20:20
  • \$\begingroup\$ Naming a generic array a, then redefining a as a generic atom and never referring to the original array is not very helpful in an explanation. \$\endgroup\$ Mar 21, 2020 at 0:09
3
\$\begingroup\$

Join by intersection

Given a list of strings, output these strings joined by their largest intersecting parts. Your output has to be optimal. Strings have to be joined in the order given.

What is an intersection anyway?

Suppose you have two strings:

"abcbc" "bcbcd"

You extract all suffixes of the first string, as well as all prefixes of the second string:

["abcbc", "bcbc", "cbc", "bc", "c"]
["bcbcd", "bcbc", "bcb", "bc", "b"]

We trunctuate both of these lists to the length of the list of the smaller length (it's an identity in this current case).

Then, we find all items at the same index which are equal to the other item at the same index:

["bcbc", "bc"]
["bcbc", "bc"]

We return the longest string of the output. Therefore, the intersection is:

"bcbc"

How to join two strings by the intersection

To join by the intersection you simply

  1. Append the first string without the intersection to the output string
  2. Append the intersection to the output string
  3. Append the second string without the intersection to the output string

For example, in our example case:

"abcbc" "bcbcd"
(The intersection is "bcbc")

Step 1. Out:"a"
Step 2. Out:"abcbc"
Step 3. Out:"abcbcd"

Reducing a join over a list

If you want to reduce a join over a list

["abc","bcd","rfh","hal"]

You connect them by their longest common substring:

abc
 bcd
    rfh
      hal
=========
abcdrfhal

Therefore the expected output is abcdrfhal.

Further walkdown

You cannot join two strings if their substring can be found in the middle. For example:

["aXc","bXd"]

If you try to match them by the middle substring:

aXc
bXd

You would realize that the other overlapping characters are not equal to each other. That is, a is not equal to b, and c is not equal to d. In that case you simply append the string in the join:

aXc
   bXd
======
aXcbXd

Likewise, if either of these strings contain each other, but isn't equal to the other string, you should simply append the string. E.g.

["abcd","bc"]

would give

abcd
    bc
======
abcdbc

Substrings can overlap past each other. E.g.

["abc","bcd","cde"]

would result in the following join:

abc
 bcd
  cde
=====
abcde

which would evidently make the output abcde.


Strings have to overlap as much as possible. That means, in this example:

["abcbc","bcbcd"]

This is not okay (even if they do overlap):

abcbc
   bcbcd
========
abcbcbcd

Instead, this should be done:

abcbc
 bcbcd
======
abcbcd

The join is consecutive based on the consecutive inputs. For example:

abcde
  cde
     abcde
==========
abcdeabcde

Test cases

A program is worth a thousand words. Here 's a reference implementation that I use to check the test cases.

["abc","bcd","rfh","hal"] -> "abcdrfhal"
["mmm","qqq","rrr"] -> "mmmqqqrrr"
["abcbc","bcbcd"] -> "abcbcd"
["aXc","bXd"]    -> "aXcbXd"
["abc","bcd","cde"] -> "abcde"
["abcd","bc"] -> "abcdbc"
["abcde", "cde", "abcde"] -> "abcdeabcde"
\$\endgroup\$
15
  • \$\begingroup\$ How would you join aXc and bXd? They have the common substring X in the middle. \$\endgroup\$
    – Bubbler
    Mar 25, 2020 at 2:24
  • \$\begingroup\$ Can strings overlap past each other like abc,bcd,cde->abcde? \$\endgroup\$
    – xnor
    Mar 25, 2020 at 2:25
  • \$\begingroup\$ Do strings have to overlap as much as possible, or just overlap any amount? For example, for abcbc and bcbcd, is either of abcbcd or abcbcbcd OK? \$\endgroup\$
    – xnor
    Mar 25, 2020 at 4:43
  • \$\begingroup\$ Do strings have to be joined in the order given? I feel like the answer is surely "yes", but the text doesn't say outright. Really, I think all these Sandbox questions come from the fact that the task is never actually stated precisely, and doing that would probably head off any further question. \$\endgroup\$
    – xnor
    Mar 25, 2020 at 4:49
  • 2
    \$\begingroup\$ Along these lines, what happens if one string contains another? Do we do abcd,bc->abcd? \$\endgroup\$
    – xnor
    Mar 25, 2020 at 4:51
  • \$\begingroup\$ Suggested test case: abcde, cde, abcde. \$\endgroup\$ Mar 25, 2020 at 4:52
  • \$\begingroup\$ @JonathanFrech Well, what's the expected output? I thought it was abcde in this case. \$\endgroup\$
    – user92069
    Mar 25, 2020 at 6:00
  • \$\begingroup\$ I was not completely sure what the output would be. abcdeabcde does seem reasonable. \$\endgroup\$ Mar 25, 2020 at 7:40
  • 2
    \$\begingroup\$ I still don't actually understand how the task works precisely. A reference implementation isn't a replacement for a specification. \$\endgroup\$
    – xnor
    Mar 25, 2020 at 23:09
  • \$\begingroup\$ @xnor I've added back the spec, can you understand it now? \$\endgroup\$
    – user92069
    Mar 26, 2020 at 6:24
  • \$\begingroup\$ Not really, sorry. I still wouldn't know what abcd,bc would give. \$\endgroup\$
    – xnor
    Mar 26, 2020 at 6:29
  • \$\begingroup\$ @xnor Are there any more test cases you don't understand? \$\endgroup\$
    – user92069
    Mar 26, 2020 at 6:35
  • \$\begingroup\$ This seems to be related to the shortest superstring problem for two strings, but you don't have to handle the case where one of the strings is a substring of another, and the joining order is fixed. Is that correct? Just informing that the specification spans four pages on my laptop, with default browser font size. \$\endgroup\$ Mar 26, 2020 at 6:55
  • \$\begingroup\$ @a'_' en.wikipedia.org/wiki/… \$\endgroup\$ Mar 26, 2020 at 6:58
  • \$\begingroup\$ @mypronounismonicareinstate Ah, it's a duplicate. Thank you for the mention. \$\endgroup\$
    – user92069
    Mar 26, 2020 at 6:58
3
\$\begingroup\$

Sum in 2540 Sums

This is my attempt to pair with .

You need to write a program that sums all codepoints of the input string.

Rules

  • The input will always be in printable ASCII.
  • The sum of the codepoints of your source must be exactly 2540.

    • You are allowed to use your language's own code page to calculate your program's codepoints.
  • Null bytes (which don't contribute to your codepoint sum) are banned.

  • The program must not work with any consecutive substring removed.
  • This is . Your score is the length of your source code, the shorter being better.
\$\endgroup\$
6
  • \$\begingroup\$ You defined the "base score" only to reference that term exactly once. It seems to be move confusing than helpful. Wouldn't "The sum of the codepoints of your source must be exactly 2540" be clearer and shorter? \$\endgroup\$
    – Wheat Wizard Mod
    Apr 9, 2020 at 21:18
  • \$\begingroup\$ Although I am neither suggesting nor recommending against, this could also work as code-bowling if you either outlaw null bytes or sum up the (codepoints+1). \$\endgroup\$
    – Wheat Wizard Mod
    Apr 9, 2020 at 21:22
  • \$\begingroup\$ @AdHocGarfHunter The rules are a lot simpler if it were code-golf, and we haven't paired codepoint sum with code golf before. Also I need to fullfill a goal to pair code-bowling with code-golf. This analysis says that there are 11 tags not paired with code-golf, I'm going to make it 10. \$\endgroup\$
    – user92069
    Apr 9, 2020 at 21:24
  • \$\begingroup\$ As far as I know, [pristine-programming] is the tag for programming with the substring removal restriction here. (I think this would work as a [code-bowling] as well as well) \$\endgroup\$ Apr 10, 2020 at 0:12
  • \$\begingroup\$ @mypronounismonicareinstate So which side are you for? Code golf or code bowling? \$\endgroup\$
    – user92069
    Apr 10, 2020 at 0:53
  • \$\begingroup\$ Probably code-golf. \$\endgroup\$ Apr 10, 2020 at 1:07
3
\$\begingroup\$

Will this simplified befunge-93 program terminate?

The challenge today is to solve the halting problem for simplified befunge-93.

Simplified befunge-93 has exactly four instructions - > v < ^ @. The program is restricted to a 80x24 grid. Each of the commands modifies the instruction pointer (so that, for instance > makes the instruction pointer start executing commands to the right), except of the @ instruction, which terminates the program.

When the instruction pointer reaches the end, it wraps around (imagine the snake game).

You may read input in form of a string or a two-dimensional array using any reasonable device. The output may be either a truthy value if the program terminates, or a falsy value if the program doesn't terminate.

Example data

Input:
>v
^<

Output: Doesn't terminate.
----------------------------------------
Input:
> v
 @
^ <

Output: Doesn't terminate.
----------------------------------------
Input:
v@
[23 newlines]
>v

Output: Terminates.
----------------------------------------
Input:
v @
[23 newlines]
>v

Output: Doesn't terminate.
----------------------------------------
Input:

Output: Doesn't terminate.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Possibly dupe? \$\endgroup\$ Apr 27, 2020 at 8:47
  • \$\begingroup\$ is the instruction ptr initially at 0 0 and moving to the right? \$\endgroup\$
    – ngn
    Apr 27, 2020 at 8:55
  • \$\begingroup\$ yes, I maybe forgot to state that. But it's most probably a dupe right now, so I don't think I should push it forward anymore :P \$\endgroup\$ Apr 27, 2020 at 8:56
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\$
\$\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
1
18 19
20
21 22
155

You must log in to answer this question.

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