495
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

| |
\$\endgroup\$

3001 Answers 3001

6
\$\begingroup\$

my first post on here, be gentle ;)


Find all anagrams within a text

Somehow I stumbled upon an implementation of a school assignment from about a year ago, and after having seen many amazing and mindblowing code-golf solutions on here, I thought it's time I bring my own challenge and see how much you guys can blow my mind again ;)

The assignment

Given a text, find all words that have at least one other word in the text as an anagram (case insensitive). Multiple occurrences of the same word are not counted.

The output shall be grouped by words that are an anagram of each other.

Rules

  • How you handle input/output is up to you. Function-parameters, file-io, standard in/out, whatever works the best for you.
  • You must be able handle any non-empty input as long as you don't run into language or memory limitations.
  • The output does not have any fixed formatting. That means you may put them each group at a line, or put them all at one line but use different delimiters, a 2d array, some other exotic data-structure your language of choice happens to have, as long as it makes reasonable sense, it is considered correct. (This means that for example if you are just writing a function, that function does not need to display the output, it could just provide it as a return-value.) Just keep in mind the requirement that the words that are an anagram of each other should be grouped together.
  • The order in which the output appears does not matter. That applies to the order of the groups as well as the order of the words within the group.
  • A group of only one word is invalid, since that fails the "have at least one other word in the text as an anagram" requirement. (just omit them from your output ^^)
  • Each word should only appear once in the output
  • All interpunction characters are stripped away from the word before checking for anagrams. That means that "it's" and "its" are the same word (and thus both are an anagram of "sit"). My sample program at the bottom uses http://en.cppreference.com/w/cpp/string/byte/ispunct as check if a character is an interpuntion character. If your language has such a method, you may use it. Otherwise take the characters from the default C locale as specified on there:

    !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

  • All other characters are part of the word and treated as is, so "a" and "á" are not the same.

Example

Given the following input text (the actual text I was given as example by school :P, no idea where this text is coming from...)

Parts of the world have sunlight for close to 24 hours during summer. Dan went to the north pole to lead an expedition during summer. He had a strap on his head to identify himself as the leader. Dan had to deal with the sun never going down for 42 consecutive days and his leadership strap soon became a blindfold. He wondered what kind of traps lay ahead of him.

the following output would be correct:

  • 24, 42
  • deal, lead
  • and, dan
  • parts, strap, traps

Or this would also be correct:

24, 42 | deal, lead | and, dan | parts, strap, traps

This one would not

24, 42 , deal, lead , and, dan , parts, strap, traps

(since the groups are not obvious)

My own (non golfed) version to check

The is the exact program I submitted to school back then. You may use it to check your own results.

Added bonus: If it happens to be that this program has a bug (I haven't found them yet) your submission is allowed to have it as well, since it is used to check the result. (In that case you are of course not required to have said bugs)

#include <string>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <algorithm>
#include <cstring>

void stringRemoveInterpunction(std::string& string);
void stringToLower(std::string& string);
std::string stringToAnagramIdentifier(std::string word);

/**
 * due to use of std::ispunct and std::tolower it may not work for text with non-ascii characters??!
 */
int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cerr << "usage: " << argv[0] << " <filename>" << std::endl;
        return 1;
    }

    std::ifstream fileStream(argv[1]);
    if (!fileStream) {
        std::cerr << "Could not open file " << argv[1] << std::endl;
        return 2;
    }

    // map to store the anagrams, key is so called "anagram identifier", value is a list of the words.
    std::map<std::string, std::set<std::string>> anagrams;

    // read words separated by whitespace from the file
    for (std::string word; fileStream >> word;) {
        // remove interpunction & convert to lowercase, since casing should be ignored
        stringRemoveInterpunction(word); stringToLower(word);

        // add to anagrams-store
        anagrams[stringToAnagramIdentifier(word)].insert(word);
    }

    // display all the anagrams
    for (auto anagram : anagrams) {
        // skip entries which contains only one item, no anagrams found
        if (anagram.second.size() <= 1) {
            continue;
        }

        // output a comma-separated list of the anagrams
        auto anagramIterator = anagram.second.begin();
        std::cout << *anagramIterator++;
        while (anagramIterator != anagram.second.end()) {
            std::cout << ", " << *anagramIterator++;
        }
        std::cout << std::endl;
    }

    return 0;
}

void stringRemoveInterpunction(std::string& string) {
    string.erase(std::remove_if(string.begin(), string.end(), std::ptr_fun<int, int>(&ispunct)), string.end());
}

void stringToLower(std::string& string) {
    std::transform(string.begin(), string.end(), string.begin(), std::ptr_fun<int, int>(&std::tolower));
}

std::string stringToAnagramIdentifier(std::string word) {
    // sort the characters
    std::sort(word.begin(), word.end());
    return word;
}

Sandbox Questions

  • Do i need to add other tags, or is just code-golf enough?
  • I'm not completely sure about the upper-limit of the input text. My idea was that the code should be able to handle any size input as long as its within the memory-limits of the language. Like you don't have to write "memory optimal code" or something, but also shouldn't asume it is smaller than X. I could also just pick an upper limit of "1 kilobyte" or something to avoid any uncertainty about the requirements I think this is fine now as it is.
  • Someone in the comments below asked how to handle special characters like $?() so I took a look at how my "check program" handled that and it strips them away before doing the anagram check. So I added a rule for that, but while writing that I felt it makes it needlessly complicated and I'm considering ditching that rule and altering my check-program to reflect that (but then I cant claim its the exact same anymore :( )
  • Any other parts that are not clear?
