426
\$\begingroup\$

What is the Sandbox?

This "Sandbox" is a place where Programming Puzzles & Code Golf (PPCG) users can get feedback on prospective challenges they wish to post to the main page. This is useful because writing a clear and fully specified challenge on the first try can be difficult. There is a much better chance of your challenge being well received if you post it in the Sandbox first.

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

\$\endgroup\$
  • 2
    \$\begingroup\$ Suggestion: instead of having a notice on the top answer ("note: if you are..."), you'd better just put a moderator notice below the question \$\endgroup\$ – nicael Mar 19 '18 at 19:35
  • 3
    \$\begingroup\$ @nicael We can only choose from three post notices: citation needed, current event, and insufficient explanation. \$\endgroup\$ – Dennis Apr 7 '18 at 14:43
  • \$\begingroup\$ If you remove a post but didn't post it you can replace the text body with [](lots of text here to reach the min chars) to make it much smaller when removed \$\endgroup\$ – Christopher Apr 13 '18 at 17:54
  • 5
    \$\begingroup\$ @Christopher Please don't do that for old proposals. It clutters the first page with an answer nobody cares about anymore, instead of staying hidden on page 10 where it will bother nobody. \$\endgroup\$ – Dennis Apr 13 '18 at 18:17
  • \$\begingroup\$ @Dennis ? what are you talking about. As if if you didn't post it like you just removed you own sandbox because dupe or something \$\endgroup\$ – Christopher Apr 13 '18 at 18:18
  • 4
    \$\begingroup\$ @Christopher If your proposal is still on the first few pages, you can replace the proposal with a stub to save vertical space on these pages. However, if your proposal is already on page 10, editing your proposal will bump it to page 1, where space is more precious than on page 10. \$\endgroup\$ – Dennis Apr 13 '18 at 18:21
  • \$\begingroup\$ @Dennis ohh that makes sense \$\endgroup\$ – Christopher Apr 13 '18 at 18:25
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/12599/… \$\endgroup\$ – Redwolf Programs Apr 17 '18 at 17:38
  • 1
    \$\begingroup\$ Maybe it's time to consider cleaning some of this up a bit. There's just too much to go through and some of these proposals are years old and obviously not going anywhere (even some of the good ones). Perhaps cull anything that is two years old and has likewise been inactive for as long? \$\endgroup\$ – ouflak Aug 6 '18 at 9:07
  • \$\begingroup\$ @ouflak You can sort posts by "active". That seems to resolve all of the problems you describe. \$\endgroup\$ – FryAmTheEggman Sep 27 '18 at 19:04
  • \$\begingroup\$ I already posted this, but codegolf.stackexchange.com/questions/176599/… \$\endgroup\$ – 2br-2b Nov 27 '18 at 2:38
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ It seems like there is a rollback war with moderators and the Community user to add and remove the featured tag. \$\endgroup\$ – smileycreations15 Mar 21 at 21:13
  • 3
    \$\begingroup\$ @smileycreations15 That's unfortunately unavoidable. Community is an automatic script, and, since most featured questions are only temporarily so, it assumes that we don't want this question to be featured forever. However, we do, so a mod has to edit the tag in every now and then. \$\endgroup\$ – Erik the Outgolfer Mar 24 at 15:22
  • 2
    \$\begingroup\$ @EriktheOutgolfer Yeah. Maybe they can create a special [featured-pin] tag which will both feature it and pin it from removal by the Community user. \$\endgroup\$ – smileycreations15 Mar 24 at 17:20

2376 Answers 2376

1
\$\begingroup\$

Not a challenge, but not certain of the wording so trying it out here:


Tips for golfing in JSLint


What general tips do you have for golfing in JavaScript restricted to satisfying JSLint with default options? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to JSLint (e.g. "remove comments" is not an answer).

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

Unjagged my array


Given a jagged array of integers, rearrange the integers such that

  • The shape of the jagged array is unchanged, and

  • The jaggedness of each subarray is minimized.

Here "jaggedness" is defined as the sum of the absolute differences in each subarray. If an array has only one element, then the jaggedness of that array must be 0, since there are no absolute differences to consider.

We only care about the differences in elements in the same subarray. So for example:

[[1, 2], [100]]

has a jaggedness of 1, since the first array has a jaggedness of \$abs(1-2) = 1\$ and the second array has a jaggedness of 0. We don't care that the difference between 2 and 100 is 98 since they are different subarrays.

Here's an example:

Input: [[16, 8], [15], [4, 42, 23]]
jaggedness of input: [abs(16 - 8)] + [0] + [abs(4 - 42) + abs(42 - 23)] =
8 + 38 + 19 = 65

One possible output: [[4, 8], [42], [15, 16, 23]]
jaggedness of this output: [abs(4 - 8)] + [0] + [abs(15 - 16) + abs(16 - 23)] = 4 + 1 + 7 = 12

Of course, this is one possible output. Any of these outputs would also have a jaggedness of 12:

[[4, 8], [42], [23, 16, 15]]
[[8, 4], [42], [15, 16, 23]]
[[8, 4], [42], [23, 16, 15]]

Clarifications

  • The input will always contain non-negative integers. The input will also always have a length >= 1, and all of the subarrays will have a length >= 1. This means that you must handle inputs as small as [[n]], where n is any non-negative integer.
  • If the input is already arranged to be as smooth as possible, it is acceptable for your code to output the integers in a different order, as long as this new order has the same jaggedness. For example, if the input was

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

    then your program may return the input unchanged, or it may return

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

    or any of the other arrangements with jaggedness 3.

Fastest code

