480
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

2872 Answers 2872

1
17 18
19
20 21
96
2
\$\begingroup\$

Write a brute-forcer for the 3-byte input 'emoticon numbers' challenge

The Emoticon numbers! challenge asks you to identify the 3-byte snippet which evaluates to the highest numeric value in your language, and which also has the bytes in the form ABA (where the outer two are identical and the middle one is different), and which generates an output that is only digits.

I trust your claim that you have identified the best possible one is honestly intended, but as a casual scripter I'm not totally convinced, and can't be reassured by unfamiliar language specification references - since there are only 256^2 possible values, can you convince me with brute force instead?

Write a program or function which:

  1. takes no input
  2. generates all the possible 3-byte sequences matching the pattern ABA and evaluates them in the same language. (No using one language to generate the best pattern for a different language).
  3. Processes all the ones which evaluate to digits-only (output text matches the regex ^[0-9]+$, with or without trailing newline).
  4. Outputs just the ABA sequence which evaluated to the highest value, and an optional trailing newline. No errors or stderr output from failed evaluations.

Clarifications:

  • There's no limit on runtime, but your program must at least plausibly finish if run for long enough. Particularly, if evaluating one of the byte sequences would get stuck prompting for keyboard input, or go into an infinite loop, or quit the interpreter, you must avoid or handle that.
  • If you are able to usefully reduce the search space (and explain why it's valid for your language) to avoid searching 256^2 options, that's OK. Especially if you need to do so to get past an infinite loop, etc.

Show off your brute-force strength by forcing your brute-forcer into the smallest possible space. Fewest bytes wins.

Tag:

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ The whole challenge seems really brute-force :)) \$\endgroup\$ – Mr. Xcoder Jun 9 '17 at 17:17
  • 1
    \$\begingroup\$ I actually did that to prove that 9E9 is the optimal JS solution. \$\endgroup\$ – programmer5000 Jun 9 '17 at 17:33
  • \$\begingroup\$ -100 points if your brute forcer fits ABA :D \$\endgroup\$ – CalculatorFeline Jun 9 '17 at 18:47
  • \$\begingroup\$ Now I'm wondering if there are languages for which some program of the form ABA neither halts nor obviously doesn't halt. It's likely too short, but who knows. \$\endgroup\$ – user62131 Jun 10 '17 at 3:55
  • \$\begingroup\$ [With no downvotes or critique it's not too badly formed, but with only +1 upvotes it's not popular either so I am not going to post it] \$\endgroup\$ – TessellatingHeckler Jun 28 '17 at 0:31
2
\$\begingroup\$

Inspired by lifecompetes.com

Multiplayer Game of Life (GOL)

There are n players that play the Game of Life (standard rules) on an 50 x 50 grid. (Size, border conditions? Toroidal, Absorbing, Mirroring?)

Before first GOL-Step

When the game starts, each player has 12 cells that he can place anywhere he want as long as they do not overlap. Before the first GOL-step occures every player has to place 6 cells. If two players place their cell on the same spot no cell wil be placed an thei cells will remain in each players bank.

During game

In each GOL-Step, each player can place as many new cell on the grid as he has in his bank. If two or more players want to place a cell on the same spot, no cell will be placed there (the cells will remain in each players bank). Every six GOL-steps all the players who have less that 12 cells in their bank will get a new cell in their bank.

Goal

The goal is achieving the maximum number of cells on the grid during 1000 GOL-steps.

How to participate

Each participant has to write a javascript function of the following form (multiple return statements allowed.)

function my_bots_name(field, bank, golstep){
  /* your code */
  return p;
}

Where p is a 2d array of points [[x1,y1],[x2,y2],[x3,y3],...] that the player wants to set. field contains a 2d array of the GOL grid, bank indicates the number of cells in the player's bank, and golstep is the index of the current GOL step (golstep == 0 before the first GOL-step occurs). The function may not the global variables and cannot access Math.random() or Date(). In field the empty cells will be set to 0, the own cells will be set to 2 and the other player's cells will be set to 1. (You will not be able to distinguish between various other players.)

The winner will be determined with a game that contains all valid submissions after one week after the first submission.

TODO

The exact environment will be provided so everyone can test the own function before the official runs.

  • What size of the grid is appropriate? (dependent on number of players?)
  • How many steps should be computed?
  • What border conditions should be chosen?
  • Is the restriction of Math.random() and Date() apropriate? (The idea was that the games will be the same no matter of who/when they will be run. (Deterministic) )
| |
\$\endgroup\$
  • \$\begingroup\$ relevant. also relevant. \$\endgroup\$ – Martin Ender Aug 6 '14 at 12:20
  • \$\begingroup\$ It looks like it was abandoned, since the user has not been here for more than a month. I was not able to read everything yet - is there something important that should be considered or is it a challenge that shouln't even be started? \$\endgroup\$ – flawr Aug 6 '14 at 13:03
  • \$\begingroup\$ I just thought you might want to have a look to get some inspiration from a previous spec. \$\endgroup\$ – Martin Ender Aug 6 '14 at 13:09
  • \$\begingroup\$ Ok thank you, I wil read them later. \$\endgroup\$ – flawr Aug 6 '14 at 13:21
  • \$\begingroup\$ What do you mean by "standard rules"? The standard rules for Life have binary cells, and this doesn't. \$\endgroup\$ – Peter Taylor Aug 7 '14 at 22:07
  • \$\begingroup\$ Well each cell of the grid can have two states: occupied by a live cell or not. For executing a GOL-Step it does not matter which cell is of which player, they are all treated the same. (As it is in lifecompetes.com) \$\endgroup\$ – flawr Aug 7 '14 at 22:15
  • \$\begingroup\$ What happens to an empty cell that has 3 neighbours of different players? Are new cells only born if they have 3 neighbours of the same player? \$\endgroup\$ – trichoplax Aug 10 '14 at 20:23
  • \$\begingroup\$ Thank you for pointing this out, I did never think about this special case but I just checked livecompetes and they handle this as follows: A new cell is born if two or three of the neighbours are from the same player. If there are three different players invovled the space remains empty. \$\endgroup\$ – flawr Aug 10 '14 at 20:40
  • \$\begingroup\$ why n players instead of 2 players? \$\endgroup\$ – Sparr Aug 18 '14 at 4:31
  • 1
    \$\begingroup\$ Can you provide some thoughts why only two players would make a better game? If you could start it with n players at once you can let all submissions compete against each other as you do in the original lifecompetes.com \$\endgroup\$ – flawr Aug 18 '14 at 8:11
  • \$\begingroup\$ @programmer5000 Yes, feel free to adopt! Just make sure work out the details in the sandbox before posting. If you want me to help in one way or another, just ping me! \$\endgroup\$ – flawr Jun 9 '17 at 17:43
  • \$\begingroup\$ Can you add support for other languages? \$\endgroup\$ – CalculatorFeline Jun 9 '17 at 18:46
  • \$\begingroup\$ @programmer5000 I thought you wanted to adopt it?!? \$\endgroup\$ – flawr Jun 9 '17 at 19:32
  • \$\begingroup\$ Please next time say that you want to list it for adoption rather than adopting it yourself! \$\endgroup\$ – flawr Jun 9 '17 at 19:39
2
\$\begingroup\$

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

Edit: I'll have to clarify the optional features and there may be more. Essential I want to have the basic features covered, and if anything beyond gets implemented because it saves characters that is okay, but not required.

Edit: Updated but still working on it. Will definitely include edge cases and more examples as test cases.

Edit: It might be cool to have this implemented as a function, and then have some follow up questions where you are allowed to call the function created here while only counting the function call as characters, and not the contents.

Still working on the specifics, but getting it the idea out there.


2-Dimensional Regex

Given a 2-Dimensional regex and a block of text, do a match, a single search and replace or a global search and replace depending on the input.

Implement this as a function. The input should be two arguments to the function. The first is the regex, and the second argument is the string to match. The output should be a truthy or falsey value when doing a match, or the string when doing a search and replace.


Match

Input:

/aaa/
/bbb/
/ccc/

and

aaaab
dbbba
ecccc

Output:

A truthy value

Single Search and Replace

Replace the first instance of the match. The search order is the match that includes the top most character. If multiple matches end up with the top-most character on the same line, then include the left-most match.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaabba
bccaabba
bbbaaaaa

Global Search and Replace

Replace all occurrences of the match. Matches do not overlap, and you use the same search order as the single search and replace.

Input:

s/bb/cc/
 /bb/cc/

