What is the Sandbox?

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

See the Sandbox FAQ for more information on how to use the Sandbox.

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

• How are tags added to questions? – guest271314 Jan 9 at 7:51
• @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] – DJMcMayhem Aug 29 at 15:19
• Why no featured anymore? Can't we have it auto-added or something? – JL2210 Sep 26 at 15:57
• @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary – caird coinheringaahing Sep 29 at 13:43
• I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . – AZTECCO Oct 5 at 19:39

Concatenate my strings!

As you know, we all like to save bytes around here. So, my strings are special: they come in four different flavours depending on the highest code point in the string:

• ASC (code points up to 0x7F). Like ISO but all bytes have values less than 0x80.
• ISO (code points up to 0xFF). Each byte represents a code point.
• UTF (code points up to 0x7FF). Uses UTF-8 encoding.
• UCS (code points up to 0xFFFF). Uses UCS-2 encoding.

For input you will receive two strings, each represented by a flavour identifier and a sequence of bytes representing the code points according to the flavour. You then need to output a byte sequence using the best flavour to hold the concatenation. Except where limited by standard loopholes, you don't need to use the designations ASC, ISO, UTF and UCS, so for instance if you choose to use numbers 0-3 for the flavours then the output flavour is simply the maximum of the two input flavours.

Example:

ISO 43 6F 64 65 A0 + ASC 47 6F 6C 66 = ISO 43 6F 64 65 A0 47 6F 6C 66


This is , so the shortest program or function wins!

• how do you define the best flavor for concatenation? im guessing 'shortest'... but it would help to say it. also maybe a few more examples? – don bright Jul 7 '18 at 2:22
• @donbright "depending on the highest code point in the string" – user202729 Jul 7 '18 at 4:49
• @donbright You can do it depending on the highest code point, but you can just assume the highest code point of the input strings given their flavour if it's easier. – Neil Jul 7 '18 at 10:04
• oh i get it now. thanks. i like this. – don bright Jul 7 '18 at 14:13
• Well, I still don't get it - (1) why do you say "code points up to 0x7FF" for UTF-8? UTF-8 can encode codepoints up to 10FFFF. Do you mean some byte-limited variant of UTF-8? (2) except for UTF-8, it seems the task is just to choose the higher encoding ("maximum of the two input flavours" as you say), and possibly add 00 prefix bytes if output flavour is UCS-2. Is UTF-8 intended to be the main part of the challenge? Or am I missing something? (More examples and test cases would probably help by the way.) – sundar Jul 8 '18 at 19:43
• @sundar Because U+0800 takes 3 bytes in UTF-8 but only 2 in UCS-2, I'm pretending that I'm choosing the golfiest encoding for the bytes... I didn't want the challenge to get bogged down in the detail of choosing which encoding was best for a given string. Also, 00 suffix bytes only helps for some of the conversions. – Neil Jul 8 '18 at 20:59

Count binomial coefficient entries

This task is very simple. For integer $n \ge 0$, given the binomial coefficients of all the expansions of $(x+y)^m$ for $0 \le m \le n$, count the number of occurrences of $n$. This is OEIS A003016.

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

Smallest Match-3 Game

I was reading about Match Three games, games about manipulating a field of symbols to generate lines of three or more matching symbols, and was thinking a playable game would be a pretty short program, if golfed.

The reason I think that is because it has less rules than Chess, so I thought that when golfed it'd be a simpler program shorter than the Smallest chess program, which uses 487 bytes of Assembly, or less than 2 MB in any language used to answer that question.

Here's the other questions on this site, relating to Match-3 games:

Question:

How small can a Match-3 Game Program be?

Rules

• The symbols used can be any ones you want, just have at least 3 different symbols.

• At least a 4x4 board. Board size can be customized, if that's somehow easier.

• Board must start with a valid configuration, can stall player interaction and visibly reform the board, but player action must only be start to be allowed on a valid board.

• Any method of moving symbols is allowed. It could be sliding rows around, instead of swapping the positions of pieces, either side by side or anywhere on the board, or some other innovative way of moving pieces. But the board starts filled, and you move the symbols already there.

• Any method of selection of what to move is allowed.

• When a match happens, it's removed, and new pieces arrive, somehow. They don't have to fall from the top.

• It'd be nice if it could detect when there's no more valid moves.

• Random progression instead of deterministic would be nice as well.

Sandbox Questions

Not sure how much variability in the end result I should have. I want to have maximum customization.

I suppose I could have the score for each entry be something like:

Bytes of code - average number of bytes used to implement each optional feature.

• what is match-3? – don bright Jul 7 '18 at 2:45
• Yeah, it would be good to have a short description of the game, to keep the question self-contained and make sure we're all on the same page. Also might be good to mention at the start that you're looking to golf a playable, interactive version of the game, and not a solver or anything like that (which is what I initially assumed). – sundar Jul 8 '18 at 19:23

An example text for scrambled-words experiment. Version 1

Introduction

This challenge is based on an old experiment that proves that we only need first two and last two letters in order to uniquely identify a word. The remaining middle-characters can be completely scrambled and yet we should not have any problems in reading the whole word. And the speed of reading even longest scrambled-words based text shouldn't be significantly longer than reading an "normal" text.

The challenge itself is to write a shortest possible code (any language) that can be used to generate test texts to prove above described idea.

The experiment in the background of this challenge was conducted many years ago by some English or American scientist. I can't credit particular source or recall any other details. The challenge itself is created by me.

Challenge

Write the shortest possible code to generate test text (any length) based on following algorithm:

1. For each word in input text.
• If word is 5 characters long or less -- keep it unchanged.
• If word is 6 characters long or longer -- keep first two and last two characters unchanged and scramble remaining ones.
2. Print generated resulting text with scrambled words.

There there no corner cases except for two assumptions:

1. Words with 5 characters and less should be kept untouched.
2. Your code must support all UTF-8 characters, not just English / non-Latin alphabet.

I assume "standard" approach here, so the winner of the challenge will be determined by the length of the code.

Example Input and Output

Input:

• This challenge is based on an old experiment.
• Print generated resulting text with scrambled words.

Output:

• This chllenage is based on an old exripmeent.
• Print gertaneed reitlusng text with scbrmaled words.

An example text for scrambled-words experiment. Version 2

Challenge

The extended version of this challenge adds only one new assumption to base / above algorithm:

1. For each word in input text.
• If word is 4 characters long or less -- keep it unchanged.
• If word is 5 characters long -- keep first and last character unchanged and scramble remaining three.
• If word is 6 characters long or longer -- keep first two and last two characters unchanged and scramble remaining ones.
2. Print generated resulting text with scrambled words.

And again:

1. Words with 5 characters 4 characters and less should be kept untouched.
2. Your code must support all UTF-8 characters, not just English / non-Latin alphabet.

Example Input and Output

Input:

• This challenge is based on an old experiment.
• Print generated resulting text with scrambled words.

Output:

• This chllenage is baesd on an old exripmeent.
• Pirnt gertaneed reitlusng text with scbrmaled wrods.
• See codegolf.stackexchange.com/q/9261/194 and the "Related questions" in its sidebar. This isn't identical, but I don't think it adds anything interesting. – Peter Taylor Jul 12 '18 at 16:41
• I agree with @PeterTaylor; I don't think the differing lengths of what and when to scramble make this sufficiently different from the challenge he linked. Personally, I would dupe hammer this. Don't let that discourage you though; this was a well-written challenge for a newcomer and it's great to see a newcomer making use of the Sandbox. Welcome to PPCG! :) – Shaggy Jul 13 '18 at 22:43
• I totally agree with both of you that moving this challenge out of Sandbox would produce us a perfect dupe! :> So, obviously, I am not going to do this. I have only one supporting question here. Do we have any tools / ways here at Code Golf to encourage particular language? Among all answers to question you pointed out there are no trace of solution in Javascript or any other way I could run this in a browser. Do I have any option to encourage such solution, if I need it (i.e. some bounty etc.)? – trejder Jul 16 '18 at 11:58
• @trejder Yes, you can put a bounty on the list of bounties with no deadline. That means you offer a multiple of 50 (up to 500) of your own reputation. – wastl Aug 1 '18 at 14:08
• @wastl Thanks for the suggestion, but I decided to go with a "regular" bounty instead. – trejder Aug 5 '18 at 7:49

Two functions with same input/output, with largest difference in bytes.

This challenge is a terrible idea. Don't try submitting it or anything similar!

Provide two functions with the largest difference in bytes. (These two functions will be referred to in bold italics to distinguish them from built-in functions available in your language in the rules below.)

Rules:

1. Both functions must take an input and must produce an output. The input to and output from both functions must be identical.

2. Both functions must be explicitly named. The function names must have the same byte count.

3. You may not define any other functions.

4. If you use a built-in function your language provides, it must be used with the same number of parameters in each of the functions.

5. You may use string/numeric literals or any built-in constants, but you must use exactly the same ones in both functions.

6. You can define variables, must you must use the same variable names in both functions.

7. You can use comments, no-ops, and the equivalent, but they must be the same in both functions.