| |
\$\endgroup\$
  • \$\begingroup\$ What happens if there are 3 that are anagrams, such as eat ate tea? Are they all printed in one line / group? \$\endgroup\$ – FlipTack Dec 19 '16 at 17:27
  • \$\begingroup\$ @Flp.Tkc yes, like "parts, strap, traps" in the example \$\endgroup\$ – Olle Kelderman Dec 19 '16 at 17:29
  • \$\begingroup\$ I suggest you remove the grouping rule, since it's not really the interesting part of the challenge. It just adds code and limits the solutions. It's apparent which of the words that are together anyway. I do suggest they have to be grouped though, but without the need for delimiters. \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:24
  • \$\begingroup\$ I think the memory rule is fine. I'm quite sure people will write a script that in theory would work for any input length if it wasn't for language or memory limitations. I also suggest you guarantee at least one character in the input. Otherwise people would need to add code just to handle empty input and that's not the interesting part of the challenge. \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:29
  • \$\begingroup\$ You should add rules regarding special characters. Are it's, sit and its anagrams? What about hyphens? Can there be any special characters such as $?() etc? How are they treated? \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:31
  • \$\begingroup\$ @StewieGriffin The grouping thing is a natural result of my solution to the problem back then, and imo its a fun part of the challenge, so I'm not totally sure about removing it. About the memory limit: I'm totally fine with the guarantee of at least one character if you think empty input needs special handling (i didnt think it would, but I dont really care :P) And yes, you are correct about special characters. I'd say "it's" is two words: "it" and "s". All special characters are ignored, so essentially regarded as whitespace between words. I'll add that \$\endgroup\$ – Olle Kelderman Dec 20 '16 at 23:35
  • \$\begingroup\$ welp, turns out I handled special characters differently, I strip them away from the word, so "it's" becomes "its", guess that'll be the rule then since I want to keep as close as possible to the original program \$\endgroup\$ – Olle Kelderman Dec 20 '16 at 23:48
  • \$\begingroup\$ @StewieGriffin I added a rule about special character handling, but I'm not completely sure about it, thoughts? (see my added "sandbox question") \$\endgroup\$ – Olle Kelderman Dec 21 '16 at 0:05
  • \$\begingroup\$ parsing and anagrams are relevant tags, maybe strings too, but I'm not sure about that one. \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 7:43
  • \$\begingroup\$ !"#$%&'()*+,-./:;<=>?@[]^_{|}~ are all the non-alphanumeric ASCII-characters, except \` . I suggest you include the missing two symbols in the list to ignore, and say: "All non-alphanumeric characters (except spaces and newlines) must be trimmed away. So, it's and its are the same word." (You might want to rephrase that since my English isn't perfect, but something along those lines. If this is the rule then R2D2 and dr.22 will be anagrams, I'm not sure if that the desired behavior..? \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:17
  • \$\begingroup\$ PS! I don't mean to be difficult, it's just that in my experience you'll get these questions sooner or later. So it's a good thing to sort it out while it's still in the Sandbox :) \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:20
  • \$\begingroup\$ @StewieGriffin those two characters should have been included, look at the list from en.cppreference.com/w/cpp/string/byte/ispunct where I got it from, somehow I messed up the copy-paste :( And about "what is desired behaviour?" Im honestly not sure, I never really thought about it before you mentioned it and then I looked at how my sample program handled it. I remember putting in the ispunct-trim for stuff like commas after a word, im not sure about characters within the word... \$\endgroup\$ – Olle Kelderman Dec 21 '16 at 10:26
  • \$\begingroup\$ You can say that the input will not have any special characters except ' and -. Those two must be trimmed away. I think you must include those two, since these can be found in many texts. \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:34
6
\$\begingroup\$

WHAT IS THIS DOING HERE?

How low can you go? - Signal Limbo.

Sometimes we need a low voltage, sometimes we need a high voltage. Let's design a VDC power supply!

The challenge is simple, with 2 lines (+5V and GND), Create a Variable DC power supply on a standard breadboard that ranges from +12V (+/-0.1) to 0V.

INPUT: 5VDC (power rail +), 0VDC (power rail -), 5K, OR 10K potentiometer

OUTPUT: 12-0VDC depending linearly on potentiometer. There is no lower limit to the ammount of current that this circuit needs to be able to supply.

Rules:

enter image description here

this is a standard breadboard. Image courtesy of SparkFun's breadboard tutorial.

A standard breadboard consists of 2 power rails, 2 colums of 5 general pins, and 30 rows.

  • All pins on one row (a,b,c,d, and e are all a single row) are connected.
  • All pins on separate rows are Separate.
  • The opposite is true for power lines. (columns are connected, but not rows)

Electrical components are restricted as follows.

  • All electrical products which have a public datasheet are valid in this challenge, EXCEPT
    • Those without DIP Packaging XOR Those without through hole packaging
    • Those with PCBs
  • All Non-Passive components used in your entry must have a part number, or spec sheet.
  • All passive components (except wire) must have a value, given in Ohms, Henries, or Farads.
  • No pin may be left floating. All pins must be connected to somewhere on the bread board.

Scoring:

You will be scored based on the area that your entry spans. Do Not Score with the power rails, only components within the labelled grid shall be scored.

The area (measured in pin spaces) will be taken by the smallest rectangle that can be drawn around all of the breadboard connections.

this is a , so the entry with the least area consumed wins! good luck!

Tools

Circuits.IO Will be a great standard for this challenge. I ask that you consider this before any other simulator, it's simple, and easy to share. I am not requiring that you use it.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ To one who doesn't have experience with a standard breadboard, the "column" of 5 would better be described as a row, given the picture. This goes for everything in the first set of bullets - switch "row" with "column" and vice versa. \$\endgroup\$ – MildlyMilquetoast Dec 15 '16 at 3:45
  • 4
    \$\begingroup\$ The description of how the breadboard is internally wired is not very clear, but seems to be saying the opposite of how every breadboard I've ever used was wired. \$\endgroup\$ – Peter Taylor Dec 15 '16 at 10:44
  • \$\begingroup\$ Alright, thank you Mistah, and Peter, I'll be sure to remedy these qualms tonight! \$\endgroup\$ – tuskiomi Dec 16 '16 at 15:24
  • \$\begingroup\$ 1. "that ranges from +12V (+/-0.1) to 0V". Is the +/- there to allow for tolerances in component manufacture, to allow for smoothed oscillations in the output, or both? 2. The wiring explanation is still not very clear IMO. How about "All pins on one row (e.g. 23a-23b-23c-23d-23e) are connected"? 3. In the other meta question, validation was mooted as via Spice. I'm not familiar enough with it: is it capable of emulating any product with a public datasheet, or is there a conflict there? \$\endgroup\$ – Peter Taylor Dec 18 '16 at 20:17
  • \$\begingroup\$ @PeterTaylor spice is the framework for all modern advanced circuit simulators. \$\endgroup\$ – tuskiomi Dec 18 '16 at 20:19
  • \$\begingroup\$ Let me rephrase that. In your answer to the other meta question, you said "provided that each challenge specifies a freely available digital testing environment". I don't see such a specification in this challenge, and it's not obvious that "All electrical products which have a public datasheet are valid in this challenge" is compatible with it. Does this question meet your own criteria for acceptability? \$\endgroup\$ – Peter Taylor Dec 18 '16 at 20:29
  • \$\begingroup\$ My bad: I mixed up two usernames starting with t. I think you still need to answer the question of how answers are verified, though. \$\endgroup\$ – Peter Taylor Dec 18 '16 at 23:21
  • \$\begingroup\$ What's the distance from column a to power -? \$\endgroup\$ – l4m2 Dec 31 '17 at 14:49
6
\$\begingroup\$

PPCG VS CR KotH

I am working as fast as I can to get this ready. Please be patient. I have a real job and will attempt to work on this on vacation to the northern states using mobile. I give no promises.

I challenged CR to a KotH challenge. So here is the specs.

Two sides in a arena. 1000x1000. Resources scattered about. A giant area in the center filled with resources. You must build a base and defend your ancient.

You have a few kinds of buildings:

  1. Wall: a simple wall that must be broken before walking through. It has 1/2/4/8 health (upgrades). It can be changed into a gate.
  2. Gate: a gate that lets the side that made it walk through. Health: 1/2/2/4
  3. Turret: Deals 1/1/2/4 damage to the lowest health enemy within a 1/2/4/4 block radius and has 1/1/4/8 health.
  4. Resource drop: a place that you can drop resources. Has 2/2/4/6 health.
  5. Tower of vision. Gives 10 sight radius with health of five. Costs two resources to build.

Upgrades are 1/2/3/4. The first upgrade is just buying the building.

Gates when transformed stay the same level as the wall they started as, can still be upgraded.

Every bot starts with five health, one damage, and three sight radius. They can upgrade each by four for the cost of 1/2/2/2.

All upgrades take one bot. It takes 1/2/2/3 turns to upgrade an item. The bot must upgrade the item all at once or it must restart and repay the cost. Building a item takes one resource.

| |
\$\endgroup\$
  • 2
    \$\begingroup\$ so, how does turn order work? is there a way to attack excluding turrets? \$\endgroup\$ – Destructible Lemon Jul 29 '17 at 2:54
  • 1
    \$\begingroup\$ Will the bots have knowledge of the entire 1000x1000 area or what is the line of sight? \$\endgroup\$ – Simon Forsberg Jul 29 '17 at 8:48
  • 2
    \$\begingroup\$ I'd recommend not making the challenge too complicated/complex. I'm not sure that skill points are necessary. \$\endgroup\$ – Simon Forsberg Jul 29 '17 at 8:49
  • \$\begingroup\$ How does it work with the Q&A site format? Or is it an off-site challenge? \$\endgroup\$ – ugoren Jul 29 '17 at 19:10
  • 2
    \$\begingroup\$ @ugoren King of the Hill challenges like this one are very much on-topic on PPCG, and in fact we even have a tag for challenges like these: koth. \$\endgroup\$ – user41805 Jul 29 '17 at 19:53
  • \$\begingroup\$ @Cowsquack, You're right, it's OK. A bit strange for my taste, since the war happens off-site, but never mind. \$\endgroup\$ – ugoren Jul 29 '17 at 20:16
  • \$\begingroup\$ @SimonForsberg good point \$\endgroup\$ – Christopher Jul 29 '17 at 23:26
  • \$\begingroup\$ This will not be a challenge between PPCG and CR. Challenge declined \$\endgroup\$ – Simon Forsberg Aug 4 '17 at 18:50
  • \$\begingroup\$ Since this idea is dead now, consider developing it further as a normal KoTH or deleting and editing it down to a stub. \$\endgroup\$ – HyperNeutrino Oct 30 '17 at 2:24
6
\$\begingroup\$

PPCG Handwriting OCR

(insert logo here once I make it)

Given an image consisting of handwritten text, output the text that is written. The image of the handwritten text will be generated by taking characters from one or more handwriting samples given by PPCG users.

Rules

  • You may not hardcode your program to only recognize the samples in the corpus.
  • There will be sufficient spacing between characters to avoid ambiguity.
  • Only ASCII alphanumeric characters (those matching the regex [A-Za-z0-9], i.e. uppercase and lowercase English letters and digits) will be present in the input.
  • Inputs will be formed by concatenating individual characters from the handwriting samples.
  • The test cases used for scoring may be modified at any point if I feel it is necessary to do so. Reasons may include but are not limited to: needing more test cases to have a single winner, removing problematic test cases, and fixing errors in test cases.

Aside from the above considerations, there are no guarantees on the appearance of the handwriting, as these are actual handwriting samples and thus can have drastic variances.

Score

Your score will be the number of test cases that are correctly recognized, divided by the total number of test cases. The highest score wins. In the event of a tie, the first submission to reach the high score wins. Additional test cases may be added to break ties.

Handwriting Samples

This Imgur album contains the handwriting samples, as well as the names of the users who contributed them.


I've made a chat room for submitting handwriting samples. The more samples I get, the better this challenge will be, so please take a few minutes and submit a sample!

| |
\$\endgroup\$
  • \$\begingroup\$ You may not hardcode your program to only recognize the samples in the corpus.: Can we tailor our code to be better for the samples than other inputs though? \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:08
  • \$\begingroup\$ The test cases used for scoring may be modified at any point: Will current answers be modified? \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:09
  • 1
    \$\begingroup\$ @TheLethalCoder 1) No. 2) Answers will be run on the test cases any time the answer or the test cases change, and the scores will be updated accordingly. \$\endgroup\$ – user45941 Aug 2 '17 at 16:11
  • \$\begingroup\$ Hadn't seen that loophole before :) \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:13
  • \$\begingroup\$ Can I nitpick again and say handwriting OCR is called ICR? :P \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:06
  • \$\begingroup\$ Can you add an example input as well? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:07
  • 2
    \$\begingroup\$ @TheLethalCoder 1) ICR is when a program tries to learn what handwriting looks like via machine learning. OCR is just parsing written/text input into data. This is OCR, not ICR. 2) I'll add some examples once I get more samples and finish writing my generator. \$\endgroup\$ – user45941 Aug 3 '17 at 9:08
  • \$\begingroup\$ Can you assume a minimum height for the characters? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:28
  • \$\begingroup\$ @TheLethalCoder Aside from the above considerations, there are no guarantees on the appearance of the handwriting, as these are actual handwriting samples and thus can have drastic variances. \$\endgroup\$ – user45941 Aug 3 '17 at 9:29
  • \$\begingroup\$ To be honest with no restrictions this is going to be very hard, Do you lose points for returning extra information? Assume the input Hello if I return H.e.l.l.o. is that 100% for that test case or do I lose and get something like 50%? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:31
  • \$\begingroup\$ And does the output have to be in the correct order? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:58
  • \$\begingroup\$ @TheLethalCoder It's all or nothing. Getting 100% on a test battery challenge should be hard. \$\endgroup\$ – user45941 Aug 3 '17 at 9:58
  • \$\begingroup\$ Please update imgur album \$\endgroup\$ – Pavel Sep 18 '17 at 4:28
  • \$\begingroup\$ @Pavel I will once I finish cutting up the images. My free time has been limited these past few weeks. \$\endgroup\$ – user45941 Sep 18 '17 at 4:29
6
\$\begingroup\$

2 Spooky 4 Me

