449
\$\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\$
  • 2
    \$\begingroup\$ Suggestion: instead of having a notice on the top answer ("note: if you are..."), you'd better just put a moderator notice below the question \$\endgroup\$ – nicael Mar 19 '18 at 19:35
  • 3
    \$\begingroup\$ @nicael We can only choose from three post notices: citation needed, current event, and insufficient explanation. \$\endgroup\$ – Dennis Apr 7 '18 at 14:43
  • \$\begingroup\$ If you remove a post but didn't post it you can replace the text body with [](lots of text here to reach the min chars) to make it much smaller when removed \$\endgroup\$ – Christopher Apr 13 '18 at 17:54
  • 5
    \$\begingroup\$ @Christopher Please don't do that for old proposals. It clutters the first page with an answer nobody cares about anymore, instead of staying hidden on page 10 where it will bother nobody. \$\endgroup\$ – Dennis Apr 13 '18 at 18:17
  • \$\begingroup\$ @Dennis ? what are you talking about. As if if you didn't post it like you just removed you own sandbox because dupe or something \$\endgroup\$ – Christopher Apr 13 '18 at 18:18
  • 4
    \$\begingroup\$ @Christopher If your proposal is still on the first few pages, you can replace the proposal with a stub to save vertical space on these pages. However, if your proposal is already on page 10, editing your proposal will bump it to page 1, where space is more precious than on page 10. \$\endgroup\$ – Dennis Apr 13 '18 at 18:21
  • \$\begingroup\$ @Dennis ohh that makes sense \$\endgroup\$ – Christopher Apr 13 '18 at 18:25
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/12599/… \$\endgroup\$ – Redwolf Programs Apr 17 '18 at 17:38
  • 1
    \$\begingroup\$ Maybe it's time to consider cleaning some of this up a bit. There's just too much to go through and some of these proposals are years old and obviously not going anywhere (even some of the good ones). Perhaps cull anything that is two years old and has likewise been inactive for as long? \$\endgroup\$ – ouflak Aug 6 '18 at 9:07
  • 1
    \$\begingroup\$ @ouflak You can sort posts by "active". That seems to resolve all of the problems you describe. \$\endgroup\$ – FryAmTheEggman Sep 27 '18 at 19:04
  • \$\begingroup\$ I already posted this, but codegolf.stackexchange.com/questions/176599/… \$\endgroup\$ – 2br-2b Nov 27 '18 at 2:38
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ It seems like there is a rollback war with moderators and the Community user to add and remove the featured tag. \$\endgroup\$ – smileycreations15 Mar 21 at 21:13
  • 3
    \$\begingroup\$ @smileycreations15 That's unfortunately unavoidable. Community is an automatic script, and, since most featured questions are only temporarily so, it assumes that we don't want this question to be featured forever. However, we do, so a mod has to edit the tag in every now and then. \$\endgroup\$ – Erik the Outgolfer Mar 24 at 15:22
  • 3
    \$\begingroup\$ @EriktheOutgolfer Yeah. Maybe they can create a special [featured-pin] tag which will both feature it and pin it from removal by the Community user. \$\endgroup\$ – smileycreations15 Mar 24 at 17:20

2477 Answers 2477

0
\$\begingroup\$

Iterated Matrix Multiplication

Given an nxn matrix A, an nx1 matrix X, and a list L of ordered pairs in [0,n)x[0,n), determine if there exists some integer k>=0 such that, with B=A^k*X, for all (D,E) in L, B[D]<B[E].

Why it's possible: Every entry of the natural number power of a general matrix can be expressed via sums of multiples of powers of the matrix's eigenvalues, like 2^k+4*6^k-10*3^k, and for any two such expressions, there will always be some k beyond which one term dominates the expression, and the sign of their difference can no longer change, so one way to solve the problem would be to calculate that k.

Test cases:

[[1,2],[2,3]],[3,4],[(0,1)] -> Yes (k=0)
[[1,2],[2,3]],[3,4],[(1,0)] -> No
[[1,2],[2,3]],[4,3],[(1,0)] -> Yes (k=0)
[[1,2],[2,3]],[4,3],[(0,1)] -> Yes (k=1)
[[1,-2],[2,-3]],[3,4],[(1,0)] -> Yes (k=1)
[[-1,-2],[2,-3]],[3,4],[(1,0)] -> Yes (k=2)
[[-1,-2],[2,-3]],[3,4],[(1,0),(0,1)] -> No
\$\endgroup\$
  • 1
    \$\begingroup\$ 1. For fastest-code you need to describe how you will measure it, selecting a test size which is large enough to give meaningful differences but small enough to be feasible. That probably means that you need to write a reference implementation or three (trying difference approaches). 2. For floating point questions, you need to do some numerical analysis to determine on what range of input it's feasible to write a correct program, and then guarantee that the input will be within that range. 3. You need to think about what level of library support is fair. \$\endgroup\$ – Peter Taylor Apr 13 '16 at 8:54
0
\$\begingroup\$

Colorize!

In Ruby, the colorize gem allows you to output text to the terminal in pretty colors:

Blue, bold text saying "This is a box"

It uses the ANSI color standard to tell the terminal how to color things, then trusts that the terminal will do the right thing. For this challenge, you can too.

What you'll do is take a a pair of lidts of strings, in whatever format you want. For example, if you wanted comma-separated values:

+-----+,| box |,+-----+
red,blue,red

The first list is what you'll be colorizing. The second list is a list of color names that are the same as the ones in the Wikipedia article. You'll colorize each string from the first list with the respective color from the second. The two lists will always have the same number of items, and the second will only ever contain valid color names. The strings in the first will only contain valid, printable ASCII characters.

And apply those colors -- as given by the ANSI standard linked above -- to the text, printing each string on its own line. For example, with this (heavily ungolfed) code:

#to be written

you'd get this:

[picture of result]

You may not use any libraries built to do this, and the standard loopholes are disallowed.


I'm thinking of adding extra credit for bolding/doing multiple things at once. Is that a good idea?

Aside from that, how is the rest of the challenge?


To-do list:

  • Copy the list from Wikipedia to here
  • Add pictures, demo code
  • Add that you have to change the color back to default at the end
\$\endgroup\$
  • \$\begingroup\$ The comma separated thing seems unnecessary, in most languages this just adds a boring split(',') call. You also probably want to only allow printable ASCII in the body of the strings (or at least put some restriction otherwise stuff can get pretty hairy). In addition you should explain what is necessary to know from the ANSI standard in your question body. \$\endgroup\$ – FryAmTheEggman Apr 13 '16 at 13:03
  • \$\begingroup\$ @FryAmTheEggman I linked the relevant part and stated "ANSI color standard" when it was first mentioned. What input format would you suggest that can deliver a set of lines to colorized and a set of colors to use? \$\endgroup\$ – Nic Hartley Apr 13 '16 at 13:22
  • \$\begingroup\$ Just say what they are: a list of strings and a list of colours. The link doesn't matter: if Wikipedia is down or they change that page so it doesn't help here then I can't answer your question without guessing what you mean. Also, the reason I said printable ASCII is that some ASCII is still hard to deal with. What about control characters, etc.? \$\endgroup\$ – FryAmTheEggman Apr 13 '16 at 13:27
  • \$\begingroup\$ @FryAmTheEggman Oh, I see. I'll update it to have "input of two lists in whatever format you want" and "printable ASCII characters only". As for requiring Wikipedia to be up, I'll copy and paste it when I have time. However, note that ANSI's standards are available online, and Googling "ANSI color standard" yields their website as well. Wikipedia is far more readable. \$\endgroup\$ – Nic Hartley Apr 13 '16 at 13:32
0
\$\begingroup\$

I'm a Puzzle!

Your task is to print the string "I'm on OS!", where OS is the operating system that the program is run on without version numbers.

Standard loopholes apply.

In addition, programs with hardcoded values (e.g. print "I'm on AFakeOS") will be disqualified.

As this is Code Golf, your score will be the length of your full program.


Any suggestions?

Java example:

class A {
    public static void main(String[] args){
        System.out.println("I am a " + System.getProperty("os.name").replaceAll(" .*","")
                                     + "!");
    }
}
\$\endgroup\$
  • 5
    \$\begingroup\$ When making something in Java, "noncompetitive" is implicit. \$\endgroup\$ – Cyoce Feb 13 '16 at 7:31
  • 1
    \$\begingroup\$ :P I've been lurking and waiting for an idea long enough to know. \$\endgroup\$ – 0az Feb 13 '16 at 13:07
  • \$\begingroup\$ "If run in a browser (JavaScript and/or any other browser scripting languages), the browser should be output instead." Why is that? I'm pretty sure you can detect the operating system even if you're in a browser. \$\endgroup\$ – Martin Ender Feb 13 '16 at 17:40
  • \$\begingroup\$ And my suggestion for "other bonuses, penalties, ..." is drop all of them. \$\endgroup\$ – Martin Ender Feb 13 '16 at 17:40
  • \$\begingroup\$ Added Java example solution. Removed bonuses. Read the linked question. \$\endgroup\$ – 0az Feb 13 '16 at 21:32
  • 1
    \$\begingroup\$ Exactly what is acceptable output? If Windows 10, is Windows? Windows 10? Windows NT Version 10.[build n]? \$\endgroup\$ – lirtosiast Feb 14 '16 at 5:24
  • \$\begingroup\$ How portable does this need to be? E.g. would uname -o be acceptable? \$\endgroup\$ – Peter Taylor Feb 15 '16 at 12:46
  • \$\begingroup\$ Considering that uname prints Darwin on my MacBook, and -o is an illegal option, uname -o would not work. I guess a possible definition of portable would be "works correctly on OS X, Windows, and most of the more common Linux distros" \$\endgroup\$ – 0az Apr 18 '16 at 3:01
  • \$\begingroup\$ @alphadelta That entails unambiguously defining the operative words most of the and more common in the phrase most of the more common Linux distros, which is objectively impossible. \$\endgroup\$ – cat Apr 24 '16 at 2:14
  • \$\begingroup\$ Perl 5, fourteen bytes as a subroutine: {"I'm on $^O!"} (where ^O is actually the F byte). (Fifteen as a program that prints: say"I'm on $^O!".) I can only imagine that the golfing languages will get down to one or two bytes, then. :-) \$\endgroup\$ – msh210 Apr 26 '16 at 22:32
0
\$\begingroup\$

@Sandbox:

  • Not sure if is correct here.
  • Do I need test cases for this? They will make this very lengthy.

Tags:

Find the structs!

The Challenge

Given a piece of C-code, add a /* before and a */ after every top-level structure definition that you find. You may not do this for structures that are defined inside other structures.

  • A structure can be identified by the struct keyword followed by an identifier, an opening {, some alphanumeric characters inside the structure and a closing };.
  • A structure identifier will only consist of alphanumeric characters.
  • One structure may also contain other structures with an unlimited depth.
  • Comments and whitespaces may appear anywhere in the code and have no effect. // starts a single line comment and code enclosed in /* and */ is a multiline comment.
  • You can't rely on a specific indentation style.
  • A structure will not contain any braces {} that are not part of another structure definition.
  • There can be multiple top-level structures in the input. You have to consider them all.
  • The input will only contain printable ASCII and newlines.

Example

So the output for

int z;
struct example1 /* comment here */  {
    int x; // struct comment {int x;};
    struct nested
    {
        char* s;
        int* y;
    };
};
int y;

//struct { };

struct example2{int x;};

would be

int z;
/*struct example /* comment here */  {
    int x; // struct comment {int x;};
    struct nested
    {
        char* s;
        int* y;
    };
};*/
int y;

//struct { };

/*struct example2{int x;};*/

Rules

Happy Coding!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this has some problems, as most questions that say "Given some C code do...", with what counts as valid. What about things like trigraphs, or macros or... ? \$\endgroup\$ – FryAmTheEggman Apr 13 '16 at 17:56
  • \$\begingroup\$ @FryAmTheEggman So it would be fine, when I limit the possible code-contents to a certain subset of C like I did for the struct contents? \$\endgroup\$ – Denker Apr 13 '16 at 19:00
  • \$\begingroup\$ Yeah, but I'm not well versed enough in C grammar to be able to say for sure that that'll be enough. \$\endgroup\$ – FryAmTheEggman Apr 13 '16 at 19:05
  • \$\begingroup\$ @FryAmTheEggman Thought about this and I actually don't need all that C-syntax stuff. Just came from the origin of this, but it's no really needed. Should be clear now. \$\endgroup\$ – Denker Apr 13 '16 at 20:23
  • \$\begingroup\$ Please work on your spelling before posting this, if you do. \$\endgroup\$ – Nic Hartley Apr 14 '16 at 18:52
  • \$\begingroup\$ @QPaysTaxes You can't fault OP for speaking ESL; this is why anyone can edit posts on SE. \$\endgroup\$ – cat Apr 24 '16 at 1:20
  • \$\begingroup\$ @cat That's actually wrong. You can't suggest edits on meta, and this answer isn't CW, so I'm not able to edit this. If you'd like to confirm, take any of your accounts with less than the required rep, go to meta, and try to edit something. It doesn't let you. \$\endgroup\$ – Nic Hartley Apr 24 '16 at 2:04
  • \$\begingroup\$ @QPaysTaxes I'm aware there are no suggested edits on Meta, because that would mean more, more clogged review queues for popular sites. I meant when the challenge is posted which is the only time small grammar things will matter anyhow, and I tend to be the type to fix that stuff. \$\endgroup\$ – cat Apr 24 '16 at 2:08
  • \$\begingroup\$ @cat Oh, I see. I thought you meant I should edit the Sandbox post, which... I can't. I've been told several times to "just edit it!" on various Metas where I don't have permission; I have yet to be told "edit it when this is on main" :P \$\endgroup\$ – Nic Hartley Apr 24 '16 at 2:11
0
\$\begingroup\$

Spiral text

Write a function or program that given a text with one or more characters in it outputs the text as a square spiral. The first letter of the text must be the center of the spiral and then all the characters must follow a clockwise spiral pattern as follow, striping all white spaces:

           789[10]
           612[11]
           543[12]
              [13]

Example

Input: Hello World!
Output:

               ORLD
               WHE!
               OLL

The text could be any length. Please validate with the following texts:

Once upon a time

Expected output:

o   n   a   t
p   o   n   i
u   e   c   m
            e


Tyger Tyger, burning bright, In the forests of the night; 

Expected output:

g   h   t   ;           
i   i   g   h   t,  I   n
n   r   y   g   e   r   t
e   b   t   t   y   ,   h
h   g   r   e   g   b   e
t   n   i   n   r   u   f
f   o   t   s   e   r   o

The minimung length of the input text is one character.

Note: Somewhat similar to this question

\$\endgroup\$
  • \$\begingroup\$ Test cases are more useful if you also include the expected output. ;) \$\endgroup\$ – Martin Ender Apr 29 '16 at 9:16
  • \$\begingroup\$ @MartinBüttner yay! Doing that \$\endgroup\$ – Averroes Apr 29 '16 at 9:17
  • 1
    \$\begingroup\$ Also having to support the empty string seems like an annoying special case that isn't likely to add anything interesting to most answers, so I'd personally probably let the input have at least one character, but that's your call. \$\endgroup\$ – Martin Ender Apr 29 '16 at 9:18
  • \$\begingroup\$ When you say "somewhat similar": why should I not vote to close it as a duplicate? It seems that the only difference is a reflection in the leading diagonal, which I would class as trivial. \$\endgroup\$ – Peter Taylor Apr 29 '16 at 11:55
  • \$\begingroup\$ @PeterTaylor First of all the other question doesn't have any answer and it is a bit old so maybe now this question can get a little more audience now. Secondly the other question add "The characters can spiral into previous characters" that this doesn't add to the specs so I think they are different questions. \$\endgroup\$ – Averroes Apr 29 '16 at 12:39
  • \$\begingroup\$ Ok, the other question is horrible. This is actually more like various spiralling numbers questions, with the main difference being that it spirals outwards rather than inwards. \$\endgroup\$ – Peter Taylor Apr 29 '16 at 12:52
0
\$\begingroup\$

You have an even number of identical balls. Half of them are "Light" balls and other half are "Heavy" balls which are heavier than the light balls for a unknown amount. You have to separate them into the "Light" box and a "Heavy" box using a scale instrument which tells you precisely for how much the left side is heavier than the right side when the balls are weighted on it.

Find a way to separate a given number of the balls with the minimal weightings as possible.

This is a challenge to programmatically reslove this question.


The solution should be an algorithm that would separate the given amount of balls with the least weightings as possible.

The Input can be any even number of balls, where the heavy balls will differ in weight from the light balls by a random amount. The balls are marked from 1 to n, and the "heavy" and "light" properties are assigned to all the balls randomly.

Now the program can take any number of balls and place it on the "right" side of a "scale" and then another amount of balls to be placed on the "left" side of the scale. It can read for how much exactly one side is heavier than the another, and then it can proceed to weight another set of balls until he can for sure tell for each numbered ball if it is "light" or "heavy". It should know how to process this in a least "weightings" or "uses of the scale" as possible.