and

abbaabba
bbbaabba
bbbaaaaa

Output:

accaacca
bccaacca
bbbaaaaa

Another example:

Input:

s/aba/bbb/
 /aba/aba/
 /aba/bbb/g

and

aaaabaaaa
  aabaababa
aababaababa
aabaaabbaba
 aba

Output:

aaabbbaaa
  aabaabbbb
aabbbbababa
aabaaabbbbb
 aba

Rules

  • Only ASCII characters 32 through 126 are valid.
  • Character classes are valid, [a-c4-6] would match an a,b, c, 4, 5, or 6. And [b?7] matches one b, one ?, or one 7.
  • . matches any character.
  • Use \ to escape there special characters to match their literal character instead of their special meaning: {}[]/\.?*.
  • a? matches 0 or 1 a's.
  • b+ matches 1 or more b's.
  • c* matches 0 or more c's.
  • b{2} matches 2 b's. Ranges such as {2,5} to match 2 to 5 b's is optional.
  • g flag replaces all of the occurrences, without it only the first occurrence would be replaced. This flag is optional.

Optional features:

  • Capture groups are optional. Please specify whether to use () or \(\) to match literal parenthesis.
  • Grouping such as (ab)+ matching all of abababab.
| |
\$\endgroup\$
  • \$\begingroup\$ Sounds interesting, but apart from the character-class and . addition it's very similar to codegolf.stackexchange.com/questions/37867/programmers-garden. Some specifics you should clarify (I know you're still working on it, but before I forget it...): Is the regex always rectangular? Are regex and replacement equal in shape? And make sure to specify that matches found with g never overlap. \$\endgroup\$ – Martin Ender Sep 17 '14 at 17:04
  • \$\begingroup\$ First occurrence with which search order? What about all the other things which make up a regex (in particular, full alternation and repetition)? \$\endgroup\$ – Peter Taylor Sep 17 '14 at 17:13
  • \$\begingroup\$ @MartinBüttner I got the inspiration for it while working on the garden one since 2-D regexes would help a lot with that problem! I think it would be cool to implement a lot of regex features and that would be a different problem. /i for case insensitive, maybe even capture groups. The replacement could be a different size than the match (I'll have to define how that affects making a previous match now invalid while using /g). \$\endgroup\$ – hmatt1 Sep 17 '14 at 17:58
  • \$\begingroup\$ @PeterTaylor I'd love to define and add other regex features, but I don't want to make the challenge too hard. I'll think about how to implement repetition and non-rectangular searches. Definitely interested in hearing ideas about making this interesting and feasible! \$\endgroup\$ – hmatt1 Sep 17 '14 at 18:00
  • \$\begingroup\$ As far as overlapping matches goes, it might be okay to have that in the input, but then have the one that would get replaced would be the first in whatever search order we end up choosing. \$\endgroup\$ – hmatt1 Sep 17 '14 at 18:02
  • \$\begingroup\$ If the only regex features you have are a small subset of character classes, it's potentially misleading to call it a regex problem at all. It might be less confusing to talk about 2D pattern matching instead. \$\endgroup\$ – Peter Taylor Sep 17 '14 at 21:11
  • \$\begingroup\$ @PeterTaylor I'm planning on adding more regex features. Good point though! Thanks! \$\endgroup\$ – hmatt1 Sep 17 '14 at 21:16
  • \$\begingroup\$ Having implemented a large part of the ECMAScript regex flavour before, let me tell you that a) getting the spec right and b) implementing regular expressions is a lot of work. Starting with your spec: is repetition greedy? You've got character classes with ranges - what about invalid ranges? What about - at the beginning or end of the string? What about character class negation? What about []? Likewise, what about invalid {m,n} quantifiers? Also, I'd definitely leave out grouping and capturing - that complicates things significantly. \$\endgroup\$ – Martin Ender Sep 24 '14 at 22:17
  • \$\begingroup\$ Added to that are the difficulties from the fact that your regex is 2D. How do I specify that the stuff in two lines is repeated the same amount of times? E.g. if I want to match an n x 2 block of as, I couldn't just write a+ in two lines, right? Because the +s are technically independent. What if there's a + in one line and no + in another? etc... \$\endgroup\$ – Martin Ender Sep 24 '14 at 22:19
  • \$\begingroup\$ @programmer5000 you are welcome to adopt this! \$\endgroup\$ – hmatt1 Jun 9 '17 at 19:36
  • \$\begingroup\$ The second and third examples are the same. \$\endgroup\$ – CalculatorFeline Jun 11 '17 at 4:38
2
\$\begingroup\$

stdin FPS

Count the input FPS ("F"s per second)

Task:

Read a potentially infinite text stream. While you do, display (at least once per second) your FPS, i.e. the amount the characters "f" or "F" appeared.

The FPS has to be accumulated over a time frame of five seconds, meaning you can't just print the number of Fs you've seen this second every second.

Rules:

  • Standard loopholes are banned
  • Read one character (or byte) at a time. If (and only if) your language doesn't have the ability to read characters as they appear in the input, you may read the input one line at a time.
  • The FPS display may be in any reasonable format, for example 3.54fps or 0.9224
  • You may round the resulting numbers to 2 (or more) digits after the decimal point, but no less. Displaying only integers is not allowed.
  • To display a new value, you may either:
    • clear the screen before printing a new value,
    • overwrite the existing value,
    • or seperate the values by newline characters
  • Be case-insensitive
  • In the first second, you don't have to display anything, and if you do, your value doesn't have to be accurate or meaningful.
  • Before five seconds have elapsed, you have to average over the total elapsed time since execution started.