In terms of halloween, some things are just too spooky for me... Feel like we need some serious doots from skeletons to fuel our hallowed weens. So, in the spirit of that end, print the following, exactly as it is shown, if and only if the input does not equal "DOOT" (in all caps ONLY):

               _.---._
             .'       '.
             :)       (:
             \ (@) (@) /
              \   A   /
               )     (
               \"""""/
                '._.'
                 .=.
         .---._.-.=.-._.---.
        / ':-(_.-: :-._)-:' \
       / /' (__.-: :-.__) '\ \
      / /  (___.-' '-.___)  \ \
     / /   (___.-'^'-.___)   \ \
    / /    (___.-'='-.___)    \ \
   / /     (____.'='.____)     \ \
  / /       (___.'='.___)       \ \
 (_.:       '---'.=.'---'       :._)
 :||        __  _.=._  __        ||:
 :||       (  '.-.=.-.'  )       ||:
 :||       \    '.=.'    /       ||:
 :||        \    .=.    /        ||:
 :||       .-'.'-._.-'.'-.       ||:
.:::\      ( ,): O O :(, )      /:::.
|||| '     / /''--'--''\ \     ' ||||
''''      / /           \ \      ''''
         / /             \ \
        / /               \ \
       / /                 \ \
      / /                   \ \
     / /                     \ \
    /.'                       '.\
   (_)'                       '(_)
    \\.                       .//
     \\.                     .//
      \\.                   .//
       \\.                 .//
        \\.               .//
         \\.             .//
          \\.           .//
          ///)         (\\\
        ,///'           '\\\,
       ///'               '\\\
      ""'                   '""

However, if the input DOES equal "DOOT", in all caps only, print this instead:

               _.---._
             .'       '.
             :)       (:
             \ (@) (@) /
              \   A   /
               )     (
               \"""""/
                '._.'          ' ''''    _''|
                 .=.       @=====***===::_  |
         .---._.-.=.-._.---. (( \-@|_) )) `.|
        / ':-(_.-: :-._)-:' \ ]--------'"
       / /' (__.-: :-.__) '\ \   ||:
      / /  (___.-' '-.___)  \ \  ||:
     / /   (___.-'^'-.___)   \ \ ||:
    / /    (___.-'='-.___)    \ \||:
   / /     (____.'='.____)     \ ||:
  / /       (___.'='.___)       \||:
 (_.:       '---'.=.'---'       :._)
 :||        __  _.=._  __       
 :||       (  '.-.=.-.'  )      
 :||       \    '.=.'    /       
 :||        \    .=.    /      
 :||       .-'.'-._.-'.'-.       
.:::\      ( ,): O O :(, )   
|||| '     / /''--'--''\ \    
''''      / /           \ \
         / /             \ \
        / /               \ \
       / /                 \ \
      / /                   \ \
     / /                     \ \
    /.'                       '.\
   (_)'                       '(_)
    \\.                       .//
     \\.                     .//
      \\.                   .//
       \\.                 .//
        \\.               .//
         \\.             .//
          \\.           .//
          ///)         (\\\
        ,///'           '\\\,
       ///'               '\\\
      ""'                   '""

Rules

  • Trailing newlines and spaces are allowed.
  • The design is horizontally symmetric, if you find inconsistencies let me know.

Doot it up, and enjoy!


(Yes, I'm going to make it more official when posting on the actual SE)

| |
\$\endgroup\$
  • 4
    \$\begingroup\$ What about this challenge ensures that the same old techniques won't be the best ones (i.e. that it adds value to the site)? \$\endgroup\$ – Peter Taylor Oct 13 '17 at 23:01
  • 2
    \$\begingroup\$ @PeterTaylor worse? Better? 10x worse? 10x better? I don't really know what makes the challenge unique beyond a formal proof that it is, but if the users enjoy it; why not allow it... current event challenges attract new users. \$\endgroup\$ – Magic Octopus Urn Oct 16 '17 at 23:03
6
\$\begingroup\$

Check equation proofs in a ring

The recent to prove that (-a)×(-a) = a×a attracted a number of faulty submissions, because there wasn't an easy way to verify the proofs. So, let's write some proof checkers.

Input

Your program should take a sequence of strings representing expressions in a ring. Valid expressions consist of:

  • Single-lowercase-letter variables (a to z)
  • Two constants: the additive identity 0 and multiplicative identity 1
  • Compound expressions: (X+Y), (X*Y) and (-X), where X and Y stand for subexpressions. (The parentheses must always be present, and there must be no whitespace.)

Task

Your program should check whether:

  • All strings except the first and last represent valid expressions.
  • Each expression (after the first) can be obtained from the preceding expression, by substituting one of the ring axioms in the expression exactly once.

Output truthy if these conditions are met. Otherwise, output falsey.

You may assume that the first and last strings in the input are valid expressions. But your program must check the intermediate strings.

The ring axioms

For this challenge, use the following substitution rules (and do not use any others). Substitutions can go both left-to-right and right-to-left.

  1. (X+(Y+Z)) = ((X+Y)+Z)

  2. (X+0) = X

  3. (X+(-X)) = 0

  4. (X+Y) = (Y+X)

  5. (X*(Y*Z)) = ((X*Y)*Z)

  6. (X*1) = X

  7. (1*X) = X

  8. (X*(Y+Z)) = ((X*Y)+(X*Z))

  9. ((X+Y)*Z) = ((X*Z)+(Y*Z))

Scoring

Proof checkers are traditionally small, so that people can review them easily. Therefore, your program should be written in as few bytes as possible.

Meta comments

Is the input format fair for most languages and approaches?

Usually, code-golf problems should not require input validation. However, I thought it would be appropriate behaviour for a proof checker. I think the current spec still accommodates regex-based solutions.

The format for the original challenge also listed which axiom was used for each step. I could include this but I doubt that it improves the challenge much.

Test cases

Valid proofs

(0+a)
(a+0)
a

(a*(-1))
((a*(-1))+0)
((a*(-1))+(a+(-a)))
(((a*(-1))+a)+(-a))
(((a*(-1))+(a*1))+(-a))
((a*((-1)+1))+(-a))
((a*(1+(-1)))+(-a))
((a*0)+(-a))

Invalid proofs

These proofs are missing intermediate steps.

(0+a)
a

(-0)
((-0)+0)
0

((a*0)+(-a))
(0+(-a))

This is simply untrue, so no proof should ever be accepted.

(a*b)
(b*a)

Invalid expressions

Your proof checker should reject if these appear partway through a proof.

a+b

(a+-b)

(a + b)

1+

42
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ You should include the ring axioms to make the post self-contained. \$\endgroup\$ – Laikoni Oct 18 '17 at 16:23
6
\$\begingroup\$

ASCII Stock Exchange

At the ASCII Stock Exchange, each character has a price. If a character is used more often, its price rises, otherwise the price decreases over time.

Initially, each character has price 10. [Meta: Is this too low/high?] After each answer, the prices change as follows:

  • Each character that is not used in the answer's code has its price decreased by one, except when the price is already one, in which case it stays one.
  • If a character is used n-times, then its price increases by n.

We define the score of a piece of code as the sum of the prices of its characters.

Example

For the sake of simplicity, we only consider characters A, B and C for this example. The challenge itself works with all bytes from \0 to \255. Initially, we have the following prices:

A -> 10, B -> 10, C -> 10

If the code of the first answer is BAAA, then is has a score of 40 (computed by taking the previous character prices into account) and the prices change to

A -> 13, B -> 11, C -> 9

If the next answer is CC, it has a score of 18 and the prices are updated to

A -> 12, B -> 10, C -> 11

The Task

Your objective is to write a program or function which calculates the score of a given piece of code in dependence of a list of previous answers which all influence the initial prices in the way described above.

The goal is to do so while minimizing the submission's score itself in the context of this challenge, that is your submission should be able to calculate its own score by taking a list of all previous submissions and its own source code as input.

The answer with the lowest score in each language wins.

Rules

  • You may take a list of strings and a string as input, or require that the string to be scored is the first/last element of the list, or any other reasonable input format.
  • You may not answer twice in a row.
  • If an answer in language X has already been posted, you may only post another answer in language X if your submission achieves a lower score than the previous answer and the code is not identical.
  • For this challenge only major releases of languages are considered their own language (e.g. Java 7 vs. Java 8). If there already is an answer in version A of a language and you have an answer in version B of the language and are in doubt whether version B is different enough from version A to be treated as different language, make sure that your code is not valid in version A.

Answer Format

To avoid having to copy all previous answers in order to calculate your submission's score, the chain will maintain a score calculator on TIO. Click on the link to the calculator in the previous answer and enter your code into the input field to calculate its score. Then add your code as a command-line argument, generate a new link and include it in your answer for the next submission.

If you wrote answer number 42 in Haskell with a score of 100, please format it as

42. Haskell, score 100

 <code>

TIO-Link, explanation, ...

Score calculator for next answer

Test Cases

These test cases are in the format list of strings, string to score -> result.

[], "BAAA" -> 40
["BAAA"], "CC" -> 18
["abc"], "abc" -> 33
["ab12", "aa22", "31a"], "ac23" -> 42
["a","b","c","d","e","f","g","h","i","j"], "123" -> 3

Meta

  • Any idea what could be a good initial price? I picked the number 10 rather arbitrarily.
  • Letting the cost of unused characters decrease until 0 might lead to score 0 answers. Do you think this is a problem and the minimum cost should be 1? Minimum changed to 1.
  • I'm unsure what range of characters is a sensible choice. Limiting answers to printable ASCII plus white space would make things easier but also exclude a lot of languages. Another possibility would be to allow the whole byte range from \0 to \255. Then also golfing languages could participate, albeit to score them they would need to be converted to their byte form which usually contains a lot of unprintable characters. The score calculator is able to handle unprintables, but I don't know how to insert them into the text fields on TIO. All bytes from \0 to '\255' are allowed.
  • Is the winning criterion suitable for answer chaining?
  • A leader board snippet would be nice, but I don't know how to modify the existing ones. If someone could provide such a snippet, I would be very grateful.
  • Relevant tags?
| |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think decreasing the scores to 1 is more sensible, because otherwise I could write a submission using all (or even just one of) the zero-score characters a billion times (say, in a comment), keeping a "minimum" score, but then subsequent submissions would have completely absurd scores, and it'd be easy to outgolf later, leading to a boring answer chain. \$\endgroup\$ – Giuseppe Oct 2 '17 at 18:08
  • \$\begingroup\$ You may want to correct "enter your code into the input field to calculate its score. Then add your code as a command-line argument," \$\endgroup\$ – caird coinheringaahing Oct 2 '17 at 19:55
  • 2
    \$\begingroup\$ I think allowing all 256 bytes is a good idea because languages like Jelly, 05AB1E, etc. will more than likely use more than the printable ASCII chars. \$\endgroup\$ – ETHproductions Oct 2 '17 at 20:30
  • 3
    \$\begingroup\$ "While in principal Python 2.7.14 and Python 2.7.13 are different languages according to the site rules, I recommend to avoid using the fact that it is technically allowed as an excuse to post boring answers." Recommendations do not work, especially when they're as imprecise as this. (Are you "recommending" not treating Python 2 and Python 3 as separate languages? I have no idea). If you want to ban boring exploitation of the convention on different interpreters, ban it outright, but give a clear definition of how lines should be drawn. \$\endgroup\$ – Peter Taylor Oct 2 '17 at 21:21
6
\$\begingroup\$

Note: If you are seeing this first, you might want to sort by active.

Unhappy numbers ascii art

Draw a square (or a rectangle as close to a square as possible) that represents the cycle of an unhappy number.

[ short description of unhappy numbers here + example ]

[ square formating rules ]

Input

Unhappy integer.

Output

ASCII art.

Example

Input:
4
Output:
 4 -  16 - 37 
20         58
42 - 145 - 89
| |
\$\endgroup\$
  • \$\begingroup\$ The cycle of an unhappy number is a constant. \$\endgroup\$ – J B Mar 7 '11 at 23:42
  • \$\begingroup\$ @JB: thanks, I will rephrase the question. I didn't mean the 4 cycle. (Why did I chose 4 as an example? :/ ) \$\endgroup\$ – Eelvex Mar 8 '11 at 4:56
  • \$\begingroup\$ @Eelvex This is an nice challenge. Are you still interested in finishing it? \$\endgroup\$ – J Atkin Feb 7 '16 at 19:06
  • 1
    \$\begingroup\$ This challenge proposal has been inactive for over a month. I would like to take ownership of the challenge and make it ready for posting. Please let me know within the next 2 weeks if you have any objections and would still like to finish and post this challenge yourself. \$\endgroup\$ – J Atkin Feb 10 '16 at 0:19
  • \$\begingroup\$ @JAtkin, no objections. \$\endgroup\$ – Eelvex Feb 12 '16 at 11:20
  • 1
    \$\begingroup\$ If this was posted, can you please delete it? \$\endgroup\$ – MD XF Aug 17 '17 at 16:58
6
\$\begingroup\$

Chess ASCII Art, Knight

In honor of the world chess championship, in the shortest possible program, output the following ASCII art piece

      ,....,
   ,::::::<
  ,::/^\"``.
 ,::/, `   e`.
,::; |        '.
,::|  \___,-.  c)
;::|     \   '-'
;::|      \
;::|   _.=`\
`;:|.=` _.=`\
  '|_.=`   __\
   `\_..==`` /
    .'.___.-'.
   /          \
  ('--......--')
  /'--......--'\
   "--......--"

This is a code-golf challenge

| |
\$\endgroup\$
  • \$\begingroup\$ You might want to make sure all the lines are aligned properly (they could be fine, since I'm on mobile and I know it can display differently, but it looks bent to me). \$\endgroup\$ – Οurous Nov 23 '18 at 19:59
  • \$\begingroup\$ you're right, it was a little bent, I've reformatted it \$\endgroup\$ – Thaufeki Nov 23 '18 at 20:17
  • 2
    \$\begingroup\$ Seems straightforward enough \$\endgroup\$ – Quintec Nov 24 '18 at 1:23
  • \$\begingroup\$ lol, akin to image compression of pixel art in a very specific case :) I like the idea. \$\endgroup\$ – alan2here Nov 24 '18 at 22:22
  • \$\begingroup\$ The very worst is approx 145 bytes + "verbatim output this". Be fun to see much better ones :) \$\endgroup\$ – alan2here Nov 24 '18 at 22:33
  • 1
    \$\begingroup\$ Isn't the World Chess Championship already over? According to google it ended nov. 28th. ;) Did you forgot to post it? \$\endgroup\$ – Kevin Cruijssen Dec 3 '18 at 9:08
  • \$\begingroup\$ Yeah, I made this post on November 23rd, cross-posting from sandbox eventually slipped my mind \$\endgroup\$ – Thaufeki Dec 3 '18 at 14:42
  • \$\begingroup\$ @Thaufeki You could still post it, or are you going to wait a year? ;) \$\endgroup\$ – Kevin Cruijssen Dec 4 '18 at 10:22
  • \$\begingroup\$ I would have to wait two, next one isn't until 2020! I'll post it now \$\endgroup\$ – Thaufeki Dec 4 '18 at 14:43
