459
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2562 Answers 2562

1
\$\begingroup\$

Interpret a Maximal Number of Brainf*** Variants

A while ago in chat, I had an idea:

enter image description here

It was prompty shot down as impossible. Because of that, I'm making it a challenge!

Valid Languages

The only valid brainfuck variants you can use are the languages appearing on this link and this link (along with regular brainfuck, of course). Those two links are July 3rd, 2017 captures of the esolangs.org pages for brainfuck derivatives and brainfuck equivalents.

The Task

Your task is to create one program that, when fed code from any variant of brainfuck you say you can interpret, along with input for that program, will execute that code according to the spec of that variant. You cannot tell the interpreter beforehand what variant it is supposed to interpret.

There is one very important note: in brainfuck, for example, all characters not used are ignored as comments. Any program that is entered will not contain comments. All input will only contain characters that are not ignored by the spec.

Knowing this, if two variants of brainfuck overlap enough that you cannot differentiate between two valid, however short, programs in them, and if each language wants a different result, you can only include one of those languages.

Scoring

The most important part of this challenge is maximizing the number of variants you can support. However, you also don't want to make it too long. Therefore, the following is your score:

(variantsSupported * 300) - interpreterBytes

Highest score wins.

\$\endgroup\$
  • \$\begingroup\$ yeah the problem is that ignored characters are not well defined. that is, any string of characters, excluding [ and ] (they might be misbalanced) is a valid bf program. that's a part of the spec pretty much \$\endgroup\$ – Destructible Lemon Aug 2 '17 at 23:25
  • \$\begingroup\$ @DestructibleLemon I'm (trying) to remove that from the spec - if part of the spec is that some chars are no-ops, your interpreter does not have to handle them \$\endgroup\$ – Stephen Aug 2 '17 at 23:35
1
\$\begingroup\$

I've got a challenge, but I'm not quite sure how to implement it in a way that's on-topic. It's possible this type of question just doesn't mesh with PPCG, but that's what the SandBox is for, right?

The gist is that I want a sort implemented lazily. So lazily that you don't actually write one, you steal someone else's. Your code should take an input, find/scrape an existing sorting algorithm off StackExchange (just PPCG?), run it, and output the sorted list.

Here's what I've got so far:

The Laziest Sort

I need a program that sorts a list, but man am I lazy. I don't mean "I'll just write a bubble sort and call it a day" lazy, but "I don't even want to write any sort at all" lazy. In fact, I don't even want to look at a sorting algorithm.

Given a list of numbers, I want you to return to me a sorted list. But like I said, I don't want to look a sorting algorithm. Instead, I want you to go find an existing sorting algorithm, run it, and tell me what it said.

The rules (This is part of where I need the SandBox)

  • You may not use any native sorting algorithms (like Collections.sort()).
  • You may use any sorting algorithm you can find, so long as it is from StackExchange.
  • You may import the code from the algorithm you use and run it from your answer, so long as the actual algorithm isn't in your source code.
  • Anything other requirement this challenge needs? I feel like this describes the problem I have in mind, but I've only made a few questions and they're typically math/array based.

Scoring

seems an odd tag here, but seems to be frowned upon. Especially since I don't have a great question formed yet, but I feel like I've got a reasonable idea here. Any tips on how to get this question presentable enough to actually post?

\$\endgroup\$
  • 1
    \$\begingroup\$ Yeah, we have a tag for this. It's called duct-tape-coding \$\endgroup\$ – geokavel Aug 5 '17 at 4:41
  • \$\begingroup\$ I would use code-golf for this personally. \$\endgroup\$ – Gryphon Aug 8 '17 at 2:42
  • \$\begingroup\$ You mean, implement Stacksort? :) (not exactly the same, but very similar) \$\endgroup\$ – Sanchises Aug 8 '17 at 11:27
1
\$\begingroup\$

Ah, Polish notation is always so confusing... [ABANDONED]

...so I order you to show me just how it works!That is, if you accept the challenge of course. For example, I can't even determine if xyz01 is supposed to do x(y(z(0)),1) or x(y(z(0),1)), if I don't know the arities. And, even if I know the arities, I can't understand what 20121012100 does in first glance (I have to think much to realize it's 2(0,1(2(1(0),1(2(1(0),0)))))). So, please, make my life easier.


Your challenge is, given a string, to "aritify" it. Here's how you do it:

First, you get a string (expression) containing up to 3 distinct chars, representing operators/functions with specific arities 0, 1 and 2.