8. Both functions must contain the same amount of whitespace (or equivalently, don't count whitespace at all.)

9. You can import libraries/packages and the equivalent, as long as you import the same ones for both functions.

10. You can use pre-processor directives as long as they are the same for both functions.

If any of these rules mean your language cannot compete, so be it.

Not really sure how to tag this. A little bit of and .

• I don't think this is a good idea. {Main downvote} – user202729 Jul 12 '18 at 16:26
• Give up. E.g. in APL, ⊢ and ⊢⊢⊢⊢⊢⊢⊢⊢⊢ do the same. – Adám Jul 12 '18 at 16:26
• @Adám, with those rules, it'd be something like f←⊢ and g←⊢(⊢(⊢(⊢(...)))) due to rules #2 and #3. The same thing still applies to OP: give up! – Zacharý Jul 12 '18 at 16:36
• Thank you. I am happy to give up! – ngm Jul 12 '18 at 16:56
• @Zacharý I intended them to be dyadic, but whatever… – Adám Jul 12 '18 at 17:18
• "Both functions must take an input", which I assume would restrict the functions to monadic. – Zacharý Jul 12 '18 at 17:39

Maximal number of programming languages in 1KiB

In this code-challenge your task is to write a program/function with a maximum of 1024 bytes, the goal is to interpret/compile as many programming languages as possible.

Rules

You're free to use any combination of inputs and outputs as you wish.

Input

Inputs will be the name1 of the programming language and the source code.

The inputs can be

• read from a file (you may hardcode a filename if it helps)
• taken as command-line arguments
• taken as function arguments
• a combination of the above

1: you may choose to encode them, as long as the encoding is bijective - for example numbering the languages 1 through n.

Output

The output can be

• the resulting side-effects of interpreting the program in the specified language
• valid machine code that produces the above

What is a programming language?

For the purpose of this challenge a programming language needs to be

• Turing-complete
• publicly listed, as in having one of the following:
• released before 13. July 2018
• able to do I/O

What does my interpreter/compiler need to implement?

For each of the chosen programming languages, your program does not need to implement the full language. It suffices to implement a working subset of it as long as it stays Turing-complete.

Scoring

The answer that implements the greatest number of different programming languages wins.

Sandbox

• Should I leave the source size restriction and use a different scoring, eg. $\frac{\#bytes}{\#langs ^ n}$ for some $n \ge 1$?
• Should I disallow using polyglotting (maybe eval could be used several times that way which would be boring)?
• How should I properly define different programming languages (should I count different versions as 1 each)?
• Additional places for entries, descriptions of programming languages?
• Missing tags or other suggestions?
• Given that Perl can do BF in 120 bytes, I would think a bunch of BF derivatives like Ook could be tacked on for very little overhead, which would seem to break your scoring system. I'm not sure how to rule that out, though. – AdmBorkBork Jul 13 '18 at 16:20
• @AdmBorkBork: It kind of depends on what derivatives, I guess. You're right, I need to figure out a good way to rule out counting derivatives which just extend BF, otherwise it would be boring.. An idea would be: For each language you must give a program achieving some trivial task X and it isn't allowed to work in any other language. – ბიმო Jul 13 '18 at 17:01
• @FryAmTheEggman: You're free to determine language by looking at the source, however you're given the name as input: "Inputs will be the name of the programming language and the source code." Just looked in meta and found this, so I will remove the notice that you can ignore that input (I didn't know that before and didn't want to prevent people from determining the language themselves). – ბიმო Jul 13 '18 at 20:18
• Sorry, I missed that! Maybe it would be better to put that at the start of the input section? Something like: "Your interpreter will be given the source and language names as inputs inn one of the following ways: ..." perhaps? – FryAmTheEggman Jul 13 '18 at 20:21
• @FryAmTheEggman Thanks for the feedback! I put it to the beginning of that section and removed the notice about encoding further information (it's a standard loophole anyways and doesn't make things clearer). – ბიმო Jul 13 '18 at 20:29

Quiet QR

Your mission, should you choose to accept it is to infiltrate the top secret HQ of the Big Bad Evil Guy (TM) and extract information on their latest evil scheme saved in the file Plan.txt.

The target PC is isolated from any and all network connections, and you can't physically connect anything to it. The server room is equipped with sound sensors that will detect key presses.

Your tools are restricted to a mobile phone equipped with a QR code reader. Your recommended course of action is to write a code on the target machine that will display the file content as QR code.

You are to complete the mission with the least number of keystrokes as to minimise the sound generated by the mechanical keyboard.
It is advisable not to use languages that require unicode characters as entering one character will require multiple key presses (Eg:þ = Alt+0254) is considered 5 keystrokes.

You are to assume that the machine will have its terminal open and ready for input at the root directory of the system (C:\> or /).

All programming languages can be accessed directly from root folder. The target file is on the root folder.

Javascript is available as command line executable named js usable as (js filename) and prints output.

Image viewer is called view and usable as (view imagefile) [Extension is not needed]

Possible ways of output:

1. An image containing the QR code

2. ASCII art depicting the QR code using characters like █ ▄▀

4. Other formats of 2D barcodes are accepted on the condition of being readable by a standard reader.

Example Solution for batch file:

copy con a.bat
open file Plan.txt
echo █ ▄▀
^Z
a


=59 keystrokes.

The symbols are 4 keystrokes each:

• ▀ Alt+991

• █ Alt+987

• ▄ Alt+988

^Z as Ctrl+z and is considered 2 ketstrokes (F6 is considered one).
New lines and spaces are one keystroke each.
Capital letters are 2 strokes (Shift+c).
CAPITAL words are one keystroke added to the length of the word (Shift+capital).
No need to clean the screen at the end because the evidence will be erased by a Micro-EMP device that will disable the machine.

• Why not just have a question to turn text into a QR code? The keystroke golfing just seems to complicate things – Jo King Jul 18 '18 at 11:54
• @JoKing The premise of the challenge is to extract information from a pc with the least keystrokes. – workoverflow Jul 22 '18 at 9:06
• In that case, what operating system is the PC? What type of QR code do you want (alphanumeric or byte?)? Can you add a link or explain an algorithm to generate you type of QR code (questions should be self-contained)? How big can the input be (100 bytes? 1kb?), and what characters can it contain? – Jo King Jul 22 '18 at 9:15
• You may assume that the PC have an open terminal window ready for input in whatever OS you'd want (Bash, PowerShell, Command prompt,.....) The QR code must be able to encode alphanumeric+punctuation text in the file Plan.txt – workoverflow Jul 24 '18 at 10:29

Irrational Array indexing Starts at 3.

I came across the following brilliant comment, which suggests that subsequent sets of digit from pi should be used to Index an array, from a user named on the r/programmer humor subreddit context for the curious.

To fix the duplicate problem, instead take an extra digit whenever you are about
to duplicate a key: arr[3], arr[1], arr[4], arr[15],
arr[9], arr[2], arr[6], arr[5], arr[35] and so on.

Exercise for the reader: write a program that outputs the nth index of this array, and describe for yourself the limitations of the program (what is the maximum value of n? what is the minimum?)


Your task (should you choose to accept it), is to implement a function (or rather pair of functions/ (pair of full programs/ one of each)) that converts to and from this cutting-edge choice.

You may either write a single function that receives two inputs one being an integer input, and two being which way to go, or you can write a pair of functions and your score will be the sum of their sizes.

Put another way, implement both f(x) and $f^{-1}(x)$ according to this table. You may also instead implement f(x-1), and $f^{-1}(x)$ + 1 (1 indexed arrays), but you will get some stern looks.

x f(x)
------
0 3
1 1
2 4
3 15
4 9
5 2
6 6
7 5
8 35
19 950
21 841
41 6280


This problem is essentially identical to OEIS A064809, although the table there is one indexed.

This is code-golf, so shortest code in bytes wins. As always, you may use any programming language, but standard loopholes are prohibitted. What is allowed though, is that at no penalty you may optionally take in a second or third input with the first 10,000 digits of pi. Your code must work with 0<=x<=1000. Even if you choose to receive pi as input, I'll personally encourage you to write one that doesn't require pi as input, It'll obviously be unscored, but you'll earn some imaginary internet points.

• Note that we have mathjax now so you could write $f^{-1}(x)$ etc. You may also want to include the first 3-digit number in the examples. I also expect that every answer will choose to take the optional input, except for those that already have access to the digits of pi. – FryAmTheEggman Jul 18 '18 at 20:41
• I suspect it too. I figured having to dynamically compute all of the digits of pi was a bit beyond the scope of challenge, but I really wanted to see answers that don't. – Rohan Jhunjhunwala Jul 18 '18 at 21:36
• I think they might be different enough to be posted as two different challenges, but its a bit borderline so I'd definitely either ask chat or meta if you wanted to do that. Otherwise, there's not a particularly good reason not to require calculating digits of pi in this way, I think? So if that's the question you'd rather ask then go ahead. The only significant difference will probably be receiving fewer answers, and the only real drawback could be that people say its a dupe of finding pi to an arbitrary number of digits, perhaps. – FryAmTheEggman Jul 19 '18 at 5:41
• This is OEIS entry A064809. I actually had an idea for a similar challenge recently of splitting a given string into substrings in such a way as to avoid duplicate substrings. – Shaggy Jul 19 '18 at 8:27
• "but standard loopholes are permitted" <- prohibited perhaps? "If you choose to not take in this input, your code must work with 0<=x<=1000" <- does this mean there's a different limit for those who do take that input? (It looks like with 10000 digits you'd be able to handle upto x = 2675.) – sundar Jul 19 '18 at 11:57
• Definitely post 2 different challenges. – user202729 Jul 19 '18 at 14:25
• should I link them? – Rohan Jhunjhunwala Jul 19 '18 at 16:05
• @sundar I'll make that limit apply to both. I'll still give you 10k digits of pi though, out of "kindness". – Rohan Jhunjhunwala Jul 19 '18 at 16:07

Projective related points

Points A, B, C, D and A′, B′, C′, D′ are related by a projective transformation if their cross ratios are equal.

Given A, B, C, D four ordered points on a line, their cross ratio is defined as:

$\displaystyle\frac{distance(A,C)\times distance(B,D)}{distance(A,D)\times distance(B,C)}$,

where $distance(A,C)$ is the Euclidean distance between points A and C.

Challenge

Given a set of eight points, say if yes or no the set can be splited into two subgroups (each subgroup with four points) where the two subgroups are related by a projective transformation.

Input

A set of 8 points, each point defined by its Cartesian coordinates (integer coordinates).

Output

Either a specific true output (true, 1, yes, ...) or a specific false output (false, 0, no, ...).

Example

{(10,100),(25,100),(2,63),(2,33),(31,100),(2,13),(2,3),(17,100)} --> true
with subgroups:
{(10,100),(25,100),(31,100),(17,100)}
and
{(2,63),(2,33),(2,13),(2,3)}

{(45,54),(8,23),(8,8),(8,29),(27,30),(15,14),(9,6),(8,15)} --> true
with subgroups:
{(8,23),(8,8),(8,29),(8,15)}
and
{(45,54),(27,30),(15,14),(9,6)}


Hint (no need to use division or square root)

In order to avoid floating points, you can use the fact that points A, B, C, D and A′, B′, C′, D′ are related by a projective transformation implies:

$distance^2(A,C)\times distance^2(B,D)\times distance^2(A',D')\times distance^2(B',C')$

equals

$distance^2(A',C')\times distance^2(B',D')\times distance^2(A,D)\times distance^2(B,C)$

Rules

• The input and output can be given in any convenient format.
• No need to output the two subgroups.
• No need to handle the case when at least two points in the set are the same.
• No need to check the fact that the four points in each subgroup are aligned.
• In your submission, please state the true and the false values.
• Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
• If possible, please include a link to an on-line testing environment so other people can try out your code!
• Standard loopholes are forbidden.
• This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
• As with most problems involving floating point comparisons, I think you should include a large-ish number of test cases and require that submissions pass all of those cases. That way people can be sure their submissions are sufficiently accurate. – FryAmTheEggman Jul 13 '18 at 20:40
• @FryAmTheEggman In fact there is a way to work only with integers, I'll add a hint. – mdahmoune Jul 16 '18 at 10:53
• I had totally missed that the input would always be integers. Cary on, but I still recommend including at least several test cases to make users more able to be sure their submission works without having to find edge cases on their own. – FryAmTheEggman Jul 16 '18 at 14:35
• @FryAmTheEggman Ok I'll add more examples. – mdahmoune Jul 16 '18 at 15:55
• Is the cross ratio $\overline{AC}\times\frac{\overline{BD}}{\overline{AD}}\times\overline{BC}$ or $\frac{\overline{AC}\times\overline{BD}}{\overline{AD}\times\overline{BC}}$? – wastl Jul 18 '18 at 11:31
• @wastl it's the second one, thanks for the remark, I just updated the formula. – mdahmoune Jul 18 '18 at 11:39

The Shifty Maze

You are a wild mouse and you have stumbled on a maze that some human has constructed to observe your behavior. The maze is littered with blobs of peanut butter and has a cache of sunflower seeds near its center. After discovering the seeds, you decide that you want to take them all home to your personal cache. You must find your way to the seeds and exit the maze. Since there are so many seeds, it takes you many trips to get them all.

Things go well your first time. You find your way to the seeds, bring a few back, and return to the maze. To your surprise, when you return the second time, the maze looks nothing like it did before, but you quickly figure out that the entrance was simply in a different place and continue navigating as usual. The next time you return to the maze, you are once again lost, but you find a familiar pattern of peanut butter dabs and find your way to the sunflower seeds once again. Naturally, you catch onto this pattern and eventually retrieve all the sunflower seeds.

The Challenge

Your task is to make a "mouse" bot that navigates through a maze where the entrance moves to somewhere else on the edge of the maze every time you exit and enter it. You have no limits on memory, but no absolute sense of direction and a limited visual field. You can only exit the maze after finding the cache. Your goal is to get all of the seeds in as few steps as possible.

Mazes

A perfect maze is randomly generated using a randomized version of Prim's Algorithm starting from a cell near the center. The seed cache will be close to the center. 10% of the cells will be dabbed with 3-5 units of peanut butter. There will not be any peanut butter on the same cell as the seed cache. The maze used for scoring will be 30x30 cells.

Actions

Each turn, you can move forward or turn 90 degrees in either direction. If there is any peanut butter on your current cell, you may also eat one unit of it instead of moving or turning. (Partially eaten peanut butter can be used to create landmarks for navigation.)

Vision

You can see every cell in a straight line in front of you until a wall obstructs your view. You can also see one cell to your left and right, provided there is no wall between that cell and your current cell.

For each cell that you can see, you can see whether there is a wall on each of the four edges of the cell, how much peanut butter is on that cell, and whether it is the seed cache or the exit.

Example

+-----+-------+-+---+
|     |  5    | |   |
| ----+-- +---+ | --+
|4    |   |@   3    |
| --+-+ --+---- | --+
|   | |    4   <|   |
| --+ | --+ | | +-+ |
|         | | |   | |
| | +-- --+-+ +-- +-+
| | |    3  | |     |
+-+-+-------+-+ ----+


@ is the seed cache. Numbers are blobs of peanut butter. < is the mouse (facing west)

The vision for the mouse would look something like this:

  +-+

+ +
| |
+ +
4|
+ +
|
+-+ + +
|.(^)3
+ +-+ +


No memory limit

You can remember as little or as much as you would like. The challenge is in figuring out where you are as quickly as possible and reduce the amount of time you spend wandering.

Test Driver

The test driver can be found here.

Coding

Your solution should be compatible with Python 3.7. You should implement a class with the following methods:

• A constructor taking no arguments
• get_action, which is called with one argument representing your vision on each step of navigation (more on that below). This should return a string representing the action to take: forward, left, right, or eat are valid values. If this returns an action that cannot be taken, an exception will be thrown and your solution will be considered invalid.
• enter_maze, which is called without arguments each time the maze is entered. No return value is expected and the function doesn't actually have to do anything. The next time get_action is called, you are guaranteed to be on the cell on the edge of the maze facing away from the entrance/exit.

The Vision Object

You will receive an object with the following attributes:

• left and right: the cells to your left and right. If there is a wall that obstructs your view, this will be '???' instead of the cell view object.
• forward: a list of all the cells in your forward vision, starting with your current cell and continuing until the last cell in your vision.

Any of these cell views may also be None, indicating the entrance/exit of the maze.

Each visible cell inside the maze will be an object with the following attributes:

• forward, left, right, back: booleans indicating whether there is a wall in the given directions, oriented the same way as the mouse.
• contents: an integer representing the amount of peanut butter (if any), None (if nothing is on the cell), or 'cache' if the cell contains the seed cache.

Scoring and Rules

• Standard loopholes apply.
• If your bot only works on the scoring maze, it is an invalid solution. Your bot does not receive enough input to distinguish the scoring maze from another maze, so hard-coding a route will produce an invalid solution.
• Run the test driver to score your result. It uses an isolated and seeded random number generator to ensure that all entries get the same maze and sequence of entrances. The total number of turns it took to retrieve all of the seeds (this takes 100 iterations through the maze) is your score.
• You must output a valid move each turn. Moving into a wall or attempting to eat nonexistent peanut butter will result in an error that you have no opportunity to recover from.
• You may not exit the maze until you have visited the cell containing the seed cache since the last time you entered the maze.
• Is it guaranteed that when enter_maze is called, the mouse is on an edge of the maze? – user202729 Jul 20 '18 at 6:54
• @user202729 I should clarify that. Thanks for pointing that out. – Beefster Jul 20 '18 at 16:47

Encoding nested tuples

Related: this

Working on my recent esolang μ6 I found myself a neat puzzle: Given the set of all natual numbers and the set of all nested tuples over the natural numbers, find a bijection between those two sets.

A nested tuple $t \in T$ is recursively defined, it is one of the two:

• an natural ($\ n \in \mathbb{N}_0\$) number itself: $\;t = n$
• a tuple of two nested tuples ($\ t_l,t_r \in T\$): $\;t = (t_l,t_r)$

If it helps you can think of a nested tuple as a binary tree that has only values in its leaves.

Challenge

Your task is to define two programs/functions, let's call them $\ E\$ (encode) and $\ D\$ (decode) which are each others inverses:

Given any natural number $n \in \mathbb{N}_0$ the output $E(n)$ is a unique element of $\ T$ and $\ D(E(n)) = n$.

Given any nested tuple $\ t \in T$ the output $\ D(t)$ is a unique element of $\ \mathbb{N}_0$ and $\ E(D(t)) = t$.

Rules

Inputs to the two programs/functions can be

• an integer or a string representation thereof for $\ E$
• a nested tuple/list, custom data-type1 for $\ D$

Outputs can either be of the same type as the input of the inverse function/program or printed to stdout.

Example

Since you're free to implement any bijection, it's difficult to give meaningful test cases. These are just a few examples using this encoding-function and this decoding-function:

0 <-> 0
1 <-> (0,0)
3 <-> ((0,0),0)
20415 <-> ((1,0),(1,2))
55340232221111877631 <-> ((0,(1,0)),(2,1))
1000000000000000000000000 <-> 500000000000000000000000


1: For example if your language doesn't support nested tuples/lists, you don't need to count its definition towards your byte count. As an example a Haskell submission could assume data T = El Integer | Nest T T.

Sandbox

• Anything unclear?
• Is this maybe too much to ask in a code-golf?
• I could "simplify" it by asking for two $\ E_k$ and $\ D_k$ which would for all inputs $k$ map $\ \mathbb{N_0} \leftrightarrow \mathbb{N_0}^k\$..

Most Turing-incomplete Instruction Set

This challenge expects you to define an instruction set $I = \{ \texttt{instr}_1 \dots \texttt{instr}_n \}$ which is provably Turing complete. The catch is that any subset $I'$ that is proper (ie. $I' \neq I$) must not be Turing complete.

