571
\$\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".

\$\endgroup\$
2
  • \$\begingroup\$ What if I posted on the sandbox a long time ago and get no response? \$\endgroup\$
    – None1
    Commented May 15 at 14:05
  • \$\begingroup\$ @None1 If you don't get feedback for a while you can ask in the nineteenth byte \$\endgroup\$
    – mousetail
    Commented May 29 at 13:27

4704 Answers 4704

1
81 82
83
84 85
157
1
\$\begingroup\$

Find the best character arrangement

You want to write your English essay. However, all characters on your keyboard broke other than the arrow keys and the enter key. You want to find out how to place the characters so you can write your essay with the least movement.

Formally, you have to assign to each character of !"$%&'()+,-./0123456789:;<=?[]`abcdefghijklmnopqrstuvwxyz⇦⇧ a unique integer coordinate, and minimize \$ d = \sum_{c_1 , c_2} {\text{freq}(c_1, c_2) \text{dist}(c_1, c_2)} \$, with \$\text{dist}\$ being the Manhattan destince between the position of the characters, and \$\text{freq}\$ being the frequency of the character pair, which is described here, with the frequency of each pair not detailed assumed \$0\$.

Scoring

The winner is the code which could produce the best result in a minute on my computer, with the tie breaker being the time until that result is found.

Rules

  • Your language must have a freely available interpreter/compiler capable of running on Linux
  • Standard loopholes are disallowed, except optimizing for the given test cases - you are allowed (and even expected) to fine-tune your solution to produce the best solution on this given test case.
  • You can't hardcode calculations - the solution should be found by the code during its execution, not beforehand.
  • You can use any reasonable output format (i.e. output your solution and when did you find it when your program terminates, output your solution whenever the program improves it, etc.).
  • You will receive the frequency JSON in stdin.
  • Your solution must be deterministic. You can use PRGNs, you just have to hard code their seed.
\$\endgroup\$
1
\$\begingroup\$

Bloons TD 6 Upgrade Paths

\$\endgroup\$
3
  • 1
    \$\begingroup\$ add tag kolmogorov-complexity. Interesting idea, I quite enjoy the upgrade path system in this game :) especially when the abilities that lock eachother out make sense to be mutually exclusive, like the catapult vs the crossbow \$\endgroup\$ Commented Jun 26, 2022 at 22:11
  • \$\begingroup\$ @thejonymyster actually idk if that applies because the order is not fixed \$\endgroup\$
    – qwr
    Commented Jun 30, 2022 at 17:22
  • \$\begingroup\$ that just makes it a set, which still counts imo. "output this set" would make sense as kc. if anything, though, heres another challenge which does that \$\endgroup\$ Commented Jun 30, 2022 at 23:04
1
\$\begingroup\$

Where does the seesaw balance?

There have been a couple seesaw balance questions but none of them are doing this version of the question. Adding weight to one side, or small inputs with ascii art have been done already, but I think this would be unique enough to not be a duplicate.

Problem: Given some ordered sequence of single-digit positive integers representing weights (say 0kg to 9kg), output at what index or indices the fulcrum have to be at such that the beam balances. If it doesn't balance anywhere, then output some non-location without erroring.

This is assuming a massless beam. The fulcrum is at the center of one of the weights, and the output must be integer-valued (no putting the fulcrum between two weights). Output can be either 0-indexed or 1-indexed and should be specified in the answer.

Valid outputs if the seesaw balances would include 2, 8.0, [5], a list of all positions that work, "3" and so on, but not 4.25. Valid outputs if the seesaw does not balance anywhere would include -1, [], "", NaN and so on, but not 0 or [7].

Example: Given the input [2,3,0,0,5,9,4] the output should be 4 since a pivot at that index causes the torques/moments to balance (2*4+3*3+0*2+0*1 = 9*1+4*2). Below is a visualization:

2300594 (weights)
=======
    ^
0123456 (indices)

The weight at the fulcrum doesn't contribute to either side.

Failure example: Given the input [1,3,4,1,2] the output should be -1 (or null or [] or some other obviously non-position output) because at no fulcrum position would this this seesaw be stable and balanced.

