556
\$\begingroup\$

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

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

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

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

Discussion

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

  • Parts of the challenge you found unclear
  • Comments addressing specific points mentioned in the proposal
  • Problems that could make the challenge uninteresting or unfit for the site

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

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

4046 Answers 4046

1
72 73
74
75 76
135
1
\$\begingroup\$

Gitify a complete graph

Give a natural number n = 1, 2, ..., create a git repository that represents a complete graph of size n.

Details

  • A complete graph is a graph, where every node is connected to every other node (except for itself).
  • The graph is represented as follows: Each commit is the equivalent of one node. And edge is represented by a parent/child relationship of two commits, that is, one commit must have the other as a parent.
  • You must create a local repository. You can use git itself or other libraries, but you can also create it by writing the raw files. You must include all languages, tools or non-standard libraries of your language/s of choice you use in the title.
  • The repo created must be readable with the current git version 2.37.x, that is when you execute git log --graph --oneline after you created the repo the graph should be visible (usually probably not in a very nice layout if it is a complete graph).

Example Outputs

If we use bash with git installed, can execute following commands to get the outputs for n = 1, 2, 3. Note that these programs are not solutions to the challenge themselves (they don't take n as an input) but merely generate a valid output repository.

Graph Size Bash
1 git init;git commit --allow-empty -m x
2 git init;git commit --allow-empty -m x;git commit --allow-empty -m x
3 git init;git commit --allow-empty -m x;git commit --allow-empty -m x;git checkout -b first HEAD^;git merge master --no-ff -m x

META:

I've decided to simplify the challenge to just create a complete graph instead of arbitrary graphs.

Given a undirected connected graph, create a git repository with a commit graph that is isomorphic to the input graph.

  • This is just a rough idea: I first should think about what kind of graphs can actually be represented in a git repository. (the input format could be flexible: take an adjacency matrix or e.g. a list of edges or maybe some native graph structure)
  • another idea would be following: given some \$n =1,2,3,\ldots\$ create complete graph of \$n\$ nodes
\$\endgroup\$
2
  • \$\begingroup\$ Should adjecency read adjacency? \$\endgroup\$ Jun 19, 2019 at 22:38
  • \$\begingroup\$ @JonathanFrech yes, thanks a lot! \$\endgroup\$
    – flawr
    Jun 20, 2019 at 12:33
1
\$\begingroup\$

Verify the diamond property

A polytope is a generalization of the concepts of polygons and polyhedra to higher dimensional space.

Now higher dimensional space is a little hard to picture so we have a variety of tools for thinking about and working with polytopes to ease this issue.

One of these tools is a Hasse diagram.1 The Hasse diagram doesn't preserve all information about the polytope, it is concerned with which elements of the polytope are incident on each other.

The elements of the polytope are the polytopes that make up the polytope, so for example in a polyhedron (3d) the elements are its faces (2d), edges (1d), vertices (0d), the polyhedron itself, and the empty set2.

An element is incident on another if it is a subset of that element. So for example, all the faces of a polyhedron are incident on the polyhedron itself. No two faces are incident on each other even though they overlap at an edge.

There are a couple of properties we can observe.

  • Every element must be incident on the polytope itself.
  • The empty set is incident on every other element.
  • Every element is incident on itself.
  • Elements are only incident on other elements which are of higher dimension.
  • Incidence is transitive: If \$A\$ is incident on \$B\$ and \$B\$ is incident on \$C\$, then \$A\$ is incident on \$C\$.

A Hasse diagram draws the elements of the polytope as a graph; connecting incident elements. However we leverage these facts above to simplify the graphs. For one we organize the elements in rows by dimension. All the vertices go in one row, all the edges go in another. At the top we have the polytope itself, and at the bottom we have the empty set. We don't draw connections from an element to itself. Since all elements are incident on themselves there is no point. We also don't draw connections between elements whose dimensions differ by more than 1, since these connections can always be derived from the transitive property.

Example image

Taken from wikimedia commons image by David Eppstein and Steelpillow. This image has been released into the public domain by its authors.

TODO

I started writing this challenge, and it turned out a lot more complex than I thought because I have to define what an abstract polytope is. I don't have time right now for this and I will come back later.


1: Hasse diagrams are used for many things not just polytopes, but we are going to skip over that because here we are interested in polytopes. 2: Thinking of the empty set as an element can be a little bit weird, but it does make the math simpler so we do it.

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

Next Special String

\$\endgroup\$
4
  • \$\begingroup\$ You need to specify what you mean by "so you need to have some fast enough solution too". You might want to use restricted-time. You should also format the test cases to be easier to copy \$\endgroup\$ Jul 19 at 8:39
  • \$\begingroup\$ Is there any particular reason "just to make it even more interesting" is in LaTeX? \$\endgroup\$ Jul 19 at 8:45
  • \$\begingroup\$ @CommandMaster Done, Thank you. No, nothing in particular \$\endgroup\$
    – cheems
    Jul 19 at 10:46
  • \$\begingroup\$ 30 seconds isn't objective enough, you should specify where it is run. TIO might be good, or perhaps you just want restricted-complexity (I'd say 30 seconds with \$ N \leq 300 \$ is approximately \$ O(n^{3.5}) \$) \$\endgroup\$ Jul 20 at 11:38
1
\$\begingroup\$

Find all matches for the digit pattern

In an older challenge, you were tasked with finding numbers which, in base-ten, matched this specific digit pattern:

(n)(x)(n+1)(x)(n+2)(x)(n+3) etc...

Meaning any number between 4 and 18 digits long such that the digits could be considered as a string of increasing single digits interlaced with (at most) a constant single digit number.

For example, 19293949 would fit the pattern, with n being 1 and x being 9.

In this challenge, instead of deciding whether a given number fits one fixed pattern, you will be given a pattern as input, and are tasked with outputting the sequence of numbers which match the pattern.

Patterns

This section is a definition of what the patterns are and what they represent. A format similar to the one used in the original post will be used for these examples. More clarification on I/O rules will come afterward.

A pattern consists of one or more clearly delimited tokens, each matching a single base-ten digit.

(token)(token)(token)

Tokens can either be constants, accumulators, or a loop.

Constants are each marked with a single token, and there can be up to ten different constants, as each distinct constant represents a distinct digit from each other constant. Here it is represented as a single character from a to j in parenthesis ()

(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)

This pattern, for example, could match the number 1234567890, but not the number 1111111111.

