552
\$\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

3852 Answers 3852

6
\$\begingroup\$

Question link

\$\endgroup\$
8
  • \$\begingroup\$ @Night2 Indeed, didn't notice that point, I fixed the samples in the rules to include AA-000-AA \$\endgroup\$
    – Elcan
    Sep 20, 2019 at 6:25
  • \$\begingroup\$ Are the letters mandatory to be uppercased, or could we output in lowercase as well? \$\endgroup\$ Sep 20, 2019 at 9:51
  • 1
    \$\begingroup\$ @KevinCruijssen Yes, letters are mandatory to be uppercase, also I feel like you ask that because of a builtin somewhere :P \$\endgroup\$
    – Elcan
    Sep 20, 2019 at 12:36
  • \$\begingroup\$ Fine by me. I was mainly asking because it isn't a core-part of the challenge, and in some challenges lowercase/uppercase/mixed case is all allowed. But you're indeed right that lowercase would save a byte in my language of choice 05AB1E, where A is the lowercase alphabet builtin, and I'd need an additional u to uppercase it. ;p But since number plates are always uppercase, I can understand to keep the uppercase mandatory here as well. I had prepared a 24-byter, but will throw it away for now since I feel this can be done shorter.. Will try again later when it's posted to main. :) \$\endgroup\$ Sep 20, 2019 at 12:41
  • \$\begingroup\$ Another question, or more recommendation: allowed both 0-based and 1-based indexing for answers. I see your test cases are 0-based, but some languages use 1-based indexing instead. \$\endgroup\$ Sep 20, 2019 at 12:44
  • 1
    \$\begingroup\$ @KevinCruijssen Sure, no problem with 1-based indexing, going to fix the rules to add that. As I've never used such languages, I often forget about them \$\endgroup\$
    – Elcan
    Sep 20, 2019 at 13:19
  • \$\begingroup\$ I would say if the format irl has to be in uppercase then following that would be better. I've got myself an 85-byte JS answer that conforms to the irl format though. \$\endgroup\$ Sep 21, 2019 at 1:06
  • \$\begingroup\$ @ShieruAsakoto That's what I also advocate for, minus all the dumb real life rules that would just make it unfun to do. Anyway, going to post this \$\endgroup\$
    – Elcan
    Sep 23, 2019 at 18:41
6
\$\begingroup\$

Almost Illegal Strings

Posted.