6
\$\begingroup\$

Is this checkmate?

Input

A chess position in FEN format. You can assume the input is a valid chess position.

Output

Two distinct consistent outputs for checkmate or not.

Examples

enter image description here

8/8/8/8/8/5BKN/8/7k b - - 93 47
Mate

| |
\$\endgroup\$
  • \$\begingroup\$ I suggest wording similar to “two distinct consistent outputs for checkmate or not” \$\endgroup\$ – Quintec Mar 12 '19 at 11:52
  • \$\begingroup\$ @Quintec Thanks. \$\endgroup\$ – user9207 Mar 12 '19 at 11:58
  • 4
    \$\begingroup\$ I'd recommend keeping it all self-contained and having a description for the FFN format, as well as a few more test cases \$\endgroup\$ – Jo King Mar 12 '19 at 21:41
  • 2
    \$\begingroup\$ Is restricted to the FFN format a part of the challenge? Why not allow it in any reasonable format? \$\endgroup\$ – tsh Mar 13 '19 at 5:47
  • \$\begingroup\$ @Quintec why not just say truthy or falsey? \$\endgroup\$ – qwr Jun 20 '19 at 14:48
  • \$\begingroup\$ I suggest removing the restriction to FEN format, as it doesn't really add anything to the challenge, and specifying that the output be a truthy or falsey value as that is the usual spec for these types of challenges. \$\endgroup\$ – scatter Aug 26 '19 at 13:28
6
\$\begingroup\$

Lexicographically earliest valid UTF-8 byte sequence permutation

There are currently 1,114,112 possible Unicode characters (code points). Each character has a unique valid byte sequence in the UTF-8 encoding. Different characters have different length encodings:

  • ASCII characters have a 1-byte encoding 00-7F.
  • The next 1920 characters have a 2-byte encoding C2 80-DF BF.
  • The rest of the BMP has a 3-byte encoding E0 A0 80-ED 9F BF and EE 80 80-EF BF BF.
  • The other planes have a 4-byte encoding F0 90 80 80-F4 8F BF BF.

It's possible for two strings (specific non-normalised sequences of Unicode code points) of Unicode to have byte sequences that are permutations of each other in a number of ways:

  • One string could simply be a permutation of the other at the Unicode level, e.g. ab (61 62) and ba (62 61).
  • UTF-8 continuation bytes could be switched between two characters, e.g. ¡â (C2 A1 C3 A2) and ¢á (C2 A2 C3 A1).
  • UTF-8 continuation bytes could be switched within a character, e.g. (E1 B4 B5) and (E1 B5 B4).

For this challenge I would like you to write a program or function that finds the string whose UTF-8 byte sequence is lexicographically earliest of all such sequences that are permutations of the UTF-8 byte sequence of a given Unicode string.

For example, if your input is ᵴ¢ába (E1 B5 B4 C2 A2 C3 A1 62 61) your output would be ab¡âᴵ (61 62 C2 A1 C3 A2 E1 B4 B5).

Note however that some byte sequences are not valid UTF-8 (e.g. E0 80 A0 which is an overlong encoding for a space) so you need to take care to avoid these.

It would be helpful if your "Try It Online" or similar link includes a footer that helps demonstrate the correctness of your output, where this is not obvious from the I/O format or code.

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

| |
\$\endgroup\$
  • 3
    \$\begingroup\$ For test cases, it will probably be a good idea to provide both strings and hex since I'd guess many languages will have to try both. Also this probably needs at least a link to an explanation of UTF8 continuation bytes. \$\endgroup\$ – FryAmTheEggman Jun 29 '19 at 16:57
  • 1
    \$\begingroup\$ "permutation of its canonical" should be "permutation of the input's canonical". \$\endgroup\$ – Erik the Outgolfer Jun 29 '19 at 17:00
  • 1
    \$\begingroup\$ @FryAmTheEggman ... but I provided the hex? I'm not sure what I'm missing... \$\endgroup\$ – Neil Jun 29 '19 at 23:24
  • 1
    \$\begingroup\$ @EriktheOutgolfer How about "I would like you to write a program or function that returns the Unicode string whose canonical UTF-8 byte sequence is the lexicographically earliest of all such sequences that are permutations of the canonical UTF-8 byte sequence of a given Unicode string"? \$\endgroup\$ – Neil Jun 29 '19 at 23:27
  • 1
    \$\begingroup\$ I meant in the example that you actually had, and presumably some number of test cases. I only mentioned it because I thought it was odd that you did it in the explanation but not the example. \$\endgroup\$ – FryAmTheEggman Jun 29 '19 at 23:54
  • \$\begingroup\$ @Neil Looks good. :) \$\endgroup\$ – Erik the Outgolfer Jun 30 '19 at 16:34
  • \$\begingroup\$ I'm wary of the use of the word "canonical" in this question, because it raises issues in my mind about normalisation of Unicode strings. I think that the intended challenge is really about byte arrays with constraints on the most significant bits, and I think it would be better to make that explicit (and to make the constraints explicit). \$\endgroup\$ – Peter Taylor Jul 2 '19 at 11:16
  • \$\begingroup\$ @PeterTaylor There is that, but I wanted to exclude sequences such as E0 80 A0. \$\endgroup\$ – Neil Jul 2 '19 at 13:23
  • \$\begingroup\$ @Neil, I think there's a miscommunication here. I'm saying that instead of talking about Unicode strings the question should explicitly state the FSS-UTF constraints on byte sequences, and maybe rule out encoding UTF-16 surrogate codepoints and codepoints greater than 0x10FFFF. \$\endgroup\$ – Peter Taylor Jul 2 '19 at 13:48
  • \$\begingroup\$ @PeterTaylor OK but I really wanted this to be a string question rather than a byte sequence question... \$\endgroup\$ – Neil Jul 2 '19 at 16:20
  • \$\begingroup\$ The problem then is dealing with the lexicographically first rearrangement of C3 A9 (é in normal form C) being 65 CC 81 (é in normal form D). \$\endgroup\$ – Peter Taylor Jul 2 '19 at 16:29
  • \$\begingroup\$ @PeterTaylor Is that possible to do just by permuting the byte sequence? \$\endgroup\$ – Neil Jul 2 '19 at 16:34
  • \$\begingroup\$ No, and that's why I'm arguing that the question should be phrased in terms of byte sequences rather than strings. \$\endgroup\$ – Peter Taylor Jul 2 '19 at 17:40
  • \$\begingroup\$ There’s a mistake in the example: á is C3A1 and ¡ is C2A1. Good challenge. From the sound of it I/O will be flexible; this seems sensible since it keeps it open to more languages. \$\endgroup\$ – Nick Kennedy Jul 2 '19 at 17:54
  • \$\begingroup\$ @PeterTaylor I wanted it to be clear that these byte sequences must be a valid UTF-8 encoding of a Unicode string. I've tried rewriting the question a bit... \$\endgroup\$ – Neil Jul 2 '19 at 23:55