Sandbox questions:

  • Dupes? (I don't know what to search for)
| |
\$\endgroup\$
  • \$\begingroup\$ "In the first second, you don't have to display anything" and "The FPS has to be accumulated over a time frame of at least 5 seconds" are kind of conflicting. As I understand, we don't have to display anything in the first five seconds... \$\endgroup\$ – Mr. Xcoder Jun 11 '17 at 11:57
  • \$\begingroup\$ @Mr.Xcoder I will clarify. What I mean is that in the first second you don't have to display anything, after the first second the amount of Fs in the first second, after the second second the average amount of Fs in the last two seconds and so on, until you reach the fifth second, after which you may choose to average only over the last five seconds. \$\endgroup\$ – L3viathan Jun 11 '17 at 11:58
  • \$\begingroup\$ Also, before posting, I advice you to clarify "potentially infinite text stream"... the community will react if you do not specify how the input is specifically taken \$\endgroup\$ – Mr. Xcoder Jun 11 '17 at 12:01
  • \$\begingroup\$ @Mr.Xcoder Clarified (and changed) the five seconds rule. What do you suggest regarding the "potentially infinite text stream"? Adding exceptions for memory limits, etc.? Or clarifying again that output has to occur "live"? \$\endgroup\$ – L3viathan Jun 11 '17 at 12:06
  • \$\begingroup\$ Add both the specs, and wait to see if there are any other suggestion here \$\endgroup\$ – Mr. Xcoder Jun 11 '17 at 12:15
2
\$\begingroup\$

Implement Nopfunge

Background

Nopfunge is a very simple Befunge derivative, with no stack and no real form of data storage; all it has is an instruction pointer and five commands ("turn north", "turn south", "turn east", "turn west", "continue in same direction"). However, what it does have is a program that repeats forever in two dimensions, which turns out to be enough to make it Turing complete.

The task

Your program must take, as input, four 2D arrays of characters, a, b, c, and d, via any reasonable means. Each of these will have the same dimensions, and they will be rectangular (although not necessarily square). (Note: This is a simplification from the actual syntax of Nopfunge, but is still just as Turing-complete.)

The program will then conceptually work on an infinite array formed out of sub-arrays identical to the inputs, formed by placing a in the top left corner, b along the top edge, c along the left edge, and d everywhere else, like this:

abbbbbbb …
cddddddd …
cddddddd …
cddddddd …

⫶⫶⫶⫶⫶⫶⫶

(Note that because you can't assume your language can do infinite work in finite time, you won't be able to actually represent the compressed array in memory, so you won't be able to calculate the value at a particular coordinate pair in advance; rather, you'll have to calculate it lazily and/or every time it's needed.)

Then simulate the progress of a Nopfunge program on this array. Specifically, there's an instruction pointer that has a position on the array, and a direction; it starts at the top-left corner, going to the right. Repeatedly, run the command specified by the character at the instruction pointer:

  • >: Move the instruction pointer one position to the right; it now points right
  • <: Move the instruction pointer one position to the left; it now points left
  • ^: Move the instruction pointer one position upwards; it now points up
  • v: Move the instruction pointer one position downwards; it now points down
  • (space): Move the instruction pointer one position in its current direction

Should the instruction pointer ever attempt to move outside its infinite array (by moving above the top edge or to the left of the left edge), your program should exit. If the instruction pointer never attempts to move outside its infinite array, the program should never exit. (Or in other words, the task is to halt if and only if the Nopfunge program does.)

Clarifications

  • You can input the arrays as arrays of character codes (i.e. integers) rather than characters if you wish, but if you do, they must use the ASCII/Unicode encodings, 62 60 94 118 32 for > < ^ v .
  • Your program can do anything if the input arrays aren't all the same size or aren't rectangular.
  • You may take additional inputs for the dimensions (width and height) of the input arrays, if you wish.
  • It doesn't matter what (if anything) your program outputs; all that matters is whether or not it halts.

Victory condition

This is , so shorter programs (in bytes) are considered to have a better score.

Sandbox questions

  • Is the specification easy to understand and unambiguous?

  • Is this the best possible input format? I wanted to avoid the secondary task of having to parse Nopfunge's input format (which uses = and ; to split one array into the four given here), but am not sure whether this format or that one is more convenient for solving the task.

| |
\$\endgroup\$
  • \$\begingroup\$ Note so I don't forget: it was pointed out in chat that test cases will be helpful. \$\endgroup\$ – user62131 Jun 21 '17 at 10:15
2
\$\begingroup\$

Reindent Java/C/C++/etc. code

Write a program that adds or removes whitespace to format code nicely. Rules for what the code should look like when you're done:

  • No line should contain more than one of { and }.
  • A { should always be the last thing on a line.
  • A } should always be the only thing on a line (besides whitespace that comes before it).
  • The amount of whitespace in front of each line should be a fixed multiple of the current nesting count. (You can use any amount of indentation you want, as long as it doesn't change.)
  • No whitespace should be inserted or removed that doesn't contribute to satisfying one of these rules.

The nesting count for the first line is 0. The nesting count of any other line is the nesting count of the previous line, plus one if the previous line contains a {, minus one if the current line contains a }.

{ and } inside string literals and comments don't count in the above rules. A string literal is text enclosed in single or double quotes, where single or double quotes with a backslash before them aren't interpreted as the end of the string literal. A comment is text enclosed in /* and */, or text going from // to the end of the line. /* */ comments can be nested.

For example, it should reformat this:

    main() {printf("Hello!"); // I don't care about the world...
        }

into this:

main() {
    printf("Hello!"); // I don't care about the world...
}

| |
\$\endgroup\$
  • \$\begingroup\$ Strictly interpreted, the current rules don't allow any legal output for input "{}". You probably need to define rules for string literals and comments. I also note that you don't require the indentation to be consistent (different lines can use different multiples of the nesting count), and that inputs with badly indented lines which aren't adjacent to { or } can't be fixed by inserting or removing whitespace adjacent to { or }. \$\endgroup\$ – Peter Taylor Jul 23 '14 at 9:54
  • \$\begingroup\$ @PeterTaylor Fixed those problems. (I think). \$\endgroup\$ – tbodt Jul 23 '14 at 15:49
  • \$\begingroup\$ Fixed some of them. You still need to add exceptions for { or } inside a string literal or comment, including definitions for what constitutes a string literal or comment (since it varies between languages). \$\endgroup\$ – Peter Taylor Jul 24 '14 at 15:06
  • \$\begingroup\$ @PeterTaylor oh, now I understand what you meant. \$\endgroup\$ – tbodt Jul 24 '14 at 15:51
  • \$\begingroup\$ @tbodt I'd like to take over this challenge if you don't plan on posting it \$\endgroup\$ – musicman523 Jun 26 '17 at 23:29
  • \$\begingroup\$ @musicman523 nah I think i'll post it \$\endgroup\$ – tbodt Jun 26 '17 at 23:46
  • \$\begingroup\$ imo the first code snippet is better than the latter \$\endgroup\$ – Okx Jun 27 '17 at 10:01
2
\$\begingroup\$

RoboCops and Robbers

A while ago we made some code to golf brain-flak for us. Eventually the code got so good that us humans could no longer compete against it.

Now the code has turned against it and its your job to stop it. You need to out golf the robots. They've already golfed all the numbers so you need to write some Brain-Flak code that pushes a positive number to the stack, but is shorter than the code produced by these two bots:

  • The Python, This bot eats numbers for breakfast and caches them for lunch, it still is the top scoring bot on the challenge and its coming for you.

  • The Number Cruncher, based on Neil's top scoring Perl answer, made from boiling hot JavaScript and raw HTML this bot takes no prisoners.

Since we need to stop these rampaging robots as soon as possible you need to come up with the smallest number you can to beat them.

Rules

  • You must write a program to push a number to the stack in Brain-Flak.

  • It must be shorter than the code produced by both of the two bots above when asked to produce the same number

  • Your answer must be stack clean (must push the same number regardless of the contents of the stack) and must not use [].

  • Your score will be the number you produce, with a lower score being better.

  • In the event of a tie where two people have the same number the person with the shorter code will win, if that does not resolve then the first earlier will win.

| |
\$\endgroup\$
  • \$\begingroup\$ Why the ban on []? Irresponsible usage is banned by the immediately preceding condition. \$\endgroup\$ – CalculatorFeline Jun 30 '17 at 2:15
  • \$\begingroup\$ @CalculatorFeline The original question the bots came from also banned it. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 30 '17 at 2:16
  • \$\begingroup\$ This seems so obviously a dupe of the question it links that I'm wondering whether I missed something, because I can't think why you'd put in the effort to sandbox it. \$\endgroup\$ – Peter Taylor Jun 30 '17 at 7:18
  • \$\begingroup\$ @PeterTaylor I think you are missing something. The previous question was a meta golf where one writes a program to write Brain-Flak programs. In this challenge you write a single Brain-Flak program. Its basically a CNR where all the cops submissions are generated by bots. Please let me know if there is anything I can do to make it clearer, or if you still think this is a dupe. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 30 '17 at 13:07
  • \$\begingroup\$ Doesn't this lua answer have the best score? \$\endgroup\$ – nmjcman101 Jun 30 '17 at 14:19
  • \$\begingroup\$ @nmjcman101 Oh it does. I hadn't even seen that! I'll fix the question. Thanks. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 30 '17 at 14:20
  • \$\begingroup\$ Also I'm assuming that this would be posted as a single question, not an actual Cops thread and Robbers thread? \$\endgroup\$ – nmjcman101 Jun 30 '17 at 14:21
  • 1
    \$\begingroup\$ @nmjcman101 It would be posted as a single question. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 30 '17 at 14:22
  • \$\begingroup\$ @EinkornEnchanter, but the point of CNR is that the robber's answer does the same thing as the cop's answer. Any answer to this is essentially something which can be combined with the existing answers to the meta-golf to make a better answer to the meta-golf. You could effectively get answers to this question by posting a bounty on the existing one. \$\endgroup\$ – Peter Taylor Jun 30 '17 at 19:56
2
\$\begingroup\$

Deep-dichotomize a list

Given a list, dichotomize it (i.e. split it in half), then dichotomize both resulting sublists, etc., until you reach sublists of length 1.

For example, given [1,2,3,4,5,6,7,8]:

  Dichotomize: [[1,2,3,4],[5,6,7,8]]
  Map dichotomize: [[[1,2],[3,4]],[[5,6],[7,8]]]
  Map map dichotomize: [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[8]]]]
  We end here because we only have singletons

If the list has an odd length, the longest of the two lists should be the second one. For example, [1,2,3,4,5] is dichotomized into [[1,2],[3,4,5]].

The content of the list is irrelevant (you can use whatever you want). You can use any list-like representation of your language, as long as both the Input and the Output use the same representation.

Test cases

Input                          Output
[1]                            [1]
[1,2]                          [[1],[2]]
[1,2,3,4]                      [[[1],[2]],[[3],[4]]]
[1,2,3,4,5,6,7,8,9]            [[[[1],[2]],[[3],[4]]],[[[5],[6]],[[7],[[8],[9]]]]

Scoring

This is , so the shortest answer in bytes wins.

| |
\$\endgroup\$
  • \$\begingroup\$ Does the output have to be a list/array? It seems that you're really building a binary tree, and being more flexible in the output would allow languages like Haskell with strict typing which doesn't allow lists of varying depth to participate. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:19
  • \$\begingroup\$ @PeterTaylor To me, You can use any list-like representation of your language includes nested lists and so trees. Maybe I should be clearer. \$\endgroup\$ – Fatalize Jun 28 '17 at 10:22
  • \$\begingroup\$ I don't think a binary tree is really list-like. \$\endgroup\$ – Peter Taylor Jun 28 '17 at 10:23
  • \$\begingroup\$ Suggested tags: code-golf, array-manipulation, recursion. \$\endgroup\$ – Erik the Outgolfer Jun 28 '17 at 13:25
  • 1
    \$\begingroup\$ Third testcase is a bit off, a ] is missing at the end. \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 12:58
  • \$\begingroup\$ "If the list has an odd length, the longest of the two lists should be the second one" seems like unnecessary fluff to me. \$\endgroup\$ – scatter Jun 30 '17 at 14:42
  • \$\begingroup\$ @Christian Why? \$\endgroup\$ – Fatalize Jun 30 '17 at 14:48
  • \$\begingroup\$ @Christian No it's not, how should I split [1, 2, 3, 4, 5] without that information? \$\endgroup\$ – Erik the Outgolfer Jun 30 '17 at 15:16
  • 1
    \$\begingroup\$ @Fatalize Because you could just as easily say it doesn't matter, whichever your language does by default is fine. \$\endgroup\$ – scatter Jun 30 '17 at 15:52
  • \$\begingroup\$ I also think it would be cleaner to allow odd splits to go whatever way. \$\endgroup\$ – xnor Jul 7 '17 at 5:07
2
\$\begingroup\$

Create a "Neverending" Quine

Your task is to create a program which, when run, outputs its source code repeatedly until stopped. You are allowed to have an extra newline between outputs.
NOTE: All standard loopholes are strictly forbidden. That means cheating quines, etc.


This is , so may the shortest answer win and the best programmer prosper...

| |
\$\endgroup\$
  • \$\begingroup\$ Never mind. Found a duplicate. \$\endgroup\$ – ckjbgames Jun 30 '17 at 23:32
  • \$\begingroup\$ Please delete this proposal then and edit it down to a stub. Thanks! \$\endgroup\$ – HyperNeutrino Jul 25 '17 at 0:26
2
\$\begingroup\$

It halts. But why?

Cops/Robbers section

The robbers/cops section can be found here.


Challenge

Cops

Your job is to write a program that always halts. It can do anything it likes, as long as, given any input, it eventually stops. You must also write a mathematical proof that it stops. Two weeks after you have posted your answer (since math is hard, we want to give the Robbers a chance to steal your academic success), you should edit in this mathematical proof. Once you have done so, you are safe, and your score will be the length of your program (in bytes). Whichever safe program has the lowest score wins!

Robbers

Your job is to write a mathematical proof that a given cops program halts, and post it as an answer. You must do so before the cop posts their proof.

You get 1 point for each post cracked, unless you crack it within 24 hours, in which case it is only 0.1 points (this is to prevent people from racking up points on easy answers). You obviously cannot crack your own submissions.

Notes

  1. Cops may not use undocumented or incorrectly documented features of the programming language they are using.
  2. Although the proofs will be written in the informal style common within mathematics (as opposed to completely formal proofs), they must theoretically be valid in the framework of ZFC. This will not come into play for most answers, seeing as most of mathematics can be formalized in ZFC, but some might if they use crazy metamathematical shenanigans (please do not do this (just kidding, go crazy kids)).
    • This means that cops must write programs that can be proven to halt in ZFC. This means, for example the program if isProofThatZFCisInconsistient(input) then infiniteLoop else stop) would be invalid, since although this program always halts (presumably), you cannot prove this fact in ZFC.
  3. Cops, your program is not safe until you post the proof.