Then, you convert the string to function-call representation, separating arguments with ,s and enclosing them in ()s (e.g. 212110102010 -> 2(1(2(1(1(0)),1(0))),2(0,1(0)))). This is the string you will return.

Rules

  • You are guaranteed that you are only given one expression (e.g. never something like 120010 -> 1(2(0,0))1(0) which contains more than one expression as a whole). Also, the input will never be empty.
  • There will not be missing trailing arguments, so something like 20 -> 2(0,the heck?) will never occur.
  • You may choose any 3 chars for the arities (e.g. n for 0, m for 1, d for 2), but you must specify them in your answer. You can't use any of ()[]<>{},; or space.
  • For the brackets, you may choose any one of (), [], <> or {}.
  • For the argument separator, you may choose ,, ; or (space). Also, the separator may have a trailing space, or both a trailing and a leading space, if it isn't a space. You must use a separator, it makes my life easier (how am I supposed to be able to read 211012101200 as 2(1(1(0))1(2(1(0)1(2(00))))) instead of 2(1(1(0)),1(2(1(0),1(2(0,0)))))? It's not properly organized.)
  • Chars defining arities must be outside the brackets, to the left, so something like 1200 -> ((0,02)1) or ((0,0)2)1 is disallowed instead of 1(2(0,0)). I want to know what operator it is before I start reading the arguments.
  • The 0-arity operator must not have appended brackets (e.g. 210110 -> 2(1(0),1(1(0))), not 2(1(0()),1(1(0())))), it's just useless cluttering that reduces simplicity, since you can always treat them as literals.
  • You may not omit the operator names (e.g. 221010121100 -> (((),()),(((()),))) is disallowed, 2(2(1(0),1(0)),1(2(1(1(0)),0))) is correct).
  • The chars used for input must be the same as those used for output.

Test cases

Most of these test cases are already in this post, I've just summed them up here and added some more. I used 012 as arities, ()s as brackets and , as separator here.

Input        -> Output

20121012100  -> 2(0,1(2(1(0),1(2(1(0),0)))))
212110102010 -> 2(1(2(1(1(0)),1(0))),2(0,1(0)))
211012101200 -> 2(1(1(0)),1(2(1(0),1(2(0,0)))))
1200         -> 1(2(0,0))
210110       -> 2(1(0),1(1(0)))
221010121100 -> 2(2(1(0),1(0)),1(2(1(1(0)),0)))
10           -> 1(0)
0            -> 0

Sandbox

  • Please comment if there's any error in the test-cases.
  • How could I make this challenge better?
  • Bumps: 3
\$\endgroup\$
  • \$\begingroup\$ Can I adopt and post this abandoned proposal? \$\endgroup\$ – programmer5000 Jun 9 '17 at 1:38
  • \$\begingroup\$ @programmer5000 Not entirely abandoned yet. \$\endgroup\$ – Erik the Outgolfer Jun 9 '17 at 7:53
1
\$\begingroup\$

The Mode of an Image

Given an image as input, output it's mode; that is the colour that appears most in it. However, I am on a tight schedule and so need this code to compute as fast as possible.

Input

Input can be in any reasonable format for your program i.e. filename or image object. However, the input image must have at least 3 channels i.e. r, g, b or 24bpp.

Output

Output can be by any reasonable means i.e. return of a method or print to STDOUT.

Test Cases

//TODO: add them

Scoring

As this is the winner is the answer which scores the lowest total time over all of the test cases. For example, if there are two test cases then the score = timeForTestCase1 + timeForTestCase2.

In the even that more than one winning answer scores the same more test cases will be added. The winning answers will be notified and should be updated accordingly.

Sandbox

  • Test case suggestions?
  • Better scoring mechanism? i.e. average of the time for each test case
\$\endgroup\$
  • \$\begingroup\$ Will all input images be of the same dimensions? \$\endgroup\$ – Cows quack Aug 10 '17 at 15:11
  • \$\begingroup\$ @Cowsquack No they will vary \$\endgroup\$ – TheLethalCoder Aug 10 '17 at 15:12
1
\$\begingroup\$

Will it rain?

The challenge is essentially: given an image of the sky (without foreign entities in the way like birds, trees, or my brother), predict whether or not it will rain in the next hour or so. To generate these test cases, I will take a picture of the sky and check if it rains, repeating this procedure many times (making sure to go take pictures right before forecast periods of rain).