So the goal is to write the most efficient program that can most efficiently separate the balls using the minimal amount of "weightings", and doing that for as many cases of given balls as possible.

\$\endgroup\$
  • 1
    \$\begingroup\$ This seems too simple. The optimal algorithm is well-known to the point where it's a common interview question. It would just be a race to be the first to implement it in the chosen language. \$\endgroup\$ – Mego Apr 29 '16 at 19:17
  • \$\begingroup\$ @Mego Thank you for your review, Btw How would one write such an algorithm? Does something like that already exists? My main point of posting this was to answer that question, I would appriciate if you have any way of providing any help. \$\endgroup\$ – Vepir Apr 29 '16 at 19:25
  • \$\begingroup\$ @Mego The "interview" question you're thinking of is probably a version with one different weight, as pointed out in the linked question. This seems challenging enough; one could even consider comparing different numbers of balls. \$\endgroup\$ – feersum Apr 29 '16 at 20:45
  • 1
    \$\begingroup\$ What this needs to be a good question is some kind of output specification, e.g. giving the expected number of comparisons, an interactive protocol with the user giving comparison results, or some kind of tree decision representation. \$\endgroup\$ – feersum Apr 29 '16 at 20:47
  • \$\begingroup\$ I would just set a pivot ball (e.g. the first one) and compare everything else with it. Runtime complexity O(n). \$\endgroup\$ – Leaky Nun Apr 30 '16 at 14:36
  • \$\begingroup\$ @Kennylau but that is exactly the oposite of the solution. You would have then too many unecessary weightings, since the goal is to do it in least possible weightings no matter how complex the real solution might be \$\endgroup\$ – Vepir Apr 30 '16 at 15:11
0
\$\begingroup\$

Is this a helpful starting layout?

My computer has a Patience-style card game installed on it. It takes two packs of cards, removes the Aces, shuffles them, and deals 8 cards.

In order to maintain my 100% perfect completion record, I want as helpful a starting layout as possible. Deuces are immediately playable, so they are helpful cards. However other cards can only be played on cards of descending rank and opposite colour, which means that cards of the same rank and colour unhelpfully clog up the layout.

The challenge is to write a program or function which accepts a string or list of eight cards and outputs a truthy or falsy value. Cards are identified by their rank, which is one of the characters 23456789TJQK, and their suit, which is one of the characters CDHS. (Note that using numbers 10-13 for the rank is not an acceptable input.) For a layout to be helpful there must be at least one Deuce of any rank, and (except Deuces) there must not be any pairs of cards with the same rank and colour. Examples:

4H7STHTD5C5D2HQS -> unhelpful because of two red Tens
TD8S4CKC4HKD5S5H -> unhelpful because of no Deuces
2H7SJH3S4HKS7H3H -> helpful layout

This is , so the shortest program wins.

\$\endgroup\$
  • \$\begingroup\$ At first I thought this was a request for help, not the setting for a problem. You'll want to add what those inputs mean, what "a helpful layout" means, in detail. \$\endgroup\$ – Nic Hartley May 2 '16 at 18:19
  • \$\begingroup\$ As I understand, this can be solved by checking if the string contains 2 and its chunks of two are distinct, which seems pretty straightforward. \$\endgroup\$ – xnor May 3 '16 at 11:46
  • \$\begingroup\$ @xnor Not quite distinct, since a) you have to ignore the chunks that contain 2 and b) H==D and S==C for the purposes of comparison. \$\endgroup\$ – Neil May 3 '16 at 11:57
0
\$\begingroup\$

Solve for the Operators

In this challenge, you will be given a bunch of numbers and an answer. Your job is to find a sequence of operators that will successfully solve this equation. Use the numbers in the order that they are given

Operators: +, -, *, /

For example,

Numbers given: 2, 6, 8, 4, 5

Answer: 9

2__3__8__4__5 = 9

The program should find which operators can be used in the blanks to make the equation true. Remember Order of Operations Matters (PEMDAS)

Output:

2*3-8/4+5 = 9

Only 1 solution is needed per problem

Rules

  1. No built-in math functions beyond operators.
  2. Must Follow Order of Operations
  3. Must give one correct output.
  4. Least Number of Bytes Wins.

Examples:

Numbers: 4, 4, 4, 4

Answer: 0

4 - 4 + 4 + 4 = 0

Numbers: 1, 8, 6, 4, 5, 2, 3, 3

Answer: -35

1*8+6-4*5*2-3*3 = -35

Numbers: 1, -2

Answer: 3

1--2 = 3
\$\endgroup\$
  • 2
    \$\begingroup\$ In many languages, this will just be "find the cartesian product of +-*/ repeated as many times as there are blanks with itself, insert them over the blanks and call eval". It's fine if you want that, but it seems somewhat, uh, boring? \$\endgroup\$ – FryAmTheEggman May 5 '16 at 13:26
  • 1
    \$\begingroup\$ 4 - 4 + 4 + 4 = 8 \$\endgroup\$ – trichoplax May 5 '16 at 13:30
0
\$\begingroup\$

Make a times table sheet

The challenge is to make an ascii art version of a times table sheet.

Look at the following:

times tables.

Your answer should have the same layout as this table:

  • You should not include the title or the footer or worry about colors. Black and white is fine.
  • The times tables lines in each box should be randomly ordered.
  • You should include all the horizontal and vertical lines in the image (except in the header and footer).
  • The equals signs should be aligned in each column as in the example above.
  • It should be in ASCII art.

I am not worried about the precise spacing as long as the layout is as specified.

\$\endgroup\$
  • \$\begingroup\$ no ascii art for me? \$\endgroup\$ – Leaky Nun May 6 '16 at 17:41
  • \$\begingroup\$ @KennyLau I could make it ASCII art if people love that. \$\endgroup\$ – user9206 May 6 '16 at 18:22
0
\$\begingroup\$

Challenge

Create a factor tree from a number. A factor tree will take a number > 1, n, and find 2 numbers that multiply together to equal n that are greater than 1. Then, it will repeat for the factors until every section reaches a number that does. Then it will output the last numbers.

For example:

enter image description here

Examples:

Input: n = 20

Graph(This is not the output):

enter image description here

Output: 2x2x2x3

Input: n = 54

Output:2x3x3x3

Input: n = 72

Output: 3x3x2x2x2

Input: n = 2

Output: 2

Scoring