| |
\$\endgroup\$
  • 3
    \$\begingroup\$ This seems to be more a knowledge of obscure theorems contest than a programming contest. While the Curry-Howard correspondence says that the two are related, IMO this isn't really on topic. \$\endgroup\$ – Peter Taylor Jul 6 '17 at 13:30
  • \$\begingroup\$ @Peter Taylor well, you would also need to golf the obscure theorems. \$\endgroup\$ – PyRulez Jul 6 '17 at 14:09
  • \$\begingroup\$ ^ and obfuscation could come into play. \$\endgroup\$ – FlipTack Jan 3 '18 at 19:22
2
\$\begingroup\$

ASCII Art Turtle

As you know, the LOGO programming language allows you to manoeuvre a turtle and draw lines in a graphical way. It occurs to me that we can do this for .

A minimal set of commands to produce would be the R(otate right), F(orward) and P(en) commands. For example, the string FPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPFPRRRFRRRRPF would produce the following output:

\|/
- -
/|\

However that AAT code is rather inconvenient so I have chosen the following slightly more compact instruction set:

  • F Move one cell in the current direction. Initially the current direction is east. If the pen is down, the cell just vacated is set to one of -/|\ appropriately.
  • B Move one cell in the reverse direction. (Initially this would be west, of course.) The cell vacated is set in the same way as for F (since the output characters are all symmetric).
  • R Rotate right 45°. Only the current direction changes; nothing is drawn and the current position does not move.
  • L Rotate left 45°. Otherwise as per R.
  • D Lower the pen. Note that the pen starts lowered.
  • U Raise the pen.

The above image could therefore be drawn using the command string BULFDBULFDBULFDBULFDBULFDBULFDBULFDB, while the string LFFUBRFDFFFFFFFFFFFFFFFFFRFFRFBRRFFFFFFFFFFFFFFFFFFFFFUBLLFDFFBLLFFFFFFFFFFFFFFFFFFFFFUBRRFDFRRFFFFFFFFFFFFFFFFFFFFFURBDBBUFLBDBBBBBBBBBLLFFFURBDBBBUFRBDBBBLBB should hopefully produce this somewhat familiar picture:

 /-----------------\ 
/                   \
---------------------
|                   |
---------------------
|                   |
---------------------
\                   /
 \---------|  /----/ 
           | /       
           |/        

Your function or program must take input as a string, or whatever the nearest equivalent is in your language, and output a newline-delimited or newline-terminated string. (For those of you used to using TIO it should be possible to paste the raw string into the ▼ Input field and show the output directly in the ▼ Output field.) Extra blank rows or columns are not allowed, but you are allowed to pad all the lines to the length of the longest non-blank line. You can take input in lower or mixed case if you prefer. You can assume that the input will only use those six letters. You can further assume that U and D commands alternate. You can also assume that you will never write in the same place twice.

This is , so the shortest program that breaks no standard loopholes wins!

| |
\$\endgroup\$
2
\$\begingroup\$

An order of primeness

Introduction

In a recent question the concepts of super-primes were explored. A super-prime is a prime whose index is also a prime.

  • 2 is not a super-prime, its index is 1
  • 3 is a super-prime, its index is 2
  • 5 is a super-prime, its index is 3
  • 7 is not a super-prime, its index is 4
  • ...

The first few of these super-primes are 3, 5, 11, 17, 31, 41, 59, ...

Let us call these primes of at least order 2, because they are more prime than regular primes (which are only of order 1).

Primes of order of 3 or greater can be defined similar. A prime is of order 3 if its index is a prime of order 2.

The first few of the primes at least of order 3 are 5, 11, 31, 41, 59, 127, 179, 277, ...

This is sequence A049076. It was defined by Neil Fernandez in 1999. More information can be found in his Exploring Primeness Project.

Task

Given a prime, return its order.
More formally

  • INPUT: A single integer which is guaranteed to be a prime
  • OUTPUT: A single integer which is the order of the input.
  • You can either return or print the result.

This is , so shortest code wins.

Testcases

           2 ->  1
           3 ->  2
           5 ->  3
           7 ->  1
       52711 ->  9
435748987787 -> 11 (happens to be the 11. Prime of order 11)

Sandbox Questions

  1. Does it need any more clarification?
  2. Should I define order 0 (not a prime) and allow any number as input, or would that over-complicate the challenge?
  3. Primes of higher order tend to get big very fast. Should I somehow specify that a language only has to work for test-cases it can actually handle or is their a consensus already?
  4. Is the introduction too big?
