555
\$\begingroup\$

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

Sandbox FAQ

Posting

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

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

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

Discussion

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

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

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

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3920 Answers 3920

1
13 14
15
16 17
131
3
\$\begingroup\$

Dot matrix number visualization

Your task is to make a program that takes a number as input and outputs it as a wall of characters with spaces. The digits should be written like this:

  1    222   333     4  55555  666  77777  888   999   000 
 11   2   2 3   3   44  5     6   6     7 8   8 9   9 0   0
1 1       2     3  4 4  5555  6        7  8   8 9   9 0  00
  1      2    33  4  4      5 6666    7    888   9999 0 0 0
  1     2       3 44444     5 6   6  7    8   8     9 00  0
  1    2    3   3    4  5   5 6   6  7    8   8 9   9 0   0
11111 22222  333     4   555   666   7     888   999   000  

Each digit is represented as a grid of 5x7 characters consisting of spaces and the digit itself. The number should be written like above with a vertical line of spaces separating the different digits.

The preformatted text above should be the output of a 1234567890 number input. If you guys like this challenge, I'll post an image that better visualizes how each number should be printed.

Lowest size program wins.

Edit: Added a picture to better illustrate the digits. Dotmatrix digit grid

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's pretty clear what you're giving as the task, but an image would help, as the pre-formatted text is rather hard to read \$\endgroup\$ Jan 17, 2017 at 11:59
  • \$\begingroup\$ @TrojanByAccident: It is pretty obvious what result the author wanted even without the image. \$\endgroup\$
    – sergiol
    Jan 24, 2017 at 17:34
3
\$\begingroup\$

Powerful numbers

Look at the number 81 expressed as the sum of distinct powers of the same base:

  • 81 = 81 (well, duh)
  • 81 = 80 + 1 (easy)
  • 81 = 9*9
  • 81 = 4*4*4 + 4*4 + 1
  • 81 = 3*3*3*3
  • 81 = 2*2*2*2*2*2 + 2*2*2*2 + 1 (if you thought that was obvious...)
  • 81 = 1 + 1 + ... + 1 (yeah, yeah...)

As you can see, for N > 4, there are always 4 trivial bases: 1, 2, N-1 and N. Powerful numbers are those numbers which have at least one nontrivial base. Please write a program or function that, given a number N > 4, outputs a truthy or falsy value for whether a nontrivial base exists. The results for N up to 30 should be as follows:

(1  F)  16  T
(2  F)  17  T
(3  F)  18  F
(4  F)  19  F
 5  F   20  T
 6  F   21  T
 7  F   22  F
 8  F   23  F
 9  T   24  F
10  T   25  T
11  F   26  T
12  T   27  T
13  T   28  T
14  F   29  F
15  F   30  T

This is , so the shortest solution wins!

\$\endgroup\$
17
  • 2
    \$\begingroup\$ "Your challenge is, given a number N, to return the Nth Powerful number." I doubt that there's any way to generate the Nth number other than counting up from 1 and stopping once you've encountered N of them. So why not reduce it to "given a number, determine whether it's powerful"? \$\endgroup\$ Jan 19, 2017 at 12:13
  • 2
    \$\begingroup\$ Simplified definition: "a powerful number is a number which can be written using only the digits 0 and 1 in any base other than 1, 2, n, or n-1." \$\endgroup\$
    – user62131
    Jan 19, 2017 at 15:37
  • 1
    \$\begingroup\$ I believe a (very golfed) reference implementation in ES6 to determine whether a number is powerful would be a=>(g=b=>b>1&&(f=c=>c&&c%b|f(c/b|0),f(a)<2)+g(b-1))(a)>3. This gives these first 1000 powerful numbers. The sequence doesn't seem to be on OEIS though. \$\endgroup\$ Jan 19, 2017 at 17:36
  • \$\begingroup\$ @MartinEnder I was under the impression that it was more common to ask for the Nth or first N terms rather than just verifying a particular term. Perhaps if I ask for all Powerful numbers up to N? \$\endgroup\$
    – Neil
    Jan 19, 2017 at 21:01
  • 2
    \$\begingroup\$ @Neil I think that's even worse. That way you make 100% sure that there's no way to avoid wrapping the entire program in a boring loop. \$\endgroup\$ Jan 19, 2017 at 21:10
  • \$\begingroup\$ I like challenges like this better as a decision-problem, since that's what it comes down to. Outputting the Nth such number or the first N just adds extra code around the real meat of the challenge. \$\endgroup\$ Jan 19, 2017 at 22:03
  • \$\begingroup\$ Example for first N terms: codegolf.stackexchange.com/questions/107420/… \$\endgroup\$
    – Neil
    Jan 20, 2017 at 9:45
  • \$\begingroup\$ @MartinEnder OK, how about if, given an integer N greater than 1, the result should be the number of representations? \$\endgroup\$
    – Neil
    Jan 20, 2017 at 19:18
  • \$\begingroup\$ @Neil That's fine, but I'm curious why you're so strongly opposed to making it a simple decision problem. :) \$\endgroup\$ Jan 21, 2017 at 14:38
  • \$\begingroup\$ @MartinEnder You want people to add extra code to compare the result to 4 around the real meat of the challenge? (Sorry I couldn't resist!) \$\endgroup\$
    – Neil
    Jan 21, 2017 at 15:48
  • \$\begingroup\$ Quoting me now, are you? :P But you don't actually have to count all of them since 4 are already given: 1, 2, n-1, and n. So all you really have to do in a decision-problem is check if there are any between 3 and n-2, inclusive. \$\endgroup\$ Jan 21, 2017 at 22:40
  • \$\begingroup\$ That said, I'm not sure which path would be shorter in most langs. My attempts in JS for both versions of the problem turned out the same length. \$\endgroup\$ Jan 21, 2017 at 23:37
  • \$\begingroup\$ @ETHproductions OK I'm convinced now. \$\endgroup\$
    – Neil
    Jan 22, 2017 at 1:08
  • \$\begingroup\$ Related OEIS sequence \$\endgroup\$ Jan 22, 2017 at 22:23
  • \$\begingroup\$ I actually don't know whether decision-problem would be better than just counting how many bases it's powerful in. There are arguments for and against each. My solutions turned out the same length in JS, but in Jelly the decision-problem solution came out as just 2 extra bytes added to an 8-byte counting solution. I guess it just comes down to what you want to see in the challenge. \$\endgroup\$ Jan 23, 2017 at 16:48
3
\$\begingroup\$

Does Mathematica Have a Builtin?

Mathematica has a lot of builtins.

Your task is to take in a question names and its tags; and to guess whether or not Mathematica has a builtin that solves that question.

Rules

  • Your code must be less than 100 bytes long.

  • You may use internet to access the Mathematica reference guide you may also use the internet to access the tag wikis. Standard loopholes apply to internet access.

  • For this challenge we will consider a valid builtin to be a builtin that does most of the computation for the challenge. Extra bytes spent on trivialities like IO formatting will be ignored.

  • You must output a truthy value if Mathematica has a builtin to solve that challenge and a falsy value otherwise.

  • If Mathematica has a builtin and for some reason the challenge does not allow Mathematica to compete or bans builtins your program must still output truthy.

Scoring

This is a so you will be scored on the percentage questions here (This is currently a work in progress there will be more cases in the final question) that your program gets the correct answer on.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ As always with builtins, you'll want to outline exactly what counts as "built-in". For example, if a challenge is about printing hexagonal numbers, does using PolygonalNumber with fixing r = 6 count? (not sure if that's an accurate example, but you get the point). The test battery would make things 100% indisputable, but it's something you might want to think about when making the test battery. \$\endgroup\$
    – Sp3000
    Jan 26, 2017 at 1:55
  • \$\begingroup\$ On a side note, is a hardcoded approach okay, e.g. regex golfing the pass vs fail set? \$\endgroup\$
    – Sp3000
    Jan 26, 2017 at 1:55
  • \$\begingroup\$ @ETHproductions I meant the later, a function that does most of the work. I am not sure if I am going to write a super strict definition of builtin but I will be writing at least a loose one. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 1:57
  • \$\begingroup\$ @Sp3000 Hardcoded is fine. I would like to see all sorts of approaches to this problem including regex. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 1:58
  • \$\begingroup\$ My question codegolf.stackexchange.com/questions/107181/… was solved in Mathematica with a built-in that I wasn't expecting. That might be useful for your tests \$\endgroup\$
    – Gareth
    Jan 26, 2017 at 9:22
  • \$\begingroup\$ Can you read the Mathematica answer off the page if it exists, or is the idea to only read the question? \$\endgroup\$
    – xnor
    Jan 26, 2017 at 9:40
  • \$\begingroup\$ @Gareth Thanks I am in need of more test cases. \$\endgroup\$
    – Wheat Wizard Mod
    Jan 26, 2017 at 12:52
  • \$\begingroup\$ Answer: Hardcode truthy because Mathematica ALWAYS has a builtin :P \$\endgroup\$
    – user42649
    Apr 10, 2017 at 13:05
3
\$\begingroup\$

Minimal QWERTY

The task -- to output the layout of a QWERTY keyboard:

QWERTYUIOP
ASDFGHJKL
ZXCVBNM

But, you will be scored based on the length of your code, and on the number of distinct characters in it.

Rules

1) The code must output the three lines of text above (or the text above with optional trailing newline)

2) Standard loophole restrictions apply

3) If the language contains predefined information about the QWERTY layout, you are not allowed to use that information.

Scoring

