538
\$\begingroup\$

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3549 Answers 3549

1
45 46
47
48 49
119
1
\$\begingroup\$

Smooth Usage [On hold while alternative scoring is considered]

We've all seen CPU usage graphs like this one:

CPU Usage example

Doesn't that look ugly? It would look much nicer as a lovely smooth sine wave...


Challenge

Write a program in the language of your choice that will infinitely produce a regular sine wave in Task Manager's (or Activity Monitor's if that's your thing) CPU usage graph.

You may assume:

  • Background CPU usage is constant
  • Only a single core must display the pattern
  • The system has sufficient cooling to prevent thermal throttling
  • Features such as Intel TurboBoost are disabled

This is tagged as to encourage short answers, but ultimately will be a as I suspect perfect solutions will be hard to come by.

\$\endgroup\$
5
  • \$\begingroup\$ Related: stackoverflow.com/questions/551494/… \$\endgroup\$
    – MTCoster
    Aug 11 '17 at 15:14
  • \$\begingroup\$ code-golf and popularity-contest don't mix together. You have to choose one or the other, but making it strictly code-golf would be difficult because you'd have to define what is a good enough sine wave, but on the other hand popularity contests are very risky to do. \$\endgroup\$
    – dzaima
    Aug 11 '17 at 15:16
  • \$\begingroup\$ @dzaima That was exactly my dilemma - which would you suggest fits the challenge best? \$\endgroup\$
    – MTCoster
    Aug 11 '17 at 15:17
  • \$\begingroup\$ I'd say a scoring algorithm of some sort would be best for this, no idea how you'd do it. Like the related one was objective. If you could read the word, it was valid. With this, is a bumpy sin-wave a sin-wave? \$\endgroup\$ Aug 11 '17 at 20:39
  • \$\begingroup\$ @MTCoster If you're not sure whether popularity-contest fits, then you can be sure that it does not. It is quite difficult to make an well received one. Go with code-golf or make a code-challenge if you can come up with a good own winning criterion. \$\endgroup\$
    – flawr
    Aug 11 '17 at 20:53
1
\$\begingroup\$

Reverse Cycling with Rubik's

In Cycling with Rubik's, you were asked to find the period of a given sequence of turns - or, in Geobits' words:

Given a sequence of turns, [find] the fewest number of times it must be performed to return the cube to its original state.

Today, I'm asking you to do the opposite.

Terms you might not know:

  • "algorithm": a sequence of moves on the faces of a Rubik's cube
  • "period": the minimum number of times an algorithm must be repeated before a solved cube returns to the solved state

Input

The input will be the period of a Rubik's cube algorithm. This is an integer between 1 and 1260, as any algorithm can be performed 0 times, and the highest possible period for any given algorithm is 1260.

Output

The output will be any algorithm that has a period equal to the input. Algorithms should use standard notation, namely:

R - Turn the right face clockwise 90°
L - Turn the left face clockwise 90°
U - Turn the up (top) face clockwise 90°
D - Turn the down (bottom) face clockwise 90°
F - Turn the front face clockwise 90°
B - Turn the back face clockwise 90°

Adding the prime mark ' to the end of any move changes it from a clockwise rotation to a counterclockwise one, so F' turns the front face counterclockwise, and F F' would return it to the original state right away.

If you're still confused about face turns, you can check out this.

Examples

Input -> Output
1     -> FF'
4     -> R
4     -> UD
6     -> RUR'U'
12    -> LLUUFFUURRUU
56    -> LUFFRDRBF
105   -> LF
120   -> UFFR'DBBRL'
315   -> FRBL
1260  -> U1R3U1F3D2

Winner

As with , the answer with the least bytes wins! As this is very difficult (it might be impossible), I will give a +50 bounty to the first answer, or +100 if it's under 100 bytes. Good luck!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The order of the Rubik's cube group is 2²⁷ 3¹⁴ 5³ 7² 11, so by Lagrange's theorem there's no algorithm of order 13. \$\endgroup\$ Aug 17 '17 at 8:41
  • \$\begingroup\$ @PeterTaylor Is the same true for any other prime? \$\endgroup\$
    – H.PWiz
    Aug 17 '17 at 15:24
  • \$\begingroup\$ @H.PWiz, the same is true for any other number which isn't a factor of the order of the group. I'm not sure whether subgroups exist for all factors smaller than the largest order of an element. Certainly they do for all prime factors, by Sylow's theorems. \$\endgroup\$ Aug 17 '17 at 15:28
  • \$\begingroup\$ @PeterTaylor I don't know any group theory, but thanks anyway. \$\endgroup\$
    – H.PWiz
    Aug 17 '17 at 15:32
  • \$\begingroup\$ Hmm.. unlike the Cyling with Rubik's challenge, this one can only be solved by bruteforce if I understand correctly? Also, what's with the R3 and F3 in the 1260 test case? These can just be R' or F'. Or if you are allowing 3 instead of ' as output, I would mention it somewhere in the challenge. Off-topic: But it's funny that my Rubik's cube logo is almost next to your challenge title, since I posted the previous sandbox answer. ;p \$\endgroup\$ Aug 18 '17 at 6:49
1
\$\begingroup\$

Time bomb ping pong


Challenge - Both teams

All users are divided into two teams based on their PPCG ID. For example, my ID can be found here, from which you can see that my ID is 34388. To check on which team you are, run the following snippet:

function update_team(){var e=document.getElementById("user-id").value,t=(document.getElementById("team-result"),"");t=e.match(/^\d+$/)||0===e.length?-1!==even_top_50.indexOf(parseInt(e))?"You are in team: ALPHA":-1!==odd_top_50.indexOf(parseInt(e))?"You are in team: BETA":0==e.length?"":"You are in team: "+(parseInt(e)%2==0?"ALPHA":"BETA"):"ID must be numeric",document.getElementById("team-result").innerHTML=t}var even_top_50=[12012,20260,17602,11259,26997,194,31716,20080,58563,47066,1426,4098,30688,56656,41723,3967,1490,31516,40695,29577,43319,15599,32686,3191,4020,67,34718,41024,7311,39328,16766,7110,31625,2867,59107,52210,16120,6710,68942,10740,9365,84,1147,15,199,7162,1308,3103,26600,59487],odd_top_50=[8478,36398,21487,3808,42545,3852,53748,48934,34388,21348,4162,34531,25180,31414,24877,31957,20469,31343,7416,45941,32014,39242,42963,11006,6828,9498,9288,14215,4198,3544,30164,33208,4372,95,41805,56178,668,47120,30525,55735,51507,57100,6699,737,39022,46855,51939,32700,59376,7209];
.main-header,.main-input,.result{font-family:Montserrat,sans-serif;text-align:center}.main-header{font-size:24px}.main-input{display:block;margin:12px auto auto}.result{margin-top:24px}
<br><div><div class="main-header"> Enter your PPCG ID </div><input class="main-input" maxlength="6" onkeyup="update_team()" id="user-id"> <div class="result" id="team-result"> </div></div>

Each user has two options:

  • Start a new bomb
  • Perform a counterattack

These actions are discussed here:


Start a new bomb