6
\$\begingroup\$

Compose Fill In The Blanks

| |
\$\endgroup\$
  • \$\begingroup\$ Can you add some test cases? \$\endgroup\$ – MilkyWay90 Jul 27 '19 at 14:35
  • \$\begingroup\$ @MilkyWay90 Ok I added some \$\endgroup\$ – Wheat Wizard Jul 27 '19 at 14:47
  • \$\begingroup\$ Okay, I give /support (also, you may want to add disallowing standard loopholes and using any default io method to finish it up) \$\endgroup\$ – MilkyWay90 Jul 27 '19 at 14:48
  • 3
    \$\begingroup\$ @MilkyWay90 Those are already standard I am not going to be making my post any more cluttered with stuff that adds nothing. \$\endgroup\$ – Wheat Wizard Jul 27 '19 at 14:53
6
\$\begingroup\$

Move arrows along a contour

Posted here

| |
\$\endgroup\$
  • \$\begingroup\$ I've edited in a question since it needs 2D for clarity. \$\endgroup\$ – Adám Jul 26 '19 at 8:48
  • \$\begingroup\$ @Adám Only the arrows move. "+-|" always stay in place, or are "hidden" behind an arrow. So, you second example is correct (I deleted the first one) \$\endgroup\$ – Galen Ivanov Jul 26 '19 at 9:02
  • \$\begingroup\$ Continuing @Adám's question: Are shapes always separated by at least one space, or can they be next to each other like ++++\n++++, and we have to determine if it's a ++++\n++++ or +--+\n+--+ based on the directions the arrows are facing? I.e. is this a possible/valid input, and are those outputs correct? \$\endgroup\$ – Kevin Cruijssen Jul 26 '19 at 11:26
  • \$\begingroup\$ @GalenIvanov I didn't have anything but arrows move, and not it doesn't follow, because you couldn't tell what was behind the arrows, -s or +s which is what would make the two possible answers. \$\endgroup\$ – Adám Jul 26 '19 at 11:28
  • 1
    \$\begingroup\$ @KevinCruijssen Example 2 has two adjacent shapes with no (vertical) spacing. \$\endgroup\$ – Adám Jul 26 '19 at 11:29
  • \$\begingroup\$ @Adám Ah, you're right. As for your question however, you'd still know +<<+\n+>>+ is +--+\n+--+ due to the directions of the arrows in combination with the rule "when an arrow is on a corner, it keeps its current direction and changes it only after the turn is taken". See the pastebin in my previous comment for some test cases where you do know it's ++++\n++++ instead, because of the arrow directions. +^<+\n+>v+ will be two ++++\n++++ boxes, but +<<+\n+>>+ will be one +--+\n+--+ box. \$\endgroup\$ – Kevin Cruijssen Jul 26 '19 at 11:37
  • \$\begingroup\$ @KevinCruijssen Good point, but OP actually never says that the input is an obtainable state, though it does make sense. I still have a feeling that there could be ambiguous cases. \$\endgroup\$ – Adám Jul 26 '19 at 11:41
  • 1
    \$\begingroup\$ @KevinCruijssen The shapes will always be separated by at least one space, I'll add it to the description. \$\endgroup\$ – Galen Ivanov Jul 26 '19 at 11:44
  • \$\begingroup\$ @GalenIvanov Probably better indeed to not have to deal with confusing ambiguous cases. In that case I would also have at least a newline separation, so test case 2 should be slightly modified. :) \$\endgroup\$ – Kevin Cruijssen Jul 26 '19 at 11:45
  • \$\begingroup\$ @Adám Oh, I see - indeed I need to correct the second case to have a vertical space between the shapes. \$\endgroup\$ – Galen Ivanov Jul 26 '19 at 11:51
  • 2
    \$\begingroup\$ Even single tracks can be incredibly difficult: [" ++ ","++++","++^+"," ++ "] only has one possible output: [" ++ ","++++","+++>"," ++ "] \$\endgroup\$ – Adám Jul 26 '19 at 11:55
  • 2
    \$\begingroup\$ @AdámYes, this is the only output. Do you think a condition that sharp turns are forbidden will help? (this means no two + can be adjacent) \$\endgroup\$ – Galen Ivanov Jul 26 '19 at 12:21
  • 1
    \$\begingroup\$ @GalenIvanov Maybe that's indeed better to reduce confusion and make the challenge someone more manageable. Although you can still deduct the solution in Adam's comment above, having no spaces inside the space makes it rather difficult to parse correct. Always having at least one |/- between two + will always give the shapes always spaces, making it easier to parse individual shapes. In which case Adam's one would become [" +-+ "," | | ","+-+ +-+","| |","+-+ ^-+"," | | "," +-+ "] -> [" +-+ "," | | ","+-+ +-+","| |","+-+ +>+"," | | "," +-+ "] \$\endgroup\$ – Kevin Cruijssen Jul 26 '19 at 13:55
  • \$\begingroup\$ @KevinCruijssen Thanks, I added clarification. \$\endgroup\$ – Galen Ivanov Jul 26 '19 at 14:09
  • 1
    \$\begingroup\$ @GalenIvanov Maybe also change the one Adam edited in, since it's still with ++ below one-another. :) \$\endgroup\$ – Kevin Cruijssen Jul 26 '19 at 15:08
6
\$\begingroup\$

Posted here

| |
\$\endgroup\$
  • \$\begingroup\$ I found a lot of similar questions, but not quite the same. Would it be considered a duplicate? \$\endgroup\$ – Jitse Aug 1 '19 at 8:17
  • \$\begingroup\$ we've had double factorial closed before as a dupe of the vanilla factorial question \$\endgroup\$ – Giuseppe Aug 1 '19 at 12:03
  • 1
    \$\begingroup\$ @Giuseppe Thanks! I found that post, but I thought the variable factorial range might make it considerably different from the original challenge. \$\endgroup\$ – Jitse Aug 1 '19 at 12:12
  • \$\begingroup\$ Can we take input as two integers? \$\endgroup\$ – Adám Aug 1 '19 at 12:49
  • \$\begingroup\$ Can you give a definition for the multi-factorials above 2? \$\endgroup\$ – MilkyWay90 Aug 2 '19 at 4:55
  • \$\begingroup\$ @Adám That makes the challenge somewhat easier, but I suppose it is fair. I added the other input option. \$\endgroup\$ – Jitse Aug 2 '19 at 7:04
  • \$\begingroup\$ @MilkyWay90 Yes! Totally skipped that part, oops. Is it clear enough like this? \$\endgroup\$ – Jitse Aug 2 '19 at 7:05
  • 1
    \$\begingroup\$ @KevinCruijssen Input numbers can be in any format, of course. I thought this was included in the default I/O rules, buy I will specify this in the challenge. \$\endgroup\$ – Jitse Aug 2 '19 at 12:39
  • \$\begingroup\$ @KevinCruijssen In the input, at least one factorial sign is expected, i.e. a positive integer. I suppose the correct return value for a factorial number of zero would just be the base, but as the challenge is to calculate a factorial, this seems like an unreasonable restriction. The same goes for a factorial number lager than the base. If the factorial number is equal to the base, the base should be returned as per the generalized formula. I will add additional examples to clear this up. Thanks for the feedback! \$\endgroup\$ – Jitse Aug 2 '19 at 12:39
  • \$\begingroup\$ @KevinCruijssen The range(start,stop,step) function in Python 3 returns a generator with an initial value of start (or 0 if not specified) and a final value of stop-1. For example, the list representation of range(1,4) is [1,2,3]. If this list is sliced as [1,2,3][::-1], the returned list is [3,2,1], which can also be achieved with range(3,0,-1). When the slicing operator is applied to the generator directly, a new generator is returned which generates the sliced list instead. Does that answer your question? Also, range(420,0,-30) would be a cleaner approach in this case. \$\endgroup\$ – Jitse Aug 2 '19 at 13:08
  • \$\begingroup\$ @Jitse Ah ok, now it makes more sense. I indeed knew range(1,4) is [1,2,3]. And I also knew [::-1] reverses the order, since I see it used in answers every now and then. Seeing the range(1,4)[::-1] == range(3,0,-1) now I'm not sure why I didn't see it myself when I asked you the question. And yes, range(value,0,-n) would indeed be clearer than range(1,value+1)[::-n]. ;) \$\endgroup\$ – Kevin Cruijssen Aug 2 '19 at 13:24
  • \$\begingroup\$ Seems good except maybe you should specify that \$n!^{(k)} = n\underbrace{!\ldots!}{k}\$ (n!^{(k)} = n\underbrace{!\ldots!}{k}) \$\endgroup\$ – MilkyWay90 Aug 2 '19 at 16:47
6
\$\begingroup\$

Cliquish Program

Challenge: Write a program that accepts a character (or byte, see additional information) as input. Then:

  1. If the character is contained within the source code, output a different character also in your source code.
  2. If the character is not contained within the source code, output a different character also not in your source code.

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