The score will be defined as [Length of the program in bytes]*[# of distinct characters in the program], with lowest score winning.

For example, the code

ABAB1212

would have score 8*4=32 since it has length 8, but only 4 distinct characters: AB12

And the code:

ABC!!!{{{

Would have score 9*5=45, since it has length 9, and 5 distinct characters: ABC!{

\$\endgroup\$
11
  • 3
    \$\begingroup\$ I really like this scoring system; it strikes a great balance between cutting down chars and cutting down the number of distinct chars you're using. I was going to say that this might not be the best way to use this scoring system, but anything other than "output this exact string" would likely be solvable in 10 bytes in golfing languages, or not solvable in 100 in non-golfing langs. (Perhaps a string with more repetition would work better though, but we won't know until the challenge is posted.) \$\endgroup\$ May 6, 2017 at 20:31
  • 1
    \$\begingroup\$ About "If the language contains predefined information about the QWERTY layout, you are not allowed to use it.": does this mean you're not allowed to use the language, or just the QWERTY built-in? \$\endgroup\$ May 6, 2017 at 20:33
  • 1
    \$\begingroup\$ @ETHproductions Thanks for the input! The reason I thought thought the QWERTY task would work well with this scoring system is that the output consists almost entirely of a large number of distinct characters (meaning any substantial use of string literals for the output would be very bad for the score), and those characters are fairly disordered, meaning a simple loop won't solve it. Do you have thoughts on other possible tasks for this scoring system? \$\endgroup\$
    – Maria
    May 7, 2017 at 1:54
  • \$\begingroup\$ Regarding your second question -- the language would be allowed; they just wouldn't be allowed to use the predefined information. I've changed the wording to make that clear (I see that it was ambiguous before - thanks for catching that) \$\endgroup\$
    – Maria
    May 7, 2017 at 1:58
  • \$\begingroup\$ May be too close to this challenge. It's not quite the same, but the basic task is similar (golf down a large set of distinct characters into a set of mostly repeated characters). This challenge is even closer, requesting printing a constant string with many distinct characters, and using the same scoring method; that's almost certainly a duplicate at this point. \$\endgroup\$
    – user62131
    May 7, 2017 at 2:23
  • \$\begingroup\$ @ComradeSparklePony I think this is covered by the condition to exclude this? \$\endgroup\$ May 7, 2017 at 21:02
  • \$\begingroup\$ @PaŭloEbermann Oops, I missed that. \$\endgroup\$
    – sporklpony
    May 7, 2017 at 21:05
  • \$\begingroup\$ +1, when are you going to post this? \$\endgroup\$
    – MD XF
    May 10, 2017 at 1:22
  • \$\begingroup\$ I kinda agree with @ETHproductions first comment regarding a string with more repetition and non-golfing languages. For example, to solve this in fewest bytes in Java 7 (I know, Java 7 is verbose as F.. xD), it will be: String r(){return"QWERTYUIOP\nASDFGHJKL\nZXCVBNM";} (score of 51 bytes * 41 unique characters = 2091). With fewest characters possible you'll abuse unicodes and it becomes pastebin.com/unrn6xj2 (too long for comment..), with a score of 343 bytes * 18 unique characters = 6174.. But of course, you're free to post it nonetheless as is. Java won't ever compete anyway ;) \$\endgroup\$ May 10, 2017 at 9:07
  • \$\begingroup\$ But I like the scoring mechanism, and it's also a fairly easy challenge for most golfing languages, where the size vs unique characters really matters, which is of course the focus of code-golfing languages. So perhaps just post it, and I'll just score 2091 with my Java 7 answer. ;) \$\endgroup\$ May 10, 2017 at 9:10
  • \$\begingroup\$ Japt, 4 points ;D :D \$\endgroup\$ May 19, 2017 at 20:13
3
\$\begingroup\$

Exiting Vim — Cops & Robbers

In honour of the recent milestone, let's turn escaping Vim into a game!

Rules for Cops

Starting from launching vim with no arguments (i.e. no initial file open), provide a sequence of keys to be typed in to the editor.

Rules for Robbers

Starting from the state described by the cop, provide a sequence of keys to exit Vim.

Scoring

Cops are scored by the difference between key counts <robber_key_count> - <cop_key_count>, and robbers are scored by the ratio of key counts <cop_key_count> / <robber_key_count>. Higher scores are better.

Keys are counted as one per key-down event (e.g. a sequence of Ctrl+X, Ctrl+Y, Ctrl+Z only need count the Ctrl once, unless it must be released during the sequence). Note that this is not the same as the golf-rules scoring for Vim.

Plugins are not permitted.

Example 1

Cop (1 key): i

Robber (4 keys): Esc : q Enter

Score for cop = 4 - 1 = 3, score for robber = 1 / 4 = 0.25

Example 2

Cop (2 keys): i i

Robber (5 keys): Esc : q ! Enter

Score for cop = 5 - 2 = 3, score for robber = 2 / 5 = 0.4

Example 3

Cop (3 keys): i Ctrl+V

Robber (6 keys): Return Esc : q ! Enter

Score for cop = 6 - 3 = 3, score for robber = 3 / 6 = 0.5

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm not sure that the scoring here rewards cops enough for ingenuity (all the examples score 3 after all!), so ideas on that would be great. Also I'm considering banning Esc & Ctrl+[ to make this more interesting, but I suspect even with Esc permitted there are ways to get seriously tied-up. \$\endgroup\$
    – Dave
    May 23, 2017 at 20:13
  • \$\begingroup\$ I'm worried that there may not be much scope for the cops to improve; it'd be something of a design flaw in the challenge if there's a hard limit to how well a cop can do. Also, what about key sequences that depend on the environment within which vim is running? (For example, Ctrl-Z will suspend vim and require the use of the shell to either exit or restart it, but how you do that depends on which shell is running; or on Linux, Ctrl-Alt-F1 will probably switch to a different virtual terminal altogether, and what assumptions can you make about its state?) \$\endgroup\$
    – user62131
    May 31, 2017 at 21:35
  • \$\begingroup\$ Another potential problem: exit sequences which have side effects. In particular, I'm thinking about Alt-SysRq-K, which is guaranteed to exit vim, in addition to everything else, on Linux systems which have it enabled. That compares favourably to basically all the exit strings you have right now, and there's no way, short of reconfiguring the OS, to block it. \$\endgroup\$
    – user62131
    May 31, 2017 at 21:36
  • \$\begingroup\$ @ais523 I'm thinking it could easily be restricted to "vim-only" commands, so anything which is intercepted by the shell can be forbidden. But I agree that it feels like there's a hard-limit on the cop (though I don't know vim nearly well enough to be sure, and I've seen some hints around the internet that it's possible to get exceedingly stuck, but perhaps only because some modes need obscure non-esc keys, rather than needing more keys). Any ideas for better scoring? \$\endgroup\$
    – Dave
    Jun 5, 2017 at 20:36
3
\$\begingroup\$

Mark Duplicates

Given a list of non-negative integers, find the values which are duplicates and mark their positions.

For example, given [1, 2, 3, 2, 1], the output could be [1, 1, 0, 1, 1] where each 1 signifies that the value at that position is duplicated elsewhere in the array and each 0 signifies that the value at that position is unique.

Your output may use either 0 and 1, boolean values for false and true, or any other two distinct values as long as you remain consistent.

This is so minimize the length of your code.

Test Cases

[] -> []
[5] -> [0]
[0, 1] -> [0, 0]
[2, 2] -> [1, 1]
[1, 2, 3, 2, 1] -> [1, 1, 0, 1, 1]
[6, 3, 6, 3, 5, 2, 3] -> [1, 1, 1, 1, 0, 0, 1]
\$\endgroup\$
12
  • 2
    \$\begingroup\$ Ironically, I feel this is a duplicate of (or at least closely related to) and existing challenge but I can't find it at the moment. \$\endgroup\$
    – Shaggy
    May 24, 2017 at 10:43
  • \$\begingroup\$ Would we have to use 0 & 1 or could we use any 2 distinct & consistent values? \$\endgroup\$
    – Shaggy
    May 24, 2017 at 11:06
  • \$\begingroup\$ I.e Nub Sieve? \$\endgroup\$
    – Adám
    May 24, 2017 at 11:27
  • \$\begingroup\$ @Adám I previously made a challenge for nub sieve. This is slightly different since we aren't choosing positions to filter for only the unique values. \$\endgroup\$
    – miles
    May 24, 2017 at 18:43
  • 1
    \$\begingroup\$ @Shaggy Yes, any choice of output values is fine as long as its two distinct values that you use consistently. \$\endgroup\$
    – miles
    May 24, 2017 at 18:45
  • \$\begingroup\$ Isn't this just NOT nub sieve? \$\endgroup\$
    – Adám
    May 24, 2017 at 18:47
  • \$\begingroup\$ @Adám For the [1, 2, 3, 2, 1], nub sieve could be [1, 1, 1, 0, 0], [0, 1, 1, 0, 1], [0, 0, 1, 1, 1], [1, 0, 1, 1, 0], and the not of each is [0, 0, 0, 1, 1], [1, 0, 0, 1, 0], [1, 1, 0 ,0, 0], [0, 1, 0, 0, 1]. \$\endgroup\$
    – miles
    May 24, 2017 at 19:21
  • \$\begingroup\$ I think this would be interesting if the first time an entry appears it's not counted as a duplicate. \$\endgroup\$
    – xnor
    May 24, 2017 at 19:37
  • \$\begingroup\$ @xnor Wouldn't that be not( nub-sieve( x ) )? \$\endgroup\$
    – miles
    May 24, 2017 at 20:23
  • \$\begingroup\$ How does nub-sieve work? My suggestion is because it means the position of the item matters rather than just its value, so it's not just mapping each entry x to l.count(x)>1. \$\endgroup\$
    – xnor
    May 24, 2017 at 20:26
  • \$\begingroup\$ The first occurrence of a value is marked true and all subsequent occurrences of the same value are marked false. Nub-sieve. My previous challenge for distinct sieves is a relaxed variant to nub-sieve. For [1, 2, 3, 2, 1], a proper nub-sieve would be [1, 1, 1, 0, 0], and not of that would be [0, 0, 0, 1, 1]. I do agree with that last sentence about how most solutions in golfing languages would probably just count occurrences. \$\endgroup\$
    – miles
    May 24, 2017 at 20:44
  • \$\begingroup\$ @miles can I adopt and post this abandoned proposal? \$\endgroup\$
    – user58826
    Jun 9, 2017 at 1:34
3
\$\begingroup\$

This message is open for anyone to adopt and post to main. For more details, see the chat room or meta post.

Nonogram it

Nonograms are one of my favorite types of puzzles, but sometimes there are not enough of them to solve!

The challenge here is to write a program that would take an image and output the values for the columns and rows of the puzzle.

INPUT: black and white PNG on STDIN

OUTPUT: two lines with the values to create the puzzle. First line is the columns, second the rows. The format of both lines is: [a,b,c...],[d,...],... (lists of integers separated with commas delimited with [], with each list separated by commas, ending in a newline. No dangling commas allowed inside the lists or at line end)

The squares on the image should be of 5x5px. The thereshold for determining if a square is filled is if it has at least 30% black inside it.

(3 sample images will be added later)


I'm not sure about the scoring for this challenge, most likely it should be a .

Additional scoring criteria I can think of:

  • allowing to enter square size or cols*rows of the puzzle.
  • accepting non black and white images
  • reading other image types
  • providing a solver
\$\endgroup\$
12
  • 1
    \$\begingroup\$ wait, is the PNG itself in the STDIN, or a file path to it? I assume the latter, but it's currently formulated as if it's the former. Also, the threshold needs to be clarified. Also, why is the image scaled up in the first place? \$\endgroup\$ Mar 26, 2014 at 19:59
  • 2
    \$\begingroup\$ Also, I'd prefer an ascii-art input (a grid of hashes and spaces) than having the challenge complicated by looking up and interfacing an image manipulation API. \$\endgroup\$ Mar 26, 2014 at 20:02
  • \$\begingroup\$ It could be a file path if that's more accesible. I didn't say the image was scaled, the 5*5 squares are for the grid to create the nonogram, just to avoid another required parameter(number of cols*rows desired). About the ascii-art, that would have no challenge, just a count() \$\endgroup\$
    – Einacio
    Mar 27, 2014 at 15:42
  • 1
    \$\begingroup\$ I don't think a PNG library showoff is a good challenge for this site. There's no thinking present, just having to learn an API and hope it has short enough names. \$\endgroup\$ Mar 27, 2014 at 15:45
  • 1
    \$\begingroup\$ I don't understand the 5x5 rule. Is it that there are 5x5 pixels in the image, and 5x5 pixels in the grid? 5x5s are no puzzles. \$\endgroup\$ Mar 27, 2014 at 15:46
  • \$\begingroup\$ It wouldn't be the first challenge using PNG, so I see no problem there. About the grid, I'll prepare the example images later, I hope that'll be clearer to understand \$\endgroup\$
    – Einacio
    Mar 27, 2014 at 16:02
  • 1
    \$\begingroup\$ Seeing that you prescribe exactly how black and white cells are to be determined, unique solubility of the resulting nonogram is no criterion? \$\endgroup\$ Mar 31, 2014 at 11:28
  • \$\begingroup\$ @m.buettner I proposed the fixed grid and cell criterion with the idea of being able to check results against others. I forgot about ambiguous solutions, and I don't know how difficult is to test for it, specially if it ends as a code-golf. Maybe I should rule it out explicitly to keep answers simpler? \$\endgroup\$
    – Einacio
    Mar 31, 2014 at 14:18
  • 1
    \$\begingroup\$ @Einacio well, uniqueness could be checked with a solver (there might be easier ways). I suppose you just have to decide whether you want soluble or comparable answers. If you are going for soluble, you can make this a "code challenge" and determine the score based on both code length and similarity to input image. \$\endgroup\$ Mar 31, 2014 at 14:58
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 16:29
  • \$\begingroup\$ @programmer5000 Hi, I totally forgot about this challenge, I haven't had much free time in those 3 years to give it some love. I would be delighted to see someone pull it through, do I have to do something more than post it in the chat? \$\endgroup\$
    – Einacio
    Jun 9, 2017 at 19:40
  • \$\begingroup\$ @Einacio just post a link to this answer and nothing else in that chat room. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 19:55
3
\$\begingroup\$

Irreducible Polynomials over a Finite Field

Given a polynomial whose coefficients are in a finite field, deduce whether or not it is irreducible, without using any related built-ins (you can use a built-in that represents polynomials, but you cannot use built-ins for factoring or otherwise finding information about the polynomial).

A polynomial in F[x] (where F is a field) is considered irreducible if it cannot be factored into the product of non-constant polynomials.

I/O:

Your program/function will take two inputs:

  • a prime number for the order of the Finite Field
  • some representation for the polynomial

Output a truthy value if the polynomial is irreducible, and a falsy value otherwise.

Test Cases

Your program must run in a reasonable time for this (i.e. 1 hour is definitely too long):

>>> F = 2, f(x) = x^3 + x^2 + x + 1
false
>>> F = 5, f(x) = x^4 + 4x^3 + 4x^2 + x
false
>>> F = 2, f(x) = x^4 + x + 1
true
>>> F = 5, f(x) = x^3 + x + 1
true
>>> F = 5, f(x) = x^6 + 2x^4 + 2x^3 + x^2 + 2x + 1
false
>>> F = 2, f(x) = x^6 + x^2 + 1
false
>>> F = 5, f(x) = 4x^4
false

Meta Note:

These are all really related:

The first especially. This challenge is very similar to the first, except that the first is for irreducible polynomials over Z (the integers), whereas this is for irreducible polynomials over finite fields. Although the challenges are similar, I feel this is different enough to warrant a new challenge

\$\endgroup\$
5
  • \$\begingroup\$ Is the polynomial guaranteed to be monic? Is the zero polynomial irreducible? Also, are you OK with brute-force solutions that take huge amounts of time? \$\endgroup\$
    – xnor
    Oct 18, 2014 at 5:20
  • \$\begingroup\$ @xnor No, the polynomial is not guaranteed to be monic, yes brute-force is okay if it runs in reasonable time for the test cases - I wrote a program that took <20 min for all but the 2nd last test case, which would take 2 days. Regarding zero polynomial, I need to do a bit of research first. \$\endgroup\$
    – Justin
    Oct 27, 2014 at 5:56
  • 1
    \$\begingroup\$ Now that I almost have an answer to the polynomial factoring question I can say that the test cases can be handled by brute force in a slow language in a few seconds. It's the case over Z that allows tough performance requirements with simple test cases. \$\endgroup\$ Oct 28, 2014 at 7:54
  • \$\begingroup\$ @programmer5000 No, I would still like to use this. I had forgotten about it, and I will improve it and post it to main. Thank you for reminding me about this post \$\endgroup\$
    – Justin
    Jun 11, 2017 at 6:59
  • \$\begingroup\$ I feel like many people will not know what a finite field is. I think you should explain it in the post to allow people to answer without google. \$\endgroup\$ Jun 11, 2017 at 19:19
3
\$\begingroup\$

ASKEY robbers

You are a robber in the ASCII world. ASCII lock-key work in similar fashion as the real-world: matching ridges. Your objective is to write a program which generates a duplicate key for the ASCII locks.

Example:

A Lock is given as:

   |\    |\         
 __| \___| \____             
|               | 
|_______________| 

Its key shall be something like:

 _______________
|   __     __   |
|  |  \   |  \  |  
|__|   \__|   \_|

The fit being something like:

 _______________
|   __     __   |
|  ||\\   ||\\  |
|__|| \\__|| \\_|
|               |
|_______________| 

SandBox

I think the fit is weird. It didn't go as I had imagined when I finished typing in the ASCII drawing.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ This has potential, but it needs a clear specification as to what a fit is, and what constitutes a lock (i.e. some constraint on the input). \$\endgroup\$ Jun 14, 2017 at 17:47
  • \$\begingroup\$ Yes. This is very incomplete/unclear as of yet. \$\endgroup\$ Jun 15, 2017 at 3:27
3
\$\begingroup\$

When did I need to be born to celebrate a magic birthday?

I was born in 1984 and in 2016 I became 32 years old, which is 20 in base 16, what a coincidence!

Your task is, given the year of interest -say 2016- , to calculate the year I had to be born to be able to say In 2016 I have celebrated/I will celebrate my 20th birthday (in base 16).

  1. take n-digit decimal number - the year xy.
  2. Split it in half, if n is odd, the digit the middle is appended to number side.
  3. Calculate the year I had to be born to be x base ys old in the year of xy.

Your code shall return Not-a-Number or error message if the decomposition cannot be resolved.

Walkthough:

>  foo(2016)
1: '2016' -> '20' '16'
2: 20 base 16 = 32
3: 2016-32 = 1984
>> 1984

> foo(445)
1: '445' ->'44' '5'
2: 44 base 5 = 24
3: 445-24 = 421
>> 421

>foo(7)
1: '7' -> '7' ''
Error, base not defined
>> nan

>foo(10)
1: '10' -> '1' '0'
Error, base 0 don't exist
>> nan

>foo(1805)
1: '1805'->'18' '5'
Syntax error
>> nan

Test cases:

 7    : nan/error
10    : nan/error
78    : 71
445   : 421 
1024  : 1000
1805  : nan/error
1936  : 1891
1984  : 1891
1999  : 1891
2016  : 1984
2015  : 1985
10002 : 9998
10912 : 10759
116015: 115769

Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Boo-urns to input validation! Can you add a full example? \$\endgroup\$
    – Shaggy
    Jun 21, 2017 at 16:14
  • \$\begingroup\$ Do you mean full ungolfed code or full path from, say 445 to 421? \$\endgroup\$
    – Crowley
    Jun 21, 2017 at 16:25
  • \$\begingroup\$ Just a walkthrough of how to get from input to output. \$\endgroup\$
    – Shaggy
    Jun 21, 2017 at 16:26
  • \$\begingroup\$ @Shaggy Thanks for sugegstion. Is it better now? \$\endgroup\$
    – Crowley
    Jun 21, 2017 at 17:16
  • \$\begingroup\$ Shouldn't 1999 result in 1891? \$\endgroup\$
    – Emigna
    Jun 22, 2017 at 8:49
  • \$\begingroup\$ @Emigna Correct. Updated. \$\endgroup\$
    – Crowley
    Jun 22, 2017 at 13:36
3
\$\begingroup\$

Is there a total ordering?

TL;DR:

Given a set of strings, determine whether the characters expose a total ordering based on location in the strings.


In this challenge, strings are used as a predicate to determine the order in which characters should appear in this set. For example, the string

"ONE"

Says:

  • All instances of "N" should appear only after instances of "O"

  • All instances of "E" should appear only after instances of "N"

By this reasoning, the string "FOOOONZAi.EE" follows this ordering, but "NEEEE3#?EAO" does not (there is an "O" after an "N").


Your challenge is to take a set of strings and determine whether these strings define a total ordering without any logical flaws. This would occur as a cycle of any length, such as:

  • "N" must follow "P"

  • "P" must follow "N"

...or such as:

  • "A" must follow "B"

  • "B" must follow "C"

  • "C" must follow "A"

etc.


Rather than strings, you may take in lists of characters or integers if you wish.

Since this is a , you may output any two consistent values for yes or no, such as true and false, zero and non-zero, exception and no exception, etc. Just specify your output format in your answer.


Test Cases

["ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX"] -> true (one possible ordering is "TWFOUIVXNHRE")
["SEVEN"] -> false ("E" must follow "V" which must follow "E")
["ZERO", "FOUR"] -> false ("R" must follow "O", but "O" must follow "U" which must follow "R")
["", ".", "forty", "this->~why();", " -y."] -> true
["AB", "BC", "CD", "DE", "AC", "BD", "CE", "EA"] -> false

(more can be written if needed)

Scoring

This is , so the shortest answer in each language wins.

Sandbox

How can I make this more clear? Any suggestions?

\$\endgroup\$
6
  • \$\begingroup\$ This could be more general if you allow lists as input rather than strings. \$\endgroup\$
    – lirtosiast
    Jul 13, 2017 at 22:18
  • \$\begingroup\$ @lirtosiast So a list of lists of characters? \$\endgroup\$ Jul 14, 2017 at 0:52
  • \$\begingroup\$ I would recommend lists of integers instead of strings. I feel the challenge would be "cleaner" that way, but that's up to you. Also, you should have a test case where where each pair is consistent but the whole set isn't. \$\endgroup\$
    – Zgarb
    Jul 15, 2017 at 7:17
  • \$\begingroup\$ Is this not effectively the same as your previous challenge of whether a directed graph has a cycle? \$\endgroup\$
    – xnor
    Jul 16, 2017 at 1:19
  • \$\begingroup\$ @xnor I suppose it is, though I think the challenging part is collecting the edges by vertex. How about this: I rewrite the challenge to be "Give a valid ordering for a set of strings, guaranteed that one exists"? \$\endgroup\$ Jul 16, 2017 at 3:49
  • \$\begingroup\$ @musicman523 I remember a DAG sorting challenge, I think that would be a dupe of it. \$\endgroup\$
    – xnor
    Jul 16, 2017 at 3:52
3
\$\begingroup\$

Make a Minecraft Crafting Table

\$\endgroup\$
3
  • \$\begingroup\$ +1 This seems like a really fun challenge! I think you should clarify what counts as a recipe. For instance, are gold chestplates and iron chestplates counted as 2 working recipes, or do you need to implement all chestplates to count for 1 recipe? Similarly, for unshaped crafting, does each valid combination (ie ----G---- and -G------- for gold nuggets) count seperately? \$\endgroup\$ Jul 15, 2017 at 0:03
  • \$\begingroup\$ Unfortunately, you were ninja'd by Minecraft 1.12, which adds recipe hints ;) \$\endgroup\$
    – hyper-neutrino Mod
    Jul 15, 2017 at 20:24
  • 1
    \$\begingroup\$ @HyperNeutrino I posted this first (MC 1.12 came out June 7th) so I ninja'd Minecraft \$\endgroup\$ Jul 15, 2017 at 20:25
3
\$\begingroup\$

Self-Improvement

Your Task

You must create a self-mutable program that, when run, outputs a non-zero integer and also overwrites the file with a program that outputs double the number.

For example, if I run the program self-improvement and it outputs 10, it must output 20 when I run it the second time, output 40 the next time, and so on.

Additional Notes

  • You must not rely on any file on the computer other than your program.
  • Said program must consist of only one file.
  • Of course, no loopholes that are banned from the entire site.
  • You can assume that your program won't go tested beyond the range -2^16 to 2^16-1.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ no loopholes banned -> no loopholes that are banned, overwrite -> overwrites. Also, something on how far this needs to go might be important - does it have to work infinitely, or only to INT_MAX for the language in question? If you choose the second option, keep in mind language with very small numeric caps. Otherwise, welcome to PPCG, I really like this question, and I'm glad you Sandbox'd it :) \$\endgroup\$
    – Stephen
    Jul 17, 2017 at 21:33
  • \$\begingroup\$ @StepHen Thanks; I decided that they can assume that the parameters won't go beyond INT_MAX. \$\endgroup\$ Jul 17, 2017 at 21:38
  • 2
    \$\begingroup\$ In case anyone needs to find it at some point, don't forget about this standard loophole. \$\endgroup\$
    – Stephen
    Jul 17, 2017 at 22:24
  • \$\begingroup\$ @Artyer I stated "any nonzero integer". That excludes 0. \$\endgroup\$ Jul 17, 2017 at 22:55
  • \$\begingroup\$ @LawfulLazy I didn't read that too well. \$\endgroup\$
    – Artyer
    Jul 17, 2017 at 22:58
  • \$\begingroup\$ @Artyer I'll make sure to embolden it. I've also set a minimum integer range for StepHen. \$\endgroup\$ Jul 17, 2017 at 22:59
3
\$\begingroup\$

How high can you count in English?

Challenge

In 500 bytes (or fewer) write a program that outputs a list of the English word forms of as many consecutive integers greater than zero as you can.

For example, score 6:

one two three four five six

Example submission (hopefully you can do better than this):


Python 3, score 43 (488 bytes)

print(["one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen", "sixteen","seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two","twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven","twenty-eight","twenty-nine","thirty","thirty-one","thirty-two","thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven","thirty-eight","thirty-nine","forty","forty-one","forty-two","forty-three"])

Try it online!


Scoring and rules

For each language, the person whose code counts the highest wins. In case of a tie, the person who submitted first wins.

  • No modules, libraries, builtins that convert from numeric to word form are allowed.
  • You must output all integers from 1 (one) to n (your score) without missing any. If you want to output 0 (zero) as well, that's fine.
  • You are allowed up to 500 bytes of code. Your code may be a full program or function.
  • Number format: for consistency, all numbers must match the output of this site.
  • Standard loopholes apply (of course)
  • Standard output rules apply
\$\endgroup\$
10
  • 2
    \$\begingroup\$ Come on, you could at least make your example better by just using a single space-separated string ;) but nice challenge! :) \$\endgroup\$
    – hyper-neutrino Mod
    Jul 18, 2017 at 18:00
  • 1
    \$\begingroup\$ Alternate title: How high can you count in English? \$\endgroup\$
    – Stephen
    Jul 18, 2017 at 18:06
  • \$\begingroup\$ You may, however, omit "and" if you'd like. do we have to omit and or not? Personally, I'd say you wouldn't as it 'sounds more correct'. \$\endgroup\$
    – Okx
    Jul 18, 2017 at 18:11
  • \$\begingroup\$ @StepHen changed, thanks. \$\endgroup\$
    – wrymug
    Jul 18, 2017 at 18:15
  • \$\begingroup\$ Your edit doesn't answer my question. Do we have to omit and or not? \$\endgroup\$
    – Okx
    Jul 18, 2017 at 18:15
  • \$\begingroup\$ @Okx I take your point. Removed. \$\endgroup\$
    – wrymug
    Jul 18, 2017 at 18:28
  • 1
    \$\begingroup\$ I'm not sure this adds to existing number-to-english challenges like this or this. Past getting the same basic pattern of digits down, the question seems to be how many prefixes for powers of 1000 one can compress into the remaining bytes. \$\endgroup\$
    – xnor
    Jul 18, 2017 at 18:33
  • 1
    \$\begingroup\$ Off the jokes, what if I can count to infinity? \$\endgroup\$ Jul 20, 2017 at 13:40
  • \$\begingroup\$ @courtois I don't see how that would be possible, but I guess you'd win \$\endgroup\$
    – wrymug
    Jul 20, 2017 at 13:42
  • \$\begingroup\$ @rosslh yeah you're right, I just saw the sentence Number format: for consistency, all numbers must match the output of [this](https://lingojam.com/NumbersToWords) site. And for my method, it would have been with million of billion of billion of ... though the site stops at one hundred novenonagintanongentillion, something like 3002 zeros. \$\endgroup\$ Jul 20, 2017 at 13:43
3
\$\begingroup\$

ASCII addition

Objective

Given two strings, your job is to:

  1. Convert each character to their respective ASCII decimal value
  2. Concatenate the numbers into one large number
  3. Add these values together
  4. Get the ASCII characters represented of each pair of numbers starting from the right (or if there are not enough numbers, take a number alone)
  5. Leave unprintables (ie not in the range 32 - 126), and output the rest

An example for HELLO and WORLD

"HELLO"    + "WORLD"
H E L L O  + W O R L D
7269767679 + 8779827668
1 60 49 59 53 47    (separated to show ASCII conversion easily)
   <  1  ;  5  /    convert to ASCII by converting pairs to their respective characters (note: you start from the last pair)
<1;5/               output (note there is no 0x01) 

Notes

  • Each string will be a maximum of 6 characters long
  • Input will always contain readable ASCII characters
  • You have to take pairs of numbers from the end of the sum and convert each one of them to ASCII
  • You must not print unreadable characters if their values appear and instead skip them

Examples

ABC + XYZ  //input
656667 + 888990
1 54 56 57
   6  8  9       //again 0x01 is left out
689      //output

Rules

  • Your submission can be either a program or a function

This is so the program with the shortest bytecount wins!

Sandbox Questions

  • Are the specs clear enough?
  • Will this question give me hats?
  • Any better title suggestions?
\$\endgroup\$
12
  • \$\begingroup\$ What range of ASCII characters do we need to be able to handle in the input? Only printable characters or any? \$\endgroup\$ Dec 20, 2016 at 20:07
  • 1
    \$\begingroup\$ I swear we've had this challenge, but I can't seem to find it ... \$\endgroup\$ Dec 20, 2016 at 20:21
  • \$\begingroup\$ Edited that into the specs \$\endgroup\$
    – user41805
    Dec 20, 2016 at 20:22
  • \$\begingroup\$ @TimmyD How's this now? \$\endgroup\$
    – user41805
    Dec 21, 2016 at 7:28
  • \$\begingroup\$ what if a character is unprintable? do we still need to output it then? \$\endgroup\$ Dec 21, 2016 at 7:46
  • \$\begingroup\$ @DestructibleWatermelon Yes \$\endgroup\$
    – user41805
    Dec 21, 2016 at 7:56
  • \$\begingroup\$ Better wording. Given that a bunch of control codes are possible, some test cases that demonstrate expected behavior when (e.g.) 11 or 13 occur in the output would be of good value. \$\endgroup\$ Dec 21, 2016 at 13:49
  • \$\begingroup\$ @TimmyD Do you think it would be a good idea if I restrict the output to displaying only characters if their values are between 32 and 126 because outputting other values might be difficult in some languages? \$\endgroup\$
    – user41805
    Dec 21, 2016 at 13:54
  • \$\begingroup\$ That may be a better way to go, but you'll need to be very careful with the wording. For example, suppose that the output number is ...226... and the 26 is slated to be the pair of digits that get converted to ASCII. Obviously, that's outside the printable range, so let's look at the next digit, but now 226 is also outside. Does that mean just the 6 is skipped? The 26 is skipped? The 226 is skipped? \$\endgroup\$ Dec 21, 2016 at 13:58
  • \$\begingroup\$ @Cowsquack You don't say precisely (but we see it in the test case) how many digits we need to parse at a time, before outputting. \$\endgroup\$ Jul 18, 2017 at 14:06
  • \$\begingroup\$ @V.Courtois Is this clearer now? \$\endgroup\$
    – user41805
    Jul 19, 2017 at 12:48
  • \$\begingroup\$ @Cowsquack This is! In fact you could see, in the comments some were wondering too if we had to print things like 125 -> }. \$\endgroup\$ Jul 19, 2017 at 12:55
3
\$\begingroup\$

Deduplicate equivalent expressions

Suppose we wanted to generate all expressions containing at most 2 of + and −. We might have a list like this:

a + b + c         b + c + a
a + b - c         b + c - a
a - b + c         b - c + a
a - b - c         b - c - a
a + c + b         c + a + b
a + c - b         c + a - b
a - c + b         c - a + b
a - c - b         c - a - b
b + a + c         c + b + a
b + a - c         c + b - a
b - a + c         c - b + a
b - a - c         c - b - a

There is a lot of repetition here. It surely isn't necessary to include all of a + b + c, a + c + b, b + a + c, b + c + a, c + a + b, and c + b + a, since they all mean the same thing. This can be deduced from knowing that, for any x and y, x + y is the same as y + x.

Similarly, b + a - c and a - c + b are equivalent. To deduce this, one must know that, for any x and y, x - y is the same as x + (-y).

Let's assume the following:

[1]: a + b == b + a
[2]: a - b == a + -b

Then, we can deduce that b + a - c and a - c + b are equivalent:

start:  b + a - c
        b + a + -c        by 2
        a + b + -c        by 1
        a + -c + b        by 1
end:    a - c + b         by 2

Therefore, they are the same. After performing similar proofs, we are left with the list:

a + b + c
a + b - c
a - b + c
a - b - c
b - a + c
b - c - a
c - b - a

Definition of an expression

An expression can be described as:

variable   = "a" | "b" | "c" | ... | "y" | "z";
digit      = "0" | "1" | "2" | ... | "8" | "9";
number     = digit . digit*;
operator   = "!" | "#" | "$" | "%" | "&" | "*" | "+"
           | "~" | "-" | "." | "/" | ":" | ";" | "<"
           | "=" | ">" | "?" | "@" | "^" | "_" | "`"
           | "|";
data       = number | variable;
subexpr    = data | operator* . data;
expression = subexpr
           | subexpr . operator . expression;

Where | suggests alternatives, . suggests concatenation (with potential whitespace around each operand), * suggests "0 or more times", and " is a string literal.

x + y, j * i - 3, u & 4 * 2 < ~4, q % ~*^t and r are all expressions.

You should assume all operators are left-associative.

Definition of assumptions

An assumption is a pair of expressions said to be equivalent. This means one can be transformed into the other. When performing a transformation using an assumption, one replaces all the appropriate variables and maintains the numbers as they are. (These "variables" can also be sub-expressions, which is any expression not using an operator in the assumption.)

For example, if the assumption is !a == a + 5, then one can transform t + 5 into !t and 3 + 5 into !3.

Another example: if the assumption is a + b == a * b @ b, then 5 + 2 can become 5 * 2 @ 2 and z * 3 @ 3 can become z + 3, but z * 4 @ a cannot be reduced further using this rule.

One last example: if the assumption is a < b == a, then 1 + 3 & 5 < 2 * 3 + 6 would become 1 + 3 & 5, and 1 + 2 < x + y < 7 $ q would become 1 + 2, since it would be equivalent to (1 + 2) < (x + y) < (7 $ q), which is thus 1 + 2.

If either side of the assumption is a single variable, numbers are excluded from this assumption. E.g., the assumption a == 3 would only apply to variables.

Expression equality

Two expressions are equal if they can be proven to be the same. Variables must be the same for each expression; for example, a + b is not by default the same as b + c.

Challenge

Your task is to remove "duplicate" expressions given some assumptions. You can use any unambiguous symbol or method, including taking a pair of strings, to represent an expression. The expressions remaining in the result do not necessarily have to be in the set, but must be equivalent by the given assumptions. E.g., if you have a + b - c and b - c + a in the input, you can have -c + b + a represent these in the resultant set. You should try each equation in the order that it's given to you (to simulate "precedence").

The input consists of a list of assumptions and a list of input expressions. The input expressions can be an array or container of strings or string pointers, or in any way standard to your language. (E.g., for C, one should expect null-terminated strings.) The input format must be consistent for all runs.

The output can be a list representation (as is standard to your language), can be separated by newlines (\r, \n, and \r\n are acceptable), or separated by commas. The output format must be consistent between runs.

This is a , so the shortest program in bytes wins.

Test cases

Every output is merely an example, and is not the only valid output.

Assumptions: { e1 == e2, e3 == e4, ... eN-1 == eN }
Input: { expr1, expr2, ... exprN }
Output: { expr1, expr2, ..., exprK }

Assumptions: { "a + b" == "b + a" }
Input: { "3 + 4", "4 + 3", "5 * a", "a + 2", "2 * a", "a * 5", "a + b", "2 + a" }
Output: { "3 + 4", "5 * a", "a + 2", "2 * a", "a * 5", "a + b" }

Assumptions: { "a + 0" == "a", "a * 1" == "a", "a * b" == "b * a", "a + b" == "b + a" }
Input: { "1 * 2 * 3", "3 * 2 + 0", "1 + 2 + 3" }
Output: { "1 * 2 * 3", "1 + 2 + 3" }
    OR: { "2 * 3", "1 + 2 + 3" }

Assumptions: { "~a" == "a ~ a" }
Input: { "~z", "z ~ z", "~a", "~~a", "a ~ a ~ a ~ a" }
Output: { "~a", "~z", "~~a" }

Assumptions: { "a + b" == "0" }
Input: { "x + y", "0", "3 + y + a + v + k", "75", "4 + 2" }
Output: { "0", "75" }

Assumptions: { }
Input: { "x + y", "x + y", "y + x", "3", "3 ! 3" }
Output: { "x + y", "y + x", "3", "3 ! 3" }

Assumptions: { "j" == "3" }
Input: { "v + t", "z", "q", "q + r + t", "4 + 2" }
Output: { "v + t", "z", "q + r + t", "4 + 2" }

Assumptions: { "a" == "b" }
Input: { "a", "b + c", "e % t", "q & t", "!3", "z" }
Output: { "a", "b + c", "e % t", "q & t", "!3" }

Assumptions: { "1 & 0" == "0", "1 & 1" == "1", "0 & 0" == "0", "a & b" == "b & a", "0 ? a : b" == "b", "1 ? a : b" == "a" }
Input: { "1 & 1 & 0", "j & k", "y & z", "z & y", "1 & 0 ? k & j : 0" }
Output: { "0", "j & k", "y & z" }
\$\endgroup\$
9
  • \$\begingroup\$ Several of your expressions are inconsistently quoted. I also think you should explain what should happen when the assumption is something like 3 == a. Would I remove one of: 5, 7? It seems if you had a == b as the assumption you would, but the other one is counter-intuitive to me. Also, a == b is rather odd on its own, perhaps that is also a good test case. Also, the empty assumption if you intend to allow it. \$\endgroup\$ Jul 17, 2017 at 3:18
  • \$\begingroup\$ @FryAmTheEggman Could you clarify your first question? Are you asking what should happen if 5, 7 is the input given the assumption a == 3? \$\endgroup\$ Jul 17, 2017 at 4:00
  • \$\begingroup\$ Yes, that's what I meant. \$\endgroup\$ Jul 17, 2017 at 4:08
  • \$\begingroup\$ 1. subexpr = data | operator* . data; is surely equivalent to just subexpr = operator* . data;? 2. For the second test case it would be more illustrative to include an example output like { "0 * 2 + 3", "1 + 2 + 3" }. 3. I'm not sure what you mean by "If either side of the assumption is a single variable, numbers are excluded from this assumption". Is it that an assumption a == 3 with input {"b == 2", "c == 2", "4 == 2"} should give output e.g. {"3 == 2", "4 == 2"} rather than {"3 == 2"}? \$\endgroup\$ Jul 17, 2017 at 7:43
  • \$\begingroup\$ @PeterTaylor 1. yeah, I original had * mean "1 or more"; will fix. 2. good idea. 3. Well, the way that input would be parsed is b = = 2, with a binary = followed by a unary =. Could you perhaps use a different symbol? I don't quite understand your confusion. \$\endgroup\$ Jul 17, 2017 at 16:53
  • \$\begingroup\$ Sure: assumptions: { "a" == "3" }; input: {"b + 2", "c + 2", "4 + 2"}. Is {"3 + 2", "4 + 2"} the correct output? \$\endgroup\$ Jul 17, 2017 at 18:03
  • \$\begingroup\$ @PeterTaylor Yes, it is. \$\endgroup\$ Jul 17, 2017 at 18:34
  • \$\begingroup\$ The definition of assumptions includes an assumption with more than one operator, but none of the test cases do. I would think that's an important thing to test. \$\endgroup\$ Jul 26, 2017 at 11:06
  • \$\begingroup\$ @PeterTaylor Added. \$\endgroup\$ Jul 26, 2017 at 19:32
3
\$\begingroup\$

Challenge: Count integers 1 to 10, but slowly on a time delay.

Your challenge is to print the integers 1 to 10 to the screen with each integer separated by a newline, but on a time delay, such that it should take “n” seconds before the integer “n” is printed to the screen. For example, the program will wait 1 second before printing 1 and a newline, and then the program will wait 2 seconds before print 2 and a newline, and then the program will wait 3 seconds before print 3 and a newline.

So the expected standard output to the screen is this:

1
2
3
4
5
6
7
8
9
10

But the program will patiently wait “n” seconds before printing the integer “n” to the screen, so as your program may interpret it as …

waiting 1 second …

1

waiting 2 seconds …

2

waiting 3 seconds …

3

, and so on …

Restrictions:

1) Since some programming languages may not have a sense of system time, you are not allowed to use any modules/libraries/functions which can measure the time of your program within your program. Therefore all programming languages can be used. This restriction puts all the programming languages on an equal level.