Edge cases: An input that is all zeros (eg. [0,0,0,0,0,0]) can balance at any index, but the program only needs to output at least one of them. An input that doesn't follow the input rules (eg. [], ["a","b"], [-3], [1.234,2.34,3.4]) is not expected to give any output of any kind and can error out.

Test cases: Using NaN as the "no solution" output. Output is 0-indexed.

[6] -> 0
[1,0] -> 0
[1,1] -> NaN
[9,1,9] -> 1
[1,2,3,4] -> 2
[1,2,3,4,5] -> NaN
[1,3,4,1,2] -> NaN
[2,3,0,0,5,9,4] -> 4
[1,2,3,4,5,6,7] -> 4
[0,0,0,3,0,0,0,3] -> 5
[0,0,0,3,0,0,3,0] -> NaN
[1,0,0,2,0,0,0,0,0,0,0,0] -> 2
[6,2,6,3,4,8,1,1,1,1,1,1,1,1,1,1,1] -> 5

Being code golf, fewer bytes of code is better here!

\$\endgroup\$
8
  • \$\begingroup\$ You might mention that we can use 0 or 1 indexing (if it is allowed) \$\endgroup\$
    – naffetS
    Commented Jun 30, 2022 at 18:40
  • \$\begingroup\$ That's a good idea, thanks! \$\endgroup\$
    – rtrb
    Commented Jun 30, 2022 at 18:52
  • \$\begingroup\$ Can we instead output all indices that would work (hence an empty list in the case of none)? \$\endgroup\$
    – naffetS
    Commented Jun 30, 2022 at 18:57
  • \$\begingroup\$ I don't see why not. In most cases that'll just be a list with one element but it covers the edge cases pretty well. I already had [5] and [] as valid outputs for the success/fail states but I'll clarify further. \$\endgroup\$
    – rtrb
    Commented Jun 30, 2022 at 19:00
  • \$\begingroup\$ Welcome to CGCC and thanks for using the Sandbox! I suggest stating explicitly that this is code-golf in the challenge body (besides the tag). \$\endgroup\$
    – pajonk
    Commented Jun 30, 2022 at 20:36
  • \$\begingroup\$ Thank you! Updated \$\endgroup\$
    – rtrb
    Commented Jun 30, 2022 at 22:22
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/151318/… Closely related: codegolf.stackexchange.com/questions/132512/… \$\endgroup\$
    – Laikoni
    Commented Jul 1, 2022 at 4:39
  • \$\begingroup\$ The second one might be close enough to be considered a duplicate, given that the main task is the same and only the input format is different. However personally I prefer the simpler format from this challenge. \$\endgroup\$
    – Laikoni
    Commented Jul 1, 2022 at 4:44
1
\$\begingroup\$

Get multi-dimensional indices in a list

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

Erverse Hte Ifrst Wto Eltters fo Aech Owrd

\$\endgroup\$
3
  • \$\begingroup\$ Will all words in input contains at least two letters? Also, a testcase where some first two letters of words are equals should be helpful. \$\endgroup\$
    – tsh
    Commented Jul 4, 2022 at 6:12
  • \$\begingroup\$ Suggested testcases: (empty input) -> (empty output), i ate a banana -> i tae a abnana, pptx is one of ooxml format -> pptx si noe fo ooxml ofrmat. \$\endgroup\$
    – tsh
    Commented Jul 4, 2022 at 6:20
  • \$\begingroup\$ @tsh and that there will be no one-letter words \$\endgroup\$
    – Seggan
    Commented Jul 4, 2022 at 14:27
1
\$\begingroup\$

Nest some addition, differently

This question is a follow-up to Nest some addition.

Lambda calculus is a system of computation based on single-argument functions; everything in it is such a function. Due to this functional nature, juxtaposition is commonly used to denote function application, grouped from left to right. For example, \$(f g) h=f g h\$ denotes what would conventionally be written \$(f(g))(h)=f(g)(h)\$.

Church numerals are a way of encoding the nonnegative integers in this system. They can be defined as follows:
\$\begin{align*} \overparen{\underparen0} f &= \operatorname{id}\\ \overparen{\underparen 1} f &= f\circ\left(\overparen{\underparen 0} f\right)=f\\ \overparen{\underparen 2} f &= f\circ\left(\overparen{\underparen 1} f\right)=f\circ f\\ \vdots\\ \overparen{\underparen n} f &= f\circ\left(\overparen{\underparen{n-1}} f\right)\\ &=\underbrace{f\circ\cdots\circ f}_n, \end{align*}\$
where \$\circ\$ denotes function composition. In other words, the Church numeral \$\overparen{\underparen n}\$ can be seen as a unary operator on a function \$f\$ that nests that function \$n\$ times.