Additional Information

  • Your program must consist of at least 2 distinct characters.
  • Your program must have at least 2 possible outputs.
  • Your program does not have to be deterministic; it may output a character at random (with any distribution), so long as it conforms to the above criteria.
  • Your program may optionally take a byte as input instead of characters. If you do, the code page the input is written in must contain at least each distinct byte in the source code, as well as at least two different bytes not in the source code.
  • You may take input and give output in any reasonable way. For example, you may take input as a function parameter, a command-line argument, a line from STDIN, a triple-nested array containing a single character, etc. You could output via return value, STDOUT, exit code (if applicable), fax output, etc. The input and output formats must be consistent, however.
  • Your output can only consist of the required character, optionally followed by one trailing newline. Prompt information (such as ans =) is exempt from this rule; such unpreventable output is acceptable.
| |
\$\endgroup\$
  • 2
    \$\begingroup\$ Slightly more interesting than most generalised quines. Have you checked quine for dupes? \$\endgroup\$ – Peter Taylor Aug 2 '19 at 7:32
  • 1
    \$\begingroup\$ @PeterTaylor related related related. I couldn't find any exact dupes. \$\endgroup\$ – Conor O'Brien Aug 2 '19 at 19:39
  • \$\begingroup\$ What if your program contains all but one possible character? What encoding are the characters in? UTF-8? latin-1? ASCII? \$\endgroup\$ – Beefster Aug 2 '19 at 20:18
  • \$\begingroup\$ @Beefster Hopefully I've addressed your first question. As per your second, I believe we have a standard consensus on what a character is \$\endgroup\$ – Conor O'Brien Aug 11 '19 at 18:13
  • \$\begingroup\$ By induction the program must have 4 possible outputs. Inside/outside of the source × two included in each (if choose one, output the other). Btw I don't understand the title \$\endgroup\$ – Mark Jeronimus Aug 22 '19 at 7:05
6
\$\begingroup\$

ASCII Maze Unrendering 3000

Posted

| |
\$\endgroup\$
  • \$\begingroup\$ Part of the wall for the current only test case seems a bit too narrow. \$\endgroup\$ – Unrelated String Aug 28 '19 at 2:37
  • \$\begingroup\$ I think this could be considered a special case of this challenge, with slight differences in the voxel style. \$\endgroup\$ – flawr Aug 29 '19 at 6:56
  • \$\begingroup\$ @flawr You're right. As written, this is a duplicate. Do you know if the reverse has been done, taking the 3d version and returning the original? \$\endgroup\$ – Hiatsu Aug 29 '19 at 17:52
  • \$\begingroup\$ I don't think the reverse has been done, but I'm not sure this would make a good challenge. I'm still thinking about how one could make this. I mean the 2d version you propose would make it a bit simpler. \$\endgroup\$ – flawr Aug 29 '19 at 19:10
  • 1
    \$\begingroup\$ Yes. The full 3d version would almost certainly be impossible, because most voxels would be completely blocked. Here, every block is visible, and a human can figure out where the walls are, so a computer should be able to do it too. \$\endgroup\$ – Hiatsu Aug 29 '19 at 19:17
6
\$\begingroup\$

Question link

| |
\$\endgroup\$
  • \$\begingroup\$ @Night2 Indeed, didn't notice that point, I fixed the samples in the rules to include AA-000-AA \$\endgroup\$ – Elcan Sep 20 '19 at 6:25
  • \$\begingroup\$ Are the letters mandatory to be uppercased, or could we output in lowercase as well? \$\endgroup\$ – Kevin Cruijssen Sep 20 '19 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 '19 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\$ – Kevin Cruijssen Sep 20 '19 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\$ – Kevin Cruijssen Sep 20 '19 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 '19 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\$ – Shieru Asakoto Sep 21 '19 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 '19 at 18:41
6
\$\begingroup\$

The Ever-Changing Labyrinth (WIP)

This is a 2-player asymmetric KotH challenge.

  • One player controls a pair of telepathically connected adventurers. The game ends when either one of these adventurers reaches the end.
  • The other player has the ability to change the maze and tries to keep the adventurers from solving it.

Gameplay

At the beginning of the game, the Maze Master creates a \$6 \times 6\$ maze.

Every cell of the maze must always be reachable from every other cell.

Both adventurers begin on the northwest corner cell. The goal is on the southeast corner cell. One adventurer begins facing east and the other begins facing south.

The game proceeds in a turn-based fashion, alternating between each player.

  • Adventurers:
    • Observe surroundings of themself and the other adventurer:
      • The wall directly ahead on the current cell is observed
      • If there is no wall directly ahead on the current cell, every wall is observed along each cell ahead in a straight line until a wall obstructs the adventurer's sight
      • The walls on the left and right of the current cell are observed
      • If there is no wall to the left, the wall ahead on the cell to the left can be observed
      • If there is no wall to the right, the wall ahead on the cell to the right can be observed
    • Either moves forward, changes orientation, or waits
  • The maze master, in order:
    • Receives one mana, which can be used to modify the maze
    • Observes the entire maze, including the position and orientation of the adventurer
    • May remove a wall from anywhere in the maze that is not currently visible to the adventurer
    • May add a wall to anywhere in the maze that is not currently visible to the adventurer, provided it does not separate the maze into two unconnected halves.

Illustration of how adventurers observe the maze:

Adventurer vision 1 Adventurer vision 2

The adventurer in the above image is facing east and sees all the green cells and walls. The dotted green lines indicate non-walls the adventurer can see.

Adventurers may occupy the same space and face different directions. Observation occurs before either of them chooses an action; movement is resolved simultaneously.

The cost to modify the maze increases exponentially over time. The cost to change a wall slot is \$2^n\$, where \$n\$ is the number of times that that particular wall slot has been added or removed since the beginning of the game.

The maze master can stockpile an arbitrarily large amount of mana, but can only change two walls per turn (removing one, then adding one)

Coding

  • Both players may retain as much state as they wish for the entire duration of the game.
  • State will not be remembered between games.
  • Players will not be able to access the state of the other player.
  • Players must not use global variables.
  • Each player will receive an isolated RNG state at the beginning of the game. To ensure that all games have the same outcome with a given seed, all non-deterministic behavior must use the provided RNG.
  • Each turn has a time limit of 5ms.

Implementation language will probably be Javascript / WASM so that the challenge can be accessed easily without downloading additional language runtimes/compilers.

Scoring

Adventurers compete only with other adventurers, and the same goes for maze masters.

Both roles are scored by the average number of turns it takes for the adventurer to complete the maze over a series of 5 games between each pair of players. If a game lasts for 50,000 turns without an adventurer completing the maze, the score will be 50,000 for that game. If this number turns out to be too small, I reserve the right as the challenge creator to increase it.

The adventurer with the lowest score wins.

The maze master with the highest score wins.

Scores will be updated when a adventurer or maze master is added or updated.


| |
\$\endgroup\$
  • \$\begingroup\$ Assumes that the maze master will only wait if the adventurer waits, would that always make waiting a bad choice for the adventurer? \$\endgroup\$ – user202729 Aug 7 at 1:19
  • \$\begingroup\$ Does "not visible" mean "not visible at the moment"? \$\endgroup\$ – user202729 Aug 7 at 1:20
  • \$\begingroup\$ Is the "increase over time" by power of 2 or linear? \$\endgroup\$ – user202729 Aug 7 at 1:21
  • \$\begingroup\$ @user202729 waiting is probably never a good idea for the adventurer, yes, and linear. \$\endgroup\$ – Beefster Aug 7 at 5:16
  • \$\begingroup\$ Would the score of every maze master change whenever an adventurer program is posted, and vice versa? \$\endgroup\$ – user202729 Aug 7 at 5:31
  • \$\begingroup\$ Perhaps "if the game doesn't terminate after X turns then the score will be X", with X large enough such that the optimal adventurer can always achieve a score smaller than X (but small enough so it's practical to compute) \$\endgroup\$ – user202729 Aug 7 at 5:34
  • \$\begingroup\$ Regarding language: if the challenger is implemented in some language that can invoke other programs (such as JavaScript (Node.js)), then it's possible to communicate over standard input/output and let people submit in any language. \$\endgroup\$ – user202729 Aug 7 at 5:34
  • \$\begingroup\$ There should be some time limit for each turn. \$\endgroup\$ – user202729 Aug 7 at 5:35
  • \$\begingroup\$ @user202729 A couple reasons why I probably won't communicate over stdin/stdout: 1. it can be tricky to avoid deadlock; 2. I want the challenge to be accessible to many users without requiring them to download additional language runtimes. \$\endgroup\$ – Beefster Aug 7 at 15:54
  • \$\begingroup\$ So the observed information would be [number of free cells to the left, number of free cells to the right, number of free cells in front]? \$\endgroup\$ – user202729 Aug 8 at 0:37
  • \$\begingroup\$ "The behavior must be deterministic with a fixed RNG"? (I'm not sure how to phrase this.) \$\endgroup\$ – user202729 Aug 8 at 0:43
  • \$\begingroup\$ There exists a maze master algorithm that makes the duration O(n^4) moves regardless of the adventurer algorithm, where n is the side length. \$\endgroup\$ – user202729 Aug 8 at 0:49
  • \$\begingroup\$ And I believe that asymptotically it's not possible to do better. \$\endgroup\$ – user202729 Aug 8 at 0:50
  • \$\begingroup\$ So the judge program is written in browser JavaScript? \$\endgroup\$ – user202729 Aug 8 at 14:12
  • 1
    \$\begingroup\$ Here are a couple more ideas that buff the adventurer: a) randomly generated initial maze (might make the game too stale), b) mana costs are 2 ** n instead of n + 1 (personal favorite), c) 2 adventurers, and only 1 has to reach the exit, d) adventurer can move perpendicular to the direction they're facing, e) adventurer can move any number of cells forward in a turn. I don't know how any of these affect the problem, though, as I haven't yet had time to sit down and analyze it. \$\endgroup\$ – Alion Aug 19 at 22:30
6
\$\begingroup\$

Output a unique sign sequence

A sign sequence is an infinite sequence consisting entirely of \$1\$ and \$-1\$. These can be constructed a number of ways, for example:

  • Alternating signs: \$1, -1, 1, -1, ...\$
  • \$-1\$ for primes, \$1\$ for non-primes: \$1, -1, -1, 1, -1, 1, -1, ...\$
  • All \$1\$s: \$1, 1, 1, ...\$

Your task is to write a piece of code that outputs a deterministic sign sequence that no other answer already outputs. You must include a proof that your sequence is unique from all sequences posted before yours. You do not have to worry about keeping up to date for newer answers, as they must ensure their sequences are unique, not you.