| |
\$\endgroup\$
  • \$\begingroup\$ This is just a loop round the linked question, and as such qualifies as a duplicate for the purposes of this site. \$\endgroup\$ – Peter Taylor Jul 10 '17 at 14:04
  • 1
    \$\begingroup\$ I think this might be an interesting question. \$\endgroup\$ – CalculatorFeline Jul 10 '17 at 22:14
  • \$\begingroup\$ Last test case -> 10 (or all the other cases ->+1) \$\endgroup\$ – J42161217 Jul 10 '17 at 23:24
2
\$\begingroup\$

These are two separate challenges.


Convert to mixed-radix ZYX…432.234…XYZ

Related: Convert from mixed-radix ZYX…432.234…XYZ and Convert to and from the factorial number system.

Given a non-negative real number (no greater than 1×1040 or the biggest your language can comfortably accommodate, whichever is less) convert it to mixed-radix ZYX…432.234…XYZ using the base-36 digits [0-9A-Z] or [0-9a-z] with no leading zeros (except for values smaller than 1). Any reasonable rounding is fine.

Examples

00 (0 × !1)
11 (1 × !1)
210 (1 × !2 + 0 × !1)
311 (1 × !2 + 1 × !1)
420 (2 × !2 + 0 × !1)
421300 (1 × !4 + 3 × !3 + 0 × !2 + 0 ×!1)
1004020 (4 × !4 + 0 × !3 + 2 × !2 + 0 ×!1)
123452304111
42949672958B6570020211
1000000000017A5726651220
184467440737095516157BC43F35350835000211
0.50.1
0.3333333333333333330.02
0.250.112
0.10.0022
5.12521.003
2.7182818284590452351.111111111111111111
0.0013888888888888890.00001


Convert from mixed-radix ZYX…432.234…XYZ

Related: Convert to mixed-radix ZYX…432.234…XYZ and Convert to and from the factorial number system.

Given a string (no longer than 71 characters or the maximum that gives a result your language can comfortably accommodate, whichever is less) convert it from mixed-base mixed-radix ZYX…432.234…XYZ using the base-36 digits [0-9A-Z] or [0-9a-z]. Any reasonable rounding is fine.

Examples

0 (0 × !1) → 0
1 (1 × !1) → 1
10 (1 × !2 + 0 × !1) → 2
11 (1 × !2 + 1 × !1) → 3
20 (2 × !2 + 0 × !1) → 4
1300 (1 × !4 + 3 × !3 + 0 × !2 + 0 ×!1) → 42
4020 (4 × !4 + 0 × !3 + 2 × !2 + 0 ×!1) → 100
230411112345
8B65700202114294967295
17A572665122010000000000
7BC43F3535083500021118446744073709551615
0.10.5
0.020.333333333333333333
0.1120.25
0.00220.1
21.0035.125
1.1111111111111111112.718281828459045235
0.000010.001388888888888889


| |
\$\endgroup\$
  • \$\begingroup\$ I think this is ready. \$\endgroup\$ – Zacharý Jul 11 '17 at 21:56
  • \$\begingroup\$ I'd like this more with a list of digits 0-35 in the factorial base rather than including letters. \$\endgroup\$ – xnor Jul 13 '17 at 8:16
  • \$\begingroup\$ @xnor Interesting. In that case, there should be no specific upper limit, right? \$\endgroup\$ – Adám Jul 13 '17 at 8:17
  • \$\begingroup\$ @Adám That's right, unless you want a limit for the sake of languages' number bounds. \$\endgroup\$ – xnor Jul 13 '17 at 8:18
  • \$\begingroup\$ @xnor I assume that's covered by default rules. This simplifies the challenge text, so I'll make the change. Thanks \$\endgroup\$ – Adám Jul 13 '17 at 8:18
  • \$\begingroup\$ @xnor How is this? \$\endgroup\$ – Adám Jul 13 '17 at 8:24
  • \$\begingroup\$ @Adám Looks good to me. Is your plan to post a challenge for just one direction? \$\endgroup\$ – xnor Jul 13 '17 at 8:32
  • \$\begingroup\$ @xnor Uh, did you read the post? \$\endgroup\$ – Adám Jul 13 '17 at 8:33
  • \$\begingroup\$ @Adám Yes, and I'm not sure if your plan is to post two challenges, or just whichever direction is more interesting. \$\endgroup\$ – xnor Jul 13 '17 at 8:51
  • \$\begingroup\$ @xnor Two challenges. However, I just noticed that factoradic can easily represent floats too, so should I extend/modify the challenges to that? It would certainly make them different from the existing one. \$\endgroup\$ – Adám Jul 13 '17 at 8:53
  • \$\begingroup\$ Yes, you should do that so built-ins won't be useful (cough Jelly cough) in addition to distinguishing this from the existing challenge. \$\endgroup\$ – Zacharý Jul 13 '17 at 19:57
  • 1
    \$\begingroup\$ The original challenge with letters was way better... \$\endgroup\$ – J42161217 Jul 14 '17 at 6:25
  • \$\begingroup\$ I actually agree with @Jenny_mathy because languages like Jelly naturally output different bases in a list format, rather than a string of letters. \$\endgroup\$ – Zacharý Jul 14 '17 at 13:17
  • \$\begingroup\$ @Jenny_mathy Like this? \$\endgroup\$ – Adám Jul 14 '17 at 14:22
  • \$\begingroup\$ @Zacharý Ping ^ \$\endgroup\$ – Adám Jul 14 '17 at 14:22
2
\$\begingroup\$

Solve the Trolley Problem

Philosophers have long pondered the Trolley problem. Unfortunately, this no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!

Your program will take as input a (finite) directed graph (with at most one edge from x to y, for any x and y), with a designated node, and a nonnegative integer attached to each edge (representing the number of people tied to that track). In addition, every node has at least one exit edge.

The trolley starts at the designated node. Each turn, if the trolley is at node x, the utilitarian selects an edge (x,y). The people on that edge die, and trolley is now at edge y. This process continues forever.

Note that people can only die once, so if the edge (x,y) has n people tied to it, and the trolley runs over them, say, 100 times, it will still only result in n deaths.

The utilitarian makes his choices in such a way as to minimize the number of people that die (which is guaranteed to be finite, since there are only finite people). Your program will output this number.

You may take the input graph in any reasonable way you like. For example, you could take it as a matrix, and count the designated node as the one labeled 0. Or you could use something like x1,y1,n1;x2,y2,n2;.... For example 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 to represent the standard trolley problem (with loops at the end).

Testcases:

  • 0,a,0;a,b,5;a,c,1;b,b,0;c,c,0 -> 1 (Go from 0 to a, a to c (killing one person), and then keep looping the trolley from c to c).
  • 0,0,1;0,a,5;a,a,0 -> 1 (Keep going from 0 to 0, running over 1 person for all eternity),
  • 0,a,5;0,b,1;a,a,1;b,b,6 -> 6 (0 -> a -> a -> a -> a -> ... (note that the greedy solution of going to b would be incorrect))
  • 0,a,1;0,b,5;a,b,1;b,a,1 -> 3 (0 -> a -> b -> a -> b -> ...)
  • 0,a,1;0,b,1;a,a,0;b,b,0 -> 1 (Note that there are two different options that the utilitarian might take that both kill only one person)

This is , so the shortest answer wins! Good luck.

Notes: There will be no sick loop de loops and multitrack drifting is banned.

| |
\$\endgroup\$
  • \$\begingroup\$ So basically: find the cycle of lowest weight? That's pretty similar to finding the cycle of greatest weight, which is equivalent (for integer weights) to codegolf.stackexchange.com/q/107274/194 \$\endgroup\$ – Peter Taylor Jul 22 '17 at 9:36
  • \$\begingroup\$ @Peter Taylor no, since you may have to kill lots of people to get to that cycle, or it might not be reachable at all. \$\endgroup\$ – PyRulez Jul 22 '17 at 12:26
  • \$\begingroup\$ Aha, so it's finding a rho of lowest weight. Still potentially quite similar in implementation, but certainly admits alternative approaches. It might improve clarity to explicitly describe the rho form of the paths to consider. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 12:33
  • \$\begingroup\$ @Peter Taylor what is rho? \$\endgroup\$ – PyRulez Jul 22 '17 at 15:44
  • \$\begingroup\$ ρ , as in Pollard's rho which uses paths which eventually loop back on themselves to factor composite numbers. \$\endgroup\$ – Peter Taylor Jul 22 '17 at 16:08
  • \$\begingroup\$ You should delete this as it has been posted. \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 19:41
2
\$\begingroup\$

An anagram chain