Important note: Numbers cannot have leading 0s, so the pattern would not match 0123456789.

(a)(a)(a)

This pattern would match 111, 222, etc. all the way up to 999. It would not match 000, as it contains leading 0s, and it would not match 123, as all of the digits marked with the same constant must be the same.

Accumulators are marked with a single fixed symbol. The first instance of an accumulator represents any digit from 0 to 9, and each successive instance represents a digit that is one more than the previous instance. Here it is represented as (n+)

(n+)(n+)(n+)(n+)(n+)

For example, this pattern matches 12345, 23456, 34567, 45678, and 56789. Combining constants and accumulators is allowed, giving us access to patterns similar to that of the original challenge:

(a)(n+)(a)(n+)(b)(n+)(b)

Constants can't match the same digits as other constants, but they are allowed to match the same digits as accumulators. This pattern matches, for example, 9192838, but it also matches 1112333.

This isn't enough to support the pattern given in the original problem, so finally we introduce the loop token. This token can only appear at the end of the pattern, or not at all. Here it is represented as ...

(a)(b)(c)(n+)(n+)...

A pattern with the loop token matches all numbers that the pattern would if it did not have the loop, as well as all numbers matched by the pattern repeated twice, as well as three times, as well as four times etc. This pattern matches 78901, but it also matches 7890178923, as well as 789017892378945, etc. all the way up to 7890178923789457896778989.

(a)(a)(a)...

Beware: A pattern with no accumulators but having constants and a loop matches infinitely many numbers. This one matches 111, 111111, 111111111, etc.

Rules

Input can be given in any reasonable format, so long as each token type is clearly distinct, clearly delimited, and consistent. This includes lists of characters, lists of strings, lists of numbers, a single string, curried arguments, etc.

The loop token in particular can be taken anywhere in the input convenient, including separate from all of the other tokens. e.g. you could take it as a separate boolean input, or a command line argument, or at the beginning of the string instead, etc.

Standard rules apply, so you can either output all matches, or take another number n as input and return the nth matching number, etc. Whatever the rules in the tag allow is fine with me.

You may assume any/all of the following:

  • All patterns given have at least a single valid match.
  • When given a pattern with finitely many matches, you will not be given an input asking you to exceed that amount of matches (so you wont be asked to generate the 11th number that matches (a)).
  • Constant variable names first appear in some specific order. So you could, for example, accept (a)(b)(c)(a)(c) but ignore (x)(y)(z) and (c)(b)(a). So long as at least one equivalent form is allowed, it's fine. I doubt this helps anyone, just covering my bases.
  • Not strictly an assumption, but you are allowed to ignore 0 as an output number or assume no input will ask for it, as it technically breaks the "no leading zeros" rule. Edge cases wouldn't add much to the challenge :P

Finally, this is , so shortest code in bytes wins.

Examples

Examples will be given as a pattern, followed by a natural n, followed by the nth matching number (including 0), 0 indexed, all delimited with |.

Still work in progress, the ?s are temporary,

(a)          |   1 | 1
(a)          |   9 | 9
(a)(b)(c)    |   0 | 102
(a)(b)(c)    |   1 | 103
(a)(b)(c)    |   7 | 109
(a)(b)(c)    |   8 | 120
(a)(b)(c)    |   9 | 123
(a)(b)(c)    |   ? | 987
(a)(b)(c)... |   ? | 987
(a)(b)(c)... | ?+1 | 102102
(n+)         |   1 | 1
(n+)         |   9 | 9
(n+)...      |   1 | 1
(n+)...      |   9 | 9
(n+)...      |  10 | 12
(n+)...      |  11 | 23
(n+)...      |  17 | 89
(n+)...      |  18 | 123
(n+)...      |  19 | 234
(n+)...      |  24 | 789
(n+)...      |  25 | 1234
(n+)...      |  26 | 2345

Meta

Should I allow leading zeroes in interest of reducing edge cases?

\$\endgroup\$
7
  • \$\begingroup\$ Can you take the loop as a separate boolean, instead of as a token at the end of the pattern? \$\endgroup\$ Jul 18 at 3:56
  • \$\begingroup\$ @CommandMaster sure thing, i'll clarify \$\endgroup\$ Jul 18 at 4:28
  • \$\begingroup\$ For examples format you can use just pattern | beginning of sequence or pattern | n | nth number in sequence (with several ns for each pattern). The second one may be better for sequences which are tricky for big ns. \$\endgroup\$
    – pajonk
    Jul 18 at 8:02
  • 1
    \$\begingroup\$ @thejonymyster ofc you can use other delimiters like \t and justify to make it more human-readable. \$\endgroup\$
    – pajonk
    Jul 19 at 7:27
  • \$\begingroup\$ @pajonk right thats a good idea, i was planning on justifying as well but i was rushed away from my computer ~_~; i feel bad about boosting this post to the top over and over so ill get it next edit when i add a bunch of test cases lol \$\endgroup\$ Jul 19 at 12:36
  • 1
    \$\begingroup\$ Do the matches have to be in order? If so, do they have to be in numerical order, or can they be in lexographic order (like 10 being after 1)? \$\endgroup\$
    – Steffan
    Jul 22 at 1:55
  • \$\begingroup\$ @Steffan oh actually good point, i guess the order doesnt matter so much. that makes writing examples much more difficult though >_< will have to rephrase the rules next edit, ty \$\endgroup\$ Jul 22 at 2:52
1
\$\begingroup\$

Cube calendar numbers

Two-cube calendar

Credit: Marco Verch CC BY 2.0

A two-cube calendar, as shown in the picture, uses two cubes with digits painted on the faces to display the date. For dates in the range 1-9, a leading zero is used ("01", "02", ..., "09").

Now, if you do the math, you might come to the conclusion that these calendars should be impossible. After all, the numbers "0","1" and "2" must appear on both cubes, since they can appear on the tens place and the other cube has only six faces. This means that there are only six faces remaining for the other seven numbers.

Two-cube calendars use a trick where the face with a "6" can be rotated upside down to look like a "9". For example, one cube may have faces "012345" and the other one "012678" where the "6" can also be a nine. For the purposes of this challenge these kind of font-dependent tricks are banned.

With these restrictions we can only display the numbers from 0 to 21 for a total of 22 numbers. We can display some other numbers too, but we are only interested in the longest possible sequence of numbers displayable (no gaps), starting from 0.