You may output in any reasonable manner, including (but not limited to):

  • Outputting an infinite list/generator/tuple of values
  • Outputting the next value in the sequence each time your code is run
  • Outputting the sequence infinitely

You may not take any input (unless necessary), so outputing the first \$n\$ terms or the \$n\$th term is not allowed.

I've included my implementation of a sequence as the first answer, to ensure that all answers have to provide a proof of uniqueness.


This is a , so the answer with the most votes wins. You should aim to do the following things in your answer:

  • Be creative. Avoid simply outputting constant runs of \$1\$s or \$-1\$s or outputting one value when a number is insert common numeric property here and the other when not (e.g. primes or Fibonacci numbers).
  • Avoid copying others. While all sequences must be unique, aim to be innovative, rather than simply slightly modify another user's sequence (for example, swapping the placements of \$1\$ and \$-1\$)
  • Make it clear what your program is doing. Not everyone can read a Jelly, R or Java answer, but they can read an explanation of the answer, as well as an explanation of how/why you chose this specific sequence and the proof of uniqueness included in your answer

Voters should consider the following when casting their votes:

  • How creative is the sequence? Has it been done to death before, or is it something you've never seen before?

  • Is it unique, or is it simply a slight modification on a sequence that many other users have done? If it is a modification, is it uncreative, or has the author seen a property that others haven't?

  • How clever is the implementation of the sequence, and how well explained is it? For this, consider both the actual code of the answer and the algorithm it implements. If the code uses a language specific trick you find particularly impressive, it may be worth an upvote. If the implementation of the algorithm is so general than any language could be used, yet is still creative and unique, it's probably worth an upvote. However, if the code is overly convoluted when a simpler method would work, or if the algorithm is incredibly inefficient when a better version exists, consider casting a downvote.

    Furthermore, while you may not be able to understand the 10 bytes of 05AB1E posted, if explained well, you should be able to get a solid understanding of how those 10 bytes implement the chosen sequence, and how clever it is. And while you may be able to fluently read Python, if poorly coded with no explanation, you may not be able to fully understand how that program works. Consider this factor when voting.

Voters should not vote for an answer for any of the following reasons:

  • The program is written in your favourite/least favourite language
    • Voting for the use of tricks within a language are fine. Voting for an answer because of the language, is not an acceptable reason
  • The program is short/long/written with ASCII characters/written without ASCII characters
  • You recognize the user who wrote the answer and you love/hate them
  • Any other reason not specified above (e.g. "This answer uses the e character, I love it!")

Meta

  • This challenge wasn't designed with as the primary focus. Rather, it's tagged that way because I can't think of any better winning criteria that would lead to the results I'm looking for. I'd love to hear any and all suggestions you have for better winning criteria, but I would like you to consider whether that criteria promotes the central focuses I'm aiming for, which are (in decreasing order of importance):

    • Interesting sequences. For example, wouldn't work, as it's reductive nature would lead people to use the more basic sign sequences
    • Interesting code. This could work for most criteria, but it shouldn't be a priority over the sequences
    • A winning criteria better than . there's no point suggesting an alternative, more objective criteria if it will reduce the importance of the previous two points.
  • challenges are difficult to make objective. I believe that I've made it as objective as I can by including voting criteria, but if you have any suggestions, I'd love to hear them

  • Is this clear enough?

  • Are there any obvious voting reasons I've missed?

  • Is this a duplicate?

  • Tags are , , . Any suggestions?

    • I'm considering because new answers depend on the previous ones. However, this is an edge case IMO of the tag, so I'd appreciate some feedback on whether to include it or not.
  • Any further feedback?

| |
\$\endgroup\$
  • 3
    \$\begingroup\$ Is shortness of the answer not supposed to be a factor at all? That is, we don't try to golf our answers? Even more, are voters supposed to consider just the sequence, or the code producing it? I'm not quite sure if "How clever is the implementation" is meant to apply to the code itself or just the general strategy. \$\endgroup\$ – xnor Sep 22 at 23:14
  • \$\begingroup\$ @xnor No, golfing your answer is unimportant, but perfectly acceptable. Voters should consider both the code and the sequence, but primarily the sequence. The code should mainly be considered for how "elegant/clever/good" the vote perceives it to be. "How clever is the implementation" kinda applies to both the code and the strategy. Using language-specific tricks are a reason to consider code "clever" as is implemented a fully generalised method that any language to pick up and use with no trouble \$\endgroup\$ – caird coinheringaahing Sep 22 at 23:34
  • 2
    \$\begingroup\$ I think this works much better as answer-chaining than as pop-con. As evidence I'd say that almost half of the challenge being devoted to explaining the voting rather than the challenge isn't a good sign. I think looking at recent successful pop-cons shows that pop-cons are generally only good if the task just won't lend itself at all to another scoring criterion. This, at least to me, seems like a great idea for answer-chaining. \$\endgroup\$ – FryAmTheEggman Sep 24 at 19:08
  • 2
    \$\begingroup\$ @FryAmTheEggman I do dislike the fact that this is a pop-con, and the only reason it is, is because I couldn't find any other criteria which would inspire the creativity in sequences I'm looking for (e.g. the reductive attitude of code golf would make this very boring). The issue I see with making it answer chaining is that the winning criteria is a bit iffy. "Second-to-last" isn't the best winning criteria as already discussed on meta, but it gets even worse when new answers aren't more difficult than previous ones, as the challenge will continue ad infinitum until (cont) \$\endgroup\$ – caird coinheringaahing Sep 24 at 19:19
  • 1
    \$\begingroup\$ (cont) people get bored and stop posting, rather than new answers are genuinely too difficult to make. There are an infinite number of sign sequences, so "running" out isn't an issue, and each new answer isn't more difficult because there are so many to choose from. Furthermore, I don't think it'd inspire the creativity I'm looking for. I don't think it'd be as bad as, say code golf, but I feel like people will resort to posting basic sequences in order to keep the chain from dying, thus extending it way beyond being fun \$\endgroup\$ – caird coinheringaahing Sep 24 at 19:20
  • \$\begingroup\$ I had initially thought that preventing the obvious abuse cases was relatively simple (no prefix/suffixes and not periodic) but I've realised that it would actually be much more difficult than that. I still think this probably works better if massaged into something that works for answer-chaining, but you are probably right that it isn't as good a fit as my first impression was. \$\endgroup\$ – FryAmTheEggman Sep 24 at 20:36
  • 1
    \$\begingroup\$ This might be interesting as a cops-and-robbers challenge, though it would have to be a finite slice of an infinite sequence in that case. \$\endgroup\$ – Beefster Oct 2 at 19:21
  • \$\begingroup\$ @Beefster I think the only (or maybe best) way this could work as a CnR is where the cops reveal their code+language (and maybe a few terms of the sequence) and the robbers have to find the generating function for that sequence, but that would almost definitely lead to obfuscated code, rather than „how is the sequence generated“ being the focal point for answerers, which pivots away from the main idea of the challenge being interesting sequences, not interesting code \$\endgroup\$ – caird coinheringaahing Oct 2 at 19:51
6
\$\begingroup\$

Almost Illegal Strings

Posted.

| |
\$\endgroup\$
  • \$\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 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 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 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 at 21:12
  • \$\begingroup\$ Rule suggestion: commenting out the almost illegal string is not allowed \$\endgroup\$ – Beefster Oct 28 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 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 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 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 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 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 at 1:10
5
\$\begingroup\$

I attempted a problem I threw out as a suggested for 1p5.

In c, lex and yacc I needed more than 9600 characters ungolfed (fully commented, errors handled, some debugging code left in place, but some efficiency sacrificed in the name of shorter code), which seems pretty long, but c is about the most pessimal language you could choose for this problem except fortran 77 or something from the Turing Tarpit. The reference implementation can run its own build, which has some of that bootstrapping voodoo.

None-the-less, this is a relatively big project, and I don't want to post it unless people feel it is both well specified and interesting.

As yet there is no validation script, and I am not sure how one could be written as the acceptable output order could be post-order depth first or post-order breadth first and there is a left-first vs. right-first ambiguity on both. What a bother.

Aside: I'm quite proud of the lex and yacc part of my code, as I consider it spiffy.


A minimal implementation of the make (1) utility.

By minimal I mean,

  • No built in rules, and no pattern or suffix rules.
  • No variables and therefore no variable assignment or manipulations; also no variable expansion which includes no expansion of environment variables.
  • No automatic variables like $< and $@.

This only leaves constructs (called rules) of the form

<target> ":" <prerequisite>* "\n" ["\t" <action> "\n"]*

Where each <target> and <prerequisite> is a whitespace delimited string which may (or may not) represent a filename. Empty lines have no effect and "#" marks the beginning of a end of line comment (the sequence "#[^\n]*\n" should be treated as "\n" so it does not interfere with rules; this has the side effect of making "#" illegal in targets, prerequisites and actions). Colons are prohibited in identifiers.

The program should take its input from the standard input or by reading a file called "makefile" - implementer's choice. The program then attempts to "build" every target named on the command line. Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error and cause the program to exit before execution of any rules. In the event that no target is named on the command line, default to building the first target in the input.

Duplicate targets may (not must!) be treated as an error.

A target is deemed already built if

  1. It names an existing file and
  2. All its prerequisites are fulfilled

Otherwise it is built by

  1. Building all unfulfilled prerequisites then
  2. Running each <action> sequentially in the order they appear in the input, and if the action returns an exceptional exit state, stopping the program.

A prerequisite is deemed fulfilled if

  • The prerequisite represents an existing file and
  • The prerequisite is built and
  • The target is "newer" than the (fully built) prerequisite

A target is deemed "older" (i.e. not "newer") than its prerequisite if one of

  • Both represent files and the prerequisite has been modified more recently than the target.
  • The target does not represent an existing file, and the prerequisite does.

apply.

Authors on systems which do not support fork/exec semantics may write a batch file or script which is invoked as the program terminates, but that script must stop on the first unsuccessful action.

Sample Input

# Babymake compatible makefile for babymake
all:babymake

babymake : lex.yy.o  y.tab.o  babymake.o 
    cc -o babymake lex.yy.o y.tab.o babymake.o