There is a another binary operator that performs addition on two Church numerals:
\$\begin{align*} \operatorname{dda} \overparen{\underparen a} \overparen{\underparen b} f&= \overparen{\underparen{a+b}} f\\ &= \left(\overparen{\underparen b} f\right)\circ\left(\overparen{\underparen a} f\right). \end{align*}\$
That is, we nest \$f\$ \$a\$ times, then another \$b\$ times.

As with \$\operatorname{add}\$, \$\operatorname{dda} \overparen{\underparen a}\$ is a unary operator that, when applied to another Church numeral \$\overparen{\underparen b}\$, results in \$\overparen{\underparen{a+b}}\$. Now what happens when we reverse the order, i.e. attempt to evaluate \$\overparen{\underparen a}\operatorname{dda}\$? This resulting function still has arity \$a+1\$.

Task

Given (optionally) an integer \$a\ge0\$, and another \$a+1\$ integers \$x_0,x_1,...,x_a\ge0\$ in a consistent ordering, compute the integer \$n\$ such that \$\overparen{\underparen n}=\overparen{\underparen a} \operatorname{dda} \overparen{\underparen{x_0}} \overparen{\underparen{x_1}}...\overparen{\underparen{x_a}}\$.

You will also need to know the multiplication and exponentiation rules:
\$\begin{align*} \overparen{\underparen{a\times b}} f&=\overparen{\underparen b} \left(\overparen{\underparen a} f\right)=\left(\overparen{\underparen b}\circ\overparen{\underparen a}\right)f\\ \overparen{\underparen{a^b}} f &= \overparen{\underparen b} \overparen{\underparen a} f. \end{align*}\$

Example

Take \$4 \operatorname{dda} 3\,2\,1\,3\,2\$:
\$\begin{align*} \overparen{\underparen{4}} \operatorname{dda} \overparen{\underparen{3}} \overparen{\underparen{2}} \overparen{\underparen{1}} \overparen{\underparen{3}} \overparen{\underparen{2}} &= \left(\operatorname{dda}\circ\operatorname{dda}\circ\operatorname{dda}\circ\operatorname{dda}\right) \overparen{\underparen{3}} \overparen{\underparen{2}} \overparen{\underparen{1}} \overparen{\underparen{3}} \overparen{\underparen{2}}\\ &=\operatorname{dda}\left(\operatorname{dda}\left(\operatorname{dda}\left(\operatorname{dda} \overparen{\underparen{3}}\right)\right)\right) \overparen{\underparen{2}} \overparen{\underparen{1}} \overparen{\underparen{3}} \overparen{\underparen{2}}\\ &=\overparen{\underparen{2}} \overparen{\underparen{1}} \left(\operatorname{dda}\left(\operatorname{dda}\left(\operatorname{dda} \overparen{\underparen{3}}\right)\right) \overparen{\underparen{1}} \overparen{\underparen{3}}\right) \overparen{\underparen{2}}\\ &=\operatorname{dda}\left(\operatorname{dda}\left(\operatorname{dda} \overparen{\underparen{3}}\right)\right) \overparen{\underparen{1}} \overparen{\underparen{3}} \overparen{\underparen{2}}\\ &=\left(\overparen{\underparen{1}} \overparen{\underparen{3}}\right) \left(\operatorname{dda}\left(\operatorname{dda} \overparen{\underparen{3}}\right) \overparen{\underparen{3}} \overparen{\underparen{2}}\right)\\ &=\overparen{\underparen{3}} \left(\left(\overparen{\underparen{3}} \overparen{\underparen{2}}\right)\circ\left(\operatorname{dda} \overparen{\underparen{3}} \overparen{\underparen{2}}\right)\right)\\ &=\overparen{\underparen{3}} \left(\overparen{\underparen{8}} \times \overparen{\underparen{5}}\right)\\ &= \left(\overparen{\underparen{40^3}}\right)=\overparen{\underparen{64000}} \end{align*}\$