Your challenge is to create a program, P_0, that outputs P_1, that outputs P_2, that outputs... P_n, which finally outputs P_0. Every program in that chain has to be a permutation of every other program, and every program has to be distinct.

For example, if your program (P_0) was

abcd

And that generated another program (P_1)

badc

Which generated another program (P_2)

dabc

Which outputted the first program, you would have a anagram chain of length 3.

Your goal is to make as long a chain as possible, in as short a program as possible.

Your final score will be your chain length - in case there's a tie, the program with the shortest bytecount wins. If there's a tie again, the first poster wins.

Meta:

  • I need a better title. Any suggestions?
| |
\$\endgroup\$
  • \$\begingroup\$ [Related]. Actually, I'm pretty sure this is a dupe of another challenge that I can't find at the moment. \$\endgroup\$ – Shaggy Jul 23 '17 at 10:13
2
\$\begingroup\$

KotH: Atom Bomb Chess

(Draft. I'll flesh it out some more later. It will probably be implemented in JavaScript or maybe C++.)

Atom Bomb Chess is a variant of chess played much the same as regular chess. The only differences are:

  1. The game ends when one or both players have no pieces, or if 50 moves have been made without a piece being captured.
  2. When a piece is captured, all pieces a king's move away are also "captured", and the piece doing the capturing is also "captured".

For example, let's look at a 4x4:

pbbr
....
....
RBBP

Where r/R is a rook, b/B is a bishop, and p/P is a pawn. Suppose R moves forward 3 spaces. Then, it captures the p and "explodes":

..br
....
....
.BBP

The idea of this KotH is to make a program that plays Atom Bomb Chess. I will have a few programs to test your submissions against.

| |
\$\endgroup\$
  • \$\begingroup\$ This is a really cool idea! Obviously you'll need to flesh out the rules a bit more, but this is a great start. I would also suggest fixing the board size (you seem to suggest it can be played on any size board, but I think it would be easiest to set it as a constant ahead of time). \$\endgroup\$ – musicman523 Jul 23 '17 at 22:31
  • \$\begingroup\$ @musicman523 Yeah, it'd probably be played on an 8x8 \$\endgroup\$ – Conor O'Brien Jul 23 '17 at 22:35
  • 1
    \$\begingroup\$ you forgot that pawns are partially nuke proof \$\endgroup\$ – Destructible Lemon Jul 23 '17 at 23:15
  • \$\begingroup\$ @DestructibleLemon Please elaborate ? I wasn't aware there was some standard rulebook. \$\endgroup\$ – Conor O'Brien Jul 24 '17 at 1:45
  • 2
    \$\begingroup\$ I'm not entirely sure where it is, but I remember that pawns, while still being eliminated if they are capturing, or are captured, will not get removed if they are adjacent to a capture. maybe use lichess? \$\endgroup\$ – Destructible Lemon Jul 24 '17 at 2:51
  • \$\begingroup\$ @DestructibleLemon I remember playing it when I was younger with no such restriction, perhaps there are multiple variants. Why suggest lichess? Does it have that mode? \$\endgroup\$ – Conor O'Brien Jul 24 '17 at 18:02
  • \$\begingroup\$ Apart from pawns being nuke proof, the game ends as soon as you nuke the enemy king, if you play on lichess. There are videos on YouTube which include an explanation of the rules and basic "opening theory". \$\endgroup\$ – Sleafar Jul 28 '17 at 18:17
2
\$\begingroup\$

Who Won the Chess Game?

Bear with me, this is incredibly bare-bones at the moment; I'll work on this over-time, just wanted to gauge interest on the over-all idea.


Given an input list of moves l, output who won the chess game given that white always goes first, alternating moves from there. Using the following convention for naming the chess squares:

enter image description here

Where the pieces are:

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

The first assumption you will make is that the list of moves passed is a VALID chess game, to completion. The following would be an example input:

[[A2,A4],[A7,A6],...]

The first two moves given would result in:

rnbqkbnr
pppppppp
........
........
P.......
........
.PPPPPPP
RNBQKBNR

Which is white's first move, followed by black's move:

rnbqkbnr
.ppppppp
p.......
........
P.......
........
.PPPPPPP
RNBQKBNR

Then, you would continue parsing moves until a king disappears. Whichever king is left should be declared the winner.


Waiting to Gauge Interest Before Wasting Time on Full Testcase

| |
\$\endgroup\$
2
\$\begingroup\$

Nested list unpacking

In Python 3.5+, the * operator can unpack a list within a list.

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

The unpacked elements are placed directly into the outer list without increasing the list depth. Note that this is different from the nested three-element list

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

Your goal is to simplify a nested list expression by resolving all instances of unpacking. So, the output will simply be a nested list without any *.

Specifically, the input will be an expression that consists of

  • A non-empty list of expressions [..]
  • An non-empty unpacked list of expressions *[..].
  • A digit 1 through 9

The outermost layer will always be a non-empty list. The output is such an expression without any unpacking.

Input: A string of characters [],*123456789

Output: Its unpacked analogue. This can be a string or list structure.

This challenge can be done in any language. Python and other languages with the same unpacking format may not use eval or exec or equivalents.

TODO: I/O details, test cases

| |
\$\endgroup\$
  • \$\begingroup\$ This is similar to least Levenshtein distance to a balanced list (replace *[ with { and then remove unbalanced ]). \$\endgroup\$ – Peter Taylor Jul 25 '17 at 7:20
2
\$\begingroup\$

Tell me my vocabulary words! Donated.

When taking textbook notes, I need to write down the vocabulary words and their definition. So your task is to write some code that will give me the vocabulary words and their definitions!

Vocabulary words are detonated with a * on both sides of them, like this: Sentences are .-delimited, meaning that after every . a new sentence starts. An example of a valid sentence would be: This sentence has a *vocab word* in it. The vocab word in the sentence is 'vocab word'.

Input: A string of text with some words marked with asterisks. Only valid inputs will be provided, meaning that only sentences with exactly two asterisks inside of them, and there is something between the asterisks.

Output: A list or delimited string where each item is in the following format: Vocabulary word: sentence. The Vocabulary word is the vocab word found in the sentence. The sentence must be the one with the emboldened vocabulary word in it. If there is any whitespace other than the s separating the words, it needs to be stripped.

Test cases:

Input: *Alan Turing* invented the Turing machine. A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Output: *Alan Turing*: *Alan Turing* invented the Turing machine.
        *Turing machine": A *Turing machine* is a machine that follows simple rules, but is capable of any computation.

Input: What is code-golf? *Code-golf* is the best site on the SE network. But what is SE, you ask? *SE* is a group of Q&A sites, with a system to prevent bad posts.

Output: *Code-golf*: *Code-golf* is the best site on the SE network.
        *SE*: *SE* is a group of Q&A sites, with a system to prevent bad posts.

| |
\$\endgroup\$
  • \$\begingroup\$ So split on '.' and then filter to strings containing a *? Or can there be asterisks which don't mark vocabulary words? Should we trim whitespace at the start and end of the sentences? \$\endgroup\$ – Peter Taylor Apr 6 '17 at 9:54
  • \$\begingroup\$ @PeterTaylor A string surrounded by * is a vocab word, like this: *vocab word*. You need to format the outputted sentence correctly, and trim whitespace. I will edit when I have more time. \$\endgroup\$ – Comrade SparklePony Apr 6 '17 at 13:52
  • \$\begingroup\$ Are the following valid inputs or not? a) Unbalanced* asterisk; b) Empty ** vocabulary word; c) Vocabulary* word *has bad spacing. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 10:05
  • \$\begingroup\$ Only the last one is valid. \$\endgroup\$ – Comrade SparklePony Apr 7 '17 at 13:25
  • \$\begingroup\$ The latest wording "only sentences with exactly two asterisks in them" suggests that there's no need to filter: just split on ., trim, and prepend Vocabulary word: to each sentence. \$\endgroup\$ – Peter Taylor Apr 7 '17 at 21:03
2
\$\begingroup\$

Base 32 RFC 4648 Compliant Alphabet!

When writing my handy-dandy totp/hotp token implementation in Python and Swift (ad: here), I encountered for the first time RFC 4648. There is a nice and long memo about RFC 4648, but I only had to focus on a very specific part of it: Page 8. If you are bored and want some enthralling reading, you can find this memo here, and a useful table here.

Basically, I was looking for the alphabet that could be used when base 32 decoding a String. Well, this is it: ABCDEFGHIJKLMNOPQRSTUVWXYZ234567, and padding, =. However, simply printing that is not the challenge –– that would be too simple1. Instead, we are going to print this (the comments are for your reference and do not need to be printed):