This is a challenge, so the submission with the shortest run time for a hidden test case will win. I will use 2 different test cases with different shapes, and your score will be the sum of the time for each. (I haven't yet decided how large these test cases should be. I might adjust them once submissions come in so that it takes an appropriate amount of time.)

All submissions will be tested on my machine:

  • Windows 10
  • i7-4790k
  • 8 GB RAM

You can use any language that is freely available on Windows 10. Please also provide instructions for running your submission. I will test each submission at my soonest convenience after it's posted, and then comment an unofficial score. After 1 week, I will test every submission, and post a leaderboard.

Test Cases

These test cases were generated with and verified by a python brute-forcer.

Input: [[1, 2, 9], [10, 11]]
Output: [[9, 10, 11], [1, 2]] (jaggedness 3)

Input: [[4, 8, 15], [16], [23, 42]]
Output: [[4, 8, 15], [16], [23, 42]] (jaggedness 30)

Input: [[45, 98, 9, 46], [48, 53, 59], [13], [38, 94]]
Output: [[45, 46, 48, 53], [9, 13, 38], [59], [94, 98]] (jaggedness 41)

Note that none of these test cases show the only acceptable answer, merely one acceptable answer. For example, any output would remain valid if a subarray was reversed.

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

43 quintillion permutations

We can represent a Rubik's Cube as a net as follows (when solved):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Each letter represents the corresponding colour (W is white, G green etc.)

It has been shown that there are \$43,252,003,274,489,856,000\$ (~\$43\$ quintillion) different permutations that a Rubik's Cube can be in.

Your task is to take an integer between \$1\$ and \$43,252,003,274,489,856,000\$ and output the corresponding permutation, in the manner shown above. You may choose how the permutations are ordered, but the algorithm you use must be shown to generate a unique, and correct, permutation for each possible input.

Invalid permutation rules

Taken from this page

If we say each permutation has a parity, based on the parity of the number of swaps to reach that permutation, we can say

  • Each corner piece has three possible orientations. It can be oriented correctly (0), clockwise (1) or counterclockwise (2). The sum of corner orientations always remain divisible by 3

  • Each legal rotation on the Rubik's Cube always flips an even number of edges so there can't be only one piece oriented wrong.

  • Considering the permutation of all the corners and edges, the overall parity must be even which means that each legal move always performs the equivalent of an even number of swaps (ignoring orientation)

For example the following three net are invalid outputs:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRYBBBOO
   YYO
   YYY
   YYY

(The yellow/orange/blue corner is rotated into an impossible permutation)

Rules

  • You must prove, however way you wish, that the algorithm is valid. You do not have to enumerate every single permutation, as long as you prove the validity of your algorithm.
  • This is a so the shortest code, in bytes, wins.

Sandbox

  • Any feedback or duplicates?
  • Any suggestions for tags?
  • I believe I've covered the rules for invalid permutations, but if not, or you have a clearer set of rules, don't hesitate to comment
\$\endgroup\$
  • \$\begingroup\$ I think the requirement for 1:1 mapping is a bit much. I think it would be much more reasonable to only require that there is at least one numeric representation for every possible permutation and that every whole number corresponds to exactly one permutation. I can't even begin to wrap my mind around a solution that ensures there are no duplicate states on the way up to 43-whatever quintillion, but I can think of a few that could theoretically encode any permutation, but with duplicates in the mapping. \$\endgroup\$ – Beefster Dec 11 '18 at 22:20
  • \$\begingroup\$ More on "every whole number corresponds to exactly one permutation" - the number of permutations of a rubik's cube requires a minimum of 66 bits to represent, so arbitrary-length integers are already a requirement to implement this challenge, therefore it is totally reasonable to need arbitrarily long integers to represent all permutations. \$\endgroup\$ – Beefster Dec 11 '18 at 22:23
  • \$\begingroup\$ @Beefster I have been toying with the idea of converting this to a code challenge, where your score is the number of unique permutations you are able to output. \$\endgroup\$ – caird coinheringaahing Dec 11 '18 at 22:51
  • \$\begingroup\$ The issue with that is that it's trivial to cover all the permutations by associating each bit in the binary representation as whether or not to rotate a certain side 1-quarter turn clockwise. The other issue is that it's very difficult to calculate the minimum number needed to represent all permutations for any given algorigthm. I like the idea of making it a code challenge better than code golf, but I can't think of a good criteria either. \$\endgroup\$ – Beefster Dec 11 '18 at 23:05
1
\$\begingroup\$

Destroy the Computers with Magnets!

The robot apocalypse has finally arrived. But as we all know, robots are controlled by computers. And magnets are a convenient way of disabling computers.

Your task: place the magnet close enough to the computer so that it disables the computer.

A computer looks like this (always the exact same size):

 ____
|    |
|    |
|____|

The magnet looks like this:

o

The magnet needs to be touching the computer to do its work:

 o____o
o|    |o
o|    |o
o|____|o
 oooooo

Note the lack of placements on the top; that is intentional. People use the computer on that side, and would easily see the magnet and remove it.

So if you are given a picture of some computers:

       ____
      |    |
 ____ |    |
|    ||____|
|    |      ____
|____|     |    |
           |    |
           |____|

You should place 1 magnet for computer next to the computers:

       ____
      |    |
 ____ |    |
|    ||____|
|    |  o   ____
|____|     |    |
 o        o|    |
           |____|

Magnets may touch computers, but there must be 1 touching magnet per computer.

Due to the apocalypse, resources are scarce, so your program to place magnets must be as short as possible.

Test cases:

Input
~~~~~
Example outputs (not only possible outputs)
=====
       ____
      |    |
 ____ |    |
|    ||____|
|    |      ____
|____|     |    |
           |    |
           |____|
~~~~~
       ____
      |    |
 ____ |    |
|    ||____|
|    |  o   ____
|____|     |    |
 o        o|    |
           |____|

        ____
       |    |
  ____ |    |o
 |    ||____|
 |    |     o____
o|____|     |    |
            |    |
            |____|
=====
More soon....
\$\endgroup\$
  • \$\begingroup\$ Is it permissible for a "component" to be adjacent to multiple voting machines? For example, with two voting boxes 1 space apart, would placing two components in that column be valid? \$\endgroup\$ – Kamil Drakari Dec 15 '17 at 20:03
  • \$\begingroup\$ @KamilDrakari That is allowed, I will edit. \$\endgroup\$ – Comrade SparklePony Dec 16 '17 at 0:27
  • \$\begingroup\$ Would these be valid outputs? Also is the voting machine always the same size? \$\endgroup\$ – ბიმო Dec 16 '17 at 20:24
  • \$\begingroup\$ @BruceForte Those are all valid outputs except for number 4: there must be at least 1 physical component per voting machine (as it says in the challenge.) Voting machines are all the same size. I will edit. \$\endgroup\$ – Comrade SparklePony Dec 18 '17 at 14:24
1
\$\begingroup\$

Minimal Substring Lookup Table

A fairly common component of code golf challenges is taking input as a string, and finding the index of that string within an array. A common way to golf that action is to instead store a substring of each item in the array, and take the same substring of the input to use when looking up the index. For example, this question has some fairly large strings that need to be indexed, but this answer found that each item could be uniquely identified by its 4th letter.

Challenge

Find the shortest substring that, when applied to each string in the input, results in a new set of unique strings.

Input

  • Input is list of strings in any default format
  • The strings will consist of printable ASCII characters.
  • The strings will not have trailing spaces
  • There will be no duplicate strings

Output

  • Output should be a list of the shortened strings after applying the substring
  • If outputting indexes, 0-indexing or 1-indexing may be used.
  • When strings have different lengths, substrings exceeding the length of some lines may be handled any of these ways:
    • Truncate to the available characters, e.g. ["abc","acd","ab"] => ["bc","cd","b"]
    • Pad shorter strings with spaces, e.g. ["abc","acd","ab"] => ["bc","cd","b "]. Note that input strings can contain spaces which need to be taken into account, so ["ab c","acdc","ab"] must not become ["b ","cd","b "].
    • Wrap back to the start of the shorter string, e.g. ["abc","acd","ab"] => ["bc","cd","ba"]. Note that even with this method it is not necessary to look for substrings where every string wraps; the starting index should always be within the length of the longest input string.

Sandbox questions

  • Should I restrict the input strings to only a subset of printable ASCII?
  • Should I enforce one specific behavior for handling shorter strings? Requiring wrapping would let the challenge look for even shorter solutions requiring full wrapping, e.g. ["aba","ab"] => ["a","b"], but I don't want languages with different default substring implementations to need a lot of work just to get the wrapping working.
  • I used the term "substring" as something that is "applied" to a string to get the shortened version, but I know that's extremely wrong. Is there a better way to phrase this?
  • This challenge is related, but uses arbitrary substrings rather than aligned substrings. Should I mention it somewhere?
\$\endgroup\$
  • \$\begingroup\$ "Should I enforce one specific behavior for handling shorter strings?" - Personally, I'd say yes. \$\endgroup\$ – Shaggy Dec 20 '18 at 19:02
  • \$\begingroup\$ I think it would be better to output the position and length of the substring, rather than every substring. \$\endgroup\$ – 12Me21 Dec 30 '18 at 1:24
  • \$\begingroup\$ Alternatively, you could just say that all input strings have the same length. \$\endgroup\$ – japh Jan 16 at 8:43
1
\$\begingroup\$

Piano Scale Fingering

There are 12 different major scales on the piano, which have similar, but not identical, fingering. Furthermore, the fingering for each hand is slightly different.

The fingers of each hand are numbererd starting at 1 for the thumb. Each note usually takes the next finger in turn. For the left hand playing an ascending scale, this means that the numbers decrease, while for the right hand the numbers increase.

Of course you will run out of fingers before you get to the end of the scale. For the left hand, this means that when you get to the thumb you need to start again with one of the other fingers, while for the right hand this means that when you get to a certain finger you need to start again with the thumb.

Although there are eight notes in an octave, the part that repeats in the middle of a scale is seven, which is a prime number. Scales are therefore normally played using the repeatying sequnces 4321321 in the left hand and 1231234 in the right hand; the little finger is only used to avoid switching to the thumb on the first or last note respectively. Other adjustments also apply at the very start and end of the scale.

There are a couple of rules which work for most scales. The first rule is that you try to play the tonic with the thumb except at the appropriate end of the scale when you use the little finger. If you can't follow that rule then with the right hand you use the thumb when switching from a black note to a white note; with the left hand you aim for the thumb to land on a white note just before a black note.

Here is a full list of all 12 keys and their fingerings:

 #  Key Left Hand       Right Hand
-6  Gb  432132143213212 234123423412345
-5  Db  321432132143212 231234123123412
-4  Ab  321432132143212 231231234123123
-3  Eb  321432132143212 212341231234123
-2  Bb  321432132143212 212312341231234
-1  F   543213214321321 123412341231234
 0  C   543213214321321 123123412312345
 1  G   543213214321321 123123412312345
 2  D   543213214321321 123123412312345
 3  A   543213214321321 123123412312345
 4  E   543213214321321 123123412312345
 5  B   432143213214321 123123412312345
 6  F#  432132143213212 234123123412345

Please write a program function which takes as input the key (or #, which is the number of sharps in the key, or the negation of the number of flats in the key) of a scale and a flag (e.g. L or R) for which hand, and output the fingering for two octaves as above. (For longer scales you simply repeat the middle 7 digits so I don't see the utility of asking you to output an arbitrary number of octaves.)

Note that Gb is enharmonic to F# on the piano but you might find it easier to support one rather than the other. Please indicate which one your answer supports.

As an alternative to writing a single function I will also allow two named functions (one for each hand) but not two lambdas. The 1 byte per extra file penalty applies if you submit two full programs.

\$\endgroup\$
  • \$\begingroup\$ Why not two lambdas? \$\endgroup\$ – wizzwizz4 Dec 24 '18 at 9:42
  • \$\begingroup\$ @wizzwizz4 You're not allowed to encode the answer in your choice of boolean flags, and IMHO allowing lambdas would violate that loophole, but for named functions the answer isn't encoded in the name, so that's OK. (You could of course just pay the penalty for naming your lambdas.) \$\endgroup\$ – Neil Dec 24 '18 at 10:08
  • \$\begingroup\$ Some languages don't feature named lambdas, e.g. a LISP dialect without defvar. It seems completely arbitrary. \$\endgroup\$ – wizzwizz4 Dec 24 '18 at 10:10
  • \$\begingroup\$ What's wrong with lambdas? That rule is completely arbitrary. \$\endgroup\$ – Beefster Dec 28 '18 at 19:29
1
\$\begingroup\$

Front lines go front!

Given two lists of positive integers, bring the elements in the first one that are in the second to the far left, keeping their order the same as in the first list. You can assume that the second list's elements will all be unique.

These approaches are forbidden.

For example, let's call the first list \$A\$ and the second \$B\$. Here are some test cases:

\$A=[1,3,4,1,2,1,4,3,2,1,3,2,4,1],B=[1,3]\rightarrow[1,3,1,1,3,1,3,1,4,2,4,2,2,4]\$

\$A=[],B=[1,4,5]\rightarrow[]\$

\$A=[1,2,3,4,5,6,7,8,10],B=[]\rightarrow[1,2,3,4,5,6,7,8,10]\$

\$A=[],B=[]\rightarrow[]\$

\$A=[1,2,2,1,3,4,4],B=[1,2]\rightarrow[1,2,2,1,3,4,4]\$

\$A=[3,4,4,1,2,1,5],B=[1,5,2]\rightarrow[1,2,1,5,3,4,4]\$

\$A=[1,2,3,2,1,2,3,2,1],B=[4,5,6]\rightarrow[1,2,3,2,1,2,3,2,1]\$

\$A=[2,2,1,2,1,3,3,1,4],B=[1,2,3,4]\rightarrow[2,2,1,2,1,3,3,1,4]\$

Note: the integers aren't necessarily single-digit.

\$\endgroup\$
  • \$\begingroup\$ @JonathanFrech Yes. How could it be used anyway? \$\endgroup\$ – Erik the Outgolfer Dec 27 '18 at 11:42
  • \$\begingroup\$ @JonathanFrech Clarified. \$\endgroup\$ – Erik the Outgolfer Dec 27 '18 at 15:52
1
\$\begingroup\$

Do not not not not make a filter that doesn't not not not get rid of these words!

Tags: code-golf

Your program has to scan each run of "not"s in a sentence, and if the number of "not"s is odd, then replace it with only one "not". If it is even, replace it with the empty string.

Notes:

  • The "not"s are case-insensitive, so your input may be "not" or "Not" or more.
  • The input may only be taken in as a string.

Test cases:

 Don't not not -->  Don't
 not not not a not not  -->  not a
 NoT nOt not NOT noT a Not nOt noT  -->  not a not
hello notnot anot not anota not not not --> hello a anota not
\$\endgroup\$
  • 2
    \$\begingroup\$ We've had a very similar challenge before. On my phone so can't search properly for it to determine if it would be similar enough to be a dupe target. \$\endgroup\$ – Shaggy Dec 21 '18 at 19:27
  • \$\begingroup\$ Oh, let me see that then. \$\endgroup\$ – MilkyWay90 Dec 21 '18 at 19:40
  • \$\begingroup\$ So, input and output as a string? Would list of words be acceptable input/output? \$\endgroup\$ – ბიმო Dec 23 '18 at 14:20
  • \$\begingroup\$ @BMO List of words is not a valid format \$\endgroup\$ – MilkyWay90 Dec 25 '18 at 23:28
  • \$\begingroup\$ So, should I make this a question? \$\endgroup\$ – MilkyWay90 Dec 25 '18 at 23:30
  • \$\begingroup\$ What exactly counts as a not? Can it be part of another word? Do the nots have to be separated from each other by a single space? \$\endgroup\$ – 12Me21 Dec 30 '18 at 1:10
  • \$\begingroup\$ @12Me21 it can be part of another word \$\endgroup\$ – MilkyWay90 Dec 30 '18 at 3:07
1
\$\begingroup\$

Radiation Showdown KotH

In radiation hardening challenges, the goal is to write a program whose behavior doesn't change when an arbitrary character is removed from its source. This KotH explores an adversarial variant on this challenge in which two programs compete to survive the most character deletions. The twist is that each program is provided the source code of its opponent and outputs which character should be deleted from its opponent's source code next.

Gameplay

Suppose program A and B are competitors.

  1. Each program is run and the output is recorded. Let the output of program A be a and the output of program B be b. If one program fails to output a valid character index of its opponent's source code, the other program will be declared the winner of the match. If neither program outputs a valid index, then a tie is declared.
  2. The a'th character is removed from program B and the b'th character is removed from program A.
  3. Repeat steps 1 and 2 until there is a winner or a tie.

Submissions

Submissions should be a complete javascript or python program which:

  • Begins with a shebang (#!) indicating which language it is written. For python entries, this should be #!/usr/bin/python. For javascript entries this should be #!/app/.heroku/node/bin/node.
  • Takes three command line arguments: the code for the opponent program, the start of the range of deletable characters (x), and the end of the range (y). In python these can be accessed using sys.argv, while in javascript they can be found in process.argv.
  • Prints a number in the range [x,y) to stdout and terminates in less than 10 seconds.

Note: The index of the first deletable character of your opponent's program (x) is the index of the first character after the shebang. y is the length of the opponent program in characters (so y-1 is the last deletable character).

Sample Submissions

Python:

#!/usr/bin/python
import sys

# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
print (sys.argv[3]-1)
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

Javascript:

#!/app/.heroku/node/bin/node
// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
console.log(Math.round(Math.random() * process.argv[4]));
// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

Controller

I've hosted a web based controller at https://radiationshowdownkoth.herokuapp.com/. It should conform to the behavior specified in the Gameplay section. Let me know if you find any bugs.

Rules

  • Standard loopholes apply.
  • The use of preexisting interpreters and their components (parsers, lexers, etc) is banned. This includes, but is not limited to, calling the python and node binaries from your program (eg os.popen("python -c ...")), using builtin eval functions (eg python's exec), and using relevant modules (such as python's astlib). However, you may use regular expressions.
  • No malicious code.

Logistics

It will be a Round Robin Tournament. Each submission will be matched against every other submission. For each victory a submission achieves, it will be awarded 1 point. Likewise, ties are worth 0.5 points and losses are worth 0 points. The submission with the most points after all rounds have been completed wins this KotH. The winner will receive a bounty from yours truly, and the most popular entry will be awarded accepted answer. This KotH will be open to entries for a week following its posting, at which point the tournament will be run and a winner declared.

Meta

  • Duplicate?
  • Clarifications?
  • Other Language Suggestions besides Python & Javascript?
  • Are there any trivial strategies that would be overwhelmingly effective?
  • Any other foreseeable problems?
\$\endgroup\$
  • \$\begingroup\$ Would an empty program that outputs 0 auto win? \$\endgroup\$ – user202729 Dec 30 '18 at 3:31
  • \$\begingroup\$ Also, removing the shebang would kill the program. \$\endgroup\$ – user202729 Dec 30 '18 at 3:31
  • \$\begingroup\$ @user202729 Yes, I believe an empty program that outputs 0 would always win as the rules are currently written. Is it possible to write such a program in Javascript or Python? \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 3:35
  • \$\begingroup\$ @user202729 Actually, I am mistaken. If a program outputs 0 it will lose because 0 is not in the valid range of deletable characters (passed in as the second and third arguments to the program). This range starts after the end of the shebang in order to prevent the second exploit you pointed out. I will try to clarify this in the spec. However, a 0 character program that printed its second command line argument would auto win. As far as I know, it is not possible to write such a program in Javascript or Python, but please let me know how if it is. Thanks for the exploits :). \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 3:53
  • \$\begingroup\$ How are x and y computed? \$\endgroup\$ – user202729 Dec 30 '18 at 3:54
  • \$\begingroup\$ @user202729 x is the index of the first character after the shebang. y is the length of the program in bytes. I've edited the spec to include this information. \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 4:07
  • \$\begingroup\$ I like it! I'm not very experienced, but I'd say it's ready to go. \$\endgroup\$ – MilkyWay90 Dec 30 '18 at 4:10
  • \$\begingroup\$ Hm... in that case I'd say that because Python and Javascript are both "sensitive" (?) to radiation, making a program that would never lose is pretty easy. (just remove the first non-comment character or similar) \$\endgroup\$ – user202729 Dec 30 '18 at 4:12
  • \$\begingroup\$ @user202729 One way to defend yourself against a program that deletes the first non-comment character would be to define a variable with a really long name on the first non-comment line of the program. But I see your point. Any ideas for better choices of languages? \$\endgroup\$ – Zachary Cotton Dec 30 '18 at 4:28
  • \$\begingroup\$ It might be better to make the challenge "given a Python/JS program, delete a character so that it throws an error." Because AFAIK it's always possible, and such a program will never lose. \$\endgroup\$ – user202729 Jan 1 at 14:59
1
\$\begingroup\$

Unfactor a list

Jelly has an interesting built-in, ÆẸ. It's the inverse of ÆE. ÆE returns the exponents of the prime factors of an integer n, where each exponent corresponds to the prime number at its index, so, for example, [3, 5, 1] represents \$2^3\cdot3^5\cdot5^1\$. If a prime isn't included in the prime factorization of n, but there is at least one prime after it that is included, a zero is put in its place (\$p^0=1\$). So, for example, [3, 0, 5, 1] represents \$2^3\cdot5^5\cdot7^1\$, and [0, 4, 4, 50, 0, 7] represents \$3^4\cdot5^4\cdot7^{50}\cdot13^7\$.

Your job is to implement ÆẸ, ÆE's inverse. That is, you'll be given a list returned by ÆE, and your job is to find n.

You must always return a positive integer (strictly greater than zero). You may assume the input doesn't have negative or float exponents or trailing zeroes.

Note that you're encouraged not to use ÆẸ or your language's equivalent (if any) in your answer.

Using any of the standard loopholes is prohibited.

Test cases (you don't have to support exponents, an output or an input's length beyond your natural signed integer type's limit):

[] -> 1
[0, 4] -> 81
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] -> 1111
[10] -> 1024
[3, 5, 1] -> 9720
[3, 0, 5, 1] -> 175000
[31] -> 2147483648
[32] -> 4294967296
[63] -> 9223372036854775808
[64] -> 18446744073709551616
[0, 4, 4, 50, 0, 7] -> 5713082599062385095715588395684396863698753591853983125

Make more test cases:

To generate the input that corresponds to a given output, use this program.

To generate the output that corresponds to a given input, use this program.

\$\endgroup\$
  • \$\begingroup\$ @Adám Hm, I included the stuff for clarity, but I can remove it as well. EDIT: Removed the fluff. \$\endgroup\$ – Erik the Outgolfer Jan 7 at 22:49
1
\$\begingroup\$

Where can I get to from each location? (Transitive Closure)

Given an undirected graph (network) \$G\$, construct a new graph in which vertex (node) pair \$(u,v)\$ is an edge (are connected) if and only if a path \$(u,w_1,w_2,...,w_k,v)\$ exists in \$G\$ for some \$k\ge 0\$. This is known as \$G\$'s transitive closure. If this is clear to you, you're ready to get started. Otherwise, just read through the below sections. It is actually a very simple problem.

I/O formats

Take for example the graph (network)

1──2  3──4
│     │
5  6──7──8

We can represent¹ it as an adjacency (connection) matrix:

 │1 2 3 4 5 6 7 8
─┼───────────────
1│  ┘ 
2│
3│      ┘
4│
5│┘
6│            ┘
7│    ┘         ┘
8│

which is:

[[0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,1,0,0,0,1],[0,0,0,0,0,0,0,0]]

Note that here only one of \$(u,v),(v,u)\$ is represented, but we consider both directions as valid edges (connections).

Or as a list of of edges²:

[[1,2],[1,5],[3,4],[5,1],[6,7],[7,3],[7,8]]

Or for each vertex³ (node), the list of its adjacent vertices:

[[2,5],[1],[7,4],[1],[7],[3,8],[8],[]]

Or as a dictionary⁴:

{"1":[2,5],"3":[7,4],"7":[6,3,8]}

Any of these, and any other reasonable input and output formats (you optionally may use one format for input and another for output) are allowed, but you must state what your formats are. However, it is required that your formats support under-representing (e.g. [3,7] but not [7,3]) and over-representing (e.g. both [3,7] and [7,3]).

Walk-through

Let's use the representation [[1,2],[1,5],[3,4],[5,1],[6,7],[7,3],[7,8]]. Since 1 is connected to 2 then 2 is also connected to 1, so we add (it doesn't matter where) this edge (connection):

[[1,2],[1,5],[2,1],[3,4],[5,1],[6,7],[7,3],[7,8]]

It is also possible to travel [1,5] in reverse, but that pair is already represented further in the list. Now note that it is possible to find a path from 2 to 5, and vice versa, via 1, so we add these two edges:

[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8]]