Your program must give the correct result for at least 50% of the provided test cases. The input will be the filename of a local file in JPG or PNG format. The output should be a single value indicating whether or not it will rain in the next hour or so, as a boolean, one of two distinct values, or any other sort of distinguishable message.

Test cases to come, if people like this idea

Winning

As this is a , the answer with the highest score (upvotes - downvotes) wins. However, no answer will be accepted


Meta

  • This question is probably unclear right now, but this is just to get a general idea for whether or not people would like this challenge.
  • Is this a duplicate?
  • Is the criterion tag () appropriate for this challenge?
\$\endgroup\$
  • 4
    \$\begingroup\$ If you have to ask if pop-con is appropriate here I think this challenge is already doomed as a pop-con. But why don't you use it as a test-battery-challenge and use the percentage of correct ones as a criterion? \$\endgroup\$ – flawr Aug 8 '17 at 21:40
  • \$\begingroup\$ This challenge rests on the test cases, if the skies have distinct features in them when it rains to when it won't i.e. darker it should be fine. If they all look similar it will never work. \$\endgroup\$ – TheLethalCoder Aug 9 '17 at 10:44
1
\$\begingroup\$

Left or Right?

You have a carousel of images, and you know the index of the image you wish to view.

The carousel shows a few images per page, so you need to be able to calculate if you need to move at all.

Also, the carousel wraps - so you can click 'right' on the last page to go to the first page, and 'left' on the first to go to the last.

The first image on the first page is at index 0 - and the last page may not, depending on the amount of images, always be full. If you prefer, you may start your indexing at 1 instead, but remember that the indexes in all of the example inputs will need to have 1 added to them.

Input

4 numbers, in whatever format is suitable for your language;

  • Total - The amount of images in the carousel (1 or greater)
  • PageSize - The amount of images per section in the carousel
  • CurrentIndex - The index of the image you are currently looking at (0 to Total-1)
  • DestinationIndex - The index of the image you wish to look at.

Output

The desired direction to scroll (if at all). This should be the fastest direction (ie least amount of clicks), desiring right in the case of a tie.

Either;

  • L - Click the left button (ie, go backwards)
  • R - Click the right button (ie, go forwards)
  • N - No movement required - output this if the image you seek is on the same page as your current image.

If you prefer, you may specify 3 other distinct outputs, such as -1 0 and 1 for example.

Examples

Say we have 5 3 0 4, so 5 total images, a page size of 3, we're currently at image index 0, aiming for 4. Our carousel would look something like this:

< [0 1 2] >

Pressing either left or right (there are only 2 pages) would lead us to this:

< [ 3 4 ] >

On this page, we can see image 4 which we are aiming for, so in this example, you would be expected to return R. Although L is the same length, in this exercise we are to favour going right in the case of a tie. Also note that you are expected to return just the direction you would need to go, so if you would have to click R 3 times, still only return one R.

Here are some more test cases;

5 2 0 2 -> R
10 5 1 4 -> N
10 3 8 1 -> R
10 3 8 4 -> L
\$\endgroup\$
  • \$\begingroup\$ I think this is kind of easy for this is site. One suggestion I have is to make the carousel "broken", such that it moves by n pages per click, instead of 1. Then a fourth output would be "X", saying that it's impossible to reach a certain image. \$\endgroup\$ – geokavel Aug 9 '17 at 2:45
  • \$\begingroup\$ You should allow 1-indexing and not force everyone to use 0-indexing. Also the first test case is returning L or R allowed or should you prefer to return R over L always? \$\endgroup\$ – TheLethalCoder Aug 9 '17 at 10:35
  • \$\begingroup\$ @geokavel I don't think that's necessary, easy challenges are still good challenges. \$\endgroup\$ – TheLethalCoder Aug 9 '17 at 10:35
  • \$\begingroup\$ Guess it's ok as is. \$\endgroup\$ – geokavel Aug 9 '17 at 16:49
  • \$\begingroup\$ TheLethalCoder good point, I did mean to do that, but forgot to mention it. Also I did mention that in the first paragraph of the output section, but I'll reiterate it in the example paragraph you refer to. geokavel - Thanks for your input - but I personally would like to see a few more easier challenges on this site to encourage newbies (like myself) \$\endgroup\$ – Shadow Aug 9 '17 at 23:39
  • \$\begingroup\$ @TheLethalCoder - actually, using 1 based indexes would change the input as well. Do we still generally allow that when the input is going to change? \$\endgroup\$ – Shadow Aug 9 '17 at 23:42
  • \$\begingroup\$ @shadow Yes we usually allow people to use 0 or 1 indexing irrespective of whether the input changes or not. \$\endgroup\$ – TheLethalCoder Aug 10 '17 at 7:52
  • \$\begingroup\$ Could we output, for example, 1, -1, and 0 instead of R, L, and N? \$\endgroup\$ – Stephen Aug 10 '17 at 19:23
  • \$\begingroup\$ @StepHen - I don't see why not. \$\endgroup\$ – Shadow Aug 10 '17 at 23:06