__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x00 - 0x0F or   0 -  15
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x10 - 0x1F or  16 -  31
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x20 - 0x2F or  32 -  47
__,__,26,27, 28,29,30,31, __,__,__,__, __, 0,__,__,  // 0x30 - 0x3F or  48 -  63
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x40 - 0x4F or  64 -  79 
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x50 - 0x5F or  80 -  95
__, 0, 1, 2,  3, 4, 5, 6,  7, 8, 9,10, 11,12,13,14,  // 0x60 - 0x6F or  96 - 111
15,16,17,18, 19,20,21,22, 23,24,25,__, __,__,__,__,  // 0x70 - 0x7F or 112 - 127
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x80 - 0x8F or 128 - 143
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0x90 - 0x9F or 144 - 159
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xA0 - 0xAF or 160 - 175
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xB0 - 0xBF or 176 - 191
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xC0 - 0xCF or 192 - 207
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xD0 - 0xDF or 208 - 223
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xE0 - 0xEF or 224 - 239
__,__,__,__, __,__,__,__, __,__,__,__, __,__,__,__,  // 0xF0 - 0xFF or 240 - 255

There may be trailing spaces after every line, and trailing newlines after the last one.

Also, the single digit numbers can be written as 0[digit] instead of [space][digit]. However, be sure to include the spaces between the four groups.

By the way, the __ actually represent 255, but the former do not make me drown in a sea of digits.


1 Should the challenge be to just print that string?

Any other suggestions to make this challenge more interesting?

| |
\$\endgroup\$
  • \$\begingroup\$ Perhaps get a list of characters (of any length) and print such a table? \$\endgroup\$ – ugoren Jul 29 '17 at 19:14
2
\$\begingroup\$

Is this 2048 board valid?

Some 2048 boards are impossible to get into. For example,

2 _ _ 2
_ _ _ _
_ _ _ _
2 _ _ 2

will never occur in a 2048 game. Additionally, these are all impossible:

8 _ _ 8    8 _ _ _    2 2 2 2
_ _ _ _    _ 8 _ _    2 2 _ _
_ _ _ _    _ _ _ _    _ _ _ _
8 _ _ _    _ _ _ _    _ _ _ _

Your program needs to accept a 2048 board, and return a truthy value if the board is reachable, else falsy.

//Explanation of 2048 goes here.

I've listed 4 different boards that cover major test cases. Are there any others I'm missing?

| |
\$\endgroup\$
  • \$\begingroup\$ hehe, don't forget [tag:sliding-puzzle] \$\endgroup\$ – Stephen Aug 1 '17 at 19:56
  • \$\begingroup\$ As you've stated yourself the main thing missing here is the bulk of the challenge. \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 9:14
  • \$\begingroup\$ I wonder if it suffices to look one step back, or if you need to check if the previous position can itself be produced. \$\endgroup\$ – xnor Aug 4 '17 at 7:35
2
\$\begingroup\$

Smooth Usage [On hold while alternative scoring is considered]

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

CPU Usage example

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


Challenge

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

You may assume:

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

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

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

Time bomb ping pong


Challenge - Both teams

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

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

Each user has two options:

  • Start a new bomb
  • Perform a counterattack

These actions are discussed here:


Start a new bomb

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

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

This is an example of a new bomb submission:


Python 2, 9 bytes (index = 1)

Outputs the number 30.

print 5*6

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



Perform a counterattack

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

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

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


Python 2, 12 bytes (index = 2)

Defuses Python 2, 9 bytes, Adnan.

Inserts 1, / and 3. Outputs 30:

print 15*6/3

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



Scoring system

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

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


Sandbox notes

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

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

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

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

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

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

Thanks in advance!

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

Conversion: 2 dice from 3


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

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

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

Input

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

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

Output

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

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

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

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

Checking for correctness

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

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

Scoring

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

Prior work

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

Test cases

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


Sandbox questions

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

Is this a valid Takuzu board?

Takuzu is a logic game in which you have to complete a grid with cells containing 0s and 1s. The grid must follow 3 rules:

  1. No three horizontal or vertical cells in a row can be the same.
  2. There must be an equal number of 0s and 1s in each row and column.
  3. No two rows can be the same, and no two columns can be the same.

Let's look at a finished grid:

0011
1100
0101
1010

As you can see, this board follows rule 1, 2 and 3. There are no three horizontal or vertical cells that are the same, all the rows and columns contain an equal number of 0s and 1s, and no two rows and no two columns are the same.

Let's look at a grid that isn't valid:

110100
010011
011010
101100
100011
001101

There's a bunch of problems with this grid. For example, row 5 has three 0s in a row, and column 2 has three 1s in a row, followed by three 0s. Therefore, this is not a valid grid.

Task:

Your task is to make a program which, given a 2D array of n * n 0s and 1s, verifies the board to see if it's a valid, finished Takuzu board.

Examples:

0011
1100
0101
1010

This board follows all the rules, and is therefore a valid Takuzu board. You must return a truthy value for this.

11
00

This is not a valid board - row 1 doesn't follow rule 2. You must return a falsey value for this.

Rules and Specs:

  • You can assume that all boards are square of dimensions n * n, where n is a positive even integer.
  • You can assume that all boards are finished.
  • You may take input as a 2D array containing values signifying 0 and 1, or as a string.
  • You must output consistent truthy and falsey values for truthy and falsey boards, and the values representing "truthy" and "falsey" cannot be the same.

This is , so shortest code in bytes wins!