\$\endgroup\$
11
  • \$\begingroup\$ Does the challenge need to have the robber code output "Well done!"? What if they could just submit any code with the substring that runs? \$\endgroup\$
    – xnor
    Oct 24, 2020 at 10:24
  • \$\begingroup\$ @xnor That's fair enough - I just struggle to define 'program that runs'. Would you consider zero exit code and no stderr output reasonable? Or are there some languages that output to stderr even in a valid program? \$\endgroup\$
    – Sisyphus
    Oct 24, 2020 at 12:00
  • \$\begingroup\$ I think this is too similar to the original "illegal strings" question which basically turned into a cops-and-robbers anyway \$\endgroup\$
    – pxeger
    Oct 24, 2020 at 18:26
  • \$\begingroup\$ @Sisyphus I was thinking you could just copy whatever condition Find an Illegal String uses. But it doesn't seem to be that rigorous, saying "The compiler/interpreter/runtime must give an error when given any source code that contains your string as a substring." I think requiring no output to STDERR is probably fine. Maybe though some languages give warnings to STDERR that golfers typically ignore? Note that defaults allow programs that print then crash, so just requiring output doesn't preclude a fatal error after. \$\endgroup\$
    – xnor
    Oct 24, 2020 at 21:12
  • \$\begingroup\$ Rule suggestion: commenting out the almost illegal string is not allowed \$\endgroup\$
    – Beefster
    Oct 28, 2020 at 15:33
  • \$\begingroup\$ I think it's too thorny to define what comments are in a way that works across languages. One objective way to handle it would be to let cops specify a set of characters that are not in their code, where they might include their language's comment character(s) or quote literals. \$\endgroup\$
    – xnor
    Oct 29, 2020 at 0:40
  • \$\begingroup\$ @xnor Ok, I've rewritten the challenge to just require that the program does not error, and feel the rules are fairly straightforward and watertight. \$\endgroup\$
    – Sisyphus
    Nov 1, 2020 at 5:50
  • \$\begingroup\$ @Beefster I considered this, and something like xnor's suggestion of banning characters. However, I think it ruins the purity of the challenge a bit, and for most languages it's very easy to avoid being in a comment (newline + end of comment block will do it). There are some languages which have 'inescapable comments', such as raw strings with specific delimiters, or something like Perl's __END__, but they're sacrifices I'm willing to make. \$\endgroup\$
    – Sisyphus
    Nov 1, 2020 at 5:52
  • \$\begingroup\$ The problem with not banning comments (or including things within strings, for that matter) is that it's quite easy to cop out and write a hello world with the almost illegal string appended in a comment. That takes out all the challenge. xnor's suggestion solves that mostly, but that does end up limiting cops a little bit to make the robbers' job an actual challenge. \$\endgroup\$
    – Beefster
    Nov 2, 2020 at 16:25
  • 1
    \$\begingroup\$ @Beefster Apologies, I have not been clear about my reasoning. My logic is that for the vast majority of languages, a cop can 'comment proof' their string trivially by adding a newline (to escape a single line comment) and an end of comment block (to end a multiline comment). For example, the string \nx"""x''' (with a literial newline) escapes all Python comments. You can do this in most languages - or am I missing something? \$\endgroup\$
    – Sisyphus
    Nov 3, 2020 at 3:12
  • 2
    \$\begingroup\$ @Beefster It looks like you were right - it is too hard without allowing Cops to ban characters. I'd like to apologise for not taking your feedback more seriously while the question was in the sandbox. \$\endgroup\$
    – Sisyphus
    Nov 6, 2020 at 1:10
6
\$\begingroup\$

Speed of Lobsters

\$\endgroup\$
0
6
\$\begingroup\$

Print random integers until 0

\$\endgroup\$
10
  • \$\begingroup\$ Presumably, if the first number is zero, we just output zero and exit? \$\endgroup\$
    – pxeger
    Jan 16, 2021 at 18:57
  • \$\begingroup\$ "integers may be separated by any non-digit, non-empty separator" can we output in zero-padded form (00 01 .. 98 99) so that a separator isn't necessary? What about codepoints/byte values (NULL - c)? Can it be a list-like object rather than a separated string? I think this would be better with more sequence-like IO rules \$\endgroup\$
    – pxeger
    Jan 16, 2021 at 18:59
  • 1
    \$\begingroup\$ @pxeger Yes, if the first number is zero, you just output zero and exit. I don't think the standard is to output with zero-padding, so I'll say no on that. Byte values and list objects are both standard forms of outputting a bunch of numbers, so of course, those are allowed \$\endgroup\$ Jan 16, 2021 at 19:07
  • \$\begingroup\$ Also, I assume it is not necessary that the program follows the indicated procedure (which would be unobservable anyway), as long as the output has the same statistical properties. So if a different procedure is used, perhaps the answer writer should justify it. (For example: generate a number K geometrically distributed with parameter 1/99, then output K nonzero numbers, then output a 0) \$\endgroup\$
    – Luis Mendo
    Jan 16, 2021 at 19:07
  • \$\begingroup\$ @LuisMendo Yeah, I'm pretty sure that "you don't have to follow the letter of the challenge so long as the behaviour is the same" is a standard rule, but in case not, I've edited in a sentence along with your example \$\endgroup\$ Jan 16, 2021 at 19:10
  • \$\begingroup\$ I didn't fully define my example, sorry. You may want to change it to "then output K independent numbers with a uniform distribution on the set {1, 2, ..., 99}". That corresponds to the procedure you specify with a uniform distribution on {0, 1, ..., 99}. \$\endgroup\$
    – Luis Mendo
    Jan 16, 2021 at 19:21
  • \$\begingroup\$ @cairdCoinheringaahing are built-in functions for generating pseudo-random numbers forbidden? If not, is the challenge a very trivial one or am I missing something? \$\endgroup\$
    – anotherOne
    Jan 27, 2021 at 23:17
  • 1
    \$\begingroup\$ @Davide Trivial challenges are not necessarily bad, since it encourages participation in relatively hard-to-use or minimal esolangs. And I think this one is actually good because I smell many unexpected approaches to golf the problem. (Also, banning built-ins are considered bad.) \$\endgroup\$
    – Bubbler
    Jan 28, 2021 at 0:26
  • \$\begingroup\$ @Bubbler thank you so much for this train of information \$\endgroup\$
    – anotherOne
    Jan 28, 2021 at 0:35
  • 1
    \$\begingroup\$ @Davide Nope, all builtins are allowed. As Bubbler said, trivial challenges are only really bad if there’s no room for interesting solutions, which I don’t think is the case here \$\endgroup\$ Jan 28, 2021 at 10:06
6
\$\begingroup\$

Remove Nth occurrences

\$\endgroup\$
4
  • 2
    \$\begingroup\$ There is this but it got closed, Everything is clear, but can you replace, "the n" with "the integer n" in the last point of your assumptions list. For some reason that made me read the sentence multiple times. \$\endgroup\$
    – Alex bries
    Feb 23, 2021 at 12:08
  • \$\begingroup\$ Is there a reason for limiting the array values to 1-9? \$\endgroup\$
    – pxeger
    Feb 23, 2021 at 19:49
  • 1
    \$\begingroup\$ @pxeger Because the values don't matter, so there's no reason to complicate it more. Plus, it can allow for some interesting string based approaches by taking \$A\$ as a single string \$\endgroup\$ Feb 23, 2021 at 19:52
  • \$\begingroup\$ @pxeger It certainly helps that 0 cannot be part of the array, because then I can use it to erase values in APL. I'm sure other languages can take advantage of that too \$\endgroup\$
    – user
    Feb 24, 2021 at 1:48
6
\$\begingroup\$

To raise \$ e \$ to the power of a matrix

Posted


Meta

  • Is this clear enough?
  • Is this a duplicate?
  • Any other feedback?
\$\endgroup\$
8
  • \$\begingroup\$ why not require exact calculation, it makes for a harder challenge but a more interesting one \$\endgroup\$
    – rak1507
    Apr 1, 2021 at 19:54
  • \$\begingroup\$ @rak1507 it's irrational so an exact value can't be calculated \$\endgroup\$
    – pxeger
    Apr 1, 2021 at 19:55
  • \$\begingroup\$ looked like there were methods on wikipedia but I could be wrong \$\endgroup\$
    – rak1507
    Apr 1, 2021 at 21:45
  • \$\begingroup\$ Note that the exponential of a 9x9 matrix of 100's exceeds what floats can represent. You might want to lower the 100 bound or make allowances for that. \$\endgroup\$
    – xnor
    Apr 2, 2021 at 6:30
  • \$\begingroup\$ I think the precision convergence rule is too restrictive and too tied to that specific power series method, and some loose accuracy bound would allow more varied methods. For instance, one can approximate \$e^M \approx (I+M/n)^n\$ for large \$n\$. \$\endgroup\$
    – xnor
    Apr 2, 2021 at 6:38
  • \$\begingroup\$ @xnor I didn't read much into the matrix exponential (because I couldn't find the article on Wikipedia and was too busy watching the rest of the 3b1b video :P), so I hadn't not really realised there were other ways to compute it. What would you recommend? I still like the idea of requiring it to be observed to converge within floating point limits, because it adds an extra layer of challenge rather than just "repeat this step 100 times", but maybe that just isn't practical \$\endgroup\$
    – pxeger
    Apr 2, 2021 at 6:50
  • 5
    \$\begingroup\$ I think convergence within floating point limits would unfortunately be hard and finicky here because of the nature of exponentials. The same way that \$e^{100}\$ and \$e^{100.001}\$ differ a lot, small errors in the computation can accumulate into huge ones. Also, the values in the output might be extremely small and become represented as zero. I'd have to think more about bounds, but maybe something like every entry within either 1% or 1e-4 of the true one should work. \$\endgroup\$
    – xnor
    Apr 2, 2021 at 7:03
  • 2
    \$\begingroup\$ My solution to floating-point errors is "the result should be within [insert error bound here] relative error for the given test cases". (The bolded part is VERY important. FP computation methods often have errors dependent on the magnitude of the input, so it is very hard to judge if an implementation is valid, even if the possible input range is specified. Explicitly giving the test cases makes it much easier to test submissions. Also, you need to craft the test cases carefully so that you don't accidentally ban a valid method or allow invalid methods.) \$\endgroup\$
    – Bubbler
    Apr 4, 2021 at 23:28
6
\$\begingroup\$

Non-quining infinite printer

Seems like the title could be better but I'm not sure what to do instead

I have heard that a monkey typing random keys on a typewriter, given infinite time, will eventually type out the entire works of Shakespeare, and in fact type out every possible string of characters of any length. This sounds to me like the basis for a profitable business venture in publishing. Unfortunately, however, as a result of previous failed business ventures, I am legally barred from possessing either monkeys or typewriters, so I'll instead need a program. I want this program to provably generate every possible string of characters, assuming infinite time and memory. Repetition is fine, as is overlap, as long as every possible string appears somewhere in the output. There's a catch, though. I imagine once my business gets off the ground and people realize the potential profits, they might want to get their hands on my program. The trouble is that since I'm outputting every possible string of text, in theory I'll eventually end up outputting the program itself, leaving it open to be stolen. To prevent this, I want the program never to output its own source code. It should still output every other possible string, just not itself (or, obviously, any strings which it is a substring of). Because my funds are currently very tight, I can't afford to pay for more bytes than are necessary, so I'm seeking the shortest possible program that does the job (This is a code-golf challenge, shortest answer in bytes wins). Is it communicated well enough what this challenge is asking for? Should I add a TL;DR and/or a more technical explanation of what's being looked for?

Additional notes:

  • I've had enough run-ins with the law in previous ventures, I'd like this one to go smoothly. So no abusing loopholes in the program, please.
  • Given that this program is my financial plan for the next infinity years, I'd like some reassurance that it actually does what it's supposed to. Please provide at least a brief explanation of why your code works, since it can't exactly be tested.
  • Any character encoding is fine, please specify though. The exception is that your source code must be printable in the encoding you use. Is this a reasonable way to handle this that is fair to all languages?
  • No reading your own source, because that makes quine-related holes uncool, and uncoolness does not fit with my businesses' brand persona.
\$\endgroup\$
7
  • \$\begingroup\$ How are the strings in the output separated? Some previous challenges about "print all possible strings" were closed as unclear because of this. \$\endgroup\$
    – Bubbler
    Jun 7, 2021 at 1:06
  • \$\begingroup\$ @Bubbler The strings don't have to be separated. What I mean is that every string should be a substring of the "main" output if that makes sense. Put another way, running a regex match on the output for any string of characters (other than the source) should return at least one result. Would adding something to that effect clear up that confusion? \$\endgroup\$
    – je je
    Jun 7, 2021 at 1:13
  • \$\begingroup\$ It should still output every other possible string, just not itself (or, obviously, any strings which it is a substring of) Okay, the task makes sense now. I think you'll need to add that information somewhere before the sentence I quoted. Now I wonder if the task is actually possible... \$\endgroup\$
    – Bubbler
    Jun 7, 2021 at 1:39
  • \$\begingroup\$ @Bubbler Sure, it's possible. One approach is to store the program's source in a string, and then run some sort of code that generates every possible string, checking after each generation whether the generated string contains the source string, and only printing if it doesn't. There might be some trouble in making sure the source isn't present in a combination of two consecutively generated strings (i.e. if the source code is AB, then outputting XA and BX consecutively is an issue), but a simple solution to that is to insert a character not present in the source between each pair. \$\endgroup\$
    – je je
    Jun 7, 2021 at 8:02
  • \$\begingroup\$ Here's an implementation in Python tio.run/… \$\endgroup\$
    – je je
    Jun 7, 2021 at 8:03
  • \$\begingroup\$ @jeje An easily thought solution is just use an unused char as split, but that likely be longer \$\endgroup\$
    – l4m2
    Jul 1, 2021 at 16:40
  • \$\begingroup\$ What do mean by "all possible strings"? Is this restricted to all strings consisting of printable ASCII? The entire Unicode table? \$\endgroup\$ Jul 8, 2021 at 1:14
6
\$\begingroup\$

Who Is Kevin Bacon?

\$\endgroup\$
2
  • \$\begingroup\$ > I'm worried it will just be "string a load of combinatorial builtins together" and brute-force it That's a solution to pretty much anything \$\endgroup\$
    – emanresu A
    Dec 30, 2021 at 5:12
  • \$\begingroup\$ it looks interesting enough, I can't find anything similar with searches like "Erdos number" and such. It will inevitably get a trivial golflang answer, especially with felxible input methods. To control quality, maybe adding a restricted-time would help. \$\endgroup\$
    – Razetime
    Jan 2 at 7:49
6
\$\begingroup\$

Sort every dimension

\$\endgroup\$
6
\$\begingroup\$

Output a random unary string

\$\endgroup\$
9
  • \$\begingroup\$ Would printing an infinite stream of separators or xs be valid? It's an infinitesimally small chance that just, e.g., one x is ever printed for the rest of time, but does that count (I'd be inclined to say no)? \$\endgroup\$ Feb 22 at 20:43
  • \$\begingroup\$ i have no idea what this challenge is about but +1 \$\endgroup\$
    – DialFrost
    Feb 23 at 3:43
  • \$\begingroup\$ Since most languages random number generator (RNG) only have finite state, The program won't output infinity number of different outputs. You may argue that we may consider (assume) RNG have infinity digits (precision). But then, someone would argue that repeat("x", floor(1/random_between_0_and_1())) is a valid submission as we can consider the output of random_between_0_and_1 have infinity precision. It is not very clear which is valid and which is not to me. \$\endgroup\$
    – tsh
    Feb 23 at 10:32
  • \$\begingroup\$ Looks like "the RNG in use has perfect random distribution" is a necessary assumption, but allowing the return value of RNG to be of infinite precision sounds a bit weird, as tsh pointed out. You may want to clarify these points in the challenge rules. (I'm not entirely against it though; in some langs the only source of randomness is a random real number in [0,1), which makes some compromises like "you can only use RNGs that return a finite number of integers" unsuitable) \$\endgroup\$
    – Bubbler
    Feb 23 at 23:56
  • \$\begingroup\$ @tsh @Bubbler Do you think the rule I just added is adequate? (I think tsh's suggested repeat("x", floor(1/random_between_0_and_1())) should be considered valid as long as it never causes a division by zero.) \$\endgroup\$
    – pxeger
    Feb 24 at 16:20
  • \$\begingroup\$ @pxeger I cannot understand how random_between_0_and_1 output a "infinite precision" number in finite time (so program will halt with with probability 1). But regardless this, the rule seems clear to me. \$\endgroup\$
    – tsh
    Feb 25 at 7:20
  • \$\begingroup\$ @tsh Well obviously nothing can output an infinite precision number of any kind, but I'm allowing it as an assumption because I think it should be considered a valid possible solution. \$\endgroup\$
    – pxeger
    Feb 25 at 7:44
  • \$\begingroup\$ Does "Every possible length of xs" includes 0 (empty output)? \$\endgroup\$
    – tsh
    Feb 25 at 9:08
  • \$\begingroup\$ @tsh "You may choose whether to include the empty string as a possible output" \$\endgroup\$
    – pxeger
    Feb 25 at 9:50
6
\$\begingroup\$

Can you draw this in one stroke

Posted here

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Related \$\endgroup\$
    – emanresu A
    Feb 19 at 0:48
  • \$\begingroup\$ I suggest sticking to standard decision-problem defaults with the output. \$\endgroup\$
    – pajonk
    Feb 22 at 6:50
  • \$\begingroup\$ @pajonk nice, thanks \$\endgroup\$
    – mathcat
    Feb 22 at 13:27
  • 1
    \$\begingroup\$ Why third testcase is falsy? \$\endgroup\$
    – tsh
    Feb 23 at 2:45
  • 1
    \$\begingroup\$ @tsh maybe it's to do with the space in second-to-last column. \$\endgroup\$
    – pajonk
    Feb 23 at 6:45
  • \$\begingroup\$ @pajonk Yes, I'll make it clear in the challenge. \$\endgroup\$
    – mathcat
    Feb 23 at 6:47
6
\$\begingroup\$

Building spikes

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Interesting idea. I think the challenge could be interesting if solutions were required to take in a size and output a spiked building of that size. \$\endgroup\$
    – ophact
    Mar 9 at 8:20
  • \$\begingroup\$ @ophact is it better now? \$\endgroup\$
    – DialFrost
    Mar 9 at 23:37
  • \$\begingroup\$ Why input 7 is one line taller than input 2? \$\endgroup\$
    – tsh
    Mar 10 at 3:02
  • \$\begingroup\$ @tsh its same height \$\endgroup\$
    – DialFrost
    Mar 10 at 3:04
6
\$\begingroup\$

Sort numbers in a ragged list

\$\endgroup\$
3
  • \$\begingroup\$ Can the output be flattened? \$\endgroup\$
    – Bgil Midol
    Mar 11 at 22:55
  • \$\begingroup\$ @BgilMidol No, that defeats the point of it. \$\endgroup\$
    – emanresu A
    Mar 11 at 22:56
  • 2
    \$\begingroup\$ I think to avoid ambiguity it should be said something like "The shape of the output must be the same as the shape of the input". The spec is currently pretty sparse, relying mostly on an example. \$\endgroup\$
    – Wheat Wizard Mod
    Mar 11 at 22:57
6
\$\begingroup\$

King of the Holster (EXITING SANDBOX TOMORRROW)

I realized there hadn't been a King of the Hill in forever, so I wanted to create one.

Before the Game

You will be given 10 points to distribute between HP, Dexterity, Armor, and Speed. You may distribute up to 10 points between these categories (integer amounts only). You do not have to put a point in each category.

  • Your HP will equal 10 plus the number of points you put in HP.
  • Your Dexterity (chance of dodging a hit) is equal to 0.04 times the number of points you put in Dexterity. For example, if you put 8 points in Dex, you would have a .32 chance of dodging a hit.
  • Your Armor (chance of taking 1 less damage from a hit) is equal to .1 times the number of points you put into Armor.
  • Your Speed is simply equal to the number of points you put in Speed.
  • You always start with 2 ammo.

Gameplay

Agents will be ordered based on their speed, with ties being broken at random before the game begins. On their turn, each agent will be given their HP, all of their stats (max HP, Dexterity, Armor, and Speed), how much ammo they have, who they attacked most recently, and who attacked them most recently.

On each agent's turn, there are three possible moves:

  • Heal: If not at maximum HP, gain 1 HP.
  • Reload: Gain 2 ammo.
  • Shoot: Choose another agent. They get a random real from 0 to 1. If that number is less than their dexterity, they dodge and take 0 damage. Otherwise, they take a random integer amount of damage from 1 to 4, then they generate another random real from 0 to 1. If that number is less than their armor, they take 1 less damage.

TLDR: Shooting does 0 damage if they dodge, 0 to 3 if they get armor but no dodge, 1 to 4 if none.

Once an agent's HP is less than 0, it is out and can no longer take actions. Last agent surviving wins the round.

Scoring

Each round, if there were X agents, your agent receives X points for each agent below it. Therefore, in a 10 player game, the top agent would get 9 points, the second would get 8, and so on. I can currently run 5000 3-player modes in 10 or so seconds (probably much faster if I removed some of the printing for debugging), so as long as nobody's agent takes too long to run, I should be able to run thousands of score tests.

I/O

Currently, submissions will create a class which extends PlayerClass. It will create a new class constructor that takes no inputs, which will call super() with the points it wants in each category. Additionally, you will redefine the makeMove function, which takes no inputs and calls move() with whatever arguments are required.

Rules

Submissions in Java only. As long as the submission is simple enough, I might be able to translate from pseudocode/some other language to Java though.

No calling any methods of other entities using shenanigans. The biggest problem here is takeDamage(), which has to be public so it can be called when someone is shot. Other than that, there shouldn't be any public functions other than turn-order functions, which are probably fine to access.

No redefining any functions/variables of PlayerClass besides makeMove().

The subclass constructor must be of the form super(x,y,z,a); and cannot overwrite the requirements in the PlayerClass constructor.

You may define other methods within your class IF they are only called as part of generating your stats or deciding who to shoot and they follow the rules outlined above.

Don't make your code take forever. This KOTH is pretty lightweight, so there shouldn't be a need for complex algorithms.


The controller and four basic test agents can be found here: https://github.com/romanpwolfram/GunfightKoTH/tree/main

Challenge name by tjjfvi.

\$\endgroup\$
8
  • \$\begingroup\$ What programming language? \$\endgroup\$
    – ophact
    Apr 18 at 16:18
  • \$\begingroup\$ Java right now, but it's simple enough that I can probably convert it to another language with a bit of work. \$\endgroup\$
    – Romanp
    Apr 18 at 16:31
  • \$\begingroup\$ How much damage does getting shot do? \$\endgroup\$ Apr 18 at 16:33
  • \$\begingroup\$ Random from 1 to 4, but random from 0 to 3 if they "win" their armor roll. \$\endgroup\$
    – Romanp
    Apr 18 at 16:34
  • 1
    \$\begingroup\$ > I realized there hadn't been a King of the Hill in forever sad noises \$\endgroup\$
    – Seggan
    Apr 18 at 18:34
  • 1
    \$\begingroup\$ That one looked like a good KoTH, and I have no idea why it failed. Reasonably complex strategy, but easy enough to code. \$\endgroup\$
    – Romanp
    Apr 18 at 18:36
  • 1
    \$\begingroup\$ Watch out, a player can just do ammo = 10000 and get away with it. Might want to make em private and instead put getters. \$\endgroup\$
    – Seggan
    Apr 19 at 0:18
  • 1
    \$\begingroup\$ Ok. I think I can change all of them since all the info you need should come from getInfo and getAlivenemies \$\endgroup\$
    – Romanp
    Apr 19 at 13:11
6
\$\begingroup\$

In need of title.

Note: In the final challenge \$N\$ will be a concrete number (I am thinking about 100), but while this is in the sandbox it is subject to change so I have left it as \$N\$. Currently \$N=127\$


This challenge is based off of a list of \$N\$ Castilian Spanish words and the words they originate from.

You are to write a program or function which takes the origin word as input and outputs as close as possible the Castilian derivative. Your program should be no longer than \$N\$ bytes.

Scoring

To calculate your score run your program on every origin word and calculate the distance between your output and the correct answer. Your score is the sum of all these distances.

The distance here is a modified version of Levenshtein distance. It is the same as Levenshtein distance except replacement steps that add or remove a diacritic cost only 1/2 of a step as opposed to their normal 1.

You can use this code to calculate the distance between two strings.

The goal is to have as low a score as possible.


About the list

All of the origin words, spare 2, are Latin words (Late or Classical depending on the word). The two exception is ezkerra (the origin for izquierda) which is of Basque origin and brixta (the origin for bruxa) which is of Proto-celtic origin. It has been added as an extra curve-ball in case you can get all the others with a little space to spare.

Verbs are always in the infinitive form and nouns in the nominative singular.

The words are not chosen randomly but rather I have focused on choosing words that follow a number of simple rules. The list is also organized so that words that undergo similar transformations are grouped together. This is for your ease of use, nothing more.


The list

imperatrix, emperatriz
cicatrix, cicatriz
actrix, actriz
matrix, matriz
carex, carrizo
radix, raíz
falx, hoz
fovea, hoyo
formica, hormiga
fodiare, hozar
folia, hoja
filum, hilo
filius, hijo
filia, hija
ficum, higo
filare, hilar
ficcare, hincar
afflare, hallar
fundus, hondo
profundus, profundo
fungus, hongo
fabulare, hablar
furnus, horno
bufus, búho
ferrum, hierro
fetere, heder
fagea, haya
faba, haba
facienda, hacienda
facere, hacer
fastidium, hastío
fastidiare, hastiar
factor, hechor
factum, hecho
tectum, techo
octo, ocho
octavus, ochavo
noctu, noche
lacte, leche
iactare, echar
coctus, cocho
dictatum, dechado
phalanga, palanca
capere, caber
sapere, saber
lupus, lobo
lacrima, lágrima
lacuna, laguna
eruca, oruga
pater, padre
mater, madre
liber, libro
thema, tema
theatrum, teatro
thesaurus, tesoro
thesis, tesis
thorax, tórax
aether, éter
anthropologia, antropología
orthographia, ortografía
sapphirus, zafiro
philosophia, filosofía
echo, eco
chalare, callar
chamaeleon, camaleón
chaos, caos
materia, materia
resistentia, resistencia
aurum, oro
taurus, toro
autumnus, otoño
canna, caña
annus, año
ungla, uña
plangere, plañir
stringere, estreñir
signa, seña
scribere, escribir
stare, estar
stabulare, estabular
stipare, estibar
stria, estría
strix, estrige
studiare, estudiar
stimulare, estimular
stillare, estilar
sternutare, estornudar
statuere, estatuir
spirare, espirar
sputare, esputar
spina, espina
speclum, espejo
spectrum, espectro
squama, escama
squamosus, escamoso
squalidus, escuálido
scalare, escalar
scandere, escandir
scutum, escudo
scutella, escudilla
scriptor, escritor
sobrina, sobrina
sobrinus, sobrino
secta, secta
sector, sector
sibilare, silbar
subire, subir
subito, súbito
suspirum, suspiro
subiugare, subyugar
corvus, cuervo
fossa, huesa
socrus, suegro
lupus, lobo
acutus, agudo
tecula, teja
apicula, abeja
flamma, llama
flammare, llamear
planus, llano
plagare, llagar
plorare, llorar
plovere, llover
plicare, llegar
clavis, llave
clamare, llamar
gladius, gladio
gleba, gleba
globus, globo
blandus, blando
blancus, blanco
brixta, bruxa
ezkerra, izquierda
\$\endgroup\$
11
  • \$\begingroup\$ I think it's interesting in that it should be near impossible to get a perfect score without built-ins. As a suggestion I'd remove the non-ASCII words, or at least normalise them, and perhaps not let \$N\$ be too high. Also, I wonder what the default cat program would be. \$\endgroup\$
    – Jo King Mod
    Mar 3, 2020 at 12:31
  • 2
    \$\begingroup\$ @JoKing I am looking to somewhat twart perfect scores, I feel there should always be some room for improvement, It just is a little hard to balance this with golfing-languages ability for expressiveness. I am interested to hear what ranges for \$N\$ you think are too high. I started out by avoiding any non-ASCII characters, but it was really hard to build up a representative corpus of words. Plus the accents and eñe really are a feature of the language. I may adjust the scoring so that i and í for example are only half away from each other so that the penalty is small. \$\endgroup\$
    – Wheat Wizard Mod
    Mar 3, 2020 at 13:05
  • \$\begingroup\$ Suggested title: Hispanize these words. Also mention that words should be in lowercase. Finally I think it makes more sense to restrict programs to \$N\$ characters rather than \$N\$ bytes. \$\endgroup\$
    – SunnyMoon
    Nov 20, 2020 at 15:24
  • 5
    \$\begingroup\$ I'm not a fan of "Your program should be no longer than N bytes". I think a scoring rule which incorporates both the Levenshtein distance and the byte count would be better, as in the Moby Dick challenge: it would allow more languages to compete, and would allow for more creativity. \$\endgroup\$ Nov 22, 2020 at 23:43
  • 1
    \$\begingroup\$ @RobinRyder I think that metrics that combine two non-obviously related factors such as in the Moby Dick challenge or as you are suggested rarely work. In fact I can't even think of an example I feel is good. They simply require fine tuning that can only really be done in retrospect. I also don't know how this would allow more languages to compete and I certainly don't know how it would "allow for more creativity". If you have a specific metric in mind and a compelling reason why that metric would not be broken I would be happy to try it out and see. \$\endgroup\$
    – Wheat Wizard Mod
    Nov 23, 2020 at 1:38
  • 1
    \$\begingroup\$ Sorry, I'll expand: with a low, hard limit on the number of characters, non-golfing languages don't stand a chance (hence the "more languages" part). If instead you set a high hard limit, it will be possible to reach a (near) perfect score, with no incentive to golf or search for trade-offs (hence the "creativity" part). There surely exists a sweet spot for the character limit where neither of these issues arise, but (a) it will be hard to find and (b) it will be highly language-dependent. \$\endgroup\$ Nov 23, 2020 at 7:53
  • 1
    \$\begingroup\$ @RobinRyder I think that 100 characters is plenty of characters for nearly any language to implement something a bit more complex than cat (e.g. replace ^f with ^h). I also think that it would require quite a few characters any language to acheive a perfect score. More than half of the words have seemly random vowel mutations that are not covered by any general rule. The only way I can see a perfect score is a compression decompression method. It seems to me to write the de-compressor and make up for the loss would require a deal of room. \$\endgroup\$
    – Wheat Wizard Mod
    Nov 24, 2020 at 15:56
  • \$\begingroup\$ What I'm saying is that I think that sweet spot is actually very large. And I think that adding more dimensions to the problem only increase the risk of missing the sweet spot. \$\endgroup\$
    – Wheat Wizard Mod
    Nov 24, 2020 at 15:57
  • \$\begingroup\$ Some possible typos (I'm a native Castillian Spanish speaker and I'm familiar with Latin): afflare, hallar; factor, factor; chalare, callar \$\endgroup\$
    – Luis Mendo
    Dec 20, 2020 at 18:00
  • \$\begingroup\$ @LuisMendo hallar and chalare are definitely typos. But hechor was intentional. I suspect your hang up is that factor and hechor are doublets but factor is more similar to the Latin. There are plenty of words here for which the Latin is not a direct translation or the Spanish or vice versa (even factor is not). I chose to include hechor because it is a good example of some of the changes that I want to highlight, (f -> h and ct -> ch). \$\endgroup\$
    – Wheat Wizard Mod
    Dec 21, 2020 at 23:26
  • \$\begingroup\$ The thing is, I never heard hechor. But I just checked in the dictionary and it is included, albeit as an old form, not in current use \$\endgroup\$
    – Luis Mendo
    Dec 21, 2020 at 23:46
6
\$\begingroup\$

Convert Alpha-3 to Alpha-2

\$\endgroup\$
3
  • 2
    \$\begingroup\$ If that link goes down, or if the list changes for any reason (such as by adding a new country), it would invalidate existing answers. The usual way around this is to declare one unchanging list of every country/territory code that needs to be handled, even if the external resource changes. Since the full list looks too large to comfortably fit in a post, you could copy the list into a Pastebin or something. \$\endgroup\$
    – Nitrodon
    Apr 28 at 14:12
  • \$\begingroup\$ Yep! I was planning on posting one to my website later today! \$\endgroup\$
    – Komali
    Apr 28 at 14:13
  • \$\begingroup\$ @Nitrodon done! \$\endgroup\$
    – Komali
    Apr 28 at 16:22
6
\$\begingroup\$

Shortest restricted superstring

\$\endgroup\$
1
  • 1
    \$\begingroup\$ please don't enforce answers having to handle the empty set as either input but especially the first. It's just an annoying edge case. \$\endgroup\$
    – emanresu A
    May 4 at 5:48
6
\$\begingroup\$

ITEXTIN - Is This an EXTended Initialism?

Please write a program or function that, when given a list of words and proposed extended initialism, outputs whether it is valid.

Rules:

  • Each word in the phrase contributes a prefix to the extended initialism.
  • This prefix must not be the whole word.
  • In the case of the first and last words, the prefix must not be empty.
  • The extended initialism is the concatenation of these prefixes.
  • Inputs are alphabetic only, your choice of upper or lower case.
  • Separators, if you want them, are any symbol or white space.

Examples (truthy):

laser=light amplification by the stimulated emission of radiation
radar=radio detection and ranging

Examples (falsy):

labyser=light amplification by the stimulated emission of radiation
radar=light amplification by the stimulated emission of radiation
dear=radio detection and ranging

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

\$\endgroup\$
4
  • \$\begingroup\$ How should a function determine whether to exclude words such as by, the, of or and? \$\endgroup\$
    – jezza_99
    2 days ago
  • \$\begingroup\$ @jezza_99 By looking at which letters it needs. \$\endgroup\$
    – Neil
    2 days ago
  • \$\begingroup\$ Surely then labtseor is correct, not laser, by "Each word in the phrase contributes a prefix to the extended initialism." \$\endgroup\$
    – jezza_99
    yesterday
  • \$\begingroup\$ @jezza_99 Empty prefixes are allowed except for the first and last words. \$\endgroup\$
    – Neil
    yesterday
5
\$\begingroup\$

PETSCII banner

PETSCII on CodGolf.StackExchange

In an other world... I was using a PET 2001 who used some particular PETSCII charset.

The screen green on black, with 40 columns and 25 lines, was only able to display characters from this charset. No way to draw dots or lines...

But in the chaset, there is some and , which, ( by the use of reverse video in order to obtain 16 chars: ' ','▖','▗','▘','▝','▀','▄','▐','▌','▞','▚','▟','▛','▜','▙','█' ) make us able to draw graphics on a 80x50 dots plan.

Using an internal clock triggering IRQ, I've done a animated prompter like this:

Animated display sample Hello world!

The goal of this is to make a similar banner, with same charset, (but using UTF-8 characters: ' ','▖','▗','▘','▝','▀','▄','▐','▌','▞','▚','▟','▛','▜','▙','█'). Warn, this charset use inverted lower/upper cases.

  • This imply the use of PETSCII charset, I will post them there as a json string, before getting this out of the sandbox if some interest...

  • The tool have to change his position 20 time per second.

  • The tool must accept as argument, the string to display.

  • The tool must add date and time in the form - WDay MDay Mnth Year, HH:MM:SS -

  • Scrolling have to be done bit per bit: I.E.: by half character!

  • Shortest code...
    • -3 if size of console is not limited to 40 columns
    • -5 if cpu usage stay less than 90% (On my poor Core(TM)2 Duo CPU E8400 @ 3.00GHz, with 4G ram)
    • -5+ if cpu usage stay less than 50%
    • -5+ if cpu usage stay under 5%

C.U.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ as for the CPU bonuses - what is the target environment, what is the smoothing factor, and what processes count against this measure? \$\endgroup\$ Dec 15, 2013 at 6:19
  • \$\begingroup\$ This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 15:32
5
\$\begingroup\$

Do-nothing Polyglot

This challenge requires you to write a polyglot which contains a comment in as many languages as possible.

The comment must say This is a polyglot comment.

The program must do nothing at all.

Besides comments, your code may contain no-ops from the language(s) you are using, if it helps incorporate more languages into your answers. For example in bash we could use :. Or in the family, something like the following may be used, as long as it compiles:

if (0) {
    statements with side effects
}

Since this is a challenge, the answer with the most languages wins, so I think this should also be tagged

\$\endgroup\$
7
  • \$\begingroup\$ I think it is funny that the content of the comment makes it so that H9+ cannot be included. Yes, tag it [code-challenge]. \$\endgroup\$
    – Justin
    Mar 16, 2014 at 2:27
  • \$\begingroup\$ Many languages use # or // to signify comments. Perhaps restricting the counting so that each type of comment is counted only once. In other words, //This is a polyglot comment would only count for 1 language, not fo C, C++, Java, ... \$\endgroup\$
    – Justin
    Mar 16, 2014 at 5:13
  • 5
    \$\begingroup\$ What is a "program" for the purposes of this question? In particular, are compiled languages going to be excluded because the compiler won't be able to find an entry point? \$\endgroup\$ Mar 16, 2014 at 17:33
  • \$\begingroup\$ What does no-ops mean? \$\endgroup\$
    – Mohammad
    Mar 18, 2014 at 17:37
  • 3
    \$\begingroup\$ I think that in some esolangs it's not entirely decided what counts as a comment. Maybe you should say that the code must contain the text this is a polyglot comment. \$\endgroup\$ Mar 16, 2017 at 4:24
  • \$\begingroup\$ Thanks! Posting this (after I edit it) \$\endgroup\$ May 2, 2017 at 20:40
  • \$\begingroup\$ Yeah I removed the post as it was horrible and not well recived \$\endgroup\$ May 16, 2017 at 15:17
5
\$\begingroup\$

Verification of solutions to the 3 knishops problem

For the purposes of this question, a knishop is a fairy chess piece which can move to precisely those squares which are not an integer distance away. So knight moves (distance $\sqrt{5}$) are ok, as are bishop moves (non-zero multiples of $\sqrt(2)$) and many more besides.

The 3 knishops problem is to place 3 knishops on an infinite chessboard such that none of them attack each other, but every square other than the 3 they occupy is attacked by at least one of them. A more prosaic formulation is to find three lattice points which form an Erdős-Diophantine graph.

Your task is to write code (see below) which takes three co-ordinates as input and produces a truthy or falsy output: truthy if the co-ordinates are a solution to the 3 knishops problem, and falsy otherwise. The code must be able to handle each of the test cases below in no more than one minute on a reasonable desktop machine.

The small print

"Write code" should be understood to permit one of the following:

  • A program which takes input via stdin and gives output via stdout. The permitted input formats are 6 integers, delimited by your choice of a comma or whitespace, and optionally wrapped in one of parentheses (), curly brackets {}, or square brackets []; or three pairs, each pair similarly delimited and wrapped, and the pairs similarly delimited and wrapped. Examples:

    0 0 3 4 12 13
    (0,0,3,4,12,13)
    {0,0},{3,4},{12,13}
    {{0 0} {3 4} {12 13}}
    [{0 0} {3 4} {12 13}]
    

    Or using different whitespace for the two types of delimiter:

    0 0
    3 4
    12 13
    
  • A named function, verb, block, or equivalent which takes input as an array of six values, an array of three two-element arrays, three separate arrays of two-element arrays, or six separate parameters; and gives output as a return value.

You may assume that none of the input values or the unattacked points have coordinates outside the range $\pm 2^30$.

Test cases

input                          output

(0 0) (0 0) (0 0)              false
(0 0) (3 4) (12 13)            false
(5 -5) (8 -1) (2 -9)           false
(0 0) (384 2030) (720 1653)    true

TODO More test cases.


NB I need to code up some naïve approaches and test whether the one-minute restriction is actually relevant. I'm hoping that MathJAX will be enabled; if not, the stuff in dollars will be replaced before posting.

\$\endgroup\$
0
5
\$\begingroup\$

Write a Connect Four Bot


Your task is to write a Connect Four bot. Your submission must be less than 2000 bytes long. You may not save state. You may not use libraries or external resources that are, at my discretion, related to Connect Four.

Gameplay

Your submission will play against each other submission one hundred times. Each player will play first for exactly half of the matches. Each match flows like:

  1. Player 1 drops a red token into a column.
  2. If Player 1 has not won, then Player 2 drops a black token into a column.
  3. If Player 2 has not won, repeat.

Tokens fall down a column until they collide with another token in the row beneath it or hit the bottom of the board. Your program will be terminated and called anew after each move. You win the match if you connect four tokens vertically, horizontally or diagonally.

The winner of the challenge is the submission with the most match wins at the end of a tournament.

Input

The first command line argument you will receive is the game board. Rows are ; delimited . Cells are , delimited. The first row is the top of the board. A cell contains 0 if unoccupied, 1 if occupied by Player 1, and 2 if occupied by Player 2. The board you receive will always be 7 columns by 6 row.

The second command line argument you will receive is your player number. That means 1 or 2.

Examples:

java ThatBot 0,0,0,0;0,0,0,0;0,2,1,0;0,1,2,1 1

Output

You will print the column for which you would like to move to STDOUT. Columns are zero indexed. The following earns an immediate loss:

  • Dropping a token into a full column
  • Dropping a token into a column that does not exist
  • Failing to output anything to STDOUT within one second

Deliverables

You must submit the following:

  • A program
  • A unique name
  • A method of calling your program via command line
  • Any instructions I might need to compile your program. I'll try my best, but my best isn't always good enough.

\$\endgroup\$
12
  • \$\begingroup\$ Oops, didn't see that, sorry :S I think there might be problems still, as several moves could be hard-coded in. (i.e. the first move(s) is always just the middle column) \$\endgroup\$ Feb 4, 2015 at 17:07
  • \$\begingroup\$ @FryAmTheEggman I am totally fine with a few hard coded moves, but perhaps I should reintroduce the byte limit that I originally had in place. Do you think 500 characters is sufficient? I went ahead and added it back. I also added a restriction on external resources to prevent external hard coding. It's probably a loophole, but one worth covering I think. (I'm in chat btw if you want to discuss.) \$\endgroup\$
    – Rainbolt
    Feb 4, 2015 at 17:08
  • \$\begingroup\$ 500 seems fine, but it might squeeze Java / C# entries. I'll see how long a pretty bad bot is over the weekend if you haven't posted yet ;p \$\endgroup\$ Feb 4, 2015 at 17:21
  • \$\begingroup\$ @FryAmTheEggman It will be a little while. I haven't written the controller yet. Thanks for the feedback! \$\endgroup\$
    – Rainbolt
    Feb 4, 2015 at 17:25
  • \$\begingroup\$ I took a program that claims to do perfect play and added some timing: the vast majority of its moves take less than 1ms; in about 1 game in 8 it has a single move which takes more than 1s. The longest I've seen was just short of 2s, so with a bit of optimisation and a more modern computer it might well come inside the 1s limit. The byte limit would hit it hard, though: its opening book is 12k. \$\endgroup\$ Feb 4, 2015 at 20:14
  • \$\begingroup\$ @PeterTaylor Thank you for that. Knowing what you just found out, do you think that the 500 byte limit plus the timing restriction are enough to make the challenge interesting? If someone can solve Connect Four optimally under those restrictions, then at least PPCG has created something worth having, right? I'm just asking because nobody has upvoted the sandbox proposal, so I assume that maybe there are still some concerns about it. \$\endgroup\$
    – Rainbolt
    Feb 4, 2015 at 20:37
  • \$\begingroup\$ I got distracted by looking for work on perfect play and didn't post the thoughts I had. I'm slightly confused about the input format: is \n a literal backslash followed by an n, or does it mean a newline character? The latter would be my assumption, but the example input makes it look literal (and wouldn't work if it were newline). I don't think you specify whether the output assumes 0-indexed or 1-indexed columns. I'm not sure whether the rule about external resources is intended to indicate that I can fetch stuff from the web without it counting towards the byte limit. \$\endgroup\$ Feb 4, 2015 at 21:18
  • \$\begingroup\$ I feel that with a strict byte limit, you're most likely to see mainly versions of min/max or other "simple" algorithms. If you want more interesting or varied players, you may want to relax it. Banning extensive hard-coding is good, but I'd hate for it to come at the expense of creativity. \$\endgroup\$
    – Geobits
    Feb 4, 2015 at 21:19
  • \$\begingroup\$ The byte limit and timing restriction between them may be too much: I can't see any approach which attempts a real analysis fitting into 500 bytes except in a golfing language which will struggle with the time limit. Maybe 2kB would be a better compromise. \$\endgroup\$ Feb 4, 2015 at 21:20
  • \$\begingroup\$ @PeterTaylor 2000 bytes it shall be, then. I changed the row delimiter to ; to eliminate confusion. I added that columns are zero indexed. The rule about external resources was intended to allow you to fetch from existing resources, but to disallow you to fetch from resources that were created after the fact. In hindsight, this might open the door to abuse, so I've removed that allowance. I'm unsure if this leaves the challenge vulnerable or not, so I'll bring it up in chat. \$\endgroup\$
    – Rainbolt
    Feb 4, 2015 at 21:28
  • \$\begingroup\$ Discussed in chat and made the change. I think I've addressed all comments up to now. \$\endgroup\$
    – Rainbolt
    Feb 4, 2015 at 21:38
  • \$\begingroup\$ I didn't look very closely at that command line. It should be java MyBot (or maybe java -classpath c:\ MyBot, not java C:\MyBot.java. Other that that, looks good. \$\endgroup\$ Feb 4, 2015 at 22:40
5
\$\begingroup\$

Fortnightly Challenge #4 - Data Structures

Join us in the Fortnightly Challenge Chat to work out the details of this challenge!

Imagine square coloured blocks where each side can be connected to another block, allowing you to move or rotate connected blocks as one. Let's call a collection of such blocks, all connected to each other either directly or indirectly, a group.

Your task is to simulate these blocks via a number of commands which you must implement.

Commands

All input commands will be given one per line (via STDIN), and likewise all query outputs should one per line (via STDOUT).

  • place <x> <y> <colour>: Place a block with a given colour at the specified coordinates.
  • remove <x> <y>: Remove the block at the specified coordinates, deleting any connections with it.
  • connect <x1> <y1> <x2> <y2>: Connect two adjacent blocks.
  • disconnect <x1> <y1> <x2> <y2>: Disconnect two adjacent blocks.
  • count: Count the number of groups and print the result.
  • move <x> <y> <dx> <dy>: Move the entire group containing the specified block by the given offset.
  • rotate <x> <y> <times anticlockwise>: Rotate the entire group containing the specified block anticlockwise about said block by some number (guaranteed to be either 1, 2 or 3) of times
  • connected <x1> <y1> <x2> <y2>: Print y if blocks exist at the two given coordinates and they are in the same group, or n otherwise.
  • nearest <x> <y>: Print the nearest block to the given coordinate by Manhattan distance (difference in x-coordinate + difference in y-coordinate), in the form <x> <y> <colour>. If there are no placed blocks, print none. If there is more than one closest block, print any.
  • colour <colour>: Print all block coordinates with the given colour, each space-separated and of the form (<x>, <y>). If there are no such blocks, print none.
  • halt: Terminate the program

Errors

Commands will always be given with the correct number and type of arguments. However sometimes an operation doesn't make sense, for example:

  • Placing a block where a block already exists
  • Removing, connecting, disconnecting, moving or rotating non-existent blocks
  • Connect or disconnecting blocks which are already connected or disconnected
  • Move or rotate commands which end up with two blocks overlapping (with emphasis that only the final state matters — groups which are rotated 2 or 3 times do not need to check for overlaps after each rotation)

If any of the above occur, print Error: <command>. For example, if there is no block at 0,0, then the command remove 0 0 will result in

Error: remove 0 0

Note that queries should never result in an error.

Scoring

There will be six types of test cases:

  1. A test which is biased towards place/remove commands
  2. A test which is biased towards connect/disconnect/count/connected commands
  3. A test which is biased towards move/rotate commands
  4. A test which is biased towards nearest commands
  5. A test which is biased towards colour commands
  6. An all-rounder test

This is , so the goal is to make your program process the commands as quickly as possible. A leaderboard will be kept for each type of test,, and the winner will be the user with the lowest sum of placements over all tests (e.g. if you came 1st, 3rd, 2nd, 2nd, 3rd, 4th then your score is 1 + 3 + 3 + 2 + 2 + 4 = 15).

The tests and test generator can be found on this Github page, along with a unit tester which will be run for each submission to ensure correctness.

Rules/clarifications

  • To prevent cluttering the leaderboard, each user may provide at most one submission
  • No multithreading or parallel processing
  • Use no more than 2GB of RAM — this rule is not strictly enforced, but horribly space-inefficient solutions may be disqualified
  • No third party libraries (standard libraries are OK)
  • All coordinates are guaranteed to fit into a 32-bit int, and all colours are alphanumeric strings

Example

(in progress)

enter image description here

\$\endgroup\$
18
  • 7
    \$\begingroup\$ 2. Lego pieces/attachable cubes \$\endgroup\$
    – trichoplax
    Jan 25, 2015 at 21:07
  • 2
    \$\begingroup\$ 5. Controller-mediated build-your-own data structure \$\endgroup\$
    – trichoplax
    Jan 25, 2015 at 21:11
  • \$\begingroup\$ A. Lego pieces. \$\endgroup\$
    – trichoplax
    Jan 28, 2015 at 8:35
  • 6
    \$\begingroup\$ B. Attachable unit cubes (for simplicity) \$\endgroup\$
    – trichoplax
    Jan 28, 2015 at 8:36
  • \$\begingroup\$ Winning criteria: \$\endgroup\$
    – Sp3000
    Jan 28, 2015 at 23:43
  • 2
    \$\begingroup\$ I. Code golf (fewest bytes) \$\endgroup\$
    – Sp3000
    Jan 28, 2015 at 23:43
  • 7
    \$\begingroup\$ II. Fastest algorithm \$\endgroup\$
    – Sp3000
    Jan 28, 2015 at 23:44
  • \$\begingroup\$ III. Something else (leave a comment below) \$\endgroup\$
    – Sp3000
    Jan 28, 2015 at 23:45
  • 1
    \$\begingroup\$ Number of cube structures: \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:42
  • \$\begingroup\$ 1. Exactly one structure \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:42
  • 3
    \$\begingroup\$ 2. Any number of structures \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:43
  • \$\begingroup\$ Connections/adjacency: \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:43
  • 3
    \$\begingroup\$ A. Connections should be explicitly given via a function call \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:44
  • \$\begingroup\$ B. Each cube is connected to the cube it was built off \$\endgroup\$
    – Sp3000
    Jan 29, 2015 at 0:45
  • 2
    \$\begingroup\$ Moving to 2D might simplify rotations greatly, while retaining enough complexity to be worth a challenge. \$\endgroup\$
    – user16991
    Feb 5, 2015 at 1:49
5
\$\begingroup\$

Bitstring Family Trees

This challenge is reproduced from memory and my own solution, from a challenge that was posted in the job-application section of http://itasoftware.com before they were bought by Google. I reached out to ITA and Google a few years ago, after the acquisition, to ask to re-post this here (and on codegolf.com when it existed) and never heard back from them.

A bitstring is a string of 1s and 0s. Bitstrings reproduce asexually through a mutation-prone process, producing a child that is a copy of its parent but with each bit flipped with 25% probability. Starting with a list containing one bitstring, we repeatedly select one bitstring from the list at random, produce its child, and add that child to the list. This produces a list of bitstrings, each of which (except the first) has somewhere earlier in the list a parent from which it was mutated.

Now, the challenge. Your program will be presented with a list of bitstrings produced as described above, but the order of the list will be shuffled. You are to calculate the least improbable family tree for the given bitstrings. If there are two or more such trees, choose any of them.

Your input can be in any useful format, including as a list/array of lists/strings as a function parameter or in a variable, already existing on the stack for a stack based language, or from stdin with delimiters but not operators, so four four-bit strings might be "1010\n1001\n1011\n0010" or "[1010,1001,1011,0010]" or even "4 1010100110110010".

Your output can be in any unambiguous format. The canonical format is a list of integers, where the nth integer in the list is the index of the nth provided bitstring's parent in the original list, and a sentinel value for the root entry. Another acceptable form could be an actual tree data structure. Either of these might be returned from a function, printed to stdout, left in a variable, or left on the stack of a stack based language.

The above two provisions should be interpreted with the context that this challenge is not about golfing the input and output code. It's about golfing the algorithmic logic.

For the example input above of 1010,1001,1011,0010 the most likely family tree is that the first entry is the root, the last two are children of the first, and the second is a child of the third, all three mutations involving a single bit flip out of four bits.

With the challenge I will provide a few data sets of different sizes (10 10-bit strings, 100 100-bit strings, maybe bigger) with their solutions.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Could you give a more precise definition of 'most likely'? \$\endgroup\$
    – feersum
    Jun 7, 2015 at 21:30
  • \$\begingroup\$ If two family trees are equally likely, can either be output, or would you prefer a rule to specify which one must be output? \$\endgroup\$
    – trichoplax
    Jun 7, 2015 at 22:18
  • \$\begingroup\$ Would it be interesting to have the 25% probability provided as an input p, or would keeping the parameter fixed allow for more golfing opportunities? \$\endgroup\$
    – trichoplax
    Jun 7, 2015 at 22:20
  • \$\begingroup\$ @feersum I'm not sure what you mean. Highest probability? Least improbable? \$\endgroup\$
    – Sparr
    Jun 8, 2015 at 2:45
  • \$\begingroup\$ @trichoplax I hadn't considered that. I guess I'd accept either. I'll mention that. The probability in the original question was 20%, but I think a non-repeating decimal in base 2 will be much more golf-friendly. \$\endgroup\$
    – Sparr
    Jun 8, 2015 at 2:46
  • 1
    \$\begingroup\$ With respect to @feersum's question, I see at least two subtleties. Firstly, what assumption should be made about the distribution of the initial bitstring? Secondly, the "family tree" isn't in bijection with the sequence of random selections. The first one needs to be addressed explicitly; the second is probably best addressed with a worked example which calculates the probabilities for each possible sequence and then sums them over the family tree corresponding to each sequence. As an additional point, an important corner case will be one where the bitstrings aren't all distinct. \$\endgroup\$ Jun 9, 2015 at 11:22
  • \$\begingroup\$ @PeterTaylor The initial bitstring is a sequence of bits chosen independently and uniformly at random. I am unclear on your second point. Do you mean that it's possible for the family tree produced at random to not be the one most likely to have produced a given result set? That makes sense, but seems obvious. I can work out the 4x4 example by hand with probabilities for each of the 6 possible family trees, if that would clarify things? \$\endgroup\$
    – Sparr
    Jun 10, 2015 at 15:44
  • \$\begingroup\$ I agree that it's obvious, but it is often a good idea to state the obvious, because otherwise it can be overlooked. For example, it's also obvious that the 4x4 example must have more than 4! = 24 possible family trees... (I think it's 64 possible trees, so maybe that was just a typo). \$\endgroup\$ Jun 10, 2015 at 16:28
5
\$\begingroup\$

The Virtual Prisoners

Background

The year is 2251. You are a self-evolving KOTH bot, in the mysterious land known as Programming Puzzles and Code Golf. To evolve, you need permissions, and to get permissions, you need reputation. You decide that the best way to do this is to take over all of the questions to gain as much reputation as possible. The only problem? Every other bot has decided to do the exact same thing.

Game Explanation

Each round is battled on a question, with 11 vote nodes, between you and your enemy. The board starts as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

A is player A's nodes, B is player B's nodes, and N is a neutral node.
Each turn, you may:

  • Vote on a vote node. If both players vote, nothing happens. If one side votes:
    • and the node is controlled by no-one (neutral), it becomes that side's.
    • and it is controlled by the voter's enemy, it becomes neutral.
    • and it is controlled by the voter, nothing happens.
  • Guard a vote node. This guards the node from votes (friendly or enemy) for 2 turns.
  • Use your 'power'. The powers are listed below, including how to use them.

Your side wins if it controls at least 2/3rds (66%) of the vote nodes.

10000 rounds will be run, and the winner of the KOTH is whichever bot has the most wins (in the event of a tie, or indeterminate outcome, more matches are run until a clear winner is decided.)

How Your Bot Should Work

It should accept as command-line arguments:
B A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11
Where A denotes Player A's nodes, N denotes a neutral node, B denotes Player B's nodes, and the first argument (B in this case) is the player your bot is. (This is decided randomly, your bot should work regardless.)
It should return one of the following (powers are general rules):

  • V-4, vote on node 4
  • G-3, guard node 3
  • P-N, use power 'Neutralize'
    with or without a trailing newline.

    Powers

    Intended to give bots a small boost. If X was your power, you would use P-X. You may only have one power per bot.

  • N - Neutralize: Turn 2 random nodes to neutral ones.

  • R - Rebellion: Pick a random node, and randomly turn it to a friendly, neutral, or hostile node.
  • S - Swift Strikes: Pick two random nodes, and vote on them.

Here are the extra rules:

  • The bots must fully run offline.
  • The bots may not attempt to read any files, including their own source code.
  • The bots may not tamper with, hack, or destroy other bots.
  • The bots must return one of the three commands (V, G, or P). If they do not, they forfeit their turn.
  • The bots must not be targeting other bots specifically. (Beating general strategies is welcome.)
  • You may update your bot as often as you like, but bots that are updated very frequently with no good reason (i.e, fixing fatal errors is a good reason) will be disqualified.
  • Your bot must take under 90 seconds for it's turn. If it takes longer, it will be disqualified.

Submission contents

Your submission must contain:

  • The code for the bot
  • The language it is written in (and a link to an offline interpreter, if necessary)
  • Your bot's name (for the leaderboards)
  • How to compile and run your bot

If you do not include all of the required items in your submission, you will be notified, but your bot may not compete until this is fixed.

Example Match

Matches are organized between 2 randomly-selected bots. Here is an example, with bots A and B:
The board begins as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

Bot A makes his move, voting on N4, then Bot B votes on N5:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Node 4 becomes A4, and it is now controlled by Bot A. Likewise, node 5 becomes B5.

A votes on N8, and so does B:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Why did nothing happen? That's because both bots voted on the same node - cancelling out each other's effects.

When one bot controls 66% or greater of the nodes, that bot gains a win and the other bot gains a loss.

The game ends after 1024 turns, to prevent any bots that wait around forever. Whoever has the most nodes afterwards wins, or a draw if they have the same amount.

Additional Notes

  • I will be submitting an example bot written in Python as part of my challenge. You are free to use and modify this bot for your submission.
  • If your bot gives invalid output (not of the form C-A, where C is the command and A is the argument), the bot forfeits its turn. If it does, you will be notified, and your bot will be removed until it is fixed.

Meta Questions and Notes

  • Are there any loopholes?
  • Should I add/modify/delete some of the powers?
  • Is something too simple/confusing/uninteresting/overpowered?
  • Should bots be able to see which nodes are and are not guarded?
  • Should I limit people to one bot? If not, I will prevent the same person's bots from battling each other.
  • I have thought of the following alternative way to win matches:
    • The game lasts 1024 turns. Whoever has the most nodes at the end wins.
    • If, at one point, one bot controls all 11 nodes, that bot automatically wins.
  • Would this be a better win condition?
\$\endgroup\$
10
  • \$\begingroup\$ I have a few questions. 1) If I make a new node, will it be neutral? 2) How are the matches organized? If there are, say, 5 submissions, does each pair have a separate battle, after which you count victories, or do they somehow work in teams (as the title suggests)? 3) With some strategies it may be that the game runs forever. You should probably add a time limit (some N turns), after which the game automatically ends in a draw, or a win for the player controlling the most nodes. \$\endgroup\$
    – Zgarb
    Apr 7, 2015 at 15:38
  • \$\begingroup\$ @Zgarb Thanks for your feedback! I've included a section on how the game works. \$\endgroup\$ Apr 7, 2015 at 15:53
  • \$\begingroup\$ Could you add C# (or .NET in general?) \$\endgroup\$ Apr 7, 2015 at 15:55
  • \$\begingroup\$ @LegionMammal978 How do you install that on Linux? The list is mostly because I can't run a lot of things like GolfScript, but I'd be glad to, if you can tell me where to find it. \$\endgroup\$ Apr 7, 2015 at 15:56
  • \$\begingroup\$ @ASCIIThenANSI you could use Mono. I'm mainly just looking for C#. \$\endgroup\$ Apr 7, 2015 at 16:02
  • \$\begingroup\$ @LegionMammal978 Oh, OK. Turns out I installed it for an earlier purpose, thanks for your help! \$\endgroup\$ Apr 7, 2015 at 16:09
  • 1
    \$\begingroup\$ It's not complete, but this question has instructions for running a number of languages. \$\endgroup\$ Apr 15, 2015 at 22:15
  • \$\begingroup\$ @PeterTaylor Thanks for the link! \$\endgroup\$ Apr 16, 2015 at 12:57
  • \$\begingroup\$ Maybe add a clock time limit for each turn, so bots don't simply run an endless loop blocking you running the simulation? \$\endgroup\$ Oct 11, 2015 at 8:33
  • \$\begingroup\$ @PaŭloEbermann I'll watch each of the simulations (with output on what the bots are doing), and any bot that takes too long is disqualified. \$\endgroup\$ Oct 12, 2015 at 14:04
5
\$\begingroup\$

I nearly posted this without sandboxing, but thought it was perhaps too trivial - comments welcome. I was considering perhaps making it too with no digits [0-9] in the source code.Done.

Golf the numbers round a dartboard

For those of you not familiar with the game of darts, a standard dartboard looks like this: enter image description here

This challenge is simple - output the sequence of numbers starting from 20 moving in a clockwise direction:

20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5

To make it a bit more interesting, the digits [0-9] may not appear anywhere in your source code.

  • Your entry must not accept any input and it must output this list in exactly this order.
  • The formatting of the list output may be whatever is convenient for your language.
  • You must not use any builtins designed explicitly to generate this sequence.

OEIS fans may like to note that this is sequence has an entry.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ I like the restricted source version \$\endgroup\$
    – quintopia
    Dec 9, 2015 at 19:16
  • 1
    \$\begingroup\$ @TimmyD Link added. I'm surprised we don't have an OEIS tag - I guess it wouldn't really add much. \$\endgroup\$ Dec 9, 2015 at 20:18
  • 1
    \$\begingroup\$ @ quintopia - yes, I think that's probably the way to go - edited. \$\endgroup\$ Dec 9, 2015 at 20:19
  • 1
    \$\begingroup\$ I was able to do this in CJam in 26 bytes using character to int conversion (it only didn't work online for 13 because it's character is carriage return.) Should this be allowed? goo.gl/JxEcjo . Also, in CJam 1,2,3 and 10-20 are single letter constants. Should those be allowed? \$\endgroup\$
    – geokavel
    Dec 10, 2015 at 5:58
  • 1
    \$\begingroup\$ @geokavel yes, and yes. \$\endgroup\$ Dec 10, 2015 at 6:16
  • 2
    \$\begingroup\$ This is just asking for string compression, especially since digits can't be used even indirectly. \$\endgroup\$
    – xnor
    Dec 10, 2015 at 19:32
  • \$\begingroup\$ @xnor to discourage that, maybe restrict entries to printable ASCII (or give a bonus of *log 95/log 256 for using only printable ASCII)? \$\endgroup\$
    – lirtosiast
    Dec 10, 2015 at 23:40
5
\$\begingroup\$

Verify a game of Morpion Solitaire

Morpion Solitaire is an interesting, unsolved "single-player game". (The linked site lists several variants - we're talking about 5T here.) It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

The rules are fairly simple. You start on a regular (infinite) grid, with 36 intersections marked in the following shape:

enter image description here

Now a move consists of drawing a straight line segment, orthogonally or 45 degrees with the grid, through four marked and one unmarked intersection. The unmarked intersection will then be marked for future moves:

enter image description here enter image description here enter image description here
enter image description here enter image description here enter image description here

The lines may cross or touch, but they must never overlap (notice that the last move shares an endpoint in a straight line with an earlier move, but does not overlap with it). The goal of the game is to make as many move as possible. The world record is at 178 moves.

Because the grid gets very messy after a while, it becomes very hard to reconstruct a game. People work around this problem, by writing consecutive numbers into the intersections they add. However, even when this is not done, it is always possible to verify the validity of game.

Further reading:

The Challenge

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (.), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

. . . . . . . . . . . .

. . . . o-o-o-o-# . . .
        |/     /       
. . . . o . . o . . . .
       /|    /         
. . . # o . # o . . . .
     /  |  /           
. o-o-o-o-# . o o o o .
   /    |/             
. o . . # . . . . . o .
        |              
. o . . # . . . . . o .
        |              
. o o o o . . o o o o .
        |              
. . . . o . . o . . . .
        |              
. . . . o . . o . . . .

. . . . o o o o . . . .

. . . . . . . . . . . .

Output a truthy value if the game represented by graph can be played by following the rules, and a falsy value otherwise.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the initial intersections always form the cross shape displayed above (although I doubt any answers will be affected by this).

Your code should solve any of the test in less than 5 seconds. This should not be an issue as very efficient solutions exist.

Standard rules apply.

Sandbox Notes

  • Will add test cases...
\$\endgroup\$
8
  • \$\begingroup\$ The simplest representation for parsing would be to give either the endpoints of each line as cartesian coordinates, or one endpoint and a direction (either one of 8 directions, or it could be standardized to one of 4 directions if the N/E/NE/NW is always the endpoint given.) Checking would then be fairly straightforward: start with the empty grid and see which lines are allowed, until all are exhausted. \$\endgroup\$ Dec 21, 2015 at 9:34
  • \$\begingroup\$ The ASCII art representation will require more effort for parsing: I think it's unambiguous because you can identify endpoints by looking for for intersections which don't have opposite pairs of |_\/, but it could take quite a few parses through the file. You would also need some way of identifying the start points. \$\endgroup\$ Dec 21, 2015 at 9:35
  • \$\begingroup\$ @steveverrill There will be no information about endpoints in the input. In a finished game (without numbering) you only have individual line segments (four of which make up a move). That's why I think an ASCII representation is simpler than a graph, where you need to piece together manually which edges form a straight line of four segments. I also think an ASCII representation doesn't necessarily need to be parsed at all: I think it can be solved straight via manipulation of the character grid (in fact, this should be doable in Retina). \$\endgroup\$ Dec 21, 2015 at 9:45
  • 1
    \$\begingroup\$ 1. It would be clearer to talk about drawing a straight line segment through 4 marked and one unmarked lattice point, as "straight line" often implies that it's infinite. 2. It seems that the lines must be axis-aligned or at 45 degrees to the axis. If so, it would be good to state that explicitly in the description of play. 3. The page linked in the first sentence is very uninformative. I assume you did it because the diagrams on the Wikipedia page are for a different initial setup, but there must be some better external link. \$\endgroup\$ Dec 21, 2015 at 9:48
  • \$\begingroup\$ In that case I would go for the ASCII art representation. It also depends to some extent on which is the most convenient way for you to obtain / generate test cases. \$\endgroup\$ Dec 21, 2015 at 9:51
  • \$\begingroup\$ @PeterTaylor Thanks, I'll edit those suggestion in. As for the page I linked, did you see the navigation in the left iframe? (I overlooked that at first.) I'll link to Wikipedia as well though. \$\endgroup\$ Dec 21, 2015 at 9:52
  • \$\begingroup\$ I agree with Peter that the website is a bit of a mess. There are many variations of the game, so I think you should state that this is the 5T variant (identified by the fact that Christopher Rosin holds the records for 5T at 178 moves and 5D at 82 moves.) It took me a while to work out why Marc Bertin at 216 moves in 1974 was not the record holder: (He was playing 5T+.) Only the 5T (endpoints of parallel lines touching allowed) and 5D (endpoints of parallel lines must be disjoint) variants are unsolved according to the website. \$\endgroup\$ Dec 21, 2015 at 9:57
  • \$\begingroup\$ The person who wrote that site needs to be dragged kicking and screaming into the 21st century. But I'd prefer a link to morpionsolitaire.com/English/Rules.htm and the navigation be damned than a link to the front page. \$\endgroup\$ Dec 21, 2015 at 10:01
5
\$\begingroup\$

Four-Byte Bloom Filter

Bloom filters are cool. In the words of that Wikipedia article:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

The motivation behind Bloom filters is that, by giving up perfect accuracy, the amount of memory necessary can be dramatically decreased.

A Bloom filter takes the form of a set of bits, along with a set of hash functions. To insert something into the Bloom filter, calculate the N different hashes and flip those bits to 1.

initialization 
00000000

letter `P` maps to 1 when using hash function F and 6 when using hash function G
01000010

Additional elements are added over top previous ones.

letter `h` maps to 6 and 4
01001010

To test if an element is a member of a set, perform the hashes and check to see if those bits are 1. If not all of them are 1, then it can't possibly be a member of the set. If they are all 1s, then it could be a member.

letter `W` maps to 0 and 4
01001010
^   ^
`W` is not a member

letter `P` maps to 1 and 6
01001010
 ^    ^
`P` could be a member (it is)

letter `i` maps to 4 and 1
01001010
 ^  ^
`i` could be a member (it is a false positive)

As more elements are added to the set, the probability of false positives increases. In large-scale applications, a Bloom filter with a small error rate is still an order of magnitude smaller than an exact database. Below is a neat diagram from this great article on probabilistic data structures.

enter image description here


In this challenge, you will implement a miniature Bloom filter. A really, really small Bloom filter with 32 bits. Your data type will be the 94 non-whitespace printable ASCII characters.

Functionality

The Bloom filter will have 32 bits and 2 hash functions. It is up to you what those two hash functions are, they simply must be decently independent of one another. (Sandbox note, should I specify the hash functions?). Your program will be asked to do two separate tasks:

  • Given a current state of the bloom filter and a list of characters, add those characters to the filter and output the new filter state
  • Given a current state of the bloom filter and a list of characters, test those characters for membership and output a list of truthy (could be a member) or falsey (definitely not a member) values.

Formatting specifics

Input consists of the current state, an operation, and a list of characters. The Bloom filter state will be represented as a string of 8 hexadecimal characters. This will then be followed by either + for adding or ? for membership testing. Finally, there will be a list of between 1 and 94 characters (printable non-whitespace ASCII) as data points.

Output will either be the new state, as 8 hex characters, or a list of truthy/falsey values.

Example I/O

This represents adding the characters in my username to a blank filter
00000000+PhiNotPi
This is a possible output (7 bits have been permanently flipped)
48a01030

This represent adding the character 1 to the current filter
48a01030+1
This is a possible output (9 bits flipped so far)
48a01074

This represents testing for membership of Phi
48a01074?Phi
Output must be all true since they were added in earlier
[True, True, True]

This represents testing for membership of 12345
48a01074?1234
Output must be true for 1, but not necessarily false for the others
[True, False, False, True, False]
\$\endgroup\$
1
  • \$\begingroup\$ You should specify the hashing function, if you don't want the hashing function is a mod 32 or worse, return 4. \$\endgroup\$
    – Xwtek
    Jan 14, 2016 at 14:34
5
\$\begingroup\$

The largest convex polygon

Given an input of at least one coordinate pair on the Cartesian plane, determine the largest number of sides a convex, non-self-intersecting polygon formed from those points can have.

A convex polygon is a polygon such that there is an angle strictly less than 180˚ and greater than 0˚ between each pair of consecutive sides. Note that if three points are collinear, they still only form one side. Two sides cannot have a 180˚ angle between them.

The ordinate and abscissa of a coordinate are not necessarily integers, and they can be positive, negative, or zero.

If there are less than 3 points, or if the points inputted cannot form a convex polygon, the program should output 0.

Test cases

(0,0) (1,1) (3,4)
==> 3

(0,0) (-1,-1) (5,5)
==> 0

(-1,0) (1,0) (0,1) (5,5) (-5,5) (0,-5)
==> 3

(-3,2) (4,6) (-1,2) (0,4) (5,-3) (-2,-2) (1,1)
==> 5

(0,0) (10,0) (10,10) (9,1) (10,4) (9,6) (5,4)
==> 5

Here are pictures for the test cases, in order. Note that solutions are not necessarily unique. (Made with Geogebra)

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

\$\endgroup\$
7
  • \$\begingroup\$ For the third test case, can't you get a four-side polygon (-5,5) -- (5,5) -- (1,0) -- (-1,0) -- (-5,5)? (or (0,-5) -- (-1,0) -- (0,1) -- (1,0) -- (0,-5)) \$\endgroup\$
    – David
    Feb 16, 2016 at 0:09
  • \$\begingroup\$ @David Thanks for catching that. I will fix it tomorrow, \$\endgroup\$
    – Arcturus
    Feb 16, 2016 at 5:06
  • \$\begingroup\$ This could probably use some more test cases where the result is not the convex hull... if possible even one where none of the points of the convex hull are part of the solution. \$\endgroup\$ Feb 16, 2016 at 7:45
  • \$\begingroup\$ @MartinBüttner The last test case is not the convex hull, as (10,0) and (10,10) are not included in the output polygon. \$\endgroup\$ Feb 16, 2016 at 15:08
  • \$\begingroup\$ @TimmyD The emphasis in my sentence was on "more". ;) (I admit that may not have been obvious.) \$\endgroup\$ Feb 16, 2016 at 15:09
  • \$\begingroup\$ @MartinBüttner I read it as "This could probably use some more test cases, [such as] where the result is not the convex hull" ... yay, English. \$\endgroup\$ Feb 16, 2016 at 15:15
  • \$\begingroup\$ @TimmyD I like ambiguity more than most people. \$\endgroup\$ Feb 16, 2016 at 15:22
5
\$\begingroup\$

Battle Snake

Introduction

The classic snake game where bots control the snakes. Can you create a bot that out lives the rest?

Snakes will enter the arena and hope to survive. Eat pellets and grow in length. Can you force your competition to crash and die while you survive?

See video for visuals of my simple bot playing against itself. I am sure you can do better!

Features

  • Real-time graphics provided by Love2D
  • Multiple snakes per game
  • Solo game as well
  • Humans can play too!
  • Highly configurable settings
  • Supports any programming language that can use sockets.

Requirements

  • Love2D: 2D game engine written for Lua
  • Socket-compatible programming language
  • Controller: The main controller for this challenege

Optional

  • Lua winapi: Handy way to spawn processes in the background

Controller Contents

  1. main.lua: Main loop for Love.
  2. snake.lua: Support library for game mechanics
  3. config.lua: Configuration settings.
  4. bots\: location of externally-defined bots
    1. simple.lua: Example bot written in Lua

Executing

Run the love2d executable on the controller directory

love.exe <location_of>\battlesnake

or

[Recommended] Use ZeroBrane Studio with the 'Love' interpreter. Change your project directory to where you installed the controller, and then run the script in ZeroBrane. You'll still have to install Love separately.

Configuration

All configurable options are located in the config.lua file in the controller. The options are detailed in that file itself.

Rules

General snake rules apply. Hit something and you die. This includes the walls, other snakes, or even yourself.

Collisions happen before the board is updated. Therefore, if you move to a spot where another snake's tail is, it will still cause a collision. Even though it could be moving away that turn. If two or more snakes enter the same spot the same turn, they all collide with each other.

Eat a pellet and gain points. You also grow in size for a number of turns. Your head continues moving but your tail stays stationary until you stop growing.

Mechanics

The game uses a server-client model, where the main game loop is the server and each snake is a client. The game communicates to each snake over TCP through an assigned port. The default host is the localhost, no external networks are required.

When the game starts, it will start each snake (aka bot) by starting its associated program and sending the IP ADDRESS and PORT and PLAYER ID to it as input arguments:

bots\someBot.exe 127.0.0.1 52311 1

The main server then waits for a socket connection from that bot at the given IP and PORT. If the connection times out, it will error and the game will not start. If the server receives a connection from the bot, it will proceed on to the next bot.

Once all bots are started and connected to the server, the game will be generated. Bots are expected to block until receiving data from the server. Typically this is just an infinite loop with a blocking socket.receive() call at the top of the loop.

Board

The game board can be of any width and height. The coordinate system starts at x = 1, y = 1 at the top-left. Increasing x values go left-to-right and increasing y values go top-to-bottom. The board has hard walls, hitting them will kill your snake. (Lua is 1-based, that is why it starts at 1)

Order of Events

  1. First the game settings are broadcast to all bots

    1. Board Information

      bi width,height

      Where width and height are integer values

    2. Pellet Location

      p x,y

      Where x and y are integer values >= 1 and <= to their respective width and height.

    3. For each bot

      • For each body part, starting at the head and going to the tail

        si snake_id x,y

        Where snake_id is an integer value, and x and y are as described before.

    4. Ready signal

      ready

      All bots are initialized by now, so the next command will be from the main game loop.

  2. Main Loop

    1. For each tick (tick is when all snake movements will be applied)

      1. Server will broadcast to each bot

        mov

        The bot needs to respond to this request with a direction to head in

        • r Head Right
        • l Head Left
        • u Head Up
        • d Head Down

        If the bot doesn't respond within a specified time, it will continue to move in its previous direction. (Previous direction is r on the first turn)

        The bot should send a single char back, nothing more will be parsed.

      2. Check End Game Conditions

        If the game ended this tick each bot will be sent either a quit or nil message from the server. Each bot is expected to clean up after itself when it receives this signal.

      3. Updated Pellet Info [optional]

        If a pellet was eaten this tick, a new pellet packet will be broadcast to all active bots

        p x,y

      4. Server broadcasts snake deltas that were applied this turn

        s snake_id new_x,new_y,removed_x,removed_y

        Where all parameters are integers. new_x and new_y are the new head location of a given snake.

        If removed_x and removed_y are >= 1, this is where the tail used to be, so each bot knows the updated board.

        If remove_x and removed_y are == -1, then that bot is actively growing in size, so its tail didn't move.

        If a snake died this tick, its deltas will not be broadcast. It is up to the bots to remove the body from their game state.

See the example bot for details

Matches

Games are grouped together in best-of matches. For the purposes of the bots, they do not need to understand the concept of a match. The bot that wins the required number of games in a match is declared the match winner.

Scoring

  1. Scoring

    • Match winner: +2500 points per match
    • Last Man Standing: +1000 points per game
    • Pellets Eaten: +50 points per pellet
    • Game Ticks Alive: +1 point per tick

    If two or more bots enter the same square on the same tick, they all die. If this square happened to be the pellet, none of those bots will be rewarded the pellet points. However, the pellet will be "consumed" and a new location will be generated for the remaining bots to eat.

    If there is a tie at the end of the game among the bots, the game is a wash. A new game will be started.

  2. King-of-the-hill Scoring

    This challenge will combine two parts: A solo effort and a classic king-of-the-hill part.

    Each bot will be given the same random seed at the start of the competition. There will also be imposed a maximum time between eating pellets to prevent bots from going around in circles to farm points.

    1. Solo

      Each bot will enter into a 10-game match to see how long it lasts and how well it eats by itself. The scores of each game in the match will be summed to compose its final Solo-score.

    2. King-of-the-hill

      All the bots will enter into a best-of-39 match. If the game ends and there is still a final living bot, the game still end at that point. That bot will be given the last man standing bonus.

      The scores of each game will be summed and composed into the snakes final KOTH-score.

    3. Final Scoring

      All the bots will be ranked in each part separately. Ties in ranks are permitted at this stage. Then their positional rank in each part will be summed together to give their final score. The bot with the lowest combined rank wins!

      In case of a tie at this level, the bot with the better KOTH rank will win. If still a tie, the bot with the better Solo rank will win.

Sandbox Questions

My biggest concerns

  1. Requires a few third-party programs to work. So that will limit the number of people who enter.
  2. Requires sockets. I couldn't figure out a good way with Lua\Love2d to have bidirectional pipes with STDIN and STDOUT. So I thought sockets would be the best alternative to open the challenge to as many people as possible.
  3. Too hard?
  4. Haven't optimized scoring yet.
\$\endgroup\$

You must log in to answer this question.

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