461
\$\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\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43

2615 Answers 2615

1
\$\begingroup\$

Generating Punnett Squares

The task will be to generate a simple (monohybrid cross) Punnett Square, given the "genotype" of two parents.

A "trait" will be represented as a single alphabetical character (eg 'a').

An allele for a trait is that character, but if the allele is dominant if it is uppercased, and recessive if lowercased (eg 'a' or 'A').

A genotype is two alleles, both of which can be either dominant or recessive. Note that if a genotype is heterozygous (has one dominant and one recessive allele) the dominant allele will always come first (eg "AA" or "Aa" or "aa").

The input will be two strings of length 2, each of which is a valid genotype for one trait. You can take input as arguments to your function or program, or from a file. You should output a Punnett Square in exactly this format:

  A  a
A AA Aa
a Aa aa

(This would have been for the input "Aa" and "Aa"). The output can be to stdout, as a string, or to a file.

The first parent (which is the first argument) should be across the top, and the second parent should be down the side, so for the input "AA" and "aa", the output should be:

  A  A
a Aa Aa
a Aa Aa

Your code is expected to work with any trait (letter of the alphabet).

Another way to phrase this problem might be to output a table of the cartesian product of two strings of length 2, where each string consists of only uppercase or lowercase variants of one character, and the data in each cell should be sorted such that each uppercase character comes before each lowercase character.

Full sample of behaviour for some trait "a":

"AA", "AA" ->

  A  A
A AA AA
A AA AA

"AA", "Aa" ->

  A  A
A AA AA
a Aa Aa

"AA", "aa" ->

  A  A
a Aa Aa
a Aa Aa

"Aa", "AA" ->

  A  a
A AA Aa
A AA Aa

"Aa", "Aa" ->

  A  a
A AA Aa
a Aa aa

"Aa", "aa" ->

  A  a
a Aa aa
a Aa aa

"aa", "AA" ->

  a  a
A Aa Aa
A Aa Aa

"aa", "Aa" ->

  a  a
A Aa Aa
a aa aa

"aa", "aa" ->

  a  a
a aa aa
a aa aa

This is my first attempt at a challenge so I'd like some feedback on if it's any good and how it can be improved. I haven't been able to find any challenge like this, so hopefully it's not a duplicate.

Have I explained it clearly?

Is this idea interesting enough for a challenge?

What other tags would I use with such a challenge?

\$\endgroup\$
1
\$\begingroup\$

Where in the world am I?

Original Challenge

This challenge has a single aim, given no input, print out the user's current location, with a minimum of the following info:

  • City
  • Country

So any of the following are allowed:

  • "London, England"
  • "Eifel Tower, Paris, France"
  • ["London", "England"]
  • {"country": "Scotland", "city": "Edinburgh"}

The following are not allowed:

  • [51.5074, 0.1278]
  • {"country": "Scotland", "city": "Edinburgh", ISP: "EE"}

Do not show the user's IP or ISP name, or any extra output.

Standard code golf rules apply

Good luck, and have fun!

Reason for limits

Thanks

programmer5000 - Suggesting to post here after original was deleted

caird coinheringaahing - Lon and Lat rules

\$\endgroup\$
  • \$\begingroup\$ Is returning a list of geo-cordinates allowed? You might want to clarify that in the question \$\endgroup\$ – caird coinheringaahing Aug 28 '17 at 14:12
  • 3
    \$\begingroup\$ This has a number of issues with ill-defined cases. In particular, the following are not addressed: (A) my location is unambiguously in a given country, but there's no city within several hours' drive; (B) my location is unambiguously not inside any country; (C) the territorial ownership of my location is disputed; (D) it's not clear what the name of the country is (where your example of Edinburgh is a good one: if Scotland is correct, is UK incorrect? How about dependencies, colonies, etc?) \$\endgroup\$ – Peter Taylor Aug 28 '17 at 21:26
  • 2
    \$\begingroup\$ In addition, it contradicts itself over whether {"country": "Scotland", "city": "Edinburgh"} is allowed or not; and it is not very testable. To make this a good challenge I would recommend taking latitude and longitude as inputs and providing a complete and unambiguous specification of exactly what the output string should be such that any incorrect answer can be shown to be incorrect with a test case which it fails. \$\endgroup\$ – Peter Taylor Aug 28 '17 at 21:28
  • \$\begingroup\$ TBH, if someone was onboard the International Space Station and decided to take time out to complete my code golf challenge I would take it as a compliment. For international waters I would be OK with an answer that pointed towards that. For ones with multiple answers / disputed it would probably be reasonable to accept multiple answers, but there may be issues with this I have not foreseen. \$\endgroup\$ – jrtapsell Aug 28 '17 at 21:35
  • \$\begingroup\$ RE: The contradiction, this was an omission I hope I have fixed now \$\endgroup\$ – jrtapsell Aug 28 '17 at 21:37
  • \$\begingroup\$ Is there a way to fix this issue more generally? I know my answer is a bit vague and not built into the question \$\endgroup\$ – jrtapsell Sep 1 '17 at 10:31
  • \$\begingroup\$ Is this challenge good to go, needs changes, or not of use? \$\endgroup\$ – jrtapsell Sep 2 '17 at 23:20
1
\$\begingroup\$

Displaying exponent towers in ASCII

Background

Unlike + and *, the exponentiation operator ^ is not associative. The convention is that ^ is right associative, so that a^(b^c) = a^b^c. Of course, nested exponentials are usually displayed as nested superscripts, which can be represented in ASCII as:

            c
           b
a^(b^c) = a

For a general right associative operator &, there would be no way to simplify the expression (a&b)&c. However, exponentiation satisfies the rule

           bc
(a^b)^c = a

where bc means b*c.

Combining these rules, we can express any arbitrarily parenthesized exponential expression using only superscripts and juxtaposition. For example,

                                               d
                                              c  f
                                             b  e
(a^(b^(c^d)))^(e^f) = a^((b^(c^d))*(e^f)) = a

Challenge

Write a function that, given a string consisting of lowercase letters, parentheses, and ^ that represents a valid mathematical expression (see rules), prints an ASCII representation of this expression in the manner described above.

Rules

  • The input string is any element of the context-free grammar determined by the rules
    S → any lowercase letter
    S → (S^S)

  • The output must consist of only lowercase letters, spaces and newlines.

  • The resulting ASCII picture must have exactly one letter per column.

  • The left to right order of the letters must be preserved from input to output.

  • This is , so shortest answer in bytes wins.

Test Cases

Input: a
Output:
a

Input: (a^(b^c))
Output:
  c
 b
a

Input: ((a^b)^(c^d))
Output:
   d
 bc
a

Input: ((a^(b^c))^d)
Output:
  c
 b d
a

Meta

  • Is it clear what picture you are supposed to output?

  • This challenge has some similarities to this other challenge, but I think they are far enough part to not be dupes: Convert exponents into ASCII art.

\$\endgroup\$
1
\$\begingroup\$

Erdős–Straus conjecture

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give me the answer for n=7777 . How much time did it take your program to find it? What do you mean by "result must be returned for all valid inputs".Is 1500 years ok for bigger n? Brute-forcing this is very easy but it takes forever. \$\endgroup\$ – J42161217 Sep 9 '17 at 10:06
  • \$\begingroup\$ @Jenny_mathy I'll put a reasonable limit and the last part means you need to output the right numbers if x is valid (a whole number larger than 2) \$\endgroup\$ – Anthony Pham Sep 9 '17 at 11:28
1
\$\begingroup\$

Determine the Resultant

META:

I'm not yet sure which one of the following two versions would be more interesting:

Version a: Given two integral polynomials P,Q determine their resultant Res(P,Q).

Version b: Given two monic integral polynomials P,Q determine the polynomials A,B such that AP+BQ = Res(P,Q). Where deg A < deg Q and deg B < deg P.

Definitions

The resultant is defined as

Here the product iterates over all complex numbers pairs that are zeros of each polynomial. For integral polyonmials this is an integer. (One other way - and certainly not the only - is via the determinant given here.) The corresponding integral polynomials A,B such that AP+BQ = Res(P,Q) with deg A < deg Q and deg B < deg P are unique.

\$\endgroup\$
  • \$\begingroup\$ Are these polynomials on Z? You say complex number pairs which suggests it is some numeric set. \$\endgroup\$ – Wheat Wizard Sep 17 '17 at 0:28
  • \$\begingroup\$ Those pairs are not necessarily integers, but the polynomials are. \$\endgroup\$ – flawr Sep 17 '17 at 14:29
1
\$\begingroup\$

Pythagorean Double Regex

Posted by NH. in Zendo:

though depending on the regex flavor, things like that pythagorean triple could be hard to do.

The rule in question was:

Given a pair of numbers, match if the two numbers are part of some integral Pythagorean triple, else don't match.

Challenge

Given a pair of positive integers, write a regex that matches if and only if the pair of integers are part of a Pythagorean triple - i.e. if the two integers are a and b, either a2+b2 is a perfect square or |a2-b2| is. (Note: x,x should match, even though 0,x,x is not a true Pythagorean triple)

Input

  • Integers represented in any base, separated by a character not used in the representation of that base

Test cases

NB: All but one of these test cases were taken from the game of Zendo from which the rule came, so they may not test boundary cases of the rule

True:
3,4
4,3
30,40
16,12
20,21
21,20
4,5
40,50
24,25
7,7

False:
1,2
5,6
7,8
4,10
9,10
3,100
9,16
24,20

This is , so the shortest regex in bytes wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ 1. Ideally a question should be self-contained. This barely makes sense without following the links. I'm not even sure whether the answers have to be regexes or whether that was just the original context. 2. What's the scoring system / winning criterion? \$\endgroup\$ – Peter Taylor Sep 11 '17 at 7:53
  • \$\begingroup\$ @PeterTaylor is this better? \$\endgroup\$ – boboquack Sep 11 '17 at 8:35
  • \$\begingroup\$ Definitely improved, yes. I'm still not sure what "(from the game)" refers to. Also, are you taking into account that by default we consider unary to be an acceptable input format for positive integers when writing a regex? I advise being explicit about whether numbers must be in decimal or whether unary is acceptable. \$\endgroup\$ – Peter Taylor Sep 11 '17 at 8:44
  • 1
    \$\begingroup\$ @PeterTaylor fixed up again \$\endgroup\$ – boboquack Sep 11 '17 at 9:07