Challenge

Your task is to define some environment (eg. a stack, an unbounded tape, tuples, integers, funcions etc.) over which you have complete freedom to choose, let us call this environment $E$.

To initialize $E$ you will define a way of transforming the source code $s$ and inputs $in_0,\dots,in_r$ to some $E_{initial}$. The same holds for the output of your programming language, you can define the output as any mapping of the end state $E_{end}$ to your output set.

The main task is to find an as large as possible number of instructions which define a Turing complete programming language, but removing any instruction from that set must result in a programming language that is not Turing complete.

An instruction $\texttt{instr}_i$ takes some non-negative number $m$ of arguments and modifies the environment, ie.

$$\texttt{instr}_i : A_0 \times \cdots \times A_m \times E \to E$$

where $A_0,\dots,A_m$ are the sets of valid arguments, you're free to define these as you wish (eg. natural numbers, integers, Booleans, labels etc.).

Submission

• the language specification
• informal proof of validity
• an implementation of the language.

Rules

• this is a and your score will be the number of instructions, the goal is to maximize this number (ties will be broken by favouring the earliest submission)
• your programming language only needs to support input by using some special initial environment $E_{initial}$
• the same holds for the output(s), these only need to be encoded in the final $E_{end}$
• the definitions of $E$ and the way of transforming input/output do not need to be formal (eg. it suffices to just say something along the lines of: "My language works with a stack of integers, initially it will contain all the inputs beginning with the first one at the bottom of the stack. Output will be the top of the stack or zero if it's empty.")
• you will need to provide an informal proof of why your submission is valid, consisting of
• an informal proof of Turing completeness of the instruction set $I$
• an informal proof of why any proper subset of $I$ is not Turing complete
• these proofs may rely on reductions to known Turing complete languages (eg. Turing machines, BitBitJump, brainfuck etc.)

