528
\$\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 needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

\$\endgroup\$
0

3422 Answers 3422

1
7 8
9
10 11
115
4
\$\begingroup\$

A Spherical Die

Inspiration

I have a spherical die, but it's a cheap one so it doesn't work properly. When I roll it, it doesn't always land directly on a "face" marking, but instead can result in an ambiguous result ("is that a 6, a 4 or a 2?")

Assumptions

Assume the die is a perfect, evenly-weighted Unit Sphere (i.e. all points on the surface are radius 1cm from the center) , such that a "roll" can result in any point on the sphere being the uppermost point (the "roll value").

Assume that, if the die is placed or rolled such that 1 is at the "north pole", the conventions of a normal die will follow, i.e:

  • 6 will be at the "south pole"
  • 4, 5, 3, 2 will be on the "equator", clockwise in that order, equidistant around the sphere.

So, before it's rolled, the die looks like this:

image of die

The Challenge

Given a simulated roll of the die (i.e. coordinates representing the top of the die after it's rolled) with the conditions above, identify the closest value (1-6) to that point (i.e. what the roll value should resolve to).

Input

A co-ordinate on the sphere.

There are a few co-ordinate systems used for spheres, the two I'm familiar with (and so will provide examples in) are as follows:

  • P(1, φ, Θ) where φ is the "azimuth angle" (0..360), Θ is the "polar angle" (0..180)

  • P(x,y,z) where \$x^2+y^2+z^2=1\$

(note: the conversion between the two is: x = cos(φ)·sin(Θ); y = sin(φ)·sin(Θ); z = cos(Θ))

for clarity:

  • roll "1" is at P(1,n,0)
  • roll "2" is at P(1,270,90)
  • roll "3" is at P(1,180,90)
  • roll "4" is at P(1,0,90)
  • roll "5" is at P(1,90,90)
  • roll "6" is at P(1,n,180)

Output

The nearest value (1-6) to that point. If the point is equidistant to two or more points, output any one of them.

Usual exclusions etc. apply.

\$\endgroup\$
17
  • \$\begingroup\$ Does anyone know the maths for this? Feel free to edit it in! \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 9:40
  • \$\begingroup\$ I'm not sure I understand: You want us to generate a random point on a sphere and output the face of the die it corresponds to? \$\endgroup\$ – flawr Nov 22 '19 at 9:57
  • \$\begingroup\$ yeah, so generate a random point on the sphere, then find the nearest "face" - i.e. the nearest of the 6 points (top, bottom, 4 points on opposite sides around middle) \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 11:11
  • \$\begingroup\$ This will be exactly equivalent to a uniform distribution over 6 values, just based on the symmetry of the situation. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 12:33
  • \$\begingroup\$ @AlienAtSystem yes, all outcomes are equally likely; but the challenge is determining which number any given point on the face of the sphere is closest to \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 13:04
  • 4
    \$\begingroup\$ That's not the challenge as posted. Right now, it's "Takes no input, returns the number the (internally generated) random point is closest to" which is, under the consensus of no unobservable requirements simply equal to "Takes no input, returns uniform random value from 1-6". If you want the challenge to be "Input is point on sphere, output is number it's closest to", then write that. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 13:09
  • \$\begingroup\$ @AlienAtSystem I've edited to try and make it clearer what I'm looking for. Is it clearer now? \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 13:15
  • \$\begingroup\$ It's clearer that my point still stands. Look, "Make Voronoi cells on sphere" and "Generate uniformly random points on sphere" are both good challenges. But when put together like that, they annihilate each other and give you an extremely quick shortcut right from Input (None) to output (a die roll) that doesn't require calculation of either part. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 13:21
  • 2
    \$\begingroup\$ @AlienAtSystem thanks for the feedback, I'd never heard of a Voronoi cell before. What I'm asking, then, is "generate a random point on a sphere and say which Voronoi cell that point is in". Can you explain why that doesn't work? Note that I'm asking for both the point and the cell to be output, not just the cell - otherwise I agree, given the "no unobservable requirements" rule it would be possible to just generate a random number and pretend you'd done it properly (although that would be against the spirit of it) \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 13:24
  • \$\begingroup\$ Would it be better for the point on the sphere to be the input, then? \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 13:27
  • \$\begingroup\$ If you want the challenge to be about finding the points it's closest to, yes. \$\endgroup\$ – AlienAtSystem Nov 22 '19 at 13:31
  • \$\begingroup\$ I want it to be a good challenge on this theme, whatever that would look like :) \$\endgroup\$ – simonalexander2005 Nov 22 '19 at 13:33
  • \$\begingroup\$ Although I don't think the current challenge is bad, it's usually best to not have multiple challenges into one nor multiple outputs (since some languages aren't able to output more than once very easily). The two challenges are: 1. Generate a random coordinate on a sphere (in whichever coordinate system you want); 2. Given a (random) coordinate on a sphere, output the dice-value closest to it. No. 1 already is a challenge, so I agree it might be better to rewrite it to challenge No. 2. I do like the general idea though, so +1 from me. \$\endgroup\$ – Kevin Cruijssen Nov 22 '19 at 14:36
  • \$\begingroup\$ It would also need some info about the size of the sphere, and what to do when the coordinate is exactly in the center between two or three poles. \$\endgroup\$ – Kevin Cruijssen Nov 22 '19 at 14:39
  • 1
    \$\begingroup\$ Note that the actual implementation is very simple, as explained in chat. \$\endgroup\$ – user202729 Jul 15 '20 at 2:43
4
\$\begingroup\$

Note: this challenge is a work-in-progress, so suggestions would be appreciated

Questions for meta:

  • How can I prevent people from just using SHA or MD5 one-way compression?
  • are these language restrictions fair?
  • is this scoring system fair?
  • are there any obvious cheap answers?
  • what other tags should be added?
  • what should the challenge title be?
  • will these restrictions adequately prevent people trying to cheat their way through?
  • should a limit be put on a password length? Should I limit passwords to ASCII printable characters?

The challenge

Your challenge is to first choose a "password" (please do not use your actual password). Then, you will create a program which will output a truthy value if and only if this password is given as input, falsy otherwise. Your goal will be to make it so others are unable to reverse-engineer this password (and you will keep this password secret for now).

Scoring

The scoring for this challenge is somewhat different than regular . During the first two weeks from when an answer is posted, other users will have the opportunity to try to crack your password by reverse-engineering your code. If anyone gets your password correct during this two week period, your answer will be marked as cracked. If two weeks pass without users finding the password, your answer can be marked as safe once you share the password (again, please do not use your actual password, you should make up a new one that you don't use anywhere).

Note that you may use any tools at your disposal (online tools, brute-force attacks, modified code, etc) to extract someone else's password from their code.

Of all the safe answers, the one with the shortest source code (i.e. ) wins!

Rules

To make things fair for everyone, you may only use languages that appear on TIO, or languages that have well-written documentation and are used somewhat widely. You must also provide a link to try your code online that anyone can access (as such, you may not use languages behind paywalls like MATLAB but Octave is still on the table because it's free).

Even if you don't want to post an answer, feel free to try to crack any of the existing answer's passwords! If you get a password, you can simply leave a comment on that answer and that answer will be cracked.

Note

If you edit the code in your answer, the two week period will reset! You may edit any explanations in your answer freely (I will verify that any answers marked safe did not cheat).

tags: code-golf

\$\endgroup\$
18
  • \$\begingroup\$ Example answer \$\endgroup\$ – Daniel H. Aug 19 '20 at 12:38
  • \$\begingroup\$ Surely any cryptographic hash function (which are implemented in many languages) will make it easy to generate an impossible-to-crack answer? For instance, in R I can write test=scan(,'');if(digest::digest(test,"md5")=="b6778692586dc649267723ccc3356fad")TRUE else FALSE and I'll be pretty confident that nobody will crack my password... \$\endgroup\$ – Dominic van Essen Aug 19 '20 at 15:10
  • 1
    \$\begingroup\$ That is a good point. It seems like this challenge is similar to just writing a hash function. You might want to add other ideas to make the challenge more interesting \$\endgroup\$ – thesilican Aug 19 '20 at 16:06
  • \$\begingroup\$ That's what I was about to write, any hash function with a hidden default salt depending on the language, or anything like that, could be hiding the password easily enough. \$\endgroup\$ – V. Courtois Aug 19 '20 at 16:06
  • \$\begingroup\$ @DominicvanEssen is this an actual MD5 hash? I was unable to reverse it (note that a lot of MD5 hashes can be reversed with online tools like this). Note that for this challenge people would be allowed any and all tools at their disposal to crack passwords. This means people are very much allowed to reverse-engineer code in any ways they please \$\endgroup\$ – Daniel H. Aug 19 '20 at 16:06
  • \$\begingroup\$ Answering in many esolangs could hide the password easily enough, too. If I answer in Lenguage, Unary, Mariolang,... \$\endgroup\$ – V. Courtois Aug 19 '20 at 16:07
  • \$\begingroup\$ @V.Courtois this is true, but the point is not to read the password in the source code. The point of the challenge would be to reverse-engineer their code to crack a password (so documentation and online tools are all fair game). Also, Unary will likely be an invalid language because people must be able to actually run the program online (and Unary programs are usually way too big to run online) \$\endgroup\$ – Daniel H. Aug 19 '20 at 16:08
  • \$\begingroup\$ Now that I think about it, any type of loop could hide the password easily enough, too. But even with what I said before and what I'm saying now, I think this challenge has to exist (if not existing already), because having many valid answers is not a problem (not to me, at least). \$\endgroup\$ – V. Courtois Aug 19 '20 at 16:09
  • \$\begingroup\$ @DominicvanEssen also, even if nobody can reverse your password, that's still fine - the winner of this challenge is whoever has the shortest code out of all the uncracked passwords. In other words, this is still a codegolf challenge, but answers can be disqualified if anyone finds the password. So, if you want to win but you don't have the shortest code, you simply have to crack other people's passwords! \$\endgroup\$ – Daniel H. Aug 19 '20 at 16:15
  • \$\begingroup\$ @DanielH. Yes, my example was an actual MD5 hash (the password was mypassword). You're right that some hash functions can be reversed, but there are many cryptographically-secure ones for which this is difficult. \$\endgroup\$ – Dominic van Essen Aug 19 '20 at 16:17
  • \$\begingroup\$ @DominicvanEssen I'm unfamiliar with MD5 hashes, but when I converted mypassword to an MD5 hash using three different online tools I got 34819d7beeabb9260a5c854bc85b3e44 every time instead of the hash in your answer. Could you please provide a TIO link for the R code (when I copy-pasted it into TIO it didn't work for me and I'm unfamiliar with R)? I'd like to try experimenting with MD5 \$\endgroup\$ – Daniel H. Aug 19 '20 at 16:22
  • \$\begingroup\$ I'm afraid that the R 'digest' library is not installed on TIO (making a link was the first thing I tried). \$\endgroup\$ – Dominic van Essen Aug 19 '20 at 16:25
  • \$\begingroup\$ But, after some research, it turns-out that R adds some (consistent) extra characters to the string by default before applying MD5. This behaviour can be switched off, at which point mypassword indeed hashes to 34819d7beeabb9260a5c854bc85b3e44. \$\endgroup\$ – Dominic van Essen Aug 19 '20 at 16:46
  • \$\begingroup\$ how many letters are the passowrds capped at? Are unprintables allowed? \$\endgroup\$ – Razetime Aug 20 '20 at 3:30
  • \$\begingroup\$ @Razetime I might add a restriction of 16 characters, ASCII printables only. I will have to try to balance this cap though - if it's too short, passwords can easily be brute-forced. If it's too long, everyone will just use one-way compression and passwords will never be cracked \$\endgroup\$ – Daniel H. Aug 20 '20 at 11:24
4
\$\begingroup\$

Stroke Count of a Chinese Numeral Posted

\$\endgroup\$
5
  • \$\begingroup\$ Related (not dupe). Stroke count is actually good idea because it avoids the need to hardcode Chinese characters. The description looks clear enough to me. \$\endgroup\$ – Bubbler Aug 5 '20 at 3:11
  • \$\begingroup\$ Might be useful: tio.run/… \$\endgroup\$ – user202729 Aug 5 '20 at 11:45
  • \$\begingroup\$ (to read the test cases) \$\endgroup\$ – user202729 Aug 5 '20 at 11:45
  • \$\begingroup\$ Has it been posted to main? I can't seem to find it. \$\endgroup\$ – V. Courtois Aug 21 '20 at 10:02
  • 1
    \$\begingroup\$ @V.Courtois posted. \$\endgroup\$ – att Aug 25 '20 at 4:54
4
\$\begingroup\$

All work and no play but it gets thinner every time

Your objective is to output the unique string with the following properties:

  • Each paragraph consists entirely of repetitions of the sentence All work and no play makes Jack a dull boy.
  • The first paragraph is a single line with exactly one repetition of the sentence.
  • Each line of each subsequent paragraph is shorter than the longest line of the previous paragraph.
  • Each line contains as many words of the sentence as possible without exceeding the length limit, and no trailing whitespace.
  • Paragraph ends when its next line would be identical of some previous line of the same paragraph, possibly terminating the last sentence early.
  • The last paragraph has the same width as the longest word in the sentence (5).
  • There's a pair of line ends between each pair of paragraphs, a single line end after the last paragraph, and no line end before the first paragraph.

The string produced by these rules has: 5025 bytes when using Windows line ends (CR LF) or 4796 bytes using Linux line ends (LF); 229 line ends; 103 full repetitions of the sentence and 11 partial repetitions. It can be compressed into a 249-byte deflate stream (bubblegum code). The full string is included below for reference.

All work and no play makes Jack a dull boy.

All work and no play makes Jack a dull
boy. All work and no play makes Jack a
dull boy. All work and no play makes Jack
a dull boy. All work and no play makes
Jack a dull boy. All work and no play
makes Jack a dull boy. All work and no
play makes Jack a dull boy. All work and
no play makes Jack a dull boy. All work
and no play makes Jack a dull boy. All
work and no play makes Jack a dull boy.

All work and no play makes Jack a dull
boy. All work and no play makes Jack a
dull boy. All work and no play makes
Jack a dull boy. All work and no play
makes Jack a dull boy. All work and no
play makes Jack a dull boy. All work and
no play makes Jack a dull boy. All work
and no play makes Jack a dull boy. All
work and no play makes Jack a dull boy.

All work and no play makes Jack a dull
boy. All work and no play makes Jack a
dull boy. All work and no play makes
Jack a dull boy. All work and no play
makes Jack a dull boy. All work and no
play makes Jack a dull boy. All work
and no play makes Jack a dull boy. All
work and no play makes Jack a dull boy.

All work and no play makes Jack a dull
boy. All work and no play makes Jack a
dull boy. All work and no play makes
Jack a dull boy. All work and no play
makes Jack a dull boy. All work and no
play makes Jack a dull boy. All work
and no play makes Jack a dull boy. All
work and no play makes Jack a dull

All work and no play makes Jack a
dull boy. All work and no play makes
Jack a dull boy. All work and no play
makes Jack a dull boy. All work and
no play makes Jack a dull boy. All
work and no play makes Jack a dull
boy. All work and no play makes Jack
a dull boy. All work and no play

All work and no play makes Jack a
dull boy. All work and no play makes
Jack a dull boy. All work and no
play makes Jack a dull boy. All work
and no play makes Jack a dull boy.

All work and no play makes Jack a
dull boy. All work and no play
makes Jack a dull boy. All work and
no play makes Jack a dull boy. All
work and no play makes Jack a dull
boy. All work and no play makes
Jack a dull boy. All work and no
play makes Jack a dull boy. All

All work and no play makes Jack a
dull boy. All work and no play
makes Jack a dull boy. All work
and no play makes Jack a dull boy.

All work and no play makes Jack a
dull boy. All work and no play
makes Jack a dull boy. All work
and no play makes Jack a dull
boy. All work and no play makes
Jack a dull boy. All work and no
play makes Jack a dull boy. All
work and no play makes Jack a

All work and no play makes Jack
a dull boy. All work and no play
makes Jack a dull boy. All work
and no play makes Jack a dull
boy. All work and no play makes
Jack a dull boy. All work and no
play makes Jack a dull boy. All
work and no play makes Jack a
dull boy. All work and no play

All work and no play makes Jack
a dull boy. All work and no
play makes Jack a dull boy. All
work and no play makes Jack a
dull boy. All work and no play
makes Jack a dull boy. All work
and no play makes Jack a dull
boy. All work and no play makes
Jack a dull boy. All work and
no play makes Jack a dull boy.

All work and no play makes
Jack a dull boy. All work and
no play makes Jack a dull boy.

All work and no play makes
Jack a dull boy. All work and
no play makes Jack a dull
boy. All work and no play
makes Jack a dull boy. All
work and no play makes Jack a
dull boy. All work and no
play makes Jack a dull boy.

All work and no play makes
Jack a dull boy. All work
and no play makes Jack a
dull boy. All work and no
play makes Jack a dull boy.

All work and no play makes
Jack a dull boy. All work
and no play makes Jack a
dull boy. All work and no
play makes Jack a dull
boy. All work and no play
makes Jack a dull boy. All
work and no play makes

All work and no play
makes Jack a dull boy.

All work and no play
makes Jack a dull
boy. All work and no
play makes Jack a
dull boy. All work
and no play makes
Jack a dull boy. All
work and no play

All work and no
play makes Jack a
dull boy. All work
and no play makes
Jack a dull boy.

All work and no
play makes Jack a
dull boy. All
work and no play
makes Jack a dull
boy. All work and
no play makes
Jack a dull boy.

All work and no
play makes Jack
a dull boy. All
work and no play
makes Jack a
dull boy. All

All work and no
play makes Jack
a dull boy. All
work and no

All work and
no play makes
Jack a dull
boy. All work
and no play
makes Jack a
dull boy. All
work and no
play makes

All work and
no play
makes Jack a
dull boy.

All work
and no play
makes Jack
a dull boy.

All work
and no
play makes
Jack a
dull boy.

All work
and no
play
makes
Jack a
dull boy.

All work
and no
play
makes
Jack a
dull
boy. All
work and
no play

All
work
and no
play
makes
Jack a
dull
boy.

All
work
and
no
play
makes
Jack
a
dull
boy.
\$\endgroup\$
6
  • \$\begingroup\$ So a sentences can span one or more lines? Was thinking the sentences got shorter until you said there's 103 full repetitions. No clear explanation on what exactly paragraphs, paragraph widths, sentences, lines, and line ends are. \$\endgroup\$ – Noodle9 Sep 28 '20 at 15:05
  • \$\begingroup\$ @Noodle9 I've added some of the reference output; would the reference suffice to explain those? \$\endgroup\$ – John Dvorak Sep 28 '20 at 15:30
  • \$\begingroup\$ Can you simply add the whole output? (I still don't understand it) \$\endgroup\$ – the default. Sep 28 '20 at 15:37
  • \$\begingroup\$ @thedefault. added. I didn't want to clutter the sandbox. \$\endgroup\$ – John Dvorak Sep 28 '20 at 15:39
  • \$\begingroup\$ Alternative name: Write a novel for Jack Torrance \$\endgroup\$ – Razetime Sep 28 '20 at 15:51
  • \$\begingroup\$ Better to say what you mean by these terms. Maybe a template of the output where lines are, say, seperared by newline characters. Sentences are substring of "..." containing only whole words and ended by a period. Paragraphs are seperated by two newlines. Or whatever it actually is. \$\endgroup\$ – Noodle9 Sep 28 '20 at 17:07
4
\$\begingroup\$

Make a quine that shrinks and grows

Write a program that outputs another program that is:

  • Larger in bytes than the original
  • Outputs a program that is smaller than itself that also obeys these rules and is larger than the original program

Basically the output should alternate between larger than the previous program and smaller than it, while increasing in total size as it goes.

Related

\$\endgroup\$
2
  • \$\begingroup\$ Perhaps it should be "larger than the program two before" rather than "larger than the original?" As stated, a 5-length program could output a 7-length, which outputs a 6-length, which then oscillates between 7 and 6, not growing in total size as it goes. \$\endgroup\$ – Ethan Chapman Oct 8 '20 at 18:51
  • \$\begingroup\$ Probably should be named something other than a quine because I find that term misleading for the challenge you described. \$\endgroup\$ – Beefster Oct 14 '20 at 21:12
4
\$\begingroup\$

The goal of this challenge is to fill a niche that is mostly lacking on this site. In my observations there most parsing verification challenges fall into two categories:

  1. Super easy parsing. This parsing can usually be done with a regex, and regex based answers usually do well.

  2. Super complex parsing. These are challenges with a lot of small parsing components that would on their own be type 1, but together make for long code with a lot of edge cases.

Neither of these categories are really bad, each can have fun challenges, but I want to shoot for something different. A challenge which is hard, hard enough that a regex will be unable to do the brunt of the work but with a easy to understand spec.


The goal of this challenge is to parse a lisp-like lambda function. Your code should accept a string as input and output of two possible consistent values. One which corresponds to an affirmative response (i.e. the input is a properly formatted lambda) and the other corresponds to a negative response (i.e. the input is not a properly formatted lambda).

I've put together 3 specifications of what constitutes a validly formatted lambda for this challenge. The first is a quick intuition base explanation. It explains the process and what things mean even if it is not perfectly rigorous. The second a formal grammar which expresses the idea succinctly and with no ambiguity. And the third is raw code, which is the hardest to read for humans but allows you to play around with the idea by trying different inputs. I recommend you read one of the first two and play around with the third.

Formatting

The challenge uses a lisp like format. This consists of "lists" which are just parentheses enclosing lowercase words, and other lists separated each by a single space. So

(foo (bar baz) foobar)

Would be a lisp-like "list". For our challenge each list will be identified by it's first element (which should by highlighted by the syntax highlighter), which must be either app, abs, or var, representing applications, abstractions and variables, respectively.

An application is the application of one lambda function to another. It is represented by a three element list starting with of course app followed by two other valid lambda expressions. So if S and K were valid lambdas then:

(app S K)

would be a valid lambda too.

The other two abstractions and variables work together, an abstraction introduces new names for variables and variables use those names. An abstraction encloses some lambda which must be valid with the introduced variable name, and a variable can only use names which are given by abstractions that surround it. So

(abs x (abs y (var x)))

Is valid because the x name was introduced and used in a nested context. But

(app (abs x (var x)) (var x))

Is not because even though there is an abstraction for x the second (var x) is not surrounded by any abstraction at all, let alone one that introduces x.

Additionally abstractions can only introduce new variables, so

(abs x (abs x (var x)))

is not valid because the name x is ambiguous, it could refer to either abstraction. Variable names must be a string of lowercase ascii letters (a-z).

Grammar

Now for the golfy definition. This parse cannot be defined in terms of a context free grammar, so this grammar uses context. The context is a set of strings of lowercase ascii letters as these are the valid variable names.

\$ \begin{array}[rr] \ S\left(x\in C\right) &:= \color{green}{\texttt{(var }}x\color{green}{\texttt{)}} \\ S\left(x\notin C\right) &:= \color{green}{\texttt{(abs }} x\texttt{ }S(C\cup\{x\})\color{green}{\texttt{)}} \\ S\left(C\right) &:= \color{green}{\texttt{(app }} S(C)\texttt{ }S(C)\color{green}{\texttt{)}} \end{array} \$

Any string spanned by the grammar is valid and any string not is invalid.

Code

I've exhausted myself with the above. I will write to code in a bit when I've eaten and stuff.

Scoring

This is so answers will be scored in bytes with the goal being a smaller score.

Test cases

Reject

(abs x (var x
uuuuuuuuu
)))(abs x (var x))
app (abs x (var x)) (abs x (var x))
(mmm hummus)
(abs x (var y))
(abs x (abs x (var x)))
(app (abs x (var x)) (var x))
(abs (var k) (var (vark k)))

Accept

(abs x (var x))
(abs x (abs y (var x)))
(abs xx (app (var xx) (var xx)))
(app (abs ab (app (var ab) (var ab))) (abs ab (app (var ab) (var ab))))
\$\endgroup\$
4
\$\begingroup\$

In need of title.

Note: In the final challenge \$N\$ will be a concrete number (I am thinking about 100), but while this is in the sandbox it is subject to change so I have left it as \$N\$.


This challenge is based off of a list of \$N\$ Castilian Spanish words and the words they originate from.

You are to write a program or function which takes the origin word as input and outputs as close as possible the Castilian derivative. Your program should be no longer than \$N\$ bytes.

Scoring

To calculate your score run your program on every origin word and calculate the distance between your output and the correct answer. Your score is the sum of all these distances.

The distance here is a modified version of Levenshtein distance. It is the same as Levenshtein distance except replacement steps that add or remove a diacritic cost only 1/2 of a step as opposed to their normal 1.

You can use this code to calculate the distance between two strings.

The goal is to have as low a score as possible.


About the list

All of the origin words, spare 1, are Latin words (Late or Classical depending on the word). The one exception is ezkerra (the origin for izquierda) which is of Basque origin. It has been added as an extra curve-ball in case you can get all the others with a little space to spare.

Verbs are always in the infinitive form and nouns in the nominative singular.

The words are not chosen randomly but rather I have focused on choosing words that follow a number of simple rules. The list is also organized so that words that undergo similar transformations are grouped together. This is for your ease of use, nothing more.


The list

faba, haba
facienda, hacienda
facere, hacer
fundus, hondo
profundus, profundo
fungus, hongo
fabulare, hablar
furnus, horno
ferrum, hierro
filus, hijo
filum, hilo
folia, hoja
fovea, hoyo
fagea, haya
fastidium, hastío
fastidiare, hastiar
afflare, hallar
formica, hormiga
fetere, heder
ficcare, hincar
factor, hechor
factum, hecho
octo, ocho
octavus, ochavo
noctu, noche
lacte, leche
iactare, echar
coctus, cocho
dictatum, dechado
capere, caber
sapere, saber
lupus, lobo
lacrima, lágrima
lacuna, laguna
eruca, oruga
pater, padre
mater, madre
liber, libro
thema, tema
theatrum, teatro
thesaurus, tesoro
thesis, tesis
thorax, tórax
aether, éter
anthropologia, antropología
orthographia, ortografía
sapphirus, zafiro
philosophia, filosofía
echo, eco
chalare, callar
chamaeleon, camaleón
chaos, caos
materia, materia
resistentia, resistencia
aurum, oro
taurus, toro
autumnus, otoño
annus, año
scribere, escribir
scutum, escudo
scutella, escudilla
scriptor, escritor
ezkerra, izquierda
\$\endgroup\$
12
  • \$\begingroup\$ I think it's interesting in that it should be near impossible to get a perfect score without built-ins. As a suggestion I'd remove the non-ASCII words, or at least normalise them, and perhaps not let \$N\$ be too high. Also, I wonder what the default cat program would be. \$\endgroup\$ – Jo King Mod Mar 3 '20 at 12:31
  • 2
    \$\begingroup\$ @JoKing I am looking to somewhat twart perfect scores, I feel there should always be some room for improvement, It just is a little hard to balance this with golfing-languages ability for expressiveness. I am interested to hear what ranges for \$N\$ you think are too high. I started out by avoiding any non-ASCII characters, but it was really hard to build up a representative corpus of words. Plus the accents and eñe really are a feature of the language. I may adjust the scoring so that i and í for example are only half away from each other so that the penalty is small. \$\endgroup\$ – Wheat Wizard Mod Mar 3 '20 at 13:05
  • \$\begingroup\$ Suggested title: Hispanize these words. Also mention that words should be in lowercase. Finally I think it makes more sense to restrict programs to \$N\$ characters rather than \$N\$ bytes. \$\endgroup\$ – SunnyMoon Nov 20 '20 at 15:24
  • 4
    \$\begingroup\$ I'm not a fan of "Your program should be no longer than N bytes". I think a scoring rule which incorporates both the Levenshtein distance and the byte count would be better, as in the Moby Dick challenge: it would allow more languages to compete, and would allow for more creativity. \$\endgroup\$ – Robin Ryder Nov 22 '20 at 23:43
  • 1
    \$\begingroup\$ @RobinRyder I think that metrics that combine two non-obviously related factors such as in the Moby Dick challenge or as you are suggested rarely work. In fact I can't even think of an example I feel is good. They simply require fine tuning that can only really be done in retrospect. I also don't know how this would allow more languages to compete and I certainly don't know how it would "allow for more creativity". If you have a specific metric in mind and a compelling reason why that metric would not be broken I would be happy to try it out and see. \$\endgroup\$ – Wheat Wizard Mod Nov 23 '20 at 1:38
  • 1
    \$\begingroup\$ Sorry, I'll expand: with a low, hard limit on the number of characters, non-golfing languages don't stand a chance (hence the "more languages" part). If instead you set a high hard limit, it will be possible to reach a (near) perfect score, with no incentive to golf or search for trade-offs (hence the "creativity" part). There surely exists a sweet spot for the character limit where neither of these issues arise, but (a) it will be hard to find and (b) it will be highly language-dependent. \$\endgroup\$ – Robin Ryder Nov 23 '20 at 7:53
  • 1
    \$\begingroup\$ @RobinRyder I think that 100 characters is plenty of characters for nearly any language to implement something a bit more complex than cat (e.g. replace ^f with ^h). I also think that it would require quite a few characters any language to acheive a perfect score. More than half of the words have seemly random vowel mutations that are not covered by any general rule. The only way I can see a perfect score is a compression decompression method. It seems to me to write the de-compressor and make up for the loss would require a deal of room. \$\endgroup\$ – Wheat Wizard Mod Nov 24 '20 at 15:56
  • \$\begingroup\$ What I'm saying is that I think that sweet spot is actually very large. And I think that adding more dimensions to the problem only increase the risk of missing the sweet spot. \$\endgroup\$ – Wheat Wizard Mod Nov 24 '20 at 15:57
  • \$\begingroup\$ I'm not sure the modified version of the Levenshtein distance really adds something to the challenge, but it certainly makes it harder to score an answer. Would you consider updating your script so that it accepts the whole list of translations? \$\endgroup\$ – Arnauld Dec 2 '20 at 22:36
  • \$\begingroup\$ Some possible typos (I'm a native Castillian Spanish speaker and I'm familiar with Latin): afflare, hallar; factor, factor; chalare, callar \$\endgroup\$ – Luis Mendo Dec 20 '20 at 18:00
  • \$\begingroup\$ @LuisMendo hallar and chalare are definitely typos. But hechor was intentional. I suspect your hang up is that factor and hechor are doublets but factor is more similar to the Latin. There are plenty of words here for which the Latin is not a direct translation or the Spanish or vice versa (even factor is not). I chose to include hechor because it is a good example of some of the changes that I want to highlight, (f -> h and ct -> ch). \$\endgroup\$ – Wheat Wizard Mod Dec 21 '20 at 23:26
  • \$\begingroup\$ The thing is, I never heard hechor. But I just checked in the dictionary and it is included, albeit as an old form, not in current use \$\endgroup\$ – Luis Mendo Dec 21 '20 at 23:46
4
\$\begingroup\$

Strobogrammatic Numbers


Definition

A number which is rotationally symmetrical, i.e., it'll appear the same when rotated by 180 deg in the plane of your screen. The following figure illustrates it better,


strobogrammatic-number

(source: w3resource.com)

Task

Given a number as the input, determine if it's strobogrammatic or not.

Examples

  • Truthy
1
8
0
69
96
69169
1001
666999
888888
101010101
  • Falsey
2
3
4
5
7
666
969
1000
88881888
969696969

Rules

  • The number is guaranteed to be less than a billion.
  • We are considering 1 in it's roman numeral format for the sake of the challenge.
  • Input can be taken as number, or an array of chars, or as string.
  • Output would be a truthy/falsey value.
  • This is a , so fewest bytes will win!

Meta

  • Although I've tried a search, but is this a duplicate?
  • Is the challenge's text clear enough?
  • Any tricky/interesting test case?
\$\endgroup\$
1
4
\$\begingroup\$

Explain a Code Golf Answer

Background

When writing Code Golf answers, it is often a good idea to add an explanation of the code so the reader understands what's going on. For example, this this answer by @Makonede (abridged):

        θ  # last element of
Σ          # the input, sorted in increasing order by
     1¢    # the number of ones of
   %       # modulo
 žJ        # 4294967296
    b      # in binary

The full program is written on the first line, then a blank line, then on each successive line, a little snippet of the program, aligned using spaces with its position in the full program, and then some comments on the right-hand side explaining each part.

I, for one, find writing and aligning these explanations tedious, so let's outsource it to a program.

Task

Given a program as a string, and a list of sets of pairs of start/end indices to form an inclusive range, output each sub-string defined by the indices on a new line, indented to its respective position in the whole string, with a # at the end of the line, padded so that there are two spaces before the # after the last sub-string, ready for the user to add their explanation.

Rules

  • You may use 0-based or 1-based indexing
  • You are guaranteed to receive valid, non-overlapping ranges, which together cover the whole string
  • You may assume the program string contains no newlines, tabs or other unprintable characters, and no double-width characters
  • Standard I/O rules and loopholes apply
  • This is , so shortest code in bytes wins

Examples (1-based indexing)

Inputs: abcdwxyz, (1-8)
Output:

abcdwxyz  #

Inputs: abcdwxyz, (5-7), (1-2),(8-8), (3-4)
Output:

    wxy   #
ab     z  #
  cd      #

Inputs: <<<$[grep -c wx $0-grep -c y\z $0];:<<'Q', (6-20), (22-37), (4-5),(38-38),(21-21), (1-3), (39-39), (40-40), (41-45)]
Output:

     `grep -c wx $0`                           #
                     `grep -c y\z $0`          #
   $[               -                ]         #
<<<                                            #
                                      ;        #
                                       :       #
                                        <<'Q'  #

Meta

  • Is this a duplicate?
  • Is this clear enough?
  • Any other feedback?
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Razetime Dec 24 '20 at 10:32
  • 1
    \$\begingroup\$ @Razetime I would say this is a dupe :-( \$\endgroup\$ – pxeger Dec 24 '20 at 13:35
  • \$\begingroup\$ I'd say this is simpler and more suited for code golf because it functions without the need for a complex priority system. You may want to request more opinions on the nineteenth byte. \$\endgroup\$ – Razetime Dec 24 '20 at 17:51
4
\$\begingroup\$

Interpret Interval Notation

\$\endgroup\$
13
  • \$\begingroup\$ @Adám yes to and -ish characters. I also broadened the scope to all meaningful intervals, so ranges may overlap and [5,5] (all integers x where 5<=x<=5)is [5] but not [5,5) (all integers x where 5<=x<5) and (5,5) (all integers x where5<x<5) are undefined. \$\endgroup\$ – Aiden4 Dec 22 '20 at 21:07
  • 2
    \$\begingroup\$ All integers x where 5<=x<5 would be [], no? \$\endgroup\$ – Adám Dec 22 '20 at 22:25
  • \$\begingroup\$ I'd put all the undefined cases separately, or at least at the end. \$\endgroup\$ – Adám Dec 23 '20 at 0:09
  • 2
    \$\begingroup\$ Typo: the [9,13] test case should either be [9,13) or 13 is missing from the output. \$\endgroup\$ – Dingus Dec 23 '20 at 2:35
  • \$\begingroup\$ undefined cases should be undefined behavior instead. Otherwise, one need to handle it separately which feels bad. Otherwise, it's a good challenge :) \$\endgroup\$ – vrintle Dec 23 '20 at 11:22
  • \$\begingroup\$ If you allow other symbols for the brackets, make sure to prohibit other phrases as that can be abused. \$\endgroup\$ – Adám Dec 23 '20 at 15:16
  • \$\begingroup\$ @Adám what do you mean by phrases? \$\endgroup\$ – pxeger Dec 23 '20 at 16:06
  • 3
    \$\begingroup\$ @pxeger Multi-character constructs. It'd allow solutions to require an input format that contained the necessary code such that the solution becomes an eval. \$\endgroup\$ – Adám Dec 23 '20 at 16:46
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Razetime Dec 24 '20 at 10:44
  • \$\begingroup\$ Is parsing a string necessary? Could you also allow other constructs (tuples with a marker to show if they're open or closed)? \$\endgroup\$ – user Dec 25 '20 at 21:56
  • \$\begingroup\$ Just asking frankly, did you forgot to post this, or is something yet missing? \$\endgroup\$ – vrintle Jan 4 at 2:59
  • \$\begingroup\$ @user I am going to say no to other constructs otherwise, it is basically a duplicate of the related challenge. \$\endgroup\$ – Aiden4 Jan 4 at 15:03
  • \$\begingroup\$ @vrintle Something like that. I haven't really been active since just before Christmas. I'll probably post it this afternoon. \$\endgroup\$ – Aiden4 Jan 4 at 15:04
4
\$\begingroup\$

Implement a zipwith function

\$\endgroup\$
14
  • \$\begingroup\$ APL or J will win this with 2 bytes (that's the shortest possible score, right?) \$\endgroup\$ – Adám Jan 14 at 21:23
  • \$\begingroup\$ Required tag: restricted-source \$\endgroup\$ – Adám Jan 14 at 21:24
  • \$\begingroup\$ Why the builtin restriction? \$\endgroup\$ – Redwolf Programs Jan 14 at 21:45
  • \$\begingroup\$ @RedwolfPrograms To avoid trivialising the challenge \$\endgroup\$ – Dude coinheringaahing Jan 14 at 21:52
  • \$\begingroup\$ @Adám 1) if those 2 bytes are a builtin, then no, otherwise, very possible. 2) Why [restricted-source]? \$\endgroup\$ – Dude coinheringaahing Jan 14 at 21:52
  • \$\begingroup\$ Any reason for banning that builtin in Haskell and Jelly? What's wrong with people submitting that as answer? They won't get upvoted much anyway. And it still lets people use builtins in other languages. \$\endgroup\$ – user Jan 14 at 22:14
  • \$\begingroup\$ @cairdcoinheringaahing No, that'd be prohibited by your source restrictions rule on an exact built-in. Rather, it'd be a more general built-in (so not "exact") plus a parameter that makes the general built-in choose the required behaviour. \$\endgroup\$ – Adám Jan 15 at 3:21
  • \$\begingroup\$ Allowing the built-in and seeing how many languages have it could be interesting in its own right. Or, generalize the problem to nzipwith, which takes an n-ary function and n sequences (and optionally the value n) and call the function for each n-tuple from the n sequences. \$\endgroup\$ – Bubbler Jan 15 at 6:10
  • \$\begingroup\$ I've softened the builtin ban to simply encourage people to post a non-builtin answer as well. @Bubbler Possibly, but I think it'd be a good challenge to simply have the basic zipwith given that it's a fairly common functional programming construct \$\endgroup\$ – Dude coinheringaahing Jan 15 at 14:39
  • \$\begingroup\$ I think it's better to not ban them, and simply let builtin users wallow in their downvotes/shame so they don't do it again \$\endgroup\$ – pxeger Jan 16 at 19:45
  • \$\begingroup\$ @pxeger I've removed the builtin ban, and changed it to encourage builtin-only answers to include a non-builtin version as well \$\endgroup\$ – Dude coinheringaahing Jan 16 at 19:47
  • \$\begingroup\$ Would taking input as two lazily evaluated iterators over the elements of the list or outputting an iterator over the results be acceptable \$\endgroup\$ – Aiden4 Jan 26 at 1:39
  • \$\begingroup\$ @Aiden4 I think that taking lists as lazy iterators is an accepted I/O method, so yes \$\endgroup\$ – Dude coinheringaahing Jan 26 at 9:11
  • \$\begingroup\$ I find the former ban on Jelly's " interesting considering that there's no way to really pass it a function. \$\endgroup\$ – Unrelated String Jan 26 at 9:36
4
\$\begingroup\$

KoTH: Hunter-Gatherer Society

, ,

In this challenge, the goal is to write a bot (Javascript function) which survives for as long as possible with its tribe. The bots are placed on an island, with the ability to hunt, gather, farm, and build. Tribes can fight, and the last alive wins.

This challenge is complicated, and it's designed to be that way. I'd recommend starting out with bots that specialize in a particular type of strategy, like gathering berries or fighting. To keep this post from being longer than it already is, technical details will be included in the links labeled More at the end of each section. (Meta: These links don't go anywhere yet)

Overview

Bots have hit points and hunger. In order to survive, bots need to eat. There are various foods, such as berries from berry bushes, bread from farming, and meat from hunting. Materials like sticks, rocks, logs, and ores can be found around the island, and used to make tools and buildings.

The island has grasslands, forests, and rivers. Rabbits and elk can be hunted for meat and hide, with sticks, rocks, or spears. Meat can be cooked over a campfire. Tribes can build walls to protect their farms and bases, and fight to defend them with weapons and armor. Bots can talk to their tribe members, and trade for rare materials.

Hit Points, Hunger, and Turns

All bots have a number of hit points, and a number of hunger points. Bots start with 7.5 hit points, out of a maximum of 10. When they reach 0 or below, they die. Various actions take hunger. Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points.

Games consist of a number of turns. During each turn, all bots can perform actions including moving, eating, harvesting, and fighting. Each action takes a certain amount of hunger, and every action performed in the same turn after the first one doubles the hunger taken.

More: Turns

Terrain

The world consists of a square grid, with a radius determined by floor(25 * sqrt(bot_count)) + 25. The center of the grid will always be [0, 0], with coordinated ranging from [-radius, -radius] to [radius, radius]. Positions will always be specified in absolute coordinates as an array [x, y], and most actions that take a position argument will require the bot to be adjacent to that position unless otherwise specified.

This land is divided into four biomes:

  • Grassland
  • Forest
  • River
  • Ocean

The outer ring of 25 grid squares will be ocean. This consists of a beach closer to the center, with water continuing to the boundary of the world. Rivers will generate similarly, usually with a width of 5-10, with a thin beach on each side.

Each naturally generated terrain square can be one of the following:

  • Plain
  • Bush
  • Berry bush
  • Tree
  • Stone
  • Copper ore
  • Iron ore
  • Sand
  • Water

Grasslands are mostly plain, with some stones and bushes. Forests are more interesting, with many trees and some stones, bushes, and berry bushes.

More: Terrain

Movement

Bots can move in any of four directions: north(), east(), south(), or west(). Only some terrain can be walked into:

  • Plain
  • Sand
  • Farmland
  • Bush (+1)
  • Berry bush (+1)
  • Water (+2)

It typically takes 1 hunger to move. However, moving into certain terrain (marked with +1 or +2) can take extra hunger. An addition hunger point is taken for every 10 items the bot is holding, rounded down. Multiple bots can occupy the same position.

Food

There are four foods, which restore different amounts of hunger:

  • Berries: 10
  • Meat: 15
  • Bread: 25
  • Cooked meat: 40

Foods also restore 10% of their hunger restoration in hit points.

Berries can be collected from berry bushes, by returning harvest() when adjacent to (or standing in) a berry bush. Meat is obtained by hunting, bread is crafted with grain, and cooked meat requires a campfire.

Grain can be initially collected by returning harvest() when adjacent to (or standing in) plain land. It can also be collected from farming. Bread can be crafted by returning craft(Item.BREAD) while holding 1 grain and 1 rock. The rock will not be consumed.

More: Food, Harvesting

Resources

Many types of terrain can be broken by returning break(position), turning into plain land and giving items:

  • Bush: Stick × 1
  • Berry bush: Berries × 1
  • Tree: Log × 2
  • Stone: Stone × 1
  • Copper ore: Copper ore × 1
  • Iron ore: Iron ore × 1

Trees require an axe to break. All four will reappear after a number of turns if the land remains plain.

A stone axe can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_AXE), and will break after 10 uses.

More: Breaking, Crafting

Farming

A stone shovel can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SHOVEL). A shovel can be used to turn plain land into farmland, and will break after 20 uses. This is done by returning shovel(position).

Grain can be planted on farmland by returning plant(position). It will take around 100 to 200 turns to grow, although the amount of time is much shorter within 20 squares of water. Grain starts as Growth.NOT_GROWN, and cannot be harvested (only broken). It then becomes Growth.GROWING after about 70% of the total time, and will give one grain when broken or harvested. Finally, the last stage is Growth.GROWN, where two to four wheat are given from harvesting.

More: Farming

Hunting

A stone spear can be crafted from 1 stick and 1 stone by returning craft(Item.STONE_SPEAR). A spear can be used to hunt, as well as a stick or stone. Bots can attack at a position by returning attack(position) (hunt(position) and fight(position) are aliases). Movement happens before attacking, so simply attacking an animal's current position may not work. If attacking would hit multiple targets, damage is distributed between them evenly.

Sticks and stones have a range of 1, with sticks dealing 0.35 hit points, and stones dealing 0.75. Spears deal one hit point, with a maximum range of 2. A spear breaks after 10 successful hits. Attacking takes 10 hunger, whether or not any target is successfully hit.

There are two types of animals: rabbits and elk. Rabbits have 1 hit point, and elk have 4. Rabbits will move every 1 to 2 turns, avoiding bots if they are very close. Elk will move every 2 to 4 turns, and will always move away from attackers for 2 to 4 turns after being attacked. Rabbits will give the last bot to hit them 1 meat, and have a 25% chance of giving 1 hide to the second to last player to hit them. Elk are similar, giving 1 meat and 1 hide to the last bot to hit them, and 1 meat to the bot that hit them the 2nd to last time.

More: Hunting

Tribes

All bots will be part of a tribe. Tribes are determined by the creator of the bot, can contain any number of bots from any number of writers. Bots in the same tribe will be able to recognize each other, while bots outside their tribe will only have their tribe name known. Tribe members cannot attack each other.

If a tribe member is next to another one, they can give an item with give(name, item), or transfer any JSON-serializable data with talk(name, data).

Armor can be crafted from 2 hide with craft(Item.ARMOR). When a bot is holding armor, it can take up to 10 hit points before breaking. Bots fight with other bots in the same way they hunt animals. When a bot is killed, its items are distributed among the bots that attacked it recently according to the damage done.

More: Tribes, Fighting

Building

Bots can build walls and campfires, by returning build(build, position), where build is one of Terrain.WOOD_WALL, Terrain.STONE_WALL, Terrain.CRATE, or Terrain.CAMPFIRE. Wood walls require 2 logs, and take 10 hits with an axe to break, giving the bot that breaks it one log. Stone walls require 4 stones, and take 75 hits with an axe to break, giving the bot that breaks it one stone.

Crates require 1 log and 1 bronze, and can store items. If you're adjacent to a crate, you can store items in it with store(position, items), and take an item with take(position, items). Crates can store up to 40 items. The contents of crates are visible to any bot.

Campfires require 1 stone, and 2 sticks, and can be used to cook meat. Campfires can be given fuel using fuel(position, item), accepting sticks, logs, and charcoal. Bots can cook meat or logs (which turn into cooked meat and charcoal, respectively) using cook(Item.MEAT) or cook(Item.LOG), if adjacent to a campfire. Cooking meat uses 3 fuel, and cooking logs uses 5. A stick provides 1 fuel, a log provides 5, and charcoal provides 15.

A campfire can be broken with an axe, and will give the bot that breaks it all of the unused fuel it holds. Partially consumed logs or charcoal will not be given.

More: Building, Cooking

Upgrading

Copper ore and iron ore can be cooked into bronze and iron in a campfire, requiring 10 and 15 fuel respectively. Bronze and iron can be used to craft stronger axes, shovels, and spears, by replacing the stone in the recipe with the corresponding item.

For axes and shovels, the material affects the durability:

  • Stone axe: 10
  • Bronze axe: 15
  • Iron axe: 25

All shovels have twice the durability of a similarly strong axe. Spears are different, with all tiers having 10 durability. Instead, the number of hit points dealt is upgraded:

  • Stone spear: 1.0
  • Bronze spear: 1.5
  • Iron spear: 2.5

Because these items are so rare, trading might be a good way for a tribe to advance. By returning offer(sell, buy), any bot can offer a number of items they have (sell) for a number of items they want to have (buy). All bots will receive an array of offers made on the last turn, and can accept one with accept(offer), where offer is an offer ID.

The sell array should contain IDs of items the bot is holding, while buy should be an array of objects. All objects should have an item property with the Item wanted, and an optional durability property can specify a minimum durability acceptable. If no minimum durability is included, only undamaged items will be accepted.

More: Trading

Bots

Many arguments and functions involve enums including Terrain and Item. Here is a reference:

  • Terrain: PLAIN, BUSH, TREE, STONE, COPPER_ORE, IRON_ORE, FARMLAND, SAND, WATER, WOOD_WALL, STONE_WALL, CAMPFIRE
  • Item: STICK, BERRIES, LOG, STONE, COPPER_ORE, IRON_ORE, CHARCOAL, BRONZE, IRON, MEAT, COOKED_MEAT, GRAIN, BREAD, HIDE, ARMOR, STONE_AXE, BRONZE_AXE, IRON_AXE, STONE_SHOVEL, BRONZE_SHOVEL, IRON_SHOVEL, STONE_SPEAR, BRONZE_SPEAR, IRON_SPEAR
  • Growth: EMPTY, NOT_GROWN, GROWING, GROWN
  • Animal: RABBIT, ELK

All bots should be Javascript functions, which take four arguments:

  • grid: A 15 by 15 grid centered around the bot, with all items being objects:
    • terrain: A type of Terrain
    • details: An object, with a has_berries property for Terrain.BUSH, a growth property for farmland (Growth.EMPTY if no grain is planted), a hit_points property for walls (starts as 10 for wood or 75 for stone), and a fuels property for campfires (array of Items.STICK, Items.LOG, and Items.CHARCOAL, does not include partially burned)
    • bots: An array of bots, with all being objects:
      • tribe: A string containing a tribe name
      • name: A string containing a bot name, if the bot is in the same tribe
    • animals: An array of animals, with all being one of Animal.RABBIT or Animal.ELK
  • bot: An object with information about the bot:
    • hit_points: Hit points
    • hunger: Hunger
    • position: Position as [x, y]
    • items: An array of items held, with all items being objects:
      • id: A unique ID for this item
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
  • offers: An array of offers from other bots on the last turn:
    • id: An ID unique to the offer
    • sell: An array of the items the seller is offering:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the remaining uses (or hit points) until broken
    • buy: An array of items the seller wants:
      • item: A type of Item
      • durability: For armor, axes, shovels, or spears, the minimum durability acceptable
  • talking: An array of data sent from other bots on the last turn:
    • name: The name of the sending bot
    • data: The data sent by the bot
  • storage: An object that can be used for storage between turns

Meta

(Note that none of the links to More work yet)

  • Is this clear enough as it is, without the technical details?
  • Is there too much information, or is it too hard to read?
  • Do you think there will be strategy and clever bot design?
  • Would you compete in this challenge? Why not?

New features

Things I recently added:

  • Trading between tribes
  • Communication within tribes
  • Bronze and iron, and better tools
  • Crates to store items
\$\endgroup\$
8
  • \$\begingroup\$ When you say "Bots start with 75, out of a maximum of 100, and when they drop below 0 hunger points they instead lose 10% of the hunger taken in hit points." Did you mean: "Bots start with 75 hitpoints, out of a maximum of 100, and when they drop below 0 hit points they instead lose 10% of the hunger taken in hit points."? \$\endgroup\$ – DanielOnMSE Mar 9 at 4:58
  • \$\begingroup\$ @DanielOnMSE The reverse, mostly. Bots start with 7.5/10 hit points, and 75/100 hunger. When a bot drops below 0 hunger, additional hunger is taken from the bot's hit points instead (but scaled by 10%) \$\endgroup\$ – Redwolf Programs Mar 9 at 5:19
  • \$\begingroup\$ Ahh okay. I think this contradicts "Bots start with 7.5 hunger, out of a maximum of 10. When they reach 0 or below, they die" Unless hitpoints/hungers still mean something when dead? Nice idea btw. I've upvoted. I'll continue to trawl through it and see if I can find any errors. I think I get what you are trying to say with the hitpoints/hunger but I think you may have accidentally swapped the two in some places? \$\endgroup\$ – DanielOnMSE Mar 9 at 5:28
  • \$\begingroup\$ @DanielOnMSE Ah, I see what you mean. I'll fix that. \$\endgroup\$ – Redwolf Programs Mar 9 at 5:44
  • \$\begingroup\$ Just food for thought. Might make the challenge more approachable if you wrote a script that created the world state and takes input/gives output every turn to the bots? Or is part of this challenge making the "game" itself? Perhaps you've already considered this and made something. Whether or not this is implemented will determine the complexity of this, imo. Like if you could create something everyone involved could use to test their bot? Also give it fixed input and output formats? \$\endgroup\$ – DanielOnMSE Mar 9 at 5:53
  • 2
    \$\begingroup\$ @DanielOnMSE Usually that's part of making a KoTH, yeah. There's a controller program (usually written by the author before posting) that manages all of the bots, sets up the games, determines the winner, etc. \$\endgroup\$ – Redwolf Programs Mar 9 at 13:21
  • \$\begingroup\$ This challenge seems very interesting but even more complex to me... but I'd give it a try. However, it would need many participating bots to utilize all of its features and make it fun to play. Technical note: break won't work as a function name (it's reserved) unless it's an object property. \$\endgroup\$ – FZs May 18 at 15:38
  • 1
    \$\begingroup\$ @FZs Part of my goal when designing this KotH was specifically for it to be very complex; I'm hoping bots will be sort of forced to specialize. Thanks for noticing the break thing, I guess I'll rename that to destroy or mine \$\endgroup\$ – Redwolf Programs May 18 at 15:40
4
\$\begingroup\$

Calculate the 'geothmetic meandian' of a set of numbers

Randall Munroe's March 10 xkcd comic "Geothmetic Meandian" defines the 'geothmetic meandian' of a set of positive real numbers as follows.

Define a function F, such that F accepts a set of n positive real numbers and returns the set (a, b, c), where a is the arithmetic mean of the set (the sum of the numbers in the set divided by n), b is the geometric mean of the set (the product of the numbers in the set to the power of 1/n), and c is the median of the set (the average of the middle two numbers in the sorted set when n is even, and the middle number in the set when n is odd). The function F can therefore be applied again to its own output. Iterating F an infinite number of times should cause its three outputs to converge to one value g. This value g is defined as the geothmetic meandian of the original set of positive reals. (For the purposes of this challenge, you may assume this value exists and does not diverge.)

Given a nonempty list of positive real numbers in any convenient and reasonable format and a positive integer q, compute its 'geothmetic meandian' to q significant figures. Standard rules apply, and the shortest code in bytes wins.

Test cases

[[1], 2] --> 1.0
[[2, 8], 4] --> 4.742
[[1, 1, 2, 3, 5], 6] --> 2.08906
[[1, 2, 4, 8], 6] --> 3.13227
[[1.1, 2.2, 4.4, 8.8], 9] --> 3.44550208
\$\endgroup\$
9
  • 4
    \$\begingroup\$ This seems like a decent challenge, but I don't know if the rounding requirement adds anything. \$\endgroup\$ – rak1507 Mar 11 at 2:40
  • \$\begingroup\$ @rak1507 I was accounting for if different languages have different levels of floating-point precision, and also because the calculation needs to stop at some defined point. \$\endgroup\$ – Cloudy7 Mar 11 at 3:24
  • 3
    \$\begingroup\$ The problem with taking the number of significant figures q as input is that you're banning the use of float and double numbers entirely (doubles will break at q >= 16 or so), which is a big no-no. You could take the number of iterations i instead and require the solutions to output the result of i-th iteration. \$\endgroup\$ – Bubbler Mar 12 at 5:05
  • \$\begingroup\$ @Bubbler I envisioned part of the challenge to be determining when to stop the iteration of F. Should I then restrict q to be a positive integer from 1 to 7 or something similar? \$\endgroup\$ – Cloudy7 Mar 12 at 17:28
  • \$\begingroup\$ Alternatively, we can have have a fixed number of iterations i and output the geothmetic meandian to the highest precision possible given i iterations. However, thinking about it, I agree this part of the challenge may be unfeasible. \$\endgroup\$ – Cloudy7 Mar 12 at 17:39
  • \$\begingroup\$ Oh dear. I just tried another test case and due to floating-point errors in calculation, my program slowly drifts by 2e-12 indefinitely as F is iterated... \$\endgroup\$ – Cloudy7 Mar 12 at 17:49
  • 3
    \$\begingroup\$ How about this: Given a value q (a positive floating-point number), stop iteration when the difference between the maximum and the minimum is less than q, and output any of the three numbers (or all of them). Allow the solutions to fail if q is too small compared to the input (i.e. it is outside the precision capability of the floating-point type in use). I think this is clearer to specify the error margin this way. \$\endgroup\$ – Bubbler Mar 15 at 3:46
  • \$\begingroup\$ Or just require that all programs use a fixed q, e.g. 100? \$\endgroup\$ – pxeger Mar 20 at 17:53
  • 1
    \$\begingroup\$ I feel like adding anything to do with the precision will just complicate things, and most of the code will be for handling that, not for actually answering the challenge. IMO it's fine to say 'until it converges', and leave specifics up to the challenge answerers. \$\endgroup\$ – rak1507 Mar 22 at 12:19
4
\$\begingroup\$

Complete the landscape

Carcassonne is a tile-based game, where the objective is to construct Roads, Cities and Monasteries, in order to score points. The game works by players taking turns to draw and place tiles to construct a landscape, then claiming roads, cities and monasteries. An example landscape is:

Example Landscape

There are \$19\$ distinct tiles (ignoring rotations), each of which contains at least one feature (Road, City or Monastery):

All tiles

Also, notice that the landscape must be consistent. This means that roads must connect to other roads, city edges must connect to other city edges and fields must connect to fields. Therefore, these tiles are inconsistent:

Inconsistent tiles

To avoid this challenge being about image processing, we can translate each tile into a list containing \$5\$ values, according to this legend:

[North edge, East edge, South edge, West Edge, # of cities]

0: Field
1: Road
2: City

For instance, this tile can be described as [2, 0, 1, 1, 1]. Using this legend, we can describe each tile uniquely, and it's rotations are rotations of the first four elements. The entire grid can be described as a rectangular matrix, with a \$20^\text{th}\$ distinct value for an empty square. Translating the first landscape into this format, we get:

[
 [             [],              [], [1, 1, 0, 0, 0], [1, 1, 2, 1, 1], [0, 1, 0, 1, 0],              [],              []],
 [[1, 0, 1, 0, 0],              [], [0, 0, 0, 0, 0], [2, 0, 2, 0, 2],              [], [0, 2, 2, 2, 1], [0, 0, 0, 2, 1]],
 [[1, 1, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [2, 2, 0, 0, 1], [2, 2, 0, 2, 1], [2, 0, 0, 2, 1],              []]
]

using [] to represent an empty square. The complete list of tiles (ignoring rotations) in the same grid as the second image is

[1, 0, 1, 0, 0] [0, 0, 1, 1, 0] [2, 1, 1, 1, 1] [0, 1, 1, 1, 0] [2, 0, 0, 0, 1]
[2, 2, 0, 2, 1] [0, 0, 0, 0, 0] [2, 2, 2, 2, 1] [2, 2, 0, 0, 1] [2, 1, 1, 2, 1]
[2, 2, 0, 0, 2] [0, 0, 1, 0, 0] [2, 0, 1, 1, 1] [2, 1, 1, 0, 1] [0, 2, 0, 2, 1]
[1, 1, 1, 1, 0] [2, 1, 0, 1, 1] [2, 2, 1, 2, 1] [2, 0, 2, 0, 2]

Your task is to take in a rectangular matrix where every element save one is one of the 19 tiles given above or one of their rotations. Tiles can appear more than once, and not every tile will appear in every input. This landscape will be consistent, as defined above. You should take in this input and output the tile that could fill the empty space in the array, keeping the landscape consistent, as defined above.

As the number of cities on a tile is redundant for this task, you may choose instead to only work with 17 tiles (as 2 tiles are duplicated when ignoring cities) and take input as lists in the form [N, E, S, W] instead.

If there are multiple tiles that would work, you may output either all of them or just one. If no such tile exists, you may produce any output/result that could not be construed as a tile (i.e. it's not in the 19 tiles specified above, nor in any of their rotations). The representation of the "empty space" in the input may be your choice, so long as its consistent, and (although I'm not sure why you would) it isn't one of the 19 tiles above or their rotations, and there will only ever be a single empty space.

This is , so the shortest code in bytes wins.

Test cases

test cases to be added


Meta

  • Is this clear enough?
    • More specifically, is the definition of a "consistent landscape" objective and understandable?
  • This is a somewhat related question, but I believe there are enough differences between the two for them to not be duplicates. Thoughts?
  • Tags are , , , . Any suggestions?
  • Any further feedback?
\$\endgroup\$
10
  • \$\begingroup\$ @Beefster Aside from involving tiling, I'm not quire sure how that challenge is related, let alone a possible duplicate \$\endgroup\$ – Dude coinheringaahing Sep 28 '20 at 22:00
  • \$\begingroup\$ Filling Carcassonne tiles in a grid can be thought of as a specific case of wang tiles with a different set of tiles, but upon closer inspection, seeing as your challenge is to complete the landscape, rather than fill a grid from nothing, this is actually a pretty different challenge. \$\endgroup\$ – Beefster Sep 28 '20 at 22:03
  • \$\begingroup\$ Related \$\endgroup\$ – Beefster Sep 28 '20 at 22:04
  • \$\begingroup\$ Does the 5th field, the # of citys, add anything? Makes it more cumbersome to store/rotate the tiles. Though it's understandable if you want to keep true to Carcassonne. \$\endgroup\$ – xash Mar 17 at 19:21
  • \$\begingroup\$ @xash Yes, without the number of cities, some tiles (e.g. [2,2,0,0,1] and [2,2,0,0,2]) have the same representation as an array \$\endgroup\$ – Dude coinheringaahing Mar 17 at 19:22
  • \$\begingroup\$ @xash As "there will only ever be a single empty space.", "the empty space" makes more sense, as it refers to the only empty space in the input \$\endgroup\$ – Dude coinheringaahing Mar 17 at 19:26
  • \$\begingroup\$ Ah! I thought "The "empty space" in the input may be your choice" refers to which empty space to choose to fill, not the representation. Sorry, haven't slept well, makes perfect sense. :-) \$\endgroup\$ – xash Mar 17 at 19:29
  • \$\begingroup\$ While I agree that to match Carcassonne, the number of cities field is useful for disambiguating two different tiles, it would never affect whether a tile fits into the space or not, so for this challenge it seems redundant. \$\endgroup\$ – Nick Kennedy Mar 20 at 7:42
  • \$\begingroup\$ Will the 19 possible tiles be supplied as an input or do they need to be encoded into the answer? \$\endgroup\$ – Nick Kennedy Mar 20 at 7:46
  • \$\begingroup\$ @NickKennedy Good point, I didn't realise that. I've added in a note about the redundancy of the city count. No, the tiles will not be provided as input, so the answer will need to implement some way of encoding them \$\endgroup\$ – Dude coinheringaahing Mar 21 at 11:52
4
\$\begingroup\$

Hide a message in ASCII art and an image

(needs cooler title)


Cops


Robbers

\$\endgroup\$
7
  • 1
    \$\begingroup\$ How the heck?! I was just drafting a challenge about stenography and images yesterday and then I see this.. \$\endgroup\$ – Redwolf Programs Mar 26 at 16:28
  • \$\begingroup\$ @RedwolfPrograms was your idea the exact same as mine? \$\endgroup\$ – Beefster Mar 26 at 16:35
  • 1
    \$\begingroup\$ Not identical, there was no ASCII art included, but considering there are only 5 steganography questions on the whole site that's an insane coincidence \$\endgroup\$ – Redwolf Programs Mar 26 at 17:03
  • 1
    \$\begingroup\$ If the robber doesn’t know any of the messages, it might be hard to verify any potential explanation. It might be more fun and easier to verify a correct solution if the cop posts N codes and the solutions to N-1 of them, and the robber has to use those to reverse engineer the method and decode the last one. Alternately, the cop could have to pick from a list of pre-selected messages so the robber has some idea what to look for. \$\endgroup\$ – water_ghosts Mar 26 at 17:33
  • 1
    \$\begingroup\$ Do the ascii+png files have to contain all the information necessary for decoding? For example, could I use a book cipher where the PNG encodes word numbers, and you then have to look up the corresponding words from The Great Gatsby? \$\endgroup\$ – water_ghosts Mar 26 at 18:03
  • \$\begingroup\$ @water_ghosts I think a book cipher should only be allowed if you provide a link to the book. All data needed to decode aside from the image and ascii art should be present in the post and be constant across all encodings. \$\endgroup\$ – Beefster Mar 29 at 18:43
  • \$\begingroup\$ This is amazing! You, dear sir/ma'am, get an upvote \$\endgroup\$ – StackMeter Apr 3 at 17:05
4
\$\begingroup\$

Determine Circles

\$\endgroup\$
12
  • \$\begingroup\$ Nice idea, but could you make it clearer what do you mean by cross? A test case would be good. \$\endgroup\$ – math Apr 6 at 7:04
  • \$\begingroup\$ @math intersect or some concept like that. Can you give some better wording if you can understand what I mean? I can't find any word that suit line go over dot \$\endgroup\$ – okie Apr 6 at 7:09
  • \$\begingroup\$ Maybe: 1, 2, 3 points will need 1 circle only to be sure that the points touch the circles boundary? Is that what you mean? \$\endgroup\$ – math Apr 6 at 7:17
  • \$\begingroup\$ Some testcases are definitely needed, like five points on one circle and three points on another. Also, are the coordinates integers or real numbers? \$\endgroup\$ – Bubbler Apr 6 at 8:15
  • \$\begingroup\$ @Bubbler Real number I think \$\endgroup\$ – okie Apr 6 at 8:17
  • \$\begingroup\$ @okie Then you need to explicitly write it down, and add some testcases with non-integer coordinates. \$\endgroup\$ – Bubbler Apr 6 at 8:21
  • \$\begingroup\$ In this problem, the answer does not change continuously with small perturbations of the input coordinates. Is it allowed to output the wrong answer due to floating point errors? For instance, if the input coordinates were (0,0),(0.3,0.3),(1,1) then the output should be 2. However, if the second point were instead (0.3,0.300...00001) then the answer should be 1. Given that floating point types are usually unable to tell these two cases apart, are we allowed to output either 1 or 2? \$\endgroup\$ – Delfad0r Apr 6 at 16:01
  • \$\begingroup\$ @Delfad0r Thanks for your help. To solve such problem (float precision), I decided to add a limit to float so that precision are not extreme. \$\endgroup\$ – okie Apr 7 at 0:15
  • 1
    \$\begingroup\$ Another possible approach (which I personally prefer, but the choice is entirely up to you) could be to only have integer coordinates as input, and then ask for an exact solution. If I am not mistaken, this problem should be solvable without resorting to square roots and similar, and therefore without any possibility of floating point errors. \$\endgroup\$ – Delfad0r Apr 7 at 12:30
  • \$\begingroup\$ @Delfad0r But it's like a float *100 0.03*100 = 30 which just get every number bigger? \$\endgroup\$ – okie Apr 7 at 23:38
  • \$\begingroup\$ @okie Yes, but the difference is that computations with integers are exact, while computations with floats are not. It shouldn't matter too much however, do whatever you prefer :) \$\endgroup\$ – Delfad0r Apr 7 at 23:43
  • \$\begingroup\$ @Delfad0r I think I would take Integer, Thanks! \$\endgroup\$ – okie Apr 8 at 0:04
4
\$\begingroup\$

posted lol

\$\endgroup\$
8
  • \$\begingroup\$ Another suggestion it can be kolmogorov complexity challe ge too, if someone downloads tags and compresses the text \$\endgroup\$ – wasif Apr 12 at 5:31
  • \$\begingroup\$ @Wasif it's better as an internet challenge because a new tag might be created after challenge posting making the list invalid. \$\endgroup\$ – exedraj Apr 12 at 5:31
  • \$\begingroup\$ Should the list include the synonym tags, i.e. the tags that are listed as being on no questions in the tag listing? \$\endgroup\$ – Dude coinheringaahing Apr 12 at 13:30
  • \$\begingroup\$ @cairdcoinheringaahing if it is listed on the tags page, then it needs to be included \$\endgroup\$ – exedraj Apr 12 at 22:54
  • \$\begingroup\$ What is the 43 for in example program? \$\endgroup\$ – tsh Apr 14 at 3:18
  • \$\begingroup\$ @tsh 43 is the number of occurrences of tag when you try and access a page of tags that doesn't exist \$\endgroup\$ – exedraj Apr 14 at 3:19
  • \$\begingroup\$ Rule is still too wide, everyone can upload code to codegolf.stackexchange.com \$\endgroup\$ – l4m2 Apr 15 at 4:19
  • \$\begingroup\$ @l4m2 if people include all the tags in a post, then they will have to a) keep it constantly updated (which wouldn't be viewed favourably by the community) and b) withstand potential downvotes for loop holing on both the answer to this and the answer that has the tags \$\endgroup\$ – exedraj Apr 15 at 4:45
4
\$\begingroup\$

Implement an Over function

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Can we take \$a\$ and \$b\$ as [a,b]? In effect, this would make the challenge a \$g\$ reduction of \$f\$ mapped over that input list. \$\endgroup\$ – Adám Apr 19 at 21:12
  • 2
    \$\begingroup\$ @Adám I think it would be unfair (and potentially unobservable) to ban languages from taking it as [a,b], and doing so would likely just create solutions in the form pair input; map f; reduce g \$\endgroup\$ – Dude coinheringaahing Apr 19 at 21:41
4
\$\begingroup\$

Rob the King: Hexagonal Mazes

Consider the following hexagonal maze:

     E . \ . . .
    . . . \ . \ .
   . . . . \ . \ .
  _ _ _ _ . \ . \ .
 . / . . . . . . | .
. | . . _ _ _ _ / . .
 . \ . \ . . . / . .
  . \ . \ . . / . .
   . \ . \ . . . .
    . \ . \ / . .
     . \ . | . X

E represents the entrance, X the exit. |_/\ are walls and . are free spaces. In order to navigate from E to X, we can move to any free space in the up to 6 immediately surrounding spaces. The path from E to X, marked with P is:

     E P \ P P P
    . . P \ P \ P
   . . . P \ P \ P
  _ _ _ _ P \ P \ P
 . / . . . P P P | P
. | . . _ _ _ _ / . P
 . \ . \ . . . / . P
  . \ . \ . . / . P
   . \ . \ . . . P
    . \ . \ / . P
     . \ . | . X

This isn't the only path, but the others are trivial variations on it.


Cops

You are to write a function in Python 3 which takes a positive integer \$n \ge 2\$ and returns a hexagonal maze of side-length \$n\$, as shown above. The maze will meet the following criteria:

  • The only characters in the output are EX.|_\/, space and newline
  • The hexagon is shown as a hexagon. That means:
    • The first \$n\$ lines will have one more non-space character than the previous line (the first has \$n\$ non-space characters), separated by a single space, and offset from adjacent lines
    • The first \$n\$ lines have one fewer leading space than the previous line (the first line has \$n - 1\$ leading spaces)
    • The next \$n - 1\$ lines have one more leading space than the previous line
    • The next \$n - 1\$ lines will have one fewer non-space character than the previous line, separated by a single space, and offset from adjacent lines
    • Lines may not have trailing whitespace
  • The E is the first non-space character on the first line, and the X is the last non-space character on the last line
  • There is at least 1 valid path that connects the E and the X, only moving from one free space to an adjacent free space.

How your program generates these mazes is entirely up to you. It could randomly places walls in the grid, ensuring there is always at least one path left, or it could only block the center row except for one gap, or anything else.

You may return either a multi-line string, or a list of lines. Lines should have appropriate space padding at the start, and may have a consistent amount of trailing spaces. "Consistent" here means either the same number on each line, or padding each line to the same length.

The Robbers will be writing maze-solving programs that try to solve your mazes, so you should aim to generate mazes that are somewhat difficult to solve.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

Empty mazes of sizes \$n = 2, 3, 4, 5, 6\$:

                                                                 E . . . . .
                                           E . . . .            . . . . . . .
                         E . . .          . . . . . .          . . . . . . . .
           E . .        . . . . .        . . . . . . .        . . . . . . . . .
 E .      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
. . .    . . . . .    . . . . . . .    . . . . . . . . .    . . . . . . . . . . .
 . X      . . . .      . . . . . .      . . . . . . . .      . . . . . . . . . .
           . . X        . . . . .        . . . . . . .        . . . . . . . . .
                         . . . X          . . . . . .          . . . . . . . .
                                           . . . . X            . . . . . . .
                                                                 . . . . . X

Robbers

You are to write a Python 3 function that takes in the return value of a cop's answer. It may also take the number of sides, \$n\$, as an argument if you so wish. The input will only contain EX_|/\. and space, and newlines if inputting as a multiline string. It will either be a multiline string or a list of lines. Your function should handle both.

Your function should then output the maze with any valid path connecting the E and X using only connected free spaces. You may show the path with any character aside from EX_|/\., space or newline.

This is not , you are under no obligation to golf your submission.

Additionally, you may submit multiple submissions. You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified


Scoring

The scoring will take the form of a round-robin, similar to challenges. Every cop will be paired up with every robber, and the following will happen with each pair:

  • The controller will call the cop's function 5 times with \$n = 2\$ as an argument, saving each of the 5 mazes. The cop will have 1 minute to produce each maze
  • It will then pass each maze to the robber to solve. The robber will have 1 minute per maze to produce a correct output.
  • If all 5 mazes are correctly solved by the robber within 1 minute each, the controller goes again, but with \$n = 3\$, and so on, increasing the \$n\$ by one, until either:
    • The robber fails to solve a maze within 1 minute
    • The robber produces an incorrect solution to an input maze
    • The cop fails to return a maze within 1 minute
    • The cop returns a maze with no path

At this point, both the cop and the robber receive points equal to the highest \$n\$ that neither of them failed. If the cop failed, the robber receives an additional point, and if the robber failed, the cop receives an additional point instead.

If both the cop and the robber reach \$n = 50\$ without failing, they both receive \$50\$ points.

After all pairs have be run, the cop and robber with the most points are the respective winners


Meta

\$\endgroup\$
5
  • 2
    \$\begingroup\$ If you want to automate the scoring process, you might want to restrict the I/O further, e.g. only allow stdin/stdout as a hexagon-shaped multi-line string. (I'm suggesting stdio because I assume you want to allow different languages.) Looks interesting, though I have a slight feeling that a full Dijkstra impl in C will almost surely win as a robber. \$\endgroup\$ – Bubbler Apr 12 at 23:01
  • \$\begingroup\$ @Bubbler Good point, I've updated the I/O to be stricter. \$\endgroup\$ – Dude coinheringaahing Apr 12 at 23:22
  • \$\begingroup\$ @Bubbler I've decided to limit it to Python 3 functions, as I was struggling to make a controller that would allow any language to compete \$\endgroup\$ – Dude coinheringaahing Apr 23 at 15:49
  • \$\begingroup\$ It's a minor thing, but maybe change E and X to A and B? It seems more logical that way \$\endgroup\$ – pxeger Apr 24 at 15:52
  • \$\begingroup\$ @pxeger I chose E and X as "entrance" and "exit" respectively, but I doubt it'll affect any solutions as opposed to A/B \$\endgroup\$ – Dude coinheringaahing Apr 24 at 16:06
4
\$\begingroup\$

Death-onacci sequence (WIP)

The traditional Fibonacci sequence grows forever:

0 1 1 2 3 5 8 13 21 ... 1,346,269 ...

and is given by this formula:

f(n) = f(n-1) + f(n-2)

where the initial numbers in the sequence are 0, 1.

However, there's a set of as-yet unnamed sequences, where a previous number 'dies' and is removed from the total.

For instance the sequence for the 5th death-onacci (m = 5) is given by

f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) - f(n-5)

And the first m-1 numbers is 0, followed by a single 1 (so for m=5 the sequence start 0 0 0 0 1)

Test cases:

Here are some test cases:

n f(n), m=3 f(n), m=4 f(n), m=5
0 0 0 0
1 0 0 0
2 1 0 0
3 1 1 0
4 2 1 1
5 2 2 1
6 3 4 2
7 3 6 4
8 4 11 8
9 4 19 14
10 5 32 27
11 5 56 51
12 6 96 96
13 6 165 180
14 7 285 340
15 7 490 640
16 8 844 1205
17 8 1454 2269
18 9 2503 4274
19 9 4311 8048
20 10 7424 15156
21 10 12784 28542
22 11 22016 53751
23 11 37913 101223
24 12 65289 190624
25 12 112434 358984
26 13 193620 676040
27 13 333430 1273120
28 14 574195 2397545
29 14 988811 4515065
30 15 1702816 8502786
31 15 2932392 16012476

You must write a function or program that takes one number M, and prints out the first 31 M-Death-onacci numbers. M will be a whole number larger than 0 and less than 31. The output can be in any human readable format, and you can take input in any reasonable manner. (Command line arguments, function arguments, STDIN, etc.)

As usual, this is Code-golf, so standard loopholes apply and the shortest answer in bytes wins!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Very similar. \$\endgroup\$ – Razetime Apr 24 at 9:57
  • \$\begingroup\$ @Razetime definitely, but hopefully different enough? \$\endgroup\$ – Pureferret Apr 24 at 10:02
  • \$\begingroup\$ Well, it's a WIP. You can go ahead and add more details which distinguish it. 'tis the sandbox, after all. \$\endgroup\$ – Razetime Apr 24 at 10:04
  • \$\begingroup\$ @Razetime how's it looking now? \$\endgroup\$ – Pureferret Apr 24 at 10:23
  • 1
    \$\begingroup\$ looks better, and the tests are more comprehensive. I suggest posting in TNB for other people's feedback. \$\endgroup\$ – Razetime Apr 24 at 11:11
4
\$\begingroup\$

Do I need a win streak?

\$\endgroup\$
10
  • 2
    \$\begingroup\$ taking P as a fraction seems fine, but it seems more convenient separately since we're just supposed to increment N and P till the desired ratio is achieved. What is the allowance for floating point errors on this question? \$\endgroup\$ – Razetime Apr 24 at 10:07
  • \$\begingroup\$ an additional "Streak bonus" for every x games might be an interesting addition. \$\endgroup\$ – Razetime Apr 24 at 10:08
  • 1
    \$\begingroup\$ @Razetime Oh did I say fraction, I meant a decimal value between 0 and 1, eg: 0.53 for 53%. There wont be more than two decimal places in the input so I doubt if any language will run into floating point errors at all. \$\endgroup\$ – Manish Kundu Apr 24 at 10:11
  • 1
    \$\begingroup\$ I updated the question to allow P as decimal. About the streak bonus, I think it might complicate things quite a bit so I am not going with that. \$\endgroup\$ – Manish Kundu Apr 24 at 10:21
  • \$\begingroup\$ You should clarify in the text if the inputs W, N can be taken separately or only as one number corresponding to W/N. And if so, please address Razetime's comment on floating point errors \$\endgroup\$ – Luis Mendo Apr 24 at 15:17
  • \$\begingroup\$ @LuisMendo Yes, taking them separately is fine. I updated the post again, please check if it is clear now. \$\endgroup\$ – Manish Kundu Apr 24 at 15:47
  • \$\begingroup\$ I'd suggest also allowing languages to take P as a fraction. Other than that, this looks good to go \$\endgroup\$ – Dude coinheringaahing Apr 24 at 16:09
  • 1
    \$\begingroup\$ I think they have to be taken separately. In the first example, if you take W/N as 0.2 you cannot compute the output, because you don't know if W=1, N=5, or W=2,N=10, or... \$\endgroup\$ – Luis Mendo Apr 24 at 17:32
  • 1
    \$\begingroup\$ Oh yes, you're right about that. You'd have to consider both the values to calculate the answer. \$\endgroup\$ – Manish Kundu Apr 24 at 19:01
  • 1
    \$\begingroup\$ @LuisMendo But if it somehow benefits you to take it say as a string of the form "W/N" with the original values of W and N, then that's fine too. I think the rules clarify that point. \$\endgroup\$ – Manish Kundu Apr 24 at 19:16
4
\$\begingroup\$

Gelatin integer metagolf

\$\endgroup\$
0
4
\$\begingroup\$

Drawing the Stack Overflow logo

\$\endgroup\$
14
  • \$\begingroup\$ I don't think restricting the language is a good idea. Move languages promotes diversity among submissions. However, I'm still new to the site so I'm not really sure. \$\endgroup\$ – EnderShadow8 Apr 30 at 4:32
  • \$\begingroup\$ Like Ender said, language-specific challenges are strongly discouraged - here, it doesn't add anything, so removing the restriction would improve the challenge by allowing a wider variety of approaches and solutions. \$\endgroup\$ – hyper-neutrino Mod Apr 30 at 4:34
  • \$\begingroup\$ Also, seeing as to how this is a ascii-art challenge, you will need to either provide the exact text that needs to be outputted or a formal specification of what is considered valid output and what isn't - for example, could I just submit . and claim it's a very zoomed out logo? These will need to be clarified. Overall, I like the idea though. \$\endgroup\$ – hyper-neutrino Mod Apr 30 at 4:35
  • \$\begingroup\$ I think if you require the output to be the exact example you gave it would make it much easier to determine which answers are valid. \$\endgroup\$ – Redwolf Programs Apr 30 at 5:15
  • \$\begingroup\$ @RedwolfPrograms It's the best I got, but I'll make it official. \$\endgroup\$ – Matt Sanchez Apr 30 at 5:20
  • \$\begingroup\$ This challenge looks pretty good now, so I've upvoted, although I'd still recommend waiting a day or two just in case anyone else has feedback on the formatting or finds something unclear. \$\endgroup\$ – Redwolf Programs Apr 30 at 5:28
  • \$\begingroup\$ A tip for future challenges: Anyone (not just you) reading the challenge and an answer should be able to decide (without disagreement) if the answer is valid or not. "Resembles a logo" is very subjective in this sense, and phrases like "as close as" should be avoided too. \$\endgroup\$ – Bubbler Apr 30 at 5:34
  • \$\begingroup\$ @Bubbler Is this better? \$\endgroup\$ – Matt Sanchez Apr 30 at 6:10
  • \$\begingroup\$ Yeah, it's better. A question: would you allow printing trailing spaces at the end of each line, or printing a trailing newline at the end? (These are commonly allowed because they don't impact the ascii art shown and they're hard to avoid in multiple languages) \$\endgroup\$ – Bubbler Apr 30 at 6:21
  • \$\begingroup\$ @Bubbler I added a list of questions that are asked in the comments. Can I add the same if I posted this on main? \$\endgroup\$ – Matt Sanchez Apr 30 at 7:39
  • \$\begingroup\$ I'd recommend to edit the challenge text directly to include any clarifications. \$\endgroup\$ – Bubbler Apr 30 at 7:45
  • \$\begingroup\$ @Bubbler It will do and I'm hoping that when this gets published, I gain enough reputation just to talk in chat. \$\endgroup\$ – Matt Sanchez Apr 30 at 7:50
  • \$\begingroup\$ Tags-wise: [kolmogorov-complexity]. I'd suggest just removing the 2 paragraphs beneath the output, as they just make it more confusing. A simple "output this exact text, with an optional trailing newline. Lines may have optional trailing spaces. Shortest code wins" is enough (plus the output itself) \$\endgroup\$ – Dude coinheringaahing Apr 30 at 17:35
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ – Dude coinheringaahing May 1 at 13:46
4
\$\begingroup\$

Time bomb KoTH

\$\endgroup\$
9
  • \$\begingroup\$ Enforcing determinism prevents luck based winning, which I personally like. Adds a sense of balance. \$\endgroup\$ – Razetime May 1 at 15:59
  • 2
    \$\begingroup\$ Determinism also means anyone can run a simulation of the game on their own machine. The game then devolves into aggressive metagaming and iteratively updating one's bots to always beat the opponents'. If you decide to enforce determinism among the bots, you must have some outside source of randomness to prevent players from simply simulating the entire game and instead actually formulate a strategy that is robust enough to still work well in the face of unknowns. \$\endgroup\$ – EnderShadow8 May 2 at 9:57
  • 1
    \$\begingroup\$ I personally like a bit of non determinism to spice things up but then this came along. So you have to be careful. \$\endgroup\$ – EnderShadow8 May 2 at 9:58
  • \$\begingroup\$ @EnderShadow8 yeah I saw that answer. In the current design, the array for the numbers selected in the previous round will be initialized with random numbers on the first round, giving the initial seed of randomness \$\endgroup\$ – leo3065 May 2 at 15:36
  • 1
    \$\begingroup\$ Another thing to consider: high numbers will have very small winning chances, and the entire game is biased towards low numbers (they come first, they don't subtract much, large numbers take many points on explosion vs large numbers give many points on success). So all "smart" bots will choose <= n / 2 numbers, but then the trigger will also be lower, so bots have to choose even lower numbers. That can lead to a case of positive feedback. It may or may not cause problems, but it may be good to keep that in mind. \$\endgroup\$ – FZs May 2 at 19:24
  • 1
    \$\begingroup\$ And to the determinism topic: a viable compromise between determinism and randomness could be made: making the only allowed non-deterministic part a seeded PRNG function provided by the controller. The PRNG seeds used for the official ranking are kept secret, but it's still possible to replicate the given match by using the same seed. \$\endgroup\$ – FZs May 2 at 19:58
  • 1
    \$\begingroup\$ @FZs That's true. I may need to buff the reward for larger numbers to encourage playing them. Also about the determinism topic, after some searching I found some method to provide a seeded random, and I think I'm going to try that. \$\endgroup\$ – leo3065 May 3 at 7:41
  • 1
    \$\begingroup\$ More about the determinism: I decided to decide the secret seed before the challenge starts and provide the hash to prove that I won't change the key mid-challenge. \$\endgroup\$ – leo3065 May 3 at 9:14
  • \$\begingroup\$ I've edited this down to a stub now that it's been posted to save space \$\endgroup\$ – Dude coinheringaahing May 3 at 14:17
4
\$\begingroup\$

Count up to 21

21 is a game my teachers had my classmates and I play in order to kill some time. The game works as follows:

  • All contestants stand in a circle. The aim is to count to 21, one by one.
  • At any time, any player may begin the counting by saying 1.
  • The plays then continue the counting by saying the next number. However, if multiple players say the number at the same time, the count resets, and someone has to say 1 again.
  • The first player who says 21 is "out", and the game begins again with the same contestants except for the "out" player(s)
  • The final player left is disqualified, and the entire game begins again. The last player not disqualified wins.

We are going to run a challenge, where bots aim to play this game.

You are to write a function in Python 3 that takes a list of lists \$L\$ as argument. Each list in \$L\$ represents a round in the game, with the last element being the most recent. The \$i\$th element of each list always corresponds to the same bot. Each list in \$L\$ will contain \$n\$ integers between \$0\$ and \$21\$, where \$n\$ is the number of contestants left in the game. The lists are either all \$0\$s, or are \$n-1\$ \$0\$s and a single non-zero value \$v\$.

If a list is all \$0\$s, either it is the first round, or the counter was reset in the previous round.

That function should then return either:

  • \$0\$, meaning that your bot stays quiet
  • \$v+1\$, meaning that your bot is attempting to guess this round

And that's it!


The competition will work exactly as described above. The controller will run 100 games. Each game will works as follows:

  • The first round begins with all \$n\$ contestants. They will count up to 21, eliminating each contestant as they count to 21, and resetting the count to 0. The final player left is then eliminated, and the next round with \$n-1\$ contestants is run. At the end, the final player left standing wins
  • The player with the most wins after 100 games wins overall

You may not include anything in your submission that attempts to communicate with other submissions, attempts to interfere with other submissions or the controller or anything that could be malicious. If you do, your submission will be disqualified

If any game has more than 10000 rounds, it'll be terminated and no player will win.


Example bot

This is Random:

import random

def bot(history):
	return random.choice([0, max(history[-1]) + 1])
\$\endgroup\$
12
  • 7
    \$\begingroup\$ Infinite loops might happen quite often \$\endgroup\$ – Redwolf Programs Apr 28 at 1:51
  • 1
    \$\begingroup\$ @RedwolfPrograms Put a limit of 10000 rounds per game \$\endgroup\$ – Dude coinheringaahing Apr 28 at 20:32
  • \$\begingroup\$ TNB Feedback link \$\endgroup\$ – Dude coinheringaahing Apr 28 at 21:16
  • 2
    \$\begingroup\$ So, if next number is 21: Is there any reason a bot will not to say 21 in that round? \$\endgroup\$ – tsh Apr 29 at 1:30
  • 2
    \$\begingroup\$ I feel like someone's going to just add a bot to say every single number no matter what. \$\endgroup\$ – emanresu A Apr 29 at 10:54
  • \$\begingroup\$ @tsh If multiple bots say 21, none of them win and the count resets \$\endgroup\$ – Dude coinheringaahing Apr 29 at 11:51
  • \$\begingroup\$ Can you post the code to run the game so we can test our bots? \$\endgroup\$ – fasterthanlight Apr 29 at 21:05
  • \$\begingroup\$ @fasterthanlight I haven't written the controller yet, so no \$\endgroup\$ – Dude coinheringaahing Apr 29 at 22:57
  • 2
    \$\begingroup\$ but if i will lost their turn if i dont say 21, and the worst case is a tie if I say 21? So any reason I try to be silent? \$\endgroup\$ – tsh Apr 30 at 5:10
  • 2
    \$\begingroup\$ Because there's no reason to not say 21, infinite loops are probably going to occur no matter what. You might want to consider adding a rule regarding this to prevent infinite loops (or if everyone but 1 says a number the bot who said 0 can be eliminated) \$\endgroup\$ – fasterthanlight Apr 30 at 12:44
  • \$\begingroup\$ Just wondering, is saving state between different turns allowed? Or between rounds? Or between games? You also don't seem to distinguish between rounds and turns (i.e times when the count resets vs. opportunities to guess), which may cause confusion. Also, a suggestion: Maybe let each game have only a small subset of the bots as contestants, so that if there's that one bot who always says 21 as soon as possible, it would just harm itself rather than ruining the challenge. (Sorry for this long block of text.) \$\endgroup\$ – Andrew Li May 4 at 3:42
  • \$\begingroup\$ Interestingly, this is completely different from the game of 21 I know. \$\endgroup\$ – pxeger May 23 at 15:57
4
\$\begingroup\$

Challenge Statement

The goal of this challenge is to build the 5 state Infinite Time Turing machine that takes the longest to halt.

The rest of this challenge is some definitions and an example to help you.

Turing Machines

For clarity we will define the Turing machines as used for this problem. This is going to be rather formal. If you are familiar with Turing machines this is a single-tape, binary Turing machine, without an explicit halt state, and with the possibility of a no shift move. But for the sake of absolute clarity here is how we will define a classical Turing machine and its execution:

A Turing machine consists of a \$3\$-Tuple containing the following:

  • \$Q\$: A finite non-empty set of states.
  • \$q_s : Q\$: The initial state.
  • \$\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$: A partial transition function, which maps a state and a binary symbol, to a state, a binary symbol and a direction (left, right or no movement).

During execution of a specific Turing machine the machine has a condition which is a \$3\$-Tuple of the following:

  • \$\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$: The tape represented by a function from an integer to a binary symbol.
  • \$k_\alpha :\mathbb{Z}\$: The location of the read head.
  • \$q_\alpha : Q\$: The current state.

For a Turing machine the transition function takes the condition of a machine at step \$\alpha\$ and tells us the state of the machine at step \$\alpha + 1\$. This is done using the transition function \$\delta\$. We call the function \$\delta\$ with the current state and the symbol under the read head:

\$ \delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$

If this does not yield a result, then we consider the machine to have halted at step \$\alpha\$, and the condition remains the same. If it does yield a result \$\left(q_\delta, s_\delta, m_\delta\right)\$ then the new state at \$\alpha+1\$ is as follows:

  • \$\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\$ (That is the tape replaces the symbol at the read head with the symbol given by \$\delta\$)
  • \$k_{\alpha+1} = k_\alpha+m_\delta\$ (That is the read head moves left right or not at all)
  • \$q_{\alpha+1} = q_\delta\$ (That is the new state is the state given by \$\delta\$)

Additionally we define the condition of the machine at time \$0\$.

  • \$\xi_0(k)=0\$ (Tape is all zeros to start)
  • \$k_0=0\$ (Read head starts a zero)
  • \$q_0=q_s\$ (Start in the initial state)

And thus by induction the state of a Turing machine is defined for all steps corresponding to a natural number.

Infinite Ordinals

In this section I will introduce the concept of transfinite ordinals in a somewhat informal context. If you would like to look up a more formal definition this explanation is based of of the Von Neumann definition of ordinals.

In most contexts when talking about the order of events we use natural numbers. We can assign numbers to events such that events with smaller numbers happen earlier. However in this challenge we will care about events that happen after an infinite number of prior events, and for this natural numbers fail. So we will introduce infinite ordinals.

To do this we will use a special function \$g\$. The \$g\$ function takes a set of numbers and gives us the smallest number greater than all the numbers in that set. For a finite set of natural numbers this is just the maximum plus 1. However this function is not defined on natural numbers alone. For example what is \$g(\mathbb{N})\$, or the smallest number greater than all naturals. To create our ordinals we say

  • \$0\$ exists and is an ordinal.
  • If \$X\$ is a set of ordinals then \$g(X)\$ exists and is an ordinal.

This gives us the natural numbers (e.g. \$1 = g(\{0\})\$, \$2 = g(\{1\})\$ etc.) but also gives us numbers beyond that. For example \$g(\mathbb{N})\$, this is the smallest infinite ordinal, and we will call it \$\omega\$ for short. And there are ordinals after it, for example \$g(\{\omega\})\$ which we will call \$\omega + 1\$.

We will in general use some math symbols \$+\$, \$\times\$ etc. in ways that are not defined explicitly. There are precise rules about these operators, but we will just use them as special notation without definition. Hopefully their use should be clear though. Here are a few specific ordinals to help you out:

\$ \begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\ \omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\ \omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z\in \mathbb{N}\})\\ \omega^\omega &=& & & g(\{\omega^x\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\})\\ \end{eqnarray} \$

If an ordinal is not the successor of another ordinal, meaning there is not a next smaller ordinal, we call that ordinal a limit ordinal. For example \$\omega\$, \$\omega\times3\$, and \$\omega^{\omega\times 2}+\omega^6\times 4\$ are all limit ordinals. \$3\$, \$\omega\times 5 + 12\$ and \$\omega^{\omega^\omega}+1\$ are not. Some authors will specify further that 0 is not a limit ordinal, we will be explicit about 0 when we talk about limit ordinals to avoid confusion.

Infinite Time Turing Machines

A classical Turing machine is equipped with a start status, and a way to get from one status to another. This allows you to determine the status of the machine at any finite step.

Infinite time Turing machines extend classical Turing machines to have a defined status non-zero limit ordinals as well. That is ordinals as defined above which are not the successor of any previous ordinal. This addition makes the condition of the machine defined at transfinite time as well.

Formal definition

For this we add an additional object to the machine's definition

  • \$q_l : Q\$: The limit state

And we define the condition of the machine at some limit ordinal \$\lambda\$ to be

  • \$\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$
  • \$k_n = 0\$
  • \$q_n = q_l\$

\$\$

Example

Here we have a diagram of the current 2-state champion:

2-State champion If we want to calculate how long this takes to halt we can't just throw it into a computer and run it, rather we have to determine it by hand.

To start we follow the machine through it's normal execution. It starts at \$q_1\$ and we can see that from there it always moves to \$q_2\$ flipping the cell under the read-write head. So here it turns the cell on. Then since the cell is on it will transition back to \$q_1\$, turning the cell off and moving to the right. This puts us in the exact same condition as the start, except the read-write head has advanced by 1. So it will continue in this loop of flipping on bit on and off and moving to the right endlessly.

ANIMATION 1 HERE

Now that we have determined the behavior of the machine for all finite steps we can figure out the state at step \$\omega\$. Each cell is on for at most 1 step, before being turned off, and then it is never on again. So the limit supremum of each cell is \$0\$, and at step \$\omega\$ the tape is entirely empty.

So this means that after \$\omega\$ the machine just repeats its exact behavior, the condition at step \$\omega+n\$ is the same as the condition at step \$n\$. And this persists even after we hit another limit ordinal, \$\omega+\omega\$, the tape remains blank and just repeats the same behavior over and over.

ANIMATION 2 HERE

So we now have an accurate description of the machine for states of the form \$\omega\times n + m\$, and it doesn't halt for any of those steps. It just repeats the same infinite pattern an infinite number of times. So now we can look at the step after all the steps we have described. We take the next limit ordinal:

\$ g(\{\omega\times n + m : n\in \mathbb{N}, m \in \mathbb{N}\}) = \omega\times\omega = \omega^2 \$

Your first instinct might be that the tape will be completely empty again, since it was empty at every step \$\omega\times n\$. However with infinities instincts can be misleading, so we should look at the definitions carefully instead.

In order for a cell to be zero it must converge to zero. Since the only possibilities are zero and one, this means that for each cell there must be some step \$x\$ after which that cell is always zero. Previously since each cell was only turned on once that step was just the step after it was turned off.

Now if such a step were to exist for a cell \$k\$ it would be of the form \$\omega\times n + m\$, however we know that the cell will be turned on again some time during the \$\omega\times(n+1)\$ iteration. In fact it will be turned on at exactly step \$\omega\times(n+1) + 2k + 1\$.

So no cell (with a non-negative index) will converge to a stable value. Meaning that by the limit supremum all non-negative cells will be on at time \$\omega^2\$.

ANIMATION 3 HERE

So here we finally get some new behavior. With cell 0 on, the machine transitions to \$q_2\$ turning the cell off, and since \$q_2\$ doesn't have a transition for off cells the machine halts.

This gives us a total of \$\omega^2+1\$ steps until halting.

\$\endgroup\$
3
  • \$\begingroup\$ It'd be nice to link the ITTM paper. Also, showing an example ITTM and explaining its halting time (like your ⍵×⍵ 2-state ITTM) would be helpful. \$\endgroup\$ – user41805 May 7 at 12:39
  • \$\begingroup\$ @user41805 I'm currently working on an explanation for my 2-state ITTM champion. But the animations are a bit time consuming. I meant to link some ITTM papers, so I will add those links when I finish the edit I am working on. Thanks. \$\endgroup\$ – Wheat Wizard Mod May 7 at 12:42
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/36747/45613 and codegolf.stackexchange.com/questions/18028/… (This doesn't seem to be a duplicate) \$\endgroup\$ – Beefster May 18 at 16:25
4
\$\begingroup\$

Reveal by Halves (in need of a better name)

Inspired by this: http://nolandc.com/smalljs/mouse_reveal/ (source).

A valid answer:

  • Takes a number \$w\$ and (assumed non-negative) integer \$x\$.
  • Outputs an integer list with a length of \$2^w\$, initially filled with zeroes.
  • For each number \$n\$ from \$0\$ to \$w-1\$ (inclusive), divide the list into sub-lists of size \$2^n\$, then increment all of the values in the sub-list that contains the index \$x\$.

Examples

(with coordinates from left, 0 indexed, but your answer may have change these)

w=3, x=1
23110000

w=2, x=2
0021

w=3, x=5
00002311

w=4, x=4
1111432200000000

w=2, x=100
Do not need to handle (can do anything) because x is out of bounds

Meta questions

  • Are these tags fitting?
  • Would this be better in one dimension? (like \$3, 2\$ returns 11320000) Edit: I've changed it to one dimension but I can revert if it makes it less interesting.
  • Should \$w\$ or \$2^w\$ be the input?
  • Is this a duplicate?
\$\endgroup\$
1
  • 1
    \$\begingroup\$ My opinions on some meta questions. 1) I think one dimension would be better, the core of the challenge remains the same but the challenge itself becomes more "pure" which, in my opinion, is a good thing. 2) I'm a fan of flexible I/O, so if it were up to me I'd let people choose if they want \$w\$, \$2^w\$ or both as input. If you don't like this, both options are honestly fine. \$\endgroup\$ – Delfad0r May 10 at 22:24
4
\$\begingroup\$

I'm Lazy*: Top-left align my text

posted

\$\endgroup\$
2
  • \$\begingroup\$ Definitely not too trivial for code golf \$\endgroup\$ – qwr Jun 2 at 14:20
  • \$\begingroup\$ I think squash up could be its own challenge which has room for simplification. My thoughts being using a transposed grid of strings, which I guess can work for this challenge too \$\endgroup\$ – qwr Jun 2 at 14:21
4
\$\begingroup\$

Demonstrate some advanced abstract algebra

\$\endgroup\$
10
  • \$\begingroup\$ I think we should be able to define the types and values of S, rather than necessarily using integers. In that case, - and + would not (necessarily) be actual arithmetic negation and addition, so maybe they would have to be renamed to use other symbols (or just use function syntax f(a,b)?) \$\endgroup\$ – pxeger May 31 at 8:50
  • \$\begingroup\$ And do all 9 functions have to operate on the same set S? I think it could be more interesting if they didn't have to, but it might result in cheating/loopholes. Also, what does "uniquely exhibits" mean exactly? Demonstrates exactly one of the 9 properties? \$\endgroup\$ – pxeger May 31 at 8:52
  • \$\begingroup\$ In fact, I think people will just submit "addition, addition, multiplication, subtraction" for the first 4 at least, and I suspect they will almost always be the shortest option in most languages so it might not be very interesting as it is \$\endgroup\$ – pxeger May 31 at 9:04
  • \$\begingroup\$ Writing one program is hard enough. Writing 9 seems like a lot to ask. I think you could make a stripped down challenge using just commutativity and associativity. I barely known any abstract algebra. I think these varieties are called magmas? \$\endgroup\$ – qwr Jun 2 at 14:54
  • \$\begingroup\$ Is this even possible with the surjectivity condition? You should provide an example of each program. \$\endgroup\$ – qwr Jun 2 at 14:57
  • \$\begingroup\$ @qwr I don't have examples for each program, and even if I did, I wouldn't include them as that would just lead to people porting them into their own languages. Yes, I believe magma is the correct term for \$*\$ here. I'm not sure if this is possible, but I'd be surprised if it isn't. I've allowed for an answer to be a proof of impossibility however, on that off-chance. \$\endgroup\$ – Dude coinheringaahing Jun 2 at 15:04
  • \$\begingroup\$ Well it's more than a magma since you added more two more operators right \$\endgroup\$ – qwr Jun 2 at 15:18
  • \$\begingroup\$ @qwr No, I believe a magma is just a pair, the binary operator and the set its closed on, no matter the additional operators defined on that set \$\endgroup\$ – Dude coinheringaahing Jun 2 at 15:31
  • \$\begingroup\$ This is a really cool problem. It is hard so I wouldn't be again having a separate "easy" version with just the main three: commutative/associative/distributive. Uniquely exhibiting those is already a nontrivial and neat challenge. I don't know if others would vote a dupe, but I'd def be in favor of having both. As is, I don't think the harder version will have a lot activity. But I do think an easier one would! \$\endgroup\$ – AviFS Jun 13 at 1:18
  • \$\begingroup\$ @AviFS I do actually have an easier version Sandboxed, where I think they're clearly separate enough to not be dupes. \$\endgroup\$ – Dude coinheringaahing Jun 13 at 1:42
4
\$\begingroup\$

Reconstruct a recursively prime-encoded integer

\$\endgroup\$
1
  • \$\begingroup\$ Looks great! At first glance seems easy but it's actually a little more difficult. I think it's ready to post, although you might want to wait a day or so. \$\endgroup\$ – Recursive Co. Jun 20 at 12:14
1
7 8
9
10 11
115

You must log in to answer this question.

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