Sandbox for Proposed Challenges

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

Sandbox FAQ

Posting

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Get the Sandbox Viewer to view the sandbox more easily!

• Also, I'd love some advice on how to specify what to do for some of the more "exotic" languages. e.g. C and such will obviously just use function-pointers… but I really don't want to alienate any Jelly golfers; those solutions are always my favorite! – JamesTheAwesomeDude May 20 at 15:49
• Even function-pointers in C wouldn't help afaik, because you can't dynamically construct the function. Maybe you should allowed output the source of G, or alternatively make R take m and pk and just function directly as G. – Command Master May 21 at 7:48
• @CommandMaster Thanks for the feedback! Would defining R(digest, pk) work? Such that it gets composed: R(φ(m), pk) -- (this would also align better with the way the original paper defined them.) – JamesTheAwesomeDude May 21 at 14:08
• I think it would work, and it's also good because it lets programming languages without the concept of a "function" participate – Command Master May 21 at 14:15
• @CommandMaster How's the current setup look? I'm certainly worried about accomodating languages without functions. Especially Jelly; I'm not really sure how it works, but I always enjoy those answers a lot! – JamesTheAwesomeDude May 21 at 14:39
• I've edited this down to a stub now that it's been posted to save space – caird coinheringaahing Jun 7 at 1:02

Write a netquine

There are a lot of online interpreters, for a lot of languages. For example, there's the ubiquitous TIO, but there are also smaller, more specific ones that others have made, such as interpreters for Vyxal, ngn/k, or Grok.

Your goal today is to write a netquine, or a program whose output, when used as a URL, leads to that program in an interpreter for that language. Essentially, if you have a link to your program, and the program outputs that link, it's valid.

For example, say you write a Vyxal program λλλλ. In the Vyxal interpreter, if you press the button to generate a permalink for this program, you get:

http://lyxal.pythonanywhere.com?flags=&code=%CE%BB%CE%BB%CE%BB%CE%BB&inputs=&header=&footer=


However, due to the way that the interpreter processes links, you could also leave out the blank fields:

http://lyxal.pythonanywhere.com/?code=%CE%BB%CE%BB%CE%BB%CE%BB


You can even replace the HTML character codes with the actual characters:

http://lyxal.pythonanywhere.com/?code=λλλλ


All of these are valid links to the Vyxal program λλλλ, and therefore would all be valid outputs for a netquine.

• Obviously, Standard loopholes are forbidden.

• Even though URL shorteners are forbidden by default, shortening a URL, like in the example, is fine, as long as it still leads to the right place.

• For the purposes of this challenge, a web browser may be considered an "interpreter" for HTML and/or CSS. This means you might be able to do something along these lines.

• Usual rules apply, as do usual rules.

• This is , so the shortest answer in bytes wins!

Meta

• Is this question clear enough?

• Should I change the scoring to accommodate the potential differences in URL length? (lengths of domain names, different ways of generating links, the ability to shorten links, etc.)

• Any other feedback?

• This question is quite similar, but it only allows for TIO languages, and it doesn't allow any sort of shortening, even if the link is still valid (there was a comment asking about that), so I would consider it to be related, but not a dupe.

• Interesting idea, but you won't get many answers because most online interpreters use an external compression algorithm to shorten the hash (and then base64 it), which is quite lengthy to implement from scratch. Note that the existing answers on the linked challenge all use a gzip or zlib builtin. – Bubbler Jun 9 at 23:12
• You should provide a list of valid online interpreters, as someone could just make a.com lead to an interpreter for a program in some language that outputs https://www.a.com. Also, please define "in" in the sentence "leads to that program in an interpreter". Does the HTML of that page simply have to contain the program? – Makonede Jun 9 at 23:40

Determine Centrosymmetric String

Let's define a centrosymmetric string as follows:

• First, add spaces to the end of each line to make the input a rectangle $$\ A_{m×n} \$$.
• The input is "centrosymmetric" string if and only if you get the original rectangle if you rotate the rectangle 180°. That is, it has 2-fold rotational symmetry, so $$\ A_{i,j}=A_{m+1-i,n+1-j} \$$ holds for all $$\ A_{1\dots m, 1\dots n} \$$.

Input

Input a non-empty string. You may assume it:

• does not contain leading / trailing new lines;
• does not contain trailing spaces on any lines;
• only contains new line, space, and lowercase a-z.

You may choose to handle any of CR, LF, or CR-LF as the new line character in your program.

Input may be in any reasonable format, including but not limited to:

• A built-in string type;
• A NULL-terminated character array;
• An array of integer code-points;

Note that you are not allowed to take the string padded already as it trivialises the challenge.

Output

Determine if the given input is a centrosymmetric string (as defined in this post), outputting two distinct values, or truthy vs. falsey values (they can be swapped relative to their normal meaning).

Test cases

Truthy

a

aba

a
b
a

ab
ba

abc
cba

abc
ded
cba

a a

a

a

a

a

a c
b
c a

a

b
b

a

zzzzz
z
z
z
zzzzz

n  n  oo   oo  n  n
nn n o  o o  o nn n
n nn o  o o  o n nn
n  n  oo   oo  n  n


Falsy

ab

a
a
b

a
b
a

ab
ab

aa
bb

   a
a a
aaaaa
a     a

• I think a worked-through example would be a good idea – pxeger May 31 at 8:29
• What is the meaning of the 2 in A_{m×n}2? – pxeger May 31 at 8:37
• Related – pxeger May 31 at 8:39
• When you say "square", do you actually mean "rectangle"? – Bubbler May 31 at 8:40
• @pxeger the 2. is accidentally left there after I remove the line break between 1. blah 2. blah. Should be removed. – tsh May 31 at 8:44
• @Bubbler changed to rectangle. I'm not quite sure about these words. – tsh May 31 at 8:44
• @tsh A square is a rectangle with all side lengths the same, so m == n. Sometimes in English, "square" is used as an adjective to simply mean "having right-angled corners", which is quite confusing – pxeger May 31 at 8:46

Encode USB packets code-golfbinarycoding-theoryencoding

Posted

• Is the fifth example correct? Shouldn't 11111111 (8 ones) be JJJJJJKKK? If not, how is 11111111 distinguished from 11111101? (This also applies to your other challenge). – Spitemaster Jun 6 at 19:33
• @Spitemaster yep, you're right - fixed. – pxeger Jun 9 at 14:33

Given matrix $$\A\$$ and $$\A^n\$$, work out any possible positive $$\n\$$.

Examples:

• $$\\begin{pmatrix}1&2&3\\3&2&1\\1&0&1\end{pmatrix},\begin{pmatrix}36&32&44\\52&40&52\\12&8&12\end{pmatrix}\rightarrow 3\$$
• $$\\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix},\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\rightarrow \text{any integer }\ge 3\$$
• $$\\begin{pmatrix}0&1\\1&0\end{pmatrix},\begin{pmatrix}0&1\\1&0\end{pmatrix}\rightarrow \text{any odd positive integer }\$$

Sandbox Notes