Sandbox

As pointed out by Nathaniel, it is currently possible to get an arbitrary large score.. If anyone has a nice fix that will prevent that (and similar exploits), please leave a comment.

• I like the idea, but the instruction set can easily be made arbitrarily large. E.g. environment starts in state 0. Instruction A1 changes the state to state 1 if it's in state 0, otherwise it's an error. Instruction A2 changes the state to state 2 if it's in state 1, otherwise it's an error. [...] Instruction A1000000 changes the state to state 1000000 if it's in state 999999, otherwise it's an error. Instructions S, K perform as per SK calculus, but only if the environment is in state 1000000. This scores 1000002. – Nathaniel Aug 7 '18 at 12:46
• @Nathaniel: I didn't think of that :( Finding a nice definition/rule to prevent these kinds of exploits will be quite difficult. I'll see what can be done. – ბიმო Aug 7 '18 at 12:51
• For N*'s attack, a function can take binary input and decide one state per input – l4m2 Aug 10 '18 at 15:54
• @l4m2: I thought about that too, it's better than what I have now. But it would still allow an "attack" where you abuse the stack/tape/.., for example: Take a setup with a stack, A1 pushes 1, A2 pushes 2 if ToS=1 else pushes 0, .. A<really-large-number> acts as a Turing-complete instruction when ToS = <really-large-number>-1 and else it acts as clear stack. – ბიმო Aug 10 '18 at 16:08
• Oh and there might be some confusion about state and environment which are not distinguished in that definition. Only allowing moving to one state/environment would prevent a regular add instruction, since the resulting state would be different for a lot of operands. – ბიმო Aug 10 '18 at 16:22
• @OMᗺ It's still covered – l4m2 Aug 10 '18 at 16:30
• @l4m2: But that would mean that there needs to bean infinite amount of states, each configuration of state and tape/stack/.. would be state. Leaving us with the problem that there can't be an instruction put X where X is placed on the tape/stack because it would be different for different Xs. Or am I missing something? – ბიმო Aug 10 '18 at 16:42

Define the structure X as a non-empty array of (smaller) X objects and "1". Split an X object into the smallest amount of continuous parts Y, length of each of Y don't exceed n, so that each X is either part of a Y, or exactly some Ys. It's fine if output only express which part has how many 1's.

Samples:

[1,[1,1,1]],3 => 1;111
[1,[1,1,1]],2 => 1;11;1 or 1;1;11
[[1,1,1],[1,1,1]],1 => 1;1;1;1;1;1
[[1,1,1],[1,1,1]],2 => 11;1;11;1 or etc.
[[1,1,1],[1,1,1]],3 => 111;111
[[1,1,1],[1,1,1]],4 => 111;111
[[1,1,1],[1,1,1]],5 => 111;111
[[1,1,1],[1,1,1]],6 => 111111

• What is a "non-self-contain array"? – user202729 Aug 7 '18 at 15:17
• @user202729 Some languages allow array like A=[A], which is here not allowed – l4m2 Aug 7 '18 at 15:18
• I think you should work on the explanation, it's not very clear without looking at the testcases. Also what about languages that don't allow lists/arrays with different types? Would it be ok to define an appropriate type? Or should input be taken as string? – ბიმო Aug 7 '18 at 18:04

A function to traverse an array and re-generate the same array

We take an array, then write a function that will traverse the array and generate the array in a format given in the example below.

For example, given the array:

Array

(

[0] => Array
( [name] => Tom
[age] => 32
[key] => Array
( [0] => abc
[1] => def
[2] => efg
)
)
[1] => Array
( [name] => Jim
[age] => 30
[key] => Array
( [0] => abc
[1] => def
[2] => efg
)
( [0] => Array
( [state] => CA
[country] => US
)
[1] => Array
( [state] => NY
[country] => US
)
)
)
)


Output should be:

User: 0
name: Tom
age: 32
key:
0: abc
1: def
2: efg
User: 1
name: Jim
age: 30
key:
0: abc
1: def
2: efg
0:
state: CA
country: US
1:
state: NY
country: US


Challenge rules:

• You can assume array can be multidimensional
• The array can also be array of cars, schools, districts etc.
• The preferred output is in json format
• Indentation for the output is a simple json format

code-golf

The function will be tested with any sort of multidimensional arrays for speed of execution

• Can you give a quick explanation of how you generated the array? For example, where does Name come from, and what are the rules behind indentation? – Jo King Aug 9 '18 at 6:17
• The array just contains User details which will include the Name, Age, Address etc. – Mochesane Aug 9 '18 at 6:45
• Hi! Welcome to PPCG. We usually require challenges to be a bit more precisely defined, to avoid ambiguity. For eg., you mention " generate the array in a format given in the example below", and the rules say "the preferred output is in json format" - but the format in the example is not JSON (and has some possible issues, for eg. address not being indented). Also, the post says "array" throughout, but what you're actually working with looks like a nested hashmap/dictionary structure. – sundar Aug 12 '18 at 11:46
• Finally, you've mentioned code-golf, but also that the answers will be tested for speed of execution - do you intend code-golf (number of bytes) to be the primary winning criterion and the speed of execution the tie-breaker? Or do you mean all answers have to transform a particular large input within a certain time (say 1 minute) to be valid? In the latter case, it would be useful to specify what the large, multidimensional input will be, and what the maximum time of execution allowed is. – sundar Aug 12 '18 at 11:46

Game of Circles king-of-the-hill

This is a hidden-identity game with Detectives and Robbers. You will write either a Detective bot or a Robber bot. All Robbers know the identity of all other Robbers. Each turn, a bot must either:

1. Draw a private circle:
• The actual circle drawn is public information
• Detectives receive the number of Robbers in the circle privately
2. Draw a public circle
• The player that draws the circle declares the number of robbers in the circle (may or may not be true)

Finally, the player with the most circles (public or private) around them dies. In the case of a tie, no player dies.

The game ends when a single side has been eliminated or when no players have died for 3 turns.