1
\$\begingroup\$

Create a .pdf file

Your task is, given a non-empty string, to create a valid PDF (also see here for more information about the structure of PDF-files) file that contains no more than this string (no page numbers, date etc). Your submission has can either be a function or full program that achieves this task.

Rules

  • The input will be a non-empty string of printable ASCII characters, additionally the characters \n & \t may be part of the input but not the last character
  • Your program/function produces a valid PDF file that contains that string but no more
  • The representation of the string doesn't matter, except that it has to be a different color than the background, meaning valid representations may be (not limited to):
    • green text on black background (or the other way around)
    • the font is irrelevant but has to be consistent (it has to be readable without using a loupe)
    • some sort of image that represents the string
  • The output has to be case sensitive
  • If the string doesn't fit page width it needs to be split in a consistent manner such that it fits onto multiple lines (this means each character needs to be visible)
  • If the lines don't fit onto a single page, you'll need to insert pagebreaks
  • The width of a \t and (space) need to be visibly different (\t larger)
  • The PDF may contain one trailing empty page
  • The PDF can be printed to STDOUT (ie. call_your_program > test.pdf would result in a valid PDF) or create a new file somewhere on your filesystem (the filename doesn't need to end in .pdf or .PDF)

Example inputs

Valid

Printable string:

Hello, World!

Printable string containing newline(s):

Foo\nBar

Printable string containing newlines & horizontal tabs:

Line 1:\t!"#$%&\'()*+,-./0123456789:;<=>?\nLine 2:\t@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_\nLine 3:\t`abcdefghijklmnopqrstuvwxyz{|}~

Invalid

Trailing newline:

Hello, World!\n

Carriage return:

Foo\r\nBar

Empty string:

Sandbox

Tags will be: , ,

  • Are there other relevant tags?
  • Is the challenge specific enough (creating PDFs that only work in an exotic PDF-reader etc)?
    • Should I limit the question such that the file has to be "viewable" in (for example) xpdf?
    • If so, would xpdf be a good choice?
  • Is "readable" well defined enough (for example some people may claim that they are able to read Wingdings or even worse Comic Sans :P)
  • Should I enforce a certain font size? What about even enforcing a certain font itself? (I feel this takes away too much freedom)
  • Should I limit input such that it always fits onto a single page? (Loophole: people could choose a font size such that the input can only be one letter)
\$\endgroup\$
  • \$\begingroup\$ Is there a publicly available spec of the format, that doesn't require six months of waiting, 100$, signing a non-disclosure agreement and sacrificing a goat? If yes, do link. If not, I'm going to nope out of the challenge. \$\endgroup\$ – John Dvorak Sep 23 '17 at 14:48
  • \$\begingroup\$ @JohnDvorak I'm looking for a solution for this issue, but it seems like without changing the file-format there's no way around this :( What a shame.. Also the pricing seems dynamic, are you referring to this? Because for me it shows nearly 200$ O.O \$\endgroup\$ – ბიმო Sep 23 '17 at 15:14
  • \$\begingroup\$ Oh boy. It seems I tried to overshoot the price by a comfortable margin and failed miserably. \$\endgroup\$ – John Dvorak Sep 23 '17 at 15:19
  • \$\begingroup\$ This is ridiculous.. I expected the specs for PDF to be free since it is such a wide-spread format. Do you have a suggestion to resolve this issue apart from deleting this challenge? \$\endgroup\$ – ბიმო Sep 23 '17 at 15:22
  • 1
    \$\begingroup\$ You could go with a different format. OpenDocumentFormat is just a bunch of well documented XMLs packaged in a single ZIP file. Golfers can then try and see how much they can bend the rules before OpenOffice starts whining. Plus, zip files can technically be created without a library - just stick a mostly constant header before the uncompressed data. \$\endgroup\$ – John Dvorak Sep 23 '17 at 15:29
  • 2
    \$\begingroup\$ I think adobe.com/content/dam/Adobe/en/devnet/acrobat/pdfs/… is publicly available, but I don't think this question's spec is quite clear enough. In particular, it should address line wrapping when the input text doesn't include newlines. \$\endgroup\$ – Peter Taylor Sep 23 '17 at 16:50
  • \$\begingroup\$ @PeterTaylor Oh, yep that's public :) Thanks a lot! I'll see how I can address the line wrapping issue in a sensible manner (either by removing the \ns in the input or by creating a rule such that they can't just be ignored). \$\endgroup\$ – ბიმო Sep 23 '17 at 21:20
  • \$\begingroup\$ My main concern there is that it would be easy to just blit the text without caring whether it goes outside the page and is effectively lost. \$\endgroup\$ – Peter Taylor Sep 23 '17 at 21:35
  • \$\begingroup\$ @PeterTaylor Good call! I updated the post, feel free edit in any suggestions or clarifications (this goes for anyone! If I'm not happy with it I can always revert). \$\endgroup\$ – ბიმო Sep 23 '17 at 22:20
1
\$\begingroup\$

Number of all hyperrectangle-filling walks

Your input:

  • size of the hyperrectangle – generally an n-tuple
    • eg. (s,s) in case of a square
  • position in the hyperrectangle – generally 0 <= pos[i] < size[i] for i-th dimension
    • eg. (x,y) where 0 <= x < s and 0 <= y < s in case of a (s,s) square.

Your task: Find the number of walks in the hyperrectangle, which start at the given position and visit each cell of the hyperrectangle exactly once.

In the context of this task, a walk is a sequence of positions, such that each position after the first differs from the previous one in exactly one dimension by amount of exactly 1. Eg. in the case of a 2x2 square, a possible walk would be (0,0) -> (0,1) -> (1,1) -> (1,0).

Note: It doesn't matter whether x is vertical position and y horizontal or vice versa. Neither it matters whether coordinates grow downwards / upwards or to the left / right (eg. vertical axis might grow downwards or upwards without any effect on the result). These statements extend to higher dimensions as well.

Related task: Longest hypercube path

Example

Given size = (3,3) and pos = (0,0), there are 8 solutions. These can be divided into four equivalence classes under the relation of transposition, viz. A == Transpose(A). Only one solution for each equivalence class needs to be found, the other one can be obtained by simply transposing the first one.

The four "canonical" solutions: (3,3);(0,0) Canonical solutions

Output: 8.

Possible specializations

Specialization 1: Support only hypercubes (hyperrectangles with equal sizes in each dimension). Specialization 2: Support only 2-dimensional hypercubes (squares).

My questions

  1. (Obvious question) Has this task already been presented?
  2. Is this task (in its general form) too difficult? Would it be more reasonable to restrict it to one of the specializations (or to a different specialization)?

\$\endgroup\$
  • \$\begingroup\$ Have you made a reference implementation? It seems to me that it would be worth generating some sequences for the two specialisations and seeing whether they're in OEIS, and whether closed forms for the answers and known. \$\endgroup\$ – Peter Taylor Oct 1 '17 at 20:11
  • \$\begingroup\$ @PeterTaylor Those were my thoughts, but I haven't yet gotten around to making an implementation. I suspect the sequences for specializations (especially Spec. 2) will be in OEIS and most likely will have a closed-form solution, but it's in the higher dimensions where it gets interesting, especially if you consider optimizations based on symmetries. \$\endgroup\$ – kyrill Oct 1 '17 at 20:31
  • \$\begingroup\$ @PeterTaylor I have written a (hopefully correct) implementation in Python 2; though it being a brute-force algorithm, higher dimensional hypercuboids may require some time to be examined... \$\endgroup\$ – Jonathan Frech Oct 8 '17 at 12:52
  • \$\begingroup\$ The relevant OEIS sequence for a hypercube of side lengths 2, starting at one corner, is A003043. \$\endgroup\$ – Jonathan Frech Oct 8 '17 at 14:48
  • \$\begingroup\$ I for one really like this challenge and do not think any specialization which makes the task easier is required. \$\endgroup\$ – Jonathan Frech Oct 8 '17 at 20:36
1
\$\begingroup\$

Detect Ambiguity in a Context-Free Grammar

Sandbox notes:

  • Is the background too hard to understand? If so, should I clarify it further at the risk of making it unreasonably long, or simply delete it and state that the reader should have a knowledge of context-free grammars?
  • Is there anything I should clarify in the specifications?
  • Are there any other tags I should add? I couldn't find any better ones.
  • Should I add more test cases?
  • Apparently at the moment this problem is undecidable (which I found out way too late). Would this problem be decidable if I let solutions assume that ambiguous grammars will always have an unambiguous counterpart (in other words, the program will never be given an inherently ambiguous grammar?

Background

A Context-Free Grammar (CFG) is a set of rules for constructing strings. For example, the following is a CFG describing BF:

progcommand | command prog
command+ | - | , | . | < | > | loop
loop[ prog ]

Let's see how the BF program ,[-] can be constructed using this grammar:

Parse tree for a context-free grammar

Wikipedia formally defines a grammar as a group of four items:

  • A set of nonterminals, which are the "variables". In the example above, these are prog, command, and loop.
  • A set of terminals, which are symbols in the alphabet that strings are composed of. In the example above, these are the BF program characters +-,.<>[].
  • A set of production rules, which define what nonterminals are allowed to become. Each rule consists of a head, which is a nonterminal, and a body, which is a list of terminals and nonterminals. In the example above, these are the production rules:
    • progcommand
    • progcommand prog
    • command+
    • command-
    • ...
    • commandloop
    • loop[ prog ]
  • One nonterminal that serves as the starting point for the grammar (in other words, the root node in the parse tree). In the example above, this is prog.

Consider the following context-free grammar:

bitstringbit | bit bitstring
bit1 | 0

It may be tempting to collapse the two lines:

bitstring1 | 0 | bitstring bitstring

The disadvantage of this representation over the original is that it is ambiguous - that is, given a string, it is possible to deriving that string in multiple different ways. For example, in this grammar, the string 101 may be derived as ((10)1) or (1(01)).

The problem with ambiguity is that there is not a single way to create a representation of the generation process, which is useful for e.g. parse trees.

A useful subset of CFGs

To make CFGs easier to manipulate, we will constrain them in this way:

  • Restrict the alphabet of terminals to 0 and 1,
  • Identify nonterminals by a number rather than a name (either 0- or 1-indexed),
  • Assume the first nonterminal (0 or 1 depending on indexing scheme) to be the initial one.

In this way, we have reduced the description of a CFG down to two inputs:

  • A number representing the quantity of nonterminals
  • A list of production rules, which is a list of pairs (head, body), where head designates a nonterminal for the head, and body is a list of terms which can be terminals or nonterminals.

The Task

Given a representation of a context-free grammar as described above, output a truthy or falsey value representing whether the grammar is ambiguous.

This is , so the shortest valid submission (measured in bytes wins).

Specifications

  • You can use any two distinct non-empty strings instead of 1 and 0 for the terminals.
  • You can assume the lists representing the bodies of the production rules are nonempty.
  • You may take input in any reasonable format. If you are taking input as a number and a list and your language does not support mixed-type lists, you can assume the existence of two special nonterminals that represent the terminals 0 and 1. If this is done, please specify the two nonterminals in your answer.
  • You can assume that every nonterminal can "halt", that is, be mapped to a finite string of nonterminals. This means that you will never get an input like:

    string0 string | 1 string

    This also means that every nonterminal must have at least one production rule.

  • Keep in mind that production rules are technically a set. The order of the rules is not relevant, so your program should be able to handle them in any order.
  • You can assume there will be less than 100 production rules, and therefore less than 100 distinct nonterminals.
  • You can assume that the input will be a well-formed CFG in whatever input format you designate.

Test Cases

In these examples, nonterminals are zero-indexed.

Ambiguous (Truthy)


Only empty strings:

1, [
    (0, []),
    (0, [0])
]

Readable form:

string | string


Any string of bits:

1, [
    (0, []),
    (0, ["0"]),
    (0, ["1"]),
    (0, [0, 0])
]

Readable form:

string | 1 | 0 | string string


Nonempty strings of ones, separated by zeroes:

2, [
    (1, ["1"]),
    (1, ["1", 1]),
    (0, [1]),
    (0, [0, "0", 0])
]

Readable form:

stringones | string 0 string
ones1 | 1 ones


Odd-length strings of bits:

1, [
    (0, ["0"]),
    (0, ["1"]),
    (0, [0, 0, 0])
]   

Readable form:

string0 | 1 | string string string


1 and 0 balanced like parenthesis:

1, [
    (0, []),
    (0, ["1", 0, "0"]),
    (0, [0, 0])
]

Readable form:

string | 1 string 0 | string string


Unambiguous (Falsey)


Only empty strings:

1, [
    (0, [])
]

Readable form:

string


Any string of bits:

1, [
    (0, []),
    (0, ["0", 0]),
    (0, ["1", 0])
]

Readable form:

string | 0 string | 1 string


Nonempty strings of ones, separated by zeroes:

0, [
    (0, [1]),
    (0, [1, "0", 0]),
    (1, ["1"]),
    (1, ["1", 1])
]

Readable form:

stringones | ones 0 string
ones1 | 1 ones


Odd-length strings of bits:

2, [
    (0, [1]),
    (0, [1, 1, 0]),
    (1, ["0"]),
    (1, ["1"])
]

stringbit | bit bit string bit0 | 1


1 and 0 balanced like parenthesis:

1, [
    (0, []),
    (0, ["1", 0, "0", 0])
]

Readable form:

string | 1 string 0 string


\$\endgroup\$
  • \$\begingroup\$ I think the CFG is described quite well, but the "useful subset" seems a little confusing - you restrict terminals to [0,1] and non-terminals to numbers and say "...body is a list of terms which can be terminals or nonterminals", but in the examples you have bodies containing quoted numbers. \$\endgroup\$ – Jonathan Allan Aug 24 '17 at 23:39
  • \$\begingroup\$ @JonathanAllan Yes, the quoted ones are terminals, and the unquoted ones are indices of nonterminals. I might change that if it turns out to be too complicated. \$\endgroup\$ – Esolanging Fruit Sep 21 '17 at 2:24
1
\$\begingroup\$

Is it Odd or Even

A group is an "Odd or Even group" if there is some member a such that every member in the group can be represented as either k • k or k • k • a.

For example the group Z4 is an even odd group if a = 1

0 = 2 • 2             Even
1 = 2 • 2 • 1         Odd
2 = 1 • 1             Even
3 = 1 • 1 • 1         Odd

The even and odd members can overlap, for example in Z5 if a =1 every member is both even and odd.

0 = 0 • 0 = 2 • 2 • 1 Even and Odd
1 = 3 • 3 = 0 • 0 • 1 Even and Odd
2 = 1 • 1 = 3 • 3 • 1 Even and Odd
3 = 4 • 4 = 1 • 1 • 1 Even and Odd
4 = 2 • 2 = 4 • 4 • 1 Even and Odd

An example of a group that is not an Even or Odd group is the Klein-4 group (Z2×Z2), because k + k = 0 for all k meaning there can be only one even member and one odd member despite there being 4 members of the group.

Task

Given the Cayley table of a finite group determine if it is a Odd or Even group. You will be guaranteed that the input is a group, but you will not be guaranteed anything else. This is a so your code should output two distinct values one for accept and one for reject.

Answers will be scored in bytes with fewer bytes being better.

Test cases

True

0 1
1 0

0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2

0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

0 1 2 3 4 5
1 0 4 5 2 3
2 5 0 4 3 1
3 4 5 0 1 2
4 3 1 2 5 0
5 2 3 1 0 4

False

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

0 1 2 3 4 5 6 7
1 2 3 0 5 6 7 4
2 3 0 1 6 7 4 5
3 0 1 2 7 4 5 6
4 5 6 7 0 1 2 3
5 6 7 4 1 2 3 0
6 7 4 5 2 3 0 1
7 4 5 6 3 0 1 2
\$\endgroup\$
  • \$\begingroup\$ The first paragraph is difficult to understand: It is not very clear that you define the terms "even" and "odd" and that the definition is dependent on a. Furthermore you first talk about numbers, but then talk about members of a group, so I'd avoid mentioning numbers, and perhaps link the wikipedia page about groups. The additive notation suggests you're only considering abelian groups, is that true? I'd also define first Z_n as the cyclic group of order n. \$\endgroup\$ – flawr Oct 5 '17 at 19:52
  • \$\begingroup\$ Next question: The definition of "even" and "odd" seems to depend on a, so what is a then in your test cases? \$\endgroup\$ – flawr Oct 5 '17 at 19:55
  • \$\begingroup\$ @flawr I'll try to clean up the first bit but addressing your second question. In the truthy examples a can be any member of the following sets {1}, {1,3}, {0,1,2,3,4}, {1,2,3} (same order as examples). \$\endgroup\$ – Wheat Wizard Oct 5 '17 at 20:02
  • \$\begingroup\$ @flawr Is that a better explanation? \$\endgroup\$ – Wheat Wizard Oct 5 '17 at 20:04
  • \$\begingroup\$ Yes now it is a lot clearer! One question remains, do you only consider abelian groups? \$\endgroup\$ – flawr Oct 5 '17 at 20:29
  • \$\begingroup\$ @flawr No, the 4th test case is the dihedral 6 group which is not commutative. \$\endgroup\$ – Wheat Wizard Oct 5 '17 at 21:02
  • \$\begingroup\$ In that case you'd probably be better off using multiplicative notation and explicitly saying that it is possible that the operation is noncommutative. \$\endgroup\$ – flawr Oct 5 '17 at 21:05
  • \$\begingroup\$ I think you should add some more explanation about the input, without some knowledge of group theory one cannot understand what is a Cayley table or what to do with it. (You use just $Z4$ or $Z5$ in your explanation, but then there are tables in the test cases, which is confusing) \$\endgroup\$ – Leo Oct 6 '17 at 4:34
  • \$\begingroup\$ Could use a test case where the number of distinct squares is at least half the size of the group but the group is not odd or even. \$\endgroup\$ – Peter Taylor Oct 6 '17 at 7:33
  • \$\begingroup\$ @PeterTaylor I'd rather not. The test cases are already much larger than the rest of the question, and there are not a lot of falsy cases. If there is such a case then it would be enormous. \$\endgroup\$ – Wheat Wizard Oct 6 '17 at 13:04
1
\$\begingroup\$

Evaluate a Starting Position in a Partitioning Game


Two players play a partitioning game. At the start of the game, there are n stones, all in a single heap. When a player takes a turn, they must divide an existing heap into two, ensuring that every heap still has a distinct size. The game is over when a player has no legal moves; that player loses.

For example, suppose that Max and Min are playing with n=6. Initially it is Max's turn, and he divides the starting heap into a heap of size one and a heap of size five. Min then divides the heap of size five into heaps of size two and three (her only option because she cannot make another heap of size one). Max, seeing heaps of size one, two, and three, has no legal move and loses.

Alternatively, Max could have split the size-six heap into heaps of size two and four. But then Min could not split the heap of size two (she would end up with both new heaps having size one), nor could she split the heap of size four evenly (for the same reason), so she would be forced to split the heap of size four into heaps of size one and three. Max would have lost anyway.

Since Max, the player to move first, has no winning strategy at n=6, call six a losing number. Similarly, call values of n for which Max can win (at least if he plays cleverly) winning numbers. Max wants a way to distinguish winning and losing numbers for his upcoming rematch against Min.

Write a program or function that, given an n, returns or outputs one value for losing numbers and a distinct value for winning numbers. For testing purposes, the first 50 winning numbers are:

3, 4, 5, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 27, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 78, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93

(This sequence is related to, but distinct from A161983.)

Rules and scoring are as usual for . The checkmark will go to an answer with well-explained and/or especially clever golfing, even if it doesn't compete with terser languages.

\$\endgroup\$
1
\$\begingroup\$

Generate a program to output a string in yup

yup is an older language of mine with the following commands:

0   Pushes 0 to the stack.
e   Takes an argument N and pushes exp(N).
|   Takes an argument N and pushes ln(N).
~   Switches top two items on stack.
:   Duplicates the top item on the stack.
-   Subtracts the top of stack from the second-to-top of stack.
{   Begin while loop (while top of stack is positive and is defined).
}   End while loop.
$   Reverse the stack.
[   Moves the bottom of the stack to the top of the stack.
]   Moves the top of the stack to the bottom of the stack.
*   Pushes an input item (char/number) to the stack.
\   Terminates the program.
@   Outputs top of stack as a character. (When used on a non-int, rounds the real portion.)
#   Outputs top of stack as a number.

For example, the program 00e pushes 0, then 0, then pops a 0, pushing exp(0), yielding the stack [0, 1].

Rules

Your challenge, should you choose to accept it, is to create a program that, when given a string, outputs a short yup program that would output the given string. Your score is determined by the total number of bytes used to generate all test cases below.

Test cases

Formatted as a .JSON file (array of strings):

["Hello, World!", " !\"#$%&'()*+,-./0123456789:;<=>?", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "zyxwvutsrqponmlkjihgfedcba", "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz", "", "[[<<>>]]", "adksjf 9823-0 =-ao0sdf';zlx", "b662bf6c7a7cac66561025cf2509506f", "yup", " ~!}", "death surely will find us all", "NO_ONE_IS_HERE", "Ra Ra Rasputin", "hello\nWORLD", "*0e-{0e-}#", "            ", "go play nethack", "\ttabs\n vs spaces\r\n", ".", "~", "it is not necessarily unfair that we can single-handedly close challenges, --MrXcoder", "\nconst math = require(\"mathjs\");\nconst escape = require(\"escape-string-regexp\");\nconst Stack = require(\"./stack.js\");\nconst entries = require(\"./entries.js\");", "Never gonna give you up\nNever gonna let you down\nNever gonna turn around\nAnd outgolf you", "010100101000001000100111101010", "O0O0O0OOOO00O000O0OOOO0O00O0", "[0, [1, [2, 3], 4], 5]", "(()()()))))(()()))"]

If I feel submissions too heavily optimize for the given inputs, I will use a second set of words, with an md5hash of 30272eee598205bab2904e9768502517.

\$\endgroup\$
  • \$\begingroup\$ Will you use the second set of words for all submission or only the one you feel like it's optimized? Also why not just combine both sets in any case? \$\endgroup\$ – ბიმო Oct 26 '17 at 16:55
  • \$\begingroup\$ @BruceForte Once I feel that there are optimized answers, I will use the second list. (It's really just a variation of the first list with changed characters and similar, to ensure optimizing some constants but not others is prohibited) \$\endgroup\$ – Conor O'Brien Oct 26 '17 at 17:13
1
\$\begingroup\$

The XOR Quines!

Your challenge is to make a program that outputs its source code but when each of its bytes are XORed with its answer number, it outputs the source code of the previous program.

For example, if the previous program was:

print 1

and your program is number #2, than your program could be this:

cngpv*%rpklv"3%+

which outputs in your language:

cngpv*%rpklv"3%+

and when each byte is XORed with 2, you get:

alert('print 1')

which outputs the previous program:

print 1

Note that the first program doesn't have to do anything other than output its own source code.

The second-to last answer after a month of no answers posted wins.

\$\endgroup\$
  • \$\begingroup\$ This is going to be too hardcore. \$\endgroup\$ – my pronoun is monicareinstate Oct 25 '17 at 12:21
  • 1
    \$\begingroup\$ This is going to be way too hard except in certain esolangs. Since every answer builds off of the previous one, they are probably going to get bigger. I would recommend starting with a simple esolang that ignores most characters. \$\endgroup\$ – Esolanging Fruit Oct 25 '17 at 15:53
1
\$\begingroup\$

Insertion sort counter

Calculate the number of moves necessary to do an insertion sort of an input vector containing positive integers.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

You must count the number of times a number is moved from its original position. For instance, the vector [1,2,3,4] requires no moves, as it's already sorted, while the vector [1,3,4,2] requires one move, since the last 2 must be moved two places to the left.

Example:

Input: 
[6, 5, 3, 1, 8, 7, 2, 4]
Sorting:
0: [6, 5, 3, 1, 8, 7, 2, 4]
1: [5, 6, 3, 1, 8, 7, 2, 4]
2: [3, 5, 6, 1, 8, 7, 2, 4]
3: [1, 3, 5, 6, 8, 7, 2, 4]
4: [1, 3, 5, 6, 7, 8, 2, 4]
5: [1, 2, 3, 5, 6, 7, 8, 4]
6: [1, 2, 3, 4, 5, 6, 7, 8]
Output: 6

Test cases:

To be added!

\$\endgroup\$
  • \$\begingroup\$ You should describe what an insertion sort is, for those who don't know. \$\endgroup\$ – Okx Oct 24 '17 at 9:13
  • \$\begingroup\$ Will do :) Thanks. \$\endgroup\$ – Stewie Griffin Oct 24 '17 at 9:13
  • \$\begingroup\$ As defined, the answer is always len(input). I've no idea what the example is supposed to show (or how it's counting). \$\endgroup\$ – Peter Taylor Oct 25 '17 at 7:27
  • \$\begingroup\$ @PeterTaylor The number of insertions (maybe I should call it moves, or something else?) necessary for the array [1, 2, 3, 4] is zero. The number of moves for the array [1, 3, 4, 2] is one, since the only number that must be moved when using the insertion sort algorithm is the last 2, that must be moved two steps to the left, resulting in a sorted array. Placing a number back in its original position doesn't count as an insertion/move. Does that make sense? \$\endgroup\$ – Stewie Griffin Oct 25 '17 at 7:58
  • \$\begingroup\$ So "Count the number of array elements a[i] which are not the greatest element in a[:i+1]"? \$\endgroup\$ – Peter Taylor Oct 25 '17 at 8:25
  • \$\begingroup\$ I guess that's another way to put it, yes... \$\endgroup\$ – Stewie Griffin Oct 25 '17 at 8:53
  • 1
    \$\begingroup\$ Maybe you could have it count the number of swaps assuming that you can only move a number by swapping it with one of its neighbors (and many implementations of insertion sort actually do this, especially those operating on arrays). For example, the number of moves for [1,3,4,2] would be 2, because the number 2 must be shifted twice to the left. \$\endgroup\$ – Leo Oct 26 '17 at 4:37
  • \$\begingroup\$ That's actually a good idea. Thanks! :) I'll probably change it when I get the time. :) \$\endgroup\$ – Stewie Griffin Oct 26 '17 at 6:04
1
\$\begingroup\$

Tear Down that Wall

Related (dupe?)

  • This is my first time submitting a challenge.
  • Suggestions and constructive criticism are always welcome.

Cops:

As the cop, your task is to create a code that outputs this ASCII wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__

However, by deleting some part(s) of the code, it must also output a broken wall:

___|___|___|___|___|___|___|___|___|__
_|___|___|___|___|___|___|___|___|___|
___|___|___|___|___|___|___|___|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__
_|___|___                    |___|___|
___|___|_                    __|___|__

Rules:

  1. Your code must terminate in a reasonable amount of time as long as it's correct. That means that the whole code and the correctly broken code must output the wall (broken or not) within 60 (too much or too little time? sugestions?) seconds. That doesn't apply if the code is incorrectly broken by the robber.
  2. The broken wall needs to be output(ted? English is hard) without addition of code.
  3. You may obfuscate the code as much as you see fit. (does hashing/encrypting count as obfuscating? if so, should it be allowed?)
  4. You must state what language you used in your answer.
  5. Your wall will be safe if, after 1 week, it hasn't been broken. You must also reveal the answer. Your wall will not be safe until you have revealed the answer.
  6. The outputs must match the exact ASCII walls provided. Leading/trailing newlines are allowed as long as the output matches the one provided. The walls consist of 13 lines and 38 columns of the characters | and _. The broken section of the wall is a block of 20 whitespace characters per line, beginning at the fourth line. The "padding" is of 9 characters (| or _) to either side of the whitespace block.
  7. Preferably, include a link to an online interpreter for your chosen language.

(any other rules suggestions?)

Robbers:

As the robber, your task is to, well, break the wall!

Rules:

  1. You may not add any code to the answer, only delete.
  2. The code is considered broken if and only if it outputs the entire broken wall.
  3. The broken code must be a valid submission in the same language as the original code.
  4. Please include in your answer a link to the answer you cracked and which part(s) of the code you modified.

Sandbox:

  • Suggestions?
\$\endgroup\$
1
\$\begingroup\$

Square-free Rock-Paper-Scissors tournament

On the day of the Codegolf Rock-Paper-Scissors tournament you hear through the grapevine that everybody else is going to play a fix square-free sequence (a sequence made of the letters R, P, S is square-free if it does not contain a subsequence that repeats twice. See Don't repeat yourself in Rock-Paper-Scissors for details.)

Task

Write a program that for a game of N rounds, in each round n

  1. prints one of R, P, S - its own nth hand (using all information gained so far)
  2. receives an input of either R, P, S - the nth letter of the opponent's sequence

Rules

  • Rock beats scissors, scissors beats paper, paper beats rock.

  • The "opponents" are all the square-free sequences of the given length.

  • Your program may read the opponents moves at once and print its own moves - as long as it is functionally equivalent to a program reading the moves in the order specified in section "task".

  • The program does not carry a state between playing against different opponents.

  • Each entry should include a scoring script computing the score of the candidate against all square-free sequences of length N.

Scoring

I am posting this to get some input about interesting scoring methods and a good choice of N.

Programs should score high if they win against a large fraction of square free sequences in an economic way. A possible criterium of "winning" against a single sequence is winning more hands against an opponent than losing. A possible criterium of scoring high is number of games won divided by the root of bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd say 16 could be a good choice for N, this would give 798 different opponents, which are still a manageable amount, and each game would probably be long enough to make the square-free analisys matter \$\endgroup\$ – Leo Oct 31 '17 at 3:39
  • \$\begingroup\$ To win with a small margin it is enough to exploit that the sequence does not repeat. I think we need to put the winning margin into the score or put a threshold. \$\endgroup\$ – mschauer Oct 31 '17 at 7:58
  • \$\begingroup\$ Maybe (rounds won - rounds lost)/bytes^2 , where rounds are counted from all the matches together \$\endgroup\$ – Leo Oct 31 '17 at 8:50
1
\$\begingroup\$

Can You Catch the Robber?

This is not a cops and robbers type challenge, but a code-golf challenge based on the PBS Infinite Series video Cops and Robbers Theorem.

Challenge

You will be given an undirected and connected graph. You may also assume the graph contains no self-loops; that is, the graph will not contain a vertex with an edge connecting to itself. You must determine if the graph is cop-win. That means that if a cop and robber start at any vertex, the cop will eventually land on the same vertex as the robber, with the cop and robber taking turns traversing one edge at a time, starting with the cop. Both the cop and the robber are playing optimally and have the option to not move on their turn.

If you haven't watched the video, let me explain how to simplify the problem. First, let's start with a definition. A pitfall is any vertex v whose neighbors are all a distance of 0 or 1 from a common vertex w, where v is not equal to w. To determine if a graph is cop-win, you must repeatedly remove pitfalls and the edges that connect to it until the graph is reduced to a single vertex or there are no more pitfalls to remove. If the graph can be reduced to a single vertex in this way, it is cop-win. A couple visual examples follow.

Example 1

>o---o---o
  \ / \ /
   o---o
    \ /
     o

  o---o<
 / \ /
o---o
 \ /
  o

 >o
 / \
o---o
 \ /
  o

>o---o
  \ /
   o

 >o
 /
o

o

Result: Cop-win

Example 2

  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
 /     \
o       o
 \     /
  o---o

Result: Not cop-win

Examples

Input: [[2,3],[2,4],[0,1,3,4,6],[0,2,5,6,8],[1,2,6,7,9],[3,8],[2,3,4,8,9,10],[4,9],[3,5,6,10],[4,6,7,10,11],[6,8,9,11],[9,10]]
Output: Truthy

Input: [[3],[4],[5],[0,5,6],[1,6],[2,3,7],[3,4,8],[5,9],[6,9,10],[7,8,11],[8],[9,12],[11]]
Output: Falsy

Input: [[1,2],[0,3],[0,3],[1,2]]
Output: Falsy

Input: [[1,2,3],[0,2,3],[0,1,3],[0,1,2]]
Output: Truthy

Rules

You may take input as an adjacency list, adjacency matrix, or list of edges, whose vertices may be 0-indexed or 1-indexed. Your output must be a truthy or falsy value. This is , so the least number of bytes in each language wins.

Notes

This is my first post; I could certainly benefit from some help in formulating and polishing my challenge. If anyone believes my language was ambiguous or contradictory to what was said in the video, please help me clarify.

\$\endgroup\$
  • \$\begingroup\$ What is the input here? It looks a list of each vertex's neighbors, but could you clarify? \$\endgroup\$ – KSmarts Oct 3 '17 at 15:16
  • \$\begingroup\$ Yes that's what I was going for, an adjacency list. A map of each vertex to a list of its neighbors. \$\endgroup\$ – kamoroso94 Oct 3 '17 at 16:34
  • 2
    \$\begingroup\$ This looks like a good question: meaty enough that there's something to golf, but simple enough not to scare everyone away. What I would suggest is flexibility in the input: allow people to choose whether to take input as adjacency matrix, adjacency list in the format you've used for the test cases, or list of edges. Also, allow people to use 1-indexed vertices rather than 0-indexed if they prefer. \$\endgroup\$ – Peter Taylor Oct 10 '17 at 8:18
  • \$\begingroup\$ I definitely agree with your suggestion of input leniency. I'll update the challenge. \$\endgroup\$ – kamoroso94 Oct 12 '17 at 8:57
  • 1
    \$\begingroup\$ I'd suggest explaining what a cop-win graph is in full, including the start positions and that both players play an optimal strategy. A link to a non-video explanation would also be good for anyone who can't or doesn't want to watch a video. \$\endgroup\$ – xnor Oct 12 '17 at 21:06
  • \$\begingroup\$ Thank you for the feedback, @xnor. I've worked it into the challenge. I feel it's an improvement. I think that the visual examples take up too much vertical space, so I'm not sure if I should include them or not. \$\endgroup\$ – kamoroso94 Oct 31 '17 at 2:17
  • \$\begingroup\$ IIRC it shouldn't be "start at any vertex", but the selection of the start position is part of the game, also under condition of optimal play, with the cop selecting their position first. \$\endgroup\$ – Christian Sievers Oct 31 '17 at 13:00
1
\$\begingroup\$

Polynomial Partition

META: Right now I'm wondering whether it would be a more interesting challenge to have two imput lists, and the program just needs to find a polynomial that separates the two lists (i.e. no connected component can contain points of both classes. Or altnernatively f(x,y)>0 for all (x,y) in list A, and f(x,y)<0 for all (x,y) in list B.

Given a finite list of at at least two points in the plane ℝ² (all points in the list are unique), your program should find a polynomial f in ℝ[x,y] whose zero locus Z(f) := {(x,y) ∊ ℝ² | f(x,y) = 0} partitions the plane such that each of the connected components of ℝ²\Z(f) contains at most one point of the input list. The goal is finding such an f of a low degree. (It does not have to be optimal.) Note that no point of the input list may be contained in Z(f).

Scoring

The score for each test cases is the degree of the polynomial that your algorithm produces. The total score is the product of the scores of the testcases.

Examples

The points {(0,0),(0,2)} can be separated by f(x,y) = y - 1 (degree 1) or f(x,y) = x² + y² - 1 (degree 2) or f(x,y) = x³ + 1 - y(degree 3) or (infinitely) many more.

The points {(1,1),(-1,1),(-1,-1),(1,-1)} can be separated by f(x,y) = xy (degree 2).

Test Battery

to be included...

\$\endgroup\$
  • 1
    \$\begingroup\$ (1) I presume that the words "a different" are missing from "each of the inputs is in ^one of the connected components". (2) Is the optimal solution not going to be one of the easiest approaches? \$\endgroup\$ – Peter Taylor Nov 3 '17 at 11:44
  • \$\begingroup\$ Thanks for the feedback, I rewrote (1), regarding (2): One very easy not optimal solution would be making a a small enough circle around every point, so I guess it depends. \$\endgroup\$ – flawr Nov 3 '17 at 14:43
1
\$\begingroup\$

Palindromic Collapse

Given a string s, traverse from left-to-right, finding the first prefix that is a palindrome. When you encounter the first prefix palindrome, remove the end-half of the palindrome. Insert it back into the original string, then restart again from the left side of the new word. Return the final result when no prefixes are palindromes.

Take for example "babble":

  • First check would be [ba]bble, which is not a palindrome, move on.
  • Second check would be [bab]ble, which is a palindrome (bab).
    1. Compress the palindrome to the first "half", [bab] becomes [ba].
    2. Reattach this in place of the original palindrome, resulting in [ba]ble
  • Next we repeat, finding [bab]le again, and resulting in [ba]le after steps 1 and 2.
  • We then iterate through the full word again, finding no palindromes, returning bale.

More Examples (worked out)

moom

[mo]om (not a palindrome)
[moo]m (nont a palindrome)
[moom] (palindrome) -> [mo]
[mo]   (not a palindrome, done).

Final returned result: mo


abalbalba

[ab]albalba (not a palindrome)
[aba]lbalba (palindrome) -> [ab]lbalba
[ab]lbalba  (not a palindrome)
[abl]balba  (not a palindrome)
[ablb]alba  (not a palindrome)
[ablba]lba  (palindrome) -> [abl]lba
[ab]llba    (not a palindrome)
[abl]lba    (not a palindrome)
[abll]ba    (not a palindrome)
[abllb]a    (not a palindrome)
[abllba]    (palindrome) -> [abl]
[ab]l       (not a palindrome)
[abl]       (not a palindrome, done)

Final returned result: abl


More 1-1 Examples

amanaplanacanalpanama -> amnaplanacanalpanama
1232132121            -> 123
1232132145            -> 12345
01001000123210        -> 01123210
01000000000000000001  -> 011
010101                -> 011
abbabababaa           -> ab
hellollehworld        -> helloworld
world                 -> world
<empty string>        -> <empty string>
\$\endgroup\$
  • \$\begingroup\$ You like palindrome a lot, don't you? \$\endgroup\$ – Mr. Xcoder Nov 7 '17 at 20:00
  • \$\begingroup\$ @Mr.Xcoder in all fairness it looks like Oliver Ni likes them more. \$\endgroup\$ – Magic Octopus Urn Nov 7 '17 at 22:06
1
\$\begingroup\$

Validate a StarCraft II Build Order

Explanation

You must decide whether the input represents a valid StarCraft II Build Order. Here is how you will decide:

  1. Start with the first word (it will be the race, Zerg, Protoss, or Terran)
  2. Set the list of valid units to just the ones from that race (explained later)
  3. Loop through the input (split by space)
    1. Check if the unit is in the list of valid items for the listed race
      • Otherwise, output Invalid item + the listed item's name
    2. Check that the player has enough supply to sustain that unit (if it's a unit) (explained later)
    3. Check that the player has the prerequisites for that item

Units and Structures

(will be listed in real question)

Example:

Terran:

  • CommandCenter 0 supply, requires SCV gives +15 supply
  • OrbitalCommand 0 supply, requires CommandCenter (consumes)

Zerg:

  • Hatchery -1 supply, requires Drone (consumes) gives +6 supply
  • Drone 1 supply, requires Hatchery
  • SpawningPool -1 supply, requires Hatchery, Drone (consumes)

Protoss:

  • Nexus 0 supply, requires Probe gives +15 supply

StarCraft II Mechanics

At the beginning of the game, the player starts with a town hall (Nexus, CommandCenter, or Hatchery + Overlord) and 12 workers (Probe, SCV, or Drone).

Supply is the maximum number of units one can have. Supply Depots, Pylons, and Overlords give more supply.

The sum of the supply of all produced units can never exceed the current supply value (we ignore Zerg hacks).

The Supply cannot exceed 200.

Input

You will receive an input in any valid way in this format:

Race <item> <item> .....

There will be at most 99 items, and they will be at most 30 chars long.

The race will be one of Zerg, Protoss, or Terran.

\$\endgroup\$
1
\$\begingroup\$

Lines per file

Can't believe it was not questioned yet.

I want the shortest script you can supply to take on all files on a directory and output a list in the format

file number_of_lines

Every possibility should be accounted as a valid line terminator:

- <CR>
- <LF>
- <CR><LF>
- <LF><CR>

No winner, it is a per language basis. Still thinking if I should give some bonus for sorting by line count.

\$\endgroup\$
  • \$\begingroup\$ Duplicate. Not the same but pretty much the same idea, would definitely get closed for dupeness. \$\endgroup\$ – Rɪᴋᴇʀ Nov 14 '17 at 18:58
  • \$\begingroup\$ @Riker: Counting lines requires some more effort than the file's byte size! I had even posted an answer on that question! \$\endgroup\$ – sergiol Nov 14 '17 at 21:18
  • 1
    \$\begingroup\$ It's literally just wc -l to count lines.. I'm not sure about most of the others, but I know at least my bash can be trivially modified to count lines. \$\endgroup\$ – Rɪᴋᴇʀ Nov 14 '17 at 21:33
1
\$\begingroup\$

Prune my tree

Given a well-formed ASCII art tree and the name of a node, print or return a new, well-formed tree with that node and any children removed.

†Contains non-ASCII characters.

Example

Given this input tree:

A
├ B
├ C
│ └ D
└ E

...and the node name E, the following should be returned:

A
├ B
└ C
  └ D

Well-formed trees

Rather than an exhaustive spec, I'll define well-formedness by example:

A
├ B
├ C
├ D
│ ├ E
│ └ F
├ G
│ └ H
│   ├ I
│   │ ├ J
│   │ └ K
│   └ L
└ M
  ├ N
  │ └ O
  │   └ P
  ├ Q
  └ R

The above is the only valid way to represent this tree (rules above re: trailing spaces and newline apply here and henceforth). Note that:

  1. The tree is rendered with some strict subset of the characters , , , AZ, space, and newline.
  2. The tree has one root node (in this example A) with no characters to its left or right.
  3. Each line has exactly one node.
  4. Each and is followed by a single space (required) and node name.

Rules

  • Standard loopholes are forbidden.
  • This is an challenge; input and output must be a string or array of lines or equivalent, per standard rules.
  • Trailing spaces and/or a single trailing newline are allowed in both input and output.
  • You may use any character encoding, as long your solution prints or returns characters equivalent to , , and . (ASCII characters like +, | (pipe) and L (capital "l") are not equivalent.)

    See also "Freebies" under "Scoring" below.

Input

  • The input tree will have at least one node.
  • The given named node may or may not exist in the tree. If it does not exist, the original tree should be returned.
  • Each node name will be a single character between A and Z inclusive. Node names will be unique and there will be no more than 26 nodes.
  • Node names are not guaranteed to be contiguous nor in any particular order, e.g. the following is possible input:

    Q
    └ D
    

Output

  • The output tree may have zero nodes.
  • The order of the remaining nodes in the output tree must be the same as the input tree.

Scoring

This is . The shortest solution in bytes wins.

🌟Freebies🌟: If the literal characters , , or appear in your source code, you may count them as one byte each, per occurrence.

Test cases

I'll reuse a few trees for multiple test cases.

  1. Input tree:

    A
    
    • Output if A removed:

      
      
    • Output if B removed (B doesn't exist):

      A
      
  2. Input tree:

    A
    ├ B
    ├ C
    │ └ D
    └ E
    
    • Output if C removed:

      A
      ├ B
      └ E
      
    • Output if D removed:

      A
      ├ B
      ├ C
      └ E
      
    • Output if E removed:

      A
      ├ B
      └ C
        └ D
      
  3. Input tree:

    A
    ├ B
    ├ C
    ├ D
    │ ├ E
    │ └ F
    ├ G
    │ └ H
    │   ├ I
    │   │ ├ J
    │   │ └ K
    │   └ L
    └ M
      ├ N
      │ └ O
      │   └ P
      ├ Q
      └ R
    
    • Output if H removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if L removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      ├ G
      │ └ H
      │   └ I
      │     ├ J
      │     └ K
      └ M
        ├ N
        │ └ O
        │   └ P
        ├ Q
        └ R
      
    • Output if M removed:

      A
      ├ B
      ├ C
      ├ D
      │ ├ E
      │ └ F
      └ G
        └ H
          ├ I
          │ ├ J
          │ └ K
          └ L
      

Questions for sandbox:

  1. Enough/too many/missing test cases?
  2. Enough/too many/missing details re: input/output?
\$\endgroup\$
  • \$\begingroup\$ I would just make this an (actual) ASCII-art challenge. Up to you but meh \$\endgroup\$ – HyperNeutrino Nov 13 '17 at 19:24
  • \$\begingroup\$ Given the proximity to Christmas, you could go for "trim the tree" as the title. \$\endgroup\$ – Nissa Nov 13 '17 at 21:47
  • \$\begingroup\$ I think you should show the larger test case(s) with A removed. I know/guess it will be an empty output, but still, it's a corner case that will benefit from being properly shown. \$\endgroup\$ – Stewie Griffin Nov 15 '17 at 12:24
  • \$\begingroup\$ I like the idea, but I too would prefer ASCII-only. Non-ascii adds a bunch of bytes without adding anything to the challenge itself. \$\endgroup\$ – Stewie Griffin Nov 15 '17 at 12:29
1
\$\begingroup\$

Smallest Proth Prime Power

A Proth Prime is a prime number of the form (k*2^n)+1.

The Challenge

Given a positive integer k, return the smallest non-negative integer n such that (k*2^n)+1 is a prime.

This is code-golf, so smallest answer in bytes will win!

OEIS link for this sequence

OEIS link for sequence shifted by 1, with alternative calculation method

Test cases:

Input Output
1     0
2     0
3     1
4     0
5     1
6     0
7     2
8     1
9     1
10    0
11    1
12    0
13    2
14    1
15    1
16    0
17    3
18    0
19    6
20    1
46    0
47    583
48    1

TODO:

  • Rework preamble
  • More/better test cases?
\$\endgroup\$
1
\$\begingroup\$

Make a program run infinitely

For this challenge, you will be given a program in a very simple stack-based 2D language (that will be specified by this challenge), and your task is to find an input that will make it run infinitely (i.e. make it have 0% probability of halting). For the sake of this challenge, it will be fully deterministic; that is, no random functions will exist.

Language specifications

The program runs on a 2D cartesian grid and there is a single pointer with an (x, y) coordinate and a direction (up, down, left, or right). The memory is stack-based. The pointer starts in the top-left corner at (0, 0), moving to the right. After each command is finished executing, the pointer moves one space in the direction it is currently facing. The grid is cylindrical on both sides. The following commands exist:

Movement

Absolute

^ pointer direction becomes "up"
> pointer direction becomes "right"
v pointer direction becomes "down"
< pointer direction becomes "left"

Relative

] rotate pointer direction right 90 degrees (up -> right -> down -> left ->)
[ rotate pointer direction left 90 degrees (up -> left -> down -> right ->)
# invert pointer direction (up -> down ->, left -> right ->)
| horizontally reflect pointer direction (left -> right ->)
_ vertically reflect pointer direction (up -> down ->)
\ diagonally reflect pointer direction (up -> left ->, down -> right ->)
/ diagonally reflect pointer direction (up -> right ->, down -> left ->)

Operators

+ push pop + pop
- push pop - pop
* push pop * pop
: push pop / pop (integer/floor division)
% push pop % pop (modulo; the result is the same sign as the base)

Stack Operations

. pop a value
, get a value from the input and push it to the stack
$ swap the top two values of the stack
& duplicate the top value of the stack

Conditionals

! if the top of the stack is falsy, move the pointer an extra step in its current direction (skip next command)
? if the top of the stack is truthy, rotate right, otherwise, rotate left

Other

space: do nothing
0-9  : push the value of that digit
;    : terminate

You will be given a 2D grid in any desired format (newline-delimited string, array of lines, array of arrays of character, etc). You may assume that all rows are of the same length. You can choose any set of characters to represent these; in other words, any bijection between a set of characters or a set of integers and the characters ^v<>[]#|_/\+-*:;%.,$&!? 0123456789 is valid.

You must return an array of numbers in any reasonable format where when these values are fed one-by-one into the program as inputs, the program will not terminate. There may be more than one such solution; if so, you must return at least one of them, and you do not have to be consistent in which ones you return, as long as at least one is returned. Note that the array must be finite; that is, if it keeps looping through a ,, then it does not count as a solution. There is always at least one solution.

After the program is run, no inputs should remain; that is, there must be exactly the right number of inputs in the array.

You may assume that there is at least one solution where all of the numbers are in the range [0, 256).

Test Cases

,!v;
 >v      =>  [1] (or any other single truthy value)
 ^< 

,v>v;  
 >?>?v<
  >v>>^  =>  [1, 0] or [0, 1] (or any other array of two values with opposite truthiness)
   >?  
    ;  

,1-!;v<  =>  [-1] (only this value works)
     >^

Sandbox

  • Is this too hard?
  • Is there anything unclear or anything needing more clarification?
  • Is this too easy?
  • Is the language too complicated for a challenge like this?
\$\endgroup\$
  • \$\begingroup\$ I don't really understand what 'push' and 'pop' mean thus the operator section is a little confusing to me. Also I think you need to include ; in the list of characters that one can make a bijection from. Also, would it make sense to swap the \ and / commands? If you do the characters would represent mirror planes (or plain mirrors) but now they seem a little counterintuitive to me. \$\endgroup\$ – dylnan Nov 16 '17 at 19:45
  • 1
    \$\begingroup\$ @dylnan 1. push and pop are stack operations meaning put a value onto the top of the stack and remove the top of the stack and return its value, respectively. So for example, push pop + pop means pop a value off the top, pop another value off, add them, and push it onto the top of the stack. Also, yes, I missed ;, thanks for noticing. Also, I got confused by my own wording so yes, \/ should be swapped. Thanks for the comments! \$\endgroup\$ – HyperNeutrino Nov 16 '17 at 20:07
  • \$\begingroup\$ So, if I understand, the submissions will take code in the 2D language as input, and the output will be values that, when fed into the input code, would cause it to run infinitely? \$\endgroup\$ – Kamil Drakari Nov 16 '17 at 20:30
  • \$\begingroup\$ @KamilDrakari Yep. \$\endgroup\$ – HyperNeutrino Nov 16 '17 at 20:43
  • \$\begingroup\$ How would the conditionals ! and ? deal with the stack? In your second test case, if the stack is 01 (say the right is the top) and the first ? sees the 1, wouldn't the stack have to be popped in order for the second ? to see the 0 and move into the infinite loop? \$\endgroup\$ – dylnan Nov 17 '17 at 1:21
  • \$\begingroup\$ Also, I think is too hard due to the halting problem. Even with the busy beaver Turing machines it becomes very difficult to determine whether a machine will halt with machines of only a few states. Maybe if you somehow restrict the possible modes of running infinitely (e.g. program will only run infinitely if it gets into <^>v or <v>^ loops) and restrict the length of the program but even then I think it might be too hard but I'm not sure \$\endgroup\$ – dylnan Nov 17 '17 at 1:44
  • \$\begingroup\$ @dylnan It theoretically shouldn't be too impossible because you can just go through all possible states and if it ends up in the same state as before, it will loop infinitely (because there are no non-deterministic commands). It will be horribly inefficient, but eh, it's code-golf, efficiency is not the priority :P \$\endgroup\$ – HyperNeutrino Nov 17 '17 at 1:59
1
\$\begingroup\$

Packing Density of Polyline Defined Shapes

So... I was making bacon this morning and I couldn't fit all of my bacon into my pan. However I oriented the strips, there was always one or two pieces that didn't fit. Culinary endeavors aside, here's my challenge:

Input:

pan and bacon

Each of these inputs is a list of (X,Y) coordinates that define a closed shape. The very first index and the very last index are different, but the shape is closed. It not guaranteed that the shape is convex, but it is guaranteed that the path doesn't cross itself. Further, for simplicity, you may expect all the (x,y) coordinates to be integers.

Your program must find the most occurences of bacon that can fit into the pan, allowing rotation and flipping.

Output:

An integer that represents how much bacon can fit in the pan.

Scoring and rules:

For proper cooking:

  • A bacon may touch another bacon or the edge of the pan.
  • bacon may not overlap, nor may it go off the pan.
  • The first index of both pan and bacon is always (0,0).
  • If there is a tie in number of bytes, the user whose code is formatted to look like ASCII bacon wins.
  • If two users tie and both have ascii bacon, upvotes wins. Standard rules apply. This is code golf, so the standard rules apply.

Sample input and output:

Test Case 1:

Bacon directly overlaps the pan, and is the same size.

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon: [(0,0),(0,1),(1,1),(1,0)]
Output: 1

Test Case 2:

When bacon is bigger than pan

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon: [(0,0),(0,2),(2,2),(2,0)]
Output: either 0 or an error.

Test Case 3:

What happens when bacon crosses itself?

pan: [(0,0),(0,1),(1,1),(1,0)]
bacon:[(0,0),(1,1),(0,1),(1,0)]
Output: just error here. Any way you feel like. If you manage to report an http 418 error, you get bonus points, redeemable for nothing.

Test Case 4:

What happens if the bacon doesn't exactly overlap the pan?

pan: [(0,0),(0,3),(5,3),(3,0)]
bacon: [(0,0),(0,2),(2,2),(2,0)]
Output: 2

\$\endgroup\$
  • 1
    \$\begingroup\$ This looks like a tough question, but I like it. 1.) Are the coordinates integers or can they be floats? 2.) Is the shape guaranteed to be convex and contain more than two coordinates? 3.) Because this is a code golf challenge, it's unlikely anyone will go for the second output, so you should probably stick with just one of the two output methods. 4.) Example inputs and outputs would be great. \$\endgroup\$ – Laikoni Nov 16 '17 at 21:15
  • \$\begingroup\$ Having arbitrary polygons make this tough, even just to figure out if one shape fits inside another. I think you'll do well to have extensive test cases that probe at the possibilities and defy heuristics. \$\endgroup\$ – xnor Nov 16 '17 at 21:42
  • \$\begingroup\$ I've added quite a few test cases using minimal pans and bacon. @xnor, what do you mean by 'defy heuristics'? \$\endgroup\$ – Jakob Lovern Nov 16 '17 at 21:57
  • \$\begingroup\$ @JakobLovern Like, for example, making it so that code that just outputs the ratio of the areas doesn't happen to pass all test cases. Other examples could be making sure the code allows bacon to be rotated by non-multiples of 90 degrees, doesn't just try to do some greedy fill from one corner, considers reflecting the bacon, etc. The idea is that someone whose code meets all the tail cases should be reasonably certain it meets the problem conditions. \$\endgroup\$ – xnor Nov 16 '17 at 22:36
  • 1
    \$\begingroup\$ @JakobLovern My experience has been that writing the code to do the task has been very helpful to think of edge cases and to generate test cases. You can then post it as (ungolfed) reference code, which is often appreciated by solvers. \$\endgroup\$ – xnor Nov 16 '17 at 22:43
1
\$\begingroup\$

Implement a basic two-dimensional esolang

There are hundreds of two-dimensional stack-based esoteric programming languages out there, and lots of them follow a very similar syntax:

v redirect instruction pointer down
> redirect instruction pointer right
^ redirect instruction pointer up
< redirect instruction pointer left
/ redirect instruction pointer: up -> right, right -> up, left -> down, down -> left
\ redirect instruction pointer: up -> left, left -> up, right -> down, down -> right
0 push 0 to the stack. 1 pushes 1, ... 9 pushes 9.
A push 10 to the stack. B pushes 11, ... F pushes 15.
: duplicate the top stack value
~ swap top two stack values (all languages implement this as a different character)
i read input as a ASCII character and push to stack
o print the top of stack as an ASCII character
n read input as integer and push to stack
u print the top of stack as an integer
+ increment the top of stack
- decrement the top of stack
! jump over the next command
; stop execution

Almost all two-dimensional esolangs contain more commands, but for the sake of simplicity, the one we're writing will contain only the above.


Specification

The stack should be able to hold at least 30,000 values. You may pick any integer size (e.g. 32-bit, 64-bit, unbounded, etc) for stack values.

The instruction pointer should start moving right from the top left corner of the source code, and should wrap upon exiting the playing field, meaning that this code will be an infinite loop:

<^
v>

First, < will be reached, pointing the IP off to the left.
The IP will wrap around to the right, continuing left, and hit the ^, directing it up.
Then it will wrap, hit the > and travel right, wrap, hit the v and travel down, wrap, hit the <, and start over.

\$\endgroup\$
1
\$\begingroup\$

Squaring the circle

Background

This is a generalization of this question on puzzling.SE. Essentially, it asks you to generate a circular array of integers such that any two adjacent integers add to a perfect square, and that the integers are a permutation of those from 1 to 50. The original question gave you a part of the array, and asked you to solve it. I wish to generalize this problem.

Problem Description

Given an integer n, generate a circular array of numbers from 1 to n such that any two adjacent integers sum to a perfect square, without repeats of any number.

Input

Input is limited to positive integers greater than or equal to two.

Output

If there is no possible array (as can be manually proven to be the case for n=4), then your function should gracefully handle the error and exit.

Otherwise, it should output a representation of that array for that n as a string of delimited integers, such that, if the string were concatenated into a long integer, it would be the minimum possible string. To illustrate:

1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Of these six representations, only 1 2 3 is in minimal form.

You may delimit your string in any consistent, parsable way you choose.

Example I/O

For n<32, there are no valid arrays (And I can prove it, if necessary.) The smallest n with a valid array is n=32, and it is structured:

=>01 08 28 21 04 32 17 19
15                       30
10                       06
26                       03
23                       13
02                       12
14                       24
22                       25
27                       11
  09 16 20 29 07 18 31 05

The output to n=32, would therefore be 1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

Example code

Because code is clearer than words, here's a (purposefully) very naive and inefficient routine for this in Python (2.7):

import math, itertools
def main(n):
  def test_if_a_given_list_is_a_ring(input_list):
    is_a_square = lambda value: math.sqrt(value).is_integer()
    output_flag = True
    for index in range(len(input_list)):
      if is_a_square(input_list[index]+input_list[index-1]):
        continue
      else:
        output_flag = False
      #end if
    #end for
    return output_flag
  #end test_if_a_given_list_is_correct
  def turn_it_into_a_string(input_list):
    temp_list = []
    for i in input_list:
      temp_list.append(str(i))
    #end for
    output_string = ''
    for i in temp_list:
      output_list += ' '+ i
    #end for
    return output_list[1:]
  #end turn_it_into_a_string  
 lowest = string(n)*n

 for perm in itertools.permutations(range(n,0,-1)):
    if test_if_a_given_list_is_correct(perm):
      flag = True
      for perm_character,lowest_character in zip(turn_it_into_a_string(perm),lowest):
        if int(lowest_character) < int(perm_character):
          flag = False
          break
        #end if
      #end for
      if flag:
        lowest = turn_it_into_a_string(perm)
      #end if
    #end if
  #end for
  return lowest
#end main

If you're gonna golf this code... I'd highly recommend optimizing it first.

Scoring

Programs will be scored based on: 1. Asymptotic complexity 2. Average runtime 3. Byte count 4. Runtime when the byte count is fed into the program as input

(I can't decide which of these scoring systems to use. Note that I've manually worked out that when n<=31, there are no arrays. At n=31, there is a valid double loop system, but no valid single loops.)

\$\endgroup\$
  • \$\begingroup\$ your example is not a valid ring, is it? I only see two perfect squares, 11+5=16 and 1+8=9 \$\endgroup\$ – Luca H Dec 1 '17 at 9:18
  • \$\begingroup\$ No, it isn't. As of ten minutes ago, I constructed (By hand) the ring for n=32, so I'll post that. \$\endgroup\$ – Jakob Lovern Dec 1 '17 at 18:56
  • \$\begingroup\$ (1) "ring" has a specific meaning (an algebraic structure with multiplication and addition subject to certain rules), which is distracting. How about changing it to circular array? (2) In my opinion, "generate a [circular array] of numbers from 1 to n" does not impose a restriction on the length of the array or on the impossibility of repeats. For me the clearest way to add the restrictions which I infer from the linked question would be to say that it's a permutation of the numbers from 1 to n. \$\endgroup\$ – Peter Taylor Dec 1 '17 at 21:02
  • \$\begingroup\$ (3) "This is a two part question": I only see one part. If you intend a follow-up, maybe worth including it so that you can get opinions on whether it would be closed as a dupe of the first part. \$\endgroup\$ – Peter Taylor Dec 1 '17 at 21:03
  • \$\begingroup\$ @PeterTaylor I was originally intending to ask the question twice, but score using different conditions. I expect that code which would minimize asymptotic complexity wouldn't look at all similar to code which minimizes size. I wanted to see the difference. You made a good point on the dupe problem, though, as the two questions are essentially similar to each other. \$\endgroup\$ – Jakob Lovern Dec 1 '17 at 21:44
  • \$\begingroup\$ So what's the scoring? If byte-count gets fed to the program no solutions that are < 31 bytes & if it's gonna be an average runtime based scoring you should choose large enough values such that it becomes about complexity and include how you measure. \$\endgroup\$ – ბიმო Dec 3 '17 at 3:10
  • \$\begingroup\$ That's exactly why I was asking for input on my various ideas for scoring. I don't expect that there's going to be any programs that small that can successfully answer the question, but it could happen. I'm leaning towards asymptotic complexity or byte count. \$\endgroup\$ – Jakob Lovern Dec 5 '17 at 18:01
1
\$\begingroup\$

Advancing k-combinations

k-combinations for a set of size n represent in what different ways one can pick k elements out of a set of n elements. There is a natural representation of such a pick as an integer with n bits, of which exactly k are set.

Define next[n, k] :: Pick(n, k) -> Pick(n, k) to be the group action that takes each pick to the next one, wrapping around. More formally: Let r be an n-bit integer with k bits set. Then next[n, k](r) will return the smallest integer > r that also has k bits set. If there exists no such integer, the smallest integer with k bits is returned. Example: next[4, 2](0b0011) = 0b0101, next[4, 2](0b1100) = 0b0011.

[- Annotation: if k = 0, then there is only one unique integer with zero bits set. next[n, 0](r) = 0. -]

You will be given a pick r and a positive integer step. Output (next[n, k]^step)(r), that is, apply next[n, k] step times to r.

Rules

  • You will be given 4 integers n k r step. Output (next[n, k]^step)(r)
  • 1 <= n can be assumed to be small enough to represent picks as integers naturally in your language
  • 0 <= k <= n
  • r will always be a valid pick of k out of n.
  • 0 <= step <= C(n, k) can be relatively large. As an example, C(32, 12) = 225,792,840

Criteria

Return the correct output for all valid inputs.

This is code-golf, shortest code wins.

Examples

4   2 0b1001 2  => 0b1100
16 10 0xF11F 10 => 0bF15E
4   2 0b1100 2  => 0b0101
\$\endgroup\$
  • \$\begingroup\$ Nice challenge! But what if k = n = 0? And maybe specify formally how next works. \$\endgroup\$ – ბიმო Dec 3 '17 at 5:38
1
\$\begingroup\$

Best Yahtzee score

Yahtzee is a game played with five six-sided dice and a score sheet with thirteen different boxes to fill a score in. Each box has its own scoring rules:

  • 1s, 2s, 3s, 4s, 5s, 6s all score points equal to the sum of the respective dice (that is, a roll of [3, 2, 3, 1, 5] scored as 3s would be awarded 6 points - 3 for each 3).
  • 3-of-a-kind and 4-of-a-kind (as they sound, three or four dice rolled the same) score points equal to the sum of all five dice.
  • Full house (two dice show one value, the other three show another) scores 25 points
  • Small straight (four consecutive values) scores 30 points
  • Large straight (all consecutive values) scores 40 points
  • Yahtzee (all dice show the same value) scores 50 points

The thirteenth (chance) makes sense in-game, but not so much for this challenge; additionally the game has bonuses for extra Yahtzees which make no sense here. Because the challenge is...

Given five dice as input (five integers 1-6, input however is convenient), output the highest score that roll can score as well as what box it's being score under. The score should be output as its decimal numeric value, whether that's an integer or a string representation thereof, whatever. It should be immediately recognizable as a number. How you identify boxes is up to you so long as they are all unique and any given roll that will be scored in a given box always returns the same value. Please specify in your answer how boxes are identified. Order ([score, box] or [box, score]) does not matter. If you're outputting to STDOUT or otherwise not returning two values from a function, please separate score and box with at least one non-alphanumeric character of your choosing.

Code golf, so shortest answer in a given language wins. Standard loopholes apply.

Test cases, using , as separator, and 123456kKfsly for the box names (respective of their order above):

in: 1 5 4 3 2
out: 40
in: 1 1 4 3 1
out: 10
in: 1 1 6 5 3
out: 6

Sandbox/meta

  • I saw one existing Yahtzee challenge, but IIRC it boiled down to scoring a whole game. I did the 'given five dice, what is the best score' exercise once and felt like there were some interesting challenges to be found in optimizing it.
  • Better ways to express I/O? I want it to be flexible but relatively readable...
  • My first potential submission, I'm sure I'm forgetting something...
\$\endgroup\$
  • 2
    \$\begingroup\$ IMO, multi parts output is pretty much a party killer. In that specific question, I think the score itself is enough to constitute a nice challenge. The box value is drived by conditional programming, which (of the challenge goes well) might not be present in some answers. \$\endgroup\$ – Uriel Dec 6 '17 at 22:58
  • 1
    \$\begingroup\$ Anyway, for that wide range of possibilities, you should add at least one test case to cover collisions, multiple scorings and at least one of each box type (again, as I see challenges here) \$\endgroup\$ – Uriel Dec 6 '17 at 23:00
  • \$\begingroup\$ @Uriel Thanks for the input — I planned to fill in more test cases, I guess I could've mentioned that in the meta section. I'm not trying to be difficult, but I'm curious if you could expand on your other point w/ the score itself being enough. The score is (I believe?) entirely dependent on the box being determined, and spitting something box-related out seems programmatically like a small challenge vs. the 'reward' of the output. This was why I wanted that output to be very flexible. Part of me thinks you're right, part of me thinks I'm right… so if you have more to say, please do… \$\endgroup\$ – brhfl Dec 7 '17 at 2:37
  • \$\begingroup\$ my point is, in order to get the right score the user necessarily went through the right box (and not even print it, but also did a somewhat-more-complex calculation with it) - so it's kinda like letting them output twice. \$\endgroup\$ – Uriel Dec 7 '17 at 10:02
  • 1
    \$\begingroup\$ @Uriel Makes sense, and I was leaning that way the more I thought about it last night. Cutting it also eliminates the need to address collisions. I think it's out... Thanks! \$\endgroup\$ – brhfl Dec 7 '17 at 13:35
1
\$\begingroup\$

Google Doodle Kids Coding-style simulator

One input is a list of commands. There are three action commands and a loop construct. There is some flexibility as to the command format:

  • As a string or equivalent: The loop construct should use a pair of matching brackets. The direction commands should be < and > or L and R (either case). The motion command should be ^ or F.
  • As a list of characters: The loop construct should be a sublist. The other commands should be individual characters in the list, specified as above.
  • As a list of integers: The direction commands should be -1 and 1 while the motion command should be 0.

The other input is the starting position. This consists of an two-dimensional array in any suitable format (including a newline-separated string). Background values should be represented using 0 or spaces. Carrots should be represented using -1, ^ or V (either case). The starting square should be represented using 1, @, or R (either case).

Optionally, the starting direction can be an input (one of <>V^ or an angle in degrees or turns), or it can be hard-coded (please specify the default starting direction in this case).

Command rules:

  • Loops always execute four times
  • The direction commands rotate the rabbit in place
  • The motion command moves the rabbit one square in the current direction

The rabbit wins if it eats all of the carrots.

The rabbit dies if:

  • It runs out of commands
  • It walks out of bounds
  • It walks onto the background

The starting square and carrot squares are all safe.

Your output should be a consistent truthy value if the rabbit wins, and a consistent falsy value if it dies. This can also be achieved by exception or error exit.

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

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Emigna Dec 8 '17 at 11:51
  • \$\begingroup\$ What's the background? \$\endgroup\$ – user202729 Dec 8 '17 at 12:07
  • \$\begingroup\$ 1) exception exit is already a standard way to output a falsey value, and 2) in the actual Google doodle you don't lose if you try to walk off the edge of the map, it just does nothing. \$\endgroup\$ – Nissa Dec 8 '17 at 14:02
  • \$\begingroup\$ @StephenLeppik It's not meant to exactly simulate the Doodle. \$\endgroup\$ – Neil Dec 8 '17 at 14:32
  • \$\begingroup\$ By "background" I means as in "It walks onto the background". \$\endgroup\$ – user202729 Dec 9 '17 at 10:04
  • \$\begingroup\$ @user202729 The background is any square whose value is 0 or space depending on your input format. \$\endgroup\$ – Neil Dec 9 '17 at 10:55
  • \$\begingroup\$ Ready to post to main? \$\endgroup\$ – user202729 Dec 11 '17 at 5:48
  • \$\begingroup\$ Don't abandon this... :( \$\endgroup\$ – user202729 Dec 18 '17 at 15:43

You must log in to answer this question.

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