• Since this question likely fall into pure matmul as , will this be ?
• If so, what size and $$\n\$$ is reasonable?
• Should it multiply in a modulo-$$\p\$$ ring?
• If someone provide enough extra info, they have right to post this question(actually that's why I posted in sandbox)
• Can you give some examples? – math Jun 11 at 17:01
• Sometimes lots of different n can work. What should we output then? – xnor Jun 12 at 23:06
• @xnor "Any possible positive n". But I agree that it should be specified better. – Recursive Co. Jun 14 at 11:22
• @ophact It's edited later than comment – l4m2 Jun 14 at 12:56

A Cat’s Game to Claim

Posted

• Any catchy name suggestions also appreciated! "Proclaim" rhymes as well, but I can't get it to roll of the tongue. – AviFS Jun 12 at 1:15

Build a raw string

In this challenge you will write code which, given a single line string as input, can output the raw version.

Full spec

The input will be a string like ab\n or ab\u0065e\\ or e\'543. These strings should be converted to a raw version which uses the backslashes.

This probably sounds confusing, so here is a more complete explanation.

The most common form of strings used is simply a quote (one of ', " or the backtick), followed by a sequence of unicode characters, then a closing quote which corresponds the opening one. "abc" or 'THIS is a St%ing', for instance. Note that this is not the case in all languages, for instance most golfing languages do not represent strings in this manner.

However, it's not that simple. Backslashes allow for much more complex strings, and their importance in allowing certain characters means a string like 'ab\' is invalid as the backslash "escapes" the quote. Making a backslash appear in a string requires \\ instead.

Also, quotes can be escaped via \', \" or \. A sequence like \\" should become \" while \"\ is invalid.

The newline and tab are both important, and so most mainstream languages have the \n and \t which are actually 1 character each, representing the newline and the tab, respectively. So \\t\"\n becomes

\t"



(note the trailing newline)

To add an extra layer of usability for "exotic" characters, it is possible to use a unicode escape: of the form \uxxxx where each x is one of 0123456789abcdef. This transforms into the unicode character whose codepoint is equal to the base-10 equivalent to the hexadecimal number xxxx. For instance \u0031 becomes 1 because 31 in hexadecimal is 49 in base 10, and 1 has a codepoint of 49.

Your input string may contain any of these escapes, and you may assume that \ is followed only by the backtick or any of \'"tnu. The unicode escape sequence is guaranteed to be valid, and escapes as well.

You should output this string after the transformations described.

Worked example

Input string:

ab%\u0035e\n\n\t5\'e\\54c%&\u0095


The first three characters remain identical.

\u0035 becomes 5 because 35 in hex -> 53 in base 10, and String.fromCharCode(53) === '5'.

\n\n\t becomes two newlines followed by a tab.

5 remains 5.

\' becomes ': escaped by backslash

e remains e.

\\ becomes \.

54c%& stays the same.

\u0095 is an unprintable with codepoint 149.

Result:

ab%5e

5'e\54c%&<unprintable>


(<unprintable> is an actual unprintable character) Note that functions capable of evaluating such strings are disallowed. To be clear, your program must handle the syntax described above, and not any other format.

Other test cases:

Input Output
\'\" '"
\\"\' \"'
\\u0031\u0031\\t \u00311\t
\\\\\\\\\n \\\\<NL>

[<NL> is newline]

Meta:

• Duplicate? Couldn't find anything.
• Any clarifications needed?
• Better title / tags?
• A bit unclear to me: Do we need to handle the string syntax of the answer's implementation language, or the syntax you specify here? If that of our own language, then what if our own language has few special characters? (E.g. in the APL family, it is common that the only unusual character in a string is the quote, which must be doubled.) – Adám Jun 14 at 11:54
• "eval functions or similar are not allowed." but what constitutes being similar to eval? What about functions in the JSON object of JavaScript? What about library functions to do this? Does APL's built-in ⎕JSON utility function constitute an eval, though the language's real eval is ⍎? – Adám Jun 14 at 11:56
• @Adám In some calculator questions, the OP (wisely) decides to disallow eval functions. Basically these functions. In essence, from my point of view, if your language is capable of evaluating these strings, then the function that does them is disallowed. However since APL's eval seems different, you can use them. Also in response to the one asking about string syntax, you must handle the one in the question, otherwise it gets a little unfair. – Recursive Co. Jun 14 at 12:06
• Will the input include surrounding quotes? – Adám Jun 14 at 12:56
• @Adám Nope. (filler) – Recursive Co. Jun 14 at 13:01
• Then do we have to handle unescaped ' and/or "? – Adám Jun 14 at 13:03
• @Adám You still have to handle them, just not surrounding the entire string. – Recursive Co. Jun 14 at 13:08
• Suggested test cases: '" and \'\" – Adám Jun 14 at 13:09
• @Adám You know what, the idea of not having surrounding quotes is a little confusing, so I'll remove that rule. That means that your suggested test cases are identical to each other, so I'll add the latter to demonstrate. Also will add about five more cases. – Recursive Co. Jun 14 at 15:28
• "if this string were to be enclosed in quotes in your language and parsed as an expression, no errors should show." makes it sound as if my language matters. – Adám Jun 15 at 15:35
• @Adám I'll change that – Recursive Co. Jun 15 at 15:37
• Am I allowed to use \n in my code to insert a newline, or is this considered "functions capable of evaluating such"? – Adám Jun 15 at 15:58
• – Recursive Co. Jun 15 at 15:59

COBOL(lite) interpreter.

Your task is to code an interpreter for COBOL. This interpreter should use the free format, and cut a few corners, as long as a few test scripts will run on it.

Notice; here I say interpreter, as that is the general direction of my inclination, however if it may save bytes, a compiler would also count.

Try to:

• Golf your code as much as possible
• Remove some parts of COBOL (But ask here first to see if they make sense to remove.
• Accept both CAPITAL and lowercase

Avoid:

• Standard Loopholes
• Don't remove too many parts of COBOL. I think that IDENTIFICATION DIVISION. could be ignored, but DATA DIVISION. is probably necessary.

If there is a thing that you would like to clarify on, ask in the comments. I think that this question still could stand with improvement, before it can be added to the main cg se.

• You need to be a lot more specific with what you want implemented. This can range from syntax requirements to required keywords and function. You need to specify anything and everything yo want in a possible golfed interpreter. – Razetime Jun 15 at 10:39
• I recommend checking questions tagged under interpreter on the main site for guidance. – Razetime Jun 15 at 10:40
• @Razetime I didn't have a lot of time to make this post, but that is why it is in the sandbox. I know that I will need to improve it a fair bit, before putting it on the main code golf se – smarnav Jun 15 at 23:17

Implement a feature-rich calculator

We have a few many calculator challenges on this site, but none seem to require a complex one with many different features.

This challenge is about emulating my old Casio calculator, except with no digit limit. Features are:

• basic (start with a single operation, then input the next operation)
• all clear (AC) which starts a new "calculation". No need for C.
• errors for dividing by zero (otherwise there should be no error)
• memory: M to set the memory to current number, MC as an inline expression representing the memory, and M- to get rid of the memory.

This should operate either on STDIN (prompt for commands each time) or in a function (taking in either a list of commands or a newline-separated string with commands).

Spec

Your solution should be able to handle floating-point numbers, hence float division should be used regardless of context.

When first run, the calculator will be "ON". It is guaranteed that input syntax is valid.

The chain of commands begins with a number operation number-like structure, where number can be replaced with MC to represent a reference to the memory. For instance 5 * 5 or 6/MC. Whitespace can be ignored or forbidden, that can be your call, but whatever it is you may assume syntax is valid.

Then, if your submission is a full program, it should output the result of that operation, or if a function, append that to the end of a list.

Subsequent operations can either be:

• M this sets the memory to current number. Memory can only ever hold a single number at a time.
• AC. Clears the current calculation and resets the number. Memory, however, will still be accessible.
• M-. (M minus) This clears the memory, and calls to MC will never be given when there is nothing in the memory.
• operation number where operation is + - * or /, and number is a number which can be replaced with MC.
• Off. The command Off stops the program, and it is reasonable to assume that no commands will be passed afterwards.
• - (minus sign) negates current number. Outputs the new number.

Division by zero should trigger an error and restart the calculation. AC, M, MC and M- should output nothing. Memory can be overwritten.

Note that operation number operation number will never be given, and that all operations will be performed on non-negative numbers. (we have the negate operator for negative numbers)

Also note that this challenge is less about parsing / processing a string input and more about responding to different kinds of input.

Example

As a full program, but note that a function will have to take in an array of commands. There is a >  before each command, but in your version, it is not required.

> 5*5
25
> *4
100
> /200
0.5
> /0
ERROR (or some form of ERROR)
> 15*6
90
> M
> +MC
180
> AC
> 7-MC
-83
> -
83
> M-
> +5
88
> Off


Meta: is it a duplicate? any clarifications needed?

• Maybe use the [interactive] tag, and make it clearer that this is less parsing/processing a given string input and more responding to inputs as given – caird coinheringaahing Jun 18 at 14:16
• The "error" should not terminate the program, right? Would it be OK to, on error, print anything that is distinguishable from numeric output (say "X", "Inf", or "NaN"), or print something different across errors (e.g. "Inf" for 1/0, "NaN" for 0/0)? – Bubbler Jun 25 at 1:40
• @Bubbler Yes, that's fine. You can also output Inf for 1/0 and NaN for 0/0 like you mentioned. – Recursive Co. Jun 25 at 5:10

Convert codepoint to UTF-9

UTF-9 was an April Fool's Day RFC joke specifications for encoding Unicode suitable for 9-bit nonet platforms.

Challenge

Your task is to implement a program or a function or a subroutine that takes one integer, who represents the codepoint of a character, to return a sequence of integers that represents its corresponding UTF-9 value.

Examples

Numbers that begin with 0x are hexadecimal, begin with 0 are octal, end with b are binary. Otherwise, a decimal.

input: 0x41 or 65
output: [0101], [1000001b], or [65]

input: 0xc0
output: [0300]


Hint

Section 5.2 of RFC4042 has an example of the impmenentation.

Meta

Gotta need to clarify I/O format more.

• For clarity, I'd start octal constants with 0o. Also, an explanation of how UTF-9 works should probably be included here. – Redwolf Programs Jun 19 at 1:39

Outputting Blum Integers

• I'd suggest using standard sequence rules (answers can choose $n$th, first $n$ or infinite output). I've also edited the challenge a bit, feel free to revert any changes you dislike – caird coinheringaahing Jun 18 at 14:29
• @cairdcoinheringaahing thanks for the suggestion, i'll apply it – EliteDaMyth Jun 19 at 9:14

Do these points approximately make up a regular n-sided polygon?

The input is a set of integer coordinates. Take them in whatever form you want, e.g. a list of tuples or just a plain list. The question is: can you draw an n-sided regular polygon with vertices at the specified coordinates? n being the amount of coordinates provided. Answer truthy if yes, falsy if no.

The level of precision is in integers. That means you will have to round both the x and y values of the ideal polygons to the nearest whole values. Here's an example diagram:

The triangle has points at approximately (5,5), (4,9), (1,6). You can draw a regular triangle to fit these coordinates, even if the actual points of the triangle are not at quite the same coordinates.

The same goes for the pentagon. The coordinate set (3,1), (7,1), (8,5), (5,8), (2,5) makes up a regular pentagon-ish, accurate to whole values.

Any set of coordinates can make up an infinite amount of approximate n-gons. You answer truthy if there's at least one such n-gon. One way of thinking about it is to consider a unit square around each of the points, then determine if you can stretch a regular polygon such that every point falls within the squares.

Further ground rules:

• The coordinates will always be positive.
• They do not have to be in any particular order.
• Coordinate values will never exceed 1000.
• There will not be more than 10 coordinates.

Examples:

(5,5), (4,9), (1,6) -> true
(3,1), (7,1), (8,5), (5,8), (2,5) -> true
(1,1), (1,1), (2,1) -> true
(1,1), (2,1), (130,1) -> false

(42,42) -> true


(according to Wikipedia, a monogon is still a polygon, meaning any input is valid.)

(0,1), (5,10) -> true


(any two points make up a regular bigon so this should work for any coordinates)

(1,3), (1,3), (1,3), (1,3) -> true


(any set identical coordinates will always match an n-gon that's tiny enough to have all of its coordinates rounded to the same integer).

• I just found this question. It seems to be the same question but it is closed with no answers, and I think my requirements are clearer. – KeizerHarm Jun 16 at 12:12
• I don't think the current explanation addresses the question "How are we supposed to tell if the polygon is regular without knowing its exact coordinates?" I feel like there's some way to gradually constrain polylines, but not quite sure. Also, I think "One way of thinking about it is to consider a circle of half a unit around one of the points" should be "... consider a unit square around one of the points" instead. What is the expected output of (0, 0), (0, 2), (1, 1), (2, 0) (which is borderline square with (-0.5, -0.5), (-0.5, 1.5), (1.5, 1.5), (1.5, -0.5))? – Bubbler Jun 23 at 0:15
• @Bubbler Thanks for the comment. You are correct about the circle being a square! My mistake. And yes, that would be truthy. – KeizerHarm Jun 23 at 8:59
• @Bubbler regarding "how are we supposed to tell if polygon is regular" that's asking for an example answer strategy, not part of the question, is it? The question is whether there is any regular polygon where each point falls in those unit squares. That's almost an optimisation problem. It's not impossible, all the required information is there. But I could try to come up with one approach - but answers should not feel obligated to copy that approach because for this problem there would be many solution strategies. – KeizerHarm Jun 23 at 9:03

Is this a valid Temtem character name?

Given a string of between 0 and 15 (inclusive) printable ASCII characters, determine whether the string represents an acceptable character name for the game Temtem.

The following rules apply to character names:

• Names must have at least 3 letters (a-z)
• Names may have up to 2 total prefixes and/or suffixes of at least one letter
• Prefixes and suffixes must be separated from the name by one of space, hyphen or apostrophe
• The first letter of the name and each prefix may be capitalised but all other letters must be lower case.

Truthy examples:

Daddy's girl
de Morgan
Rip Van Winkle
Spider-Man
X-Men


Falsy examples:

McDonald's
-XX-
'falsy'


Note: Temtem may apply other checks to character names not included here.

As this is , Output must be a single consistent value for all valid names. Output for invalid names must be consistent for a given invalid name, but may vary between different invalid names, so for instance a count of errors is an acceptable output format.

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

• Are Rip Van winkle and spider-Man valid? – Adám Jun 27 at 12:59
• @Adám They are for the purposes of this question, yes. – Neil Jun 27 at 13:43

Find all paths

code-golf grid

Information

• Given a non-negative odd integer (let's call it $$\n\$$), find the number of all possible paths which covers all squares and get from the start to end on a grid.
• The grid is of size $$\n\$$x$$\n\$$.
• The start of the path is the top left corner and the end is the bottom right corner.
• You have to count the number of all paths which go from the start to end which covers all squares exactly once.
• The allowed movements are up, down, left and right.

Examples

1 -> 1
3 -> 2
5 -> 104
7 -> 111712
9 -> 2688307514
11 -> 1445778936756068

• More test cases would be needed. Is this oeis.org/A121788? – Luis Mendo Jun 27 at 15:24
• I dont think this is that problem in the link – PyGamer0 Jun 27 at 15:34
• Anyway, please include more test cases – Luis Mendo Jun 27 at 16:24
• Is this oeis.org/A001184? – tsh Jun 28 at 8:22
• yes it is @tsh updated! – PyGamer0 Jun 28 at 8:37
• === Looks good! === – A username Jun 28 at 8:43

Alteration of a challenge that was considered too close to an older quasi-duplicate.

ISO Computus

from a signed integer year number provided as sole input
the integer number of the calendar week of Easter Sunday as sole output
with as few variables and as few arithmetic operations as possible.

Easter Sunday is determined according to the Gregorian Computus (as used in the all Western Christian churches, including the Catholic Church, and some others), for which there are several equivalent algorithms available, see Computus, Gent, Stockton and ESTRALGS.TXT. There are 35 possible month-day dates, from 22 March to 25 April.

The week of the year is specified by international standard ISO 8601-1: All weeks start on Monday; there are no partial weeks; the first week of the year has 4 January (or the first Thursday) in it. For more information see the Mathematics of the ISO 8601 Calendar. There are just six possible results, weeks 12 through 17. W17 will hardly ever occur – it has never occurred since 1583 at least.

Restrictions

• You may use all basic arithmetic operators, including addition, substraction, multiplication, division, integer division, modulo, rounding (with integer flooring and ceiling), exponentiation, logarithms.
• You may not use library functions that implement an algorithm for the Computus, like PHP's easter_date(), EasterSunday[year] from the Mathematica Calendar package or Easter from the R package timeDate.
• You may not use other predefined date functions, e.g. to find the day of the week or the week of the year.

Ranking score

Your solution must be an algorithm implemented as an executable script in a programming language of your choice.

• Each numeric variable and constant, whether used by name or literal value, counts as 1 point.
• Each basic operation, as defined above, counts as 1 point.
• Each definition of a custom function or method counts as 5 points.
• Each call of a custom function or method counts as 1 point.
• Imports and similar initializations required by the programming language are ignored.
• Neither reading the input value and returning or printing the output value nor eventual variables for storing their value are counted.
• The answer with the fewest points wins.
• TBD…

Example:

function CFAQEaster(year) { // Calendar FAQ
// 5 points for Div() function
var G, C, H, I, J, L // 6 points for variables
G = year % 19        // 2: 1 point for modulo, 1 point for 19
C = Div(year,100)    // 2: 1 point for function call, 1 point for 100
H = (C - Div(C,4) - Div(8*C+13,25) + 19*G + 15) % 30
// 16: 8 points for operations, 2 points for function calls, 6 points for additional numeric values
I = H - Div(H,28)*(1 - Div(29,H+1)*Div(21-G,11))
// 13: 5 points for operations, 3 points for function calls, 5 points for additional numeric values
J = (year + Div(year,4) + I + 2 - C + Div(C,4)) % 7
// 6 points for operations, 2 points for function calls, 2 points for additional numeric values
L = I - J            // 1 point for substraction
EasterMonth = 3 + Div(L+40,44)
// 6: 2 points for addition, 1 point for function call, 3 points for additional numeric values
EasterDay = L + 28 - 31*Div(EasterMonth,4)
// 6: 3 points for operations, 1 point for function call, 2 points for additional numeric values
return {Y:year, M:EasterMonth, D:EasterDay}
// 63 points in total
}


Contemporary example input: output

• 2001: 15
• 2002: 13
• 2003: 16
• 2004: 15
• 2005: 12
• 2006: 15
• 2007: 14
• 2008: 12
• 2009: 15
• 2010: 13
• 2011: 16
• 2012: 14
• 2013: 13
• 2014: 16
• 2015: 14
• 2016: 12
• 2017: 15
• 2018: 13
• 2019: 16
• 2020: 15
• 2021: 13

The return value must be correct for a complete cycle of input years, i.e. from 1 through 5700000, even though the original event that is celebrated did not occur before 30 (if ever at all) and the Gregorian Calendar was not used before late 1582, i.e. the proleptic Gregorian Calendar applies.

Resources

• I believe this challenge is better done as alorithm-golfing rather than counting characters or bytes. However, I'm not sure at all how to award a score. The rules above are very much up to bikeshedding. – Crissov Jul 1 at 10:46
• The main problem with any kind of scoring like this is that many programming languages have very different set of built-in operations and features. How many points for using a mapping or reduction on an array? How many points for swapping two numbers on the stack? How many points for using the 1 command in Hexagony, which computes x>=0?x*10+1:x*10-1? A better way would be to fix the language and a very strict set of features available, like "use Python 3, only +-*/ operators on numbers are allowed". – Bubbler Jul 14 at 7:28

Generate the shortest regex to match these but not those

• A possible short program just enumerates all the regexes. This might not be feasible, and you may not be able to score submissions at all... – Trebor Jun 28 at 17:34
• @Trebor I don't quite understand what you mean by this. – user197974 Jun 28 at 18:13
• If you just write a program and tests, one by one, all the regexes, and outputs the first one that works, this would be a valid program. But to give it a score, you would probably need days, if not years. – Trebor Jun 29 at 8:06

Solve Fermat's Last Theorem with matrices

Fermat's Last Theorem states that there is no such triple of positive integers $$\(x, y, z)\$$ such that

$$x^n + y^n = z^n$$

for all integers $$\n > 2\$$. However, this conjecture does not hold for integer matrices:

\begin{align} & \left( \begin{matrix} 1 & 3 \\ 0 & 1 \end{matrix} \right)^3 + \left( \begin{matrix} -1 & 0 \\ 1 & -1 \end{matrix} \right)^3 \\ = & \left( \begin{matrix} 1 & 9 \\ 0 & 1 \end{matrix} \right) + \left( \begin{matrix} -1 & 0 \\ 3 & -1 \end{matrix} \right) \\ = & \left( \begin{matrix} 0 & 9 \\ 3 & 0 \end{matrix} \right) \\ = & \left( \begin{matrix} 0 & 3 \\ 1 & 0 \end{matrix} \right)^3 \\ \end{align}

You are to take two $$\k \times k\$$ integer matrices $$\A\$$ and $$\B\$$, and a positive integer $$\n \ge 2\$$, and output a $$\k \times k\$$ integer matrix $$\C\$$ such that

$$A^n + B^n = C^n$$

You may output any such $$\C\$$. You may also take $$\k\$$ as an input, and you may assume that $$\k \ge 2\$$

This is , so the shortest code in bytes wins

• Is it guaranteed that A, B, n are given so that such a C exists? Why not just make a challenge about taking the nth root of a given matrix (which is arguably the hardest part of the task)? – Bubbler Jul 14 at 6:54

Ordered, linear, affine, or relevant? code-golffunctional-programminglambda-calculuscombinatory-logicclassification

Background

Linear lambda calculus is a limited form of lambda calculus, where every bound variable must be used exactly once. For example, \a b c d e -> a b (d c) e is a valid term in linear lambda calculus. When embedded as a logic system, this enforces each input to be consumed exactly once. The equivalents in logic/type/language theory are called linear logic, linear type, and linear language respectively.

Ordered lambda calculus is a more limited version: it requires the variables to be used in the order they are introduced. \a b c d e -> a (b c) (d e) is such an example.

Affine and relevant lambda calculi are relaxed versions of linear lambda calculus.

• Affine: each variable must be used at most once. \a b c d e -> a (d c) e
• Relevant: each variable must be used at least once. \a b c d -> a (c b) (d c)

If omitting and duplicating a variable are both allowed, we get plain lambda calculus.

These have interesting relationship with BCKW combinator calculus:

• Ordered lambda calculus can be represented using just B and I combinators. (I is needed to represent \a -> a.)
\a b c d e -> a (b c) (d e)
\a b c d -> B (a (b c)) d
\a b c -> B (a (b c))
\a b -> B B (B a b)
\a -> B (B B) (B a)
B (B (B B)) B

• Linear lambda calculus can be represented using B and C combinators. (I is equal to BCC, and is used only for simplicity.)
\a b c d e -> a b (d c) e
\a b c d -> a b (d c)
\a b c -> B (a b) (C I c)
\a b -> B (B (a b)) (C I)
\a -> C (B B (B B a)) (C I)
C (B C (B (B B) (B B))) (C I)

• Affine lambda calculus can be represented using BCK. K allows to delete unused variables.
\a b c d e -> a (d c) e
\a b c d -> a (d c)
\a b c -> B a (C I c)
\a b -> B (B a) (C I)
\a -> K (B (B a) (C I))
B K (C (B B B) (C I))

• Relevant lambda calculus can be represented using BCW. W allows to duplicate variables.
\a b c d -> a (c b) (d c)
\a b c -> B (a (c b)) (C I c)
\a b -> W (\c1 c2 -> B (a (c1 b)) (C I c2))
\a b -> W (\c1 -> B (B (a (c1 b))) (C I))
\a b -> W (C (B B (B B (B a (C I b)))) (C I))
...

• BCKW forms a complete basis for the plain lambda calculus.

Challenge

Given a lambda term in the format below, classify it into one of five categories (ordered, linear, affine, relevant, none of these).

The input is a lambda term that takes one or more terms as input and combines them in some way, just like all the examples used above. To simplify, we can eliminate the list of input variables, and simply use the number of variables and the "function body", where each variable used is encoded as its index in the list of arguments. \a b c d e -> a b (d c) e is encoded to 5, "1 2 (4 3) 5". (Note that it is different from de Bruijn indexes.)

The function body can be taken as a string or a nested structure of integers. The "variable index" can be 0- or 1-based, and you need to handle indexes of 10 or higher.

For output, you can choose five consistent values to represent each of the five categories.

Standard rules apply. The shortest code in bytes wins.

Test cases

length, "body" (lambda term it represents) => answer

1, "1" (\a -> a) => Ordered
2, "1 2" (\a b -> a b) => Ordered
2, "2 1" (\a b -> b a) => Linear
2, "1" (\a b -> a) => Affine
2, "2 (1 2)" (\a b -> b (a b)) => Relevant
2, "1 1" (\a b -> a a) => None
3, "1 3 (2 3)" (\a b c -> a c (b c)) => Relevant
4, "1 3 (2 3)" (\a b c d -> a c (b c)) => None
10, "1 (2 (3 4) 5) 6 7 8 (9 10)" => Ordered
10, "5 (2 (6 10) 1) 3 7 8 (9 4)" => Linear
10, "5 (2 (6 10) 1) (9 4)" => Affine
10, "1 5 (2 (3 6 10) 1) 3 7 8 (10 9 4)" => Relevant
10, "1 (2 (4 10) 1) 5 (9 4)" => None


I'm a lizard, cut here!

• I think you mean n≥2 – xnor Jul 21 at 5:05
• @xnor sure thanks – golden_bat Jul 21 at 5:11

How effective is compression?

Vyxal has a very simple format for compressed integers: a base-255-encoded string of characters wrapped in «.

With base 255, the number to be compressed needs to be 10000 or greater for the compression to have an advantage against ordinary numbers, as with 1 character, you can represent at most 3-digit numbers (up to 254), which ties with 1 + 2 (for the «) = 3 bytes; with 2 you can represent up to 65024 in 4 bytes, beating 5 for n ≥ 10000.

But what if it was another base?

If it were base 99, it would take 3 bytes, since you can only express up to 9800 with 2, which isn't any better than expressing the number. But with 3, you can reach 970299, which has 6 digits

Your challenge is to take a positive integer $$\b\$$ 11 or greater, and find the smallest number $$\n\$$ such that $$\log_b(10^n) + 2 < n\$$. You may output $$\10^n\$$ instead.

This is , shortest wins!

Testcases coming soon.

• Be sure to include the testcases for n=100 and n=1000. The correct answer is floor(1+2/(1-1/log10(n))), but the wrong answer ceil(2/(1-1/log10(n))) gives identical results for all other n. (The correct answer can be also wrong due to floating-point imprecision. Is this allowed?) – Bubbler Jul 29 at 7:45
• @Bubbler Ok, will do. Shouldn't be wrong as it's taking a single logarithm. – A username Jul 29 at 7:56
• Straightforward Python fails because of 1/3, not single logarithm btw – Bubbler Jul 29 at 8:13

Bijection between N and at-most-n-ary trees code-golfopen-ended-functionmath

Background

At-most-n-ary trees are rooted trees where each internal node has between 1 and n children (inclusive). Two trees are considered identical only if the shapes exactly match without re-ordering each node's children. In other words, the left-to-right order of children matters.

For example, the following is an example of an at-most-ternary tree (each node is marked with its out-degree, the leaves being zeros):

    2
/ \
1   2
|  / \
3  0 1
/|\   |
0 0 0  0


Related OEIS sequences: A006318 is the number of at-most-binary trees having n internal nodes, and A107708 is for at-most-ternary trees.

Challenge

Write a function or program that, given a positive integer n (1st input), maps a natural number (2nd input) to a unique at-most-n-ary tree. It must be a bijection; every tree must have a unique natural number that maps to the tree. Only the code going from a number to a tree is considered for scoring, but it is recommended to provide the opposite side to demonstrate that it is indeed a bijection.

The output format for the tree is flexible (nested arrays, string/flat array representations including parentheses or prefix notation). You can also choose the "natural number" to start at 0 or 1.

Standard rules apply. The shortest code in bytes wins.

Train A Single Perceptron

You must write a program that will train a perceptron to simulate the things described in the test cases section of this question.

What is a perceptron and how to train it

Note: This description is slightly different. Normally, the output is 1 if the dot product is greater than or equal to 0. However, it is easier if the number the dot product must be greater than 1 instead of 0, so I've changed it to that in my description.

A perceptron takes inputs and returns 1 if the dot product of the inputs and its list of weights is greater than or equal to 1 and it returns 0 otherwise. To take the dot product, multiply the elements of the list and take the sum. Example: dot product of [0,2] and [8,3] is 0+6, which equals 6. Your job is to return the list of weights that will make the perceptron return the correct outputs for a list of inputs 100% of the time.

https://towardsdatascience.com/perceptron-learning-algorithm-d5db0deab975

Inputs

The program should take as input training inputs and training labels. Each list of inputs corresponds to exactly one output. This data must be used to train the perceptron.

Outputs

The program should output the final list of weights as integers. The dot product of these weights and any valid input to the perceptron should be the correct output of the perceptron 100% of the time.

Training

How you train the perceptron is up to you. To train a perceptron to simulate an AND gate, your program should take training inputs and the correct output for each list of inputs. In the case of the AND gate, your program would take [[0,0],[0,1],[1,0],[1,1]] as the list of training inputs and [0,0,0,1] as the list of what the neuron should output given each input. The program should then output a list of weights, which will output the correct output when used in a perceptron.

Test Cases

1. AND gate:
• Input List: [[0,0],[0,1],[1,0],[1,1]]
• Correct Outputs: [0,0,0,1]
• Your program should output a list of two weights that will solve the problem of behaving like an AND gate when used in a perceptron.
2. Only outputs 1 if the third input is 1:
• Input List: [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
• Correct Outputs: [0,1,0,1,0,1,0,1]
3. OR gate:
• Input List: [[0,0],[0,1],[1,0],[1,1]]
• Correct Inputs: [0,1,1,1]
4. Make up your own test case, and try to make it interesting!

Scoring

This is code golf, so the shortest program in bytes wins.

New contributor
Joseph Walker is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Could you maybe add a note that this task is to find a line ($w \cdot x=1$) that linearly separates the two classes? That might make the challenge more accessible to people unfamiliar with perceptrons. As a side note, the decision are of linear perceptrons can be visualized quite nicely: desmos.com/calculator/d2nryjmw2t – ovs 3 hours ago
• I guess you changed the threshold to $1$ to avoid the bias? I'm not quite sure this works because now the origin $(0,0)$ is always classified as $w\cdot 0=0$. I think just going with the usual definition should be fine. – ovs 3 hours ago

Find Maximum number of 4+ letter words from Scabble Tiles

The challenge is to find the most words with 4 or more letters you can make with one set of scrabble tiles.

The tile distribution is as follows:

2 Blank Tiles
A 9  N 6    +====+===========+
B 2  O 8    | 01 | K J X Q Z |
C 2  P 2    | 02 | B C M P F |
D 4  Q 1    | 02 | H V W Y * |
E 12 R 6    | 03 | G         |
F 2  S 4    | 04 | L S U D   |
G 3  T 6    | 06 | N R T     |
H 2  U 4    | 08 | O         |
I 9  V 2    | 09 | A I       |
J 1  W 2    | 12 | E         |
K 1  X 1    +====+===========+
L 4  Y 2
M 2  Z 1


Valid words are any words that are 4+ that are available in this file, the official scrabble dictionary.

Tiles cannot be used twice. This means you can only have 1 word with a K, J, X, Q, and/or Z unless you use a blank tile to represent one of these letters.

I'm not sure how I'd do scoring on this. I want shorter code to score better, but I don't want a short piece of code that finds a lot less words to score better than a longer piece that finds many more words.

• Meh. I don't like dependency on external files; are we allowed to load it, or even embed it into the source code? – John Dvorak Dec 17 '13 at 20:00
• as for finding more vs. shorter code, you could demand all words be found – John Dvorak Dec 17 '13 at 20:19
• @JanDvorak Any way to use it. It's a text version of the official scrabble dictionary, it seemed to be the most fitting word list for the task. "All words being found" might be hard, considering there are probably many combinations of words that would deplete all the tiles. It's a maximum of 25 words, (25 words, 4 letters each, 100 tiles), but I don't know if it's possible to use all tiles with just 4 letter words. After so many words, you might not have enough tiles to make an actual word, which means you'd either have to go back or accept that you're not using all the tiles. – Rob Dec 17 '13 at 20:23
• As currently described, this is a no-input task, which means that the answer can be precomputed and then the program only needs to decompress it. Consider rewriting it to take input (either of the word list or of the tiles available). – Peter Taylor Dec 18 '13 at 8:01
• I suggest taking a list of tiles as input, loading the list of words from a predefined file and requiring all combinations / best combination to be found. Of course, if the input is the full list of tiles, the computation is going to take ages. I might allow preprocessing the word list outside the program itself (up to a certain point; a linearithmic growth?) – John Dvorak Dec 18 '13 at 8:32
• I suggest modifying this so that input is a list of tiles, limited to a full rack or less (therefore 4-7 tiles, since our minimum word length is 4). Input should be assumed to be valid based on the standard set of tiles (e.g.: it wont' have something like 3 J's or 4 G's). This would have some practical use for a player in a scrabble game to figure out their next move (though it does not take into account tiles available to them which are already on the board). – Iszi Dec 18 '13 at 21:14
• Alternative mode: Input is a list of tiles, maximum 96 (so that at least 4 are remaining in the set). Output only includes words (minimum 4 letters) which can be created without those tiles. This would be interesting as it provides words that may yet be created (though, again, not taking into account usable tiles on the board) at a given point in the game. – Iszi Dec 18 '13 at 21:15
• Output needs to be decided as either a list of all possible words, or only the highest-scoring word(s). Another enhancement may be to require that the list be sorted descending in order of score (if output is all words), then ascending alphabetically. There's no reason to take each program's output into account for scoring. Since everyone is expected to use the same dictionary, all programs' outputs should be identical (except perhaps in sorting, if that's left out of the spec). So, this should be Code Golf. – Iszi Dec 18 '13 at 21:15
• It's also worth noting that, as currently written, the task could just be to filter the given dictionary down to words which have 4 or more letters. By its very nature, the Scrabble dictionary should already exclude any words that cannot be made with a Scrabble set. – Iszi Dec 18 '13 at 21:18
• @Iszi it's not "what are all the words you can make", it's "what are all the words you can make, where every letter used depletes a tile". There's a max of 25 words if you can use all 100 tiles. – Rob Dec 19 '13 at 16:40
• I think I misunderstood the problem, then. I thought it was "all the words possible using a set of tiles" not "all the words possible, using only one set of tiles". Still, my point about code golf remains. There is an absolute maximum to the number of words (each with 4 or more letters) you can make with a single Scrabble set, and a finite number of permutations which can be used to hit that maximum. Every program written with this goal should end up with the same (or nominally similar) output. – Iszi Dec 19 '13 at 16:56

Known Issues:

• Some rules seem a bit unclear to some users.
• Clarification may be needed on what is needed to qualify for the "win percentage" bonus.
• Win percentage bonus may not be enough to be a real incentive. (This may just depend on the language or implementation.)
• Perhaps the win percentage bonus should be eliminated entirely, or maybe it should just be made a mandatory part of the spec.
• It's been suggested to use a simple 1-9 numbering system for the board positions, instead of any sort of X,Y coordinates.
• May want to allow some flexibility on the input format. (i.e.: Input must still specify the sequence of moves thus far, using whatever addressing scheme is specified in the spec, but leave the delimiters - or lack thereof - up to the developer.)
• Exactly what is expected of the program, such as how it can figure out whose turn it is or what the output should be, seems to need some clarification.
• Some test cases should probably be added.
• Clarification may be needed on the matter of what parts of the game we can assume have followed the guide already.
• Some flaws exist in the chart. (Two already mentioned in comments on the original post.) These should be identified and addressed so that proper expectations for those conditions are clearly set.
• Original post said we would not have to account for null input (i.e.: X asking what their first move should be) but this might be a good enhancement to add.

I personally think this is a great challenge. So far, I've had a very hard time finding a lot of room for optimization and got up to probably 400 characters in PowerShell before I gave up (not even half-way through the chart yet) due to some of the above issues. I'd really like to see what some more serious golfers could do with this, once the spec is properly hammered out.

Overview

This is the XKCD tic-tac-toe cheetsheet:

It's rather big, I know. But it's also your most valuable resource in your challenge.

The challenge

Create a program (in your language of choice) that uses the Optimal Move Cheatsheet (henceforth OMC) to output the optimal move when given a sequence of moves.

The input

Your program will be fed a series of moves in the following fashion:

A3 A2 B2 C2 ...


Where the first combination is always X, the second O, and so on. The letter is the Y coordinate (A-C, A at the top) and the number is the X coordinate (1-3, 1 at the left).

You may assume that the given combination is following the OMC's suggestion for each move at least for the player asking for a recommendation. You can also assume that the input will never be null (at least one move has been made). You must:

1. Figure out whether the next move is for X or O (you don't need to output this)
2. Use the OMC to decide the next move
3. Print the next move in the standard format A3

Optional:

You may also include the player's chance of winning (as a percentage) for 50 character discount on your score.

• I think a 1-9 system would be easier than any XY system, but not by too much. The biggest issue I think is that if you go by the chart (rather than formulating your own algorithm that plays the same way) you have a ton of data to enter (there are several hundred squares in the two charts). Perhaps limit the input to only sequences starting A1 B2 (or 1 5 if you use telephone keypad numbering)? That's the center square in the X chart and the top left square in the O chart. – Blckknght Dec 23 '13 at 5:14
• @Blckknght Limiting the scope of the challenge makes it less interesting. Part of the challenge (if not the entire challenge) here is to find ways to shortcut the flow while still putting out accurate results. As for the 1-9 system, the simplification may be relatively trivial but it does help clear out some otherwise unneeded bloat since everyone will probably build in some conversion to a 1-9 system anyway to shorten the code. It also enables some other shortcuts where the same move suggestion applies to multiple situations which are mathematically related. – Iszi Dec 23 '13 at 19:47
• My point is that the chart data so dominates the code size that winning answers will pretty much have to ignore the data in the chart and use an AI. So the challenge becomes "write a Tic-Tac-Toe AI that plays exactly like this chart", which seems less interesting to me than "use (part of) this chart to make an AI with trivial code". I already have working code for the problem and bonus in about 200 non-golfed characters of Python, but it will require many 1000s of characters of data, even if I exploit some symmetries. Even if I was willing to type all that data, an AI will beat it, I'm sure. – Blckknght Dec 23 '13 at 20:55
• @Blckknght I'm pretty sure even a fairly straightforward implementation of the chart can be fit within about 5,000 characters - especially in a proper golfing language. IRRC, I'd finished the X portion of the chart in about 400 characters with PowerShell before I gave up on my first go at it. Even then, there was still plenty of room for optimization, and that's in a language which is far from optimal for golfing. Certainly, it's nice when you can bang out a quick answer in 15 minutes. But not every challenge has to fit in 500 characters or less. – Iszi Dec 23 '13 at 21:12

Test for Irreducible Complexity (Check for Redundant Characters)

I may need some additional help coming up with the full spec for this competition. As of right now, this is just a concept.

Many interesting questions, such as the "42" question in this sandbox, involve finding the longest program which is not reducible. This means that no set of characters can be removed and still allow the program to function as desired.

The basic idea is that your program will test a Base Program to make sure that it contains no redundant characters. The input will consist of:

• Expected Output

Your program will simply evaluate all possible subsequences of the Base Program and verify that none of them give the Expected Output.

This challenge actually has a utility value to several other challenges. For example, it verifies the results of a "longest non-reducible"-type challenge. In addition, it could make sure that a golfed solution cannot be golfed further.

I assume that the winning criteria will be fastest program, as cycling through all the possibilities takes a long time.

Problems

A sequence of length N has 2^N subsequences. Even if each evaluation is done very quickly, it might be unfeasible to test any program with more than 20 or so characters in a reasonable amount of time.

• Problem: some subsequences of legitimate answers may be pretty dangerous to the environment. You don't want to eval just everything. – John Dvorak Dec 23 '13 at 16:59
• @JanDvorak Yes that actually is a serious problem. To what extent is it possible to fix that? – PhiNotPi Dec 23 '13 at 17:04
• Forbidding any program with dangerous subsequences? :-) – John Dvorak Dec 23 '13 at 17:05
• A more reasonable (but very difficult) solution would be the requirement to implement a sandbox. – John Dvorak Dec 23 '13 at 17:07
• Even without dangerous behavior, the halting problem will be an issue: it's hard to tell whether a shortened program will terminate at all, especially for every conceivable input. – MvG Jan 7 '14 at 23:49
• Are you sure this is possible? The problem of testing if two functions/programs/turing-complete things are equivalent is undecidable - I'm fairly sure it's reasonable easy to constract a brainfuck program that you can't tell if you can remove even a single character. – Command Master May 16 at 4:44
• Extending on my previous comment - Let's assume you have a solution to this. Take a brainfuck program you want to test if halts. Let it reduce it, now you have an equivalent irreducible program. Add +. in the end of it, and then try to reduce it again. If the code never halts, that +. is reducible and when you'll run it again it will be removed. Otherwise it's important, so it will be kept. The halting problem is undecidable, therefor this is undecidable. – Command Master May 16 at 4:54
• You can also get its undecidablility from that in Unary it will tell you if a given program is minimal, which is known to be undecidable as well – Command Master May 16 at 5:25

Popularity Contest: Implementation of a Hash Table

Create a class in some OOP language for a hash table that supports getting, setting, and removing values. You can't use the built in hash table/dictionary/map implementation. Highest votes in one week wins.

A key is any valid string. A value is any valid string, number, or boolean.

Example functionality:

hash.set("key","value");
hash.get("key"); // returns "value"
hash.set("key", 1234);
hash.get("key"); // returns 1234
hash.set("key2",hash.get("key"));
hash.get("key2"); // returns 1234
hash.delete("key");
hash.get("key"); // returns null/undefined/none/etc. or throws an error
hash.get("key2"); // still returns 1234


Definition of a hash table (from Wikipedia):

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

The hash table cannot be simply an array that is searched in linear time. It must be an actual hash table that uses a hash function to map the keys to the value.

• Popularity contest and shortest don't mix. That aside, the spec is too vague. What is a "value"? What assumptions can be made about hashcodes? If the language makes all types nullable, should null be permitted as a key? What should the type be in languages which have co- and contravariance? And for that matter, what qualifies as a "hash table", bearing in mind that people will try to exploit any loophole? – Peter Taylor Jan 2 '14 at 23:16
• @PeterTaylor Thank you for the feedback! Please see my edits, and let me know what you think. Could you meant about co/contravaraince? I looked at the wikipedia article about it but I'm not really sure how that has anything to do with this question. – hkk Jan 2 '14 at 23:37
• I think it's still vulnerable to the loophole of "I have a hashtable with one bucket" (i.e. it's really a list of (key, value) pairs which I traverse in linear time). The thing about variance is to do with static typing of the elements of the map. E.g. in Java Map<String, Integer>'s get method has signature public Integer get(Object); in C#, a Dictionary<string, int>'s Get method has signature public int Get(string). The edited version makes it clear enough that the hashtable isn't expected to be genericised. – Peter Taylor Jan 3 '14 at 0:08

Wordlist detector

You are to write a program which, given a list of words, constructs a regular expression to match all these words but nothing else. Both your program and the constructed regular expressions are to be as short as possible.

Input and Output

Input comes on standard input and consists of one line giving n, the total number of words, followed by n lines with one word each. The number of words will be less than 1000, the length of each word less than 30. Words will consist only of lower case ASCII letters, i.e. a-z. You may choose to ignore the first line and use EOF instead to end the list.

Output shall be written to standard output. It consists of a single line, giving a POSIX extended regular expression to match these words and no others. Since input for this regex is not restricted to letters only, elements like . or [^…] won't make too much sense, which limits the language in a natural way. You may choose whether you want to terminate the line with a newline or not. Programs may choose to print multiple lines of output, in which case only the last one will be used for scoring. So you might print intermediate results and continue searching for improvements.

Test cases

Each submission may be accompanied by one regular expression. When scoring the submissions, I'll use this regular expression to reconstruct a word list from it. The code to do this reconstruction can be found at the end of this post. The reconstructed word list must fit the input specification above in terms of word count and length. It would be nice if your own program would be able to regenerate that regular expression from the word list, but that is not a strict requirement. But please don't paste bogus programs just to submit a challenging regular expression, though.

These test cases will be collected and fed to all programs for scoring.

Scoring

The final score of each program will be the program size plus the size of all its generated regular expressions for the inputs collected from submitted answers, including the example from this question. So short code which produces too long results might get beaten by longer code which generates shorter expressions.

Does this still qualify as ?

Submissions which generate an incorrect regular expression for one of the test cases will be disqualified, as will those which don't terminate in the allotted time. You can use the input reconstruction program below to check whether a produced regular expression does encode the correct word list.

Requirements

All submissions are welcome, but in order to include your submission in the tournament, it must be executable with reasonable effort on my Linux machine. It shouldn't depend on any exotic libraries, or any specialized ones which take too much work away from your own program. It must operate in reasonable time, say no more than five minutes per input. Your output must be reproducible, so if you use randomization at some point, please seed the randomizer, and please don't terminate an improove loop by a timer measuring execution time or some such.

Tournament times

I'll run the first major tournament two weeks after posting this question. I'll include a table of the results in this question. I'll try to run tournaments repeatedly as late submissions arrive, but I'll not promise any regular schedule.

Example

An very simple example application would be in Python 3 (53 chars):

print('|'.join(input() for i in range(int(input()))))


And here is a test case which could be posted along with the program, although this program obviously doesn't generate exactly this concise output:

bann?ana|ap(fel|ple)|s[ou]n|[hs](a|ou)nd


The expansion of that expression could be turned into the following example input, which need not be posted as part of an answer since it can be deduced from the regular expression:

10
banana
bannana
apfel
apple
son
sun
hand
hound
sand
sound


Regex expander program

And here is a program to turn regular expressions into word lists, again written in Python 3.

#!/bin/env python3
concat = set(('',))
altin = set(('',))
altout = set()
prev = None
stack = []
regex = iter(input())
for ch in regex:
if ch == '(':
stack.append((concat, altin, altout))
altin = concat
altout = set()
prev = None
elif ch == ')':
concat.update(altout)
prev, altin, altout = stack.pop()
elif ch == '|':
altout.update(concat)
concat = altin
elif ch == '[':
ch = regex.__next__()
cls = []
while ch != ']':
if ch == '-':
crange = range(ord(cls[-1]), ord(regex.__next__()) + 1)
cls.extend(map(chr, crange))
else:
cls.append(ch)
ch = regex.__next__()
prev = concat
concat = set(w + c for w in prev for c in cls)
elif ch == '?':
concat.update(prev)
prev = None
elif ch >= 'a' and ch <= 'z':
prev = concat
concat = set(w + ch for w in prev)
else:
raise Exception("Illegal input")
if stack:
raise Exception("Unclosed group")
concat.update(altout)
words = sorted(concat)
print(len(words))
print('\n'.join(words))
`

This is restricted to the part of regular expression syntax which I expect for this answer. If you have good reason to use something I did not consider, feel free to do so although I will likely have to update this code to cope with it. If you find a bug, please let me know.

• This is just Meta regex golf under the constraint that the two lists between them cover all possible words. Given that some people are tackling that existing question on that basis, this would qualify for closing as a duplicate. – Peter Taylor Jan 8 '14 at 8:45