2) Restriction 1 makes it such that you are required to write a function which takes about 1 second to process, and then you can rerun that function “n” integer of times before printing the next integer “n” in 1 to 10 to the screen. You can call your function whatever you want or if you can get away without naming the function then you can do that, too. So, your program would see this behind the scenes:

performing function fx 1 time. #which the arbitrary function fx takes about 1 second to process.

1

performing function fx 2 times

2

performing function fx 3 times

3

… and so on

3) Therefore, your program should take about 1 + 2 + 3 + 4 … + 10 = 55 seconds to finish printing all the integers from 1 to 10 to the screen. Since you need to write a function that takes about 1 second to process, acceptable solutions can be off by plus or minus 2 seconds from 55 seconds.

4) You must time your script which counts the integers 1 to 10 on a delay, so you can use any external program to time your script. I recommend using the bash function time, and giving me the “real” time or actual elapsed time of your script in seconds. If you time your script another way, tell me how you did it. Give me three digits after the decimal place for the real time in seconds. Do not round or truncate.

winning condition:

The winning condition is the fastest program in terms of actual elapsed real time in seconds which is closest to 55 seconds. If, for example, one submission is 54.9 seconds and another is 55.1 seconds, the 55.1 second submission wins because 54.9 seconds is too fast. Again, the point of this program is to slowly print integers to the screen.

