555
\$\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

3921 Answers 3921

1
67 68
69
70 71
131
1
\$\begingroup\$

Newton Polynomial

A newton polynomial is a interpolation polynomial where the coefficients are found using the Newton's divided differences method. The relevant Wiki is here.

Your task has two parts:

  1. Given a set of inputs and outputs to find and display the polynomial that describes the series. The input can be as two lists or a dictionary like structure. e.g. $$ [x_1:y_2,\;x_2:y_2,\;...\;, x_{n-1}:y_{n-1},\; x_n:y_n] $$
  2. Given any real number, return the interpolated value.

Examples

enter image description here

Presentation of the polynomial must be in a format that is recognisable.

As ever this is code golf: so shortest answer wins.

\$\endgroup\$
7
  • \$\begingroup\$ A summary of the method would be welcome (in addition to the Wikipedia link). From a super quick skim I think there might be errors in the final example output: shouldn't \$(n-1)(n-2)\$ be \$(n-1)(n-3)\$, and similarly \$(n-1)(n-2)(n-3)\$ be \$(n-1)(n-3)(n-7)\$? \$\endgroup\$
    – Dingus
    Oct 12, 2021 at 4:49
  • \$\begingroup\$ computers don't use real numbers. but still an interesting challenge. do you care what format the output polynomial is in? \$\endgroup\$
    – don bright
    Oct 18, 2021 at 3:14
  • \$\begingroup\$ @Dingus thanks, yes working on a summary of the method, wanting to keep it consice though. no every term is included so '(n-1)(n-2)(n-3) etc. \$\endgroup\$
    – george
    Oct 18, 2021 at 20:44
  • \$\begingroup\$ @donbright true, but I haven't had time to look into using complex numbers. I'm currently not interested in using them for this. Id want the polynomial to be readable, what did you have in mind? \$\endgroup\$
    – george
    Oct 18, 2021 at 20:47
  • \$\begingroup\$ no i mean, "given any real number" should be something like "given a 32 bit floating point number in your languages format". as far as the polynomial format i was wondering if you would accept it all expanded out to \$a_nx^n + a_{n-1}x^{n-1}...a_0\$ form, to the point where it can be represented as an array of numbers, the numbers in the array are coefficients and the position in the array is the exponent. thanks. \$\endgroup\$
    – don bright
    Oct 19, 2021 at 2:09
  • \$\begingroup\$ @donbright ah I see what you're saying, yes I will amend that then. I'm not sure I quite understand how you want to layout it out. Maybe expecting a particular format is too hard and I should just ask for an array of coefficient, were you thinking of expanding (n-1)(n-2)(n-3)... for example? \$\endgroup\$
    – george
    Oct 19, 2021 at 23:06
  • \$\begingroup\$ yes the final result should be a polynomial, would it be ok to return a string saying 23.4n^4 + 3920n^3 ... \$\endgroup\$
    – don bright
    Oct 20, 2021 at 2:32
1
\$\begingroup\$

Wave square

Task

Given an integer \$n\$ with the constraints \$0 < n \leq 9\$, output the corresponding square, that for each row shifts the sequence from \$1\to n\$ by one, overflowing when needed.

I/O

Input is an integer \$n\$, \$ 0 < n \leq 9\$. Output can be as a returned String, matrix, array or to STDOUT. You can write a full program or a function.

Examples

5:

12345
23451
34512
45123
51234

2:

12
21

1:

1

9:

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

meta

Thoughts on extending the challenge to allow for inputs bigger than 9, which would then just be taken mod 10?

\$\endgroup\$
2
  • 3
    \$\begingroup\$ One idea - using letters for numbers greater than 9 (i.e a for 10, b for 11, etc.) would allow for inputs of up to 35 without disrupting the format. \$\endgroup\$
    – Dingus
    Oct 18, 2021 at 2:33
  • \$\begingroup\$ Thanks! I don't know if that'd be enough to make it distinct from another challenge though (someone posted it was a dupe in the nineteenth byte) \$\endgroup\$
    – 0xff
    Oct 18, 2021 at 8:22
1
\$\begingroup\$

Input two positive integers m, n; Output a grid looks like below:

┌──────────────┐
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
└──────────────┘

Here is an example for 5×4 grid.

Characters used in the grid is shown as this table:

Char Code Point
Space U+0020
U+2500
U+2502
U+250C
U+2510
U+2514
U+2518
U+251C
U+2524
U+252C
U+2534

You may alternative use a CJK space   (U+3000) instead of two ASCII spaces (U+0020 U+0020). If you chose this option, you should use a single horizontal grid line (U+2500) instead of two. You may verify this behavior in the code snippet at bottom.

You may output:

  • a single string
    • an array of characters, an array of integers (whose value is the code point of each character);
  • an array of strings, as the single string split by new lines;
    • or an array of array of characters, an array of array of integers;

Use ASCII Space:

<pre lang="en">┌──────────────┐
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
├──┬──┬──┬──┬──┤
│  │  │  │  │  │
├──┴──┴──┴──┴──┤
└──────────────┘</pre>

Use CJK Space:

<pre lang="zh">┌─────────┐
├─┬─┬─┬─┬─┤
│ │ │ │ │ │
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│ │ │ │ │ │
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│ │ │ │ │ │
├─┴─┴─┴─┴─┤
├─┬─┬─┬─┬─┤
│ │ │ │ │ │
├─┴─┴─┴─┴─┤
└─────────┘</pre>

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

Calculate Smith normal form of an integer matrix

Given an \$m \times n\$ matrix of integers A, there exist a \$m \times m\$ matrix P, an \$m \times n\$ matrix D, and an \$n \times n\$ matrix Q such that:

  • P and Q are unimodular matrices (i.e. matrices which are invertible and whose inverses are also integer matrices);
  • D is diagonal;
  • each diagonal entry \$d_{ii}\$ of D is nonnegative; and
  • \$d_{11} \mid d_{22} \mid \cdots \mid d_{nn} \$.

Furthermore, the matrix D is unique in this representation.

One common way to calculate D is via an algorithm that looks like a combination of the Euclidean algorithm for calculating gcd and Gaussian elimination -- applying elementary row and column operations until the matrix is in the desired format for D. Another way to calculate D is to use the fact that for each i, \$d_{11} d_{22} \cdots d_{ii}\$ is equal to the gcd of all determinants of \$i\times i\$ submatrices (including non-contiguous submatrices) of A.

The challenge

You are to write a function or program that calculates the Smith normal form of an input matrix. The output may either be in the form of the full matrix D, or in the form of a list of the diagonal entries of D. In an imperative programming language, it is also acceptable to write a function that takes a matrix by reference and mutates the matrix into its Smith normal form.