This completes the left side of the graph. Similarly, we process the right side by adding the reversals of [3,4], [6,7], and [7,3]:

[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3]]

Two-step paths via 3 are possible, so we add [7,4] and [4,7]. Similarly, two-step paths via 7 are [6,3], [3,6], [6,8], [8,6], [3,8], and [8,3]:

[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3],[7,4],[4,7],[6,3],[3,6],[6,8],[8,6],[3,8],[8,3]]

Finally, we add the three-step paths [6,4], [4,6], [4,8], and [8,4]:

[[1,2],[1,5],[2,1],[2,5],[5,2],[3,4],[5,1],[6,7],[7,3],[7,8],[4,3],[7,6],[7,3],[7,4],[4,7],[6,3],[3,6],[6,8],[8,6],[3,8],[8,3],[6,4],[4,6],[4,8],[8,4]]

And this is our answer. It could of course be in any order.


  1. Though the connections do not have direction, I've only put in one entry in the table for each connection, and obviously the diagonal is all-true too, as every node is reachable from itself.
  2. Since the connections in this challenge do not have a direction, [1,5] and [5,1] are the same connection. This serves to illustrate that such may occur in the given data.
  3. Here, each node must have its own list, as the lists are paired to their points by their position in the data. However, each list need not be exhaustive as long as all connections are represented somewhere.
  4. Here, we can omit entries that are fully covered by the other entries.

\$\endgroup\$
  • \$\begingroup\$ Am I over complicating things by allowing all the various I/Os? \$\endgroup\$ – Adám Jan 7 at 13:26
  • \$\begingroup\$ All the input formats you mentioned seem reasonable to me and I'm sure different languages could use different formats when golfing. And if you restrict it to one specific format, you'll get people asking about using other formats anyways. \$\endgroup\$ – Emigna Jan 7 at 14:27
  • \$\begingroup\$ why not state it in graph-theoretic terms - vertex, edge, path, graph, incidence matrix - instead of the more vague location/place/point, connection, journey, network, connection table? "[1,5] and [5,1] are of course the same connection" - it would be just as valid and interesting a problem if it were about directed graphs, so it's not "of course" :) tag "repeated-transformation" is unnecessary - this can be solved in O(n^3) time without the use of ⍣≡. \$\endgroup\$ – ngn Jan 7 at 14:27
  • \$\begingroup\$ @Emigna Fixed. Thanks. \$\endgroup\$ – Adám Jan 8 at 7:25
  • \$\begingroup\$ @ngn Reason: I am not educated enough. Can I bother you to edit those in? I'll remove "of course". \$\endgroup\$ – Adám Jan 8 at 7:26
  • \$\begingroup\$ @Adám sure, i'll edit it. it's nice you put "transitive closure" in the title. many challenge authors (with or without cs/maths degrees) like to reinvent terminology, obscure the problem with backstories, etc. i find that mildly annoying. example - seems to be an interesting challenge but it takes so long to figure out what the words mean. \$\endgroup\$ – ngn Jan 8 at 13:43
  • \$\begingroup\$ @Adám how does it sound now? i'm not sure if i didn't go to far with that pseudo-academic lingo... \$\endgroup\$ – ngn Jan 8 at 14:21
  • \$\begingroup\$ @ngn Thank you so much. I've added in parenthesised layman's terms upon first usage in each section, and added a bit to the intro to keep people from fleeing. I also inserted the word "pair" on the very first line before (u,v) as it seemed to me that it was missing. Correct me if I'm wrong. \$\endgroup\$ – Adám Jan 8 at 15:05
  • \$\begingroup\$ @Adám i forgot to delete the word "vertex". inserting "pair" should be fine too \$\endgroup\$ – ngn Jan 8 at 15:12
  • \$\begingroup\$ Closely related. Directed version. \$\endgroup\$ – Peter Taylor Jan 9 at 11:40
1
\$\begingroup\$

"Cumbersome Crown words"

Introduction

This is my first entry here, so please be gentle if it's poorly stated. I'll need a bit of guidance to make it a good submission.

I am a typewriter maker, and I want to prove that the design of my competitor, Mr. Crown, is very inconvenient to use. To do that, I want a list of the most cumbersome words to type out on a Crown typewriter.

Challenge

Write a program that takes an argument "n" as a positive integer. You may load the Unix words list from any source (ignore case; discard any word containing anything outside of A-Z, such as "O'Brien", "L'vov", etc.). Given the layout shown below, output the "n" most cumbersome words to write, one result per line. Each result is the cumbersome word, some form of separator (eg. a space), then their word score (see below) with two decimals of precision (and your choice of decimal separator). Bonus if results are sorted in descending order by their word score, and further bonus if ties (by score) are also sorted in alphabetic order.

Crown typewriter layout

X Q K G B P M C O F L A N D T H E R I S U W Y J V Z

Word scoring