Again, it should take approximately 55 +/- 2 seconds to print the integers 1 to 10 to the screen.

\$\endgroup\$
7
  • \$\begingroup\$ I modified my problem in such a way that no programming language should have an advantage. \$\endgroup\$
    – xyz123
    Jul 28, 2017 at 6:17
  • \$\begingroup\$ you are not allowed to use any modules/libraries/functions which can measure the time of your program Does this mean things like Stopwatch, getting the DateTime, Thread.Sleep, etc? \$\endgroup\$ Jul 28, 2017 at 9:56
  • \$\begingroup\$ Nice challenge by the way but I'm not sure I like the winning condition. What's wrong with a code-golf? Also if I was you I'd trim some of the fluff down, at the moment there is a lot of text to information. \$\endgroup\$ Jul 28, 2017 at 10:00
  • 2
    \$\begingroup\$ Will this not also vary dependent on what machine is running it? I really like the idea but I can imagine it being quite hard to test - especially with that winning condition, as I can imagine it coming down to hundredths of seconds, which would doubtlessly vary depending on the computer running it. Really like the idea nonetheless \$\endgroup\$
    – space junk
    Jul 28, 2017 at 11:01
  • 2
    \$\begingroup\$ I suppose you could do it by only running them on TIO? TIO's time limit is 60 seconds so you'll have ample time, & it should be a bit more uniform in terms of processing time. \$\endgroup\$
    – space junk
    Jul 28, 2017 at 11:02
  • \$\begingroup\$ Yes, TheLethalCoder you would not be allowed to do that. After I thought about, I realize that different computers may have different specifications for runtimes, although I suppose the winning condition could be the least number of bytes, but I was thinking about setting the winning condition to the fastest program which is closest to 55 seconds because if somebody wrote a program which had less bytes, but it was 1.9 seconds over 55 seconds, then it might be too slow for a lot of the other programs which had more bytes, but were faster. \$\endgroup\$
    – xyz123
    Jul 28, 2017 at 15:08
  • \$\begingroup\$ Although if I set the winning condition to the least number of bytes, then I believe that I would have to increase the restraint to acceptable programs cannot be off by +/- 1 second from 55 seconds. \$\endgroup\$
    – xyz123
    Jul 28, 2017 at 15:09