Shortest bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you mean a factor tree, not factorial. That is very different. \$\endgroup\$ – Rɪᴋᴇʀ May 7 '16 at 3:11
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ yes that is what i meant. Thank you \$\endgroup\$ – JoshK May 7 '16 at 3:18
  • \$\begingroup\$ Would it be more interesting if i had the output be the tree instead of the numbers? \$\endgroup\$ – JoshK May 7 '16 at 3:20
  • \$\begingroup\$ yeah, I think the numbers is probably a dupe. Plus, it would be more fun/hard. (hard isn't bad) \$\endgroup\$ – Rɪᴋᴇʀ May 7 '16 at 3:20
  • \$\begingroup\$ I recommend having output be a image/ascii art, though that needs more specifications. \$\endgroup\$ – Rɪᴋᴇʀ May 8 '16 at 20:31
  • \$\begingroup\$ As it stands, this is a duplicate of codegolf.stackexchange.com/questions/1979/factorize-me \$\endgroup\$ – Mego May 13 '16 at 5:27
0
\$\begingroup\$

The incremental Gijswijt's sequence

The Gijswijt's sequence G is a sequence where the next term is the maximal number of repeating blocks of terms going so far backward.

The first numbers of this series are: 1, 1, 2, 1, 1, 2, 2, 2, 3

The incremental Gijswijt's sequence I is a sequence of Gijswijt's indices where any term of this last sequence I(n) has an image in Gijswijt G(I(n)) that is greater or equal all terms that precede it in that sequence G .

In other terms, It is an increasing sequence of indexes i for which G(i) is at least as large as G(j) for any j < i. Thus it contains the index of every 1 up to the first 2, every 2 up to the first 3, etc

Example:

  G= 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3,...

  I= 1, 2, 3,       6, 7, 8, 9,                        18,                           28,                        37,...

Your program must output the most you can print from the starting of sequence until the delay between printing two consecutive terms exceeds 10 minutes, the actual number of outputs is your score.

For matter of reliability, the complete accurate "run-lengthed" G sequence must be linked through pastbin or any raw data repository.

the output will be so large to fit an int32 registry, so i suggest to print it modulo 1000007 or dont.

if the scores are not be divergent enough i will apply some salt, scoring is evaluated to N/T where T is executon time in seconds for the last term of sequence, the tie broken by the earlier post .

Only another 45 secs after the delay cap are given as an extra time.

\$\endgroup\$
  • \$\begingroup\$ I would VTC as unclear. \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 16:08
  • \$\begingroup\$ hmmm what is unclear ? \$\endgroup\$ – Abr001am May 4 '16 at 16:08
  • \$\begingroup\$ Winning criterion. until nothing appears in the console for 10 minutes is a bit vague. \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 16:08
  • \$\begingroup\$ 10 minutes from last output, is this what u asked me to clarify ? \$\endgroup\$ – Abr001am May 4 '16 at 16:10
  • \$\begingroup\$ "nothing appears" is a bit vague. I think you want something more like "the time to calculate the next term is > 10 minutes." \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 16:11
  • \$\begingroup\$ yes when it exceeds that cap, execution must be halted \$\endgroup\$ – Abr001am May 4 '16 at 16:12
  • \$\begingroup\$ .. I mean the wording in unclear. Can you say something like the time to calculate rather than the console is empty? \$\endgroup\$ – Rɪᴋᴇʀ May 4 '16 at 16:15
  • \$\begingroup\$ if that makes you contented .... \$\endgroup\$ – Abr001am May 4 '16 at 16:18
  • 1
    \$\begingroup\$ I found the definition rather hard to follow, and technically it defines an uncountable number of sequences. I suggest "The incremental Gijswijt's sequence is the (increasing) sequence of indexes i for which G(i) is at least as large as G(j) for any j < i. Thus it contains the index of every 1 up to the first 2, every 2 up to the first 3, etc. If you are familiar with the Records transform on integer sequences, this is effectively a Non-strict Records transform." \$\endgroup\$ – Peter Taylor May 7 '16 at 8:55
  • 1
    \$\begingroup\$ "For matter of reliability, the complete accurate "run-lengthed" G sequence must be linked through pastbin or any raw data repository." Why? If it's generated by the same process, it would have the same bugs. If it isn't, I don't see the point of asking every single answer to include a pastebin link. "i suggest to print it modulo 1000007 or dont." Either make this a requirement or don't. It complicates comparison of answers to make it optional. "Only another 45 secs after the delay cap are given as an extra time." Extra time for what? \$\endgroup\$ – Peter Taylor May 7 '16 at 8:59
  • \$\begingroup\$ @PeterTaylor 1. That is because it a contest for scores in increment, so any new record must be followed by a string of compressed numbers from the last terminus reached, until the new record using his own technique imagine the new score is 2 numbers far from the last result ? the algorithm must print a correct G series that is ground of I series. \$\endgroup\$ – Abr001am May 7 '16 at 10:47
  • \$\begingroup\$ 2. The numbers could be too big and unintelligible, so either print a remainder or the difference of two edges or print it all along the console modulo something. \$\endgroup\$ – Abr001am May 7 '16 at 10:49
  • \$\begingroup\$ 3. extra time for me to stop execution. \$\endgroup\$ – Abr001am May 7 '16 at 10:49
  • \$\begingroup\$ a compressed string of numbers * in the first note \$\endgroup\$ – Abr001am May 7 '16 at 11:31
0
\$\begingroup\$

Inverse Square Probability

It's a fairly well-known fact that the sum of the reciprocals of squares is equal to pi squared divided by 6. That is,

Basel Problem

This is the Basel problem and was solved by Euler in 1735. I was thinking about generating a random patchwork of squares and trying to decide how to weight the probabilities of different square sizes, when it occurred to me that I could use this fact and make the probability of choosing a square's size be the inverse of its size.

For instance, if I pick a random point on the interval [0..pi^2/6), then based on the point I pick, r, I can translate it to a square size in the following manner (all numbers rounded to 3 decimal places):

0     <= r < 1     => s = 1
1     <= r < 1.25  => s = 2
1.25  <= r < 1.361 => s = 3
1.361 <= r < 1.424 => s = 4
1.424 <= r < 1.464 => s = 5
...

Your program or function should work for any input within the limits of your language (for instance, floating point precision, lack of built-in bignum capabilities, etc). Input will always be 0 <= r < pi^2/6.

Test Cases

{to be added}
\$\endgroup\$
0
\$\begingroup\$

Functional Programming in Your Language

A lot of modern programming languages allow some form of functional programming, but I don't often see them used. I'm curious to see how different languages tackle problems that are naturally solved with some form of functional programming. The winning entry to this contest will have the shortest total code as measured in bytes for these four questions

  1. Given a three-part list, return a list containing only those members for which the third element is a string.

    sampleIn1={{1,2,"fred"},{3,2,1.23},{3,2,"this one too",1.23},{},{"apple","banana",{1,2,3}}}

    sampleOut1={{1,2,"fred"},{3,2,"this one too",1.23}}

  2. Given a list of lists, each sub-list known to have exactly two elements, both of which are numbers, return a list of the first element in each sublist multiplied by the absolute value of the second.

    sampleIn2={{3,4},{-1,3},{1.0,-3}};

    sampleOut2={12,-3,3.0}

In the sample output above I distinguish between integer and real output; in practice you can treat everything as a real number if you prefer.

  1. Given a list known to be composed only of numbers, return a list of the cube of each member, sorted by the square of each member (or its absolute value, which will have the same result).

    sampleIn3={1,-2,0.5,4};

    sampleOut3={.125,1,-8,64}

  2. Given a list known to be composed only of numbers, return a list with each member of the list divided by the number before it. Since this is undefined for the first number in the input list, that element should be omitted. Where division by zero would result, the list should include notification of exception ("N/A" or something similar as befits your language of choice).

    sampleIn4={1,-2,0,5,4};

    sampleOut4={-2,0,"N/A",0.8}

Presume that input has been assigned to a variable a in the natural list format for your language, assuming it has one.

To be clear, you don't have to use abstract functions or lambda calculus here, though I suspect that in many languages this will provide a short solution.

Standard rules apply, the examples above are only examples. Your code should work for arbitrary input.

\$\endgroup\$
  • \$\begingroup\$ This challenge explicitly disallows arbitrary classes of languages, is a do X without Y challenge, and a multi-part challenge with no interaction between the parts. The latter is not allowed on PPCG, and the others are highly discouraged. \$\endgroup\$ – Mego May 9 '16 at 19:35
  • \$\begingroup\$ @Mego Read again, I explicitly allow any technique in any type of language. \$\endgroup\$ – Michael Stern May 9 '16 at 19:36
  • \$\begingroup\$ I misread. This is still a multi-part challenge, which are not allowed. \$\endgroup\$ – Mego May 9 '16 at 19:45
  • \$\begingroup\$ @Mego I can combine the challenges. Do you have any other objections or suggestions? \$\endgroup\$ – Michael Stern May 9 '16 at 19:45
  • 1
    \$\begingroup\$ As far as I can tell, the challenges are combined. Anyways, the challenge feels like a random list of arbitrary, unrelated tasks. I think perhaps challenge #4 could stand on its own (especially if you made the operator a parameter). \$\endgroup\$ – Nathan Merrill May 9 '16 at 20:07
0
\$\begingroup\$

ASCII Hulls


Input

A string containing a rectangle made up of m rows of n characters, separated by newlines. Apart from an optional trailing newline (which you may choose), the string must contain nothing else.

All the characters will be printable ASCII (including space). So ASCII characters 32 to 176 inclusive.

The dimensions m and n will not be specified in the input. They will both be in the range 1 to 80 inclusive.

Output

A string containing the same rectangle but with the convex hull of each non-space character filled with that character, higher ASCII values overwriting lower ones.

Overwriting does not prevent a character from contributing to the convex hull. For each character, the convex hull is defined based on the locations of that character before any overwriting.

Details

The rectangle of characters forms a grid of m squares by n squares. The vertices of the convex hull for a given character are the centres of the squares containing that character (apart from any in the interior of the convex hull). All squares whose centre is on the convex hull or in its interior become that character (until any overwriting).

Outline showing convex hull Filled convex hull

Equivalently you can use the top left corner instead of the centre (or any other point in the square) provided it is consistent. This will give the same output.

Test cases

Input followed by output in a single code block

P    
   P
 P  

P    
 PPP
 P


C    C

      G    G
    C    C

   G    G

CCCCCC
  CCCCC
   CCCGGGGGG
    CGGGGGG
    GGGGGG
   GGGGGG


 W    Z
X      X


Y      Y
 W    Z

 W    Z
XXXXXXZX
 W    Z
 W    Z 
YYYYYYZY
 W    Z

Scoring

The shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ I don't understand what the "convex hull" is here. Could you give an example? \$\endgroup\$ – Nathan Merrill May 10 '16 at 21:55
  • \$\begingroup\$ @NathanMerrill It's a convex hull I think. \$\endgroup\$ – Nic Hartley May 10 '16 at 22:02
  • \$\begingroup\$ @NathanMerrill I added some test cases to visualise it \$\endgroup\$ – trichoplax May 10 '16 at 22:08
  • \$\begingroup\$ @NathanMerrill I added a diagram which hopefully sums it up better \$\endgroup\$ – trichoplax May 10 '16 at 22:52
  • \$\begingroup\$ How do you decide if a letter is within the hull? For example, it seems like the first should be P / PPPP / _PP, because part of the square between the midpoints of each letter is crossed. \$\endgroup\$ – Nic Hartley May 10 '16 at 23:11
  • \$\begingroup\$ @QPaysTaxes All squares whose centre is on the convex hull or in its interior become that character so it isn't enough for part of the square to be crossed - the centre of the square has to be on or within the convex hull. \$\endgroup\$ – trichoplax May 10 '16 at 23:28
  • \$\begingroup\$ Oh, I see. That makes more sense.r \$\endgroup\$ – Nic Hartley May 10 '16 at 23:58
  • \$\begingroup\$ I'm having a bit of trouble deciding for this one, but apart from the fact that there's multiple hulls and ASCII parsing/writing involved, is the core of the challenge any different from existing convex hull challenges? \$\endgroup\$ – Sp3000 May 11 '16 at 5:09
  • \$\begingroup\$ @Sp3000 unless the need to keep track of where the initial characters were while doing the overwriting for other characters adds anything in terms of golfing challenge, then I guess this is a duplicate \$\endgroup\$ – trichoplax May 11 '16 at 14:35
0
\$\begingroup\$

Shortest path to the exit:

  • Given a n*n grid of 3 symbolic characters {'.','#',*} , where n is inputted, the dot is a safe spot to move from/to, # is a dragon who blows fire and spits magma, * is the outlet . Define (if it can be) the shortest path to take from the extreme upper/right to the star character that a moving point can take where:

    m is an integer m < n given by user-input or a function dimention with n, that generates obstacles # at the dynamic point m modulus n from the starting point, the last # point so far is replaced by an exit *, if no such path exists print 0 or a negative amount or undifined/null anything witch doesnt throw an error.

Testcases:

input: 7,3
output:9

why? the input generates this grid

...#...
#...#..
.#...#.
..#...#
...#...
#...*..

The shortest path is marked as _

__.#...
#__.#..
.#__.#.
..#__.#
...#_..
#..._..

More TODO ...

Hints/notes

  • Solution is cyclic

  • No solutions when m+1 divides n or n-1 . (to verify)

\$\endgroup\$
  • 1
    \$\begingroup\$ Like I said in your other challenge, please use proper English grammar and spelling. \$\endgroup\$ – Nic Hartley May 10 '16 at 21:52
  • 1
    \$\begingroup\$ This looks like a standard path-finding, which we've already done. Making every mth place also make an obstacle doesn't make it sufficiently different IMO \$\endgroup\$ – Nathan Merrill May 10 '16 at 21:52
  • \$\begingroup\$ @NathanMerrill how is so ? obstacles are systematically generated but not arbitrarily \$\endgroup\$ – Abr001am May 10 '16 at 22:04
  • \$\begingroup\$ Hmmm...I guess that does allow for optimizations. Yeah, this would work for a code-golf. You should define what happens if there is no solution, or guarantee that there will always be a solution. \$\endgroup\$ – Nathan Merrill May 10 '16 at 23:05
  • 1
    \$\begingroup\$ The text says that the start is the extreme upper/right, but the example seems to start from the upper left. Do you mean upper left? Also the slash makes it look like upper or right, rather than referring to a corner, which doesn't seem consistent with the example. \$\endgroup\$ – trichoplax May 11 '16 at 0:49
  • \$\begingroup\$ @trichoplax this is not really a big issue, up/right to down/left or up/left do down/right. \$\endgroup\$ – Abr001am May 11 '16 at 6:47
  • \$\begingroup\$ @Agawa001 It's no issue either way - I'm just helping get it clear which one you want before the challenge goes live \$\endgroup\$ – trichoplax May 11 '16 at 14:30
  • \$\begingroup\$ @trichoplax the challenge will never get a soul to the other end anyways i m not really ready for another blizzard of downvotes \$\endgroup\$ – Abr001am May 11 '16 at 14:40
  • \$\begingroup\$ I never know which challenges will make it to main. I just try to help clarify them until we can tell one way or the other \$\endgroup\$ – trichoplax May 11 '16 at 14:48
  • \$\begingroup\$ I dont know why serial dvter did miss to star the 4th comment, is it because is not castigating ! \$\endgroup\$ – Abr001am May 12 '16 at 7:58
  • \$\begingroup\$ I think you have a gross misunderstanding of what constitutes serial downvoting. Serial downvoting is when somebody goes through and downvotes a lot of posts, typically out of spite. I downvoted both this and your other sandboxed post because they are very poorly specified, and you seem to have a tenuous grasp on the English language that makes understanding these challenges impossible. \$\endgroup\$ – Mego May 13 '16 at 5:23
  • \$\begingroup\$ that's penguins being penguins \$\endgroup\$ – Abr001am May 13 '16 at 7:46
0
\$\begingroup\$

Triangle Rasterization

I don't know if this is the right word for this, but here goes...

Given a triangle with a height and a width, you can convert it into squares by counting any square that the triangle occupies as a whole square. Your task is to calculate the area of this 'rasterized' triangle.

Your program should take two positive integers representing the height and width of a triangle and output the area of its 'rasterized' version. This should always be an integer.

No builtins are allowed, if there are any.

An example

What I'm actually talking about. This is a 6x4 triangle. The red area is the actual inside of the triangle, and the blue area is added on during the 'rasterization'. The total are of the red and the blue is 16. So, given 6 and 4 as inputs, your program must output 16, with or without a trailing newline.

Test cases

 input     output
 1, 1      1
 1, 2      2
 1, 3      3
 2, 2      3
 6, 4      16
 63, 47    1512

As you can probably tell, this is slightly larger than half the area of the enclosing rectangle, and gets more accurate for larger sizes.

Your program should preferably run in under a minute, but the answer with the shortest number of bytes will win.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure about the test case 63, 47? I make it 1535. \$\endgroup\$ – Peter Taylor May 12 '16 at 22:16
  • \$\begingroup\$ @PeterTaylor while fiddling around with a solution I made, I think this error comes from rounding poorly. When I tried adding 1 to each column with a non-integer value and then flooring (I believe this is equivalent to taking the ceiling) I got your answer, but when I tried adding .5 to each value and then flooring I got the value the OP got. For reference: ceil and flop \$\endgroup\$ – FryAmTheEggman May 13 '16 at 18:01
0
\$\begingroup\$

"45-degree rotation" of a square matrix


Introduction

Suppose we have a square matrix with odd sidelength, like this:

0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4

Let's divide it into nested layers as follows:

0 1 2 3 4
 +-----+
5|6 7 8|9
 | +-+ |
0|1|2|3|4
 | +-+ |
5|6 7 8|9
 +-----+
0 1 2 3 4

The nth layer, counting from the center, contains 8*(n-1) cells, and we rotate it n-1 steps in the clockwise direction:

0 5 0 1 2
 +-----+
5|1 6 7|3
 | +-+ |
0|6|2|8|4
 | +-+ |
1|7 8 3|9
 +-----+
2 3 4 9 4

Now our original matrix has been "rotated by 45 degrees", in a sense:

0 5 0 1 2
5 1 6 7 3
0 6 2 8 4
1 7 8 3 9
2 3 4 9 4

Namely, if this operation is applied twice, the result is a 90-degree rotation.

The task

Your input is an n×n matrix of single-digit integers, where n is odd, in any reasonable format. Your output is the 45-degree rotation of this matrix, as defined above.

Rules and scoring

You can write a full program or function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

[[3]] -> [[3]]
[[1,2,3],[4,5,6],[7,8,9]] -> [[4,1,2],[7,5,3],[8,9,6]]
[[0,1,2,3,4],[5,6,7,8,9],[0,1,2,3,4],[5,6,7,8,9],[0,1,2,3,4]] -> [[0,5,0,1,2],[5,1,6,7,3],[0,6,2,8,4],[1,7,8,3,9],[2,3,4,9,4]]
[[1,0,0,2,0,0,3],[0,1,0,2,0,3,0],[0,0,1,2,3,0,0],[4,4,4,5,0,0,0],[4,4,4,4,0,0,0],[4,4,4,4,0,6,7],[4,4,4,4,0,8,9]] -> [[4,0,0,1,0,0,2],[4,4,0,1,0,2,0],[4,4,4,1,2,0,0],[4,4,4,5,3,3,3],[4,4,4,0,0,0,0],[4,4,0,6,0,0,0],[4,0,8,9,7,0,0]]
\$\endgroup\$
0
\$\begingroup\$

KOTH Screeps Fighting AI

Screeps is an MMO for programmers (not a regular MMO, this is not modding, but rather the only way to play) where you program creeps. I want to make sure one more time: this is not hacking or modding, this is the only way you play the game. It has a builtin IDE that is always present.

This is your job: With 1550 energy, spawn an army of creeps to fight other player's armies. Your goal is to destroy the other team's spawn.

Specifications

  • Each team will start with 0 creeps and it's own spawn.
  • The team number will be hardcoded.
  • The spawns will be named Spawn1 and Spawn2, corresponding to each player's team
  • The room controller will be at level 8 and you will not have to worry about upgrading it.
  • Each creep will display an emoji chosen to represent it's team using creep.say(). This is so that members of the two teams can distinguished.

Rules

  • Not all creeps have to fight. Some can gather energy, build walls, etc.
  • Building structures is allowed. This includes walls, ramparts, towers, etc.

This is under construction! Please comment if you know how to improve this challenge!

\$\endgroup\$
  • \$\begingroup\$ I recall that in your purely energy gathering Screeps challenge, the example room could be used that did not require paying or creating an account. What is the situation with this new challenge? \$\endgroup\$ – trichoplax May 17 '16 at 19:20
0
\$\begingroup\$

Kill the mosketeers

Taken a NxN square field, where you are supposed to be on the extreme upper right corner, n mosketeers are waiting an execution instruction that begins with the first lefttmost shooter alternatively until the last righttmost one, in a continuous unceasable order, meanwhile, between any shot and another you are allowed to move one step either to 4 allowed perpendicular directions.

T a period permitted to reload the riffle from a shot to another, dependently of steps taken from a move to another, a step is expressed in other words, as the time taken from two consecutive shots that of a mosketeer and his neighbor, so once T steps are elapsed, the mosketeer takes turn to shot again where two shots can occur in real-time.

Your task, is more than saving your head on your shoulders, but it is rather the ability of killing all the mosketeers while they are reloading their riffles by a knife, noted that : a mosketeer can shot in an horizontal dimention if his turn comes out, and no moketeer is between him and you, morover, a mosketeer do never move.

Given two inputs, N T, say in term of integer output how many mosketeers you are able to kill, return -1 or nil the case you end up killed no matter what you tried.

Example:

input:

   4,3

steps:

...*  |... .|.. ..|. |..| .|.. ..|. |..| .|.. ..|. ...| .... ....
....  |..* .|.. ..|. |..| .|.. ..|. |..| .|.. ..|. ...| .... ....
....  |... .|.* ..|* |.*| .|*. .*|. |*.| *|.. ..|. ...| .... ....
$$$$  |$$$ $|$$ $$|$ |$$| $|$$ $$|$ |$$| $|$$ *$$$ .*$| ..*$ ...*

Output:

  4

example 2

input:

   4,2

steps:

...*  |... .|.. |.|. .|.| |... .|.| |... .|.| .... .|.| 
....  |..* .|.. |.|. .|.| |... .|.| |... .|.| .... .|.| 
....  |... .|.* |.|* .|*| |... .|*| |*.. *|.| .... *|.| 
$$$$  |$$$ $|$$ |$|$ $|$| |$*$ $$.$ $$.$ $$.$ *$.$ .$.$ 

Output:

  2

\$\endgroup\$
  • 1
    \$\begingroup\$ 1) Do you mean musketeers? 2) I think the diagrams could do with a bit of explaining - it took me a while to decipher that | meant shooting, $ is a musketeer, * is you and the spaces separated different states. 3) It's not obvious to me why it's not possible to get all four musketeers in the second case, and also more test cases would be good (especially some that result in -1) \$\endgroup\$ – Sp3000 May 22 '16 at 5:08
  • \$\begingroup\$ @Sp3000 i m sorry to puzzle u this way beucause the challenge isnt about deceiphering patterns, but honestly i think that goes without saying, the second part where yu have been stuck deceiphering it, the two remaing shooters cannot be killed because either of both can shoot you horizontally when you are busy stabbing the other. \$\endgroup\$ – Abr001am May 22 '16 at 9:22
  • \$\begingroup\$ any ways, you dont have to boggle yur mind more this will gonna be dead on meta, \$\endgroup\$ – Abr001am May 22 '16 at 9:23