Assume the pointer starts in the leftmost position, on "X". Count each movement and each hammer strike as one unit, but divide the sum by the number of characters in the word. Hence, sample word scores are:

  • THEIR: 4.8 -- 24 units (14 movements, strike "T", movement, strike "H", movement, strike "E", 2 movements, strike "I", movement, strike "R") divided by 5 characters
  • LAND: 4.25 -- 17 units (10 movements, strike "L", movement, strike "A", movement, strike "N", movement, strike "D") divided by 4 characters
  • FOWL: 9.50 -- 38 units (9 movements, strike "F", movement, strike "O", 13 movements, strike "W", 11 movements, strike "L") divided by 4 characters
  • BARBARA : 8.00 -- 56 units (4 movements, strike "B", 7 movements, strike "A", 6 movements, strike "R", 13 movements, strike "B", 7 movements, strike "A", 6 movements, strike "R", 6 movements, strike "A") divided by 7 characters
  • X: 1 -- just hit the hammer once and you're done

Note: These examples are not the most cumbersome words.

Example Input and Output

Input:

5

Standard output:

ANNA 4.25

THEIR 4.80

LAND 4.25

BARBARA 8.00

FOWL 9.50

Bonus output:

FOWL 9.50

BARBARA 8.00

THEIR 4.80

ANNA 4.25

LAND 4.25

Scoring submissions and determining the winner

I'm really not sure what the best measure of success is. Definitely not code golf, because I can never distinguish the damn things from line noise or pure black magic. But what then? I'm not very familiar with which competition types are available.

If two solutions are tied for a position, but only one of them uses the bonus output format, then that one wins the tie.

\$\endgroup\$
  • \$\begingroup\$ Tak for at du bruger sandkassen! \$\endgroup\$ – Adám Jan 4 at 13:19
  • 1
    \$\begingroup\$ You can find a list of all winning criteria here, though I think code-golf is actually the best fit. When you are bothered by illegible answers, try asking for an explanation, most users are happy to explain how their code works and which tricks they used. \$\endgroup\$ – Laikoni Jan 6 at 8:32
  • 2
    \$\begingroup\$ As for the challenge, it would be helpful to provide a transcript of the order of the letters from the image. I personally like challenges to focus on their core, in this case calculating the score of a word, and to avoid additional tasks, like sorting a list and printing the top n entries, as those can distract from the main challenge. (E.g. in a language without a build-in sort method the challenging part could become implementing a sorting algorithm even though that's presumably not the intention of your challenge.) \$\endgroup\$ – Laikoni Jan 6 at 8:51
  • \$\begingroup\$ @Laikoni thank you for the reference! I am leaning towards [popularity-contest], but otherwise I guess I can settle for [code-golf]. \$\endgroup\$ – KlaymenDK Jan 8 at 9:11
  • 3
    \$\begingroup\$ popularity-contest challenges are very hard to get right, read e.g. here. I'd strongly advise you against using it, as it is not a good fit for this otherwise nice challenge. \$\endgroup\$ – Laikoni Jan 8 at 13:28
  • \$\begingroup\$ Is the word list common for all solutions or may the answerer choose their word list? \$\endgroup\$ – Neil A. Jan 10 at 1:28
  • \$\begingroup\$ I can restrict it to the Unix Words file if that helps. \$\endgroup\$ – KlaymenDK Jan 10 at 9:31
  • \$\begingroup\$ If not a [popularity-contest], then what's the best way to score this, given that I desire code readability (so not [code-golf])? \$\endgroup\$ – KlaymenDK Jan 10 at 9:32
  • \$\begingroup\$ Imo, the heart of the challenge is to determine the score of a word: I consider the rest as unnecessary, reading words from files has been done and will only make it difficult (or even impossible) for some languages, sorting with a custom function too, has been done. So I would extract the heart of this challenge and state it as Given a word, output its score. \$\endgroup\$ – ბიმო Jan 10 at 14:01
  • 2
    \$\begingroup\$ Now, since you don't want a code-golf, popularity-contest is not really the right thing, the challenge is not computationally hard (ruling out fastest-code or the like) that kind of leaves us with: atomic-code-golf or code-challenge. For the former one I don't see a sensible way to define the challenge which leaves us with the latter and gives rise to a start of a really interesting challenge: Make it a code-challenge where the scoring is according to the word's score ("cumbersome-ness"). The problem will be characters outside of that range: \$\endgroup\$ – ბიმო Jan 10 at 14:08
  • \$\begingroup\$ Ideas (for all I'm assuming case-insensitivity): 1) You extend the range to include @!…⅓ and exchange the character _ or the unreadable one after Z with a space. Then you'll only allow submissions using this extended range. [imo the most sensible, it does restrict the submissions heavily but in an interesting and sensible way so] 2) Before scoring the submission, remove all characters outside of the range. [people will abuse this and only use characters outside of that range] 3) Only XQ…Z are valid in a submission. [this is a really tight restriction for most languages] \$\endgroup\$ – ბიმო Jan 10 at 14:14
  • \$\begingroup\$ 4) Instead of ignoring characters outside that range, penalize them with a constant (kind of expensive, but not too expensive). \$\endgroup\$ – ბიმო Jan 10 at 14:21
  • \$\begingroup\$ @BMO, thanks a ton for your feedback! I'm not sure I follow (= I'm pretty sure I don't follow) your "ideas" comment. Could you explain further? \$\endgroup\$ – KlaymenDK Jan 10 at 15:28
  • \$\begingroup\$ If you go the route of code-challenge with score being the "cumbersomeness" of the code itself, it's not clear how you'll treat characters which aren't in the range XQ…Z and there would be need of a way to score these. The ideas (1-4) would be different options to define that. \$\endgroup\$ – ბიმო Jan 10 at 16:17
1
\$\begingroup\$

My Number is Bigger Than Yours: KoTH

The concept of this game is simple; each turn, two bots submit a positive integer (in Python, so no upper bound on its size). Whichever bot submits a larger number wins a certain number of points based on the scoring put forward in the next section. This process is iterated a certain number (100?) times to form the competition, with the bot which has the highest score winning the competition between the two bots.

However, scoring is based on some metric of the difference between the submitted values such that the larger the difference is, the smaller the amount of score gained is. I'm trying to decide some metric which heavily incentivizes making a guess which narrowly beats your opponent's guess, maybe with a metric such as 1/(a-b)**2. However, as the numbers will likely grow throughout the iterations, maybe 1/(a/b)**2 might be better.

Example bot whose goal is to beat opponents who pick a constant number:

def constant_beater(my_score, opp_score, my_numbers, opp_numbers):
    if len(opp_numbers) == 0:
        return 1
    return opp_numbers[-1] + 1

The largest concern I see with this challenge is a bot which just increments much quicker than all other bots so that it wins every game with a minuscule amount every time. Maybe to curb this a score that is below a certain threshold for a game is rounded to zero to encourage more competitive choices.

\$\endgroup\$
  • \$\begingroup\$ I feel like this would be a much better challenge if bounded a bit, from maybe 1-100 for example \$\endgroup\$ – Quintec Jan 11 at 22:57
  • \$\begingroup\$ I was thinking of some sort of bounding, but I'm struggling to then find an incentive for a bot to choose anything except for the upper bound. \$\endgroup\$ – Sebastian Jan 11 at 23:02
  • \$\begingroup\$ Make it a round robin tournament? \$\endgroup\$ – Quintec Jan 11 at 23:19
  • \$\begingroup\$ Numbers from 1 to 100. 100 rounds between 2 bots, higher number wins, can only play each of the 100 numbers 1 time each. Score is the number of rounds won? The play method doesn't work well for difference between numbers. \$\endgroup\$ – fəˈnɛtɪk Jan 13 at 1:43
  • \$\begingroup\$ This sounds extremely abusable, even more if they try to tap into the others' functions. However, it still sounds real fun, reminds me of the Robot Roulette but with much better winning chances. Maybe you could add some restriction like preventing to use the same number X amount of rounds with a maximum number cap (like @fəˈnɛtɪk said but without too much limiting) \$\endgroup\$ – Belhenix Jan 15 at 22:38
  • \$\begingroup\$ Maybe instead of a maximum number cap a maximum sum cap? \$\endgroup\$ – Sebastian Jan 16 at 21:44
  • \$\begingroup\$ If there's a maximum number cap I don't think there needs to be a maximum sum cap. However, there needs to be an incentive so bots don't go spamming the maximum number 24/7 (or worse, having 2 bots spam max number to infinity and ending in a 0 point tie) \$\endgroup\$ – Belhenix Jan 17 at 23:23
  • \$\begingroup\$ Thinking about this: Perhaps the max is 100, and bots score 100-guess if they win, and -(guess/100) if they lose? \$\endgroup\$ – Spitemaster Jan 31 at 22:20
1
\$\begingroup\$

Drawing \$K_n\$ (complete graph with \$n\$ vertices)

Tags: , ,


In graph theory the complete graph with \$n\$ vertices, often written as \$K_n\$, is the graph where every vertex is connected to every other vertex. For example, \$K_3\$ with \$V = \{A,B,C\}\$ has the edges \$\bigr\{\{A,B\},\{B,C\},\{C,A\}\bigl\}\$ - forming a triangle.

Challenge

Given an even \$n \geq 4\$ you will generate/display an image of the graph \$K_n\$ as follows:

  • pick an image width \$\texttt{width} \geq 100\$
  • pick two distinct colors \$\texttt{vertex_color}\$ and \$\texttt{edge_color}\$
  • draw \$1\$ vertex with color \$\texttt{vertex_color}\$ in the middle of the image
  • draw the remaining \$n-1\$ vertices evenly distributed on a circle around it
  • connect every vertex with color \$\texttt{edge_color}\$

Rules

  • the background color doesn't matter (transparent is fine), but it must not coincide with the colors \$\texttt{vertex_color}\$ and \$\texttt{edge_color}\$
  • the radius of the circle should be \$\texttt{width/4}\$
  • the center of the circle should the middle of the image
  • the shape of the vertices doesn't matter, but they must be at least \$3\$ pixels wide
  • the edges must not overlap the vertices
  • the edges may be dashed, dotted etc.

Examples

Example output for \$K_4\$:

K_4

Example output for \$K_{12}\$:

K_12

Example output for \$K_{32}\$:

K_32

\$\endgroup\$
  • \$\begingroup\$ "the edges must not overlap the vertices" is incompatible with "draw 1 vertex ... in the middle of the image" when n is odd. \$\endgroup\$ – Peter Taylor Jan 18 at 16:21
  • \$\begingroup\$ @PeterTaylor: Good call, thank you! Restricted the input to only even integers. \$\endgroup\$ – ბიმო Jan 18 at 16:48
  • \$\begingroup\$ a bit too many rules for me but... still very interesting and fun \$\endgroup\$ – don bright Jan 31 at 2:58
  • \$\begingroup\$ @donbright: What do you mean by too many rules? Since it's graphical output, I have to set rules otherwise it'll become an art contest unfortunately. I'm open to less restrictive suggestions though. \$\endgroup\$ – ბიმო Jan 31 at 14:46
  • \$\begingroup\$ its just my personal taste. like i dont care how wide the image is, how wide vertices are or whether edges overlap, etc etc. i upvoted anyways. good luck. \$\endgroup\$ – don bright Feb 2 at 2:55
1
\$\begingroup\$

Chain round the number!

A decimal place is a digit of a number's location in a number. In the number 987654321, each digit corresponds to its decimal place. For example, in the number 16111, the 6 is in the 4th decimal place.

Normally when rounding to n decimal places, one checks the digit at n-1 (heretofore called x). If x >= 5, then the digit at n is rounded up. Otherwise the digit at n is rounded down (stays the same). Then, all digits including and after x are turned into 0.

For example, take the number 158, rounded to the 3rd decimal place. The digit at the 2nd decimal place (3rd decimal place minus one) is 5. Because of this, the 1 at the third decimal place gets rounded up. This results in the number being 258. However, the 5 and the 8 both get turned into 0, and so the final result is 200.

Chain rounding is like normal rounding, except that you do it to every digit starting with the digit at decimal place 2. Once you round to the decimal place 2, then you round to decimal place 3, and so on until decimal place n.

For example:

Input: 24472
24472    (2 < 5, so the 7 rounds down)
24470    (7 >= 5, so the 4 rounds up)
24500    (5 >= 5, so the 4 rounds up)
25000    (5 >= 5, so the 2 rounds up)
30000    (Final answer. Non chain-rounded answer would be 20000)