| |
\$\endgroup\$
  • \$\begingroup\$ 1. "No three horizontal or vertical grids in a row can be the same": there's only one grid. I propose rewording as "No horizontal or vertical line of three cells can be the same". 2. Related: codegolf.stackexchange.com/q/68646/194 , codegolf.stackexchange.com/q/118856/194 . Note that because this question works through a long example before stating very briefly that (in essence) the example is irrelevant to the question, it can very easily mislead people into thinking it's an exact dupe of the second of those related questions. \$\endgroup\$ – Peter Taylor Aug 27 '17 at 16:49
  • \$\begingroup\$ ...also note that the example you run through before giving the task can actually be performed by only using rule (2). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 6:47
  • \$\begingroup\$ @PeterTaylor Will fix the example and other points, I wasn't active for a while, sorry for the late reply. \$\endgroup\$ – clismique Aug 29 '17 at 6:48
  • 1
    \$\begingroup\$ @JonathanAllan Through fixing PeterTaylor's suggestion I also fixed yours :P \$\endgroup\$ – clismique Aug 29 '17 at 6:53
  • \$\begingroup\$ By "You must output distinct truthy and falsey values for truthy and falsey boards" do you mean "consistent" ones - i.e. the Truthy (falsey) value is to be the same for each time a valid (invalid) board is input? The normal definition of Truthy vs Falsey is language dependent: any values that conditionally evaluate as such (i.e. such that the equivalent of the pseudo-code if myVal then print("True!" else print("False!") works as expected). \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 7:05
2
\$\begingroup\$

Align the Words

Given a list of words l output them as follows:

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

Worked Example

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

1: ace

2:  ace
   face

3:  ace
   face
    please

4:  ace
   face
    please
     keep

5:  ace
   face
    please
     keep
    sheeple

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

Rules

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

100 Letters is the Perfect Amount

Oxford dictionary lists the most commonly used English letters in the following order:

EARIOTNSLCUDPMHGBFYWKVXZJQ

And assigns each the following frequencies:

Distribution of the letters...

For the purpose of this challenge, the diagram will be simplified as follows:

z   1
q   1
x   1
j   1
k   1
v   1
b   2
p   2
y   2
g   2
f   2
w   2
m   3
u   3
c   3
l   4
d   4
r   5
h   6
s   6
n   6
i   6
o   7
a   8
t   9
e   12
TOT 100

Now, onto the task at hand; I've provided you all with a dictionary of words to choose from, using this dictionary of words choose as many as you want to output. However the catch is that you must have EXACTLY the count above of each letter in the output using 7-12 words.


Scoring

  • Your base score is the length of your code in bytes.
  • You are allowed to go over or under on the number of letters required, each letter above or under results in a +5 byte penalty.
  • If the number of words you've used is between 7 and 12, no penalty is incurred.
    • IF it exceeds 12, add 10 bytes per additional word.
    • IF it is less than 7, subtract 5 per missing word.

Rules

  • You may use any word from the provided dictionary.
  • Each word you output must be distinctively separated by either a space or a newline.
  • Once a word combination has been posted, you may not use more than 6 of that answer's words together in a new answer.
    • This will be enforced by post date.
  • This is
  • Your score will be as defined in the scoring section.
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ How can you get a meaningful penalty for going under the number of letters required when you must have AT LEAST the count above of each letter? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:21
  • \$\begingroup\$ Also, who was Kolmognogniznornia? \$\endgroup\$ – Jonathan Frech Sep 19 '17 at 0:22
  • \$\begingroup\$ @JonathanFrech he was the first Aztec man to invent the concept of speech. \$\endgroup\$ – Magic Octopus Urn Sep 19 '17 at 0:30
  • 2
    \$\begingroup\$ I'm not sure this is really kolmogorov-complexity: by design, a good answer will be incompressible. However, finding a good answer is going to involve a heavy computer search, and then the posted answer is going to be a string literal. That seems completely backwards: the interesting code should be what the question asks for. \$\endgroup\$ – Peter Taylor Sep 19 '17 at 7:39
  • \$\begingroup\$ @PeterTaylor was kinda going for something more unique, y'know? Sorta like my "5 favorite letters" challenge. \$\endgroup\$ – Magic Octopus Urn Mar 13 '18 at 20:47
2
\$\begingroup\$

Implement a BrainFlump interpreter

BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.

It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.

Commands

+   #Increment the item at the pointer
-   #Decrement the item at the pointer
:   #Add a 0 to the dump, and move the pointer to it
;   #Move the pointer to a random item that is not the pointer's current position
(   #Skip to the matching ) if the item at the pointer is 0
)   #Skip to the matching ( if the item at the pointer is not 0
,   #Read a single character from STDIN and push its ascii value to the dump
    #This also moves the pointer to the new item
.   #Print the current item at the pointer modulo 127 as an ASCII character

Interpreter or Compiler?

BrainFlump is an interpreted language. Meaning your submission must take BrainFlump code as input, and return the expected output of the code.

This is as opposed to a compiler, which would take BrainFlump code as input, and return a compiled binary that returns the expected output.

Other notes

  • When the ; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
  • The . command does not pop the item from the dump
  • When the , command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
  • Any item in the dump who's value is 0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
  • Nested loops are supported
  • The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
  • BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below 0 has no effect.
  • The maximum value of an item in the dump is 255

Examples/Testcases

brainf**k emulation

++++++(;++++++++;-);.

This should output 0

Explanation

++++++        #Increment the first item to 6
(             #While the item under the pointer is not 0
    ;         #Move to another item in the dump
              #    Note the first time this loop runs,
              #    this will insert a new item
    ++++++++  #Increment the new item by 8
    ;         #Switch to another item in the dump
              #    Note there are only 2 items currently,
              #    So this will switch to the only other
              #    item, the one we initially incremented to 6
    -         #Decrement the item
)             #Repeat the loop if the item is not 0
;             #Switch to the other item
              #    Note this switches the pointer back to
              #    The item we have been incrementing by
              #    8 each loop
.             #Output as ASCII character

This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.

Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.

Random output

+:++:+++:++++:+++++:;.

This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.

Explanation

+      #Increment first item to 1
:      #Add new item and move to it
++     #Increment new item to 2
:      #Add new item and move to it
+++    #Increment new item to 3
:      #Add new item and move to it
++++   #Increment new item to 4
:      #Add new item and move to it
+++++  #Increment new item to 5
:      #Add new item and move to it
       #    Note this last item is added because ; will
       #    always switch to an item that is *not* the
       #    currently selected item
;      #Switch randomly to an item in the dump
.      #Output as ASCII character

To give a little more info on this, by the time the ; command is reached, the dump should look like this:

1 2 3 4 5 0
          ^

As ; always switches to a different item, the result will be the pointer at one of the non-zero items.

cat

,(.,)

Nice and simple, and identical to brainf**k's cat program.

For scoring purposes, you should use this gist as input when testing.

When will it end?

++++(,:+++++;++(;++++++;--):++++;---)

This program doesn't output anything, but runs for a non-deterministic amount of time.

Explanation

++++             #Increment first item to 4
(                #Start loop
    ,            #Read char from STDIN to new item in dump
    :+++++       #Push 5 to dump
    ;++          #Switch to random item in dump and add 2
    (            #Start loop
        ;++++++  #Switch to random item in dump and add 6
        ;--      #Switch to random item in dump and subtract 2
    )            #End loop
    :++++        #Push 4 to dump
    ;---         #Switch to random item in dump and subtract 3
)

This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)

The inner loop will only exit if ;-- switches to a number <= 2

The outer loop will only exit if ;--- switches to a number <= 3

Due to the inherent randomness of the language, this should always terminate... eventually.

For scoring purposes, you should use the exact string Hello, World! as input when testing.

Scoring

This is meaning the interpreter that on average runs the fastest, wins!

Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).

Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better

| |
\$\endgroup\$
2
\$\begingroup\$

Count bicubic graphs

This question assumes basic knowledge of graph theory terminology.

A cubic graph is a simple graph whose vertices each have exactly 3 edges. A bipartite graph is a vertex whose vertices can be divided into two disjoint sets such that every edge is between a vertex in one set and a vertex in the other set. A bicubic graph is a graph which is both cubic and bipartite.

It is easy to show that a bicubic graph must have the same number of vertices in each of the bipartite halves, so the number of vertices must be even. It is also easy to show that it must have at least six vertices. The only bicubic graph with six vertices (up to isomorphism) is the so-called utility graph or K3,3:

The edges are the Cartesian product of two three-element sets of vertices

Input

A positive non-zero integer n.

Output

The number of bicubic graphs with 2n vertices, up to isomorphism.

Notes

  • The graphs are not required to be connected.
  • This sequence is OEIS A008325. However, hard-coding these values will be considered a breach of standard rules. You may hard-code for inputs of up to 3, but above that the code should follow the same paths and be correct assuming unbounded memory and time for any valid input. It seems unlikely that we will extend the sequence, but it's nonetheless a worthy stretch goal.

Test cases

Input  Output

1      0
2      0
3      1
4      1
5      2
6      6
7      14
8      41
9      157
10     725
11     4196
12     29816

Winning criterion

The fastest program wins. The primary win condition is the largest input for which correct output is given within 10 minutes. In case of ties, the time taken to compute the value for that input will be compared. If the difference is less than 20 seconds, the earlier answer wins.

| |
\$\endgroup\$
2
\$\begingroup\$

All ASCII Art

Input

You will be given a set of x, y, and A pairs, where x and y represent a coordinate on a 2-d plain, and A is some character. You may take these pairs in any convenient format, e.g. a list of lists, three separate lists, a list of pairs of lists, etc.

Output

You will output a grid of spaces. However, at every coordinate specified in the input, the space should be replaced by the character. Basically, the input specifies the locations of characters, and you have to draw them.

Specifics

  • x and y may be either a coordinate or a row-column pair (e.g. the origin can be in the bottom left, with x increasing to the right and y increasing up, or the origin can be in the top left, with x increasing to the right and y increasing down).
  • All characters are guaranteed to be printable ASCII, and will never be a space.
  • x and y are >= 0
  • You may output trailing whitespace (but not infinitely). What matters is that the output visually looks like what the input specified, not the whitespace.

Test Cases

Test cases format (the test cases have the origin at the top left corner; this is optional, see specifics):

# of coordinates
row col char
row col char
...
-----------
output

Test cases:

2
0 0 :
0 1 )
-----------
:)

3
0 0 -
0 1 _
0 2 -
-----------
-_-

4
0 1 -
1 0 |
2 1 -
1 2 |
-----------
 - 
| |
 - 

11
0 0 (
0 1 ^
0 2 o
0 3 ^
0 4 )
1 1 /
1 2 |
1 3 \
2 2 |
3 1 /
3 3 \
-----------
(^o^)
 /|\
  |
 / \

Here is a Java program which can be used to test out inputs

Meta

| |
\$\endgroup\$
  • \$\begingroup\$ Is (0,0) the top-left of the output image? It kinda looks that way from your examples, but that should be made clear. \$\endgroup\$ – AdmBorkBork Nov 3 '17 at 12:30
  • \$\begingroup\$ @AdmBorkBork it is for the test cases, but its meant to be optional... I'll clarify \$\endgroup\$ – Socratic Phoenix Nov 3 '17 at 12:43
1
17 18
19
20 21
96

You must log in to answer this question.

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