Rules

  • This is code-golf: shortest code wins.
  • Standard loophole prohibitions apply.
  • You do not need to worry about integer overflow, if that applies in your language.

Examples

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

6  10       1 0
10 15  ->   0 10

6 0  0        1 0  0
0 10 0   ->   0 30 0
0 0  15       0 0  30

2 2       2 0
2 -2  ->  0 4

2 2  4 6       2 0 0 0
2 -2 0 -2  ->  0 4 0 0

Note: Mathematica already has a built-in to calculate Smith normal form. As such, you can use this to play around with test cases: Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Three new matrices are introduced at the top of the post and it isn't immediately obvious which one is the Smith normal form. Suggest stating that it's D after the first set of bullet points. \$\endgroup\$
    – Dingus
    Nov 9, 2021 at 23:34
1
\$\begingroup\$

Climbing up slippery stairs

Challenge

You're standing in front of a stairway with \$n\$ stairs in total. (If you label each staircase \$1,\cdots,n\$, the starting point counts as the 0th staircase.) You can climb up \$1,2,\cdots,k\$ stairs at a time. But some stairs are slippery; if you step on it, it will cause you to slip backwards until you stand on a non-slippery one (or the starting point). In how many ways can you get to the \$n\$th staircase with exactly \$s\$ steps?

Task: Given the list of staircases of length \$n\$ marked with either "slippery" or "non-slippery" (you can choose any two consistent values) and the values of \$k\$ and \$s\$, answer the above question.

The \$n\$th staircase is guaranteed to be non-slippery, and you cannot move further than the \$n\$th. This implies that reaching the destination before you spend \$s\$ steps doesn't count.

For example, if the stairway is [non-slippery, slippery, non-slippery] and \$k=2\$, two possible first steps (climbing one or two stairs) will result in the same position (the first staircase), but count as two distinct possible moves. And if you try to climb one stair as the second step, you will end up not moving at all, but it still counts as a step.

You may assume \$1 \le k \le n\$ and \$s \ge 1\$. Some inputs may have no way to reach the destination at all; in that case, your code should output the value of zero for any value of \$s\$.

Example and test cases

N means non-slippery, and S means slippery. 1-1-3 notation means that you can reach the top in three steps, trying to advance 1, 1, and 3 stairs at once.

N = [N, S, N, N]
k = 3
s = 1: answer = 0 (no way to climb 4 stairs at once)
s = 2: answer = 3 (1-3, 2-3, 3-1)
s = 3: answer = 4 (1-1-3, 1-2-1, 2-1-3, 2-2-1)

N = [S, S, N, S, S, N]
k = 4
s = 1: answer = 0
s = 2: answer = 2 (3-3, 4-3)
s = 3: answer = 8 (1-3-3, 1-4-3, 2-3-3, 2-4-3, 3-1-3, 3-2-3, 4-1-3, 4-2-3)

More test cases coming soon.

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

⧵begin{alignat} ... ⧵end{alignat}

Note: The title intentionally uses &#10741; (reverse solidus operator) instead of plain backslash, because otherwise MathJax would happily translate the entire title to... uh... a MathJax error box.

Background

\begin{alignat}{n} ... \end{alignat} is a lesser known LaTeX/MathJax block that allows aligning multiple parts of multi-line equations.

\begin{alignat}{5}
A&=&B&\\
 & &B&=&C&\\
 & & & &C&=&D&\\
 & & & & & &D&=&E
\end{alignat}

\begin{alignat}{5} A&=&B\\ & &B&=&C&\\ & & & &C&=&D&\\ & & & & & &D&=&E \end{alignat}

\begin{alignat}{5}
x&=&-3&a&-&2&b\\
y&=& 2&a&+& &b
\end{alignat}

\begin{alignat}{5} x&=& 3&a&-&2&b\\ y&=&-2&a&+& &b \end{alignat}

Challenge

Implement "Poor Man's ASCII-Only Alignat", which tries to replicate the behavior of MathJax but in plain text. The spec of PMAOA is as follows:

  • Let's define a "word" to be each part of a line delimited by the & character. A word can be empty, and the parts before the first & and after the last & also count as words.
  • Given a multi-line string input, identify the 1st, 2nd, 3rd, ... word of each line.
  • Right-align the 1st words of all lines, right-align the 2nd words of all lines, ..., and concatenate the aligned blocks horizontally. Padding is done with minimal amount of space characters. Trailing whitespace at the end of each line is optional.

Standard rules apply. The shortest code in bytes wins.

Test cases

Coming soon.