The challenge here is to chain round a number to the highest decimal place possible for that number.

Test cases: (all inputs will be positive whole numbers)

24472 -> 30000
1999 -> 2000    ("1 9 9 9" -> "1 9 10 0" -> "1 10 0 0" -> "2 0 0 0")
9945 -> 10000
2001 -> 2000
9444 -> 9000
9445 -> 10000
13579 -> 10000
24681 -> 30000
1337 -> 1000
5 -> 10
1 -> 1
\$\endgroup\$
  • \$\begingroup\$ Good challenge, but I think this needs more explanation on what is happening. It's probably a good idea to fix an example with digits \$ab\$ and explain how the new rounding works (ie. compare \$b\$ to \$5\$ and so on), at first I did not understand where the \$5\$ comes from. You should also address how carries are treated, it's not clear atm. \$\endgroup\$ – ბიმო Jan 22 at 19:17
  • \$\begingroup\$ @BMO I tried to clarify, is that better? (Thank you for the help). \$\endgroup\$ – Comrade SparklePony Jan 22 at 19:56
  • \$\begingroup\$ Yes, looks good to me. Make sure to make a test-case with carries, eg. when rounding \$9996\$ or the like. And also specify whether numbers can be zero or even negative. \$\endgroup\$ – ბიმო Jan 22 at 20:15
1
\$\begingroup\$

A Turtle Finds a Portal

The turtle wants to move along the grid to get to his food. He wants to know how many moves it will take for him to get there.

As well since he is slow he has teleporters set up around his domain that he will utilize if it shortens his path. Or avoid them if it lengthens his path.

Meet the turtle

🐢

The turtle lives on a grid $$\begin{matrix} X&X&X&X&X\\ X&X&X&X&X\\ X&X&🐢&X&X\\ X&X&X&X&X\\ X&X&X&X&X\\ \end{matrix}$$ The turtle can move to any adjacent square... $$\begin{matrix} X&X&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&\leftarrow&🐢&\rightarrow&X\\ X&\swarrow&\downarrow&\searrow&X\\ X&X&X&X&X\\ \end{matrix}$$

However, the turtle cannot move to a square with a mountain $$\begin{matrix} X&🌄&X&X&X\\ X&\nwarrow&\uparrow&\nearrow&X\\ X&🌄&🐢&\rightarrow&X\\ X&🌄&\downarrow&\searrow&X\\ X&🌄&X&X&X\\ \end{matrix}$$

The turtle wants to eat his straw berry, and would like to know how long it will take to get to his strawberry $$\begin{matrix} X&🌄&🍓\\ 🐢&🌄&X\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ This example would take the turtle \$5\$ turns $$\begin{matrix} X&🌄&🍓\\ \downarrow&🌄&\uparrow\\ \searrow&🌄&\uparrow\\ X&\nearrow&X\\ \end{matrix}$$ To get around mountains the turtle uses his teleporter. There are two teleports on the grid that map to each other. Stepping on the teleporter immediately moves the turtle to the corresponding teleporter. $$\begin{matrix} 🔵&🌄&🍓\\ 🐢&🌄&🔴\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$ It is now faster for the turtle to move up twice. Now the turtles shortest path is \$2\$ $$\begin{matrix} 🔵&🌄&🐢\\ \uparrow&🌄&🔴\uparrow\\ X&🌄&X\\ X&X&X\\ \end{matrix}$$

The challenge

Given an initial grid configuration output the number of moves it will take the turtle to reach his strawberry.

Rules

  • You may assume that the input grid has a solution

  • The input grid may be entered in any convenient format

  • The shortest path does not need to make use of the portal

  • The turtle cannot pass into mountain tiles

  • The turn that the turtle moves onto a teleporter square he is already on the corresponding teleporter. He never moves onto a teleporter and stays there for a move

  • You may use any ASCII character to represent mountains, turtle, empty gird square, strawberry.

  • You may use either the same character or two different characters to represent the teleporter pairs

  • A grid can have more than one path with the same shortest path length

  • Each grid will only have one strawberry and two portals

  • This is .

Test Cases formatted as lists