1
\$\begingroup\$

Archer Battle

Your challenge is to simulate a battle between two armies of archers.

Each army has a population and an accuracy. Each round, every archer will let fly an arrow at the enemy army. The archers are trained each to shoot at different targets. Any archer hit by an enemy arrow is eliminated, and is does not participate in the next round. The battle is over when all archers in one or both armies have been eliminated.

The accuracy of the archers is almost exact. That is, ceil(population * accuracy) arrows will hit their targets. (No need to use random number generation.)

Input

Take 4 inputs in any reasonable manner:

  • Army 1 population (positive integer)
  • Army 2 population (positive integer)
  • Army 1 accuracy (nonnegative float)
  • Army 2 accuracy (nonnegative float)

Output

Output the population of the winning army at the end of the battle.

\$\endgroup\$
  • 1
    \$\begingroup\$ What if there are more archers than targets, and so they can't all shoot at different targets? \$\endgroup\$ – isaacg Aug 12 '17 at 11:39
  • \$\begingroup\$ @isaacg Good point. I suppose "every archer selecting a different target" doesn't match the model perfectly. Perhaps "The archers distribute their targets among the opposing army as evenly as possible." and "`ceil(population * accuracy) enemies will be struck by arrows (capped at the remaining population of the opposing army, of course)." Any suggestions on improving the wording? And would a sample program help? \$\endgroup\$ – Matt Aug 12 '17 at 23:31
1
\$\begingroup\$

Intertwined Polyglot

Write a program which when executed as language A, produces a different program in language B, which in turn produces the name of language A. And the other way round (B to A to B).

+-----------+   Lang. A    +-----------+   Lang. B
| Program 1 | -----------> | Program 2 | -----------> "<Lang. A>"
|           |              +-----------+
|   Your    |              +-----------+
|  Program  | -----------> | Program 3 | -----------> "<Lang. B>"
+-----------+   Lang. B    +-----------+   Lang. A

Rules

  • The produced programs must be unique both from each other, and from the original program.
  • Uniqueness is defined as at least one modified or moved printing character. Example: a bc => ab c would not be considered unique, whereas a bc=> a cb would.
  • The output may contain leading and/or trailing whitespace and/or newlines, so long as the language name is intact.
  • Your program(s) may not take any input.
  • This is , so fewest bytes wins.
\$\endgroup\$
  • \$\begingroup\$ I couldn't find a matching question... but I really think this might be a dupe.. \$\endgroup\$ – officialaimm Aug 10 '17 at 12:20
  • \$\begingroup\$ You should define "unique". Does 1 character difference count? Can it be a hidden character (CR,...)? \$\endgroup\$ – Goufalite Aug 10 '17 at 12:49
  • \$\begingroup\$ @officialaimm That's what I thought too, but I had no luck finding it either \$\endgroup\$ – MTCoster Aug 10 '17 at 13:03
  • \$\begingroup\$ @Goufalite I would say yes to a single character, but I'm not sure about whitespace. For some languages it's integral, but others will ignore it \$\endgroup\$ – MTCoster Aug 10 '17 at 13:05
  • \$\begingroup\$ I believe this is the duplicate you guys are thinking of. cc @officialaimm \$\endgroup\$ – ETHproductions Aug 11 '17 at 21:01
  • \$\begingroup\$ @ETHproductions Nope, not that one... I don't even know if there is a dupe, I just doubt there might be one.. \$\endgroup\$ – officialaimm Aug 12 '17 at 3:25
  • \$\begingroup\$ The "And the other way round" should be emphasized more. On my first read, I though only A to B to A was necessary. An example would solve this and make the challenge easier to understand overall. \$\endgroup\$ – fireflame241 Aug 14 '17 at 1:31
  • \$\begingroup\$ @fireflame241 Does the diagram I've added help to ease understanding? \$\endgroup\$ – MTCoster Aug 14 '17 at 8:42
  • \$\begingroup\$ @MTCoster absolutely. However, it looks like Program 1 and Your Answer are different. Remove the dividing line? \$\endgroup\$ – fireflame241 Aug 14 '17 at 13:55
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\$
  • 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\$ – Peter Taylor 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\$ – Peter Taylor 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\$ – Kevin Cruijssen Aug 18 '17 at 6:49