To set up a new bomb, you need to do the following:

  • Create a full program in any free language which has the output X.
  • Create a custom list of characters with a maximum of 10 characters.
  • Select one or more characters from the character list and insert them into your program, which will be having the exact same output X. This ensures that there is at least one crack for your submission.
  • Only reveal the full original program and the character list. Keep the modified program secret. Also keep track of the iteration index, which in this case is 1 (since it's the start of a new bomb).

This is an example of a new bomb submission:


Python 2, 9 bytes (index = 1)

Outputs the number 30.

print 5*6

With as character set 13579/. Try it online!.



Perform a counterattack

To perform a counterattack, you need to do the following:

  • Create a new full program with at least one character inserted from the list given by the opponent, which will have the exact same output X.
  • Create a custom list of characters with a maximum of 10 characters.
  • Select one or more characters from the character list and insert them into your program, which will be having the exact same output X. This ensures that there is at least one crack for your submission.
  • Only reveal the full original program and the character list. Keep the modified program secret. Also keep track of the iteration index, which in this case is the increment of the previous index.

This is an example of a counterattack (using the previous submission):


Python 2, 12 bytes (index = 2)

Defuses Python 2, 9 bytes, Adnan.

Inserts 1, / and 3. Outputs 30:

print 15*6/3

With as character set: +-~58. Try it online!



Scoring system

Every bomb that has not been defused for 7 days gives the team 'index' points. If the index was 4, your team gets 4 points. You are only able to collect the points after you have revealed your own solution. Note that if you do not reveal your solution after the 7 days, it is still vulnerable to cracks.

As for the individual winner of the team, the person with the most cracks of the winning team gets the check mark.


Sandbox notes

  • Note that this is more of an experimental challenge. Unlike the conventional 1 vs 1 cops-and-robbers challenges, this is an attempt on an n vs n-challenge, so I have no idea whether this is a good idea or not.

  • The scoring system is a bit tricky, but I think that when a bomb has 'exploded', the opponent's team gets (index) points. The team with the most points at the end wins. The problem here is that the byte count might make things worse, since a larger program would make cracking the submission harder.

  • A problem I'm finding here is the fact that the cop can create an arbitrarily large program, which makes it almost impossible to crack. I'm not sure whether this actually is a problem, since the 'exact same output'-rule should theoretically take care of this.

  • Perhaps add a third option for the user, where the user defuses a bomb. This would consist of cracking the submission, but does not create a counterattack (for cases when this is impossible, or trivial (like adding comments)).

  • I'm also not entirely sure about the 'choose your own output'-idea. Would this leave too much options for abusement?

  • Is the maximum of 10 character too much / too little? Should this also be taken in account with the scoring?

Thanks in advance!

\$\endgroup\$
8
  • \$\begingroup\$ Maybe try the wording "one or more" instead of "at least one"? It took me a while to realise that was what you meant. For more meaningful feedback about diffusions/maximums I think you'd have to decide on a scoring mechanism first. Since both teams use the same bombs to advance their score I don't think the byte count think is that big of a problem? \$\endgroup\$ May 27 '17 at 0:38
  • \$\begingroup\$ @FryAmTheEggman Thank you for your response. I have decided that the score is just simply the sum of all index numbers of the bombs that aren't diffused after three days. This encourages counterattacks more, since the score will increment after each counterattack. \$\endgroup\$
    – Adnan
    May 27 '17 at 9:34
  • \$\begingroup\$ Nice. A never-ending hot potato game. \$\endgroup\$ May 29 '17 at 12:27
  • \$\begingroup\$ @SIGSEGV Yeah, that's what it's supposed to be. I should probably set a time limit somewhere, otherwise there will be no winner at all :p. \$\endgroup\$
    – Adnan
    May 29 '17 at 13:07
  • \$\begingroup\$ I'm worried that this could very easily turn into "stay online more than your opposition does", if an answer is given in a language that's very easy to crack. \$\endgroup\$
    – user62131
    May 31 '17 at 22:47
  • 3
    \$\begingroup\$ 1. Defuse, not diffuse. 2. Three days is not much. A carefully timed post at the start of the weekend could slip through the net. 3. Unless I missed it, there's nothing to prevent the usual CnR-killer crypto answer. Are you absolutely certain that they won't break the challenge? \$\endgroup\$ Aug 21 '17 at 12:51
  • \$\begingroup\$ @PeterTaylor Thanks for your response. I have changed the time limit to 7 days. The main problem would indeed still be cryptographic submissions. I tried to decrease the severity of this problem by making sure that the output would remain exactly the same before and after modifying the submission, but I need to experiment a bit with this to see how this would end up. Hashing would almost certainly not be possible, unless a hashing algorithm is cracked (but I'm not 100% certain about this). \$\endgroup\$
    – Adnan
    Aug 21 '17 at 13:06
  • \$\begingroup\$ As for the hashing, this worked for me: "Please, don't "implement RSA" or anything mean to the robbers. Use obscure languages and features, not boring encryption and hashing. I can't enforce this with rules, but you can expect torrential downvotes if all you do is sha(input) === "abcd1234"." \$\endgroup\$
    – user58826
    Aug 24 '17 at 14:33
1
\$\begingroup\$

Conversion: 2 dice from 3


This fascinating video from Matt Parker's standupmaths poses a challenge:

Given the result of rolling 3 indistinguishable (unordered) dice, simulate the result of rolling 2 indistinguishable (unordered) dice.

For the purposes of this challenge, simply returning the sum of 2 dice is not sufficient. Returning 2 ordered dice is acceptable, as the order can be ignored so this still fulfils the requirement.

Input

Either 3 unordered values from 1 to 6, or 3 ordered values from 1 to 6. If the values are ordered, then the output must be independent of the input order. For example, the input 1, 2, 3 should give the same output as the input 2, 1, 3.

These are standard dice. Your code may not assume the values will be from 0 to 5 instead of 1 to 6.

Output

Either 2 unordered values from 1 to 6, or 2 ordered values from 1 to 6. If the values are ordered, then different orderings will be considered equivalent. For example, output 1, 2 is equivalent to output 2, 1.

Given input that matches the probability distribution of rolling 3 dice, the probability distribution of the output must match that of rolling 2 dice.

You can choose to calculate the outputs however you wish, provided that they are deterministic (the same input in any order gives equivalent output). That is, different answers may use different mappings. So for input 1, 2, 3, one answer may give output 4, 5, while another answer may give output 5, 6. Provided all outputs occur in the correct proportions, both answers are valid.

The output must also use standard dice. Your code may not output values from 0 to 5 instead of 1 to 6.

Checking for correctness

One simple but laborious way of checking that the outputs occur in the correct proportions is to consider all 216 possible ordered triples as inputs. This automatically accounts for the fact that the unordered triple 1, 2, 3 is 6 times more likely to come up that the unordered triple 1, 1, 1, since it will occur as 6 different ordered triples (the 6 different ways of arranging 1, 2, and 3).

A valid answer will give the same output (apart from order) regardless of the order of the input, and will give any given double such as 1, 1 for exactly 6 of the ordered inputs, and any given distinct pair such as 1, 2 (equivalently 2, 1) for exactly 12 of the ordered inputs.

Scoring

The original puzzle was asking for an easy way for humans to calculate this in their heads during playing a game. This challenge is instead , so the score is the number of bytes in your code, and the lowest score in a given language wins.

Prior work

This was also posted on puzzling.SE and there are a number of approaches there. Although they are aimed at being human usable, there may be some insights there that are relevant to writing short code.

Test cases

As every answer may use a different mapping, there is no way to generate meaningful test cases for this challenge. The simplest way I can think to test is as described above under "Checking for correctness".


Sandbox questions

  • I've just discovered this previous challenge which is based on the same video. It asks only for the sum of 2 dice, rather than an unordered pair, so is not identical. Is this a sufficient difference to avoid this being a duplicate, and would it be different enough to be worthwhile posting?
\$\endgroup\$
2
  • \$\begingroup\$ Even if it's not officially a dupe I'd still like feedback on whether it's different enough to be interesting. \$\endgroup\$
    – trichoplax
    Aug 23 '17 at 15:45
  • \$\begingroup\$ Looking at the Jelly answer, I think the change required for this question is to remove the final character. So yes, it does fail the dupe test. \$\endgroup\$ Aug 23 '17 at 21:35
1
\$\begingroup\$

Just a relative

Summary

Produce a piece of golfed code that will take a spreadsheet formula and a translation vector and adjust any cell references in the formula by the translation vector.

Rules

What you need to create is a program that takes 2 inputs. A string formula and a representation of the transformation the formula is to undergo (i.e: 1 1 (column, row)).

Invalid inputs include, but are not limited too, inputs with invalid cell references, translations that produce invalid references (see definitions) and formulas formulas that don't start with an equals sign.

The output should be the formula with its' cell references transformed as per the rules above. Input types are flexible, but the output should be a string with no leading/trailing whitespace.

Definitions

Cell Reference

An alphanumeric string that within spreadsheet software, indicates the cells position on a 2D grid. They consist of two parts, an alphabetic segment a numeric segment.

The alphabetic segment represents the column position of the cell. It can be of any length, with each character belonging to the 26 letter English alphabet and is case insensitive. A numerical mapping of the column position can be attained using 26-adic bijective numeration.

The numeric segment represents the row position of the cell, and must be a positive non-zero integer.

It is also valid for the dollar $ symbol to appear in a cell reference. A single one is valid preceding both the alphabetic and numeric segments either independently or simultaneously. A dollar preceding the alphabetic segment indicates an invariant column under transformation, and a dollar preceding the numeric segment indicates an invariant row under transformation.

Function

An arbitrarily named reference to some set of instructions.

For the purpose of this challenge, these are defined as a case insensitive alphanumeric string followed by an open and closed set of rounded brackets. Within these brackets, arbitrary arguments can be present including other functions, arbitrary values and cell references. Arguments are comma seperated.

Example: CALCULATEBYTES('mycodegolfanswer', A1)

Formula

A calculation composed of arbitrary numeric operators, functions, values, cell references etc.

A formula must be started with an equals = sign and can then be followed by anything except for a numeric operator.

Examples

=SUMIFS(A1, "=2") 1 1
>>=SUMIFS(B2, "=2")

=SUMIFA1(GL93) 1 2
>>=SUMIFA1(GM95)

=ARBITRARY($A$1)+CRAZY(G$3) 3 3
>>=ARBITRARY($A$1)+CRAZY(J$3)

=$A3+B$2+$C$1 4 -2
>>=$A1+F$2+$C$1

Hope this all makes sense!

Winner is the shortest code in bytes, but bonus kudos if anyone posts a golfed answer in punch card Fortran!

Happy golfing!

\$\endgroup\$
2
  • \$\begingroup\$ 1. The post is a bit "wall of text"-ey. Maybe separate out all the description of what references are from the main challenge a little? 2. You talk about using $ for absolute referencing but don't mention them in the challenge or give any test cases for them. 3. It's normal in code-golf to assume input will be valid or (almost equivalently) allow any behaviour upon receiving invalid input (I'd suggest one of these). If you do keep an actual "error requirement" you should state if it should be the string "error" or an actual error and probably add a reason for the error to the test case(s). \$\endgroup\$ Aug 24 '17 at 21:07
  • 1
    \$\begingroup\$ @JonathanAllan Thanks for the feedback. Amended based on what you said \$\endgroup\$
    – dbr
    Aug 25 '17 at 21:59
1
\$\begingroup\$

Brain-Flak Golfing Tournament

This is a very rough draft. I am looking for as much feedback as possible while I flesh out this challenge

Welcome to the first ever Brain-Flak Golfing Tournament.

This tournament will have 2 phases. The first being a call for challenges and the second being the competition. Any user may participate in either, both or, of course, neither of the phases.

Challenge submissions

In this first phase users can submit mini challenges to be used in the competition. These will be of two varieties,

I've chosen these varieties because they tend to be the commonly agreed most "fun" tags for Brain-Flak. (SANDBOX: If you have any qualms these varieties are variable)

Kolmogorov-complexity

Kolmogorov complexity challenges, like the name implies, should provide a constant string to be output with no input. For example Hiya there earth!.

As a personal style point I find Kolmogorov complexity is most fun for strings of 10-20 characters. However feel free to answer of whatever size you think would be interesting

Sequence

For sequence challenges you should you should choose a sequence from the Online Encyclopedia of Integer Sequences, and provide its number and a brief description in the body of your answer.

Answers to sequence mini challenges will take n and output the nth term of the sequence. You may specify what indexings are permitted in your answer. Since OEIS sequences are not well specified on their own answers will only be required to support as high as are provided in the b-files of that sequence.

As a personal style point Brain-Flak is especially good at computing challenges involving or related to polygonal numbers, however variety is always welcome.


In addition to providing a challenge you must also provide a "par". A par will be a program that satisfies the requirements of your mini-challenge. The purpose of a par is two-fold:

  • It proves your mini-challenge is reasonably possible

  • It provides a default score for more casual participants who might not necessarily answer all the mini-challenges, or more serious users who run out of time.

Your par should not be your own best attempt at a challenge, it should be beatable otherwise participants would just score the par and you might as well have not made the challenge at all.

Lastly no mini-challenge should correspond to a preexisting PPCG that already has a Brain-Flak answer. For example do not submit print Hello, World! as a challenge, because we have already have very competitive solutions. Unlike earlier suggestions this will be enforced.

Challenge answers

In the second phase users will answer challenges made in the first phase. You will have one week to craft an answer in (relative) secrecy, at the end of the week answers will be revealed and a winner declared. You will have to have an answer on this question prior to the reveal.

All that is required of answers before the reveal are the following two things

  • A rundown of the byte counts. This should be your scores to each mini challenge not including ones posed by your self. If you choose not to complete a single challenge for any reason you should take the par as your score for that challenge.

  • A hash. This should be a SHA-256 hash of a string containing all of your solutions on separate lines and your ppcg user id. You may include other information in the string to throw off potential attackers if you wish, but it should not resemble any of the required elements.

These are the only two things that are required, however if you would like to include additional hints to other users you may do so, just don't reveal your own solutions ahead of time as that can make the challenge rather un-fun.

You may continuously update your answer anytime before the reveal.

You should not at any point lie about contents that are hidden. Accusations will be dealt with on a case by case basis, but if you are caught having lied you will be disqualified.

Scoring

This is still a work in progress right now its just a plan

I plan to base scoring based on graph theory. Normally it would just be the sum of individual challenges but because one cannot fairly compete in their own challenges things have to be a little bit more sophisticated. Once I decide on a good scoring system I will add a code snippet to help calculate rankings.

Scoring will obviously be based on byte counts with less being better.

Prizes

I will be offering 3 bounties for exceptional participants

  • 500 rep for the overall winner of the challenge

  • 200 rep for the runner up of the challenge

  • 100 rep for the top voted mini challenge

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

OR ,

Steganography: Hide a message in an image!


Cops

You will want to see the Default acceptable image I/O methods for image related challenges.

Your challenge is to write a program that takes a string and an image as input and somehow encodes the string in the image. You output the image.

You must also make a program that reverses the above: it takes a image, and outputs the original string (you don't need to output the original image).

Your encoder must work on any string, but it only needs to work on one type of image.

Post the encoder (but not the decoder), and preferably a few image / string input / output examples.

Your post is cracked when someone makes a program that can take an outputted image and find the string hidden in it. It doesn't have to be the decoder you intended. It can even be in another language.

Once your submission is cracked, edit in a link to the crack and your decoder program.

If, after a week, nobody* has cracked your submission, edit in that you are safe, and edit in your decoder.

This may provide ideas!

*not Nobody


Robbers

Your challenge is to find a cop post and crack it.

To crack a cop post, you make a program that reverses what cops do:

Your challenge is to write a program that takes a string and an image as input and somehow encodes the string in the image. You output the image.

In other words, your program takes an image and extracts the encoded string out of it. You don't have to output the image with or without the string.

Once you have cracked a cop's post, add a link in a comment.

The robber with the most cracks wins.


Meta:

  • Dupe? (I don't think so)
  • Winning criterion for cops:

    I really want this to be a pop-con. Pop-cons are hard but I think I have everything needed for a good pop-con covered:

    • A challenge with clear specifications that still allow for creative problem solving. I think this is clear but gives you freedom in how you encode a string.

    • A challenge where solutions that best solve the problem are also solutions that the voters are going to like. I think that voters will enjoy very creative 'encoding's.

    • Gives freedom to entrants to decide what to do in crucial parts and incentivizes them to use this freedom. You have complete freedom to pick how you hide the string. If you use a boring form of encoding, your encoder will quickly be cracked, but if you use your freedom to make a very creative encoder your submission will likely be safe.

    • It is strongly suggested to submit the challenge to the Sandbox at least a few days before posting the challenge. That way the challenge can be reviewed and discussed in order to find any mistakes or inconsistencies, and it also serves for getting a first impression whether the challenge will be well recieved. Yep, I think this is covered.

    And what MUST be included in a pop-con:

    • A popularity contest must always include an objective validity criterion, which is a set of rules that regulate what every answer must comply with. Answers that do not comply are invalid and will be removed. Yep, if you have a valid, working decoder than your stenography is reversible and therefore valid. If a week passes and you didn't have a decoder, your submission will be removed.

    • A clear specification of the goal that must be achieved. Questions like "do (this) the most creative way" should be avoided. Creativity should be the tool, not the goal. Yep, the goal is to make a program that encodes a string in an image...

    And Qualities which should be AVOIDED in popularity contests:

    • Asking to solve a specific task in a very specific way, without room for creativity. There is room for creativity within bounds in how your encoder works.

    • Asking to solve a vaguely defined task in any way that the entrant wants (this will probably make your question be closed as too broad). Nope, you have the specific task of encoding a string in an image.

    • Rules what people should consider when voting. In the past this has consistently never worked out. These sort of questions would be better off as a with specific winning criteria. Nope, I don't have any of these.

    If there's anything I'm missing, please tell me. I think this is a on-topic valid pop-con. However, if it isn't, I'd be OK with making this a .

    However, PPCG has too much code golf. We need more variety in the challenges we have here. I hope this will provide an example of a valid pop-con.

\$\endgroup\$
4
  • \$\begingroup\$ Looking at the page you linked, you could also make this an image-polyglot challenge. Output an image of [something] that also does some other tasks when run in different languages. However, I don't really get your question about code-golf vs pop-con. This is a cops-n-robbers, which is usually won by being the first entry to go X days w/o being cracked. \$\endgroup\$
    – geokavel
    Aug 26 '17 at 23:03
  • \$\begingroup\$ @geokavel most cops-n-robbers I've seen are shortest safe cop, not earliest cop. So he's probably doing highest-voted safe cop. \$\endgroup\$
    – Stephen
    Aug 26 '17 at 23:08
  • 1
    \$\begingroup\$ pop-con's are usually good for graphical output, but here if I understand correctly, the viewer will not be able to see that you manipulated the image just by looking at it. So it lacks the intuitiveness useful for pop-cons. \$\endgroup\$
    – geokavel
    Aug 26 '17 at 23:43
  • \$\begingroup\$ This fails my first test for "Is it a bad CnR?": it's easy to make a cop which uses RSA and can't be cracked within a week on current hardware without spending serious money. \$\endgroup\$ Aug 27 '17 at 16:56
1
\$\begingroup\$

Generating Punnett Squares

The task will be to generate a simple (monohybrid cross) Punnett Square, given the "genotype" of two parents.

A "trait" will be represented as a single alphabetical character (eg 'a').

An allele for a trait is that character, but if the allele is dominant if it is uppercased, and recessive if lowercased (eg 'a' or 'A').

A genotype is two alleles, both of which can be either dominant or recessive. Note that if a genotype is heterozygous (has one dominant and one recessive allele) the dominant allele will always come first (eg "AA" or "Aa" or "aa").

The input will be two strings of length 2, each of which is a valid genotype for one trait. You can take input as arguments to your function or program, or from a file. You should output a Punnett Square in exactly this format:

  A  a
A AA Aa
a Aa aa

(This would have been for the input "Aa" and "Aa"). The output can be to stdout, as a string, or to a file.

The first parent (which is the first argument) should be across the top, and the second parent should be down the side, so for the input "AA" and "aa", the output should be:

  A  A
a Aa Aa
a Aa Aa

Your code is expected to work with any trait (letter of the alphabet).

Another way to phrase this problem might be to output a table of the cartesian product of two strings of length 2, where each string consists of only uppercase or lowercase variants of one character, and the data in each cell should be sorted such that each uppercase character comes before each lowercase character.

Full sample of behaviour for some trait "a":

"AA", "AA" ->

  A  A
A AA AA
A AA AA

"AA", "Aa" ->

  A  A
A AA AA
a Aa Aa

"AA", "aa" ->

  A  A
a Aa Aa
a Aa Aa

"Aa", "AA" ->

  A  a
A AA Aa
A AA Aa

"Aa", "Aa" ->

  A  a
A AA Aa
a Aa aa

"Aa", "aa" ->

  A  a
a Aa aa
a Aa aa

"aa", "AA" ->

  a  a
A Aa Aa
A Aa Aa

"aa", "Aa" ->

  a  a
A Aa Aa
a aa aa

"aa", "aa" ->

  a  a
a aa aa
a aa aa

This is my first attempt at a challenge so I'd like some feedback on if it's any good and how it can be improved. I haven't been able to find any challenge like this, so hopefully it's not a duplicate.

Have I explained it clearly?

Is this idea interesting enough for a challenge?

What other tags would I use with such a challenge?

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

Displaying exponent towers in ASCII

Background

Unlike + and *, the exponentiation operator ^ is not associative. The convention is that ^ is right associative, so that a^(b^c) = a^b^c. Of course, nested exponentials are usually displayed as nested superscripts, which can be represented in ASCII as:

            c
           b
a^(b^c) = a

For a general right associative operator &, there would be no way to simplify the expression (a&b)&c. However, exponentiation satisfies the rule

           bc
(a^b)^c = a

where bc means b*c.

Combining these rules, we can express any arbitrarily parenthesized exponential expression using only superscripts and juxtaposition. For example,

                                               d
                                              c  f
                                             b  e
(a^(b^(c^d)))^(e^f) = a^((b^(c^d))*(e^f)) = a

Challenge

Write a function that, given a string consisting of lowercase letters, parentheses, and ^ that represents a valid mathematical expression (see rules), prints an ASCII representation of this expression in the manner described above.

Rules

  • The input string is any element of the context-free grammar determined by the rules
    S → any lowercase letter
    S → (S^S)

  • The output must consist of only lowercase letters, spaces and newlines.

  • The resulting ASCII picture must have exactly one letter per column.

  • The left to right order of the letters must be preserved from input to output.

  • This is , so shortest answer in bytes wins.

Test Cases

Input: a
Output:
a

Input: (a^(b^c))
Output:
  c
 b
a

Input: ((a^b)^(c^d))
Output:
   d
 bc
a

Input: ((a^(b^c))^d)
Output:
  c
 b d
a

Meta

  • Is it clear what picture you are supposed to output?

  • This challenge has some similarities to this other challenge, but I think they are far enough part to not be dupes: Convert exponents into ASCII art.

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

Erdős–Straus conjecture

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you give me the answer for n=7777 . How much time did it take your program to find it? What do you mean by "result must be returned for all valid inputs".Is 1500 years ok for bigger n? Brute-forcing this is very easy but it takes forever. \$\endgroup\$
    – ZaMoC
    Sep 9 '17 at 10:06
  • \$\begingroup\$ @Jenny_mathy I'll put a reasonable limit and the last part means you need to output the right numbers if x is valid (a whole number larger than 2) \$\endgroup\$ Sep 9 '17 at 11:28
1
\$\begingroup\$

Determine the Resultant

META:

I'm not yet sure which one of the following two versions would be more interesting:

Version a: Given two integral polynomials P,Q determine their resultant Res(P,Q).

Version b: Given two monic integral polynomials P,Q determine the polynomials A,B such that AP+BQ = Res(P,Q). Where deg A < deg Q and deg B < deg P.

Definitions

The resultant is defined as

Here the product iterates over all complex numbers pairs that are zeros of each polynomial. For integral polyonmials this is an integer. (One other way - and certainly not the only - is via the determinant given here.) The corresponding integral polynomials A,B such that AP+BQ = Res(P,Q) with deg A < deg Q and deg B < deg P are unique.

\$\endgroup\$
2
  • \$\begingroup\$ Are these polynomials on Z? You say complex number pairs which suggests it is some numeric set. \$\endgroup\$
    – Grain Ghost Mod
    Sep 17 '17 at 0:28
  • \$\begingroup\$ Those pairs are not necessarily integers, but the polynomials are. \$\endgroup\$
    – flawr
    Sep 17 '17 at 14:29
1
\$\begingroup\$

Pythagorean Double Regex

Posted by NH. in Zendo:

though depending on the regex flavor, things like that pythagorean triple could be hard to do.

The rule in question was:

Given a pair of numbers, match if the two numbers are part of some integral Pythagorean triple, else don't match.

Challenge

Given a pair of positive integers, write a regex that matches if and only if the pair of integers are part of a Pythagorean triple - i.e. if the two integers are a and b, either a2+b2 is a perfect square or |a2-b2| is. (Note: x,x should match, even though 0,x,x is not a true Pythagorean triple)

Input

  • Integers represented in any base, separated by a character not used in the representation of that base

Test cases

NB: All but one of these test cases were taken from the game of Zendo from which the rule came, so they may not test boundary cases of the rule

True:
3,4
4,3
30,40
16,12
20,21
21,20
4,5
40,50
24,25
7,7

False:
1,2
5,6
7,8
4,10
9,10
3,100
9,16
24,20

This is , so the shortest regex in bytes wins!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 1. Ideally a question should be self-contained. This barely makes sense without following the links. I'm not even sure whether the answers have to be regexes or whether that was just the original context. 2. What's the scoring system / winning criterion? \$\endgroup\$ Sep 11 '17 at 7:53
  • \$\begingroup\$ @PeterTaylor is this better? \$\endgroup\$
    – boboquack
    Sep 11 '17 at 8:35
  • \$\begingroup\$ Definitely improved, yes. I'm still not sure what "(from the game)" refers to. Also, are you taking into account that by default we consider unary to be an acceptable input format for positive integers when writing a regex? I advise being explicit about whether numbers must be in decimal or whether unary is acceptable. \$\endgroup\$ Sep 11 '17 at 8:44
  • 1
    \$\begingroup\$ @PeterTaylor fixed up again \$\endgroup\$
    – boboquack
    Sep 11 '17 at 9:07
1
\$\begingroup\$

Align the Words

Given a list of words l output them as follows:

  • Iterate through l, if it's the first word, output it as usual.
  • If it's not the first word, iterate through this nth word and:
    • Find the first letter of word n that's in word n-1.
    • Align the first occurrence of that letter in word n with the first occurrence in word n-1 and print it on the next line.

Worked Example

Input: [ace,face,please,keep,sheeple]

1: ace

2:  ace
   face

3:  ace
   face
    please

4:  ace
   face
    please
     keep

5:  ace
   face
    please
     keep
    sheeple

[Note: You only print step #5, the rest is to show the process.]

Rules

  • Lowest byte-count wins, this is .
  • All consecutive words in the input list l will have at least 1 letter in common.
    • If the input is invalid, any return is fine (error, nothing, etc...)
  • A word is defined here as a collection of a-z (lowercase ONLY alpha characters).
\$\endgroup\$
4
  • \$\begingroup\$ Related, not a dupe. \$\endgroup\$ Sep 11 '17 at 18:48
  • \$\begingroup\$ To be clear, are we to output every step along the way, or just the final arrangement? If every step along the way, what's an appropriate separator? \$\endgroup\$ Sep 11 '17 at 19:04
  • \$\begingroup\$ @AdmBorkBork final product, should make that clear I s'pose. \$\endgroup\$ Sep 11 '17 at 21:13
  • \$\begingroup\$ Are we allowed to use uppercase only instead of lowercase only as well? Not really relevant for the programming language I usually golf in, but I can imagine it's relevant for some programming languages. \$\endgroup\$ Sep 26 '17 at 12:00
1
\$\begingroup\$

Create a .pdf file

Your task is, given a non-empty string, to create a valid PDF (also see here for more information about the structure of PDF-files) file that contains no more than this string (no page numbers, date etc). Your submission has can either be a function or full program that achieves this task.

Rules

  • The input will be a non-empty string of printable ASCII characters, additionally the characters \n & \t may be part of the input but not the last character
  • Your program/function produces a valid PDF file that contains that string but no more
  • The representation of the string doesn't matter, except that it has to be a different color than the background, meaning valid representations may be (not limited to):
    • green text on black background (or the other way around)
    • the font is irrelevant but has to be consistent (it has to be readable without using a loupe)
    • some sort of image that represents the string
  • The output has to be case sensitive
  • If the string doesn't fit page width it needs to be split in a consistent manner such that it fits onto multiple lines (this means each character needs to be visible)
  • If the lines don't fit onto a single page, you'll need to insert pagebreaks
  • The width of a \t and (space) need to be visibly different (\t larger)
  • The PDF may contain one trailing empty page
  • The PDF can be printed to STDOUT (ie. call_your_program > test.pdf would result in a valid PDF) or create a new file somewhere on your filesystem (the filename doesn't need to end in .pdf or .PDF)

Example inputs

Valid

Printable string:

Hello, World!

Printable string containing newline(s):

Foo\nBar

Printable string containing newlines & horizontal tabs:

Line 1:\t!"#$%&\'()*+,-./0123456789:;<=>?\nLine 2:\t@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_\nLine 3:\t`abcdefghijklmnopqrstuvwxyz{|}~

Invalid

Trailing newline:

Hello, World!\n

Carriage return:

Foo\r\nBar

Empty string:

Sandbox

Tags will be: , ,

  • Are there other relevant tags?
  • Is the challenge specific enough (creating PDFs that only work in an exotic PDF-reader etc)?
    • Should I limit the question such that the file has to be "viewable" in (for example) xpdf?
    • If so, would xpdf be a good choice?
  • Is "readable" well defined enough (for example some people may claim that they are able to read Wingdings or even worse Comic Sans :P)
  • Should I enforce a certain font size? What about even enforcing a certain font itself? (I feel this takes away too much freedom)
  • Should I limit input such that it always fits onto a single page? (Loophole: people could choose a font size such that the input can only be one letter)
\$\endgroup\$
9
  • \$\begingroup\$ Is there a publicly available spec of the format, that doesn't require six months of waiting, 100$, signing a non-disclosure agreement and sacrificing a goat? If yes, do link. If not, I'm going to nope out of the challenge. \$\endgroup\$ Sep 23 '17 at 14:48
  • \$\begingroup\$ @JohnDvorak I'm looking for a solution for this issue, but it seems like without changing the file-format there's no way around this :( What a shame.. Also the pricing seems dynamic, are you referring to this? Because for me it shows nearly 200$ O.O \$\endgroup\$ Sep 23 '17 at 15:14
  • \$\begingroup\$ Oh boy. It seems I tried to overshoot the price by a comfortable margin and failed miserably. \$\endgroup\$ Sep 23 '17 at 15:19
  • \$\begingroup\$ This is ridiculous.. I expected the specs for PDF to be free since it is such a wide-spread format. Do you have a suggestion to resolve this issue apart from deleting this challenge? \$\endgroup\$ Sep 23 '17 at 15:22
  • 1
    \$\begingroup\$ You could go with a different format. OpenDocumentFormat is just a bunch of well documented XMLs packaged in a single ZIP file. Golfers can then try and see how much they can bend the rules before OpenOffice starts whining. Plus, zip files can technically be created without a library - just stick a mostly constant header before the uncompressed data. \$\endgroup\$ Sep 23 '17 at 15:29
  • 2
    \$\begingroup\$ I think adobe.com/content/dam/Adobe/en/devnet/acrobat/pdfs/… is publicly available, but I don't think this question's spec is quite clear enough. In particular, it should address line wrapping when the input text doesn't include newlines. \$\endgroup\$ Sep 23 '17 at 16:50
  • \$\begingroup\$ @PeterTaylor Oh, yep that's public :) Thanks a lot! I'll see how I can address the line wrapping issue in a sensible manner (either by removing the \ns in the input or by creating a rule such that they can't just be ignored). \$\endgroup\$ Sep 23 '17 at 21:20
  • \$\begingroup\$ My main concern there is that it would be easy to just blit the text without caring whether it goes outside the page and is effectively lost. \$\endgroup\$ Sep 23 '17 at 21:35
  • \$\begingroup\$ @PeterTaylor Good call! I updated the post, feel free edit in any suggestions or clarifications (this goes for anyone! If I'm not happy with it I can always revert). \$\endgroup\$ Sep 23 '17 at 22:20
1
\$\begingroup\$

Number of all hyperrectangle-filling walks

Your input:

  • size of the hyperrectangle – generally an n-tuple
    • eg. (s,s) in case of a square
  • position in the hyperrectangle – generally 0 <= pos[i] < size[i] for i-th dimension
    • eg. (x,y) where 0 <= x < s and 0 <= y < s in case of a (s,s) square.

Your task: Find the number of walks in the hyperrectangle, which start at the given position and visit each cell of the hyperrectangle exactly once.

In the context of this task, a walk is a sequence of positions, such that each position after the first differs from the previous one in exactly one dimension by amount of exactly 1. Eg. in the case of a 2x2 square, a possible walk would be (0,0) -> (0,1) -> (1,1) -> (1,0).

Note: It doesn't matter whether x is vertical position and y horizontal or vice versa. Neither it matters whether coordinates grow downwards / upwards or to the left / right (eg. vertical axis might grow downwards or upwards without any effect on the result). These statements extend to higher dimensions as well.

Related task: Longest hypercube path

Example

Given size = (3,3) and pos = (0,0), there are 8 solutions. These can be divided into four equivalence classes under the relation of transposition, viz. A == Transpose(A). Only one solution for each equivalence class needs to be found, the other one can be obtained by simply transposing the first one.

The four "canonical" solutions: (3,3);(0,0) Canonical solutions

Output: 8.

Possible specializations

Specialization 1: Support only hypercubes (hyperrectangles with equal sizes in each dimension). Specialization 2: Support only 2-dimensional hypercubes (squares).

My questions

  1. (Obvious question) Has this task already been presented?
  2. Is this task (in its general form) too difficult? Would it be more reasonable to restrict it to one of the specializations (or to a different specialization)?
\$\endgroup\$
5
  • \$\begingroup\$ Have you made a reference implementation? It seems to me that it would be worth generating some sequences for the two specialisations and seeing whether they're in OEIS, and whether closed forms for the answers and known. \$\endgroup\$ Oct 1 '17 at 20:11
  • \$\begingroup\$ @PeterTaylor Those were my thoughts, but I haven't yet gotten around to making an implementation. I suspect the sequences for specializations (especially Spec. 2) will be in OEIS and most likely will have a closed-form solution, but it's in the higher dimensions where it gets interesting, especially if you consider optimizations based on symmetries. \$\endgroup\$
    – kyrill
    Oct 1 '17 at 20:31
  • \$\begingroup\$ @PeterTaylor I have written a (hopefully correct) implementation in Python 2; though it being a brute-force algorithm, higher dimensional hypercuboids may require some time to be examined... \$\endgroup\$ Oct 8 '17 at 12:52
  • \$\begingroup\$ The relevant OEIS sequence for a hypercube of side lengths 2, starting at one corner, is A003043. \$\endgroup\$ Oct 8 '17 at 14:48
  • \$\begingroup\$ I for one really like this challenge and do not think any specialization which makes the task easier is required. \$\endgroup\$ Oct 8 '17 at 20:36
1
\$\begingroup\$

Detect Ambiguity in a Context-Free Grammar

Sandbox notes:

  • Is the background too hard to understand? If so, should I clarify it further at the risk of making it unreasonably long, or simply delete it and state that the reader should have a knowledge of context-free grammars?
  • Is there anything I should clarify in the specifications?
  • Are there any other tags I should add? I couldn't find any better ones.
  • Should I add more test cases?
  • Apparently at the moment this problem is undecidable (which I found out way too late). Would this problem be decidable if I let solutions assume that ambiguous grammars will always have an unambiguous counterpart (in other words, the program will never be given an inherently ambiguous grammar?

Background

A Context-Free Grammar (CFG) is a set of rules for constructing strings. For example, the following is a CFG describing BF:

progcommand | command prog
command+ | - | , | . | < | > | loop
loop[ prog ]

Let's see how the BF program ,[-] can be constructed using this grammar:

Parse tree for a context-free grammar

Wikipedia formally defines a grammar as a group of four items:

  • A set of nonterminals, which are the "variables". In the example above, these are prog, command, and loop.
  • A set of terminals, which are symbols in the alphabet that strings are composed of. In the example above, these are the BF program characters +-,.<>[].
  • A set of production rules, which define what nonterminals are allowed to become. Each rule consists of a head, which is a nonterminal, and a body, which is a list of terminals and nonterminals. In the example above, these are the production rules:
    • progcommand
    • progcommand prog
    • command+
    • command-
    • ...
    • commandloop
    • loop[ prog ]
  • One nonterminal that serves as the starting point for the grammar (in other words, the root node in the parse tree). In the example above, this is prog.

Consider the following context-free grammar:

bitstringbit | bit bitstring
bit1 | 0

It may be tempting to collapse the two lines:

bitstring1 | 0 | bitstring bitstring

The disadvantage of this representation over the original is that it is ambiguous - that is, given a string, it is possible to deriving that string in multiple different ways. For example, in this grammar, the string 101 may be derived as ((10)1) or (1(01)).

The problem with ambiguity is that there is not a single way to create a representation of the generation process, which is useful for e.g. parse trees.

A useful subset of CFGs

To make CFGs easier to manipulate, we will constrain them in this way:

  • Restrict the alphabet of terminals to 0 and 1,
  • Identify nonterminals by a number rather than a name (either 0- or 1-indexed),
  • Assume the first nonterminal (0 or 1 depending on indexing scheme) to be the initial one.

In this way, we have reduced the description of a CFG down to two inputs:

  • A number representing the quantity of nonterminals
  • A list of production rules, which is a list of pairs (head, body), where head designates a nonterminal for the head, and body is a list of terms which can be terminals or nonterminals.

The Task

Given a representation of a context-free grammar as described above, output a truthy or falsey value representing whether the grammar is ambiguous.

This is , so the shortest valid submission (measured in bytes wins).

Specifications

  • You can use any two distinct non-empty strings instead of 1 and 0 for the terminals.
  • You can assume the lists representing the bodies of the production rules are nonempty.
  • You may take input in any reasonable format. If you are taking input as a number and a list and your language does not support mixed-type lists, you can assume the existence of two special nonterminals that represent the terminals 0 and 1. If this is done, please specify the two nonterminals in your answer.
  • You can assume that every nonterminal can "halt", that is, be mapped to a finite string of nonterminals. This means that you will never get an input like:

    string0 string | 1 string

    This also means that every nonterminal must have at least one production rule.

  • Keep in mind that production rules are technically a set. The order of the rules is not relevant, so your program should be able to handle them in any order.
  • You can assume there will be less than 100 production rules, and therefore less than 100 distinct nonterminals.
  • You can assume that the input will be a well-formed CFG in whatever input format you designate.

Test Cases

In these examples, nonterminals are zero-indexed.

Ambiguous (Truthy)


Only empty strings:

1, [
    (0, []),
    (0, [0])
]

Readable form:

string | string


Any string of bits:

1, [
    (0, []),
    (0, ["0"]),
    (0, ["1"]),
    (0, [0, 0])
]

Readable form:

string | 1 | 0 | string string


Nonempty strings of ones, separated by zeroes:

2, [
    (1, ["1"]),
    (1, ["1", 1]),
    (0, [1]),
    (0, [0, "0", 0])
]

Readable form:

stringones | string 0 string
ones1 | 1 ones


Odd-length strings of bits:

1, [
    (0, ["0"]),
    (0, ["1"]),
    (0, [0, 0, 0])
]   

Readable form:

string0 | 1 | string string string


1 and 0 balanced like parenthesis:

1, [
    (0, []),
    (0, ["1", 0, "0"]),
    (0, [0, 0])
]

Readable form:

string | 1 string 0 | string string


Unambiguous (Falsey)


Only empty strings:

1, [
    (0, [])
]

Readable form:

string


Any string of bits:

1, [
    (0, []),
    (0, ["0", 0]),
    (0, ["1", 0])
]

Readable form:

string | 0 string | 1 string


Nonempty strings of ones, separated by zeroes:

0, [
    (0, [1]),
    (0, [1, "0", 0]),
    (1, ["1"]),
    (1, ["1", 1])
]

Readable form:

stringones | ones 0 string
ones1 | 1 ones


Odd-length strings of bits:

2, [
    (0, [1]),
    (0, [1, 1, 0]),
    (1, ["0"]),
    (1, ["1"])
]

stringbit | bit bit string bit0 | 1


1 and 0 balanced like parenthesis:

1, [
    (0, []),
    (0, ["1", 0, "0", 0])
]

Readable form:

string | 1 string 0 string


\$\endgroup\$
2
  • \$\begingroup\$ I think the CFG is described quite well, but the "useful subset" seems a little confusing - you restrict terminals to [0,1] and non-terminals to numbers and say "...body is a list of terms which can be terminals or nonterminals", but in the examples you have bodies containing quoted numbers. \$\endgroup\$ Aug 24 '17 at 23:39
  • \$\begingroup\$ @JonathanAllan Yes, the quoted ones are terminals, and the unquoted ones are indices of nonterminals. I might change that if it turns out to be too complicated. \$\endgroup\$ Sep 21 '17 at 2:24
1
\$\begingroup\$

Is it Odd or Even

A group is an "Odd or Even group" if there is some member a such that every member in the group can be represented as either k • k or k • k • a.

For example the group Z4 is an even odd group if a = 1

0 = 2 • 2             Even
1 = 2 • 2 • 1         Odd
2 = 1 • 1             Even
3 = 1 • 1 • 1         Odd

The even and odd members can overlap, for example in Z5 if a =1 every member is both even and odd.

0 = 0 • 0 = 2 • 2 • 1 Even and Odd
1 = 3 • 3 = 0 • 0 • 1 Even and Odd
2 = 1 • 1 = 3 • 3 • 1 Even and Odd
3 = 4 • 4 = 1 • 1 • 1 Even and Odd
4 = 2 • 2 = 4 • 4 • 1 Even and Odd

An example of a group that is not an Even or Odd group is the Klein-4 group (Z2×Z2), because k + k = 0 for all k meaning there can be only one even member and one odd member despite there being 4 members of the group.

Task

Given the Cayley table of a finite group determine if it is a Odd or Even group. You will be guaranteed that the input is a group, but you will not be guaranteed anything else. This is a so your code should output two distinct values one for accept and one for reject.

Answers will be scored in bytes with fewer bytes being better.

Test cases

True

0 1
1 0

0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2

0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

0 1 2 3 4 5
1 0 4 5 2 3
2 5 0 4 3 1
3 4 5 0 1 2
4 3 1 2 5 0
5 2 3 1 0 4

False

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

0 1 2 3 4 5 6 7
1 2 3 0 5 6 7 4
2 3 0 1 6 7 4 5
3 0 1 2 7 4 5 6
4 5 6 7 0 1 2 3
5 6 7 4 1 2 3 0
6 7 4 5 2 3 0 1
7 4 5 6 3 0 1 2
\$\endgroup\$
10
  • \$\begingroup\$ The first paragraph is difficult to understand: It is not very clear that you define the terms "even" and "odd" and that the definition is dependent on a. Furthermore you first talk about numbers, but then talk about members of a group, so I'd avoid mentioning numbers, and perhaps link the wikipedia page about groups. The additive notation suggests you're only considering abelian groups, is that true? I'd also define first Z_n as the cyclic group of order n. \$\endgroup\$
    – flawr
    Oct 5 '17 at 19:52
  • \$\begingroup\$ Next question: The definition of "even" and "odd" seems to depend on a, so what is a then in your test cases? \$\endgroup\$
    – flawr
    Oct 5 '17 at 19:55
  • \$\begingroup\$ @flawr I'll try to clean up the first bit but addressing your second question. In the truthy examples a can be any member of the following sets {1}, {1,3}, {0,1,2,3,4}, {1,2,3} (same order as examples). \$\endgroup\$
    – Grain Ghost Mod
    Oct 5 '17 at 20:02
  • \$\begingroup\$ @flawr Is that a better explanation? \$\endgroup\$
    – Grain Ghost Mod
    Oct 5 '17 at 20:04
  • \$\begingroup\$ Yes now it is a lot clearer! One question remains, do you only consider abelian groups? \$\endgroup\$
    – flawr
    Oct 5 '17 at 20:29
  • \$\begingroup\$ @flawr No, the 4th test case is the dihedral 6 group which is not commutative. \$\endgroup\$
    – Grain Ghost Mod
    Oct 5 '17 at 21:02
  • \$\begingroup\$ In that case you'd probably be better off using multiplicative notation and explicitly saying that it is possible that the operation is noncommutative. \$\endgroup\$
    – flawr
    Oct 5 '17 at 21:05
  • \$\begingroup\$ I think you should add some more explanation about the input, without some knowledge of group theory one cannot understand what is a Cayley table or what to do with it. (You use just $Z4$ or $Z5$ in your explanation, but then there are tables in the test cases, which is confusing) \$\endgroup\$
    – Leo
    Oct 6 '17 at 4:34
  • \$\begingroup\$ Could use a test case where the number of distinct squares is at least half the size of the group but the group is not odd or even. \$\endgroup\$ Oct 6 '17 at 7:33
  • \$\begingroup\$ @PeterTaylor I'd rather not. The test cases are already much larger than the rest of the question, and there are not a lot of falsy cases. If there is such a case then it would be enormous. \$\endgroup\$
    – Grain Ghost Mod
    Oct 6 '17 at 13:04
1
\$\begingroup\$

Evaluate a Starting Position in a Partitioning Game


Two players play a partitioning game. At the start of the game, there are n stones, all in a single heap. When a player takes a turn, they must divide an existing heap into two, ensuring that every heap still has a distinct size. The game is over when a player has no legal moves; that player loses.

For example, suppose that Max and Min are playing with n=6. Initially it is Max's turn, and he divides the starting heap into a heap of size one and a heap of size five. Min then divides the heap of size five into heaps of size two and three (her only option because she cannot make another heap of size one). Max, seeing heaps of size one, two, and three, has no legal move and loses.

Alternatively, Max could have split the size-six heap into heaps of size two and four. But then Min could not split the heap of size two (she would end up with both new heaps having size one), nor could she split the heap of size four evenly (for the same reason), so she would be forced to split the heap of size four into heaps of size one and three. Max would have lost anyway.

Since Max, the player to move first, has no winning strategy at n=6, call six a losing number. Similarly, call values of n for which Max can win (at least if he plays cleverly) winning numbers. Max wants a way to distinguish winning and losing numbers for his upcoming rematch against Min.

Write a program or function that, given an n, returns or outputs one value for losing numbers and a distinct value for winning numbers. For testing purposes, the first 50 winning numbers are:

3, 4, 5, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 27, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 78, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93

(This sequence is related to, but distinct from A161983.)

Rules and scoring are as usual for . The checkmark will go to an answer with well-explained and/or especially clever golfing, even if it doesn't compete with terser languages.

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

Generate a program to output a string in yup

yup is an older language of mine with the following commands:

0   Pushes 0 to the stack.
e   Takes an argument N and pushes exp(N).
|   Takes an argument N and pushes ln(N).
~   Switches top two items on stack.
:   Duplicates the top item on the stack.
-   Subtracts the top of stack from the second-to-top of stack.
{   Begin while loop (while top of stack is positive and is defined).
}   End while loop.
$   Reverse the stack.
[   Moves the bottom of the stack to the top of the stack.
]   Moves the top of the stack to the bottom of the stack.
*   Pushes an input item (char/number) to the stack.
\   Terminates the program.
@   Outputs top of stack as a character. (When used on a non-int, rounds the real portion.)
#   Outputs top of stack as a number.

For example, the program 00e pushes 0, then 0, then pops a 0, pushing exp(0), yielding the stack [0, 1].

Rules

Your challenge, should you choose to accept it, is to create a program that, when given a string, outputs a short yup program that would output the given string. Your score is determined by the total number of bytes used to generate all test cases below.

Test cases

Formatted as a .JSON file (array of strings):

["Hello, World!", " !\"#$%&'()*+,-./0123456789:;<=>?", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "zyxwvutsrqponmlkjihgfedcba", "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz", "", "[[<<>>]]", "adksjf 9823-0 =-ao0sdf';zlx", "b662bf6c7a7cac66561025cf2509506f", "yup", " ~!}", "death surely will find us all", "NO_ONE_IS_HERE", "Ra Ra Rasputin", "hello\nWORLD", "*0e-{0e-}#", "            ", "go play nethack", "\ttabs\n vs spaces\r\n", ".", "~", "it is not necessarily unfair that we can single-handedly close challenges, --MrXcoder", "\nconst math = require(\"mathjs\");\nconst escape = require(\"escape-string-regexp\");\nconst Stack = require(\"./stack.js\");\nconst entries = require(\"./entries.js\");", "Never gonna give you up\nNever gonna let you down\nNever gonna turn around\nAnd outgolf you", "010100101000001000100111101010", "O0O0O0OOOO00O000O0OOOO0O00O0", "[0, [1, [2, 3], 4], 5]", "(()()()))))(()()))"]

If I feel submissions too heavily optimize for the given inputs, I will use a second set of words, with an md5hash of 30272eee598205bab2904e9768502517.

\$\endgroup\$
2
  • \$\begingroup\$ Will you use the second set of words for all submission or only the one you feel like it's optimized? Also why not just combine both sets in any case? \$\endgroup\$ Oct 26 '17 at 16:55
  • \$\begingroup\$ @BruceForte Once I feel that there are optimized answers, I will use the second list. (It's really just a variation of the first list with changed characters and similar, to ensure optimizing some constants but not others is prohibited) \$\endgroup\$ Oct 26 '17 at 17:13
1
\$\begingroup\$

The XOR Quines!

Your challenge is to make a program that outputs its source code but when each of its bytes are XORed with its answer number, it outputs the source code of the previous program.

For example, if the previous program was:

print 1

and your program is number #2, than your program could be this:

cngpv*%rpklv"3%+

which outputs in your language:

cngpv*%rpklv"3%+

and when each byte is XORed with 2, you get:

alert('print 1')

which outputs the previous program:

print 1

Note that the first program doesn't have to do anything other than output its own source code.

The second-to last answer after a month of no answers posted wins.

\$\endgroup\$
2
  • \$\begingroup\$ This is going to be too hardcore. \$\endgroup\$ Oct 25 '17 at 12:21
  • 1
    \$\begingroup\$ This is going to be way too hard except in certain esolangs. Since every answer builds off of the previous one, they are probably going to get bigger. I would recommend starting with a simple esolang that ignores most characters. \$\endgroup\$ Oct 25 '17 at 15:53
1
\$\begingroup\$

Insertion sort counter

Calculate the number of moves necessary to do an insertion sort of an input vector containing positive integers.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

You must count the number of times a number is moved from its original position. For instance, the vector [1,2,3,4] requires no moves, as it's already sorted, while the vector [1,3,4,2] requires one move, since the last 2 must be moved two places to the left.

Example:

Input: 
[6, 5, 3, 1, 8, 7, 2, 4]
Sorting:
0: [6, 5, 3, 1, 8, 7, 2, 4]
1: [5, 6, 3, 1, 8, 7, 2, 4]
2: [3, 5, 6, 1, 8, 7, 2, 4]
3: [1, 3, 5, 6, 8, 7, 2, 4]
4: [1, 3, 5, 6, 7, 8, 2, 4]
5: [1, 2, 3, 5, 6, 7, 8, 4]
6: [1, 2, 3, 4, 5, 6, 7, 8]
Output: 6

Test cases:

To be added!

\$\endgroup\$
8
  • \$\begingroup\$ You should describe what an insertion sort is, for those who don't know. \$\endgroup\$
    – Okx
    Oct 24 '17 at 9:13
  • \$\begingroup\$ Will do :) Thanks. \$\endgroup\$ Oct 24 '17 at 9:13
  • \$\begingroup\$ As defined, the answer is always len(input). I've no idea what the example is supposed to show (or how it's counting). \$\endgroup\$ Oct 25 '17 at 7:27
  • \$\begingroup\$ @PeterTaylor The number of insertions (maybe I should call it moves, or something else?) necessary for the array [1, 2, 3, 4] is zero. The number of moves for the array [1, 3, 4, 2] is one, since the only number that must be moved when using the insertion sort algorithm is the last 2, that must be moved two steps to the left, resulting in a sorted array. Placing a number back in its original position doesn't count as an insertion/move. Does that make sense? \$\endgroup\$ Oct 25 '17 at 7:58
  • \$\begingroup\$ So "Count the number of array elements a[i] which are not the greatest element in a[:i+1]"? \$\endgroup\$ Oct 25 '17 at 8:25
  • \$\begingroup\$ I guess that's another way to put it, yes... \$\endgroup\$ Oct 25 '17 at 8:53
  • 1
    \$\begingroup\$ Maybe you could have it count the number of swaps assuming that you can only move a number by swapping it with one of its neighbors (and many implementations of insertion sort actually do this, especially those operating on arrays). For example, the number of moves for [1,3,4,2] would be 2, because the number 2 must be shifted twice to the left. \$\endgroup\$
    – Leo
    Oct 26 '17 at 4:37
  • \$\begingroup\$ That's actually a good idea. Thanks! :) I'll probably change it when I get the time. :) \$\endgroup\$ Oct 26 '17 at 6:04
1
\$\begingroup\$

Tear Down that Wall

Related (dupe?)

  • This is my first time submitting a challenge.
  • Suggestions and constructive criticism are always welcome.

Cops:

As the cop, your task is to create a code that outputs this ASCII wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__

However, by deleting some part(s) of the code, it must also output a broken wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__

Rules:

  1. Your code must terminate in a reasonable amount of time as long as it's correct. That means that the whole code and the correctly broken code must output the wall (broken or not) within 60 (too much or too little time? sugestions?) seconds. That doesn't apply if the code is incorrectly broken by the robber.
  2. The broken wall needs to be output(ted? English is hard) without addition of code.
  3. You may obfuscate the code as much as you see fit. (does hashing/encrypting count as obfuscating? if so, should it be allowed?)
  4. You must state what language you used in your answer.
  5. Your wall will be safe if, after 1 week, it hasn't been broken. You must also reveal the answer. Your wall will not be safe until you have revealed the answer.
  6. The outputs must match the exact ASCII walls provided. Leading/trailing newlines are allowed as long as the output matches the one provided. The walls consist of 13 lines and 38 columns of the characters | and _. The broken section of the wall is a block of 20 whitespace characters per line, beginning at the fourth line. The "padding" is of 9 characters (| or _) to either side of the whitespace block.
  7. Preferably, include a link to an online interpreter for your chosen language.

(any other rules suggestions?)

Robbers:

As the robber, your task is to, well, break the wall!

Rules:

  1. You may not add any code to the answer, only delete.
  2. The code is considered broken if and only if it outputs the entire broken wall.
  3. The broken code must be a valid submission in the same language as the original code.
  4. Please include in your answer a link to the answer you cracked and which part(s) of the code you modified.

Sandbox:

  • Suggestions?
\$\endgroup\$
3
1
\$\begingroup\$

Does the Riemann hypothesis hold?

I would like to earn a million dollars, and the hardest way to do it is apparently solving one of the Millenium problems, so let's focus on one: the Riemann hypothesis.

Now, how could I possibly ever solve it? By writing a computer program, of course! However, I am lazy, so I would rather have you do the work for me by making the program as short as possible (to minimize the number of key strokes required for me to verify your results)

The challenge

Your goal is to write a program in a language of your choice which would decide the Riemann hypothesis. More precisely, you should write a program which terminates iff the Riemann hypothesis fails.

Restrictions

  • The program has to work when running with empty input [Sandbox note: perhaps allow input but add it to byte count?]
  • Standard loopholes are forbidden.
  • Your program must provably terminate iff RH is false. For example, submitting two programs, one trivially terminating, one trivially not terminating, and claiming one of them works, is not allowed, since neither of the programs provably works.
  • You must give a proof of equivalence of your program's termination with RH failing, with references to other work allowed. I give myself the right to decide whether the work referenced is valid or not, to exclude the many proofs and disproofs of RH.
  • If the Riemann hypothesis doesn't hold, your program can throw an error, or simply exit, as long as the program cannot continue beyond that.
  • You may assume you have unlimited memory and time, and also that your number types can hold real numbers of arbitrary size to arbitrary precision.
  • This is , so the shortest code in bytes wins!

Sandbox comment

To address the comments below, let me clarify why this challenge is most definitely solvable. Note that the problem is not of the sort "give a counterexample to RH" (if it did, then it would fall under this discussion and I completely agree it would not be a good challenge). Instead, it asks for a program whose termination depends on RH, and then one can give valid solutions regardless of the fact that RH is not solved yet.

To give an analogy (following Deedlit's example), suppose we have replaced RH with Goldbach's conjecture. This conjecture surely is unresolved, but one can give a valid solution to the challenge, for example by following this pseudocode:

n = 4
while true:
 found = false
 for k from 1 to n-1:
  if k is prime and n-k is prime:
   found = true
   break
 if found == false:
  break
 else:
  n = n+2
return 0

If Goldbach's conjecture is false, this program will eventually terminate by returning 0 (namely, when it finds the first counterexample). Otherwise, it will stay in the while loop forever. Hence it would be a valid solution.

My challenge as it stands can be solved in a similar manner, perhaps using

one of the many known equivalents of RH.

\$\endgroup\$
19
  • \$\begingroup\$ codegolf.meta.stackexchange.com/q/11033/45941 \$\endgroup\$
    – user45941
    Oct 27 '17 at 19:47
  • 1
    \$\begingroup\$ @Mego My proposed challenge doesn't fall under that discussion. It is not an open problem whether a solution for that problem is possible. \$\endgroup\$
    – Wojowu
    Oct 27 '17 at 19:51
  • \$\begingroup\$ Relying on open problems for challenges is not a good idea. Either it will be impossible to answer because the problem isn't solved, or answers will be trivial copy jobs of the proof once the problem is solved. This challenge relies on both an open problem (Riemann hypothesis) and an unsolvable problem (halting problem). \$\endgroup\$
    – user45941
    Oct 27 '17 at 20:42
  • 1
    \$\begingroup\$ @Mego The way I have phrased my problem makes it possible, but not trivial, once the Riemann hypothesis is unsolved. True, the problem trivializes once we get a (dis)proof of RH, but until then I don't see an issue with this problem. Also, I don't see how halting problem is in any way relevant here. \$\endgroup\$
    – Wojowu
    Oct 27 '17 at 20:58
  • \$\begingroup\$ You don't see how the halting problem is relevant in a challenge for writing problems that halt iff some unsolved problem in mathematics is true? \$\endgroup\$
    – user45941
    Oct 27 '17 at 20:59
  • 1
    \$\begingroup\$ @Mego Let me rephrase - I don't see how its unsolvability impacts the challenge in any way. \$\endgroup\$
    – Wojowu
    Oct 27 '17 at 21:01
  • 3
    \$\begingroup\$ @Mego As an example, it is straightforward to write a program that halts if and only if the Goldbach conjecture is false. Simply test out even numbers one at a time until you find one that is not the sum of two prime numbers. The unsolvability of the halting problem doesn't have any bearing on this, since we aren't relying on an algorithm that determines the halting behavior of all programs. A program that halts precisely when the Riemann Hypothesis is true could be done similarly. \$\endgroup\$
    – Deedlit
    Oct 27 '17 at 22:01
  • \$\begingroup\$ @Deedlit Can one also show that it is possible to write a program that halts iff Goldbach's conjecture is true? \$\endgroup\$ Oct 27 '17 at 22:31
  • \$\begingroup\$ @JonathanFrech I believe that's an open problem. However, thanks to your comment I've realized I have mixed things up - my challenge should've been about RH being false, not true (so just like in Deedlit's example with Goldbach). Sorry if any confusion was caused. \$\endgroup\$
    – Wojowu
    Oct 27 '17 at 22:43
  • \$\begingroup\$ @Wojowu Well, that seems solvable then. Would one, however, not simply loop through all complex numbers (as one has a lot of computational power), implement the zeta function (again, infinite computational power) and halt if they find a counterexample to the hypothesis? \$\endgroup\$ Oct 27 '17 at 22:49
  • \$\begingroup\$ @JonathanFrech It needs to be quite a bit more than that, because there are uncountably many complex numbers, so you can't loop over them all even with unbounded computing power. I believe you can do it by evaluating a contour integral around rectangles in the complex plane and looping over these rectangles. And it gets annoying around the critical line. It's definitely more complicated than just implementing the zeta function, though. \$\endgroup\$
    – Chris
    Oct 28 '17 at 1:58
  • \$\begingroup\$ @Chris Could one not loop through all possible sums of all rationals to approximate the reals, argue that every real is computable by an infinite sum of rationals, do that twice to gain a program which theoretically looks at every complex number, implement the zeta function and check if the hypothesis holds? \$\endgroup\$ Oct 28 '17 at 12:02
  • \$\begingroup\$ @JonathanFrech It's not possible to look at all possible infinite sums of rational numbers. Some (in fact, most) are uncomputable, and either way there are just too many real/complex numbers. Try to implement your algorithm in a real language like C, you will see that this simply doesn't go through. \$\endgroup\$
    – Wojowu
    Oct 28 '17 at 12:06
  • 2
    \$\begingroup\$ @JonathanFrech It is not possible to cycle through all possible complex numbers, but there are other ways which would let one verify the Riemann hypothesis. \$\endgroup\$
    – Wojowu
    Oct 28 '17 at 12:17
  • 1
    \$\begingroup\$ @Chris err, yes, that's what I meant. \$\endgroup\$
    – Wojowu
    Oct 28 '17 at 20:40
1
\$\begingroup\$

Square-free Rock-Paper-Scissors tournament

On the day of the Codegolf Rock-Paper-Scissors tournament you hear through the grapevine that everybody else is going to play a fix square-free sequence (a sequence made of the letters R, P, S is square-free if it does not contain a subsequence that repeats twice. See Don't repeat yourself in Rock-Paper-Scissors for details.)

Task

Write a program that for a game of N rounds, in each round n

  1. prints one of R, P, S - its own nth hand (using all information gained so far)
  2. receives an input of either R, P, S - the nth letter of the opponent's sequence

Rules

  • Rock beats scissors, scissors beats paper, paper beats rock.

  • The "opponents" are all the square-free sequences of the given length.

  • Your program may read the opponents moves at once and print its own moves - as long as it is functionally equivalent to a program reading the moves in the order specified in section "task".

  • The program does not carry a state between playing against different opponents.

  • Each entry should include a scoring script computing the score of the candidate against all square-free sequences of length N.

Scoring

I am posting this to get some input about interesting scoring methods and a good choice of N.

Programs should score high if they win against a large fraction of square free sequences in an economic way. A possible criterium of "winning" against a single sequence is winning more hands against an opponent than losing. A possible criterium of scoring high is number of games won divided by the root of bytes.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I'd say 16 could be a good choice for N, this would give 798 different opponents, which are still a manageable amount, and each game would probably be long enough to make the square-free analisys matter \$\endgroup\$
    – Leo
    Oct 31 '17 at 3:39
  • \$\begingroup\$ To win with a small margin it is enough to exploit that the sequence does not repeat. I think we need to put the winning margin into the score or put a threshold. \$\endgroup\$
    – mschauer
    Oct 31 '17 at 7:58
  • \$\begingroup\$ Maybe (rounds won - rounds lost)/bytes^2 , where rounds are counted from all the matches together \$\endgroup\$
    – Leo
    Oct 31 '17 at 8:50
1
\$\begingroup\$

Can You Catch the Robber?

This is not a cops and robbers type challenge, but a code-golf challenge based on the PBS Infinite Series video Cops and Robbers Theorem.

Challenge

You will be given an undirected and connected graph. You may also assume the graph contains no self-loops; that is, the graph will not contain a vertex with an edge connecting to itself. You must determine if the graph is cop-win. That means that if a cop and robber start at any vertex, the cop will eventually land on the same vertex as the robber, with the cop and robber taking turns traversing one edge at a time, starting with the cop. Both the cop and the robber are playing optimally and have the option to not move on their turn.

If you haven't watched the video, let me explain how to simplify the problem. First, let's start with a definition. A pitfall is any vertex v whose neighbors are all a distance of 0 or 1 from a common vertex w, where v is not equal to w. To determine if a graph is cop-win, you must repeatedly remove pitfalls and the edges that connect to it until the graph is reduced to a single vertex or there are no more pitfalls to remove. If the graph can be reduced to a single vertex in this way, it is cop-win. A couple visual examples follow.

Example 1

>o---o---o
  \ / \ /
   o---o
    \ /
     o

  o---o<
 / \ /
o---o
 \ /
  o

 >o
 / \
o---o
 \ /
  o

>o---o
  \ /
   o

 >o
 /
o

o

Result: Cop-win

Example 2

  o---o---o<
 /     \   \
o---o   o---o
 \   \ /   /
  o---o---o

  o---o
 /     \
o---o   o---o
 \   \ /   /
  o---o---o<

  o---o
 /     \
o---o<  o---o
 \   \ /
  o---o

  o---o
 /     \
o       o---o<
 \     /
  o---o

  o---o
 /     \
o       o
 \     /
  o---o

Result: Not cop-win

Examples

Input: [[2,3],[2,4],[0,1,3,4,6],[0,2,5,6,8],[1,2,6,7,9],[3,8],[2,3,4,8,9,10],[4,9],[3,5,6,10],[4,6,7,10,11],[6,8,9,11],[9,10]]
Output: Truthy

Input: [[3],[4],[5],[0,5,6],[1,6],[2,3,7],[3,4,8],[5,9],[6,9,10],[7,8,11],[8],[9,12],[11]]
Output: Falsy

Input: [[1,2],[0,3],[0,3],[1,2]]
Output: Falsy

Input: [[1,2,3],[0,2,3],[0,1,3],[0,1,2]]
Output: Truthy

Rules

You may take input as an adjacency list, adjacency matrix, or list of edges, whose vertices may be 0-indexed or 1-indexed. Your output must be a truthy or falsy value. This is , so the least number of bytes in each language wins.

Notes

This is my first post; I could certainly benefit from some help in formulating and polishing my challenge. If anyone believes my language was ambiguous or contradictory to what was said in the video, please help me clarify.

\$\endgroup\$
7
  • \$\begingroup\$ What is the input here? It looks a list of each vertex's neighbors, but could you clarify? \$\endgroup\$
    – KSmarts
    Oct 3 '17 at 15:16
  • \$\begingroup\$ Yes that's what I was going for, an adjacency list. A map of each vertex to a list of its neighbors. \$\endgroup\$
    – kamoroso94
    Oct 3 '17 at 16:34
  • 2
    \$\begingroup\$ This looks like a good question: meaty enough that there's something to golf, but simple enough not to scare everyone away. What I would suggest is flexibility in the input: allow people to choose whether to take input as adjacency matrix, adjacency list in the format you've used for the test cases, or list of edges. Also, allow people to use 1-indexed vertices rather than 0-indexed if they prefer. \$\endgroup\$ Oct 10 '17 at 8:18
  • \$\begingroup\$ I definitely agree with your suggestion of input leniency. I'll update the challenge. \$\endgroup\$
    – kamoroso94
    Oct 12 '17 at 8:57
  • 1
    \$\begingroup\$ I'd suggest explaining what a cop-win graph is in full, including the start positions and that both players play an optimal strategy. A link to a non-video explanation would also be good for anyone who can't or doesn't want to watch a video. \$\endgroup\$
    – xnor
    Oct 12 '17 at 21:06
  • \$\begingroup\$ Thank you for the feedback, @xnor. I've worked it into the challenge. I feel it's an improvement. I think that the visual examples take up too much vertical space, so I'm not sure if I should include them or not. \$\endgroup\$
    – kamoroso94
    Oct 31 '17 at 2:17
  • \$\begingroup\$ IIRC it shouldn't be "start at any vertex", but the selection of the start position is part of the game, also under condition of optimal play, with the cop selecting their position first. \$\endgroup\$ Oct 31 '17 at 13:00
1
\$\begingroup\$

Polynomial Partition

META: Right now I'm wondering whether it would be a more interesting challenge to have two imput lists, and the program just needs to find a polynomial that separates the two lists (i.e. no connected component can contain points of both classes. Or altnernatively f(x,y)>0 for all (x,y) in list A, and f(x,y)<0 for all (x,y) in list B.

Given a finite list of at at least two points in the plane ℝ² (all points in the list are unique), your program should find a polynomial f in ℝ[x,y] whose zero locus Z(f) := {(x,y) ∊ ℝ² | f(x,y) = 0} partitions the plane such that each of the connected components of ℝ²\Z(f) contains at most one point of the input list. The goal is finding such an f of a low degree. (It does not have to be optimal.) Note that no point of the input list may be contained in Z(f).

Scoring

The score for each test cases is the degree of the polynomial that your algorithm produces. The total score is the product of the scores of the testcases.

Examples

The points {(0,0),(0,2)} can be separated by f(x,y) = y - 1 (degree 1) or f(x,y) = x² + y² - 1 (degree 2) or f(x,y) = x³ + 1 - y(degree 3) or (infinitely) many more.

The points {(1,1),(-1,1),(-1,-1),(1,-1)} can be separated by f(x,y) = xy (degree 2).

Test Battery

to be included...

\$\endgroup\$
2
  • 1
    \$\begingroup\$ (1) I presume that the words "a different" are missing from "each of the inputs is in ^one of the connected components". (2) Is the optimal solution not going to be one of the easiest approaches? \$\endgroup\$ Nov 3 '17 at 11:44
  • \$\begingroup\$ Thanks for the feedback, I rewrote (1), regarding (2): One very easy not optimal solution would be making a a small enough circle around every point, so I guess it depends. \$\endgroup\$
    – flawr
    Nov 3 '17 at 14:43
1
\$\begingroup\$

Palindromic Collapse

Given a string s, traverse from left-to-right, finding the first prefix that is a palindrome. When you encounter the first prefix palindrome, remove the end-half of the palindrome. Insert it back into the original string, then restart again from the left side of the new word. Return the final result when no prefixes are palindromes.

Take for example "babble":

  • First check would be [ba]bble, which is not a palindrome, move on.
  • Second check would be [bab]ble, which is a palindrome (bab).
    1. Compress the palindrome to the first "half", [bab] becomes [ba].
    2. Reattach this in place of the original palindrome, resulting in [ba]ble
  • Next we repeat, finding [bab]le again, and resulting in [ba]le after steps 1 and 2.
  • We then iterate through the full word again, finding no palindromes, returning bale.

More Examples (worked out)

moom

[mo]om (not a palindrome)
[moo]m (nont a palindrome)
[moom] (palindrome) -> [mo]
[mo]   (not a palindrome, done).

Final returned result: mo


abalbalba

[ab]albalba (not a palindrome)
[aba]lbalba (palindrome) -> [ab]lbalba
[ab]lbalba  (not a palindrome)
[abl]balba  (not a palindrome)
[ablb]alba  (not a palindrome)
[ablba]lba  (palindrome) -> [abl]lba
[ab]llba    (not a palindrome)
[abl]lba    (not a palindrome)
[abll]ba    (not a palindrome)
[abllb]a    (not a palindrome)
[abllba]    (palindrome) -> [abl]
[ab]l       (not a palindrome)
[abl]       (not a palindrome, done)

Final returned result: abl


More 1-1 Examples

amanaplanacanalpanama -> amnaplanacanalpanama
1232132121            -> 123
1232132145            -> 12345
01001000123210        -> 01123210
01000000000000000001  -> 011
010101                -> 011
abbabababaa           -> ab
hellollehworld        -> helloworld
world                 -> world
<empty string>        -> <empty string>
\$\endgroup\$
2
  • \$\begingroup\$ You like palindrome a lot, don't you? \$\endgroup\$
    – Mr. Xcoder
    Nov 7 '17 at 20:00
  • \$\begingroup\$ @Mr.Xcoder in all fairness it looks like Oliver Ni likes them more. \$\endgroup\$ Nov 7 '17 at 22:06
1
\$\begingroup\$

Validate a StarCraft II Build Order

Explanation

You must decide whether the input represents a valid StarCraft II Build Order. Here is how you will decide:

  1. Start with the first word (it will be the race, Zerg, Protoss, or Terran)
  2. Set the list of valid units to just the ones from that race (explained later)
  3. Loop through the input (split by space)
    1. Check if the unit is in the list of valid items for the listed race
      • Otherwise, output Invalid item + the listed item's name
    2. Check that the player has enough supply to sustain that unit (if it's a unit) (explained later)
    3. Check that the player has the prerequisites for that item

Units and Structures

(will be listed in real question)

Example:

Terran:

  • CommandCenter 0 supply, requires SCV gives +15 supply
  • OrbitalCommand 0 supply, requires CommandCenter (consumes)

Zerg:

  • Hatchery -1 supply, requires Drone (consumes) gives +6 supply
  • Drone 1 supply, requires Hatchery
  • SpawningPool -1 supply, requires Hatchery, Drone (consumes)

Protoss:

  • Nexus 0 supply, requires Probe gives +15 supply

StarCraft II Mechanics

At the beginning of the game, the player starts with a town hall (Nexus, CommandCenter, or Hatchery + Overlord) and 12 workers (Probe, SCV, or Drone).

Supply is the maximum number of units one can have. Supply Depots, Pylons, and Overlords give more supply.

The sum of the supply of all produced units can never exceed the current supply value (we ignore Zerg hacks).

The Supply cannot exceed 200.

Input

You will receive an input in any valid way in this format:

Race <item> <item> .....

There will be at most 99 items, and they will be at most 30 chars long.

The race will be one of Zerg, Protoss, or Terran.

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

Lines per file

Can't believe it was not questioned yet.

I want the shortest script you can supply to take on all files on a directory and output a list in the format

file number_of_lines

Every possibility should be accounted as a valid line terminator:

- <CR>
- <LF>
- <CR><LF>
- <LF><CR>

No winner, it is a per language basis. Still thinking if I should give some bonus for sorting by line count.

\$\endgroup\$
3
  • \$\begingroup\$ Duplicate. Not the same but pretty much the same idea, would definitely get closed for dupeness. \$\endgroup\$ Nov 14 '17 at 18:58
  • \$\begingroup\$ @Riker: Counting lines requires some more effort than the file's byte size! I had even posted an answer on that question! \$\endgroup\$
    – sergiol
    Nov 14 '17 at 21:18
  • 1
    \$\begingroup\$ It's literally just wc -l to count lines.. I'm not sure about most of the others, but I know at least my bash can be trivially modified to count lines. \$\endgroup\$ Nov 14 '17 at 21:33
1
\$\begingroup\$

Prune my tree

Given a well-formed ASCII art tree and the name of a node, print or return a new, well-formed tree with that node and any children removed.

†Contains non-ASCII characters.

Example

Given this input tree:

A
├ B
├ C
│ └ D
└ E

...and the node name E, the following should be returned:

A
├ B
└ C
  └ D

Well-formed trees

Rather than an exhaustive spec, I'll define well-formedness by example:

A
├ B
├ C
├ D
│ ├ E
│ └ F
├ G
│ └ H
│   ├ I
│   │ ├ J
│   │ └ K
│   └ L
└ M
  ├ N
  │ └ O
  │   └ P
  ├ Q
  └ R

The above is the only valid way to represent this tree (rules above re: trailing spaces and newline apply here and henceforth). Note that:

  1. The tree is rendered with some strict subset of the characters , , , AZ, space, and newline.
  2. The tree has one root node (in this example A) with no characters to its left or right.
  3. Each line has exactly one node.
  4. Each and is followed by a single space (required) and node name.

Rules

  • Standard loopholes are forbidden.
  • This is an challenge; input and output must be a string or array of lines or equivalent, per standard rules.
  • Trailing spaces and/or a single trailing newline are allowed in both input and output.
  • You may use any character encoding, as long your solution prints or returns characters equivalent to , , and . (ASCII characters like +, | (pipe) and L (capital "l") are not equivalent.)

    See also "Freebies" under "Scoring" below.

Input

  • The input tree will have at least one node.
  • The given named node may or may not exist in the tree. If it does not exist, the original tree should be returned.
  • Each node name will be a single character between A and Z inclusive. Node names will be unique and there will be no more than 26 nodes.
  • Node names are not guaranteed to be contiguous nor in any particular order, e.g. the following is possible input:

    Q
    └ D
    

Output

  • The output tree may have zero nodes.
  • The order of the remaining nodes in the output tree must be the same as the input tree.

Scoring

This is . The shortest solution in bytes wins.

🌟Freebies🌟: If the literal characters , , or appear in your source code, you may count them as one byte each, per occurrence.

Test cases

I'll reuse a few trees for multiple test cases.

  1. Input tree:

    A
    
    • Output if A removed:

      
      
    • Output if B removed (B doesn't exist):

      A
      
  2. Input tree:

    A
    ├ B
    ├ C
    │ └ D
    └ E
    
    • Output if C removed:

      A
      ├ B
      └ E
      
    • Output if D removed:

      A
      ├ B
      ├ C
      └ E
      
    • Output if E removed:

      A
      ├ B
      └ C
        └ D
      
  3. Input tree:

    A
    ├ B
    ├ C
    ├ D
    │ ├ E
    │ └ F
    ├ G
    │ └ H
    │   ├ I
    │   │ ├ J
    │   │ └ K
    │   └ L
    └ M
      ├ N
      │ └ O
      │   └ P
      ├ Q
      └ R
    
    • Output if H removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if L removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      │ └ H
      │   └ I
      │     ├ J
      │     └ K
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if M removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      └ G
        └ H
          ├ I
          │ ├ J
          │ └ K
          └ L
      

Questions for sandbox:

  1. Enough/too many/missing test cases?
  2. Enough/too many/missing details re: input/output?
\$\endgroup\$
4
  • \$\begingroup\$ I would just make this an (actual) ASCII-art challenge. Up to you but meh \$\endgroup\$
    – hyper-neutrino Mod
    Nov 13 '17 at 19:24
  • \$\begingroup\$ Given the proximity to Christmas, you could go for "trim the tree" as the title. \$\endgroup\$
    – Nissa
    Nov 13 '17 at 21:47
  • \$\begingroup\$ I think you should show the larger test case(s) with A removed. I know/guess it will be an empty output, but still, it's a corner case that will benefit from being properly shown. \$\endgroup\$ Nov 15 '17 at 12:24
  • \$\begingroup\$ I like the idea, but I too would prefer ASCII-only. Non-ascii adds a bunch of bytes without adding anything to the challenge itself. \$\endgroup\$ Nov 15 '17 at 12:29
1
45 46
47
48 49
119

You must log in to answer this question.

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