3
\$\begingroup\$

Random number from 0 to n


Challenge

Write a program/function that, given a positive integer n, outputs a uniformly random integer from 0 to n.

Input

  • Input will be a positive (non-zero) integer.
  • It will be in your language's number handling capabilities. // reword

Output

  • Output must be a uniformly (pseudo)random integer.
  • Every integer in the range [0, n) must have an equal chance of being outputted.
  • You may assume that your chosen language's built-in RNG is uniform.
  • Must be in 0 to n, in [0, n), ≥ 0 and < n

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
  • Built-in functions that perform this task are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

Note that this challenge is tagged and hence will have non-deterministic outputs.

Incoming!


Sandbox

  • We seriously don't have this already?!
\$\endgroup\$
14
  • \$\begingroup\$ Interesting idea, but how will the test cases work? Also I imagine builtins will be the shortest for many languages \$\endgroup\$ Aug 9, 2017 at 8:39
  • \$\begingroup\$ @Chris_Rands not all challenges need test cases. \$\endgroup\$ Aug 9, 2017 at 10:27
  • \$\begingroup\$ Definition of random? We don't have it because it's a bad idea. \$\endgroup\$
    – feersum
    Aug 9, 2017 at 11:32
  • \$\begingroup\$ @Chris_Rands They're going to be random test cases. :P And yes, built-ins, but I'm afraid I don't like banning built-ins. \$\endgroup\$ Aug 9, 2017 at 12:39
  • \$\begingroup\$ @feersum Yeah, I have to iterate over that better. Basically, it has to be uniformly pseudo-random. Any suggestions? \$\endgroup\$ Aug 9, 2017 at 12:41
  • \$\begingroup\$ @AdmBorkBork If you do find a dupe, please let me know! I've searched everywhere and asked in chat, but I couldn't find one. \$\endgroup\$ Aug 9, 2017 at 12:42
  • \$\begingroup\$ Extremely closely related \$\endgroup\$ Aug 9, 2017 at 12:54
  • \$\begingroup\$ @AdmBorkBork Aha, I didn't find that (probably because it isn't tagged with number :P). It's very close but it has some arbitrary restrictions... Good enough to have a regular one? \$\endgroup\$ Aug 9, 2017 at 13:19
  • 1
    \$\begingroup\$ The only way an answer can be valid here and fail the "arbitrary restrictions" there is if it's a trivial call to a built-in, so this question doesn't add anything to the site. \$\endgroup\$ Aug 9, 2017 at 14:12
  • \$\begingroup\$ Now define pseudorandom. Also, using a hardware random generator is not allowed? \$\endgroup\$
    – feersum
    Aug 9, 2017 at 14:16
  • \$\begingroup\$ @feersum I am not sure how much more I can define "random". I have edited in the fact that you can assume that your language's RNG is uniform. Where have I disallowed hardware random generators? \$\endgroup\$ Aug 10, 2017 at 2:07
  • \$\begingroup\$ it has to be uniformly pseudo-random Pseudorandom is not random. \$\endgroup\$
    – feersum
    Aug 10, 2017 at 12:23
  • \$\begingroup\$ So now the only definition of "random" we have is that built-ins that are designated as random number generators are considered "random". So the challenge can only be answered by builtins, since there is no other definition provided. \$\endgroup\$
    – feersum
    Aug 10, 2017 at 12:24
  • \$\begingroup\$ @totallyhuman What if the language has a built-in RNG which is not a uniform RNG? \$\endgroup\$
    – isaacg
    Aug 12, 2017 at 13:09