Each game consists of 17 Detective and 3 Robbers. (META: These numbers I'm not sure about).

The bots that will participate in each game will be chosen using two genetic algorithms. There will be 100 simultaneous games, and the first genetic algorithm will choose the 1700 players for the Detectives, while the second genetic algorithm will choose the 300 Robbers. The fitness function for each bot will be how long they survived in the game (by percentage).

After 1000 rounds, players are ranked by their population (two scoreboards, one for Detectives, one for Robbers)

• Sounds kinda like the Werewolf/Mafia game. Makes me wonder how well The Resistance boardgame will translate to a KotH. – sundar Aug 12 '18 at 11:20
• I don't understand the bit about genetic algorithms though - will the bots that we submit just be the base population for the GA then? Or will there be no mutation or crossover in the GA (in which case it's pretty much not a GA)? That bit needs some more elaboration and possibly some tweaking. – sundar Aug 12 '18 at 11:21
• Yep, this is similar to Werewolf/Mafia. I considered starting out with that, but I thought it might cause some confusion as there is no "nighttime", and robbers have no extra powers outside of knowing all of the other robbers. – Nathan Merrill Aug 12 '18 at 13:41
• The bots will be the base population. Breeding will be asexual (single parent), and mutations means randomly picking a bot. You are right, this isn't a string GA, but it's the best term I could come up with. – Nathan Merrill Aug 12 '18 at 13:43

4B/5B Encoding

To transmit data in binary there's a technique called NRZI where a transition from +V to -V or vice-versa encodes a 1 and the absence of such a transition a 0.

In case there are a lot of 1 s this is a good method because there will be a lot of transmissions and the risk of getting out of sync is smaller, however it's still tricky for long runs of 0. One solution is 4B/5B encoding which takes 4bits and encodes it in 5bits in a way such that there are at most 3 consecutive bits. The encoding is as follows:

0000 -> 11110
0001 -> 01001
0010 -> 10100
0011 -> 10101
0100 -> 01010
0101 -> 01011
0110 -> 01110
0111 -> 01111
1000 -> 10010
1001 -> 10011
1010 -> 10110
1011 -> 10111
1100 -> 11010
1101 -> 11011
1110 -> 11100
1111 -> 11101


Challenge

Given an bytestring, you will need to encode it with the aforementioned encoding.

Rules

• Input will be a bytestring
• to avoid padding-issues, it will always have a length that is a multiple of 4 bytes
• Output will be of the same a bytestring
• You may not assume that input (nor output) is printable

Examples

Note: You need to handle both printable and unprintable examples!

ASCII examples

ORLY -> WWEis
OBMO -> WUEm]
SSePCcGG -> ]WW-~U]U=O
aHAHaHAHaHAHaHAHaHaO -> rU%%RrU%%RrU%%RrU%%RrU'%]
S#KPOCFWcSaOCR!@sz!\q9OKqY!L -> ]iU]~WUU9ouWW%]UWJ%^}_j%zzk5uWzW:%Z


c0 ff ee 00 -> d7 bb de 73 de
66 6f 6f 00 -> 73 9d d7 77 de
50 50 43 47 -> 5f 97 e5 55 4f
48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 21 00 00 00 -> 54 9c b7 69 da 77 69 aa 79 6f 77 5f 47 69 ca a2 7d ef 7b de


Drat! This was actually run three years ago! See Implement INTERCAL's Binary Operators

Mingle and Select

The programming language INTERCAL has two operators, "mingle" or "interleave" (represented by $), and "select" (represented by ~). Mingle takes two 16-bit values and produces a 32-bit value by taking single bits alternately from its left and right operands, and concatenating them together - for example, 65535$ 0 will yield -1431655766 as follows: 65535 is 0xFFFF, or 0b1111111111111111; 0 is 0b0000000000000000. Taking the bits alternately gives 0b10101010101010101010101010101010, or 0xAAAAAAAA, which evaluates to the signed integer -1431655766.

A simplified implementation of Select takes two 32-bit operands, and produces a 32-bit value by comparing the bits in the two operands, and wherever the right operand has a 1 bit, take the corresponding bit from the left operand. The resulting bits are compressed to the right, and zero-filled on the left - for example, an 8-bit version of select, given 79 ~ 42, would return 3, as follows: 79 is 0b01001111, and 42 is 0b00101010. Numbering the bits from the left starting with 1, we need to take the third, fifth, and seventh bits of 79, which are 0, 1, and 1, respectively. We then compress them to the right - 011 - and zero-fill, yielding 0b00000011, or 3.

The challenge