[ ['T', 'X', 'X', 'S', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 3
[ ['T', 'M', 'X', 'S', 'X'], ['X', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'X', 'S', 'O'], ['O', 'M', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'] ] --> 2
[ ['T', 'M', 'X', 'S', 'X'], ['O', 'M', 'X', 'X', 'X'], ['O', 'X', 'X', 'X', 'X'] ] --> 4
[ ['T', 'M', 'S', 'X', 'O'], ['X', 'M', 'M', 'M', 'M'], ['X', 'X', 'X', 'X', 'O'] ] --> 7

Test Cases formatted for humans

T X X S X
X X X X X
X X X X X --> 3

T M X S X
X M X X X
O X X X O --> 4

T M X S O
O M X X X
X X X X X --> 2

T M X S X
O M X X X
O X X X X --> 4

T M S X O
X M M M M
X X X X O --> 7

Credits

Design and structure via: Hungry mouse by Arnauld

Proposed Challenges Edit Advice: Kamil-drakari, beefster

\$\endgroup\$
  • 1
    \$\begingroup\$ How many teleporters at most? \$\endgroup\$ – Quintec Jan 18 at 0:33
  • 1
    \$\begingroup\$ @Quintec Since they say pairs, then... only two at most, because there's no way to represent multiple pairs \$\endgroup\$ – ASCII-only Jan 18 at 3:28
  • \$\begingroup\$ @Quintec. Yea one at most. I'll add to the rules. \$\endgroup\$ – akozi Jan 18 at 10:13
  • 1
    \$\begingroup\$ You should clarify how diagonal moves work near mountains. The first diagram showing the basic movement options includes diagonal moves, but the example with the strawberry would only be two moves regardless of portals if a diagonal move was used. \$\endgroup\$ – Kamil Drakari Jan 18 at 19:29
  • \$\begingroup\$ @kmail. Very true. Will add condition when on computer. \$\endgroup\$ – akozi Jan 19 at 15:16
  • 1
    \$\begingroup\$ I would suggest taking the "gun" out of the title because "portal gun" suggests being able to place your own portals. I would also allow input to be in any convenient format rather than requiring it to be a list of lists with a predefined key. I think for your examples, you should use space and newline separated grids. And one last thing: rather than "The grid must have a possible solution to reach the strawberry", you should state "You may assume that the input grid has a solution". Good challenge though. Just a couple tweaks will make it a great challenge. \$\endgroup\$ – Beefster Jan 24 at 17:46
  • 1
    \$\begingroup\$ I would like a testcase where the portal is in the way of the turtle, meaning that the turtle has to use the portal twice. Something like "TOSMO","MMMMX", "XXXXX" or "TOSXX", "MMMMX", "OXXXX" (both evaluate to 4 moves) \$\endgroup\$ – Black Owl Kai Feb 3 at 20:50
  • \$\begingroup\$ @BlackOwlKai I'm considering making portals single use? Thoughts? \$\endgroup\$ – akozi Feb 3 at 21:31
  • \$\begingroup\$ This is also an option and could allow some more interesting golf approaches. Also, the single-use option would make brute-force algorithms more lengthy, because they need to keep track of whether the portal has been used. Either way, it should be clarified in the rules. But I still would like to add a testcase "XXXMO", "XMXMX", "XOXMX", TMSMX", where the portal is between the turtle and the strawberry, even if portals are single-use. \$\endgroup\$ – Black Owl Kai Feb 3 at 21:53
  • \$\begingroup\$ Will do. I'll add this to rules aftter I get off my bus ride. As I won't have internet to edit. Cheers, Thanks for the suggestion. \$\endgroup\$ – akozi Feb 3 at 22:36
  • \$\begingroup\$ Support for the emoticons is not guaranteed, and they aren't in the fonts on my Linux system. IMO an image would be preferable. \$\endgroup\$ – Peter Taylor Feb 4 at 14:36
  • \$\begingroup\$ @PeterTaylor Will do. I'll do this once home from work. If you want to try doing it now I would approve the edit. Cheers. \$\endgroup\$ – akozi Feb 4 at 14:52
  • \$\begingroup\$ You have a typo on rule 6: "empty gird square" should be "empty grid square". Also, why does it need to be an ASCII character value? Why can't I use an int? \$\endgroup\$ – Beefster Feb 4 at 17:33
  • \$\begingroup\$ Will fix the spelling. As far as I'm aware integers are ascii characters? \$\endgroup\$ – akozi Feb 4 at 17:37
  • \$\begingroup\$ @Beefster I'll specify in the post though. \$\endgroup\$ – akozi Feb 4 at 17:38
1
\$\begingroup\$

Playing Pickomino

\$\endgroup\$
  • \$\begingroup\$ A worked example or 2 would be useful; I missed, on my first readthrough, that we must take the highest available tile <= the score rather than any tile <= the score and was therefore confused by a couple of the test cases. Although, I'm still confused by the 3rd last one - either the output is wrong or (more likely!) I'm too tired/drunk to figure it out. Nice challenge, though :) \$\endgroup\$ – Shaggy Feb 1 at 1:18
1
\$\begingroup\$

SLIPpery Packets

The Serial Line Internet Protocol is an early internet protocol, used to essentially escape any "packet END" bytes that may appear in a packet. It has since been replaced by the more sophisticated Point-to-Point protocol, however it is still preferred on microcontrollers and low-level devices due to its simplicity.

Your goal is to implement simplified encoding and decoding functions following this protocol as a function/program/subroutine/etc.

The following table lists the special bytes used:

Hex    Dec   ISO 8859-1   Abbrev  
0xC0   192   À            END      
0XDB   219   Û            ESC
0xDC   220   Ü            ESC_END
0xDD   221   Ý            ESC_ESC

(The ISO 8859-1 characters are for visualizing where non-ASCII bytes are in the string.)

Encoding follows this system, iterating through each byte:

  • If the END byte appears in the packet, write ESC, ESC_END instead
  • If the ESC byte appears in the packet, write ESC, ESC_ESC instead
  • Otherwise, write byte verbatim
  • At the end, an END byte is appended to the message, and it is returned

Some implementations, such as the reference C implementation from RFC 1055, prepend an END byte to the string to be sent. This is omitted here for simplicity.

Decoding follows in reverse:

  • If ESC, ESC_END appears in the packet, write END instead
  • If ESC, ESC_ESC appears in the packet, write ESC instead
  • Protocol violations that involve ESC followed by a "bad byte" that isn't ESC_END or ESC_ESC should be handled by writing the "bad byte"
  • The first END byte seen (not following ESC) is interpreted as the end of the packet. The decoded packet should be returned without the END byte. You are guaranteed to have at least one such END byte appear.

Input/Output

For encoding, input is a packet (string of bytes) and output is the encoded packet (string of bytes).

For decoding, input is a "byte stream" (string of bytes) and output is the (first) decoded packet (string of bytes).

Test cases

Inputs

''                --> 'À'
'test\n'          --> 'test\nÀ'
'testÀ'           --> 'testÛÜÀ'
'teÛst'           --> 'teÛÝstÀ'
'À'               --> 'ÛÜÀ'
'ÛÜÛÝÀÛ'          --> 'ÛÝÜÛÝÝÛÜÛÝÀ'

Outputs

'À'               --> ''
'testÀblah blahÀ' --> 'test'
'teÛÝstÀ'         --> 'teÛst'
'testÛÜÛÜÀ'       --> 'testÀÀ'
'ÛÝÜÛÝÝÛÜÛÝÀ'     --> 'ÛÜÛÝÀÛ'
'ÛÀÀ'             --> 'À'
'ÛµÀ¶'            --> 'µ'

Scoring

Your score is the sum of the number of bytes in your encoding and decoding functions (or programs, etc.)


I have also considered requiring functions to take a length of packet in bytes which is used in encoding and decoding (similar to RFC 1055), not requiring handling protocol violations (ex. RFC 1055), and not testing decoding packets that have an END byte as not the last byte. Your opinions on how restrictive this challenge should be are appreciated.

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

One circle, two inputs, eight outputs

Given the values of only two quantities from the following eight quantities ​​(the rest is unknown):

  1. Radius of circle: \$\displaystyle R\$
  2. Diameter of the circle: \$\displaystyle D=2\times R\$
  3. Circumference of the sector: \$\displaystyle C=2\times\pi\times R=\pi\times D\$
  4. Area of the circle: \$\displaystyle A=\pi\times R^2\$
  5. Angle of the sector: \$\displaystyle\alpha\$
  6. Length of arc: \$\displaystyle LA=\frac{C\times \alpha}{360°}\$
  7. Area of the sector: \$\displaystyle AS=\frac{A\times \alpha}{360°}\$
  8. Perimeter of the sector: \$\displaystyle PS=LA+2\times R=LA+D\$

compute the rest of quantities if possible, else put special output (-1, False,...) if at least one of the quantities can not be computed.

Input

Two quantities with there values (non negative integers)

Output

The values of the eight previous quantities (decimal with any precision or rounded integer).

Example

In this example the inputs is the ordered list of the previous quantities. Values are integers, angles in degrees, and outputs as rounded integers.

[16, ?, ?, ?, 100, ?, ?, ?]   --> [16, 32, 100, 804, 100, 27, 223, 59]
[24, ?, ?, ?, ?, ?, ?, 58]    --> [24, 48, 150, 1809, 23, 10, 120, 58]
[28, ?, ?, ?, ?, ?, ?, 188]   --> [28, 56, 175, 2463, 270, 132, 1848, 188]
[?, 18, ?, ?, ?, ?, ?, 41]    --> [9, 18, 56, 254, 146, 23, 103, 41]
[?, 28, ?, ?, ?, ?, ?, 808]   --> [14, 28, 87, 615, 3191, 780, 5460, 808]
[?, 88, 220, ?, ?, ?, ?, ?]   --> False
[?, ?, 88, ?, ?, 84, ?, ?]    --> [14, 28, 88, 616, 343, 84, 588, 112]
[?, ?, 220, ?, ?, 66, ?, ?]   --> [35, 70, 220, 3851, 108, 66, 1155, 136]
[?, ?, ?, 50, 50, ?, ?, ?]    --> [3, 7, 25, 50, 50, 3, 6, 11]
[?, ?, ?, 254, ?, ?, 18, ?]   --> [8, 17, 56, 254, 25, 4, 18, 21]
[?, ?, ?, 707, 75, ?, ?, ?]   --> [15, 30, 94, 707, 75, 19, 147, 49]
[?, ?, ?, ?, 99, 24, ?, ?]    --> [13, 27, 87, 606, 99, 24, 166, 51]
[?, ?, ?, ?, 140, ?, 175, ?]  --> [11, 23, 75, 450, 140, 29, 175, 53]
[?, ?, ?, ?, 324, 85, ?, ?]   --> [15, 30, 94, 709, 324, 85, 638, 115]
[?, ?, ?, ?, 324, ?, 3465, ?] --> [35, 70, 219, 3850, 324, 197, 3465, 267]
[?, ?, ?, ?, ?, 66, 88, ?]    --> False

Rules

  • The input and output can be given in any convenient format.
  • Specify in the answer the special output when quantities can not be computed all.
  • Specify in the answer whether the angle is in degree or radian or other unit.
  • π can be set to 3.14 or 22/7 or 355/113 or any more precise value.
  • No need to handle invalid input values.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
1
\$\begingroup\$

Gregorian-Hijri(Islamic) Calendar Conversion

Introduction

The Hijri, or Islamic calendar is a lunar calendar used in the Islamic countries to determine the dates of traditional events. The year in the Hijri calendar is usually denoted AH xxxx. The Hijri calendar has an epoch on 16 July 622 on Julian calendar.

Like other lunar calendars, in the Hijri calendar a year consists of 12 months, each month consists of 29 or 30 days. A year is thus 354 days, or in leap years there are 355. On average there are 11 leap years every 30 years.

There is a tabular variant which uses arithmetic calculations in place of astronomical observations to determine the dates. There is also a solar version of the Hijri calendar, which is used in Iran and Afghanistan.

In this challenge, only the tabular variant will be discussed.

The tabular Hijri calendar

All western dates below will be shown in (possibly proleptic) Gregorian even if the date is before 15 October 1582.

There are 12 months in each year in the Hijri calendar, with alternating 29- or 30-day periods. The odd months have 30 days, and the even months have 29 days (except for the 12th month Dhu al-Hijjah in leap years which also has 30 days). The month names are as follows (according to this Wikipedia template):

#    Name              Number of days
1    Muharram          30
2    Safar             29
3    Rabi' al-awwal    30
4    Rabi' al-Thani    29
5    Jumada al-awwal   30
6    Jumada al-Thani   29
7    Rajab             30
8    Sha'ban           29
9    Ramadan           30
10   Shawwal           29
11   Dhu al-Qidah      30
12   Dhu al-Hijjah     29 / 30 (in leap years only)

There are 11 leap years every 30 years. There are 3 versions to determine the leap years, but the most common version is to set the years with \$y\in\{2,5,7,10,13,16,18,21,24,26,29\}(\text{mod }30)\$ as leap years. (Be reminded that the calendar stars from year 1.)

The Hijri calendar has its first day (i.e. 1 Muharram 1) on 19 July 622.

As an example, we now convert the date 8 February 2019 into Hijri (Here we define a cycle to be 30 years):

  1. Date: 8 February 2019
  2. Dates from the Epoch: \$1396 \times 365 + 339 + 166 + 38 = 510083\$
    • There are 1396 (\$2019 - 623\$) full years, so \$1396 \times 365\$ days
    • There are 339 (\$349 - 14 + 4\$) leap years between 2 dates
    • There are 166 days between 19 June 622 to 1 January 623, and 38 days between 1 January 2019 to 8 February 2019
  3. Cycle: \$510083 \div 10631 = 47\text{ (cycles) and }10426\text{ (days)}\$
    • One ordinary year is 354 days and there are 11 leap years in a 30-year cycle, so total days in a cycle is \$354\frac{11}{30} \times 30 = 10631\$
  4. \$10427 - (354 \times 29 + 11) = 150\$, so this this is the 150th day of the 30th year in the 48th cycle, which is \$47 \times 30 + 30 = \text{(AH) }1440\$.
    • The subtraction has 18 \$354\$s and 11 \$355\$s, but there is not enough space to write it all.
  5. \$150 - 30 - 29 - 30 - 29 - 30 = 2\$, so this is the 2nd day of the 6th month in the year AH 1440.

As a result the complete Hijri date of 8 February 2019 is 2 Jumada al-Thani 1440.

Challenge

Write a program or function that converts the (Gregorian) input date into the corresponding Hijri date.

The program or function may receive the input date in any reasonable format, but it must output the Hijri date in the format of [date] [month name] [year]. The italics above shall be ignored.

The input month and day may be 0-indexed for convenience, but you must state so if you use this convention.

You may assume that the input is always a valid Gregorian date, and is always not earlier than the Gregorian epoch of the calendar, 19 July 622.

Sample I/O

Input:  "19 July 622" / "622-7-19" / [622, 7, 19] / (622, 6, 19) (0-indexed month)
Output: "1 Muharram 1" (The epoch date)

Input:  "8 February 2019" / "2019-2-8" / [2019, 2, 8] / (2019, 1, 8) (0-indexed month)
Output: "2 Jumada al-Thani 1440" (The example date)

Input:  "12 August 2019" / "2019-8-12" / [2019, 8, 12] / (2019, 7, 12) (0-indexed month)
Output: "10 Dhu al-Hijjah 1440" (The start date of Eid ul-Adha in AH 1440)

Input:  "9 August 2021" / "2021-8-9" / [2021, 8, 9] / (2021, 7, 9) (0-indexed month)
Output: "30 Dhu al-Hijjah 1442" (The next leap day)

Winning Criteria

As this is a , shortest answer of each language wins. Standard loopholes are banned by default.

\$\endgroup\$
  • \$\begingroup\$ What is "47 R 10426"? \$\endgroup\$ – Adám Feb 8 at 8:16
  • \$\begingroup\$ @Adám The quotient is 47, with remainder 10426. When I was in primary school I was taught like 5/3 = 1...2 and heard in western countries it'd be written as 5/3 = 1 R2 \$\endgroup\$ – Shieru Asakoto Feb 8 at 8:17
  • 2
    \$\begingroup\$ This starts off really well, explicitly addressing the usual ambiguities with Gregorian calendar-related questions and the particular complications of the Islamic calendar. But for me it starts to fall apart at the example, which has a lot of unexplained magic numbers and introduces new terms like cycle. I suggest that you should take the example slower: which number in step 2 is the number of leap days? Define a cycle as (I assume) 30 Iunar years. \$\endgroup\$ – Peter Taylor Feb 8 at 21:34
  • \$\begingroup\$ I also suggest that you reconsider the requirement to output month names. That really makes it two barely related challenges (a calendar conversion and a kolmogorov-complexity for an array of 12 strings) packaged as one. \$\endgroup\$ – Peter Taylor Feb 8 at 21:35
1
\$\begingroup\$

Unique Skittle Pairs

This is my first question, so hopefully it's OK.

I like to eat Skittles. However, I only like to eat them in pairs, and and those pairs must not have two Skittles of the same color. Your task is to find the most pairs that you can that match these requirements.

Challenge

Input (taken from standard input) is a set of Skittles formatted like so: pyyyggoooorr, where p is purple, y is yellow, g is green, o is orange, and r is red. The number of letters for each color corresponds to the number of Skittles that are that color. The only colors used in this challenge are purple, yellow, green, orange, and red. The input will always be even in length and lowercase.

Output is the most possible pairs of Skittles that I like to eat given the input. Different outputs don't matter as long as they are valid, i.e. for an input of pygo, both py go and po gy are valid outputs. Output for invalid input doesn't matter.

The output must be in the same format as the test cases.

Examples/Test Cases

Permutations of these solutions are valid. You do not have to output all valid outputs. Multiple output lines here means multiple valid outputs.

> ppyy
py py

> yggooo
yo go go

> pyygorrr
pr yr yg or
py yr gr or

> yggoor
yg go or
yo go gr
go go yr

> yggor
(anything, including no output/errors)

> gygoro
yg go or
yo go gr
go go yr

> ygoOor
(anything, including no output/errors)

> ggorrrrr
gr gr or

> pppyyygggooorrrr
py py py ro ro ro rg
po po po ry ry ry rg
py po py ro ry ro rg
etc.

Least bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I'd forgotten about that. \$\endgroup\$ – CG One Handed Feb 27 at 19:16
  • \$\begingroup\$ I believe this is a dupe. The only differences are the slightly more inconvenient input/output of this challenge and the different group size. However, forcing the output to be the actual pairs prevents using the most dominant strategy of simply calculating the number of groups. Personally I think they are too close anyway, but some people may disagree. \$\endgroup\$ – FryAmTheEggman Mar 1 at 20:14
1
\$\begingroup\$

Sort according to cyclic order

Cyclic order on a set is a function f taking three distinct elements of a set, returning bool and having following properties:

  1. If f(a, b, c) then f(b, c, a)
  2. If f(a, b, c) then not f(c, b, a)
  3. If f(a, b, c) and f(a, c, d) then f(a, b, d)
  4. One of f(a, b, c) and f(c, b, a) is true

Values of f when arguments are not distinct don't matter. You are given a list of dictinct numbers and a function f posessing the above properties when arguments are taken from the list. Your task is to arrange the numbers in such an odrer that

f(a, b, c) if and only if k > j > i or i > k > j or j > i > k

(i.e. numbers a, b, c come in that order modulo cyclic permutaion)

Score is the total number of calls to the function f on some dataset.

It's not very clear to me how to create the dataset and how to count calls to f across different languages. Is it better to just give a list of n*(n-1)*(n-2) values of f as input (and score by bytes)?

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi and welcome to PPCG. Thank you for using the Sandbox. Please don't specify a challenge using a specific (and unstated) programming language, as many people will have a hard time understanding that. At the very least, explain the notation. \$\endgroup\$ – Adám Mar 5 at 23:49
  • \$\begingroup\$ @Adám Thank you for your comment. I've removed all language-specific notation \$\endgroup\$ – Nikita Mar 6 at 0:09
  • \$\begingroup\$ Is 4. OR or XOR? \$\endgroup\$ – Adám Mar 6 at 5:51
  • \$\begingroup\$ @Adam 2. says that one of f(a, b, c) and f(c, b, a) is false, 4. says that one is true. Maybe it would be best to combine them into just 2. Exactly one of f(a, b, c) and f(c, b, a) is true \$\endgroup\$ – Nikita Mar 6 at 20:49
  • \$\begingroup\$ Neat challenge idea. For the scoring, maybe you can ask for the expected number of calls to f on a random n-element set. It should be easy to Monte Carlo simulate scores, as long as they're different enough. One issue is that people can pick an element e and then only do queries of the form f(e,x,y), to reduce this to a standard sorting problem. \$\endgroup\$ – Lopsy Apr 2 at 20:31
1
\$\begingroup\$

Data.List.nub :: Eq a => [a] -> [a]

Tags: , ,


O(n^2). The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means `essence'.) It is a special case of nubBy, which allows the programmer to supply their own equality test.

> nub [1,2,3,4,3,2,1,2,4,3,5]
[1,2,3,4,5]

Goal

If you ever golfed in Haskell and you kind of needed to deduplicate a list, chances are that you chose a different route or were annoyed that there seems to be no solution shorter than importing Data.List.

In this challenge you will write a function [a] -> [a] (unnamed or named) which removes duplicates from a list, the order does not have to be preserved.

Scoring

Since I don't think it's possible to get something shorter than 20 bytes and Haskell sometimes is really annoying to golf with if you want to use lengthy functions, the scoring mechanism will count tokens, please use this program to count the tokens and use the generated template.

  • If your solution is a named function or operator, it must not be defined in another file/module (ie. banning imports).

  • Each solution may impose type constraints, each set of type constraints counts as its own language, compiler flags can be used without any restrictions.

  • Your solution may not assume that the input is non-empty, however if you have an elegant solution which fails on empty input, feel free to include it in your post.

How are tokens counted?

Tokens are counted by using GHC's lexer which you can import Language.Haskell.Extes.Lexer, except that newlines will count as a token too.

White space is ignored, every token of the language will count as one, no matter how long it is so ma >>= f will count as the three tokens ma, >>= and f the same holds true for string or number literals (eg. "abc" or 1.0 each count as 1).

Test cases

[] -> []
[1] -> [1]
[1,1,1] -> [1]
[3,1,1,2] -> [1,2,3]
[1,2,3,3,2,1] -> [1,2,3]
\$\endgroup\$
  • 1
    \$\begingroup\$ I think I'm missing something, but what stops the import Data.List;nub solution from winning with score 4? \$\endgroup\$ – xnor Mar 16 at 1:26
  • 1
    \$\begingroup\$ @xnor: No you didn't, my bad. Fixed, I hope. \$\endgroup\$ – ბიმო Mar 16 at 2:49
  • 2
    \$\begingroup\$ Hmm, this way it's still no good. Using nubBy (==) is still going to be hard to beat. Guess I need to ban imports completely :( \$\endgroup\$ – ბიმო Mar 16 at 2:53
  • 1
    \$\begingroup\$ Yeah, I think banning imports is the way to go. I know past token-counting challenges have had "exploits" where the code payload is put into a huge string or number payload, the decompressed and executed by a general-purpose program. I don't see offhand a good way to do that in Haskell without imports though -- do you? \$\endgroup\$ – xnor Mar 16 at 3:03
  • \$\begingroup\$ I tried writing a solution and the best general-type solution I got is the same as the one I'd use for golfing with imports banned, with 17 tokens. I'm unfortunately not seeing a way to take advantage of long built-ins like the scoring encourages. I see a shorter approach for a restricted type that feels both optimal and hard-to-improve to me. If you don't have some clever better method up your sleeve, I'd suggest a more complex task. Nice token-counting script by way, the number labelling makes it very clear. \$\endgroup\$ – xnor Mar 16 at 3:36
  • \$\begingroup\$ @xnor: Without imports one could still embed an interpreter, I guess. I was thinking earlier about this and I think there's nothing wrong with counting literals as multiple tokens. However yeah, probably it's best to come up with a more complex task. Thanks for your feedback. \$\endgroup\$ – ბიმო Mar 16 at 3:59
  • \$\begingroup\$ I don't really see how counting tokens is too much better, and it makes the challenge language specific. \$\endgroup\$ – dfeuer Mar 19 at 22:26
1
\$\begingroup\$

Challenge

Create a function takes in two 2-dimensional arrays of Characters (or Strings if the programming language does not have characters as a datatype) as inputs: a and b.

Your task is to determine if b contains a. If this is so, return true. Otherwise, return false.

Sample Test Cases

a:

123
456
789

b:

123
456
789

should return true.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

should return true.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

should return false.

Least bytes wins.

\$\endgroup\$
  • \$\begingroup\$ does the block need to be as-is? No lines inbetween? No characters? i.e. does code\golf appear in `code!!\trucking!!\golf!!`? \$\endgroup\$ – Ven Mar 25 at 11:04
1
\$\begingroup\$

When should Mario work?

Challenge

Given a list of not_working_days, a period of time (date to date), and a days_I_must_work calculate the days that Mario should work in order to make the biggest amount of money.

Explanation

You might be wondering what do I refer when I said make the biggest amount of money. Mario works for this super weird company. The company likes to increase Marios' daily salary in \$\lceil50\%\rceil\$ every time he attends consecutively. That means, If Mario daily salary is \$$2\$ on Monday, on Tuesday he will earn \$$3\$, Wednesday \$$5\$, Thursday \$$8\$ and Friday \$$12\$. That sounds awesome. Sadly, what easy comes, easy goes, and every time he misses work, the company decreases Marios' daily salary in \$\lfloor-50\%\rfloor\$ (half of the salary rounded up is left over). In addition to that, if he misses work consecutively, the company stacks the \$-50\%\$ malus to his daily salary.

Example. Lets assume Mario worked from Monday to Friday but he misses Wednesday.

  • Monday = \$$2\$
  • Tuesday = \$$3\$$
  • Wednesday = \$$0\$ (he did not work)
  • Thursday = \$$2\$ (Instead of a \$+50\%\$ he got a \$-50\%\$)
  • Friday = \$$3\$.

At the end Mario got \$$10\$ in the whole week. Lets do the same example but in this case he missed Tuesday and Wednesday.

  • Monday = \$$2\$
  • Tuesday = \$$0\$ (he did not work)
  • Wednesday = \$$0\$ (he did not work)
  • Thursday = \$$1\$ (He got a \$\lfloor-50\%\rfloor\$ reduction (\$$1\$) and another \$\lfloor-50\%\rfloor\$ reduction (\$$1 - (\lfloor$1*0.50\rfloor)=$1-\lfloor$0.5\rfloor = $1-$0 = $1\$))
  • Friday = \$$2\$.

In this case he only made \$$\$5. But even missing work 2 days he can make more than last example.

  • Monday = \$$2 \$
  • Tuesday = \$$3 \$
  • Wednesday = \$$5 \$
  • Thursday = \$$0\$ (he did not work)
  • Friday = \$$0\$ (he did not work)

This time he made \$$10\$, more than last time he only worked 3 days


Now, Given the amount of days Mario have to work (days_I_must_work), a date range representing the dates that Mario may work (date to date) and a special list not_working_days containing the days (YYYY-MM-DD) that Mario must not work, output the date range in which Mario would make the biggest amount of money.

Note:

  • By law, Mario can not work Sundays but the company doesn't care and reduces -50% anyway.
  • Mario initial daily salary always going to be \$$2\$

Rules

  • You can take the input in any order you want as long as is a valid input
  • You may take and output the dates in any format
  • Assume there wont be any leap year and all dates will be in the range [2019-01-01, 2019-12-31]
  • This is

Test Cases: WIP

\$\endgroup\$
  • 2
    \$\begingroup\$ I think the date parsing adds very little to this challenge: why not make the dates just be integers? Otherwise, I think the only thing to clear up is that when not working the salary is halved and then rounded up. The current wording sounds a bit like "half of the salary rounded up is removed" vs "half of the salary rounded up is left over". \$\endgroup\$ – FryAmTheEggman Mar 22 at 22:15
  • \$\begingroup\$ @FryAmTheEggman You may take and output the dates in any format So you can take the dates as integers if you need so \$\endgroup\$ – Luis felipe De jesus Munoz Mar 29 at 13:55
  • \$\begingroup\$ You may want to change the earlier part that lists a date format (i.e. the YYYY-MM_DD) then, since I definitely would not have expected that. To save people some Googling you also may want to point out that the first day of 2019 was a Tuesday. \$\endgroup\$ – FryAmTheEggman Mar 29 at 18:53
1
\$\begingroup\$

Fix Brain-Flak push-pop redundancy

I may need more/better test cases. Also, this is my first challenge and I'm not entirely sure what I'm doing.

Brain-Flak is a stack-based esoteric language with eight commands:

()     Evaluates to 1
<>     Switch active stack; evaluates to 0
[]     Evaluates to height of current stack
{}     Pop current stack; evaluates to the popped number
(...)  Execute block and push the result; evaluates as result
<...>  Execute block; evaluates as 0
[...]  Execute block; evaluates as negation of result 
{...}  While top of active stack is nonzero, execute block

Write a program or function to detect and remove one common type of push-pop redundancy that often occurs when writing Brain-Flak code.

To determine whether a push and pop are truly redundant, we must understand which scopes use the return value of instructions:

  • The return value of any top-level instruction is ignored.
  • (...) will always use the return values of its children.
  • <...> will always ignore the top-level instruction of its children.
  • {...} will pass the return values of its children to the enclosing scope; that is, their return values will be used if and only if {...} itself is in a scope that uses its return value.
  • [...] theoretically works like {...} in this sense; however, you may assume that [...] is always in a scope that cares about return value, thus treating it like (...).

The type of redundancy we are interested in occurs in any substring of the form (A)B{} satisfying the following:

  • A is a balanced string; that is, the parentheses around A are matched.
  • (A) is in a scope that ignores its return value.
  • B does not contain [], <>, or either half of the {...} monad.
  • The {} immediately following B pops the value pushed by (A). That is, B has an equal number of {} and ...), and no prefix of B has more {} than ...).

Note that B is typically not a balanced string.

To remove this redundancy, we temporarily introduce a symbol 0 to the language, which evaluates to 0. With this symbol, a redundant string (A)B{} can be safely replaced by 0BA. Since Brain-Flak does not have a 0 symbol, we must make simplifications to remove it.

  • A 0 with a sibling can be removed entirely. (Note that if there are two 0s as the only children of a monad, only one of them can be removed.)
  • [0] and <0> can be simplified to 0.
  • If you encounter a (0), find the matching {}; replace both (0) and that {} with 0s.
  • {0} will never happen. If I'm wrong about this, you may have undefined behavior in this case.

Rules

  • Input is a string taken by any reasonable method.
  • Input is guaranteed to be valid Brain-Flak code consisting only of brackets.
  • Any [...] monads in the input will be in scopes that do not ignore their return values.
  • Input can be empty, in which case it clearly does not contain redundancy of any kind.
  • Output is a functionally equivalent block of Brain-Flak code without any redundancy of this type.
  • If your solution is in Brain-Flak, it should hopefully not detect any redundancy in its own code.
  • This is , so the shortest program (in bytes) in each language wins.

Test cases

With redundancy (with redundant push and pop marked):

Shortest redundancy
({}){} -> {}
^  ^^^

First example
({}<>)({}()) -> ({}<>())
^    ^ ^^

Second example
({}<({}<>)><>)(<((()()()){}[((){}{})])>) -> (<((()()()){}[((){}<({}<>)><>{})])>)
^            ^                 ^^

Inside the zero monad
({}<({}{})>{}) -> ({}({}{}))
    ^    ^ ^^

Inside a loop
{({}{})([{}])} -> {([{}{}])}
 ^    ^  ^^

Two redundancies
({}<({}{})>)({}{}) -> ({}{}{})
^   ^    ^ ^ ^^^^

No redundancy (output should be the same as input):

-empty string-
(({}<>)({}()))         - unlike the second test case, the pushed value is used again
(({}){})               - standard code for doubling the top value on the stack
({}{})<>{}             - push and pop not on same stack
(()){{}{}}             - loop starts between push and pop
({(({}[()]))}{})([]{}) - stack height is used after push
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe in your redundant examples, show which part is redundant, and what it could minify to? \$\endgroup\$ – DJMcMayhem Apr 1 at 4:24
  • \$\begingroup\$ Why not have the output as the input with the redundancies removed? \$\endgroup\$ – Jo King Apr 8 at 6:32
  • \$\begingroup\$ @JoKing I wasn't sure if that would make the challenge too complicated. I'll edit in a version describing how to remove these redundancies. \$\endgroup\$ – Nitrodon Apr 8 at 16:04
1
\$\begingroup\$

Rando Expo Stringo Combo

(Sandbox: Essentially, let's sandbox a sensible version of the 'to string or not to string' kerfuffle, with added formulae.)

This challenge is code golf but with possible tradeoffs of capability vs byte count - better solutions get a higher score, but worse solutions can still compete if they are short enough.

Le challenge

Given an input of characters (or whatever), return a string (or whatever) constructed of a random combination of a subset of the characters in the string. I'll accept continuations, lambdas, whatever you can print or call without arguments.

I would heartily encourage solutions using obscure areas of Unicode because they look more fun. You must specify the valid input domain.

Standard loophole elimination applies.

How long may that input be? And what kind of inputs?

Well, as long as you like, up to a maximum of 32 characters/elements.

Le scoring

Ah, just to annoy you, we'll go for a formula:

S = orderedScore * (log_2(domainSize) + log_2(uniqueCombos)) / (solutionLengthBytes + 1)

Where * orderedScore is 2 for an ordered input/output type and 1 for an unordered one * domainSize is the count of possible values for each element, maximum 65536. If you can only take sorted input or your domain is only 1 value (strings of 'a'), you just get 1. If you can do 7-bit ASCII, it's 128. If you use null-terminated ASCII strings, it's 127... * uniqueCombos is the count of unique combinations of the input elements which your program can produce for the maximum input it can handle.

So a 1 byte solution which can return all possible combinations of an ordered input for a 32 length unique input, which can accept inputs in the 7-bit ASCII characters, nets you a score of 2 * (7 + 32) / 1 = 78. A Java solution (bite me) using sets will net you more like 1*27/500 -> 0.054...

If you can only cope with the letter 'a' but it can be whatever length, you get uniqueCombos = 32. If you just return the first m characters then again it is 32.

The maximum score is 2 * (log_2(2^16) + log_2(2^32)) / (0 + 1) = 96.

If write a 1 byte answer which can only accept strings of 'a' and you just return 'a' every time, that's technically valid but will score

You must provide an example of a maximal case for reference, along with the aforementioned spec of the domain.

Maximum score wins.

FAQ

  1. Must we cope with blank? No, the set of input characters/values is up to you, but I won't make you cope with a zero length input.

  2. Must we sample fairly No, but the unique count is for all the possible results. If it isn't possible, it doesn't count.

  3. Must we cope with non-unique inputs Yes most definitely.

  4. Does that mean we can't input sets Not if that would prevent non-unique inputs, so lists of sets could work, I guess?

  5. When you say combinations, do you mean permutations? I mean sets-with-counts, so 'aaab' and 'aaba' count for 1, not 2, but 'aab' and 'ab' are different.

  6. Can I output as Vulcan hand signals Your input and output types must match. Strings in, strings out. Lists of numbers input, so output.

Will the input be sorted for ordered inputs?

No. If you require sorted inputs, it counts as unordered input (half score).

Examples

input -> valid results if we sort them:

'' -> ''
'a' -> 'a'
'ab' -> 'a', 'b', 'ab' 
'aab' -> 'a', 'b', 'aa', 'ab', 'aab' 
'aba' -> 'a', 'b', 'aa', 'ab', 'aab'

As numbers

(2,100,2) -> (2),(100),(2,2),(2,100)

etc

Sandbox questions:

  1. Is the scoring too opaque? I was aiming to make it possible for a tradeoff between solution length and function, and also to permit higher level languages to compete with some of the golfing languages.

  2. I had hoped to score higher for evenly distributing combinations, but I can't see a sensible way of measuring it. One temptation was to sample the results for some number of input scaling with the input length, but my head.

  3. Is there a too-simple winning case? If a golfing language just returned the input string (i.e. zero bytes), and could handle numbers to 65k, that would count as 2 * 16 / 1 = 32... is it too hard to beat that?

\$\endgroup\$
  • \$\begingroup\$ I had a hard time understanding what this challenge was about. I don't think your explanation of combinations or your examples do a particularly good job of specifying what you want. I think you should strongly consider finding someone to go over this in person, since I think there's too much to be tackled by just the sandbox. Separately, your scoring system does seem rather poor, since to get a score of 32 after the rest was maximised your code could be no longer than 2 bytes, if I haven't made an error. (That said if I understand correctly many golfing languages could solve this in 2 bytes) \$\endgroup\$ – FryAmTheEggman Apr 15 at 19:27
1
\$\begingroup\$

Ragtag Band of Misfits

(Guaging interest)

This is a sort of sequel to Adventurers in the Ruins, taking place in a 2D dungeon, using a multi-agent team


A group of five adventurers enters a dungeon and wants to get the best loot. There are other parties competing for loot. Each party member has different abilities, health, stamina amounts, and carry capacity. Each has independent knowledge and must exchange information via a speak action.

The dungeon is made of rooms connected on a 2D grid. A room may have 1-4 doors. Some doors may be one-way. Rooms may have treasures, monsters, and traps.

As in the prequel challenge, treasure requires bidding and all actions resolve simultaneously with a specific priority on action types.

Party members

There are five classes of characters comprising each party

  1. Quartermaster
    • 100kg carry capacity, 10 HP, 1000 stamina, 5 power
    • Can heal party members in the same room
  2. Ranger
    • 50kg carry capacity, 10 HP, 1000 stamina, 8 power
    • Can see and attack monsters in adjacent rooms that are connected by a door
  3. Fighter
    • 50kg carry capacity, 25 HP, 1000 stamina, 8 power
    • Double damage to monsters
  4. Thief
    • 30kg carry capacity, 10 HP, 1500 stamina, 5 power
    • Automatically detects booby trapped treasures and can take them without triggering the trap
    • Can steal treasure from enemy adventurers in the same room
    • Can booby trap a treasure, making it appear twice as valuable, but dealing damage to whoever picks it up.
    • Effective bid on treasures is doubled. Wins ties on treasure bids except against other thieves.
  5. Wizard
    • 20kg carry capacity, 8 HP, 1500 stamina, 4 power
    • Can communicate telepathically with any single teammate without needing to be in the same room. This is a two-way channel of communication.
    • Can telepathically visit the room a teammate is currently in, seeing its contents and doors and enabling teleportation to that room
    • Can teleport self or ally in same room to any previously visited room or the same room as any ally.
    • Can teleport any ally to the current room
    • Carried treasure does not increase cost for moving between rooms or teleporting
    • Deals half damage to monsters

Actions available to adventurers of all classes

  • Move between rooms
  • Exit the dungeon (if in the starting room)
  • Speak (can be combined with certain actions)
  • Send a message to the wizard
  • Pick up a treasure (bidding rules work the same as the first challenge)
  • Gift a treasure to another party member in the same room
  • Drop a treasure
  • Attack a monster
  • Attack a rival adventurer in the same room
  • Guard (prevent oncoming attacks and theft attempts)
  • Wait

Communication

Adventurers can communicate by speaking, which will be heard by all teammates in the same room. Speaking requires no stamina and can be combined with movement or gifting, but is limited to be a 20-character string. (Use of emojis for increased message density is fair game)

Combat

A power must be specified when attacking a monster. This cannot be higher than the adventurer's power rating. That amount of stamina will be expended and the monster will be damaged by that amount. If the monster is still alive after all attacks have resolved, the monster will then deal its damage split among all combatants that attacked that turn, minimum of 1 damage.

If adventurers are outnumbered by monsters in any room, the monsters will attack anyone attempting to pick up treasure for 1 damage each.

Defeating a monster will cause the monster to drop up to 3 treasures (typically more valuable than the others in the room) and the characters who attacked the monster that turn will level up, gaining 1 power.

Attacking a rival adventurer will deal one fifth of the damage normally dealt to monsters, but will not result in a counterattack. Attacking an adventurer who either guards or moves into another room will result in a miss. It is possible for adventurers to kill each other on the same turn since attacks resolve simultaneously.

Coding

You will write a bot for each party member. They may not share data (other than constants and libraries).

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

Make a markdown Table of contents parser

A simple Code Golf challenge in the likes of the Markdown parser.

The parser should ignore normal text and other markup (without an # before it).

Some valid headers are: ### Header 3, # Header1, Text # Header

Sample input:

# Hello
Lorem # Hello2
Hi this is normal text

## This is a subheader
Lorem ipsum

### Subsub
Solor di amet

# Hello again
This is more text!

sample output:

Hello
Hello2
- This is a subheader
--- Subsub
Hello again
\$\endgroup\$
  • 1
    \$\begingroup\$ What about ```[linebreak]# text in code[linebreak]```? Or with indentation? What about where there is no space (still formats) : #no space? Or inside quote: > # header/spoiler: >! #header? Please specify these and any other edge cases. \$\endgroup\$ – Artemis Fowl Apr 12 at 15:45
  • 1
    \$\begingroup\$ I'd personally recommend trying to avoid so many edge cases. If you give a precise list of all of the cases that the parser has to care about and then just say something like "ignore any other markup" I think your challenge will be better. \$\endgroup\$ – FryAmTheEggman Apr 15 at 16:10
0
\$\begingroup\$

Write a compiler/interpreter for ...

Inspired by the lisp challenge here.
It is a series of puzzles.

I don't like to see a simple eval solution, so:

  • interpreting the language is fine
  • translating the language to a different language is fine.

I think this is specific for each language.

Only the syntax and the basic commands.
Also specific.

Winning criteria should not be code golf.
The goal should be that you can "learn" an other language by looking at the code.

Languages that might be good candidates:

  • Lisp
  • APL
  • J
  • Brainfuck (already posted)
  • Whitespace
  • Forth
\$\endgroup\$
  • 1
    \$\begingroup\$ This only works for languages which are small and well defined. BF fits those criteria. Whitespace does too. The others may not. Lisp and Forth have so many dialects that you would have to specify exactly which dialect to support; Lisp, Forth, APL and J might have too many built-ins to fit in an answer: there are character limits. \$\endgroup\$ – Peter Taylor May 12 '13 at 15:16
  • \$\begingroup\$ You don't have to provide all the built-ins, but that is why it is here. \$\endgroup\$ – Johannes Kuhn May 12 '13 at 15:38
  • \$\begingroup\$ What defines the "basic commands"? \$\endgroup\$ – ASCIIThenANSI Aug 31 '15 at 17:54
  • \$\begingroup\$ I don't know? Maybe that you can do the basic stuff with it like +,-,print,... \$\endgroup\$ – Johannes Kuhn Aug 31 '15 at 18:22

You must log in to answer this question.

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