0
\$\begingroup\$

Serialize and Deserialize a Binary Tree!

A coding website, leetcode.com, has a method to serialize a binary tree.

Serialize means making a binary tree linear.

For example, we have:

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

    1
   / \
  2   3
     / \
    4   5

First, we fill the missing places with 0:

      1
     / \
    /   \
   /     \
  2       3
 / \     / \
0   0   4   5

Then read out all the lines from top to bottom:

->      1
       / \
      /   \
     /     \
->  2       3
   / \     / \
-> 0   0   4   5

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

Let's look at another example:

   1
    \
     2
    /
   3

Fill the missing places with 0:

   1
  / \
 0   2
    / \
   3   0

Note that 0 cannot have any child.

Therefore, this tree is serialized as [1,0,2,3,0].

Your task is to write two programs/functions, one to serialize, one to deserialize.

Specs

  • They may share code.
  • The binary tree will only contain positive integers.
  • A node in the binary tree is represented by [name,left_child,right_child].
  • You may not pre-fill the binary tree with 0s.
  • [1,0,2,3,0,0,0] is invalid.
  • Unlike the website given, [1,0,2,3] is invalid.

Notes

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

Matching a string using a huge number of steps

Your task is to write a regex that matches a string you defined in as close to n steps as is humanly possible.