Test cases

a   x           result
0   9               9
1   2,2             4
2   3,4,5           5000
2   7,1,8           120
3   2,2,2,2         65536
3   2,3,2,4         7213895789838336
4   3,2,1,3,2       64000
4   3,1,4,1,5       8782696764280
5   1,2,1,2,1,2     42
5   1,2,1,3,1,4     176820
5   2,1,2,1,2,1     446941881
6   1,2,1,2,1,2,1   331776

5   2,2,2,1,1,1     46067585792061179986003103589270890479268003416963782070185329396818296983805445959073166440720581387038540029877988577743446452288030374115737071650858255804704645216460811594784946208110262803842901974222092931885696117997589640107161975226690021967819064275487285233512229404788315869062112469518816261355388074282508579612820589720868169439536003406995417291950455148984482997260637332557020455012974915559243748189682760671362747474046184227448861411296966290899881082905099904256926315617201402705453906211612138979485925239261758925413761498970666786937460520926437582982463058742990808351770234630680221463616795434886004399826242096099

Notes

  • I expect this should differ quite a bit from the previous challenge for non-lambda-calculus-based languages due to how \$a\ge4\$ expands.
    • But is there a viable method that's not just brute force lambda calculus expansion?
\$\endgroup\$
1
\$\begingroup\$

Convert Descriptive Notation to Algebraic Notation

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

Runs Between Values

In my work, I needed to find all the indices of values in a list that were between two given values. However, because these associated values tended to come in "clumps", it made sense to compress them into "runs", which describe sections of the list matching the criteria based on the starting and ending index of the sequence of matching values. For example, suppose we're looking for values between \$1\$ and \$3\$ in the following list:

i =  0 1 2 3 4 5 6 7 8 9 
a = [1 4 5 3 2 1 0 5 2 3]
     ✓     ✓ ✓ ✓     ✓ ✓
i =  0     3 4 5     8 9 

So we output \$[(0,0), (3,5), (8,9)]\$.

More formally: Given a list of integers \$[a_1, ...a_n]\$ and two integers \$x\$ and \$y\$, output all tuples of indices \$(i,j)\$ where the values in the subsequence \$[a_i,...,a_j]\$ are between \$x\$ and \$y\$ inclusive. (The values in the subsequence do not have to be in order.) You must return as few tuples as necessary to cover all the values between \$x\$ and \$y\$ - e.g. in the above example you should not return \$[(0,0), (3,4), (5,5), (8,9)]\$.

Your indices may start from 0 or 1. Standard loopholes are forbidden.

Here's a program to generate test cases.

Sandbox Questions

I haven't gone through all previous challenges, so I don't know if this has been done before.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ I don't think the part of x <= a_i <= y is necessary for the challenge - I believe it would be better if the input was an array of true/false (and you only need to compress runs of true). It currently seems like you combine finding elements between x and y and compressing runs, which is generally discouraged \$\endgroup\$ Commented Jul 16, 2022 at 17:12
  • \$\begingroup\$ Should I make a new challenge for that, or edit this one? \$\endgroup\$ Commented Jul 18, 2022 at 15:19
  • \$\begingroup\$ Since it's in the sandbox, it's fine to edit it however you want \$\endgroup\$ Commented Jul 18, 2022 at 16:49
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\$ Commented Jun 19, 2019 at 22:38
  • \$\begingroup\$ @JonathanFrech yes, thanks a lot! \$\endgroup\$
    – flawr
    Commented 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\$ Commented Jul 19, 2022 at 8:39
  • \$\begingroup\$ Is there any particular reason "just to make it even more interesting" is in LaTeX? \$\endgroup\$ Commented Jul 19, 2022 at 8:45
  • \$\begingroup\$ @CommandMaster Done, Thank you. No, nothing in particular \$\endgroup\$
    – cheems
    Commented Jul 19, 2022 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\$ Commented Jul 20, 2022 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\$ Commented Jul 18, 2022 at 3:56
  • \$\begingroup\$ @CommandMaster sure thing, i'll clarify \$\endgroup\$ Commented Jul 18, 2022 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
    Commented Jul 18, 2022 at 8:02
  • 1
    \$\begingroup\$ @thejonymyster ofc you can use other delimiters like \t and justify to make it more human-readable. \$\endgroup\$
    – pajonk
    Commented Jul 19, 2022 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\$ Commented Jul 19, 2022 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\$
    – naffetS
    Commented Jul 22, 2022 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\$ Commented Jul 22, 2022 at 2:52
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
    Commented Jul 24, 2022 at 15:49
  • \$\begingroup\$ @pxeger right I'll make it clear \$\endgroup\$
    – math scat
    Commented Jul 24, 2022 at 15:55
  • 1
    \$\begingroup\$ Could you detail what each program should output, supposing your code is abcd? \$\endgroup\$ Commented Jul 24, 2022 at 16:09