If, instead of using base 10, we would have used base 6, we could display 0-35 for a total of 36 numbers.

If, instead of using cubes, we would have used octahedrons (8 faces), we could display 0-65 (using base 10).

And finally, with three cubes we can get 0-76 for a total of 77 numbers (using base 10).

The maximal amount of numbers we can get in the initial range is called the cube calendar number. It depends on the number of faces, on the number of dice ("cubes") and on the base of the numbers.

Task

Given a base b, the number of faces f and the number of dice d, return the cube calendar number for those parameters.

b, f and d are natural numbers guranteed to satify:

\$b\ge 2\$

\$b\ge f \ge 1\$

\$d\ge 1\$

Test cases

todo

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

Move n, out n

Your task is to write a code, where if you move n adjacent characters, the program has to output n.
The code has to work for all integer n's \$0 \le n < \text{code-size}\$
The winning-criteria is

Rules

  • Code length has to be greater than 1
  • You can choose which substring to move for each n
  • Code size is not measured by bytes (ofc), but by the number of characters

Example Program

abcd

abcd -> 0
bcad -> 1 (Move a)
acdb -> 2 (Move cd)
bcda -> 3 (Move bcd)

\$\endgroup\$
3
  • \$\begingroup\$ Do we get to choose which substring gets moved and whither, for each n? Or do we have to make it work for every possible move?? \$\endgroup\$
    – pxeger
    Jul 24 at 15:49
  • \$\begingroup\$ @pxeger right I'll make it clear \$\endgroup\$
    – mathcat
    Jul 24 at 15:55
  • 1
    \$\begingroup\$ Could you detail what each program should output, supposing your code is abcd? \$\endgroup\$ Jul 24 at 16:09
1
\$\begingroup\$

Find The Average String

\$\endgroup\$
20
  • \$\begingroup\$ Tag: edit-distance \$\endgroup\$
    – Steffan
    Jul 28 at 23:49
  • \$\begingroup\$ string, ring can also be sring. The only other possibility for Hello and Ho is Heo. \$\endgroup\$
    – Steffan
    Jul 28 at 23:57
  • \$\begingroup\$ If there are multiple possibilities, can we output all of them? If so, can it contain duplicates? (I'm running a script for Seggan, Steffan to look for more possibilities - it's really slow.) \$\endgroup\$
    – Steffan
    Jul 29 at 0:02
  • \$\begingroup\$ Ok, it took like 10 mins to run, but here's the full list: ['Seffan', 'Sefgan', 'Segfan', 'Stefgan', 'Stegfan', 'Steggan'] \$\endgroup\$
    – Steffan
    Jul 29 at 0:11
  • \$\begingroup\$ @Steffan thanks \$\endgroup\$
    – Seggan
    Jul 29 at 1:05
  • \$\begingroup\$ you can remove "I hand-made these, so some might be wrong" sicne I checked them with Vyxal lol \$\endgroup\$
    – Steffan
    Jul 29 at 2:27
  • \$\begingroup\$ Why cannot I simply output the first input and do nothing? For example, for input Seggan, Steffan, Seggan have edit distance 0 to Seggan and 3 to Steffan which average is 1.5. \$\endgroup\$
    – tsh
    Jul 29 at 2:33
  • \$\begingroup\$ @tsh The rules state: "You may not output any of the inputs" \$\endgroup\$
    – Steffan
    Jul 29 at 3:26
  • \$\begingroup\$ @Steffan So, for input abc, abcd, should I output abce so it have average 1 instead of abc which have average 0.5? \$\endgroup\$
    – tsh
    Jul 29 at 5:03
  • \$\begingroup\$ How do we define Levenshtein distance with multi-case input? Is the distance between Ab and ab 0 or 1? I suggest sticking to upper- or lower-case. Suggested test case with no common letters. \$\endgroup\$
    – pajonk
    Jul 29 at 5:31
  • \$\begingroup\$ Will the outputs only contain characters in the inputs? This would simplify things a lot, and the current test cases imply that. \$\endgroup\$
    – Steffan
    Jul 29 at 15:52
  • \$\begingroup\$ @tsh Probably, the intended output would be abd with average 1, but waitnig for clarification. \$\endgroup\$
    – Steffan
    Jul 29 at 15:53
  • \$\begingroup\$ @pajonk there will be no inputs without common letters. Sure, I'll stick to lowercase \$\endgroup\$
    – Seggan
    Jul 29 at 15:57
  • 1
    \$\begingroup\$ I would suggest changing output a word with "lowest average distance" to two inputs to output a word with "lowest maximum distance" to two inputs and allow output one of input as-is. It may solve the confuse output for abc abcd, and keeping all current testcases valid. This will be different if two input have distance at least 4, for example abcdef, af -> [abcf abdf abef acdf acef adef] but not abf acf adf aef abcdf abcef abdef acdef. \$\endgroup\$
    – tsh
    Jul 30 at 6:42
  • 1
    \$\begingroup\$ From current specification, average of aaa and aaaa is... aa, aaaaa? it could be confuse to me. \$\endgroup\$
    – tsh
    Jul 30 at 8:48
1
\$\begingroup\$

Make a super fair number

An even distribution number is a number such that if you select any of it's digits at random the probability of it being any particular value (e.g. 0 or 6) is the same, \$\frac1{10}\$. A precise definition is given later on.

Here are a few examples:

  • \$\frac{137174210}{1111111111} =0.\overline{1234567890}\$ is an even distribution number.
  • \$2.3\$ is not an even distribution number since 7 of the digits 1456789 never appear and all but two of the digits are 0.
  • \$1.023456789\$ may look like it's an even distribution number, but for this challenge we count all the digits after the decimal point, including all the 0s. So nearly all the digits are 0, and the probability of selecting anything else is \$0\$.

Precisely speaking if we have a sequence of digits \$\{d_0^\infty\}\$ then the "probability" of a particular digit \$k\$ in that sequence is:

\$ \displaystyle P(\{d_0^\infty\},k) = \lim_{n\rightarrow\infty}\dfrac{\left|\{i\in[0\dots n], d_i=k\}\right|}{n} \$

That is if we take the prefixes of size \$n\$ and determine the probability that a digit selected uniformly from that prefix is \$k\$, then the overall probability is the limit as \$n\$ goes to infinity.

Thus an even distribution number is a number where all the probabilities for each \$k\$, converge and give \$\frac1{10}\$.