The regex must match the whole string without the global flag on.

Scoring

The score would be regex length + string length + absolute difference between the number of steps and n.

For example, if n = 65536, this example has 6 bytes as regex, 49152 bytes in the string, and 65539 steps, which would account for a total score of 6+49152+3=49161.

Lowest score wins.

Requirements

  1. n = 65536 (2**16)
  2. n = 59049 (3**10)
  3. n = 40320 (8!)

The total score will calculated from the scores of the three programs.

Questions:

  • How can I make this challenge better?
\$\endgroup\$
  • \$\begingroup\$ Wouldn't the score be 6 + 49152 + 3 for your example? \$\endgroup\$ – Sp3000 May 20 '16 at 14:07
  • \$\begingroup\$ Yes, thank you for reminding. \$\endgroup\$ – Leaky Nun May 20 '16 at 14:12
  • \$\begingroup\$ fyi if you don't end up allowing undershooting, the absolute difference... part should probably be (number of steps - 65536) \$\endgroup\$ – Sp3000 May 20 '16 at 14:45
  • \$\begingroup\$ Also, can we have a regex which theoretically gives a number of steps we can prove, but doesn't work in practice (e.g. due to insufficient memory)? \$\endgroup\$ – Sp3000 May 20 '16 at 14:46
  • 3
    \$\begingroup\$ What is a step? Whatever it is, it seems uninteresting as we can do an empty string with (){65536} or something like that. \$\endgroup\$ – feersum May 20 '16 at 21:19
0
\$\begingroup\$

Brainfuck-golf: find the maximum of two numbers

You will be provided with two numbers on the first two memory cells, and you will write a code in brainfuck to put the maximum of the two numbers on the third memory cell.

  • You may use this template and this template to test your code. Just append your code to the templates.
  • You may destroy the numbers in the first two cells.
  • The pointer must initially point to the first cell.
  • The two initial numbers will be positive.
  • , will halt your program (waits for input which I will not supply).
  • The tape is semi-infinite. Your numbers are on the first two memory cells.
  • The cells do not wrap around. They just increase until the number is bigger than the age of the universe in terms of picoseconds.