1
\$\begingroup\$

Find The Average String

\$\endgroup\$
20
  • \$\begingroup\$ Tag: edit-distance \$\endgroup\$
    – naffetS
    Commented Jul 28, 2022 at 23:49
  • \$\begingroup\$ string, ring can also be sring. The only other possibility for Hello and Ho is Heo. \$\endgroup\$
    – naffetS
    Commented Jul 28, 2022 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\$
    – naffetS
    Commented Jul 29, 2022 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\$
    – naffetS
    Commented Jul 29, 2022 at 0:11
  • \$\begingroup\$ @Steffan thanks \$\endgroup\$
    – Seggan
    Commented Jul 29, 2022 at 1:05
  • \$\begingroup\$ you can remove "I hand-made these, so some might be wrong" sicne I checked them with Vyxal lol \$\endgroup\$
    – naffetS
    Commented Jul 29, 2022 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
    Commented Jul 29, 2022 at 2:33
  • \$\begingroup\$ @tsh The rules state: "You may not output any of the inputs" \$\endgroup\$
    – naffetS
    Commented Jul 29, 2022 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
    Commented Jul 29, 2022 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
    Commented Jul 29, 2022 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\$
    – naffetS
    Commented Jul 29, 2022 at 15:52
  • \$\begingroup\$ @tsh Probably, the intended output would be abd with average 1, but waitnig for clarification. \$\endgroup\$
    – naffetS
    Commented Jul 29, 2022 at 15:53
  • \$\begingroup\$ @pajonk there will be no inputs without common letters. Sure, I'll stick to lowercase \$\endgroup\$
    – Seggan
    Commented Jul 29, 2022 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
    Commented Jul 30, 2022 at 6:42
  • 1
    \$\begingroup\$ From current specification, average of aaa and aaaa is... aa, aaaaa? it could be confuse to me. \$\endgroup\$
    – tsh
    Commented Jul 30, 2022 at 8:48
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
    Commented Aug 4, 2022 at 6:09
  • \$\begingroup\$ That's essentially what it outputs. \$\endgroup\$
    – bigyihsuan
    Commented Aug 4, 2022 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
    Commented Aug 4, 2022 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\$ Commented Aug 4, 2022 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
    Commented Aug 5, 2022 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
    Commented Aug 3, 2022 at 9:58
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
    Commented Aug 9, 2022 at 7:55
  • \$\begingroup\$ @mousetail I meant if x=10. I'll rephrase. Thanks \$\endgroup\$
    – user108721
    Commented Aug 9, 2022 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
    Commented Aug 9, 2022 at 16:38
  • \$\begingroup\$ @DLosc Thank you. I changed sealed to opaque. I also changed the randomness wording. Is it better now? \$\endgroup\$
    – user108721
    Commented Aug 9, 2022 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
    Commented Aug 11, 2022 at 21:11
  • \$\begingroup\$ @user Added the tag. From reading the guidance it seems code-challenge is right. \$\endgroup\$
    – user108721
    Commented Aug 11, 2022 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
    Commented Aug 18, 2022 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
    Commented Aug 18, 2022 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\$
    – naffetS
    Commented Aug 22, 2022 at 17:25
1
\$\begingroup\$

Make a Brainfuck Interpreter

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

Posted