Now a super fair number is a number \$x\$ such that for any rational number \$r\$, \$x+r\$ is an even distribution number.

Task

Output a super fair number. Since super fair numbers are irrational you should output as an infinite sequence of digits. You can do this using any of the defaults.

This is so the goal is to minimize the size of your source code as measured in bytes.

\$\endgroup\$
1
  • \$\begingroup\$ I'm not sure if the super fair condition is equivalent to every slice with an arithmetic progression of digit positions being evenly distributed, but I think this alternate condition might be easier for solvers to prove correctness for. \$\endgroup\$
    – xnor
    Aug 5 at 11:38
1
\$\begingroup\$

Implement String Projection

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Do I understand correctly that it's simply: keep characters from first input that are in the second input? \$\endgroup\$
    – pajonk
    Aug 4 at 6:09
  • \$\begingroup\$ That's essentially what it outputs. \$\endgroup\$
    – bigyihsuan
    Aug 4 at 15:01
  • 2
    \$\begingroup\$ Why not state it in the challenge then? If you like, you may keep the formal definition, but I think it's just confusing. Also, what do you mean by if you have unicode support? Do we have to handle unicode or not? I suggest removing this test-case. \$\endgroup\$
    – pajonk
    Aug 4 at 17:37
  • 1
    \$\begingroup\$ I like the challenge, but I think that adding an informal description of the procedure (like pajonk's) is necessary. \$\endgroup\$ Aug 4 at 18:53
  • 1
    \$\begingroup\$ I suggest removing the formal definition of projection and the pseudocode. I don't think they help readers at all here. \$\endgroup\$
    – xnor
    Aug 5 at 10:11
1
\$\begingroup\$
\$\endgroup\$
0
1
\$\begingroup\$

Same number list shape?

Given two lists of positive integers, decide whether the two lists can be made equal by only repeated application of any/either of these two functions:

  • Multiply all numbers of one list by a positive integer constant
  • Add a positive integer constant to all numbers in one list

This is , so shortest code wins.

Extra spec:

  • You can assume lists will be at least three integers long.
  • Both lists input will be the same length.
  • Both lists will be given in strictly ascending order.
  • Standard I/O and rules apply.

Worked out example:

list a: 2 4 8
list b: 1 4 10

multiply elements of list a by 3

list a: 6 12 24
list b: 1 4  10

multiply elements of list b by 2

list a: 6 12 24
list b: 2 8  20

add 4 to elements of list b

list a: 6 12 24
list b: 6 12 24

done, return truthy

Shorter examples

1 1 1 1
3 3 3 3
true

5 10 11 14 16
2 12 14 20 24
true

10 100 1000 10000 100000
1  10  100  1000  10000
true

31   301  3001 30001 300001
1113 1131 1311 3111  21111
true

1 11 111 1111 11111
1 10 100 1000 10000
true

1 2 3 5 8  13
2 3 5 8 13 21
false

1 2 4 8 16
1 3 5 9 17
false

2 3 4 5
7 7 7 7
false

Meta

  • Is it a dupe of are they colinear? Methinks maybe but this only has strictly ascending inputs, slope guaranteed to be on (0,inf) exclusive, and arbitrarily many "points".

  • Better title? This was initially going to emphasize the fact that the allowed transforms don't alter the ratios of differences between numbers, but idk if it's relevant with this new phrasing

  • Ascending order? Is this assumption necessary/would the challenge be better without it maybe?

  • Any better falsy examples? I can't think of any other significant ones, probably will have to wait til post when people are all like "suggested test case:"

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Another way to think about this is "do these 2D points lie on a straight line with positive slope?", where the lists contain the respective x- and y-coordinates. \$\endgroup\$
    – xnor
    Aug 3 at 9:58
1
\$\begingroup\$

Longest N-Sum Sub-Array

Write a program or function which when given an array of non-negative integers and a number N, output the longest contiguous sub-sequence of said array whose sum adds up to N.

Constraints

  • If there are multiple such sub-sequences, output any of them or all of them (duplicates are OK).
  • You may output the starting and ending indices of the solution.
  • There will always be a solution, but it can be an empty list.
  • N ≥ 0.

This is , so shortest code in bytes wins.

\$\endgroup\$
1
  • \$\begingroup\$ Related \$\endgroup\$
    – c--
    Aug 8 at 18:26
1
\$\begingroup\$

When to give up and start again

Consider the following setup. An evil wizard has ten opaque boxes in front of him. Hidden from you, he chooses a random number of coins \$x \in \{1 \dots 10\}\$ and spreads them uniformly at random in the boxes. That is, there should be equal probability of assignment of coins to boxes from all possible assignments of \$x\$ coins to 10 boxes. If you can prove that in fact there are \$x=10\$ coins hidden in the boxes the wizard will grant you a wish.

In this game, you can look inside one box at a time chosen by you. When you do that, you can see how many coins there are in that box.

However the wizard, being evil, will never let you look in box 10. This might still be ok as you might find 10 coins in the other boxes and in fact the only way to be granted the wish is to have found all 10 coins in the first 9 boxes.

Unfortunately, the wizard does not let you play the game for free. It costs you one dollar to look in box 1, two dollars to look in box two, four in box three, doubling each time up to 256 dollars for box 9. Remember, you can never look in box 10.

The wizard has one last twist for you. At any point, you can choose to give up on this set of boxes and get him to start the whole process again (with a new random \$x\$). Of course, if you have looked in all the 9 boxes and you still have not found 10 coins you have no choice but to give up and start again. But you might want to give up earlier too. Sadly you never get any money back so your costs just carry on building.

Your goal is to devise a strategy that will get you the wish at the minimum expected cost. You should report your mean cost.

Testing

Once you have chosen your strategy, you should run it until you get the wish 10,000 times and report the mean cost. If two answers have the same strategy, the one posted first wins. If two strategies have similar mean costs you may need to test it 100,000 or even more times to tell the difference.

\$\endgroup\$
8
  • \$\begingroup\$ "You want to find out if there are 10 points that have been chosen". I'm confused about the meaning of this sentance \$\endgroup\$
    – mousetail
    Aug 9 at 7:55
  • \$\begingroup\$ @mousetail I meant if x=10. I'll rephrase. Thanks \$\endgroup\$
    – graffe
    Aug 9 at 8:29
  • 1
    \$\begingroup\$ What does "spreads them uniformly at random in the boxes" mean? "Spreads them uniformly" sounds like each box gets the same number of coins, but that obviously can't be true. From the rest of the challenge, it seems like he puts the coins in the boxes at random, such that each box contains 0 or more coins and each coin is in one of the boxes. (Also, I'm not sure how the boxes can be sealed if the wizard is putting coins in them--does he magically teleport the coins? Why can't the boxes just be normal unsealed boxes?) \$\endgroup\$
    – DLosc
    Aug 9 at 16:38
  • \$\begingroup\$ @DLosc Thank you. I changed sealed to opaque. I also changed the randomness wording. Is it better now? \$\endgroup\$
    – graffe
    Aug 9 at 16:56
  • \$\begingroup\$ Just to clarify, is this a KotH? Could you put tags at the top if you find any that are applicable? \$\endgroup\$
    – user
    Aug 11 at 21:11
  • \$\begingroup\$ @user Added the tag. From reading the guidance it seems code-challenge is right. \$\endgroup\$
    – graffe
    Aug 11 at 21:14
  • \$\begingroup\$ "so your costs just carry on building" Does that mean that when you open the first box of the second set, the cost is one greater than your position in the first set? Or does it reset to 1, but add on the the total from the first set? \$\endgroup\$
    – Xcali
    Aug 18 at 22:42
  • \$\begingroup\$ What's the winning criteria? Shortest code? Lowest average cost? If the latter, a consistent number of runs needs to be determined. \$\endgroup\$
    – Xcali
    Aug 18 at 22:43
1
\$\begingroup\$

Solve the Greek Computer Puzzle Toy

Posted live: Solve the Greek Computer Puzzle Toy

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

Find "Millionaire" score

I was looking through the uploads of GAMES Magazine to archive.org, and in the first publication I found a challenge called "Millionaire: a word-and-number prize competition".

In this game, each word is assigned a score in the following way:

  1. Turn each letter in the word into a number: A becomes 1, B becomes 2, C becomes 3, and so on.
  2. Multiply the numbers.

For example, the score for BED is \$2*5*4 = 40\$.

(In the competition, the goal was to find the word whose score is closest to a million, but that's not relevant here.)

The challenge

Given a word (i.e. a sequence of uppercase letters) as an input, output its score.

Test cases

Input Output
A 1
Z 26
BED 40
CHAIR 3888
BOTTOM 2340000

Questions

This challenge is probably not new -- please let me know what it's duplicating. I could make the challenge something like "given a list of words, find the word whose score is closes to a million", but I think that's particularly uninteresting.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Closely related, likely related enough to count as a duplicate. This one multiplies the letters, that one adds them. Although if it was me, I would close the other one as it requires you to error if there's special characters, and you have to handle both lowercase and uppercase. \$\endgroup\$
    – Steffan
    Aug 22 at 17:25
1
\$\begingroup\$

Make a Brainfuck Interpreter

\$\endgroup\$
3
  • 1
    \$\begingroup\$ @thejonymyster woops. fixed \$\endgroup\$
    – Seggan
    Aug 30 at 22:57
  • \$\begingroup\$ It might be nicer to allow solvers to assume that the input doesn't contain anything besides <>,.+-[]? \$\endgroup\$ Aug 30 at 23:29
  • \$\begingroup\$ @Adam true. I'll update it \$\endgroup\$
    – Seggan
    Aug 30 at 23:56
1
\$\begingroup\$

Optimally pop all the bubbles

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

Render a triangle in vulkan

The vulkan API is famous for requiring graphic engines to be very verbose (usually at least 1000 lines of code for a basic result). I am curious to see how far we can escape this trend.

Task

Using vulkan and no other rendering API, have a triangle rendered to screen with a color pattern as seen in this image: vulkan triangle For rendering to screen, some extensions are needed. You should use the minimal number of extensions and layers necessary.

Points are counted as the number of bytes of the program file plus number of bytes of shader files if needed.

You can take whatever shortcuts you want as long as it runs on your machine. You should provide a screenshot of the result as a minimal kind of proof.

Hints

  • As a reference implementation you can check the vulkan tutorial. The code of 15_hello_triangle.cpp is 34536 bytes, and it uses two shaders of 389 and 158 for a total of 35 083 bytes. The c++ code is contained in a single file but this is far to be an optimal solution.
  • You can assert the running machine will be yours and skip all the property checks for devices, queues etc.
  • Well known window creation libraries such as GLFW or SDL are authorized.
  • You can use existing Language bindings to provide a solution in you favorite language.
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and thanks for using the Sandbox! \$\endgroup\$
    – Steffan
    Sep 5 at 19:04
1
\$\begingroup\$

Posted

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

Erasure Poetry

Given two strings \$A\$ and \$B\$, count how many characters need to be removed from \$A\$ to transform it into string \$B\$. (META: i am still brainstorming what this actual challenge part should be).

However, you will not be "writing" programs/functions to solve this challenge, so much as you will be finding them in the previous answer.

Challenge specification

(meta: as previously stated, the exact challenge here may change, but it will stay similarly topical)

Take two strings \$A\$ and \$B\$

Scoring specification

Contrary to what I said in the intro, you will technically be writing a program or function to solve this challenge. However, you will not be scored directly on your code length.

Included with your answer will be (some representation of) the bytes you will remove from the previous answers program such that it becomes your program. If this is not possible with removals alone, you may also add bytes to the previous answer, but this will come with a score penalty.

In particular: Your score is the number of bytes you need to add, with byte deletions having no impact on your score. Lowest score wins.

The first answer to base your score off of will be provided at the bottom of this post.

Answer chaining rules

Importantly, no two answers may use the same language. Flags and version numbers do not differentiate languages in this challenge.

(meta: need to clarify more rules regarding answer chaining)

0. language name, +n bytes

program

Try It Online!

meta

work in progresss, but feel free to suggest anything you think i might be missing, even if it seems obvious

Rule change idea: Using a language again is permissible if your answer in Language A will score lower (better) than the previous answer in Language A. thoughts?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ How does this work with SBCS? \$\endgroup\$ Sep 5 at 17:37
  • \$\begingroup\$ @CommandMaster not sure yet, im thinking about just making it based on the byte value itself. seems fair since most languages use just printable ascii, and from what ive seen, most SCBSes have their printable ascii on the same bytes as regular printable ascii. I might require / ask that languages with alternate encodings provide a hex dump. Does that sound reasonable? \$\endgroup\$ Sep 5 at 18:09
1
\$\begingroup\$

Guess the Caesar cipher shift

A Caesar cipher is a cipher which takes a message and an integer \$n\$ between 0 and 25 (inclusive). Each letter in the message is then "shifted over" in the alphabet by \$n\$ letters, wrapping around the beginning of the alphabet. For example, when \$n=1\$, A becomes B, B becomes C, and so on, up to Z which becomes A. (Uppercase/lowercase is kept the same and punctuation is ignored.)

The challenge

Given a string which represents a message encoded using a Caesar cipher with some shift \$n \in [0,25]\$, output a guess for \$n\$. (You can decide whether punctuation is included or stripped ahead of time.) For example, if you take the word Happy code golfing! and encode it using a Caesar cipher with a shift of 3, you get Kdssb frgh jroilqj!. So if your program takes in Kdssb frgh jroilqj!, it should output 3. Your solution should be deterministic -- e.g. no random number generators.

Scoring

To find the score of your function, it should be tested on every paragraph in Pride and Prejudice1 and every possible shift value (from 0 to 25). Here's a link to a text file with each paragraph on a single line, and here's an alternate version where the quote marks have been replaced with ASCII alternatives. There are 2074 paragraphs, so there are \$26*2074 = 53924\$ test inputs. Your score is equal to

$$s(b,p)=(1+\sqrt{b}) (1+\sqrt{p})-1$$ $$b = \text{number of bytes}$$ $$p = \text{proportion incorrect} = 1-\frac{\text{number of test inputs correct}}{53924}$$

so, for example, a 100 byte program that got 13481 tests correct (i.e. \$\frac34\$ of them incorrect) would have a score of \$(1+\sqrt{100})(1+\sqrt{\frac34})-1 = 15.5\$.

Your goal is to minimize your score.

Here's a link to some Python code, which can be run online, containing a test harness, along with a baseline program to which you can compare your answer. In this case, I've opted to remove all punctuation before parsing each line. For reference, this function is 89 characters and gets 40144/53924 tests correct, so its score is 14.70850917.

Test cases

Input Output
Hs hr z sqtsg tmhudqrzkkx zbjmnvkdcfdc, sgzs z rhmfkd lzm hm onrrdrrhnm ne z fnnc enqstmd, ltrs ad hm vzms ne z vhed. 25
“Rk! brx duh d juhdw ghdo wrr dsw, brx nqrz, wr olnh shrsoh lq jhqhudo. Brx qhyhu vhh d idxow lq dqbergb. Doo wkh zruog duh jrrg dqg djuhhdeoh lq brxu hbhv. L qhyhu khdug brx vshdn loo ri d kxpdq ehlqj lq pb olih.” 3
“That is a question which Mr. Darcy only can answer.” 0
Vczqrsvky cffbvu ritycp, reu klievu rnrp. Yvi ivjzjkretv yru efk zealivu yvi nzky kyv xvekcvdre, reu yv nrj kyzebzex fw yvi nzky jfdv tfdgcrtvetp, nyve kylj rttfjkvu sp Dzjj Szexcvp, 17

1Chosen because it's the most popular book on Gutenberg at the time of writing.

Questions

The scoring function seems like it could be gamed by writing a really short, really inaccurate function, so I'm thinking of adding a function which penalizes incorrect answers even harsher.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Every paragraph in a whole book? Man, that will be a pain to do lol \$\endgroup\$
    – Steffan
    Aug 24 at 2:32
  • 1
    \$\begingroup\$ Suggested tags: test-battery, cipher, string. Related: codegolf.stackexchange.com/questions/241532/… \$\endgroup\$
    – pajonk
    Aug 24 at 11:02
  • 1
    \$\begingroup\$ Suggestion: make accuracy explicit (as correct guesses / total tests). Also maybe add a line that the goal is to minimise the score. \$\endgroup\$
    – pajonk
    Aug 24 at 11:07
  • \$\begingroup\$ @pajonk Is this too similar to the related question? \$\endgroup\$ Aug 24 at 16:38
  • 1
    \$\begingroup\$ @Adam, no, I don't think so. Although the concept of reversing Caesar is common to both of them, the test-battery will surely make resulting approaches very different. I provided the link only for reference. \$\endgroup\$
    – pajonk
    Aug 24 at 18:22
  • 1
    \$\begingroup\$ you might want to ban random generators since luck can affect score \$\endgroup\$
    – okie
    Sep 3 at 4:01
  • 1
    \$\begingroup\$ The scoring functions seems to mean that any code that gets everything correct gets a score of 0 no matter how long it is. An empty program also scores 0 in a language where this is a valid program producing 0, say by exit code. \$\endgroup\$
    – xnor
    Sep 11 at 10:44
  • \$\begingroup\$ @xnor I've updated the function to resolve this, though it's not particularly elegant. \$\endgroup\$ Sep 11 at 19:43
  • \$\begingroup\$ a 0 byte answer with 0 correct will have score 1, same as a 1 byte answer that get 100% correct, which means 0 byte basically wins \$\endgroup\$
    – okie
    Sep 17 at 2:26
1
\$\begingroup\$

Title

God Save the Queen (or King)!

Input

A calendar year from 927 to the present year. For example 2022.

Output

You can use any three distinguishable outputs. As an example,

“K” (short for King)

or

“Q” (short for Queen)

depending on which was right in England in that year. If there was both a King and Queen in that year you can output either.

If there was no King or Queen for the whole of that year, your code must output something that is not one of those two messages.

Dates

Kings: 937-1553, 1603-1649, 1660-1702, 1714-1837, 1901-1952, 2022

Queens: 1553-1603, 1689-1694, 1702-1714, 1837-1901, 1952-2022

\$\endgroup\$
7
  • \$\begingroup\$ An interesting idea: instead of forcing it to be on January 1, allow years with multiple monarchs to choose one arbitrarily? Could add some depth to the compression strategies. \$\endgroup\$ Sep 17 at 5:23
  • \$\begingroup\$ @UnrelatedString Good idea \$\endgroup\$
    – graffe
    Sep 17 at 5:28
  • 1
    \$\begingroup\$ Two downvotes?? Please explain \$\endgroup\$
    – graffe
    Sep 17 at 5:30
  • \$\begingroup\$ The fixed output strings are a common thing to avoid. I think they'd be better off as any two outputs of the golfer's choice, with everything else corresponding to neither king nor queen. \$\endgroup\$
    – xnor
    Sep 17 at 7:57
  • \$\begingroup\$ @xnor that's a shame as the messages are what make the challenge more fun. \$\endgroup\$
    – graffe
    Sep 17 at 9:20
  • \$\begingroup\$ I really don't see how "K" or "Q" (which is what the output requires now) makes the challenge more fun. \$\endgroup\$
    – user
    Sep 17 at 16:37
  • \$\begingroup\$ @user it was previously "God Save the King" but I changed it on xnor's advice. \$\endgroup\$
    – graffe
    Sep 17 at 16:40
1
\$\begingroup\$

Construct Digit From Digits

In the game All Ten, each day you are given four single-digit positive integers, and have to use all four of those numbers once each to construct the values 1 through 10 using the following operations:

  • Addition
  • Subtraction
  • Multiplication
  • Division
  • Concatenation, i.e. joining two numbers together; for example, \$1 \text{ concat } 23 = 123\$. (You can only apply this operation if both of the numbers are integers and the number on the right is non-negative.)

So, for example, given numbers \$[4,4,8,9]\$, to make \$4\$ you could do \$((4 \text{ concat } 4) - 8 ) / 9\$. which equals \$(44 - 8)/9 = 36 / 9 = 4\$.

You're allowed to compose these operations however you want, in whatever order, including concatenation (e.g. you can do \$16 - ((2-1) \text{ concat } 3) = 16 + (-1 \text{ concat } 3) = 16 - 13 = 3\$.)

The challenge:

Your function is given two inputs: \$I\$, which is a list of four single digit positive integers (i.e. in the range \$1,2,\ldots,9\$) which are not necessarily unique, and \$n\$, which is also a single digit positive integer.

Your function should return a way of using all four numbers in \$I\$ to construct \$n\$ using the rules above.

Output Format

You can provide the output in any meaningful way, including:

  • A string (or list of numbers/characters) representing the expression which evaluates to \$n\$, using any symbols besides \$1,2,\ldots,9\$ to represent the operations / parentheses necessary
    • e.g. "((4c4)-8)/9"
    • You're also allowed to represent concatenation with the empty string (i.e. no operator at all) -- e.g. "((44)-8)/9"
    • You can leave out parentheses if you specify the order of operations -- e.g. you say that concatenation has highest priority, then return "(44-8)/9"
  • A tree or nested list with where each leaf represents a number in \$I\$ and the parents represent the various operations

You may assume there is at least one solution; if there's more than one solution, you may output any of them.

Test cases

[To do -- I need to enumerate all of the possible ways to construct a given value for this to be useful.]

Questions

This is a really bad title, but it's hard to describe succintly. There's also a lot of text here, but I don't know how to shorten it.

\$\endgroup\$
8
  • \$\begingroup\$ May the output be in Reverse Polish notation, removing the need for parenthesis completely? Or does that bend the 'provide output in any meaningful way' too much? \$\endgroup\$ Sep 27 at 12:07
  • \$\begingroup\$ Also, is the division regular division or integer division? If the first, is something like ((1/5)concat 5)*8 = 2 valid (where 1 /5 -> 0.2 concat 5 -> 0.25 *8 -> 2)? And how to deal with floating point inaccuracies in that case? \$\endgroup\$ Sep 27 at 12:13
  • \$\begingroup\$ Closely related - partial duplicate Difference is that that challenge asks to use the digits 0 through 9, instead of an input-list of 4 digits. And this challenge allows concatenation, whereas the other answer allowed exponentiation. But my 05AB1E answer would be nearly the same. \$\endgroup\$ Sep 27 at 12:26
  • \$\begingroup\$ @KevinCruijssen (1) I think that Polish notation should be allowed. (2) It's supposed to be regular divison, though the expression you gave isn't valid because you aren't allowed to concatenate non-integers. I don't understand the second part -- the solver needs to handle floating point inaccuracies so they give the correct answer. (3) I don't know how close two challenges need to be before they are counted as distinct -- do you think this is still worth posting? It seems like the answer is no... \$\endgroup\$ Sep 27 at 15:00
  • \$\begingroup\$ @97.100.97.109 In the original game, concatenation is only allowed on the original integers; i.e. you cannot do (2 - 1) concat 3. Is that not the case here? \$\endgroup\$
    – pigrammer
    Sep 27 at 16:36
  • \$\begingroup\$ @pigrammer You can if you do, e.g. (2-1)=, which saves a 1 to your "workspace", which means you can then do 1 concat 3. \$\endgroup\$ Sep 27 at 17:35
  • \$\begingroup\$ @97.100.97.109 No, it gives an error "Combo buttons cannot be used in two-digit numbers" \$\endgroup\$
    – pigrammer
    Sep 27 at 17:36
  • \$\begingroup\$ @prigrammer Whoops, I was wrong. I think I'll still allow it since it makes the application marginally simpler. \$\endgroup\$ Sep 27 at 18:47
1
\$\begingroup\$

Create a nibble shorthand

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is it strict graphical-output or we may return a collection of symbols (read: ascii-art) to represent a nibble? Also, is scaling allowed (I mean, like mirrored r is smaller version of the image for the reverse of r)? \$\endgroup\$
    – pajonk
    Sep 25 at 18:47
  • \$\begingroup\$ @pajonk It's graphical output. Scaling is not allowed. \$\endgroup\$
    – Wheat Wizard Mod
    Sep 25 at 18:53
1
\$\begingroup\$

N-element Rock Paper Scissors

Given an odd integer \$n>2\$, decide the winner for \$n\$-element Rock Paper Scissors.

What is \$n\$-element Rock Paper Scissors?

Rock Paper Scissors is a game in which two players choose between the elements Rock, Paper, and Scissors, and simultaneously reveal their selections. If one player chooses Rock, they will win against a player who chose Scissors, lose against a player who choses Paper, and tie a player who also chose Rock. It is a zero sum game, so a player losing means their opponent has won, and vice versa. Every element beats one element, loses to another, and ties with itself.

A common extension to this game is to add two aditional elements (most famously "Lizard" and "Spock"). In this extension, there are now 5 elements, so each element beats two elements, loses to two elements, but still ties only itself. We can generalize this cleanly to any odd number of elements \$n\$, in which each element will beat \$(n-1)/2\$ elements, lose to \$(n-1)/2\$ elements, and tie with itself.

Challenge specification

Program 1

This program should take an odd integer \$n>2\$ as input in any reasonable format decided by the solver, and output the Program 2 as defined below in terms of \$n\$. Alternatively, this program may instead take the Program 2's inputs along with \$n\$, and provide the Program 2's expected output instead.

This program is the one you will be scored on. This is , so shortest code in bytes wins.

Program 2

This program should take two elements \$A\$ and \$B\$ as input in any reasonable format decided by the solver, and consistently output either one of the following:

  • Whether \$A\$ beats \$B\$, loses to \$B\$, or ties with \$B\$.
  • The winner between \$A\$ and \$B\$, or in the case of a tie, some other distinct output.

Only \$n\$ possible inputs need to be handled by this program. Each possible element must consistently beat \$(n-1)/2\$ elements, lose to \$(n-1)/2\$ elements, and tie with itself. If some element \$a\$ beats an element \$b\$, element \$b\$ loses to element \$a\$. Which elements are allowed and which elements beat which etc. are to be decided by the solver. This must be consistent for each execution of Program 2 for the same \$n\$

Examples:

Your I/O may differ.

Format:
n (input to Program 1)
a b c d e (list of inputs accepted by Program 2, space delimited for all examples)
x y (inputs to Program 2, space delimited for all examples)
value (whether x wins, loses, or ties y)

3
r p s
r p
lose

3
r p s
r r
tie

3
r p s
r s
win

5
0 1 2 3 4
0 1
win

5
0 1 2 3 4
0 2
win

5
0 1 2 3 4
0 3
lose

5
0 1 2 3 4
0 4
lose

5
abcde bcdea cdeab deabc eabcd
bcdea cdeab
lose

5
abcde bcdea cdeab deabc eabcd
bcdea deabc
lose

5
abcde bcdea cdeab deabc eabcd
bcdea eabcd
win

5
abcde bcdea cdeab deabc eabcd
bcdea abcde
win

5
abcde bcdea cdeab deabc eabcd
bcdea bcdea
tie

13
a b c d e f g h i j k l m
g e
lose

13
a b c d e f g h i j k l m
g m
win

13
a b c d e f g h i j k l m
d h
win

13
a b c d e f g h i j k l m
h d
lose

Meta

Everything clear? Any other examples needed? Maybe a worked out example?

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

Longest alternating subsequence

\$\endgroup\$
2
  • \$\begingroup\$ If our language uses an SBCS, can we use UTF-8 if it helps with the score? \$\endgroup\$
    – Steffan
    Sep 29 at 0:22
  • \$\begingroup\$ @Steffan You can choose the encoding in your favor if your language supports multiple encodings. \$\endgroup\$
    – Bubbler
    Sep 29 at 0:32
0
\$\begingroup\$

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.

\$\endgroup\$
11
  • \$\begingroup\$ Meh. I don't like dependency on external files; are we allowed to load it, or even embed it into the source code? \$\endgroup\$ Dec 17, 2013 at 20:00
  • \$\begingroup\$ as for finding more vs. shorter code, you could demand all words be found \$\endgroup\$ Dec 17, 2013 at 20:19
  • \$\begingroup\$ @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. \$\endgroup\$
    – Rob
    Dec 17, 2013 at 20:23
  • 5
    \$\begingroup\$ 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). \$\endgroup\$ Dec 18, 2013 at 8:01
  • \$\begingroup\$ 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?) \$\endgroup\$ Dec 18, 2013 at 8:32
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – Iszi
    Dec 18, 2013 at 21:14
  • \$\begingroup\$ 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. \$\endgroup\$
    – Iszi
    Dec 18, 2013 at 21:15
  • \$\begingroup\$ 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. \$\endgroup\$
    – Iszi
    Dec 18, 2013 at 21:15
  • \$\begingroup\$ 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. \$\endgroup\$
    – Iszi
    Dec 18, 2013 at 21:18
  • \$\begingroup\$ @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. \$\endgroup\$
    – Rob
    Dec 19, 2013 at 16:40
  • \$\begingroup\$ 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. \$\endgroup\$
    – Iszi
    Dec 19, 2013 at 16:56