1
\$\begingroup\$

Numbers to Algorithms

Another horrible part of Cubically is attempting to print numbers when the notepad is occupied. Since you can't add up existing faces, the integer (or ASCII value) you have to print needs to be on one single face.

The maximum value you can store on one Cubically face is 45. This isn't great, but it's better than nothing. Your challenge is to write a program that automates the process of getting the values 0-45 onto the top face.

Your program will take an input number n and produce a Cubically code snippet as output. This Cubically snippet should achieve the task of getting all integers on the top face to sum up to n. If you don't yet know how Cubically works, go check out the repo. Here's a run-down of all you need to know.

Cubically is my esolang based on a Rubik's Cube. Its 3x3x3 memory cube is initialized like this (without the comments on the right):

   000
   000          top face
   000
111222333444    left, front, right, and back faces, respectively
111222333444
111222333444
   555
   555          down face
   555

It uses quarter turn notation, so RRLL turns the cube to look like this:

   505
   505
   505
111424333242
111424333242
111424333242
   050
   050
   050

Now the sum of the top face is 30. So if n is 30, RRLL would be a valid output.

In addition to quarter turn notation, you can send a subscript number to face turns to mean "turn the xth layer inwards from the [face] face, where x is the subscript number". So R1 would turn the cube to look like this:

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

Arbitrary base conversion

Given an integer n of any sign, output a list of digits of its representation in a given base b not in -1, 0, 1. If b is positive, n will be non-negative.

Rules:

  • You may not use arbitrary base conversion built-ins like Jelly's b or 05AB1E's в.
  • You may assume the input is valid, as above.
  • All digits must be greater than or equal to 0 and strictly less than b.
  • For zero you must return [].

Test cases