babymake.o : babymake.c babymake.h
    cc -c babymake.c

lex.yy.o: lex.yy.c y.tab.h
    cc -c lex.yy.c

lex.yy.c : babymake.l
    lex babymake.l

y.tab.o: y.tab.c babymake.h
    cc -c y.tab.c

y.tab.c : babymake.y  
    yacc -d babymake.y

clean:
    rm -f babymake.o  lex.yy.o  y.tab.o

cleaner: clean # just testing end of line comments
    rm -f y.tab.c y.tab.h
    rm -f lex.yy.c

bogus: boguser 
    echo "building bogus" # test in another context

Sample output

$ ./babymake < babymake.example cleaner
 rm -f babymake.o  lex.yy.o  y.tab.o
 rm -f y.tab.c y.tab.h
 rm -f lex.yy.c
$ ./babymake < babymake.example all    
 cc -c babymake.c
 yacc -d babymake.y
 cc -c y.tab.c
 lex babymake.l
 cc -c lex.yy.c
 cc -o babymake lex.yy.o y.tab.o babymake.o
$ ./babymake < babymake.example    
$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.
| |
\$\endgroup\$
  • \$\begingroup\$ The program should take it's input from the standard input or by reading a file called "makefile" - is this a choice for the implementer to make? Or should the program read stdin, and if it's empty then look for makefile? Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error before execution of any rules. Does "generate an error" include aborting, such that no rules are executed? Running each in sequence - missing "action"? Why is the sample input indented? I'll do an edit for punctuation in a bit. \$\endgroup\$ – Peter Taylor May 20 '11 at 21:36
  • \$\begingroup\$ In order. (1) Implementer's choice. Should be more specific. (2) Generate an error means abort; this is a unix utility after all. (3) The sample is indented because I made a strenuous effort to get the tabs in, and MarkDown just doesn't like tabs. Also there is a new sample input that has some comments in. \$\endgroup\$ – dmckee --- ex-moderator kitten May 20 '11 at 21:49
  • \$\begingroup\$ More questions: 1) The target is "newer" than the prerequisite once *they* have been fulfilled. What does this mean? Should this text be talking about building? 2) Under what circumstances can a target be built twice? \$\endgroup\$ – Peter Taylor May 21 '11 at 19:51
  • \$\begingroup\$ 1) Yes and 2) Standard make never builds a target twice, and neither does my reference implementation. But I should probably say that it is or is not allowed. Do you have a feeling in the matter? \$\endgroup\$ – dmckee --- ex-moderator kitten May 21 '11 at 20:43
  • \$\begingroup\$ Saying that it is not allowed is probably best. Otherwise there's potential for stuff to go wrong when multiple targets depend on clean, which will never be built because it doesn't correspond to a file. \$\endgroup\$ – Peter Taylor May 21 '11 at 21:15
  • 1
    \$\begingroup\$ I suggest that the golf exercise be to simply output the list of commands to run, not actually execute them. Will make testing much easier. \$\endgroup\$ – MtnViewMark May 27 '11 at 0:50
  • \$\begingroup\$ This is awesome. But I'm too mystified by make to even fathom how it goes about it. I'd never be able to do this without stealing ideas from other posts on the page. But then, I'm an introverted intuitive, intellectuals would probbly have an easier time. :) I haven't checked, but .. I say it's ready to post. Answers may be slow in coming, but they WILL come! \$\endgroup\$ – luser droog Nov 23 '12 at 4:45
  • \$\begingroup\$ @luserdroog my reference implementation builds a directed graph (in the technical sense) of dependencies and then starts evaluating from the named target(s). I can't recall right off if I enforced acycality on the graph or not. I believe that real make insists on it. \$\endgroup\$ – dmckee --- ex-moderator kitten Nov 23 '12 at 5:10
  • \$\begingroup\$ That doesn't semm quite so unfathomable. I suppose the variables and impicit rules are responsible for much of the mystery. \$\endgroup\$ – luser droog Nov 23 '12 at 5:45
  • \$\begingroup\$ This has been inactive for five years. If you're not going to post it, may I? \$\endgroup\$ – MD XF Aug 17 '17 at 16:59
  • \$\begingroup\$ @MDXF I think I'd rather post this one myself, but it may be a few days. \$\endgroup\$ – dmckee --- ex-moderator kitten Aug 17 '17 at 19:51
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\$
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\$
  • \$\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\$ – FryAmTheEggman Feb 4 '15 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 '15 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\$ – FryAmTheEggman Feb 4 '15 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 '15 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\$ – Peter Taylor Feb 4 '15 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 '15 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\$ – Peter Taylor Feb 4 '15 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 '15 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\$ – Peter Taylor Feb 4 '15 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 '15 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 '15 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\$ – Peter Taylor Feb 4 '15 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\$
  • 7
    \$\begingroup\$ 2. Lego pieces/attachable cubes \$\endgroup\$ – trichoplax Jan 25 '15 at 21:07
  • 2
    \$\begingroup\$ 5. Controller-mediated build-your-own data structure \$\endgroup\$ – trichoplax Jan 25 '15 at 21:11
  • \$\begingroup\$ A. Lego pieces. \$\endgroup\$ – trichoplax Jan 28 '15 at 8:35
  • 6
    \$\begingroup\$ B. Attachable unit cubes (for simplicity) \$\endgroup\$ – trichoplax Jan 28 '15 at 8:36
  • \$\begingroup\$ Winning criteria: \$\endgroup\$ – Sp3000 Jan 28 '15 at 23:43
  • 2
    \$\begingroup\$ I. Code golf (fewest bytes) \$\endgroup\$ – Sp3000 Jan 28 '15 at 23:43
  • 7
    \$\begingroup\$ II. Fastest algorithm \$\endgroup\$ – Sp3000 Jan 28 '15 at 23:44
  • \$\begingroup\$ III. Something else (leave a comment below) \$\endgroup\$ – Sp3000 Jan 28 '15 at 23:45
  • 1
    \$\begingroup\$ Number of cube structures: \$\endgroup\$ – Sp3000 Jan 29 '15 at 0:42
  • \$\begingroup\$ 1. Exactly one structure \$\endgroup\$ – Sp3000 Jan 29 '15 at 0:42
  • 3
    \$\begingroup\$ 2. Any number of structures \$\endgroup\$ – Sp3000 Jan 29 '15 at 0:43
  • \$\begingroup\$ Connections/adjacency: \$\endgroup\$ – Sp3000 Jan 29 '15 at 0:43
  • 3
    \$\begingroup\$ A. Connections should be explicitly given via a function call \$\endgroup\$ – Sp3000 Jan 29 '15 at 0:44
  • \$\begingroup\$ B. Each cube is connected to the cube it was built off \$\endgroup\$ – Sp3000 Jan 29 '15 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 '15 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\$
  • 1
    \$\begingroup\$ Could you give a more precise definition of 'most likely'? \$\endgroup\$ – feersum Jun 7 '15 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 '15 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 '15 at 22:20
  • \$\begingroup\$ @feersum I'm not sure what you mean. Highest probability? Least improbable? \$\endgroup\$ – Sparr Jun 8 '15 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 '15 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\$ – Peter Taylor Jun 9 '15 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 '15 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\$ – Peter Taylor Jun 10 '15 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\$
  • \$\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 '15 at 15:38
  • \$\begingroup\$ @Zgarb Thanks for your feedback! I've included a section on how the game works. \$\endgroup\$ – ASCIIThenANSI Apr 7 '15 at 15:53
  • \$\begingroup\$ Could you add C# (or .NET in general?) \$\endgroup\$ – LegionMammal978 Apr 7 '15 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\$ – ASCIIThenANSI Apr 7 '15 at 15:56
  • \$\begingroup\$ @ASCIIThenANSI you could use Mono. I'm mainly just looking for C#. \$\endgroup\$ – LegionMammal978 Apr 7 '15 at 16:02
  • \$\begingroup\$ @LegionMammal978 Oh, OK. Turns out I installed it for an earlier purpose, thanks for your help! \$\endgroup\$ – ASCIIThenANSI Apr 7 '15 at 16:09
  • 1
    \$\begingroup\$ It's not complete, but this question has instructions for running a number of languages. \$\endgroup\$ – Peter Taylor Apr 15 '15 at 22:15
  • \$\begingroup\$ @PeterTaylor Thanks for the link! \$\endgroup\$ – ASCIIThenANSI Apr 16 '15 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\$ – Paŭlo Ebermann Oct 11 '15 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\$ – ASCIIThenANSI Oct 12 '15 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\$
  • 4
    \$\begingroup\$ I like the restricted source version \$\endgroup\$ – quintopia Dec 9 '15 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\$ – Digital Trauma Dec 9 '15 at 20:18
  • 1
    \$\begingroup\$ @ quintopia - yes, I think that's probably the way to go - edited. \$\endgroup\$ – Digital Trauma Dec 9 '15 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 '15 at 5:58
  • 1
    \$\begingroup\$ @geokavel yes, and yes. \$\endgroup\$ – Digital Trauma Dec 10 '15 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 '15 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 '15 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\$
  • \$\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\$ – Level River St Dec 21 '15 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\$ – Level River St Dec 21 '15 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\$ – Martin Ender Dec 21 '15 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\$ – Peter Taylor Dec 21 '15 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\$ – Level River St Dec 21 '15 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\$ – Martin Ender Dec 21 '15 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\$ – Level River St Dec 21 '15 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\$ – Peter Taylor Dec 21 '15 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\$
  • \$\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 '16 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\$
  • \$\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 '16 at 0:09
  • \$\begingroup\$ @David Thanks for catching that. I will fix it tomorrow, \$\endgroup\$ – Arcturus Feb 16 '16 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\$ – Martin Ender Feb 16 '16 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\$ – AdmBorkBork Feb 16 '16 at 15:08
  • \$\begingroup\$ @TimmyD The emphasis in my sentence was on "more". ;) (I admit that may not have been obvious.) \$\endgroup\$ – Martin Ender Feb 16 '16 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\$ – AdmBorkBork Feb 16 '16 at 15:15
  • \$\begingroup\$ @TimmyD I like ambiguity more than most people. \$\endgroup\$ – Martin Ender Feb 16 '16 at 15:22

You must log in to answer this question.

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