Without using INTERCAL, and without using in any other language any operator builtin that amounts to either mingle or select, implement both operators. You may implement them for 16- or 32-bit integers, and as either operators or functions, but input and output must be UNsigned decimal integers. (I'm not going to require input or output in INTERCAL-style insanity!)

Further constraint: The minimum bit width of the operands must be 16 bits for mingle (no constraint for select), and if they are unequal in width, the shorter is zero-filled on the left to match the width of the longer (zero fill applies to both mingle and select).

test cases to be written and inserted here

This is , so shortest solution in each language 'wins'. (Naturally, the standard loopholes are forbidden.)

• "You may implement them for 16- or 32-bit integers, and as either operators or functions, but input and output must be signed decimal integers." This puts languages such as CJam which only have unbounded integer types at a disadvantage. Is that intended? – Peter Taylor Aug 13 '18 at 11:03
• @PeterTaylor - The intent here is not to exclude or disadvantage any particular language (other than INTERCAL), but to 'force' zero-fill on select, and return negative values for some cases of mingle. Would it be better to say that values returned must be some power of 2 times 16-bits wide? – Jeff Zeitlin Aug 13 '18 at 11:32
• I'm not sure why an integer width is necessary for select: just say that it's zero-filled and make sure that the corner case of a ~ -1 (the only way that there's nothing to fill) is covered by test cases for a positive, zero, and negative. – Peter Taylor Aug 13 '18 at 11:49
• For mingle, it seems to me that if the operands are really 16-bit values then the example should be -1 $0, and if you require the output to be negative iff the first operand is negative then it easily generalises to unbounded integer types. However, the result of -1$ 0 in an unbounded type is unbounded, so there is a genuine problem there. I suggest mentioning that briefly as a rationale for why languages without bounded integer types must nevertheless implement a bounded mingle. – Peter Taylor Aug 13 '18 at 11:52
• @PeterTaylor - but zero-filled to what width? One could argue that if an arbwidth is allowed, then no zeros need to be added, and 79 ~ 10 could validly be argued to be -1. – Jeff Zeitlin Aug 13 '18 at 11:52
• To infinite width. The most significant bit is effectively a sign bit. – Peter Taylor Aug 13 '18 at 11:57
• @PeterTaylor - Good catch on 65535 vs -1. I think that this and the arbwidth problem can be addressed by simply changing the 'signed' constraint to 'unsigned'. – Jeff Zeitlin Aug 13 '18 at 12:06
• But how do I tell the (selected) MSB from presumed zero-filling? Is 79~10 equal to 3, or to -1? – Jeff Zeitlin Aug 13 '18 at 12:07
• UPDATE: Constraints changed. – Jeff Zeitlin Aug 13 '18 at 12:19
• "But how do I tell the (selected) MSB from presumed zero-filling?" The answer would have been that you can only get a negative result if both operands are negative, but now that you've changed to unsigned this is no longer an issue. – Peter Taylor Aug 13 '18 at 13:44
• @PeterTaylor - It's been rendered academic; the challenge has already been run - see codegolf.stackexchange.com/questions/54412/… – Jeff Zeitlin Aug 13 '18 at 18:30

Delimiter-Chaos

Write a program of at most 150 bytes length that produces different outputs (to stdout) if you insert token-delimiters into the source code.

Score

The program with the highest number of different outputs wins.

Rules

For this challenge, we assume that the source code is tokenized prior to compilation/ interpretation. A delimiter is any character which, when inserted at a given position, changes the way the source code is tokenized, but is not part of a token on its own.

Example

(python)

a = "0"
b = "0"
ainb="12"
print(ainb)


This prints 12. If you insert two spaces, you get:

a = "0"
b = "0"
ainb="12"
print(a in b)


which prints "True"

This gives a total score of 2 for 2 (known) different outputs

Rule clarifications

• Only program versions that exit with zero error code count towards the score.
• All versions have to be listed explicitly in the answer.
• Put the score into the title of the answer.
• If your code produces different outputs in different programming languages, they count.

Write in Ge'ez!

Ge'ez is a now-dead language used for liturgy in the Ethiopian Orthodox Church. It's traditionally written in a very distinctive script with many loops and curves. But for ease of reading, it's often transliterated into Latin letters.

Your task here is to take some writing in Latin characters and convert it to the Ge'ez script. For example, the input gəʿəz (the name of the language) should give the output ግዕዝ.

Details

Every letter in the Ge'ez script represents both a consonant and the following vowel. There are eight vowels

ä u i a e ə o wa


and twenty-six consonants

h l ḥ m ś r s ḳ b t ḫ n ʾ k w ʿ z y d g ṭ p̣ ṣ ḍ f p


which give 208 combinations. (In reality, some of these combinations like "wwa" don't actually happen, and there are some extra letters like "mya" not covered by this system, but ignore all that for the purposes of the challenge.)

The combinations are encoded in a convenient way in Unicode. The consonant defines the starting position, and the vowel defines the offset.

C    start (hex)
----------------
h    1200
l    1208
ḥ    1210
m    1218
ś    1220
r    1228
s    1230
q    1240
b    1260
t    1270
x    1280
n    1290
ʾ    12A0
k    12A8
w    12C8
ʿ    12D0
z    12D8
y    12E8
d    12F0
g    1308
ṭ    1320
p̣    1330
ṣ    1338
ḍ    1340
f    1348
p    1350

V    offset
-----------
ä    +0
u    +1
i    +2
a    +3
e    +4
ə    +5
o    +6
wa   +7


(Again, reality is a bit more complicated, but ignore that for the challenge.)

Your task is to take a string written in Latin letters, and output the corresponding Ge'ez syllables. If a consonant is followed by a vowel, add the consonant's start point to the vowel's offset, and print the corresponding Unicode character. If a consonant is not followed by a vowel, use the start point with no offset (as if the vowel were ä).

Input is a Unicode string, or a list of Unicode codepoints as integers. Output is a Unicode string, or a list of Unicode codepoints as integers. A "Unicode string" here can be in any official encoding (UTF-7, UTF-8, UTF-16, UTF-32…). NFC and NFD are both acceptable.

This is code golf; shortest code (in bytes) in each language wins. Standard loopholes forbidden.

Test cases:

gəʿəz    ግዕዝ
[TODO more to come here]

• One option would be replacing the Unicode characters in the input with ASCII digraphs. Would this make the challenge better? – Draconis Aug 25 '18 at 3:15

Pyramid of Bots

In this game, your bot is trying to get as high off the ground as possible. However, it can only stand on top of other bots, which are trying to get higher, too!

Overview

Your bot should be a Javascript function. It's return value should tell the program if the bot should move left, move right, or jump. Every bot starts out on a 2 dimensional grid, with a width and height set by (botCount * 2) + 1. Bots are placed on either side of the center space, and every other bot is spaced 1 apart from any other bot. They all start at y=0, and far left is x=0.

Gravity

If there is no bot on top of your bot, it can return the value jump. When a bot jumps, it moves 1 square up. If at any point in time there is nothing under the bot, it moves down 1. A bot cannot return jump if nothing is under it. If your bot is on top of another bot which moves left, your bot will fall.

Function params

Your function has 3 parameters: dirs, height, and map. The array dirs contains four boolean values, representing if there is a bot or arena border: below, to left, to right, above. The parameter height is an array with 2 elements: your height, current winner's height. The map array contains the height/width of the array, and then the amount of turns left in the game.

Running the game

In one game, the bot function will be run 800 times. Each of these is a turn. Your bot should return jump, or a direction. The bot can only move in a direction if there is no bot currently there. The two directions are left and right. Standard loopholes are not allowed (when are they ever allowed??), and the bot who wins the most out of 1000 games is the winner.

• I don't see the strategy in this. There's no way for a bot to reliably move up. No bot will stand still, so you literally have to guess whether or not an adjacent bot will move under you, and then hope that they move up while other adjacent bots move under. – Nathan Merrill Aug 27 '18 at 16:21

Cleanup after Easter

As most people (probably) know, Easter was about a month ago. But around the community park, there're still some eggs hidden! Can you build a (Javascript only, please) bot to help us find them?

The Course:

The bots will compete on a 201 by 201 field, with coordinates ranging from (-100,-100) to (100,100). All bots will start at (0,0) and will begin. The course has 3 types of areas: wall, egg, and grass.

Finding Eggs:

You will build a function to find the Easter eggs. To see, use the function checkZone(x,y). The ouputs are:

0=Grass
1=Wall
2=Egg
3=Bot


To find a player, use findPlayer(name) (Returns coordinates array) or detectPlayers(x,y) (Returns name or null). If your bot lands on a spot with an egg, it will not be able to pick it up until it uses the function fetchEgg(). If there is not an egg, your turn will stop.

Moving:

Moving is done by returning a string. This string can be north, south, east, west, or none. Assume that directions are like a compass placed on a Cartesian plane:

North=Y+1
East=X+1
South=Y-1
West=X-1


Winning:

When all eggs are found, the game is over. If you move North to an egg, you must pick it up on the next turn in order to obtain it. If you try to move into a wall, nothing will happen. To get your current position, use getLocation(), which returns an array [x,y]. Use getBasket() to get how many eggs you have. The course will be designed so that all eggs are accessible, but some may be hard to get. If an egg is found by two bots in the same turn, each bot get 0.5 added to their basket, as they split the reward.

Functions list:

checkZone(x,y): Returns an integer, takes 2 integers as parameters between -100 and 100
0=Empty
1=Wall
2=Egg
findPlayer(name): Takes string as parameter, returns player's position as an array of integers or null if player is nonexistant
detectPlayers(x,y):  Returns an array of player names, takes 2 integers as parameters between -100 and 100
fetchEgg(): Fetches egg in current position if exists
getLocation(): Returns array with x and y coordinates
move functions: Returns true or ends turn (Ends turn if cannot move)


Example:

function rabbitInDisguise() {
var loc = getLocation();
if (getLocation(loc[0], loc[1]) == 2) {
fetchEgg();
} else {
if (getLocation(loc[0], loc[1] + 1)) {
moveNorth();
} else {
moveEast();
}
}
}


UPDATE 1: Added findPlayer(name) and detectPlayers(x,y) functions, made locating functions "background", and added simultaneous egg finding rules

• 1. I don't see the competition here. I find egg, and I grab it as fast as I can. 2. You don't describe what other players look like. – Nathan Merrill Apr 18 '18 at 15:05
• @NathanMerrill Whichever bot is best at searching for the eggs will win. If Bot A moves in circles around the board, but Bot B scans a 5 x 5 area around it and makes a map, who do you think would win? Also, what do you mean by "You don't describe what other players look like." – Redwolf Programs Apr 18 '18 at 15:08
• @user202729 Mistype...I'm about to fix it – Redwolf Programs Apr 18 '18 at 15:09
• And how does program interact with each other? Is there any limit on how many (library) function call can be done in each function? – user202729 Apr 18 '18 at 15:12
• it cannot run more than one function per turn – Redwolf Programs Apr 18 '18 at 15:16
• 2. You said that 0=grass, 1=Wall, and 2=Egg. What does a player look like? 1. Right, let me check all the locations nearest me, and walk to the closest one. (You can slightly improve on this by identifying eggs that other players will go for). it cannot run more than one function per turn: Your example bot breaks that. – Nathan Merrill Apr 18 '18 at 15:17
• Players are invisible, since it could complicate things. I'll edit to address the problems, though. – Redwolf Programs Apr 18 '18 at 15:18
• If players are invisible, then this is not a KotH. This is a code-challenge to retrieve the eggs as fast as possible. – Nathan Merrill Apr 18 '18 at 15:19
• @NathanMerrill Fixed. Players can be found using findPlayer() and detectPlayers() – Redwolf Programs Apr 18 '18 at 15:27
• So they can investigate the whole board in one turn? Sounds more interesting then. – user202729 Apr 18 '18 at 15:40
• @user202729 I think moveRandom() would be fine (It just makes it easier to program), but I'll add more info on the functions. – Redwolf Programs Apr 18 '18 at 15:45
• @user202729 Good point. Feature eliminated. – Redwolf Programs Apr 18 '18 at 15:51
• Any other problems you can think of? – Redwolf Programs Apr 18 '18 at 15:54
• @PeterTaylor (what does KISS stand for?) – user202729 Apr 19 '18 at 13:58
• @user202729, softwareengineering.stackexchange.com/a/87/13258 – Peter Taylor Apr 19 '18 at 14:02

Compute strings with a fixed distance

Consider a binary string of total length N. For example 000111000111 with $N=12$. We can store this string more efficiently by just recording the indices where bits are first flipped. In this case $(3, 6, 9)$ is sufficient information to reproduce the string. Here are some more examples using this representation:

10101010 is represented inefficiently by (0, 1, 2, 3, 4, 5, 6, 7)
1111100000 is represented by (0, 5)
0000011111 is represented by (5)


Let us call this representation of a string its compressed representation (even though sometimes the compression is worse than doing nothing).

Now recall the Levenshtein distance between two strings. This is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.

Given a compressed representation of a string $S$ of uncompressed length $N$ and two positive integers $k$ and $d$, the task is to output the compressed representation of $k$ distinct strings of uncompressed length $N$, each with Levenshtein distance exactly $d$ from $S$. If there are not that many distinct strings possible, simply output as many as possible.

Your code must run with $N = 1000000$ and $k, d < 20$ in less than a minute on a normal desktop PC.

• I feel like I'm missing something here. Everything above "Task" is clear, but I don't understand what's going on below. If S = "0000", k = 1, and d = 1, then I simply print out one of "1000", "0100", "0010","0001" (in compressed format)? – Nathan Merrill Aug 30 '18 at 20:09
• @NathanMerrill Yes. It’s less trivial with other starting strings and larger d. – Anush Aug 30 '18 at 20:26
• Right. There seems to be two parts to this challenge then: Iterating through Levenshtien mutations, and converting to/from the compressed representation. Unless I'm missing how they are related, I'd argue that you remove one of the parts. – Nathan Merrill Aug 30 '18 at 20:32
• It appears that iterating Levenshtien mutations would be a duplicate – Nathan Merrill Aug 30 '18 at 20:33
• @NathanMerrill Thanks for the possible dupe link. For your first comment, the idea was to do it without first uncompressing. I will try to improve the question. – Anush Aug 31 '18 at 9:10

Definition

Let f(n) be the sum of the sums of each possible factor permutation of n. Determine (Y f)(n) (a fixed-point combinator) for all n from 2 to the input i (where i is an integer greater than 2).

Example

A quick example of f(n) first:

f(8) = (2 + 2 + 2) + (2 + 4) + (4 + 2) + (8)
f(8) = 26


An example of (Y f)(n):

(Y f)(8)
f(8) = 26 (shown above)
f(26) = (2 + 13) + (26) = 41
f(41) = (41) = 41
(Y f)(8) = 41


Let g(i) define a function which implements the described problem.

g(2)
2

g(4)
2
3
41

g(8)
2
3
41
5
11
7
41


Competition

This is a challenge, which means that the solution with the lowest asymptotic time complexity (in Θ(...)) wins!

In the case of a tie, the winner will be determined by rules, so please submit an implementation of your code along with the algorithm. Tie-break will occur on a Google Compute Engine n1-standard-8 instance.

• In your example of f(8), why do you include 1 in (8+1)? Should it not be just (8)? I could make (2+2+2) into (2+2+2+1). – Don Thousand Sep 3 '18 at 16:22
• @RushabhMehta You're entirely correct! My bad, let me fix that. – Addison Crump Sep 3 '18 at 16:27
• I'm also pretty sure that in your system, the only fixed points are prime numbers. Is that desired functionality? – Don Thousand Sep 3 '18 at 16:33
• @RushabhMehta See the title. :P – Addison Crump Sep 3 '18 at 16:45
• Finally, I would mention that permutations are distinct, just so that its obvious how you are counting all the different factors. – Don Thousand Sep 3 '18 at 16:47
• @RushabhMehta Is that a sufficient change? – Addison Crump Sep 3 '18 at 16:49
• That should be fine. Nice challenge! – Don Thousand Sep 3 '18 at 16:52
• 1. What's a factor permutation? 2. I doubt anyone can give even a moderately tight analysis of the runtime for an implementation of g without a very tight analysis of the output of f, so I don't think it makes sense to post this without first editing in tight bounds on the output of f. – Peter Taylor Sep 5 '18 at 10:18

Bijective base banana to decimal

I'm trying to decide between 2 versions of this challenge:

Prefixes version

Let bijective base banana be bijective base 6 with each digit represented by a different prefix of the word "banana" as follows:

1: "b"
2: "ba"
3: "ban"
4: "bana"
5: "banan"
6: "banana"


The input will be a string made up of a concatenation of zero or more of only these strings. This represents a number in bijective base 6 (with most significant digit first).

The output will be the same number in (non-bijective) decimal.

For example: (input : output)

"" : 0
"b" : 1
"bb" : 7
"bbanana" : 12
"bananab" : 37
"bananabanana" : 42


A worked example:

bananabanbana
banana ban bana
6      3   4
6*36 + 3*6 + 4*1
216  + 18  + 4
238


This is code golf, so the winner for each language is the code with the fewest bytes.

Suffixes version

Let bijective base banana be bijective base 6 with each digit represented by a different suffix of the word "banana" as follows:

1: "a"
2: "na"
3: "ana"
4: "nana"
5: "anana"
6: "banana"


The input will be a string made up of a concatenation of zero or more of only these strings. This represents a number in bijective base 6 (with most significant digit first).

The output will be the same number in (non-bijective) decimal.

For example: (input : output)

"" : 0
"a" : 1
"aa" : 7
"abanana" : 12
"bananaa" : 37
"bananabanana" : 42


A worked example:

bananaananana
banana ana nana
6      3   4
6*36 + 3*6 + 4*1
216  + 18  + 4
238


This is code golf, so the winner for each language is the code with the fewest bytes.

Sandbox questions

• Is this a duplicate or near enough a duplicate to be worth changing?
• Are there any flaws that would make the challenge uninteresting?
• I'm considering changing from prefixes to suffixes following this comment from H.PWiz
• I currently prefer the suffixes version, but the worked example shows that the interpretation is no longer unique. It would either need to be specified that the match must be greedy (or non-greedy) or a different word would need to be chosen. I lean towards choosing a word which still gives enough ambiguity to force looking ahead, while still keeping the overall conclusion unique. I can't see a way of doing this without making the last character unique though, which reduces to a reversed version of the prefixes version (you can still ignore all other letters).
• This is interesting, but I can't help but feel like this is two problems glued into one. – Don Thousand Sep 3 '18 at 16:27
• It's definitely 2 problems glued onto 1. What I'm wondering is will that make for additional golfing opportunities in at least some languages? I suspect it will, and I'd expect myself to underestimate the possibilities since there are many more insightful people tackling challenges, in many languages. – trichoplax Sep 3 '18 at 17:58
• Hmm, It seems like all that matters is where the bs are. I wonder if it would be a more or less interesting challenge with a different word – H.PWiz Sep 3 '18 at 18:18
• Good point. Suffixes instead of prefixes might give a bit more of a challenge. As long as the output is still guaranteed unique – trichoplax Sep 3 '18 at 18:34
• @trichoplax I'm pretty sure you can't do suffixes, since its no longer unique. – Don Thousand Sep 3 '18 at 20:24
• @RushabhMehta yes it stops working for the word "banana" then (I added a note about this in my 4th sandbox point). It would still work for words that don't contain any of their own suffixes as non-suffix substrings. Like "aardvark". I'm not sure which way to go yet – trichoplax Sep 3 '18 at 20:37
• @trichoplax Your last bullet was exactly my issue. Suffixes don't help at all. – Don Thousand Sep 3 '18 at 22:34

Facto-RLE

Given a non-empty string containing non-numeric printable ASCII characters, compute its facto-run-length encoded version.

Definition

Let $S$ be a non-empty string of length $l\in\mathbb{N}^+$ containing non-numeric printable ASCII characters. For each positive factor $n|l$ one can represent $S$ as a $n\times(l/n)$ matrix of characters. Let $M^n$ denote these matrices.
For a given $n$ and $j\in\{1,\dots,l/n\}$, let $C^n_j$ be the string representing the $j$-th column of $M^n$. Let $E^n_j := \text{RLE}(C^n_j)$ denote the array of this string's run-length encoded version.
Let $R^n := \text{CNCT}(\text{ZIP}(E^n_1,\dots,E^n_{l/n}))$ denote the string representation of all $E^n_j$ zipped together.
The facto-run-length encoding of $S$ is defined as the string array $\text{FRLE}(S):=[R^n:n|l]$.

For a family of $k\in\mathbb{N}^+$ arrays $A^i$ with respective lengths $l^i, i\in\{1,\dots,k\}$ and elements $A^i_j,j\in\{1,\dots,l^i\}$, let $Z_j:=[A^i_j:i\in\{1,\dots,k\}\land j\leq l_i]$ denote the array of elements with index $j$, if present. Furthermore, define $\text{ZIP}(A^1,\dots,A^k) := Z_1\Vert\dots\Vert Z_{\max\{l_i\}}$ as the concatenated array of all $Z_j$.
For an array of strings $A$ of length $j$, define $\text{CNCT(A)}:=A_1\Vert \dots\Vert A_j$ as the concatenation of all strings of $A$.

Example

Let $S:=\text{"Hello world!"}$, therefore $l=12$ with positive factors $\{1,2,3,4,6,12\}$. $$M^2=\begin{pmatrix} \text{H}&\text{e}&\text{l}&\text{l}&\text{o}&\text{ }\\ \text{w}&\text{o}&\text{r}&\text{l}&\text{d}&\text{!} \end{pmatrix}, \\C^2_1=\text{"Hw"}, C^2_2=\text{"eo"}, C^2_3=\text{"lr"}, \\C^2_4=\text{"ll"}, C^2_5=\text{"od"}, C^2_6=\text{" !"}, \\E^2_1=[\text{"H"},\text{"w"}], E^2_2=[\text{"e"},\text{"o"}], E^2_3=[\text{"l"},\text{"r"}], \\E^2_4=[\text{"l2"}], E^2_5=[\text{"o"},\text{"d"}], E^2_6=[\text{" "},\text{"!"}], \\R^2=\text{"Hell2o word!"}$$

$$M^4=\begin{pmatrix} \text{H}&\text{e}&\text{l}\\ \text{l}&\text{o}&\text{ }\\ \text{w}&\text{o}&\text{r}\\ \text{l}&\text{d}&\text{!}\\ \end{pmatrix}, \\C^4_1=\text{"Hlwl"}, C^4_2=\text{"eood"}, C^4_3=\text{"l r!"}, \\E^4_1=[\text{"H"}, \text{"l"}, \text{"w"}, \text{"l"}], E^4_2=[\text{"e"}, \text{"o2"}, \text{"d"}], E^4_1=[\text{"l"}, \text{" "}, \text{"r"}, \text{"!"}],\\ R^4=\text{STR}([\text{"H"},\text{"e"},\text{"l"},\text{"l"},\text{"o2"},\text{" "},\text{"w"},\text{"d"},\text{"r"},\text{"l"},\text{"!"}])=\text{"Hello2 wdrl!"}$$

$$M^{12}=\begin{pmatrix} \text{H}\\ \text{e}\\ \text{l}\\ \text{l}\\ \text{o}\\ \text{ }\\ \text{w}\\ \text{o}\\ \text{r}\\ \text{l}\\ \text{d}\\ \text{!}\\ \end{pmatrix}, \\C^{12}_1=\text{"Hello world!"}, \\E^{12}_1=[\text{"H"},\text{"e"},\text{"l2"},\text{"o"},\text{" "},\text{"w"},\text{"o"},\text{"r"},\text{"l"},\text{"d"},\text{"!"}], \\R^{12}=\text{"Hel2o world!"}$$

Therefore the following follows. $$\text{FRLE}(\text{"Hello world!"}) = [\dots, \text{"Hell2o word!"}, \dots, \text{"Hello2 wdrl!"}, \dots, \text{"Hel2o world!"}]$$

Tags code-golf, array-manipulation, string

• If you can't think of a way to put it into words, you could put it into code, and then someone here can translate that reference implementation into a description. Plus you can then include the reference implementation in the spec for people who read code better than prose – trichoplax Sep 4 '18 at 19:13
• Okay,I can do that! – Zacharý Sep 5 '18 at 13:50
• @Zacharý I have attempted to write a task definition. If this is not what you intended, you can simply roll back. – Jonathan Frech Sep 7 '18 at 3:37
• By the way, I think giving a factor as input would be a nicer challenge than adding a wrapper to encode for every factor. – Jonathan Frech Sep 7 '18 at 3:40
• @JonathanFrech, there isn't universal agreement on the meaning of zip applied to a non-square 2D array, so you need to define it unambiguously. – Peter Taylor Sep 7 '18 at 10:13
• @PeterTaylor Attempted to do so. I intend to only zip one-dimensional arrays. – Jonathan Frech Sep 7 '18 at 10:46
• Thanks! I think this definition works! – Zacharý Sep 7 '18 at 14:58

I have an idea for a KOTH challenge (that is marginally similar to the current Reaper KOTH), but none of the expertise required to make it work. The idea is based on the card game Diamant aka Incan Gold, and the rules of the game are:

• The game is played over 5 expeditions, each with the same structure.
• At the start of each expedition, a special deck of cards is shuffled, containing gem cards and hazard cards (and in some versions of the game, one artifact card is added to the deck every expedition).
• Every turn, a card is revealed from the deck.
• If a hazard card is revealed and another copy of the same hazard has already been revealed in the expedition, the expedition immediately ends and all remaining players lose their accumulated gems. The revealed hazard card is removed from the deck for future expeditions.
• If a gem card is revealed, the number of gems shown on the card is shared evenly between remaining players, with any remainder placed in a common pool.
• After the card is revealed, if the expedition has not ended, then players simultaneously decide whether they want to "Stay" or "Go Home".
• All players who choose "Go Home" share the gems in the common pool between them (leaving any remainder), and then bank all of their gems. They are no longer in the expedition.
• If a single player chooses "Go Home", they claim all of the gems in the common pool plus any artifacts that were revealed.
• If there are players remaining in the expedition, then a new turn begins.
• If there are no players remaining in the expedition, then the expedition ends.
• If this was the last expedition, then players count up the gems they banked plus bonus gems for artifacts they claimed, and the player with the most gems wins.

My thought is that we could simplify the game for KOTH - one expedition, no artifacts - and run games which pit 4 bots against each other in some configuration, with each bot's overall rating being its average score per game.

The problem is that I have no experience in any meaningful programming languages. The other problem is that I don't know how to run a contest like that. The other other problem is that I don't know whether it's worth running.

Can anyone offer assistance or advice on any of those three problems?

• For problem 1, there are 2 optinos, either ask somebody else to write the bot (if the challenge is interesting enough), or to learn a programming language. – user202729 Sep 14 '18 at 5:32

My Ribosomes Got a Firmware Upgrade

So all of the Apple iBosomes in my body have been updated to RibOS 4.0 now… while I appreciate the additional optimizations that were added, unfortunately for me they've dropped support for the legacy mRNA API.

So since my RNA Polymerase library still needs to return strings in the format AUUCGGUCAAAGU for the code still using it, I'll need to add some code to the getBasePairs() method to translate it from the new API.

Challenge

• Your input will be a string in base64 (because codons are exactly 6 bits) representing the genome.
• You should output a string with the equivalent RNA base pair sequence:
• 00 becomes A.
• 01 becomes G.
• 10 becomes C.
• 11 becomes U.
• All languages are allowed.
• Your I/O must be in these exact string formats, even if they're small enough to encode as integers.
• The shortest answer in bytes wins.
• Are you asking for a method that does a base64 to base4 conversion and pretty-prints the result? – Jonathan Frech Sep 18 '18 at 21:15
• @JonathanFrech Kinda, I guess. – Nissa Sep 18 '18 at 21:17
• So using lax I/O I can take the input as an integer and output four unique values like this? – Jonathan Frech Sep 18 '18 at 21:21
• @JonathanFrech wasn't what I had in mind; I'll edit the proposal once I finish the essay I'm working on right now. – Nissa Sep 18 '18 at 21:26

Output the answer after yours code-golfstack-exchange-api

Related: Output the answer above yours

This challenge is very similar to the above, but I hope it's different enough to warrant posting. The difference is that you need to post the answer that is posted after yours (the whole answer, not just the <code> block). Also, your output can be the answer text or the HTML code of the answer. When your post is still the newest post, your program should just output nothing.

Rules

1. No URL Shorteners
2. No programs that need to be run at a specific URL.

I think mine is different enough from the linked question, because that has some different rules, and my version closes loopholes used on the other question. Also, no one utilizes the StackAPI on that one.

Put +, -, * into 1 _ 2 _ 3 ... n to make the expression equal 0, for a given 3 <= n <= 30, and output the valid equation (0=1+2-3). Exactly one operator between each number.

There exists some patterns, such as ((1-2)-(3-4))+((5-6)-(7-8))... and 1+((2-3)-(4-5))+(6-7). Maybe we can find patterns that solve the whole problem?

There are no solutions without * for at least n={5,6,9,10,13,14,17,18,21,22}, so it looks like we need * for n=4x+1 and n=4x+2.

There are no solutions without + for n < 18.

There are no solutions without - (obviously).

Brute-forced examples:

1. 0=1+2-3
2. 0=1-2-3+4
3. 0=1*2-3-4+5
4. 0=1+2*3+4-5-6
5. 0=1+2-3-4+5+6-7
6. 0=1*2*3+4-5-6-7+8
7. 0=1-2+3*4*5+6-7*8-9
8. 0=1-2*3+4*5-6*7+8+9+10
9. 0=1*2+3*4+5*6-7*8-9+10+11
10. 0=1-2+3*4-5*6-7-8*9+10*11-12
11. 0=1+2*3+4+5-6-7-8+9+10+11-12-13
12. 0=1*2+3*4+5*6+7+8*9+10-11*12+13-14
13. 0=1-2-3-4-5-6-7+8-9+10-11+12-13+14+15
14. 0=1*2*3*4*5*6+7+8-9*10*11-12+13+14+15*16
15. 0=1*2*3*4*5*6+7*8*9+10-11*12*13+14*15+16*17
16. 0=1*2*3*4*5*6-7*8-9-10-11*12-13-14*15-16*17-18
17. 0=1*2*3*4*5*6-7-8-9*10-11-12-13-14-15*16-17*18-19
18. 0=1*2*3*4*5*6-7-8-9*10-11-12-13*14-15-16-17-18*19-20
19. 0=1*2*3*4*5*6-7-8-9-10-11-12*13-14-15-16-17-18-19-20*21
20. 0=1*2*3*4*5*6-7-8-9-10-11*12-13-14-15-16-17-18-19-20*21-22
21. 0=1*2*3*4*5*6*7-8*9-10*11-12-13*14-15*16*17-18-19-20-21-22*23
22. 0=1*2*3*4*5*6*7-8*9*10-11-12-13-14*15*16-17-18-19*20-21*22-23-24
23. 0=1*2*3*4*5*6*7-8*9*10-11-12*13*14-15*16-17-18*19-20*21-22*23-24*25
24. 0=1*2*3*4*5*6*7*8-9*10*11-12*13*14-15*16*17-18*19*20-21*22*23-24*25*26
25. 0=1*2*3*4*5*6*7*8-9*10*11-12-13*14*15-16-17-18*19*20-21-22*23*24-25*26*27
26. 0=1*2*3*4*5*6*7*8*9-10-11*12*13*14*15-16-17-18-19-20-21*22-23*24-25*26-27*28
• Related Also, do you want this to be code golf (shortest code) or a different type of challenge? – geokavel Sep 23 '18 at 21:15
• – user202729 Sep 26 '18 at 15:22
• @user202729 yep. Unlike that one, this doesn't allow turning the 1 negative, which does seem to make the problem unsolvable without multiplication. – Filip Haglund Sep 26 '18 at 15:52