\$\endgroup\$
  • \$\begingroup\$ Language specific challenges are generally frowned upon. And if this wasn't restricted to BF, it would be to trivial. \$\endgroup\$ – DJMcMayhem May 21 '16 at 8:36
  • \$\begingroup\$ How is regex-golf different from this? \$\endgroup\$ – Leaky Nun May 21 '16 at 8:43
  • \$\begingroup\$ Regex-golf is slightly different since there are many versions of regex with different behavior. But hey, I could be wrong. We've had BF only challenges before. (such as codegolf.stackexchange.com/questions/33019/brainfuck-sorting, codegolf.stackexchange.com/questions/9178/…, and codegolf.stackexchange.com/questions/2445/… I'd leave it up for a while and see what other people think. \$\endgroup\$ – DJMcMayhem May 21 '16 at 8:54
  • \$\begingroup\$ It may be a duplicate of the first linked challenge, because this challenge is only about comparing... \$\endgroup\$ – Leaky Nun May 21 '16 at 9:03
  • \$\begingroup\$ Can we use ,, and if so what will it do (e.g. set to 0, set to -1, no change)? \$\endgroup\$ – Sp3000 May 21 '16 at 11:39
  • 1
    \$\begingroup\$ Since this is a) language specific, b) asks for a snippet, c) asks for a task that is probably often just a minor component of a more elaborate program, how about posting it as a tips question instead? \$\endgroup\$ – Martin Ender May 21 '16 at 11:51
  • 3
    \$\begingroup\$ You should also specify the details of the Brainfuck interpreter. Semi-infinite or infinite tape? Byte values or arbitrary-precision integers in the cells? Etc... \$\endgroup\$ – Martin Ender May 21 '16 at 11:52
  • \$\begingroup\$ Why tips? \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 13 '16 at 23:33
0
\$\begingroup\$

Primary Chances

Write a program that lists all possible outcomes for a general election with any number of candidates.

Rules:

  • Your answer must output how many states each candidate won in any format.
  • Candidates can have any name.
  • This is , so standard loopholes are forbidden, and shortest code wins.
\$\endgroup\$
0
\$\begingroup\$

Sort 2D points by Sierpiński curve order


[ WORK IN PROGRESS]


Input

A collection of distinct 2D points in the range [0,1] X [0,1].

Output

An ordered collection of the same 2D points, meeting the criteria for Sierpiński curve order.

Sierpiński curve order

  • The points are in the order that the Sierpiński curve would pass through them.
  • The order is cyclic - it does not matter which point is first.
  • The order may be clockwise or anticlockwise/counterclockwise, provided it is consistent.
  • The point at the centre of the range, (0.5, 0.5), may fall into any triangular quarter of the range, provided it is in the correct order among other points in that quarter. Similarly for all other points where both coordinates have finite binary expansion.

Although the curve is infinitely long and fills the unit square, it is arranged in a convenient shape that allows ordering points by calculating only a finite number of iterations. For example, if there are 4 points, one in each triangular quarter of the square, then they can be ordered based only on this information as the curve fills one triangular quarter before moving on to the next so the exact position without that quarter is not relevant.


Sandbox questions

  • Should ambiguous points be allowed to fall in any direction, or should I impose that they always fall left rather than right and up rather than down? Or just insist that the solution choose a consistent direction rule?
  • Can I assume that any three points that can be described by floating point variables can be ordered in a finite number of subdivisions? I'm pretty sure but welcome a counterexample.
\$\endgroup\$
0
\$\begingroup\$

Find ALL Longest Common Substrings

Unlike "Longest Common Substring" algorithm which returns just one string, or the length of it. This algorithm returns a score after taking all separate longest common substrings into account.

This program returns the score of how similar one string is to another according to the following rules:

  1. isolate only the longest (non-overlaping) matching substrings.
  2. score every longest substring found with this formula: (substring.length / ((string1.length + string2.length) / 2)) * substring.length
  3. sum the scores and return.

STEP 1 Example:

string1 = ABCD

string2 = ZBCA

Deconstructing string1: (list of substring in order)

ABCD

ABC

AB

A (also found in string2)

BCD

BC (also found in string2)

B (also found in string2 but ignored - part of a longer substring)

CD

C (also found in string2 but ignored - part of a longer substring)

D

Matches: A, BC

STEP 2 Example: (substring.length / ((string1.length + string2.length) / 2)) * substring.length

A: (1/((4+4)/2)) * 1 = .25

BC: (2/((4+4)/2)) * 2 = 1

Step 3 Example:

.25 + 1 = 1.25, Return 1.25

Here's an example of longer strings of variable length:

string1 = Approximate This

string2 = Appropriate That Thing

Matches: Appro, i, ate Th,  Thi

Appro: (5/((16+22)/2)) * 5 = 1.3157894736842105263157894736842

ate Th: (6/((16+22)/2)) * 6 = 1.8947368421052631578947368421053

i: (1/((16+22)/2)) * 1 = 0.05263157894736842105263157894737

 Thi: (4/((16+22)/2)) * 4 = 0.47368421052631578947368421052632

Return: 4.1052631578947368421052631578948
\$\endgroup\$
0
\$\begingroup\$

Fizzbuzz for tensorflow

Since I was a new and naive user, I posted this question. In one day it got over 25 upvotes but was shut down for being too broad. Clearly there is community interest -- so by the suggestion of @DrGreenEggsandHamDJ I'll try it again in the sandbox. I'd really like to see some of the answers here, so I appreciate any help you can give turning this question into a proper submission.

Original text copied below:


Inspired by the job-interview with Joel Grus, the goal of this challenge is to write a tensorflow (or other deep/machine learning) program that learns Fizzbuzz and correctly prints out the answers to the positive integers less than 1000.

You can assume there are files named train.csv and test.csv and each contain a sorted list of sequential integers and the fizzbuzz answer:

 ...
 100, buzz
 101, 101
 102, fizz
 103, 103
 104, 104
 105, buzz
 ...
 150000, fizzbuzz

test.csv spans 1-1000 and train.csv spans 1001-150000.