0
\$\begingroup\$

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:

  • Base Program (in the same language as your answer)
  • 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.

\$\endgroup\$
8
  • \$\begingroup\$ Problem: some subsequences of legitimate answers may be pretty dangerous to the environment. You don't want to eval just everything. \$\endgroup\$ Dec 23, 2013 at 16:59
  • \$\begingroup\$ @JanDvorak Yes that actually is a serious problem. To what extent is it possible to fix that? \$\endgroup\$
    – PhiNotPi
    Dec 23, 2013 at 17:04
  • 1
    \$\begingroup\$ Forbidding any program with dangerous subsequences? :-) \$\endgroup\$ Dec 23, 2013 at 17:05
  • 1
    \$\begingroup\$ A more reasonable (but very difficult) solution would be the requirement to implement a sandbox. \$\endgroup\$ Dec 23, 2013 at 17:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – MvG
    Jan 7, 2014 at 23:49
  • \$\begingroup\$ 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. \$\endgroup\$ May 16, 2021 at 4:44
  • \$\begingroup\$ 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. \$\endgroup\$ May 16, 2021 at 4:54
  • \$\begingroup\$ 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 \$\endgroup\$ May 16, 2021 at 5:25
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Jan 8, 2014 at 8:45
0
\$\begingroup\$

Rhymalator

(at the point, it's just something that came to me before i wake up, so it may need some adjusting, and i'd like some feedback as to if this could be fun)


The code challenge is to write a program that takes as input a calculation in Reverse Polish Notation and outputs the result. It must at least implement + - * /. It So far so easy, but to make it fun and "artistic", the following restriction applies:

  • The source code must rhyme when read. Example in PHP

    $iterator = str_split($a);
    foreach ($iterator as $key=>$value){
        if ($key > 3){
            ++$virtue;
        }
    }
    

    (the rhyme is on value-virtue)

  • Lines whitout readable characters count as whitespace (the two lines with } in the example)

\$\endgroup\$
2
  • \$\begingroup\$ How does that example rhyme...? \$\endgroup\$
    – Doorknob
    Jan 25, 2014 at 12:54
  • \$\begingroup\$ @DoorknobofSnow well, i'm not really a poet, that's why i propose it as a challenge for others :p. if you have a better example i'll replace it \$\endgroup\$
    – Einacio
    Jan 27, 2014 at 15:58
1
72 73
74
75 76
135

You must log in to answer this question.

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