3
\$\begingroup\$

Case Matching Find Replace

Take three inputs, a string of text, T; a string of characters to replace, F; and a string of characters to replace them with, R. For each substring of T with the same (case insensitive) characters as F, replace them with the characters in R. However, keep the same case as the original text.

If there are more characters in R than F, the extra characters should be the same case as they are in R. If there are numbers or symbols in F, then the corresponding characters in R should keep the case they have in R. F will not necessarily appear in T.

You can assume all text will be in the printable ASCII range.

Examples

"Text input", "text", "test" -> "Test input"

"tHiS Is a PiEcE oF tExT", "is", "abcde" -> "tHaBcde Abcde a PiEcE oF tExT"

"The birch canoe slid on the smooth planks", "o", " OH MY " -> "The birch can OH MY e slid  OH MY n the sm OH MY  OH MY th planks"

"The score was 10 to 5", "10", "tEn" -> "The score was tEn to 5"

"I wrote my code in Brain$#@!", "$#@!", "Friend" -> "I wrote my code in BrainFriend"

"This challenge was created by Andrew Piliser", "Andrew Piliser", "Martin Ender" -> "This challenge was created by Martin Ender"

// Has a match, but does not match case 
"John does not know", "John Doe", "Jane Doe" -> "Jane does not know"

// No match
"Glue the sheet to the dark blue background", "Glue the sheet to the dark-blue background", "foo" -> "Glue the sheet to the dark blue background"

// Only take full matches
"aaa", "aa", "b" -> "ba"

// Apply matching once across the string as a whole, do not iterate on replaced text
"aaaa", "aa", "a" -> "aa"
\$\endgroup\$
8
  • \$\begingroup\$ Example(s) where the replacement string narrowly does not appear in the text might help. \$\endgroup\$
    – isaacg
    Aug 17, 2017 at 19:55
  • \$\begingroup\$ @isaacg Added one, let me know if it's not what you were thinking \$\endgroup\$
    – Andrew
    Aug 17, 2017 at 21:11
  • \$\begingroup\$ What is the expected output for "aaa","aa","b" and "aaaa","aa","a"? \$\endgroup\$ Aug 17, 2017 at 21:33
  • \$\begingroup\$ Will we guaranteed that F will appear at least once in T? \$\endgroup\$
    – Shaggy
    Aug 17, 2017 at 21:58
  • \$\begingroup\$ @Shaggy F will not necessarily appear in T. \$\endgroup\$
    – Andrew
    Aug 17, 2017 at 22:04
  • \$\begingroup\$ @fireflame241 Added your two examples, good catch. \$\endgroup\$
    – Andrew
    Aug 17, 2017 at 22:07
  • \$\begingroup\$ I would personally appreciate some kind of note on test case 3. It took me quite a while to realize that John Doe actually appears in full in the input string, rather than requiring we be able to replace all instances of John with Jane in that situation. \$\endgroup\$ Aug 18, 2017 at 17:45
  • 1
    \$\begingroup\$ @KamilDrakari Added explanation for that case and a few others. Thanks for the feedback! \$\endgroup\$
    – Andrew
    Aug 18, 2017 at 19:03
3
\$\begingroup\$

n-gon in m-gon

What is the greatest equilateral triangle you can fit into a regular pentagon? This is what this challenge is about, but with regular n-gons/m-gons.

Challenge

Given two integers m,n greater or equal to 3, find the maximal ratio of the areas of the two polygons such that the m-gon is completely contained in the n-gon.

Details

We are always talking about regular polygons, this means that all sides have the same length and all vertices are on a circle. The output can be a floating point-, fixed point- or rational number and must be correct to three decimal places.

Examples

 m  n  ratio (area m-gon / area n-gon)
 x  x  1 (for all x)
 3  4  1/4*sqrt(3) = 0.4330
 4  3  12/(7*sqrt(3)+12) = 0.4974
 3  6  1/2 = 0.5
 6  3  2/3 = 0.6667
 

Would be nice to have larger examples.

\$\endgroup\$
2
  • \$\begingroup\$ You may consider changing the language of the initial problem specification and input/output chart to specify that you are comparing the areas of the m- and n- gons \$\endgroup\$ Sep 26, 2017 at 21:37
  • \$\begingroup\$ I see what you mean but right now I have difficulty coming up with a better wording (english is not my native language), if you have a better suggestion feel free to directly edit it! \$\endgroup\$
    – flawr
    Sep 26, 2017 at 22:39
3
\$\begingroup\$

Got Your PIN!

I bet I can write down your PIN! 0000 0001 0002 0003 ... 9999.

Task: Write a program that outputs a string containing all possible four digit PINs.

The string should not contain any whitespace (trailing newline is okay).

Score: Length of program (in bytes) + length of output.

Explanation

The output string only needs to contain each PIN somewhere in it; digits can be reused. For instance the string “123456789” contains the PINs 1234, 2345,3456,4567,5678,and 6789. By reusing digits, it's possible to save a significant amount of space from the naive implementation (0000000100020003...9999).

At best, this could be written as a 10,003 digit string. 4 digit for the first PIN, then one more digit for the other 9999 PINs.

Testing your code

I've written a basic Python script that can check your solution and indicate any PINs you are missing.

import sys
s = sys.stdin.readline()
passes = True
for ix in range(10000):
    pin = "%04d" % (ix)
    if s.find(pin) == -1:
        print("Missing PIN %s" % pin)
        passes = False

if passes:
    print('Result passes!')
print('String length is %d characters.' % len(s))
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Nice, but I think you need to replace code-golf with code-challenge as this isn't just scored by shortest code. \$\endgroup\$
    – Adám
    Sep 28, 2017 at 22:25
  • \$\begingroup\$ Very related \$\endgroup\$
    – H.PWiz
    Sep 28, 2017 at 22:29
  • \$\begingroup\$ This is just codegolf.stackexchange.com/q/42728/194 with hard-coded input, and hence qualifies as a dupe. \$\endgroup\$ Sep 29, 2017 at 11:08
  • \$\begingroup\$ Too bad it's a duplicate... but now I know about De Bruijn sequences! \$\endgroup\$
    – Dominic A.
    Sep 29, 2017 at 23:19
  • \$\begingroup\$ @PeterTaylor: I think there's one even more dupey than that; I've been trying to find it all day. The "background" to it was a keypad on a building door that had a 4-digit code. \$\endgroup\$
    – Shaggy
    Sep 30, 2017 at 0:59
3
\$\begingroup\$

Roll identical boson dice

When you roll two dice, the chance of a 5 and 6 in either order is a 2 in 36 (or 1/18), since it could happen as (5,6) or (6,5). But (6,6) can only happen one way and has a 1 in 36 chance.

Our dice will instead work as identical bosons: (5,6) and (6,5) are a single outcome {5,6} that is equally likely to {6,6}. So, each of these 21 unordered pairs is equally likely, with chance 1/21.

{1,1}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,2}, {2,3}, {2,4}, {2,5}, {2,6}, {3,3}, {3,4}, {3,5}, {3,6}, {4,4}, {4,5}, {4,6}, {5,5}, {5,6}, {6,6}

Similarly, for 3 dice, [5,5,6], [5,6,5], and [6,5,5] all count as a single outcome {5,5,6}, but [6,5,6] is different.

Task: Output a random roll of n boson dice, so that each possible result is equally likely as an unordered multiset, i.e. when sorted.

It's OK if your output is ordered as long as the overall probabilities are right. You may sometimes output [5,6] and sometimes [6,5] as long as their total chance is 1/21. They don't have to each be 1/42 chance. You could output [5,6] with 1/21 chance and never [6,5].

Input: A positive integer n

Output: A random list of n numbers from 1 to 6, so that each outcome is equally like when taken as an unordered multiset.

Time restriction: Your code has work up to n=50 within 1 minute.

\$\endgroup\$
3
  • \$\begingroup\$ I think it's unlikely that there'll be an algorithm for this terser than simply constructing the list of all possibilities, then selecting a random element from it. As such, I'm not sure the randomness adds to the task here. It's possible I'm wrong. (I toyed with some methods of restricting complexity to ban this solution, but I couldn't find one I was satisfied with.) \$\endgroup\$
    – user62131
    Jun 22, 2017 at 22:48
  • \$\begingroup\$ @ais523 I know some fairly nice methods to generate these directly, but I don't know if they'll beat out the boring one you suggest. Rolling repeatedly until sorted is also boring and direct. Maybe a complexity restriction is needed. I'll see what I can golf up. \$\endgroup\$
    – xnor
    Jun 23, 2017 at 7:24
  • \$\begingroup\$ with the (new) time restriction this is more like math-golf than code-golf. Can you give away any of your "nice methods"? Is it the weighted probability of every digit of the 50-digit number ,one of them? \$\endgroup\$
    – user72269
    Oct 2, 2017 at 17:29
3
\$\begingroup\$

Limited-Information Maze-Solving Bot

(Still in draft/beta format. Feedback welcome.)

Based on a challenge idea I posted in chat and the ensuing conversation. Thanks to NathanMerrill, zgarb, and Jonathan Frech for assistance in fleshing this out.

The challenge

You're writing two separate programs/functions/routines/etc. The first, which we'll call the helper program, takes the input maze and calls the second, which we'll call the solving bot. The solving bot must solve the maze based on its interaction with the helper program.

The maze is 51x51 characters in size. For clarity in this challenge description, it is composed of # walls and corridors, but you can use any two distinct, consistent ASCII characters of your choice. E.g., use ! for walls and x for corridors, use 1 for walls and 0 for corridors, etc. This maze is one of many that will be the input to your helper program/function.

The maze start is always guaranteed to be somewhere on the left-most column, and the exit is always guaranteed to be somewhere on the right-most column. The maze is guaranteed to have at least one path from the start to the exit. As a result of this construction, the very top row and very bottom row are all #, and the very left and right columns are all # except for the start and exit.

The solving bot that you're creating needs to find a solution to the maze (not necessarily the shortest), but is limited in that it can only "see" a new 5x5 section of the maze at a time. The bot is scored by how many times it needs to request a new 5x5 section from the helper program/function.

The upper bound is obviously to simply request every possible 5x5 section, for a score of around 100. The lower bound is where someone with perfect knowledge of the maze can request only those 5x5 sections containing the exact route of the shortest solution, possibly as low as 10. Your bot will be run through (1000?) different mazes, and the bot with the fewest total requests will be the winner.

The solving bot is placed on the left-hand side where the start is, and the first 5x5 section is provided for free. However, the bot doesn't know where, vertically, it is on the left-hand side of the maze. It could be in the top corner (as in the example below), in the bottom corner, or anywhere in between.

Input/Output