Rules

  1. You must not hard-code the rules to Fizzbuzz anywhere in your program. The output must be from a machine learned representation that is learned while running the code.
  2. You must utilize train.csv in the training set and check your output against test.csv. You cannot use test.csv during training.
  3. You must get all outputs correct from test.csv (but as is case with deep-learning, we'll allow your code to fail this rule no more than 5% of the time).
  4. You may use any language and any external module (eg. python/tensorflow) as long they explicitly perform some kind of learning. Reference both the language and the module in the title of your post.
  5. This is a popularity contest, so the submission with the most votes after one week wins.
\$\endgroup\$
  • \$\begingroup\$ What are the odds this will work well without an obscene number of iterations? A week doesn't seem like much time to test more than a single method or two. \$\endgroup\$ – Geobits May 25 '16 at 2:58
  • \$\begingroup\$ @geobits I'm not sure, but I can train a decent random forest model on Netflix predictions or a CNN to recognize basic images in about in hour. I figured the community would enjoy the challenge of a basic programming task in an unconventional manner. Surely fizzbuzz can't be that hard... \$\endgroup\$ – Hooked May 25 '16 at 3:05
  • \$\begingroup\$ Well, one problem that comes to mind immediately is that you need it to output valid code at all. So you're going to need to compile/run/whatever for every slight variation in the code. So then you need to figure out what building blocks you can give it to start with. A list of keywords to try, just random ascii, somewhere in between? That part in particular seems underspecified, but could make or break the odds of it working imo. \$\endgroup\$ – Geobits May 25 '16 at 3:08
  • 1
    \$\begingroup\$ I foresee arguments over where exactly the line falls for "hard-cod[ing] the rules to Fizzbuzz". \$\endgroup\$ – Peter Taylor May 25 '16 at 11:45
  • \$\begingroup\$ Hmmm....if you come up with arbitrary rules of fizzbuzz (like different numbers, different amounts of numbers), that might work to prevent hardcoding. \$\endgroup\$ – Nathan Merrill May 25 '16 at 14:24
0
\$\begingroup\$

What can I build?

The Rules

Today I have decided to make geometric shapes out of toothpicks and gumdrops! However, I have a limited supply, so you have to figure out what I can build. I will give you an input in the format m n, where m is toothpicks (edges) and n is gumdrops (vertices.) Your output should be, in any output format of your choice, all 3D geometric shapes such that the amount of edges=m and the amount of vertices=n. The list of 3D geometric shapes you will use is this: Gist

  • You may NOT access the Internet.
  • No builtins relating to geometry or solids
  • This is code golf, so shortest code wins.
  • For no solids and invalid input, output nothing

Examples

In: 3 2 Out: <empty>
In: CodeGolf123 Out: <empty>
In: 12 6 Out (Bonus): {regular tetrahedron,unit equilateral square pyramid,unit equilateral triangular dipyramid,unit equilateral triangular prism,unit equilateral pentagonal pyramid,regular octahedron} Out (Regular): {regular octahedron} `

\$\endgroup\$
  • \$\begingroup\$ The first 3 rules can be deleted, as they're ppcg defaults \$\endgroup\$ – Bálint May 22 '16 at 20:03
  • \$\begingroup\$ Not the first... \$\endgroup\$ – ev3commander May 22 '16 at 20:04
  • \$\begingroup\$ I think this would work better with 1 solid with exactly n and m edges and sides. \$\endgroup\$ – Rɪᴋᴇʀ May 22 '16 at 20:29
  • \$\begingroup\$ How about doing that, but having this as a bonus? \$\endgroup\$ – ev3commander May 22 '16 at 20:37
  • 4
    \$\begingroup\$ 1. KISS. Ditch the stuff about the external file: the overhead to load it and the overhead generated by requiring it to be UTF-8 mean that no-one would want to use it anyway. 2. "No builtins" literally bans people from using any language. Specify what built-ins are banned. 3. Make the data available in a usable format: i.e. a text file hosted on gist.github.com or pastebin. 4. The bonus is a no-brainer: a 10% saving for changing two == to <=. Either make it compulsory or remove it entirely, because as it stands it's just complication. \$\endgroup\$ – Peter Taylor May 22 '16 at 22:38
  • \$\begingroup\$ @petertaylor: I am currently on a phone so I can't put a gist... \$\endgroup\$ – ev3commander May 23 '16 at 10:42
  • 2
    \$\begingroup\$ There are a lot of shapes in that gist. Some of them are specified in different formats. If they're all to be supported it would be nice to have a standard format to represent them. Also some of these shapes specify different edge lengths. Will the challenge assume all edges are length 1 or will you potentially need to break toothpicks and keep track of the remaining pieces? \$\endgroup\$ – Poke May 26 '16 at 21:02
  • 1
    \$\begingroup\$ @Poke 1. Will fix 2. Irrelevant-- you have all sorts of toothpicks, some miniscule and others huge. \$\endgroup\$ – ev3commander May 26 '16 at 23:43
0
\$\begingroup\$

Code me music

Challenge

Write a program that will play music based on input.

Input

When your program is run it will be given a small song. Each note in the song will have 3 components:

[octave][pitch][duration]

where octave is the octave for the note to be played in, pitch is the key of the note (a b c d e f g), and duration is the length of the note in milliseconds. For example, 4c1000 would be middle c played for one second. Notes in a song are separated by spaces. Flats and sharps are possible, and they go after the note like this: 5gb1000 (5th octave g flat) for flats and 5g#1000 (5th octave g sharp) for sharps.

Output

Your program must produce sound based on the input. If one of the notes in the input is 3f500, your program must play f in the third octave for a half of a second.

Other notes

  • This is code golf, so shortest program in (insert period of time) wins.
  • No functions, only full programs.
  • The sound can be whatever you please.
  • Here are the frequencies of notes in the 4th octave in hertz:

    • 4c - 261.63
    • 4c#/4db - 277.18
    • 4d - 293.66
    • 4d#/4eb - 311.13
    • 4e - 329.63
    • 4f - 349.23
    • 4f#/4gb - 369.99
    • 4g - 392.00
    • 4g#/4ab - 415.30
    • 4a - 440.00
    • 4a#/4bb - 466.16
    • 4b - 493.88
  • A list of all frequencies is here.

Sandbox

  • Is the challenge objective clear?
  • This challenge may be hard for some languages, is that a problem?
  • Is this already a challenge?
  • Any positive feedback is welcome.
\$\endgroup\$
  • \$\begingroup\$ I think this could be improved by explaining what the frequencies are for the pitches at a given octave, and then explaining how an octave relates to that. That information is necessary to answer in any language which doesn't handle that itself, so I think it warrants being in the post rather than being behind a (potentially stale) link. In addition, you probably need to have some kind of leniency about frequency and duration, machines are not perfect after all. \$\endgroup\$ – FryAmTheEggman May 27 '16 at 14:35
  • \$\begingroup\$ @FryAmTheEggman Thank you for your feedback, updated challenge. \$\endgroup\$ – lapras May 27 '16 at 14:54
  • \$\begingroup\$ Yes, this is already a challenge. (And, curiously, the second sandbox proposal which is a variant on that challenge in just a week). \$\endgroup\$ – Peter Taylor May 28 '16 at 10:55
0
\$\begingroup\$

Plan a special tournament

tags: [more tags required]


I host a special tournament with any number n >= 2 of participants.

Here is a list of plans of tournaments for n = 2 to 20:

 2: 1) DE-2c-1w
 3: 1) RR-3c-1w
 4: 1) DE-4c-1w
 5: 1) RR-5c-2w 2) DE-2c-1w
 6: 1) RR-6c-3w 2) RR-3c-1w
 7: 1) RR-7c-3w 2) RR-3c-1w
 8: 1) DE-8c-1w
 9: 1) RR-9c-4w 2) DE-4c-1w
10: 1) RR-10c-5w 2) RR-5c-2w 3) DE-2c-1w
11: 1) RR-11c-5w 2) RR-5c-2w 3) DE-2c-1w
12: 1) RR-12c-6w 2) RR-6c-3w 3) RR-3c-1w
13: 1) RR-13c-6w 2) RR-6c-3w 3) RR-3c-1w
14: 1) RR-14c-7w 2) RR-7c-3w 3) RR-3c-1w
15: 1) RR-15c-7w 2) RR-7c-3w 3) RR-3c-1w
16: 1) DE-16c-1w
17: 1) RR-17c-8w 2) DE-8c-1w
18: 1) RR-18c-9w 2) RR-9c-4w 3) DE-4c-1w
19: 1) RR-19c-9w 2) RR-9c-4w 3) DE-4c-1w
20: 1) RR-20c-10w 2) RR-10c-5w 3) RR-5c-2w 4) DE-2c-1w

Explanation of the plan

  • The entire tournament enters the first round, which has c = n participants.
  • For each round:
    • If c is a power of 2, then this round will be a double elimination round, with 1 winner. After this round, the tournament ends.
    • Else, this round will be a round robin round, with floor(c/2) winners that continue to the next round.
      • If only one winner continues, the tournament ends.
      • Else, let c be the number of winners, and start again from "For each round".

The Challenge

Given n, return a plan of the special tournament with n participants.

This is a , so shortest code wins.

TODO: Reword the explanation clearly, write more content.

\$\endgroup\$
  • \$\begingroup\$ How does a round robin with five people work, where you have two winners? Most round robins would have a bye, so you'd end up with three winners continuing on. (same for any odd number) \$\endgroup\$ – Geobits Jun 4 '16 at 19:02
0
\$\begingroup\$

Golf a 2d maze (Yes, a whole game)

Nowadays, I am interested in making games. especially mazes. In this golf round of code, You should make a maze game. You can do it with just preset mazes, but, if you make it randomly generate, I will be a-maze-d and will give you bonus points.(Huh. is that a pun?) So, Go on, Why don't you try right now?

DETAILS:

  • Input W(Up), A(Left), S(Down), D(Right) until the player gets to the finish.
  • Display the maze and the player each input.
  • Move the player Up if the input is 'W', Down if 'S', Left if 'A', and Right if 'D'.
  • The Character for the wall and the player is undefined. you choose.
  • The Character for the wall, the player and the end square should be all different.

MAZE GENERATING:

  • You should get the Width and height in the input.
  • Not Necessary, but you can use Prim or Kruskal.
  • Also you can use the method mentioned in here.
\$\endgroup\$
  • 1
    \$\begingroup\$ The spec as is probably has too many ambiguities, e.g. 1) What counts as a "maze"? 2) If I was to golf this question right now, I'd put the exit next to the player and make it so that the only valid move is into the exit. That would save a ton of bytes since I only have to check one input. 3) If random generation is optional, it's almost certain that it won't be done (but if you do make it mandatory, then you would need to specify what random generation means) 4) Do we have to handle invalid input from the user? \$\endgroup\$ – Sp3000 Jun 5 '16 at 6:50
  • \$\begingroup\$ In order for this to fit as a challenge on this site, it needs to have a winning criterion. For example, code-golf (shortest code wins), or fastest-code. You can also use code-challenge if you define a score based on something else, but there must be some way of assigning a score to each solution so they can be put in order and encourage competition. \$\endgroup\$ – trichoplax Jun 6 '16 at 13:52
  • \$\begingroup\$ I think this could be an interesting challenge, but it needs to be well defined before it will be ready. \$\endgroup\$ – trichoplax Jun 6 '16 at 13:57
  • \$\begingroup\$ It is code-golf. \$\endgroup\$ – user54200 Jun 6 '16 at 14:01

You must log in to answer this question.

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