256, 10 -> [2, 5, 6]
256, -10 -> [3, 5, 6]
1000, 25 -> [1, 15, 0]
1000, -30 -> [2, 27, 10]
0, 300 -> [0]
1000, 1000 -> [1, 0]
18446744073709551615, 4 -> [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
18446744073709551615, -5 -> [3, 3, 2, 1, 3, 3, 1, 2, 1, 2, 2, 3, 0, 1, 1, 4, 0, 2, 0, 4, 3, 4, 2, 3, 3, 1, 4, 4]

Sandbox

Is this a dupe?

\$\endgroup\$
  • \$\begingroup\$ I'd suggest 0 in any base be the empty array, so it doesn't need special handling from recursive solutions and the like. \$\endgroup\$ – ETHproductions Aug 6 '17 at 21:57
  • \$\begingroup\$ @ETHproductions Let's see...well, [0] shouldn't actually need special-case handling if you put the sum check before the special cases...but otherwise I did consider []. \$\endgroup\$ – Erik the Outgolfer Aug 7 '17 at 8:47
  • \$\begingroup\$ We had this challenge which was closed as dupe of that challange. \$\endgroup\$ – nimi Aug 20 '17 at 18:10
  • \$\begingroup\$ @nimi Hmm...from the title you would guess that it's about converting to bases 2..36 although that doesn't seem to be the case so not sure if this is a dupe or something. \$\endgroup\$ – Erik the Outgolfer Aug 20 '17 at 18:29
1
\$\begingroup\$

Bomberman

Given an input Bomberman board b, use the following characters to define the different bomberman tiles:

  • X denotes the outer boundary of the board.
    • X is always in each of the four corners of the board.
    • X may only be on the boundaries of the board.
  • - denotes an empty space.
    • When a bomb blows up over an empty space, it replaces it with *; and may continue.
  • o denotes a blocker that is breakable.
    • When a bomb blows up over a breakable blocker, it replaces it with *; and stops.
  • O denotes an impenetrable blocker.
    • When a bomb reaches an impenetrable blocker, it stops prior to it.
  • 0-9 describes a bomb of n power.
    • When a bomb explodes it explodes in a plus pattern.
    • A bomb of 0 strength would be: *.
    • A bomb of 1 strength would be: * \n***\n *
    • And so on... 1-indexing is not okay because that would make the 9 bomb a 10 bomb.

Worked Example

An example board would be (without bombs):

XXXXXXXXXXXX
X----------X
X-oo---O---X
X--------O-X
X--OoO-----X
X----------X
X--O-------X
X-------O--X
-----o------
X---------OX
X--O---o---X
XXXXXXXXXXXX

If we were to add some randomized bombs to this board we would see:

XXXXXXXXXXXX
X----------X
X-oo-1-O---X
X--------O-X
X--OoO--0--X
X---1------X
X--O-3-----X
X-------O--X
--4--o------
X---------OX
X--O-2-o---X
XXXXXXXXXXXX

This should, when input to your program, output the following explosion pattern:

XXXXXXXXXXXX
X----*-----X
X-oo***O---X # This didn't get blocked, it's just a small explosion.
X----*---O-X
X-*O*O--*--X # This destroyed a brittle block.
X-****-----X
X-*O*****--X # This got hard blocked.
X-*--*--O--X
*******---** # Notice how it wraps, because there's no boundary.
X-*--*----OX
X-*O****---X # This got hard-blocked.
XXXXXXXXXXXX

Example 1:

Input:

XX
XX

Output:

XX
XX

Example 2:

Input:

X-O--X
-o2-o-
-1--1-
-o-2o-
X--O-X

Output:

X-O--X
-****-
******
-****-
X--O-X

Example 3:

Input:

X     X
 OOOO
  1114


X     X

Output:

X    *X
 OOOO*
*******
  ****
     *
X    *X

Rules

More examples, soon. Is this good? Sandbox? What should I change?

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

Is Effort Inversely Correlated with Upvotes?

Inspired by this chat message and the subsequent conversation

Introduction

PPCG is infamous (famous?) for it's short golfing language answers that are showered with upvotes. But, are these short answers full of hard-core golfing, or are they just a few builtins that work? Do these answers take effort, and deserve upvotes, or are upvotes and effort inversely correlated?

The Challenge

To get some variables out of the way, x=effort, and y=votes

Your challenge is, given a question ID, output A if the question has a strong positive correlation between effort and votes, B if it has a weak correlation between efforts and votes, or C if it has a strong negative correlation between effort and votes. A may be any value never given as B or C, B may be any value never given as A or C, and C may be any value never given as A or B (You doubt have to have consistent values across runs, but the set of values for A must not intersect with B or C, etc.).

Defining Effort

Effort is an awfully complex concept, but for this challenge we will grossly simplify it to the number of significant edits. significant edits, in this context, will be the number of edits, by the question author, that occurred more than 1 minute after the previous edit (initial posting, in this case, counts as an edit).

Defining Votes

Votes is upVotes - downVotes.

Defining Correlation

For the sake of simplicity, will we use the least-squares regression line as our correlation model. If R^2 (the determination coefficient) is less than .3 (e.g. < 30% of the variation is explained by the model), we will say that there is weak correlation. If R^2 is greater than or equal to .3, we will say that the correlation is strong. Negative vs. positive correlation must be determined from the sign of R (the correlation coefficient).

What Points?

The data points that should be included in your regression are points of the form (votes, effort) for each answer in the given question.

Test Cases

//TODO

Specifics

  • For the purposes of this challenge, you may access the api.stackexchange.com website. You may not shorten the URL with any out-of-language utilities (e.g. tinyurl, but you can still compress it if your language supports compression)
  • You may not violate any standard loopholes
  • You may take input and give output in any reasonable format
  • You should exclude community wikis from your calculations

Meta

\$\endgroup\$
  • \$\begingroup\$ Effort: significantEdits \$\endgroup\$ – programmer5000 Aug 22 '17 at 20:22
  • \$\begingroup\$ @programmer5000 okay \$\endgroup\$ – Socratic Phoenix Aug 22 '17 at 20:32
  • \$\begingroup\$ You spent effort on this, have an upvote! \$\endgroup\$ – programmer5000 Aug 22 '17 at 21:20
  • \$\begingroup\$ "number of edits greater than 5 characters" counted how? Levenshtein distance with substitution counted as 1? (This is a terrible proxy for effort: apart from anything else, adding strikeout to record a one-byte improvement would take you past the threshold, even if the improvement was suggested in comments and required no effort on the OP's part). \$\endgroup\$ – Peter Taylor Aug 23 '17 at 21:23
  • \$\begingroup\$ @PeterTaylor that's intentional (the strikeout), but I agree that's it's a bad proxy for effort.. I'll try and create a better one... \$\endgroup\$ – Socratic Phoenix Aug 23 '17 at 21:39
  • \$\begingroup\$ @PeterTaylor updated definition of effort, is it better or worse? \$\endgroup\$ – Socratic Phoenix Aug 24 '17 at 18:03
1
\$\begingroup\$

Word Problem Generator

Already exists here!

Word problems can be a great way to test comprehension of concepts, but they are pain to write. That's why you need to make a program that takes an equation (or set of equations), and makes a word problem out of them. For example, if the input is x+3=8, you can output, Mary has 3 more apples than Johnny. If Mary has 8 apples, how many does Johnny have?

The best answers for this challenge will be able to handle many different types of equations and randomly generate a variety of unique word problems. It might be o.k. if your program creates non-sensical word problems, as long as they describe the input equation/equation set and people like them.

Rules

  • Submission must be no longer than 2000 bytes
  • External files and URL's may be used to access word lists not specifically made for this challenge. You can also use libraries for parsing mathematical equations and sentence generation that were not specifically made for this challenge (WolframAlpha is acceptable). Inquire about other acceptable usage of external sources.
  • Golfing is encouraged. Most popularity contests ask for readable code, but with a tight 2000 byte limit, I encourage golfing as much as possible (even using a golfing language), so that you'll have enough bytes remaining to create interesting word problems.

Examples

  • atan(x) = 5/4 => "At what angle should Jan hit the soccer ball to hit a target 5 feet high and 4 feet away?"
  • x+5 = y, 2(x-1) = y-1 => "Paul is 5 years older than Sally. Last year Paul was twice Sally's age. How old are Paul and Sally?"
  • x = 6^2/4^2 => "How much more pizza is there in a 12 inch pizza than an 8 inch pizza?"

Submission

With your submission, you include the types of equations/equation sets it can handle (we'll assume that a,b,c,d,e,f,g refer to constants and t,u,v,w,x,y,z refer to variables).

As an example, let's say your program can only make 1 type of word problem: "How long will it take for a boat with speed a to catch up to a boat with speed b that is distance c ahead of the first boat?" In that case, you write that your program only handles equations of the form at = bt + c, so people will know to only test it with things like 5t = 3t + 2 or 4t = 2t + 1.

Furthermore, you should mention if your program can make multiple types of word problems for one type of equation/equation set. For example, an equation of the form a + bx = c could lead to word problems about the time it takes to get from one point to another, or the amount of a particular coin you need to reach a certain amount of money.

Likewise, mention other ways your program creates variety in generating word problems.

Finally, you can include some sample word problems your program has generated, and the equations they were for.

Minimum Requirements

The most basic acceptable solution should handle at least 1 equation/equation set with at least 1 variable, 1 constant, and 1 mathematical operation. Such a minimal program might only handle equations of the form x = a + 1. It might output word problems like, "If Jerry has a apples, and he picks 1 more, how many does he have now?" Obviously, you should not strive for the bare minimum.


All suggestions welcome!

\$\endgroup\$
  • 1
    \$\begingroup\$ In case you haven't seen it yet: Tag Wiki for popularity contest. As noted there, you should include an objective validity criterion. You already have some useful rules, but it's still not clear me what the minimum requirement for an answer is. E.g. would handling only equations x=1+2 suffice? What about only x=3. \$\endgroup\$ – Laikoni Jul 21 '17 at 8:51
  • \$\begingroup\$ @Laikoni ty, updated. \$\endgroup\$ – geokavel Jul 21 '17 at 15:35
  • \$\begingroup\$ Personally, I dislike the scoring. Having a hard byte count limit discourages more verbose languages, but at the same time, byte count is not a factor in scoring. Also, I'm not sure popularity-contest is the right choice here. I would either 1) Make it a code-golf and impose strict requirements on what the program should be able to do, or 2) Make it a test-battery, where the score is the percentage of inputs that result in coherent output \$\endgroup\$ – musicman523 Jul 21 '17 at 20:59
  • \$\begingroup\$ @musicman523 I've thought about other formats than pop-con, but I think they all significantly reduce creativity. I don't have a perfect answer for byte count limit, but I think it is needed, otherwise people can spend forever hardcoding all sorts of words problems, which is not really what I'm looking for. Also, one tradeoff is the languages that are usually more verbose are the more established ones that also have more library access. \$\endgroup\$ – geokavel Jul 21 '17 at 21:55
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\$
  • \$\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\$ – Jonathan Allan 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\$
  • \$\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\$ – Peter Taylor 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\$
1
\$\begingroup\$

Where in the world am I?

Original Challenge

This challenge has a single aim, given no input, print out the user's current location, with a minimum of the following info:

  • City
  • Country

So any of the following are allowed:

  • "London, England"
  • "Eifel Tower, Paris, France"
  • ["London", "England"]
  • {"country": "Scotland", "city": "Edinburgh"}

The following are not allowed:

  • [51.5074, 0.1278]
  • {"country": "Scotland", "city": "Edinburgh", ISP: "EE"}

Do not show the user's IP or ISP name, or any extra output.

Standard code golf rules apply

Good luck, and have fun!

Reason for limits

Thanks

programmer5000 - Suggesting to post here after original was deleted

caird coinheringaahing - Lon and Lat rules

\$\endgroup\$
  • \$\begingroup\$ Is returning a list of geo-cordinates allowed? You might want to clarify that in the question \$\endgroup\$ – caird coinheringaahing Aug 28 '17 at 14:12
  • 3
    \$\begingroup\$ This has a number of issues with ill-defined cases. In particular, the following are not addressed: (A) my location is unambiguously in a given country, but there's no city within several hours' drive; (B) my location is unambiguously not inside any country; (C) the territorial ownership of my location is disputed; (D) it's not clear what the name of the country is (where your example of Edinburgh is a good one: if Scotland is correct, is UK incorrect? How about dependencies, colonies, etc?) \$\endgroup\$ – Peter Taylor Aug 28 '17 at 21:26
  • 2
    \$\begingroup\$ In addition, it contradicts itself over whether {"country": "Scotland", "city": "Edinburgh"} is allowed or not; and it is not very testable. To make this a good challenge I would recommend taking latitude and longitude as inputs and providing a complete and unambiguous specification of exactly what the output string should be such that any incorrect answer can be shown to be incorrect with a test case which it fails. \$\endgroup\$ – Peter Taylor Aug 28 '17 at 21:28
  • \$\begingroup\$ TBH, if someone was onboard the International Space Station and decided to take time out to complete my code golf challenge I would take it as a compliment. For international waters I would be OK with an answer that pointed towards that. For ones with multiple answers / disputed it would probably be reasonable to accept multiple answers, but there may be issues with this I have not foreseen. \$\endgroup\$ – jrtapsell Aug 28 '17 at 21:35
  • \$\begingroup\$ RE: The contradiction, this was an omission I hope I have fixed now \$\endgroup\$ – jrtapsell Aug 28 '17 at 21:37
  • \$\begingroup\$ Is there a way to fix this issue more generally? I know my answer is a bit vague and not built into the question \$\endgroup\$ – jrtapsell Sep 1 '17 at 10:31
  • \$\begingroup\$ Is this challenge good to go, needs changes, or not of use? \$\endgroup\$ – jrtapsell Sep 2 '17 at 23:20
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\$
  • 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\$ – J42161217 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\$ – Anthony Pham 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\$
  • \$\begingroup\$ Are these polynomials on Z? You say complex number pairs which suggests it is some numeric set. \$\endgroup\$ – Sriotchilism O'Zaic 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\$
  • 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\$ – Peter Taylor 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\$ – Peter Taylor Sep 11 '17 at 8:44
  • 1
    \$\begingroup\$ @PeterTaylor fixed up again \$\endgroup\$ – boboquack Sep 11 '17 at 9:07
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\$
  • \$\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\$ – John Dvorak 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\$ – John Dvorak 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\$ – John Dvorak 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\$ – Peter Taylor 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\$ – Peter Taylor 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\$
  • \$\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\$ – Peter Taylor 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\$ – Jonathan Frech 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\$ – Jonathan Frech 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\$ – Jonathan Frech 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\$
  • \$\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\$ – Jonathan Allan 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\$ – Esolanging Fruit 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\$
  • \$\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\$ – Sriotchilism O'Zaic Oct 5 '17 at 20:02
  • \$\begingroup\$ @flawr Is that a better explanation? \$\endgroup\$ – Sriotchilism O'Zaic 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\$ – Sriotchilism O'Zaic 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\$ – Peter Taylor 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\$ – Sriotchilism O'Zaic 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\$
  • \$\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\$ – Conor O'Brien 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\$
  • \$\begingroup\$ This is going to be too hardcore. \$\endgroup\$ – someone 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\$ – Esolanging Fruit Oct 25 '17 at 15:53

You must log in to answer this question.

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