\$\endgroup\$
0
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\$
    – naffetS
    Commented Aug 24, 2022 at 2:32
  • 1
    \$\begingroup\$ Suggested tags: test-battery, cipher, string. Related: codegolf.stackexchange.com/questions/241532/… \$\endgroup\$
    – pajonk
    Commented Aug 24, 2022 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
    Commented Aug 24, 2022 at 11:07
  • \$\begingroup\$ @pajonk Is this too similar to the related question? \$\endgroup\$ Commented Aug 24, 2022 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
    Commented Aug 24, 2022 at 18:22
  • 1
    \$\begingroup\$ you might want to ban random generators since luck can affect score \$\endgroup\$
    – okie
    Commented Sep 3, 2022 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
    Commented Sep 11, 2022 at 10:44
  • \$\begingroup\$ @xnor I've updated the function to resolve this, though it's not particularly elegant. \$\endgroup\$ Commented Sep 11, 2022 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
    Commented Sep 17, 2022 at 2:26
1
\$\begingroup\$

Calculate Pi unto a Point using the Nilakantha series

\$\endgroup\$
2
  • \$\begingroup\$ What should be the desired precision - are floating-point errors ok? Suggested tag: sequence (+adopting output rules from there). Suggestion: merge odd and even cases to one using \$(-1)^n\$ for \$n>1\$. Please make the test-cases copy-friendly (see codegolf.meta.stackexchange.com/a/8101/55372). \$\endgroup\$
    – pajonk
    Commented Sep 13, 2022 at 11:41
  • \$\begingroup\$ There you go. I've added all of that. \$\endgroup\$ Commented Sep 13, 2022 at 12:48
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\$ Commented Sep 17, 2022 at 5:23
  • \$\begingroup\$ @UnrelatedString Good idea \$\endgroup\$
    – user108721
    Commented Sep 17, 2022 at 5:28
  • 1
    \$\begingroup\$ Two downvotes?? Please explain \$\endgroup\$
    – user108721
    Commented Sep 17, 2022 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
    Commented Sep 17, 2022 at 7:57
  • \$\begingroup\$ @xnor that's a shame as the messages are what make the challenge more fun. \$\endgroup\$
    – user108721
    Commented Sep 17, 2022 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
    Commented Sep 17, 2022 at 16:37
  • \$\begingroup\$ @user it was previously "God Save the King" but I changed it on xnor's advice. \$\endgroup\$
    – user108721
    Commented Sep 17, 2022 at 16:40
1
\$\begingroup\$

Is there a area that can see the entire perimeter of a polygon

Oh no, your despotic regime has too many political prisoners and not enough guards! Time for drastic measures: Only build prisons that require only a single guard. But there are many prison design and little time. How to check?

The challenge

Given a polygon, as a list of points, determine if there is a area (where the guard can stand) that can see the entire perimeter of the polygon.

Any convex shape trivially qualifies:

pentagon

Some concave shapes qualify too:

concave shape

But not all:

concave shape where there is no place for a guard

Algorithm hint

The area where a guard can stand is the intersection of the areas on the inside of the tangent of every edge.

Test Cases

Image Points Outcome
TBD
\$\endgroup\$
1
\$\begingroup\$

Calculating Pi using the Gregory-Leibniz series unto a point

\$\endgroup\$
2
  • \$\begingroup\$ Why can't we treat \$\pi_n\$ as a sequence? Also, some test-cases would be nice. \$\endgroup\$
    – pajonk
    Commented Sep 17, 2022 at 19:27
  • \$\begingroup\$ I think this might be too similar to your earlier challenge on Nilakantha series. For instance, loopy walt's answer is already summing up the Gregory-Leibniz series then correcting it by \$\pm 1/n \$ at the end. \$\endgroup\$
    – xnor
    Commented Sep 17, 2022 at 20:35
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\$ Commented Sep 27, 2022 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\$ Commented Sep 27, 2022 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\$ Commented Sep 27, 2022 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\$ Commented Sep 27, 2022 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
    Commented Sep 27, 2022 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\$ Commented Sep 27, 2022 at 17:35
  • \$\begingroup\$ @97.100.97.109 No, it gives an error "Combo buttons cannot be used in two-digit numbers" \$\endgroup\$
    – pigrammer
    Commented Sep 27, 2022 at 17:36
  • \$\begingroup\$ @prigrammer Whoops, I was wrong. I think I'll still allow it since it makes the application marginally simpler. \$\endgroup\$ Commented Sep 27, 2022 at 18:47
1
81 82
83
84 85
157

You must log in to answer this question.

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