The code you're writing be required to take the maze as an input (STDIN, a file to read, etc.) and call a subroutine of some sort for the solution bot.

Input: (1000?) 51x51 mazes Output: How many total requests your solving bot took

Yes, this is a non-observable requirement to be on the honor system and ensure the two "halves" of your program (i.e., the I/O half and the solving half) talk to each other correctly and accurately. I trust the community enough to believe that this is OK.

Further rules

Your solving bot should be deterministic. That is, when presented with the same maze two or more times, it should request the same number of 5x5 sections.

Example Maze

(generated from http://www.delorie.com/game-room/mazes/genmaze.cgi )

###################################################
            #     # #   # #   #   #         #   # #
# ######### ##### # # # # # # # # # ####### ### # #
#   #       #   #   # # #   # # #         #   # # #
### # ####### # # ### # ### # # ############# # # #
#   #   #   # # #   # #     # #   #   #   # #   # #
# ####### # ### ### ####### # ### # # # # # # ### #
#     #   #       #       # # #   # # # # # # #   #
##### # ################# # # # ### ### # # # # ###
#   #       #     #         # #         # # # #   #
### ####### ##### # ######### ##### ##### # ##### #
#   #           #   #       #     # #   # #   #   #
# ##### ### ### # ### ########### # # # # # # ### #
#       # # #   # # #   #         # # # #   # #   #
######### # ### # # ### # ######### # ##### # # ###
#       # #   #   # # #   #       # # #     # # # #
# ##### # ### ##### # ##### ##### # # # ##### # # #
#     #   #       # # #   #     # #   # #     # # #
### # ####### # ### # # # ##### # ### # ####### # #
#   #     #   #   # #   #   #   #   # # #         #
# ####### # ##### # ####### # ### # ### # ### # ###
# #     # #     # #       # # #   #   #   #   #   #
# # ### # ##### # # ####### # # ##### ####### ### #
#   #   #       # #     #   # #     #   #   # # # #
##### ########### ##### # ########### # # # # # # #
# #   #       #   #   # #       #   # # # # #   # #
# # ### # ##### ### # # ### ### # # # ### # ##### #
#   # # #       #   #     # # #   # #   # #   #   #
##### # # ##### # ##### # # # ##### ### # ### # ###
#   # # #     # #   #   # #   #         #   # #   #
# # # # ##### # ### # ### ##### ### ##### # # ### #
# # #   #     #     # # #         #       # # #   #
# ####### ########### # ############### ##### # ###
#     #   #   #       #             # #   #   # # #
##### # ### # # ####### ######### # # ### # ### # #
#   #     # # # #       #       # #   #   # #   # #
# ##### # ### # # ######### ### ##### # ### # ### #
# #     #   #   #     #   # #   #     # #   #     #
# # ####### ######### # # # ##### ### # # ##### ###
# # # #     #     #   # # #     # # #   #     #   #
# # # # ######### # ##### ##### # # ##### ### # # #
#   #   # #     # # #     #   #     #   # #   # # #
### ##### # ### # # # ### # # ####### ### ### # # #
# #     # # #   # # # #   # #       #       #   # #
# ##### # # # ### # # ##### ####### ####### ##### #
#       #   # #   # #       # #   # #       #   # #
### ######### # # # ######### # # # # ####### # # #
#   #   #   # # # #   #         #   #     #   #   #
# ### # # # # # ##### # ####### ########### ##### #
#     #   #   #       #       #             #      
###################################################

Example starting block:

#####

# ###
#   #
### #
\$\endgroup\$
11
  • \$\begingroup\$ Does the solving bot also have to find the maze's start by scanning the left side or is it placed at the start position? \$\endgroup\$ Sep 17, 2017 at 19:18
  • \$\begingroup\$ related \$\endgroup\$
    – Liam
    Sep 17, 2017 at 21:47
  • \$\begingroup\$ @JonathanFrech Good point. We'll say that it's placed at the start position and the first 5x5 area is free. \$\endgroup\$ Sep 18, 2017 at 16:39
  • \$\begingroup\$ You could maybe only use one space wide corridors, as the second space does not add any information and thus you do not really get a true 5x5 section of the maze. Just a thought, though. \$\endgroup\$ Sep 25, 2017 at 11:50
  • \$\begingroup\$ @JonathanFrech No, that's a good point. I went with double-wide corridors since it looks more even with the character height, but looks aren't important when doing this challenge. I'll update the sizing. \$\endgroup\$ Sep 25, 2017 at 15:54
  • \$\begingroup\$ Are this maze's dimensions not 51x51? \$\endgroup\$ Sep 25, 2017 at 16:29
  • \$\begingroup\$ @JonathanFrech Apparently, with that generator, a size 50 doesn't yield a size 50. I'll either find a different generator or make my own for the actual challenge. Thanks! \$\endgroup\$ Sep 25, 2017 at 17:28
  • \$\begingroup\$ I think the problem does not lie in the generator; it lies in the maze's nature. If your corridors are always one character wide and you have walls on the far left and far right, your maze size has to be odd. \$\endgroup\$ Sep 25, 2017 at 19:13
  • \$\begingroup\$ Does this allow for "relative" vision? As in, after we get the initial block we would request "The next block to the right" instead of "the block at (2,7)"? \$\endgroup\$ Sep 26, 2017 at 20:22
  • \$\begingroup\$ @KamilDrakari Sure, that would be allowed. It's dependent upon how that half of your submission works. \$\endgroup\$ Sep 26, 2017 at 20:32
  • \$\begingroup\$ @JonathanFrech Good point. Maybe I'll compromise and make it a 51x51 maze. Thanks for the insight. \$\endgroup\$ Sep 26, 2017 at 20:32
3
\$\begingroup\$

Type the alphabet as fast as you can

Your task is to make a program that measures how fast you can type the letters of the English alphabet.

  • The program shall only accept lowercase letters a to z in alphabetical order.
  • Each letter is echoed as typed on the same line (without new line or any other separators between letters).
  • If you type an invalid character the program shall output Fail and exit.
  • If you type all 26 letters the program shall output the time in milliseconds it took from the first to the last letter and exit.
  • The timer starts when you type the first letter, a.

Example outputs:

b
Fail

abcdefgg
Fail

abcdefghijklmnopqrstuvwxyz
6440

This is , so shortest answer in bytes wins.

\$\endgroup\$
3
  • \$\begingroup\$ Related. I would also recommend to put "time" in some way into the title. \$\endgroup\$
    – Laikoni
    Oct 27, 2017 at 13:49
  • \$\begingroup\$ Thanks @Laikoni \$\endgroup\$ Oct 27, 2017 at 14:53
  • \$\begingroup\$ Does the output have to be strictly in milliseconds, or at least in milliseconds, e.g. nanoseconds. Many builtin timing functions are in ns these days. \$\endgroup\$
    – nimi
    Oct 27, 2017 at 16:39
3
\$\begingroup\$

Stable modular exponents

It is well-known that the final three digits of Graham's number are 387. This is because Graham's number is a ridiculously tall exponent tower of threes: 3^(3^(3^...))), and it can be shown that any such tower of height at least 5 has 387 as its final three digits.

This generalises: given any base n and any starting number a, the exponent tower a^(a^(a^...))) will eventually stabilize modulo n. After that point, whatever you put in the topmost exponent, be it just a last a, or a continuation of the exponent tower (i.e. more than one a), or any other number, its congruency class modulo n will not change. That is the challenge that I set before you here today.

Problem statement