\$\endgroup\$
2
  • \$\begingroup\$ By saying align, is extra spaces allowed? For example, `"a&b\ncd&e" -> "..a..b\n.cd..e" \$\endgroup\$
    – tsh
    Nov 9, 2021 at 10:02
  • \$\begingroup\$ @tsh No, the padding should be minimal. \$\endgroup\$
    – Bubbler
    Nov 9, 2021 at 10:14
1
\$\begingroup\$

What is the maximum value generated by interleaving?

INTERCAL has an interleave operator which does the following operation. Let left operand be asdf and right one qwer in binary, respectively. The operation produces a binary value aqswdefr.

INTERCAL internally treats data as unsigned integers, so the value of the eight-bit value represents 0 to 255 in decimal, inclusively.

If one operand has fewer bits than the other, the fewer one gets padded with zero before operation. So, asd interleaving with qwer is equal to 0asd interleaving with qwer, which is 0qawsedr: it represents 0 to 127 in decimal.

Also, INTERCAL has an extension that handles any bases. Let's assume if 3-base numbers are handled. If each operand has 1 and 3 digits respectively, the maximum value for each operand is represented as 2 and 222 in 3-base number, respectively. Interleaving them results in 020222, which is 188 in decimal.

Task

Given an input of three unsigned integers, output the largest possible value generated by interleaving. The three integers are: number of digits for left operand, number of digits for right operand, and in what base those operands are described with.

Restrictions

  • Base shall be 2 or greater.
  • Each operand has at least 1 digit.

Rules

  • In either function or a program.
  • Standard I/O rules apply, as long as every input and output value is represented as same base or same representation.
    • So varying output base is not allowed.
  • If input is represented as a list-like format, any orders of arguments or input values are fine.
  • No standard loopholes.
  • Shortest code wins

Test cases

TODO.

meta

  • Am I missing any appropriate tags yet?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The I/O rules seem fine. I'd suggest changing the title to something like 'What is the maximum value generated by interleaving?' Also, 'output what the possibly largest value interleaving generates' -> 'output the largest possible value generated by interleaving'. \$\endgroup\$
    – Dingus
    Nov 12, 2021 at 4:14
1
\$\begingroup\$

Constructing Solar Panels from Squares part 2

Thanks to all your generous contributions of code, my horde of minions can now precisely calculate how to construct solar panels of any size, but there's a problem.

The logistics department used these results to calculate how many square panels they would need for every size up to 1,000,000, which is way too many panels. As it turns out, larger panels are more expensive than cheaper ones, so I've decided we need to try to use the largest square panels we can wherever possible.

To make matters worse, my team of scientists tell me that we should avoid using multiple panels of the same size in our configuration, except for our tiny 1x1 panels, to make sure the panels don't fall apart.

The Challenge

Given a positive integer n, output a list of square numbers that sums to n containing the largest squares possible such that no square number other than 1 appears multiple times.

A square number is any integer that is the result of multiplying an integer by itself. For example 16 is a square number because 4 x 4 = 16 This is A000290

For example: For n = 12, you could achieve the desired size with 4 panels of sizes [9, 1, 1, 1]. As 9 is the largest square possible in this configuration, this is the best answer. For n = 13, you can achieve the desired size with only 2 panels: [9, 4]

If n is a square number, the output should be [n].

Input

A positive integer n representing the total desired surface area of the solar panels. Note that 0 is not positive.

Output

A list of square numbers that sums to n containing the largest squares possible.

Testcases

1 -> [1]
2 -> [1,1]
3 -> [1,1,1]
4 -> [4]
7 -> [4,1,1,1]
8 -> [4,4]
9 -> [9]
12 -> [9,1,1,1]
13 -> [9,4]
18 -> [16,1,1]
30 -> [25,4,1]
50 -> [49,1]
60 -> [49,9,1,1]
70 -> [64,4,1,1]
95 -> [81,9,4,1]
300 -> [289,9,1,1]
1246 -> [1225,16,4,1]
12460 -> [12321,121,16,1,1]
172593 -> [172225,361,4,1,1,1]

Sandbox

I don't think this challenge is similar enough to part 1 to be considered a dupe, as while some answers from part 1 could be trivially modified to work for part 2, they would likely be out-golfed by better approaches.

That said I'm not sure how well-worded the output requirement is. a list of square numbers that sums to n containing the largest squares possible such that no square number other than 1 appears multiple times. feels poorly worded, but I'm not sure how I could word it better.

\$\endgroup\$
7
  • \$\begingroup\$ The challenge is unclear. I think you copied part 1 but forgot to edit testcase and example of challenge \$\endgroup\$
    – okie
    Nov 17, 2021 at 1:04
  • 1
    \$\begingroup\$ such that no square number other than 1 appears multiple times - test cases don't agree. \$\endgroup\$
    – pajonk
    Nov 17, 2021 at 5:24
  • \$\begingroup\$ I did generate new testcases when I wrote this, but I guess I messed up when putting them in. I'll re-run and update the testcases now \$\endgroup\$
    – Mayube
    Nov 17, 2021 at 22:15
  • \$\begingroup\$ 8->4,4 having 2 4 \$\endgroup\$
    – okie
    Nov 18, 2021 at 0:43
  • \$\begingroup\$ Am not sure if this question may be solved by modify the previous one trivially. But there would be many answer be very similar though. I'm not sure if it would be a duplicate to that one in such case. \$\endgroup\$
    – tsh
    Nov 18, 2021 at 3:59
  • \$\begingroup\$ @okie yeah, the problem is with the wording of the challenge, not the testcases. Not sure how best to word it... \$\endgroup\$
    – Mayube
    Nov 18, 2021 at 14:07
  • \$\begingroup\$ So only the largest and 1 can appear multiple time? \$\endgroup\$
    – okie
    Nov 18, 2021 at 23:27
1
\$\begingroup\$

Implement Unix Timestamp to Daytime

Given an unsigned integer that represents a timestamp since 1970/01/01 00:00:00 (which is Unix epoch time), output one of these to represent the daytime in GMT timezone:

  • An array that stores year, month, date, hour, minute, second.
  • A string in format YYYYMMDDHHmmss.
  • Or whatever similar, as long as it complies with standard i/o rules.

Rules

  • Implement the function or the full program from vanilla.
    • So no built-ins nor libraries that has the fuctionality (see next section).
  • Implement leap year, too; but don't leap second (although leap second is not supported).
  • You just need to support up to 2038/01/19 (so input range shall be 0 to 2147483647 (inclusive)).
  • Standard loopholes apply.
  • Standard I/O rules apply.
  • Input and output format should be consistent and not ambiguous.
    • So, for example, if output is a string like 1970121000, it's unqualified, as it can be recognized as 1970/01/21 00:00:00, 1970/12/01 00:00:00, or 1970/01/02 10:00:00.
  • Shortest code wins.

Examples of bad answers

Test cases

0
-> 1970/01/01 00:00:00
999999999
-> 2001/09/09 01:46:39
1145141919
-> 2006/04/15 22:58:39
1330500000
-> 2012/02/29 07:20:00
1633773293
-> 2021/10/09 09:54:53
2147483647
-> 2038/01/19 03:14:07

Hint

Here are implementations:

Related problems

Meta

  • I once posted here but it's closed.
  • TODO. define what builtins are.
    • The most problem is that that KSH answer has a function that directly converts to the objective string; should I prohibit it?
  • Maybe I wanted to say no date objects allowed.
  • Is what is so-called date object ambiguos?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Unix Timestamp does not support leap seconds. So there is nothing to do to require someone implement leap second support for an Unix Timestamp. \$\endgroup\$
    – tsh
    Oct 12, 2021 at 6:28
  • 1
    \$\begingroup\$ Am I required to support year above 2038? As, you know, support only 1970~2038 would avoid some leap year issues for 2100 or 2200. \$\endgroup\$
    – tsh
    Oct 12, 2021 at 6:31
  • \$\begingroup\$ @tsh 1. Thank you for pointing out leap seconds. 2. I clarified to support until 2038. \$\endgroup\$
    – user100411
    Oct 12, 2021 at 12:27
1
\$\begingroup\$

Permutation of all the number which separated by ':' and ','

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf and thanks for using the Sandbox! This is a great challenge, but as it stands it's a little unclear from the instructions what's being asked. For example it's clear from the example that 1-2,11,44:110-113 means output every permutation of 1,2,11,44 on the left column and 110,111,112,113 on the right column, but that's not explained in the instructions. \$\endgroup\$
    – Mayube
    Nov 12, 2021 at 20:52
  • \$\begingroup\$ @Mayube Thanks for your comment, I've updated the instructions. \$\endgroup\$
    – obnews
    Nov 12, 2021 at 22:02
1
\$\begingroup\$

Print random characters indefinitely

Task


Continuously print a random character (a-z, A-Z, 0-9) not separated by a newline (\n).

Expected output


b7gFDRtgFc67h90h8H76f5dD55f7GJ6GRT86hG7TH6T7302f2f4 ...

Note: output should be randomised.

Requirements/Rules


  1. Output must be continuous (i.e. never ending),
  2. Output may not comprise of newlines,
  3. Output must be random,
  4. Output must be only composed of characters: a-z, A-Z, 0-9.
  5. No loopholes, regarding programming language version(s). Use only the tools available with that programming language, no third-party packages, modules, or other addons.

Points


  • Smallest file size (in bytes)

Notes

Concerns: None at the moment...

\$\endgroup\$
9
  • 1
    \$\begingroup\$ I think this would count as a duplicate of this. It's a language specific version, and indefinite, but making something loop forever isn't really the hard part of the challenge I think. \$\endgroup\$
    – Riker
    Nov 29, 2021 at 0:51
  • \$\begingroup\$ @Rɪᴋᴇʀ no, not because different. \$\endgroup\$
    – Fmbalbuena
    Nov 29, 2021 at 0:51
  • 1
    \$\begingroup\$ Is "creativity" part of the scoring? If so, there's no way to objectively determine how creative something is, so you can't use that as a scoring criterion. You should probably clarify Python 3.8 is the only allowed language, or just drop that entirely (which I'd strongly recommend). \$\endgroup\$ Nov 29, 2021 at 0:52
  • 1
    \$\begingroup\$ @RedwolfPrograms and Riker thank you for the tips, i'll make the suggested edits to the criterias ASAP. \$\endgroup\$ Nov 29, 2021 at 0:57
  • 1
    \$\begingroup\$ Not limited to python, this might be different enough. I consider something a duplicate if the more specific challenge doesn't really encourage any different approaches than whatever worked for the previous ones, but limiting to alphanumeric and forcing an infinite stream is probably good. You should probably check if there's any other ones tagged [random] that look too similar though. \$\endgroup\$
    – Riker
    Nov 29, 2021 at 0:59
  • \$\begingroup\$ @Rɪᴋᴇʀ Understood. Thanks again! \$\endgroup\$ Nov 29, 2021 at 1:01
  • 1
    \$\begingroup\$ No problem! It's an interesting challenge, and if it really hasn't been done before then I think it would be quite fun to do. \$\endgroup\$
    – Riker
    Nov 29, 2021 at 1:13
  • \$\begingroup\$ Ok! Will post this in ~22 hours... \$\endgroup\$ Nov 29, 2021 at 1:16
  • \$\begingroup\$ We've had similar versions of this challenge before, and they've all been closed as a dupe of this and/or this. Personally, I would hammer this closed as a dupe of those two, as I don't think this adds anything that they don't - it's just a trivial combination of the two \$\endgroup\$ Nov 29, 2021 at 1:20
1
\$\begingroup\$

Largest SKI Reduction in under 100 characters

The challenge

Create a program in SKI Combinator Calculus in under 100 characters that produces the largest result after terminating.

Scoring

The score will be the number of characters in the final reduction. The highest is the winner.

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

Fully matched numbers

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

Convert superscript numbers to normal numbers

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Maybe specify exactly what characters will be included in the input? \$\endgroup\$
    – emanresu A
    Dec 11, 2021 at 22:02
  • \$\begingroup\$ @emanresuA Done \$\endgroup\$
    – Ginger
    Dec 12, 2021 at 0:05
1
\$\begingroup\$

Posted here

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

Rotate two differently cased subwords independently

You have one string made of two subwords in different cases, the upper case first, then the lowercase:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

And you must return each subword cycled by a given increment. (N.b. the letters aren't rotated through the alphabet, but each character is shifted in the word)

The subwords are not always the same length as each other, and are part of the same 'data' structure. If your language cannot store strings, you're permitted to store the 'string' in a single array, e.g. ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

Here are the test cases:

Input Output
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", 13 'NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm'
"ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyzabcdefghijklm", 13 'NOPQRSTUVWXYZABCDEFGHIJKLMabcdefghijklmnopqrstuvwxyz'
"ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyz", 26 'ABCDEFGHIJKLMNOPQRSTUVWXYZopqrstuvwxyzn'
"ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyz", 13 'NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyz'
"ABCnopqrstuvwxyz", 2 'BCAyznopqrstuvwx'
"AAABBBcccddd", 2 "BBAAABddcccd"
"AAABBBcccddd", 6 "AAABBBcccddd"
"HELLOworld", 5 'LLOHErldwo'
"CODEgolf", 0 'CODEgolf'

Here is an ungolfed example program:

const subWordRotate = (original, rot) => [...original.split(/([A-Z]+)(?![A-Z][a-z]+)/)].map(list => [, ...list].reduce((memo, char, index, input) => {
  memo = memo.slice(0, input.length);
  memo.splice((index + rot) % (input.length), 1, char);
  return memo
}, Array(original.length).fill('')).join('')).join('')


const testCases = [
  ["ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", 13],
  ["ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyzabcdefghijklm", 13],
  ["ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyz", 26],
  ["ABCDEFGHIJKLMNOPQRSTUVWXYZnopqrstuvwxyz", 13],
  ["ABCnopqrstuvwxyz", 2],
  ["AAABBBcccddd", 2],
  ["AAABBBcccddd", 3],
  ["AAABBBcccddd", 4],
  ["AAABBBcccddd", 5],
  ["AAABBBcccddd", 6],
  ["AAABBBcccddd", 7],
  ["AAABBBcccddd", 8],
  ["AAABBBcccddd", 9],
  ["AAABBBcccddd", 10],
  ["HELLOworld", 69],
  ["CODEgolf", 0]
]
testCases.forEach(
    testCase => console.log(`original: ${testCase[0]}, rotated by ${testCase[1]}: ${subWordRotate(...testCase)}`)
  );


Sandbox note: I think there is a bug in my code, such that ["AAABBBcccddd", 6],["AAABBBcccddd", 7], return the same values. I think this is the same bug that is preventing me specifying how negative numbers work. Any help fixing the code would be much appreciated

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

The Most Wanted Prime Numbers

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

Can we patch the corona certificate validation code (part 1/3)?

The new chancellor of Germany, Mr. Olaf Scholz, is in deep trouble: the Covid app does not show the vaccination status correctly beginning with booster vaccinations. He was not involved in the development of the app, since that was under chancellor Angela Merkel. He is now hiring you, Secret Agent 0x007, in order to understand the problem and later apply a strategy to fix the problem.

In step 1, Mr. Scholz wants to understand how the app has worked correctly when booster vaccinations were not even thought of. Mr. Scholz is an important person, so he has no time to read lengthy source code. Your code has to be .

These are the rules of valid vaccinations:

  • There are 4 vaccination types in Germany: BioNTech (B), Moderna (M), Astra Zeneca (A) and Johnson&Johnson (J).
  • A person is considered vaccinated 14 days after the necessary amount of injections.
  • Biontech, Moderna and Astra Zeneca need 2 injections, Johnson needs 1 injection only.
  • If 2 injections are needed, the second injection may occur earliest 28 days after the first injection.
  • If 2 injections are needed, the second injection may only be with the same vaccination type.
  • You get an entry in your vaccination pass which has the date in the format YYMMDD. COVID-19 is all post 2000, so we never need a 4 digit year.
  • A full entry is in the form YYMMDD X followed by a newline, where X is the vaccination type.

How the application works:

You get the input in a reasonable form, e.g.

  • from stdin, separated by newlines of your platform
  • an array of strings (like argv)
  • a function with variable number of arguments (like ...)

The first line/entry is today's date, which you check the validity against. This comes from a time server, so it's always valid. Each following line/entry is for one injection. There may be many of them, mainly limited by your platform (254 is certainly enough, also for part 2 and 3).

The application gives the following output:

  • injected after a successful injection with the 14 days period not over
  • vaccinated 14 days after the necessary amount of injections
  • manipulated in case things do not match

manipulated takes precedence over vaccinated over injected. The output may contain arbitrary leading or trailing whitespace. A newline is not needed (it will be displayed in a mobile phone app textbox anyway).

The output can be

  • on stdout
  • the return value of the function

As there are quite some anti-vaxxers, the application checks for manipulations.

  • Totally invalid vaccination types (like Y)
  • Mix of vaccination types for the first and second injection
  • More injections than needed
  • Invalid date (like 200231 - there is no February 31st)
  • Date too early (earlier than 200101, the beginning of the pandemic)
  • Injection date later than today
  • Injections in wrong order (second date before first date)

You don't need to consider:

  • dates other than 6 digits
  • characters in the date other than 0-9
  • other character than space as the separator
  • more than 1 character as vaccination type

Test cases:

<any date>
200231 X
= manipulated (invalid vaccination type)

<any date>
210301 B
210329 A
= manipulated (different vaccination types)

<any date>
210301 B
210329 B
210426 B
= manipulated (too many injections)

210814
210301 J
210814 J
= manipulated (too many injections)

<any date>
200231 B 
= manipulated (invalid date February 31st)

<any date>
191231 B 
= manipulated (date earlier than the pandemic)

210301
210302 J
= manipulated (date of the injection is tomorrow)
 
210301
210301 J
= injected (14 days not over)

210315
210301 J
= vaccinated (14 days over, only 1 injection needed)

210315
210301 B
= injected (14 days over, but 2 injections needed)

<any date>
210301 B
210302 B
= manipulated (28 days between 2 injections required)

210331
210301 B
210329 B
= injected (28 days between 2 injections, but not 14 days after the last one)

210412
210301 B
210329 B
= vaccinated (28 days between 2 injections, 14 days after the last one)

210412
210329 B
210301 B
= manipulated (injections in wrong order)

About realism: while this challenge has a realistic background, not all vaccination of rules in Germany are considered. Do not claim that your program can calculate the validity of a COVID-19 vaccination certificate.

Coming up:

  • part 2, in which you need to consider booster vaccinations the wrong way
  • part 3, in which you check whether you can patch the wrong code of part 2 to make it work correctly

I would appreciate if you participate in all 3 parts.

\$\endgroup\$
5
  • \$\begingroup\$ Regarding the process: I will start writing part 2 when I have received feedback on part 1. I will start writing part 3 when I received feedback on part 2. I want to release part 1 not before all 3 parts were reviewed. Would that be fine? \$\endgroup\$ Dec 18, 2021 at 21:06
  • \$\begingroup\$ Interesting question, and I like it. The only thing that really sticks out to me is the input format, you should probably clarify before anybody asks - can you take input as an array/list of strings, rather than a newline delimited string? i.e. ["a", "b"] instead of "a\nb". It really doesn't matter much which you pick but since newline delimited strings would take more bytes for most langs, it's probably going to get asked immediately. \$\endgroup\$
    – Riker
    Dec 18, 2021 at 21:24
  • \$\begingroup\$ @Riker: thank you for the feedback. Yes, if that's a common thing to have for input, that's totally fine. Is there an example for a formulation considering all the common inputs? \$\endgroup\$ Dec 18, 2021 at 21:26
  • 1
    \$\begingroup\$ I'm unsure if it counts as common, but yeah - it's just that indexing an array is probably shorter than calling .split("\n") for many languages, lol. Regarding posting 3 challenges, I think it's worthwhile to sandbox all 3 before posting any of course, but then posting maybe each one on sunday or something for 3 weeks would be fun. Somebody in chat compared it to a mini advent of code (golf) :) \$\endgroup\$
    – Riker
    Dec 18, 2021 at 21:29
  • \$\begingroup\$ I implemented this challenge (non-golfed) and all test cases work. I'll start working on the next one now. \$\endgroup\$ Dec 27, 2021 at 15:22
1
\$\begingroup\$

Fuzzy friends

Introduction

Congratulations! You've been selected to do research a a newly discovered animal called a fuzzy, a docile, simple creature that strongly resembles a cotton ball. Fuzzies love to be near other fuzzies, but not all fuzzies want to be near each other.

There are 6 types of fuzzies, 1a, 1b, 2a, 2b, 3a, and 3b. Each obeys different rules.

  • Type 1a fuzzies want to be near any type b fuzzy. (vice versa for 1b)

  • Type 3a fuzzies want to be near any type a fuzzy. (vice versa for 3b)

  • Finally, type 2 fuzzies want to be near any fuzzy type, a or b.

  • Perfect pairings are matches in which both fuzzies want to be near each other (ex. 1a and 1b)

  • Semiperfect pairings are matches in which only one fuzzy wants to be near the other (ex 3a and 1b)

  • Imperfect pairings are matches in which neither fuzzy wants to be with the other (ex. 3a and 3b)

Your Challenge

Given a list of fuzzies:

  1. Output the total number of perfect pairings. If there are any left:
  2. Output the number of semiperfect pairings. If there are any left:
  3. Output how many leftover bachelors there are.

Output and input format don't matter as long as you state them both.

Test cases

1a, 1b:
1a and 1b are a perfect match
> 1 perfect, 0 semiperfect, 0 bachelors
1a, 2b, 2a, 3b:
1a and 2b are a perfect match
2a and 3b are a semiperfect match
> 1 perfect, 1 semiperfect, 0 bachelors
1a, 1b, 2a, 3a, 3b, 3b:
1a and 1b are a perfect match
2a and 3a are a perfect match
3b and 3b are an imperfect match
> 2 perfect, 0 semiperfect, 1 bachelor
1b, 2a, 3a
1b and 2a are a perfect match
3a is left over
(note: could also be:
2a and 3a are a perfect match
1b is left over
for the same result)
> 1 perfect, 0 semiperfect, 1 bachelor

Scoring

This is , so shortest in bytes wins.

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

Make a negative afterimage

We've all seen the strange, inverted-color images of the American Flag or similar that look correct after you stare at them for a minute and look at a white object. These are called negative afterimages.

Your Challenge

Given an image as input, your program should return that same image, recolored to create a negative afterimage. To do this, simply invert each color in the image. Your program may take either raw image data or a path to an image file as input, and either create a new image file or display the inverted image as output.

Scoring

This is code-golf, so shortest answer wins.

\$\endgroup\$
2
  • \$\begingroup\$ What does inverted-color mean? For example, if input color is pink, should I output darkred, darkgreen or lightgreen? \$\endgroup\$
    – tsh
    Dec 23, 2021 at 8:23
  • \$\begingroup\$ How many colors should I support at least. Is a program only support black-white image acceptable? Or what about 16 color image? \$\endgroup\$
    – tsh
    Dec 23, 2021 at 8:24
1
\$\begingroup\$

Loading Circle Animation

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think it would be simpler if a program was just required to output eight frames, then stop. The infinite looping is unnecessary. (I think it's fine how it is) \$\endgroup\$
    – Wezl oOvOo
    Oct 28, 2021 at 1:45
  • \$\begingroup\$ For example, someone submit a progrom like this: while True: print(".#\n#\n#..#\n.##);clearScreen();print(.##\n#\n#\n.##);clearScreen()... The program try to print a frame, and then clear the screen immediately. It in theory output each frame one by one. But user would be hard to distinguish each frames. Also, if you try to take a screenshot, most time you will got an empty screen (suppose clearScreen would be much slower than print). Is this still a valid answer? \$\endgroup\$
    – tsh
    Nov 4, 2021 at 8:03
  • \$\begingroup\$ @tsh Yes, as long as the user can tell what the animation is. \$\endgroup\$
    – Yousername
    Nov 12, 2021 at 22:59
1
\$\begingroup\$

Shuffle a subsequence

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

Pluralize a Noun List

Currently Closed

\$\endgroup\$
7
  • \$\begingroup\$ Can you change dropbox to github? \$\endgroup\$
    – Fmbalbuena
    Jan 3 at 3:17
  • \$\begingroup\$ I can see if I can do that. Got some other big changes this thing probably needs though. \$\endgroup\$
    – Romanp
    Jan 4 at 4:02
  • \$\begingroup\$ most users use Github \$\endgroup\$
    – Fmbalbuena
    Jan 4 at 4:03
  • \$\begingroup\$ Got it. I realized that my lists of words were not particularly accurate, so as soon as I get better ones, I will switch to Github. \$\endgroup\$
    – Romanp
    Jan 5 at 12:58
  • \$\begingroup\$ The link example fakehtpps://python.org can be [link](fakehtpps://python.org) \$\endgroup\$
    – Fmbalbuena
    Jan 5 at 15:03
  • \$\begingroup\$ test-battery would be a good tag for this, I think \$\endgroup\$
    – user
    Jan 12 at 1:45
  • \$\begingroup\$ Now that this is posted, could you edit it down to a stub and delete it? \$\endgroup\$ Jan 12 at 3:05
1
\$\begingroup\$

Minimal Randomness

In this challenge, you take input and shuffle the letters in a random, non-deterministic way which minimizes the probability that the output is different from the input.

Rules

  1. Your program must take input and use only substitution and transposition to randomly modify the input.

  2. There must be a slight, non-zero probability that the output differs from the input.

  3. Your program is graded based on the probability of its output differing from the input, with a lower probability being better.

  4. If two programs are tied in score, the tie is settled by the code size, with a shorter code being better.

  5. Your program must be non-deterministic.

Meta

I'll post this to main soon unless there are any issues with it.

\$\endgroup\$
3
  • \$\begingroup\$ don't post it to main right away, wait for feedback and upvotes \$\endgroup\$ Jan 13 at 22:59
  • 1
    \$\begingroup\$ yeah. That's what I meant, sorry if it sounded like "if nobody looks at this, it must be amazing!" \$\endgroup\$
    – Binary198
    Jan 14 at 15:52
  • \$\begingroup\$ Seem a busy beaver and shuffle/next_permu, assuming it's possible to return differ \$\endgroup\$
    – l4m2
    Jan 18 at 13:00
1
\$\begingroup\$

Short programs for fixed outputs

Inspired by Lynn's Jelly puzzles. Check them out if you're interested in practicing your Jelly skills

Cops

The cops should choose three things:

  • A freely available programming language,
  • a byte count \$B\$, and
  • a number of programs to write, \$n\$ (minimum 5)

They should then write \$n\$ programs, each of which:

  • is exactly \$B\$ bytes long, and

  • outputs a fixed, non-empty, non-whitespace output. That is, the output should contain at least one non-whitespace character. "Fixed" can mean that either:

    • it outputs the same thing no matter what input is provided, or
    • that it always outputs the same thing and takes no input.

    You may choose which of these meanings to take, but it must be the same for all \$n\$ programs. Please mention which of these options your programs use.

The cops should then reveal the following bits of information:

  • The programming language used,
  • the byte count \$B\$,
  • any command line flags used for specific outputs,
  • the \$n\$ outputs for each of the \$n\$ programs. If the outputs use any non-printable ASCII characters, please include a hexdump of the output.

The Robbers will be attempting to find \$B\$ byte long programs that output the same outputs, so you should keep your programs secret.

For example, if you choose to write 7 programs in Python, each of them 10 bytes, that output

4, True, 2 3 , 1, 72, ! and [0]

then you may have these 7 programs (one per line).

Robbers will crack one of your \$n\$ outputs if they can find any \$B\$ byte program in your language that has the same output. Note that the program does not have to be the same as the cop's program.

Any outputs that go a week without being cracked can be marked safe, and the programs for each output should be revealed. Until the program is revealed for a specific output, it can still be cracked.

You may post multiple answers, but each answer should be independent from all others. Your score is equal to the total number of safe outputs across all your answers. The user with the highest score wins.

Robbers

You should find a Cops answer with at least one uncracked, unsafe output, and attempt to crack any of the outputs. That is, find a program that is exactly \$B\$ bytes long that outputs the same fixed output. Note that your program does not have to be the same as the Cop's original answer, just that the output has to be equal.

If you crack an answer, please do the following:

  • Leave a comment on the Cop's answer, linking to either your answer or a TIO (or similar) link demonstrating the crack
  • If this is your first crack, post an answer to the Robbers thread with your crack, linking to the relevant Cop answer
  • For further cracks, edit them in to your existing answer, linking to the relevant Cop answer

A Robber's score is equal to the total number of cracks they make. The Robber with the highest score wins.


Meta

\$\endgroup\$
1
  • \$\begingroup\$ Other than the original inspiration, is there any reason to have multiple tasks in one cop submission? Since they're not related to each other and each one can be cracked individually, it seems like they should each be separate answers. \$\endgroup\$
    – DLosc
    Jan 15 at 0:46
1
\$\begingroup\$

Cell Evolution

Your lab needed to simulate how a particular cell evolves over time in a 2D grid space. A sample 2D grid space below shows a single cell at the centre of the grid.

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

The cell evolution follows these rules:

  1. '0' indicates no live cell
  2. A positive number indicates a live cell. The number indicates its age.
  3. A cell will grow from age 1 to 5 in each evolution
  4. After age 5, a cell will die at the next evolution (resetting to '0')
  5. If a cell has 4 or more neighbours (adjacent and diagonally), it will die due to over-crowding.
  6. In each evolution, a live cell will spread to its neighbour (adjacent and diagonally) if there is no live cell there and that neighbour is not overcrowded (surrounded by less than 4 cells)

Given an integer n in the input, which represents the size of the grid given, output the next generation of cells until all cells are dead ("0")

Extra rules:

  1. The first live cell is always in the center of the grid
  2. n must be odd so the live cell is always centered
  3. The grid size <=9 to prevent incredibly large outputs of data

Test case

Only 1 to save space in question

Input: 3

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

This is code-golf, so shortest bytes wins!

Tags:

matrix

code-golf

ascii-art

cellular-automata

Please check the tags or edit them if they're wrong or you think a particular tag is not here. Feel free to comment on this puzzle!

\$\endgroup\$
3
  • \$\begingroup\$ What happens to the centre if n is even? Will there be 4 alive cells or 1? Where would the alive cell be placed? \$\endgroup\$
    – PyGamer0
    Jan 19 at 8:39
  • \$\begingroup\$ The grid size must be odd so the live cell is always centered. Read the rules carefully @PyGamer0 u didnt read the extra rules \$\endgroup\$
    – DialFrost
    Jan 19 at 8:48
  • 1
    \$\begingroup\$ Could you include a test case to illustrate? Great idea btw. \$\endgroup\$
    – ophact
    Jan 19 at 13:29
1
\$\begingroup\$

From code to golf (Cops and Robbers)

\$\endgroup\$
6
  • \$\begingroup\$ Is allowed to remove letter? \$\endgroup\$
    – Fmbalbuena
    Jan 17 at 23:45
  • \$\begingroup\$ @Fmbalbuena Nope. \$\endgroup\$
    – emanresu A
    Jan 17 at 23:55
  • \$\begingroup\$ there will be someone say that the program are changed “239742387” times \$\endgroup\$
    – okie
    Jan 17 at 23:55
  • 1
    \$\begingroup\$ @okie Then there will probably be some sort of pattern, and it'll be possible to find that. \$\endgroup\$
    – emanresu A
    Jan 17 at 23:56
  • \$\begingroup\$ @emanresuA yea and that will be another interesting part of this challenge. \$\endgroup\$
    – okie
    Jan 17 at 23:59
  • \$\begingroup\$ @okie Exactly!! \$\endgroup\$
    – emanresu A
    Jan 18 at 0:01
1
\$\begingroup\$

Navigate the city

The government of your country has just completed a city designed to accommodate a few hundred thousand people. It has all sorts of facilities including roads, restaurants, malls, houses, etc. You have been invited to test the road system, but you are completely unfamiliar with it, so you need a GPS. Your challenge is to make one.

Description of the city

Note: when I say "a x a grid", I mean that there are a horizontal roads and a vertical roads within the grid.

To make the challenge easier (because of course making a GPS is difficult in itself), the city is fixed. The city's road system is based on a very rigid grid. This grid is pictured further below.

The grid has a size of 15x15 and the roads are labeled as [r/c num][dir] where "r/c num" is the row/column number (whether it is a row or column depends on the direction of the road) and "dir" is the direction. If the road runs from west to east, "dir" is E, and if it runs from north to south, "dir" is S. For instance, "1E" is the first row of the grid, while "12S" is the twelfth column of the grid. Each row and column of the grid has a length of 14km (1km between each intersection).

The Central Business District (CBD) is the 5x5 sub-grid situated in the middle of the grid. Due to the traffic parameters set below, it is important for your GPS to route the user away from the CBD if it is not necessary to pass through that district. Note that the CBD includes the borders of the 5x5 sub-grid.

At each intersection, there is a traffic light. The amount of time to wait is as follows:

  • there is a "base time" which is 400 if the intersection is in the CBD, and is the row position of the intersection (row 1 column 2 would be the intersection between 1E and 2S) times the column position otherwise;
  • the waiting time to turn left is equal to the base time;
  • the waiting time to go straight is equal to the base time, multiplied by 2;
  • the waiting time to turn right is equal to the base time, multiplied by 3.

The times above are measured in seconds.

In addition to the standard grid of roads, there is an expressway circling the inner part of the city. It passes directly over parts of the 4E, 4S, 12E and 12S roads in such a way that it forms a square. In both directions, there is an innovative exit/entry elevator at each place where there would be an intersection if you took the 4E, 4S, 12E or 12S road rather than the expressway. It is positioned in such a way that you can skip the traffic light for that intersection and get going, and in addition to that you can turn your car around in whichever direction you would like and go that way. I know it sounds rather confusing, but in essence you can exit at any intersection and go whichever way you wish, with the distances still being measured in kilometers in all cases. Note that the elevator is instantaneous (once again, not very realistic, but who uses elevators for cars on the main road anyway?). Upon entering the expressway, you can go in either direction. On the expressway, there are no at-grade intersections, so the traffic is free-flowing, and there are no waits at traffic lights or any other obstruction. Entry onto the expressway is done at any intersection involving the 4E, 4S, 12E or 12S road. Cars entering the expressway do not need to wait at a traffic light before doing so. Once again, the way in which the entry elevator is designed ensures that all distances are still measured in kilometers. This means that you can drive 1km from an intersection, enter the expressway there, and drive 3km on the expressway, with the total distance being 4km.

The city sets speed limits as follows:

  • 30 for all roads within the CBD;
  • 60 for all standard roads outside the CBD;
  • 120 for the expressway.

These speeds are measured in kilometers per hour.

Picture of the grid

Everything inside, and including, the bold black outline, is the Central Business District. The blue outline represents the expressway.

enter image description here

Challenge

Write a GPS which takes in a start intersection and end intersection, and attempts to output the fastest route from the start to the end. The "intersection" must be an intersection between two roads and can be specified in whichever reasonable input format you would like. You could take the row and column, the names of the two roads, etc. as long as it's reasonable.

Your output should be a list of directions in whichever reasonable output format you would like. Each direction should specify the direction to turn (straight, left, right, and for the expressway, enter/exit), the road to turn on and the number of "kilometers after the previous direction" to wait before executing this direction. For instance, "After 7km, exit the expressway onto 12E (East)". If the direction is to be executed while on the expressway, it must not take intersections into account. Your program may optionally decide to omit directions telling the user to "continue straight", but it may not omit any other direction. As shown above, directions telling the user to enter or exit an expressway must specify the direction to head upon entry ("enter the expressway (South)", for instance). You may direct the user in any direction from the starting intersection, and arrive at the end intersection from any side. It should also tell the user for how long he or she will have to drive, down to the second, and, optionally, the distance he or she will have to drive, which is necessarily measured in kilometers.

Your GPS may assume that the user will always be driving at the speed limit. It may also assume that the start and end are different.

Scoring

There are 225 x 224 = 50400 ways to choose start/end pairs. Your GPS will be scored based on the sum of the amounts of time it takes to drive from the start to the end, for each pair of start/end points. The GPS with the smallest total is the winner.

In the unlikely event of a tie between two or more submissions, length of code shall be the tiebreaker.

No test cases because there is never a single route for any start/end pair.


The tags for this challenge are , , and .

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

Play chess (KOTH)

Your task is to write a chess engine that will compete with other submissions in a chess tournament. Well, almost. Since writing a full engine can be a bit tedious, you only need to write the evaluation function.

An evaluation function takes a chessboard as input and returns how "favorable" the position is. If white is winning, the evaluation function should return a large positive number. If black is winning, a large negative number. If the situation is tied, a number close to zero.

Chess engines then simulate different possible games to some depth and choose the moves that lead to the best result.

A classic evaluation function is as follows:

  • Set r=0
  • For every white pawn, add 1. For every black pawn, subtract 1.
  • Same for knights and bishops, except add or subtract 3.
  • For rooks, use 5
  • And for queens, use 9

This evaluation function only takes into account material advantage; that is, just the raw amount of different pieces. More complicated evaluation functions may consider the position of individual pieces, what kind of structures do the pawns form etc.

Your task is to write an evaluation function in C in at most 150 bytes. The evaluation function takes as input 7 bitboards. A bitboard is a 64-bit integer that assigns one bit to every square of the chessboard. The first bitboard has a bit set for every piece in the chessboard. The second one encodes the owner of the piece. The remaining bitboards have a bit set for every pawn, knight, bishop, rook and queen respectively. There is no bitboard for the king, since you can calculate it using the first and last 5 bitboards. Your function will return a signed integer.

For your convenience, I've aliased __builtin__popcount to p and uint64_t to q, and also included every standard header. You should name your function e.

Note that a slow evaluation function means that the engine won't be able to search as deep as with a fast one.

TODO: more details... and also write the engine

Meta

  • Is 150 bytes a good number?
  • Almost tempted to not alias the popcount... would have interesting results
\$\endgroup\$
4
  • \$\begingroup\$ How will this be KOTH if nobody actually competes in a game of chess? \$\endgroup\$ Jan 24 at 20:38
  • 1
    \$\begingroup\$ @thejonymyster You write the evaluation function. A chess bot with your evaluation function competes (rest of the bot is standardized). \$\endgroup\$
    – AnttiP
    Jan 24 at 20:39
  • \$\begingroup\$ Oh, interesting! \$\endgroup\$ Jan 24 at 20:40
  • 1
    \$\begingroup\$ @thejonymyster counts how many bits are set in a number. It's massively useful here, since the board data is in 64-bit integers. \$\endgroup\$
    – AnttiP
    Jan 24 at 20:50
1
\$\begingroup\$

Count the ways to transform (2)

Your input is a matrix (2d array) of positive integers. For example:

\begin{matrix} 1 & 1 & 4 & 7\\ 1 & 3 & 5 & 6\\ 2 & 1 & 4 & 5 \\ \end{matrix}

A semi-continuous transformation of this matrix is a rearranging of elements that preserves immediate neighbors. For example, we can swap the \$2\$ in the bottom left, and the \$1\$ in the top left corner.

\begin{matrix} 2 & 1 & 4 & 7\\ 1 & 3 & 5 & 6\\ 1 & 1 & 4 & 5 \\ \end{matrix}

This is fine, because every number has the same neighborhood counts. That is, we can make a sorted list of numbers and their neighbors, and verify the they are the same:

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 2,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,5 \\ 4 & 1,5,7 \\ 4 & 1,5,5 \\ 5 & 3,4,4,6 \\ 6 & 5,5,7 \\ 7 & 4,6 \end{matrix}

Here is another example.

\begin{matrix} 2 & 1 & 1\\ 1 & 3 & 1\\ 1 & 1 & 4\\ \end{matrix}

Let's make a neighbor list. Note that we are gonna have duplicate entries (which is fine)

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,1 \\ 1 & 1,2,3 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 1,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,1 \\ 4 & 1,1 \\ \end{matrix}

Now, can we swap the top left \$2\$ and the bottom left \$1\$? It may look fine at first glance, but we must be careful! By swapping those two elements we would create a \$1\$ which has neighbors \$2,3,4\$, which didn't exist in the first input.

Just to demonstrate, here is the matrix after this non-semi-continuous transformation:

\begin{matrix} 1 & 1 & 1\\ 1 & 3 & 1\\ 2 & 1 & 4\\ \end{matrix}

And here is the neighbor list:

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,1 \\ 1 & 1,1,3 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 2,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,1 \\ 4 & 1,1 \\ \end{matrix}

Which is has changed after the transformation, ergo the transformation is non-semi-continuous (on this input).

To clarify, semi-continuity is a property of a transformation on some specific matrix.

Your code will take a matrix as input and output the number of (unique) semi-continuous transformations. Two transformations are different if the output is different. So for example swapping two identical numbers is the same as the identity transform (doing nothing).

Or in other words: Your code will take a matrix and return the number of matrices with those dimensions that have the same neighbor-list.

\$\endgroup\$
1
67 68
69
70 71
131

You must log in to answer this question.

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