Write a program or a function that takes two numbers a and n (within your language's standard signed or unsigned integer range) as input, and outputs the limit l of the sequence a%n, (a^a)%n, (a^(a^a))%n,..., which can be mathematically proven to be eventually constant (and therefore have a well-defined limit).

Your program should be able to handle a > n (note that a and a+n doesn't necessarily give the same result), and we require that 0 <= l < n.

Warning: Reducing the exponents mudulo n, i.e. calculating this sequence recursively using b[0] = a%n, b[i] = (a^b[i-1])%n will yield the wrong result, and might not stabilize.

Test cases

If we call the function f(a, n), it should give the following:

> f(3, 1000)
387
> f(6, 10)
6
> f(5, 9)
2
> f(14, 9)
4
> f(3, 81)
0

Scoring criteria

Standard code golf rules, use as few bytes as possible.

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

Voronoi Iteration

Given a finite set of points in the plane, output the set vertices of the corresponding Voronoi diagram.

Details

A vertex of the voronoi diagram is a point of the plane that has the same distance to the three or more closest input points. As usual, you don't have to worry about the rounding issues of limited precision floating point numbers.

Examples

[(0,0),(2,0),(0,2),(2,2)] -> [(1,1)]
[(0,0),(1,0)] -> []
[(0,0),(2,0),(0,2)] -> [(1,1)]

Inspired by this question on MO.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I suggest having a test case with floating point coordinates. \$\endgroup\$
    – DELETE_ME
    Jan 22, 2018 at 14:10
  • \$\begingroup\$ (although I already understood the test cases) it would be helpful to have an image. \$\endgroup\$
    – DELETE_ME
    Jan 22, 2018 at 14:16
  • \$\begingroup\$ @user202729 It definitely needs more examples, but you can obviously interpret these coordinates as floating points as well. \$\endgroup\$
    – flawr
    Jan 22, 2018 at 14:17
  • \$\begingroup\$ Having a test case with floating point coordinates will help testing if programs handle floating point input correctly. \$\endgroup\$
    – DELETE_ME
    Jan 28, 2018 at 7:32
3
\$\begingroup\$

Invisible target - probability KotH

?


In short

Walls are gradually added and the player nearest to the stationary invisible target at the end of the game wins.


Detail

Players are all present on a 32 by 32 grid of square cells, which wraps toroidally. One randomly chosen cell is the target, which is not indicated to any of the players (regardless of whether they are on that cell or not). The target does not move.

Players all take their turn simultaneously. After each turn there is a small chance of a wall being added.

Wall rules

  • The wall will never be placed on a player.
  • The wall will never be placed in a cell that does not have a route to the target.
  • Of the possible positions for the wall to be placed, one will be chosen uniformly pseudorandomly.
  • The probability of a wall being placed each turn is 1/7.
  • The wall will be placed such that every player still has a route to the target (this includes never placing a wall on the target).

Note that a player having a route to the target means that there exists a path that does not include a wall. If another player blocks the path it still counts as a path.

Movement rules

  • A player can move to any of the 4 orthogonally adjacent cells (or stay still).
  • A player cannot share a cell with another player.
  • A player cannot move onto a wall.
  • A player can move onto the target, but will have no way of knowing that this has happened.

Starting position

At the start of the game the arena will have no walls and the players will be randomly positioned with the guarantee that there are no other players within each player's 5 by 5 neighbourhood.

Winning

Play will continue until no wall can be placed for 10 consecutive attempts (note that attempts only occur with probability 1/7 each turn so this will take more than 10 turns). When play stops the player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many, and in most cases there will be a player on the target cell, meaning only a single winner.

Each of the (one or several) joint winners scores one point. Games will be played until one player is the clear winner, or until it is clear there should be joint winners overall.


Input and output

Input

During an N player game the input will be a space separated string of N+1 integers received on STDIN:

  • The player's position (an integer).
  • The position of any wall added since the player's last turn (an integer).
  • The position of every enemy player (N-1 integers).

Positions will be single integers from 0 to 1023, representing the distance in English reading order from the top left cell.

For a 4 by 4 arena this would give the following numbering:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

If no wall was added the wall location will be 1024.

During a particular game the order of enemy players will be consistent - the nth location will always refer to the same enemy player.

Output

The player must send an integer from 0 to 4 to STDOUT representing a move in English reading order:

  0
1 2 3
  4

(2 being no move).

A move to an unoccupied cell will not necessarily succeed - it will fail if another player is also trying to move to the same cell.

A move to an occupied cell will not necessarily fail - it will succeed if that player is also moving away from that cell (provided that player succeeds in moving away from that cell, and no other player is also trying to move to that cell).

This means two players can swap cells if they both decide to on the same turn.

A player taking longer than 50 milliseconds to respond will not move.


Sandbox questions

  • If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

  • Should this be tagged ? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

  • I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

  • Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own current cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own current cell instead. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

  • Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?

  • Alternative adversarial 2 player version: One player is the target, and the other player is seeking the target. Each player can move one square orthogonally or stay still. Walls are added as in the multiplayer game, and the game ends when the seeker moves onto the target's cell. The score of each player is the number of moves the game lasted. Lower score is better for the seeker player, higher score is better for the target player. The target can always see the location of the seeker. The seeker can never see the location of the target. Might also be interesting to allow both players to choose where to place a wall on their turn (in addition to moving). This might open up the possibility of double bluff. Walls would still be prevented from being placed on a cell that doesn't leave a path from seeker to target. Would this be more/less interesting than the multiplayer version? Are they sufficiently distinct to post as separate challenges, or should one be chosen as the one to be posted? Would this adversarial version work best as two KotHs that use each other's answers to judge their own answers (like a cops and robbers challenge) or should all the seeker answers and target answers be posted to one challenge? Alternatively each answer could be required to deal with being either a seeker or a target, but I like the idea of people being able to specialise and build just one or other, without being obliged to write both.

\$\endgroup\$
15
  • \$\begingroup\$ I believe the best strategy is to take all of the connected squares, and find the one that has the shortest walking distance to all other squares. Also, I think that walls should be placed every turn, as it appears to only slow down the game. \$\endgroup\$ Jun 20, 2015 at 0:18
  • \$\begingroup\$ Also, I believe an interesting variant would be to have it more like the cats/mice KotH, where several mice compete to stand on the square first, and the cat tries to delay them as long as possible. \$\endgroup\$ Jun 20, 2015 at 0:21
  • \$\begingroup\$ @NathanMerrill thanks for the feedback. When you say walls should be placed every turn, do you mean each time any player moves, or each time all N players have moved? \$\endgroup\$
    – trichoplax
    Jun 20, 2015 at 0:23
  • \$\begingroup\$ Each time all N players have moved, although I wouldn't be against the other either. \$\endgroup\$ Jun 20, 2015 at 0:24
  • \$\begingroup\$ Would the variant involve a cat that knows the position of the target? \$\endgroup\$
    – trichoplax
    Jun 20, 2015 at 0:24
  • \$\begingroup\$ Yes, it would (wouldn't be interesting otherwise, I think) \$\endgroup\$ Jun 20, 2015 at 0:25
  • \$\begingroup\$ @NathanMerrill my problem with adding the wall at the same point each time, after N players have moved, is that this means the players at the start of the cycle get first choice about where to move, which becomes more relevant in the later stages of the game. \$\endgroup\$
    – trichoplax
    Jun 20, 2015 at 0:26
  • 1
    \$\begingroup\$ Then I would add a wall after N+1 players have taken a turn, or rotate the player's turns \$\endgroup\$ Jun 20, 2015 at 0:26
  • \$\begingroup\$ That's an interesting idea - I'll consider changing it to that (N + 1 turns between walls) \$\endgroup\$
    – trichoplax
    Jun 20, 2015 at 0:27
  • \$\begingroup\$ I'm not against several moves per player between walls though. I've chosen the arena small enough to allow a large number of moves in total, and the cell a player wishes to be on may be several cells away from the current cell, so I don't feel a strong need to add walls at high frequency. \$\endgroup\$
    – trichoplax
    Jun 20, 2015 at 0:30
  • \$\begingroup\$ Moving to the center of the arena may well be worse than a uniformly random strategy ;) There's definitely one better than random though. \$\endgroup\$
    – feersum
    Jun 20, 2015 at 10:01
  • \$\begingroup\$ Question: will player bots have information storage? That is, will a player be able to remember every wall that has been placed? \$\endgroup\$ Jul 29, 2017 at 1:30
  • \$\begingroup\$ @Draco18s yes the players will persist between moves, and can store information. I may place an upper limit on the amount of storage, but if I do it will be very generous. \$\endgroup\$
    – trichoplax
    Jul 29, 2017 at 1:36
  • \$\begingroup\$ In which case, moving randomly is not the best strategy :) \$\endgroup\$ Jul 29, 2017 at 1:38
  • \$\begingroup\$ No, I'm thinking not, especially as a player can track what all of the other players are doing (they are distinguishable from each other, not just generic "enemy", but "player 1", "player 2", ...) \$\endgroup\$
    – trichoplax
    Jul 29, 2017 at 1:39
3
\$\begingroup\$

Number rewinder

Inspired by this SO question and little bit expanded.

Your task is to rotate left a given integer by one digit in a given base and return integer (move the MSD to the LSD position).

Input: Two integers Number > Base > 1
Output: Result

Test cases:

Number Base  Result  String representations
61453   10    14536  61453 -> 14536
61453   16      223  F00D -> DF (00DF)
61453    8   229481  170015 -> 700151
60429   16    49374  EC0D -> C0DE
62977   16    24607  F601 -> 601F

This is Code-golf, standard loopholes are forbidden and shortest answer wins.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ I don't think your restriction about strings is going to work out well, there's not really a way to verify strings aren't being used. In any case, string rotation isn't that much different from the arithmetic required to do this operation. Personally, I'd recommend just allowing them. Thanks for using the sandbox! \$\endgroup\$ Feb 5, 2018 at 22:09
  • \$\begingroup\$ (i.e., we don't like do X without Y or unobservable behavior) \$\endgroup\$
    – DELETE_ME
    Feb 6, 2018 at 5:45
  • \$\begingroup\$ @FryAmTheEggman If there isn't some ToString-like function that opperates on any base using strings may be more difficult than dealing with it numerically. \$\endgroup\$
    – Crowley
    Feb 6, 2018 at 8:12
  • 3
    \$\begingroup\$ I've never heard "rewind" used with this meaning before. I would call that operation "rotation left". \$\endgroup\$ Feb 6, 2018 at 11:09
  • \$\begingroup\$ @PeterTaylor Thanks for suggestion. I've updated bounds for the inputs to avoid rotating 1 digit "number" \$\endgroup\$
    – Crowley
    Feb 6, 2018 at 16:04
3
\$\begingroup\$

The Programming Language Quiz, Mark II - Cops

\$\endgroup\$
8
  • \$\begingroup\$ I would say posting the challenge separately for cops and for robbers with cross-referencing links will be better, because posting robbers' answers to the cops' thread is a bit obfuscating I think, and it seems to be the general method to post a C&R. \$\endgroup\$ Dec 14, 2017 at 0:56
  • 5
    \$\begingroup\$ For the languages on Try it Online!, what's to stop me from trying to run a cops submission on every language there? Doesn't that put all those languages at a disadvantage? \$\endgroup\$
    – KSmarts
    Dec 14, 2017 at 18:46
  • 1
    \$\begingroup\$ Same concern as @KSmarts. With the C&R challenges where it is instead the code is hidden it's hard to crack answers because there are a large amount of possible programs they could have written (naively) but there are a relatively small number of languages so people could just try them all. I feel like there could be some added rules to get around this but I don't know what they'd be \$\endgroup\$
    – dylnan
    Dec 15, 2017 at 1:17
  • \$\begingroup\$ So basically it is possible but impractical to try all of the languages on TIO. \$\endgroup\$
    – DELETE_ME
    Dec 15, 2017 at 11:21
  • \$\begingroup\$ @KSmarts Good point. As DLosc pointed out, changing the time restriction to, say, 5 minutes would most likely handle it. \$\endgroup\$ Dec 15, 2017 at 15:20
  • \$\begingroup\$ @DLosc 1) Unary output seems perfectly acceptable, I'll edit it in. 2) I think allowing arbitrary starting and ending delimiters is a good idea 3) non-standard flags are flags that aren't required to run the program. Although, in hindsight, a better idea would be to allow flags but the answer has to state which flags are used. 4) Thanks for pointing that out, editing now. \$\endgroup\$ Dec 15, 2017 at 15:27
  • \$\begingroup\$ @DLosc Edited in \$\endgroup\$ Dec 15, 2017 at 22:53
  • \$\begingroup\$ The character limit for PPCG answers has been bumped to 65,536. Also, not that printable ASCII excludes newlines. \$\endgroup\$
    – Dennis
    Dec 16, 2017 at 4:33
3
\$\begingroup\$

How acceptable is it to base challenges off of pre-existing challenges? I saw the challenge for Your Own Pet Ascii Snake and had a thought about making the output look more 'snakelike' by printing the characters |,\,/,(,),_ instead of always using the + character.

Here's how it would work. You would get some positive, negative, and 0 numbers as input, and based on those numbers, the snake moves one row down and that many characters in that direction. So, for a snake like the ones in the previous problem, your array would be restricted to the numbers 0, 1, and -1.

Here are the rules to draw the snake, the characters you print are dependent on the spacing of the lines before and after it.

So, say your snake is at position n (in the previous problem, n=30 to start, in this one you need to figure out a number for n that will keep your entire snake on the screen),

if the input is 0 you print n-1 spaces and a |
if the input is +1 you print n spaces and a \
if the input is +2 you print n spaces and \_, +10 would be \_________ (9 _ and a backslash)
if the input is -1 you print n-2 spaces and /
if the input is -2 you print n-3 spaces and _/, -10 would be _________/

Here's an example snake based on this array [+4, -3, +1, -4, +2, -3, +2, +5, -4, -1, -2, 0, +4, -4]

                        |
                         \___
                          __/
                          \
                       ___/
                       \_
                      __/
                      \_
                        \____
                        ____/
                       /
                     _/
                    |
                     \___
                     ___/

I could also add optional 'curvy' rules that would include the '(' and ')' characters on direction changes to produce a snake like this, based on the same array above:

                         |
                         \___
                          ___)
                         (_
                       ____)
                      (__
                      ___)
                     (__
                        \____
                        _____)
                       /
                     _/
                    (
                     \___
                     ____)

note that for the curvy snake, 0s are handled differently depending on if there is a direction change in the rows above and below them, here there is a negative, 0, positive pattern, so we use a '(', if there were no direction change we'd use a |, and in the opposite pattern, a ')'

There are spaces to the left of my example snake because I didn't want to count out how many spaces I should leave exactly, I don't know whether it should be mandatory to cut out extra whitespace to the left, or whether to let people have as much or as little whitespace as they want, provided that their snake doesn't 'go off screen'

\$\endgroup\$
2
  • \$\begingroup\$ I don't think there's a problem determining the next line randomly. For example, my program could generate the numbers for all 30 lines and then go back and format the characters appropriately. However, I'm not sure that's different enough to warrant its own challenge. Your second idea, though, regarding taking +1/-1/0 as input, that has some merit as it's pretty radically different than the existing snake challenge. \$\endgroup\$ Feb 23, 2018 at 19:29
  • \$\begingroup\$ I'm far, far too tired for you to rely on my opinion alone but this looks sufficiently different enough from the 2 existing challenges to not be a dupe, once it's fleshed out a bit more. I'd suggest waiting a while before posting it, though, as people do get jaded of a barrage of similarly themed challenges. \$\endgroup\$
    – Shaggy
    Feb 24, 2018 at 21:26
1
13 14
15
16 17
131

You must log in to answer this question.

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